Local identification of sensor attack and distributed resilient state estimation for linear systems

Published in: IEEE Conference on Decision and Control (CDC) 2018
Authors: Junsoo Kim, Jin Gyu Lee, Chanhwa Lee, Hyungbo Shim, Jin H. Seo
Abstract: This paper presents a distributed attack-resilient state estimation scheme for continuous-time linear systems having redundant sensors when some of them are corrupted by adversaries. We first design a distributed state observer so that individual observers from each of output measurements communicate with their neighbors and cooperate to recover the full state of the system. Then, the observers are partitioned into disjoint groups and local monitoring systems are designed for each of them. Even though the system is not observable from measurements in each group, every influential attack is detected and identified by local monitors using only local information and local observer estimates within the local group, with the help of sensing redundancy. In process of local attack identification, a notion of sensor attack identifiability is introduced which does not require observability. Finally, all corrupted output measurements are removed from the observer communication and the distributed resilient state estimation is achieved.

DOI: 10.1109/CDC.2018.8619126
Presentation material: CDC2018_JunsooKim

Distributed resilient state estimation problem?

We start with the issue of malicious sensor attacks on control systems. Since networked control systems became known as vulnerable to cyber-sensor attacks, those situations have been formulated as the following signal injection into output variables. Let the plant be given as

which has $p$ -sensors. Here the attack $a(t)$ is unknown and its size might be arbitrary large, and it is different from the conventional fault signals or disturbances because it might be carefully designed not to be detected at the controller.

As a defender, resilient state estimation problem has been formulated in recent years. From the rationale that the attack resource is limited in usual it is commonly assumed that up to $q$ -sensors are attacked out of $p$ -sensors. The objective of this problem is to identify unattacked $p-q$ sensors and carry out state estimation with those identified sensors.

For the first topic of this article, we will briefly review that resilient state estimation problem

is solvable when the plant has many redundant sensors.
is known as generally combinatorial in nature.

For this, let us briefly illustrate an existing scheme [1] for identification of unattacked sensors. Suppose there are 5-sensors and 2-attacks so the problem is to find 3-unattacked-sensors. The first step is to prepare a detection scheme for each selection of 3-sensors such that the detection alarm rings if and only if those indicated selection includes an attacked sensor. If there is an attack alarm, it means the selection includes an attacked sensor, and otherwise if there is no attack alarm, it guarantees that the selection is identified as attack free.

Then, identification of unattacked sensors can be achieved by inspection of $p$ choose $q$ cases. Applying the detection scheme for each selection one by one, it eventually finds out a set of unattacked sensors.

This identification scheme is valid for $2q$ –redundant observable systems. The notion $2q$ -redundant observability means the systems is observable from any $p-2q$ sensors. For the formal definition the pair $(A,C)$ is said $2q$ -redundant observable if its observability matrix has full column rank even though any $2q$ -rows are removed from the output matrix. Under this condition, every injection of $q$ -sensor attacks is identifiable so that the problem of resilient state estimation is solvable.

Based on $2q$ -redundant observability, various solutions have been presented such as observer based approach or nonlinear generalization. However, this problem is generally NP-hard, and is combinatorial in nature in most cases. This nature can be found in literature. For example, in the results, it constructs combinatorially many observers, or the cardinality of searching space for optimization is $p$ choose $q$ . In the scheme described above, as well, it also generally needs combinatorially many inspections. so the thing is, they require a substantial computational effort as the number of sensor increases.

However, local identification can avoid this combinatorial explosion. For example, suppose there are $p=45$ sensors and $q=6$ attacks. In the existing centralized problem, we must consider as much as 45 choose 6 cases. But if we can give a partition to the sensors and divide it into 3 identification problems, then we can divide the number $p$ by 3, and it will drastically reduce the cases. Again in general, if we can give a partition to the sensors and divide it into local problems, it will reduce the computational complexity.

So, we propose distributed resilient state estimation. From now on, we consider $p$ -sensors partitioned into $k$ -local groups as follows

in which the index set $P_1$ to $P_k$ is nothing but for the partition so that their disjoint union is equal to the set $\{1,2,...,p\}$ , and the stack of the matrices from $C_{P_1}$ to $C_{P_k}$ is just the same with the matrix $C$ . From now on, for each local sensor group, only local output $y_{P_l}$ is considered, up to $q$ -local attack denoted by $a_{P_l}$ is considered, and crucially it should be noted that the local pair $(A,C_{P_l})$ may not be observable even though the pair $(A,C)$ for the overall system is observable.

