[發明專利]基于關聯規則挖掘的不可達路徑檢測方法

有效

• 申請號: 201210501664.7
• 申請日: 2012-11-30
• 公開（公告）號: CN102968375A
• 公開（公告）日: 2013-03-13
• 發明（設計）人: 姜淑娟;韓寒;張艷梅;袁冠
• 申請（專利權）人: 中國礦業大學
• 主分類號: G06F11/36
• 分類號: G06F11/36
• 代理公司: 南京知識律師事務所 32207
• 代理人: 高桂珍

1.基于關聯規則挖掘的不可達路徑檢測方法，該基于關聯規則挖掘的不可達路徑檢測方法包括獲取數據集、基于關聯規則挖掘的分支相關性的確定及不可達路徑的檢測，其特征在于，獲取數據集，首先采用靜態分析技術，利用Soot對程序進行預處理，構建程序的控制流圖、控制樹及蘊含樹，然后設計搜索算法找出具有控制關系的分支節點序列集U，對于?u_i∈U，采用動態分析技術，通過JDI監聽序列u_i中各個分支節點n_i1,?n_i2,?…,?n_ik的執行情況，在輸入域內隨機獲取N個抽樣輸入向量，要求當程序輸入每個抽樣向量時n_i1,?n_i2,?…,?n_ik全部執行，若存在某節點n_im不執行，則換取其它抽樣值，直到所有的分支節點都執行；基于關聯規則挖掘的分支相關性的確定，從數據集D_i中，找出所有滿足支持度大于等于最小支持度min_support的頻繁項集，我們采用FP-Growth算法進行挖掘，首先需要讀取數據集D_i，構造頻繁1-項集及FP-Tree，然后根據算法2在FP-Tree上進行頻繁項集的挖掘，算法2采用分而治之的方法，它將FP-Tree分解成一些條件模式庫CPB，每個CPB和一個頻繁1-項集相關聯，我們根據CPB構造其相應的條件FP-tree，然后再采用遞歸算法分別對這些條件FP-tree進行挖掘，從而得到所有的頻繁項集F(D_i,?min_support)；利用上一步得到的頻繁項集F(D_i,?min_support)來產生規則，如果某一規則的置信度大于等于最小置信度(min_confidence)，則該規則為關聯規則，頻繁項集{A,?B}產生的規則A????????????????????????????????????????????????B，每個關聯規則的生成為，?對于?f∈F(D_i,?min_support)，產生f的所有非空子集；?對于f的每一個非空子集v，若，則規則為關聯規則；不可達路徑的檢測，設n_i和n_j是程序中的兩個條件語句，如果經關聯規則挖掘后得到(n_i,?n_j)有T→T(或T→F)的相關性，則n_i的真分支和n_j的假(或真)分支構成沖突子路徑；同樣地，如果(n_i,?n_j)有F→T(或F→F)的相關性，則n_i的假分支和n_j的假(或真)分支構成沖突子路徑；對于任何一條路徑，若該路徑包含沖突子路徑，則它為不可達路徑。

2.基于關聯規則挖掘的不可達路徑檢測方法中的分支取值序列集的獲取算法，其特征在于，該算法采用逆向遍歷并結合遞歸算法來實現；算法首先從出口節點開始，對控制樹主干上的節點序列進行逆向的遍歷分析，并調用函數Son()對當前節點及其子節點進行分析，遍歷分析當前節點的子節點，根據循環節點的定義判定當前節點是否是循環節點，若當前節點為循環節點，則將該節點記錄下來，并結合遞歸算法遞歸當前子節點，遞歸結束后再次記錄當前節點；若當前節點為分支節點，則直接遞歸當前子節點，遞歸完成后，再根據其兄弟節點的存儲情況來選擇當前節點的記錄方式；若當前節點為葉子節點，則直接返回空值，無需記錄；當對控制樹主干上的所有節點遍歷完成后，可得到由具有控制關系的各個分支節點序列組成的序列集合U，依次對U中的每條序列進行抽樣執行分析，最終得到各個序列的分支取值序列集的集合S，算法結束。