作者投稿和查稿 主编审稿 专家审稿 编委审稿 远程编辑

计算机工程 ›› 2011, Vol. 37 ›› Issue (14): 68-69. doi: 10.3969/j.issn.1000-3428.2011.14.021

• 软件技术与数据库 • 上一篇    下一篇

基于条件值的C/C++预处理测试算法

娄坚波,刘久富,李金奎,王 伟   

  1. (南京航空航天大学自动化学院,南京 210016)
  • 收稿日期:2011-01-14 出版日期:2011-07-20 发布日期:2011-07-20
  • 作者简介:娄坚波(1986-),男,硕士研究生,主研方向:软件静态测试;刘久富,博士;李金奎、王 伟,硕士研究生
  • 基金资助:
    南京航空航天大学基本科研业务费专项科研基金资助项目(NS2010069)

Test Algorithm of C/C++ Preprocessing Based on Conditional Value

LOU Jian-bo, LIU Jiu-fu, LI Jin-kui, WANG Wei   

  1. (College of Automation Engineering, Nanjing University of Aeronautics and Astronautics, Nanjing 210016, China)
  • Received:2011-01-14 Online:2011-07-20 Published:2011-07-20

摘要: 传统C/C++代码的预处理分析利用符号执行推断预处理中自由变量条件表达式的值,但是该算法的时间复杂度是指数型的。为降低时间复杂度,提出一种快速符号执行算法。源代码通过词法分析器得到预处理变量和路径条件,为预处理变量建立节点,把路径条件转化为条件表达式,通过符号执行算法将两者整合为条件值c-value的形式,最终显示预处理结束后每一个预处理变量的条件值。实例结果表明,该算法能免去传统符号执行中对于路径可行性的分析,从而降低时间复杂度。

关键词: 符号执行, 预处理变量, 条件值, 条件表达式

Abstract: Traditional C/C++ code relying on preprocessing can be quite complex to analyze. Symbolic execution can be used to infer these expressions using the free variables, but its time complexity is exponential. In order to reduce the time complexity, this paper puts forward a method of fast symbolic execution. By using lexical analyzer, preprocessing variables and path conditions from source code are gotten. Next is building node for each preprocessing variable and converting path conditions into conditional expressions, they are merged into conditional values(c-values) through the algorithm of symbolic execution. The result is to display each preprocessing variable’s c-value after pretreatment. Experimental results show that the path feasibility analysis of traditional symbolic evaluation can be omitted. So it can reduce the time complexity by using symbolic execution algorithm.

Key words: symbolic execution, preprocessing variable, conditional value, conditional expression

中图分类号: