没有合适的资源?快使用搜索试试~ 我知道了~
131理论计算机科学电子笔记76(2002)网址:http://www.elsevier.nl/locate/entcs/volume76.html14页模型检测Mar′sadadelMarGallard oa,1,2Pedr oMerin oa,3Ernesto Pimentela,4aDpto。de Lenguajes y Ciencias de laComputacion马拉加29071马拉加,西班牙摘要在实现抽象模型检查时,用于抽象时态属性的经典方法是基于定义一个抽象满足关系,该抽象满足关系低于标准满足关系。因此,从抽象模型到具体模型,普遍属性的满足性被直接保持。然而,这个结果可能是不切实际的,因为抽象模型通常是不精确和不完整的。因此,如果一个支持抽象模型检验的模型检验工具给出了否定的答案,用户必须分析产生的反例,以确定属性是否真的失败,或者相反,抽象模型太不精确,无法获得确定的结果。我们已经开发了一种替代方法抽象的时间属性的思想的基础上过近似。 在本文中,我们比较了这两种方法关于泛/存在性质的可满足性/反驳,证明它们产生互补的结果。最后,我们研究了确保基于过近似的方法在分析泛性质时也产生1介绍模型检测[1]代表了近20年来在形式化方法研究中最有用的成果之一,以提高软件和其他相关系统的质量。模型检查器使用的是1本研究得到了CICYT项目TIC 2001 -2705-C 03 -02和TIC 99 -1083-C 02 -01的部分支持。2电子邮件地址:gallardo@lcc.uma.es3电子邮件地址:pedro@lcc.uma.es4电子邮件地址:ernesto@lcc.uma.es2002年由ElsevierScienceB. V. 操作访问根据C CB Y-NC-N D许可证进行。GALLARDO,MERINO,PIMENTEL132|∀∃|e一个系统,一个模型,它可以自动检查系统的可达状态,以检查给定的属性是否满足。通常,这些属性用时态逻辑的一些变体来表达,其中线性时间时态逻辑(LTL)是最常用的逻辑之一[12]。在模型检测的背景下,抽象解释[2]被用作处理所谓的状态爆炸问题的一种方法,该问题在分析实际系统时发生。抽象模型检验涉及两个活动。一方面,为了缩小原模型M的状态空间,我们应用抽象解释构造了一个逼近M的抽象模型Mα。另一方面,我们抽象了原始的满足关系,=,它针对具体模型评估时间属性,并定义一个抽象关系=α,以针对抽象模型重新解释属性的含义。给定一个一般的时间性质f,抽象过程的最终目标是M α|= αfM|= f(U1)M α|= αfM|= f(U2)M α|= αf M |= f(E 1)M α|= αf M |= f(E 2)然而,只有当M和Mα是双相似的[10]时,才可能强保持普适和存在性质,这在目标是减少状态空间时需要相当大的约束。因此,它是公认的,一个合理的抽象模型的建设可能会涉及一些信息的损失时,分析时间属性。抽象=欠近似的经典方法[3,5这个定义直接产生了普适性质的弱保持性(U1)。然而,由于抽象模型的不完整性/不精确性,剩余的保存结果可能会失败。解决这个问题的方法是分析由分析产生的反例,以确定它们是否是[11]或者像[5]那样对实验模型进行属性驱动/域驱动的细化。在[5]中,作者还提出了一个分析存在性(E1和E2)的建议,它是基于构造一个不同的抽象模型Mα,在M α上它们被直接保持。我们采用[8]中开发的过度近似方法来定义过度近似属性的抽象满足关系。在这种情况下,抽象模型比具体模型满足更多的性质,并且现在直接保留了对存在性质(E2)的反驳。然而,与经典方法一样,我们需要进行额外的分析,以便|GALLARDO,MERINO,PIMENTEL133a0级的1a0级0∈I −≤≤→≤≤−→Ia0级的1J实现剩余的保存效果。本文对这两种互补方法进行了比较。我们还研究了不精确性和不完全性如何影响保性结果,并说明了保证过逼近方法也可用于分析泛性质(U1)的可满足性的条件。最后,我们认为,一个混合的方法集成的经典和过近似的方法可能是有用的,以改善一组属性进行分析,而不修改抽象模型。然而,这种混合方法的描述超出了本文的目的,这是专门比较两种方法。本文的结构如下。第二部分是抽象模型的构建。在第三节中,我们介绍了抽象时序逻辑的经典方法和过近似方法.我们用一个例子来说明这两种方法,以展示应用每一种方法的自然方式。第四节讨论了不完全性和不精确性问题,最后在第五节给出了结论。2抽象并发系统并发程序的执行可以通过带标记的事务系统(LTS)来定义,如M=(A,N,−−→,s0),其中A是可重写的原子计算的集合,N是事务和数据的集合,−− →N×A×N是一一个标记的转换关系,s0是初始状态。 我们写s−→sJ,a0级的1(s,a,sJ)∈−−→。 Atracex=t0−→t1−→. . . Misaseqenceoftatates和它表示从状态t 0开始的(可能是无限的)计算,其中a0a1. 是执行一个缓存的等式。Givenatracex=t0−→t1−→ ... 、一个j我们用x表示su ∈ x路径tj−→一tj+1aj+1−→ ... .一个完整的跟踪x=t0−→0.... . . 你 好 。 . 这是一个在未来无法实现的趋势。我们是一家人终止的痕迹有一个永远重复的最终状态。 集合O(M)={x|x = s 0−→. 是一个完整的跟踪}定义了由转换系统M确定的跟踪语义。利用三元组α=(A,α,α),β)构造了一个线性代数系统M =(A,α,−→α,sα)的一个线性代数。(α,α)是一个抽象状态格,其中偏序α表示每个抽象状态的精确度,最小的e,是最精确的。函数β:β(s)α是将每个状态s与其[5]在后面,我们总是假设M α是M的α抽象解释。Givenatracex=t0−→t1−→···,我们用β(x)表示抽象[5]我们没有用α来表示这个函数,因为这个名字通常指的是(2<$,<$)和(<$α,≤α)之间的伽罗瓦联络的下伴随α:2<$→ <$α。不管怎样,α({s})= β(s).GALLARDO,MERINO,PIMENTEL13401I−I−⟨ ⟩ ∈联系我们0一0α101我我1212α0div(n)l0,吃,n偶数l0,思考,n多重,多重eat,l1,n奇数(n)think,l1,ntr aceβ(t)−a→0β(t)−a→1 ·· ·。没有一个p是唯一的,β(x)不是一个元素,αa0级O(M α). Inaddition,givenxα=tα−a→0tα−a→1·· ·andyα=rα−→rα−→1α·· ·,当n ∈ i ≥ 0时,我们可以得到xα≤αyα。tα≤αrα。D efin it ion2. 1我们知道M α是Iα−crectwrtM,i∈x∈O(M)存在x α∈ O(Mα)使得β(x)≤α x α.在抽象解释中,α正确性意味着抽象转换系统过度逼近原始转换系统,这可能会在分析抽象模型上的时态属性时引入不精确性此外,抽象转换系统的构造还可能产生所谓的这些迹线是不期望的,因为它们可能导致在分析时间属性时获得错误的答案。α完备性的概念D efin it ion2. 2我们知道M αisIα−cmpletwrtMi∈xα∈O(M α)存在x∈ O(M)使得β(x)≤α x α.例2.3这个例子摘自[5],它是经典方法的关键参考文献之一。考虑一个由两个过程(用餐的数学家)组成的系统,这两个过程使用一个并行版本的Col- latz程序来互斥地访问他们可能到达的临界区。条件是LTSM=(λ,A,−−→,s0),其中sys是-tem表示n是{think,eat}2×N,N是自然数的集合。一个元件l0,l1,nn表示每个数学家的状态,思考或进食,以及变量n的当前值。动作集是A=odd(n),even(n),mult(n),div(n),初始状态s0是think,think,100,转换关系定义如下:也就是说,n的奇偶性决定了哪个数学家可以吃。6C〇nsidertheabstractLTSM α=(α,A,−−→α,sα),其中erα={think,eat}2×{,e,o,T}。集合{e,e,o,T}是偏序≤ α的格,定义为:s α≤αs α惠s α=e或s α= T。初始状态是sα=think,think,e并且最佳应力应变曲线由以下公式表示:[6]我们可以考虑更多的初始状态(可以添加额外的转换规则),使这个模型复杂化。然而,这个具体的模型足以说明本文的主要结果。ααGALLARDO,MERINO,PIMENTEL135不I≤I→ ⟨ ⟩ ⟨ ⟩ ⟨⟩10050/Opα0αdiv(n)l0,吃,T多重,多重eat,l1, T偶数l0,思考,T偶数l0,思考,ediv(n)l0,吃,e多重,多重eat,l1,o奇数(n)think,l1, T奇数(n)think,l1,o请注意,操作div(n)(n:=n/2)生成n的不精确值。此外,一旦执行了此操作,就不可能为n生成更精确的值。定义β:α=β(l0,l1,n)=l0,l1,e i αn是偶数且β(l0,l1,n)=l0,l1,o,否则,考虑α=(α,(α,α),β)。则Mα对于M是α-正确的。时间复杂度O(M)x=think,think,100偶数− →思考,吃,div(n)−→想想,想想,50分钟偶数−→思考,吃,奇数(n)div(n)−→思考,思考,25分钟→吃,思考,25分钟......它被抽象为xα∈ O(Mα)(即β(x)≤αxα),其中xα=think,think,e偶数−→α偶数吃,吃,吃,div(n)−→αdiv(n)想想,想想,T−→α思考,吃,T奇数(n)−→αthink,think,T迹xα是不精确的,因为从第三个状态开始,变量n的奇偶性已经丢失,即β(x)=xα。 (Mα)也包含一些“虚假”痕迹 像想想,想想,偶数−→α思考,吃,e奇数(n)div(n)−→α多重,多重想想,想想,T−→α吃,想,T偶数−→αthink,think,TNowconsiderM α=(nα,A,−−→p,sα),其中n−−→p是一个实数是:)div(npl0,吃,e偶pl0,思考,e)div(npl0,吃,e多重,多重eat,l1,o奇数pthink,l1,oGALLARDO,MERINO,PIMENTEL136pI−¬¬ⓍP∈ P<${<$∈}FKPa0级pp111注意,在这个例子中,操作div(n)的不精确性是通过在两个粗体规则之间进行非确定性选择来解决的。因此,O(M α)比O(M α)包含 更 多 的 抽 象 迹 , 但 O ( M α ) 中 的 抽 象 迹 却 更 简 单 .M αisalsoIα−crectwrtM,而逼近x∈ O(M)的抽象迹是αeven(n)pdiv(n)px1=think,think,e−→αthink,eat,e−→αeven(n)pdiv(n)p想想,想想,−→p奇数(n)想,吃,吃,−→αthink,think,o注意β(x)=xα。 此外,Mα还包含“伪”迹。 在1个p相反,一个过渡系统Mα使得O(Mα)={xα,xα}将是α完备wrt M.然而,请注意,对于这个例子,定义一个生成完整模型的抽象转换系统3抽象时态逻辑Kripke结构用于评估模型的时态公式。在本节中,我们总结了提取Kripke结构的经典方法,并讨论了从该定义中可能推导出的主要保存结果。为了方便地将经典方法和我们的命题结合起来,我们考虑了弱Kripke结构,其中否定不是作为连接词处理的,而是作为构造原子命题的一种方式3.1时态逻辑给定Prop一组命题,我们构造集合=Prop Prop,其中Prop=p:p道具 让可以是使用的元素、标准布尔运算符、except和时态运算符:nextALTSM=(A,n,−−→,s0)m可以用来构造一个kKripk结构K= nM,τn其中τ:n → 2 P是一个函数,它为P在每个状态下的命题赋予真值。K=<$M ,τ<$ 是 一 个 Kripke 结 构 i <$s∈<$p, <$p∈Prop. 例 如 , p∈τ(s)p∈τ(s))和不矛盾原理(PNC)(i.例如,p/∈τ(s)p/∈τ(s))成立。注意,它定义了对动作的解释和对原子命题的解释。在下文中,p表示非否定和否定的原子命题。定义3.1设K = τM,τ M是一个弱Kripke/Kripke结构。给予迹x = t0− →. ,以及性质p ∈ P和f,g ∈ F,我们定义了关系GALLARDO,MERINO,PIMENTEL137τ0||||−→我 −−→CCCα α7Cα αKCCCCCCCC|= inductively asfollows:X|= τpi<$p∈τ(t0).X| = τfgi x| = τf或x| = τg。X| =τfgi x| = τf和x |= τg。X| = τf→gi x| = τf蕴含x| = τg。X|=τfi x1|= τf。X|= τfik≥ 0.x k|= τf。X|= τfik≥ 0.x k|= τf。X|= τfUgik≥0。(x k)|= τgandj10),因为抽象从一开始就丢失了关于n > 10的所有信息。这也适用于过近似方法。然而,命题4.5指出,当条件SC成立时,此方法可能会使用一些似乎与抽象不一致的属性。例如,考虑公式(n=2)。显然,经典方法不能分析它,而对偶方法的情况则不同。 注意n=2/∈τ α(s α)s α,n=0even(n)/∈τ α(sα). 因此,检查M α|= α(n=2)等价于证明M α|= αeven(n)。前面的命题允许我们定义公式f的抽象扩张的概念。α定义4.6[公式的抽象扩展]给定f∈F,我们定义f,这是一个最好的测试扩展f,as {f J|f J<$αf}。例如,n = 2α ={n = a|even(a)}= even(n). 然而,一般来说不能保证公式F可以被构造。 我们只使用运算符α表示给定公式的具体化集合它表示由于抽象解释而可能损失fαff这很容易证明。一般来说,相反的情况是不正确的,αf和f不重合;这意味着Iα修改了f的含义,无法恢复的记忆下一个定义捕获了由于存在 抽象模型中不精确的抽象痕迹定义4.7我们说公式f∈F不会失去精度,O(M α)i x α∈ O(M α),如果x α|= αf则x α|= α<$f。命题4.8假设K是一个Kripke结构8,并且公式f∈ F对于O(Mα)不失精度,则M α|=αfM|=Δfα证据 假设f =p。 给定x(M),由α正确性,存在x α(M α)使得β(x)αxα。很容易证明β(x)= αp意味着x α= αp。但根据定义4.7,这是不可能的,因此β(x)= αp。由于是一个Kripke结构,这意味着β(x)=p。最后,根据命题4.5,我们有x=p α。其余的情况都是在公式结构上进行归纳证明的。✷前一命题指出,当待分析的公式f相对于抽象模型没有失去精度时,可以使用过近似方法来将该universalformulaf。我们可以让您的信息更加准确[8]这个条件可能会被削弱,但我们在这里使用它来简化证明。GALLARDO,MERINO,PIMENTEL143C∨pppC如果给定的公式在给定的抽象模型中失去精度,虽然这一结果的发展超出了本文的范围,但该方法是基于在模型检查过程中检查变量所取的抽象值。最后,假设待检验的公式f没有丢失信息α由于抽象的解释,即f=f,抽象模型在分析普适公式的满足性时,经典方法和过逼近方法是一致的,即,|=αf惠M α|=αf。例4.9在前面的例子中,考虑公式f=k(l0=thinkl1=think)。 在一个bstractiondoes不是modifyf的条件下,我们有f对模型M α不损失精度,并且fα= f.在这些条件下,提供Mα|=α(l0=thinkl1=think)是保证M α的等式|=α(l0=thinkl1=think)。5讨论和结论从我们使用时态逻辑验证并发系统的经验中,我们注意到许多性质自然地表示为通用公式,但其他性质更容易被反驳。这一观察结果与许多模型检查工具(如SPIN [9])中实现的功能一致。这使我们认为,在实现抽象模型检测时,抽象属性的理想方法应该是将经典方法和我们的过近似方法结合起来。经典的方法可以通过证明一些关键属性的满足来增加软件质量的置信度,并且我们的方法可以用来丢弃非常关键的错误。在分析泛性质时,我们可以认为经典方法和过近似方法分别产生最精确和最不精确的抽象满足关系。在这方面,我们开发了一种方法,当这两种方法不能提供明确的答案时,该方法允许用户获得中间精度的结果,从而避免构建新的抽象模型。 我们目前正在扩展我们的工具α自旋[6,7]http://www.lcc.uma.es/~gisum/fmse/tools将此capa-能力致谢我们感谢审稿人为改进本文提出的宝贵意见。引用[1] E. Clarke,O.Grumberg,D.Peled,Model Checking,MIT Press,2000.1[2] 库索河抽象解释:通过构造或近似固定点进行程序静态分析的统一格模型,GALLARDO,MERINO,PIMENTEL144Conf. Record of the 4th ACM Principles of Programming Languages conference,1977,pp. 238-252. 1[3] E.M. Clarke,O. Grumberg,D.E. Long,Model Checking and Abstraction,ACM Transactions on Programming Languages and Systems(TOPLAS),16(5)(1994)1512-1245. 1[4] E.M. Clarke,O.Grumberg,S.Jha,Y.Lu和H.维斯反例引导的抽象细化。2000年第12届计算机辅助验证国际会议论文集,pp。154-169. 1[5] D. 达 姆 斯 河 Gerth , O. Grumberg , Abstract Interpretation of ReactiveSystems , ACM Transactions on Programming Languages and Systems(TOPLAS),19(2)(1997)2531、2.3[6] M.M. Gallardo , P. Merino , A Framework for Automatic Construction ofAbstract PROMELA Models,Theoretical and Practical Aspects of SPIN ModelChecking,LNCS-1680,1999,pp. 184-199. 5[7] M.M. Gallardo,J.Martinez,P.Merino,E.Rosales,使用XML实现模型检查的抽象。ACM Symposium on Applied Computing2002,pp. 1021-1025. 5[8] M.M. Gallardo,P. Merino,E. Pimentel,2002年第六届集成设计过程技术世界会议论文集,并行系统的抽象LTL属性。1、4[9] 陈文辉,软件工程与应用,硕士论文,2000。5[10] C. 卢 瓦 索 Graf , J. Sifakis , A. Boujjani , S. Bensalem , PropertyPreserving Abstractions for the Verification of Concurrent Systems。系统设计中的形式化方法6(1995)1-35。1[11] C.S. Pasareanu , M.B.Dwyer 和 W.Visser , Finding Feasible Counter-examples when Model Checking Java Programs,InProc. of the 7th Tools andAlgorithms for the Construction and Analysis of Systems LNCS-2031,2001,pp.284-298. 1[12] Z. 甘露A.Pnueli,反应和并发系统的时序逻辑- Specification,Springer-Verlag,New York,1992. 1
下载后可阅读完整内容,剩余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直接复制
信息提交成功