Natural Adversaries: Fuzzing Autonomous Vehicles with Realistic Roadside Object Placements

This paper introduces TrashFuzz, a black-box fuzzing algorithm that manipulates the realistic placement of common roadside objects to generate adversarial scenarios causing autonomous vehicles to misperceive traffic signals and violate traffic laws, demonstrating significant vulnerabilities in the Apollo system without relying on unnatural adversarial patches.

The Gist

Imagine you are teaching a robot to drive a car. You want to make sure it's safe, so you test it by throwing obstacles in its path. Most researchers test this by putting up weird, glowing, or strangely shaped signs that no human would ever see in real life. It's like testing a robot chef by throwing a glowing, neon-colored tomato at them. If the robot gets confused, sure, you found a bug, but that's not a realistic problem.

This paper introduces a new way to test self-driving cars called TRASHFUZZ. Instead of using weird, fake objects, the researchers ask: "What if we just move the normal, boring stuff we see on every street—like trash cans, benches, and trees—to slightly different spots? Could that confuse the robot?"

Here is the breakdown of their work using some everyday analogies:

1. The Problem: The Robot vs. The Real World

Self-driving cars (Autonomous Vehicles or AVs) rely on cameras and sensors to "see" the road. They are trained to follow rules, just like human drivers. However, the rules for where to put trash cans, trees, and signs were written for humans, not robots.

