More Web Proxy on the site http://driver.im/

research-article

Open access

Testing Automated Driving Systems by Breaking Many Laws Efficiently

Authors:

Xiaodong Zhang,

Zijiang YangAuthors Info & Claims

ISSTA 2023: Proceedings of the 32nd ACM SIGSOFT International Symposium on Software Testing and Analysis

Pages 942 - 953

https://doi.org/10.1145/3597926.3598108

Published: 13 July 2023 Publication History

Abstract

An automated driving system (ADS), as the brain of an autonomous vehicle (AV), should be tested thoroughly ahead of deployment. ADS must satisfy a complex set of rules to ensure road safety, e.g., the existing traffic laws and possibly future laws that are dedicated to AVs. To comprehensively test an ADS, we would like to systematically discover diverse scenarios in which certain traffic law is violated. The challenge is that (1) there are many traffic laws (e.g., 13 testable articles in Chinese traffic laws and 16 testable articles in Singapore traffic laws, with 81 and 43 violation situations respectively); and (2) many of traffic laws are only relevant in complicated specific scenarios.

Existing approaches to testing ADS either focus on simple oracles such as no-collision or have limited capacity in generating diverse law-violating scenarios. In this work, we propose ABLE, a new ADS testing method inspired by the success of GFlowNet, which Aims to Break many Laws Efficiently by generating diverse scenarios. Different from vanilla GFlowNet, ABLE drives the testing process with dynamically updated testing objectives (based on a robustness semantics of signal temporal logic) as well as active learning, so as to effectively explore the vast search space. We evaluate ABLE based on Apollo and LGSVL, and the results show that ABLE outperforms the state-of-the-art by violating 17% and 25% more laws when testing Apollo 6.0 and Apollo 7.0, most of which are hard-to-violate laws, respectively.

References

[1]

Afsoon Afzal, Claire Le Goues, and Christopher Steven Timperley. 2021. Mithra: Anomaly Detection as an Oracle for Cyberphysical Systems. IEEE Transactions on Software Engineering, 1–1.

[2]

Matthias Althoff and Sebastian Lutz. 2018. Automatic generation of safety-critical test scenarios for collision avoidance of road vehicles. In 2018 IEEE Intelligent Vehicles Symposium (IV). 1326–1333.

Digital Library

[3]

Christof Angermueller, David Dohan, David Belanger, Ramya Deshpande, Kevin Murphy, and Lucy Colwell. 2019. Model-based reinforcement learning for biological sequence design. In International conference on learning representations.

[4]

Anonymous. 2023. Lawbreaker. https://lawbreaker2022.github.io/ [Online; accessed Jan 2023]

[5]

Anonymous. 2023. Source code and experiment data. https://anonymous.4open.science/r/ISSTA2023DATA-0C8E

[6]

AVUnit. 2021. AVUnit. https://avunit.readthedocs.io/en/latest/ [Online; accessed Apr 2022]

[7]

AVUnit. 2021. Specification-based Autonomous Vehicle Testing. https://avunit2021.github.io/ [Online; accessed Agu 2022]

[8]

Philip Bachman and Doina Precup. 2015. Data generation as sequential decision making. Advances in Neural Information Processing Systems, 28 (2015).

[9]

Baidu. 2019. APOLLO 6.0. https://github.com/ApolloAuto/apollo/releases/tag/\\v6.0.0 [Online; accessed Aug 2022]

[10]

Baidu. 2021. APOLLO 7.0. https://github.com/ApolloAuto/apollo/releases/tag/\\v7.0.0 [Online; accessed Aug 2022]

[11]

Emmanuel Bengio, Moksh Jain, Maksym Korablyov, Doina Precup, and Yoshua Bengio. 2021. Flow Network based Generative Models for Non-Iterative Diverse Candidate Generation. Advances in Neural Information Processing Systems, 34 (2021).

[12]

Zihang Dai, Amjad Almahairi, Philip Bachman, Eduard Hovy, and Aaron Courville. 2017. Calibrating energy-based generative adversarial networks. arXiv preprint arXiv:1702.01691.

[13]

Steve Dent. 2022. Tesla recalls Full Self Driving feature that lets cars roll through stop signs. https://techcrunch.com/2022/02/01/tesla-recalls-full-self-driving-feature-that-lets-cars-roll-through-stop-signs/

[14]

