一種基于圖計(jì)算的網(wǎng)絡(luò)實(shí)體行為評(píng)估算法設(shè)計(jì)

楊正權(quán) 翟欣虎 秦益飛

一.引言

圖是一種揭示實(shí)體之間關(guān)系的語(yǔ)義網(wǎng)絡(luò)，以符號(hào)形式對(duì)現(xiàn)實(shí)世界的事物及其相互關(guān)系進(jìn)行形式化地描述。其基本組成單位“實(shí)體-關(guān)系-實(shí)體”三元組，以及實(shí)體及其相關(guān)屬性值對(duì)，實(shí)體間通過(guò)關(guān)系相互聯(lián)結(jié)構(gòu)成網(wǎng)狀的結(jié)構(gòu)。現(xiàn)階段圖計(jì)算在各個(gè)領(lǐng)域都有廣泛的應(yīng)用，例如：信息檢索/搜索，自然語(yǔ)言理解，問(wèn)答系統(tǒng)，推薦系統(tǒng)，公安刑偵，社交類(lèi)業(yè)務(wù)等。通過(guò)圖的方式可以更好的展示實(shí)體之間的關(guān)系。

互聯(lián)網(wǎng)上的各類(lèi)數(shù)據(jù)以圖的方式存儲(chǔ)則可以更清晰直觀的展現(xiàn)各個(gè)實(shí)體的行為以及實(shí)體間的關(guān)系。一種典型的場(chǎng)景是，當(dāng)用戶(hù)產(chǎn)生登錄運(yùn)營(yíng)商服務(wù)器，訪(fǎng)問(wèn)互聯(lián)網(wǎng)網(wǎng)站，下載文件等行為時(shí)，以及運(yùn)營(yíng)商內(nèi)部一些資產(chǎn)服務(wù)器上的應(yīng)用自動(dòng)訪(fǎng)問(wèn)互聯(lián)網(wǎng)用于軟件更新，一些監(jiān)控服務(wù)對(duì)其他資產(chǎn)服務(wù)器進(jìn)行安全掃描等等。運(yùn)營(yíng)商都會(huì)記錄下這些行為日志并進(jìn)行相應(yīng)的分析審計(jì)。通常的行為日志內(nèi)容表述如下：

A用戶(hù) - 在某個(gè)時(shí)間 - 登錄了 - a應(yīng)用

B用戶(hù) - 在某個(gè)時(shí)間 - 訪(fǎng)問(wèn)了 - b網(wǎng)站

C用戶(hù) - 在某個(gè)時(shí)間 - 下載了 - c文件

A設(shè)備 - 在某個(gè)時(shí)間 - 連接了 - a服務(wù)

B應(yīng)用 - 在某個(gè)時(shí)間 - 掃描了 - C設(shè)備

上述日志條目中，頭尾兩端的字段為網(wǎng)絡(luò)實(shí)體（用戶(hù)，設(shè)備，應(yīng)用等），中間的字段為關(guān)系（登錄，訪(fǎng)問(wèn)，下載，連接，掃描等），時(shí)間屬性則作為實(shí)體或關(guān)系的屬性值。

使用圖的形式展現(xiàn)網(wǎng)絡(luò)實(shí)體行為關(guān)系更為清晰直觀，但存在的問(wèn)題是當(dāng)網(wǎng)絡(luò)規(guī)模變大，網(wǎng)絡(luò)中實(shí)體數(shù)量大幅增加時(shí)，例如實(shí)體數(shù)量達(dá)到數(shù)以千計(jì)萬(wàn)計(jì)時(shí)，如此龐大的數(shù)量以圖的形式展現(xiàn)將變的無(wú)法適應(yīng)，審計(jì)人員無(wú)法從千萬(wàn)個(gè)節(jié)點(diǎn)以及千萬(wàn)條邊中找出需要關(guān)注最有價(jià)值的數(shù)據(jù)。所以采用圖的形式展現(xiàn)，和傳統(tǒng)數(shù)據(jù)表形式展現(xiàn)相比同樣需要一套數(shù)據(jù)的評(píng)估排序篩選的方法，以找出最有價(jià)值的數(shù)據(jù)。

從龐大的圖數(shù)據(jù)集中找出更有價(jià)值的數(shù)據(jù)用于呈現(xiàn)有一些方法，比較常見(jiàn)的一種是在圖中為每個(gè)實(shí)體計(jì)算若干項(xiàng)評(píng)估指標(biāo)，例如該實(shí)體的最后更新時(shí)間，該實(shí)體出現(xiàn)的次數(shù)，該實(shí)體關(guān)聯(lián)關(guān)系數(shù)等。審計(jì)人員從若干項(xiàng)指標(biāo)中人工選擇需要關(guān)注的按數(shù)值大小按升序或降序排列，最終篩選出topN項(xiàng)實(shí)體及其關(guān)聯(lián)關(guān)系。

