基于GPU并行計算的快速智能入侵檢測技術(shù)研究

1、入侵檢測系統(tǒng)（Intrusion Detection System, IDS）作為保障網(wǎng)絡(luò)和主機安全的重要手段，一直是研究者和工業(yè)界的關(guān)注熱點。根據(jù)數(shù)據(jù)源不同可以分為： HIDS 和 NIDS 根據(jù)入侵檢測技術(shù)不同入侵檢測分為： 異常檢測 和 誤用檢測 1）對未知攻擊的有效檢測： 目前商業(yè)入侵檢測系統(tǒng)中大量使用的是基于模式 匹配的誤用檢測方法，只能檢測出已知攻擊，不 能檢測到新的攻擊類型。2）高速環(huán)境下的檢測： 高速大流量網(wǎng)絡(luò)數(shù)據(jù)使智能IDS在建模和檢測階 段均面臨巨大的數(shù)據(jù)運算和分析壓力，容易產(chǎn)生 大量漏報、誤報。針對問題 1）：針對問題 2）：支持向量機 ( Support Vector

2、Machines, SVM)是20 世紀(jì)90年代發(fā)展起來的一種新的機器學(xué)習(xí)方法。它基于結(jié)構(gòu)風(fēng)險最小化原理，能夠有效地避免經(jīng) 典學(xué)習(xí)方法中出現(xiàn)的過學(xué)習(xí)、欠學(xué)習(xí)、維數(shù)災(zāi)難 以及陷入局部極小點等諸多問題。在入侵檢測上有不少學(xué)者開展了研究，得到了初 步成功的結(jié)果 。考慮給定的訓(xùn)練樣本集 L: (x1, y1)， ，(xN, yN)，x Rd，y+1,-1， N為樣本數(shù)，d為輸入維數(shù)，x為 輸入數(shù)據(jù)， y為輸出數(shù)據(jù)。如果y的值為“1”，表示對應(yīng)的樣本為正常樣本，如果y的值為 “-1”，表示對應(yīng)的樣本為異常樣本，即有入侵發(fā)生。根據(jù)支持向量機理論，對于待分類樣本存在一個最優(yōu)分類超平面，使得兩類樣本以最大距離

3、被完全分開。 求解該超平面可以看成解如下問題： ， 是拉格朗日乘子，對應(yīng)于 0 的向量稱為支持向量。 K( xi, x )為核函數(shù)。 求解該問題，得到最優(yōu)分類函數(shù)： 由SVM的理論可以知道： SVM最優(yōu)分類面的位置僅由支持向量來決定，而 與非支持向量無關(guān)。在SVM分類中，只有那些在兩類樣本相鄰邊界或 附近的向量才有可能成為支持向量。在特征空間中，待分類的每一類樣本都由它的凸包包圍。 凸包是包含數(shù)據(jù)集中所有樣本的最小凸多面體。對線性可分問題，支持向量只可能從凸包頂點集中產(chǎn)生。 尋找到凸包頂點集就能獲得SVM約簡訓(xùn)練集。當(dāng)待分類樣本間呈現(xiàn)交疊狀態(tài)，即線性不可分時，部分 凸包頂點落入了對方樣本的凸包

4、空間，除了頂點向量之 外，交疊域中的部分樣本也對分類起著關(guān)鍵作用。Step1： 分別計算正負(fù)類樣本的空間幾何凸包，分別 獲取頂點向量集。Step2: 判斷兩個正負(fù)類樣本的凸包是否相交，如果 相交，分別從正負(fù)類樣本的原始樣本集中去 除步驟1中獲取的頂點向量。Step3: 重復(fù)步驟1，直到兩個凸包不再相交。以每次迭代計算中獲得的頂點向量集可以有效構(gòu)建 約簡SVM訓(xùn)練樣本集。正類正類負(fù)類負(fù)類基于凸包頂點構(gòu)建的約簡SVM訓(xùn)練集，能準(zhǔn)確的獲取了SVM分類所需的關(guān)鍵向量，使標(biāo)準(zhǔn)支持向量機在訓(xùn)練階段的時空復(fù)雜度大大降低 ，而無有效分類信息損失。. . .凸包具有天然的分治特性：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): 經(jīng)驗風(fēng)險值，經(jīng)驗風(fēng)險值，Err：錯誤率：錯誤率

6、模模型型選選擇擇參參數(shù)數(shù)選選擇擇在GPU并行計算中，各并行算法的設(shè)計和移植是關(guān)鍵，涉及： 1）基于歐式距離的樣本初選算法 2）凸包并行計算算法 3）SVM分類測試算法2010.12010.6 (1) 研究約簡SVM快速智能分類算法。(2) 研究高維凸包計算和分解算法。2010.72010.12 (1)在GPU上的實現(xiàn)基于距離的樣本初選算法。(2)在GPU上實現(xiàn)SVM分類測試算法。 2011.12011.6 (1) 在GPU上的實現(xiàn)凸包分解計算算法。 (2) 針對目標(biāo)數(shù)據(jù)集，研究支持向量機模型優(yōu)化。2011.72011.12 (1) 在入侵檢測海量數(shù)據(jù)集上，實驗驗證和完善基于 GPU并行計算和約

7、簡SVM的快速入侵檢測算法。(2) 總結(jié)、完善、撰寫研究報告、論文。 合合 計計出版出版發(fā)表費發(fā)表費會議及會議及調(diào)研費調(diào)研費材料材料、圖圖書資料費書資料費其他其他經(jīng)費經(jīng)費合計合計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