没有合适的资源?快使用搜索试试~ 我知道了~
TOM框架中基于规则的Java协议验证程序
理论计算机科学电子笔记117(2005)209-227www.elsevier.com/locate/entcs基于规则的Java协议验证程序Horatiu Cirstea,Pierre-Etienne Moreau,Antoine Reilles洛里亚大学南希二世INRIA CNRSCampusScientique,BP239,54506V和oeuvr re-l`es-NancyCedexFrance摘要本文提出了一种方法,在一个框架,称为TOM,合并声明性和命令式功能的模型检查器的发展。我们说明了我们的方法,通过指定在TOM的Needham-Schroeder公钥协议,旨在建立一个相互认证的发起者和响应者之间的通信,通过一个不安全的网络。我们描述了代理交换消息的行为,以及入侵者和安全不变量的协议应该使用TOM重写规则进行验证。搜索空间的(深度优先或广度优先)探索是使用语言的命令式特性来描述的。我们提出了几个优化,我们比较我们的结果与现有的方法。保留字:模型检查器,协议验证,Java,TOM。1介绍采用重写规则和策略的程序设计已被用于描述几种计算逻辑和变迁系统。在ELAN[2]或MAUDE[4]等基于重写的语言中,转换可以通过条件重写规则来描述,并且使用策略来定义这些规则的应用方式。例如,我们可以定义一种策略,它以所有可能的方式穷尽地应用所有规则,从而验证从初始状态开始,是否可以达到某个状态(通过连续的转换)。然后,使用这样的基于重写的框架以便模型检查转换系统并且特别是像Needham-Schroeder公钥协议的密码协议是自然的。1571-0661 © 2004 Elsevier B. V.根据CC BY-NC-ND许可证开放访问。doi:10.1016/j.entcs.2004.06.022210H. Cirstea等人/理论计算机科学电子笔记117(2005)209Needham-Schroeder公钥协议[14]已经使用多种方法进行了分析,从FDR[15]等模型检查器到NRL [10]等基于定理证明的方法。虽然这个协议只被几个规则描述,但直到1995年G. Lowe [8].在发现安全问题和修改版本的正确性证明之后[9],已经使用了其他几种方法来展示攻击并获得正确的版本[10,12,5]。该协议的最终目标是提供通过不安全网络通信的代理之间的相互认证。代理使用由密钥服务器分发的公钥来加密它们的消息。这里我们考虑G. Lowe在[8]中,我们假设每个代理都知道所有其他代理的公钥,但不能访问它们的私钥。在本文中,我们分析了Needham-Schroeder公钥协议使用的方法,重写规则结合了一个命令式的编程风格,导致一个清晰和灵活的规范,可以有效地执行。更确切地说,我们解释了如何在TOM[13]中指定该协议,TOM是C和Java的扩展,为这些语言添加了模式匹配功能。该协议通过定义参与者之间交换的消息及其随后的状态变化来描述例如,想要发起新通信会话的代理发送消息(在网络中)并进入新状态,其中它期望确认消息。因此,协议可以被看作是代理(包括可能的入侵者)和通信网络的状态序列。因此,很自然地使用重写规则来描述从一种状态到另一种状态的转换,并使用策略来描述这些规则的应用方式TOM条件重写规则描述了代理和入侵者的状态转换以及协议应满足的不变量。该规范既自然又简洁,描述协议的重写规则直接从经典演示中获得[8]。为了提高效率,利用了语言的祈使功能。指导这些规则并探索搜索空间的策略完全使用TOM的命令部分定义。我们获得了非常可靠和有效的深度优先和广度优先战略。规范的执行允许一方面描述攻击,另一方面通过探索所有可能的行为来验证正确的版本。第2节简要介绍了TOM环境。李约瑟-施罗德H. Cirstea等人/理论计算机科学电子笔记117(2005)209211ApiGen生成的Java类TOM定义数据类型定义Fig. 1. TOM和ApiGen之间的相互作用公钥协议在第3节中描述,同时还有一个攻击和一个修正版本。第4节给出了协议的编码,并将我们的结果与其他方法进行了比较。最后一部分总结了本文并对今后的工作提出了展望。2TOM环境TOM是一种语言扩展,它为现有的命令式语言添加了新的匹配原语。这特别适合于描述结构化实体的各种转换,例如树/术语和XML文档。该系统的主要创新之处在于其语言和数据结构的独立性。从实现的角度来看,它是一个编译器,它接受不同的本地语言,如C或Java,其编译过程包括将匹配的结构翻译成底层的本地语言。它的设计遵循我们在基于规则的系统的高效编译方面的经验[7]。对于感兴趣的读者,与TOM相关的设计和实现问题在[13]中介绍。该语言提供了匹配模复杂理论的支持。例如,我们可以指定一个匹配的模结合性和中性元素(也称为列表匹配),这对于建模搜索空间的探索和执行基于列表或XML的转换特别有用。TOM工具与ApiGen系统结合使用,ApiGen系统是抽象语法树实现的生成器[16](见图1)。开始TOM编译程序Java+编译的TOMJava+TOM程序javac字节码212H. Cirstea等人/理论计算机科学电子笔记117(2005)209从输入数据类型定义,ApiGen生成Java中的数据类型,并将此数据类型的定义作为TOM的输入。然后,用户可以在生成的Abstract XML Tree类上使用match构造编写代码,TOM将其编译为普通Java。所生成的代码的特点是强类型与通用接口相结合,并通过最大的子项共享的内存效率和快速相等检查。出于暂时的原因,我们假设TOM只添加了两个新结构:%match和build(')。第一种结构类似于ML和相关语言的匹配原语:给定一个术语(称为主语)和一个模式-动作对列表,匹配原语选择一个匹配主语的模式并执行相关动作。因此,这个结构可以被看作是经典开关/情况结构的扩展。第二种结构是一种机制,它允许人们轻松地在定义的签名上构建基础项 这个操作符称为build,后面是一个在构造函数、变量和函数调用上构建的格式良好的术语。这个词是用前缀写符号为了更好地理解TOM当使用Java作为本机语言时,两个整数的比较可以用以下方式描述:public boolean alert(intn, intn) {%match(Natt1, Natt2) {x,x-> { return true; }{ returntrue;}zero(),zero(_)-> { return false; } zero(x),zero(y)-> { return zero(x,y);}}}这个例子应该这样理解:给定两个项t1和t2(表示Peano整数),如果t1大于或等于t2,则对CherterThan的求值返回true。这是通过(非线性)模式匹配(第一个模式)和匿名变量(第二个和第三个模式)来实现的的读者应该注意,变量不需要声明:它们的类型是从使用它们的运算符的定义中自动推断出来的。将一个常数与一个变量区分开来(e)。G.常数零),可以使用空括号。如前所述,TOM的一个重要特性是支持列表匹配,也被称为具有中性元素的关联匹配。 让我们考虑用于构建自然数列表(NatList)的关联运算符conc。在TOM中,关联运算符是可变的,每个子项可以是排序元素或列表(在我们的例子中分别是Nat或NatList)。为了说明关联匹配的表现力,我们可以定义一个排序算法如下:public int findDuplicate(intfindDuplicate) {%match(NatListl) {conc(X1*,x,X2*,y,X3*)->{H. Cirstea等人/理论计算机科学电子笔记117(2005)209213if(x,y)){ return}_ -> { returnl;}}}在这个例子中,我们可以注意到列表变量的使用,用一个' * '注释给定一个部分排序的列表,排序函数试图找到两个元素x和y,使得x大于y。如果存在两个这样的元素,它们将被交换,并递归地应用排序函数当列表排序时,无法在列表中找到,并尝试下一个模式。事实上,这种模式对它的主体没有任何限制,因此触发了相应的动作,并返回了排序列表l。3Needham-Schroeder公钥协议Needham-Schroeder公钥协议[14]旨在通过不安全的网络在发起者和响应者之间建立相互认证。每个代理A拥有一个公共密钥K(A)和一个(私有)秘密密钥K(A)的逆,公共密钥K(A)可以由任何其他代理从密钥服务器 用代理A的公钥加密的消息m由{m}K(A)表示,并且只能由所有者解密对应的密钥,即A。在本文中,我们只考虑[8]中提出的简化版本,假设每个代理在开始时知道所有其他代理的公钥。1.A→B: {NA,A}K(B)2.B→A: {NA,NB}K(A)3.A→B: {NB}K(B)该协议使用随机数,这些随机数是要在该协议的单次运行中使用的新鲜随机数。我们将由代理A生成的随机数表示为NA。发起者A试图与代理B建立会话。为此,A向B发送消息,该消息包含新生成的随机数NA及其身份,并且该消息用其密钥K(B)加密。当B接收到这样的消息时,代理可以解密它并提取随机数NA和发送者的身份。代理B生成一个新的随机数NB,并将其与NA一起发送到A,该消息使用A.当A收到这个响应时,它可以解密消息,并假设已经与B建立了会话。 代理A将随机数NB发送回B,并且当接收到该最后消息时,B假设会话214H. Cirstea等人/理论计算机科学电子笔记117(2005)209因为只有A才能解密包含NB的消息。对于像Needham-Schroeder公钥协议这样的认证协议,期望的主要属性是防止入侵者冒充两个代理中的一个。入侵者是通信网络的用户,因此,它可以发起与其他代理的标准会话,并且它可以响应其他代理发送的消息。入侵者可以拦截来自网络的任何消息,并可以解密用其密钥加密的消息。从解密的消息中获得的随机数可以被入侵者用于生成新的(假的)消息。入侵者无法解密的截获消息将按原样重放。在[8]中提出了一种对协议的攻击,其中入侵者冒充代理A,以便与代理B建立会话。该攻击涉及协议的两个同时运行:一个由A发起以建立与入侵者I的通信,第二个由试图冒充A(由I(A)表示)以建立与B的通信的I发起。攻击涉及以下步骤,其中I.n,II.n分别代表第一和第二会话中的步骤,I(A)代表冒充代理A的入侵者:I.1.A→I:{NA,A}K(I)二.1.I(A)→B:{NA,A}K(B)二.2.B→I(A):{NA,NB}K(A)I.2.I→A:{NA,NB}K(A)I.3.A→I:{NB}K(I)二.3.I(A)→B:{NB}K(B)代理A试图通过发送新生成的随机数NA来与入侵者I建立会话。 入侵者解密消息并发起与B的第二次会话,但声称是A。代理B用A的密钥加密的消息响应I,入侵者拦截它并将其转发给A。A能够解密最后一条消息,并向I发送适当的响应。因此,入侵者可以获得随机数NB,并将其加密发送给B。此时,B认为已经与A建立了会话,而实际上这个会话已经与入侵者建立了。在[9]中所示的校正中,响应者在消息的加密部分中引入其标识,并且发起者检查该标识是否对应于与其开始会话的代理。然后修改协议的第二步,修正后的协议变为:H. Cirstea等人/理论计算机科学电子笔记117(2005)2092151.A→B: {NA,A}K(B)2.B→A: {NA,NB,B}K(A)3.A→B: {NB}K(B)4Needham-Schroeder协议的TOM在本节中,我们将描述TOM中的协议。TOM重写规则对应于在发送和/或接收消息之后代理从一个状态到另一个状态的转换。指导这些重写规则的应用的策略描述了一种形式的模型检查,其中探索了所有可能的这种探索可以以深度优先或广度优先的方式进行。前一种方法在攻击存在时更有效地检测攻击,因此当搜索空间的探索未完成时,而后一种方法在分析校正版本时更有效,因此最终探索了所有可能的状态。我们在本文中提出的具体化技术允许我们探索有限的状态空间,因此,它非常适合检测对协议的攻击,而不是在无界模型中证明其正确性我们首先介绍了参与协议的不同实体的编码,例如交换消息的代理,拦截这些消息的入侵者以及用作通信支持的网络。正如我们稍后将看到的,代理(发起者和响应者)的数量在实现中没有一方面,这使我们能够展示TOM规范的表现力,另一方面,在效率方面,将结果与ELAN[3]和Mur [6]等其他方法进行比较。每个代理的特征是在发送或接收消息时修改的状态。代理的转换,更一般地说,全球环境从一个状态到另一个状态的转换由TOM重写规则指定。然后,通过尝试将每个定义的规则应用于当前状态来探索所有可能的行为。如前所述,使用多排序签名抽象地定义数据集,更确切地说,我们使用ApiGen生成Java实现,以确保最大的子项共享。 代理、消息和网络的完整说明在第4.1节中描述。 在第4.2节中,我们展示了如何使用TOM来简明地描述代理的行为(使用转换规则)和搜索空间的探索(使用Java本地代码)。216H. Cirstea等人/理论计算机科学电子笔记117(2005)2094.1数据结构代理(可以是发起者或响应者)由三个属性定义:身份ID,当前状态和他们创建的noncenonce。 类型Agent的对象可以使用构造函数代理生成如以下ApiGen定义所述:Agent::= agent(id:AgentId,state:AgentState,nonce:Nonce)代理的标识要么是显式定义的名称,要么是通用的发送者 或接收器:AgentId::= alice|鲍勃|戴|sender(number:int)|receiver(number:int)AgentState状态有三种可能的值。如果代理既没有发送也没有接收新会话的请求,则该代理处于SLEEP状态。 在WAIT状态下,代理已经发送或接收了一个请求,当到达COMMIT状态时,代理已经建立了一个会话。所有这些状态都有明确的定义:代理状态::=睡眠|等|承诺代理创建的随机数通常是标识会话的随机数,但在我们的编码中,我们考虑跟踪使用它们的代理的随机数:Nonce::= N(id1:AgentId,id2:AgentId)当使用这种编码时,如果生成随机数的代理记录它,那么代理在每个时刻都知道谁是它正在与之建立会话的代理。 例如,代理alice生成并生成-当尝试与bob建立会话时,orizes nonceN(alice,bob)。虚拟随机数DN被定义为N(dai,dai),其中dai是虚拟代理身份。代理之间交换的消息包含消息的发送者(src)和接收者(dst)的身份Message::= msg(src:AgentId,dst:AgentId,key:Key,nonce1:Nonce,nonce2:Nonce,adr:地址)代理的地址及其私钥仅取决于其身份:地址::= A(id:AgentId)密钥::= K(id:AgentId)H. Cirstea等人/理论计算机科学电子笔记117(2005)209217包含源地址和目的地址的消息头不加密(因此可以被入侵者伪造),而包含所有其他信息的消息主体使用给定的密钥加密,并且只能由私钥的所有者解密通信网络可以被看作是一个消息列表,因此我们使用ApiGen的列表构造函数引入ListMessage类型作为Message类型对象的列表。类似地,我们可以定义代理列表(ListAgent)和随机数列表(ListNonce)。入侵者是一种特殊的代理,不仅参与正常的通信,而且还可以拦截和创建(假)消息。入侵者存储(在随机数中)截获的消息的随机数,用它的密钥加密的消息和(在消息中)它不能解密的消息。Intruder::= intruder(id:AgentId,nonces:ListNonce,消息:ListMessage)下一节介绍的重写规则描述了全局状态的修改,全局状态由参与通信的所有代理的状态和网络的状态组成。还有两种特殊的状态,分别表示在当前会话上成功攻击后获得的配置和消息交换期间的错误:State::= state(用户:ListAgent,接收者:ListAgent,入侵者:Intruder,网络:ListMessage)|误差|ERROR4.2重写规则重写规则描述了参与会话的诚实代理的行为和试图冒充其中一个代理的入侵者的行为,协议的不变量也由重写规则表示。4.2.1特工会话的一个参与者的状态的每次修改由重写规则描述。开始时,所有代理都处于SLEEP状态,等待发起会话或接收新会话的请求。当发起者x处于睡眠状态时,它可以通过发送包含随机数的消息来发起与(随机选择的)响应者y的会话,并且它的地址,并用y的公钥编码。我们可以通过以下规则来描述全局状态变化:218H. Cirstea等人/理论计算机科学电子笔记117(2005)209∗‚‚∗ ∗‚ ‚ ∗ ∗‚:<$S1+agent(x,SLEEP,)+S2<$S1+agent(x,WAIT,N(x,y))+S2<$‚∗∗‚ ‚∗ ∗‚接收者:<$R1+agent(y,,)+R2<$R1+agent(y,,)+R2<$===入侵者:网络:M‚ ‚‚ ‚M‚‚+ msg(x,y,K(y),N(x,y),DN(),A(x))ifsizeMessage(M){public void onResume(状态state =set.add();}}在上面的重写规则中,x和y是AgentId类型的变量,分别表示发起者的身份和响应者的身份。由于concAgent是(AgentList的)列表构造函数,因此在处理此运算符时采用关联匹配,因此两个代理的标识x和y从两个列表我我∗H. Cirstea等人/理论计算机科学电子笔记117(2005)209219∗SS∗发起者和接收者。事实上,当穷尽地探索搜索空间时,将考虑对应匹配的所有可能的解决方案。我们在这个规则中使用了TOM提供的几个语法特性:和其他变量一样,这可以在操作部分中重用以构建新术语。标记后者可以由空列表实例化发送消息的发送方切换到WAIT状态,等待响应。响应者列表dst保持不变(因为仅用于选择可能的目的地)。第二个类似的规则考虑了初始消息的目的地是入侵者而不是响应者的情况‚∗ ∗‚ ‚ ∗ ∗‚n:<$S1+agent(x,SLEEP,)+S2<$S1+agent(x,WAIT,N(x,w))+S2<$‚接收器:R‚ ‚ ‚R===入侵者: ·intruder(w,,)intruder(w,,)‚网络:M‚ ‚M‚+ msg(x,w,K(w),N(x,w),DN(),A(x))ifsizeMessage(M) { if(sizeMessage({消息消息= 'msg(w,y,K(y),resp,init,A(yp)); if(!existMessage(message,state={\fnSimHei\bord1\shad1\pos(200,288)由于用于选择随机数和代理的关联匹配,每次应用此规则时,要么生成不同的消息,要么将消息发送到不同的目的地。这样,入侵者生成所有可能的消息,并将它们发送(如果尚未发送)给所有可能的代理。类似的规则描述了只包含一个随机数的消息的构造。S∗∗222H. Cirstea等人/理论计算机科学电子笔记117(2005)209‚S‚∗∗‚‚4.2.3不变量用于指定协议正确性条件的不变量也由重写规则表示。我们必须检查响应者的真实性,也就是说,检查响应发起者的代理是否确实是正确的代理(而不是入侵者)。同样,我们应该验证通信是与发起它的代理建立的,即发起者的真实性。我们没有指定建立通信的代理应该遵守的条件,而是定义了可以被视为违反协议真实性重写规则描述了第一个不变量的否定,因此,攻击的可能性检查发起者是否已经结束了协议(i. e.处于COMMIT状态),而相应的响应者(不是入侵者)既没有提交也没有发送适当的响应(因此准备好提交)。更确切地说,如果存在处于COMMIT状态的发起者,使得对应的响应者既不是在状态COMMIT或状态WAIT(等待确认从发起人)。‚∗ ∗‚n:<$S1+agent(x,COMMIT,N(x,y))+S2<$‚接收器:R‚‚·=攻击intruder:<$intruder(w,,)<$‚ ‚网络:M如果y/=w如果agent(y,WAIT,N(y,x))/∈R如果agent(y,COMMIT,N(y,x))/∈R<$对于发起者的真实性,我们进行类似的操作,我们验证响应者是否处于COMMIT状态,而相应的发起者尚未达到此状态:‚ ‚我:接收器:<$R1+agent(y,COMMIT,N(y,x))+R2<$入侵者: ‚·intruder(w,,)·=攻击‚∗‚网络:M如果x/=w如果agent(x,COMMIT,N(x,y))/∈S如果这两个重写规则中的一个可以在规范的执行过程中应用,则不能确保协议的真实性,并且可以从执行的跟踪中描述攻击。如果可以应用第一个重写规则,我们可以得出结论,响应者已被(入侵者)模拟,如果可以应用第二个重写规则,我们可以得出结论,发起者已被(入侵者)模拟H. Cirstea等人/理论计算机科学电子笔记117(2005)2092234.3探索搜索空间重写规则用于指定协议和不变量的行为,应该由描述其应用的策略来指导。基本上,我们希望以任何顺序和所有可能的方式重复应用所有上述重写规则,直到可以应用其中一个攻击规则在以前用ELAN编写的实现中,使用回溯机制来探索搜索空间:当消息不指向对于攻击,执行回溯并选择新的目的地和/或地址。我们继续这样做,直到发现攻击或没有新的消息可以生成。这允许入侵者生成所有可能的消息,并将它们发送(如果尚未发送)给所有可能的代理。当使用回溯方法时,一个困难是对深度优先策略以外的策略进行建模。在我们的例子中,由于几个转换可能导致相同的状态,所以用广度优先策略探索搜索空间并删除双精度,从而减少要探索的状态数量是很有趣的。当使用TOM时,与ELAN或Prolog等系统相反,搜索空间必须显式处理。一方面,这导致了更复杂的实现,但另一方面,这为搜索策略的描述提供了更多的灵活性,从而使其更加具体和优化。在当前的实现中,我们从包含初始状态的一组状态开始。然后,对于集合中的每个状态,我们计算后继者的集合:通过应用单个过渡步骤可以到达的所有状态。重复这个过程,直到在状态集中发现攻击或达到固定点:不能再执行转换。假设start是所有代理都处于SLEEP状态的初始状态,set1和set2是Java集合,并且computeSuccessors是一个将状态作为输入并计算一组后继者的函数,所提出的战略可按如下方式实施:public boolean translation(int n){ set1.add(int n);同时(!set1.isEmpty()){ Iteratorit= set1.iterator();while(it.hasNext()){ computeSuccessors(it.next(),set2); } if(set2.contains(ATTACK)){ return true;}set1= set2;}返回false;}224H. Cirstea等人/理论计算机科学电子笔记117(2005)2094.4TOM实现与现有方法的比较我们将TOM规范与模型检查器Mur [11]中定义的类似规范以及基于重写的语言ELAN[3]中描述的另一个规范进行我们选择后者主要是出于历史原因,而前者则是因为它提供了间接的比较。这些方法在描述协议的方式上与TOM方法非常相似,因此这些实现的效率比较非常可靠。当然,该协议的几个其他实现是可用的(例如,G.在Spin或Maude中),但由于相应规范存在重大差异,因此尚未实现直接比较。在ELAN中,描述协议的规则和指导这些规则的策略是在同一级别定义的因此,我们得到了一个统一的规范,但是,尽管策略语言相当强大,并且深度优先搜索方法的定义是自然和简单的,但广度优先策略的描述是复杂的一些操作符,例如,用于构建消息列表的操作符,被声明为关联交换的,从而避免了一些隐式操作,例如对消息进行排序。在Mur实现中使用的规则与ELAN和TOM规范中使用的规则类似,但交互代理的数量是内置的。有两种可能的内置验证策略(深度优先和广度优先)在执行时指定。几种优化,例如,通过对称性的减少,允许一个削减(显着)搜索空间是可用的。首先,我们可以比较这些方法建模的容易程度。 为此,我们需要使用类似于[1]中使用的某种度量。 由于该指标只反映了部分情况,因此在解释结果时必须小心。我们将比较规范不同部分的行数。这不是没有问题的,因为行数受到布局约定的影响,并且必须在代码大小,规范的清晰度和开发时间之间进行妥协。线总剥离数据规则控制穆尔河44932347255内置Elan4392504915435汤姆5633813025875Total测量整个规范中的行,包括注释,H. Cirstea等人/理论计算机科学电子笔记117(2005)209225数量网络规模时间(秒)发送RCV穆尔河Elan汤姆1110.110.010.081121.470.110.3411338.901.200.662112.760.490.5121277.01-7.8822169.5039.043.5231113.6934.902.62321703.76-69.592226456.53-234.54图二. 比较MurELAN和TOM实现。而Stripped是指定代码的大小,没有注释。其他列比较数据结构、模型定义和控制过程的声明的大小。请注意,此度量的主要区别在于控制程序的大小。如前所述,在Mur中,探索策略是内置的,规则以深度优先或广度优先的方式反复应用。在ELAN中,使用用户定义的重写策略,而在TOM中,控制使用本地语言Java表示。这导致了TOM中的细粒度和非常灵活的控制,但对应的是控制过程的长度。这种对模型执行的细粒度控制导致模型的优化执行。测试在具有512MB内存和256KB缓存的1.4 GHz Xeon工作站上进行。对于这些测试,我们考虑了固定版本的方案,如[9]所述因此,我们探索整个搜索空间,表明有没有攻击的修正版本的协议时,在网络中的代理和消息的可变数量被认为是。图2所示的结果清楚地表明了TOM方法的重要性。在小问题上,效率与Mur和ELAN相当。在更大的例子中(例如,网络中有2个节点,2个接收者和1条消息),实验结果表明TOM比ELAN和MurRing快10到20倍。226H. Cirstea等人/理论计算机科学电子笔记117(2005)209让我们提醒一下,所呈现的实现是用Java编写的,与分别用C++和C编写的Mur和ELAN版本相同。因此,增益并不来自低级别的实现细节:性能改善来自搜索空间的探索方式。在ELAN中,由于回溯,应用了深度优先搜索策略。在Mur中,我们使用了广度优先搜索策略,并结合了与排序程序类似的对称性降低优化。 在汤姆,我们使用了4.3节中描述的非常简单的广度优先搜索策略,并结合了状态的最大共享表示(通过ApiGen获得)。这使我们能够有效地比较和消除冗余状态,从而减少搜索空间。既然汤姆知道不支持关联-交换匹配,两个等价的状态可以不同地表示(消息和随机数的存储顺序很重要)。为了改善这种状态的共享,我们使用排序的消息和随机数列表,以这样一种方式,我们操纵规范表示。因此,通过比较指针,可以在恒定时间内执行两个状态的比较。表2中的结果还表明,对于某些参数(例如3个UART和2个接收器),ELAN版本无法在512 MB内存内验证协议的正确性。5结论我们已经提出了一种方法合并声明和命令式范式的Needham-Schroeder公钥协议的验证。描述协议的规则很容易用TOM条件重写规则表示。TOM中的内置列表匹配允许我们表达并轻松处理从一组代理中随机选择代理或从一组消息中随机选择消息。实现的重写规则描述了代理和入侵者的行为网络中的接收者和接收者的数量以及最大消息数量是不固定的,但可以在验证时给出这样我们就得到了一个既灵活又有效的简明规范。我们规范的性能优于其他工具。这项工作的一个明显的延续将是,一方面,我们的实现方法的改进,例如,更好的关联或关联交换匹配算法。另一方面,更复杂的协议应该用这样的混合来指定和验证。H. Cirstea等人/理论计算机科学电子笔记117(2005)209227建模策略。 我们的技术在表现力和效率方面的比较应该扩展到其他工具,例如Spin引用[1] D. Basin和G.丹可Maude与haskell:安全协议分析的实验比较。在K。Futatsugi,编辑,理论计算机科学电子笔记,第36卷。Elsevier Science Publishers,2001.[2] P. Borova n sky',C. K ir chn er,H. K ir chner,P. - E. 莫雷阿乌和C。 Ringeissen. 一个关于ELAN的故事在第二届重写逻辑及其应用国际研讨会,第15卷,PONT-`A-MOUSSON(法国),September r 1998。核心计算系统中的电气节点。[3] H. Cirstea。使用重写和策略的身份验证协议。第三届国际声明性语言实践问题研讨会,LNCS1990卷,第138-153页,美国拉斯维加斯,2001年3月[4] M. Clavel,F. 杜兰,S。 Eker,P. 林科林,N。 妈的-哦,J。 我是你,还有C。 Talcott.Maude 2.0系统。In R. Nieuwenhuis,编辑,Rewriting Techniques and Applications(RTA2003),计算机科学讲义第2706号,第76-87页。Springer-Verlag,2003年6月。[5] G.丹可从重写理论到时态逻辑理论。在第二届国际研讨会上重新编写LogicanditsApplications,第15卷,Pont-a`-Mosson(法文),Septembe r 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直接复制
信息提交成功