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 |
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 |
|
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 |
|
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 |
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 |
29 |
||
6 |
10 |
38 |
||
7 |
12 |
50 |
||
8 |
12 |
56 |
||
9 |
14 |
68 |
||
10 |
14 |
72 |
||
11 |
14 |
78 |
||
12 |
16 |
86 |
||
13 |
16 |
92 |
||
14 |
16 |
100 |
||
15 |
18 |
108 |
||
16 |
18 |
112 |
||
17 |
20 |
118 |
||
18 |
20 |
122 |
||
19 |
22 |
128 |
||
20 |
22 |
134 |
||
21 |
22 |
134 |
||
22 |
22 |
140 |
||
23 |
24 |
146 |
||
24 |
24 |
146 |
||
25 |
24 |
152 |
||
26 |
24 |
158 |
||
27 |
26 |
160 |
||
28 |
26 |
162 |
||
29 |
26 |
166 |
||
30 |
26 |
166 |
||
40 |
32 |
198 |
||
50 |
34 |
214 |
||
60 |
38 |
238 |
||
70 |
40 |
test4_70.csv |
||
80 |
42 |
test4_80.csv |
||
90 |
44 |
test4_90.csv |
||
100 |
44 |
test.4_100csv |
Security and Privacy: assurance, modeling, testing & validation
Technologies: software & firmware