Jaccard改進(jìn)算法在用戶實體行為分析分組異常檢測中的應(yīng)用

蔣 明 方 圓

(國家電網(wǎng)安徽省電力有限公司信息通信分公司 安徽 合肥 230009)

0 引 言

用戶實體行為分析(User Entity Behavior Analysis，UEBA)是現(xiàn)代安全信息事件管理系統(tǒng)(Security Information Event Management System，SIEMS)中對于安全事件進(jìn)行二次分析的重要手段，其主要分析的目標(biāo)是檢測主體(可理解為用戶、賬號、主機(jī)等，這些信息均可與實際用戶即自然人進(jìn)行關(guān)聯(lián))對于客體(可以理解為實體)相關(guān)操作中是否存在異常，實體可以是主機(jī)、服務(wù)/端口、文件夾/文件、系統(tǒng)定時任務(wù)、Windows主機(jī)的注冊表等。一般而言，這種分析的方法包括特征匹配、流式計算、基于機(jī)器學(xué)習(xí)的分析，其中基于機(jī)器學(xué)習(xí)的分析是用戶實體行為分析中比較重要的手段。在用戶實體行為分析中，可以對特征進(jìn)行匹配(如使用一些正則方法)或者使用流式計算(其本質(zhì)上也是一種特征匹配方式，只不過包含了對于多狀態(tài)機(jī)的處理)方法，對于無法使用特征分析的未知威脅則可以利用機(jī)器學(xué)習(xí)的方法進(jìn)行檢測。這些未知威脅檢測包括諸如對于數(shù)據(jù)竊取的分析、數(shù)據(jù)橫向移動的分析、賬號盜用分析、金融欺詐(如養(yǎng)號等)、用戶撞庫、拖庫等。

在實際應(yīng)用中，分組異?；蛴脩舴纸M異常也是一種特別需要關(guān)注的未知威脅，而且是非常重要的一種威脅，其判斷依據(jù)是根據(jù)歷史數(shù)據(jù)(主要是用戶對于系統(tǒng)的訪問日志或者是主機(jī)之間的訪問記錄)，對當(dāng)前需要檢測的數(shù)據(jù)進(jìn)行判斷；在實際分析中，系統(tǒng)將收集各類訪問日志，根據(jù)主體之間訪問的相似程度劃分為若干組，當(dāng)對相關(guān)數(shù)據(jù)進(jìn)行驗證時，計算其行為是否存在跨組訪問。本質(zhì)上，對于分組異常的分析是一種無監(jiān)督學(xué)習(xí)，需要利用諸如K-means、DBScan、山峰聚類、混合高斯、K近鄰等聚類分析算法。

由于在實際環(huán)境中，可以收集到的訪問日志中最多的就是主機(jī)之間的連接信息，系統(tǒng)可以比較方便地從諸如網(wǎng)絡(luò)流量探針或者如路由器、交換機(jī)等網(wǎng)絡(luò)設(shè)備的Netflow/sFlow統(tǒng)計信息中較為容易地獲得(相較于文件、注冊表等的訪問而言，如果需要獲取這些信息則應(yīng)在相關(guān)主機(jī)上安裝代理程序)，故分組異常分析的焦點一般也集中于主機(jī)之間的訪問關(guān)系，換言之，可以對主機(jī)間訪問進(jìn)行畫像，找出其中存在的異常行為，但由于一般在一個大型企業(yè)或?qū)W校網(wǎng)絡(luò)中，存在超大量的IP地址(對于一些特殊的大型企業(yè)級用戶而言，可能超過20萬個)，采用一般的聚類算法無法做到快速分析，從而導(dǎo)致實時性較差，故提出基于改進(jìn)的Jaccard相似性評估算法，此算法特別針對IP地址形成的數(shù)據(jù)向量，可以較大程度地提升處理速度，而且可以對保存的數(shù)據(jù)進(jìn)行壓縮。

1 相關(guān)算法

在用戶實體行為分析中，對于用戶分組異常的首要問題就是怎樣通過數(shù)據(jù)對用戶進(jìn)行分組，這需要評估用戶之間的相似程度，即用戶之間存在多少相似性，這些問題在一些電商網(wǎng)站中的應(yīng)用顯得尤其重要，特別是應(yīng)用協(xié)同過濾在商品推薦的場景下。

由于在本文中，分析的數(shù)據(jù)是來源于主機(jī)之間的訪問記錄，即主機(jī)之間的通信情況，而且主要是分析內(nèi)網(wǎng)主機(jī)之間的訪問，所以分析的焦點就是如何根據(jù)這些數(shù)據(jù)對相關(guān)訪問源主機(jī)進(jìn)行分組劃分。

