Informatica 41 (2017) 193–207 193
Defense Strategies against Byzantine Attacks in a Consensus-Based Network
Intrusion Detection System
Michel Toulouse, Hai Le and Cao Vien Phung
Vietnamese German University, Vietnam
E-mail: michel.toulouse, hai.lh@vgu.edu.vn, caovienphung@gmail.com
Denis Hock
Frankfurt University of Applied Sciences, Germany
E-mail: dehock@fb2.fra-uas.de
Keywords: network security, intrusion detection, consensus algorithms, Byzantine attacks
Received: March 29, 2017
The purpose of a Network Intrusion Detection System (NIDS) is to monitor network traffic such to detect
malicious usages of network facilities. NIDSs can also be part of the affected network facilities and be
the subject of attacks aiming at degrading their detection capabilities. The present paper investigates such
vulnerabilities in a recent consensus-based NIDS proposal [1]. This system uses an average consensus
algorithm to share information among the NIDS modules and to develop coordinated responses to network
intrusions. It is known however that consensus algorithms are not resilient to compromised nodes sharing
falsified information, i.e. they can be the target of Byzantine attacks. Our work proposes two different
strategies aiming at identifying compromised NIDS modules sharing falsified information. Also, a sim-
ple approach is proposed to isolate compromised modules, returning the NIDS into a non-compromised
state. Validations of the defense strategies are provided through several simulations of Distributed Denial
of Service attacks using the NSL-KDD data set. The efficiency of the proposed methods at identifying
compromised NIDS nodes and maintaining the accuracy of the NIDS is compared. The computational
cost for protecting the consensus-based NIDS against Byzantine attacks is evaluated. Finally we analyze
the behavior of the consensus-based NIDS once a compromised module has been isolated.
Povzetek: Sistemi za odkrivanje napadov v omrežjih temeljijo na pojavih nenavadnega prometa, vendar so
občutljivi na napade. Prispevek opisuje obrambo pred bizantinskimi napadi.
1 Introduction
Network intrusion detection systems are part of a vast ar-
ray of tools that protect computer infrastructures against
malicious activities. The specific task of NIDSs is to mon-
itor computer network infrastructures, seeking to identify
malicious intends through the analysis of network traffic.
Today’s computer networks are quite large, composed of
several heterogeneous sub-networks. Consequently, traffic
monitoring often needs to be done distributively with sen-
sors and traffic analysis modules placed at different strate-
gic locations, in charge of monitoring and analyzing the
traffic of a specific sub-network.
Usually, NIDS monitoring modules are connected by a
network, allowing security information collected about a
sub-network to be shared with other NIDS modules. Which
information is shared and how it is shared often character-
ize the organization of NIDSs as centralized, hierarchical
or distributed [2]. The monitoring modules of centralized
and hierarchical NIDS architectures, which can be limited
to simply collecting data, send their information up in the
hierarchy for further analysis. To the extend that analy-
sis and responses depend on a single or few modules in the
NIDS, these systems can be completely incapacitated by at-
tacks that target the more intelligent modules. A common
mitigation for these risks is to avoid a single point of fail-
ure by using distributed Intrusion Detection Systems [3, 4].
Modules in distributed intrusion detection systems are of-
ten full scale sensing and analytical devices. The modules
cooperate by sharing information to address attacks from
concurrent sources (such as distributed denial of service),
to develop network wide coordinated responses to attacks
or simply to increase the detection accuracy of each NIDS
module. Early distributed systems [5, 6], where also build
upon a master–slave architecture and require the data to be
sent to a central location for further analysis. Today, us-
ing peer-to-peer systems [7, 8, 9, 10], it is possible to rec-
ognize attacks by analyzing shared information in a fully
distributed manner.
While it is more difficult to completely disable dis-
tributed systems compared to centralized ones, modules of
a distributed system can still be the target of attacks aim-
ing to disable locally the system or to mask attacks in some
sub-networks to other nodes of the distributed NIDS. The
194 Informatica 41 (2017) 193–207 M. Toulouse et al.
present research addresses the vulnerability of a recently
proposed fully distributed NIDS [1]. This system uses an
average-consensus algorithm for computing network wide
security information that can then be used to recognize at-
tacks and activate coordinated responses to malignant ac-
tivities. However, it is well known that consensus algo-
rithms are not resilient to compromised nodes sharing fal-
sified information, i.e. they can be the target of Byzantine
attacks.
Consensus algorithms are based on peer-to-peer commu-
nications among neighbor nodes of a computer network
(no routing). They are distributed iterative algorithms in
which each node of the network repeatedly updates its cur-
rent value based on its own previous value and the previous
values of its neighbors in the network. The objective is to
reach a "consensus", i.e. each node computes a same out-
put that depends on initial values distributed across the net-
work while using only local updates. Repeating such local
computation, and given overlapping neighborhoods, a con-
sensus eventually emerges by diffusion of local updates.
Consensus algorithms have a long history in computer
science where they provide solutions to distributed com-
puting problems. For example, consensus algorithms solve
the leader election problem, where processes must select
one of them to coordinate tasks in a distributed system
[11]. Consensus algorithms have also found applications
or research interests in physics [12], process control [13],
robotic [14], operations research [15], services at IoT edge
nodes [16], not to mention its application in the controver-
sial bitcoin currency [17].
Average consensus refers to a particular form of consen-
sus where cooperative nodes compute the average sum of
their initial values. Average consensus algorithms also have
a wide range of applications, for example we find them
recently in wireless network applications such as cooper-
ative spectrum sensing in cognitive radio networks [18],
distributed detection in wireless networks [19], sensor net-
works [20].
Consensus algorithms vulnerabilities to sharing falsi-
fied information have been known for a long time. Orig-
inally, consensus algorithms solved the problem of reach-
ing agreement assuming a non-faulty non-adversarial com-
puting environment. In reality, links can fail, nodes can
stop transmitting data to neighbors (faulty links, nodes) or
nodes can transmit incorrect data, possibly falsified by an
adversarial actor (Byzantine nodes). The resilience of con-
sensus algorithms has been analyzed in the context of fault-
tolerant systems in Lamport, Pease and Shostack [21, 22].
The problem of reaching consensus in faulty and adversar-
ial environments became known as the Byzantine agree-
ment problem [22]. The problem asks under which condi-
tions consensus can be reached in the presence of Byzan-
tine faults. In [21], it is proved that resilient consensus
algorithms cannot be designed in a fully connected net-
work (complete graph) of n processors if the number m
of Byzantine nodes is 3m + 1 ≥ n. The Byzantine agree-
ment problem in [22] refers specifically to attacks in which
Byzantine nodes modify the initial values for which con-
sensus is computed (data falsification attacks). Since then,
the Byzantine agreement problem has been adapted to con-
sider new failure conditions, i.e. different attack models, as
well as quite diverse network settings.
Research studies aiming at detecting Byzantine nodes
are of a particular relevance to our work. In [23, 24], a tech-
nique based on the detection of outliers is applied to find
compromised nodes in a consensus-based spectrum sens-
ing algorithm for ad hoc wireless networks. In [24], several
attack models are proposed to subvert the spectrum sens-
ing algorithm. One attack model is a covert adaptive data
injection attack, which adjusts attack strategies by manipu-
lating the sensing results. The proposed defense consists to
isolate neighbor nodes that send numerical data that deviate
too much from some norm. In [25], the detection of Byzan-
tine nodes is derived from reputation-based trust manage-
ment strategies. In this paper, one type of attacks consists
of malicious robots injecting false data to neighbors in a
multirobot system controlled by a consensus algorithm for
the purpose of formation control. The proposed defense
system consists to decrease the consensus weight contri-
bution of a node that has its reputation drops during the
computation of consensus states. Defense strategies against
Byzantine attacks also originate from research in process
control and control theory, fields where one of the focus is
to provide methodological approaches to detect faulty com-
ponents in a system. In [26, 27, 28] different approaches
based on control theory are proposed to detect Byzantine
attacks on consensus algorithms. In [26, 27], using model-
based fault detection techniques, it is shown that if the net-
work of consensus nodes is 2k + 1 connected then up to k
Byzantine nodes can be identified. However model-based
proposals for detecting multiple attackers seem computa-
tionally costly, they likely have only limited applicability.
Our work focuses on detecting Byzantine attackers in the
consensus-based NIDS of [1]. One of our two detection
techniques, outlier detection, derives from outlier methods
monitoring applications of consensus algorithms to coop-
erative spectrum sensing [24]. The second detection tech-
nique, fault detection, derives from a model-based fault
detection technique in process control and control theory
[27]. We also introduce an approach to remove compro-
mised NIDS modules such that the intrusion detection sys-
tem can be returned to a non-compromised state.
The removal of compromised modules conflicts with
some mathematical assumptions about average consensus
algorithms. Indeed, proofs that neighbor to neighbor data
exchanges converge to a consensus are valid under the as-
sumption the network is static. The removal of a compro-
mised module changes the network topology of the NIDS,
thus the system is no longer guarantee to work correctly
even under normal circumstances (no attacks). Here, the
relevant background research comes from dynamic consen-
sus theory concerned with applications of consensus algo-
rithms to dynamic network topologies, facing issues such
as communication time-delays, failing physical links or
Defense Strategies against Byzantine Attacks . . . Informatica 41 (2017) 193–207 195
network nodes and mobile wireless networks [29, 30, 31].
While our objective is only to logically remove (isolate) a
compromised NIDS module, the network conditions this is
creating are quite similar to the work in [32, 33, 34], there-
fore we have drawn our solution more specifically from
these researches.
All the solutions proposed in this paper are based on
local knowledge. Decisions to categorize modules as
compromised and to further removing the compromised
module depend on information gathered from neighbors
only. The computation to detect and remove compromised
modules is therefore fully distributed, thus keeping the
consensus-based NIDS fully distributed. Last, we have de-
signed our defense strategies to protect the NIDS against
a single compromised module. Detecting and removing
multiple compromised modules following potentially co-
ordinated attackers is left to a future work.
The major contributions of this paper include present-
ing the impact of malicious peers on the detection capa-
bility of our consensus based Network Intrusion Detection
Systems (NIDS) scheme. We analyze the vulnerabilities
of consensus-based NIDS by proposing a Byzantine attack
model, which aim to adjust and stealthily manipulate re-
sults. Our defense strategies detect and remove compro-
mised NIDS modules without impacting the logical func-
tionality of the system. We compare these strategies un-
der various detection parameters and network topologies
through extensive simulations and analysis using a real
NIDS and the NSL-KDD data set [35]. Our results demon-
strate that the conducted method can indeed unveil peers
with malicious intend and disruptions in the information
exchange of peer-to-peer NIDS.
In the remainder, we briefly describe the consensus-
based NIDS in [1]. We point out variations of falsification
attacks and outline our two detection techniques to adjust
the trustworthiness of participating peers. Thereafter, we il-
lustrate the salient features of our prediction model to iden-
tify Byzantine peers and describe a practical experiment we
conducted to showcase its functionality.
2 Consensus based NIDS
This section describes the average consensus algorithm.
Next, a summary of the consensus-based NIDS in [1] is
provided. Lastly, we describe our approach to isolate com-
promised modules together with the mathematical back-
ground that supports this approach.
2.1 Average consensus
The average consensus algorithm computes the average
sum 1n
∑n
i=1 xi of some initial values x1, x2, . . . , xn. It is
a distributed algorithm where each process can be viewed
as running independently on a particular node of an undi-
rected graph. Let G = (V,E) be such a graph where
V = {v1, v2, . . . , vn} denotes the set of nodes, and E de-
notes the corresponding set of edges. Graphs have an ad-
jacency structure represented by an n × n adjacency ma-
trix (denoted by A here) where aij = 1 if and only if
(vi, vj) ∈ E, aij = 0 otherwise. The adjacency struc-
ture of G defines for each node vi ∈ G a neighborhood Ni
where Ni = {vj ∈ V |(vi, vj) ∈ E}.
Each node vi of G computes the following recurrence
equation:
xi(t+ 1) = Wiixi(t) +
∑
j∈Ni
Wijxj(t), (1)
where recurrence i is initialized with xi(0) = xi, the ini-
tial value of each node i (from now on we denote node vi
simply by i). The purpose of a consensus algorithm is to
make "consensus", i.e. xi(t) converges asymptotically to
1
n
∑n
i=1 xi for all nodes i ∈ G. As evidence from Equation
(1), each node i obtains xi(t + 1) using only its previous
value xi(t) and the previous values xj(t) of the nodes that
are in the neighborhood of i (xj , j ∈ Ni). Nonetheless, all
nodes converge to 1n
∑n
i=1 xi because the diffusion of the
local averages through neighborhoods that share common
nodes accounts for all nodes computing the global average.
Whether nodes reach consensus and which particular
consensus value is reached is determined by the dynamics
of the linear dynamical system that equation (1) specifies,
which in turn depends on the transition matrixW . Each en-
tryWij of matrixW represents a weight on edge (i, j) ∈ G.
These individual weights have to be chosen carefully to en-
sure convergence, and convergence to a specific value. For
example, in equation (1), making consensus on 1n
∑n
i=1 xi
can be obtained by computing local averages of xi(t) and
xj(t) for j ∈ Ni using Wij = 1|Ni|+1 for (i, j) ∈ G (in-
cluding self-edge (i, i)).
A system as in (1) can reach consensus if the weight
matrix satisfies certain conditions, as stated in [36]. Two
conditions concern our application of average consensus
to network intrusion detection: 1- the undirected graph G
needs to be connected, i.e. there is a path between each pair
of nodes; 2- the weight matrix W must be row stochas-
tic, i.e.
∑n
j=1Wij = 1, the sum of the weights of each
row equal 1 (note that for undirected graph, wij = wji,
therefore W = WT , consequently the weight matrix W
is doubly-stochastic,
∑n
j=1Wij =
∑n
i=1Wji = 1). Sev-
eral weight matrices satisfy these conditions, the following
matrices have been used for the consensus-based NIDS:
– Metropolis-Hasting matrix:
Wij =

