基于0-1背包算法的社交網(wǎng)絡(luò)行為隱寫術(shù)

高鵬，柴鵬翔，郎俊

1 引言

隱寫術(shù)［1~4］也稱數(shù)據(jù)隱藏，是指利用信息嵌入算法，將秘密信息隱藏到非機(jī)密載體中的技術(shù). 隨著隱寫分析技術(shù)能力的不斷提高，傳統(tǒng)隱寫術(shù)的安全性不容樂觀，利用社交網(wǎng)絡(luò)行為進(jìn)行信息隱藏能更好地對抗隱寫分析. 社交網(wǎng)絡(luò)的最大的傳播特征是及時(shí)性與交互性，在社交網(wǎng)絡(luò)下行為隱寫的實(shí)例中，曾以Twitter 信息的長短來攜帶秘密信息［5］；也可以構(gòu)建信息隱藏通用框架，將信息嵌入到由選定的社交網(wǎng)絡(luò)和多個(gè)在線賬戶進(jìn)行的一系列活動中［6］.

圖1 點(diǎn)贊行為隱寫

文獻(xiàn)［7］提出一對一點(diǎn)贊行為隱寫，如圖1 所示.該方法將點(diǎn)贊矩陣H與秘密信息M進(jìn)行二進(jìn)制內(nèi)積，并對b·D通過點(diǎn)贊概率p進(jìn)行反算數(shù)編碼得到發(fā)送矩陣G，隨后發(fā)送者根據(jù)G進(jìn)行點(diǎn)贊行為來傳送信息. 接收者通過p對矩陣A進(jìn)行算數(shù)編碼，并對結(jié)果乘系數(shù)b-1得到B，最后根據(jù)數(shù)據(jù)重建獲得M. 但在實(shí)際應(yīng)用中，該方法無法滿足一對多傳輸模式. 對于傳輸秘密信息中含有大量連續(xù)相同比特的情況，會產(chǎn)生較高的誤碼率，并且要求發(fā)送者和接收者有較多的共同好友，在實(shí)際應(yīng)用中并不容易實(shí)現(xiàn).

針對文獻(xiàn)［7］存在的上述問題，本文提出基于0-1背包算法［8］的社交網(wǎng)絡(luò)下一對多行為隱寫. 首先通過加入CMI編碼預(yù)處理，降低了誤碼率. 其次提出一對多行為隱寫算法，通過引入0-1 背包人員分配協(xié)議，降低發(fā)送者和接收者有較多的共同好友這一限制條件，并實(shí)現(xiàn)了發(fā)送者對接收者操作可控.

2 基于0-1 背包算法的社交網(wǎng)絡(luò)下一對多行為隱寫

本文提出的基于0-1 背包算法的一對多行為隱寫整體框架圖如圖2所示.

圖2 基于0-1背包算法的一對多行為隱寫

2.1 發(fā)送端

發(fā)送端具體流程如下：

（1）M=［m1，m2，…，ml］T表示二進(jìn)制秘密信息，n表示發(fā)送者S擁有的全部好友數(shù).H表示點(diǎn)贊矩陣，用來記錄S給好友發(fā)表過的動態(tài)的點(diǎn)贊情況.

H的第i行對應(yīng)S的第i個(gè)好友，H的第j列表示S對不同好友的第j個(gè)動態(tài)的點(diǎn)贊狀態(tài)，若點(diǎn)了贊，則H中相應(yīng)元素記錄為1；若未點(diǎn)贊，則H中相應(yīng)元素記錄為0.

（2）發(fā)送者S給r1個(gè)接收者Ri（i=1，2，…，r1）傳送秘密信息M. 為了避免M中含有大量連續(xù)相同比特，將M進(jìn)行CMI編碼［9］得到序列N.

（3）H和N進(jìn)行二進(jìn)制內(nèi)積得到發(fā)送序列D，并根據(jù)以往發(fā)送者對每個(gè)好友的點(diǎn)贊概率p，對b·D經(jīng)過反算術(shù)編碼得到發(fā)送矩陣G. 反算數(shù)編碼是一種數(shù)據(jù)解壓縮的過程［10］，目的是通過概率p將0 和1 之間的小數(shù)表示成信息串. 概率p是通過對H的觀察所得，其中1的概率為H對應(yīng)行中1 所占的比例；0 的概率為H對應(yīng)行中0所占的比例. 對D乘系數(shù)b以滿足D中都為小數(shù)的條件，b的值通常取10-1或10-2.

（4）發(fā)送者按照G對其n個(gè)好友后續(xù)的動態(tài)進(jìn)行點(diǎn)贊，若G中某元素為1，則進(jìn)行點(diǎn)贊；若G中某元素為0，則不進(jìn)行點(diǎn)贊.

2.2 接收端

接收端采用發(fā)送者對多個(gè)接收者進(jìn)行人員分配的方案. 接收者用Ri表示（i=1，2，…，r1，r1為接收者的個(gè)數(shù)），非接收者用Nj表示（j=1，2，…，r2，r2為非接收者的個(gè)數(shù)）.Ri和Nj統(tǒng)稱為可能接收者Pλ（λ=1，2，…，k）.k滿足：

k=r1+r2（2）

接收端具體流程如下：

（1）根據(jù)人員分配協(xié)議，從Pλ（λ=1，2，…，r1+r2）中選出Ri（i=1，2，…，r1）.Ri根據(jù)點(diǎn)贊情況重構(gòu)Gi，Gi代表S與Ri的共同好友所對應(yīng)的發(fā)送矩陣. 接收端將Gi依次按行連接，去除相同的行（冗余）并用矩陣A表示.

（2）根據(jù)p對A進(jìn)行算數(shù)編碼，并將編碼后結(jié)果乘b-1得到B. 算術(shù)編碼是一種數(shù)據(jù)壓縮過程［10］，目的是通過概率p將信息串表示成0 和1 之間的小數(shù)，其中p的獲得與2.1 節(jié)相同.A是G的子矩陣，C是H的子矩陣. 由于G的每一行與H是相對應(yīng)的，接收端通過觀察H來獲得與A所對應(yīng)的C. 利用數(shù)據(jù)重建求解N，對N進(jìn)行CMI解碼得到M.

為了實(shí)現(xiàn)發(fā)送者對接收者狀態(tài)的操作可控，人員分配協(xié)議需滿足以下兩個(gè)條件：接收端的狀態(tài)可用數(shù)值y表示；發(fā)送者通過控制y的值，對接收端的狀態(tài)進(jìn)行控制.

將wλ表示Pλ的權(quán)重. 當(dāng)Pλ為接收者，wλ>0；當(dāng)Pλ為非接收者，wλ=0. 令

故y的值反映了可能接收者Pλ的狀態(tài). 發(fā)送者設(shè)定一個(gè)閾值a（a>y），通過改變a的值來控制Pλ的狀態(tài).a和y的關(guān)系滿足：

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

現(xiàn)將wλ用wλ·xλ表示，其中xλ∈｛0，1｝，xλ=1 時(shí)，Pλ為接收者；xλ=0時(shí)，Pλ為非接收者. 則以上關(guān)系的數(shù)學(xué)模型為

此數(shù)學(xué)模型的文字?jǐn)⑹鰹椋喊l(fā)送者設(shè)定閾值a來控制Pλ的狀態(tài)，Pλ狀態(tài)的最優(yōu)解滿足a與y的差值最小. 故針對一對多行為隱寫的人員分配協(xié)議，可用0-1 背包算法來解決.

0-1 背包人員分配協(xié)議如圖3 所示，Pλ各自擁有重量wλ和價(jià)值vλ，并且根據(jù)發(fā)送者S公布的0-1背包信息，利用動態(tài)規(guī)劃法計(jì)算得知最優(yōu)解時(shí)背包問題的最大價(jià)值v［k］［c］［11］. 接收端在k個(gè)Pλ中隨機(jī)選出r1個(gè)Pλ，他們的價(jià)值用vkφ（φ=1，2，…，r1）表示，并判斷式（6）是否成立.

圖3 0-1背包人員分配協(xié)議

如果式（6）成立，則這r1個(gè)Pλ均為接收者；否則再次進(jìn)行0-1背包人員分配協(xié)議過程.

2.3 算法流程

將上述發(fā)送端和接收端整合，則本文所提出的基于0-1 背包算法的一對多行為隱寫技術(shù)詳細(xì)流程如算法1所示.

算法1 中，發(fā)送端對應(yīng)偽代碼中1~4 行，接收端對應(yīng)偽代碼中5~16行，0-1 背包問題的求解過程對應(yīng)偽代碼中5~10 行，0-1 背包分配協(xié)議對應(yīng)偽代碼中第11 行.算法的時(shí)間及空間復(fù)雜度均為O（ck）.

3 實(shí)驗(yàn)結(jié)果

本文以微信中某一個(gè)用戶作為發(fā)送者，使用We Chat Moment Stat 檢索其朋友在Android 設(shè)備上發(fā)布的動態(tài)，選擇滿足條件的朋友作為接收者，以此為基礎(chǔ)進(jìn)行測試實(shí)驗(yàn)并分析. 實(shí)驗(yàn)采用酷睿4 核i5-6300HQ，8 GB 內(nèi)存，NVIDIA GeForce GTX 950M GPU，操作系統(tǒng)為Windows 10 的設(shè)備上進(jìn)行，使用MATLAB 編程語言實(shí)現(xiàn).

