基于0-1背包算法的社交网络行为隐写术

高鹏，柴鹏翔，郎俊

1 引言

隐写术［1~4］也称数据隐藏，是指利用信息嵌入算法，将秘密信息隐藏到非机密载体中的技术. 随着隐写分析技术能力的不断提高，传统隐写术的安全性不容乐观，利用社交网络行为进行信息隐藏能更好地对抗隐写分析. 社交网络的最大的传播特征是及时性与交互性，在社交网络下行为隐写的实例中，曾以Twitter 信息的长短来携带秘密信息［5］；也可以构建信息隐藏通用框架，将信息嵌入到由选定的社交网络和多个在线账户进行的一系列活动中［6］.

图1 点赞行为隐写

文献［7］提出一对一点赞行为隐写，如图1 所示.该方法将点赞矩阵H与秘密信息M进行二进制内积，并对b·D通过点赞概率p进行反算数编码得到发送矩阵G，随后发送者根据G进行点赞行为来传送信息. 接收者通过p对矩阵A进行算数编码，并对结果乘系数b-1得到B，最后根据数据重建获得M. 但在实际应用中，该方法无法满足一对多传输模式. 对于传输秘密信息中含有大量连续相同比特的情况，会产生较高的误码率，并且要求发送者和接收者有较多的共同好友，在实际应用中并不容易实现.

针对文献［7］存在的上述问题，本文提出基于0-1背包算法［8］的社交网络下一对多行为隐写. 首先通过加入CMI编码预处理，降低了误码率. 其次提出一对多行为隐写算法，通过引入0-1 背包人员分配协议，降低发送者和接收者有较多的共同好友这一限制条件，并实现了发送者对接收者操作可控.

2 基于0-1 背包算法的社交网络下一对多行为隐写

本文提出的基于0-1 背包算法的一对多行为隐写整体框架图如图2所示.

图2 基于0-1背包算法的一对多行为隐写

2.1 发送端

发送端具体流程如下：

（1）M=［m1，m2，…，ml］T表示二进制秘密信息，n表示发送者S拥有的全部好友数.H表示点赞矩阵，用来记录S给好友发表过的动态的点赞情况.

H的第i行对应S的第i个好友，H的第j列表示S对不同好友的第j个动态的点赞状态，若点了赞，则H中相应元素记录为1；若未点赞，则H中相应元素记录为0.

（2）发送者S给r1个接收者Ri（i=1，2，…，r1）传送秘密信息M. 为了避免M中含有大量连续相同比特，将M进行CMI编码［9］得到序列N.

（3）H和N进行二进制内积得到发送序列D，并根据以往发送者对每个好友的点赞概率p，对b·D经过反算术编码得到发送矩阵G. 反算数编码是一种数据解压缩的过程［10］，目的是通过概率p将0 和1 之间的小数表示成信息串. 概率p是通过对H的观察所得，其中1的概率为H对应行中1 所占的比例；0 的概率为H对应行中0所占的比例. 对D乘系数b以满足D中都为小数的条件，b的值通常取10-1或10-2.

（4）发送者按照G对其n个好友后续的动态进行点赞，若G中某元素为1，则进行点赞；若G中某元素为0，则不进行点赞.

2.2 接收端

接收端采用发送者对多个接收者进行人员分配的方案. 接收者用Ri表示（i=1，2，…，r1，r1为接收者的个数），非接收者用Nj表示（j=1，2，…，r2，r2为非接收者的个数）.Ri和Nj统称为可能接收者Pλ（λ=1，2，…，k）.k满足：

k=r1+r2（2）

接收端具体流程如下：

（1）根据人员分配协议，从Pλ（λ=1，2，…，r1+r2）中选出Ri（i=1，2，…，r1）.Ri根据点赞情况重构Gi，Gi代表S与Ri的共同好友所对应的发送矩阵. 接收端将Gi依次按行连接，去除相同的行（冗余）并用矩阵A表示.

（2）根据p对A进行算数编码，并将编码后结果乘b-1得到B. 算术编码是一种数据压缩过程［10］，目的是通过概率p将信息串表示成0 和1 之间的小数，其中p的获得与2.1 节相同.A是G的子矩阵，C是H的子矩阵. 由于G的每一行与H是相对应的，接收端通过观察H来获得与A所对应的C. 利用数据重建求解N，对N进行CMI解码得到M.

