Worst-Case Execution Time Analysis for Parallel Run-Time Monitoring

The increasing safety-critical role of real-time systems requires increased attention to their security and reliability. Several recent studies have shown that parallel run-time monitoring of programs can significantly improve the security and reliability of computing systems. However, these techniques cannot be applied to real-time systems without first estimating their impact on worst-case execution time (WCET). In this paper, we present a method for determining the impact of parallel monitoring on WCET using a mixed integer linear programming (MILP) formulation. We use our method to estimate the WCET for seven benchmark programs and two possible monitoring techniques. This estimate is compared against observed execution times from simulation and an upper bound based on sequential monitoring. The results show that our method estimates a WCET within 71% of worst-case observed execution times and up to 74% lower than the sequential bound.