Evolutionary Testing for Timing Analysis of Parallel Embedded Software

Embedded real-time software must be verified for their timing correctness where knowledge about the Worst-Case Execution Time (WCET) is the building block of such verification. The WCET of embedded software can be estimated using either static analysis or measurement-based analysis. Previously, the WCET research assumes sequential code running on single-core platforms. However, as computation is steadily moving towards using a combination of parallel programming and multicore hardware, necessary research in WCET analysis should be taken into account. While focusing on the measurement-based analysis, the aim of this research is to find the WCET of parallel embedded software by generating the test-data using search algorithms. In this paper, the use of a meta-heuristic optimizing search technique-Genetic Algorithm is demonstrated, to automatically generate such test-data. The search-based optimization used yielded the input vectors of the parallel embedded software that cause maximal execution times. These execution times can be either the WCET of the parallel embedded software or very close to it. The process was evaluated in terms of its scalability, safety and applicability. The generated test-data showed improvements over randomly generated data.