Randomizing Parallel Real-Time Tasks:
A Scheduler-Oblivious Mechanism to Harness Security

We distinguish two classes of schedule-based attackers by their goal and mode of interaction: the Schedule-Intrusive Attacker and the Schedule-Non-Intrusive Attacker.

The Schedule-Intrusive Attacker cannot modify scheduling parameters (e.g., period, deadline, priority), but can execute arbitrary code within the compromised subtask’s execution window, gaining access to all resources available to that subtask. This enables false-data injection [37] or resource-contention attacks such as cache-based Denial-of-Service [6]. Additionally, we assume that nodes from other ADAG s cannot tamper with the ADAG generation code or its associated data. This can be ensured by executing the generation algorithm within a trusted component or under standard system-level isolation mechanisms (e.g., MMU/MPU-based memory protection). Finally, we assume the runtime enforces per-node execution budgets to mitigate WCET overruns and prevent DoS attacks through temporal isolation.

The Schedule-Non-Intrusive Attacker does not directly interfere with a victim’s execution but gathers critical information through side channels. For example, an attacker may passively observe power, electromagnetic, or WiFi fluctuations to infer sensitive data such as keystrokes or the type of computation performed [2], then use the extracted information to compromise other system components (e.g., using a recovered password to access a critical application) or reveal private data. This distinction matters because the two types rely on different attack vectors (as will be discussed in Section 4.2) and require separate metrics and mitigation strategies, both addressable by schedule randomization.

An attack vector is the means by which an attacker exploits a vulnerability. Schedule-based vectors fall into two categories: those that depend on the attacker’s execution relative to a victim subtask’s execution window, and those that depend on knowing the exact (absolute) time of the victim’s execution. Nasri et al. [25] identified the following four relative-timing vectors:

The Pincer vector demands that the attacker execute both before and after the victim, making it the hardest to exploit. Nasri et al. [25] adopted this definition possibly to expose weaknesses in existing defenses – showing that even a hard-to-launch attack can succeed. From a defensive standpoint, eliminating both the Anterior vector and Posterior vector automatically eliminates Pincer vector, so we adopt a strictly stronger variant that models an attacker who needs either (i.e., not necessarily both) relative-timing vectors:

These four vectors require the attacker to co-execute with the victim – running immediately before, after, or concurrently. They characterize the Schedule-Intrusive Attacker, which interferes with or probes the victim through shared resources. Since chip-level shared resources (last-level caches, memory buses) span all cores, we assume an attacker subtask on any core can target a victim on any other core whenever an attack vector’s relative timing relationship is satisfied.

A Schedule-Non-Intrusive Attacker, by contrast, remains passive and relies on timing alignment: it succeeds when the attacker can predict when a victim computation occurs, so that external observations (e.g., power, electromagnetic, or WiFi traces) can be sampled at the right moment. We model this as a fifth vector, the Absolute-Time-aware vector.

For example, if a Schedule-Non-Intrusive Attacker knows the exact time a decryption routine executes, it can sample power or thermal traces at that moment to infer the key length or the specific algorithm in use.

A Schedule-Intrusive Attacker requires both a victim and an attacker subtask on the same system (Section 4.2), and that any subtask may act maliciously toward any other – regardless of which core the subtasks execute on (Section 4.1). Recall that $\widehat{𝒯}$ is the set of all subtasks across all DAGs. Let ${\widehat{𝒯}}_{\mathrm{vul}}\subseteq \widehat{𝒯}$ and ${\widehat{𝒯}}_{\mathrm{att}}\subseteq \widehat{𝒯}$ denote the sets of vulnerable and attacker subtasks, respectively. Such information may be obtained using threat analysis and risk assessment [34]. We assume an attacker must execute within a bounded interval relative to the victim, called the vulnerable window, because attacks far from the victim’s execution are unlikely to succeed.

Let $A=\{$Anterior, Posterior, PincerOR, Concurrent $\}$ denote the set of attack vectors available to a Schedule-Intrusive Attacker (Section 4.2). Consider a subtask $\tau \in V_i$ of DAG task $G_i$, scheduled under the NPWC algorithm (Section 3), whose $j^{th}$ instance starts executing at time $t_1$ and finishes at $t_2$. The vulnerable window of this instance for attack vector $a\in A$ is the interval defined as follows:

