TESTOR-基于模型的范式获得测试序列.doc

TESTOR：基于模型的范式获得测试序列

摘要：基于组件的系统的可靠性分析可以使用专门的组件或系统工具，也可以使用基于模型的范式，此范式可先于工具或可与工具一块使用。尤其，组件系统的基于模型的范式能明确地模拟出组件的结构、性能及组件的集成。而基于模型的测试可以获得测试序列，此序列能连续产生测试实例并在系统工具上运行。
迄今，已经提出了几种可进行基于模型的测试的几种方法，但是其中很少几种方法表现了特有的可用于工业环境的特性。这里，我们要说明的是TeStor，一种允许从状态机和序列图中得到测试序列test sequence generator算法。我们来详述这一算法，将其应用于系统研究，并提供与它的实现工具的联系。

1、 导论
粗略的说，一个基于组件的系统是一组可重用的组件的集合，组件的设计需满足质量标准，此标准将会在[10]体系设计中介绍。组件可被设计和可重复使用，并在各种各样的环境下装配，以生产出大量的软件。
一个基于组件的系统的可靠性极大地取决于组件的质量和组件集成后的质量及其体系结构。当一个组件的质量可能被孤立地进行分析时，组件集成后的质量则要在组件集成后方可得到测试。
过去，要进行准确的测试需要组件装配完成之后才可以，随着模型的发展，在组件研制或购买前，模型本身就要被分析。模型发展是一个（非常老的）想法，即一个系统的成功很大程度上是通过示例法和抽象系统的结构与性能而获得的。而模型分析的本质是这样一个想法，即运用模型来代表（预期的）系统结构和性能，以估计系统所能达到的某些质量，并在此后确保该系统的实现。
本文中，我们在整体上把注意力集中在基于组件的系统的模型测试。我们认为组件的结构和功能是已知的，以及当组件集成系统时组件之间是怎么样相互作用的也是已知的。我们的算法的目标是为了得到可靠的测试序列，用来测试组件集成后的符合度。
迄今，许多不同的方法和工具已经被提出，可从系统模型中得到测试用例。（相关的基于模型的测试方法将在第2部分略述。）然而，这其中极少部分可能被认为适用于“工业环境”。在[7]中叙述的，事实上，一个基于模型的测试方法要适用于工业需求必须以从一些额外的要求和限制：首先，我们不能认为一个正式（完整且一贯的）软件系统的固定模型存在。相反，我们可合理假设的是UML图形式的一种非正式的范式。此外，这种方法应该是可用的（另外的形式不应该被要求），及时的（甚至不完整的模型就可以开始描述一个测试计划），并且有工具支持的（自动化的工具支持能从根本上降低测试花费）。令人惊讶的是，即使目前许多基于模型的测试方法已经提出，但是其中很少满足这样的要求。
这里，我们提出的test sequence generator(TESTOR),它可以从基于模型的范式中得到可用的测试序列。每个组件的功能模式都以UML状态图的形式提出，这样的模型明确地说明了哪些组件相互作用和如何进行相互作用。序列图被用作一个抽象的甚至是一个未完善的（粗略的）范式，此范式是该测试必须包括的。TESTOR将UML状态机和序列图输入，并且通过从状态图中重新获得缺失信息来综合出更详细的序列图（符合理论方案）。输出信息表明测试序列（其中包括一组测试中的系统的响应及对这些响应的预期反应[14]）以更信息化的方案形式来详细说明。与其它的方法不同，在TESTOR中，测试序列的形成过程不需要计算状态机模型的并行成分，也不需要任何附加方法，它完全由工具支持的。
下文中将进行如下安排：第2部分中，我们将分析一些相关工作。利用第3部分来叙述一下TESTOR算法。第4部分叙述TESTOR是如何完成的。第5部分提供了这一建议性的算法的初始估算。而第6部分则对本文进行总结。

2、相关工作
近些年来，明确的模型的运用在软件发展过程中得到扩展。（最显著的是面向对象分析和设计中UML的运用）。许多研究人员将他们的研究点放在了通过描述各种系统模型来寻找指引测试活动的各种方法和工具[2]。在这个部分，我们简略地总结出目前利用UML图来做测试的一些研究结果。
许多基于模型的测试方法是以状态机为基础的。最初在测试中尝试运用UML状态图的是Offutt和Abdurazik[21]，他们将这些图转化为正式的SRC详细说明；还有Liuying和Zhichang[18] 运用状态机的规范语义来获得测试实例；Kim et al.[17] 则致力于研究分类测试。前些日子，Hartmann et al.[15] 把[21]中的方法扩展到基于组件的实例中，而Antonniol et al.[5] 则设想通过覆盖FSM里的被选路径后得到源于UML状态图的测试序列。
基于序列的测试的相关建议包括：(1)Graubmann和Rudolph[12]的方法，即测试实例范式序列图中包括了信息序列图表（MSC）联机表达式和高水平信息序列图(hMSC)；（2）Harel和Marelly[13]的方法,此方法是为恢复系统基于序列的范式而特别设计的；（3）为导出测试结果、测试地点和测试操作者，TOTEM[8]（具统一模型语言的测试面向对象系统）利用了与每一个实例相关联的序列或协作图；（4）SENTOR[25]以Junit 为基础来得出测试实例的来源。（5）由于各种类别和方法在序列图中是指定的，SeDiTeC[11]会自动为他们生成测试小程序。目前[6]中正在讨论Cow Suit工具和方法能否在工业背景提供一个整体又实际的手段来生成或设计UML基础测试设备。
很少有方法，比如我们的，在测试实例生成中，需要同时使用状态机和序列图。UMLAUT（通用模型语言多用途转换器）[3]能通过测试生成检验工具（TGV）将UML图转换成一种中间的易识别的正规说明。AGEDIS（基于组件的分布式软件的自动生成执行测试程序）[1]为了应用模型语言，根据AML（一种专门的UML配置文件）产生和执行测试实例。SCENT（基于序列的有效的测试软件）以结构的方式产生序列图并将其转为状态图。
我们的工作分享了他们用系统模型指导测试活动的思想，尤其是分享了他们UMLAUT，TGV，AGEDIS和SCENT联合运用状态和序列图的思想。不同于其他运用UML图建构和测试手段，我们将自己置于一个基础组件的背景中，在这种情况下，状态图模拟组件在组件系统中是如何运行的。

3.测试序列的生成算法
根据[14]，基于模型的测试序列生成算法，以测试中的软件模型和可指导测试实例选取（在[16]中被称为test purpose）的测试指令集为主要输入数据，然后可输出一个测试范式，它包含一组响应，此响应连同预期反应一起被测试机导入系统中。
基于模型的测试序列生成算法（TeStor），输入组件的运作模型（以组件的状态机为条件）和一个显示测试指令的序列图（inSD），然后输出一系列显示最短路径的序列图（outSD），这些最短路径覆盖inSD.换句话说，每一个输出序列图包括了由输入序列图传达的信息，输入序列图因组件状态机收集的信息而提高或完善。值得注意的是TeStor算法在无需构建全局自动化的情况下，如无需并行组合不同的运转状态，就可以通过分别刺激不同的状态机来识别不同的测试序列输出图。这一重要优化可解决著名的状态剧变问题。
我们研究了一个案例以有助于解释TeStor的运行方式。图.1.a-d）说明状态机与西门子C.N.X光通信系统（OSS）的系统结构有联系。每一个状态机表示一个组件，并且，假设信息只能通过一对组件转换的话，转移标号可识别被转换的信息。因为每一个转换中，?或！被规定了以下含义：?l[!l]识别信息l的输入[输出]。
光通信系统（OSS）及其系统结构已在[20]中作了介绍，也不再本文的讨论范围内。（状态机的标识被重新命名以增强可读性）。用作测试指令的序列图在图.1.e)中作了说明。

图. 1.a - d) SA 组件运行状态, e) 输入序列图（inSD）

通过聚焦输入序列图中的首要信息m(非被访问)和浏览每一个状态机，TeStor可从状态机的当前状态开始，搜索能抵达m的路径。当找到此种路径时，TeStor递归移向输入序列图的下一信息m′(非被访问)，并检验从当前状态开始可抵达m′的路径。在程序的最后部分，TeStor试图用一种特殊的路径（输出序列图）合并不同的路径，这种特殊的路径从初始状态开始移动直至覆盖输入序列图中的所有信息。

图. 2. 生成的四种路径（The four traces generated）

图. 2.显示了应用TeStor到图.1.的案例后生成的四种输出序列图路径。为增强可读性，我们描述了每一个组件的输出序列图的生命线和信息转换后组件达到的状态。按TeStor算法，m9最先从图.1.e)的输入序列图中被选取。从四个状态机的起始状态开始，组件C2和C3能交换m9。C2转换成状态s1。接着，m3在输入序列图中被选取。C1和C2能从它们的当前状态（分别是s0和s1）抵达m3。每当分析输入序列图中的最后信息时，另一算法“合并”，会通过检验不同组件的运行是否同步及何时同步，来合并不同的路径。
TeStor算法可分为两个步骤：
1. 状态机直线化: 从sm的当前状态s开始，而不是跨越m去识别可抵达m的路径，我们开始在一系列线性路径中分解sm。为限制直线化路径的数量，TeStor会避免循环和重复，比如每一条路径分支是空的，每一对路径不能共享交换。
2. 测试序列生成：第二个步骤包含了测试序列的生成。为识别输入序列图中的主路径，此步骤会监测每一种直线化状态机。主路径容纳了输入序列图中的所有信息，且信息顺序与输入序列图中一致。它还包括任何其它可在状态机中模拟输入序列图路径的必备信息。由于循环能被移动，由TeStor生成的主路径是极小的。这种算法里有一个生效区域，它能检测主路径应何时合并、怎样合并以生成输出序列图。
下面我们将详述TeStor算法。3.1和3.2部分我们会详细阐述直线化和用于TeStor的测试序列生成算法。为简明起见，本文省略了可见于[23]的算法细节。
TeStor运用了一下方法：
—— MessageSet messages(SD sd):信息设置，返回序列图sd中信息
—— boolean isEmpty(Set s): 当且仅当集s空闲时，回送true
—— delete(Set s, Element el):从集s中删除元素el。
—— add(Set s,Element el):添加元素el至集s。
—— updateIs(SD sd)：更新每一个状态机器初始状态的方法。
对每一个状态机器（sm）来说，直线化算法是被调用的(lines 2-5)。我们假设每一个状态机器都处于它自己的初始状态中。
TeStor 伪程序（Pseudo-Code）

在lines 6-24，TeStor算法试图为每一条信息m构建主路径，并把这些路径合并以获得想要的输出序列图。对输入序列图中的每一条信息m来说，测试序列生成法就被启用。它返回一组sdSetMsg的路径，其中包含了信息m和任何其它能交换信息m的附加信息。每一条信息产生一组路径的构建。为给输入序列图生成一条唯一的主路径，输入序列图中任何一条信息的主路径都需被合并。应当注意的是，updateIs法的调用领先于测试序列生成法的调用，因为每一条路经均须设立不同的初始状态。Lines9和17中提出的错误可以确定在状态机SM集内部再生成输入序列图是不可能的。当此种错误出现时，说明输入序列图和状态机器间的不相容。Lines19-22的编码，通过为当前信息m追加已经得到的路径至已存储的输出序列图，可构建出输出序列图。比如，为领先于输入序列图中m的信息构建路径。

3.1直线化
从组件状态图的初始状态开始，每一种交换中都含有直线化算法，此交换存在于某种状态至初始状态，或者目标状态。大致而言，直线化程序创造了一种任何时间都可抵达分支状态的路径。（比如：输出度＞1或输入度＞1的状态）。从先前已抵达的状态开始直至现存的未访问状态，这种算法是迭代的。
生成的直线性路径数量可用以下方式计算：

以下是直线化的属性特征：
1.划分中介状态（处于路径中间的状态）和外部状态（路径的起始或目标状态）。
——外部状态是所有输出度＞1或输入度＞1的状态，或者是起始状态，或者是结束状态；中介状态是其它的状态。
2.直线化不会丢失信息。比如：可从直线化状态开始重构初始状态机。

用于光通信系统（OSS）的直线化：下面我们展示将直线化算法应用于图.1.的案例后产生的结果。作为一个案例，我们将解释组件C2的路径是怎样获得的。C2的初始状态是S0(如图.1.b所示)。因为输出度（S0）=2，所以S0是一种外部状态。正是由于信息8才创建了路径1。路径2跟随m9指示的路线并以输出度等于2的状态S3为终点。当循环信息m9生成路径3时，路径4是抵达状态S0的路线。

3.2测试序列生成
测试序列生成的输入数据是信息m和可识别已探查状态机及相关路径的两个集合，而输出数据是能显示不同路线的路径集，这些路线引导系统交换信息m。用于递归的第一和第二种输入数据，可传播每一个状态机抵达的状态及构建的路径。两个集合在第一次调用中是空闲的。
设Cs(Cr)为发送(接收)信息m的组件。这种算法首先从Cs和Cr的直线性路径中生成两组路径集合，最后用合并法将它们合并，然后生成输出序列图。
测试序列生成运用了直线性状态机并可用以下方式合成：
1.当m必须被交换时，设C的状态为is
测试序列生成法会选取含m的直线性路径。我们检测每一个被选取的路径t是否包含is状态，如果包含了is状态，路径t就被选取。否则我们须检测能否合并一些路径以达到is状态。这些路径的选取遵守以下规则：i)若路径包含两倍的信息m，它会被拒绝。ii)若路径添加了一个循环(可达到一种被访问状态)，那么它也会被拒绝。
这一过程由生效法实现并能识别可能包含新信息的主路径，这些新信息迎合系统的需要以达到一种可以交换信息m的配置。
2.主路径中的任一添加信息出于需要都会引进其他信息。事实上，对每一条添加到主路径的信息来说，测试序列生成算法被调用时会同时伴随已更新的状态机和已构建的作为参数的路径。
对算法的完全描述请参阅附录A。下面将详述生效算法和合成算法。

生效：这种算法的输入数据是路径t，信息m，路径t的当前状态cs，组件C的初始状态is(组件C包含路径t)和用作避免无限循环的路径集tr。这种算法的输出数据是主路径集ST，一种有效路径。
如果无法抵达初始状态is，它也会执行有效性检测以返回一个空集。
生效算法里我们运用以下方法：
——append(Trace tr1,Trace tr2)：将tr2.tr1指定到tr1.。
——Trace subtrace(t,s1,s2)：返回t的主路径，t的主路径以s1为起点，s2为终点。
——tracesSet tracesToValidate(s)：返回路径集以及须被验证的目标状态s。
——boolean contains(t,m)：当且仅当路径t包含了转换信息m时，返回true
——State initialState(Trace t)：返回送路径t的初态。
——State finalState(Trace t)：返回送路径t的终态。

生效法功能的编码可分为三个部分：i)重合当前状态cs和初态is，lines5-9；ii)抵达路径t的起始状态，lines10-14；iii)由tracesToValidate迭代区别其他路径，lines19-29。在主路径的递归构建中，含已考虑信息m的路径通过生效法的嵌套调用进行循环，在一种状态上循环的路径不作考虑。(lines19-27)
生效伪程序（Validation Pseudo-Code）

合并法：这种方法输入两组序列图并试着将它们合并为一个单序列图，每一个序列图包含一组须输入序列图中的信息，但也可以添加其他信息以满足一些组件需要符合输入序列图的要求。然后合并法会试着把各个序列图和并在第一组，同时在第二组中保留每一个序列图。
纳入输入序列图的每一条信息用下列推理迭代：
设当前信息m及其原信息m′。我们确信m和m′均被纳入序列图中（如果m′存在的话）。我们须牢记每一个序列都是完整的，以确保系统无需附加信息就能交换信息m，然后设第一组的信息集为setS，第二组的信息集为setR。这种算法可以检测是否存在一个信息排序可以使系统按照支配其运转状态的状态机去交换setS和setR中的全部信息。
应用于光通信系统（OSS）的测试序列生成：下面，我们用案例来说明TeStor如何工作。我们仅考虑图1方案中的几个步骤。如图1.e)所示，输入序列图的第一个信息是m9。3.1节中利用了m9的路径和组件C3、C2相关，组件C3和C2的发送器是C3（与状态机SMs关联），接收器是C2（与状态机SMr关联）。
通过分析为发送器和接收器生成的路径，有用的路径是 itcs = {1} 和 itcr = {2; 3}。因为itcr中的路径3只能通过循环达到起始状态，它就没有用。至今，已获得的sdSet只包含一个序列图：通过转换信息m9，组件C3达到状态S0，C2达到状态S1。
图1.e)输入序列图中的第二条信息是m3. sms = C2 和 smr =C1. itcs = {2} 和 itcr = {3; 7; 10; 13}。必须考虑的路径是：组件C2的路径2和组件C1的路径3、路径13。路径3因能抵达状态S0而被选取。路径7因下列理由而无法被选取：其初态是S1；可抵达状态S0的路径是路径3、4和16，但是路径3和4因为会导致循环而被删除（路径3也包含信息m3）。路径16必须考虑路径9、10、13、14这些会导致循环或包含信息m3的路径。路径13能被选取是因为它能合并路径5达到状态S0，S0或的路线S0 m4 S2 m6 S6 m3 S7.
然后路径3和13构建两个不同的序列图。第一个序列图仅需交换信息m3，m3可指示组件达到状态S0，组件C1达到状态S1。第二个序列图要求在信息m3,m4,m6之前包括串联路径13、路径5后得到的主路径。
达到的状态如下：序列图1中C1is = S1, C2is = S2, C3is = S0, C4is = S0 和序列图2中 C1is = S7, C2is = S2, C3is = S0, C4is = S0.
同样的推论可应用于余下的信息。仅有另一信息m1生成两种不同的序列图。所以，如图2所示，获得的序列图有4个。

4.辅助工具
实现TeStor算法需有Charmy插件，作为结构性分析的一个有效的框架。TeStor插件的测试版可见于[4]。
当标准化的Charmy能编辑SA拓扑结构，组件的运行，输入序列图时，TeStor插件会输入此信息并产生输出序列图。
图3显示了Charmy的一些屏幕截图及其TeStor插件。图3.a显示了序列编辑程序，它能画出输入序列图和产生的输出序列图，而图3.b生动描绘了线程编辑程序，它能说明每一个组件的运行状态。

Fig. 3. Some screenshots of TeStor and Charmy

对Charmy、TeStor插件和案例的Charmy模型的更多描述请参阅[4]。

5.一些初步的想法
如第二部分所言，迄今已有许多以UML为标识的基于模型的测试法。但是，TeStor却与它们有很大的不同，理由如下：i) TeStor不需要组件状态机的并联组合。当其他技术往往需要创建一个全局模型来呈现系统集成时，TeStor却可独立分析组件的运转状态。状态机的直线化进程能合并陆续产生的各路径以再生成输出序列图。因为输入序列图只涉及生成路径的一个子集，这种方法能有效减轻状态剧变问题；ii) TeStor不需要任何形成标识。它只需要状态机和序列图作输入数据。iii) TeStor能满足工业上一些重要而有争议的需求：低测试作用力和高测试准确度。尽量减少加强模型的使用，也就是说，不需要另外的信息和完整的模型。另一方面，为保证测试的准确度应从模型生成测试案例，模型应尽可能丰富。状态机和序列图的使用能实现这一目标。iiii) TeStor完全由工具支持。
从完整性、正确性和复杂性来看，本文对算法的陈述只能算一些初步的想法。日后会改进这种非正式的表述。
关于完整性，TeStor没有从SA运行模型中生成出所有可能的路径。事实上，因为测试序列生成法创建了循环路径，完整性就不能得到保证（将来也不会）。但是，TeStor算法保证至少保证输入序列图信息出现一次。
相反，谈到正确性，根据经验我能证实TeStor是正确的。（比如，这种算法生成的路径是状态机中的实路径）。为明确起见，直线化算法包含了状态机中的路径。测试序列生成算法先选取那些可抵达m的直线性路经，然后以状态机的同步方式为基础合并这些路径。最后，这种算法的合并功能保证生成的路径被纳入系统的运行中。
从所占时间和空间来看，这种算法在计算方面是复杂的。直线化算法需访问状态机图表的每一条弧，那样它就变得像弧的数量一样复杂。测试序列生成算法的复杂性取决于直线化算法生成的路径数量、输入序列图的大小和输入序列图的“不完整性”（比如，考虑到状态机，输入序列图在多大程度上是不完整的）。我们计划在日后正式讨论这种算法在计算和时间上的复杂性。

6.结论及日后的工作
TeStor是输入状态机和序列图，并以序列图形式生成测试序列的算法。这种算法以这样一种构想为基础——序列图常常是一种不完整的说明并描述重要的预期中的系统响应。这种不完整的说明可以从状态机中重获遗漏信息而得到完善。TeStor是作为Charmy分析结构的插件而实现的。
在以后的工作中，我们将综合在[9]基于模型的测试方法学中的TeStor测试案例选取法。我们将着手把集成工具支持的方法学应用于[20]中提到的西门子C.N.X系统，估测在西门子C.N.X下此法的有效性。此外，我们目前正在分析如何把TeStor生成测试序列转换成可执行测试。
我们设想中的另一有趣综合是把TeStor输出数据用作Use Interaction Test (UIT) 方法[6]的输入数据。通过分类法 [22], UIT以UML序列图为专用参考模型，系统地为集成测试阶段构建和规定了一组测试案例。我们相信我们能联合UIT努力简化的主要优点和一组更有效的推演测试案例。
我们设想中的其他改进是分析同时产生直线性路线和生成测试序列的可能性，并将以更深刻的形式阐述输入序列图。尤其，我们希望能抽取所有那些正确实现输入序列图的输出序列图，一如图4所示：输入序列图1（比如，任何包含m1、m3的路径，与m2不相容）和输入序列图2（比如，任何包含m1的路径紧接着是m2，最后是m3。）

Fig. 4. inSD1 and inSD2 in the UML 2 formalism

致谢
我们在此感谢大力支持这项研究并提供研究案例的西门子C.N.X，感谢Pierluigi Pierini、Antonia Bertolino 和 Eda Marchetti 为论文前期工作所作的贡献。我们也非常感谢许多不知名的审阅者对本文提出的修改意见。

参考文献：
1. AGEDIS Project. http://www.agedis.de/index.shtml.
2. Model-based Testing Home Page. based testing/.
Maintained by Harry Robinson.
3. UMLAUT Project. http://www.irisa.fr/UMLAUT/.
4. CHARMY Project. Charmy Web Site. http://www.di.univaq.it/charmy, 2004.
5. G. Antoniol, L. C. Briand, M. D. Penta, and Y. Labiche. A Case Study Using the Round-Trip Strategy for State-Based Class Testing. In Proc. IEEE ISSRE2002, 2002.
6. F. Basanieri, A. Bertolino, and E. Marchetti. The Cow Suite Approach to Planning and Deriving Test Suites in UML Project . In Fifth International Conference on the Unified Modeling Language - the Language and its applications(UML 2002), pages 383{397, Dresden, Germany, September 2002.
7. A. Bertolino, E. Marchetti, and H. Muccini. Introducing a Reasonably Complete and Coherent Approach for Model-based Testing. In In Testing and Analysis of Component-Based Systems Workshop, Tacos 2004. To be pubblished in Electronic Notes of Theoretical Computer Science, 2004.
8. L. Briand and Y. Labiche. A UML-Based Approach to System Testing. Journal of Software and System Modelling (SoSyM), 1(1):10{42, 2002.
9. A. Bucchiarone, H. Muccini, P. Pelliccione, and P. Pierini. Model-Checking plus Testing: from Software Architecture Analysis to Code Testing. In Proc. Interna-tional Testing Methodology workshop, Lecture Notes in Computer Science, LNCS, vol. 3236, pp. 351 - 365 (2004), October 2004.
10. I. Crnkovic and M. Larsson, editors. Building Reliable Component-based Software Systems. Artech House, July 2002.
11. F. Fraikin and T. Leonhardt. Seditec - testing based on sequence diagrams. In Proc. IEEE CASE 02, Edingburgh, September 2002.
12. P. Graubmann and E. Rudolph. HyperMSCs and Sequence Diagrams for use case modeling and testing. In Proc. UML 2000, volume LNCS Vol.1939, pages 32-46,2000.
13. D. Harel and R. Marelly. Specifying and Executing Behavioural Requirements: The Play In/Play-Out Approach. Journal of Software and System Modelling (SoSyM), 2003.
14. A. Hartman. Model Based Test Generation Tools. Technical report, AGEDIS project Downloads, 2002.
15. J. Hartmann, C. Imoberdof, and M. Meisenger. UML-Based Integration Testing. In ACM Proc. ISSTA 2000, Portland, 2000.
16. C. Jard and T. J¶eron. TGV: Theory, Principles and Algorithms. In Conf. IDPT 2002, Pasadena (USA), 2002.
17. G. Kim, H. S. Hong, D. H. Bae, and S. Cha. Test Cases Generation from UML State Diagram. IEEE Proceedings - Software, 146(4):187{192, August 1999.
18. L. Liuying and Q. Zhichang. Test Selection from UML Statecharts. In Proc. of 31st Int. Conf. on Technology of Object-Oriented Language and System, China, 22-25 September 1999.
19. E. Marchetti. Software Testing in the XXI Century: Methods, Tools and New Approaches to Manage, Control and Evaluate This Critical Phase. PhD thesis, University of Pisa, September 2003.
20. H. Muccini, P. Pelliccione, A. Bucchiarone, and P. Pierini. Software Architecture-driven System Testing through Model-Checking. Technical Report TRCS 035/2004, University of L'Aquila, 2004.
21. J. O®utt and A. Abdurazik. Generating Test from UML Speci¯cations. In Proc. UML 99, Fort Collins, CO, October 1999.
22. T. J. Ostrand and M. J. Balcer. The category-partition method for specifying and generating functional tests. Communications of the ACM, 31(6):676{686, June 1988.
23. P. Pelliccione, H. Muccini, A. Bucchiarone, and F. Facchini. Deriving Test Sequences from Model-based Speci¯cations. Technical Report TRCS 002/2005, University of L'Aquila, 2005.
24. J. Ryser and M. Glinz. Using Dependency Charts to ImproveScenario-Based Testing, 2000.
25. J. Wittevrongel and F. Maurer. Using UML to Partially Automate Generation of Scenario-Based Test Drivers. In Springer, editor, OOIS 2001, 2001.

附录A：测试序列生成
此附录中我们以伪编码的形式，更完整地陈述测试序列生成算法。这种算法运用了一下方法：
——TracesSet extractTraces(SMId sm, Message m)：抽取所有包含信息m的路径。
——SMId senderSM(Message m)：返回发送信息m的状态机的ID。
——SMId receiverSM(Message m)：返回接收信息m的状态机的ID。
——SDSet merge(SDSet sdSenderSet,SDSet sdReceiverSet)：合并两组序列图。这两组图呈现一系列效应以满足发送和接收状态机再生成输入序列图运行的要求。这种算法试图为第一组和第二组中的每一个元素构建一个能让系统运行的序列。如果无法获得正常的运行，这种算法不会在输出设备中引进任何序列。如果结果集空闲，就不能从两组输入装置开始获得一种正常的运行状态。
——msgSet messages(Trace t)：返回纳入输入路径的信息集。
——State startState(Trace t, Message m)：返回路径中信息的起始状态。
——Int size(Set s)：返回S集的大小。
这种算法先开始识别那些可能发送/接收m的组件，然后选取包含信息m的直线化路径（lines2-11）。路径的选取由抽取路径法执行。
测试序列生成的伪程序（Test Sequence Generation Pseudo-Code）

算法的下一部分包含相等的两方面：一是发送组件状态机（lines13-40），一是接收组件状态机（lines41-68)。发送组件是指能发送信息m的组件。相应地，接收组件是指能接收信息m的组件。两者中的任何一个都能构建路径集，这些路径集能指示系统怎样运转以实现信息m的交换。仅以发送组件而言，我们注意到测试序列生成算法运用了生效法（line15）。这种方法将在下文详述，它能敏锐识别允许系统交换信息m的每一条路经。
对每一条识别的路径和引进的新信息，一个测试序列生成的循环呼叫会被执行（line23）。
测试序列生成由集smSet和trSet调用，它们分别随着当前状态机sm和当前路径t的加入而增长。事实上，递归调用的目的在于用SM所需的细节填充构建中的序列，已考虑过的除外。每一个嵌套调用中，另一个SM及相关路径会被添加。
程序的余下部分，lines13-34，呈现了序列设置的构建，序列设置串联了递归调用的结果。

算法的最后一部分是，通过合并发送和接收状态机所需的序列图集，构建序列图的输出数据。