Infiltrating the Sky: Data Delay and Overflow Attacks in Earth Observation Constellations

As EO satellites continuously scan Earth’s surface, they generate vast monitoring data that must be transmitted to the ground for processing and analysis. However, several factors hinder efficient satellite data downlinking. Firstly, the geographical requirements and high costs of constructing ground stations limit their number and distribution, resulting in few available windows for downlinking data [2]. Secondly, the high velocity of satellites results in short contact windows with ground stations, typically lasting only 7-10 minutes [3, 4]. Third, due to the physical limitations of radio frequency spectrum allocation and atmospheric absorption, data rates from satellite to ground station remain limited to an average of 160 Mbit/s [5], even with a variety of bands and advanced antenna design or modulation and coding schemes. These factors lead to insufficient downlink resources for the satellite data, necessitating onboard storage and resulting in delayed transmission, ranging from a few hours to several days [6].

A trend in EO involves multiple types of constellations collaboratively achieving mission goals. For instance, a low-priority EO constellation consists of satellites with low-resolution cameras sweeping the Earth’s surface for continuous monitoring, while a much smaller high-priority constellation with high-resolution cameras focus on specific Areas of Interest (AoIs) based on results from low-priority satellites and/or requests from users [6]. Furthermore, constellations are increasingly supporting user-scheduled time-sensitive sensing tasks to enable critical use cases such as rapid disaster response or real-time emergency management [7], and will prioritize transmission of such user-scheduled high-priority tasks over the default (low-priority) monitoring tasks via fast tracked data delivery to the ground [8].

In face of limited ground stations, the low- and high-priority constellations may share communication channels and ground stations to maximize the chance and data rate of downlink communication [9]. When there is a high-priority request such as monitoring the spread of forest fires at a specific location from a user, the low-priority satellites may be preempted of their communication resources to prioritize high-value data transmission, in which case the low-priority monitoring data must be stored until there is a future transmission opportunity.

This paper investigates the possibility that an attacker may utilize the sharing of communication resources and opportunities among mixed-priority EO satellites to launch intelligent attacks targeting critical data captured by low-priority EO satellites. Such attacks include, for instance, delaying the downlink of target data captured at a certain time and location, or dropping such data from the internal storage of a satellite before it can be downlinked. In doing so, for instance, the attacking entity (potentially a nation or organization) may aim to prevent downlink and analysis of sensitive information, such as regional warfare strategies or illegal operations, without launching large-scale, easily detectable attacks such as disabling a large number of ground stations (as happened at the beginning of the Russia-Ukraine conflict) [10] or jamming all satellite communication channels [11, 12].

We explore a new attack surface that exploits the competition for limited downlink resources between different types of EO satellites. Specifically, when an attacker deliberately schedules tasks from high-priority satellites that shares the limited downlink resources with a low-priority satellite, the latter will have to wait for the next transmission opportunity, leading to data on the low-priority satellite being delayed. If data accumulated on the low-priority satellite exceeds the internal storage limit, some data will be dropped. Specifically, by leveraging the predictable dynamics of satellites, including orbit information, scheduling policies, and queue status on the satellite, an attacker can intelligently select its attack strategy, such as how many/which transmission windows to attack, to make its attack more viable and less detectable. In this paper, we formalize data delay and data overflow problems, where an attacker targets a specific piece of data to delay or drop, and design two algorithms to solve these problems. Our attack can be planned or even launched before the target data is captured by a satellite, and utilize only legitimate services provided by different EO constellations, thus making the attack easy to launch and the attack target hard to locate or protect.

The contribution of this paper is listed as follows:

• •

  We explore and propose a new type of attack targeting data captured by certain EO satellites that share communication resources with others, utilizing the shared communication resources to delay or prevent the downlink of the target data via legitimate EO service requests.

• •

  We formulate two possible attack goals of an adversary: the data delay attack and the data overflow attack, and devise algorithms to find feasible attack strategies considering orbital dynamics, bandwidth, storage, and attack costs. We analyze the feasibility or optimality of our algorithms in typical attack scenarios.

• •

  We evaluate the attacks using real-world satellite orbital dynamics and imaging data, demonstrating their practical implications and effectiveness.

The data delay attack is devised to prolong the delay of target data transmission from a low-priority satellite to the ground station. By targeting specific data and its corresponding satellite, the attacker schedules tasks to high-priority satellites, thereby occupying the time slots typically used by the target low-priority satellite for downlink. Consequently, the targeted data must wait longer for additional available time slots to downlink, resulting in significant delays in data retrieval and potential mission-critical impacts. We design an algorithm to enable the attacker to find the minimum cost attack strategy in §V. We show that when targeting unit data, our algorithm can always find a feasible attack strategy when one exists, and is optimal in terms of cost by proving its optimality when the queue is not empty upon initialization—an assumption typically met in practice due to limited communication resources.

The data overflow attack, exploiting the limited onboard capacity of satellites, poses a more severe threat than the data delay attack and leads to the dropping of the target data, rendering it irrecoverable. As EO satellites continually collect new data, the objective of an attacker is to find an attack strategy that keeps the target data onboard until it is dropped when new data occupy its space. This requires more delicate control over when and which time slots to attack, as attacking more slots may not result in a higher attack success probability. We devise an algorithm to search for the attack strategy, and for unit data as the target, our algorithm can return a feasible attack strategy whenever one exists. See §VI for more details.

Proofs for the lemma and theorems of our theoretical analysis are provided in the Appendix.

An attacker’s goal is to find an attack strategy that can delay the target data beyond a certain threshold, called the target downlink time $t^{*}(\tilde{\tau})>t_{e}(\tilde{\tau},\emptyset)$, with the minimum attack cost. We define the Data Delay problem of finding the optimal data delay attack strategy as follows:

Intuitively, if the satellite’s internal storage is infinite, then attacking a transmissible time slot before the target data downlink will directly result in the target data’s downlink time being delayed by one transmissible time slot. However, what complicates the attack strategy is that if an attack results in the onboard queue being full at this time slot or some time later than the attacked slot but before the target downlink time, then further attacking any slot before or during the onboard queue being full will have no impact on further delaying the downlink time of the target data. As shown in Fig. 6, regardless of whether an attack occurs at $t^{\prime}$ or not, by the end of $t^{\prime\prime}$, the amount of data ahead of the target data is the same as it would be if no attack had occurred up to $t^{\prime\prime}$. To model the queue full condition, we define $t_{lb}(\tau,\mathcal{Y}_{s^{*}})\!\triangleq\!\max\{t_{0},\max_{t}\{Q_{s^{*}}(t,\mathcal{Y}_{s^{*}})\!=\!c_{s^{*}}\text{ and }t_{0}\!\leq\!t\!<\!t_{e}(\tau,\mathcal{Y}_{s^{*}})\}\}$ as the last time slot when the queue is full before the data unit $\tau$ is transmitted under the attack strategy $\mathcal{Y}_{s^{*}}$. If no data overflow occurs before ${\tau}$ is transmitted out, then $t_{lb}(\tau,\mathcal{Y}_{s^{*}})=t_{0}$.

The following lemma shows that attacks on time slots at or before the queue is full do not delay the data unit $\tau\in\Theta$.

Based on Lemma 1, we devise Algorithm 1 to find a feasible data delay attack strategy and prove its optimality for unit target data. We first initialize the attack strategy $\mathcal{Y}_{s^{*}}$. Then for each data unit $\tau\in\Theta$, we get the expected downlink time and the last queue full time without any attack (lines 1-1). If $\tau$ is dropped without any attack, then we do not need to conduct the delay attack (line 1). If the evacuation time $t_{e}(\tau,\mathcal{Y}_{s^{*}})-t_{e}(\tau,\emptyset)$ is smaller than the target duration $t^{*}(\tilde{\tau})-t_{e}(\tau,\mathcal{Y}_{s^{*}})$, which means $\tau$ needs more attack time slots to delay longer, we then begin to find the minimum cost attack strategy for $\tau$ (line 1). We first construct a set $\hat{T}_{\tau}$ that contains all the attackable time slots that potentially have attack strength for $\tau$ (line 1). Then we find the minimum cost attack time slot in $\hat{T}_{\tau}$ as $\hat{t}$ (line 1). If multiple attackable slots have the same cost, the earliest one is chosen. If the set $\hat{T}_{\tau}$ is empty, indicating the absence of any time slot that can be attacked, then the attack fails and $\tau$ can be transmitted before $t^{*}(\tilde{\tau})$ no matter how the attacker attacks (line 1). If $\hat{t}$ is found, we add $\hat{t}$ to the attack strategy $\mathcal{Y}_{s^{*}}$ and update the expected downlink time $t_{e}(\tau,\mathcal{Y}_{s^{*}})$ and the last queue full time $t_{lb}(\tau,\mathcal{Y}_{s^{*}})$ (lines 1-1). These two times need to be updated because additional attacks on $\hat{t}$ might influence whether further exploration of new attack time slots is needed and exclude time slots that definitely do not have attack strength. We repeat the process until the delay target is met (line 1), or if the target data is dropped (line 1).

