基于模型的自动化测试工具的实现

1、基于模型的自动化测试工具的实现摘要基于模型的测试是本文首先介绍了Atmel-View框架以及菜单系统UI在其中所将扮演的角色、与各个功能模块间的关系。其次讲解了Atmel-View内存映射窗口结合OSD应用的UI设计思想，涉及了多图层表现的想法，硬件OSD与伪OSD的比较使用。然后详细阐述了基于Atmel-View的菜单系统方案和框架结构，针对最重要的MenuMode菜单构建函数分析其数据抽象、界面绘制和事件响应处理过程。其后介绍Nucleus Plus，给出进程通信、进程同步在菜单系统中支持蓝牙模块的应用方法。本方案的实现提供了一套层次化、结构化、可扩展的电子相框菜单系统，并有效支持了蓝牙模

2、块的应用。关键词：OSD，内存映射窗口，菜单系统，UIFULFILL UI OF DIGITAL PHOTO FRAMEBASED ON ATMEL-VIEWABSTRACTAtmel Corporation's Atmel-View is the application for board AT76C120, it has already provided low level realization for digital photo frame, and it could be an extendable and mature solution. Based on current

3、functions of Atmel-View, we will design and fulfill the Menu System.Firstly the framework of Atmel-View, which role Menu System UI acts and how it relates with other function modules were introduced in this paper. Then the concept of SDRAM- Mapping Window with OSD's usage was proposed. It referr

4、ed to the idea of multiple image layer interface and the comparison the usage of hardware OSD and Pseudo OSD. Then the details of Menu System's framework were illustrated. The process of data abstraction, interface drawing and event handling were analyzed for the most important Menu building fun

5、ction MenuMode. After that Nucleus Plus was introduced and the method to use process communication, process synchronization for supporting Bluetooth module in Menu System was given. The UI solution provides a layered, structural and extendable Menu System for digital photo frame. And it effectively

6、supports Bluetooth module.Key words: OSD, SDRAM-Mapping Window, Menu System, UI目 录第一章 绪论21.1.软件测试简介21.2.软件测试工具发展现状21.3.项目背景和论文结构21.3.1.项目背景21.3.2.论文结构2第二章 基于模型的测试22.1.MBT一般操作流程22.2.MBT模型表现形式22.3.MBT测试用例生成22.4.MBT预期输出生成2第三章 系统架构23.1.功能概述及流程23.2.系统架构2第四章 系统各功能实现2第五章 实例分析：ATM系统2第六章 结论及展望2参考文献2第一章 绪论1.1

7、. 软件测试简介随着电子信息化的飞速发展，计算机软件已经遍布于人类社会的各个角落，远至月球探测卫星的发射系统，近至个人携带的MP3音乐播放器。但是软件带来巨大便利的同时，软件中的任何微小缺陷也可能带来难以估量的损失。据美国国家标准技术研究院（NIST）2002年公布的一份研究报告显示，软件故障平均每年对美国经济造成的损失约为595亿美元，占其国民生产总值的0.6% 1 。因此，如何保证软件的质量显得尤为关键。软件测试能够有效地帮助软件开发人员找出系统中存在的错误，从而在很大程度上保证软件的质量。现代软件工程理论将软件测试作为软件开发过程的重要组成部分，软件开发过程中有一半以上的资源都花费在软件

8、测试上。早期的软件测试等同于程序调试，1957年Charles Baker才正式将两者区别开来，他认为调试侧重于保证程序运行，而测试侧重于保证程序解决问题2。1979年Myers提出“测试是带有发现错误意图去执行程序的过程”3，越是发现了错误才说明测试过程的成功。1983年美国国家标准局（NBS）发表了评估软件生命周期各阶段的测试方法4，同年美国电气和电子工程师协会（IEEE）发布了八大软件测试相关文档的标准5，人们开始利用这些评估标准来衡量测试软件的质量。1988年David Gelperin等在书中写道，“测试是为了证明软件符合需求规约，发现缺陷和防止错误”6。时间测试阶段 -1956面向

9、调试时期1957-1978面向论证时期1979-1982面向破坏时期1983-1987面向评估时期1988- now 面向防止时期表1-1 测试的发展阶段6测试不可能遍历所有可能出现的情况，必须在适当的时候终止测试。如果一味地追求缺陷数量，很可能得不偿失。常用的判断标准有：代码覆盖率、测试用例通过率、缺陷数量收敛率等等。图1-1 缺陷数量收敛图1.2. 软件测试工具发展现状纯手工地进行软件测试往往是费时费力的，而且测试人员容易因为疏忽产生失误，测试准确性无法得到足够的保证。于是人们需要开发一些自动化工具来管理或者执行测试过程，虽然编写软件测试工具需要引入额外的工作量，但是软件测试工具能大大提高

