（计算机软件与理论专业论文）程序自动化调试的多谓词开关方法.pdf

中山大学硕士研究生学位论文 论文题目：程序自动化调试的多谓词开关方法 专业：计算机软件与理论 硕士生：李兵 指导教师：刘咏梅教授 摘要 程序调试是软件开发过程中最关键的环节之一，调试的开销将直接影响到软件的成 本和软件公司的收益。对于程序员来说，调试也是一个非常单调乏味的工作。因此，程 序的自动化调试方法成为了计算机领域的热点课题，得到不同领域众多研究者的关注， 继而出现了各种各样的自动化调试方法，如算法调试、切片技术、基于模型调试、基于 概率调试、基于程序状态调试、d e l t a 调试等等。 现有的大多数调试技术都是经验性的，即依靠专家经验和一些启发式性质。为此， 刘咏梅教授分析了要基于第一原理为程序调试建立一个精确的理论基础的重要性。本文 研究的起点是张翔宇教授等人提出的一种程序调试的单谓词开关方法，其主要思想是通 过改变程序运行过程中的一个谓词实例的取值使得原来错误的程序最终运行得到正确 的结果，然后根据被开关的谓词利用切片技术来确定诊断范围。但很多情况下，只对单 个谓词实例进行开关并不能够使程序得到正确的运行。针对单谓词开关算法的局限性， 本文提出有界调试的多谓词开关算法( b o u n d e dd e b u g g i n gv i am u l t i p l ep r e d i c a t es w i t c h i n g a l g o r i t h m ，b m p s ) ，通过在程序运行过程中开关多个谓词实例来得到一个正确的运行， 且在此运行中每个循环的执行次数不超过一个给定的上界。b m p s 算法可以通过一个可 满足性( s a t i s f i a b i l i t y ，s a t ) 求解器来实现。 文中讨论的程序错误主要为右端( r i g h th a n d s i d e ，r o t s ) 错误，即错误出现在控制谓 程序自动化调试的多谓词开关方法 词或者赋值语句的右边。对于只含条件控制语句的程序，本文证明了b m s 算法对于r h s 错误是准完备的，即真实错误的部分语句一定会被b m p s 算法返回。对于含循环的程序， 本文证明了当循环展开的次数足够大时，b m p s 算法对于r h s 错误是准完备的。 本文对所提b m p s 算法进行了初步的实验评估。本文深入分析了调试领域权威标准 西门子标准中的t c a s 程序，得出t c a s 程序的4 1 个错误版本中有3 9 个版本是r h s 错误。本文还对大量小型错误c 程序进行了调试实验，实验结果表明b m p s 能够有效 地锁定错误。 关键词：谓词开关、程序切片、d e l t a 调试、b m p s 、c b m c 中山大学硕士研究生学位论文 t i t l e ：a u t o m a t e dp r o g r a md e b u g g i n gv i am u l t i p l ep r e d i c a t es w i t c h i n g m a jo r ：c o m p u t e rs o f t w a r ea n dt h e o r y n a m e ：b i n gl i s u p e r v i s o r ：p r o f y o n g m e il i u a b s t r a c t p r o g r a md e b u g g i n gi so n eo ft h em o s tc r i t i c a lp a r t si nt h es o f t w a r ed e v e l o p m e n tc y c l e ， w h i c hd e r t e r m i n e st h ec o s to ft h es o f t w a r e a l s o ，i ti sat e d i o u sw o r kf o rp r o g r a m m e r s a sa r e s u l t ，a u t o m a t e dp r o g r a md e b u g g i n gh a sb e c o m eah o ts p o to fc o m p u t e rs c i e n c e ，w h i c hi s c o n c e r n e db yr e s e a r c h e r sf r o mb o mt h e o r e t i c a lc o m p u t e rs c i e n c ea n dp r a c t i c a lc o m p u t e r s c i e n c e v a r i o u sa u t o m a t i c d e b u g g i n ga p p r o a c h e sc o m eo u to n ea f t e ra n o t h e r ，i n c l u d i n g a l g o r i t h m i cd e b u g g i n g ，p r o g r a ms l i c i n g ，m o d e l - b a s e dd e b u g g i n g ，p r o b a b i l i t y b a s e d d e b u g g i n g ，p r o g r a ms t a t e b a s e dd e b u g g i n g ，d e l t ad e b u g g i n ga n ds oo n i nap r e v i o u sp a p e r ，l i ua r g u e df o rt h ei m p o r t a n c eo fe s t a b l i s h i n gap r e c i s et h e o r e t i c a l f o u n d a t i o nf o rp r o g r a md e b u g g i n gf r o mf i r s tp r i n c i p l e s i nt h i sp a p e r ，w ep r e s e n taf i r s ts t e p t o w a r d sat h e o r e t i c a le x p l o r a t i o no fp r o g r a md e b u g g i n ga l g o r i t h m s t h es t a r t i n gp o i n to fo u r w o r ki st h er e c e n td e b u g g i n ga p p r o a c hb a s e do np r e d i c a t es w i t c h i n g t h ei d e ai st os w i t c ht h e o u t c o m eo fa l li n s t a n c eo fap r e d i c a t et ob r i n gt h ep r o g r a me x e c u t i o nt oas u c c e s s f u l c o m p l e t i o na n dt h e ni d e n t i f yt h ef a u l tb ye x a m i n i n gt h es w i t c h e dp r e d i c a t e h o w e v e r ，n o t h e o r e t i c a la n a l y s i so ft h ea p p r o a c hi sa v a i l a b l e i nt h i sp a p e r ，w eg e n e r a l i z et h ea b o v ei d e a , a n dp r o p o s et h eb o u n d e dd e b u g g i n gv i am u l t i p l ep r e d i c a t es w i t c h i n g0 3 m p s ) a l g o r i t h m ， w h i c hl o c a t e sf a u l t st h r o u g hs w i t c h i n gt h eo u t c o m e so fi n s t a n c e so fm u l t i p l ep r e d i c a t e st og e t as u c c e s s f u le x e c u t i o nw h e r ee a c hl o o pi se x e c u t e df o rab o u n d e dn u m b e ro ft i m e s c l e a r l y ， b m p sc a l lb ei m p l e m e n t e db yr e s o r t i n gt oas a ts o l v e r w ef o c u sa t t e n t i o no nr h sf a u l t s ，t h a ti s ，f a u l t st h a to c c u ri nt h ec o n t r o lp r e d i c a t e sa n d r i g h t h a n d - s i d e so fa s s i g n m e n ts t a t e m e n t s w ep r o v et h a tf o rc o n d i t i o n a lp r o g r a m s ，b m p si s q u a s i - c o m p l e t ef o rr h sf a u l t si nt h es e n s et h a ts o m ep a r to fa n yt r u ed i a g n o s i sw i l lb e i i i - 程序自动化调试的多谓词开关方法 r e t u r n e db yb m p s ；a n df o ri t e r a t i v ep r o g r a m s ，w h e nt h eb o u n di ss u f f i c i e n t l yl a r g e ，b m p si s a l s oq u a s i c o m p l e t ef o rr h sf a u l t s w eh a v ec o n d u c t e dp r e l i m i n a r ye x p e r i m e n t st oe v a l u a l t eo u rb m p sa l g o r i t h m w e a n a l y z e dt h et c a st a s ko ft h es i e m e n ss u i t e ，a n di d e n t i f i e dt h a t3 9o ft h e4 1f a u l t yv e r s i o n s a l er h sf a u l t s i n i t i a le x p e r i m e n t a t i o n 、历md e b u g g i n gs m a l lcp r o g r a m ss h o w e dt h a to u r a p p r o a c hi sp r o m i s i n g k 呵w o r d s ：p r e d i c a t es w i t c h i n g ，p r o g r a ms l i c i n g ，d e l t ad e b u g g i n g ，b m p s ，c b m c i v 程序自动化调试的多谓词开关方法 论文原创性声明内容 本人郑重声明：所呈交的学位论文，是本人在导师的指导下， 独立进行研究工作所取得的成果。除文中已经注明引用的内容外， 本论文不包含任何其他个人或集体己经发表或撰写过的作品成果。 对本文的研究作出重要贡献的个人和集体，均己在文中以明确方 式标明。本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名： 澎只 日期：。年多月弓日 学位论文使用授权声明 本人完全了解中山大学有关保留、使用学位论文的规定，即： 学校有权保留学位论文并向国家主管部门或其指定机构送交论文 的电子版和纸质版，有权将学位论文用于非赢利目的的少量复制 并允许论文进入学校图书馆、院系资料室被查阅，有权将学位论 文的内容编入有关数据库进行检索，可以采用复印、缩印或其他 方法保存学位论文。 学位论文作者签名：孝e 日期：刀口年月多e l 导师签名：爿啷枢 e l 期：z 口口年6 月多e l 中山大学硕士研究生学位论文 1 1 论文选题的背景 第一章绪论 程序调试是指在程序运行产生错误时，查找错误产生原因的过程。程序调试是软件 开发过程中最耗费时间、人力但又无法避免的一个环节。程序调试主要包括从程序中探 测错误、定位错误以及修复错误这三个关键环节。近年来，随着软件行业的蓬勃发展以 及程序的日趋复杂，程序的自动化调试 1 】已经成为软件工程以及人工智能领域中的热门 研究课题。比较典型的自动化调试方法有d e l t a 调试方法【2 ，3 ，4 ，5 ，6 】、程序切片技术 【7 ，8 ，9 ，1 0 、基于概率的方法【1 1 】以及基于程序状态的方法 1 2 ，1 3 ，1 4 等软件工程领域的方 法以及基于模型调试 1 5 ，1 6 ，1 7 ，1 8 ，1 9 ，2 0 这种人工智能领域的方法。这些自动化调试方法 的研究主要专注于探测错误并精确地从程序中定位错误。本文所作的研究是关于程序错 误定位的。 z e l l e r 2 ，3 ，4 ，5 提出的d e l t a 调试方法是一种基于程序自动测试的自动化调试方法， 它最大的特点在于调试过程中不需要对程序代码进行任何静态分析。早期，z e l l e r 4 于 1 9 9 9 年提出d e l t a 调试是为了在软件回归测试失败后分离出那些导致原来运行正确的程 序出现错误的代码变化。之后，z e l l e r 又把d e l t a 调试扩充到错误测试用例的简化、分 离导致程序故障的输入不同点 2 】以及分离导致程序故障的因果链【3 】。 程序切片是研究历史较长的一项技术，它是一种分析程序代码的手段，对程序调试 起到了很大的作用。从1 9 7 9 年w e i s e r 提出切片的概念，到现在已经有三十年的历史， 当然，各种切片的方法也层出不穷【7 ，8 ，9 ，1 0 】，不再局限于w e i s e r 所提出的切片概念。切 片技术作为一种程序分析的技术，已经深入到程序验证、程序调试的各个方面，有一大 类自动化调试方法在实现过程中都要用到程序切片技术。 程序自动化调试的多谓词开关方法 基于概率的方法是以统计学为基础，根据程序在多个测试用例上的运行情况来确定 程序语句的可疑程度。这种方法能够很好地处理程序中同时存在多个错误的情况。虽然 它不能精确定位出一些错误语句，但是，根据语句的可疑度程序员能有效地查找出缺陷 代码。j o n e s 11 1 提出的方法就是基于概率的方法，其中对程序语句的可疑度从多个方面 进行了较全面的形式化定义。 基于程序状态的方法的基本思想是改变程序运行中某个程序状态的一些可疑变量 值来使得原来错误的运行得到正确的运行结果，然后根据修改过的程序状态来定位程序 的错误语句。传统的基于程序状态的方法允许任意改变程序状态，这使得搜索的空间巨 大、效率不高。例如：对一个3 2 位整型变量，其可能的取值就有2 3 2 个之多。针对这个 问题，文献 1 4 1 提出了单谓词开关算法，算法中只允许改变控制谓词的取值。如果进行 谓词开关之后程序能返回正确的结果，则可以根据被开关的谓词来锁定程序中的错误语 句。但是，他们没有对所提出的算法做任何理论上的分析，例如：他们没有给出在什么 情况下他们的方法是可行的。显然，在一些情况下，对单个谓词实例进行开关是不够的。 基于模型的调试方法是一种人工智能领域的方法。它的主要思想是把硬件中基于模 型诊断的思想应用到程序调试上来。基于模型的调试方法最早是用于在逻辑语言p r o l o g 中定位错误，之后应用到硬件描述语言w h d l ) 中定位错误，现在又扩展到了c 语言、 j a v a 语言等。基于模型方法的优点在于能够直接根据给定的程序代码抽象出程序的语义 模型，将其转化为逻辑上的推理。但由于程序的完备模型是不可计算的，现有模型大都 是针对某些预期的错误提出来的，具有一定的启发式性质，并且对错误的定位不够精确。 针对这些问题，文献 1 5 根据基于模型诊断的基本理论将程序调试任务在情景演算 ( s i t u a t i o nc a l c u l u s ) 中形式化，用严密的逻辑语言对调试任务进行了简洁描述，并提出了 更合理的程序修复模型。 虽然众多的自动化调试方法被提出，但它们大多数是经验性的，即它们都依赖于专 家经验和一些启发式性质。为此，文献 1 5 1 强调了从第一原理为程序调试建立一个精确 的理论基础的重要性，这个理论基础应该包括两个部分：1 、对程序调试任务的一个形 式化定义；2 、对相关程序调试算法的探讨。情景演算是一种适于描述动态世界的逻辑 一2 一 中山大学硕士研究生学位论文 语言，文献 1 5 在情景演算中给出了程序调试任务的一个形式化定义。本文在文献 1 5 】 工作的基础上，进行程序自动化调试算法理论分析的初步探索。 1 2 论文选题的意义 著名的计算机科学家b r i a nk e m i g h a n 曾经说过，软件调试要比编写代码困难一倍， 如果你发挥出了最佳才智才编写出一个代码，那么你的智商便不足以调试这个代码。在 一般的软件开发过程中，软件调试的耗费是非常惊人的。据不完全统计，一半以上的软 件工程师将一半以上的时间用于调试上【2 l 】。软件调试是一项高难度的任务，而且难以 估计到底需要多长时间才能完成。对于一个隐藏得比较深的错误，可能需要几天、几个 星期甚至几个月的时间才能够定位到错误的根源，以至于导致项目延期甚至取消和放弃 项目。 程序调试问题是一个复杂度高、难度大的任务，可以从以下几个方面进行分析【2 1 】。 首先，如果把定位软件错误看作是一个特别的搜索问题，那么搜索的复杂度会很高。 原因主要有两个方面：第一，搜索的空间是整个软件系统，从所包含的信息量来看，这 个空间是很庞大的，因为一个典型的软件系统中包含着数千个代码文件；第二，这是一 个无明确目标的搜索，真正的内在原因往往隐藏得很深。 其次，为了寻找错误发生的根本原因，调试人员有时必须深入到软件系统的底层， 研究内部的数据和代码。与顶层不同，底层的数据大多是以原始形态存在的，即使有注 释，理解和分析难度仍然比较大。 第三，由于要在一个较大的问题空间内定位错误，故要求调试人员必须有丰富的专 业知识，熟悉问题空间内的各个软件模块以及它们之间的接1 2 1 。对于每个模块，调试人 员不仅要知道其概况，有时还必须深刻理解其具体实现。 第四，每个调试任务都有很多特殊性，基本上找不到两个完全一样的调试任务。因 此，当进行一个新的调试任务时很难找到可以模仿或借鉴的先例，几乎每一步都要根据 自己的调试经验不断探索来完成。 程序自动化调试的多谓词开关方法 第五，软件的大型化、层次的增多等都在增加软件调试的难度。 由于调试在软件开发过程中的高复杂性以及不可避免性，程序的自动化调试逐渐受 到研究者们的重视，而且随着软件行业的蓬勃发展和软件的日趋复杂，自动化调试更成 了现今的热门研究领域。自动化调试技术将调试这个繁杂的工作交给计算机来处理，而 不是如程序编写规范那样通过对程序员编程的种种限制来减少错误的发生，或者仅仅提 供一个更友好的界面和更强大的程序调试控制功能。自动化程序调试技术的巨大潜力在 于能够将程序中错误代码的范围在很短的时间内极大地缩小，将一个几千上万行的可疑 错误范围缩减到几行甚至一行代码，从而加速软件开发的周期，减少软件开发的成本。 1 3 本文的主要工作 针对张翔宇教授等人 1 4 所提出的单谓词开关方法的局限性，本文提出有界调试的 多谓词开关算法( b o u n d e dd e b u g g i n gv 砌m u l t i p l e p r e d i c a t es w i t c h i n ga l g o r i t h m ，b m p s ) ， 通过在程序运行过程中开关多个谓词实例来得到一个正确的运行，且在此运行中每个循 环的执行次数不超过一个给定的上界。b m p s 算法可以通过一个s a t 求解器来实现。 本文的调试对象为不含过程调用的c 语言程序，称为w h i l e 程序。对程序调试的形式化 研究需要一种程序的形式语义。同文献 1 5 】中的策略，本文将w h i l e 程序视为g o l o g 程 序，因此可以通过g o l o g 语言在情景演算中的形式语义得到w h i l e 程序在情景演算中的 形式语义，其中g o l o g 语言是l e v e s q u e 等人 2 2 】在1 9 9 7 年提出的一种用于高级机器人 控制的程序设计语言。 本文所提出的调试算法的核心概念是关键谓词集( c r i t i c a lp r e d i c a t es e t ，c p s ) 。直觉 上，对于一个错误的测试用例，一个关键谓词集是满足如下性质的控制谓词集合：在程 序运行过程中，改变此谓词集中谓词的实例的取值可以使得程序运行最终得到正确的输 出。在本文中，程序的错误限制为右端( r i g h th a n d s i d e ，r h s ) 错误，即错误出现在控制 谓词上或者是赋值语句的右边。本文通过在程序依赖l 药( p r o g r a md e p e n d e n c y g r a p h ，p d g ) 中施加一些限制识别出了一类错误，称为谓词切( p r e d i c a t e c u t ) 错误。直觉上，对于谓 4 ， 中山大学硕士研究生学位论文 词切错误，错误在程序中传播的唯一途径就是通过控制谓词。基于将关键谓词集与谓词 切错误联系起来的一个关键性质，本文证明了：1 、对于条件程序，b m p s 对于r h s 错 误是准完备的，即任何真实诊断的部分语句一定会被b m p s 返回；2 、对于循环程序， 当给定的循环展开的界足够大时，b m p s 对于r h s 错误是准完备的。 本文利用标准c 的模型检测工具c b m c 3 4 实现b m p s 的算法思想并进行了初步实 验。本文对大量小型错误c 语言程序进行了调试实验，实验结果表明b m p s 能快速且 有效地锁定程序中的错误语句。此外，本文对r o t h e r m e l 和h a r r o l d 2 3 于1 9 9 9 年提出 的西门子标准中的t c a s 程序进行了深入分析和一些实验。本文分析得出在t c a s 程序 的4 1 个错误版本中，有3 9 个版本是r h s 错误，并且这3 9 个版本中只有一个不是谓词 切错误。 1 4 本文的结构安排 本文首先对现今比较典型的几种自动化调试方法进行回顾，并将这些调试方法分为 两大类进行描述：一类是软件工程中的方法；另一类是人工智能中的方法。第三章简要 ， 介绍本研究工作的基础知识，主要包括情景演算、g o l o g 语言以及文献 1 5 所提出的 程序调试在情景演算中的形式化定义。第四章给出对核心概念关键谓词集的形式化定义， 其中包括为了形式化关键谓词集而定义的一系列概念。然后，第五章给出有界调试的多 谓词开关算法和相应的定理。最后，本文给出所提算法的实验评估，其中包括对大量小 型错误c 程序的调试，以及对西门子标准中的t c a s 程序的深入分析。 1 5 本章小结 本章首先根据程序自动化调试方法的研究现状分析了本课题的研究背景。然后，本 章根据程序调试的复杂性和不可避免性分析了本文选题的意义。本章第三节对本文所作 的主要工作进行了简要描述。最后，给出了本文主要结构的安排。 程序自动化调试的多谓词开关方法 第二章程序自动化调试 由于调试在软件开发过程中的重要地位，程序自动化调试方法的研究逐渐受到研究 者们的重视，而且随着软件行业的蓬勃发展和软件的日趋复杂，程序自动化调试更成了 现今的热门研究领域。本章首先就现今流行的一些自动化调试方法分软件工程类和人工 智能类方法分别进行介绍。然后，本章将这两大类调试方法的优势和劣势进行分析对比。 最后，本章总结当前自动化调试领域的研究现状和存在的一些问题。 2 1 软件工程类的方法 自动化调试的研究方法中有很多是属于软件工程中的方法，这些方法都不可避免要 依靠程序测试来收集引发程序错误的信息，而信息的可靠性和多样性会对调试的结果产 生较大的影响。现有的软件工程领域的程序调试方法主要包括d e l t a 调试【2 ，3 ，4 ，5 ，6 】、切 片技术【7 ，8 ，9 ，1 0 】、基于概率的方法【1 1 】以及基于程序状态的方法【1 2 ，1 3 ，1 4 】，下面将分别 对这几种调试方法进行探讨。 2 1 1d e l t a 调试 z e l l e r 提出的d e l t a 调试【2 ，3 ，4 】是一种基于程序自动测试的自动化调试方法，它不依 赖于对程序代码的分析。d e l t a 调试的应用范围贯穿着整个程序调试过程，几乎所有对 程序运行有影响的因素都可以用d e l t a 调试方法分离出其中与程序故障相关的部分。下 面对d e l t a 调试方法在程序调试过程中的具体应用进行简要介绍。 ( 1 ) 分离诱导故障的程序代码变化 4 】 一6 一 中山大学硕士研究生学位论文 将整个程序的改变分成若干个代码段上的改变，且一段代码的改变当作一个原子变 化。把一个原子变化应用到原始正确程序，如果程序运行出现了预期故障，则可以认为 就是这个原子变化导致了预期故障。此时，错误的范围也就缩d , n 了一个原子变化上。 根据这一思想，z e l l e r 提出了查找诱导故障最小变化集的近似算法砌算法。砝算法采 用二分搜索策略：如果变化集c 中只含有一个变化，则这个变化按定义就是最小故障诱 导集，否则将c 划分为两个子集c 1 和c 2 分别进行测试。 ( 2 ) 简化故障测试用例 2 】 测试程序时，当出现了一个错误测试用例，程序员都希望这个测试用例尽可能简洁 明了。因为一个简洁的测试用例可以让程序员更好地专注于程序中的错误。z e l l e r 以自 动测试为基础实现了这个手工操作过程自动化，提出如下简化测试用例的最小化算法 d d m 加。 令c 。为引发故障的程序输入，1 ，l 是由c 。划分出的”个输入子集，而v ，表示 f 的补集c 。厶。测试每个子集i 以及它们的补集v ，可以得到以下四种情况： s t e p l ：如果测试任何厶导致预期故障，则f 就是一个更小的引发故障的输入，将i 分 为两个子集，继续化简a t ： s t e p 2 ：如果测试任何v ，导致预期故障，则v ，就是一个更小的引发故障的输入，将v ，分 为”1 个子集，继续化简v ，； s t e p 3 ：如果没有测试导致预期故障，则增加粒度至2 胛继续进行测试； s t e p 4 ：粒度不能再增加，则得到的故障诱导输入子集是最小的。 ( 3 ) 分离诱导故障的输入不同点【2 】 程序自动化调试的多谓词开关方法 加算法存在一个很大的劣势：简化所得的输入规模越大，需要的测试就越多。当 一次测试的时间很长且要简化的输入规模非常大时，编胁算法就体现不出优越性。因此， z e l l e r 提出分离诱导故障的输入不同点算法。此算法不仅在保持故障的前提下删减测试 用例中的变化，还在保持测试用例通过的前提下增加变化。 ( 4 ) 分离诱导故障的因果链 3 】 程序执行的任何时刻都有一个程序状态。当一个程序出现故障，从程序状态的角度 上看是产生了错误的程序状态。z e l l e r 正是从这一角度出发考虑程序产生故障的原因， 把整个程序的运行过程看成是一个程序状态的有限序列。程序状态并非一开始就是错误 的。错误状态的最初产生是由于执行了错误代码，之后这个错误状态又感染它的下一个 状态，这样一直演进到被人感知到的错误状态。显然，如果知道程序是在什么时候由正 确状态转变为了错误状态，就可以将错误代码的范围缩小到这个转变过程所执行的代码 上。 一个错误程序状态中被感染的变量和值只是这个状态的很小一部分。如果将故障运 行中的一个程序状态与正确运行中对等位置的状态进行比较，就可以利用分离不同点算 法分离出引发故障的某些变量和值。两个运行在多个对等位置上进行比较就得到了一条 由引发故障的变量和值组成的因果链。只要检查因果链中的变量和值就可以分离出程序 状态由正确到错误的转变时期所执行的代码。 2 1 2 程序切片 程序切片的原始概念是w e i s e r 于1 9 7 9 年提出来的。一个变量在程序中相关位置的 切片由程序中影响此变量在相关位置取值的程序语句组成。切片规范( s l i c i n gc r i t e r i o n ) 是一个二元组铆，功，表示对程序中第以行语句中的变量x 进行切片。每一个切片都对 应一个切片规范。由于不同应用领域的需要，各种不同的切片定义以及计算它们的方法 不断被提出。这些切片定义主要可以分为两大类：静态切片( s t a t i cs l i c i n g ) 和动态切片 中山大学硕士研究生学位论文 ( s t a t i cs l i c i n g ) 。静态切片的计算不依赖于具体程序输入，需要考虑所有的输入情况；动 态切片与某一具体的程序输入相关，故动态切片一般比静态切片要小。下面分静态切片 和动态切片对切片技术做简要介绍。 ( 1 ) 静态切片【8 ，9 】 在w e i s e r 的方法中，切片是根据程序中语句之间的数据依赖和控制依赖关系来进 行计算的，切片中包括对相关位置特定变量有影响的所有语句。在切片过程中，直接对 静态代码进行分析，因此w e i s e r 的方法是一种静态切片方法。f e r r a n t e 等人【8 提出另一 种计算静态切片的方法，这也是现在计算静态切片所广泛使用的方法。他们首先定义出 程序依赖 ( p r o g r a md e p e n d e n c y g r a p h ，p d g ) 的概念，然后将切片计算问题转化为程序 依赖图中顶点之间的一个可达性问题。p d g 是一个有向图，顶点代表赋值语句或控制谓 词，边代表语句之间的数据依赖和控制依赖关系。p d g 中一个顶点v 的静态切片为p d g 中可达顶点v 的所有顶点的并集。下面给出一个静态切片的例子。 如下程序的输入为n ，输出前n 个正整数的和与积。 i n ti ：= 1 ； i n ts u m ：= o ； i n t p r o d u c t ：2l ； w h i l e ( i 也是c 的碰撞集但不是极小碰撞集。 诊断和冲突集的关系可由如下定理给出。 定理2 4 2 4 】如果是被诊断系统( s d ，c o m p ，o b s ) 的所有冲突集组成的集族的一个( 极 小) 碰撞集，则是系统( s d ，c o m p ，o b s ) 的一个( 极小) 诊断。 r e i t e r 提出的算法中，极小碰撞集是通过为所有冲突集构造一个极小碰撞树的方法 得到。 2 2 2 基于模型调试 将基于模型诊断的思想引入到调试领域的关键思想在于互换模型和实际系统的角 色，即模型用来描述待诊断的程序，而观测到的系统行为由测试用例给出。我们可以由 程序自动化调试的多谓词开关方法 给定程序以及所用编程语言的语义直接得出模型。抽象出的模型要能够分辨不同的元件 并且描述它们的行为，还要包含对程序结构的描述。下面采用w o t a w a 2 0 提出的一个模 型对程序段尸1 进行诊断来说明基于模型调试的基本原理。 程序段p 1 ： 1s = aa n d 及 2 d = n o t & 3e = so rc ； 在模型所用的逻辑语言中，添加非逻辑符号切( c ， 和o u t ( c ，功。且指定m ( c ， 功表示元件c 中输入变量矿的值，o u t ( c ，r e ) 表示元件c 中输出变量y 的值，使m ( c ， 和o u t ( c ，功与元件的输入输出端联系起来。下面以如上所述的程序p 1 为例说明如何 利用基于模型诊断的思想来进行调试。 由于每个语句都作为一个元件，这里c o m p 即是集合 1 ，2 ，3 ) 。根据上语言 2 0 的语义以及给定的程序尸1 ，可以得到如下的模型。 尸l 的行为描述为： a b ( 1 ) _ o u t ( 1 ，$ 2i n ( 1 ，a ) a n di n ( 1 ，功 1a b ( 2 ) _ o u t ( 2 ，功2 n o ti n ( 2 ，$ 1a b ( 3 ) 一o u t ( 3 ，四2i n ( 3 ，研o ri n ( 3 ，c ) 尸l 的结构描述为： o u t ( 1 ，$ 2 加( 2 ，固ai n ( 2 ，固= i n ( 3 ，$ 给出测试用例产吲= lb = ic = o ，d 印胁，则可以得到o b s 如下： 切( 1 ，a ) ：1 ，i n ( 1 ，动2 1 ，m ( 3 ，o = o ，o u t ( 2 ，研= o ，o u t ( 3 ，毋= o ) 中山大学硕士研究生学位论文 输入测试用例r 中的给定输入，运行程序p l ，可以得到庐1 ，与r 中给出的输出值 相矛盾，很明显程序中存在错误，为了得出诊断即找出错误，按照基于模型诊断的思想 先要找出( s d ，c o m p ，o b s ) 的冲突集。很明显 1 ，3 ) 是一个冲突集。其实 2 ，3 ) 也是 一个冲突集，根据定义2 2 ， 2 ，3 ) 是一个冲突集当且仅当s d u o b su 1a b ( 2 ) ，1a b ( 3 ) 是不可满足的。由1a b ( 2 ) 以及- ia b ( 2 ) _ o u t ( 2 ，d ) = n o ti n ( 2 ，d 可得o u t ( 2 ，d ) = n o ti n ( 2 ，j s ) ，又有o u t ( 2 ，d ) = o ，则可得i n ( 2 ，回= 1 。根据结构描述中i n ( 2 ，$ = i n ( 3 ， 固可知i n ( 3 ，$ = l ，又n ( 3 ，o = 0 ，可以得出o u t ( 3 ，日= 1 ，这与o b s 中o u t ( 3 ，毋= o 相 矛盾，故s duo b su 1a b ( 2 ) ， a b ( 3 ) ) 是不可满足的。( s d ，c o m p ，o b s ) 的冲突集 有 1 ，3 ) 和 2 ，3 ) 。根据定理2 4 ，可以直接得到诊断 3 和 l ，2 。 ( 1 ) 基于相关性的模型 基于相关性的模型是根据程序语句之间的相关性而构造的。m a y e r 和s t u m p t n e r 1 6 】 对基于相关性的建模进行了总结，将建模过程分为结构抽象、相关性的表示和冲突的提 取三个步骤。 所谓结构抽象是指由程序语句之间的相关性转换为一个“元件联系 模型，其中 元件对应于程序语句，而联系对应于语句之间的联系，每个元件都有一个输入集合加( o 和一个输出集合o u t ( c ) ，分别表示元件c 所含语句中可能被使用或者被修改的变量的集 合。相关性表示是指由程序语言的语义和给定程序得到的“元件联系”模型的逻辑描述。 模型只表述一个变量v 的值是正确的，记为o k ( v ) ，或者是错误的，记为1o k ( v ) 。若元件 c 的行为是正常的且f ”( c ) 中的变量的值都是正确的，则o u t ( c ) 中的值也是正确的。最后 是冲突提取，根据给定的测试用例弘町，d 中的输入，运行程序，并将运行所得的输 出与0 中的输出对比。对任意一个变量v ，如果运行所得值与d 中的值相同则其对应的 模型元素o k ( v ) 记为真，否则记为假。如果由模型和测试实际值的逻辑描述既可以得到 o k ( v ) y 可l ：a 得到1o k ( v ) n 找到冲突，那么使得o j i ( 功和1o k ( v ) n 时成立的元件集就是一个 冲突集。 程序自动化调试的多谓词开关方法 ( 2 ) 基于值的模型 基于相关性的模型虽然能很简洁地抽象出程序语义，但是使用这类模型返回的诊断 经常是错误的。在基于相关性的模型中，由于对程序语言语义的粗糙抽象，不能够保证 得出的是真诊断【1 6 】。基于值的模型则加强了对模型的表示，它使用具体的变量值而不 只是变量的对或错来抽象程序的语义模型。如果模型中的同一个变量可以得到两个不同 的值，则就会产生冲突。基于值的模型与基于相关性的模型相比，最大的优势在于基于 值的模型能够更精确地近似有控制流的程序。 2 3 联系与对比 软件工程中的方法更着重于对程序的测试，通过收集测试过程中得到的信息来决定 程序发生故障的原因。d e l t a 调试是完全根据测试来锁定程序故障原因的，引发故障的 因素在程序测试过程中不断缩减，最终被精确地定位出来；谓词开关方法也是通过反复 的测试来找到关键谓词；而基于概率的方法同样是对多次测试的结果进行统计。基于模 型的方法则不同，它更注重于程序的语义，通过语义抽取程序模型，从而将调试过程转 换谓逻辑上的推理过程。下面对各种方法的优势和劣势进行简要分析。 d e l t a 调试是一种基于程序自动测试的技术，是一种纯实验性的调试方法。d e l t a 调 试最大的特点是只需要一个自动测试的软件就可以很好地实现自动化。它的不足之处主 要有两点：其一是需要进行大量的测试，但随着硬件设备的不断加速可以弥补这一不足； 其二是在分离算法中总是需要一次正确运行和一次错误运行进行比较，特别是在分离引 发故障的状态不同点时还需要这两次运行过程尽可能相似。 文献 1 4 】提出的谓词开关方法是一种基于程序状态的调试方法，当然其中还结合了 d e l t a 调试进行错误测试用例的简化。这种方法从某种程度上来说与z e l l e r 提出的因果 链方法有异曲同工之妙，都是找出个引发故障的原因：一个是关键谓词，一个是因果 链。尽管从理论上来讲，因果链方法考虑得更加全面一些，但是谓词开关方法相对来说 效率更高。 中山大学硕士研究生学位论文 基于概率的方法建立在统计学理论的基础上，它的优点在于同等条件下可以更加快 速地返回诊断。相对于因果链方法和谓词开关方法，基于概率的方法没有对程序运行过 程进行改变。它并不是专注于某一次错误运行，而是通过对多次运行进行统计把可能导 致故障的语句以可疑度的方式表示出来。 基于模型的方法是一种人工智能领域的方法，它的好处在于可以直接从程序的语义 抽象出模型。由于完备模型的不可计算性，只能有针对性地进行抽象。因此，模型的选 取就直接影响到诊断的结果。文献【1 5 】针对现有模型的缺陷提出将基于模型调试与经验 性的调试方法严格区分开来，去除掉选取模型时的启发式性质，从根本上为调试建立一 个精确的理论基础。 2 4 研究现状与存在的问题 自动化调试方法是计算机领域中的一个热点问题，特别是在软件工程领域中受到很 多研究者的重视，研究成果也较显著 2 ，3 ，4 ，5 ，6 ，11 ，1 2 ，1 3 ，1 4 。在人工智能领域，基于模型 的程序调试方法也取得了一定的进展 1 5 ，1 6 ，1 7 ，1 8 ，1 9 ，2 0 】，但由于模型选取时存在的一些 问题使得基于模型的方法没有突破性的进展。 现有的自动化调试方法大多数是经验性的方法，它们依赖于一些启发式性质。大多 数调试方法都没有对所提算法进行严格的理论分析，例如：它们没有明确所提算法的适 应范围，即对什么情况下算法才是可行的没有给出明确的定义，只是通过一些示例或实 验结果来证明其有效性。 针对以上问题，文献【1 5 】提出必须从第一原理为程序调试建立一个精确的理论基础， 这是自动化调试方法要实现深度上扩展所迫切需要的一个理论基础。 程序调试是伴随着程序的产生而出现的。数十年来，调试在软件开发过程中的作用 越来越突显出来。由于调试一直是一个手工的操作过程，花费的人力资源很大。有时定 位一个错误可能几个星期甚至几个月都毫无进展，这将大量耗费软件公司的人力和时间。 程序自动化调试的多谓词开关方法 而随着自动化调试方法的出现，就有可能让机器去完成这个繁重的任务，从而大量减少 调试方面所需的人力和时间的耗费。 2 5 本章小结 调试在软件开发过程中的重要性使得自动化调试技术长时间内无疑都会是研究的 热点问题。本章将现有的一些自动化调试方法分软件工程类方法与人工智能类方法作了 简要介绍，并重点对几种调试技术进行了讨论，其中包括z e l l e r 提出的d e l t a 调试方法、 文献【11 1 提出的基于概率的方法、文献【1 4 提出的谓词开关方法以及基于模型的程序调 试方法。此外，本章还对各种自动化调试方法进行了对比，分析了各种方法的优势和劣 势以及普遍存在的一些问题，并对自动化调试领域的研究现状作了简要总结。 中山大学硕士研究生学位论文 第三章研究基础 本章主