基于布魯姆過濾器的計算機動態(tài)取證技術(shù)研究

鄢喜愛　常衛(wèi)東　譚　敏

(湖南警察學(xué)院信息技術(shù)系　湖南 長沙 410138)

(網(wǎng)絡(luò)犯罪偵察湖南省普通高等學(xué)校重點實驗室　湖南 長沙 410138)

?

基于布魯姆過濾器的計算機動態(tài)取證技術(shù)研究

鄢喜愛常衛(wèi)東譚敏

(湖南警察學(xué)院信息技術(shù)系湖南 長沙 410138)

(網(wǎng)絡(luò)犯罪偵察湖南省普通高等學(xué)校重點實驗室湖南 長沙 410138)

摘要靜態(tài)取證時效性不足，動態(tài)取證則可獲得更為真實、實時的證據(jù)。動態(tài)取證最關(guān)鍵的是證據(jù)識別。證據(jù)識別本質(zhì)上是對網(wǎng)絡(luò)數(shù)據(jù)流進(jìn)行分類，以判斷其行為是合法還是非法。布魯姆過濾器采用一個位串表示數(shù)據(jù)集合并有效支持元素的哈希查詢，從而被廣泛應(yīng)用于包分類算法中。首先對標(biāo)準(zhǔn)布魯姆過濾器算法進(jìn)行分析，并對算法存在的缺陷進(jìn)行改進(jìn)。在此基礎(chǔ)上，設(shè)計一個基于布魯姆過濾器的分布式計算機動態(tài)取證系統(tǒng)，并采取安全有效措施對證據(jù)進(jìn)行傳送。實驗表明：該系統(tǒng)能對網(wǎng)絡(luò)攻擊行為進(jìn)行動態(tài)地檢測，且檢測準(zhǔn)確率高、誤判率低。

關(guān)鍵詞信息安全計算機取證布魯姆過濾器動態(tài)取證

RESEARCH ON DYNAMIC COMPUTER FORENSICS BASED ON BLOOM FILTERS

Yan XiaiChang WeidongTan Min

(Department of Information Technology,Hunan Police Academy,Changsha 410138,Hunan,China)(Key Laboratory of Network Crime Investigation,Colleges of Hunan Province,Changsha 410138,Hunan,China)

AbstractStatic forensics is short in timeliness, while dynamic forensics can achieve more authentic and real-time evidences. Evidence identification is pivotal to dynamic forensics. The essence of evidence identification is to classify the network data flow so as to judge whether the behaviours are legal or illegal. Bloom filter represents the data set with a bit string and effectively supports hash query on membership, so that it is used widely in packet classification algorithm. In this paper we first analyse the standard Bloom filter, and improve its defects. Based on these, we design a Bloom filters-based distributed dynamic computer forensics system, and employ secure and effective means to transmit evidences. Experiment shows that this system can dynamically detect network intrusion behaviours with high detection accurate rate and low false positives.

KeywordsInformation securityComputer forensicsBloom filterDynamic forensics

0引言

隨著互聯(lián)網(wǎng)的普及，網(wǎng)絡(luò)犯罪的案件呈多發(fā)態(tài)勢。計算機取證的任務(wù)是提取真實、完整、具有法律效力的電子證據(jù)。計算機取證技術(shù)分為靜態(tài)取證和動態(tài)取證兩種：靜態(tài)取證多為案發(fā)后對存儲介質(zhì)的數(shù)據(jù)進(jìn)行分析，動態(tài)取證則是實時地監(jiān)控系統(tǒng)數(shù)據(jù)，一旦有可疑現(xiàn)象，則進(jìn)行告警并進(jìn)行證據(jù)提取。從時效性和真實性等方面考慮，動態(tài)取證要優(yōu)于靜態(tài)取證，但動態(tài)取證的復(fù)雜度高，在海量的網(wǎng)絡(luò)數(shù)據(jù)中搜尋電子證據(jù)，宛如大海撈針。由此可見，動態(tài)取證的難點在于證據(jù)的識別[1-3]。

本文著重研究的是網(wǎng)絡(luò)攻擊案件中電子證據(jù)的動態(tài)識別。證據(jù)識別的一般方法是：在計算機終端、路由器等節(jié)點部署取證工具，通過訓(xùn)練設(shè)置一定的規(guī)則集，對網(wǎng)絡(luò)流進(jìn)行監(jiān)測，若有數(shù)據(jù)流與訓(xùn)練規(guī)則匹配，則認(rèn)定是網(wǎng)絡(luò)入侵行為。

