一種基于反饋優(yōu)化的啟發(fā)式軟件調(diào)試框架

鞠小林，錢 潔，趙春雨，陳志華

(1.南通大學 信息科學技術(shù)學院，江蘇 南通 226019；2.南京大學 計算機科學與技術(shù)系，江蘇 南京 210023)

軟件缺陷定位的終極目標是幫助調(diào)試人員快速準確地識別并修復缺陷。已有的缺陷定位技術(shù)大多數(shù)是給定出錯可疑度高的候選程序?qū)嶓w集合，或者這些候選程序?qū)嶓w依據(jù)可疑度降序排列的排序列表[1-2]。然而，最新的一份研究表明，這些缺陷定位技術(shù)在軟件開發(fā)實踐中并沒有得到廣泛的應用[3]。主要原因在于這些缺陷定位技術(shù)給出的定位報告將程序?qū)嶓w視為獨立個體而忽略這些實體之間的關(guān)系，包含的程序?qū)嶓w與程序執(zhí)行順序或源代碼中出現(xiàn)的順序并不一致，從而不利于程序員調(diào)試時分析和理解程序[4]。例如，基于程序語句的缺陷定位技術(shù)通常直接給出一個按語句懷疑度降序排列的檢查列表[5-6]，并不提供列表中語句之間的關(guān)系，而大多數(shù)情況下，由于檢查列表中的語句在源程序中并不連續(xù)，程序員在識別語句是否有錯時，通常需要自己分析該語句的前后相關(guān)語句，人工厘清語句之間的相關(guān)關(guān)系，并憑借經(jīng)驗判斷當前審查語句是否出錯。這種方式增加了程序員的工作量，并增加了人為出錯的可能性。在沒有上下文信息的前提下，調(diào)試人員在審查缺陷定位報告時，只閱讀一條程序語句，往往很難判斷其是否存在缺陷[7]。此外，在實踐中，程序缺陷往往不僅僅是程序中的某一行出錯，有些時候會跨越幾個行代碼甚至跨越不同類、文件等[8]。為此，我們需要一些啟發(fā)式的信息輔助程序員進行判斷。例如，提供當前審查的程序語句在執(zhí)行時的上下文，以及與當前語句存在依賴關(guān)系的那些語句等信息。程序員基于這些啟發(fā)信息，可以更高效地甄別當前審查的語句是否包含軟件缺陷。此外，以往的缺陷定位技術(shù)往往是一次性提供定位信息，不能依據(jù)調(diào)試人員已有工作動態(tài)地調(diào)整缺陷定位報告，這種方式會影響到軟件調(diào)試的精度和效率。研究發(fā)現(xiàn)許多軟件缺陷在定位報告排序列表中往往處于列表的后端[9]，這種現(xiàn)象更是削弱了現(xiàn)有缺陷定位技術(shù)在實踐中的效用。為此，我們在程序調(diào)試過程中引入反饋機制，即當程序員完成對當前語句判斷之后，依據(jù)判斷結(jié)論對其余語句的懷疑度做動態(tài)調(diào)整，進一步優(yōu)化缺陷定位報告，從而得到更優(yōu)的語句審查順序。

基于上述考慮，本文提出了一種基于程序員調(diào)試反饋的啟發(fā)式軟件調(diào)試框架。該調(diào)試框架借助程序分析技術(shù)，自動將準確的相關(guān)語句信息等以直觀的圖形展示給程序員，以幫助程序員進行缺陷定位的判斷；此外，根據(jù)程序員的反饋，動態(tài)優(yōu)化前期所得的缺陷定位報告為后續(xù)剩余缺陷定位服務，從而提高缺陷定位報告的效率。

本文的主要貢獻如下：

1)提出一種收集并建模缺陷相關(guān)信息方法。首先定義了該上下文信息表示的數(shù)據(jù)結(jié)構(gòu)，接著借助程序靜態(tài)分析技術(shù)和動態(tài)執(zhí)行跟蹤技術(shù)，跟蹤并記錄軟件失效時執(zhí)行上下文信息。

2)給出精化的缺陷相關(guān)上下文信息的可視化方法。通過直觀給出缺陷相關(guān)信息的依賴和傳遞關(guān)系，并只保留必要的缺陷關(guān)聯(lián)信息，幫助調(diào)試人員高效識別和修復軟件缺陷。

3)基于程序員在調(diào)試過程中的反饋信息，提出動態(tài)調(diào)整缺陷定位報告的策略，并給出基于單個反饋和成組反饋的缺陷定位優(yōu)化算法。

4)設(shè)計并實現(xiàn)了一個基于上述策略和算法的原型系統(tǒng)(稱為HDebug)。通過邀請一批學生使用，實驗驗證了本文提出方法的有效性。

1 預備知識

1.1 基于頻譜的缺陷定位

基于頻譜的缺陷定位方法首先運行一組測試用例，借助程序跟蹤技術(shù)記錄程序?qū)嶓w(如程序語句、謂詞、基本塊等)的覆蓋信息及程序執(zhí)行結(jié)果(如圖1 所示)；接著，利用一組缺陷懷疑度計算公式(如Tarantula[10]、Naish[11]、DStar[12]等)計算程序?qū)嶓w的缺陷可疑程度；最后，將程序?qū)嶓w按照可疑度降序排列，形成缺陷定位報告。

這類方法的可疑度計算大部分是基于一個共同的假設(shè)：程序?qū)嶓w的可疑度與失敗測試用例執(zhí)行覆蓋次數(shù)正相關(guān)，與成功測試執(zhí)行覆蓋測試負相關(guān)[10]。圖1 中左邊矩陣(N spectra)表示包含M 個程序?qū)嶓w的程序經(jīng)過N 個測試用例運行的覆蓋情況(aij表示第j 個程序?qū)嶓w被第i 個測試用例覆蓋信息)，右邊的矩陣則記錄了這N 個測試用例的執(zhí)行結(jié)果(成功或失敗)。基于頻譜的缺陷定位先根據(jù)上述假設(shè)設(shè)計懷疑度計算公式，然后基于圖1 中的兩個矩陣數(shù)據(jù)計算每個程序?qū)嶓w的可疑度，程序員根據(jù)懷疑度的降序依次甄別程序?qū)嶓w是否包含缺陷。

圖1 基于頻譜的缺陷定位矩陣Fig.1 Matrix for spectrum-based fault localization

1.2 信息收集與建模

為了輔助程序員調(diào)試時識別軟件缺陷，需要提供與程序出錯語句密切相關(guān)的程序信息。這些信息可以初步分為靜態(tài)信息和動態(tài)信息兩類。其中程序員關(guān)注的動態(tài)信息主要為程序執(zhí)行路徑，以及與出錯語句相關(guān)的變量取值變化等；而靜態(tài)信息則包括出錯語句控制依賴的其他語句信息等。下面我們分析這兩類信息的搜集與建模。

對于程序靜態(tài)信息的搜集，我們的主要工作是獲取目標程序的控制流程圖。控制流圖構(gòu)造技術(shù)已經(jīng)十分成熟，具體的技術(shù)不在文中一一贅述。得到的控制流圖將被用于后續(xù)階段模型分析及可視化展示。

程序的動態(tài)信息主要是為了幫助調(diào)試人員了解軟件行為。在本文的方法中將記錄如下信息：1)程序執(zhí)行的軌跡。由于程序的任意基本塊中的所有語句執(zhí)行軌跡一致，因此我們選用基本塊作為執(zhí)行軌跡的一部分：此外，由于謂詞決定了程序下一步執(zhí)行哪個基本塊，并且從實際的調(diào)試反饋可知，謂詞是最容易發(fā)生缺陷的程序?qū)嶓w之一[13]，因此執(zhí)行軌跡中也記錄執(zhí)行的謂詞信息。2)謂詞或基本塊對應的變量取值。對于程序執(zhí)行軌跡中的基本塊，調(diào)試人員通常關(guān)心基本塊中涉及的變量在進入基本塊前的取值情況，以及當控制流進入并執(zhí)行完基本塊后涉及變量的取值變化。

由于在軟件調(diào)試過程中，調(diào)試人員通常只關(guān)心與程序產(chǎn)生失效輸出的位置緊密相關(guān)的其他語句，而非程序中所有語句，因此，我們并不需要不加篩選地提供程序所有的信息，相反，只需要提供少量的與可疑缺陷語句密切相關(guān)的語句和謂詞。在方法實現(xiàn)時，我們借助隊列機制，滾動記載程序最近的執(zhí)行動態(tài)信息，用于交互調(diào)試階段的可視化程序信息展示。圖2 給出了本文方法中描述程序執(zhí)行隊列及隊列元素所使用的變量表的數(shù)據(jù)結(jié)構(gòu)。

圖2 程序執(zhí)行動態(tài)信息跟蹤數(shù)據(jù)模型Fig.2 Data traced during program running

圖2 所示的數(shù)據(jù)結(jié)構(gòu)設(shè)計借鑒了動態(tài)語言Python 編譯器對變量(對象)的處理方式。其中，隊列用于保存一定長度的執(zhí)行序列(以基本塊和謂詞為單位)。不保存所有的跟蹤執(zhí)行序列原因有兩點：一是由于存儲空間的制約無法全部保存，因此，程序執(zhí)行過程可能會產(chǎn)生無限長的執(zhí)行序列；二是沒有必要全部保存這些信息。保存這些信息只是用于輔助程序員調(diào)試時判斷決策，太多的信息對程序員的判斷不但沒有幫助，反而會降低判斷效率，甚至會干擾程序員作出正確的判斷。變量表用于存放隊列中基本塊或謂詞所使用的變量(為提高處理速度并節(jié)省存儲空間，采用指針形式存放鏈接到變量實際存儲位置的地址)。變量表的構(gòu)造可通過

迭代計算得到。

