AlhazenML: Explaining Program Behavior

When a program crashes or behaves pathologically, isolating the exact conditions that trigger the bug is often the most time-consuming part of software maintenance. In their foundational work, Kampmann et al. presented an approach to automatically learn associations between program failures and input structure.

Their proposed idea affiliates syntactical input features—such as input length, numerical thresholds, or the presence of particular derivation sequences—with faulty program behavior. Based on these associations, the tool Alhazen automatically generates human-interpretable hypotheses (in the form of decision trees) explaining why failure-inducing inputs cause a defect.

Why Do We Need to Explain Program Behavior?

Consider a motivating example. Suppose we have a program under test: The Calculator. It evaluates arithmetic equations and trigonometric functions, and calculates square roots.

Because the calculator only processes inputs conforming to a structured grammar, we specify its input format with a context-free grammar:

from fuzzingbook.Grammars import Grammar

CALCULATOR_GRAMMAR: Grammar = {
    "<start>": ["<function>(<term>)"],
    "<function>": ["sqrt", "tan", "cos", "sin"],
    "<term>": ["-<value>", "<value>"],
    "<value>": ["<integer>.<integer>", "<integer>"],
    "<integer>": ["<digit><integer>", "<digit>"],
    "<digit>": ["0", "1", "2", "3", "4", "5", "6", "7", "8", "9"]
}
START_SYMBOL = "<start>"

Observing Failures

Now let us evaluate two sample inputs against our calculator:

from alhazenML.calculator import evaluate_samples

samples = ['sqrt(-16)', 'tan(4)']
oracle_results = evaluate_samples(samples)
print(oracle_results)

Output:

{
    ('sqrt(-16)', OracleResult.BUG),
    ('tan(4)', OracleResult.NO_BUG)
}

We observe that sqrt(-16) triggers a bug (in this case, taking the square root of a negative number raises an unhandled ValueError), whereas tan(4) executes without failure.

Manual Refinement vs. Automated Learning

Ordinarily, a developer investigating this behavior would manually create test cases to narrow down the trigger:

guesses = ['cos(-16)', 'tan(-16)', 'sqrt(-100)', 'sqrt(-20.23)']
print(evaluate_samples(guesses))

Output:

{
    ('cos(-16)', OracleResult.NO_BUG),
    ('tan(-16)', OracleResult.NO_BUG),
    ('sqrt(-100)', OracleResult.NO_BUG),  # e.g., if negative integers are masked
    ('sqrt(-20.23)', OracleResult.BUG)
}

Manually guessing input combinations is tedious, incomplete, and fails for complex real-world software.

This is precisely where Alhazen comes in: It automatically generates new inputs, executes the target program, extracts grammatical features from the parse trees, and trains an interpretable machine learning model (such as a decision tree or random forest) that describes the precise boundaries of the failure region.

Looking Forward

By connecting grammar-guided generation with interpretable ML models, automated debugging transforms from passive error reporting into active scientific diagnosis. The Python implementation of Alhazen was later featured in The Debugging Book, providing a foundation for our ongoing work on semantic explanation of software defects.