[發明專利]一種新型分析信息流的方法

無效

• 申請號: 200910233881.0
• 申請日: 2009-10-23
• 公開（公告）號: CN102043925A
• 公開（公告）日: 2011-05-04
• 發明（設計）人: 鞠時光;李驍淳
• 申請（專利權）人: 鎮江雅迅軟件有限責任公司
• 主分類號: G06F21/22
• 分類號: G06F21/22;H04L29/06
• 代理公司: 暫無信息
• 代理人: 暫無信息

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

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

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

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

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

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

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

2.根據權利要求1所述的分析方法，其特征在于，所述掃描系統源代碼步驟中具體采用詞法分析程序對系統源代碼進行掃描。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(1)信息流樹線索化

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

(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指向它的左指針指向的結點，此結點即為要找的下一個源變量結點，尋找過程結束。