where ${\mathrm{\Delta }}_1$ and ${\mathrm{\Delta }}_2$ are the durations of the windows immediately before and after subtask $\tau$’s execution, respectively, during which an attacker subtask can successfully launch an attack (Fig. 1(a)).

We assume that if the attacker does not execute within the vulnerable window, then no attack can be launched (Fig. 1(a)). Let ${𝒞}_a\left(\tau \right)$ denote the minimum time an attacker must execute within the vulnerable window of victim $\tau$ to launch an attack of type $a\in A$.

Because the tasks are periodic, the schedule repeats after a fixed repeating window¹¹1With a single task, the repeating window is just the period; with multiple tasks it is the hyperperiod. (equal to the least common multiple of all task periods when all are released simultaneously). An attacker can therefore study one repeating window to predict all future schedules when no randomization is performed. Next, we define threat and system threat event. Our metric System Threat is the probability of a system threat event.

Fig. 1(b) illustrates System Threat on a two-core schedule. Victim subtask ${\tau }_{\text{vul}}$ runs on core $c_1$ and is only vulnerable to a Posterior attack; its vulnerable window (red) follows each execution of ${\tau }_{\text{vul}}$. Two attacker subtasks ${\tau }_{\text{att}}$ and ${\tau }_{\text{att}}^{\prime }$ run on core $c_2$ across three repeating windows with different (i.e., randomized) start times. In Repeating Window 1, ${\tau }_{\text{att}}^{\prime }$ overlaps with the vulnerable window, producing a threat $\mathrm{th}({\tau }_{\text{att}}^{\prime },{\tau }_{\text{vul}},\text{Posterior})$; a system threat event $ℰ$ therefore occurs (✓). In Repeating Window 2, neither attacker overlaps the window, so no system threat event occurs ($\times$). In Repeating Window 3, both ${\tau }_{\text{att}}$ and ${\tau }_{\text{att}}^{\prime }$ overlap the window – two individual threats – but these together still constitute a single system threat event (✓), since $ℰ$ is defined as the union of all threats within one repeating window. Overall, 2 out of 3 repeating windows contain a system threat event, giving $\mathrm{TH}({\widehat{𝒯}}_{\mathrm{att}},{\widehat{𝒯}}_{\mathrm{vul}})=2/3$.

System Threat captures whether an attacker subtask overlaps a victim’s vulnerable window but does not address vulnerability to the Absolute-Time-aware vector. An Absolute-Time-aware vector succeeds when an attacker can predict when a subtask executes, so the defense must make execution timing hard to predict.

We propose a second metric, Task Distribution Entropy, a Shannon-style [30] entropy measuring the slot uncertainty of a given subtask – how the start time of the subtask varies across the time slots within the period of the task. This task-oriented perspective contrasts with the Schedule Entropy of TaskShuffler [36], which is slot-oriented: for each time slot, [36] measures how many different subtasks could execute in that time slot. As we will show in Section 5.3, the task-oriented view provides a more accurate evaluation of security.

Task Distribution Entropy quantifies a subtask’s temporal uncertainty. If a subtask tends to start in the same time slot $t_j$ relative to the start of the period, the probability $p_{i,j}$ dominates and $H_{\text{dist}}\left({\tau }_i\right)$ is low, making the subtask easy to predict. Conversely, higher $H_{\text{dist}}\left({\tau }_i\right)$ means start times are spread more uniformly, making an Absolute-Time-aware vector harder.

TaskShuffler [36] uses a slot-oriented view of uncertainty: for each time slot, it asks which subtask could execute here? We instead use a task-oriented view: for each subtask, we ask when could this subtask execute (i.e., how its start time is distributed across the time slots within the period of the task)? We compare the two approaches with a simple example.

