基于改進(jìn)Apriori 算法的鐵路網(wǎng)絡(luò)安全預(yù)警方法研究

崔偉健，馬小寧，孫思齊

（1.中國鐵道科學(xué)研究院，北京 100081；2.中國鐵道科學(xué)研究院 電子計(jì)算技術(shù)研究所，北京 100081）

隨著鐵路信息化的快速發(fā)展，鐵路各業(yè)務(wù)系統(tǒng)已高度依賴信息技術(shù)，隨之而來的網(wǎng)絡(luò)安全形勢也日趨嚴(yán)峻，從簡單的網(wǎng)絡(luò)安全攻擊試探、網(wǎng)頁掛馬篡改，到有組織、大規(guī)模的DDos 攻擊、APT（Advanced Persistent Threat）攻擊等，對鐵路信息系統(tǒng)穩(wěn)定運(yùn)行和各項(xiàng)業(yè)務(wù)穩(wěn)定開展帶來了嚴(yán)重威脅，甚至?xí)绊戣F路行車安全和人民生命財(cái)產(chǎn)安全[1]。近年來，鐵路大力發(fā)展網(wǎng)絡(luò)安全建設(shè)，初步建成網(wǎng)絡(luò)安全防護(hù)體系，但網(wǎng)絡(luò)安全建設(shè)工作起步較晚，目前，安全防護(hù)仍停留在常規(guī)保障、事后處理階段，尚未建成行之有效的行業(yè)網(wǎng)絡(luò)安全預(yù)警體系。

在食品衛(wèi)生、公路交通、電網(wǎng)電力等行業(yè)，已開展了網(wǎng)絡(luò)安全預(yù)警技術(shù)研究[2-4]，還有一些學(xué)者對自修正系數(shù)、異常流量分析、DDos 攻擊分析等網(wǎng)絡(luò)安全預(yù)警方法開展研究[5-7]，在鐵路網(wǎng)絡(luò)安全領(lǐng)域，針對系統(tǒng)、流量的網(wǎng)絡(luò)安全預(yù)警方法研究相對較多，如基于網(wǎng)閘技術(shù)的高速鐵路地震預(yù)警[8]、車貨實(shí)時(shí)追蹤預(yù)警[9]、基于大數(shù)據(jù)技術(shù)的網(wǎng)絡(luò)安全態(tài)勢感知[10]等，但從鐵路網(wǎng)絡(luò)安全合規(guī)測評角度開展網(wǎng)絡(luò)安全預(yù)警的研究相對較少，在鐵路大力發(fā)展網(wǎng)絡(luò)安全測評和大數(shù)據(jù)建設(shè)的背景下，結(jié)合網(wǎng)絡(luò)安全測評工作實(shí)際，研究基于大數(shù)據(jù)技術(shù)的網(wǎng)絡(luò)安全預(yù)警方法具有較強(qiáng)的現(xiàn)實(shí)意義。

目前，Apriori 算法在鐵路網(wǎng)絡(luò)安全預(yù)測與感知[11-12]中應(yīng)用較為廣泛，且應(yīng)用效果已得到廣泛認(rèn)可。本文分析了Apriori 算法特性，提出了一種改進(jìn)的Apriori 算法，結(jié)合鐵路某單位實(shí)際案例，對算法應(yīng)用進(jìn)行驗(yàn)證。研究表明，改進(jìn)的Apriori 算法在鐵路網(wǎng)絡(luò)安全預(yù)警工作中有較高的應(yīng)用價(jià)值。

1 Apriori 算法及改進(jìn)

1.1 術(shù)語定義

下面給出Apriori 算法中涉及的部分術(shù)語定義。

（1）支持度和最小支持度：初始數(shù)據(jù)中包含某一項(xiàng)集的比例，用S%表示；在計(jì)算中，需滿足的支持度的最小值記為最小支持度，用min_Sup表示。

（2）置信度和最小置信度：在迭代過程中，當(dāng)前項(xiàng)集與其前一層相關(guān)子項(xiàng)集支持度的比例，用C%表示；在計(jì)算中，需滿足的置信度的最小值記為最小置信度，用min_Con表示。

（3）候選項(xiàng)集：在迭代過程中，包含當(dāng)前層所有項(xiàng)集的集合，用Ck表示。

（4）頻繁項(xiàng)集：在迭代過程中，滿足最小支持度項(xiàng)集的集合，用Lk表示。

（5）最大頻繁項(xiàng)集：如果頻繁項(xiàng)集Lk的所有超集都是非頻繁項(xiàng)集，那么當(dāng)前頻繁項(xiàng)集Lk即為最大頻繁項(xiàng)集，用MFI表示。

