Computer Security Resource Center

Computer Security Resource Center

Computer Security
Resource Center

This is an archive
(replace .gov by .rip)

Automated Combinatorial Testing for Software

Testing Event Sequences

SEQUENCE COVERING ARRAY LIBRARY 

Many testing problems involve sequences of operations. For example, an embedded system may accept multiple sensor inputs and generate output to several communication links and effectors such as machine controls. It is important to test combinations of connected components, but also to test the order in which they could be connected. There is an empirical basis for the use of sequence covering arrays. In reviews of various failure reports, when sequences of events were involved, the critical condition for triggering failures generally was whether or not a particular event had occurred prior to a second one, not necessarily if they were back to back. In other words, the report might say something like 'failure occurred when <event A> if B is already connected'. So it appeared that A didn't have to immediately follow B, but the fact that it followed B at some point after B had already occurred was sufficient to trigger a failure. Sequence covering arrays, as we have defined them, ensure that any t events will be tested in every possible order. 

For example, we may have a factory automation system that uses certain devices interacting with a control program. For this problem we can define a sequence covering array, which is a set of tests that ensure all t-sequences of events have been tested. The t events in the sequence may be interleaved with others, but all t-way permutations will be tested. We want to test the following events: 

Event

Description

a

connect air flow meter

b

connect pressure guage

c

connect satellite link

d

connect pressure readout

e

engage drive motor

f

engage steering control

There are 6! = 720 possible sequences for these six events, and the system should respond correctly and safely no matter the order in which they occur. Operators may be instructed to use a particular order, but mistakes are inevitable, and should not result in injury to users or compromise the mission. We want to test this system as thoroughly as possible, but time and budget constraints do not allow for testing all possible sequences, so we will test all 3-event sequences. With six events, a, b, c, d, e, and f, one subset of three is {b, d, e}, which can be arranged in six permutations: <b d e>, <b e d>, <d b e>, <d e b>, <e b d>, <e d b>. A test that covers the permutation <d b e> is: <a d c f b e>; another is <a d c b e f>. With only 10 tests, we can test all 3-event sequences: 

Test

Sequence

1

a

b

c

d

e

f

2

f

e

d

c

b

a

3

d

e

f

a

b

c

4

c

b

a

f

e

d

5

b

f

a

d

c

e

6

e

c

d

a

f

b

7

a

e

f

c

b

d

8

d

b

c

f

e

a

9

c

e

a

d

b

f

10

f

b

d

a

e

c

(Keep in mind that this example is small for convenience. A real system may have, for example, 10 devices to connect, in which case the number of permutations is 10!, or 3,628,800 tests for exhaustive testing. In that case, a 3-sequence covering array with 14 tests would be a much more dramatic improvement.) 

Definition. We define a sequence covering array, SCA(N, S, t) as an N x Smatrix where entries are from a finite set S of s symbols, such that every t-length permutation of symbols from S occurs in at least one row; the t symbols in the permutation are not required to be adjacent. 

Example 1. Consider the problem of testing four events, a, b, c, and d. There are 4! = 24 possible permutations of these four events, but we can test all 3-sequences of these events with only six tests: 

 

1

2

3

4

1

a

d

b

c

2

b

a

c

d

3

b

d

c

a

4

c

a

b

d

5

c

d

b

a

6

d

a

c

b

Example 2. Generating a 2-sequence covering array is trivial: list the events in some order for one test and in the reverse order for the second test. 
 

 

1

2

3

4

1

a

b

c

d

2

d

c

b

a

 

As shown in example 2, only two tests are needed to cover all 2-way permutations of symbols. Other values of t > 2 will require more. The example below covers all 3-way permutations for five events in eight tests. Arrays for other event set sizes can be found in the library table following. 

 

1

2

3

4

5

1

a

b

c

d

e

2

e

d

c

b

a

3

b

a

e

d

c

4

c

e

a

b

d

5

d

e

a

b

c

6

c

d

b

a

e

7

a

e

c

d

b

8

b

d

c

e

a

SEQUENCE COVERING ARRAY LIBRARY

The sequence covering arrays are provided in comma separated value form. Currently arrays are for 3-way interactions only. Longer permutations will be added in the future. For 2-way permutations, event sequences can simply be reversed, as shown in Example 2, so these arrays are not included in the library. Please note that these arrays were prepared with a quick and dirty greedy algorithm in Oct 09, and can probably be improved upon. We are working on this now. If you have an algorithm that generates smaller arrays, we would be happy to host them, citing your algorithm of course; feel free to email me at kuhn@nist.gov if interested. 
 

3-way permutations

4-way permutations

Events

Number  Tests

Test file

Number  Tests

Test file

5

8

test3_5.csv

29

test4_5.csv

6

10

test3_6.csv

38

test4_6.csv

7

12

test3_7.csv

50

test4_7.csv

8

12

test3_8.csv

56

test4_8.csv

9

14

test3_9.csv

68

test4_9.csv

10

14

test3_10.csv

72

test4_10.csv

11

14

test3_11.csv

78

test4_11.csv

12

16

test3_12.csv

86

test4_12.csv

13

16

test3_13.csv

92

test4_13.csv

14

16

test3_14.csv

100

test4_14.csv

15

18

test3_15.csv

108

test4_15.csv

16

18

test3_16.csv

112

test4_16.csv

17

20

test3_17.csv

118

test4_17.csv

18

20

test3_18.csv

122

test4_18.csv

19

22

test3_19.csv

128

test4_19.csv

20

22

test3_20.csv

134

test4_20.csv

21

22

test3_21.csv

134

test4_21.csv

22

22

test3_22.csv

140

test4_22.csv

23

24

test3_23.csv

146

test4_23.csv

24

24

test3_24.csv

146

test4_24.csv

25

24

test3_25.csv

152

test4_25.csv

26

24

test3_26.csv

158

test4_26.csv

27

26

test3_27.csv

160

test4_27.csv

28

26

test3_28.csv

162

test4_28.csv

29

26

test3_29.csv

166

test4_29.csv

30

26

test3_30.csv

166

test4_30.csv

40

32

test3_40.csv

198

test4_40.csv

50

34

test3_50.csv

214

test4_50.csv

60

38

test3_60.csv

238

test4_60.csv

70

40

test3_70.csv

 

test4_70.csv

80

42

test3_80.csv

 

test4_80.csv

90

44

test3_90.csv

 

test4_90.csv

100

44

test.3_100csv

 

test.4_100csv

 

Created May 24, 2016, Updated October 07, 2019