基于内存建模的测试数据自动生成方法研究
|
摘要
软件测试是保证软件质量和提高软件可靠性的主要手段,其关键和核心问题之一是测试数据的生成。测试数据自动生成技术可以降低软件的开发成本,大大提高软件测试的效率,是当今软件测试自动化领域的一个研究重点。结构测试是一种重要的软件测试方法,其针对程序内部结构的语句覆盖、分支覆盖和条件覆盖等测试问题都可以归结为面向路径的测试数据生成问题。
目前已经提出的面向路径的测试数据自动生成方法主要分三类：基于符号执行的静态方法、基于程序实际执行的动态方法和基于动态符号执行的动静结合的方法。这些方法大部分针对数值型变量的测试数据自动生成。复杂结构体、字符串和数组是C语言中常用的数据类型,并且在实际程序中有广泛的应用。传统的符号执行方法很难模拟这些变量在程序执行过程中的操作语义,而动态方法又很难构造适合这些变量的适应值函数。
为此,本文提出一种静态的基于内存建模的测试数据自动生成方法,该方法可以自动生成能执行被测路径的复杂结构体、字符串和数组测试数据。本文主要完成了以下工作：
(1)创建了一种由四个抽象内存表构建的抽象内存模型：元变量抽象内存表PMTable、结构变量抽象内存表STMTable、字符串变量抽象内存表SRMTable和数组变量抽象内存表ARMTable。该抽象内存模型可以精准的记录复杂结构体、字符串和数组变量在程序执行过程中的状态。
(2)设计了复杂结构体、字符串和数组变量在抽象内存模型中的操作规则：通过对抽象内存模型的操作可以模拟指向复杂结构体和字符串的指针操作；字符串常用的库函数操作可以准确的映射到对抽象内存模型的操作；通过对抽象内存模型的操作可以模拟动态下标对应的数组元素的操作。
(3)提出了基于该抽象内存模型的复杂结构体、字符串和数组测试数据自动生成算法。利用此抽象内存模型辅助符号执行被测路径,把路径执行过程中复杂结构体、字符串和数组变量的语义操作映射到对抽象内存的操作,通过抽象内存来精准的记录路径的约束条件。并设计了一种分两步进行字符串和数组路径约束条件求解的方法,首先对字符串长度、字符串中受约束字符的位置、数组长度和数组中动态下标变量进行约束求解,之后再对字符串中确定位置的字符元素和数组中确定下标的元素进行求解,从而提高了求解效率并且解决了数组动态下标问题。
(4)对所提算法进行实例分析,并且在自动单元测试系统UATS基础上对该方法进行了实验,实验结果证明了该方法的可行性。
Software testing plays an important role in the process of guaranteeing software quality and reliability. Structural testing is an important technique of software testing, and most sutructural testing method such as statement coverage, branch coverage, condition converage can be come down to Path-oriented test data generation. Test data generation is a key element of software testing, and automatic generation of it can greatly improve the efficiency of software testing. A number of different automatic test data generation methods for structural testing have been investigated, and these methods can be divided into three categories:static method based on symbolic execution, dynamic method based on concrete execution and dynamic symbolic execution, but most of them are aiming at numerical variables.
Complex structure, string and array are fundamental data type in C programming language, and have wide usage in practical application. However, it is hard to automaticly generate complex structure, string and array test data for a path. Symbolic execution is the main technology of static test data generation method, but traditional symbolic execution is hardly to simulate semantic operation of these kinds of variables. Dynamic test data generation method based on concrete execution is hardly to construct suitable fitness functions of these variables.
So we propose a static memory-modeling based automatic test data generation method, which can automaticly generate complex structural, string and array test data for the tested path.
Creative works in this dissertation are mainly focused on the following aspects:
(1) We present an abstract memory model which contains four abstract memory tables:PMTable used to describe numerical variable, STMTable used to describe structural variable, SRMTable used to describe string variable and ARMTable used to describe array variable. The abstract memory model can exactly record the state of complex structure, string and array variable on execution of the tested program.
(2) We make an rule of the operation of complex structure, string and array variable on the abstract memory model:the operation of pointers pointing to complex structure and string can be simulated by the operation on the abstract memory model; commonly used string library function's operation can be mapped to the operation on the abstract memory model; the operation of array elements with dynamic subscript can be mapped to the operation on the abstract memory model.
(3) We present the test data generation algorithm for complex structure, string and array variable based on the abstract memory model. The semantic operation of the statement of complex structure, string and array variable is mapped to the operation of abstract memory on symbolic execution of the path, and the constraint of the path is recorded exactly in the abstract memory. And we present a two-step constraint solving method which is used to solve path constraints on string and array variable, we firstly solve the constraints on string length, the location of special constrained char element in string, array lengh and array dynamic subscript variable, then solve the path constraints on char element in string and array element with fixed location, and this method improve the efficiency of constraint solving and solve the dynamic array subscript problem.
(4) We analyze the algorithm with instance and implement the algorithm in an automatic unit test tool called UATS, and the results of experiments prove that this method is feasible.
目前已经提出的面向路径的测试数据自动生成方法主要分三类：基于符号执行的静态方法、基于程序实际执行的动态方法和基于动态符号执行的动静结合的方法。这些方法大部分针对数值型变量的测试数据自动生成。复杂结构体、字符串和数组是C语言中常用的数据类型,并且在实际程序中有广泛的应用。传统的符号执行方法很难模拟这些变量在程序执行过程中的操作语义,而动态方法又很难构造适合这些变量的适应值函数。
为此,本文提出一种静态的基于内存建模的测试数据自动生成方法,该方法可以自动生成能执行被测路径的复杂结构体、字符串和数组测试数据。本文主要完成了以下工作：
(1)创建了一种由四个抽象内存表构建的抽象内存模型：元变量抽象内存表PMTable、结构变量抽象内存表STMTable、字符串变量抽象内存表SRMTable和数组变量抽象内存表ARMTable。该抽象内存模型可以精准的记录复杂结构体、字符串和数组变量在程序执行过程中的状态。
(2)设计了复杂结构体、字符串和数组变量在抽象内存模型中的操作规则：通过对抽象内存模型的操作可以模拟指向复杂结构体和字符串的指针操作；字符串常用的库函数操作可以准确的映射到对抽象内存模型的操作；通过对抽象内存模型的操作可以模拟动态下标对应的数组元素的操作。
(3)提出了基于该抽象内存模型的复杂结构体、字符串和数组测试数据自动生成算法。利用此抽象内存模型辅助符号执行被测路径,把路径执行过程中复杂结构体、字符串和数组变量的语义操作映射到对抽象内存的操作,通过抽象内存来精准的记录路径的约束条件。并设计了一种分两步进行字符串和数组路径约束条件求解的方法,首先对字符串长度、字符串中受约束字符的位置、数组长度和数组中动态下标变量进行约束求解,之后再对字符串中确定位置的字符元素和数组中确定下标的元素进行求解,从而提高了求解效率并且解决了数组动态下标问题。
(4)对所提算法进行实例分析,并且在自动单元测试系统UATS基础上对该方法进行了实验,实验结果证明了该方法的可行性。
Software testing plays an important role in the process of guaranteeing software quality and reliability. Structural testing is an important technique of software testing, and most sutructural testing method such as statement coverage, branch coverage, condition converage can be come down to Path-oriented test data generation. Test data generation is a key element of software testing, and automatic generation of it can greatly improve the efficiency of software testing. A number of different automatic test data generation methods for structural testing have been investigated, and these methods can be divided into three categories:static method based on symbolic execution, dynamic method based on concrete execution and dynamic symbolic execution, but most of them are aiming at numerical variables.
Complex structure, string and array are fundamental data type in C programming language, and have wide usage in practical application. However, it is hard to automaticly generate complex structure, string and array test data for a path. Symbolic execution is the main technology of static test data generation method, but traditional symbolic execution is hardly to simulate semantic operation of these kinds of variables. Dynamic test data generation method based on concrete execution is hardly to construct suitable fitness functions of these variables.
So we propose a static memory-modeling based automatic test data generation method, which can automaticly generate complex structural, string and array test data for the tested path.
Creative works in this dissertation are mainly focused on the following aspects:
(1) We present an abstract memory model which contains four abstract memory tables:PMTable used to describe numerical variable, STMTable used to describe structural variable, SRMTable used to describe string variable and ARMTable used to describe array variable. The abstract memory model can exactly record the state of complex structure, string and array variable on execution of the tested program.
(2) We make an rule of the operation of complex structure, string and array variable on the abstract memory model:the operation of pointers pointing to complex structure and string can be simulated by the operation on the abstract memory model; commonly used string library function's operation can be mapped to the operation on the abstract memory model; the operation of array elements with dynamic subscript can be mapped to the operation on the abstract memory model.
(3) We present the test data generation algorithm for complex structure, string and array variable based on the abstract memory model. The semantic operation of the statement of complex structure, string and array variable is mapped to the operation of abstract memory on symbolic execution of the path, and the constraint of the path is recorded exactly in the abstract memory. And we present a two-step constraint solving method which is used to solve path constraints on string and array variable, we firstly solve the constraints on string length, the location of special constrained char element in string, array lengh and array dynamic subscript variable, then solve the path constraints on char element in string and array element with fixed location, and this method improve the efficiency of constraint solving and solve the dynamic array subscript problem.
(4) We analyze the algorithm with instance and implement the algorithm in an automatic unit test tool called UATS, and the results of experiments prove that this method is feasible.
引文
[1]Boehm B W. The high cost of software. Practical Strategies for Developing Large Software Systems,1975:3-15.
[2]Martin J, McClure C. Software Maintenance:The Problem and Its Solutions, Englewood Cliffs, NJ:Prentice Hall,1983.
[3]Huang J C. Program Instrumentation and Software Testing. Computer, Apr.1978.
[4]Goodenough J B, Gehtart S L. Toward a Theory of Test Data Selection. In IEEE Transactionsons on software Engineering, June 1975, Vol.SE-1.
[5]Zhang J. A path-based approach to the detection of infinite looping. In 2nd Asia-Pacific Conference on Quality Software (APAQS'01),2001:88-94
[6]Zitser M, Lippmann R, and Leek T. Testing static analysis tools using exploitable buffer overflows from open source code, In ACM Symposium on the Foundations of Software Engineering,2004:97-106.
[7]朱鸿,金凌紫.软件质量保障与测试[M].北京：科学出版社,1997.
[8]郑人杰.计算机软件测试技术[M].北京：清华大学出版社,1992.
[9]李留英.UML测试技术的研究与实现[博士学位论文].北京：国防科学技术大学研究生院,2000.
[10]暴建民,杨孝宗,杨楠等.测试数据选择理论20年[J].软件学报,1996,7(12)：743～751.
[11]Gotlieb A., Denmat Tristan, Botella B. Goal-oriented test data generation for programs with pointer variables, In Proceedings of the 29th Annual International Computer Software and Applications Conference,2005:449-454.
[12]Korel B. Automated test data generation for programs with procedures. In International Symposium on Software Testing and Analysis (ISSTA'96),1996: 209-215.
[13]单锦辉.面向路径的测试数据自动生成方法研究[博士学位论文].北京：国防科技大学研究生院,2002.
[14]Chen T Y, Leung H, Mak I K. Adaptive random testing. In 9th Asian Computing Science Conference, LNCS 3321,2004:320-329.
[15]Ferguson R. Korel B. The chaining approach for software test data generation. IEEE Transactions on Software Engineering, January 1996,5(1):63-86.
[16]Korel B, Al-Yami A.M. Assertion-oriented automated test data generation. In 18thInternational Comference on Software Engineering (ICSE'96),1996:71-86.
[17]Edvardsson J. A survey on automatic test data generation. In Proceeding of the Second Conference on Computer and Engineering in Linkoping, ECSEL, Oct.1999: 21-28.
[18]IEEE Standard Glossary, IEEE Std 729-1983.
[19]Dijkstra E W. Notes on Structured Programming. Structure Programming. Academic Press,1972.
[20]Roger S.Pressman.软件工程实践者的研究方法[M].北京：机械工业出版社.2002.
[21]张海藩.软件工程导论(第四版)[M].北京：清华大学出版社,2003.
[22]Offutt A J, Jin Z Y, Pan J.The Dynamic Domain Reduction Procedure for Test Data Generation. Software Practice and Experience, January 1997,29(2):167-193.
[23]Beizer B. Software testing techniques[M]. Dreamtech Press,2002.
[24]赵瑞莲.软件测试[M].北京：高等教育出版社.2004.
[25]Zhu H. A Formal Analysis of the Subsume Relation Between Software Test Adequacy Criteria. IEEE Transaction on Software Engineering.1996,22(4):248-255.
[26]Myers G J, Sandier C, Badgett T. The art of software testing. Wiley,2011.
[27]Howden W. Weak Mutation Testing and Completeness of Test Sets. IEEE Transaction on Software Engineering,1982,8(4):371-379.
[28]Woodward M R, Halewook K. From Weak to Strong, Dead or Alive? An Analysis of Some Mutation Testing Issues, In Proceedings of Second Workshop Software Testing, Verification and Analysis. Banff, Canada,1988:152-158.
[29]严俊.基于约束求解的自动化软件测试研究[博士学位论文].北京：中国科学院研究生院,2007.
[30]Ramanmoorthy C, SIU-BUN F Ho, Chen W. On the automated generation of program test data. IEEE Transactions on Software Engineering,1976, SE-2(4):293-300.
[31]King J C. Symbolic execution and program testing. Communications of the ACM, July 1976,19(7):385-394.
[32]Boyer R, Elspas B, Levitt K. SELECT-a formal system for testing and debugging programs by symbolic execution. In Proceedings of the International Conference on Reliable Software, pages 234-245,1975.
[33]Xu Z X, Zhang J. A test data generation tool for unit testing of C programs. In Proceedings of the Sixth International Conference on Quality Software. Washington D C:IEEE Computer Society Press,2006:107-116.
[34]Zhang J. Symbolic execution of program paths involving pointer and structure variables. In Proceedings of the Fourth International Conference on Quality Software, Washington D C:IEEE Computer Society Press,2004:87-92.
[35]Korel B. Automated software test data generation. IEEE Transactions on Software Engineering,1990,16(8):870-879.
[36]McMinn P. Search-based software test data generation:a survey. Software Testing, Verification and Reliability,2004,14(2):105-156.
[37]薛云志,陈伟,王永吉,等.一种基于Messy GA的结构测试数据自动生成方法[J]。软件学报,2006,17(8)：1688-1697.
[38]Godefroid P, Klarlund N, Sen K. DART:Directed automated random testing. In Proceedings of the 2005 ACM SIGPLAN Conference on Programming Language Design and Implementation, pages 213-223,2005.
[39]Sen K, Marinov D, Agha G. CUTE:a concolic unit testing engine for C. In Proceedings of the 10th European Software Engineering Conference Held Jointly with 13th ACM SIGSOFT International Symposium on Foundations of Software Engineering (ESEC/FSE'05). New York:ACM Press,2005:263-272.
[40]Godefroid P. Compositional dynamic test generation. In Proceedings of the 2007 POPL Conference. New York:ACM Press,2007:47-54.
[41]Godefroid P, Levin M Y, Molnar D. Automated whitebox fuzz testing, In Proceedings of the Network and Distributed Systems Security Symposium, Feb,2008.
[42]Cadar C, Ganesh V, Pawlowski P M, et al. EXE:automatically generating inputs of death. ACM Transactions on Information and System Security (TISSEC),12(2),2008: 10
[43]Godefroid P, Kinder J. Proving memory safety of floating-point computations by combining static and dynamic program analysis. In:Proceedings of the 19th international symposium on Software testing and analysis,2010:1-12
[44]Miller W, Spooner D L. Automatic generation of floating-point Test Data. IEEE Tracsactions on software engineering, September 1976, SE-2(3):223-226
[45]Burnim J, Sen K. Heuristics for Scalable Dynamic Test Generation. In Proceedings of the 23th IEEE International Conference on Automated Software Engineering. Washington D C:IEEE Computer Society Press,2008:443-446.
[46]Majumdar R, Sen K. Hybrid Concolic Testing. In the 29th International Conference on Software Engineering,2007:416-426.
[47]Wang Z, Yu X, Sun T, et al. Test Data generation for Derived Types in C Program. In Third IEEE International Symposium on Theoretical Aspects of Software Engineering. 2009,155-162.
[48]Gallagher M, Narasimhan V L. ADTEST:A test data generation suite for ada software systems. IEEE Transactions on Software Engineering,1997,23(8):473-484.
[49]Xie X, Lu Y. Extended Combination Testing:Generates Array Test Suite. In IEEE International Symposium on Parallel and Distributed Processing with Applications, 2009:685-690.
[50]Lin M X, Chen Y L, Yu K, et al. Lazy Symbolic Evaluation and its Path Constraints Solution. In Proceedings of Automation of Software Test,2009:79-87.
[51]林梦香,陈胤立,陈睿,等.基于懒替换的C符号执行.北京航空航天大学学报.2009,35(6)：687-691.
[52]Venet A, Brat G. Precise and efficient static array bound checking for large embedded C programs. In PLDI,2004:231-242.
[53]Lakhotia K, McMinn P, Harman M. Automated Test Data Generation for Coverage: Haven't We Solved This Problem Yet? Testing:Academic and Industrial Conference-Practice and Research Techniques,2009:95-104.
[54]Visvanathan S, Gupta N. Generating test data for functions with pointer inputs. In Proceedings of the 17th IEEE International Conference on Automated Software Engineering. Washington D C:IEEE Computer Society Press,2002:149-160
[55]Sai-ngern S, Lursinsap C, Sophatsathit P. An address mapping approach for test data generation of dynamic linked structures. Information and Software Technology,2005, 47(3):199-214.
[56]单锦辉,王戟,齐治昌.面向路径的测试数据自动生成方法述评[J].电子学报,2004,32(1)：109-113
[57]Lyu M R, Rangarajan S, Moorsel A P. Optimal allocation of test resources for software reliablility growth modeling in software development. IEEE Transactions on Reliability,2002,51(2):183-192.
[58]Zhao R L, Lyu M R. Character string predicate based automatic software test data generation. In Proceedings of the Third International Conference on Quality Software, 2003:255-263.
[59]Zhao R L, Lyu M R, Min Y H. Automatic string test data generation for detecting domain errors. Software Testing, Verification and Reliability,2010,20:209-236.
[60]Alshraideh M, Bottaci L. Search-Based software test data generation for string data using program-specific search operators. Software Testing, Verification and Reliability,2006,16:175-203.
[61]Ruan H, Zhang J, Yan J. Test Data Generation for C Programs with String-handling Functions. In proceedings of the second IFIP/IEEE International Symposium on Theoretical Aspects of Software Engineering,2008:219-226,
[62]Xu Z X, Kremenek T, Zhang J. A memory model for static analysis of C programs. In Leveraging Applications of Formal Methods, Verification, and Validation, Springer, 2010:535-548.
[63]Bjorner N, Tillmann N, Voronkov A. Path feasibility analysis for string-manipulating programs. In Tools and Algorithms for the Construction and Analysis of Systems, Springer,2009:307-321.
[64]Kiezun A, Ganesh V, Guo P J, et.al. HAMPI:a solver for string constraints. In Proceedings of the eighteenth International Symposium on Software Testing and Analysis,2009:105-116.
[65]DeMillo R A, Offutt A J. Constraint-based automatic test data generation. IEEE Transactions on Software Engineering, September 1991,17(9):900-910.
[66]Chung L, Bieman J M. Generating input data structures for automated program testing. Software Testing, Verification and Reliablity,2009,19(1):3-36.
[67]Xu Z, Zhang J. SimC:Automatic Test Data Generation for Unit C Programs. In Proceedings of the Sixth International Conference on Quality Software,2004: 107-116.
[68]Zhang J. Symbolic execution of program paths involving pointer and structure variables. In Proceedings of the Fourth International Conference on Quality Software, 2004:87-92.
[69]Tillmann N, Halleux J D. Pex-white box test generation for.NET. In Tests and Proofs, Springer,2008:134-153.
[70]刘克,单志广,王戟,等.“可信软件基础研究”重大研究计划综述[J].中国科学基金,22(003),2008：145-151.
[71]郑人杰.计算机软件测试技术[M].北京：清华大学出版社,1992.
[72]Zhu H, Hall P. Test Data Adequaey Measurement. Software Engineer Journal,1993, Vol.8, No.l, pp.21-30.
[73]Zhu H, A Fomral Analysis of the Subsume Relation Between Sotfware Test Adeuqaey Criteria, IEEE Transactions on Software Engineering,1996,22(4), pp.248-255.
[74]梅宏,王千祥,张路,等.软件分析技术进展[J].计算机学报,32(9),2009：1697-1710.
[75]宫云战,杨朝红,金大海,等.软件缺陷模式与测试[M].科学出版社,2011.
[76]W.S.Humphrey. The quality attitude. news@sei 2004, Number 3, http://www.sei.cmu.edu/library/abstracts/news-at-sei/wattsnew20043.crm
[77]Cadar C, Dunbar D, Engler D. KLEE:Unassisted and automatic generation of high-coverage tests for complex systems programs. In Proceedings of the 8th USENDC conference on Operating systems design and implementation,2008: 209-224.
[78]Jeannet B, Mine A. Apron:A library of numerical abstract domains for static analysis [C]. In:CAV,2009:661-667.
[79]Clarke L A. A system to generate test data and symbolically execute programs. IEEE Transactions on software engineering,1976:215-222.
[80]Zhang J, Chen X, Wang X. Path-oriented test data generation using symbolic execution and constraint solving techniques. In Proceedings of the Second International Conference on Software Engineering and Formal Methods,2004: 242-250.
[81]Xu Z X, Zhang J. Path and context sensitive inter-procedural memory leak detection. In The Eighth International Conference on Quality Software,2008:412-420.
[82]Flanagan C, Qadeer S. Predicate abstraction for software verification. In:POPL,2002: 191-202.
[83]Ball T, Majumdar R, Millstein T, et al. Automatic predicate abstraction of C programs. In:PLDI,2001:203-213.
[84]D'Silva V, Kroening D, Weissenbacher G. A survey of automated techniques for formal software verification. Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on,27(7),2008:1165-1178.
[85]Gent I P, Jefferson C, Miguel I. Minion:A fast, scalable, constraint solver. In: Proceedings of the 2006 conference on ECAI 2006,2006:98-102.
[86]Gulwani S, Srivastava S, Venkatesan R. Program analysis as constraint solving. ACM SIGPLAN Notices,43(6),2008:281-292.
[87]Gotlieb A, Botella B, Rueher M. Automatic test data generation using constraint solving techniques. In:Proceedings of the 1998 ACM SIGSOFT international symposium on Software testing and analysis,1998:53-62.
[88]Tillmann N, De Halleux J. Pex-white box test generation for. net. Tests and Proofs, 2008:134-153.
[89]Ernst M D. Static and dynamic analysis:Synergy and duality. In:ICSE Workshop on Dynamic Analysis,2003:24-27.
[90]Zhang R, Huang S, Qi Z, et al. Combining Static and Dynamic Analysis to Discover Software Vulnerabilities. In:Fifth International Conference on Innovative Mobile and Internet Services in Ubiquitous Computing (IMIS),2011:175-181.
[91]Csallner C, Smaragdakis Y. Check 'n' crash:combining static checking and testing. In: Proceedings of the 27th international conference on Software engineering,2005: 422-431.
[92]Zhang S, Saff D, Bu Y, et al. Combined static and dynamic automated test generation. In:Proceedings of the 2011 International Symposium on Software Testing and Analysis,2011:353-363.
[93]Pingali K, Cook W. Pointer Analysis:Building a Foundation for Effective Program Analysis. [Dissertation], The University of Texas at Austin,2009.
[94]Andersen L O. Program analysis and specialization for the C programming language. [Dissertation], University of Cophenhagen,1994.
[95]Hind M. Pointer analysis:haven't we solved this problem yet?. In:Proceedings of the 2001 ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering,2001:54-61.
[96]Lhotak O, Chung K C A. Points-to analysis with efficient strong updates. In:POPL, 2011:3-16.
[97]Steensgaard B. Points-to analysis in almost linear time. In:POPL,1996:32-41.
[98]Pearce D J, Kelly P H J, Hankin C. Efficient field-sensitive pointer analysis for C.In Proceedings of the 5th ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering, June 07-08,2004, Washington DC, USA.
[99]Nguyen T V N, Irigoin F. Efficient and effective array bound checking. ACM Transactions on Programming Languages and Systems (TOPLAS),27(3),2005: 527-570.
[100]Kim S W, Choe K M. String analysis as an abstract interpretation. In:Proceedings of the 12th international conference on Verification, model checking, and abstract interpretation,2011:294-308.
[101]Avots D, Dalton M, Livshits V B, et al. Improving software security with a C pointer analysis. In:Proceedings of the 27th international conference on Software engineering, 2005:332-341.
[102]Necula G, McPeak S, Rahul S, et al. CIL:Intermediate language and tools for analysis and transformation of C programs. In:Compiler Construction,2002:209-265.
[103]Pasareanu C, Visser W. A survey of new trends in symbolic execution for software testing and analysis. International Journal on Software Tools for Technology Transfer (STTT),11(4),2009:339-353.
[104]Zhu J, Calman S. Symbolic pointer analysis revisited. In:PLDI,2004:145-157.
[105]Gutzmann T, Lundberg J, Lowe W. Towards path-sensitive points-to analysis. In: Seventh IEEE International Working Conference on Source Code Analysis and Manipulation,2007:59-68.
[106]Steven S. Muchnick. Advanced compiler design implementation. Morgan Kaufinann, 1997.
[107]Sagiv M, Reps T, Wilhelm R. Parametric shape analysis via 3-valued logic. ACM Transactions on Programming Languages and Systems (TOPLAS),24(3),2002: 217-298.
[108]Zheng X, Rugina R. Demand-driven alias analysis for C. In:POPL,2008:197-208.
[109]Waddell O, Dybvig R. Fast and effective procedure inlining. Static Analysis,1997: 35-52.
[110]Dillig I, Dillig T, Aiken A. Sound, complete and scalable path-sensitive analysis. In: PLDI,2008:270-280.
[111]Balakrishnan G, Sankaranarayanan S, Ivancic F, et al. SLR:Path-sensitive analysis through infeasible-path detection and syntactic language refinement. Static Analysis, 2008:238-254.
[112]Thakur A, Govindarajan R. Comprehensive path-sensitive data-flow analysis. In: Proceedings of the 6th annual IEEE/ACM international symposium on Code generation and optimization,2008:55-63.
[113]Evans D, Larochelle D. Improving security using extensible lightweight static analysis. IEEE Software,19(1),2002:42-51.
[114]Holzmann G J. Static source code checking for user-defined properties. In:Proc. Integrated Design and Process Technology (IDPT), vol.2,2002.
[115]Zhu H, Hall P, May J. Software unit test coverage and adequancy. ACM Computing Surveys, Dec 1997,29(4):366-427.
[116]Weyuker E, Rapps S. Selecting software test data using data flow information. IEEE Transactions on Software Engineering, Apr.1985.
[117]Ntafos S. On required element testing. IEEE Transactions on Software Engineering, 1984,10(6):795-803.
[118]Laski J, Korel B. A data flow oriented program testing strategy. IEEE Transactions on Software Engineering,1983,9(3):347-354.
[119]Howden W E. Reliablity of the path analysis testing strategy. IEEE Transactions on Software Engineering,1976(3):208-215.
[120]宫云战.软件测试[M].北京：国防工业出版社,2006.
[121]http://Pmd.sourceforge.net/
[122]http://findbugs.sourceforge.net/
[123]http://www.coverity.com/
[124]http://www.klocwork.com/
[125]赵瑞莲.软件测试方法研究[博士学位论文].北京：中国科学院研究生院,2001.
[126]Kung D. Design recovery for software testing of object-oriented programs. In Proceedings of Working Conference on Reverse Engineering, IEEE Computer Society Press,1993,202-211.
[127]Doong R, Frankl P. The ASTOOT approach to testing object-oriented program. ACM Transactions on Software Engineering and Methodlogy,1994,3(2),101-130.
[128]Chen H, Tse T, Chan F, et al. In Black and White:an integrated approach to class-level testing of object-oriented programs. ACM Transactions on Software Engineering and Methodlogy,1998,7(3),250-295.
[2]Martin J, McClure C. Software Maintenance:The Problem and Its Solutions, Englewood Cliffs, NJ:Prentice Hall,1983.
[3]Huang J C. Program Instrumentation and Software Testing. Computer, Apr.1978.
[4]Goodenough J B, Gehtart S L. Toward a Theory of Test Data Selection. In IEEE Transactionsons on software Engineering, June 1975, Vol.SE-1.
[5]Zhang J. A path-based approach to the detection of infinite looping. In 2nd Asia-Pacific Conference on Quality Software (APAQS'01),2001:88-94
[6]Zitser M, Lippmann R, and Leek T. Testing static analysis tools using exploitable buffer overflows from open source code, In ACM Symposium on the Foundations of Software Engineering,2004:97-106.
[7]朱鸿,金凌紫.软件质量保障与测试[M].北京：科学出版社,1997.
[8]郑人杰.计算机软件测试技术[M].北京：清华大学出版社,1992.
[9]李留英.UML测试技术的研究与实现[博士学位论文].北京：国防科学技术大学研究生院,2000.
[10]暴建民,杨孝宗,杨楠等.测试数据选择理论20年[J].软件学报,1996,7(12)：743～751.
[11]Gotlieb A., Denmat Tristan, Botella B. Goal-oriented test data generation for programs with pointer variables, In Proceedings of the 29th Annual International Computer Software and Applications Conference,2005:449-454.
[12]Korel B. Automated test data generation for programs with procedures. In International Symposium on Software Testing and Analysis (ISSTA'96),1996: 209-215.
[13]单锦辉.面向路径的测试数据自动生成方法研究[博士学位论文].北京：国防科技大学研究生院,2002.
[14]Chen T Y, Leung H, Mak I K. Adaptive random testing. In 9th Asian Computing Science Conference, LNCS 3321,2004:320-329.
[15]Ferguson R. Korel B. The chaining approach for software test data generation. IEEE Transactions on Software Engineering, January 1996,5(1):63-86.
[16]Korel B, Al-Yami A.M. Assertion-oriented automated test data generation. In 18thInternational Comference on Software Engineering (ICSE'96),1996:71-86.
[17]Edvardsson J. A survey on automatic test data generation. In Proceeding of the Second Conference on Computer and Engineering in Linkoping, ECSEL, Oct.1999: 21-28.
[18]IEEE Standard Glossary, IEEE Std 729-1983.
[19]Dijkstra E W. Notes on Structured Programming. Structure Programming. Academic Press,1972.
[20]Roger S.Pressman.软件工程实践者的研究方法[M].北京：机械工业出版社.2002.
[21]张海藩.软件工程导论(第四版)[M].北京：清华大学出版社,2003.
[22]Offutt A J, Jin Z Y, Pan J.The Dynamic Domain Reduction Procedure for Test Data Generation. Software Practice and Experience, January 1997,29(2):167-193.
[23]Beizer B. Software testing techniques[M]. Dreamtech Press,2002.
[24]赵瑞莲.软件测试[M].北京：高等教育出版社.2004.
[25]Zhu H. A Formal Analysis of the Subsume Relation Between Software Test Adequacy Criteria. IEEE Transaction on Software Engineering.1996,22(4):248-255.
[26]Myers G J, Sandier C, Badgett T. The art of software testing. Wiley,2011.
[27]Howden W. Weak Mutation Testing and Completeness of Test Sets. IEEE Transaction on Software Engineering,1982,8(4):371-379.
[28]Woodward M R, Halewook K. From Weak to Strong, Dead or Alive? An Analysis of Some Mutation Testing Issues, In Proceedings of Second Workshop Software Testing, Verification and Analysis. Banff, Canada,1988:152-158.
[29]严俊.基于约束求解的自动化软件测试研究[博士学位论文].北京：中国科学院研究生院,2007.
[30]Ramanmoorthy C, SIU-BUN F Ho, Chen W. On the automated generation of program test data. IEEE Transactions on Software Engineering,1976, SE-2(4):293-300.
[31]King J C. Symbolic execution and program testing. Communications of the ACM, July 1976,19(7):385-394.
[32]Boyer R, Elspas B, Levitt K. SELECT-a formal system for testing and debugging programs by symbolic execution. In Proceedings of the International Conference on Reliable Software, pages 234-245,1975.
[33]Xu Z X, Zhang J. A test data generation tool for unit testing of C programs. In Proceedings of the Sixth International Conference on Quality Software. Washington D C:IEEE Computer Society Press,2006:107-116.
[34]Zhang J. Symbolic execution of program paths involving pointer and structure variables. In Proceedings of the Fourth International Conference on Quality Software, Washington D C:IEEE Computer Society Press,2004:87-92.
[35]Korel B. Automated software test data generation. IEEE Transactions on Software Engineering,1990,16(8):870-879.
[36]McMinn P. Search-based software test data generation:a survey. Software Testing, Verification and Reliability,2004,14(2):105-156.
[37]薛云志,陈伟,王永吉,等.一种基于Messy GA的结构测试数据自动生成方法[J]。软件学报,2006,17(8)：1688-1697.
[38]Godefroid P, Klarlund N, Sen K. DART:Directed automated random testing. In Proceedings of the 2005 ACM SIGPLAN Conference on Programming Language Design and Implementation, pages 213-223,2005.
[39]Sen K, Marinov D, Agha G. CUTE:a concolic unit testing engine for C. In Proceedings of the 10th European Software Engineering Conference Held Jointly with 13th ACM SIGSOFT International Symposium on Foundations of Software Engineering (ESEC/FSE'05). New York:ACM Press,2005:263-272.
[40]Godefroid P. Compositional dynamic test generation. In Proceedings of the 2007 POPL Conference. New York:ACM Press,2007:47-54.
[41]Godefroid P, Levin M Y, Molnar D. Automated whitebox fuzz testing, In Proceedings of the Network and Distributed Systems Security Symposium, Feb,2008.
[42]Cadar C, Ganesh V, Pawlowski P M, et al. EXE:automatically generating inputs of death. ACM Transactions on Information and System Security (TISSEC),12(2),2008: 10
[43]Godefroid P, Kinder J. Proving memory safety of floating-point computations by combining static and dynamic program analysis. In:Proceedings of the 19th international symposium on Software testing and analysis,2010:1-12
[44]Miller W, Spooner D L. Automatic generation of floating-point Test Data. IEEE Tracsactions on software engineering, September 1976, SE-2(3):223-226
[45]Burnim J, Sen K. Heuristics for Scalable Dynamic Test Generation. In Proceedings of the 23th IEEE International Conference on Automated Software Engineering. Washington D C:IEEE Computer Society Press,2008:443-446.
[46]Majumdar R, Sen K. Hybrid Concolic Testing. In the 29th International Conference on Software Engineering,2007:416-426.
[47]Wang Z, Yu X, Sun T, et al. Test Data generation for Derived Types in C Program. In Third IEEE International Symposium on Theoretical Aspects of Software Engineering. 2009,155-162.
[48]Gallagher M, Narasimhan V L. ADTEST:A test data generation suite for ada software systems. IEEE Transactions on Software Engineering,1997,23(8):473-484.
[49]Xie X, Lu Y. Extended Combination Testing:Generates Array Test Suite. In IEEE International Symposium on Parallel and Distributed Processing with Applications, 2009:685-690.
[50]Lin M X, Chen Y L, Yu K, et al. Lazy Symbolic Evaluation and its Path Constraints Solution. In Proceedings of Automation of Software Test,2009:79-87.
[51]林梦香,陈胤立,陈睿,等.基于懒替换的C符号执行.北京航空航天大学学报.2009,35(6)：687-691.
[52]Venet A, Brat G. Precise and efficient static array bound checking for large embedded C programs. In PLDI,2004:231-242.
[53]Lakhotia K, McMinn P, Harman M. Automated Test Data Generation for Coverage: Haven't We Solved This Problem Yet? Testing:Academic and Industrial Conference-Practice and Research Techniques,2009:95-104.
[54]Visvanathan S, Gupta N. Generating test data for functions with pointer inputs. In Proceedings of the 17th IEEE International Conference on Automated Software Engineering. Washington D C:IEEE Computer Society Press,2002:149-160
[55]Sai-ngern S, Lursinsap C, Sophatsathit P. An address mapping approach for test data generation of dynamic linked structures. Information and Software Technology,2005, 47(3):199-214.
[56]单锦辉,王戟,齐治昌.面向路径的测试数据自动生成方法述评[J].电子学报,2004,32(1)：109-113
[57]Lyu M R, Rangarajan S, Moorsel A P. Optimal allocation of test resources for software reliablility growth modeling in software development. IEEE Transactions on Reliability,2002,51(2):183-192.
[58]Zhao R L, Lyu M R. Character string predicate based automatic software test data generation. In Proceedings of the Third International Conference on Quality Software, 2003:255-263.
[59]Zhao R L, Lyu M R, Min Y H. Automatic string test data generation for detecting domain errors. Software Testing, Verification and Reliability,2010,20:209-236.
[60]Alshraideh M, Bottaci L. Search-Based software test data generation for string data using program-specific search operators. Software Testing, Verification and Reliability,2006,16:175-203.
[61]Ruan H, Zhang J, Yan J. Test Data Generation for C Programs with String-handling Functions. In proceedings of the second IFIP/IEEE International Symposium on Theoretical Aspects of Software Engineering,2008:219-226,
[62]Xu Z X, Kremenek T, Zhang J. A memory model for static analysis of C programs. In Leveraging Applications of Formal Methods, Verification, and Validation, Springer, 2010:535-548.
[63]Bjorner N, Tillmann N, Voronkov A. Path feasibility analysis for string-manipulating programs. In Tools and Algorithms for the Construction and Analysis of Systems, Springer,2009:307-321.
[64]Kiezun A, Ganesh V, Guo P J, et.al. HAMPI:a solver for string constraints. In Proceedings of the eighteenth International Symposium on Software Testing and Analysis,2009:105-116.
[65]DeMillo R A, Offutt A J. Constraint-based automatic test data generation. IEEE Transactions on Software Engineering, September 1991,17(9):900-910.
[66]Chung L, Bieman J M. Generating input data structures for automated program testing. Software Testing, Verification and Reliablity,2009,19(1):3-36.
[67]Xu Z, Zhang J. SimC:Automatic Test Data Generation for Unit C Programs. In Proceedings of the Sixth International Conference on Quality Software,2004: 107-116.
[68]Zhang J. Symbolic execution of program paths involving pointer and structure variables. In Proceedings of the Fourth International Conference on Quality Software, 2004:87-92.
[69]Tillmann N, Halleux J D. Pex-white box test generation for.NET. In Tests and Proofs, Springer,2008:134-153.
[70]刘克,单志广,王戟,等.“可信软件基础研究”重大研究计划综述[J].中国科学基金,22(003),2008：145-151.
[71]郑人杰.计算机软件测试技术[M].北京：清华大学出版社,1992.
[72]Zhu H, Hall P. Test Data Adequaey Measurement. Software Engineer Journal,1993, Vol.8, No.l, pp.21-30.
[73]Zhu H, A Fomral Analysis of the Subsume Relation Between Sotfware Test Adeuqaey Criteria, IEEE Transactions on Software Engineering,1996,22(4), pp.248-255.
[74]梅宏,王千祥,张路,等.软件分析技术进展[J].计算机学报,32(9),2009：1697-1710.
[75]宫云战,杨朝红,金大海,等.软件缺陷模式与测试[M].科学出版社,2011.
[76]W.S.Humphrey. The quality attitude. news@sei 2004, Number 3, http://www.sei.cmu.edu/library/abstracts/news-at-sei/wattsnew20043.crm
[77]Cadar C, Dunbar D, Engler D. KLEE:Unassisted and automatic generation of high-coverage tests for complex systems programs. In Proceedings of the 8th USENDC conference on Operating systems design and implementation,2008: 209-224.
[78]Jeannet B, Mine A. Apron:A library of numerical abstract domains for static analysis [C]. In:CAV,2009:661-667.
[79]Clarke L A. A system to generate test data and symbolically execute programs. IEEE Transactions on software engineering,1976:215-222.
[80]Zhang J, Chen X, Wang X. Path-oriented test data generation using symbolic execution and constraint solving techniques. In Proceedings of the Second International Conference on Software Engineering and Formal Methods,2004: 242-250.
[81]Xu Z X, Zhang J. Path and context sensitive inter-procedural memory leak detection. In The Eighth International Conference on Quality Software,2008:412-420.
[82]Flanagan C, Qadeer S. Predicate abstraction for software verification. In:POPL,2002: 191-202.
[83]Ball T, Majumdar R, Millstein T, et al. Automatic predicate abstraction of C programs. In:PLDI,2001:203-213.
[84]D'Silva V, Kroening D, Weissenbacher G. A survey of automated techniques for formal software verification. Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on,27(7),2008:1165-1178.
[85]Gent I P, Jefferson C, Miguel I. Minion:A fast, scalable, constraint solver. In: Proceedings of the 2006 conference on ECAI 2006,2006:98-102.
[86]Gulwani S, Srivastava S, Venkatesan R. Program analysis as constraint solving. ACM SIGPLAN Notices,43(6),2008:281-292.
[87]Gotlieb A, Botella B, Rueher M. Automatic test data generation using constraint solving techniques. In:Proceedings of the 1998 ACM SIGSOFT international symposium on Software testing and analysis,1998:53-62.
[88]Tillmann N, De Halleux J. Pex-white box test generation for. net. Tests and Proofs, 2008:134-153.
[89]Ernst M D. Static and dynamic analysis:Synergy and duality. In:ICSE Workshop on Dynamic Analysis,2003:24-27.
[90]Zhang R, Huang S, Qi Z, et al. Combining Static and Dynamic Analysis to Discover Software Vulnerabilities. In:Fifth International Conference on Innovative Mobile and Internet Services in Ubiquitous Computing (IMIS),2011:175-181.
[91]Csallner C, Smaragdakis Y. Check 'n' crash:combining static checking and testing. In: Proceedings of the 27th international conference on Software engineering,2005: 422-431.
[92]Zhang S, Saff D, Bu Y, et al. Combined static and dynamic automated test generation. In:Proceedings of the 2011 International Symposium on Software Testing and Analysis,2011:353-363.
[93]Pingali K, Cook W. Pointer Analysis:Building a Foundation for Effective Program Analysis. [Dissertation], The University of Texas at Austin,2009.
[94]Andersen L O. Program analysis and specialization for the C programming language. [Dissertation], University of Cophenhagen,1994.
[95]Hind M. Pointer analysis:haven't we solved this problem yet?. In:Proceedings of the 2001 ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering,2001:54-61.
[96]Lhotak O, Chung K C A. Points-to analysis with efficient strong updates. In:POPL, 2011:3-16.
[97]Steensgaard B. Points-to analysis in almost linear time. In:POPL,1996:32-41.
[98]Pearce D J, Kelly P H J, Hankin C. Efficient field-sensitive pointer analysis for C.In Proceedings of the 5th ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering, June 07-08,2004, Washington DC, USA.
[99]Nguyen T V N, Irigoin F. Efficient and effective array bound checking. ACM Transactions on Programming Languages and Systems (TOPLAS),27(3),2005: 527-570.
[100]Kim S W, Choe K M. String analysis as an abstract interpretation. In:Proceedings of the 12th international conference on Verification, model checking, and abstract interpretation,2011:294-308.
[101]Avots D, Dalton M, Livshits V B, et al. Improving software security with a C pointer analysis. In:Proceedings of the 27th international conference on Software engineering, 2005:332-341.
[102]Necula G, McPeak S, Rahul S, et al. CIL:Intermediate language and tools for analysis and transformation of C programs. In:Compiler Construction,2002:209-265.
[103]Pasareanu C, Visser W. A survey of new trends in symbolic execution for software testing and analysis. International Journal on Software Tools for Technology Transfer (STTT),11(4),2009:339-353.
[104]Zhu J, Calman S. Symbolic pointer analysis revisited. In:PLDI,2004:145-157.
[105]Gutzmann T, Lundberg J, Lowe W. Towards path-sensitive points-to analysis. In: Seventh IEEE International Working Conference on Source Code Analysis and Manipulation,2007:59-68.
[106]Steven S. Muchnick. Advanced compiler design implementation. Morgan Kaufinann, 1997.
[107]Sagiv M, Reps T, Wilhelm R. Parametric shape analysis via 3-valued logic. ACM Transactions on Programming Languages and Systems (TOPLAS),24(3),2002: 217-298.
[108]Zheng X, Rugina R. Demand-driven alias analysis for C. In:POPL,2008:197-208.
[109]Waddell O, Dybvig R. Fast and effective procedure inlining. Static Analysis,1997: 35-52.
[110]Dillig I, Dillig T, Aiken A. Sound, complete and scalable path-sensitive analysis. In: PLDI,2008:270-280.
[111]Balakrishnan G, Sankaranarayanan S, Ivancic F, et al. SLR:Path-sensitive analysis through infeasible-path detection and syntactic language refinement. Static Analysis, 2008:238-254.
[112]Thakur A, Govindarajan R. Comprehensive path-sensitive data-flow analysis. In: Proceedings of the 6th annual IEEE/ACM international symposium on Code generation and optimization,2008:55-63.
[113]Evans D, Larochelle D. Improving security using extensible lightweight static analysis. IEEE Software,19(1),2002:42-51.
[114]Holzmann G J. Static source code checking for user-defined properties. In:Proc. Integrated Design and Process Technology (IDPT), vol.2,2002.
[115]Zhu H, Hall P, May J. Software unit test coverage and adequancy. ACM Computing Surveys, Dec 1997,29(4):366-427.
[116]Weyuker E, Rapps S. Selecting software test data using data flow information. IEEE Transactions on Software Engineering, Apr.1985.
[117]Ntafos S. On required element testing. IEEE Transactions on Software Engineering, 1984,10(6):795-803.
[118]Laski J, Korel B. A data flow oriented program testing strategy. IEEE Transactions on Software Engineering,1983,9(3):347-354.
[119]Howden W E. Reliablity of the path analysis testing strategy. IEEE Transactions on Software Engineering,1976(3):208-215.
[120]宫云战.软件测试[M].北京：国防工业出版社,2006.
[121]http://Pmd.sourceforge.net/
[122]http://findbugs.sourceforge.net/
[123]http://www.coverity.com/
[124]http://www.klocwork.com/
[125]赵瑞莲.软件测试方法研究[博士学位论文].北京：中国科学院研究生院,2001.
[126]Kung D. Design recovery for software testing of object-oriented programs. In Proceedings of Working Conference on Reverse Engineering, IEEE Computer Society Press,1993,202-211.
[127]Doong R, Frankl P. The ASTOOT approach to testing object-oriented program. ACM Transactions on Software Engineering and Methodlogy,1994,3(2),101-130.
[128]Chen H, Tse T, Chan F, et al. In Black and White:an integrated approach to class-level testing of object-oriented programs. ACM Transactions on Software Engineering and Methodlogy,1998,7(3),250-295.