Search

A software product is typically “upgraded” many times over its lifetime. Reactive systems are no exception, undergoing evolutionary version changes to add features and fix bugs. Evolving these stateful systems, such as email clients, software agents, smart cell phones, and personal digital assistants, is complicated by the fact that new versions of the software must deal correctly with legacy instances. Users of earlier versions have invested significant resources in creating the state of the legacy instance, and usually require that this state be upgraded appropriately when the new system version is activated. However, validating the correctness of this upgrading behavior is particularly difficult, whether through testing or automated reasoning techniques like theorem proving or model checking, because legacy states are typically unreachable to the new version of the software. This paper explores this problem and requirements for its solution. It then presents a simple and widely applicable upgrade framework, based upon the idea of a supermodel that allows upgrade behavior to be validated using mainstream approaches. Finally, it also gives techniques for simplifying the validation problem.

With a few exceptions, previous formal methods for reactive system analysis have focused on finite state machines represented in terms of boolean states and boolean next-state functions. By contrast, in many reactive system domains requirements engineers and developers think in terms of complex data types and expressive next-state functions. Formal methods for reactive system design must be extended to meet their needs as well. I term a reactive system i>function rich if expressing its state, next-state function, or output function naturally requires this higher expressive power. ISAT, a prototype formal-methods based tool environment, is intended to assist in the creation and validation of function rich reactive systems. This paper describes a case study I have carried out using ISAT to design, validate, synthesize, and evolve controllers for the email agent components making up a novel spam-free email system that I deployed in a user trial in July 1999. The trial has been running since, with high availability, through several evolutionary specification changes and resulting software releases. The case study illustrates the use of a mix of validation techniques, from scenario simulation and coverage through static analysis and theorem proving, and discusses the value each technique adds. In addition to summarizing ISAT and the trial, this paper discusses tool requirements placed by the domain and task, the simple and powerful platform/controller/pure-functions software architecture of the components, and lessons learned.

Real-time systems are becoming increasingly widespread, often in safety-critical applications. It is therefore crucial that these systems be corrects however, there are few automated tools for analyzing concurrency and timing properties of these systems. The PARTS toolset uses a Petri-net-based reachability analysis to analyze program specifications written in an Ada-83 subset. Our i>simple time Petri nets are specifically aimed at facilitating real-time analysis. In order to control the state-explosion problem, PARTS employs several optimization techniques aimed at state-space reduction. In this paper we discuss our approach and we report on extensive experiments with several examples of real-time specifications based on Ada 83. When possible, we also compare our experimental results with results obtained by other approaches to real-time analysis.

Reactive systems control many useful and complex real-world devices. Tool-supported specification modelling helps software engineers design such systems correctly. One such tool is a scenario generator, which constructs an input event sequence for the spec model that reaches a state satisfying given criteria. It can uncover counterexamples to desired safety properties, explain feature interactions in concrete terms to requirements analysts, and even provide online help to end users learning how to use a system. However, while exhaustive search algorithms work in limited domains, the problem is highly intractable for the functionally rich models that correspond naturally to complex systems engineers wish to design. This paper describes a novel heuristic approach to the problem that is applicable to a large class of infinite state reactive systems. The key idea is to piece together scenarios that achieve subgoals into a single scenario achieving the conjunction of the subgoals. The scenarios are mined from a library captured independently during requirements acquisition. Explanation-based generalization then abstracts them so they may be coinstantiated and interleaved. The approach is implemented, and I present the results of applying the tool to tasks arising from a case study of telephony feature interactions.

Validating the specification of a reactive system, such as a telephone switching system, traffic controller, or automated network service, is difficult, primarily because it is extremely hard even tostate a set of complete and correct requirements, let alone toprove that a specification satisfies them. In the ISAT project[10], end-user requirements are stated as concrete behavior scenarios, and a multi-functional apprentice system aids the human developer in acquiring and maintaining a specification consistent with the scenarios. ISAT's Validation Assistant (isat-va) embodies a novel, systematic, and incremental approach to validation based on the novel technique ofsound scenario generalization, which automatically states and proves validation lemmas. This technique enablesisat-va to organize the validity proof around a novel knowledge structure, thelibrary of generalized fragments, and provides automated progress tracking and semi-automated help in increasing proof coverage. The approach combines the advantages of software testing and automated theorem proving of formal requirements, avoiding most of their shortcomings, while providing unique advantages of its own.