EO satellites operate on predefined orbits, covering large regions of the Earth at fixed times. If the attacker’s goal is to delay or drop data of a specific location at a specific time, due to imaging frequency limitations, only a few or possibly just one data unit may be a uniquely valuable resource. In the following, we analyze the completeness and optimality of Algorithm 1 in finding the minimum cost attack strategy for single-unit target data, which suffices for many attack tasks.

An attacker’s goal is to find a feasible attack strategy to drop the onboard target data, preventing it from being downlinked to the ground station. We define the Data Overflow problem of finding the feasible data overflow attack strategy as follows:

We design Algorithm 2 to solve the Data Overflow problem. The attack begins by initializing the attack strategy $\mathcal{Y}_{s^{*}}$ as an empty set (line 2). For each data unit $\tau$, we calculate its expected downlink time $t_{e}(\tau,\mathcal{Y}_{s^{*}})$ and the initial queue full time $t_{lb}(\tau,\emptyset)$ without any attack (lines 2$-$2). In addition, we generate two sets of time slots: $\textsf{T}_{n}$ is the set of attackable time slots at and after the initial image downlink time that are sorted in ascending order, and $\textsf{T}_{p}$ is the set of attackable time slots before the initial image downlink time that are sorted in descending order (lines 2$-$2). $t_{n}$ and $t_{p}$ are the next attack time slot in $\textsf{T}_{n}$ and $\textsf{T}_{p}$, respectively (line 2). If $t_{n}\!\leq\!t_{e}(\tau,\mathcal{Y}_{s^{*}})$, which means we can attack the time slot $t_{n}$ and keep the target data onboard and at the top of the queue, then we update the expected downlink time $t_{e}(\tau,\mathcal{Y}_{s^{*}})$ based on the new attack strategy $\mathcal{Y}_{s^{*}}$ that includes the time slot $t_{n}$ and update $t_{n}$ to the next element in $\textsf{T}_{n}$ (lines 2$-$2). Else if $t_{n}>t_{e}(\tau,\mathcal{Y}_{s^{*}})$, which means the next attackable time slot in $\textsf{T}_{n}$ cannot contribute to delaying the downlink time of the target data, we need to attack the time slot $t_{p}$ in $\textsf{T}_{p}$ to delay the downlink time of $\tau$ to make sure $\tau$ remains onboard (lines 2$-$2). If $\textsf{T}_{p}$ is empty or new data overflow happens due to the attack on $t_{p}$, then the attack fails (line 2). This means there is no available attackable time slot to delay $\tau$ further; $\tau$ is downlinked before it can be dropped. This process repeats for each target unit in $\Theta$ until all are dropped. Theorem 2 shows the completeness of Algorithm 2 for targeting a single data unit.

Our attacks’ feasibility depends on three main conditions: (1) contention for limited communication resources between high- and low-priority satellites, (2) the attacker’s ability to schedule transmission of high-priority tasks for specific satellites at specific times, and (3) the attacker’s knowledge of orbit information, scheduling policies, and the target satellite’s queue status. We next explain why these conditions are very likely met by current and future constellations.

(1) Resource contention. Given the high cost and environmental requirements for building ground stations, sharing of ground stations among multiple constellations are becoming increasingly common for minimizing cost and maximizing performance [38, 39]. For instance, the Ground Station Operations team at Planet Labs Inc. has begun integrating software and hardware architectures across different constellations to support multiple missions through their ground station networks, aiming to reduce on-orbit reaction latency and increase the utilization of individual ground stations [9].

(2) Attacker’s ability to schedule transmission of high-priority tasks. Critical applications such as rapid disaster response or real-time emergency management require the delivering of user-scheduled high-priority, time-sensitive sensing data to the ground, which is being supported by more and more EO constellations. Such services can then be utilized by an attacker to preempt low-priority transmission during shared communication windows. For instance, Planet Labs allows users to schedule Assured Tasking Orders at specific times when satellites pass over designated areas [7, 40], and have the data delivered with minimum delay via its Fast Track Delivery service [8]. The data of such orders will be transmitted as soon as possible in the next communication windows after being generated, which opens up a possible avenue for adversarial scheduling of such orders to launch an attack. The attacker can further profile the delay in launching an attack, by submitting multiple high-priority tasks and observing their downlink/delivery times prior to launching the actual attack.

