Sensor Network Attack Synthesis against Fault Diagnosis of Discrete Event Systems ^†

We first review some common notations of DESs used throughout this paper; the reader is referred to [6] for more details. It is assumed that a DES to be diagnosed is modeled as a finite-state automaton (automaton for short) $G=(Q,\mathrm{\Sigma },\delta ,q_0)$, where Q is the finite set of states, $\mathrm{\Sigma }$ is the finite set of events, $\delta :Q\times \mathrm{\Sigma }\to Q$ is the partial transition function, and $q_0\in Q$ is the initial state. Suppose that set $\mathrm{\Sigma }$ is divided into the observable event set ${\mathrm{\Sigma }}_o$ and the unobservable event set ${\mathrm{\Sigma }}_{uo}$. The set of active events at state q is defined as $\mathrm{\Gamma }\left(q\right)=\{\sigma \in \mathrm{\Sigma }|\delta (q,\sigma )!\}$, where “!” means “defined”. The language generated by G, denoted by $L\left(G\right)$ or simply L, is defined as $L=\{s\in {\mathrm{\Sigma }}^{*}\mid \delta \left(q_0,s\right)!\}$, where ${\mathrm{\Sigma }}^{*}$ denotes the Kleene closure of $\mathrm{\Sigma }$. Let s denote a word of L. The set of the prefixes of s is denoted as $\overline{s}=\{u\in {\mathrm{\Sigma }}^{*}|(\exists v\in {\mathrm{\Sigma }}^{*})[uv=s]\}$.

The natural projection $P:{\mathrm{\Sigma }}^{*}\to {\mathrm{\Sigma }}_o^{*}$ is defined as (where $\epsilon$ is the empty word) The inverse projection $P^{-1}:{\mathrm{\Sigma }}_o^{*}\to 2^{{\mathrm{\Sigma }}^{*}}$ is defined as $P^{-1}\left(w\right)=\{s\in L\left(G\right)|P\left(s\right)=w\}$, i.e., $P^{-1}\left(w\right)$ consists of all words s in $L\left(G\right)$ whose observations are w.

Let $G_1=(Q_1,{\mathrm{\Sigma }}_1,{\delta }_1,q_{01})$ and $G_2=(Q_2,{\mathrm{\Sigma }}_2,{\delta }_2,q_{02})$. The parallel composition between $G_1$ and $G_2$ is defined as $G_1\Vert G_2=Ac(Q_1\times Q_2,{\mathrm{\Sigma }}_1\cup {\mathrm{\Sigma }}_2,\delta ,(q_{01},q_{02}))$, where $\delta [(q_1,q_2),\sigma ]=(q_1^{\prime },q_2^{\prime })\mathrm{if}{\delta }_1(q_1,\sigma )=q_1^{\prime }$ and ${\delta }_2(q_2,\sigma )=q_2^{\prime }$; $\delta [(q_1,q_2),\sigma ]=(q_1^{\prime },q_2)\mathrm{if}{\delta }_1(q_1,\sigma )=q_1^{\prime }$ and $\sigma \notin {\mathrm{\Sigma }}_2$; $\delta [(q_1,q_2),\sigma ]=(q_1,q_2^{\prime })\mathrm{if}{\delta }_2(q_2,\sigma )=q_2^{\prime }$ and $\sigma \notin {\mathrm{\Sigma }}_1$; otherwise, it is undefined. In the definition of $G_1\Vert G_2$, $Ac(·)$ denotes the accessible part of an automaton.

