吳雯君，沈卓煒，曹玖新

〔東南大學(xué)網(wǎng)絡(luò)空間安全學(xué)院，江蘇南京 211189；網(wǎng)絡(luò)空間國(guó)際治理研究基地（東南大學(xué)），江蘇南京211189〕

1 引言

發(fā)布/訂閱分布式系統(tǒng)是基于數(shù)據(jù)分發(fā)服務(wù)[1]（DDS）中間件開(kāi)發(fā)的分布式系統(tǒng)，構(gòu)件間采用發(fā)布/訂閱模式通信。系統(tǒng)廣泛應(yīng)用于各種關(guān)鍵領(lǐng)域，如自動(dòng)駕駛汽車(chē)、醫(yī)療系統(tǒng)等。隨著系統(tǒng)規(guī)模日益龐大，構(gòu)件關(guān)聯(lián)日趨復(fù)雜，其安全可靠運(yùn)行面臨著挑戰(zhàn)[2]。若系統(tǒng)構(gòu)件出現(xiàn)異常，可能會(huì)導(dǎo)致整個(gè)分布式系統(tǒng)失效，造成嚴(yán)重的損失。如攻擊者利用某一構(gòu)件作為攻擊“入口”[3]，發(fā)布某個(gè)主題的錯(cuò)誤消息，訂閱該主題的構(gòu)件接收消息后執(zhí)行錯(cuò)誤操作。因此對(duì)系統(tǒng)進(jìn)行狀態(tài)監(jiān)控，把握構(gòu)件間的發(fā)布訂閱關(guān)系，監(jiān)測(cè)異常狀態(tài)，保障系統(tǒng)安全十分必要[4]。

這類(lèi)系統(tǒng)在正常運(yùn)行過(guò)程中往往存在多種運(yùn)行模式，對(duì)其開(kāi)展實(shí)時(shí)監(jiān)控的策略為：將系統(tǒng)當(dāng)前的運(yùn)行狀態(tài)與已知的正常模式匹配，判斷系統(tǒng)是否處于異常狀態(tài)。因此，根據(jù)已有監(jiān)控狀態(tài)數(shù)據(jù)識(shí)別出系統(tǒng)中存在的運(yùn)行模式，是系統(tǒng)異常狀態(tài)監(jiān)控的前提條件和基礎(chǔ)。對(duì)于這類(lèi)系統(tǒng)的監(jiān)控工具來(lái)說(shuō)，由于獨(dú)立于系統(tǒng)，不了解其業(yè)務(wù)邏輯，只能掌握其底層通信中間件層的發(fā)布/訂閱事件日志數(shù)據(jù)，因此在這類(lèi)系統(tǒng)中識(shí)別運(yùn)行模式尤為困難。

Apriori算法[5]是挖掘頻繁項(xiàng)集的經(jīng)典算法，用于挖掘數(shù)據(jù)中潛在的模式或規(guī)則，F(xiàn)P-growth算法對(duì)Apriori算法進(jìn)行了改進(jìn)，提高了運(yùn)行效率。這兩種算法均基于支持度閾值挖掘且以假設(shè)為前提：數(shù)據(jù)庫(kù)中各個(gè)項(xiàng)的重要性相同且均勻分布[6]。而在大多數(shù)系統(tǒng)中，每種運(yùn)行模式運(yùn)行時(shí)長(zhǎng)的占比不同且重要程度存在差異，按照支持度挖掘，很有可能挖掘不出運(yùn)行時(shí)長(zhǎng)短但重要的運(yùn)行模式。因此，本文針對(duì)發(fā)布/訂閱分布式系統(tǒng)的運(yùn)行特點(diǎn)，在中間件層面采集構(gòu)件的歷史通信數(shù)據(jù)，利用改進(jìn)的加權(quán)頻繁項(xiàng)集挖掘算法，挖掘系統(tǒng)運(yùn)行模式。根據(jù)挖掘結(jié)果構(gòu)建的知識(shí)庫(kù)對(duì)系統(tǒng)的異常檢測(cè)工作有重要意義。

2 運(yùn)行模式挖掘流程

