🔬 CSS323 — White-Box Testing Cheat Sheet

1. What Is White-Box Testing?

One-liner: Testing based on internal logic — you open the hood and design tests based on the code structure.

• Also called Structural Testing
• Expected results still come from requirements (not from the code itself!)
• It is a technique for designing tests — NOT a level of testing
• Applies primarily to lower levels: unit and component testing

🚗 Analogy: Black-box = test-drive the car. White-box = open the hood, inspect the engine. Same car, completely different perspective.

2. White-Box Testing Techniques (4 families)

1. Logic Coverage — branch, statement, condition, path
2. Data-flow Coverage — def/use pairs
3. Path Conditions and Symbolic Evaluation
4. Other (e.g., fault-based testing)

3. Control Flow Graph (CFG) Basics

A CFG represents a program as nodes (statements/decisions) and edges (control flow between them).

🗺️ Analogy: CFG is a map of the program — nodes are stops, edges are roads. Testing = making sure you've travelled every road.

4. Logic Coverage Types (6 types — know all!)

5. Statement Coverage

Every statement executed at least once. Simplest form.

• Also called: Node Coverage
• How many test cases? → Enough to hit every node

Example: if (Y <= 0) then Y := -Y; while (Y > 0) do input(X); Y := Y-1

→ Just 1 test case Y = -1 covers all nodes: takes the then branch AND enters the loop

⚠️ Statement coverage can be achieved while missing entire branches! It's the weakest criterion.

6. Branch Coverage

Every branch edge traversed AND every entry point taken ≥ once.

• Also called: Edge Coverage
• For an if-else: must test both the true path AND the false path

Branch ⇒ Statement? (Does branch coverage guarantee statement coverage?)

$\boxed{\text{Branch Coverage} \Rightarrow \text{Statement Coverage} \quad \text{(assuming no dead code)}}$