10、软件测试的效率和质量，并且市面上也已经存在着许多现成的测试工具。名称产商简介WinRunnerMercury Interactive支持自动录制、检测和回放用户操作LoadRunnerMercury Interactive模拟大量并发负载来预测系统性能TestDirectorMercury Interactive基于Web的测试管理系统RobotIBM具有测试和管理的双重功能xUnit最流行的开源单元测试框架SilkTestBorland软件功能测试工具WASMicrosoft强大的网站压力测试工具JTestParasoft针对Java语言的自动化白盒测试工具JMeterApache100%用

11、Java实现的功能和性能测试工具WebLoadRadViewWeb性能测试和分析工具表1-2 常用软件测试工具一般来说，自动化测试可以分为：基于代码的测试和基于图形化用户界面的测试。基于代码的测试是指通过程序提供的公共接口，直接验证各个类、库和模块在不同的输入情况下返回结果的正确性与否，如xUnit系列框架。而基于图形化用户界面的测试则是通过模拟用户动作行为（比如键盘输入、鼠标点击），产生某些事件来观察和判断程序响应是否满足预期，如WinRunner。绝大部分软件测试工具并不能自动完成整个测试过程，测试人员依然需要事先编写好测试脚本或测试用例，即一组测试输入、执行条件和预期结果。测试用例能够被

12、快速和反复地执行，方便地使得发现的软件错误重现。当测试本身就需要多次重复时（比如回归测试、压力测试），其优点将更加显著。基于模型的测试（MBT, Model-Based Testing）是一种轻量级自动生成测试用例的方法，测试人员的关注点在于构建一个能够描述被测系统各方面数据和行为的形式化机器可读模型。为了抽象出理想的模型可能需要花费一定的时间，但是模型构建的工作可以在软件开发生命周期的早期就开始，只要求被测系统的需求定义完成即可。而且往往在将非形式化的需求转化为形式化的模型过程中，需求中的遗漏和不足部分将被发现。模型所带来的回报也是巨大的，因为一旦模型被确立且其能够准确反映被测系统的真实需求

13、，软件测试工具就能够分析模型自动得到测试用例。软件测试的主要目的就是发现错误。事实证明，MBT确实具有很强的错误发现能力。IBM公司和BMW公司的研究表明，MBT发现的错误和手工设计的测试集发现的错误数量差不多。而微软公司的某一应用中，MBT发现了多10倍的错误14。其它的一些研究结果中（如图1-2），和人工测试相比MBT都是发现更多或者相同数量的错误。当然MBT也不是万能的，它发现错误的能力很大程度上依赖于建模和选择测试用例选择要求人员的水平。图1-2 各种测试方法整个测试过程的花费时间图14MBT能否降低测试的花费和时间，取决于建立和维护模型加上生成测试用例花费的时间是否比其它方法设计和维

14、护测试集所需要的时间少，通常情况下答案是肯定的。而且MBT可以提高测试效率，因为人工测试受限于测试人员的思维活跃程度，MBT使用的测试用例生成算法和启发式用例选择机制能够快速生成大量测试用例，达到对模型更高的覆盖率却仅需要多花费少量运行测试用例生成程序的时间。如果SUT支持大规模地测试，MBT必然将发现更多的错误。有时侯测试用例没有通过，并不是因为程序编写的错误，而是因为系统需求定义存在错误。其它形式的软件测试一般无法发现此类错误，但是MBT可以。我们知道，软件开发中的错误越早发现需要付出的修复代价越小，MBT把一些错误扼杀在需求阶段，贡献无疑是巨大的。此外， MBT具有良好的应付软件需求变更

15、的能力。传统的测试方法很可能需要重新设计编写所有测试用例，MBT只需要调整模型后再自动生成测试用例。凡事有利必有弊，好的模型可以让测试过程一帆风顺，模型也给测试过程带来了许多问题。实施MBT的测试人员需要具有比普通测试人员更强的系统抽象能力，因为SUT很可能并不容易建模。当MBT的测试用例没有通过时，测试人员无法断定是SUT存在错误还是建模存在错误，增加了错误分析的代价。传统的人工测试的测试用例都是依据系统需求定义的，MBT的测试用例生成算法难免产生一些无效冗余的测试用例，测试用例通过率不再是衡量软件测试效率的有效标准。认识到这些MBT的不足之处，我们才能更加正确地利用MBT。目前代表性的支持

16、MBT的测试工具有：IBM公司的GOTCHA-TCBeans软件测试套件，面向Java、C/C+语言编写的应用程序接口（API, Application Program Interfaces）和软件协议7；微软公司的Spec Explorer工具，具有创建软件行为模型、可视化分析模型、验证模型有效性和根据模型生成测试用例等功能8；“净室”公司的CleanTest，主要用于净室软件工程中使用的统计测试过程9。此外，军方也积极尝试MBT技术，比如美国海军水面战中心开发的SMERFS10和CASRE11。1.3. 项目背景和论文结构1.3.1. 项目背景本课题来源于作者实习所在的微软公司，旨在遵照基

17、于模型的软件测试理论开始实现一款自动化测试工具，该工具能够支持有限状态机模型的输入，然后自动生成抽象测试用例。用户填充实现完整的测试用例后，此工具能执行测试用例并给出测试报告。该测试工具将被主要用于微软公司SCCM系统的基于角色权限控制（RBAC， Role-Based Access Control）功能的测试。特别地，在测试用例生成过程中算法需要结合参数配对组合测试技术，尽可能缩减测试用例数目却又不影响测试质量。因为与传统的单纯正交排列组合测试相比，配对组合测试技术具有较大的优越性。1.3.2. 论文结构本文第二章主要介绍MBT测试技术，依照MBT测试的一般流程来说明工具使用的模型表现形式、

18、测试用例生成算法和预期输出的生成。第三章介绍系统的总体架构和简要阐述系统各模块的功能。第四章使用类图和算法伪代码详细讨论系统的设计和实现。第五章通过一个虚构的自动取款机（ATM， Automatic Teller Machines）系统来演示如何使用我们完成的工具进行MBT测试。最后作简要的总结及展望。第二章 基于模型的测试2.2.1. MBT一般操作流程基于模型的测试依赖于三项关键技术：模型的表现形式、测试用例的生成算法和产生其它辅助性内容（包括预期结果）的工具12。模型是MBT技术的核心，不同领域的不同软件系统适用的模型表现形式都不尽相同，测试人员应该结合被测系统的工作特点和自身对模型的熟

19、悉程度来慎重选择。如果没有使用正确的模型表现形式，会拖累影响整个测试流程。针对各个不同的模型表现形式，如今已有许多测试用例算法与之对应，我们可以在实际应用过程中灵活地借鉴参考来设计自己的算法。至于产生其它辅助性内容的工具，它在不同项目之间不具有可移植性，只有根据不同项目来专门设计实现。图2-1 MBT一般操作流程13上图展示了MBT的一般操作流程。首先在系统需求或者规约文档的基础上建立某种形式的模型（步骤1），模型说明了系统所有的潜在行为意图。接下来需要定义测试用例的选择要求（步骤2），形成测试用例规约（步骤3），编写算法将其应用于模型之上来生成测试用例（步骤4）。然后在被测系统（SUT， S

20、ystem Under Test）环境中真正执行所有测试用例（步骤5-1），可以利用测试脚本来自动化执行测试，最终得到测试结果（步骤5-2）。2.2. MBT模型表现形式理想的模型需要容易被测试人员理解，能够把大的复杂的问题描述成小的简单的系统，最好还是以一种测试用例生成工具方便识别的形式。想要同时满足以上所有的特性是很困难的，但是可以把几种不同的模型整合成一个，扬长避短地得到理想模型。在MBT中使用过的模型可能有几十甚至上百种，我们不可能也没有必要去逐一了解，Mark Utting和Bruno Legeard把它们大致分为以下几种 14：类型示例基于Pre/PostB、OCL、JML、Spe

21、c#、Z基于转换FSM、状态图、UML状态机统计式马尔可夫链基于历史消息队列图、UML顺序图函数式HOL系统操作式Petri网数据流式Lustre、块状图表2-1 MBT模型分类基于转换的模型是我们最为熟悉的模型类型，它们集中于描述系统在不同状态之间的转换过程。通常是以节点和弧线的形式出现，节点代表系统的状态，弧线代表系统的动作或操作。有限状态机（FSM， Finite State Machine）模型可以被认为是该类模型的鼻祖，是极其重要的一种模型表现形式。图2-2是一个描述了门的四种不同状态及其转换关系的FSM。Harel在FSM的基础上添加了层次、并发和交流概念，扩展成了状态图模型15，

22、从而在面对复杂系统时也能够轻松建立模型。之后又有人删去了Harel的状态图模型中的部分特性，同时增加了一些新的特性，形成了统一建模语言（UML，Unified Modeling Language）状态机模型。UML状态机模型用于定义类之间状态相关的行为，包括方法调用和数据域的修改。图2-2 FSM示例我们工具主要面向的是RBAC功能的测试，频繁关心具有不同权限的不同角色所能执行的操作。把系统抽象为变量集合和修改这些变量操作的基于Pre/Post的模型需要测试人员预先学习一段时间才能完全掌握，所以基本不予考虑。我们也并不需要描述系统行为随着时间变化的变化情况，RBAC测试中不涉及分布式并发操作，

23、侧重关心系统控制流而不是数据流，可见基本的FSM模型就已经满足相关要求。而且FMS模型也最为简便，测试工具识别起来没有任何问题，降低了编写测试工具的难度，测试人员构建模型时可以从SUT设计文档中的UML状态图稍加变化直接转化而来。如果以后需要额外考虑系统事件和测试输入的概率分布，只需要为每个状态之间的迁移动作增加概率相关属性，非常轻松地支持统计式模型。2.3. MBT测试用例生成软件测试过程中的执行和监督过程已经可以使用现代化的自动测试工具代替完成，至于如何生成测试用例，依然是一件棘手的事情。MBT中使用的测试用例生成方法主要依赖于所使用的模型表现形式，针对不同的模型表现形式，研究者分别想出了

