Control Flow Graph

software-engineering testing

Definition

Control Flow Graph (CFG)

An intra-procedural Control Flow Graph is a graph $G=(N,E)$ used to represent the execution paths of a procedure $P$. It serves as the foundation for structural testing (white-box testing).

Elements

A CFG consists of the following components:

Nodes

Nodes in the graph represent basic blocks (plus distinct entry and exit blocks).

Basic Block

A maximal length sequence of non-conditional instructions such that:

1. Single Entry: No code within the block is the destination of a jump instruction (only the first instruction is).
2. Single Exit: Only the last instruction may cause the program to jump to a different block.

Implication: If the first instruction executes, the entire block executes.

• Entry Block: A special node with an edge to the first basic block of the procedure.
• Exit Block: A special node that all “return” statements (explicit or implicit) connect to.

Edges

Edges represent the flow of control. An edge exists from block A to block B if the execution of A can be immediately followed by B.

• Unconditional: Sequential flow or goto.
• Conditional: Branches (A \to B if condition C holds).

Construction

The graph is constructed by analysing control structures:

1. Sequential Statements: Grouped into a single Basic Block until a jump or target is encountered .
2. Conditional (if): Splits flow into labelled edges (True/False).
3. Loops (for/while): Creates cycles in the graph (Back-edges).
4. Implicit Returns: All paths must eventually connect to the unique Exit Block.

Purpose

The CFG allows us to define and measure coverage criteria:

Control Flow Coverage

• Statement Coverage: % of executed basic blocks.
• Branch Coverage: % of executed edges (most widely used in industry).
• Path Coverage: % of executed paths (often infeasible due to loops).
• Loop Coverage: Ensuring loops are executed 0, 1, and >1 times.

Data Flow Coverage

The CFG is also used to track variable usage:

• Variable Definition: A block that assigns a value to variable v.
• Variable Use: A block that reads v.
• Def-Clear Path: A path from a definition to a use without re-defining the variable.

Example: absoluteSum

Code:

public int absoluteSum(int x, int y) {
    int sum = 0;                  // BB_1 (Entry logic)
    if (x < 0) {                  // BB_1 (Condition matches definition of block if distinct)
        x = -x;                   // BB_2
    }
    if (y < 0) {                  // BB_3
        y = -y;                   // BB_4
    }
    sum = x + y;                  // BB_5
    return sum;                   // BB_5 (Exit logic)
}
 

CFG:

graph TD
    Entry((Entry)) --> B1["BB<sub>1</sub>: sum=0; if x<0"]
    B1 -- "True" --> B2["BB<sub>2</sub>: x = -x"]
    B1 -- "False" --> B3{"BB<sub>3</sub>: if y < 0"}
    B2 --> B3
    B3 -- "True" --> B4["BB<sub>4</sub>: y = -y"]
    B3 -- "False" --> B5["BB<sub>5</sub>: sum=x+y; return"]
    B4 --> B5
    B5 --> Exit((Exit))