确定计算机恶意程序样本家族数的系统和方法

摘要

本发明涉及确定计算机恶意程序样本家族数的系统和方法。确定计算机恶意程序样本家族数的系统包括：恶意程序样本特征提取模块，其提取恶意程序样本的特征并计算每两个恶意程序样本间的距离，得到距离矩阵D。恶意程序样本距离计算模块，其计算恶意程序样本间的距离。家族间距离计算模块，其计算两个家族之间的距离。恶意程序样本聚类模块，其逐层对恶意程序样本进行聚类，并计算每层聚类结果的VNFS；VNFS计算模块，其计算每层分家族结果的VNFS。上述系统可通过比较各个层次的VNFS值，找到VNFS值最小层的分家族结果，即可得到最优家族个数。

说明书

技术领域

本发明涉及计算机反恶意程序类软件领域，尤其涉及一种确定计算机恶意程序样本家族数的系统和方法。

背景技术

目前，计算机反恶意程序软件对恶意程序文件处理的基本原理是：首先对可疑文件进行鉴定，判定其属于正常程序或者恶意程序；对确认为恶意程序的样本文件分家族，然后分析同家族恶意程序的特性，提取其“通杀”特征；剩余无法提取“通杀”特征的样本提取“自动”特征，生成相应的恶意程序特征库。根据所生成的恶意程序特征库，计算机反恶意程序软件扫描客户端计算机中的文件，并判断每个文件是否与特征库中的恶意程序特征相匹配，如果匹配则为恶意程序。这里，“同家族恶意程序”指传播途径、功能、内容或行为相同或相似的恶意程序集合；“通杀”特征指能够匹配同家族所有恶意程序的特征；“自动”特征指匹配单一恶意程序的二进制特征。通常，一个“通杀”特征能查杀的恶意程序要远高于一个“自动”特征所能匹配的恶意程序。

随着计算机技术的发展和软件的多样性，恶意代码的数量急剧增长，恶意代码的种类也呈现多样化发展的态势。但是，这些新出现的恶意代码并不是完全没有共性：有部分恶意程序是在原有代码基础上修改生成的，病毒作者根据原有恶意程序的源代码，为了绕过反恶意程序软件的查杀(即“免杀”)，在其基础上做出了一定的修改；而且这些新生成的恶意程序之间也是具有共性的。如果能将恶意程序快速、准确地进行分类(分家族)，将极大地提高计算机反恶意程序软件处理这些新恶意程序的效率，从而缩短对新恶意程序的处理时间，同时有利于提高每个特征的查杀能力，从而缩小恶意特征库的大小。

对于计算机反恶意程序软件厂商所收集的恶意程序样本集中到底有多少个家族，不同的反恶意程序软件给出的结果各不相同，要对恶意程序正确分类和处理，首先必须正确确定恶意程序家族数。因此，恶意程序家族数的确定成为计算机反恶意程序软件在计算机恶意程序处理领域中的重要内容。

近年来，数据挖掘技术的不断发展在一定程度上解决了人们处理海量数据的难题。数据挖掘就是从大量、不完全、有噪声、模糊和随机的应用数据中抽取隐含在其中人们事先不知道，但又是潜在有价值的信息和知识(模型或规则)的过程。聚类算法是数据挖掘领域研究最广泛的问题之一。聚类分析是把相似的目标归类的过程，其目的在于把目标对象划分为一系列有意义的组(或称类)，使得每个组中的目标尽量“相似”或“接近”，而不同组的目标尽可能“相异”或“远离”。把数据挖掘技术中的聚类算法应用于计算机反恶意程序类软件中，可以把具有共性的同家族恶意程序分成一类，同时把差异较大的恶意程序区分开来。但对于给定的恶意样本集，到底该分成多少家族是聚类分析的关键问题之一。

发明内容

针对该问题，本发明提出基于数据挖掘技术的凝聚型层次聚类方法的V_NFS聚类有效性指标来自动确定恶意程序家族数，同时最大可能地将同家族的恶意程序分成一个家族，而将差异较大的恶意程序区分开来。本发明的第一目的是提出一种确定计算机恶意程序样本家族数的系统。

本发明的第二目的是提供一种使用上述系统确定计算机恶意程序样本家族数的方法。

为了实现上述第一目的，本发明采用如下技术方案：

确定计算机恶意程序样本家族数的系统，其包括：

恶意程序样本特征提取模块，其提取恶意程序样本的特征并通过下述恶意程序样本距离计算模块计算每两个恶意程序样本间的距离，得到距离矩阵D。

恶意程序样本距离计算模块，其对不同的恶意程序样本特征采用不同的计算公式，计算恶意程序样本间的距离。

家族间距离计算模块，其计算两个家族之间的距离，计算公式为：

