杜宝坤

V1

2022/07/08阅读:10主题:全栈蓝

横向联邦学习-梯度安全聚合

一 背景

最近总结自己的公众号的时候,发现一个问题:对于联邦学习的文章,基本都是在讲述纵向联邦学习,对于横向联邦学习的技术涉及较少,所以心血来潮之下,决定写几篇文章来压压箱子底。

横向联邦:现代移动设备可以访问大量适合学习模型的数据,这些数据反过来可以大大提高设备上的用户体验。例如,语言模型可以提高语音识别和文本输入,图像模型可以自动选择好的照片。然而,这些丰富的数据通常是隐私敏感的、数量很大的,或者两者兼有,这可能会阻止记录到数据中心并使用常规方法在那里进行分析训练。

所以针对于此研发人员设计了一种新的模式,即让训练数据分布在移动设备上,并通过聚集本地计算的更新来学习共享模型。我们将这种模式称为联邦学习。

横向联邦学习面临较多的挑战,大致总结如下:

  • 设备的异构性,不稳定;
  • 通信网络的异构性、不稳定、不可靠;
  • 数据的异构性,Non IID问题(云端数据与机器非私有隶属关系,可以通过Global Shuffle解决);
  • 框架的算法效率,通信的频率等;
  • 训练过程中的隐私性;

本篇文章作为介绍横向联邦学习的首作,主要讲解下横向联邦学习的模式、难点、参数的更新方式,后续文章会陆续从以下方面进行介绍;

  1. 高效的共享模型构建构建更新模式;
  2. 构建更新共享模型中的隐私安全风险以及应对手段;
  3. 横向联邦学习的前沿技术;

二 横向联邦学习的安全问题

在上一篇文章中,我们介绍了横向联邦学习的两种模型更新的方式:

  • FedSGD
  • FedAVG

上面介绍的两个算法,所有的梯度、参数等都是通过明文的形式传递的,所以存在泄露问题,下面我们就介绍下梯度泄露;

梯度会泄露用户的个人信息,在NeurIPS 2019中,《Deep Leakage from Gradients》一文指出,从梯度可以推断出原始的训练数据,包括图像和文本数据。

其中报道了一个用20行基于PyTorch核心代码的样例,运用GAN的思想,让分布式训练中的一个攻击方可以从整个模型更新梯度的过程中,通过减少梯度差异的方式,不断生成与其他参与各方相同的数据,从而实现『偷取』数据。

  • Deep Leakage by Gradient Matching
  • 其核心算法是匹配虚拟数据和真实数据之间的梯度。在PyTorch中,不到20行就可以实现它!
def deep_leakage_from_gradients(model, origin_grad)
  dummy_data 
= torch.randn(origin_data.size())
  dummy_label =  torch.randn(dummy_label.size())
  optimizer = torch.optim.LBFGS([dummy_data, dummy_label] )

  for iters in range(300):
    def closure():
      optimizer.zero_grad()
      dummy_pred = model(dummy_data) 
      dummy_loss = criterion(dummy_pred, dummy_label) 
      dummy_grad = grad(dummy_loss, model.parameters(), create_graph=True)

      grad_diff = sum(((dummy_grad - origin_grad) ** 2).sum() \
        for dummy_g, origin_g in zip(dummy_grad, origin_grad))
      
      grad_diff.backward()
      return grad_diff
    
    optimizer.step(closure)
    
  return  dummy_data, dummy_label
  • 在视觉图片上的实验效果
  • 在语言模型上的实验效果

三 前置知识

但是其实早在2017年,谷歌的Bonawitz等发表了《Practical Secure Aggregation for Privacy-Preserving Machine Learning》这篇文章,详细阐述了针对梯度泄露攻击设计的Secure Aggregation协议,我们简称为SMPC.

  • 前置知识

秘密分享:可以参考我专栏里面的文章,隐私计算基础组件系列-秘密分享

DH密钥交换:可以参考我专栏里面的文章,隐私计算加密技术基础系列-Diffie–Hellman key exchange

下面我们再简单分享下秘密分享和DH秘钥交换,这里只做简单的介绍,如果有需要详细了解这两个知识点内容的同学,请移步到上面的链接。

1 简单介绍下秘密分享

下面简单介绍下秘密分享,有想全面了解的,请移步 隐私计算基础组件系列-秘密分享

主要是介绍阈值秘密分享,阈值秘密分享的基本思路是,基于秘密分享的便携性与安全性的考量,如果有个n个秘密分片,我们只需要凑齐 k( 1 < K <n )个人,他们手中的信息拼凑起来,就可以获取秘密。

那么如何才能做到这点呢?有以下几个问题需要考虑;

  • 随机性:挑选的k个人,需要是随机挑选的k个人,不能是一个固定的选取。
  • 必然性:随机选出的这k个人,必须能需要的数字进行解密。

那么,是什么样的技术可以实现呢?

大家还记得学习《线性代数》的时候吧,在线性代数的课上,k个参与者,相当于k个变量,那么需要k个方程就才可以解出来。

计算逻辑

秘密数字:D;

参与方:n个参与者,

一个大的素数:p,约束这个素数要大于D和n

  • 首先,构造出n个方程式,构造公式 ,这个公式是从文章How to Share a Secret里面分析的,说白了就是多项式,列举如下:

    • 公式展开:

      ,其中

    • 公式举例(假设k为3,n为10)

      a_0 = D$;

      a_0 = D$;

      ......

      a_0 = D$;

  • 然后,目前的方程组里面,还有 的(k-1)个变量,那么这几个变量如何获取呢?根据Adi Shamir在ACM发布的《How to Share a Secret 》的描述, The coefficients in q(x) are randomly chosen from a uniform distribution over the integers in [0, p), 也就是说在[0,p)的范围内均匀分布中进行获取。

  • 然后,原始文章中也对 进行了约束是大素数的取模,不过这理解这个大素数的p的作用更多是控制我们选择 的大小的,防止数据的过于膨胀;(唯一解的问题,在构造的时候基本可以规避,大家可以自行证明,提示一下:系数行列式不等于零);

  • 最后,将这个n个方程划分给n个参与者。需要计算的时候,只需要将k个方程获取进行联合计算就可以计算出a也就是秘密D。

案例介绍

下面通过一个案例,介绍下基于多项式的阈值秘密分享。

  • 输入

    • 秘密数字:D = 88
    • 参与方:10个,
    • 大素数:991
    • 解密阈值:3
  • 加密逻辑

    • 首先,生成方程组

      ,其中

      ,其中

      ......

      ,其中

    • 然后,基于素数生成 的值,设定 ,则方程组如下,并且

      ,其中

      ,其中 $;

      ......

      ,其中

    • 然后,可见 都小于我们设置的素数991,符合预设,所以将这10个方程分布分发到10个参与者分片Server。

  • 解密逻辑

    • 首先,假设抽取参与者1,2, 10的方程组成方程组进行解密,则方程组如下:

    • 最后,求解这个方程组,则 ,则解出秘密D。

2 简单介绍下DH秘钥交换

下面先简单介绍下DH秘钥交换,有想全面了解的,请移步 隐私计算加密技术基础系列-Diffie–Hellman key exchange

最简单,最早提出的这个协议使用一个质数p整数模n乘法群以及其原根g。下面展示这个算法,绿色表示非秘密信息,红色粗体表示秘密信息:

由上面的流程可以看到,Alice和Bob最终都得到了同样的值,因为在模p的情况下 相等。注意 是秘密的。

三 横向联邦学习的参数更新机制

2.2 安全聚合算法 简介

但是其实早在2017年,谷歌的Bonawitz等发表了《Practical Secure Aggregation for Privacy-Preserving Machine Learning》这篇文章,详细阐述了针对梯度泄露攻击设计的Secure Aggregation协议。

3.2 First Attempt: Masking with One-Time Pads

安全地聚合用户数据向量的第一次尝试涉及到每对用户u,v,用户u < v同意一个秘密的总顺序,这个秘密被记为su,v。每个用户用他们与所有其他用户构建的秘密蒙蔽了他们的输入值xu。如果u将su,v加到xu上,v从xv中减去它,那么当它们的向量相加时,掩码就会被取消,但它们的实际输入不会显示出来。形式上,每个用户的盲值是

P是一个公共的大的素数。

整体流程如下:

上面的方案是存在问题的,假设用户2在上传 的时候掉线了,没有把 发送给服务器,那么这一轮全局更新中,服务端的聚合值 是没有意义的。

3.3 Second Attempt: Masking with One-Time Pads with Recovery

上面的方案,在有用户掉线的时候,存在聚合时效的情况。所以考虑恢复方案,比如用户2掉线的时候,进行恢复阶段的处理,对于用户2的添加的扰动值 来说,用户1和用户3是知道的,所以服务器只要询问用户1和用户3,获取相应的扰动值,就可以剔除影响,完成聚合。

  • 问题
    • 在回复秘密之前,其他用户可能会在恢复阶段退出,这将需要一个额外的恢复阶段来报告新删除的用户的秘密,所以这个方案的要求比较严格,考虑一个较为松散的方案替换。
    • 延迟的通信可能会导致服务器认为某个用户被删除了,从而可以从所有其他用户那里恢复他们的机密。但是如果是网络延迟,将导致服务器能够在收到用户的秘密后解密他们的个人信息。

3.4 Final Attempt: Double-Masking

针对上面存在的问题,采用双掩码机制,即使用两个随机数,并且加入秘密分享的机制。

  • 为用户u引入另外一个随机数 。所有的 均使用秘密分享的方式分享给其他用户,在恢复阶段,至少t个用户才能恢复一个秘密。
  • 在聚合阶段
    • 如果用户u掉线,只聚合第一个分享的随机数 ;
    • 如果用户u不掉线,则聚合两个随机数 ;\

整体流程如下,由于这个整体流程较为复杂,所以本问仅仅进行大体介绍,后续会另开一篇文章进行详细的介绍。

四 参考资料

  • Deep Leakage from Gradients
  • Secure Analytics: Federated Learning and Secure Aggregation
  • Federated Learning of Deep Networks using Model Averaging
  • Practical Secure Aggregation for Privacy-Preserving Machine Learning

五 番外篇

个人介绍:杜宝坤,隐私计算行业从业者,从0到1带领团队构建了京东的联邦学习解决方案9N-FL,同时主导了联邦学习框架与联邦开门红业务。 框架层面:实现了电商营销领域支持超大规模的工业化联邦学习解决方案,支持超大规模样本PSI隐私对齐、安全的树模型与神经网络模型等众多模型支持。 业务层面:实现了业务侧的开门红业务落地,开创了新的业务增长点,产生了显著的业务经济效益。 个人比较喜欢学习新东西,乐于钻研技术。基于从全链路思考与决策技术规划的考量,研究的领域比较多,从工程架构、大数据到机器学习算法与算法框架均有涉及。欢迎喜欢技术的同学和我交流,邮箱:baokun06@163.com

六 公众号导读

自己撰写博客已经很长一段时间了,由于个人涉猎的技术领域比较多,所以对高并发与高性能、分布式、传统机器学习算法与框架、深度学习算法与框架、密码安全、隐私计算、联邦学习、大数据等都有涉及。主导过多个大项目包括零售的联邦学习,社区做过多次分享,另外自己坚持写原创博客,多篇文章有过万的阅读。公众号秃顶的码农大家可以按照话题进行连续阅读,里面的章节我都做过按照学习路线的排序,话题就是公众号里面下面的标红的这个,大家点击去就可以看本话题下的多篇文章了,比如下图(话题分为:一、隐私计算 二、联邦学习 三、机器学习框架 四、机器学习算法 五、高性能计算 六、广告算法 七、程序人生),知乎号同理关注专利即可。

一切有为法,如梦幻泡影,如露亦如电,应作如是观。

分类:

后端

标签:

后端

作者介绍

杜宝坤
V1