DEV Community

Krishnasai Rollamadugu
Krishnasai Rollamadugu

Posted on

The oracle problem: testing's oldest unsolved question, and why AI just made it urgent

#testing #ai #computerscience #qa

Here's a question that sounds trivial and isn't: when your program produces an output, how do you know it's the right one?

That's the test oracle problem, and it's one of the oldest open problems in software testing (the definitive survey is Barr, Harman, McMinn, Shahbaz & Yoo, IEEE TSE 2015). Every test you've ever written quietly answered it somehow — and AI testing tools are now answering it for you, which is exactly why it's worth understanding.

What an "oracle" actually is

An oracle is the mechanism that decides pass or fail. When you write:

assert add(2, 3) == 5
Enter fullscreen mode Exit fullscreen mode

the == 5 is your oracle. You, the human, knew the right answer and hard-coded it. Easy.

Now scale that up. What's the correct output of a route planner for a 10,000-node graph? A tax calculation across 40 interacting rules? An ML model's ranking? A PDF renderer? You often cannot just write down the expected answer. That's the oracle problem: the hard part of testing isn't running the program, it's knowing what correct looks like.

How we actually cope (the oracle taxonomy)

We rarely have a perfect oracle, so we use partial ones:

  • Specified oracle — a spec or reference implementation says the exact answer. Strongest, rarest.
  • Derived oracle — infer correctness from other artifacts: a previous version (regression), documentation, or a slower-but-trusted implementation.
  • Metamorphic oracle — when you can't check one output, check a relation between outputs. You may not know sin(x), but you know sin(x) == sin(x + 2π). Hugely useful for scientific code, ML, and anything without a ground truth.
  • Implicit oracle — the "obvious" failures anyone can detect without a spec: crashes, hangs, memory corruption. Cheap but weak — "it didn't crash" is a very low bar.
  • Human oracle — a person eyeballs it. Expensive, unscalable, inconsistent.

Most real suites are a pile of implicit + specified oracles, which is why they catch crashes and the handful of cases someone thought to assert — and miss the subtle wrong-but-plausible outputs.

Why AI makes this urgent

Two shifts just collided with the oracle problem:

  1. AI writes the oracle. When an LLM generates your assertions, it is deciding what "correct" means — and models love weak, behaviour-echoing assertions (type checks, "no exception", loose ranges) that look like tests but barely constrain the output. A green suite full of weak oracles is the oracle problem wearing a disguise.
  2. AI is the oracle. "LLM-as-judge" makes the model itself the pass/fail mechanism. That's an implicit-ish oracle with opinions — convenient, scalable, and unaccountable unless you measure it. (I've measured one: a local LLM judge waved through ~1 in 4 genuinely wrong outputs while ~100% confident.)

In both cases we've quietly handed the oldest hard problem in testing to a system that's fluent, fast, and frequently wrong — without noticing we did it.

The practical takeaway

  • Name your oracle. For any important test, ask: what decides correct here, and how strong is it? "It returns a string" is not an oracle; it's a vibe.
  • Reach for metamorphic relations when there's no ground truth — they're underused and powerful.
  • If an AI is your oracle, treat it as an oracle under test: check it against real ground truth, measure how often it's wrong, and don't trust its confidence.

The oracle problem never went away. We just built tools that paper over it more convincingly. Knowing it's there is most of the battle.

How do you solve the oracle problem on your hardest-to-verify code? Metamorphic testing? A reference implementation? I'd love to hear the approaches.

I'm Krishnasai Rollamadugu — a test automation architect researching trust and measurement in AI-driven software testing.

Top comments (0)