基于SPIN的SSL3.0握手协议模型检测

文章介绍了密钥交换协议SSL3.0协议,并利用模型检测工具SPIN对其进行了形式化分析、建模和验证。实验结果表明此验证方法的正确性,证明了协议本身的安全性与可行性,并且提高了协议的验证效率。     

基于时态认知逻辑的Web服务模型检测

传统模型检测技术主要采用时态逻辑描述被验证的规范,人们较少注意多智能体认知逻辑的模型检测问题.而在分布式系统领域,系统和协议的规范很适合用认知逻辑来描述.Web服务是一个典型的分布式系统.把Web服务组合建模为多智能体系统,并成功采用我们实现的时态认知逻辑符号模型检测工具MCTK验证了SAS股票分析服务实例.同时采用WSAT,WS-Engineer和SPIN 3个模型检测工具在相同实验环境下验证了该实例,实验结果表明我们的Web服务模型检测方法不仅比这3个模型检测工具更高效,而且支持认知逻辑规范的验证,这是这3个模型检测工具所不具备的.     

基于SPIN的网络认证协议高效模型检测

为了有效地提高网络认证协议建模和验证的效率,基于模型检测方法提出一个通用的网络认证协议模型描述方法,结合模型检测工具SPIN可以方便地进行性质验证。通过一些模型的简化策略,不仅可以对不同协议进行高效建模,而且减小了模型的状态空间。与现有的文献相比,自动化程度较高,模型验证的效率较好。基于该方法,对PKM认证协议进行了模型检测,实验证明该模型分析验证方法的有效性,可用于其他网络认证协议的分析验证。     

带复杂数据结构的模型检测工具

模型检测是近二十几年来最成功的自动验证技术之一，而模型检测工具的开发是将模型检测和实际相结合的关键．为了有效地对涉及到复杂数据类型的并发传值系统进行模型检测，总结了以扩展的带赋值符号迁移图和模态图分别作为并发系统和逻辑公式的语义模型来实现模型检测工具的工作，特别是将复杂数据结构引入传值进程定义语言和带赋值符号迁移图．同时结合实际例子说明模型检测工具的有效性．     

基于四方的安全电子商务支付协议分析与验证

以基于四方的安全电子商务支付协议为研究对象,建立了协议的有限状态模型以及安全计算树逻辑CTL公式,利用符号模型检测工具SMV对协议的原子性进行检测验证。验证结果证明,基于四方的安全电子商务支付协议满足电子支付的金钱原子性、商品原子性以及确认发送原子性,协议符合电子支付的原子性安全要求。     

基于不变量查找的German协议验证

提出了一种通过查找缓存一致性协议不变量来验证带参协议正确性的新方法.缓存一致性协议验证的难点在于必须证明协议对于任意大小的带参系统都成立.我们通过寻找不变量和协议规则之间的对应关系来计算辅助不变量,从而帮助推导验证缓存一致性协议.我们设计实现了一个不变量查找工具并将该工具应用到German协议上计算它们的辅助不变量并成功地验证了协议的安全性质.     

基于Spin的SET协议模型检测研究

模型检测技术已成功地运用于验证复杂系统的性质。本文提出运用Promela语言对电子商务协议进行建模的方法,对比分析了有无入侵者时简化的SET协议的运行情况。运用Spin模型检测工具,对SET协议的Promela模型进行了检测,对电子商务协议中的关键性质认证性和保密性进行了分析与检测,发现了协议中的缺陷。     

移动支付协议PCMS的形式化分析和验证

移动电子商务协议的形式化分析和验证是近年来移动电子商务协议的一个重要研究热点。以一个支付网关为中心的匿名的移动电子商务支付协议PCMS为研究对象,建立了PCMS协议的时间自动机模型,并用计算树逻辑CTL公式描述PCMS协议的部分性质,最后利用模型检测工具UPPAAL对PCMS协议的无死锁、时效性、有效性和钱原子性进行检测验证。验证结果表明,以支付网关为中心的匿名的安全支付协议PCMS满足无死锁、时效性、有效性和钱原子性。     

Web服务的形式化验证

将Web服务组合建模为多智能体系统,采用时态知识逻辑模型检测工具MCTK刻画贷款协议Web服务实例,并验证相关的时态知识规范。在同一实验环境下,采用另一种时态知识逻辑模型检测工具MCMAS进行建模,并验证该实例。实验结果表明,基于MCTK的Web服务模型检测方法比基于MCMAS的方法更有效。     

一种基于广播的cache一致性协议的设计和验证

在全互联的网络结构下,提出了一种基于广播的cache一致性协议的详细设计,使请求传输不再像目录协议中的那样,经过第三方中转,而是直接发给所有节点,由最新拥有副本者给出响应。对协议进行了分析证明,并建立了模型,通过模型检测工具NuSMV验证了协议的正确性。     

State space reduction in modeling checking parameterized cache coherence protocol by two-dimensional abstraction

Scalability of cache coherence protocol is a key component in future shared-memory multi-core or multi-processor systems. The state space explosion is the first hurdle while applying model-checking to scalable protocols. In order to validate parameterized cache coherence protocols effectively, we present a new method of reducing the state space of parameterized systems, two-dimensional abstraction (TDA). Drawing inspiration from the design principle of parameterized systems, an abstract model of an unbounded system is constructed out of finite states. The mathematical principles underlying TDA is presented. Theoretical reasoning demonstrates that TDA is correct and sound. An example of parameterized cache coherence protocol based on MESI illustrates how to produce a much smaller abstract model by TDA. We also demonstrate the power of our method by applying it to various well-known classes of protocols. During the development of TH-1A supercomputer system, TDA was used to verify the coherence protocol in FT-1000 CPU and showed the potential advantages in reducing the verification complexity.     

MANET虚假路由形式化验证

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

Model checking mobile ad hoc networks

Modeling arbitrary connectivity changes within mobile ad hoc networks (MANETs) makes application of automated formal verification challenging. We use constrained labeled transition systems as a semantic model to represent mobility. To model check MANET protocols with respect to the underlying topology and connectivity changes, we introduce a branching-time temporal logic. The path quantifiers are parameterized by multi-hop constraints over topologies, to discriminate the paths over which the temporal behavior should be investigated; the paths that violate the multi-hop constraints are not considered. A model checking algorithm is presented to verify MANETs that allow arbitrary mobility, under the assumption of reliable communication. It is applied to analyze a leader election protocol.     

多障碍环境中移动机器人的光滑轨迹规划

根据轮式移动机器人参数化轨迹生成模型,结合多障碍物结构化环境中障碍物的建模,把其和参数化轨迹规划模型融合,得到了具有一般性的多障碍物环境中轮式移动机器人光滑轨迹规划模型;并利用最优化控制原理,建立了任意性能指标下,多障碍物环境中最优参数化轨迹生成模型。结合数值求解方法,推导了多障碍物环境中参数化轨迹规划非线性求解模型的求解方法。最后通过仿真验证了参数化轨迹规划求解模型的正确性。     

Networks of Processes with Parameterized State Space

In general, the verification of parameterized networks is undecidable. In recent years there has been a lot of research to identify subclasses of parameterized systems for which certain properties are decidable. Some of the results are based on finite abstractions of the parameterized system in order to use model-checking techniques to establish those properties. In a previous paper we presented a method which allows to compute abstractions of a parameterized system modeled in the decidable logic WS1S. These WS1S systems provide an intuitive way to describe parameterized systems of finite state processes. In practice however, the processes in the network themselves are infinite because of unbounded data structures. One source of unboundedness can be the usage of a parameterized data structure. Another typical source may be the presence of structures ranging over subsets of participating processes. E.g., this is the case for group membership or distributed shared memory consistency protocols. In this paper we use deductive methods to deal with such networks where the data structure is parameterized by the number of processes and an extra parameter. We show how to derive an abstract WS1S system which can be subject to algorithmic verification. For illustration of the method we verify the correctness of a distributed shared memory consistency protocol using PVS for the deductive verification part and the tools PAX and SMV for the algorithmic part.     

Inductively Verifying Invariant Properties of Parameterized Systems

Verification of distributed algorithms can be naturally cast as verifying parameterized systems, the parameter being the number of processes. In general, a parameterized concurrent system represents an infinite family (of finite state systems) parameterized by a recursively defined type such as chains, trees. It is therefore natural to verify parameterized systems by inducting over this type. However, construction of such proofs require combination of model checking with deductive capability. In this paper, we develop a logic program transformation based proof methodology which achieves this combination. One of our transformations (unfolding) represents a single resolution step. Thus model checking can be achieved by repeated application of unfolding. Other transformations (such as folding) represent deductive reasoning and help recognize the induction hypothesis in an inductive proof. Moreover the unfolding and folding transformations can be arbitrarily interleaved in a proof, resulting in a tight integration of decision procedures (such as model checking) with deductive verification.Based on this technique, we have designed and implemented an invariant prover for parameterized systems. Our proof technique is geared to automate nested induction proofs which do not involve strengthening of induction hypothesis. The prover has been used to automatically verify invariant properties of parameterized cache coherence protocols, including broadcast protocols and protocols with global conditions. Furthermore, we have employed the prover for automatic verification of mutual exclusion in the Java Meta-Locking Algorithm. Meta-Locking is a distributed algorithm developed recently by designers in Sun Microsystems for ensuring secure access of Java objects by an arbitrary number of Java threads.     

包含协议和语义的构件一致性验证方法

在基于构件的系统设计中,需要对构件的一致性进行验证。构件的一致性包括语义一致性和协议一致性,已有的一致性验证方法仅支持构件的协议一致性验证。而在实际应用中除了要进行构件的协议一致性验证外,还需要进行其语义一致性验证。为此提出了一种包含协议和语义的构件一致性验证方法。所提方法将方法语义与基于场景的需求规约相结合,使用语义扩展接口自动机模型(SIA)来建模构件的语义和协议信息,使用带有语义约束的UML交互概观图来表示基于场景的需求规约。通过对SIA和带语义约束的UML交互概观图的行为的理论分析,进一步形成了一种一致性验证算法,并用实例来说明其过程。该算法不仅能够检验系统中构件的协议一致性,而且能够检验其语义一致性。该算法中的方法语义包括了该方法参数的类型和详细语义信息,更符合实际应用情形。     

基于模型检测的OpenFlow多交换机数据包转发协议的分析与验证

OpenFlow协议是SDN网络中控制平面与数据转发平面之间进行交互的规范与标准,其正确性将直接影响到整个网络功能的实现。通过模型检测技术实现一种验证OpenFlow协议正确性的形式化方法。首先提取OpenFlow协议的核心子协议,即OpenFlow多交换机数据包转发协议作为验证的实例;然后运用协议行为自动机对该子协议进行形式化建模,并且通过时态逻辑描述协议需要进行验证的性质;最后给出算法验证协议模型是否满足给定的性质要求,以此检测OpenFlow协议是否存在正确性漏洞,以便对其进行修正。     

Fast Byzantine Consensus

We present the first protocol that reaches asynchronous Byzantine consensus in two communication steps in the common case. We prove that our protocol is optimal in terms of both number of communication steps and number of processes for two--step consensus. The protocol can be used to build a replicated state machine that requires only three communication steps per request in the common case. Further, we show a parameterized version of the protocol that is safe despite f Byzantine failures and, in the common case, guarantees two-step execution despite some number t of failures (tle f). We show that this parameterized two-step consensus protocol is also optimal in terms of both number of communication steps and number of processes.     

Verifying Temporal Properties of Reactive Systems: A STeP Tutorial

We review a number of formal verification techniques supported by STeP, the Stanford Temporal Prover, describing how the tool can be used to verify properties of several versions of the Bakery Mutual exclusion algorithm for mutual exclusion. We verify the classic two-process algorithm and simple variants, as well as an atomic parameterized version. The methods used include deductive verification rules, verification diagrams, automatic invariant generation, and finite-state model checking and abstraction.