Journal of Software:2014.25(3):472-488

(中国科学院 计算技术研究所 计算机体系结构国家重点实验室, 北京 100190;首都师范大学 信息工程学院, 北京 100089;中国科学院大学, 北京 100049;中国科学院 信息工程研究所 第五研究室, 北京 100093)
Efficient Scene-Sensitive Fault Detection Approach
ZHONG Lu-Jie,HUO Wei,LI Long,LI Feng,FENG Xiao-Bing,ZHANG Zhao-Qing
(State Key Laboratory of Computer Architecture, Institute of Computing Technology, The Chinese Academy of Sciences, Beijing 100190, China;Information Engineering College, Capital Normal University, Beijing 100089, China;University of Chinese Academy of Sciences, Beijing 100049, China;No.5 Research Laboratory, Institute of Information Engineering, Chinese Academy of Sciences, Beijing 100049, China)
Chart / table
Similar Articles
Article :Browse 2058   Download 2193
Received:October 08, 2012    Revised:April 07, 2013
> 中文摘要: 定值-引用类错误是一类非常重要且常见的错误.当前,对这类错误的检测很难同时达到高精度和高可扩展性.通过合理组合敏感和不敏感的检测方法并控制两类方法的实施范围,可以同时达到高检测精度和高可扩展性.提出一种新颖的场景敏感的检测方法,该方法根据触发状态对潜在错误语句分类,识别不同类别语句的触发场景并实施不同开销的检测,在不降低精度的同时最小化检测开销.设计了一个多项式时间复杂度的流敏感、域敏感和上下文敏感的场景分析以进行分类,并基于程序依赖信息识别触发场景,仅对必要的触发场景实施路径敏感的检测.为上述方法实现了一种原型系统——Minerva.通过使用空指针引用错误检测为实例研究以及总代码规模超过290万行,最大单个应用超过200万行的应用验证,用例实验结果表明,Minerva的平均检测时间比当前先进水平的路径敏感检测工具Clang-sa和Saturn分别快3倍和46倍.而Minerva的误报率仅为24%,是Clang-sa和Saturn误报率的1/3左右,并且Minerva未发现漏报已知错误.上述数据表明,所提出的场景敏感的错误检测方法可同时获得高可扩展性和高检测精度.
Abstract:Def-Use faults are a very important and common type of faults. The state-of-the-art detection schemes for such faults still hardly achieve both preciseness and scalability. This paper applies the idea of combining the sensitive and insensitive detection approaches and deploying the effective range of the two approaches to achieve both high detection scalability and high precision. The study results in a new scene- sensitive detection strategy based on a classification scheme on statements that contain potential faults. The key idea is to classify these statements into different categories based on how a potential fault in these statements might be triggered. It uses polynomial flow-, field- and context-sensitive summary based scene analysis to do the classification and identifies triggering scenes based on program dependence information. Different detection schemes with different amount of overheads are then applied to different categories and thus reducing the overall overhead and achieving a higher scalability. The path-sensitive detection schemes are only performed on the necessary triggering scenes. The proposed approach is implemented in a prototype system, called Minerva. Using null pointer dereference fault detection as an example and verifying the approach through applications whose total code size exceed 2.9 million lines (one application exceeds 2 million lines), the experimental results show that the average detection time of Minerva is 3× and 46× faster than the two state-of-the-art path-sensitive detection tools, Clang-sa and Saturn, respectively. The false positive rate of Minerva is 24%, which is also a third of that of Clang-sa and Saturn's. There is no false negative on the known faults. The results show that the proposed scene-sensitive fault detection approach can achieve both high scalability and high accuracy.
文章编号:     中图分类号:    文献标志码:
基金项目:国家自然科学基金(61100011,61202055,61303053);国家高技术研究发展计划(863)(2012AA010901);国家自然科学基金创新研究群体科学基金(60921002) 国家自然科学基金(61100011,61202055,61303053);国家高技术研究发展计划(863)(2012AA010901);国家自然科学基金创新研究群体科学基金(60921002)
Foundation items:
Reference text:


ZHONG Lu-Jie,HUO Wei,LI Long,LI Feng,FENG Xiao-Bing,ZHANG Zhao-Qing.Efficient Scene-Sensitive Fault Detection Approach.Journal of Software,2014,25(3):472-488