间隔认证新突破：将MLP对抗鲁棒性问题转化为格遍历问题
对抗鲁棒性是AI安全的核心问题之一，但现有方法往往只能提供“局部”保证。近日，一篇来自arXiv的论文（编号2607.08773）提出了一种全新的理论框架，将多层感知机（MLP）的对抗鲁棒性问题转化为格遍历问题，并首次系统定义了“完备认证”概念，为可验证AI安全性开辟了新路径。
问题背景：从“声音”到“完备”
传统对抗鲁棒性研究关注的是：给定一个输入点 x，能否找到一个尽可能大的区间（即轴对齐超矩形），使得 x 在该区间内任意扰动都不会改变MLP的分类结果？这类区间被称为声音认证（Sound Certification）。然而，论文作者指出，这种认证只回答了“哪里安全”，却没有回答“哪里不安全”。
为此，他们引入了完备认证（Complete Certification）的概念：一个区间 I 是完备认证，当且仅当 x ∈ I，且一旦 x 移出 I，MLP的预测必定改变。换句话说，完备认证精确刻画了分类决策的“边界”。
核心方法：格遍历与“细化-验证”迭代
论文的核心洞察在于：所有可能的候选区间构成一个格（Lattice），每个格元素对应一个区间。对抗鲁棒性问题因此等价于在这个格上寻找满足特定性质的元素。
作者设计了专用的格遍历算子，并采用“细化-验证”（Refine & Verify）迭代方案：
- 在每一轮，算法生成一个候选区间；
- 利用形式化MLP验证器（如基于SMT或MILP的求解器）检查该区间是否满足声音或完备条件；
- 若满足，则尝试扩大（声音）或缩小（完备）区间，继续遍历；
- 直到找到最大声音区间或最小区间。
该方案保证了声音最大性（即找到的区间是最大的声音区间）和完备最小性（即找到的区间是最小的完备区间）。
不对称性：优化问题的复杂度差异
论文进一步研究了优化问题，发现了有趣的不对称性：
- 对于完备认证，最小解可以在多项式次oracle调用内求得；
- 对于声音认证，问题被证明是强难解的（strongly intractable）。
这一结果揭示了两种认证在计算本质上的差异：寻找“安全边界”比寻找“分类边界”更难。
此外，对于对称区间（即 ℓ∞-球），作者给出了对数复杂度的算法，显著提升了效率。
实验验证：ParallelepipedoNN系统
作者实现了名为 ParallelepipedoNN 的系统，并在多个标准MLP模型上进行了评估。实验表明，该方法能够有效生成最大声音区间和最小完备区间，且计算开销在可接受范围内。
意义与展望
这项工作的意义在于：
- 理论统一：将对抗鲁棒性纳入格论的框架，为后续研究提供了数学基础。
- 完备认证首次定义：补全了AI安全性验证的“另一半”，使认证不仅告诉用户“哪里安全”，更明确“哪里不安全”。
- 复杂度分类：清晰划定了不同认证问题的计算边界，指导实际算法设计。
未来，该框架有望扩展到卷积神经网络、Transformer等更复杂的架构，并与其他形式化验证方法结合，推动可验证AI从理论走向工程应用。