基于一致性测试理论的Statechart描述的测试用例自动生成

本文研究Statechart描述的测试语义和测试用例的自动生成.基于Tretmans的从标记转换系统描述自动生成测试用例的方法,我们研究如何从Statechart描述自动生成测试用例.本文的主要贡献在于建立了基于Statechart描述的一致性测试和测试用例生成的形式化基础.为Statechart描述建立了形式化测试语...     

面向访问验证保护级的安全VMM形式化原型系统设计和实现

操作系统是计算机软件系统的基础,具有控制逻辑复杂、安全性和可靠性要求高等特点。在国内外高等级安全操作系统的规范和标准中,都提出了对内核进行形式化规范和验证的要求。近年来国内相关研究机构相继开发了满足GB 17859-1999“强制访问控制级”和“结构化保护级”的安全操作系统原型,但对更高级别的安全操作系统的研发尚属空白。在“面向访问验证保护级安全操作系统”课题的研究中,设计并实现了一个基于Haskell的安全VMM原型系统—CASVisor.CASVisor严格定义了系统的形式化规范,可用于指导高性能的C程序的实现,并为形式化的分析和验证打下基础,同时CASVisor具备模拟功能,以便实施基于快速原型的开发方法。     

Temporal Development Methods for Agent-Based

In this paper we overview one specific approach to the formal development of multi-agent systems. This approach is based on the use of temporal logics to represent both the behaviour of individual agents, and the macro-level behaviour of multi-agent systems. We describe how formal specification, verification and refinement can all be developed using this temporal basis, and how implementation can be achieved by directly executing these formal representations. We also show how the basic framework can be extended in various ways to handle the representation and implementation of agents capable of more complex deliberation and reasoning.This revised version was published online in August 2005 with a corrected cover date.     

Formal verification of Ada programs

The Penelope verification editor and its formal basis are described. Penelope is a prototype system for the interactive development and verification of programs that are written in a rich subset of sequential Ada. Because it generates verification conditions incrementally, Penelope can be used to develop a program and its correctness proof in concert. If an already-verified program is modified, one can attempt to prove the modified version by replaying and modifying the original sequence of proof steps. Verification conditions are generated by predicate transformers whose logical soundness can be proven by establishing a precise formal connection between predicate transformation and denotational definitions in the style of continuation semantics. Penelope's specification language, Larch/Ada, belongs to the family of Larch interface languages. It scales up properly, in the sense that one can demonstrate the soundness of decomposing an implementation hierarchically and reasoning locally about the implementation of each node in the hierarchy     

Business Processes Verification for e-Government Service Delivery

Domain experts knowledge represents a major source of information in the design and the development of user-centric and distributed service-based applications, such as those of e-government. Issues related both to the communication among domain and IT experts, and to the implementation of domain dependent requirements in service-based applications, have to be carefully considered to support both Public Administrations efficiency and citizen satisfaction. In this article, we provide as user-friendly approach toward business process assessment via formal verification. Starting from a semi-formal notation, well understood and largely used by domain experts, we provide a mapping to a formal specification in the form of a process algebra. This transformation makes possible formal and automatic verification of desired quality requirements. The approach has been already applied, with encouraging results, in the e-government domain to verify the quality of business processes related to the delivery of e-government digital services to citizens. Moreover, the approach is supported by a plug-in for the Eclipse platform permitting to have an integrated environment in which to design the process model and to assess its quality.     

Formal specification of concurrent systems

This paper presents a formal methodology for developing concurrent systems. We extend the Larch family of specification languages and tools with the CCS process algebra to support the specification and verification of concurrent systems. We present and follow a refinement strategy that relates an implementation in a programming language to a formal specification of such a system. We illustrate our methodology on an example that uses the preconditioned conjugate gradient method for solving a linear system of equations.     

Hardware-software codesign of embedded systems

