Timing Anomalies in WCET Analysis

Timing anomalies are counter-intuitive behaviors observed in worst-case execution time (WCET) analysis. A key aspect of these anomalies is that a locally faster execution does not necessarily lead to a reduction in the overall program execution time. Therefore, WCET analysis must examine all possible execution states conservatively to ensure the safety of the analysis results, making the process extremely challenging. On the contrary, if it can be ensured that there are no timing anomalies in the program and platform to be analyzed, the number of states and the time required for WCET analysis can be significantly reduced. Consequently, addressing timing anomalies is a critical challenge in WCET analysis. However, despite more than 20 years of research, the academic community has not reached a unified definition and consensus on the problem of timing anomalies. This article reviews various perspectives from the literature since the concept of timing anomalies was first introduced. We classified these viewpoints based on their definitions and descriptions, and evaluates their respective strengths and weaknesses. Additionally, we investigated the causes of timing anomalies, identifying three main factors: scheduling strategies, cache behavior, and component interactions. Furthermore, we explored current research efforts aimed at detecting and eliminating timing anomalies, highlighting the issues and limitations of these approaches. we suggest that future research on timing anomalies should be integrated with WCET analysis methods to more effectively address these challenges.