日志模板提取的FT-Tree改進(jìn)算法研究

顧海艷,鄭淇文

(江蘇警官學(xué)院計(jì)算機(jī)信息與網(wǎng)絡(luò)安全系,江蘇 南京 210031)

計(jì)算機(jī)日志是用于動(dòng)態(tài)記錄系統(tǒng)操作事件的、具有特定格式和特定功能的文件,主要包含系統(tǒng)本身、應(yīng)用程序、安全管理等方面的行為信息,具有自動(dòng)性、真實(shí)性和全面性等特點(diǎn). 通過(guò)對(duì)日志文件信息的提取分析,可為網(wǎng)絡(luò)安全管理提供依據(jù),也可為確定犯罪方法、手段、途徑、時(shí)間、地點(diǎn)提供證據(jù)支持,乃至復(fù)現(xiàn)相關(guān)涉網(wǎng)犯罪過(guò)程,因而日志已經(jīng)作為一種電子證據(jù)在偵查辦案中得到普遍應(yīng)用. 根據(jù)中國(guó)裁判文書網(wǎng)(http://wenshu.court.gov.cn/)提供的2009年至2019年相關(guān)案件信息中涉及日志的已宣判刑事案件數(shù)如圖1所示,不難發(fā)現(xiàn),自2014年以來(lái),日志文件越來(lái)越多地作為證據(jù)在案件中被采信. 隨著各種網(wǎng)絡(luò)應(yīng)用的快速發(fā)展,對(duì)日志文件分析的需求在迅速增加,如何在網(wǎng)絡(luò)安全管理、案件偵辦過(guò)程中實(shí)現(xiàn)對(duì)海量日志信息的快速準(zhǔn)確分析變得越發(fā)重要. 因此,亟需研究日志文件模板的高效可靠提取方法.

圖1 已宣判涉及日志的刑事案件數(shù)隨年份的變化情況Fig.1 Changes of the number of criminal cases adjudicated involving logs along with the years

日志文件模板提取方法目前主要采用基于聚類的算法. Tang等[1]在預(yù)先確定日志聚類數(shù)目的情況下,研究建立了基于詞對(duì)關(guān)系的聚類方法以提取日志模板. 李文杰等[2]改進(jìn)了基于密度的空間聚類算法,通過(guò)自適應(yīng)法設(shè)置E鄰域,實(shí)現(xiàn)了將對(duì)象按簇進(jìn)行聚類的日志模板提取方法. Vaarandi等[3]提出使用聚合層次聚類,利用聚類結(jié)果,選擇每個(gè)聚類中與其他序列距離最小的序列作為日志模板. Nandi等[4]通過(guò)引入日志時(shí)間序列關(guān)系輔助聚類構(gòu)建過(guò)程,提高了模板挖掘的準(zhǔn)確率. 雙鍇等[5]提出了基于歸一化特征的日志模板挖掘算法,在先驗(yàn)信息較少時(shí)可取得更好的效果.

崔元等[6]對(duì)目前公認(rèn)的基于統(tǒng)計(jì)模板的提取模型、基于標(biāo)簽識(shí)別樹(shù)模板的提取模型和基于在線模板的提取模型進(jìn)行了對(duì)比分析,發(fā)現(xiàn)基于標(biāo)簽識(shí)別樹(shù)的提取模板模型是三者中最為穩(wěn)定和可靠的算法模型,而基于統(tǒng)計(jì)模板的聚類算法模型在模板提取中并沒(méi)有優(yōu)勢(shì). 2017年Zhang等[7]在標(biāo)簽識(shí)別樹(shù)模型基礎(chǔ)上提出了FT-Tree(frequent template tree,頻繁模板樹(shù))模型,該模型是通過(guò)識(shí)別日志單詞的頻繁組合來(lái)構(gòu)建日志模板,實(shí)驗(yàn)表明,FT-Tree模型與標(biāo)簽識(shí)別樹(shù)模型的提取結(jié)果具有相似的準(zhǔn)確度,但FT-Tree模型的計(jì)算成本和增量可追溯性比標(biāo)簽識(shí)別樹(shù)模型更具優(yōu)勢(shì). 通過(guò)對(duì)FT-tree算法進(jìn)一步研究發(fā)現(xiàn),模型構(gòu)建中剪枝參數(shù)為人工設(shè)定,易導(dǎo)致模板提取結(jié)果的準(zhǔn)確度受到影響. 因不同的日志文件記載不同的信息,不同計(jì)算機(jī)系統(tǒng)使用不同的日志記錄方式[8],為此本文以最常見(jiàn)的網(wǎng)絡(luò)服務(wù)器日志文件為對(duì)象,研究FT-Tree算法的改進(jìn)方法,以提高日志模板提取的準(zhǔn)確度.

1 FT-Tree日志模板提取算法簡(jiǎn)介

1.1 FT-Tree日志模板提取算法

FT-Tree算法是在結(jié)合FP-Grouth算法(frequent pattern tree,頻繁模式樹(shù))與標(biāo)簽識(shí)別樹(shù)算法的優(yōu)勢(shì)的基礎(chǔ)上提出的的模板提取算法[9]. 該算法源碼可通過(guò)開(kāi)源平臺(tái)(https://github.com/slzhangsd/Craftsman)獲取,用該算法提取日志模板的流程如下.

(1)第一次遍歷整個(gè)日志數(shù)據(jù),獲得詞頻序列L,即獲得以頻率大小為依據(jù)的詞袋模型排序.

(2)第二次遍歷整個(gè)日志數(shù)據(jù),根據(jù)詞頻序列L,對(duì)每條日志記錄構(gòu)造其日志單詞鏈表{Mi}. 每個(gè)鏈表的第一個(gè)結(jié)點(diǎn)是在詞頻序列L中詞頻最高的單詞,其它結(jié)點(diǎn)的排序根據(jù)單詞在詞頻列表中從高到低順序確定.

(3)依據(jù)是否共享共同前綴,將這些鏈表組合成多叉樹(shù)林,即構(gòu)建多棵FT-Tree樹(shù).

(4)第三次遍歷日志數(shù)據(jù),即遍歷該多叉樹(shù)林,根據(jù)每個(gè)結(jié)點(diǎn)的子結(jié)點(diǎn)數(shù)進(jìn)行剪枝以構(gòu)造FT-Tree模型. 剪枝過(guò)程中根據(jù)設(shè)定的閾值常量K(K≥2),對(duì)每一個(gè)結(jié)點(diǎn)的子結(jié)點(diǎn)數(shù)進(jìn)行統(tǒng)計(jì),如果某結(jié)點(diǎn)的子結(jié)點(diǎn)數(shù)小于常量K,就意味著該結(jié)點(diǎn)與大部分結(jié)點(diǎn)情況不匹配,則將該結(jié)點(diǎn)的所有子結(jié)點(diǎn)刪去,使該結(jié)點(diǎn)成為葉結(jié)點(diǎn).

(5)如果有新的數(shù)據(jù)需要處理,只需要在已有的FT-Tree模型的基礎(chǔ)上重復(fù)進(jìn)行生長(zhǎng)和剪枝操作.

1.2 FT-Tree提取日志模板算法優(yōu)劣分析

FT-Tree算法提取日志模板的基本思路是:日志模板應(yīng)當(dāng)是在日志記錄中較為頻繁出現(xiàn)的詞袋模型的組合,該算法只要遍歷3次日志數(shù)據(jù)即可得到模板結(jié)果. 相比于聚類算法需要進(jìn)行多次迭代[10],FT-Tree提取算法的優(yōu)勢(shì):一是可大大減少計(jì)算時(shí)間和占用計(jì)算資源;二是如果新加入的日志數(shù)據(jù)不引起詞頻列表數(shù)據(jù)順序的變化,則該算法構(gòu)造的模型可以自動(dòng)生長(zhǎng),這是需要重新訓(xùn)練的聚類算法所不能比擬的;三是生成的模板提取結(jié)果是結(jié)構(gòu)化數(shù)據(jù),便于做進(jìn)一步分析研究.

雖然FT-Tree算法優(yōu)勢(shì)明顯,但也存在不足,主要表現(xiàn)在構(gòu)造FT-Tree樹(shù)時(shí),其剪枝閾值常量K是由人工憑經(jīng)驗(yàn)設(shè)定,隨機(jī)性大、缺乏理論依據(jù). 由于各類日志數(shù)據(jù)的差異較大,僅憑經(jīng)驗(yàn)確定剪枝閾值,很有可能出現(xiàn)幸存者偏差,因此需要對(duì)剪枝參數(shù)的確定方法進(jìn)行改進(jìn).

2 FT-Tree算法的改進(jìn)思路及其實(shí)現(xiàn)

2.1 FT-Tree算法的改進(jìn)思路

經(jīng)分析比較,本文選用Apriori算法對(duì)FT-Tree算法的剪枝過(guò)程進(jìn)行改進(jìn). Apriori算法是經(jīng)典的關(guān)聯(lián)規(guī)則挖掘算法,最早由Agrawal等人于1993提出[11]. 一般而言,關(guān)聯(lián)規(guī)則可表示為形如A→B的蘊(yùn)含表達(dá)式,其中A和B是不相交的項(xiàng)集.關(guān)聯(lián)規(guī)則的強(qiáng)度可用支持度(support)和置信度(confidence)來(lái)度量[12].

A→B規(guī)則的支持度是指該規(guī)則在給定事務(wù)集中出現(xiàn)的概率,其計(jì)算如下:

support(A→B)=P(A∪B),

(1)

A→B規(guī)則的置信度是指B在包含A的事務(wù)中出現(xiàn)的概率,其計(jì)算如下:

confidence(A→B)=P(A|B)=P(A∪B)/P(A),

(2)

通過(guò)發(fā)現(xiàn)滿足最小支持度的頻繁項(xiàng)集,可進(jìn)一步提取滿足最小置信度的強(qiáng)規(guī)則[13].本研究利用Apriori算法通過(guò)抓取日志記錄中詞關(guān)聯(lián)的強(qiáng)規(guī)則,來(lái)獲得日志模板.

改進(jìn)后的FT-Tree算法具體步驟如下:

(1)-(2)步驟與FT-Tree算法相同.

(3)依據(jù)是否共享共同前綴,將這些鏈表組合成多叉樹(shù)林.多叉樹(shù)的結(jié)點(diǎn)以列表中的詞命名,同時(shí)結(jié)點(diǎn)中保存該詞在構(gòu)造過(guò)程中出現(xiàn)的次數(shù).

(4)計(jì)算各個(gè)結(jié)點(diǎn)置信度{xi},并利用Apriori算法計(jì)算置信度閾值X.第i個(gè)結(jié)點(diǎn)的置信度計(jì)算公式為:

xi=ni/n,

(3)

式中,n為所在樹(shù)的根結(jié)點(diǎn)出現(xiàn)次數(shù),ni為第i個(gè)結(jié)點(diǎn)在對(duì)應(yīng)位置出現(xiàn)的次數(shù).對(duì)于每棵FT-Tree樹(shù),其根結(jié)點(diǎn)是詞頻最高的頻繁詞,結(jié)點(diǎn)的置信度也就是{根結(jié)點(diǎn)}→{非根結(jié)點(diǎn)}這個(gè)關(guān)聯(lián)規(guī)則的置信度,置信度較大的結(jié)點(diǎn)(即出現(xiàn)次數(shù)排在前列,人工設(shè)定置信度前列的標(biāo)準(zhǔn)為ε)也就是強(qiáng)規(guī)則結(jié)點(diǎn).利用Apriori算法,根據(jù)ε計(jì)算強(qiáng)規(guī)則結(jié)點(diǎn)的置信度閾值X.

(5)根據(jù)置信度閾值X,對(duì)非強(qiáng)規(guī)則結(jié)點(diǎn)進(jìn)行剪枝.置信度標(biāo)準(zhǔn)ε雖然也是人工設(shè)定,但它是根據(jù)置信度排在前列的原則確定,要比直接根據(jù)人工選定的子結(jié)點(diǎn)數(shù)閾值常量K進(jìn)行裁剪更加科學(xué).

2.2 改進(jìn)FT-Tree算法的實(shí)現(xiàn)

網(wǎng)絡(luò)服務(wù)器日志文件的特點(diǎn):(1)不存在以漢字為基礎(chǔ)的日志記錄格式,沒(méi)有必要考慮漢字對(duì)日志模板的影響;(2)日志記錄各成分間主要以“[ ]”“,”“{ }”為隔斷.針對(duì)這些特點(diǎn),為兼顧算法準(zhǔn)確度與速度,本文采用正則表達(dá)式作為分詞的依據(jù),以研究FT-Tree算法的改進(jìn)算法.

2.2.1 數(shù)據(jù)預(yù)處理

日志文件數(shù)據(jù)預(yù)處理主要包括數(shù)據(jù)清洗和構(gòu)造詞袋模型兩個(gè)過(guò)程. 數(shù)據(jù)清洗的主要工作包括刪除冗余的日志記錄、對(duì)日志記錄進(jìn)行分類并剔除日志記錄中的具體報(bào)錯(cuò)信息、刪除日志記錄中的URL,以提高模板提取的準(zhǔn)確性. 構(gòu)建詞袋模型就是生成字典格式記錄的數(shù)據(jù),這是模板提取程序段的輸入數(shù)據(jù).

(1)數(shù)據(jù)清洗

清洗過(guò)程中主要使用4個(gè)函數(shù).

①Deduplication1函數(shù)

由于網(wǎng)絡(luò)在建立端與端之間連接時(shí)常常會(huì)失敗,從而留下冗余的日志記錄. 本文使用python的re標(biāo)準(zhǔn)庫(kù)中的函數(shù)Deduplication1去除重復(fù)日志記錄.

②Classify_*函數(shù)、check_Classify函數(shù)

網(wǎng)絡(luò)服務(wù)器在提供java等服務(wù)出錯(cuò)時(shí)會(huì)報(bào)錯(cuò),而日志會(huì)詳細(xì)記錄報(bào)錯(cuò)內(nèi)容. “WANGRING”“INFO”“ALERT”和“NOTICE”這4類日志記錄中都可能會(huì)記錄報(bào)錯(cuò)信息,本文編寫了Classify_*函數(shù)和check_Classify函數(shù),實(shí)現(xiàn)對(duì)日志記錄的分類和報(bào)錯(cuò)日志中錯(cuò)誤內(nèi)容的處理.

③Deduplication5函數(shù)

記錄在網(wǎng)絡(luò)服務(wù)器日志中的URL常常會(huì)因調(diào)用同一種服務(wù)而重復(fù)出現(xiàn). 例如提供郵件服務(wù)的網(wǎng)絡(luò)服務(wù)器在用戶每次登陸時(shí)都會(huì)調(diào)用對(duì)應(yīng)的jsp服務(wù). 如果不進(jìn)行清洗,很有可能會(huì)成為后期日志模板提取的噪點(diǎn),從而影響日志模板提取的準(zhǔn)確性. 為此本文選用re標(biāo)準(zhǔn)庫(kù)中Deduplication5的函數(shù)去除日志數(shù)據(jù)中的URL.

(2)構(gòu)造詞袋模型

自然語(yǔ)言處理(NLP)技術(shù)通過(guò)切詞將目標(biāo)文本劃分為不同的單元,并計(jì)算其權(quán)重. 網(wǎng)絡(luò)服務(wù)器日志文件以“Time stamp”“Message-type”“Detail message”為切入點(diǎn),由于“Detail message”數(shù)據(jù)量龐大,在使用空格區(qū)分“Time stamp”“Message-type”之后,只能選擇使用逗號(hào)來(lái)分隔“Detail message”. 本文使用re標(biāo)準(zhǔn)庫(kù)中的切詞函數(shù)abstract2,構(gòu)建根據(jù)逗號(hào)切割的正則表達(dá)式(,[＾(,|{|}|[|])] ??,);再利用 re.findall( )函數(shù)將所有匹配結(jié)果以字典形式返回. 根據(jù)字典的鍵值對(duì),可清晰展現(xiàn)各單詞的出現(xiàn)次數(shù).

2.2.2 算法實(shí)現(xiàn)

算法實(shí)現(xiàn)就是把已經(jīng)完成切詞的數(shù)據(jù)按照一定的方法構(gòu)建成有邏輯結(jié)構(gòu)的多叉樹(shù)林. 改進(jìn)的FT-Tree日志模板提取算法主要實(shí)現(xiàn)步驟如下:

(1)構(gòu)建詞頻序列. 由于切詞過(guò)程中已經(jīng)將日志中的單詞及其出現(xiàn)次數(shù)寫入了對(duì)應(yīng)字典中,故該步驟只需要調(diào)取對(duì)應(yīng)字典即可.

(2)調(diào)用seedcreate函數(shù)并按行接收日志記錄,按詞頻序列由高到低,建立該記錄的單詞鏈表,然后將該鏈表作為返回值輸出.

(3)構(gòu)建多叉樹(shù)林. 基于treelib標(biāo)準(zhǔn)庫(kù),根據(jù)seedcreate函數(shù)返回值構(gòu)建改進(jìn)的多叉樹(shù)林.

(4)計(jì)算置信度和置信度閾值. 根據(jù)公式(3)計(jì)算每個(gè)非根結(jié)點(diǎn)置信度xi. 一般研究認(rèn)為置信度在前30%的為強(qiáng)規(guī)則結(jié)點(diǎn),因而本文設(shè)定置信度前列的標(biāo)準(zhǔn)ε=1/e(e為自然常數(shù),取e=2.718),即選取置信度在前36.79%的結(jié)點(diǎn)為強(qiáng)規(guī)則結(jié)點(diǎn).

(5)剪枝構(gòu)建改進(jìn)FT-Tree模型. 根據(jù)得到的置信度閾值X,對(duì)構(gòu)建的多叉樹(shù)林進(jìn)行剪枝.

3 結(jié)果與討論

為了檢驗(yàn)本文改進(jìn)算法的日志模板提取效果,在聯(lián)想電腦拯救者r720-15IKBN、Windows10家庭中文版、python3環(huán)境中,利用某高校真實(shí)網(wǎng)絡(luò)服務(wù)器的10 MB日志文件wmsvr.log.2019-08-21進(jìn)行了日志模板提取實(shí)驗(yàn).

3.1 實(shí)驗(yàn)過(guò)程

(1)數(shù)據(jù)清洗. 數(shù)據(jù)預(yù)處理結(jié)束后,形成一個(gè)具有712個(gè)單詞的詞頻列表,列表中排在前10的單詞集和出現(xiàn)次數(shù)如表1所示.

表1 詞頻列表中前10位的單詞出現(xiàn)次數(shù)Table 1 Occurrence times of the top 10 words in the word frequency list

(2)提取日志模板. 經(jīng)檢查,10 MB的日志文件共包含28 417條日志信息,用改進(jìn)算法提取發(fā)現(xiàn)共有64條日志模板. 部分提取結(jié)果如圖2所示.

圖2 改進(jìn)FT-Tree算法提取的部分日志模板Fig.2 Partial log templates extracted by the improved FT-Tree algorithm

(3)對(duì)比實(shí)驗(yàn). 將本文改進(jìn)算法與FT-Tree算法進(jìn)行實(shí)驗(yàn)對(duì)比分析. 因FT-Tree算法需要人為設(shè)定剪枝常量K值,為檢驗(yàn)不同K值對(duì)提取模板結(jié)果的影響,使K值依次從2到10循環(huán)運(yùn)行,并根據(jù)apache系統(tǒng)通用日志格式,對(duì)提取的模板數(shù)據(jù)進(jìn)行準(zhǔn)確度分析. 兩種算法運(yùn)行后提取的模板數(shù)量、符合通用格式的模板數(shù)量對(duì)比如表2所示.

表2 兩種FT-Tree算法提取的日志模板數(shù)對(duì)比Table 2 Comparison of the number of log templates extracted by two FT-Tree algorithms

3.2 實(shí)驗(yàn)結(jié)果分析

(1)從表2可以發(fā)現(xiàn),隨著FT-Tree算法中剪枝常量K值增加,提取的模板數(shù)量隨之減少,說(shuō)明剪枝參數(shù)設(shè)定對(duì)模板提取的結(jié)果有明顯的影響. 這也進(jìn)一步說(shuō)明對(duì)剪枝參數(shù)設(shè)定方法進(jìn)行研究很有必要.

(2)由表2還可以發(fā)現(xiàn),FT-Tree算法在K=2時(shí)提取模板數(shù)最多,共37種,提取的結(jié)果準(zhǔn)確度最高達(dá)到86.5%;而改進(jìn)算法可提取64種模板,提取結(jié)果的準(zhǔn)確度達(dá)到95.3%. 這充分表明改進(jìn)算法提取的模板結(jié)果不僅豐富,而且準(zhǔn)確度高.

(3)另外根據(jù)實(shí)驗(yàn)中記錄的中間數(shù)據(jù)還可以發(fā)現(xiàn),Apriori算法計(jì)算的置信度閾值X=0.001 081,這是人工憑經(jīng)驗(yàn)無(wú)法確定的數(shù)值,說(shuō)明用算法選取閾值的方法更科學(xué)準(zhǔn)確.

綜上,兩種算法的模板提取結(jié)果對(duì)比,充分說(shuō)明改進(jìn)的算法有效提高了日志模板提取的準(zhǔn)確度.

4 結(jié)論

隨著涉網(wǎng)案件數(shù)量的快速增長(zhǎng),日志文件作為電子證據(jù)在偵查辦案中越來(lái)越受到重視,日志文件的分析研究也將受到更多關(guān)注. 本文鑒于當(dāng)前日志模板提取中存在的不足,提出了基于FT-Tree算法的日志模板提取改進(jìn)算法. 針對(duì)FT-Tree算法因剪枝閾值人為設(shè)置而導(dǎo)致模型準(zhǔn)確度不高的問(wèn)題,將Apriori算法利用置信度抓取強(qiáng)規(guī)則的思想引入模型構(gòu)建中,改進(jìn)了原算法中剪枝參數(shù)的確定方法,從而提高了日志模板提取的準(zhǔn)確度;并利用某高校真實(shí)網(wǎng)絡(luò)服務(wù)器日志文件進(jìn)行了實(shí)驗(yàn)驗(yàn)證,結(jié)果表明改進(jìn)的FT-Tree算法是可靠、高效的,能更好地滿足實(shí)際應(yīng)用需要.