数据竞争的主动检测技术

Software testing is helpful on improving software quality. With the wide adoption of multi-core CPUs and the development of multithreaded programs, traditional software testing techniques cannot be applied to detect concurrency bugs existing in multithreaded programs. Among all kinds of concurrent bugs, data race is a basic one. Traditional data race detection techniques cannot precisely and effectively detect data races of a multithreaded programs. Recently, dynamic detection of data races becomes much hot. However, academy community have encountered a bottleneck on dynamic detection techniques. Based on current situation at home and abroad, we will present two active testing techniques toward data race detection. The first one aims at overcoming the weaknesses of traditional dynamic techniques that can only detect data races in given executions. We will focus on active techniques to schedule a given multithreaded program, so as to expose those hidden data races that can be then detectable by traditional dynamic techniques. The second one is based on a novel detection technique to actively mine possible data races together with randomized scheduling. It probabilistically guarantees to detect all data races of a given multithreaded program. The two techniques are used at different stages of software testing and together to improve software quality.

软件测试有助于提高软件的质量。随着多核CPU的普及和多线程程序的开发，传统的软件测试方法无法用于检测存在于多线程程序中的并发缺陷。而数据竞争是最基本的一种并发缺陷。传统的数据竞争检测方法无法准确并有效地检测出一个多线程程序中的数据竞争。近年来，数据竞争的动态检测方法备受学术界的关注。但是，目前学术界对数据竞争的动态检测的研究已经遇到了一个瓶颈。基于国内外的研究现状，我们将提出两种数据竞争的主动检测技术。一种是针对传统动态检测技术只能检测给定程序运行中的数据竞争的。我们将通过主动调度给定多线程程序的运行，使得隐藏的数据竞争暴露出来，从而被传统的检测方法检测到。另一种则是基于一种新型的检测技术，结合随机调度的方法，主动去挖掘可能发生的数据竞争并检测，并在概率上保证给定程序中的每个数据竞争都会被检测到。两种检测方法将应用于软件测试的不同阶段，一起用于改进多线程软件的质量。

本课题主要研究了并发程序中的数据竞争的主动检测技术。多线程程序在运行时具有不确定性，其中的并发缺陷难以检测。而数据竞争则是这些并发缺陷中非常基础的一种缺陷。传统的数据竞争检测依赖于默认调度（即操作系统的调度）。本课题主要研究了用于数据竞争检测的主动调度技术。主要包括三方面的内容。.首先，本课题提出了一种新型的数据竞争定义及一种基于硬件的检测方法，可以用于并发程序在大规模测试环境中的数据竞争检测，不仅仅具有检测开销低的特点，而且有效性得以保证。.其次，本课题提出了一种有概率保证的数据竞争主动调度检测技术，主要依赖于基于并发缺陷（数据竞争）半径的概率检测方法RPro，并在死锁的检测中得到了验证，且有概率保证。之后进一步扩展到数据竞争的主动调度检测。.最后，本课题提出了针对大量测试输入下的跨运行、跨线程的数据竞争主动采样检测技术，主要根据数据竞争的特点（即每个数据竞争需要两次不同线程的内存访问），提出分析据跨线程和跨运行的采样技术，达到了逐渐降低采样开销的同时，和传统的数据竞争检测方法相比，保持了数据竞争检测有效性。.本项目发表文章12篇，其中CCF A类11篇。获得专利授权3项。项目负责人及项目团队研究生均获得了国家至院校的不同荣誉。.本项目超额完成了预期目标。