吳華勛

（福建省郵電學(xué)校，福建 福州 350008）

計(jì)算機(jī)網(wǎng)絡(luò)極大地改變了人們的生活方式，提升了生產(chǎn)效率。但是由于計(jì)算機(jī)網(wǎng)絡(luò)的覆蓋范圍大、信息交換量高，給計(jì)算機(jī)網(wǎng)絡(luò)安全帶來了隱患[1]。很多黑客以計(jì)算機(jī)網(wǎng)絡(luò)為目標(biāo)，通過入侵計(jì)算機(jī)網(wǎng)絡(luò)獲取信息謀取私人利益。計(jì)算機(jī)網(wǎng)絡(luò)安全的一項(xiàng)重要內(nèi)容，就是對(duì)黑客的入侵行為進(jìn)行檢測(cè)，即入侵檢測(cè)[2]。入侵檢測(cè)發(fā)現(xiàn)入侵行為即可以調(diào)度防御算法，抵御黑客的進(jìn)一步入侵，保護(hù)計(jì)算機(jī)網(wǎng)絡(luò)的安全。入侵檢測(cè)算法的核心是字符匹配機(jī)制，通過各種規(guī)則的設(shè)計(jì)和匹配算法，找到具有入侵行為特征的程序[3]。該文進(jìn)一步改進(jìn)鮑威爾入侵檢測(cè)算法，希望建立一種效果更好的入侵檢測(cè)算法。

1 鮑威爾算法及其改進(jìn)

1.1 鮑威爾入侵檢測(cè)算法

鮑威爾算法的實(shí)質(zhì)是一種字符匹配算法，最早出現(xiàn)于字符比較、字符串相似性判斷的研究工作中。在這個(gè)標(biāo)準(zhǔn)字符串中，配置兩個(gè)關(guān)鍵詞符，一個(gè)是“Good”字符，一個(gè)是“Bad”字符。然后，將待匹配的字符串和這個(gè)標(biāo)準(zhǔn)字符串進(jìn)行比較。比較的順序，是沿著字符串長(zhǎng)度方向上，從左到右的執(zhí)行。在匹配過程中，通過和關(guān)鍵詞符即“Good”字符、“Bad”字符的比較，確定匹配是否成功，匹配結(jié)果可以用于是否發(fā)生入侵行為的判定。

圖1就給出了有關(guān)標(biāo)準(zhǔn)字符串和待匹配字符串匹配過程的描述。

從圖1中可以看出，圖1（a）中用B表示的字符串就是標(biāo)準(zhǔn)字符串，用T表示的字符串就是匹配字符串?！癇ad”字符在字符串中用h表示，關(guān)鍵后綴用字符z表示。

圖1（b）表示了標(biāo)準(zhǔn)串中不含有“Bad”字符的情況，匹配過程會(huì)將標(biāo)準(zhǔn)字符串直接移動(dòng)到字符h之后。

圖1（c）表示了標(biāo)準(zhǔn)串中含有“Bad”字符的情況，匹配過程會(huì)將標(biāo)準(zhǔn)字符串直接移動(dòng)到字符h所對(duì)應(yīng)的位置上。

圖1 鮑威爾算法中字符串的匹配過程