此外，通過實時跟蹤記錄變量的值。為了能追蹤到變量歷史的取值信息，我們保存一定時期內(nèi)的變量取值變化。不同基本塊可能使用到相同的變量，但是在使用時其值可能變化，也有可能不變，因此，我們保存了變量值(Var_value)及變量的引用計數(shù)器(ref_count)。當變量值發(fā)生變化時，如果新的變量值在表中不存在，則新建一項并將引用計數(shù)器設(shè)置為1；如果新的變量值在表中已經(jīng)存在，則將對應項的引用計數(shù)器增加1。在實現(xiàn)上述操作時，我們采用哈希函數(shù)映射的方法，可以快速找到并更新表中對應的項。

2 基于反饋優(yōu)化的啟發(fā)式軟件調(diào)試框架

本文提出一種兩階段的啟發(fā)式交互調(diào)試框架(如圖3 所示)。借助開源軟件分析工具Soot 實現(xiàn)對待測程序的靜態(tài)分析以獲取程序的結(jié)構(gòu)信息，結(jié)合缺陷定位報告，計算程序后向切片及控制流程圖等。同時，借助JVM 編程接口JDI 實現(xiàn)對Java 程序運行時的監(jiān)控，跟蹤并記錄程序運行時的堆棧信息。用dot 格式可視化展示程序運行時與當前審查語句相關(guān)的執(zhí)行上下文。此外，根據(jù)調(diào)試人員的反饋，動態(tài)優(yōu)化缺陷定位報告，實現(xiàn)交互式的調(diào)試，提高定位缺陷的效率。

圖3 基于反饋優(yōu)化的啟發(fā)式軟件調(diào)試框架Fig.3 Heuristic debugging framework based on the feedback optimization

在圖3 中，程序運行監(jiān)控和靜態(tài)分析(后向切片)模塊分別用于搜集程序運行時的動態(tài)信息和靜態(tài)切片。在計算靜態(tài)切片時，根據(jù)當前審查語句所在函數(shù)的規(guī)模，確定需要顯示的靜態(tài)信息，并計算控制流圖片段，隨后我們在控制流圖片段上添加程序執(zhí)行時的動態(tài)信息，并生成dot 格式文檔，通過圖中的交互式可視化調(diào)試接口展示給調(diào)試人員，用于輔助其對當前審查語句判斷。此外，調(diào)試人員針對當前審查語句給出的判斷結(jié)論，同樣通過調(diào)試接口反饋給動態(tài)調(diào)整模塊，根據(jù)本文提出的可疑度調(diào)整算法動態(tài)調(diào)整剩余語句的可疑度，從而推薦下一條審查語句。下面從啟發(fā)信息可視化建模和缺陷報告動態(tài)優(yōu)化兩方面詳細描述方法實現(xiàn)細節(jié)。

2.1 啟發(fā)信息可視化建模

可視化的目的是為程序調(diào)試人員提供針對當前語句的輔助判斷信息。過多的信息和過少的信息都不利于調(diào)試人員作出正確判斷，并且遵循局部化原則，應該盡可能提供與當前語句密切相關(guān)的程序內(nèi)容。一個容易想到的辦法是提供當前審查語句所在函數(shù)的控制流程圖，然后在圖上增加其他輔助信息。但是這種方法面臨一個困境：當前語句所在函數(shù)的規(guī)模有可能很大，導致給出的可視化圖形模型信息量太大而不便于程序調(diào)試人員甄別當前語句是否正確；此外，當前語句所在函數(shù)的規(guī)模有可能很小(例如只有簡單的幾行代碼)，這種情況又導致可提供的信息量太少，同樣不利于程序調(diào)試人員甄別當前語句。因此，按照當前審查的語句所在函數(shù)的規(guī)模，本文給出3 種用于可視化的策略:

1)當所在函數(shù)規(guī)模適中時(如基本塊個數(shù)低于某個上界⊥，高于某個下界⊥)，直接給出函數(shù)的控制流程圖，并將動態(tài)行為信息(如變量取值等)添加到控制流程圖中對應的程序執(zhí)行路徑上加以顯示。

2)當所在函數(shù)規(guī)模過大時(如基本塊個數(shù)高于某個上界⊥)，在該函數(shù)的控制流程圖上進行刪減，刪除部分距離程序執(zhí)行路徑較遠的分支，并將動態(tài)行為信息(如變量取值等)添加到控制流程圖中對應的程序執(zhí)行路徑上加以顯示。

3)當所在函數(shù)規(guī)模過小時(如基本塊個數(shù)低于某個下界⊥)，直接給出函數(shù)的控制流程圖，同時，針對該函數(shù)的上一級調(diào)用函數(shù)進行分析，分析策略即是現(xiàn)在給出的3 種策略。最后將動態(tài)行為信息(如變量取值等)添加到控制流程圖中對應的程序執(zhí)行路徑上加以顯示。

