Translating Grafcet specifications into Mealy machines for conformance test purposes

Conformance test is a black-box test technique aiming at checking whether an implementation conforms to its specification. Numerous results have been already obtained in this field for specifications expressed in a formal language. However, these results cannot be applied for conformance test of industrial logic controllers whose specifications are given in standardized specification languages. To contribute to solve this issue, this paper proposes a method to obtain, from a Grafcet specification, an equivalent Mealy machine, without semantics loss. This method permits to describe explicitly and formally all the states and transitions that are implicitly represented in a Grafcet model.     

Live sequence charts applied to hardware requirements specification and verification

Techniques and tools for formally verifying compliance with industry standards are important, especially in System-on-Chip (SoC) designs: a failure to integrate externally developed intellectual property (IP) cores is prohibitively costly. There are three essential components in the practical verification of compliance with a standard. First, an easy-to-read and yet formal specification of the standard is needed; we propose Live Sequence Charts (LSCs) as a high-level visual notation for writing specifications. Second, assertions should be generated directly from the specification; an implementation will be scrutinized, usually by model checking, to check that it satisfies each assertion. Third, a formal link must be made between proofs of assertions and compliance with the original specification. As an example, we take the Virtual Component Interface (VCI) Standard. We compare three efforts in verifying that the same register transfer level code is VCI-compliant. The first two efforts were manual, while the third used a tool, lscAssert, to automatically generate assertions in LTL. We discuss the details of the assertion generation algorithm.     

A toolset for conformance testing against UML sequence diagrams based on event-driven colored Petri nets

Novel techniques and a toolset are presented for automatically testing the conformance of software implementations against partial behavioral models constituted by a set of parameterized UML sequence diagrams, describing both external interactions with users or client applications and internal interactions between objects in the system. Test code is automatically generated from the sequence diagrams and executed on the implementation under test, and test results and coverage information are presented back visually in the model. A runtime test library handles internal interaction checking, test stubs, and user interaction testing, taking advantage of aspect-oriented programming techniques. Incremental conformance checking is achieved by first translating sequence diagrams to Extended Petri Nets that combine the characteristics of Colored Petri Nets and Event-Driven Petri Nets.     

Concurrent runtime monitoring of formally specified programs

A methodology for continuously monitoring a program for specification consistency during program execution is described. Prior development of the formal specification and program is assumed. The program is annotated with constructs from a formal specification language, and the formal specification constructs are transformed into checking code, which is then inserted into the underlying program. Calls to this checking code are inserted into underlying program wherever it can potentially become inconsistent with its specification. If an inconsistency does in fact occur, diagnostic information is provided. The implementation of such a system for Anna (annotated Ada) subtype annotations is presented     

基于形式化监控的可信软件构造模型

传统的形式化方法和软件运行时监控都是提高软件可信性的有效途径,但存在监控需求表达能力不强及代码分散等问题。针对该问题,提出基于形式化监控的可信软件构造技术FM-TSPM,将形式化方法和运行时监控相结合,实现跨领域的方法融合。用形式化方法描述监控约束,根据监控约束生成方面监控代码,解决代码分散问题。采用AOP编织器将方面代码编织到目标系统中,构造出带监控能力的可信软件。     

Automatic analysis of consistency between requirements and designs

Writing requirements in a formal notation permits automatic assessment of such properties as ambiguity, consistency, and completeness. However, verifying that the properties expressed in requirements are preserved in other software life cycle artifacts remains difficult. The existing techniques either require substantial manual effort and skill or suffer from exponential explosion of the number of states in the generated state spaces. “Light-weight” formal methods is an approach to achieve scalability in fully automatic verification by checking an abstraction of the system for only certain properties. We describe light-weight techniques for automatic analysis of consistency between software requirements (expressed in SCR) and detailed designs in low-degree-polynomial time, achieved at the expense of using imprecise data-flow analysis techniques. A specification language SCR describes the systems as state machines with event-driven transitions. We define detailed designs to be consistent with their SCR requirements if they contain exactly the same transitions. We have developed a language for specifying detailed designs, an analysis technique to create a model of a design through data-flow analysis of the language constructs, and a method to automatically generate and check properties derived from requirements to ensure a design's consistency with them. These ideas are implemented in a tool named CORD, which we used to uncover errors in designs of some existing systems     

Translation of Z specifications to executable code: Application to the database domain

ContextIt is well-known that the use of formal methods in the software development process results in high-quality software products. Having specified the software requirements in a formal notation, the question is how they can be transformed into an implementation. There is typically a mismatch between the specification and the implementation, known as the specification-implementation gap.ObjectiveThis paper introduces a set of translation functions to fill the specification-implementation gap in the domain of database applications. We only present the formal definition, not the implementation, of the translation functions.MethodWe chose Z, SQL and Delphi languages to illustrate our methodology. Because the mathematical foundation of Z has many properties in common with SQL, the translation functions from Z to SQL are derived easily. For the translation of Z to Delphi, we extend Delphi libraries to support Z mathematical structures such as sets and tuples. Then, based on these libraries, we derive the translation functions from Z to Delphi. Therefore, we establish a formal relationship between Z specifications and Delphi/SQL code. To prove the soundness of the translation from a Z abstract schema to the Delphi/SQL code, we define a Z design-level schema. We investigate the consistency of the Z abstract schema with the Z design-level schema by using Z refinement rules. Then, by the use of the laws of Morgan refinement calculus, we prove that the Delphi/SQL code refines the Z design-level schema.ResultsThe proposed approach can be used to build the correct prototype of a database application from its specification. This prototype can be evolved, or may be used to validate the software requirements specification against user requirements.ConclusionTherefore, the work presented in this paper reduces the overall cost of the development of database applications because early validation reveals requirement errors sooner in the software development cycle.     

Formal Methods in Designing Embedded Systems—the SACRES Experience

From automotive electronics to avionics, embedded systems are part of our everyday life, and developed societies are increasingly dependent on their reliability in operation. At the same time, current design practice is inadequate in coping with the challenge of constructing dependable embedded systems.SACRES is an experimental design environment aimed at the seamless development of embedded systems. It incorporates state-of-the-art industrial design tools and provides formal specification, model checking technology and validated code generation. These concepts have been integrated on the basis of the synchronous approach to reactive systems.As a result, synchronous compilation techniques have been enhanced, in particular as regards techniques for distributed code generation. Formal verification technology was advanced to increase efficiency, handle composed systems and cover some real-time aspects. The new approach of translation validation was developed and proven to work.Real bugs have been found even in well-tested models. It was demonstrated that a formal design including verification is often more efficient than testing. As a consequence, all user partners are committed to further introducing formal design and verification technology.This paper summarises the essential achievements of the project. It explains the results in terms of the basic ideas, the available tools and methodology, as well as the experience gained.     

Integrating a formal method into a software engineering process with UML and Java

We describe how CSP-OZ, a formal method combining the process algebra CSP with the specification language Object-Z, can be integrated into an object-oriented software engineering process employing the UML as a modelling and Java as an implementation language. The benefit of this integration lies in the rigour of the formal method, which improves the precision of the constructed models and opens up the possibility of (1) verifying properties of models in the early design phases, and (2) checking adherence of implementations to models. The envisaged application area of our approach is the design of distributed reactive systems. To this end, we propose a specific UML profile for reactive systems. The profile contains facilities for modelling components, their interfaces and interconnections via synchronous/broadcast communication, and the overall architecture of a system. The integration with the formal method proceeds by generating a significant part of the CSP-OZ specification from the initially developed UML model. The formal specification is on the one hand the starting point for verifying properties of the model, for instance by using the FDR model checker. On the other hand, it is the basis for generating contracts for the final implementation. Contracts are written in the Java Modeling Language (JML) complemented by CSP_jassda, an assertion language for specifying orderings between method invocations. A set of tools for runtime checking can be used to supervise the adherence of the final Java implementation to the generated contracts. This research was partially supported by the DFG project ForMooS (grants OL 98/3-2 and WE 2290/5-1). C. B. Jones     

Java-MaC: A Run-time Assurance Tool for Java Programs

We describe Java-MaC, a prototype implementation of the Monitoring and Checking (MaC) architecture for Java programs. The MaC architecture provides assurance about the correct execution of target programs at run-time. Monitoring and checking is performed based on a formal specification of system requirements. MaC bridges the gap between formal verification, which ensures the correctness of a design rather than an implementation, and testing, which only partially validates an implementation. Java-MaC provides a lightweight formal method solution as a viable complement to the current heavyweight formal methods. An important aspect of the architecture is the clear separation between monitoring implementation-dependent low-level behaviors and checking high-level behaviors against a formal requirements specification. Another salient feature is automatic instrumentation of executable codes. The paper presents an overview of the MaC architecture and a prototype implementation Java-MaC.     

Computer-aided discovery of formal specification behavioral requirements and requirement to implementation mappings

This paper presents two computer-aided techniques for discovering formal specification behavioral requirements and for mapping components and methods within an implementation to their driving requirements. The first technique is an informal technique while the second technique is formal. The first technique uses a system reference model abstraction and a set of existing formal specifications to discover implementation components that are not well covered by the formal specification set. This technique also provides a mapping between requirements and code segments driven by those requirements. The second technique uses a bounded constraint solver to match a set of tests with a generic formal specification taken from a small library.     

A formal and visual modeling approach to choreography based web services composition and conformance verification

Web services have emerged as the building blocks of a service-oriented architecture that supports not only enterprise application integration (EAI) and business process management (BPM) within an organization but also B2B collaboration based on business process integration. The web services choreography approach to B2B process integration allows business partners to orchestrate their own web services privately, while conforming with an agreed specification of the common ordering conditions and constraints under which messages are exchanged among partners’ web services. In this approach, choreography conformance is an essential requirement for the successful implementation of collaborative processes. A formal approach to web services composition and conformance verification based on WS-CDL and WS-BPEL is presented. This approach involves model checking as an automated means of verifying choreography conformance. The main contributions include a precise notion of choreography conformance on which verification is based as well as support for the complementary use of visual modeling (e.g. UML) and standard WS-¹ notations in composition.     

Formal firewall conformance testing: an application of test and proof techniques

Firewalls are an important means to secure critical ICT infrastructures. As configurable off‐the‐shelf products, the effectiveness of a firewall crucially depends on both the correctness of the implementation itself as well as the correct configuration. While testing the implementation can be done once by the manufacturer, the configuration needs to be tested for each application individually. This is particularly challenging as the configuration, implementing a firewall policy, is inherently complex, hard to understand, administrated by different stakeholders and thus difficult to validate. This paper presents a formal model of both stateless and stateful firewalls (packet filters), including NAT , to which a specification‐based conformance test case generation approach is applied. Furthermore, a verified optimisation technique for this approach is presented: starting from a formal model for stateless firewalls, a collection of semantics‐preserving policy transformation rules and an algorithm that optimizes the specification with respect of the number of test cases required for path coverage of the model are derived. We extend an existing approach that integrates verification and testing, that is, tests and proofs to support conformance testing of network policies. The presented approach is supported by a test framework that allows to test actual firewalls using the test cases generated on the basis of the formal model. Finally, a report on several larger case studies is presented. Copyright © 2014 John Wiley & Sons, Ltd.     

Modelling and validating the man-machine interface

This paper describes a formal model for expressing the functional requirements of the man-machine interfaces of interactive systems. It also shows how this model can facilitate the automation of other useful activities such as checking for inconsistency, redundancy, and incompleteness in the specification, and validating the implementation of the interface against its original requirements. Finally, the paper comments on the authors' experience in developing an interactive system using this formal model.     

Software monitoring through formal specification animation

This paper presents a formal specification-based software monitoring approach that can dynamically and continuously monitor the behaviors of a target system and explicitly recognize undesirable behaviors in the implementation with respect to its formal specification. The key idea of our approach is in building a monitoring module that connects a specification animator with a program debugger. The requirements information about expected dynamic behaviors of the target system are gathered from the formal specification animator, while the actual behaviors of concrete implementations of the target system are obtained through the program debugger. Based on the information obtained from both sides, the judgement on the conformance of the concrete implementation with respect to the formal specification is made timely while the target system is running. Furthermore, the proposed formal specification-based software monitoring technique does not embed any instrumentation codes to the target system nor does it annotate the target system with any formal specifications. It can detect implementation errors in a real-time manner, and help the developers and users of the system to react to the problems before critical failure occurs.     

Specification and design of transactions in information systems: aformal approach

In conventional information systems development, consistency between requirements specifications and design is achieved by manual checking. The application of the transformational paradigm to the specification and design phases is proposed. Requirements are expressed in the ADISSA notation, using the ADISSA method, a transaction-oriented refinement of structured systems analysis. The control part of a transaction is transformed into a formal specification, the FSM (finite state machine) transaction, by applying a set of rules. The design stage is realized by an algorithm which compares the FSM transaction into simpler transactions and implements them with a hierarchical set of finite-state machines. Consistency between the formal specification and the result of the design is achieved by proving that the latter has the same behavior as the former     

Semiautomatic implementation of protocols using an Estelle-Ccompiler

The basic ideas underlying an Estelle-C compiler, which accepts an Estelle protocol specification and produces a protocol implementation in C, are presented. The implementation of the ISO (International Organization for Standardization) class-2 transparent protocol, using the semiautomatic approach, is discussed. A manual implementation of the protocol is performed and compared to the semiautomatic implementation. The semiautomatic approach to protocol implementation offers several advantages over the conventional manual one, including correctness and modularity in protocol implementation code, conformance to the specification, and reduction in implementation time. Finally, ongoing development of a new Estelle-C compiler is presented     

Systems engineering principles for the design of biomedical signal processing systems

Systems engineering aims to produce reliable systems which function according to specification. In this paper we follow a systems engineering approach to design a biomedical signal processing system. We discuss requirements capturing, specification definition, implementation and testing of a classification system. These steps are executed as formal as possible. The requirements, which motivate the system design, are based on diabetes research. The main requirement for the classification system is to be a reliable component of a machine which controls diabetes. Reliability is very important, because uncontrolled diabetes may lead to hyperglycaemia (raised blood sugar) and over a period of time may cause serious damage to many of the body systems, especially the nerves and blood vessels. In a second step, these requirements are refined into a formal CSP‖ B model. The formal model expresses the system functionality in a clear and semantically strong way. Subsequently, the proven system model was translated into an implementation. This implementation was tested with use cases and failure cases.Formal modeling and automated model checking gave us deep insight in the system functionality. This insight enabled us to create a reliable and trustworthy implementation. With extensive tests we established trust in the reliability of the implementation.