1.1 Jaccard相似性算法

一般而言，用于評估相似性的算法主要包括如余弦夾角、局部敏感哈希、皮爾遜相關(guān)系數(shù)等方法，而針對主機(jī)訪問記錄，Jaccard相似性算法由于能比較好地適用此方面的數(shù)據(jù)分析，而且計算較為簡單，故在用戶相似性分析中采用基于Jaccard算法，其基本計算方法如下。

使用符號ui、uj分別表示現(xiàn)網(wǎng)中的兩個用戶，其訪問主機(jī)集合分別是Hi、Hj，而這兩個用戶的基于訪問主機(jī)的相似程度計算公式為：

(1)

在式(1)中用戶之間的相似度是通過它們訪問主機(jī)之間的情況來評判的，其分子是用戶訪問主機(jī)的交集而其分母則為用戶同時訪問主機(jī)的并集，當(dāng)然還有若干種Jaccard的變體，如文獻(xiàn)[1]中提出的基于權(quán)重的Jaccard相似度度量方法，文獻(xiàn)[2]中的相似矩陣方法，另如式(1)中分母修改為較大集合的元素數(shù)量等。但無論是哪種Jaccard方法，它們在分析諸如IP主機(jī)之間訪問行為的場合，都顯得捉襟見肘，而且在某種程度上可能不能正確反映不同用戶之間的訪問關(guān)系，其復(fù)雜度為O(mn2),其中:m為分組數(shù)量；n為用戶數(shù)量。

另外，本文參照文獻(xiàn)[3-9]給出了UEBA中的對于異常分組分析的一系列成套思路，但在這些文獻(xiàn)中并未提及分組異常檢測的具體方法，文獻(xiàn)[10]提出了針對網(wǎng)絡(luò)流量用戶行為異常檢測的一些方法，但未就分組異常檢測提出相關(guān)具體方案，其主要關(guān)注點仍是針對一些網(wǎng)絡(luò)數(shù)據(jù)特征的抽取。

1.2 Jaccard相似性算法改進(jìn)

1.2.1網(wǎng)段訪問分析

在前文中已經(jīng)提到，現(xiàn)實環(huán)境中可能存在超大規(guī)模的主機(jī)訪問記錄，其規(guī)模多達(dá)20余萬，而且它們可能來自不同的內(nèi)網(wǎng)網(wǎng)段(可能10、172、192等內(nèi)網(wǎng)均涉及到)，故這些數(shù)據(jù)離散程度過大，使用傳統(tǒng)的Jaccard相似性算法進(jìn)行集合計算所消耗的CPU性能相當(dāng)巨大，甚至是不可能完成的任務(wù)。

由于是針對IP主機(jī)的訪問關(guān)系分析，故可以對于數(shù)據(jù)進(jìn)行一些分層處理并對主機(jī)數(shù)據(jù)進(jìn)行一定的預(yù)備處理。

根據(jù)各主機(jī)訪問目標(biāo)機(jī)器的網(wǎng)段情況，使用{0,1}n向量來標(biāo)識其訪問的目標(biāo)網(wǎng)段，即通過這種方式先從網(wǎng)段的方面進(jìn)行劃分。如對于一個192.168子網(wǎng)網(wǎng)段，其包含了256子網(wǎng)，在實際實現(xiàn)時，使用32個字節(jié)的數(shù)組來表示，故可以涵蓋這256個子網(wǎng)，如某用戶(實際上是主機(jī))對某個子網(wǎng)的數(shù)據(jù)進(jìn)行訪問，則將其標(biāo)志值1，否則為0，對于存在n個用戶的系統(tǒng)而言，可以形式化地表示為：

A=[a1,a2,…，an]Tai∈{0,1}256

(2)

對于式(2)而言，矩陣A就是不同用戶的網(wǎng)段訪問關(guān)系矩陣，其中每個向量的維度均為256(即可以認(rèn)為是32個字節(jié))，而且為了計算統(tǒng)一起見，可以將式(1)中的分母部分進(jìn)行修改，則對于兩個用戶的相似度而言，可以變形為如下形式：

(3)

可以看出，在式(3)中分母部分已經(jīng)修改成了所有用戶針對所有網(wǎng)段的訪問關(guān)系，進(jìn)一步地，如果需要更為快速地進(jìn)行計算，可以直接將分母部分修改為256，從而加速整體計算；分子的交集計算部分可以直接采用二進(jìn)制位與方式，以做到最大程度的優(yōu)化。

