一种基于精确共识的网络入侵检测系统

摘要

在最近的一项研究中，Toulouse等人[1]提出了一种基于平均共识算法的完全分布式网络入侵检测系统（NIDS）。在该初步研究中，NIDS的各个模块通过反复将其状态与其邻居的状态进行局部平均，从而渐近收敛到相同的值，该值随后被用作衡量整个网络所监控流量某些相关状态的指标。在本文中，我们利用局部平均实现了一种基于共识的NIDS的有限收敛过程，如[1]所述。我们将此实现称为exact consensus，因为局部平均能够在有限步数内精确计算出初始NIDS状态的某个函数。此外，与仅能计算平均和函数的渐近共识不同，这种新的分布式协议几乎可以计算初始NIDS状态的任意函数。我们进行了测试，将渐近共识与这种新的精确共识协议进行比较。特别是，我们在入侵检测系统所做出决策具有相同预定义精度水平的前提下，比较了两种方法的收敛速度。

关键词： 网络安全 · Intrusion检测 · Distributed平均共识 · Control theory

1 引言

网络入侵检测系统通过分析网络流量来监控计算机网络基础设施，以识别恶意行为。通常，检测过程分为两个阶段：观察阶段，即收集网络流量信息；以及分析阶段，即对观测到的流量进行分析，并将其分类为良性或恶意网络流量。流量观测通过传感器实现，这些传感器收集网络流量特定特征的信息。由于当今的计算机网络规模较大，且由多个异构子网络组成，因此流量观测通常需要在不同战略位置部署传感器，进行分布式操作。

图1说明了这种情况，展示了分布在受监控网络中的传感器，其中每个传感器负责观测一个子网络的本地流量。

在完全分布式NIDS中，传感器不仅限于观察子网络中的本地流量，它们还会对本地子网络的流量进行分析。在这种情况下，传感器是具备完整感知和分析能力的设备，我们将其称为NIDS模块。在完全分布式NIDS的背景下，图1（节点1、2、3和4）中的传感器代表模块，成对传感器之间的链路（{1, 2}、{2, 3}、{3, 4}和{4, 1}）与传感器共同构成了NIDS网络。

在每个传感器层面进行分析时，NIDS模块可以对本地流量进行分类，并在需要时采取补救措施。然而，在某些情况下，一定程度的本地分析结果聚合有助于应对来自多个并发源的攻击（例如分布式拒绝服务（DDoS）），制定覆盖整个网络的协调响应，或简单地基于其他子网络的信息提高每个本地NIDS模块的检测准确率。无论执行何种完全分布式的全局分析，为了实施一致的补救措施，参与分析的模块必须得出相同的结论，即必须达成共识。

最近，在Toulouse等人[1]的研究中，一种线性迭代算法，特别是平均共识算法，被用于以完全分布式的方式计算某些全网状态值的一致性。在该初步工作中，NIDS的模块反复将其状态与相邻NIDS模块的状态进行平均。所有模块渐近收敛到同一个值，该值被用作被监控网络系统某些相关全网状态的度量。然而，[1]中提出的策略存在一些缺点。其一是收敛是渐近的，共识阶段可能需要相当大的迭代次数，模块才能达到一个可行近似，即允许以高准确性对网络状态做出决策的近似值。第二，该方法仅能计算初始值的平均和。

本文借鉴[2,3]，将共识理论与网络可观测性理论的一些核心概念相结合[4]。可观测性理论的主要思想是，如果一个系统是可观测的，则可以根据系统的输出推算其内部状态。每个模块计算的局部平均被建模为系统输出。考虑图1中的NIDS网络，并假设xi(0)是与节点i相关联的某个初始值。令f(xi(t+1)) = 1/3(xi−1(t) + xi(t) + xi+1(t))（使用适当的模函数处理边界条件）为节点i的局部平均函数。则xi(1) = f(xi(0))且xi(2) = f(xi(1)) = f(f(xi(0)))。在图1中，f(x1(2)) = f(x4(1) + x1(1) + x2(1))，其中x4(1) = f(x3(0) + x4(0) + x1(0))，x1(1) = f(x4(0) + x1(0) + x2(0))，以及x2(1) = f(x1(0) + x2(0) + x3(0))。经过仅两次局部平均迭代后，节点1已看到网络中所有其他节点的初始值（尽管这些值已被局部平均变换），因此它可以计算NIDS网络初始值的任意函数f。

在我们的精确共识算法中，在第t次迭代时，每个NIDS模块i通过NIDS系统的模块i将其自身状态xi(t)以及NIDS网络中邻居的状态xj(t)累积为“可观测输出”。经过有限次迭代后，模块i已累积足够的信息，以计算依赖于NIDS网络中所有模块初始状态的任意函数f。只需找到一个函数Γi，即可利用模块i观测并累积的值来计算f。将可观测性应用于[1]中的系统，可减少收敛到共识所需的迭代次数，实现精确收敛（而非渐近值收敛），并允许计算几乎任意基于本地网络流量分析所产生的初始值函数的共识。