Consider a DAG $G$ with a large number of subtasks, $N=|V|\gg 1$, and a large period $T$. In each period, the start time of each subtask is uniformly random (hard to predict) except for one subtask ${\tau }_i$ (easy to predict). The subtask ${\tau }_i$ executes with equal chance in the $m^{th}$ or $n^{th}$ time slots in every period (as shown in Fig. 2).

Note that Eq. (2) computes the entropy of a subtask over different time slots, whereas Eq. (3) computes the entropy of a time slot over different subtasks. Applying Eq. (3) to the example in Fig. 2, all subtasks other than ${\tau }_i$ have an equal probability of $1/(N-1)$ of appearing in any slot other than $m$ and $n$. The slot entropy for these slots is $H_{\mathrm{\Gamma }}(S_t)=-(N-1)\times \frac{1}{N-1}{\log }_2\frac{1}{N-1}={\log }_2(N-1)$. For slots $m$ and $n$, subtask ${\tau }_i$ executes with probability $p_{i,m}=p_{i,n}=0.5$. The remaining $0.5$ probability is distributed equally among the other $(N-1)$ subtasks, giving each a probability of $0.5/(N-1)$. The entropy is thus:

By contrast, our proposed Eq. (2) yields $H_{\text{dist}}\left({\tau }_i\right)=-2\times 0.5{\log }_{2}0.5=1$, which directly reveals ${\tau }_i$’s high predictability – a fact that the slot-oriented schedule entropy obscures. The extension of TaskShuffler [35] takes the minimum slot entropy as its system-level metric;³³3The original TaskShuffler [36] sums the entropy for all slots as the system security evaluation, which suffers even more from the same limitation. for this example, that minimum is $H_{\mathrm{\Gamma }}(S_m)=1+0.5{\log }_2(N-1)$, which grows logarithmically with $N$ and far exceeds $1$ when $N$ is large. By contrast, $H_{\text{dist}}\left({\tau }_i\right)=1$ is constant regardless of $N$, correctly indicating that the execution time slot of ${\tau }_i$ is nearly deterministic.

Task Distribution Entropy thus evaluates security on a subtask-by-subtask basis, leaving it to the system designer to determine how to assess the overall system’s security (e.g., via the average or minimum Task Distribution Entropy across all subtasks). The example above exposes two limitations of schedule entropy [36]: (i) it is slot-oriented rather than task-oriented, so high entropy in some slots can mask the vulnerability of specific subtasks; and (ii) aggregating into an “overall system entropy” overstates security, because high entropy in one part of the schedule provides little protection for a more predictable part. In practice, an attacker is more likely to target individual subtasks rather than the entire system at once, so an aggregated entropy metric tends to overestimate security.

CDR converts an original DAG $G_i$ into an ADAG ${\widehat{G}}_i$ through two phases.

Having established the mechanisms for dependency and temporal augmentation, we now address the framework’s expressive power: Can the ADAG model represent any desired execution behavior? An execution timeline (or simply timeline) is a concrete assignment of start times to subtasks consistent with non-preemptive scheduling on $m$ cores, whether work-conserving or not. This section proves a sufficiency result: for any valid timeline, there exists a choice of added edges $E_{\mathrm{\Delta }}$ and fake subtasks’ WCET s that compels the NPWC scheduler to exactly reproduce the timeline. Let $S$ be a schedule for a DAG $G=(V,E)$ on $m$ identical cores, mapping every subtask to a start time.

This definition captures all possible non-preemptive schedules, whether work-conserving or not: the only restrictions are resource capacity ($m$ cores) and precedence – a core may idle even if ready subtasks exist. We now state a theorem confirming that the ADAG model can express every non-preemptive schedule. Its implications are discussed after the proof.

At runtime, fake subtasks receive random execution times based on the spare processing capacity (i.e., available slack) before the deadline. The random execution time for all the fake subtasks is determined based on schedulability analysis of the DAG. The question is: for a given number of dedicated cores $m$, how large can the fake-work volume $\mathrm{vol}(V^F)$ be while keeping ${\widehat{G}}_i$ schedulable under NPWC scheduler? We use Graham’s classic bound [13] to determine the random execution time of the subtasks.

