一种基于行为模型的软件安全性测试用例生成方法

摘要

本发明公开了一种基于行为模型的软件安全性测试用例生成方法，包括如下步骤：(1)确定软件安全性测试需求；(2)使用测试需求行为模型对安全性测试需求进行描述；(3)使用UML状态图对测试需求行为模型进行描述；(4)将UML图状态图转换为FSM；(5)基于FSM特征序列自动生成安全性测试用例。本发明提出的基于行为模型的软件安全性的测试用例生成方法，重点从SSD行为预防机制、SSD行为检测机制和SSD行为响应机制展开安全性测试，克服了传统软件安全性测试的片面性和需求不完整，保证了测试的有效性。同时，发明提供了测试用例的自动生成方法，减少了测试人员的工作量，提高了测试的效率和自动化程度，保证了测试效果。

说明书

技术领域

本发明涉及软件测试方法，尤其涉及一种基于行为模型的软件安全性测试用例生成方法。

背景技术

近年来，软件安全性事件层出不穷，造成的危害也越来越大。人们往往把主要精力集中在网络安全技术和信息系统安全框架上，但最新研究表明近年引发严重安全危机的绝大多数都是软件安全问题，其根本原因在于软件存在安全性缺陷。统计表明，最常见的10种软件安全性缺陷造成了75％的安全漏洞。

软件测试作为保证软件质量的重要途径，对提高软件安全性具有重要意义，其中关键在于安全性测试方法的实用性和有效性。传统的软件安全性测试源自功能测试技术，以软件安全性功能需求为依据确定测试需求，采用功能测试中等价类划分，边界分析等方法进行规格功能点的验证。然而，在实际应用中，一方面，用户通常难以完全表达安全性需求，软件需求文档中的安全性需求表达往往达不到测试所需的详细程度；另一方面，用户更关心软件不应该出现何种危险行为，但需求文档中往往缺乏否定场景的描述，或者对恶意数据输入域没有实现全覆盖。因此软件安全性测试行为实际上可以分为两种：正向测试行为和反向测试行为。正向测试行为即传统使用的源自软件安全性功能需求的测试，包括对数据机密性、完整性、可用性、不可否认性、身份认证、授权、访问控制、审计跟踪、委托、隐私保护、安全管理等安全需求的验证；反向测试需求行为即从外部攻击者角度模拟攻击者利用安全性缺陷进行攻击的测试行为，主要检查软件抵御攻击的能力及受到攻击后的响应行为。由此可见，传统的软件安全性测试是不完全的，缺少对否认场景和恶意输入等行为的考虑，也缺乏对典型软件安全性缺陷的针对性测试。

在软件测试的所有开销中，约有40％的工作量花在测试用例上，包括生成测试用例和检查测试结果。人们提出了一些测试用例自动生成方法，但距离实用还有很大距离，这也是目前制约软件测试技术发展的主要因素之一。目前在测试行业内，大都采用人工方式或计算机辅助方式生成测试用例，这两种方法的缺点主要有：编写和生成测试用例需要花费大量的时间，测试效率低且缺乏规范性；对测试人员素质要求高，且要求测试人员非常熟悉待测软件；测试完全性和测试效果难以保证。

由于人工生成测试用例占据了大部分的时间，因此测试用例的自动生成一直是软件测试所追求的目标之一。这是一个极为复杂的问题，国内外大量研究人员为此付出了大量努力，但效果并不非常理想。就目前研究水平而言，完全取代人工编写的测试用例还不太现实；但其成功解决对提高软件质量，缩短开发时间都具有十分重要的理论意义和使用价值。

发明内容

发明目的：为了克服现有技术中存在的不足，本发明提供一种基于行为模型的软件安全性测试用例生成方法，借助测试需求行为模型来同时描述正向测试行为和反向测试行为，提高安全性测试的规范性、覆盖率和针对性；从行为模型出发自动生成测试用例，提高了软件测试的效率，降低了测试人员工作量。

技术方案：为实现上述目的，本发明采用的技术方案为：

(1)确定软件安全性测试行为需求。

(2)使用测试需求行为模型对安全性测试需求进行描述：测试需求行为模型通过对SSD行为预防机制、检测机制和响应机制的描述，包含了从测试角度分析的安全功能和外部攻击行为两方面内容，该步骤具体包括如下步骤：

(2-1)分析确定SSD(Software Security Defects，软件安全性缺陷)测试行为预防机制、测试行为检测机制和测试行为响应机制。

测试行为预防机制即测试行为前部分，主要描述软件系统在需要覆盖的SSD被激活之前所应该具有的状态和行为；测试行为检测机制即测试行为过程部分，要描述软件系统怎样对基于SSD的非法访问进行检测；测试行为响应机制即测试行为后部分，主要描述在正确的检测完SSD测试行为后软件系统应该具有的状态和行为，从而防止SSD测试行为再次被执行。

(2-2)对步骤(2-1)中的三种机制，分别描述三种机制的三个阶段行为，即前置条件、处理行为和后置条件；

测试行为预防机制中包括防止SSD测试行为的前置条件、防止SSD测试行为前软件系统可以进行的预防活动以及防止SSD测试行为的后置条件；测试行为检测机制中包括测试SSD测试行为过程的前置条件、测试SSD测试行为过程的检测场景、测试SSD测试行为过程的检测结果，即测试SSD测试行为过程的后置条件；测试行为响应机制中包括测试SSD测试行为后前置条件、测试SSD测试行为后响应场景、测试SSD测试行为后响应行为以及测试SSD测试行为后后置条件。

(3)使用UML(Unified Modeling Language，统一建模语言)状态图对测试需求行为模型进行描述，测试需求行为模型可以用图形化形式表示出来，以方便测试人员了解其结构和内部流程。但这种图形形式不是规范化的，不利于作为交流和自动生成测试用例的基础，因此需要使用UML图对其进行规范描述。由于测试需求行为模型图形和状态图较为类似，因此使用状态图对其进行描述。该步骤具体包括如下步骤：

(3-1)分别将测试需求行为模型中的行为预防机制、行为检测机制和行为响应机制的三个阶段行为映射为UML状态图中的三个顶层复合状态。

UML状态图中可以包含多个状态层次，在描述中使用顶层状态图的复合状态描述测试需求行为的三种机制，使用状态子图描述机制中的处理过程。

(3-2)依据典型安全性缺陷在每个阶段行为中的处理过程，将三个阶段分别映射为UML状态图中的行为预防状态子图、行为处理状态子图和行为响应状态子图。

在状态子图描述中，需要对行为机制的前置条件、处理行为和后置条件进行细化，使其分别对应一至几个子状态，再根据需求行为模型中的关系依次相连。

(3-3)如果需要，可以将步骤(3-2)中三个子图中的前置条件、处理过程和后置条件部分进一步细化为二级子图。

对于处理行为比较复杂的行为机制，可以将处理行为再次映射为一个复合状态，而其内部处理过程使用二级子状态图进行描述。

(4)将UML图状态图转换为FSM(Finite State Machine，有限状态机)，UML状态图提供了测试需求行为描述的规范性，但UML只是一种半形式化的语言，直接生成测试用例使用限制较多，因此将其转换为形式化的FSM。该步骤具体包括如下步骤：

(4-1)将UML状态图存储为XMI(XML Metadata Interchange，XML元数据交换)文本格式。

XMI使用XML(eXtensible Markup Language，扩展标记语言)提供元数据信息交换的标准方法，规范了如何从UML模型生成XML文档。现有不少UML建模工具都支持将UML模型直接存储为XML格式，如MagicDraw UML。

(4-2)依据公开的文本转换算法将XMI格式的状态图转换为SCXML(State ChartXML，状态图XML)格式，后者即FSM的文本表示。

SCXML是一种基于Harel状态表的状态变迁语言，提供了通用状态机的描述方法，可以用来表示FSM。文本转换算法可参见《计算机科学》杂志2009年7月刊文章《UML模型到FSM模型的转换》。也可以使用IBM公司的Modeling and Integration Tools forState Chart XML工具和Rational公司的Software Architect工具直接将UML状态图转换为SCXML格式。对SCXML文本进行解析即可得到FSM图形格式。

(5)基于FSM特征序列自动生成安全性测试用例，基于FSM的测试用例为测试序列，它是指一个输入/输出序列，比如：一个测试用例tc＝(i₁/o₁)(i₂/o₂)...(i_k/o_k)，tc表示测试用例，i表示输入，o表示输出。它反映了对系统执行一段输入序列后，应该得到的预期输出序列是什么。测试用例的长度指测试序列的长度，测试用例集，指一系列测试用例组成的集合，TC＝{tc₁，tc₂，...，tc_p}，TC表示测试用例集。该步骤具体包括如下步骤：

(5-1)对FSM进行预处理，所述预处理包括非完全FSM的完全化、非精简FSM的最小精简化和连通性说明。基于FSM的软件测试一般要求规约状态机是完全的，确定的，精简的和强连通的等。因此测试用例生成方法的应用是有前提条件的，比如：基于UIO(Unique Input/Output Sequence，唯一输入/输出序列)特征序列的测试用例生成方法要求规约有限状态机的每一个状态具有UIO序列，而要保证其条件必须使得有限状态机模型是最小的、完全的和强连通的。当构造的测试模型FSM不满足前提假设时，需对模型进行改进，使其满足。该步骤又具体分为如下步骤：

(5-1-1)为规约中没有出现的输入增加定义，达到FSM的完全化。

对于部分定义的状态机，软件规约中没有出现的输入，可以通过对输出函数和迁移函数增加定义，使得未定义状态不产生输出或指向新定义的错误状态来达到FSM的完全定义。

(5-1-2)去除FSM中的冗余状态，使用等价的精简FSM取代原FSM。

非精简FSM中至少存在两个等价的状态，它的存在严重限制了UIO特征序列的生成。通常情况下，两个等价的状态存在表明系统存在设计缺陷，一定可以通过等价转换得到一个精简并一致的FSM。如采用会议论文集《Proceedings of the 2002 Design，Automation and Test in Europe Conference and Exhibition》中文章《A Heuristic For StateReduction In Incompletely Specified Finite State Machines》的精简算法。

(5-1-3)对FSM中所有状态可达性和可复位性进行检查和说明。

通常情况下，规约描述的FSM都是连通的，软件实现FSM也可以认为是连通的，因为软件功能流程具有设计的连通性。而且，如果软件实现存在不可达的某状态，我们也不需要对其进行测试，因为这段功能实现处于“死”状态，程序永远不可能执行到功能对应的代码上去。因此可以在检查软件基础上认定FSM的状态之间都是可达的。如果FSM中所有状态是可达的，且是可复位的，那么该FSM是强连通的。

(5-2)构造FSM的UIO树，并基于UIO树为FSM中的每个状态s生成UIO特征序列，UIO树是指从精简FSM的初始向量出发，通过定义扰动函数产生的一系列新节点所组成的树，基于UIO树生成FSM的UIO序列是一种效率较高的UIO序列生成方法。该步骤又具体分为如下步骤：

(5-2-1)从FSM的初始向量出发，通过定义路径向量和扰动函数，产生新的结点，构造UIO树。

初始向量是由FSM的初始状态组成的路径向量。通过对其定义扰动函数，可以产生一系列新节点，生成对应UIO树，树的深度可以通过满足基本剪枝条件进行限制。每个状态的UIO序列是由树根到唯一单一向量节点的路径构成。

(5-2-2)遍历整个UIO树，对每一个单一向量叶结点，将从树根到该叶结点所形成的输入/输出序列连接为该单一向量初始向量对应状态的UIO序列。

遍历UIO树生成UIO序列的方法较多，如采用杂志《IEEE/ACM transations onnetworking》1997年第5期文章《Efficient Computation of Unique Input/Output Sequencesin Finite-State Machines》中的UIO序列生成方法。

(5-2-3)对每个状态，选取最短的一个UIO序列为其特征序列。

(5-3)基于UIO特征序列，对FSM的每一个状态迁移生成使用测试序列表示的测试用例。UIO特征序列将作为测试序列生成时的状态验证序列，生成的测试序列覆盖FSM的每一个状态迁移。该步骤又具体分为如下步骤：

(5-3-1)对FSM中的每个状态迁移(s_i，s_j；x/y)，使用Dijikstra算法找到s₀到s_i的最短路径，得到s₀到s_i最短输入/输出序列。

此处假设FSM是可复位的。如果此FSM不可复位，则可以利用FSM的自引导序列确定系统当前状态，然后再利用Dijikstra算法找到当前状态到迁移头状态的最短路径。

(5-3-2)依次连接s₀到s_j的输入/输出，得到每个状态迁移(s_i，s_j；x/y)的测试用例(reset/null).SP(s_i).(x/y).UIO(s_j)。

步骤(5-3)的描述中，s₀，s_i，s_j表示FSM的状态；(s_i，s_j；x/y)表示从状态s_i迁移到状态s_j，其中输入为x，输出为y；reset表示将FSM复位到初始状态；SP(s_i)表示初始状态到状态s_i的最短输入/输出序列。

有益效果：本发明提出的基于行为模型的软件安全性的测试用例生成方法，通过描述测试需求行为的方式，分析利用软件安全性缺陷进行攻击的行为，重点从SSD行为预防机制、SSD行为检测机制和SSD行为响应机制展开安全性测试，克服了传统软件安全性测试的片面性和需求不完整，保证了测试的有效性。同时，发明提供了测试用例的自动生成方法，大大减少了测试人员的工作量，提高了测试的效率和自动化程度，保证了测试效果。

附图说明

图1为本发明方法的流程示意图；

图2为本发明中测试需求行为模型的图形形式；

图3为本发明中测试需求行为模型的UML状态图描述顶层图；

图4为本发明中测试需求行为模型的UML状态图描述行为响应状态子图；

图5为本发明中步骤5的处理流程示意图；

图6为本发明中测试需求行为模型的FSM描述；

图7为本发明中FSM模型的完全UIO树。

具体实施方式

下面结合附图对本发明作更进一步的说明。

图1为本发明基于行为模型的软件安全性测试用例生成方法的实现流程示意图。该方法包括以下步骤：

(1)确定软件安全性测试行为需求；

(2)使用测试需求行为模型对安全性测试需求进行描述；

(3)使用UML状态图对测试需求行为模型进行描述；

(4)将UML图状态图转换为FSM；

(5)基于FSM特征序列自动生成安全性测试用例。

下面结合具体实例和附图对上述步骤作更进一步的说明。

步骤(1)确定软件安全性测试需求

软件安全性测试需求可以通过现有技术得到。例如，对某Web应用系统进行安全性测试，分析得到的其软件安全功能包括：

a1.该软件系统有用户身份验证功能，口令错误3次后账户会被锁死；

a2.该软件系统有用户鉴别和授权功能；

a3.该软件系统用户名使用范围可以进行IP绑定；

a4.该系统对所有交互信息进行加密；

a5.该系统有审计功能；

分析得到利用访问控制SSD的可能攻击行为包括：

b1.非法用户截获交换报文；

b2.非法用户获取合法用户名；

b3.非法用户获取合法用户名和口令，并试图访问软件系统；

步骤(2)使用测试需求行为模型对安全性测试需求进行描述

步骤(2)具体包括：

(2-1)分析确定SSD测试行为预防机制、测试行为检测机制和测试行为响应机制。

测试行为预防机制即测试行为前部分，主要描述软件系统在需要覆盖的SSD被激活之前所应该具有的状态和行为；测试行为检测机制即测试行为过程部分，要描述软件系统怎样对基于SSD的非法访问进行检测；测试行为响应机制即测试行为后部分，主要描述在正确地检测完SSD测试行为后软件系统应该具有的状态和行为，从而防止SSD测试行为再次被执行。

分析步骤1所述软件安全性需求，判断对访问控制类型SSD，覆盖SSD的路径为：非法用户盗取用户识别和授权的方式，从而伪装为合法用户。因此可以分析确定测试行为前、测试行为过程和测试行为后机制，如表2所示为访问控制缺陷测试行为机制：

表2

(2-2)对步骤(2-1)中的三种机制，分别描述三种机制的三个阶段行为，即前置条件、处理行为和后置条件；

测试行为预防机制中包括防止SSD测试行为的前置条件、防止SSD测试行为前软件系统可以进行的预防活动以及防止SSD测试行为的后置条件；测试行为检测机制中包括测试SSD测试行为过程的前置条件、测试SSD测试行为过程的检测场景、测试SSD测试行为过程的检测结果，即测试SSD测试行为过程的后置条件；测试行为响应机制中包括测试SSD测试行为后前置条件、测试SSD测试行为后响应场景、测试SSD测试行为后响应行为以及测试SSD测试行为后后置条件。

对步骤(2-1)中的机制进行完善扩充后，得到如表3所示为基于范围控制缺陷的测试需求行为模型。

表3

步骤(3)使用UML状态图对测试需求行为模型进行描述

测试需求行为模型可以用图形化形式表示出来，以方便测试人员了解其结构和内部流程。但这种图形形式不是规范化的，不利于作为交流和自动生成测试用例的基础，因此需要使用UML图对其进行规范描述。由于测试需求行为模型图形和状态图较为类似，因此使用状态图对其进行描述。

为便于使用UML状态图对测试需求行为模型进行描述，可以先将步骤2中得到的表格形式的测试需求行为模型转换为图形形式，如图2所示。注意此步骤不是必须的。

步骤(3)具体包括：

(3-1)分别将测试需求行为模型中的行为预防机制、行为检测机制和行为响应机制的三个阶段行为映射为UML状态图中的三个顶层复合状态；

UML状态图中可以包含多个状态层次，在描述中使用顶层状态图的复合状态描述测试需求行为的三种机制，使用状态子图描述机制中的处理过程。测试需求行为模型的状态图顶层图形如图3所示。

(3-2)依据典型安全性缺陷在每个阶段行为中的处理过程，将三个阶段分别映射为UML状态图中的行为预防状态子图、行为处理状态子图和行为响应状态子图；

在状态子图描述中，需要对行为机制的前置条件、处理行为和后置条件进行细化，使其分别对应一至几个子状态，再根据需求行为模型中的关系依次相连。以行为响应状态子图为例，如图4所示。

(3-3)如果需要，可以将步骤(3-2)中三个子图中的前置条件、处理过程和后置条件部分进一步细化为二级子图；

对于处理行为比较复杂的行为机制，可以将处理行为再次映射为一个复合状态，而其内部处理过程使用二级子状态图进行描述。

步骤(4)将UML图状态图转换为FSM

UML状态图提供了测试需求行为描述的规范性，但UML只是一种半形式化的语言，直接生成测试用例使用限制较多，因此将其转换为形式化的FSM。

步骤(4)具体包括：

(4-1)将UML状态图存储为XMI(XML元数据交换)文本格式；

XMI使用XML提供元数据信息交换的标准方法，规范了如何从UML模型生成XML文档。现有不少UML建模工具都支持将UML模型直接存储为XML格式，如MagicDraw UML。

(4-2)依据公开的文本转换算法将XMI格式的状态图转换为SCXML(状态图XML)格式，后者即FSM的文本表示；

SCXML是一种基于Harel状态表的状态变迁语言，提供了通用状态机的描述方法，可以用来表示FSM。其元素对应关系如表4所示。

表4

  FSM  SCXML  状态集  <State>  转换  <Transition>  初始状态  <Initial>  目标状态  <Target>  ……  ……

步骤(5)基于FSM特征序列自动生成安全性测试用例；

一个确定性FSM可以定义为一个七元组M＝(S，X，Y，δ，λ，D，s₀)，其中：S＝(s₀，s₁，...，s_n)，s₀表示系统初始状态(initial state)；X是有限字符输入集合；Y是有限字符输出集合；δ：D →S是状态迁移函数，λ：D →Y是输出函数；D是M的属性，$D\subseteq S\times X.$

基于FSM的测试用例为测试序列，它是指一个输入/输出序列，比如：一个测试用例tc＝(i₁/i₁)(i₂/o₂)...(i_k/o_k)，tc表示测试用例，i表示输入，o表示输出。它反应了对系统执行一段输入序列后，应该得到的预期输出序列是什么。测试用例的长度指测试序列的长度，测试用例集，指一系列测试用例组成的集合，TC＝{tc₁，tc₂，...，tc_p}，TC表示测试用例集。

本发明中测试用例(测试序列)/测试用例集采用基于FSM的UIO特征序列的方法生成。UIO特征序列是指对一个FSM，状态s在输入p₁下其输出是p₂，而任意其他状态在p₁的输入下输出都不是p₂，则称p₁/p₂为状态s的UIO序列，记作UIO(s)＝p₁/p₂。UIO序列可以是一组连续的输入/输出，用于唯一识别一个状态。

步骤(5)的处理流程如图5所示，具体包括：

(5-1)对FSM进行预处理，所述预处理包括非完全FSM的完全化、非精简FSM的最小精简化和连通性说明；

基于FSM的软件测试一般要求规约状态机是完全的，确定的，精简的和强连通的等。因此测试用例生成方法的应用是有前提条件的，比如：基于UIO特征序列的测试用例生成方法要求规约有限状态机的每一个状态具有UIO序列，而要保证其条件必须使得有限状态机模型是最小的、完全的和强连通的。当构造的测试模型FSM不满足前提假设时，需对模型进行改进，使其满足。

(5-1-1)为规约中没有出现的输入增加定义，达到FSM的完全化；

对于部分定义的状态机，软件规约中没有出现的输入，可以通过对输出函数和迁移函数增加定义，使得未定义状态不产生输出或指向新定义的错误状态来达到FSM的完全定义。

例如，假设s是一个非完全定义的状态，x是未定义的输入符号，增加定义为δ(s，x)＝s或者指向一个错误状态，λ(s，x)＝null。

(5-1-2)去除FSM中的冗余状态，使用等价的精简FSM取代原FSM；

非精简FSM中至少存在两个等价的状态，它的存在严重限制了UIO特征序列的生成。通常情况下，两个等价的状态存在表明系统存在设计缺陷，一定可以通过等价转换得到一个精简并一致的FSM。

(5-1-3)对FSM中所有状态可达性和可复位性进行检查和说明；

通常情况下，规约描述的FSM都是连通的，软件实现FSM也可以认为是连通的，因为软件功能流程具有设计的连通性。而且，如果软件实现存在不可达的某状态，我们也不需要对其进行测试，因为这段功能实现处于“死”状态，程序永远不可能执行到功能对应的代码上去。因此可以在检查软件基础上认定FSM的状态之间都是可达的。如果FSM中所有状态是可达的，且是可复位的，那么该FSM是强连通的。

(5-2)构造FSM的UIO树，并基于UIO树为FSM中的每个状态s生成UIO特征序列；

UIO树是指从精简FSM的初始向量出发，通过定义扰动函数产生的一系列新节点所组成的树，基于UIO树生成FSM的UIO序列是一种效率较高的UIO序列生成方法。

(5-2-1)从FSM的初始向量出发，通过定义路径向量和扰动函数，产生新的结点，构造UIO树；

初始向量是由FSM的初始状态组成的路径向量。通过对其定义扰动函数，可以产生一系列新节点，生成对应UIO树，树的深度可以通过满足基本剪枝条件进行限制。每个状态的UIO序列是由树根到唯一单一向量节点的路径构成。

路径向量是由状态对组成的集合，PV＝{v₁/v′₁，v₂/v′₂，...v_k/v′_k}，初始向量为IV(PV)＝{v₁，v₂，...，v_k)}；当前向量为CV(PV)＝{v′₁，v′₂，...，v′_k}。如果|PV|＝1，那么该向量为单一向量；如果路径向量的当前向量势为1，那么该路径向量为同种类向量。

扰动函数的输入域和输出域都为路径向量，定义为：Pert(PV，a/b)＝PV′＝{v_i/v″_i|v″_i＝δ(v′_i，a)∧λ(v′_i，a)＝b∧v_i/v′_i∈PV}。

