WCET analysis methods: Pitfalls and challenges on their trustworthiness

Abstract

In the last three decades a number of methods have been devised to find upper-bounds for the execution time of critical tasks in time-critical systems. Most of such methods aim to compute Worst-Case Execution Time (WCET) estimates, which can be used as trustworthy upper-bounds for the execution time that the analysed programs will ever take during operation. The range of analysis approaches used include static, measurement-based and probabilistic methods, as well as hybrid combinations of them. Each of those approaches delivers its results on the assumption that certain hypotheses hold on the timing behaviour of the system as well that the user is able to provide the needed input information. Often enough the trustworthiness of those methods is only adjudged on the basis of the soundness of the method itself. However, trustworthiness rests a great deal also on the viability of the assumptions that the method makes on the system and on the user's ability, and on the extent to which those assumptions hold in practice. This paper discusses the hypotheses on which the major state-of-the-art timing analyses methods rely, identifying pitfalls and challenges that cause uncertainty and reduce confidence on the computed WCET estimates. While identifying weaknesses, this paper does not wish to discredit any method but rather to increase awareness on their limitations and enable an informed selection of the technique that best fits the user needs.