發(fā)布/訂閱分布式系統(tǒng)中的業(yè)務(wù)邏輯對(duì)應(yīng)運(yùn)行模式，改變構(gòu)件間的交互關(guān)系就可切換模式。構(gòu)件利用中間件分發(fā)消息，基于主題可構(gòu)建構(gòu)件間的交互關(guān)系。針對(duì)系統(tǒng)的通信機(jī)制和運(yùn)行特點(diǎn)，設(shè)計(jì)了運(yùn)行模式挖掘及應(yīng)用流程，如圖1所示。

圖1 系統(tǒng)運(yùn)行模式挖掘及應(yīng)用流程

發(fā)布/訂閱分布式系統(tǒng)的監(jiān)控分為建模階段和檢測(cè)階段，在離線建模階段利用運(yùn)行模式挖掘結(jié)果構(gòu)建的知識(shí)庫(kù)可用于在線檢測(cè)階段的模式比較，決策者可以根據(jù)結(jié)果做出相應(yīng)的判斷。本文涉及的運(yùn)行模式挖掘主要包括三個(gè)部分。

（1）數(shù)據(jù)采集

利用攔截器機(jī)制采集構(gòu)件通信消息的相關(guān)信息，包括構(gòu)件發(fā)布或訂閱一條消息的時(shí)間、構(gòu)件名稱、主題和動(dòng)作，其中動(dòng)作分為發(fā)布和訂閱。

（2）數(shù)據(jù)預(yù)處理

將采集的數(shù)據(jù)根據(jù)相同的主題和對(duì)應(yīng)的發(fā)布或訂閱動(dòng)作構(gòu)建構(gòu)件間的發(fā)布訂閱關(guān)系，形成發(fā)布訂閱事件，其表示如表1所示，其中發(fā)布者和訂閱者對(duì)應(yīng)構(gòu)件名稱。

表1 發(fā)布訂閱事件

根據(jù)事件集合，對(duì)每一組發(fā)布訂閱關(guān)系以I1,I2…In進(jìn)行標(biāo)記得到發(fā)布訂閱事件標(biāo)記表，標(biāo)記表的字段信息如表2所示。根據(jù)表2中的主題及其對(duì)應(yīng)的發(fā)布者和訂閱者能夠得到系統(tǒng)的發(fā)布訂閱關(guān)系拓?fù)鋱D。對(duì)發(fā)布訂閱事件標(biāo)記得到事件序列，該序列呈現(xiàn)出兩個(gè)特點(diǎn)[7]。

表2 事件標(biāo)記表

1）規(guī)律性：發(fā)布/訂閱分布式系統(tǒng)中構(gòu)件間的發(fā)布訂閱關(guān)系通常事先確定。當(dāng)系統(tǒng)在不同運(yùn)行模式下執(zhí)行時(shí)，構(gòu)件間產(chǎn)生的發(fā)布訂閱事件是固定的。因此，同一模式下的發(fā)生的事件具有相關(guān)性，為運(yùn)行模式挖掘奠定了基礎(chǔ)。

2）重復(fù)性：系統(tǒng)在某一運(yùn)行模式下運(yùn)行時(shí)，構(gòu)件會(huì)按照設(shè)定的發(fā)布訂閱關(guān)系發(fā)布或接收消息，在不切換運(yùn)行模式的前提下，事件序列會(huì)重復(fù)出現(xiàn)。

（3）模式挖掘

對(duì)數(shù)據(jù)預(yù)處理后得到的事件序列進(jìn)行切分，以每個(gè)子序列中的事件集合作為一個(gè)事務(wù)構(gòu)建事務(wù)數(shù)據(jù)庫(kù)，應(yīng)用加權(quán)頻繁項(xiàng)集挖掘算法進(jìn)行模式挖掘。對(duì)挖掘結(jié)果進(jìn)行分析評(píng)估，可構(gòu)建運(yùn)行模式知識(shí)庫(kù)，包括基本信息、模式事件和事件屬性。異常檢測(cè)時(shí)根據(jù)運(yùn)行模式構(gòu)建有限自動(dòng)機(jī)進(jìn)行模式匹配，以發(fā)現(xiàn)系統(tǒng)的異常運(yùn)行狀態(tài)。

3 加權(quán)頻繁項(xiàng)集挖掘算法