網(wǎng)絡(luò)流量監(jiān)測的核心是網(wǎng)絡(luò)數(shù)據(jù)包分類過程。目前網(wǎng)絡(luò)數(shù)據(jù)包經(jīng)典的分類算法有：基本數(shù)據(jù)結(jié)構(gòu)分類算法、啟發(fā)式算法、多維分解算法、TCAM算法、布魯姆過濾器算法。在這五類經(jīng)典的數(shù)據(jù)包分類算法中，基于布魯姆過濾器算法的分類效率較高，它只需要很少的存儲便能快速地查找出相匹配的結(jié)果，是近年來包分類算法領(lǐng)域的一個研究熱點[4-6]。為此，本文提出一個基于布魯姆過濾器的電子證據(jù)動態(tài)識別方法，設(shè)計了一個基于布魯姆過濾器的的動態(tài)取證原型系統(tǒng)，期望對網(wǎng)絡(luò)入侵的證據(jù)進(jìn)行準(zhǔn)確識別，并及時提取。

1布魯姆過濾器

1.1標(biāo)準(zhǔn)布魯姆過濾器算法

布魯姆過濾器是一種空間高效的隨機化數(shù)據(jù)結(jié)構(gòu)，用于元素集合的精簡表示和隸屬關(guān)系查詢。布魯姆過濾器廣泛應(yīng)用于網(wǎng)絡(luò)數(shù)據(jù)包分類、IP路由查找、深度數(shù)據(jù)包檢測等方面[7]。

標(biāo)準(zhǔn)布魯姆過濾器是m位的向量V表示查詢的匯總信息。假設(shè)元素的集合為S={s1,s2,…,sn}，每個元素對應(yīng)K個哈希函數(shù)h1(x),h2(x),…,hk(x)，哈希函數(shù)的取值范圍是[0,m-1]。m位的向量V的初始狀態(tài)全部為0，當(dāng)進(jìn)行元素存儲時，設(shè)置V中h1(x),h2(x),…,hk(x)位全部為1，當(dāng)進(jìn)行元素查詢時，查找h1(x),h2(x),…,hk(x)位是否全部為1，若全部為1，則元素位于集合中，否則，元素不在集合中[8]。

例：假設(shè)向量長度為m=6 bit,哈希函數(shù)的個數(shù)k=2，分別為：h1(x)=xmod6，…，h2(x)=(2x+1)mod6，設(shè)S={13,14}，查詢元素{12,19}是否位于集合中。插入與查詢的結(jié)果如圖1所示。

圖1　標(biāo)準(zhǔn)布魯姆過濾器插入與查詢實例

布魯姆過濾器不存在將是屬于集合的元素判斷為非集合的元素(假陰性)，可能將不屬于集合的元素判斷為屬于集合的元素(假陽性)。它雖然存在假陽性的誤判，但其快速查找和節(jié)約存儲空間的優(yōu)點遠(yuǎn)超過假陽性的誤判，并且可通過個設(shè)置多個布魯姆過濾器來降低假陽性的誤判。

從取證角度來說，由于布魯姆過濾器不存在假陰性(形如不存在將壞人說成好人)，也就不存在有漏網(wǎng)之魚，所以布魯姆過濾器比較適合用來進(jìn)行動態(tài)電子證據(jù)的識別。

1.2標(biāo)準(zhǔn)布魯姆過濾器算法的改進(jìn)

標(biāo)準(zhǔn)布魯姆過濾器算法的缺陷有兩點：一是存在假陽性(形如可能將好人說成壞人)，導(dǎo)致這種情況是由于匯總信息中置1位過于稠密；二是不支持元素的刪除，因為作刪除的位可能是其他已存在元素的哈希值，導(dǎo)致其他元素查詢不準(zhǔn)確。動態(tài)電子證據(jù)的檢測中，規(guī)則會自適應(yīng)更新，可能會存在規(guī)則的刪除操作，此外，系統(tǒng)應(yīng)盡量減少假陽性的判斷。因此，必須對標(biāo)準(zhǔn)布魯姆過濾器進(jìn)行改進(jìn)。

我們提出一個基于計數(shù)布魯姆過濾器陣列的算法，其中采用陣列是為了降低假陽性，采用計數(shù)器是為了支持元素的刪除操作。

計數(shù)式布魯姆過濾器元素插入算法：

Step1向量V的初始狀態(tài)全部為0。

Step2計算插入元素h1(x),h2(x),…,hk(x)值。

Step3查看對應(yīng)哈希位的值，n=n+1。

Step4重復(fù)Step2。

計數(shù)式布魯姆過濾器元素刪除算法：

Step1計算刪除元素h1(x),h2(x),…,hk(x)值。

Step2查看對應(yīng)哈希位的值，n=n-1。

