基于程序切片的隱秘通信
2010-01-01 00:00:00付東來陳夠喜
計算機應用研究 2010年2期
摘 要:提出了一種基于程序切片技術的隱秘通信方法。該方法借助于程序切片的思想找到了0，1信號與程序代碼間的對應關系，提出了具體的通信模型，詳細論述了隱秘通信方法。該方法具有良好的不可感知性及抗提取性。
關鍵詞:信息隱藏; 程序切片; 隱秘通信
中圖分類號:TP309
文獻標志碼:A
文章編號:1001-3695(2010)02-0740-02
doi:10.3969/j.issn.1001-3695.2010.02.093
Covert communication method based on program slicing
FU Dong-lai， CHEN Gou-xi
(School of Electron Computer Science Technology， North University of China， Taiyuan 030051， China)
Abstract:The paper presented a covert communication method based on program slicing.Found the relationship between an arbitrary 0，1 string and code. In addition to this，proposed a covert communication model and discussed an algorithm in detail. The method is imperceptibility and anti-extractable.
Key words:steganography; program slicing; covert communication
0 引言
隱秘通信是發送者將秘密信息嵌入到看似平常的信息中進行傳送，以防止第三方檢測出秘密信息的一種技術。它與密碼學的不同之處在于后者著眼于隱藏信息的內容，而隱秘技術則主要是隱藏信息的存在。在1983年Simmons提出的“囚犯問題”模型中，Alice利用密碼技術將越獄方案傳遞給Bob時，會引起看守者Willie的極大關注，從而導致信息傳遞失敗。然而，如果Alice借助隱秘技術則有可能騙過Willie達到成功傳遞信息的目的。
目前，大多數隱秘通信方法利用搭載秘密信息載體本身的冗余特性及人類對信息的掩蔽效應，使得秘密信息不可感知。已有的隱秘通信方法包括以下幾種:通過調整文字間距，利用文本文件搭載秘密信息;通過修改圖像中最不重要位搭載秘密信息;利用各種網絡協議攜帶秘密信息。但是，隱秘通信的實質并不局限于載體嵌入的方法，也可以通過信息的特殊轉換完成隱秘通信。例如，文獻[1]提出的非多媒體載體嵌入的新隱秘通道，文獻[2]提出一種新的基于時間機制的通道，文獻[3，4]基于IP的時間機制隱秘通道。程序切片技術[5]是一種分析和理解程序的技術，它通過對源代碼中每個興趣點計算切片達到理解程序的目的。目前，該技術已經廣泛應用于程序分析、理解、調試、測試、軟件維護、度量、逆向工程、再工程等領域，但較少應用在信息隱藏領域。
本文借助于程序切片的思想找到了用0，1表示的信號與程序代碼間的對應關系，該方法通過將一段固定長度的0，1序列轉換為程序代碼完成隱秘通信。
1 基本概念
為了討論方便，本文首先定義一些重要術語[6～11]。
定義1 控制依賴。設s1、s2和s3為程序P的三條語句，s2控制依賴于s1，當且僅當s2是否執行依賴于s1的執行。如果s2控制依賴于s1，并且在s1到s2的路徑上不存在語句s3，使得s2控制依賴于s3，那么s2直接控制依賴于s1，記為CD(s2，s1)。
定義2 數據依賴。設s1、s2為程序P的兩條語句，v為一變量，如果變量v在s1中定義，在s2中使用，并且在s1到s2的路徑上，沒有語句對v進行重新定義，則稱s2數據依賴于s1，記為DD(s2，s1)。
定義3 程序依賴圖PDG。程序P的程序依賴圖可用二元組G=(N， E)表示。其中:N是節點的集合，表示程序的基本模塊;E表示邊的集合，每條邊是一個有序節點對〈ni，nj〉，它表示ni與nj之間存在直接控制依賴或數據依賴關系，即CD(nj，ni)或DD(nj，ni)。
定義4 切片準則。程序P的切片準則是一個二元組〈s ， v〉。其中:s是程序中的一條語句;v是在語句s定義(向變量所在的地址空間寫內容)或使用(讀取變量所代表的內容)的變量或變量的集合。
定義5 程序的切片。依據切片準則〈s，v〉，在PDG上利用圖的可達性算法，首先尋找與語句s具有直接數據依賴或直接控制依賴的語句節點，然后再尋找與這些新節點有直接數據依賴或直接控制依賴的語句節點。一直反復下去，直到找不到新的語句節點為止，將這些節點按源程序順序進行排列，即為程序P關于語句s的一個切片，記為R(s，v)。
定義6 隱秘通信系統H。隱秘通信系統用五元組H=(C，M，C′，E，D)表示。其中:C是所有可能的掩飾信息，M是秘密信息的集合，嵌入函數E: C×M→C′。其中C′與C的近似性趨近于1，提取函數D:C′，→M。
定義7 二叉樹。二叉樹是n(n≥0)個節點的有限集合。當n=0時，稱為空二叉樹;當n>0時，有且僅有一個節點為二叉樹的根，其余節點被分成兩個互不相交的子集，一個作為左子集，另一個作為右子集，每個子集又是一棵二叉樹，記為BT(n)。
定義8 滿二叉樹。它是一棵深度為k且有2k-1個節點的二叉樹，記為FBT(n)。
2 基于程序切片的隱秘通信
2.1 基本模型
為了敘述簡單提出以下兩個假設:
a)Alice和Bob都擁有一段程序P，該程序片段P的程序依賴圖PDG滿足FBT(n)的性質，記為PDG_FBT(n)。
b)在PDG_FBT(n)的遍歷過程中，其左孩子記為0，右孩子記為1，那么當遍歷到一個葉子節點時就構成了一個0，1字符序列，Alice和Bob對此非常清楚。
基于以上兩個假設，當Alice準備與Bob進行通信時，Alice僅需首先將信號調制為0，1序列，然后根據PDG_FBT(n)葉子節點的容量將信號分割為多個子信號，將子信號映射為PDG_FBT(n)中某個葉子節點的一個切片準則，將此準則傳遞給Bob，Bob收到信號后，再依據切片準則尋找PDG_FBT(n)的一個子集并遍歷得到Alice的信號。其通信模型如圖1所示。
2.2 算法描述
基于程序切片的隱秘通信模型形式化的定義為Γ=(C，M，C′，E，D)。其中:C就是一段程序P;M是秘密信息的集合，嵌入函數E: C×M→C′(切片準則)，提取函數D: C×C′→M。算法的具體步驟如下:
a)構造一個程序片段 P，P的程序依賴圖PDG滿足FBT(n)的性質，那么這棵滿二叉樹就可表示任意一個n位的0，1字符序列。圖2是一個程序P的程序依賴圖，si表示程序的語句，有序對〈si，sj〉表示語句si與sj之間具有直接控制依賴或直接數據依賴關系。由圖2可見它是一個PDG_FBT(n)，n為15。其中葉子節點可分別表示的0，1序列:S7:000;S8:001;S9:010;S10:011;S11:100;S12:101;S13:110;S14:111。
b)依據葉子節點容量bk分割M為mi。如果假設M有m位0，1構成，m滿足:m=bkn，n為正整數的集合，那么M就可定義為
M={mi|mi由bk位的0，1構成，1≤i≤n}，圖2中bk=3。
c)依據每一個mi，構造切片準則=psi=〈s，v〉。
(a)令node=根節點(PDG_FBT(n))，j=1;
(b)取得mi的第j 位，vj=bitj(mi);
(c)如果vj為0，則令node=左孩子(node)，否則令node=右孩子(node);
(d)如果j==bk，則執行(e)，否則返回至(b)取mi的下一位;
(e)依據節點node構造切片準則psi=〈s，v〉。
d)依據切片準則psi=〈s，v〉利用基于程序依賴圖的圖可達性算法[8]計算切片。以圖2為例，假設切片準則psi=〈s，v〉中的s=s9，則切片后的程序依賴圖將變為圖3。于是，Bob按照左孩子為0、右孩子為1的編碼規則即可獲得Alice所傳遞的消息。
3 系統安全性
基于信息論的觀點，隱秘通信系統的安全性主要體現在以下三個方面:
a)不可感知性。假設PS是Γ系統通過信道發送的隱秘信息的概率分布，PC是搭載秘密信息載體的概率分布，則條件熵D(PC||PS)=∑c∈CPC(C)log2PC(C)PS(C)可用于度量嵌入過程E對概率分布PC的影響，若有D(PC||PS)≤ε，則Γ系統抵抗被動攻擊是ε-安全的。在Γ系統中，由于載體集合C是依據秘密信息集合M而定，隱秘信息集合C′與C相同，嵌入過程E不影響PC，Γ系統達到了較好的抗感知能力。
b)抗提取性。在Γ系統中，如果Willie發現信道中含有秘密信息并成功得到了隱秘信息psi=〈s，v〉，但由于切片準則僅是一些程序變量的集合，僅僅依據這些零散的信息是無法恢復程序P的。依據Γ系統的提取過程D，在P不存在的情況下，提取秘密信息是非常困難的。
c)魯棒性。在Γ系統中，如果Willie刻意偽造、竄改信道內容即切片準則psi=〈s，v〉，將直接導致切片算法的輸出出錯。
不可感知性、抗提取性反映了系統抗被動攻擊能力;魯棒性體現了系統抗主動攻擊能力。它們之間相互依賴、相互制約。提高系統的抗主動攻擊能力，必然會犧牲系統的抗被動攻擊能力。從隱秘通信的角度出發，系統的安全性對指標的要求由強到弱依次是:不可感知性、抗提取性、魯棒性。
4 結束語
