（交通信息工程及控制专业论文）测试用例自动生成算法在车载ATP中的研究与应用.pdf

中文摘要 摘要：为确保列车运行安全，提高运输效率并增强市场竞争力，铁路部门提出了 发展适于我国国情的c t c s ( c h i n e s et r a i nc o n t r o ls y s t e m ) 系统策略。目前关于 c t c s 一3 级列控系统的研究正在逐步进行和完善之中。作为一个安全苛求的铁路控 制系统，c t c s 必须要进行一系列完整功能的测试，以确保对系统的全面验证。功 能测试是确保系统安全最重要的部分，其目的在于验证系统是否满足需求规范。 作为整个列车的控制核心，车载子系统功能测试的重要性也就不言而喻。 测试是一项非常耗时的工程，恰当的测试方法可以提高测试效率。测试用例 是测试全部过程的核心，同时也是测试执行环节的基本依据。测试自动化的趋势 使得测试用例自动生成成为该领域的关键问题与难题之一。由于不同的测试数据 发现错误的能力存在很大差异，为了提高测试效率降低测试成本，应该选用高效 的测试数据。因此，本文主要针对c t c s 3 级车载a t p ( a u t o m a t i ct r a i np r o t e c t i o n ) 子系统的测试方法和测试用例自动生成展开研究。 本文首先从传统测试理论出发，分析了这些测试手段自身的优点与不足。由 于单纯的黑盒测试和白盒测试各自的不完备性，选用混合测试方法对两者进行优 势互补，并详细阐述了混合测试方法的原理和具体实施过程。选取混合测试方法 所体现出的逐步测试思路为测试用例的良好设计提供了基础。 其次，研究了混合测试方法下的测试用例自动生成技术。经验和实践表明， 两两组合覆盖测试是一种实际而有效的用例生成方法。所以本文结合测试领域组 合覆盖的思想，重点研究了基于网络模型两两覆盖的组合测试用例自动生成算法， 并就参数排序策略对该算法性能的影响进行了分析与评价，进而提出了相应的解 决措施。 最后，以c t c s 3 级车载a t p 子系统为研究对象，对其被测功能进行了需求 分析。基于车载a t p 速度监督功能的测试需求，在不同工作模式下对被测功能进 行了层次划分；在一定的参数选择及排序策略下，利用组合测试用例自动生成算 法完成了不同模式、层次的测试用例自动生成及约减，以及所生成用例的管理及 维护等。用例生成结果表明，在恰当的参数选取及排序策略下，本文所述测试用 例自动生成算法能够在保证测试覆盖率的同时具备较高的用例约减率，该方法将 对提高测试效率具有重要的积极意义。 关键词：c t c s 3 ；车载筒r p ；混合测试方法；组合测试；测试用例自动生成 分类号： u 2 8 4 9 1 a bs t r a c t a b s t r a c t ：i no r d e rt o g u a r a n t e et h es a f e t yo ft r a i no p e r a t i o n ，i m p r o v et h e t r a n s p o r t a t i o ne f f i c i e n c ya n dm a r k e tc o m p e t i t i v e n e s s ，t h es y s t e ms t r a t e g yo fc t c s ( c h i n e s et r a i nc o n t r o ls y s t e m ) i sp r o p o s e db yr a i l w a yd e p a r t m e n tb a s e do nt h e n a t i o n a ls i t u a t i o n s t h er e s e a r c ho nc t c s 一3i sg r a d u a l l yp e r f o r m e da n di m p r o v e d ，a n d 嬲as a f e t yc r i t i c a lr a i lc o n t r o ls y s t e m ，t h e r es h o u l db ec o m p l e t et e s tf o rc t c st oe n s u e t h ec o m p r e h e n s i v ev e r i f i c a t i o no ft h es y s t e m ，i nw h i c ht h ef u n c t i o n a lt e s ti st h em o s t i m p o r t a n tp a r tf o r t h es y s t e ms a f e t y , w i t ht h ea i ma tv e r i f y i n gw h e t h e rt h es y s t e mc o u l d m e e tt h es y s t e mr e q u i r e m e n ts p e c i f i c a t i o n s a n da st h ek e yp a r to ft r a i nc o n t r o l ，i ti so f g r e a ti m p o r t a n c ef o rt h ef u n c t i o nt e s to fo n b o a r ds u b s y s t e m t e s ti sat i m ec o n s u m i n gp r o j e c t ，a n da p p r o p r i a t et e s tm e t h o dw i l li m p r o v et h e e f f i c i e n c y t h et e s tc a s ei st h ec o r eo ft h ew h o l et e s t i n gp r o c e s s ，a n di s a l s ot h e f u n d a m e n t a lb a s i so ft h et e s te x e c u t i o n w i t ht h ed e v e l o p m e n to ft e s ta u t o m a t i o n ，t h e g e n e r a t i o no ft e s tc a s eh a sb e c o m eo n eo ft h ek e yp r o b l e m s t h ea b i l i t yo fd e t e c t i o nf o r e r r o r sw o u l dv a r yw i t ht e s t i n gd a t a , s oh i g he f f i c i e n tt e s t i n gd a t as h o u l db es e l e c t e dt o i m p r o v e t h ee f f i c i e n c ya n dr e d u c et h ec o s t t h ea i mo ft h i sp a p e ri st h et e s tm e t h o da n d t e s tc a s ea m o m a t i cg e n e r a t i o nf o ro n b o a r da t p ( a u t o m a t i ct r a i np r o t e c t i o n ) s u b s y s t e m i nc t c s 3 f i r s t l y , s t a r t i n gw i t ht h et r a d i t i o n a lt e s t i n gt h e o r y , t h ea d v a n t a g e sa n dd i s a d v a n t a g e s o ft h ee x i s t i n gt e s tm e t h o d sa r ea n a l y z e d a st h eb l a c k - b o xa n dw h i t e b o xt e s ta r e i n c o m p l e t e ，t h eh y b r i dt e s t ，i nw h i c ht h eb l a c k - b o xa n dw h i t e b o xa p p r o a c ha r e c o m b i n e d ，i sp r o p o s e dt ob ea l li m p r o v e m e n t ，a n dt h ep r i n c i p l ea n di m p l e m e n t i n g p r o c e s so fh y b r i dt e s ta r ed e t a i l e dd e s c r i b e d t h et h o u g h t so fh y b r i dt e s tp r o v i d eab a s i s f o rt h ed e s i g no ft e s tc a s e s e c o n d l y , t e s tc a s ea u t o m a t i cg e n e r a t i o ni nh y b r i dt e s ti sr e s e a r c h e d t h ep a i r w i s e c o v e r i n gt e s ti sa i le f f e c t i v ea p p r o a c hf o rt e s tc a s ea u t o m a t i cg e n e r a t i o n b a s e do nt h e c o n s i d e r a t i o no fc o m b i n e dc o v e t i n gi nt e s t ，t h ea l g o r i t h mo fp a i r w i s et e s tc a s e a u t o m a t i cg e n e r a t i n gb a s e do nt h en e tm o d e li sm a i n l ys t u d i e d ，t h ei n f l u e n c eo f p a r a m e t e rs o r t i n gi sa n a l y z e d ，a n dc o r r e s p o n d i n gs o l u t i o n sa l ep r e s e n t e d f i n a l l y , t a k et h eo n b o a r da t ps u b s y s t e mo fc t c s - 3a st h eo b j e c t ，t h et e s t i n g f u n c t i o nr e q u i r e m e n t sa r ea n a l y z e d b a s e do nt h et e s t i n gr e q u i r e m e n to fs p e e d s u p e r v i s i o nf u n c t i o ni no n b o a r da t ps u b s y s t e m ，t h eh i e r a r c h i c a ld i v i s i o no ft h et e s t i n g f u n c t i o n si sm a d ef o rd i f f e r e n to p e r a t i n gm o d e u n d e rc e r t a i np a r a m e t e rs e l e c t i n ga n d s o r t i n gs t r a t e g y , t h et e s tc a s ea u t o m a t i cg e n e r a t i o ni nd i f f e r e n tm o d ea n dh i e r a r c h yi s r e a l i z e db yt h ep r o p o s e da u t o m a t i cg e n e r a t i n ga l g o r i t h m ，a n da l s ot h er e d u c t i o na n d m a n a g e m e n to f t h et e s tc a s e s t h eg e n e r a t i n gr e s u l td e m o n s t r a t e st h a t ，w i t ha p p r o p r i a t e p a r a m e t e rs e l e c t i o na n ds o r t i n gs t r a t e g y , t h et e s tc a s ea u t o m a t i cg e n e r a t i o na l g o r i t h m e r i t i sah i g hc o v e r a g ea n dr e d u c t i o nr a t e ，a n dt h e r ew o u l db ei m p o r t a n ts i g n i f i c a n c ef o r t h et e s t i n ge f f i c i e n c y k e y w o r d s ：c t c s 一3 ；o n b o a r da t p ；h y b r i dt e s tm e t h o d ；c o m b i n a t o r i a lt e s t ；t e s tc a s e a u t o m a t i cg e n e r a t i o n c i a s s n o ：ij 2 8 4 9 1 v 图索引 图卜1c t c s - 3 级列控系统结构图7 图2 - 1 常见的测试方法1 0 图2 - 2 车载a t p 混合测试流图14 图2 - 3 混合测试方法流程图1 4 图2 - 4 被测功能层次划分图1 5 图2 - 5 测试用例生成方法1 7 图3 - i 组合覆盖原理结构图2 6 图3 - 2 算法流程图2 7 图3 - 3 算法顺序执行图2 9 图3 - 4 不同排序策略下的用例生成比较3 l 图3 - 5 改进后的算法执行图3 2 图4 - im r s p 的选择3 5 图4 - 2 目标距离模式下的速度监控曲线3 6 图4 - 3 速度监控功能划分3 8 图4 - 4 测试用例集结构3 9 图4 - 5 输入参数取值示意4 4 图4 - 6 程序功能结构图4 5 图4 - 7 组合测试用例生成过程示意图4 6 图4 8 基本用例集生成4 7 图4 - 9 覆盖率检查表4 8 图4 - 1 0 补充用例集4 8 图4 - i1 基本用例集生成图4 9 图4 - 1 2 覆盖率检查表4 9 图4 - 1 3 补充用例集5 0 图4 - 1 4 测试用例生成设置界面5 1 图4 15 用例生成软件界面5 2 图4 - 16 测试用例导出5 3 表索引 表2 - i 白盒测试和黑盒测试的对比分析1 3 表3 - i 单参数覆盖测试用例表2 2 表3 - 2 单参数组合覆盖测试用例表2 3 表3 - 3 测试用例集执行结果2 3 表3 - 4 单参数组合覆盖测试用例输出结果2 3 表3 - 5 二参数组合覆盖测试用例2 4 表3 - 6 二参数组合覆盖测试用例输出结果2 4 表3 7 遗漏项统计表2 8 表3 8 参数选择测试结果3 0 表4 - i 不同模式分类列表3 8 表4 - 2 输入变量列表4 0 表4 - 3f s 模式下的变量列表4 0 表4 - 4c o 模式下的变量列表4 l 表4 - 5o s 模式下的变量列表4 l 表4 - 6s h 模式下的变量列表4 2 表4 - 7s b 模式下的变量列表4 2 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的研 究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表或 撰写过的研究成果，也不包含为获得北京交通大学或其他教育机构的学位或证书 而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作 了明确的说明并表示了谢意。 学位做作者签名： 雷1 l 、拎 签字日期： 习年占月，g 日 学位论文版权使用授权书 本学位论文作者完全了解北京交通大学有关保留、使用学位论文的规定。特 授权北京交通大学可以将学位论文的全部或部分内容编入有关数据库进行检索， 并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校向国 家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：庸小 导师签名： 签字日期： 洲年6 月8 开 身防 答字嗍：1 “月i r 致谢 本论文的工作是在我的导师宁滨教授的亲切关怀和悉心指导下完成的。宁滨 老师严谨的治学态度和科学的工作方法给了我极大的帮助和影响，宁老师高屋建 瓴的学术眼光、兢兢业业的工作精神，为我树立了良好榜样。在宁老师的指导下， 我不仅学到了宽广的专业知识，更学到了做人的道理。两年来宁老师对我的谆谆 教导和悉心关怀都令我受益匪浅，在此向宁滨老师表达我最崇高的敬意和最衷心 的感谢! 在这里要特别感谢实验室的李开成老师，在平时的科研工作中李老师给予了 我很多的帮助与指导，在学习上和生活上也给予了我很大的关心和支持! 李老师 渊博的学识、孜孜不倦的科研精神都令我深受鼓舞。每当我遇到困难、碰到“瓶 颈”的时候，李老师都非常耐心地为我答疑解惑。课题的研究和论文的顺利完成， 离不开李老师的悉心指点。在此衷心感谢两年来李老师对我的关心与指导! 同时，感谢实验室唐涛教授在百忙之中对我的科研工作及毕业论文写作的关 怀与指导! 感谢课题组的马连川老师和袁磊老师，他们对于我的科研工作和论文 也提出了许多宝贵意见，对我耐心指导，开拓我的思路，鼓励我继续前进，衷心 感i 身 他们对我的指导和教诲! 在实验室工作及论文撰写期间，刘江、刘辉、任军、庞新胜等同学对我的研 究工作给予了热情帮助，在此向他们表达我的感激之情! 感谢我的舍友薛丽萍同 学以及好友李晓艳、杨韬、矫亮亮等同学一直以来的关心和帮助! 感谢同实验室 的王艺燕、张倩以及陈通同学，感谢他们使我度过了一段非常快乐的研究生学习 生活! 另外也要感谢我的家人，他们一直都是我的孥强后盾和精神支柱。我的每一 次挫折，都得到他们的理解与关怀，我的每一次进步，都离不开他们的支持与鼓 励! 在短暂的研究生学习期问，除了我自己的努力和付出之外，更多的是要感谢 轨道交通控制与安全国家重点实验室的所有老师和同学对我的帮助与支持! 本论文由国家自然科学基金项目“列车运行控制及组织的基础理论与关键技 术研究”( 项目号：6 0 6 3 4 0 1 0 ) 支持。 1 引言 1 1 综述 随着我国高速铁路发展建设的需要，国产高速铁路列车运行控制系统的研发 生产迫在眉睫。列车运行控制系统已经成为铁路信号系统的核心设备。高速列车 的安全运行，离不开性能先进、安全、可靠、高效的列车运行控制系统。2 0 0 2 年 中国铁路从跨越式发展的高度提出了发展适于我国国情的中国列车运行控制系统 ( c h i n e s et r a i nc o n t r o ls y s t e m ，以下简称c t c s ) ，研究并制定了c t c s 的总体框 架和技术规范。 铁道部已经明确要求在干线提速及新线中优先发展c t c s 系统，在对国外先 进技术进行消化吸收的基础上，实现引进设备的国产化。基于通信的e t c s 2 级 列控系统在欧洲的成功运营，也加快了中国基于无线通信的c t c s 3 级列控系统 的研制和实施步伐。我国3 0 0 k m h 及以上高速铁路将以c t c s 3 级列控设备作为控 制系统，应用到铁路提速建设中。 1 1 1 选题背景 配备性能先进、安全可靠的列车运行控制系统是确保列车运行安全和提高运 输效率的迫切需要。我国3 0 0 k m h 及以上高速客运专线确定将c t c s 3 级列控系统 作为全路统一技术平台体系，并兼容c t c s 2 级列控系统实现动车组上下线运行。 c t c s 3 级列控系统主要是在c t c s 2 级列控系统的基础上，通过集成e t c s 无线 控车的关键技术来构建相应的技术平台。 目前f 在进行之中的武广客运专线、广深港客运专线及郑西客运专线信号系 统均采用c t c s 一3 级列控系统。 为了确保列车运行安全，需要对c t c s 3 级列控系统丌展功能测试、子系统( 部 件) 的互连互通性验证、性能评价等工作，而其中有些工作无法或者非常难以在 铁路现场进行，有的工作在现场进行工程花费巨大。c t c s 3 级列控系统综合仿真 测试平台的建立，可以为系统的设计研究及设备集成提供良好的辅助设计、研发 平台、验证测试平台，便于进行c t c s 3 级列车运行控制系统的系统研究、方案比 较、设备测试评估等工作。在仿真测试平台中仿真功能只是其中一部份，该平台 的测试功能也同样重要。 c t c s 3 级列控系统仿真测试平台的建立，首先可以推进c t c s 3 级列控系统 的完善；其次仿真平台的建立可以对c t c s 3 级列控系统技术规范的建立提供多方 位的借鉴和补充，还可以推进c t c s 3 级列控系统在我国铁路中的实现进程。简而 言之，c t c s 3 级列控系统仿真测试平台的建立为今后c t c s 3 级列控系统标准技 术规范的建立以及日后c t c s 3 级标准系统的测试提供了宝贵的完善和借鉴意义。 1 1 2 选题目的 为了保证设备投入使用时的安全可靠，在使用前必定要进行一系列的测试以 验证其完成的功能以及故障一安全性。本文研究的是c t c s 3 级列控制系统中的核 心子系统车载a t p ( a u t o m a t i ct r a i np r o t e c t i o n ，也即列车超速防护) 设备的功能测 试。 目前国内c t c s 3 级列控系统仍处于研究阶段，技术尚未完全成熟。控制高速 列车的列控系统一旦失效所造成的后果将不堪设想，因此设备运行的稳定性、与 其他列控设备之间的互联互通性、遇到错误信息和故障情况的容错处理等，都需 要验证和加强，但目前国内针对这方面的测试和验证还存在很大的空白。车载a t p 设备作为列控系统的重要组成部分，对其各方面性能，尤其是互操作性和安全性 等进行测试，是非常重要的。 因此需要对c t c s 3 级列控车载a t p 设备的测试方法进行研究，并对相应的 测试工作展开更为深入的探索。 在采用计算机控制的系统，主要是依靠软件来实现系统的各种复杂功能。软 件测试正是发现问题的主要手段。而测试的首要问题是如何选择和生成测试用例， 以使测试尽可能有效地进行。对于测试用例的定义，i e e e6 1 0 1 2 标准测试用例的 定义如下i lj ： 测试用例( a ) 是一组输入即运行前提条件，和为某特定的目标而生成的预期 结果，例如：测试某一特定的程序路径或验证程序是否符合某特定需求； 测试用例( b ) 是一个文档，详细说明输入、期望输出，和为一测试项所准备 的一组执行条件。 i e e e6 1 0 1 2 标准的( a ) 是测试用例的实质，而( b ) 是测试用例的一种存在 形式。简单地说，测试用例应由测试输入数据和与之对应的预期输出结果两部分 组成，输入数据是测试用例的核心。 对于一个复杂的系统来说，对系统进行验证所需的测试用例规模庞大。成本 开销无疑也会随之加重。如果采取手工测试的方式，往往对测试人员所具备的知 识和经验有着极高的要求，再者，这种方式的测试效率和成本开销都很难满足实 2 际需求，而且用例设计也在很大程度上受制于测试人员的主观性影响。这样，对 一些开发成本原本就十分昂贵，且有着严格质量要求的高复杂度的安全软件而言， 对其进行手工测试就会使得质量往往难以得到保证。 可见，提高测试效率的一个重要途径就是尽可能地实现自动化测试。而测试 过程自动化中最为关键的技术之一是测试用例的自动生成，测试用例设计的好坏 将直接影响到测试工作的成功与否。用例自动生成的实现可以有效改变以往靠直 觉、凭经验的传统测试。因此，测试用例自动生成技术不仅能提高测试效率，降 低测试成本，而且对测试质量也能起到很好的保证作用。 1 1 3 研究意义 作为对安全要求非常严格的铁路控制系统，c t c s 必定要通过一系列的测试工 作，以确保对系统的全面验证评估。系统功能测试是确保系统安全最重要的部分， 功能测试的目的在于验证系统能否满足自身的需求规范。 车载子系统作为c t c s 3 级列控系统的重要组成部分，对其各方面性能尤其是 互操作性进行功能测试也就显得非常重要。车载设备的功能测试有助于及时发现 设备问题，改进设备性能。对即将投入使用的设备进行全面的测试，评估设备的 可用性、可靠性，从而确保行车安全和提高运输效率。 由于c t c s 3 级列控系统具有自主知识产权，且c t c s 的提出相对较晚，使得 在相关设备的测试评估等方面急需开展相关研究。虽然e t c s ( e u r o p e a nt r a i n c o n t r o ls y s t e m ，即欧洲列车运行控制系统) 发布了一些关于车载设备测试的可供 参考的规范，但是由于技术保密等方面的原因，许多核心的内容还需要深入研究 和自主研究。而国内对列控系统的测试工作刚刚起步，相关测试研究相对甚少。 对于列控系统的测试评估是设备正式投入运营前必不可少的重要环节，本课题的 研究旨在对c t c s 3 级列控系统的测试相关内容进行理论及方法的研究探讨，奠定 前期基础，从而加快c t c s 一3 级列控系统的测试研究步伐。 1 2 国内外现状 1 2 1列车运行控制系统测试 在列车运行控制系统的测试方面，国外铁路非常重视并进行了大量的研究。 2 0 0 4 年意大利佛罗伦斯大学曾为s c m t 开发出了一个基于仿真技术的 a t p a t c ( a u t o m a t i ct r a i nc o n t r 0 1 ) 测试系统，并称之为h i l ( h 锄蛔a r ei nt h el o o p ) 3 测试系统【2 1 。该系统提出了一种切实有效的解决办法来完成a t p 澳, , g 速设备的测试工 作，并极大地简化了设备的验证程序。该方法的优点在于无需测试人员的现场值 守。再者，由于测试环境的可控性和可重复性，使得能够对不同解决方案进行有 效对比。另外，这种仿真技术也使得对一些极端的测试环境的模拟变得简单可行。 g d en i c o l a t 3 】提出了一种基于白盒测试和黑盒测试的混合测试方法对安全关 键系统进行测试。这种方法主要是以被测系统的规格说明书为依据，将系统分割 为若干个相互独立的逻辑子单元。这种分割方法通过采集各个逻辑模块的实际输 出，达到对系统逐步测试的目的。其优点在于在测试过程中能够实现对故障的快 速定位与诊断，验证系统的j 下确性。 p d it o m m a s o 【4 j 针对e t c s 的地面关键设备r b c ( r a d i ob l o c kc e n t e r ) 的安全 性测试展开了一定研究。主要是通过仿真手段来提供列车与r b c 之间数据通信异 常情况下的测试案例，从而完成对来r b c 系统安全性的验证工作。 西班牙c e d e xl i f 实验室借助仿真测试方法建立了e u r o c a b 测试平台，并开 发了一些测试工具，实现了测试序列的定义、生成和查看以及测试管理和测试结 果分析评估等功能。 e r t m su n i s i g 工作组对e t c s 车载设备的测试工作发布了较为详细的文档。 如文献 5 】至文献【7 主要包括：如何从系统的需求规范s r s ( s y s t e mr e q u i r e m n e t s s p e c i f i c a t i o n ) 中提取系统特征；测试案例的设计原则与方法；如何由测试案例构 成测试子序列，再由测试子序列构成测试序列等内容。 但是，国内对列控系统的测试研究却相对甚少。最主要的是上海同济大学针 对微机联锁软件的测试评估方面展开了一系列研究与实践，并完成了微机联锁软 件测试评估平台的成功建设等相关工作【8 】。另外文献【9 】中对c t c s 2 级列控系统的 应答器报文测试用例自动生成进行了研究，但该文献主要是以站场图的拓扑结构 为依据进行数据搜索来实现用例自动生成，缺乏一定的通用性。 c t c s 3 级列控系统是在引进、消化和吸收欧洲e t c s 列控系统技术体系、技 术标准和成熟产品的基础上，结合我国铁路运输的实际状况并做出了相应改进的 具有完全自主知识产权的高可靠、高安全列控系统。当前对c t c s 3 级列控技术的 研究工作f 在有序进行之中，但相关设备的测试评估尚待深入研究。 1 2 2 测试用例自动生成技术 测试的实质是根据系统的规格说明或内部结构选取一批测试数据，形成测试 用例。可见，在测试工作中，测试用例的设计与生成是最为重要的环节。 全面测试需要大量的测试用例，单纯的手动生成方式往往十分困难。因此测 4 试用例的自动生成便成为自动化测试中的一个重要问题。由于期望结果构造的困 难性，所以一般说到测试用例生成时都侧重于仅生成输入数据 1 0 l ( 注：本文也基 于这一约定说法) 。 所以，更进一步地讲，测试数据生成是测试的核心与关键。即如何从大量的 输入数据中选择具有代表性的典型、适量的数据，特别是如何选用优化的测试集 合来提高测试效率。为此，探讨如何生成高效的测试数据，有着很重要的意义。 测试一般大体可分为功能测试和结构测试，由于本文研究的是功能测试，所 以对于结构测试的用例生成技术的研究现状在此不作讨论。 功能测试中的用例设计，只考虑系统的功能实现，并不关注系统的内部结构 和实现细节。关于功能测试测试数据生成的主要研究成果如下： t s a i 提出的从关系代数查询表示的规格说明中自动生成测试用例的方法，该方 法适合于数据库和数据处理系统【l 。 w e y u k e r 提出的基于布尔规格说明的测试数据生成方法，该方法将l o v e s n o 的 基于控制的形式化规格说明方法进行了改进，用a n d o r 表对规格说明书中的条 件进行描述，比较适合于过程控制系统【l 2 1 。 h a l l 提出利用z 规格说明进行软件测试数据生成的方法，该方法要求测试人 员具有丰富的测试经验和较高的专业水平【1 3 j 。 兰毓华在h a l l 的研究基础上提出了基于z 规格说明的软件测试用例自动生成 方法，该方法在自动生成测试之前，必须先将软件需求规格说明用z 语言进行形 式化描述【j 制。 尽管形式化方法在用例生成技术上取得了很多研究成果，但由于纯形式化的 东西理解困难，且缺乏基于形式化语言的测试准则的描述及相应的支持工具等， 使得形式化的应用实现受到很大限制。 形式化描述在系统规格说明的描述过程中所遇到的困难，使得人们把目光逐 渐转移到了接口测试方面。 比较简单的是基于接口参数的黑盒测试用例选择方法。该方法对系统中的各 个接口参数采用等价类划分和边界值法进行相关处理后得到一组典型取值，接着 对这些取值组合进行随机选取，或者是采用启发式方法进行选取。 组合覆盖作为一种基于接口参数测试的重要方法，充分考虑了系统中各种因 素以及其相互作用会产生的可能情况，这样就可以依据实际需要去设计测试用例。 从而达到用较少的测试用例去尽可能多地覆盖一些影响系统的因素。实践表明， 这些不完全测试的结果能够反映出完全测试的内在规律，具有较好的代表性。 组合覆盖方法按照其覆盖程度的不同可以分为单参数覆盖，两两组合覆盖， 以及三三组合覆盖等。但是，随着系统复杂特性的增加，如果片面地追求高覆盖 程度，由此产生的测试用例数量无疑会急剧膨胀。所以，对于组合覆盖测试用例 生成技术的研究，人们重点关注的是两两组合覆盖法。两两组合覆盖作为一种科 学有效且非常实用的测试方法，其相应的测试数据生成算法成为人们研究一直研 究和关注的重点问题。 美国贝尔实验室的d m c o h e n 与s r d a l a i 等提出了一种基于两两组合覆盖的 测试数据启发式生成方法，开发了相应的测试用例自动生成工具a e t g ，并且申请 了专利【1 5 17 1 。 l c i 等人提出了一种基于参数顺序的渐进扩充的两两组合覆盖测试数据生成的 贪心算法，并开发了相应的测试用例自动生成工具p a i r t e s t t 墙j 9 1 。 k o b a y a s h i 等人提出了一种代数方法，作为启发式方法的补充，该方法在某些 情况下的效果要优于启发式方法和贪心算法【2 0 】。 w i l l i a m s 也给出了一种以j 下交拉丁方算法为基础的代数算法并进行了算法实 现，该算法能有效生成测试用例【2 1 1 。 s c h r o e d e r 等人提出了一种利用系统输入输出关系等附加信息的方法，对组合 覆盖测试数据进行有效约简【2 2 1 。该方法可以在不降低错误检测能力的前提下，对 测试数据集进行约简。但是，获取附加信息本身需要一定的开销成本，所以这种 方法有时还不如直接使用组合覆盖测试方法更为简单高效。 东南大学聂长海等人，在前人已有研究成果的基础上，对多种算法做出了相 应改进，所生成的测试数据与同类工具相比具有一定的特点和优势【2 3 - 2 4 , 3 0 , 3 2 1 。 总的来说，由于两两组合覆盖测试数据生成问题是一个n p 问题，因此关于这 个问题的求解方法只能利用启发式方法、贪心算法等进行近似求解，而且解决这 个问题的各种方法具有不同的优缺点。由于测试技术的研究尚未达到成熟的阶段， 加之测试质量要求的r 益严格，使得在该领域丌展更多的深入研究和应用非常必 要。 1 3c t c s 3 级列控系统 1 3 1c t c s 3 级列控系统概述 作为中国列车控制系统( c t c s ) 的重要组成部分之一，c t c s 3 级列控系统 采用g s m - r ( g l o b a ls y s t e mf o rm o b i l ec o m m u n i c a t i o n sf o rr a i l w a y ) 无线通信系 统实现地面列车问信息的连续、双向传输。c t c s 3 级列控系统结构图如图1 1 所示【2 5 1 。 6 ：! ：! 竺 c t c s 车载设备 图卜1c t c s 一3 级列控系统结构图 f i g u r e1 - 1s y s t e ma r c h i t e c t u r eo fc t c s - 3 c t c s 3 级列控系统采用固定闭塞方式的列车间隔控制和目标距离模式控制 ( d i s t a n c e t o g o ) 方式的速度控制。轨道电路仅用于列车占用检查和列车完整性检 查；固定应答器提供测距修j 下的定位基准及运行方向等信息；r b c 根据固定闭塞 信息及进路信息产生行车许可并通过g s m r 网络传送给车载设备，其它与列车运 行控制系统有关的信息如临时限速及线路参数等也通过无线通信系统传输到车载 设备。 1 3 2c t c s 3 级列控系统车载设备及相关测试内容 在c t c s 3 级列车运行控制系统中，车载设备主要接收来自r b c 、应答器、 7 轨道电路( 降级时) 以及司机控制台的控制指令，监督并控制列车的安全运行： 接收机车的速度传感器信息，计算列车的速度和位置，并根据r b c 的m a ( m o v e m e n t a u t h o r i t y ) 信息，计算动态速度曲线，当列车超速时实施制动，从而 确保列车安全。 车载设备主要功能包括： 确定来自于轨道描述的可允许的等级； 处理司机输入的c t c s 等级； 最严格速度曲线的计算； 目标距离模式曲线的实时计算； 向地面系统发送列车运行的动态信息； 速度比较和控制干预，本功能用于监督比较当前速度和列车位置，并且采 取适当的措施； 对于车载设备的研究目前正处于测试阶段。实验室测试主要是采用真实设备 和模拟设备相结合的方式，以功能测试为重点。对c t c s 3 级列控系统车载设备的 功能测试和验证内容如下【2 6 l 。 ( 1 ) 车载设备基本功能测试。包括：t c r ( t r a c kc i r c u i tr e a d e r ) 等各子功能 模块功能测试、制动功能测试、列车溜逸防护功能测试、车尾保持功能 测试等。 ( 2 ) 车载设备工作模式功能测试。包括：完全监控等各个工作模式下的功能 测试以及模式转换功能测试、等级转换功能测试等。 ( 3 ) 车载设备模式监控曲线测试。包括：区间追踪运行、正线接发列车、侧 线接发行车、临时限速等条件下速度监控曲线的功能测试。 ( 4 ) 故障条件模式测试。包括：模拟在轨道电路故障、应答器丢失、列车空 转打滑、车载主机切换等故障条件下的车载设备功能测试等。 1 4 本文主要内容和组织结构 本文主要针对c t c s 3 级列控系统车载a t p 设备的测试用例自动生成技术展开 研究。 首先简要介绍了本文的研究背景、意义以及c t c s 3 级列控系统和车载设备的 相关知识；接着阐述了混合测试方法的基本思想及实施过程，再结合测试领域组 合覆盖的思想，重点研究了基于网络模型两两覆盖的组合测试用例自动生成算法； 并就参数排序策略对该算法性能的影响进行了分析与评价，进而提出了相应的解 决措施：最后对组合测试用例自动生成技术在c t c s 3 级列控系统车载设备功能测 试中进行了研究、实现与总结。 本文结构安排如下： 第一章：引言。简单介绍了论文的研究背景、目的及意义，并就研究对象 的相关技术作了简明必要的阐述。 第二章：车载a t p 测试方法的选取。介绍了黑盒测试和白盒测试的相关理 论，并分析总结了两者的优势和不足，进而提出采用混合测试方法。并针 对混合测试方法的具体实施过程做了进一步研究，就用例规模问题提出了 用例自动生成及用例约减的必要性。 第三章：组合测试用例自动生成算法的研究。基于上文选取的混合测试方 法，结合实际测试需求特性，重点研究了基于网络模型的组合测试用例自 动生成算法，分析了参数排序策略对该算法性能的影响，提出了相应的解 决措施。 第四章：组合用例自动生成算法在车载a t p 功能测试中的应用。详细有序 地完成了混合测试方法和改进的组合测试用例自动生成算法在c t c s 3 级 列控系统车载a t p 中的应用设计与实现，并就用例生成结果对本文所述方 法在约减及对测试的意义进行了总结。 第五章：结论和展望。对论文工作进行总结，并提出进一步研究工作的展 望。 1 5 本章小结 本章首先对当前我国铁路信号系统的发展需求及现状进行了介绍。在此基础 上，指出了针对c t c s 3 级车载设备进行功能测试的重要性。由于测试用例是整个 测试活动的核心与关键问题，由此提出了本文的研究重点，即以c t c s 3 级车载a t p 子系统为研究对象，展开测试用例自动生成技术在车载a t p 测试中的研究与应用。 最后简要阐述了c t c s 3 级列控系统及其车载子系统的结构组成以及测试内容等相 关内容，并介绍了本文的主要研究内容及论文组织结构。 9 2 车载a t p 测试方法的选取 随着系统规模的增加，使得测试的重要性与复杂性也随之增加。探求更贴合 实际测试需求的测试方法也就显得十分必要。 常见的测试方法及其分类如下图2 一l 所示。其中，从被测系统是否需要被执 行的角度出发，可以划分为静态测试和动态测试这两类。黑盒测试和白盒测试均 属于动态测试的范畴。如果测试工作针对的是被测系统的实际功能，则属于黑盒 测试范畴，倘若是针对系统的内部结构进行测试，则称为白盒测试。本文主要是 针对动态测试展开后续研究，所以下文仅就黑盒测试和白盒测试做简要阐述。 2 1 黑盒测试