随着多核处理器的普及,多线程程序已经越来越普遍。对于程序员来说,编写正确的多线程程序显得越发重要。在多线程程序运行过程中,线程的调度顺序往往是不确定的,程序员很难完全考虑清楚所有可能的线程调度顺序。并行bug的触发通常和某一种特定的线程调度顺序有关,而这种线程调度顺序又可能隐藏在庞大的线程调度空间中,因此,并行bug在软件的测试阶段很难被检测到。而且,并行bug广泛存在于多线程程序中,严重影响了软件的可靠性。已有的一些技术通过动态测试所有线程调度顺序的方法来检测并行bug,这类技术在面对一些规模稍大的多线程程序时就会效率低下,因为随着程序规模的增大,线程调度顺序的规模也相应地呈指数级增长,因此,这类技术往往应用在规模小的核心程序上。还有一些技术通过记录多线程程序的运行时信息,然后根据所定义的一些并行bug模式来推断出可疑并行bug,最后再动态验证每一个可疑并行bug,检测到真正的并行bug。这类技术在检测并行bug过程中需要对多线程程序进行插装来完成信息记录和动态验证,从而会带来运行时开销,因此,检测效率也是并行bug检测面临的一大问题。本文面向多线程程序,研究了多种并行bug检测技术,提出了多种策略来提高并行bug检测的效率。1)基于程序切片的并行bug检测技术。为了有效地检测多线程程序中的并行bug,我们采用静动结合的方法,同时还使用了程序切片技术来提高动态分析的效率。通过静态分析程序,能够得到程序中几乎所有的可疑并行bug,但同时也可能包含了大量的误报,因此需要对静态分析的结果进行动态验证。在动态验证之前,我们使用程序切片技术,将程序中与可疑并行bug无关的代码剔除掉。在动态验证的时候,只需要对规模更小的程序进行动态分析就可以检测到并行bug。其中,静态分析的方法能够有效地指导动态验证,使得动态验证时可以只分析静态分析的结果;程序切片使得动态验证能够更高效地检测到真正的并行bug;动态验证的作用则有效地优化了静态分析的结果。我们实现了一个原型工具ColFinder来验证我们的方法,ColFinder能够有效地检测到多线程程序中的并行bug,程序切片技术使得并行bug被动态验证的时间平均减少了33%。2)基于分布并行的有害数据竞争检测技术。数据竞争是多线程程序中最常见的一种并行bug,我们专门针对这种并行bug提出了一种基于分布并行的检测技术。我们使用静态数据竞争检测技术对程序进行分析,找到几乎所有的可疑数据竞争。为了检测到程序中真正有害的数据竞争,我们需要对静态分析得到的所有可疑数据竞争进行动态验证。但是需要被验证的可疑数据竞争数量可能非常多,为了提高效率,我们将所有可疑数据竞争分发到多台机器上,然后多台机器并行地对所有可疑数据竞争进行动态验证。在每台机器上,我们通过插装指令的方式控制线程调度顺序,动态创建数据竞争条件,检查其是否会造成程序失效。我们实现了一个原型工具PRFinder来验证我们的方法,PRFinder有效地检测到了程序中的数据竞争,而且检测的时间随着机器数的增多呈线性减少。3)基于分组归类的有害数据竞争检测技术。已有的技术在动态验证数据竞争的时候,在程序的每一次动态运行过程中,只验证一个数据竞争是否是有害的。然而,当需要验证的数据竞争的数量很多的时候,就需要运行程序很多次才能验证完所有的数据竞争。根据两个数据竞争的四个访存操作是否相互冲突,我们提出了一种分组技术将互不干扰的数据竞争归类到同一组中,使得同一组中的数据竞争能够在程序的一次动态运行过程中被验证。由于在一次程序动态运行过程中我们需要同时验证多个数据竞争,我们设计了新的动态验证策略来检测程序中的有害数据竞争。我们的方法不仅能够成功地检测到有害数据竞争,而且需要动态运行程序的次数比已有的方法少很多。我们实现了一个原型工具RaceChecker来验证我们的方法,RaceChecker能够有效地检测出多线程程序中的有害数据竞争,和已有的工作RaceFuzzer和RaceMob相比,RaceChecker检测时间分别平均减少81%和45%。4)基于线程交织冗余分析的并行bug检测技术。基于线程交织模式的通用并行bug检测技术能够同时检测到多线程程序中多种类型的并行bug,但是由于其所定义的线程交织模式之间存在着相互重叠,导致有些线程交织会被重复分析。为了提高检测效率,我们设计了一些策略来判断一个线程交织是否是冗余的,然后针对所有的线程交织提出了一种冗余线程交织剔除算法,根据这个算法我们可以设计一种不存在线程交织冗余分析的通用并行bug检测技术。为了验证我们的方法,我们将剔除冗余线程交织的思想应用到已有的两种技术PECAN和Maple中,实验结果表明我们的技术不会影响并行bug的检测结果。而且改进后的PECAN检测时间减少了40.0%,改进后的Maple检测时间减少了44.4%。