[發明專利]一種基于系統源代碼搜索隱通道的信息流分析方法

無效

• 申請號: 200810022701.X
• 申請日: 2008-07-24
• 公開（公告）號: CN101377806A
• 公開（公告）日: 2009-03-04
• 發明（設計）人: 鞠時光;宋梅香;王昌達;周從華;曾建
• 申請（專利權）人: 江蘇大學
• 主分類號: G06F21/22
• 分類號: G06F21/22;H04L29/06
• 代理公司: 南京知識律師事務所
• 代理人: 汪旭東

1、一種基于系統源代碼搜索隱通道的信息流分析方法，其特征在于，所述信息流分析方法包括下列步驟：

(1)借助程序設計語言編譯系統中的詞法分析程序，掃描系統源代碼，分別識別出源代碼中的函數和函數中的語句、變量；

(2)根據掃描程序識別出的函數以及函數調用語句，確定函數間的調用關系，構造語句樹段，給出每個函數的函數依賴集；

(3)根據掃描程序識別出的能產生信息流的語句和變量，作為信息流分析的輸入，構造函數信息流樹，并進行剪枝；

(4)遍歷函數信息流樹，輸出每個函數的信息流向圖；

(5)根據函數依賴集和它的信息流向圖，以函數依賴集為單位，獲得依賴集中函數間的共享變量可見性和可修改性信息，生成共享資源矩陣；

(6)以共享資源矩陣作為輸入，搜索隱通道，輸出系統中存在的隱通道序列。

2、根據權利要求1所述的分析方法，其特征在于，所述步驟(1)進一步包括下列步驟：

(1.1)預定義關鍵字表的結構和內容，存放所有關鍵字；用字符表存放掃描源代碼時識別出的標識符，字符表包括全局變量字符表和局部變量字符表；用函數名表存放掃描源代碼時識別出的函數名；

(1.2)用詞法分析程序對系統源代碼進行掃描，對一個輸入的字符串，通過查找關鍵字表、字符表和函數名表，來確定字符串的屬性，以二元式的形式輸出語句記號序列，語句記號序列包括標識記號和記號屬性。

3、根據權利要求1所述的分析方法，其特征在于，所述構造函數信息流樹步驟中，語句信息流規則為，將語句分為賦值語句、函數返回值語句、函數調用語句、控制語句和嵌套控制語句五類，分別給出它們的信息流規則。

4、根據權利要求1所述的分析方法，其特征在于，所述構造函數信息流樹步驟中，語句樹段構造規則是：語句信息流的源變量信息始終記錄在左孩子變量結點中，而語句信息流的目標變量信息始終記錄在右孩子變量結點中。

5、根據權利要求1所述的分析方法，其特征在于，所述步驟(3)中，剪枝的算法包括以下步驟：

(3.1)對函數中的語句，構造語句樹段，若語句為簡單語句，則按步驟(3.2)處理；若語句為嵌套控制語句，則按步驟(3.3)處理；

(3.2)對函數中簡單語句樹段進行遍歷，遍歷的過程中查看是否需要剪枝：遍歷源變量結點時，按步驟(3.4)處理；遍歷目標變量結點時，按步驟(3.5)處理；遍歷非變量結點時，無需任何處理；

(3.3)函數中嵌套控制語句的信息流樹進行遍歷，遍歷的過程中查看是否需要剪枝：遍歷目標變量結點時，按步驟(3.5)處理；遍歷源變量結點時，查看以它為源變量的目標變量結點：若有某一目標變量結點與其記錄的變量相同，則無需任何處理；否則，按步驟(3.4)處理；遍歷非變量結點時，無需任何處理；

(3.4)對源變量結點，考察已生成的函數信息流樹中的每一個變量結點，若其中某一變量結點是它父結點的右孩子，且與該源變量結點記錄的是同一變量，則分以下兩種情況處理：

①記錄的是局部變量，則將這一變量結點的父結點的左子樹復制，并替換該源變量結點；

