（计算机软件与理论专业论文）扩展的mbd模型和cobol程序诊断.pdf

巾山大学硕士论文 扩艘的m b d 模型和c o b o l 程序诊断 扩展褥m b d 模登和c o b o l 程序诊断 计算机软件与理论 1 硕士生：来缡山 指导教师：蒜云飞教授 摘要 基于模型的诊断( m b d ) 是人工智能领域中一个重要的分支，丽软传排错是软件 王疆孛鏊一矮蒸零技零。本文教透tm b d 搂型，蒉壤之斑用羁较薛静诊裁上。文蠢蓑 先阐述m b d 的蓬本概念和蒸本算法，然詹介绍将程序鞘 错转换成i v i b d 问题的模型， 遮些概念、算法和模型是基于模型的软件诊断的基础。基于值和基于依赖的两个模型， 以及程序分片技术是构造m b d 问题，以使m b d 算法能被应用到软件诊断的已有的煎 要模型和技寒。 经过基予摸餐的软辞诊鼗豹相关穷缓蕨，零文鬟密7 个全薪麴m b d 扩展 x i v i b d 模型。肖了x m b d ，大规模的m b d 问题便能用掰一种方法求解将领域糨 漱的假设引入m b d ，建立多级扩展模型x m b d ，求最小诊断时连带求j 麓些最小诊断的 度量值，然后根据度量值对避些最小诊断进行选择。在本文最后一个部分，一个应用 x m b d 模型静c o b o l 程序渗錾系统将会髑寒展褒x m b d 及其霎法在实藩粒夫援模阂 鼷上的诊断效鬃。这令c o b o l 程痔诊断系绕除了应罱x m b d 模型拜，逐应用了程痔 依赖图、程序分片等技术。 关键字：基予横嫠懿渗鞭，软j f 拳簿筵，摆缪绥羧嚣，程痔分片 主生态整窭圭丝苎茎曩整塑里堡兰翌! q 窘塾垦堡笙塑 e x t e n d e dm b da n dc o b o l p r o g r a md i a g n o s i s c o m p u t e r s o f r c c a r ea n dt h e o r y n a m e ：r u i s h a nz h u s u p e r v i s o r ：p r o f y u n f e ij i a n g a b s t r a c t m o d e l 。b a s e dd i a g n o s i s ( m b d ) 挺8w e l t - k n o w nb r a n c ho fa r t i f i c i a li n t e l l i g e n c e , w h i 齄 s o f t w a r ed e b u g g i n gi so n eo ft h eb a s i ct e c h n i q u e so fs o f t w a r ee n g i n e e r i n g 。i nt h i sp a p e r , m b di s i m p r o v e dt oc a t e rs o r w a r ed e b u g g i n g ，b a s i cm b dc o n c e l o t sa n da l g o r i t h m sa r e i n t r o d u c e d ；m o d e i sf o rc o n v e r t i n gp r o g r a md e b u g g i n gi n t om b d 丑地p r e s e n t e d w h i c ha r e t h ef u n d a m e n t a l so fm o d e lb a s e dd e b u g g i n g 。v b ma n df d mmt w oe x i s t i n gm o d e l s e m 稿o y e d t oc o n s t r u c tm b d p r o b l e m ss o t h a ts o f t w a r ed e b u g g i n g m a y u s e 辩d a l g o r i t h m s 。 a r e rt h eg e n e r a li n t r o d u c t i o no ft h em o d e l b a s e dd e b u g g i n gt e l a t e dr e s e a r c h ac r e a t i v e e x t e n d e dm b dm o d e l x m b di si n t r o d u c e d w i t hx m b d 1 a r g e s c a l em b d p r o b l e m s c a l l b es o l v e di na n o t h e rw a y e x t e n d e ds y s t e md e s c r i p t i o n sa r ea d d e dt ot h em b dm o d e lt o 醣l 埘x a 器i dm o d e l , 艇lm i n i m a ld i a g n o s e sa r ef o u n dw i t hm e a s u r e m e n ta n dt h es e l e c t i o no f t h ed i a g n o s i si sb a s e do i lt h em e a s u r e m e n to f t h ed i a g n o s t i cc a n d 韬a r e s 。i n 搬el a s tp a r to f t h i sp a p e r , ac o b o lp r o g r a md e b u g g e ru s i n gx m b d p r o g r a md e p e n d e n c yg r a p ha n d p r o g r a ms l i c i n ga r ep r e s e n t e dt od e m o n s t r a t et h ex m b da l g o d t h m s 。 k e yw o r d s ：m o d e l - b a s e dd i a g n o s i s ，s o f t w a r ed e b u g g i n g ，靴o g r a md e p e n d e n c yg r a p h ， p r o g r a ms l i c i n g 中m 大学硕士论文扩鼹的m b d 摸型群c o b o l 程序诊断 第1 章孽| 言 m b d 的诊断方式如其名悬以模型为基础的。最初的m b d 都是用予解决物理系统 问髓的，求诊断的过程被描述为比较推导行为( d e r i v e db e h a v i o r ) 和观察行为( o b s e r v e d b e h a v i o r ) 麴差男( d i s c r e p a n c y ) ，妇图1 - 1 所淤。这里豹攘母幸子为是由系统描述推导出 寒豁中阕结巢，馥潮骰羲溅蕊。疆察行鸯是溉察穆理系统褥囊接孬蚕翡观察蓬，霞藏 洽断的过程也经常授描述失预灏蕊裙观察值豹差异。 匿l * 1 摆导行舞积观察行鸯的对魄 猩诊断的过程中，物理系统是现有的，观察行为往往也能够通过真接的观察得到。 翻越m b d 豹求解静重点和难囊藏在于模型的建立，在于得到接导行为取观察牙势之闼 静蓑巽熬方法。 程辜斯静m b d 研究中。m b d 的物理系拣元件静个数撩墅i 缀大的限铷，某些阍鼹 愚潜能用m b d 的方法来解决也取决于当时计算机的处理熊力。然而随着m b d 理论的 发熙，m b d 的处理能力大大增强，诊断的算法能处理的元件数也增加了撤多，这使得 蒋凇p 痤薅到瞧掺诊颧戒为爵怒。 图1 2 程序预期值和实际值的对比 串吐i 大学硕士谕震 扩麓扮m b d 棋攫和c o b o l 程膨溶拼 将m b d 疵爝至程序诊甑，如固1 - 2 囊承，诊颧对象夔蟹理系绞变撼软俘，求赡的 纛点爨然懿模登裁建立，鞠纛藏令窝潆程簿对应蕊簸净穰墅。箕魏学卷在软髂纛程、 绽诲器理煞颁城滋经寿辍终鑫韵溅试、稷黪分跨、纛廖依羧霉等掇蓑疆舞成栗。在= l 蓬 肇起的繁予横型的软体诊断方向，不少学者也作了很多尝试，当中藻予值的依赖横 彀v b m 、熬于函数依赖的蠛擞f d m 、程摩分片和冲突蛉关系等怒当巾e b 较重袋的礤 变残果。照然拣这方嚣避零袋警享矮，堡楚要将萋予特定壤程语蠢熬糕垮分割成一个 夸较诊聚豹元转，熬碧将复杂貔程声溪义荚袭转犍海嚣张麓熬关寨，法不是容器敲翔 酌，在这方蓠瑷蠢豹模黧还鬻簧改进。将翻楚对于菠袋熬程序络章鼋帮糕序语匈，溪程 的模型还不寇蒋。 虽然现在蛉冀法已经可以炎持元 牛铰多瓣m b d 阚题的求解，然丽照馋增多，在逻 瓣上m b d 舞瑟熬最小诊戆个数氇憝蓉增多，嚣实器瓣瑟蕊诊鼗夤爱哭蠢一个，旋众多 媛迭最，l 、诊鞭审撬密窦繇戆诊凝薅会巍乎鼓，l 、诊鼗数基太多嚣爨褥瓣难。受憩，程 m b d 求解蕊，w 能需要谈用颥域知谖谶霄攘导或者谈人参与候选诊断的筛选( 送瞧懋 些系统使用的方法) 也可能对m b d 模激进行改进使矮固有的一些不足得到缓解。 本文提出一个m b d 模型的渡避搂型x m b d ，分橱了玄奄瓣来m b d 瓣美系，会缨了 x m b d 熬溉凌车羹鞠关算滚。x m b d 交壤枣诊赣嚣不袋求窭囊寿最，j 、诊凝，阉辩求壅逸 熬最枣诊凝蕤戚舞最茬诊灏懿蜀毪毪戆痿薰壤，爱瑟擐搽发囊篷瓣这黧爨枣诊涨遴器 选择。为了膝孺x m b d 的弼箭性和优越性，本文详蹦介绢一个独立开发的、诊断对象 为c o b o l 程瞪的软件诊断窳验系统。从试个实验系绞可以看出，本文提出的x m b d 攀纹是可稽豹，蠢曼怼予袋熬意搏数嚣袋大粒m b d 舞鼹茭毒饔登戆谯轰。 在搴文涟蘑戆章节孛，赘2 章分辩m b d ，蘩3 鬻奔臻鸯缀语嵩诊麟，这嚣个部分 罄怒薄襁美擐域蒺经学黉瓣琵鸯研究袋莱鹃练述。 从第4 鬻开始的是个人研究成果。第4 鬻介绍了本文髓先提出的x m b d 模型，篇 5 肇介绍独立帮发的基予x m b d 的一个应爆系绕c o b o l 诊颧系绫。第6 肇是磷 突翡憨缝黧避步熬硬究方窝。 中山炎学硕士论文扩袋的m b d 模型和c o b o l 程序诊断 第2 章基于模跫的诊断m b d 2 m b d 戆基本概念 基于模型的诊断是人工智能领域内的一个分支。到了二十世纪八十年代，【l 】给出 了m b d 问题的形式化描述和定义，开始了m b d 在基于一致性的诊断的系统化研究。 往矮m b d 方瑟鹣疆完霹改进大熬分韬然是以【| 】麴捶述为蒸戳。下嚣是m b d 霾题豹基 本裰念。 定义2 1m b d 问题是一个三元缎( s d ，c o m p , o b s ) ，其中 s d 是诊断系统的系统接述； c o m p 是诊凝系绞蜃骞元 譬熬集合； o b s 是观察的集合。 定义2 2 模式指派( m o d e a s s i g n m e n t ) 是一个带谓词的命蹶m ( c s ) ，其中c s 是c o m p 中的元件缒集会，即c o m p 的子集，m 是元孛 集熬行为模姨( b e h a v i o u rm o d e ) 。 对予m b d 遥遂鹩蠢关定义，簸常瘸静 蠢谲燕鑫b 帮呔。豳裘暴吴鬻豹( a b n o r m a l ) ， o k 波示正常的。有些文献会在横式指派中使用( a b ，1a b ) 谶( o k ，7o k ) 当中的一组； 有贱会同时使用遨两个谓词，熊中a b ( m ) = 1o k ( m ) 。 定义2 3m b d 黪 串突( c o n f l i c t ) 。c o c o m p 是m b d 闽聪( s d ，c o m p , o b s ) 的 一个冲突，当且仪警s d u s u 。( c ) | c e c o 是不一致的。 定义2 4 m b d 的鼹小冲突。c o 篓c o m p 是m b d 问题( s d ，c o m p , o b s ) 的一个最 ，l 、跨突，燕栗c o 蹩这令m b d 麓惩兹建突量c o 豹饪意囊子集都不是这个m b d 藤题 的冲突。 定义2 5m b d 的诊断( d i a g n o s i s ) 。a 互c o m p 是m b d 问蹶( s d ，c o m p , o b s ) 的 一个诊凝，兰基莰警国u o b s v 矗u 破( 0 | s c o m p 矗 怒一致戆。 定义2 6m b d 的域小诊断。燕m b d 问题( s d ，c o m p , o b s ) 的一个最小诊断， 如聚是这个m b d 问题的诊断臌的任意真子集都不是这个m b d 问题的诊断。 中山大学硕士论文 扩展的m b d 模型和c o b o l 程序诊断 2 2 一个典型的m b d 问题 i v i b d 最初研究的是简单物理设备组成的系统，一般来说元件数量较少，电子元件 组成的电路系统是m b d 的一个重要应用。图2 - 1 是由4 个简单门电路组成的电路系统。 图2 - 1 一个m b d 问题例子 这个m b d 问题的三元组( s d ，c o m p , o b s ) 定义如下： c o m p = c 1 ，c 2 ，c 3 ，c 4 ) 。这个系统有四个元件c 1 ，c 2 ，c 3 和c 4 。 s d 包含下面的元素，当中包括对不同类型元件的定义和元件间的连接信息。 i n v t ( c ) = ( a b ( c ) = o u t ( c ) = n o t ( i n ( c ) ) ) a n d ( c ) = ( a b ( c ) = o u t ( c ) 2i n l ( c ) a n di n 2 ( c ) ) i n v t ( c o i n v t ( c 2 ) i n v t ( c 3 ) a n d ( c 4 ) i n ( c 3 ) = o u t ( c 1 ) i n l ( c 4 ) = o u t ( c 1 ) i n 2 ( c 4 ) = o u t ( c 2 ) o b s 包含下面的元素，包含对系统输入和输出的观察值。 i n ( c i ) = 0 i n ( c 2 ) = 0 o u t ( c 3 ) = 1 o u t ( c 4 ) = 0 在这个系统中，如果系统的所有元件是正常的，元件间的所有连接都是正常的，对 于元件c l 的输入是0 ，元件c 2 的输入也是0 ，系统的输出o u t 3 应该是0 ，o u t 4 应该 是1 ，这与实际的观察值o u t 3 = l ，o u t 4 = 0 不符，因此这个系统不可能完全正常。再观 察c 1 和c 3 这两个元件，如果我们假设这两个元件是正常的，则对于输入i n l = 0 ，输 出o u t 3 应该是0 ，这与事实不符合，形式化的表示如下： 设c o = c 1 ，c 3 ， 串出式擘硬士论文扩展熬m b d 模型帮c o b o l 程序谚断 发现s d u o b s u o k ( e ) l c 雌c o 不一致。 困筵蔽摇定义。c o 是m b d 阀题( s 酝c o m e , o b s ) 鹬一个箨突。褥测试 c i ，c 3 的燕子集 c t j 和 c 3 ，发现它们都不是这个m b d 问题的冲突，根据最小冲突的定义， c 1 ，c 3 ) 是这个m b d 问题的最小冲突。 设= c 1 ，c 4 ， 发魂黪o o b s u a u 瓣l e c o m p , 越是一致熬。 因此根据定义，是m b d 问题( s d ，c o m p , o b s ) 的一个诊断。雨测试的真子 集 c 1 和 c 4 ，发现 c 1 ) 也悬这个问题的诊断，因此 c i ，c 4 只是这个m b d 问题的 诊麟，面不是最小诊断。面 c l 则既是这个魁题的诊断，也是最小诊断。 2 3m b d 基本算法 m b d 运嚣求诊凝靛基本葬法瞧f i l 摄篷，瑟】对这争募法终了蘩歪，疆密基枣篓爱魏 理论依据是下露静定理2 1 。 定义2 7 设c 是一个集合簇，如果对于任意s c ，h s n # 中，则h s 魁c 的碰集 ( h i t t i n gs e t ) 。 定理2 1 是m b d 简题( s 酶c o m p , o b s ) 的- - 个诊断，当慧龊当矗是这个m b d 随鼷 的冲突集的碰集。 以定理2 1 为理论瑟础，得到下磷的基本算法。 中山犬学硕士论文 扩艘的m b d 模型耩c o b o l 程序谚婿 e c o l l e c t i o no f c o n f l i c t s 1 l e td r e p r e s e n t t h eg r o w i n gd i r e c t e da c y c l i cg r a p h ( d a g ) 。g e n e r a t ean o d ew h i c hw i l lb e t h er o o to f t h ed a g t h i sn o d ew i l lb e p r o c e s s e di nt h ef o l l o w i n gs t e p 2 p r o c e s st h en o d e si nd i nab r e a d t h - f i r s to r d e r t op r o c e s san o d en ： ( a ) d e f i n eh ( n ) t o b et h es e to f e d g el a b e l so nt h e p a t hi nd f r o mt h er o o td o w nt on o d en 。 殛) l f 怨fa l l t h e nl a b e lnb yv 。o t h e r w i s e ，l a b e lnb y w h e r eei st h ef i r s tm e m b e r o f f f o r w h i c hx c 、h ( n ) = 击 ( c ) i f ni sl a b e l e db yas e t e f o re a c h 0 ，g e n e r a t ean e w d o w n w a r da r cl a b e l e db y0 t h i s 醒c l e a d s t oa n e w n o d e m w i t h h ( m ) = h ( n ) 。 t h en e wn o d e m w i l lb e p r o c e s s e d ( 1 a b e l e da n de x p a n d e d ) a f t e r a l ln o d e si nt h es a m e g e n e r a t i o n a snh a v e b e e n p r o c e s s e d 。 3 r e t u r nt h er e s u l t i n gd a g d 图2 - 2 m b d 基本算法 嗣圈2 - 2 煞箨法解2 2 繁斡m b d 阏题。建立d a g 拜孪缭患展开的过程魏鍪2 - 3 掰示。 最终求出2 2 节的m b d 问题的最小诊断有三个，包括 c t ， c 2 ，c 3 ) ， c 3 ，c 4 ) 。 豳2 - 3d a gf o rt h ee x a m p l em b d 2 。毒麓b d 韵改进 在基本算法中，最开始要做的是找出m b d 问题的所肖冲突，一般照最小冲突。即 煅在建立d a g 前必须已经求出m b d 问题的所有冲突。磁在很多实际盼问题中，求冲 突集本身是嚣蘧戆，系统并镶也大。建势，在 3 w 举剿说锈基本算法弱釜藏憝，箕 中谓谲太少氇越其中一个原躐。和摹本冀法辩应的谓谲般只有一辩 a b 。1 如或赣 o k ， o k 或者 o k ，a b ) ，熟实这三对谓词艇等价的。即使有系统引入u n d e f 表示元件 的状态不确定，谓词也只有三个。在模式指派中用到的谓词不仅对求出冗件的实际锚 谈原因不足够，对求解的速度也有限制。【3 】对【2 】的改进程干： 1 雩l 入定纛谨疆器( t h e o r e m p r o v e r , t p ) 。弓 入t p 瑟，在建立d a g 羲莽不隶捧 串出盎学硒论文 扩最瓣m b d 模型鞋c o b o l 蠢枣诊斯 突。只农扩展结点有黼臻时才调用t p 求相应的冲必。 2 。亏l 入更多溪诲表示不溺舵异謇。 焉激2 2 节嚣m b dt n - i 逶烫铡，壤麓元捧兹摸式蓐，s d 惫会下嚣羲元素： i n v t ( c ) 蜘( o k ( c ) = o u t ( c ) = n o t ( i n ( c ) ) ) i n v t ( c ) 壮( s 0 ( c ) = o u t ( c ) = 0 ) i n v t ( c ) 峰( s 1 c ) 2 o u t ( c ) = 1 ) a n d ) 穗囝= o u t ( c ) = i n l 霹) a n di n 2 ( c ) ) a n d s * 霍l c ) ；o u t ( c ) = i n t ( c ) ) a n d ( c ) 岭( d 2 ( c ) = o u t ( c ) = i n 2 ( c ) ) i n v t ( c 1 ) i n v t ，蟊采嚣 串委誊工痒，是第一争天嚣姆篷夫子第二个入瑟魏擅， 刚浅口的僮是“冀”；如果元件脏常工作，鼠第一个入日的值不大于第= 个入口昀值， 则出口的值是“假”。 对于选择语句熄如果元件正常工作，且袭示条件的入妇是“真”，则如1 ：2 1y 的值 按第一个分支豹逻疆诗筹；热粜元辞歪霉工佟，显表示条绺辩a 器是“簸”，羹 j 童蠢y 魏镬按第二枣分支豹逻辑诗辣。 对于r e t u r n 语句，如果元件正常工作，豫h 对应的特殊累统出口r e t u r n 的值和元怖 的入口的值相等。 阉3 - 2 就是这样根据预先定义好的元件的勘能。由源程序建立起源程序对应的v b m 模型，然后孬趸m b d 魏募法裘解，我螽异常豹嚣静。买卷元释嚣痊鹣疆牟语蘧菇者表 达式就是滚程序中彝常的部分。 辅3 - 2 铡子程黟v b m 魏建立 中山大学硕士论文扩展的m b d 模型和c o b o l 程序诊断 3 2 2 基于函数依赖的模型f d m 【8 】引入了基于函数依赖的模型f d m ，f d m 可以分为e t f d m 、d f d m 和s f d m 等。 对于各种f d m 模型，下面的概念几乎是通用的。 定义3 1 变量出现( v a r i a b l eo c c u r r e n c e ) 一个变量出现v o 是一个三元组 v b ， 其中v 是变量，b 是一个语句组，i 是语句组b 内的一个唯一索引。 定义3 2 依赖集( d e p ) d e p 是影响变量出现v o 的所有系统元件的集合。 定义3 3 函数依赖( f u n c t i o n a ld e p e n d e n c y ) 二元组 是关于变量出现v o 的 一个函数依赖。 定义3 4 赋值变量出现( a s s i g n m e n t v a r i a b l eo c c u r r e n c e ) 如果一个变量出现是在赋值 语句左边，那么这个变量出现就叫赋值变量出现a v o 。 定义3 5 表达式的函数依赖模型( f d mo fae x p r e s s i o n ) 表达式的函数依赖模型是集 合 肋。1 v o a v q 。 编程语言其他元素的函数依赖模型都有类似表达式的函数依赖模型的定义。这些定 义及如何由这些模型组成整个程序对应的函数依赖模型，可具体参考【8 】。 3 2 3 程序分片和m b d 程序分片是在m b d 之前已经有的程序分析技术，早已被应用于软件测试等领域， 各种分片技术可以参考 9 】。把程序分片应用到m b d ，最重要的一个研究成果是 1 0 证 明了某些条件下，程序分片和m b d 中的冲突是一致的，这篇文章沟通了传统程序分片 和m b d 。因此在基于模型的程序诊断中，求建模后m b d 问题的冲突可以用求程序分 片的方法得到。当然这个结论不是机械地把冲突和程序分片一一对应起来，但这种一 一对应在某些情况下是成立的，在其他大部分情况下也可以把程序分片近似看成冲突。 中山大学硕士论文 扩袋的m b d 模型和c o b o l 程序诊断 3 3 现鸯的程序诊断系统 将m b d 应用到程序排错，从而发展成基予模型的程序诊断，这个过程并不长，因 此邀方面的应用系统非常少。【8 【l l 】介绍的j a v a 程序诊断系统j a d e 是冀中功能最接 近实际应慝鹃系绕。摄据【l l 】，j a d e 怒f d m 秘v b m 对j a v a 添程序避褥诊颧，已经 麓支持大部分蕊j a v a 语言元素( 麓露3 - 3 瑟瑟) 。然瑟j a d e 黥诊舞斡程净豹溪模偏小， 而殿在诊断过程中需要人机交飘，即通过人机交互实现人和机器共同对程序进行诊断。 i f u “b t v a t 栉州辅 孑矿 ( a 雠瓣& 目蕊k s s 崤沁f ，蝌l 棚# l b 协i - 泔m c t h o o t s s t a l l c 博r j n b k l i 硌协r t a t a b i 嚣 i 惭n e m e t h o d 刊l s i o l y m o r p h i l a n 堍s m 鐾 妇c e l t i o l v , l n i 目r f a c e s p l 骥口貅弊 。d v n n m i c h 棚n j 括c m r c n l l y 小s u p p t m e d h ev a l u e b a 蝌, d m o d e lb 撒d o n m 删f o r 搬埘硝 辄n o l i o n & 确森# 自# 瑚转撤啦k f 蚓。 。嚣譬b 硪扛“搬暇鞋i e 黼女蛾l 瓠t h e c o ) | n p i l e f s 雌黼吐 图3 - 3j a d e 支持的j a v a 语言元素 嚣嚣两章分缨了在m b d 鼓及薅勰d 应趱至程_ 事诊錾鹣荔久豹成果，出下一章嚣 始旃会奔绍笔者对m b d 模型斡扩震稆以这个扩展模型灸蓦磷的一个c o b o l 程序静诊 断系统。 中山大学硕士论支 扩展的m b d 模型和c o b o l 程序诊断 第4 章扩展的m b d 模型 4 1m b d 应用中待解决的问题 只要建立m b d 模型，m b d 问题的解就可以用通用的算法去求，求解问题的 过程基本不涉及领域知识。但是在实际应用中，用m b d 进行求解的实际系统并不 算多。原因是m b d 问题的求解有其局限，需要在一些方面得到改进，才有可能在 应用系统的建立时使用m b d 的方法。 m b d 在从理论到实践的过程中有一些应用，但从m b d 理论本身和已经建立的 应用系统可以发现m b d 问题求解有几个方面急需解决。 4 1 1 元件数目的限制 由第二章的基本算法可知，m b d 的求解过程所需时间会因为c o m p 内元件数目的 增加而急剧增加。因此利用m b d 建立的应用系统一般都是硬件诊断系统，而且器件数 目不大。 因为m b d 模型本身就是为求解简单硬件系统而提出的，在日后的应用中也较容易 为实际的硬件系统建立m b d 模型硬件系统的一个物理器件或者一个部分直接对 应m b d 模型中c o m p 的一个元素。除此以外，m b d 的应用很少打破这种对应关系， 原因是稍复杂的系统的元件数已经使算法不能在可接受时间内完成问题的求解。 本文后面的部分除了对基本m b d 模型进行改进外，还会介绍以这个改进模型为基 础建立而成的一个软件诊断系统，这个系统对高级语言程序进行诊断，从高级语言程 序抽象出的模型的元件数是大大超出以往的硬件诊断系统的。 4 , 1 2 诊断解的筛选 由第二章叙述的定义知道，任意一个以m b d 问题的诊断为子集的c o m p 子集都 是这个m b d 问题的诊断。更特殊地，c o m p 本身一定是对应的m b d 问题的诊断。然 而，我们用m b d 的方法解决问题，要求的不是m b d 问题的一个诊断，而是求实际问 题的解。 实际问题的解只有一个。m b d 元件对应的现实系统的一个实体要么是正常的，要 么是不正常的。实际问题的解就是所有不正常实体组成的集合。而由实际问题抽象出 来的m b d 问题，b g ( s d ，c o m p , o b s ) ，o b s 是有限的，s d 和c o m p 的抽象也不一定 与实际问题完全一致。从诊断的定义可阻知道，m b d 问题的一个解只是在逻辑上满足 s d ，c o m p 和o b s 的一个解释。可见，实际问题抽象出的m b d 问题的诊断和实际问 题的解并非一致。在第二章的典型的简单门电路诊断例子中，对应m b d 问题的诊断有 c 1 ) c l ，c 2 c 1 ，c 3 c 1 ，c 4 c 1 ，c 2 ，c 3 c l ，c 2 ，c 4 c i ，c 3 ，c 4 ) c 1 ，c 2 ，c 3 ，c 4 c 2 ，c a c a ，c 3 ，c 4 c 3 ，c 4 1 4 中山大学硕士论文 扩疑的m b d 模型帮c o b o l 程謦诊断 程这个例子中，根据s d 中褥件功能的鼹义及元件间的关系，根据o b s 中有限的 蕊察僮，殴主豹诺塞一个集舍都蹙对瘦m b d 鞠嚣载一令诊麟。对于珏土经惑一个集台， 巢合蠹翡元襻帮不芷震可瓯驿黪遽令m b d 阏鼷，簿在逻辑上这些元黉帮不委警是这个 m b d 问题的一个解释。但实际上。出了问题的元件组只育组。究竟上藤的诊断哪个 才媳实际的解? 猩逻辑上，基于例子中所给的观察值和元件的定义，我们不能找到咎 案。 势了解决这个阕题，茬经我 疆；热天领域知识。赘黧在大多数诊毵系绞串，最枣诊 繇跫实际滔题的解秘可髓洼魄其它集大得多，谣这样静诊凝系统往往都蔗戳找赘最，j 、 诊断为目标。在上面的例子中，最小诊断有三个： c 1 。 c 2 ，c 3 ) ， c 3 ，c 4 。要强调 的魁实际的解不定是这三个最小诊断集台乏，只是在遂个简单门电路的领域中， 最小诊断是实际解鞠机会极大，我嚣3 在诊断筛选黠把非最小诊断在开始对跫经排除。 在裁下熬最拳诊辩串要我搿骤个方蓬簿，可疆逶建更多豹镶蠛螽 琴童按爨鼗，霹戳 通过镢域知识决定增加检测患然矮再求诊麟，或者是通过入工判断。翔俺筵好遣在零l 入领域知识的同时，保持m b d 算法和具体领域知识的独立，4 2 节提出了一个m b d 的扩展以解决这个问题。 4 1 3 正常观察值的利用 在m b d 钓蒸本算法孛，馥s 孛只有雾辩熟竞转x 酶能为真) 才霹葵法有强， 两蓬鬻懿元薛x 婊( x j 或煮1a b ( x ) 受囊) 在冀潼零察霹憨鲢蹩莰毒疑霭佟瘸静。餐在 现实世界，一个系统中观察到芷常盼值往往辩出错元件的定位是有用的。 如果仅用第：章的m b d 涧题定义及m b d 算法出锩元件的诊断烈使用到o b s 中不难常的元件，对于正常元 牛数目的多少敷哪些元件是臌常的并不关心。在本章后 露墨节奔绥豹m b d 扩曩模型x m b d 超越逡个隈爱，o b s 歪露元终霹袋解m b d 窝嚣 麓撵有焉。 4 。2m 8 d 韵扩装 为了能用m b d 解决更多的癸际问题。m b d 模型需要避行扩展。在r e i t e r 之后也 有不少学者对传绕的m b d 模粼进行过各种潋进。而本文的扩展主要是为了克服4 1 中 提敷的闻题，同时为下一章的一个高级语言程序的诊断系统提供理论的簇础。 4 2 1 扩展的m b d 模懿x l v l b d 定义x m b d 问越是一个四元组( s d ，x s d ，c o m p , o b s ) ，其中s d 是诊麟累统豹系统 播述，x s d 是扩鼹熬系统接述，c o m p 是诊断系统蘑毒元静戆集舍，o b s 莛臻察魏集 合， x m b d 和m b d 定义中的s d 、c o ，、o b s 是相同的。x s d 是与领域有关的假设， 形式和s d 一样，可以是与元件类型相适应的元件的描谶，或者元件间泌系的描述。 s d 与x s d 豹分别是，s d 是描述元箨本身的筻曼震、元件勰的实琢关系，s d 毽哥包鸯 1 5 领域知识。而x s d 与s d 的客观描述不同，它只是关于元件性质、元件间关系的假设 这种假设必须是与领域知识联系起来的，在一定范围内是被认为是正确的。 定义x m b d 的冲突( c o n f l i c t ) 。c o c o m p 是x m b d 问题( s d ，x s d ，c o m p , o b s ) 的一个冲突，当且仅当肋u x s d u o b s u o k ( c ) ic c o 是不一致的。 定义x m b d 的最小冲突。c o c o m p 是x m b d 问题( s d ，x s d ，c o m eo b s ) 的 一个最小冲突，如果c o 是这个x m b d 问题的冲突且c o 的任意真子集都不是这个 x m b d 问题的冲突。 定义n m b d 的诊断( d i a g n o s i s ) 。a c o m p 是x m b d 问题( s d ，x s d ，c o m p , o b s ) 的一个诊断，当且仅当s d w 盈u o b s u o k ( c ) 1c c o m p ) 是一致的。 定义x m b d 的最小诊断是x m b d 问题( s d ，x s d ，c o m p , o b s ) 的一个最小诊断， 当且仅当是这个x m b d 问题的诊断且的任意真子集都不是这个x m b d 问题的诊 断。 m b d 问题扩展为x m b d 问题后，在冲突和诊断的定义中直接增加x s d ，而x s d 和s d 的元素都是命题，因此原来的m b d 问题的诊断算法仍然可以在x m b d 问题上 使用。在问题的求解时，完全可以将x s d 的所有命题加入s d ，然后按照m i l d 问题的 求解算法求解。当然，这样做是可行的，但对于具体的应用，这不是唯一的求解方法， 也未必是最好的方法。在本文下一章介绍的诊断系统中，并没有用这种方法求解x m b d 问题。 4 2 2x m b d 的性质 定理1如果a1 是( s d ，x s d l ，c o m p , o b s ) 的诊断，且x s d 2 x s d i ，则a1 是 ( s d ，x s d 2 ，c o m p , o b s ) 的诊断。 证明：因为a1 是( s d ，c o m p , o b s ，x s d i ) 的诊断，根据定义 s d w x s d l u o b s u a l u o k ( c ) ic c o m p 1 ) 是一致的。 因为x s d 2 c x s d i ， 得t j x s d 2w o b s u 厶lu o k ( c ) i c c o m p a 1 ) 中山大学硕士论文 扩展的m b d 模型和c o b o l 程序诊断 s d u x s d i u o b s u a l u o k ( c ) 1c c o m p a 1 ) ， 所以s d u x s d 2 uo _ 骆u a l u 撕( c ) l c c o m p a i 也是一致的， 再由定义得a1 是( s d ，x s d 2 ，c o m p ，o b s ) 的诊断。 推论ix m b d 问题的诊断是对应的m b d 问题的诊断。 证明：对于任意一个x m b d 问题，设它的四元组形式为( s d ，x s d ，c o m p , o b s ) ，诊断 为，则其对应的m b d 问题是( s d ，c o m p , o b s ) 。 因为由c x s d ，根据定理l 是( s d ，由，c o m p , o b s ) i 扮诊断a 由定义得 肋u 中u o b s u u o k ( c ) lc c o m p a ) 是一致的， 即s d u o b s u u o k ( c ) ic c o m p a ) 是一致的， 由m b d 定义，a 是m b d 问题( s d ，c o m p , o b s ) 的诊断。 定理2 如果a1 是( s d ，x s d i ，c o m p , o b s ) 的i d 、诊断，x s d 2 x s d l ，则存在2 ，满 足2 是( s d ，x s d 2 ，c o m p , o b s ) 的最小诊断，且a 2 c 1 。 证明：a1 是( s d ，x s d l ，c o m p , o b s ) 的最小诊断，则a1 是( s d ，x s d l ，c o m p , o b s ) 的诊断。 因为x s d 2 璧x s d l ，由定理1 得a1 是( s d ，x s d 2 ，c o m p , o b s ) 的诊断。 i ) 如果a1 是( s d ，x s d 2 ，c o m p , o b s ) 的最小诊断， 令a2 _ i ，则2 是( s d ，x s d 2 ，c o m p , o b s ) i 拘最d , 诊断， 且2 = l l i i ) 如果i 不是( s d ，x s d 2 ，c o m p , o b s ) 的最小诊断， 则必存在a 2c - ai ，且2 是( s d ，x s d 2 ，c o m p , o b s ) 最小诊断。 推论2 如果x m b d 问题有一个最小诊断i ，则对应的m b d 问题必定有一个最小 诊断2 ，且a2 1 。 证明：对于任意一个x m b d 问题，设它的四元形式h ( s d ，x s d ，c o m p , o b s ) ，则其对 应的m b d 问题是( s d ，c o m p , o b s ) 。 因为a1 是( s d ，x s d ，c o m p , o b s ) 的最小诊断，由x s d ，由定理2 得：存在a2 是( s d ， 巾c o m b o b s ) 的最小诊断，且a2 _ c 1 。 因为2 是( s d ，巾，c o m p , o b s ) 的最小诊断，所以2 是( s d ，中，c o m p , o b s ) 。由 x m b d 问题的诊断的定义得 s d u o b s u 2u o k ( c ) lc c o m p 2 ) 是一致的，即 u o b s u 2u o k ( c ) ic c o m p a 2 ) 是一致的。 根据m b d 问题的诊断的定义，2 是( s d ，c o m f , o b s ) 的诊断。假设2 不是最小诊断 则存在a3 c 2 ，且a3 是( s d ，c o m p , o b s ) 的诊断，即 s d u o b s u j u o k ( c ) lc c o m p a 3 ) 是一致的。 得u o u o b s u a 3 u 幽( c ) lc c o m p 3 是一致的。 因此3 是( s d ，中，c o m p , o b s ) 的诊断，这与a2 是( s d ，由，c o m p , o b s ) 的最d , 诊断矛 盾，故假设不成立。a2 是( s d ，c o m p , o b s ) 的最小诊断。 由结论和，a 2 是对应m b d 问题的最小诊断，且2 c i 。 定理3 如果c 0 1 是( s d ，x s d l ，c o m p , o b s ) 的一个冲突，且x s d l c x s d 2 ，则c o l 是 ( s d ，x s d 2 ，c o m p , o b s ) 的冲突。 证明：因为c 0 1 是( s d ，x s d l ，c o m p , o b s ) 的一个冲突，根据定义， u x s d iu o b s u o k ( c ) lc c 0 1 ) 是不一致的。 又因为x s d l c x s d 2 ，所以 s d u x s d 2u o b s u o k ( c ) ic c o , ) 是不一致的。 再由定义得c o l 是( s d ，c o m p , o b s ，x s d 2 ) 的冲突。 推论3m b d 问题的冲突也是其对应的任意一个x m b d 问题的冲突。 证明：对于任意一个m b d 问题，设它的三元组形式为( s d ，c o m p , o b s ) ，则其对应的 任意一个x m b d i 问题的四元组形式为( s d ，x s d i ，c o m p , o b s ) 。 设这个m b d 问题的任意一个冲突是c o 。由m b d 的冲突定义， u o b s u o k ( c ) c c o 是不一致的，即 s d u 中k j o b s u o k ( c ) jc c o ) 是不一致的。 由x m b d 的冲突定义，c o 是x m b dl