Algorithmic Input Generation for More Effective Software Testing
Abstract
It is impossible in practice to comprehensively test even small software programs due to the vastness of the reachable state space; however, modern cyber-physical systems such as aircraft require a high degree of confidence in software safety and reliability. Here we explore methods of generating test sets to effectively and efficiently explore a program space for a module of the Traffic Collision Avoidance System (TCAS) used on commercial aircraft. A formal model of TCAS in the model-checking language NuSMV provides an output oracle. We compare test sets generated using various methods, including covering arrays, random, and a low-complexity input paradigm applied to 28 versions of the TCAS C program containing seeded errors. Faults are triggered by tests for all 28 programs using a combination of covering arrays and random input generation. Complexity-based inputs perform more efficiently than covering arrays, and can be paired with random input generation to create efficient and effective test sets. A random forest classifier identifies variable values that can be targeted to generate tests even more efficiently in future work, by combining a machine-learned fuzzing algorithm with more complex model oracles developed in model-based systems engineering (MBSE) software.
Document Details
- Document Type
- Technical Report
- Publication Date
- Nov 01, 2021
- Accession Number
- AD1204605
Entities
People
- Christopher J. Mccormack
- Jackson R. Mayo
- Jinseo Lee
- Laura W. Epifanovskaya
- Reginald N. Meeson
- Robert C. Armstrong
Organizations
- Institute for Defense Analyses
- Sandia National Laboratories