{'fraction_non_alphanumeric': 0.04245894896700098, 'fraction_numerical': 0.008827158540829563, 'mean_word_length': 4.106300484652666, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 4, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 1, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 5, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
A Dynamic Watermarking Algorithm for Finite Markov Decision Problems

Dynamic watermarking, as an active intrusion detection technique, can potentially detect replay attacks, spoofing attacks, and deception attacks in the feedback channel for control systems. In this paper, we develop a novel dynamic watermarking algorithm for finite-state finite-action Markov decision processes and present upper bounds on the mean time between false alarms, and the mean delay between the time an attack occurs and when it is detected. We further compute the sensitivity of the performance of the control system as a function of the watermark. We demonstrate the effectiveness of the proposed dynamic watermarking algorithm by detecting a spoofing attack in a sensor network system.

treated as disturbance inputs, and a monitoring system is required to detect against such deliberate attacks to secure the control. Leveraging control properties as invariants to monitor system's behavior and detect such attacks has been proposed in the past (in either passive style [13], [14] or active style [15], [16]). Dynamic watermarking, as one of these active defense technique for CPS, has been actively studied in recent years [17]- [19]. In dynamic watermarking, some random signals are deliberately added to the control actions as "watermark". As shown in Figure 1, the injected random signals excite a known response from the sensors following the plant dynamics. Actuator or controller can then determine if sensor or the communication link has been under attack by cross checking the covariance of the residual signal (i.e., sensor measurements) with the injected watermark.

A. Related Work
In the past decade, dynamic watermarking has been studied in the area of control security as an effective defense mechanism against numerous types of attack on the sensor feedbacks. And it has been shown that dynamic watermarking is effective against certain attack surfaces for the linear time invariant (LTI) system. For example, some early works applied Gaussian-based dynamic watermarking on the control signal to detect against replay attack [20], [21], integrity attacks [22], and stealthy attack [23]. [24] also considered attack surface is considered where a subset of control input can be manipulated by the attacker. Later, [25]- [27] introduced the distortion power as a general metric for arbitrary attack scenarios and developed testing scheme that ensures zero power distortion. In [28]- [30], the authors used securable and unsecurable subspaces of the linear dynamic system to analyze the capability of applying dynamic watermarking for a given system. SUch model was further generalized in [31] as an LTI system with partial state observations, and in [32] as a networked control system. Using dynamic watermarking to detect against attacks on sensors for real-world systems, such as robotics mobility platform [33], multi-vehicle transportation system testbed [34], and automatic power generation system [35] are also reported respectively.
While the dynamic watermarking has been studied for linear time invariant system with Gaussian disturbance, it has also been analyzed in the system with arbitrary non-Gaussian noise [36], linear time-varying systems [37], [38], and nonlinear systems [34], [39]. For example, [40] considered the linear system case when the covariance matrix of the measurement noise is unknown or slowly varying over the time. The dynamic watermarking has also been adapted into secure control system with both attack detection and mitigation. For example, [41] combined sensor switching as the mitigation strategy with the dynamic waterkaring as the detection strategy.

B. Contribution of the Paper
In this paper, we extend the dynamic watermarking algorithm to a finite Markov decision process (MDP). The watermark is added by changing the control policy of the controller. Compared with the linear/nonlinear model with dynamic watermarking, MDP model allows for more abstract elements (e.g., active and sleep) in the state and action space. In this paper, we propose a CUSUM-type detection scheme to detect whether the information coming from the feedback channel is authentic or has been compromised. We analyze the performance bound of the detection algorithm in terms of the detection delay and false alarms, and also the control loss due to introducing such watermarks into the system. We apply dynamic watermarking algorithm to detect a spoofing attack on a power management system in a sensor network. We demonstrate the trade-off between detection performance and control loss for different magnitude of the watermark applied to the system.

C. Outline
The paper is organized as follows: The system model is defined as a discrete time Markov decision problem in Section II. The attack and watermark (defense) policy embedded within the MDP formulation is defined in Section II-A, with the sequential hypothesis testing of detecting such an attack in Section II-B. The CUSUM-based detection scheme with its performance criteria is introduced in Section III. In Section IV, the loss between using the watermarked policy with the original policy is analyzed when there is no attacker present in the system. In Section V, we apply dynamic watermarking on a power management model for sensing network as the simulation, with trade-offs between the system loss and detection performance. In Section VI, we conclude the discussion and present our thoughts on the potential directions for the future work.

D. Notations
In this paper, We use [n] {1, 2, ..., n}. The vector 1 n means a n-dimensional vector with all ones. In the context of finite state and action space, denote X = {1, ..., n} and A = {1, ..., m} respectively with |X | = n and |A| = m. We use ℘(X ) to denote the set of probability measures over the set X . For discussion with two consecutive time steps, the index set i, l ∈ [n], j ∈ [m], are often used for state X t , observation Y t and action A t respectively at time t, with primes for time t+1. The history of state up to time t is defined as X t {X 1 , X 2 , ..., X t }, and similarly for the history of observations Y t and actions A t .
Subscript (·, ·) with brackets on is treated as an extension for state and action pair, where k = (i − 1)m + j is the corresponding index in the single index system. For example, η (i,j) means the (i − 1)m + j th element of the vector η, and P k,k means the element in the k th row and the k th column of the matrix P . Same terminology applies for P k,k = P (i,j),k with k = (i − 1)m + j.

II. PROBLEM FORMULATION
A discrete-time Markov decision problem is being considered with state space X , action space A, and state transition kernel R ∈ [0, 1] nm×n , where for i, i ∈ [n], j ∈ [m], and k = (i − 1)m + j. The observation available to the controller is Y t . Without an attack in the system, we assume the sensing is perfect, i.e., Y t = X t . We use γ : X → ℘(A) to denote a stationary Markov control policy of the controller, with Γ denoted as the set of all stationary Markov policies. The following assumptions are made for the control policy and system dynamics: The control policy γ ∈ Γ is stationary and Markov.
Assumption 2. The MDP satisfies: 1) The state and action spaces are finite sets.
The second condition in the above assumption is sometimes referred as the "Doeblin's condition", which is a sufficient condition for uniformly ergodic Markov chains. A Markov chain satisfying this condition has a unique stationary distribution and the convergence rate to the invariant distribution is geometric.
Denote h : X × A → R as the cost function, and α ∈ (0, 1) as the discount factor. The control performance using control policy γ without attack is measured by the total discounted expected cost where φ 0 is denoted as the null attack case, i.e., Y t = X t . Let γ * be the optimal stationary Markov policy for the above performance index.

