research-article

Targeting requirements violations of autonomous driving systems by dynamic evolutionary search

Authors:

Fuyuki Ishikawa,

Tao XieAuthors Info & Claims

ASE '21: Proceedings of the 36th IEEE/ACM International Conference on Automated Software Engineering

Pages 279 - 291

https://doi.org/10.1109/ASE51524.2021.9678883

Published: 24 June 2022 Publication History

Abstract

Autonomous Driving Systems (ADSs) are complex systems that must satisfy multiple requirements such as safety, compliance to traffic rules, and comfortableness. However, satisfying all these requirements may not always be possible due to emerging environmental conditions. Therefore, the ADSs may have to make trade-offs among multiple requirements during the ongoing operation, resulting in one or more requirements violations. For ADS engineers, it is highly important to know which combinations of requirements violations may occur, as different combinations can expose different types of failures. However, there is currently no testing approach that can generate scenarios to expose different combinations of requirements violations. To address this issue, in this paper, we introduce the notion of requirements violation pattern to characterize a specific combination of requirements violations. Based on this notion, we propose a testing approach named EMOOD that can effectively generate test scenarios to expose as many requirements violation patterns as possible. EMOOD uses a prioritization technique to sort all possible patterns to search for, from the most to the least critical ones. Then, EMOOD iteratively includes an evolutionary many-objective optimization algorithm to find different combinations of requirements violations. In each iteration, the targeted pattern is determined by a dynamic prioritization technique to give preferences to those patterns with higher criticality and higher likelihood to occur. We apply EMOOD to an industrial ADS under two common traffic situations. Evaluation results show that EMOOD outperforms three baseline approaches in generating test scenarios by discovering more requirements violation patterns.

References

[1]

U. Topcu, N. Bliss, N. Cooke, M. L. Cummings, A. Llorens, H. E. Shrobe, and L. Zuck, "Assured autonomy: Path toward living with autonomous systems we can trust," CoRR, vol. abs/2010.14443, 2020.

[2]

Waymo, "On the Road to Fully Self-Driving: Waymo Safety Report," 2018. [Online]. Available: https://waymo.com/safety/

[3]

Voyage, "Open Autonomous Safety," 2019. [Online]. Available: https://github.com/voyage/open-autonomous-safety

[4]

I. Majzik, O. Semeráth, C. Hajdu, K. Marussy, Z. Szatmári, Z. Micskei, A. Vörös, A. A. Babikian, and D. Varró, "Towards system-level testing with coverage guarantees for autonomous vehicles," in Proc. 22nd IEEE International Conference on Model Driven Engineering Languages and Systems (MODELS), 2019, pp. 89--94, - 12.

[5]

N. Kalra and S. M. Paddock, Driving to Safety: How Many Miles of Driving Would It Take to Demonstrate Autonomous Vehicle Reliability? RAND Corporation, 2016.

[6]

R. Ben Abdessalem, S. Nejati, L. C. Briand, and T. Stifter, "Testing advanced driver assistance systems using multi-objective search and neural networks," in Proc. 31st IEEE/ACM International Conference on Automated Software Engineering (ASE), 2016, pp. 63--74

Digital Library

[7]

R. Ben Abdessalem, "Testing vision-based control systems using learnable evolutionary algorithms," in Proc. 40th IEEE/ACM International Conference on Software Engineering (ICSE), 2018, pp. 1016--1026

Digital Library

[8]

R. Ben Abdessalem, A. Panichella, S. Nejati, L. C. Briand, and T. Stifter, "Testing autonomous cars for feature interaction failures using many-objective search," in Proc. 33rd IEEE/ACM International Conference on Automated Software Engineering (ASE), 2018, pp. 143--154

Digital Library

[9]

A. Gambi, M. Mueller, and G. Fraser, "Automatically testing self-driving cars with search-based procedural content generation," in Proc. 28th ACM International Symposium on Software Testing and Analysis (ISSTA), 2019, pp. 318--328

Digital Library

[10]

A. Calò, P. Arcaini, S. Ali, F. Hauer, and F. Ishikawa, "Generating avoidable collision scenarios for testing autonomous driving systems," in Proc. 13th IEEE International Conference on Software Testing, Validation and Verification (ICST), 2020, pp. 375--386

[11]

A. Calò, "Simultaneously searching and solving multiple avoidable collisions for testing autonomous driving systems," in Proc. 22nd ACM Genetic and Evolutionary Computation Conference (GECCO), 2020, pp. 1055--1063

Digital Library

[12]

G. Li, Y. Li, S. Jha, T. Tsai, M. B. Sullivan, S. K. S. Hari, Z. Kalbarczyk, and R. K. Iyer, "AV-FUZZER: finding safety violations in autonomous driving systems," in Proc. 31st IEEE International Symposium on Software Reliability Engineering (ISSRE), 2020, pp. 25--36

