引用
Acharya J, Sun Z, Zhang H. Robust Testing and Estimation under Manipulation Attacks[C]//International Conference on Machine Learning. PMLR, 2021: 43-53.
摘要
本文主要研究了强污染模型中离散分布的鲁棒测试和估计，本文同时考虑“中心化设置”及“带信息约束的分布式设置”，其中，信息约束包括通信约束和局部差分隐私约束。该技术将操纵攻击强度与来自用户的信息之间的以汉明距离作为指标的 EMD 距离联系起来。在中心化环境下，本文为学习和测试两个环节都提供了最优误差界，而其在局部信息约束下的下界基于最新的应用于分布式推理的下界方法。在通信环境约束下，本文开发了基于随机哈希和 L1/L1 等距的新算法。
引言
来自用户的数据构成了现代分布式学习系统例如联合学习的骨架。此类大型分布式系统存在两个使其推理任务变得具有挑战的两个关键因素：1）用户端具有信息约束；2）存在可以完全控制 γ 部分用户的 γ-操纵攻击。
本文基于现有研究，进一步研究了在有信息约束和无信息约束的条件下针对对于离散分布的推理的操纵攻击。这种场景下，两大挑战同时存在，但同时也普遍，更具实践意义。
图 1 带信息约束和操纵攻击的分布式模型示意图
问题设置
图 1 展示了带信息约束和操纵攻击的分布式模型，其中，x1 至 xn 为 n 个采自某个数据分散在 n 个用户处的未知分布 p 的样本，经过信息约束 W1 至 Wn 的处理后形成消息 y1 至 yn。而 yi 经过 γ-操纵攻击，其中小于等于 γn 个消息被攻击并篡改，成为 yi’。中心服务器最终接收到 yi’与其他未改变的 yi 共同形成的数据 Zi 并试图通过这批数据对分布 p 进行推理。
本文的贡献主要如下：1）确定了对抗攻击对基于调制信号数据集的白盒及黑盒模型的效果，并验证了对抗攻击在信号序列数据集上的有效性。2）在保证对抗攻击的隐蔽性和有效性的前提下，确定了最优的扰动水平。3）发现信号置信度与攻击成功率成反比，并获得了多组具有高鲁棒性的信号。
通信协议
本文使用公共-硬币的非交互式协议，所有用户都能获取公共的随机项 U，且 U 独立于 X。每个用户 i 选择一条通道 Wi，并对原数据进行映射变换，因此，对于输入分布 p 和被选通道 Wi，形成的消息分布如下所示：
图 2 Wi 下的 Yi 分布表达式
于是，将 Wi 泛化至所有的 W 分布，可以进一步得到消息 Yi 的分布如下：
图 3 Yi 分布表达式
信息约束
本文考虑两种信息约束，分别是 LDP（局部差分隐私）约束和通信约束。两者定义分别如下：
图 4 LDP 约束定义
图 5 通信约束定义
推理任务
本文考虑分布估计（学习）和拟合优度（测试）的基本任务。其中，DL（分布学习）的目标是设计消息方案并且对依赖的分布 p 进行估计，损失通过估计和实际分布的总偏差距离衡量。本文希望通过为最坏分布设计最优消息方案及估计以描述操纵攻击下的最大损失（风险）的最小值：
图 6 DL 的损失描述
另一个任务 IT（身份测试），目的是在给定消息方案的情况下识别 γ-操纵攻击，其最小化最大风险定义如下：
图 7 IT 的损失描述
主要贡献
1. 基于操纵攻击可以改变 n 份消息中的 γ 部分，本文使用基于汉明距离的 EMD 距离描述了在这种攻击下进行学习和测试的困难程度。
2. 在没有信息约束的情况下，本文给出了分布学习的最大风险的最小值并证明了其完备性。同时，本文在测试这一更为复杂的场景下也给出了最大风险的最小值，上述两个风险的表达式如下图所示：
图 8 两种场景下的最大风险最小值
3. 在信息约束和攻击同时存在的情况下，本文同样提供了估计及测试的一般下界。该结果建立在最近开发的分布式推理框架的基础上，并根据信道信息矩阵的跟踪范数限制消息之间的 EMD 距离。通信约束下，本文基于随机哈希提出了一种协议以匹配该情况下的下界，同时发现操纵攻击在信息约束下效果更加显著。该环境下，本文还基于 L1/L1 等距提出了一种鲁棒测试的算法，结果显示后续还需为研究通信约束是如何限制 EMD 并缩小约束及非约束场景下的差距做出更多工作和努力。隐私约束下，本文为估计和测试场景都提出了一种匹配现有研究中上界的下界。现有的比本文的下界更低的下界基于一种更弱的威胁模型，因此与本文结果不具有直接可比性。本文的所有风险上下界总结如下：
图 9 本文所有场景的风险上下界总表
操纵攻击强度建模
本文使用 EMD 对操纵攻击的强度进行建模，基于汉明距离的 EMD 距离定义如下：
图 10 基于汉明距离的 EMD 距离
基于该定义，如果 Q1 和 Q2 是 yn 域中长度为 n 的消息的分布，且 EMD 距离不超过 cγn，则对于某个常数 c，操纵攻击能够将 Q1 假扮为 Q2。定理 1 描述了该内容，该定理的关键点在于从一个输入分布的混合中考虑消息分布。其中，α 是指概率分布域中的某个指定分布到另一个域的有限子集内的所有元素的总偏差距离的最小值。
图 11 定理 1
鲁棒身份测试和学习
在无信息约束的情况下，本文提出如下定理，并从而得到推论如下：
图 12 公理 2 及其推论
定理 2 的第一项是隐含在样本复杂度界中的统计比率，定理 2 隐含了当 γ 远大于 1/sqrt(n)和 1/sqrt(k)的偏小值，操纵攻击带来的风险会显著大于统计风险。上界基于 L1 检验，下界则基于 EMD 距离得到证明。推论上界由经验分布得到，第一项是除去攻击的基本风险，而第二项则来自定理 2 中的第二项且包含测试到学习的简化。
测试上界
对于上界的处理，本文通过两个阶段进行。本文首先将身份测试约简为均匀性测试，然后为均匀性测试提供了一种算法。首先，通过如下引理，本文将身份测试约简为均匀性测试，接着，作者使用多个引理，经过多次推导，最终得到基于均匀性测试的算法如图 14。其中，值得注意的是，该证明表明，对于任何常数失效概率 β，鲁棒身份测试的风险与定理 2 中的风险同不大于一个常数因子，这在后续的误差提升考虑中会十分重要。
图 13 用于由身份测试向均匀测试约简的引理
图 14 基于均匀测试的测试算法
下界
本文关于下界使用如下引理，并通过将中心化场景改变为分布式场景，即通过将 EMD 设置为 γn/2 并处理 α，最终得到结论。
图 15 用于计算下界的引理
鲁棒约束推断
本章阐述了本文关于通信和 LDP 约束下的相关结论。首先，在通信约束下，本文对于分布学习及身份测试的风险界的结论如图 16 和图 17 所示。其中，定理 8 第一项表示通信约束下无攻击的风险，而第二项则表明 l < logk 时，操纵攻击使得风险增加的量与无约束环境下多了因子 sqrt(k/2^l)。对于定理 9，其第一项均表示无信息约束下的风险，同样地，操纵攻击下的风险项相比无约束情况下以上述因子增长。本文认为，两者的上界已经属于较紧的边界，而下界的进一步逼近则是未来一个很有趣的可能工作方向。最后，LDP 约束下，本文分别为 DL 和 IT 场景建立下界如图 18 所示。值得注意的是，现有研究已经表明了本场景下的上界及下界，本文认可该研究得出的上界结论，但对其下界结论进行了扩展和补充，因为本文基于一个更强的威胁模型，因此虽然该研究得出的下界更小，但与本文结论并不存在直接可比性。
图 16 通信约束下分布学习的风险界
图 17 通信约束下身份测试的风险界
图 18 LDP 约束下学习和身份测试的风险下界
另外，针对通信约束下的 DL 和 IT 场景，本文分别提出协议描述与估计量、身份测试方案如图 19 和图 20 所示。
图 19 通信约束下 DL 协议描述与估计量
图 20 通信约束下 IT 测试方案
总结与展望
本文列举了现有分布式学习系统在操纵攻击和通信约束、LDP 约束下的风险上下界，进行了完整证明，并提出了一系列 DL 的估计方法或 IT 测试方法。其中，部分边界已较为紧逼，而部分边界则仍然较松，这是本文后续的可能工作方向。
致谢
本文由南京大学软件学院 2021 级硕士研究生顾明政翻译转述。