鬼佬大哥大
  • / 8
  • 下載費用:30 金幣  

基于編程模式和模式匹配的漏洞聚類方法.pdf

摘要
申請專利號:

CN201510443533.1

申請日:

2015.07.27

公開號:

CN105045715A

公開日:

2015.11.11

當前法律狀態:

授權

有效性:

有權

法律詳情: 授權|||實質審查的生效IPC(主分類):G06F 11/36申請日:20150727|||公開
IPC分類號: G06F11/36 主分類號: G06F11/36
申請人: 電子科技大學
發明人: 張小松; 宋珺; 牛偉納; 卓中流; 陳瑞東; 孫恩博; 戴中印; 黃金
地址: 611731四川省成都市高新區(西區)西源大道2006號
優先權:
專利代理機構: 電子科技大學專利中心51203 代理人: 李明光
PDF完整版下載: PDF下載
法律狀態
申請(專利)號:

CN201510443533.1

授權公告號:

||||||

法律狀態公告日:

2018.01.12|||2015.12.09|||2015.11.11

法律狀態類型:

授權|||實質審查的生效|||公開

摘要

本方法用于軟件脆弱性分析,屬于計算機程序安全領域。本發明是一種基于編程模式和模式匹配的漏洞發現方法,可以將程序內所有函數進行統一分析,根據每個函數中出現的不同的關鍵詞、API符號,將每個函數映射到向量空間,并利用矩陣分析方法提取出這些函數中占據主導地位的編程模式,以及每個函數最傾向的編程模式。通過計算歐幾里得距離,將編程模式相近的函數發現并聚類為一類,并藉此發現潛在的、和已知漏洞相似的漏洞。

權利要求書

1.一種基于編程模式和模式匹配的漏洞聚類的方法,具體包括以下步驟:
步驟1.編程模式提取;記已知存在漏洞的函數為函數F,對于一個包含(Cf—1)個函數的
程序源代碼,進行如下步驟的操作:
步驟1-1:將函數F置于所述程序源代碼中,此時程序源代碼包含有Cf個函數,統計插
入函數F后的程序源代碼中出現的不同關鍵詞并記其總數量為Cn,所述關鍵詞類型包括保留
字、函數名、變量名;
步驟1-2:為該程序源代碼的每個函數創建一個維度為Cn的列向量Mi,i=1,2,…Cf,列向
量Mi中的每個元素與步驟1-1所統計的不同關鍵詞一一對應,若列向量Mi對應的函數中包
含有相應關鍵詞,則列向量Mi中相應位置的元素值記為1,否則記為零;將創建的Cf個列向
量合并為一個Cn×Cf的矩陣M;
步驟1-3:選取特征數值D,0<D≤Cf;
步驟1-4:對矩陣M進行截斷奇異值分解M=USVT,并取前D個奇異值,分解之后得到
矩陣U、S、V;其中,矩陣U為Cn*D階矩陣,矩陣S為D*D階對角矩陣,矩陣V為Cf*D
階矩陣;
矩陣V的每一個行向量與所述程序源代碼中的每一個函數一一對應,即矩陣V的每一個
行向量即代表所述程序源代碼中的一個函數的模式塊,由此得到Cf個與程序源代碼的函數一
一對應的模式塊向量,提取其中與函數F對應的模式塊向量;
步驟2.模式匹配聚類;對于步驟1中提取出的Cf個函數的模式塊向量,進行如下步驟的
操作:
步驟2-1:針對程序源代碼中除函數F之外的函數所對應的模式塊向量,計算每個模式塊
向量Fi與函數F的模式塊向量的歐幾里得距離;
步驟2-2:設定歐氏距離閾值δ,將與函數F的模式塊向量的歐幾里得距離小于等于閾值
δ的模式塊向量對應的函數提取出來,即將程序源代碼中與帶有漏洞的函數F具有較近歐氏
距離即較高相似度的函數聚類為一類,供進一步分析。
2.根據權利要求1所述的基于編程模式和模式匹配的漏洞聚類的方法,其特征在于,所
述歐幾里得距離S(Fi,F)的具體公式如下:
S ( F i , F ) = Σ j = 1 D ( a j - b j ) 2 ]]>
其中,向量(a1a2…aD)、(b1b2…bD)分別為模式塊向量Fi及函數F的模式塊向量。

說明書

基于編程模式和模式匹配的漏洞聚類方法

技術領域

本發明屬于計算機程序安全領域,提供一種基于編程模式和模式匹配的漏洞聚類方法。

背景技術

脆弱性(Vulnerability)是系統具體實現或安全策略上存在的缺陷和不足。軟件脆弱性的存
在給系統服務的可持續性和數據的安全性帶來了巨大的危害,是威脅信息系統安全的主要因
素。黑客、蠕蟲病毒和木馬等都利用安全脆弱性來實現對計算機系統的入侵或自身傳播。

計算機系統在社會生活中的應用日益廣泛,安全脆弱性的數目呈迅速遞增之勢,從發現
到首次被利用的時間間隔越來越短,安全漏洞的風險等級節節升高。如何應對安全漏洞給信
息系統帶來的威脅,已成了計算機安全領域的重大問題之一。除了利用己知脆弱性,有的黑
客善于挖掘并利用一些尚未公布的脆弱性以達到他們不可告人的目的,而相比于此,安全研
究者們在脆弱性研究工作的影響方面顯得被動和滯后。所以加大對脆弱性的研究力度是非常
有必要的,以便對各類脆弱性采取更為主動合理的處理方式。如何來檢測一個現有軟件的安
全性是解決安全問題的頭等大事。從問題的源頭就開始關注安全,越早發現軟件存在的脆弱
性問題,那么造成的損失就越小。因此,對計算機軟件脆弱性分析方法的研究具有重要的理
論和實用價值。

當前,根據分析對象不同可將脆弱性分析方法分為兩類:源代碼分析和二進制分析。源
代碼分析是對程序的源代碼進行手動或自動的代碼審計,根據審查人員的經驗來審查代碼中
是否包含常見已知漏洞或者潛在安全缺陷;二進制分析是在不運行程序的情況下對軟件匯編
代碼進行分析,以發現一些潛在的漏洞,它直接反映了機器執行程序的實際過程,比源代碼
分析更底層但更難以分析,需要通過特定的逆向平臺對軟件程序進行反匯編,得到相應的反
匯編文本。

專利申請“一種基于屬性提取的軟件漏洞挖掘系統及方法”(申請號:CN201410577779)
提供一種基于屬性提取的軟件漏洞挖掘系統及方法,包括以下步驟:提取待測軟件關鍵代碼
的步驟;對待測軟件在虛擬機環境中執行,并采用虛擬機故障注入引擎與關鍵代碼進行測試
交互,記錄測試結果;將測試結果結合挖掘經驗知識庫進行推理。該發明的不足在于,漏洞
發掘非常依賴于經驗知識庫的完備,若知識庫不包含相關信息,則難以檢測出新類型的漏洞。

專利申請“一種用于漏洞發掘的動態符號執行路徑搜索方法”(申請號:CN201410230479)
提供如下方法,在使用動態符號執行對被測程序的可能執行路徑進行搜索的過程中,標記實
際執行被測程序時觸發漏洞的路徑,對于路徑探索過程中生成的每一個新的測試用例,計算
該測試用例執行路徑與上次觸發漏洞路徑的相關度r,并以此計算該測試用例對應執行路徑的
權重分數score,在下次執行測試時選擇score值最大的測試用例執行。該發明的不足在于,
漏洞發掘依賴于合適的測試用例的設計,難以設計出適用于不同程序類型的一組用例,故難
以保證效率和準確性。

發明內容

本發明主要解決的技術問題在于,為了更有效率、更準確的比較程序漏洞代碼的相似性,
以更好的將代碼進行聚類,并發現潛在的漏洞代碼,提出了這樣一種漏洞聚類方法。本發明
主要研究源代碼分析,屬于靜態分析方法。

本發明涉及的相關術語解釋如下:

