3．1 进行以下判断：

　　1.3.1若当前处理完的为第一个分支，则插入一个新的状态，并使最后一个节点指向这个新插入的节点

　　2.3.1若不是第一个分支，则使最后一个节点指向第一个分支的最后一个节点

　　4.1将当前节点置为算法开始时传入的节点，即分支的父节点，进行判断：

　　1.4.1当前父节点是否有超过1个的子分支，若有则进行判断：若超过一个子分支的下一个节点都是第一个分支的最后一个节点，则将这些子分支合并成一个子分支，即由父状态指向第一个分支的最后一个节点，概率为各个子分支的和

　　2．若还有其他分支，则进入其他分支，并设置当前分支为算法开始时传入的父节点，重复步骤1

　　经以上算法作用后，运行剖面可以表示为｛OPi｜OPi=＜Oi,Pi＞，i=1,2,…，N｝，其中Oi表示组成这个运行剖面的其中一个运行，Pi表示这个运行发生的概率。

　　每一个运行经算法作用后，都表示为一Markov链，根据算法，可以看出，该Markov链之包含了运行中的带有输入的节点以及其中的一些关键节点，该Markov链综合了每个运行的运行图以及其状态细化图，以下的程序处理都基于此Markov链。

　　3．测试用例自动生成

　　测试用例是根据运行剖面随机生成的。在运行剖面中已经规定了每个输入变量的取值类型以及取值范围，并且认为变量在取值范围内均匀分布或分段均匀分布（由于很难确定变量的具体分布，这里假设为均匀分布）。软件可靠性测试是一种随机测试，测试用例的选取方式是随机选取。因此，根据随机测试的原则，在运行剖面给定的输入变量的取值区间内任意抽取一个变量的实际取值。将各个变量按顺序组合起来便生成了测试用例。用于软件可靠性测试的测试用例可以定义为：根据运行剖面生成的、完成对某一功能进行测试的、按顺序输入到被测软件的一系列输入变量的有序组合。

　　嵌入式系统中，输入可能为硬件信号或者人机接口，这就需要在标示测试输入类型时进行特殊标记，这里，可采用两种方法，一是软件模拟硬件信号，即当需要硬件信号时，由软件模拟此硬件信号，来保证测试的执行。二是对需要的硬件信号进行标示，当需要硬件信号时，系统会提示需要某个硬件信号的触发。

　　根据运行剖面生成测试用例的过程为：运行剖面由一系列变量的取值区间和该运行发生的概率组成。

　　首先，要随机抽取一个运行来实现对某一功能的一次测试。抽取运行的过程如下：

　　① 将运行剖面｛OPi｜OPi=＜Oi,Pi＞，i=1,2,…，N｝中所有运行发生的概率Pi求前j项和，形成一个数列｛Sj｝，Sj=∑Pi，其中，i=1,…j，j=1,2,…，N；N为软件运行剖面中运行总数，规定S0=0,并有S1=P1,Sn=1.0,Sj-Sj-1=Pj。这里运行相互独立。

　　② 任给一个随机数η∈(0,1.0)，观察η落在哪个区间，若η满足Sj-1＜η≤Sj，则该随机数η与Pj这个概率值对应，那么这次随机抽到的运行为Oj。

　　③ 确定了抽到的运行为Oi后，就可以确定该运行的输入情况，假设该运行有m个输入，每个输入的可选值分别为I1,I2…Im，将其排列为一个二进制串，若 I1有m1个可选输入，I2有m2个可选输入Im有mm个可选输入，则二进制串为(00…0) (00…0)……(00…0)，其中，第一个括号内的0有m1个，第二个括号中的0有m2个，第m个括号中的0有mm个，构造一个布尔类型的数组，数组的大小为2(I1+I2+…+Im)，数组的初始值均为false，每次产生一个测试用例时，从m个输入的I1,I2…Im中每一个输入的可选值中各选一个，并把二进制串中的相应位置1，m个输入都选好后，把对应的标记数组置为true。生成一个测试用例后，首先判断对应的标记数组，若为true，则需要重新生成一个用例。

　　④ 其中，要进行第二次抽样来确定运行中每个输入的取值区间将取到的实体（即具体取值）。实体的确定将按照输入变量的属性分两种情况进行：

　　a. 对于连续型输入变量，运行剖面给出的是该变量的取值区间的上下限［I.down,I.up］。抽样时将根据输入变量的数据类型，在区间［I.down,I.up］内随机抽取一个满足输入变量数据类型的具体值，作为该输入变量的实体。

　　b. 对于可选离散型输入变量，运行剖面给出的是一组离散点Ii,i=1,2,…,mi;mi为离散点的个数。抽样时将在［1,mi］内随机抽取一个整数j，以确定选哪一个离散点作为该输入变量的实体，并将该实体转化为该输入变量的数据类型。

　　c. 通过对运行和各个实体两个步骤的抽样，完成一个测试用例的生成。

　　应用测试用例可以进行软件可靠性测试。

　　系统负责根据以上算法策略等产生测试用例，输入到整个测试系统中，执行可靠性测试，测试系统根据某种判断策略，来决定此用例是否通过测试，若在规定的时间内，规定的输入条件下，所有用例均通过测试，则测试完成，若其中有测试用例没有通过测试，只需要对被测软件进行修改，消除其中的错误，再次进行测试，而整个测试系统不需要任何改动，大大的提高了测试的效率和灵活性。这种测试是统计测试，测试完全根据各个运行所发生的概率以及运行的权重来进行的，在测试中, 优先测试那些最重要或最频繁使用的功能，释放和缓解最高级别的风险，有助于尽早发现那些对可靠性有最大影响的故障。

　　4．结束语

　　本文完全从工程应用的角度出发，根据被测软件的需求规格说明书，通过和软件使用人员充分的交流，由测试人员构造出软件的运行剖面，并用文中定义的运行图来描述，经过算法转化为带标记的 Markov链描述，依据该Markov链，可以自动生成测试用例。配合相应的测试环境，进行自动化的可靠性测试，可以极大的提高测试的效率，被测嵌入式系统的可靠性也可以进行更加充分的验证。

　　今后的工作主要是输入模型的提取与识别以及重组，从本文的前面，可以看出，系统的输入还是比较繁琐的，如果能够直接读取被测软件的UML图，从图中提取各种信息，从而自动构造软件的运行剖面，则可以使整个过程更加高效，符合软件测试的发展趋势。此外，支撑测试环境的搭建，也需要认真的研究。

　　本文作者创新点：

　　1．传统的软件测试都是根据软件的源代码进行测试，本文则根据软件的需求规格说明书进行测试，大大提高了测试的效率和灵活性。

　　2．用带标记的Markov链对软件运行剖面建模，为自动产生测试用例打下了基础。

　　3．能对产生的测试用例情况进行标记，避免产生相同的测试用例，提高了测试的效率。