Apriori算法挖掘頻繁項(xiàng)集有兩點(diǎn)不足：（1）多次遍歷事務(wù)數(shù)據(jù)庫(kù)效率低下；（2）以項(xiàng)的重要性相同為前提，完全依賴于支持度閾值，若閾值設(shè)置過(guò)高，會(huì)丟失較低頻率的項(xiàng)集。在系統(tǒng)中，項(xiàng)對(duì)應(yīng)發(fā)布訂閱事件，項(xiàng)集對(duì)應(yīng)運(yùn)行模式，不同事件的影響程度存在差異，且每種運(yùn)行模式的運(yùn)行時(shí)長(zhǎng)不同，事件的頻次也存在差異。因此按照支持度挖掘會(huì)導(dǎo)致運(yùn)行時(shí)間短但是重要的運(yùn)行模式丟失?；谏鲜鰡?wèn)題，本文提出了加權(quán)頻繁項(xiàng)集挖掘算法，引入了項(xiàng)的權(quán)值概念，從頻次和影響程度兩個(gè)方面體現(xiàn)項(xiàng)的重要性，進(jìn)一步得到事務(wù)的權(quán)值，利用加權(quán)支持度挖掘，并結(jié)合事務(wù)矩陣提高挖掘效率。

3.1 相關(guān)定義

本文對(duì)加權(quán)頻繁項(xiàng)集挖掘算法給出的定義為：

設(shè)I={I1,I2…Im}是項(xiàng)的集合，在系統(tǒng)中對(duì)應(yīng)發(fā)布訂閱事件集合。事務(wù)數(shù)據(jù)庫(kù)D中每個(gè)事務(wù)T都是項(xiàng)集I的子集，TI。

定義1 事務(wù)矩陣M

通過(guò)遍歷原始事務(wù)數(shù)據(jù)庫(kù)，利用矩陣M存儲(chǔ)事務(wù)，并對(duì)事務(wù)去重、計(jì)數(shù)。當(dāng)事務(wù)數(shù)據(jù)庫(kù)中重復(fù)事務(wù)較多時(shí)，能夠極大地壓縮事務(wù)數(shù)據(jù)庫(kù)[8～9]。

定義2 項(xiàng)的影響度

項(xiàng)即發(fā)布訂閱事件，其影響度E(Ij)與構(gòu)件間的發(fā)布訂閱關(guān)系有關(guān)。影響度的計(jì)算參考了PageRank算法計(jì)算過(guò)程，該算法通過(guò)分析網(wǎng)頁(yè)間的鏈接關(guān)系，對(duì)網(wǎng)頁(yè)重要性進(jìn)行評(píng)估[10]。基于構(gòu)件發(fā)布訂閱關(guān)系拓?fù)鋱D，評(píng)估各個(gè)構(gòu)件的影響度：各節(jié)點(diǎn)不再是網(wǎng)頁(yè)而是構(gòu)件，有向邊由鏈接變成發(fā)布訂閱關(guān)系。計(jì)算公式為：

其中，CR(p)表示構(gòu)件p的影響度，n為構(gòu)件總數(shù)，pi表示訂閱構(gòu)件p的第i個(gè)構(gòu)件，C(pi)表示訂閱構(gòu)件pi的構(gòu)件數(shù)，CR(pi)/C(pi)表示構(gòu)件pi傳遞給每個(gè)訂閱者的CR值，d為阻尼因子取值0.85。E(Ij)定義為發(fā)布訂閱事件中發(fā)布者構(gòu)件的CR值。

定義3 項(xiàng)的權(quán)重

項(xiàng)的權(quán)重是與項(xiàng)的特性相關(guān)的值，設(shè)項(xiàng)Ij對(duì)應(yīng)的權(quán)重為w(Ij)，權(quán)重與項(xiàng)在事務(wù)數(shù)據(jù)庫(kù)中出現(xiàn)的頻次和項(xiàng)自身的影響度有關(guān)，權(quán)重定義為：

其中，E(Ij)為項(xiàng)的影響度，P(Ij)=Count(Ij)/|D|表示項(xiàng)Ij在事務(wù)數(shù)據(jù)庫(kù)中出現(xiàn)的概率，Count(Ij)為項(xiàng)Ij的頻次，|D|表示數(shù)據(jù)庫(kù)的事務(wù)總數(shù)，以P(Ij)的倒數(shù)體現(xiàn)項(xiàng)Ij在的頻次方面的重要性。α和β分別表示項(xiàng)的影響度和頻次影響程度的系數(shù)，令α+β=1，根據(jù)實(shí)際場(chǎng)景調(diào)整α和β的取值，實(shí)現(xiàn)有效挖掘。

