[發明專利]一種程序不可達路徑的自動檢測方法

在審

• 申請號: 201510843266.7
• 申請日: 2015-11-26
• 公開（公告）號: CN105446881A
• 公開（公告）日: 2016-03-30
• 發明（設計）人: 唐鄭熠;王金水;薛醒思;洪茂雄;胡文瑜;劉建華
• 申請（專利權）人: 福建工程學院
• 主分類號: G06F11/36
• 分類號: G06F11/36
• 代理公司: 北京市商泰律師事務所 11255
• 代理人: 王曉彬

技術領域

本發明屬于軟件測試領域，具體地，本發明涉及一種程序不可達路徑的自動檢測方法。

背景技術

術語解釋：

控制流圖:控制流圖(ControlFlowGraph)是程序語句邏輯執行順序的圖形化表達方式，簡稱為CFG。CFG包括節點和有向邊兩類元素：節點表示程序中的語句，并且有唯一的入口節點與出口節點；邊表示節點之間的順序關系。

程序路徑:是指由CFG中的節點構成的一個序列，若該序列的首節點為入口節點，末節點為出口節點，則該路徑稱為完整路徑。

不可達路徑:是指在任何情況下都不會出現的程序路徑。

軟件測試是軟件質量保障的重要手段，需要耗費大量的人力與物力。統計數據表明，軟件測試的開銷占到了軟件開發總成本的60％以上。軟件測試的自動化是提高軟件測試質量、降低成本、提高效率的一個重要途徑，因此被學術界與工業界廣泛地關注與研究。大體上，軟件測試可以分為功能測試與結構測試，后者是指對程序的內部邏輯結構進行測試，以判定程序的各條路徑是否能夠滿足需求。然而充分覆蓋程序的測試是難以達成的，因為即使是并不復雜的程序段，也會由于分支、循環結構的存在，導致產生規模巨大的路徑空間。因此，結構測試的一個重要研究領域，就是解決面向程序路徑的測試數據生成問題。而不可達路徑的檢測，則是其中的一個重要研究熱點。所謂的程序不可達路徑，是指在任何輸入下，都不會被執行的程序路徑。程序不可達路徑的存在，會導致在生成測試數據時，產生大量的無效測試數據，從而在測試執行時浪費大量的人力與物力，從而大大影響到測試的效率。因此，不可達路徑的檢測不僅能夠降低測試成本，還能夠有效提高測試效率，一直以來都是軟件測試領域的一個研究熱點。

程序中所存在的不可達路徑是代碼冗余的一種表現形式，Liverpool大學的Yates與Malevris兩位學者，通過實驗證明了在大型軟件系統中通常都會包含有10-25％的冗余代碼。不可達路徑的檢測問題已經被證明是一個不可判定問題，因此所有的檢測方法都是非完備的，即不存在能夠檢測出所有不可達路徑的算法。目前，檢測程序不可達路徑的方法，可以分為靜態檢測與動態檢測兩類。

1.靜態檢測技術

靜態檢測技術可依據原理，分為兩類：

●基于路徑條件可滿足性的方法：是指針對所有的程序路徑，通過對滿足路徑條件的謂詞組合進行求解，依據解的存在性來判定路徑的可達性。這類方法具有較高的復雜度。

●基于分支相關性的方法：是指通過對分支語句進行相關性分析的手段，來檢測不可達路徑。

在第一類技術中，典型的方法，是抽取程序的每條路徑的分支謂詞，并規約為一個方程組，通過求解方程組是否有解來判定路徑是否可達。然而這類方法具有較高的復雜性，并且缺乏表達數組、結構體等復合數據類型的能力。此外，還有一些類似的方法：使用區間算術規約程序路徑，但這類方法在處理條件謂詞中的非線性表達式時，效率較為低下；使用代碼模式檢測程序分支，并通過符號執行技術進行路徑的可達性檢測，但這類方法的通用性受到代碼模式的約束；使用變量的抽象取值范圍規約程序的狀態條件，通過判斷路徑的變量取值范圍來判定路徑是否可達，但這類方法不能很好地處理復合的分支條件。

程序分支之間的相關性是產生不可達路徑的主要原因，在具有一定復雜度的程序中，9-40％的分支語句會存在相關系。但基于相關性分析的檢測方法由于無法分析結構復雜的分支條件，因此難以獲得令人滿意的節點覆蓋率。該類方法的代表性工作包括：在傳統的數據流分析中加入了分支相關性分析，從而提高傳統數據流分析的精度；通過判斷賦值語句、分支語句之間的沖突性來識別不可達路徑，然而該方法卻缺乏處理循環結構的能力；通過對控制流與數據流的靜態分析，來確定相關性語句，并進而判定不可達路徑，其特點是能夠處理函數調用關系。

2.動態檢測技術

動態檢測技術是指在進行路徑測試的過程中，依據測試用例生成的復雜度來判定待測試的路徑是否可達。然而動態檢測技術的檢查代價通常較大，并且無法保證檢測結果的絕對準確，具有較強的不確定性。

常見的方法包括：使用基于啟發式策略的方法檢測不可達路徑，其依據是可達路徑的部分屬相同這一原理，從而通過檢測試數據的生成軌跡來實現路徑可達性的檢測；使用語義更新技術，從程序語義上來排除程序中的不可達路徑；利用遺傳算法來檢測不可達路徑，為了更好地引導搜索，該類方法會通過融合控制流圖的信息，進行適應度函數的設計。

現有的技術方案，存在以下的問題：

(1)復雜度較高，檢測效率較低。