域名抢注与拼写错误检测

01 · 生成问题的形式化建模

设目标域名为字符串 s（如 example，不含 TLD），字符集 Σ（常见配置为 a–z 与 0–9，36 字符）。变体生成的本质是：在 s 的邻域（neighborhood）内按编辑操作搜索候选集合 G(s)。形式化定义如下：

• 单编辑邻域（Order-1）：对 s 施加一次删除、插入、替换或相邻转置操作所得全部字符串的集合，即 Damerau-Levenshtein 距离 ≤1 的字符串集合。其规模上界约为：删除 n 个 + 重复（视为特殊插入）n 个 + 转置 (n−1) 个 + 插入 36n 个 + 替换 35n 个（n 为字符串长度，36 字符集下替换有 35 种选择）。
• Order-2 邻域：两次编辑操作的复合空间。规模近似为 Order-1 的平方量级，仅在品牌保护的高价值场景中局部启用（如针对支付类品牌的双字符错误）。
• 结构化邻域：不属于编辑距离框架的操作——子域化、连字符插入、前后缀词缀组合（combosquatting）、TLD 替换与同形字符替换。这些操作由独立生成器（generator）实现，与编辑类生成器输出做并集去重。

1.1 候选质量控制原则

• 不可读性过滤：连续元音超过 3 个、键盘两侧远距离字符组合（如 qza）等低概率候选直接丢弃。
• 可发音性先验：发音算法（见 §04）得分过低且无关键词语义的候选降权。
• 去重与规范化：所有候选先经 IDNA 2008 规范化（RFC 5890-5894 的 NFC/NFKC 与 STD3 规则）后比较，避免 Punycode 形态差异造成重复解析。

02 · 编辑距离族算法

2.1 Levenshtein 距离与 Damerau-Levenshtein 距离

工程实现可复用成熟库：Python 生态的 python-Levenshtein（C 实现）或 rapidfuzz（向量化、支持多进程），短字符串距离计算可达每秒百万级，千级品牌×数千候选的相似度排序不构成性能瓶颈。

Levenshtein 距离定义两字符串间最少的单字符编辑（插入、删除、替换）次数，是变体相似度度量的基线。Damerau-Levenshtein 距离额外计入相邻转置操作，与人类"敲反两个字母"的错误模式直接对应——因此变体生成应以 Damerau 变体为基准：它恰好覆盖"删除/插入/替换/转置"四类自然拼写错误。

function damerau_levenshtein(a, b):
    # 经典动态规划实现，O(|a|×|b|) 时间/空间
    # d[i][j] = a[0:i] 与 b[0:j] 的 Damerau-Levenshtein 距离
    # 递推含四种操作代价 + 相邻转置的特判（i,j>1 且 a[i]==b[j-1] 且 a[i-1]==b[j]）

2.2 归一化与阈值设定

原始编辑距离随域名长度增长而放大，工程上采用归一化形式：

similarity(s, g) = 1 − dist(s, g) / max(|s|, |g|)
# 经验阈值：归一化相似度 ≥ 0.80 视为高置信变体；
# 0.65–0.80 进入人工复核队列；< 0.65 通常为用户创造力范畴，仅保留结构化生成器（combosquatting 等）输出

阈值基线来源于学术研究的测量结论：真实人类拼写错误中，绝大多数为单字符错误（Damerau 1964 年对打字错误的经典统计——约 80% 以上为单错误类型），这正是 Order-1 邻域覆盖率极高的原因；双错误候选数量指数增长但命中率递减，故作为低优先级层。

2.3 与其他字符串度量的分工

03 · 键盘邻接加权

替换类错误中，"敲到隔壁键"占人类输入错误的最大比例。键盘距离模型将 QWERTY 布局编码为坐标网格，为每对字符赋予物理距离 d_k(c₁, c₂)，替换代价按距离衰减函数取值：

# 代价函数示例（工程可调）
cost_replace(c1, c2) = 1.0                    # 随机替换
cost_replace(c1, c2) = 0.3  if 相邻键(d_k ≤ 1)
cost_replace(c1, c2) = 0.6  if 同一手同排(d_k ≤ 2)
# 效果：邻居键替换（如 x→z、n→b）保留更多候选进入高优先级队列

