PDF《一种场景敏感的高效错误检测方法》

国家高技术研究发展计划(863)(2012AA010901);

国家自然科 学基金创新研究群体科学基金(60921002) 收稿时间: 2012-10-08;

修改时间: 2013-03-20;

定稿时间: 2013-04-07 衷璐洁 等:一种场景敏感的高效错误检测方法

473 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. Key words: def-use fault;

fault detection;

sink triggering scene;

scene-sensitive;

program analysis 定值-引用类错误通常很容易发生但较难精确地检测.代表性的定值-引用类错误包括空指针引用、未赋值 引用、除零错、缓冲区溢出等.这类错误难以精确检测,是因为这些错误中由错误源到达错误目标的路径往往 很长且涉及的路径数众多.不仅规模大的应用程序包含大量的执行路径,即便是小规模的程序,仍有可能具有大 量的路径数.例如 SPEC CPU2000 中的 164.gzip,其程序代码规模仅为

8 000 行,但涉及的路径数却超过了 3.49E+11[1] . 一直以来,高可扩展性和高检测精度都是静态错误检测所追求的目标.为了获得高检测精度,有很多方法采 用了路径敏感的检测策略,但这些方法在可扩展性上的不足严重影响了它们的实用性.为了提高可扩展性,一些 路径敏感的检测方法引入了需求驱动的策略,但仍然存在这样一些问题:1) 检测的可扩展性提高了,但检测精 度却有所降低.例如在 Clang-sa[2] 中,为了减少开销,它限制了所能处理的路径条件表达式的类型,因此导致了检 测精度上的损失;

2) 路径敏感的开销仍然很大.如文献[3?7]实施路径敏感检测的范围是整个程序中所有的潜 在错误语句,但对于定值-引用类错误而言,潜在错误语句涉及的引用点数量众多,错误触发的场景也更为复杂, 对于这样的情形,通常以切片为主要技术的需求驱动策略往往不够有效. 我们对 OpenSSH[8] 和Wireshark[9] 等实用程序进行分析后发现:1) 有些错误在每条潜在执行路径上都会被 触发;

2) 有些错误在任何潜在执行路径上都不会被触发;

3) 有些错误可能在一些但不是全部的执行路径上才 会被触发.基于上述发现,我们认为为了保证检测精度,有必要采用路径敏感的检测方法,但是没有必要对所有 的潜在错误语句都采用路径敏感的检测方法. 如图