[發(fā)明專利]一種面向隱蔽通道分析的系統(tǒng)分析和劃分方法

無效

• 申請(qǐng)?zhí)枺?/td>: 200810156069.8
• 申請(qǐng)日: 2008-09-19
• 公開（公告）號(hào): CN101364203A
• 公開（公告）日: 2009-02-11
• 發(fā)明（設(shè)計(jì)）人: 曾慶凱;支雷磊
• 申請(qǐng)（專利權(quán)）人: 南京大學(xué)
• 主分類號(hào): G06F11/36
• 分類號(hào): G06F11/36
• 代理公司: 南京天翼專利代理有限責(zé)任公司
• 代理人: 湯志武;王鵬翔

技術(shù)領(lǐng)域

本發(fā)明涉及高等級(jí)安全系統(tǒng)中使用的面向隱蔽通道分析的系統(tǒng)分析和劃分方法。

背景技術(shù)

隱蔽通道分析是高等級(jí)安全系統(tǒng)開發(fā)中不可或缺的環(huán)節(jié)，對(duì)源代碼進(jìn)行隱蔽通道分析是一種重要手段。隨著系統(tǒng)規(guī)模和復(fù)雜度的不斷提高，面對(duì)龐大的系統(tǒng)，源代碼分析問題的規(guī)模使得工作越來越困難。所以，需要有一種方法，對(duì)系統(tǒng)進(jìn)行源代碼分析和劃分，以降低分析工作的規(guī)模。

在系統(tǒng)源代碼中，函數(shù)是分析的基本單位，通過分析函數(shù)之間的相互調(diào)用關(guān)系，發(fā)現(xiàn)函數(shù)之間的依賴關(guān)系(函數(shù)之間的調(diào)用和被調(diào)用關(guān)系)，據(jù)此進(jìn)行系統(tǒng)劃分，可以為后續(xù)隱蔽通道分析提供分析處理的次序和范圍，查找并行分析的可能。本發(fā)明提供一種對(duì)函數(shù)調(diào)用圖進(jìn)行分析和劃分方法，可簡(jiǎn)化此后進(jìn)行隱蔽通道分析的問題復(fù)雜度，提高分析效率。同時(shí)，本方法也可用于其它信息流分析的預(yù)處理過程。

發(fā)明內(nèi)容

本發(fā)明目的是：提出一種面向隱蔽通道分析的系統(tǒng)分析和劃分方法。在源代碼的隱蔽通道分析中，針對(duì)因系統(tǒng)代碼規(guī)模龐大、錯(cuò)綜復(fù)雜，不利于分析處理的問題，提供一種分析整個(gè)系統(tǒng)的函數(shù)調(diào)用關(guān)系，并把系統(tǒng)分成連通分支的方法。

本發(fā)明技術(shù)方案是：面向隱蔽通道分析的系統(tǒng)分析和劃分方法，實(shí)施系統(tǒng)分析和劃分的工作流程，步驟10：初始化動(dòng)作；步驟11：判斷函數(shù)調(diào)用圖是否為空，如果為空轉(zhuǎn)步驟12，表示分析劃分算法結(jié)束，否則轉(zhuǎn)步驟13；步驟12：輸出分析的結(jié)果；步驟13：判斷函數(shù)調(diào)用圖是否連通，如果連通轉(zhuǎn)步驟16，否則轉(zhuǎn)步驟14；步驟14：找出函數(shù)調(diào)用圖所有不連通的分支；步驟15：循環(huán)分析函數(shù)調(diào)用圖的每個(gè)連通分支；步驟16：判斷函數(shù)調(diào)用圖中是否存在不依賴其他節(jié)點(diǎn)的節(jié)點(diǎn)，即出度為0的節(jié)點(diǎn)；如果存在節(jié)點(diǎn)轉(zhuǎn)步驟17，否則轉(zhuǎn)步驟19；步驟17：找到出度為0的節(jié)點(diǎn)；步驟18：把出度為0的節(jié)點(diǎn)從函數(shù)調(diào)用圖中刪除，并且把該節(jié)點(diǎn)加入結(jié)果鏈表的末尾；結(jié)果鏈表指存儲(chǔ)分析結(jié)果的鏈表，其中的元素可能為連通分支、單個(gè)節(jié)點(diǎn)或極大強(qiáng)連通子圖；序列中的先后關(guān)系表明了元素之間的依賴關(guān)系，后面元素只依賴前面的元素；步驟19：判斷函數(shù)調(diào)用圖中是否存在極大強(qiáng)連通子圖，并且這個(gè)子圖沒有指向子圖外節(jié)點(diǎn)的邊；如果存在轉(zhuǎn)步驟1a，否則轉(zhuǎn)步驟11；步驟1a：找到函數(shù)調(diào)用圖中的極大強(qiáng)連通子圖，并且該子圖沒有指向子圖外節(jié)點(diǎn)的邊；步驟1b：刪除此極大強(qiáng)連通子圖，并且把該子圖加入結(jié)果鏈表末尾。步驟1c：結(jié)束狀態(tài)。

