Combinatorial Interaction Testing for Test
Selection in Grammar-Based Testing
Elke Salecker, Sabine Glesner
Technical University of Berlin, Germany
Workshop on Combinatorial Testing (CT) 2012
Montreal, Canada
Introduction
Background
Approach
Evaluation
Motivation
Grammar-based Testing
• black-box testing approach
• test data derived from context-free grammar
à automatic generation of test data
Elke Salecker, Sabine Glesner
1
Conclusions
Introduction
Background
Approach
Evaluation
Motivation
Grammar-based Testing
• black-box testing approach
• test data derived from context-free grammar
à automatic generation of test data
Problem
• exhaustive testing of test sets infeasible
• controlled/random-based enumaration process
• rule combination coverage not in focus
Elke Salecker, Sabine Glesner
1
Conclusions
Introduction
Background
Approach
Evaluation
Motivation
Grammar-based Testing
• black-box testing approach
• test data derived from context-free grammar
à automatic generation of test data
Problem
• exhaustive testing of test sets infeasible
• controlled/random-based enumaration process
• rule combination coverage not in focus
New Approach
à test selection based on combinatorial interaction testing
à automatic generation of CIT test specification
Elke Salecker, Sabine Glesner
1
Conclusions
Introduction
Background
Approach
Evaluation
Outline
1 Introduction
2 CIT and Grammars
3 Test Set Generation
4 Evaluation
5 Conclusions
Elke Salecker, Sabine Glesner
2
Conclusions
Introduction
Background
Approach
Evaluation
Combinatorial Interaction Testing
CIT specification:
parameters, values
Elke Salecker, Sabine Glesner
P1
a1
a2
a3
P2
b1
b2
P3
c1
c2
P4
d1
d2
3
Conclusions
Introduction
Background
Approach
Evaluation
Combinatorial Interaction Testing
CIT specification:
parameters, values
test case
Elke Salecker, Sabine Glesner
P1
a1
a2
a3
P2
b1
b2
P3
c1
c2
P4
d1
d2
(a1 , b1 , c1 , d2 )
3
Conclusions
Introduction
Background
Approach
Evaluation
Combinatorial Interaction Testing
CIT specification:
parameters, values
P1
a1
a2
a3
P2
b1
b2
P3
c1
c2
P4
d1
d2
test case
(a1 , b1 , c1 , d2 )
test set
P1 × P2 × P3 × P4, 24 test cases
Elke Salecker, Sabine Glesner
3
Conclusions
Introduction
Background
Approach
Evaluation
Combinatorial Interaction Testing
CIT specification:
parameters, values
P1
a1
a2
a3
P2
b1
b2
P3
c1
c2
P4
d1
d2
test case
(a1 , b1 , c1 , d2 )
test set
P1 × P2 × P3 × P4, 24 test cases
coverage criterion
(t=2)
1 a3
2 a2
3 a1
4 a1
5 a2
6 a3
Elke Salecker, Sabine Glesner
b1
b2
b2
b1
b1
b2
c1
c2
c1
c2
c1
c2
d2
d2
d2
d1
d1
d1
3
Conclusions
Introduction
Background
Approach
Evaluation
Combinatorial Interaction Testing
CIT specification:
parameters, values
P1
a1
a2
a3
P2
b1
b2
P3
c1
c2
P4
d1
d2
test case
(a1 , b1 , c1 , d2 )
test set
P1 × P2 × P3 × P4, 24 test cases
coverage criterion
(t=2)
1 a3
2 a2
3 a1
4 a1
5 a2
6 a3
constraints
Elke Salecker, Sabine Glesner
b1
b2
b2
b1
b1
b2
c1
c2
c1
c2
c1
c2
d2
d2
d2
d1
d1
d1
¬(b1 ∧ c2 )
3
Conclusions
Introduction
Background
Approach
Evaluation
Grammars
nonterminals N = {, r, imm}
terminals
Σ = {Const, ObjAddr, Content, Plus, Assign}
Elke Salecker, Sabine Glesner
4
Conclusions
Introduction
Background
Approach
Evaluation
Conclusions
Grammars
N = {, r, imm}
Σ = {Const, ObjAddr, Content, Plus, Assign}
def:
→ Assign((ObjAddr a), r)
add:
r → Plus(r, r)
addimm:
r → Plus(r, imm)
use:
r → Content(ObjAddr a)
r2c:
r → Const c
r2i:
r → imm
i2c:
imm → Const c
start symbol nonterminals
terminals
rules
(lhs → rhs)
Elke Salecker, Sabine Glesner
4
Introduction
Background
Approach
Evaluation
Conclusions
Grammars
N = {, r, imm}
Σ = {Const, ObjAddr, Content, Plus, Assign}
def:
→ Assign((ObjAddr a), r)
add:
r → Plus(r, r)
addimm:
r → Plus(r, imm)
use:
r → Content(ObjAddr a)
r2c:
r → Const c
r2i:
r → imm
i2c:
imm → Const c
start symbol derivation
sequence of rule applications
< add, addimm, r2c >
nonterminals
terminals
rules
(lhs → rhs)
r
Elke Salecker, Sabine Glesner
4
Introduction
Background
Approach
Evaluation
Conclusions
Grammars
N = {, r, imm}
Σ = {Const, ObjAddr, Content, Plus, Assign}
def:
→ Assign((ObjAddr a), r)
add:
r → Plus(r, r)
addimm:
r → Plus(r, imm)
use:
r → Content(ObjAddr a)
r2c:
r → Const c
r2i:
r → imm
i2c:
imm → Const c
start symbol derivation
sequence of rule applications
< add, addimm, r2c >
nonterminals
terminals
rules
(lhs → rhs)
r
Plus
r
Elke Salecker, Sabine Glesner
r
4
Introduction
Background
Approach
Evaluation
Conclusions
Grammars
N = {, r, imm}
Σ = {Const, ObjAddr, Content, Plus, Assign}
def:
→ Assign((ObjAddr a), r)
add:
r → Plus(r, r)
addimm:
r → Plus(r, imm)
use:
r → Content(ObjAddr a)
r2c:
r → Const c
r2i:
r → imm
i2c:
imm → Const c
start symbol derivation
sequence of rule applications
< add, addimm, r2c >
nonterminals
terminals
rules
(lhs → rhs)
r
Plus
r
Plus
r
r
Elke Salecker, Sabine Glesner
r
Plus
imm
4
Introduction
Background
Approach
Evaluation
Conclusions
Grammars
N = {, r, imm}
Σ = {Const, ObjAddr, Content, Plus, Assign}
def:
→ Assign((ObjAddr a), r)
add:
r → Plus(r, r)
addimm:
r → Plus(r, imm)
use:
r → Content(ObjAddr a)
r2c:
r → Const c
r2i:
r → imm
i2c:
imm → Const c
start symbol derivation
sequence of rule applications
< add, addimm, r2c >
nonterminals
terminals
rules
(lhs → rhs)
r
Plus
r
Plus
r
Elke Salecker, Sabine Glesner
r
Plus
r
Plus
imm
r
Plus
Const 2
4
imm
Introduction
Background
Approach
Evaluation
Outline
1 Introduction
2 CIT and Grammars
3 Test Set Generation
4 Evaluation
5 Conclusions
Elke Salecker, Sabine Glesner
5
Conclusions
Introduction
Background
Approach
Evaluation
Symmetry in Derivations
r2c
i2c
add
addimm
r → Const c
imm → Const c
r → Plus(r, r)
r → Plus(r, imm)
derivation:
add ⇒ addimm ⇒ r2c ⇒ i2c ⇒ r2c
Plus
Plus
Const 2
Const 4
Const 2
Elke Salecker, Sabine Glesner
6
Conclusions
Introduction
Background
Approach
Evaluation
Conclusions
Symmetry in Derivations
r2c
i2c
add
addimm
r → Const c
imm → Const c
r → Plus(r, r)
r → Plus(r, imm)
derivation:
add ⇒ addimm ⇒ r2c ⇒ i2c ⇒ r2c
Plus
Plus
Const 2
Const 4
Const 2
Elke Salecker, Sabine Glesner
derivation:
add ⇒ r2c ⇒ addimm ⇒ r2c ⇒ i2c
Plus
Const 4
Plus
Const 2
6
Const 2
Introduction
Background
Approach
Evaluation
Principle of Specification Generation
1
2
3
...
6
7
...
30
1
def
def
def
Derivations with
2
3
add add
add use
add r2c
Fixed Length
4
5
6
r2c r2c r2c
add r2c r2c
add r2c r2c
def
def
add
add
addimm
addimm
r2c
use
i2c
i2c
use
use
def
add
use
add
use
use
Elke Salecker, Sabine Glesner
7
Conclusions
Introduction
Background
Approach
Evaluation
Principle of Specification Generation
1
2
3
...
6
7
...
30
1
def
def
def
def
def
Derivations with
2
3
add add
add use
add r2c
add
add
addimm
addimm
Fixed Length
4
5
6
r2c r2c r2c
add r2c r2c
add r2c r2c
r2c
use
i2c
i2c
use
use
def add use
add use use
P1 P2 P3
P4 P5 P6
derivation length = number of parameters
value of parameter i = rule can be applied in step i
constraints for invalid combinations
Elke Salecker, Sabine Glesner
7
Conclusions
Introduction
Background
Approach
Evaluation
CIT Specification Generation
1
Generate compact representation of derivations
2
Calculate value sets
3
Calculate constraints
Elke Salecker, Sabine Glesner
8
Conclusions
Introduction
Background
Approach
Evaluation
Conclusions
Generate Compact Representation of Derivations
Recursive Construction:
Base Case
derivation length = 1
store for terminal rules
lhs nonterminal, rule identifier
Recursion
derivation length > 1
Elke Salecker, Sabine Glesner
9
Introduction
Background
Approach
Evaluation
Conclusions
Generate Compact Representation of Derivations
Recursive Construction:
Base Case
derivation length = 1
store for terminal rules
lhs nonterminal, rule identifier
Recursion
derivation length > 1
check remaining rules
split overall length for number of nonterminals in rule
find smaller derivations
store lhs nonterminal, rule identifier, extended pattern
Elke Salecker, Sabine Glesner
9
Introduction
Background
Approach
Evaluation
Conclusions
Generate Compact Representation of Derivations
def:
→Assign((ObjAddr a),r)
add:
r → Plus(r, r)
addimm:
r → Plus(r, imm)
use:
r → Content(ObjAddr a)
r2c:
r → Const c
r2i:
r → imm
i2c:
imm → Const c
Elke Salecker, Sabine Glesner
L NT
1 r
Rule
use
r2c
imm i2c
RHS Pattern
∅
∅
∅
10
Introduction
Background
Approach
Evaluation
Conclusions
Generate Compact Representation of Derivations
def:
→Assign((ObjAddr a),r)
add:
r → Plus(r, r)
addimm:
r → Plus(r, imm)
use:
r → Content(ObjAddr a)
r2c:
r → Const c
r2i:
r → imm
i2c:
imm → Const c
Elke Salecker, Sabine Glesner
L NT
1 r
Rule
use
r2c
imm i2c
2 r
r2i
def
3 r
addimm
add
def
RHS Pattern
∅
∅
∅
< (1, imm) >
< (1, reg) >
< (1, reg), (1, imm) >
< (1, r), (1, r) >
< (2,r) >
10
Introduction
Background
Approach
Evaluation
Conclusions
Generate Compact Representation of Derivations
def:
→Assign((ObjAddr a),r)
add:
r → Plus(r, r)
addimm:
r → Plus(r, imm)
use:
r → Content(ObjAddr a)
r2c:
r → Const c
r2i:
r → imm
i2c:
imm → Const c
Elke Salecker, Sabine Glesner
L NT
1 r
Rule
use
r2c
imm i2c
2 r
r2i
def
3 r
addimm
add
def
4
add
RHS Pattern
∅
∅
∅
< (1, imm) >
< (1, reg) >
< (1, reg), (1, imm) >
< (1, r), (1, r) >
< (2,r) >
< (1, r), (2, r) >
< (2, r), (1, r) >
10
Introduction
Background
Approach
Evaluation
Generate Value Sets
Recursive Construction:
Base Case
derivation length = 1
collect rules for length 1
Recursion
derivation length > 1
iterate over rules with considered nonterminal
extend parameter with rules
for each rule iterate over alternatives
descend for each nonterminal
Elke Salecker, Sabine Glesner
11
Conclusions
Introduction
Background
Approach
Evaluation
Conclusions
Generate Compact Representation of Derivations
L NT Rule
1 r
use
r2c
imm i2c
2 r
r2i
def
3 r
addimm
add
def
4 r
addimm
add
def
RHS Pattern
∅
∅
∅
< (1, imm) >
< (1, r) >
< (1, r), (1, imm) >
< (1, r), (1, r) >
< (2,reg) >
< (2, r), (1, imm) >
< (1, r), (2, r) >
< (2, r), (1, r) >
< (3,r) >
Elke Salecker, Sabine Glesner
P1
P2
P3
P4
12
Introduction
Background
Approach
Evaluation
Conclusions
Generate Compact Representation of Derivations
L NT Rule
1 r
use
r2c
imm i2c
2 r
r2i
def
3 r
addimm
add
def
4 r
addimm
add
def
RHS Pattern
∅
∅
∅
< (1, imm) >
< (1, r) >
< (1, r), (1, imm) >
< (1, r), (1, r) >
< (2,reg) >
< (2, r), (1, imm) >
< (1, r), (2, r) >
< (2, r), (1, r) >
< (3,r) >
Elke Salecker, Sabine Glesner
P1
P2
P3
P4
def
12
Introduction
Background
Approach
Evaluation
Conclusions
Generate Compact Representation of Derivations
L NT Rule
1 r
use
r2c
imm i2c
2 r
r2i
def
3 r
addimm
add
def
4 r
addimm
add
def
RHS Pattern
∅
∅
∅
< (1, imm) >
< (1, r) >
< (1, r), (1, imm) >
< (1, r), (1, r) >
< (2,reg) >
< (2, r), (1, imm) >
< (1, r), (2, r) >
< (2, r), (1, r) >
< (3,r) >
Elke Salecker, Sabine Glesner
P1
P2
P3
P4
def
addimm
12
Introduction
Background
Approach
Evaluation
Conclusions
Generate Compact Representation of Derivations
L NT Rule
1 r
use
r2c
imm i2c
2 r
r2i
def
3 r
addimm
add
def
4 r
addimm
add
def
RHS Pattern
∅
∅
∅
< (1, imm) >
< (1, r) >
< (1, r), (1, imm) >
< (1, r), (1, r) >
< (2,reg) >
< (2, r), (1, imm) >
< (1, r), (2, r) >
< (2, r), (1, r) >
< (3,r) >
Elke Salecker, Sabine Glesner
P1
P2
P3
P4
def
add
use, r2c
12
Introduction
Background
Approach
Evaluation
Conclusions
Generate Compact Representation of Derivations
L NT Rule
1 r
use
r2c
imm i2c
2 r
r2i
def
3 r
addimm
add
def
4 r
addimm
add
def
RHS Pattern
∅
∅
∅
< (1, imm) >
< (1, r) >
< (1, r), (1, imm) >
< (1, r), (1, r) >
< (2,reg) >
< (2, r), (1, imm) >
< (1, r), (2, r) >
< (2, r), (1, r) >
< (3,r) >
Elke Salecker, Sabine Glesner
P1
P2
P3
P4
def
addimm
use, r2c
i2c
12
Introduction
Background
Approach
Evaluation
Generate Constraints
Recursive Construction:
Base Case
derivation length = 1
disjunction of all rules for length 1
Recursion
derivation length > 1
iterate over rules with considered nonterminal
construct disjunction
for each rule iterate over alternatives
construct disjunction
for each alternative
construct conjunction
Elke Salecker, Sabine Glesner
13
Conclusions
Introduction
Background
Approach
Evaluation
Conclusions
Generate Compact Representation of Derivations
L NT Rule
1 r
use
r2c
imm i2c
2 r
r2i
def
3 r
addimm
add
def
4 r
addimm
add
def
RHS Pattern
∅
∅
∅
< (1, imm) >
< (1, r) >
< (1, r), (1, imm) >
< (1, r), (1, r) >
< (2,reg) >
< (2, r), (1, imm) >
< (1, r), (2, r) >
< (2, r), (1, r) >
< (3,r) >
Elke Salecker, Sabine Glesner
14
Introduction
Background
Approach
Evaluation
Conclusions
Generate Compact Representation of Derivations
L NT Rule
1 r
use
r2c
imm i2c
2 r
r2i
def
3 r
addimm
add
def
4 r
addimm
add
def
RHS Pattern
∅
∅
∅
< (1, imm) >
< (1, r) >
< (1, r), (1, imm) >
< (1, r), (1, r) >
< (2,reg) >
< (2, r), (1, imm) >
< (1, r), (2, r) >
< (2, r), (1, r) >
< (3,r) >
Elke Salecker, Sabine Glesner
def −→ f
14
Introduction
Background
Approach
Evaluation
Conclusions
Generate Compact Representation of Derivations
L NT Rule
1 r
use
r2c
imm i2c
2 r
r2i
def
3 r
addimm
add
def
4 r
addimm
add
def
RHS Pattern
∅
∅
∅
< (1, imm) >
< (1, r) >
< (1, r), (1, imm) >
< (1, r), (1, r) >
< (2,reg) >
< (2, r), (1, imm) >
< (1, r), (2, r) >
< (2, r), (1, r) >
< (3,r) >
Elke Salecker, Sabine Glesner
def −→
(addimm ∧ f )
14
Introduction
Background
Approach
Evaluation
Conclusions
Generate Compact Representation of Derivations
L NT Rule
1 r
use
r2c
imm i2c
2 r
r2i
def
3 r
addimm
add
def
4 r
addimm
add
def
RHS Pattern
∅
∅
∅
< (1, imm) >
< (1, r) >
< (1, r), (1, imm) >
< (1, r), (1, r) >
< (2,reg) >
< (2, r), (1, imm) >
< (1, r), (2, r) >
< (2, r), (1, r) >
< (3,r) >
Elke Salecker, Sabine Glesner
def −→
(addimm ∧
((use ∨ r2c) ∧ f))
14
Introduction
Background
Approach
Evaluation
Conclusions
Generate Compact Representation of Derivations
L NT Rule
1 r
use
r2c
imm i2c
2 r
r2i
def
3 r
addimm
add
def
4 r
addimm
add
def
RHS Pattern
∅
∅
∅
< (1, imm) >
< (1, r) >
< (1, r), (1, imm) >
< (1, r), (1, r) >
< (2,reg) >
< (2, r), (1, imm) >
< (1, r), (2, r) >
< (2, r), (1, r) >
< (3,r) >
Elke Salecker, Sabine Glesner
def −→
(addimm ∧
((use ∨ r2c) ∧ i2c))
14
Introduction
Background
Approach
Evaluation
Outline
1 Introduction
2 CIT and Grammars
3 Test Set Generation
4 Evaluation
5 Conclusions
Elke Salecker, Sabine Glesner
15
Conclusions
Introduction
Background
Approach
Evaluation
Conclusions
Size of Parameters
G1
G2
P1
P2
P3
P4
P5
Spec3
5
17
9
Spec4
10
38
26
13
Spec5
10
43
38
26
13
Spec6
12
55
47
38
26
Spec3
5
21
13
Spec4
10
44
30
20
Spec5
10
53
47
32
20
Spec6
12
88
67
54
32
P6
13
G1
86
12
G2
110
12
rules
initial rules
rules
initial rules
20
à generation within seconds
Elke Salecker, Sabine Glesner
16
Introduction
Background
Approach
Evaluation
Size of Test Sets
L
6
8
10
Spec
Derivations
TCases(ACTS)
Spec
Derivations
TCases(ACTS)
Spec
Derivations
TCases(ACTS)
Elke Salecker, Sabine Glesner
G1
5 (1)
1 23 42
64
16
1 23 44
640
22
3 6
12 4
7168
32
G2
6 (2)
24 42
128
25
24 44
1280
32
4 6
2 4
14336
38
G3
6 (1)
1 22 3 5 2
144
13
1 22 3 5 4
2160
17
2
1 2 3 56
36288
24
G4
7 (2)
23 3 5 2
288
22
23 3 5 4
4320
28
23 3 5 6
30
17
Conclusions
Introduction
Background
Approach
Evaluation
Size of Test Sets
L
6
8
10
Spec
Derivations
TCases(ACTS)
Spec
Derivations
TCases(ACTS)
Spec
Derivations
TCases(ACTS)
G1
5 (1)
1 23 42
64
16
1 23 44
640
22
3 6
12 4
7168
32
G2
6 (2)
24 42
128
25
24 44
1280
32
4 6
2 4
14336
38
G3
6 (1)
1 22 3 5 2
144
13
1 22 3 5 4
2160
17
2
1 2 3 56
36288
24
G4
7 (2)
23 3 5 2
288
22
23 3 5 4
4320
28
23 3 5 6
30
• significant reduction
• generation failed for case study grammars
Elke Salecker, Sabine Glesner
17
Conclusions
Introduction
Background
Approach
Evaluation
Conclusion and Future Work
Conclusion
• new approach for grammar-based testing
• criterion guarantees t-wise rule coverage
• test selection based on combinatorial interaction testing
• CIT specification automatically generated
• very encouraging results regarding test set size
Elke Salecker, Sabine Glesner
18
Conclusions
Introduction
Background
Approach
Evaluation
Conclusion and Future Work
Conclusion
• new approach for grammar-based testing
• criterion guarantees t-wise rule coverage
• test selection based on combinatorial interaction testing
• CIT specification automatically generated
• very encouraging results regarding test set size
Future Work
• enhancement of constraint generation
• combination with alternative approach for grammar-based
testing
• comprehensive case study for compiler back ends
Elke Salecker, Sabine Glesner
18
Conclusions