没有合适的资源?快使用搜索试试~ 我知道了~
理论计算机科学电子笔记186(2007)27-42www.elsevier.com/locate/entcs知识的时态逻辑及其在安全ClareDixona,Mari-CarmenFern'andezGagob,MichaelFisheraand Wiebe van der Hoeka一 利物浦大学计算机科学系,利物浦L69 7ZF,英国{clare,michael,wiebe}@ csc.liv.ac.ukbDepartamentodeLenguajesyCienciasdelaComputacio'n,U iversityOfMalaga,29071Ma'laga,Spainmcgago@lcc.uma.es摘要知识的时间逻辑对于推理代理或组件的知识很重要的情况以及这种知识可能随着时间发生变化的情况是有用的。在这里,我们研究知识的时态逻辑在安全协议的规范和验证中的应用。我们展示了如何指定与认证协议相关的典型假设。我们考虑这些逻辑的验证方法,特别关注使用子句归结的证明。最后,我们提出了经验,从使用一个决议为基础的定理证明适用于特定的时间逻辑知识的安全协议。保留字:知识的时间逻辑,安全性,验证,定理证明,归结1介绍随着越来越多的信息以电子方式传送,并且随着这些数据的敏感性增加,越来越需要提供用于确保计算机之间的信息传送的安全性的机制。此外,随着网格和普适计算的出现,安全性和信任是这些技术成功的关键。这种对安全性的需求导致了密码协议的发展,其中发生了对相关个人和消息的认证 鉴于该领域的重要性,至关重要的是,使用的技术,提供自动分析这些协议之前部署。自从计算机之间信息传输的安全性成为一个问题以来,很明显,形式化方法应该在分析协议安全性方面发挥关键作用。已经开发了广泛的适用于安全的形式验证工具[36]。通常,这些涉及完全(或1571-0661 © 2007 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi:10.1016/j.entcs.2006.11.04328C. Dixon等人/理论计算机科学电子笔记186(2007)27我最少抽象)状态空间探索,例如通过模型检查[33,38],或使用高阶工具的复杂定理证明[41,13]。虽然这两种类型的方法都取得了重大进展,但都不是完全令人满意的:第一种方法具有无限状态空间的局限性(即使是抽象技术);第二种方法由于所需的人工干预的复杂性而受到限制,并且缺乏成功概率很高的方法。 一个更有吸引力的解决方案介于这两者之间,即使用证明方法,但限制逻辑到可判定或半可判定的片段。虽然这种限制并不总是可能的,但有很多加密协议,这种风格的分析可能是有效的。特别是,许多可以根据参与者的知识和信念的变化来捕获的认证技术都Burrows、Abadi和Needham(BAN逻辑)[3]提出了逻辑工具在安全协议分析中的应用。这些是专门为处理身份验证问题而设计的信念逻辑虽然这些逻辑都是抽象的,但它们有许多缺点,如缺乏语义,无法明确表达时间,需要捕获额外的功能等,这导致了扩展的发展,或类似风格的逻辑,旨在更大的系统类别,如[21,50]。在本文中,我们描述了如何使用标准的,众所周知的模态和时态逻辑的组合,而不是开发专用逻辑,指定安全协议。时态逻辑是经典逻辑的扩展,广泛用于复杂系统的规范和验证。在这种逻辑中,时间是一个附加的维度,因此逻辑属性可以随着时间的推移而演变;因此这种形式的逻辑非常适合于随时间变化的系统,例如动态或自适应系统。时态逻辑已被用于计算机科学和人工智能的许多领域,包括反应(例如分布式或并发)系统的规范和验证[34],从时态规范合成程序[42,31],通过模型检查进行算法验证[26,7],知识表示和推理[15,2,52]以及时态数据库[6,5]。模态逻辑涉及对可能世界的推理。这些世界由每个代理或过程的关系连接起来,表示可能的替代世界。 一个公式如果这些请求是一个错误,则可能在一个错误中指定删除日期(s,t)是i-关系,且在t中成立. 必须有一个公式,记为一个世界s当且仅当对于所有的世界t如果(s,t)在i关系中,则在t.模态逻辑已经被用来捕捉诸如知识,信念,欲望,意图(例如[15,44])等概念。特别是,模态逻辑S5已经被用来推理知识[15]。由于我们对知识感兴趣,我们使用运算符Ki而不是知道k i。和Kii iinsteadofi,而K i iidentestatagi nti逻辑的组合已经被用来指定复杂的系统,如分布式或多代理系统。当指定这样的系统时,我们可能需要表示系统的动态,信息和激励方面动态方面通常使用时间或动态逻辑、信息方面我C. Dixon等人/理论计算机科学电子笔记186(2007)2729例如使用模态逻辑S5和KD 45的知识或信念,以及使用模态逻辑KD的动机方面,例如期望、意图和愿望。在本文中,我们将集中讨论知识的特定时间逻辑[15,37]。这是一个时间逻辑丰富的模态连接词,用于表示一组过程的知识,使用模态逻辑S5。 这些逻辑可以用来形式化陈述,例如:本 文 的 结 构 如 下 。 在 第 2 节 中 , 我 们 描 述 了 一 个 特 殊 的 认 证 协 议 , 即Needham-Schroeder协议。在第3节中,我们为本文中使用的知识时态逻辑KL(n)提供了语法和语义,而在第4节中,我们讨论了如何使用这种逻辑来指定诸如Needham-Schroeder协议之类的协议。在第5节中,我们概述了知识时态逻辑的基于归结的证明方法。在第6节中,我们提供的结果进行了手工证明和自动定理证明相关的逻辑。在第7节中,我们提到了相关的工作,在第8节中,我们提供了结论性意见。2带公钥的Needham-Schroeder协议带有公钥的Needham-Schroeder协议[40]旨在在发起协议的代理A和响应A的代理B之间建立认证。完整的协议由七条消息组成,但我们专注于仅由三条消息组成的我们忽略的消息是代理从服务器请求其他代理公钥的消息。请注意,省略这些步骤相当于假设每个代理始终知道所有其他代理该协议可以描述为以下三个步骤:消息方向内容消息1A→B{NA,A}发布密钥(B)消息2B→A{NB,NA}发布密钥(A)消息3A→B{NB}发布密钥(B)注意,形式为{X,Y}pub key(Z)的消息内容表示包含X和Y但随后用Z形式为NX的元素是特殊的数据项,称为随机数。通常,协议将生成它们自己唯一的随机数(通常是加密的),该随机数至少在最初是所有其他代理未知的。消息1:A向B发送一个加密的随机数和A30C. Dixon等人/理论计算机科学电子笔记186(2007)27消息2:当B接收到消息1时,它使用其对应的私钥对其进行解密以获得NA。然后,B将随机数NA返回给A,并生成另一个自己的随机数NB,并将其发送回去,这一次用A消息3:当A接收到消息2时,它返回BLowe [33]描述了对该协议的中间人攻击代理A试图与不诚实的代理C运行协议。C假装是A,与B一起运行协议。两个协议运行的步骤是交错的,结果是B认为他一直在用A运行协议,而实际上他一直在用C运行协议。因此,C学习B3语法和语义逻辑KL(n),我们考虑的知识时序逻辑是线性时间时序逻辑与多模态S5的融合我们首先给出KL(n)的语法和语义,其中每个模态关系被限制为等价关系[24]。时间分量在具有有限过去和有限未来的离散线性时间模型上解释;对于这样的时间流的明显选择是(N,<),即,按通常的“小于”关系排序的自然数。这种逻辑已经被详细研究[24],是最常用的知识时序逻辑3.1语法公式由集合P={p,q,r,. . 原始命题。语言KL ( n )包含标准的命题连接词<$(not)、(or)、(and)和(implies)。对于知识,我们假设一组代理Ag={1,. n},并引入一组一元模态联结词Ki,其中i∈Ag,公式Kiφ读作“agent iknows φ“.对于时间维度,我们采用通常的[19]将来时时间连接词集合. (next),(sometimes),(eventually),(总是),U(直到)和W(除非,或弱直到)。KL(n),WFFK的合式公式集定义如下:• 假,真,P的任何元素都在WFFK中;• 如果A和B在WFFK中,则也是(其中i∈Ag)KiA.一我们定义了一些特殊的公式类,这些公式在后面会有用。定义3.1文字要么是p,要么是<$p,其中p∈ P。定义3.2模态文字是Kil或<$Kil,其中l是文字,i∈Ag。欧元A组 B组A组B组A组 B组A.A.一AU BAW BC. Dixon等人/理论计算机科学电子笔记186(2007)27313.2语义首先,我们假设世界可能处于一组状态S中的任何一个状态。3.3时间轴t是一个无限长的、线性的、离散的状态序列,由自然数索引。让TLines成为所有时间线的集合。定义3.4点q是一对q=(t,u),其中t∈TLines是一个时间轴,u∈N是到t的时间索引。设点是所有点的集合。定义3.5赋值π是一个函数π:点× P → {T,F}。定义3.6模型M,是一个结构M= RTL,R1,.,Rn,π,其中:• TLTLines是一组时间线,具有一个特殊的时间线t0;• Ri,对于所有i∈Ag,是点上的主体可及性关系,即,Ri=Points×Points,其中每个Ri是等价关系;以及• π是一个估值。像往常一样,我们通过满足关系定义语言的语义。|='.对于KL(n),这种关系在形式为<$M,q<$(其中M是模型,q是TL×N中的点)的对和WFFK中的公式之间成立。定义满意度关系的规则如下。我们省略了一些经典运算符的语义,因为它们是标准的,以及时间运算符U和W,因为它们将不会在本文中进一步使用。M,(t,u)|= trueM,(t,u)|= falseM,(t,u)|= pi<$ π((t,u),p)= T(其中p∈ P)M,(t,u)|=<$A iM,(t,u)|= AM,(t,u)|= ABiM,(t,u)|= A或M,(t,u)|= BM,(t,u)|=. AiM,(t,u+1)|= AM,(t,u)|=AiuJ∈ N, 如果(u≤uJ),则M,(t,uJ)|=AM,(t,u)|=<$Ai <$$>uJ∈ N使得(u ≤ uJ)且<$M,(t,uJ)<$|= AM,(t,u)|= KiA itJ∈TL. uJ∈ N。 若((t,u),(tJ,uJ))∈Ri则M,(tJ,uJ)m|= A对于任何公式A,如果存在某个模型M和时间轴t,使得M,(t,0)|A,则说A是满意的。如果对于任何公式A,对于所有模型M,存在时间轴t,使得32C. Dixon等人/理论计算机科学电子笔记186(2007)27M,(t,0)|= A,则A被称为有效。注意,这是(时态)逻辑的锚定版本,即有效性和满意度进行了评价C. Dixon等人/理论计算机科学电子笔记186(2007)2733在时间的开始(例如[14])。由于KL(n)模型中的主体可达性关系是等价关系,所以正规模态系统S5的公理在KL(n)模型中成立。 系统S5被广泛认为是理想化知识的逻辑,因此KL(n)通常被称为知识的时间逻辑。4使用知识的时间逻辑的具体化在本节中,我们将概述如何使用KL(n)来指定Needham-Schroeder协议。为了做到这一点,我们使用以下语法约定。设M、M1和M2是消息上的变量,W是键上的变量,N是随机数上的变量,V是键和随机数的值上的变量,X、Y、.成为代理人的变量。此外,对于每个代理X,我们假设有密钥pub key(X)和priv key(X),而在这个协议中,A和B是代表两个特定代理的常数。我们确定以下谓词:• 如果代理X发送由密钥W加密的消息M,则send(X,M,W)是满足的;• 如果代理X接收到由密钥W加密的消息M,则rcv(X,M,W)是满足的;• Msg(M)是满足的,如果M是消息;• nonce(N)是满足的,如果N是nonce;• val pub key(X,V)是满足的,如果X的公钥的值是V;• val priv key(X,V)是满足的,如果X的私钥的值是V;• val nonce(N,V)是满足的,如果nonceN的值是V;• contains(M1,M2)是满足的,如果消息M2包含在M1中。为了简化描述,我们允许对代理、消息和密钥的集合进行量化和相等。当我们假设代理、消息、密钥和随机数的有限集合以下是典型假设的例子:• 最初,只有代理A知道它自己的随机数NA的内容,只有B知道它自己的随机数NB的内容;• 发送的消息不能保证到达所需的目的地;• 如果消息被代理接收,则该消息必须先前已被某个代理发送;• 消息的知识持续存在,即代理不会忘记消息内容;• 如果接收到消息,并且接收方知道所需的私钥,则接收方将知道消息的内容;以及• 入侵者可以截取发送给其他人的消息我们允许用一元函数“pub key(X)”和“priv key(X)”来简单地表示公钥和私钥所有代理都知道所有其他代理的公钥,但每个代理34C. Dixon等人/理论计算机科学电子笔记186(2007)27而不是给一套完整的公理,我们提供了一些例子来说明如何指定上述假设。• 最初,只有代理A知道它自己的随机数的值,只有B知道它自己的随机数的值。KAval nonce(NA,an)<$KAval nonce(NB,an)<$KAval nonce(NB,bn)等.在上面的an和bn是特殊值的nonce和将有类似的公式有关的B请注意,这些语句是初始条件,必须在时间开始时成立。• 发送的邮件不保证到达。没有公理的形式send(.. . )rcv(.. . )• 如果有任何消息到达,那么该消息必须是由某个代理先前发送的。M,W. rcv(X,M,W)≠Y. ·snd(Y,M,W)不是因为它是一种操作,它可以在P中进行某些操作,并具有以下电磁学特性M,(t,u)|=·A我的<$uJ∈N suchthat(0≤uJ
下载后可阅读完整内容,剩余1页未读,立即下载
cpongm
- 粉丝: 5
- 资源: 2万+
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
最新资源
- 李兴华Java基础教程:从入门到精通
- U盘与硬盘启动安装教程:从菜鸟到专家
- C++面试宝典:动态内存管理与继承解析
- C++ STL源码深度解析:专家级剖析与关键技术
- C/C++调用DOS命令实战指南
- 神经网络补偿的多传感器航迹融合技术
- GIS中的大地坐标系与椭球体解析
- 海思Hi3515 H.264编解码处理器用户手册
- Oracle基础练习题与解答
- 谷歌地球3D建筑筛选新流程详解
- CFO与CIO携手:数据管理与企业增值的战略
- Eclipse IDE基础教程:从入门到精通
- Shell脚本专家宝典:全面学习与资源指南
- Tomcat安装指南:附带JDK配置步骤
- NA3003A电子水准仪数据格式解析与转换研究
- 自动化专业英语词汇精华:必备术语集锦
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功