2. 中国科学院 计算机网络信息中心, 北京 100190
为进一步提高测试生成效率，提升大规模测试生成的自动化程度，构建了一种基于着色Petri网模型的一致性云测试生成方法，称为PT-Cloud方法，并将该方法实现为可提供一致性测试生成服务的云测试生成平台.该方法利用MapReduce技术，实现了面向测试生成需求的被测系统着色Petri网模型重构和标记，并在此基础上以实际测试数据驱动一致性测试例的自动生成.经实际测试生成和执行实践验证，PT-Cloud方法能保证所生成的测试例是切实可执行的，同时有效提高了测试生成的效率和自动化程度.
2. Computer Network Information Center, Chinese Academy of Sciences, Beijing 100190, China
To improve efficiency and automation degree of large-scale test generation, a colored Petri nets (CPN) model based conformance test generation approach, named as PT-Cloud approach, is proposed and implemented to provide a cloud based conformance test case generation service. Utilizing MapReduce technology, PT-Cloud approach could perform test generation oriented model reconfiguration and labeling process, and then test cases with actual input data could be automatically generated. Validated through practical test generation and execution, the PT-Cloud approach could guarantee that all generated test cases are sufficiently feasible for practical test executions, and the efficiency and automatic degree of test generation are effectively promoted.
基于模型的一致性测试方法[1]通过构建面向测试需求的软件系统功能行为模型来生成更为全面、准确的测试例，有助于提高测试生成效率. 选择软件描述模型是基于模型测试方法的基础，与有限状态机、标记变迁系统、进程代数等常用软件形式建模方法相比，着色Petri网(CPN，colored Petri nets)[2]能更加直观、准确地刻画复杂软件交互和并发行为，且CPN模型的动态模拟是一种以实际数据驱动模型控制流和数据流的协同执行过程，基于这种模拟执行能生成大量实际可执行的测试例，保证测试生成的有效性. 分析已有基于CPN模型的测试生成相关研究[3-6]可知，在测试生成中通常存在大量可并行的测试生成操作，因此若利用MapReduce云计算架构[7]在并行计算能力和高可靠服务等方面的优势，实现云计算与基于CPN模型的测试生成方法的协同融合，可进一步提高测试生成效率，提升大规模测试生成的自动化程度.
笔者利用MapReduce云计算架构，并选择着色Petri网作为基础形式模型，构建基于CPN模型的一致性云测试生成方法，称为PT-Cloud方法，包括2个相关过程：1)由于一般的层次CPN模型无法直接应用于云测试应用，故笔者实现了一种基于MapReduce技术的模型快速重构方法，对源模型描述中元素的数据组织结构进行自动解析和重构，使转换后的模型描述方式能直接用于测试例生成过程；2)以基于CPN模型模拟执行的一致性测试生成方法为理论基础[6]，利用MapReduce技术实现并行的测试例生成，以实际数据驱动多个满足条件的测试用例的自动生成. 最后，笔者将PT-Cloud方法实现为可提供一致性测试生成服务的一套完整可用的云测试生成服务平台，称为PT-Cloud Tool.
1 面向测试的CPN模型重构通过主流CPN建模工具CPN Tools[2]构建的被测系统CPN模型使用可扩展标记语言XML方式进行模型结构和元素描述，主要部分包括〈globbox〉区中描述的颜色集(colorset)和变量(var)等，以及〈page〉区中描述的位置(place)、变迁(transititon)、弧(arc)等. 该方式适用于模型的显示和手工模拟执行，但利用其支持基于模拟执行的测试自动生成时，需要在不同区内完成大量的元素定位和关联查找操作，效率非常低；且该描述中存在和测试需求无关的冗余描述，如元素显示位置、对齐方式等. 故笔者提出一种被测系统的功能CPN模型(通过CPN Tools工具建模)向一致性测试可用的CPN模型的快速转换方法，使处理效率从min级降到了s级.
1.1 基于MapReduce的模型重构多路双向链表作为被测系统CPN模型的模型元素组织和描述方式，如图 1所示. 该模型描述的关键是以变迁元素为切入，记录其关联的所有输入输出弧，继而关联每条弧对应的所有位置. 其优势在于这种元素关联组织方式直接面向基于CPN模型模拟执行的测试生成过程，以实际数据驱动链表遍历作为主要操作，避免了基于XML描述进行测试例生成时所需的大量重复查找和关联判定操作.
|
图 1 基于多路双向链表的模型元素描述 |
因为源CPN模型的XML描述文件中，模型元素以扁平方式完成统一组织描述，并未以变迁元素为中心，且存在大量与测试无关的冗余信息，故模型重组需要首先分离并提取不含有冗余信息的位置、变迁、弧等关键模型元素，在此基础上才能完成以变迁元素为核心，基于多路双向链表描述方式的模型重构. 笔者提出使用2次MapReduce过程首先完成分离模型元素节点和去除冗余信息，基于此构建模型对应的多路双向链表，实现高效用的CPN模型重构. 其主要执行过程可详细表述如下.
1) 首次Map任务：将源模型文件按照不同〈page〉区进行分段后交由各Map任务，即以〈page〉区偏移量为关键值分片源模型文件，将各个分段中描述的位置、变迁、弧等关键模型元素数据进行分离，每个元素包含其描述属性都形成一个独立描述记录. 首次Reduce任务：当各个独立记录按照位置、元素和弧3种类型被重组排序后交由各自Reduce任务，提取属性并剔除无关信息，即位置元素保留其身份标识号(ID，identification)、名称、类型、托肯初始值、所属pageID；变迁元素保留其ID、名称、防卫表达式、所属pageID；弧元素保留其ID、类型、弧表达式、关联位置和变迁的ID、所属pageID等，而源文件中对各元素显示位置、显示形状、对齐方式等属性描述均因与后续测试生成无关而去掉. 经过首次MapReduce处理后，源文件中的各个位置、变迁和弧元素事实上形成了不同的小记录，可认为是多路双向链表结构中的不同节点.
2) 迭代Map任务：将首次MapReduce处理得到的中间文件进行分片后交由各Map任务，即以中间文件的元素描述偏移量为关键值进行分片，以变迁ID为索引进行元素记录的输出，即变迁元素节点和弧元素节点因直接含有变迁ID数据可直接输出该节点记录，而位置元素节点记录中因没有变迁ID数据而以位置ID代替，并标识为不同类型的ID值. 迭代Reduce任务：当各个以变迁ID数据独立标识的节点记录被重组排序后交由不同的Reduce任务，特别地，位置节点记录也一并交由所有Reduce任务备用. 按照如图 1所示的多路双向链表组织方式，将具有相同变迁ID的变迁节点和弧节点进行关联，并按照弧节点中的位置ID信息在位置节点记录集中找到相关节点完成关联. 经过迭代MapReduce处理后，形成了以不同变迁节点为核心，关联了其对应的所有输入输出弧，以及弧关联的所有输入位置或输出位置的多个多路双向子链表. 最后将重复的位置节点合并，即可构成用于后续测试生成的基于多路双向链表的被测系统CPN模型描述，且与源模型同构，即位置、变迁和弧之间的关联拓扑不变. 特别地，颜色集类型和变量等信息会单独提取，嵌入在相应链表节点中的属性域值.
1.2 模型重构的行为一致性上述模型转换方法可保证通过CPN Tools工具构建的被测系统功能CPN模型(记为MF)和重构后得到的测试CPN模型(记为MT)具有行为一致性，即MF和MT在相同点火路径的驱动下应具有相同的输出序列. 可定性证明为：MF和MT中所有网结构元素及其关联关系和MF中所有初始函数、弧表达式、着色函数、防卫表达式等定义在模型转换和重构过程中均未改变；MF和MT的点火规则也相同. 因此，对任意以MF为起点的点火路径，MF和MT具有相同的点火过程和行为执行路径，那么它们在该路径点火执行后的输出也必然相同.
2 基于CPN模型的云测试生成笔者之前研究提出的基于CPN模型的一致性测试生成方法[6]由具体初始数据(CPN模型初始标识)驱动执行，1次只生成1个测试例模型，若初始数据可导致多个并发操作执行，或多个初始数据同时执行来快速生成对应多路径的大量测试例时，测试生成效率很低. 为此，笔者提出一种基于MapReduce技术的多路径测试例自动生成方法.
2.1 面向测试需求的模型标记依照一致性测试需求，将被测系统CPN模型中的位置元素区分为可观察态(被测系统等待测试输入或被测系统呈现可观察的测试输出)或内部态(被测系统内部运行外部无法观察到输出)；将模型中的变迁元素区分为输入行为(测试者向被测系统提供输入)、输出行为(被测系统产生测试者可观察的输出)或内部行为(被测系统内部执行的不可观察行为). 在自动生成测试例前需要基于被测系统的CPN模型完成上述位置和变迁元素的区分标识. 在基于多路双向链表的模型描述中，通过扩展并设置相应节点属性域的值来实现上述区分标识.
2.2 基于MapReduce的测试自动生成由初始数据导致多个并发操作执行，或多个初始数据同时执行等多路径执行情景下的测试例生成问题，可分解成相对独立的多个测试例的生成问题，故非常适合使用MapReduce并行处理技术对上述基本的测试生成方法进行重新设计，目标是将模型模拟执行的过程并行化，同一时刻被激活的多个变迁可同时点火执行且完成测试相关处理(即非交叠语义下的并发执行方式)，以有效提高多路径测试生成效率. 图 2给出测试生成算法的总体设计.
|
图 2 基于MapReduce的测试生成算法总体设计 |
测试生成过程采用多次迭代MapReduce的方式对模型进行模拟执行，即被测系统模型在当前标识下若存在可点火的变迁，那么意味着被测系统存在可执行的被测行为，则驱动一轮基于MapReduce的测试生成过程. 在Map任务执行前，依据可运行Map任务的个数，将被测系统对应的多路双向链表模型进行分段，每段由唯一ID标识且包含若干变迁元素及其关联的位置和弧元素. 链表分段遵循2个原则：分段边界为位置元素，该元素将重复出现在相邻2段中以形成以变迁为中心的完整行为单元；层次CPN模型页内也可分为多段. 分段后的每段链表都由对应的Map任务判定其中是否存在可点火的变迁元素并记录类型(输入/输出/内部)和ID. 使用3个Reduce任务分别对当前所有可点火执行的输入变迁、输出变迁和内部变迁完成相应的测试生成处理. 具体执行过程可表述如下.
Map任务：遍历该链表段，依据位置上的托肯数据、变迁防卫表达式和输入弧表达式来综合判定该链表片段中是否存在可激活的变迁元素. 若没有可激活变迁，则不提交后续Reduce任务. 若存在可激活变迁，则将该变迁及其关联的所有输入输出弧，以及每条弧关联的所有位置和该链表片段ID信息，依据迁类型(输入/输出/内部)一并提交到不同的Reduce任务进行后续处理.
Reduce任务：3个Reduce任务分别对可点火执行的输入变迁、输出变迁和内部变迁完成相应的测试生成处理. 其中，为输入变迁对应的输入位置添加延决变迁元素，描述允许因等待输入而非死锁的静止态；点火执行输入变迁或输出变迁，并为其对应的可观察位置分别增加测试结果判定单元，即新增2个位置元素和1个变迁元素，其中1个位置的托肯数据给出期望观察到的测试输出值，另1个位置为测试结果指示位置，只允许pass或fail托肯数据，如可观察位置体现的测试执行实际输出值与预期测试结果位置上描述的预期输出相同，则产生pass数据，否则产生fail数据，而这种判定就是通过新增变迁执行的. 若为内部变迁，则点火变迁执行并记录点火前后相关联位置上的托肯数据变化.
经Reduce任务处理后的变迁片段描述的是模型的当前一步执行情况，因每次MapReduce迭代中都会记录链表分段信息和变迁ID，故参照原模型双向链表中的关联关系，可将当前处理完成的变迁片段合并到已生成的测试模型中，描述从初始状态到当前执行时所有可行路径形成的测试模型. 当被测系统模型中不再有可点火执行的变迁元素时，测试生成过程终止，得到被测系统在指定初始输入数据驱动下生成的所有可行的完整测试例模型.
测试生成过程中MapReduce的迭代次数等于被测系统模型中所有可执行路径的最大长度，在模型规模较大时可在有限步内生成所有可行的测试用例. 与现有采用状态空间的方法相比，有效避免了因模型规模较大而导致测试无法生成的问题.
3 PT-Cloud Tool云测试生成平台PT-Cloud Tool平台基于Hadoop框架设计与实现，平台主体功能均以服务构件的方式实现在平台服务层，并最终以B/S统一门户为用户提供基于CPN模型的一致性测试生成服务. 主要服务构件包括模型重构业务依赖的模型分析和模型管理构件，测试自动生成业务依赖的手动、自动生成构件和存储构件，以及用户管理、资源监控和日志分析等平台管理构件. 业务构件部分采用MapReduce查询语言实现迭代MapReduce处理. 平台统一门户前端使用Jquery UI和XYTips进行动态渲染，并通过调整Canvas画布的展示顺序来完成模型的正确显示，增强平台易用性. 前端获得和显示的模型元素数据均通过JS(JavaScript)对象存储更新，便于在前端数据动态改变时与后台数据存储保持数据一致.
3.1 平台实际应用示例以PT-Cloud Tool平台作为被测系统的好处在于本系统功能需求非常明确，便于建立准确的被测CPN模型，且其中复杂并发行为适合使用PT-Cloud方法进行功能一致性测试. 通过对系统进行不断地测试实践和代码修正，可在完善PT-Cloud Tool系统的同时，检验PT-Cloud方法的有效性并持续改进. PT-Cloud Tool平台的主要业务流程包括源模型文件(使用CPN Tools工具建模)上传、模型分析重构(得到可用于测试生成的CPN模型)、测试例自动生成等. 实验环境包括4台虚拟机(双核2.5 GHz处理器+4 G内存)组成的虚拟化基础设施，部署Hadoop1.1.2运行支撑环境和Mysql数据库.
首先，图 3给出的模型是经过基于MapReduce的模型重构后显示的，可用于后面测试自动生成的PT-Cloud Tool平台功能层次CPN模型，其中替代变迁Uploader/Parser/Generator分别对应于上述平台3个主要业务的描述. 图 4例示了在描述上传业务的子模型中如何对输入输出行为进行变迁元素的标识，如拟将Upload变迁标识为输入变迁，描述上传CPN模型源文件的输入操作. 位置localServer和位置cloudFile作为uploadFile变迁的输出位置都将被标识为可观察位置，即该位置将在测试例模型中参与描述预期输出值，供判定一致性结果.
|
图 3 描述平台业务的CPN测试模型 |
|
图 4 测试模型的输入输出变迁标记 |
图 5给出了图 4所示上传业务的子模型对应的一个测试模型示例. 其中，作为输入位置uploadFile添加了延决变迁suspen，说明系统在该位置时可能出现因等待用户上传文件而呈现的静止态，而不是出现死锁；对输入变迁uploadFile和changeFile对应的可观察位置集localServer/cloudFile/ getXMLFile分别增加了2个位置元素和1个变迁元素组成的测试结果判定单元，其中1个位置给出希望观察到的预期输出值，如上传文件后提交云端Hadoop分布式文件系统存储的To_c位置上应该观察到源文件备份test.cpn和待处理文件test.xml；而另1个位置为测试结果指示位置，如在CloudFile位置上体现的测试执行实际观察值与To_c位置上描述的预期测试输出相同，则产生pass数据，否则产生fail数据，而这种判定就是通过新增变迁的点火执行的. 利用这种测试结果判定单元可明确标识测试执行是否存在与预期不一致的观察结果.
|
图 5 自动生成的测试模型示例 |
平台主要业务流程共涉及11个功能测试项，对每个功能测试项考虑若干正常输入和若干异常输入后共生成32个测试用例，并完成了平台自测.
3.2 测试生成效率分析以笔者研发的简单点对点(P2P，peer-to-peer)文件共享系统作为被测，完成Liu等[6]给出的基于CPN模型的一致性测试生成基本方法与PT-Cloud云测试生成方法的测试生成效率对比实验. 简单P2P文件共享系统遵照BitTorrent协议[8]实现P2P网络中文件快速分发和共享. 该系统实现逻辑较为复杂，存在较多的可并发操作，适合作为对比实验的被测软件. 为简单P2P文件共享系统构建的层次CPN模型包括16个子页模块. 被测系统实验运行场景设置为1个新下载者、3个已有部分文件片段的下载者和1个有完整文件的种子之间共享单一文件的10个片段，涵盖了被测软件的主要功能.
PT-Cloud Tool平台提供的手动测试生成功能可模拟Liu等[6]给出的测试生成基本方法的执行. 特别说明，若某个测试例描述的软件行为只包含顺序执行操作时，并不会产生多路径并发执行情况，因此，选择选择3个代表性的并发行为功能来生成测试例：1个下载者成功接收1个文件片段后并发执行片段存储和新片段请求操作；1个新下载者分别向2个下载者和种子并发请求3个不同的文件片段；3个下载者并发向同一个下载者请求2个相同的文件片段. 测试生成时间结果如表 1所示.
|
表 1 测试生成时间对比实验结果 |
分析可知，PT-Cloud云测试生成方法在测试生成效率方面优势明显，CPN模型的快速转换处理效率和测试生成效率从min级降到了s级. 模型规模较大时笔者方法仍可在有限步内生成所有可行的测试用例，与基于状态空间生成测试例的方法相比，有效避免了模型状态空间爆炸所导致的测试无法有效生成的问题. 因此，面对初始数据可导致多个并发操作执行，或多个初始数据同时执行而引发的多路径测试生成问题，PT-Cloud方法能有效提高测试生成效率，且PT-Cloud Tool平台实现也极大提高了基于CPN模型生成大量测试例的自动化程度.
4 结束语PT-Cloud方法高效实现了被测系统面向测试需求的CPN模型重构，并有效支撑了以实际测试数据驱动的基于模型模拟执行来实现多路径并行执行的测试例自动生成，保证所生成的测试例的可执行性，且有效提高了基于CPN模型的一致性测试生成的效率和自动化程度. 鉴于目前尚未发现支持基于CPN模型进行测试生成的软件系统平台，本文设计实现的 PT-Cloud Tool具有很好的实用价值.
| [1] | Hernan P L, Stefan H, Delphine L. Model-based testing for concurrent systems with labelled event structures[J]. Software Testing, Verification and Reliability , 2014, 24 (7) :558–590. doi:10.1002/stvr.v24.7 |
| [2] | Jensen K, Kristensen L M. Coloured Petri nets: modelling and validation of concurrent systems[M]. Berlin: Springer-Verlag , 2009 . |
| [3] | Farooq U, Lam C P, Li Huaizhong. Towards automated test sequence generation[C]//ASWEC-2008. Perth: IEEE Press, 2008: 441-450. |
| [4] | Zhang Yan, Tang Tao, Huang Qing, et al. The test of train control system based on colored Petri net[C]//WCICA-2011. Taipei: IEEE Press, 2011: 315-320. |
| [5] | Wu Daohua, Schnieder E, Krause J. Model-based test generation techniques verifying the on-board module of a satellite-based train control system model[C]//ICIRT-2013. Beijing: IEEE Press, 2013: 274-279. |
| [6] | Liu Jing, Ye Xinming, Zhou Jiantao, et al. I/O conformance test generation with colored Petri nets[J]. Applied Mathematics and Information Sciences , 2014, 8 (6) :2695–2704. doi:10.12785/amis/080605 |
| [7] | Di G L, Ferrucci F, Murolo A, et al. A parallel genetic algorithm based on Hadoop MapReduce for the automatic generation of JUnit test suites[C]//ICST-2012. Montreal: IEEE Press, 2012: 785-793. |
| [8] | Cohen B. Incentives build robustness in BitTorrent[C]//2003 Workshop on Economics of Peer-to-Peer Systems. Berkeley: UC Berkeley, 2003: 1-5. |