分类算法在手机取证中的应用

肖程望，卢军，余力耕

（武汉邮电科学研究院湖北武汉430074）

分类算法在手机取证中的应用

肖程望，卢军，余力耕

（武汉邮电科学研究院湖北武汉430074）

在当今社会，手机犯罪越来越引起人们的重视，对研究人员来说需要马上研究相应的对策加以应对，智能手机的使用率越来越高也促使了手机取证技术的研究发展。同时采用Android系统的智能手机越来越多，针对Android系统手机取证的电子证据进行相应的数据分析，能更方便和直观的发现手机信息中的重点与需要关注的目标对象。在本文中应用了朴素贝叶斯分类算法对数据中各联系人进行分类，而朴素贝叶斯分类算法的条件独立性假设是非常苛刻的，很难在正常情况下满足，本文中提出了一种基于变异系数法的加权朴素贝叶斯分类模型，克服这个问题关键在于利用各项指标间所包含的信息的差异，通过计算得到指标的权重。有效地提高了朴素贝叶斯算法的分类性能，并且也继承了贝叶斯分类算法的简单性，本文首先对算法原理进行了分析与证明，然后描述了相应的算法，在最后给出了基于变异系数法的属性权值求解方法。

手机取证；取证方法；分类算法；朴素贝叶斯；变异系数

手机等各类电子产品中的电子证据，包括：短信、通讯录、通话记录和浏览记录等逐渐成为新的诉讼证据之一，例如通过短信和通话记录可以了解嫌疑人与外界的联系，查看嫌疑人的手机GPS记录来确定嫌疑人的活动轨迹，而且QQ聊天记录、邮件、上网记录等都有很大的可能记录着犯罪份子的犯罪行为[1]。手机的取证对于一个案件的侦破有着十分重大的意义，手机取证这一概念也随之提出。

同时，最近三年中使用Android系统的手机所占市场份额正在快速上升，通过市场调查机构报告显示，在全球手机智能操作系统中所占份额最高的是Android，达到了72.1%，IOS排第二，占据了24.4%的份额，剩下的就是WP等等其他操作系统了。Android操作系统已经成为当今全球第一大操作系统，并且其增长没有任何衰减的趋势[2]。大量利用手机进行诽谤、诈骗等的犯罪活动也在最近两发频频发生，这与Android系统手机的迅猛发展不无关系。面对这种情况，对智能手机，包括使用Android系统的，进行取证技术与分析方面的相关研究必须要尽快发展起来。

对提取数据的分析与分类也显得更加的重要，本文提出了一种贝叶斯分类优化算法，基于变异系数，介绍了算法详情、原理与相应的实现步骤。

1 取证信息分析

手机取证是一个对目标手机中的与案件有关的数据进行提取的过程。通过一些技术分析，确保原始手机未被损坏、篡改，并且收集的数据不可被修改，并且最终获得具有法律效力的证据能够帮助公安机关人员破案[3]。

重要证据源主要保存在Android系统手机中的手机内存和sim卡中。提取出的信息大致有联系人、短信息、通话记录、浏览历史记录、多媒体信息、GPS信息、目标手机上的app内信息等[4]，具体如图1所示。

2 手机取证分析

通过分析从数据库中提取出的位置信息和时间，可以得知手机使用者的行为与活动规律。通过分析通讯录与短信数据库中的信息，可以分析出使用者与某个人或某几人联系比较密切[5]。同时，通过查看浏览器历史记，可以看到使用者的爱好与兴趣。

同时在分析和监控团伙的各个手机时，使用基于Apriori算法的信息归纳总结，通过分析提取出的通讯录和短信数据来分析出团伙中的主要人物或关键人物。各个手机使用者之间的关系和它们之间的相互影响能够很快的求出。在经过了这么多年的研究后，只是把数据从手机中取出并不是一个十分困难的事情，现在主要是要对取出数据进行分析和归类。在众多分类方法和理论中，朴素贝叶斯（naïve Bayes，NB）由于精确度高、计算高效、算法不复杂并且计算原理简单易懂，而且具有坚实的理论基础，使得它在不同领域得到了广泛应用[5]。然而朴素贝叶斯分类有一个前提就是：属性值之间是相互独立的在给定分类特征条件下。通常情况下，这种基于独立性的假设是很难满足的。朴素的贝叶斯分类最大的缺陷是它无法处理特征符合所产生的变化（即前面提到过的实际上难以满足的相互独立）[6]。

本文就是在提取出数据的基础上，利用朴素贝叶斯算法对信息进行分类，并针对朴素贝叶斯算法中的不足之处进行了优化与研究。引入了变异系数来对不同特征的属性进行权重分析，以获得更加客观和精确的分类结果。

表1 提取信息表

3 算法分析

3.1 基本介绍

数据分类主要分为两个阶段：学习阶段（构造分类模型）、分类阶段（使用模型预测给定数据的类标号）。而其中的的关键是构造分类器。其中朴素贝叶斯分类模型（NBC）已被广泛使用，主要是因为它有着坚实的数学基础，以及稳定的分类效率[7]。朴素贝叶斯模型有以下几大优点：所需参数少、算法也比较简单、缺失数据不太敏感。

同时还有一种贝叶斯分类器也有很多人在进行研究，那就是贝叶斯网络（BayesNet），它是一个有向的无环图，上面带有概率注释，并且没一个节点表示了一个随机变量，并且可以在其上进行学习[8]。而经过研究学习后发现这会增加贝叶斯算法的复杂性，这主要是因为特征值之间的相互依赖。因此，当应用于实践，它往往需要被简化。这就给我们提出了一个问题：如何来提高其分类性能而又不会增加计算的复杂性呢。阅读各种文献资料后，发现了有基于信息增益和利用爬山算法等方法、还有提出了采用粗糙集技术来确定属性权值的方法[9]。然而经过实验后，我们发现在上述方法中虽然有一定的提高，但是在分析手机取证提取出的数据时改进的效果并不是十分理想。

变异系数法（Coefficient of variation method）是一种客观赋权的方法，在很多场合也有利用，它是直接利用各个特征项所包含的信息大小，来决定各个特征项的权重值[10]。这主要是因为在评价一类事物时，相互间差别越大的特征项越能表达这些事物的不同之处，更能反映相互之间的差距。因此本文利用变异系数对贝叶斯分类模型进行了优化，并对算法的原理进行了说明。

3.2 加权朴素贝叶斯分类模型

3.2.1 朴素贝叶斯分类

P（A|B）表示了在B发生的前提下，A发生的概率。这是个条件概率。然而在实际生活中，我们可以很轻易的知道P（A|B），但是P（B|A）却很难知道，而贝叶斯定律就是帮助我们获得P（B|A）的。首先给出贝叶斯定理[11]。

贝叶斯分类在所有分类算法中是十分简单的主要有以下几步组成[12]：

1）设一个待分类项为X=[a1，a2，…，an]表示，分别描述在n个属性A1，A2，…，An上的值；

2）假定有m个类，用C=[b1，b2，…，bn]表示；

3）计 算 出P（C1|x），P（C2|x），P（C3|x），…，P（Cn|x）；

4）如果P（Ck|x）是所有概率中最大的，那么这个待分类项就属于Ck类。其中先验概率p(x1|Ci)，p(x2|Ci)，…，p(xn|Ci)可以从之前收集的数据中求得。

3.2.2 加权朴素贝叶斯分类

朴素贝叶斯模型（NBC）认为所有条件都是互不影响并且对分类结果的权重都是1，然而并非如此，在同一个问题中时，据常理所知，有的条件可能更重要些，而有的对结果可能影响较小。为了解决这个问题，需要给不容的条件附上不同的权重值，则可以得到经过了加权的朴素贝叶斯模型为：

其中，wk代表了属性Ai的权重值。对应的属性的权值越大，那么它对分类结果的影响就越大。而如何确定不同属性的权值，那又产生了一个新的问题了。