Jyotirmoy V Deshmukh, Alexandre Donzé, Shromona Ghosh, Xiaoqing Jin, Garvit Juniwal, and Sanjit A Seshia. 2017. Robust online monitoring of signal temporal logic. Formal Methods in System Design, 51, 1 (2017), 5–30.

Digital Library

[15]

Alexey Dosovitskiy, German Ros, Felipe Codevilla, Antonio Lopez, and Vladlen Koltun. 2017. CARLA: An Open Urban Driving Simulator. In Proceedings of the 1st Annual Conference on Robot Learning, Sergey Levine, Vincent Vanhoucke, and Ken Goldberg (Eds.) (Proceedings of Machine Learning Research, Vol. 78). PMLR, 1–16.

[16]

R Elvik, A Høye, T Vaa, and M Sørensen. 2009. The Handbook of Road Safety Measures, Second 350 Edition.

[17]

Shuo Feng, Xintao Yan, Haowei Sun, Yiheng Feng, and Henry X Liu. 2021. Intelligent driving intelligence test for autonomous vehicles with naturalistic and adversarial environment. Nature communications, 12, 1 (2021), 1–14.

[18]

Daniel J. Fremont, Tommaso Dreossi, Shromona Ghosh, Xiangyu Yue, Alberto L. Sangiovanni-Vincentelli, and Sanjit A. Seshia. 2019. Scenic: A Language for Scenario Specification and Scene Generation. In Proceedings of the 40th ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI 2019). Association for Computing Machinery, New York, NY, USA. 63–78. isbn:9781450367127

Digital Library

[19]

Bernd Gassmann, Fabian Oboril, Cornelius Buerkle, Shuang Liu, Shoumeng Yan, Maria Soledad Elli, Ignacio Alvarez, Naveen Aerrabotu, Suhel Jaber, and Peter van Beek. 2019. Towards standardization of AV safety: C++ library for responsibility sensitive safety. In 2019 IEEE Intelligent Vehicles Symposium (IV). 2265–2271.

Digital Library

[20]

Sai Krishna Gottipati, Boris Sattarov, Sufeng Niu, Yashaswi Pathak, Haoran Wei, Shengchao Liu, Simon Blackburn, Karam Thomas, Connor Coley, and Jian Tang. 2020. Learning to navigate the synthetically accessible chemical space using reinforcement learning. In International Conference on Machine Learning. 3668–3679.

[21]

Chinese Government. 2021. Regulations for the Implementation of the Road Traffic Safety Law of the People’s Republic of China. http://www.gov.cn/gongbao/content/2004/content_62772.htm [Online; accessed Mar 2022]

[22]

Will Grathwohl, Kevin Swersky, Milad Hashemi, David Duvenaud, and Chris Maddison. 2021. Oops i took a gradient: Scalable sampling for discrete distributions. In International Conference on Machine Learning. 3831–3841.

[23]

Fitash Ul Haq, Donghwan Shin, and Lionel Briand. 2022. Efficient online testing for DNN-enabled systems using surrogate-assisted and many-objective optimization. In Proceedings of the 44th International Conference on Software Engineering. 811–822.

Digital Library

[24]

Mohammad Hekmatnejad, Shakiba Yaghoubi, Adel Dokhanchi, Heni Ben Amor, Aviral Shrivastava, Lina Karam, and Georgios Fainekos. 2019. Encoding and Monitoring Responsibility Sensitive Safety Rules for Automated Vehicles in Signal Temporal Logic. In Proceedings of the 17th ACM-IEEE International Conference on Formal Methods and Models for System Design (MEMOCODE ’19). Association for Computing Machinery, New York, NY, USA. Article 6, 11 pages. isbn:9781450369978 https://doi.org/10.1145/3359986.3361203

Digital Library

[25]

Hardi Hungar, Frank Köster, and Jens Mazzega. 2017. Test specifications for highly automated driving functions: Highway pilot. Presentation at Vehicle Test & Development Symposium.

[26]

Moksh Jain, Emmanuel Bengio, Alex-Hernandez Garcia, Jarrid Rector-Brooks, Bonaventure FP Dossou, Chanakya Ekbote, Jie Fu, Tianyu Zhang, Micheal Kilgour, and Dinghuai Zhang. 2022. Biological Sequence Design with GFlowNets. arXiv preprint arXiv:2203.04115.

[27]

Ian Rhys Jenkins, Ludvig Oliver Gee, Alessia Knauss, Hang Yin, and Jan Schroeder. 2018. Accident scenario generation with recurrent neural networks. In 2018 21st International Conference on Intelligent Transportation Systems (ITSC). 3340–3345.

