Predicates, Path Predicates and Achievable Paths in Software Testing

Path Sensitizing

Review: Achievable and Unachievable Paths:

• We want to select and test enough paths to achieve a satisfactory notion of test completeness, such as C₁ + C₂
• Extract the programs control flow graph and select a set of tentative covering paths
• For any path in that set, interpret the predicates along the path as needed to express them in terms of the input vector
• In general, individual predicates are compound or may become compound as a result of interpretation
• Trace the path through by multiplying the individual compound predicates to achieve a Boolean expression such as

        (A + BC) (D + E) (FGH) (IJ) (K) (I) (L)

• Multiply the expression to achieve a sum of products form:

        ADFGHIJKL + AEFGHIKL + BCDFGHIJKL + BCEFCHIJKL

• Each product term denotes a set of inequalities, that if solved will yield an input vector that will drive the routine along the designated path
• Solve any one of the inequality sets for the chosen path, and you have found a set of input values for the path
• If you can find a solution, the the path is achievable
• If you cannot find a solution, then the path is achievable
• If you cannot find a solution to any of the sets of inequalities, the path is not achievable
• The act of finding a set of solutions to the path predicate expression is called path sensitization

Heuristic Procedures for Sensitizing Paths:

• This is a workable approach, instead of selecting the paths without considering how to sensitize, attempt to choose a covering path set that is easy to sensitize and pick hard to sensitize paths only as you must to achieve coverage
• Identify all variables that affect the decision
• Classify the predicates as dependent or independent
• Start the path selection with uncorrelated, independent predicates
• If coverage has not been achieved using independent uncorrelated predicates, extend the path set using correlated predicates
• If coverage has not been achieved, extend the cases to those that involve dependent predicates
• Finally, use correlated and dependent predicates