Evolutionary Grammar-Based Fuzzing

EvoGFuzz stands for evolutionary grammar-based fuzzing. This approach leverages evolutionary optimization techniques to systematically explore the space of a program's potential inputs, with a particular emphasis on identifying inputs that trigger exceptional behavior or crashes. With a user-defined objective, EvoGFuzz adapts and refines the input generation strategy over generations, making it a powerful tool for discovering software defects.

Efficient defect detection hinges on generating inputs that are simultaneously valid and diverse. Using grammars ensures that inputs conform to expected syntax, while probabilistic grammar rules assign probabilities to alternative derivations. By combining evolutionary algorithms with probabilistic grammars, we can steer input generation toward critical code paths or bug-prone features.

1. The Target Program: The Calculator

To illustrate the technique, we examine a target program: calculator. It evaluates arithmetic and trigonometric expressions along with square roots:

import math

def calculator(inp: str) -> float:
    """Evaluate arithmetic, trigonometric, and square root expressions."""
    return eval(
        str(inp), {"sqrt": math.sqrt, "sin": math.sin, "cos": math.cos, "tan": math.tan}
    )

Evaluating standard expressions works as expected:

print(calculator('cos(6 * 3.141)'))  # Output: 0.999993677717667
print(calculator('sqrt(6 * 6)'))      # Output: 6.0

2. Defining an Oracle Function

To detect defects automatically, we define an oracle function that classifies executions into NO_BUG or BUG:

from evogfuzz.oracle import OracleResult

def oracle(inp: str) -> OracleResult:
    try:
        calculator(inp)
    except ValueError:
        return OracleResult.BUG
    return OracleResult.NO_BUG

Testing initial inputs:

initial_inputs = ['sqrt(1)', 'cos(912)', 'tan(4)']
for inp in initial_inputs:
    print(inp.ljust(20), oracle(inp))
# Output:
# sqrt(1)              NO_BUG
# cos(912)             NO_BUG
# tan(4)               NO_BUG

3. Creating the Input Grammar

Next, we provide a context-free grammar defining the valid input structure:

from fuzzingbook.Grammars import Grammar, is_valid_grammar

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

assert is_valid_grammar(CALCGRAMMAR)

4. Fuzzing with EvoGFuzz

We initialize EvoGFuzz with our grammar, oracle, initial seeds, and iteration limit:

from evogfuzz.evogfuzz_class import EvoGFuzz

epp = EvoGFuzz(
    grammar=CALCGRAMMAR,
    oracle=oracle,
    inputs=initial_inputs,
    iterations=20
)

found_exception_inputs = epp.fuzz()
print(f"EvoGFuzz found {len(found_exception_inputs)} bug-triggering inputs!")

Sample defect-triggering inputs discovered:

sqrt(-444744.5717)
sqrt(-41.4)
sqrt(-29.43)
sqrt(-1187573157.4)
sqrt(-9399.56)
sqrt(-52353.22)
sqrt(-836.5)
sqrt(-6.41)
sqrt(-1.3)

EvoGFuzz rapidly learns that generating negative terms inside sqrt(...) causes math domain errors (ValueError), reinforcing the probabilities of those production rules to generate hundreds of diverse failure cases.

5. Custom Fitness Functions

You can guide the evolutionary optimization toward specific behaviors by passing a custom fitness function. For example, to prioritize inputs that explore the cos function:

from evogfuzz.input import Input

def fitness_function_cos(inp: Input) -> float:
    return 1.0 if 'cos' in str(inp) else 0.0

epp = EvoGFuzz(
    grammar=CALCGRAMMAR,
    oracle=oracle,
    inputs=initial_inputs,
    fitness_function=fitness_function_cos,
    iterations=10
)

epp.fuzz()

Conclusion

By combining grammar specifications with evolutionary algorithms, EvoGFuzz moves beyond blind random fuzzing. It dynamically optimizes production probabilities, discovering edge cases that standard random fuzzers struggle to reach.

EvoGFuzz is open source on GitHub: github.com/martineberlein/evogfuzz.