Designers generally implement embedded controllers for reactive real-time applications as mixed software-hardware systems. In our formal methodology for specifying, modeling, automatically synthesizing, and verifying such systems, design takes place within a unified framework that prejudices neither hardware nor software implementation. After interactive partitioning, this approach automatically synthesizes the entire design, including hardware-software interfaces. Maintaining a finite-state machine model throughout, it preserves the formal properties of the design. It also allows verification of both specification and implementation, as well as the use of specification refinement through formal verification     

The KeY tool

KeY is a tool that provides facilities for formal specification and verification of programs within a commercial platform for UML based software development. Using the KeY tool, formal methods and object-oriented development techniques are applied in an integrated manner. Formal specification is performed using the Object Constraint Language (OCL), which is part of the UML standard. KeY provides support for the authoring and formal analysis of OCL constraints. The target language of KeY based development is Java Card DL, a proper subset of Java for smart card applications and embedded systems. KeY uses a dynamic logic for Java Card DL to express proof obligations, and provides a state-of-the-art theorem prover for interactive and automated verification. Apart from its integration into UML based software development, a characteristic feature of KeY is that formal specification and verification can be introduced incrementally.     

Comparison of specification decomposition methods in Event-B

Decomposition is an important phase in the design of medium and large-scale systems. Various architectures of software systems and decomposition methods are studied in numerous publications. Presently, formal specifications of software systems are mainly used for experimental purposes; for this reason, their size and complexity are relatively low. As a result, in the development of a nontrivial specification, different approaches to the decomposition should be compared and the most suitable approach should be chosen. In this paper, the experience gained in the deductive verification of the formal specification of the mandatory entity-role model of access and information flows control in Linux (MROSL DP-model) using the formal Event-B method and stepwise refinement technique is analyzed. Two approaches to the refinementbased decomposition of specifications are compared and the sources and features of the complexity of the architecture of the model are investigated.     

A Formal Verification Environment for Railway Signaling System Design

A fundamental problem in the design and development of embedded control systems is the verification of safety requirements. Formal methods, offering a mathematical way to specify and analyze the behavior of a system, together with the related support tools can successfully be applied in the formal proof that a system is safe. However, the complexity of real systems is such that automated tools often fail to formally validate such systems.This paper outlines an experience on formal specification and verification carried out in a pilot project aiming at the validation of a railway computer based interlocking system. Both the specification and the verification phases were carried out in the JACK (Just Another Concurrency Kit) integrated environment. The formal specification of the system was done by means of process algebra terms. The formal verification of the safety requirements was done first by giving a logical specification of such safety requirements, and then by means of model checking algorithms. Abstraction techniques were defined to make the problem of safety requirements validation tractable by the JACK environment.     

Specifying transaction-based information systems with regularexpressions

The work is about the formal specification of transaction-based, interactive information systems. A transaction is a task that the user can execute independently, and the system can be defined as a partially ordered set of transactions. The general framework is the transformational paradigm, based on the classical Waterfall development model (W.W. Royce, 1970). The stages are systems analysis, software specification, design, and implementation. The systems analysis and software specification stages are covered. An informal, transaction-oriented method for systems analysis is proposed. The resulting system specification involves two parts: a high-level specification of each transaction and a formal specification of the system's control flow, i.e., the order of execution of the transactions. The system's control flow is expressed in a formal language describing concurrent regular expressions built on transaction names. At the software specification stage, some operational requirements, such as connect/disconnect transactions and the application of the all-or-nothing principle, are added to the system specification. Then a serial product automaton (SPA) is used to transform the concurrent expression into a single regular expression. This result is proven to be consistent with the system specification     

Deriving complexity information from a formal communication protocol specification

