准确性无损的软件缺陷检测高可扩展性优化研究

Achieving high accuracy, high scalability and the practicability are the ultimate goals for software static fault detection. Under the situation of having no effective way to reduce the exponential complexity of analysis algorithms, users cannot suffer the huge overhead of high accurate analysis, especially for large-scale programs. While with the rapid development of novel hardware and computation environment, it provides the opportunities to implement an effective and efficient fault detection approach. In this research, we propose an optimized multi-level solution to achieve high scalability and high detection accuracy, which takes advantage of the coordination of reducing the analysis scale and utilizing the computing abilities of the novel hardware and computation environment. The main research contents include: 1) presenting the fault detection approach with general fault description, self-adaptive detection generation mechanism and strategies of minimizing the input scale of path-sensitive analysis, which are performed on the scope of applications analysis and fault detection algorithms; 2) presenting the parallel accelerating strategies on program analysis and detection methods. By way of multi-level coordination of hardware and software acceleration, we will have a practical, accurate and scalable fault detection approach, which is expected to be widely used in large-scale programs fault detection.

实用、准确且具有高可扩展性是软件静态缺陷检测方法追求的终极目标。在尚无有效方法降低高准确性分析算法指数级复杂度的背景之下，当程序规模变大时，高准确性分析的高开销是用户所不能承受的。当前，迅速发展的新型硬件与计算环境为静态缺陷检测方法提供新机遇的同时，大规模应用程序对于高效、准确的缺陷检测方法的需求也更为迫切。针对这些现状，本项目紧密围绕减小缺陷检测计算规模和提高缺陷检测计算能力两个核心，在保障检测准确性的基础上，设计极小化路径敏感分析规模和基于新型硬件与计算环境的多层次协同的高可扩展性优化方案。主要研究内容包括：（1）提出应用层和缺陷检测层路径敏感分析范围减小策略，以及通用定值-引用缺陷描述和自适应检测生成机制；（2）提出程序分析及缺陷检测层的并行加速策略及算法。从而实现可应用于大规模程序检测，以高检测可扩展性为驱动、实用准确的、多层次软硬件加速融合的软件缺陷检测方法。

对于静态软件缺陷检测方法而言，在获得高准确性的同时具备高可扩展性一直以来都是该领域研究的重要目标。目前由于高准确性的分析与检测算法的指数级复杂度及传统硬件环境的计算能力受限等问题，令可服务于大规模应用的准确、高效的软件缺陷检测方法的需求更为迫切。针对上述问题与需求，本项目就如何在保障检测准确性的同时获得高可扩展性的方法开展了研究工作，主要包括：(A) 以极小化路径敏感输入为目标的多层次规模减小策略融合的实用缺陷检测方法的研究，和(B)以提高计算能力为目标的程序分析及缺陷检测的并行加速方法的研究。围绕项目研究内容，项目组所取得的一些代表性研究成果如下：(1) 提出了基于缺陷触发相关模式提取的准确性无损保障机制及基于缺陷属性格的适用于更多缺陷类型的缺陷描述方案；(2) 提出了应用层、程序分析层和检测层三层融合的极小化路径敏感分析输入控制优化策略；(3) 提出了一组包含基于库函数建模的指针分析及面向特定领域应用的准确性及可扩展性优化的策略；(4) 提出了基于GPU的程序分析分类信息及危险路径并行提取方法；(5) 提出了符号执行路径探索的并行加速方法及策略；(6) 开展了服务于通用性、实用性及高可扩展性目标的试验研究，对项目组所提出的关键理论和技术进行了验证。经过三年的研究工作，项目组圆满地完成了预期研究任务。在准确性无损的软件缺陷检测高可扩展性优化方面取得了一系列的研究成果，形成了自主知识产权，为程序分析及缺陷检测等相关领域的研究奠定了坚实的基础。项目组共发表/录用学术论文11篇，其中SCI期刊论文6篇，软件学报2篇。申请和获授权的国家发明专利8项。项目组成员多次参加国内外学术交流。在人才培养方面，项目组2位老师晋升副高职称，培养硕士研究生7名，博士研究生1名。