  In high-level Autonomous Driving (AD) systems, behavioral planning is in
charge of making high-level driving decisions such as cruising and stopping,
and thus highly securitycritical. In this work, we perform the first systematic
study of semantic security vulnerabilities specific to overly-conservative AD
behavioral planning behaviors, i.e., those that can cause failed or
significantly-degraded mission performance, which can be critical for AD
services such as robo-taxi/delivery. We call them semantic Denial-of-Service
(DoS) vulnerabilities, which we envision to be most generally exposed in
practical AD systems due to the tendency for conservativeness to avoid safety
incidents. To achieve high practicality and realism, we assume that the
attacker can only introduce seemingly-benign external physical objects to the
driving environment, e.g., off-road dumped cardboard boxes.
  To systematically discover such vulnerabilities, we design PlanFuzz, a novel
dynamic testing approach that addresses various problem-specific design
challenges. Specifically, we propose and identify planning invariants as novel
testing oracles, and design new input generation to systematically enforce
problemspecific constraints for attacker-introduced physical objects. We also
design a novel behavioral planning vulnerability distance metric to effectively
guide the discovery. We evaluate PlanFuzz on 3 planning implementations from
practical open-source AD systems, and find that it can effectively discover 9
previouslyunknown semantic DoS vulnerabilities without false positives. We find
all our new designs necessary, as without each design, statistically
significant performance drops are generally observed. We further perform
exploitation case studies using simulation and real-vehicle traces. We discuss
root causes and potential fixes.
