New version page

# UT Arlington CSE 4321 - Graph-Based Testing

Pages: 27
Documents in this Course

48 pages

21 pages

18 pages

50 pages

55 pages

23 pages

5 pages

6 pages

38 pages

30 pages

28 pages

32 pages

Unformatted text preview:

9/12/11 1 Software Testing and Maintenance 1 Graph-Based Testing  Introduction  Basic Concepts  Control Flow Testing  Data Flow Testing  Summary Software Testing and Maintenance 2 Motivation  Graph-based testing first builds a graph model for the program under test, and then tries to cover certain elements in the graph model.  Graph is one of the most widely used structures for abstraction.  Transportation network, social network, molecular structure, geographic modeling, etc.  Graph is a well-defined, well-studied structure  Many algorithms have been reported that allow for easy manipulation of graphs.9/12/11 2 Software Testing and Maintenance 3 Major Steps  Step 1: Build a graph model  What information to be captured, and how to represent those information?  Step 2: Identify test requirements  A test requirement is a structural entity in the graph model that must be covered during testing  Step 3: Select test paths to cover those requirements  Step 4: Derive test data so that those test paths can be executed Software Testing and Maintenance 4 Graph Models  Control flow graph: Captures information about how the control is transferred in a program.  Data flow graph: Augments a CFG with data flow information  Dependency graph: Captures the data/control dependencies among program statements  Cause-effect graph: Modeling relationships among program input conditions, known as causes, and output conditions, known as effects9/12/11 3 Software Testing and Maintenance 5 Graph-Based Testing  Introduction  Basic Concepts  Control Flow Testing  Data Flow Testing  Summary Software Testing and Maintenance 6 Graph  A graph consists of a set of nodes and edges that connect pairs of nodes.  Formally, a graph G = <N, N0, Nf, E):  N: a set of nodes  N0 ⊆ N: a set of initial nodes  Nf ⊆ N: a set of final nodes  E ⊆ N × N: a set of edges  In our context, N, N0, and Nf contain at least one node.9/12/11 4 Software Testing and Maintenance 7 Example n0 n1 n2 n3 n3 n4 n7 n0 n1 n2 n5 n6 n8 n9 N = {n0, n1, n2, n3} N0 = {n0} Nf = {n3} E = {(n0, n1), (n0, n2), (n1, n3), (n2, n3)} N = {n0, n1, n2, n3 , n4, n5, n6 , n7, n8, n9} N0 = {n0 , n1, n2} Nf = {n7, n8, n9} E = {(n0, n3), (n0, n4), (n1, n4), (n1, n5), …} Software Testing and Maintenance 8 Path, Subpath, Test Path  A path is a sequence [n1, n2, …, nM] of nodes, where each pair of adjacent nodes (ni, ni+1) is an edge.  The length of a path refers to the number of edges in the path  A subpath of a path p is a subsequence of p, possibly p itself.  A test path is a path, possibly of length zero, that starts at an initial node, and ends at a final node  Represents a path that is executed during a test run9/12/11 5 Software Testing and Maintenance 9 Reachability  A node n is syntactically reachable from node n’ if there exists a path from n’ to n.  A node n is semantically reachable from node n’ if it is possible to execute a path from n’ to n with some input.  reach(n): the set of nodes and edges that can be syntactically reached from node n. Software Testing and Maintenance 10 Example n3 n4 n7 n0 n1 n2 n5 n6 n8 n9 p1 = [n0, n3, n7] p2 = [n1, n4, n8, n5, n1] p3 = [n4, n8, n5] reach(n0) = ? reach(n5) = ?9/12/11 6 Software Testing and Maintenance 11 SESE Graph n0 n1 n2 n3 n4 n5 n6 Software Testing and Maintenance 12 Visit & Tour  A test path p is said to visit a node n (or an edge e) if node n (or edge e) is in path p.  A test path p is said to tour a path q if q is a subpath of p.9/12/11 7 Software Testing and Maintenance 13 Test Case vs Test Path n0 n1 n2 n3 a < b a > b a = b t1: (a = 0, b = 1) => p1 = [n0, n1, n3, n2] t2: (a = 1, b = 1) => p2 = [n0, n3, n2] t3: (a = 2, b = 1) => p3 = [n0, n2] Software Testing and Maintenance 14 Graph-Based Testing  Introduction  Basic Concepts  Control Flow Testing  Data Flow Testing  Summary9/12/11 8 Software Testing and Maintenance 15 Basic Block  A basic block, or simply a block, is a sequence of consecutive statements with a single entry and a single exit point.  Control always enters a basic block at its entry point, and exits from its exit point.  No entry, halt, or exit inside a basic block  If a basic block contains a single statement, then the entry and exit points coincide. Software Testing and Maintenance 16 Example 1. begin 2. int x, y, power; 3. float z; 4. input (x, y); 5. if (y < 0) 6. power = -y; 7. else 8. power = y; 9. z = 1; 10. while (power != 0) { 11. z = z * x; 12. power = power – 1; 13. } 14. if (y < 0) 15. z = 1/z; 16. output (z); 17. end; Block Lines Entry Exit 1 2, 3, 4, 5 2 5 2 6 6 6 3 8 8 8 4 9 9 9 5 10 10 10 6 11, 12 11 12 7 14 14 14 8 15 15 15 9 16 16 169/12/11 9 Software Testing and Maintenance 17 Function Calls  Should a function call be treated like a regular statement or as a separate block of its own? Software Testing and Maintenance 18 Control Flow Graph  A control flow graph is a graph with two distinguished nodes, start and end.  Node start has no incoming edges, and node end has no outgoing edges.  Every node can be reached from start, and can reach end.  In a CFG, a node is typically a basic block, and an edge indicates the flow of control from one block to another.9/12/11 10 Software Testing and Maintenance 19 Example start end 1 2 3 4 5 6 7 8 9 false false true true true false Software Testing and Maintenance 20 Node Coverage  A 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.  path(T): the set of paths that are exercised by the execution of T  In other words, the set TR of test requirements for Node Coverage contains each reachable node in G.9/12/11 11 Software Testing and Maintenance 21 Edge Coverage  The TR for Edge Coverage contains each reachable path of length up to 1, inclusive, in a graph G.  Note that Edge Coverage subsumes Node Coverage. Software Testing and Maintenance 22 Node …

View Full Document