Dance of the ADS: Orchestrating Failures through Historically-Informed Scenario Fuzzing

This paper introduces ScenarioFuzz, a novel scenario-based fuzzing methodology that leverages historical test data, map networks, and graph neural networks to autonomously generate and optimize high-risk scenarios, significantly reducing testing time while uncovering numerous safety-critical bugs in autonomous driving systems.

The Gist

Imagine you are a director preparing a play for a very talented, but slightly nervous, lead actor: the Autonomous Driving System (ADS). Your goal is to test this actor to see if they can handle any situation without crashing the stage.

The problem? You can't just guess what scenes to write. If you throw random objects at the actor, they might just stand there confused, or the scene might be so unrealistic that the actor ignores it. You need a way to create thousands of "scripts" (scenarios) that are tricky enough to reveal the actor's weaknesses, but realistic enough to matter.

This paper introduces ScenarioFuzz, a new method that acts like a choreographer who knows the history of the theater. Instead of writing scripts from scratch or guessing, it uses the "stage map" to find the best places for trouble to happen, learns from past mistakes, and creates a "dance" of failures to find bugs.

Here is how it works, broken down into simple steps:

1. The Map is the Script (No More Guessing)

Usually, testers pick random spots on a map to start a test. It's like telling an actor, "Start dancing anywhere in the city." This is inefficient and often leads to boring or impossible scenes.

ScenarioFuzz is smarter. It uses a technique called "Map Crawling."

• The Analogy: Imagine a detective walking through a city map, not to get lost, but to find every single intersection, every traffic light, and every possible path a car could take.
• The Result: Instead of guessing, the system builds a massive library of "seed" scenarios. These are the starting points for the test, guaranteed to be on real roads with real traffic lights. It's like having a library of every possible stage setting before the play even begins.

2. The "Mutation" Dance (Making Things Weird)

Once we have a good starting scene, we need to make it tricky. This is where Mutation comes in.

• The Analogy: Think of a scene as a recipe. The "Mutation" process is like a chef who keeps tweaking the recipe to see if the dish breaks.
  • Change the weather: Suddenly, it's pouring rain or foggy.
  • Change the actors: A pedestrian appears out of nowhere, or a truck changes color.
  • Change the path: The car has to take a weird turn or stop suddenly.
• The Strategy: The system uses two types of changes:
  1. Random: Throwing in wild, unpredictable changes (like adding a dragon to the play).
  2. Neighbor: Making small, subtle tweaks to a scene that already caused a problem (like making the rain slightly heavier). This helps the system dig deeper into why a crash happened.

3. The "Crystal Ball" (The AI Filter)

Here is the biggest time-saver. If you generate 1,000 weird scenes, 900 of them might be boring and safe. Running all of them in a simulator takes hours.

• The Analogy: Imagine you have a Crystal Ball (an AI model) that looks at a script and says, "This scene is boring, skip it," or "This scene looks dangerous, run it immediately!"
• How it works: The system uses a Graph Neural Network (GNN). It looks at the "shape" of the scenario (where the cars are, where the lights are) and predicts: "Based on what we learned from past tests, this specific combination of rain + pedestrian + red light is 90% likely to cause a crash."
• The Benefit: It filters out the boring stuff and only runs the "high-risk" scenes. This saves massive amounts of time.

4. The "Replay" and "Categorization"

When the system finally finds a bug (a crash, a red-light run, or the car getting stuck), it doesn't just say "Error." It saves the whole movie.

• The Analogy: It's like a sports analyst reviewing game footage. The system takes all the crashes it found and groups them into 54 different categories (e.g., "The car didn't see the child," "The car got confused by the red truck," "The car froze at the intersection").
• The Outcome: The researchers found 58 distinct bugs in six different self-driving systems. They found things like:
  • The car's "eyes" (sensors) couldn't see low-lying objects like a child lying on the ground.
  • The car got confused by reflections on wet roads.
  • The car didn't know how to handle a pedestrian crossing aggressively.

Why This Matters

Before this, testing self-driving cars was like trying to find a needle in a haystack by throwing darts blindfolded.

• Old Way: Randomly placing cars and hoping for a crash. (Slow, inefficient, misses many bugs).
• ScenarioFuzz: Uses the map to find the "hot spots," uses AI to predict where the trouble will be, and learns from every mistake to get better at finding the next one.

The Bottom Line:
This paper presents a smarter, faster way to break self-driving cars (in a safe, simulated environment) so they can be fixed before they hit the real road. It reduced testing time by 60% and found double the number of errors compared to previous methods. It's the difference between a chaotic jam session and a perfectly orchestrated dance of failure designed to make the system safer.

Technical Summary

Here is a detailed technical summary of the paper "Dance of the ADS: Orchestrating Failures through Historically-Informed Scenario Fuzzing."

1. Problem Statement

As Autonomous Driving Systems (ADS) evolve toward higher levels of autonomy (Level 3–5), their safety verification becomes increasingly complex due to the probabilistic nature of deep learning, vast parameter spaces, and diverse environmental interactions.

• Limitations of Current Methods: Existing scenario-based testing often relies on predefined scenario libraries (scripts) derived from accident data or traffic videos. These are labor-intensive to construct, limited in scope, and often fail to cover edge cases not present in historical data.
• Limitations of Random Fuzzing: Methods that generate scenarios purely randomly (e.g., Drivefuzz) suffer from:
  • Inefficiency: Randomly placing vehicles and pedestrians often results in unrealistic or physically impossible scenarios, wasting computational resources.
  • Lack of Context: Random generation ignores road topology, traffic rules, and logical path constraints, leading to low discovery rates of meaningful errors.