Now, the objective of distributed resilient state estimation is as follows.

local identification of unattacked sensors for each local output $y_{P_l}$
state estimation with identified sensors in a distributed manner

Because the system is not observable from each local sensor, a distributed state observer will be introduced.

Under what condition is the problem solvable?

As the notion of redundant observability has been checked to play the key role in the centralized problem, we can make the question: under what condition is the distributed problem solvable? One possible answer is to require $2q$ -redundant observability for each local group, but it seems very restrictive, because the systems is generally not even observable from a local sensor group. Then, what if it requires sensing redundancy only, and does not require full state observability?

With the following definition, we introduce the notion of $2q$ -redundant sensors.

Let us consider the plant with one local group $y_{P_l}$ of $l$ -th measurements. With these local sensors, it may not be observable so the observability matrix with respect to $(A,C_{P_l})$ may not have full column rank, but it is said $2q$ -redundant if this observability rank remains the same even when we remove any $2q$ -rows from the local output matrix. It means that the local group has $2q$ -redundant sensors so it does not lose its observability rank removing any $2q$ -sensors. So, the main point is:

“There is no need of full state observability for the sake of local identification of sensor attack.”

It can be proved that every injection of $q$ -local attacks is locally identifiable if and only if the local pair $(A,C_{P_l})$ is $2q$ -redundant.

Design of distributed resilient state observer

First of all, we design “partial” observer for each single output $y_i \in R,$ $i=1,2,...,p$ . Considering Kalman observable decomposition for each $y_i \in R$ as

we can find the observable $z_i$ subsystem. Then, we can design a Luenberger observer for this observable sub-state, so that the estimate $\hat z_i$ converges to $z_i$ if the output $y_i$ is not attacked. By doing so, we can take the benefit that this yields un-corrupted (partial) estimates as many as the number of unattacked sensors. By doing so, we can preserve many unattacked partial estimates and carry out the identification efficiently.

The following is for an overview of the proposed observer.

We designed partial observers for each output $y_i, i=1,...,p$ where some of them are under attack, but it preserves many unattacked observers and they contain partial estimate $\hat z_i$ for the state $x$ . Next, attack identification is carried out for each local group. For this, the identification algorithm in [1] is applied for each local group. Then, identified partial estimates are fed into the observer network, and through the communication, the full state $x$ is recovered in every sensor node.

The proposed distributed resilient state observer simply takes the form as

where the set $N_i$ is for the neighbors of node $i$ and $\gamma$ is for the coupling gain. The term $\hat x_j^{net}$ is the state information transmitted from node $j$ to its neighbors. The detail for this term can be found in the paper but the main point is, the partial estimate $\hat z_j$ in node $j$ is fed into the observer network only when it is identified.

In the case when the partial estimate $\hat z_j$ is identified as attack free, it is transmitted to its neighbors, otherwise, it is suspected to be attacked and it is excluded from the network.

Putting all together now we get the main result. Our standing assumptions are threefold:

The pair $(A,C)$ for the overall system is observable.
Each local sensor group $y_{P_l}$ has $2q$ -redundant sensors, i.e., the pair $(A,C_{P_l})$ is $2q$ -redundant.
The communication graph is directed and strongly connected. For example, the directed ring network as follows satisfies the condition.

Under these assumptions, the main result states that the full state is recovered by each single node provided that the coupling gain $\gamma$ is sufficiently large, even though some of them are under attack.

Conclusion

For local identification, the conventional $2q$ -redundant observability can be relaxed as the redundant sensors condition, in which the full state observability is not necessary.
A distributed solution to resilient state estimation is presented so it reduces the combinatorial complexity as:

Simulation file

requires MATLAB/Simulink, tested in MATLAB2016b
Download: KimLeeLeeShimSeo
Run “parameter.m”, and then run “simulation.slx”. Simulation result plots are available by running “plot_fig.m”.

Previous work

[1] “Detection of sensor attack and resilient state estimation for uniformly observable nonlinear systems”
Junsoo Kim, Chanhwa Lee, Hyungbo Shim, Yongsoon Eun, and Jin H. Seo
IEEE Transactions on Automatic Control, 2019
http://dx.doi.org/10.1109/TAC.2018.2840819
See also: https://post.cdsl.kr/archives/1474