The Test Oracle

In the previous lesson’s test cases, the expected result was read from the specification: the rule was written down, and the test case repeated it. This is the easiest case. If the rule is not written down, if the computation is too complex to verify by hand, or if no one fully knows the correct result, where does the expected result come from?

This question is called the oracle problem. A test oracle is the source that decides whether the observed result is correct. Without a test oracle there is no test; only a program that has been run.

The Oracle Problem

An oracle has a cost, and that cost is often higher than the test itself. Calling a function is cheap; knowing independently that the returned value is correct is expensive.

The most common oracle is the specified oracle: the expected value is read from the specification and written into the test case. Its limit was seen in the second lesson — if the specification is wrong, the oracle is wrong too, and every test confirms a wrong truth as correct.

Its second limit is scale. For twenty inputs the expected value can be written by hand; for eight hundred it cannot. Once the input space grows, the expected value has to be generated.

For comparison, two more rules are added to the fee computation: a book returned to a different branch adds 5 units, and student members pay half the total, rounded down since there is no fractional currency.

// fee.mjs — three-rule total fee computation
export function totalFee({ daysLate, memberType, offBranch = false }) {
  const base = Math.min(Math.max(daysLate - 3, 0) * 2, 20);
  const total = base + (offBranch ? 5 : 0);
  return memberType === 'student' ? Math.round(total / 2) : total;
}

export function inputs() {
  const list = [];
  for (const memberType of ['member', 'student']) {
    for (const offBranch of [false, true]) {
      for (let daysLate = 0; daysLate <= 20; daysLate += 1) {
        list.push({ daysLate, memberType, offBranch });
      }
    }
  }
  return list;
}

Writing the expected value by hand for eighty-four inputs is not reasonable. Three separate oracles are built.

Independent Second Computation

The first approach computes the same rule a different way. If the actual implementation uses a closed arithmetic form, the second computation sums the days one by one. Because the two paths differ, the odds that they share the same defect are low.

// oracle-second-computation.mjs — a second computation derived independently of the rule
import { totalFee, inputs } from './fee.mjs';

function reference({ daysLate, memberType, offBranch }) {
  let base = 0;
  for (let day = 1; day <= daysLate; day += 1) {
    if (day <= 3) continue;
    if (base >= 20) break;
    base += 2;
  }
  const total = base + (offBranch ? 5 : 0);
  return memberType === 'student' ? Math.floor(total / 2) : total;
}

const deviations = inputs().filter((g) => totalFee(g) !== reference(g));
console.log(`second computation: ${inputs().length} inputs, ${deviations.length} deviations`);
for (const g of deviations.slice(0, 3)) {
  console.log(`  day=${g.daysLate} ${g.memberType} offBranch=${g.offBranch}: computed ${totalFee(g)}, reference ${reference(g)}`);
}

second computation: 84 inputs, 21 deviations
  day=0 student offBranch=true: computed 3, reference 2
  day=1 student offBranch=true: computed 3, reference 2
  day=2 student offBranch=true: computed 3, reference 2

Twenty-one deviations were found. The defect is in the rounding: the rule says round down, the implementation rounds to the nearest. When a student and an off-branch return combine, the total becomes an odd number and the two roundings diverge.

This approach is also called a pseudo-oracle. Its cost is plain: doing the same work twice. For this reason it is applied only in computation-heavy and high-risk areas. It also has a trap — if the second computation is written by looking at the first, it inherits the same misunderstanding and the two sides stay silent together.

Metamorphic Relation

The second approach never knows the expected value at all. Instead it builds a metamorphic relation that states how the output must change when the input changes in a specific way. If the relation does not hold, there is a defect; if it holds, only that relation has been learned about.

// oracle-metamorphic.mjs — relations built without knowing the expected value
import { totalFee, inputs } from './fee.mjs';

const RELATIONS = {
  'MI1 fee does not decrease as delay increases': () => {
    for (const memberType of ['member', 'student']) {
      for (let day = 1; day <= 20; day += 1) {
        const before = totalFee({ daysLate: day - 1, memberType });
        const after = totalFee({ daysLate: day, memberType });
        if (after < before) return `day=${day} ${memberType}: ${before} -> ${after}`;
      }
    }
    return null;
  },
  'MI2 fee does not exceed 25 units': () => {
    for (const g of inputs()) {
      if (totalFee(g) > 25) return `day=${g.daysLate} ${g.memberType}: ${totalFee(g)}`;
    }
    return null;
  },
  'MI3 twice the student fee does not exceed the member fee': () => {
    for (const g of inputs().filter((x) => x.memberType === 'member')) {
      const member = totalFee(g);
      const student = totalFee({ ...g, memberType: 'student' });
      if (student * 2 > member) return `day=${g.daysLate} offBranch=${g.offBranch}: student ${student}, member ${member}`;
    }
    return null;
  },
};

