Graph Coverage in Software Testing

1. 1 Graph Coverage (2) Graph Coverage (2)

2. Reading Assignment Reading Assignment P. Ammann and J. Offutt Introduction to Software Testing Section 2.2 2

3. 3 Outline Outline Testing and Covering Graphs Node and Edge Coverage Covering Multiple Edges Simple Paths and Prime Paths

4. 4 Testing and Covering Graphs Testing and Covering Graphs We use graphs in testing as follows : Developing a model of the software as a graph Requiring tests to visit or tour specific sets of nodes, edges or subpaths Coverage : Given a set TR of test requirements for a criterion C, a set of tests T satisfies C on a graph if and only if for every test requirement in TR, there is a test path in path(T) that meets the test requirement tr Structural Coverage Criteria : Defined on a graph just in terms of nodes and edges Data Flow Coverage Criteria : Requires a graph to be annotated with references to variables

5. 5 Node Coverage Node Coverage Formal Definition: For each node n reach G (N 0 ), TR contains the predicate visit n. Standard Definition: Test set T satisfies node coverage on graph G if and only if for every syntactically reachable node n in N, there is some path p in path(T) such that p visits n. Simple Definition: TR contains each reachable node in G.

6. 6 Edge Coverage Edge Coverage Simple Definition: TR contains each reachable path of length up to 1, inclusive, in G. The length up to 1 allows for graphs with one node and no edges Edge coverage is slightly stronger than node coverage Which graphs have different Node Coverage and Edge Coverage criteria?

7. 7 Covering Multiple Edges Covering Multiple Edges Edge-pair coverage requires pairs of edges , or subpaths of length 2 TR contains each reachable path of length up to 2, inclusive, in G. The length up to 2 is used to include graphs that have less than 2 edges The logical extension is to require. Complete Path Coverage (CPC) : TR contains all paths in G. Impossible if the graph has a loop. Specified Path Coverage (SPC) : TR contains a set S of test paths, where S is supplied as a parameter.

8. 8 Structural Coverage Example Structural Coverage Example Node Coverage TR = { 0, 1, 2, 3, 4, 5, 6 } Test Paths: [ 0, 1, 2, 3, 6 ] [ 0, 1, 2, 4, 5, 4, 6 ] 6 0 2 1 3 4 Edge Coverage TR = { (0,1), (0,2), (1,2), (2,3), (2,4), (3,6), (4,5), (4,6), (5,4) } Test Paths: [ 0, 1, 2, 3, 6 ] [ 0, 2, 4, 5, 4, 6 ] Edge-Pair Coverage TR = { [0,1,2], [0,2,3], [0,2,4], [1,2,3], [1,2,4], [2,3,6], [2,4,5], [2,4,6], [4,5,4], [5,4,5], [5,4,6] } Test Paths: [ 0, 1, 2, 3, 6 ] [ 0, 1, 2, 4, 6 ] [ 0, 2, 3, 6 ] [ 0, 2, 4, 5, 4, 5, 4, 6 ] Complete Path Coverage Test Paths: [ 0, 1, 2, 3, 6 ] [ 0, 1, 2, 4, 6 ] [ 0, 1, 2, 4, 5, 4, 6 ] [ 0, 1, 2, 4, 5, 4, 5, 4, 6 ] [ 0, 1, 2, 4, 5, 4, 5, 4, 5, 4, 6 ] 5

9. 9 Loops in Graphs Loops in Graphs If a graph contains a loop, it has an infinite number of paths Thus, CPC is not feasible SPC is not satisfactory because the results are subjective and vary with the tester

10. 10 Simple Paths and Prime Paths Simple Paths and Prime Paths Simple Path : A path from node n i to n j is simple if no node appears more than once, except possibly the first and last nodes are the same No internal loops Includes all other subpaths A loop is a simple path

11. 11 Simple Paths and Prime Paths Simple Paths and Prime Paths Prime Path : A simple path that does not appear as a proper subpath of any other simple path Simple Paths : [ 0, 1, 3, 0 ], [ 0, 2, 3, 0], [ 1, 3, 0, 1 ], [ 2, 3, 0, 2 ], [ 3, 0, 1, 3 ], [ 3, 0, 2, 3 ], [ 1, 3, 0, 2 ], [ 2, 3, 0, 1 ], [ 0, 1, 3 ], [ 0, 2, 3 ], [ 1, 3, 0 ], [ 2, 3, 0 ], [ 3, 0, 1 ], [3, 0, 2 ], [ 0, 1], [ 0, 2 ], [ 1, 3 ], [ 2, 3 ], [ 3, 0 ], [0], [1], [2], [3] Prime Paths : [ 0, 1, 3, 0 ], [ 0, 2, 3, 0], [ 1, 3, 0, 1 ], [ 2, 3, 0, 2 ], [ 3, 0, 1, 3 ], [ 3, 0, 2, 3 ], [ 1, 3, 0, 2 ], [ 2, 3, 0, 1 ] 1 2 0 3

12. 12 Prime Path Coverage Prime Path Coverage A simple, elegant and finite criterion that requires loops to be executed as well as skipped Prime Path Coverage (PPC) : TR contains each prime path in G. Will tour all paths of length 0, 1, That is, it subsumes node, edge, and edge-pair coverage

13. 13 Round Trips Round Trips Round-Trip Path : A prime path that starts and ends at the same node Simple Round Trip Coverage (SRTC) : TR contains at least one round-trip path for each reachable node in G that begins and ends a round- trip path. Complete Round Trip Coverage (CRTC) : TR contains all round-trip paths for each reachable node in G. These criteria omit nodes and edges that are not in round trips That is, they do not subsume edge-pair, edge, or node coverage

14. 14 Simple & Prime Path Example Simple & Prime Path Example 5 0 2 1 3 4 6 Len 0 [0] [1] [2] [3] [4] [5] [6] ! ! means path terminates Len 1 [0, 1] [0, 2] [1, 2] [2, 3] [2, 4] [3, 6] ! [4, 6] ! [4, 5] [5, 4] Len 2 [0, 1, 2] [0, 2, 3] [0, 2, 4] [1, 2, 3] [1, 2, 4] [2, 3, 6] ! [2, 4, 6] ! [2, 4, 5] ! [4, 5, 4] * [5, 4, 6] ! [5, 4, 5] * * means path cycles Len 3 [0, 1, 2, 3] [0, 1, 2, 4] [0, 2, 3, 6] ! [0, 2, 4, 6] ! [0, 2, 4, 5] ! [1, 2, 3, 6] ! [1, 2, 4, 5] ! [1, 2, 4, 6] ! Len 4 [0, 1, 2, 3, 6] ! [0, 1, 2, 4, 6] ! [0, 1, 2, 4, 5] ! Prime Paths Simple paths

15. 15 Key Points Key Points Graphs are used in Testing Developing a model of the software as a graph Requiring test cases to visit or tour specific sets of nodes, edges or sub-paths. Test criteria are rules that define test criteria. Node and Edge Coverage Simple and prime paths