Step3重復(fù)Step1。

計數(shù)式布魯姆過濾器元素查詢算法：

Step1計算查詢元素h1(x),h2(x),…,hk(x)值。

Step2查看對應(yīng)哈希位的值。

Step3if all(n)>0元素屬于集合；else元素不屬于集合。

計數(shù)式布魯姆過濾器陣列算法：

Step1設(shè)置多個布魯姆過濾器，并分配唯一的ID，ID∈{1,2,…,t}。

Step2設(shè)置一個定位哈希函數(shù)H(x)，H(x)∈[1,t]。

Step3查詢元素為Y,計算H(y)，取?H(y)」，找到對應(yīng)的ID。

Step4計算h1(y),h2(y),…,hk(y)，在定位的過濾器上將對應(yīng)的位加1。

1.3布魯姆過濾器的特點及應(yīng)用前景

布魯姆過濾器采用非常精簡的形式來表示信息，哈希查找的時間為常數(shù)級，存儲空間開銷特別小，占用網(wǎng)絡(luò)帶寬、高速緩存相當(dāng)?shù)?，特別適用于海量數(shù)據(jù)集中的特征字符的查找和識別。Broder A等人得出結(jié)論：當(dāng)在受限空間完成集合查詢時，就應(yīng)當(dāng)考慮使用布魯姆過濾器[9]。

布魯姆過濾器存在一定假陽性的判斷，但能通過調(diào)整參數(shù)設(shè)置，優(yōu)化算法設(shè)計，使假陽性判斷的概率變?yōu)榭山邮艿姆秶畠?nèi)。

Broder A等人預(yù)測：目前，布魯姆過濾器所展現(xiàn)的應(yīng)用只是冰山一角，伴隨著算法本身的改進(jìn)和查詢集合爆炸式的增長，它將在未來計算網(wǎng)絡(luò)和新的技術(shù)領(lǐng)域得到更廣泛的應(yīng)用[9]。

2基于布魯姆過濾器的計算機動態(tài)取證系統(tǒng)

2.1系統(tǒng)架構(gòu)

基于布魯姆過濾器的動態(tài)電子證據(jù)識別的總體框架如圖2所示。取證服務(wù)器是整個系統(tǒng)的控制中心，一方面負(fù)責(zé)取證任務(wù)的發(fā)起，將證據(jù)規(guī)則集分部署至布魯姆過濾器陣列中；另一方面負(fù)責(zé)階段性取證任務(wù)的終結(jié)，對證據(jù)提取節(jié)點發(fā)送的取證結(jié)果篩選、組合和重構(gòu)，使之再現(xiàn)整個入侵行為的完整細(xì)節(jié)，并生成一份完整的取證報告。

圖2　動態(tài)電子證據(jù)識別系統(tǒng)架構(gòu)

取證節(jié)點中的證據(jù)提取模塊主要負(fù)責(zé)證據(jù)的收集，當(dāng)證據(jù)識別模塊發(fā)現(xiàn)有入侵行為時，它記錄兩方面的內(nèi)容：一是記錄入侵時被入侵節(jié)點的運行情況，例如系統(tǒng)內(nèi)存信息、CPU的占用率、磁盤的讀寫情況、緩沖區(qū)信息等，這些信息是網(wǎng)絡(luò)入侵時的現(xiàn)場快照，是還原犯罪現(xiàn)場的必備依據(jù)；二是記錄入侵時的網(wǎng)絡(luò)通信情況。證據(jù)提取之后，必須安全地提交至證據(jù)服務(wù)器。

為了防止證據(jù)傳輸過程中被他人篡改、偽造，我們對證據(jù)的傳送設(shè)計了以下傳輸流程。

證據(jù)發(fā)送方：

Setp1對證據(jù)內(nèi)容進(jìn)行對稱加密，對稱密鑰為K，C=Ek(M)。

Step2計算證據(jù)內(nèi)容的安全散列，并數(shù)字簽名，h=SHA(M)，C1=Esend-private(h)。

Step3利用接收方證據(jù)服務(wù)器的公鑰對K進(jìn)行加密，C2=Esever-pulic(K)。

Step4將C,C1,C2打包傳送至證據(jù)服務(wù)器。

證據(jù)接收方：

Step1驗證簽名，確認(rèn)發(fā)送者身份，h=Dsend-pubic(C1)。

Step2獲取會話密鑰，并解密證據(jù)內(nèi)容，K=Dsever-private(C2)，M=Dk(C)。

Step3檢查完整性，重新計算SHA(M)，判斷其值是否等于h。

