Compositional Verification for Autonomous Systems with Deep Learning Components

Corina S. Pasareanu, Divya Gopinath, Huafeng YuarXiv 2018 · OpenReview

TL;DR

This paper introduces a compositional approach to formally verify autonomous systems that incorporate deep neural networks (DNNs). By leveraging "assume-guarantee" reasoning and defining contracts for individual components, the authors enable scalable verification of complex systems, addressing the inherent unpredictability of DNNs.

What Problem Does This Paper Address?

The increasing prevalence of autonomous systems, from self-driving cars to drones, necessitates strong safety guarantees. However, these systems are often large, complex, and rely on data-driven machine learning components like Deep Neural Networks (DNNs). DNNs, while powerful, are notoriously unpredictable and lack the theoretical foundations for formal assurance, making traditional verification methods insufficient. Existing assurance approaches are often expensive, inadequate, and not designed for advanced autonomy. This paper tackles the challenge of providing formal safety guarantees for these learning-enabled autonomous systems by developing a scalable verification framework.

Methods

The core of the proposed solution is a compositional assume-guarantee verification approach. Instead of verifying the entire complex system at once (which is often intractable), the authors decompose it into smaller, manageable components.

Here's how it works:

  • Assume-Guarantee Contracts: For each component (including DNNs), the authors define "contracts." These contracts specify the component's expected input-output behavior and the assumptions under which its guarantees hold. This allows designers to model and incorporate the behavior of DNNs alongside traditional components.
  • Component-wise Verification: The framework then uses these contracts to decompose the overall system verification into local verifications of individual components. This enables the use of specialized tools for different component types (e.g., model checking for controllers, specific analysis for DNNs).
  • DNN Analysis for Safe Regions: To address the unpredictability of DNNs, the authors propose a technique to automatically discover "safe regions" within the input space where the DNN is likely to behave predictably and robustly to adversarial perturbations. This involves clustering input data with known correct labels to identify dense regions.
  • Targeted Safety: For DNNs, they introduce the concept of "targeted safety," which guarantees that for a specific incorrect label, no input within a safe region will be mapped to that label. This provides a more practical form of assurance than complete robustness.
  • Compositional Reasoning: The contracts derived from the DNN analysis are then used in assume-guarantee rules to reason about the entire system. If the contracts for individual components imply the system-level safety property, then the overall system is considered verified.

Datasets

The paper mentions the use of the MNIST dataset for evaluating their DNN analysis technique. They also discuss experiments on a neural network implementation of the ACAS Xu system, for which they were supplied with a large set of generated inputs and their corresponding verified labels by domain experts.

Key Insights and Ideas

  • Decomposition is Key: The paper strongly advocates for compositional verification as the only scalable way to handle the complexity of modern autonomous systems, especially those with DNNs.
  • Contracts Bridge the Gap: Assume-guarantee contracts are presented as a crucial mechanism for bridging the gap between traditional system components and the opaque nature of DNNs. They allow for formal reasoning about learning-enabled components.
  • Safe Regions for DNN Predictability: Identifying "safe regions" where DNNs exhibit predictable behavior is a pragmatic approach to gaining assurance. This moves beyond verifying individual points to guaranteeing behavior over entire input domains.
  • Targeted Safety is Practical: For safety-critical applications, guaranteeing that a DNN won't produce a specific dangerous output (targeted safety) is often more achievable and useful than guaranteeing complete robustness against any adversarial attack.
  • Integration of Diverse Tools: The compositional approach allows for seamless integration of different verification tools, each suited to the specific characteristics of a component.

Key Results

The paper demonstrates the approach on an autonomous vehicle subsystem (emergency braking system) and the ACAS Xu aircraft collision avoidance system.

For the ACAS Xu case study:

  • They identified 177 regions where the network was either completely safe or safe against specific target labels.
  • They provide an example of a safety guarantee for a specific region, stating that inputs within a certain Manhattan distance from a centroid will be classified as "Clear-of-Conflict" (COC).
  • The analysis also discovered adversarial examples that were validated by domain experts.

Limitations and Future Work

  • Manual Effort in Contract Generation: The authors acknowledge that coming up with suitable assumptions and guarantees for assume-guarantee reasoning can be a difficult manual process. While progress has been made in automating this, it remains a challenge.
  • Scalability of DNN Verification: While the approach aims for scalability, the verification of even simple neural networks is noted as an NP-complete problem. Focusing on clusters helps, but it's still a computationally intensive task.
  • Adaptive Components: The paper touches upon adaptive components (e.g., those using reinforcement learning) and suggests that their verification might need to be done at runtime, with model uncertainty used to trigger fail-safe actions. This is an area for future exploration.
  • Empirical Guarantees for Testing: The authors suggest that for components where formal analysis is not feasible, testing or simulation can be used, yielding empirical guarantees. This highlights a trade-off between formal assurance and practical implementation.
  • Evaluating on Real Platforms: The authors are currently working on evaluating the proposed approach on various simulation and real autonomous platforms, including self-driving cars, autonomous quadcopters, and airplanes, which will provide further validation.

Summary updated

Abstract

As autonomy becomes prevalent in many applications, ranging from recommendation systems to fully autonomous vehicles, there is an increased need to provide safety guarantees for such systems. The problem is difficult, as these are large, complex systems which operate in uncertain environments, requiring data-driven machine-learning components. However, learning techniques such as Deep Neural Networks, widely used today, are inherently unpredictable and lack the theoretical foundations to provide strong assurance guarantees. We present a compositional approach for the scalable, formal verification of autonomous systems that contain Deep Neural Network components. The approach uses assume-guarantee reasoning whereby {\em contracts}, encoding the input-output behavior of individual components, allow the designer to model and incorporate the behavior of the learning-enabled components working side-by-side with the other components. We illustrate the approach on an example taken from the autonomous vehicles domain.
BibTeX
@misc{pasareanu2018compositional,
  author = {Corina S. Pasareanu and Divya Gopinath and Huafeng Yu},
  title = {{Compositional Verification for Autonomous Systems with Deep Learning Components}},
  year = {2018},
  eprint = {1810.08303},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1810.08303},
}
Figure