A. The Attack Model
Now at some time τ the overall system is attacked by an adversary, who launches a deception attack in the feedback channel. If there is no attack, we can take τ = ∞. We make the following assumption for attack policy: Assumption 3. The attack policy φ ∈ Φ is stationary and takes up to two-steps of memory of the states.
The adversary thus transmits Y t to the controller according to a transition kernel φ ∈ Φ such that Y t ∼ φ(·|X t+1 , X t ).
Note that the space of Markov (one-step) attack policies is a subset of Φ. To see why the two-steps of memory assumption is important for more advanced attack, notice that if the realizations of X t and A t are both given at time t + 1, the attacker could then draw Y t+1 as another realization from the same distribution as [X t+1 |X t , A t ], which cannot be detected. For attack policy with one-step memory, the attacker only knows the realization instead of the distribution of X t+1 . However, if the attacker knows the history of the state, then the distribution of X t+1 can be estimated using X t andÂ t . Since the system dynamics and control policy are both Markov, the attacker doesn't necessarily need the entire history of the state to predict what A t is. In fact, {X t , X t+1 } is sufficient for the attacker to computeÂ t and therefore we consider the case when attack policy may take up to two-steps of memory.
When an adversary is present, one of the key ideas of applying dynamic watermarking to a linear system is to insert a random noise with a specific distribution along with the actuation signal. Let ν : X → ℘(A) denote the watermark andγ = (1 − β)γ * + βν denote the watermarked control signal with β ∈ [0, 1]. By using watermarked control policỹ γ instead of the optimal policy γ * , it naturally introduces a control loss with respect to J when β > 0. In Section IV, we include the detailed discussion of such loss under the no attack case but with the watermarked policyγ.
Similar to the analysis for the linear system case [26], we make the following assumptions. 2) The distribution of watermark ν and the watermark parameter β.
Note that the assumptions above only implies the distribution ofγ is known, but the realizations of the actions (a 1 , a 2 , . . .) are still kept secret from the attacker. We further assume that the system does not have prior knowledge of the attack strategy φ. Now the control performance under attack is captured by the total discounted expected cost: where A t ∼ γ(·|Y t ) and Y t ∼ φ(·|X t , X t−1 ).

B. Sequential Hypothesis Testing: Pre-vs Post-attack
In this section, we formulate the precise sequential hypotheses testing problem, whose goal is to raise an alarm when an attack is detected. This is equivalent to testing whether or not Y t = X t for all time t. Let P γ and P γ,φ denote, respectively, the transition kernel of the state (X t , A t ) under pre-attack scenario and under post-attack scenario. Note that the preattack matrix P γ only takes control policy γ as the input and the observation Y t is the same as X t . On the other hand, the post-attack matrix P γ,φ takes both the control and the attack policies as input, and the observations are generated according to the attack policy.
Recall that the size of the state and action space are |X | = n and |A| = m.
For any stationary Markov control policy γ ∈ Γ, the policy can be parameterized by a n × m probability matrix. With a little abuse of notation here, we denote such matrix as γ, Similar to the control policy, the attacker's policy can be parametrized by a n 2 ×n transition probability matrix φ where We now prove that this setting is a sufficient condition for the Markov relationship of {X t , A t } discussed above.
Lemma 1. Given a Markov policy γ : X → A and an attack policy with two steps memory φ : X × X → X , the induced system state and action pair {X t , A t } is a Markov process, under both pre-and post-attack phase with probability transition matrices P γ and P γ,φ respectively, where Proof: Please refer to Appendix A.
For a control policy γ and an attack policy φ, the null and alternative hypotheses at time t are defined as H a : Under Attack -{(X t , A t )} t is generated according to a Markov model with a unknown transition matrix P γ,φ . Now if the node conducting the hypothesis testing has the knowledge of {X t , A t }, it becomes an online change detection problem of Markov observations with unknown post-change probabilities, which has been studied recently in [42]. The challenge here is that the controller only observes {Y t , A t } where Y t is reported by the attacker in the post-attack case. As a result, the change detection algorithms observes a non-Markovian process {Y t , A t } in the post-attack case. This further implies the results of [42] are not directly applicable. In fact, this non-Markovian property holds for Markov attack policy as well. Instead, we show in Section B that {X t , Y t , A t } t∈N forms a Markov chain and apply Hoeffding inequality for functions of Markov chain to detect a change in the transition probability. The details of this algorithm are described below.

III. CHANGE DETECTION FOR DYNAMIC WATERMARKING
To deal with the challenge discussed above, we define a CUSUM-type detection scheme for the sequential hypothesis testing problem as a function of observation and action pair. We first define the indicator function as The counting variables are defined as The test statistic available to the controller, is defined as where If n k:n l,j = 0, we letq k:n l |l,j = 0 for all l ∈ X . The CUSUM test statistic is defined as where M is the minimum number of observations required to estimate the post-attack transition probabilities. The detection scheme is then defined as where c is the threshold for the CUSUM test statistic. To analyze the detection performance, the criteria considered in this paper are: mean delay (MD) if there is an attack at unknown time τ < ∞ and mean time between false alarms (MTBFA) if there is no attack, or equivalently τ = ∞. Letting T := T (c, M ), the MD and MTBFA is defined as Without loss of generality, we may assume that τ = 0 and MD = E τ =0 [T ]. In Section III, the delay and false alarm performance of using (3) will be discussed.

A. Performance Bounds on Delay and False Alarm
Since the state space X t during pre-attack case satisfies assumption 2 and the observation Y t is the same as the true state X t , the results in [42] can be directly applied for MTBFA. We state the results as follows.
Proof: Please refer to (i) of Theorem 1 in [42].
To calculate the mean delay (MD), notice that the state space X t is no longer directly available to the controller, thus the result in [42] does not directly apply. We show in Section B that (X t , Y t , A t ) t∈N forms a Markov chain satisfying the Doeblin condition. Thereafter, we apply Hoeffding inequality for functions of Markov chains to establish the following result.
Theorem 3. Suppose that the Markov chain X t satisfies Assumption 2 before attack. Thenq k:n l |l,j P → Q l |l,j , for some matrix Q as n → ∞. Further, assume that with λ 1 and π Y,A defined in Lemma 7 and Equation (12) in Section B respectively .
Proof: Please refer to Section B.
The assumption of zero elements in Q and R being the same ensures certain level of stealthiness of the attack. In other words, it will be trivial for the controller to raise an alarm if the observation it received has probability zero to occur according to the pre-attack dynamics R, conditioned on the last-step observation and action pair. Note that if the original policy is deterministic, then for any fixed attack policy φ, λ 1 is linear in β according to Equation (9) in Section B.
Overall, we notice that the upper bound on the mean delay increases linearly with respect to the threshold c, when the second term in the maximum dominates. And it is hard to draw such relationship directly between the mean delay and the strength β of the watermark since the stationary distribution matrix Q also depends on β. In Section V, we numerically compare the detection performance in terms of the mean delay for different values of β, and with a constraint of minimum mean time between false alarms (MTBFA).

IV. PERFORMANCE LOSS WITH DYNAMIC WATERMARKING
To analyze the performance difference between the system with the original optimal policy γ * and the watermarked policỹ γ under no attack case, we apply some existing results in the literature of perturbation analysis. Recall that the system evolves based on Denote the γ-policy induced probability matrix the state X t as S γ , we have Without watermark, γ * is defined as the optimal control policy, with L γ * as the corresponding probability transition matrix for X t . Now with watermark ν, the system changes toγ = (1 − β)γ * + βν, with where L ν is the state transition matrix that is induced purely by the watermark policy ν. Given the control policy γ, consider the performance cost as a column vector η(γ), where where h γ (i) = j h(i, j)γ i,j is the cost function. For small values of the watermark magnitude β, we now compute the control loss after applying watermark to the original policy.
To introduce the result, we first define g α : Γ → R |X | , the socalled α-potential, which measures how the discounted cost using control policy γ ∈ Γ differs from the average cost, for any given initial state X 0 . The i th of g α (γ) is defined as where for a given policy γ, h γ ∈ R |X | is the cost,η γ = E πγ (h γ ) is the average cost, and π γ is the stationary distribu-tion over the state space under the policy γ. The matrix form can be then written as with e as a vector with all ones and π γ is construed as a row vector.
The following lemma computes the perturbation in the performance index of Markov chain as a function of the transition matrix.
Lemma 5. Let L γ and L γ be two irreducible transition probability matrices on the same state space and g α (γ) be the alpha potential under L γ . Denote η(γ) and η(γ ) as the discounted performance cost with discount factor α ∈ (0, 1), for L γ and L γ respectively. Then, Proof: Please refer to Section 4 and 5.1 in [43]. Compared with the reference, note that the definition of discounted performance cost η(γ) i in (5) has been changed without (1−α) term in the front. This change also reflects the deletion of (1 − α) term in (6).
Given any control policy γ and a discount factor α, define A γ I − αL γ . Applying the above result on a system with optimal policy γ * and watermarked policyγ implies where (a) follows from (4) and (b) follows from the perturbed matrix inversion formula in Section 5.1.10.2 of [44]. Now if the watermark distribution is fixed, or equivalently L ν is fixed, then taking derivative with respect to β yields This result further implies that the loss of control performance increases linearly for small magnitude of the watermark, where the rate of such loss depends on the choice of ν. As we discussed at the end of Section III, now we have showed that both control and detection performance can be derived as a function of the watermark strength denoted by β. This introduces a trade-off of between how quickly we can detect an attack and how good the watermarked policy is in terms of control performance as compared to the original policy. In the next section, we discuss a numerical simulation to illustrate this trade-off.

