Distributed Filtering Design with Enhanced Resilience to Coordinated Byzantine Attacks

In recent years, the development of the internet of things (IoT) and machine learning techniques have led to the wide use of cyber-physical systems (CPS) in various infrastructures, such as smart grids, environment monitoring, and signal processing [1, 2, 3, 4]. However, the high reliance of CPS on sensor cooperation makes them vulnerable to various security threats. As a result of malicious attacks, false information spreads throughout the network and threatens the integrity of the entire system [5]. Therefore, the study of security threats in CPS has gained considerable attention from academia and industry in the past few years [6, 7, 8, 9, 10, 11]. In CPSs, distributed filtering and secure estimation are becoming more prevalent due to their resilience to node failures and scalability [12, 13].

Attack strategies influence the performance of CPSs and create complications in developing protection methods against malicious behavior [14, 15]. In CPSs, attacks can be divided into two groups: denial-of-service (DoS) attacks and integrity attacks. DoS attacks occur when the communication links between agents are blocked, and agents cannot exchange information [16]. In contrast, integrity attacks occur when adversaries or malicious agents inject false information into the network [17, 18]. A stealthy attack is also categorized as an integrity attack in which an adversary injects false information into a network without being detected. Various studies have examined the impact of stealthy attacks on state estimation scenarios and investigated situations where adversaries design attacks to degrade the performance of the network [19, 20, 21].

An optimal attack design from an attacker perspective can aid in developing protection methods operating in worst-case scenarios. To this end, [21] designs a false data-injection strategy that maximizes the trace of error covariance in a remote state estimation scenario. An event-based stealthy attack strategy that degrades estimation accuracy is proposed in [22], while [23] develops a stealthy attack strategy and its optimal defense mechanism by exploiting power grid vulnerabilities. Furthermore, [24] proposes a linear stealthy attack strategy and its feasibility constraints. Moreover, [4] proposes an optimal attack strategy and sufficient conditions to limit the resulting estimation error. In [25], authors investigate the impact of reset attacks on cyber-physical systems, while [26] designs a stealthy attack that maximizes the network-wide estimation error by jointly selecting the optimal subset of Byzantine agents and perturbation covariance matrices. In [27], a false data-injection attack on a distributed CPS is proposed that enforces the local state estimates to remain within a pre-specified range.

It is also vital to analyze how countermeasures taken by agents can reduce the impact of the attack. One approach is to detect adversaries and then implement corrective measures [28, 29, 30]. In [31], for example, attack detection is achieved through trusted agents that raise a flag when an adversary is detected. Alternatively, agents can safeguard information and guarantee system performance by running attack-resilient algorithms [32, 33, 34, 31, 35, 36, 37]. In [32, 33], attack-resilient remote state estimators are studied, where the former proposes a stochastic detector with a random threshold to determine whether to fuse the received data, and the latter detects malicious agents using the statistical correlation between trusted agents. Using a probabilistic protector for each sensor, [34] proposes a robust distributed state estimator that decides whether to use data from neighbors based on their innovation signals. Moreover, a Byzantine-resilient distributed state estimation algorithm is proposed in [38] that employs an internal iteration loop within the local aggregation process to compute the trimmed-mean among neighbors.

Providing an extra procedure to protect the system from adversaries [28, 29, 30, 31] can increase the computational load of the agent and make the algorithm undesirable for resource-constrained scenarios. To resolve this issue, works in [35, 39] reduce the weight assigned to measurements whose norm exceeds a certain threshold, limiting the impact of falsified observations, to provide resilience against measurement attacks. Furthermore, the secure state estimation problem in [40] is solved by a local observer that achieves robustness against malicious agents by employing the median of its local estimates. Our primary motivation for conducting this study was to develop an algorithm that provides robustness against malicious adversaries without imposing an extra computation burden on agents.

Even though multi-agent distributed systems are robust to dynamic changes in the network, they are reliant on local interactions that consume power and bandwidth [41]. Partial-sharing-based approaches, originally proposed in [42, 43], reduce local communication overhead by sharing only a fraction of information during each inter-agent interaction. The simplicity of implementation and efficiency of computation make partial-sharing strategies prevalent in distributed processing scenarios [44, 45]. To the best of our knowledge, partial-sharing-based approaches have not been investigated in an adversarial environment. Additionally, the lack of computationally light distributed algorithms that are robust to coordinated attacks inspired us to conduct this research.