(3) Attacker’s knowledge of satellite orbits, scheduling, and queues. Firstly, the orbit information for both low- and high-priority satellites is publicly accessible [41], and since they must adhere to the orbit parameters claimed before their launch in FCC regulations, their future orbits are also predictable. Secondly, an attacker could obtain the communication scheduling policy via various methods. For instance, there has been extensive research on scheduling policy inference from measurement data, using deep learning [42] or probabilistic inference [43]. An attacker could also compromise a satellite (possibly even an outdated or decommissioned one), a ground station, or even a cloud-hosted copy of the satellite communication codebase, to uncover the scheduling policy. An insider attack from within the operator’s organization is also possible. Thirdly, an attacker can use various information sources to assist in determining the initial queue’s data volume. Fig. 8 shows the data collection pattern of a single satellite over three days. The satellite’s data collection is predictable and periodically repeats, focusing solely on gathering data above specific areas of the Earth’s surface. For a specific satellite, the dynamics of data generation rate and captured images can be reliably predicted. So if an attacker can determine the size of the queue at a certain moment and utilize the queue’s data generation and downlink patterns, it can relatively accurately determine the initial queue size at the start of the attack.

To determine the queue size at a specific time, an attacker with access to the satellite and ground station channel can infer that a satellite’s queue is empty if it does not downlink data during a transmissible window with no competition. Without channel access, the attacker can infer this from publicly available data via the open-source global network of satellite ground stations [44]. Other starting points for the attacker include evolving the queue from the target satellite’s initial launch. Other methods could also be used to infer queue status at a specific time, for instance, using input/output communication patterns with fuzzy inference systems [45] or other queue length estimation algorithms [46].

Dealing with estimation noise. An attacker may mis-estimate data size and data rate in the real-world, which may lead to failure of attacks if they are calculated based on inaccurate information. Heuristic strategies can be employed to deal with noise in such estimation. For instance, the attacker can increase the attack’s robustness against noise by attacking $M$ extra data units both before and after its primary target of $N$ units. If it can find an attack strategy that is feasible for all $N\!+\!2M$ data units as the target, then even if noise in queue dynamics or data rate estimation causes the attack to be unsuccessful on some data at the beginning or the end, there is still a high chance that the true target of $N$ units is successfully attacked. We show that this strategy can significantly increase both attacks’ robustness to estimation noise in §VIII.

There are other approaches to mitigate the impact of noise. For example, in a data delay attack, the attacker can generate a strategy to delay the target data past the target downlink time by a few time slots. Alternatively, redundantly attacking multiple time slots near the target data’s downlink time can also help combat noise. Since attack strategies can be generated and tested through simulation, the attacker can tailor multiple strategies for specific target data and select the most robust one against noise for a real-world attack.

Proof of Lemma 1

• Proof.

  Given an attack strategy $\mathcal{Y}_{s^{*}}$, let $t_{\sf ovf}$ be an arbitrary slot in $[t_{0},t_{lb}(\tau,\mathcal{Y}_{s*})]$ at which the queue is full under $\mathcal{Y}_{s^{*}}$, i.e., $Q_{s^{*}}(t_{\sf ovf},\mathcal{Y}_{s^{*}})=c_{s^{*}}$. Further let $t^{\prime}_{\sf ovf}\in[t_{0},t_{\sf ovf})$ be the last slot before $t_{\sf ovf}$ satisfying the same condition as $t_{\sf ovf}$ (when queue is full); if no such slot exists then let $t^{\prime}_{\sf ovf}=t_{0}-1$.

To prove Lemma 1, we show that adding any attackable time slot $t^{\prime}\in\mathcal{A}_{s^{*}}\cap(t^{\prime}_{\sf ovf},t_{\sf ovf}]$ to attack strategy $\mathcal{Y}_{s^{*}}$ will result in the same queue evolution in both $Q_{s^{*}}(t,\mathcal{Y}_{s^{*}}\cup\{t^{\prime}\})$ and $Q_{s^{*}}(\tau,t,\mathcal{Y}_{s^{*}}\cup\{t^{\prime}\})$ as before adding $t^{\prime}$, for any $t\geq t_{\sf ovf}$.