上述策略1)到策略3)中的選擇依據(jù)是函數(shù)規(guī)模，其中的上界(⊥)和下界(⊥)是兩個經(jīng)驗值，由調(diào)試人員依據(jù)歷史調(diào)試經(jīng)驗設(shè)置，通?？梢苑謩e設(shè)置為20 和8。

接下來我們詳細闡述在這3 種策略下，可疑語句輔助調(diào)試信息可視化的算法實現(xiàn)，下面算法1 給出了具體的實現(xiàn)過程。

算法1可疑語句輔助調(diào)試信息可視化算法

輸入：

輸出：

在算法1 中，輸入的是程序源代碼P、程序員當前審查的語句ExaStmt(即缺陷定位技術(shù)提供的懷疑度列表中可疑度最高的語句)、程序運行時跟蹤的一組動態(tài)信息TraceInfo(數(shù)據(jù)結(jié)構(gòu)包含一個隊列及其指向的變量存儲列表，見圖2)、一組系統(tǒng)設(shè)置參數(shù)＜⊥，⊥，W＞用于表示函數(shù)規(guī)模的上界、下界及最終顯示窗口中節(jié)點的最大數(shù)量。首先獲取當前檢查語句ExaStmt 所在的函數(shù)fun，統(tǒng)計函數(shù)fun 的規(guī)模(基本塊數(shù))，然后依據(jù)系統(tǒng)設(shè)定的閾值(⊥，⊥)分別處理策略1)(第3—5 行)、策略2)(第6—14行)及策略3)(第15—17 行)所面臨的情況，最后將處理的結(jié)果轉(zhuǎn)化為用DOT 語言書寫的圖形描述文件。算法1 中的S1_Gen(fun，ExaStmt，TraceInfo，W)，S2_Gen(FunList，ExaStmt，TraceInfo，W)，以及S3_Gen(fun，ExaStmt，TraceInfo，W)函數(shù)以程序的控制流程圖為基礎(chǔ)，開展數(shù)據(jù)依賴分析，提取出與當前審查語句相關(guān)的基本塊和謂詞，并將程序執(zhí)行中獲取的動態(tài)信息添加到這些相關(guān)的基本塊和謂詞所在的節(jié)點。此外，為了避免最終顯示過多的輔助信息，通過計算節(jié)點與當前執(zhí)行路徑的距離，刪除原控制流程圖上與當前執(zhí)行路徑關(guān)系不大的節(jié)點。節(jié)點與當前執(zhí)行路徑的距離定義為從節(jié)點到當前執(zhí)行路徑所需經(jīng)過的最少節(jié)點數(shù)，為

其中path* 表示一條從node* 節(jié)點開始經(jīng)歷一系列節(jié)點到達最后節(jié)點node，并且path* 中只有唯一的節(jié)點node 屬于當前執(zhí)行路徑path。因此上述距離可以理解為最短路徑。

下面依次介紹3 個函數(shù)的算法實現(xiàn)：

算法2 首先構(gòu)造出從函數(shù)入口到指定語句(ExaStmt)的一個控制流程圖片段SegCFG(第1行)；接著以當前語句(ExaStmt)為切片準則，在第1 步得到的控制流程圖片段SegCFG 上進行后向切片，同時以參數(shù)W 限定后向切片的最大規(guī)模(第2 行)；隨后針對后向切片中的每一依賴語句，計算其引用變量，并從跟蹤信息TraceInfo 中將這些引用變量在執(zhí)行時所對應的值取出添加到控制流程圖片段SegCFG 中對應節(jié)點的變量位置(第3—10 行)。需要注意的是：在算法2 中，用node.stmt.v.values 表示節(jié)點ndoe 中有一個語句stmt，并且stmt 有一個引用變量v。類似地，函數(shù)TraceInfo.getValues(node，v)表示對象TraceInfo 有處理函數(shù)getValues，其功能是獲取對應節(jié)點(node)中變量(v)的值。

接下來介紹函數(shù)S2_Gen(FunList，ExaStmt，TraceInfo，W)的算法實現(xiàn)(見算法3)。

算法3 首先依次計算函數(shù)列表中所有函數(shù)的控制流程圖片段，并將這些控制流程圖片段按照調(diào)用和被調(diào)用的順序拼接為一張大的控制流程圖片段SegCFG(第1—6 行)，其中函數(shù)fun.getCaller()返回的是當前函數(shù)調(diào)用其他函數(shù)fun()的語句集合，由于當前函數(shù)在調(diào)用其他函數(shù)fun()時可能出現(xiàn)多個調(diào)用位置，因此函數(shù)fun.getCaller()可能返回一組語句；隨后的工作(第7—15 行)類似于S1_Gen()函數(shù)的對應部分功能，即計算當前審查語句ExaStmt 的后向切片，并將切片中存在數(shù)據(jù)依賴關(guān)系的變量值通過提取跟蹤信息TraceInfo 獲得(由函數(shù)TraceInfo.getValues(node，v)實現(xiàn))。接下來介紹當前審查語句所在函數(shù)規(guī)模十分龐大、超過限定閾值的情況下，如何顯示輔助調(diào)試信息的過程(見算法4)。

