在软件产业高速发展的今天,并行软件系统已经成为一类主流的软件系统,在社会生产和生活中发挥着重要的作用。例如,网络软件系统,包括基于云计算的软件系统和基于物联网的软件系统,大都具有并行性特点。对并行软件进行测试的难度非常大,因为并行软件的状态空间规模都很大,软件中的并行行为导致其状态空间规模呈指数级增长。工业界大量使用的手工测试方法无法完成对并行软件的测试；学术界很多基于形式化模型的自动测试方法,也受困于并行行为所导致的状态爆炸问题,很难有效完成测试。有的形式化方法并不适合于对状态数目大的并行软件进行建模,例如有限状态机(Finite State Machine, FSM),所以基于此类模型的经典测试方法都不能适用于并行软件；有的形式化方法可以完成对并行软件的建模,例如着色Petri网(Colored Petri Nets, CP-nets)和符号变迁系统(Labelled Transition System, LTS),但是,现有的基于这些模型的测试方法大都不针对并行行为作特殊处理,所以生成的测试序列数量大、覆盖率低、冗余度高,无法有效地针对并行软件进行测试。本文认为,解决并行软件的测试问题,一方面要选择适合于并行行为建模和测试的形式化建模语言；另一方面要基于这种语言提出针对并行行为具有高覆盖率、低冗余率、高执行效率的测试方法。本文选择形式化建模语言CP-nets为待测并行软件系统建模,并针对并行软件测试问题提出了完整的解决方法。首先,针对系统模型状态空间规模过大的问题,提出了基于迹等价的模型化简算法,能够在不改变测试结果的前提下缩小系统状态空间规模,提升测试效率；其次,针对系统中复杂的并性行为,提出了针对待测行为线性序列的测试例生成算法,能够高效地生成对待测行为完全覆盖的测试例；最后,提出了测试序列优化算法,能够去除测试例中的冗余序列,进一步提升测试的效率。上述算法共同构成了一种完整的针对并行软件的测试方法,能够有效地完成针对并行软件中待测行为的测试,具有完全覆盖性、无冗余性和高效性的特点。本文主要的贡献和创新性成果如下：1、提出一种基于迹等价的CP-nets模型化简算法。首先,定义面向测试的CP-nets (Testing-oriented CP-nets, ToCPN)模型,在待测软件系统的ToCPN模型中,进行被测实现部分和测试模拟环境部分的划分,并将连接两部分的端口位置和端口变迁标记为可观察位置和可观察变迁；其次,提出发生序列的迹的定义,即一条发生序列中的可观察元素构成的序列称为迹；最后,提出基于迹等价的并行软件模型化简算法,对符合条件的位置、变迁和其他模型元素进行化简,将被化简的功能合并到邻近的模型元素中。经证明,本文提出的化简算法得到的模型与原始模型符合迹等价条件,也就是外部行为等价条件；而化简后模型的状态空间规模将大幅减小,状态数量和发生序列数量都显著下降。故化简可以在保证测试结果不变的前提下大幅提升测试效率,本算法为解决并行软件测试问题提供了模型基础。2、提出一种基于CP-nets模型的针对待测行为线性序列的测试例生成算法。首先,定义了待测的行为线性序列(Linear Behavior Sequence, LBS)的概念,用于描述待测行为和测试目的；其次,提出基于LBS的测试例生成算法,即通过状态投影、极大极小状态匹配、子序列及完全序列搜索等操作,自动生成覆盖LBS的测试例；最后,证明了本算法生成的测试例能够完全覆盖系统模型中包含LBS的全部发生序列。在本算法中,并不需要遍历系统模型的全部状态空间,而是通过状态投影等操作,在系统模型状态空间中,定位LBS待测行为的前后状态,再针对前后状态之间的状态子图进行测试序列搜索和生成；而子图之外的部分与LBS行为无关,故本算法不对子图之外的部分进行测试序列的搜索和生成,这一点保证了算法具备低冗余率和高执行效率。故本算法生成的测试例具有完全覆盖性、低冗余性和高效性的特点。3、提出了基于CP-nets的针对冗余序列的测试序列优化算法。当LBS行为出现在的三路及三路以上并行结构时,以及当系统中含有大量内部行为时,基于LBS的测试例生成算法将生成含有冗余序列和内部行为信息的测试例。而且,并行路径数目越多,内部行为数量越大,冗余率就越高。针对上述问题,本文提出了两种针对冗余序列的测试序列优化算法。其中,针对多路并行行为的测试序列优化算法针对投影操作得到的状态空间子图,进行基于LBS点火行为制导的搜索操作,这种算法可以去除多路并行导致的冗余序列；针对内部行为的测试序列优化算法针对生成的测试序列进行可观察行为提取操作,并删除提取后得到的相同序列,这种算法可以去除内部行为导致的冗余序列和序列中的内部行为信息。经过上述优化后的测试例,不仅保持了对待测行为的完全覆盖性,而且具备了无冗余性,提升了测试的效率；同时,测试序列中将不再含有内部行为信息,仅含有针对待测实现部分的输入输出信息,更加有利于测试的执行。