Slide 1Control-Flow TestingMotivationProgram RepresentationControl Flow GraphsExample of a CFGCFG: The For LoopCFG: The For Loop (cont’d)CFGs: Switch-CaseCFGs: Switch-Case (cont’d)CFGs: Switch-Case (cont’d)CFGs: Switch-Case (cont’d)CFGs: Switch-Case (cont’d)Program PathsPath ConditionPath Condition (cont’d)Number of PathsNumber of Paths (cont’d)Number of Paths (cont’d)Number of Paths (cont’d)Number of Paths (cont’d)Number of Paths (cont’d)Number of Paths (cont’d)Infinite PathsInfeasible PathsInfeasible Paths (cont’d)Infeasible Paths (cont’d)Infeasible Paths (cont’d)Control-Flow CriteriaOverviewStatement CoverageStatement Coverage (cont’d)Statement Coverage (cont’d)Statement Coverage (cont’d)Statement Coverage (cont’d)Possible Predicate FaultsBranch CoverageBranch Coverage (cont’d)Branch Coverage (cont’d)Condition CoverageCondition Coverage (cont’d)Condition/Decision CoverageCondition / Decision Coverage (cont’d)Multiple Condition CoverageMultiple Condition Coverage (cont’d)Multiple Condition Coverage (cont’d)Multiple Condition Coverage (cont’d)Modified Condition/Decision CoverageModified Condition/Decision Coverage (cont’d)Modified Condition/Decision Coverage (cont’d)Modified Condition/Decision Coverage (cont’d)Modified Condition/Decision Coverage (cont’d)Modified Condition/Decision Coverage (cont’d)Modified Condition/Decision Coverage (cont’d)Modified Condition/Decision Coverage (cont’d)Modified Condition/Decision Coverage (cont’d)Modified Condition/Decision Coverage (cont’d)Modified Condition/Decision Coverage (cont’d)Modified Condition/Decision Coverage (cont’d)Modified Condition/Decision Coverage (cont’d)Modified Condition/Decision Coverage (cont’d)SubsumptionSubsumption HierarchySummaryExhaustive Path TestingA “real” ExampleThe COUNT ProgramThe COUNT ProgramThe COUNT ProgramTest CasesOutcomeDebugging the COUNT ProgramDebugging the COUNT Program (cont’d)feofDebugging the COUNT Program (cont’d)Lessons...CS 451Software EngineeringWhite Box TestingPart 1: Control-Flow Testing1Control-Flow Testing•Control-flow testing is a structural testing strategy that uses the program’s control flow as a model.•Control-flow testing techniques are based on judiciously selecting a set of test paths through the program.•The set of paths chosen is used to achieve a certain measure of testing thoroughness.–E.g., pick enough paths to assure that every source statement is executed as least once.2Motivation•The source code is the “ultimate” program specification.–“Ultimate” does not imply “without errors”, but rather “the best we have”.•Execution control is one of the essential things we implement when we create a program.•We would like to test our program vis a vis the control structure we have implemented.–We hope that by exercising the control structure of our program in a systematic way we’ll be able to expose faults. •Control-flow testing is most applicable to unit testing.3Program Representation 4Control Flow Graphs•A Control Flow Graph (CFG) is a static, abstract representation of a program.•A CFG is a directed graph G = (N, E) –Each node, in the set N, is either a statement node or a predicate node.–A statement node represents a simple statement. Alternatively, a statement node can be used to represent a basic block.–A predicate node represents a conditional statement. –Each edge, in the set E, represents the flow of control between statements.–Optionally, we use circles to represent statement nodes, and rectangles to represent predicate nodes.5Example of a CFGscanf (“%d, %d”, &x, &y);if (y < 0)pow = -y;elsepow = y;z = 1.0;while (pow != 0) {z = z * x;pow = pow – 1;}if (y < 0)z = 1.0 / z ;printf(“%f”, z);y < 0printf ( … )scanf ( … )pow = -yTFpow = ypow != 0TFz = z * xpow = pow-1y < 0TFz = 1.0/zz = 1.06CFG: The For LoopWhat does the CFG for the following code fragment look like?S0;for ( j = 1; j <= limit; j=j+1 ){S1;}Sn;7CFG: The For Loop (cont’d)S0;for ( j = 1; j <= limit; j=j+1 ){S1;}Sn;S1S0Tj = 1Fj  limitj=j+1Sn8CFGs: Switch-CaseS0;switch ( e ){case v1:S1;break;case v2:S2;break;default:S3;}Sn;What does the CFG for the following code fragment look like? 9CFGs: Switch-Case (cont’d)S0;switch ( e ){case v1:S1;break;case v2:S2;break;default:S3;}Sn;TSnFS3S2S1S0e == v1Fe == v2T10CFGs: Switch-Case (cont’d) S0;switch ( e ){case v1:S1;break;case v2:S2;break;case v3:S3;default:S4;}Sn;TSnFS4S2S1S0e == v1Fe == v2TS3Fe == v3T11CFGs: Switch-Case (cont’d) S0;switch ( e ){case v1:case v2:S2;break;case v3:S3;break;default:S4;}Sn;S0e == v1TSnFS3S2e == v2Fe == v3TFTS4 12CFGs: Switch-Case (cont’d)S0;switch( e ){case v1:S1;case v2:S2;case v3:S3;default:S4;}Sn;TSnFS4S2S1S0e == v1Fe == v2TS3Fe == v3T13Program Paths •A path is a unique sequence of executable statements from one point of the program to another point.•In a graph, a path is a sequence (n1, n2, …, nt) of nodes such that <ni,ni+1> is an edge in the graph,  i=1, 2,.., t-1 (t > 0).14Path Condition•Path condition: the conjunction of the individual predicate conditions which are generated at each branch point along the path. •The path condition must be satisfied by the input data in order for the path to be executed.15Path Condition (cont’d)Example: PC(1,2,4,5,6,8,10) = (y≥0 ∧ pow==0 y ∧ ≥0)1234TF567TF8910TFFy < 0pow != 0y < 016Number of Paths The simple CFG shown here has 2 different paths:(S1, P1, S2, S3)(S1, P1, S3)S1P1S2S3return maxmax = xmax = yTFy > x17Number of Paths (cont’d)How many paths?if ((A||B) && (C||D){S1;}else{S2;}18Number of Paths (cont’d)Although it is possible to represent the program using the CFG shown on the left, it is incorrect to assume that there are only 2 paths. P1S1SnTFS2(A||B) && (C||D)19Number of Paths (cont’d)There are:2 statements + Sn 4 branches7 paths (4T + 3 F)(A, C, S1)(A, C, D, S1)(A, C, D, S2)(A, B, C, S1)(A, B, C, D, S1)(A, B, C, D, S2) (A, B, S2) DS1SnTFS2CABTTTFFF20Number of Paths (cont’d)Two procedures with the same number of predicates and branches, but different number of path.S1AS2BS3CS4S1AS2BS3CS421Number of Paths (cont’d)Example #1•(A, B, C, S4)•(A, S1, B, C, S4)•(A, S1, B, C, S3, S4)•(A, S1, B, S2, C, S4)•(A, S1, B, S2, C, S3, S4)•(A, B, S2, C, S4)•(A, B, S2, C, S3, S4)•(A, B, C, S3, S4)Example #2•(A, S1, S4)•(A, B, S2, S4)•(A, B, C, S3, S4)•(A, B, C, S4)22Number of Paths