K-Means和KNN日志異常檢測(cè)方法*

烏旭東，容曉峰，仲姝锜

(西安工業(yè)大學(xué) 英特爾嵌入式技術(shù)聯(lián)合實(shí)驗(yàn)室，西安 710021)

日志是一種半結(jié)構(gòu)化的數(shù)據(jù)，記錄著系統(tǒng)運(yùn)行的關(guān)鍵行為，在系統(tǒng)出錯(cuò)的情況下可以通過查找日志來定位故障，與日俱增的日志數(shù)據(jù)規(guī)模和網(wǎng)絡(luò)安全問題使網(wǎng)絡(luò)管理者面臨嚴(yán)峻的挑戰(zhàn)[1]。近年來，異常檢測(cè)作為數(shù)據(jù)挖掘的一個(gè)分支正受到越來越多的關(guān)注，異常檢測(cè)是指從數(shù)據(jù)中找出不符合預(yù)期的數(shù)據(jù)模式的過程[2]。日志數(shù)據(jù)的異常檢測(cè)行為從本質(zhì)上講可以看作為分類問題，即從大量存在異常日志行為的數(shù)據(jù)中區(qū)分出正常行為和異常行為，并在異常行為中判斷出具體的攻擊方式[3]。當(dāng)服務(wù)器運(yùn)行時(shí)，日志會(huì)記錄并生成用戶訪問的過程，可以通過日志中的信息來查找異常用戶的信息。因此，分析日志成為檢測(cè)用戶異常行為的最有效方法之一[4-6]。