• 同指法邻近键全集：除水平相邻外，同列上下键（如 e→d→c 斜向）也属于高频误敲区，建表时以每键 6–8 个邻近键为宜。
• 数字行与符号：1/l/i、0/o、5/s 等跨行混淆需显式加入混淆对表（见 §05）。
• 移动端扩展：触屏输入的误触模式与物理键盘不同（邻近热区更大、自动纠错介入），键盘距离表应提供移动端权重变体——这也是本课题区分"桌面变体"与"移动变体"两条生成管线的原因。

实证支撑（fat-finger distance）：Moore 与 Edelman（FC 2010）将上述思想形式化为"胖手指距离"（fat-finger distance）——仅允许使用 QWERTY 键盘相邻字符完成插入/删除/替换/转置的最少操作次数。其抽样人工核验表明：编辑距离 1 的候选几乎全部被确认为拼写错误域名；距离 2 时"纯编辑距离"候选误报明显增多，而 fat-finger 距离 2 的候选仍大概率是真变体。该结论直接支持本课题把"键盘加权距离 ≤1"设为高优先级扫描层、距离 2 仅对高价值品牌局部启用。

04 · 发音相似算法

部分拼写错误源于"按发音记错"（如 exampel）。Soundex（1918 年起用于美国人口普查）与 Metaphone / Double Metaphone（Philips, 1990/2000）将字符串编码为发音指纹，指纹相同即视为同音候选。工程用法：

• 对目标域名计算发音指纹，再枚举"指纹相同或相近"的拼写形式（可结合常见拼读错误规则表，如 -le 结尾误作 -el）。
• 发音生成器输出量小（每域名通常 <20 个候选）但命中率不可忽视，Moore & Edelman 2010 的测量即包含此类错误模式。
• 中文场景边界：拼音域名的混淆模式（如 zhifubao vs zfb 缩写、前后鼻音 ang/an、平翘舌 z/zh）无现成发音算法可用，本课题采用规则表+拼音音节库方式处理（见第4页 §07）。

05 · 视觉混淆字符表（Homoglyph / IDN）

同形字符攻击用视觉上不可区分的外文字符替换域名中的 ASCII 字符，经 Punycode（RFC 3492）编码注册。典型混淆对：

5.1 检测方法

• Unicode 规范化比对：候选域名经 NFKC 规范化后与品牌名比对，规范化后相等即命中同形攻击（Unicode UTS #39 定义了"混淆检测"的完整机制，包括 Skeleton 算法）。
• 全量混淆对枚举：对品牌名每个字符，从混淆对表中替换生成候选（k 个混淆位 × 每位置 2–4 个混淆字符）。
• 浏览器呈现层差异：浏览器对 Punycode 域名的显示策略不同（如 Firefox 地址栏默认对非当前语言字符的 Punycode 域名显示 xn-- 原形，而部分浏览器/历史版本曾直接显示 Unicode 形态），2017 年 Xudong Zheng 构造的 apple.com 西里尔同形域名 PoC 即利用了这一差异——检测系统应以"跨浏览器一致呈现为 Unicode"作为高危判据之一。

06 · 生成策略工程实现与候选空间估算

综合主流开源工具的工程实践，本课题的生成引擎按以下生成器组合实现（与 dnstwist 的策略集对应）：

注：上表量级为算法决定的可复算理论值（随字符集、词典规模、裁剪策略变化），非实测统计，供容量规划参考。

6.1 工具实现对照

注：dnstwist 仓库地址 github.com/elceef/dnstwist；URLCrazy 仓库地址 github.com/urbanadventurer/urlcrazy，具体策略以各仓库文档为准。

07 · 生成引擎的完备性评估

生成引擎是否"够全"，须以真实错误分布为标尺。评估方法：

• 错误语料回放：收集真实误输入样本（公开的拼写错误语料、企业 DNS 日志中的 NXDOMAIN 聚合、输入法纠错数据），计算回放命中率：真实错误落在生成候选集合中的比例。目标：Order-1 覆盖 ≥95%（依据：单字符错误占人类拼写错误绝对多数）。
• 反向校验（负召回）：抽样生成候选做人工标注，估计"生成但未注册"候选中将来被注册的比例，用于校准优先级排序的有效性。
• 版本化基线：生成策略集、字符集、词典全部版本化管理；每次变更以固定品牌集回放对比，保证引擎演进可回溯。

本节参考来源（第2页）