基于GPU并行计算的快速智能入侵检测技术研究

1、入侵检测系统（Intrusion Detection System, IDS）作为保障网络和主机安全的重要手段，一直是研究者和工业界的关注热点。根据数据源不同可以分为： HIDS 和 NIDS 根据入侵检测技术不同入侵检测分为： 异常检测 和 误用检测 1）对未知攻击的有效检测： 目前商业入侵检测系统中大量使用的是基于模式 匹配的误用检测方法，只能检测出已知攻击，不 能检测到新的攻击类型。2）高速环境下的检测： 高速大流量网络数据使智能IDS在建模和检测阶 段均面临巨大的数据运算和分析压力，容易产生 大量漏报、误报。针对问题 1）：针对问题 2）：支持向量机 ( Support Vector

2、Machines, SVM)是20 世纪90年代发展起来的一种新的机器学习方法。它基于结构风险最小化原理，能够有效地避免经 典学习方法中出现的过学习、欠学习、维数灾难 以及陷入局部极小点等诸多问题。在入侵检测上有不少学者开展了研究，得到了初 步成功的结果 。考虑给定的训练样本集 L: (x1, y1)， ，(xN, yN)，x Rd，y+1,-1， N为样本数，d为输入维数，x为 输入数据， y为输出数据。如果y的值为“1”，表示对应的样本为正常样本，如果y的值为 “-1”，表示对应的样本为异常样本，即有入侵发生。根据支持向量机理论，对于待分类样本存在一个最优分类超平面，使得两类样本以最大距离

3、被完全分开。 求解该超平面可以看成解如下问题： ， 是拉格朗日乘子，对应于 0 的向量称为支持向量。 K( xi, x )为核函数。 求解该问题，得到最优分类函数： 由SVM的理论可以知道： SVM最优分类面的位置仅由支持向量来决定，而 与非支持向量无关。在SVM分类中，只有那些在两类样本相邻边界或 附近的向量才有可能成为支持向量。在特征空间中，待分类的每一类样本都由它的凸包包围。 凸包是包含数据集中所有样本的最小凸多面体。对线性可分问题，支持向量只可能从凸包顶点集中产生。 寻找到凸包顶点集就能获得SVM约简训练集。当待分类样本间呈现交叠状态，即线性不可分时，部分 凸包顶点落入了对方样本的凸包

4、空间，除了顶点向量之 外，交叠域中的部分样本也对分类起着关键作用。Step1： 分别计算正负类样本的空间几何凸包，分别 获取顶点向量集。Step2: 判断两个正负类样本的凸包是否相交，如果 相交，分别从正负类样本的原始样本集中去 除步骤1中获取的顶点向量。Step3: 重复步骤1，直到两个凸包不再相交。以每次迭代计算中获得的顶点向量集可以有效构建 约简SVM训练样本集。正类正类负类负类基于凸包顶点构建的约简SVM训练集，能准确的获取了SVM分类所需的关键向量，使标准支持向量机在训练阶段的时空复杂度大大降低 ，而无有效分类信息损失。. . .凸包具有天然的分治特性：conv(L)=conv(A

5、B) = conv(vert(conv(A) B) = conv(A vert(conv(B)= conv(vert(conv(A) vert(conv(B)A, B 和L 是样本集，L= A B, vert(conv(A), vert(conv(B) 分别代表凸包conv(A)和conv(B)的顶点集。也就是说，如果将原始点集划分为若干子集，分别计算这些子集的最小凸包，在这些子凸包顶点集上形成的凸包，与在原始点集上形成的凸包是等效的。 建立一个分类精度高，推广能力好的异常检测分类器步骤建立一个分类精度高，推广能力好的异常检测分类器步骤E(P): 经验风险值，经验风险值，Err：错误率：错误率

6、模模型型选选择择参参数数选选择择在GPU并行计算中，各并行算法的设计和移植是关键，涉及： 1）基于欧式距离的样本初选算法 2）凸包并行计算算法 3）SVM分类测试算法2010.12010.6 (1) 研究约简SVM快速智能分类算法。(2) 研究高维凸包计算和分解算法。2010.72010.12 (1)在GPU上的实现基于距离的样本初选算法。(2)在GPU上实现SVM分类测试算法。 2011.12011.6 (1) 在GPU上的实现凸包分解计算算法。 (2) 针对目标数据集，研究支持向量机模型优化。2011.72011.12 (1) 在入侵检测海量数据集上，实验验证和完善基于 GPU并行计算和约

7、简SVM的快速入侵检测算法。(2) 总结、完善、撰写研究报告、论文。 合合 计计出版出版发表费发表费会议及会议及调研费调研费材料材料、图图书资料费书资料费其他其他经费经费合计合计31.410.30.32010年年1.50.70.50.20.12011年年1.50.70.50.10.2线程分配模型多级存储器模型 David Kirk/NVIDIA and Wen-mei W. HwuTaiwan, June 30-July 2, 200838DeviceGrid 1Block(0, 0)Block(1, 0)Block(2, 0)Block(0, 1)Block(1, 1)Block(2, 1)

8、Block (1, 1)Thread(0, 1)Thread(1, 1)Thread(2, 1)Thread(3, 1)Thread(4, 1)Thread(0, 2)Thread(1, 2)Thread(2, 2)Thread(3, 2)Thread(4, 2)Thread(0, 0)Thread(1, 0)Thread(2, 0)Thread(3, 0)Thread(4, 0)Courtesy: NDVIA David Kirk/NVIDIA and Wen-mei W. HwuTaiwan, June 30-July 2, 200839nEach block can execute in

9、 any order relative to other blocs!CUDA Thread BlockThread Id #:0 1 2 3 m Thread programCourtesy: John Nickolls, NVIDIA David Kirk/NVIDIA and Wen-mei W. HwuTaiwan, June 30-July 2, 200840DeviceBlock 0Block 1Block 2Block 3Block 4Block 5Block 6Block 7Kernel gridBlock 0Block 1Block 2Block 3Block 4Block

10、5Block 6Block 7DeviceBlock 0Block 1Block 2Block 3Block 4Block 5Block 6Block 7Each block can execute in any order relative to other blocks. time David Kirk/NVIDIA and Wen-mei W. HwuTaiwan, June 30-July 2, 200841nSM maintains thread/block id #snSM manages/schedules thread executiont0 t1 t2 tmBlocksSPS

11、haredMemoryMT IUSPSharedMemoryMT IUt0 t1 t2 tmBlocksSM 1SM 0 David Kirk/NVIDIA and Wen-mei W. HwuTaiwan, June 30-July 2, 200842Each Block is executed as 32-thread WarpsAn implementation decision, not part of the CUDA programming modelWarps are scheduling units in SMIf 3 blocks are assigned to an SM and each block has 256 threads, how many Warps are there in an SM?Each Block is divided into 256/32 = 8 WarpsThere are 8 * 3 = 24 Warps At any point in time, only one of the 24 Warps will be selected f