基于改进BP算法的DNS图挖掘恶意域名检测方法

马 骁，蔡满春，芦天亮

(中国人民公安大学信息网络安全学院，北京 102600)

0 引言

恶意域名为近来网络攻击者所使用的主要手段，它也是互联网资源URL的重要组成部分[1]，互联网设置及其相关管理政策中很少有漏洞允许这些恶意域名在DNS服务器上注册。虽然黑名单可以简单、快速识别此类恶意域名，但该技术无法满足域名生成和注册对速度的要求[2]。

前人在研究中已经开始使用DNS数据的特征，一般方法从DNS记录、查询和响应中提取多个特征，并进一步利用历史模式和本地主机的网络流量特征来增强这些特征，基于这些特征和一些训练数据集，可以建立一个分类器来区分恶意域和良性域[3-4]。但这不仅需要识别更多相关的特征，并且这些所依赖的特征稳定性不强，攻击者可以很轻易地改变这些特征，使分类器无法检测出来，其根本原因是现有的研究中所依赖的许多特性都是关于单个域或主机的本地特性。已经有很多检测恶意域名相关研究。在此，将简要讨论与本研究方法最相关的代表性工作。

Notos[5]是使用被动DNS数据识别恶意域名的先驱。Notos基于从DNS查询中提取的特征动态分配未知域的声誉分数。Expose[6]遵循类似的方法，并克服了Notos的一些限制(例如，Expose需要更少的训练时间和更少的训练数据)。此外，Expose的不同之处在于它不知道恶意域提供的服务类型(例如，僵尸网络、钓鱼、快速流动)。本研究通过关注在ip上部署恶意域的全局拓扑，而不是其本地特性，是对Expose和Notos的补充。当Expose和Notos能够访问单个DNS查询时，它们的检测性能最好，这可能是相当敏感的。本研究方法同时适用于公共聚合的被动DNS数据，因此不会引起隐私问题。

Rahbarinia[7]等人提出了一种基于行为的技术来跟踪恶意软件控制的域。其主要思想是从DNS查询日志中提取超出二部主机域图的用户行为模式。相反，本研究使用的技术利用的是被动DNS数据，而不是用户DNS查询行为，Rahbarinia所使用的特性不适用于本研究的被动DNS数据。

Pratyusa K.Manadhata[8]等人提出通过分析DNS查询日志来识别恶意域。其主要技术是建立一个二部主域图(由主机查询哪些域)，然后根据已知的恶意域和良性域，应用置信传播来发现恶意域。其原理是：如果主机查询一个恶意域名，该主机很有可能被恶意域携带的病毒感染，同样被感染主机查询的域名更有可能是恶意的。被动DNS数据也可以被建模为二部图，通过在被动DNS数据上应用信念传播来识别恶意域似乎很有说服力。然而，研究发现推理直觉虽然在主机域图中工作得很好，但在被动DNS数据中推理直觉却不能很好地发挥作用。与主机域图相比，域解析图具有以下几方面优势：首先，被动DNS数据是在全局收集数据，提供了域和ip之间映射的更全面的视图，而主机域图通常仅限于单个企业或ISP的视角；其次，主机域图包含关于单个用户敏感的私有信息，分享这些信息可能会引起严重的隐私问题；再者，域解析图是域ip映射的聚合信息，而不涉及个人的信息，是可以公开共享的。

B.Guan[9]等人设计了一种对域名恶意概率评分的方法。他使用被动DNS数据来构建一个域解析图，并在此基础上，构建了未知域到恶意域的任意路径，给出了未知域恶意概率评分的数学公式。该方法对小标记数据非常灵活，它只关心是否存在从域到恶意的路径，并基于该路经计算恶意分数。与该方法相比，本研究通过对BP算法进行改进，使检测方式更加灵活。DNS图中节点之间的关联是通过DNS数据建立的，并依赖所有节点之间的关联来计算信誉评分，以此判断图中每个节点是否合法。

已有的研究虽然也涉及到被动DNS数据，但本文提出的检测方法与前人所不同的是DNS图中节点之间的关联是通过DNS数据建立的，并依赖所有节点之间的关联来计算信誉评分，从而判断图中每个节点是否合法。并且该方法也是基于域分辨率图的，考虑到马尔可夫随机场(MRF)，我们采用了一个新的置信传播算法来获得域的恶意评分。

通过对BP算法的改进，并使用精确率(也称查准率)、召回率(也称查全率)、正确率、F-measure和ROC曲线下面积(AUC)来衡量该方法的有效性，精确率、召回率和正确率均超过95%，F-measure和AUC也展示出良好的结果。在实验操作中，以域名和主机ip为数据源构建DNS图，挖掘域和主机ip之间的内在关系，并基于BP算法的思想开发了一种基于同质化关系计算图中每个节点信誉评分的算法。

1 可用于图挖掘的BP算法

在信息产业如此发达的今天，用户产生了大量的数据，这些数据包含有许多信息，为了从数据中提取有价值的信息，数据挖掘应运而生，而图挖掘正是数据挖掘的重要组成部分，图挖掘是指通过图模型的方法来提取数据。