[13]

T. Laurent, P. Arcaini, F. Ishikawa, and A. Ventresque, "Achieving weight coverage for an autonomous driving system with search-based test generation," in Proc. 25th IEEE International Conference on Engineering of Complex Computer Systems (ICECCS), 2020, pp. 93--102

[14]

P. Arcaini, X.-Y. Zhang, and F. Ishikawa, "Targeting patterns of driving characteristics in testing autonomous driving systems," in Proc. 14th IEEE International Conference on Software Testing, Verification and Validation (ICST), 2021, pp. 295--305

[15]

Y. Li, J. Tao, and F. Wotawa, "Ontology-based test generation for automated and autonomous driving functions," Information and Software Technology, vol. 117, 2020

Digital Library

[16]

F. Hauer, T. Schmidt, B. Holzmüller, and A. Pretschner, "Did we test all scenarios for automated and autonomous driving systems?" in Proc. 22nd IEEE Intelligent Transportation Systems Conference (ITSC), 2019, pp. 2950--2955

Digital Library

[17]

C. Zhang, Y. Liu, D. Zhao, and Y. Su, "Roadview: A traffic scene simulator for autonomous vehicle simulation testing," in Proc. 17th International IEEE Conference on Intelligent Transportation Systems (ITSC), 2014, pp. 1160--1165

[18]

D. Zhao and H. Peng, "From the lab to the street: Solving the challenge of accelerating automated vehicle testing," CoRR, vol. abs/1707.04792, 2017.

[19]

A. Belbachir, J.-C. Smal, J.-M. Blosseville, and D. Gruyer, "Simulation-driven validation of advanced driving-assistance systems," Procedia-Social and Behavioral Sciences, vol. 48, pp. 1205--1214, 2012.

[20]

S. Shalev-Shwartz, S. Shammah, and A. Shashua, "On a formal model of safe and scalable self-driving cars," CoRR, vol. abs/1708.06374, 2017.

[21]

ISO, "Road vehicles - Functional safety," 2011. [Online]. Available: https://www.iso.org/standard/68383.html

[22]

K. Czarnecki, "Automated driving system (ads) high-level quality requirements analysis- driving behavior safety," Waterloo Intelligent Systems Engineering Lab (WISE) Report, University of Waterloo, 2018.

[23]

C. E. Tuncali, G. Fainekos, D. Prokhorov, H. Ito, and J. Kapinski, "Requirements-driven test generation for autonomous vehicles with machine learning components," IEEE Transactions on Intelligent Vehicles, vol. 5, no. 2, pp. 265--280, 2019

[24]

J. Morse, D. Araiza-Illan, K. Eder, J. Lawry, and A. Richards, "A fuzzy approach to qualification in design exploration for autonomous robots and systems," in Proc. 26th IEEE International Conference on Fuzzy Systems (FUZZ-IEEE), 2017, pp. 1--6

Digital Library

[25]

L. Baresi, L. Pasquale, and P. Spoletini, "Fuzzy goals for requirements-driven adaptation," in Proc. 18th IEEE International Requirements Engineering Conference (RE), 2010, pp. 125--134

Digital Library

[26]

EMOO-DP, "Project website for "Targeting Requirements Violations of Autonomous Driving Systems by Dynamic Evolutionary Search"," 2021. [Online]. Available: https://sites.google.com/view/emoodproj/

[27]

A. Corso, R. J. Moss, M. Koren, R. Lee, and M. J. Kochenderfer, "A survey of algorithms for black-box safety validation," CoRR, vol. abs/2005.02979, 2020.

[28]

S. Chand and M. Wagner, "Evolutionary many-objective optimization: A quick-start guide," Surveys in Operations Research and Management Science, vol. 20, no. 2, pp. 35--42, 2015.

[29]

K. Deb and H. Jain, "An evolutionary many-objective optimization algorithm using reference-point-based nondominated sorting approach, part i: solving problems with box constraints," IEEE Transactions on Evolutionary Computation, vol. 18, no. 4, pp. 577--601, 2013

[30]

A. Ramirez, J. R. Romero, and S. Ventura, "A survey of many-objective optimisation in search-based software engineering," Journal of Systems and Software, vol. 149, pp. 382--395, 2019

[31]

T. Dreossi, D. J. Fremont, S. Ghosh, E. Kim, H. Ravanbakhsh, M. Vazquez-Chanlatte, and S. A. Seshia, "VerifAI: A toolkit for the formal design and analysis of artificial intelligence-based systems," in Proc. 31st International Conference on Computer-Aided Verification (CAV), 2019, pp. 432--442

[32]

F. Klück, M. Zimmermann, F. Wotawa, and M. Nica, "Performance comparison of two search-based testing strategies for ADAS system validation," in Proc. 31st IFIP International Conference on Testing Software and Systems (ICTSS), 2019, pp. 140--156

