没有合适的资源?快使用搜索试试~ 我知道了~
理论计算机科学电子笔记118(2005)37-55www.elsevier.com/locate/entcs使用模板验证基于场景的规范Girish Keshav Palshikar1塔塔研究开发和设计中心(TRDDC),54 B,Hadapsar工业区,浦那411013,印度。摘要通过列出系统交互的场景来描述系统的动态行为已经成为一种流行的做法。消息序列图(MSC)是一个严格的和广泛使用的符号,用于指定系统行为的这种情况。高级MSC(HMSC)提供了层次化和模块化的组合工具,用于从基本MSC构建复杂的场景。虽然HMSC的属性的形式验证的一般问题是棘手的,我们提出了一个框架限制验证。我们提出了简单的模板常用类型的属性,并讨论有效的算法来验证它们。关键词:基于场景的规范,消息序列图,形式验证,形式方法。1介绍在构建实用的业务系统以及安全关键型实时嵌入式系统(例如,铁路系统[23]。以易于理解的非数学方式向最终用户传达系统的动态行为要求并不总是容易的,特别是在要求分析的早期阶段,其中要求需要是高层次和抽象的(从设计和实现问题中删除)。描述系统的一种简单直观的方法是列出其1电子邮件地址:girishp@pune.tcs.co.in2电子邮件地址:pbhaduri@pune.tcs.co.in1571-0661 © 2004 Elsevier B. V.根据CC BY-NC-ND许可证开放访问。doi:10.1016/j.entcs.2004.12.01738G.K. Palshikar,P.Bhaduri/Electronic Notes in Theoretical Computer Science 118(2005)37有意的行为。 在最高的抽象层次上,场景描述了系统与其环境和其他外部系统的一组交互。交互包括参与其中的实体(包括系统组件)和事件发生。交互场景通常代表一组可能的事件序列(情节)。每个交互场景通常被分类为理想的(晴天)或不理想的(雨天)。理想情况下,实现应该满足所有晴天交互场景,而不满足雨天交互场景。需要一种简单的、有表现力的、直观的、图形化的和标准化的符号来指定系统的交互场景。消息序列图(MSC)就是这样一种简单、直观且数学上严格的符号[25,13]。MSC已广泛用于电信领域,并且也越来越多地用于许多其他应用[23]。UML中的序列图和用例符号在语义上和视觉上接近MSC符号[12,11,20,8]。MSC的ITU标准[14]包括其数学语义。其他研究人员已经使用诸如转换系统、进程代数等的形式化为MSC提供了数学语义[16,19,18,9]。在本文中,我们使用了由Alfred等[2]给出的偏序语义。 符号的形式语义的主要用途是它可以用于设计形式验证和分析算法。例如,使用MSC编写的规范可以被分析以检测各种问题,例如缺少场景和竞争条件。可以设计形式验证算法,检查使用MSC编写的给定规范是否满足以适当的形式表示法编写的给定属性[2,1,24,17,4,21,22,5]。模型检查工具也被应用于MSC的正式验证[3,10]。本文提出了一组受限的简单属性模板和错误验证算法,以检查给定的高级MSC(HMSC)是否满足给定的属性。由于HMSC规范的形式验证的一般问题是棘手的,当属性在时间逻辑或等效符号中指定时,在[7,15,5]之后,我们限制了可以指定的属性的种类,并给出了使用每个模板指定的属性的我们提出了一个比较,其中我们牺牲了有效验证的表达能力。MSC符号已经以几种方式扩展(例如,[26]);这里我们只关注MSC和HMSC符号的核心方面。第2节概述了HMSC表示法及其形式语义。第3节讨论了我们的方法的属性模板和算法来验证它们。第4节提供结论和进一步的工作。G.K. Palshikar,P.Bhaduri/Electronic Notes in Theoretical Computer Science 118(2005)3739→→≤2HMSC语义我们假设熟悉基本的MSC表示法及其偏序(线性时间)语义[2](参见附录A的概述)。在这里,我们总结了MSC-图和HMSC的相关定义。2.1MSC图的线性时间语义MSC图本质上是一个有向(不一定是无环)图,其中每个顶点都引用一个基本MSC。定义2.1MSC图G是一个元组(V,→,vI,vT,μ),其中V是顶点的有限集合,是V上的二元关系(的每个元素是G中的有向边),vI是初始顶点,vT是终端顶点,μ是将每个顶点映射到基本MSCm的标记函数。当定义MSC图的语义时,有两种方式来解释基本MSCm1和m2的级联。在同步级联中,m1中的所有事件都先于m2中的任何事件.异步级联对应于逐个实例地级联两个MSC。定义2.2与具有相同实例集合的两个基本MSCm1和m2的同步连接相关联的偏序是位置(m1)和位置(m2)上的偏序≤m1,m2,由下式给出:≤m1≤m2位置(m1)×位置(m2)其中位置(m)是基本MSCm中的位置(事件)的集合,并且是用于两个集合的不相交并集的运算符。每个位置由一个元组其中i是实例的唯一ID,l是实例i的可视顺序中事件的ID(参见附录A)。定义2.3与具有相同实例集合的两个基本MSCm1和m2的异步连接相由以下关系的传递闭包给出的位置(m1)和位置(m2)上的偏序m1,m2:≤m1≤m2<${( m1, m2)|i<,l > m1(m1)m2<,l > m2 {m2}{m2}图1显示了一个MSC图(未显示初始顶点和终端顶点,初始顶点连接到v0,顶点v 2、v 3连接到终端顶点)。在这个MSC图中,从初始顶点到终端顶点有无限多条路径(由于其中的循环);例如,,,等。语义学中的概念40G.K. Palshikar,P.Bhaduri/Electronic Notes in Theoretical Computer Science 118(2005)37v0v2P1 P2 P3连接P1 P2 P3批准v1v3P1 P2 P3失败报告P1 P2 P3请求服务s_connect_p1s_approve_p2r_connect_p2r_approve_p1r_fail_p1r_fail1_p1s_connect_p1r_connect_p2s_fail_p2s_report_p2r_report_p3s_connect1_p1r_connect1_p2s_fail1_p2s_report1_p2s_fail_p2s_report_p2r_report_p3s_req_service_p1r_req_service_p3r_report1_p3s_req_service_p1r_req_service_p3Fig. 1. MSC图表图1还示出了MSC图中行走v 0,v1,v 0,v 1,v 3>的优先图;该图是通过同步连接v 0,v1,v0,v1和v3的基本MSC获得的。<虚线表示根据定义2.2添加的优先图中的边;我们省略了传递闭包所包含的边。请注意,位置(事件)在漫游中的v0(和v1)的不同实例中被重命名(由于不相交的并集)。定义2.4在(a)同步连接下的MSC图G的语义是通过以下方式获得的所有有限和无限游程的集合:(i)(a)沿着G中的每个行走同步连接每个基本MSC,以及(ii)在从(i)中的偏序由于MSC图中的行走集可能是无限的(如果它有循环),所以运行集也是无限的。判定给定MSC-图是否满足给定性质P(其中P被指定为自动机)的问题对于同步级联是coNP-完全的,而对于异步级联是不可判定r_fail_p1G.K. Palshikar,P.Bhaduri/Electronic Notes in Theoretical Computer Science 118(2005)3741∈ ∩ ∈∩concatenation [3].2.2HMSC的线性时间语义本质上,HMSC是一个分层(多级)图,其节点是基本MSC或另一个HMSC,因此允许图的嵌套定义2.5高级消息序列图(HMSC)H是一个元组(N,B,v I,v T,μ,E),其中N是节点的有限集合,B是盒子(或超级节点)的有限集合,v I N B是初始节点或盒子,v T N B是终端节点或盒子,μ是一个标记函数,将N中的每个节点映射到基本MSC,将B中的每个盒子映射到已经定义的HMSC,E是集合连接节点和盒子的边。我们省 略了MSC 标准中 的一些HMSC 功能, 如条件和 内联表达 式。HMSCH是什么意思? 首先,HMSC被分解为MSC-图,通过递归地用相应的HMSC替换盒来获得。 HMSC的含义则是这个可扩展MSC-图的所有可能的有限或无限运行的集合[3];这里要求HMSC的嵌套不是相互递归的,即, 如果HMSCH的节点用另一个HMSCH3HMSC验证给定一个HMSCH和一个关于H的游程的性质P,验证问题是判断H的所有游程是否满足P。P通常使用像LTL或CTL、自动机或模板MSC这样的时序逻辑来陈述。一个简单的验证算法将检查H的部分或全部运行,以决定H是否满足P。判定给定MSC-图是否满足给定性质P(其中P被指定为自动子)的一般问题是不可判定的[3]。然而,我们考虑下面的一些特殊类别的在[7,15,5]之后,我们假设属性属于各种预定义的模板,因此牺牲了易于使用和验证效率的通用性。这些属性是根据输入HMSC运行中事件的相对顺序来说明的。虽然属性模板不能表达实际上可能感兴趣的所有属性,但它们确实涵盖了广泛的典型属性类别。此外,我们提出了有效的图论算法(基于线性时间语义的HMSC),以验证使用这些模板所述的属性。42G.K. Palshikar,P.Bhaduri/Electronic Notes in Theoretical Computer Science 118(2005)37∧∧HMSC中的每个内部事件都有一个唯一的ID,该ID由其发生的基本MSC中的唯一位置指定。用户定义的事件E通常对应于HMSC中内部事件的非空有限集合γ(E)。属性是根据用户定义的事件及其否定来指定的。我们说用户定义的事件发生在任何与之对应的内部事件发生时。如果一个用户定义的事件E代表一个文件,夜间集合{e1,. ,e k}, 则否定事件not(E)代表不(e1)...不是(e k)。 在图1中,用户事件(下划线代表注意在本文中,我们所有的验证算法假设同步concation- nation在MSC图的语义这使得算法在本质上是模块化的异步级联的验证算法更复杂,因为它们涉及从输入MSC图构造全局可达性图3.1追踪跟踪属性在输入HMSCH的所有运行或至少一个运行中以指定顺序断言事件序列的发生。属性的模板如下所示。粗体的术语由用户给出,用斜线分隔的粗体术语是备选项,其中一个由用户选择每个ai都是用户定义的事件或其否定。事件的子序列X = [a1,a2,.,ak]发生在一些/所有HMSCH定义3.1设H是一个MSC-图,σ = u0,u1,u2,.. 是H的一个游程,其中每个ui是H中某个MSCM中的一个内部事件。正的用户定义的事件a ={e1,. ,e n}在σ中发生,如果存在某个事件e ∈ a,且在σ中有ui(i≥0)使得ui=e. 一个负的用户定义的事件不是(a),其中a是正的用户定义的事件a ={e1,.,e n}出现在σ中,如果a不出现在σ中,即,如果不存在e∈a且在σ中不存在ui(i≥0)使得ui=e.在运行中发生的用户定义事件的概念可以概括为序列X = [a1,a2,. ,a n]的(积极或消极)用户定义的事件通过归纳定义3.2。G.K. Palshikar,P.Bhaduri/Electronic Notes in Theoretical Computer Science 118(2005)3743·∪∪X=[“P 1 send s connec t to“,发生在HMSCH的某些运行中。定义3.2设H是MSC-图且σ = u0,u1,u2,. 是H的一个游程,其中每个ui是H中某个MSCM中的一个内部事件。 迹线X = [a1,a2,.如果x是σ的前缀,其中σ = x · y,则用户定义的(正或负)事件中的一个发生在σ中,使得1发生在x中,其余的跟踪[a2,.,n]发生在剩余的运行y中。 在这里,是连接对序列的操作假设X中的所有事件都是用户定义的正事件。则X发生在HMSC H的给定有限或无限游程σ中,如果存在一系列内部事件B = ,使得bi∈ai且B作为σ内的子序列出现.子序列B不需要在σ中是连续的,即,在σ中的bi和bi+1之间可能存在其它事件。现在假设X中的一个或多个ai则X发生在HMSC H的给定有限或无限行程σ中,如果存在一系列内部事件b1,.,bn(其中n = X中的正用户定义事件的数量),使得(i)每个bi都处于X中的正用户定义事件中(按照它们在X中发生的顺序),(ii)B是σ内的子序列,以及(iii)对于每对bi和bi+1在B中,使得bi∈ap且bi+1∈aq,没有来自任何负的ap和aq之间的用户定义事件发生在σ中的bi和bi+1之间。例如,下面的属性检查在图1的HMSC中是否有任何运行,其中P1发送连接消息,但P1在那之后没有接收到批准消息。检验跟踪性质的一个主要困难是H的游程可能是无限的。Vent的子序列X=[不(“P 1接收到来自)”]在HMSC H的某些运行中发生。序列X可以包括一些循环或重复,如下所示。为了简单起见,我们假设X不包括任何负用户-定义的事件。设H是一个HMSC,S是通过对H进行剖分而得到的MSC图中出现的基本MSC的集合。对于给定的内部事件e,令φ(e)表示来自S的基本MSC的集合,其中e发生(显然φ(e)/=S且φ(e)=S);例如, φ(到P1记得正的用户定义事件E代表有限集合γ(E)={e1,.,e p},内部事件。 然后函数φ可以扩展到用户定义的事件E为:φ(E)=e∈γ(E)φ(e)=φ(e1) ...φ(e p). 这里,φ(E)表示H中的基本MSC的集合,其包含至少一个对应于MSC的内部事件。44G.K. Palshikar,P.Bhaduri/Electronic Notes in Theoretical Computer Science 118(2005)37用户定义的事件E。我们需要更多的定义。定义3.3设H是基本MSC集合S上的MSC-图。则序列w = 是MSC图H中的基本MSC S的集合中的正内部事件的序列。 令w = 是H 的可行迹。则函数f在w中划分β,如果(i)f(M)= β,如果w由单个MSC M组成且M∈φ(β);(ii)如果w =·则f(Mi)= β的一个真前缀x(其中β = x·y),Mi∈φ(x)且f在。在图1中,w=是H的可行迹. 此外,函数f={v 1> →,v3> →}在w中划分β=。注意,f将β的非空子序列与w中的每个基本MSC相关联。可以设计一个简单的算法来构造一个函数f,它将给定的β在w中划分;这样的f对于给定的w,β是唯一的,因为β中的每个事件都是内部事件,属于S中唯一的基本MSC。算法1(history tracing a)检查使用跟踪模板声明的属性如下(我们假设选择了some选项)。我们系统地从X中选择内部事件的置换β,在H中形成通过函数f划分β的候选可行迹w,并有效地检查β是否出现在对应于w中基本MSC的同步级联的优先关系的某种线性化中。可行迹的长度至多为k,因此在数量上是有限对于上面的第二个属性,X = [a1,a2,a3],其中a1=“P 1发送连接到“,a 2 =“P 1接收来 自“, a 3 =“P 1发送连 接到“。φ(a1)= φ(a3)={v0},φ(a2)={v1}和γ(a1)= γ(a3)={sconnectp1},γ(a2)={r fail p1}。 只有一个可能的β = ,其中e1 =s connect p1,e 2 = rfail p1,e 3 = s connect p 1.因此w= 其中M1= v0,M2= v1,M3= v0是H的可行迹,函数f={M1<$→< sconnectp1>,M2<$→,M3<$→< sconnectp 1>}在w中划分β. β、w和f的这种选择显然满足了内部的循环;因此属性是满意的。显然,图1中的HMSC不能满足以下特性。G.K. Palshikar,P.Bhaduri/Electronic Notes in Theoretical Computer Science 118(2005)3745≤≤≤||--子序列X=[“P1send“P 1发送连接到“]发生在HMSC H的某些运行中。算法1中断跟踪a输入HMSC H;{实际上H是用于HMSC的被忽略的MSC图}输入X =[a1,.,a k]{正用户定义事件的有限序列}如果X出现在H的某个运行中,则输出true;否则为false设S=H中所有基本MSC的集合;令φ(ai)=用户定义事件ai的基本MSC的集合;令γ(ai)=用户定义事件ai中的内部事件的集合;对于每个序列β = 其中e i∈γ(a i)do对于每个可行迹w = ,1ak,的基本MSC,使得函数f在w之间划分β,returntrue;{对w中的每个MSC执行}for(x= 1;ok==truex≤a;x++)dofor(j=2;ok==truej f(Mx);j++)do对于(i= 1;i j;i++),{RM=MSCM的优先顺序}如果在(RMx,f(Mx)j,f(Mx)i)之前,则returnfalse;break;end if首尾相接端如果ok ==true,则返回(true);如果结束,则结束return(false);算法1的复杂度很容易看出是O(Ak·mk),其中A是对应于任何事件ai的内部事件的最大数量在X中(即, A=max γ(ai)),m是H中基本MSC的数量,k是X中事件的数量。为了降低复杂度,我们强制k=10的上限,这意味着可以使用多达10个用户定义的事件来声明跟踪属性,这在实践中是可以接受的。[5]中报道的早期工作提出了一种用于基本MSC的类似算法,46G.K. Palshikar,P.Bhaduri/Electronic Notes in Theoretical Computer Science 118(2005)37关于我们来自[“P 1 send s connec t to“]的事件和来自[“P 1receivees fail from“,“P 1 receive es app rove from“]的事件在HMSCH的所有X中的集合;例如,{{a,b},{a,c}}={a,b,c}。你的意思是其分析。该算法是有效的,并没有明确检查所有可能的有限线性化H。显然,即使X中存在重复,该方法也有效。该算法可以针对以下情况进行修改:(a)当X包含负的用户定义事件时;和/或(b)在模板中选择所有运行选项为了在实践中更好地使用,我们已经扩展了这种方法,以提供额外的选项,例如打包的连续性,跟踪的位置3.2后果另一种有用的属性是使用下面的模板指定的 这里X = x1,.,Xm,Y = y1,.,yn是给定的用户定义的事件或其否定的集合。来自X的每个/一个/所有事件导致来自Y的一个/所有在HMSCH的所有例如,在图1中,下面的属性声明,P1发送连接消息后,P1接收失败或在每次运行中批准消息。作为另一个示例,在图1中,以下属性声明每个P1发送连接消息或P1接收失败消息的发生之后是P1接收批准消息或P1在每次运行中发送请求服务Eacheventsfrom[“为了简单起见,我们再次假设X,Y不包括任何负用户定义的事件给定一组集合X,我们用X表示模板如下:• 属性模式:在HMSC H的所有运行中,来自X的事件导致来自Y的事件。意义:对于H的每个游程σ,如果存在某个内部事件x∈X,那么是否存在某个内部事件G.K. Palshikar,P.Bhaduri/Electronic Notes in Theoretical Computer Science 118(2005)3747∈·有限游程σ = e1,e2,. 的MSC图H,如果某个内部事件a∈ A发生在σ中(即, ei=a对于某个i≥1)则(i)存在某个事件b∈存在内部事件的某种有序排列Y1,序列x·Y1是σ的一个子序列(迹)?YsuchBy Y,使得序列x y(通过连接x和y)是σ?• 属性模式:在HMSC H的所有运行中,来自X的事件导致来自Y的所有事件。对H的每个游程σ,如果存在某个内部事件x∈X,则某个有序排列Y1的内部事件Y存在,使得序列x·Y1是子序列(跟踪)的σ?• 属性模式:在HMSC H的所有运行中,来自X的每个事件都会导致来自Y的 事 件 。 意 义 : 是 否 对 H 的 每 个 游 程 σ , 对 于 r∈a∈X , 如 果 x是tssomeintx∈a,则存在一些内部事件y一个子序列(跟踪)的σ?∈Y,使得序列x·y为• 属性模式:在HMSC H的所有运行中,来自X的每个事件都会导致来自Y的所有事件。意思是:对于H的每个游程σ和每个用户事件a∈X,如果存在某个内部事件x∈a,那么当选择第一个“所有事件”选项时,其含义定义相似我们通过一个算法来说明该方法,以验证上面列出的第二个结果属性模式。定义3.5设H是MSC-图。设A是H中的正用户定义事件,B是H中的正用户定义事件的集合。我们说A必须被B中的某个事件跟随,记为A<$B,如果对每个使得对于某些j > i∈j=b(即,a之后是b);以及(ii)AB在剩余的运行ei+1,ei+2,.中为真。,e j−1,e j+1,. 的σ。备注3.6• 如果在HMSCH的某个运行中没有来自A的事件发生,则A_B对于该运行是空• 如果两个内部事件e1和e2属于同一bMSC(即,φ(e1)=φ(e2)=M)则{e1}<${{e2}}i <$e1在M的优先顺序中先于e2。例如,在图1中,很容易看到{► {”P 2发送批准给P 1“,“P 2发送失败给P 1”}。命题3.7设H是一个MSC-图,A是一个正的用户定义事件,B是H上的一个非空的正用户事件集合。则A ≠ B当且仅当对于A中的每个内部事件e1,存在一个48G.K. Palshikar,P.Bhaduri/Electronic Notes in Theoretical Computer Science 118(2005)37|| ≤||||B中的内部事件e2,其中φ(e1)=M1,φ(e2)=M2,使得以下成立:• 如果M1 = M2 =某个bMSC M,则在与M相关联的偏序中e1在e2之前;或者• 如果M1/= M2,则(i)M1从H的起始顶点可达,并且(ii) M2可以从M1到达,并且(iii) H的端顶点可从M2到达,并且(iv) 从H的起始顶点到H的结束顶点的每一条经过M1的有向路径在M1之后也经过M2。下面的算法2实现命题3.7来检查给定顶点u是否总是被图G中的另一个顶点v跟随,关于G中的特定给定的开始和结束顶点。该算法本质上执行从u开始的图G的递归深度优先遍历,并在到达L中的任何顶点时回溯。布尔标记的访问过的全局数组标记已经访问过的顶点。算法2的复杂度显然与深度优先图遍历相同,即O(V+E)。用于结果属性的算法3(其中选择上面列出的第二结果属性模式)如下。如果集合Y中的每个用户定义事件最多包含N个内部事件,则算法显式检查N|Y|组合。我们通过对Y中(例如, Y10),在实际情况下是令人满意的。 最早的一批-- per [5]提出了用于基本MSC及其分析的类似算法。同样,该算法是有效的,并且没有显式地检查H的所有可能的有限线性化。当X或Y包含负的用户定义事件时,可以修改该算法除了跟踪和结果之外,我们还定义了其他模板来指定更多种类的属性,例如优先级。4结论和进一步工作在需求分析阶段,通过列出交互示例来指定系统行为的方法正在得到广泛的接受。因此,分析基于MIMO的系统规范以及早发现错误并对系统要求获得信心是非常重要的。消息序列图和高级消息序列图提供了一种严格而直观的形式主义,用于指定系统的此类场景G.K. Palshikar,P.Bhaduri/Electronic Notes in Theoretical Computer Science 118(2005)3749----| |----算法2必须遵循[V];最初,V中的每个顶点都是未访问的intk =(k,k);输入start,end,u∈V;{u/=start,u/=end}输入LV\{start,end,u};如果u在任意路径上总是被L中的至少一个顶点跟随,则输出true通过u从开始到结束;否则为false{假设:u从start可到达,end从u可到达}returntrue;将u标记为已访问对于每个与u相邻的顶点w,if(visited[w] ||w ==开始||w∈L)则继续end if如果(w== end),则return(false);u不总是后跟Lend ifreturntrue; 将w标记为已访问if(must后跟(G,start,end,w,L)==false)then return(false);如果结束,则结束return(true);TEM行为HMSC提供了层次化和模块化的组合工具,用于从基本场景构建复杂场景。其他符号,如UML用例和序列图,已经根据HMSC给出了形式化的语义。已经提出了几种技术来分析HMSC指定的场景:竞争条件检测,缺失场景检测和正式验证。虽然HMSC属性的形式验证的一般问题是棘手的,在本文中,我们提出了简单直观的模板,用于说明常见类型的属性和验证它们的算法。为了进一步的工作,我们需要添加更多的模板来扩展可以指定的属性类型。我们可以考虑使用受限的线性时态逻辑(或正则表达式)来陈述HMSC的属性。这种方法当然限制了陈述HM-SC属性的表达能力验证实时序列图[6]或具有时序特性的MSC [26]也是相当有趣的。50G.K. Palshikar,P.Bhaduri/Electronic Notes in Theoretical Computer Science 118(2005)37------算法3中断结果b输入HMSCH;实际上H是HMSC输入的有限个非空集合X,Y的正用户定义事件在H中输出为真,如果对于H的所有运行σ,X中存在n个内部事件x和一些内部事件的排列Y1,x·Y1作为子序列(跟踪);否则为falseY使得σ包含{γ(a)表示用户定义的事件a中的内部事件的集合}对于(i = 1; i≤|X|; i ++)do{检查X中的每个内部事件}对于每个内部事件x∈γ(X[i]),{在H的所有游程中,x后面是否都是Y的所有元素?}对于每个组合L = s.t. ei∈γ(Y[i])do if(φ(x)==φ(ei)for everyei∈L)then如果(x在ei,对于L中的每个ei),则return(true);end if其他if(must followed by(H,startH,endH,x,L))then return(true);x是一个结束如果结束如果端x的end后面不是Y的所有元素return(false);确认我们感谢BMF工具项目团队实施我们的想法并提供宝贵的反馈。我们感谢Mathai Joseph教授在整个工作期间的支持和鼓励。第一作者要感谢ManaseePalshikar博士。A基本MSC表示法的线性时间语义A.1基本的MSC符号我们在这里只介绍MSC表示法中的一些基本功能;我们省略了动作、内联表达式和门等功能。在MSC中,实体代表实例(或进程),事件通常代表进程发送和接收消息-还有其他类型的事件,如G.K. Palshikar,P.Bhaduri/Electronic Notes in Theoretical Computer Science 118(2005)3751蒸汽锅炉阀压力表控制器可用状态T1状态关闭状态高压T1CMD打图A.1. 基本MSC与定时器相关的那些相同实例和消息的含义取决于所描述的系统。实例不一定代表计算机程序;它指的是一些活跃的代理或实体。电文不一定代表实际的数据电文;它可以指某种信息交换。消息有一个名称,没有进一步的结构或细节(在最简单的情况下)。MSC不关心消息传输的实际机制或信道,除非假定消息总是按顺序传送而没有任何丢失或更正。此外,发送是非阻塞的,即,发送方不等待直到接收方接收到消息。图A.1所示的MSC描述了阀门、控制器和压力表3个实体之间的简单交互。实例的每条垂直线表示实例中发生的事件;最上面的事件是(实例中)最早的事件,依此类推。实例的事件的这种时间顺序称为它的局部顺序。局部秩序中事件之间的视觉距离是无关紧要的。在图A.1中,阀门和压力表过程分别使用名为状态关闭和状态高压的消息将其各自的状态发送到控制器然后,控制器使用名为cmd open的消息向阀门发出打开命令。注意,MSC仅描绘了一种场景;许多其他场景是可能的,例如,一种是阀门打开,压力低,控制器发出命令关闭阀门。MSC被封闭在一个矩形框架中,并有一个名称(本例中为SteamBoilerMSC符号允许人们通过使用称为共区域的构造来避免进程的事件子集的任何特定排序。 共区由沿着过程的垂直线的虚线段指示,并且该虚线内的事件是无序的。图A.1显示了52G.K. Palshikar,P.Bhaduri/Electronic Notes in Theoretical Computer Science 118(2005)37控制器的共同区域,其中控制器不对来自阀的状态关闭消息和来自压力计的状态高压消息的接收施加任何顺序(这些消息可以以任何顺序接收许多场景将消息流与时间约束关联起来。可以使用三个特殊事件在MSC符号中轻松指定此类场景计时器设置事件由连接到单个进程的时间轴的沙漏符号表示。计时器重置事件由连接到进程的时间轴的十字表示。超时事件通过用一条折线将计时器的沙漏符号连接到流程时间轴来表示。每个计时器都有一个唯一的名称。当然,对于每个计时器,计时器重置和超时事件必须在计时器设置事件之前。在图A.1中,控制器在等待来自阀门和压力表实例的消息之前启动计时器t在这个特定的场景中,控制器在超时之前接收到这两个消息,然后重置定时器t1。条件是MSC表示法中的一种非正式描述机制,用于显示单个实例或一组实例必须达到的状态或情况。条件以文本标签的形式写在一个六边形框中,该六边形框放置在单个实例上或一组实例中。如果条件C被放置在单个实例P上,则P的执行不会继续到下一个事件(在局部顺序上的条件之下),也就是说,条件C是实例中下一个事件的先决条件。如果条件C被放置在一组实例P1,.,Pk,则所有k个实例都必须达到满足条件C的局部状态;只有在达到该状态之后,k个实例中的任何一个才能在它们各自的局部顺序中进一步前进。在这种情况下,条件C可以被认为是用于确保实例P1,.,Pk在进一步进行之前达到相同的状态。在图A.1中,实例阀门和压力表共享一个称为状态可用的条件;只有当这两个实例都达到满足该条件的状态时,它们才能继续执行其本地命令。图A.1中的基本MSC具体说明了什么情况?看起来MSC只代表一个事件序列;实际上它代表几个实际的事件序列,每个事件序列都捕获预期的为了清楚地理解这一点,我们正式定义了基本MSC的线性时间语义。A.2基本MSC的线性时间语义到目前为止讨论的MSC符号被称为基本MSC,以将其与稍后定义的HMSC区分开来。我们现在正式定义线性时间语义,G.K. Palshikar,P.Bhaduri/Electronic Notes in Theoretical Computer Science 118(2005)3753一个基本的MSC在相关的偏序和运行的集合[2,6,5]。对于给定基本MSC m中的每个实例i,我们将有序序列0. lmax(m,i)是从实例顶部到底部编号的有限个离散位置。 基本MSCm中的实例i上的每个位置(表示为m)与事件相关联,该事件可以是消息的发送或接收、条件或定时器事件设置、重置、超时。当基本MSC从上下文中清除时,我们删除下标m。基本MSCm的语义根据部分阶≤m由m在其位置的集合上诱导。 偏序由以下优先关系Rm获得:• 沿着实例线的视觉顺序: Rm i,l+ 1>,除非两个连续位置在共区域• 消息的发送先于其接收:如果i,l>是发送事件,<是消息的对应接收事件,则 Rm iJ,lJ>•共享条件引起同步屏障:如果位置和指相同的条件c,则 Rm iJ,lJ+1>• 共区域内的事件在它们之间没有顺序:假设,,.,是共区域中的事件。如果l >0(即, 在共区域之前存在至少一个事件),则 Rm i,l>, Rm i,l + 1>,., Rm i,l +k >. 还有,如果k_lmax(i,m)(即,在共区域之后存在至少一个事件),则 Rm i,l+k+ 1>, Rm i,l +k+ 1>,... , Rm i,l+k+1>.我们假设基本MSCm是良构的,使得关系Rm是非循环的。我们称Rm为基本MSCm的优先关系。偏序≤m是Rm的自反传递闭包.定义A.1基本MSCm的语义是所有游程的集合(即,线性化)的偏序≤m。这意味着我们有并发的交织语义:任何两个事件在偏序中不可比,可以以任何顺序发生。还要注意,基本MSC的每次运行是有限的事件序列,并且每个基本MSC只有有限数量的这种有限运行。图A.2中的优先关系图描述了图A.1的基本MSC中位置(事件)之间的优先关系Rm。这个优先图的顶点代表事件;如果u直接在v之前,则存在从事件u到事件v的有向边,即,我的心一个事件v只有在所有前面的事件都发生之后才能发生如果MSC是格式良好的,则对应的优先级图54G.K. Palshikar,P.Bhaduri/Electronic Notes in Theoretical Computer Science 118(2005)37e6e5e1 =阀门向控制器e2 =控制器从阀门接收status_closee3 =压力计将status_high_pressure发送到控制器e4 =控制器从压力计接收status_high_pressure e5 =控制器向阀门发送cmd_opene8 e6 =阀从控制器接收CMD_open e7 =设置定时器t1e8 =复位定时器t1c1 =条件correct_status_availablee4e2e1 e7 e3C1图A.2. 图A.1中基本MSC的优先级图有向无环图(DAG)。引用[1] 巴尔河,K. Etessami和M. Yannakakis,MSC图的可实现性和验证,在:Proc. 28th Int. Co
下载后可阅读完整内容,剩余1页未读,立即下载
![.pdf](https://img-home.csdnimg.cn/images/20210720083646.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.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)
会员权益专享
最新资源
- 京瓷TASKalfa系列维修手册:安全与操作指南
- 小波变换在视频压缩中的应用
- Microsoft OfficeXP详解:WordXP、ExcelXP和PowerPointXP
- 雀巢在线媒介投放策划:门户网站与广告效果分析
- 用友NC-V56供应链功能升级详解(84页)
- 计算机病毒与防御策略探索
- 企业网NAT技术实践:2022年部署互联网出口策略
- 软件测试面试必备:概念、原则与常见问题解析
- 2022年Windows IIS服务器内外网配置详解与Serv-U FTP服务器安装
- 中国联通:企业级ICT转型与创新实践
- C#图形图像编程深入解析:GDI+与多媒体应用
- Xilinx AXI Interconnect v2.1用户指南
- DIY编程电缆全攻略:接口类型与自制指南
- 电脑维护与硬盘数据恢复指南
- 计算机网络技术专业剖析:人才培养与改革
- 量化多因子指数增强策略:微观视角的实证分析
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
![](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)