基于UPGMA的恶意代码系统发生树构建方法

开篇：润墨网以专业的文秘视角，为您筛选了一篇基于UPGMA的恶意代码系统发生树构建方法范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

【 摘 要 】 借鉴生物信息学中的物种系统发生树构建方法，提出了基于恶意代码函数调用图和非加权组平均法（upgma）的恶意代码系统发生树构建方法，并利用恶意代码函数调用图的相似性距离数据对本方法进行了实验。此方法能够为恶意代码的同源及演化特性分析研究与恶意代码的检测和防范提供有力的支撑和参考。

【 关键词 】 恶意代码;函数调用图;UPGMA法;系统发生树构建

A Method Constructing the Phylogenetic Tree of Malware Based on UPGMA

Jiang Zhi-xiong Wang Bao-sheng Sun Zhi-feng Tang Yong Tian Shuo-wei

（Department of Computer Science，National University of Defense Technology HunanChangsha 410073）

【 Abstract 】 Using for reference on the methods that construct the phylogenetic tree among genes or speces in bioinformatics， this paper presents a method that constructs the phylogenetic tree of malware based on function-call graphs of malware and UPGMA method， and do some experiments using value of the similarity distance of marware’s function-call graphs （called SDMFG）.This method provide a strong support and reference for analysis of the homology and evolution characteristics of malware and malware detection and prevention.

【 Keywords 】 malware; function-call graphs ;upgma method; phylogenetic tree

1 引言

恶意代码分析是检测和防范恶意代码的重要基础。随着恶意代码开发的各类源代码、技术文档和辅助工具的日益丰富，恶意代码的产生更为简单和模块化，变种和演化更为多样和快速，数量呈加速增长的趋势，每天捕获成千上万个样本已经是很平常的事了。在实际中，除了分析恶意代码的各种外部表现，人们还关心恶意代码在同源和演化方面的内在特性，包括恶意代码从何而来、如何发展变化以及家族之间和变种之间的关系等等。

本文将通过IDA工具和插件提取每个恶意样本的函数调用图，计算出每两个恶意代码函数调用图之间的相似性距离，构造一个距离矩阵，利用生物信息学中的UPGMA法建立这组恶意代码样本的系统发生树，从而体现恶意代码的同源性关系，对恶意代码样本的演化分析和聚类分析提供帮助。

2 函数调用图的相似性距离

文献[1]提出了一种函数调用图的相似性度量――恶意代码函数调用图的相似性距离（SDMFG， The Similar Distance of Malware’s Function-call Graphs）。此度量方法主要是借鉴编辑距离的思想，把两个恶意代码函数调用图的相似性看做由一个图转化为另一个图的最小成本，用顶点间的匹配操作代替图的编辑操作、匹配路径代替编辑路径、匹配成本代替编辑成本，综合函数指令序列的相似性以及函数的调用关系的相似性计算顶点的相似性，并把1与顶点的相似性之差作为顶点间匹配的成本，最后通过计算完美匹配路径的最小匹配成本来度量两个恶意代码的函数调用图的相似性。

3 UPGMA法构建系统发生树

3.1 系统发生树

系统发生树，也称进化树，是三个或者更多基因或者生物体之间进化关系的典型图示。它是由一系列节点和分支组成的，其中每个节点代表一个基因或者生物体。分支末端的节点（外部节点，也叫叶节点）对应一个基因或者生物体。内部节点代表一个推断出的共同祖先，它在过去的某个时候分歧出两个独立的分支。这样的树浓缩了千言万语，不仅表示了数据集之间的关系，还体现了它们的分歧时间和它们共同祖先的特征。

系统发生树结构的基本信息在计算机程序中常常用Newick格式表示。例如用Newick格式来表示图1中的树，可写成{[（A，B），（C，D）]，E}。

3.2 UPGMA法

在生物信息学中，通常都是用物种的系统发生树（即进化树）来表示物种之间的进化关系的，系统发生树的构建方法主要有两种：一种是基于距离数据构建，一种是基于特征数据构建。由于本文利用的是恶意代码函数调用图的相似性距离数据，所以主要借鉴生物信息学中基于距离的系统发生分析方法。

利用UPGMA构建进化树时，首先用n个叶节点表示n个分类单元（序列），每个分类单元自成一类，然后从距离矩阵中选择距离最小的一对分类单元聚为一类，形成一个新的分类群，并计算这个新的分类群与其他分类单元之间的距离，得到一个新的距离矩阵，重复上述过程，最终会得到一个以所有分类单元为叶节点的系统进化树。

UPGMA法是树重建方法中比较简单的一种。该方法是基于统计的，像所有基于距离的方法一样，要求数据能够精简为所有被研究的物种两两之间遗传距离的度量。一般来说，UPGMA方法需要建立一个距离矩阵，例如为4个物种A、B、C和D建立的矩阵，假设其两两距离如表1所示。

在这个矩阵中， dAB表示物种A和B之间的距离，dAC表示物种A和C之间的距离，以此类推。 非加权组平均法的基本思想是：首先将两个距离最近的物种合成一个复合物种组。这里，假设距离矩阵中最小值是dAB，所有物种A和B首先合成一组（AB）。第一次聚类后，要更新距离矩阵，计算新组（AB）与物种C和D之间的距离：d（AB）C=（1/2）（dAC+dBC），d（AB）D=（1/2）（dAD+dBD）。然后，将新的距离矩阵中距离最小的两个物种再次合成一个复合物种组。如此反复，直到所有物种都聚为一类。如果在树中用分支长度表示物种之间的进化距离，则分支点位于原来两个物种之间距离的一半处（例如在第一次聚类中，dAB/2分支点所在位置）。

确定进化分支图中每一条分支的相对长度，只要利用距离矩阵中的信息进行简单计算。如果假设所有家系的进化速率不变，那么内部节点将置于与分叉树上相对应的两个物种距离相等的地方。例如，物种A和B之间的距离（dAB）是10，那么连接这两个物种和它们共同祖先的一对分支均应为dAB/2，即5.0。这个简单的估计分支长度的方法使得UPGMA成为能构造有根系统发生树的少数几种方法之一。

3.3 构建系统发生树

这里简要介绍下UPGMA法构建恶意代码样本系统发生树的具体算法。

算法：

输入：一组n个恶意代码样本及其任意两个之间的函数调用图的相似性距离d;

输出：这组恶意代码样本系统发生树T。

有几个步骤。

（1）构建n个恶意代码样本的距离矩阵C1，每列都对应一个恶意代码样本，从第一个恶意代码样本到第n-1个样本，每行也都对应一个恶意代码样本，从第二个样本到第n个样本;矩阵元素的值就是所对应的两个恶意代码样本之间的函数调用图的相似性距离d;构建完矩阵之后进入步骤（2）。

（2）找到距离矩阵C1的值最小（即相似性距离最小）的元素，将它对应的两个恶意代码样本A和B合成一个复合样本组（AB），并计算连接这两个样本和它们共同祖先的一对分支的长度dAB/2，进入步骤（3）。

（3）更新距离矩阵。如果距离矩阵C1中有A列和B列且只有A或者B行，则将距离矩阵C1的A列和B列合成一列（AB）并将B行（或者A行）去掉，其余不变，得到了一个新的（n-2） （n-2）的距离矩阵C2;如果距离矩阵C1中有A行和B行且只有A或者B列，方法类似;如果距离矩阵C1中有A列和B列且有A行和B行，则将距离矩阵C1的A列和B列合成一列（AB），将距离矩阵C1的A行和B行合成一行（AB），其余不变，得到了一个新的距离矩阵C2。进入步骤（4）。

（4）计算距离矩阵C2。首先分别计算距离矩阵C2中与复合样本组（AB）相关的位置的矩阵元素的值，计算方法如下：新组（AB）与任一样本C的距离=（样本A与样本C的距离+样本B与样本C的距离）/2，即d（AB）C=（1/2）（dAC+dBC）;这样计算新组（AB）与剩下的所有样本之间的距离，并填入距离矩阵C2相应的位置;与复合样本组（AB）无关的矩阵位置，它们的值不变;进入步骤（5）。

（5）重复步骤（2），即在距离矩阵C2中找到值最小的元素，将其对应的两个恶意代码样本再次合成一个复合样本组;重复步骤（3）（4），直到这n个恶意代码样本都聚为一类。

（6）根据前面聚类过程，重建这n个恶意代码样本的系统发生树T。

下面用一个实例来说明UPGMA算法构建系统发生树的过程。对一组5个恶意代码样本（A、B、C、D和E），且它们之间的两两函数调用图相似性距离分别如表2所示，易知，样本D和E的相似性距离是距离矩阵C1中最小的元素值（dDE=1.9），所以样本D和E聚到一组，并合成一个复合样本组（DE），连接这两个样本和它们共同祖先的一对分支的长度dDE /2=0.95。

因为距离矩阵C1中有D行和E行且只有D列，去掉D列，合并D行E行，得到了一个3×3的距离矩阵C2。然后计算新的距离矩阵C2，dA（DE） = （1/2）（dAD+ dAE） = 4.9，dB（DE）= （1/2）（dBD+ dBE）=3.9，dC（DE）= （1/2）（dCD+ dCE） = 3.1，样本D和E之外的3个样本中任何两个样本的相似性距离不变，距离矩阵C2如表3所示。

可见，样本A和B的相似性距离是距离矩阵C2中最小的元素值（dAB=2.8），所以样本A和B聚到一组，并合成一个复合样本组（AB），连接这两个样本和它们共同祖先的一对分支的长度dAB /2=1.4。方法同上，计算新的距离矩阵C3，d（AB）C= （1/2）（dAC+ dBC） = 4.0，d（AB）（DE）= （1/2）（dA（DE） + dB（DE）） =4.4，其余元素值继承距离矩阵C2中对应元素的值。距离矩阵C3如表4所示。

样本C和复合样本组（DE）的相似性距离是距离矩阵C3中最小的元素值（dC（DE）=3.1），所以样本C和复合样本组（DE）聚到一组，并合成一个复合样本组（C（DE）），连接这两个样本和它们共同祖先的一对分支的长度dC（DE）/2=1.55。去掉C列，并用C行和DE行合并成（C（DE））行，得到了一个1×1的距离矩阵C4。然后计算新的距离矩阵C4，d（AB）（C（DE）） = （1/2）（d（AB）C+ d（AB）（DE）） = 4.2，距离矩阵C4如表5所示。

复合样本组（AB）和复合样本组（C（DE））的相似性距离是距离矩阵C4中最小的元素值（d（AB）（C（DE）） =4.2），所以复合样本组（AB）和复合样本组（C（DE））聚到一组，并合成一个复合样本组（（AB）（C（DE））），连接这两个样本和它们共同祖先的一对分支的长度d（AB）（C（DE）） /2=2.1。

4 实验结果与分析

实验中的数据集来自于Kaspersky的恶意代码样本。这些恶意代码样本包括Trojan、virus、worm和backdoor等种类。每个恶意代码样文件的名字都是由恶意代码名称以及样本哈希值构成。所有工作都是在Windows XP系统上，用C语言编写并在VC6.0上实现的。

我们选取了7个Trojan.Win32样本、4个Trojan-Dropper.Win32.VB样本、3个Virus.Win32.Virut样本和2个Trojan-Downloader.Win32.CodecPack样本进行函数调用图的提取，并计算了他们两两之间的SDMFG值。根据这些值利用UPGMA法进行分析，得到的系统发生树如图2所示。