Digital Library

[33]

T. G. Dietterich, "Ensemble methods in machine learning," in Proc. 1st International Workshop on Multiple Classifier Systems Multiple (MCS), 2000, pp. 1--15

[34]

M. Harman, S. A. Mansouri, and Y. Zhang, "Search-based software engineering: Trends, techniques and applications," ACM Computing Surveys, vol. 45, no. 1, pp. 11:1--11:61, 2012

Digital Library

[35]

A. Benitez-Hidalgo, A. J. Nebro, J. Garcia-Nieto, I. Oregi, and J. Del Ser, "jMetalPy: A Python framework for multi-objective optimization with metaheuristics," Swarm and Evolutionary Computation, vol. 51, 2019

[36]

B. L. Miller, D. E. Goldberg et al., "Genetic algorithms, tournament selection, and the effects of noise," Complex systems, vol. 9, no. 3, pp. 193--212, 1995.

[37]

A. Arcuri and L. Briand, "A practical guide for using statistical tests to assess randomized algorithms in software engineering," in Proc. 33rd IEEE/ACM International Conference on Software Engineering (ICSE), 2011, pp. 1--10

Digital Library

[38]

J. A. Capon, Elementary Statistics for the Social Sciences: Study Guide. Wadsworth Publishing Company Belmont, 1991.

[39]

A. Vargha and H. D. Delaney, "A critique and improvement of the CL common language effect size statistics of McGraw and Wong," Journal of Educational and Behavioral Statistics, vol. 25, no. 2, pp. 101--132, 2000

[40]

SAE, "Taxonomy and definitions for terms related to driving automation systems for on-road motor vehicles," 2018. [Online]. Available: https://www.sae.org/standards/content/j3016_201806/

[41]

A. Panichella, F. M. Kifetew, and P. Tonella, "Reformulating branch coverage as a many-objective optimization problem," in Proc. 8th IEEE International Conference on Software Testing, Verification and Validation (ICST), 2015, pp. 1--10

[42]

A. Panichella, "Automated test case generation as a many-objective optimisation problem with dynamic selection of the targets," IEEE Transactions on Software Engineering, vol. 44, no. 2, pp. 122--158, 2017

[43]

G. Fraser and A. Arcuri, "EvoSuite: automatic test suite generation for object-oriented software," in Proc. 19th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering (ESEC/FSE), 2011, pp. 416--419

Digital Library

[44]

Z. Tahir and R. Alexander, "Coverage based testing for V&V and safety assurance of self-driving autonomous vehicle: A systematic literature review," in Proc. 2nd IEEE International Conference On Artificial Intelligence Testing (AITest), 2020, pp. 23--30

[45]

Y. Tian, K. Pei, S. Jana, and B. Ray, "DeepTest: Automated testing of deep-neural-network-driven autonomous cars," in Proc. 40th IEEE/ACM International Conference on Software Engineering (ICSE), 2018, pp. 303--314

Digital Library

[46]

R. Alexander, H. Hawkins, and A. Rae, Situation coverage - a coverage criterion for testing autonomous robots. Department of Computer Science, University of York, 2015, vol. Report number YCS-2015-496.

[47]

S. Nejati, K. Gaaloul, C. Menghi, L. C. Briand, S. Foster, and D. Wolfe, "Evaluating model testing and model checking for finding requirements violations in Simulink models," in Proc. 27th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering (ESEC/FSE), 2019, pp. 1015--1025

Digital Library

[48]

C. Gladisch, T. Heinz, C. Heinzemann, J. Oehlerking, A. von Vietinghoff, and T. Pfitzer, "Experience paper: search-based testing in automated driving control applications," in Proc. 34th IEEE/ACM International Conference on Automated Software Engineering (ASE), 2019, pp. 26--37

Digital Library

Cited By

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
Song QEngström ERuneson P(2024)Industry Practices for Challenging Autonomous Driving Systems with Critical ScenariosACM Transactions on Software Engineering and Methodology10.1145/364033433:4(1-35)Online publication date: 11-Jan-2024
https://dl.acm.org/doi/10.1145/3640334
Giamattei LGuerriero APietrantuono RRusso S(2024)Causality-driven Testing of Autonomous Driving SystemsACM Transactions on Software Engineering and Methodology10.1145/363570933:3(1-35)Online publication date: 15-Mar-2024
https://dl.acm.org/doi/10.1145/3635709
Show More Cited By

Targeting requirements violations of autonomous driving systems by dynamic evolutionary search
1. Software and its engineering
  1. Software creation and management
    1. Software verification and validation
      1. Software defect analysis

Recommendations

