Unit Testing

Motivation

Flowgraphs and Path Testing

• Mainly target at structural faults in our fault model. • Path testing is basis from which more sophisticated methods are “grown” • Path testing is traditional for unit testing

Ye Wu http://www.ise.gmu.edu/~wuye

9/19/2001

© Ye Wu

1

9/19/2001

© Ye Wu

2

Path testing terminologies

Path testing terminologies

• Control Flow Graph (CFG) A graphical representation of a program’s control structure. • Basic block (process block) – Maximal sequence of statements such that if one statement is executed, all statements in the basic block are reached.

• Nodes – represent Basic Blocks (Begin node, end node) • Arcs – represent control moving from one node to another node • Decision – branch, node with 2 or more outgoing arcs • Junction – Node with 2 ore more incoming edges

– No branch – Single entry, single exit 9/19/2001

© Ye Wu

3

9/19/2001

© Ye Wu

4

How to Derive CFG – if

System.out.print("Please input an integer:"); InputStreamReader isr = new InputStreamReader (System.in); BufferedReader br = new BufferedReader (isr); t = Integer.parseInt(br.readLine()); flag = false; if (t > 0) { for( i = 2; i <= ( int)Math.sqrt((double)t); i++) { if ( t % i == 0) { System.out. println("It's COMPOSITE number!"); flag = true; break; } } if (!flag) System.out.println("It's PRIME number"); } else System.out.println("Please input a positive NUM!"); 9/19/2001

© Ye Wu

S1

S1 if (e) S2 endif S3

if

e S2

-e S3

5

9/19/2001

© Ye Wu

6

1

How to Derive CFG – if-else

How to Derive CFG – while

S1

S1 If (e) S2 Else S3 endif S4

S1

if-else

e

S3

S2

9/19/2001

S1 while (e) S2 end while S3

-e

while

e

-e

S2

S4

S3

© Ye Wu

7

How to Derive CFG – for

9/19/2001

© Ye Wu

8

How to Derive CFG – repeat

S1

S1 for i = A to B do S2 end for S3

S1

for

S1 repeat S2 until (e) S3

i≤B

S2 i>B i= i+1

S2

repeat

e S3

S3 9/19/2001

© Ye Wu

9

How to Derive CFG – case S1 switch (X) case A: S2 case B: S3 otherwise S4 end case S5 9/19/2001

9/19/2001

© Ye Wu

case A

B

S3

switch (X) case A: S2 case B: S3 otherwise S4 end case S5

-A case B

S2

-B S4

S1 switch ___ A

S2

B

S3

A|B|…

S4

S5

S5 © Ye Wu

10

How to Derive CFG – case

S1

A

-e

11

9/19/2001

© Ye Wu

12

2

System.out.print("Please input an integer:"); InputStreamReader isr = new InputStreamReader (System.in); S1 BufferedReader br = new BufferedReader (isr); t = Integer.parseInt(br.readLine()); flag = false; if (t > 0) { for( i = 2; i <= ( int)Math.sqrt((double)t); i++) { if ( t % i == 0) { System.out. println("It's COMPOSITE number!"); S2 flag = true; break; } S3 S4 } if (!flag) System.out.println("It's PRIME number"); } else System.out.println("Please input a positive NUM!"); 9/19/2001