本文提出的工作与最近关于应用可观测性理论来检测数据伪造攻击同时计算平均共识的研究密切相关[5–7]。然而，我们的重点是将这些数学发展应用于精确共识过程的设计，如[2,3]中所述。我们的具体贡献是提出一种基于精确共识的网络入侵检测系统。接下来，我们首先描述[1]中提出的系统。然后，我们描述所提出的基于精确共识的分布式函数计算方法。在第4节中，我们将该新方法与[1]中提出的系统进行若干方面的比较。最后，在第5节中提供总结和未来研究方向。

2 平均共识和基于共识的网络入侵检测系统

共识算法在计算机科学及其他领域有着悠久的历史，曾被用于支持网络上的分布式计算。共识算法通常用于计算机网络任务，其中对同一现象进行多次读取，然后融合以提供聚合的观测结果。传感器网络提供了许多应用，[8,9]分布式系统中的任务协调[10]，物理学中的应用[11]，过程控制[12]，机器人[13]，运筹学[14]，物联网边缘节点的服务[15]，更不用说它在有争议的比特币货币中的应用了[16]。平均共识是指一种特定形式的共识，其中协作节点计算其初始值的平均和。本节首先对平均共识进行正式介绍，然后简要描述[1]中的基于共识的网络入侵检测系统。

2.1 平均共识

平均共识算法计算平均和
$$
\frac{1}{n}\sum_{i=1}^{n} x_i
$$
某些初始值x₁, x₂, …, xₙ。设G=(V, E)为一个NIDS网络的图表示（无向图），其中节点集V={1, 2, …, n}表示NIDS模块，边集E表示相应的NIDS网络链路。该图的邻接结构汇总于一个n×n邻接矩阵A，其中Aᵢⱼ=1当且仅当(i, j)∈E，否则Aᵢⱼ=0。G的邻接结构为每个节点i∈G定义了一个邻居集Nᵢ，其中Nᵢ={j∈V | (i, j)∈E}。

为了分布式计算（1），每个节点执行以下线性迭代：
$$
x_i(t+1) = W_{ii}x_i(t) + \sum_{j \in N_i} W_{ij}x_j(t),
$$
其中xi(0) = xi是节点i在迭代t=0时的初始值，Nᵢ是网络中与节点i直接相邻的节点集合，W是一个权重矩阵，可定义如下：
$$
W_{ij} =
\begin{cases}
\frac{1}{1+\max(d_i,d_j)} & \text{if } j \in N_i \
1 - \sum_{k \in N_i} W_{ik} & \text{if } i = j \
0 & \text{if } j \notin N_i
\end{cases}
$$
其中dᵢ = |Nᵢ|。

给定式(3)中描述的权重矩阵，式(2)中的线性迭代对每个节点而言，是将其状态与其邻居的状态进行反复平均。这种局部平均使得xi(t)渐近值收敛到式(1)中的平均和，当i=1..n时成立。由于在实际中迭代必须在某个时刻停止，因此式(2)仅计算式(1)的一个近似值。我们称这些n近似值为“共识”，如果它们根据某个预定义的阈值或特定应用的目的与式(1)足够接近。然而，达到可接受共识所需的迭代次数可能很大。

节点可能永远不会达成任何共识，或者它们可能就一个不同于式（1）中平均和的值达成共识。这取决于方程（2）的动力学行为，而该行为又依赖于权重矩阵W，该矩阵是一种基于精确共识的网络入侵检测系统邻接矩阵的加权版本A对于图G。系统xi(t)，i=1..n（由公式(2)定义）在权重矩阵满足某些条件时收敛到$\frac{1}{n}\sum_{i=1}^{n} x_i$，如[17]中所述。这些条件中的两个是：1‐生成相应邻接矩阵的图G A是连通的，即G中任意两个节点之间存在路径；2‐权重矩阵W是行随机的，即$\sum_{j=1}^{n} W_{ij}=1$，每一行权重之和等于1（注意对于无向图wᵢⱼ=wⱼᵢ，因此W=Wᵀ，从而权重矩阵W是双随机的$\sum_{j=1}^{n} W_{ij}=\sum_{i=1}^{n} W_{ji}=1$）。多个权重矩阵满足这些条件，公式(3)中的权重矩阵就是其中之一。

2.2 基于共识的入侵检测系统

基于共识的网络入侵检测系统[1]是一种完全分布式的网络入侵检测系统。它使用第2.1节中的渐近平均共识算法来聚合各个NIDS模块计算出的关于被监控网络状态的局部信息。在该系统中，每个NIDS模块的检测方法均采用基于异常的朴素贝叶斯分类器。每个NIDS模块会为观测到的良性或恶性网络流量计算一个初始局部概率。该分析阶段产生似然值P(Oᵢ|h)，表示模块i观测到的流量属于以下两个假设之一的概率：流量是异常的hₐ和流量是正常的hₙ。该局部分析阶段之后是一个全网范围的共识阶段，通过分布式计算对数似然的平均和
$$
\frac{1}{n}\sum_{i=1}^{n} P(O_i|h).
$$
共识阶段的初始值计算为xi(0) = log P(Oᵢ|h)。共识阶段包含n个并行的共识循环（共识循环是公式(2)的计算机程序实现），每个NIDS网络模块对应一个循环。共识循环i的停止条件由||xi(t+1) − xi(t)|| < ε给出，即当模块i在第t次与第t+1次迭代之间的共识值(xi(t))变化小于预定义的阈值ε时，循环停止（ε的取值被设定为在保证对网络流量状态判断准确性的同时，最小化共识阶段的迭代次数）。对于满足收敛假设的权重矩阵W，值||xi(t+1)−xi(t)||随t→∞渐近减小，因此该差值最终总会小于ε。设cᵢ表示共识循环i满足其停止条件所需的迭代次数。则共识阶段的迭代次数v由
$$
v = \max{c_1, c_2, …, c_n}.
$$
注意共识阶段是同步的，所有节点必须在进入执行共识循环迭代t+1之前完成迭代t的共识循环。

共识阶段一旦完成，每个NIDS模块i都会得到P(O|hn) = ∏ⁿᵢ₌₁ P(Oᵢ|hn)的似然的一个近似值≈P(O|hn)ᵢ，该似然表示网络广泛的观测网络流量是良性的，以及≈P(O|ha)ᵢ对P(O|ha)的近似= ∏ⁿᵢ₌₁ P(Oᵢ|ha)，即网络范围内观测到的网络流量为恶意的似然。最终是否发出警报由比值≈P(O|ha)ᵢ / ≈P(O|hn)ᵢ > τ与某个警报准则决定。

3 精确共识

本节描述了将用于取代网络入侵检测系统实现中渐近平均共识算法的精确共识算法[1]。我们首先对每个模块级别的可观测的NIDS输出进行建模。接着描述构成精确共识算法的线性变换。最后通过不同共识函数的示例来说明该算法。

3.1 可观测输出