Targeting requirements violations of autonomous driving systems by dynamic evolutionary search (HOP at GECCO'22)
GECCO '22: Proceedings of the Genetic and Evolutionary Computation Conference Companion

Autonomous Driving Systems (ADSs) must satisfy multiple requirements. In some cases, satisfying all of them may not be possible due to environmental conditions. Therefore, ADSs usually make tradeoffs among the requirements, resulting in one or more ...
Software Systems Requirements

This module describes course SWE 2623 on software systems requirements given at the School of Computing and Software Engineering Southern Polytechnic State University. The process of extracting, deriving, and validating software requirements from a ...
Approximate non-dominated sorting for evolutionary many-objective optimization

Non-dominated sorting has widely been adopted and shown to be very effective in dominance based evolutionary multi-objective optimization where the number of objectives is two or three. In dealing with many-objective optimization problems, where the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ASE '21: Proceedings of the 36th IEEE/ACM International Conference on Automated Software Engineering

November 2021

1446 pages

ISBN:9781665403375

General Chair:
John Grundy
Monash University, Australia

Sponsors

In-Cooperation

IEEE CS

Publisher

IEEE Press

Publication History

Published: 24 June 2022

Check for updates

Author Tags

Qualifiers

Research-article

Conference

ASE '21

Sponsor:

ASE '21: 36th IEEE/ACM International Conference on Automated Software Engineering

November 15 - 19, 2021

Melbourne, Australia

Acceptance Rates

Overall Acceptance Rate 82 of 337 submissions, 24%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

11
Total Citations
View Citations
57
Total Downloads

Downloads (Last 12 months)25
Downloads (Last 6 weeks)4

Reflects downloads up to 26 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

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
Song QEngström ERuneson P(2024)Industry Practices for Challenging Autonomous Driving Systems with Critical ScenariosACM Transactions on Software Engineering and Methodology10.1145/364033433:4(1-35)Online publication date: 11-Jan-2024
https://dl.acm.org/doi/10.1145/3640334
Giamattei LGuerriero APietrantuono RRusso S(2024)Causality-driven Testing of Autonomous Driving SystemsACM Transactions on Software Engineering and Methodology10.1145/363570933:3(1-35)Online publication date: 15-Mar-2024
https://dl.acm.org/doi/10.1145/3635709
Jiang JYang JZhang YWang ZYou HChen J(2024)A Post-training Framework for Improving the Performance of Deep Learning Models via Model TransformationACM Transactions on Software Engineering and Methodology10.1145/363001133:3(1-41)Online publication date: 15-Mar-2024
https://dl.acm.org/doi/10.1145/3630011
Sun HPoskitt CSun YSun JChen YRoychoudhury APaiva AAbreu RStorey M(2024)ACAV: A Framework for Automatic Causality Analysis in Autonomous Vehicle Accident RecordingsProceedings of the IEEE/ACM 46th International Conference on Software Engineering10.1145/3597503.3639175(1-13)Online publication date: 20-May-2024
https://dl.acm.org/doi/10.1145/3597503.3639175
Valle PArrieta AArratibel MJust RFraser G(2023)Applying and Extending the Delta Debugging Algorithm for Elevator Dispatching Algorithms (Experience Paper)Proceedings of the 32nd ACM SIGSOFT International Symposium on Software Testing and Analysis10.1145/3597926.3598117(1055-1067)Online publication date: 12-Jul-2023
https://dl.acm.org/doi/10.1145/3597926.3598117
Tang SZhang ZZhang YZhou JGuo YLiu SGuo SLi YMa LXue YLiu Y(2023)A Survey on Automated Driving System Testing: Landscapes and TrendsACM Transactions on Software Engineering and Methodology10.1145/357964232:5(1-62)Online publication date: 24-Jul-2023
https://dl.acm.org/doi/10.1145/3579642
He JBao ZZhang QSun WLiu JFang CLin Y(2022)ElecDaug: Electromagnetic Data Augmentation for Model Repair based on Metamorphic RelationProceedings of the 37th IEEE/ACM International Conference on Automated Software Engineering10.1145/3551349.3559536(1-5)Online publication date: 10-Oct-2022
https://dl.acm.org/doi/10.1145/3551349.3559536
Zhang YWang ZJiang JYou HChen J(2022)Toward Improving the Robustness of Deep Learning Models via Model TransformationProceedings of the 37th IEEE/ACM International Conference on Automated Software Engineering10.1145/3551349.3556920(1-13)Online publication date: 10-Oct-2022
https://dl.acm.org/doi/10.1145/3551349.3556920
Laurent TKlikovits SArcaini PIshikawa FVentresque A(2022)Parameter Coverage for Testing of Autonomous Driving Systems under UncertaintyACM Transactions on Software Engineering and Methodology10.1145/355027032:3(1-31)Online publication date: 22-Jul-2022
https://dl.acm.org/doi/10.1145/3550270
Show More Cited By

View Options

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

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents