Algebraic-grammatical specifications and synthesis of structured program schemas

The paper proposes hierarchical specifications of classes of algorithms and programs (both sequential and parallel) in algebras of hyperschemas (AHS), based on Glushkov's systems of algorithmic algebras. Derivation-control algorithms for various grammatical models are presented in AHS.Translated from Kibernetika, No. 6, pp. 5–16, November–December, 1989.     

On the algebra of structured specifications

We develop module algebra for structured specifications with model oriented denotations. Our work extends the existing theory with specification building operators for non-protecting importation modes and with new algebraic rules (most notably for initial semantics) and upgrades the pushout-style semantics of parameterized modules to capture the (possible) sharing between the body of the parameterized modules and the instances of the parameters. We specify a set of sufficient abstract conditions, smoothly satisfied in the actual situations, and prove the isomorphism between the parallel and the serial instantiation of multiple parameters. Our module algebra development is done at the level of abstract institutions, which means that our results are very general and directly applicable to a wide variety of specification and programming formalisms that are rigorously based upon some logical system.     

On requirement verification for evolving Statecharts specifications

Software development processes have been evolving from rigid, pre-specified, and sequential to incremental, and iterative. This evolution has been dictated by the need to accommodate evolving user requirements and reduce the delay between design decision and feedback from users. Formal verification techniques, however, have largely ignored this evolution and even when they made enormous improvements and found significant uses in practice, like in the case of model checking, they remained confined into the niches of safety-critical systems. Model checking verifies if a system’s model \(\mathcal{M}\) satisfies a set of requirements, formalized as a set of logic properties \(\Phi\) . Current model-checking approaches, however, implicitly rely on the assumption that both the complete model \(\mathcal{M}\) and the whole set of properties \(\Phi\) are fully specified when verification takes place. Very often, however, \(\mathcal{M}\) is subject to change because its development is iterative and its definition evolves through stages of incompleteness, where alternative design decisions are explored, typically to evaluate some quality trade-offs. Evolving systems specifications of this kind ask for novel verification approaches that tolerate incompleteness and support incremental analysis of alternative designs for certain functionalities. This is exactly the focus of this paper, which develops an incremental model-checking approach for evolving Statecharts. Statecharts have been chosen both because they are increasingly used in practice natively support model refinements.     

VVSL: A language for structured VDM specifications

VVSL is a VDM specification language of the British School with modularisation constructs allowing sharing of hidden state variables and parameterisation constructs for structuring specifications, and with constructs for expressing temporal aspects of the concurrent execution of operations which interfere via state variables. The modularisation and parameterisation constructs have been inspired by the kernel design language COLD-K from the ESPRIT project 432: METEOR, and the constructs for expressing temporal aspects by various temporal logics based on linear and discrete time. VVSL is provided with a well-defined semantics by defining a translation to COLD-K extended with constructs which are required for translation of the VVSL constructs for expressing temporal aspects.In this paper, the syntax for the modularisation and parameterisation constructs of VVSL is outlined. Their meaning is informally described by giving an intuitive explanation and by outlining the translation to COLD-K. It is explained in some detail how sharing of hidden state variables is modelled. Examples of the use of the modularisation and parameterisation constructs are also given. These examples are based on a formal definition of the relational data model. With respect to the constructs for expressing temporal aspects, the ideas underlying the use of temporal formulae in VVSL are briefly outlined and a simple example is given.     

On the existence of translations of structured specifications

We provide a set of sufficient conditions for the existence of translations of structured specifications across specification formalisms. The most basic condition is the existence of a translation between the logical systems underlying the specification formalisms, which corresponds to the unstructured situation. Our approach is based upon institution theory and especially upon a recent abstract approach to structured specifications in which both the underlying logics and the structuring systems are treated fully abstractly. Hence our result is applicable to a wide range of actual specification formalisms that may employ different logics as well as different structuring systems, and is very relevant within the context of the fastly developing heterogeneous specification paradigm.     

Unified verification and monitoring of executable UML specifications

Software and Systems Modeling - The increasing complexity of embedded systems renders software verification more complex, requiring monitoring and formal techniques, like model-checking. However,...     

Soundness in verification of algebraic specifications with OBJ

The algebraic specification tools of the OBJ family have no notion of open terms or quantifiers. Nonetheless there are methods of proving universally quantified statements about specifications. These methods are examined and found to be unsound.     

Enhancing structured review with model-based verification

We propose a development framework that extends the scope of structured review by supplementing the structured review with model-based verification. The proposed approach uses the Unified Modeling Language (UML) as a modeling notation. We discuss a set of correctness arguments that can be used in conjunction with formal verification and validation (V&V) in order to improve the quality and dependability of systems in a cost-effective way. Formal methods can be esoteric; consequently, their large scale application is hindered. We propose a framework based on the integration of lightweight formal methods and structured reviews. Moreover, we show that structured reviews enable us to handle aspects of V&V that cannot be fully automated. To demonstrate the feasibility of our approach, we have conducted a study on a security-critical system - a patient document service (PDS) system.     

Template-based program verification and program synthesis

Program verification is the task of automatically generating proofs for a program’s compliance with a given specification. Program synthesis is the task of automatically generating a program that meets a given specification. Both program verification and program synthesis can be viewed as search problems, for proofs and programs, respectively. For these search problems, we present approaches based on user-provided insights in the form of templates. Templates are hints about the syntactic forms of the invariants and programs, and help guide the search for solutions. We show how to reduce the template-based search problem to satisfiability solving, which permits the use of off-the-shelf solvers to efficiently explore the search space. Template-based approaches have allowed us to verify and synthesize programs outside the abilities of previous verifiers and synthesizers. Our approach can verify and synthesize difficult algorithmic textbook programs (e.g., sorting and dynamic programming-based algorithms) and difficult arithmetic programs.     