②記錄的是全局變量，則將這一變量結點的父結點的左子樹復制，并作為該源變量結點的左子樹；

(3.5)對目標變量結點，考察已生成的函數信息流樹中的每一個變量結點，若其中某一變量結點是它父結點的右孩子，且與該結點記錄的是同一變量，則分以下三種情況處理：

①這一變量結點有左子樹，則用“nullstmt”類型結點替換它；

②這一變量結點無左子樹，且它的父結點和右孩子結點均為語句結點，則將它所在的語句樹段從樹中刪除；

③這一變量結點無左子樹，且它的父結點或右孩子結點不是語句結點，則僅將此變量結點從信息流樹中刪除；

(3.6)將經過剪枝處理的語句樹段連到函數信息流樹中；

(3.7)對函數中每一條語句，重復以上步驟，直到函數體結束；

(3.8)對得到的函數信息流樹考察其所有變量結點，若某一變量結點是它父結點的左孩子，且結點中記錄的是局部變量，則將該變量結點從樹中刪除；

(3.9)對得到的函數信息流樹考察其每一個語句樹段，對簡單語句樹段，按步驟(10)處理；對嵌套控制語句樹段，按步驟(11)處理；

(3.10)對簡單語句樹段，若其中某一變量結點是它父結點的右孩子，且它記錄的是局部變量，則分以下兩種情況處理：

①這一變量結點的父結點和右孩子結點均為語句結點，則將此樹段從信息流樹中刪除；

②這一變量結點的父結點或右孩子結點是變量結點，則僅將此結點從語句樹段中刪除；

(3.11)對嵌套控制語句樹段，若其中某一變量結點是它父結點的右孩子，且它記錄的是局部變量，則分以下兩種情況處理：

①這一變量結點的父親結點和右孩子結點都不是變量結點，則用null類型結點代替此結點；

②這一變量結點的父親結點或右孩子結點是變量結點，則僅將此右子樹結點從語句樹段中刪除。

6、根據權利要求1所述的分析方法，其特征在于，所述步驟(4)中，由函數信息流樹生成信息流向圖的方法如下：

(4.1)信息流樹線索化

在構造語句樹段時，令源變量結點的右子樹指針始終指向其后生成的目標變量或null類型結點，并令目標變量結點的右子樹指針也始終指向其后生成的結點；

(4.2)遍歷線索化的信息流樹，生成信息流向圖

①遍歷語句樹段尋找目標變量的過程：

a)對樹中某一語句樹段中的一個源變量結點，設有一指針Q，令其指向該源變量結點的右指針指向的結點；

b)如果Q指向結點是變量類型結點，表示該結點記錄的是目標變量，找到一條信息流，將信息流信息寫入信息流向圖中；

c)若此結點左指針不為空，則Q指向其左指針指向的結點，跳至步驟b)；若其左指針為空，則Q指向其右指針指向的結點。若Q為空，或Q指向結點為語句結點，或Q指向結點與源變量結點不在同一語句結點下，則此次遍歷結束；

d)如果Q指向結點是語句類型結點，則Q指向它的右指針指向的結點，跳至步驟b)；

e)如果Q指向結點是null類型結點，表示則Q指向它的左子樹結點，跳至步驟b)；

②尋找源變量結點過程

設P為指向信息流樹中某一源變量結點的指針，假設根據上述遍歷語句樹段中目標變量結點的過程，已經找出了所有以P指向結點為源變量的信息流的目標變量結點，接下來要找到樹中下一個源變量結點，進行遍歷，則在樹中尋找下一個源變量結點的過程如下：

a)如果P的左指針不為空，則P指向它的左指針指向的結點，此結點即為要找的下一個源變量結點，尋找過程結束；

b)如果P的左指針為空，則P指向它的右指針指向的結點；

c)跳至第f)步，直至P的左指針不為空；

d)指向它的左指針指向的結點；

e)如果P指向結點是語句結點，則P指向它的左指針指向的結點，此結點即為要找的下一個源變量結點，尋找過程結束。