隨著大數(shù)據(jù)的快速發(fā)展，基于日志的異常檢測(cè)方法分為三大類：基于模型的技術(shù)、基于鄰近度的技術(shù)和基于密度的技術(shù)。基于模型的技術(shù)建立了一個(gè)數(shù)據(jù)模型，該模型不能完美擬合的對(duì)象則為異常對(duì)象。將異常和正常對(duì)象定義為兩個(gè)不同的類，使用分類技術(shù)建立兩個(gè)類的模型。分類技術(shù)中訓(xùn)練集很重要，由于異常相對(duì)稀少，所以無法檢測(cè)可能會(huì)出現(xiàn)的新異常[7]。文獻(xiàn)[8]提出了一個(gè)新的基于Apache Hive的數(shù)據(jù)存儲(chǔ)和分析架構(gòu)來處理大量的Hadoop日志數(shù)據(jù)，使用平均移動(dòng)和3-sigma技術(shù)設(shè)計(jì)并實(shí)現(xiàn)了三種異常檢測(cè)方法，分別為基本法、線性權(quán)重法和指數(shù)權(quán)重法，在一個(gè)名稱結(jié)點(diǎn)和四個(gè)數(shù)據(jù)結(jié)點(diǎn)的Hadoop平臺(tái)下評(píng)估了提出的方法的有效性。文獻(xiàn)[9]提出了一種不需要任何特定應(yīng)用知識(shí)在非結(jié)構(gòu)化系統(tǒng)日志中進(jìn)行異常檢測(cè)的技術(shù)，包括一種從自由文本消息中提取日志密鑰的方法，在Hadoop平臺(tái)下實(shí)驗(yàn)的誤報(bào)率約為13%。文獻(xiàn)[10]通過源代碼匹配日志的格式，找出相關(guān)變量，通過詞袋模型提取對(duì)應(yīng)日志變量的特征，使用這些特征通過主成分分析方法降維，根據(jù)主成分分析的最大可分性檢測(cè)異常的日志文件，使用決策樹可視化該結(jié)果。文獻(xiàn)[11]使用隨機(jī)索引為代表的操作序列，根據(jù)其上下文為每個(gè)日志中的操作特征化，使用支持向量機(jī)關(guān)聯(lián)序列到故障或無故障的類別上，以此來預(yù)測(cè)系統(tǒng)故障。文獻(xiàn)[12]應(yīng)用文本挖掘技術(shù)將日志文件中的消息分類為常見情況，通過考慮日志消息的時(shí)間特性來提高分類準(zhǔn)確性，并利用可視化工具來評(píng)估和驗(yàn)證用于系統(tǒng)管理的有效的時(shí)間模式。基于鄰近度的技術(shù)考慮對(duì)象之間的鄰近性度量，例如“距離”。 文獻(xiàn)[13]提出了一種日志文件異常檢測(cè)方法，動(dòng)態(tài)地從示例文件中的某些模式產(chǎn)生規(guī)則，并能夠?qū)W習(xí)新類型的攻擊，同時(shí)盡量減少人類行為的需要，采用Hadoop平臺(tái)，提供分布式存儲(chǔ)和分布式數(shù)據(jù)處理來支持并行處理加快執(zhí)行速度。文獻(xiàn)[14]使用數(shù)據(jù)挖掘方法來分析Web日志文件獲取有關(guān)用戶的更多信息，描述了日志文件格式、類型和內(nèi)容，并提供了Web使用挖掘過程的概述。文獻(xiàn)[15]提取源代碼中的一組日志語句并生成可到達(dá)性圖，表示了日志語句的可到達(dá)關(guān)系，通過將有關(guān)日志語句的信息與信息檢索技術(shù)相結(jié)合創(chuàng)建日志消息，并根據(jù)這些消息的執(zhí)行單元對(duì)其分組跟蹤，提出了一種基于概率后綴樹的檢測(cè)算法，組織并區(qū)分序列所具有的顯著統(tǒng)計(jì)特性，在CloudStack測(cè)試平臺(tái)和Hadoop生產(chǎn)系統(tǒng)上試驗(yàn)，結(jié)果與其他四種檢測(cè)異常的算法相比，能夠有效地檢測(cè)運(yùn)行異常。由于在現(xiàn)實(shí)情況下異常點(diǎn)較少，文獻(xiàn)[16]提出一種基于隔離的異常檢測(cè)算法，創(chuàng)建了隔離樹可快速收斂但需要二次抽樣才可達(dá)到高精度?；诿芏鹊募夹g(shù)認(rèn)為低密度區(qū)域?qū)ο笫钱惓｜c(diǎn)。文獻(xiàn)[17]提出了一種局部離群點(diǎn)檢測(cè)算法，時(shí)間復(fù)雜度較高且不適用于大規(guī)模數(shù)據(jù)集和高維數(shù)據(jù)集的離群點(diǎn)檢測(cè)。文獻(xiàn)[18]提出了一種基于密度的檢測(cè)算法，該算法引入了局部離群因子(Local Outlier Factor，LOF)，并通過數(shù)據(jù)的 LOF 值的大小來判斷該數(shù)據(jù)是否異常，此類算法只適用于靜態(tài)的數(shù)據(jù)檢測(cè)，一旦數(shù)據(jù)量發(fā)生了波動(dòng)，就需要重新計(jì)算所有數(shù)據(jù)的 LOF 值，算法適應(yīng)性較差，不適合動(dòng)態(tài)數(shù)據(jù)的檢測(cè)過程。文獻(xiàn)[19]假設(shè)數(shù)據(jù)樣本服從一元高斯分布，將距離均值兩倍或三倍方差以外的測(cè)試樣本判斷為異常。

在大量日志中，異常日志僅僅是一小部分，人工篩選成本高而且效率低，標(biāo)記每條日志為正?；虍惓t更加困難。因此，文中擬提出一種無監(jiān)督學(xué)習(xí)和有監(jiān)督學(xué)習(xí)結(jié)合的異常檢測(cè)方法，以求在保持較高精確率的同時(shí)，具有較高的召回率。

1 檢測(cè)方法

Web日志是網(wǎng)站分析和網(wǎng)站數(shù)據(jù)倉(cāng)庫的數(shù)據(jù)基礎(chǔ)來源，目前常見的Web日志格式主要為兩類，一類是Apache的NCSA(National Center for Supercomputing Applications)日志格式，另一類是IIS(Internet Information Services)的W3C(World Wide Web Consortium)日志格式。本文采用Apache的NCSA日志格式，常見的NCSA日志格式包含訪問主機(jī)、標(biāo)識(shí)符、授權(quán)用戶、日期時(shí)間、請(qǐng)求、狀態(tài)碼、傳輸字節(jié)數(shù)、來源頁面和用戶代理，示例為

