并发软件在软件行业中扮演了一个重要角色,可靠的软件质量需要全面的测试工作来保证。并发软件执行过程非常复杂,系统的状态数目巨大,然而目前的软件测试方法大多数都存在覆盖率低、冗余率高或测试效率低等现象。因此在保证无冗余的情况下,生成对测试目标完全覆盖的测试序列是非常困难的。本文采用待测行为集合描述测试目的,并将测试覆盖标准定义为对待测行为及其数据相关行为执行路径的全覆盖。为提升测试序列获取效果和效率,本文基于形式化语言着色Petri网(Colored Petri Net,CPN),提出一种适用于并发软件的测试序列生成方法。该方法在状态空间中通过状态节点投影、状态结点剪枝、弧剪枝等方法,去除与测试目的无关的执行路径,以缩减状态空间规模。针对基于状态空间剪枝的并发软件测试序列生成方法,做了以下四个方面的工作:(1)采用待测行为集合描述测试目的,并将测试覆盖标准定义为对待测、及其数据相关行为执行路径覆盖。对CPN模型进行扩展,将软件系统模型中的变迁划分为四类:(1)待测行为,(2)相关行为,(3)与待测、相关行为存在并发关系的并发无关行为,(4)与待测、相关行为不存在并发关系的非并发无关行为。为下文针对两种无关行为提出剪枝奠定基础。(2)提出状态节点投影等方法,基于扩展CPN模型的状态空间,对非并发无关行为的执行路径进行状态空间剪枝。得到由待测、相关行为及并发无关行为执行序列构成的状态空间子图,达到第一步缩减状态空间的目的。(3)提出状态节点剪枝、变迁弧剪枝等方法,对并发无关行为进行剪枝。根据并发无关行为在模型中的位置关系,可细分为纯、前、中、后无关行为四种类型。通过状态节点剪枝操作可以去除纯、前、后无关行为全部的执行路径;通过变迁弧剪枝操作可以去除中无关行为多余的执行路径。两种剪枝操作进一步缩减了状态空间的规模,将测试序列生成的范围缩到最小。(4)提出全序列连接等方法,基于剪枝后的状态空间生成测试序列。测试序列完全覆盖待测、相关行为全部执行路径,对于并发无关行为和非并发无关行为则仅选取一条最短执行路径进行覆盖。由此得到从系统初始状态到结束状态的完整测试序列的集合。且测试序列是对待测、相关行为的执行路径达到全覆盖且无冗余性的测试效果。最后完成测试序列生成算法的全覆盖性和无冗余性的证明。采用本方法对警务管理系统实例完成测试序列的生成,验证了本算法的完全覆盖性、无冗余性;并将测试结果与其他方法进行了对比与分析,验证了本算法的高效性。