1.2 Apriori 算法

Apriori 算法核心是逐層搜索迭代，在每一層迭代中，由候選項(xiàng)集Ck（k=1,2,···,n）生成頻繁項(xiàng)集Lk，在層間迭代中，由當(dāng)前層頻繁項(xiàng)集Lk生成下一層候選項(xiàng)集Ck+1，通過有限次數(shù)的迭代后，找出數(shù)據(jù)中隱含的最大頻繁項(xiàng)集。

設(shè)I={i1,i2,···,im}為所有項(xiàng)目的集合，T是一個(gè)由項(xiàng)目組成的集合，且滿足T?I；項(xiàng)目數(shù)據(jù)庫D為T的集合，滿足D={T1,T2,···,Tn}，|D|是D的總項(xiàng)目數(shù)。設(shè)X，Y為I中項(xiàng)的集合，滿足X?I,Y?I，關(guān)聯(lián)規(guī)則就是形如X?Y的邏輯蘊(yùn)含關(guān)系，且X∩Y=?。

根據(jù)上述可以得到一個(gè)關(guān)聯(lián)規(guī)則X?Y(S%,C%)，其中，S%為滿足條件的項(xiàng)目占總項(xiàng)目數(shù) |D|的比例，即支持度，計(jì)算公式如式（1）：

C%為D中包含X項(xiàng)目又包含Y項(xiàng)目的比例，即置信度，計(jì)算公式如式（2）：

Apriori 算法流程如圖1 所示。

圖1 Apriori 算法流程

Apriori 算法雖然應(yīng)用廣泛，但每層迭代計(jì)算都需對數(shù)據(jù)庫進(jìn)行多次掃描，數(shù)據(jù)量級大時(shí)存在數(shù)據(jù)庫掃描頻率高、算法效率低、會(huì)產(chǎn)生大量中間項(xiàng)集等不足。

1.3 Apriori 算法改進(jìn)思路

許多學(xué)者對Apriori 算法優(yōu)化進(jìn)行了研究，如張雷[13]等人在基于改進(jìn)Apriori 算法的客戶需求數(shù)據(jù)分析方法中，提出基于布爾矩陣的改進(jìn)Apriori 算法，胡世昌[14]等人研究提出基于二進(jìn)制編碼的改進(jìn)Apriori 算法，殷茗[15]等人提出基于鄰接表的改進(jìn)Apriori 算法，陳江平[16]等人提出利用概率方法改進(jìn)的Apriori 算法。各類改進(jìn)的Apriori 算法均實(shí)現(xiàn)了降耗提效，取得了一定效果。

本文從最大頻繁項(xiàng)集的性質(zhì)著手，研究提出一種Apriori 算法改進(jìn)方法。根據(jù)傳統(tǒng)Apriori 算法，最大頻繁項(xiàng)集必定存在下述3 個(gè)性質(zhì)：

（1）最大頻繁項(xiàng)集必為N個(gè)事務(wù)集的交集，且N≥min_S up_N，其中，min_Sup_N為最小支持?jǐn)?shù)，其值為事務(wù)集個(gè)數(shù)與最小支持度的乘積向上取整；

（2）最大頻繁項(xiàng)集支持度一定小于或等于其他頻繁項(xiàng)集支持度；

（3）最大頻繁項(xiàng)集中所含元素項(xiàng)個(gè)數(shù)必定大于或等于其他頻繁項(xiàng)集中元素項(xiàng)個(gè)數(shù)。

根據(jù)上述性質(zhì)，可以得出以下2 個(gè)推論：

（1）最大頻繁項(xiàng)集可由min_Sup_N個(gè)事務(wù)集求交集得出；

（2）任意min_Sup_N個(gè)事務(wù)集求交集結(jié)果中，所含元素項(xiàng)個(gè)數(shù)最多的項(xiàng)集一定是最大頻繁項(xiàng)集。

根據(jù)上述推論，可以得出Apriori 算法改進(jìn)思路，即通過求交集運(yùn)算方式找出數(shù)據(jù)中的最大頻繁項(xiàng)集。

1.4 改進(jìn)的Apriori 算法

預(yù)設(shè)項(xiàng)目集合I，事務(wù)集合T，項(xiàng)目數(shù)據(jù)庫D，最小支持度min_Sup并計(jì)算出min_Sup_N，則單次交集計(jì)算公式如式（3）：

