On the use of a formal requirements engineering language: The Generalized Railroad Crossing Problem

In this paper, we report on the use of theAlbert II requirements specification language through the handling of the Generalized Railroad Crossing case study. This formal language is based on an ontology of concepts used for capturing requirements inherent in real-time, distributed systems. Because of itsnaturalness, the language supports a direct mapping of customers’ informal needs onto formal statements, without having to introduce artificial elements. The language is founded on a formal framework (real-time temporal logic) which supports the reasoning process of the analyst during the elaboration of the specification. Such support for the reasoning is illustrated in the context of a goal-oriented approach adopted for the elaboration of the case study.     

A Computational Framework for Practical Social Reasoning

This article describes a framework for practical social reasoning designed to be used for analysis, specification, and implementation of the social layer of agent reasoning in multiagent systems. Our framework, called the expectation strategy behavior (ESB) framework, is based on (i) using sets of update rules for social beliefs tied to observations (so‐called expectations), (ii) bounding the amount of reasoning to be performed over these rules by defining a reasoning strategy, and (iii) influencing the agent's decision‐making logic by means of behaviors conditioned on the truth status of current and future social beliefs. We introduce the foundations of ESB conceptually and present a formal framework and an actual implementation of a reasoning engine, which is specifically combined with a general (belief–desire–intention‐based) practical reasoning programming system. We illustrate the generality of ESB through select case studies, which show that it is able to represent and implement different typical styles of social reasoning. The broad coverage of existing social reasoning methods, the modularity that derives from its declarative nature, and its focus on practical implementation make ESB a useful tool for building advanced socially reasoning agents.     

Specification of behavioral anti-patterns for the verification of block-structured Collaborative Business Processes

Context: The verification of the control flow of a Collaborative Business Process (CBP) is important when developing cross-organizational systems, since the control flow defines the behavior of the cross-organizational collaboration. Behavioral anti-patterns have been proposed to improve the performance of formal verification methods. However, a systematic approach for the discovery and specification of behavioral anti-patterns of CBPs has not been proposed so far.Objective: The aim of this work is an approach to systematically discover and specify the behavioral anti-patterns of block-structured CBP models.Method: The approach proposes using the metamodel of a CBP language to discover all possible combinations of constructs leading to a problem in the behavior of block-structured CBPs. Each combination is called minimal CBP. The set of all minimal CBPs with behavioral problems defines the unsoundness profile of a CBP language, from which is possible specifying the behavioral anti-patterns of such language.Results: The approach for specification of behavioral anti-patterns was applied to the UP-ColBPIP language. Twelve behavioral anti-patterns were defined, including support to complex control flow such as advanced synchronization, cancellation and exception management, and multiple instances. Anti-patterns were evaluated on a repository of block-structured CBP models and compared with a formal verification method. Results show that the verification based on anti-patterns is as accurate as the formal method, but it clearly improves the performance of the latter.Conclusion: By using the proposed approach, it is possible to systematically specify behavioral anti-patterns for block-structured CBP languages. During the discovery of anti-patterns different formalisms can be used. With this approach, the specification of anti-patterns provides the exact combination of elements that can cause a problem, making error correction and result interpretation easier. Although the proposed approach was defined for the context of CBPs, it could be applied to the context of intra-organizational processes.     

A goal-based framework for contextual requirements modeling and analysis

Requirements engineering (RE) research often ignores or presumes a uniform nature of the context in which the system operates. This assumption is no longer valid in emerging computing paradigms, such as ambient, pervasive and ubiquitous computing, where it is essential to monitor and adapt to an inherently varying context. Besides influencing the software, context may influence stakeholders’ goals and their choices to meet them. In this paper, we propose a goal-oriented RE modeling and reasoning framework for systems operating in varying contexts. We introduce contextual goal models to relate goals and contexts; context analysis to refine contexts and identify ways to verify them; reasoning techniques to derive requirements reflecting the context and users priorities at runtime; and finally, design time reasoning techniques to derive requirements for a system to be developed at minimum cost and valid in all considered contexts. We illustrate and evaluate our approach through a case study about a museum-guide mobile information system.     

Modeling high assurance agent-based Earthquake Management System using formal techniques

Disaster management systems are complex applications due to their distributed and decentralized nature. Various components execute in parallel with high need of coordination with each other. In such applications, interaction and communication issues are difficult to model and implement. In this paper, we have proposed agent-based Earthquake Management System (EMS) which is modeled and analyzed using formal approach. Traditionally, such systems undergo through various transformations starting from requirement models and specification to analysis, design and implementation. A variety of formal approaches are available to specify systems for analyzing their structure and behavior; however, there are certain limitations in using these techniques due to their expressiveness and behavior requirements. We have adopted combination of Pi-calculus and Pi-ADL formal languages to model EMS from analysis to design. The formal approach helps to enhance reliability and flexibility of the system by reducing the redundant information. It reduces chances of errors by explicitly mentioning working flow of information. Additionally, a prototype application is presented as proof of concept in EMS context. We have also evaluated our formal specification by using ArchWare and ABC tools; also, comparison of prototype application with major existing techniques is highlighted.     