First, consider any slot $t\in[t^{\prime},t_{\sf ovf}]$. By definition, when $t=t^{\prime}$, the full queue $Q_{s^{*}}(t,\mathcal{Y}_{s^{*}}\cup\{t^{\prime}\})=\min\{c_{s_{*}},Q_{s^{*}}(t,\mathcal{Y}_{s^{*}})+\alpha^{\tau}_{s^{*}}(t^{\prime})\}$, where $\alpha^{\tau}_{s^{*}}(t^{\prime})$ is the additional residual data amount due to transmission slot $t^{\prime}$ being attacked. Similarly, the subqueue before target data $\tau$ will become $Q_{s^{*}}(\tau,t,\mathcal{Y}_{s^{*}}\cup\{t^{\prime}\})=Q_{s^{*}}(\tau,t,\mathcal{Y}_{s^{*}})+\alpha^{\tau}_{s^{*}}(t^{\prime})$.

If $t^{\prime}=t_{\sf ovf}$, we have a full queue $Q_{s^{*}}(t^{\prime},\mathcal{Y}_{s^{*}})=c_{s^{*}}$, and so $Q_{s^{*}}(t^{\prime},\mathcal{Y}_{s^{*}}\cup\{t^{\prime}\})=\min\{c_{s^{*}},Q_{s^{*}}(t^{\prime},\mathcal{Y}_{s^{*}})+\alpha^{\tau}_{s^{*}}(t^{\prime})\}=c_{s^{*}}$. In this case, the downlink data amount decreases to $O_{s^{*}}(t^{\prime},\mathcal{Y}_{s^{*}}\cup\{t^{\prime}\})=O_{s^{*}}(t^{\prime},\mathcal{Y}_{s^{*}})-\alpha^{\tau}_{s^{*}}(t^{\prime})$ due to the attack, and the dropped amount increases to $D_{s^{*}}(t^{\prime},\mathcal{Y}_{s^{*}}\cup\{t^{\prime}\})=D_{s^{*}}(t^{\prime},\mathcal{Y}_{s^{*}})+\alpha^{\tau}_{s^{*}}(t^{\prime})$ due to additional queue overflow. Hence, the subqueue before target data $\tau$ also remains the same: $Q_{s^{*}}(\tau,t^{\prime},\mathcal{Y}_{s^{*}}\cup\{t^{\prime}\})=Q_{s^{*}}(\tau,t^{\prime},\mathcal{Y}_{s^{*}})$. Since both $Q_{s^{*}}(t^{\prime},\mathcal{Y}_{s^{*}})$ and $Q_{s^{*}}(\tau,t,\mathcal{Y}_{s^{*}}\cup\{t^{\prime}\})$ remains unchanged at $t^{\prime}=t_{\sf ovf}$, the queue evolution after $t_{\sf ovf}$ is unaffected.

If $t^{\prime}<t_{\sf ovf}$, the remaining queue at time $t^{\prime}$ is increased by $\alpha^{\tau}_{s^{*}}(t^{\prime})$, that is, $Q_{s^{*}}(t^{\prime},\mathcal{Y}_{s^{*}}\cup\{t^{\prime}\})=Q_{s^{*}}(t^{\prime},\mathcal{Y}_{s^{*}})+\alpha^{\tau}_{s^{*}}(t^{\prime})$. By induction, we have $Q_{s^{*}}(t,\mathcal{Y}_{s^{*}}\cup\{t^{\prime}\})=Q_{s^{*}}(t,\mathcal{Y}_{s^{*}})+\alpha^{\tau}_{s^{*}}(t^{\prime})$ for each time slot $t\in[t^{\prime},t_{\sf ovf})$. At time $t=t_{\sf ovf}$, since $Q_{s^{*}}(t,\mathcal{Y}_{s^{*}})=c_{s^{*}}$, this leads to the same derivation as above where $Q_{s^{*}}(t,\mathcal{Y}_{s^{*}}\cup\{t^{\prime}\})=\min\{c_{s^{*}},Q_{s^{*}}(t,\mathcal{Y}_{s^{*}})+\alpha^{\tau}_{s^{*}}(t^{\prime})\}=c_{s^{*}}$. Similarly, we have $Q_{s^{*}}(\tau,t,\mathcal{Y}_{s^{*}}\cup\{t^{\prime}\})=Q_{s^{*}}(\tau,t,\mathcal{Y}_{s^{*}})+\alpha^{\tau}_{s^{*}}(t^{\prime})$ for each time slot $t\in[t^{\prime},t_{\sf ovf})$ due to the downlink amount $O_{s^{*}}(t^{\prime},\mathcal{Y}_{s^{*}}\cup\{t^{\prime}\})$ being reduced by $\alpha^{\tau}_{s^{*}}(t^{\prime})$ at time $t^{\prime}$. At time $t=t_{\sf ovf}$, the dropped amount $D_{s^{*}}(t,\mathcal{Y}_{s^{*}}\cup\{t^{\prime}\})$ increased by $\alpha^{\tau}_{s^{*}}(t^{\prime})$ due to queue overflow, and hence the subqueue $Q_{s^{*}}(\tau,t,\mathcal{Y}_{s^{*}}\cup\{t^{\prime}\})$ still remains the same. Hence, the queue evolution after $t_{\sf ovf}$ remains unaffected.