定義4 事務(wù)的權(quán)重

事務(wù)的權(quán)重為事務(wù)中包含項(xiàng)的權(quán)重的平均值乘以事務(wù)計(jì)數(shù)，|Tk|表示事務(wù)中項(xiàng)的個(gè)數(shù)，則第k個(gè)事務(wù)Tk的權(quán)重為：

定義5 項(xiàng)集的加權(quán)支持度

項(xiàng)集的加權(quán)支持度為包含項(xiàng)集的事務(wù)權(quán)重之和與所有事務(wù)權(quán)重總和的比值，項(xiàng)集t的加權(quán)支持度計(jì)算公式為：

3.2 算法描述

基于上述定義，本文提出了加權(quán)頻繁項(xiàng)集挖掘算法如表3所示。

表3 加權(quán)頻繁項(xiàng)集挖掘算法

4 實(shí)驗(yàn)與結(jié)果

4.1 算法應(yīng)用實(shí)例

實(shí)驗(yàn)基于實(shí)驗(yàn)室自主研發(fā)的“信息集成管理軟件”DDS中間件產(chǎn)品模擬了自動(dòng)駕駛汽車(chē)的控制系統(tǒng)。應(yīng)用構(gòu)件包含若干個(gè)傳感器、數(shù)據(jù)處理和分析的控制器以及控制行駛的執(zhí)行器，應(yīng)用構(gòu)件利用中間件進(jìn)行通信，如圖2所示。

圖2 自動(dòng)駕駛汽車(chē)控制系統(tǒng)

控制系統(tǒng)中存在三種運(yùn)行模式：正常行駛、剎車(chē)和轉(zhuǎn)彎，該系統(tǒng)的構(gòu)件發(fā)布訂閱關(guān)系拓?fù)鋱D如圖3所示。其中圓形表示構(gòu)件，箭頭表示發(fā)布訂閱關(guān)系，I1-I6表示發(fā)布訂閱事件，正常行駛模式下事件I1,I2,I3,I4對(duì)應(yīng)的構(gòu)件間存在交互，同樣剎車(chē)模式為I1,I2,I3,I5事件，轉(zhuǎn)彎模式為I1,I2,I3,I6事件。

圖3 發(fā)布/訂閱關(guān)系拓?fù)鋱D

利用攔截器機(jī)制在中間件層采集系統(tǒng)運(yùn)行一段時(shí)間的構(gòu)件間發(fā)布/訂閱數(shù)據(jù)，其中大部分時(shí)間是正常行駛，轉(zhuǎn)彎和剎車(chē)所占時(shí)間比例較小。對(duì)數(shù)據(jù)預(yù)處理后執(zhí)行加權(quán)頻繁項(xiàng)集挖掘算法，設(shè)置最小支持度閾值Supmin=0.2，項(xiàng)的權(quán)重系數(shù)α=0.5，β=0.5。對(duì)挖掘結(jié)果取最大頻繁項(xiàng)集得到最終結(jié)果，見(jiàn)表4。

表4 頻繁項(xiàng)集挖掘結(jié)果

實(shí)驗(yàn)表明，本文提出的方案能夠挖掘出系統(tǒng)中存在的運(yùn)行模式，對(duì)挖掘結(jié)果分析處理后構(gòu)建運(yùn)行模式知識(shí)庫(kù)，可用于進(jìn)一步的異常檢測(cè)。

4.2 算法分析與驗(yàn)證

利用實(shí)例中采集的數(shù)據(jù)，通過(guò)兩組實(shí)驗(yàn)驗(yàn)證本文提出的加權(quán)頻繁項(xiàng)集挖掘算法的有效性和效率。

（1）算法的有效性

算法的有效性檢驗(yàn)是測(cè)試本文提出的算法和Apriori算法產(chǎn)生的頻繁項(xiàng)集和對(duì)應(yīng)的支持度情況，同時(shí)驗(yàn)證了α和β系數(shù)的取值對(duì)支持度的影響。令最小支持度閾值Supmin=0.2，計(jì)算4-項(xiàng)集的支持度，實(shí)驗(yàn)結(jié)果如表5所示。

表5 4-項(xiàng)集挖掘結(jié)果