被动DNS通过复制用户在其DNS基础设施中自愿部署的传感器捕获服务器间的DNS消息，并将捕获的DNS消息进一步处理，然后存储在一个中央DNS记录数据库，就可以对其进行各种查询，它提供了域和ip之间映射的全面视图[10]。我们使用网站的API从www.dnsdb.info下载了被动DNS数据库，被动DNS数据包含了DNS不同方面的丰富信息，本文主要分析DNS数据中的A记录，仅使用(d,ip)两列[11]。d为域名，解析为ip。尽管DNS记录的许多特征都可以被它所属的域名进行改变，但攻击者必须在其控制或访问的ip上托管恶意域名。此外，一些恶意域名经常采用逃避检测策略，如频繁创建新域名、更换域名等措施，使其动态特征存在于恶意域名组之间，而不是单个域名[12]之中。实际上恶意域名正在随着时间的推移在互联网空间中大量移动，同时在移动的过程中共享一些不同的特性。因此，很有可能多个恶意域名最终被托管在同一个ip上，同样也有可能多个ip被用来托管同一个恶意域名，这在它们之间创建了内在的关联。为了消除这种关联，攻击者必须尽量减少托管恶意域的ip数量以及每个ip所托管的恶意域的数量。而要做到这一点，攻击者则会付出极高的成本代价，并限制自身对可用资源的利用。因此，我们认为域名和ip之间的关联为研究攻击者如何组织和部署恶意资源提供了一个可靠稳定的方法，这可以进一步用于图的构建。所构建的图是一个二部图，一边对应域，另一边对应ip，如图1所示，它只有域名与ip的连接。如果存在A记录中存在(d，ip)两列，则从域d到ip形成一条边，在图1中由箭头表示。

图1 域名解析图

置信传播算法(Belief propagation,BP)也被称为和积消息传递[13]，像贝叶斯网络和马尔可夫随机场都是对图形模型(GM)执行推理的消息传递算法，以任何观察到的节点为条件来计算每个未观察到的节点的边缘分布。置信传播算法是人工智能和信息理论中常用的方法，并在许多应用中得到应用[14-15]。

作为马尔可夫随机场模型的基础，BP算法最重要的元素之一是马尔可夫特性。BP算法依赖于图上节点的交互，当BP在图上运行时，消息在任意两个相邻节点之间按照马尔可夫性质进行交互。因此，在解释所提算法的操作之前，首先简单地讨论一下马尔可夫随机场。

马尔可夫随机场(MRF)是一组具有马尔可夫性质的随机变量，由无向图描述。无向图G=(V,E)，其中V=v1,v2，…，vn是顶点集合。每个顶点对应一个随机变量[16]，因为它具有马尔可夫性质，因此它只依赖于其相邻节点的性质。给定一个节点vi∈V,Ni是节点vi的邻居集，如果(vi,vj)∈E，且vj∈Ni，则节点vi是节点Ni的邻集。那么MRF符合局部属性:

(1)没有结合物联网，实物信息没有上链，实现共享。传统的货物信息监督依靠第三方监管，或者是核心企业本身，信息有一定的滞后。实物信息没有定量化，后期跟踪成本高，影响信息对称的问题，阻碍了供应链金融的发展。

P(vi|vjvj∈V/vi)=P(vi|vjvj∈Ni)

(1)

将MRF模型的上述特性应用到DNS图中，DNS图的每个顶点对应一个随机变量，该随机变量代表主机ip或域名的随机变量[17]。然后，为了检测恶意域，定义一个知识集为D=(dl,dm)，其中vi=dl表示该主机ip或域是合法的，其余表示该主机ip或域是恶意的。

2 用于DNS图挖掘恶意域名检测的BP算法改进

本研究提出的方法承继了BP算法的所有特性，并添加了一些条件来优化操作，提高算法的性能以获得最终结果。该算法允许图中的每个节点通过传递消息作为证据与其邻域进行交互，以评估其邻域的标签。算法开始时，给图上的每个节点vi赋初始值为恶意概率，标记为函数Fi(vi)。节点的fji(vi,vj)=P(vi|vj)，即节点vj具有标记vj时，vi具有vi的概率。因为图是无向的，所以相邻两个节点的势函数是对称的，即fji(vi,vj)=fji(vj,vi)，如表1所示:

表1 两个节点之间的推断表

其中0

该算法的原理是基于消息传递，一个消息从vi发送到vj，问节点vi如何看待它邻居的标签。消息从vi传递到vj标记为mij(xi)，如图2所示。对于∀eji∈E，将消息mij(vi)和mji(vj)按以下公式计算，计算节点vi到节点vj的消息:

(2)