Synthesizing structured analysis and object‐based formal specifications

Structured Analysis (SA) is a widely‐used software development method. SA specifications are based on Data Flow Diagrams (DFD's), Data Dictionaries (DD's) and Process Specifications (P‐Specs). As used in practice, SA specifications are not formal. Seemingly orthogonal approaches to specifications are those using formal, object‐based, abstract model specification languages, e.g., VDM, Z, Larch/C++ and SPECS. These languages support object‐based software development in that they are designed to specify abstract data types (ADT's). We suggest formalizing SA specifications by: (i) formally specifying flow value types as ADT's in DD's, (ii) formally specifying P‐Specs using both the assertional style of the aforementioned specification languages and ADT operations defined in DD's, and (iii) adopting a formal semantics for DFD “execution steps”. The resulting formalized SA specifications, DFD‐SPECS, are well‐suited to the specification of distributed or concurrent systems. We provide an example DFD‐SPEC for a client‐server system with a replicated server. When synthesized with our recent results in the direct execution of formal, model‐based specifications, DFD‐SPECS will also support the direct execution of specifications of concurrent or distributed systems.     

Development graphs—Proof management for structured specifications

Development graphs are a tool for dealing with structured specifications in a formal program development in order to ease the management of change and reusing proofs. In this work, we extend development graphs with hiding (e.g. hidden operations). Hiding is a particularly difficult to realize operation, since it does not admit such a good decomposition of the involved specifications as other structuring operations do. We develop both a semantics and proof rules for development graphs with hiding. The rules are proven to be sound, and also complete relative to an oracle for conservative extensions. We also show that an absolutely complete set of rules cannot exist.The whole framework is developed in a way independent of the underlying logical system (and thus also does not prescribe the nature of the parts of a specification that may be hidden). We also show how various other logic independent specification formalisms can be mapped into development graphs; thus, development graphs can serve as a kernel formalism for management of proofs and of change.     

Language-Based Program Verification via Expressive Types

Recent developments in the area of expressive types have the prospect to supply the ordinary programmer with a programming language rich enough to verify complex program properties. Program verification is made possible via tractable type checking. We explore this possibility by considering two specific examples; verifying sortedness and resource usage verification. We show that advanced type error diagnosis methods become essential to assist the user in case of type checking failure. Our results point out new research directions for the development of programming environments in which users can write and verify their programs.     

Formal verification of OIL component specifications using mCRL2

International Journal on Software Tools for Technology Transfer - To aid in making software bug-free, several high-tech companies are moving from coding to modelling. In some cases model checking...     

An approach for machine-assisted verification of Timed CSP specifications

The real-time process calculus Timed CSP is capable of expressing properties such as deadlock-freedom and real-time constraints. It is therefore well-suited to model and verify embedded software. However, proofs about Timed CSP specifications are not ensured to be correct since comprehensive machine-assistance for Timed CSP is not yet available. In this paper, we present our formalization of Timed CSP in the Isabelle/HOL theorem prover, which we have formulated as an operational coalgebraic semantics together with bisimulation equivalences and coalgebraic invariants. This allows for semi-automated and mechanically checked proofs about Timed CSP specifications. Mechanically checked proofs enhance confidence in verification because corner cases cannot be overlooked. We additionally apply our formalization to an abstract specification with real-time constraints. This is the basis for our current work, in which we verify a simple real-time operating system deployed on a satellite. As this operating system has to cope with arbitrarily many threads, we use verification techniques from the area of parameterized systems for which we outline their formalization.     

An oversampling approach for mining program specifications

Automatic protocol mining is a promising approach for inferring accurate and complete API protocols. However, just as with any data-mining technique, this approach requires sufficient training data (object usage scenarios). Existing approaches resolve the problem by analyzing more programs, which may cause significant runtime overhead. In this paper, we propose an inheritance-based oversampling approach for object usage scenarios (OUSs). Our technique is based on the inheritance relationship in object-oriented programs. Given an object-oriented program p, generally, the OUSs that can be collected from a run of p are not more than the objects used during the run. With our technique, a maximum of n times more OUSs can be achieved, where n is the average number of super-classes of all general OUSs. To investigate the effect of our technique, we implement it in our previous prototype tool, ISpecMiner, and use the tool to mine protocols from several real-world programs. Experimental results show that our technique can collect 1.95 times more OUSs than general approaches. Additionally, accurate and complete API protocols are more likely to be achieved. Furthermore, our technique can mine API protocols for classes never even used in programs, which are valuable for validating software architectures, program documentation, and understanding. Although our technique will introduce some runtime overhead, it is trivial and acceptable.     

Semantic constraint specification and verification of ebXML business process specifications

Electronic Business using eXtensible Markup Language (ebXML) Business Process Specification Schema (BPSS) supports the specification of the set of elements required to configure a runtime system in order to execute a set of ebXML business transactions. The BPSS is available in two stand-alone representations; a UML version and an XML version. Due to the limitations of UML notations and XML syntax, however, the current ebXML BPSS specification is insufficient to formally specify semantic constraints of modeling elements. In this study, we propose a classification scheme for BPSS semantic constraints, and describe how to represent those semantic constraints formally using Object Constraint Language. As a way to verify a particular Business Process Specification (BPS) with formal semantic constraint modeling, we suggest a rule-based approach to represent the formal semantic constraints, and describe a detail mechanism to apply the rule-based specified constraints to the BPS in a prototype implementation.