從表5可以看出，加權(quán)頻繁項(xiàng)集挖掘算法的挖掘結(jié)果中包含小概率發(fā)生事件的I5和I6的項(xiàng)集支持度相較于Apriori算法都有所提高，包含I4的項(xiàng)集支持度有所降低，項(xiàng)集的加權(quán)支持度趨于均值。實(shí)驗(yàn)表明，通過(guò)對(duì)項(xiàng)從影響度和頻次兩個(gè)方面進(jìn)行加權(quán)，提升了發(fā)生次數(shù)少且有價(jià)值的項(xiàng)的支持度，能夠挖掘出包含小概率發(fā)生事件的運(yùn)行模式。

同時(shí)，加權(quán)頻繁項(xiàng)集挖掘算法中隨著參數(shù)值α的增大，對(duì)項(xiàng)的影響度的側(cè)重增加，在支持度均值之上的項(xiàng)集支持度逐漸提高，均值之下的支持度逐漸降低，項(xiàng)集的支持度區(qū)分更加鮮明。當(dāng)α取0.7時(shí)，項(xiàng)集{I1,I2,I3,I6}的支持度低于最小支持度閾值，對(duì)項(xiàng)的頻次的側(cè)重過(guò)低，因此α取0.5既從頻次方面提高項(xiàng)集支持度，又體現(xiàn)影響度對(duì)支持度的影響。

（2）算法的效率

為了驗(yàn)證文本提出的算法的性能，實(shí)驗(yàn)令最小支持度閾值Supmin=0.2，為保證實(shí)驗(yàn)結(jié)果不受項(xiàng)的影響度權(quán)重的影響，令α=0，β=1。分別使用改進(jìn)的算法、Apriori算法和FP-growth算法對(duì)不同的事務(wù)數(shù)、相同事務(wù)數(shù)下不同的支持度進(jìn)行實(shí)驗(yàn)，比較了三種算法的執(zhí)行時(shí)間，實(shí)驗(yàn)結(jié)果如圖4和圖5所示。

圖4 不同事務(wù)數(shù)運(yùn)行時(shí)間對(duì)比

圖5 不同支持度閾值運(yùn)行時(shí)間對(duì)比

從圖4可以看出，隨著系統(tǒng)運(yùn)行時(shí)間的增長(zhǎng)，構(gòu)建的事務(wù)數(shù)據(jù)庫(kù)中的事務(wù)數(shù)越多，在不同的事務(wù)數(shù)下，本文提出的算法相較于Apriori算法和FPgrowth算法性能有了顯著或有效的提升，且隨著事務(wù)數(shù)的增大，處理時(shí)間的差距越大。這是因?yàn)楦倪M(jìn)算法只掃描一遍事務(wù)數(shù)據(jù)庫(kù)，利用事務(wù)矩陣對(duì)事務(wù)數(shù)據(jù)庫(kù)進(jìn)行了壓縮，減少了掃描時(shí)間，且矩陣中的與操作也減少了項(xiàng)集支持度的計(jì)算時(shí)間。

圖5為事務(wù)數(shù)為5000時(shí)，支持度閾值選取0.1-0.5的情況下三種算法的運(yùn)行時(shí)間，當(dāng)支持度閾值越大，挖掘時(shí)間越短。改進(jìn)的算法與Apriori算法相比運(yùn)行時(shí)間隨支持度閾值變化的幅度較小且在每種支持度閾值下的運(yùn)行時(shí)間均優(yōu)于其他兩種算法。

5 結(jié)束語(yǔ)

本文提出了一種加權(quán)頻繁項(xiàng)集挖掘算法應(yīng)用于發(fā)布/訂閱分布式系統(tǒng)中的運(yùn)行模式識(shí)別，挖掘結(jié)果可用于系統(tǒng)異常狀態(tài)的檢測(cè)。在具體的應(yīng)用場(chǎng)景中，通過(guò)實(shí)驗(yàn)分析和驗(yàn)證，本文提出的算法能夠有效地挖掘出系統(tǒng)中存在的運(yùn)行模式且運(yùn)行效率優(yōu)于Apriori算法和FP-growth算法。在后續(xù)工作中，將研究改進(jìn)算法的并行化方案以處理海量的發(fā)布/訂閱分布式系統(tǒng)運(yùn)行數(shù)據(jù)，進(jìn)一步提高算法的性能。