Digital Library

[28]

Moritz Klischat and Matthias Althoff. 2019. Generating critical test scenarios for automated vehicles with evolutionary algorithms. In 2019 IEEE Intelligent Vehicles Symposium (IV). 2352–2358.

Digital Library

[29]

Mark Koren, Saud Alsaif, Ritchie Lee, and Mykel J. Kochenderfer. 2018. Adaptive Stress Testing for Autonomous Vehicles. In 2018 IEEE Intelligent Vehicles Symposium (IV). 1–7.

[30]

LG Silicon Valley Lab. 2019. Maps Content. https://content.lgsvlsimulator.com/maps/ [Online; accessed Jul 2022]

[31]

LG Silicon Valley Lab. 2019. Maps Content. https://content.lgsvlsimulator.com/vehicles/ [Online; accessed Jul 2022]

[32]

Ritchie Lee, Ole J Mengshoel, Anshu Saksena, Ryan W Gardner, Daniel Genin, Joshua Silbermann, Michael Owen, and Mykel J Kochenderfer. 2020. Adaptive Stress Testing: Finding Likely Failure Events with Reinforcement Learning. Journal of Artificial Intelligence Research, 69 (2020), 1165–1201.

[33]

Ao Li, Shitao Chen, Liting Sun, Nanning Zheng, Masayoshi Tomizuka, and Wei Zhan. 2021. SceGene: Bio-Inspired Traffic Scenario Generation for Autonomous Driving Testing. IEEE Transactions on Intelligent Transportation Systems.

[34]

Guanpeng Li, Yiran Li, Saurabh Jha, Timothy Tsai, Michael Sullivan, Siva Kumar Sastry Hari, Zbigniew Kalbarczyk, and Ravishankar Iyer. 2020. AV-FUZZER: Finding Safety Violations in Autonomous Driving Systems. In 2020 IEEE 31st International Symposium on Software Reliability Engineering (ISSRE). 25–36.

[35]

Youzhi Luo, Keqiang Yan, and Shuiwang Ji. 2021. Graphdf: A discrete flow model for molecular graph generation. In International Conference on Machine Learning. 7192–7203.

[36]

Oded Maler and Dejan Nickovic. 2004. Monitoring temporal properties of continuous signals. In Formal Techniques, Modelling and Analysis of Timed and Fault-Tolerant Systems. Springer, 152–166.

[37]

Satoshi Masuda, Hiroaki Nakamura, and Kohichi Kajitani. 2018. Rule-based searching for collision test cases of autonomous vehicles simulation. IET Intelligent Transport Systems, 12, 9 (2018), 1088–1095.

[38]

Alexandra S Mueller, Jessica B Cicchino, and David S Zuby. 2020. What humanlike errors do autonomous vehicles need to avoid to maximize safety? Journal of safety research, 75 (2020), 310–318.

[39]

Galen E Mullins, Austin G Dress, Paul G Stankiewicz, Jordan D Appler, and Satyandra K Gupta. 2018. Accelerated testing and evaluation of autonomous vehicles via imitation learning. In 2018 IEEE International Conference on Robotics and Automation (ICRA). 5636–5642.

Digital Library

[40]

Dejan Ničković and Tomoya Yamaguchi. 2020. RTAMT: Online robustness monitors from STL. In International Symposium on Automated Technology for Verification and Analysis. 564–571.

Digital Library

[41]

Hari Mohan Pandey, Ankit Chaudhary, and Deepti Mehrotra. 2014. A comparative review of approaches to prevent premature convergence in GA. Applied Soft Computing, 24 (2014), 1047–1077. issn:1568-4946 https://doi.org/10.1016/j.asoc.2014.08.025

Digital Library

[42]

Michael Pines. 2022. Top Causes of Car Accidents: 25 Most Common Causes of Accidents on the Road. https://seriousaccidents.com/legal-advice/top-causes-of-car-accidents/ [Online; accessed Agu 2022]

[43]

Vasumathi Raman, Alexandre Donzé, Mehdi Maasoumy, Richard M. Murray, Alberto Sangiovanni-Vincentelli, and Sanjit A. Seshia. 2014. Model predictive control with signal temporal logic specifications. In 53rd IEEE Conference on Decision and Control. 81–87. https://doi.org/10.1109/CDC.2014.7039363

[44]

