Definition-Use Pair

software-engineering testing

Definition

Definition-Use Pair

A Definition-Use Pair (DU Pair) is a concept in data flow testing that connects the definition of a variable (where it is assigned a value) to its usage (where that value is read).

A DU pair for variable $v$ is a tuple $(d,u)$, where:

1. $d$ is a node in the CFG where $v$ is defined.
2. $u$ is a node in the CFG where $v$ is used.
3. There exists a definition-clear path from $d$ to $u$.

Concepts

Variable Definition & Use

• Definition ($d$): Assignment, parameter, input read (e.g., x = 1, read(x)).
• Use ($u$): Computation, condition, output (e.g., y = x + 1, if (x > 0)).

Definition-Clear Path

A path $d\to \cdots \to u$ is definition-clear for $v$ if no other node on the path re-defines $v$. If $v$ were re-defined at node $k$ (where $d\to \cdots \to k\to \cdots \to u$), then the use at $u$ would rely on the value from $k$, not $d$.

Reaching Definitions Analysis

DU pairs are computed with a reaching-definitions static analysis. For each node $n$ and variable $v$, it computes all definitions of $v$ that possibly reach $n$ via a definition-clear path.

Definitions:

• $pred(n)=\{m\mid (m,n,c)\in E_{CFG}\}$: Predecessors of $n$.
• $succ(m)=\{n\mid (m,n,c)\in E_{CFG}\}$: Successors of $m$.
• $gen(n)=\{v_n\mid n\text{ is a definition for }v\}$: Definitions generated in $n$.
• $kill(n)=\{v_m\mid n\text{ is a definition for }v\wedge m\ne n\}$: Definitions killed in $n$.

Algorithm (Fixpoint Iteration): We compute two sets for every node:

1. $\text{Reach}(n)$: The reaching definitions at the beginning of $n$.

$$Reach(n)=\bigcup _{m\in pred(n)}ReachOut(m)$$

2. $\text{ReachOut}(n)$: The reaching definitions at the end of $n$.

$$ReachOut(n)=(Reach(n)\setminus kill(n))\cup gen(n)$$

Metrics

DU-Pairs Coverage

The percentage of all feasible valid DU pairs that are exercised by the test suite.

$$DU\text{-}PairsCoverage=\frac{\text{Number of executed DU pairs}}{\text{Total number of DU pairs}}\times 100\%$$

• Strength: Stronger than branch coverage and can be equivalent to path coverage in specific cases, but generally more focused on data dependencies.

Example

Example: Simple

1: x = 1;
2: y = 1;
3: if (a) {
4:    x = 0;
5: }
6: return x;

DU Pairs for x:

1. Def at 1: x = 1 reaches usage at 6 if path is $1\to 2\to 3\to 5\to 6$ (Branch a is False).
   • Pair: $(1,6)$.
2. Def at 4: x = 0 reaches usage at 6 if path is $1\to 2\to 3\to 4\to 5\to 6$ (Branch a is True).
   • Pair: $(4,6)$.

DU Pairs for y:

• Def at 2: y = 1.
• Use: None.
• Result: No DU pairs for y.

Coverage Analysis: To achieve 100% DU-Pairs Coverage for x, we need a test where a is True (executes pair $(4,6)$) and a test where a is False (executes pair $(1,6)$).

Example: Invoice Calculation

Exercise 5: Data Flow Coverage

You are given the following function calculateInvoice and an initial test suite.

01 int calculateInvoice(int items, boolean isVIP) {
02   int total = 0;        // d1
03   int surcharge = 0;    // d5
04
05   for (int i = 1; i <= items; i++) {
06     total += 100;       // d2
07
08     if (i % 3 == 0) {
09       surcharge += 20;  // d6
10     } else {
11       surcharge += 10;  // d7
12     }
13   }
14
15   if (isVIP) {
16     total = total - 50; // d3
17   }
18
19   total += surcharge;   // d4
20   return total;
21 }

Initial Tests:

• T1: items = 0, isVIP = false
• T2: items = 1, isVIP = false

a) Control Flow Graph (CFG):

We define the following Basic Blocks (BB):

• BB0 (Entry): Lines 1-5 (initialisation).
• BB1 (Loop Header): Line 5 (condition i <= items).
• BB2 (Loop Body Start): Line 6 (total += 100) and 8 (condition i % 3 == 0).
• BB3 (If True): Line 9 (surcharge += 20).
• BB4 (If False): Line 11 (surcharge += 10).
• BB5 (Loop Increment): Line 5 (i++).
• BB6 (After Loop): Line 15 (condition isVIP).
• BB7 (VIP Branch): Line 16 (total -= 50).
• $BB8 (Exit): Line 19 (total += surcharge) and 20 (return).

Graph:

graph TD
    Entry((Entry)) --> BB0["BB<sub>0</sub>: total=0; sur=0; i=1"]
    BB0 --> BB1{"BB<sub>1</sub>: i <= items"}
    BB1 -- "True" --> BB2{"BB<sub>2</sub>: total+=100; i%3==0"}
    BB1 -- "False" --> BB6{"BB<sub>6</sub>: isVIP"}
    BB2 -- "True" --> BB3["BB<sub>3</sub>: sur+=20"]
    BB2 -- "False" --> BB4["BB<sub>4</sub>: sur+=10"]
    BB3 --> BB5["BB<sub>5</sub>: i++"]
    BB4 --> BB5
    BB5 --> BB1
    BB6 -- "True" --> BB7["BB<sub>7</sub>: total-=50"]
    BB6 -- "False" --> BB8["BB<sub>8</sub>: total+=sur; return"]
    BB7 --> BB8
    BB8 --> Exit((Exit))

b) Reaching Definitions:

Definitions:

