A Dynamic Jamming Game for Real-Time Status Updates

We study timely status updates of a real-time system in an adversarial setting. The system samples a physical process, and sends the samples from the source (e.g., a sensor) to the destination (e.g, a control center) through a channel. For real-time monitoring/control tasks, it is crucial for the system to update the status of the physical process"timely". We measure the timeliness of status updates by the time elapsed since the latest update at the destination was generated at the source, and define the time elapsed as age of information, or age in short. To sabotage the system, an attacker aims to maximize the age by jamming the channel and hence causing delay in status updates. The system aims to minimize the age by judiciously choosing when to sample and send the updates. We model the ongoing repeated interaction between the attacker and the system as a dynamic game. In each stage game, the attacker chooses the jamming time according to the jamming time distribution, and the system responds by delaying the sampling according to the sampling policy. We prove that there exists a unique stationary equilibrium in the game, and provide a complete analytical characterization of the equilibrium. Our results shed lights on how the attacker sabotages the system and how the system should defend against the attacker.


I. INTRODUCTION
The success of many existing and emerging engineering systems hinges upon the timely status updates of the underlying physical processes. Such systems range from real-time monitoring systems, such as sensor networks monitoring air pollution [1] and Internet-of-Things (IoT) [2], to networked control systems, such as autonomous vehicles [3] and power grids [4]. Timely status updates ensure that the system always has fresh information about the physical process, and that it can monitor and control the process effectively.
The age of information, or age in short, is becoming the prevailing metric to measure the timeliness of status updates [5]- [20]. At any time instant, the age of information is defined as the amount of time elapsed since the most recently received update was generated. A large age indicates that the information about the physical process is outdated, since the most recently received update was generated long time ago. Therefore, the goal is to minimize the age of information. However, minimizing age of information requires careful decisions on when to sample the process and send the samples. Suppose that we have just updated the status. On the one hand, we do not want to update the status immediately, because the Yin Sun was supported in part by ONR grant N00014- 17-1-2417. new update would be almost the same as the old update, and hence carry little fresh information. On the other hand, we do not want to wait for a long time before updating the status, because the previous update would become outdated before the next update. In summary, we need to make sure that both the information sent and that received are fresh, in order to minimize the age of information [8], [16].
While there have been a growing body of works that address the problem of minimizing the age of information in various scenarios [5]- [10], [13], [15], [16], few works have studied this problem in an adversarial setting [17]. Since timely status updates are of particular importance to real-time monitoring and control systems, the attackers of these systems may specifically target their capability of timely updating the status [21], [22]. Therefore, it is crucial to understand how would an attacker sabotage a real-time monitoring/control system, how should the system defend against the attack, and to what extent the attacker can degrade the timeliness of status update. In this paper, we try to answer these questions in a stylized model.
We formulate a dynamic game to model the repeated interaction between a real-time monitoring/control system and its attacker. The system takes samples from a physical process to monitor and sends the samples to a destination through a wireless channel. An attacker jams the channel so that the system cannot send new updates in timely fashion. The attacker aims to find a jamming time distribution to maximize the age of information. After the jamming is over, the system chooses when to sample and send the next update. The system aims to find a sampling policy to minimize the age of information. We summarize the main contributions of this paper as follows.
• We prove that there exists a unique stationary equilibrium in the game, and that the system cannot further reduce the age at the stationary equilibrium by using more complicated equilibrium strategies. • We provide a complete analytical characterization of the equilibrium, which sheds lights on how the system should defend against the attacker. Specifically, the equilibrium sampling policy tries to make the time differences between subsequent update deliveries as equal as possible. • We also provide insights on how the attacker should abotage the system. Specifically, the attacker will choose a jamming time distribution with as high variance as possible.

