用于高速网络超连接主机检测中的流抽样装置和方法

摘要

一种用于高速网络超连接主机检测中的流抽样装置和方法，该装置由新流检测模块、误差吸收模块和随机抽样模块三个模块组成。流抽样方法是先由新流检测模块对每个到达的分组进行检测，判断该分组是否属于一个新流；若该分组属于新流，即表示有新流到达，则由误差吸收模块计算新流检测模块的检测误差概率，并依据该数值调整该新流的抽样概率；再由随机抽样模块根据误差吸收模块计算的抽样概率产生随机数，以决定是否抽样该流。本发明特点是克服了现有技术缺陷，实现了独立于流标识的等概率随机抽样，具有10Gbps线速处理能力和较小复杂度的存储空间，装置结构简单，工作稳定、可靠，成本低，能够广泛应用于现在及未来的高速网络中，具有很好的应用前景。

说明书

技术领域

本发明涉及一种网络安全检测技术，确切地说，涉及一种用于高速网络超连接主机检测中的流抽样装置及其流抽样的实现方法，属于网络互连通信技术领域。

背景技术

近年来，网络安全事件频繁发生，各种病毒泛滥，例如分布式拒绝服务攻击(DDoS)、蠕虫(Worms)病毒传播、端口扫描(Port Scan)等，有的网络安全事故能够造成巨大的经济损失。随着互联网逐渐渗透到人类经济、社会活动的各个方面，准确、快速地检测和响应网络安全事件已经成为互联网领域中不可或缺的重要技术。

经研究发现，网络安全事件所具有的相似行为有利于检测的进行。例如，扫描式蠕虫(Scanning Worms)在进行传播时，被病毒感染的主机通常会在短时间内向大量其它主机发送分组。为了发现具有安全漏洞的主机，入侵者往往利用端口扫描技术通过一台主机向大量其它主机的同一端口或同一主机的不同端口发送探测分组。从网络层角度看，如果在短时间内，发现网络中有一系列IP分组具有同一源IP地址、不同目的IP地址(或同一目的IP地址、不同端口号)，则网络安全检测系统就可以把源IP地址的主机列为嫌疑主机，并作进一步的分析及响应。与以上情况相对称，分布式拒绝服务攻击(DDoS)是在短时间内大量不同主机向同一目标主机发送攻击分组，在此情况下，则是短时间内的一系列IP分组具有同一目的IP地址和不同的源IP地址。

上述这些情况的共同特点是：在短时间内某个主机与其它主机间存在大量不同的IP流(IP flow)，此种情况下的主机被称为超连接主机。IP流(IP flow)是一系列具有共同属性的IP分组集合，其中的共同属性取决于它们的流标识(流ID或flow ID)。在以上例子中，传播蠕虫病毒的主机、进行端口扫描的主机、以及DDoS的被攻击者都是超连接主机。超连接主机的存在就预示着网络安全事件的发生，并可以此为触发条件继续进行分析和响应。因此检测和发现超连接主机是网络安全检测中的重要基础。

目前，网络安全检测系统(如入侵检测系统、防火墙等)已广泛部署于各个局域网的边缘或网络的入口处，用于保护各企事业单位的内部网络。近年来，DDoS在攻击目标的同时，大量消耗网络带宽；蠕虫的传播往往使相关链路迅速达到饱和。这些安全事件都会使互联网服务提供商(ISP)的核心网络服务质量下降，促使越来越多的ISP正在或计划在其核心网络部署网络安全检测系统。另外，大型企业内部网络及其Web站点往往是DDoS的攻击目标，而且，随着业务的发展，这些网络的接入带宽也在不断提升。这就需要网络安全检测能够适应更高的链路速率(2.5Gbps以上)，以满足ISP或大型企业的需要。

