通过机器学习进行恶意软件分析：Deepviz中的聚类算法基本原理
去年以来，我们发现很多的音像公司开始接触机器学习和人工智能，希望能找到一条快速有效的途径来分析并隔离新型的恶意软件，同时，扩大恶意软件库。然而，事实上这里存在一个很大的问题就是很多人把机器学习当成了无所不能的魔术棒——他们开始用机器学习的时候，只是把尽量多的样例交给算法去计算，就算完成了，而事实上这样做不完全正确。
0×00 简介
Deepviz是一款强大的恶意软件自动分析平台，也是一个强大有效的智能威胁情报平台，除此之外它还能够对所有由恶意软件分析仪中提取的数据进行分析，通过关联算法做出最好的抉择。
机器学习是Deepviz用到的关键技术，它能够识别新型恶意软件，还能找到相似的样品进行关联，并扩大的恶意软件库。但实际上，执行一个有效的机器学习算法并不像大多数人想象的那么简单——并不是“给智能机器尽量多的详细的信息，它就会自己找到诀窍”。
接下来我们一步步的探索机器学习的原理。
0×01.聚类算法
聚类分析是一种统计分析技术，目的在于从给定的数据集合中识别出重要的群组。我们可以通过已有的恶意软件群组发现与之相似的新型恶意软件或者与这个群组具有相同特征的样例。为了给一个数据集合分组，我们需要一个表达式来描述数据集合中每个元素间的相似性。
每一个元素用一个特征集合描述，这个特征集合的属性在某些方面对这个元素非常重要。设计特征集合的时候，有两个要点需要考虑到：
第一，要明白如何选择属性。正如上面所说，很多人以为聚类分析就应该让分析程序提取数百万属性进行计算，却忽略了一点：被考虑进来的属性越多，计算的时间也会越多，而且，有些属性并不能用于准确区分出恶意软件。例如，用PE文件的唯一熵属性做为特征集合将会导致错误的聚类化。不过无论如何，我们需要找到足够多的属性可以让我们将一些具有特殊行为的恶意软件分成几个不同的恶意软件群组。所以我们要提取的属性是对恶意软件分析有意义的属性， 这也是Deepvid恶意软件分析器最大的组成部分。
第二，找到最合适的量度来验证并且对比恶意软件的属性。每个恶意软件都可以被描述成数值性质的属性(例如：信息熵)或者抽象性质的属性。在数学上，相似度度量就是用来描述两个对象的相似程度。欧式距离就是其中一种被广为人知的用于比较数值型属性相似度的方法。那么，抽象型数据的相似性该如何度量呢？Deepviz中给出了两个恶意软件以及与之相关的IPs和URLs，我们该如何比较这两个集合呢？怎样把他们进行聚合？
举个例子说明，如下图片展示的是所有访问过网站complifies.ru的软件的MD5聚合：
我们的聚类算法把样本分成4个不同的群组，上图是整个聚合过程的最后一步截图。
要想得到相似集合，我们需要知道每个元素和其他元素之间在哪些方面相似，或者说哪些方面不同。这些值可以通过距离矩阵表现出来。
基于此，我们需要得到的东西是：
1.选择一个特征集合，该集合由一个或者多个属性组成，通过该集合可以将原始数据集合中的元素进行分类。 2.选择一个计算距离的算法，通过该算法可以计算各个元素间的距离。 然后，我们需要做的步骤是： 3.比较一个元素与该元素本身的距离，以及该元素与数据集合中其他元素的距离 4.用一个聚类算法来把相似的元素聚合。在我们的例子中，我们聚合的是恶意软件群组
元素间的相似度
欧式距离被大量的运用在计算数字型的元素之间的距离。在这里，我将介绍的是另一种计算距离的方法—杰卡德距离(Jaccard distance)，作为抽象型数值的度量。
先给一个例子，以下是两个样本以及与他们有关的URLs列表，计算出集合中每个元素与该样本的相似度，具体结果如下
样本
26414a9d627606c4974d8c3f372b0797 和 27f72541c93e206dcd5b2d4171e66f9a:如下：
具体结果页面：
https://intel.deepviz.com/hash/26414a9d627606c4974d8c3f372b0797/
https://intel.deepviz.com/hash/27f72541c93e206dcd5b2d4171e66f9a/
杰卡德相似度用于比较抽象数据点之间的相似程度，是最广泛使用的相似度算法。该算法被定义为两个结合交集的元素个数占并集的比重。如果两个集合没有重复的元素，那么杰卡德相似度就是0。如果两个集合所有元素都一样，杰卡德相似度就是1，杰卡德相似度的计算公式如下：
思考一下下面的题目：
1.集合A由19个元素组成
2.集合B由12个元素组成
3.两个集合相交的元素总共有4个
通过杰卡德公式可以推算出两个集合的相似度是0.15 因此上面的公式同样可以变形用距离计算的公式，如下：
distance = 1 – similarity
如果我们计算所有样本间的杰卡德距离，就能得出以下的距离矩阵：
如图，集合A与B的距离是0.15，A与C的距离是0.8等等。元素和他本身的距离是0，对称的，A与B的之间的距离和B与A之间的距离是一样的，是以对角线对称的。为了优化矩阵的计算时间，我们可以使用这个对称的性质只计算一半的矩阵。
矩阵计算完后，就能把这个距离矩阵输入到聚类算法中进一步计算。从这里我们可以看出，从数据中提取的属性越有效，接下来的聚类算法聚合出的结果也将越准确。
聚类算法（DBSCAN）
聚类算法通过元素间的距离对各个元素进行分类。更简单地说就是一个元素与其所在的集合的距离，这也包括特征集合中的元素。那么，我们如何将这个算法运用到恶意软件分析中呢？
DBSCAN(基于密度的聚类算法）是一个比较有代表性的基于密度的聚类算法，这个算法是在于将簇定义为密度相连的点的最大集合，把具有足够高密度的区域划分为簇，并可以在噪声的空间数据库中发现任意形状的聚类
前面，我们已经计算出了集合的距离矩阵，因此我们就可以知道每一个元素与任意一个其他元素的距离。
这个算法需要有两个输入：
1.最小密度（min_pts） 2.扫描半径（eps）
如下图所示：
1.密度：某个点为中心，半径为eps的区域内的点的个数称为该点的密度。 2.核心点：以该点为中心，半径eps的区域内的点的个数大于最小包含点数（min_pts），则这个点称为核心点，这些区域内的点形成一个簇 3.边界点：密度小鱼最小包含点数（min_pts）的点称为边界点，有趣的是边界点其邻域内包含至少一个核心点。 4.噪声点：不属于核心点或者边界点的就是噪声点
从以上的定义中可以知道，每一个形成的簇都至少包含有min_pts个点。 eps半径的值设定的越高，簇的形成的限制就会越小。中等距离的样例可能就会被划分进同一个簇，原来是噪声的点可能变成边界点（甚至是一个核心点）。所以说，Min_pts和eps的值在我们的恶意分析程序里面可能会做出一定的改变。
另一方面需要说明的是，一个噪声点并非和簇一点关系都没有，这依赖于我们是否想要找到新的变种或是替代已有的恶意软件簇。
现在，我们再多举几个例子感受下。
在前面的例子中，我们已经通过“URLs”作为特征属性得到了元素间的距离，接下来我们通过IPs来做聚类。
从我们的网络威胁感知记录的页面中，我们发现一个有趣的IP：1.234.83.146
通过我们的威胁感知系统的API，我们发现1.234.83.146这个IP与我们的353个样例同时有关联
第一步，我们用杰卡德距离算法计算所有所有样例与IPs列表得到的距离矩阵，
杰卡德距离的值从0（表示两个样本具有相同的IPs列表）到1（表示两个样本毫无关系），然后我们通过DBSCAN算法计算出簇，其中半径eps为0.5，最小密度min_pts设置成1，这意味着噪声点也会变成一个簇。
需要说明的是，上图并不是DBSCAN算法算出的结果，上图只是距离矩阵在空间图上的表述而已，矩阵图需要进一步计算才能得到簇。有图明显可以看出，DBSCAN划分了两个簇，其中簇的完整信息下载地址： https://deepvizblog.files.wordpress.com/2016/01/cluster1.docx
然后我们试着把参数的值改变下，看看结果：把半径eps设置成0.1，最小密度min_pts设置成1
正如预料的那样，DBSCAN算法划分出了更多的簇
具体的信息下载地址： https://deepvizblog.files.wordpress.com/2016/01/cluster2.docx
以上只是一些很简单的例子，但你可以通过聚类算法识别出更多新的样本，无论是不是恶意软件簇，只要能提取到正确的数据，他就能帮你识别并孤立恶意软件。
以下是我们威胁感知平台得到的一些孤立样本
Deepviz Threat Intel 290f3104a53cc5776d3ad8b562291680 4fa660009cba0b3401f71439b885e067 6368cc6d88c559bb27da31ef251a52a1 27bd99bf75491447fb3383d1f54f4e40 c7b19f8250b70ae5bd46590749bf9660 8f68c9a4a1769f57651a6a26b0ea2cf9
正文到此结束
热门推荐
相关文章
近期评论
-
666
-
文章和留言都翻到11页了 没有OOM
-
-
朋友，翻页到11页，及以后，会出现OOM，无法访问
-
-
-
-
版本号是多少，你可以下载哪个代码仓库，jdk选1.8 直接跑就行
-
-
Loading...
![[HBLOG]公众号](https://www.liuhaihua.cn/img/qrcode_gzh.jpg)
