在软件生命周期过程中,软件测试是保证软件质量的关键环节之一。随着多核处理器和并行分布式系统的不断发展,并发程序设计方法受到了广泛的关注与讨论,纵观现代软件行业,从操作系统到互联网,并发程序无处不在。虽然并发程序在当前有着广泛的应用,但其执行行为的不确定性却给测试带来了新的挑战。一方面需要调整、改进传统的测试策略和方法;另一方面探索出适应并发程序特征的测试理论与技术也尤为必要。高效的测试用例来自于对程序的准确分析,并发程序分析方法大致可分为静态分析和动态分析两大类,静态分析直接分析源程序,而动态分析则分析程序的运行时信息。执行行为的不确定性是并发程序的独有特征,并发程序测试方法在执行测试用例时或者控制其行为,或者不控制其行为,前者被称为不确定性测试,而后者被称为确定性测试。不确定性测试使用的测试用例与传统顺序程序测试方法所使用的测试用例类似,只包括必要的程序输入和输出,而确定性测试使用的测试用例还包括能够控制程序执行行为的测试序列。可达性测试综合运用了动态分析技术与确定性执行技术,在给定测试输入的前提下,该测试方法能自动生成并发程序的所有偏序测试序列,从而测试该程序的所有可能执行行为,具有很高的实用性。可达性测试在确定性执行测试序列时需要进行一定的运行时控制,究其根本原因是该方法对竞争表的计算不够准确。通过对控制结构和竞争差异等概念进行重新定义,改进和完善了现有的可达性测试方法,新方法在对测试序列进行确定性执行时无需额外的运行时控制,提高了测试的执行效率。与大多数并发程序结构性测试方法一样,可达性测试面临着测试序列集过大而无法穷尽的难题。针对并发程序测试序列集过大的根本原因,提出了一种全发送接收语句对测试准则,利用可达性测试生成测试序列集的完备性来保证覆盖所有的发送接收语句对,完善与改进现有可达性测试方法以生成较小的能满足该准则的测试序列集,从而达到约简测试序列集的目的。Concolic测试是另一种实用性较高的并发程序测试方法,其遍历并发程序测试序列的方法与可达性测试类似,但它结合符号执行等技术部分解决了可达性测试并未涉及的测试输入选择问题。Concolic测试在对并发程序进行动态分析时使用了传统的先发生于(happened-before)关系,实验表明使用这种关系会产生较大规模的测试序列集。针对Concolic测试中先发生于关系对测试序列集规模的影响,研究支持保结性的弱先发生于关系,提出了一种既能保证一定测试充分性,又能减小测试序列集规模的等价类测试方法,并设计了相应的测试序列选择策略,从而进一步提高了Concolic测试的实用性。