On Interaction Effects in Greybox Fuzzing

1. Problem Statement

Greybox fuzzing (e.g., AFL++) is a dominant technique for automated software testing, relying on mutation strategies to generate new test inputs. Current state-of-the-art fuzzers, such as AFL++ and MOPT, operate under a critical assumption: mutators are independent.

• AFL++ uses a fixed probability distribution to select mutators.
• MOPT optimizes the selection probability of each mutator in isolation using genetic algorithms.
• The Gap: Both approaches assume that the probability of a mutator $m_n$ being effective is independent of the previously selected mutator $m_{n-1}$. The authors hypothesize that this assumption is flawed and that interaction effects exist between mutators (i.e., the combination of specific mutator pairs yields significantly more "interesting" inputs—those that increase code coverage—than others).

2. Methodology

The authors propose a three-pronged methodology to investigate and leverage these interaction effects:

A. Empirical Investigation (RQ1)

To validate the existence of interaction effects, the authors:

1. Dataset Collection: Ran AFL++ on 13 target programs (from FuzzBench) with specific modifications:
   • Limited mutator sequence length to $l=2$.
   • Sampled mutators uniformly at random (to ensure balanced data).
   • Tracked the number of interesting inputs generated by every possible pair $\langle i, j \rangle$.
2. Statistical Modeling: Fitted a linear model: $\hat{N}(i, j) = \mu + \alpha_i + \beta_j + \gamma_{ij}$.
   • $\alpha_i$ and $\beta_j$ represent the individual effects of the first and second mutators.
   • $\gamma_{ij}$ represents the interaction effect.
3. Analysis: Performed a two-way ANOVA. Results showed that the interaction term $\gamma_{ij}$ explains a statistically significant proportion of the variance in the number of interesting inputs, confirming that mutator combinations are not independent.

B. Proposed Solution: MuoFuzz

Based on the finding of interaction effects, the authors designed MuoFuzz, a fuzzer that learns and exploits these dependencies.

• Core Concept: Instead of selecting mutators independently, MuoFuzz learns the conditional probability $Pr(m_n = j | m_{n-1} = i)$.
• Two-Phase Architecture:
  1. Training Phase: Runs for a set duration ($T_{train}$, e.g., 1 hour). It uses AFL++ with uniform random sampling to build a matrix $N(i, j)$ counting interesting inputs for every pair. It then converts this into a transition probability matrix.
  2. Guided Mutation Phase: Generates mutator sequences using a Markov Random Walk.
     • Selects the first mutator $m_1$ (experimentally determined to be better as a uniform random selection rather than weighted).
     • Selects subsequent mutators $m_n$ by sampling from the learned distribution $Pr(m_n | m_{n-1})$.
     • Uses an $\epsilon$-greedy Multi-Armed Bandit (MAB) algorithm to dynamically optimize the sequence length $l$.

C. Evaluation Strategy

The authors compared MuoFuzz against:

• AFL++: The baseline with fixed probabilities.
• MOPT: The baseline that optimizes individual mutator probabilities (ignoring interactions).
• Benchmarks: FuzzBench (13 programs for coverage) and MAGMA (8 programs for bug detection).
• Metrics: Code coverage (median and time-to-coverage) and number of unique bugs found.

3. Key Contributions

1. Empirical Evidence of Interaction: Proved via statistical modeling (ANOVA) that the order and combination of mutators significantly impact fuzzing effectiveness, challenging the independence assumption of current strategies.
2. MuoFuzz Implementation: Developed a novel mutation strategy that models mutator selection as a conditional probability problem (similar to bigram language models in NLP).
3. Comprehensive Evaluation: Demonstrated that leveraging interaction effects leads to superior performance in both code coverage and bug discovery compared to state-of-the-art fuzzers.

4. Results

• Code Coverage:
  • MuoFuzz achieved the highest code coverage in 10 out of 13 FuzzBench programs.
  • It statistically significantly outperformed AFL++ in 9/13 programs and MOPT in 8/13 programs.
  • Efficiency: MuoFuzz reached the 24-hour coverage of AFL++ in an average of 15 hours and MOPT in 16.5 hours, demonstrating faster convergence.
• Bug Discovery:
  • In the MAGMA benchmark, MuoFuzz found 4 bugs that AFL++ missed.
  • It found 1 bug that both AFL++ and MOPT missed.
  • It found the same total number of bugs as MOPT but discovered a distinct set of bugs, suggesting it explores different program states.
• Ablation Study:
  • Context Window: Using only the immediate previous mutator ($p=1$) outperformed using two previous mutators ($p=2$), avoiding the "curse of dimensionality" (data sparsity).
  • First Mutator: Uniformly random selection of the first mutator performed better than weighted selection, preserving exploration.
  • Training Time: A 1-hour training phase was optimal; shorter or longer phases yielded suboptimal results.
  • Generalization: Probabilities learned on one program did not generalize well to others, confirming the need for per-program training.

5. Significance and Implications

• Paradigm Shift: The paper challenges the standard "independent mutator" model in greybox fuzzing, suggesting that sequence context is a critical factor in mutation efficiency.
• NLP Inspiration: The approach draws a direct parallel to Bigram Language Models in Natural Language Processing, opening a new avenue for applying advanced sequence modeling (e.g., RNNs, Transformers) to fuzzing.
• Practical Impact: MuoFuzz provides a lightweight, effective upgrade to existing fuzzers (like AFL++) without requiring heavy machine learning infrastructure during the inference phase. It proves that simple statistical learning of mutator pairs can yield significant security benefits.
• Future Work: The authors suggest extending this concept to predict not just the next mutator, but the next mutation location based on previous actions, and exploring more complex sequence models.

In conclusion, MuoFuzz demonstrates that by acknowledging and learning the interaction effects between mutation operators, fuzzers can generate more effective test inputs, leading to higher code coverage and the discovery of previously missed vulnerabilities.