This paper proposes a Byzantine-resilient consensus-based distributed filter (BR-CDF) where agents exchange a fraction of their state estimates at each instant. We study the convergence of the BR-CDF and characterize its performance under a coordinated data falsification attack. In addition, we design the optimal attack by solving an optimization problem where Byzantine agents cooperate on designing the covariance of their falsification data or the order of the information fractions they share. The Byzantine agent is a legitimate network agent that shares false information with neighbors to degrade the overall performance of the network. The numerical results validate the theoretical findings and illustrate the robustness of the BR-CDF algorithm.

The remainder of the article is organized as follows. Section II investigates the system model and the attack strategy, while Section III proposes the Byzantine-resilient consensus-based distributed filter. Section IV analyzes the stability and performance of the BR-CDF algorithm and derives its convergence conditions. The performance of the BR-CDF algorithm is investigated under data falsification attacks in Section V, and Section VI develops an optimal coordinated attack strategy. Simulation results are presented in Section VII, and Section VIII concludes the article.

Consider a multi-agent network consisting of $L$ agents attempting to estimate a dynamic system state through their local observations. The network is modeled as an undirected graph $\mathcal{G}(\mathcal{V},\mathcal{E})$, where $\mathcal{V}$ is the set of all agents and pairs in set $\mathcal{E}$ represent communication links between agents. The network adjacency matrix is denoted by $\mathbf{E}$ and $\mathbf{D}$ is a diagonal matrix whose diagonal entries are the degrees of corresponding agents. The neighbor set ${\cal N}_{i}$ contains agents connected to agent $i$ within a single hop, excluding the agent itself.

The state-space model, characterizing the dynamics of the state vector and observation sequences at each agent $i$ and time instant $k$, is given by

where $\mathbf{x}(k)\in\mathbb{R}^{m}$ is the state, $\mathbf{y}_{i}(k)\in\mathbb{R}^{n}$ is the local observation, $\mathbf{A}\in\mathbb{R}^{m\times m}$ is the state matrix, and $\mathbf{H}_{i}\in\mathbb{R}^{n\times m}$ is the observation matrix. The state noise $\mathbf{w}(k)$ and observation noise $\mathbf{v}_{i}(k)$ are mutually independent zero-mean Gaussian processes with covariance matrices $\mathbf{Q}\in\mathbb{R}^{m\times m}$ and $\mathbf{R}_{i}\in\mathbb{R}^{n\times n}$, respectively. Network agents can employ a consensus-based distributed Kalman filter (CDF) to estimate $\mathbf{x}(k)$ in a collaborative manner [46]. Accordingly, the state estimate at agent $i$ is given by

where $\mathbf{C}_{i}\in\mathbb{R}^{m\times m}$ denotes the consensus gain, $\mathbf{K}_{i}(k)\in\mathbb{R}^{m\times n}$ is the Kalman gain, and $\bar{\mathbf{x}}_{j}(k)$ is the received state estimates from neighboring agent $j$.

To analyze the impact of data falsification attacks on network performance, the attack model needs to be specified. For this purpose, we assume a subset of agents to be Byzantines, i.e., ${\cal B}\subseteq\mathcal{V}$, that intend to disrupt the performance of the entire network [17]. Fig. 1 shows the dynamic of the information exchange in a network with Byzantine agents. As seen in Fig. 1, a regular agent shares the actual value of the state estimate $\mathbf{\hat{x}}_{j}(k)$ with its neighbors. In contrast, a Byzantine agent $j\in{\cal B}$ shares a perturbed version of its state estimate with neighbors; in particular, the shared information at each agent $j$ is denoted by

where $\boldsymbol{\delta}_{j}(k)$ denotes the perturbation sequence. To maximize the attack stealthiness, i.e., the ability to evade detection, the perturbation sequence is drawn from a zero-mean Gaussian distribution with covariance $\mathbf{\Sigma}_{j}=\mathbb{E}\{\boldsymbol{\delta}_{j}(k)\boldsymbol{\delta}_{j}^{\text{T}}(k)\}$ [47, 48]. Moreover, to further degrade the network performance, Byzantines can cooperate in designing the attack strategy. The network-wide coordinated attack covariance is denoted by $\boldsymbol{\Sigma}=\mathbb{E}\{\boldsymbol{\delta}(k)\boldsymbol{\delta}^{\text{T}}(k)\}$ where $\boldsymbol{\delta}(k)=[\boldsymbol{\delta}_{1}^{\text{T}}(k),\cdots,\boldsymbol{\delta}_{L}^{\text{T}}(k)]^{\text{T}}$ is the network-wide attack sequence with $\boldsymbol{\delta}_{j}(k)=\mathbf{0}$ if $j\notin\mathcal{B}$.

By applying partial sharing of information to state estimates in (2), we reduce the information flow between agents at a given instant while maintaining the advantages of cooperation [42, 43]. In particular, each agent only shares a fraction of its state estimate with neighbors rather than the entire vector (i.e., $l$ entries of $\mathbf{\hat{x}}_{j}(k)\in\mathbb{R}^{m}$, with $l\leq m$). Although partial-sharing was originally introduced to reduce inter-agent communication overhead, we show that adopting this idea in the current setting improves robustness to Byzantine attacks.

The state estimate entry selection process is performed at each agent $j$ using a selection matrix $\mathbf{S}_{j}(k)$ of size $m\times m$, whose main diagonal contains $l$ ones and $m-l$ zeros. The ones on the main diagonal of $\mathbf{S}_{j}(k)$ specify the entries of the state estimate $\mathbf{\hat{x}}_{j}(k)$ to be shared with neighbors. Selecting $l$ entries from $m$ can either be done stochastically or sequentially, as in [42] and [43]. In this paper, we use uncoordinated partial-sharing, which is a special case of stochastic partial-sharing [42]. In uncoordinated partial-sharing, each agent $j$ is initialized with random selection matrices. The selection matrix at the current time instant, i.e., $\mathbf{S}_{j}(k)$, can be obtained by performing $\tau$ right-circular shift operations on the main diagonal of the selection matrix used in the previous time instant. In other words, if $\mathbf{s}_{j}(k)\in\mathbb{R}^{m}$ contains the main diagonal elements of $\mathbf{S}_{j}(k)$ at the current instant, then $\mathbf{s}_{j}(k)=\text{right-circular shift}\{\mathbf{s}_{j}(k-1),\tau\}$. Then the selection matrix at the current instant can be constructed as $\mathbf{S}_{j}(k)=\textsf{diag}\{\mathbf{s}_{j}(k)\}$. This allows each agent $j$ to share only the initial selection matrix $\mathbf{S}_{j}(k)$ with its neighbors, and maintain a record of the indices of parameters shared without needing any additional mechanisms. As a result, the frequency of each entry of the state estimate being shared is equal to $p_{e}=\frac{l}{m}$.

Due to partial sharing, every agent receives a fraction of the perturbed state estimate vectors from its neighbors, i.e., $\mathbf{S}_{j}(k)\mathbf{\bar{x}}_{j}(k)$. Thus, unlike (3), the received information here must be compensated to fill in the missing elements. At each agent $i$, the missing values from neighbors $(\mathbf{I}-\mathbf{S}_{j}(k))\mathbf{\hat{x}}_{j}(k)$ are replaced by $(\mathbf{I}-\mathbf{S}_{j}(k))\mathbf{\hat{x}}_{i}(k)$. Subsequently, the state update at agent $i$, as in (2), is modified as follows.

At each agent $i$, the Kalman gain is obtained by minimizing the trace of the estimation error covariance $\mathbf{P}_{i}(k)\triangleq\mathbb{E}\{\mathbf{e}_{i}(k)\mathbf{e}^{\text{T}}_{i}(k)\}$ with the estimation error evolving as

where

Accordingly, using (III), we can obtain the evolution of the estimation error covariance at agent $i$ as follows,

where $\boldsymbol{\Sigma}_{sp}=\mathbb{E}\{\boldsymbol{\delta}_{s}(k)\boldsymbol{\delta}_{p}^{\text{T}}(k)\}$ and

Similarly, the cross-terms of the error covariance, i.e., $\mathbf{P}_{ij}(k)\triangleq\mathbb{E}\{\mathbf{e}_{i}(k)\mathbf{e}^{\text{T}}_{j}(k)\}$, evolve as

with

Differentiating the trace of (7) with respect to $\mathbf{K}_{i}(k)$ gives

with $\mathbf{M}_{i}(k)=\mathbf{R}_{i}+\mathbf{H}_{i}\mathbf{P}_{i}(k)\mathbf{H}_{i}^{\text{T}}$.

The distributed Kalman filter based on partial sharing is summarized by (4)–(7). We see that the local covariance update in (7) requires access to cross-term covariance matrices of neighbors, resulting in considerable communication overhead. To reduce the communication overhead, for sufficiently small gain values, i.e., $\mathbf{C}_{i}$, we can ignore the term $\Delta\mathbf{P}_{i}(k)$ in (7) and the last term of $\mathbf{F}_{i}(k)$ in (6) [46], i.e., we have

with $\mathbf{\hat{F}}_{i}(k)=\mathbf{A}-\mathbf{K}_{i}(k)\mathbf{H}_{i}$. Accordingly, the optimal Kalman gain reduces to

With the above approximations, we obtain a distributed consensus-based Kalman filter, albeit suboptimal [46, 49], that only requires local variables in the error covariance update at each agent. It is worth noting that the last term in (8) is only used to characterize the impact of the perturbation covariances, and since the attack is stealthy from the perspective of an agent, it is excluded from the filtering algorithm. As a result, in addition to the initial selection matrix $\mathbf{S}_{j}(0)$, each agent $j$ shares a fraction of the perturbed state estimate, i.e., $\mathbf{S}_{j}(k)\mathbf{\bar{x}}_{j}(k)$, with its neighbors at each instant. The proposed BR-CDF algorithm with reduced communication is summarized in Algorithm 1. We shall see that the BR-CDF in Algorithm 1 performs closely to the solution that shares all necessary variables.

This section provides a detailed stability analysis of the BR-CDF algorithm. For this purpose, we make the following assumption:
Assumption 1: The selection matrix $\mathbf{S}_{i}(k)$ for all $i\in\mathcal{N}$ is independent of any other data, and the selection matrices $\mathbf{S}_{i}(k)$ and $\mathbf{S}_{j}(s)$ for all $i\neq j$ and $k\neq s$ are independent.

This section investigates the robustness of the BR-CDF in Algorithm 1 to data falsification attacks. We assume that Byzantine agents start perturbing the information once the network reaches steady-state, i.e., $k=k_{0}>0$. We further assume that the attack remains stealthy from the perspective of agents; thus, the consensus gain $\mathbf{C}_{i}$ remains fixed for $k~{}\geq~{}k_{0}$.

In steady-state, the error covariance matrix in (8) satisfies

where $\mathbf{P}_{i}=\lim_{k\rightarrow\infty}\mathbf{P}_{i}(k)$. Defining $\mathbf{P}\triangleq\textsf{diag}(\{\mathbf{P}_{i}\}_{i=1}^{L})$, $\mathbf{\hat{F}}\triangleq\textsf{diag}(\{\mathbf{\hat{F}}_{i}\}_{i=1}^{L})$, $\mathbf{K}\triangleq\textsf{diag}(\{\mathbf{K}_{i}\}_{i=1}^{L})$, $\mathbf{C}\triangleq\textsf{diag}(\{\mathbf{C}_{i}\}_{i=1}^{L})$, and $\mathbf{R}\triangleq\textsf{diag}(\{\mathbf{R}_{i}\}_{i=1}^{L})$, the network-wide version of (23) is given by

where $\mathbf{\Sigma}$ is the network-wide coordinated attack covariance. Under Assumption 1, we have

and using the result of (21), we finally have

The last term in (26) describes the impact of the coordinated Byzantine attack on the error covariance matrix that is scaled by $p_{e}$. Thus, defining the steady-state network-wide MSE (NMSE) as

we see that partial sharing, i.e., $p_{e}<1$, results in lower steady-state NMSE compared to the case when the full state is shared, i.e., $p_{e}=1$, which gives enhanced robustness against coordinated Byzantine attacks.

To analyze the worst-case performance of the BR-CDF algorithm, we consider a scenario where Byzantine agents design a coordinated attack to maximize the NMSE. Based on the attack model in Section II and the error covariance of the BR-CDF algorithm in (7), Byzantine agents have the following two levers to design their coordinated attack:

• •

  The design of perturbation covariance matrix $\mathbf{\Sigma}$, modeled as the covariance of zero-mean Gaussian sequences.

• •

  The choice of selection matrices that impacts the sequence of information fractions that Byzantine agents share at the beginning of the attack, i.e., $\mathbf{S}_{i}(k_{0})$ for $i\in\mathcal{B}$.

We ensure that the attack remains stealthy from the perspective of regular agents by setting an upper bound on the energy of the perturbation sequences, i.e., $\text{tr}(\boldsymbol{\Sigma})\leq\eta$. Assuming Byzantines start perturbing information once agents reach steady-state, i.e., $k=k_{0}$, we derive an expression for the NMSE pertaining to the estimator in (4). The network-wide evolution of the estimation error of the BR-CDF algorithm, given in (III), is given by

where $\mathbf{e}(k)\triangleq[\mathbf{e}_{1}^{\text{T}}(k),\cdots,\mathbf{e}_{L}^{\text{T}}(k)]^{\text{T}}$,