2018–2022 · Completed

DARPA Assured Autonomy

Funded by DARPA, Assured Autonomy program.

Assured Autonomy project overview

Introduction

Intelligent autonomous systems are being increasingly applied to various domains and industries, due to advances in modelling, sensing, algorithm design and other technologies. However, formal safety assurances for these systems has not kept pace with these advances: this is because autonomous systems rely heavily on machine learning technologies, which lack the necessary mathematical framework to provide guarantees on correctness. Without assurances, trust in the safety and operation of any learning-enabled cyber-physical system (LE-CPS) will be limited, hampering their broad deployment.

This project aims to address this challenge by developing new mathematical approaches and tools for the verification of data-driven ML algorithms in these systems to enhance their autonomy and assure they are achieving an acceptable level of safety.

Motivation

Cyber-Physical Systems (CPSs) with learning components are increasingly being deployed in safety-critical applications. However formal verification methodologies only offer limited support for the safety analysis of such systems. The project aims to fill this gap by developing new algorithms and software toolkits for the verification of learning-enabled CPSs (LE-CPSs).

Objectives and current results

To enable the development of verification methods, the project aims at defining semantic models and formal specification languages for LE-CPSs. Our efforts are focussed on two main objectives:

  • the analysis of neural networks in isolation and
  • the analysis of interactions between several learning-enabled components and the environment.

Our group contributed several techniques to verify neural networks via, e.g., Mixed-integer Linear Programming or Symbolic Interval Propagation. Our approaches present state-of-the-art solutions for the verification of both feed-forward and recurrent neural networks.

We extended the techniques above to account for LE-CPSs operating in an environment. The resulting models are amenable to formal verification and we proposed several techniques to verify them against specifications expressed in rich logics such as LTL, CTL or ATL.

More details on our current research can be found in the Software and Publications sections below.

Software

The following tools have been developed within the project:

  • VENUS (VErification of NeUral Systems), a state-of-the-art sound and complete verification toolkit for ReLU-based feed-forward neural networks. It can be used to check reachability and local adversarial robustness properties. VENUS implements a MILP-based verification method and leverages dependency relations between the ReLU nodes to prune the search tree that needs to be considered during branch-and-bound. It additionally implements methods based on symbolic interval propagation and input domain splitting. [paper] [download]

Team members

Principal investigator

Research associates

Collaborators

Previous collaborators

Funding

This research is funded by DARPA under the Assured Autonomy program.

Publications

2022

SAC 2022

Repairing misclassifications in neural networks using limited data

P. Henriksen, F. Leofante, A. Lomuscio

