軟體測試所需成本高達總成本的 50%，因此成為軟體發展(Software Development)過程中的主要瓶頸。現今發展軟體系統的趨勢，趨向於藉由輔助工具(Auxiliary Tool)來降低軟體測試(Software Testing)所需的資源，但現有測試系統大多需要使用者自行設定測試環境(Testing Driver)，測試的效能也隨之影響，主要原因是測試分析工具無法有系統地自動產生測試資料，以證明相關輸入資料可到達特定的執行環境(Program State)，這卻是我們用來印證測試效率及品質最直接的方法。本論文中，我們將以程式邏輯推論為出發點，有系統地產生測試資料(Testing Inputs)以執行所有可能路徑(Possible Paths)。我們實作了一個自動測試工具，稱為 ALERT，能自動分析程式執行時的邏輯條件(Logic Constraints)，以表示執行的語義(Execution Semantics), 藉此可推論剩下可能執行路徑的測試輸入。我們利用 gcov 來分析 ALERT 的測試效率，所自動產生的測試資料可達 90% 的涵蓋率。

摘要 iii
Abstract iv
誌謝 v
Table of Contents vi
List of Figures viii
List of Tables ix
1. Introduction - 1 -
1.1. Software Testing - 1 -
1.2. Test Strategies - 3 -
1.3. Motivation - 4 -
1.3.1. Feasible Inputs - 4 -
1.4. Objective - 5 -
1.4.1. Logic constraints extraction - 5 -
1.4.2. Runtime predicates resolution - 6 -
1.5. Synopsis - 6 -
2. Related Work - 7 -
2.1. Data Reconstruction for Cause Effect Chains - 7 -
2.2. Model Checking - 8 -
2.3. Techniques of Fault Localizers - 9 -
2.4. Symbolic Evaluation and Concrete Evaluation - 10 -
3. ALERT overview - 11 -
3.1. Instrumentation for Runtime Trace - 19 -
3.2. Generation of Runtime Constraints - 19 -
3.3. Symbolic Evaluation Framework - 20 -
3.4. Automatic Logic Evaluation - 22 -
4. Implementation - 25 -
4.1. Instrumenter - 25 -
4.1.1. Branch Oriented - 26 -
4.1.2. Condition Sensitive - 26 -
4.1.3. Function driven - 26 -
4.2. Symbolic Evaluator - 27 -
4.2.1. Paired Symbols - 27 -
4.2.2. Dependency - 30 -
4.3. Logic Resolver - 30 -
4.3.1. Variable - 30 -
4.3.2. Freezing Expression - 31 -
4.3.3. Domain Range - 31 -
4.4. Implementation Difficulties - 31 -
4.4.1. Generation of User-defined Type Interface - 32 -
4.4.2. State-sensitive Variable Renaming - 32 -
5. Experimental Results - 34 -
5.1. Instrumentation and Generation Overhead - 34 -
5.2. Expand and Explore - 34 -
5.3. Similar Path Discovery - 35 -
6. Conclusion - 37 -
6.1. Future Work - 37 -
6.1.1. Feasible Input Generation - 38 -
6.1.2. Delta Debugging - 38 -
References - 39 -

[1] "gcov: a Test Coverage Program http://gcc.gnu.org/onlinedocs/gcc-3.0/gcc_8.html,"
[2] H. Cleve and A. Zeller, "Locating causes of program failures," in ICSE '05: Proceedings of the 27th International Conference on Software Engineering, 2005, pp. 342-351.
[3] W. R. Bush, J. D. Pincus and D. J. Sielaff, "A static analyzer for finding dynamic programming errors," SPE, vol. 30, pp. 775-802, 2000.
[4] J. Whaley, M. C. Martin and M. S. Lam, "Automatic extraction of object-oriented component interfaces," in ISSTA '02: Proceedings of the 2002 ACM SIGSOFT International Symposium on Software Testing and Analysis, 2002, pp. 218-228.
[5] D. Jackson, "Aspect: detecting bugs with abstract dependences," ACM Trans. Softw. Eng. Methodol., vol. 4, pp. 109-145, 1995.
[6] D. Engler, D. Y. Chen, S. Hallem, A. Chou and B. Chelf, "Bugs as deviant behavior: A general approach to inferring errors in systems code," in SOSP '01: Proceedings of the Eighteenth ACM Symposium on Operating Systems Principles, 2001, pp. 57-72.
[7] S. Hallem, B. Chelf, Y. Xie and D. Engler, "A system and language for building system-specific, static analyses," in PLDI '02: Proceedings of the ACM SIGPLAN 2002 Conference on Programming Language Design and Implementation, 2002, pp. 69-82.
[8] H. R. and J. B., "Purify: Fast Detection of. Memory Leaks and Access Errors." Winter USENIX. Conference, 1992.
[9] P. Godefroid, N. Klarlund and K. Sen, "DART: Directed automated random testing," in PLDI '05: Proceedings of the 2005 ACM SIGPLAN Conference on Programming Language Design and Implementation, 2005, pp. 213-223.
[10] B. Demsky and M. Rinard, "Data structure repair using goal-directed reasoning," in ICSE '05: Proceedings of the 27th International Conference on Software Engineering, 2005, pp. 176-185.
[11] H. Agrawal and E. H. Spafford, "Bibliography on debugging and backtracking," SIGSOFT Softw. Eng. Notes, vol. 14, pp. 49-56, 1989.
[12] T. Wang and A. Roychoudhury, "Automated path generation for software fault localization," in ASE '05: Proceedings of the 20th IEEE/ACM International Conference on Automated Software Engineering, 2005, pp. 347-351.
[13] C. Flanagan, K. R. M. Leino, M. Lillibridge, G. Nelson, J. B. Saxe and R. Stata, "Extended static checking for java," in PLDI '02: Proceedings of the ACM SIGPLAN 2002 Conference on Programming Language Design and Implementation, 2002, pp. 234-245.
[14] lp_solve http://lpsolve.sourceforge.net/
[15] K. Sen, D. Marinov and G. Agha, "CUTE: A concolic unit testing engine for C," in ESEC/FSE-13: Proceedings of the 10th European Software Engineering Conference Held Jointly with 13th ACM SIGSOFT International Symposium on Foundations of Software Engineering, 2005, pp. 263-272.
[16] SWI-Prolog -- an LGPL comprehensive portable Prolog compiler. http://www.swi-prolog.org/
[17] zlib -- A Massively Spiffy Yet Delicately Unobtrusive Compression Library. http://www.zlib.net/