1
1+max(di,dj)
if i 6= j and j ∈ Ni
1−
∑
k∈Ni Wik if i = j
0 if i 6= j and j 6∈ Ni
where di = |Ni|.
– Best-constant edge weight matrix:
Wij =
2
λ1(L) + λn−1(L)
196 Informatica 41 (2017) 193–207 M. Toulouse et al.
BA
1
A
3
B
C
B
B
B
D
C
C42
D
D
sensor
sensor
sensor
sensor
Figure 1: Network Intrusion Detection System.
where L is the Laplacian matrix of the NIDS network,
λ1, λn−1 are the first and n− 1 eigenvalues of L.
– Local-degree weights matrix where the weight of an
edge is the largest degree of its two adjacent vertices
Wij =
1
max{di, dj}
.
– Max-degree weight where dmax is the largest degree
of the vertices in the network
Wij =
1
dmax
.
Note for the last three matrices, Wii = 1−
∑
k∈Ni Wik
and Wij = 0 if j 6∈ Ni. Note also these weight matri-
ces guarantee asymptotic convergence, x(t) converges to
1
n
∑n
i=1 xi(0) as t → ∞, we refer to this average consen-
sus algorithm as the asymptotic average consensus. Weight
matrices have an impact on the speed of convergence (the
number of iterations needed to get close enough to the av-
erage sum) [37, 38]. Given an average consensus applica-
tion, it worth to compare the convergence speed of differ-
ent weight matrices to identify the one with the best per-
formance. It worth noticing that the graph topology also
impacts the convergence speed of average consensus algo-
rithms [39].
2.2 Consensus-based NIDS
As pictured in Figure 1, a consensus-based NIDS is a set
of modules each placed strategically on nodes of the moni-
tored computer network such to observe traffic in the corre-
sponding sub-network. Each module consists of traffic sen-
sors that receive copies of all transported packets within the
observed network and calculates an initial local probabil-
ity for observing benign or malignant network traffic. The
NIDS modules observing local network traffic are them-
selves connected by a physical network. Without lost of
generality, we assume that the physical links connecting
pairs of NIDS modules are direct (wired or wireless) phys-
ical links. The NIDS network is modeled by a graph where
each node of the graph represents an NIDS module. It is
assumed that this graph is connected. For the purpose of
analysis and comparisons, we study specific topologies of
NIDS networks, we refer to such specific network as an
NIDS network topology.
2.2.1 Network traffic analysis
The detection method of each NIDS module is "anomaly
based" using the well-known naive Bayes classifier. The
analysis focuses on detecting Distributed Denial of Service
(DDoS) attacks, such as Land-attack, Syn-flood and UDP-
storm. The naive Bayes classifier assess the statistical nor-
mal behavior - the ’likelihood’ of a set of values to occur -
with the help of labeled historic data. Our set of m fea-
tures includes most of the variables offered by the NLS
KDD data set, such as the number of bytes, service, and
number of connections. The probabilities of intrusion is
computed for each of these features. P (oj |h) expresses the
likelihood of the occurrence oj given the historic anoma-
lous ha or normal hn occurrences. Thus, if events receive
the same values than benign or malignant network traffic
during training, they result in a high probability for those.
Assuming conditional independence of the m features, the
joint likelihood P (Oi|h) of NIDS module i is the product
of all feature likelihoods:
P (Oi|h) =
m∏
j=1
P (oj |h). (2)
Each NIDS module locally assigns the joint likelihood, in-
dicating the abnormality of each event.
2.2.2 Consensus phase
Following the sensing and data analysis by the Bayesian
network, each NIDS module enters into a phase where
it computes the average sum of the n log-likelihoods:
1
n
∑n
i=1 xi(0), while communicating only with direct
neighbors. This phase is labeled as the NIDS consensus
phase. Let xi(0) = log(P (Oi|h)) be the initial state of
module i, where xi(0) is the likelihood for module i to
see a certain set of network features. As explained in sec-
tion 2.1, the average sum is computed iteratively and inde-
pendently by each module i as a weighted sum of xi and
the xj for j ∈ Ni as defined in equation (1). We iden-
tify as the consensus loop the iterations of equation (1) and
xi(t + 1) as the consensus value of module i at iteration
t + 1. The consensus phase is the computation performed
by the n consensus loops to reach consensus. This phase is
defined in mathematical terms by the following dynamical
system:
x(t+ 1) = Wx(t), t = 0, 1, . . . (3)
where x(t) is a vector of n entries denoting the n consensus
values at iteration t of the consensus phase, and W is the
weight matrix.
The stopping condition of consensus loop i (also known
as ’convergence parameter’ of the recurrence i) is given by
Defense Strategies against Byzantine Attacks . . . Informatica 41 (2017) 193–207 197
|xi(t+ 1)−xi(t)| < , i.e. when the change in the consen-
sus value from iteration t to iteration t+ 1 is smaller than a
pre-defined threshold value . For weight matrices satisfy-
ing convergence assumptions, the value |xi(t+ 1)− xi(t)|
decreases asymptotically as t → ∞, once this value is
smaller than , the corresponding consensus loop is said
to have converged. A consensus phase is completed once
each consensus loop has converged. The number of itera-
tions of a consensus phase is given by the consensus loop
that needed the largest number of iterations to satisfy the
stopping condition. The convergence speed of a consensus
phase is the number of iterations needed for the consen-
sus phase to complete. The value of  is set such to min-
imize the number of iterations during the consensus phase
while insuring accuracy of the decision about the state of
the network traffic. The consensus phase is synchronous,
all nodes must have completed the consensus loop at it-
eration t before proceeding to execute the consensus loop
iteration t+1. Finally, as a matter of implementation, once
an NIDS module has converged, it stops updating its con-
sensus value but continues to send the last updated value to
its neighbors.
2.3 Removing compromised modules
As discussed in the introduction, once a NIDS module j
has been identified by a neighbor i as compromised, mod-
ule j must be logically disconnected from i to maintain the
integrity of the intrusion detection system. It is relatively
simple to disconnect an NIDS module locally because the
weight matrix W is known to each NIDS module i (or at
least the weights associated to row i are known). Once a
node i has identified a neighbor j as compromised, node i
simply can apply the following change to the weight ma-
trix: Wij = 0. Unfortunately, Wiixi(t) +
∑
j∈Ni Wij(t)
no longer sum up to 1, then W fails to satisfy one of the
two consensus convergence conditions. In order to fully
address this issue, we have revisited the convergence proofs
of average consensus, more specifically the convergence
proofs for dynamic consensus (consensus under dynamic
network topologies).
The consensus algorithm described in Section 2.1 is a
static consensus algorithm because the weight matrix stay
unchanged during the consensus phase. The weight ma-
trix (which is actually a weighted adjacency matrix) mir-
rors the physical network topology underlying the NIDS.
Static consensus cannot be used for applications where the
underlying network topology is dynamic, i.e. where links
or nodes fail, or where nodes enter and leave the network
dynamically such as for wireless ad-hoc network. Dy-
namic consensus theory formally addresses consensus con-
vergence issues arising in dynamical networks. Dynamic
consensus is relevant to our work as the impact on the NIDS
of logically removing a compromised module is (model
wise) the same as a failing node. The convergence theory
of dynamic consensus is the mathematical support to our
solution strategy for the removal of compromised nodes
in a consensus-based NIDS. There are several avenues in
control theory to address dynamic network, the work in
[32, 33, 34] is directly related to our problem.
As stated in section 2.1, the two convergence conditions
the consensus phase of NIDS must satisfy are network con-
nectivity and stochastic weight matrix. In [32], it is shown
that the connectivity condition is surprisingly mild for dy-
namic network topologies, the collection of dynamically
changing topologies during the consensus phase only needs
to be jointly connected to guarantee convergence. In our
work this condition is always satisfied. Only one NIDS
module is removed during a consensus phase, therefore
the collection of network topologies is limited to two. For
the NIDS network topologies tested in the experimentation
section of this paper, each topology is connected.
We have violation of convergence condition related to
the stochastic weight matrix, this is fixed as followed. Once
a node i has identified a neighbor j as compromised, node
i set Wij = 0, thus locally removing the link (i, j). The
situation where Wiixi(t) +
∑
j∈Ni Wij(t) < 1 from set-
ting Wij = 0 is eliminated by increasing the weight of the
self-edge by the same amount Wij : Wii = Wii + Wij .
This solution is only implementable if the information for
updating the weights of row i in W can be computed lo-
cally. This is the case for the Metropolis-Hasting weight
matrix as the weight of each edge depends on the degree
of adjacent nodes. This will not work for weight matri-
ces like the best-constant edge weight matrix or the max-
degree weight matrix where the weights depend on global
information (such as the max-degree node in the network).
Tests in this paper where nodes are logically disconnected
in a NIDS network topology are based on the Metropolis-
Hasting weight matrix.
3 Detection of Byzantine attacks
Byzantine attacks aim at degrading the accuracy of the net-
work intrusion detection system. Accuracy is defined as
follow:
TP + TN
TP + TN + FP + FN
,
where TP (True Positive) is the number of attacks detected
when it is actually an attack; TN (True Negative) is the
number of normals detected when it is actually normal; FP
(False Positive) is the number of attacks detected when it is
actually normal; FN (False Negative) is the number of nor-
mals detected when it is actually an attack. Byzantine at-
tacks of NIDS modules can aim at masking malicious traf-
fic by decreasing the probability of attacks initially com-
puted by the naive Bayesian. Attackers may also increase
the probability of attacks computed by the naive Bayesian,
thus increasing the number of false positives, the reliability
of the system is then questioned by the system administra-
tors.
This section first provides an attack model on the con-
sensus phase, this model is used by tests conducted in the
198 Informatica 41 (2017) 193–207 M. Toulouse et al.
Figure 2: Convergence speeds with and without loop dis-
ruption.
next section. Second, two techniques are described which
aim at identifying compromised NIDS modules.
3.1 Byzantine attack model
Byzantine attacks on the consensus phase of consensus-
based intrusion detection algorithms can take the following
forms [27, 40]:
1. Data falsification attacks: Sensor values are falsified,
thus the consensus loop is initialized with values orig-
inating from falsified network traffic readings;
2. Consensus loop disruptions:
(a) the attacker ignore the consensus value com-
puted at each iteration and keeps transmitting the
same constant c;
(b) the attacker send to its neighbors a falsified con-
sensus value [27].
Figure 2 illustrates the impact of a type 2(a) attack on
the convergence speed of the consensus phase. It plots the
distribution of the convergence speed of 1000 consensus
phases each having only honest NIDS modules (No attack)
versus a scenario where each consensus phase has one com-
promised module sending the same constant value c to its
neighbors (Attack). Figure 2 shows that convergence speed
is much slower in a compromised system, each consensus
phase needing between 250 to 300 iterations to converge,
while in a system without a compromised module consen-
sus phases need between 40 to 125 iterations to converge.
Moreover, NIDS modules in a compromised system fail to
converge to the average consensus 1N
∑N
i=1 xi(0), rather
they all converge to c [41].
In this paper we seek to discover consensus loop disrup-
tion attacks of type 2(b). Equation (4) below models this
type of attacks inside the consensus loop of a compromised
NIDS module:
xj(t+ 1) = Wjjxj(t) +
∑
i∈Nj
Wjixi(t) + uj(t). (4)
This recurrence equation is similar to equation (1) excepts
for the variable uj(t) which models the value selected
by the attacker for modifying the true consensus value of
the compromised node j. The falsified consensus value
xj(t + 1) is sent to all the neighbors of node j at iteration
t + 1. Other Byzantine attack models, including multiple
colluding attackers, are described in [24, 42].
3.2 Detection techniques
We describe two detection techniques that handle consen-
sus loop disruptions of type 2(b) by a single Byzantine at-
tacker. The first detection technique is an outlier detection
procedure. This procedure is executed by each module i
and evaluates at each consensus loop iteration the potential
that a neighbor of module i is compromised. The second
detection technique is an adaptation to cyber-attacks of a
model-based fault-detection technique in process engineer-
ing and control theory. Like the first one, it is a procedure
executed by each module, observing its neighbors, seeking
to identify a compromised one.
3.2.1 Outlier detection
Outlier detection techniques have been applied to detect
Byzantine attacks in wireless sensor networks [43]. These
techniques use distance thresholds between the value xj(t)
sent by a neighbor j to node i and some reference value
ri. For example, if ri(t) = xi(t), neighbor j is flagged
as compromised if |xj(t) − xi(t)| > λ for some threshold
value λ. However this idea had to be refined. For exam-
ple, a unique predefined threshold for all nodes may eas-
ily be discovered by intruders. Furthermore, as nodes of
a consensus algorithm converge to a same value, the abso-
lute differences |xj(t) − xi(t)| between two nodes i and j
converge to zero as t → ∞, rendering the outlier detec-
tion potentially insensitive when the absolute differences
get smaller than λ.
Adaptive thresholds have been proposed to address the
above issues [23, 24]. It consists for each node i to com-
pute a local threshold λi and to adapt the threshold at each
consensus iteration to the reduction of absolute differences
|xj(t)− xi(t)|. In [23], the threshold
λi(t+ 1) =
∑
j∈Ni |xj(t+ 1)− xi(t+ 1)|∑
j∈Ni |xj(t)− xi(t)|
λi(t) (5)
(for properly initialized λi(0)) is computed by each node
i and at each iteration of the consensus phase. The rule
in equation (5) computes λi using the diffusion dynam-
ics of consensus algorithms, so unless the attacker can get
multi-hops information access, it cannot foresee the value
of its neighbor thresholds. Consequently, the attacker can-
not adapt its consensus loop disruption attack to keep the
values under the radar of the detection procedure. As the
network converges towards consensus, the value λ con-
verges toward zero, leading to the attackers to be eventually
filter out.
Defense Strategies against Byzantine Attacks . . . Informatica 41 (2017) 193–207 199
Note that λi(t) partitions neighbors of node i into two
sets, those neighbors j that have a deviation |xj(t) −
xi(t)| ≥ λi(t) are considered suspicious, they constitute
the neighborhoodNFi of states that have less weight in the
computation of the consensus value xi(t+ 1):
xi(t+ 1) = xi(t) + 
∑
j∈NTi
xj(t) +