222.X.X.X [27/Oct/2019:14:50:28+0800]“GET /my/ HTTP/1.1” 303 440 “Mozilla/5.0(Windows NT 10.0;Win64;x64)AppleWebKit/537.36(KHTML,like Gecko)Chrome/71.0.3578.98 Safari/537.36”

檢測(cè)過程如下：

① 對(duì)源日志進(jìn)行詞的切分，考慮到上下文的聯(lián)系，運(yùn)用GloVe方法對(duì)日志進(jìn)行向量化，構(gòu)建單詞的詞向量;

② 運(yùn)用K-Means方法進(jìn)行聚類，得到分類后將分類標(biāo)簽追加到詞向量的末尾;

③ 在測(cè)試日志上運(yùn)用窗口為10，步長(zhǎng)為5的滑動(dòng)窗口每次取10條日志，運(yùn)用GloVe方法進(jìn)行向量化得到無標(biāo)簽的向量組;

④ 利用K-近鄰(K-nearest Neighbors,KNN)方法檢測(cè)每個(gè)向量所屬的類別和其對(duì)應(yīng)的概率，根據(jù)概率和確定向量組所屬的類別。

1.1 向量模板構(gòu)建

由于日志的數(shù)據(jù)量大、異常出現(xiàn)的情況少，對(duì)每條日志都進(jìn)行標(biāo)注顯然是不可行的。日志一般由訪問主機(jī)、請(qǐng)求、狀態(tài)碼、傳輸字節(jié)數(shù)、來源頁面和用戶代理等組成，其表示出來的語義由每個(gè)單詞組成，那么每個(gè)單詞和其所在的日志所表達(dá)的意思就存在包含的關(guān)系，明白一條日志的語義不僅與其中的一個(gè)單詞有關(guān)，還涉及到每個(gè)單詞與其前后的聯(lián)系。潛在語義分析(Latent Semantic Analysis,LSA)的復(fù)雜度高、計(jì)算代價(jià)大，而且所有單詞權(quán)重一致，Word 2vec不能充分利用語料，為了保留每個(gè)單詞和單詞與上下文的聯(lián)系，采用GloVe方法[20]將日志映射為向量。單詞映射后的詞向量示例：

POST -0.195 446 -0.574 467 -0.470 006

0.429 785 0.130 880 -0.439 768 0.209 260

-0.093 765 0.216 039 0.662 611 0.005 264

0.467 367 -0.430 639 -0.561 740 -0.195 026

0.382 339 -0.738 498 1.108 774 0.005 039

-0.290 427 0.423 914 0.717 930 -0.402 835

-0.599 006 0.704 752 -0.237 082 0.177 782

0.116 570 0.605 918 0.336 175 1.160 042

0.641 670 1.163 572 -0.247 168 -1.088 245

0.662 692 0.633 095 -0.070 681 -0.451 162

-0.541 639 -0.225 370 -0.868 071 -0.364 506

0.273 865 0.478 514 -0.686 345 1.153 848

-0.483 402 -0.055 478 -0.264 137

利用全局矩陣分解和局部上下文窗口兼顧較長(zhǎng)范圍的全局信息和短距離的單詞上下文信息，保留了每條日志中的每個(gè)單詞的語義信息，其模型目標(biāo)函數(shù)為

(1)

(2)

其中x為式(1)中的Xij，根據(jù)文獻(xiàn)[20]可知，α取3/4，xmax取100時(shí)效果最好。

通過GloVe對(duì)單詞進(jìn)行映射，將日志分為單詞和其對(duì)應(yīng)的向量，去掉單詞內(nèi)容僅留下向量，得到K-means算法所需要輸入的符合標(biāo)準(zhǔn)的數(shù)據(jù)。

1.2 K-means聚類

將得到的向量數(shù)據(jù)集輸入K-means聚類算法，輸入K值即可得到分類的向量結(jié)果。將向量數(shù)據(jù)分類主要是為了給數(shù)據(jù)標(biāo)記，作為訓(xùn)練數(shù)據(jù)輸入。實(shí)驗(yàn)過程中給出一組無標(biāo)簽數(shù)據(jù)集：

(3)

