[發明專利]以布爾表達式的求值序列為謂詞單元的軟件錯誤定位方法

無效

• 申請號: 201210002136.7
• 申請日: 2012-01-05
• 公開（公告）號: CN102541741A
• 公開（公告）日: 2012-07-04
• 發明（設計）人: 張震宇;高文超
• 申請（專利權）人: 中國科學院軟件研究所
• 主分類號: G06F11/36
• 分類號: G06F11/36
• 代理公司: 北京君尚知識產權代理事務所(普通合伙) 11200
• 代理人: 俞達成

技術領域

本發明屬于軟件測試技術領域，涉及一種軟件錯誤定位方法，特別提供了一種以布爾表達式的求值序列為謂詞單元的軟件錯誤定位方法，可應用于動態的軟件錯誤定位。

背景技術

為了修改軟件中存在的錯誤，對錯誤進行定位是必要的步驟之一。軟件測試中的錯誤定位是最困難、最耗時的任務，使用一種自動化的錯誤定位技術來協助程序員找到錯誤是解決軟件測試問題的趨勢。

學術界早在十年前已經提出了自動化錯誤定位的概念。一種流行的方法是通過查找與程序執行結果相關度高的程序語句來定位程序錯誤。這類方法稱為“語句級別的統計錯誤定位方法”，它關注的是程序語句在成功測試用例和失敗測試用例執行中的執行信息的差異。要應用此類分析技術，必須具備兩個關鍵因素：(1)一個(或一組)用于參考的程序執行信息特征，用以提供分析語句可疑度的信息；(2)一個評估函數，用以衡量語句的可疑度。Jones等人于2002年基于此類方法進行了研究。

還有一種方法是將特定的程序語句(例如布爾表達式)視作謂詞，將謂詞作為程序實體，進行可疑度評估。此類方法對比每個謂詞在成功測試用例執行中的求值和在失敗測試用例執行中的求值。二者的差別越大，說明這個謂詞與程序錯誤的相關度越高。按照謂詞可疑度對謂詞進行排序，就可以獲得與程序錯誤最相關的謂詞，把謂詞位置映射回程序中，就可以預測程序錯誤的位置。由于這種方法只需要對選定的謂詞的執行信息進行采樣，而不必采集所有語句的執行信息，所以可以減輕插樁對程序行為帶來的影響，降低采集執行信息的復雜度，同時避免暴露太多的代碼，降低信息泄露的風險。這里，插樁是指程序插樁技術，它在保證被測程序原有邏輯完整性的基礎上在程序中插入探針，通過探針的執行捕獲程序運行數據。

Liblit等人(2005年)，柳超等人(2006年)，Chilimbi等人(2009年)分別就此種方法提出了謂詞可疑度的評估函數。舉例來說，Liblit等人提出的CBI方法衡量謂詞在失敗測試用例中被評估成“true”的可能性，并與其整個測試用例集中的相應可能性進行對比。柳超等人提出的SOBER方法通過對比一次執行中謂詞被評估成“true”和“false”的比例——求值偏差——來預測和程序錯誤相關的謂詞(一個謂詞的求值偏差指的是在一次執行中這個謂詞被評估成“true”的比例)。

上述基于謂詞的統計錯誤定位技術雖然解決了收集所有語句執行信息而造成的數據量龐大的問題，然而粒度較粗，并沒有充分利用能夠收集到的謂詞執行信息。隨著軟件復雜度的增加，復合型布爾表達式經常被用作謂詞，將組成復合表達式的原子型表達式(如“a＞3&&b＜10”中的子句“a＞3”和“b＜10”)用作謂詞是很自然的想法。然而，常見編程語言(例如C，C++，Java等)的短路求值機制使得對原子布爾表達式的求值變得困難。含有“&&”和“||”操作符的操作數表達式，在進行求值時，只要最終的結果已經可以確定是true或false，求值過程便告終止，這就稱之為短路求值。短路求值機制是關系操作符的重要屬性，也是確定編程語言中表達式求值的規則。舉例來說，在復合型布爾表達式“a＞3&&b＜10”中，當原子型布爾表達式“a＞3”求值為“false”時，對原子型布爾表達式“b＜10”將不再求值，因為該復合型布爾表達式的求值已經確定為“false”。因此，是否對每個原子型布爾表達式都進行求值是不可預測的。同時，由于存在有例如“p！＝3&&p[0]＞0”形式的復合型布爾表達式，對各個原子型布爾表達式進行強行求值也是不安全的。由于種種原因，將原子型布爾表達式直接用作謂詞變得不可行。

基于謂詞的統計錯誤定位方法使用較粗粒度的信息，導致算法準確度降低，從而影響實用性，有必要尋找更細粒度的謂詞以解決這個問題。

發明內容

本發明的目的在于克服現有技術中存在的上述問題，提供一種以布爾表達式的求值序列為謂詞單元的軟件錯誤定位方法。

本發明的方法，其步驟包括：

1、提取待測軟件程序中的各布爾表達式，得到其對應的布爾表達式的求值序列；

2、將上述布爾表達式的求值序列作為謂詞，收集各謂詞在程序執行中的執行信息，所述執行信息包括執行結果(true或false)和次數；

3、根據上述各謂詞的執行信息，計算各謂詞的可疑度，根據可疑度確定與軟件錯誤相關的謂詞；

4、根據上述與軟件錯誤相關的謂詞的位置定位軟件錯誤位置。