下载掌阅APP，畅读海量书库
立即打开
1.基于扩展UIO序列的测试方法
基于FSM的测试序列生成方法中最常用的是UIO方法，绝大多数状态机都存在UIO序列，UIO序列是D序列或W序列的子集，其长度比D方法和W方法获得的序列长度短。由于未考虑状态迁移的前置条件，直接将UIO方法用于EFSM模型会产生测试序列的不可执行问题。
Chun W.、Amer P.D.等最早将UIO序列引入EFSM模型，不过没有给出可执行UIO序列的定义和生成方法。例如，某团队提出的基于EFSM测试序列的生成方法中使用了上下文无关唯一序列（Context Independent Unique Sequence，CIUS），该方法只在测试序列生成时考虑测试序列的可执行性，CIUS用作状态鉴别序列。事实上CIUS也是一种UIO序列，不过，并非每个EFSM都有CIUS，该方法的适用范围因此受到限制。
Ramalingam T.、Thulasiraman K.等提出了一种基于转换可执行性分析的方法，称为UIO E （Executable Unique Input Output）。利用转换可执行性分析（Transition Executability Analysis，TEA），以状态配置为节点，以可执行转换为弧，采用广度优先的策略，扩展生成一棵TEA树，并由此生成一个可执行的转换测试序列。这种方法解决了转换的可执行性问题，并利用转换子序列间未转换的重叠来尽量缩短测试序列。UIO E 方法首先将EFSM转换为规范化EFSM，然后配置初始状态，并选择一个以当前状态作为起始的可执行待测转换，对其进行TEA扩展，得到对应的UIO E 序列。所谓进行TEA扩展，就是通过对EFSM的转换可执行性分析，生成一棵TEA树。接着按照“EFSM中的每个转换都被测试一次”的原则，依次对其他待测转换进行TEA扩展并产生相应的UIO E 序列，直到所有的转换都被测试过。连接所有的测试事件，形成最终的测试序列。如果一个EFSM是转换强连通的且无陷阱，那么通过UIO E 方法总是能够得到可执行测试序列。
UIO E 方法的局限性在于对EFSM进行了简化，模型中仅存在环境变量（即某些内部变量），这些变量的初始值都是常数，因此可以用符号执行的方法进行可执行性分析，而没有考虑各状态迁移中存在的输入变量。
2.将EFSM转化为相应的FSM
为了更好地利用已有的基于FSM的测试方法，有研究者试图将EFSM转化为与之等价的FSM，然后利用现有的FSM测试序列生成方法产生可执行的测试序列。但是这种转化并不简单。首先，状态迁移的行为与变量相互关联；其次，状态迁移之间通过迁移上的操作以及变量产生交互作用。这种方法容易导致“状态爆炸”。
Duale A.Y.、Uyar M.U.等给出了一种规定了某些限制条件的EFSM自动生成可执行测试序列的方法，指出基于EFSM自动生成测试序列的困难源于EFSM模型含有不可达路径。引起不可达路径是由于所谓的上下文变量的存在，变量之间的相互依赖产生了行为冲突和条件冲突，使某些路径不可达。
当EFSM模型的所有冲突都被消除后，就可直接利用现有的基于FSM的自动测试生成方法。该方法只生成可达路径。但是该方法对EFSM模型做了一定的限制，比如规定规范由单个进程构成且不存在指针、递归函数和无限循环，以及所有的条件和行为都是线性的等，这些规定同样限制了该方法的使用范围。
3.基于标准生成EFSM测试序列
EFSM的数据流测试通常基于有向数据流图，在实际测试中，通常选择一个包含了EFSM数据流特征的标准，标准定义了需遍历的路径，这些路径只是图中所有可能的路径的一个子集。EFSM数据流测试覆盖标准的选择是一个权衡过程：所选的标准越强，对IUT（被测实现）的检查就越透彻；所选的标准越弱，则所需的测试用例数量越少，测试代价相对较小。
EFSM数据流测试的目的是发现和测试EFSM的状态迁移之间的数据依赖关系，通常是通过检查变量定义和使用之间的关联关系来完成的。Ural H.定义了数据流覆盖标准All-use和IO-df-chain。All-use标准要求从变量的定义到使用跟踪每个变量关联，并要求在对变量的跟踪过程中，该变量不能被重新定义。假设在结点J变量X被定义，在结点K变量X被使用，为了跟踪变量在定义和使用之间的关联，构造define-clear-use路径，该路径是连接从结点J到结点K的路径且结点J是路径中唯一的定义变量X的结点。如果这样的define-clear-use路径存在，那么变量X和结点J、K构成的关联称为define-use pair，又叫du-pair，表示为du(X,J,K)。一个测试序列如果能够覆盖每个变量的define-clear-use路径或du-pair至少一次，则它是满足All-use标准的。IO-df-chain标准的定义和All-use标准类似，不同的是IO-df-chain标准跟踪的是每个输出与影响该输出的所有输入之间的关联。
EFSM的控制部分涉及状态的转换。在实际基于EFSM的控制流测试中，通常要求测试序列覆盖EFSM中的每个状态转换至少一次。Chen W.H.等将覆盖标准作为测试序列的产生依据，该方法将EFSM转换为一个有向数据流图，在流图上标出变量的定义和使用，定义和选定数据流测试覆盖标准，选择测试序列和测试数据来满足该标准。在此基础上扩展测试用例，使之满足控制流测试覆盖标准。
4.基于流分析生成EFSM测试序列
结合FSM和EFSM的优势，控制流部分利用FSM测试序列生成方法，数据流部分借助EFSM数据流测试方法，也是一类兼顾数据流和控制流全面测试的EFSM测试序列生成方法。
Sarikaya、Bochmann G.等将功能程序测试方法应用于EFSM的数据流测试。该方法使用数据流图（Data Flow Graph，DFG）模拟ESTELLE规范中的信息流，使用分解和功能划分的方法得到规范的数据流功能模块，然后对这些模块进行测试。该方法未考虑测试序列的可执行性问题，得到的测试序列有可能不可执行。Miller R.、Paul S.首先将EFSM转换为一个等价的修改了输入和输出的FSM，转换没有改变状态的数目，但增加了状态迁移的数目。然后由该FSM构建一个数据流图，结合FSM的控制流图（Control Flow Graph，CFG）生成同时测试控制流和数据流并覆盖所有定义-观测路径的测试序列。该方法生成的测试序列是可执行的，但是其关于IUT的假定——例如IUT中使用的变量是可以由测试者访问的——在很多情况下是无法满足的。Chanson S.T.、Zhu Jin song提出了结合控制流和数据流分析技术产生EFSM测试序列的UTS（Unified Test Sequence）方法。该方法涉及四个算法：
·算法1对EFSM模型的控制部分基于FSM产生测试子序列，该子序列与特征序列具有相同的故障检测能力。
·算法2利用数据流分析技术分析EFSM模型的数据部分，得到EFSM状态转换之间的依赖关系，表示为转换依赖图（Transition Dependence Graph，TDG），给出了转换之间的控制和数据依赖，以及所有变量的du-pair和def-clear路径，并通过合并相连的路径，产生一条经过数据流和包含所有I/O依赖的路径。
·算法3合并前两个算法产生覆盖全部du-path和全部转换的子序列。
·算法4对子序列进行可执行性检验并得到最终的EFSM测试序列，可执行性检验是通过CSP（Constraint Satisfaction Problem）方法和转换回路分析完成的。该方法对EFSM做了一些简化，对测试序列可执行性的检验是在测试序列生成后进行的。
Huang C.M.等提出了一种基于EFSM模型的可执行数据流和控制流的测试序列生成方法。在数据流部分，探测和测试含有变量定义使用以及输出使用的迁移路径。一个可执行测试序列包含三部分：①可执行交换序列（Executable Switching Sequence，ECSS）；②可执行DO路径（EDO-path）或可执行控制路径（EC-path），EDO和EC由以ECSS尾状态为根结点的TEA树扩展获得；③可执行回退路径（EBP-path），EBP由以EDO序列尾状态为根结点的TEA树扩展获得。其中，DO路径定义为定义-输出路径（Definition-Output Path），ECSS为测试前缀，EBP为测试后缀。在该方法中，所有的测试序列都是可执行的，但该方法是基于EFSM分析可达性的，故存在状态爆炸问题。此外，该方法为获得可执行测试序列，必须先初始化输入参数，这使得产生的测试序列会因为输入参数值的不同而不同。