Transforming $G_i$ into ${\widehat{G}}_i$ increases volume and potentially the critical path. We adapt Graham’s bound to the ADAG model as follows:

Dependency augmentation randomly adds precedence edges to constrain concurrency, reducing exploitable overlaps (in particular, Concurrent vectors). Adding edges does not change the randomization budget $m\cdot D-\mathrm{vol}(G)$ (the right-hand side of Eq. (5)), but can increase the critical-path length $\mathrm{len}(G^{\prime })$ of the intermediate graph, consuming a larger share of that budget on the left-hand side. Accordingly, our augmentation mechanism admits an edge only if it (i) does not create a cycle and (ii) preserves feasibility under Graham’s bound.

Algo. 2 generates a randomized valid dependency extension by sampling candidate edges with probability $p$. An edge $(u,v)$ is safe if adding it to the current graph keeps the graph acyclic and satisfies Graham’s bound, i.e., (i) it does not introduce a directed cycle (equivalently, there is no existing path $v\rightsquigarrow u$ before adding $(u,v)$), and (ii) the intermediate graph still satisfies Eq. (5) for the given $(m,D)$.

The cycle check $\text{PathExists}(v,u,(V,E^{\prime }))$ is a standard reachability query. We maintain the transitive closure of the edge set incrementally, reducing each check to a constant-time set membership test; maintaining this closure across $O({|V|}^2)$ candidate edges yields $O({|V|}^3)$ worst-case complexity.

An edge $(u,v)$ is added only if no path from $v$ to $u$ exists in the current graph (line 7), preventing cycles, and only if the intermediate graph still satisfies Graham’s bound (line 9), maintaining schedulability after every addition. The parameter $p$ controls the density of augmentation: a higher $p$ samples more candidate edges, producing a more constrained graph with less exploitable concurrency. The resulting intermediate DAG $G^{\prime }$ (e.g., the dashed edge $E_{\mathrm{\Delta }}$ in Stage 2 of Fig. 3) can therefore be safely passed to Phase 2, where runtime fake-subtask budgets are sampled within the remaining schedulability margin.

We now describe how to assign random WCET s to fake subtasks at runtime while preserving schedulability.

Directly using Eq. (5) to randomly assign fake-subtask execution time $\mathrm{vol}(V^F)$ is problematic because $\mathrm{len}({\widehat{G}}_i)$ depends on the assigned fake WCET s: different assignments can change the critical path from one branch to another. Fig. 4 illustrates this: the top path has length $(3+8+3)=14$ in the original DAG (ignoring the square-shaped fake subtasks), but in the ADAG the bottom path has length $(3+3+9+1+3+3)=22$ and becomes the longest. We address this circular dependency via the following lemma.

We randomly generated all DAG s using the method of Melani et al. [22]. Generation starts from a root subtask and repeatedly expands each non-terminal subtask by sampling a set of successors. Each successor is designated terminal or non-terminal with a preset probability, and non-terminal successors are expanded recursively up to a maximum depth of 3.

We consider four Schedule-Intrusive Attacker vectors: Anterior, Posterior, PincerOR, and Concurrent. Unless otherwise specified, the vulnerable-window length is set to 20% of the victim subtask’s WCET. The minimum attacker execution time (${𝒞}_a\left({\tau }_{\mathrm{vul}}\right)$) is set to 10% of the corresponding vulnerable-window length. Section 8.2 reports how varying these parameters affects System Threat.

We evaluate configurations using System Threat (Eq. (1)) and Task Distribution Entropy (Eq. (2)), estimated via Monte Carlo simulation. Each run produces one randomized schedule for a full hyperperiod. System Threat is estimated as the fraction of total runs that contain at least one system threat event (Def. 5.3). We use 10,000 runs per DAG for System Threat and 5,000 runs for Task Distribution Entropy, yielding a relative standard error below $0.3\%$.

We first investigate how attack parameters affect System Threat using 100 DAG tasks ($U_i\in [0.1,5.0]$). We swept two parameters in 10% increments: (1) Vulnerable window size: from 10% to 100% of the victim subtask’s WCET, and (2) Required attacker time: from 10% to 100% of the vulnerable window.

