Skip to content

MC DC

1. Modified Condition/Decision Coverage (MC/DC)

MC/DC is a condition coverage technique designed to test important combinations of conditions effectively without the exponential blowup in test suite size associated with Multiple Condition Coverage (MCC).

  • Core Motivation: In MCC, a decision with $n$ conditions requires $2^n$ test cases; MC/DC reduces this to a linear requirement (at least $n+1$ cases) while maintaining similar bug-detection effectiveness.
  • Key Principle: Each basic condition must be shown to independently affect the outcome of a decision. This means changing a single condition while keeping others constant must result in a change to the decision's outcome.
  • Requirements for MC/DC:
    1. Every decision in the program must take both True and False values.
    2. Every condition in each decision must take both True and False values.
    3. Each condition must independently affect the decision outcome.

  • Subsumption Hierarchy: MC/DC is stronger than Branch and Condition/Decision coverage but is subsumed by MCC.

  • To test an AND gate: You must make the other inputs True. (Pick the easiest/shortest path to True).

  • To test an OR gate: You must make the other inputs False. (You have to shut down all other "parallel" paths so only yours is left).

2. Path Testing and Control Flow Graphs (CFG)

Path testing aims to design test cases such that all linearly independent1. To test an AND gate: You must make the other inputs True**. (Pick the easiest/shortest path to True).

  1. To test an OR gate: You must make the other inputs False. (You have to shut down all other "parallel" paths so only yours is left). paths** in a program are executed at least once.

  2. Control Flow Graph (CFG): A tool used to describe the sequence in which instructions execute and how control flows through the program.

    • Nodes: Represent numbered statements in the program.
    • Edges: Represent the transfer of control between statements.
  3. CFG Basics: Every program is composed of three basic structures that can be modeled in a CFG: Sequence, Selection (if-else), and Iteration (while/loops).
  4. Linearly Independent Path: A path that introduces at least one new edge not included in any other independent path. Identifying these is straightforward for simple programs but difficult for complex ones.

3. McCabe’s Cyclomatic Metric

This metric provides an upper bound for the number of linearly independent paths and a quantitative measure of testing difficulty.

  • Calculations for $V(G)$:
    1. Formula 1: $V(G) = E - N + 2$, where $E$ is the number of edges and $N$ is the number of nodes.
    2. Formula 2: $V(G) = \text{Total number of bounded areas} + 1$.
  • Significance: It serves as a lower bound on the number of test cases required to guarantee coverage of all independent paths.
  • Maintenance Insight: High cyclomatic complexity indicates a program is psychologically complex and difficult to understand; many organizations restrict functions to a maximum complexity of ten.

4. Data Flow-Based Testing

This strategy selects test paths based on the locations of definitions and uses of variables.

  • Definitions:
    • DEF(S): The set of variables defined in statement $S$.
    • USES(S): The set of variables used in statement $S$.
  • Live Variables: A variable $X$ is "live" at statement $S1$ if it was defined at a previous statement $S$ and no other definition of $X$ occurs on the path between $S$ and $S1$.
  • Definition-Use (DU) Chain: A triplet $[X, S, S1]$ where variable $X$ is defined at $S$, used at $S1$, and is live at $S1$.
  • Strategy: A common data flow testing goal is to ensure every DU chain is covered at least once, which is particularly useful for nested logic and loops.

5. Mutation Testing (Fault-Based Testing)

Unlike coverage-based testing, mutation testing focuses on the effectiveness of the test suite itself by inserting faults into the program.

  • Process: Small, arbitrary changes (mutants) are made to the code, such as deleting a statement, altering an arithmetic operator (e.g., changing $+$ to $-$), or changing a constant value.
  • Killing Mutants: A mutant is considered "dead" if at least one test case in the suite produces an incorrect result for it; if a mutant remains "alive," the test suite must be enhanced to detect it.

  • Underlying Hypotheses:

    1. Competent Programmer Hypothesis: Programmers create programs close to being correct, differing only by simple errors.
    2. Coupling Effect: Complex errors are usually the result of several simple errors combined; therefore, detecting simple errors is often sufficient.

  • MC/DC

  • Path Testing and CFG
  • McCabe’s Cyclometric Testing
  • Data Flow-based Testing
  • Mutation Testing (Fault-Based Testing)