編程模式:在本發明中,編程模式是指,反應了一個函數的源代碼中,函數名、變量名、
保留字三者組合而成的向量,可以從一定程度上反應該函數的功能;

模式塊向量:在本發明中,模式塊向量是指,反應了一個函數對于指定多種編程模式的“傾
向”程度的向量,這是根據數學方法得到的結果;

截斷奇異值分解:奇異值分解是矩陣特征值分解在非方針情況下的推廣,用來計算描述
一般矩陣重要特征的分析方法;很多情況下,前面一小部分的奇異值之和占據了所有奇異值
總和的絕大部分,故可以截斷前一部分的奇異值來過濾“噪音”,得到矩陣重要的信息,這就
是截斷奇異值分解;

歐幾里得距離:是一個通常采用的距離定義,指在m維空間中兩個點之間的真實距離,
或者向量的自然長度(即該點到原點的距離);

模式匹配:在本發明中,模式匹配是指,通過計算若干函數的模式塊與目標函數的模式
塊的歐幾里得距離,找到與目標函數模式塊最相近的函數。

本發明具體采用如下技術方案:

一種基于編程模式和模式匹配的漏洞聚類的方法,其流程圖如圖1所示,具體包括以下
步驟:

步驟1.編程模式提取,其流程如圖2所示;記已知存在漏洞的函數為函數F,對于一個
包含(Cf-1)個函數的程序源代碼,進行如下步驟的操作:

步驟1-1:將函數F置于所述程序源代碼中,此時程序源代碼包含有Cf個函數,統計插
入函數F后的程序源代碼中出現的不同關鍵詞并記其總數量為Cn,所述關鍵詞類型包括保留
字、函數名、變量名;

步驟1-2:為該程序源代碼的每個函數創建一個維度為Cn的列向量Mi,i=1,2,…Cf,列向
量Mi中的每個元素與步驟1-1所統計的不同關鍵詞一一對應,若列向量Mi對應的函數中包
含有相應關鍵詞,則列向量Mi中相應位置的元素值記為1,否則記為零;將創建的Cf個列向
量合并為一個Cn×Cf的矩陣M;

步驟1-3:選取特征數值D,0<D≤Cf,數值D代表之后步驟從源代碼中提取出的模式
種類的數量的最大值;D值過小則不能提供足夠的精度,過大則不能提供更高的精度;

步驟1-4:對矩陣M進行截斷奇異值分解M=USVT,并取前D個奇異值,分解之后得到
矩陣U、S、V;其中,矩陣U為Cn*D階矩陣,矩陣S為D*D階對角矩陣,矩陣V為Cf*D
階矩陣;

矩陣V的每一個行向量與所述程序源代碼中的每一個函數一一對應,即矩陣V的每一個
行向量即代表所述程序源代碼中的一個函數的模式塊,由此得到Cf個與程序源代碼的函數一
一對應的模式塊向量,提取其中與函數F對應的模式塊向量;

步驟2.模式匹配聚類,其流程圖如圖3所示;對于步驟1中提取出的Cf個函數的模式塊,
進行如下步驟的操作:

步驟2-1:針對程序源代碼中除函數F之外的函數所對應的模式塊向量,計算每個模式塊
向量Fi與函數F的模式塊向量的歐幾里得距離;

步驟2-2:設定歐氏距離閾值δ,將與函數F的模式塊向量的歐幾里得距離小于等于閾值
δ的模式塊向量對應的函數提取出來,即將程序源代碼中與帶有漏洞的函數F具有較近歐氏
距離即較高相似度的函數聚類為一類,供進一步分析。

本發明的有益效果:

對于一個開放源代碼的程序,當已知其中某個函數存在漏洞時,利用本發明方法可以將
包括該漏洞函數在內的所有函數進行統一分析,根據每個函數中出現的不同的關鍵詞、API
符號,將每個函數用向量表示出來,并利用矩陣分析方法提取出這些函數中占據主導地位的
編程模式,以及每個函數最傾向的編程模式;并通過計算歐幾里得距離,將編程模式相近的
函數找出來、聚類為一類;本方法不僅可以將相似函數聚類,并且可以藉此發現潛在的、和
已知漏洞相似的漏洞函數。

