Trustworthy Systems

High-assurance timing analysis for a high-assurance real-time OS

Authors

Thomas Sewell, Felix Kam and Gernot Heiser

DATA61

UNSW Sydney

Abstract

Worst-case execution time (WCET) analysis of real-time code needs to be performed on the executable binary code for soundness. Obtaining tight WCET bounds requires determination of loop bounds and elimination of infeasible paths. The binary code, however, lacks information necessary to determine these bounds. This information is usually provided through manual intervention, or preserved in the binary by a specially modified compiler. We propose an alternative approach, using an existing translation-validation framework, to enable high-assurance, automatic determination of loop bounds and infeasible paths. We show that this approach automatically determines all loop bounds and many (possibly all) infeasible paths in the seL4 microkernel, as well as in standard WCET benchmarks which are in the language subset of our C parser. We also design and validate an improvement to the seL4 implementation, which permits a key part of the kernel's API to be available to users in a real-time setting.

BibTeX Entry

  @article{Sewell_KH_17,
    author           = {Sewell, Thomas and Kam, Felix and Heiser, Gernot},
    date             = {2017-9-1},
    doi              = {https://doi.org/10.1007/s11241-017-9286-3},
    issue            = {5},
    journal          = {Real-Time Systems},
    keywords         = {real-time, worst-case execution time, formal verification, {seL4}, {OS}, timing},
    month            = sep,
    pages            = {812-853},
    paperurl         = {https://trustworthy.systems/publications/full_text/Sewell_KH_17.pdf},
    publisher        = {Springer},
    title            = {High-Assurance Timing Analysis for a High-Assurance Real-Time {OS}},
    volume           = {53},
    year             = {2017}
  }

Download