High-level debugging of distributed systems: The behavioral abstraction approach

Most extant debugging aids force their users to think about errors in programs from a low-level, unit-at-a-time perspective. Such a perspective is inadequate for debugging large complex systems, particularly distributed systems. In this paper, we present a high-level approach to debugging that offers an alternative to the traditional techniques. We describe a language, edl, developed to support this high-level approach to debugging and outline a set of tools that has been constructed to effect this approach. The paper includes an example illustrating the approach and discusses a number of problems encountered while developing these debugging tools.     

Automatic generation of execution tools in a GANDALF environment

The formal definition of a programming language in denotational style is taken as the basis for the automatic generation of its interpreter. The facilities available in GANDALF are exploited to implement and integrate such a generation technique in a GANDALF environment.     

Knowledge-based fault localization in debugging

Fault localization in program debugging is the process of identifying program statements which cause anomalous behavior. We have developed a prototype, knowledge-based model of the fault localization process. Novel features of the model include the integration of prototypic and causal reasoning about faults and a recognition-based mechanism for program abstraction. An explicit division of knowledge from the applications, programming, and language domains facilitate model tuning within as well as across applications domains. We describe model structure and performance for a class of faults associated with master file update programs.     

Design synthesis in VLSI and software engineering

In this paper we present the results of the Working Group on Design Synthesis and Measurement. This group explored the issues that separate and bind software engineering and VLSI design. The issues on which we comment are design views and tradeoff, levels of abstraction and their importance, and design methodologies and their effect on decisions. We also examine the support environments needed to facilitate design in VLSI and software engineering, state-of-the-art of silicon compilation today, and the types of problems that are best suited to silicon compilation.     

Flow: A software development environment using diagrams

The multiuser software development system FLOW uses a diagrammatic language, FLOW-DL, to represent the system under development. Once a module has been keyed in, one of three post-processors is called to generate source code in Pascal, Fortran, or Cobol. A fourth post-processor generates documentation. The system also includes a syntax-directed editor, as well as a software production data base which holds the FLOW-DL source code, interface data relating to the program modules, and control information pertaining to the state of the system under development. The package is portable; a graphics terminal is not required. Versions of the production system have been used for the past 4 years to develop a number of medium-sized software systems.     

Software quality metrics based on interconnectivity

We state a set of criteria that has guided the development of a metric system for measuring the quality of a largescale software product. This metric system uses the flow of information within the system as an index of system interconnectivity. Based on this observed interconnectivity, a variety of software metrics can be defined. The types of software quality features that can be measured by this approach are summarized. The data-flow analysis techniques used to establish the paths of information flow are explained and illustrated. Finally, a means of integrating various metrics and models into a comprehensive software development environment is discussed. This possible integration is explained in terms of the Gandalf system currently under development at Carnegie-Mellon University.     

Programming measurement and estimation in the software engineering laboratory

This paper presents an attempt to examine a set of basic relationships among various software development variables, such as size, effort, project duration, staff size, and productivity. These variables are plotted against each other for 15 Software Engineering Laboratory projects that were developed for NASA/Goddard Space Flight Center by Computer Sciences Corporation. Certain relationships are derived in the form of equations, and these equations are compared with a set derived by Walston and Felix for IBM Federal Systems Division project data. Although the equations do not have the same coefficients, they are seen to have similar exponents. In fact, the Software Engineering Laboratory equations tend to be within one standard error of estimate of the IBM equations.     

A database model of debugging

Debugging a program can be viewed as performing queries and updates on a database that contains program source information as well as the state of the executing program. This approach integrates the facilities of a traditional debugger into a programming environment by providing access to runtime information through normal database query operations. We are building a programming environment in which all program information is stored in a relational database system. This system will include capabilities to provide the programmer a simple yet powerful mechanism for describing debugging requests.     

Software fault tree analysis

With the increased use of software in safety critical systems, software safety has become an important factor in system quality. This paper describes a technique, software fault tree analysis, for the safety analysis of software. The technique interfaces with hardware fault tree analysis to allow the safety of the entire system to be maximized. Experience with the technique and its practicality are discussed.     

Evaluating a data abstraction testing system based on formal specifications