传统的超连接主机检测技术大都使用维护每流状态的方法。例如，为了检测端口扫描，Snort系统通过保存每个流信息(即由源、目的地址对组成的流标识)来统计每个源主机与多少不同主机(或端口)进行通信。然而，链路的高速化给超连接主机检测带来了很大的挑战：一方面，在高速链路中，单位时间内存在大量的流(Flow)。为了保存这大量的流的标识，必须使用高容量的存储器；另一方面，为了在高速网络中线速处理IP分组，必须使用高速存储器。根据现有的半导体技术，动态随机访问存储器(DRAM)容量大，但是其访问速度较慢(速率为几十纳秒)，不能适应高速网络中的线速处理需求；而静态随机访问存储器(SRAM)访问速度虽快(速率为几纳秒)，但是其容量有限(只有几十Mbits)，不能满足维护每流状态的要求。

为了应对网络高速化带来的可扩展性挑战，人们近来普遍采用基于流抽样(Flow Sampling)的方法。其基本思想是对每个新观测到的流进行固定概率的抽样，与抽样流相关的主机(包括源IP地址主机或目的IP地址主机)被视为重点测量对象，并对它们进行流测量(例如，为这些主机的流维护每流状态，用于流计数)。在以后的测量中，如果某个重点测量对象的流个数超过设定的门限，则将判断该测量对象为超连接主机。因为与超连接主机相关的流的数量较多，只要流抽样概率的数值设计合理，则超连接主机将在概率保证下被列为重点测量对象。

对于超连接主机的检测来说，流抽样必须满足两个基本要求：(1)抽样的一次性：在网络层，测量的基本单位是分组，而一个流会有多个分组，“抽样的一次性”要求：对每一个流只进行一次抽样，并不依赖于实际测量到的、属于该流的分组数量；这就保证了抽样的基本单位是流，而不是分组。(2)等概率随机抽样：任何一个流被抽样的概率是相等的，并不依赖于流标识的内容；这就保证了每一个主机被列为重点测量对象的概率与它的流数量成正比，从而使得超连接主机在概率保证下被列为重点测量对象。

当前，现有技术都是使用基于哈希流抽样(hash based flow sampling)方法来进行流抽样，其基本思想是：给定一个哈希函数h，其自变量定义域为流标识的空间F，函数值域为H：[0，1)；再给定一个抽样域S：[x，x+r)，其中检测开始点所在位置x(实数)和抽样概率r的取值范围是：0≤x＜x+r≤1；对于每个到达的分组，记它所归属的流的流标识为f，求它的哈希值h(f)，如果h(f)∈S，则该分组所在的流被抽样；否则，不被抽样。

设定哈希函数h和抽样域S：[x，x+r)后，一个流是否被抽样就依赖于流标识f，即其哈希函数值h(f)是否在S范围内。为了满足“等概率随机抽样”的要求，哈希函数h必须满足均匀随机哈希(uniform random hashing)属性：对于任意的流标识f，哈希函数值h(f)是均匀分布于H：[0，1)上的随机变量。在理论上并不能证明存在有满足均匀随机哈希属性的哈希函数，因此使用基于哈希流抽样的基本假设前提是：存在有足够近似的均匀随机哈希属性的哈希函数。

基于哈希流抽样算法的关键是哈希函数的选择。所选择的哈希函数必须同时满足以下三个要求：(1)计算快速，(2)安全性高，(3)有足够好的均匀随机哈希属性。

由于要对链路到达的每个IP分组进行线速处理，因此所选择的哈希函数必须能够在最短的分组到达时间间隔内完成一次哈希值的计算。例如：在OC-48(2.5Gbps)、OC-192(10Gbps)链路下，每个哈希值的计算时间必须分别小于128纳秒、32纳秒。这就要求哈希函数计算器应该具有很快的计算速度，以适应不同的高速链路。

超连接主机检测主要应用于网络安全领域，因而检测系统本身的安全性能更为重要。由于基于哈希流抽样的算法是使用哈希函数进行流抽样，因此它容易遭受算法复杂性攻击而存在安全隐患。例如，在DDoS攻击中，如果事先掌握了流抽样中使用的哈希函数，攻击者就可以通过伪造源IP地址来产生一系列特定的攻击流，使得这些流标识的哈希值都(或大部分)落在抽样域之外，从而逃避超连接主机检测。

