Fault Detection Condition

Consider the following function:

boolean pass(int a, int b) {
    if (a >= 0 && b >= 0) {
        int mean = (a - b) / 2; // should be (a + b) / 2
        return mean >= 40;
    } else {
        return false;
    }
}

The table below demonstrates three test cases that evaluate incorrectly for different reasons.

These tests cannot reveal the fault because they do not satisfy the fault detection condition. A fault detection condition consists of three constraints:

Reachability Constraint

---

The test input must be able to reach the faulty statement such that it is executed.

In the example, test #1 exercises the else condition so mean is never created.

This error holds for any \(a, b: (a < 0) \vee (b < 0)\). So the reachability constraint is \(a \geq 0 \wedge b \geq 0\).

Test #1 gives \(b < 0\), so it does not satisfy the reachability constraint.

Necessity Constraint (State Infection)

---

The test input must make the faulty statement produce an incorrect intermediate result.

In the example, test #2 gives (a - b) == (a + b), so mean is calculated correctly despite the error.

This error holds for any \((a - b) = (a + b)\), or \(b = 0\), so the necessity constraint is \(b \neq 0\).

Test #2 gives \(b = 0\), so it does not satisfy the necessity constraint.

Propagation Constraint

---

The test input must propagate the incorrect intermediate result so that the final result is incorrect and observable.

In the example, test #3 gives mean == 45, and since 45 >= 40 both the correct and incorrect implementations return true.

There are two options here:

• \((a - b) \geq 80 \wedge (a + b) < 80\). Since \(a \geq 0 \wedge b \geq 0\), this is impossible.
• \((a - b) < 80 \wedge (a + b) \geq 80\).

So the propagation constraint is \((80 - b) < a < (80 + b)\).

Test #3 gives \(70 < 100 < 90\), which is false. So test #3 doesn't satisfy the propagation constraint.

Fault Detection Condition

These three constraints together form the complete fault detection condition: \[ a \geq 0 \text{ and }\\ b > 0 \text{ and }\\ (80 - b) < a < (80 + b) \]

A test case can only reveal the fault if it matches this condition.

Note that if the correctness of mean = (a - b) / 2 and mean = (a + b) / 2 were flipped, this error condition would still hold.

In reality, we don't know whether code under a given test is faulty. Even if it is faulty, we don't know exactly where or in what way. This is an experience game. When a test has demonstrated the presence of a fault, we know the detection condition has been met. A test misses the chance of revealing a fault only because it does not satisfy the detection condition.

Generating Test Cases

Fault detection conditions can also be used to generate test cases or prove functional equivalence. For the above example, we may generate a test, e.g., \(a = 60, b = 50\).

• When a test can be generated from the condition, it demonstrates that the two versions are functionally equivalent.
• If the condition is unsatisfiable, the two versions are functionally equivalent.

Fault Detection Condition Exercise

Consider the following faulty code snippet:

boolean foo(int x, int y) {
    int z;
    if (x > 0) {
        z = x * y;
    } else {
        z = y + y; // Should be y * y
    }
    return z > y;
}

1. Can the following test cases reveal the fault? Why or why not?

   • foo(1, 1)
     • No, because \(x > 0\) only the correct branch is exercised.
     • \(z > y\) returns the expected value.
     • Not satisfied: reachability constraint
       • \(x \leq 0\)
   • foo(0, 0)
     • No. The else branch is exercised, but \((y + y) = (y \cdot y)\) for \(y = 0\).
     • \(z > y\) returns the expected value.
     • Not satisfied: necessity constraint
       • \((y + y) = (y \cdot y)\), meaning \(y \not\in \{0, 2\}\)
   • foo(0, 2)
     • No. The else branch is exercised, but \((y + y) = (y \cdot y)\) for \(y = 2\).
     • \(z > y\) returns the expected value.
     • Not satisfied: necessity constraint
       • \(y \not\in \{0, 2\}\) as above.
   • foo(0, 3)
     • No.
       • The else branch is exercised.
       • \((y + y) = 6 \neq 9 = (y \cdot y)\), so the intermediate result is incorrect.
       • However, because \(z = 6 > 3 = y\) the incorrect intermediate result doesn't produce an incorrect and observable final result. \(z > y\) returns the expected value.
         • Reworded: both correct and incorrect versions return a correct result.
     • Not satisfied: propagation constraint
       • \((y + y > y) \not\equiv (y \cdot y > y)\)
       • Two scenarios:
         • \(y + y > y\) and \(y \cdot y \leq y\)
           • \(y > 0\) and \(0 \leq y \leq 1\)
           • So \(0 < y \leq 1\).
         • \(y + y \leq y\) and \(y \cdot y > y\)
           • \(y \leq 0\) and \((y < 0 \text{ or } y > 1)\)
           • So \(y < 0\).
       • Putting these scenarios together reduces to \(y \leq 1: y \neq 0\).

2. What is the complete fault detection condition?

   • Reachability Constraint: \(x \leq 0\)
   • Necessity Constraint: \(y \not\in \{0, 2\}\)
   • Propagation Constraint: \(y \leq 1 : y \neq 0\)

So the full fault detection condition is:

• \(\{(x, y) : x \leq 0, y \leq 1 : y \neq 0\}\)
• x <= 0 and y <= 1 and y != 0.