王 骞，闫夏莉，叶崛宇，张海阔，李真辉

(中国互联网络信息中心，北京 100190)

0 引 言

DNS(Domain Name System)是互联网领域的关键基础设施之一，主要为互联网用户提供域名到IP的转换服务。随着互联网产业的迅猛发展，DNS的数据量也在持续地飞速增长，DNS已经成为当前最庞大的分布式数据系统。

为了实现数据冗余和负载均衡，权威DNS常具有多个节点。以根区为例，目前有13个域名服务器，在全球还有超过1000个镜像节点，域名数据在所有节点都有备份。节点间通过标准DNS协议进行数据同步。

这种多节点分布式部署结构和数据同步方式，一方面为系统的可用性提供了保障，另一方面也引入了数据的一致性问题。对于DNS来说，解析服务的时效性要求相对较低，分布式节点只需要满足数据的最终一致性；解析服务的正确性要求相对较高，其主要的一致性问题是拜占庭将军问题[1-3]：

拜占庭将军问题是由Lamport等人[2]在其同名论文中提出的分布式对等网络通信容错问题。由于系统异常、数据篡改或网络攻击等因素，分布式系统中的节点数据可能会出错，变成不可信节点，称为“拜占庭节点”。拜占庭节点会向其他节点发送错误的信息，破坏系统的一致性，造成恶劣影响，称为“拜占庭错误”。

DNS系统出现拜占庭错误的影响是巨大的，如2010年搜索引擎“百度”遭到攻击，DNS权威解析数据被篡改，在分布式系统中产生了拜占庭节点，造成服务器长时间无法访问，范围涉及国内绝大部分省市，影响恶劣。

本文结合DNS数据的特点，分析并借鉴现有的拜占庭容错协议，提出面向权威DNS的数据一致性保障机制，旨在解决解析数据的一致性问题，提高拜占庭容错能力。

1 相关工作

1.1 权威DNS数据管理

权威DNS系统一般基于M/S机制[4]，采取多层的主从分布式部署结构，每一层可包含多个节点，每个节点都存有完整的数据副本。该主从结构中，除最上层节点外，每个节点既是下一层节点的主域名服务器(简称“主”)，也是其上一层节点的从域名服务器(简称“辅”)。为方便系统异构，主辅节点按照标准的IXFR[5](Incremental Transfer)和AXFR(Authoritative Transfer)协议进行数据同步。

权威DNS系统结构中，一般由底层的叶子节点对外提供解析服务，其他层级的节点主要用于系统拓展和分层管理，向叶子节点提供信息传递。

1.2 相关技术及存在问题

现有的DNS体系还没有保障权威DNS解析节点(叶子节点)数据一致性的机制。当前主要通过一些安全认证机制加固权威DNS服务器，保障其数据的安全性和完整性，主流的机制为TSIG和DNSSEC。

TSIG[6]是一种事务签名机制，通过共享密钥和散列函数对DNS消息进行验证。TSIG可以解决通信信道的安全问题，但是无法解决数据存储的安全问题，对文件数据篡改没有防御效果，不能保证存储过程的数据一致性，因而也无法解决拜占庭将军问题。

DNSSEC[6]通过非对称加密方式对DNS资源记录进行数字签名，验证资源记录的完整性和真实性。然而DNSSEC机制验证范围有限，只对签名的数据做验证，如果区文件存在未签名数据则无法验证，并且DNSSEC大规模部署难度较大，目前权威DNS解析系统覆盖程度不够，实施性欠缺。

现有的DNS安全机制无法有效解决DNS的拜占庭将军问题，保障权威DNS数据的一致性。拜占庭将军问题目前主要基于区块链架构，利用支持拜占庭容错的共识协议来解决，经典的拜占庭容错协议[7-11]主要有PBFT、POW和POS，其中，POW协议是通过工作量证明来选择可发布数据的节点，而POS协议则是通过权益证明进行可信节点选择，而PBFT是针对状态机副本为主的分布式系统的算法，旨在让系统中大部分可信节点来覆盖恶意节点的行为，该协议的适用场景与现有权威DNS的部署架构较为一致。

经过上述分析，基于区块链架构的拜占庭容错协议是解决权威DNS数据一致性的一种方式。然而，区块链架构对现有的DNS体系改动成本高，性能方面可能存在欠缺。本文在不改变DNS系统架构的前提下，综合分析拜占庭容错协议与现有架构的契合程度，借鉴了分布式系统的PBFT[12]协议设计一致性保障机制。

2 权威DNS数据一致性保障机制

2.1 总体架构

本文基于自行设计的DNS数据一致性校验和，参照PBFT[13]算法，设计了适用于DNS系统结构的一致性保障流程，建立了权威DNS数据一致性保障机制，整体架构如图1所示。

图1 权威DNS数据一致性保障机制总体架构

该机制基于一致性校验和，在DNS原有的数据层增加了校验文件，以此为基础，在DNS原有的数据同步协议层，设计了主节点数据协商方案。该方案的设计借鉴了PBFT算法的状态机机制和共识流程，可以排查拜占庭节点，保障解析数据的一致性。

该机制通过数据协商完成更新数据校验，保障数据的一致性。另外，如果校验过程发现存在节点数据异常，可为异常节点重复数据同步过程，完成异常数据修正。

权威DNS数据一致性保障机制在原有的权威DNS基础上，引入了数据校验和数据源选择及修正过程。这2个过程都是基于DNS系统现有的数据持久化存储结构和主辅通信框架设计的，可与DNS系统很好地衔接。

2.2 一致性校验和

DNS权威解析数据存储在区文件和增量日志文件中。区文件记录某历史版本全量数据，增量日志文件记录之后的所有版本的增量更新事务。以区文件所有资源记录(Resource Record， RR)为基础，叠加增量更新事务的资源记录操作，可得到已记录的所有版本的权威DNS数据。分析权威DNS数据文件存储结构，其增量日志文件内容有如下特点：对同一条资源记录的增、删操作可抵消；资源记录操作满足交换律，不同批次对同一条资源记录的操作可以合并抵消；数据集合具有连续性，旧版本数据集合叠加更新事务的资源记录操作，可得到新版本数据。

为进行数据的一致性核验，根据DNS权威数据的存储特点，本文采用异或算法[14-19]计算一致性校验和。将区文件和增量日志文件中资源记录的哈希值进行异或运算生成异或码，作为解析数据的一致性和，各版本的权威DNS数据的一致性校验和根据公式(1)生成：

(1)

公式(1)中，Di表示第i个版本的权威数据一致性校验和，函数X(T)定义为对集合T所有元素进行异或运算，H(Rj1)为资源记录Rj1的哈希值，Hj为第j个版本权威DNS数据所有资源记录哈希值的集合。

根据公式(1)，一致性校验和生成算法[18]如算法1所示。

算法1一致性校验和生成算法

输入：区文件资源记录集合R1={R11,R12，…}，更新事务trans_i涉及的变更资源记录集合Ri={Ri1,Ri2，…}，本地最大版本号k

输出：所有版本的校验和集合{D1,D2，…，Dk}

1:forR1iinR1:

2: ifi==1:

3:D1=H(R1i) //R1i的哈希值H(R1i)

4: else

5:D1=D1⊕H(R1i)

6: forjin range(2,k+1):

7:Dj=Dj-1

8: foriin range(1,len(Rj)+1):

9:Dj=Dj⊕H(Rji)

基于一致性校验和算法可生成权威DNS服务已记录的各版本校验和。本文为权威DNS增加一个校验文件，用于存储和管理DNS权威服务的所有一致性校验和。利用DNS已有的数据管理结构，将校验文件以标准数据文件格式嵌入到DNS系统。校验和的这种嵌入方式有2个优点：存储的数据格式与DNS系统能有效兼容；利用DNS的查询协议可以安全便捷地获取到权威数据各个版本的一致性校验和。

2.3 一致性保障流程

基于权威DNS数据的一致性校验和，针对主辅解析数据同步更新过程，采用协商共识方案实现数据可信源选择，保障辅节点数据的一致性。数据更新过程中借鉴了PBFT算法的协商共识思想[20]，辅节点根据待更新数据生成待更新版本的校验和，并向其所有的主节点请求该版本的校验和，收集所有主的校验和对本地新的校验和进行投票协商。只有当主节点超过半数的校验和与之一致时认为待更新数据可信，否则重新选择可信数据源，完成辅节点数据更新。在协商过程中，辅与主遵循TSIG通信协议，以保障通信信道安全。整个数据更新保障流程如图2和算法2所示。

算法2数据更新保障方案

输入：辅节点为S，S最新版本号为k-1，k-1版本的校验和为Dk-1，主节点集合为M={M1,M2，…}，S收到主M2的更新记录集合Rk={Rk1,Rk2，…}

输出：S选择可信主节点Mc，获得版本k-1到k的更新数据，完成本地数据更新

1: forRkiinRk:

2:Hki=H(Rki) //Rki的哈希值Hki

3:Hk={Hk1,Hk2，…}

4:Dk=digest(Dk-1,Hk)

5: forMiinM:

7: NUM(Dk)++

10: if NUM(Dk)≥N/2:

11:Mc=M2

13:Mc=Mp

14: else

15:Mc=Mrandom//随机选择一个主

16: 向Mc请求增量更新数据，完成本地更新

图2 数据更新保障流程

解析数据更新时，如果在校验过程发现存在不可信节点，则继续向上一层主节点重复数据校验过程，修复不可信节点的数据。

3 应用场景分析

3.1 解析数据一致性分析

为方便对权威DNS系统进行数据一致性分析，以及后续的实验仿真，基于现有权威DNS体系架构，进行以下假设：

假设1DNS下发数据异常的节点为拜占庭节点，拜占庭节点的出现(即节点发生下发数据异常)为独立的小概率事件A。

假设2DNS节点最大负载能力为T。

假设3第m级为m-1级节点数量的T倍，并按照数量T分成多组，每组的m-1级节点配置T2个m级辅节点，结构示意图如图3所示。

图3 权威DNS部署结构模型

为方便对模型分析，后续所有公式中涉及的数学符号参见表1[21]的符号定义与说明。

表1 符号定义与说明

符号说明P出现单节点下发数据异常的概率Pfail叶子节点解析异常的概率N所有中间层级的节点总数Nm第m级节点数量,m=1,2,3….T权威解析节点最大负载能力M权威DNS的层级数Pmsm级单个节点下发数据异常的概率Pm(A)m级有节点下发数据异常的概率Pm(H)m级每组主节点中半数及以上的节点下发数据异常的概率

现有的DNS权威服务系统，在无DNS数据一致性校验机制的情况下，只要有一个中间节点的解析内容出错就会引起叶子节点出现数据异常，导致解析数据不一致。因此，现有系统解析数据不一致的概率为公式(2)：

Pfail=1-(1-P)N

(2)

引入本文DNS权威一致性保障机制后，系统具有容错性。对于m级的中间节点来说，有2种情况会导致下发数据异常：节点本身的原因引起下发数据异常，即事件A发生；m-1级半数及以上主节点出现下发数据异常导致本地获取的更新数据异常。一个m级中间节点出现下发数据异常的概率为公式(3)：

Pms=P+(1-P)Pm-1(H)

(3)

m级每组主集合半数及以上下发数据异常的概率为公式(4)：

(4)

当最后一级中间节点至少有一组出现半数或半数以上节点下发数据异常才会导致叶子节点出现数据异常，导致数据不一致。因此引入DNS权威一致性保障机制后，系统解析数据不一致的概率为公式(5)：

Pfail=1-(1-P(M-1)(H))NM-1/T

(5)

3.2 分析结果对比

假设，顶级节点数量为2个，由于A为小概率事件，设置P为0.001，分别设置变量T和M的取值[22-23]，据公式(3)～公式(5)得到数据一致性保障机制引入前后，解析数据不一致概率对比如图4、表2及图5、表3所示。

图4 解析数据不一致概率与T的关系

表2 解析数据不一致概率与T的关系

PfailT4T6810原系统/%0.991.391.782.17改进系统/%0.011.07e-41.12e-61.20e-8

由图4和表2分析结果可见，权威DNS级数不变的情况下，随着解析节点负载量T的增加，每一层节点数量增大，对原系统来说，系统节点数量增多，解析数据不一致概率增大。对引入一致性保障机制的改进系统来说，解析数据的校验样本增多，解析数据不一致概率减小。

图5 解析数据不一致概率与m的关系

表3 解析数据不一致概率与m的关系

Pfailm3456原系统/%1.398.2540.4495.55改进系统/%1.07e-42.40e-51.44e-48.62e-4

由图5和表3分析结果可见，权威DNS解析节点负载量不变的情况下，随着级数m的增加，对于原系统来说，随着级数的增加，系统节点数量增多，拜占庭节点发生率增大，解析数据不一致概率增大。对于改进系统来说，一方面由于每一层都有出错的概率，增大了拜占庭节点出现概率，另一方面，级数的增加也增加了对解析数据的校验次数，降低了解析数据不一致的概率。但总体来看，随着级数增加，解析数据的不一致概率呈现增大趋势。

总之，分别对级数变量m和负载量T进行分析，对比改进前后系统解析数据不一致的概率，面向DNS的数据一致性保障机制可有效降低解析数据不一致的可能性。

4 结束语

本文创新性地将PBFT共识算法的核心思想应用于权威DNS系统，并提出了适用于权威DNS的一致性校验和，为DNS系统建立了一套行之有效的解析数据一致性保障机制。解决了由于网络攻击、违规操作等引发的权威DNS拜占庭将军问题，对解析数据进行安全预判，在数据生效前进行一致性核验，排除拜占庭节点对解析数据的影响，有效降低了解析服务的安全隐患。本文加强了权威DNS解析系统数据的拜占庭容错能力，整个机制也可以与DNS系统无缝衔接，有良好的可实施性。