• total: $d_1$ (Line 2), $d_2$ (Line 6), $d_3$ (Line 16), $d_4$ (Line 19).
• surcharge: $d_5$ (Line 3), $d_6$ (Line 9), $d_7$ (Line 11).

Analysis Table:

Node $n$	Reach($n$) (In)	ReachOut($n$) (Out)
BB0	$\varnothing$	$\{d_1,d_5\}$
BB1	$\{d_1,d_2,d_5,d_6,d_7\}$	$\{d_1,d_2,d_5,d_6,d_7\}$
BB2	$\{d_1,d_2,d_5,d_6,d_7\}$	$\{d_2,d_5,d_6,d_7\}$ (kills $d_1$)
BB3	$\{d_2,d_5,d_6,d_7\}$	$\{d_2,d_6\}$ (kills $d_5,d_7$)
BB4	$\{d_2,d_5,d_6,d_7\}$	$\{d_2,d_7\}$ (kills $d_5,d_6$)
BB5	$\{d_2,d_6,d_7\}$	$\{d_2,d_6,d_7\}$
BB6	$\{d_1,d_2,d_5,d_6,d_7\}$	$\{d_1,d_2,d_5,d_6,d_7\}$
BB7	$\{d_1,d_2,d_5,d_6,d_7\}$	$\{d_3,d_5,d_6,d_7\}$ (kills $d_1,d_2$)
BB8	$\{d_1,d_2,d_3,d_5,d_6,d_7\}$	$\{d_4,d_5,d_6,d_7\}$ (kills $d_1,d_2,d_3$)

How to build this table?

The table is constructed iteratively until the sets stop changing (fixpoint).

1. Reach(n) comes from predecessors:
   • Example for BB1: It has predecessors BB0 and BB5.
   • $Reach(BB1)=ReachOut(BB0)\cup ReachOut(BB5)$.
   • $Reach(BB1)=\{d_1,d_5\}\cup \{d_2,d_6,d_7\}=\{d_1,d_2,d_5,d_6,d_7\}$.
2. ReachOut(n) applies changes within the block:
   • Formula: $ReachOut(n)=(Reach(n)\setminus kill(n))\cup gen(n)$.
   • Example for BB2:
   • Input: $Reach(BB2)=\{d_1,d_2,d_5,d_6,d_7\}$.
   • Kill: Line 6 defines total ($d_2$), so it kills all other definitions of total ($d_1$ from Line 2).
   • Gen: Line 6 generates $d_2$.
   • Result: Remove $d_1$, add $d_2$, keep everything else ($d_5,d_6,d_7$).
   • $ReachOut(BB2)=\{d_2,d_5,d_6,d_7\}$.

c) DU-Pairs and Coverage:

1. List of DU-Pairs:

Variable total:

• $(2,6)$: Feasible ($items\ge 1$).
• $(6,6)$: Feasible ($items\ge 2$).
• $(2,16)$: Feasible ($items=0,isVIP$).
• $(6,16)$: Feasible ($items\ge 1,isVIP$).
• $(2,19)$: Feasible ($items=0,!isVIP$).
• $(6,19)$: Feasible ($items\ge 1,!isVIP$).
• $(16,19)$: Feasible ($isVIP$).
• $(19,20)$: Feasible (Always).

Variable surcharge:

• $(3,11)$: Feasible ($i=1$, reaches Line 11).
• $(3,9)$: Infeasible. Requires $i=1$ to satisfy $i\%3==0$ (Impossible).
• $(11,11)$: Feasible ($i=1\to 2$).
• $(11,9)$: Feasible ($i=2\to 3$).
• $(9,11)$: Feasible ($i=3\to 4$).
• $(9,9)$: Infeasible. Requires $i\%3==0$ and $(i+1)\%3==0$ (Impossible).
• $(3,19)$: Feasible ($items=0$).
• $(11,19)$: Feasible (End on loop index not div by 3).
• $(9,19)$: Feasible (End on loop index div by 3).

2. Coverage of Initial Tests:

• T1 (items=0, !VIP): Path $0\to 1\to 6\to 8$.
  • Covers: total $(2,19),(19,20)$; surcharge $(3,19)$.
• T2 (items=1, !VIP): Path $0\to 1\to 2\to 4\to 5\to 1\to 6\to 8$.
  • Covers: total $(2,6),(6,19),(19,20)$; surcharge $(3,11),(11,19)$.

Executed Pairs: $\{(2,19),(19,20),(3,19),(2,6),(6,19),(3,11),(11,19)\}$.
Total Feasible Pairs: 15 (8 for total + 7 for surcharge).
Coverage: $7/15\approx 46.6\%$.

3. Extending the Test Suite:

To achieve 100% coverage, we need to cover the remaining pairs:

• total: $(6,6),(2,16),(6,16),(16,19)$.
• surcharge: $(11,11),(11,9),(9,11),(9,19)$.

New Tests:

• T3 (items=0, VIP): Covers $(2,16),(16,19)$.
• T4 (items=4, VIP):
  • Loop: $i=1$ (L11), $i=2$ (L11), $i=3$ (L9), $i=4$ (L11).
  • Covers:
    • total: $(6,6)$ (multiple iterations), $(6,16)$ (after loop).
    • surcharge: $(11,11)$ ($1\to 2$), $(11,9)$ ($2\to 3$), $(9,11)$ ($3\to 4$), $(11,19)$ (end).
• T5 (items=3, !VIP):
  • Loop: $1,2,3$. Ends on 3 (L9).
  • Covers: surcharge $(9,19)$.

4. Feasibility:
Achieving 100% DU-pair coverage is not always possible due to infeasible paths. In this example, pairs like $(3,9)$ and $(9,9)$ are infeasible because the logic ($i\%3==0$) and the loop counter initialization prevent those specific definition-use combinations from ever being executed.