將數(shù)據(jù)集分為k個(gè)類C=C1，C2，…,Ck,損失函數(shù)為

(4)

每個(gè)類中的中心點(diǎn)為

(5)

K-Means算法使用貪心策略[21-22]求得一個(gè)近似解，步驟如下：

① 在樣本中選擇k個(gè)點(diǎn)充當(dāng)中心點(diǎn)；② 計(jì)算所有點(diǎn)到中心點(diǎn)的距離dist((xi),uj),把樣本點(diǎn)劃入最近的類中x(i)屬于u(near)；③ 根據(jù)樣本點(diǎn)重新計(jì)算簇中心；④ 重復(fù)②③。

實(shí)驗(yàn)使用K-Means聚類將向量映射到空間中形成不同的簇類，以不同的顏色區(qū)分，如圖1所示，聚類完成后將得到的分類標(biāo)簽添加到向量數(shù)據(jù)集中作為訓(xùn)練數(shù)據(jù)。

圖1 聚類結(jié)果

1.3 KNN異常檢測(cè)

實(shí)驗(yàn)以滑動(dòng)窗口的方式選取測(cè)試日志，窗口大小為10，步長(zhǎng)為5。對(duì)其進(jìn)行向量化，對(duì)每一條向量都進(jìn)行預(yù)測(cè)，得到其所屬類別Ci和概率Pi，分別累加得到最后的概率和為

(6)

選出概率最大的一類作為其所屬分類，其核心代碼為

S:source tagged data/輸入帶標(biāo)簽的數(shù)據(jù)；

T:test vector data/輸入測(cè)試向量數(shù)據(jù)；

W:windows size/輸入窗口大小。

for each vector in W/累加向量概率，取最大值作為結(jié)果：

p(vector)+= p(vector)；

if p(vector) > result；

result= p(vector)。

計(jì)算步驟如下：

① 計(jì)算測(cè)試數(shù)據(jù)與各個(gè)訓(xùn)練數(shù)據(jù)之間的距離；

② 按照距離的遞增關(guān)系進(jìn)行排序；

③ 選取距離最小的K個(gè)點(diǎn)；

④ 確定前K個(gè)點(diǎn)所在類別的出現(xiàn)頻率；

⑤ 返回前K個(gè)點(diǎn)中出現(xiàn)頻率最高的類別作為測(cè)試數(shù)據(jù)的預(yù)測(cè)分類。

對(duì)單詞的詞向量分類后的結(jié)果示例為

Your input is:[‘0.018 071’‘-0.035 667’

‘0.010 582’‘0.029 942’‘0.018 918’

‘0.063 902’‘0.004 891’‘-0.021 608’

‘0.042 474’‘0.023 72’‘-0.040 775’

‘-0.012 949’‘-0.036 745’‘0.030 719’

‘-0.006 368’‘0.057 134’‘0.015 395’

‘0.068 345’‘0.018 37’‘-0.001 688’

‘0.023 931’‘0.044 815’‘-0.011 621’

‘-0.003 934’‘0.017 733’‘-0.015 501’

‘0.040 929’‘0.001 506’‘-0.054 238’

‘-0.047 16’‘-0.034 344’‘-0.010 893’

‘-0.024 657’‘0.030 823’‘0.024 507’

‘-0.008 823’‘-0.055 855’‘-0.017 933’

‘0.054 512’‘-0.033 674’‘-0.023 098’

‘-0.077 288’‘-0.072 619’‘-0.021 143’

‘0.045 811’‘-0.004 346’‘0.024 517’

‘-0.034 229’‘0.056 217’‘0.023 467’]

and classified to class:1

2 實(shí)驗(yàn)及結(jié)果

2.1 實(shí)驗(yàn)環(huán)境及數(shù)據(jù)集

為驗(yàn)證文中方法的有效性，實(shí)驗(yàn)環(huán)境在服務(wù)器上配置，處理器為Intel Xeon(R) CPU E5-2620 v3@2.40 GHz×24，32GRAM，操作系統(tǒng)為Ubuntu 18.04.2 LTS(64位)。實(shí)驗(yàn)數(shù)據(jù)集來自于某高校Model平臺(tái)Apache服務(wù)器上的Web訪問日志，共33 649條記錄。

