ADGFUZZ: Assignment Dependency-Guided Fuzzing for Robotic Vehicles

ADGFUZZ: Assignment Dependency-Guided Fuzzing for Robotic Vehicles

Speakers: Yuncheng Wang

Conference: NDSS Symposium

YouTube: https://www.youtube.com/watch?v=KF8TbyHD3qo

Overview

Robotic vehicles (RVs) -- UAVs, UGVs, and autonomous platforms -- are cyber-physical systems where software bugs don't just crash programs but can cause mission failure, loss of control, or physical crashes. This talk presents ADGFUZZ, a fuzzing framework that exploits a key observation: 28% of bugs in ArduPilot's 10-year bug history are caused by incorrect assignment statements. By analyzing assignment dependencies to partition the massive input space into focused subspaces, ADGFUZZ discovered 87 unique bugs in ArduPilot (78 previously unknown) and 35 bugs in PX4, including logic errors in waypoint tracking where a copter falsely reports reaching waypoints while drifting in the opposite direction.

The approach uses entropy-based scoring to prioritize input subspaces with higher bug-triggering potential, enabling efficient exploration of the enormous configuration space (thousands of parameters, hundreds of commands, various environmental factors).

Background

▶ Watch: RV security challenges: massive input space and logic bugs (0:00)

Robotic vehicle control software integrates control theory, physics, and embedded systems, translating physical models into code through approximations and auxiliary variables. This translation is error-prone: small mistakes lead to incomplete logic, incorrect assumptions, or unexpected interactions. The input space is massive (thousands of configuration parameters, hundreds of commands, environmental factors), and testing all combinations is infeasible while testing inputs independently misses deep logic bugs.

The motivating example demonstrates a waypoint tracking bug in ArduPilot's copter navigation. The controller uses a virtual reference point that moves along the planned path independently of the copter's actual position. Under strong wind, the copter drifts away from the path, but the virtual reference point continues advancing. Because the controller never verifies the copter's actual position, it falsely reports waypoint reached when the reference point passes the waypoint -- even though the copter may be kilometers away. The bug traces through assignment dependencies: an incorrect lower bound of 0.1 on the advancing speed causes the virtual reference point to always progress, regardless of actual copter displacement.

Key Findings

▶ Watch: Virtual reference point bug: incorrect speed lower bound of 0.1 (4:00)

• 87 unique bugs in ArduPilot including 78 previously unknown, and 35 bugs in PX4
• 28% of ArduPilot bugs over 10 years are directly caused by incorrect assignments, motivating the assignment-dependency-guided approach
• Assignment dependency graphs (ADGs) effectively partition the massive input space into focused, semantically meaningful subspaces
• Entropy-based selection prioritizes input subspaces with higher uncertainty and bug-triggering potential
• Cross-validation on real hardware confirms that bugs found in software-in-the-loop (SITL) simulation reproduce on physical platforms
• Bugs include false waypoint reaching, loss of control under specific environmental conditions, and incorrect mission state transitions
• Results were released with an Ubuntu virtual machine and source code for reproducibility

Technical Deep Dive

▶ Watch: 28% of ArduPilot bugs caused by incorrect assignments (6:00)

ADGFUZZ operates in three stages:

Static Analysis: Assignment statements are analyzed to extract assignment dependency graphs (ADGs) where variables are classified as root (input-derived), semi (intermediate), or leaf (output-affecting) nodes. Edges represent assignment dependencies. Variables within each ADG subgraph are semantically connected, enabling mapping to corresponding system inputs through shared physical semantics (e.g., wp_radius_cm maps to the parameter WP_NAVI_RADIUS).

Matched Input Set (MIS) Construction: ADG variables are mapped to multi-source inputs (configuration parameters, commands, environmental factors) using semantic matching that handles equivalent physical concepts (angle, acceleration, etc.). Each MIS represents a focused input subspace where assignment-related bugs are likely to occur. Shannon entropy measures the semantic information richness of each MIS, with higher entropy indicating higher uncertainty and bug-triggering potential.

Parallel Fuzzing with Entropy-Guided Selection: Three models run in parallel: the simulation model (SITL with predefined missions), the execution model (selecting MIS and generating test cases), and the oracle model (monitoring execution logs for anomalies and dynamically updating entropy scores). MIS selection probability is proportional to entropy, balancing exploitation of promising subspaces with exploration of new ones. When a bug is found, the system switches to a new MIS.

Demo / Proof of Concept

▶ Watch: Results: 87 bugs in ArduPilot, 35 in PX4 (10:00)

ADGFUZZ was evaluated on ArduPilot (copter and plane) and PX4 (copter) using software-in-the-loop simulation with MAVProxy and MAVLink. Each platform was tested continuously for 24 hours. Discovered bugs were cross-validated on real hardware to confirm physical reproducibility.

The waypoint tracking bug demonstrates the practical impact: a copter on a delivery mission could report completing its route while actually drifting off-course, potentially losing the package or flying into restricted airspace.

Defensive Implications

▶ Watch: Q&A: physical constraints and developer response to findings (12:00)

• RV certification: Assignment dependency analysis provides a systematic methodology for security testing as part of RV certification processes, going beyond traditional coverage-based testing
• Safety-critical software verification: The approach generalizes beyond RV controllers to any CPS software where physical models are translated into code
• Input space prioritization: Entropy-based MIS selection provides a principled method for focusing limited testing resources on the most bug-prone input combinations
• Open-source tooling: The released VM and source code enable RV developers to integrate ADGFUZZ into their testing pipelines

Key Takeaways

• 28% of ArduPilot bugs over 10 years are caused by incorrect assignment statements
• Assignment dependency graphs partition the massive RV input space into focused, semantically meaningful subspaces
• 87 bugs found in ArduPilot (78 new) and 35 in PX4, cross-validated on real hardware
• Entropy-based selection prioritizes input subspaces with higher bug-triggering potential
• The approach is generalizable to broader CPS and safety-critical systems beyond robotic vehicles

About the Speaker(s)

Yuncheng Wang (presented by Yinan) is from the University of Chinese Academy of Sciences and the Institute of Information Engineering. The research addresses the intersection of control theory and software security in autonomous systems.