$D_{\mathrm{KL}}=\frac{1}{N_K{N}_L}{\Sigma }_{i\in C_K}{\Sigma }_{j\in C_L}d(X_i,Y_j)$公式(3)；

在公式(3)中，D_KL表示家族K与家族L间的距离，d(X_i，Y_j)表示分别位于家族K与家族L的两个恶意程序X_i和Y_j特征之间的距离，X_i和Y_j分别表示第L族中的第i个样本和第K族中的第j个样本，C_K表示家族K，N_K表示家族K中恶意程序样本的个数，C_L表示家族L，N_L表示家族L中恶意程序样本的个数。

恶意程序样本聚类模块，逐层对恶意程序样本进行聚类(家族)，并根据下述V_NFS计算模块计算每层聚类结果(分家族结果)的V_NFS；V_NFS计算模块，其计算每层分家族结果的V_NFS，计算公式为：

$V_{\mathrm{NFS}}=\mathrm{scat}\left(c\right)-\mathrm{sep}\left(c\right)=\underset{i=1}{\overset{c}{\Sigma }}\underset{k=1}{\overset{n_i}{\Sigma }}{\left|\right|x_{\mathrm{ik}}-v_i\left|\right|}^2-\underset{i=1}{\overset{c}{\Sigma }}{\left|\right|v_i-\bar{v}\left|\right|}^2*(n_i-1)$公式(4)；

在公式(4)中，c代表家族数，n_i是家族i包含的样本数，x_ik是家族i的第k个样本，是家族i的中心点，v_i表示与该家族中所有样本点距离和最小的样本点(恶意程序样本)，v_i的计算公式为：

公式(5)；

在公式(5)中，x_ik表示家族i中的第k个样本，x_ij表示家族i中的第j个样本，(x_ik-x_ij)表示，样本x_ik与样本x_ij的距离，n_ci表示家族i中的样本总数；

是整个数据集的全局中心点，v表示与全局所有样本点距离和最小的样本点，v的计算公式为：

公式(6)；

在公式(6)中，x_k表示全局的第k个样本，x_j表示全局的第j个样本，n表示全局样本的总数。

为了实现上述第二目的，本发明采用如下技术方案：

使用上述系统确定计算机恶意程序样本家族数的方法，其包括如下步骤：

第一步、恶意程序样本数据处理：

根据恶意程序样本特征提取模块提取恶意程序样本的特征，初始时将每个恶意程序样本作为一个家族，并由恶意程序样本距离计算模块采用合适的距离度量方法来计算每两个恶意程序样本间的距离，得到距离矩阵D，矩阵D中的每个元素代表两两家族之间的距离；

第二步、对恶意程序样本进行聚类，并计算各个聚类结果的V_NFS：

当家族数大于用户设定值u时，循环以下操作：

①查找距离矩阵D，合并距离最近的两个家族C1和C2，得到包含|C1|+|C2|个样本的新家族C；

②家族间距离计算模块根据公式(3)计算新家族C到其他家族的距离；

③更新距离矩阵D，删除与C1和C2有关的距离，添加新家族C到其他家族的距离。

④V_NFS计算模块根据公式(4)、(5)、(6)计算当前层分家族结果的V_NFS；

第三步、通过比较各个层次的V_NFS值，找到V_NFS值最小层的分家族结果，即可得到最优家族个数。

聚类是将物理或抽象对象的集合分成相似的对象类的过程。簇是数据对象的集合，这些对象与同一个簇中的对象彼此相似，而与其他簇中的对象相异。本发明中，恶意程序的一个“家族”可以被看成是一个“簇”。本发明中对样本对象的聚类过程，即对恶意程序的分家族过程采用的基本方法为：将每个恶意程序样本各自作为一个原子簇，然后对这些原子簇逐层进行聚合，直至满足一定的终止条件(用户设定的最小家族数u或者1)。该方法称为“凝聚型层次聚类”方法。而如何选择一个最佳的聚类数目，即对于给定的恶意样本集，到底该分成多少类本发明中采用聚类有效性指标V_NFS进行评价，并最终得到最佳的分家族数量。

附图说明

图1为本发明确定计算机恶意程序样本家族数方法的流程简图。

具体实施方式

确定计算机恶意程序样本家族数的系统，其包括：

恶意程序样本特征提取模块，其提取恶意程序样本的特征并通过下述恶意程序样本距离计算模块计算每两个恶意程序样本间的距离，得到距离矩阵D。恶意程序样本的特征可以采用多种表征方式，如：基于N-Grams的字节内容，Windows API序列，指令频度等。

a)基于N-Grams的字节内容：N-Grams指的是可执行文件中的n个连续字节子的序列。例如，串“text”可以由以下N-Grams组成：

bi-grams:_T，TE，EX，XT，T_

tri-grams:_TE，TEX，EXT，XT_，T__