In the literature of fault diagnosis in DESs, the unobservable event set ${\mathrm{\Sigma }}_{uo}$ is further partitioned into the set of regular unobservable events ${\mathrm{\Sigma }}_{reg}$ and the set of fault events ${\mathrm{\Sigma }}_f$. Let $\mathrm{\Psi }\left({\mathrm{\Sigma }}_f\right)=\{sf\in L\mid s\in {\mathrm{\Sigma }}^{*},f\in {\mathrm{\Sigma }}_f\}$ denote the set of all finite words in L that end with a fault event f. With some abuse of notation, ${\mathrm{\Sigma }}_f\in s$ denotes that $\overline{s}\cap \mathrm{\Psi }\left({\mathrm{\Sigma }}_f\right)\ne \varnothing$. A word s is said to be faulty (resp., normal) if ${\mathrm{\Sigma }}_f\in s$ (resp., ${\mathrm{\Sigma }}_f\notin s$). The fault diagnosis problem in a DES aims to decide, using the current observation $w\in {\mathrm{\Sigma }}_o^{*}$, if a fault has already occurred or not. To solve this problem, one wishes to build a diagnosis function $\gamma :{\mathrm{\Sigma }}_o^{*}\to \{N,F,U\}$ associating each observation to a diagnosis state such that In other words, an observation w is called normal if $\gamma \left(w\right)=N$ since, in this case, no word producing w contains a fault; faulty if $\gamma \left(w\right)=F$ since, in this case, all words producing w contain a fault; ambiguous otherwise. A standard way to compute the diagnosis function is by using a diagnoser. The diagnoser of G is defined as

Its construction procedure is detailed in [6]. By construction, it holds $L\left(Diag\right(G\left)\right)=P\left(L\right(G\left)\right)$. The diagnoser state space $Q_d$ is a subset of $2^{Q\times \{N,F\}}$. The diagnoser allows one to associate every state to a diagnosis value $\gamma \left(q_d\right)=\gamma \left(w\right)$, where $q_d={\delta }_d(q_{d,0},w)$. The diagnoser state $q_d$ is negative if $\gamma \left(q_d\right)=N$; positive if $\gamma \left(q_d\right)=F$; uncertain if $\gamma \left(q_d\right)=U$. Figure 2a shows a plant G, where ${\mathrm{\Sigma }}_o=\{a,b,d,e\}$, ${\mathrm{\Sigma }}_{uo}=\{c,f\}$, and ${\mathrm{\Sigma }}_f=\left\{f\right\}$. The corresponding diagnoser is shown in Figure 2b.

In our previous work [24], we detail the constructions of two special diagnosers, called Attacker Diagnoser and Operator Diagnoser. The former diagnoser describes all attack words $w_a$ that can be generated under attack. The latter diagnoser describes how all words $w_a\in {\mathrm{\Sigma }}_a^{*}$ are recognized by the operator. Starting from a diagnoser $Diag\left(G\right)=(Q_d,{\mathrm{\Sigma }}_o,{\delta }_d,q_{d,0})$, we build the following:

By Statement (1) in Proposition 1, the language of the attacker diagnoser consists of all possible attack words w. According to Statement (2), the diagnosis state estimation of $Dia{g}_{att}\left(G\right)$ based on w is the same as that of $Diag\left(G\right)$ based on s, where $w_a=\xi \left(w\right)$.

By Statement (1) in Proposition 2, all words in ${\mathcal{S}}_s$ and ${\mathcal{S}}_e$ can be generated by $Dia{g}_{opr}\left(G\right)$. By Statement (2), a word in ${\mathcal{S}}_s$ generated by $Dia{g}_{opr}\left(G\right)$ can correspond to a corrupted observation $w^{\prime }\in P\left(L\left(G\right)\right)$ recognized by the operator. Statement (3) implies that (i) the diagnosis state estimation of $Dia{g}_{opr}\left(G\right)$ based on a stealthy word $w_a\in {\mathcal{S}}_s$ is the same as that of $Diag\left(G\right)$ based on $w^{\prime }$, where $w^{\prime }=\widehat{P}\left(w_a\right)$; (ii) all exposing words $w_a\in {\mathcal{S}}_e$ yield $q_{\varnothing }$.

As defined, every state of J-$Diag\left(G\right)$ is a pair $x=(q_d,{\overline{q}}_d)$. The states of J-$Diag\left(G\right)$ can be partitioned into stealthy states and exposing states as follows.

If an exposing word $w_a\in {\mathcal{S}}_e$ yields an exposing state, we conclude that the attacker that produces $w_a$ is stealthy. However, if a stealthy word $w_a\in {\mathcal{S}}_s$ yields a stealthy state, it can only be inferred that the attacker producing $w_a$ is currently undiscovered. There is a case where, following the future evolution of G, the attacker will be inevitably discovered. This leads to the notion of a weakly exposing region, denoted as $X_{we}\supseteq X_e$, which can be computed iteratively by a procedure in [21]. In the first iteration,