Logical foundations for representing object-oriented systems

Abstract

Object-oriented programming languages are designed for computing or simulating the behaviour of interacting objects, but their encapsulated contexts and procedural methods are not well suited to non-procedural techniques in theorem provers, optimizers, and automated design and analysis tools. Logic is the non-procedural system par excellence, but the predicate calculus notation for logic is awkward for representing and reasoning about encapsulated contexts. Conceptual graphs are a graphic system of logic that is better suited to O-O systems. First, they explicitly represent the contexts that are ignored or obscured in predicate calculus. Second, Peirce's rules of inference for reasoning with graphs are explicitly formulated in terms of contexts and the conditions for importing and exporting information from contexts. This article describes the context mechanisms of conceptual graphs, the rules of inference for reasoning with the graphs, and their use as a design language for object-oriented systems.     

Rule acquisition and attribute reduction in real decision formal contexts

Formal Concept Analysis of real set formal contexts is a generalization of classical formal contexts. By dividing the attributes into condition attributes and decision attributes, the notion of real decision formal contexts is introduced. Based on an implication mapping, problems of rule acquisition and attribute reduction of real decision formal contexts are examined. The extraction of “if–then” rules from the real decision formal contexts, and the approach to attribute reduction of the real decision formal contexts are discussed. By the proposed approach, attributes which are non-essential to the maximal s rules or l rules (to be defined later in the text) can be removed. Furthermore, discernibility matrices and discernibility functions for computing the attribute reducts of the real decision formal contexts are constructed to determine all attribute reducts of the real set formal contexts without affecting the results of the acquired maximal s rules or l rules.     

Recent Advances in Real-Time Maude

This paper gives an overview of recent advances in Real-Time Maude. Real-Time Maude extends the Maude rewriting logic tool to support formal specification and analysis of object-based real-time systems. It emphasizes ease and generality of specification and supports a spectrum of analysis methods, including symbolic simulation, unbounded and time-bounded reachability analysis, and LTL model checking. Real-Time Maude can be used to specify and analyze many systems that, due to their unbounded features, such as unbounded data structures or dynamic object and message creation, cannot be modeled by current timed/hybrid automaton-based tools. We illustrate this expressiveness and generality by summarizing two case studies: (i) an advanced scheduling algorithm with unbounded queues; and (ii) a state-of-the-art wireless sensor network algorithm. Finally, we give some (often easily checkable) conditions that ensure that Real-Time Maude's analysis methods are complete, also for dense time, for object-based real-time systems. In practice, our result implies that Real-Time Maude's time-bounded search and model checking of LTL time-bounded formulas are complete decision procedures for a large and useful class of non-Zeno real-time systems that fall outside the scope of systems that can be modeled in decidable fragments of hybrid automata, including the sensor network case study discussed in this paper.     

The Control Layer in Open Mechanized Reasoning Systems: Annotations and Tactics

We are interested in developing a methodology for integrating mechanized reasoning systems such as Theorem Provers, Computer Algebra Systems, and Model Checkers. Our approach is to provide a framework for specifying mechanized reasoning systems and to use specifications as a starting point for integration. We build on the work presented by Giunchigliaet al. (1994) which introduces the notion of Open Mechanized Reasoning Systems (OMRS) as a specification framework for integrating reasoning systems. An OMRS specification consists of three components: the logic component, the control component, and the interaction component. In this paper we focus on the control level. We propose to specify the control component by first adding control knowledge to the data structures representing the logic by means of annotations and then by specifying proof strategies via tactics. To show the adequacy of the approach we present and discuss a structured specification of constraint contextual rewriting as a set of cooperating specialized reasoning modules.     

A survey of languages for specifying dynamics: a knowledgeengineering perspective

A number of formal specification languages for knowledge-based systems has been developed. Characteristics for knowledge-based systems are a complex knowledge base and an inference engine which uses this knowledge to solve a given problem. Specification languages for knowledge-based systems have to cover both aspects. They have to provide the means to specify a complex and large amount of knowledge and they have to provide the means to specify the dynamic reasoning behavior of a knowledge-based system. We focus on the second aspect. For this purpose, we survey existing approaches for specifying dynamic behavior in related areas of research. In fact, we have taken approaches for the specification of information systems (Language for Conceptual Modeling and TROLL), approaches for the specification of database updates and logic programming (Transaction Logic and Dynamic Database Logic) and the generic specification framework of abstract state machines     

