An Efficient Modular Method for the Control of Concurrent Discrete Event Systems: A Language-based Approach

In this paper, we are interested in the control of a particular class of Concurrent Discrete Event Systems defined by a collection of components that interact with each other. We investigate the computation of the supremal controllable language contained in the language of the specification. We do not adopt the decentralized approach. Instead, we have chosen to use a modular centralized approach and to perform the control on some approximations of the plant derived from the behavior of each component. The behavior of these approximations is restricted so that they respect a new language property for discrete event systems called partial controllability condition that depends on the specification. It is shown that, under some assumptions, the intersection of these “controlled approximations” corresponds to the supremal controllable language contained in the specification with respect to the plant. This computation is performed without having to build the whole plant, hence avoiding the state space explosion induced by the concurrent nature of the plant. It is finally shown that the class of specifications on which our method can be applied strictly subsumes the class of separable specifications.

User’s manual as a requirements specification: case studies

This paper argues that a users manual makes an excellent software requirements specification. It describes several experiences, including one in industry, of writing users manuals as requirements specifications. Finally, it discusses several lessons learned from the experiences.

Using trust assumptions with security requirements

Assumptions are frequently made during requirements analysis of a system about the trustworthiness of its various components (including human components). These trust assumptions, whether implicit or explicit, affect the scope of the analysis, derivation of security requirements, and in some cases how functionality is realized. This paper presents trust assumptions in the context of analysis of security requirements. A running example shows how trust assumptions can be used by a requirements engineer to help define and limit the scope of analysis and to document the decisions made during the process. The paper concludes with a case study examining the impact of trust assumptions on software that uses the secure electronic transaction specification.

---

Generating relational database transactions from eb 3 attribute definitions

eb ³ is a trace-based formal language created for the specification of information systems. In eb ³, each entity and association attribute is independently defined by a recursive function on the valid traces of external events. This paper describes an algorithm that generates, for each external event, a transaction that updates the value of affected attributes in their relational database representation. The benefits are twofold: eb ³ attribute specifications are automatically translated into executable programs, eliminating system design and implementation steps; the construction of information systems is streamlined, because eb ³ specifications are simpler and shorter to write than corresponding traditional specifications, design and implementations. In particular, the paper shows that simple eb ³ constructs can replace complex SQL queries which are typically difficult to write.

Modeling and verification of a telecommunication application using live sequence charts and the Play-Engine tool

We apply the scenario-based approach to modeling, via the language of live sequence charts (LSCs) and the Play-Engine tool to a real-world complex telecommunication service, . It allows a user to call for help from a doctor, the fire brigade, a car maintenance service, etc. These kinds of services are built on top of an embedded platform, using both new and existing service components, and their complexity stems from their distributed architecture, the various time constraints they entail, and their rapidly evolving underlying systems. A well known problem in this class of telecommunication applications is that of feature interaction, whereby a new feature might cause problems in the execution of existing features. Our approach provides a methodology for high-level modeling of telecommunication applications that can help in detecting feature interaction at early development stages. We exhibit the results of applying the methodology to the specification, animation and formal verification of the Depannage service.

Specification and analysis of the AER/NCA active network protocol suite in Real-Time Maude

This paper describes the application of the Real-Time Maude tool and the Maude formal methodology to the specification and analysis of the AER/NCA suite of active network multicast protocol components. Because of the time-sensitive and resource-sensitive behavior, the presence of probabilistic algorithms, and the composability of its components, AER/NCA poses challenging new problems for its formal specification and analysis. Real-Time Maude is a natural extension of the Maude rewriting logic language and tool for the specification and analysis of real-time object-based distributed systems. It supports a wide spectrum of formal methods, including: executable specification; symbolic simulation; breadth-first search for failures of safety properties in infinite-state systems; and linear temporal logic model checking of time-bounded temporal logic formulas. These methods complement those offered by network simulators on the one hand, and timed-automaton-based tools and general-purpose theorem provers on the other. Our experience shows that Real-Time Maude is well-suited to meet the AER/NCA modeling challenges, and that its methods have proved effective in uncovering subtle and important errors in the informal use case specification.

Methods for quantitative usability requirements: a case study on the development of the user interface of a mobile phone

Quantitative usability requirements are a critical but challenging, and hence an often neglected aspect of a usability engineering process. A case study is described where quantitative usability requirements played a key role in the development of a new user interface of a mobile phone. Within the practical constraints of the project, existing methods for determining usability requirements and evaluating the extent to which these are met, could not be applied as such, therefore tailored methods had to be developed. These methods and their applications are discussed.

---

Methodologies to evolve formal specifications through refinement and retrenchment in an analysis–revision cycle

The development of requirement specifications is done by accumulating knowledge about the desired systems in a progressive manner. This process can be supported by an analysis–revision cycle, in which the analysis phase checks the correctness of a given specification, and the revision phase modifies it, in case some problems are detected. To date, the analysis and revision activities have been typically considered in isolation, resulting in ineffective support to the stakeholders’ work. In response to that, this article introduces methodologies to conduct an interactive and integrated approach, grounded on the formalization of two basic types of evolutions (refinements and retrenchments) over multi-valued specification and modeling formalisms. Evaluation results are included to show that this approach can indeed help the stakeholders identify and clarify requirements through different stages of development.

Analyzing Security Protocols Using Time-Bounded Task-PIOAs

This paper presents the time-bounded task-PIOA modeling framework, an extension of the probabilistic input/output automata (PIOA) framework that can be used for modeling and verifying security protocols. Time-bounded task-PIOAs can describe probabilistic and nondeterministic behavior, as well as time-bounded computation. Together, these features support modeling of important aspects of security protocols, including secrecy requirements and limitations on the computational power of adversarial parties. They also support security protocol verification using methods that are compatible with less formal approaches used in the computational cryptography research community. We illustrate the use of our framework by outlining a proof of functional correctness and security properties for a well-known oblivious transfer protocol.

Lexical systems: graph models of natural language lexicons

We introduce a new type of lexical structure called lexical system, an interoperable model that can feed both monolingual and multilingual language resources. We begin with a formal characterization of lexical systems as simple directed graphs, solely made up of nodes corresponding to lexical entities and links. To illustrate our approach, we present data borrowed from a lexical system that has been generated from the French DiCo database. We later explain how the compilation of the original dictionary-like database into a net-like one has been made possible. Finally, we discuss the potential of the proposed lexical structure for designing multilingual lexical resources.

Interacting with mobile services: an evaluation of camera-phones and visual tags

We present a study of using camera-phones and visual-tags to access mobile services. Firstly, a user-experience study is described in which participants were both observed learning to interact with a prototype mobile service and interviewed about their experiences. Secondly, a pointing-device task is presented in which quantitative data was gathered regarding the speed and accuracy with which participants aimed and clicked on visual-tags using camera-phones. We found that participants’ attitudes to visual-tag-based applications were broadly positive, although they had several important reservations about camera-phone technology more generally. Data from our pointing-device task demonstrated that novice users were able to aim and click on visual-tags quickly (well under 3 s per pointing-device trial on average) and accurately (almost all meeting our defined speed/accuracy tradeoff of 6% error-rate). Based on our findings, design lessons for camera-phone and visual-tag applications are presented.

---

The 2007 IEEE CEC simulated car racing competition

This paper describes the simulated car racing competition that was arranged as part of the 2007 IEEE Congress on Evolutionary Computation. Both the game that was used as the domain for the competition, the controllers submitted as entries to the competition and its results are presented. With this paper, we hope to provide some insight into the efficacy of various computational intelligence methods on a well-defined game task, as well as an example of one way of running a competition. In the process, we provide a set of reference results for those who wish to use the simplerace game to benchmark their own algorithms. The paper is co-authored by the organizers and participants of the competition.

---

Coverage metrics for temporal logic model checking*

In formal verification, we verify that a system is correct with respect to a specification. Even when the system is proved to be correct, there is still a question of how complete the specification is, and whether it really covers all the behaviors of the system. In this paper we study coverage metrics for model checking. Coverage metrics are based on modifications we apply to the system in order to check which parts of it were actually relevant for the verification process to succeed. We introduce two principles that we believe should be part of any coverage metric for model checking: a distinction between state-based and logic-based coverage, and a distinction between the system and its environment. We suggest several coverage metrics that apply these principles, and we describe two algorithms for finding the non-covered parts of the system under these definitions. The first algorithm is a symbolic implementation of a naive algorithm that model checks many variants of the original system. The second algorithm improves the naive algorithm by exploiting overlaps in the variants. We also suggest a few helpful outputs to the user, once the non-covered parts are found.

Experience of using a lightweight formal specification method for a commercial embedded system product line

A simple specification method is introduced and the results of its application to a series of projects in Philips are reported. The method is principally designed to ensure that that every unusual scenario is considered in a systematic way. In practice, this has led to high-quality specifications and accelerated product development. While the straightforward tabular notation used has proved readily understandable to non-technical personnel, it is also a formal method, producing a model of system behaviour as a finite state machine. In this respect, the notation is unusual in being designed to preserve as far as possible a view of the overall system state and how this changes. The notation also features a constraint table which may be described as a kind of spreadsheet for invariants to help define the states of the system.

Inferring specifications to detect errors in code

A new technique is presented to statically check a given procedure against a user-provided property. The method requires no annotations; it automatically infers a context-dependent specification for each procedure call, so that only as much information about a procedure is used as is needed to analyze its caller. Specifications are inferred iteratively. Empty specifications are initially used to over-approximate the effects of all procedure calls; these are later refined in response to spurious counterexamples. When the analysis terminates, any remaining counterexample is guaranteed to be valid. However, since the heap is finitized, the absence of a counterexample does not guarantee the validity of the given property in general.