• The Analogy: Imagine a human driver sees a trash can on the sidewalk and thinks, "That's just a bin." But a robot might look at that same bin and think, "Is that a pedestrian? Is that a car? Is that a giant rock?"
• The Issue: Previous tests used "adversarial patches" (like putting a sticker on a stop sign to make the robot think it's a speed limit sign). But in the real world, nobody puts stickers on stop signs. We need to know if normal things can break the robot.

2. The Solution: TRASHFUZZ (The "Trash Can Tester")

The researchers built a tool called TRASHFUZZ. Think of it as a very picky, super-fast robot chef who is trying to break a new recipe.

• The Rules: The tool has a strict rulebook (based on real city laws) that says, "You can move the trash can, but you can't put it in the middle of the road, and you can't put it on top of a tree." It must look like a normal street.
• The Method: The tool uses a "Greedy Search." Imagine you are trying to find the perfect spot to trip a robot dog. You don't just throw a rock randomly. You move the rock an inch to the left. Did the dog stumble? Good. Now move it an inch to the right. Did it stumble more? Keep moving it that way.
• The Goal: The tool moves normal objects (bins, benches, trees) around, checking if the car starts to make illegal moves, like running a red light or stopping in the middle of the road for no reason.

3. The Experiment: Breaking the Robot

They tested this on Apollo, a famous self-driving car system, using a video game simulator (LGSVL) that looks like the real world.

• The Result: They found that by simply arranging normal trash cans and benches in specific, legal ways, they could trick the car into breaking 15 out of 24 traffic laws they tested.
• The Scary Part: In one case, they arranged a few innocent-looking trash cans near a traffic light. The car got so confused by the clutter that it thought a Red Light was Green. It almost drove right into traffic!
• The "Overload" Analogy: Imagine you are trying to listen to a song, but someone starts whispering 50 different things in your ear at once. You get overwhelmed and stop listening to the music. That's what happened to the car's "brain." The trash cans were so confusing that the car's brain stopped working correctly.

4. Why This Matters

This paper proves that we don't need evil hackers with glowing stickers to break self-driving cars. We just need to look at how we design our streets.

• The Takeaway: The rules for where we put trash cans and trees were written for human eyes. They might be perfect for us, but they are a nightmare for robots.
• The Fix: We might need to change city planning. Maybe trash cans need to be a specific shape or color so robots don't get confused. Or maybe we need to test cars with "real world" messiness, not just perfect, clean test tracks.

Summary

TRASHFUZZ is like a "stress test" for self-driving cars using only the boring, everyday objects we see every day. It showed that if we just move a few trash cans around legally, we can make a self-driving car run a red light or stop in the middle of the road. This tells us that to make self-driving cars safe, we need to design our cities with robots in mind, not just humans.

Technical Summary

Here is a detailed technical summary of the paper "Natural Adversaries: Fuzzing Autonomous Vehicles with Realistic Roadside Object Placements."

1. Problem Statement

Autonomous Vehicles (AVs) rely on perception systems to interpret their environment. While existing adversarial testing focuses on conspicuous, unnatural objects (e.g., adversarial patches on traffic cones or billboards) or white-box attacks that manipulate agent behaviors, these scenarios often lack realism and practical applicability.

The authors identify a critical gap: Can AV perception be deceived by "natural" roadside objects (trash bins, benches, trees, hydrants) that strictly adhere to government design guidelines and appear benign to human drivers? Furthermore, can such natural misperceptions escalate into serious safety violations, such as traffic law infractions or collisions? Current testing pipelines often fail to account for these subtle, guideline-compliant anomalies.

2. Methodology: TRASHFUZZ

The authors propose TRASHFUZZ, a black-box fuzzing framework designed to systematically generate realistic adversarial scenarios by manipulating the placement of common roadside objects.

A. Natural Scenario Generation (Constraint Satisfaction)

To ensure realism, TRASHFUZZ does not place objects arbitrarily. Instead, it enforces a set of 12 formalized rules derived from real-world regulatory documents (e.g., Singapore's Code of Practice for Works on Public Streets and Guidelines on Greenery Provision).

• Rules include: Minimum distances between objects and roads/footpaths, height-based distance constraints for trees near infrastructure, and orientation rules for trash bins.
• Implementation: These rules are translated into mathematical formulas (using distance functions like dis(obj, road)) that act as hard constraints during scenario generation. Any mutation violating these rules is discarded.

B. Attack Vector and Object Library

• Objects: The system utilizes a library of standard 3D assets from the Unity Asset Store (bins, benches, trees, hydrants) rather than custom adversarial patches.
• Encoding: Scenarios are encoded as vectors containing the position (forward, right), rotation, and type of $n$ adversarial objects.

C. Greedy Gradient-Guided Black-Box Search

Since the attack is black-box (no access to internal DNN weights), TRASHFUZZ employs a specialized search algorithm:

1. Objective Function: The goal is to minimize the robustness of the AV's behavior against a set of traffic law specifications defined in Signal Temporal Logic (STL).
   • The STL formulas are decomposed into a set of "violation goals" ($\Theta$).
   • The robustness metric $\rho(\phi, \pi)$ quantifies how close a trace $\pi$ is to violating a specification $\phi$. A value $\le 0$ indicates a violation.
2. Gradient Calculation: The algorithm estimates a "gradient" by comparing the robustness of an initial scenario against mutated scenarios:
   $$G(\lambda, \lambda', \phi) = \frac{\rho(\phi, \pi) - \rho(\phi, \pi')}{E(\lambda) - E(\lambda')}$$
   This gradient indicates how much a specific object placement change influences the likelihood of a violation.
3. Search Strategy: The algorithm is greedy. It selects the mutation with the highest absolute gradient value (indicating the most significant move toward a violation) as the "seed" for the next iteration. This allows it to navigate the vast, constrained search space efficiently without requiring white-box knowledge.

3. Key Contributions

1. Natural Adversarial Framework: Introduction of TRASHFUZZ, the first fuzzing approach that generates adversarial scenarios using only guideline-compliant, patch-free roadside objects.
2. Formalization of Realism: The translation of complex, natural-language road design guidelines into executable mathematical constraints, ensuring all generated scenarios are legally and physically plausible.
3. Black-Box Optimization: A novel gradient-guided search algorithm tailored for black-box AV testing that operates within a highly constrained search space (natural scenarios) to maximize traffic law violation coverage.
4. Comprehensive Evaluation: Implementation and testing on the Baidu Apollo ADS (v7.0) using the LGSVL simulator, alongside preliminary validation on Autoware.

4. Experimental Results

The authors evaluated TRASHFUZZ against the Baidu Apollo system across 24 testable Chinese traffic laws.

• Violation Coverage: TRASHFUZZ successfully induced violations in 15 out of 24 traffic laws.
  • It covered all violations found by the baseline tool LawBreaker (which mutates agent behaviors).
  • It discovered one additional violation (Sub-law 7 of Article 51 regarding right-of-way) that LawBreaker missed, demonstrating the unique threat posed by static object placement.
• Types of Failures:
  • Misclassification/Segmentation: Trash bins were misidentified as pedestrians or bicycles, causing the AV to hesitate or stop unnecessarily.
  • Perception Overload: Specific arrangements of bins near traffic lights caused the perception system to fail, leading to misinterpreting a red light as green (or vice versa), resulting in dangerous aggressive driving or indefinite stopping.
• Efficiency: TRASHFUZZ covered more violation goals than the genetic-algorithm-based LawBreaker within the same query budget (620 queries), proving the efficacy of the gradient-guided approach in constrained spaces.
• Generalizability: Preliminary tests on Autoware (using CARLA) showed similar misclassification patterns, suggesting the vulnerability is systemic across different ADS stacks.

5. Significance and Implications

• Safety Criticality: The study proves that AVs are vulnerable to "natural" attacks. An attacker does not need specialized equipment or white-box knowledge; simply rearranging trash bins or benches according to standard guidelines can cause critical failures.
• Regulatory Gap: Current roadside design guidelines are optimized for human drivers, not AV perception systems. The paper suggests these guidelines may need revision (e.g., standardizing bin shapes or colors) to prevent perception overload.
• Testing Paradigm Shift: The work argues that AV safety testing must evolve beyond testing for collisions and agent behaviors to include object-placement anomalies that exploit perception bottlenecks.
• Practicality: Unlike previous adversarial attacks requiring visible patches or white-box access, TRASHFUZZ demonstrates a realistic, low-cost, and high-impact threat vector that is feasible to execute in the real world.