2.2 評(píng)價(jià)標(biāo)準(zhǔn)

由于日志數(shù)據(jù)量較大，且正常日志多異常日志少，因此利用混淆矩陣來檢測(cè)模型的準(zhǔn)確性。規(guī)定“1”為正類，代表異常；“0”為負(fù)類，代表合法。混淆矩陣是一個(gè)包含兩個(gè)維度(“實(shí)際”和“預(yù)測(cè)”)的表格和兩個(gè)維度的“類別”集合。其中，行代表預(yù)測(cè)數(shù)據(jù)，列代表實(shí)際數(shù)據(jù)，見表1。

表1 混淆矩陣

表1中，TP為正確肯定，指實(shí)際為正例，預(yù)測(cè)也為正例；FN為錯(cuò)誤否定(漏報(bào))，指實(shí)際為正例，預(yù)測(cè)為負(fù)例；FP 為錯(cuò)誤肯定(誤報(bào))，指實(shí)際為負(fù)例，預(yù)測(cè)為正例；TN為正確否定，指實(shí)際為負(fù)例，預(yù)測(cè)也為負(fù)例。

2.3 模型整體性能評(píng)價(jià)

對(duì)日志數(shù)據(jù)進(jìn)行向量化，利用GloVe方法把日志映射為50維向量，得到的結(jié)果是每個(gè)單詞及其對(duì)應(yīng)的向量。將得到的向量進(jìn)行K-means聚類，聚類完成后進(jìn)行標(biāo)記，得到一組帶有標(biāo)簽的向量數(shù)據(jù)，將其作為訓(xùn)練數(shù)據(jù)。取新的一組日志數(shù)據(jù)，同樣利用GloVe方法對(duì)其進(jìn)行向量化，得到一組無標(biāo)簽的向量，將這組無標(biāo)簽的向量作為測(cè)試數(shù)據(jù)。將訓(xùn)練數(shù)據(jù)和測(cè)試數(shù)據(jù)輸入KNN算法中，即可得到測(cè)試數(shù)據(jù)中向量的所屬分類。

實(shí)驗(yàn)中，通過修改算法中的K值來觀測(cè)算法對(duì)于不同的參數(shù)表現(xiàn)出的不同性能。修改一次K值會(huì)出現(xiàn)一次結(jié)果，對(duì)這些結(jié)果進(jìn)行分析，不同K值的檢測(cè)結(jié)果見表2，同時(shí)對(duì)精確率、召回率和F1值作曲線對(duì)比，如圖2所示。

表2 不同K值的性能

從表2可以看出，隨著K值從2逐漸增大到5，損失函數(shù)先減小后增大，并且當(dāng)K值為2和3時(shí)能取到最低0.050，對(duì)應(yīng)的精確率、召回率和F1值取到最大。

從圖2可以看出，隨著K值從2逐漸增大到5，精確率、召回率和F1值先增大后減小，并且當(dāng)K值為2和3時(shí)能取到最高，分別為0.92,0.96,0.93。

圖2 不同K值的性能

將文中方法和Proposed,Logistic,Decision Tree，SVM和Random Forest等5種不同方法的異常檢測(cè)性能做比較，取精確率、召回率和F1值，結(jié)果如圖3所示。

圖3 不同方法性能比較

3 結(jié) 論

本文提出了一種K-Means和KNN結(jié)合的日志異常檢測(cè)方法。利用GloVe方法對(duì)日志用向量表示，用K-means方法將得到的向量分類并標(biāo)記，用滑動(dòng)窗口取測(cè)試日志切片，將測(cè)試日志向量化，用KNN方法對(duì)測(cè)試日志對(duì)應(yīng)的向量進(jìn)行預(yù)測(cè)，得到了預(yù)測(cè)分類結(jié)果。

結(jié)果表明，隨著K值從2逐漸增大到5，損失函數(shù)先減小后增大，并且當(dāng)K值為3和4時(shí)能取到最低為0.05，對(duì)應(yīng)的精確率、召回率和F1值取到最大，分別為0.92,0.96,0.93。文中方法和現(xiàn)有其他5種方法相比，在精確率相同的條件下有更高的召回率。