24、一些解决方案。如果系统的模型是由一系列逻辑表达式所组成的，那么可以使用定理证明的方法。定理证明方法原先是被用于自动证明数学公式，MBT生成测试用例时根据逻辑表达式的有效说明把模型划分为不同等价类，每个等价类描述了SUT的某一行为。这些等价类就可以用于生成测试用例，最简单的划分方法是析取范式的方法。当需要为程序的特定执行路径寻找输入时，沿着路径使用符号执行的方法，结合途中遇到的一些分支断言，我们可以求出预期输入所需要满足的约束。于是可以用各种约束来建立MBT的模型，收集不同执行路径中数据约束再利用约束编程中的方法求解得到测试用例。其中约束编程是一种通过约束来描述变量间关系的编程方法，求解约束的方

25、法有布尔式求解方法和数值分析方法。MBT自然还会让人想到模型检测，即检测模型是否满足特定的属性。无论检测结果是满足属性还是违背属性，都可以形成测试用例。但是一般来说反例的作用更大，因为测试用例中的各种断言正是通过反例来生成的，从而有效地识别出系统是否正常工作。模型检测会遇到的问题是，生成的用例中存在过多冗余用例,导致软件测试执行的代价增加。为此，Hamon 等人详细讨论提出了高效模型检测的方法16。类似于描述程序所有可执行路径的控制流和描述程序所有变量定义和内存使用的数据流，事件流模型描述的是GUI上所有可执行的事件序列。通常情况下，GUI又可以分为不同的层次结构，比如整个GUI系统是由各种对

26、话框所组成的，那么系统的事件流图就是由对话框各自的事件流图组成的。把复杂系统拆分为相对独立的组件单独分析，也是所有MBT测试用例生成方法通用的窍门。马尔可夫链也是MBT中生成测试用例的重要方法之一，它由两大部件组成：代表系统所有使用场景的FSM和评价FSM来说明系统统计性使用信息的操作说明。马尔可夫链模型为MBT提供了测试的侧重点，即着重测试那些用户经常使用的功能。因为对于系统中那些极少概率出现的错误，是几乎不可能被发现的。我们选用的是FSM模型，所以可以利用图论中的一些遍历方法，比如广度优先遍历算法或者深度优先遍历算法，每找到的一条可执行路径对应于一个测试用例。当FSM包含的状态比较多时，遍

27、历组成FSM有向图产生的测试用例数量可能太多，不仅难以测试包含冗余测试用例。可以通过指定初始遍历节点和限定路径长度的方法来减少生成测试用例的数量，但是更好的是下面介绍的组合测试。软件开发者和用户经常还会遇到这样的问题，把同样的软件应用从一台机器换到另外一台机器上使用时，原先从未出过故障的软件突然变得无法正常使用。问题有许多可能的影响因素，比如跟软件安装所在机器的操作系统类型有关，或者是系统物理内存的大小，甚至网卡型号等等。除了硬件环境的不同，软件接受的输入参数也很可能不同，比如同一款Web应用发布后，不同国家的用户将会输入不同编码的内容。软件能否经得住各种条件下的考验，是软件测试需要解决的问题

28、。当然，最简单和理想的情况下是把所有可能出现的硬件配置和参数取值都测试一遍。但是现实并不允许测试人员这么做，因为造成的测试用例数量是指数性爆炸增长的，N个分别有M种取值的影响因素将需要MN个测试用例来完成测试。后来人们发现通过巧妙地选取测试用例，只要求某些参数的组合情况被包含，能够在保证测试效率的同时大大缩减测试用例数量。该理论是基于以下事实的，软件中的错误大部分都是由单个参数所导致的，一般最多是由两个参数相互作用而触发，三个或三个以上的情况几乎没有。如果测试用例集包含了任意t个参数的所有取值组合，那么称该测试用例集组合强度为t，或者说它是t-way的。图2-3 不同组合强度下的错误发现率图2

29、-3是NIST报告中总结的几个应用使用不同组合强度的测试用例集测试后的错误发现率曲线17。我们可以看出，随着组合强度的增加，错误发现率显著增长。以NASA应用为例，67%的错误由单个参数触发，93%由两个参数相互作用后触发，98%由三个参数一起造成。其它应用的错误发现率曲线也都比较相像，组合强度等于4到6时错误发现率都达到了将近100%。特别的，生成2-way的测试用例集的方法被称为pair-wise（或all-pairs）测试方法。目前pair-wise是使用最普遍的组合测试技术，因为软件中的绝大部分错误都只由一个或两个参数造成，pair-wise生成的测试用例能够覆盖足够的错误空间。使用p