Summarizing the above, since the queue evolution of both the full queue and the subqueue before $\tau$ remains unchanged after $t_{\sf ovf}$, the expected evacuation time of the target data $\tau$ remains unchanged. By definition of $t_{lb}(\tau,\mathcal{Y}_{s*})$, this means attacking any single slot before $t_{lb}(\tau,\mathcal{Y}_{s*})$ results in no attack strength. The conclusion extends to an arbitrary set of attack slots before $t_{lb}(\tau,\mathcal{Y}_{s*})$ by induction over the set, thus proving Lemma 1. ∎

Proof of Theorem 1

• Proof.

  We prove Theorem 1 by induction.

Let $\textsf{next}(t)=\min_{t^{\prime}}\{t^{\prime}|t^{\prime}\in\mathcal{X}_{s^{*}}\text{ and }t^{\prime}>{t}\}$ be the next transmissible time slot after time $t$. Let $\delta_{s^{*}}^{t}$ be the number of transmissible time slots between the original (non-attacked) evacuation time $t_{e}(\tau,\emptyset)$ and the delay target $t$. Assume the data delay attack problem is feasible for a target delay $t^{*}(\tau)=t$, we define a minimal attack strategy (MAS) to be a feasible attack strategy $\mathcal{Y}_{s^{*}}$ for target delay $t$, such that removing any slot from $\mathcal{Y}_{s^{*}}$ results in it no longer being feasible for $t$. By definition, a MAS has the following properties:

1. 1.

   A MAS for $t$ must have size equal to $\delta_{s^{*}}^{t}$;

2. 2.

   A MAS for $\textsf{next}(t)$ has exactly one more time slot than a MAS for $t$;

3. 3.

   A minimum-cost attack strategy for $t$ must be a MAS (but not vice versa).

The third property above is true because, if a minimum-cost attack strategy $\mathcal{Y}_{s^{*}}$ is not a MAS, then there exists at least one time slot in $\mathcal{Y}_{s^{*}}$, such that removing it still results in a feasible attack strategy with less cost.

Based on the above, we prove the following statement by induction: in every iteration $i$ of Algorithm 1, it finds a minimum-cost attack strategy with target delay equal to the $i$-th transmissible time slot after $t_{e}(\tau,\emptyset)$.

Base step: Before the first iteration ($i=0$), the statement is true, since $\mathcal{Y}_{s^{*}}=\emptyset$ is a minimum-cost attack strategy for target delay equal to the original evacuation time $t_{e}(\tau,\emptyset)$.

Induction step: Let $t$ be the $i$-th transmissible time slot after $t_{e}(\tau,\emptyset)$. Assume target delay $t$ is feasible, and our algorithm has found a minimum-cost attack strategy ${{\mathcal{Y}_{s^{*}}^{t}}}$ for $t$ at iteration $i$. Further assume target delay $\textsf{next}(t)$ is also feasible. We will prove that our algorithm finds a minimum-cost attack strategy for $\textsf{next}(t)$ at iteration $i+1$.

Our induction proof is divided into two parts: (1) Algorithm 1 finds a minimal (and thus feasible) attack strategy for $\textsf{next}(t)$ at iteration $i+1$. (2) The attack strategy has the minimum cost among all feasible strategies for $\textsf{next}(t)$.

