（计算机软件与理论专业论文）基于错误解释的故障定位方法研究.pdf

硕士学位论文 m a s t e r st h e s i s 中文摘要 计算机系统的飞速发展给软件提出了更高的要求，如何提高软件质量这一课题 的研究越来越得到人们的重视，而软件的可靠性、正确性、安全性等性质是保证软 件具有高质量的关键因素。当软件发生故障后，怎样定位软件故障是当今软件故障 领域的热点。 对故障进行定位是程序诊断的核心问题。当软件失效后，一个模型检查器将自 动产生一个反例，这个反例表现出不正常的行为。但是，用户必须确定这个反例是 否真的表现出了错误的行为，还是这个反例它仅仅是由于不正确说明文档而引起 的。当已知存在故障，隔离和修改系统的故障部分将是一件十分困难的工作。本论 文是在研究了已有的相似度量方法和错误解释技术方法之后，定义了一种相似度量 标准，该标准是基于数据流差异的，提出了一种基于错误解释的故障定位方法，该 方法是基于g r o c e 方法之上的。最后，用一个简单的程序进行故障定位试验，通过 对试验结果的分析和比较，表明了特别在定位与数据流有关的程序故障方面，本文 所提的故障定位方法能够有效地进行故障定位。 本文主要作了以下几部分的研究工作： ( 1 ) 研究了基于数据流的相似度量标准 定义了一种基于数据流差异的相似度量标准，该相似度量标准是用程序间的路 径距离来衡量的，本文给出了路径距离的具体算法，并将该算法运用到了基于错误 解释的故障定位方法中。 ( 2 ) 基于错误解释的故障定位方法研究 在故障定位的前期使用静态切片，提出了基于错误解释的故障定位方法。g r o c e 提出的故障定位方法是在比较反例与最相似成功路径的差异阶段使用动态切片( 差 异切片) ，在前期处理的代码量比较多，且需要动态追踪程序的执行历史，其执行 代价较高。本文针对以上问题，在前期使用静态切片( k j o t t e n s t e i n 和l m o t t e n s t e i n 的过程内切片) ，减少了后期处理的代码量，使得解释方法更有针对性。在此基础 上，提出了基于错误解释的故障定位方法，该方法能够有效地解决与程序数据流有 关的故障。 ( 3 ) 实验结果分析 采用本文提出的故障定位方法，以一个具体的c 语言程序为例，在本文提出的 距离度量算法的基础上，进行了故障定位试验，并进行了实验分析，实验证明该方 法在定位与数据流相关的程序故障时精度较高。 关键词：故障定位；错误解释：静态单赋值：距离度量；过程内切片 硕士学位论文 m a s t e r + st h e s i s a b s t r a c t 鼢t h ed e v e l o p m e n to fc o m p u t e rs y s t e m , d e m a n d so fs o f t w a r eb e c o m em o r ea n d m o r eh i g h e r , s ow eh a v eb e c o m ei n c r e a s i n g l yc o n c e r n e da b o u tt h er e s e a r c hp r o j e c to f e n h a n c i n gs o f t w a r eq u a l i t y 砀er e l i a b i l i t y , a c c u r a c y , s e c u r i t yo fs o f t w a r ea r et h ek e y f a c t o r so fe n s u r i n gs o f t w a r eh a v eh i g h e rq u a l i t y n o w , h o wt ol o c a t es o f t w a r ef a i l u r e a f t e ri tw a sw r o n gi st h eh o ts p o ti n 也ea r e ao fs o f t w a r ef a i l u r e l o c a t i n go ft h ec a u s eo fs o f t w a r ef a i l u r ei st h eh e a r to fp r o c e d u r ed i a g n o s e 铎盈钮 t h es o f t w a r ei sf a i l u r e ，am o d e lc h e c k e rw i l la u t o m a t i c a l l yp r o d u c eac o u n t e r e x a m p l e ， t h i se o u n t e r e x a m p l es h o ws o m ea b n o r m a lb e h a v i o r h o w e v e r , t h eu s e rm u s td e c i d ei ft h e e o u n t e r e x a m p l eg e n u i n e l ys h o w se r r o n e o u sb e h a v i o ro ri ti sj u s tc a u s e db yi n c o r r e c t s p e c i f i c a t i o n i nt h ee v e n tt h a tt h ee r r o ri sr e a l ，t h e r er e m a i n st h ec h a l l e n g i n gt a s kt o i s o l a t ea n dm o d i f yt h ef a u l t ya s p e c t so ft h es y s t e m n er e s e a r c ho ft h i sp a p e ri sb a s e do n s i m i l a r i t yp a t hm e a s u r e m e n ta n de r r o re x p l a n a t i o n 舱d e s c r i b eap a t hs i m i l a r i t y m e a s u r e m e n ta l g o r i t h mf o rd a t af l o wd i f f e r e n c ea n daf a u l tl o c a t i o nm e t h o db a s e do n e r r o re x p l a n a t i o nw h i c hb a s e do ng r o c e sm e t h o d f i n a l l y , w eu s ea s i m p l ep r o g r a mt o d ot h ee x p e r i m e n to ff a u l tl o c a t i o n , w i t hc o n t r a s ta n da n a l y s i so ft h et e s tr e s u l t s ，i ts h o w t h a tt h em e t h o do fp r o c e d u r ef a u l tl o c a t i o nm e n t i o n e di nt h i sa r t i c l ei nh a n d l i n gt h ed a t a f l o we r r o r sc a nb ee f f e c t i v e l yl o c a t e df a u l t i no u rr e s e a r c h , t h ef o l l o w i n ga s p e c t sh a v eb e e nr e s e a r c h e d ： 1 t h er e s e a r c ho nt h ec r i t e r i o nf o rs i m i l a r i t ym e a s u r e m e n tb a s e do nd a t af l o w i nt h i sp a p e r , i td e f m e sas i m i l a r i t ym e a s u r e m e n tc r i t e r i o nb a s e do nd a t af l o w d i f f e r e n c e s ；i tg i v e sas p e c i f i ca l g o r i t h ma b o u tp a t hd i s t a n c e ，a n da p p l i e st h ea l g o r i t h mt o t h ef a u l tl o c a t i o na l g o r i t h mb a s e do na ne r r o r e x p l a n a t i o n 2 r e s e a r c ho nf a u l tl o c a t i o nb a s e do ne r r o re x p l a n a t i o n i nt h i sp a p e r , 、航t ht h eu s eo fs t a t i cs l i c i n gi nt h ep r o p h a s eo ft h ef a u l tl o c a t i o n , a f a u l tl o c a t i o nm e t h o db a s e do ne r r o re x p l a n a t i o ni sp r o p o s e d g r o c ep r o p o s e daf a u l t l o c a t i o nm e t h o dw i t ht h eu s eo fd y n a r n i es l i c e ( s l i c e ) i nt h el a t ep e r i o d , s ot h ec o d e a m o u n ti nt h ep r e - p r o c e s s i n gi sm o r e ，a n dn e e d sd y n a m i ct r a c i n gt h eh i s t o r yo f p r o c e d u r e e x e c u t i n g ，t h ec o s ti sm u c hh i g h e r i no r d e rt os o l v ea b o v ep r o b l e m s ，w eu s et h es t a t i c s l i c e ( t h ei n t e r p r o c e d u a ls l i c i n go fk j o t t e n s t e i na n dl m o t t e n s t e i n ) i nt h ep r o p h a s e ，s oi t r e d u c e st h ec o d ea m o u n ti nt h el a t ep e r i o d , m a k i n ge r r o re x p l a n a t i o nb e t t e r o nt h i sb a s i s ， am e t h o do ff a u l tl o c a t i o nb a s e do ne r r o re x p l a n a t i o ni sp r o p o s e d 3 ，n l ea n a l y s i so fe x p e r i m e n t a lr e s u l t s a c c o r d i n gt ot h ef a u l tl o c a t i o nm e t h o dm e n t i o n e di nt h i sa r t i c l e , u s i n gas p e c i f i cc p r o g r a m 弱a ne x a m p l ea n do nt h eb a s i so ft h ed i s t a n c em e a s u r e m e n ta l g o r i t h m m e n t i o n e di nt h i sa r t i c l e ，w ed oaf a u l tl o c a t i o ne x p e r i m e n t , a n dg i v et h ea n a l y s i so f e x p e r i m e n t a lr e s u l t s t h er e s u l t ss h o wt h a tt h ep r o p o s e dm e t h o dh a sh i 业a c c u r a c yi n l o c a l i z i n gt h ep r o g r a mf a u l t sr e l a t e dt op r o g r a md a t af l o we r r o r s k 呵w o r d s ：f a u l tl o c a t i o n ；e r r o re x p l a n a t i o n ；s t a t i cs i n g l ea s s i g n m e n t ；d i s t a n c e m e a s u r e ；i n t e r p r o c e d u a ls l i c i n g 硕士学位论文 m a s t e r st h e s i s 华中师范大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，独立进行研究工作 所取得的研究成果。除文中已经标明引用的内容外，本论文不包含任何其他个人或 集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已在 文中以明确方式标明。本声明的法律结果由本人承担。 作者签名：卸 i ，桕 日期：钏7 年6 月7 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有权 保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借 阅。本人授权华中师范大学可以将本学位论文的全部或部分内容编入有关数据库进 行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。同意华中 师范大学可以用不同方式在不同媒体上发表、传播学位论文的全部或部分内容。 作者签名：邹j 、桷 日期：啪降6 月1 日 导师签名： 日期： 叶5 踊 l 卅年6 f 月f 日 本人已经认真阅读“c a l i s 高校学位论文全文数据库发布章程”，同意将本人的 学位论文提交“c a l i s 高校学位论文全文数据库 中全文发布，并可按“章程 中的 规定享受相关权益。回童途塞握变卮澄卮；旦圭生；旦= 生；旦三生发查。 作者签名：鄞 i 、橡 日期：伽7 年6b 日鼬旧 秘月0 ：qh爱叶 戤 师期 争日 硕士学位论文 m a s t e r st h e s i s 第一章绪论 随着计算机技术的快速发展，计算机已经普遍应用于人们的日常生活和关键控 制领域当中。计算机在这些应用领域中起着十分重要的作用，例如计算机应用于航 空、银行、医疗、工业控制、核武器等一些关键领域当中，它一旦发生错误要么威 胁人们的生命安全，要么会造成巨大经济损失。在一些非安全关键领域，比如说超 市、学校等等这些非安全关键领域，计算机在其中扮演的角色也十分的重要，一旦 发生错误将会造成一些重要的信息丢失、管理混乱。所以人们对计算机的要求也越 来越高，一方面要求硬件可靠，另一方面同时也要求软件可靠。但是因为计算机软 件开发的各个阶段都需要人的参与，并且随着软件功能的日益强大，软件规模也随 之变得越来越大，导致软件出错的可能性也越来越大。因此，怎样提高软件质量， 保证软件的可靠性已经成为软件开发人员十分关注的问题。 软件质量在现实生活中扮演着很重要的角色。当软件发生故障后，快速找到使 软件出现故障的错误原因并且准确地进行软件故障定位，这是一项十分艰巨且有挑 战性的工作，它在软件开发和维护过程当中，将会消耗掉很多的人力和物力l j 引。因 此，人们十分希望能够找到一种可靠的并且实用的软件自动化的调试技术。 1 1 论文研究背景 程序的调试过程是一个找出程序代码中存在的错误并且改正错误的过程，它需 要调试人员在很短的时间内找到程序中出现错误的程序代码段。它是一项既消耗时 间又浪费人力和物力的工作。程序调试人员的首要目的就是要准确地定位出现错误 的代码或者是找到出现错误的代码存在的范围。从而人们需要研究和开发新的程序 调试方法或者工具，来提高软件开发效率。 软件失效指的就是软件的预期输出和实际的输出不相同。当软件失效后，怎样 找到导致软件失效的故障位置或者是引起软件失效的故障原因，这就是程序软件的 故障定位问题。当已知软件发生失效后，我们可以研究怎么样根据软件运行时的输 入和它的运行行为来快速、准确地定位出现错误的软件故障部分，这将是一个十分 有价值的研究课题。程序软件的故障定位技术能够帮助开发人员查明失效根源，从 而减少了因调试而付出的努力。它是一个十分复杂的问题，它牵扯到软件工程领域 中的诸多问题，例如软件的测试路径生成、测试用例的自动生成方法的研究【z 4 j 、程 序切片技术和其应用的研究，还有程序的模型检查技术【6 j 和错误解释( e r r o r 硕士学位论文 m a s t e r st h e s i s e x p t a n a t i o n ) 技术的研究等等。以上所述的这些技术问题之间有着密不可分的关系， 我们想要从本质上解决其中的任何一个问题都是非常困难的。 1 2 问题描述 故障定位的方法很多，其中模型检查应用于软件故障定位已经成为近年来的一 个焦点，并且已经取得了一些成就。模型检查技术的优点是自动化程度高，当所设 计的系统不满足系统的某个性质时，模型检查工具将会返回一个反例，通过对反例 的分析可以得到性质不成立的原因，可以为修正系统提供重要线索【1 2 】。错误解释是 一种可用于定位程序故障的方法，用户靠分析失败路径和成功路径之间的不同，也 就是差异，来理解程序故障的本质，从而进行故障定位。但是目前将这两种技术结 合起来进行故障定位的研究还比较少，本文研究的问题是，研究怎样将模型验证技 术和错误解释技术进行结合，使之能够更好地进行程序故障定位。 1 3 国内外研究现状及存在问题 1 3 1 研究现状 近年来，在程序自动调试技术及软件故障定位技术方面的研究，国内外都取得 了不少的研究成果。 到目前为止，国外的研究情况主要有： d a v i dl e w i s 1 】提出的因果论的反事实分析，原因c 导致结果e 发生当且仅当如 果c 不发生的话，e 也不会发生。他还提出因果论的理论可用于错误解释，但是他 只是提出了这样一个思想，没有把这一思想进行实现。 a l e xg r 0 c e 【4 】等人提出用距离度量来进行错误解释的方法，该方法是一种能帮 助用户进行故障定位的技术，它是源于l e w i s 的因果论的反事实分析【2 6 j ，是基于程 序路径的距离度量的。他提出了一种路径距离的定义，但是没有给出具体算法，并 且他是在后期对程序使用程序的差异切片，在此基础上再来分析反例和与之最为相 似的成功路径之间的差异，计算代价太大。 r u ia b r e u 等【8 1 提出的一种软件多故障定位的动态建模方法，它是一种基于模型 的方法，在该方法中，从动态执行行为得到程序模型，并用人工合成的程序和西门 子软件基准这两者来评估它的诊断性能，他们在程序和基准中扩展之以此来提供多 重故障。该方法能定位多重故障，它采用动态执行行为来进行故障诊断，诊断结果 比较精确。但是该方法在碰撞集的计算方面比较复杂，时间代价比较大。 r u ia b r e u 等瞄】提出了另外一种基于观察者模型的故障定位，该方法也是一种 2 硕士学位论文 m a s t e r st h e s i s 动态建模方法，它是基于对程序执行轨迹上的逻辑推理，他们提出了一种简单的诊 断性能模型在不同参数下的影响，比如说测试集大小和覆盖率，用这个诊断结果来 定位软件故障的根本原因。该方法能定位多重故障，但是该方法需要依赖于足够多 的测试案例。 p e g g yc e l l i e r 等1 9 讨论了形式化的概念分析f f o r m a lc o n c e p t 加1 a l y s l 。s j 日 - 匕i a 有助于 故障定位，他们考虑到了有故障的代码行的一些关联规则，用形式化的概念分析来 分析这些规则，以此来提高包含在规则里的信息的可读性。对于程序员知道故障的 大概位置还有仅仅能跟踪一部分的轨迹的程序来说，该方法比较有效。因此它的适 用范围不太广。 w a n g 等【7 】提出了一种相似路径集的生成算法，该算法是基于控制流度量的。 w a n g 提出的算法思想是在失效路径的领域附近，我们可以通过改变分支条件的真 假的取值情况来寻找和生成与失效路径最为相近的路径，他们提出的算法并没有保 证所生成路径是否可行。但是他所提出的算法对于定位有关数据流的程序故障作用 不太大。 d e n n i sj e f f r e y 等【1 0 】分析了用值替代来定位故障，其基本思想是他们先根据故障 的可能性来把程序语句进行分类，有故障的程序语句中用到的值，如果改变这些值， 程序就能输出正确的结果。这种方法对于那些有错的语句或者是只有一条有错的语 句是很有效的。 国内在故障定位方面的研究情况主要有： 朱凯【l l 】也提出了一种相似路径集的生成算法，该算法的思想是基于失效路径无 约束边的，主要是通过分析失效路径和相似成功路径的差异，在此基础上再来进行 故障定位的。雷志翔【2 1 】在朱凯工作的基础上，对相似路径集的生成算法进行了改进， 并实现了该算法。朱和雷的工作对于定位与控制流有关的程序故障比较有效，但是 对于与数据流有关的程序故障效果不太显著。 1 3 2 当前存在的问题 在应用程序的开发过程中，由于各种原因，应用程序中不可避免地存在着一些 故障。目前，故障定位方面的技术研究也比较多，但这些技术研究中或多或少存在 一些问题，具体如下： ( 1 ) 朱凯和雷志翔都是采用程序的控制流进行路径问的相似性度量，所获得的相 似路径可用于定位与控制流有关的故障，但不能用来处理一些与数据流有关的故 障。 3 硕士学位论文 m a s t e r st h e s i s ( 2 ) g - r o t e 提出的错误解释技术，是在后期对程序进行切片，在前期将一些无用 的变量也表示为静态单赋值形式，浪费了大量的时间。 1 4 本文研究目标和主要研究工作 本文的研究对象是程序自动调试中的故障定位技术。本文的大背景是软件测 试，是在已有的模型检查的方法中再加入错误解释的思想，给出了一种程序调试方 法，该方法被称为基于错误解释的故障定位方法。本文的研究重点和核心内容将包 括以下几个方面： ( 1 ) 定义一种基于数据流差异的相似度量标准，用该标准来衡量两条路径之 间的相似性，以此来找到与反例最相近的成功路径。 ( 2 ) 对g r o t e 的基于错误解释的故障定位方法进行改进，使用前期切片进行 处理，且选用的是程序静态内切片，执行代价较小，最后提出具体算法并进行故障 定位实验，并对实验结果进行分析。 其中，基于错误解释的故障定位方法的原理是当程序出现故障后，对程序进行 切片，模型检查器根据程序的静态单赋值形式和规约来产生反例，根据反例来生成 相似的成功路径，再用路径距离来度量成功路径和失效路径间的差异，找到最相似 的成功路径，最后对差异进行比较和分析进行错误解释，从而来达到故障定位的目 的。 1 5 论文的组织结构 论文共分6 章： 第1 章：绪论。介绍论文的研究背景和意义、国内外研究现状，给出了研究目 标、主要研究内容和论文的组织结构。 第2 章：研究基础。主要包括程序分析技术、静态单赋值技术、故障解释技术、 程序切片相关的知识。 第3 章：距离度量的研究。详细描述了路径距离的思想，并给出了路径距离的 具体算法，以此路径距离来度量路径之间的相似性。 第4 章：基于错误解释的故障定位方法。本章在第3 章讨论的距离度量的基础 上，讨论了错误解释的生成，其中包括程序路径的表示，找到最相似的成功路径， 和分析失效路径和成功路径之间的差异得到一个错误解释，从而来进行故障定位。 第5 章：以一个具体的c 语言程序为研究对象进行了程序故障定位的试验，用 这个实例的方式来具体讨论怎样来度量路径之间的相似程度，和怎样生成最相似的 4 硕士学位论文 m a s t e r st h e s i s 成功路径，最后还具体分析了最相似成功路径和反例之间的差异，以此来进行错误 解释和故障定位。 第6 章：总结与展望。对本研究的创新与贡献进行了总结，并指出了本故障定 位方法的不足之处以及以后的进一步工作。 5 第二章研究基础 2 1 程序分析技术 2 1 1 控钥流图 在程序中，一般都会有一些连续的多行程序代码，它们形成程序中一个个相对 独立的构造语句块，并且都具有这样一个特性，那就是只能通过构造语句块的第一 条语句进入，通过最后一条语句离开构造语句块。 程序的基本模块有如下的一些定义： 定义2 1 一个基本模块指的就是程序中的一组连贯的语句，语句中的控制流在 模块开始时进入，在模块结束时离开，而不可能在除模块结束之外的地方停止或出 现。 由上面的定义可知，每个基本模块都有且只有一个入口和出口，控制流都只能 从模块的入口处进入基本模块，从模块的出口处离开基本模块。 定义2 2 一个控制流图g 指的就是一个有向图，该有向图的节点就是一个基本 模块，该模块是一个具有唯一入口和唯一出口的模块。如果有两个基本模块a 和b ， 控制可以直接从a 流向b ，那么的话从节点a 到节点b 有一条有向边。 控制流图是程序分析领域中一个十分重要的概念，它可以把源程序用图的形式 表示出来，在控制流图上可以很方便地分析一些问题，比如说语句间的前趋关系和 后继关系、支配节点、后支配节点以及程序执行路径等等相关问题。在这些概念的 基础上，我们就可以进一步分析语句间的控制依赖和依赖关系。在控制流图中，我 们用节点表示程序中的基本模块，边表示基本模块之间的关系。 2 1 2 控制流分析 控制流分析就是去寻找程序过程内或过程间的控制流。所谓程序过程内控制 流，它主要是指一个过程的各条语句之间的控制流，它一般包含三种基本程序结构 引起的控制流关系以及一些控制语句引起的控制流关系。程序过程间的控制流主要 指的是由过程调用引起的。这里我们主要分析的是程序过程内的控制流。控制流分 析一般包括两个部分：构造控制流图( c f g ，c o n t r o f t o wg r a p h ) ，寻找控 制流图中的控制点( d o m i n a n c e ) 、后控制点( p o s t - d o m i n a n c e ) 和控制边境 ( d o m i n a n tf r o n t i e r ) 等等。这里我们用形式化方式来描述控制流图，如下： 6 硕士学位论文 m a s t e r st h e s i s 定义2 3 控制流图控制流图的定义可描述为一个三元组，形式如：g = ，该三元组中( n ，e ) 是表示的是一个有向图，n 表示的是节点的集合，e 表示的是有向边的集合，r o o t 表示的是根节点，从该根节点出发到图中的任意的一 个节点都有相应的路径存在。 在一个控制流图中，节点表示的是基本模块或者是语句，有向边指的是从前驱 的节点指向后继的节点。控制流图表示的是程序语句之间的控制流，通过该图，我 们可以知道程序语句之间的关系，以及语句执行时的流向。 定义2 4 控制点从控制流图的根节点到一个节点的所有路径上都包含的节点 为该节点的控制点。由控制点的定义可知，直接控制点( i m m e d i a t ed o m i n a n c e ) 的定义可以描述为：当且仅当不存在这样一个节点c ( c 与a 和b 都不相等) ，使a 控制c ，同时c 控制b 成立，那么这样就可以说a 直接控制b ( a 与b 不相等) 。 定义2 5 后控制点从节点x 到控制流图的出口节点的所有路径都包含的节点 称为节点的后控制点，我们用l d ( x ) 来表示。 定义2 6 控制边境节点x 的控制边境我们用d f ( x ) 来表示，d f ( x ) 的定义如下： ，、 d s ( x ) = i zi3 y p r e d ( z ) ，3 y p r b d ( z ) ，, 驻m o m yax d o r k j 在上述定义中，p r e d ( z ) 表示的是z 节点在控制流图上的前驱节点集，x d o m y 表示x 控制y ，x 为y 的控制点。由控制边境的定义可知，虽然说节点x 能够控制 它的控制边境z 的一部分前驱，但是它不能控制z 的所有的前驱。 2 1 3 数据流分析 数据流描述的是变量的值从它们的定义点怎样流到它们的使用点。数据流分析 指的就是通过检查静态代码来导出关于程序动态行为的信息。数据流分析，英文简 写为d f a ( d a t af l o wa n a l y s i s ) ，它指的是分析程序中所有变量的定值( 即指对变量 赋值或输入值) 和引用之间关系的过程。 数据流分析分为两种，一种是过程内的数据流分析，另一种是过程间的数据流 分析，一般来说，过程内的数据流分析常见的包括表达式分析、活跃变量分析、使 用定义链分析，过程间的数据流分析包括形式边界集体、可能别名和可能被修改。 一般来说，对基本的数据流方程的求解进行抽象可以被认为是有关数据流的分 7 析问题。数据流分析依据的是控制流的走向，从这个方面来说，数据流分析可以分 为两种，一种是正向的数据流分析，另一种是反向的数据流分析。正向的数据流分 析指的就是我们可以根据一个基本块的入口处的数据流值来计算该块出口处的数 据流值。与之恰好相反，反向的数据流分析指的是根据一个基本块的出口处的数据 流值计算该块的入口处的数据流值。 基木块间数据流值的汇合方式有两种，用n 和u 来表示。比如说，在一个正向 的数据流分析中，我们可以这样计算基本块的入口处的数据流值，它就等于从该块 的所有前驱的基本块的出口处的数据流的值的累加和，也就是汇合，但是在反向的 数据流方程中，情况就刚好相反，基本块的出口处的数据流值它是等于该块的所有 后继的基本块的入口处的数据流的值的累加和( 汇合) 。当然有时候我们也不需要 区分n 和u ，那么我们可以用m e r g e 来表示n 和u 其中之一。 我们可以这样来定义正向数据流分析的基本方程，如下图，方程如下： f o u r ( b ) = ( 川印一k i l l ( b ) ) ug e n ( b ) 1 川固= 朋g 曙窖( d u 丁( p ) ) l ，e ，撑武印 在上面的方程中，p r e d ( b ) 所代表的意思是控制流图中基本块b 的前驱节点的 集合。 同样，我们可以这样来定义反向数据流分析的基本方程，如下图，方程如下： ii n ( b ) = ( o u t ( b ) 一删珂( 且) ) uu z g ( b ) 1o u t ( b ) = 脚窖，寥( 五i | ，( s ) ) l j e 铀c c ( o i 在上面的方程中，s u c c ( b ) 所代表的意思就是控制流图中基本块b 的后继节点 的集合。 传统的数据流分析方法，一般都是基于程序的控制流图的，使用的方法就是迭 代法。就拿j 下向的数据流方程来说，我们可以采用深度为主的顺序进行计算，比如 我们常见的定值一引用链分析；同样地，对于反向的数据流方程，我们可以采用深 度为主的逆序进行计算，比如说引用一定值链分析。 8 硕士学位论文 m a s t e r st h e s i s 到目前为止，已经存在了许多的数据流分析算法，比较常见的就有迭代算法、 消除算法、可达性算法等等。 下面我们就来看下迭代算法，迭代算法的主要思想是它可以通过把节点初始化 为可靠的值，然后我们再来连续地计算这些变量的值，直到该值不再发生变化，也 就是固点，用这种方式来解决一个等式系统；或者可以采用不停地重复计算所有节 点的数据流的属性，到该属性的值不再发生变化，也就是到达了稳定的状态。在用 迭代法求解的算法中，我们还需要注意两点，一点就是，像需要利用其所有前驱( 或 后继) 信息进行u 运算以此来获得该方程本身的一些相关信息的这样一类的方程， 我们采取的方法就是让它的迭代初值都取最小值；另一点与第一点类似，就是像需 要利用其所有前驱( 或后继) 信息进行n 运算以此来获得该方程本身的一些相关信 息的这样一类的方程，我们可以让它的迭代初值都取最大值。 对于消去算法，它的主要优点就是可以通过利用流图的结构属性来减少有关的 数据流问题，从而可以减少我们所需要作的大量工作。消去算法的主要思想就是可 以把连续地把应用图进行转换，以此来把流图归约到一个点上去，这里图的转换指 的就是，我们采用图的分析或者是图的分裂来确定一个区间，以此来得到一个派生 图。这样的话，在一个区间内，我们可以用区间内头节点的数据流的属性来对数据 流属性的值进行确定。从而我们就能延迟替代联立方程中的一些值。 早在19 9 4 年，就有人提出了可达性算法，他们是哥本哈根大学的t h o m a sr e p s 和m o o t ys a g i v 等一些人。他们提出的可达性算法的主要思想是把过程间数据流问 题转换成另一种比较特殊的图形可达性问题( 这里的可达性指的是沿着过程间即可 以对路径进行实现) ，最后该问题就变化为对有效的图的算法的解决。但是该算法 还有一个很大的缺点，那就是一方面数据流的集合是有限的，另一方面数据流函数 分布在集合的操作上，这里的集合操作指的是并或交的集合操作。但不管怎么说， 该算法可以解决一大类的过程间的数据流分析问题。 2 1 4 数据依赖和控制依赖分析 这里我们来对两种依赖进行分析，控制依赖一般用于表示因为控制流而导致的 9 硕士学位论文 m a s t e r st h e s i s 程序实体与程序实体间的关系；而对于数据依赖来说，它常用于表示程序中因为数 据的定义和使用而形成的实体与实体间的关系。 定义2 7 控制依赖这里g 表示的是一个控制流图，n 1 和n 2 表示的是控制流图 g 中的节点，若下列三个条件满足都的话，我们就认为n 2 控制依赖n 1 ，可以用c d ( n 1 ，n 1 ) 来表示。 1 ) 在节点n 1 和n 2 之间存在一条可执行路径p ； 2 ) 在执行路径p 上，对于除了节点n 1 和n 2 的每个节点n ，节点n 2 都是它的 后控制点； 3 ) 节点n 2 不是节点n 1 的后控制点。 程序中的依赖关系有两种，一种是语句间的控制依赖，另一种就是变量数据间 的数据依赖。上面我们简单介绍了控制依赖，下面我们再来看下数据依赖。它的形 式化定义如下： 定义2 8 数据流直接依赖设n 1 ，n 2 为控制流图中的两个节点，v 为一个程序 变量，如果下列三个条件都满足的话，就可以称n 1 关于变量v 数据流直接依赖节 点n 2 ，我们用d d ( n l ，n 2 ，v ) 来表示。 1 ) 节点n 2 对变量v 进行了定义，也就是v ed e f n 2 】； 2 ) 节点n 1 执行时使用了变量v 的值，也就是v eu s e n 1 = 3 ) 节点n 2 与节点n 1 间存在一条可执行路径，并且没有语句在该条可执行路 径上对变量v 重新进行定义。 定义2 9 数据依赖设n 1 ，n 2 为程序p 中的两个语句，若3v ( v 为变量) 满 足这一个函数d d ( n l ，n 2 ，v ) ，我们就可以称作语句n 1 数据依赖n 2 ，可以用 d d ( n l ，n 2 ) 来表示。 定义2 1 0 可到达定义如果节点s 是数据依赖于节点d 的，我们就称节点d 是s 的一个可到达定义。 2 1 5 程序依赖图 按照j f c r r n a t e 等人于1 9 8 7 年的定义，程序依赖图由三个部分组成，一个是控 1 0 硕士学位论文 m a s t e r st h e s i s 制流图，一个是控制依赖图( c o n t r o d e p e n d e n c eg r a p h ，c d g ) ，还有一个是数 据依赖图( d a t ad e p e n d e n c eg r a p h ，d d g ) 。其中，控制流图描述了一个程序中的 控制流，它和正常情况下的流图相类似；控制依赖图包含了程序中的控制依赖；数 据依赖图指的是一个程序中语句之间所有数据依赖的集合。控制依赖图包含几种类 型的节点，节点为如下几种：语句节点表示的是程序中的语句；域节点总括了 域中语句间的控制依赖；谓词节点( 由此可以引出两条边) 表示的是程序中的策 略或分支条件。控制依赖图中的域节点可利用相同的控制依赖来把语句进行组合。 数据依赖图包含语句间的数据依赖。我们可以通过在控制依赖图的节点之间插入数 据依赖边来构造数据依赖图。 定义2 1 2 控制依赖图用有向图( n ，c ) 来表示，其中节点集n 表示的是程序 中所有语句对应的节点集合，c 表示的是边集；对于语句s 1 ，s 2 ，如果有s 1 直接控 制依赖于s 2 ，表示为c d ( s l ，s 2 ) ，则把边s 1 一s 2 加入到边集c 中。 定义2 1 3 数据依赖用有向图( n ，d ) 来表示，其中节点集n 表示的是程序中 所有语句对应的节点集合，d 表示的是边集；对于语句s 1 ，s 2 ，如果有s 1 数据依 赖于s 2 ，表示为d d ( s l ，s 2 ) ，则把边s 1 一s 2 加入到边集d 中。 定义2 1 4 设( n ，c ) ，( n ，d ) 分别是程序p 的控制依赖图和数据依赖图， 则程序依赖图是( n ，e ) 用( n ，c u d u x ) 表示，其中x 表示程序中的其他依 赖关系。 在结构化程序中，程序依赖图一般包含过程内依赖图和过程间依赖图，过程内 依赖图针对的是只含有一个过程的程序，而过程间依赖图针对的是含有多个过程的 程序。这里我们主要讨论过程内依赖图。 过程内依赖图一般称为过程依赖图，英文简写为p d g ( p r o c e d u r ed e p e n d e n c e g r a p h ) ，该图可被用来描述一个过程，其中，图的节点表示语句和控制谓词表达式， 边包含控制依赖边和数据依赖边。控制依赖边表示的是表达式执行时依赖的控制条 件；数据依赖边表示的是语句或表达式之间的数据流。另外，每个过程依赖图还包 含一个入口节点( e n t r y ) ，该入口节点用于表示过程的入口。 2 2 静态单赋值技术基础 2 2 1 概述 我们对程序进行数据流分析时，需要找到已定义变量的使用位置，或者是要找 到在表达式中所用变量的定义位置。在数据流分析中，我们经常使用d e f - u s e 链， 它是一种可以使数据流分析变得有效的数据结构，它采用的方式是：对于流图中的 硕士学位论文 m a s t e r st h e s i s 第一条语句，用一个指针列表指向变量的所有使用位置，该指针列表是作编译器维 护的。采用这种方式的好处在于，它可以使编译器实现从使用到定义、从定义到使 用的快速转换。 如今，对于d e f - u s e 链的使用有了很大的改进，具体体现在使用静态单赋值表， 英文简写为s s a ( s t a t i cs i n g l ea s s i g n m e n t ) 。使用s s a 表的话，那么每个变量在程 序中都将有一个唯一的定义。之所以有单赋值表前加上静态两个字的原因，是因为 一个静态的定义位置很有可能会位于动态运行多次的循环结构中，也就是说，所有 的变量都不会被重新定义。 2 2 2 数据流图 一个程序的数据流图，也就是我们经常所说的是定义使用图，它能捕获程序中 的基本块的定义流。它类似与程序的控制流图，控制流图由节点、边和所有经过控 制流图的边所组成的。 用程序语言写的程序，比如说c 和j a v a 。在程序中，变量被定义为给它们赋 值，在表达式里使用它们。对于一个赋值语句，比如说x = y + z ，我们可以说该条 语句定义了变量x ，同时这条语句也使用了变量y 和z 。那么，另一条赋值语句x = x + y ，则表示该条语句定义了x 并且在右边的表达式里使用了它。程序中的变量 声明被认为是变量的定义。例如，语句i n tx ，y a 【1 0 】；为一个声明，它定义了三个 变量x ，y ，a 1 0 。一个输入函数，比如说c 里的s c a n t 函数，我们也可以认为是 定义了一个或者更多变量。例如，语句s e a n f ( “d d ”，& x ，& y ) ；定义了变量x ，y 。 同样地，对于输出函数， 比如说p r i n t f ( o u t p u t ：d w ，x + y ) ；语句，该语句可以 被认为使用或者参考了变量x 和y 。一个参数x ，如果它将值传递给一个函数，认 为它是使用或者参考x 。一个参数x ，如果它引用调用，认为它既定义也使用x 。考 虑以下的指针语句序列： z2 x ； y = z + l ； 气= 2 5 ； - y = * z + 1 ； 对于以上语句，我们可以判断出第一条语句定义了一个指针变量z ，第二条语 句定义了y 和使用了z ，第三条语句通过z 定义了x ，最后一条语句定义了y ，使用 了x ，通过指针变量z 访问了x 。但是对于矩阵来说，情况有点复杂。考虑以下用c 语言写的两条语句： 1 2 硕士学位论文 m a s t e r st h e s i s t t a ta 【1 0 l a i 】= 汁y l 我们认为第一条语句声明并定义了变量a 。