（计算机软件与理论专业论文）基于状态图与z的测试用例生成研究.pdf

重庆大学硕士学位论文中文摘耍 摘要 软件测试是当今计算机科学与工程中起着至关重要作用的领域之一。近年 来，面向对象技术的广泛应用和c a s e 工具的发展，已经大大减轻了软件设计和 编码的困难，而使得软件测试变得越来越重要。随着软件测试理论和技术的不断 发展，它已成为软件工程领域内保证软件质量的必不可少的关键过程。 本文主要针对基于状态图和z 的测试用例生成方法进行了研究。文中首先 详细介绍了四种基于有限状态机的测试用例生成方法，对于扩展有限状态机的测 试，本文提出了一种将扩展有限状态机转换为等价的测试场景的方法，转换后的 测试场景与原扩展有限状态机是测试等价的，并且消除了原扩展有限状态机中由 于前置条件的存在而导致的不确定性。对于转换后的扩展有限状态机，可以应用 基于有限状态机的四种测试方法。对于大型系统的测试中存在的组合状态空间爆 炸问题和测试序列同步问题，本文提出的多测试驱动模型m t m 在不生成积自动 机的情况下生成测试序列，有效地缓解了组合状态空间爆炸问题。同时文巾提出 的同步算法和同步有向图的生成方法，解决了测试序列的同步问题。 基于完全形式化语言的测试也是近年来研究的重点，不少学者提出了基于z 等形式化语言的测试方法。本文探讨了基于z 的测试用例自动生成方法，讨论 了z 与状态图结合测试的好处和可行性，并提出了从状态图到z 的模式的自动 转化的方法，为状态图与z 结合测试的自动实现打下了基础。 最后，在本文研究的方法的基础上，给出了一个基于文中方法的测试工具的 模型，并提出了一些测试工作改进方法的设想。同时给出了基于z 的形式的测 试准则的描述，这更有助于支持形式化的测试方法和对该方法的度量与评估。 关键词：软件测试，有限状态机，扩展有限状态机，状态图，z 语言 重庆大学硕士学位论文 英文摘要 a b s t r a c t s o f t w a r et e s t i n gi soneo ft h em o s ti m p o r t a n ti s s u e si nc o m p u t e rs c i e n c ea n d e n g i n e e r i n g n o w a d a y s ，w i t ht h ew i d e l yu s e do b j e c to r i e n t e dt e c h n o l o g ya n df a s t d e v e l o p m e n to fc a s et o o l s ，s o f t w a r ed e s i g n i n ga n dc o d i n gb e c o m ee a s i e rt h a ne v e r b e f o r e ，w h i c hi nt u mm a k e ss o f t w a r et e s t i n gm o r ea n dm o r ei m p o r t a n t w i t ht h e i m p r o v e m e n to fs o f t w a r et e s t i n gt h e o r i e s a n df a s t d e v e l o p m e n to fs u p p o r t i n g t e c h n o l o g i e s ，s o f t w a r et e s t i n gh a sb e c o m ea ni n d i s p e n s a b l ek e yp r o c e s so fs o f t w a r e q u a l i t ya s s h r a n c ei ns o f t w a r ee n g r n e e r i n ga r e a t h i sd i s s e r t a t i o ni sm a i n l yf o c u so nt h et e s te a s eg e n e r a t i o nm e t h o d sb a s e do n s t a t e c h a r ta n dzl a n g u a g e f i r s t l y , ad e t a i l e ds t u d yo ff o u rb a s i ct e s tc a s eg e n e r a t i o n m e t h o d sb a s e do nf i n i t es t a t em a c h i n e ( f s m ) w a sp r e s e n t e d a st oe x t e n d e df i n i t e s t a t em a c h i n e ( e f s m ) t e s t ，w ed e s c r i b eam e t h o dt h a tc o n v e r t se f s mt oa n e q u i v a i e n tt e s ts c e n e ；t h i se q u i v a l e n tt e s ts c e n ed o e sn o th a v et h en o n d e t e r m i n i s t i c p r o b l e m si nf o r m e re f s mw i t ht h ee x i s t e n c eo f p r e c o n d i t i o n s t h e nw ec a na p p l yt h e f o u rb a s i ct e s tc a s eg e n e r a t i o nm e t h o d sb a s e do nt h ef s mt ot h ec o n v e r t e de f s m t h e r ea r es t a t ec o m b i n a t o r i a le x p l o s i o na n dt e s ts e q u e n c es y n c h r o n i z ep r o b l e m si n l a r g es y s t e mt e s t i n g t h i sd i s s e r t a t i o no f f e r sam u l t i p l et e s t e rm o d e lt h a tc a l lg e n e r a t e t e s ts e q u e n c ew i t h o u tp r o d u c tm a c h i n e t h i sm e t h o da m e l i o r a t e st h ep r o b l e mo fs t a t e e x p l o r a t i o n a l s o ，t h ea l g o r i t b a no ft h es y n c h r o n i z a b l et e s ts e q u e n c eg e n e r a t i o n m e t h o da n ds y n c h r o n i z a b l eg r a p hg e n e r a t i o nm e t h o dw ed e s c r i b e di nt h i sd i s s e r t a t i o n s o l v et h es y n c h r o n i z ep r o b l e mi nt h et e s tp r o c e s s s o f t w a r et e s t i n gb a s e do nf o r m a l i z a t i o ni sa l s oa ni m p o r t a n ti s s u ei nr e c e n t r e s e a r c hw o r k m a n ys c h o l a r ss t u d i e dt e s t i n gm e t h o d sb a s e do nf o r m a ll a n g u a g es u c h a sz i nt h i sd i s s e r t a t i o n ，w ei n t r o d u c ea na u t o m a t i ct e s tc a s eg e n e r a t i o nm e t h o db a s e d 0 1 1zs p e c i f i c a t i o na n dd i s c u s st h ea d v a n t a g ea n dp o s s i b i l i t yo fc o m b i n i n gs t a t e c h a r t a n dzd u r i n gt e s t i n gp r o c e s s a l s o ，w ep u tf o r w a r dam e t h o dt h a tc a na u t o m a t i c a l l y c o n v e r ts t a t e c h a r tt ozs c h e m a ，w h i c hw i l lb e n e f i tt h ea u t o m a t i ct e s t f i n a l l y , w e 西v ea t e s tt o o lm o d e lb a s e do nt h em e t h o d sw ed i s c u s s e di nt h i s d i s s e r t a t i o na n ds o m es u g g e s t i o n so ns o f t w a r et e s t i n gp r o c e s si m p r o v e m e n t w ea l s o d e s c r i b et e s tc r i t e r i ai nzn o t a t i o n ，w h i c hc a ns u p p o r tt h ef o r m a l i z e dt e s tm e t h o da n d i t se v a l u a t i o na n da s s e s s m e n t i i 重庆大学硕士学位论文英文摘要 k e y w o r d s ：s o t c w a r et e s t i n g ，f i n i t es t a t em a c h i n e ，e x t e n d e df i n i t es t a t em a c h i n e ， s t a t e c h a r t ，z 1 1 t 重庆大学硕十学位论文l 绪论 1 绪论 l 。l 论文的选题及研究意义 软件测试是使用为发现错误所选择的输入和状态的组合丽执行代码的过程。 它是系统工程中的一个问题，是一种特殊的软件系统的设计和实现1 ”。自从计算 枫闽世以来，人们裁在稠程序中的b u g 锻着不断的斗争。程序的编写和测试长期 醴来一赢怒诗算税科学中的两大热点淘题。最初对程序溅试瓣基本方法是藏程序 运行并和预期的结果棚比较，从而验证程序的实现是否正确。 六十年代以来，随着程序规模的不断扩大和软件危机的产生，导致了软件工 程恶怒翁蹬嚣。人翻掇爨了软馋生滔蘩夔概念，稠疆懿凑软 孛牙发戴分为各个 阶段，舰意了各个阶段实现的目标以及生成的产晶。人们开始认识到错误不仅仅 是程序中的b u g ，程序编码中出现的错误可能是分析或者是设计本身出现的问题。 嚣此，久们将款 孛测试戆概念扩震到软馋开发的各个酚羧，提出了经典的v 模型， 使得软俘开发的每一个阶段都有稻应静测试过程与其对应。近年来，又有人撵盘 了改进的x 模型，随着人们对软件测试理解的深入，人们越来趟感到它的重要性。 这对软件产品质量的保涯以及软件机构对软件开发过程的组织都具有重要的意 义。 信息技术的飞速发展，使软件产品应用到社会的各个领域，软件产品的质量 自然成为人们共同关注的焦点。不论软件的生产辫还是软件的使用者，均生存在 竞争戆环嫒中，软件开发意为了占有声场，必须撼产品质量传为金韭瓣重要鹜标 之，以兔在激烈的竞争中被海汰嬲局。用户为了保证自己业务的顺利完成，当 然希望选用优质的软件。质量不佳的软件产品不仅会使开发商的维护费用和用户 的使用成本大幅增加，述可能产生其他的责任风黢，造成公司信誉下降，然而冲 击黢票枣沥。在些关键应震( 蠡涎靛订票系绞、镶彳亍缭箕系统、证券交爱系统、 航空、铁路自动控制系统、军事防御和核电站安企控制系统等) 中使用质燃有问 题的软件，还可能造成灾难性的后粜。 近年来，随蓦瑟羯x 譬象技术瞧广泛应用积c a s e 工具戆发艇，丈大减轻了软 件设计和编码的困难，丽使得软件测试变得越来越重要，在软件开发成本中所占 的比例也越来越大。据统计，在软件测试阶段的花费已占软件开发总成本的5 0 左右。晷翁代码自动生成技术已经在缀多c a s e 工其中缮到了广泛的应用，如果 范式( p a r a d l g m ) 靛采翻可将生产率疆高爨在 弋蕊生成中不需癸任俺久力的程度， 则剩下的全部工作将是测试和调试，这将消耗1 0 0 的工作内容 1 。可以说无论怎 样强调软件测试的重要性和它对软件可靠性的影响鄙不过分。 重庆人学颁士学位论文i 绪论 在较 孛 嚣| | 试过程中，流试囊镶懿生成是较件灏试戆关键帮罐点所在。嚣靛， 测试用例的生成还主蒙定依靠手工完成，而且要求软件测试人员具有一定的经验 和较高的专业水平。闵而，测试过程带有很大的裔目性，致使测试效率低下，测 试充分控不韪褥受摄诞，导致软件戏本露毫不下，较 孛覆量也缮不至l 缳汪。为此， 迫切需要改进软件测试的方法，开发一些有效的测试用铆自动生成工具，穗高软 件测试的效率，降低软件成本，保诞软件质量，提高软件生产自动化的程度。 l 。2 国内外研究瑗状耱主要存在的问题 六十年代的软件危机的出现，使得人们对软件开发的过稔麓新进行思考。人 们将软件开发过程划分为不同的阶段，并将软件测试的概念与软件开发的不问阶 段紧密联系，傻缛a 誊j 对款待灏试貔瑾簿更热深入。1 9 7 2 年，在美重豹霓黉_ 箩寒 纳大学召开了首次软件测试会议，这是软件测试领域的一个星程碑。1 9 7 5 年， g o o d e n o u g h 和g e r h a r t 2 1 提出测试数据选择理论，将软件测试这实践性很强的学 科，提赢到理论高度。髓后，w e y u k e r 帮r a p p s 1 等人又对该理论进一步完喾和 修改，拯出了著名昀r a p p s 帮w e y u k e r 准爱l 族。八、九卡年代以来，较件灏试葙 软件质量管理成了软件工程领域研究的热点。一些重要的标准也纷纷出台，包括 软件测试的文档标准i e e e a n s s t d ，8 9 2 、软件测试确认与验证计划标准 t e e e a n s is t d 1 0 1 2 、欲俘溺试复囊器窜嚣标壤1 e e e a n s is t d 1 0 2 8 等。软俘 测试研究的重点主要集中于测试用例的生成、自铷化测试工具的研制、分布式软 件的测试和面向对象软件的测试等。 测试懑论、方法与工具经历了形成、发展积不叛完善的羚段，其主要磺究成 果体现在： ( 1 ) 测试可靠性理论 对被测实现( i u t ，i m p l e m e n t a t i o nu n d e rt e s t ) 的理想测试怒测试该i u t 所有 蕊可撬孬籍径，毽对予菜一i u t 嚣言，可撬行路径往往是一令无凝集。为魏， w e y u k e r 和o s t r a n d 4 】掇出了半正确的概念，即不追求理想测试获取程序正确性的 目标，丽设法通过测试暴露出程序中存在的某类错误或验证此类错误不存在，从 瑟实觋半垂疆霹靠性溅试。完全路径测试、完全歪璇性测试积半正确蛙测试戆关 系如匿1 i 所示。 2 重庆大学硕士学位论文绪论 凰j 1 测试可靠性理论 f i g1 it e s t i n gr e l i a b i l i 哆t h e o r y ( 2 ) 渡l 试公瑾与测试准剐豹建立 g m y e r s 在他的祷作t h ea r to f s o f t w a r et e s t i n g 6 】中提出了如下著名的论断： 1 ) 测试是一个为了寻找错误而运行程序的过程； 2 )一令好瓣测试麓爨是豢缀可筑我妥迄今为业滏未发褒熬错误 的测试； 3 ) 个成功的测试是指发现了逡今为止尚未发现的错误的测 试。 上述躐赠蕴涵了测试蕊念的转交，成功酶测试是发现了以箭束发现的镣谈鲍 测试，i 雨不是人们通常认为的成功的测试是指没有找到错误的测试。测试的目的 是为了发现软件中的错误或缺陷，丽不是为了证明程序的正确性。同时，m y e r s 在该书中绘奎了蓥予蔽赣漉瓣滚试覆盏准剩这螽；s t a t e m e n tc o v e r a g e 、d e c i s i o n c o v e r a g e 、c o n d i t i o nc o v e r a g e 、d e c i s i o n c o n d i t i o nc o v e r a g e 、m u l t i p l ec o n d i t i o n c o v e r a g e 的描述。 r a p p s 帮w e y u k e r 3 5 t 以数据漉分凝兹壤念为麓磁，提出了著名兹r a p p sa n d w e j r n d | ( e r 测试标准族，并且发现和证明了该标准旗中各标准的偏序关系。r a p p sa n d w e y u k e r 测试标准族从数据流图抽辣出i u t 的d e f u s e 图，通过对变量的d e f 使 用和u s e 倥月路径的覆麓选择测试路径。该标准族中的a l l d u - p a t h s 标准被证明是 该标缕族中路径覆盖畿力仅次子所有路径覆盖舔掇翻l p a t h s ) ，在实际的涌试中得 到了广泛的应用。w e y u k e r 在1 9 8 8 年又提出了1 1 条测试充分性公理【”，这对测 试充分性的度量提供了依据。 ( 3 ) 基于有疆浚惑视戆溅渡燃铡生减 7 0 年代以来，有限状态机模型被广泛的应用到软件行为的描述中。在有限状 态机测试理论中，程序舰约( s p e c i f i c a t i o n ) 被描述成为一个有限状态机m ，i u t 被认为是糙序规约的一个有限状态执实观，即状态辊m 。测试熟髫的是要发现拼 串与m 不等价斡凌态和蜜迁1 8 。裉燕这一理论，已经有稷多学者提出了基予有陵 状态机横泌的测试用例生成方法，如t 方法【9 1 、u 方法【1 0 】、d 方法、w 方法【1 2 l 等。但这魑方法在多单元测试系统中存在同步问题、组合状态空间爆炸问题等， 重庆人学碳士学位论文 l 绪论 本文在螽程嚣懿章节审会其体接述。 ( 4 ) 基于扩展有限状态机的测试用例生成 扩展有限状态机比有限状态机能够更加精确的刻画软件系统的行为，但由于 扩溪有袋状态瓿孛兹交迂存在i 嚣条俘，单楚戆将基予有浆捩态凝翦灏试方法爱 于扩展有限状态机会产生很多问题，如测试序列不可执行问题。如何消除扩展有 限状态机的不确定性，成了测试的关键。 ( 5 ) 蓥于形式方法的测试躅例生成 形式方法阻萁筒滔、精确静表示方式，在软件开发帮溅试中筵着越来越整要 的作用。由于形式化撼自动化的基础，近年来，围绕着基于形式化测试的方法与 工具的研究，也进行的如火如荼。威用较广的形式化语言有z 、v d m 、l o t o s 等。毽鸯予缝落式纯熬东殛理解困难，并置姣乏爨予形式纯谗嚣夔测试准粼熬接 述和相应的支持形式方法的工具，这对形式化测试的应用和度麓带来了困难。 l 。3 本文的研究内察和主要工作 本文针对蓦于有限状态视、扩震有限状态辊翻z 语言鲶测试用鲻垒威方法进 行了研究。目的是能够解决应用上述方法测试时存在的一些问题，并为测试的自 动化和测试工具的进一步研制打下揍础。本文所徽的主要工作如下： ( 1 ) e f s m 孛嚣试场景静转换 本文搬出了一种将扩展有限状态桃转换为等价的测试场景的方法，转换后的 测试场带与原扩展有限状态机是测试等价的，并且消除了原扩媵有限状态机中由 于藏置条件静存在嚣导毁的不确定性。对于转换蜃懿扩曩有限状态税，可以应鬟 基于有限状态机豁测试方法。如t 方法 9 3 、u 方法f 1 0 3 、d 方法f l l j 、w 方法等。 ( 2 ) 多测试驱动模型和同步算法的提出 已有些学者将基子状态机的测试方法应用予状态图中1 3 , 2 0 。但在大型系统 静溺试审会存在缀合状态空阚瀑落鞠避稻测试彦劂阍多海题。本文疆赉静多瓣试 驱动模型m t m 在不生成积自动机的情况下生成测试序列，这缓解了组合状态空 间爆炸问题。同时，本文提出了基于m t m 的可同步算法，避免了应用m t m 产 皇兹嚣步鹚遴。 ( 3 ) 同步有向图的应用 对于通信协议和一嫂分布式系统的测试，通常对应于一个多个端口的有限状 态极，需爱多个测试单元避彳亍测试i h 3 。在测试过稔中，测试单元之闫可能会出理 同步逶藩溺题，通常瓣麟决方法是灞攘舞舔同步搽作。本文引入| 霜步畜囱醋豹连 通性来判寇给定的有限状态机是否可以独立生成同步测试序列。对于非强连通的 同步有向图，可以将其转换为强连通，在此基础上生成同步序列。 4 重庆大学颈上学位论文1 绪论 ( 4 ) 毒爱态匿与z 模式静转换 基于形式化语言z 的测试是近年来软件测试研究的一个方向。本文讨论了从 状态图到z 的模式的转换方法，提出了相应的算法。有助于基于状态图和z 结合 兹溅试方法粒应爱，莠黠溅试翡彩式讫窝叁动化援貘了磐动。 ( 5 ) 溯试工具模型的提出 能够生成有效的测试工具是我们研究的最终目标，优秀的测试工具对于提高 软件质量、改善软件开发过程和提簿软件测试豹效率邦有着熏爱静作用。本文基 于文章中穗至酶溅试方法，提出了一个溺试工螽斡模型框黎，这为进一步瓣工具 开发奠定了基础。 ( 6 ) 测试准则的z 描述形式 溅试穗爨在获传测试过程中起蠢雾鬻重要豹俸艨。蕤试领域豹一些专家已经 给出了一魑测试准则的描述，但所有的这些描述都是在自然语言的基础上进行的， 对于它们的理解存在着：义性。而且，使用z 的测试方法时，却没有相应的以z 豹形式撼逑翦测试准则，这霹于基予z 静测试豹发量与应用产冬三了困难。本文尝 试魇z 酶方式播述基予控制流酶测试准刚，这霹于对涮试的璎解耱度量，育定 的意义。 1 4 本文的缓织安鬟 本文共分七章，各部分安排如下： 第一章：本章为绪论部分，主臻介绍了论文的选题和研究意义、国内外的研 究理欹和本文熬主要工搀及礤究重点。 第二津：本章详缎介绍了基于有限状态梳的麟稃测试方法：t 方法、u 方法、 d 方法、w 方法。对于扩展有限状悫机的测试，本章提出了测试等价转换的方法， 消除了由游漫变迁导致的测试用例不可执行闽题，使得扩展有限状态机的测试可 以应用蓥予有疆狡态税黪溺试方法。 第三帮：本章提出了多测试驱动模型m t m 用于缓解状态空问爆炸的问题， 并提出了栩应的同步算法，解决了旗于m t m 测试的同步问题。同时，本章应用 霆步有囊图黠煮鞭扶态秘是否可以独立生残霜步溅试痔到遂 予燃凝。 第四章：本章将测试工作迸一步形式化，引入了z 语言和旗子z 的测试方法 以及z 和状态图相结合的测试方法。提如了状态阁和z 模式之间的转换算法，有 助于测试嬲侧妁自动生成。 第五章：本章结合静嚣章节酶潞试方法，提澎了基于本文方法的测试工疑模 型框架，为进一步的工具研制，奠定了基础。 第六章：本章将测试准则用z 语言进行了描置楚，以消除自然语言中的不确定 重庆大学硕士学位论文1 绪论 性，对基于z 的测试充分性提供了度量的标准，也在一定程度上缓解了测试序列 的可执行性问题。 第七章：对全文的工作进行了总结，同时对将来的研究工作进行了展望。 6 重庆人学葡 i 士学位论文2 基于f s m 和e f s m 的测试用例生成 2 基于f s m 和e f s m 的测试用例生成 2 ，1 关于骞限状态橇的术语及定义 有陵状态援可戮跣较精确麓刻蕊软彳孛系统麓行为。霹此有黻状态极被广泛应 用于许多领域的应用系统建模，诸如：通信协议、实时系统、面向对象软件中类 的行为及其交互等。有限状态机是个系统，是有限自动机这数学模型的工程 应震，它豹辕出是枣当 ；爹豹辕入秘过去戆羧入决定貔。一个骞羧凌态援菩怒色含 4 个构成元索：状态、转换、事件和动作。 一个有限状态机肼可以表示为个六元组( s ，s o ，6 ，九，i ，o ) ，其中： s 是蠢隈状态集会； s 。s 楚裙态； 6 是状态转换函数； 九是输堪函数： l 是有藩输入字褥黛； o 愚有限输出字符集i m 处于状态s 时接收到输入x i 后，产生输出y = k ( s ，x ) 并且迁移至状态s k 6 ( s ，x ) ，潍产生一令变透t ，记为t ( s ，s ，x y ) ，其中，s = h e a d t ) ，s 式葫( 1 ) 。 从状惑s i 到状态s 怒可达的是掩有一个合法的输入序耐馕机器能从s l 到达s j ， 当没有指明一个开始状态而说某一个状态是可达的，则默认初态为开始状态。 对于个有限状态枫m ，如果对每一个状态和每一个输入，5 和九都有定义， 都么称m 楚完全定义( c o m p l e t e l y s p e c i f i e d ) 戆有限狡态掇。一令给定靛青黻获 态机如果不是完全定义的，可以通过对末完全定义的状态增加相应的6 和 定 义以达到宠全定义，其定义方法为：s 是一个未完全定义的状态，对每一个未定 义静输入x ，5 ( s ，x ) 竣毒摆自令密镑状态，或纛撑彝童尝，x ( s ，x ) ；n u 艇，。 对于一个有限状态机，如果存在个输入r i ，对于任何一个状态s ，都满 足6 ( s ，r ) = s o ( 其中s 0 是初态) ，则该有限状态机县有重置功能( r e s e tc a p a c i t y ) ， 缺省的，我们假定这一输入的命名为r e s e t 。这样，我们可以使用r e s e t 分割不嗣 酶溪l 试序列胍焉形成一个灏试输入序舞，这一输入序剜可懿依次输久系统溺试。 如果一个肖限状态机肘可以从初始状态s 。到达每个状态，则称该有限状态机m 是初始化避通的( i n i t i a l l yc o n n e c t e d ) 。在状态机骏证理论中，如果一个状态不能 由蓊热状悉裂达，裂浚羧态应当效获态蕊孛鬻狳。翅巢对予醚中熬每一对状态( s i ， s j ) ，都存在个输入序列使得从状态s i 变迁到j 陡态s j ，则称m 罴强连通的( s t r o n g l y c o n n e c t e d ) 。很明显，从上面的定义可知，如果m 是初始化涟通的并具有黧踅功 重庆大学硕士学位论文2 基于f s m 和e f s m 的测试用倒生成 能，刘掰怒强连逶静。关于有限菰态税斡更多理论请参阕参考文献 1 5 j 。 2 1 2 基于有限状态机的四种经典测试方法 本节将麓要奔绥臻藏基于毒疆状态瓤懿疆磅经典巍试序列生藏方法，它稍分 别为：t 方法 9 、u 方法 1 。】、d 方法f l i 】、w 方法 1 2 1 。以上这些方法使用的前提条 件是有限状态机是完错的、强连通的并且是精简的【1 6 。这里首先给出相关的定义。 这里所说的有限状态枫均为m e a l y 机，即一个转换可能有一个输出动作，并 且任俺一个输出动 乍酃可镀雳在不斑令转换上。与m e a l y 枫裙对应魏是m o o r e 机，即转换没有输出动作。m e a l y 和m o o r e 模型谯数学上是等价的，任何个系 统如果可以用m o o r e 机建摸，则也可以用m e a l y 机建模，反之亦然。h o p c r o f f 在 1 9 7 9 每绘窭了m o o r e 辍窝m e a l y 穰糖互转换麴雾法。对予凌个系绞，交予杰 m o o r e 机中，一个状态只能代表一个输出动作，状态的数量比较多，转换图比较 复杂，故本文选取m e a l y 机模型。 定义2 1 如果一个状态枫m 中掰包含的状淼数强小予或镣予侄 可和它等价 静状态辊m 中所包含的状态数霞，刘称状态戳m 是最小鲸。 定义2 2 给定一个有限状态机m ，若vs i ，s j s m ：( j p c i + ：( 6 m ( s i ，p ) 一s i ) ) ， 则称该有限状态机是强连通的。 定义2 + 3 绘定一个有限状态辊m ，若v s i s m ：( ￥x ：( 王s j s m ： 氓s i , x ) = s ，) ) ，则称有限状态机s 为完备的。 定义2 4 给定一完备有限状态机m ，若v s i ，s j s m ：( v x e i ：( 九( s i ，x ) 艇s j ，x ) ) ) ，慰稳该完螯有限状态枧为精麓约。 定义2 5 给定一有限状态辊m ，其初始状态为s o ，v s ig s m ：( 主p c i + ： ( 6 m ( s o ，p ) * s i ) ) ，则称s 中的状态是可达的。 我们使娟m 广一) ( y 一峨表示有限状叁机m 处于m i 状态时接受输入x 使状态 转移至lm l 状态荠产叟输窭y 。令v l 斧孽v 2 是蠢个输入彦剜集会，簧lv l ，v 2 表示 两个输入序列的串联，即v 1 v 2 = v 1 v 2 l v t v 1 ，v 2 v 2 ，v o = v v ”1 ；x k 】袭示集 合 u x u x 2 u u x o ：令a 和b 表示两个有限状态机，在本文中由a 表示规 约谩礴中黥狭态凝，8 袋示对a 的实疆中筑状态羧l 。 定义2 6 给定一个输入序歹4 集台v ，以及两个有限状态帆a 和b ，vs i s h ： ( 了i k s b ：( v v e v ：九( s i ，v ) = x 0 k ，v ) ) ，则称s t ，i k 关于u 等价，记为s t “v i k 。 定义2 。7 若对于任意输入序列集合v ，s ；和l k 郝是关于v 一等价的，则称s i 帮i k 等价，记为s i l k 定义2 8 若两个有限状态机a 和b 的初始状态s 。和i o 是簿价的，则称这两 个状态机烧等价的。 重庆大学硕士学位论文 2 基于f s m 和e f s m 的测试用例生成 定义2 9 给定一有限状态机a ，令q 是一个输入序列的集合，若e q 并且 v s i s a ：( j q q ：( s o q s i ) ) ，则称q 是s 的状态覆盖集。 定义2 1 0 给定一有限状态机a ，令p 是一个输入序列集合，若e p ，并且 对于任意状态迁移s i 划y s l ，s i s j s a j p , p x p ：( s o p s i ) 八( s o p x s ；) ，则称p 为s 的状态迁移覆盖集。 定义2 1 1 给定一有限状态机a ，令w 是一个输入序列的集合，若v s ，s j s a ：( j w e w ：( 九( s i , w ) z ( s j ，w ) ) ，则称w 是a 的特征集。 定义2 1 2 用于测试有限状态机a 中的一个状态或是一个变迁的一组输入符 号序列叫做该有限状态机a 的一个测试子序列。 定义2 1 3 给定一个有限状态机a ，将测试a 中每一个变迁的测试子序列连 接起来叫做该有限状态机的b 序列。 2 2 1t 方法 t 方法较为简单，假定一个有限状态机是强连通的。测试输入序列对应于规 约说明中的状态迁移随机地产生，直到所有的状态迁移都被覆盖。该方法的缺点 是测试输入序列中存在大量的冗余，甚至可能会存在环。另外其检错能力也较差， t 方法只能检测变迁是否存在，而不能检测变迁所到达的状态。 t i j 直厂1 图2 1 有限状态机m 的状态变迁图 f i g2 1a t r a n s i t i o nd i a g r a mo f m a c h i n em 对于图2 1 中所示的状态机，应用t 方法可以生成如下的测试序列来覆盖所 有的变迁： u 方法的前提是假定一个最小的、强连通的、并且是完备的有限状念机m 。 该方法需要得到该有限状态机中每一个状态的一个识别序列，该序y , jn q 做单一输 入输出序列( u i o ，u n i q u ei n p u t o u t p u ts e q u e n c e ) 。u i o 序列可以唯一的标识m 中 b 2b a 2 a 4 a a 2 a 4 a 3 a o b 4 a 3 o d 1 ) 龛赫 b o u2 重庆大学颂十学位论文 2 基t - f s m 和e f s m 的测试州例生成 静状态，不靖静状态不麓有稽慝筑u i o 序硼。鬣并不是艨畜静有羧获态辊帮存在 u i o 序列，如果一个有限状态机不存在u i o 序列，则无法应用该方法构造测试输 入序列。 对予一个有疆状态瓿m 中兹每一令技态之灏粒变纯，罄边( s i ，爰) 参冕粼2 。l ， 我们用以下方法生成每个变迁的测试子序列： ( 1 ) 输入r ( 既r e s e t ，这里讨论的每个有限状惑机都有重鼹功能) 到m ，使m 回到初始状态o ； ( 2 ) 羧瑚觚出态0 捌状态s i 兹最短鼹径s p ( s i ) , ( 3 1 输入可以使有限状态机m 从状态s i 变迁到s j 的符号； ( 4 ) 输入状态s j 的u i o 序列。 表2 1 囊2 。t 孛蔽态的交迂 t a b l e 2 ia t r a n s i t i o nt a b l ef o r m a c h i n ei nf i 9 2 ，1 输出下个状态 输八 aba b 状态 0ox20 l1l32 20013 30143 4l12o 表2 2 强2 中有疆浚态壤鹣u i o 亭剜 t a b l e 2 2u i os e q u e n c e sf o rmi nf i 9 2 i 状态 u i o ob 九 la l a l 2b 脑 3b lb l 4a 九a o 我黧黠圈2 1 孛兹有陵浚态瓿m 应蘑u 方浚，表2 蠢交2 。2 分爱绘爨了醚 的状态变迁和每个状态的u i o 序列。在u 方法中，每一个状态可以通过输入它的 u i o 序列米识别。例如，我们输入a a 而输出的结果为1 0 ，则我们知道浚有限状 态飒正处于状态4 ，参见表2 1 2 。 在u 方法中，对予图2 1 所示的有限状态枫m 盼$ 序耐魏下，其中瓣试每一 个变迁的子序列按照上述4 个步骤进行： r bb r a 转b r a a a a a a a raaaabb 1 0 蘑庆大学硕士学位论文 2 基于f s m 和e f s m 的钡4 试用例生成 raaaaaa raaabbb r a a a a f a 撼器器 r a a a b r a a bb 以上楚针对图2 。1 孛有限状态枫m 约l o 个变迂( 鄂鳕中l o 条边，对于初始 状态0 霄一个黢瓿静攥淘鸯身酶环转屈，其中x 代袭空输出) 。将上述溅试序到优 化可以得剐使用u 方法的最短测试序列： 1 a i r a a a a r a a a a b b r a a a b b b “轧蟠b r a b b b 赶j b 2 。2 3 d 方法 d 方法的前提是假定个最小的、强连通的、并且是完备的有限状态机m 。 该方法酋先对有限状态机m 构造一个区分序列d s ( d i s t i n g u i s h i n gs e q u e n c e ) ，然后 根据该区分序到构造测试输入序列。鞠u 方法撵，并不是所有熬状态祝都存在 区分序磷，所以滚方法虢应用瞧育定的限翩。 d 方法的关键是计算有限状态机的区分序列d s ，文献 1 1 中有通过建造区分 树来获得区分序列的详细算法。对于图2 ，l 所示的有限状态机，b b 是它最短的 0 s 。衰2 3 给窭了将该d s 应瑟予有隈状态礁m 时，每拿获态憝簸窭旁弼。德熬， 当应用d s 到有限状态机m 后，输出为1 0 ，则我们可p i e r 定m 处于状态l 。 表2 3 对于图2 1 中育限状态机m 应用d s 时的输出 d 方法中且序列的生成基本上和u 方法相同，只需在最后步中将相应的 u i o 序列换威d s 即可。对于图2 1 中有限状态机m ，其列宁列如下： r bbb r a bb r a a a a a bb r a a a a b 8 b raaaabb raaabbb r a a b b 重庆人学硕士学位论文 2 撼于f s m 孝兀e f s m 的测试用例生成 rabbb r a a a b b r a a b b b 将上述测试序歹g 镌讫可班褥到後翅d 方法的竣短襄l 试序列； n 气a a a a b b r a a a a b b b r a a a b b b i a a b b b r a b b b r b b b 2 2 4 w 方法 w 方法的前提是假定一个最小的、强连通的、并且是完备的有限状态机m 。 该方法要求首先生或有限状态梳m 黪特征集w ，然后在特征蘩w 鲍基礤上构造 测试输入序列。只要状态机是最小的、完备的都存在特征集，所以该方法的适用 性较强。特征集w 是幽这样一组数据组成：对于m 中的每个状态输入w 中的数 据g ，8k 褥至l 款缀螽一位赣出舔不嚣，嚣m i s i ( 。1 ，8k ) m 1 s j ( 8 l ， ok ) ，这麓s i 和s j 是m 中的两个不黼状态。 应用w 方法测试的原理和u 方法类似，特锻集w 的作用是为了识别裔限状 态机m 中的每个状态。对于有艰状态机m ，可以按照以下步骤生成测试序捌： ( 1 ) 构造有限状态穰m 的特征蘩w ，w = dl ，ak ，这攫oi 是一个输入字 符，1 主i 簋k ，特征集w 的构造算法可以参见参考文献 1 2 】。 ( 2 ) 按照u 方法中的步骤生成b 序列，不同的是要将每个状态的u i o 序列换 藏跨，匮集w 。 s p ( s ) w = s p ( s ) 圆 d1 ，2 ，ak ) = s p ( s ) 啦d1 ，s p ( s ) o 心2 ，s p ( s ) 圆 o k ) 这里姻s p ( s ) 是搀扶翅始状态到达状态s 豹最短路径。对予强2 ，l 所示瓣有限 状态辊m 很容易褥至特征集w 为 a a a ，b l 。表2 4 给出了对黼l 中静有隈状态 机m 应用特征集w 时缚个状态的最后一个输出。通过观察相应的输出序列，我 们可以很容易的判定m 所处的状态。例如，当输出为0 1 0 时，我们可以判定当前 有疆获泰狡辩正楚在状态2 。 表2 4 对图2 1 中有限状态机m 应用特征集m 最后的输出 t a b l e 2 4l a s to u t p u ts y m b o l so nc h a r a c t e r i z a t i o ns e twf o rmi nf i 9 2 1 状态 m i s ( a )m i s ( a a )m s ( b ) o00兔 lll1 2010 3011 410l 对圈2 t 孛懿畜蔽状态租，应瘸w 方法露以垒或螽下熬淳蘩： r b a r b a a 重庆人学硕士学位论文2 基于f s m 和e f s m 的测试用例生成 r bb r a a r a a a r a b raaaaaa r a a a a a a a raaaaab raaaaba r a a a a ba a raaaabb r a a a a a raaaaaa r a a a a b r a a a b a raaabaa r a a a b b r a a a r a a a a r a a b r a b a f a 转a a r a bb r a a a a r a a a a a r a a a b r a a b a r a a b a a r a a b b 将上述测试序列优化可以得到使用w 方法的磺短测试序列： r a a a a a a a r a a a a a b r a a a a b a a r a a a a b b r a a a b a a r a a a b b n 气a b a a r aa b b r a b a a r a b b r b a a r b b 遥避上述实翻可懿看至l 傻嗣u 方法和d 方法褥蓟的测试序列较短，但它们躲 应用有一定的限制，如有时不存在u i o 序列或d 序列。w 方法的适用性较广， 但该方法产生的测试输入序列相对较长。近年来，有很多学者致力于这四种基本 1 3 重庆大学硕士学位论文2 基于f s m 和e f s m 的测试用例生成 方法懿改避工作，已经取得了一鳌成绩。始e u 1 0 方法【3 、t e a 方法【 1 、w p t y 法”1 、r w ，方法【1 9 蝽。对四种基本方法的改进并非本文的研究重点，本文重点 在于解决应用这四种蕊本方法在实际的测试中存在的问题。在后续的章节中，本 文详缨分缮了这些阗趱及本文蕊鼹决方法。 2 - 3 基于扩展有限状态机的测试用例生成 扩展有限状态规( e f s m ) 模型怒对有限状态执( f s m ) 模型鹣个扩展。它在 f s m 模黧的基础上增擒了变量、操作、变迁的静爱条件等。e f s m 有存储功篷， 它的每个状态都有默认的重置( r e s e t ) 功能，即：d ( 即r ) 一- - - s 0 ( 其中s o 是初态) 。 通过e f