進(jìn)一步出現(xiàn)了上述方法的改進(jìn)方法，在計(jì)算出每個(gè)實(shí)體的若干項(xiàng)評(píng)估指標(biāo)的基礎(chǔ)上，給每種指標(biāo)賦一個(gè)經(jīng)驗(yàn)權(quán)重值，再計(jì)算所有指標(biāo)的加權(quán)平均值，審計(jì)人員直接按最終的加權(quán)平均值的數(shù)值大小升序或降序排列實(shí)體，同樣最終列出topN項(xiàng)實(shí)體及其關(guān)聯(lián)關(guān)系。

針對(duì)上述例舉的現(xiàn)有方法中的第一種，最大的弊端是通過(guò)單個(gè)指標(biāo)的排序并不能完整的評(píng)價(jià)某個(gè)實(shí)體的真實(shí)情況，并且這種單一維度的評(píng)價(jià)方法本質(zhì)上和采用圖表方式的存儲(chǔ)并無(wú)本質(zhì)區(qū)別，并不能很好發(fā)揮出圖的關(guān)聯(lián)關(guān)系特性。

針對(duì)上述例舉的現(xiàn)有方法的改進(jìn)方法，該方法雖然通過(guò)多個(gè)指標(biāo)對(duì)實(shí)體做了多維度的綜合評(píng)估，但其對(duì)每種指標(biāo)權(quán)重的選擇完全基于人工經(jīng)驗(yàn)，而這種基于經(jīng)驗(yàn)確定的權(quán)重值并不能保證其合理性，不合理的權(quán)重值會(huì)導(dǎo)致某幾項(xiàng)指標(biāo)在計(jì)算加權(quán)平均后完全失去了效果，影響最終的評(píng)估結(jié)果。

和上述兩種現(xiàn)有方法相比較，本文設(shè)計(jì)的算法避免了通過(guò)單個(gè)指標(biāo)對(duì)實(shí)體評(píng)估的單一性，同時(shí)在采用多個(gè)指標(biāo)綜合評(píng)估的基礎(chǔ)上，改進(jìn)了通過(guò)人工設(shè)置經(jīng)驗(yàn)權(quán)重這種不太合理的方法，充分利用了圖的特性，采用一種基于動(dòng)態(tài)指標(biāo)的評(píng)估方法，可以更加全面準(zhǔn)確的對(duì)實(shí)體進(jìn)行評(píng)估，在圖中篩選并展現(xiàn)出更合理的網(wǎng)絡(luò)實(shí)體及其關(guān)聯(lián)關(guān)系。

二.網(wǎng)絡(luò)實(shí)體行為評(píng)估算法設(shè)計(jì)

（一）評(píng)估算法總體流程設(shè)計(jì)

運(yùn)營(yíng)商記錄的其網(wǎng)絡(luò)中各種網(wǎng)絡(luò)實(shí)體的各種操作記錄的日志，提取抽象以后通常都可以用以下屬性來(lái)描述：

上表中舉例的行為記錄表示：

用戶(hù)Tom在2020.08.01 12：23：45下載了名叫Manual的pdf文件。

通常情況下，運(yùn)營(yíng)商服務(wù)器每時(shí)每刻都會(huì)記錄下上述大量的行為日志，本設(shè)計(jì)算法收到這些日志后，按如下流程處理：

步驟①，獲取指定時(shí)間范圍內(nèi)運(yùn)營(yíng)商服務(wù)器所產(chǎn)生的各種行為日志，時(shí)間范圍長(zhǎng)短不做限制。

步驟②，將日志中的“實(shí)體”以及“作用對(duì)象實(shí)體”作為頂點(diǎn)，“行為”作為邊，采用圖的方法存儲(chǔ)，即按頂點(diǎn)的關(guān)鍵字分組。

步驟③，統(tǒng)計(jì)圖中上述指定時(shí)間范圍內(nèi)的每個(gè)頂點(diǎn)的各項(xiàng)指標(biāo)，即每一組中實(shí)體的相關(guān)指標(biāo)，這些指標(biāo)包括并不限于：頂點(diǎn)上報(bào)次數(shù)，度中心性，緊密中心性，中介中心性等。

步驟④，計(jì)算每個(gè)實(shí)體每種指標(biāo)在上述時(shí)間范圍內(nèi)的數(shù)據(jù)中相應(yīng)的概率密度（對(duì)于離散型隨機(jī)變量即指其分布律），即該計(jì)算的概率密度數(shù)值只基于本次獲取的這批數(shù)據(jù)得出。

