没有合适的资源?快使用搜索试试~ 我知道了~
理论计算机科学电子笔记137(2005)205-224www.elsevier.com/locate/entcs模型检测向下模拟格雷姆·史密斯1澳大利亚昆士兰大学信息技术与电气工程学院约翰·德里克2谢菲尔德大学计算机科学系She Wereld,英国摘要本文展示了如何向下模拟可以检查使用现有的时序逻辑模型检查器。特别是,我们展示了如何分支时间时序逻辑CTL可以用来编码标准的向下模拟条件。我们这样做是为了操作的阻塞或保护解释(通常用于指定反应式系统)以及许多基于状态的规范语言中使用的更常见的非阻塞解释该方法足够通用,可以与任何基于状态的规范语言和任何可以编码该语言的CTL模型检查器一起使用。关键词:精化,模型检测,CTL。1介绍基于状态的形式主义的数据精化通常通过证明具体系统模拟抽象系统来检查[7]。模拟的概念是由向下和向上的模拟规则捕获的,这些规则包括与具体和抽象系统的可能初始化和转换相关的手工证明这些条件,即使是简单的系统,1 电子邮件地址:smith@itee.uq.edu.au2电子邮件:J. dcs.shef.ac.uk1571-0661 © 2005 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi:10.1016/j.entcs.2005.04.032206G. 史密斯,J。Derrick/Electronic Notes in Theoretical Computer Science 137(2005)最好的是冗长乏味,最坏的是容易出错。因此,通常认为有必要提供工具支持来证明数据细化。大多数现有的工具支持涉及定理证明器的使用这些工具要求用户设计大部分的证明步骤,因此可以帮助用户深入了解细化。然而,它们也需要大量的数学证明专业知识。此外,当用户无法证明一个条件时,这可能是因为条件不为真(并且细化不成立),或者因为所需的证明对用户来说太难(并且细化可能成立)。区分这两种情况往往是困难的[4]。与定理证明相对,模型检查[3]是一种全自动的技术,用于确定特定系统是否满足给定的属性。模型检查器彻底检查系统的状态空间,以确定属性是否成立。在后一种情况下,模型检查器通常会提供一个反例或见证,提供对属性不成立的原因的深入了解。模型检查器最初仅限于有限系统,以及适合于建模系统的简单符号,其中复杂性在于控制结构,而不是数据,例如,硬件系统和通信协议。最近的进展意味着这些限制不再是绝对的。属性保持抽象的自动技术[10,16,2]和有界模型检查[5]是允许检查具有无限状态空间的系统的两种方法。强大的自动决策过程允许模型检查器语言支持高级规范结构,如lambda表达式,集合解析以及泛存在量化器[6]。因此,可以对用高级语言编写的检查规范进行建模[18]。因此,可以考虑使用模型检查器来证明数据修正。这样做有两个主要挑战。首先,模型检查器期望在单个系统上检查属性。因此,我们需要把抽象和具体的系统结合起来。其次,检查的属性通常是行为属性,即,通过系统状态的路径的性质因此,我们需要将模拟条件表示为行为属性。如何做到这一点取决于如何将抽象和具体的系统结合起来。因此,这两项挑战是相互关联的。我们发现分支时间时序逻辑CTL [8]特别适合于模拟规则的建模。在本文中,我们展示了CTL模型检查器,例如,NuSMV [1]或SAL [5]可用于检查向下模拟的标准条件我们这样做既是为了系统G. 史密斯,J。Derrick/Electronic Notes in Theoretical Computer Science 137(2005)207具有阻塞或保护的操作解释,以及具有更常见的非阻塞解释的操作[7]。我们计划在未来的工作中将该方法扩展到向上模拟。在第二节中,我们介绍了时序逻辑CTL。在第3节中,我们描述了如何在阻塞语义下检查向下模拟,并在第4节中将这些想法扩展到非阻塞语义。我们的方法不是特定于特定的基于状态的规范语言,也不是特定的CTL模型检查器。在第5节中,我们讨论了在SAL中使用Z规范[20]实例化我们的方法的经验。我们在第6节结束。2CTL时态逻辑用于定义Kripke结构的属性。Kripke结构本质上是具有总转换关系的状态转换系统,即,其中每个状态具有至少一个启用的转换。通过Kripke结构的无限状态序列(其中每个状态通过转移关系与其后继状态相关)被称为路径。CTL [8]是一个分支时间时序逻辑,这意味着它的公式可以在Kripke结构的给定状态开始的所有路径上解释。我们写M,s0<$f来表示对于Kripke结构M,CTL公式f在状态s0中成立。在语法上,我们将CTL公式分为三类:(i) 那些其最外层运算符(如果有的话)不是时间运算符的,(ii) 最外层的算子是时间算子(X(下一个), U(直到), F(最终)或 G(总是)),并以存在路径量化器 E为前缀,以及(iii) 那些最外层的算子是一个以普适路径量化器A为前缀的时间算子的人。范畴(i)中的公式包括关于Kripke结构的状态的原子命题,以及其他CTL公式第(一)、(二)和(三)类。具体地说,如果f1和f2是CTL公式,那么<$f1、f1<$f2、f1<$f2、f1<$f2和f1惠f2也是。在类别(ii)中的公式表示的属性是真的至少有一条路径的Kripke结构M从s0开始。例如,EXf1,其中f1是CTL公式,声明对于至少一条从状态s0开始的路径,f1在下一个状态中保持。类似地,E[f1Uf2]指出,对于至少一条从s0开始的路径,f1保持直到f2保持的某个状态此外,EFf1声明对于至少一个从s0开始的路径,f1最终成立,并且EGf1声明对于至少一个从s0开始的路径,f1总是成立。208G. 史密斯,J。Derrick/Electronic Notes in Theoretical Computer Science 137(2005)范畴(iii)中的公式表示了在M的从s0开始的所有路径上都为真的性质。例如,AXf1,其中f1是CTL公式,声明对于从状态s0开始的所有路径,f1在下一个状态中成立。类似地,A[f1Uf2]指出,对于从s0开始的所有路径,f1成立,直到f2成立的某个状态此外,AFf1指出,对于从s0开始的所有路径,f1最终成立,AGf1指出,对于从s0开始的所有路径,f1始终成立。更正式地说,上面介绍的CTL公式的语义可以给出如下(其中p是一个原子命题,f1和f2是CTL公式)。CTL的语义(i)M,s0pip在s0M,s0f1i上为真,而不是M,s0f1M,s0f1f2iM,s0f1和M,s0f2M,s0f1f2iM,s0<$(<$f1<$f2)M,s0f1f2iM,s0f1f2M,s0f1惠f2iM,s0(f1f2)(f2f1)(ii)M,s0 EX f1i对于 某条路径(s0,s1,. . ),M,s1<$f1M,s0<$E [f1Uf2] i对某条路径(s0,s1,. . ),存在一个i,M,si,f2和对于所有ji,M,sjf1M,s0EFf1iM,s0E[trueUf1](<$aJ∈AS·aJR cJ<$a AOpiaJ)定义3.1的条件1称为初始化。 它要求对于每一个具体的初始状态,都有一个由检索关系R关联的初始抽象状态。条件2被称为适用性。它要求抽象操作仅在与具体状态相关的状态中启用,其中相应的3操作的输入和输出参数可以嵌入到S的状态中,如Smith和Winter [19]所述。210G. 史密斯,J。Derrick/Electronic Notes in Theoretical Computer Science 137(2005)响应具体操作被启用,反之亦然。条件3被称为正确性。它要求无论何时一个具体操作可以导致状态变化(t,tJ),对于任何与t相关的抽象状态s,相应的抽象操作可以导致(s,sJ),使得sJ与tJ相关。也就是说,具体操作的结果与相应的抽象操作的要求是一致的。3.1一般方法在本节中,我们讨论了一种通用的方法来检查下的模拟阻塞语义与CTL模型检查。我们首先提供了用于单独检查每个向下模拟条件然后,我们将这些系统组合成一个系统,在这个系统中,所有的条件都可以同时检查。后一个系统也可以用来单独检查条件;当一个细化不成立时,这对发现问题很有用。我们在模型中只考虑了检查条件所必需的约束。可以添加更多的约束以使模型的状态空间更小,从而使模型检查更有效。然而,确定实现这一目标的最佳约束条件将作为未来的工作。为了说明我们的方法,考虑以下以Z [20]风格给出的简单抽象和抽象系统有一个变量x,它初始为0,可以递增1或2。混凝土系统有一个变量y,初始值为0,可以递增1. 两个系统的变量上限都是10。A=x[x:0] 。 . 第10页]AInit=^[A|x=0]AOp=^[A|xJ=x+ 1<$xJ=x+2]C=0. . 第10页]CInit=^[C|y=0]COp=^[100C|yJ=y+1]在这个例子中,指定C是在检索关系x=y下对A的向下模拟。如引言中所述,我们需要将这些系统组合起来,以检查模拟条件。正如所料,定义3.1的条件既指抽象的状态,也指具体的状态。因此,一个合并的系统必须能够访问两者。我们假设抽象系统和具体系统的状态变量是不相交的,就像上面的例子一样如果它们不是,它们可以通过系统的重命名而不相交。例如,变量x可以重命名为A。x在抽象规范中和C. x在具体操作中。然后,组合状态可以包括G. 史密斯,J。Derrick/Electronic Notes in Theoretical Computer Science 137(2005)211两个系统的变量对于我们的例子,我们将有声明x:0.. 10和y:0。10在我们的联合系统中。3.1.1初始化我们首先考虑初始化条件。这个条件要求对于每个具体的初始状态,我们能够找到一个由检索关系R关联的抽象初始状态。因此,我们需要一种方法,可以访问我们的组合系统中的所有具体初始状态。 这样做的一种方法是初始化组合系统,以便初始化状态的具体部分。对于我们的例子,我们的组合系统M初始化=^[x:0. . 10;y:0。 . 第10页]并将被初始化如下。Ini tinit=^[Minit|y=0]为了检查是否存在与给定的具体初始状态相关的抽象初始状态,我们引入了一个操作InitAinit,它将状态的抽象部分更改为初始值,并保持具体部分不变。对于我们的例子,这将是以下内容Ini tAinit=^[Minit|xJ=0yJ=y]注意,由于InitAinit在任何状态下都被使能,因此转换关系是Kripke结构所需的总和。这对于任何抽象的具体化都是正确的,除了没有抽象初始状态的退化情况现在,我们假设用户不会提供这种退化的抽象规范。我们将在本节结束时回到这个问题给定上述操作,初始化条件成立,如果操作可以执行,使得状态的结果抽象和具体部分由R相关。对于我们的示例,此检查在CTL中表示如下。EXx=y也就是说,存在下一个状态,使得x=y。请注意,CTL运算符EX允许我们确定是否可以执行操作并达到特定状态。这种存在性量化下一个状态的能力使得CTL对于捕获仿真条件特别有用。 如果有一个以上的抽象初始状态,那么上面EX的使用意味着只有其中一个需要与具体初始状态相关212G. 史密斯,J。Derrick/Electronic Notes in Theoretical Computer Science 137(2005)我们检查初始化的方法总结如下(以Z风格):A和C分别表示抽象和具体状态,AInit和CInit分别表示抽象和具体初始化,R表示检索关系。系统:M初始化=^[A;C]Ini tinit=^[Minit|Cini t]Ini tAinit=^[Minit|AInitC]初始化检查:EXR3.1.2适用性我们现在考虑适用性条件。为了检查适用性,我们需要能够确定每个抽象和具体操作是否可以发生。CTL只允许引用状态变量的命题,而不允许操作。因此,我们在组合状态中引入变量ev来表示发生的最后一个操作的名称,并且我们对ev类型的值使用不同的字体。对于我们的示例,用于检查适用性的组合系统的状态如下所示(Choose操作在下面解释)。Mapp=n[x:0. . 10;y:0。 . 10;ev:{AOp,COp,Choose}]适用性条件要求抽象操作可以从抽象状态发生,恰好当相应的具体操作可以从通过检索关系R与抽象状态相关的具体状态发生时。因此,我们需要一种手段,能够访问抽象和具体部分相关的所有组合状态。请注意,该条件并不要求抽象和具体状态都是可达的;这一点我们将在第5节中返回。同样,我们可以通过对我们的组合系统进行适当的初始化来做到这一点;在这种情况下,对R成立的所有状态进行初始化。对于我们的示例,我们将如下初始化组合系统。(Theev初始值并不重要,且未指定。)Ini tapp=^[Mapp|x=y]然后,我们介绍了相应的操作的抽象和具体的操作。对于我们的示例,我们有以下内容。AOpapp=^[Mapp|(xJ=x+ 1<$xJ=x+2)evJ=AOp]COpapp=^[M]app|yJ=y+ 1[evJ=COp]G. 史密斯,J。Derrick/Electronic Notes in Theoretical Computer Science 137(2005)213,app1 1由于通常不会在所有状态下都启用操作,例如,例如,当x= 10和y= 10时,AOpapp和COpapp这个操作Choose总是启用的,它只是选择一个新的状态;实际状态并不重要,也不需要指定。选择app=^[Mapp|evJ=Choose]具体化现在表示一个Kripke结构,并且适用性条件成立,如果每当可以执行抽象操作时,可以执行相应的具体操作,反之亦然。对于我们的示例,该检查可以用CTL表示如下。EX(ev=AOp)惠EX(ev=COp)(Note我们写ev=AOp而不是ev=AOpapp,因为ev的类型是一组名称,而不是实际操作本身。我们检查适用性的方法总结如下(Z样式):AOp1,.,AOpn表示抽象操作,而COp1,.,COpn,相应的具体操作。系统:Mapp={A;C;ev:{A0p1, . . ,AOpn,COp1, . . . ,COpn,Choose}]Ini tapp=^[Mapp|R]AOp1app=^[M|AOpevJ=AOp].AOP=^[M|AOpevJ=AOp]n, appapp nnJCOp1,app=^[Mapp|缔约方会议1日.=COp1]COpn,app=^[Mapp|COpN=COpn]选择app=^[Mapp|evJ=Choose]适用性检查:(EX(ev=AOp1)惠EX(ev=COp1)).(EX(ev=AOpn)惠EX(ev=COpn))3.1.3正确性我们终于找到了正确性。与适用性一样,我们需要能够引用操作的发生来检查正确性。因此,我们再次引入变量ev来表示最后一次发生的操作国214G. 史密斯,J。Derrick/Electronic Notes in Theoretical Computer Science 137(2005)对于我们的示例,组合系统的最大优点是检查适用性条件。Mcorr=^Mapp正确性条件要求当对应的具体操作可以从通过检索关系R与抽象状态相关的具体状态发生时,抽象操作可以从抽象状态发生。因此,我们再次将组合系统初始化为R成立的状态。对于我们的例子,我们将初始化组合系统的适用性条件Initcorr=^Initapp此外,正确性条件要求通过执行具体操作而达到的任何状态都被R与通过执行抽象操作而达到的抽象状态相关联。如果组合系统中对应于抽象操作的操作不改变具体状态,并且对应于具体操作的操作不改变抽象状态,则我们可以在CTL中捕获这一点。也就是说,对于我们的示例,我们有以下操作。AOpcorr=^[AOpapp|yJ=y]COpcorr=^[COpapp|xJ=x]这允许我们顺序执行操作COpcorr和AOpcorr,使得所达到的最终状态的抽象部分与仅执行AOpcorr所能达到的部分相同,并且具体部分与仅执行COpcorr所能达到的部分相同。我们再次需要一个“选择”操作来确保转换关系是完全的。选择corr=^选择应用程序然后,正确性条件成立,如果在一个具体的操作被执行后,相应的抽象操作可以被执行,并导致一个状态,其中R成立。对于我们的示例,该检查可以用CTL表示如下。AX(ev=COpX(ev=AOpX=y))注意,使用CTL操作符AX来确保COp的所有后状态都正确。考虑了EX运算符在AX运算符的范围内,因此G. 史密斯,J。Derrick/Electronic Notes in Theoretical Computer Science 137(2005)2151通过执行COpcorr来量化所达到的状态的下一状态。(For由于AX仅查看通过执行COpcorr而达到的那些状态,因此我们不需要关心初始化之后ev的值。我们检查正确性的方法总结如下(Z风格)。系统:Mc或rr={A;C;ev:{A0p1, . . ,AOpn,COp1, . . . ,COpn,Choose}]Ini tcorrr=^[Mcorrr|R]AOp1,corr=^[Mcorr| AOp1∧ Ξ C ∧ ev J= AOp].AOpn,corr=^[Mcorr|AOpnCevJ=AOpn]COp1,corrr=^[M]corrr|[COp1].COpn,corr=^[Mcorr|COpnAevJ=COpn]选择corrr=^[M]corrr|evJ=Choose]正确性检查:AX(ev=COp1EX(ev=AOp1R)).AX(ev=COpnEX(ev=AOpnR))3.1.4向下模拟我们已经展示了如何构造三个系统,每个系统都可以用来检查其中一个向下模拟条件。为了同时检查所有的条件,我们现在提出一个结合上述条件的系统。适用性条件Mapp的系统与正确性条件Mcorr的系统之间的唯一区别是在Mcorr中包含了抽象状态在相应的操作中不改变的约束。具体操作,反之亦然。这些约束条件不影响CTL公式检验适用性的正确性。因此,可以在Mcorr上检查适用性和正确性。要检查初始化条件,需要添加InitA操作。它也必须包含在ev的类型中,以允许识别对应于操作的转换。对于我们的示例,所需的状态如下所示。Mds=^[x:0. . 10;y:0。 . 10;ev:{InitA,AOp,COp,Choose}]初始化检查还需要不同的初始状态集。为了适应所有的检查,我们扩大了初始化,以允许所有需要的初始状态。对于我们的例子,初始化如下。216G. 史密斯,J。Derrick/Electronic Notes in Theoretical Computer Science 137(2005)1.,ds1 1JIni tds=^[Mds|(y=0x=y)]除了包含谓词外,操作与前面一样evJ=InitA中的InitA。 对于我们的示例,我们有以下内容。Ini tAds=^[Mds|xJ=0yJ=yevJ=I ni tA]J J J JAOpds=^[Mds|(x=x+ 1<$x=x+2)y=yev=AOp]COpds=^[Mds|yJ=y+ 1xJ=xevJ=COp]选择ds=^[Mds|evJ=Choose]然后,我们可以像以前一样检查每个条件,当限制到适当的初始状态时。对于我们的例子,初始化检查是在y= 0的初始状态上执行的y=0EX(ev=InitAx=y)适用性检查在x=y的状态上执行。x=y(EX(ev=AOp)惠EX(ev=COp))类似地,对x=y的状态执行正确性检查。x=yAX(ev=COpEX(ev=AOpx=y))我们检查向下模拟的方法总结如下(Z系统:Mds=^[A;C;ev:{I ni tA,AOp1, . . . ,AOpn,COp1, . . . ,COpn,Choose}]Ini tds=^[Mds|CInit[R]Ini tAds=^[Mds|AInitCevJ=I ni tA]AOp1ds=^[M|AOpCevJ=AOp].AOpn,ds=^[Mds|AOpnCev=AOpn]JCOp1,ds=^[Mds|COp1COp=COp].COpn,ds=^[Mds|COpnAevJ=COpn]选择ds=^[Mds|evJ=Choose]G. 史密斯,J。Derrick/Electronic Notes in Theoretical Computer Science 137(2005)217向下模拟检查:(CInitEXEX(ev=InitAEXR))∧(R=EX(ev=AOp1)惠EX(ev=COp1).EX(ev=AOpn)惠EX(ev=COpn)∧(RAX(ev=COp1EX(ev=AOp1R)).AX(ev=COpnEX(ev=AOpnR)Choose操作确保转换关系是所需的总数。因此,这种方法甚至适用于没有初始状态的退化抽象规范。或者,我们可以将抽象初始状态的存在作为方法的一个要求,从而能够从上面的系统中删除Choose操作4非阻塞语义状态转换系统的非阻塞语义是最常见的语义。它用于大多数流行的基于状态的规范语言,如Z [20]。在这种语义下,一个操作有一个前提条件,在这个前提条件之外,它的行为是不确定的。它的主要用途是在指定的顺序系统。给定第3节开头描述的系统,在非阻塞语义下,向下模拟定义如下[7]。定义4.1 A规范C =(CS,CI,{COp1,.,COpn})是规范A =(AS,AI,{AOp1,. ,AOpn}),如果在AS和CS之间存在检索关系R,使得对于所有i∈ 1. n.(i) c∈CI·(ii) a∈AS;c ∈CS·aR c<$((<$aJ∈AS·a AOpiaJ)<$(<$cJ∈CS·c COpicJ))(iii) a∈AS;c,cJ∈CS·(aJ∈AS·a AOpiaJ)a R c(aJ∈AS·aJR cjAAOpiaJ)定义4.1的条件1是初始化条件。它要求,对于每一个具体的初始状态,都有一个由218G. 史密斯,J。Derrick/Electronic Notes in Theoretical Computer Science 137(2005)检索关系R。条件2是适用条件。它要求抽象操作仅在与启用了相应具体操作的具体状态相关的状态中启用。条件3是正确性条件。它要求,每当一个具体的操作可以导致状态变化(t,tJ),对于任何与t相关的抽象状态s,如果相应的抽象操作被启用,那么它可以导致(s,sJ),使得sJ与tJ相关。4.1一般方法使用CTL模型检查器在非阻塞语义下检查向下模拟的一般方法我们使用相同的系统来处理各个条件,以及同时检查所有条件。4.1.1初始化初始化条件与阻塞语义相同。因此,它以相同的方式进行检查。4.1.2适用性适用性条件仅与阻塞语义的适用性条件不同,因为它具有隐含性,而不是声明抽象和具体操作被启用的谓词之间的等价性。在用于阻塞语义的相同系统Mapp下,我们可以如下所示地表示上一节示例的适用性检查。EX(ev=AOp)EX(ev=COp)更一般地,对于抽象操作AOp1,…、AOpn和对应的具体操作COp1、...,COpn,我们有下面的CTL公式。(EX(ev=AOp1))EX(ev=COp1)).(EX(ev=AOpn)EXEX(ev=COpn))4.1.3正确性正确性条件类似于阻塞模型,但需要启用抽象操作的额外前提G. 史密斯,J。Derrick/Electronic Notes in Theoretical Computer Science 137(2005)219.这是必需的,因为当对应的具体操作被启用时,抽象操作并不总是被启用。在用于分块语义的相同系统Mcorr下,我们可以将上一节示例的正确性检查表示如下(再次记住ev是一组名称)。EX(ev=AOp)AX(ev=COpEX(ev=AOpx=y))更一般地,我们有以下CTL公式(其中R表示检索关系)。(EX(ev=AOp1)AX(ev=COp1EX(ev=AOp1R).(EX(ev=AOpn)AX(ev=COpnEX(ev=AOpnR)回想一下,在这个正确性模型中,Mcorr是用Rtrue初始化的,也就是说,我们已经处于A和C通过检索关系相关联的状态。因此,没有必要用R来预先确定公式。然而,这在下面是必要的,因为用于向下模拟的模型Mds可以用R true或CInit true初始化。4.1.4向下模拟为了同时检查所有条件,我们遵循针对阻塞语义解释的方法。用于向下模拟检查的通用CTL公式如下(其中CInit表示具体初始化)。(CInitEXEX(ev=InitAEXR))∧(R(EX(ev=AOp1)EX(ev=COp1)).(EX(ev=AOpn)EXEX(ev=COpn)∧(R(EX(ev=AOp1)AX(ev=COp1EX(ev=AOp1R)∧.(EX(ev=AOpn)AX(ev=COpnEX(ev=AOpnR)220G. 史密斯,J。Derrick/Electronic Notes in Theoretical Computer Science 137(2005)5讨论上一节介绍的方法可以应用于任何基于状态的规范语言和任何支持该规范语言的CTL模型检查器。我们已经在SAL中使用Z及其编码进行了实验[18]。到目前为止,我们的实验还没有利用SAL工具的全部功能。因此,我们被限制在具有有限且相对较小的状态空间的规范。SAL支持许多优化功能,以及变量抽象功能,可以有效地用于忽略不影响我们希望证明的属性的这些特征需要作为扩展我们可以处理的规格大小的手段进行此外,SAL的未来版本预计将支持谓词抽象[10,16,2];我们认为这对于将我们的方法用于更大的示例至关重要。使用SAL,我们已经能够以最低限度的一旦规格以适当的输入格式写入,例如,在第271-273页示例的初始版本中,[21]检索关系太弱4,如果不完成整个证明,就不会立即明显。SAL中向下模拟的编码很容易就发现了这个错误,尽管破译反例需要对这个问题有一定的理解我们并不是第一个使用工具支持来检测此错误的人。Robinson成功地发现了这一点,他开发了一种使用Possum Z动画器自动检查向下模拟的方法[15]。他的方法依赖于Possum评估复杂Z谓词的能力,这些谓词涉及抽象和具体规范状态的量化。我们还在SAL中编码了Robinson上述示例中的问题是由于检索关系不覆盖不可达状态,而规范实际上是在加强的检索关系下通过向下模拟而相关的。我们推测这是一个经常发生的错误,因为规范通常更关注系统的可达状态。不可达状态并不影响一个规范是否是另一个规范的向下模拟。向下模拟条件考虑不可达状态的原因是,否则可达状态将需要[4]这个错误在后来的文本版本中通过在其中一个规范中增加不变量得到了纠正。G. 史密斯,J。Derrick/Electronic Notes in Theoretical Computer Science 137(2005)2211作为排放条件的一部分进行计算。这不是一个简单的手工或定理证明。然而,它是模型检查过程的固有部分,即,因为模型检查涉及对系统的(可达的)状态空间的穷举搜索。因此,我们可以将我们的方法限制为只检查可达状态,因此,只需要一个与可达状态相关的检索关系;一个可以说更适合规范因此,我们不会检查完整的向下模拟条件;然而,对可达状态的限制足以知道一个规范是另一个规范的向下模拟。要做到这一点,我们需要将系统初始化为一个初始化具体状态的系统,并且不允许在初始化抽象状态的操作之前执行抽象操作。这可以通过包括表示抽象状态是否已经被初始化的Mreach=^[A;C;b:{0,1};ev:{I ni t,I ni tA,AOp1, . . . ,AOpn,COp1, . . . ,COpn,Choose}]Ini treach=^[Mreach|CInit[b]=0[ev]=I ni t]J JIni tAreach=^[Mreach|b =0AInitCb =1ev=I ni tA]AOp1,reach=^[Mreach| b = 1 ∧ AOp1∧ Ξ C ∧ bJ= b ∧ ev J= AOp].AOpn,reach=^[Mreach|b =1<$AOpn<$$>C<$bJ=b <$evJ=AOpn]COp1,reach=^[Mreach|COp1[A][b][J=b][ev][J=COp1].COpn,reach=^[Mreach|COpnAbJ=b evJ=COpn]选择reach=^[Mreach|evJ=Choose]然后,M到达中的所有状态将包括可到达的抽象状态和具体状态。由于Mreach的初始状态仅限于状态的具体部分被初始化的那些状态,因此检查初始化的条件将被简化如下。EX(ev=InitAR)需要修改适用性和正确性条件,以便对M中R成立的所有状态进行检查。这可以 对于非阻塞模型,可以通过简单地用时间算子AG来预先固定公式来完成。可通过以下公式检查适用性。222G. 史密斯,J。Derrick/Electronic Notes in Theoretical Computer Science 137(2005)AG(R(EX(ev=AOp1)EX(ev=COp1)).(EX(ev=AOpn)EX(ev=COpn)类似地,正确性将由以下公式检查AG(R)(EX(ev=AOp1)AX(ev=COp1EX(ev=AOp1R)∧.(EX(ev=AOpn)AX(ev=COpnEX(ev=AOpnR)对于阻塞模型,我们还必须在适用性和正确性检查的前提中检查b= 1。这在上述公式中是不必要的,因为EX(ev=AOp)形式的前件意味着b= 1。我们以另一种自动检查基于状态的细化的方法的简要讨论来结束本节。 在CSP模型检查器FDR中有许多基于Z的语言子集的编码[9,14,13]。FDR不是一个时态逻辑模型检查器。 相反,它检查两个规范之间的细化。它通过比较规范的失败/分歧语义来做到这一点;这种方法相当于基于模拟的细化[12,11]。这种方法的优点是不需要检索关系然而,由于不可能检查单个模拟条件,因此在精化不成立时发现问题可能更加困难。此外,由于FDR是为进程代数而开发的,而不是基于状态的符号,因此编码这种符号更加困难;例如,迄今为止,FDR中没有Z的完整编码。我们认为这两种办法是相辅相成的。6结论在本文中,我们已经展示了如何向下模拟可以检查使用现有的时序逻辑模型检查器。特别是,我们已经展示了如何分支时间时序逻辑CTL可以用来编码标准的向下模拟条件。我们这样做是为了操作的阻塞或保护解释(通常在指定反应式系统时使用)以及许多基于状态的规范语言中使用的更常见的非阻塞操作解释(用于建模顺序系统)。我们已经使用该方法来检查Z规范之间的向下模拟G. 史密斯,J。Derrick/Electronic Notes in Theoretical Computer Science 137(2005)223使用SAL CTL模型检查器进行验证。然而,这种方法是通用的,足以与任何基于状态的规范语言和任何CTL模型检查器一起使用,其中可以对语言进行编码。我们设想的方法变得更加适用,因为它利用了当前在时态逻辑模型检测社区的研究成果,将模型检测扩展到更大的系统,甚至在有限的状态空间。确认我们要感谢Leonardo de Rezia和John Rushby在SAL的使用上给予的帮助。这篇文章也得益于Kirsten Winter和Ian Hayes的引用[1] A. Cimatti,E.克拉克角,澳-地Giunchiglia和M.罗维里NuSMV:一个新的符号模型验证器。在N. Halbwachs和D. Peled,编辑,计算机辅助验证国际会议(CAVSpringer-Verlag,1999.[2] E. Clarke,O. Grumberg,S. Jha,Y. Lu和H.维斯反例引导的抽象细化。在东亚。Emerson和A.P. Sistla,编辑,计算机辅助验证国际会议(CAVSpringer-Verlag,2000.[3] E. Clarke,O. Grumberg和D.佩尔德。 模型检查。麻省理工学院出版社,2000年。[4] D. Craigen,S.Gerhart和T.拉斯顿形式化方法现实检验:工业应用。IEEE软件工程学报,21(2):90[5] L. de Escherichia,S.奥雷Rushby,N.尚卡尔,M。Sorea和A.蒂瓦里 SAL 2. 在R. Alzheimer和D. Peled,编辑,计算机辅助验证国际会议(CAV 2004),LNCS第3114卷,第496-500页。Springer-Verlag,2004.[6] L. de Escherichia,S. Owre和N.史恩卡SAL语言手册。技术报告SRI- CSL-01-02(修订版2),SRI International,2003年。[7] J. Derrick和E.煮一下Z和Object-Z中的细化,基础和高级应用。Springer-Verlag,2001.[8] E.A. 爱默生时态和模态逻辑。在j.van Leeuwen,编辑,Handbook of Theoretical ComputerScience,卷B,第996-1072页Elsevier Science Publishers,1990.[9] C. Fischer和H.维海姆使用FDR对CSP-OZ规范进行模型检查。在K。荒木,A. Galloway,and K.田口,编辑,集成形式方法国际会议Springer-Verlag,1999.[10] S.GrafanddH. 萨 伊 德岛 与 PVS 一 起 使 用 的 数 据 段 的 传 输 。 在 计 算 机辅 助 验 证 国 际会 议(CAV'97),LNCS的第1254卷,第72-83页中Springer-Verlag,1997.[11] J. He.过程细化。在J.麦克德米德,编辑,理论和实践的细化。巴特沃斯,1989年。[12] M.约瑟夫一种基于状态的进程通信方法。分布式计算,3:9224G. 史密斯,J。Derrick/Electronic Notes in Theoretical Computer Science 137(2005)[13] G. Kassel和G.史密斯模型检查Object-Z类:使用FDR的一些实验。亚太软件工程会议(APSE
下载后可阅读完整内容,剩余1页未读,立即下载
![.pdf](https://img-home.csdnimg.cn/images/20210720083646.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![application/msword](https://img-home.csdnimg.cn/images/20210720083327.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://profile-avatar.csdnimg.cn/default.jpg!1)
cpongm
- 粉丝: 4
- 资源: 2万+
上传资源 快速赚钱
我的内容管理 收起
我的资源 快来上传第一个资源
我的收益
登录查看自己的收益我的积分 登录查看自己的积分
我的C币 登录后查看C币余额
我的收藏
我的下载
下载帮助
![](https://csdnimg.cn/release/wenkucmsfe/public/img/voice.245cc511.png)
会员权益专享
最新资源
- VMP技术解析:Handle块优化与壳模板初始化
- C++ Primer 第四版更新:现代编程风格与标准库
- 计算机系统基础实验:缓冲区溢出攻击(Lab3)
- 中国结算网上业务平台:证券登记操作详解与常见问题
- FPGA驱动的五子棋博弈系统:加速与创新娱乐体验
- 多旋翼飞行器定点位置控制器设计实验
- 基于流量预测与潮汐效应的动态载频优化策略
- SQL练习:查询分析与高级操作
- 海底数据中心散热优化:从MATLAB到动态模拟
- 移动应用作业:MyDiaryBook - Google Material Design 日记APP
- Linux提权技术详解:从内核漏洞到Sudo配置错误
- 93分钟快速入门 LaTeX:从入门到实践
- 5G测试新挑战与罗德与施瓦茨解决方案
- EAS系统性能优化与故障诊断指南
- Java并发编程:JUC核心概念解析与应用
- 数据结构实验报告:基于不同存储结构的线性表和树实现
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035111.png)
安全验证
文档复制为VIP权益,开通VIP直接复制
![](https://csdnimg.cn/release/wenkucmsfe/public/img/green-success.6a4acb44.png)