A Message Passing Approach for Decision
Fusion in Adversarial Multi-Sensor Networks
Andrea Abrardo, Mauro Barni, Kassem Kallas and Benedetta Tondia

arXiv:1702.08357v1 [] 27 Feb 2017

a Department

of Information Engineering and Mathematics, Via Roma 56, Siena, Italy

Abstract
We consider a simple, yet widely studied, set-up in which a Fusion Center
(FC) is asked to make a binary decision about a sequence of system states by
relying on the possibly corrupted decisions provided by byzantine nodes, i.e.
nodes which deliberately alter the result of the local decision to induce an error
at the fusion center. When independent states are considered, the optimum
fusion rule over a batch of observations has already been derived, however its
complexity prevents its use in conjunction with large observation windows.
In this paper, we propose a near-optimal algorithm based on message passing that greatly reduces the computational burden of the optimum fusion rule.
In addition, the proposed algorithm retains very good performance also in the
case of dependent system states. By first focusing on the case of small observation windows, we use numerical simulations to show that the proposed scheme
introduces a negligible increase of the decision error probability compared to
the optimum fusion rule. We then analyse the performance of the new scheme
when the FC make its decision by relying on long observation windows. We do
so by considering both the case of independent and Markovian system states and
show that the obtained performance are superior to those obtained with prior
suboptimal schemes. As an additional result, we confirm the previous finding
that, in some cases, it is preferable for the byzantine nodes to minimise the mutual information between the sequence system states and the reports submitted
to the FC, rather than always flipping the local decision.
Keywords: Adversarial signal processing, Decision fusion in adversarial

Preprint submitted to Journal of Information Fusion

February 28, 2017

setting, Decision fusion in the presence of Byzantines, Message passing
algorithm, Factor graph.

1. Introduction
Decision fusion for distributed detection has received an increasing attention
for its importance in several applications, including wireless networks, cognitive
radio, multimedia forensics and many others. One of the most common scenarios
is the parallel distributed fusion model. According to this model, the n nodes
of a multi-sensor network gather information about a system and make a local
decision about the system status. Then the nodes send the local decisions to
a Fusion Center (FC), which is in charge of making a final decision about the
state of the system. [1]
In this paper, we focus on an adversarial version of the above problem, in
which a number of malicious nodes, often referred to as Byzantines [1], aims at
inducing a decision error at the FC [2]. This is a recurrent problem in many
situations wherein the nodes may make a profit from a decision error. As an
example, consider a cognitive radio system [3, 4, 5, 6] in which secondary users
cooperate in sensing the frequency spectrum to decide about its occupancy
and the possibility to use the available spectrum to transmit their own data.
While cooperation among secondary users allows to make a better decision, it
is possible that one or more users deliberately alter their measurements to let
the system think that the spectrum is busy, when in fact it is not, in order to
gain an exclusive opportunity to use the spectrum. Online reputation systems
offer another example [7]. Here a fusion center must make a final decision about
the reputation of an item like a good or a service by relying on user’s feedback.
Even in this case, it is possible that malevolent users provide a fake feedback to
alter the reputation of the item under inspection. Similar examples are found in
many other applications, including wireless sensor networks [2], [3], distributed
detection [8], [9], multimedia forensics [10] and adversarial signal processing [11].
In this paper we focus on a binary version of the fusion problem, wherein

2

the system can assume only two states. Specifically, the nodes observe the
system over m time instants and make a local decision about the sequence of
system states. Local decisions are not error-free and hence they may be wrong
with a certain error probability. Honest nodes send their decision to the fusion
center, while byzantine nodes try to induce a decision error and hence flip the
local decision with probability Pmal before sending it to the FC. The fusion
center knows that some of the nodes are Byzantines with a certain probability
distribution, but it does not know their position.
1.1. Prior Work
In a simplified version of the problem, the FC makes its decision on the
status of the system at instant j by relying only on the corresponding reports,
and ignoring the node reports relative to different instants. In this case, and in
the absence of Byzantines, the Bayesian optimal fusion rule has been derived
in [12],[13] and it is known as Chair-Varshney rule. If local error probabilities
are symmetric and equal across the network, Chair-Varshney rule boils down to
simple majority-based decision. In the presence of Byzantines, Chair-Varshney
rule requires the knowledge of Byzantines’ positions along with the flipping
probability Pmal . Since this information is rarely available, the FC may resort
to a suboptimal fusion strategy.
In [8], by adopting a Neyman-Pearson setup and assuming that the byzantine
nodes know the true state of the system, the asymptotic performance obtainable by the FC are analysed as a function of the percentage of Byzantines in
the network. By formalising the attack problem as the minimisation of the
Kullback-Leibler distance between the reports received by the FC under the
two hypotheses, the blinding percentage, that is, the percentage of Byzantines
irremediably compromising the possibility of making a correct decision, is determined.
In order to improve the estimation of the sequence of system states, the
FC can gather a number of reports provided by the nodes before making a
global decision (multiple observation fusion). In cooperative spectrum sensing,
3

for instance, this corresponds to collectively decide about the white holes over a
time window, or, more realistically, at different frequency slots. The advantage
of deciding over a sequence of states rather than on each single state separately,
is that in such a way it is possible for the FC to understand which are the
byzantine nodes and discard the corresponding observations (such an operation
is usually referred to as Byzantine isolation). Such a scenario has also been
studied in [8], showing that - at least asymptotically - the blinding percentage
is always equal to 50%. In [14], the analysis of [8] is extended to a situation
in which the Byzantines do not know the true state of the system. Byzantine
isolation is achieved by counting the mismatches between the reports received
from each node and the global decision made by the FC. The performance of the
proposed scheme are evaluated in a cognitive-radio scenario for finite values of n.
In order to cope with the lack of knowledge about the strategy adopted by the
attacker, the decision fusion problem is casted into a game-theoretic formulation,
where each party makes the best choice without knowing the strategy adopted
by the other party.
A slightly different approach is adopted in [15]. By assuming that the FC is
able to derive the statistics of the reports submitted by honest nodes, Byzantine
isolation is carried out whenever the reports received from a node deviate from
the expected statistics. In this way, a correct decision can be made also when
the percentage of Byzantines exceeds 50%. The limit of the approach proposed
in [15], is that it does not work when the reports sent by the Byzantines have
the same statistics of those transmitted by the honest nodes. This is the case,
for instance, in a perfectly symmetric setup with equiprobable system states,
symmetric local error probabilities, and an attack strategy consisting of simple
decision flipping.
A soft isolation scheme is proposed in [16], where the reports from suspect byzantine nodes are given a lower importance rather being immediately
discarded. Even in [16], the lack of knowledge at the FC about the strategy
adopted by the attacker (and viceversa) is coped with by adopting a gametheoretic formulation. A rather different approach is adopted in [17], where a
4