Autarkic Computations in Formal Proofs

Formal proofs in mathematics and computer science are being studied because these objects can be verified by a very simple computer program. An important open problem is whether these formal proofs can be generated with an effort not much greater than writing a mathematical paper in, say, LATEX. Modern systems for proof development make the formalization of reasoning relatively easy. However, formalizing computations in such a manner that the results can be used in formal proofs is not immediate. In this paper we show how to obtain formal proofs of statements such as Prime(61) in the context of Peano arithmetic or (x+1)(x+1)=x ²+2x+1 in the context of rings. We hope that the method will help bridge the gap between the efficient systems of computer algebra and the reliable systems of proof development.     

Hybrid

Combining higher-order abstract syntax and (co)-induction in a logical framework is well known to be problematic. We describe the theory and the practice of a tool called Hybrid, within Isabelle/HOL and Coq, which aims to address many of these difficulties. It allows object logics to be represented using higher-order abstract syntax, and reasoned about using tactical theorem proving and principles of (co)induction. Moreover, it is definitional, which guarantees consistency within a classical type theory. The idea is to have a de Bruijn representation of λ-terms providing a definitional layer that allows the user to represent object languages using higher-order abstract syntax, while offering tools for reasoning about them at the higher level. In this paper we describe how to use Hybrid in a multi-level reasoning fashion, similar in spirit to other systems such as Twelf and Abella. By explicitly referencing provability in a middle layer called a specification logic, we solve the problem of reasoning by (co)induction in the presence of non-stratifiable hypothetical judgments, which allow very elegant and succinct specifications of object logic inference rules. We first demonstrate the method on a simple example, formally proving type soundness (subject reduction) for a fragment of a pure functional language, using a minimal intuitionistic logic as the specification logic. We then prove an analogous result for a continuation-machine presentation of the operational semantics of the same language, encoded this time in an ordered linear logic that serves as the specification layer. This example demonstrates the ease with which we can incorporate new specification logics, and also illustrates a significantly more complex object logic whose encoding is elegantly expressed using features of the new specification logic.     

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.     

Towards Monitoring-Oriented Programming: A Paradigm Combining Specification and Implementation

With the explosion of software size, checking conformance of implementation to specification becomes an increasingly important but also hard problem. Current practice based on ad-hoc testing does not provide correctness guarantees, while highly confident traditional formal methods like model checking and theorem proving are still too expensive to become common practice. In this paper we present a paradigm for combining formal specification with implementation, called monitoring-oriented programming (MoP), providing a light-weighted formal method to check conformance of implementation to specification at runtime. System requirements are expressed using formal specifications given as annotations inserted at various user selected places in programs. Efficient monitoring code using the same target language as the implementation is then automatically generated during a pre-compilation stage. The generated code has the same effect as a logical checking of requirements and can be used in any context, in particular to trigger user defined actions, when requirements are violated. Our proposal is language- and logic- independent, and we argue that it smoothly integrates other interesting system development paradigms, such as design by contract and aspect oriented programming. A prototype has been implemented for Java, which currently supports requirements expressed using past time and future time linear temporal logics, as well as extended regular expressions.     

Planning Proofs of Equations in CCS

Most efforts to automate formal verification of communicating systems have centred around finite-state systems (FSSs). However, FSSs are incapable of modelling many practical communicating systems, including a novel class of problems, which we call VIPS. VIPSs are value-passing, infinite-state, parameterised systems. Existing approaches using model checking over FSSs are insufficient for VIPSs. This is due to their inability both to reason with and about domain-specific theories, and to cope with systems having an unbounded or arbitrary state space.We use the Calculus of Communicating Systems (CCS) (Communication and Concurrency. London: Prentice Hall, 1989) to express and specify VIPSs. We take program verification to be proving the program and its intended specification equivalent. We use the laws of CCS to conduct the verification task. This approach allows us to study communicating systems and the data such systems communicate. Automating theorem proving in this context is an extremely difficult task.We provide automated methods for CCS analysis; they are applicable to both FSSs and VIPSs. Adding these methods to the CL ^A M proof planner (Lecture Notes in Artificial Intelligence, Vol. 449, Springer, 1990, pp. 647, 648), we have implemented an automated verification planner capable of dealing with problems that previously required human interaction. This paper describes these methods, gives an account as to why they work, and provides a short summary of experimental results.     

Interval propagation to reason about sets: Definition and implementation of a practical language

