Software evolution is made difficult by the need to integrate new features with all previously implemented features in the system. We present Spotlight, a prototype editor for software plans that seeks to address this problem by providing the programmer a principled way to separately develop and incrementally integrate independent features.

Automated testing typically uses specifications to drive the generation of test inputs and/or the checking of program outputs. Many software systems have structurally complex inputs that cannot be adequately described using simple formalisms such as context-free grammars. In order to generate such inputs, many automated testing environments require the user to express the structure of the input using an unfamiliar formal notation. This raises the cost of employing automated testing, thereby offsetting the benefits gained. We present yagg (yet another generator-generator), a tool that allows the programmer to specify the input using a syntax very similar to that of LEX and YACC, widely used scanner and parser generators. yagg allows the user to bound the input space using several different techniques, and generates an input generator that systematically enumerates inputs. We evaluate the ease of use and performance of the tool relative to a model checker-based generator used in previous research. Our experiences indicate that yagg generators can be somewhat slower, but that the ease-of-use afforded by the familiar syntax may be attractive to users.

The "oracle problem" is a well-known challenge for software testing. Without some means of automatically computing the correct answer for test cases, testers must instead compute the results by hand, or use a previous version of the software. In this paper, we investigate the feasibility of revealing software faults by augmenting the code with complete, specification-based assertions. Our evaluation method is to (1) develop a formal specification, (2) translate this specification into assertions, (3) inject or identify existing faults, and (4) for each version of the assertion-enhanced system containing a fault, execute it using a set of test inputs and check for assertion violations. Our goal is to determine whether specification-based assertions are a viable method of revealing faults, and to begin to assess the extent to which their cost-effectiveness can be improved. Our evaluation is based on two case studies involving real-world software systems. Our results indicate that specification-based assertions can effectively reveal faults, as long as they adversely affect the program state. We describe techniques that we used for translating high-level specifications into code-level assertions. We also discuss the costs associated with the approach, and potential techniques for reducing these costs.

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.

The contribution of this paper is an experiment that shows the potential value of a combination of selective reverse engineering to formal specifications and bounded exhaustive testing to improve the assurance levels of complex software. A key problem is to scale up test input generation so that meaningful results can be obtained. We present an approach, using Alloy and TestEra for test input generation, which we evaluate by experimental application to the Galileo dynamic fault tree analysis tool.

Modeling and analysis is indispensable in engineering. To be safe and effective, a modeling method requires a language with a validated semantics; feature-rich, easy-to-use, dependable tools; and low engineering costs. Today we lack adequate means to develop such methods. We present a partial solution combining two techniques: formal methods for language design, and package-oriented programming for function and usability at low cost. We have evaluated the approach in an end-to-end experiment. We deployed an existing reliability method to NASA in a package-oriented tool and surveyed engineers to assess its usability. We formally specified, improved, and validated the language. To assess cost, we built a package-based tool for the new language. Our data show that the approach can enable cost-effective deployment of sound methods by effective tools.

Modeling languages and the software tools which support them are essential to engineering. However, as these languages become more sophisticated, it becomes difficult to assure both the validity of their semantic specifications and the dependability of their program implementations. To ameliorate this problem we propose to develop shared semantic domains and corresponding implementations for families of related modeling languages. The idea is to amortize investments at the intermediate level across multiple language definitions and implementations. To assess the practicality of this approach for modeling languages, we applied it to two languages for reliability modeling and analysis. In earlier work, we developed the intermediate semantic domain of failure automata (FA), which we used to formalize the semantics of dynamic fault trees (DFTs). in this paper, we show that a variant of the original FA can serve as a common semantic domain for both DFTs and reliability block diagrams (RBDs). Our experiences suggest that the use of a common semantic domain and a shared analyzer for expressions at this level can ease the task of formalizing and implementing modeling languages, reducing development costs and improving their dependability.

Truly successful models for component-based software development continue to prove elusive. One of the few is the use of operating system, database and similar programs in many systems. We address three related problems in this paper. First, we lack needed models. Second, we do not know the conditions under which such models can succeed. In particular, it is unclear whether the notable success with operating systems can be replicated. Third, we do not know whether certain specific models can succeed. We are addressing these problems by evaluating a particular model that shares important characteristics with the successful operating system example: using compatible PC packages as components. Our approach to evaluating such a model is to engage in a case study that aims to build an industrially successful system representative of an important class of systems. We report on our use of the model to develop a computational tool for reliability engineering. We draw two conclusions. First, this kind of model has the potential to succeed. Second, even today, the model can produce significant returns, but it clearly carries considerable risks.

We present Galileo, an innovative engineering modeling and analysis tool built using an approach we call package-oriented programming (POP). Galileo represents an ongoing evaluation of the POP approach, where multiple large, architecturally coherent components are tightly integrated in an overall software system. Galileo utilizes Microsoft Word, Internet Explorer, and Visio to provide a low cost, richly functional fault tree modeling superstructure. Based on the success of previous prototypes of the tool, we are now building a version for industrial use under an agreement with NASA Langley Research Center.

Computational modeling tools are critical to engineering. In the absence of a sufficiently complete, mathematically precise, abstract specification of the semantics of the modeling framework supported by such a tool, rigorous validation of the framework and of models built using it is impossible; there is no sound basis for program implementation, verification or documentation; the scientific foundation of the framework remains weak; and significant conceptual errors in framework definition and implementation are likely. Yet such specifications are rarely defined. We present an approach based on the use of formal specification and denotational semantics techniques from software engineering and programming language design. To illustrate the approach, we present elements of a formal semantics for a dynamic fault tree framework that promises to aid reliability analysis. No such specification of the meaning of dynamic fault trees has been defined previously. The approach revealed important shortcomings in the previous, informal definitions of the framework, and thus led to significant improvements, suggesting that formally specifying framework semantics is critical to effective framework design.

Sophisticated modeling and analysis methods are being developed in academic and industrial research labs for reliability engineering and other domains. The evaluation and evolution of such methods based on use in practice is critical to research progress, but few such methods see widespread use. A critical impediment to disseminating new methods is the inability to produce, at a reasonable cost, supporting software tools that have the: usability and dependability characteristics that industrial users require; and evolvability to accommodate software change as the underlying analysis methods are refined and enhanced. The difficulty of software development thus emerges as a key impediment to advances in engineering modeling and analysis. This paper presents an approach to tool development that attacks these problems. Progress requires synergistic, interdisciplinary collaborations between application-domain and software-engineering researchers. The authors have pursued such an approach in developing Galileo: a fault tree modeling and analysis tool. These innovations are described in two dimensions: (1) the Galileo core reliability modeling and analysis function; and (2) the authors' work on software engineering for high-quality, low-cost modeling and analysis tools.

Sophisticated dependability analysis techniques are being developed in academia and research labs, but few have gained wide acceptance in industry. To be valuable, such techniques must be supported by usable, dependable software tools. We present our approach to addressing these issues in developing a dynamic fault tree analysis tool called Galileo. Galileo is designed to support efficient system-level analysis by automatically decomposing fault trees into modules that are solved separately using appropriate techniques. Usability is addressed by a software architecture based on a component-based design technique that we call package-oriented programming. We integrate multiple, volume-priced mass-market software packages to provide the bulk of the tool superstructure. To address tool dependability, we are developing natural language and partial formal specifications of fault tree elements, and we exploit the inherent redundancy associated with multiple analysis techniques as an aid in testing.

No abstract available.