提高路径敏感缺陷检测方法的效率及精度研究  

Improving the Efficiency and Accuracy of Path-Sensitive Defect Detecting

作　　者：赵云山[1] 宫云战[1] 刘莉[1] 肖庆[1] 杨朝红[1,2] 

机构地区：[1]北京邮电大学网络与交换技术国家重点实验室,北京100876 [2]装甲兵工程学院信息工程系,北京100072

出　　处：《计算机学报》2011年第6期1100-1113,共14页Chinese Journal of Computers

基　　金：国家"八六三"高技术研究发展计划项目基金(2009AA012404);国家自然科学基金项目"航天嵌入式软件缺陷检测方法研究;系统研发及应用"(91018002;2010)资助

摘　　要：路径敏感的缺陷检测方法其缺陷状态会关联当前控制流节点的所有数据流信息,由于其中包含与缺陷检测无关的数据流,因此会导致分析效率下降.为了避免全路径敏感分析时的路径爆炸问题,一般会在控制流汇合节点进行缺陷状态合并,而这种粗糙的合并策略带来的精度损失会引起误报.针对上述问题,文中提出一种基于缺陷的程序切片方法,该方法基于缺陷特征和路径条件建立切片准则,根据控制流节点上的数据流信息与切片准则的包含关系进行程序切片,得到的切片程序在缺陷检测时切片掉了缺陷无关节点且与源程序完全等价,以提高缺陷检测效率.为了进一步减少路径敏感分析方法的误报,提出一种基于切片的缺陷状态合并策略,根据控制流分支节点的路径条件,对缺陷状态添加状态属性,从而有选择地对控制流汇合节点进行状态合并,减少精度损失.文中所述方法已在缺陷检测系统(DTSGCC)中实现.对大量Linux中GCC开源工程的测试结果表明,文中提出的方法可以提高路径敏感缺陷检测方法的效率,并减少误报.While detecting defects with path-sensitivity, the defect state contains all data flow in- formation of the current control flow vex, which might lower the efficiency by the defect irrespective data flow information. Further, in order to avoid the path explosion while full-path-sensitive analysis, the defect states encountering the control flow confluent nodes might be simply merged. The preliminary state-merging strategy might lead to an accuracy loss which could induce false positives. To address the above issues, this paper proposes a new program slicing algorithm based on defect patterns. The slice criteria include defect feature and path condition, and the source program is sliced by the inclusion relation between the CFG dataflow information and the slice criteria. The sliced program not only slices the defect irrespective codes, but also is totally equivalent to the original program, which improves the efficiency. In order to further reduce the false positives of path-sensitive analysis, this paper presents a refined state-merging strategy to diminish the accuracy loss, which selectively merges the defect states by adding path condition as state attribute. The authors have implemented the technique in DTSGCC （Defect Testing System for GCC）, a software defect detecting tool for GCC projects in Linux. DTSGCC is applied to validate plenty of GCC open source projects. Experimental results suggest that applying the tech-nique to path-sensitive defect detecting analysis improves the efficiency, at the same time reduce potential false positives.

关 键 词：静态分析 缺陷检测 路径敏感 误报 程序切片 上下文敏感分析 域敏感分析 

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