Part (1): Feasibility and Minimality. Let ${{\mathcal{\overline{Y}}_{s^{*}}^{\textsf{next}(t)}}}$ be an arbitrary MAS (which is feasible) for target delay $\textsf{next}(t)$. We now describe a step-by-step process for transforming ${{\mathcal{\overline{Y}}_{s^{*}}^{\textsf{next}(t)}}}$ into an MAS for $\textsf{next}(t)$ that has the exact shape of ${{\mathcal{Y}_{s^{*}}^{t}}}\cup\{\bar{t}\}$, i.e., the solution we found in iteration $i$ plus an extra element $\bar{t}$. Each step replaces one element $t_{2}\in{{\mathcal{\overline{Y}}_{s^{*}}^{\textsf{next}(t)}}}$ but not in ${{\mathcal{Y}_{s^{*}}^{t}}}$ with one $t_{1}\in{{\mathcal{Y}_{s^{*}}^{t}}}\setminus{{\mathcal{\overline{Y}}_{s^{*}}^{\textsf{next}(t)}}}$, until when ${{\mathcal{Y}_{s^{*}}^{t}}}\subset{{\mathcal{\overline{Y}}_{s^{*}}^{\textsf{next}(t)}}}$. During the transformation, we prove that after each step:
(a) the attack strategy is still feasible;
(b) the attack strategy is still minimal (having size $\delta_{s^{*}}^{t}+1$);
(c) the intersection between ${{\mathcal{\overline{Y}}_{s^{*}}^{\textsf{next}(t)}}}$ and ${{\mathcal{Y}_{s^{*}}^{t}}}$ increases by $1$.

Consider $t_{1}\in{{\mathcal{Y}_{s^{*}}^{t}}}\setminus{{\mathcal{\overline{Y}}_{s^{*}}^{\textsf{next}(t)}}}$, and let $\mathcal{Y}^{\prime}={{\mathcal{\overline{Y}}_{s^{*}}^{\textsf{next}(t)}}}\cup\{t_{1}\}$. Since ${{\mathcal{Y}_{s^{*}}^{t}}}\not\subseteq{{\mathcal{\overline{Y}}_{s^{*}}^{\textsf{next}(t)}}}$ until termination, such $t_{1}$ must exist. Two cases may arise: either $\mathcal{Y}^{\prime}$ results in the evacuation time of the target data until $\textsf{next}(\textsf{next}(t))$—resulting in an extra delay of the target data—or the evacuation remains the same at $\textsf{next}(t)$. Both cases are discussed below:

$\vartriangleright$ Case 1: adding $t_{1}$ results in additional delay. In this case, we find any $t_{2}\in{{\mathcal{\overline{Y}}_{s^{*}}^{\textsf{next}(t)}}}\setminus{{\mathcal{Y}_{s^{*}}^{t}}}$, and remove $t_{2}$ from ${{\mathcal{\overline{Y}}_{s^{*}}^{\textsf{next}(t)}}}$. Such $t_{2}$ must exist since $|{{\mathcal{\overline{Y}}_{s^{*}}^{\textsf{next}(t)}}}|>|{{\mathcal{Y}_{s^{*}}^{t}}}|$. After this:

(a) Since before removing $t_{2}$, the strategy ${{\mathcal{\overline{Y}}_{s^{*}}^{\textsf{next}(t)}}}$ delays target data until $\textsf{next}(\textsf{next}(t))$, then after removing $t_{2}$, the expected evacuation time is still at least $\textsf{next}(t)$, proving feasibility of the new ${{\mathcal{\overline{Y}}_{s^{*}}^{\textsf{next}(t)}}}$ for target delay $\textsf{next}(t)$.

(b) The size of ${{\mathcal{\overline{Y}}_{s^{*}}^{\textsf{next}(t)}}}$ remains unchanged before adding $t_{1}$ versus after removing $t_{2}$, and hence ${{\mathcal{\overline{Y}}_{s^{*}}^{\textsf{next}(t)}}}$ is still minimal.

(c) Replacing $t_{2}$ with $t_{1}$ results in one more element that ${{\mathcal{\overline{Y}}_{s^{*}}^{\textsf{next}(t)}}}$ and ${{\mathcal{Y}_{s^{*}}^{t}}}$ have in common.

