一種基於程序動態依賴關係的軟體故障定位方法
2023-05-20 10:57:06
專利名稱：一種基於程序動態依賴關係的軟體故障定位方法
技術領域：
本發明涉及計算機軟體自動化調試技術，尤其涉及一種基於程序動態依賴關係的
軟體故障定位方法。
背景技術：
軟體調試，是軟體開發過程中發現和減少軟體缺陷的一個過程，通常始於程序出
現故障以後。軟體故障一般通過三個階段產生程式設計師在代碼中製造了一個缺陷，缺陷造成
了程序中的錯誤狀態，錯誤狀態進而引發了程序故障，它以可感知的外部錯誤的形式出現。
隨後，程式設計師會執行某個失敗的測試用例，使用調試器反覆設置斷點，觀察程序狀態直到錯
誤狀態的出現。然後推斷可能的感染源，定位缺陷位置並驗證，修正軟體缺陷。
當前，軟體中的某些缺陷或錯誤，可以通過改進軟體開發環境，靜態的探測原始碼
或動態的檢查對不變量的違反來輔助發現；而絕大多數錯誤，則只能依賴於開發人員的經
驗和直覺，通過人工的方式來發現。 人工審查代碼，以及在程序中插入輸出語句或斷言，單步執行跟蹤缺陷軌跡等方法的效率很低，軟體開發人員在調試上花費了大量的時間和精力——據統計大約要佔去工作的一半甚至更多，這也是軟體系統中的缺陷難以在開發過程中充分修復的一個重要原因。另外，調試需要對於程序的功能和實現有較深入的理解，是一件比較困難的工作，所以調試任務通常只能由程序的開發人員來完成，其他人員難以勝任，這樣一來就會影響軟體的開發速度。 手工調試已經難以適應軟體質量保證和快速開發的雙重要求。如果有自動化的調
試方法，可以根據測試用例的狀態信息，以及各種程序實體執行的覆蓋信息，指出軟體缺陷
在原始碼中可能存在的位置，無疑將極大的提高軟體生產率和軟體質量。 程序依賴關係反映了程序實體之間相互作用的關係。它包含兩種數據依賴關係
和控制依賴關係。數據依賴關係表示由於數據的定義和使用形成的實體之間的關係。通俗
的講，如果兩條語句存在數據依賴關係，當調換這兩條語句時，則會使得其中至少一條語句
中使用的變量的值不正確。控制依賴關係表示由於控制流引起的程序實體之間的關係。通
俗的講，如果一個謂詞表達式的值會影響到一條語句是否被執行，則語句控制依賴於謂詞
表達式。從程序是否被執行的角度，程序依賴關係又可以分為靜態依賴關係和動態依賴關
系兩種。靜態依賴關係顯示了實體間所有可能的相互作用關係，而動態依賴關係則表明了
某次執行中程序實體相互作用的情況。 在回歸測試，每日構建，測試驅動的開發等軟體開發的一些場景中，由於軟體版本的變更，經常會在原始碼中引入難以發現的缺陷。針對這些缺陷的調試工作會很頻繁和煩瑣。但同時，在這些場景中，程序的原始碼，一套測試組件的狀態信息和程序的動態依賴關係都是可以獲得的。因此，研究一種使用程序動態依賴關係和測試用例狀態信息的故障定位技術，對於提高軟體生產率和軟體質量，有著重要的意義。
發明內容
有鑑於此，本發明的主要目的在於提供一種基於程序動態依賴關係的軟體故障定位方法，通過搜集C語言執行時的軌跡信息，解析動態依賴關係，計算出可執行語句的可疑度，並將它們由大到小排列，以故障定位報告的形式給出，提高了調試的自動化程度，從而提升軟體的開發速度。 為達到上述目的，本發明的技術方案是這樣實現的 —種基於程序動態依賴關係的軟體故障定位方法，該方法包括 A.使用作用於連結時的優化器，獲取程序源文件中存在的靜態控制依賴信息，編
譯源文件為可執行文件，並對其進行動態二進位插裝； B.根據得到的靜態控制依賴信息，基於一組測試用例集執行程序，搜集其動態執行軌跡信息，並判定每個測試用例通過或失敗的狀態； C.解析所得到的軌跡信息，得到可執行語句間的動態依賴關係； D.根據所生成的動態依賴關係，運用依賴關係的可疑度計算公式，計算每條動態
依賴關係的可疑度，然後將可疑度的值映射到對應的可執行語句上； E.將各語句按照可疑度從大到小進行降序排列，輸出軟體故障定位的報告。 其中，所述被定位的程序原始碼文件為C語言。 所述軟體故障類型包括兩類 數據流相關的故障，包括存在於變量定義，變量使用，變量重定義，變量刪除，常量值的改變等程序操作中的故障； 控制流相關的故障，包括存在於不必要的代碼塊的添加，路徑的刪除，謂詞條件的
定義，執行順序的改變，外部函數的訪問，函數值的返回等程序操作中的故障。 步驟A所述的作用於連結時的優化器，是一種重寫連結器，其輸入為目標文件和
庫文件，而不是程序的可執行文件。 步驟A所述的動態二進位插裝過程，是利用一個基於動態插裝工具，通過在程序
執行的過程中插入二進位分析代碼來獲取程序性能信息的過程。 步驟B所述的動態執行軌跡信息，包括 Bl.被執行的指令信息 B2.被執行的依賴關係 B3.當前指令所產生的值 信息塊Bl所述中的指令信息，包含了指令的唯一編號，使用的依賴關係的個數，指令對應的文件名和語句行號。 信息塊B2所述中的依賴關係，包含了被依賴的指令的編號。此外，第一條依賴關
系總是表示控制依賴關係，可以為空。之後的依賴關係均是數據依賴關係。 信息塊B3所述中的值，包含了當前指令定義的值，它們可以是變量的值或者是變
量的地址或為空，並以十六進位的形式表示。 步驟C所述的解析過程，包括 CI.解析得到可執行語句間動態控制依賴關係的過程
C2.解析得到可執行語句間動態數據依賴關係的過程 步驟C1所述的過程，是根據B2中的信息得到指令間的動態控制依賴關係，再根據Bl中指令和可執行語句間的映射關係，得到可執行語句間的動態控制依賴關係的解析過 程。 步驟C2所述的過程，是根據B2中的信息得到指令間的動態數據依賴關係，如果B3 中的值是變量的值而非變量的地址，則根據Bl中指令和可執行語句間的映射關係，得到可 執行語句之間的動態數據依賴關係的解析過程。
步驟D所述的可疑度計算公式，包括如下信息 Dl.動態數據或動態控制依賴關係出現在通過的測試用例中的次數
D2.動態數據或動態控制依賴關係出現在失敗的測試用例中的次數
D3.整套測試組件通過的測試用例的個數
D4.整套測試組件失敗的測試用例的個數 步驟E所述的報告，為輔助程式設計師進行軟體故障定位，按可疑度從大到小排列可 執行語句，包括了如下信息El.可執行語句所在文件名E2.可執行語句所在行號E3.可執行語句所在的動態控制依賴關係的個數E4.可執行語句所在的動態數據依賴關係的個數E5.可執行語句的可疑度E6.可執行語句的可疑度排名
圖1為本發明基於程序動態依賴關係的軟體故障定位方法流程示意圖。
具體實施例方式
下面結合附圖及本發明的實施例對本發明的方法作進一步詳細的說明。
本發明的基本思想為首先使用連結時的優化器處理源文件，得到靜態的控制依
賴關係；再通過動態插裝工具，執行測試組件，並得到測試用例狀態和執行軌跡信息；然後
解析執行軌跡信息得到動態依賴關係；由可疑度計算公式得到動態依賴關係的可疑度，並
映射到可執行語句上；最後，根據可執行語句的可疑度，生成故障定位報告。
圖1為本發明基於程序動態依賴關係的軟體故障定位方法流程示意圖；如圖1所
示，該方法包括如下步驟 步驟101 :連結時優化器根據原始碼編譯生成的二進位文件得到靜態控制依賴關 系。 這裡，所謂連結時優化為軟體編譯技術術語。它表示由連結器執行的操作，發生在 編譯之後程序執行之前。連結器是一個程序，將一個或多個編譯器或彙編器生成的目標文 件外加庫連結為一個可執行文件。目標文件是包括機器碼和連結器可用信息的程序模塊。 簡單的講，連結器的工作就是解析未定義的符號引用，將目標文件中的佔位符替換為符號 的地址。連結器還要完成程序中各目標文件的地址空間的組織，這可能設計重定位工作。
所述靜態控制依賴關係是指不執行程序，僅分析程序原始碼，得到的程序語句和 謂詞間可能存在的控制依賴關係。
6
步驟102 :動態插裝工具執行測試組件，並根據靜態控制依賴關係，生成執行軌跡 信息。同時得到測試組件中各測試用例通過或失敗的狀態。 這裡，所謂動態插裝為軟體工程術語，是藉助往被測程序中插入操作(稱為"探
針")，以便獲取程序的控制流和數據流信息，從而實現測試目的的方法。 測試組件為軟體工程術語，是測試用例的一組集合，用來測試某個程序是否有特
定的一些行為。 一個測試套件通常也包含對於每個測試用例如何使用和在測試過程中應收
集哪些信息的詳細說明。 執行軌跡信息是程序執行過程的指令流信息的記錄，一般完整地記錄了程序執行 過程中所執行指令的內容和順序。 測試用例的通過或失敗狀態即可通過人工的方式判定，也可以通過和已知的測試 諭示對比而得到。 步驟103 :根據所得到的軌跡信息，解析產生可執行語句間的動態依賴關係。
這裡，解析產生的動態依賴關係包括動態控制依賴關係和動態數據依賴關係。它 們分別表示在程序執行中由於控制流和數據流而引起的語句之間的相互作用。
步驟104 :根據所生成的動態依賴關係，運用依賴關係的可疑度計算公式，計算每 條動態依賴關係的可疑度，然後將可疑度的值映射到對應的可執行語句上。
為說明依賴關係的可疑度計算公式，引入如下記號
ctrld印(a，b):表示一條控制依賴關係，語句b控制依賴於語句a
datad印(a， b):表示一條數據依賴關係，語句b數據依賴於語句a
d印(a，b):表示一條依賴關係，可以是ctrld印(a，b)也可以是datad印(a， b)
failed(d印(a， b)):表示依賴關係d印(a， b)出現在失敗測試用例中的次數
passed(d印(a， b)):表示依賴關係d印(a， b)出現在通過測試用例中的次數
totalfailed :表示測試組件中失敗測試用例總共的個數
由上，依賴關係的可疑度計算公式定義如下 ",,、、 孤^(A/7("，6)) = /, ^ .7 j ^ ., J" z M ^ z A:
,ta,/ed x (/az/efi (鄉(a,6) +戸^(鄉(fl,6)) 為說明如何將依賴關係的可疑度映射到語句上，引入如下記號
First (s):表示語句行號i的集合，i與語句s間有依賴關係d印(s， i)
Second(s):表示語句行號j的集合，j與語句s間有依賴關係d印(j， s) , 、 '■ 乂 步驟105 :將得到的各語句的可疑度按從大到小排序，輸出語句所在的文件名，行 號，動態控制依賴關係的個數，動態數據依賴關係的個數，可疑度及排名，產生程序故障定 位報告。 綜上所述，程序動態依賴關係的收集和可疑度計算模型是本發明的核心。最終產 生的故障定位報告，可供開發者按可疑度從大到小的順序對可疑代碼進行審查，減少程序 調試階段的必須檢查的代碼範圍和數量，提高定位程序故障的效率。
權利要求
一種基於程序動態依賴關係的軟體故障定位方法，其特徵在於，該方法包括A.使用作用於連結時的優化器，獲取程序源文件中存在的靜態控制依賴信息，編譯源文件為可執行文件，並對其進行動態二進位插裝；B.根據得到的靜態控制依賴信息，基於一組測試用例集執行程序，搜集其動態執行軌跡信息，並判定每個測試用例通過或失敗的狀態；C.解析所得到的軌跡信息，得到可執行語句間的動態依賴關係；D.根據所生成的動態依賴關係，運用依賴關係的可疑度計算公式，計算每條動態依賴關係的可疑度，然後將可疑度的值映射到對應的可執行語句上；E.將各語句按照可疑度從大到小進行降序排列，輸出軟體故障定位的報告。
2. 根據權利要求l所述的定位方法，其特徵在於，所述被定位的程序源文件為C語言代 碼文件。
3. 根據權利要求1所述的定位方法，其特徵在於，所述軟體故障類型包括兩類 數據流相關的故障，包括存在於變量定義，變量使用，變量重定義，變量刪除，常量值的改變；控制流相關的故障，包括存在於不必要的代碼塊的添加，路徑的刪除，謂詞條件的定 義，執行順序的改變，外部函數的訪問，函數值的返回。
4. 根據權利要求1所述的方法，其特徵在於，步驟A所述的作用於連結時的優化器，是 一種重寫連結器，其輸入為目標文件和庫文件，而不是程序的可執行文件。
5. 根據權利要求1所述的方法，其特徵在於，步驟A所述的動態二進位插裝過程，是利 用一個動態插裝工具，通過在程序執行的過程中插入二進位分析代碼來獲取程序性能信息 的過程。
6. 根據權利要求1所述的方法，其特徵在於，步驟B所述的動態執行軌跡信息，包括了 Bl.被執行的指令信息；B2.被執行的依賴關係； B3.當前指令所產生的值。
7. 根據權利要求6所述的方法，其特徵在於，信息塊B1中的指令信息，包含了指令的唯 一編號，使用的依賴關係的個數，指令對應的文件名和語句行號。
8. 根據權利要求6所述的方法，其特徵在於，信息塊B2中的依賴關係，包含了被依賴的 指令的編號；此外，第一條依賴關係總是表示控制依賴關係，可以為空；之後的依賴關係均 是數據依賴關係。
9. 根據權利要求6所述的方法，其特徵在於，信息塊B3中的值，包含了當前指令定義的 值，它們可以是變量的值或者是變量的地址或為空，並以十六進位的形式表示。
10. 根據權利要求6所述的方法，其特徵在於，步驟C所述的解析過程，包括了 Cl.解析Bl和B2的信息得到可執行語句間動態控制依賴關係的過程；C2.解析Bl， B2和B3的信息得到可執行語句間動態數據依賴關係的過程。
11. 根據權利要求10所述的方法，其特徵在於，步驟Cl是根據B2中的信息得到指令間 的動態控制依賴關係；再根據B1中指令和可執行語句間的映射關係，得到可執行語句間的 動態控制依賴關係。
12. 根據權利要求10所述的方法，其特徵在於，步驟C2是根據B2中的信息得到指令間的動態數據依賴關係；如果B3中的值是變量的值而非變量的地址，則根據B1中指令和可執 行語句間的映射關係，得到可執行語句之間的動態數據依賴關係。
13. 根據權利要求1所述的方法，其特徵在於，步驟D所述的可疑度計算公式，需要如下 信息 >Dl.動態數據或動態控制依賴關係出現在通過的測試用例中的次數； D2.動態數據或動態控制依賴關係出現在失敗的測試用例中的次數； D3.整套測試組件通過的測試用例的個數； D4.整套測試組件失敗的測試用例的個數。
14. 根據權利要求1所述的方法，其特徵在於，步驟E所述的報告，為輔助程式設計師進行軟 件故障定位，按可疑度從大到小排列可執行語句，給出了如下信息El.可執行語句所在文件名； E2.可執行語句所在行號；E3.可執行語句所在的動態控制依賴關係的個數； E4.可執行語句所在的動態數據依賴關係的個數； E5.可執行語句的可疑度；E6.可執行語句的可疑度排名。
全文摘要
本發明公開了一種基於程序動態依賴關係的軟體故障定位方法，包括基於作用於連結時的優化器，獲取靜態控制依賴信息；動態插裝可執行程序，搜集動態執行軌跡信息；解析軌跡信息，得到動態依賴關係；再根據動態依賴關係的可疑度公式，計算每動態依賴關係的可疑度；然後將可疑度的值映射到程序的可執行語句上；最後將各語句按照可疑度的大小進行降序排列，輸出軟體故障定位的報告。開發者可以按可疑度從大到小的順序對代碼進行審查，減少程序調試階段的必須檢查的代碼範圍和數量，提高定位程序故障的效率。本發明具有自動化程度高、定位準確度高的優點。
文檔編號G06F11/36GK101739339SQ20091024411
公開日2010年6月16日 申請日期2009年12月29日 優先權日2009年12月29日
發明者李未, 虞凱 申請人:北京航空航天大學