關(guān)鍵后綴z在鮑威爾算法中扮演了非常重要的角色，用于引導(dǎo)鮑威爾算法完成整個(gè)匹配過程。在匹配的執(zhí)行過程中，字符串之間會(huì)出現(xiàn)有一部分匹配、另一部分不匹配的情況。通過記錄匹配位置和匹配長(zhǎng)度，可以找到匹配長(zhǎng)度最長(zhǎng)的字串，進(jìn)而根據(jù)后綴字符z進(jìn)行移動(dòng)處理。這里的操作包括以下3種情況：第一種情況，標(biāo)準(zhǔn)字符串中還存在其他子串中也包括關(guān)鍵后綴的情況，這時(shí)可以通過移動(dòng)這些子串使其到達(dá)和關(guān)鍵后綴對(duì)齊的位置。這時(shí)的具體操作，可以參考圖2（a）。第二種情況，標(biāo)準(zhǔn)字符串中沒有其他子串包括關(guān)鍵后綴的情況，這時(shí)需要在標(biāo)準(zhǔn)字符串的前綴子串中進(jìn)行進(jìn)一步尋找，如果能找到這樣的前綴，使其和關(guān)鍵后綴對(duì)齊即可。第三種情況，標(biāo)準(zhǔn)字符串中既沒有包括關(guān)鍵后綴的其他子串，也找不到包括關(guān)鍵后綴的前綴子串，這時(shí)只能將整個(gè)標(biāo)準(zhǔn)字符串移動(dòng)到關(guān)鍵后綴再后面一個(gè)字符的位置，這時(shí)的具體操作，可以參考圖2（b）。

圖2 關(guān)鍵后綴引導(dǎo)的匹配過程所發(fā)生的不同情況

在鮑威爾算法中，采用關(guān)鍵后綴完成匹配過程的引導(dǎo)一般通過配置一個(gè)數(shù)組來實(shí)現(xiàn)，這個(gè)數(shù)組及數(shù)組滿足的關(guān)系如公式（1）所示。

式中：參數(shù)k表示了一個(gè)長(zhǎng)度，這個(gè)長(zhǎng)度是和標(biāo)準(zhǔn)字符串相匹配的字符串的最大長(zhǎng)度；參數(shù)i表示字符串中的位；Datagroup表示字符數(shù)組。

根據(jù)這個(gè)公式所表達(dá)的內(nèi)容，關(guān)鍵后綴引導(dǎo)下的鮑威爾算法執(zhí)行的匹配過程在數(shù)學(xué)上的形式如式（2）所示：

式中：參數(shù)B表示標(biāo)準(zhǔn)字符串；參數(shù)i、m表示字符串中的位；參數(shù)k表示長(zhǎng)度。

1.2 鮑威爾算法的改進(jìn)處理

通過鮑威爾算法的原理分析可知，鮑威爾算法匹配準(zhǔn)確率與最大移動(dòng)距離直接相關(guān)。如果能進(jìn)一步增大移動(dòng)距離，不僅會(huì)提升匹配準(zhǔn)確率，也會(huì)減少匹配次數(shù)，從而提升鮑威爾算法的執(zhí)行效率?；诖?，該文對(duì)鮑威爾算法的改進(jìn)，確定了進(jìn)一步增大移動(dòng)距離的思路。

根據(jù)鮑威爾算法的兩種策略，首先得到一個(gè)初始的最大移動(dòng)距離MobileLength1。在此基礎(chǔ)上，將匹配字符串中兩個(gè)臨近字符T[k+1]和T[k+2]組合匹配，從而可以得到一個(gè)新的最大移動(dòng)距離MobileLength2。通過比較新的最大移動(dòng)距離和初始最大移動(dòng)距離，選取匹配算法實(shí)際采用的最大移動(dòng)距離。

該文改進(jìn)的鮑威爾算法的執(zhí)行過程一共包括以下5個(gè)步驟。

第一個(gè)步驟，構(gòu)建一個(gè)新的數(shù)組用于計(jì)數(shù)統(tǒng)計(jì)，它主要負(fù)責(zé)記錄每個(gè)字符在標(biāo)準(zhǔn)字符串中一共出現(xiàn)了幾次，這個(gè)數(shù)組的數(shù)學(xué)形式如式（3）所示：

式中：參數(shù)Btime（char）表示了任意一個(gè)字符在標(biāo)準(zhǔn)字符串中出現(xiàn)的次數(shù)。根據(jù)公式（3）可以看出，如果任意一個(gè)字符在標(biāo)準(zhǔn)字符串中出現(xiàn)的次數(shù)恰好為1，那么數(shù)組就記錄為1；如果任意一個(gè)字符在標(biāo)準(zhǔn)字符串中出現(xiàn)的次數(shù)大于1，那么數(shù)組就記錄為0。

