基于布鲁姆过滤器的计算机动态取证技术研究

鄢喜爱　常卫东　谭　敏

(湖南警察学院信息技术系　湖南 长沙 410138)

(网络犯罪侦察湖南省普通高等学校重点实验室　湖南 长沙 410138)



基于布鲁姆过滤器的计算机动态取证技术研究

鄢喜爱常卫东谭敏

(湖南警察学院信息技术系湖南 长沙 410138)

(网络犯罪侦察湖南省普通高等学校重点实验室湖南 长沙 410138)

摘要静态取证时效性不足，动态取证则可获得更为真实、实时的证据。动态取证最关键的是证据识别。证据识别本质上是对网络数据流进行分类，以判断其行为是合法还是非法。布鲁姆过滤器采用一个位串表示数据集合并有效支持元素的哈希查询，从而被广泛应用于包分类算法中。首先对标准布鲁姆过滤器算法进行分析，并对算法存在的缺陷进行改进。在此基础上，设计一个基于布鲁姆过滤器的分布式计算机动态取证系统，并采取安全有效措施对证据进行传送。实验表明：该系统能对网络攻击行为进行动态地检测，且检测准确率高、误判率低。

关键词信息安全计算机取证布鲁姆过滤器动态取证

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引言

随着互联网的普及，网络犯罪的案件呈多发态势。计算机取证的任务是提取真实、完整、具有法律效力的电子证据。计算机取证技术分为静态取证和动态取证两种：静态取证多为案发后对存储介质的数据进行分析，动态取证则是实时地监控系统数据，一旦有可疑现象，则进行告警并进行证据提取。从时效性和真实性等方面考虑，动态取证要优于静态取证，但动态取证的复杂度高，在海量的网络数据中搜寻电子证据，宛如大海捞针。由此可见，动态取证的难点在于证据的识别[1-3]。

本文着重研究的是网络攻击案件中电子证据的动态识别。证据识别的一般方法是：在计算机终端、路由器等节点部署取证工具，通过训练设置一定的规则集，对网络流进行监测，若有数据流与训练规则匹配，则认定是网络入侵行为。

网络流量监测的核心是网络数据包分类过程。目前网络数据包经典的分类算法有：基本数据结构分类算法、启发式算法、多维分解算法、TCAM算法、布鲁姆过滤器算法。在这五类经典的数据包分类算法中，基于布鲁姆过滤器算法的分类效率较高，它只需要很少的存储便能快速地查找出相匹配的结果，是近年来包分类算法领域的一个研究热点[4-6]。为此，本文提出一个基于布鲁姆过滤器的电子证据动态识别方法，设计了一个基于布鲁姆过滤器的的动态取证原型系统，期望对网络入侵的证据进行准确识别，并及时提取。

1布鲁姆过滤器

1.1标准布鲁姆过滤器算法

布鲁姆过滤器是一种空间高效的随机化数据结构，用于元素集合的精简表示和隶属关系查询。布鲁姆过滤器广泛应用于网络数据包分类、IP路由查找、深度数据包检测等方面[7]。

标准布鲁姆过滤器是m位的向量V表示查询的汇总信息。假设元素的集合为S={s1,s2,…,sn}，每个元素对应K个哈希函数h1(x),h2(x),…,hk(x)，哈希函数的取值范围是[0,m-1]。m位的向量V的初始状态全部为0，当进行元素存储时，设置V中h1(x),h2(x),…,hk(x)位全部为1，当进行元素查询时，查找h1(x),h2(x),…,hk(x)位是否全部为1，若全部为1，则元素位于集合中，否则，元素不在集合中[8]。

例：假设向量长度为m=6 bit,哈希函数的个数k=2，分别为：h1(x)=xmod6，…，h2(x)=(2x+1)mod6，设S={13,14}，查询元素{12,19}是否位于集合中。插入与查询的结果如图1所示。

图1　标准布鲁姆过滤器插入与查询实例

布鲁姆过滤器不存在将是属于集合的元素判断为非集合的元素(假阴性)，可能将不属于集合的元素判断为属于集合的元素(假阳性)。它虽然存在假阳性的误判，但其快速查找和节约存储空间的优点远超过假阳性的误判，并且可通过个设置多个布鲁姆过滤器来降低假阳性的误判。

从取证角度来说，由于布鲁姆过滤器不存在假阴性(形如不存在将坏人说成好人)，也就不存在有漏网之鱼，所以布鲁姆过滤器比较适合用来进行动态电子证据的识别。

1.2标准布鲁姆过滤器算法的改进

