Software randomization of execution times for avionic systems

Among the wide range of research work we've done during the past, one of the "most blue sky" areas has been in the area of probabilistic timing analysis (PTA), where specific hardware support randomizes sources of execution time variability, making it possible to produce accurate statistical predictions of worst-case execution probabilities, see our PROXIMA research project and our PROARTIS research project.

When done with a hardware platform customized to randomize execution time variability, this approach has been shown to be effective. Of course, there are significant commercial challenges to introducing new, specific hardware even into those industries which have a critical need for worst-case execution time.

Within the PROXIMA project, we are also considering the effect of software-only randomization. A recent paper ¹ demonstrates the viability of this approach through an avionics case study based on a single-core IMA (Integrated Modular Avionics) concept.

In this paper, systemic timing issues are avoided by randomly locating memory objects, which helps to avoid timing anomalies (for example, pathological cache effects, where the layout guarantees a cache miss every time a variable is accessed). The randomization was achieved through a specially modified compiler, and a run-time system.

Using a modified version of RapiTime, the case study identified a WCET in the order of 140k CPU cycles, which would only be exceeded one time in 10¹⁵ (which would be acceptable even for DO-178C Level A systems).

This was compared with the longest observed execution time of a non-randomized version of the same software. In line with industrial practice, we added 20% to this to give a WCET estimate. The results are shown in the graph below.

(Click image to enlarge)

Although this brief summary can only scratch the surface, more information is available: if you would like to get a copy the actual paper, you can get in touch with us here

¹ F. Wartel, Kosmidis, L., Gogonel, A., Baldovin, A., Stephenson, Z., Triquet, B., Quinones, E., Lo, C., Mezzetti, E., Broster, I., Abella, J., Cucu-Grosjean, L., Vardanega, T., and Cazorla, F. J., “Timing Analysis of an Avionics Case Study on Complex Hardware/Software Platforms”, in DATE, 2015.