Jaccard改進算法在用戶實體行為分析分組異常檢測中的應用

蔣 明 方 圓

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

0 引 言

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

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

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

1 相關算法

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

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

1.1 Jaccard相似性算法

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

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

(1)

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

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

1.2 Jaccard相似性算法改進

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

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

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

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

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

(2)

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

(3)

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

另外，為了充分發(fā)揮現(xiàn)代CPU指令集的并發(fā)能力，可以采用x86平臺的AVX2/AVX512向量指令集以并發(fā)地進行位與運算，如_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；進行分組聚類計算時，可以采用一種簡單的策略進行聚類，即設定一個用戶間相似度閾值tu，如超過tu則可以認為是同組用戶，否則不是同組用戶，故分組的數(shù)量不定。具體算法流程如算法1所示。

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

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

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

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

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

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

Step4算法結(jié)束。

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

(4)

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

1.2.3主機訪問分析和訪問異常分析

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

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

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

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

(5)

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

(6)

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

2 實驗與分析

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

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

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

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

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

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

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

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

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

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

3 結(jié) 語

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

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

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

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