S1; if (t > 0) { for( i = 2; p; i++) { if ( t % i == 0) S2 } if (!flag) S3 else S4

© Ye Wu

13

S1

t>0 Sb p

t >=0 !p

!flag

flag S3

t >=0

Sa

S4 Send

© Ye Wu

if (!flag) S3 else S4

S4

if-else

t>0

9/19/2001

i++; if

S1

S1; if (t > 0) { for( i = 2; p; i++) { if ( t % i == 0) S2 } if (!flag) S3 else S4

S1; if (t > 0) { for( i = 2; p; i++) { if ( t % i == 0) S2 }

for

Sb

Sa

14

p

for

t >=0

if S2

X

!p

i++; !flag

if flag

S3

Send 9/19/2001

© Ye Wu

S1

t>0

S4

Send 15

9/19/2001

Basic Path Coverage Techniques (1)

© Ye Wu

16

Example if ( a > 0 && b > 0 && c < 0) { … }

• Statement Coverage – Every statement in the program must be tested – Each node in CFG has to be covered

condition

a > 0 && b > 0 && c < 0

• Branch Coverage – Each branch must be taken at least once – Each edge in CFG must be covered

9/19/2001

© Ye Wu

decision

17

9/19/2001

© Ye Wu

18

3

Example

Basic Path Coverage Techniques (2) • Conditional coverage – Every condition in every decision has evaluated to both True and False for at least once

• Multiple condition/Decision coverage(MC/DC) – Every decision and every condition within the decision have taken every outcome at least once

9/19/2001

© Ye Wu

19

Test case 1: Test case 2: Test case 3: Test case 4: Test case 5: Test case 6: Test case 7: Test case 8:

9/19/2001

© Ye Wu

c= 1 c = -1 c= 1 c = -1 c= 1 c = -1 c= 1 c = -1

BC

CC

MC/DC

20

Terminologies • Path Segment (subpath ) – A sequence of arcs through the CFG, not necessarily complete. • Complete path(Path) – A subpath starts from the begin node and stop at the end node. • Length of a subpath – Number of arcs in a subpath. • Loop – Subpath that begins and ends at the same node.

– 2n – Infeasible combinations

9/19/2001

b=1 b=1 b =-1 b =-1 b=1 b=1 b =-1 b =-1

© Ye Wu

Basic Path Coverage Techniques (3) • Multiple condition coverage All true-false combinations of conditions for a decision need to be test at least once

a=1 a=1 a=1 a=1 a =-1 a =-1 a =-1 a =-1

21

9/19/2001

© Ye Wu

22

Basic Path Coverage Techniques (4)

Relationships Among Coverage Criteria

• Path coverage

• Subsumes

– Every complete path is executed for at least once

A testing criteria C1 subsumes C2 is for any test set T that satisfies C1, T also satisfies C2.

• Simple path coverage – Every simple path (no repeat occurrence of edges) is executed for at least once

MC

Path

MC/DC

• Elementary path coverage – Every elementary path (no repeat occurrence of nodes) is executed for at least once

CC

SPath

EPath

BC SC

9/19/2001

© Ye Wu

23

9/19/2001

© Ye Wu

24

4

Special Considerations

Effectiveness of Path Testing

• Handling loops in path testing

• Can caught about 60% bugs in unit testing

– Run the loop 0, 1, N times, N is the maximum – Run the loop, 0, 1, N, a, N-1

• Path testing can not reveal wrong or missing functions • Path testing may not catch interface errors • Path testing can not catch data flow errors • Path testing can not catch specification errors • Validate path coverage is difficult

• Boundary Testing

9/19/2001

© Ye Wu

25

9/19/2001

Test Case Generation

© Ye Wu

26

Path Sensitizing

• Path selection – – – – – –

Simple path vs. complicate path Incremental vs. big -bang Non functional meaning path Loops Multi-entry and multi-exit program Uncoverable code

9/19/2001

© Ye Wu

Finding a set of input values that will cause a component to follow a selected path.

27

9/19/2001

Predicate Expression

© Ye Wu

28

Predicate Expression

• Predicate interpretation The act of symbolic substitution of operations along the path In order to express the predicate solely in terms of the input v ector. input x1 ,x2 ; if (x1 + x2 > 0) { …… } x1 and x 2 are solely depends on inputs.

input x1 ,x2 ; y = x2 + 7; if (x1 + y > 0) { …… } (x1 + y > 0) ⇔ (x1 + x 2 + 7 > 0)

input x1 ,x2 ; if (x1 > 0) { y = x2 + 7; } else { y = x1 + 5; } if (y > 0){ … …} (y > 0) ⇔ ((x 1 > 0)&&(x2 +7>0))|| _____

• A predicate is said to be process dependent– if a predicate whose truth value can change as a result of the processing. • A pair of predicates whose outcomes depend on one or more variables are said to be correlated predicates.

(x1 > 0)&&(x1+5>0))

Path predicate are the specific form of the predicates of the decisions Along the selected path after interpretation. 9/19/2001

© Ye Wu

29

9/19/2001

© Ye Wu

30

5

Predicate Expression

Path Instrumentation

• Path Predicate expression – the set of path predicates associated with a path

Instrument – to modify a program so that it measures coverage while executing.

– Independent, uncorrelated predicates – Independent, correlated predicates – Dependent predicates

9/19/2001

© Ye Wu

• Link Markers • Link Counters • Other instrumentation approaches 31

9/19/2001

© Ye Wu

32

6