Path Testing

Structural Testing (White-box Testing)

• Also known as glass/white/open box testing
• A software testing technique whereby explicit knowledge of the internal workings of the item being tested are used to select the test data
• Black-box testing uses program specification
• White-box testing is based on specific knowledge of the source code to define the test cases and to examine outputs.

White-box Testing

• White-box testing methods are very amenable to:
  • Rigorous definitions
    • Control flow, data flow, coverage criteria
  • Mathematical analysis • Graphs, path analysis
  • Precise measurement
    • Metrics, coverage analysis

Program Graph - Definition

• Given a program written in an imperative programming language, its program graph is a directed graph in which nodes are statement fragments, and edges represent flow of control
• A complete statement is also considered a statement fragment

DD-Path

• A decision-to-decision path (DD-Path) is a chain in a program graph such that:
  • Case1: it consists of a single node with indeg=0
  • Case2: it consists of a single node with outdeg=0
  • Case3: it consists of a single node with indeg ≥ 2 or outdeg ≥ 2
  • Case4: it consists of a single node with indeg =1, and outdeg = 1
  • Case5: it is a maximal chain of length ≥ 1 - DD-Paths are also known as segments

DD-Path Graph

• Given a program written in an imperative language, its DD-Path graph is a directed graph, in which nodes are DD-Paths of its program graph, and edges represent control flow between successor DD-Paths.
• Also known as Control Flow Graph

Control Flow Graph Derivation

• Straightforward process
• Some judgement is required
• The last statement in a segment must be a predicate, a loop control, a break, or a method exit
• Let’s try an example...

Control flow graphs

• Depict which program segments may be followed by others
• A segment is a node in the CFG (control flow graphs)
• A conditional transfer of control is a branch represented by an edge
• An entry node (no inbound edges) represents the entry point to a method
• An exit node (no outbound edges) represents an exit point of a method
• An entry-exit path is a path from the entry node to the exit node
• Path expressions represent paths as sequences of nodes
• Loops are represented as segments within parentheses followed by an asterisk
  • Example: ABC(DEF)*DGL
• How many path expressions in this example?

Test Coverage

Code coverage models

• Statement Coverage
• Segment Coverage
• Branch Coverage
• Condition Coverage
• Branch & Condition Coverage
• Modified Condition/Decision Coverage

Statement coverage

• Achieved when all statements in a method have been executed at least once

• How many test cases do we need to achieve statement coverage in our example?

• Segment coverage counts segments rather than statements

• May produce drastically different numbers

  • Assume two segments P and Q
  • P has one statement, Q has nine
  • Exercising only one of the segments will give 10% or 90% statement coverage
  • Segment coverage will be 50% in both cases

• Statement coverage is most used in industry

• Typical coverage target is 80-90%

  • Why don’t we aim at 100%?

Statement coverage problems

• Predicate may be tested for only one value (misses many bugs)
• Loop bodies may only be iterated once
• Statement coverage can be achieved without branch coverage. Important cases may be missed

Branch coverage

• Achieved when every branch from a node is executed at least once
• At least one true and one false evaluation for each predicate
• Can be achieved with D+1 paths in a control flow graph with D 2-way branching nodes and no loops
  • Even less if there are loops

Branch coverage problems

• Short-circuit evaluation means that many predicates might not be evaluated
• A compound predicate is treated as a single statement. If n clauses, 2n combinations, but only 2 are tested
• Only a subset of all entry-exit paths is tested

Condition coverage

• Condition coverage reports the true or false outcome of each condition.
• Condition coverage measures the conditions independently of each other.

𝐶𝑜𝑛𝑑𝑖𝑡𝑖𝑜𝑛 𝐶𝑜𝑣𝑒𝑟𝑎𝑔𝑒 = # 𝑜𝑓 𝑐𝑜𝑛𝑑𝑖𝑡𝑖𝑜𝑛𝑠 𝑡h𝑎𝑡 𝑎𝑟𝑒 𝑏𝑜𝑡h 𝑇 𝑎𝑛𝑑 𝐹 / 𝑡𝑜𝑡𝑎𝑙 # 𝑜𝑓 𝑐𝑜𝑛𝑑𝑖𝑡𝑖𝑜𝑛𝑠

Branch & Condition Coverage

• Sometimes branch and condition coverage is also called as “Decision Coverage”
  • It is computed by considering both branch and individual condition coverage measures

Modified Condition/Decision Coverage

• Key idea: test important combinations of conditions and limiting testing costs
  • Extend branch and decision coverage with the requirement that each condition should affect the decision outcome independently
  • In other words, each condition should be evaluated one time to "true" and one time to "false", and this with affecting the decision's outcome.
• Often required for the mission-critical systems

Dealing with Loops

• Loops are highly fault-prone, so they need to be tested carefully
• Simple view: Every loop involves a decision to traverse the loop or not
• A bit better: Boundary value analysis on the index variable
• Nested loops have to be tested separately starting with the innermost

Test Case Creation

Creating test cases

• In order to increase the coverage of a test suite, one needs to generate test cases that exercise certain statements or follow a specific path
• This is not always easy to do ...

Creating a test case

• The key question for creating a test for a path is:
  • How to make the path execute, if possible.
    • Generate input data that satisfies all the conditions on the path
  • The key items you need to generate a test case for a path:
  • Input vector
  • Predicate
  • Path predicate
  • Predicate interpretation
  • Path predicate expression
  • Create test input from path predicate expression

Input Vector

• Input vector is:
  • A collection of all data entities read by the routine whose values must be fixed prior to entering the routine.
• The members of an input vector are: - Input arguments to the routine
  • Global variables and constants - Files
  • Network connections
  • Timers

Predicate

• A predicate is
  • A logical function evaluated at a decision point.
    • In the following example, each of a < b and c < d are predicates

Path Predicate Expression

• A path predicate expression is
  • An interpreted path predicate
• A path predicate interpretation is
  • A path predicate may contain local variables.
  • Local variables cannot be selected independently of the input variables
  • Local variables are eliminated with symbolic execution - A symbolic execution is
  • Symbolically substituting operations along a path in order to express the predicate solely in terms of the input vector and a constant vector.
  • A predicate may have different interpretations depending on how control reaches the predicate.

Attributes of a Path Predicate Interpretation

• The attributes of a path predicate interpretation are:
  • No local variables
  • A set of constraints in terms of the input vector, and, maybe, constants
  • Path forcing inputs are generated by solving the constraints
  • If a path predicate expression has no solution, the path is infeasible

Selecting paths

• A program unit may contain a large number of paths.
  • Path selection becomes a problem
  • Some selected paths may be infeasible
• What strategy would you use to select paths?
  • Select as many short paths as possible
    • Tradeoffs?
  • Choose longer paths
    • Tradeoffs?
• What about infeasible paths?
  • What would you do about them?
  • Make an effort to write program text with fewer or no infeasible paths.