II. RELATED WORKS
Most works on age of information do not consider an attacker attacking the system [5]- [10], [13], [15], [16]. The most related work is [17], where the authors study age of information in an adversarial setting. There are two major differences between our work and [17]. First, our work studies the interaction of the user and the attacker at the MAC layer, while their work [17] studies the interaction in the physical layer. This difference results in different models of actions and more importantly, different models of interaction (e.g., different payoff functions). Second, our work models the interaction as a dynamic game, while their work [17] uses a static game model. Therefore, we study the ongoing interaction between the user and the attacker, where the user needs to develop a defense policy that specifies a sequence of sampling actions over time. In contrast, their work studies the one-shot interaction, where the user needs to determine a scalar action.

A. System Model
Consider a real-time monitoring system in the presence of an attacker (see Fig. 1 for an illustration). The real-time monitoring system could be a stand-alone system by itself (e.g., sensor networks [1] and Internet-of-Things [2]), or a component of a real-time control system (e.g., autonomous vehicles [3] and power grids [4]). The monitoring system consists of a sensor that collects information about some physical process, and a transmitter that sends information to a receiver. The (monitoring) system aims to timely update the information collected, which is crucial for any real-time monitoring or control system. The system achieves timely update of information by judiciously choosing when to sample the physical process and when to transmit the samples. The attacker aims to sabotage the timely status updates of the system, through jamming the wireless channel between the transmitter and the receiver.
Next, we describe the system model in details. 1 Since the system updates a small amount of information (e.g., a sensor reading, a control signal) at each time, the duration of each transmission is negligible and assumed to be zero [7], [13], [15]. Therefore, although the attacker can monitor the channel and detect a transmission, it is difficult for the attacker to target the transmission (e.g., through colliding with the transmitted packet). Instead, after detecting the transmission of a sample, the attacker can occupy the channel for some amount of time in order to delay the delivery of the next sample. Specifically, to delay the transmission of the n-th sample, the attacker jams the channel for a random duration of A n . This formulation physical process sampler Tx sensor Rx monitor control receiver attacker jamming Fig. 1. Illustration of the system model.
includes the case when the attacker jams the channel for a deterministic amount of time (by making the distribution a Dirac delta function). We make the following assumption. 2 Assumption 1: The attacker's jamming time for each transmission is identically and independently distributed (i.i.d.) with probability density function (pdf) f A .
We impose the following constraints on the maximum and average jamming time: For all n = 1, 2, . . ., it holds almost surely that The maximum jamming time A max is set up to reduce the chance that the system can locate the attacker. The attacker would like to limit the jamming time to be no longer than A max to remain elusive. The constraint on the average jamming time comes from the energy constraint of the attacker. Since the attacker's action is the jamming time distribution f A , we translates the constraints in (1) into constraints on f A as follows The system employs carrier sensing to monitor the channel. Once the channel is idle (i.e., after the attacker stops occupying the channel), the system decides when to sample the physical process and when to transmit the sample. One may wonder why the system does not sample and transmit immediately after the channel is idle? While the system should transmit the sample immediately after sampling (for timely update of information), it may not be optimal to sample immediately after the channel becomes idle. We refer interested readers to [16, Sec. I] for an example illustrating why the system may want to delay the sampling. We write D n as the delay of the n-th sample after the channel is idle. Denoting the sampling time of the n-th sample as S n , we have where we define S 0 = 0.
We use the age of information to evaluate the timely update of information [5], [6]. At any time t, the age of information is the time since the last status update of the physical process t ∆(t) jamming by attacker: t sampling by system: t Fig. 2. Illustration of the system dynamics and evolution of the age of information. Sn is the sampling time of the n-th sample. The transmission of the sample is assumed to be instant. An is the attacker's jamming time for the n-th sample, and Dn is the system's delay of the n-th sample after the channel is idle.
(i.e., since the last sample). We denote the age of information at time t by ∆(t), which can be calculated as The evolution of the age is shown in Fig. 2.

