并发缺陷的快速检测、定位及高质量补丁自动生成研究

Rapid detection, accurate localization and high quality patch generation for concurrent faults are important research questions in concurrent program analysis, and researchers have achieved fruitful results in the past three decades. However, there are still some issues of low detecting efficiency, high false positives, high false negatives, inaccurate localizing and low quality of the generated patch. This project proposes a method of concurrent defect detection based on the combination of maximum causal reduction and adaptive random scheduling, an approach of concurrent fault localization based on constraint solving and Delta Debugging, as well as a technique of defect repairing for the analysis of related variables and the minimum lock set. This project will explore more efficient and reliable methods for concurrency fault detection, localization and fixing. It will also have great significance for revealing the law of concurrent defects trigger, localizing and fixing, and will lay the foundation for the high-quality concurrent programs.

面向并发缺陷的快速检测、精准定位和高质量补丁生成是并发程序分析的重要问题，近三十年来取得了丰硕的成果。但当前的研究仍然存在检测效率低、漏报误报高、定位不精准、修复质量不高等问题，本项目提出了基于最大因果约简和自适应随机调度相结合的并发缺陷检测方法、基于约束求解和差异调试的缺陷定位方法以及针对关联变量分析和最小锁集的并发缺陷修复方法，探索从并发缺陷的检测、定位到修复的一整套更为高效、更为可靠的并发缺陷调试方法。对揭示并发缺陷的产生规律、检测技术及修复方法都有重要的意义，为并发程序的高质量运行奠定了基础。

随着硬件性能不断提升，为了极大程度地利用硬件性能，并发程序应运而生。然而，并发程序开发难度高、维护成本大等特点，为软件开发人员带来了很大的挑战。因此，如何及时地对并发缺陷进行检测、定位及自动化修复成为了业界亟待解决的难题。本项目针对以上难题，从并发缺陷检测、定位及修复三个方面展开研究。（1）在并发缺陷检测方面，本项目提出基于内存访问模式的并发程序执行轨迹间距离衡量方式，并基于此提出并发程序自适应随机调度算法；同时对最大因果约减算法进行改进，通过在构建并发程序约束时引入有向图的指导，过滤不合法以及不可解约束从而进一步提升并发缺陷的检测效率；（2）在并发缺陷定位方面，本项目设计并提出了针对并发程序的覆盖衡量标准MAP-Coverage，该覆盖度量与并发测试执行的揭错能力有较强的相关性。在此基础上，本项目借助MAP-Coverage的引导，求解出更易触发并发缺陷的线程调度，进一步提升并发程序缺陷的定位速度；（3）在并发缺陷修复方面，本项目围绕并发程序特有的加锁策略展开，提出使用静态程序分析以及约束求解的方式来自动化推测并生成加锁策略的方法，进而完成并发缺陷的自动化修复过程。..本项目目前共撰写论文12篇（10篇已发表，2篇已录用），其中国际顶级会议CCF-A类会议及期刊论文6篇，CCF-A类中文期刊论文2篇，CCF-B类会议及期刊论文2篇，CCF-C类会议论文2篇。获得CCF-A类会议FSE杰出论文奖一项。..在本项目研发期间，团队整理出一个并发缺陷数据集。数据集中共包含53个包含并发缺陷的程序，项目团队对其中的程序进行了分析，数据集中包含了能够复现缺陷的测试程序，以及缺陷相关分析。数据集共包含代码95954行，涉及到apache、jfreechart等大型商业或开源软件，对并发程序分析具有一定指导意义。..本项目在并发缺陷检测、定位及修复三个方面展开研究，一定程度上解决了（1）并发缺陷检测过程中线程调度空间爆炸的难题；（2）并发缺陷精确定位难的问题以及（3）并发缺陷修复补丁效率低和普适性差的难题。