附圖說明

圖1為本發明的總體工作流程圖

圖2為模式抽取模塊的工作流程圖

圖3為模式匹配模塊的工作流程圖

具體實施方式

本具體實施方式提供一種基于編程模式和模式匹配的漏洞聚類的方法,其流程圖如圖1
所示,具體包括以下步驟:

步驟1.編程模式提取,其流程如圖2所示;記已知存在漏洞的函數為函數F,對于一個
包含(Cf—1)個函數的程序源代碼,進行如下步驟的操作:

步驟1-1:將函數F置于所述程序源代碼中,此時程序源代碼包含有Cf個函數,統計插
入函數F后的程序源代碼中出現的不同關鍵詞并記其總數量為Cn,所述關鍵詞類型包括保留
字、函數名、變量名;

步驟1-2:為該程序源代碼的每個函數創建一個維度為Cn的列向量Mi,i=1,2,…Cf,列向
量Mi中的每個元素與步驟1-1所統計的不同關鍵詞一一對應,若列向量Mi對應的函數中包
含有相應關鍵詞,則列向量Mi中相應位置的元素值記為1,否則記為零;將創建的Cf個列向
量合并為一個Cn×Cf的矩陣M;

步驟1-3:選取特征數值D,0<D≤Cf,數值D代表之后步驟從源代碼中提取出的模式
種類的數量的最大值;D值過小則不能提供足夠的精度,過大則不能提供更高的精度;

步驟1-4:對矩陣M進行截斷奇異值分解,并取前D個奇異值,分解之后得到矩陣U、
S、V:


其中,矩陣U為Cn*D階矩陣,矩陣S為D*D階對角矩陣,矩陣V為Cf*D階矩陣;矩陣U
的每一列記載了一種主要的編程模式共計D種,在某種程度上顯示該模式里某個關鍵字的使
用頻率;矩陣S的對角線上的每個奇異值反映了矩陣U中每個編程模式的重要程度;矩陣V
的每一行反映了某個函數對D種編程模式的“傾向”,“傾向”越相近的函數,則它們越有可能
屬于一類;

矩陣V的每一個行向量與所述程序源代碼中的每一個函數一一對應,即矩陣V的每一個
行向量即代表所述程序源代碼中的一個函數的模式塊,由此得到Cf個與程序源代碼的函數一
一對應的模式塊向量,提取其中與函數F對應的模式塊向量;

步驟2.模式匹配聚類,其流程圖如圖3所示;對于步驟1中提取出的Cf個函數的模式塊,
進行如下步驟的操作:

步驟2-1:針對程序源代碼中除函數F之外的函數所對應的模式塊向量,計算每個模式塊
向量Fi與函數F的模式塊向量的歐幾里得距離S(Fi,F),具體公式如下:

S ( F i , F ) = Σ j = 1 D ( a j - b j ) 2 ]]>

其中,向量(a1a2…aD)、(b1b2…bD)分別為模式塊向量Fi及函數F的模式塊向量;

步驟2-2:設定歐氏距離閾值δ,將與函數F的模式塊向量的歐幾里得距離小于等于閾值
δ的模式塊向量對應的函數提取出來,即將程序源代碼中與帶有漏洞的函數F具有較近歐氏
距離即較高相似度的函數聚類為一類,供進一步分析。

關 鍵 詞:
基于 編程 模式 匹配 漏洞 方法
  專利查詢網所有資源均是用戶自行上傳分享,僅供網友學習交流,未經上傳用戶書面授權,請勿作他用。
關于本文
本文標題:基于編程模式和模式匹配的漏洞聚類方法.pdf
鏈接地址:http://www.wwszu.club/p-6401508.html
關于我們 - 網站聲明 - 網站地圖 - 資源地圖 - 友情鏈接 - 網站客服客服 - 聯系我們

[email protected] 2017-2018 zhuanlichaxun.net網站版權所有
經營許可證編號:粵ICP備17046363號-1 
 


收起
展開
鬼佬大哥大