Alëna Rodionova, Ignacio Alvarez, Maria Soledad Elli, Fabian Oboril, Johannes Quast, and Rahul Mangharam. 2020. How safe is safe enough? Automatic safety constraints boundary estimation for decision-making in automated vehicles. In 2020 IEEE Intelligent Vehicles Symposium (IV). 1457–1464.

[45]

Guodong Rong, Byung Hyun Shin, Hadi Tabatabaee, Qiang Lu, Steve Lemke, Mārtiņš Možeiko, Eric Boise, Geehoon Uhm, Mark Gerow, Shalin Mehta, Eugene Agafonov, Tae Hyung Kim, Eric Sterner, Keunhae Ushiroda, Michael Reyes, Dmitry Zelenkovsky, and Seonman Kim. 2020. LGSVL Simulator: A High Fidelity Simulator for Autonomous Driving. In 2020 IEEE 23rd International Conference on Intelligent Transportation Systems (ITSC). 1–6.

[46]

Ari Seff, Wenda Zhou, Farhan Damani, Abigail Doyle, and Ryan P Adams. 2019. Discrete object generation with reversible inductive construction. Advances in Neural Information Processing Systems, 32 (2019).

[47]

Chence Shi, Minkai Xu, Zhaocheng Zhu, Weinan Zhang, Ming Zhang, and Jian Tang. 2019. GraphAF: a Flow-based Autoregressive Model for Molecular Graph Generation. In International Conference on Learning Representations.

[48]

Yang Sun, Christopher M Poskitt, Jun Sun, Yuqi Chen, and Zijiang Yang. 2022. LawBreaker: An Approach for Specifying Traffic Laws and Fuzzing Autonomous Vehicles. In 37th IEEE/ACM International Conference on Automated Software Engineering. 1–12.

[49]

Jessica Van Brummelen, Marie O’Brien, Dominique Gruyer, and Homayoun Najjaran. 2018. Autonomous vehicle perception: The technology of today and tomorrow. Transportation Research Part C: Emerging Technologies, 89 (2018), 384–406. issn:0968-090X

[50]

Yutong Xie, Chence Shi, Hao Zhou, Yuwei Yang, Weinan Zhang, Yong Yu, and Lei Li. 2021. \MARS Markov Molecular Sampling for Multi-objective Drug Discovery. In International Conference on Learning Representations. https://openreview.net/forum?id=kHSu4ebxFXY

Cited By

Tang SZhang ZZhou JLei LZhou YXue YFilkov VRay BZhou M(2024)LeGEND: A Top-Down Approach to Scenario Generation of Autonomous Driving Systems Assisted by Large Language ModelsProceedings of the 39th IEEE/ACM International Conference on Automated Software Engineering10.1145/3691620.3695520(1497-1508)Online publication date: 27-Oct-2024
https://dl.acm.org/doi/10.1145/3691620.3695520
Wang TGu TDeng HLi HKuang XZhao GChristakis MPradel M(2024)Dance of the ADS: Orchestrating Failures through Historically-Informed Scenario FuzzingProceedings of the 33rd ACM SIGSOFT International Symposium on Software Testing and Analysis10.1145/3650212.3680344(1086-1098)Online publication date: 11-Sep-2024
https://dl.acm.org/doi/10.1145/3650212.3680344
Li ZDai JHuang ZYou NZhang YYang MChristakis MPradel M(2024)VioHawk: Detecting Traffic Violations of Autonomous Driving Systems through Criticality-Guided Simulation TestingProceedings of the 33rd ACM SIGSOFT International Symposium on Software Testing and Analysis10.1145/3650212.3680325(844-855)Online publication date: 11-Sep-2024
https://dl.acm.org/doi/10.1145/3650212.3680325
Show More Cited By

Index Terms

Testing Automated Driving Systems by Breaking Many Laws Efficiently
1. Software and its engineering
  1. Software creation and management
    1. Software verification and validation
      1. Software defect analysis
        Software testing and debugging

Recommendations

LawBreaker: An Approach for Specifying Traffic Laws and Fuzzing Autonomous Vehicles
ASE '22: Proceedings of the 37th IEEE/ACM International Conference on Automated Software Engineering

Autonomous driving systems (ADSs) must be tested thoroughly before they can be deployed in autonomous vehicles. High-fidelity simulators allow them to be tested against diverse scenarios, including those that are difficult to recreate in real-world ...
Metamorphic Fuzz Testing of Autonomous Vehicles
ICSEW'20: Proceedings of the IEEE/ACM 42nd International Conference on Software Engineering Workshops