第二個(gè)步驟，結(jié)合匹配字符串的具體情況，組合T[k+2]和T[k+2]并提取相鄰字符，提取后的結(jié)果納入char（1，2），之后將char（1，2）和標(biāo)準(zhǔn)字符串進(jìn)行相似性比較。

第三個(gè)步驟，如果標(biāo)準(zhǔn)字符串中并不含有char（1，2）一樣的子串，再將char（1，2）和標(biāo)準(zhǔn)字符串中的首字符比較一次。如果char（1，2）也不含有標(biāo)準(zhǔn)字符串中的首字符B[1]，這時(shí)MobileLength2的大小記錄為m+2；如果char（1，2）中的首字符和標(biāo)準(zhǔn)字符串中的首字符B[1]一致，這時(shí)MobileLength2的大小也記錄為m+2；如果char（1，2）中的次字符和標(biāo)準(zhǔn)字符串中的首字符B[1]一致，這時(shí)MobileLength2的大小記錄為m+1。

第四個(gè)步驟，如果標(biāo)準(zhǔn)字符串中存在與char（1，2）一致的子串，同時(shí)char（1，2）中沒有和標(biāo)準(zhǔn)字符串首字符B[1]一致的字符，并且Dtime（char）=1，這時(shí)MobileLength2的大小記錄為m+2。

第五個(gè)步驟，如果標(biāo)準(zhǔn)字符串中存在與char（1，2）一致的子串，同時(shí)char（1，2）中沒有和標(biāo)準(zhǔn)字符串首字符B[1]一致的字符，并且Dtime（char）=0，這時(shí)MobileLength2的大小和MobileLength1一致。MobileLength1的大小按照公式（4）進(jìn)行計(jì)算：

式中：參數(shù)B表示標(biāo)準(zhǔn)字符串；參數(shù)i、m表示字符串中的位；參數(shù)k表示長(zhǎng)度；MobileLength表示移動(dòng)長(zhǎng)度。

2 改進(jìn)鮑威爾算法的計(jì)算機(jī)網(wǎng)絡(luò)入侵檢測(cè)試驗(yàn)

該文通過詳細(xì)的改進(jìn)設(shè)計(jì)，改變了鮑威爾算法的執(zhí)行過程。為了驗(yàn)證這種改進(jìn)處理所達(dá)到的效果，該文進(jìn)一步進(jìn)行計(jì)算機(jī)網(wǎng)絡(luò)入侵檢測(cè)試驗(yàn)。檢測(cè)試驗(yàn)中所使用的計(jì)算機(jī)CPU為雙核配置，單核主頻為3.0GHz。操作系統(tǒng)選擇了Windows10.0系統(tǒng)，選擇的計(jì)算機(jī)網(wǎng)絡(luò)入侵檢測(cè)系統(tǒng)為斯諾特檢測(cè)平臺(tái)。

選擇斯諾特檢測(cè)平臺(tái)的原因在于其突出的開源特征。這種開源的設(shè)計(jì)，可以便捷地加入自己設(shè)計(jì)的程序和代碼。在該文的驗(yàn)證試驗(yàn)中加入了自己設(shè)計(jì)的檢測(cè)算法，然后從斯諾特平臺(tái)的主函數(shù)中加以調(diào)用，就可以進(jìn)行入侵檢測(cè)試驗(yàn)和算法性能驗(yàn)證了。

在試驗(yàn)過程中，選擇了傳統(tǒng)的鮑威爾算法和該文改進(jìn)處理后的鮑威爾算法，方便比較改進(jìn)前后的算法性能。

