（控制科学与工程专业论文）车站站场图逻辑语义解析及基本联锁数据生成算法研究和实现.pdf

摘要 摘要 软件测试是保证软件质量的关键步骤。测试有效性取决于测试数据的正确 性。本文以铁路车站计算机联锁软件测试评估平台的优化为背景，研究了站场 图逻辑语义解析及基本联锁数据生成算法，并应用到平台子系统站场c a d 拼贴 及数据校验中，以确保此子系统生成的测试数据正确、充分。 论文介绍了拼贴站场图的单元图库、站场图结构，定义了站场图逻辑语义， 阐述了站场图构成规则的知识表示及规则库的建立，提出了运用规则库进行逻 辑语义解析的算法，即在遍历站场图的过程中，由单元图类别匹配相应规则， 进行逻辑语义解析。涉及进路上各单元图间逻辑语义解析时，采用深度优先图 搜索算法搜索进路。论文对进路搜索算法也有详细的论述。逻辑语义解析过程 中，输出站场图中的错误类别及其位置信息，提示修改。此过程保证了站场图数 据的正确性，生成的进路信息作为测试用基本联锁数据存于牛1 0 k 文件中。作为 实际应用研究，文中介绍了站场c a d 拼贴及数据校验子系统的程序设计、功能 实现，并详细阐述了其中站场图逻辑语义解析及基本联锁数据生成的程序实现。 关键词：软件测试，计算机联锁，逻辑语义，算法，图搜索 a b s t r a c t s o f t w a r et e s t i n gi st h ek e ys t e pt oa s s u r es o f t w a r eq u a l i t y c o r r e c t n e s so ft h e d a t ai sv e r yi m p o r t a n tt ov a l i ds o f l w v a _ r et e s t i n g u n d e rt h er e s ( 地r c hb a c k g r o u n do f o p t i m i z a t i o nf o rc o m p m 盯i n t e r l o c k i n gs o f t w a r et e s t i n ga n da s s e s s m e n tp l a t f o r m 口& | a p ) ，l o g i cs e m a n t i c sa n a l y s i sa n d b a s i ci n t e r l o c k i n gd a t ag e n e r a t o ra l g o r i t h mf o r r a i l w a ys t a t i o nl a y o u t sf r s l ) i sp r o p o s e di nt h i s 耻孵；a n dt h ea l g o r i t h m i s i m p l e m e n t e d i nr s lc a da n dd a t ag e n e r a t o rs u b s y s t e mt oa s s u r et h ec o r r e c 艟l e s $ a n d s u m c i e n c yo f t a s t i n g d a t a a f t e ru n i tg r a p k c sl i b r a r ya n ds t r u c t u r eo fr s la r ei n t r o d u c e d ，l o g i cs e m a n t i c s f o rr s li sd e f i n e d t h e nk n o w l e d g er e p r e s a n 姐f i o no fr s lc o m p o s i n gr u l e si s e x p a t i a t e da n d r u l e sl i b r a r yi sc o n s t r u c t e d a n da l o g i cs e m a n t i c sa n a l y s i sa l g o r i t h m b a s e d0 1 1r u l e sl i b r a r yi sp r o p o s e d ，w h i c hm a t c h e sc o r r e s p o n d i n gr u l e sa c c o r d i n gt o t y p eo f u n i tg r a p h i c si np r o c e s so f s e a r c h i n gr s l i f l o g i cs e m a n t i c st h a ti sr d a t i v et o r o u t e si sa n a l y z e d , r o u t e ss h o u l db es e a r c h e db a s e do n d e p t h - f i r s tg r a p h s e a r c hf i r s t l y a n dr o u t e ss e a r c h i n ga l g o r i t h mi sp r o p o s e di nt h i sp a p e r r s le r r o r sa n dp o s i t i o n i n f o r m a t i o na t er e c o r d e da n ds h o w e di no r d e rt om o d i 母r s l c o r r e c t n e s so fr s l d a t ai sa s s u r e d ，a n dm u t e sd a t aw h i c ha r es e a r c h e di nt h i sp r o c e s sa r es a v e di nf i l e n a m e d + 1 0 k r o u t e sd a t a 础b a s i c i n t e r l o c k i n gd a t af o rt e s t i n g a si na p p l i c a t i o n , t h e & s i g no fr s lc a d a n dd a t ag e n e r a t o r s u b s y s t e mi se x p a t i a t e d , e s p e c i a l l yt h e i m p l e m e n t a t i o no fl o g i cs e m a n t i c sa n a l y s i sf o rr s la n db a s i ci n t e r l o c k i n gd a t a g e n e r a t o ra l g o r i t h m k e yw o r d s ： s o a r e t e s t i n g ，c o m p u t e ri n t e r l o c k i n g ，l o g i cs e m a n t i c s ， a l g o r i t h m ，g r a p h s e a r c h i i 学位论文版权使用授权书 本人完全了解同济大学关于收集、保存、使用学位论文的规定， 同意如下各项内容：按照学校要求提交学位论文的印刷本和电子版 本；学校有权保存学位论文的印刷本和电子版，并采用影印、缩印、 扫描、数字化或其它手段保存论文；学校有权提供目录检索以及提供 本学位论文全文或者部分的阅览服务；学校有权按有关规定向国家有 关部门或者机构送交论文的复印件和电子版；在不以赢利为目的的前 提下，学校可以适当复制论文的部分或全部内容用于学术活动。 学位论文作者签名：脊车燕 w 毋年月日 经指导教师同意，本学位论文属于保密，在年解密后适用 本授权书。 指导教师签名：学位论文作者签名： 年月日年月日 同济大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行 研究工作所取得的成果。除文中已经注明引用的内容外，本学位论文 的研究成果不包含任何他人创作的、已公开发表或者没有公开发表的 作品的内容。对本论文所涉及的研究工作做出贡献的其他个人和集 体，均已在文中以明确方式标明。本学位论文原创性声明的法律责任 由本人承担。 签名：济辜出 五竹年；月t t - 日 第l 章绪论 1 1 研究背景 第1 章绪论 计算机联锁系统是以计算机为主要技术手段实现车站联锁的强实时性逻辑 运算、安全控制系统，该系统直接控制着整个铁路车站内的信号设备、保证车 站行车安全、提高运输效率以及满足各种站场规模和运输作业的需要。其中作 为联锁系统核心的联锁控制软件是一类安全性完善度等级为4 级( 最高等级) 的安全软件( 吴芳美，2 0 0 1 ) ，其可靠性、安全性至关重要。但是其中的联锁软 件，一方面由于其不透明性而无法预见可能存在的缺陷，另一方面由于开通试 验时运输停顿的时间限制，无法充分地测试其性能。因此在联锁软件正式投入 运行之前对其进行完备( 穷举) 测试很有必要。 联锁软件的开发者、测试者和用户对待软件测试评估的主观意愿是不同的。 开发者主观上往往希望在测试时软件没有错误；用户则希望找出尽可能多的错 误和那些被认为是隐患的问题以排除后患。因此，联锁软件的测试和评估需要 由独立于开发者和用户的专门人员使用规定的标准、方法及工具来进行第三方 测试，并在测试的基础上对联锁软件给出公正客观的评估。 独立于开发方的第三方测试方在对软件进行安全性测试时常会受到许多条 件限制，一个是知识产权保护的问题，另一个是通用性问题，即需要面对不同 制式和版本的被测软件。在这些限制下，采用“黑箱”测试( b l a c k b o xt e s t i n g ) 的方法是可行的，包括功能测试、数据驱动测试或基于规格说明的测试 ( s p e c i f i c a t i o n b a s e dt e s t i n g ) ( 周苏，1 9 9 2 ) 。用这种方法进行测试时，可 以不考虑软件内部结构的情况，测试方只要知道该软件输入和输出之间的关系， 看它的输入能否被正确地接受，并正确地输出结果，即是否满足功能需求。 正是在这样的背景下，研究室成功研制了铁路车站计算机联锁软件测试评 估平台( c o m p u t e ri n t e r l o c k i n gs o f t w a r et e s t i n ga n da s s e s s m e n tp l a t f o r m 。 简称t & a p ) 。t & a p 是一个融入现代计算机仿真技术、网络通信技术、数据库技 术、可视化技术和软件自动测试等新技术的分布式软件测试评估工具，通过对 软件自动测试和手工测试完成联锁软件的安全性测试评估。 第l 章绪论 t & a p 系统中，测试数据生成是基础。t & a p 对测试用数据具有严格的证确性、 完备性要求，因为测试用数据的差错会直接导致测试结果的错误判断、测试中 断或平台系统瘫痪。测试数据是在站场图的基础上自动生成的，因此，站场图 数据的正确性是测试数据正确的根本所在。铁路车站站场图逻辑语义解析及基 本联锁数据生成算法就是为了更好地保证站场数据正确性而提出的。为了实现 站场数据正确性的自动检查，首先要研究的问题就是站场图逻辑语义、站场图 构成规则的知识表示，便于计算机识别和应用。 1 2 逻辑语义的研究概况 语义是反映人类的思维过程和客观实际的，可以简单地看作是按照各种表 示方法所表示的数据( 符号) 所代表的概念的含义，以及这些含义之间的关系， 是对数据的抽象或者更高层次的逻辑表示。对于计算机领域来说，语义一般是 指用户对于那些用来描述现实世界的计算机表示的解释，即用户用来联系计算 机表示和现实世界的途径。在自然语言理解和机器翻译中，语义分析的目的是 根据上下文辨识一个多义词在指定句子中的确切意义，然后根据该句子的句法 结构和该词的语义推导出这个句子的句义，并用形式化的方式表达出来，从而 使计算机能够根据这一表示进行推理。逻辑语义( l o g i cs e m a n t i c s ) 是一种语 义关系，是对语言中各种语义关系的高度抽象。客观世界中存在的各种事物、 动作、现象等都存在着一定的逻辑关系，这种关系是客观的，是高度抽象概括 的。在特定的交际环境下，某一语言片断( 通常指句子) 的各个基本单元之间 也必然存在着某种逻辑关系，这些逻辑关系就称为逻辑语义( 董振东，1 9 8 0 ) 。 逻辑语义是主要的语义分析技术之一。 在日常生活和工作中，有大量信息是用图的形式来表现的。相应地，也会 有图的语义理解，图中各元素间的语义关系即逻辑语义。目前，在有关计算机 对图的语义理解方面所作的研究工作还存在着一定的局限性。c a r l oc o l o m o 提 出了一种提高图的表示层次的合成方法，这种方法被用于提取图的表示层次的 内容并应用到可视信息检索系统( c a r l oc o l o m o ，1 9 9 9 ) 。根据这种方法，视觉 信息依据一定的规则被分类，这些规则反映了特定的上下文语义。然而定义这 些规则是比较困难的，这些规则应从特定应用域的特性中归纳出来，并且要采 用合适的知识表达方法形式化，以便被计算机易于理解和应用。 第l 章绪论 1 3 知识工程的发展概况 知识工程的概念出现于1 9 7 7 年，已成为一门新兴的边缘学科。知识工程是 人工智能在知识信息处理方面的发展，它研究如何由计算机表示知识，进行问 题的自动求解。其目标就是探索关于知识的获取( 包括学习) 、知识表示、保存 ( 记忆) 、交换( 变换) 、运用( 包括检索、推理及其它各种形式的加工) 的理 论、方法及实现技术( 童颓，1 9 9 2 ) 。知识工程的发展从时间上划分大体上经历 了3 个时期( 陆汝钤，2 0 0 1 ) ： 1 大约从1 9 6 5 至1 9 7 4 年为实验性系统时期。1 9 6 5 年费哥巴姆教授与其它 科学家合作，研制出d e n d r a l 专家系统。这是一种推断分子结构的计算机程序， 该系统贮存有非常丰富的化学知识，它所解决问题的能力达到专家水平，甚至 在某些方面超过同行专家的能力，其中包括它的设计者。d e n d r a l 系统标志着 “专家系统”的诞生。 2 从1 9 7 5 至1 9 8 0 年为m y c i n 时期。7 0 年代中期m y c i n 专家系统研制成功， 这是一种用医学诊断与治疗感染性疾病计算机程序的“专家系统”。m y c i n 专家 系统是规范性计算机专家系统的代表，许多其它专家系统都是在m y c i n 专家系 统的基础上研制而成的。m y c i n 系统不但具有较高的性能，而且具有解释功能和 知识获取功能，可以用英语与用户对话，回答用户提出的问题，还可以在专家 指导下学习医疗知识，该系统还使用了知识库的概念和不精确推理技术。m y c i n 系统对计算机专家系统的理论和实践，都有较大的贡献。 3 1 9 8 0 年以来为知识工程的“产品”在产业部门开始应用的时期。知识工 程的研究，目前在美国开展得较为活跃和深入，并且主要集中在斯坦福大学。 知识工程的主要研究领域有：软计算、主题a g e n t 、自然语言理解与机器翻 译、逻辑与推理、形象思维研究、基于事例的推理、机器学习以及知识本体论 等。 知识表示作为知识工程的一个重要内容，主要研究知识的形式化表达方法、 表示与控制的关系，表示与推理的关系及知识表示与其它研究领域的关系，其 目的在于通过知识的有效表达，使人工智能程序能利用这些知识作出决策、制 定计划、识别对象和状态、分析景物和获取结论等( 姚玉川，1 9 8 8 ) 。 对知识表示的要求主要有： 表示能力：能正确地、有效地将问题求解所需的各类知识表示出来。 第1 章绪论 可理解性：所表示的知识应易读、易懂、便于知识获取、知识库的检查修 改及维护。 可访问性：能有效地利用知识库中的知识。 可扩充性：能方便地扩充知识库。 此外还有相容性、正确性、简洁性等等。 在人工智能发展初期，知识表示作为人工智能的分支，如自然语言理解中 的特定问题求解。知识表示研究可追溯到2 0 世纪6 0 年代麻省理工大学和卡内 基梅隆大学的问题求解和语义网络的研究工作。7 0 年代，随着人工智能的发展， 知识表示推广迅速。到了8 0 年代，四个主流的知识表示框架已经形成：( 1 ) 语 义网络；( 2 ) 框架；( 3 ) 产生式系统；( 4 ) 谓词逻辑。此外，还提出了许多非 规范逻辑，如模糊逻辑( f u z z yl o g i c ) 、时态逻辑( t e m p o r a ll o g i c ) 、模态逻辑 ( m o d a ll o g i c ) 、高阶逻辑( h i g e r o r d e rl o g i c ) 、内省逻辑( i n t r o s p e c t i o n l o g i c ) 以及其它各种非单调逻辑。一阶谓词逻辑是一种高度形式化的语言系统， 研究的是假设与结论之间的蕴涵关系。由于它精确、无二义性，容易被计算机 所理解和操作，同时又与自然语言相似，故可以用来表示人类的某些知识。作 为一种知识表示的方法，一阶谓词逻辑系统体现出了严密性、精确性和可解释 性等诸多优越性，使得它成为人工智能领域应用较早、较广泛，也是较成功的 一种知识表示模式( 赵卵生，2 0 0 1 ) 。 在所有的知识工程中，知识表示的重要性是不言而喻的。因为一方面获取 的知识必须表示成某种形式，否则就无法记录知识；另一方面没有表示也就谈 不上运用知识，而表示的好坏直接影响着运用它的系统的质量( 赵瑞清，1 9 9 1 ) 。 知识运用也是知识工程的重要研究内容，主要包括： 推理：各种推理方法与模式的研究，研究前提与结论之间的各种逻辑关系 和其置信度的传递规则等。 搜索：各种搜索方式与方法的研究，研究如何从一个浩瀚的对象( 包括知 识本身) 空间中搜索满足给定条件或要求的特定对象。 管理及维护：对知识库的各种操作，例如，检索、增加、修改和删除，以 及保证知识库中知识的一致性和完整性约束等。 匹配：指在数据库中或其它对象库中，找出一个或多个与给定“模板”匹 配的数据或对象的各种原理与方法。( 何新贵，1 9 9 0 ) 4 第1 章绪论 1 4 论文主要工作 在t & a p 系统中，站场数据生成及站场联锁特征数据抽取子系统提供测试用 数据，是整个平台运行的基础。随着铁路车站站场运营复杂性的增加，此子系 统中所构造的单元图库很难随意扩充、搜索所得单元进路数据不完备等有待改 进之处逐渐显露，并急待解决以满足测试复杂站场联锁软件的需求。为此，作 者所在的课题小组对之进行了优化改进站场c a d 拼帖及数据生成予系统。 本文研究了对站场图进行逻辑语义解析并生成基本联锁数据的算法及实现，为 测试用数据生成提供正确、完备的基本联锁数据。 论文主要内容包括以下几个方面： 介绍软件测试理论、t & a p 系统的软件系统结构、数据类型，说明t & a p 站场数据生成及站场联锁特征抽取子系统的功能及需要优化改进之处。 ( 第二章) 定义站场图逻辑语义、分析站场图构成规则，并采用一阶谓词逻辑表示 方法形式化这些规则，建立规则库，提出站场图逻辑语义解析算法。在 遍历站场图的过程中，根据单元图所属类别匹配相应构成规则，解析其 逻辑语义。解析涉及进路上逻辑语义时，调用单元进路搜索算法先进行 进路搜索。( 第三章) 详细阐述单元进路搜索算法。采用深度优先搜索策略，以站场图为搜索 空间，不分咽喉搜索站场图中存在的所有单元进路。对进路相关信息及 敌对信号机信息，分别应用约定方向优先搜索策略和进路数据比较法进 行搜索。( 第四章) 结合面向对象技术及面向对象编程，讨论了站场c a d 拼帖及数据校验 子系统的程序设计、站场图逻辑语义解析及基本联锁数据生成的程序实 现。( 第五章) 在总结现有成果的基础上，展望有待深入研究的问题。( 第六章) 第2 章软件测试和测试平台 2 1 软件测试 第2 章软件测试和测试平台 6 0 年代中期，随着软件的规模和复杂度f i 益增大，软件开发质量难以控制， 出现“软件危机”。1 9 6 8 年，在北大西洋公约组织( n a t 0 ) 的一次学术研讨会上 提出了“软件工程”的概念( 黄锡滋，1 9 9 3 ) ，将软件开发视为工程，以规范化、 工程化的方法开发软件，研究应用于计算机软件的定义、开发和维护的一整套 方法、工具、文档、实践标准和工序。目的在于提高软件质量、加速开发进度、 降低开发费用，实现软件生产从手工作坊模式到工程化、社会化的转变。与此 同时，人们开始认识到软件测试的重要作用。1 9 8 2 年6 月，首届软件测试会议 在美国的北卡罗来纳大学召开。会议之后，软件测试的研究取得了令人瞩目的 进展。 2 1 1 软件测试与测试数据 软件测试就是在软件投入运行前，对软件需求分析、设计规格说明和编码 的最终复查，是软件质量保证的关键步骤，是软件生存周期的重要阶段( 飞思 科技产品研发中心，2 0 0 3 ) 。在软件生存周期中，软件测试横跨两个阶段：通常 在编写完每一个程序模块就对它进行单元测试，测试者与编写者往往是同一个 人；在每个模块都完成单元测试后，对软件系统还要进行各种综合测试，通常 由专门的测试人员来承担这项工作。 1 9 8 3 年i e e e 提出软件工程标准术语中给软件测试的定义是( 郑人杰，1 9 9 2 ) “使用人工或自动手段来运行或测定某个软件系统的过程，其目的在于检验它 是否满足规定的需求或是弄清预期结果与实际结果之间的差别”。这就明确提出 了软件测试是以检验是否满足需求为目标。g r e n f o r dj m y e r s 就软件测试目的提 出以下观点( g r e n f o f dj m y e r s ，1 9 7 9 ) ： 1 ) 软件测试是为了发现错误而执行程序的过程： 2 ) 测试是为了证明程序有错，而不是证明程序无错误； 3 1 一个好的测试用例在于发现至今未发现的错误； 第2 章软件测试和测试平台 钔一个成功的测试是发现了至今未发现的错误的测试。 可见，软件测试的本质是针对要测试的内容确定测试用例( p a u l c j o r g e n s e n ，2 0 0 3 ) ，通过运行来检验软件是否f 确。要进行测试，必须包括两 个基本要素：一是被测试程序，二是用以运行软件的数据，称为测试数据( 朱 鸿，1 9 9 7 ) 。软件测试需要大量的测试数据支持。针对被测对象，在测试前要生 成一整套测试用数据。这些数据涵盖了被测对象的属性、测试需求等信息。测 试数据是测试案例的输入数据，正确、完备的测试数据无疑可以提高测试的有 效性和充分性。 2 1 2 软件测试流程和步骤 软件质量保证是贯穿软件开发全过程的活动，其中最关键的步骤之一是软 件测试，软件测试流程可以大致分为两类活动：一类是测试准备活动，另一类 是测试执行活动。一个规范化的测试过程通常包括以下基本的测试活动( 飞思 科技产品研发中心，2 0 0 3 ；r e xb l a c k ，2 0 0 3 ：郑人杰，1 9 9 8 ：吴钦藩，1 9 9 7 ) ： 1 ) 拟定测试计划。在制定测试计划时，要充分考虑整个项目的开发时间和 开发进度以及一些人为因素和客观条件等，使得测试计划是可行的。测 试计划的内容主要有测试的内容、进度安排、测试所需的环境和条件、 测试培训安排等。 2 ) 编制测试大纲。测试大纲是测试的依据，它明确详尽地规定了在测试中 针对系统的每一项功能或特征所必须完成的基本测试项目和测试完成 的标准。 3 ) 根据测试大纲设计和生成测试用例。在设计测试用例的时候，可以综合 利用各种设计技术，产生测试设计说明文档，其内容主要有被测项目、 测试数据、测试过程、预期输出结果等。 4 ) 实施钡4 试。测试的实施阶段是由一系列的测试周期组成的。在每个测试 周期中，测试人员和开发人员将依据预先编制好的测试大纲和准备好的 测试用例，对被测软件或设备进行完整的测试。 5 ) 生成测试报告。测试完成后，要形成相应的测试报告，主要对测试进行 概要说明，列出测试的结论，指出缺陷和错误，对软件进行评估。另外， 给出一些建议，如可采用的修改方法，各项修改预计的工作量及修改的 第2 章软件测试和测试平台 负责人员等。 实施测试过程应分步进行，每个步骤在逻辑上是前一个步骤的继续。软件 系统通常由若干个子系统组成，每个子系统又由许多模块组成，因此，软件的 测试基本上由以下几个步骤完成，如图2 1 所示。 图2 1 软件测试步骤 1 ) 单元澳9 试：又称模块测试。是对软件中的基本组成单元进行测试，如一 个模块、一个过程，其目的是检验软件基本组成单元能否完成预定功能。 单元测试需要编写一个驱动模块和若干个桩( s t u b ) 模块。驱动模块的 功能是向被测模块提供测试数据。桩模块的功能是模拟被测模块所调用 的子模块。 2 ) 集成测试：又称组装测试、子系统测试。是在软件系统集成过程中所进 行的测试，其主要目的是检验与软件设计相关的程序结构问题，检查软 件模块之问的接口是否正确。 3 ) 系统测试：是对已经集成好的整个软件系统进行测试，以验证软件系统 的正确性和性能等能否满足需求规格说明所指定的要求。 4 ) 验收测试：测试内容与系统测试基本类似，但是它是在用户积极参与下 进行的，旨在验证软件是否能满足用户的需要。大多数软件生产者使用 一种a l p h a 测试和b e t a 测试的过程。a l p h a 测试是在开发者的现场由 客户来实旌的，被测试的软件是在开发者从用户的角度进行常规设置的 环境下运行的。b e t a 测试是在一个或多个客户的现场由该软件的最终 第2 章软件测试和测试平台 用户实施的。与a l p h a 测试不同的是，b e t a 测试时开发者通常不在现 场。 2 1 3 软件测试方法 对软件进行测试有很多种方法，根据不同的原则可以有不同的分类方法。 按照选择或产生测试数据所根据的信息的来源，软件测试方法可以分为如下几 种( 朱鸿，1 9 9 7 ) ： 1 ) 以程序为基础的测试。它通过对程序的分析来产生或选择测试数据。它 还以程序被执行的程度来判断测试是否充分。 2 ) 以需求和功能规约为基础的测试。它通过分析软件的需求和功能规约来 选择和产生测试数据，并根据软件需求和功能规约中所规定的功能和性 能是否都得到了充分的检验来判断测试是否充分。 3 ) 程序与需求相结合的测试。它综合考虑软件的需求和实现来选择和产生 测试数据，判断测试的充分性。这一途径早已为人们所公认为软件测试 的必由之路，它可以发扬以程序为基础的测试和以需求为基础的测试两 者的优点，避免两者的不足之处。 4 ) 以界面为基础的测试。以界面为基础的测试仅仅依靠软件与其运行环境 之间的界面来选择和产生测试数据，而不管软件的具体需求和具体实现 细节。典型的界面信息包括软件输入、输出数据的类型、取值范围以及 取值的概率分布等。例如，随机测试就是种以界面为基础的测试方法。 程序和需求相结合的测试和以程序为基础的软件测试都需要了解程序的实 现细节，把被测软件看作是一个“白箱”，从而，在软件测试文献中，也常称之 为白箱测试。而以需求为基础的和以界面为基础的软件测试方法均无需了解软 件的实现细节，在测试过程中把软件看作是一个“黑箱”，从而在软件测试文献 中，也常称之为黑箱测试。 按照选择和产生测试数据以及判断测试充分性的方法，软件测试方法还可 以分为以下几类： 1 ) 结构性测试。结构性测试旨在充分地覆盖软件的结构，并以软件中的某 类成分是否都已得到测试为准则来判断软件测试的充分性。例如，语句 覆盖是一种结构性测试方法，它要求选择测试数据使得程序中所有的语 第2 章软件测试和测试平台 句都得到运行，并根据是否所有语句都得到了运行来决定测试是否可以 终止。 2 ) 排错性测试。排错性测试旨在排除软件中包含某类错误的可能性，并根 据一个测试数据集排除软件错误可能性的能力来度量其测试的充分性。 例如，变异体测试方法对被测软件的代码进行改变，产生原来程序的一 系列变异体。然后，将原程序和其变异体的输出结果进行比较。如果所 有的与原程序不等价的变异体都和原程序在某个测试数据上产生不同 的输出，那么，这个测试数据集就被认为是充分的。 3 ) 分域测试。分域测试方法通过对软件的实现或和软件的需求进行分析， 将软件的输入空间划分成一系列子空间，然后在每一个子空间内选择一 个或多个测试数据。 4 ) 功能测试。功能测试根据软件所需的功能或和所实现的功能选择测试 数据，分析测试的充分性。 一个成功的测试包括两个主要方面：一是软件在所有的( 或是足够多的) 测试数据上是正确的；二是测试数据是充分的，即软件在测试数据上的表现能 够充分地反映软件的总体表现( 朱鸿，1 9 9 7 ) 。测试数据是执行测试的基础，不 论采用何种测试方法，测试数据生成都是软件测试的根本环节。 2 2 计算机联锁软件测试评估平台 2 2 1 t & a p 的软件系统结构 在黑箱模型的功能模块划分基础上，并参照测试平台的物理结构，我们将 t a p 划分为以下几个子系统( 吴芳美，1 9 9 9 ) ： 1 ) 站场数据生成及站场联锁特征数据抽取子系统a ：通过站场图c a d 拼帖自动生成站场拓扑数据，智能搜索产生站场设备表和联锁表， 在此基础上可以通过人工校验数据是否正确，随后生成运行集和操 作集，这些站场数据都保存在数据库中。 2 ) 测试案例自动生成和扩展、测试结果动态判定及站场显示子系统b ： 整个平台的主控系统，它根据测试计划和测试用例的设计选取操作 集和运行集的相应记录构成“有效”的测试用例，并用于判定被测 1 0 第2 章软件测试和测试平台 联锁软件的输入输出响应是否正常的工具。它根据当前证在进 行的测试用例以及现场状态分析被测联锁软件的设备控制命令是否 合乎联锁逻辑绘出正确或错误的标记，并把判定结果送入数据库。 3 ) 通用现场仿真子系统c ：为被测联锁系统提供一个虚拟的现场环境， 它接受来自被测联锁软件的控制命令，返回站场设备的状态信息。 仿真子系统不仅可以模拟“室外三大件”( 轨道电路、道岔、信号机) 的常规的状态及状态转换，而且还可以根据测试要求模拟各种故障 状态和列调车在站内的各种运营作业( 屠海漾，1 9 9 9 ) 。 4 ) 测试结果记录及查询子系统d ：负责测试结果存贮，同时也可以对 测试结果进行查询。 5 1 数据库管理子系统e ：为实现平台的分布式结构及数据与算法分离 的程序设计思路而设的功能模块，它利用开放数据库互连的客户 服务器模式来满足第二代平台的分布式系统结构要求和数据库管理 要求。 图2 2 计算机联锁软件测试平台系统结构 第2 章软件测试利测试平台 6 1 平台通信子系统f ：嵌在各个子系统的内部保证在各个子系统之间 以及平台与被测系统之间的实时、动态数据交换，基本任务是完成 站场静态数据的传送和进行各种动态信息交换。 图2 2 显示了各子系统之间的关系，整个系统可以分成两大部分。一部分是 直接进行测试工作的软件自动测试系统，包括子系统b 、c 、d 、f ；另一部分则 是为软件测试系统提供被测车立占联锁特征数据的数据伺服系统，包括子系统a 、 e 。 测试评估平台的各个子系统工作时既可相互配合，构成一个完整的软件测 试评估平台，有些子系统又可以稍加改造构成一个独立的软件产品，适应不同 的实际需要。例如站场拓扑图数据生成、联锁软件测试集生成及校验子系统既 是测试评估平台的一个子系统，又可以作为联锁系统开发商设计开发过程中的 调试设备生成站场数据。 测试评估平台两大组成部分的信息交换主要是一些站场联锁特征数据的传 送，由软件测试系统提出数据服务要求，数据伺服系统提供联锁特征数据服务。 而平台子系统间以及平台和被测联锁软件之间的所有动态数据的实时传输都是 基于t c p 1 p 协议的。 测试评估平台的测试过程为：用户利用平台提供的铁路车站信号设备平面 布置图c a d 工具，录入被测车站的信号设备及其拓扑关系，并对录入结果进行 正确性检查，然后生成联锁软件测试集；基于这些测试集数据和安全性需求， 平台为被测软件提供一套被测软件控制车站的信号设备仿真环境，并实现测试 用例动态扩展；测试结束后，动态判定、记录、查询和浏览测试结果，评判软 件质量及其可靠性。 2 2 2t “p 系统数据类型 数据( d a t a ) 通常指用符号记录下来的、可以识别的信息。由于这些符号已 被人们赋予了特定的语义，因此，它们就具有传递信息的功能( 施伯乐，1 9 9 9 ) 。 数据交换是测试系统正常运作的基础。根据t & a p 系统的数据对时效性的不同 要求，可以将其分为动态数据和静态数据。 动态数据指输入操作、输出控制、表示信息及大量的内部状态信息，须随 时间推移而实时地、动态地刷新，即数据只是在特定的时间间隔内有效。例如 第2 章软件测试和测试平台 有一些设备状态表示信息，每隔一段时间就需要对它进行一次采样，随时更新； 再如测试系统发送给被测系统的命令，也是实时动态发送的。 静态数据没有严格的实时性，主要描述现场设备及属性( 如信号类型、方 向、道岔类型、轨道区段类型以及静态进路表等) 的数据。t & a p 系统中包含了 大量的静态数据： 1 1 站场拓扑数据 站场拓扑数据是对站场信号平面布置图信息的一种描述方式，包括信号机、 区段、道岔的位置和相互关系。这种描述实际上是对信号平面布置图的一种形 式化描述，它有两方面用途，一方面用于现场仿真的动态显示，另一方面是作 为测试用基础数据生成的原始依据。 2 ) 设备数据 设备包括信号机、道岔、轨道电路区段。设备数据因此也相应的记录了一 个站场内的全部信号设备的名称、相互之间的联系以及属性等。站场的设备数 据一旦正确生成便不再改动。 3 ) 进路数据 进路数据记录的是列车和机车车辆在车站内运行线路上的信号机、轨道区 段、道岔设备以及设备之间的拓扑关系等信息。进路数据信息类型有单元进路、 长调车进路、组合列车进路、延续进路、引导进路、平面溜放进路、非进路调 车进路以及驼峰推送进路。以上数据并不是每个车站全部具备，但联锁数据自 动生成子系统却必须具有以上功能，以适用于不同的车站。 图2 3 是平台的静态数据流向图。站场拓扑数据是设备数据、进路数据生成 的原始数据，设备数据、进路数据属于测试用基础数据，是平台测试案例自动 生成、仿真环境生成、测试结果动态判定的输入数据，是测试环境生成的基础， 也是平台正常工作的必要条件。站场拓扑数据、设备数据及进路数据应满足以 下要求： 1 ) 完整性：测试用基础数据必须包含站场信号设备和进路信息、相关信息 等所有数据。 2 ) 拓扑性：测试用基础数据大多不是孤立存在的，数据与数据之间通常存 在着一定的拓扑关系。 3 ) 正确性：测试用基础数据的错误可能会导致测试案例生成的错误，进而 造成测试结果动态判定的错误，严重时可能会导致测试中断或系统瘫 第2 章软件测试和测试平台 痪。因此，测试用基础数据的正确与否是测试成败的关键所在。为了防 止数据有错误，必须提供检查、校验及修改手段。 图2 3 静态数据流向图 2 2 3 站场数据生成及站场联锁特征数据抽取子系统的优化 站场数据生成及站场联锁特征数据抽取子系统是联锁软件测试平台的一个 重要组成部分。该子系统由铁路站场信号基本数据录入器，站场数据自动生成 及校验系统两个程序组成。此子系统完成如下功能： ( 1 ) 站场数据计算机辅助生成 站场数据是指铁路车站信号平面布置图中有关信号设备的名称、型号及其 平面布置、区域分割等数据，控制台盘面上有关操作按钮、表示灯和信号复示 器等部件的配置及名称等数据，以及这些设备及部件之间的各种相互关系数据。 站场数据计算机辅助生成的功能由铁路站场信号基本数据录入器完成。站 场数据生成的输入依据为站场信号平面布置图、控制台盘面布置图、信号显示 关系图及行( 调) 车的特殊要求等，其输入方式采用面向对象的单元图拼贴方 式。另外，站场数据的生成要考虑满足整个平台的需要，并保证所生成数据的 正确性。为此，在以面向对象的单元图拼贴方式手工拼贴控制台盘面布置图和 录入相关数据后，需对输入的数据进行正确性校验。 1 4 第2 章软件测试和测试平台 f 2 1 测试用数据生成 测试用数据是指t & a p 进行测试时所需的基础数据，包括进路( 单元进路、 长调车进路、延续进路、引导进路等) 数据、运行仿真命令数据以及与它们有 关的设备数据，是测试案例自动生成、扩展及测试结果动态判定时所需的数据 和现场环境仿真所需的数据，是测试环境生成的基础。平台对测试用数据具有 严格的正确性、完备性要求，因为测试用数据的差错会直接导致测试结果的错 误判断、测试中断或平台系统瘫痪。 铁路站场信号基本数据录入器采用面向对象的单元图拼贴方式，具有使用 便捷、高效、可视和通用等特点。但是随着铁路车站站场复杂性的增加，站场 图录入过程中出现单元图库中不存在的单元，而程序中单元图库的扩充一直是 站场数据生成及站场联锁特征数据抽取子系统较难解决的问题，给站场图录入 带来了诸多不便。对站场数据正确性的校验不仅包括站场数据是否完整、设备 命名是否合法、是否满足平台中后续模块或子系统对站场数据的特殊要求等， 还应依据铁路信号的有关联锁规则对单元图间、单元与进路之间的各种语义关 系进行检查。站场数据生成及站场联锁特征数据抽取子系统对站场图进行智能 搜索生成基本联锁表。由于程序算法中采用分咽喉对站场图进行搜索，导致对 某些特殊站场搜索所得的进路不完备，需要对进路搜索算法加以改进和优化。 而且构成站场数据生成及站场联锁特征数据抽取子系统的铁路站场信号基本数 据录入器，站场数据自动生成及校验系统两个程序相互独立，运行中又要进行 不断的数据交换，有许多重复性的工作，因此本课题小组将以上两个程序优化 集成为一个子系统站场c a d 拼贴及数据生成子系统。 站场c a d 拼贴及数据生成子系统分为站场c a d 拼贴、站场图逻辑语义解析 及基本联锁数据生成、测试用数据生成及校验三大功能模块。此优化系统采用 一种基于单元的知识集成表达方法，利用a c t i v e x 控件技术( 虞翊，1 9 9 7 3 ： 李杰，2 0 0 4 ) 构造单元图库，完成站场图的拼帖。站场图拓扑数据是生成测试 数据的原始数据，具有严格的正确性、完备性要求，针对这一要求，笔者提出 站场图逻辑语义解析及基本联锁数据生成算法，在遍历站场图的过程中，解析 站场图逻辑语义，并生成基本联锁数据。测试用数据生成及校验模块应用可视 化技术、采用人机交互方式，以图形的方式显现数据之间的规律和联系，提高 测试集生成的效率。其中，站场图逻辑语义解析及基本联锁数据生成是作者研 究的重点。由铁路信号站场拓扑性知识导出站场图构成规则，建立规则库，并 第2 章软件测试和测试平台 应用这些规则解析站场图逻辑语义。解析过程不仅实现了对站场图中各单元图 之间的语义关系检查，其中调用优化的进路搜索算法搜索得到站场图中所有可 能存在的单元进路，并据此进一步解析单元与进路间的逻辑语义，保证站场数 据符合铁路信号联锁规则要求，使得在此基础上生成的测试数据正确、完备。 站场c a d 拼贴及数据生成是t & a p 的测试用数据生成子系统，是整个t & a p 重要 的组成部分，是平台运行的基础。 第3 章站场图逻辑语义解析算法 3 1 站场图 第3 章站场图逻辑语义解析算法 站场图中包含了铁路信号站场拓扑性信息，即铁路信号平面布置图中有关 设备( 带有名称、型号等) 的平面布置、区域分割等拓扑性数据以及控制台盘 面上有关按钮、表示灯和信号复示器等部件之间的各种相互关系数据( 虞翊， 1 9 9 7 1 2 ) 。它是生成测试数据的基础。为了满足知识表达完备性和信息输入简 捷性的要求，t & a p 选择了一种基于单元的知识集成表达方法，利用a c t i v e x 控 件技术( 虞翊，1 9 9 7 3 ；李杰，2 0 0 4 ) 构造能够表征设备的单元图形，并以这 些单元图形为基本单位，拼贴成站场控制台盘面图，与设备相关的其它数据( 如 设备名称、公里坐标等) 可通过对话框输入，并以单元数据结构为基本元素， 构成站场拓扑结构图( 简称站场图) 。 3 1 1 单元图形库 由于t & a p 是应用于铁路信号领域，站场拓扑信息的输入方式不但要便捷、 高效和可视化，而且要便于铁路信号专业人员接受。因此，系统采用了面向单 元对象的录入方式，利用a c t i v e x 控件技术建立一个可扩充的单元图形库。图形 库中的每个单元图形对象的数据由单元图形数据( u n i t i m a g ed a t a ) 和单元结构 数据( u n i ts t r u c t u r ed a t a ) 两部分组成。单元图形数据描述的是单元图形内部的 物理特征，一个单元图可以纳入多个关系比较密切的信号设备或部件图形符号 ( 信号机、绝缘节、按钮、道岔、轨道等) 及称谓，供站场实时信息显示用。 根据图形特征把包含信号机、绝缘节和轨道的单元图纳入一类信号机单元， 包含按钮和轨道的单元图纳入一类按钮单元，从而这些单元图可分为六大 类( 共1 7 5 个常用单元图) ：信号机( s i g n a l ) 、单( 双) 动道葫( s w i t c h ) 、 轨道( t r a c k ) 、复式交分道翁( r s w i t c h ) 、表示灯( i n d i c a t o r ) 、按 钮( b u t t o n ) ，如图3 1 所示。单元结构数据描述的是铁路信号站场平面布 置图和控制台盘面布置图中拓扑性信息，是生成测试数据的主要信息。单元结 构数据的结构如下： 1 7 第3 章站场幽逻辑语义解析算法 s t r u c r _ u r q r r i n tc 0 1 o f u n i h i n tr o w o f u n i t ： i n tc o d c ； i n tp o s ro fu n i t ； c h a rn a m e 4 n a m e l c n t h ； i n tt y p e _ o fm a c h i n e 4 ： 单元图形列坐标 单元图形行坐标 单元代码 绝缘节的公里坐标 设备名称数