As Fig. 6 shows, System Threat increases with larger vulnerable windows and decreases with longer required attacker execution times. Based on these trends, we fix the vulnerable window at 20% and the required attacker time at 10% for all subsequent experiments.

We evaluate multi-task systems under federated scheduling. We generated 200 task sets, each containing a random number of DAG s, with total utilization up to 15.0.

The hyperperiod (the least common multiple of all task periods) can grow very large for random period sets – in ours, the largest exceeds ${10}^{40}$ – making full-hyperperiod simulation infeasible. We therefore scale each task set to a bounded hyperperiod $H^{\star }$ chosen from a predefined set of HCN [26]: we select the HCN closest to the original hyperperiod, then for each task ${\tau }_i$ replace its period with the divisor of $H^{\star }$ closest to $T_i$. Subtask WCET s are scaled by ${\alpha }_i=T_i^{\prime }/T_i$, where $T_i^{\prime }$ is the new period assigned to task ${\tau }_i$ and the fractional remainders are then redistributed greedily (largest remainder first) to minimize utilization error. Fig. 6 confirms that this scaling introduces negligible utilization distortion even when compressing hyperperiods from ${10}^{40}$ down to at most 45,360.

We apply both CDR phases: Schedulability-Constrained Edge Augmentation (Dep. Aug.; Algo. 2) followed by FRESH. Core availability is expressed as a core multiplier $\kappa =M/M_{\min }$, where $M$ is the available core count and $M_{\min }$ the minimum satisfying the federated schedulability condition (Eq. (8)); $\kappa =1$ is minimal provisioning and larger $\kappa$ indicates more spare capacity. Let $vp$ denote the fraction of subtasks designated as vulnerable and $ap$ the fraction of subtasks designated as attackers.

Fig. 8 shows System Threat reduction for varying $vp$ and $ap$: threat decreases consistently across all configurations, with larger reductions when fewer subtasks are vulnerable or when the attacker fraction is small. Fig. 8 (left) plots threat reduction versus the core multiplier $\kappa$. The results exhibit a non-monotonic dependence on $\kappa$: for larger $p$ (more aggressive dependency augmentation), threat reduction can decrease as $\kappa$ grows from $1$ toward $\approx 2$ before increasing at higher $\kappa$. The right panel of Fig. 8 aggregates threat reduction over all possible attacks for varying values of $p$. Increasing $p$ enforces more serialization (reducing exploitable concurrency) but also amplifies non-monotonic behavior, analyzed in Section 8.4.

Fig. 9 shows anomalies – cases where the ADAG exhibits higher threat than the original DAG. These (red points) constitute only about 8% of task sets and the increase in threat for each such task is relatively small (the vertical distance of each red dot from $y=x$ is small). This aligns with Nasri et al.’s [25] observation that randomization can open new attack vectors. An offline screening step that retains only the candidate ADAG s not raising threat would mitigate these regressions, a direction we leave for future work.

To investigate the non-monotonic behavior observed in multi-task settings, we isolate single-DAG systems, decoupling inter-task attack scenarios from the intrinsic properties of the task graph. We generated 400 DAG tasks with $U_i\in [1.5,\mathrm{\hspace{0.17em}6.0}]$ and varied the core multiplier ($\kappa$) from 1.0 to 2.0.

Fig. 11 plots System Threat against the core multiplier. Threat follows a reverse-U-shaped curve, highest at intermediate core counts and lowest at the extremes of the core range. Equivalently, threat reduction peaks when the system is either tightly or generously provisioned. This non-monotonic trend reveals that allocating more cores does not necessarily improve security. The counter-intuitive finding stems from two competing effects, which we term intrinsic and extrinsic security:

1. 1.

   Intrinsic security arises from limited parallelism. Tight core budgets force more sequential execution, reducing attacker–victim overlap. Adding cores increases concurrency and opens more vulnerable windows, eroding this inherent protection.

2. 2.

   Extrinsic security arises from randomization. The randomization budget grows with the number of cores $m$. At low core counts, even small budgets effectively shift execution windows because parallelism is limited. As $m$ increases moderately, the loss of intrinsic security outpaces the randomization gains. At high core counts, the randomization budget becomes large enough to dominate, restoring threat reduction.

These two mechanisms explain the multi-task results (Section 8.3). Dependency edges (Fig. 8) strengthen intrinsic security by enforcing serialization within each DAG, but increased concurrency as core count grows gradually offsets this effect, reproducing the non-monotonic trend. Threat reduction is higher in single-task systems because randomization directly separates attacker–victim windows, whereas independent per-task randomization limits the ability to reduce cross-task overlap.

Using the 400 DAGs from Section 8.4, this section presents the runtime overhead of ADAG generation, the total time spent by the NPWC scheduler (i.e., scheduling overhead) in making all the scheduling decisions in a period of an ADAG, and its comparison to that of the original DAG. We performed time measurements using the std::chrono::steady_clock (monotonic, nanosecond-resolution) wrapped in Resource Acquisition Is Initialization (RAII) scoped timers around each ADAG generation phase and the NPWC scheduler in our simulator. For this set of experiments, we used a mid-range desktop AMD Ryzen 5 3600 CPU with threads pinned (OMP_PROC_BIND=close, OMP_PLACES=cores). Each point in the plots of Fig. 12 represents the median for 100 trials, with the relative standard error kept below $0.4\%$.

We measured (the left subfigure in Fig. 12) the time taken by the three individual phases of ADAG generation: (1) fake-subtask insertion, Algo. 1, (2) Dependency Augmentation, Algo. 2, and (3) Temporal Augmentation under FRESH, Algo. 3. We set the extra edge probability $p=0.3$ and core multiplier $\kappa =1$. The total time by all three phases for each release of a DAG has median $232\mu \text{s}$ with a 99th percentile below $595\mu \text{s}$, dominated by FRESH (median $108\mu \text{s}$), then fake-subtask insertion (median $55\mu \text{s}$), and the edge augmentation (median $69\mu \text{s}$ at $p=0.3$, shrinking sharply as fewer extra edges are added at smaller $p$). The overhead of ADAG generation thus stays in the few-hundred-microsecond range.

The total overhead of the NPWC scheduler in making all the scheduling decisions (e.g., checking predecessors’ completion, deciding which ready nodes to dispatch for execution) in one period is measured (the middle sub-figure in Fig. 12) for the original DAG, for the ADAG with no dependency augmentation ($p=0$) and also with both temporal and dependency augmentations ($p=0.3$). The scheduling overhead of NPWC exhibits no noticeable variation with or without dependency augmentation; the curves for $p=0$ and $p=0.3$ in the middle subfigure nearly overlap. The difference in overhead for scheduling ADAG in comparison to the original DAG is mainly due to temporal augmentation; however, the absolute per-period total scheduling overhead stays in tens to hundreds of microseconds.

To quantify the additional scheduling overhead relative to the baseline (i.e., unaugmented DAG), we compute the ratio of the scheduling overhead of the ADAG to that of the original DAG, varying the extra-edge probability $p\in \{0.1,0.2,0.3\}$ across core multipliers $\kappa \in \{1,1.5,2,3,4\}$ (right subfigure of Fig. 12). The NPWC scheduler incurs approximately $2.5\times$ higher overhead when scheduling ADAG s compared to the original DAG across the entire range of $p$. This increase is primarily attributable to the doubling of the number of vertices in the ADAG (i.e., total $2|V|$ nodes in an ADAG). The contribution of dependency augmentation is, as discussed above, quite minor.

CDR reduces System Threat in both single- and multi-task systems, at sub-millisecond per-release randomization cost and an approximately $2.5\times$ scheduler overhead: dependency augmentation provides intrinsic security through serialization, while temporal augmentation provides extrinsic security via randomization. Resource provisioning exhibits a non-obvious trade-off – intermediate core counts may reduce randomization benefits, so systems should be either tightly or generously provisioned. In multi-task environments, per-task randomization alone does not eliminate cross-task leakage through shared microarchitectural resources; combining it with spatial isolation (e.g., cache partitioning or bandwidth throttling) would further strengthen security.