tolerant scheme that mitigates the impact of Byzantines on the global decision
is used rather that removing the reports submitted by suspect nodes from the
fusion procedure.
When the value of Pmal and the probability that a node is Byzantine are
known, the optimum fusion rule under multiple observation can be derived [18].
Since Pmal is usually not known to the FC, in [18] the value of Pmal used to
define the optimum fusion rule and the value actually used by the Byzantines
are strategically chosen in a game-theoretic context. Different priors about
the distribution of Byzantines in the network are considered ranging from an
extreme case in which the exact number of Byzantines in the network is known
to a maximum entropy case. One of the main results in [18] is that the best
option for the Byzantines is not to always flip the local decision (corresponding
to Pmal = 1), since this would ease the isolation of malicious nodes. In fact,
for certain combinations of the distribution of Byzantines within the network
and the length of the observation window, it is better for the Byzantines to
minimise the mutual information between the reports submitted to the FC and
the system states.
1.2. Contribution
The main problem of the optimum decision fusion scheme proposed in [18] is
its computational complexity, which grows exponentially with the length of the
observation window. Such a complexity prevents the adoption of the optimum
decision fusion rule in many practical situations. Also the results regarding the
optimum strategies of the Byzantines and the FC derived in [18] refer only to
the case of small observation windows.
In the attempt to diminish the computational complexity while minimising
the loss of performance with respect to the optimum fusion rule, we propose
a new, nearly-optimum, fusion scheme based on message passing and factor
graphs. Message passing algorithms, based on the so called Generalised Distributive Law (GLD, [19],[20]), have been widely applied to solve a large range of
optimisation problems, including decoding of Low Density Parity Check (LDPC)
5

codes [21] and BCJR codes [19], dynamic programming [22], solution of probabilistic inference problems on Bayesian networks [23] (in this case message
passing algorithms are known as belief propagation). Here we use message passing to introduce a near-optimal solution of the decision fusion problem with
multiple observation whose complexity grows only linearly with the size of the
observation window, thus marking a dramatic improvement with respect to the
exponential complexity of the optimal scheme proposed in [18].
Using numerical simulations and by first focusing on the case of small observation windows, for which the optimum solution can still be applied, we prove
that the new scheme gives near-optimal performance at a much lower complexity than the optimum scheme. We then use numerical simulations to evaluate
the performance of the proposed method for long observation windows. As a
result, we show that, even in this case, the proposed solution maintains the performance improvement over the simple majority rule, the hard isolation scheme
in [14] and the soft isolation scheme in [16].
As opposed to previous works, we do not limit our analysis to the case of
independent system states, but we extend it to a more realistic scenario where
the sequence of states obey a Markovian distribution [24] as depicted in Figure 2.
The Markovian model is rather common in the case of cognitive radio networks
[25, 26, 27] where the primary user occupancy of the spectrum is often modelled
as a Hidden Markov Model (HMM). The Markovian case is found to be more
favourable for the FC with respect to the case of independent states, due the
additional a-priori information available to the FC in this case.
Last but not the least, we confirm that the dual optimum behaviour of
the Byzantines observed in [18] is also present in the case of large observation
windows, even if in the Markovian case, the Byzantines may continue using the
maximum attack power (Pmal = 1) for larger observation windows.
The rest of this paper is organised as follows. In Section 2, we introduce
the notation used in the paper and give a precise formulation of the addressed
problem. In Section 3, we describe the new message passing decision rule based
on factor graph. In Section 4, we first discuss the complexity of the proposed
6

Byzantine Node

Byzantine Node

Honest Node

Local Decision

Local Decision

Local Decision

Attack

Attack

Fusion Center
Figure 1: Sketch of the adversarial decision fusion scheme.

solution compared to the optimal solution. Then, by considering both independent and Markovian system states, we compare the performance of the message
passing algorithm to the majority rule, the hard isolation scheme [14], the soft
isolation scheme described in [16] and the optimal fusion rule. In addition, we
discuss the impact that the length of the observation window has on the optimal behaviour of the Byzantines. We conclude the paper in Section 5 with
some final remarks.

2. Notation and Problem Formulation
The problem faced with in this paper, is depicted in Figure 1. We let s =
{s1 , s2 , . . . , sm } with si ∈ {0, 1} indicate the sequence of system states over
an observation window of length m. The nodes collect information about the
system through the vectors x1 , x2 . . . xn , with xj indicating the observations
available at node j. Based on such observations, a node j makes a local decision
ui,j about system state si . We assume that the local error probability, hereafter
indicated as ε, does not depend on either i or j. The state of the nodes in the
network is given by the vector h = {h1 , h2 , . . . , hn } with hj = 1/0 indicating
that node j is honest or Byzantine, respectively. Finally, the matrix R =
7

Figure 2: Markovian model for system states. When ρ = 0.5 subsequent states are independent.

{ri,j }, i = 1, . . . , m, j = 1, . . . , n contains all the reports received by the FC.
Specifically, ri,j is the report sent by node j relative to si . As stated before, for
honest nodes we have ui,j = ri,j while, for Byzantines we have p(ui,j 6= ri,j ) =
Pmal . The Byzantines corrupt the local decisions independently of each other.
By assuming that the transmission between nodes and fusion center takes
place over error-free channels, the report is equal to the local decision with probability 1 for honest nodes and with probability 1 − Pmal for Byzantines. Hence,
according to the local decision error model, we can derive the probabilities of
the reports for honest nodes:

p (ri,j |si , hj = 1) = (1 − ε)δ(ri,j − si ) + ε(1 − δ(ri,j − si )),

(1)

where δ(a) is defined as:

δ(a) =



1, if a = 0

(2)


0, otherwise.
On the other hand, by introducing η = ε(1 − Pmal ) + (1 − ε)Pmal , i.e., the
probability that the fusion center receives a wrong report from a byzantine node,
we have:

p (ri,j |si , hj = 0) = (1 − η)δ(ri,j − si ) + η(1 − δ(ri,j − si ))

8

(3)

As for the number of Byzantines, we consider a situation in which the states
of the nodes are independent of each other and the state of each node is described
by a Bernoulli random variable with parameter α, that is p(hj = 0) = α, ∀j. In
this way, the number of byzantine nodes in the network is a random variable
following a binomial distribution, corresponding to the maximum entropy case
Q
[18] with p (h) = p(hj ), where p(hj ) = α(1 − hj ) + (1 − α)hj .
j

Regarding the sequence of states s, we assume a Markov model as shown in
Q
Figure 2 , i.e., p (s) =
p(si |si−1 ). The transition probabilities are given by
i

p(si |si−1 ) = 1 − ρ if si = si−1 and p(si |si−1 ) = ρ when si 6= si−1 , whereas for
i = 1 we have p(s1 |s0 ) = p(s1 ) = 0.5.
In this paper we look for the the bitwise Maximum A Posteriori Probability
(MAP) estimation of the system states {si } which reads as follows:

ŝi

arg max p (si |R)
si ∈{0,1}
P
arg max
p (s, h|R)

=
=

(law of total probability)

si ∈{0,1} {s,h}\si

=

P

arg max

p (R|s, h) p(s)p(h)

(Bayes)

si ∈{0,1} {s,h}\si

=

arg max

P

Q

p (ri,j |si , hj )

si ∈{0,1} {s,h}\si i,j

Q
i

p(si |si−1 )

Q

p(hj )

j

(4)
where the notation

P

denotes a summation over all the possible combina-

\

tions of values that the variables contained in the expression within the summation may assume by keeping the parameter listed after the operator \ fixed. For
a given h, the matrix of the observations R at the FC follows a HMM [28]. The
optimisation problem in (4) has been solved in [18] for the case of independent
system states. Even in such a simple case, however, the complexity of the optimum decision rule is exceedingly large, thus limiting the use of the optimum
decision only in the case of small observation windows (typically m not larger
than 10). In the next section we introduce a sub-optimum solution of (4) based
on message passing, which greatly reduces the computational complexity at the
price of a negligible loss of accuracy.

9

3. A Decision Fusion Algorithm Based on Message Passing
3.1. Introduction to Sum-product message passing
In this section we provide a brief introduction to the message passing (MP)
algorithm for marginalization of sum-product problems. Let us start by considering N binary variables z = {z1 , z2 , . . . , zN }, zi ∈ {0, 1}. Then, consider the
function f (z) with factorization:
f (z) =

Y

fk (Zk )

(5)

k

where fk , k = 1, . . . , M are functions of a subset Zk of the whole set of variables.
We are interested in computing the marginal of f with respect to a general
variable zi , defined as the sum of f over all possible values of z, i.e.:
µ(zi ) =

XY
z\zi

where notation

P

fk (Zk )

(6)

k

denotes a sum over all possible combinations of values of

z\zi

the variables in z by keeping zi fixed. Note that marginalization problem occurs
when we want to compute any arbitrary probability from joint probabilities by
summing out variables that we are not interested in. In this general setting, determining the marginals by exhaustive search requires 2N operations. However,
in many situations it is possible to exploit the distributive law of multiplication
to get a substantial reduction in complexity.
To elaborate, let associate with problem (6) a bipartite factor graph, in which
for each variable we draw a variable node (circle) and for each function we draw
a factor node (square). A variable node is connected to a factor node k by an
edge if and only if the corresponding variable belongs to Zk . This means that
the set of vertices is partitioned into two groups (the set of nodes corresponding
to variables and the set of nodes corresponding to factors) and that an edge
always connects a variable node to a factor node.
Let now assume that the factor graph is a single tree, i.e., a connected graph
where there is an unique path to connect two nodes. In this case, it is straightforward to derive an algorithm which allows to solve the marginalization problem
10

Figure 3: Node-to-factor message passing.

with reduced complexity. The algorithm is the MP algorithm, which has been
broadly used in the last years in channel coding applications [29], [30].
To describe how the MP algorithm works, let us first define messages as
2-dimensional vectors, denoted by m = {m(0), m(1)}. Such messages are exchanged between variable nodes and function nodes and viceversa, according to
the following rules. Let us first consider variable-to-function messages (mvf ),
and take the portion of factor graph depicted in Fig. 3 as an illustrative example. In this graph, the variable node zi is connected to L factor nodes, namely
f1 , f2 , . . . , fL . For the MP algorithm to work properly, node zi must deliver the
(l)

messages mvf , l = 1, . . . , L to all its adjacent nodes. Without loss of generality,
(1)

let us focus on message mvf . Such a message can be evaluated and delivered
(l)

upon receiving messages mf v , l = 2, . . . , L, i.e., upon receiving messages from
(1)

all function nodes except f1 . In particular, mvf may be straightforwardly evaluated by calculating the element-wise product of the incoming messages, i.e.:
(1)

mvf (q) =

L
Y

(j)

mf v (q)

(7)

j=2

for q = 0, 1. Let us now consider factor-to-variable messages, and refer to the
factor graph of Fig. 4 where P variable nodes are connected to the factor node
11

Figure 4: Factor-to-node message passing.

fk , i.e., according to the previous notation, Zk = {z1 , . . . , zP }. In this case, the
(l)

node fk must deliver the messages mf v , l = 1, . . . , P to all its adjacent nodes.
(1)

(l)

Let us consider again mf v : upon receiving the messages mvf , l = 2, . . . , P , fk
(1)