The remaining iterations are executed similarly to Equation (4). We do not present the complete procedure here for the sake of brevity but illustrate it via Example 2. Dually, we define the strongly stealthy region as $X_{ss}=X\setminus X_{we}\subseteq X_s$.

The resulting SJD is obtained by removing all states in $X_{we}$ from a JD and taking its accessible part. Then, we define a subset of the states of $SJ$-$Diag\left(G\right)$, called pre-empting states, which will be used in the procedure to extract an attack function from $SJ$-$Diag\left(G\right)$.

A state $x_{ss}\in X_{ss}$ is pre-empting if i) there exists an event $\sigma \in {\mathrm{\Sigma }}_o$ whose occurrence (even if erased) causes J-$Diag\left(G\right)$ to lead outside $X_{ss}$; ii) however, $\sigma$ can be definitely pre-empted by inserting an appropriate word of events in ${\mathrm{\Sigma }}_{+}$ to reach a state in the strongly stealthy state. This state captures the races between inserted events and internal system events. Specifically, at a pre-empting state, the inserted word must be performed before the execution of event $\sigma$. In Example 2, state $\left(\right\{3F\},\{0N\left\}\right)$ is a pre-empting state (highlighted in green), where event d must be pre-empted by inserting a fake event $e_{+}$ to reach a state $(\left\{3F\right\},\{5N,6N\})\in X_{ss}$; otherwise, the occurrence of $d\in {\mathrm{\Sigma }}_o\setminus {\mathrm{\Sigma }}_{era}$ will take $\left(\right\{3F\},\{0N\left\}\right)$ to an exposing state $(\left\{4F\right\},\left\{d_{\varnothing }\right\})$.

In order to synthesize an attacker, the following definition is first required.

The following objective is to show how an attacker may determine an attack function from an SJD. In [21], an algorithmic procedure is presented for this purpose. The main idea is to select attack words that do not end in any state that has an inserted event as a successor transition, of course, including the pre-empting state. Compared with [21], it is now expected to synthesize the attack function producing an attack word that only does not end in pre-empting states. This means that an attacker cannot stay in the pre-empting state when determining its attack function. Now, we provide the following attacker synthesis algorithm, i.e., Algorithm 1.

Algorithm 1 Synthesis of the corrupting function $\varphi$

Require: $G=(Q,\mathrm{\Sigma },\delta ,q_0)$ and $SJ$-$Diag\left(G\right)=(X_{ss},{\mathrm{\Sigma }}_a,{\delta }_{sa},$$x_0)$ Ensure: corrupting function $\varphi \in \Phi$ 1: $\varphi \leftarrow Synth\left(SJD\right)$ 2: procedure Synth($SJD$) 3:       initialization: $w\leftarrow \epsilon$ 4:       select a word $w_{a,+}\in L_{+}(SJ$-$Diag\left(G\right),x_0)$ 5:       $\xi \left(w\right):=w_{a,+}$; $\varphi \left(w\right):=\widehat{P}\left(\xi \left(w\right)\right)$ 6:       $x_{ss}:={\delta }_{sa}\left(x_0,w_{a,+}\right)$ 7:       while a new observable event $\sigma \in {\mathrm{\Sigma }}_o$ is produced by G do 8:            $I:=\varnothing$ 9:            if $\sigma \in {\mathrm{\Gamma }}_{SJ}\left(x_{ss}\right)$ then $I:=I\cup \left\{\sigma \right\}$ 10:          if ${\sigma }_{-}\in {\mathrm{\Gamma }}_{SJ}\left(x_{ss}\right)$ then $I:=I\cup \left\{{\sigma }_{-}\right\}$ 11:          select an event ${\sigma }^{\prime }\in I$ and a word $w_{a,+}\in L_{+}(SJ$-$Diag\left(G\right),{\delta }_{sa}(x_{ss},{\sigma }^{\prime }))$ 12:          let $w_a:={\sigma }^{\prime }{w}_{a,+}$ and $w_a^{\prime }\in \{{\sigma }^{\prime },w_a\}$ 13:          let $x_{ss}:={\delta }_{sa}(x_{ss},{\sigma }^{\prime })$ 14:          if $x_{ss}\in X_{np}$ then $\xi \left(w\sigma \right)\in \xi \left(w\right)w_a^{\prime }$ and $x_{ss}:={\delta }_{sa}(x_{ss},w_a^{\prime })$ 15:          if $x_{ss}\in X_p$ then $\xi \left(w\sigma \right):=\xi \left(w\right)w_a$ and $x_{ss}:={\delta }_{sa}(x_{ss},w_a)$ 16:          $\varphi \left(w\sigma \right):=\widehat{P}\left(\xi \left(w\sigma \right)\right)$ 17:          $w\leftarrow w\sigma$ 18:     end while 19: end procedure