如公式(2)所示，当节点vi希望向节点vj发送消息时，必须先收集其相邻节点的所有消息，然后再向节点vj发送消息。在BP方法中，所有节点都实时地将自己的想法发送给它们的邻居，但没有必要这样做，因为并不是图上的所有节点都有知识可以发送给它的邻居。例如在第一次交互中，只有知识节点可以向它的邻居发送消息，告诉他们如何看待自己的恶意概率，因为所有剩余的节点的恶意概率都是0.5，告诉它的邻居的恶意概率是没有意义的。所以我们设置一条规则，只有节点的恶意概率不等于0.5时才发送消息。加入算法的第二条规则是考虑知识节点的恶意概率。在每次交互中，知识节点的概率不应该再次计算，因为它的标签是已知的，无论它的邻居怎么想它都不能改变。

图2 信息间的传递

(3)

(4)

(5)

3 实验

3.1 实验准备

通过在www.alexa.com、Bambenek Consulting (https:∥osint.bambenekconsulting.com/feeds/)和360网络安全实验室(https:∥data.netlab.360.com/dga/)上可以收集到实验所需的十万个良性域名和十万个恶意域名。将这些域名分为两组，一组用于训练模型，一组用于实验。

实验所用来构建DNS图的数据从DNS数据服务器中收集，被动DNS数据包括域名系统不同方面的丰富信息，本文主要分析域名系统数据中A记录的域名和ip数据。由于Graphlab上的几乎所有功能都是并行运行的，可以快速高效地得到结果和数据，所有的处理都是在Graphlab上远程完成的。Graphlab在处理对象之间关系数据时表现出良好的性能。虽然实现起来相当复杂，但对于某些网络问题来说，它要优于其他的方法。

首先对无知识的子图进行处理，DNS图中并不是所有节点都可以连接在一起成为大图，因而DNS图中存在大量的子图，而有些子图对恶意域和合法域一无所知，从而不能计算出恶意评分，所以，将他们从构建的图表中删除。其次，实验通过直接与BP算法交互来提高算法性能的结果，BP算法的主要思想是在接收到邻居节点的消息后，改变图上所有节点的概率。但恶意节点或白节点是已知的，其概率不应改变，因此，在实验中，知识节点的概率固定为初始值。通过进行对比实验，将改进BP算法与标签传播算法[18]以及通过被动DNS数据图分析发现恶意域名的方法进行比较，说明改进方法的有效性。

从图上所有顶点和边的初始值开始，该算法将挖掘出的图与已知的部分图一起进行处理，从而判断其恶意或合法。这被称为先验知识，恶意节点的初始声誉得分为0.99，合法节点为0.01。所有其他节点为未知标签，它的声誉评分为0.5。在所有边中，一个常数值表示两个相邻节点的关系，如表1所示。BP算法将在具有上述初始值的图上进行挖掘，并运行至满足某个阈值或达到交互次数的限制为止。但在实验过程中阈值固定设置为0.005，对于任何子图，所有节点的消息传递将以最大10次进行交互。收敛条件设为:

(6)

3.2 实验结果

通过使用精确率(也称查准率)、召回率(也称查全率)、正确率、F-measure和ROC曲线下面积(AUC)来衡量改进BP算法的有效性，准确度是通过得到模型正确识别的个体数与识别出来的个体总数之比来反应其正确率；召回率是正确识别的个体总数与测试集中存在的个体总数之比；F-measure值是精确度和召回率的调和平均值；ROC通过预测正例排在负例前面的概率来衡量二分类模型优劣程度。

为了证明本研究提出的改进方法在性能上的优越性，将改进的BP算法与标签传播算法[18](Label Propagation Algorithm)以及基于被动DNS数据图分析检测恶意域名[19]进行对照，与处理此数据的步骤相同，也是在Graphlab中完成操作。LPA是基于图的半监督学习方法，它的思路是基于标记的节点信息去预测未标记的节点信息。对照结果如下所示，其中图3是3种算法的ROC曲线，图4是3种算法的P-R曲线，表2为3种算法的性能对照。

图3 3种方法的ROC曲线

图4 3种方法的P-R曲线

表2 3种方法的性能对照

通过比较3种方法的ROC曲线以及精确率等性能指标，不难看出本研究的改进BP算法与其他两种方法相比优势明显。同时我们也表明这个结果与标签传播中的恶意域并不矛盾，因为他们的方法是针对不同类型的数据进行推断而设计的。

4 结束语

本文提出了一种基于DNS图的恶意域名挖掘方法，通过添加算法的条件来改进BP算法，并将改进后的BP算法应用于基于DNS图的恶意域检测中。DNS图能表示域之间的关系及其ip地址，在对图上所有节点设置初始值后，使用置信传播法计算图节点的信誉，这种方法在关系分类问题上取得了显著的效果。该算法应用于真实DNS流量，其精确率、正确率和召回率均超过95%，这表明，该方法在实际应用中对恶意域检测是有效的。此外，此方法并不限定于特定的DNS技术，对于DGA、恶意软件、僵尸网络等都可以发挥作用，具有较强的可扩展性和有效性。因此，实验结果证明了提出的改进BP算法可以很好地解决恶意域检测问题。目前，本研究仅使用被动DNS数据库中的A记录构建DNS图，下一步如何将记录类型扩展为NS、MX、PTR等，以增强节点间的关系，并评估改进后的检测效果是需要我们进一步研究的内容。