• YES, normally — traversing all branches means visiting all statements
• Exception: Dead code = code unreachable via any executable path (Branch coverage can't help you there)

Statement ⇒ Branch? (Does statement coverage guarantee branch coverage?)

NO — You can execute all statements with 1 test case and still miss a branch direction (e.g., never take the false path of an if)

🍎 Swift analogy: guard let x = optional else { return } — statement coverage hits return once. Branch coverage requires also testing when optional IS nil (the else path gets taken).

7. Condition Coverage

Each individual condition in a compound predicate must be True ≥ once AND False ≥ once.

• A branch predicate may have multiple conditions: if (Y <= 0) or (X = 0)
• Condition coverage ≠ branch coverage (you can satisfy each condition's T/F without testing the overall predicate's outcome both ways)
• Normally:

$\boxed{\text{Condition Coverage} \Rightarrow \text{Branch Coverage}}$

Condition Table for if A or B:

💡 Branch coverage only needs T and F for the whole expression. Condition coverage needs T and F for each component (A and B separately).

8. Branch/Condition Coverage

Achieves BOTH Branch AND Condition coverage simultaneously.

$\boxed{\text{Branch/Condition} \Rightarrow \text{Branch Coverage AND Condition Coverage}}$

9. Compound Condition Coverage

All combinations of condition values at every branch statement covered.

• Motivation: compilers use short-circuit evaluation
  • if (A) or (y/x=5) → if A is True, y/x=5 is never evaluated → division by zero hidden!
• Forces every combination: TT, TF, FT, FF
• Also called: Multiple Condition Coverage

$\boxed{\text{Compound Condition} \Rightarrow \text{Branch/Condition Coverage}}$

Example — if (Y<=0) or (X=0) — 4 combinations required:

🎮 Analogy: Testing a two-button combo in a game controller — you can't just test each button alone. You need all 4 combinations (both pressed, only A, only B, neither).

10. Path Coverage

All program paths traversed ≥ once.

• Theoretically strongest but impractical with loops
• A for loop repeating 30 times with 3 paths = $3^{30}$ paths!

$\boxed{V(\text{total paths}) = \prod_{i=1}^{n} (\text{paths per iteration}_i)}$

Practical alternatives when Path Coverage is impossible:

1. Loop Coverage
2. Basis Paths Coverage
3. Data-flow Coverage

11. Loop Coverage

Loop body must be executed 0, 1, 2, t, max, and max+1 times.

🛗 Elevator analogy: Test the elevator when: no floors pressed (0), pressed once, pressed twice, pressed normal number, pressed maximum floors, pressed more than maximum.

12. Basis Paths Coverage

Design test cases to execute all linearly independent paths ≥ once.

• Achieves 100% Statement Coverage AND 100% Branch Coverage
• Uses McCabe's Cyclomatic Complexity to find the number of independent paths
• Rule for loops in basis paths:
  • while loop body executed at most once
  • repeat-until loop body executed at most twice

$\boxed{\text{Basis Paths} \Rightarrow \text{Branch} \Rightarrow \text{Statement}}$

13. Cyclomatic Complexity — Three Formulas

V(G) = number of linearly independent paths = minimum number of test cases for Basis Paths coverage.

Developed by Thomas J. McCabe, Sr. in 1976.

$\boxed{V(G) = P + 1}$ where $P$ = number of predicate nodes (decision nodes: if, while, for, case…)

$\boxed{V(G) = \text{Number of Regions in the Flow Graph}}$ (Count enclosed areas including the outer infinite region)

$\boxed{V(G) = E - N + 2}$ where $E$ = number of edges, $N$ = number of nodes

🍎 Xcode analogy: Cyclomatic Complexity is literally a metric Xcode can show you. Apple recommends keeping functions below CC = 10. Higher CC = harder to test = harder to maintain.

✅ Worked Example (from lecture):

$V(G) = P+1 = 3+1 = 4 \quad \checkmark$ $V(G) = E-N+2 = 10-8+2 = 4 \quad \checkmark$ $V(G) = R = 4 \quad \checkmark$

→ 4 independent paths → need 4 test cases for basis path coverage

Exercise Answer (IF A=10, IF B>C):

IF A = 10 THEN        ← predicate node 1
  IF B > C THEN       ← predicate node 2
    A = B
  ELSE
    A = C
  ENDIF
ENDIF
Print A, B, C

• P = 2 predicate nodes → V(G) = 2 + 1 = 3
• Regions = 3 (left region, right region, outer region)
• E - N + 2: count edges and nodes in the flowchart diagram

14. Coverage Subsumption Hierarchy (Part I — Logic)

"A ⇒ B" means "achieving A guarantees achieving B" (A is stronger, subsumes B)

             Path
           /      \
          ↓        ↓
 Compound          Basis Paths    Loop
 Condition              ↓
      ↓         Branch/Condition
 Branch/         /    ↓
 Condition ←---      Branch
      ↓                ↓
 Condition          Statement

Key subsumption rules:

• Path ⇒ Basis Paths ⇒ Branch ⇒ Statement
• Compound Condition ⇒ Branch/Condition ⇒ Branch ⇒ Statement
• Condition ⇒ Branch ⇒ Statement
• Path ⇒ Loop

🔵 PART II — Data-Flow Coverage

15. Data-Flow Coverage — Core Idea

Cover paths along which variables are defined and then used.

The key question: "After a variable is set, is it actually used before being overwritten?"

16. Variable Definition (DEF)

A variable v is DEFINED when it appears on the:

• Left-hand side of an assignment: x = 17, x = y+1
• Input statement: read(x), input(x)
• Call-by-reference parameter: update(&x, y)

17. Variable Use (USE)

A variable v is USED when it appears on the:

• Right-hand side of an assignment: y = x + 17
• Call-by-value parameter: y = sqrt(x), update(x, y)
• Predicate of a branch statement: if (x > 0)

Two Types of Use:

Example: if (x > 0) { print(y); }

• x → p-use (in predicate)
• y → c-use (in computation)

A variable can be both used AND redefined in one statement: y = y + x — USE of y (RHS) and DEF of y(LHS)

18. Key Data-Flow Terms

⚠️ A du-pair does NOT require a feasible def-clear path — it only requires that one exists in the graph structure.

19. Dataflow Coverage Criteria (3 levels)

$\boxed{\text{All-du-paths} \Rightarrow \text{All-Uses} \Rightarrow \text{All-Defs}}$

20. Full Subsumption Hierarchy (Complete)

                        PATH
                       /    \
                      ↓      ↓
         Compound   All-du-paths    Loop
         Condition       ↓
             ↓        All-Uses
         Branch/     /     ↓
         Condition  ↓    All-Defs
             ↓    Basis Paths
         Condition      ↓
                      Branch
                        ↓
                    Statement

Memory trick: Strongest to weakest on the logic side:

Path → Compound → B/C → Condition → Branch → Statement

Memory trick: Strongest to weakest on the dataflow side:

All-du-paths → All-Uses → All-Defs → (overlaps with Branch)

📋 STEP-BY-STEP EXAM GUIDES

🛠️ How to Compute Cyclomatic Complexity (Step-by-Step)

Given: A code fragment OR a flow graph diagram.

Step 1 — Draw / Identify the CFG

• Assign a number to each node
• Draw edges for each control flow (if true, if false, loop back, etc.)

Step 2 — Count the three things:

• $P$ = number of predicate nodes (any node with 2 outgoing edges: if, while, for, switch)
• $N$ = total number of nodes
• $E$ = total number of edges

Step 3 — Apply any of the 3 formulas (all give the same answer): $V(G) = P + 1 \qquad \text{or} \qquad V(G) = E - N + 2 \qquad \text{or} \qquad V(G) = R$

Step 4 — List the independent paths:

• Start with the "straight-through" path (all conditions false / skip all)
• Each new path changes ONE decision from the previous path
• Total = V(G) paths

🍎 Swift tip: An if with no else = 1 predicate node. An if-else if-else = 2 predicate nodes. A switch with 5 cases = 4 predicate nodes (5-1).

🛠️ How to Identify DU-Pairs (Step-by-Step)

Given: Code + CFG with numbered nodes.

Step 1 — Find all DEFs for each variable:

• Look for: LHS of assignment, input statements, call-by-reference params
• Record: which node number is the DEF

Step 2 — Find all USEs for each variable:

• Look for: RHS of assignment, predicates (p-use), output, call-by-value params
• Record: node number (c-use) or edge <a,b> (p-use) for each USE

Step 3 — For each (def node, use node/edge) pair:

• Trace: is there a path from the DEF node to the USE node/edge that has no re-definition of the variable?
• If yes → this is a du-pair, record the def-clear path(s)

Step 4 — Build the DU-pair table:

| du-pair | path(s) |
| (def_node, use_node) | <node, node, ...> |

Step 5 — Mark infeasible paths:

• Can this path actually execute given the code logic?
• If not → mark as infeasible!

Worked Example — Variable A in Example 1:

Code:
1. input(A,B)       ← DEF of A at node 1
   if (B>1) {
2.   A = A+7        ← DEF of A at node 2, USE of A (c-use, RHS)
   }
3. if (A>10) {      ← USE of A (p-use) → edge <3,4> and <3,5>
4.   B = A+B        ← USE of A (c-use)
   }
5. output(A,B)      ← USE of A (c-use)

DEFs of A: node 1, node 2 USEs of A:

• node 2 (c-use): A+7 uses A
• edge <3,4> (p-use): A>10 is true
• edge <3,5> (p-use): A≤10 is false (A>10 is false)
• node 4 (c-use): A+B uses A
• node 5 (c-use): output(A,B) uses A

DU-pairs for A:

🛠️ How to Check Coverage Criteria (Step-by-Step)

Checking All-Defs Coverage:

Goal: Every DEF must have ≥ 1 du-pair that is covered by the test cases.

Step 1: List all definitions (which nodes define the variable)

Step 2: For each definition node, check: do the given test case paths cover at least one du-pair starting from that def?

Step 3: If every def node has at least one covered du-pair → All-Defs ✅

Checking All-Uses Coverage:

Goal: Every du-pair must be covered by at least one test case path.

Step 1: List ALL du-pairs (from your table)

Step 2: For each test case path, identify which du-pairs it subsumes (is a sub-path of the test path AND is def-clear)

Step 3: Check: is every du-pair in the table covered by at least one test case?

Step 4: If any du-pair has no ✓ → All-Uses NOT achieved. Identify which du-pair is missing.

Step 5: To fix: find what input values force the specific uncovered path to execute.

Worked Example — Checking Coverage with 3 paths:

Test cases: <1,2,3,4,5>, <1,3,4,5>, <1,2,3,5>

All-Defs: def@1 covered by (1,2)✓, def@2 covered by (2,4)✓ → All-Defs ✅

All-Uses: du-pair (1, <3,5>) is never covered → All-Uses ❌

Fix: Add test case <1,3,5> = input where B ≤ 1 (skip node 2, A not redefined) AND A ≤ 10 (skip node 4)

🛠️ Exercise 1 Answer — Variable B DU-Pairs

Code:
1. input(A,B)       ← DEF of B at node 1
   if (B>1) {       ← USE of B (p-use) → edges <1,2> and <1,3>
2.   A = A+7
   }
3. if (A>10) {
4.   B = A+B        ← DEF of B at node 4, USE of B (c-use, RHS)
   }
5. output(A,B)      ← USE of B (c-use)

DEFs of B: node 1, node 4

USEs of B:

• edge <1,2> (p-use): B>1 true
• edge <1,3> (p-use): B≤1 false (B>1 is false)
• node 4 (c-use): A+B on RHS
• node 5 (c-use): output(A,B)

DU-pairs for Variable B:

🛠️ Exercise 2 Answer — Coverage Check for Variable B

Test cases: <1,2,3,4,5>, <1,3,4,5>, <1,2,3,5>

Question 2.1 — Are these paths def-clear for B?

Question 2.2 — All-Defs and All-Uses check:

• All-Defs for B: def@1 ✅, def@4 ✅ → All-Defs ACHIEVED ✅
• All-Uses for B: All du-pairs covered → All-Uses ACHIEVED ✅

Variable B is fully covered by the 3 test cases! Variable A is the problematic one.

Question 2.3 — Additional test case needed?

• For variable B: no additional test cases needed
• For variable A: need <1,3,5> to cover du-pair (1, <3,5>) for All-Uses

21. Big Picture Summary

WHITE-BOX TESTING
  ├── Structural/internal logic
  ├── Expected results from REQUIREMENTS (not code)
  └── Applies to unit + component testing

LOGIC COVERAGE (6 types, weakest→strongest)
  Statement → Branch → Condition → Branch/Condition
  → Compound Condition → Path

SUBSUMPTION (A⇒B means A is stronger, guarantees B)
  Path ⇒ All-du-paths ⇒ All-Uses ⇒ All-Defs
  Path ⇒ Basis Paths ⇒ Branch ⇒ Statement
  Compound ⇒ B/C ⇒ Condition ⇒ Branch ⇒ Statement
  All-Uses ⇒ Branch
  Path ⇒ Loop

CYCLOMATIC COMPLEXITY
  V(G) = P+1 = E-N+2 = R (number of regions)
  = minimum test cases for Basis Paths

DATA-FLOW KEY CONCEPTS
  DEF: LHS of assignment, input(), call-by-ref
  USE: RHS of assignment, predicate (p-use), output, call-by-val
  du-pair: (def_node, use_node/edge) with def-clear path

DATA-FLOW CRITERIA (weakest→strongest)
  All-Defs → All-Uses → All-du-paths

🍎 Final Apple thought: White-box testing is what Apple's compiler team does internally. When they test the Swift compiler, they don't just test "does my code compile?" — they trace every path through the type checker, every branch in the optimizer, every def-use chain in the IR. That's white-box, industrial-scale.

Cheat sheet for CSS323 Software Engineering — Chapter 8.5: White-Box Testing The bugs aren't in the black box. They're hiding in the branches you never tested. 🔍