没有合适的资源?快使用搜索试试~ 我知道了~
理论计算机科学电子笔记174(2007)61-82www.elsevier.com/locate/entcs基于模型的数据库沃尔夫冈·迈耶1马库斯·施图姆特纳2南澳大利亚大学高级计算研究中心澳大利亚阿德莱德摘要在过去的十年中,基于模型的软件调试(MBSD)已经发表了大量的工作。我们总结的基本思想,并提出不同的方法作为抽象的具体语义的编程语言。我们比较了基于模型的框架与其他著名的自动化的方法,并提出了开放的问题,挑战和MBSD的未来发展方向。保留字:基于模型的自动推理1引言基于模型的软件调试(MBSD)是基于模型的诊断(MBD)技术在调试计算机程序中的应用。基于模型的诊断首先由[14]引入,随后由[34]完善诊断最初集中在定位物理系统中的故障,特别是在电子电路中的故障门。MBSD首先由[11,5]引入,目标是识别逻辑程序中的错误子句;该方法已扩展到不同的编程语言,包括VHDL[16]和Java[27]。在详细描述MBSD方法之前,总结了MBD的基本原则MBD的基本原理是将一个模型,一个系统的正确行为的描述,与系统的观察行为进行比较。传统的MBD系统通过直接测量接收所观察到的行为的描述,而模型由系统的设计者提供使用模型预期行为与实际观察行为之间的差异1电子邮件:mayer@cs.unisa.edu.au2电子邮件:mst@cs.unisa.edu.au1571-0661 © 2007 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi:10.1016/j.entcs.2006.12.03062W. 迈耶,M。Stumptner/Electronic Notes in Theoretical Computer Science 174(2007)61程序一致性测试组件连续集MBSD引擎诊断语言语义测试用例故障假设Fig. 1. MBSD循环识别那些被认为偏离其正常行为的组件,这些组件可以解释观察到的行为。翻译到软件领域,用程序代替具体的系统,并在一组测试用例上观察其行为似乎是可能的。这在实践中是困难的,因为需要正确程序的正式描述来检测差异。当前软件工程实践表明,很少提供正式模型,如果可用的话,它们通常会支持维护问题,其中程序所需功能的更改不会在正式模型中反映出来。此外,形式化模型通常不涵盖系统的完整行为,而是限于程序的特定属性。以下部分简要介绍MBSD的原则和基本定义。第2.4第5节分析了模型之间的关系,随后在第6节讨论了相关工作。MBSD的一些潜在的未来发展在第7节中提出。2基于模型的软件架构(MBSD)采用MBD进行调试的关键思想是交换模型和实际系统的角色:模型反映(不正确的)程序的行为,而测试用例指定预期的结果。程序计算的值与指定结果之间的差异程序的指令被划分为一组模型组件,这些组件每个组件可以在正常模式下运行,表示为<$AB(·),其中组件如程序中指定的那样运行,或者在一个或多个AB正常模式下运行,表示为AB(·),具有不同的功能。直观地说,每个组件模式对应于一个特定的修改W. 迈耶,M。Stumptner/Electronic Notes in Theoretical Computer Science 174(2007)6163的计划。3.将模型组件、程序语言语义的形式化描述和一组测试用例提交给一致性测试模块,以确定反映故障假设的程序是否如果程序可能满足测试用例指定的行为,则程序被发现与测试用例指定一致在发现程序不一致的情况下,计算导出不一致性所需的一组组件MBSD引擎根据组件的模式分配计算可能的解释,并调用一致性测试模块来确定解释是否确实有效。这个过程不断重复,直到找到一个(或所有)可能的解释2.1什么是一个问题?MBSD依赖于测试用例规范来确定一组故障表示是否合理的解释假设给出了一个非空的测试用例集是足够的,每个测试用例描述了使用特定输入值的测试运行的预期结果。定义2.1一个程序P的测试用例是一对In,Out,其中In和Out指定P的输入值和预期结果。在整个工作中,假设集合In完全指定了程序4在下文中,In和Out表示测试用例提供的断言和满足断言的状态集。测试用例可以一般化以允许在任意标签上断言。定义2.2测试问题是一个元组P,T,C,其中P是所考虑的程序的源文本,T是一组测试用例,C表示从P导出的组件集。集合C是P中所有语句的分区,是调试器返回为了简化演示,假设每个程序语句都有一个单独的组件例2.3图2中的程序计算一个链表,其中包含著名的斐波那契序列的前n个元素。该程序被划分为十个组件,每个组件代表一个语句。当运行输入n= 5时,标签末尾的预期结果是list›→[1, 1, 2, 3, 5]。表示为断言,期望的结果是assert@endlist.value==1 list.next.value==1&&list.next.next.value==2 list.next.next.next.value==3&&list.next.next. next.next.value==5 list.next.next.next.next.next ==nil程序在标签9处包含错误:a ←a−b被计算,导致不正确的结果列表<$→ [1,1,0,−1,−1]。3与突变测试[32]的主要区别是,我们对程序的修改不一定是可执行的,但可能是在包含多个具体表达式的抽象层次上。[4]对于本文讨论的所有模型,这个假设可能不是必需的。 对于基于程序执行的模型,初始状态必须完全指定,以获得唯一的执行轨迹。64W. 迈耶,M。Stumptner/Electronic Notes in Theoretical Computer Science 174(2007)61intnums{ intnums;intnums;publicinitfindDuplicate(intn,nums){1number ←n;2下一个←3返回此;}}4inta←1;5intb ←0;6intnil;7而(n>0){8b←a+b;9a←a - b;10return();11init findDuplicate(i, i);12n←n−1;}端图二. 斐波那契规划2.2MBSD引擎一旦检测到失败的测试执行,为了计算解释,采用了Reiter一组故障假设Δ=Δ{C1, . . ,Ck}是一个可变的表达式,如果在组件Ci处的改进模型可以表现出偏离行为,而其余组件表现出正常行为,则不再意味着不正确的行为。由MBSD引擎生成的每个故障假设对应于程序的修改。 一个组件C,它表示原始程序源代码被替换为组件CJ,它指定了C或不指定任何特定行为。5在遇到失败的测试用例的情况下,MBSD引擎确定暗示失败所必需的一组程序组件(“配置集”)。在最简单的形式中,切片[37]的变体可以应用于计算集合。一般来说,诸如Resolution演算或基于约束的系统[23]之类的算法用于计算小冲突。使用Reiter2.3一致性测试一致性测试模块决定程序P的变体PJ是否符合测试用例规范所预期的行为通过应用从MBSD发动机获得的故障假设Δ,从P导出PJ转换-P到PJ的转换是模型特定的,并在以下章节中呈现。定义2.4错误假设Δ与测试用例规范的集合T一致,当且仅当对于所有测试用例,不能推导出满足程序模型的所有程序执行(修改为响应Δ)违反测试用例。5不同的模型应用不同的策略来确定由异常分量影响的变量和场。在这里,它隐含地假设只有C中存在的变量是不确定的。 这一限制将在第3.9节中放宽。W. 迈耶,M。Stumptner/Electronic Notes in Theoretical Computer Science 174(2007)6165颈7C4C 5C 6n0的忽略0a0级n1a 1b1b0的列表1忽略 1堆 1列表0<$AB(C4)→ok(a0)<$AB(C5)→ok(b0)<$AB(C6)→ok(列表 0)<$AB(C7)<$AB(C 8)<$<$AB(C 9)<$<$AB(C12)ok(a 0)ok(b 0)ok(n 0)→ok(v 1)vi∈ {a1,b1}<$AB(C7)<$<$AB(C 12)ok(n 0)→ok(n 1)<$AB(C7)<$AB(C 8)<$<$AB(C 9)<$<$AB(C10)<$AB(C 11)<$AB(C12)ok(a 0)ok(b 0)ok(n0)ok(list 0)→ok(wi)i∈ {list1,ignore1,heap1}图三. FibList程序的依赖模型2.4基于一致性的最优模型使用程序的符号执行来决定程序是否满足所有测试规范,从而产生最佳MBSD模型。不幸的是,这个模型一般是不可计算的,必须引入近似值。例2.5图2中的程序显然违反了例2.3中给出的测试用例:程序计算list.next.next.value的值为0,而断言要求满足值2。从执行跟踪中可以确定,除了[returnthis]3之外的所有组件都是导出实例变量的错误值所必需的MBSD引擎随后为冲突中的每个组件创建故障候选,并重新检查测试用例。假设选择了组件[a<$a-b]9,并且程序中的第9行被更一般的变量[a<$Q]9替换。占位符Q不是原始程序语法的一部分,而是由一致性测试人员引入的,表示一个未知的表达式。执行过程如前所述继续进行,直到到达标号9,变量a的值被设置为一个(此时未知 的 )值 , 由 标 号 1 表 示 。继 续 执 行, 并 且 将R11 存 储 在新 创 建 的列 表 节 点([list←. ]10)。 循环迭代,直到条件变为false,程序终止于最终状态,其中list›→[list1,.] [55]一切有情,皆是虚妄。很容易看出,例2.5中的跟踪的最终状态与例2.3中给出的断言一致,如果将断言中指定的值赋给了tagi。因此,组件9是测试执行失败的潜在原因。对剩余的候选解释重复此过程[1][2][3][4][5][6][7][8][9][10][11][12][13][14][15][16][17][18][19n >0b← a+ ba← a− blist← new FibListignore← list.FibList( b,list) n← n−1列表0←nullb0←00←166W. 迈耶,M。Stumptner/Electronic Notes in Theoretical Computer Science 174(2007)613依赖性建模从程序语句之间的依赖关系导出的模型是最早开发的模型之一。虽然术语后来,MBSD被应用于 Prolog程序[11,5]和用硬件描述语言VHDL[16,39]编写的程序,自动配置系统的知识库[15]以及命令式和面向对象的语言[27,38]。在下文中,重点是使用Java的工作。Wieland依赖性模型利用公共模型表示,而模型之间的差异在依赖性和堆数据结构的近似中被发现。3.1结构抽象依赖模型是由程序P中语句之间的依赖关系构建的,它已经被转换成静态单一分配形式(SSA)[13]。SSA形式是一种程序表示,其中每个变量只分配一次,并且计算语句之间的依赖关系变得微不足道。如果存在这样的执行,使得Sj在Si之前,并且S i的结果的计算需要由S j计算的值(“数据依赖性”),或者S j的结果可能导致S i是(不可)可达的(“控制依赖性”),则语句S i直接依赖于语句S j。这对于检测不涉及使用错误变量的故障是足够的,并将在第3.9节中放宽。整个方法的模型是通过组合方法语句的依赖关系获得的。由此产生的依赖关系基本上与通过应用切片算法获得的依赖关系相同[37,41]。将依赖关系转换为组件连接模型,其中组件对应于程序语句,连接对应于语句之间的依赖关系。每个分量C∈C都有一组输入(C)和一组输出(C),对应于由C表示的语句可能使用和修改的所有变量和位置。例3.1图3描述了为图2中的程序创建的组件和连接的图形表示。循环结构已经被折叠成一个单独的组件,在输入和输出变量之间具有不同的依赖关系。例如,变量a1取决于n0、a0、b0的值以及C7、C8和C9的故障假设。这些依赖关系的计算将在下一节中更详细地讨论。[38]中的术语我们更喜欢用“依赖”这个词来W. 迈耶,M。Stumptner/Electronic Notes in Theoretical Computer Science 174(2007)6167由于堆数据结构的精确建模取决于所使用的模型,因此表示对象的连接被省略,而是表示为单个连接,即堆。3.2依赖性表示在命题逻辑中,构件连接模型被编译成句子该模型仅表示变量v的值是正确的ok(v)还是不正确的<$ok(v)。如果原始组件C的所有行为都被简化以保持正确性,(C)中的输入={vi1,.,vim}提供正确的值,并且C本身是正确的。在这种情况下,组件的输出out(C)= { v,j,.,vjn}也是正确的:<$AB(C)ok(vi1). ok(vim)→ok(vj1)ok(vjn).否则,C规则被形成为使得C对于任何潜在的可预测变量vk都不预测ok(vk)。整个程序的模型是通过形成所有句子的连接词来获得的。堆数据结构的抽象,即堆位置的进一步讨论在3.43.3浓缩萃取为了计算T=0,0,1,2,3,4,5,6,7,8,9,9,10,10,11,11,12,12,13,14,15,15,16,17,18,19,19,对于每个变量vk,如果从执行中获得的值与O中指定的值一致,则相应的模型命题ok(vk)被设置为真,否则否定的命题被断言。断言ok(vk)被添加到I中指定的所有变量vk,表示T提供的所有输入都是正确的。通过文字AB(C),C∈C将故障假设Δ引入模型。对于所有剩余的COM-i∈C\Δ,<$AB(CJ)成立。为了识别解释失败的测试断言的组件,线性时间单元res-time解决方案证明器(LTUR)的应用,以获得模型的逻辑表示和表示测试结果的事实之间的不一致。如果有一个变量v,其中ok(v)和<$ok(v)都可以导出,则找到了一个矛盾。对两个冲突文字的推导有贡献的分量形成冲突。3.4ETDM基于执行跟踪的模型(Execution Trace based Model,ETDM)是由(错误的)程序P在测试用例指定的输入I上的单次执行中的语句之间的依赖关系构建的。程序在状态I开始运行,随后将执行轨迹转换为SSA形式,并用作依赖性计算的基础。由于只考虑单个执行路径68W. 迈耶,M。Stumptner/Electronic Notes in Theoretical Computer Science 174(2007)61ETDMDDMSDM见图4。 ETDM、DDM和SDM精确地表示变量和动态数据结构,并忽略尚未执行的语句之间的依赖关系。该模型是免费的虚假的依赖关系,因为只有在执行过程中实际出现的依赖关系被考虑。堆数据结构被视为普通变量,不需要特殊考虑。缺点是执行程序会为长时间运行的程序增加额外的开销,因为程序必须为每个测试用例执行一次例3.2图4给出了从2.1节给出的程序和测试用例中获得的不同模型的标记为12的语句处的堆抽象。对于每个循环迭代,单独的位置ii,i∈ {1,.,5},表示类型FibList的实例。引用类型的所有变量的值都是精确已知的,不需要近似。3.5DDM与ETDM相比,详细依赖模型(Detailed Dependency Model,DDM)不依赖于程序执行来构建模型表示。相反,应用静态分析技术来分析程序的控制和数据流,包括动态创建的数据结构。必须考虑所有可能的处决。在初步步骤中分析程序,将动态分配的数据结构划分为单独的抽象位置。定义3.3位置表示一个或多个对象,这些对象可能在运行时被程序分配。潜在地表示多于单个对象的位置是摘要位置。每个位置都包含类型和实例列表ι5FibListnumbernextι4FibListnumbernext···ι1FibListnumbernext无忽略'ι伊列表忽略无无列表列表我忽略FibList忽略下number下numberFibList下numberFibList下numberFibListW. 迈耶,M。Stumptner/Electronic Notes in Theoretical Computer Science 174(2007)6169表示对象的变量。在图4中,潜在地表示多于一个对象的位置用双边界描绘。例3.4使用[12]中给出的简单堆分析,可以从图2中标号12处的程序中获得以下堆分区(图4):变量list和ignore引用同一个唯一对象(FibList的实例)。对象的下一个实例变量的值 然而,在这方面, 不知道哪个对象被引用,也不知道通过下一个实例变量可到达的结构是否是循环的,甚至不知道与包含引用的对象不同。7在位置对应于单个对象的情况下,与常规变量的建模没有区别。对于摘要位置,必须扩展逻辑表示,以说明不知道引用的是哪个对象。对于表示多个具体对象的位置k,ok(k)和<$ok(<$k)只有在保证这一事实对由<$k表示的所有具体对象都成立时才能被断言。由于控制流程中的模糊性以及在初步分析阶段对堆数据结构的近似,该模型可能包含虚假的依赖关系。例3.5图4中DDM中使用的堆分区比ETDM中使用的更简洁,因为堆位置{11,.,14}不再被明确地表示,而是被概括为单个命题14。该模型在内存和运行时间方面的要求低于ETDM,但可能会导致更多的潜在解释。3.6SDM大型程序(几MB的源代码)需要更抽象的模型才能进行调试。摘要依赖模型(SDM)进一步从DDM中抽象出来,并将堆数据结构表示为与指向该位置的变量相对应的抽象位置。该模型创建一个单一的位置,代表每个程序变量引用的整个数据结构。堆结构的粗略近似允许更有效的推理,但引入了由别名和汇总位置引起的不精确性。为了提供安全的近似,必须添加依赖项以确保模型提供安全的抽象。示例3.6图4中描述的SDM的堆抽象表示由两个变量list和ignore引用的动态数据结构,作为两个位置,ilist和iignore。请 注意,已经创建了两个抽象位置,7先进的形状分析方法,如[35],可以推断出更多的信息,如数据结构的形状以及节点是否被多个位置引用。70W. 迈耶,M。Stumptner/Electronic Notes in Theoretical Computer Science 174(2007)61都代表着同样的具体物体如果程序包含修改两个变量之一指向的位置的指令,则必须修改语句的依赖表示,以将相同的修改反映到另一个位置。3.7建模硬件描述[39]提出了一种基于依赖关系的模型,旨在定位VHDL编程语言子集中的故障。VHDL的语义是基于并发进程的概念,这些进程可以通过改变信号的激活来触发,并且可以反过来改变其他信号的激活。 VHDL程序的依赖模型将并发进程表示为组件,将每个进程使用和改变的信号表示类似于DDM和SDM,循环依赖图被折叠成单个节点。从观察到不正确的信号开始(通过手动检查或使用自动比较器工具[16]),识别可能导致不正确结果的信号和过程。通过连接的组合和故障模型表达VHDL程序中常见的故障,可以有效地隔离故障。3.8基于计划的建模(PBM)Kuper [26]为LISP程序引入了一个交互式调试器DEBUSSI,它也是基于表达式之间的依赖关系。该模型构造了一个简单的计划(本质上是一个依赖图),表示在程序执行期间计算的表达式和子表达式及其相互依赖性。用于识别潜在错误表达式的推理策略基于约束暂停[14],以免除不能对错误负责的条件表达式排除不太可能的解释的简单分析用于过滤候选解释。Kuper遵循分层的交互式过程,提示用户判断在运行时获得的特定表达式是否正确。基于结果,系统消除与用户的回答相冲突的解释,如果被标识的表达式表示函数应用程序,则会产生使用函数体的新调试问题3.9抽象依赖模型(AbstractDependency Based前面讨论的模型能够定位涉及不正确的表达式的故障,但不提供必要的手段来定位涉及缺失语句或分配给错误变量的故障为了定位这样的故障,补充模型不是来自程序是必要的。[36,33]中介绍的思想首次尝试利用简单的规范[21]来定义方法的输入变量和结果变量之间的潜在故障的指示是通过比较程序诱导的依赖关系与测试用例规范中获得的依赖关系来获得的。这些W. 迈耶,M。Stumptner/Electronic Notes in Theoretical Computer Science 174(2007)6171提示随后用于修改程序,以在赋值表达式的左侧。[33]使用基于约束的方法来计算合适的变量集。该算法限制ADM检测和诊断丢失的依赖关系。4基于价值的模型虽然在前一节中介绍的基于依赖关系的模型是轻量级的工具,甚至可以有效地应用于大型程序[16],但对于面向对象的程序,它们经常返回许多虚假的诊断。进一步的分析表明,一致性测试器中不充分的推理能力是导致误报的主要特别是,将具体语义粗略抽象为计算ok(·)和<$ok(·)的抽象转换太弱,无法确定特定候选是不一致的,必须假设一致性一种可能的补救方法是加强模型表示,以便在某些情况下可以导出冲突,排除虚假的解释。本节概述了一些加强模型表示和冲突提取过程的方法和以前一样,我们的重点是Java模型,忽略了VHDL程序的类似开发[40]。4.1基于价值的模型(VBM)在[ 27 ]中提出了对基于依赖关系的模型的直接扩展,用程序计算的具体值替换(<$)ok(·)文字。模型计算具体值(或者在没有接收到所有所需输入值的情况下不计算值)。该模型基本上模拟了程序,假设计算新值所需的所有值都是已知的,否则不会预测任何值。当为同一模型变量导出两个离散值时,将导出信息。例4.1图5给出了从图2中的程序导出的逻辑模型。循环不再表示为单个组件,而是由包含循环条件和主体模型的分层结构组成。这些又包含描述各个语句和调用方法的模型。文字a.b.c表示程序状态a中对象b的实例变量c。只有当两个表达式中至少有一个计算为具体值时,模型才会强制执行=运算符。否则,该模型不会预测任何值,因此假设一致性。循环体和条件的模型的副本是动态实例化的,这取决于前一次迭代的条件模型的模拟结果。这个过程重复,直到条件的模型不意味着真。如果条件为false,则由前面的模型导出的变量值与循环组件的输出统一。否则,无法确定迭代次数,并且循环无法预测72W. 迈耶,M。Stumptner/Electronic Notes in Theoretical Computer Science 174(2007)61<$AB(C4)→a 0= 1<$AB(C5)→b 0= 0<$AB(C6)→列表 0=nil<$AB(C7)<$<$AB(C8)→bi=ai−1+bi−1<$AB(C7)<$<$AB(C9)→ai=ai−1−biAB(C10)→列表i=ii(iifresh inheapi−1)i=,kheapJ. i。k=heapi−1. i。我的朋友,我的朋友。value=0heapJ. ii.next→nil我我我<$AB(C7)<$<$AB(C11)<$<$AB(C1)→heapi. listi。value=bikh/i=,kheapi. i。k=heapJ. i.k我我<$AB(C7)<$<$AB(C11)<$<$AB(C2)→ψi/i=,kheapi. i. k=heapJ. i。k我<$AB(C7)<$<$AB(C12)→ni=ni−1+1我heapi.listi.next=listi−1图五. 用于VBM的FibList其产出。 在[27]中给出了这种传播过程的正式描述。VBM可以有效地处理各种程序,与切片相比,基于依赖关系的对于不同实例变量由程序的不同部分处理的数据结构,堆分区模型提供了更好的解释。然而,结果的可靠性取决于分配左侧变量故障的情况下。与基于依赖关系的模型相比,VBM的主要优点是它能够更精确地近似程序的控制流程,并且即使对于无分支执行也能产生矛盾。4.2异常模型(EM)VBM对于简单控制流的程序是有效的,但是对于任意控制流,如结构化异常处理和非局部分支,VBM的表达能力不够。EM通过改变模型构造来使用静态单一信息形式(SSI)[3]来消除这种限制,SSI是一种双向表示,旨在支持向前和向后推理。组件模型的转换被扩展为包含SSI表单引入的元素,但与普通VBM相比保持不变冲突提取器可以描述如下:模型被表示为一个连续图,并被划分为具有单个入口点的区域。如果在区域中检测到不一致,则整个区域被标记为不一致,并且必须遵循不同的路径。一旦包含程序入口点的区域被标记为不一致,则不存在一致执行,并且与最外层区域相关联的组件集作为一致返回4.3基于解释的抽象模型(AIM)大多数先前提出的模型的一个共同的固有问题是,模型必须表示程序的所有可能执行面向对象W. 迈耶,M。Stumptner/Electronic Notes in Theoretical Computer Science 174(2007)6173对于具有多态性和副作用的程序,必须计算调用图和数据流的保守近似,从而导致具有紧密互连的组件的潜在大模型。基于抽象解释的模型AIM [28]将建模方法从静态转变为动态,将结构建模阶段与冲突提取相结合。程序的具体语义被替换为一个区间格来近似不能精确确定的程序状态。故障假设适用于P和动态生成的模型,构造只可行的路径。应用一系列向前和向后分析[6]来消除不会导致测试用例指定结果的路径。如果没有可行路径剩余,则检测到冲突。建模过程更有效,因为只生成可行的执行路径可以可靠地检测和定位涉及分配给错误变量的故障4.4基于谓词抽象的模型(Predicate Abstraction Based Model,PAM)[24]引入谓词抽象[4]和VBM之间的合成。当普通的VBM无法导出冲突时,PAM被应用于模型中无法预测值的区域。如果可以导出一组足以证明模型不一致的谓词,则返回一个不一致。虽然抽象细化方法已被证明在验证程序方面表现良好[9],但由故障假设引入的未指定程序元素对细化过程的影响仍有待进一步研究。更详细地分析。4.5堆不变模型(Heap Invariant Model,HIM)堆不变模型(Heap Invariant Model,HIM)[8]使用谓词来表示堆数据结构的不变量。例如,由程序操作的特定树数据结构应该始终是非循环的。HIM使用普通的VBM来模拟程序,跟踪堆不变量。 如果发现一个不变量被违反,模型将被向后追溯,以找到第一个引入违反的分量C。表示到达C的分量和表示C不幸的是,[8]中提出的精确算法的描述相当模糊,但似乎HIM可以被视为VBM模型的一个变体,通过简单的谓词抽象和冲突最小化来增强。4.6高级观察模型(HOM)与HIM和AIM中提出的想法类似的想法已经引入在[29]中。该模型通过将AIM中使用的区间格与模拟程序执行的某些属性的一组固定谓词相结合,提供了更高的精度和更好的冲突检测。谓词与74W. 迈耶,M。Stumptner/Electronic Notes in Theoretical Computer Science 174(2007)61AIM允许一致性测试人员构建精炼模型,当纯AIM或抽象属性单独不能提供有用信息时,该模型可以检测到冲突。HOM包含抽象属性的目录,每个属性与用于与用户交互的纯文本描述相关联。由HOM表示的属性包括:(i)变量和数据结构应该(不)在执行中的两个点之间修改,(ii)数据结构应该总是(a)循环的,或者(iii)循环应该覆盖数据结构的所有元素。这种高级规范的好处是双重的:(i)任何违反属性的错误候选都被消除,(ii)一致性测试人员可以利用这些属性来构建更精确的模型,并更好地近似一致性测试。这些属性已经被确认为排除了一些虚假的,但难以消除对一组玩具程序的解释。对更大范围的方案进行彻底评价仍是今后的工作。5比较模型在这项工作中总结的模型可以根据多个标准进行比较以下方面可能是确定特定模型是否适合给定程序所感兴趣的:• 精确度:作为有效解释返回的虚假结果的比例。• 完整性:是否保证MBSD引擎返回的解释中始终包含真正的故障?从从业者的角度来看,第一个方面很重要模型之间的关系ΔΔ用于比较不同建模方法的结果具体地说,AΔB表示从方法A获得的所有诊断ΔA中作为可能解释返回的程序语句集是从B获得的诊断ΔB所涉及的程序语句的子集:定义5.1AΔB←→S∈ΔAS SJSJ∈ΔB模型A暗示了模型B认为有效的解释的一个子集(或相同的集合),并且可能比B返回更少的虚假解释。在本节中,假设模型使用相同的测试用例规范、堆抽象和程序组件。5.1依赖模型层次结构在第3节中介绍的模型之间存在以下关系:ETDMΔDDMΔSDMW. 迈耶,M。Stumptner/Electronic Notes in Theoretical Computer Science 174(2007)6175证据假设模型应用相同的推理策略和模型表示,那么检查每个模型应用的堆抽象和依赖关系的近似就足够了。虽然ETDM只表示单个执行,但DDM安全地近似了所有可能执行中的依赖关系。在ETDM中建模的所有依赖关系必须包含在DDM中。可以看出,DDM(SDM)中的动态数据结构的表示是通过聚合堆位置并为摘要位置添加附加依赖性而从ETDM由此可见,为精确模型导出的依赖关系集因此,只要精确模型是一致的,抽象模型也是一致的。Q通过对动态数据结构的支持扩展Kuper以同样的方式扩展Hunt静态和动态切片的定义[37]产生了以下内容:DICEΔSSLICEΔRDSLICEΔEXECΔ RDSLICEΔSSLICEEXEC表示程序中所有指令的集合和执行指令的集合,DICE、DSLICE和SSLICE表示从程序切片和动态和静态切片、重新编译获得的指令。在[41]中表明,如果不存在结构故障,则基于相关性的模型中的接触面等效于切片。ETDMΔDSLICE和DDMΔSSLICE其中,对于第二个包含,要求用于计算SSLICE的堆抽象不比DDM中使用的堆抽象更精确。如果只有一个变量被观察到是不正确的,依赖模式会导致与切片相同的结果。当仅限于单一故障解释时,解释恰好是每个不正确变量的各个切片交叉点中包含的解释[41]。否则,与纯粹基于切片的策略相比,基于模型的方法可以通过应用组件的特定故障模型来改善结果。切片和基于依赖性的模型对于一般故障都是不完整的两者都保证在故障未被屏蔽的情况下,故障被包括在解释集合中,不涉及缺失或额外的语句或对错误变量的赋值。76W. 迈耶,M。Stumptner/Electronic Notes in Theoretical Computer Science 174(2007)615.2VBM层次结构很容易看出,VBM的精确度低于无环模型(LFM)[30]和PAM,因为这两个模型都是VBM的专业化:LFM,PAMΔVBM证据LFM和PAM都对VBM进行了扩展,增加了对组件行为模型的约束。当VBM本身是一致的时,扩展会被应用,以改进一致性测试的近似。由此可见,专门的模型推导出从普通VBM获得的所有冲突的超集。因此,只要专用模型一致,VBMQAIMΔEMΔVBM证据AIM可以被视为EM的动态展开,在某些路径无法在程序状态下实现的情况下,将控制流程图专门化为路径的子集。区间格严格来说比VBM中使用的简单格更有表现力。因此,AIM具有潜在的更大的控制位置集合,每个控制位置比EM更专业,并且至少用EM提供的信息量进行注释。AIM模型的一致性意味着EM模型的一致性。EM也提供了比VBM更少的解释:虽然一致性测试人员对两个模型应用相同的网格,但由于用于条件的基于区域的推理更好,EM形式证明是简洁的,但可以通过归纳模型的结构来建立。QHOMΔAIM证据HOM是从AIM中获得的,通过将区间格替换为区间格和表示HOM建模的抽象的抽象格的约化乘积[31]。这意味着HOM的一致性测试器为每个程序状态导出至少与AIM相同的信息。因此,由AIM导出的所有冲突都可以由HOM导出,并且只要HOM是一致的,AIM就是一致的。根据Reiter单独的ADM不能直接与之前的任何模型进行比较,因为依赖性是计算的,而不是用于建模,并且没有值被传播。ADMΔR证据 所有的解释都必须由程序中的语句组成。QW. 迈耶,M。Stumptner/Electronic Notes in Theoretical Computer Science 174(2007)6177ΔΔVBM-1 DSLICE如果VBM仅限于单一故障诊断。证据VBM和它的所有变体精确地模拟程序的行为时,没有故障的假设。可以通过计算不正确变量的动态切片来推导出一致性θεDSLICE。根据Reiter对于包含多个组件的解释,该结果不成立,因为VBM可能计算由不在DSLICE中的组件组成的连接。Q当仅限于单组分解释时,VBM比ETDMVBM-1 ETDM。证据VBMDSLICE精确地包含计算(不正确的)值所需的语句,并且两个模型都在没有错误假设的情况下模拟程序。 由VBM导出的初始冲突必须包含在DSLICE中;对于ETDM,冲突等效于DSLICE。ETDM和VBM中使用的冲突提取器都对DSLICE中的相同候选集进行操作。可以看出,只要ETDM消除了一个候选项,VBM也会消除该候选项:ETDM的约束对应于所有输入变量都表示为ok(·)的模型路径。在这种情况下,VBM的表示也可以模拟执行,因为所有需要的输入值都是已知的。因此,只要ETDM导出一个冲突,VBM就可以导出相同的冲突。Q使用统计学和不安全近似的模型的结果各不相同,无法与大多数其他模型进行比较。如果从PRECISE获得的结果不能保证从ADM、DICE、HM、LFM或HIM获得的结果是超集。其余的模型使用了一个安全的近似具体语义。因此,这些模型都不能提供比PRECISE更好的结果(PRECISE一般不可计算):定理5.2精密度ΔM,M∈ {HOM,PAM}其他模型的结果遵循的是Δ的传递性。证据 微不足道,因为模型是PRECISE的安全近似值。Q图6总结了不同模型之间的关系除了程序切片、LFM、HIM和Hunt模型之外,所有模型都保证定位不涉及结构故障的故障。大多数模型不能可靠地检测或定位涉及缺失或额外语句、使用错误变量和其他结构性差异的错误。ADM、AIM和HOM是78W. 迈耶,M。Stumptner/Electronic Notes in Theoretical Computer Science 174(2007)61⊆1⊆Δ⊆Δ⊆Δ⊆Δ⊆Δ⊆Δ⊆Δ、、、、EXEC、INSTR、、、SSLICE、、、、、、ADM、、、、DSLICESDMDICE,HM、、、ETDMDDM、PBM、、、VBM,不,不,,,,LF MEMPam他AIMHOM,,、、、精确见图6。 不同模型在给定适当的测试用例规范的情况下,保证定位和检测故障任何MBSD方法都不能检测到未表现为失败测试用例的6相关工作在[2]中提出了一种调试VHDL的方法,该方法原则上对应于基于依赖性的MBSD。故障模型表示为插入到原始设计中的多路复用器组件,其中通道选择器信号表示故障假设。附加约束限制了有效解释中整个模型随后被转换为命题逻辑,并使用SAT求解器求解故障的数量增加,并且在没有找到解决方案的情况下重复该过程。在[20]中描述了一种基于故障模拟的方法,其中通过用常数0或1替换信号来识别潜在的故障,以确定信号是否通过利用电路的结构组成来减少要测试的信号的可能组合的数量为故障模拟引入的常数可以看作是一个强故障模型,预测的是一个常数而不是没有值根本因此,[20]需要两次模拟运行,而基于模型的方法只需要一次。基于故障模拟的方法依赖于智能修剪技术来减少要模拟的故障组合的数量,而不是建立解释的冲突。Delta Error(DD)[10]旨在通过最小化表现出错误的运行(“失败运行”)和没有表现出错误的类似运行(“通过运行”)之间的差异来隔离程序失败的根本原因。系统地探索并最小化两次执行中同一点的程序状态之间的差异,从而得出一个解释程序失败原因的⊆ΔΔ⊆Δ、、、、W. 迈耶,M。Stumptner/Electro
下载后可阅读完整内容,剩余1页未读,立即下载
cpongm
- 粉丝: 4
- 资源: 2万+
上传资源 快速赚钱
- 我的内容管理 收起
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
会员权益专享
最新资源
- zigbee-cluster-library-specification
- JSBSim Reference Manual
- c++校园超市商品信息管理系统课程设计说明书(含源代码) (2).pdf
- 建筑供配电系统相关课件.pptx
- 企业管理规章制度及管理模式.doc
- vb打开摄像头.doc
- 云计算-可信计算中认证协议改进方案.pdf
- [详细完整版]单片机编程4.ppt
- c语言常用算法.pdf
- c++经典程序代码大全.pdf
- 单片机数字时钟资料.doc
- 11项目管理前沿1.0.pptx
- 基于ssm的“魅力”繁峙宣传网站的设计与实现论文.doc
- 智慧交通综合解决方案.pptx
- 建筑防潮设计-PowerPointPresentati.pptx
- SPC统计过程控制程序.pptx
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功