在取證節(jié)點中的證據(jù)識別模塊部署布魯姆過濾器陣列，證據(jù)識別模塊的主要任務(wù)是對網(wǎng)絡(luò)流進(jìn)行監(jiān)測，當(dāng)發(fā)現(xiàn)有入侵行為時，發(fā)出告警信息，提醒證據(jù)提取模塊及時提取證據(jù)。

為了負(fù)載均衡，提高規(guī)則匹配的速度，將數(shù)據(jù)流分為TCP數(shù)據(jù)流和UDP數(shù)據(jù)流兩類，布魯姆過濾器查詢匹配的元素為{源IP，目標(biāo)IP，源端口，目標(biāo)端口，連接狀態(tài)}。

2.2電子證據(jù)的動態(tài)識別流程

算法的結(jié)構(gòu)流程如圖3所示。對于需要檢測的數(shù)據(jù)包，首先將多維多模式匹配分解單維單模式匹配，將源IP、目標(biāo)IP、源端口、目標(biāo)端口、連接狀態(tài)通過單模式匹配得到規(guī)則集S1,S2,S3,S4,S5；再將S1與S2做叉積運算得S12，將S3與S4做叉積運算得S34，將S12與S34做叉積運算得S1234；最后將S1234與S5做叉積運算得S12345，得到五維相匹配的規(guī)則集合。最后根據(jù)優(yōu)先級的高低得到最終的結(jié)果。

圖3　基于布魯姆過濾器查詢匹配算法

為了降低布魯姆過濾器誤判(假陽性)，過濾器采用陣列的形式，每個過濾器分配一個ID。進(jìn)行指定的元素查詢時，先通過一個哈希函數(shù)H(x)進(jìn)行定位，找到相對應(yīng)的過濾器。K值取9(根據(jù)文獻(xiàn)[7]，K=9時假陽性概率最低)，再計算H1(x),H2(x),…,H9(x)，若相對應(yīng)計數(shù)式布魯姆過濾器每位的值全大于0，則認(rèn)為是入侵行為，否則認(rèn)為是屬于正常流量。

證據(jù)識別的流程如圖4所示。

圖4　動態(tài)電子證據(jù)的識別流程

2.3基于布魯姆過濾器動態(tài)取證的優(yōu)勢

靜態(tài)取證逐漸演變?yōu)閯討B(tài)取證已達(dá)成共識。動態(tài)取證的關(guān)鍵是證據(jù)的識別，也即將網(wǎng)絡(luò)流量進(jìn)行分類，將攻擊行為從行為中分離出來。

在現(xiàn)有的一些常規(guī)分類算法中：K最近鄰算法是一種懶惰的學(xué)習(xí)算法，計算的負(fù)擔(dān)全部落在分類部分；支持向量機具有良好的泛化能力,但訓(xùn)練時間非常長, 故而不太適合處理大規(guī)模數(shù)據(jù)集；樸素貝葉斯方法假設(shè)屬性獨立，誤判的可能性很大。為此，這些方法都不太適合動態(tài)的證據(jù)識別。

基于布魯姆過濾器動態(tài)取證的優(yōu)勢有：不存在假陰性的判斷；訓(xùn)練時間短，匹配速度快，特別適合于大規(guī)模數(shù)據(jù)中網(wǎng)絡(luò)攻擊頻繁的證據(jù)提?。恍畔⒈硎竞唵?，節(jié)約了網(wǎng)絡(luò)帶寬，并有效地降低了計算和存儲的開銷。

3實驗分析評價

根據(jù)上述設(shè)計算法，我們開發(fā)了一個基于布魯姆過濾器的動態(tài)取證的原型系統(tǒng)，并在Linux平臺上對取證的性能進(jìn)行了測試。實驗中主要采用了檢測準(zhǔn)確率(DSR)和假陽性誤斷率(FFR)兩個指標(biāo)來評價。

其中TA為連接記錄中帶有入侵性質(zhì)的次數(shù)，DS為檢測出來帶有入侵行為的次數(shù)，F(xiàn)R為非入侵行為判斷為入侵行為的次數(shù)。

實驗中利用第5屆知識發(fā)現(xiàn)和數(shù)據(jù)挖掘國際會議提供的數(shù)據(jù)集進(jìn)行測試。該數(shù)據(jù)集提供的是網(wǎng)絡(luò)連接數(shù)據(jù)，專用于對網(wǎng)絡(luò)入侵檢測行為的檢測，具體數(shù)據(jù)有DOS攻擊類、PROBE攻擊類、R2L攻擊類和U2R攻擊類和正常數(shù)據(jù)五類，每個TCP/IP 連接都標(biāo)注了持續(xù)時間，協(xié)議類型、正常或具體的攻擊類型等屬性。實驗中從實驗訓(xùn)練集中隨機抽出20%的記錄作為訓(xùn)練集，從實驗測試集中隨機抽出20%的記錄作為測試集，取k=9。系統(tǒng)的誤判率如表1所示。