for (const [name, relation] of Object.entries(RELATIONS)) {
  const violation = relation();
  console.log(`${name}: ${violation === null ? 'holds' : `violated — ${violation}`}`);
}

MI1 fee does not decrease as delay increases: holds
MI2 fee does not exceed 25 units: holds
MI3 twice the student fee does not exceed the member fee: violated — day=0 offBranch=true: student 3, member 5

Two of the three relations held, one was violated, and it showed the same defect — without the expected value being written anywhere. For this reason metamorphic relations are counted as a partial oracle: they can show that a defect exists, but they cannot confirm correctness.

That two relations held is also information. One relation holding says the class of defect that relation defines is absent; all of them holding does not say the program is correct. Because relations hold across the entire input space, they suit use together with generated inputs.

Golden File

The third approach records the expected value. The program’s output today is written to a file, and later runs are compared against that file. This file is called a golden file.

// oracle-golden.mjs — using a recorded output as an oracle
import { writeFileSync, readFileSync } from 'node:fs';
import { totalFee, inputs } from './fee.mjs';

const golden = inputs().map((g) => ({ ...g, fee: totalFee(g) }));
writeFileSync('golden.json', JSON.stringify(golden));
console.log(`golden file: ${golden.length} records written`);

const recorded = JSON.parse(readFileSync('golden.json', 'utf8'));
const unchanged = recorded.filter((k) => totalFee(k) !== k.fee);
console.log(`unchanged version: ${unchanged.length} differences`);

function raisesLimitTo25({ daysLate, memberType, offBranch }) {
  const base = Math.min(Math.max(daysLate - 3, 0) * 2, 25);
  const total = base + (offBranch ? 5 : 0);
  return memberType === 'student' ? Math.round(total / 2) : total;
}
const changed = recorded.filter((k) => raisesLimitTo25(k) !== k.fee);
console.log(`version that raises the limit: ${changed.length} differences`);

const defectiveRecord = recorded.find((k) => k.memberType === 'student' && k.offBranch && k.daysLate === 0);
console.log(`golden file's day=0 student offBranch record: ${defectiveRecord.fee} (correct is 2)`);

golden file: 84 records written
unchanged version: 0 differences
version that raises the limit: 28 differences
golden file's day=0 student offBranch record: 3 (correct is 2)

The golden file caught the version that silently raised the cap in twenty-eight records. This is where it is strong: it detects an unwanted change cheaply and removes the work of writing expected values entirely.

The last line shows its weakness. Because the file was produced from output that already carried the rounding defect, it recorded the defect too. That defect now counts as “expected behavior,” and fixing it lowers the golden file — whoever fixes it silences the test by refreshing the file. A golden file does not find defects; it freezes existing behavior.

For this reason a golden file must be read when it is accepted. A golden file too large to read is an oracle that has never been checked.

Choosing an Oracle

The three approaches do not do the same job, and they are used together.

The specified oracle is used for a small number of high-value test cases: the examples that define the rule itself. The independent second computation comes into play in computation-heavy areas and when the input space is large. Metamorphic relations work where the expected value cannot be known and are most productive together with generated inputs. The golden file catches unwanted change wherever the output is broad and structural.

There is also a human oracle: the person who knows the correct answer. It is the most expensive and slowest oracle, but for some questions it is the only one — a program cannot decide whether a warning message is understandable.

There is one criterion for selection: the oracle must be independent of the program it tests. An oracle derived from the program’s own output is the program confirming itself.

Summary

• A test oracle is the source that decides whether the observed result is correct; without an oracle there is no test, only a run.
• The specified oracle confirms a wrong truth if the specification is wrong, and it cannot be written by hand once the input space grows.
• The independent second computation computes the same rule a different way; in the example it found twenty-one deviations in eighty-four inputs, but if written by looking at the first, it inherits the same misunderstanding.
• A metamorphic relation shows a defect without ever knowing the expected value; it is a partial oracle, and its holding does not confirm correctness.
• A golden file catches unwanted change cheaply, but it freezes the defect present at the moment it was produced as expected behavior.
• The oracle’s one criterion is independence from the program it tests.

Next Step

When an oracle shows a deviation, the work does not end, it begins. The deviation must be recorded, described in a repeatable way, prioritized, fixed, and the fix confirmed. Each of these steps is a state, and only specific transitions between them are valid. The course’s final lesson builds this cycle.