[發明專利]一種基于樹結構的密碼算法邏輯表達式識別方法

有效

• 申請號: 201210196764.3
• 申請日: 2012-06-14
• 公開（公告）號: CN102799806A
• 公開（公告）日: 2012-11-28
• 發明（設計）人: 蔣烈輝;尹青;李繼中;謝耀濱;何紅旗;常瑞;劉鐵銘
• 申請（專利權）人: 中國人民解放軍信息工程大學
• 主分類號: G06F21/00
• 分類號: G06F21/00
• 代理公司: 鄭州大通專利商標代理有限公司 41111
• 代理人: 白毅明

1.一種基于樹結構的密碼算法邏輯表達式識別方法，其特征是：通過下述步驟識別密碼算法及密碼函數：

1）通過研究不同密碼算法的實現原理，抽取出密碼算法實現中所使用的邏輯表達式LE，采用樹形結構存儲到密碼算法邏輯表達式特征數據庫T_character中；

2）對待識別的目標程序進行反匯編分析，得到目標程序的函數序列P<F₁,F₂…F_n>，對函數F_i進行基本塊內數據流分析，構建僅含有邏輯操作的抽象語法樹集合F_i<T₁,T₂…T_m>，即目標模式樹；其中i標識一個函數，m是抽象語法樹個數，n是函數個數；

3）根據密碼算法邏輯表達式特征數據庫T_characte，使用樹結構的匹配算法M(T_target,T_character)，對目標程序的函數F_i抽象語法樹集合進行匹配，并記錄匹配結果；

4）重復第3步，直到所有函數完成匹配；

5）對匹配結果進行梳理，標注的信息主要有：函數名、密碼算法名稱、邏輯表達式的內容、LE在文件中的偏移地址。

2.根據權利要求1所述的基于樹結構的密碼算法邏輯表達式識別方法，其特征是：采用模式樹構建算法PTCA構建密碼算法邏輯表達式特征數據庫T_character，具體流程如下：

步驟1：掃描邏輯表達式LE，記錄操作優先級最小的操作符OP_min，創建特征樹內部結點，并掛載在其父結點的相應位置，并把OP_min保存在內部結點中，OP_min把LP分成左、右兩個部分；

步驟2：左部若為操作數，則掛載在父結點相應位置；若為LE，則調用PTCA算法進行處理；

步驟3：右部若為操作數，則掛載在父結點相應位置；若為LE，則調用PTCA?算法進行處理；

步驟4：遍歷完所有邏輯操作符，算法結束。

3.根據權利要求1或2所述的基于樹結構的密碼算法邏輯表達式識別方法，其特征是：在對目標代碼反匯編的基礎上，以函數為基本粒度進行局部數據流分析，構建目標模式樹，具體流程如下：

步驟1：對目標代碼進行反匯編，結果記為P＝(f₁，f₂…f_n)；

步驟2：在函數f_i內掃描邏輯操作符，具有直接邏輯關系的操作聚合到一個模式樹中，函數f_i內的模式子樹集合為T_i=(t₁,t₂…t_m)；

步驟3：重復步驟2，直至所有函數被處理一遍，記錄下程序P的模式樹集合T＝(T₁,T₂…T_m)，算法結束。其中i標識一個函數，m是模式子樹個數，n是函數個數。

4.根據權利要求3所述的基于樹結構的密碼算法邏輯表達式識別方法，其特征是：在函數的模式子樹構建后，根據定義的密碼函數LE特征樹數據庫進行匹配，匹配過程分成兩個部分：內結點匹配和葉子結點匹配，基于樹結構的匹配算法TreeMatch（TargetTree，PatternTree，L）實現步驟如下：

步驟1：初始化識別結果Result、左子樹的識別結果L_result、右子樹的識別結果R_result分別為false；

步驟2：判斷目標樹T的根節點是否為葉子節點，若是則轉步驟3，若不是則轉步驟6；

步驟3：模式樹P的根節點是否為葉子節點，若不是則返回Result為false并結束，否則轉步驟4；

步驟4：判斷P和T的根節點操作數類型是否相同，若相同則把T的根葉子節點作為P的根葉子節點的副節點，并加入到關系序列L中，轉步驟5，否則返回?Result為false，結束；

步驟5：判斷P的根葉子節點是否有相同的節點信息，若不同，則返回Result為true，否則，取與P的根葉子節點相同節點的副節點N，并判斷T的根葉子節點是否與N相同，若相同，返回Result為true并結束，否則，返回Result為false并結束；

步驟6：判斷樹P的根節點是否為內部節點，若不是則返回Result為false并結束，若是則轉步驟7；

步驟7：判斷T和P的根節點運算符是否相同，若相同，轉步驟8，若不同，轉步驟9；

步驟8：以T的左子樹、P的左子樹、L為輸入參數，調用TreeMatch算法，返回結果為L_result，以T的右子樹、P的右子樹、L為輸入參數，調用TreeMatch算法，返回結果為R_result，若L_result和R_result都為真，則返回Result為true，結束；

步驟9：以T的左子樹、P、L為輸入參數，調用TreeMatch算法，返回結果為L_result，以T的右子樹、P、L為輸入參數，調用TreeMatch算法，返回結果為R_result，若L_result和R?result有一個為真，則返回Result為true，結束。?