AS_PATH验证算法与工程实现第4页：验证算法与工程实现

01 · 验证框架：输入、术语与前置处理

1.1 输入与核心术语

AS_PATH验证（定义于draft-ietf-sidrops-aspa-verification草案，v26，2026年7月，WG Last Call）的输入有二：BGP路由的AS_PATH（按惯例写为AS_1, AS_2, …, AS_N，AS_N为起源AS，AS_1为最接近接收路由器的AS）与全网ASPA验证数据仓（由验证器从RPKI资料库构建的"每AS一张授权提供商表"）。核心判定函数为attestation(x, y)（"授权提供商声明"判定）：

1.2 前置处理规则

• prepending去重：AS_PATH中相邻的重复ASN（合法的长度操纵技术）在验证前折叠为单一个体，避免把同一跳的重复声明误判为多跳；
• 非常规段处理：现行草案规定，AS_PATH中含AS_SET（或AS_CONFED_SET）的路径直接判Invalid——非常规段使关系验证失去意义（RFC 6472亦建议弃用AS_SET）；
• 联盟与confederation段：AS_CONFED_SEQUENCE/AS_CONFED_SET属于域内信息，不参与跨域关系验证；
• AS4重建：验证仅适用于支持4字节ASN的BGP会话；同时收到AS_PATH与AS4_PATH时，先在RFC 6793 §4.2.3重建AS_PATH后再执行验证；
• 邻居AS一致性检查：AS_PATH中最近添加的AS（透明IX场景除外）必须与BGP邻居ASN一致，否则视为Malformed并按RFC 7606 treat-as-withdraw处置——该检查可部分防御"剥离自身ASN"的泄露/操纵手法；
• 按AFI分别验证：IPv4与IPv6的AS_PATH分别套用对应的afiLimit过滤后的声明表。

02 · 三段式验证算法详解

2.1 算法直觉：合法路径的"山形"结构

在健康（无环、无隐藏关系）的客户—提供商拓扑中，一条路由从起源到接收者，其商业关系方向必然呈"上坡→（可选顶点）→下坡"的单峰结构：先沿客户→提供商链一路上行，至多到达一个拓扑顶点（该顶点可能无上游、或对顶端关系无声明），再沿提供商→客户链路一路下行。任何"先下坡又上坡"（第二上坡）都是泄露或路径操纵的结构性特征——这是整份验证算法的几何直觉。

2.2 判定步骤（概念性描述，精确算法以所锁定草案版本第6节为准）

1. 完成§01的预处理（去重、分段、按AFI选表、AS4重建、邻居AS检查）；
2. 从起源侧逐跳计算attestation值，确定上坡的两个边界——max_up_ramp（首个“Not Provider+”出现的位置，界定上坡上界）与min_up_ramp（首个“No Attestation”（Unknown）或“Not Provider+”出现的位置，界定上坡下界）；
3. 对从提供商方向收到的路由，再从接收侧对称计算下坡边界（max/min_down_ramp）；从客户或对等方向收到时，下坡边界为0；
4. 若 max_up_ramp + max_down_ramp < N（路径存在超出授权边界的跳），输出Invalid；否则若 min_up_ramp + min_down_ramp < N（路径包含Unknown段，无法完全确认），输出Unknown；否则输出Valid。

-- 概念性伪代码（教学示意，以所锁定草案版本第6节为准）
function verify_as_path(path[], aspa_db, from_direction):
    seq = reconstruct_as4_path(path)          -- RFC 6793：先合并AS4_PATH
    if empty(seq) or has_as_set(seq): return INVALID
    if last_added_as(seq) != neighbor_asn:    -- 透明IX除外
        return MALFORMED                      -- RFC 7606 treat-as-withdraw
    att[i] = attestation(seq[i], seq[i+1])    -- 从起源侧向外逐对
    max_up = N; for i: if att[i]==NOT_PROVIDER_PLUS: max_up=i; break
    min_up = N; for i: if att[i] in {NOT_PROVIDER_PLUS, NO_ATTESTATION}: min_up=i; break
    if from_direction in {customer, peer}: max_down = min_down = 0
    else: 从接收侧对称计算 max_down / min_down   -- 下坡反向授权核验
    if max_up + max_down < N: return INVALID
    if min_up + min_down < N: return UNKNOWN
    return VALID

精确语义提示：“上坡True*→顶点→下坡”是教学化形态描述；草案的精确形式化采用max/min up-ramp与down-ramp边界——Unknown同时影响min边界（使路径落回Unknown）与max边界的可达性，而明确的“Not Provider+”是触发Invalid的核心信号；下坡段按客户侧反向授权核验，合法下坡的每一跳在反向核验下同样呈Provider+。实现务必以所锁定草案版本第6节算法为准。

2.3 判定示例

注：上表为教学化示例，用于说明判定逻辑；第3、4行对照体现provider-free声明（AS0）在顶点判定中的价值——这正是草案鼓励tier-1签发provider-free ASPA的原因。边界情形（单AS路径、全Unknown路径、多声明合并等）的精确定义请直接核对所锁定草案版本的第6节。

03 · 判定结果与路由策略映射

3.1 三态结果

3.2 关键性质辨析：False≠"一定是攻击"

常见误读澄清：草案对下坡段的核验采用客户侧反向授权——合法下坡的每一跳在反向核验下同样呈Provider+（下坡段的客户在其ASPA中声明了该提供商）；“Not Provider+”出现在上坡中途（上坡尚未到顶即遇明确反证）才是Invalid的直接依据。将下坡段理解为“沿正向逐跳得到False”是阅读算法时最常见的错误，也是实现误报的重要来源。

04 · 算法演进与正确性论证

• 早期社区方案：ASPA思路于2019—2020年进入SIDR/SIDROPS讨论时，社区曾提出多种验证算法变体，在顶点处理、prepending容忍、Unknown语义、AS_SET处置等细节上存在分歧；
• 草案收敛：draft-ietf-sidrops-aspa-verification（主要作者包括Kotikalapudi Sriram等）经多轮迭代收敛为统一算法，v26（2026年7月）进入WG Last Call；
• 形式化分析：IETF第110次会议（2021年）议程收录了该验证算法正确性的形式化分析报告（IETF 110 SIDROPS议程材料，datatracker可查），从理论上论证了算法对合法路径不误判（soundness方向）与对特定操纵可检出（completeness方向）的性质；
• 出站侧验证新方向（2026）：draft-zhang-sidrops-aspa-egress提出在出站eBGP方向执行ASPA验证——在泄露扩散出本AS之前于出口就地拦截，并可辅助发现本地配置与ASPA注册错误，与入站验证及RFC 9234 OTC形成互补；
• 持续修订：顶点语义、AS_SET处理、多ASPA合并规则等细节仍随草案版本微调——工程实现必须锁定所遵循的草案版本并在升级时回归测试（第8页工具适配清单）。

05 · RTR协议扩展：从验证器到路由器

现行RTR标准RFC 8210（2017年）只定义了Prefix PDU等ROV数据分发能力。为将ASPA验证数据送达路由器，SIDROPS制定了修订草案draft-ietf-sidrops-8210bis，新增ASPAs PDU：按客户AS组织其授权提供商集合（含afiLimit）下发。路由器侧缓存该数据仓，在BGP选路/策略环节对每条路由实时执行§02的形态匹配（计算为纯查表操作，转发面无密码学负担）。

06 · 开源与厂商实现现状（截至2026年）

6.1 软件支持矩阵

6.2 性能与规模评估

• 验证器侧：ASPA对象总量极小（2025年底全球仅556个customer ASID，对象体积以KB计），验证开销相对既有RPKI验证几乎可忽略；主要新增工作是"每AS提供商表"的规范化合并与版本跟踪；
• RTR通道：ASPAs PDU数据量小、更新低频（关系声明远慢于ROA churn），带宽与时延压力远低于Prefix PDU全量同步；
• 路由器侧：每条路由的形态匹配为O(路径长度)的简单状态扫描，现代转发平台可忽略其开销；内存占用为一张"AS→提供商集合"映射表；
• 结论：ASPA的工程成本瓶颈不在计算与存储，而在关系声明的准确性与覆盖率（组织治理问题），这与BGPsec的成本结构形成鲜明对照。

本节参考来源（第4页）