图中右边是各个恶意代码样本的名称，左边是用线段表示的恶意代码样本间的同源关系，其中用直线连接恶意代码样本或者由恶意代码样本构成的复合样本组及它们的父节点，线段的长度体现了恶意代码样本或者由恶意代码样本构成的复合样本组到它们父节点的分支长度。其长度由下面的标度尺统一度量。

容易看出，同一恶意代码的不同样本基本分在一类里，而不同恶意代码的样本则没有分在一起，同一恶意代码的不同样本之间的分支长度很小，而不同恶意代码的样本之间的分支长度较大，所以同源分析结果比较好，基本体现了实际情况。

实验验证了基于恶意代码的函数调用图和UPGMA法对恶意代码的同源关系进行分析的方法具有技术可行性，表明该方法既能正确反映同类恶意代码样本之间的演化关系，体现了代码的演化方向，也能区分不同类恶意代码样本的家族属性。

5 结束语

本文利用生物信息学里的UPGMA法为恶意代码样本构建了系统发生树，比较深入和准确地刻画了样本之间的相似性，形象地描述了样本之间的演化关系。此方法能够为恶意代码样本的自动聚类分析以及样本的演化发展和同源性分析提供有效的参考和支持。

参考文献

[1] 刘星，唐勇，黄遵国，李琰，官强.恶意代码的函数调用图相似性分析[J].计算机工程与科学，2013.

[2] David W主编，钟扬，王莉，张亮，主译.生物信息学.高等教育出版社，2003.

[3] Dan E.Krane& Michael L.Raymer.生物信息学概论[M].北京：清华大学出版社，2004.

[4] Simmons MP，Müller KF，Norton AP. Alignment of and phylogenetic inference from random sequences： The susceptibility of alternative alignment methods to creating artifactual resolution and support. Molecular Phylogenetics and Evolution，2010，57（3）：1004-1016.

[5] Liu L，Yu L，Kubatko L，Pearl DK，Edwards SV. Coalescent methods for estimating phylogenetic trees. Molecular Phylogenetics and Evolution，2009，53： 320-328.

[6] 朱雯.基于距离矩阵的进化树构建方法研究[D].长沙：湖南大学，2010.

[7] 方志鹤.恶意代码分类的研究与实现[D].国防科学技术大学， 2011.

[8] 左黎明，徐保根，汤鹏志，刘二根.未知恶意代码族群归属决策研究[J].微电子学与计算机， 2012.

[9] L.A.Goldberg，P.W.Goldberg，C.A.Phillips，et al.Constructing computer virus phylogenies[J]. Journal of Algorithms，1998，26（1）：188-208.

[10] M.Hayes，A.Walenstein，A.Lakhotia.Evolution of malware phylogeny modeling systems using automated variant generation[J]. Journal in Computer Virology， 2008：1-9.

[11] Xin Hu，Sandeep Bhatkar，Kent Griffin，Kang G. Shin. MutantX-S： scalable malware clustering based on static features. 2013 USENIX conference on Annual Technical Conference，2013.

基金项目：

国家自然科学基金，项目编号61472437。

作者简介：

江志雄（1985-），男，云南昆明人，国防科学技术大学硕士在读;主要研究方向和关注领域：网络与信息安全。

王宝生（1970-），男，河北沧州人，国防科学技术大学计算机学院研究员，博士生导师;主要研究方向和关注领域：网络与信息安全。

孙志峰（1978-），男，河北冀州人，国防科学技术大学硕士在读;主要研究方向和关注领域：网络安全。

唐勇（1976-），男，湖南衡阳人，国防科学技术大学计算机学院助理研究员;主要研究方向和关注领域：网络与信息安全。

田朔玮（1984-），男，内蒙古呼和浩特人，国防科学技术大学硕士在读;主要研究方向和关注领域：计算机网络安全。