步驟⑤，計(jì)算每個(gè)實(shí)體所有指標(biāo)概率密度結(jié)果的數(shù)學(xué)期望，即求每個(gè)頂點(diǎn)所有指標(biāo)的算術(shù)平均值。

步驟⑥，將每個(gè)實(shí)體按按數(shù)學(xué)期望大小排序，選出其topN實(shí)體及其關(guān)聯(lián)關(guān)系作為最終結(jié)果展現(xiàn)給審計(jì)人員查看。

（二）實(shí)體行為圖存儲(chǔ)方式設(shè)計(jì)

圖是由（V， E）來(lái)表示的，對(duì)于無(wú)向圖來(lái)說(shuō)，其中 V =（v0， v1， ... ， vn），E = { （vi，vj） （0 <= i， j <= n且i 不等于j）}，對(duì)于有向圖，E = { < vi，vj > （0 <= i， j <= n且i 不等于j）}。V是頂點(diǎn)的集合，E是邊的集合。圖可以有兩種典型的表示方法，一個(gè)是鄰接矩陣，另一個(gè)是鄰接鏈表，這兩種方法都可以表示有向圖和無(wú)向圖。

鄰接矩陣是用兩個(gè)數(shù)組來(lái)表示一個(gè)圖：一個(gè)一維數(shù)組用來(lái)存儲(chǔ)每個(gè)頂點(diǎn)的信息；一個(gè)二維數(shù)組（即鄰接矩陣）用來(lái)存儲(chǔ)圖中的邊或弧信息。對(duì)于圖G =（V， E）來(lái)說(shuō)，鄰接矩陣matrix是一個(gè)|V|*|V|的方陣，假設(shè)1 <= i， j <= |V|，如果matrix[i][j] == 0，則表示頂點(diǎn)i和頂點(diǎn)j之間沒(méi)有邊相連；反之，如果matrix[i][j] ！= 0，則表示表示頂點(diǎn)i和頂點(diǎn)j之間有邊相連，且matrix[i][j]存儲(chǔ)的值即為該邊的權(quán)重。

鄰接鏈表是一種不錯(cuò)的圖存儲(chǔ)結(jié)構(gòu)，由于它在表示稀疏圖的時(shí)候非常緊湊而成為通常的選擇。對(duì)于圖G =（V， E）來(lái)說(shuō)，在其鄰接鏈表表示中，每個(gè)結(jié)點(diǎn)對(duì)應(yīng)一條鏈表，因此這個(gè)圖里有V條鏈表。假設(shè)用一個(gè)V維的數(shù)組Adj來(lái)存儲(chǔ)這V條鏈表，且Adj[i]表示的是結(jié)點(diǎn)i對(duì)應(yīng)的鏈表，那么Adj[i]這條鏈表里存儲(chǔ)的就是所有與節(jié)點(diǎn)i之間有邊相連的結(jié)點(diǎn)，即與結(jié)點(diǎn)i相鄰的結(jié)點(diǎn)。

在本算法適用場(chǎng)景中，采用有向圖來(lái)描述網(wǎng)絡(luò)實(shí)體的行為關(guān)系并采用鄰接鏈表的方式存儲(chǔ)數(shù)據(jù)更為合適。以用戶(hù)Tom在2020.08.01 12：23：45下載了名叫Manual的pdf文件這條行為日志為例，將“Tom”和“Manual.pdf”這類(lèi)關(guān)鍵字唯一的實(shí)體名作為圖的頂點(diǎn)，此次的“下載”行為作為從頂點(diǎn)“Tom”到頂點(diǎn)“Manual.pdf”的有向邊。即：

1. 采用實(shí)體名作為頂點(diǎn)唯一性的關(guān)鍵字；

2. 采用和有向邊相鄰的一組兩個(gè)實(shí)體名作為邊唯一性的聯(lián)合關(guān)鍵字；

3. 給每個(gè)頂點(diǎn)設(shè)置特征數(shù)組：（上報(bào)次數(shù)，度中心性，緊密中心性，中介中心性，...）。

反復(fù)將行為日志抽象提取后加入圖并計(jì)算頂點(diǎn)的屬性值即構(gòu)成了一個(gè)復(fù)雜的有向圖。圖上的每個(gè)頂點(diǎn)應(yīng)該都有1-N條相連接的邊，同理也就擁有1-N個(gè)相鄰的頂點(diǎn)，即采用鄰接鏈表的方式按頂點(diǎn)的關(guān)鍵字進(jìn)行了分組操作。

（三）實(shí)體行為評(píng)估算法設(shè)計(jì)

評(píng)估算法主要涉及對(duì)圖中頂點(diǎn)相關(guān)特征的計(jì)算，具體如下：

1. 頂點(diǎn)上報(bào)次數(shù)：當(dāng)行為日志中的實(shí)體名在圖的頂點(diǎn)集V中已經(jīng)存在，則該頂點(diǎn)的上報(bào)次數(shù)加1，統(tǒng)計(jì)一段時(shí)間內(nèi)每個(gè)頂點(diǎn)的上報(bào)次數(shù)。

2. 度中心性：該特征是計(jì)算頂點(diǎn)上傳入和傳出關(guān)系的數(shù)量，可以用于在圖中查找“熱”（popular）的節(jié)點(diǎn)。在本算法適用的場(chǎng)景中，即統(tǒng)計(jì)一段時(shí)間內(nèi)每個(gè)頂點(diǎn)的鄰接頂點(diǎn)數(shù)。

3. 緊密中心性：該特性是一種檢測(cè)節(jié)點(diǎn)通過(guò)子圖傳播信息有效性的方法。該方法度量是節(jié)點(diǎn)與所有其他節(jié)點(diǎn)的距離近的程度。在所有節(jié)點(diǎn)對(duì)的最短路徑計(jì)算的基礎(chǔ)上，緊密中心性算法計(jì)算一個(gè)節(jié)點(diǎn)到所有其他節(jié)點(diǎn)的距離之和。然后將得到的和求倒數(shù)，以確定該節(jié)點(diǎn)的緊密性中心性得分。節(jié)點(diǎn)的緊密中心性用以下的公式來(lái)計(jì)算：

其中，u是一個(gè)節(jié)點(diǎn)，n是圖中的節(jié)點(diǎn)數(shù)，d（u，v）是另一個(gè)節(jié)點(diǎn)V和U之間的最短路徑距離。

更常見(jiàn)的是將該分?jǐn)?shù)歸一化，使該得分代表最短路徑的平均長(zhǎng)度，而不是它們的總和。這種調(diào)整允許比較不同大小圖節(jié)點(diǎn)的緊密性中心性。

歸一化后的緊密中心性公式如下：

在本算法適用場(chǎng)景中，即篩選出一段時(shí)間范圍內(nèi)的所有頂點(diǎn)和邊，在此基礎(chǔ)上計(jì)算每個(gè)頂點(diǎn)的緊密中心度。

4. 中介中心性：該特征是一種檢測(cè)節(jié)點(diǎn)對(duì)圖中信息或資源流的影響程度的方法。它通常用于查找充當(dāng)從圖的一部分到另一部分的橋梁型節(jié)點(diǎn)。該算法首先計(jì)算連接圖中每對(duì)節(jié)點(diǎn)之間的最短（權(quán)重）路徑。每個(gè)節(jié)點(diǎn)都會(huì)根據(jù)這些通過(guò)該節(jié)點(diǎn)的最短路徑的數(shù)量得到一個(gè)分?jǐn)?shù)。經(jīng)過(guò)節(jié)點(diǎn)的最短路徑越多，該節(jié)點(diǎn)的得分越高。

中介中心性是將最短路徑通過(guò)如下公式計(jì)算后累加的結(jié)果：

在公式中u是一個(gè)節(jié)點(diǎn)，p是節(jié)點(diǎn)s和t之間最短路徑的數(shù)量，p（u）是s和t之間通過(guò)u的最短路徑的數(shù)量。

同理在本算法適用場(chǎng)景中，即篩選出一段時(shí)間范圍內(nèi)的所有頂點(diǎn)和邊，在此基礎(chǔ)上計(jì)算每個(gè)頂點(diǎn)的中介中心度。

計(jì)算出一段時(shí)間范圍內(nèi)圖中每個(gè)頂點(diǎn)的上述4種或更多特征的特征數(shù)組后，將該批數(shù)據(jù)中出現(xiàn)的不重復(fù)的頂點(diǎn)對(duì)應(yīng)的其中一種特征作為離散型隨機(jī)變量，將該特征的數(shù)值作為隨機(jī)變量的出現(xiàn)次數(shù)，計(jì)算這批數(shù)據(jù)中不重復(fù)的頂點(diǎn)的所有特征相應(yīng)的分布律，即每個(gè)頂點(diǎn)對(duì)應(yīng)特征在所有頂點(diǎn)對(duì)應(yīng)特征中的占比。舉例如下：選取了一段時(shí)間范圍的行為日志按圖存儲(chǔ)后有3個(gè)頂點(diǎn)，計(jì)算這3個(gè)頂點(diǎn)對(duì)應(yīng)的特征數(shù)組分別為（20，3，0.3，4），（4，1，1，2），（12，2，0.6，1.4），那么對(duì)于3個(gè)頂點(diǎn)特征分布律數(shù)組為：

計(jì)算每個(gè)頂點(diǎn)特征分布律數(shù)組中所有數(shù)值的數(shù)學(xué)期望，最終結(jié)果即為每個(gè)頂點(diǎn)的評(píng)估值，按評(píng)估值大小進(jìn)行排序，選出topN對(duì)應(yīng)的頂點(diǎn)即最終被篩選出的實(shí)體及其對(duì)應(yīng)的行為關(guān)系。

三.網(wǎng)絡(luò)實(shí)體行為評(píng)估算法驗(yàn)證

（一）驗(yàn)證數(shù)據(jù)建立

Apache JMeter是Apache組織開(kāi)發(fā)的基于Java的壓力測(cè)試工具，用于對(duì)軟件做壓力測(cè)試，JMeter 可用于模擬在服務(wù)器、網(wǎng)絡(luò)或者其他對(duì)象上附加高負(fù)載以測(cè)試其提供服務(wù)的受壓能力，或者分析其提供的服務(wù)在不同負(fù)載條件下的總性能情況。

驗(yàn)證方法基于JMeter搭建，使用一臺(tái)服務(wù)器作為代理網(wǎng)關(guān)，可以記錄下接入用戶(hù)的上網(wǎng)日志，另一臺(tái)PC終端上運(yùn)行JMeter，用于模擬多用戶(hù)的互聯(lián)網(wǎng)訪(fǎng)問(wèn)行為。設(shè)置JMeter模擬50名不同的用戶(hù)，隨機(jī)訪(fǎng)問(wèn)100個(gè)預(yù)選出的互聯(lián)網(wǎng)網(wǎng)站，為每位用戶(hù)設(shè)置不同的訪(fǎng)問(wèn)網(wǎng)站數(shù)量閾值以及訪(fǎng)問(wèn)的頻率閾值，從網(wǎng)關(guān)服務(wù)器收集一天內(nèi)所有訪(fǎng)問(wèn)請(qǐng)求記錄約80萬(wàn)條作為待檢測(cè)樣本。同時(shí)記錄下JMeter針對(duì)每個(gè)用戶(hù)訪(fǎng)問(wèn)量及訪(fǎng)問(wèn)頻率的設(shè)置，如下：

將上述數(shù)據(jù)采用本文設(shè)計(jì)的圖方式存儲(chǔ)并分析評(píng)估每個(gè)模擬用戶(hù)的行為，得到每個(gè)用戶(hù)最終的評(píng)估值的排名，同時(shí)也給出每個(gè)特性單獨(dú)的排名，如下：

（二）驗(yàn)證方法及結(jié)果分析

對(duì)于無(wú)監(jiān)督的預(yù)測(cè)結(jié)果業(yè)界并沒(méi)有評(píng)估結(jié)果“好壞”的統(tǒng)一標(biāo)準(zhǔn)，本驗(yàn)證通過(guò)將評(píng)估結(jié)果和互聯(lián)網(wǎng)領(lǐng)域比較常用及容易理解的PageRank熱度排名的方式做對(duì)比，計(jì)算50名模擬用戶(hù)的排名和PageRank排名兩數(shù)組的相關(guān)系數(shù)，系數(shù)約接近于1表示評(píng)估的排名和PageRank排名越接近。驗(yàn)證結(jié)果如下：

結(jié)果表明，本算法評(píng)估的結(jié)果和PageRank排名最接近，可以認(rèn)為是通常情況下比較認(rèn)可的結(jié)果。

四.結(jié)束語(yǔ)

因?yàn)楸疚乃枋龅姆椒ㄍㄟ^(guò)多個(gè)維度對(duì)網(wǎng)絡(luò)實(shí)體進(jìn)行評(píng)估，相比于人工選擇單一維度的評(píng)估，評(píng)估結(jié)果更全面。

同時(shí)本文所述方法基于預(yù)選出的實(shí)際時(shí)間范圍的數(shù)據(jù)，對(duì)網(wǎng)絡(luò)實(shí)體動(dòng)態(tài)計(jì)算多個(gè)維度權(quán)重的相對(duì)比例而不是固定不變的比例值，評(píng)估結(jié)果的準(zhǔn)確性更高。

作者單位：江蘇易安聯(lián)網(wǎng)絡(luò)技術(shù)有限公司