在試驗(yàn)過程中，設(shè)置了隨機(jī)長(zhǎng)度的100個(gè)字符串，作為鮑威爾算法和改進(jìn)鮑威爾算法的檢測(cè)樣本。這些字符串長(zhǎng)度不一，構(gòu)成也沒有具體的規(guī)律。受到篇幅的限制，該文給出了前6個(gè)字符串的效果，見表1。

表1 100個(gè)隨機(jī)字符串中的前6個(gè)樣本

為了客觀地評(píng)價(jià)兩種算法的性能，整個(gè)試驗(yàn)過程進(jìn)行三項(xiàng)試驗(yàn)。其中，第一項(xiàng)試驗(yàn)就是比較鮑威爾算法和改進(jìn)鮑威爾算法的字符匹配次數(shù)，這一結(jié)果的示例如圖3所示。

從圖3給出的第一組試驗(yàn)的比較結(jié)果可以明顯看出，在入侵檢測(cè)算法的字符比較次數(shù)方面，該文提出的改進(jìn)鮑威爾算法的比較次數(shù)明顯低于鮑威爾算法的比較次數(shù)。從兩條曲線的對(duì)比情況可以看出，隨著字符串長(zhǎng)度不斷變長(zhǎng)，字符比較次數(shù)都有明顯的下降，但該文提出的改進(jìn)鮑威爾算法下降速度更快。

圖3 第一組試驗(yàn)的比較結(jié)果

進(jìn)一步比較鮑威爾算法和改進(jìn)鮑威爾算法的窗口移動(dòng)次數(shù)，這一結(jié)果的示例如圖4所示。

從圖4給出的第二組試驗(yàn)的比較結(jié)果可以明顯看出，在入侵檢測(cè)算法的窗口移動(dòng)次數(shù)方面，該文提出的改進(jìn)鮑威爾算法的移動(dòng)次數(shù)明顯低于鮑威爾算法的移動(dòng)次數(shù)。從兩條曲線的對(duì)比情況可以看出，隨著字符串長(zhǎng)度不斷變長(zhǎng)，窗口移動(dòng)次數(shù)都有明顯的下降，但該文提出的改進(jìn)鮑威爾算法下降速度更快。

圖4 第二組試驗(yàn)的比較結(jié)果

進(jìn)一步比較鮑威爾算法和改進(jìn)鮑威爾算法的執(zhí)行時(shí)間，這一結(jié)果的示例如圖5所示。

從圖5給出的第三組試驗(yàn)的比較結(jié)果可以明顯看出，在入侵檢測(cè)算法的執(zhí)行時(shí)間方面，該文提出的改進(jìn)鮑威爾算法的執(zhí)行時(shí)間明顯低于鮑威爾算法的執(zhí)行時(shí)間。從5組對(duì)比結(jié)果可以看出，隨著數(shù)據(jù)包大小的增加，執(zhí)行時(shí)間都有所增加，但改進(jìn)鮑威爾算法的執(zhí)行時(shí)間增加的更慢。

圖5 第三組試驗(yàn)的比較結(jié)果

3 結(jié)論

計(jì)算機(jī)網(wǎng)絡(luò)安全是計(jì)算機(jī)網(wǎng)絡(luò)領(lǐng)域中的研究熱點(diǎn)，入侵檢測(cè)算法是保護(hù)計(jì)算機(jī)網(wǎng)絡(luò)安全的重要手段。該文針對(duì)鮑威爾入侵檢測(cè)算法進(jìn)行改進(jìn)，提出了一種新的入侵檢測(cè)算法。在該算法中，通過組合字符的使用提升匹配準(zhǔn)確率，通過三種策略調(diào)整最大移動(dòng)長(zhǎng)度，使其更符合檢測(cè)過程的需要。試驗(yàn)結(jié)果表明，改進(jìn)鮑威爾算法具有更少的比較和移動(dòng)次數(shù)，算法的執(zhí)行時(shí)間也更低，可以提升計(jì)算機(jī)網(wǎng)絡(luò)入侵檢測(cè)的效果。