路径条件生成中的优化策略  

Optimization strategy in generation of path condition

作　　者：于亚南[1,2] 周喜[1] 

机构地区：[1]中国科学院研究生院,北京100049 [2]中国科学院新疆理化技术研究所,新疆乌鲁木齐830011

出　　处：《计算机工程与设计》2012年第10期3995-3998,4003,共5页Computer Engineering and Design

基　　金：工业和信息化部电子信息产业发展基金项目([2009]453);新疆维吾尔自治区自然科学基金项目(2010211B26);自治区电子发展基金项目--新疆软件服务外包共性技术支撑平台([2011]327)

摘　　要：为了提高利用符号执行生成测试数据的效率,提出了一种结合传统前向遍历和后向遍历的方法。通过对传统前向遍历和后向遍历方式的优缺点进行对比分析,设计了一个结合二者优点的算法。该算法将程序分块处理,整体采用前向遍历的思想,但在每一个块中是后向遍历代码的;它兼具前向遍历较早发现不可达路径的优点和后向遍历可以避免不相关变量赋值的优点,解决了传统前向遍历中的冗余问题。实验结果表明了该方法的可行性和有效性。To improve the efficiency of generating test data by using symbolic execution, a method combining forward traversal and backward traversal is proposed. After studying and comparing these advantages and disadvantages of forward traversal and backward traversal, an algorithm integrating the advantages of both of traversal methods is designed. It partitions a program into blocks, acting as a forward traversal on the whole while as backward traversal in every block. This method combines the advan- tages of checking infeasible paths as soon as possible in forward traversal and avoiding unnecessary assignments in backward traversal. The redundancy problems in forward traversal are solved. Finally the experimental result demonstrates this algorithm＇s feasibility and effectiveness.

关 键 词：符号执行 路径条件 前向遍历 后向遍历 依赖变量 

分 类 号：TP311.56[自动化与计算机技术—计算机软件与理论]