3.1 可行性分析

我們以S的某8 位朋友作為可能接收者，將M的位數(shù)l設(shè)為16，反算數(shù)編碼的位數(shù)設(shè)為8. 在傳遞大小為128×128 的二值圖實(shí)際實(shí)驗(yàn)中，依次按列選取16 個(gè)像素點(diǎn)作為秘密信息，并選出至少與S有8 位共同好友的6 位作為可能接收者，每傳遞16 位秘密信息，發(fā)送者根據(jù)0-1 背包分配協(xié)議隨機(jī)選取4 位接收者，2 位非接收者；在傳遞大小為256×256 的灰度圖模擬實(shí)驗(yàn)中，發(fā)送端將灰度圖分解為八個(gè)二值圖進(jìn)行遍歷操作，接收端將恢復(fù)后的八個(gè)二值圖合成為灰度圖進(jìn)行誤碼率分析.

3.1.1 傳遞二值圖可行性分析

圖4（a）為待傳遞的二值圖像，圖4（b）為直接傳遞后的結(jié)果，誤碼率高達(dá)49.29%，可見對于二值圖中大量連續(xù)相同比特的情況，算數(shù)編碼具有較大的誤差. 圖4（c）為加入混沌變換［12］圖像處理后的結(jié)果，誤碼率高達(dá)52.44%，分析得知，混沌變換不能徹底解決大量連續(xù)相同比特的情況. 圖4（d）為加入CMI編碼圖像處理后的結(jié)果，誤碼率為0.02%. 由此可見，本文中提出的加入CMI編碼圖像預(yù)處理方法誤碼率較低，有較好的可行性.

圖4 傳遞二值圖的可行性分析

3.1.2 傳遞灰度圖可行性分析

圖5（a）為Lena 灰度圖，圖5（b）至圖5（i）依次為灰度圖分解的八個(gè)位圖，圖5（j）為接收端恢復(fù)后的灰度圖. 8 個(gè)位圖總誤碼率為0.461%，灰度圖誤碼率為3.06%. 實(shí)驗(yàn)結(jié)果表明，本方案有較低的誤碼率，并且有較好的可行性.

3.2 接收者掉線情況下可行性分析

要保證接收端正確提取秘密信息Ml×1，就要確保其他接收者收到的發(fā)送矩陣的并集不小于2l行.Ri（i=1，2，…，r1）與S的共同好友數(shù)用ni（i=1，2，…，r1）來表示.h表示Ri（i=1，2，…，r1）與S共同好友數(shù)的算術(shù)平均值：

掉線情況分析如下：

（1）當(dāng)至少有1 位接收者（用Rf表示，f∈｛1，2，…，r1｝）與S的共同好友數(shù)大于或等于2l時(shí)，Rf與其他在線接收者不會受掉線接收者的影響；

（2）當(dāng)Ri（i=1，2，…，r1）與S的共同好友數(shù)都小于2l時(shí)，r1個(gè)接收者中僅有s（s≤r1）個(gè)人在線的情況下，在線接收者能收到發(fā)送矩陣的并集不小于2l行的概率p1為：

本小節(jié)在數(shù)據(jù)集樣本的基礎(chǔ)上，傳遞4 位秘密信息，選取與S共同好友數(shù)為3 的5 位朋友作為可能接收者. 每一種情況都進(jìn)行1000次測試，結(jié)果如圖6所示.

實(shí)驗(yàn)分析如下：

對比綠色和橙色條形圖可知，在線接收者的個(gè)數(shù)s并不是決定是否接收成功的關(guān)鍵，關(guān)鍵在于h與s的乘積是否大于2l. 對比黃色和橙色條形圖可知，其他條件不變的情況下，h對成功率影響較大，故在實(shí)際應(yīng)用可以提高h(yuǎn)來提高傳遞秘密信息的成功率.

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

暴力破解攻擊［13］往往針對具有有限容量的密碼字典并且有破解成功提醒的加密方案，社交網(wǎng)絡(luò)下行為隱寫雖然具有有限容量的密碼字典，但并沒有破解成功提醒. 所以針對暴力破解攻擊，本文的方案理論上是絕對安全的.

