Contract-Based Verification of Timing Enforcers

Sagar Chaki, Dionisio de Niz, ACM SIGAda’s High Integrity Language Technology International Workshop on Model-Based Development and Contract-Based Programming (HILT), October 6-7, 2016, Pittsburgh, PA, USA.

Abstract: A timing enforcer not only allocates CPU cycles to threads but also uses timers to enforce time budgets. An approach for verifying safety properties of timing enforcers at the source code level is presented. We assume that the enforcer is implemented as a set of entry functions that are executed atomically on critical system-level events, such as arrival and departure of periodic jobs. The key idea is to express the safety property as an invariant, and prove that it is inductive across all the entry functions. The approach is validated by proving correctness of the enforcement of CPU cycle budgets for tasks by a mixed-criticality scheduler called ZSRM that is implemented in C. The inductiveness of the necessary ZSRM invariants is proved by expressing them as function contracts using the ACSL specification language, and verifying the contracts using the Frama-C tool.