may evaluate the message mf v as:
"
(1)
mf v (q)

=

X

fk (q, z2 , . . . , zP )

z2 ,...,zP

P
Y

#
(p)
mvf (zp )

(8)

p=2

for q = 0, 1.
Given the message passing rules at each node, it is now possible to derive
the MP algorithm which allows to compute the marginals in (6). The process
starts at the leaf nodes, i.e., those nodes which have only one connecting edge.
In particular, each variable leaf node passes an all-ones message to its adjacent
(k)

factor node, whilst each factor leaf node, say fk (zi ) passes the message mf v (q) =
fk (zi = q) to its adjacent node zi . After initialization at leaf nodes, for every
edge we can compute the outgoing message as soon as all incoming messages
from all other edges connected to the same node are received (according to the
message passing rules (7) and (8)). When a message has been sent in both
directions along every edge the algorithm stops. This situation is depicted in
Fig. 5: upon receiving messages from all its adjacent factor nodes, node zi can
evaluate the exact marginal as:

12

Figure 5: End of message passing for node zi .

µ(zi ) =

Y

(k)

mf v (zi ).

(9)

k=1,...,L

With regard to complexity, factors to variables message passing can be accomplished with 2P operations, P being the number of variables in fk . On the
other hand, variables to nodes message passing’s complexity can be neglected,
and, hence, the MP algorithm allows to noticeably reduce the complexity of
the problem provided that the numerosity of Zk is much lower than N . With
regard to the optimization, Equation (9) evaluates the marginal for both zi = 0
and zi = 1, which represent the approximated computation of the sum-product
for both hypotheses. Hence, the optimization is obtained by choosing the value
of zi which maximizes it.
3.2. Nearly-optimal data fusion by means of message passing
The objective function of the optimal fusion rule expressed in (4) can be seen
as a marginalization of a sum product of functions of binary variables, and, as
such, it falls within the MP framework described in the previous Section. More
specifically, in our problem, the variables are the system states si and the status
of the nodes hj , while the functions are the probabilities of the reports shown in
13

Figure 6: Factor graph for the problem at hand.

equations (1) and (3), the conditional probabilities p(si |si−1 ), and the a-priori
probabilities p(hj ). The resulting bipartite graph is shown in Figure 6.
It is worth noting that the graph is a loopy graph, i.e., it contains cycles,
and as such it is not a tree. However, although it was originally designed for
acyclic graphical models, it was found that the MP algorithm can be used for
general graphs, e.g., in channel decoding problems [31]. In general, when the
marginalization problem is associated to a loopy graph, the implementation of
MP requires to establish a scheduling policy to initiate the procedure, so that
variable nodes may receive messages from all the connected factors, thus evaluating the marginals. In this case, a single run of the MP algorithm may not
be sufficient to achieve a good approximation of the exact marginals, and progressive refinements must be obtained through successive iterations. However,
in the presence of loopy graphs, there is no guarantee of either convergence or
optimality of the final solution. In many cases, the performance of the messagepassing algorithms is closely related to the structure of the graph, in general,
and its cycles, in particular. Many previous works in the field of channel cod-

14

ing, e.g., see [32], reached the conclusion that, for good performance, the factor
graph should not contain short cycles. In our case, it is possible to see from
Figure 6 that the shortest cycles have order 6, i.e., a message before returning
to the sender must cross at least six different nodes. We speculate that such a
minimum cycles length is sufficient to provide good performance for the problem
at hand. We will prove through simulations that such a conjecture is true.
To elaborate further, based on the graph of Figure 6 and on the general
MP rules reported in the previous Section, we are now capable of deriving the
messages for the scenario at hand. In Figure 7, we display all the exchanged
messages for the graph in Figure 6 that are exchanged to estimate in parallel
each of the states si , i ∈ {0, 1} in the vector s = {s1 , s2 , . . . , sm }. Specifically,
we have:
(l)

τi (si )
(r)

τi (si )
(l)

ϕi (si )
(r)

ϕi (si )
(r)

ϕ1 (s1 )
(u)

νi,j (si )

=
=
=

(l)

n
Q

(r)

j=1
n
Q

ϕi (si )
ϕi (si )
P
si+1 =0,1

=

P
si−1 =0,1

i = 1, . . . , m

(u)

i = 1, . . . , m

νi,j (si )
(l)

i = 1, . . . , m − 1

(r)

i = 2, . . . , m

p (si+1 |si ) τi+1 (si+1 )
p (si |si−1 ) τi−1 (si−1 )

=
=

j=1

(u)

νi,j (si )

p(s1 )
P

(u)

i = 1, . . . , m, j = 1, . . . , n

(u)

i = 1, . . . , m − 1, j = 1, . . . , n

p (ri,j |si , hj ) λj,i (hj )

hj =0,1
(d)

νi,j (si )

=

(r)

(l)

ϕi (si )ϕi (si )

n
Q
k=1
k6=j

(d)

νm,j (sm )

=

n
Q

(r)

ϕi (sm )

k=1
k6=j

(d)

λj,i (hj )
(u)

λj,i (hj )
(d)

ωj (hj )
(u)

ωj (hj )

=

(u)

νm,k (sm )
(d)

P
si =0,1

=

νi,k (si )

p (ri,j |si , hj ) νi,j (si )

(u)

ωj (hj )
m
Q

=

i=1

=

m
Q
q=1
q6=i

(d)

λj,q (hj )

j = 1, . . . , n
i = 1, . . . , m, j = 1, . . . , n
i = 1, . . . , m, j = 1, . . . , n

λj,i (hj )

(d)

j = 1, . . . , n

p(hj )

j = 1, . . . , n
(10)

As for the scheduling policy, we initiate the MP procedure by sending the
(u)

(u)

messages λj,i (hj ) = ωj (hj ) to all p (ri,j |si , hj ) factor nodes, and by sending
15

16
Figure 7: Factor graph for the problem at hand with the illustration of all the exchanged messages.