3.3 变异系数

将各属性视为随机变量Mi，任一随机变量Mi的标准差与平均数的比值称为其对应的变异系数，记为CVi。把所有的属性对应的变异系数相加后，对各个变异系数进行归一化处理后就可以得到对应的权重了[13]。在评价手机联系人的亲密度关系时，有多种评价标准，例如：通话次数、通话时长、短信次数、短信中关键字词的出现频率、邮件联系次数等等。而由于各个指标的量纲不同，自然是不能直接拿来比较的，还需要进行归一化和利用到变异系数来进行处理，然后才能得到各个指标的权重系数。

下面来进行一个实例分析：用变异系数法去计算手机中各个指标对亲密度关系的权重大小。下列数据是调查了10余部手机中的所有相关数据，计算出各个对应指标的变异系数，这些指标所对应的权重系数反应出了对亲密度分类结果的影响大小，并作为确定各项指标权重的依据。具体计算数据见表2：

表2 各指标的权重

计算过程如下：

1）分别计算这些数据的平均数和标准差，这主要依靠之前提取的各个数据；

2）计算出变异系数（均值与标准差的比值）；

3）将每一个指标所对应的变异系数相加求出总和；

4）计算出每一个指标所对应的权重。

上面求出的权重系数表明了不同指标对最后分类结果的影响大小，所以是可作权重系数应用在加权贝叶斯分类模型中的。

3.4 算法实现

基于变异系数的加权朴素贝叶斯分类算法的实现关键在于求解各条件属性的变异系数，并确定各条件属性的权重值，具体算法如下：

1）提取数据处理：将提取出的数据和预先准备的数据进行相应的处理，例如一些缺失数据的补充和数据之间的离散处理；

2）判断：如果是分类任务，则到（6），如果是训练任务则到（3）；

3）概率表学习（构造分类模型）：按照预先准备的练习数据，针对每一个属性Ai的属性值xik，每个分类的类别Ci、以及各个Ci的出现概率，计算在Ci发生的前提下，aik的出现概率p(xki|Ci)[14]；

4）变异系数计算：计算出变异系数=对应的均值/对应的标准差，然后经过归一化处理后得出对应的权重系数；

5）生成经过了加权的朴素贝叶斯分类器，并且吧加权朴素贝叶斯概率表已经各个对应属性权值表保存下来以供分类使用；

6）分类：利用保存了的概率表以及属性权值列表，并且使用之前生成的朴素贝叶斯分类器，得出分类结果。

4 实验测试

在提取了10部手机内的信息进行了加权贝叶斯分类算法的概率表和变异系数的学习后，对新取得的手机内信息进行分类后可知道手机内联系人与此人的亲密度关系。下表列出了集合名称、各个属性名称以及分类结果。

图1 加权贝叶斯分类结果

同时，利用朴素贝叶斯算法对相同数据进行处理后，可以发现加上由变异系数得出的权重之后，能更准确吧手机使用者内的联系人进行亲密度分类。原因在于权重计算考虑到了特征项在类间的分布，类间的分布的越不均匀，对类的贡献能力越大，同时对分类结果的影响也就越大，因此它的权重就越大。

5 结 论

现今，有很多犯罪分子通过手机进行交流、预谋犯罪等等行为，所以对手机提取数据的分析与提取数据的分类也显得更加的重要，本文提出了一种基于变异系数的贝叶斯分类算法，并给出了相应的算法实现步骤。并提取了某部手机中的测试数据，通过实验比较了朴素贝叶斯分类与基于变异系数的贝叶斯分类的效果，实验表明本算法在分类性能上有一定的优越性。