式（3）中，intersection表示求交集運(yùn)算，Ti，Tj，Tk，···為參與計(jì)算的事務(wù)集，滿足i≠j≠k≠···，總數(shù)為min_Sup_N個(gè)，Qm為所求交集結(jié)果，通過不斷交集計(jì)算，找出含元素項(xiàng)個(gè)數(shù)最多的Qm，或Qm的集合，即為所求最大頻繁項(xiàng)集。

改進(jìn)的Apriori 算法流程如圖2 所示。

圖2 改進(jìn)的Apriori 算法流程

2 改進(jìn)的Apriori 算法性能分析

與常規(guī)的正向推演、過程優(yōu)化的改進(jìn)方式不同，本文從最大頻繁項(xiàng)集性質(zhì)入手，對算法運(yùn)算過程進(jìn)行改進(jìn)，與傳統(tǒng)Apriori 算法相比，優(yōu)化了逐層迭代過程，在數(shù)據(jù)庫掃描頻率、計(jì)算復(fù)雜度、臨時(shí)存儲(chǔ)空間占用等方面有明顯改善。

2.1 數(shù)據(jù)庫掃描頻率和計(jì)算穩(wěn)定度分析

在數(shù)據(jù)庫掃描方面，傳統(tǒng)Apriori 算法每層迭代都要遍歷數(shù)據(jù)庫，而改進(jìn)的Apriori 算法將原始數(shù)據(jù)映射至緩存矩陣中，在計(jì)算過程中，僅遍歷一次數(shù)據(jù)庫即可，數(shù)據(jù)庫掃描頻率顯著降低，數(shù)據(jù)庫I/O 耗能明顯減少。

在計(jì)算穩(wěn)定度方面，傳統(tǒng)Apriori 算法在計(jì)算過程中會(huì)不斷剪枝，因此，計(jì)算穩(wěn)定度與初始矩陣維數(shù)、初始數(shù)據(jù)稠密程度、剪枝條件關(guān)系較大，而改進(jìn)的Apriori 算法計(jì)算量僅與初始數(shù)據(jù)維數(shù)、最小支持度有關(guān)，算法計(jì)算穩(wěn)定度相對較高。

2.2 計(jì)算時(shí)間和復(fù)雜度分析

設(shè)n為事務(wù)集T的數(shù)量，m為每個(gè)事務(wù)集T的平均項(xiàng)目數(shù)，q為滿足min_Sup的頻繁項(xiàng)集元素個(gè)數(shù)最大值，tD為掃描初始數(shù)據(jù)元素項(xiàng)所需時(shí)間，ta為掃描數(shù)組每個(gè)元素所需時(shí)間，tc為每次進(jìn)行簡單四則運(yùn)算所需時(shí)間，tapriori和tnew_apriori分別代表傳統(tǒng)和改進(jìn)后Apriori 算法計(jì)算出滿足min_Sup的頻繁項(xiàng)集所需時(shí)間。

（1）tapriori時(shí)間性能分析

對于tapriori，由于傳統(tǒng)Apriori 算法在運(yùn)算過程中不斷進(jìn)行剪枝操作，對初始數(shù)據(jù)較為敏感，初始數(shù)據(jù)矩陣較為稀疏時(shí)，逐層迭代過程中剪枝量相對較大，到下一個(gè)迭代層，運(yùn)算量較低。而初始數(shù)據(jù)矩陣較為稠密時(shí)，其剪枝量相對較小，此時(shí)算法運(yùn)算量在前幾層迭代中會(huì)逐層遞加，最終總運(yùn)算量也會(huì)相對較大，傳統(tǒng)Apriori 算法的計(jì)算復(fù)雜度不穩(wěn)定性在后續(xù)仿真實(shí)驗(yàn)中也進(jìn)行了驗(yàn)證。另外，傳統(tǒng)Apriori 算法對min_Sup也比較敏感，min_Sup越大，算法迭代次數(shù)越多，數(shù)據(jù)庫I/O 次數(shù)越多，消耗的tD及運(yùn)算次數(shù)也相對越大。

（2）tnew_apriori時(shí)間性能分析

對于tnew_apriori，需要計(jì)算次交集，由于項(xiàng)目矩陣行元素項(xiàng)均為順序排列，且對應(yīng)元素項(xiàng)在同一列，故在計(jì)算min_Sup_N個(gè)矩陣交集時(shí)，僅需對各矩陣對應(yīng)列元素項(xiàng)進(jìn)行求與操作即可，結(jié)果為1，證明該元素項(xiàng)為交集元素；為0，則證明不是交集元素。最終計(jì)算次數(shù)近似為 (min_Sup_N-1)·n，因此，tnew_apriori的計(jì)算公式如式（4）：