$\vartriangleright$ Case 2: adding $t_{1}$ results in no additional delay. This means a buffer overflow has happened after $t_{1}$, resulting in zero attack strength of $t_{1}$ according to Lemma 1. Let $t_{lb}^{t_{1}}<\textsf{next}(t)$ be the earliest time slot after $t_{1}$ that has a full queue before adding $t_{1}$ to ${{\mathcal{\overline{Y}}_{s^{*}}^{\textsf{next}(t)}}}$. Assume we can find $t_{2}\in{{\mathcal{\overline{Y}}_{s^{*}}^{\textsf{next}(t)}}}$ such that $t_{2}\leq t_{lb}^{t_{1}}$, then removing $t_{2}$ from ${{\mathcal{\overline{Y}}_{s^{*}}^{\textsf{next}(t)}}}$ will result in the same queue evolution after $t_{lb}^{t_{1}}$, following the same proof logic of Lemma 1. In this case, we have: (a) the resulting ${{\mathcal{\overline{Y}}_{s^{*}}^{\textsf{next}(t)}}}$ is still feasible since removing $t_{2}$ does not result in reduction of evacuation time; (b) ${{\mathcal{\overline{Y}}_{s^{*}}^{\textsf{next}(t)}}}$ is still minimal; (c) ${{\mathcal{\overline{Y}}_{s^{*}}^{\textsf{next}(t)}}}$ has one more common element with ${{\mathcal{Y}_{s^{*}}^{t}}}$.

We now show that there must exist such a $t_{2}\in{{\mathcal{\overline{Y}}_{s^{*}}^{\textsf{next}(t)}}}$ and $t_{2}\leq t_{lb}^{t_{1}}$. Assume such a $t_{2}$ does not exist. This means that even without any attack before $t_{lb}^{t_{1}}$, the queue is still full at $t_{lb}^{t_{1}}$. In this case, adding $t_{1}$ to any attack strategy—including ${{\mathcal{Y}_{s^{*}}^{t}}}\setminus\{t_{1}\}$—will result in zero attack strength by Lemma 1. This contradicts ${{\mathcal{Y}_{s^{*}}^{t}}}$ being minimal in the induction hypothesis. Therefore, there must exist at least one element $t_{2}\leq t_{lb}^{t_{1}}$ that is in the attack strategy ${{\mathcal{\overline{Y}}_{s^{*}}^{\textsf{next}(t)}}}$.

To summarize, in whichever case above, one can always find a $t_{2}\in{{\mathcal{\overline{Y}}_{s^{*}}^{\textsf{next}(t)}}}\setminus{{\mathcal{Y}_{s^{*}}^{t}}}$, and replace it with a $t_{1}\in{{\mathcal{Y}_{s^{*}}^{t}}}\setminus{{\mathcal{\overline{Y}}_{s^{*}}^{\textsf{next}(t)}}}$, which preserves both feasibility and minimality of ${{\mathcal{\overline{Y}}_{s^{*}}^{\textsf{next}(t)}}}$. After up to $\delta^{t}_{s^{*}}$ steps, the attack strategy ${{\mathcal{\overline{Y}}_{s^{*}}^{\textsf{next}(t)}}}$ becomes a MAS in the shape of ${{\mathcal{Y}_{s^{*}}^{t}}}\cup\{\bar{t}\}$.

Remark: Note that the above transformation is valid not just between ${{\mathcal{\overline{Y}}_{s^{*}}^{\textsf{next}(t)}}}$ and ${{\mathcal{Y}_{s^{*}}^{t}}}$, but also any pair of MASs. This fact will be used in Part (2) of this proof, as well as the next proof for Theorem 2 that is based on a similar idea.

Finally, to complete the proof of Part (1), as long as a feasible solution ${{\mathcal{Y}_{s^{*}}^{t}}}\cup\{\bar{t}\}$ exists for target delay $\textsf{next}(t)$, Algorithm 1 can always find such a $\bar{t}$ in Line 1. To show this, note that if $\bar{t}$ exists before $t_{lb}(\tau,{{\mathcal{Y}_{s^{*}}^{t}}})$ in the algorithm, then by Lemma 1 it will have zero attack strength. In this case, adding $\bar{t}$ to ${{\mathcal{Y}_{s^{*}}^{t}}}$ leads to a non-minimal attack strategy, violating our proof above that ${{\mathcal{Y}_{s^{*}}^{t}}}\cup\{\bar{t}\}$ is a MAS. Hence $\bar{t}$ (which earlier proof shows to exist) must be in the range $\hat{T}_{\tau}$ that the algorithm searches within, proving $\hat{T}_{\tau}$ to be non-empty. By finding a slot with non-zero attack strength, the algorithm finds one such $\bar{t}$, leading to a MAS feasible to $\textsf{next}(t)$ in iteration $i+1$.