On Scheduler Side-Channels in Dynamic-Priority Real-Time Systems

Chien-Ying Chen, Sibin Mohan, Rodolfo Pellizzoni, Rakesh B. BobbaarXiv 2020 · arXiv

Introduction

Real-Time Systems (RTS) are the backbone of safety-critical infrastructure, from automotive braking systems to medical implants. These systems rely on schedulers to ensure tasks meet strict deadlines. Historically, scheduler side-channels have allowed unprivileged "observer" tasks to infer the execution patterns of high-priority "victim" tasks. However, existing attacks like ScheduLeak were designed for Fixed-Priority (FP) systems. It was widely believed that Dynamic-Priority systems, such as Earliest Deadline First (EDF), were inherently more resistant to such reconnaissance due to their "priority-flipping" nature.

The Challenge of Dynamic Priorities

In EDF scheduling, task priorities are not static; they change at runtime based on absolute deadlines. This dynamism breaks the "persistent priority" assumption required by previous attacks. In an EDF system, an observer task might have a higher priority than the victim at one moment and a lower priority the next. This makes it difficult to determine if a delay in the observer's execution is due to preemption by the victim or simply the observer's own scheduling parameters.

The DyPS Methodology

To overcome these challenges, researchers developed DyPS (Dynamic-Priority ScheduLeak). DyPS is a four-step algorithm designed to handle the uncertainty of dynamic priorities by identifying "safe" observation windows.

The four main steps of the DyPS attack algorithm.
  1. Observer Phase Reconstruction ($\phi_o$): The observer first establishes its own arrival "ground truth" by analyzing multiple start times to find the earliest possible wake-up point.
  2. Identifying Valid Execution Intervals: DyPS filters out intervals where the observer might have had a higher priority than the victim. Only intervals where the victim is guaranteed to have higher priority (if it arrives) are used for inference.
  3. Candidate Computation: By analyzing preemption points within these valid windows, the algorithm generates potential arrival times for the victim.
  4. Victim Phase Inference: Using a "schedule ladder diagram," DyPS finds the most consistent arrival pattern across multiple periods to pinpoint the victim's phase ($\phi_v$).

Evaluation and Results

The effectiveness of DyPS was evaluated using 6,000 synthetic task sets generated via the UUniFast algorithm. These sets included realistic factors like execution jitter and sporadic task arrivals.

The results demonstrate a significant leap in precision over previous methods. While ScheduLeak struggles in EDF environments, achieving a mean precision of only 0.54, DyPS reaches a precision of 0.978.

Inference precision of DyPS vs. ScheduLeak as a function of attack duration.

As shown in the figure, DyPS quickly converges to near-perfect precision within an observation period of approximately 10x the Least Common Multiple (LCM) of the task periods. The attack remains robust even under high system utilization (up to 90%) and increasing task counts.

Discussion and Future Work

DyPS effectively debunks the notion that EDF scheduling provides "security through complexity." However, certain defenses remain possible. For instance, perfectly harmonic task phases and periods can create constant delays that degrade attack precision.

Future research will likely focus on extending these attacks to multi-core systems, where parallel execution introduces new complexities, and developing dedicated "schedule randomization" countermeasures to protect EDF-based real-time systems from timing-based side-channel leaks.

Summary updated

Abstract

While the existence of scheduler side-channels has been demonstrated recently for fixed-priority real-time systems (RTS), there have been no similar explorations for dynamic-priority systems. The dynamic nature of such scheduling algorithms, e.g., EDF, poses a significant challenge in this regard. In this paper we demonstrate that side-channels exist in dynamic priority real-time systems. Using this side-channel, our proposed DyPS algorithm is able to effectively infer, with high precision, critical task information from the vantage point of an unprivileged (user space) task. Apart from demonstrating the effectiveness of DyPS, we also explore the various factors that impact such attack algorithms using a large number of synthetic task sets. We also compare against the state-of-the-art and demonstrate that our proposed DyPS algorithms outperform the ScheduLeak algorithms in attacking the EDF RTS.
BibTeX
@misc{chen2020scheduler,
  author = {Chien-Ying Chen and Sibin Mohan and Rodolfo Pellizzoni and Rakesh B. Bobba},
  title = {{On Scheduler Side-Channels in Dynamic-Priority Real-Time Systems}},
  year = {2020},
  eprint = {2001.06519},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2001.06519},
}

Loading related content...

Figure