EDiFy: An Execution time Distribution Finder

Embedded real-time systems are subjected to stringent timing constraints. Analysing their timing behaviour is therefore of great significance. So far, research on the timing behaviour of real-time systems has been primarily focused on finding out what happens in the worst-case (i.e., finding the worst case execution time, or WCET). While a WCET estimate can be used to verify that a system is able to meet deadlines, it does not contain any further information about how the system behaves most of the time. An execution time distribution does contain this information and can provide useful insights regarding the timing behaviour of a system. In this paper, we present EDiFy, a measurement-based framework that derives execution time distributions by exhaustive evaluation of program inputs. We overcome the scalability and state-space explosion problem by i) using static analysis to reduce the input space and ii) using an anytime algorithm which allows deriving a precise approximation on the execution time distribution. We exemplify EDiFy on several benchmarks from the TACLeBench and EEMBC benchmark suites, and show that the anytime algorithm provides precise estimates already after a short time