方程(2)对一个局部系统对其自身状态xi(t)与其邻居xj(t)的状态j∈Nᵢ)进行平均的过程进行模。现在，我们对整个共识阶段以及每个局部系统用于计算平均值的状态进行建模。首先，给出共识阶段的动态方程：
$$
x(t+1) = Wx(t), t = 0, 1, …
$$
其中x(t)是一个包含n个元素的向量，其中第i个元素表示式(xi(t)在公式(2)中线性迭代的值，而W是权重矩阵。下一个方程从模块i的角度建模系统的可观测输出，该方程用精确共识替代了公式(2)的线性迭代：
$$
x(t+1) = Wx(t) \
y_i(t) = C_ix(t)
$$
其中，Cᵢx(t)返回模块i可观测到的x(t)的状态。矩阵Cᵢ是一个(degi+1)的×n矩阵，其元素Cᵢ[k,j]=1在j∈Nᵢ时为1，否则为Cᵢ[k,j]=0。因此，矩阵Cᵢ是每行仅有一个1的矩阵，表示向量x(t)中可被模块i直接访问的值。向量yᵢ(t)具有(degi+1)个元素，每个元素j表示模块i∪j∈Nᵢ在时间t的状态xⱼ(t)。本质上，yᵢ将模块i在共识阶段期间观察到的所有值堆叠起来。yᵢ的规模为((degi+1)×v)，其中(degi+1)是每次迭代t存储的值的数量，v是共识阶段的迭代次数，如公式(4)所定义。

3.2 代数变换

在共识阶段执行期间，每个模块i将信息存储在其列向量yᵢ中。该信息用于计算f(x(0))。精确共识算法需要一个函数Γᵢ，使得在共识阶段结束时，每个模块i能够根据yᵢ计算出f(x(0))，即Γᵢyᵢ=f(x(0))。

本节描述了用于在共识阶段执行前计算Γᵢ的共识阶段动态的数学表示。这些变换是矩阵，其中大多数因模块而异。

第一个线性变换是共识函数的矩阵表示f(x(0))。设f=$\frac{1}{n}\sum_{i=1}^{n} x_i(0)$（平均和函数）为每个模块根据分布在NIDS网络中的初始值xi(0)计算出的函数。该函数的矩阵表示为行向量1×n Q=[1/n, 1/n, …]，其中n为NIDS网络中模块的数量。可以验证f(x(0))=Q(x(0))。

我们现在定义可观测性矩阵。可观测性矩阵Oᵢ是一个线性变换，它直接从初始值向量x(0)、yᵢ=Oᵢx(0)计算出yᵢ。它是描述模块i在共识阶段期间观测到的值的数学模型。再次令x(t)表示在共识阶段第t次迭代时xᵢ、i=1..n的状态向量。根据线性代数，x(t)=Wᵗx(0)（其中Wᵗ为矩阵W自身相乘t次的结果），因此yᵢ(t)=CᵢWᵗx(0)。在第t=0次迭代时，yᵢ(0)观测到其自身的初始值xᵢ(0)及其邻居的初始值，即yᵢ(0)=Cᵢx(0)。在第t=1次迭代时，yᵢ(1)累积了其自身的值xᵢ(1)=Wᵢᵢxᵢ(0)+∑ⱼ∈NᵢWᵢⱼxⱼ(0)，以及其邻居计算出的值。从数学上看，对于第t=1次迭代，这等价于yᵢ(1)=CᵢWx(0)。在第t=2次迭代时，向量x(2)是通过计算x(1)=Wx(0)得到x(2)=Wx(1)的结果。这两个计算步骤在数学上等价于x(2)=W²x(0)，其中W²=W×W。因此，在t=2时，yᵢ累积了yᵢ=CᵢW²x(0)。Oᵢ定义如下：
$$
O_i =
\begin{bmatrix}
C_i \
C_iW \
C_iW^2 \
\vdots \
C_iW^{v-1}
\end{bmatrix}
$$
其中v是共识阶段的迭代次数。共识阶段后存储在向量yᵢ中的值可通过可观测性矩阵从数学上描述如下：
$$
\begin{bmatrix}
y_i(0) \
y_i(1) \
y_i(2) \
\vdots \
y_i(v-1)
\end{bmatrix} =
\begin{bmatrix}
C_i \
C_iW \
C_iW^2 \
\vdots \
C_iW^{v-1}
\end{bmatrix} x(0)
$$
其中每个yᵢ(t)t=0..v−1是一个包含(degi+1)个元素的列向量。

函数Γᵢ可以从可观测性矩阵Oᵢ推导出来，如果f的矩阵表示位于Oᵢ的行空间中（参见[2,3]中的证明）。因此，函数Γᵢ是Oᵢ各行的线性组合。为了解Γᵢ，需要解线性方程组
$$
\Gamma_i O_i^T = Q^T
$$
求解该方程，其中Oᵢᵀ是可观测性矩阵Oᵢ的转置，Qᵀ是对应于行向量Q的列向量。已知Γᵢ后，模块i可计算共识函数：f(x(0))：
$$
\Gamma_i
\begin{bmatrix}
y_i(0) \
y_i(1) \
y_i(2) \
\vdots \
y_i(v-1)
\end{bmatrix} = \Gamma_i O_i x(0) = Q x(0).
$$
可观测性矩阵的行维度v−1（共识阶段的迭代次数）由函数f的参数集决定。如果f的输入来自NIDS网络中的所有模块，那么每个计算f的模块都需要“观测”到每个模块的初始值。在这种情况下，v−1等于从模块i到网络中任何其他模块j的最长路径（因为数据从一个模块传播到另一个模块需要一次共识阶段迭代）[2,3]。在最坏情况下，共识阶段的迭代次数以及可观测性矩阵的行维度Oᵢ和列向量yᵢ的上界为网络中模块的数量。实际上，迭代次数更小，其上界为n−degi[2,3]，因此
$$
v \leq n - deg_i + 1
$$
公式(11)是一个上界。对于规则网络拓扑，可以计算出一个下界，该下界对应于网络直径[2,3]。为了从可观测性矩阵计算f(x(0))，必须选择共识算法的权重矩阵（见公式(3)），使得Q（即f的矩阵表示）位于可观测性矩阵Oᵢ的行空间中。在平均共识的情况下，几乎任意权重矩阵都满足此条件。最后，每个模块i只需存储矩阵Γᵢ，其他矩阵Oᵢ, Cᵢ, W和Q可在中央模块预先计算，仅需将矩阵Γᵢ推送到模块i，并用于计算共识函数f(x(0))。

3.3 共识函数的一些示例

考虑图1中的NIDS网络，一个环形网络。假设除了检测各个子网络级别的异常行为外，NIDS模块还需要计算一些代表整个被监控网络流量状态的全网范围值。我们考虑三种此类全网范围值的例子：平均和函数、最大值函数以及多数函数。

在描述Γᵢ函数以及该函数如何在每个模块级别上计算这些函数之前，我们首先展示矩阵Oᵢ,W, Cᵢ和Q如何在中央模块进行计算。

首先定义权重矩阵W，这三个示例中的权重矩阵与公式(3)中的权重矩阵相同。对于图1中4个模块的NIDS环形网络，这得到
$$
W =
\begin{bmatrix}
0.33 & 0.33 & 0 & 0.33 \
0.33 & 0.33 & 0.33 & 0 \
0 & 0.33 & 0.33 & 0.33 \
0.33 & 0 & 0.33 & 0.33
\end{bmatrix}
$$
接下来，为环形网络中的每个模块i计算邻接矩阵Cᵢ。在环形网络中，一个节点的度为deg=2。由于环是一个正则图，所有节点具有相同的度，因此每个矩阵Cᵢ的维度为(degi+1)×n，即3×4，因为图1中NIDS环形网络的模块数量为4。如前所述，Cᵢ是一个矩阵，其每一行仅有一个1，表示向量x(t)中可被模块i直接访问的值。这些值包括NIDS网络中与i相邻的每个模块j的值以及模块i本身的值。作为一个具体示例，我们考虑在图1中与模块2和模块4相邻的模块1，为此我们生成C₁、O₁，然后生成Γ₁。矩阵C₁如下所示：
$$
C_1 =
\begin{bmatrix}
1 & 0 & 0 & 0 \
0 & 1 & 0 & 0 \
0 & 0 & 0 & 1
\end{bmatrix}
$$
为了生成矩阵O₁，我们需要知道v。根据公式(11)，每个模块的该数值为2。矩阵O₁如下所示：
$$
O_1 = [C_1 \quad C_1W] =
\begin{bmatrix}
1 & 0 & 0 & 0 \
0 & 1 & 0 & 0 \
0 & 0 & 0 & 1 \
0.33 & 0.33 & 0 & 0.33 \
0.33 & 0.33 & 0.33 & 0 \
0.33 & 0 & 0.33 & 0.33
\end{bmatrix}
$$
下一步是计算Γ₁，即矩阵O₁各行的线性组合的系数。为了计算Γ₁，我们求解方程(9)中定义的线性方程组。对于这一部分，上述三个函数f将分别考虑。

平均和函数

平均和函数的矩阵表示$f = \frac{1}{n}\sum_{i=1}^{4} x_i(0)$是行向量Q=[0.25, 0.25, 0.25, 0.25]。求解Q和i=1，我们得到线性方程组O₁ᵀ=Qᵀ：
$$
\begin{bmatrix}
1 & 0 & 0 & 0.33 & 0.33 & 0.33 \
0 & 1 & 0 & 0.33 & 0.33 & 0 \
0 & 0 & 0 & 0 & 0.33 & 0.33 \
0 & 0 & 1 & 0.33 & 0 & 0.33
\end{bmatrix} =
\begin{bmatrix}
0.25 \
0.25 \
0.25 \
0.25
\end{bmatrix}
$$
该系统有无穷多解，其中一个为[−0.66,−0.33,−0.75, 2,−0.25, 1]，因此Γ₁=[−0.66,−0.33,−0.75, 2,−0.25, 1]。

一旦矩阵W、Oᵢ、Γᵢ和Cᵢ被计算出来，每个解矩阵Γᵢ将被发送到其对应的模块i。然后每个NIDS模块都具备了独立计算共识值$\frac{1}{n}\sum_{i=1}^{4} x_i(0)$所需的资源。首先，每个模块i用xᵢ(0)初始化其共识循环，该值表示其监控的子网络中流量的状态。接下来，所有模块进入共识阶段，在此期间，每个模块i将本地观察到的共识阶段状态存储在yᵢ(t)中。

假设模块1到4的初始值xᵢ(0)分别为1、2、3和4，因此x(0)=[1, 2, 3, 4]和$f = \frac{1}{n}\sum_{i=1}^{4} x_i(0) = 2.5$。我们再次考虑模块1的情况。在共识阶段第一次迭代后，列向量y₁(0)的内容可被数学描述为
$$
y_1(0) =
\begin{bmatrix}
1 & 0 & 0 & 0 \
0 & 1 & 0 & 0 \
0 & 0 & 0 & 1
\end{bmatrix}
\begin{bmatrix}
1 \
2 \
3 \
4
\end{bmatrix} =
\begin{bmatrix}
1 \
2 \
4
\end{bmatrix}
$$
在共识阶段的第二次迭代中，存储在y₁(1)=C₁Wx(0)的值
$$
\begin{bmatrix}
0.33 & 0.33 & 0 & 0.33 \
0.33 & 0.33 & 0.33 & 0 \
0.33 & 0 & 0.33 & 0.33
\end{bmatrix}
\begin{bmatrix}
1 \
2 \
3 \
4
\end{bmatrix} =
\begin{bmatrix}
2.31 \
2.0 \
2.66
\end{bmatrix}
$$
执行两个共识阶段后，列向量y₁ᵀ=[1, 2, 4, 2.31, 2, 2.66]。根据公式(10)，每个模块可本地计算共识值为$\frac{1}{n}\sum_{i=1}^{4} x_i(0) = \Gamma_i y_i$。实际上，Γ₁×y₁=2.46≈2.5的乘积，其差异由舍入误差引起。

最大值函数

在入侵检测的背景下，了解流量在哪一个子网络中受到最严重的损害可能是有意义的。这可以被视为一个最大值函数。为了就该值达成共识，我们可能希望每个模块通过求解恒等函数的方程(9)来恢复其他每个模块的初始值I₄：
$$
\begin{bmatrix}
1 & 0 & 0 & 0.33 & 0.33 & 0.33 \
0 & 1 & 0 & 0.33 & 0.33 & 0 \
0 & 0 & 0 & 0 & 0.33 & 0.33 \
0 & 0 & 1 & 0.33 & 0 & 0.33
\end{bmatrix} =
\begin{bmatrix}
1 & 0 & 0 & 0 \
0 & 1 & 0 & 0 \
0 & 0 & 1 & 0 \
0 & 0 & 0 & 1
\end{bmatrix}
$$
注意，W、C₁和O₁与之前的示例相同。唯一的区别是共识函数f=I₄。因此，Γ₁通过求解得到
之前的线性方程组O₁ᵀ=I₄。该方程组的解如下：
$$
\Gamma_1 =
\begin{bmatrix}
0.917 & -0.028 & -0.836 & -0.082 \
-0.083 & 0.953 & -0.336 & -0.033 \
-0.083 & -0.008 & -0.336 & 0.869 \
0.250 & 0.083 & -0.497 & 0.249 \
0.000 & 0.058 & 1.515 & -0.149 \
0.000 & -0.058 & 1.515 & 0.149
\end{bmatrix}
$$
假设模块1到4的初始值xᵢ(0)与前一个示例中的相同，则y₁ᵀ=[1, 2, 4, 2.31, 2, 2.66]也与平均和示例中的相同。可以验证
Γ₁ᵀ×y₁=[0.9965, 1.9994, 3.0598, 4.0015]，舍入误差导致了差异。每个模块都可以重构初始值，因此在每个模块i上计算max(Γᵢ×yᵢ)将返回相同的值4，所有模块就受异常流量影响最严重的子网络达成共识。

多数函数

作为最后一个例子，我们可以计算多数函数的Γᵢ，这是一个经典的分布式共识问题。在网络入侵检测系统（NIDS）场景中，该共识函数可用于判断大多数本地网络是否报告了异常流量。在此情况下，假设各模块的初始值xᵢ(0)为0或1，这些值可轻松从每个模块的朴素贝叶斯计算出的概率分布中提取。

多数函数的一种矩阵表示是全1的行向量：Q=[1, 1, 1, 1]。求解O₁ᵀ=Qᵀ
$$
\begin{bmatrix}
1 & 0 & 0 & 0.33 & 0.33 & 0.33 \
0 & 1 & 0 & 0.33 & 0.33 & 0 \
0 & 0 & 0 & 0 & 0.33 & 0.33 \
0 & 0 & 1 & 0.33 & 0 & 0.33
\end{bmatrix} =
\begin{bmatrix}
1 \
1 \
1 \
1
\end{bmatrix}
$$
我们得到Γ₁=[−0.043, 0.000, 0.434, 1.587, 1.444, 0.129]。假设初始值向量为x(0)=[0, 0, 0, 1]。共识阶段的第一次迭代返回y₁(0)
$$
y_1(0) =
\begin{bmatrix}
1 & 0 & 0 & 0 \
0 & 1 & 0 & 0 \
0 & 0 & 0 & 1
\end{bmatrix}
\begin{bmatrix}
0 \
0 \
0 \
1
\end{bmatrix} =
\begin{bmatrix}
0 \
0 \
1
\end{bmatrix}
$$
第二次迭代返回y₁(1)=C₁Wx(0)
$$
\begin{bmatrix}
0.33 & 0.33 & 0 & 0.33 \
0.33 & 0.33 & 0.33 & 0 \
0.33 & 0 & 0.33 & 0.33
\end{bmatrix}
\begin{bmatrix}
0 \
0 \
0 \
1
\end{bmatrix} =
\begin{bmatrix}
0.333 \
0 \
0.333
\end{bmatrix}
$$
经过两次共识迭代，列向量y₁ᵀ=[0, 0, 1, 0.333, 0, 0.333]。可以验证，乘积Γ₁×y₁=0.999≈1被解释为x(0)，仅包含一个1，异常流量仅在一个子网络中被报告，因此多数函数返回0。

4 实证验证与比较

本节中的测试和比较基于第2.2节所述的渐近共识网络入侵检测系统（详见[1]）以及第3节所述的精确值共识算法。在本节中，我们首先描述对两种算法进行测试的仿真环境，接着介绍第3节中算法实现的细节，最后提供两种算法的数值比较与分析。

4.1 仿真环境

我们针对11种不同的NIDS规则网络拓扑进行了测试：包含9、25、49、81和121个模块的环形结构，包含9、25、49、81和121个模块的二维环面，以及彼得森图（10个节点，15条边）。每次运行输入一个测试集和一个表示NIDS网络拓扑的图。测试集中的网络流量来自NLS-KDD数据集[18]，这是KDD’99数据集的改进版本。KDD’99数据集由麻省理工学院林肯实验室在国防高级研究计划局（DARPA）和空军研究实验室（AFRL）的资助下生成，用于评估计算机网络入侵检测系统[19,20]。与KDD’99数据集类似，NLS-KDD数据集的流量表示和分析基于41个特征。需要注意的是，我们已对NSL-KDD数据集中的攻击进行了过滤，仅保留了拒绝服务攻击。

每次测试包括对上述11种NIDS网络拓扑中的一种执行1000次迭代。在一次迭代中，网络拓扑中的每个NIDS模块从NSL-KDD数据集中读取本地网络流量，对本地流量进行贝叶斯分析，然后执行其共识循环直至收敛。

4.2 精确值共识实现

流量读取和贝叶斯分析的实现与渐近共识实现相同。模块i对本地网络流量的贝叶斯分析返回两个值：P(Oᵢ|ha)，表示模块i处观测到的流量为异常的似然；P(Oᵢ|hn)，表示模块i处观测到的流量为正常的似然。这些值用于以相应的对数似然初始化每个模块i的共识循环：xᵢᴬ(0) = log(P(Oᵢ|ha)) 和 xᵢᴺ(0) = log(P(Oᵢ|hn))，其中i=1..n。

精确共识的共识循环实现如下：
- 矩阵Oᵢ、Cᵢ、Γᵢ在每次测试开始之前预先计算（一次测试执行1000个共识阶段）
- 在每次测试开始之前，矩阵Γᵢ会被分发到各个模块。
- 在共识阶段的第t次迭代中，每个模块i将xᴬ(t)的可观测值存储在向量yᵢᴬ(t)中，并将xᴺ(t)的可观测值存储在向量yᵢᴺ(t)中。每个模块i在给定迭代t计算出的完整迭代结果如下：
$$
x^A(t+1) = Wx^A(t) \
y_i^A(t) = C_i x^A(t)
$$
$$
x^N(t+1) = Wx^N(t) \
y_i^N(t) = C_i x^N(t)
$$
- 我们为精确共识测试了两种停止条件：上界n−degi(11)以及与所测网络拓扑结构的直径相对应的下界（不同于渐近共识，其停止条件为||xᵢᴬ(t+1)−xᵢᴬ(t)||<ε和||xᵢᴺ(t+1)−xᵢᴺ(t)||<ε）
- 在共识阶段结束时，每个模块计算xᵢᴬ=Γᵢ×yᵢᴬ和xᵢᴺ=Γᵢ×yᵢᴺ以获得共识比率xᵢᴬ/xᵢᴺ。

一旦共识阶段完成，每个NIDS模块i会根据预定义的警报值比率λ，通过共识比率xᵢᴬ/xᵢᴺ>λ来决定是否发出警报。我们将xᵢᴬ/xᵢᴺ称为共识比率，因为每个模块达到的比率完全相同。共识比率的每一项表示观测到的流量为正常或异常的概率，即P(h|O)=αP(h)(∏ⁿᵢ₌₁P(Oᵢ|h))，其中为各模块计算的初始概率的联合似然（α为归一化常数）。回顾渐近共识将联合似然计算为初始对数似然的平均和：$\frac{1}{n}\sum_{i=1}^{n} P(O_i|h) = \exp(\sum_{i=1}^{n} \log P(O_i|h))$。

如第2.2节所述，$\exp(\sum_{i=1}^{n} \log P(O_i|h))$仅是对联合初始似然分布的近似，因为平均和是渐近计算的。因此，通过渐近共识计算出的比率≈P(hₐ|O)ᵢ/≈P(hₙ|O)ᵢ只是对精确共识比率xᵢᴬ/xᵢᴺ的近似。

4.3 测试结果

表1比较了渐近共识和精确共识过程的收敛速度。该表包含11行，对应于测试的11种网络拓扑。结果位于各行与“渐近值”和“精确值”两列交叉处。对于每种拓扑结构，我们运行了1000次共识阶段，每次具有不同的初始值。记录的结果是每个共识阶段执行的平均迭代次数（四舍五入）。对于渐近共识，迭代次数凭经验设定，以确保真实比率的近似$\frac{\sum_{i=1}^{n} \log(p_i^A)/n}{\sum_{i=1}^{n} \log(p_i^N)/n}$足够接近，使得每个NIDS模块产生相同的警报决策。对于精确共识，迭代次数由第11节中的上界公式(3.2)定义。此处的测试仅确认在这些界限内达到了收敛。此外，由于表1中的所有网络拓扑均为正则图，因此可为每个节点计算相同的下界，即图的直径。对于环，直径为n/2，对于二维环面，直径为n¹/²，而对于彼得森图，直径为2。因此，在表1的“精确值”列中，a/b分别表示计算共识值所需的迭代次数的下界和上界。

拓扑结构	规模	渐近值	精确值
Ring	9	25	5/7
Ring	25	146	13/23
Ring	49	452	25/47
Ring	81	990	41/79
Ring	121	1772	61/119
Torus	9	7	3/7
Torus	25	16	5/23
Torus	49	28	7/47
Torus	81	43	9/79
Torus	121	59	11/119
彼得森	10	9	2/8

表1中的结果表明，在环形拓扑结构中，精确共识的收敛速度明显更快；而对于二维环面，精确下界结果相较于渐近共识显著更优。这些结果表明，采用基于共识的网络入侵检测系统并使用精确共识，可大幅降低达成共识所需的通信开销。

表1报告了平均和共识函数的比较结果。如式(11)及其相关讨论所示，精确共识达到共识所需的迭代次数与所计算的共识函数无关。因此，精确共识在表1中表现出的性能对于任何其他共识函数都将保持一致。

任何共识函数都可以通过精确共识来计算，这一点可以从第3.3节中最大值函数的示例推导出来。在此示例中，使用恒等函数将初始输入x(0)传递到每个NIDS模块，从而允许每个模块计算其本地定义的任何函数。

准确性 网络入侵检测系统（NIDS）的准确性是指准确决策所占的百分比，即仅在网络遭受攻击时报告攻击。准确性取决于共识比率。我们可能认为基于近似联合似然的比率准确性较低（例如在未遭受攻击时发出警报），但[1]中的结果表明，情况未必如此，前提是渐近共识迭代次数足够大。然而，其逆命题并不成立，通常情况下，渐近共识的准确性不能超过精确共识。因此，我们不报告精确共识下的网络入侵检测系统准确性结果。每个模块都基于所提供的初始信息精确地计算函数，因此精确共识得出的网络入侵检测系统决策准确性已达到最佳水平，至少与计算函数近似值的渐近共识相当，甚至更优。

需要注意的是，精确共识的上述良好性能仅限于静态网络。NIDS网络的拓扑结构可能会因链路或节点发生物理故障，或因对网络入侵检测系统基础设施的网络攻击而发生变化。例如，如果图1中节点1和节点2之间的链路发生故障，则这两个节点的度将降低，因此需要重新计算矩阵C₁和C₂，以及这两个节点的可观测性和Γ矩阵。这些重新计算需要时间，但可以在本地完成。然而，图的直径无法在本地计算，因此后续共识阶段的迭代次数只能由上界确定。第二个问题是，通信方面的改进是以增加NIDS节点的存储能力和每次共识阶段结束时进行一次矩阵乘法为代价的。

5 结论

我们提出了一种新的基于精确共识的完全分布式网络入侵检测系统设计。该新设计基于精确共识，显著减少了共识阶段达到收敛所需的迭代次数。由于完全分布式NIDS非常适合监控可能存在能耗和带宽限制的无线网络流量，这些改进使该设计更接近实际部署。这一新设计还扩展了初始NIDS值可计算的函数集合，几乎可适用于任何函数。多种共识函数的引入无疑提高了系统的灵活性，并使完全分布式NIDS设计能够用于检测新型网络攻击（当前工作仅检测拒绝服务攻击）。

未来工作方面，我们仍需分析理论发展在[2,3]中设计网络入侵检测系统时可能的应用范围和局限性。一个简单的例子是，可以计算多个共识函数，并且理论上可以使用单个观测矩阵来计算它们。需要进行实证分析以理解可观测性矩阵与定义它们的权重矩阵之间的关系。我们还将考虑这些模型在动态网络中的高效适用性的发展。最后，更广泛地说，我们将继续探索控制理论这一丰富领域，以寻找适用于设计NIDS的模型。这种直觉并非全新，文献中已经提出了控制理论在网络安全中的若干应用，例如参见[21,22]仅举几例。