Driving simulation is the primary approach for testing the software components of autonomous vehicles. This paper presents an automated testing method, termed metamorphic fuzz testing (MFT), in the context of simulation testing of autonomous driving. ...
Transition to Automated: The Interaction of Activating the In-vehicle Automated Driving System
Design, User Experience, and Usability. Application Domains
Abstract
Automated driving system (ADS) becomes more popularized in recent years, and the level 2 and level 3 ADS have already been equipped on several production car models in the market. The activating interaction of the ADS is very important since it is ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ISSTA 2023: Proceedings of the 32nd ACM SIGSOFT International Symposium on Software Testing and Analysis

July 2023

1554 pages

ISBN:9798400702211

DOI:10.1145/3597926

General Chair:
René Just
University of Washington, USA
,
Program Chair:
Gordon Fraser
University of Passau, Germany

Copyright © 2023 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 13 July 2023

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

MOE Tier 3

Conference

ISSTA '23

Sponsor:

SIGSOFT

ISSTA '23: 32nd ACM SIGSOFT International Symposium on Software Testing and Analysis

July 17 - 21, 2023

WA, Seattle, USA

Acceptance Rates

Overall Acceptance Rate 58 of 213 submissions, 27%

Upcoming Conference

ISSTA '25

Sponsor:
sigsoft

34th ACM SIGSOFT International Symposium on Software Testing and Analysis

June 25 - 28, 2025

Trondheim , Norway

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
724
Total Downloads

Downloads (Last 12 months)389
Downloads (Last 6 weeks)60

Reflects downloads up to 01 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Tang SZhang ZZhou JLei LZhou YXue YFilkov VRay BZhou M(2024)LeGEND: A Top-Down Approach to Scenario Generation of Autonomous Driving Systems Assisted by Large Language ModelsProceedings of the 39th IEEE/ACM International Conference on Automated Software Engineering10.1145/3691620.3695520(1497-1508)Online publication date: 27-Oct-2024
https://dl.acm.org/doi/10.1145/3691620.3695520
Wang TGu TDeng HLi HKuang XZhao GChristakis MPradel M(2024)Dance of the ADS: Orchestrating Failures through Historically-Informed Scenario FuzzingProceedings of the 33rd ACM SIGSOFT International Symposium on Software Testing and Analysis10.1145/3650212.3680344(1086-1098)Online publication date: 11-Sep-2024
https://dl.acm.org/doi/10.1145/3650212.3680344
Li ZDai JHuang ZYou NZhang YYang MChristakis MPradel M(2024)VioHawk: Detecting Traffic Violations of Autonomous Driving Systems through Criticality-Guided Simulation TestingProceedings of the 33rd ACM SIGSOFT International Symposium on Software Testing and Analysis10.1145/3650212.3680325(844-855)Online publication date: 11-Sep-2024
https://dl.acm.org/doi/10.1145/3650212.3680325
Lu YTian YBi YChen BPeng XChristakis MPradel M(2024)DiaVio: LLM-Empowered Diagnosis of Safety Violations in ADS Simulation TestingProceedings of the 33rd ACM SIGSOFT International Symposium on Software Testing and Analysis10.1145/3650212.3652135(376-388)Online publication date: 11-Sep-2024
https://dl.acm.org/doi/10.1145/3650212.3652135
Zhang XBao JShen Y(2024)Testing Object Detection Models For Autonomous Vehicles Against Hazards2024 International Conference on Networking and Network Applications (NaNA)10.1109/NaNA63151.2024.00095(542-548)Online publication date: 9-Aug-2024
https://doi.org/10.1109/NaNA63151.2024.00095
Gulzar MMatiisen TMuhammad N(2024)Scenario Driven Development for Open Source Autonomous Driving Stack2024 IEEE 29th International Conference on Emerging Technologies and Factory Automation (ETFA)10.1109/ETFA61755.2024.10710800(1-8)Online publication date: 10-Sep-2024
https://doi.org/10.1109/ETFA61755.2024.10710800
Li JBai GPham LSun J(2023)Towards an Effective and Interpretable Refinement Approach for DNN Verification2023 IEEE 23rd International Conference on Software Quality, Reliability, and Security (QRS)10.1109/QRS60937.2023.00062(569-580)Online publication date: 22-Oct-2023
https://doi.org/10.1109/QRS60937.2023.00062

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents