用于安全协议分析的一种新的状态剪枝方法

Strand空间模型是利用图的形式来描述和分析安全协议的。通过对该模型的研究,总结了已有的状态空间简化技术;研究了如何将认证测试理论应用于安全协议分析中,根据认证测试理论我们得出了一个剪枝定理。研究表明该剪枝定理能够大大减少协议分析中的冗余状态,提高了协议分析的效率。     

有界模型检测和串空间模型相结合的安全协议验证

提出用BMC和串空间结合的方法对安全协议进行验证.首先是通过串空间的出测试理论先构造不安全协议的部分丛结构,通过该丛结构来约束协议运行的的规模和角色行为;然后用BMC对该丛结构进行建模,建立起对应的有限状态自动机和LTL验证规范,进行验证,有效减轻状态空间爆炸问题;利用不安全协议丛结构的特点,对BMC的下界进行优化.这种方式结合了模型检测和定理证明的优点,通过典型的安全协议的分析和实验,验证了本方法较传统的模型检测方法在验证安全协议时,验证效率提高明显.     

安全协议分析中的状态空间简化技术

通过对基于Strand空间模型的安全协议分析方法的研究,提出了协议分析过程中改进的状态空间简化技术,即在协议分析中将状态空间简化技术与剪枝定理相结合,以达到更加有效地简化状态空间的目的。并以Needham-Schroeder—Lowe协议为例,说明了利用该技术进行协议分析的过程。     

一种基于状态扩展的安全协议验证机制

基于模型检测验证协议的方法存在状态空间爆炸问题,其中基于目标绑定搜索状态空间的方法有效控制了状态空间,但不能完全给出协议的运行情况。针对这一问题,提出了一种基于状态扩展的安全协议自动化验证机制,首先对协议状态进行初始搜索,给出协议运行需要的事件,得到协议基本状态,然后进行扩展搜索,考虑基本状态与其他协议运行的关系,形成协议扩展状态。该机制能够有效反映出协议的运行情况,且能够同时对多种安全性质进行验证。     

基于事件集的反应系统模型的验证

在总结前人工作的基础上,提出了一种有效检测并发或反应系统的动态行为模型中违反安全属性的方法,目的是减少为检测违反安全属性所需检测的状态数量,验证过程包括构造一个由所有独立状态图组成的全局状态空间图,并遍历这个全局状态空间图中的状态以便检测安全协议。首先读待验证的安全属性和可能会违反这些属性的相关事件集,构造全局状态空间图只考虑相关事件产生的状态转换。使用该方法验证了"火车道口"系统,减少了59%的搜索空间。     

基于串空间的安全协议自动化验证算法

以串空间模型为理论基础,提出安全协议自动化验证算法IVAP。对于有漏洞的协议,针对不安全属性逆向搜索主体串树,自动生成改进协议并对其进行验证,直至生成一个安全的改进协议。实验结果证明了该自动化验证算法的有效性,与AAAP算法相比,其协议验证效率更高。     

MANET虚假路由形式化验证

提出了Ad-hoc网络虚假路由攻击的形式化验证和分析方法,主要是在参数化Ad-hoc路由协议串空间模型的基础上采用改进的Athena状态表示法来描述问题域,并采用相应的证明搜索过程来完成目标验证。最后设计实现了虚假路由自动验证系统FRpoofor,用它验证和分析了Ariadne安全路由协议运行环境下某些虚假路由的建立过程,以此说明方法的有效性。     

认证测试方法的改进及应用

基于串空间模型的认证测试方法被证明是一种分析认证协议的有效工具,为了使之适用于类型更多、规模更大的安全协议,并提高其在协议的认证性、可达性、机密性、非否认性、会话密钥的新鲜性及主体间的关联度上的分析能力,对原有的认证测试方法进行改进,充分利用消息格式,细化分析步骤,增添相关符号以分析复杂协议的更多安全特性。利用该方法能缩减模型检测自动化工具的搜索范围,在解决空间爆炸问题的同时有效地找到多方协议的具体攻击路径,而且它对安全协议的设计和验证也具有一定的指导作用。     

认证测试方法的改进及应用

基于串空间模型的认证测试方法被证明是一种分析认证协议的有效工具,为了使之适用于类型更多、规模更大的安全协议,并提高其在协议的认证性、可达性、机密性、非否认性、会话密钥的新鲜性及主体间的关联度上的分析能力,对原有的认证测试方法进行改进,充分利用消息格式,细化分析步骤,增添相关符号以分析复杂协议的更多安全特性。利用该方法能缩减模型检测自动化工具的搜索范围,在解决空间爆炸问题的同时有效地找到多方协议的具体攻击路径,而且它对安全协议的设计和验证也具有一定的指导作用。     

Needham-Schroeder 协议的认证测试方法形式化分析

在安全协议的形式化分析方法中,串空间模型和基于串空间模型的认证测试方法是比较常用的验证方法。针对Needham- Schroeder协议存在中间人攻击的缺陷,提出对协议的改进并采用认证测试方法,验证了改进的协议可以满足协议的安全目标。     

AVSP算法

AVSP(Automatic Verifier of Secrurity Protocols)是基于串空间模型(Strand Space Model),并结合使用定理证明和模型检测技术开发出来的密码安全协议自动验证工具。AVSP使用了理想的语义和逻辑来表达安全协议的保密性,同时采用了一些证明策略以控制和减少状态空间爆炸的规模,并加快发现协议中存在的漏洞。     

Study on Strand Space Model Theory

The growing interest in the application of formal methods of cryptographic pro-tocol analysis has led to the development of a number of different ways for analyzing protocol. In this paper, it is strictly proved that if for any strand, there exists at least one bundle containing it, then an entity authentication protocol is secure in strand space model (SSM) with some small extensions. Unfortunately, the results of attack scenario demonstrate that this protocol and the Yahalom protocol and its modification are de facto insecure. By analyzing the reasons of failure of formal inference in strand space model, some deficiencies in original SSM are pointed out. In orderto break through these limitations of analytic capability of SSM, the generalized strand space model(GSSM) induced by some protocol is proposed. In this model, some new classes of strands, oracle strands, high order oracle strands etc., are developed, and some notions are formalized strictly in GSSM, such as protocol attacks, valid protocol run and successful protocol run. GSSM can then be used to further analyze the entity authentication protocol. This analysis sheds light on why this protocol would be vulnerable while it illustrates that GSSM not only can prove security protocol correct, but also can be efficiently used to construct protocol attacks. It is also pointed out that using other protocol to attack some given protocol is essentially the same as the case of using the most of protocol itself.     

Formal automatic verification of cache coherence in multiprocessors with relaxed memory models

State-based, formal methods have been successfully applied to the automatic verification of cache coherence in sequentially consistent systems. However, coherence in shared memory multiprocessors under a relaxed memory model is much more complex to verify automatically. With relaxed memory models, incoming invalidations and outgoing updates can be delayed in each cache while processors are allowed to race ahead. This buffering of memory accesses considerably increases the amount of state in each cache and the complexity of protocol interactions. Moreover, because caches can hold inconsistent copies of the same data for long periods of time, coherence cannot be verified by simply checking that cached copies are identical at all times. This paper makes two major contributions. First, we demonstrate how to model and verify cache coherence under a relaxed memory model in the context of state-based verification methods. Frameworks for modeling the hardware and for generating correct memory access sequences driving the hardware model are developed. We also show correctness properties which must be verified on the hardware model. Second, we demonstrate a successful application of a state-based verification tool called SSM for the verification of the delayed protocol, an aggressive protocol for relaxed memory models. SSM is based on an abstraction technique preserving the properties to verify. We show that with classical, explicit approaches the verification of cache coherence is realistically unfeasible because of the state space explosion problem, whereas SSM is able to verify protocols both at both behavioral and message-passing levels.     

对改进的无线认证协议SSM的分析

针对刘霞提出的改进的Server-specific MAKEP协议,首次利用一种新兴的形式化分析工具—串空间模型对其进行分析。先对协议的机密性进行分析,并运用“理想”和“诚实”两个概念简化分析协议的步骤,证明了rs,rc是保密的,然后对协议的认证性进行分析,分析包括响应者认证和发起者认证。最终结果表明改进的SSM协议能够达到协议的安全目标。     

不同粒度下的文档分类

提出了句子空间模型及基于句子空间模型的分类算法。比较了从词、句子两个不同粒度对文档进行表示的向量空间模型和句子空间模型在对同一问题进行分类时的召回率和准确率。实验表明，与向量空间模型相比，句子空间模型在许多情况下具有较好的分类性能。     

基于串空间理论的安全协议自动验证

针对目前串空间理论依赖分析人员主观判断、无法使用自动化工具进行验证的问题,提出了基于串空间理论的协议认证属性标准化验证过程。首先为协议消息项定义类型标签,对串空间及认证测试理论进行扩展;然后通过判断测试元素出现位置、检验测试元素参数一致性、确认变换进行边唯一存在性和检验目标串参数一致性,将基于串空间理论的协议验证过程标准化为可程序实现的步骤。该算法的时间复杂度为O(n²),避免了模型检测方法的状态空间爆炸问题,并在此基础上实现了安全协议认证属性的自动化验证工具。以BAN-Yahalom协议和TLS 1.0握手协议为例进行了标准化的分析验证,找到了对BAN-Yahalom协议的一种新攻击形式。该攻击无需限制服务器对随机数的检查,比Syverson发现的攻击更具普遍性。     

基于多维度抽象和广度优先搜索空间划分的隐蔽信息流检测方法*

隐蔽信息流检测是开发可信计算机系统中的关键问题,而状态空间爆炸是基于状态机模型检测隐蔽信息流的主要障碍。提出一种多安全级系统中基于主体安全级的二维抽象方法,在此基础上设计了广度优先的搜索空间划分方法,使得划分变量的选取范围更大,扩展了搜索空间划分的应用范围,克服了深度优先划分方法中划分变量难以选取的问题。实验数据表明,结合抽象和搜索空间划分的方法有效降低了模型的验证规模,因此有效缓解了状态空间爆炸问题。