已阅读5页,还剩49页未读, 继续免费阅读
(计算机软件与理论专业论文)基于时间自动机模型的测试用例生成方法研究.pdf.pdf 免费下载
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
原创性声明 本人郑重声明:所呈交的学位论文,是本人在导师的指导下,独立进行研 究所取得的成果。除文中已经注明引用的内容外,本论文不包含任何其他个人 或集体已经发表或撰写过的科研成果。对本文的研究作出重要贡献的个人和集 体,均己在文中以明确方式标明。本声明的法律责任由本人承担。 学位论文作者: 蓖素嗖瓦 日期:矽扣年j 一月 ;口日 学位论文使用授权声明 本人在导师指导下完成的论文及相关的职务作品,知识产权归属郑州大学。 根据郑州大学有关保留、使用学位论文的规定,同意学校保留或向国家有关部 门或机构送交论文的复印件和电子版,允许论文被查阅和借阅;本人授权郑州 大学可以将本学位论文的全部或部分编入有关数据库进行检索,可以采用影印、 缩印或者其他复制手段保存论文和汇编本学位论文。本人离校后发表、使用学 位论文或与该学位论文直接相关的学术论文或成果时,第一署名单位仍然为郑 州大学。保密论文在解密后应遵守此规定。 学位论文作者: 芄素重巍 日期:劲 矿年 月 如e l 摘要 摘要 软件测试是提高软件可靠性和保证软件正确性最基本和最重要的手段,而 测试用例的设计又是软件测试的核心,是软件测试质量的根本保障。随着软件 系统规模的r 益扩大和应用领域的不断拓展,使得对软件系统的测试变得更加 困难。因此,自动化的软件测试技术成为近年来软件测试的重要研究方向。 基于模型的测试用例生成技术已被证明是很有发展前景的测试反应式软件 系统的自动化测试用例生成方法,它用形式化的方法对系统进行建模并基于所 建模型生成测试用例。模型检测是基于模型的测试用例生成方法用到的主要技 术,因此在测试用例生成过程中状态空间爆炸问题也不可避免。另外,对于实 时系统而言,系统时序逻辑的错误会产生灾难性的后果。因此,如何避免测试 用例生成中的状态空间爆炸并尽量发现软件中隐含的时序逻辑错误是本文研究 的主要内容。 本文通过对基于时间自动机模型的测试用例生成方法进行研究并对具有不 同时间尺度的一类实时系统进行分析,提出了一种基于时间自动机模型的测试 用例生成方法的优化技术。该方法通过对原时间自动机模型的结构进行改进来 减少状态空间爆炸造成的影响,加快基于模型的测试用例生成的速度并减小生 成的测试用例集的大小。 实时系统通常是并发的,因此响应时间依赖于不同任务的执行时间和执行 次序。本文通过对基于任务扩展的时间自动机模型的变异测试方法进行研究并 深入分析了并发实时系统的内部行为特性以及各种可能的测试假设,提出了一 种变异测试生成方法,定义了模拟实时系统各种时序错误的变异操作符,并使 用调度分析工具t i m e s 来对实时系统建模,使用定义的变异操作符对系统的时 间自动机模型进行变异,从而生成导致系统实时性问题发生的测试序列。 关键词:实时系统基于模型的测试测试用例时间自动机模型检测 状态空间爆炸变异测试 a b s t r a c t a b s t r a c t s o f t w a r et e s t i n gi st h em o s tf u n d a m e n t a la n di m p o r t a n tw a y t oi m p r o v es o f t w a r e r e l i a b i l i t ya n dg u a r a n t e et h ec o r r e c t n e s so fs o f t w a r e a n dt h ed e s i g no f t e s tc a s e si s t h ek e yi s s u eo fs o f t w a r et e s t i n g i ti sa l s oaf u n d a m e n t a lg u a r a n t e eo ft h eq u a l i t yo f s o f t w a r et e s t i n g 。w i t ht h ei n c r e a s i n gs c a l eo fs o f t w a r es y s t e m sa n dt h ee x p a n d i n go f a p p l i c a t i o n s ,t h et e s t i n go fs o f t w a r es y s t e m sb e c o m e sm o r ed i f f i c u l t t h e r e f o r e ,t h e t e c h n i q u e so fa u t o m a t e d s o f t w a r e t e s t i n gh a v eb e c o m e a l l i m p o r t a n t r e s e a r c h d i r e c t i o n si nr e c e n ty e a r s m o d e lb a s e dt e s tc a s e sg e n e r a t i o nh a sb e e nd e v e l o p e da sap r o m i n e n tt e c h n i q u e i nt e s t i n go fr e a c t i v es o f t w a r es y s t e m s i tu s e sf o r m a lm e t h o d st om o d e lt h es y s t e m a n dg e n e r a t e st e s tc a s e sb a s e do nt h em o d e l m o d e lc h e c k i n gi so n eo ft h em a i n t e c h n o l o g i e st h a ta r eu s e di nm o d e lb a s e dt e s tc a s eg e n e r a t i o n s oi t i si n e v i t a b l et o m e e tt h es t a t e s p a c ee x p l o s i o np r o b l e mi nt h ep r o c e s so fd e r i v i n gt e s t c a s e s i n a d d i t i o n ,t e m p o r a ll o g i ce r r o r s i nt h es y s t e m sw o u l dp e r h a p sl e a dt od i s a s t r o u s c o n s e q u e n c e s f o rr e a l t i m es y s t e m s t h e r e f o r e ,h o wt oa v o i d t h e s t a t e s p a c e e x p l o s i o ni nt h et e s t c a s eg e n e r a t i o na n dt r yt of i n di m p l i e dt e m p o r a le r r o r so f s o f t w a r ea r e t h em a i nq u e s t i o n sd i s c u s s e di nt h i st h e s i s t h et h e s i ss t u d i e st h em e t h o do ft e s tc a s eg e n e r a t i o nb a s e do nt i m e da u t o m a t a a n da n a l y z e sac l a s so fr e a l t i m es y s t e mw i t hd i f f e r e n tt i m es c a l e s at e c h n i q u eo f i m p r o v e m e n to nam e t h o do ft e s tc a s e sg e n e r a t i o nb a s e do nt i m e da u t o m a t ai s p r o p o s e d t h eo r i g i n a ls t r u c t u r eo ft i m e da u t o m a t am o d e li si m p r o v e dt or e d u c et h e i m p a c to ft h es t a t e s p a c ee x p l o s i o n a c c o r d i n g l yt h ev e l o c i t yo fm o d e l - b a s e d t e s t c a s e sg e n e r a t i o ni se n h a n c e da n dt h es i z eo ft h eg e n e r a t e dt e s ts u i t ei sr e d u c e d r e a l t i m es y s t e m sa r eo f t e nc o n c u r r e n t ,s ot h er e s p o n s et i m ed e p e n d so nt h e e x e c u t i o nt i m ea n do r d e ro fd i f f e r e n tt a s k s a f t e rs t u d y i n go nam e t h o do fm u t a t i o n t e s t i n gb a s e do nt i m e da u t o m a t ae x t e n d e dw i t h t a s k sa n da n a l y z i n gd e e p l ym e c _ h a l a c t e r i s t i c so fi n t e r n a lb e h a v i o r so fc o n c u r r e n tr e a l - t i m es y s t e ma n da l lp o s s i b l e w a y so ft e s th y p o t h e s i s ,t h i st h e s i sg i v e sa n e ww a yo fm u t a t i o nt e s t i n g w ed e f i n ea f e wk i n d so fm u t a t i o no p e r a t o rf o rs i m u l a t i n gav a r i e t yo ft i m i n ge r r o r so f r e a l - t i m e i i a b s t r a c t s y s t e m s w eu s et h et o o lo fs c h e d u l i n ga n a l y s i st i m e st om o d e lt h er e a l - t i m e s y s t e m s a n dt h et i m e da u t o m a t am o d e lo fs y s t e mi s m u t a t e db yo u rm u t a t i o n o p e r a t o r s t h i sm e t h o dc a ng e n e r a t et e s ts e q u e n c e sw h i c hc a n r e v e a lt i m i n ge r r o r so f s y s t e m s k e yw o r d s :r e a l - t i m es y s t e m s m o d e l - b a s e d t e s t i n g t e s tc a s e st i m e d a u t o m a t am o d e lc h e c k i n g s t a t e s p a c ee x p l o s i o n m u t a t i o nt e s t i i i 目录 目录 摘要i a b s t r a c t i i 目录i v 1 绪论1 1 1 研究背景和意义1 1 2 国内外研究现状2 1 3 本文所做工作4 1 4 本文结构安排4 2 基于模型的测试用例生成方法介绍6 2 1 软件测试模型6 2 2 模型检测9 2 3 基于模型的测试1 3 2 3 1 基于模型的测试1 3 2 3 2 测试用例选择准则1 4 2 3 3 基于模型的软件测试的特点1 5 2 4 本章小结1 6 3 基于时间自动机模型的测试用例生成方法优化1 7 3 1 前向符号可达性分析中的问题1 7 3 2 模型检测的加速1 9 3 3 测试生成优化2 0 3 3 1 测试生成工具2 0 3 3 2 覆盖准则2 l 3 3 3 实验验证及分析2 3 3 4 本章小结2 6 4 基于时间自动机模型的变异测试生成方法2 7 4 1 基于变异的测试2 7 i v 目录 4 2 系统模型2 8 4 2 1 任务参数和约束2 8 4 2 2 任务时间自动机2 9 4 2 3 调度分析3 1 4 2 4t i m e s 3 2 4 3 变异操作符3 2 4 3 1 任务集变异操作3 3 4 3 2 自动机变异操作3 5 4 4 变异测试用例生成3 5 4 4 1 测试生成过程3 5 4 4 2 实验设置3 6 4 4 3 实验运行3 7 4 5 本章小结4 0 5 总结与展望4 2 参考文献4 3 致谢4 7 个人简历在学期间发表的学术论文与研究成果4 8 v l 绪论 1 绪论 1 1 研究背景和意义 从计算机诞生以来,人类对程序正确性的追求从来就没有停止过。软件测 试可以帮助开发者确定和保证软件产品的质量,使用户建立对软件产品的信心。 但是,软件测试又是一项十分复杂和困难的工作。不论从测试时问还是测试资 源的消耗上往往都达到了整个项目的一半以上。因此,软件测试一直以来都是 软件工程中十分活跃的研究领域,是软件质量保证的主要活动之一,提高软件 测试的效率和性能,对于软件工程具有十分重要的价值。 随着软件系统规模的日益扩大及其应用领域的不断拓展,传统的人工测试 的局限性越来越明显。另外,由于实时系统引入了时间维,大大增加了人工方 式分析系统可能行为的难度,考虑到测试产生和执行所需的时间和资源以及测 试覆盖的充分性,测试的有效性亟待提高。基于模型的软件测试技术正是在这 样的背景下受到了密切的关注,它是一种自动化软件测试技术,属于基于规范 的软件测试范畴,其特点是:根据测试模型即被测程序的模型及其派生模型来 生成测试用例和进行测试结果评价。基于模型的测试早期主要应用于硬件测试, 目前在软件测试中也得到了越来越多的应用,并且在工业界和学术界受到了越 来越多的重视。 软件的可靠性是影响整个系统安全性的主要因素,而实时系统大多属于安 全攸关的系统,在软件系统投入运行之前,需要尽可能地发现并及时纠正软件 中的错误。从上世纪九十年代开始,随着时序逻辑( t e m p o r a ll o g i c ) n 1 、时间过 程代数、时间p e t r i 网和时间自动机( t i m e d a u t o m a t a ) 口3 等时间相关形式模型理 论的逐步成熟,人们开始研究利用这些时间相关形式模型来对实时系统进行测 试,其中时间自动机模型因为其描述能力强和描述手段简洁等一些特点,在基 于模型的测试中得到了广泛的研究和应用。 基于时间自动机模型的实时系统测试用例自动生成面临的主要问题是:实 时系统中时间维的引入大大增加了测试模型的复杂性,增加了状态空间爆炸的 可能性,从而增加了测试用例自动生成的难度。另外,不同的模型抽象级别以 及测试者对系统和与其交互环境的抽象行为的不正确的假设,都会增加系统设 计与实现的不一致性。评价一个测试方法好坏的主要标准是生成的测试用例集 1 绪论 的大小和其错误检测能力,因此,基于模型的实时系统测试用例生成方法希望 解决如下问题:用形式化的方法准确描述待测系统,并在尽量弱的测试假设下, 使生成的测试用例集尽量小但揭错能力足够强。 传统的白盒测试方法都要求测试者了解软件的内部结构,例如基于代码的 测试需要测试者熟悉代码的各个部分,尤其对于比较大的软件系统,测试人员 需要事先通读成千上万行的代码,这将是一件比较痛苦的事情。另外,当程序 运行出错时,准确定位错误发生的地方也是件比较耗时的工作。而基于模型的 测试是一种黑盒测试方法,测试人员不需要了解软件系统的内部结构,它是从 系统的需求规范说明建立系统的抽象行为模型,属于功能测试的范畴。研究基 于模型的测试技术对提高测试的自动化水平、加快软件开发进程和提高软件开 发质量都具有深远的意义。另外,很多基于模型的测试是基于需求生成测试模 型,可以在软件开发早期及时发现软件中的错误,缩短软件开发周期并减少软 件开发费用。总之,基于模型的测试技术是自动化测试领域十分活跃的研究课 题,对提高测试效率、保证软件质量和保障人类生命财产安全都具有极高的理 论价值和不可估量的实践意义。 1 2 国内外研究现状 通过对目前基于模型的测试用例自动生成方法的研究现状进行调查研究, 国外的一些组织和机构在这一研究领域己进行了大量的研究工作,并取得了阶 段性的研究成果,有些研究机构正努力将该方法运用于实践中,国内相对而言 这方面的研究较少,还处于起步阶段。 1 9 5 6 年,m o o r e 提出了有限状态机( f s m ) 模型测试框架,被认为是基于 模型测试的开端。六十年代主要研究将基于模型的测试技术应用于硬件测试。 从七十年代末开始,随着对网络和通信协议测试需求的不断增加,基于模型的测 试更加活跃。出现了各种基于有限状态机、扩展有限状态机、标号迁移系统等 时间无关形式模型的测试用例生成算法,代表性工作主要有u 一方法口1 、d 一方法 h 3 、用于有限状态机测试的w 一方法陌3 、w p 一方法3 等。从九十年代中期开始,随 着时序逻辑、时间标号迁移系统口、时间自动机等时间相关形式模型理论的逐步 发展与成熟,人们开始研究利用时间相关形式模型来测试实时系统。 基于模型的实时系统测试方法是一个相对较新的研究领域,由于时间维的 2 l 绪论 引入,该测试方法面临的主要的问题是状态空间爆炸和对时间特性测试的复杂 性。为了降低状态空间爆炸给测试用例生成带来的难度,目前各种方法的基本 思想都是将时间自动机中的位置和时钟域一起构成一个符号状态来生成有限的 状态模型,域图( r e g i o ng r a p h ) 和带图( z o n eg r a p h ) 隅1 是其中最典型的方法。 由于带图所产生的符号状态数较少,所以大多数实时系统模型检测方法都使用 带图。但是由于带图中的符号状态不具有稳定性,所以带图并不适用于测试, 因为根据带图生成的符号状态迁移序列并不一定可行。域图生成的符号状态虽 具有稳定性,但根据域图生成的符号状态数会随着自动机中时钟约束常量和时 钟个数的增长而呈指数增长。文献 9 ,1 0 采用各种状态等价关系来对系统进行 约减。文 1 1 采用符号状态拆分( p r ) 算法生成最简稳定符号状态迁移图,但 该算法的执行效率有待改进并且其所生成的状态迁移图中仍存在冗余的抽象时 间延迟迁移。文 1 2 改进了p r 算法,提出了更加简单的不含抽象时间延迟迁移 的稳定符号状态迁移图,该方法去除了与测试无关的抽象时间延迟迁移。 目前在不同的形式化模型支持下已有许多用以测试实时系统的方法。这些 方法大致可分为三类:第一,方法是否使用包含时间约束的模型或者强调测试 系统级的实时性;第二,相关工作是否使用关于并发任务、共享资源和决定相 关输入的实时协议等信息;第三,相关工作是否提出了可与其方法一起使用的 测试准则。第一种方法通常是将实时系统模型转换为不含时间约束的系统模型, 从而消除时间约束对实时系统行为分析造成的影响,然后就可以使用时间无关 的测试方法进行测试。例如文献 1 2 将时间自动机转换为格自动机( g r i d a u t o m a t a ,g a ) ,并用w p - 方法来生成测试用例;文献 1 3 采用时间抽象互模拟 方法将时间自动机模型转换为有限状态迁移图,然后再将有限状态迁移图转换 为非确定f s m ,并采用基于f s m 的方法进行测试。第二种方法主要用来测试具 有并发任务系统的可调度性,目前这方面的研究还很少。t h a n e n 钔提出了在系统 启动运行之前获得实时系统执行次序的方法,随后p e t t e r s s o n 和t h a n e n 朝通过支 持共享资源扩展了该方法,但其中所有的任务响应时间都是固定的,r o b e r t n i l s s o n n 劬等使用启发式驱动模拟方法来产生基于变异的测试用例。第三种方法 是为了提高测试用例的测试充分性而提出相关的覆盖准则。例如k r i c h e n 和 t r i p a k i s n 7 1 提出了使用非确定和部分可观察模型进行一致性测试的方法,该方法 扩展了由h e s s e l 等n 8 3 提出的测试准则,测试用例描述允许与实现进行一些可能 的交互。 3 l 绪论 对实时系统的测试是一项非常困难和复杂的工作,以上所述方法各有优缺 点,针对不同的系统都有更适合它的测试用例生成方法,这有待于人们进一步 的研究与发现。目前基于模型的测试用例生成方法还处于理论研究阶段,并没 有大规模地应用于工程级的测试中,但我们相信该方法具有广阔的发展前景。 1 3 本文所做工作 本文对基于模型的测试用例自动生成方法进行了深入地学习、分析和研究, 在此过程中所做工作主要有以下几个方面: ( 1 ) 研究了基于模型的测试用例生成方法,尤其深入了解了基于时间自动 机模型的实时系统测试用例的自动生成方法。 ( 2 ) 研究了时间自动机及其扩展模型的形式化语法和语义,以及模型检测 的原理、方法和工具,并对模型检测中的状态空间爆炸问题及其解决方法进行 了分析。 ( 3 ) 实时系统中经常存在不同的时间尺度,针对这类系统,本文通过引入 一个加速技术来对原时间自动机模型的结构进行改进,从而加快模型检测的速 度,减少测试用例生成时间以及测试用例集的大小。 ( 4 ) 对于并发实时系统,响应时间可能依赖于不同任务的执行次序和执行 时间以及优先级约束和共享资源的分配等,本文在深入研究了基于变异的测试 方法的基础上,通过分析该类系统可能隐含的错误来定义各种变异操作符,以 此来模拟系统的各种错误,产生能够检测出这些错误的测试用例。 1 4 本文结构安排 本文共分五章: 第1 章主要介绍了基于模型的测试用例生成方法的研究背景和意义、国内 外研究现状及本文所研究的内容。 第2 章介绍了基于模型的测试用例生成方法的原理,各种常用的系统模型 和模型检测的方法原理及工具。 第3 章分析了对具有不同时间尺度的系统进行模型检测时产生的状态空间 分裂问题,然后介绍了一种模型检测的加速技术,并将该技术引入基于模型的 测试用例生成中,最后进行了实验验证及分析。 4 1 绪论 第4 章介绍了时间自动机模型的一种扩展模型和基于变异的测试方法,通 过分析具有实时任务和资源约束等的一类系统的特性,定义了模拟该类系统可 能出现的错误的各种变异操作符,最后进行了实验验证。 第5 章对全文的工作进行总结,并展望下一步工作。 5 2 基于模型的测试用例生成方法介绍 2 基于模型的测试用例生成方法介绍 2 1 软件测试模型 软件模型是对软件结构和软件行为的抽象描述。软件结构可以用部署图、 组件图等进行描述,软件行为则使用系统输入序列、条件、活动、输出逻辑等 进行描述。通过对软件的结构和功能进行适当层次的抽象并用易于理解的方式 进行描述,以此产生的模型可以作为软件的测试模型,它是对被测软件系统精 确的描述。通常对于不同的软件行为要用不同的系统模型来描述,如代码结构 间的行为关系可以用数据流图、控制流图和程序依赖图等来表示,软件外部行 为则可以用状态机和决策表来描述。基于模型的软件测试可根据软件结构模型 和软件行为模型生成测试用例。随着软件系统规模的日益庞大使得基于程序的 测试越来越困难,而基于模型的软件测试方法是一种自动化的软件测试技术, 它可以有效地提高软件测试效率,减少软件开发周期。另外,还有利于评价测 试结果,进行测试失效辨识。 针对被测试软件的不同特性以及不同的测试目的,目前已经提出了多种测 试模型,其中比较典型的软件测试模型主要有:有限状态机、基于时序逻辑的 模型、基于p e t r in e t 的模型、u m l 模型、马尔科夫链等模型。 ( 1 ) 有限状态机 使用有限状态机模型来进行测试的研究可以追溯到e f m o o r e 的早期研究: “顺序机的想象实验”。后来,它主要应用于对协议的一致性测试中。有限状态 机模型有成熟的理论基础,而且可以利用形式语言和自动机理论来进行设计和 分析,尤其适合用来描述反应式软件系统( r e a c t i v es y s t e m s ) ,是最常用的软件 描述和软件测试模型。有限状态机可以用状态迁移图或状态迁移矩阵表示,并 可根据迁移覆盖或状态覆盖生成测试用例。基于有限状态机的测试模型假设系 统在某个时刻总是处于某个状态,并且软件可能的输入由当前的状态决定,而 且当前的输入决定了软件从该状态向其它状态的迁移。基于有限状态机模型的 测试已经取得了一定的研究成果n9 舯| ,但对于复杂的软件系统,构造状态机模型 的工作量比较大,因此自动构造系统的有限状态机模型十分关键。基于有限状 态机的模型主要包括有限状态机( f s m ) 、扩展有限状态机( e f s m ) 、状态图 ( s t a t e c h a r t s ) 等,在实时领域主要有时间自动机及其变体。 6 2 基于模型的测试用例生成方法介绍 ( 2 ) 基于时序逻辑的模型 基于时序逻辑的模型用时间结构上的时序断言( 例如线性时序逻辑( l 1 乙) 、 计算树逻辑( c t l ) 等) 描述系统的行为,是一类基于历史的规范。实时系统可 以用相应的实时逻辑来规约,如时间命题时序逻辑( t p t l ) 、隐式实时逻辑 ( t r i o ) 2 13 等。 ( 3 ) 基于p e t r in e t 的模型 基于p e t r in e t 的模型用带t o k e n 的状态和迁移来表示并发系统。适用于实时 系统建模的变体主要包括时间p e t r in e t s 瞳引、e r n e t s 等。其中,位置、迁移、t o k e n 等可以和时间约束相关联。 ( 4 ) u m l 模型 统一建模语言( u m l ) 作为事实上的面向对象建模标准语言在面向对象开 发中得到了广泛的应用,出现了如r a t i o n a lr o s e 等大量的商品化支持工具。近 年来基于u m l 模型的测试也得到了广泛的关注与研究。基于u m l 模型的测试 研究主要集中于u m l 的状态图。状态图是有限状态机的扩展,它强调了对复杂 的实时系统进行建模,提供了层次状态机的框架和并发机制的描述,因此u m l 对单个类的行为建模时使用状态图。 ( 5 ) 马尔科夫链 马尔科夫链是一种以统计理论为基础的统计模型,在软件统计测试中得到 了广泛的应用。它实际上是一种具有概率迁移特征的有限状态机,可以根据状 态间的迁移概率自动生成测试用例并对测试结果进行分析,从而对软件的可靠 性指标和性能指标等进行度量1 。马尔科夫链可以用随机迁移矩阵或带迁移概 率的状态迁移图来表示。基于马尔科夫链的测试充分性准则通常要求测试中使 用与实际中相同的马尔科夫链迁移覆盖。另外,马尔科夫链模型还适用于对很 多种软件进行统计测试,而且迁移和状态覆盖的平均期望时间还可通过仿真得 到,有利于在大规模软件开发早期对软件系统进行费用和测试时间的规划。马 尔科夫链是统计测试的基本模型,在r a y t h e o n 、微软以及美国联邦航空署都得 到了深入的研究和成功的应用。 ( 6 ) 时间自动机 时间自动机是有限状态机的一种扩展模型。本文主要研究基于时间自动机 模型的测试用例生成方法,使用时间自动机来描述实时系统的抽象行为,以软 件系统的时间自动机模型作为测试生成模型。下面是时间自动机的形式化语法 7 2 基于模型的测试用例生成方法介绍 和语义及与之相关的一些概念瞳4 1 。 时钟约束痧的集合( i ) 0 0 由以下语法定义: 函:堍i c 鱼阵c i p q i 少l 八晚 其中,工是x 中的一个时钟,c 是非负有理数集q 中的一个常量。 时钟集合x 上的一个时钟解释v 为每个时钟赋一个实型值,也即它是从x 到非负实数集r 的一个映射。x 上的一个时钟解释v 满足x 上的一个时钟约束西 当且仅当根据v 给定的值西求值为真。对于6 r ,汁6 表示将每个时钟x 映射 到v 彤的时钟解释;对于yc x , v y = o 表示将每个x ey 赋值为0 ,并且在 其余的时钟上满足v 的x 上的时钟解释。 定义2 1( 时间自动机) 时间自动机可以表示为一个五元组乱,t o ,爿 p , 其中 ( 1 ) l 是一个有限的位置集; ( 2 ) l o e l 是起始位置; ( 3 ) 是一个有限的标记集; ( 4 ) x 是一个有限的时钟集; ( 5 ) ,是一个映射,即用( 中的某个时钟约束来标记每个位置,其中的 时钟约束称为位置不变式; ( 6 ) ec _ l z 2 x o ( 2 0 l 是一个迁移的集合。一个迁移勺,a ,痧l 芦 表示在 符号a 下从位置s 到位置s t 的迁移。西是x 上的一个时钟约束,指明迁移什么时 候可以发生,集合2 c x 给出在这次迁移中将被重置的时钟。 时间自动机彳的语义通过与它相关的状态迁移系统s 一来定义。& 的状态是 一个二元组o ,v ) ,其中s 是彳的一个位置,v 是x 上的满足不变式地) 的一个时 钟解释。如果s 是彳的初始位置并且对于所有的时钟变量x 都有啪= o ,则状态 o ,) 就是s 彳的初始状态。在s 彳中有两种类型的迁移: ( 1 ) 延迟迁移:对于一个状态( l d 和一个实值时间增量赴0 ,如果对于所有 的0 - 4 _ 锚,舢嘟满足不变式i ( 0 ,则( 厶v ) o ( 厶计回,所有的时钟同步增长; ( 2 ) 离散迁移:( 厶功- ( ,:1 ,阻:= 0 ) ,对应于边( 厶口,西l ,i ) 的迁移,其中v 满 足痧。 为便于模拟复杂的实时系统,下面是时间自动机乘积构造( p r o d u c t c o n s t r u c t i o n ) 的定义,根据定义可以用系统各个组件的乘积来模拟整个系统。 定义2 2 ( 乘积构造) 设a i = 和a 2 = 是两 8 2 基于模型的测试用例生成方法介绍 个时间自动机,且时钟集粥和恐是不相交的。那么,乘积么l i 陋2 是时间自动机 ,其中地l 芦2 ) 叫s 1 ) 八i ( s 2 ) r 迁移根据以下定义: ( 1 ) 对于a ) - l f l z 2 ,e 1 中每个 和岛中每个 , e 包含 。 ( 2 ) 对于a ey 1 z 2 ,e 1 中每个勺,a ,西l 芦 和最中每个t ,e 包含 。 ( 3 ) 对于a e ) - 2 y 1 ,e 2 中每个勺,a ,西l 芦 和e l 中每个t ,e 包含 。 时间自动机网络是一组时间自动机a 1 ,- - 4 n 的并行组合a 1 | | 1 口n ,可以通过 定义2 2 来构造时间自动机网络,其中每个时间自动机a 舢s f 鱼) 称为一个进程。 进程间的同步通信使用输入和输出动作以握手同步的方式进行,异步通信以共 享全局变量的方式进行。为了模拟进程间的握手同步,时间自动机中的标记集 中应包括以口? 表示的输入动作符号、以口! 表示的输出动作符号和由唯一符号r 表示的内部动作。时间自动机网络的状态是一个二元组 ,表示当前位置的 一个向量,u 表示记录各个时钟当前值的一个时钟赋值。时间自动机网络也有延 迟迁移和离散迁移两种类型的迁移。设厶表示位置向量,的第f 个元素, 2 :伽表 示用f 替换向量,中的厶,时间自动机网络中的迁移规则如下所示: ( 1 ) 延迟迁移: o ,如果u e l ( o 并且( “+ 回及d ,其中i ( 0 - - 八及厶) ( 2 ) 离散迁移: 与 如果厶屿f ;,u g ,u = 【r o 】u ,u i ( 1 1 i l i ) 一 ,如果存在i - j 使得 1 趾吗,;,0 坠! k 并且u 百八自,以及 2 2 【,j u r j 卜o u 并且u t i ( 1 1 ti l i 】 1 j l j ) 注意到,时间自动机网络是一个封闭的系统,它不执行任何的外部动作。 2 2 模型检测 模型检测的研究始于上世纪八十年代初,它是一种用于验证安全攸关并发 系统正确性的自动化技术。模型检测最早应用于硬件的性能检测中,随着通信 技术的不断发展,被逐渐应用于通信协议、安全认证协议、控制系统等方面的 9 2 基于模型的测试用例生成方法介绍 分析与验证中,取得了令人瞩目的成就, 开始研究软件模型检测、无限状态系统, 检测侧。 并从学术界转到了产业界。目前已经 以及与程序分析和软件测试相结合的 模型检测的基本思想瞳7 t 矧是通过状态空间的穷尽搜索来确认系统是否具有 某些性质,即给定一个系统描述s 和系统规约甲,生成等价于系统s 的模型m , 然后通过模型检测算法来证明规约甲在模型m 中成立,因系统s 和m 是等价 的,从而证明了系统s 满足规约甲。模型检测通常采用对状态空间进行穷举搜 索的方法来验证系统的某个性质,因此为保证使用模型检测方法时可以在有限 的时间内得到确定的结论,生成的系统模型必须是有穷的。 模型检测的主要优点是它的自动化程度很高,只需用有穷状态模型和逻辑 公式分别将系统实现和待验证的系统规范描述出来,之后的判断过程则完全可 以由模型检测工具自动完成,不需要人的参与。另外,如果系统实现不满足系 统规范,模型检测器还可以返回一个导致性质不满足的反例路径,供人们调试 使用。主要的不足之处是它在穷举搜索系统状态空间时易产生状态空间爆炸问 题,大大增加了系统穷举搜索所需的时间和空间开销,从而加大基于模型的测 试用例生成的难度。 目前已有多种技术可以用来减少状态空间爆炸造成的影响,例如,符号模 型检测、o n t h e f l y 技术、抽象( a b s t r a c t i o n ) 、偏序规约( p a r t i a lo r d e rr e d u c t i o n ) 、 等价( e q u i v a l e n c e ) 和模拟( s i m u l a t i o n ) 、组合推理( c o m p o s i t i o n a lr e a s o n i n g ) 、 对称( s y m m e t r y ) 和归纳( i n d u c t i o n ) 等,下面分别对这些技术进行简要介绍。 ( 1 ) 符号模型检测 符号模型检测是一种用逻辑公式隐式地表示系统的状态集合和迁移关系, 并在符号状态空间上进行搜索的技术汹1 。它使用b r y a n t 的o b d d s ( o r d e r e d b i n a r yd e c i s i o nd i a g r a m s ) 来表示逻辑公式,使得状态迁移关系表示比较紧凑, 从而降低系统模型所需的内存空间。符号化表示对于数字电路设计的建模十分 自然,而且由于它能够捕获电路设计确定的状态空间,因此能够对具有极大状 态空间的系统进行验证。模型检测工具s m v ( s y m b o l i cm o d e lv e r i f i e r ) 就是采 用符号模型检测技术设计的。 ( 2 ) o n t h e f l y 技术 o n t h e - f l y 技术使得在对时间自动机进行验证时,可以只在需要时生成系统 自动机的状态,避免为系统建立整个状态空间。它的优点是自动机中的一些状 1 0 2 基于模型的测试用例生成方法介绍 态可能永远也不会产生,并且反例可能在完成乘积自动机的创建之前就被找到, 不需要再生成剩余的部分。 ( 3 ) 抽象 抽象技术适用于具有复杂数据结构的反应式系统或与数据路径有关的电路 系统。抽象是解决状态空间爆炸问题的一种很重要也很有效的技术,有两种主 要的抽象技术:数据抽象和影响锥缩减口引。前者在系统的精确数据值和一个较 小的抽象数据值之间建立一个映射关系,并通过扩展转换和状态之间的映射来 生成一个比现实系统小得多的抽象系统。后者通过消除不影响规范的一些变量 状态来压缩状态空间,并通过验证得到的简化自动机模型的性质来降低模型检 测的复杂性。 ( 4 ) 偏序规约 对于并发系统,一次执行过程中所有事件的线性排列称为交叠序列。在交 叠模型下,对并发执行的n 个事件模型检测要搜索所有的n ! 种交叠,这可能会导 致状态空间的爆炸,而许多时态逻辑对同一组独立事件的不同交叠并不敏感( 即 在其上的真值是相同的) ,偏序技术通过避免对独立迁移之间不必要的交叠进行 搜索来减少模型检测时的状态数,该方法主要适用于异步系统。模型检测工具 s p i n 就是b e l l 实验室的g h o l z m a n n 等人用偏序规约等技术研制的。 ( 5 ) 等价和模拟 对于逻辑l 和结构m ,该方法通过互模拟等价关系和模拟关系找到一个更 小的结构m ,m t 与m 满足l 上相同的公式集,从而使状态数目显著减少。 ( 6 ) 组合推理 组合推理主要用于由多个并发进程组成的有穷状态系统中,通过将全局行 为的性质分解为若干个局部性质分别进行验证,若系统满足每个局部性质,而 所有局部性质的合取又相当于整个性质,则整个系统一定满足该性质。当组件 之间相互依赖时,需要在验证一个组件性质时假设其它组件的行为,并且这些 假设在后来其它组件的正确性被确立后必须抛弃掉,该策略即由a p n u e l i 提出 的假设保证推理。 ( 7 ) 对称 并发系统中经常包含对称的部分,这些对称能用来缩减系统状态空间,对 称采用置换图来定义系统状态空间上的一种等价关系o r b i t 关系,并通过等价 类划分来约减系统状态空间。由这种等价关系引出的商模型通常比原模型更小, 2 基于模型的测试用例生成方法介绍 而且与原模型互模拟等价,可用来验证原模型中表达为c t l 公式的任何性质。 ( 8 ) 归纳 归纳方法主要用于无限多个有穷状态系统的验证,因为有穷状态系统的无 穷族的状态集是无限的,所以可以被认为是状态空间爆炸问题。有穷状态系统 的无穷族的验证问题是不可判定的,但是对于特定的族还是可以解决的,最常 见的方法是对进程数目进行归纳。 目前存在很多描述和验证实时系统的工具,比如k r o n o s 、s m v 和u p p a a l 等。下面我们分别对以上工具做简要介绍: ( 1 ) k r o n o s 研发于v e r i m a g 的工具k r o n o s 支持通信时间自动机集合的分析。分析 的执行可以通过一个列举或符号程序来搜索带自动机实现。该工具支持对分支 实时时序逻辑t c t l 和各种过程代数符号界面如e t - l o t o s 的模型检测。额外 的启发思想包括各种状态空间约减的最小算法。 ( 2 ) s m v s m v 是由l m c m i l l a n 博士于1 9 9 2 年开发出的模型检测工具。s m v 程序由 有限状态迁移系统和c t l 公式两部分组成。运行s m v 程序后,若有限状态迁 移系统满足c t l 所描述的性质,则输出真,否则输出假并生成性质不被满足的 反例。s m v 是在符号状态空间上进行搜索的,在大多数情况下,符号化表示集 合比显示地表示更加紧凑。因此,s m v 能有效地缓解状态空间爆炸问题。 ( 3 ) u p p a a l u p p a a l 是由瑞典的u p p s a l a 大学与丹麦的a a l b o r g 大学联合研发的、用于 时间自动机建模、模拟和自动验证的工具集,已成功用于实时控制器和通信协 议的验证。本文使用的测试用例生成工具u p p a a lc o v
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2026年下半年大兴安岭地区事业单位公开招聘工作人员185人笔试备考题库与答案解析
- 【昌邑市中医院】公开招聘2026年度编外专业技术工作人员笔试备考题库与答案解析
- 化学与环境模板课件
- 2026湖南黄金集团地质勘探有限责任公司并购团队招聘4人笔试备考题库与答案解析
- 回校园的课件
- 化学选择题课件
- 2026年漆器工艺品制造行业前景分析报告及未来五至十年创新驱动与生态构建
- 2026年麻纤维纺前加工和纺纱行业趋势报告及未来五至十年新质生产力与高质量发展
- 黑猩猩来了课件
- 2026江苏扬州市邗江区招聘社区工作者8人考试参考试题及答案解析
- 煤矿测量新手培训课件
- 义工考核管理制度
- 言语治疗共鸣障碍课件
- 福建莆田市拔尖人才选拔考试六年级试卷及答案
- 电力行业技术服务合同
- JGJ52-2006 普通混凝土用砂、石质量及检验方法标准
- 四川省民族地区旅游产业发展综合规划
- 主题班会调整心态缓解压力省公开课一等奖全国示范课微课金奖课件
- 病毒基因组课件
- 中裕能源项目短视频运营方案
- 三年级英语课标解读课件
评论
0/150
提交评论