Deriving protocol specifications from service specifications written in LOTOS

Summary.  A complete communication system is broken down into a number of protocol layers each of which provides services to the layer above it and uses services provided by its underlying layer. A service specification defines a particular ordering of the operations that a given layer provides to the layer above it. The active elements in each layer are called entities and they use a protocol in order to implement their service definition. On the basis of this relation between the service and protocol concepts we have developed algorithms for deriving protocol entity specifications from a formal service specification. The derived protocol entities ensure the correct ordering of the service primitives by exchanging synchronization messages through an underlying communication medium. This paper presents an extended version of our earlier derivation algorithms. This version of the algorithm can handle all operators and unrestricted process invocation and recursion as defined by basis LOTOS. The correctness of this derivation algorithm is formally proved. Received: January 1992 / Accepted: February 1996     

On constructing communication protocols from component-based service specifications

Constructing communication protocols from component service specifications, each of which specifies a subfunction of the target protocol, enables efficient development of a large and complex communication protocol. Concerning this construction, related techniques have been already proposed: integration of component protocol specifications into a single protocol specification and transformation of service specifications to protocol specifications. However, the integration needs special knowledge of communication protocols, and the transformation requires that a large and complex service specification should be developed as input to produce the target protocol. In order to cope with these problems, this paper proposes a new method which at first integrates component service specifications into a single service specification, and then transforms the service specification into the target protocol by a protocol synthesis technique. The most important point of view is that component integration is performed at the service specification level rather than the protocol specification level. Additionally, we define a class of ‘well-formed’ service specification which ensures correctness of the target protocol. As a result, the integration and transformation can be efficiently executed in small state space without special knowledge of communication protocols. Finally, we have shown the effectiveness of the proposed method by constructing a part of the real-life OSI protocol FTAM.     

A systematic review of code generation proposals from state machine specifications

ContextModel Driven Development (MDD) encourages the use of models for developing complex software systems. Following a MDD approach, modelling languages are used to diagrammatically model the structure and behaviour of object-oriented software, among which state-based languages (including UML state machines, finite state machines and Harel statecharts) constitute the most widely used to specify the dynamic behaviour of a system. However, generating code from state machine models as part of the final system constitutes one of the most challenging tasks due to its dynamic nature and because many state machine concepts are not supported by the object-oriented programming languages. Therefore, it is not surprising that such code generation has received great attention over the years.ObjectiveThe overall objective of this paper is to plot the landscape of published proposals in the field of object oriented code generation from state machine specifications, restricting the search neither to a specific context nor to a particular programming language.MethodWe perform a systematic, accurate literature review of published studies focusing on the object oriented implementation of state machine specifications.ResultsThe systematic review is based on a comprehensive set of 53 resources in all, which we have classified into two groups: pattern-based and not pattern-based. For each proposal, we have analysed both the state machine specification elements they support and the means the authors propose for their implementation. Additionally, the review investigates which proposals take into account desirable features to be considered in software development such as maintenance or reusability.ConclusionsOne of the conclusions drawn from the review is that most of the analysed works are based on a software design pattern. Another key finding is that many papers neither support several of the main components of the expressive richness of state machine specifications nor provide an implementation strategy that considers relevant qualitative aspects in software development.     

Reverse reachability analysis: A new technique for deadlock detection on communicating finite state machines

The communicating finite state machines can exchange messages over bounded FIFO channels. In this paper, a new technique, called reverse reachability analysis, is proposed to detect deadlocks on the communication between the communicating finite state machines. The technique is based on finding reverse reachable paths starting from possible deadlock states. If a reverse reachable path can reach the initial global state, then deadlock occurs. Otherwise the communication is deadlock-free. The effectiveness of the technique has been verified by some real protocols such as a specification of X.25 call establishment/clear protocol and Bartlet's alternating bit protocol.     

基于功能驱动的实体关联方法

系统开发中的信息建模方法实质都可以看作是针对系统功能的实体之间的关联分析,无论是结构化方法使用的E—R图建模,还是面向对象方法使用的UML建模。分析了传统的实体关联法在信息建模方面的优势以及缺陷,提出了基于功能驱动的实体关联方法的思路和模型,并进而论述了基于功能驱动的实体关联方法实现多种信息建模方法一体化的可能。     

An approach to testing specifications

An approach to testing the consistency of specifications is explored, which is applicable to the design validation of communication protocols and other cases of step-wise refinement. In this approach, a testing module compares a trace of interactions obtained from an execution of the refined specification (e.g., the protocol specification) with the reference specification (e.g., the communication service specification). Nondeterminism in reference specifications presents certain problems. Using an extended finite state transition model for the specifications, a strategy for limiting the amount of nondeterminacy is presented. An automated method for constructing a testing module for a given reference specification is discussed. Experience with the application of this testing approach to the design of a transport protocol and a distributed mutual exclusion algorithm is described.     

带时间约束的UML序列图的分析工具

统一建模语言(UML)是一种多用途的可视化建模语言,它可用于软件系统的规约、可视化的构造和建档.UML序列图描述了交互对象间的协作,如在实时和分布式系统中通讯实体间的信息交互.与其它的规约和设计过程类似,UML序列图的规约也易出错,所以对它进行分析是很有必要的.文章描述了一个对带时间约束的UML序列图进行分析的工具.     

Integrating software specifications into intrusion detection

There exist a number of Intrusion Detection Systems (IDSs) that detect computer attacks based on some defined attack scenarios. The attack scenarios or security requirements in some of these IDSs are specified in attack specification languages that are different from software specification languages. The use of two different languages for software specification and attack specification may generate redundant and conflicting requirements. The advantage of using the same language for both functional specifications and attacks specifications is that software designers can address the two different issues without learning two types of languages. We present a method of integrating Abstract State Machine Language (AsmL) and Unified Modeling Language (UML) state charts that are extended finite state machine based software specification languages, with an open source IDS Snort. This work provides AsmL and UML users an IDS that they can use without knowing how to write Snort rules. We automatically translate attack scenarios written in AsmL and UML state charts into Snort rules with context information. The original Snort is modified so that it can use the rules automatically generated by the translator. Adding context information to Snort rules improves the detection capability of Snort. To show the efficacy of the presented approach, we have built a prototype and evaluated it using a number of well-known attack scenarios.     

Security by typing

We present an approach for analyzing cryptographic protocols that are subject to attack from an active intruder who takes advantage of knowledge of the protocol rules. The approach uses a form of type system in which types are communication steps and typing constraints characterize all the messages available to the intruder. This reduces verification of authentication and secrecy properties to a typing problem in our type system. We present the typing rules, prove soundness of a type inference algorithm, and establish the correctness of the typing rules with respect to the protocol execution and intruder actions. The protocol specifications used in the approach can be automatically extracted from the conventional, informal cryptographic protocol notation commonly found in the literature. To validate the approach, we implement our algorithm in a tool called DYMNA, which is a practical and efficient environment for the specification and analysis of cryptographic protocols.     

基于UML协作图的集成测试序列生成方法

随着软件测试自动化的要求,以及UML在面向对象软件开发领域中的广泛应用,基于UML的面向对象软件测试正日益受到关注。集成测试是面向对象软件测试的一个重要阶段,在基于UML协作图生成面向对象软件的集成测试用例的过程中,一个重要内容是测试序列的生成。针对集成测试序列数量容易膨胀的现象,根据UML协作图的特点,应用过程间受限控制流图(IR-CFG)描述协作图的消息间逻辑控制关系。给出了由RationalRose开发的规格说明文件生成IRCFG的算法,并介绍了IRCFG的几种覆盖准则与基于IRCFG生成测试序列的方法。     

通信协议的实体行为描述语言CPEBSDL

提出了一种通信协议的实体描述语言CPEBSDL.CPEBSDL语言是一种描述能力很强的语言,它可以对协议实体的状态、行为及协议实体对资源的控制和访问进行形式化的描述,同以往的描述语言不同,CPEBSDL语言把协议实体之间复杂的交互行为看做是实体对协议中共同使用到的资源的控制和访问,从而简化了交互行为描述的复杂性,便于对协议进行分析和测试.给出CPEBSDL语言规则对应的上下文无关文法G(CPEBSDL),并给出了G(CPEBSDL)的乔姆斯基范式,在此基础上给出了一个判定协议行为的CPEBSDL语言描述是否合法的判定算法——CYK协议行为序列的合法性验证算法.作为一个实例,用CPEBSDL语言对ISDN数据链路层协议LAPD的链接过程进行了完整的描述,并给出了一个判定协议行为序列是否合法的例子.     

A cyber attack-resilient server inspired by biological diversity

This paper describes a novel cyber attack-resilient server inspired by the concept of biological diversity. The server consists of several virtual machines running different operating systems and different implementations of the same server protocol specification. This approach is based on the observation that not all implementations are affected by the same vulnerability, except for vulnerabilities in specifications and on shared libraries. A prototype system was built and tested to evaluate the continuity of the service. The results showed that, by exploiting a vulnerability, the prototype system could suppress downtime of the DNS service to less than 4 s without false positives.     

基于形式化规格说明的UML状态图提取

为了辅助软件开发者理解形式化规格说明,提出一种从B方法规格说明中提取UML状态图的方法。通过分析状态信息在规格说明中的表现形式,定义一系列精确的简单状态、状态迁移、复合迁移、分层状态和状态图通信等提取规则。借助状态变量表和状态迁移表,最终实现状态元素和状态关系的提取,并以此构造完整的UML状态图。实验结果验证了方法的正确性及有效性。     

A collision problem in OSI standard formal specifications

A collision problem is presented which can occur between two adjacent protocol entities, a user and its local provider. We consider synchronous and asynchronous communication mechanisms at the Service Access Point between the entities; this is normally an implementation choice. It is shown that even if the problem is limited by using a synchronous communication mechanism, instead of an asynchronous one, it still occurs. We suggest that whenever this case is found, the service provided by the protocol entity must be interpreted differently by its user, ignoring some primitives. When an asynchronous communication mechanism is used, care must be taken to verify that those primitives to be ignored cannot be misinterpreted as new primitives; finally, we point out that the protocol specification could be redesigned to handle these collision cases properly.     

Test Synthesis from UML Models of Distributed Software

The object-oriented software development process is increasingly used for the construction of complex distributed systems. In this context, behavior models have long been recognized as the basis for systematic approaches to requirements capture, specification, design, simulation, code generation, testing, and verification. Two complementary approaches for modeling behavior have proven useful in practice: interaction-based modeling (e.g., UML sequence diagrams) and state-based modeling (e.g., UML statecharts). Building on formal V&V techniques, in this article we present a method and a tool for automated synthesis of test cases from scenarios and a state-based design model of the application, remaining entirely within the UML framework. The underlying "on the fly" test synthesis algorithms are based on the input/output labeled transition system formalism, which is particularly appropriate for modeling applications involving asynchronous communication. The method is eminently compatible with classical OO development processes since it can be used to synthesize test cases from the scenarios used in early development stages to model global interactions between actors and components, instead of these test cases being derived manually. We illustrate the system test synthesis process using an air traffic control software example     

Deriving protocol specifications from service specifications written as Predicate/Transition-nets

We consider the derivation of a protocol specification from a service specification written in Predicate/Transition-nets (Pr/T-nets). The service specification describes the global behavior of a system and includes the allocation of the Pr/T-net places to N distributed sites. The paper presents a new algorithm for deriving a protocol specification that defines the behavior of N communicating entities that execute on the N sites and coordinate their actions in order to conform to the global behavior defined by the service specification. Our algorithm decomposes each transition of the service specification into a set of communicating Pr/T-subnets running on the N entities. Moreover, for efficiently controlling the conflict for shared resources, we present a timestamp-based contention control algorithm and incorporate it into the derivation algorithm. A tool has been developed that implements our algorithm and works together with other existing tools for the graphical representation of the service and derived protocol specifications. Two application examples are discussed.     

PSAMS: a communication protocol specification assessment and measurement system

An obstacle to the uses of software metrics and size models, which we have developed for measuring the complexity and maintainability of a communication protocol specified in Estelle and for estimating the size of its specification and implementation, is the time‐consuming effort in collecting the metrics. To address this problem, a software system called PSAMS (protocol specification assessment and measurement system) for automatically calculating the metrics and sizes of specification and implementation has been developed. This paper describes the design of PSAMS, which provides five functionalities for a communication protocol Estelle specification: exploring its specification, measuring its complexity, assessing its maintainability, estimating its specification size and estimating its implementation size. To demonstrate the usefulness of PSAMS, we have applied it to measure the complexity and maintainability of 10 communication protocol Estelle specifications; the measurement results and decision support information provided by each functionality are presented in this paper. With PSAMS, communication protocol designers and developers are able to assess the complexity of a communication protocol early in the specification stage and have information which helps them manage a communication software project better. Copyright © 2002 John Wiley & Sons, Ltd.     

Automatic synthesis of communication controller hardware fromprotocol specifications

Controllers for serial protocols are control-oriented designs that include complex state machines. Manually designing protocol controllers is thus tedious, error prone, and time-consuming. We present a new methodology for the efficient design of communication controller hardware suited for (but not limited to) complex, bit-serial protocols. Our methodology synthesizes controller hardware from a formal high-level specification of the protocol. In this approach, a single run of the synthesis algorithm synthesizes a complete communication architecture from a single protocol specification. The method not only reduces modeling effort but also ensures that both the interacting transaction producer and consumer controllers conform to the initial protocol specification     

Specification of realtime systems using ASTRAL

ASTRAL is a formal specification language for real-time systems. It is intended to support formal software development and, therefore, has been formally defined. The structuring mechanisms in ASTRAL allow one to build modularized specifications of complex systems with layering. A real-time system is modeled by a collection of state machine specifications and a single global specification. This paper discusses the rationale of ASTRAL's design. ASTRAL's specification style is illustrated by discussing a telephony example. Composability of one or more ASTRAL system specifications is also discussed by the introduction of a composition section, which provides the needed information to combine two or more ASTRAL system specifications     

Specification and Verification of Communication Protocols in AFFIRM Using State Transition Models

It is becoming increasingly important that communication protocols be formally specified and verified. This paper describes a particular approach–the state transition model–using a collection of mechanically supported specification and verification tools incorporated in a running system called AFFIRM. Although developed for the specification of abstract data types and the verification of their properties, the formalism embodied in AFFIRM can also express the concepts underlying state transition machines. Such models easily express most of the events occurring in protocol systems, including those of the users, their agent processes, and the communication channels. The paper reviews the basic concepts of state transition models and the AFFIRM formalism and methodology and describes their union. A detailed example, the alternating bit protocol, illustrates varous properties of interest for specification and verification. Other examples explored using this formalism are briefly described and the accumulated experience is discussed.