标准布鲁姆过滤器算法的缺陷有两点：一是存在假阳性(形如可能将好人说成坏人)，导致这种情况是由于汇总信息中置1位过于稠密；二是不支持元素的删除，因为作删除的位可能是其他已存在元素的哈希值，导致其他元素查询不准确。动态电子证据的检测中，规则会自适应更新，可能会存在规则的删除操作，此外，系统应尽量减少假阳性的判断。因此，必须对标准布鲁姆过滤器进行改进。

我们提出一个基于计数布鲁姆过滤器阵列的算法，其中采用阵列是为了降低假阳性，采用计数器是为了支持元素的删除操作。

计数式布鲁姆过滤器元素插入算法：

Step1向量V的初始状态全部为0。

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

Step3查看对应哈希位的值，n=n+1。

Step4重复Step2。

计数式布鲁姆过滤器元素删除算法：

Step1计算删除元素h1(x),h2(x),…,hk(x)值。

Step2查看对应哈希位的值，n=n-1。

Step3重复Step1。

计数式布鲁姆过滤器元素查询算法：

Step1计算查询元素h1(x),h2(x),…,hk(x)值。

Step2查看对应哈希位的值。

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

计数式布鲁姆过滤器阵列算法：

Step1设置多个布鲁姆过滤器，并分配唯一的ID，ID∈{1,2,…,t}。

Step2设置一个定位哈希函数H(x)，H(x)∈[1,t]。

Step3查询元素为Y,计算H(y)，取⎣H(y)」，找到对应的ID。

Step4计算h1(y),h2(y),…,hk(y)，在定位的过滤器上将对应的位加1。

1.3布鲁姆过滤器的特点及应用前景

布鲁姆过滤器采用非常精简的形式来表示信息，哈希查找的时间为常数级，存储空间开销特别小，占用网络带宽、高速缓存相当低，特别适用于海量数据集中的特征字符的查找和识别。Broder A等人得出结论：当在受限空间完成集合查询时，就应当考虑使用布鲁姆过滤器[9]。

布鲁姆过滤器存在一定假阳性的判断，但能通过调整参数设置，优化算法设计，使假阳性判断的概率变为可接受的范围之内。

Broder A等人预测：目前，布鲁姆过滤器所展现的应用只是冰山一角，伴随着算法本身的改进和查询集合爆炸式的增长，它将在未来计算网络和新的技术领域得到更广泛的应用[9]。

2基于布鲁姆过滤器的计算机动态取证系统

2.1系统架构

基于布鲁姆过滤器的动态电子证据识别的总体框架如图2所示。取证服务器是整个系统的控制中心，一方面负责取证任务的发起，将证据规则集分部署至布鲁姆过滤器阵列中；另一方面负责阶段性取证任务的终结，对证据提取节点发送的取证结果筛选、组合和重构，使之再现整个入侵行为的完整细节，并生成一份完整的取证报告。

图2　动态电子证据识别系统架构

取证节点中的证据提取模块主要负责证据的收集，当证据识别模块发现有入侵行为时，它记录两方面的内容：一是记录入侵时被入侵节点的运行情况，例如系统内存信息、CPU的占用率、磁盘的读写情况、缓冲区信息等，这些信息是网络入侵时的现场快照，是还原犯罪现场的必备依据；二是记录入侵时的网络通信情况。证据提取之后，必须安全地提交至证据服务器。

为了防止证据传输过程中被他人篡改、伪造，我们对证据的传送设计了以下传输流程。

证据发送方：

Setp1对证据内容进行对称加密，对称密钥为K，C=Ek(M)。

Step2计算证据内容的安全散列，并数字签名，h=SHA(M)，C1=Esend-private(h)。

Step3利用接收方证据服务器的公钥对K进行加密，C2=Esever-pulic(K)。

Step4将C,C1,C2打包传送至证据服务器。

证据接收方：

Step1验证签名，确认发送者身份，h=Dsend-pubic(C1)。

Step2获取会话密钥，并解密证据内容，K=Dsever-private(C2)，M=Dk(C)。

Step3检查完整性，重新计算SHA(M)，判断其值是否等于h。

在取证节点中的证据识别模块部署布鲁姆过滤器阵列，证据识别模块的主要任务是对网络流进行监测，当发现有入侵行为时，发出告警信息，提醒证据提取模块及时提取证据。

为了负载均衡，提高规则匹配的速度，将数据流分为TCP数据流和UDP数据流两类，布鲁姆过滤器查询匹配的元素为{源IP，目标IP，源端口，目标端口，连接状态}。

2.2电子证据的动态识别流程

算法的结构流程如图3所示。对于需要检测的数据包，首先将多维多模式匹配分解单维单模式匹配，将源IP、目标IP、源端口、目标端口、连接状态通过单模式匹配得到规则集S1,S2,S3,S4,S5；再将S1与S2做叉积运算得S12，将S3与S4做叉积运算得S34，将S12与S34做叉积运算得S1234；最后将S1234与S5做叉积运算得S12345，得到五维相匹配的规则集合。最后根据优先级的高低得到最终的结果。

图3　基于布鲁姆过滤器查询匹配算法

为了降低布鲁姆过滤器误判(假阳性)，过滤器采用阵列的形式，每个过滤器分配一个ID。进行指定的元素查询时，先通过一个哈希函数H(x)进行定位，找到相对应的过滤器。K值取9(根据文献[7]，K=9时假阳性概率最低)，再计算H1(x),H2(x),…,H9(x)，若相对应计数式布鲁姆过滤器每位的值全大于0，则认为是入侵行为，否则认为是属于正常流量。

证据识别的流程如图4所示。

图4　动态电子证据的识别流程

2.3基于布鲁姆过滤器动态取证的优势

静态取证逐渐演变为动态取证已达成共识。动态取证的关键是证据的识别，也即将网络流量进行分类，将攻击行为从行为中分离出来。

在现有的一些常规分类算法中：K最近邻算法是一种懒惰的学习算法，计算的负担全部落在分类部分；支持向量机具有良好的泛化能力,但训练时间非常长, 故而不太适合处理大规模数据集；朴素贝叶斯方法假设属性独立，误判的可能性很大。为此，这些方法都不太适合动态的证据识别。

基于布鲁姆过滤器动态取证的优势有：不存在假阴性的判断；训练时间短，匹配速度快，特别适合于大规模数据中网络攻击频繁的证据提取；信息表示简单，节约了网络带宽，并有效地降低了计算和存储的开销。

3实验分析评价

根据上述设计算法，我们开发了一个基于布鲁姆过滤器的动态取证的原型系统，并在Linux平台上对取证的性能进行了测试。实验中主要采用了检测准确率(DSR)和假阳性误断率(FFR)两个指标来评价。

其中TA为连接记录中带有入侵性质的次数，DS为检测出来带有入侵行为的次数，FR为非入侵行为判断为入侵行为的次数。

实验中利用第5届知识发现和数据挖掘国际会议提供的数据集进行测试。该数据集提供的是网络连接数据，专用于对网络入侵检测行为的检测，具体数据有DOS攻击类、PROBE攻击类、R2L攻击类和U2R攻击类和正常数据五类，每个TCP/IP 连接都标注了持续时间，协议类型、正常或具体的攻击类型等属性。实验中从实验训练集中随机抽出20%的记录作为训练集，从实验测试集中随机抽出20%的记录作为测试集，取k=9。系统的误判率如表1所示。

表1　取不同k值的误判率比较

从表中可获知基于布鲁姆过滤器的动态取证的方法具有较低的误判率。另外表明：k值存在一最优解，当k较小时，表示元素信息少，可能误判率较高；当k较大时，向量为1的位数增加，误判率同增会增加，实测k=9时为最优。

我们同时与文献[10]进行了检测准确率的比较，文献[10]是基于朴素贝叶斯的动态电子取证方法(简称Deb),本系统简称Debb，取k=9，检测准确率的比较如图5所示。实验结果表明：在k取值恰当的情况下，每一类检测准确率要略高于文献[10]的检测值。

图5　检测准确率比较图

4结语

布鲁姆过滤器的匹配算法由于其哈希匹配的常数时间和存储空间开销较小，从而使它得到了广泛的应用。本文创新地提出了基于布鲁姆过滤器的电子证据动态识别方法，并对标准的布鲁姆过滤器算法进行了改进，设计并实现了一个基于布鲁姆过滤器的计算机动态取证原型系统。从实验结果得知系统具有高准确率和低误判率，弥补了现有动态取证技术的一些不足。下一步工作是对标准布鲁姆过滤器的算法进一步优化，以降低其假阳性的判断。

参考文献

[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].微电子学与计算机,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] 鄢喜爱,杨金民,常卫东.基于贝叶斯方法的计算机动态取证[J].计算机工程与设计,2009,30(20):4614-4616.

中图分类号TP393.08

文献标识码A

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

收稿日期：2014-05-30。国家自然科学基金项目(61272401)；公安部公安理论及软件科学研究计划项目(2013LLYJHNST040)；湖南省科技厅科研项目(2014FJ3049，2013GK2013)。鄢喜爱，教授，主研领域：信息安全。常卫东，副教授。谭敏，副教授。