Information Restricted Scheduling for Concurrent Systems

15 concepts8 papers1 proposal

In concurrent systems, multiple processes run in parallel, and their execution steps are interleaved. To formally model and verify these systems, computer scientists rely on a scheduler (or oracle)—a mechanism that resolves non-determinism by deciding exactly which process takes the next step.

While this abstraction works well for verifying correctness, it introduces a severe vulnerability for security and privacy. Traditional formal models often assume an omniscient scheduler that possesses global visibility into the entire system state, including private variables and cryptographic secrets. If a system's execution path branches based on a secret input, an omniscient scheduler can observe that secret and alter the execution order accordingly. An external observer, watching only the timing or sequence of public events, can then infer the internal secret. This phenomenon is known as scheduler-driven information leakage.

The Threat of Scheduler Clairvoyance

Why do standard concurrent models fail to guarantee privacy? The root of the problem lies in how non-determinism is resolved. Traditional verification frameworks frequently treat the scheduler as a neutral or cooperative entity. However, as Alvim et al. point out, assuming a benign scheduler creates a dangerous blind spot. If an attacker can influence scheduling behavior or if the scheduler is inherently "clairvoyant"—meaning its decisions depend on hidden internal states—it creates a covert channel that leaks data through process interleaving.

[Secret State: Vote = Yes] ---> [Scheduler Sees Secret] ---> [Schedule Process A First] ---> Observer infers "Yes"
[Secret State: Vote = No ] ---> [Scheduler Sees Secret] ---> [Schedule Process B First] ---> Observer infers "No"

When a protocol contains operators that branch based on secret inputs, it becomes highly vulnerable. Braun et al. demonstrate that an omniscient scheduler can exploit these secret-dependent choices to manipulate protocol execution, effectively transforming internal non-determinism into an observable side channel.

To evaluate security properties like anonymity or oblivious transfer robustly, researchers must adopt a worst-case perspective. For example, Bérard et al. model the scheduler as an active ally to an external adversary. By calculating the maximum possible probability of a secret being revealed across all possible scheduling strategies, they quantify the absolute upper bound of information disclosure. Even when a scheduler is deterministic and merely tries to optimize performance by keeping the system busy, it can introduce vulnerabilities; Gong et al. show that deterministic, work-conserving schedulers inherently create timing side channels that leak sensitive user job arrival patterns.

Blinding the Scheduler via Epistemic Restrictions

To eliminate scheduler-mediated leakage, we must break the statistical dependency between internal secrets and scheduling choices. If the scheduler cannot see the secret, its decisions cannot correlate with the secret, and the resulting execution trace will reveal nothing to an observer.

A prominent strategy for achieving this is to enforce information-restricted scheduling using game theory and epistemic logic. Chatzikokolakis et al. and Knight et al. reframe concurrent execution as a game where the scheduler is an agent restricted to introspective strategies. Instead of granting the scheduler global visibility, it is restricted to knowing only its own history of choices and the moves immediately available to it.

[Internal Secret State] --(Hidden)--> [Introspective Scheduler] ---> [Uncorrelated Execution Order]

Because the scheduler's visibility boundaries prevent it from accessing private process states, it cannot optimize or alter execution sequences based on secrets, neutralizing the omniscient adversary threat.

A parallel approach involves making internal probabilistic choices fundamentally invisible to the execution manager. Palamidessi et al. propose a process calculus where schedulers are treated as explicit syntactic processes with restricted interaction rules. This setup ensures that when a process makes an internal random choice—such as choosing a random routing path to maintain anonymity—that choice is completely hidden from the scheduler, preventing the scheduler from adapting its strategy to expose the protocol's secret.

Formal Verification and Language Design

Enforcing information-restricted scheduling allows designers to mathematically prove that a system satisfies information-hiding properties. To verify these properties without over-constraining the system, Kramer et al. introduced a specialized modal logic called the doxastic $\mu$-calculus with error control ($D\muCEC$). By separating an agent's subjective belief from objective probabilistic truth, this logic allows developers to formally verify protocols against a restricted class of total schedulers, ensuring that scheduling choices do not inadvertently expose secrets during execution.

These theoretical insights also directly influence language design and runtime environments. When retrofitting existing programming languages with dynamic Information Flow Control (IFC), the choice of the underlying scheduling policy dictates what kind of security guarantees can be achieved. As Heule et al. demonstrated, a round-robin scheduler naturally satisfies Termination Sensitive Non-Interference (TSNI), because its strict rotation prevents execution time from being altered by secret data. Conversely, a sequential scheduler satisfies the weaker Termination Insensitive Non-Interference (TINI).

By moving away from the unrealistic assumption of omniscient scheduling and designing runtimes that restrict execution visibility, concurrent systems can achieve provable, compositionally sound privacy guarantees.

Key Foundational Work

Compositional Methods for Information-Hiding (2008) — contributed 3 concept elements to this direction.
Epistemic Strategies and Games on Concurrent Processes (2009) — contributed 3 concept elements to this direction.
A quantitative doxastic logic for probabilistic processes and applications to information-hiding (2009) — contributed 3 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_scheduler_driven_information_leakage_0c744e5f,
  title = {scheduler-driven information leakage},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/scheduler-driven-information-leakage/rdr_0c744e5fbf7e421b8a37daf052a28e43},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-21},
}

This exact version (version 1, frozen text):

@misc{lacuna_scheduler_driven_information_leakage_0c744e5f_v1,
  title = {scheduler-driven information leakage},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/scheduler-driven-information-leakage/rdr_0c744e5fbf7e421b8a37daf052a28e43/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-21},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake