Model Identification for WCET Analysis

Worst-Case Execution Time (WCET) analysis derives upper bounds for the execution times of programs. Such bounds are crucial when designing and verifying real-time systems. Static WCET analysis derives safe upper bounds. For complex hardware architectures the hardware modelling is still a challenge, leading to long analysis times and a risk of large WCET overestimation. Therefore, hybrid WCET analysis methods have appeared, where measurements are used to augment or replace the detailed low-level static WCET analysis. These methods do not in general yield a safe WCET estimate, but can still be appropriate in soft real-time systems where such WCET estimates are not crucial. In this paper we make two contributions. First, we develop a hybrid WCET analysis method, which uses regression to identify parameters in the common linear Implicit Path Enumeration Technique (IPET) model for WCET calculation. The method can use timing measurements of different granularity, including end-to-end measurements, which reduces the need for fine-grained timing measurement instrumentation. It uses a novel kind of regression, which guarantees that the identified model does not underestimate any observed execution times. Second, we initiate the development of an IPET-based theory for hybrid WCET analysis test coverage, and we formulate and prove a coverage criterion for the tests needed to identify a safe model.