算法4 首先計算函數(shù)fun()的控制流程圖片段SegCFG(第1 行)；接著依據(jù)程序的執(zhí)行跟蹤信息，構(gòu)造一條以當前審查語句ExaStmt，長度不超過W 執(zhí)行路徑片段SegPath(第2 行)；由于第1 步中得到的控制流程圖片段規(guī)模偏大，如果直接顯示給調(diào)試人員反而不利于調(diào)試人員快速獲取準確、精煉的信息，需要對初始的控制流圖片段進行刪減，去除與本次執(zhí)行關(guān)系不大的節(jié)點。針對控制流程圖片段SegCFG 中的節(jié)點，計算其與執(zhí)行路徑片段SegPath 之間的距離，若距離超過系統(tǒng)設(shè)置的閾值Min_Distance，則從SegCFG 中移除節(jié)點，同時刪除與該節(jié)點有關(guān)的邊(第3—8 行)。隨后的工作(第9—17 行)類似于S1_Gen()函數(shù)及S2_Gen()函數(shù)的對應部分功能，即以當前審查語句ExaStmt 為切片準則，在經(jīng)過刪減的控制流程圖片段上計算W 規(guī)模的后向切片，然后提取切片中變量實際執(zhí)行時的變量值，將變量取值信息添加到節(jié)點中，用于后續(xù)可視化顯示。

2.2 基于調(diào)試反饋的可疑語句推薦

在回答了調(diào)試輔助信息識別和顯示這兩個問題之后，接下來討論如何依據(jù)調(diào)試人員的反饋，動態(tài)調(diào)整缺陷定位的報告。在軟件調(diào)試過程中，調(diào)試人員借助個人經(jīng)驗對當前語句是否是錯誤語句作出判斷，然后繼續(xù)審查在排序列表中的下一條可疑語句，然而并未利用調(diào)試人員的判斷。我們認為，調(diào)試人員的判斷可以用來指導調(diào)整后續(xù)語句的檢查順序，為此提出了一種動態(tài)調(diào)整語句懷疑度的算法。該算法基于如下3 點假設(shè)：

假設(shè)1調(diào)試人員對所有審查語句作出的判斷都是正確的；

假設(shè)2如果調(diào)試人員認定當前的審查語句s是正確的，則s 語句的后向切片中的語句可疑度是被高估了的，應該調(diào)低后向切片中的語句可疑度；

假設(shè)3如果調(diào)試人員認定當前的審查語句s是錯誤的，則s 語句的前向切片中的語句可疑度是被高估了的，應該調(diào)低其前向切片中的語句可疑度。

由于現(xiàn)階段調(diào)試人員對審查語句的判斷是基于經(jīng)驗的主觀認定，人類腦力勞動的復雜性決定了其判斷結(jié)果有可能出現(xiàn)錯誤，而且出錯概率因人而異。雖然可以基于調(diào)試人員出錯概率來建立后續(xù)動態(tài)反饋模型，但那樣會大大增加模型的復雜度。為了分析方便，假設(shè)調(diào)試人員的經(jīng)驗豐富，不會出錯(即滿足假設(shè)1)。

現(xiàn)有的統(tǒng)計缺陷定位技術(shù)通常預先假設(shè)程序中的語句均有可能出錯。由PIE 模型[14]可知：軟件錯誤引發(fā)程序進入錯誤的內(nèi)部狀態(tài)，經(jīng)過程序執(zhí)行路徑向程序出口處傳播。在傳播過程中，從程序開始到該軟件錯誤處，與軟件錯誤相關(guān)語句的可疑度值都被高估，因此應該加以修正(即滿足假設(shè)3)；與之相對應的，如果一個語句是正確的，則該語句到程序出口的所有相關(guān)語句的可疑度也被高估了(即滿足假設(shè)2)。

接下來討論如何進行可疑度動態(tài)調(diào)整。本文的策略如下:

1)當調(diào)試人員認定當前審查語句s 是正確語句時，計算語句s 的后向切片Ω，計算Ω 中所有語句的懷疑度總和sum，并將s 語句的懷疑度值r 除以sum，得到一個調(diào)整度比值ρ，最后將Ω 中語句的懷疑度乘以(1 -ρ)作為新的懷疑度值。

2)當調(diào)試人員認定當前審查語句s 是錯誤語句時，計算語句s 的前向切片Ψ，計算Ψ 中所有語句的懷疑度總和sum，并將s 語句的懷疑度值r 除以sum，得到一個調(diào)節(jié)度比值ρ′，最后將Ψ 中語句的懷疑度乘以(1 -ρ′)作為新懷疑度值。