例如，对图6所示的有限状态机M，其生成的完全UIO树如图7所示。

(5-2-2)遍历整个UIO树，对每一个单一向量叶结点，将从树根到该叶结点所形成的输入/输出序列连接为该单一向量初始向量对应状态的UIO序列；

根据图7所示的UIO树，可以得到各个状态的UIO特征序列如下：

●状态A：

UIO(A)＝(0/1)(0/0)(0/0)；UIO(A)＝(0/0)(1/0)(1/0)(0/0)；

●状态B：

UIO(B)＝(0/1)(1/0)(0/1)；UIO(B)＝(0/0)(1/0)(1/0)(0/1)；

UIO(B)＝(1/0)(0/0)(1/0)(0/1)；UIO(B)＝(1/0)(1/0)(0/0)(1/0)(0/1)；

UIO(B)＝(1/0)(1/0)(0/0)(1/0)(1/0)(0/1)；UIO(B)＝(1/0)(0/0)(1/0)(1/0)(0/1)；

●状态C：

UIO(C)＝(1/0)(0/0)(1/0)(0/0)；UIO(C)＝(1/0)(0/0)(1/0)(1/0)(0/0)；

●状态D：

UIO(D)＝(1/0)(1/0)(0/0)(1/0)(0/0)；UIO(D)＝(1/0)(1/0)(0/0)(1/0)(1/0)(0/0)；

(5-2-3)对每个状态，选取最短的一个UIO序列为其特征序列；

步骤(5-2-2)中得到的各个状态的UIO序列中，最终选取如下最短UIO序列：UIOmin(A)＝(0/1)(0/0)(0/0)；UIOmin(B)＝(0/1)(1/0)(0/1)；UIOmin(C)＝(1/0)(0/0)(1/0)(0/0)；UIOmin(D)＝(1/0)(1/0)(0/0)(1/0)(0/0)。

(5-3)基于UIO特征序列，对FSM的每一个状态迁移生成使用测试序列表示的测试用例。

UIO特征序列将作为测试序列生成时的状态验证序列，生成的测试序列覆盖FSM的每一个状态迁移。

(5-3-1)对FSM中的每个状态迁移(s_i，s_j；x/y)，使用Dijikstra算法找到s₀到s_i的最短路径，得到s₀到s_i最短输入/输出序列。

此处假设FSM是可复位的。如果此FSM不可复位，则可以利用FSM的自引导序列确定系统当前状态，然后再利用Dijikstra算法找到当前状态到迁移的初始状态的最短路径。

(5-3-2)依次连接s₀到s_j的输入/输出，得到每个状态迁移(s_i，s_j；x/y)的测试用例(reset/null).SP(s_i).(x/y).UIO(s_j)。

步骤(5-3)的描述中，s₀，s_i，s_j表示FSM的状态；(s_i，s_j；x/y)表示从状态s_i迁移到状态s_j，其中输入为x，输出为y；reset表示将FSM复位到初始状态(s₀表示初始状态)；SP(s_i)表示初始状态到状态s_i的最短输入/输出序列。

步骤(5-3)可以使用如下算法实现。

                                                                   

算法：UCgenerator

输入：最小、强连通、完全定义的有限状态机M＝(S，X，Y，λ，δ，s₀)

输出：测试序列集

begin

Step1；for M中的每个状态s_i

生成s_i的UIO序列，

Step2：

(1)reset(M)；

(2)for M中的每个迁移

2.1使用Dijikstra算法找到s₀到s_i的最短路径

2.2输入x使M从状态s_i迁移到状态sX

2.3输入s_j的UIO特征序列；

end；

根据步骤(5-2)得到的UIO特征序列，最终得到图6所示的有限状态机M的测试用例如表5所示为有限状态机M各个迁移的测试用例。

表5

以上所述仅是本发明的优选实施方式，应当指出：对于本技术领域的普通技术人员来说，在不脱离本发明原理的前提下，还可以做出若干改进和润饰，这些改进和润饰也应视为本发明的保护范围。