虽然能够用哈希函数提供伪随机哈希值序列，但是，由于哈希函数是确定性函数，哈希值仍然依赖于哈希函数的输入值。如果输入具有随机性，就比较容易得到较好的随机性输出；如果输入没有随机性而又要得到足够随机的输出，就必须使用具有强均匀随机哈希属性的哈希函数。

目前公认能够产生随机性序列最好的哈希函数是MD5、SHA1等加密性哈希函数，但是这些哈希函数的计算复杂，很难实现快速运算，即使采用专用器件也需要几十个时钟周期才能产生一次输出，因此很难用于高速分组处理环境。例如，目前一些现有技术的专用硬件的一次运算过程至少需要64个时钟周期，这已经超过了高速网络环境下最小的分组处理时间，即使用Xilinx FPGA Virtex系列的最高档产品Virtex-4(500MHZ)，64个时钟周期也至少需要128纳秒。而在2.5Gbps链路下，最小分组的处理时间必须小于128纳秒，在10Gbps链路下，则要小于32纳秒。而且，由于MD5、SHA1等哈希函数算法的顺序操作特性很难通过改进的并行和流水优化技术来提高计算速度。同样，CRC32算法因其需要进行大量的乘除法运算，计算速度也较慢。而基于简单除法、乘法运算的哈希函数则因其数学结构简单而缺乏安全性。总之，现有的哈希函数中，计算速度快的哈希函数缺乏安全性或均匀随机性，而具有高安全性和强均匀随机性的哈希函数却计算速度太慢。

因此，现有的基于哈希流抽样方法只能使用在速率较低的环境下(低于2.5Gbps)。为了能够在更高速的环境下检测超连接主机，尽快设计一种新的流抽样方法就成为业内技术人员的新课题。

发明内容

有鉴于此，本发明的目的是提供一种用于高速网络超连接主机检测中的流抽样装置及其流抽样的实现方法，本发明能够较好地克服现有技术的各种缺陷，具有10Gbps线速处理能力和较小的空间复杂度，能够实现独立于流标识的等概率随机抽样，可以用于10Gbps高速网络中的安全事件检测。

为了达到上述目的，本发明提供了一种用于高速网络超连接主机检测中的流抽样装置，其特征在于：所述装置包括下述三个模块：

新流检测模块，设置在局域网的边缘、网络的入口处或核心网络内部，对输入的IP分组采用哈希函数进行检测，判断是否有新流到达，若有新流到达，则将该流的流标识送到随机抽样模块，以便对该流进行抽样；

随机抽样模块，根据误差吸收模块计算的抽样概率产生随机数，用于对新流进行随机抽样，以输出抽样流，但此时的抽样与各个新流的流标识无关；

误差吸收模块，分别连接上述两个模块，藉由新流检测模块中的流计数器统计的新流个数，计算新流检测模块的误差概率，进而调整抽样率，使得因新流检测模块没有将新流判断出来而造成的漏检误差的随机性，能够被抽样的随机性所消化，以抵消新流检测模块的检测误差，满足“等概率随机抽样”的设计要求。

所述新流检测模块是由多个彼此独立的哈希函数运算器h₁，h₂，...，h_k和与其顺序连接的m位比特的位向量存储器、与非门和流计数器所组成，其中每个哈希函数的值域都为{1，2，...，m}，哈希函数运算器的个数k和位向量存储器的比特位数m皆为自然数，k值是大于等于2的自然数，m远大于k，m可为10⁷。