Robust and verifiable machine learningDOI
BibTeX
@inproceedings{DBLP:conf/sac/HenriksenLL22,
  author     = {Patrick Henriksen and Francesco Leofante and Alessio Lomuscio},
  title      = {{Repairing misclassifications in neural networks using limited data}},
  booktitle  = {SAC '22: The 37th ACM/SIGAPP Symposium on Applied Computing, Virtual Event, April 25 - 29, 2022},
  pages      = {1031--1038},
  publisher  = {ACM},
  year       = {2022},
  doi        = {10.1145/3477314.3507059}
}
AAAI 2022

Tight Neural Network Verification via Semidefinite Relaxations and Linear Reformulations

J. Lan, Y. Zheng, A. Lomuscio

Robust and verifiable machine learningDOIPublisher
BibTeX
@inproceedings{DBLP:conf/aaai/Lan0L22,
  author     = {Jianglin Lan and Yang Zheng and Alessio Lomuscio},
  title      = {{Tight Neural Network Verification via Semidefinite Relaxations and Linear Reformulations}},
  booktitle  = {Thirty-Sixth AAAI Conference on Artificial Intelligence, AAAI 2022, Thirty-Fourth Conference on Innovative Applications of Artificial Intelligence, IAAI 2022, The Twelveth Symposium on Educational Advances in Artificial Intelligence, EAAI 2022 Virtual Event, February 22 - March 1, 2022},
  pages      = {7272--7280},
  publisher  = {AAAI Press},
  year       = {2022},
  doi        = {10.1609/AAAI.V36I7.20689}
}
JAAMAS 2022

Formal verification of neural agents in non-deterministic environments

M. E. Akintunde, E. Botoeva, P. Kouvaros, A. Lomuscio

Multi-agent systemsDOIPublisher
BibTeX
@article{DBLP:journals/aamas/AkintundeBKL22,
  author     = {Michael E. Akintunde and Elena Botoeva and Panagiotis Kouvaros and Alessio Lomuscio},
  title      = {{Formal verification of neural agents in non-deterministic environments}},
  journal    = {Auton. Agents Multi Agent Syst.},
  volume     = {36},
  number     = {1},
  pages      = {6},
  year       = {2022},
  doi        = {10.1007/S10458-021-09529-3}
}

2021

FM 2021

Formal Analysis of Neural Network-Based Systems in the Aircraft Domain

P. Kouvaros, T. Kyono, F. Leofante, A. Lomuscio, D. D. Margineantu, D. Osipychev, Y. Zheng

Robust and verifiable machine learningDOIPublisher
BibTeX
@inproceedings{DBLP:conf/fm/KouvarosKLLMOZ21,
  author     = {Panagiotis Kouvaros and Trent Kyono and Francesco Leofante and Alessio Lomuscio and Dragos D. Margineantu and Denis Osipychev and Yang Zheng},
  title      = {{Formal Analysis of Neural Network-Based Systems in the Aircraft Domain}},
  booktitle  = {Formal Methods - 24th International Symposium, FM 2021, Virtual Event, November 20-26, 2021, Proceedings},
  series     = {Lecture Notes in Computer Science},
  volume     = {13047},
  pages      = {730--740},
  publisher  = {Springer},
  year       = {2021},
  doi        = {10.1007/978-3-030-90870-6_41}
}
IJCAI 2021

Towards Scalable Complete Verification of Relu Neural Networks via Dependency-based Branching

P. Kouvaros, A. Lomuscio

Robust and verifiable machine learningDOIPublisher
BibTeX
@inproceedings{DBLP:conf/ijcai/KouvarosL21,
  author     = {Panagiotis Kouvaros and Alessio Lomuscio},
  title      = {{Towards Scalable Complete Verification of Relu Neural Networks via Dependency-based Branching}},
  booktitle  = {Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI 2021, Virtual Event / Montreal, Canada, 19-27 August 2021},
  pages      = {2643--2650},
  publisher  = {ijcai.org},
  year       = {2021},
  doi        = {10.24963/IJCAI.2021/364}
}
IJCAI 2021

Efficient Neural Network Verification via Layer-based Semidefinite Relaxations and Linear Cuts

B. Batten, P. Kouvaros, A. Lomuscio, Y. Zheng

Robust and verifiable machine learningDOIPublisher
BibTeX
@inproceedings{DBLP:conf/ijcai/BattenKLZ21,
  author     = {Ben Batten and Panagiotis Kouvaros and Alessio Lomuscio and Yang Zheng},
  title      = {{Efficient Neural Network Verification via Layer-based Semidefinite Relaxations and Linear Cuts}},
  booktitle  = {Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI 2021, Virtual Event / Montreal, Canada, 19-27 August 2021},
  pages      = {2184--2190},
  publisher  = {ijcai.org},
  year       = {2021},
  doi        = {10.24963/IJCAI.2021/301}
}

2020

ECAI 2020

Efficient Neural Network Verification via Adaptive Refinement and Adversarial Search

P. Henriksen, A. R. Lomuscio

Robust and verifiable machine learningPDFDOI
BibTeX
@inproceedings{DBLP:conf/ecai/HenriksenL20,
  author     = {Patrick Henriksen and Alessio R. Lomuscio},
  title      = {{Efficient Neural Network Verification via Adaptive Refinement and Adversarial Search}},
  booktitle  = {ECAI 2020 - 24th European Conference on Artificial Intelligence, 29 August-8 September 2020, Santiago de Compostela, Spain, August 29 - September 8, 2020 - Including 10th Conference on Prestigious Applications of Artificial Intelligence (PAIS 2020)},
  series     = {Frontiers in Artificial Intelligence and Applications},
  volume     = {325},
  pages      = {2513--2520},
  publisher  = {IOS Press},
  year       = {2020},
  doi        = {10.3233/FAIA200385}
}
AAAI 2020

Efficient Verification of ReLU-Based Neural Networks via Dependency Analysis

E. Botoeva, P. Kouvaros, J. Kronqvist, A. Lomuscio, R. Misener

Robust and verifiable machine learningPDFDOI
BibTeX
@inproceedings{DBLP:conf/aaai/BotoevaKKLM20,
  author     = {Elena Botoeva and Panagiotis Kouvaros and Jan Kronqvist and Alessio Lomuscio and Ruth Misener},
  title      = {{Efficient Verification of ReLU-Based Neural Networks via Dependency Analysis}},
  booktitle  = {The Thirty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2020, The Thirty-Second Innovative Applications of Artificial Intelligence Conference, IAAI 2020, The Tenth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2020, New York, NY, USA, February 7-12, 2020},
  pages      = {3291--3299},
  publisher  = {AAAI Press},
  year       = {2020},
  doi        = {10.1609/AAAI.V34I04.5729}
}
AAMAS 2020

Formal Verification of Neural Agents in Non-deterministic Environments

M. E. Akintunde, E. Botoeva, P. Kouvaros, A. Lomuscio

Multi-agent systemsPDFPublisherVideo
BibTeX
@inproceedings{DBLP:conf/atal/AkintundeBKL20,
  author     = {Michael E. Akintunde and Elena Botoeva and Panagiotis Kouvaros and Alessio Lomuscio},
  title      = {{Formal Verification of Neural Agents in Non-deterministic Environments}},
  booktitle  = {Proceedings of the 19th International Conference on Autonomous Agents and Multiagent Systems, AAMAS '20, Auckland, New Zealand, May 9-13, 2020},
  pages      = {25--33},
  publisher  = {International Foundation for Autonomous Agents and Multiagent Systems},
  year       = {2020},
  url        = {https://dl.acm.org/doi/10.5555/3398761.3398770}
}
KR 2020

Verifying Strategic Abilities of Neural-symbolic Multi-agent Systems

M. E. Akintunde, E. Botoeva, P. Kouvaros, A. Lomuscio

Multi-agent systemsNeurosymbolic systemsPDFDOI
BibTeX
@inproceedings{DBLP:conf/kr/AkintundeBKL20,
  author     = {Michael E. Akintunde and Elena Botoeva and Panagiotis Kouvaros and Alessio Lomuscio},
  title      = {{Verifying Strategic Abilities of Neural-symbolic Multi-agent Systems}},
  booktitle  = {Proceedings of the 17th International Conference on Principles of Knowledge Representation and Reasoning, KR 2020, Rhodes, Greece, September 12-18, 2020},
  pages      = {22--32},
  year       = {2020},
  doi        = {10.24963/KR.2020/3}
}

2019

AAAI 2019

Verification of RNN-Based Neural Agent-Environment Systems

M. E. Akintunde, A. Kevorchian, A. Lomuscio, E. Pirovano

Multi-agent systemsPDFDOI
BibTeX
@inproceedings{DBLP:conf/aaai/AkintundeKLP19,
  author     = {Michael E. Akintunde and Andreea Kevorchian and Alessio Lomuscio and Edoardo Pirovano},
  title      = {{Verification of RNN-Based Neural Agent-Environment Systems}},
  booktitle  = {The Thirty-Third AAAI Conference on Artificial Intelligence, AAAI 2019, The Thirty-First Innovative Applications of Artificial Intelligence Conference, IAAI 2019, The Ninth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2019, Honolulu, Hawaii, USA, January 27 - February 1, 2019},
  pages      = {6006--6013},
  publisher  = {AAAI Press},
  year       = {2019},
  doi        = {10.1609/AAAI.V33I01.33016006}
}

2018

KR 2018

Reachability Analysis for Neural Agent-Environment Systems

M. Akintunde, A. Lomuscio, L. Maganti, E. Pirovano

Multi-agent systemsPDFPublisher
BibTeX
@inproceedings{DBLP:conf/kr/AkitundeLMP18,
  author     = {Michael Akintunde and Alessio Lomuscio and Lalit Maganti and Edoardo Pirovano},
  title      = {{Reachability Analysis for Neural Agent-Environment Systems}},
  booktitle  = {Principles of Knowledge Representation and Reasoning: Proceedings of the Sixteenth International Conference, KR 2018, Tempe, Arizona, 30 October - 2 November 2018},
  pages      = {184--193},
  publisher  = {AAAI Press},
  year       = {2018},
  url        = {https://aaai.org/papers/22-17991-reachability-analysis-for-neural-agent-environment-systems/}
}