從式（4）中可以看出，tnew_apriori與m、min_Sup_N關(guān)聯(lián)度較大，在實(shí)際應(yīng)用過程中，m的值在某一段時(shí)期內(nèi)是固定的，因此，tnew_apriori與min_Sup_N關(guān)聯(lián)度最大，且為正相關(guān)關(guān)系。

綜合來看，改進(jìn)的Apriori 算法更加穩(wěn)定，在n、m、min_Sup值較大時(shí)，改進(jìn)算法綜合性能更優(yōu)。

2.3 空間性能分析

傳統(tǒng)Apriori 算法對存儲(chǔ)空間需求非常大，若初始元素個(gè)數(shù)為10 000，在第2 輪迭代中，生成的含2個(gè)元素項(xiàng)的候選項(xiàng)集個(gè)數(shù)會(huì)接近108個(gè)，雖然中間會(huì)進(jìn)行部分裁剪，但依然會(huì)消耗大量存儲(chǔ)空間。改進(jìn)的Apriori 算法對空間需求有限，僅需預(yù)設(shè)一個(gè)映射矩陣I，以及一個(gè)緩存矩陣S，所需存儲(chǔ)空間與中間頻繁項(xiàng)集數(shù)量有關(guān)，但由于產(chǎn)生的中間頻繁項(xiàng)集數(shù)量相對較少，故所需空間也較小。因此，改進(jìn)的Apriori 算法在空間性能上明顯占優(yōu)。

2.4 仿真驗(yàn)證

為檢驗(yàn)上述算法分析的合理性，本文利用Matlab 從兩個(gè)方面進(jìn)行了仿真驗(yàn)證。

（1）對改進(jìn)前后算法的運(yùn)算穩(wěn)定性進(jìn)行驗(yàn)證，預(yù)設(shè)50 個(gè)項(xiàng)目集，每個(gè)項(xiàng)目集包含事務(wù)集數(shù)為100，項(xiàng)目數(shù)為100 個(gè)，min_Sup=20%，采用改進(jìn)前后的Apriori 算法計(jì)算最大頻繁項(xiàng)集，傳統(tǒng)Apriori 算法對初始數(shù)據(jù)敏感度較高，計(jì)算復(fù)雜度因原始數(shù)據(jù)不同而不斷變化，運(yùn)算不夠穩(wěn)定，而改進(jìn)的Apriori 算法對初始數(shù)據(jù)不敏感，運(yùn)算穩(wěn)定度相對更高。計(jì)算結(jié)果如圖3 所示。

圖3 改進(jìn)前后Apriori 算法計(jì)算穩(wěn)定度對比

（2）進(jìn)一步對改進(jìn)前后算法的計(jì)算量進(jìn)行分析，同樣預(yù)設(shè)50 個(gè)項(xiàng)目集，每個(gè)項(xiàng)目集包含事務(wù)集數(shù)的值分別為60、70、80、90、100、110、120、130、140、150，項(xiàng)目數(shù)為100 個(gè)，min_Sup=20%，考慮到傳統(tǒng)Apriori 算法對初始數(shù)據(jù)較為敏感，用某個(gè)固定項(xiàng)目集進(jìn)行驗(yàn)證可能出現(xiàn)較大誤差，因此，對每個(gè)項(xiàng)目集取100 組初始化數(shù)據(jù)，分別計(jì)算兩種算法平均運(yùn)算次數(shù)，雖然這種計(jì)算方式也存在一定誤差，但由曲線趨勢可以判斷出，改進(jìn)的Apriori 算法計(jì)算性能明顯更優(yōu)。計(jì)算結(jié)果如圖4 所示。

圖4 改進(jìn)前后Apriori 算法計(jì)算次數(shù)對比

3 案例分析

本文結(jié)合國家等級保護(hù)2.0 標(biāo)準(zhǔn)，構(gòu)建了鐵路網(wǎng)絡(luò)安全指標(biāo)體系[17]，共包括211 項(xiàng)指標(biāo)。各項(xiàng)指標(biāo)的量化均根據(jù)實(shí)際評估結(jié)果得出。測評人員在對鐵路信息系統(tǒng)安全檢測評估過程中，對照具體指標(biāo)項(xiàng)，核查指標(biāo)符合情況，分為符合和不符合兩項(xiàng)，打分標(biāo)準(zhǔn)對應(yīng)為1 分和0 分。