所述哈希函数运算器是由能快速完成矩阵乘法、加法运算的与门和异或门两种逻辑器件组成的H₃哈希函数运算器，H₃哈希函数通过下述等式的线性变换： $>\left(\begin{array}{}>>>>b>1>>>>>>>b>2>>>>>>·>>>>>·>>>>>·>>>>>>b>z>>>\end{array},\left(\begin{array}{}>>>>r>11>>>>>r>12>>>>·>·>·>>>>r>>1>w>>>>>>>>r>21>>>>>r>22>>>>·>·>·>>>>r>>2>w>>>>>>>·>·>·>>>·>·>·>>>·>·>·>>>·>·>·>>>>>>r>>z>1>>>>>>r>>z>2>>>>>·>·>·>>>>r>zw>>>\end{array},\left(\begin{array}{}>>>>a>1>>>>>>>a>2>>>>>>·>>>>>·>>>>>·>>>>>>a>w>>>\end{array}\right)\right)\right)$₁a₂…a_w映射为z比特的二进制字符串B＝b₁b₂…b_z，其中矩阵元素r_ij＝0或1，表示矩阵行、列序号的下标i、j的取值范围分别是：{1，2，...，z}和{1，2，...，w}。

所述m比特的位向量存储器是高速多端口SRAM器件或多个并行的双端口SRAM器件，以使每个分组的处理时间不超过10纳秒，能够支持10Gbps链路上IP分组的线速处理。

所述随机抽样模块是一个随机数生成器，对每一个由误差吸收模块计算的抽样概率p_s生成一个设定区间[0，1)内的随机数r_n；若r_n＜p_s，则抽样新到达的流，否则，不抽样，用于实现独立于流标识的等概率随机抽样。

为了达到上述目的，本发明还提供了一种采用高速网络超连接主机检测中的流抽样装置进行流抽样的方法，其特征在于：先由新流检测模块对每个到达的分组进行检测，判断该分组是否属于一个新流；若该分组属于新流，即表示有新流到达，则由误差吸收模块计算新流检测模块的检测误差概率，并依据该数值调整该新流的抽样概率；然后，由随机抽样模块根据误差吸收模块计算的抽样概率产生随机数，以决定是否抽样该流。

所述方法包含下述步骤：

(1)初始化操作：在每个测量周期开始时，将新流检测模块中的位向量存储器的m个比特位和流计数器都初始化为零；

(2)检测新流：新流检测模块采用哈希函数对每个新到达的分组进行检测，判断其是否为一个新流的分组，同时将属于该流的后续分组鉴别出来，以保证流抽样的“一次性”，即对每个流只进行一次抽样；

(3)调整抽样率：误差吸收模块通过流计数器统计已检测的新流个数，再计算新流检测模块的误差概率p，则每个新流被新流检测模块成功检测出来的概率为1-p；然后根据预设抽样概率r将随机抽样模块的抽样概率调整为以保证任何一个新流被抽样的概率都等于 $>>r>=>>(>1>->p>)>>\times >>r>>1>->p>>>,>>>以满足“等概率随机抽样”的设计要求；$

(4)随机抽样：随机抽样模块根据前述步骤调整的抽样概率产生随机数，用于对新流进行随机抽样；

(5)根据流计数器的统计数值决定流抽样的进程：如果流计数器的统计数值n已经达到设定的上限数值(例如设定上限数值是为了能够将新流检测模块所产生的实际误差概率控制在较小数值之内，并接近于按照公式 $>>p>=>>>(>1>->>>(>1>->>1>m>>)>>kn>>)>>k>>>>计算的理论值，实现等概率随机抽样)，则跳转执行步骤(1)，重新启动新的测量周期；否则，跳转执行步骤(2)，继续处理下一个分组。$

所述步骤(2)进一步包括下列操作内容：

(21)每次到达一个新分组时，先由新流检测模块中的k个哈希函数运算器h₁，h₂，...，h_k分别计算该分组流标识f的k个相应哈希函数值h₁(f)，h₂(f)，...，h_k(f)，并根据哈希函数的计算结果分别访问相应位置的位向量存储器；

(22)如果位向量存储器中的第h₁(f)，h₂(f)，...，h_k(f)比特中至少有一个比特是“0”，则判定该分组属于一个新流，即有新流到达，继续执行后续操作；否则，返回步骤(21)，开始处理下一个分组；

(23)把位向量存储器中的第h₁(f)，h₂(f)，...，h_k(f)比特中为“0”的比特置为“1”后，执行操作步骤(3)。

所述步骤(3)进一步包括下列操作内容：

(31)先统计流计数器中的数值，即此时已被正确检测的新流个数n，则位向量存储器中最多会有kn个比特位为“1”，k为哈希函数运算器的个数；

(32)假设哈希值均匀分布，则根据概率论计算新流检测模块出现检测误差的漏检概率p： $>>p>=>>>(>1>->>>(>1>->>1>m>>)>>kn>>)>>k>>,>>>也就是位向量存储器中与当前到达的新流所对应的k个比特位均为“1”的概率，式中m是位向量存储器的比特位数；则每个新流被新流检测模块成功检测出来的概率为1-p；$

(33)对流计数器加1，即n＝n+1；

(34)根据预设抽样概率r将随机抽样模块的抽样概率调整为

本发明是一种用于高速网络超连接主机检测中的流抽样装置及其流抽样的实现方法，技术上的主要创新是把“等概率随机抽样”的功能从哈希函数本身中分离出来，而由专门设置的随机抽样模块完成该功能，这样就可以减弱对哈希函数的均匀随机哈希属性的要求，使得该方法能够选用计算速度快的哈希函数进行检测，从而使得本发明装置和方法具有10Gbps线速处理能力和较小复杂度的存储空间，还能够实现独立于流标识的等概率随机抽样。而且，本发明装置结构简单(只有三个控制模块)，工作稳定、安全、可靠，成本低廉，因此，本发明能广泛应用于现在及未来的高速网络环境中，具有很好的推广应用前景。

附图说明

图1是本发明用于高速网络超连接主机检测中的流抽样装置的结构组成示意图。

图2是本发明用于高速网络超连接主机检测中的流抽样装置的流抽样实现方法的操作步骤方框图。

具体实施方式

为使本发明的目的、技术方案和优点更加清楚，下面结合附图和实施例对本发明作进一步的实现细节的详细描述，最后通过实验结果来对照说明该方法的优点。

参见图1，介绍本发明用于高速网络超连接主机检测中的流抽样装置的结构组成，该装置由新流检测模块、误差吸收模块及随机抽样模块三个模块组成。其中设置在局域网的边缘、网络的入口处或核心网络内部的新流检测模块的功能是对输入的IP分组采用哈希函数进行检测，判断是否有新流到达，若有新流到达，则将该新流的流标识送到随机抽样模块，以便对该流进行抽样。随机抽样模块的功能是根据误差吸收模块计算的抽样概率产生随机数，以对新流进行随机抽样而输出抽样流，但此时进行的抽样与各个新流的流标识无关。由于新流检测模块存在测量误差(即有些新流不能被它判断出来)，误差吸收模块的功能是藉由新流检测模块中的流计数器统计的已检测的新流个数，计算新流检测模块的误差概率，再根据误差概率来调整抽样率，使得因新流检测模块没有将新流判断出来而造成的漏检误差的随机性，能够被抽样的随机性所消化，以抵消新流检测模块的检测误差，满足“等概率随机抽样”的设计要求。

其中新流检测模块是由k个彼此独立的哈希函数运算器h₁，h₂，...，h_k(k值为大于等于2的自然数，图1中k＝3)和与其顺序连接的一个m比特的位向量存储器、一个“与非”门逻辑电路和一个流计数器所组成，其中每个哈希函数的值域都为{1，2，...，m}，自然数m远大于k，m可为10⁷。

