alhazen-py

This repository contains a complete python implementation of the debugging tool Alhazen, initially proposed by Kampmann et al. [KHZ2020]. With this reimplementation we not only provide a concise and fast version of Alhazen, we also include more machine learning models to explain the circumstances of failing programs.

How to use Alhazen

To illustrate Alhazen’s capabilities, we start with a quick motivating example. First, let us introduce our program under test: The Calculator.

import math

def arith_eval(inp) -> float:
    return eval(
        str(inp), {"sqrt": math.sqrt, "sin": math.sin, "cos": math.cos, "tan": math.tan}
    )

This infamous program accepts arithmetic equations, trigonometric functions and allows us to calculate the square root. To help us determine faulty behavior, i.e., a crash, we implement an evaluation function

from alhazen.oracle import OracleResult

def prop(inp: str) -> bool:
    try:
        arith_eval(inp)
        return OracleResult.NO_BUG
    except ValueError:
        return OracleResult.BUG
    return OracleResult.UNDEF

that takes an input file and returns whether a bug occurred during the evaluation of the mathematical equations (BUG=True, NO_BUG=False). We can now test the calculator with some sample inputs:

inputs = ['cos(10)', 'sqrt(28367)', 'tan(-12)', 'sqrt(-3)']
print([(x, prop(x)) for x in inputs])

The output looks like this:

[('cos(10)', OracleResult.NO_BUG),
 ('sqrt(28367)', OracleResult.NO_BUG),
 ('tan(-12)', OracleResult.NO_BUG),
 ('sqrt(-3)', OracleResult.BUG)]

We see that sqrt(-3) results in the failure of our calculator program. We can now use Alhazen to learn the root causes of the program's failure.

First, we need to define the input format of the calculator with a grammar:

import string

grammar = {
    "<start>": ["<arith_expr>"],
    "<arith_expr>": ["<function>(<number>)"],
    "<function>": ["sqrt", "sin", "cos", "tan"],
    "<number>": ["<maybe_minus><onenine><maybe_digits>"],
    "<maybe_minus>": ["", "-"],
    "<onenine>": [str(num) for num in range(1, 10)],
    "<digit>": list(string.digits),
    "<maybe_digits>": ["", "<digits>"],
    "<digits>": ["<digit>", "<digit><digits>"],
}

Then, we can call Alhazen with the grammar, some sample inputs, and the evaluation function (program under test).

from alhazen import Alhazen

alhazen = Alhazen(
    initial_inputs=inputs,
    grammar=grammar,
    evaluation_function=prop,
)
trees = alhazen.run()

By default, Alhazen will do 10 iterations of its refinement process. Finally, Alhazen returns the learned decision tree that describes the failure-inducing inputs.

For our calculator, the learned decision tree looks something like this:

We see that the failure occurs whenever we use the sqrt(x) function and the number x has a negative sign!

Project Structure

In this repository, you find:

• the reimplementation and source code of Alhazen-py, and
• a complete introduction (jupyter-notebook) on how to use Alhazen-py and how you can add your own Learners and Generators.

Install, Development, Testing, Build

Install

If all external dependencies are available, a simple pip install alhazen-py suffices. We recommend installing alhazen-py inside a virtual environment (virtualenv):

python3.10 -m venv venv
source venv/bin/activate

pip install --upgrade pip
pip install alhazen-py

Now, the alhazen command should be available on the command line within the virtual environment.

Development and Testing

For development, we recommend using alhazen-py inside a virtual environment (virtualenv). By thing the following steps in a standard shell (bash), one can run the Alhazen tests:

git clone https://github.com/martineberlein/alhazen-py.git
cd alhazen-py/

python3.10 -m venv venv
source venv/bin/activate

pip install --upgrade pip

# Run tests
pip install -e .[dev]
python3 -m pytest

Build

alhazen-py is build locally as follows:

git clone https://github.com/martineberlein/alhazen-py.git
cd alhazen-py/

python3.10 -m venv venv
source venv/bin/activate

pip install --upgrade pip
pip install --upgrade build
python3 -m build

Then, you will find the built wheel (*.whl) in the dist/ directory.

Contributors

The initial idea for writing the guide was to explain to our students at Humboldt-Universität Zu Berlin how to use Alhazen to determine the failure circumstances of a program. The original notebooks were a joint project with my colleague Hoang Lam Nguyen from Humboldt-Universität Zu Berlin.