算法5 給出調(diào)整可疑度動態(tài)過程。Stop為排序列表的最頂端的一個語句，其懷疑度值最高。算法5的第2 行Feedback(Stop)表示調(diào)試人員對當前語句Stop作出判斷。當調(diào)試人員認定當前語句Stop是正確語句時，由算法的第3—10 行實現(xiàn)將當前語句Stop后向切片中所有語句的可疑度調(diào)低；當調(diào)試人員認定當前語句Stop是錯誤語句時，由算法的第11—18行實現(xiàn)將當前語句Stop的后向切片中所有語句的可疑度調(diào)低。即先計算Stop語句的后向切片集合Ω，接著計算當前審查語句Stop的懷疑度值與切片中所有語句的懷疑度比值ρ，用其作為調(diào)節(jié)比率，將切片中的所有語句的懷疑度動態(tài)更新。類似地，算法5中另一個變量ρ′即用于調(diào)節(jié)前向切片語句的可疑度。

算法5基于調(diào)試反饋的可疑度動態(tài)更新算法

輸入：

輸出：

然而，在算法5 中調(diào)試人員一次只能確認一條語句，調(diào)試的效率較低。事實上，在實際的軟件調(diào)試過程中，調(diào)試人員有可能一次確認一組語句，部分識別為正確語句，部分識別為錯誤語句，從而可分為兩個集合：認定為正確的語句集合(Good)和認定為錯誤的語句集合(Bad)。我們需要進一步改進算法5 以處理多個語句反饋情況，改進方法如算法6所示。

算法6基于調(diào)試反饋的可疑度動態(tài)更新算法

輸入：

輸出：

算法6 中的第3—10 行、第11—18 行與算法5的第3—10 行、第11—18 行對應部分的功能一致：都是先計算語句可疑度的調(diào)節(jié)率ρ 和ρ′，然后對原始懷疑度列表中的語句依據(jù)調(diào)節(jié)率調(diào)整得到新的可疑度評估值，最后對其進行排序以得到新的排序列表。兩者不同之處在于：算法6 增加了迭代處理多條語句的功能。當程序調(diào)試人員一次反饋給系統(tǒng)多條語句的判斷，這些語句判斷信息在算法6 的第2 行被組織成Good 和Bad 兩個集合：算法第3—10行實現(xiàn)迭代調(diào)整Good 集合中所有語句的后向切片中語句的懷疑度調(diào)整；算法第11—18 行實現(xiàn)迭代調(diào)整Bad 集合中所有語句的前向切片中語句的懷疑度調(diào)整。此外，算法6 的第19 行用于移除可疑列表中已經(jīng)確認的語句，因為這些已經(jīng)由調(diào)試人員甄別過的語句無需重新確認。

進一步分析算法5 和算法6，可以發(fā)現(xiàn)，這兩個算法中處理調(diào)試人員反饋的先后順序有可能影響到最后生成的可疑語句的排序列表。目前，尚不清楚其具體的影響程度。一個主要的原因在于這兩個算法的效果依賴于調(diào)試人員給出的判斷是否正確，從而導致我們很難從理論上進行分析。下一步對提出的方法進行實驗驗證。

3 實證研究

3.1 實驗基準程序

本文開發(fā)了一個用于調(diào)試Java 程序的原型工具，在一組基準程序上開展用戶使用研究。選擇了5個Java 程序作為實驗對象(如表1 所示)，這些實驗程序均是采用Java 編程實現(xiàn)。對于每個實驗對象程序，表1 給出了實驗對象名稱(第1 列)、實驗對象的可執(zhí)行代碼行數(shù)LOC(第2 列)、測試用例數(shù)(第3列)和研究的錯誤版本數(shù)(第4 列)。其中，前3 個程序是Java 版本的西門子程序(Siemens suits)，由Santelices 等[15]從C 語言版本轉(zhuǎn)換得到的Java 版本程序。其余程序是從SIR(subject infrastructure repository)[16]下載得到的。

表1 實驗基準程序特征Tab.1 Characteristics of studied subjects

如表1 所示，選取的實驗對象的可執(zhí)行代碼行數(shù)為數(shù)百行。除了Sorting 程序外，其他程序的測試用例均從文獻[15-16]中的兩個網(wǎng)站下載，僅選擇了其中部分的測試用例，然后隨機生成100 組不同長度的數(shù)組用于測試Sorting 程序。表1 中列出的每個版本實驗對象程序被注入單一缺陷，除了Sorting 程序外，其余程序注入的缺陷均為其他研究人員設(shè)計的。針對Sorting 程序，采用人工設(shè)計并注入了2 個缺陷(包含謂詞和賦值缺陷)。對于Jtcas 程序，從41 個缺陷版本中隨機選擇了2 個缺陷版本以避免實驗結(jié)果過分受該程序影響。對于其余的實驗對象，同樣隨機選擇2 個缺陷版本。本文一共實證研究10 個不同缺陷的定位。

3.2 實驗設(shè)置

首先，選擇表1 中的基準測試程序，依次注入缺陷，并運行測試用例，收集覆蓋信息，基于GZoltar得到初始的缺陷定位報告[17]。接著，邀請來自南通大學信息科學技術(shù)學院16 名選修軟件測試課程的學生參與該研究。為了避免由于編程經(jīng)驗差異而引起的偏差，對于每個程序，將學生隨機分為兩組，一組使用本文開發(fā)的工具HDebug，另一組使用安裝GZoltar 插件Eclipse 編程環(huán)境。記錄下每組實驗中修復每個缺陷耗費的時間，并匯總每組修復所有缺陷所需時間。

3.3 實驗結(jié)果及討論

分別統(tǒng)計兩組學生修復10 個缺陷耗費的時間(統(tǒng)計精確到分鐘)。表2 中，#1，#2，…，#8 分別為每組學生的編號?？梢钥闯觯褂霉ぞ逪Debug 的每位學生耗費的時間均小于使用GZolta 工具所耗費的時間，平均節(jié)省了約20%～35%的調(diào)試時間。

表2 修復全部缺陷所需時間Tab.2 Time cost for bug fixing of all defects min

下面進一步分析分別使用HDebug 和GZoltar在5 個基準程序上所耗費的時間。為了平衡不同基準程序調(diào)試時間的差異性，統(tǒng)一對兩組同學使用工具在每個基準程序上調(diào)試時間代價進行了變換，統(tǒng)一映射到[0，10]區(qū)間內(nèi)的1 個值。映射方法為

其中Maxk，Mink分別為兩組學生中調(diào)試同一基準程序耗費時間的最大值和最小值。ai和bi(i∈[1，8])分別為學生調(diào)試某一基準程序缺陷耗費的時間。圖4給出了兩組調(diào)試技術(shù)所耗費時間的對比。

圖4 兩種程序調(diào)試技術(shù)的時間代價對比Fig.4 Comparison of time costs between two debug techniques

從圖4 可以看出，除了Tot_info 基準程序之外的其他4 個基準程序，采用HDebug 技術(shù)的調(diào)試時間代價均低于GZoltar(中位數(shù)均低于對照技術(shù))。但圖4 也表明，基于HDebug 技術(shù)的調(diào)試代價的穩(wěn)定性不高。為了進一步驗證兩種技術(shù)的性能差異，引入以下原假設(shè)和備選假設(shè)：

H0：兩種調(diào)試技術(shù)之間沒有顯著性能差異。

H1：兩種調(diào)試技術(shù)之間性能差異非常明顯。

采用Wilcoxon 符號秩檢驗來評估原假設(shè)，如果p 值＜0.05，我們將拒絕它。在對比每個基準程序的基礎(chǔ)上分別采用HDebug 和GZoltar 技術(shù)的時間代價，利用R 計算其對比時的p 值。觀察到在5 個基準程序上計算得到的p-value 均小于0.05，這意味著性能改進是顯著的。

4 相關(guān)工作

軟件調(diào)試工具可以分為兩大類：手工調(diào)試工具和統(tǒng)計調(diào)試工具。手工調(diào)試工具屬于傳統(tǒng)工具，基于一個測試用例的單步執(zhí)行以定位程序缺陷，其主要方式是集成在軟件開發(fā)環(huán)境(integrated development environment，IDE)中；統(tǒng)計調(diào)試工具是基于統(tǒng)計缺陷定位的方法，通過統(tǒng)計分析軟件的多個測試執(zhí)行的歷史信息以定位程序缺陷。本文工作與第二類工具緊密相關(guān)，因此，本節(jié)主要討論統(tǒng)計調(diào)試工具的相關(guān)研究，這類工具主要表現(xiàn)為兩種形態(tài)：獨立工具形式和集成開發(fā)環(huán)境形式。

4.1 獨立工具形式

獨立形式的調(diào)試工具內(nèi)化了缺陷定位算法，通過分析程序靜態(tài)信息并收集程序運行信息指導程序員定位軟件缺陷，有自己一套可視化的圖形用戶接口。例如，早期的數(shù)據(jù)呈現(xiàn)調(diào)試器(data display debugger，DDD)通過分析一次執(zhí)行過程中的程序指令序列指導程序員發(fā)現(xiàn)軟件缺陷，并且支持程序員單步執(zhí)行以分析軟件行為，提供軟件局部變量(對象)的狀態(tài)信息[18]。后來文獻[10]提出的Tarantula 進一步統(tǒng)計程序多次執(zhí)行(成功和失敗)過程中的覆蓋信息，借助一個懷疑度計算公式度量程序中每一個語句(程序?qū)嶓w)的可疑度，并用不同顏色在程序代碼上標識加以區(qū)分。自此大批基于統(tǒng)計缺陷定位的軟件調(diào)試工具開始涌現(xiàn)。如Sober[19]、Ochiai[20]、Crosstab[21]、Zoltar[22]、DStar[23]等。Mecca 等[24]通過引入ACME(演化變體的代碼動畫)，首次建立一個可擴展的代碼可視化工具。這些方法大多只是用顏色標記程序?qū)嶓w出錯的概率，或者簡單給出程序執(zhí)行語句上下文信息；與他們不同是，我們的方法不僅優(yōu)化了啟發(fā)式(上下文)信息并可視化這些信息以輔助程序調(diào)試，還能根據(jù)程序員的反饋動態(tài)調(diào)整缺陷定位報告，從而能夠進一步提升缺陷定位效率。

4.2 集成開發(fā)環(huán)境形式

軟件開發(fā)人員傾向于使用相對更舒適的工具。集成軟件開發(fā)環(huán)境通常會提供許多輔助軟件開發(fā)的工具，這些工具不僅可以提供有關(guān)代碼編輯的有用功能(如行號和語法高亮顯示)，而且還可以提供有關(guān)項目組織、代碼完成、集成幫助，以及在給定階段進行斷點和查看系統(tǒng)狀態(tài)的功能，也可以分步執(zhí)行以分析每一行的系統(tǒng)行為。與IDE 不同，在程序員編輯源代碼的同一環(huán)境中，許多工具相互作用在一起，因此自動軟件調(diào)試工具往往是獨立的解決方案，通常以插件的形式被安裝到集成開發(fā)環(huán)境。分析整個系統(tǒng)的一種方法是使用代碼覆蓋工具，利用這些工具可以查看在系統(tǒng)測試運行期間執(zhí)行了哪些代碼行。通過此信息，可以查看程序是否按預期運行，如果不運行，則查看哪些行與系統(tǒng)故障有關(guān)。例如，早期Hoffmann 等[25]提出的基于集成開發(fā)環(huán)境Eclipse 的插件EclEmma，能依據(jù)IDE 收集的覆蓋信息，使用不同的顏色來顯示它是否已執(zhí)行(不計算其失敗概率)，分別為完全執(zhí)行(綠色)、部分執(zhí)行(黃色)和未執(zhí)行(紅色)。后來，Bouillon 等[26]提出的EZUnit 能夠在利用顏色標識代碼是否執(zhí)行的基礎(chǔ)上，進一步給出某次測試用例執(zhí)行時的程序調(diào)用圖。Lin 等[27]開發(fā)了一個Demo 版的Eclipse 插件Microbat，其建立在輕量級人類反饋的基礎(chǔ)上，并將反饋視為程序的一部分推斷程序執(zhí)行的可疑步驟。最新版本的SonarSource 提供了SonarLint IDE 開發(fā)插件，基于代碼的靜態(tài)分析技術(shù)，支持20 多種編程語言代碼的掃描，并提供詳細的問題分析和缺陷修復建議[28]。在預測缺陷方面，曲豫賓等[29]引入基于信息熵的主動學習策略，提升人工標注的準確性，從而提高了預測缺陷的準確度。雖然與開發(fā)環(huán)境集成增加了調(diào)試工具的開發(fā)難度，但一方面軟件開發(fā)人員更習慣使用熟悉的IDE 定位并修復缺陷，另一方面集成到開發(fā)環(huán)境有助于從開發(fā)環(huán)境獲取程序的運行信息(如覆蓋信息、執(zhí)行結(jié)果等)，不需要額外開發(fā)跟蹤工具，降低了工作量。與這類工具相比，本文的方法增加了基于程序員調(diào)試反饋的動態(tài)調(diào)整過程。

需要指出的是，目前的調(diào)試工具提供的可視化信息作用還十分有限，對程序員的調(diào)試反饋利用也很少，導致開發(fā)人員浪費大量的時間來嘗試理解調(diào)試工具處理的所有信息。開發(fā)人員必須在調(diào)試過程中于應用程序之間進行切換(在一個工具中查找軟件故障并在另一個工具中對其進行糾正)，并且無法獲得IDE 集成的所有好處，例如項目和源代碼檢測，甚至與代碼交互的編輯器，這無疑會增加調(diào)試過程中的時間代價。

5 結(jié)論與展望

本文提出了一種基于反饋優(yōu)化的啟發(fā)式軟件調(diào)試框架，通過可視化展示缺陷相關(guān)的上下文信息，旨在迭代地指導定位缺陷的根本原因，同時能根據(jù)程序員當前的反饋，優(yōu)化已有的缺陷定位報告，從而優(yōu)化下一輪的缺陷調(diào)試。初步的實驗表明，本文的方法能夠在較大程度上加速軟件調(diào)試過程。在未來工作中，首先，進一步優(yōu)化工具的界面，優(yōu)化啟發(fā)信息的內(nèi)容和表現(xiàn)形式，實現(xiàn)啟發(fā)信息可視化時的友好性；其次，考慮設(shè)計成Eclipse 插件，并和Junit 集成，以實現(xiàn)程序運行信息收集；然后，在基于程序員反饋的動態(tài)缺陷定位優(yōu)化時，考慮程序員反饋信息的正確概率，引入程序員調(diào)試反饋的歷史信息，提升動態(tài)反饋的準確度，從而得到更優(yōu)的缺陷定位報告；最后，考慮增加新功能，如動態(tài)展示程序出錯前后的執(zhí)行狀態(tài)轉(zhuǎn)換過程，增加程序員反饋的途徑等，增加推薦缺陷修復補丁等，最終提升調(diào)試的效率。