文獻(xiàn)［14］提出了利用行為相關(guān)性檢測異常點(diǎn)贊行為的隱寫分析算法，該算法將動態(tài)按點(diǎn)贊的數(shù)量升序排序. 點(diǎn)贊數(shù)量占三分之一以下的動態(tài)數(shù)目用d1表示；點(diǎn)贊數(shù)量占三分之二以上的動態(tài)數(shù)目用d2表示. 將這兩種類型可疑者做出的點(diǎn)贊數(shù)目分別用d1′和d2′表示，計(jì)算差值d=d1′/d1-d2′/d2，如果d＜0.25，則點(diǎn)贊行為異常，否則點(diǎn)贊行為正常.

圖5 傳遞灰度圖的可行性分析

圖6 接收端不同種掉線情況下的可行性分析

本實(shí)驗(yàn)利用暴力破解攻擊和文獻(xiàn)［14］的隱寫分析方法對文獻(xiàn)［7］與本文方案在不同測試集下進(jìn)行攻擊破解，數(shù)據(jù)集統(tǒng)計(jì)如表1所示.

表1 數(shù)據(jù)集樣本統(tǒng)計(jì)

在此數(shù)據(jù)集的條件下，暴力破解攻擊結(jié)果如圖7所示.

圖7 安全性分析

結(jié)果顯示，隨著文獻(xiàn)［7］中數(shù)據(jù)集的增大，發(fā)送者和接收者的共同好友增多，會導(dǎo)致暴力破解總次數(shù)變多；而0-1 背包算法下的點(diǎn)贊隱寫由于發(fā)送者和接收者們的共同好友數(shù)并沒改變，所以暴力破解字典總?cè)萘坎⑽锤淖?

我們將暴力破解字典容量用t1表示，為了測試0-1背包算法對安全性的提升，對不同數(shù)據(jù)集情況下的安全性進(jìn)行分析，實(shí)驗(yàn)結(jié)果如表2所示.

結(jié)果表明，隨著h的增加，暴力破解字典容量顯著增多，安全性顯著提高.

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

本節(jié)利用假冒攻擊［15］，對本文的安全性進(jìn)行測試. 假冒攻擊過程如下：非接收者獲得接收者的信息并假冒成接收者，由于協(xié)議中每次選取r1個(gè)可能接收者的過程是隨機(jī)的，假冒者存在一定的假冒成功的幾率. 但是假冒者收到的發(fā)送矩陣是置亂的，即使假冒者假冒成功，也并不能竊取到秘密信息，所以假冒者對通信過程是破壞，而不是竊取.

表2 不同數(shù)據(jù)集下的安全性分析

由于假冒攻擊與數(shù)據(jù)集樣本容量無關(guān)，故不考慮數(shù)據(jù)集樣本容量的影響.r3為非接收者中假冒攻擊者的個(gè)數(shù)，p2為r1個(gè)接收者被成功確認(rèn)的概率，p3為假冒攻擊者成功破壞的概率，p4為檢測出假冒者從而中斷通信的概率. 對每種情況測試1000次，為了符合社交網(wǎng)絡(luò)的隨機(jī)性，每次實(shí)驗(yàn)都將接收者和非接收者隨機(jī)排列.

每次實(shí)驗(yàn)只存在3 種情況：接收者被成功確認(rèn)；假冒攻擊者成功破壞；協(xié)議執(zhí)行過程中，出現(xiàn)兩個(gè)及以上可能接收者的背包信息相同，則假冒者一定存在，此時(shí)中斷通信. 如果不滿足3種情況的其中之一，則繼續(xù)重復(fù)協(xié)議執(zhí)行過程. 在假冒攻擊者個(gè)數(shù)為2的情況下，假冒攻擊者可能存在兩種假冒情況：分別假冒成不同的接收者；假冒成同一個(gè)接收者. 這兩種情況的統(tǒng)計(jì)次數(shù)分別置于表3單元格左側(cè)和右側(cè).

表3 假冒攻擊下的安全性測試

實(shí)驗(yàn)表明，假冒攻擊對本文協(xié)議有很強(qiáng)的破壞性，假冒者個(gè)數(shù)為1 時(shí)，破壞成功率高達(dá)80%到86%；假冒者個(gè)數(shù)為2時(shí)，破壞成功率高達(dá)90%到93%.

4 結(jié)論

本文提出了基于0-1 背包算法的社交網(wǎng)絡(luò)下行為隱寫模型，協(xié)議雙方由一對一變?yōu)橐粚Χ?，并且接收者的狀態(tài)可以由發(fā)送者控制，更加符合社交網(wǎng)絡(luò)下隨機(jī)性的特點(diǎn). 通過模擬分析得知，該方案有很好的可行性；在安全性上，該方案有很好的抗解密性，但抗檢測性不足，假冒攻擊下的安全性不高，并且在傳遞秘密信息的容量上有待提升.