另外，為了充分發(fā)揮現(xiàn)代CPU指令集的并發(fā)能力，可以采用x86平臺的AVX2/AVX512向量指令集以并發(fā)地進(jìn)行位與運算，如_mm256_and_pd或_mm512_and_pd等，位與運算的結(jié)果中包含多少個1即說明兩個用戶都訪問的網(wǎng)段有多少個；為獲取某個變量包含1的數(shù)量，算法采用最為快速的查表法(經(jīng)實驗，對于32個字節(jié)的計算約為1 000個CPU指令周期)。

1.2.2網(wǎng)段訪問聚類

根據(jù)不同用戶對于網(wǎng)段訪問的相似度計算可以形成相似度矩陣，它是一個實對稱陣，其行、列均為用戶數(shù)量，其對角線均為1；進(jìn)行分組聚類計算時，可以采用一種簡單的策略進(jìn)行聚類，即設(shè)定一個用戶間相似度閾值tu，如超過tu則可以認(rèn)為是同組用戶，否則不是同組用戶，故分組的數(shù)量不定。具體算法流程如算法1所示。

算法1網(wǎng)段訪問聚類

輸入：用戶網(wǎng)段訪問相似度矩陣。

輸出：用戶分組后的集類。

Step1初始化用戶分組集合(分組集合中的元素是對用戶的一個劃分，故元素也是集合)。

Step2從網(wǎng)段訪問相似度矩陣中獲取一個未分組用戶向量，將所有大于等于相似度閾值tu的對應(yīng)用戶加入分組集合中的一個元素。

Step3如集合為空，則將自身加入分組集合對應(yīng)元素；如存在未分組的用戶則轉(zhuǎn)Step2，如果用戶都已分組完成則轉(zhuǎn)Step4。

Step4算法結(jié)束。

最后的用戶分組集合形如{{u1,u2},{u3,u4,u5},…}，該集合用G0表示，形式化地可以表示為：

(4)

式中：集合U是所有用戶(或者是源主機(jī))組成的全集。

1.2.3主機(jī)訪問分析和訪問異常分析

與前文中對于網(wǎng)段訪問的分析類似，具體到某個C類網(wǎng)段而言(如是A類或者B類網(wǎng)段也可以最終分解到C類網(wǎng)段)，需要計算的最多只是254個主機(jī)地址(去除子網(wǎng)地址和廣播地址)，可以采用改進(jìn)的Jaccard相似性算法進(jìn)行計算，其公式也與式(2)、式(3)、式(4)無區(qū)別，只不過這里是針對不同的主機(jī)，即其向量中的每一維是否訪問了某臺主機(jī)，如訪問則為1，否則為0。

通過對于各個C類子網(wǎng)的訪問記錄計算，可以得到256個(針對B類網(wǎng)絡(luò))用戶分組集類{Gi}(下標(biāo)i的取值范圍在1到256之間)，每個Gi都是在不同子網(wǎng)下對于同一個用戶集合的劃分，對于用戶分組異常的判斷也基于這個集類以及對于網(wǎng)段訪問分組情況：{Gi}(i∈[1,256])。

在綜合判斷用戶是否存在分組異常時，遵循如下判斷方式，如存在：

?Uj∈G0Uj?G′0(ui∈Uj)

(5)

因此，針對各個網(wǎng)段主機(jī)訪問分組異常的情況，對于某個具體的用戶而言，本文算法采用異常分組比例來判斷：

(6)

在式(6)中，對于某一網(wǎng)段而言，其分子部分是對一個指示函數(shù)I的結(jié)果求和，其求和內(nèi)容主要為當(dāng)前用戶ui出現(xiàn)在分組異常的子網(wǎng)數(shù)量，而分母部分的含義則表示取歷史分組集合規(guī)模和當(dāng)前分組集合規(guī)模的大者(當(dāng)然分母也可以取別的形式，如僅歷史分組或當(dāng)前分組數(shù)量等)。故通過式(6)可以看出在此上下文中，分組異常是一個介于0和1之間的浮點數(shù)，在實際應(yīng)用時，可以設(shè)定閾值ta來評判異常分組的程度，一般可以設(shè)置為0.5。

2 實驗與分析

在實際驗證時，從運行系統(tǒng)中采樣了歷史上最近10天的相關(guān)主機(jī)訪問日志，約20億條，其主機(jī)IP地址為10.0.0.0/8的A類地址，包含了232個C類子網(wǎng)，共52 834個不同的IP地址。

