Efficient techniques and tools for software testing based on traces and coverage analysis
Doctoral thesis
Published version
Permanent lenke
https://hdl.handle.net/11250/3029526Utgivelsesdato
2022Metadata
Vis full innførselSamlinger
Originalversjon
Ahishakiye, F. (2022). Efficient techniques and tools for software testing based on traces and coverage analysis [Doctoral dissertation, Western Norway University of Applied Sciences]. HVL Open.Sammendrag
To ensure ultra-high dependability and ultra-low defect rates, certification standards such as DO-178C requires safety-critical software with the highest safety level (Level A) in avionics systems to conform to the modified condition decision coverage (MC/DC) criterion. MC/DC is a strong coverage criterion that subsumes existing coverage criteria and it requires a small number of test inputs compared to the combinatorially exhaustive multiple condition coverage (MCC). MC/DC has also proven to reveal many program defects. However, both MC/DC measurement and generating test cases satisfying MC/DC remain a challenging task. In addition, related properties such data races detection can be monitored using some methods used to check MC/DC, as good concurrency coverage increases a likelihood of catching concurrent-related bugs. To address the above challenges, existing strategies rely on intrusive instrumentation which is not recommended for safety critical software since it consumes valuable resources and can alter the behaviour of the system under test (SUT) if it remains in the released code.
To overcome the above challenges, this thesis introduces novel paradigms and tools for software testing based on traces and coverage analysis. Our aim is to analyse the MC/DC without instrumentation and to monitor data races with a lightweight instrumentation. In addition, we explore the applicability of MC/DC criterion on the design level models. Furthermore, we investigate new techniques for test cases generation satisfying MC/DC with the aim to increase the coverage.
The scientific contribution of this thesis is fourfold:
First, we propose an approach for measuring MC/DC without instrumentation. This has resulted in a tooling for MC/DC measurement and analysis based on the trace of an executing program. A static analysis is used to find conditional jumps in object code that correspond to conditions in the source code. With that information the assignments of the conditions during the execution of the code can be reconstructed by analyzing the trace. MC/DC is then evaluated and the covered/uncovered conditionals in the program can be identified. This approach is evaluated on C programs.
Secondly, we provide a non-intrusive tooling for data races detection using the continuous observation of embedded multicore systems (COEMS) technology through continuous online monitoring with lightweight instrumentation on a novel FPGA-based external platform for embedded multicore systems. It is used in combination with formal specifications in the high-level temporal stream-based specification language (TeSSLa), in which we encode a lockset-based algorithm to indicate potential race conditions. We show how to instantiate a TeSSLa template that is based on the Eraser algorithm, and present a corresponding light-weight instrumentation mechanism that emits the required observations to the FPGA with low overhead.
Thirdly, we investigated the applicability of MC/DC criterion on design level models, where specifically, we conducted a coverage analysis to Coloured Petri Nets (CPNs) models. We implement a library for CPN Tools and a post-processing tool for MC/DC coverage analysis of net inscriptions on a set of model executions and evaluate our approach on eleven larger publicly available CPN models.
In the fourth contribution, we propose a new and alternative strategy for test case generation satisfying MC/DC.We have implemented an algorithm for MC/DC test cases based on binary decision diagrams (BDDs) and evaluated on Traffic Alert and Collision Avoidance System (TCAS II) benchmarks. A performance evaluation with respect to the state-of-the art in the form of related work has been conducted.
Beskrivelse
Paper A is © IEEE. Papers B and C are reproduced with permission from Springer Nature.
In reference to IEEE copyrighted material which is used with permission in this thesis, the IEEE does not endorse any of Western Norway University of Applied Sciences’s products or services. Internal or personal use of this material is permitted. If interested in reprinting/republishing IEEE copyrighted material for advertising or promotional purposes or for creating new collective works for resale or redistribution, please go to http://www.ieee.org/publications_standards/publications/rights/rights_link.html to learn how to obtain a License from RightsLink.
Består av
Ahishakiye, F., Jakšić, S., Stolz, V., Lange, F. D., Schmitz, M., & Thoma, D. (2019). Non-intrusive MC/DC measurement based on traces. In Proceedings of the 13th International Symposium on Theoretical Aspects of Software Engineering (TASE) (pp. 86–92). IEEE. https://doi.org/10.1109/TASE.2019.00-15Ahishakiye, F., Jarabo, J. I. R., Pun, V. K. I., & Stolz, V. (2021). Hardware-assisted online data race detection. In E. Bartocci, Y. Falcone, & M. Leucker (Eds.), Formal methods in outer space: Essays dedicated to Klaus Havelund on the occasion of his 65th birthday (pp. 108–126). Springer International Publishing. https://doi.org/10.1007/978-3-030-87348-6_6
Ahishakiye, F., Requeno Jarabo, J. I., Kristensen, L. M., & Stolz, V. (2021). MC/DC test cases Generation based on BDDs. In S. Qin, J. Woodcock, & W. Zhang (Eds.), Dependable Software Engineering. Theories, Tools, and Applications (pp. 178–197). Springer International Publishing. https://doi.org/10.1007/978-3-030-91265-9_10
Ahishakiye, F., Jarabo, J. I. R., Kristensen, L. M., & Stolz, V. (2020). Coverage visualization and analysis of net inscriptions in coloured petri net models. Manuscript submitted for publication. https://doi.org/10.48550/arXiv.2005.09806