Local consistency techniques have been introduced in logic programming in order to extend the application domain of logic programming languages. The existing languages based on these techniques consider arithmetic constraints applied to variables ranging over finite integer domains. This makes difficult a natural and concise modelling as well as an efficient solving of a class of NP-complete combinatorial search problems dealing with sets. To overcome these problems, we propose a solution which consists in extending the notion of integer domains to that of set domains (sets of sets). We specify a set domain by an interval whose lower and upper bounds are known sets, ordered by set inclusion. We define the formal and practical framework of a new constraint logic programming language over set domains, called Conjunto. Conjunto comprises the usual set operation symbols (, , \), and the set inclusion relation (% MathType!MTEF!2!1!+-% feaafiart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn% hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr% 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq-Jc9% vqaqpepm0xbba9pwe9Q8fs0-yqaqpepae9pg0FirpepeKkFr0xfr-x% fr-xb9adbaqaaeaacaGaaiaabeqaamaabaabaaGcbaGaeyOHI0maaa!37EA!\[ \subseteq \]). Set expressions built using the operation symbols are interpreted as relations (s s ₁ = s ₂, ...). In addition, Conjunto provides us with a set of constraints called graduated constraints (e.g. the set cardinality) which map sets onto arithmetic terms. This allows us to handle optimization problems by applying a cost function to the quantifiable, i.e., arithmetic, terms which are associated to set terms. The constraint solving in Conjunto is based on local consistency techniques using interval reasoning which are extended to handle set constraints. The main contribution of this paper concerns the formal definition of the language and its design and implementation as a practical language.     

Coinduction for preordered algebra

We develop a combination, called hidden preordered algebra, between preordered algebra, which is an algebraic framework supporting specification and reasoning about transitions, and hidden algebra, which is the algebraic framework for behavioural specification. This combination arises naturally within the heterogeneous framework of the modern formal specification language CafeOBJ. The novel specification concept arising from this combination, and which constitutes its single unique feature, is that of behavioural transition. We extend the coinduction proof method for behavioural equivalence to coinduction for proving behavioural transitions.     

A Proof Search Specification of the π-Calculus

We present a meta-logic that contains a new quantifier (for encoding “generic judgments”) and inference rules for reasoning within fixed points of a given specification. We then specify the operational semantics and bisimulation relations for the finite π-calculus within this meta-logic. Since we restrict to the finite case, the ability of the meta-logic to reason within fixed points becomes a powerful and complete tool since simple proof search can compute this one fixed point. The quantifier helps with the delicate issues surrounding the scope of variables within π-calculus expressions and their executions (proofs). We shall illustrate several merits of the logical specifications we write: they are natural and declarative; they contain no side conditions concerning names of variables while maintaining a completely formal treatment of such variables; differences between late and open bisimulation relations are easy to see declaratively; and proof search involving the application of inference rules, unification, and backtracking can provide complete proof systems for both one-step transitions and for bisimulation.     

On Closure Under Stuttering

For over a decade, researchers in formal methods have tried to create formalisms that permit natural specification of systems and allow mathematical reasoning about their correctness. The availability of fully automated reasoning tools enables non-experts to use formal methods effectively—their responsibility reduces to specifying the model and expressing the desired properties. Thus, it is essential that these properties be represented in a language that is easy to use, sufficiently expressive and succinct. Linear-time temporal logic (LTL) is a formalism that has been used extensively by researchers for program specification and verification. One of the desired properties of LTL formulas is closure under stuttering. That is, we do not want the interpretation of formulas to change over traces where some states are repeated. This property is important from both practical and theoretical prospectives; all properties which are closed under stuttering can be expressed in LTL_–X—a fragment of LTL without the next operator. However, it is often difficult to express properties in this fragment of LTL. Further, determining whether a given LTL property is closed under stuttering is PSPACE-complete. In this paper, we introduce a notion of edges of LTL formulas and present a formal theory of closure under stuttering. Edges allow natural modelling of systems with events. Our theory enables syntactic reasoning about whether the resulting properties are closed under stuttering. Finally, we apply the theory to the pattern-based approach of specifying temporal formulas.     

Reasoning with advanced policy rules and its application to access control

This paper presents a formal framework to represent and manage advanced policy rules, which incorporate the notions of provision and obligation. Provisions are those conditions that need to be satisfied or actions that must be performed by a user or an agent before a decision is rendered, while obligations are those conditions or actions that must be fulfilled by either the user or agent or by the system itself within a certain period of time after the decision. This paper proposes a specific formalism to express provisions and obligations within a policy and investigates a reasoning mechanism within this framework. A policy decision may be supported by more than one rule-based derivation, each associated with a potentially different set of provisions and obligations (called a global PO set). The reasoning mechanism can derive all the global PO sets for each specific policy decision and facilitates the selection of the best one based on numerical weights assigned to provisions and obligations as well as on semantic relationships among them. The formal results presented in the paper hold for many applications requiring the specification of policies, but this paper illustrates the use of the proposed policy framework in the security domain only.