没有合适的资源?快使用搜索试试~ 我知道了~
理论计算机科学电子笔记48(2001)网址: http://www.elsevier.nl/locate/entcs/volume48.htmlpp. 1- 16逻辑程序作为逻辑程序马尔科·科米尼1乌迪内大学数学与信息学院意大利乌迪内Roberta Gori2 乔治·列维3比萨大学信息学院意大利比萨摘要在本文中,我们定义了一种新的验证方法,基于断言语言,能够通过逻辑程序表达用户定义的属性。我们首先应用[3]中定义的验证框架来导出足够的归纳条件来证明部分正确性。然后,我们将展示如何使用程序转换技术证明所关键词:归纳验证,抽象解释,逻辑程序转换。1介绍验证的目的是定义条件,使我们能够正式证明程序的行为符合预期,即程序是正确的。一个给定的规范,一个对程序预期行为的描述。基本上有两种方法来表示程序的实际和预期行为,通过列出所有结果或通过描述结果必须满足的属性为了表达程序的属性,我们使用断言,在一个合适的断言语言的公式一旦选择了断言语言,我们就只能验证特定的属性类1 电子邮件地址:comini@dimi.uniud.it2 电子邮件地址:gori@di.unipi.it3 电子邮件地址:levi@di.unipi.it2001年由ElsevierScienceB出版。 诉 操作访问和C CB Y-NC-ND许可证。科米尼、戈里和莱维2± →→≤P在本文中,我们提出了一种新的验证方法的基础上断言语言能够表达的属性不是一劳永逸的,但可以定义的用户通过一个逻辑程序。这就产生了一种非常强大的断言语言,它允许我们验证各种程序的不同属性。给定任何表示为建立在用户定义的谓词上的公式的属性,通过应用[3]中定义的验证框架,我们推导出部分正确性的充分归纳条件由于as-sertion语言非常强大,我们不能希望有一个有效的方法来决定何时验证结果条件然而,我们将表明,这样的条件可以证明使用著名的程序transformation- tion技术。程序转换是一种方法,它允许一个语法转换公式,同时保持其(选择)的语义。变换规则的一些示例是折叠/展开变换规则。在我们的例子中,我们通过对用户程序的转换来证明用户定义谓词上的断言。值得注意的是,允许人们表达通过用户程序定义的属性的断言语言已经在文献中定义[14,15,2,16,7]。然而,我们的方法有很大的不同。在[14,15,2]中,断言实际上与程序点相关联在运行时,这些断言将使用定义断言语言和运行时值的逻辑程序来执行。在这种方法中,规范语言的逻辑实现用于通过执行来检查实际程序的每个结果是否验证了规范,而在我们的方法中,同一个程序用于在语法上证明部分正确性的充分条件假定读者熟悉逻辑程序语义学中的术语和基本结果[1,10]以及[5,6]中提出的抽象解释理论2归纳抽象验证为了证明程序的行为符合预期,我们可以使用基于抽象解释技术的基于语义的方法这种方法使我们能够以统一的方式推导出证明部分正确性的充分条件。感兴趣的不同属性。这一做法背后的想法如下:• 程序P的具体语义[P]被定义为具体域(C,±)上的语义评价函数TP的最小定点。• 在基于标准抽象解释的程序分析中,我们要验证的属性类A,),通过通常的伽罗瓦连接α:CA和γ:A与(C,)相关C(抽象和具体化功能)。相应的摘要语义评价函数Tα是由T、α和γ。P科米尼、戈里和莱维3不S≤αPP由此产生的抽象语义是一个正确的近似的具体语义的建设和没有额外的• 定义域(A,)的元素α是指定,即,抽象的具体语义。• 程序Pw.r.t.的部分正确性。一个规范Sα可以表示为α([[P]])≤Sα。• 因为[P]被定义为算子P的最小定点,所以部分正确性的充分条件4TP(Sα)≤ Sα。(一)遵循上述方法,验证技术继承了抽象解释的优良特性也就是说,我们可以定义一个验证框架,相对于我们想要建模的(抽象)属性是参数化的。给定一个特定的属性,相应的验证条件从框架中系统地导出,并保证确实是足够的部分正确性条件。基于充分条件(1)的归纳验证方法不需要计算定点。为了使其有效地应用,我们需要• 一个具体的定点(指称)语义,它允许我们观察我们想要验证的属性。• 抽象行为的有限表示(具体化)。3验证方法(1)(在逻辑程序的情况下)最初用于抽象诊断[4],这是一种将声明式调试[16,8]扩展到调试框架的技术,参数w.r.t.抽象在[2]中采用了类似的方法,其中不同的近似(通过抽象解释建模)可以用于语义和规范。在[9]中考虑了更一般的规范(包括前置和后置条件),它定义了一个验证框架,其中可以通过简单地选择不同的抽象来重建众所周知的验证方法该方法可以用两个抽象步骤来解释。第一步涉及语义的推导,该语义对计算的特定方面进行建模,从而允许我们通过(1)推导出足够的验证条件第二步执行所需的抽象[4]事实上,Tα(Sα)≤ Sα意味着[P]]α≤ Sα,由于α([[P]])≤ [[P]]α,可以导出条件α([[P]])≤ Sα。 注意,(1)意味着指定Sα是抽象语义评估函数T α的前置定点。科米尼、戈里和莱维4LLI≤I |⇒对特定类别的属性进行建模,这些属性可以导致有限的可表示规范。因此,我们可以处理不同的部分正确性概念及其相关的证明方法。正确性在这种情况下,我们只考虑后置条件。适当的语义模型计算的答案。I/O正确性。在这种情况下,规范是成对的前条件和后条件。用这种方法可以证明,只要满足前置条件,后置条件就成立。适当的语义对目标变量的初始绑定和结果绑定之间的函数依赖性进行建模。I/O和调用正确性。规范仍然是成对的前-后条件。用这种方法,我们还可以证明所有的过程调用都满足这些先决条件。适当的语义模型之间的功能依赖关系的初始和最终绑定的变量的目标和信息的调用模式。如前所述,第二个抽象步骤涉及选择一个抽象域来近似属性。当然,我们可以为程序验证提供所有为属性的静态分析而设计的抽象域,如模式、类型、基础依赖性等。与静态分析的情况一样,通常我们失去了精度,但我们成功地得到了有限的规范。4断言和规范语言如[3]所示,第二个抽象步骤的一个特别有趣的选择是定义一个抽象域,其元素是形式规范语言中的公式(断言)在这种情况下,我们可以用适当的规范语言将程序的属性指定为断言事实上,断言让我们考虑一阶语言。我们假设的签名包括我们要验证的程序的函数、常量和变量设F是L的一组公式(断言),表示谓词的参数的性质。我们选择一个解释I来定义F的公式的语义。本文证明了在I估值σ,写为I| = σΦ,定义与通常一样。请注意,替换可以自然地被视为赋值。在此解释下,通过蕴涵在F上诱导出一个自然预序,即,ΨΦ当且仅当=Φ。我们的想法是使用F的公式作为抽象值来描述替换集合基本上我们认为科米尼、戈里和莱维5≤SSO|从断言到替换的具体化:γF(Φ):={σ∈Subst|我|=σΦ}。有可能表明,前面的具体化诱导(F,)和由集合包含排序的置换集合的幂集之间的伽罗瓦按照这种方法,我们可以为前面定义的证明方法提供验证条件为了证明I/O(和调用)的正确性,我们处理了前后指定I,O,函数,这些函数将每个纯原子p(x)关联到断言Φ,{ x }中的变量。I/O正确性。 在I/O正确性的情况下,从(1)获得的充分验证条件如下。对于每个子句c:= p(t)←p1(t1),.,pn(tn)∈P,我|= SI(p(x))[x/t]<$Φ 1<$··<$Φ n<$SO(p(x))[x/t],(cO)其中Φj:=.SO(pj(xj))[xj/tj]ifI|=SI(p(x))[x/t]<$SI(pj(xj))[xj/tj]否则为TRUEI/O和调用正确性。 在I/O和调用正确性的情况下,从(1)中获得的充分验证条件如下。对于每个子句c:= p(t)←p1(t1),.,pn(tn)∈P且每个k≤ n,和我|=SI(p(x))[x/t]<$SO(p1(x1))[x1/t1]< $ ··< $SO(pk−1(xk−1))[xk−1/tk−1]<$SI(pk(xk))[xk/tk],(c一)我|= SI(p(x))[x/t]<$SO(p1(x1))[x1/t1]< $ ···< $(c)第(1)款SO(pn (xn))[xn/tn[1]SO(p(x))[x/t],只要关系=是可判定的,我们就有一个有效的测试来检查条件。一个例子是[17]中的属性语言,它允许人们表达术语的属性,包括它们的类型和其他与静态分析相关的属性。虽然是可判定的,但可以用这些语言表达的属性类是一次性给出的此外,诸如- sertion语言的表达能力是有限的。一个更有趣的情况是让用户能够通过定义逻辑程序来定义自己的属性。如前所述,允许人们表达通过逻科米尼、戈里和莱维6辑程序定义的属性的断言语言已经在文献中定义在[14]中,这样的语言被用来科米尼、戈里和莱维7生成与程序点相关联的断言,这些断言将在运行时通过执行具有适当运行时值的逻辑程序来验证[7]提出了一种新的语言,让用户与调试器进行通信在这种语言中,规范是逻辑程序,用户断言用于交互式地诊断错误。在所有这些方法中,用户定义的逻辑程序的作用是允许扩展地导出关于预期行为的信息,即:规格。它们实际上用于对运行时值执行断言,因此检查每个程序的回答是否也满足断言。在本文中,我们提出了一种方法,其中用户定义的逻辑程序被用来有意地获取信息的预期行为。这是通过使用用户定义的程序来语法转换验证条件并证明它们来实现的本文提出的方法考虑了一种语言,其中断言是建立在用户定义的谓词上的公式这些谓词的含义由某些用户定义的逻辑程序来指定一旦导出了验证条件,就可以使用[12]中描述的程序和变换技术来证明根据我们想要验证的属性,可以使用这些技术 例如,如果我们想证明程序w.r.t. 计算的答案,我们应该小心使用保持计算的答案语义的转换。正如我们将在下面的例子中展示的那样,一般来说,为了证明我们的验证条件,只有简单的展开步骤是足够的,而对于一些更复杂的步骤,我们需要通过使用目标替换规则来证明一些中间引理[12],这允许我们用等价的(w.r.t.)选择的语义)之一。然而,值得注意的是,这些中间引理的生成通常可以通过使用展开/折叠证明方法来获得,如[13]所示。本文主要介绍了一些例子,说明我们的验证方法是如何正如下面的程序将显示的那样,大多数验证条件都很容易通过使用几个展开步骤来证明这意味着验证条件的过程可以自动化或至少半自动化。4.1反应系统我们考虑图的Prolog程序1旨在模拟一种简单的硬币回收机的可能形式,该机器接受10美分的欧元硬币,并以10美分的价格返还水,以20美分的价格返还硬币。当需要时,水会立即提供,而由于机器必须预热,因此被服务者可能需要一段时间才能得到服务行为被建模为一个无限的对(输入,输出)列表可能的输入是科米尼、戈里和莱维8warm(X)›→TRUEc1:e00([(null,null)|X]):-e00(X)。c2:e00([(10,null)|X]):-e10(X)。c3: e00([(水,哔声))|X]):-e00(X)。c4:e00(咖啡,哔)|X]):-e00(X)。c5:e10([(null,null)|X]):-e10(X)。c6:e10([(10,null)|X]):-e20(X)。c7: e10([(水,水)|X]):-e00(X)。c8:e10([(咖啡,哔声)|X]):-e10(X)。c9:e20([(null,null)|X]):-e20(X)。cA:e20([(水,水)|X]):-e10(X)。cB:e20([(咖啡,咖啡)|X]):-e00(X)。cC:e20([(coffee,null)|X]):-温暖(X)。cD: warm([(null,null)|X]):-warm 1(X)。cE:warm([(null,coffee))|X]):-e00(X)。cF:warm1([(null,coffee))|X]):-e00(X)。图1.一、 自动售货机计划和输出为这种系统的具体语义必须对部分答案进行建模,以便能够表达无限行为。然而,断言域上的(1)归结为第5页上提出的相同的充分条件因此,解释I模拟了程序的部分答案。我们想要证明的性质是,如果我们插入20美分并按下咖啡杯请求按钮,咖啡杯最终会到来。具体如下:SI:=SO:=e00(X)›→子列表([(10,),(10,),(coffee,)],X)函数X(x,X)e20(X)›→sublistX([(coffee,)]、X)warm1(X)›→TRUEcode00(X)›→match([(10,),(10,),(coffee,)],(,coffee),X)匹配10(X)›→matchX([(10,),(coffee,)],(,coffee),X)e20(X) ›→matchX([(coffee,)],( ,coffee),X)温暖(X) ›→matchX([ ],(,coffee),X)匹配warm 1(X)›→matchX([],(,coffee),X)科米尼、戈里和莱维sublist([(10,),(10,),(coffee,)],X)9sublist(Xs,Ys):-sublistX(Xs,Ys).子列表(X,[Y|Ys]):-子列表(Xs,Ys)。sublistX([],Xs).sublestX([Y| Xs]、[Y| Ys]):-sublistX(Xs,Ys)。match(Xs,X,Ys):-matchX(Xs,X,Ys).匹配(Xs,X,[Y| Ys]):-match(Xs,X,Ys).matchX([],X,[X|_]).matchX([],X,[Y| Ys]):-matchX([],X,Ys).matchX([Y| Xs]、X、[Y| Ys]):-matchX(Xs,X,Ys)。图二、用户为图1的程序定义的谓词1其中用户定义谓词的定义见图2。由于前置条件所表达的属性不需要被系统的所有轨迹明确地验证,所以我们不关心调用模式的正确性。因此,我们使用I/O正确性模式,它产生了以下归纳条件。值得注意的是,我们将要使用的展开已被证明可以保持计算的答案语义。对部分回答语义的扩展是直接的。第c1条验证条件是sublist([(10,),(10,),(coffee,)],[(null,null)|X]))match([(10,),(10,),(coffee,)],(,coffee),X)=match([(10,),(10,),(coffee,)],(,coffee),[(null,null)|X])因为我们可以证明|= SI(e 00(Y))[Y/[(null,null)|X]]= SI(e00(Z))[Z/X],即,我|=sublist([(10,),(10,),(coffee,)],[(null,null)|X])=sublist([(10,),(10,),(coffee,)],X)事实上,通过在前提中展开原子,后一个条件被重写为sublist([(10,),(10,),(coffee,)],X)科米尼、戈里和莱维sublist([(10,),(10,),(coffee,)],X)10sublistX([(10,),(10,),(coffee,)],[(null,null)|X])=科米尼、戈里和莱维sublist([(10,),(10,),(coffee,)],X)11然后,通过展开sublistX,我们得到sublist([(10,),(10,),(coffee,)],X)coffee= coffeesublist([(10,),(10,),(coffee,)],X)我们可以证明验证条件成立,因为通过一些展开步骤和逻辑蕴涵性质,它可以重写为sublist([(10,),(10,),(coffee,)],[(null,null)|X]))match([(10,),(10,),(coffee,)],(,coffee),X)=match([(10,),(10,),(coffee,)],(,coffee),X)matchX([(10,),(10,),(coffee,)],(,coffee),[(null,null)|X]),这是一个命题重言式。通过在前提中使用一些展开步骤,我们可以证明,sublist([(10,),(10,),(coffee,)],[(10,null)|X])=sublistX([(10,)、(咖啡)]、X)然后(通过一些展开步骤和逻辑蕴涵性质),我们可以证明验证条件sublist([(10,),(10,),(coffee,)],[(10,null)|X])matchX([(10,),(coffee,)],(,coffee),X)= 0match([(10,),(10,),(coffee,)],(,coffee),[(10,null)|X])条款c3类似于c1条款c4类似于c1通过在前提中使用展开步骤,我们可以证明:sublistX([(10,),(coffee,)],[(null,null))|X])=sublistX([(10,)、(咖啡)]、X)因为前提是假的。然后我们可以证明验证条件sublistX([(10,)、(咖啡)],[(null,null)|X])matchX([(10,),(coffee,)],(,coffee),X)= 0matchX([(10,),(coffee,)],(,coffee),[(null,null)|X])科米尼、戈里和莱维sublist([(10,),(10,),(coffee,)],X)12条款c6类似于c2通过在前提中使用展开步骤,我们可以证明:sublistX([(10,),(coffee,)],[(water,water))|X])=科米尼、戈里和莱维13因为前提是假的。然后我们可以证明验证条件sublistX([(10,)、(咖啡)],[(水,水)|X])match([(10,),(10,),(coffee,)],(,coffee),X)=matchX([(10,),(coffee,)],(,coffee),[(water,water)|X])条款c8类似于c5条款c9类似于c5条款cA类似于c7条款通过在前提中使用展开步骤,我们可以证明:sublistX([(coffee,)],[(coffee,coffee))|X])=sublist([(10,),(10,),(coffee,)],X)因为前提为真而结论为假。然后我们可以证明验证条件sublistX([(coffee,)],[(coffee,coffee))|X])TRUE =matchX([(coffee,)],( ,咖啡),[(咖啡,咖啡)|X])通过在前提中使用展开步骤,我们可以证明,sublistX([(coffee,)],[(coffee,null))|X])=TRUE然后我们可以证明验证条件sublistX([(coffee,)],[(coffee,null))|X])matchX([ ],(,coffee),X)=matchX([(coffee,)],( ,coffee),[(coffee,null)|X])子句cD由于TRUE= TRUE,我们可以证明验证条件TRUEmatchX([],(,coffee),X)=matchX([],(,coffee),[(null,null)|X])通过在前提中使用展开步骤,我们可以证明,TRUE/=0sublist([(10,),(10,),(coffee,)],X)因为前提为真而结论为假。然后我们可以证明验证条件TRUE= NULLmatchX([],(,coffee),[(null,coffee))|X])条款cF类似于cE科米尼、戈里和莱维14∧ ⇐⇒∧我们的结论是,该程序是部分正确的w.r.t.规格。请注意,如果我们使用了一个更强的验证条件来验证调用的正确性,我们将无法成功地证明它,因为我们不能保证每个过程调用都验证了先决条件。4.2append的一个简单属性我们现在考虑append程序c1:append([],Ys,Ys).c2:append([X| Xs]、Ys、[X| Zs]):-append(Xs,Ys,Zs).我们想证明列表的长度是保持不变的。因此,规格是SI:=append(X,Y,Z)<$→list(X)th(X,Lx)list(Y)长度(Y,Ly)SO:=append(X,Y,Z)<$→list(Z)length(Z,Lz)<$Lz=Lx+Ly其中用户定义谓词的定义是list([])。列表([X| Xs]):-list(Xs).length([],0).长度([X| Xs,Lx):-长度(Xs,Lxs),Lx = Lxs +1。由前提条件表达的属性现在必须由所有输入明确验证因此,我们使用I/O和调用正确性模式,它产生了以下归纳条件。值得注意的是,这里我们需要一个语义模型的算术自然。 这只是为了简化符号,因为我们应该选择使用数字的一阶表示(0,s(0),. ),将sum实现为用户定义的谓词,然后使用计算的答案语义。条款c1O条件是list([])th([],Lx)list(Y)th(Y,Ly)=Lz=Lx+Ly它可以通过首先证明长度(Y,Ly)的函数来证明(即,长度(Xs,X)长度(Xs,Y)长度(Xs,X)X = Y),通过使用[13]的折叠/展开证明技术,然后在前提中使用展开步骤。事实上,通过对矩阵h([],LX)和列表t([])进行展开,我们可以得到list(Y)th(Y,Ly)=list(Y)th(Y,Lz)Lz=0+Ly科米尼、戈里和莱维15c1:isort([],[]).c2:isort([X| Xs],Ys):-isort(Xs,Zs),insert(X,Zs,Ys).c3:插入(X,[],[X])。c4:插入(X,[Y| Ys]、[Y| Zs]):-X> Y,插入(X,Ys,Zs)。c5:插入(X,[Y| Ys],[X,Y| Ys]):-X =Y›→X > Y(X)→int(X)由于前提条件所表达的属性必须由所有输入明确验证,因此我们使用I/O和调用正确性模式,这产生了以下验证条件。条件是intlist([])= intlist([])sort([],[]),这可以通过几个展开步骤来证明。条件是intlist([ X])。|Xs])=xintlist(Xs),intlist([X|Xs])intlist(Zs)sort(Xs,Zs)=int(X)intn(Z)intn(Z)整数科米尼、戈里和莱维18两者都可以通过在前提中展开的几个步骤来证明科米尼、戈里和莱维19|∧⇒|||∧条件是intlist([X|Xs])intlist(Zs)sort(Xs,Zs)intlist(Ys)sor t([X|Zs], Ys)=整数t(Ys)≠ t([X|Xs], Ys)它可以通过首先证明perm的一个性质来证明,即,perm(Xs,Zs)perm([X|Zs],Y s)([X|Xs],Ys)。条款c3O条件是int(X)≠int list([])≠d([])=int list([X])≠t([X],[X]),这可以通过几个展开步骤来证明第c4条I条件是int(X)int n([Y |Y s])ord([Y |Y s])=int(X)int(Y)int(X)int n([Y |Y s])ord([Y |Y s])X> Y =int(X)int(Y)intorder(Y s)两者都可以通过在前提中展开的几个步骤来证明条款c4O条件是int(X)int n([Y |Y s])ord([Y |Y s])X> Y intlist(Zs)sort([X|Y s],Zs)=[Yintlist([Y |[X,Y](X,Y)|Y s]、[Y|Zs])它可以通过首先证明一个排序属性来证明,即,sort([XY s],Zs)order([Y Y s])X >Y=sort([X,Y Y s],[Y Zs]),然后在前提中进行一些第c5条I条件是int(X)int n([Y |Y s])ord([Y |Ys])=int(X)int(Y),这可以通过展开步骤来证明。第c5条O条件是int(X)int n([Y |Y s])ord([Y |Y s])X ≤ Y =intlist([X,Y |[X,Y])n = 0|Y s],[X,Y |Y s])它可以通过首先证明perm的一个性质来证明,即,intlist(Xs)=perm(Xs,Xs),然后在前提中进行一些展开步骤⇒科米尼、戈里和莱维20我们的结论是,该程序是部分正确的w.r.t.规格。
下载后可阅读完整内容,剩余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直接复制
信息提交成功