DNS 作为互联网最古老的分布式协议之一，其内部特性相互作用产生的理论复杂度远超直觉。加州大学与微软研究人员在 HotNets 2021 论文中证明：借助 DNAME 记录类型，DNS 能够识别任意正则语言、生成任意上下文无关语言字符串，分别等价于确定性有限自动机（DFA）与下推系统（PDS）。这一结论揭示了协议扩展叠加带来的隐性计算能力，也为验证成本评估与攻击面分析提供了形式化依据。
DNAME 重写机制构造 DFA 模拟
DNAME 与 CNAME 的关键差异在于部分重写：它可将整个子树重定向到另一域名，保留原标签结构。研究者利用这一特性，在单个区域文件中编码 DFA 的全部状态转移。解析器将待测字符串编码为查询域名发送至权威服务器，服务器通过 DNAME 链式重写模拟状态跃迁，最终在 TXT 记录中返回 "accept" 当且仅当字符串属于该正则语言。原文未给出具体区域文件规模或查询延迟数据，但机制上不依赖递归解析深度，而是在单次权威响应内完成计算。
下推系统模拟实现上下文无关生成
进一步扩展中，研究者展示 DNS 可模拟下推系统，从而生成任意上下文无关文法的字符串。利用 DNAME 的递归重写能力配合通配符与 CNAME，可在域名空间中构造栈操作：每次重写对应一次栈压入或弹出，域名标签序列即为推导过程的中间形态。该构造表明 DNS 查询过程本质上可执行图灵完备的子集计算，原文未给出具体文法规模上限，但理论上不受区域文件条目数硬性限制。
工程启示：验证边界与访问控制新范式
对运维与网络工程师而言，这项研究划定了 DNS 行为分析的理论边界：区域文件不再是静态映射表，而是可执行的逻辑程序。基于 DFA 模拟的域名白名单已可落地——将允许域名集合写成正则表达式，编码进区域文件，解析器一次查询即可完成合规性判断，适用于企业准入控制或家长过滤场景。但同时也意味着，任意 DNAME 链的引入可能隐性引入计算复杂度，验证工具需覆盖重写逻辑而非仅检查记录语法。
原文: APNIC Blog（2022-03-11）｜编译自 APNIC Blog，事实以原文为准。
来源：APNIC Blog