Protocol validation by synthesizing communications system behaviors

A technique is described for automatic validation of communication protocols that are given in the form of regular protocol diagrams. It is based on the use of the link state introduced by West [2], but it has the advantage of not requiring that the state transition diagrams of the two communicating processes be available. The technique is applied to the validation of the CCITT X.21 protocol to illustrate the ease with which it can be used to detect reception errors, deadlock errors and overflow errors.     

An interactive protocol synthesis algorithm using a global statetransition graph

An interactive synthesis algorithm, to construct two communicating finite-state machines (protocols), is presented. The machines exchange messages over two unidirectional FIFI (first-in first-out) channels when the function of the protocol has been given. The synthesis algorithm first constructs the global state transition graph (GSTG) of a protocol to be synthesized and then produces the protocol. It is based on a set of production rules and a set of deadlock avoidance rules, which guarantee that complete reception and deadlock freeness capabilities are provided in the interacting process. This synthesis algorithm prevents a designer from creating unspecified reception and nonexecutable transition, avoids the occurrence of deadlocks, and monitors for the presence of buffer overflow     

Synthesizing Distributed Protocol Specifications from a UML State Machine Modeled Service Specification

The object-oriented paradigm is widely applied in designing and implementing communication systems.Unified Modeling Language(UML) is a standard language used to model the design of object-oriented systems.A protocol state machine is a UML adopted diagram that is widely used in designing communication protocols.It has two key attractive advantages over traditional finite state machines:modeling concurrency and modeling nested hierarchical states.In a distributed communication system,each entity of the system has its own protocol that defines when and how the entity exchanges messages with other communicating entities in the system.The order of the exchanged messages must conform to the overall service specifications of the system.In object-oriented systems,both the service and the protocol specifications are modeled in UML protocol state machines.Protocol specification synthesis methods have to be applied to automatically derive the protocol specification from the service specification.Otherwise,a time-consuming process of design,analysis,and error detection and correction has to be applied iteratively until the design of the protocol becomes error-free and consistent with the service specification.Several synthesis methods are proposed in the literature for models other than UML protocol state machines,and therefore,because of the unique features of the protocol state machines,these methods are inapplicable to services modeled in UML protocol state machines.In this paper,we propose a synthesis method that automatically synthesizes the protocol specification of distributed protocol entities from the service specification,given that both types of specifications are modeled in UML protocol state machines.Our method is based on the latest UML version(UML2.3),and it is proven to synthesize protocol specifications that are syntactically and semantically correct.As an example application,the synthesis method is used to derive the protocol specification of the H.323 standard used in Internet calls.     

基于协议逆向的移动终端通信数据解析

针对移动终端通信协议及通信数据的解析,其难点在于大部分移动终端应用程序并无相关公开的技术文档,难以获知其采取的通信协议类型。指令执行序列分析技术通过分析程序执行的指令序列逆向推断出消息格式和状态机。但有时序列信息采集不全,导致状态机推断不完备,从而无法获取全部协议信息。针对上述问题,提出了一个新型的基于状态机对比推断分析的移动终端通信协议解析方案,可用于取证场景提高数据取证的准确性和完备性。该方案首先利用PIN动态二进制插桩,识别污点源并跟踪污点轨迹分析出协议消息格式;然后根据格式信息对提取的协议消息进行聚类分析推断出原始状态机;最后利用最长公共子序列（LCS,longest common subsequence）算法与已知的协议状态机进行对比,相似度最高者即为推断出的通信协议类型。在Android平台上基于两类应用程序设计实验对该方案进行测试和评估,实验结果表明可准确提取应用程序的通信内容,实用价值强。     

基于通信扩展有限状态机的测试集生成技术

在协议一致性测试中，选择恰当的测试例至关重要。文章介绍协议一致性测试的基本概念及有限状态机和扩展有限状态机的测试模型，重点探讨基于通信扩展有限状态机的测试集生成技术。     

Hierarchical reachability graph of bounded Petri nets forconcurrent-software analysis

Petri nets have been proposed as a promising tool for modeling and analyzing concurrent-software systems such as Ada programs and communication protocol software. Among analysis techniques available for Petri nets, the most general approach is to generate all possible states (markings) of the system in a form of a so-called reachability graph. However, this conventional reachability graph approach is inefficient or intractable, even for a bounded Petri net, due to state explosion in many practical applications. To cope with this problem, this paper proposes a method for constructing a hierarchically organized state space called the hierarchical reachability graph (HRG). Using the HRG, we obtain necessary and sufficient conditions for reachability and deadlock, as well as algorithms to test whether a given state or marking is reachable from the initial state and whether there is a deadlock state (a state with no successor states)     

Model and algorithm for efficient verification of high-assurance properties of real-time systems

In this paper, we present a new compositional verification methodology for efficiently verifying high-assurance properties such as reachability and deadlock freedom of real-time systems. In this methodology, each component of real-time systems is initially specified as a timed automaton and it communicates with other components via synchronous and/or asynchronous communication channels. Then, each component is analyzed by a generation of its state-space graph which is formalized as a new state-space representation model called Multiset Labeled Transition Systems (MLTSs). Afterward, the state spaces of the components are hierarchically composed and simplified through a composition algorithm and a set of condensation rules, respectively, to get a condensed state space of the system. The simplified state spaces preserve equivalence with respect to deadlock and reachable states. Such equivalence is assured by our reduction theories called IOT-failure equivalence and IOT-state equivalence. To show the performance of our methodology, we developed a verification tool RT-IOTA and carried out experiments on some benchmarks such as CSMA/CD protocol, a rail-road crossing, an alternating bit-protocol, etc. Specifically, we look at the time taken to generate the statespace, the size of the state space, and the amount of reduction achieved by our condensation rules. The results demonstrate the strength of our new technique in dealing with the state-explosion problem.     

基于Petri网的数据库系统并发控制活性分析

从数据库系统在时刻t的状态N出发,构造出相应的Petri网模型,进而构造出其可达标识图。通过分析可达标识图,可判断系统是否为死锁状态。若不是死锁状态,系统是否可能出现死锁,什么情况下系统肯定不会出现死锁。最后,给出了数据库系统中事务并发操作的死锁检测方法与避免措施。     

基于Petri网的并发系统活性分析

本文从数据库系统在时刻t的状态N出发，构造出相应的Petri网模型，进而构造出其可达标识图．通过分析可达标识图，可判断系统是否为死锁状态．若不是死锁状态，系统是否可能出现死锁，什么情况下系统肯定不会出现死锁．最后，给出了数据库系统中事务并发操作的死锁检测方法与避免措施．     

SAT-Solving the Coverability Problem for Petri Nets

Net unfoldings have attracted great attention as a powerful technique for combating state space explosion in model checking, and have been applied to verification of finite state systems including 1-safe (finite) Petri nets and synchronous products of finite transition systems. Given that net unfoldings represent the state space in a distributed, implicit manner the verification algorithm is necessarily a two step process: generation of the unfolding and reasoning about it. In his seminal work McMillan (K.L. McMillan, Symbolic Model Checking. Kluwer Academic Publishers, 1993) showed that deadlock detection on unfoldings of 1-safe Petri nets is NP-complete. Since the deadlock problem on Petri nets is PSPACE-hard it is generally accepted that the two step process will yield savings (in time and space) provided the unfoldings are small.In this paper we show how unfoldings can be extended to the context of infinite-state systems. More precisely, we show how unfoldings can be constructed to represent sets of backward reachable states of unbounded Petri nets in a symbolic fashion. Furthermore, based on unfoldings, we show how to solve the coverability problem for unbounded Petri nets using a SAT-solver. Our experiments show that the use of unfoldings, in spite of the two-step process for solving coverability, has better time and space characteristics compared to a traditional reachability based implementation that considers all interleavings for solving the coverability problem.     

Using integer programming to verify general safety and liveness properties

Analysis of concurrent systems is plagued by the state explosion problem. We describe an analysis technique that uses necessary conditions, in the form of linear inequalities, to verify certain properties of concurrent systems, thus avoiding the enumeration of the potentially explosive number of reachable states of the system. This technique has been shown to be capable of verifying simple safety properties, like freedom from deadlock, that can be expressed in terms of the number of certain events occurring in a finite execution, and has been successfully used to analyze a variety of concurrent software systems. In this paper, we extend the technique to the verification of more complex safety properties that involve the order of events and to the verification of liveness properties, which involve infinite executions.     

基于CFSM的协议形式化技术研究

本文主要了基于通信有限状态机的协议形式化技术。     

基于时间自动机的Web服务模型检测

传统的基于有限状态机的组合Web服务模型检测方法不能保证带有时间约束的组合Web服务的正确性.把组合Web服务看成多智能体系统,将带有时间约束的Web服务智能体建模为时间自动机,通过并发组合构成时间自动机网络,从而用时间自动机验证工具UPPAAL对组合Web服务的运行过程进行模拟,并验证其活性、安全性和死锁等性质.采用该方法对雇员出差安排组合Web服务进行建模和验证,结果表明,该组合Web服务存在死锁问题.最后通过分析死锁产生的路径,完善该组合Web服务的通信协议,从而消除了死锁.     

Recovery of CFSM-based protocol and service design from protocol execution traces

Reverse engineering and design recovery are two important concepts for the evolutionary design of systems software. In particular, the reverse engineering of distributed software, such as communications software, is a very challenging practical problem. Most communications software is written without the use of formal methods and is often poorly documented. Consequently, to maintain or modify such software, relevant details of the original design need to be recovered from the executable software itself. This design recovery process involves either static analysis of the code or dynamic analysis of the software behaviour based on selected execution traces. In this paper, we use the dynamic trace analysis approach. Specifically, based on execution traces as represented at selected points of observation, we generate a higher level design representation consisting of communicating finite state machines (CFSMs) corresponding to the protocol design and service constraints. Further, the temporal and concurrent aspects of the protocol behaviour are also captured in the traces and are reflected in the recovered design.     

MPI-RCDD: A Framework for MPI Runtime Communication Deadlock Detection

The message passing interface (MPI) has become a de facto standard for programming models of highperformance computing, but its rich and flexible interface semantics makes the program easy to generate communication deadlock, which seriously affects the usability of the system. However, the existing detection tools for MPI communication deadlock are not scalable enough to adapt to the continuous expansion of system scale. In this context, we propose a framework for MPI runtime communication deadlock detection, namely MPI-RCDD, which contains three kinds of main mechanisms. Firstly, MPI-RCDD has a message logging protocol that is associated with deadlock detection to ensure that the communication messages required for deadlock analysis are not lost. Secondly, it uses the asynchronous processing thread provided by the MPI to implement the transfer of dependencies between processes, so that multiple processes can participate in deadlock detection simultaneously, thus alleviating the performance bottleneck problem of centralized analysis. In addition, it uses an AND⊕OR model based algorithm named AODA to perform deadlock analysis work. The AODA algorithm combines the advantages of both timeout-based and dependency-based deadlock analysis approaches, and allows the processes in the timeout state to search for a deadlock circle or knot in the process of dependency transfer. Further, the AODA algorithm cannot lead to false positives and can represent the source of the deadlock accurately. The experimental results on typical MPI communication deadlock benchmarks such as Umpire Test Suit demonstrate the capability of MPIRCDD. Additionally, the experiments on the NPB benchmarks obtain the satisfying performance cost, which show that the MPI-RCDD has strong scalability.     

Syntactic reductions for efficient deadlock analysis

A well‐known problem in the verification of concurrent systems based on model checking is state explosion: concurrent systems are often represented by automata with a prohibitive number of states. A reduction technique to reduce state explosion in deadlock checking is presented. The method is based on an automatic syntactic simplification of a calculus of communicating systems (CCS) specification, which keeps the parts of the program structure that may lead to a deadlock and deletes the other parts. Copyright © 2002 John Wiley & Sons, Ltd.