朴素贝叶斯分类的分类能力受到了特征项间独立性这一假设的很大影响。本文提出的这样一种新的分类方法，引入了权重的计算来克服这一问题，生成了更加精确并且有效的条件属性权重，考虑到在类内分布越均匀、类间分布越不均匀的特征项，权重越大，对分类结果的影响越大，对获得更精确地分类结果十分有利[15]。同时，可以利用本文提出的方法和更多别的方法进行组合来继续优化本算法。同时可以考虑新的变异系数的度量方法以便更进一步的提高分类性能，以及是否还要考虑各属性的其他特征以及各属性间的相关性是下一步的研究方向。

[1]杜江，褚帅.智能手机取证研究[J].电脑知识与技术，2011（9）:2120-2121.

[2]Y Yao，Y Zhao.Attribute reduction in decisiontheoretic rough set models[J].Information Sciences，2013.

[3]LS Huang，A Moshchuk，HJ Wang.Clickjacking:attacks and defenses[J].Usenix Conference on Security Symposium，2012.

[4]贾娴，刘培玉，公伟.基于改进属性加权的朴素贝叶斯入侵取证研究[J].计算机工程与应用，2013，49（7）:81-84.

[5]刘磊，陈兴蜀，尹学渊，等.基于特征加权朴素贝叶斯分类算法的网络用户识别[J].计算机应用，2011，31（12）:3268-3270.

[6]王行甫，杜婷.基于属性选择的改进加权朴素贝叶斯分类算法[J].计算机系统应用，2015，24（8）:149-154.

[7]宁荣.基于粗糙集贝叶斯分类的供应商评价研究[J].物流科技，2013，36（5）:124-126.

[8]徐光美，刘宏哲等.基于特征加权的多关系朴素贝叶斯分类模型[J].计算机科学，2014，41（10）:283-285.

[9]梁天超，荆晓远.基于加权RFE-Bayes方法的软件缺陷预测模型[J].计算机技术与发展，2015（10）:131-134.

[10]饶丽丽，刘雄辉，张东站.基于特征相关的改进加权朴素贝叶斯分类算法[J].厦门大学学报:自然科学版，2012，51（4）:682-685.

[11]李翔，程玉胜.基于粗糙集理论的贝叶斯网络分类算法[J].安庆师范学院学报:自然科学版，2014（1）:36-40.

[12]夏燕，徐娜，舒健等.加权朴素贝叶斯模型在高校学科评价中的应用[J].微型电脑应用，2016，32（1）:15-18.

[13]杨敏.基于贝叶斯方法的空间数据分析及应用[D].西安：西安工程大学，2012.

[14]王小丽，远俊红.基于加权朴素贝叶斯分类法的成绩预测模型[J].电子技术与软件工程，2013（19）:225-226.

[15]刘牛.基于属性加权的朴素贝叶斯分类算法改进[J].网络安全技术与应用，2011（6）：72-74.

Application and optimization of algorithm in mobile phone forensics

XIAO Cheng⁃wang，LU Jun，YU Li⁃geng
（Wuhan Research Institute of Posts and Telecommunications，Wuhan430074，China）

In modern society，mobile phone crime phenomenon as a high⁃technology crime，need to study and the corresponding counter⁃measures to deal with，the popularity of intelligent mobile phone make the mobile phone on evidence research to a new height，wherein more and more intelligent mobile phone use Android system.this paper mainly introduces the Android system mobile phone forensics elec⁃tronic sources of evidence and forensic analysis method，finally puts forward using Android system should solve the problem of mobile phone forensics.Naive Bayes is based on an assumption of conditional independence and the assumption can scarcely be satisfied.A weighted naive Bayes classification algorithm based on Coefficient of Variation is proposed.By computing Coefficient of Variation between condition attributes and decision attribute，different condition attributes are weighted differently.With a new method offered first to solve the weights of attributes on the basis of Coefficient of Variation discusses the operation principle of the algorithm，as well as its implementation.

mobile phone forensics；method of forensics；classification algorithm；Naïve Bayes；coefficient of variation

TP301

A

1674-6236（2017）22-0049-05

2016-09-13稿件编号：201609138

肖程望（1992—），男，湖南岳阳人，硕士。研究方向：通信与信息系统。