没有合适的资源?快使用搜索试试~ 我知道了~
标签系统:历史相关属性框架
理论计算机科学电子笔记137(2005)151-174www.elsevier.com/locate/entcs标签系统:一个规范历史相关属性的框架费尔南多·罗萨-韦拉多·克拉拉·塞古拉戴维·德弗鲁托斯-埃斯克里格DepartamentodeSistemasInform'ticosyProgramacio'nUniversidad Complutense de Madrid,Spaine-mail:{fernandorosa,c se gu ra,de fru toos}@si p. 嗯。es摘要我们提出了一个通用的方法来处理历史相关的运行时错误。当人们必须控制这类错误时,通常会定义一种标记版本的语言,其中标记只捕获过程历史的必要信息我们将把这种标记语言描述为由原始语言的计算定义的可达性树的继承者。从这个事实我们可以得出结论,每个标记语言所表征的属性确实是原始语言的属性通过这种方式,我们可以在一个通用的框架中工作,而不是为每个属性定义一个特定的语义。特别是,我们仍然可以使用微积分中存在的分析机制来证明这个或其他相关的性质。我们已经将这种方法应用于分布式π演算(称为Dπ)中的资源访问控制的研究。特别地,我们已经证明了Dπ的标记版本确实是根据我们的定义的标记关键词:安全属性,增强的语义,静态分析。1介绍在文献[7,8,3,4,1]中可以找到定义证券属性的几个框架。为了指定一个属性,有时它是足够的,以检测一些错误的状态的分析系统。这些错误状态中的一些可以被静态地识别,而不管*工作得到西班牙TIC 2003-01000项目的部分支助。1571-0661 © 2005 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi:10.1016/j.entcs.2005.01.043152F. Rosa-Velardo等人理论计算机科学电子笔记137(2005)151已达到易出错状态。这种安全属性的一个例子是保密性,其中错误状态是那些正在展示秘密数据的状态。1另一方面,某些安全属性不能被证明为持有只是对现状的考察。这是历史相关属性的情况。这种情况发生的一个例子是为了访问资源,进程需要事先获得使用它的许可[7]。在前一种情况下,需要确保不会发生错误例如,通过适当的类型系统,以使它们不可被键入的方式来标识这些错误状态。然后,如果原始系统是可类型化的,并且我们对类型化语义进行了主题归约,那么我们可以保证不会发生任何错误然而,在后一种情况下,这是不可能的,因为错误不是单个状态的属性,而是整个计算的属性。执行必要的跟踪分析的最自然的方式是通过某种方式记住计算所需的信息,用于描述所考虑的错误类型,并使用此信息标记过程。在以前关于这个问题的论文中,如[7]或[10],相应的丰富语义是以一种特别的方式定义的,没有以显式的方式将它与原始语义联系起来,从而对原始语义和丰富语义之间的对应关系进行了必要的具体的不可重用的证明在本文中,我们提出了一个系统的方法来处理这些错误,首先定义一个标记的语言和标记过程的一元关系。我们将把这种标记语言描述为由原始语言的计算定义的可达性树的继承者。从这一事实我们可以得出结论,每一个被标记的语言都是原始语言的一个属性。通过这种方式,我们可以在一个通用的框架中工作,而不是为每个属性定义一个特定的语义。特别地,我们可以再次使用基于类型的分析来保证在计算过程中不会到达错误的标记状态。此外,我们还证明了商系统的集合是一个完备格,并通过定义同一系统的不同本文的其余部分组织如下:在第2节中,我们定义标记迁移系统;在第3节中,我们定义商迁移系统[1]显然,通过这样一个简单的性质,我们不能涵盖信息的隐式流。F. Rosa-Velardo等人理论计算机科学电子笔记137(2005)151153Ff,f,.1 2L,一证明它们本质上是带标签的跃迁系统。第4节展示了导出标记语言的简单方法;在第5节中,我们给出了使用这种方法的一个例子:我们证明了标记Dπ[7,6]是一个标记,根据我们的定义,因此是一个商。第6节通过定义同一系统的不同标记的组合来利用商系统格的代数结构。最后,第7节给出了我们的结论,并提出了一些未来的工作。2Tagged过渡系统在本节中,我们将正式定义什么是标记语言。我们首先定义由给定的多排序签名生成的标记语法[2,5],关于签名的符号和所考虑的标签集。定义2.1给定一个多排序的签名(S,N),设E是N的S-排序的项代数,f是N的符号,L是一组标签(Γ,N,. ∈L)。我们将E的tax称为l(f,L)-taggeds,并且我们将由E′L(或有时)表示e i tju stbyE<$),到S-排序项的代数式<$L=(<$−{f})<${f|Γ∈L},fΓ其中arity(fΓ)=arity(f),对于每个Γ∈L。就抽象语法树而言,标记项是通常的项,其中一些节点,在区别符号f是常数运算符的情况下为叶子,或者在其他情况下为内部节点,用L中的标签注释。 更一般ver sionofftagg edsyntax,E<$L1,L2,. . ,将考虑收集这些样本f1,f2,. 在《古兰经》中,每个人都有自己的一套不同的标签。例2.2让我们考虑签名(S,),其中S={N at},={Zero,Succ,+,×},arity(Zero)=N at,arity(Succ)=N at→N at,arity(+)=arity(×)=N at→N at→N at。让我们也考虑一下设L={Q,Q}。S-排序的有限元素代数的算术表达式。一种可能的标记语法是由+,× ={Zero,Succ,}生成的语法,它定义了普通表达式,其中操作符号被“环绕”或“框架”符号取代。图1显示了表达式1+(0×1)和1(0 1)的抽象语法树。我们将使用普通的标记跃迁系统。定义2.3一个标号变迁系统S是一个元组S=(E,V,→,e0),其中E是状态集,V是变迁标号集,e0∈E是初始状态,→E×V×E是变迁关系。如果(e1,a,e2)∈→我们将写为e1→e2。154F. Rosa-Velardo等人理论计算机科学电子笔记137(2005)151→n112534++Succ×Succ×零零Succ零零Succ零零图1.1+(0× 1)和1<$(0< $1)的抽象语法树图2.实施例2.6的过渡系统我们将写e eJ,如果存在一个1,. ,an∈ V且e1,... ,en∈ E sucha1a2an那ee→. →e=eJ。 我们称后者为计算序列,C是计算序列的集合,Reach(S)={e ∈ E |e0e}可达状态的集合。定义2.4设S=(E,V,→,e0)和T=(F,V,<$→,f0)是两个标号迁移系统。我们将说S和T是同构的,并且我们将写S<$T,如果存在映射h:Reach(S)→Reach(T)使得:(i) h是Reach(S)和Reach(T)之间的双射。(ii) h(e0)=f0(iii) e→aeJ惠h(e)→ah(eJ)对于所有e∈Reach(S)我们将说这样的h是标号转移系统的同构。接下来,我们将定义何时标记语法上的转换系统是原始转换系统的标记。我们将O(e)表示从标记项e中移除所有标记后得到的项,通过结构归纳法定义为:O(h(e1,.,en)= h(O(e1),.,O(en))如果f/= hO(fr(e1,. ,en)= f(O(e1),. ,O(en))F. Rosa-Velardo等人理论计算机科学电子笔记137(2005)151155一111252525343434图3.示例2.6的标记系统定义2.5设E是E的S-排序项代数和E的E<$a(f,L)-标记的Sytax。 S=(E,V,→,e0)和T=(E<$,V,→,e<$0)是两个具有hO(e<$0)=e0的过渡系统。如果以下条件成立,则我们将假设T是S的标记(i) Ife<$→ e<$JthenO(e<$)→aO(e<$J).(ii) 如果e→eJ,则对于从e0开始的所有e<$asuchthatO(e<$)=ethereexistsaunique<$JwithO(e<$J)=eJsuchthate<$→ae'J.第一个条件是标记系统的正确性:它们不引入新的转换,也就是说,它们所有的转换都来自未标记的转换。第二个是完整性条件:我们为每个原始转换都有一个唯一的标记版本。此外,独特性表明,我们不能分别记住关于同一过去的不同事情示 例 2.6 让 我 们 考 虑 排序的 签 名 ( S, N) , 其 中 S ={N at},N={1,2,3,4,5},其中y(i) =Nat, 并且标签的集合L={N,Q}。THE当我们用L中的标签标记每个符号时获得的项只是{1,. ,5},由Q或Q封闭。现在让我们考虑一下过渡制度由图2中的曲线图定义。在这个简单的例子中,定义转换系统的图实际上是一棵树,标记系统将由原始系统的一个或多个副本组成,最多一个用于注释初始符号的每种不同方式,如图3所示。但是,这些副本对于不可到达的术语可能会部分重叠,例如图4中所示的示例。请注意,在标记系统的定义中,我们允许存在一些垃圾节点(在某些条件下),这些节点从初始状态无法到达我们这样做是为了得到一个更灵活的标记系统的定义,这样我们就不需要精确地知道可达项的集合来定义一个标记系统。当然,在实践中,我们将尝试用尽可能少的垃圾来定义它们,以便使系统一156F. Rosa-Velardo等人理论计算机科学电子笔记137(2005)151111125253433422简单越好.2图4.更多示例2.6请注意,在这种情况下,所有的标记系统确实是同构的:如果我们删除每个不可达项,它们就变得相等,直到状态的名称。这是因为在这个简单的例子中,转换图是一棵树,因此,每个节点都确定了从初始节点开始的唯一路径(转换图和可达性树是同构的)。例2.7作为一个新的例子,说明非同构系统,让我们考虑图5左边的图定义的过渡系统,它不是树。特别是,我们可以把它解释为一个系统,代理可以在三个不同的服务器上,并且通过沿着箭头从一个移动到另一个。右边相应的标记系统现在可以区分到达状态3的不同方式。如果我们认为服务器2是恶意的,并且我们不希望我们的代理移动到2,那么我们对中间被标记的系统捕获的属性感兴趣在那里,标记识别服务器2已被访问的计算,如而不是标签Q。如果我们只关心哪个服务器首先然后我们将使用右边的转换系统这些简单的例子表明,存在多个具有不同标签的可达节点使得标签有用:只需检查到达状态中的3标记系统在本节中,我们将把上一节中定义的标记系统描述为它们的可达性树的子树更准确地说,2垃圾节点是无用的,但同时它们是绝对无害的,因为系统的规模不断增加F. Rosa-Velardo等人理论计算机科学电子笔记137(2005)151157一111232323332图5.例2.7的转换系统(左)和标记系统(右)系统是同构的(在我们定义的意义上)计算树,一旦我们已经识别了它的一些节点。我们从定义计算树开始。定义3.1给定S=(E,V,→,e0)是一个标号转移系统,C是S的计算序列集,我们定义相应的计算树St=(C,V,→,e0),作为通过取›→C×V×C,由规则定义e→eJlast(L)=eL→a (L→aeJ)其中计算树只是由原始系统的可达性树定义的转换系统。它只是在其状态中累积沿着计算已经访问的状态的序列以及它们之间的transitions。因此,它包含了关于过程历史的所有信息。我们有时称之为完全标记系统。然而,一般来说,我们只对这些信息的某个特定方面感兴趣。我们将使用计算之间的等价关系来识别所需的信息。定义3.2我们会说等价关系C×C是合适的如果满足以下条件:(i) L1L2last(L1)=last(L2)(ii) L, L ∈C和L <$L <$<$a∈V和e∈E,满足hatlast(L)→ae1 2 1 2 1a a a(and故最后(L2)→e)成立(L1→e)<$(L2→e)。例如,使得L1<$TL2惠last(L1)=last(L2)的关系式<$T和使得L1<$TL2惠L1=L2的关系式<$T是适当等价的平凡例子。158F. Rosa-Velardo等人理论计算机科学电子笔记137(2005)151一∼我2=我通过适当的等价,我们将描述我们感兴趣的关于过去的信息。例如,遗忘是忘记过去的一切的关系,而记忆是绝对记住一切。现在,我们定义由这样的转换等价关系。定义3.3设S=(E,V,→,e0)是一个标号迁移系统,C×C是一个合适的等价关系。我们定义S_n=(C/n,V,<$→n,[e0]),并称它为S关于n的商转移系,作为转移由规则L→LJ[L]→a[LJ]其中L,LJ∈C.定义3.2中的第一个条件被引入,使得商转移系统被一致地定义,在这个意义上,它的转移不依赖于等价类的代表的选择。第二个条件是关系至少记住计算达到的最终状态。对于上面定义的等价物,S和ST分别同构于S和St商转移系统是普通转移系统在以下意义上的保守推广命题3.4如果[L1],[L2] ∈C/n是两个等价类,使得[L] →a[L] thenlast(L)→alast(L)。1 ∼ 2 1 2当Letusup时,poset[L]→a[L]。通过定义<$→有existLJ1 ∼ 2 ∼1一和Lj,使得L1<$LJ,L2<$LJ和Lj<$→LJ。 同样,根据定义,2J1a2 1 2<$→,它认为last(L1)<$→last(LJ),并且,由于L1是合适的并且Li<$LJ,最后一个(Li)=最后一个(LJ),因此,我们完成了Q现在让我们更仔细地观察一下商转换系统集合的结构定义3.5我们用S表示商转移系统的集合,即,S={S}|合适},并通过S1 HS2 Δ S1ΔS2定义算子H和H和S1HS2 ΔS<$1<$$><$2,其中R<$$>R是R<$R的传递闭包。=1 2 1 2由这些算子诱导的阶为S2,即关系所捕获的信息越多,相应的商系统在格中的位置就越高。然后我们有以下内容F. Rosa-Velardo等人理论计算机科学电子笔记137(2005)151159⊥⊥一命题3.6(S,H,H)是一个完全格,其底部元素为S,顶部元素为St。证明首先,(S,H,H)是一个格,因为H和H都是幂等的,交换的,结合的,并满足吸收定律。为了证明它是完备的,我们必须选择S的所有子集,S是一个超自然的子集,infimumm. Let{Si |i∈I}是fS的一个子函数,且ta kef=∗i∈I穆塞韦尼和联系我们i∈I 我是阿吉Rinf和Rinsup都是合适的等价关系,Sinf和Ssup是{ S i}的下确界和上确界|i∈I},re-I.此外,如果是一个合适的等价关系,则T,因此S≤S≤ST。最后,我们仍然可以看到S和St分别同构于S和ST。后者是微不足道的。让我们看看前者。考虑由h(e)=[e]n(e∈E)给出的函数h,即限制于空计算序列的商映射。 让我们假设h是满足所需条件的双射。首先,h是双射的,因为它有last([L])=last(L)作为逆。 请注意,它定义得很好,一因为它是合适的。 此外,由于[e→eJ]= [eJ],因此,e→eJ惠h(e)→a h(eJ),对于所有e∈Re ach(S),如定义2.4所要求。Q现在让我们陈述本节的主要定理。命题3.7设S =(E,V,→,e0)是一个标号迁移系统,T=(E<$,V,<$→,e0)是S的标号. T同构于S的一个不变变换系统.假设T是S的一个标记。我们必须找到一个合适的关系式,使得T同构于S。我们将通过在S的计算序列上定义一个函数π来得到它,使得O(π(L))=last(L),Δ取π的核为π的核,即L1<$L2惠π(L1)=π(L2). 为每个在计算L时,我们通过对它的长度的归纳来定义π(L)基本情况是straig htfor ward,π(e0) =e<$0,t满足O(π(e0))=e0=last(e0). 让我们我们可以定义dπ(L)=e<$,也可以定义dπ(L→aeJ)。如果e=last(L),由于e→aeJ,且we等于O(e<$)=e,则eex为ts一个简单的例子是对标记系统的定义的定义条件2的一种改进。你好takeπ(L→aeJ)=e<$J,则存在O(e<$J)=last(L→aeJ)。很容易看出,这样定义的关系是合适的,并且T与S同 构,只要取h([L])=π(L),这是通过定义π很好地定义的,是可达项之间的双射,并且满足以下条件过渡系统之间的同构Q标记系统的定义为每个计算序列导出了一个交换图,如图6所示。在这个图中,函数π是160F. Rosa-Velardo等人理论计算机科学电子笔记137(2005)151一a B C第一季第二季第三集πe′0πae1πe2Bπce¯3图6.标记系统定义在到达每个ei的计算序列上。反之亦然。命题3.8设S=(E,V,→,e0)是一个标号迁移系统,且合适的等价关系。则S_n同构于S的一个标号。证明设S =(E,V,→,e0)是一个标号迁移系统,并给出了它的一个等价关系. 我们定义一个S的聚集,S′,同构于S′。首先,我们将标记语法中的每个项,这样标记的项可以被看作是对(e,Γ),其中e∈E。现在,我们把等价类的集合C /n作为标签集,等价类的集合C /n由适当的关系n定义。然后我们定义为→由规则e→eJlast(L)=e(e,[L])→a (eJ,[L→aeJ])转换关系<$→是很好的定义,因为它是合适的。则S<$=(E×C/V,V,<$→,(e0,[e0]))是S的一个标记. 为了包含的pr o,我们只需要检查函数h([L])=(last(L),[L])定义了一个由S<$和S组成的同构,它是立即的。Q在我们的例2.6中,由过渡系统生成的格是退化的,因为底部和顶部元素是同构的。因此,所有的标记系统也是同构的。现在我们来看一个更复杂的例子。例3.9现在让我们考虑语言Dπ3[7]和进程l<$k(go κ.gol)),它产生了平凡的代理,这些代理去到位置κ,然后在y死的时候回到l。我们将使用L={Q,N}的值来表示这个词产生的过渡系统。对于每一个自然数n,让u表示由y nn t(k)g(l)|. n. . |(κgol)|l(goκ. g(l)),that是表示正好n个代理在κ处的状态的项。图7中[3]这种语言将在第5节中正式介绍,尽管我们认为,在这里可以理解这个特殊的例子,而不必深入这些正式的细节。eF. Rosa-Velardo等人理论计算机科学电子笔记137(2005)151161nn0000111122223333..0012≤商变迁系统01≤0100123.010101210123.图7.例3.9的转换图(左)和可达性树(右)图8.例3.9的两个商跃迁系统我们给出了转换图(左)和相应的可达性树(右)。然后,图8所示的两个转换图定义了两个现状转换系统。左边的一个决定了已经死亡的特工数量的奇偶性,而右边的一个只决定了是否有探员死亡 因此,在第二种情况下,国家或-响应计算01... n,而状态识别每个计算序列以状态n结束,但是01... n.根据适用关系,识别形式为01的每一个计算... n(可达性树的右分支)只与其自身相关,而对于其余节点,它将以相同状态结束的每个计算关联起来。命题3.7陈述了存在一个同构于一个转移系统的标记的商系统。然而,这样的商系统不是必然唯一的,因为我们的同构概念完全忽略了状态的信息。例3.10在图9中,左边的图定义了一个简单的过渡162F. Rosa-Velardo等人理论计算机科学电子笔记137(2005)151F∼ 1 ∼ 0∼∼ 2 ∼ 12∼1[1]第一章[1]第一章23[12个]第一章[13个国家][12个]第一章[13个国家][第123话][132][第123话][132][1232].[1323].图9.例3.10的同构商系统系统和其他是后者的不同商系统。商系统确实是同构的,但直观上它们捕捉到了原始系统的不同性质:左边的标识了从3开始的计算,而右边的标识了从2开始的计算。为了得到唯一性(见定理3.15),我们需要一个改进的同构,它也保留了状态的一些性质。我们将通过将状态映射到公共域的函数来正式定义这些属性。定义3.11给定S=(E,V,→,e0)和T=(F,V,<$→,f0)以及一个函数f:E<$F→States将E和F中的状态映射到一个集合State,我们说映射h是f-同构,如果:(i) h是过渡系统的同构。(ii) f(h(e))=f(e),对于每个e∈Reach(S)。如果S和T之间存在一个f-同构,我们将写SfT。我们希望我们的同构尊重所达到的状态,无论是在标记和商系统。 因此,我们将确定这些过渡系统到st-同构,是st(e)=O(e)和st([L])=last(L)。为了更精确,并且滥用符号,当比较商系统时,我们将使用st:C/1C/2 →E,当比较标记系统和商系统将使用:E<$LC/→E。我们需要这两个艾玛。引理3.12If[L0]<$则[L1]<$=[L2]<$。→a[L],[L]→a[L]且last(L) =last(L)ProfIf[L] →a[L][L]→a[L]则存在LJ,LJJ,LJ和0∼ ∼ 1∼0∼ ∼ 2∼a0 0 1LJ使得LJ<$L<$LJJ,L<$LJ,其中i= 1, 2,LJ→LJ和LJJ→aLJ。2000ii0 1 0 2F. Rosa-Velardo等人理论计算机科学电子笔记137(2005)15116310200012我一一由于last(L1)=last(L2),且λ是合适的,因此存在e满足LJ=LJ→ae和LJ=LJJ→ae。同样,sinceLJ<$LJJ和适当地,它保持LJ<$LJ。 通过传递性,我们得到L1<$L2,因此[L1]=[L2]。Q引理3.13如果商系统S1和S2是st-同构的,则在S 1和S 2之间存在且仅存在一个st-同构,即由h([L]1)=[L]2定义的函数h。证明设h是S_n ~1和S_n ~2之间的st-同构.让我们通过对L的长度的归纳来看到h([L]<$1)= [L]<$2。如果L=e0,则h([e0]<$1)= [e0]<$2,因为h是同构,[e0]<$1和[e0]<$2是初始状态S1和S2的相对独立性。 NowsupposeL=LJ→ae. 归纳法一假设告诉我们h([LJ]<$1)=[LJ]<$2。由于LJ→L,则[LJ]<$→<$[L]<$。我我由于h是同构,对于i= 1,我们得到h([LJ]<$1)=[LJ]2→∼2 h([L]≠1)。设LJJ∈C使得[LJJ]<$2=h([L]<$1).由于h保持状态,last(LJJ)=st(h([L]<$1))=st([L]<$1)=last(L)。然后我们可以应用前面的引理得到h([L]<$1)=[LJJ]<$2=[L]<$2。Q引理3.14如果S≠1≠S≠2 则1 = 2。证明由于S1<$stS2,存在一个st-同构h,与前面的引理一样。现在,L<$1LJ惠[L]<$1= [LJ]<$1惠h([L]<$1)=h([LJ]<$1)惠[L]<$2= [LJ]<$2惠L<$2LJ,其中第二个等价成立,因为h是双射的。Q注意,例3.10不是前面引理的反例,因为S1和S2是同构的,但事实上,它们不是st-同构的。现在我们可以证明我们的定理了。定理3.15若T是S的一个标号,则存在一个单商S使得TstS。证明• 存在性:等价性和映射h,如命题3.7的证明中所定义的,即h([L])=π(L),使得h定义T和S之间的同构。此外,h是st-同构,因为st(h([L]))=st(π(L))=last(L)=st([L])。• 唯一性:假设存在S1和S2,使得S1≠T,T≠S2。通过传递性,S1大于S2,因此,应用前面的引理,S1 = S2。Q164F. Rosa-Velardo等人理论计算机科学电子笔记137(2005)151一一我4派生标记语言现在我们要解决的问题是,判断一个由标记语法上的归约关系定义的操作语义是否实际上是原始归约语义的标记(因此是商),这是我们最初的目标。标记的语义将在一组可能的初始标记函数标记E→E'上参数化,这将取决于我们感兴趣的特定应用 特别地,标记函数将满足O_tag=IdE,而不是反过来通常,这个函数将在标记上捕获我们感兴趣的属性所需的静态信息通常,如果对于每个P,生成标记(P)的转换系统是转换的标记,则标记语法上的语义是相对于初始标记功能标记的另一操作语义的系统由P.定义4.1我们将证明一个约化关系R<$=(E<$,V,<$→)是R=(E,V,→)相对于初始标记函数tag的标记,如果对于每个e∈E,标记转换s(E<$,V,→,tag(e))是(E,V,→,e)的标记我们将只考虑一个特殊的情况,这对于我们目前的目的来说就足够了:在这个情况下,归约关系在结构上得到了定义。让我们假设→由一组公理Ai定义:Pi→aiQifori = 1,2,. 以及一组结构规则Ri,其形式为P→QCi(P)→Ci(Q)其中上下文Ci= fi(ti,.,Q,..,tn),i=1,2,.. . 其中上下文中使用的f不是可区分的符号。然后,这些结构规则可以直接被认为是标记语法的规则在这种情况下,如果我们把每个公理Ai替换为对应于标记Pi的每种方式的标记版本Ai命题4.2让我们考虑用公理Ai定义的R为:above和一组公理A<$:P<$→ai Q′,其中hi=1,2, . . . ,这样O(P<$)=P我我O(Q′i)=Qi。每个A i都被定义为每个可能的标记44.Tobeexact,wewewillhaveaveeaxiomA¯¯ :P¯aiQ¯forreachP?在O(P<$)=P时,i,Pii→i i i i但通常它们都具有同质结构。这就是为什么我们在上面提出更简洁的符号F. Rosa-Velardo等人理论计算机科学电子笔记137(2005)151165Pi和letR<$b的关系由公理A<$1,A<$2, . .和一组通用规则R1,R2, . . R是R的一个标记。证明给定P0,我们通过规则归纳法证明条件1,›→和条件2通过规则归纳对→的定义(i) IfP<$→a P<$JthenO(P<$)→aO(P<$J)(a) A<$:P<$→ai Q¯。ByhypotesisA:O(P<$)→ai O(Q)。伊伊(b) 为了便于阅读,让我们假设fi是一个一元的常数。一在结构上,我们有一个Ri:P<$=fi(Q<$)→fi(Q<$J)=P<$J,hQ<$→a Q'J。通过归纳,我们可以得到O(Q<$)→a O(Q<$J). 以来算法fi的时间复杂度为O(P<$) =O(fi(Q<$))=fi(O(Q<$)),一并且我们可以应用规则Ri得到O(P<$)=fi(O(Q<$))→fi(O(Q<$ J))=O(fi(Q<$J))=O(P<$J)。(ii) 若P→APJ且P<$∈Reach(tag(P))such,则O(P<$)=P,则n有0存在唯一的P<$J,其中hO(P<$ J)=P<$且P<$→aP<$J:a我(a) A:P→Q。对于每个标记P的P′,我们有一个我我a x i om的uniquetagg edversion,Ai。(b) A增益,假设P=fi(Q)→a PJ=fi(QJ),其中hQ→aQJ.GivenP¯asabove,sincefiisnotdistinguished,itmustehethecaseP<$=fi(Q<$),其中hO(Q<$)=Q。 现在我们不能让他-这里,ex是一个单一的Q<$J,满足O(Q<$ J)=QJ,Q<$→aQ<$J。现在我们可以说P<$J=fi(Q<$J),这就是最大值uchO(P<$ J)=PJ且P<$→a Pj.Q这是从给定的语义导出标记语义的最简单的方式。如果后者是通过结构上的一致性来定义的,当区别的符号既没有出现在它的公理中,也没有出现在规则中时,也可以这样做。在这种情况下,这些公理和规则也可以应用于标记关系,从而定义标记项之间的结构等价。然后,如果我们将相应的同余规则添加到给定的先前约简规则的集合中,我们也获得了原始语义的标记。这就是我们将在下一节中研究的情况。5饰Dπ在本节中,我们将把所提出的方法应用于Dπ语言[7],它是π演算的分布式版本。事实上,为了简单起见,我们将考虑[6]中提出的版本。在那里,基于类型的分析被定义为检测那些存在违反使用资源(更具体地说,通道)的权限的系统。为了证明166F. Rosa-Velardo等人理论计算机科学电子笔记137(2005)151模式X,Y::=x| X@z| X˜过程P,Q::=. ......这是什么?可变局部模式元组系统| u@v| u˜本地化名称元组运动M,N::=0| M|N空组合物| (νe:E)P限制|(νke:E)N限制| k<$P)剂名字值e::= k局部性u,v::=bv基值| 一信道| e名称| X可变图10. Dπ的π在分析的基础上,在标记语法上定义了增强的语义,其中代理由它们在系统执行过程中积累的权限装饰。然后证明了主体归约定理和安全性定理,使得良好类型的代理在增强的语义中不违反权限。然而,增强的语义和原始语义之间没有形式化的联系,因此,类型系统捕获的属性与原始语义没有明确的关系。我们认为需要一种方法来表达原始微积分中的属性。在本节中,我们提供了这样的方法,因为我们证明了标记Dπ是Dπ的标记,因此,根据我们的定义,是一个商。这导致了类型系统捕获了原始系统的属性的结论。此外,我们的近似的一般性将允许我们对任何我们想要用静态分析捕获的属性做同样的事情Dπ的语法定义见图10。这些点代表π演算[9]的常用原语:终止、合成、复制、输入、输出和条件。引入了一个新的构造k(P),即P位于k处,并引入了一个本原gofor movement.创建的名称可以是渠道,也可以是地点。这样的名称是本地的,因此在使用全局引用时需要本地化的名称,如u@v在图11中,你可以找到语言的操作语义的定义。结构上的同余式(我们在这里没有展示)和大多数规则都与π-演算的规则相似只有规则(R-GO)和(R-COMM)是Dπ特有的。前者将一个进程从一个位置移动到另一个位置,而后者将通信限制在本地,即同一位置内的进程之间F. Rosa-Velardo等人理论计算机科学电子笔记137(2005)151167M|(νke:E)N (vke:E)(M|N)如果e/∈ fn(M)(R-GO)(R-COMM)(R-EQ1)(R-EQ2)(S-COPY)(S-l<$go k.P)Γ→k<$P) Γ好!v|是吗?(X:T).Q)→ k <$P)Γ|k <$Q{X:=v})H{kv:T}k<$if u=u then P else Q)Γ→k<$P) Γk<$if u=v then P else Q)Γ→k<$Q) Γk<$P)Γ →k<$P)Γ|k<$P)|Q)Γ →k<$P)Γ如果u/=vk <$(νe:E)P)Γ→ (ν k e:E)k<$P)Γ,{ke:E}如果e/=kN→NJN →NJN < $M M→MJMJ <$NJ(R-STR)(νe)N→(νe)N JM|N→M |N JN→N JM|(ν k e:E)N (v k e:E)(M|N)如果e/∈ fn(M)(R-GO)(R-COMM)(R-EQ1)(R-EQ2)(S-COPY)(S-SPLIT)(S-NEW)l<$gok.P)→k <$a!(vP)|是吗?(X:T).Q)→k <$ifu=u then P else Q ) →k<$if u=v then P else Q)→k <$P)→ k <$P |Q)→ k <$(νe:E)P)→(k<$ P)(k <$P)|k <$Q{X:= v})k <$P)k<$ Q)(k <$P)|k<$P)k <$P)|k <$Q)(νke:E)k<$P)Ifu=/v如果e/=kN→ NJN→ NJN <$M M→ MJ MJ<$ NJ(R-STR)(νe)N→(νe)N JM|N→M |N JN→N J图11. Dπ的语义图12. D π公理(Axioms ofDπ)标记Dπ是Dπ的一个版本,其中构造体()被替换为其中,Γ在类型化环境中变化,即从局部标识符到K的部分函数,K是局部类型的集合,其形式定义如下:不相关[7]。直觉上,它们将权限(使用通道)分配给每个位置的代理。例如,如果一个代理被标记为Γ并且Γ(k)=K,那么它在k处具有由K指定的权限。标记Dπ的语义由图12中的公理和规则定义。其中,Γ,{ke:E}表示Γ在k处的扩张,新名称e具有类型E。最重要的规则是(R-COMM),它允许通过通信获取新的权限。那么标签的集合L是类型化环境的集合,并且区别符号是()。通过简单地检查定义标记的规则,168F. Rosa-Velardo等人理论计算机科学电子笔记137(2005)151可以看出,它们满足前面部分中所施加的条件。事实上,我们有一个标记版本的每一个公理,为每一种方式标记的术语在其左手边。原始语言的其余规则也可以被认为是标记的规则,因为符号在他们的定义中没有出现。 然后我们有以下内容定理5.1标记Dπ是Dπ的一个标记。根据这一结果和我们对标记系统的刻画,得出由标记Dπ的每一项生成的转移系统同构于商转移系统.因此,在标记Dπ上定义的所有属性也是Dπ的属性。特别地,标记术语的每个子集错误项)定义了计算的子集( 错误的计算)。无论初始标记函数是什么,结果都是真的。然而,这个选择对于充分形式化我们所考虑的运行时错误是至关重要的:在本例中是资源访问错误。在[7]中,所选择的函数标签仅为原始演算的类型化过程定义,因此如果M不可类型化,则ntag(M)=n。因此,无法删除这些资源访问错误(违反权限)由不可键入的系统产生在我们看来,资源访问错误的定义应该独立于可类型性。然后我们应该证明类型系统排除了错误的系统。按照这种方法,我们标记每个原始进程,只需将创建的名称添加到标记中,这些名称正是代理最初有权使用的名称。我们将使用映射标签Γ(M)来这样做,其中Γ是M的初始知识。让我们考虑一下由下式定义的系统:(v a:A)(kb!(a)|k?b?(x:A).x!(c))。虽然通道a是由其作用域下的两个代理创建的事实上,名称的范围总是可以通过挤出来扩展。 特别是,该系统和(νa:A)k<$b!(a)|k?b?(x:A).x!C)是等价的。为了处理这个事实,我们将限制标签Γ(M)中的环境域到M中的自由名称的集合,也就是说,我们将具有不变量dom(r)= fn(M),我们用r M表示约束r |fn(M)。 现在我们可以定义初始标记功能。定义5.2设Φ是L中的空(部分)函数(具有空域)。新定义的函数:M→M′• tag(M)=tagΦ(M)如果M是闭的• 标签Γ(0)= 0• 标签Γ(M |N)= tagΓM(M)|tagrN(N)通过:F. Rosa-Velardo等人理论计算机科学电子笔记137(2005)151169我我KK• tagΓ((νle:E)M)=(νle:E)tagΓ,{νle:E}(M)ife∈fn(M)• tagΓ((νle:E)M)=(νle:E)tagΓ(M)ife/∈fn(M)• 标签Γ(l<$P))=l<$P)Γ在[7]中,定义了对应的标记系统M→err上的错误关系,这意味着进程可以违反其权限。为了消除这些错误,定义了一个用于原始语言的类型系统,以及另一个用于标记系统的类型系统D。现在我们需要以下引理。引理5.3如果 rM则r D标记r(M)。证明通过归纳法在用于导出ΓM的规则上的证明是直接的(参见[7]):(i) 0. 由于标号Γ(0)=0且ΓD为 0,所以论文如下。(ii) Γ k<$P)。则情况是Γ ≠kP. 因为Γ:Γ,所以得出ΓD(k<$P)。(iii) Γ-M1|M2,其中r∈Mi。通过加强它,可以得出:Γ Mi ≠Mi,通过归纳假设,Γ MiD标记ΓM(Mi),通过削弱,Γ D标记ΓM(Mi)。自标签Γ(M1|M2)= tagΓM1(M1)|标记为 ΓM2( M2),则遵循Γ D标记为 Γ(M1|M2)。(iv) 其中,r∈(vke:E)M具
下载后可阅读完整内容,剩余1页未读,立即下载
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![-](https://csdnimg.cn/download_wenku/file_type_lunwen.png)
![-](https://csdnimg.cn/download_wenku/file_type_lunwen.png)
![-](https://csdnimg.cn/download_wenku/file_type_lunwen.png)
![-](https://csdnimg.cn/download_wenku/file_type_lunwen.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)
安全验证
文档复制为VIP权益,开通VIP直接复制
![](https://csdnimg.cn/release/wenkucmsfe/public/img/green-success.6a4acb44.png)