a
∑
j∈NFi
xj(t)
for some constant a. Our outlier detection method com-
putes the threshold λ as in equation (5). Those neighbors j
that have a deviation |xj(t)− xi(t)| ≥ λi(t) are flagged as
suspicious. We use a majority rule similar to [24] to convert
the status of a neighbor NIDS module j from suspicious to
attacker. Let B be the number of common neighbors be-
tween module i and module j. If more then dB2 e neighbors
of module i report j as suspicious then module j is con-
sidered as compromised, it is disconnected/removed from
the intrusion detection system. Note that we assume a sin-
gle attacker, if the majority rule identifies more than one
neighbor as compromised, the one with the largest devia-
tion is disconnected from the NIDS network.
3.2.2 Model-based fault detection
Fault detection is a field of control engineering concerned
with identifying and locating faulty components in a sys-
tem. The techniques in this field essentially compare mea-
surements of the actual behavior of a system with its an-
ticipated behavior. In model-based fault detection, the an-
ticipated behavior is described using mathematical mod-
els [44], the measured system variables are compared with
their model estimates. Comparisons between the system
and the model show deviations when there is a fault in the
real system. Such difference between the system and its
model is called residual or residual vector. There exist
several implementations of the model-based approach, the
observer-based technique [45] 1- seeks to discriminate be-
tween deviations caused by faults in the real process from
those caused by the estimations; 2- provides a residual vec-
tor that indicates the faulty system components (so called
directional residual). Observer-based approaches to cyber-
security have been proposed recently in different contexts
[46, 47, 48, 49, 50]. We focus more specifically on appli-
cations of observer-based fault detection to identify Byzan-
tine attackers in consensus-based algorithms [26, 27].
In order to detect Byzantine attackers during the consen-
sus phase of the NIDS, the design of the consensus loop
of each NIDS module is modified to include new matrices
based computation that estimate the consensus state vector
x(t), we name observer this new function of the consensus
loop. At each iteration of the consensus loop, the observer
computes a state vector xo(t) estimating x(t), where x(t)
is the vector storing the consensus values at iteration t of
the consensus loop. We first model the consensus loop dis-
ruption attack of equation (4) in matrix form:
x(t+ 1) = Wx(t) + Inu(t) (6)
where In is the n-dimension identity matrix, and where
ui(t) = 0 whenever NIDS module i behave normally. The
observer requires inputs from the state vector x(t), i.e. the
values xj(t) ∈ x(t) where j ∈ Ni. These values are stored
in a vector yi. The consensus loop of each NIDS module i
is now defined as follow:
x(t+ 1) = Wx(t) + Inu(t)
yi(t) = Cix(t)
(7)
where Ci is a (degi + 1) × N matrix in which entry
Ci[k, l] = 1 if l ∈ Ni, otherwise Ci[k, l] = 0. The vec-
tor yi(t) has (degi + 1) entries, each entry j of yi(t) stores
the state xj(t) at time t of modules j ∈ Ni.
Equation (7) represents the consensus loop of a given
module i as if it could access all the consensus values at
iteration t, though in fact module i can only access xi(t)
and xj(t) for j ∈ Ni. The other entries of vector x(t) are
not needed during the computation performed by the re-
currence relation of node i, so it is not incorrect to model
these entries as if they were available. Note that each
NIDS module i knows the consensus matrix W , the ma-
trix Ci, xj(t) ∈ x(t) for j ∈ Ni, and the identity ma-
trix In. However, the set of non-zero ui is unknown to the
non-malicious modules. To detect a malicious neighbor of
module i, the consensus loop of "each module" computes
the following matrix operations [27]:
z(t+ 1) = (W +GCi)z(t)−Gyi(t)
xo(t) = Lz(t) +Kyi(l)
(8)
where z(t) is the state of the observer and xo(t) is the esti-
mation by the observer of module i of the consensus state
x(t). The matrices to compute z(t + 1) and xo(t) are de-
fined as follow: G = −WNi , K = CTi , L = In − KCi,
where WNi are the columns of W with indexes in Ni. The
system in (8) has roots in the observability theory of con-
trol theory, a detailed analysis of this system is beyond the
scope of this paper, we refer to [45] for an historical de-
velopment and analysis of observer-based fault detection
systems. The analysis of (8) can be simplified as the con-
sensus system (7) satisfies some conditions [26]. It can be
show that as t → ∞, xo(t) → x(t), consequently the esti-
mation error e(t) = xo(t) − x(t) converges to 0. We are
also given that equation (8) under the consensus system in
(7) simplifies to:
xoj(t) =
{
xj(t) if j = i or j ∈ Ni
zj(t) otherwise
(9)
and that the state of the observer z(t+ 1) can be expressed
in terms of the consensus matrix [27]:
z(t+ 1) = Wxo(t). (10)
The iteration error ε(t):
ε(t) = |xo(t+ 1)−Wxo(t)|
200 Informatica 41 (2017) 193–207 M. Toulouse et al.
can then be used as residual vector. From (9) and (10),
εj(t) = 0 for j 6= i and j 6∈ Ni. If εj(t) 6= 0, either
xoj(t) 6= xj(t) (estimation error is greater than 0), or uj 6=
0. Since the estimation error dissipates as t→∞, we have
(xo(t+ 1)−Wxo(t))→ Inu(t) as t→∞. If uj 6= 0 for
some j ∈ {1, . . . , n} then (xoj(t+ 1)−Wxoj(t))→ uj(t),
the corresponding module j is detected as compromised.
Together with the consensus loop in (7), the observer
defined in (8) provides an algorithm where each NIDS
module can detect whether one of its neighbor sends fal-
sified consensus data. Each module i build a consensus
system and an observer as described in equations (7) and
(8). At each consensus iteration, each module i computes
ε(t) = |xo(t + 1) − Wxo(t)|. If εj(t) 6= 0 then mod-
ule j ∈ Ni is compromised. Module i then removes log-
ically module j from its neighborhood by modifying it’s
weight matrix according to the description in Section 2.3,
thus stopping the injection of an external input by module
j into the network intrusion detection system.
4 Empirical analysis
The above two Byzantine attacks detection techniques help
the NIDS coping with adversarial environments by detect-
ing compromised modules. In this section we analyze and
compare the behavior of each technique. For example,
these techniques have a computational cost, we measure
the overhead for running each technique. We measure how
fast attacks are detected and model the accuracy of the de-
cisions made by the NIDS under each detection method.
Last, as the removal of a compromised module is obtained
by changing the weight matrix and the network topology,
we measure whether these changes have any impact on the
convergence speed of the consensus phases, i.e. whether
the system returns to its full functioning capabilities after
removing compromised modules.
To execute this empirical analysis, the two Byzantine at-
tack identification techniques described in Section (3) have
been coded as part of the consensus phase of the NIDS sim-
ulations described in [1]. We have run simulations for the
following NIDS network topologies: rings with 9 and 25
nodes (NIDS modules), 2-dimensional torus with 9 and 25
nodes, Petersen graph (10 nodes 15 edges) and several ran-
dom graphs having the same number of vertices and edges
as in the Petersen graph. A simulation consists to execute
1000 iterations of one of the above NIDS network topolo-
gies. In one iteration, each NIDS module of the network
topology reads the local network traffic from an entry of
the NSL-KDD data set, performs an Bayesian analysis of
the local traffic, then executes its consensus loop until con-
vergence. Note, we have filtered attacks in the NSL-KDD
data set to retain only denial of service attacks.
The consensus phase is implemented as follow. The
Bayesian analysis of the local network traffic by module
i returns two values: pAi the probability that the observed
traffic at module i is intrusive; pNi the probability the ob-
served traffic at module i is normal. These values are
used to initialize the consensus loop of the corresponding
module i: xAi (0) = log(pAi) and x
N
i (0) = log(pNi),
for i = 1..n. During the consensus phase, for simula-
tions involving the outlier detection technique, each NIDS
module i computes the following recurrence relations until
|xAi (t+ 1)− xAi (t)| <  and |xNi (t+ 1)− xNi (t)| < :
xAi (t+ 1) = Wiix
A
i (t) +
∑
j∈Ni
Wijx
A
j (t) + ui(t) (11)
xNi (t+ 1) = Wiix
N
i (t) +
∑
j∈Ni
Wijx
N
j (t) + ui(t). (12)
Similarly, in simulations involving the fault detection tech-
nique, each NIDS module i computes the solutions for the
following iterative systems until each recurrence of the sys-
tems has converged:
xA(t+ 1) = WxA(t) + IuA
yAi (t) = Cix
A(t)
(13)
xN (t+ 1) = WxN (t) + IuN
yNi (t) = Cix
N (t).
(14)
The matrix operations described in Equation (8) are also
computed at each iteration of the consensus loop of module
i in simulations involving the fault detection technique.
Once a consensus phase is completed, each NIDS mod-
ule i decides whether to raise an alert or not based on
its consensus approximation ratio x
A
i (t)
xNi (t)
of the actual ra-
tio
∑N
i=1 log(pAi )
n /
∑n
i=1 log(pNi )
n and some predefined alert
value ratio. As each module converges asymptotically to
the same actual ratio
∑N
i=1 log(pAi )
n /
∑n
i=1 log(pNi )
n , all mod-
ules reach a same decision, which constitutes a form of co-
ordinated response to perceived anomalies in the network
traffic.
The consensus loop disruption of the attack model 2(b)
in Section 3.1 is implemented as follow. Anomaly-based
intrusion detection systems tend to have high false positive
rates. We simulate attacks that aim to further increase the
number of false positives. Attacks inject positive values in
the consensus loop component (11) or (13). At each iter-
ation of a simulation, a to be compromised NIDS module
j is selected randomly, uAj is then assigned with a posi-
tive value. The magnitude of uAj has to be large enough
to falsify the decision at the end of the consensus phase
(i.e. raise an alert when traffic is normal), "if" the con-
sensus loop disruption attack is not detected. For exam-
ple, uAj = 0.0005 is to small, it does not have an impact
on the decision. However, a value such as uAj = 0.5 can
cause each module of the system to converge to an approxi-
mation x
A
i (t)
xNi (t)
>
∑N
i=1 log(pAi )
n /
∑n
i=1 log(pNi )
n , thus possibly
leading the NIDS to raise an alert when in fact there is no
attack.
The value uAj = 0.5 is also suitable to obtain
meaningful test results for the following reason. The
Defense Strategies against Byzantine Attacks . . . Informatica 41 (2017) 193–207 201
values pAi and pNi returned by the Bayesian anal-
ysis of a module i are the product of likelihoods∏m
j=1 P (oj |h), as the number of features is large, the
product of likelihoods are very small. During the con-
sensus phase, neighbor NIDS modules exchange log-
likelihoods, which are in the range between -20 and
-55. So uAj = 0.5 is a relativity small external input dur-
ing the consensus phase. However, it is large enough so
that our two detection techniques can always detect this
attack, but failing to detect it soon enough can lead the
consensus phase to converge to values quite different from
1
n
∑n
i=1 xi(0).
In the following sections, we first evaluate the computa-
tional cost of running each of the two detection techniques.
Subsidiary, we also report the number of consensus itera-
tions needed to detect a compromised module. Next we
analyze the efficiency of the detection techniques to pre-
vent the occurrence of false positives at the conclusion of
a consensus phase. Finally we analyze the impact of our
technique to remove a compromised NIDS module on the
convergence speed of consensus phases.
4.1 Computational costs
Table 1 reports the computational cost of running each de-
tection technique. All the simulations are executed while
no attack take place, these tests measure uniquely the over-
head for running the code implementing the two detection
techniques. The column "Cost" reports the time in millisec-
onds for running the NIDS network simulation for 1000 it-
erations. In Table 1, rows "no detection" give the cost of
running a NIDS simulation without the execution of any
detection code. Rows "outlier" and "fault" give the cost of
running NIDS modules while also executing respectively
the code for the outlier method and the fault method. The
higher costs of the detection techniques compared to "no
detection" for the same network size and topology reflects
the cost for protecting the consensus-based NIDS with the
corresponding detection techniques. Table 1 shows that the
computational overhead for outlier is clearly less than for
the fault detection method. These results were expected,
each consensus loop iteration of the fault detection method
runs several matrix operations compared to simple scalar
operations for the outlier method.
4.2 Detection speed
Figures 3 to 8 detail with which rapidity, detection speed,
the two detection techniques identify compromised mod-
ules. Each figure corresponds to a different network topol-
ogy. The values on the x axis are the number of consen-
sus iterations needed before the compromised module is
identified. The y axis displays the percentage of the 1000
consensus phases that needed a given number of consen-
sus iterations to detect a compromised module. These fig-
ures clearly show that the fault detection approach needs
fewer iterations to detect Byzantine attacks. Combining the
Table 1: Consensus-based NIDS computational simulation
costs in milliseconds.
Topology Size Detection Cost
Ring
9
no detection 0.050
outlier 0.276
fault 0.921
25
no detection 0.101
outlier 1.131
fault 3.286
Torus
9
no detection 0.027
outlier 0.121
fault 1.327
25
no detection 0.043
outlier 0.567
fault 6.055
Petersen 10
no detection 0.005
outlier 0.135
fault 0.597
Random 10
no detection 0.013
outlier 0.290
fault 1.268
computational cost in Table 1, we observe that the outlier
method has a more favorable computational overhead but
requires more iterations to detect compromised modules.
Figure 3: Detection speed of ring topology 9 nodes.
Figure 4: Detection speed of ring topology 25 nodes.
202 Informatica 41 (2017) 193–207 M. Toulouse et al.
Figure 5: Detection speed of torus topology 9 nodes.
Figure 6: Detection speed of torus topology 25 nodes.
Figure 7: Detection speed of Petersen graph.
4.3 Intrusion detection accuracy
Disruption of the consensus loops by injecting external in-
puts has an impact on the accuracy of the decision made
by the NIDS about the state of the network traffic. Table
2 measures how effective the two detection techniques are
at maintaining the accuracy of the consensus-based NIDS.
The "no attack" rows report the accuracy of the NIDS in
a non-adversarial environment. The "no detection" rows
report the accuracy of the NIDS when attacks take place
Figure 8: Detection speed of Random graphs.
while the NIDS is not protected. The "outlier" and "fault"
rows report respectively the accuracy of NIDS protected by
the outlier and fault detection methods.
The results of Table 2 are obtained without changing the
weight matrix and network topology once a compromised
NIDS module is identified (static consensus). Let l be the
iteration of the consensus phase where module i identifies
a neighbor module j as compromised. For t > l, module i
applies the following update rule:
xAi (t+ 1) = Wiix
A
i (t) +
∑
(k∈Ni∧k 6=j)
Wikx
A
k (t)
+Wijx
A
j (t)− 0.5.
This update is possible since uAj = 0.5 is known in the con-
text of our simulations, though it is not know which module
is compromised in this way. Module i removes 0.5 from the
value sent by the compromised module j, therefore mod-
ule i update its state with the true consensus values of its
neighbors.
Table 2 shows the outlier detection method less ac-
curate compared to the fault-detection method, this even
Byzantine attacks are always detected and the compro-
mised NIDS module neutralized. These results are ex-
plained by the number of consensus loop iterations needed
to detect attackers. Figures 3 to 8 show the outlier method
needing more iterations to detect compromised modules.
The more iterations it takes to detect a compromised mod-
ule, the more data injections take place prior to detection of
the compromised module and the more time injected values
have to diffuse across the NIDS modules, which cause the
NIDS decision to till the wrong way more frequently in the
case of the outlier method.
4.4 Convergence speed
This section analyzes the impact of removing a module
while the NIDS computes consensus states. According to
section 2.3, the technique we propose to isolate a compro-
mised module satisfies the average consensus convergence
conditions. Rows of the weight matrices sum up to 1. Each
Defense Strategies against Byzantine Attacks . . . Informatica 41 (2017) 193–207 203
Table 2: Accuracy of the NIDS.
Topology Size Detection TP TN FP FN
Ring
9
no attack 466 520 14 0
no detection 521 0 479 0
outlier 522 404 74 0
fault 456 525 4 15
25
no attack 527 473 0 0
no detection 475 0 525 0
outlier 497 503 58 0
fault 506 489 0 5
Torus
9
no attack 493 491 16 0
no detection 499 0 501 0
outlier 495 438 67 0
fault 478 511 0 11
25
no attack 492 507 1 0
no detection 497 0 503 0
outlier 491 456 53 0
fault 518 450 32 0
Petersen 10
no attack 501 487 12 0
no detection 481 0 519 0
outlier 477 458 65 0
fault 481 516 0 3
Random 10
no attack 451 533 16 0
no detection 485 0 515 0
outlier 503 432 65 0
fault 526 464 0 10
NIDS network topology tested in this empirical analysis
section is such that it is still connected even after one mod-
ule is removed. However, as our approach changes the
weight matrix and the NIDS network topology, two factors
that could impact the convergence speed, we still need to
analyze the consensus phase convergence speed when mod-
ules are removed. In this section we compare the consen-
sus phase convergence speed of the static consensus imple-
mentation of Section 4.3 running the Metropolis-Hasting
weight matrix with the convergence speed when the con-
sensus phase is implemented with the dynamic consensus
procedure introduced in Section 2.3.
Figures 9 to 13 compare the convergence speed of static
versus dynamic consensus for the outlier detection method
while figures 14 to 18 compare the convergence speed
of static versus dynamic consensus for the fault detec-
tion method. As we can see from figures 14 to 18, there
is no significant differences in the convergence speed of
static and dynamic consensus for the fault-based detection
method, except for the Petersen graph. With the outlier de-
tection method, as shown in figures 9 to 13, dynamic con-
sensus converges faster for some of the network topologies.
It is not entirely clear why the convergence speed is bet-
ter with dynamic consensus and some specific outlier simu-
lations. Nonetheless, figures 9 to 18 show no significant de-
crease in the convergence speed of consensus phases once
a module has been isolated. As accuracy is not impacted
by the removal of a module, this is enough to conclude that
the intrusion detection system returns to a fully functioning
state.
Figure 9: Convergence: dynamic topology, outlier detec-
tion, ring topology 9 nodes.
Figure 10: Convergence: dynamic topology, outlier detec-
tion, ring topology 25 nodes.
Figure 11: Convergence: dynamic topology, outlier detec-
tion, torus topology 9 nodes.
5 Conclusion
Local data exchanges of consensus-based distributed ap-
plications can be hacked by Byzantine attackers falsifying
computed consensus information. Several solutions have
been proposed in the literature that address Byzantine at-
tacks on consensus algorithms. We have adapted two of
these solutions, one from model-based fault detection and
one from outlier detection to protect a consensus-based net-
204 Informatica 41 (2017) 193–207 M. Toulouse et al.
Figure 12: Convergence: dynamic topology, outlier detec-
tion, torus topology 25 nodes.
Figure 13: Convergence: dynamic topology, outlier detec-
tion, Petersen graph.
Figure 14: Convergence: dynamic topology, fault detec-
tion, ring topology 9 nodes.
work intrusion detection system. We have also applied re-
sults from dynamic consensus theory to derive a simple ap-
proach to isolate compromised modules from the network
while continuing to satisfy the mathematical assumptions
requested for convergence of the consensus phase.
Our results show the two methods we propose can be
used to detect consensus loop disruptions and prevent falsi-
fications of NIDS network traffic assessments. Though pre-
liminary, our results also show significant computational
Figure 15: Convergence: dynamic topology, fault detec-
tion, ring topology 25 nodes.
Figure 16: Convergence: dynamic topology, fault detec-
tion, torus topology 9 nodes.
Figure 17: Convergence: dynamic topology, fault detec-
tion, torus topology 25 nodes.
costs of these approaches either in terms of the number of
iterations to detect attacks (outlier detection) or in terms of
the computational cost of each iteration (model-based de-
tection). This might raise issues for deploying consensus-
based NIDS in suitable environments such as wireless ad
hoc networks.
Future work will address both protecting the consensus-
based NIDS against disruptive attacks as well as getting the
Defense Strategies against Byzantine Attacks . . . Informatica 41 (2017) 193–207 205
Figure 18: Convergence: dynamic topology, fault detec-
tion, Petersen graph.
system closer to deployment in wireless network environ-
ments. We will work on reducing computational cost, by
speeding up for example the consensus phase, i.e. reduc-
ing the number of iterations needed for modules to come
with agreed decisions. This will impact Byzantine fault
detection which will need to be done at earlier stages and
at a smaller computational cost. Byzantine fault detection
will be broaden to other attack models, involving more than
one compromised module, and possibly colluding attack-
ers. Addressing multiple attackers seems achievable with-
out too much research efforts using outlier or reputation-
based methods. On the other hand, current model-based
approaches in control theory seem too computationally de-
manding and will need more research before they can be
used in a deployed system. Finally, we intend to broaden
the cooperation among NIDS modules. This depends on
consensus computing more functions of the initial values
provided by the analysis phase. There is a wide range of
functions that can be computed using distributed iterative
methods similar to average consensus. This will bring more
versatility in detecting network intrusions and allow for a
wide range coordinated responses to address detected ma-
licious network activities.
References
[1] M. Toulouse, B. Q. Minh, and P. Curtis, “A
consensus based network intrusion detection system.”
in IT Convergence and Security (ICITCS), 2015 5th
International Conference on. IEEE, 2015, pp. 1–6.
[Online]. Available: http://dblp.uni-trier.de/db/conf/
icitcs/icitcs2015.html#ToulouseMC15
[2] A. Patel, M. Taghavi, K. Bakhtiyari, and J. Ce-
lestino JúNior, “Review: An intrusion detection
and prevention system in cloud computing: A
systematic review,” J. Netw. Comput. Appl., vol. 36,
no. 1, pp. 25–41, Jan. 2013. [Online]. Available:
http://dx.doi.org/10.1016/j.jnca.2012.08.007
[3] C. V. Zhou, C. Leckie, and S. Karunasekera, “A
survey of coordinated attacks and collaborative in-
trusion detection,” Computers & Security, vol. 29,
no. 1, pp. 124 – 140, 2010. [Online]. Avail-
able: http://www.sciencedirect.com/science/article/
pii/S016740480900073X
[4] E. Vasilomanolakis, S. Karuppayah, M. Mühlhäuser,
and M. Fischer, “Taxonomy and survey of collab-
orative intrusion detection,” ACM Comput. Surv.,
vol. 47, no. 4, pp. 55:1–55:33, May 2015. [Online].
Available: http://doi.acm.org/10.1145/2716260
[5] S. R. Snapp, J. Brentano, G. V. Dias, T. L. Goan,
L. T. Heberlein, C. L. Ho, K. N. Levitt, B. Mukher-
jee, S. E. Smaha, T. Grance et al., “Dids (distributed
intrusion detection system)-motivation, architecture,
and an early prototype,” in Proceedings of the 14th
national computer security conference, vol. 1. Cite-
seer, 1991, pp. 167–176.
[6] T. Bass, “Multisensor data fusion for next generation
distributed intrusion detection systems,” in In Pro-
ceedings of the IRIS National Symposium on Sensor
and Data Fusion, 1999, pp. 24–27.
[7] R. Janakiraman, M. Waldvogel, and Q. Zhang, “In-
dra: A peer-to-peer approach to network intrusion
detection and prevention,” in Enabling Technologies:
Infrastructure for Collaborative Enterprises, 2003.
WET ICE 2003. Proceedings. Twelfth IEEE Interna-
tional Workshops on. IEEE, 2003, pp. 226–231.
[8] C. V. Zhou, S. Karunasekera, and C. Leckie, “A peer-
to-peer collaborative intrusion detection system,” in
2005 13th IEEE International Conference on Net-
works Jointly held with the 2005 IEEE 7th Malaysia
International Conf on Communic, vol. 1, Nov 2005,
pp. 118–123.
[9] M. Locasto, J. J. Parekh, A. D. Keromytis, and S. J.
Stolfo, “Towards collaborative security and p2p in-
trusion detection,” in In Proceedings of the IEEE In-
formation Assurance Workshop (IAW, 2005, pp. 333–
339.
[10] M. Marchetti, M. Messori, and M. Colajanni,
Peer-to-Peer Architecture for Collaborative Intrusion
and Malware Detection on a Large Scale. Berlin,
Heidelberg: Springer Berlin Heidelberg, 2009, pp.
475–490. [Online]. Available: http://dx.doi.org/10.
1007/978-3-642-04474-8_37
[11] N. A. Lynch, Distributed Algorithms. San Francisco,
CA, USA: Morgan Kaufmann Publishers Inc., 1996.
[12] T. Vicsek, A. Czirók, E. Ben-Jacob, I. Cohen, and
O. Shochet, “Novel type of phase transition in a sys-
tem of self-driven particles,” Phys. Rev. Lett., vol. 75,
pp. 1226–1229, Aug 1995. [Online]. Available:
http://link.aps.org/doi/10.1103/PhysRevLett.75.1226
206 Informatica 41 (2017) 193–207 M. Toulouse et al.
[13] R. Saber and R. Murray, “Consensus protocols for
networks of dynamic agents,” in American Control
Conference, 2003. Proceedings of the 2003, vol. 2,
June 2003, pp. 951–956.
[14] A. Fagiolini, M. Pellinacci, M. Valenti, G. Dini, and
A. Bicchi, “Consensus-based distributed intrusion de-
tection for multi-robot systems,” in Proc. IEEE Int.
Conf. on Robotics and Automation, 2008, pp. 120 –
127.
[15] J. Tsitsiklis, D. Bertsekas, and M. Athans, “Dis-
tributed asynchronous deterministic and stochastic
gradient optimization algorithms,” Automatic Con-
trol, IEEE Transactions on, vol. 31, no. 9, pp. 803–
812, Sep. 1986.
[16] S. Li, G. Oikonomou, T. Tryfonas, T. Chen,
and L. Xu, “A distributed consensus algorithm
for decision-making in service-oriented internet of
things,” Transactions on Industrial Informatics,
vol. 10, no. 2, pp. 1461–1468, 2014. [Online]. Avail-
able: http://ieeexplore.ieee.org/xpl/articleDetails.jsp?
arnumber=6740862
[17] A. Narayanan, J. Bonneau, E. Felten, A. Miller, and
S. Goldfeder, Bitcoin and Cryptocurrency Technolo-
gies: A Comprehensive Introduction. Princeton, NJ,
USA: Princeton University Press, 2016.
[18] I. F. Akyildiz, B. F. Lo, and R. Balakrishnan,
“Cooperative spectrum sensing in cognitive radio
networks: A survey,” Phys. Commun., vol. 4,
no. 1, pp. 40–62, Mar. 2011. [Online]. Available:
http://dx.doi.org/10.1016/j.phycom.2010.12.003
[19] G. Xiong and S. Kishore, “Consensus-based dis-
tributed detection algorithm in wireless ad hoc net-
works,” in Signal Processing and Communication
Systems, 2009. ICSPCS 2009. 3rd International Con-
ference on, Sept 2009, pp. 1–6.
[20] K. Avrachenkov, M. E. Chamie, and G. Neglia, “A
local average consensus algorithm for wireless sensor
networks,” in 2011 International Conference on Dis-
tributed Computing in Sensor Systems and Workshops
(DCOSS), June 2011, pp. 1–6.
[21] M. Pease, R. Shostak, and L. Lamport, “Reaching
agreement in the presence of faults,” J. ACM, vol. 27,
no. 2, pp. 228–234, Apr. 1980. [Online]. Available:
http://doi.acm.org/10.1145/322186.322188
[22] L. Lamport, R. Shostak, and M. Pease, “The
byzantine generals problem,” ACM Trans. Program.
Lang. Syst., vol. 4, no. 3, pp. 382–401, Jul.
1982. [Online]. Available: http://doi.acm.org/10.
1145/357172.357176
[23] S. Liu, H. Zhu, S. Li, X. Li, C. Chen, and
X. Guan, “An adaptive deviation-tolerant secure
scheme for distributed cooperative spectrum sensing,”
in 2012 IEEE Global Communications Conference,
GLOBECOM 2012, Anaheim, CA, USA, December
3-7, 2012, 2012, pp. 603–608. [Online]. Available:
http://dx.doi.org/10.1109/GLOCOM.2012.6503179
[24] Q. Yan, M. Li, T. Jiang, W. Lou, and Y. T. Hou, “Vul-
nerability and protection for distributed consensus-
based spectrum sensing in cognitive radio networks,”
in INFOCOM, 2012 Proceedings IEEE. IEEE, 2012,
pp. 900–908.
[25] W. Zeng and M.-Y. Chow, “A reputation-based secure
distributed control methodology in D-NCS.” IEEE
Trans. Industrial Electronics, vol. 61, no. 11, pp.
6294–6303, 2014. [Online]. Available: http://dblp.
uni-trier.de/db/journals/tie/tie61.html#ZengC14
[26] F. Pasqualetti, A. Bicchi, and F. Bullo, “Consensus
computation in unreliable networks: A system the-
oretic approach,” IEEE Transactions on Automatic
Control, vol. 57, no. 1, pp. 90 – 104, Jan. 2012.
[27] ——, “Distributed intrusion detection for secure con-
sensus computations,” in Decision and Control, 2007
46th IEEE Conference on, Dec 2007, pp. 5594–5599.
[28] S. Sundaram and C. N. Hadjicostis, “Distributed
function calculation via linear iterative strategies in
the presence of malicious agents,” IEEE Transactions
on Automatic Control, vol. 56, no. 7, pp. 1495–1508,
July 2011.
[29] L. Xiao, S. Boyd, and S.-J. Kim, “Distributed av-
erage consensus with least-mean-square deviation,”
Journal of Parallel and Distributed Computing,
vol. 67, no. 1, pp. 33 – 46, 2007. [Online]. Avail-
able: http://www.sciencedirect.com/science/article/
pii/S0743731506001808
[30] M. Zhu and S. Martínez, “Discrete-time dy-
namic average consensus,” Automatica, vol. 46,
no. 2, pp. 322 – 329, 2010. [Online]. Avail-
able: http://www.sciencedirect.com/science/article/
pii/S0005109809004828
[31] R. Olfati-Saber and R. M. Murray, “Consensus
problems in networks of agents with switching
topology and time-delays,” Automatic Control, IEEE
Transactions on, vol. 49, no. 9, pp. 1520–1533, Sep.
2004. [Online]. Available: http://dx.doi.org/10.1109/
tac.2004.834113
[32] L. Xiao, S. Boyd, and S. Lall, “Distributed average
consensus with time-varying metropolis weights,”
2006, unpublished. [Online]. Available: http://web.
stanford.edu/~boyd/papers/pdf/avg_metropolis.pdf
[33] L. Xiao, S. Boyd, and S. Lall, “A space-time diffusion
scheme for peer-to-peer least-squares estimation,” in
Proceedings of the Fifth International Conference
Defense Strategies against Byzantine Attacks . . . Informatica 41 (2017) 193–207 207
on Information Processing in Sensor Networks,
IPSN 2006, Nashville, Tennessee, USA, April 19-
21, 2006, 2006, pp. 168–176. [Online]. Available:
http://doi.acm.org/10.1145/1127777.1127806
[34] L. Xiao, S. Boyd, and S. Lall, “A scheme
for robust distributed sensor fusion based on
average consensus,” in Proceedings of the 4th
International Symposium on Information Processing
in Sensor Networks, ser. IPSN ’05. Piscataway,
NJ, USA: IEEE Press, 2005. [Online]. Available:
http://dl.acm.org/citation.cfm?id=1147685.1147698
[35] M. Tavallaee, E. Bagheri, W. Lu, and A. A.
Ghorbani, “A detailed analysis of the kdd cup
99 data set,” in Proceedings of the Second
IEEE International Conference on Computational
Intelligence for Security and Defense Applica-
tions, ser. CISDA’09. Piscataway, NJ, USA:
IEEE Press, 2009, pp. 53–58. [Online]. Available:
http://dl.acm.org/citation.cfm?id=1736481.1736489
[36] L. Xiao, S. Boyd, and S.-J. Kim, “Distributed
average consensus with least-mean-square deviation,”
J. Parallel Distrib. Comput., vol. 67, no. 1,
pp. 33–46, Jan. 2007. [Online]. Available: http:
//dx.doi.org/10.1016/j.jpdc.2006.08.010
[37] A. Olshevsky and J. N. Tsitsiklis, “Convergence
speed in distributed consensus and averaging,”
SIAM J. Control Optim., vol. 48, no. 1, pp.
33–55, Feb. 2009. [Online]. Available: http:
//dx.doi.org/10.1137/060678324
[38] L. Xiao and S. Boyd, “Fast linear iterations for
distributed averaging,” Systems and Control Letters,
vol. 53, pp. 65–78, 2003.
[39] S. Kar and J. M. F. Moura, “Topology for global av-
erage consensus,” October 2006, pp. 276–280.
[40] B. Kailkhura, S. Brahma, and P. K. Varshney, “Data
falsification attacks on consensus-based detection
systems,” IEEE Transactions on Signal and Informa-
tion Processing over Networks, vol. 3, no. 1, pp. 145–
158, March 2017.
[41] W. Ben-Ameur, P. Bianchi, and J. Jakubowicz,
“Robust average consensus using total variation
gossip algorithm,” in 6th International ICST Con-
ference on Performance Evaluation Methodologies
and Tools, Cargese, Corsica, France, October 9-
12, 2012, 2012, pp. 99–106. [Online]. Available:
http://dx.doi.org/10.4108/valuetools.2012.250316
[42] S. Mi, H. Han, C. Chen, J. Yan, and X. Guan, “A
secure scheme for distributed consensus estimation
against data falsification in heterogeneous wireless
sensor networks,” Sensors, vol. 16, no. 2, p. 252,
2016. [Online]. Available: http://www.mdpi.com/
1424-8220/16/2/252
[43] V. P. Illiano and E. C. Lupu, “Detecting malicious
data injections in wireless sensor networks: A
survey,” ACM Comput. Surv., vol. 48, no. 2,
pp. 24:1–24:33, Oct. 2015. [Online]. Available:
http://doi.acm.org/10.1145/2818184
[44] R. Isermann, “Model-based fault-detection and diag-
nosis - status and applications,” Annual Reviews in
Control, vol. 29, pp. 71–85, 2005.
[45] J. Chen, J. R. Patton, and H.-Y. Zhang, “Design of un-
known input observers and robust fault detection fil-
ters,” International Journal of Control, vol. 63, no. 1,
pp. 85–105, 1996.
[46] Z. A. Biron, P. Pisu, and B. HomChaudhuri,
“Observer design based cyber security for cyber
physical systems,” in Proceedings of the 10th
Annual Cyber and Information Security Research
Conference, ser. CISR ’15. New York, NY,
USA: ACM, 2015, pp. 6:1–6:6. [Online]. Available:
http://doi.acm.org/10.1145/2746266.2746272
[47] D. Ding, Z. Wang, D. W. C. Ho, and G. Wei,
“Observer-based event-triggering consensus control
for multiagent systems with lossy sensors and cyber-
attacks,” IEEE Transactions on Cybernetics, vol. PP,
no. 99, pp. 1–12, 2016.
[48] F. Pasqualetti, R. Carli, A. Bicchi, and F. Bullo, “Iden-
tifying cyber attacks via local model information,” in
International Conference on Decision and Control -
CDC 2010, Atlanta, USA, December 2010, pp. 5961
– 5966.
[49] A. Teixeira, H. Sandberg, and K. H. Johansson, “Net-
worked control systems under cyber attacks with ap-
plications to power networks,” in Proceedings of the
2010 American Control Conference, June 2010, pp.
3690–3696.
[50] L. Negash, S. Kim, and H. Choi, “Distributed
unknown-input-observers for cyber attack detection
and isolation in formation flying uavs,” CoRR,
vol. abs/1701.06325, 2017. [Online]. Available:
http://arxiv.org/abs/1701.06325