Computer Security Resource Center

Computer Security Resource Center

Computer Security
Resource Center

Automated Combinatorial Testing for Software

Autonomous Vehicles

Self-driving cars and autonomous vehicles of all types are notoriously difficult challenges for software assurance.  Both traditional testing and formal methods are even harder to apply for autonomous systems than in ordinary cases. The key problem is that these systems must be able to function correctly in a vast space of possible input conditions - lighting, rain, fog, pedestrians, animals, other vehicles, road markings, signs, etc.  Combinatorial methods are uniquely well suited to analysis and testing for this enormous input space, because by their nature they efficiently test combinations that are rare, and very probably would not be included using traditional test methods. 

The following are examples of how combinatorial testing can be applied for assurance of autonomous systems.

Tao, J., Li, Y., Wotawa, F., Felbinger, H., & Nica, M. (2019, April). On the Industrial Application of Combinatorial Testing for Autonomous Driving Functions. In 2019 IEEE International Conference on Software Testing, Verification and Validation Workshops (ICSTW)(pp. 234-240). IEEE.

We discuss a method for testing automated and autonomous driving functions using ontologies and combinatorial testing that is able to automate test case generation. Moreover, we report on the application of the method at the industrial level. There we depict the comprehensive application process from the construction of the ontology to test suite execution in detail. This case study shows that the proposed approach can be used for testing and validation of autonomous driving functions in practice.

 

Klueck, F., Li, Y., Nica, M., Tao, J., & Wotawa, F. (2018, October). Using ontologies for test suites generation for automated and autonomous driving functions. In 2018 IEEE International Symposium on Software Reliability Engineering Workshops (ISSREW)(pp. 118-123). IEEE.

In this paper, we outline a general automated testing approach to be applied for verification and validation of automated and autonomous driving functions. The approach makes use of ontologies of environment the system under test is interacting with. Ontologies are automatically converted into input models for combinatorial testing, which are used to generate test cases. The obtained abstract test cases are used to generate concrete test scenarios that provide the basis for simulation used to verify the functionality of the system under test. We discuss the general approach including its potential for automation in the automotive domain where there is growing need for sophisticated verification based on simulation in case of automated and autonomous vehicles.

 

Tuncali, C. E., Fainekos, G., Ito, H., & Kapinski, J. (2018, June). Simulation-based adversarial test generation for autonomous vehicles with machine learning components. In 2018 IEEE Intelligent Vehicles Symposium (IV)(pp. 1555-1562). IEEE.

One of the main challenges is that many autonomous driving systems have machine learning (ML) components, such as deep neural networks, for which formal properties are difficult to characterize. We present a testing framework that is compatible with test case generation and automatic falsification methods, which are used to evaluate cyber-physical systems. We demonstrate how the framework can be used to evaluate closed-loop properties of an autonomous driving system model that includes the ML components, all within a virtual environment. We demonstrate how to use test case generation methods, such as covering arrays, as well as requirement falsification methods to automatically identify problematic test scenarios. The resulting framework can be used to increase the reliability of autonomous driving systems.

 

Masuda, S., Nakamura, H., & Kajitani, K. (2018). Rule-based searching for collision test cases of autonomous vehicles simulation. IET Intelligent Transport Systems12(9), 1088-1095.

Thorough testing of AD software using simulations must be conducted in advance of testing AD cars on the road. Parameters of the many objects around an AD car, such as other cars, traffic lanes and pedestrians are required as inputs of the simulation. Therefore, the number of parameter combinations becomes extremely large. A combination of parameters is called a test case; hence, the challenge is to search collision test cases from the extremely large number of combinations. A rule-based method is the main focus because an explicit method of searching test cases is required in certain industries in the real world. In this study, a method of rule-based searching for collision test cases of autonomous vehicles simulations is proposed. Simulation models that have rules between an AD car and other cars are defined. Algorithms were also developed to search collision test cases that generate test cases incrementally. Experiments on AD simulations involving the simulation models of a three-lane highway and a signalised intersection were conducted. The results indicate the efficiency of the method.

 

Abdessalem, R. B., Nejati, S., Briand, L. C., & Stifter, T. (2018, May). Testing vision-based control systems using learnable evolutionary algorithms. In 2018 IEEE/ACM 40th International Conference on Software Engineering (ICSE)(pp. 1016-1026). IEEE.

Our evaluation performed on an industrial automotive automotive system shows that: (1) Our algorithm outperforms a baseline evolutionary search algorithm and generates 78% more distinct, critical test scenarios compared to the baseline algorithm. (2) Our algorithm accurately characterizes critical regions of the system under test, thus identifying the conditions that are likely to lead to system failures.

 

Rocklage, E., Kraft, H., Karatas, A., & Seewig, J. (2017, October). Automated scenario generation for regression testing of autonomous vehicles. In 2017 IEEE 20th International Conference on Intelligent Transportation Systems (ITSC)(pp. 476-483). IEEE.

We present a novel approach to automatically generate test scenarios for regression testing of autonomous vehicle systems as a black box in a virtual simulation environment. To achieve this we focus on the problem of generating the motion of other traffic participants without loss of generality. We combine the combinatorial interaction testing approach with a simple trajectory planner as a feasibility checker to generate efficient test sets with variable coverage. The underlying constraint satisfaction problem is solved with a simple backtracking algorithm.

 

Tuncali, C. E., Fainekos, G., Prokhorov, D., Ito, H., & Kapinski, J. (2019). Requirements-driven Test Generation for Autonomous Vehicles with Machine Learning Components. arXiv preprint arXiv:1908.01094.

We use multiple methods to generate test cases, including covering arrays, which is an efficient method to search discrete variable spaces. The resulting test cases can be used to debug the controller design by identifying controller behaviors that do not satisfy requirements. The test cases can also enhance the testing phase of development by identifying critical corner cases that correspond to the limits of the system’s allowed behaviors. We present STL requirements for an autonomous vehicle system, which capture both component-level and system level behaviors. Additionally, we present three driving scenarios and demonstrate how our requirements-driven testing framework can be used to identify critical system behaviors, which can be used to support the development process.

 

Majumdar, R., Mathur, A., Pirron, M., Stegner, L., & Zufferey, D. (2019). Paracosm: A Language and Tool for Testing Autonomous Driving Systems. arXiv preprint arXiv:1902.01084.

Paracosm allows users to programmatically describe complex driving situations with specific visual features, e.g., road layout in an urban environment, as well as reactive temporal behaviors of cars and pedestrians. Paracosm programs are executed on top of a game engine that provides realistic physics simulation and visual rendering. The infrastructure allows systematic exploration of the state space, both for visual features (lighting, shadows, fog) and for reactive interactions with the environment (pedestrians, other traffic). We define a notion of test coverage for Paracosm configurations based on combinatorial testing and low dispersion sequences.

Created May 24, 2016, Updated September 19, 2019