以機率方法辨識程式中可疑狀態並應用於程式的自動除錯之研究

Fault Localization with Statistical Suspicious Program States

趙品權(Pin-Chuan Chou)

指導教授 ： 黃泰一

國立清華大學/電機資訊學院/資訊工程學系/碩士(2007年)

摘要

大型的程式總是包含許多的錯誤 (bug)，這些錯誤只在特定的輸入 (Input) 下才會發生。程式除錯 (Fault Localization) 的步驟在Time-to-Market日漸重要的今天，關鍵性的決定了產品開發的速度。
為了找到程式的錯誤，程式設計師通常必須花費很多的時間在：人工檢查程式碼 (Examine codes) 和人工觀察程式狀態 (Program States) 有無異常。這兩項工作都是耗時且需要經驗的。
在自動程式除錯的研究領域，為了有效的縮短除錯時間，有許多的技術被提出來。其中程式碼覆蓋度 (Code Coverage) 被認可為最有效可找出可疑程式碼 (Suspicious Statements) 的一項技術。程式設計師只需檢查可疑的部份，而不需檢查所有的程式碼。然而，單純檢查程式碼在現實的除錯步驟當中是不夠的，一旦程式設計師無法在可疑程式碼中看出錯誤，還是必須手動一步步的去檢查程式狀態以找出程式行為的異常 (Anomaly in Program Behavior)。本研究發明了一項名為狀態覆蓋度 (State Coverage) 的技術，利用通過 (passed) 及失敗 (failed) 的測試輸入 (Test Cases)，以及在程式碼的分支敘述 (branch statement) 插入檢查點 (Check Point) 的方法，加上機率函數的計算，找出在特定位置和錯誤最有關係的程式狀態 (Fault Relevant States)。我們並利用此可疑程式狀態 (Suspicious States) 配合可疑程式碼來加速除錯的速度。
我們採用了有名的測試程式Siemens Suite來驗證我們的方法，實驗結果發現，透過狀態覆蓋這項技術，有高達22%的測試程式被我們精準的找出了錯誤。而整體而言，加上狀態覆蓋度的效率比單純使用程式碼覆蓋度高了86%。

關鍵字

自動除錯 ； 程式狀態 ； 程式碼覆蓋度

並列摘要

A state is statistically considered to be more suspicious if it appears more in failed cases and less in passed cases.
We implemented both code coverage and stage coverage in a debugging tool and used a commonly-used benchmark consisting of 58 faulty programs to evaluate their performance.
For 22% of these programs, their faults are within 10 statement steps of the most suspicious statement identified by code coverage.
By adding state coverage and breaking at the most suspicious state of this most suspicious statement, we increase this ratio to 41%, an 86% performance improvement.
Finally, we also explain a few cases in which both state coverage and code coverage cannot perform well.

並列關鍵字

Automated Debugging ； Program State ； Code Coverage

參考文獻

[6] Neelam Gupta, Haifeng He, Xiangyu Zhang, and Rajiv Gupta. Locating Faulty Code Using Failure-inducing Chops. In Proceedings of IEEE/ACM International Conference on

[2] H. Agrawal, J. Horgan, S. London, and W. Wong. Fault Localization Using Execution Slices and Datafow Tests. In Proceedings of IEEE Software Reliability Engineering, pages

143-151, 1995.

Automated Software Engineering, pages 263-272, 2005.

[7] M. J. Harrold, G. Rothermel, K. Sayre, R. Wu, and L. Yi. An Empirical Investigation of the Relationship Between Spectra Diferences and Regression Faults. Journal of Software Testing, Verification, and Reliability, 10(3):171-194, 2000.