本发明的哈希函数运算器推荐选择H₃哈希函数，因为H₃哈希函数通过下面的线性变换： $>\left(\begin{array}{}>>>>b>1>>>>>>>b>2>>>>>>·>>>>>·>>>>>·>>>>>>b>z>>>\end{array},\left(\begin{array}{}>>>>r>11>>>>>r>12>>>>·>·>·>>>>r>>1>w>>>>>>>>r>21>>>>>r>22>>>>·>·>·>>>>r>>2>w>>>>>>>·>·>·>>>·>·>·>>>·>·>·>>>·>·>·>>>>>>r>>z>1>>>>>>r>>z>2>>>>>·>·>·>>>>r>zw>>>\end{array},\left(\begin{array}{}>>>>a>1>>>>>>>a>2>>>>>>·>>>>>·>>>>>·>>>>>>a>w>>>\end{array}\right)\right)\right)$₁a₂…a_w映射为z比特的二进制字符串B＝b₁b₂…b_z，其中矩阵元素r_ij＝0或1，矩阵行、列序号的下标i、j的取值范围分别是：{1，2，...，z}和{1，2，...，w}。

由于H₃哈希函数运算器仅由“与”、“异或”两种逻辑门电路组成，即其是采用能够快速完成矩阵乘法、加法运算的与门和异或门两种器件组成，能够很容易地实现k个并行的H₃哈希函数计算，而且处理速度能达到纳秒级。

由于每个流只占用位向量存储器的k个比特，这样本发明装置所需要的存储空间就比较少，可以用SRAM制成位向量存储器。根据当前的半导体技术，即使是片内(on-chip)SRAM的容量也可以达到10Mbits。例如，大部分现代商用现场可编程逻辑阵列FPGA都包含多个双端口嵌入式片内SRAM。例如Xilinx公司的Virtex-4产品最多可包含552个18kbits双端口SRAM模块，总容量近10Mbits。为了提供k个哈希地址的并行访问，本发明位向量存储器采用高速多端口SRAM模块或多个并行的双端口SRAM制成。由于，目前的片内SRAM访问速度已达1～2纳秒，而片外(off-chip)SRAM也可达2～5纳秒。因此整个装置处理一个分组的时间可控制在10纳秒左右，足够支持10Gbps链路上IP分组的线速处理。

本发明的随机抽样模块是一个随机数生成器，对每一个由误差吸收模块计算的抽样概率p_s生成一个设定区间[0，1)内的随机数r_n；若r_n＜p_s，则抽样新到达的流，否则，不抽样。值得注意的是：这里产生的随机数不依赖于新到达的流标识，因此流标识的内容不影响所产生随机数的随机性，因此，本发明中的每个新流是否被抽样是独立于其流标识的等概率随机抽样。

虽然本发明与现有技术都是使用哈希函数来检测新流，但是它们之间的差别是明显的。通常，基于哈希的传统抽样方法是试图通过哈希函数来实现等概率随机抽样。但是，由于对于哈希函数的均匀随机哈希属性的假设不合理，导致这种现有技术无法用于高速网络环境中。本发明的创新之处是它使用哈希函数只是为了判断是否有新流到达，对哈希函数的均匀随机哈希属性没有特殊要求；而由本发明专门设置的、独立于流标识的随机抽样模块完成对流的抽样，从而减弱了对哈希函数的均匀随机哈希属性要求，保证在高速网络环境下也能实现等概率随机抽样。

本发明又公开了一种用于高速网络超连接主机检测中的流抽样装置进行流抽样的方法：先由新流检测模块对每个到达流抽样装置的分组进行检测，判断该分组是否属于一个新的流；若该分组属于新流，即表示有新流到达，则由误差吸收模块计算新流检测模块的检测误差概率，并依据该数值调整该新流的抽样概率；然后，由随机抽样模块根据误差吸收模块计算的抽样概率产生随机数，以决定是否抽样该流。

参见图2，介绍本发明流抽样方法的具体操作步骤：

(1)初始化操作：在每个测量周期开始时，将新流检测模块中的位向量存储器的m个比特位和流计数器都初始化为零；

(2)检测新流：新流检测模块采用哈希函数对每个新到达的分组进行检测，判断其是否为一个新流的分组，同时将属于该流的后续分组鉴别出来。由于属于同一个流的分组的流标识都相同，因此只有当一个流的第一个分组到达时才会被认为有新流到达，而当属于该流的后续分组到达时，由于位向量存储器中相应的比特位均已被设置为“1”，所以不会被认作是到达的新流，从而保证流抽样的“一次性”，即对每个流只进行一次抽样。