This algorithm may recursively associate each observation generated by G with a corresponding attack word. We now briefly explain how it works. When no event is generated by G, the attacker may insert a suitable word $w_{a,+}$ in the set $L_{+}(SJ$-$Diag\left(G\right),x_0)$ (Steps 3 and 4). In Step 5, $\xi \left(\epsilon \right)$ is computed, and the new current state $x_{ss}$ of $SJ$-$Diag\left(G\right)$ is updated. Then, we wait for G to generate a new observable event $\sigma$ (Step 7). A new set I initialized at the empty set is defined. If $\sigma$ is enabled at $x_{ss}$, $\sigma$ is added to I. If ${\sigma }_{-}$ is enabled at $x_{ss}$, ${\sigma }_{-}$ is added to I (Steps 8 to 10). In Step 11, an event ${\sigma }^{\prime }\in I$ and the insertion of a word $w_{a,+}\in L_{+}(SJ$-$Diag\left(G\right),{\delta }_{sa}(x_{ss},{\sigma }^{\prime }))$ are selected. If the current state $x_{ss}$ with the occurrence of ${\sigma }^{\prime }$ is a non-pre-empting state, an attack word $w_a^{\prime }$ is produced, which is either ${\sigma }^{\prime }$ or the concatenation of ${\sigma }^{\prime }$ and $w_{a,+}\in L_{+}(SJ$-$Diag\left(G\right),{\delta }_{sa}(x_{ss},{\sigma }^{\prime }))$ (Step 14). Otherwise, another attack word $w_a$ is produced as the concatenation of ${\sigma }^{\prime }$ and $w_{a,+}$ (Step 15). The corresponding corrupting function is computed in Step 16. Step 17 updates the observation w to $w\sigma$. This procedure goes to Step 7 when a new observable event is generated by G.

According to the property of the SJD, the above results trivially hold, which means that the corrupting function synthesized by Algorithm 1 must be stealthy. Using the notion of pre-empting states, we provide a characterization of the SJD as follows.

According to the above result, a state pair $x_{ss}=(q_d,{\overline{q}}_d)$ in the joint diagnoser reached by an attack word $w_a$ represents the joint diagnosis state estimation, where $q_d$ describes the original diagnosis state estimation of the attacker based on the original observation w, where $w_a=\xi \left(w\right)$, and ${\overline{q}}_d$ describes the corrupted diagnosis state estimation of the operator based on the corrupted observation $w^{\prime }=\widehat{P}\left(w_a\right)$.

Finally, we conclude this section by the complexity analysis of the proposed approach. Let $Diag\left(G\right)$ be a nominal diagnoser with $|Q_d|$ states. By construction, the attacker diagnoser $Dia{g}_{att}\left(G\right)$ has the same set of states of $Diag\left(G\right)$, and so does the operator diagnoser $Dia{g}_{opr}\left(G\right)$ except for the dump state $d_{\varnothing }$. Since the JD J-$Diag\left(G\right)$ is the parallel composition of $Dia{g}_{att}\left(G\right)$ and $Dia{g}_{att}\left(G\right)$, its maximum number of states is $|Q_d|\times |Q_d+1|$. Hence, the complexity of building an SJD is $O\left(\right|Q_d{|}^2)$, which is polynomial in the number of states of the nominal diagnoser. However, it is well known that the construction of the diagnoser is worst-case exponential in the number of states in the system. Hence, the overall computational complexity of an SJD is exponential in the number of states of G.

As discussed above, it is intuitive that the presence of a harmful state in the SJD is related to Problem 2, the existence of a successful attacker.