30、air-wise技术后，总测试用例数目从原来的MN下降到了约M * N。至于生成高组合强度的测试用例，测试用例集发现错误的能力没有实质上的提高，却会导致生成算法的更加复杂化和产生多得多的测试用例。最坏的情况下，当组合强度和参数的数目相等时，组合测试退化为枚举测试。组合测试的最早提出，也就是为了简化软件在各种配置环境下的测试。因为牵涉到硬件环境的搭建，配置参数测试中每增加一种测试情况比单纯地多写一个测试用例所花的代价大得多。人们迫切需要解决这一问题，使得配置参数测试成为了组合测试中最为发达的形式，尤其在那些要求适应不同硬件平台和环境的软件的测试过程中。考虑一款受5个配置因素影响的应用：操作系统（

31、Windows XP、Apple OS X、Red Hat Enterprise Linux），浏览器（IE、FireFox），网络协议（IPv4、IPv6），处理器平台（Intel、AMD）和数据库（MySQL、Sybase、Oracle），一共3·2·2·2·3=72种硬件平台。pair-wise测试只需要设计如下10个测试，就覆盖了每一种影响因素和另外一种影响因素的所有组合。编号操作系统浏览器网络协议处理器平台数据库1XPIEIPv4IntelMySQL2XPFireFoxIPv6AMDSybase3XPIEIPv6IntelOracle4OS X

32、FireFoxIPv4AMDMySQL5OS XIEIPv4IntelSybase6OS XFireFoxIPv4IntelOracle7RHELIEIPv6AMDMySQL8RHELFireFoxIPv4IntelSybase9RHELFireFoxIPv4AMDOracle10OSXFireFoxIPv6AMDOracle表2-2 pair-wise测试的配置即使被测软件没有配置选项，软件仍要处理一些输入。例如，Word 2010应用程序至少允许用户对拖黑文字进行10种不同操作：设为上标、设为下标、加粗、加下划线、设为斜体、加删除线、加灰色背景、加阴影效果、加倒影效果、加荧光效果。相关的字

33、体处理函数需要根据用户的输入来相应修改文字效果，该函数需要在所有的可能情况下都正常工作，而一共有210=1024种可能。前面的经验告诉我们，3-way的测试用例就能够达到90%以上的错误发现率，具有较高的收益-代价比。图2-4 3-way覆盖数组图2-4列出了对于具有10个变量、每个变量各有两种取值的3-way覆盖数组。覆盖数组并不唯一，这只是其中一种情况。t-way覆盖数组的特点是，任意t个参数的所有排列组合都将分别出现在覆盖数组的某一行中，比如上图中的ABC、DEG、HIJ，三个参数共有8种排列组合（000、001、010、011、100、101、110、111）都被覆盖数组所覆盖。覆盖数

34、组的每一行对应一个测试用例，相比之前的1024个测试用例，组合测试只需要13个测试用例。组合测试用例生成的本质是构造覆盖数组，最早的构造方法是利用正交数组，其定义和覆盖数组类似，唯一区别在于正交数组中所有t元组出现的次数相同，而覆盖数组不保证这一点。在某些特殊的情况下，正交数组就是最优的覆盖数组，为此，如何构造正交数组问题吸引了大量的研究者研究。Sloane在其网站上总结记录了超过200个正交数组18。利用计算机也可以自动求解出部分类型的正交数组，由已知的大覆盖数组构造小覆盖数组的方法被称为坍塌19。坍塌的缺陷在于，最终得到的覆盖数组往往并不是最优解，一般比最优解要大。另一种构造方法刚好相反，

35、是由已知的小覆盖数组递归构造出大覆盖数组。构造最优覆盖数组的实际上是一个NP完全问题20，我们知道，NP完全问题是一系列可以互相转化的问题。于是我们可以利用和借鉴其它NP完全问题的研究成果来构造覆盖数组，比如第一个被证明为NP完全问题的可满足性问题，整数规划问题，图论问题等等。数学构造方法仅限于某些特定大小或者组合强度的覆盖数组的构造，不具有通用性。NP完全问题则是困扰了人类多年的超级难题，目前还没有突破性解法，所以转化为其它问题也是大同小异。但我们可以利用局部搜索方法，比如启发式搜索算法，在较短的时间内就可以搜索出近似最优解。启发式搜索算法是利用一个已有的数组，通过合适的变换得到一个更优的覆

36、盖矩阵，不断地变换直到得到一个较优的矩阵。近年来流行的模拟自然界行为的智能优化算法中，目前已经应用到组合测试中的主要有模拟退火、禁忌搜索、遗传算法等等。更为有效的方法是贪心算法，贪心算法的思想是从空矩阵开始，然后逐行或者逐列地扩展矩阵，直到所有的t元组都被覆盖。按照扩展方式的不同，又可以分为一维扩展和二维扩展。商业工具AETG最先提出一维扩展的方法21，依次增加一行，每次尽可能多地覆盖未覆盖的t元组。微软开发的工具PICT采用类似AETG的方法生成测试用例22，不同之处在于，PICT每次产生的结果是相同的。Lei等人提出的IPO（In-parameter-order）23方法属于二维扩展，该算