该步骤还可以细分为下述操作内容：

(21)每次到达一个新分组时，先由新流检测模块中的k个哈希函数运算器h₁，h₂，...，h_k分别计算该分组流标识f的k个相应哈希函数值h₁(f)，h₂(f)，...，h_k(f)，并根据哈希函数的计算结果分别访问相应位置的位向量存储器；

(22)如果位向量存储器中的第h₁(f)，h₂(f)，...，h_k(f)比特中至少有一个比特是“0”，则判定该分组属于一个新流(即有新流到达)，流计数器加1后，执行后续操作；否则，返回步骤(21)，开始处理下一个分组；

(23)把位向量存储器中的第h₁(f)，h₂(f)，...，h_k(f)比特中为“0”的比特置为“1”后，执行操作步骤(3)。

(3)调整抽样率：误差吸收模块通过流计数器统计已检测的新流个数，再计算新流检测模块的漏检误差概率p，则每个新流被新流检测模块成功检测出来的概率为1-p；然后根据预设抽样概率r将随机抽样模块的抽样概率调整为以保证任何一个新流被抽样的概率都等于 $>>r>=>>(>1>->p>)>>\times >>r>>1>->p>>>,>>>以满足“等概率随机抽样”的设计要求。$

下面对该步骤(本发明方法的关键操作)进行详细说明：

随着新流的不断到达，位向量存储器中越来越多的比特位被设置为“1”，因此有可能出现如下情况：当一个新流的第一个分组到达时，由于哈希冲突，其流标识的k个哈希函数值正好与先期到达的其它流的流标识所计算的哈希值相同，因而由该新流所决定的位向量存储器中k个比特位已经因其它流的到达而被设置为“1”，因此，在这种情况下，该新流就不会被新流检测模块正确检测出来，从而产生检测误差。

如果一个新流到达时，新流检测模块已经正确检测出的流个数为n(也就是流计数器中的值)，则位向量存储器中最多有kn个比特位为“1”。假设哈希值均匀分布，则根据概率论，位向量存储器中由新流所决定的k个比特位均为“1”的概率为 $>>p>=>>>(>1>->>>(>1>->>1>m>>)>>kn>>)>>k>>,>>>即新流检测模块出现检测误差的漏检概率为p，因此一个新流被新流检测模块成功检测出的概率为1-p。$