B. Game Formulation
Now we formulate the dynamic game between the system and the attacker. The dynamic game consists of an infinite number of stage games. The n-th stage game takes place between the transmission of the (n − 1)−th and the n-th samples (i.e., between S n−1 and S n ). In each stage game n, the attacker takes action by choosing the jamming time A n , and the system reacts by choosing delay D n for the n-th sample. In other words, each stage game is a Stackelberg game with the attacker taking action first. Since we have restricted to i.i.d. jamming time distribution, the attacker's action is simply choosing the jamming time distribution f A . We allow the attacker to predict how the system reacts to its action, based on which the attacker will seek its optimal jamming time distribution.
The system's sampling policy dictates how to choose the delay D n for each sample. We focuses on causal policies that determine each delay D n based on information available, which is the historical and current jamming time A 1 , . . . , A n and the historical delay D 1 , . . . , D n−1 . We write the set of histories at the beginning of the n-th stage game as H n [0, A max ] n × [0, ∞) n−1 , and the set of all histories as H = ∪ ∞ n=1 H n . Then a causal sampling policy is defined as where Θ ([0, ∞)) is the set of all possible probability distributions with support within [0, ∞). In other words, π(A 1 , . . . , A n , D 1 , . . . , D n−1 ) is the probability distribution of the delay D n . We write the set of all causal policies as Π.
The payoff of interest to both the system and the attacker is the average age of information, defined as which depends on the attacker's jamming time distribution f A and the system's sampling policy π.
The system aims to minimize the average age ∆(f A , π). Its optimization problem to solve is The attacker aims to maximize the average age ∆(f A , π), in anticipation of the system's reaction to its jamming time distribution. Given any jamming time distribution f A , the system reacts by employing a sampling policy that solves (7). We write BR(f A ) as the system's reaction to f A (i.e., a solution to (7)). The function BR(f A ) is also called best response in game theoretic term. Note that under the same jamming time distribution f A , the best response BR(f A ) of the system may not be unique. However, since all best responses result in the same average age, we only need to consider an arbitrary best response.
The attacker's optimization problem can then be written as Note that we use the best response BR(f A ), instead of an arbitrary policy π, in the objective function of the attacker. This reflects the fact that the attacker can anticipate the system's best response when taking actions. In other words, each stage game is a Stackelberg game with the attacker being the leader [23]. Therefore, the attacker has strategic advantage, because it can predict how the system reacts to its action, and choose its optimal action based on this prediction. By giving the attacker strategic advantage, we can evaluate how well the system can defend in the worst case. Now we can define the equilibrium of the dynamic game. Definition 1 (Equilibrium): Aa equilibrium is a duple of two functions (f * A , π * ) such that • the system's sampling policy π * minimizes the average age under the jamming time distribution f * A , namely π * is a solution to (7). • the attacker's jamming time distribution f * A maximizes the average age in anticipation of the system's best response, namely f * A is a solution to (8). The definition of equilibrium ensures that neither the system nor the attacker could deviate from the equilibrium and get more favorable outcomes.

IV. MAIN RESULT
We give a complete characterization of equilibria in this section. Note that both optimization problems of the system and the attacker in (7) and (8) are complicated functional optimization problems. We first argue that we can simplify the problem by restricting our attention to stationary deterministic sampling policies. We then define the corresponding stationary equilibrium, prove that the stationary equilibrium is unique, and provide analytical expressions of the equilibrium jamming time distribution and the equilibrium sampling policy.

A. Restriction to Stationary Deterministic Sampling Policies
We consider stationary deterministic sampling policies, a special class of causal policies defined as follows.
A stationary deterministic policy chooses the delay D n as a fixed, deterministic function of the jamming time A n , independent of the historical jamming time A 1 , . . . , A n−1 and historical delay D 1 , . . . , D n−1 .
Although the system could choose any causal policy π ∈ Π, the following lemma suggests that given any jamming distribution f A , there exists a unique stationary deterministic sampling policy that is optimal among all causal policies.
Lemma 1: Given any jamming time distribution f A , there exists a unique stationary deterministic sampling policy that is optimal among all causal policies.
Proof: For a given jamming distribution f A , the age minimization problem of the system is equivalent to the one in [16]. Therefore, we can use [16,Theorem 4]. The results in Lemma 1 directly come from [16,Theorem 4].
Lemma 1 allows us to restrict to stationary deterministic sampling policies. According to (9), a stationary deterministic policy is completely specified by the deterministic function u. Hence, we will refer to a stationary deterministic policy as u.
Since we restrict to stationary deterministic sampling policies, we focus on stationary equilibrium defined as follows.
Definition 3 (Stationary Equilibrium): A stationary equilibrium is an equilibrium (f * A , π * ) where the sampling policy π * is stationary deterministic.
We also write a stationary equilibrium as (f * A , u * ).