V. APPLICATION OF DYNAMIC WATERMARKING ON POWER MANAGEMENT FOR SENSING NETWORK
The attack and detection scheme is applied as a security measure on a simplified version of the dynamic power management framework introduced in [45]. The overall structure of applying dynamic watermarking on this system is shown in Figure 2.

A. System Model
Consider a discrete-time Markov decision process consisting a power manager, a sensing node, a transmission node, and a queue. The state of the system denoted by X t = [X 1,t , X 2,t ] T is defined as a two-dimensional vector. Here, X 1,t ∈ {0, 1} represents the state of the sensing node at time t, with 0 as sleep and 1 as active, and X 2,t ∈ {0, 1, ..., n queue } is defined as the number of packets in queue. We denote Y t here as the reported state to the power manager which belongs to the same space as X t . Without attack, we assume X t = Y t . The action taken by the power manager is denoted by A t ∈ {0, 1}, where A t = 0 (1) refers to an eco (performance) mode for the sensing node. The transition probability matrix for the sensing node is a function of A t which can be parameterized by following: where i, i , j ∈ {0, 1} and p 0 < p 1 .
When the sensing node is active (i.e., X 1,t = 1), it measures the environment and sends a packet reflecting current scene to the queue. We then assume that there is a probability of scene change p scene which is independent across the time and also independent of the state of the sensing node. If there is a scene change at some time t while the sensing node is in sleep, we say that there is a scene miss at time t. The queue is considered as first come first service, and the transmission node is assumed to be memoryless with rate r trans .
We consider the step cost as for ρ > 0. Note that scene change occurs independently with respect to the state and action, thus X 1,t+1 = 0 implies that a scene miss will occur at time t + 1 with probability p scene . Therefore, the second term in the cost function is a soft constraint on the scene miss rate. Overall, this model is equivalent to a M/M/1 queuing system, where the arrival rate can be adjusted by the manager with two levels. In the queuing literature, such adjustment can be achieved by adjusting the price of the customer entering the system, and the set of price in our case is {ρp 0 , ρp 1 }. Such an MDP is studied in [46] and the author established the existence of an optimal policy that is threshold based. Accordingly, we consider two types of policies here: • Deterministic policy: Given a threshold l, the manager will send A t = 1 with probability 1 if the current queue length does not exceed the threshold (X 2,t ≤ l), otherwise send A t = 0 with probability 1. • Stochastic/watermarked policy: Similar to the previous case, the manager will send A t = 1 with probability 1−β if the current queue length does not exceed the threshold, otherwise send A t = 0 with the same probability 1 − β.

B. Attack and Detection Scheme
We consider a stealthy attack in this setup where at some unknown time τ , the attacker starts to manipulate the observation Y t . The attacker generates Y t according to the same system dynamics and control policy, and we assume that the attacker has the knowledge of both of them. Note that although the control policy is known to the attacker, the actual control decision is kept secret from the attacker. That is, if the control policy is deterministic, then the attacker knows exactly what the control will be. However if the control policy is stochastic, then the attacker only knows the distribution of the control as a function of state. To simulate the next observation, the attacker generates a realization of the control decision which may not be the same realization that is generated by the authentic controller. Therefore, dynamic watermarking applied on the close-loop stochastic policy forces a correlation between the realization of control decision and observation. In Figure 3b and 3c, the data points with β = 0 on the x-axis implies optimal policy with no watermark and is served as the base model. The CUSUM-based detection scheme is then constructed as follows. First, we define the space Ω sim as The test statistic is defined as is the estimator of σ ii (j) based on observations Y 1,k , ..., Y 1,t+1 , which is defined as σ k:n ii (j) = n k:n ii (j)/n k:n i (j). Given {Y 1,k:t+1 } and control decision is j, n k:n ii (j) counts the number of times observation Y 1,t visiting from state i to i , and n k:n i (j) counts the number of times observation Y 1,t starting from state i. The CUSUM statistic and stopping rule for the detection scheme is then defined as

C. Simulation Setup, Results, and Discussion
In the simulation, we set the queue length to be n queue = 20, the sensing node's transition probabilities to be p 0 = 0.2 and p 1 = 0.8. The probability of scene change is p scene = 0.5, service rate of the transmission node is r trans = 0.8. We set ρ = 20 for the cost h and α = 0.5 for the total discounted cost J. The simulation is set to stop after 10 4 steps, if there is no alarm reported by the detector.
The control performance of threshold-type deterministic policies with l ∈ {1, 2, ..., 10} are shown in Figure 3a. The optimal threshold l * = 3 found numerically is chosen to test the watermark performance in terms of control loss and detection delay. To numerically check the results in Theorem 4, Figure 3b shows the control loss for small watermark magnitude β, with an approximately linear slope. The control performance with no watermark but with attack is −11.65, which is considerably higher than the control loss introduced by the watermark.
For detection, we set c = 15 and M = 10, and the resulting mean time between false alarms (MTBFA) is no less than 7500 simulation steps for each cases. The box plot for mean delay is shown in Figure 3c. The mean delay converges for β bigger than 0.05. One instance of the CUSUM score for β = 0.05 is shown in Figure 4. Figure 4a shows the CUSUM score with watermark and no attack, which is stable and never exceeds the threshold. Figure 4a shows the CUSUM score with watermark and attack, which blows up. For Figure 4c, since the control policy without watermark is deterministic, the attacker could perfectly predict controller's decision and thus could create a virtual system with the exact dynamics but different set of realizations. In this case, the attack could gradually drive the system to a wrong state without raising an alarm. By comparing the control loss and the security gain (mean delay), it is clear that a stronger watermark leads to a higher control loss, but a better detection delay.

VI. CONCLUSION
This paper has developed dynamic watermarking in a finite MDP setting with CUSUM-like detection scheme. Unlike the LTI sytem, the setup introduced in this paper allows the state space of the system to be abstract, such as active and sleep in the power management application. We have provided a CUSUM-like detection scheme to detect whether the sensing output is the same as the true state of the system. We have presented theoretical performance guarantee of the detection scheme under the watermarked policy. The efficacy of the detection scheme has been tested in the power management system for sensing network. In the future, the finite MDP setup can be extended to a countably infinite state and action set for a wider set of applications, and distributed watermark can also be analyzed to a set of networked controllers with correlated observations for better scalability.

APPENDIX A PROOF OF LEMMA 1
In the pre-attack phase, we notice that given Y t = X t and γ is a Markov policy, we have A t |X t d = A t |X t . The state and action pair {(X t , A t )} t in the pre-attack phase trivially satisfies the Markov property.
In the post-attack phase, notice that the following forms a Markov relationship: By applying Bayes rule and Markov property, we have Note that the probabilities calculated above is with respect toγ and φ, and the subscripts are omitted to simplify the notations. Also note that A t in the conditional probability of Y t+1 in equality (a) is a dummy variable such that it is easier to combine probabilities in equality (b).
The pre-attack dynamics, or the γ-induced transition probability matrix P γ that is known to controller is where . Note that the equality (a) in (7) holds because of Y t+1 = X t+1 during the pre-attack phase.
Since the post-attack dynamics {X t , A t } is still Markov, we can define the post-attack transition probability matrix as P γ,φ , where

APPENDIX B PROOF OF THEOREM 3
By assumption, the state space X t in post-attack case still satisfies assumption 2 with parameter (m, λ). In this proof, we will first show that this property passes to the extended state Z t = (X t , A t , Y t ) and then further to the sequential pair of the extended state space Z t:t+1 = (Z t , Z t+1 ). This will allow us to utilize a Hoeffding-like inequality for the multivariate Markov chain, and such inequality further implies a concentration bound on the test statistic defined in (1). We will list this sequence of results here as the first part of the theorem proof. where λ = λγ min φ min , and γ min is the minimal non-zero element in the transition matrix γ, which can be defined as The same applies to φ min for the transition matrix φ.
Proof: Please refer to Appendix C.
This result shows that the extended Markov chain Z t under the state space Ω(φ, γ) is also uniformly ergodic, where For all discussion below, stationary distributions are with respect to γ and φ. For simplicity of notations, π is used without a lower script of γ and φ. The uniform ergodicity implies that there exists stationary distribution where Given the extended state space Z t is uniformly ergodic, we prove the following inequality for a function of Z t:t+1 .
Proof: Please refer to Appendix D.
Note that R min is determined by the system itself with transition matrix R, φ min and γ min can be independently picked by the attacker and controller with policy matrix φ and γ respectively. Now with the concentration bound of a function of Z t:t+1 proved above, we will then prove the limiting distribution of the estimators mentioned in the test statistic so combining the two will give us the concentration around the limiting distribution.
Proof: Please refer to Appendix E.
Finally, with the results stated above, the delay performance of using T (c, M ) defined in (3) can be derived as following. We recall that the estimator of π Y,A and Q = {π Y |Y,A l |l,j } are defined asπ Y,A (k, n) andQ k:n = {q k:n l |l,j } wherê π Y,A l,j (k, n) = n k:n l,j /(n − k),q k:n l |l,j = n k:n l |l,j /n k:n l,j . By the results in Lemma 8, we havê The relative entropy ofQ k:n and Q is non-negative, this implies Note that for any fixed (γ, φ) pair, (r, r ) = (i, j, l, i , j , l ) ∈ Ω(γ, φ) directly implies that the corresponding subcomponents belong to Ω X (γ, φ), Ω Y (φ), and Ω A (γ). For example, it implies that (i, i , j) ∈ Ω X (γ, φ). As a result, R min , φ min and γ min can be used as lower bounds under Ω(γ, φ). By the results in Lemma 7, and assuming the attack starts at t = 0, we have P(S 0:n < c) for any n > max M, c+α I(Q,R) . After the test statistic S 0:n defined in this paper is bounded above using Lemma 7 and 8, the remaining proof of the theorem follows the same lines of proof of the MD in Theorem 1 of [42], from Equation (14) to Equation (15).

APPENDIX C PROOF OF LEMMA 6
We will first show that Z t = (X t , A t , Y t ) is Markov: Then the preservation of assumption 2 for Z t can be shown as the following. We use S, A, and Z to denote measurable subsets drawn from the state space S and action space A, and the extended space S × A × S respectively. Recall that by assumption there exists an integer m > 0, a real number λ, and a probability measure ψ X on X such that for any S 1 ⊂ X and i ∈ X we have P φ,γ (X m ∈ S 1 |X 0 = i) ≥ λψ 1 (S 1 ).

APPENDIX E PROOF OF LEMMA 8
The stationary distribution of observation given previous observation and action pair can be calculated as π Y |Y,A (l |l, j) φ l |i,i R (i,j),i π(i, l, j) π Y (l)γ l,j .
This completes the proof.