A compiler-based specification and testing system for defining data types has been developed. The system, DAISTS (data abstraction implementation, specification, and testing system) includes formal algebraic specifications and statement and expression test coverage monitors. This paper describes our initial attempt to evaluate the effectiveness of the system in helping users produce software. In an exploratory study, subjects without prior experience with DAISTS were encouraged by the system to develop effective sets of test cases for their implementations. Furthermore, an analysis of the errors remaining in the implementations provided valuable hints about additional useful testing metrics.     

Stepwise refinement revisited

In this paper, rigorous application of stepwise refinement is explored. The steps of definition, decomposition, and completion are described, where completion is a newly introduced step. This combination of steps extends the use of stepwise refinement to larger systems. The notions of range, active objects, and backlog interface are introduced. Verification of incomplete programs via interactive testing is described. The paradigm is demonstrated in an example. The relationship between the paradigm and the current programming languages is considered. It is argued that the WHILE-DO loop is a harmful construct from this point of view.     

Can the Parr curve help with manpower distribution and resource estimation problems?

This paper analyzes the resource utilization curve devel oped by Parr. The curve is compared with several other curves, including the Rayleigh curve, a parabola, and a trapezoid, with respect to how well they fit manpower uti lization. The evaluation is performed for several projects developed in the Software Engineering Laboratory of the 6–12 man-year variety. The conclusion drawn is that the Parr curve can be made to fit the data better than the other curves. However, because of the noise in the data, it is difficult to confirm the shape of the manpower distri bution from the data alone and therefore difficult to vali date any particular model. Also, since the parameters used in the curve are not easily calculable or estimable from known data, the curve is not effective for resource estimation.     

A model of enforcement relationships among database access control dependencies

The various kinds of access decision dependencies within a predicate-based model of database protection are classified according to cost of enforcement. Petri nets and some useful extensions are described. Extended Petri nets are used to model the flow of messages and data during protection enforcement within MULTISAFE, a multimodule system architecture for secure database management. The model demonstrates that some of the stated criteria for security are met within MULTISAFE. Of particular interest is the modeling of data dependent access conditions with predicates at Petri net transitions. Tokens in the net carry the intermodule messages of MULTISAFE. Login, authorization, and database requests are traced through the model as examples. The evaluation of complex access condition predicates is described for the enforcement process. Queues of data and queues of access condition predicates are cycled through the net so that each data record is checked against each predicate. Petri nets are shown to be a useful modeling tool for database security.     

Complexity measures for assembly language programs

This paper presents the results of a study of the software complexity characteristics of a large real-time signal processing system for which there is a 6-yr maintenance history. The objective of the study was to compare values generated by software metrics to the maintenance history in order to determine which software complexity metrics would be most useful for estimating maintenance effort. The metrics that were analyzed were program size measures, software science measures, and control flow measures. During the course of the study two new software metrics were defined. The new metrics, maximum knot depth and knots per jump ratio, are both extensions of the knot count metric. When comparing the metrics to the maintenance data the control flow measures showed the strongest positive correlation.     

Incremental parsing without a parser

This article describes an algorithm for incremental parsing of expressions in the context of syntax-directed editors for programming languages. Since a syntax-directed editor represents programs as trees and statements and expressions as nodes in trees, making minor modifications in an expression can be difficult. Consider, for example, changing a “ + ” operator to a “1” operator or adding a short subexpression at a syntactically but not structurally correct position, such as inserting “) 1 (d“ at the # mark in” (a + b # + c)”. To make these changes in a typical syntax-directed editor, the user must understand the tree structure and type a number of tree-oriented construction and manipulation commands. This article describes an algorithm that allows the user to think in terms of the syntax of the expression as it is displayed on the screen (in infix notation) rather than in terms of its internal representation (which is effectively prefix), while maintaining the benefits of syntax-directed editing. This algorithm is significantly different from other incremental parsing algorithms in that it does not involve modifications to a traditional parsing algorithm or the overhead of maintaining a parser stack or any data structure other than the syntax tree. Instead, the algorithm applies tree transformations, in real-time as each token is inserted or deleted, to maintain a correct syntax tree.     

Modeling and projection in software development

Modeling is a fundamental technique for coping with undesirable complexity in constructing and reasoning about software systems. The concept of modeling can be applied to software design and implementation in two ways: a design can be viewed as an abstract model of the system it represents, and designs and implementations may be represented by even more abstract, simplified models for purposes of analysis. A discussion of these concepts and their applications is presented, including a case study showing the use of modeling in the debugging of an actual software system and remarks on research in progress.