Communication software systems have become very large and complex. Recognizing the complexity of such software systems is a key element in their development activities. Software metrics are useful quantitative indicators for assessing and predicting software quality attributes, like complexity. However, most of existing metrics are extracted from source programs at the implementation phase of the software life cycle. They cannot provide early feedback during the specification phase; and subsequently it is difficult and expensive to make changes to the system, if so indicated by the metrics. It is therefore important to be able to measure system complexity at the specification phase. However, most software specifications are written in natural languages from which metrics information is very hard to extract. In this paper, we describe how complexity information can be derived from a formal communication protocol specification written in Estelle so that it is possible to predict the complexity of its implementation and subsequently its development can be better managed. © 1998 John Wiley & Sons, Ltd.     

Role of data dictionaries in information resource management

The role of information resource dictionary systems (data dictionary systems) is important in two important phases of information resource management:First, information requirements analysis and specification, which is a complex activity requiring data dictionary support: the end result is the specification of an “Enterprise Model,” which embodies the major activities, processes, information flows, organizational constraints, and concepts. This role is examined in detail after analyzing the existing approaches to requirements analysis and specification.Second, information modeling which uses the information in the Enterprise Model to construct a formal implementation independent database specification: several information models and support tools that may aid in transforming the initial requirements into the final logical database design are examined.The metadata — knowledge about both data and processes — contained in the data dictionary can be used to provide views of data for the specialized tools that make up the database design workbench. The role of data dictionary systems in the integration of tools is discussed.     

Analog property checkers: a DDR2 case study

The formal specification component of verification can be exported to simulation through the idea of property checkers. The essence of this approach is the automatic construction of an observer from the specification in the form of a program that can be interfaced with a simulator and alert the user if the property is violated by a simulation trace. Although not complete, this lighter approach to formal verification has been effectively used in software and digital hardware to detect errors. Recently, the idea of property checkers has been extended to analog and mixed-signal systems.     

Experience on knowledge-based software engineering: A logic-based requirements language and its industrial applications

A formal requirements specification language plays an important role in software development. Not only can such language be used for stating requirements specification, but also can be used in many phases of software development life cycle. The FRORL project started from constructing a language with a solid logical foundation and further expanded to research in verification, validation, requirements analysis, debugging, and transformation. Research in this project aided in some industrial applications in which a code generation tool produced software for embedded systems. This article reports the experiences gained from this project and states the value of research in knowledge-based software engineering.     

Software assurance by bounded exhaustive testing

Bounded exhaustive testing (BET) is a verification technique in which software is automatically tested for all valid inputs up to specified size bounds. A particularly interesting case of BET arises in the context of systems that take structurally complex inputs. Early research suggests that the BET approach can reveal faults in small systems with inputs of low structural complexity, but its potential utility for larger systems with more complex input structures remains unclear. We set out to test its utility on one such system. We used Alloy and TestEra to generate inputs to test the Galileo dynamic fault tree analysis tool, for which we already had both a formal specification of the input space and a test oracle. An initial attempt to generate inputs using a straightforward translation of our specification to Alloy did not work well. The generator failed to generate inputs to meaningful bounds. We developed an approach in which we factored the specification, used TestEra to generate abstract inputs based on one factor, and passed the results through a postprocessor that reincorporated information from the second factor. Using this technique, we were able to generate test inputs to meaningful bounds, and the inputs revealed nontrivial faults in the Galileo implementation, our specification, and our oracle. Our results suggest that BET, combined with specification abstraction and factoring techniques, could become a valuable addition to our verification toolkit and that further investigation is warranted.     

Formal interaction specification in public health surveillance systems using pi-calculus

This paper provides formal specification of interactions in typical public health surveillance systems involving healthcare agencies at local, state and federal levels. Although few standards exist for exchange of healthcare information, there is a general lack of formal models of the protocols involved in the interactions between the agencies. The quality of medical care provided is an end result of a well designed choreography of diverse services provided by different healthcare entities. One of the major challenges in this field appears to be explicit formal specification of such interactions. Such formal specification work is the first step leading to both design and verification of important properties of public healthcare systems. pi-calculus is a formal modeling technique for precise specification of semantics in interacting concurrent systems where mobility is involved. Two different configurations of public health surveillance systems are modelled using pi-calculus in this paper.