quad-grams:_tEX，TEXT，EXT_，XT__，T___

提取完N-Grams后，统计每个N-Grams出现的频度，并以此

作为该恶意程序样本的特征表征。

b)Windows API序列：PE文件是微软Windows操作系统上的程序文件。Windows API序列是以PE文件对Win API函数调用的静态分析为基础，对样本提取其所调用的Win API函数序列作为特征。

c)指令频度：将恶意程序样本反汇编，过滤可识别的库代码，然后提取样本的汇编指令，统计每个指令出现的频度，构造指令频度向量来表征恶意程序样本。

除了适用于一般的恶意程序样本集，也适用于复杂的恶意程序样本集：

家族大小不一致：在一个数据集里不同家族包含的样本数差异较大，例如，家族Trojan.Win32.Genetik包含300样本，而家族Win32.Hack.PcClient仅包含40个样本。

形状不规则：数据集的空间分布可能构成各种形状。对于规则的球形，椭球形，大部分聚类有效性指标都能很好地描述聚类，正确确定家族数；但当聚类的形状不规则，很多聚类指标就失效了。本发明提出的V_NFS聚类有效性指标能很好处理形状不规则的情况。

家族密度差异大：不同家族的样本在空间分布的密度不均匀的情况。

恶意程序样本距离计算模块，其对不同的恶意程序样本特征采用不同的计算公式，计算恶意程序样本间的距离。针对指令频度和N-Grams两种特征表征方式采用cosine距离度量；针对API序列特征表征方式采用Jaccard距离度量，来计算每两个恶意程序样本间的距离，得到距离矩阵D。给定N个恶意程序样本，其距离矩阵D就是一个非负实数作为元素的N×N(N为恶意程序样本总数)的对称矩阵，矩阵中的每个元素代表两两家族之间的距离。

●两个样本特征x_i和x_j的Cosine距离定义如下：

$S_{\mathrm{ij}}=\frac{x_i^T{x}_j}{\left|x_i\right|\left|x_j\right|}$公式(1)

其中，分子表示两个样本特征向量的内积，分母表示两个样本特征向量长度的乘积。在公式(1)中，x_i^T表示向量x_i的转置，x_i和x_j分别表示第i个样本的特征向量和第j个样本的特征向量，S_ij表示两个样本间的距离。例如，向量x_i＝[1，0，0，1]，向量x_j＝[1，1，0，1]，其Cosine距离为：

$(1*1+0*1+0*0+1*1)/(\sqrt{(1^2+0^2+0^2+1^2)}*\sqrt{1^2+1^2+0^2+1^2)})=$

$2/(\sqrt{2}*\sqrt{3})=0.82.$

●两个样本特征x_i和x_j的Jaccard距离定义如下：

$\mathrm{Jaccard}=\frac{M_{01}+M_{10}}{M_{01}+M_{10}+M_{11}}$公式(2)

其中，分子表示两个样本特征相异部分的长度，分母表示两个样本特征的总长度。在公式(2)中，M₀₁表示向量x_i维度为0而向量x_j维度为1的维度和，M₁₀向量x_i维度为1而向量x_j维度为0的维度和，M₁₁表示向量x_i和向量x_j维度均为1的维度和，Jaccard表示两个样本间的距离。例如，向量x_i＝[1，0，0，1]，向量x_j＝[1，1，0，1]，其Jaccard距离为：(1+0)/(1+0+2)＝0.33。

家族间距离计算模块，其计算两个家族之间的距离，计算公式为：

$D_{\mathrm{KL}}=\frac{1}{N_K{N}_L}{\Sigma }_{i\in C_K}{\Sigma }_{j\in C_L}d(X_i,Y_j)$公式(3)；

在公式(3)中，D_KL表示家族K与家族L间的距离，d(X_i，Y_j)表示分别位于家族K与家族L的两个恶意程序X_i和Y_j特征之间的距离，X_i和Y_j分别表示家族L中的第i个样本和家族K中的第j个样本，C_K表示家族K，N_K表示家族K中恶意程序样本的个数，C_L表示家族L，N_L表示家族L中恶意程序样本的个数。

恶意程序样本聚类模块，采用逐层对恶意程序样本进行聚类，并根据V_NFS计算模块计算每层聚类结果的V_NFS；

V_NFS计算模块，其计算每层分家族结果的V_NFS，计算公式为：

$V_{\mathrm{NFS}}=\mathrm{scat}\left(c\right)-\mathrm{sep}\left(c\right)=\underset{i=1}{\overset{c}{\Sigma }}\underset{k=1}{\overset{n_i}{\Sigma }}{\left|\right|x_{\mathrm{ik}}-v_i\left|\right|}^2-\underset{i=1}{\overset{c}{\Sigma }}{\left|\right|v_i-\bar{v}\left|\right|}^2*(n_i-1)$公式(4)；

在公式(4)中，c代表家族数，n_i是家族i包含的样本数，x_ik是家族i的第k个样本，v_i是家族i的中心点，v_i的计算公式为：

公式(5)；

在公式(5)中，x_ik表示家族i中的第k个样本，x_ij表示家族i中的第j个样本，(x_ik-x_ij)表示样本x_ik与样本x_ij的距离，n_ci表示家族i中的样本总数；公式(5)的含义是，家族i的中心点v_i是指距离家族内所有样本点的距离之和最小的样本点。

v是整个数据集的全局中心点，v的计算公式为：

公式(6)；

在公式(6)中，x_k表示全局的第k个样本，x_j表示全局的第j个样本，n表示全局样本的总数。公式(6)的含义是，整个数据集的全局中心点v是指距离全局所有样本点的距离之和最小的样本。

参见图1，为本发明方法的流程图，本发明计算机恶意程序样本家族数的方法具体包括如下步骤：

第一步、恶意程序样本数据处理：

根据恶意程序样本特征提取模块提取恶意程序样本的特征，初始时将每个恶意程序样本作为一个家族，并由恶意程序样本距离计算模块采用合适的距离度量方法来计算每两个恶意程序样本间的距离，得到距离矩阵D，矩阵D中的每个元素代表两两家族之间的距离(在初始时，矩阵D中的每个元素代表两两样本之间的距离)。本发明中根据不同的特征表征采用不同的聚类度量方法。针对指令频度和N-Grams采用cosine距离度量；针对API序列采用Jaccard距离度量，来计算每两个恶意程序样本间的距离，得到距离矩阵D。cosine距离度量公式为上述公式(1)，Jaccard距离度量公式为上述公式(2)。第二步、采用“凝聚型层次聚类”构造层次树对恶意程序样本进行聚类，并计算各层聚类结果的聚类有效性指标V_NFS。

当家族数大于用户设定值u(u大于或等于1，如果用户未设定该值u，则u值取1)时，循环以下操作：

①查找距离矩阵D，合并距离最近的两个家族C1和C2，得到包含|C1|+|C2|个样本的新家族C；

②家族间距离计算模块根据公式(3)计算新家族C到其他家族的距离；

③更新距离矩阵D，删除与C1和C2有关的距离，添加新家族C到其他家族的距离；

④V_NFS计算模块根据公式(4)、(5)、(6)计算当前层分家族结果的V_NFS。

第三步、通过比较各个层次的V_NFS值，找到V_NFS值最小层的分家族结果，即可得到最优家族个数。

第四步、按照最优的归类结果，对每个样本标定家族编号。

上述第二步的过程实际是逐层合并距离最小的两个家族，直到所有的样本都在一个家族中，或者某个终止条件(达到用户设定的最小分家族数u)被满足，得到一棵或几棵树状图。对于每一层的合并结果，本发明采用聚类有效性指标V_NFS来确定最佳恶意程序家族数，从而确定最佳分解点。随着新生成家族的逐层合并，应该合并成多少个家族是最合理的，需要有一个指标来衡量。这个指标应该使得在同一个家族的恶意程序具有高度的相似性，而不在同一个家族的恶意程序具有较大的差异性。这就要求家族内部尽可能的紧凑，而家族与家族之间的距离尽可能的远离。本发明中的V_NFS聚类有效性指标正是在类内紧凑度与类间分离度之间找到一个平衡点，从而使聚类效果最佳。在上述公式(6)中，函数scat(c)用来衡量类内的紧凑度，值越小越紧凑。函数sep(c)用来衡量类间的分离度，值越大，分离得越好。本发明中聚类有效性指标V_NFS创新之一是采用距离该家族中其它点距离和最小的点作为该家族的中心点，使之能很好的处理形状不规则的样本集；该指标的另一创新之处在于对sep(c)函数的定义，弥补了“紧凑度”和“分离度”度量差别上的缺陷。sep(c)函数必须或尽可能的做到对各种不同分类法，家族的不同大小不敏感，也就是说要归一到统一的共性上。很容易看到随着层次聚类算法往上构树过程的进行，家族内紧凑度越来越差，scat(c)的值从0开始逐渐递增。与传统指标的sep(c)不同，V_NFS的sep(c)在初始时为0，然后迅速递增，达到一个峰值，再逐渐减小。对于家族和家族之间的距离，sep(c)比scat(c)更敏感，当合并两个不该合并的家族时，V_NFS的值就会有重大的改变。因此，V_NFS能在家族内紧凑度与家族间分离度之间找一个平衡点，从而获得最佳聚类效果。

以上实施例描述仅用以说明而非限制本发明的技术方案。不脱离本发明精神和范围的任何修改或局部替换，应涵盖在本发明的权利要求范围当中。