以鐵路某單位網(wǎng)絡(luò)安全預(yù)警為例，選取2019—2020 年該單位發(fā)生網(wǎng)絡(luò)安全事件時(shí)系統(tǒng)各指標(biāo)數(shù)據(jù)，從數(shù)據(jù)庫中選取300 組211 項(xiàng)三級指標(biāo)數(shù)據(jù)，基于改進(jìn)的Apriori 算法，利用Matlab 進(jìn)行仿真驗(yàn)證，挖掘得到網(wǎng)絡(luò)安全風(fēng)險(xiǎn)強(qiáng)關(guān)聯(lián)因素，由此給出網(wǎng)絡(luò)安全預(yù)警及未來一段時(shí)間內(nèi)網(wǎng)絡(luò)安全重點(diǎn)防護(hù)方向。部分抽樣出來的風(fēng)險(xiǎn)指標(biāo)數(shù)據(jù)如表1 所示。

表1 鐵路某單位網(wǎng)絡(luò)安全指標(biāo)

由于篇幅有限，上表僅列出M1～M10 指標(biāo)項(xiàng)量化后矩陣，其余201 項(xiàng)指標(biāo)量化數(shù)據(jù)未詳細(xì)展示。這里簡要介紹M1～M6 這6 項(xiàng)指標(biāo)含義。

M1：機(jī)房場地應(yīng)具備防震、防風(fēng)和防雨等能力；

M2：機(jī)房應(yīng)具備防潮、防水措施；

M3：應(yīng)設(shè)置電子門禁，記錄、鑒別和控制進(jìn)出人員；

M4：應(yīng)固定設(shè)備主要部件，設(shè)置明顯標(biāo)識(shí)；

M5：通信線纜應(yīng)在隱蔽安全處；

M6：機(jī)房應(yīng)設(shè)置防盜措施。

設(shè)min_Sup=20%、min_Con=50%時(shí)，得出的結(jié)果如下：

各頻繁項(xiàng)集對應(yīng)的置信度分別為0.63、0.50、0.50、0.56、0.50。

得出的最大頻繁項(xiàng)集有5 個(gè)，以第1 個(gè)為例，得出網(wǎng)絡(luò)安全事件與第18、24、39、49、60、192 指標(biāo)關(guān)聯(lián)度較大，滿足預(yù)設(shè)的最小支持度，且這6 項(xiàng)指標(biāo)同時(shí)不滿足要求的情況下，發(fā)生網(wǎng)絡(luò)安全事件的概率為63%。說明該單位應(yīng)著重強(qiáng)化安全管理制度制訂、惡意代碼防護(hù)、系統(tǒng)漏洞修復(fù)和補(bǔ)丁升級、系統(tǒng)應(yīng)急預(yù)案制訂和應(yīng)急演練開展、網(wǎng)絡(luò)安全專業(yè)技術(shù)人員配備等工作，加強(qiáng)網(wǎng)絡(luò)安全建設(shè)和問題整改，最大程度避免網(wǎng)絡(luò)安全事件的發(fā)生。

4 結(jié)束語

本文研究提出了一種鐵路網(wǎng)絡(luò)安全預(yù)警方法，結(jié)合鐵路大數(shù)據(jù)實(shí)際應(yīng)用情況，引入Apriori 算法支持關(guān)聯(lián)規(guī)則計(jì)算，針對傳統(tǒng)Apriori 算法在計(jì)算復(fù)雜、空間耗費(fèi)高等方面的不足，對算法過程進(jìn)行了優(yōu)化改進(jìn)，并通過理論分析和示例仿真驗(yàn)證了改進(jìn)效果。最后結(jié)合鐵路某單位實(shí)際案例，對算法在鐵路網(wǎng)絡(luò)安全預(yù)警方面的應(yīng)用進(jìn)行了分析驗(yàn)證。理論論證和實(shí)驗(yàn)結(jié)果表明，改進(jìn)的Apriori 算法性能良好，計(jì)算復(fù)雜度較低，在鐵路網(wǎng)絡(luò)安全預(yù)警領(lǐng)域具有一定的應(yīng)用價(jià)值。

改進(jìn)的Apriori 算法在交集計(jì)算、過程剪枝等步驟中均存在一定的提升空間，實(shí)際計(jì)算過程中，大多數(shù)求交集計(jì)算屬無意義計(jì)算，并不能得出有價(jià)值的結(jié)果，若對初始數(shù)據(jù)進(jìn)行一定的質(zhì)量分析，或者運(yùn)算過程中合理設(shè)置相應(yīng)策略，可進(jìn)一步減少求交集次數(shù)，加大剪枝量，大幅度提升算法效率，這也將是后期工作的研究重點(diǎn)。