the message p(s1 ) to the variable node s1 . Hence, the MP proceeds according to the general message passing rules, until all variable nodes are able to
compute the respective marginals. When this happens, the first iteration is
concluded. Then, successive iterations are carried out by starting from leaf
nodes and by taking into account the messages received at the previous iteration for the evaluation of new messages. Hence, the algorithm is stopped upon
achieving convergence of messages, or after a maximum number of iterations.
The MP scheme described above can be simplified by observing that messages can be normalized without affecting the normalized marginals. Henceforward, let us consider as normalization factors the sum of the elements of the
(l)

messages, i.e., if we consider for example τi (si ), the normalization factor is
(l)

(l)

(l)

τi (0) + τi (1). In this case, the normalized messages, say τ̄i (si ) can be conveniently represented as scalar terms in the interval (0, 1), e.g., we can consider
(l)

(l)

(l)

τ̄i (0) only since τ̄i (1) = 1 − τ̄i (0). Accordingly, the normalized messages

17

can be evaluated as:
n
Q

(l)

(l)
τ̄i

ϕ̄i

=

n
Q

(l)

ϕ̄i

n
Q

(l)

(u)

j=1

(u)

ν̄i,j

j=1

ν̄i,j +(1−ϕ̄i )
n
Q

(r)

ϕ̄i

(u)

ν̄i,j

(r)
τ̄i

=

(l)

=

ρτ̄i+1 + (1 − ρ)(1 − τ̄i+1 )

ϕ̄i

(r)

=

ρτ̄i−1 + (1 − ρ)(1 − τ̄i−1 )

(r)
ϕ̄1

=

ϕ̄i

(u)

ν̄i,j

(d)

ν̄i,j

n
Q

(r)

ϕ̄i

j=1

j=1

ν̄i,j +(1−ϕ̄i )

(l)

i = 1, . . . , m − 1

(r)

(r)

i = 2, . . . , m

p(s1 = 0)

=

(u)

(u)

=

(u)

=

(d)

=

(u)

=

λ̄j,i

ω̄j
ω̄j

(u)

k=1
k6=j

(r)

n
Q

(l)

k=1
k6=j

(r)

ϕ̄m

(d)

(u)

p(ri,j |0,0 )λ̄j,i +p(ri,j |0,1 )(1−λ̄j,i )+p(ri,j |1,0 )λ̄j,i +p(ri,j |1,1 )(1−λ̄j,i )
n
(r) (l) Q
(u)
ϕ̄i ϕ̄i
ν̄i,k
ϕ̄i ϕ̄i

=

(u)

p(ri,j |0,0 )λ̄j,i +p(ri,j |0,1 )(1−λ̄j,i )

(u)

(r)

(l)

ν̄i,k +(1−ϕ̄i )(1−ϕ̄i )

n
Q
k=1
k6=j

λ̄j,i

j=1

(u)

=

i = 1, . . . , m

(u)

(1−ν̄i,j )

(l)

ϕ̄(r)
m
(d)
ν̄m,j

n
Q

(r)

(u)

i = 1, . . . , m

(u)

(1−ν̄i,j )

j=1

n
Q
k=1
k6=j

(u)

n
Q
k=1
k6=j

(u)

i = 1, . . . , m, j = 1, . . . , n

i = 1, . . . , m − 1, j = 1, . . . , n

(1−ν̄i,k )

(u)

ν̄m,k
(r)

ν̄m,k +(1−ϕ̄m )

n
Q
k=1
k6=j

j = 1, . . . , n

(u)

(1−ν̄m,k )

(d)
(d)
p(ri,j |0,0 )ν̄i,j +p(ri,j |1,0 )(1−ν̄i,j )
(d)
(d)
(d)
(d)
p(ri,j |0,0 )ν̄i,j +p(ri,j |1,0 )(1−ν̄i,j )+p(ri,j |0,1 )ν̄i,j +p(ri,j |1,1 )(1−ν̄i,j )
m
(d)
(u) Q
λ̄j,q
ω̄j
q=1
q6=i
m
m
Q
(d)
(u)
(d)
(u) Q
λ̄j,q +(1−ω̄j )
(1−λ̄j,q )
ω̄j
q=1
q=1
q6=i
q6=i
m
Q
(d)
λ̄j,i
i=1
m
m
Q
Q
(d)
(d)
λ̄j,i +
(1−λ̄j,i )
i=1
i=1

i = 1, . . . , m, j = 1, . . . , n

i = 1, . . . , m, j = 1, . . . , n

j = 1, . . . , n

p(hj = 0)

j = 1, . . . , n
(11)

4. Simulation Results and Discussions
In this section, we analyze the performance of the MP decision fusion algorithm. We first consider the computational complexity, then we pass to evaluate
the performance in terms of error probability. In particular, we compare the
performance of the MP-based scheme to those of the optimum fusion rule [18]
(whenever possible), the soft isolation scheme presented in [16], the hard isolation scheme described in [14] and the simple majority rule. In our comparison,
18

we consider both independent and Markovian system states, for both small and
large observation window m.
4.1. Complexity Discussion
In order to evaluate the complexity of the message passing algorithm and
compare it to that of the optimum fusion scheme, we consider both the number
of operations and the running time. By number of operations we mean the
number of additions, substractions, multiplications and divisions performed by
the algorithm to estimate the vector of system states s.
By looking at equation (11), we see that running the message passing algorithm requires the following number of operations:
(l)

• 3n + 5 operations for each of τ̄i

(r)

and τ̄i .

(l)

(r)

• 3 operations for each of ϕ̄i and ϕ̄i .
(u)

• 11 operations for ν̄i,j .
(d)

• 3n + 5 operations for ν̄i,j .
(d)

• 3n + 2 operations for ν̄m,j .
(d)

• 11 operations for λ̄j,i .
(u)

(d)

• 3m + 2 operations for each of λ̄j,i and ω̄j .
summing up to 12n+6m+49 operations for each iteration over the factor graph.
On the other hand, in the case of independent node states, the optimal scheme
in [18] requires 2m (m + n) operations. Therefore, the MP algorithm is much
less computationally expensive since it passes from an exponential to a linear
complexity in m. An example of the difference in computational complexity
between the optimum and the MP algorithms is depicted in Figure 8.
With regard to time complexity, Table 1 reports the running time of the
MP and the optimal schemes. For n = 20, the optimal scheme running time is
17.547 times larger than that of the message passing algorithm. On the other