因此，该步骤的操作是：调整随机抽样模块的抽样概率为(r为本发明方法的预设抽样概率)，这样可以保证任何一个新流被该方法抽样的概率都等于r(即)，从而满足了“等概率随机抽样”需求。虽然计算p的数学公式在理论上要求哈希值必须均匀分布，但是当检测的流个数n小于某个设定的数值(例如

(31)先统计流计数器中的数值，即此时已被正确检测的新流个数n，则位向量存储器中最多会有kn个比特位为“1”，k为哈希函数运算器的个数；

(32)假设哈希值均匀分布，则根据概率论计算新流检测模块出现检测误差的漏检概率p： $>>p>=>>>(>1>->>>(>1>->>1>m>>)>>kn>>)>>k>>,>>>也就是位向量存储器中与当前到达的新流所对应的k个比特位均为“1”的概率，式中m是位向量存储器的比特位数；则每个新流被新流检测模块成功检测出来的概率为1-p；$

(33)对流计数器加1，即n＝n+1；

(34)根据预设抽样概率r将随机抽样模块的抽样概率调整为

(4)随机抽样：随机抽样模块根据前述步骤(3)调整的抽样概率产生随机数，用于对新流进行随机抽样；

(5)根据流计数器的统计数值决定流抽样的进程：如果流计数器的统计数值n已经达到设定的上限数值(例如设定上限数值是为了能将新流检测模块所产生的实际误差概率值控制在较小数值之内，并使该数值接近于按照公式 $>>p>=>>>(>1>->>>(>1>->>1>m>>)>>kn>>)>>k>>>>计算的理论值，实现等概率随机抽样)，则跳转执行步骤(1)，重新启动新的测量周期；否则，跳转执行步骤(2)，继续处理下一个分组。$

本发明的方法已经进行了实验论证。该实验使用互联网数据分析合作协会(CAIDA)及美国应用网络研究国家实验室(NLANR)提供的实际互联网数据，实验数据相关信息如下表：

  数据源 所在网络  链路速率  数据采集日期   OC48 Link A  (CAIDA)  One ISP in US   2.5Gbps  2002.8.14   2003.4.24  2003.1.15  Abilene-III(NLANR) Internet2  10Gbps  2004.7.1  CENIC-I(NLANR) CENIC  10Gbps  2005.3.18

实验中，使用文献《新的快速检测超传播者的流算法》(《New streamingalgorithms for fast detection of superspreaders》In Proceedings of the 12thAnnual Network and Distributed System Security Symposium，San Diego，California，2005)中的一级过滤算法(One level Filtering)检测超连接主机与流抽样算法进行比较。假设流个数超过k_s的主机为超连接主机，根据用户给定的参数b(b＞1)，如果流个数小于k_s/b的主机被判断为超连接主机，则称为“误检”。文献《新的快速检测超传播者的流算法》证明：对于任意给定的信任度δ(0＜δ＜1)，一级过滤算法能够自动选择合适的抽样率，以保证“漏检率”及“误检率”都小于δ。但是其假设前提是流抽样要满足“等概率随机抽样”。在实验中，分别使用基于哈希流抽样(简称为“旧方法”)和本发明方法(简称为“新方法”)来实现一级过滤算法，且这两种抽样算法都使用H₃哈希函数。

实验结果数据如下表所示：

  k_s  b                 线性流标识情况              随机流标识情况        误检率(％)     漏检率(％)       误检率(％)     漏检率(％)  旧方法  新方法  旧方法  新方法  旧方法  新方法  旧方法  新方法  500  2  1.674  0.076  8  0  0.074  0.077  0  0  5  1.089  0.027  5  1  0.028  0.027  1  0  10  2.506  0.248  5  0  0.266  0.251  0  0  1000  2  1.781  0.118  11  2  0.129  0.115  3  1  5  0.55  0.018  8  1  0.034  0.019  0  0  10  2.27  0.219  7  0  0.306  0.303  0  0  5000  2  1.977  0.158  6  1  0.191  0.169  0  1  5  0.75  0.025  6  0  0.024  0.028  1  1  10  3.913  0.384  4  0  0.358  0.391  0  0  10000  2  1.846  0.183  5  1  0.182  0.192  1  0  5  0.756  0.021  3  0  0.025  0.024  0  1  10  3.783  0.356  2  0  0.374  0.345  0  0

可以看出：流标识序列为线性流标识时，使用新方法时所产生的“漏检率”和“误检率”都小于其理论值(3％)。而使用旧方法所产生的“漏检率”在大部分情况下都超过了相应的理论值，而且比新方法时的“漏检率”高出2至9个百分点，这对于安全应用是很高的数值。虽然使用旧方法所产生的“误检率”小于理论值，但是仍比新方法高出10至40倍，这意味着用来维护嫌疑超连接主机的存储空间要大10至40倍。虽然“误检率”的绝对值比较小，但是由于正常流的数量巨大，误检所引起的存储空间的消耗也是相当可观的。使用旧方法时产生较大误差率的原因正如前面所介绍的：旧方法对线性流标识序列不能进行等概率随机抽样。对于随机流标识序列的情况，使用两个抽样算法时的检测结果都符合理论值。值得注意的是：使用新方法所产生的结果与线性流标识序列的情况下的结果没有显著区别，说明新方法对线性和随机流标识序列都能满足“等概率随机抽样”，具有较好的适应性。

试验结果说明，本发明的实验是成功的，实现了发明目的，该流抽样装置及其使用方法具有很好的应用前景。