Optimal distributed detection in the presence of Byzantines - pdf for free download

Uploaded by:
Swastik Brahma 86191 downloads 86455 Views 246KB Size

Distributed Detection in Tree Networks: Byzantines and Mitigation Techniques - pdf for free download

Swastik Brahma?

Pramod K. Varshney?

Yunghsiang S. Han†

?

†

Department of EECS, Syracuse University Department of EE, National Taiwan University of Science & Technology ABSTRACT

This paper considers the problem of optimal distributed detection with independent identical sensors in the presence of Byzantine attacks. By considering the attacker to be strategic in nature, we address the issue of designing the optimal fusion rule and the local sensor thresholds that minimize the probability of error at the fusion center (FC). We first consider the problem of finding the optimal fusion rule under the constraint of fixed local sensor thresholds and fixed Byzantine strategy. Next, we consider the problem of joint optimization of the fusion rule and local sensor thresholds for a fixed Byzantine strategy. Then we extend these results to the scenario where both the FC and the Byzantine attacker act in a strategic manner to optimize their own utilities. We model the strategic behavior of the FC and the attacker using game theory and show the existence of Nash Equilibrium. We also provide numerical results to gain insights into the solution. Index Terms— Distributed detection, Wireless sensor networks, Byzantines, Game theory 1. INTRODUCTION

1. We consider the problem of joint optimization of the fusion rule and local sensor threshold for a fixed Byzantine strategy. 2. Then we extend these results to the scenario where both the FC and the Byzantine attacker act in a strategic manner to optimize their own utilities and model it using Game Theory. 3. We provide numerical results to gain insights into the solution. 2. SYSTEM MODEL AND PROBLEM FORMULATION In this section, we present the system model used in this paper. We consider a parallel network with N sensor nodes and a fusion center (FC) trying to detect a phenomenon. 2.1. Distributed detection in sensor networks Consider a binary hypothesis testing problem with the two hypotheses H0 (signal is absent) and H1 (signal is present). Prior probabilities of the two hypotheses H0 and H1 are denoted by π0 and π1 , respectively. Each node i makes a one-bit local decision vi ∈ {0, 1} using the likelihood ratio test (1)

Distributed detection with multiple sensors is a well studied topic in detection theory [1]. The design of sensor networks for different applications has been extensively studied in the past decade. Different sensor network topologies have been considered [2] , but in this paper we focus on parallel topology. In [3], [4], the authors considered the design of the optimal fusion rule and local sensor thresholds by minimizing the probability of error at the fusion center (FC) for the parallel topology. Recently, the problem of distributed detection in the presence of Byzantine attacks has attracted attention [5, 6, 7, 8, 9]. Schemes for Byzantine node identification have been proposed in [5, 9]. Analysis of optimal Byzantine attacks is presented in [6, 9, 10]. In [7] and [8], the authors considered the problem of optimization of the fusion rule for a fixed sensor threshold. However, the problem of designing optimal detection parameters in a holistic manner by considering strategic behavior of the FC and the Byzantine is still an area of open research. In contrast to previous works, in this paper, we consider the problem of designing optimal distributed detection parameters in a holistic manner in the presence of Byzantines and also model the strategic behavior of the FC and the Byzantines using game theory. We analyze the problem under different attacking scenarios and give insights into the practical scenarios where the proposed schemes are useful. The main contributions of this paper are as follows. This work was supported in part by ARO under Grant W911NF-091-0244, AFOSR under Grants FA9550-10-1-0458, FA9550-10-1-0263 and National Science Council of Taiwan, under grants NSC 99-2221-E-011-158 -MY3, NSC 101-2221-E-011-069 -MY3.

pY i (yi )

vi =1

(0) pY i (yi )

vi =0

≷

λ

(1)

where λ is the identical threshold1 used at all the sensors and (k) pY i (yi ) is the conditional probability density function (PDF) of observation Y i under the hypothesis Hk . After making its one-bit local decision vi , node i sends ui (which may not be the same as vi ) to the FC. We assume error-free communication channels in this paper. We denote the probabilities of detection and false alarm of node i by Pd = P (vi = 1|H1 ) and Pf a = P (vi = 1|H0 ), respectively, which are assumed to be the same for every node irrespective of whether they are honest or Byzantine nodes. If a node is honest, then it forwards its own decision correctly. However, a Byzantine node, in order to undermine the network performance, may alter these decisions. 2.2. Byzantine attack model A Byzantine node, in order to undermine the network performance, may alter its decision prior to transmission. Each Byzantine decides to attack independently relying on its own observation and decision regarding the presence of the phenomenon. We define the following H H B B strategies Pj,1 , Pj,0 and Pj,1 , Pj,0 (j ∈ {0, 1}) for the honest and Byzantine nodes, respectively: Honest nodes: 1 It has been shown that the use of identical thresholds is asymptotically optimal [11].