37、法主要针对pair-wise测试。首先构造前两个参数的所有组合，形成一个小的矩阵，再分别为矩阵添加一列和必要多的行，覆盖完所有元组后结束。我们将模仿PICT工具中pair-wise算法的主要思想，使用一维扩展的贪心算法来生成覆盖数组。同时给系统留好接口，利于以后换用新的pair-wise生成算法，具体的算法设计将在第四章介绍。2.4. MBT预期输出生成三大关键技术就只剩下辅助性内容生成工具了，辅助性工具主要还是为了解决预期输出的生成问题。前面我们构造了系统的模型，模型描述了系统的状态和状态之间的动作，这些动作都是由一个个函数和方法的调用序列组成的。SUT提供的API往往不能和测试用例的要求完

38、全契合，为了让测试用例能够顺利地在SUT上执行，需要测试人员在SUT之上再包装一层，即图2-1中的适配器层。严格地说，我们编写的工具只负责生成基本的测试用例框架，或者称为抽象的测试用例。测试用例中相当于使用了打桩的设计模式，桩的实际实现由最终的测试人员补充完成，桩的实现包括对SUT提供的API的封装组合和测试判断逻辑的编写。我们把这些桩叫做token，token对应于适配器层中的某个函数和方法，两者可以直接一一对应，也可以先序列化为可扩展标记语言（XML，Extensible Markup Language）文件再利用XML解析器之类的工具生成测试用例。这样MBT的整个测试工具都变得项目之间可

39、移植了，如果某一测试条件和预期结果不同则在token中抛出异常，抛出的异常随后被测试工具捕获，最终判定该测试用例不通过。图2-5展示了一个测试工具自动生成的测试用例，用户需要实现token_1和token_2的具体逻辑，然后测试用例就能够被真正执行了。token_1和token_2执行过程中如果发现错误会触发异常，程序打印出错误提示，同时导致测试用例的总错误个数加一。反之，一切正常并给出通过提示。图2-5 测试用例示例另外我们也可以利用pair-wise来完成部分情况下预期输出的生成。对于相同输出结果的某些参数取值组合，把输出结果也当作pair-wise算法输入参数的一项，输出结果列和其它输入

40、参数的区别在于其取值唯一。PICT工具还支持混合组合强度的测试用例生成，以及输入各种约束，比如指定某些参数的组合形式必须出现或者不出现，所以具有较强的预期输出生成能力。不过如果预期输出涉及复杂的判断逻辑，还是使用委托给token来处理的方法较好。第三章 系统架构3.3.1. 功能概述及流程课题要求完成的基于模型的自动化测试工具的功能包括：支持输入FSM模型、支持添加token、支持pair-wise组合测试、支持生成测试用例框架、支持序列化FSM模型到文件和反序列化读入。其中考虑到token的可复用性，用户可以直接在工具上定义token顺序执行序列组成的函数过程，更复杂的函数过程则通过添加新的

41、token实现。用户使用该工具生成测试用例的流程如下：图3-1 生成测试用例流程用户可以直接绘制FSM模型，或者在以前保存的模型基础上修改模型，工具支持FSM模型的序列化与反序列化。绘制FSM模型时首先需要定义一些FSM的状态转换动作中用到的token和这些token组成的若干函数过程，随后在模型绘制面板中画出FSM模型相应的有向图。FSM模型的有向图包括代表不同状态的圆形节点，以及代表状态间转换动作的弧线。一个token或函数过程可以在相同的或者不同的状态转换动作中被反复使用，只要求这些token或函数过程方法头中所定义的参数被正确地赋予某个常量或者变量。变量可以有多个允许的取值，用户在pa

42、ir-wise相关面板输入各个变量的可能取值，接下来工具将分析FSM模型寻找所以可执行路径，同时结合路径长度限制和pair-wise技术来生成测试用例。最后用户还可以在生成的测试用例中再人工选择部分测试用例出来，保存为最终需要被执行的测试用例。3.2. 系统架构工具设计的主要目的是为了自动生成测试用例，而模型是驱动MBT各测试过程的根本，所以系统架构中最核心的部分是FSM的数据模型，数据模型描述了FSM中各个状态和转换动作的详细属性。比如状态名称，转换动作名称，用户所定义token的名称和所需输入输出参数，函数过程的名称和其中包含的token执行序列等等。图3-2 系统总体架构用户不是生硬地使

43、用形式化语言来描述FSM数据模型，工具提供了可视化界面，实现了鼠标选取不同绘图元素再拖拽调整的绘图方式。此外，为了持久化保存绘制好的FSM模型，系统包含了序列化模块，用于模型的序列化与反序列化。测试用例的生成过程是基于两大模块来完成的，FSM模型遍历模块负责生成各种可执行路径，pair-wise测试模块负责生成参数变量取值的不同组合。最后把参数变量取值代入可执行路径中，即得到测试用例。第四章 系统各功能实现4.前一章中我们介绍了系统的整体架构，下面将逐一介绍系统各模块的具体实现，整个系统都使用C#语言编写完成。4.1. FSM数据模型实现我们知道FSM数据模型是影响系统的关键，图4-1列出了系

44、统实际实现过程中FSM数据模型相关各类之间的关系。对于一些简单的set和get方法图中并没有标出，其它辅助性的方法也予于省略。图4-1 FSM数据模型的类图类FSM中记录着系统FSM数据模型的所有信息，它里面有两个链表分别记录FSM的状态实例和转换动作实例，同时有两个Dictionary分别记录状态和转换动作的名称与实例之间的映射关系。状态由类State描述，该类的属性有状态标识id、状态类型type和状态后置动作链表nextActions。我们定义了三种状态类型：Entry、Free和Exit，Entry和Exit分别代表初始状态和终止状态，Free代表其他自由状态。状态动作由类Action

45、描述，该类的属性有动作标识id、出发状态名称from、目的状态名称to以及动作的方法实现链表stubs。在寻找可执行的测试路径过程中，程序从初始状态开始深度遍历FSM有向图，直到到达某个终止状态或路径长度达到限制才结束。类Tour的每个实例代表一条被发现的可执行路径，因为用户并不参与Tour的命名，所以该类中设置了一个全局静态的标识计数器域idCounter，每新创建一个新实例时计数器自动加一，必要的时候可以通过ResetIdCounter方法重置计数器。除了以上代表FSM实体组成部分的类，FSM数据模型还必须描述SUT相关部分的信息。抽象类ActionImpl描述了测试中调用的SUT接口，准

46、确地说是测试适配器层中的接口，它的两个抽象方法GenDefault和GetCopy分别用于初始化和返回克隆实例。类TokenImpl和类FunctionImpl继承了类ActionImpl，其中类TokenImpl表示的是用户定义的基本token，而类FunctionImpl表示的这些token顺序序列组成的函数过程。考虑到函数过程和转换动作的相似性，类FunctionImpl中直接包含了一个类Action的实例。最后，注意一下参数和变量的区别：参数指的是函数方法头中定义的输入，而变量是在实际调用函数方法时对参数的赋值。我们使用类Parameter来表示参数，而用类Variable来表示对参数

47、的赋值，包括常量和变量。类Variable中包含一个根据其标识名称name来判断的方法IsVariable。4.2. 可视化和序列化实现系统的用户界面部分是利用WinForm技术实现的。虽然WinForm技术中已经提供了许多可以直接使用的组件，但是距离我们的要求还是有一定差距，所以我们自己设计实现了新的组件来完成FSM模型的可视化。图4-2 FSM模型可视化模块的类图接口IRenderable定义了新组件通用的属性和方法，包括组件的位置信息、绘制组件过程中触发不同事件的响应函数（Paint、PrePaint、PostPaint和PaintFocus），方法IsSelected则用于判断该组件是

48、否被鼠标选中。类StateR和TourR直接实现了接口IRenderable，但是类ActionR和类FunctionR实现的则是接口IRenderable的扩展接口IActionRenderable，该接口添加了一个保存转换动作信息的域。这些类对应于FSM数据模型中的类，绘图的实际过程由C#语言提供的系统类完成，涉及到的API24参见表4-1。方法名称作用DrawCurve绘制经过一组指定的Point结构的曲线DrawLine绘制一条连接由坐标对指定的两个点的线条DrawPolygon绘制由一组Point结构定义的多边形DrawString在指定位置并由指定的Brush和Font对象绘制指定

49、的文本字符串FillEllipse填充边框所定义椭圆的内部，该边框由一对坐标、一个宽度和一个高度指定表4-1 类Graphics部分方法图4-3展示了这几个类的绘图效果，类StateR绘制紫色的圆圈代表状态节点，类ActionR则绘制了两种代表转换动作的深绿色弧线。如果出发状态和目的状态相同，那么将绘制如action_0的弧线；如果出发状态和目的状态不同，则按照事先设计的弧度在两个状态节点之间绘制如action_1的弧线，另外增加一个三角形标志表明方向。类FunctionR以灰色粗线加圆点的形式绘制用户自定义函数过程的标记，默认排列在FSM绘制区域的左上角。类TourR把用户选中的可执行路径用

50、黄色重描一遍。图4-3 自定义UI组件示例C#语言提供了方便的标记功能来支持对象的序列化与反序列化（图4-4）。首先把准备序列化的对象标记为Serializable，然后根据不同的需要和属性特点把公共属性都标记为XmlAttribute、XmlArray或XmlIgnore，公共属性中的自定义类型也需要在定义文件中添加相应的标记。每个希望被序列化的公共属性必须提供set和get方法，否则该属性无法被正确序列化到XML文件中。XmlAttribute表示把该属性作为对象XML根节点的一个属性；XmlArray表示该属性是数组类型的，整个属性将被添加为根节点的一个子节点，另外每个数组元素又会被序列