为了实现发送者对接收者状态的操作可控，人员分配协议需满足以下两个条件：接收端的状态可用数值y表示；发送者通过控制y的值，对接收端的状态进行控制.

将wλ表示Pλ的权重. 当Pλ为接收者，wλ>0；当Pλ为非接收者，wλ=0. 令

故y的值反映了可能接收者Pλ的状态. 发送者设定一个阈值a（a>y），通过改变a的值来控制Pλ的状态.a和y的关系满足：

arg min(a-y) =y（4）

现将wλ用wλ·xλ表示，其中xλ∈｛0，1｝，xλ=1 时，Pλ为接收者；xλ=0时，Pλ为非接收者. 则以上关系的数学模型为

此数学模型的文字叙述为：发送者设定阈值a来控制Pλ的状态，Pλ状态的最优解满足a与y的差值最小. 故针对一对多行为隐写的人员分配协议，可用0-1 背包算法来解决.

0-1 背包人员分配协议如图3 所示，Pλ各自拥有重量wλ和价值vλ，并且根据发送者S公布的0-1背包信息，利用动态规划法计算得知最优解时背包问题的最大价值v［k］［c］［11］. 接收端在k个Pλ中随机选出r1个Pλ，他们的价值用vkφ（φ=1，2，…，r1）表示，并判断式（6）是否成立.

图3 0-1背包人员分配协议

如果式（6）成立，则这r1个Pλ均为接收者；否则再次进行0-1背包人员分配协议过程.

2.3 算法流程

将上述发送端和接收端整合，则本文所提出的基于0-1 背包算法的一对多行为隐写技术详细流程如算法1所示.

算法1 中，发送端对应伪代码中1~4 行，接收端对应伪代码中5~16行，0-1 背包问题的求解过程对应伪代码中5~10 行，0-1 背包分配协议对应伪代码中第11 行.算法的时间及空间复杂度均为O（ck）.

3 实验结果

本文以微信中某一个用户作为发送者，使用We Chat Moment Stat 检索其朋友在Android 设备上发布的动态，选择满足条件的朋友作为接收者，以此为基础进行测试实验并分析. 实验采用酷睿4 核i5-6300HQ，8 GB 内存，NVIDIA GeForce GTX 950M GPU，操作系统为Windows 10 的设备上进行，使用MATLAB 编程语言实现.

3.1 可行性分析

我们以S的某8 位朋友作为可能接收者，将M的位数l设为16，反算数编码的位数设为8. 在传递大小为128×128 的二值图实际实验中，依次按列选取16 个像素点作为秘密信息，并选出至少与S有8 位共同好友的6 位作为可能接收者，每传递16 位秘密信息，发送者根据0-1 背包分配协议随机选取4 位接收者，2 位非接收者；在传递大小为256×256 的灰度图模拟实验中，发送端将灰度图分解为八个二值图进行遍历操作，接收端将恢复后的八个二值图合成为灰度图进行误码率分析.

3.1.1 传递二值图可行性分析

图4（a）为待传递的二值图像，图4（b）为直接传递后的结果，误码率高达49.29%，可见对于二值图中大量连续相同比特的情况，算数编码具有较大的误差. 图4（c）为加入混沌变换［12］图像处理后的结果，误码率高达52.44%，分析得知，混沌变换不能彻底解决大量连续相同比特的情况. 图4（d）为加入CMI编码图像处理后的结果，误码率为0.02%. 由此可见，本文中提出的加入CMI编码图像预处理方法误码率较低，有较好的可行性.

图4 传递二值图的可行性分析

3.1.2 传递灰度图可行性分析

图5（a）为Lena 灰度图，图5（b）至图5（i）依次为灰度图分解的八个位图，图5（j）为接收端恢复后的灰度图. 8 个位图总误码率为0.461%，灰度图误码率为3.06%. 实验结果表明，本方案有较低的误码率，并且有较好的可行性.

3.2 接收者掉线情况下可行性分析

要保证接收端正确提取秘密信息Ml×1，就要确保其他接收者收到的发送矩阵的并集不小于2l行.Ri（i=1，2，…，r1）与S的共同好友数用ni（i=1，2，…，r1）来表示.h表示Ri（i=1，2，…，r1）与S共同好友数的算术平均值：

掉线情况分析如下：

（1）当至少有1 位接收者（用Rf表示，f∈｛1，2，…，r1｝）与S的共同好友数大于或等于2l时，Rf与其他在线接收者不会受掉线接收者的影响；

（2）当Ri（i=1，2，…，r1）与S的共同好友数都小于2l时，r1个接收者中仅有s（s≤r1）个人在线的情况下，在线接收者能收到发送矩阵的并集不小于2l行的概率p1为：

本小节在数据集样本的基础上，传递4 位秘密信息，选取与S共同好友数为3 的5 位朋友作为可能接收者. 每一种情况都进行1000次测试，结果如图6所示.

实验分析如下：

对比绿色和橙色条形图可知，在线接收者的个数s并不是决定是否接收成功的关键，关键在于h与s的乘积是否大于2l. 对比黄色和橙色条形图可知，其他条件不变的情况下，h对成功率影响较大，故在实际应用可以提高h来提高传递秘密信息的成功率.

3.3 暴力攻击下的安全性分析

暴力破解攻击［13］往往针对具有有限容量的密码字典并且有破解成功提醒的加密方案，社交网络下行为隐写虽然具有有限容量的密码字典，但并没有破解成功提醒. 所以针对暴力破解攻击，本文的方案理论上是绝对安全的.

文献［14］提出了利用行为相关性检测异常点赞行为的隐写分析算法，该算法将动态按点赞的数量升序排序. 点赞数量占三分之一以下的动态数目用d1表示；点赞数量占三分之二以上的动态数目用d2表示. 将这两种类型可疑者做出的点赞数目分别用d1′和d2′表示，计算差值d=d1′/d1-d2′/d2，如果d＜0.25，则点赞行为异常，否则点赞行为正常.

图5 传递灰度图的可行性分析

图6 接收端不同种掉线情况下的可行性分析

本实验利用暴力破解攻击和文献［14］的隐写分析方法对文献［7］与本文方案在不同测试集下进行攻击破解，数据集统计如表1所示.

表1 数据集样本统计

在此数据集的条件下，暴力破解攻击结果如图7所示.

图7 安全性分析

结果显示，随着文献［7］中数据集的增大，发送者和接收者的共同好友增多，会导致暴力破解总次数变多；而0-1 背包算法下的点赞隐写由于发送者和接收者们的共同好友数并没改变，所以暴力破解字典总容量并未改变.

我们将暴力破解字典容量用t1表示，为了测试0-1背包算法对安全性的提升，对不同数据集情况下的安全性进行分析，实验结果如表2所示.

结果表明，随着h的增加，暴力破解字典容量显著增多，安全性显著提高.

3.4 假冒攻击下的安全性分析

本节利用假冒攻击［15］，对本文的安全性进行测试. 假冒攻击过程如下：非接收者获得接收者的信息并假冒成接收者，由于协议中每次选取r1个可能接收者的过程是随机的，假冒者存在一定的假冒成功的几率. 但是假冒者收到的发送矩阵是置乱的，即使假冒者假冒成功，也并不能窃取到秘密信息，所以假冒者对通信过程是破坏，而不是窃取.

表2 不同数据集下的安全性分析

由于假冒攻击与数据集样本容量无关，故不考虑数据集样本容量的影响.r3为非接收者中假冒攻击者的个数，p2为r1个接收者被成功确认的概率，p3为假冒攻击者成功破坏的概率，p4为检测出假冒者从而中断通信的概率. 对每种情况测试1000次，为了符合社交网络的随机性，每次实验都将接收者和非接收者随机排列.

每次实验只存在3 种情况：接收者被成功确认；假冒攻击者成功破坏；协议执行过程中，出现两个及以上可能接收者的背包信息相同，则假冒者一定存在，此时中断通信. 如果不满足3种情况的其中之一，则继续重复协议执行过程. 在假冒攻击者个数为2的情况下，假冒攻击者可能存在两种假冒情况：分别假冒成不同的接收者；假冒成同一个接收者. 这两种情况的统计次数分别置于表3单元格左侧和右侧.

表3 假冒攻击下的安全性测试

实验表明，假冒攻击对本文协议有很强的破坏性，假冒者个数为1 时，破坏成功率高达80%到86%；假冒者个数为2时，破坏成功率高达90%到93%.

4 结论

本文提出了基于0-1 背包算法的社交网络下行为隐写模型，协议双方由一对一变为一对多，并且接收者的状态可以由发送者控制，更加符合社交网络下随机性的特点. 通过模拟分析得知，该方案有很好的可行性；在安全性上，该方案有很好的抗解密性，但抗检测性不足，假冒攻击下的安全性不高，并且在传递秘密信息的容量上有待提升.