[發(fā)明專利]基于關(guān)聯(lián)規(guī)則挖掘的不可達(dá)路徑檢測方法

有效

• 申請?zhí)枺?/td>: 201210501664.7
• 申請日: 2012-11-30
• 公開（公告）號: CN102968375A
• 公開（公告）日: 2013-03-13
• 發(fā)明（設(shè)計）人: 姜淑娟;韓寒;張艷梅;袁冠
• 申請（專利權(quán)）人: 中國礦業(yè)大學(xué)
• 主分類號: G06F11/36
• 分類號: G06F11/36
• 代理公司: 南京知識律師事務(wù)所 32207
• 代理人: 高桂珍

技術(shù)領(lǐng)域

本發(fā)明涉及一種軟件測試中的不可達(dá)路徑檢測方法，尤其是基于關(guān)聯(lián)規(guī)則挖掘的不可達(dá)路徑檢測方法。

背景技術(shù)

軟件測試是提高軟件質(zhì)量和可靠性的重要手段，同時也是一項昂貴的、乏味的、耗費人力的工作，它在軟件開發(fā)中占據(jù)了50%左右的耗費。如果這個過程能夠被自動地執(zhí)行，這勢必會縮短軟件的開發(fā)時間，同時也會提高軟件的質(zhì)量，從而增強(qiáng)軟件的市場競爭力。

很多軟件測試問題都可以歸結(jié)為面向路徑測試數(shù)據(jù)生成的問題，而不可達(dá)路徑的存在是面向路徑測試數(shù)據(jù)生成中的一個具有挑戰(zhàn)性的問題，沒有輸入數(shù)據(jù)能經(jīng)過這些不可達(dá)路徑，它會導(dǎo)致測試數(shù)據(jù)生成階段大量人力、財力的浪費，給測試帶來很大的困難。實驗結(jié)果表明，在一個復(fù)雜的程序中存有一定數(shù)量的不可達(dá)路徑，不可達(dá)路徑的檢測是一個不可判定的問題，路徑的可達(dá)性直接影響著測試的效率和充分性，有效地檢測到這些不可達(dá)路徑不僅能夠節(jié)約測試資源，而且能提高測試效率。

分支相關(guān)性的存在是不可達(dá)路徑的主要起因，確定分支的相關(guān)性在不可達(dá)路徑的檢測中發(fā)揮著十分重要的作用，對其進(jìn)行深入研究具有十分重要的意義。然而，分支相關(guān)性的確定是一項困難的工作，現(xiàn)有的方法大多無法及時、準(zhǔn)確地得到分支語句間的相互關(guān)系，其中，靜態(tài)分析方法復(fù)雜度高，分支節(jié)點覆蓋率低，無法與實際工程相結(jié)合，而動態(tài)分析方法則花費代價大。

發(fā)明內(nèi)容

為了解決現(xiàn)有的不可達(dá)路徑檢測方法不能有效檢測不可達(dá)路徑的問題，本發(fā)明提供一種基于關(guān)聯(lián)規(guī)則挖掘的不可達(dá)路徑檢測方法，該檢測方法有效地將靜態(tài)分析方法和動態(tài)分析技術(shù)的優(yōu)勢結(jié)合起來，既避免了使用純靜態(tài)分析方法分支節(jié)點覆蓋率低、復(fù)雜度高的缺陷，又彌補(bǔ)了使用動態(tài)分析方法收集動態(tài)信息花費代價大的問題，將關(guān)聯(lián)規(guī)則挖掘用于分支相關(guān)性的確定有著較大的優(yōu)勢和較高的效率，該方法能夠準(zhǔn)確地檢測出不可達(dá)路徑，有效地提高了軟件測試的效率。

本發(fā)明解決其技術(shù)問題所采用的技術(shù)方案是：該基于關(guān)聯(lián)規(guī)則挖掘的不可達(dá)路徑檢測方法包括獲取數(shù)據(jù)集、基于關(guān)聯(lián)規(guī)則挖掘的分支相關(guān)性的確定及不可達(dá)路徑的檢測。

（1）獲取數(shù)據(jù)集

首先采用靜態(tài)分析技術(shù)，利用Soot對程序進(jìn)行預(yù)處理，構(gòu)建程序的控制流圖、控制樹及蘊(yùn)含樹，然后設(shè)計搜索算法找出具有控制關(guān)系的分支節(jié)點序列集U。對于?u_i∈U，采用動態(tài)分析技術(shù)，通過JDI監(jiān)聽序列u_i中各個分支節(jié)點n_i1,?n_i2,?…,?n_ik的執(zhí)行情況，在輸入域內(nèi)隨機(jī)獲取N個抽樣輸入向量，要求當(dāng)程序輸入每個抽樣向量時n_i1,?n_i2,?…,?n_ik全部執(zhí)行，若存在某節(jié)點n_im不執(zhí)行，則換取其它抽樣值，直到所有的分支節(jié)點都執(zhí)行。

對于?u_i∈U，為了提升算法的效率，我們僅記錄并分析各分支節(jié)點的信息，通過soot分析當(dāng)程序輸入抽樣值I_ij時各分支節(jié)點的取向(T/F)，從而得到抽樣值I_ij對應(yīng)的分支取值序列p_ij，依此類推，獲取N個抽樣值的分支取值序列集S_i。最終分支序列集U將得到一個分支取值序列集的集合S，即

其中，p_ij是當(dāng)程序輸入抽樣值I_ij時u_i中各分支節(jié)點的取值序列，p_ij中的每個元素取值為T/F。

在介紹本步的具體算法之前，先給出如下定義：

循環(huán)節(jié)點：對于節(jié)點n，若?m，且m在蘊(yùn)含樹和控制樹中皆是N的子孫節(jié)點，則可認(rèn)為節(jié)點n為循環(huán)節(jié)點。

控制樹主干：由出口節(jié)點及其在控制樹中的所有祖先節(jié)點構(gòu)成的序列。