Page 318 - 《软件学报》2025年第5期

2218 软件学报 2025 年第 36 卷第 5 期

目标项目, 即假用户向数据收集方发送的数据包含 r 个目标项目和 k – r 个随机选择的非目标项目. 具体步骤如下.
第①步. 每个假用户初始化一个 d 比特的零向量 V.
第②步. 每个假用户将目标项目集 T 中的每个项目选中, 即集合 T 中每个项目在向量 V 中对应的比特设置
为 1.
第③步. 从非目标项目中随机选取 k – r 个项目, 将对应的比特设置为 1.
图 3 展示了 r ⩽ k 时对于子集选择机制 MGA 攻击的数据设计步骤.

初始化零向量V
将目标项目对应位设置为1

随机选取k−r位设置为1
MGA攻击伪造的向量V
图 3 子集选择机制 MGA 攻击的伪造数据示意图

r > k 时, 每个假用户从 r 个目标项目中随机选取 k 个项目, 将这 k 个项目发送给数据收集方, 即假用户
(2) 当
从 r 个目标项目中随机选取 k 个项目, 将这 k 个项目对应的比特设置为 1.
最终, 假用户向服务器发送上述方法设计的二进制向量 V, 以最大化地提高目标项目的频率估计值.

3.2 子集选择机制攻击效用

3.2.1 攻击效用评估模型
在子集选择机制中, 根据公式 (4) 可以得到目标项目 t 的频率估计值 f t ˆ , 根据公式 (14) 可以得到目标项目 t 的
ˆ ˆ
频率增加值 ∆f t . 进一步, 可以将 ∆f t 展开为:

1 ∑ n+m 1 ∑ n ∑ n+m ∑ n
˜
˜
f t,b −q f t,a −q n+m i=1 F y (t)−q n i=1 F y (t)−q F y (t) m F y (t)
i
i
ˆ
ˆ
ˆ
i
i
∆ f t = f t,b − f t,a = − = − = i=n+1 − i=1 (16)
p−q p−q p−q p−q (n+m)(p−q) n(n+m)(p−q)
其中, y i 是用户 i 发送给服务器的扰动数据. F y (t) 是计数函数, 当 y i 支持项目 t 时, F y (t) 输出 1, 否则输出 0. 子集
i i
ˆ f t 是项目 t 的真实频率, 因此, 有以下等式:
选择机制中, 项目的频率估计是无偏估计, 即 E[ f t ] = f t ,

∑ n
E[F y (t)] = n( f t (p−q)+q) (17)
i=1 i
目标项目 t 的频率增加值的期望为:

∑ n+m ∑ n
E[F y (t)] m E[F y (t)]
ˆ
E[∆f t ] = i=n+1 i − i=1 i (18)
(n+m)(p−q) n(n+m)(p−q)
公式 (18) 中的第 2 项只取决于真实用户, 为了简单起见, 将第 2 c t . 根据公式 (17) 可以得到:
项表示为常数
m( f t (p−q)+q)
c t = (19)
(n+m)(p−q)
因此, 攻击的整体效用如下:

∑ n+m ∑
E[F y (t)]
∑
ˆ
G = E[∆f t ] = i=n+1 t∈T i −c (20)
t∈T (n+m)(p−q)
∑ m( f T (p−q)+rq) ∑
其中, c = c t = , f T = f t , c 与假用户发送到数据收集方的扰动值无关. 攻击的整体效用
t∈T (n+m)(p−q) t∈T
G 取决于计数函数的期望值 E[F y (t)] .
i
3.2.2 攻击效用
mrk
结论 1. 子集选择机制 RPA 攻击整体效用为 −c .
(n+m)(p−q)d
证明: RPA 从用户数据域{1, 2,…, d}中随机选择 k 个项目, 因此, 每个项目被选中发送给数据收集方的概率是
k/d . 可以计算出计数函数的期望值, 如下所示: