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

3、和示例程序進行分析測試. 結(jié)果表明, 該方法可提高隱蔽通道標識的效率和精確性.關(guān)鍵詞:源代碼; 隱蔽通道標識; 數(shù)據(jù)流; 別名; 信息流中圖分類號:TH 122 文獻標識碼: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é), 各類安全標準中對其都有明確要求. 隱蔽通道的標識有共享資源矩陣1及其改進2、無干擾方法、隱蔽流樹3、信息流4和動態(tài)檢測5等多種方法. 其中, 共享資源矩陣及其改進和隱蔽流樹法不適

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

8、安全性分析等技術(shù), 提出了針對源代碼的隱蔽通道標識的改進方法.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)起來比迭代法難, 但當程序改動時, 較容易更新數(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é)點. 當發(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ù), 當遇到函數(shù)調(diào)用時, 用算法m ap 將目前已有的別名信息映射到函數(shù)體中, 即作為函數(shù)體分析初始別名信息. 當函數(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ù). 當碰到函數(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ù)雜度, 并且其分析精度不高. 所以, 尋找高效、精確的別名分析算法是當前所面臨的挑戰(zhàn). 另外, 如何應(yīng)對增量分析、需求驅(qū)動的分析以及部分程序的分析, 也是一種挑戰(zhàn).3 信息流安全性分析信息流控制對計算機安全十分重要, 不安全的. , 103第1

18、期支雷磊, 等:針對源代碼的隱蔽通道標識關(guān)鍵技術(shù)及其改進方法性的主要方式是訪問控制. 但是, 當數(shù)據(jù)按照訪問控制策略傳遞給訪問者后, 很難保證數(shù)據(jù)會以安全的方式傳播. 所以, 為了保證機密數(shù)據(jù)按照一定的策略合理使用, 一定要確保數(shù)據(jù)在使用程序中流動的安全性. 對源代碼的隱蔽通道分析也要關(guān)注信息流的安全性.3. 1 基本概念不失一般性, 假設(shè)程序中存在2個安全級別H 和L , 那么, 用不干擾性來描述程序沒有泄漏H 的數(shù)據(jù)給L .定義3 針對任意的存儲單元u 和v , 其中存儲安全級別為L 的變量, 當程序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)不干擾性, 但不干擾性是理想目標, 需要有更靈活的形式化方法來定義安全策略; (變量的安全級別是靜態(tài)確定的, 但在現(xiàn)實系統(tǒng)中則相反, 會造成分析結(jié)果不精確.4 源代碼隱蔽通道標識改進方法通過以上分析可以發(fā)現(xiàn), 隱蔽通道標識的關(guān)鍵技術(shù)還需要進一步完善和改進. 數(shù)據(jù)流分析需要找到更高效、精確的分析算法; 別名分析面臨著遞歸調(diào)

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

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

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

25、 減少了分析人員的工作量, 進一步提高了隱蔽通道標識的自動化程度和效率. 本方法針對源代碼的隱蔽通道標識, 能得到隱蔽通道信息流動的路徑, 為后續(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é) 語本文介紹并分析了源代碼隱蔽通道標識的主要關(guān)鍵技術(shù)及其面臨的問題和挑戰(zhàn), 并提出了針對源代碼隱蔽通道標識的改進方法. 實驗結(jié)果表明, 發(fā)現(xiàn)了并行分析的可能性, 提高了隱蔽通道標識的效率;另外, 由于精確分析了代碼中的信息流, 減少了生成的候選通道數(shù)目, 提高了標識精度. 參考文獻: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