基于懒替换的C符号执行

林梦香; 陈胤立; 陈 睿; 周 刚

基于懒替换的C符号执行

1.
北京航空航天大学软件开发环境国家重点实验室, 北京 100191
2. 国家数据交换系统工程技术研究中心, 郑州 450002

基金项目: 国家863计划资助项目(2007AA010301)

详细信息

作者简介:
林梦香(1968-),女,江苏苏州人,博士生,mxlin@nlsde.buaa.edu.cn.

中图分类号: TP 311.5
计量
- 文章访问数: 3223
- HTML全文浏览量: 95
- PDF下载量: 1644
- 被引次数: 0
出版历程
- 收稿日期: 2008-05-05
- 网络出版日期: 2009-06-30

Lazy-substitution based symbolic execution for C programs

1.
State Key Lab. of Software Development Environment, Beijing University of Aeronautics and Astronautics, Beijing 100191,China
2. National Digital Switching Engineering and Technological Research Center, Zhengzhou 450002, China

摘要

摘要: 针对传统符号执行中的动态地址计算问题,提出了基于懒替换的符号执行方法.通过引入尽可能替换的策略,基于懒替换的符号执行在无法静态确定变量的地址或符号表达式过长时不做符号替换.首先给出了基于懒替换的符号执行算法,在此基础上,详细分析了C语言主要结构尤其是数组和指针的懒符号执行语义.LazySEC是一个面向C程序的懒符号执行系统原型,初步实验表明,它可以有效地处理含有指针和结构体等涉及动态地址计算的程序语言结构.
- 软件工程 /
- 程序调试 /
- 工具
Abstract: Lazy-substitution based symbolic execution was presented in order to address the computed memory location problem in traditional symbolic execution. A form of lazy strategy was introduced into traditional symbolic execution, which substitutes program variables with their symbolic values as much as possible. When the memory locations of variables in a statement can-t be determined statically or the length of a symbolic expression for substitution is too long, those variables won-t be replaced with their symbolic values. The lazy substitution algorithm was provided. Moreover, the lazy symbolic execution semantics for most of structures in C programming language were discussed in detail, especially for array and pointer. The prototype of symbolic execution system LazySEC (a lazy symbolic executor for C programs) performs lazy-substitution based symbolic execution for C programs. Preliminary experiment results show that LazySEC can handle program structures involving computed memory locations efficiently.
- software engineering /
- program debugging /
- tools

HTML全文

参考文献(1)

[1] King J C. Symbolic execution and program testing [J]. Commun ACM,1976,19(7):385-394 [2] Godefroid P, Klarlund N, Sen K. DART: Directed automated random testing ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI-05). New York:ACM,2005:213-223 [3] Godefroid P. Compositional dynamic test generation 34th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL-07). New York: ACM, 2007:47-54 [4] Coen-Porisini A, Denaro G, Ghezzi C, et al. Using symbolic execution for verifying safety-critical systems 8th European Software Engineering Conference. New York: ACM, 2001:142-151 [5] 单锦辉, 王戟, 齐治昌. 面向路径的测试数据自动生成方法述评[J]. 电子学报, 2004, 32(1):109-113 Shan Jinhui, Wang Ji, Qi Zhichang. Survey on path-wise automatic generation of test data[J]. Acta Electronica Sinica,2004,32(1):109-113(in Chinese) [6] Boyer R S, Elspas B, Levitt K N. SELECT-a formal system for testing and debugging programs by symbolic execution Proceeding of the International Conference on Reliable Software. New York: ACM, 1975:234-245 [7] Clarke L A. A system to generate test data and symbolically execute programs [J]. IEEE Transactions Software Engineering, 1976, SE-2(3):215-222 [8] Ramamoorthy C V, Ho S B, Chen W T. On the automated generation of program test data [J]. IEEE Transactions on Software Engineering, 1976, SE-2(4):293-300 [9] Zhang Jian, Wang Xiaoxu. A constraint solver and its application to path feasibility analysis [J]. International Journal of Software Engineering and Knowledge Engineering,2001,11(2):139-156 [10] Zhang Jian. Symbolic execution of program paths involving pointer and structure variables Proc of the Fourth Int Conf on Quality Software (QSIC-04). Los Alamitos: IEEE Computer Society, 2004:87-92 [11] Khurshid S, Pasareanu C, Visser W. Generalized symbolic execution for model checking and testing Tools and Algorithms for Construction and Analysis of Systems (TACAS’03). Heidelberg: Springer, 2003:553-568 [12] Coward P D. Symbolic execution and testing [J]. Information and Software Technology,1991,33(1):53-64

施引文献

资源附件(0)

访问统计