本發(fā)明方法包括3個(gè)主要步驟，步驟13：判斷函數(shù)調(diào)用圖是否連通

步驟16：判斷函數(shù)調(diào)用圖中是否存在不依賴其他節(jié)點(diǎn)的節(jié)點(diǎn)工作流程

步驟19：判斷函數(shù)調(diào)用圖中是否存在極大強(qiáng)連通子圖

分析函數(shù)調(diào)用圖連通性的流程，分析調(diào)用圖的連通性，并且記錄所有的連通分支。步驟20：初始動(dòng)作；步驟21：去除邊的方向變?yōu)闊o向圖；步驟22：判斷這個(gè)無向圖是否有節(jié)點(diǎn)，如果有轉(zhuǎn)步驟23，否則轉(zhuǎn)步驟27；步驟23：從無向圖中任選一個(gè)節(jié)點(diǎn)，作為深度優(yōu)先遍歷的起始節(jié)點(diǎn)；步驟24：以步驟23選擇的節(jié)點(diǎn)為起始節(jié)點(diǎn)，對(duì)無向圖進(jìn)行深度優(yōu)先遍歷，并且在遍歷過程中標(biāo)記已訪問的節(jié)點(diǎn)；步驟25：選擇所有被標(biāo)記的節(jié)點(diǎn)，這些節(jié)點(diǎn)在有向的函數(shù)調(diào)用圖中組成的子圖為它的一個(gè)連通分支，找到這個(gè)連通分支；步驟26：記錄這個(gè)連通分支，即把這個(gè)連通分支放入結(jié)果集合，且從無向圖中刪除所有被標(biāo)記的節(jié)點(diǎn)，轉(zhuǎn)步驟22；步驟27結(jié)束狀態(tài)。已找到函數(shù)調(diào)用圖中的所有連通分支，并且記錄在結(jié)果集合中。

判斷函數(shù)調(diào)用圖中是否存在不依賴其他節(jié)點(diǎn)函數(shù)的流程的步驟。函數(shù)調(diào)用圖中的所有節(jié)點(diǎn)被一個(gè)鏈表組織在一起。該過程遍歷這個(gè)鏈表，查找是否有出度為0的節(jié)點(diǎn)。步驟30：初始動(dòng)作；步驟31：取鏈表的第一個(gè)節(jié)點(diǎn)；步驟32：判斷這個(gè)節(jié)點(diǎn)的出度是否為0，如果是轉(zhuǎn)步驟33，否則轉(zhuǎn)步驟34；步驟33：設(shè)置返回值為真，并且記錄該出度為0的節(jié)點(diǎn)；步驟34：判斷是否到鏈表的末尾，如果是轉(zhuǎn)步驟35，否則轉(zhuǎn)步驟36；步驟35：設(shè)置返回值為假；步驟36：取鏈表中下一個(gè)節(jié)點(diǎn)，繼續(xù)分析；步驟37：結(jié)束狀態(tài)。