51、化为该子节点的一个子节点；XmlIgnore则表示忽略此属性，该属性不参与对象的序列化过程。系统类.XmlSerializer使得编程人员能够控制如何将对象编码到XML文件中，并且支持从XML文件中重新创建原始状态的对象。接下来FSM模型的序列化与反序列化工作只要通过调用类XmlSerializer的两个简单方法就可以了。方法Serialize负责把对象的某个实例序列化到某个输出流中，方法DeSerialize则负责从某个输入流中反序列化出原始状态的对象。图4-4 XML序列化与反序列化示例代码4.3. 模型遍历算法实现显然测试的基本要求之一应该是至少把FSM模型中的每个状态和每个转换动作都执

52、行一遍，不过这样并不能很好地覆盖被测代码，而且许多重要的测试场景都会被遗漏。最为全面地测试FSM模型的方法是找出其有向图中的所有可执行路径，然后把它们都转换为测试用例去执行。但是这样遍历出来的测试用例数目又往往过于庞大，其中很大一部分还是冗余性测试用例。折衷的办法是通过路径长度来限制测试用例的产生，同时用户构建FSM模型时有意识地把复杂系统拆分为几个子系统来单独进行测试，绘制FSM模型时也可以分别指定不同的初始状态来寻找路径。对于工具生成的测试用例集，用户还可以在条件允许的情况下筛选出与SUT使用场景紧密相关的部分测试用例，形成最终的测试用例集。图4-5 模型遍历算法核心代码模型遍历算法的本质

53、是图论中的广度优先搜索（BFS， Breadth-First Search）算法，图4-5给出了算法的核心代码。算法初始时中间结果链表tours中只有一项包含初始状态entry的路径，以后每次迭代都检查tours里的每个出口状态的下一转换动作，试图增长一个单位的路径长度。为了不让搜索得到的路径包含太多重复回路，如果新扩展的动作已经被原路径多次包含，该路径及其扩展路径都将被抛弃。此外，路径的末状态必须为出口状态，并且没有后续动作或者指向其自身，路径还必须满足设定的长度要求。4.4. pair-wise测试实现此部分的实现主要模仿微软PICT工具22，运用一维扩展的贪心算法策略逐步得到覆盖矩阵。算

54、法分为两个阶段：准备阶段和生成阶段。图4-6 参数组合示例22准备阶段将计算出生成阶段所要用到的各种信息，包括需要被覆盖的不同参数取值组合。假设我们需要对A、B、C三个参数进行pair-wise组合测试，A和B有两种可能取值，C有三种可能取值。那么它们之间的两两组合情况有：AB、AC、BC，具体的取值可能如图4-6所示，pair-wise测试的最终目的就是全部覆盖这些取值情况。PICT中把每种取值情况分为三种状态：已覆盖、未覆盖、排除，我们实现的自动化测试工具中不考虑带有约束的pair-wise测试，所以只有前两种状态。每当生成一种新的测试用例时，被新测试用例覆盖的取值情况状态会跟随之改变，算

55、法直到所有取值情况的状态都为覆盖时终止。图4-7 PICT算法伪代码22原始算法的伪代码如图4-7，算法生成新测试用例时优先选取种子组合，即某些测试者认为比较重要，应该优先出现的取值组合。我们不考虑此特性的功能，下面介绍如何完成新测试用例ri的生成。如果ri为空，那么选择一种剩有最多未覆盖取值组合的参数组合，比如图4-6例子中生成第一个测试用例时AB剩有4种取值组合，而AC和BC则各有6种取值组合。当存在多个相同最大剩余取值组合的参数组合时，只选择第一个参数组合的第一种取值情况，即AC的00情况首先被选用。因为ri中还有未确定取值的参数B，所以继续while循环到else部分，考虑所有取值情况

56、集合P中包含至少一个未确定取值参数的子集Q，再从Q中筛选出与ri取值一致的取值情况。于是我们筛选出了AB的00、01，BC的00、10。如果在这些筛选出的取值情况中有未覆盖组合，那么选择能新覆盖最多取值组合的一项；如果它们都已覆盖，那么随机选择一项。这里筛选出的4种取值情况都只能新覆盖1种取值组合，所以使用AB的00，至此我们就生成了第一个测试用例，随后的测试用例生成都如上述过程。为了方便调试和用户扩充pair-wise算法，该模块被设计为独立的可执行文件。系统调用该模块时，首先通过配置文件提供的路径定位，然后利用系统类另外启动一个隐藏命令行窗口的进程运行。对于测试工具来说，这些操作都由类Pi

57、ctFile封装。用户自己实现的pair-wise算法只要满足输入参数和输出格式与我们设计的相同，即能够在配置文件中指定并良好地整合。输入参数和输出格式由类PictInputVariable和类PictOutputVariable说明，因为输出都是包含一组参数的取值情况的，所以类PictOutputVarList内部封装了一个类PictOutputVariable的链表。图4-8 PICT相关封装类4.5. 最终测试用例集实现有了模型遍历算法的实现和pair-wise测试算法，结合两者我们就能构建生成最终的测试用例集了。类SuiteMaker提供添加这两个模块所需要信息的接口，比如图4-9中列出的AppendToken、AppendFunction、AppendCaseGroup和AppendVarMap。方法