Statistical path coverage for non-deterministic complex safety-related software testing

Abstract

Emerging technologies in the embedded domain enable the development of innovative software-driven solutions. Autonomous systems are a clear example of this trend and have attracted considerable attention from different industrial sectors and research fields. In fact, they can be considered game-changers for several domains, even for the functional safety domain. These innovative safety-related systems are characterized by an increasing software complexity and high-performance requirements. Hence, a desirable requirement is to deploy an Operating System (OS), such as Linux, on these next-generation complex safety-related systems to fully take advantage of its benefits (e.g., security, reliability, software updates, performance). However, implementing a software layer, such as the Linux kernel, on a resource-sharing architecture hinders the verification process so that it is no longer feasible to base it on traditional approaches, most notably on testing. The potential of traditional testing lies in achieving exhaustive coverage, which is extremely difficult (if even feasible) in the systems with the complexity of those being developed today. Therefore, we believe that testing of software elements needs to be combined with analysis to pave the way towards safety assurance. This thesis contributes with a novel statistical analysis technique to quantify the execution path coverage of the Linux kernel and for estimating the risk entailed by untested execution paths. In the first part, the main gaps in the field of test coverage are examined, specially focused on the Linux kernel. Afterward, different research activities are conducted to statistically estimate the test coverage by the analysis of the execution paths traversed during the testing campaign. The inherent non-determinism of the Linux kernel and the viability of estimating the coverage with different methods is further demonstrated. An additional statistical method to calculate the execution probability of untested paths and determine the risk they entail is proposed. Finally, a technique that combines all these contributions in order to quantify the testing process and the risk associated with the uncovered paths. With the above contributions, this thesis proposes moving towards a statistical approach to quantify the coverage and the risk, and bridge the gap towards the certification of safety-related complex applications based on Linux or other complex OS that run on Commercial Off-The-Shelf (COTS) multi-core devices.