表1　取不同k值的誤判率比較

從表中可獲知基于布魯姆過濾器的動態(tài)取證的方法具有較低的誤判率。另外表明：k值存在一最優(yōu)解，當(dāng)k較小時，表示元素信息少，可能誤判率較高；當(dāng)k較大時，向量為1的位數(shù)增加，誤判率同增會增加，實測k=9時為最優(yōu)。

我們同時與文獻(xiàn)[10]進(jìn)行了檢測準(zhǔn)確率的比較，文獻(xiàn)[10]是基于樸素貝葉斯的動態(tài)電子取證方法(簡稱Deb),本系統(tǒng)簡稱Debb，取k=9，檢測準(zhǔn)確率的比較如圖5所示。實驗結(jié)果表明：在k取值恰當(dāng)?shù)那闆r下，每一類檢測準(zhǔn)確率要略高于文獻(xiàn)[10]的檢測值。

圖5　檢測準(zhǔn)確率比較圖

4結(jié)語

布魯姆過濾器的匹配算法由于其哈希匹配的常數(shù)時間和存儲空間開銷較小，從而使它得到了廣泛的應(yīng)用。本文創(chuàng)新地提出了基于布魯姆過濾器的電子證據(jù)動態(tài)識別方法，并對標(biāo)準(zhǔn)的布魯姆過濾器算法進(jìn)行了改進(jìn)，設(shè)計并實現(xiàn)了一個基于布魯姆過濾器的計算機動態(tài)取證原型系統(tǒng)。從實驗結(jié)果得知系統(tǒng)具有高準(zhǔn)確率和低誤判率，彌補了現(xiàn)有動態(tài)取證技術(shù)的一些不足。下一步工作是對標(biāo)準(zhǔn)布魯姆過濾器的算法進(jìn)一步優(yōu)化，以降低其假陽性的判斷。

參考文獻(xiàn)

[1] David Bennett.The Challenges Facing Computer Forensics Investigators in Obtaining Information from Mobile Devices for Use in Criminal Investigations[J].Information Security Journal:A Global Perspective,2012,21(3):159-168.

[2] 周敏,龔箭.分布式計算機取證模型研究[J].微電子學(xué)與計算機,2012,29(2):40-43.

[3] Susan Ballou,Rhesa G Gilliland.Emerging paper standards in computer forensics[J].Digital Investigation,2011,8(2):96-97.

[4] Ming Yu,Dongju Wang.A Time Efficient Algorithm Based on Bloom Filters for Longest Prefix Matching in IP Lookups[J].Journal of Computers,2013,8(10):2724-2729.

[5] Saravanan K,Senthilkumar A.FPGA implementation of Secure Authentication in WiMAX Networks using Modified WiMAX Bloom filter:A Hardware Approach[J].Journal of Discrete Mathematical Sciences and Cryptography,2013,16(6):393-404.

[6] Shailendra Shukla,Nishant Kumar,Rajiv Misra.Impact of Bloom Filter on Infection Rate in Epidemic Forwarding for ICNs[J].Wireless Personal Communications,2014,75(4):2165-2180.

[7] Bin Zhou,Rongbo Zhu,Ying Zhang.An Efficient Data Fingerprint Query Algorithm Based on Two-Leveled Bloom Filter[J].Journal of Multimedia,2013,8(2):73-81.

[8] Weijiang Liu,Wenyu Qu,Xiaona He.Detecting superpoints through a reversible counting Bloom filter[J].The Journal of Supercomputing,2013,63(1):218-234.

[9] Broder A,Mitzenmaeher M.Network APPlications of Bloom Filters:A Survey[J].Internet Mathematics,2005,1(4):485-509.

[10] 鄢喜愛,楊金民,常衛(wèi)東.基于貝葉斯方法的計算機動態(tài)取證[J].計算機工程與設(shè)計,2009,30(20):4614-4616.

中圖分類號TP393.08

文獻(xiàn)標(biāo)識碼A

DOI:10.3969/j.issn.1000-386x.2016.02.069

收稿日期：2014-05-30。國家自然科學(xué)基金項目(61272401)；公安部公安理論及軟件科學(xué)研究計劃項目(2013LLYJHNST040)；湖南省科技廳科研項目(2014FJ3049，2013GK2013)。鄢喜愛，教授，主研領(lǐng)域：信息安全。常衛(wèi)東，副教授。譚敏，副教授。