Today’s AgendaQuick ReviewGraph-Based TestingMotivationMajor StepsGraph ModelsSlide 7GraphExamplePath, Subpath, Test PathReachabilitySlide 12SESE GraphVisit & TourTest Case vs Test PathSlide 16Basic BlockSlide 18Function CallsControl Flow GraphSlide 21Node CoverageEdge CoverageNode vs Edge CoverageEdge-Pair CoverageEdge-Pair vs Edge CoverageComplete Path CoverageSimple & Prime PathPrime Path CoverageSlide 30Infeasible Test RequirementsSidetrips/DetoursSlide 33Best Effort TouringComputing Prime PathsSlide 36Example – Simple Paths (2)Example – Prime PathsExample – Test PathsSlide 40Definition/UseData Flow GraphExample (1)Example (2)DU-pair & DU-pathSlide 46NotationsAll-Defs CoverageAll-Uses CoverageAll-DU-Paths CoverageSlide 51Why data flow?Slide 53Subsumption HierarchyRecapToday’s AgendaQuiz 1Quick ReviewContinue on Graph-Based TestingSoftware Testing and Maintenance 1Quick ReviewWhat is a basic block? Software Testing and Maintenance 2Software Testing and Maintenance 3Graph-Based Testing Introduction Basic Concepts Control Flow Testing Data Flow Testing SummarySoftware Testing and Maintenance 4Motivation 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.Software Testing and Maintenance 5Major 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 executedSoftware Testing and Maintenance 6Graph 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 effectsSoftware Testing and Maintenance 7Graph-Based Testing Introduction Basic Concepts Control Flow Testing Data Flow Testing SummarySoftware Testing and Maintenance 8Graph 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.Software Testing and Maintenance 9Examplen0n1n2n3n3n4n7n0n1n2n5n6n8n9N = {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 10Path, 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 runSoftware Testing and Maintenance 11Reachability 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 12Examplen3n4n7n0n1n2n5n6n8n9p1 = [n0, n3, n7]p2 = [n1, n4, n8, n5, n1]p3 = [n4, n8, n5]reach(n0) = ? reach(n5) = ?Software Testing and Maintenance 13SESE Graphn0n1n2n3n4n5n6Software Testing and Maintenance 14Visit & 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.Software Testing and Maintenance 15Test Case vs Test Pathn0n1n2n3a < ba > ba = bt1: (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 16Graph-Based Testing Introduction Basic Concepts Control Flow Testing Data Flow Testing SummarySoftware Testing and Maintenance 17Basic 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 18Example1. begin2. int x, y, power;3. float z;4. input (x, y);5. if (y < 0)6. power = -y;7. else8. 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 Exit1 2, 3, 4, 5 2 52 6 6 63 8 8 84 9 9 95 10 10 106 11, 12 11 127 14 14 148 15 15 159 16 16 16Software Testing and Maintenance 19Function Calls Should a function call be treated like a regular statement or as a separate block of its own?Software Testing and Maintenance 20Control 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.Software Testing and Maintenance 21Examplestartend12 3456789falsefalsetruetruetruefalseSoftware Testing and Maintenance 22Node 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