B. Characterization of Equilibria
Now we give a complete characterization of stationary equilibrium.
Theorem 1: There is a unique stationary equilibrium, where the attacker's equilibrium jamming time distribution is where δ(·) is the Dirac delta function, and the system's equilibrium sampling policy is D n = u * (A n ), where the function u * is given by where (·) + max {·, 0}, and β * is a constant given by Proof: See Section V. Our result provides analytical characterization of the equilibrium, and hence shed lights on the equilibrium behavior of the system and the attacker. First, the system's policy can be viewed as a "water-filling" policy with β as the water level. The purpose of water-filling is to make the intervals between receipts of consecutive samples (i.e., S n − S n1 ) as equal as possible. When the attacker's jamming time A n = a is short, the system chooses a larger delay D n = u(a), so that the new transmission carries "fresh" information. More specifically, if the jamming time is zero, and if the system chooses zero delay, the new transmission contains exactly the same information as the previous transmission, and hence the new transmission is "wasted". On the contrary, the system chooses a smaller delay if the attacker's jamming time is long, and does not delay the transmission at all if the jamming time is above the threshold β. This ensures that the received information is not outdated by a large delay in the transmission. With such a water-filling policy, the system strikes the balance between sending fresh enough information (by not letting the delay too small) and receiving fresh enough information (by not letting the delay too large).
Since the system wishes to keep the time between receipts of consecutive samples equal, the attacker tries to make it difficult for the system to achieve this. The worst jamming distribution for the attacker is a fixed deterministic jamming time, against which the system can easily make sure that the updates are received periodically. Therefore, the best jamming distribution for the attacker should have high variance, where the realized jamming time is either the largest (A max ) or zero. This is exactly the equilibrium jamming time distribution specified in our theorem.

V. PROOF OF MAIN RESULT
In this section, we prove our main results in Theorem 1. We first derive the best response sampling policy BR(f A ), and then solve for the equilibrium jamming time distribution f * A . Based on these results, we can obtain the equilibrium sampling policy u * = BR(f * A ).

A. Best Response Sampling Policy
First, we derive the best response sampling policy BR(f A ) under any jamming time distribution f A .
Lemma 2: For any jamming time distribution f A that satisfies (2), the best response sampling policy is BR( with β satisfying Proof: We have proved in Lemma 1 that the best response sampling policy is characterized by [16,Theorem 4]. The results directly follow from [16,Theorem 4].

B. Equilibrium Jamming Time Distribution
Next, we derive the equilibrium jamming time distribution f * A . We first simplify the attacker's optimization problem (8) by the following lemma.
Lemma 3: The attacker's optimization problem (8) is equivalent to Proof: See Subsection A of Appendix. We verify that the equilibrium jamming time distribution f * A in Theorem 1 is a feasible solution to (15). Lemma 4: The equilibrium jamming time distribution f * A in Theorem 1 is a feasible solution to (15). Moreover, under f * A , the unique β that satisfies the first constraint of (15) is the β * defined in Theorem 1.
Proof: See Subsection B of Appendix. We need two properties of the objective function of (15) to prove that the feasible solution f * A is indeed the unique optimal solution. We write the objective of (15) as a function of β and f A as follows: Note that the argument β does not need to satisfy the first constraint in (15). The first useful property of the function g(β, f A ) is that when the jamming time distribution is equal to the equilibrium distribution (i.e., when f A = f * A ), the largest β that satisfies β = 1 2 g(β, f * A ) is β * . Lemma 5: The largest β that satisfies β = 1 2 g(β, f * A ) is β * . In addition, we have β > 1 2 g(β, f * A ) for any β > β * . Proof: See Subsection C of Appendix. The second useful property of the function g(β, f A ) is that for any β, the equilibrium distribution f * A maximizes g(β, f A ) among all distributions that satisfy (2).
Lemma 6: Given any β, the equilibrium distribution f * A is a solution to the following problem: s.t. f A satisfies (2).
Proof: See Subsection D of Appendix. Base on Lemma 5 and Lemma 6, we can prove that f * A is the unique optimal solution to (15) by contradiction. Suppose that there is a better solutionf A such that g(β,f A ) > g(β * , f * A ). Sincef A is feasible, we haveβ = 1 2 g(β,f A ), which implies β > 1 2 g(β * , f * A ) = β. Base on Lemma 6, we have Base on Lemma 5 and the fact thatβ > β, we have Therefore, we have g(β,f A ) < 2β, which violates the first constraint of (15). This contradiction implies that f * A is the unique optimal solution to (15).

C. Equilibrium Sampling Policy
It was proved in Lemma 4 that given equilibrium jamming time distribution f * A , the β * specified in Theorem 1 is the unique β in the best response to f * A . This concludes the proof.

VI. SIMULATION RESULTS
We have argued that the equilibrium jamming time distribution has a large variance and maximizes the age, while a deterministic jamming time is worst in maximizing the age. Now we consider a jamming time distribution that is the mixture of the two distribution: 1] is the weight of the equilibrium jamming time distribution and f D A is a deterministic jamming time with f D A (a) = δ (a − A avg ) . We choose the deterministic jamming time to be A avg so that the mixture distribution has a constant mean value.
Under the mixture distribution, we compute the age under the equilibrium sampling policy defined in (2), and that under the zero-wait sampling policy (i.e., samples immediately after the jamming). Fig. 3 shows the ages versus the weight α.
First, we can see that the equilibrium jamming distribution f * A is indeed better for the attacker, since the ages in both cases increase as the mixture distribution becomes closer to the equilibrium jamming distribution. Second, we can see that the equilibrium sampling policy achieves smaller ages than the zero-wait policy.

VII. CONCLUSION
We studied a dynamic game between a real-time system and an attacker. The system samples a physical process and sends the samples through a wireless channel, in order to perform some monitoring and control tasks. The attacker jams the channel to delay the status updates. We used the age of information as the performance metric to measure the timeliness of the status updates. We proved that there exists a unique stationary equilibrium in this game, and characterized the equilibrium analytically. Our results indicate that the attacker chooses a jamming time distribution with high variance, while the system chooses a sampling policy that results in low variance in the time between the receipts of two consecutive updates.

A. Proof of Lemma 3
We first calculate the average age ∆(f A , u) defined in (6). Since the jamming time distribution is i.i.d., and since the sampling policy is stationary deterministic, the average age ∆(f A , u) over the infinite time horizon is equal to the average age of each stage game. Therefore, we have We can further simplify (20) when u = BR(f A ) (i.e., when u is best response), by observing that a + (β − a) + = max{β, a}.
Hence, we have At this point, the attacker's optimization problem (8) can be rewritten as Note that we need the first constraint to ensure that the system is choosing the best response sampling policy.

B. Proof of Lemnma 4
Since we have and we know that f * A satisfies the second constraint of (15). Now it remains to show that there exists a unique β = β * that satisfies Suppose that β = 0. Then (25) reduces to which is impossible. Suppose that β ≥ A max . Then (25) reduces to which is impossible. Therefore, we must have β ∈ (0, A max ). Then (25) reduces to β = 1 2 It is not difficult to verify that the only positive solution to the above equation is Hence, under f * A , the unique β that satisfies the first constraint of (15) is the β * defined in Theorem 1.

D. Proof of Lemma 6
The objective function is a ratio of the weighted sum of [max{β, a}] 2 to the weighted sum of max{β, a}, where the weight is determined by f A . Since [max{β,a}] 2 max{β,a} is nondecreasing in a, we should assign the largest possible weight when a = A max . However, the distribution needs to satisfy the average jamming time condition. The equilibrium distribution f * A has the largest f * A (A max ) among all the distributions that satisfy (2).