然后對這些IP地址的近3日數(shù)據(jù)進(jìn)行采樣，分別使用傳統(tǒng)不分段、非并行、無位操作的Jaccard相似性算法以及本文的改進(jìn)后的Jaccard相似性算法實驗的性能結(jié)果，實驗平臺為Intel至強(qiáng)E5-2680 V4(此CPU支持AVX2/AVX512指令集)，64 GB內(nèi)存，操作系統(tǒng)為Ubuntu 18 LTS。表1是對于相關(guān)數(shù)據(jù)的訓(xùn)練情況，表2則是對于數(shù)據(jù)的驗證情況。

表1 數(shù)據(jù)訓(xùn)練

表2 數(shù)據(jù)驗證

在表1中，包含的源主機(jī)數(shù)量分別為1 000、2 000、5 000、10 000、20 000及50 000，訓(xùn)練時長單位為ms，可以看出在使用向量指令的情況下，其性能遠(yuǎn)遠(yuǎn)高于傳統(tǒng)的Jaccard算法，兩者相較大約相差約30倍(此數(shù)據(jù)主要為建立分組的時間，數(shù)據(jù)加載等時間消耗未統(tǒng)計在內(nèi)，而且數(shù)據(jù)是通過10次執(zhí)行得到的數(shù)學(xué)期望)。

表2與表1類似，包含的源主機(jī)數(shù)量分別為1 000、2 000、5 000、10 000、20 000及50 000，驗證時長單位為ms，可以看出在使用向量指令的情況下，其性能遠(yuǎn)遠(yuǎn)高于傳統(tǒng)的Jaccard算法，兩者也大約相差近30倍；如果采用多線程并發(fā)地進(jìn)行訓(xùn)練和驗證則速度更快。

改進(jìn)后的Jaccard算法明顯在這個較大規(guī)模的數(shù)據(jù)集上，特別是針對IPv4主機(jī)連接關(guān)系的分組上表現(xiàn)得遠(yuǎn)比傳統(tǒng)算法更快速；另外，它在數(shù)據(jù)訓(xùn)練上的提升也有良好表現(xiàn)。

通過利用網(wǎng)段劃分將用戶訪問記錄進(jìn)行分層處理，再利用Jaccard算法對相似性進(jìn)行計算，本文主要實現(xiàn)了一個基于多層模式下的改進(jìn)Jaccard相似性算法。利用本文方法可以在網(wǎng)段部分直接對驗證數(shù)據(jù)進(jìn)行篩選，這能夠極大地減少CPU計算量。

另外，由于通過使用基于二進(jìn)制位與操作的并行處理方法和用固定數(shù)值替代集合并集運算，也能在很大程度上對整體算法進(jìn)行加速，從而做到對超大規(guī)模數(shù)據(jù)的處理。

最后，由于本文算法采用了二進(jìn)制位方法表示訪問情況集合，故在相關(guān)數(shù)據(jù)的存儲上也極為節(jié)省空間，而且在對威脅進(jìn)行回溯時，獲取相關(guān)異常源來進(jìn)行展示也較為方便。

3 結(jié) 語

本文所提出的Jaccard改進(jìn)算法主要是針對IP主機(jī)間訪問的，對于一些其他的諸如用戶訪問文件/文件夾、注冊表、系統(tǒng)定時任務(wù)等也是可以應(yīng)用的，但如果在純IPv6環(huán)境下，針對IP地址的訪問分析，此方法可能需要做一些改動方可使用，其主要原因是IPv6包含了巨大的地址空間，當(dāng)然可以采用其他方法根據(jù)現(xiàn)網(wǎng)情況進(jìn)行建模。

由于本文主要分析的訪問記錄是針對內(nèi)網(wǎng)環(huán)境下的，但在有外網(wǎng)主機(jī)參與的情況下該如何高效地進(jìn)行分組是一個需要考慮的問題，初步想法應(yīng)還是根據(jù)訪問目標(biāo)的地理位置而非最終的訪問目的IP地址進(jìn)行，這在一定程度上對數(shù)據(jù)進(jìn)行了縮減，當(dāng)然也可以使用Jaccard算法進(jìn)行。

對于用戶的分組一般采用硬分組方法，即一個用戶只能屬于一個組，這種分類方法可能在一些場景下導(dǎo)致未必能非常真實地反映客觀情況，或者造成過多的離群數(shù)據(jù)，反而導(dǎo)致結(jié)果不可用，所以可以考慮采用軟分組方法處理之，即針對用戶給出其所屬用戶組的概率，依照此概率進(jìn)行分組，從而在一定程度上避免硬分組所帶來的問題。

對于一些實在無法分組的離群數(shù)據(jù)的處理也是今后需要解決的問題，這可能是需要最終算法檢驗結(jié)果是否可用并能在實際使用時是否適用的重要方面。