針對源代碼的隱蔽通道標(biāo)識關(guān)鍵技術(shù)及其改進方法

1、第43卷第1期 2009年1月上海交通大學(xué)學(xué)報JOU RN AL O F SH AN G HA I JIA OT O N G U N IV ERSIT YVol. 43No. 1 J an. 2009收稿日期:2007 11 23基金項目:國家高技術(shù)研究發(fā)展計劃(863 資助項目(2006AA01Z432 ; 國家自然科學(xué)基金資助項目(60773170, 60721002, 60473053 ;江蘇省自然科學(xué)基金資助項目(BK2005074作者簡介:支雷磊(1982 , 男, 陜西渭南人, 碩士生, 主要從事信息安全方面的研究.曾慶凱(聯(lián)系人 , 男, 教授, 博士生導(dǎo)師, 電話(T el.

2、:025 83686700; E mail:zqknju. edu. cn.文章編號:1006 2467(2009 01 0101 05針對源代碼的隱蔽通道標(biāo)識關(guān)鍵技術(shù)及其改進方法支雷磊, 王 佳, 曾慶凱(南京大學(xué)計算機軟件新技術(shù)國家重點實驗室; 計算機科學(xué)與技術(shù)系, 南京210093 摘 要:介紹了標(biāo)識源代碼中隱蔽通道的關(guān)鍵技術(shù):數(shù)據(jù)流分析、別名分析和信息流安全性分析, 并指出其存在的問題. 在綜合并優(yōu)化各種技術(shù)的基礎(chǔ)上, 提出包括結(jié)構(gòu)分析、別名分析、信息流分析和安全鑒別等過程的改進方法, 通過改造開源編譯器GCC, 利用其生成的抽象語法樹和控制流程圖, 并對Linux 0. 11文件系統(tǒng)

3、和示例程序進行分析測試. 結(jié)果表明, 該方法可提高隱蔽通道標(biāo)識的效率和精確性.關(guān)鍵詞:源代碼; 隱蔽通道標(biāo)識; 數(shù)據(jù)流; 別名; 信息流中圖分類號:TH 122 文獻標(biāo)識碼:AKey Technologies and Improvem ent of IdentifyingCovert Channels in Source CodeZH I L ei lei, WAN G J ia, ZEN G Qing kai (State Key Laboratory for Novel So ftw are Technolo gy;Departm ent of Co mputer Science and

4、T echnolog y, Nanjing U niversity , Nanjing 210093, China Abstract:T he key technolo gies o f identify ing covert channel in source co de, including data flow analy sis, alias analy sis and infor matio n flo w security analysis w ere discussed. By summ ar izing and optim izing vari o us technolog ie

5、s, an improv ed appr oach com po sed of ar chitecture analysis, alias analy sis, info rmation flow analysis and security identificatio n w as presented. A prototype of the approach w as implem ented using ab stract syntax tree and control flow gr aph w hich are generated by GCC. T he ex perimental r

6、esults show that the efficiency and precision o f cov er t channel identification are improved.Key words:source code; covert channel identification; data flow ; alias; infor mation flow隱蔽通道處理是高等級安全操作系統(tǒng)實現(xiàn)中的重要環(huán)節(jié), 各類安全標(biāo)準(zhǔn)中對其都有明確要求. 隱蔽通道的標(biāo)識有共享資源矩陣1及其改進2、無干擾方法、隱蔽流樹3、信息流4和動態(tài)檢測5等多種方法. 其中, 共享資源矩陣及其改進和隱蔽流樹法不適

7、合源代碼級的隱蔽通道標(biāo)識; 無干擾方法是一種理想方法, 但是難于實現(xiàn); 動態(tài)檢測方法能發(fā)現(xiàn)正在使用的隱蔽通道, 但是不能標(biāo)識那些沒有使用的隱蔽通道, 且影響系統(tǒng)運行效率; 信息流法是針對源代碼的隱蔽通道標(biāo)識方法. 目前很難保證系統(tǒng)描述和系統(tǒng)實現(xiàn)之間的一致性, 因此, 通過分析源代碼找到其中的隱蔽通道成為隱蔽通道研究的關(guān)鍵.源代碼的隱蔽通道標(biāo)識需要從源代碼中分析系統(tǒng)的信息流, 判斷信息流的合法性并找出非法信息流, 然后通過構(gòu)造非法流的應(yīng)用場景來標(biāo)識隱蔽通道. 因此, 需要用別名分析識別系統(tǒng)中存在的別名; 數(shù)據(jù)流分析尋找系統(tǒng)中的信息流; 信息流安全性分析辨別信息流的合法性.本文總結(jié)了數(shù)據(jù)流、別名和

8、安全性分析等技術(shù), 提出了針對源代碼的隱蔽通道標(biāo)識的改進方法.1 數(shù)據(jù)流分析數(shù)據(jù)流分析常用于語言的編譯, 在程序不運行的情況下, 分析得到程序的一系列語義信息. 數(shù)據(jù)流分析可分為過程內(nèi)數(shù)據(jù)流分析、過程間數(shù)據(jù)流分析或者任意路徑數(shù)據(jù)流分析和全路徑數(shù)據(jù)流分析. 1. 1 基本概念定義1 在數(shù)據(jù)流分析中, 根據(jù)程序控制流程圖可得(假定為前向數(shù)據(jù)流分析 :ininit=in s= out P p ! pred (s out s=in skill s gen s(1式中:s 是程序的基本塊; in s是在s 之前存在的數(shù)據(jù)流信息; out s是s 之后得到的數(shù)據(jù)流信息; init 表示程序控制流程圖的開始

9、節(jié)點; P ! pred (s 表示流程圖中, P 是s 的直接前驅(qū):kill s表示經(jīng)過s 后失效的數(shù)據(jù)流信息; g en s表示s 生成的數(shù)據(jù)流信息. 對上式進行變形得 ininit= out s=f (s f (s = out P p !pred (skill s gen s(2所以, 數(shù)據(jù)流分析框架是1個二元組L , F #, 其中:L 為半格; F 是該半格上的流函數(shù)空間. L 中的值代表程序控制流程圖中每個節(jié)點的數(shù)據(jù)流信息. F 中流函數(shù)表示數(shù)據(jù)流信息在不同節(jié)點之間的轉(zhuǎn)換情況.1. 2 數(shù)據(jù)流計算方法數(shù)據(jù)流計算方法包括迭代算法、消去法和可達性算法等. 迭代法可以用工作表算法來實現(xiàn),

10、 其計算效率與半格、流函數(shù)以及管理工作表的方法有關(guān), 是1種容易實現(xiàn)的方法; 消去法又稱為基于控制樹的分析方法, 包括區(qū)間分析和結(jié)構(gòu)分析. 因為需要進行節(jié)點分割, 實現(xiàn)起來比迭代法難, 但當(dāng)程序改動時, 較容易更新數(shù)據(jù)流信息; 可達性算法6是將過程間數(shù)據(jù)流問題轉(zhuǎn)換成一種特殊的圖形可達性問題, 該算法解決了一類過程間的數(shù)據(jù)流分析問題, 從時間.1. 3 面臨的挑戰(zhàn)對并行程序的數(shù)據(jù)流分析還需要進一步的研究. 另外, 每種數(shù)據(jù)流分析方法都要保證其結(jié)果是正確和保守的, 即給出的結(jié)果不能誤解被分析過程的行為. 所以, 必須仔細設(shè)計數(shù)據(jù)流方程, 并確信計算出的解, 如果不是預(yù)期信息的精確表示, 至少也應(yīng)該

11、是保守近似表示. 所以, 找到更加高效、精確的分析算法, 也是對數(shù)據(jù)流分析的挑戰(zhàn).2 別名分析別名分析指判定可能用2種以上方式訪問的存儲位置. 例如, 對于變量C , 可以取其地址, 且可以通過變量名或者通過指針來讀寫. 為了在數(shù)據(jù)流分析中得到較精確的結(jié)果, 需要對程序中的別名進行精確分析. 2. 1 基本概念定義2 如果2個變量指向同一塊內(nèi)存, 則認為2個變量互為別名.別名關(guān)系的表示有全別名對、間接別名對、指向關(guān)系對3種形式. 別名信息可以分為可能別名和確定別名.2. 2 別名分析方法別名分析主要有過程內(nèi)別名分析和過程間別名分析.2. 2. 1 過程內(nèi)別名分析 過程內(nèi)別名分析的過程與通常的數(shù)

12、據(jù)流分析相似. 其分析方程為outs =g ens (ins kills 應(yīng)用迭代法解方程可得到函數(shù)的別名分析結(jié)果. 2. 2. 2 過程間別名分析 過程間別名分析需要考慮函數(shù)調(diào)用, 針對函數(shù)調(diào)用處理的不同, 可分為上下文敏感和上下文不敏感2類.(1 基于過程間控制流分析. 基于過程間控制流程圖(ICFG 的分析方法為每個函數(shù)生成控制流程圖, 并對控制流程圖進行修改. 將函數(shù)調(diào)用點分成1個調(diào)用節(jié)點和1個返回節(jié)點. 針對1個函數(shù), 也增加2個節(jié)點, 1個為入口節(jié)點, 1個為出口節(jié)點. 當(dāng)發(fā)生函數(shù)調(diào)用時, 調(diào)用節(jié)點和被調(diào)用函數(shù)入口節(jié)點相連, 被調(diào)用函數(shù)出口節(jié)點和返回節(jié)點相連. 這樣, 整個被分析程

13、序組成了1個ICFG, 如圖1所示.然后, 對該控制流程圖進行分析, 生成每個節(jié)點的別名信息, 再用工作列表方法進行分析, 生成需要的別名信息.這種方法效率不高, 對大型程序所生成的ICFG 很大且上下文不敏感, 在C1和C2處不能區(qū), 102上 海 交 通 大 學(xué) 學(xué) 報第43卷 圖1 過程間控制流程圖Fig. 1 Inter pro cedural co ntro l flow gr aph向e 的偽別名信息.(2 基于調(diào)用圖的分析. 在基于調(diào)用圖(IG 的分析方法中, IG 中的節(jié)點代表1個函數(shù)調(diào)用, 節(jié)點之間的連線代表函數(shù)調(diào)用關(guān)系. 但是, 1個函數(shù)的不同調(diào)用點將生成不同的節(jié)點. 由圖

14、1程序所生成的IG 如圖2所示 .圖2 程序調(diào)用圖Fig. 2 P rog ram inv ocatio n g ra ph在別名分析時, 先處理main 函數(shù), 當(dāng)遇到函數(shù)調(diào)用時, 用算法m ap 將目前已有的別名信息映射到函數(shù)體中, 即作為函數(shù)體分析初始別名信息. 當(dāng)函數(shù)體分析完成后, 應(yīng)用算法unmap 將函數(shù)體分析結(jié)果映射回main 函數(shù), 其處理過程如圖3所示 .圖3 基于IG 的分析過程Fig. 3 A naly sis pr ocess based o n IG該方法的結(jié)果比上下文不敏感的方法精確. 但是, 在生成IG 時, 每個調(diào)用點都生成不同的節(jié)點. 這樣, 隨著被分析程序的

15、規(guī)模增大, IG 中的節(jié)點數(shù)將快速增長, 存儲需求較大. 另外, 碰到一次函數(shù)調(diào)用時, 則要對函數(shù)體進行1次分析, 其效率不高. 遞函數(shù)分析(PTF 方法7對其進行了改進. 與全部傳遞函數(shù)不同, 其只針對輸入的1個子集計算傳遞函數(shù), 1個函數(shù)有可能出現(xiàn)多個部分傳遞函數(shù). 當(dāng)碰到函數(shù)調(diào)用時, 如果函數(shù)的輸入屬于某個部分傳遞函數(shù)的輸入, 則不需要對該函數(shù)體進行別名分析而直接調(diào)用部分傳遞函數(shù), 得到其別名分析結(jié)果. 從而進一步提高處理效率.(3 基于過程調(diào)用圖的分析. 基于過程調(diào)用圖(PCG 的處理過程類似于基于控制流程圖的分析, 只是進行了分解. 分析過程分為2個層次8, 上層分析是針對PCG 圖

16、的分析, 下層分析是對函數(shù)體的分析, 兩層均采用迭代分析方法8. 圖4是圖1中程序的PCG 圖. 這種方法是流敏感的, 但不是上下文敏感, 且效率不高.圖4 過程調(diào)用圖F ig. 4 P ro cedural call g raph(4 上下文敏感的基于過程調(diào)用分析. 把函數(shù)調(diào)用圖分解成不同的強連通分支9, 針對每個連通分支, 根據(jù)相反的拓撲順序依次分析每個函數(shù), 假設(shè)其參數(shù)和全局變量指向未知的變量. 這樣, 對每1個函數(shù)計算出1個總體傳遞函數(shù). 從上往下, 在函數(shù)調(diào)用時, 將具體的別名信息傳遞給被調(diào)用函數(shù), 然后, 將被調(diào)用函數(shù)中假設(shè)未知的變量替換成具體變量, 最終得到每個函數(shù)點的別名信息.

17、上下文敏感的基于過程調(diào)用分析方法9是流敏感, 也是上下文敏感, 因采用模塊化分析方法, 提高了分析效率, 且可以對程序中的一部分進行分析. 這樣, 只需要把程序中的一部分裝入內(nèi)存就可以分析, 相比以前提出的方法, 對內(nèi)存的需求減小. 2. 3 面臨的挑戰(zhàn)在別名分析中, 堆空間的分配、遞歸數(shù)據(jù)結(jié)構(gòu)、遞歸函數(shù)調(diào)用以及函數(shù)指針的應(yīng)用等都給別名分析帶來了額外的復(fù)雜度, 并且其分析精度不高. 所以, 尋找高效、精確的別名分析算法是當(dāng)前所面臨的挑戰(zhàn). 另外, 如何應(yīng)對增量分析、需求驅(qū)動的分析以及部分程序的分析, 也是一種挑戰(zhàn).3 信息流安全性分析信息流控制對計算機安全十分重要, 不安全的. , 103第1

18、期支雷磊, 等:針對源代碼的隱蔽通道標(biāo)識關(guān)鍵技術(shù)及其改進方法性的主要方式是訪問控制. 但是, 當(dāng)數(shù)據(jù)按照訪問控制策略傳遞給訪問者后, 很難保證數(shù)據(jù)會以安全的方式傳播. 所以, 為了保證機密數(shù)據(jù)按照一定的策略合理使用, 一定要確保數(shù)據(jù)在使用程序中流動的安全性. 對源代碼的隱蔽通道分析也要關(guān)注信息流的安全性.3. 1 基本概念不失一般性, 假設(shè)程序中存在2個安全級別H 和L , 那么, 用不干擾性來描述程序沒有泄漏H 的數(shù)據(jù)給L .定義3 針對任意的存儲單元u 和v , 其中存儲安全級別為L 的變量, 當(dāng)程序c 運行完后, 存儲單元u 和v 仍然存儲的是安全級別為L 的變量, 那么, 程序c 具有

19、不干擾性.不干擾性保證觀察者在程序運行結(jié)束后, 不能從安全級別為L 的變量中得知安全級別為H 的信息, 從而保證沒有信息泄漏.3. 2 信息流安全性分析方法3. 2. 1 Denning 模型 Dennig 提出了基于格的信息流安全模型, 認為1個信息流策略針對信息流并說明1個安全類集合和1個流關(guān)系以及將存儲對象和安全類綁定的方法. 流關(guān)系定義了不同安全類之間信息流動的合法性.1個信息流模型被定義為FM =N, P, SC, , #其中:N =a, b, c, %表示邏輯存儲對象的集合或者信息容器; P 是進程的集合; SA 是安全類的集合. 集合N 中的每個對象綁定1個S A 中的安全類,

20、P 中的進程也綁定1個安全類. 是安全類的合操作. 是這個安全模型定義的合法信息流規(guī)則, 例如, 如果FM 允許安全類為A 的信息流向安全類為B 的類型, 則記作A B.根據(jù)給出的信息流安全模型, 對程序靜態(tài)的語法分析后可用于驗證程序中信息流的安全性. 3. 2. 2 基于類型系統(tǒng)的信息流安全 在類型系統(tǒng)中, 每個表達式有1個安全類型10, 包括2部分:一部分是表達式原有的類型; 另一部分表示該表達式在信息流安全策略中的使用. 編譯器讀取包含安全類型的程序, 然后進行類型檢查, 確保每個變量都按照安全策略被正確使用.基于類型系統(tǒng)的信息流安全要求為:如果1個程序可類型化, 則其滿足不干擾性. 在

21、安全類型系統(tǒng)中, 在任意偏序的安全層次上進行類型推導(dǎo)是NP 完全問題, 所以, 需要將安全層次組成1個格. 這和3. 3 面臨的挑戰(zhàn)信息流安全性分析的主要挑戰(zhàn)有12:&研究大部分停留在理論階段, 針對的都是簡單語言, 而實用語言的復(fù)雜性很高; 信息流安全策略的目的是實現(xiàn)不干擾性, 但不干擾性是理想目標(biāo), 需要有更靈活的形式化方法來定義安全策略; (變量的安全級別是靜態(tài)確定的, 但在現(xiàn)實系統(tǒng)中則相反, 會造成分析結(jié)果不精確.4 源代碼隱蔽通道標(biāo)識改進方法通過以上分析可以發(fā)現(xiàn), 隱蔽通道標(biāo)識的關(guān)鍵技術(shù)還需要進一步完善和改進. 數(shù)據(jù)流分析需要找到更高效、精確的分析算法; 別名分析面臨著遞歸調(diào)

22、用、遞歸數(shù)據(jù)結(jié)構(gòu)以及函數(shù)指針等問題; 信息流安全分析面臨著目標(biāo)過于理想、實用性不佳的問題.而現(xiàn)有的隱蔽通道標(biāo)識方法, 如共享資源矩陣和隱蔽流樹等, 不適合源代碼級的隱蔽通道標(biāo)識, 即使勉強用于源代碼, 也會使共享資源矩陣或者隱蔽流樹規(guī)模迅速增大而不易處理. 另外, 因為這些方法沒有細致地區(qū)分變量之間的信息流動, 導(dǎo)致過多偽隱蔽通道的出現(xiàn). 共享資源矩陣的改進方法也沒有從根本上解決精確標(biāo)識信息流的問題. 而且沒有采用信息流安全性分析技術(shù)來判別信息流的安全性, 需要人工識別; 即使現(xiàn)有的少數(shù)針對源代碼的標(biāo)識方法, 也沒有綜合和發(fā)揮各種技術(shù)的優(yōu)點. 例如, T sai 提出的隱蔽通道標(biāo)識方法5, 雖

23、然對信息流進行了粗略處理, 但是沒有充分利用數(shù)據(jù)流分析的精確性, 會產(chǎn)生不存在的信息流, 導(dǎo)致偽隱蔽通道數(shù)量增加; 同時, 沒有采用信息流安全性分析來自動識別非法的數(shù)據(jù)流, 其分析周期偏長.因此, 可認為源代碼隱蔽通道標(biāo)識應(yīng)包括結(jié)構(gòu)分析、別名分析、信息流分析和安全鑒別4個環(huán)節(jié), 并優(yōu)化各種技術(shù), 提出以下改進源代碼隱蔽通道的標(biāo)識方法.(1 對源代碼進行系統(tǒng)劃分. 首先, 分析源代碼, 生成函數(shù)調(diào)用圖, 將函數(shù)調(diào)用圖劃分為不同的連通分支. 從中找出可能存在的并行性, 有助于縮短隱蔽通道標(biāo)識的周期.(2 別名分析. 采用流敏感和上下文敏感的別名分析方法, 對程序中每個點的別名信息進行標(biāo)識.(3 采

24、用數(shù)據(jù)流分析方法對程序中的信息流進行標(biāo)識. 針對C 語言存在顯式信息流和隱式信息流5, 利用別名分析結(jié)果得到更精確的信息流分析結(jié)果, 再以系統(tǒng)調(diào)用為依據(jù), 生成候選隱蔽通道.104上 海 交 通 大 學(xué) 學(xué) 報第43卷以及信息流安全性分析方法, 找到非法的信息流, 以此鑒別真正的隱蔽通道和偽隱蔽通道, 并生成隱蔽通道的應(yīng)用場景. 首先, 對待分析系統(tǒng)進行劃分, 增加后續(xù)處理的并行性, 提高隱蔽通道標(biāo)識的效率; 其次, 別名分析和信息流分析提供了精確的信息流結(jié)果, 減少了偽隱蔽通道產(chǎn)生的數(shù)量, 相應(yīng)地減輕了后續(xù)處理的負擔(dān); 此外, 采用程序信息流安全性分析相關(guān)技術(shù), 可自動進行信息流安全性分析,

25、 減少了分析人員的工作量, 進一步提高了隱蔽通道標(biāo)識的自動化程度和效率. 本方法針對源代碼的隱蔽通道標(biāo)識, 能得到隱蔽通道信息流動的路徑, 為后續(xù)的隱蔽通道帶寬計算和通道消除帶來了便利.本文對開源編譯器GCC 進行改造, 在其中插入鉤子函數(shù), 通過調(diào)用共享庫中的分析程序, 實現(xiàn)對代碼的分析. 利用鉤子函數(shù)傳入的抽象語法樹和控制流程圖分析代碼, 對代碼進行精確的數(shù)據(jù)流分析.在系統(tǒng)結(jié)構(gòu)分析過程中, 首先生成系統(tǒng)的函數(shù)調(diào)用圖, 然后對其進行劃分, 找到其中強連通子圖和連通分支以及單個函數(shù)和可能的并行性, 并且為后續(xù)的分析提供處理次序. 別名分析和信息流分析采用數(shù)據(jù)流分析技術(shù), 按照結(jié)構(gòu)分析提供的次序

26、, 對系統(tǒng)中的函數(shù)分別進行分析. 最后, 按照被分析系統(tǒng)提供的系統(tǒng)調(diào)用而生成候選通道, 并且采用安全鑒別技術(shù)鑒別通道真?zhèn)?對Linux 0. 11內(nèi)核中的文件系統(tǒng)代碼進行結(jié)構(gòu)分析表明:其中共有116個函數(shù); 而sys_ioctl和tty_ioctl組成的部分可以和其他函數(shù)并行處理; 如果對結(jié)構(gòu)分析算法進行改進, 可以出現(xiàn)6個可能的并行性; 進一步改進, 出現(xiàn)了13次可能的并行性.由于C 語言程序結(jié)構(gòu)比較復(fù)雜, 在實現(xiàn)中對程序進行了簡化; 為了方便后續(xù)的通道辨別, 利用圖像軟件Graphviz 可視化地生成了各候選通道的信息流動路徑. 對某個示例程序進行分析表明:共享資源矩陣有8個候選通道; T

27、 sai 方法有4條候選通道; 而本方法只有3條候選通道. 可見通過精確的信息流分析可以減少偽隱蔽通道的數(shù)目.5 結(jié) 語本文介紹并分析了源代碼隱蔽通道標(biāo)識的主要關(guān)鍵技術(shù)及其面臨的問題和挑戰(zhàn), 并提出了針對源代碼隱蔽通道標(biāo)識的改進方法. 實驗結(jié)果表明, 發(fā)現(xiàn)了并行分析的可能性, 提高了隱蔽通道標(biāo)識的效率;另外, 由于精確分析了代碼中的信息流, 減少了生成的候選通道數(shù)目, 提高了標(biāo)識精度. 參考文獻:1 K emmerer R A. A practical appr oach to identifyingstor age and t iming channels C/Twenty Years La

28、ter Proc of IEEE the 18th Annual C omputer Security Ap plications C onference. U SA :I EEE Inc, 2002.2 K emmerer R A, T aylor T . A mo dular co ver t channelanaly sis methodolog y fo r tr usted DG/U X T M J.IEEE Trans on Sof tware Engineering, 1996, 22:224 235.3 K emmerer R A, P or ras P A. Cov ert

29、flow tr ees:Av isual appro ach to ana lyzing co vert sto rag e channels J. IEEE Trans on Sof tware Engineering, 1991, 17(11 :1166 1185.4 T sai C R, Glig or V D, Chander sekar an C S. O n theidentificatio n of cover t sto rag e channels in secure sys tems J. IEEE Trans on Sof tware Engineering, 1990, 16(6 :569 580.5 W ang C D , Ju S G. Searching cov ert channels byidentify ing malicious subjects in the time domain J.Proc of IEEE Workshop on Information Assurance, 2004(1 :68 73.6 Reps T , Sag iv M , H