19

log(number of operations)

10

6

Message Passing Scheme
Optimal Scheme

105

104

103

102
10

20

30

40

50

60

70

80

90

100

n
Figure 8: Number of operations required for different n, m = 10 and 5 message passing local
iterations for message passing and optimal schemes.

Table 1: Running Time (in seconds) for the Optimal and the Message Passing algorithms for:
m = 10, ε = 0.15, Number of Trials = 105 and Message Passing Iterations = 5.

Setting/Scheme

Message Passing

Optimal

n = 20,α = 0.45

943.807114

1.6561e+04

n = 100,α = 0.49

4888.821497

2.0817e+04

hand, for the case of n = 100, the optimal scheme needs around 4.258 times
more than the message passing scheme. The tests have been conducted using
Matlab 2014b running on a machine with 64-bit windows 7 OS with 16,0 GB of
installed RAM and Intel Core i7-2600 CPU @ 3.40GHz.
4.2. Performance Evaluation
In this section, we use numerical simulations to evaluate the performance of
the message passing algorithm and compare them to the state of the art schemes.
The results are divided into four parts. The first two parts consider, respectively,
simulations performed with small and large observation windows m. Then, in
the third part, we investigate the optimum behaviour of the Byzantines over
20

100

Majority
Hard Isolation Scheme
Soft Isolation Scheme
Message Passing
Optimal

log(Pe)

10-1
10-2
10-3

10

-4

0

0.1

0.2

0.3

0.4

0.5

α
Figure 9: Error probability as a function of α for the following setting: n = 20, independent
Sequence of States ρ = 0.5, ε = 0.15, m = 10 and Pmal = 1.0.

a range of observation windows size. Finally, in the last part, we compare the
case of independent and Markovian system states.
The simulations were carried out according to the following setup. We considered a network with n = 20 nodes, ε = 0.15, ρ = {0.95, 0.5} corresponding to
Markovian and independent sequence of system states, respectively. The probability α that a node is Byzantine is in the range [0, 0.45] corresponding to a
number of Byzantines between 0 and 9. As to Pmal we set it to either 0.5 or 11 .
The number of message passing iterations is 5. For each setting, we estimated
the error probability over 105 trials.
4.2.1. Small m
To start with, we considered a small observation window, namely m = 10.
With such a small value of m, in fact, it is possible to compare the performance
of the message passing algorithm to that of the optimum decision fusion rule.
The results we obtained are reported in Figure 9. Upon inspection of the figure,
the superior performance of the message passing algorithm over the Majority,
1 It

is know from [18] that for the Byzantines the optimum choice of Pmal is either 0.5 or

1 depending on the considered setup.

21

100
Majority
Hard Isolation Scheme
Soft Isolation Scheme
Message Passing
Optimal

log(Pe)

10-1
10-2
10-3
10-4
10-5

0

0.05

0.1

0.15

0.2

0.25

0.3

0.35

0.4

0.45

α
Figure 10: Error probability as a function of α for the following setting: n = 20, Markovian
Sequence of States ρ = 0.95, ε = 0.15, m = 10 and Pmal = 1.0

Soft and Hard isolation schemes is confirmed. More interestingly, the message
passing algorithm gives nearly optimal performance, with only a negligible performance loss with respect to the optimum scheme.
Figure 10 confirms the results shown in Figure 9 for Markovian system states
(ρ = 0.95).
4.2.2. Large m
Having shown the near optimality of the message passing scheme for small
values of m; we now leverage on the small computational complexity of such a
scheme to evaluate its performance for large values of m (m = 30). As shown
in Figure 11, by increasing the observation window all the schemes give better
performance, with the message passing algorithm always providing the best
performance. Interestingly, in this case, when the attacker uses Pmal = 1.0, the
message passing algorithm permits to almost nullify the attack of the Byzantines
for all the values of α. Concerning the residual error probability, it is due to
the fact that, even when there are no Byzantines in the network (α = 0), there
is still an error floor caused by the local errors at the nodes ε. For the case
of independent states, such an error floor is around 10−4 . In Figure 11 and

22

100
Majority
Hard Isolation Scheme
Soft Isolation Scheme
Message Passing

log(Pe)

10-1
10-2
10-3
10-4
10-5

0

0.05

0.1

0.15

0.2

0.25

0.3

0.35

0.4

0.45

α
Figure 11: Error probability as a function of α for the following setting: n = 20, Markovian
Sequence of States ρ = 0.95, ε = 0.15, m = 30 and Pmal = 1.0.

12, this error floor decreases to about 10−5 because of the additional a-priori
information available in the Markovian case.
4.2.3. Optimal choice of Pmal for the Byzantines
One of the main results proven in [18], is that setting Pmal = 1 is not
necessarily the optimal choice for the Byzantines. In fact, when the FC manages
to identify which are the malicious nodes, it can exploit the fact the malicious
nodes always flip the result of the local decision to get useful information about
the system state. In such cases, it is preferable for the Byzantines to use Pmal =
0.5 since in this way the reports send to the FC does not convey any information
about the status of the system. However, in [18], it was not possible to derive
exactly the limits determining the two different behaviours for the Byzantines
due to the impossibility of applying the optimum algorithm in conjunction with
large observation windows. By exploiting the low complexity of the message
passing scheme, we are now able to overcome the limits of the analysis carried
out in [18].
Specifically, we carried out an additional set of experiments by fixing α =
0.45 and varying the observation window in the interval [5,20]. The results we

23

10-1

log(Pe)

10

Majority
Hard Isolation Scheme
Soft Isolation Scheme
Message Passing

-2

10-3

10-4

10-5

0

0.05

0.1

0.15

0.2

0.25

0.3

0.35

0.4

0.45

α
Figure 12: Error probability as a function of α for the following setting: n = 20, Markovian
Sequence of States ρ = 0.95, ε = 0.15, m = 30 and Pmal = 0.5.

obtained confirm the general behaviour observed in [18]. For instance, in Figure
13, Pmal = 1.0 remains the Byzantines’ optimal choice up to m = 13, while for
m > 13, it is preferable for them to use Pmal = 0.5. Similar results are obtained
for independent system states as shown in Figure 14.
4.2.4. Comparison between independent and Markovian System States
In this subsection, we provide a comparison between the cases of Markovian
and independent system states.
By looking at Figure 13 and 14, we see that the Byzantines switch their
strategy from Pmal = 1 to Pmal = 0.5 for a smaller observation window (m = 10)
in the case of independent states (the switching value for the Markovian case
is m = 13). We can explain this behaviour by observing that in the case
of Markovian states, using Pmal = 0.5 results in a strong deviation from the
Markovianity assumption of the reports sent to the FC thus making it easier
the isolation of byzantine nodes. This is not the case with Pmal = 1, since, due
to the symmetry of the adopted Markov model, such a value does not alter the
expected statistics of the reports.
As a last result, in Figure 15, we compare the error probability for the case

24

100

log(Pe)

10-1
10-2
10-3

Hard Isolation Pmal=0.5
Hard Isolation Pmal=1.0

10

Soft Isolation P mal=0.5

-4

Soft Isolation P mal=1.0
Message Passing Pmal=0.5

10-5

Message Passing Pmal=1.0

8

10

12

14

16

18

20

m
Figure 13: Error probability as a function of m for the following settings: n = 20, Markovian
Sequence of States ρ = 0.95, ε = 0.15 and α = 0.45.

100

log(Pe)

10-1
10-2
Hard Isolation Pmal=0.5

10

Hard Isolation Pmal=1.0

-3

Soft Isolation P mal=0.5
Soft Isolation P mal=1.0
Message Passing Pmal=0.5
Message Passing Pmal=1.0

10-4

5

10

15

20

m
Figure 14: Error probability as a function of m for the following settings: n = 20, independent
Sequence of States ρ = 0.5, ε = 0.15 and α = 0.45.

25

10-2

Message Passing ρ =0.5
Optimal ρ =0.5
Message Passing ρ =0.95
Optimal ρ =0.95

log(Pe)

10-3

10-4

10-5

0

0.05

0.1

0.15

0.2

0.25

0.3

0.35

0.4

0.45

α
Figure 15: Comparison between the case of independent and Markovian system states (n = 20,
ρ = {0.5, 0.95}, ε = 0.15, m = 10, Pmal = 1.0).

of independent and Markov sources. Since we are interested in comparing the
achievable performance for the two cases, we consider only the performance
obtained by the optimum and the message passing algorithms. Upon inspection
of the figure, it turns out that the case of independent states is more favourable
to the Byzantines than the Markov case. The reason is that the FC may exploit
the additional a-priori information available in the Markov case to identify the
Byzantines and hence make a better decision. Such effect disappears when α
approaches 0.5, since in this case the Byzantines tend to dominate the network.
In that case, the Byzantines’ reports prevail the pool of reports at the FC
and hence, the FC becomes nearly blind so that even the additional a-priori
information about the Markov model does not offer a great help.

5. Conclusions
In this paper, we proposed a near-optimal message passing algorithm based
on factor graph for decision fusion in multi-sensor networks in the presence of
Byzantines. The effectiveness of the proposed scheme is evaluated by means of
extensive numerical simulations both for the case of independent and Markov
sequence of states. Experiments showed that, when compared to the optimum
26

fusion scheme, the proposed scheme permits to achieve near-optimal performance at a much lower computational cost: specifically, by adopting the new
algorithm based on message passing we were able to reduce the complexity from
exponential to linear. Such reduction of the complexity permits to deal with
large observation windows, thus further improving the performance of the decision. Results on large observation windows confirmed the dual behavior in the
attacking strategy of the Byzantines, looking for a trade-off between pushing the
FC to make a wrong decision on one hand and reducing the mutual information
between the reports and the system state on the other hand. In addition, the
experiments showed that the case of independent states is more favorable to
Byzantines than the Markovian case, due to the additional a-priori information
available at the FC in the Markovian case.
As future work, we plan to focus on a scenario more favorable to the Byzantines, by giving them the possibility to access the observation vectors. In this
way, they can focus their attack on the most profitable cases and avoid to flip
the local decision when it is very likely that their action will have no effect on
the FC decision. Considering the case where the nodes can send to the FC more
extensive reports (multi-bit case) [33] is another interesting extension.

References
References
[1] A. Vempaty, T. Lang, P. Varshney, Distributed inference with byzantine
data: State-of-the-art review on data falsification attacks, IEEE Signal
Processing Magazine 30 (5) (2013) 65–75.
[2] M. Abdelhakim, L. Lightfoot, J. Ren, T. Li, Distributed detection in mobile
access wireless sensor networks under byzantine attacks, IEEE Transactions
on Parallel and Distributed Systems, 25 (4) (2014) 950–959. doi:10.1109/
TPDS.2013.74.

27

[3] W. Wang, H. Li, Y. Sun, Z. Han, Securing collaborative spectrum sensing against untrustworthy secondary users in cognitive radio networks,
EURASIP Journal on Advances in Signal Processing 2010 (2010) 4.
[4] A. S. Rawat, P. Anand, H. Chen, P. K. Varshney, Collaborative spectrum
sensing in the presence of byzantine attacks in cognitive radio networks,
IEEE Transactions on Signal Processing 59 (2) (2011) 774–786.
[5] R. Zhang, J. Zhang, Y. Zhang, C. Zhang, Secure crowdsourcing-based cooperative spectrum sensing, in: Proc. of INFOCOM 2013, IEEE Conference
on Computer Communications, IEEE, 2013, pp. 2526–2534.
[6] W. Wang, L. Chen, K. G. Shin, L. Duan, Secure cooperative spectrum
sensing and access against intelligent malicious behaviors, in: Proc. of INFOCOM 2014, IEEE Conference on Computer Communications, IEEE,
2014, pp. 1267–1275.
[7] Y. Sun, Y. Liu, Security of online reputation systems: The evolution of
attacks and defenses, IEEE Signal Processing Magazine 29 (2) (2012) 87–
97.
[8] S. Marano, V. Matta, L. Tong, Distributed detection in the presence of
byzantine attacks, IEEE Transactions on Signal Processing, 57 (1) (2009)
16–29.
[9] B. Kailkhura, S. Brahma, P. Varshney, Optimal byzantine attacks on distributed detection in tree-based topologies, in: IEEE International Conference on Computing, Networking and Communications (ICNC), 2013, pp.
227–231. doi:10.1109/ICCNC.2013.6504085.
[10] M. Barni, B. Tondi, Multiple-observation hypothesis testing under adversarial conditions, in: Proc. of WIFS’13, IEEE International Workshop on
Information Forensics and Security, Guangzhou, China, 2013, pp. 91–96.
[11] M. Barni, F. Pérez-González, Coping with the enemy:

Advances in

adversary-aware signal processing, in: 2013 IEEE International Confer28

ence on Acoustics, Speech and Signal Processing, 2013, pp. 8682–8686.
doi:10.1109/ICASSP.2013.6639361.
[12] Z. Chair, P. Varshney, Optimal data fusion in multiple sensor detection
systems, IEEE Transactions on Aerospace and Electronic Systems AES22 (1) (1986) 98–101. doi:10.1109/TAES.1986.310699.
[13] P. K. Varshney, Distributed Detection and Data Fusion, Springer-Verlag,
1997.
[14] A. S. Rawat, P. Anand, H. Chen, P. K. Varshney, Collaborative spectrum
sensing in the presence of byzantine attacks in cognitive radio networks,
IEEE Transactions on Signal Processing 59 (2) (2011) 774–786. doi:10.
1109/TSP.2010.2091277.
[15] A. Vempaty, K. Agrawal, P. Varshney, H. Chen, Adaptive learning of byzantines’ behavior in cooperative spectrum sensing, in: Proc. of WCNC’11,
IEEE Conf. on Wireless Communications and Networking, 2011, pp. 1310–
1315. doi:10.1109/WCNC.2011.5779320.
[16] A. Abrardo, M. Barni, K. Kallas, B. Tondi, Decision fusion with corrupted
reports in multi-sensor networks: A game-theoretic approach, in: 53rd
IEEE Conference on Decision and Control, 2014, pp. 505–510. doi:10.
1109/CDC.2014.7039431.
[17] R. Chen, J. M. Park, K. Bian, Robust distributed spectrum sensing in cognitive radio networks, in: Proc. of INFOCOM 2008, 27th IEEE Conference
on Computer Communications, 2008, pp. –. doi:10.1109/INFOCOM.2008.
251.
[18] A. Abrardo, M. Barni, K. Kallas, B. Tondi, A game-theoretic framework for
optimum decision fusion in the presence of byzantines, IEEE Transactions
on Information Forensics and Security 11 (6) (2016) 1333–1345. doi:10.
1109/TIFS.2016.2526963.

29

[19] S. M. Aji, R. J. McEliece, The generalized distributive law, IEEE Transactions on Information Theory 46 (2) (2000) 325–343. doi:10.1109/18.
825794.
[20] P. Pakzad, V. Anantharam, A new look at the generalized distributive
law, IEEE Transactions on Information Theory 50 (6) (2004) 1132–1155.
doi:10.1109/TIT.2004.828058.
[21] R. Gallager, Low-density parity-check codes, IRE Transactions on Information Theory 8 (1) (1962) 21–28. doi:10.1109/TIT.1962.1057683.
[22] S. Verdu, H. V. Poor, Abstract dynamic programming models under commutativity conditions, SIAM Journal on Control and Optimization 25 (4)
(1987) 990–1006.
[23] J. Pearl, M. Kaufmann, Probabilistic reasoning in intelligent systems, san
mateo, ca, Cal.: Morgan Kaufmann.
[24] L. Rabiner, B. Juang, An introduction to hidden markov models, IEEE
ASSP Magazine 3 (1) (1986) 4–16. doi:10.1109/MASSP.1986.1165342.
[25] K. W. Choi, E. Hossain, Estimation of primary user parameters in cognitive radio systems via hidden markov model, IEEE Transactions on Signal
Processing 61 (3) (2013) 782–795. doi:10.1109/TSP.2012.2229998.
[26] I. A. Akbar, W. H. Tranter, Dynamic spectrum allocation in cognitive
radio using hidden markov models: Poisson distributed case, in: IEEE
Proceedings of SoutheastCon, 2007, pp. 196–201. doi:10.1109/SECON.
2007.342884.
[27] T. Jiang, H. Wang, A. V. Vasilakos, Qoe-driven channel allocation schemes
for multimedia transmission of priority-based secondary users over cognitive
radio networks, IEEE Journal on Selected Areas in Communications 30 (7)
(2012) 1215–1224. doi:10.1109/JSAC.2012.120807.

30

[28] Y. Ephraim, N. Merhav, Hidden markov processes, IEEE Transactions on
information theory 48 (6) (2002) 1518–1569.
[29] D. J. MacKay, Information theory, inference and learning algorithms, Cambridge university press, 2003.
[30] F. R. Kschischang, B. J. Frey, H.-A. Loeliger, Factor graphs and the sumproduct algorithm, IEEE Transactions on Information Theory 47 (2) (2001)
498–519.
[31] T. Richardson, R. Urbanke, Modern coding theory, Cambridge University
Press, 2008.
[32] Y. Mao, A. H. Banihashemi, A heuristic search for good low-density paritycheck codes at short block lengths, in: Communications, 2001. ICC 2001.
IEEE International Conference on, Vol. 1, IEEE, 2001, pp. 41–44.
[33] B. Kailkhura, S. Brahma, P. Varshney, On the performance analysis of
data fusion schemes with byzantines, in: IEEE International Conference on
Acoustics, Speech and Signal Processing (ICASSP), 2014, pp. 7411–7415.
doi:10.1109/ICASSP.2014.6855040.

31