• The Gap: There is a need for a fuzzing methodology that does not require predefined starting scenarios but still leverages the structural logic of the road network to generate realistic, high-risk test cases efficiently.

2. Methodology: ScenarioFuzz

The authors propose ScenarioFuzz, a framework that orchestrates failure discovery by combining map-based seed generation with historical data-driven filtering. The workflow consists of four main stages:

A. Corpus Construction via Map Crawling

Instead of starting with random points, the system extracts a Scenario Seed Corpus from map road networks (e.g., OPENDRIVE files in CARLA).

• Topological Graph Construction: The system parses map data to build a topological graph of waypoints.
• Seed Extraction: It identifies critical nodes (e.g., near traffic lights, intersections) and clusters unused nodes to create a library of valid starting positions, paths, and road types.
• Result: This creates a "foundation" of logically sound scenarios (valid paths, compliant traffic infrastructure) without needing manual scriptwriting.

B. Two-Stage Mutation Strategy

The system mutates the selected seeds using specialized mutators that cover all scenario layers (Road, Infrastructure, Objects, Weather):

1. Mission Mutator: Alters the ego vehicle's start/end points and driving direction.
2. Object Mutator: Adds/changes pedestrians and vehicles (26 types), modifying appearance, motion states (immobile, linear, maneuver, autopilot), and interactions.
3. Weather Mutator: Adjusts 8 parameters (rain, fog, sun angle, etc.) to test perception robustness.
4. Puddle Mutator: Adds ground friction variations to test control stability.

• Strategy:
  • Round 1 (Random): Broad exploration of the input space.
  • Round 2+ (Random Neighbor): Focused exploration around the "best" seeds found in the previous round (based on driving scores), balancing global coverage with local refinement.

C. Historically-Informed Seed Filtering (The "Choreographer")

To avoid wasting resources on low-risk scenarios, the system employs a Scenario Evaluation Model (SEM):

• Graph Neural Network (GNN): Mutated seeds are converted into graph data where nodes represent waypoints/objects and edges represent paths.
• Training: The GNN is trained on historical test data to predict the probability of a seed causing an error (collision, red-light run, etc.).
• Filtering: Only seeds with a high predicted risk score (confidence > 0.5) are selected for simulation execution. This model improves over time as more test data is collected.

D. Execution and Clustering

• Misbehavior Detection: The system monitors for crashes, red-light violations, speeding, lane invasion, and stagnation.
• Self-Supervised Clustering: Upon finding errors, the system uses a self-supervised method to cluster collision trajectories. This groups similar failure modes into 54 distinct high-risk scenario categories, aiding in the analysis of systemic bugs.

3. Key Contributions

1. ScenarioFuzz Framework: A novel fuzzing approach that generates error scenarios without predefined scripts, leveraging map topology to ensure logical consistency.
2. Map-Crawling Corpus: A method to automatically extract a seed corpus from road networks, eliminating the need for manual scenario definition and providing realistic boundaries for fuzzing.
3. GNN-Based Seed Filtering: A historical-data-driven model that predicts high-risk seeds, significantly reducing the computational cost of simulation.
4. Self-Supervised Clustering: A technique to categorize discovered collisions into 54 high-risk patterns, providing actionable insights for system improvement.

4. Experimental Results

The authors evaluated ScenarioFuzz against Drivefuzz (random generation) and other baselines (AV-Fuzzer, SAMOTA) across six ADS systems (Autoware, LAV, Transfuser, NEAT, Basic Agent, Behavior Agent).

• Efficiency Gains:
  • Time Cost: Reduced average execution time by 60.3% compared to Drivefuzz.
  • Discovery Rate: Increased the number of error scenarios discovered per unit of time by 103%.
• Model Performance:
  • The SEM (GNN) showed superior filtering capability compared to Radial Basis Function Networks (RBFN) used in other tools, with a Pearson correlation coefficient of 0.2965 vs. 0.0578.
  • The model's accuracy improved as historical data increased (from 1k to 3k samples).
• Bug Discovery:
  • Successfully uncovered 58 unique bugs across the six tested systems.
  • Identified 54 high-risk scenario categories prone to collisions.
• Code Coverage: ScenarioFuzz achieved higher code coverage in planning and control modules compared to Drivefuzz, as it generated more diverse and realistic interaction patterns.
• Specific Findings:
  • Autoware: Failed to detect low-lying objects (children/pedestrians lying down) and had issues with traffic light recognition in simulation.
  • End-to-End Systems (Transfuser/NEAT): Vulnerable to specific colors (red objects) and lighting conditions (night/multiple objects).
  • Planning: Most systems lacked flexible local planning for lateral traffic at intersections, leading to either aggressive right-of-way assumptions or excessive conservatism (stagnation).

5. Significance

• Paradigm Shift: Moves ADS testing away from "script-based" verification toward "data-driven, topology-aware" fuzzing.
• Scalability: By automating the seed generation and filtering process, the method makes large-scale safety verification feasible without the prohibitive cost of manual scenario engineering.
• Safety Impact: The discovery of 58 bugs and the categorization of 54 failure modes highlight critical, previously unknown vulnerabilities in both modular and end-to-end ADS architectures, particularly regarding perception in adverse conditions and planning in complex intersections.
• Reproducibility: The framework is integrated with CARLA and the Leaderboard, offering a standardized way to stress-test future autonomous systems.

In summary, ScenarioFuzz acts as a "choreographer" that uses the "history" of road networks and past test failures to orchestrate new, highly probable failure scenarios, effectively exposing the weaknesses of autonomous driving systems before they are deployed on real roads.