H H P1,1 = 1 − P0,1 = P H (x = 1|y = 1) = 1

(2)

H P1,0

= P (x = 1|y = 0) = 0

(3)

B B P1,1 = 1 − P0,1 = P B (x = 1|y = 1) = 0

(4)

B P1,0

(5)

=1−

H P0,0

H

Byzantine nodes:

=1−

B P0,0

B

= P (x = 1|y = 0) = 1

where P (x = a|y = b) is the probability that a node sends a to the FC when its actual decision is b. We assume that the FC is not aware of the exact set of Byzantine nodes and considers each node i to be Byzantine with a certain probability x. 2.3. Binary Hypothesis Testing at the Fusion Center We consider a Bayesian detection problem where the performance criterion at the fusion center is the probability of error. We also assume that the FC employs a K-out-of-N fusion rule. Global false alarm and detection probabilities are denoted by QF and QD , respectively, as N X N (π10 )i (1 − π10 )N−i (6) QF = i i=K N X N (π11 )i (1 − π11 )N−i (7) QD = i i=K

where πj0 and πj1 denote the conditional probabilities of ui = j given H0 and H1 , respectively. We can represent π10 and π11 as π10 = x(1 − Pf a ) + (1 − x)Pf a

(8)

π11 = x(1 − Pd ) + (1 − x)Pd

(9)

where x denotes the probability that bit ui received at the FC has been flipped, i = 1, · · · , N . In this paper, we assume that the network is moderately affected by Byzantines and x ≤ 0.5. The probability of error at the FC is given by PE = π0 QF + π1 (1 − QD )

(10)

The probability of error PE is a function of parameters (K, λ), which are under the control of the FC and the parameter (x) which is under the control of the attacker. This motivates us to design parameters K and λ given x such that PE is minimized. 2.4. Problem Formulation In this subsection, we formulate the Bayesian detection problem and consider the minimization of the probability of error under three different scenarios. First, we consider the problem P 1 finding the optimal fusion rule (K ∗ ) for a fixed local sensor threshold (λ) and a fixed Byzantine strategy (x). Next, we consider the problem P 2 of joint optimization of the fusion rule and the local sensor threshold (K, λ) for a fixed Byzantine strategy. Then we extend this result to the problem P 3 where both the FC and the Byzantine attacker act in a strategic manner to optimize their own utilities and model it as a minimax game. The solution to this minimax game between the FC and the Byzantines is the Nash equilibrium (NE), which is a saddle point in the design metric, PE . The problems discussed above are formally stated as follows. Problem P1: minimize PE (K, λ, x) (11) K Problem P2:

minimize K,λ

PE (K, λ, x)

(12)

Problem P3:

min max K,λ

x

PE (K, λ, x)

(13)

In the next section, we present analytical results that allow us to find the optimal design parameters for the above mentioned formulations. 3. SYSTEM DESIGN IN THE PRESENCE OF BYZANTINES In this section, we investigate the properties of the probability of error PE with respect to K, λ and x and use it to solve the optimization problems (P 1), (P 2) and (P 3). 3.1. Optimal Fusion Rule Design First, we design the optimal fusion rule assuming that the local sensor threshold λ and the Byzantine strategy (x) are fixed and known to FC. 2 Notice that the resulting optimal fusion rule and fixed local sensor threshold pair (K ∗ , λ) may not be the global minimizer of the probability of error over all possible (K, λ) pairs since λ is assumed fixed during the optimization process. However, this scheme is particularly important in the scenario where the FC wants to avoid the overhead caused by the diffusion of the new local sensor threshold messages to all nodes in the network. We present the solution of Problem P 1 in the following theorem based on [1]. Theorem 1 The optimal fusion rule K ∗ for fixed local sensor threshold λ and Byzantine strategy x is given by h i ln (π0 /π1 ) {(1 − π10 )/(1 − π11 )}N K∗ = (14) ln [{π11 (1 − π10 )}/{π10 (1 − π11 )}] where x < 0.5. When x = 0.5, FC makes the final decision based on the prior probabilities. As aforementioned, this optimal fusion rule and fixed local sensor threshold pair (K ∗ , λ) may not be the global minimizer of the probability of error over all (K, λ) pairs. Thus, we next consider the joint optimization of the fusion rule and the local sensor threshold. 3.2. Joint Optimization of Fusion Rule and Sensor Threshold In this section, we present a procedure to find the optimal fusion rule and local sensor threshold pair (K ∗ , λ∗ ) that minimizes the probability of error PE given a fixed Byzantine strategy x. This scheme is particularly important in the scenario where Byzantine attackers are performing a man-in-the-middle attack and do not have access to the local se...