Scalable and precise estimation and debugging of the worst-case execution time for analysis-friendly processors: a comeback of model checking

Estimating the worst-case execution time (WCET) of an application is an essential step in the context of developing real-time or safety-critical software, but it is also a complex and error-prone process. Conventional approaches require at least some manual inputs from the user, such as loop bounds and infeasible path information, which are hard to obtain and can lead to unsafe results if they are incorrect. This is aggravated by the lack of a comprehensive explanation of the estimate, i.e., a specific trace showing how the estimated WCET was reached. In this article, we revisit the use of Model Checking as an analysis technique for WCET estimation. Model Checking has been explored before, but did not prevail due to its poor scalability. We address this by shifting the analysis to the source code level, where code transformations can be applied that retain the timing behavior, but reduce the complexity. Furthermore, we show how Model Checking enables the reconstruction of a concrete trace of the WCET path, which can be examined in a debugger environment. A prerequisite for our approach is the use of analysis-friendly processors. This is in line with recent calls by the research community, since modern processors have reached a complexity that refutes timing analysis. Our experiments show that fast and precise estimates can be achieved with Model Checking, that its scalability can even exceed current approaches, and that new opportunities arise in the direction of “timing debugging”.