Search

For the development of communications software com- posed of many modules, protocol validation is essential to detect errors in the interactions among the modules. A number of protocol validation techniques were proposed in the past, but the validation time required by these techniques is too long for many actual protocols. This paper proposes a new fast protocol validation technique to overcome this drawback. The proposed technique is to construct the minimum acyclic form of state transitions in individual processes of the protocol, and to detect protocol errors such as system deadlocks and channel overflows fast. This paper also presents a protocol validation system based on the proposed technique to confirm its feasibility and shows validation results for some actual protocols obtained with this system. As a result, the protocol validation system is expected to contribute to a great extent to the improvement of the productivity in development and maintenance of communications software. [ABSTRACT FROM AUTHOR]

It is being recognized that recent programming environments have made significant progress towards improving the programming process. In adhering to this goal of software engineering, this paper introduces a new basis for programming environments. This basis encourages development of software in fragments of various types, called fragtypes. Fragtypes range from a simple expression type to a complete subsystem type. As a result, they are suited to the development of software in an enlarged scope that includes both programming in the small and programming in the large; The paper shows how new proposed operations on fragtypes can achieve unusual effects on the software development process. Fragtypes and their associated construction rules form the basis of the programming environment MUPE- 2, which is currently under development at McGill University. The target and the implementation language of this environment is the programming language Modula-2. [ABSTRACT FROM AUTHOR]

Composite objects are descriptions of assemblies of parts which themselves can be assemblies of other parts. Efficient storage and retrieval of composite objects is essential for computer aided design applications of database management systems. This paper introduces a clustering concept called component aggregation which considers assemblies having the same types of parts as equivalent objects. The notion of equivalent objects is used to develop a mathematical model of composite objects. It is shown that the set of equivalence classes of objects form a Boolean algebra whose minterms represent the objects which are not considered composite at the current viewing level. The algebraic structure of composite objects serves as a basis for developing a technique for organizing composite objects and supporting materialization of explosion views. The technique provides a clubstering mechanism which partitions the database into meaningful and application-oriented clusters, and allows any desired explosion view to be materialized using a minimal set of stored views. A simplified relational database for design data, and a set of frequent access patterns in design applications are outlined and used to demonstrate the benefits of database organization based on the mathematical model of composite objects. [ABSTRACT FROM AUTHOR]

The formalism of temporal logic has been suggested to be an appropriate tool for expressing the semantics of concurrent programs. This paper is concerned with the application of temporal logic to the specification of factors affecting the synchronization of concurrent processes. Towards this end, we first introduce a model for synchronization and axiomatize its behavior. SYSL, a very high-level language for specifying synchronization properties, is then described. It is designed using the primitives of temporal logic and features constructs to express properties that affect synchronization in a fairly natural and modular fashion. Since the statements in the language have intuitive interpretations, specifications are humanly readable. In addition, since they possess appropriate formal semantics, unambiguous specifications result. [ABSTRACT FROM AUTHOR]

Many modern software systems are designed to be highly configurable so they can run on and be optimized for a wide variety of platforms and usage scenarios. Testing such systems is difficult because, in effect, you are testing a multitude of systems, not just one. Moreover, bugs can and do appear in some configurations, but not in others. Our research focuses on a subset of these bugs that are "option-related"--those that manifest with high probability only when specific configuration options take on specific settings. Our goal is not only to detect these bugs, but also to automatically characterize the configuration subspaces (i.e., the options and their settings) in which they manifest. To improve efficiency, our process tests only a sample of the configuration space, which we obtain from mathematical objects called covering arrays. This paper compares two different kinds of covering arrays for this purpose and assesses the effect of sampling strategy on fault characterization accuracy. Our results strongly suggest that sampling via covering arrays allows us to characterize option-related failures nearly as well as if we had tested exhaustively, but at a much lower cost. We also provide guidelines for using our approach in practice. [ABSTRACT FROM AUTHOR]

The concept of multiway rendezvous has been proposed to implement synchronous communication among an arbitrary number of concurrent, asynchronous processes. The synchronization and exclusion problems associated with implementing multiway rendezvous are expressed succinctly in the context of the committee coordination problem. A variety of techniques to solve the synchronization and exclusion problems may be combined to design algorithms for the committee coordination problem. This paper presents a simple solution for the problem and shows how it can be implemented to develop a family of algorithms. The algorithms use message counts to solve synchronization and solve the exclusion problem by using a circulating token, or by using auxiliary resources as in the solutions for the dining or drinking philosophers problems. The paper also presents the results of a simulation study on the performance of the algorithms. The experiments measured the response time and message complexity of each algorithm as a result of variations in different model parameters including network topology and level of conflict in the system. The results from the study show that the response time for algorithms proposed in this paper is significantly better than an existing algorithm, whereas the message complexity is considerably worse. [ABSTRACT FROM AUTHOR]

Commercially available database systems do not meet the information and processing needs of design and manufacturing environments. A new generation of systems-engineering Information systems-must be built to meet these needs. In this paper, we address the architectural and computational aspects of such systems and propose solutions. We argue that a mainframe-workstation architecture is needed to provide distributed functionality while ensuring high availability and low communication overhead, that explicit control of meta-knowledge is needed to support extendibility and evolution, that large rule bases are needed to make the knowledge of the systems active, and that incremental computation models are needed to achieve the required performance of such engineering information systems. [ABSTRACT FROM AUTHOR]

Diagrams play a central role in software engineering. They are used for specifying design elements such as requirements, concurrent systems, database models and interactive systems. Families of diagrams form visual languages, and creating such diagrams constitutes visual programming. The Visual Programmer's WorkBench (VPW) addresses the rapid synthesis of programming environments for the specification, analysis, and execution of visual programs. A language-based environment for a specific visual language is generated in VPW from a specification of the syntactic structure, the abstract structure, the static semantics and the dynamic semantics of the language. VPW is built around a model of distributed processing based on shared distributed memory. This framework is used both in defining the architecture of the environment and for the execution model of visual languages. The Visual Programmer's WorkBench has been used to experiment with visual programming environments for several visual languages. This paper describes the design of the Visual Programmer's WorkBench and our experience using it to generate a distributed programming environment for a concurrent visual language. [ABSTRACT FROM AUTHOR]

While validation of user requirements has become an important goal for information system designers, very little empirical research has been done in this area. Many methodologies have been presented as the best procedures for achieving user validation of design. This paper looks at four of these methodologies in four different experimental settings. In the four experiments the following treatments were examined: HIPO versus system flowcharts, DFD versus narrative, DFD versus Warnier-Orr diagrams, and DFD versus HIPO. The main result of all four experiments was that choice of design methodology had no effect on the level of user understanding of system requirements. [ABSTRACT FROM AUTHOR]

This paper presents a new interactive synthesis algorithm to construct two communicating finite-state machines (protocols), which exchange message over two unidirectional FIFO channels when the function of the protocol has been given. The synthesis algorithm first constructs the global state transition graph (GSTG) of a protocol to be synthesized and then produces the protocol. It is based on a set of production rules and a set of deadlock avoidance rules, which guarantee that complete reception and deadlock freeness capabilities are provided in the interacting processes. This synthesis algorithm prevents a designer from creating unspecified reception and nonexecutable transition, avoids the occurrence of deadlocks, monitors for the presence of buffer overflow, although it does not help the designer synthesize a protocol to achieve some particular functionality. [ABSTRACT FROM AUTHOR]

A method for formal description of programming principles is presented in this paper. Programming principles, such as sequential search can be defined and proven even in the absence of an application. We represent a principle as a program scheme which has partially interpreted functions in it. The functions must obey certain input constraints. Use of these ideas in program proving is illustrated with examples. [ABSTRACT FROM AUTHOR]

In order to effectively optimize complex programs built in a layered or recursive fashion (possibly from reused general components), the programmer has a critical need for performance information connected directly to the design decisions and other optimization opportunities present in the code. Call path refinement profiles are novel tools for guiding the optimization of such programs, that: 1) provide detailed performance information about arbitrarily nested (direct or indirect) function call sequences, and 2) focus the user's attention on performance bottlenecks by limiting and aggregating the information presented. This paper discusses the motivation for such profiles, describes in detail their implementation in the CPPROF profiler, and relates them to previous profilers, showing how most widely available profilers can be expressed simply and efficiently in terms of call path refinements. [ABSTRACT FROM AUTHOR]

This paper studies practical reliability measurement and modeling for large commercial software systems based on test execution data collected during system testing. The application environment and the goals of reliability assessment were analyzed to identify appropriate measurement data. Various reliability growth models were used on failure data normalized by test case executions to track testing progress and provide reliability assessment. Practical problems in data collection, reliability measurement and modeling, and modeling result analysis were also examined. The results demonstrated the feasibility of reliability measurement in a large commercial software development environment and provided a practical comparison of various reliability measurements and models under such an environment. [ABSTRACT FROM AUTHOR]

We present a programming language called TCEL (Time-Constrained Event Language), whose semantics are based on time-constrained relationships between observable events. Such a semantics infers only those timing constraints necessary to achieve real-time correctness, without overconstraining the system. Moreover, an optimizing compiler can exploit this looser semantics to help tune the code, so that its worst-case execution time is consistent with its real-time requirements. In this paper we describe such a transformation system, which work$ in two phases. First, the TCEL source code is translated into an intermediate representation. Then an instruction- scheduling algorithm rearranges selected unobservable operations and synthesizes tasks guaranteed to respect the original event- based constraints. [ABSTRACT FROM AUTHOR]

This paper describes the knowledge representation and reasoning strategies in an automatic program synthesis architecture called ELF. ELF synthesizes CAD tools that automatically mute wires in VLSI circuits. The design space ELF confronts requires it to understand various physical technologies, to select an appropriate procedure-level decomposition, to choose algorithms and data structures, to manage any interdependencies, and to generate efficient code. ELF manages the design space using a variety of knowledge sources, including domain-specific knowledge. The manner in which knowledge is used determines the representation method of choice. For example, ELF uses languages to describe knowledge that is subject to modification, rules for cause-and-effect knowledge, and graphs and templates to capture knowledge interdependencies. We illustrate the effectiveness of our ideas via a tour through the synthesis steps for a specific routing tool, and a brief discussion of the performance of the resulting synthetic router as measured against an industrial tool. [ABSTRACT FROM AUTHOR]

The paper proposes a comprehensive framework for representing and using nonfunctional requirements during the development process. The framework consists of five basic components which provide for the representation of nonfunctional requirements in terms of interrelated goals. Such goals can be refined through refinement methods and can be evaluated in order to determine the degree to which a set of nonfunctional requirements is supported by a particular design. Evidence for the power of the framework is provided through the study of accuracy and performance requirements for information systems. [ABSTRACT FROM AUTHOR]

This paper presents an environment and a methodology for the design and rapid prototyping of data-intensive software applications; i.e., applications which perform substantial retrieval and update activity on persistent data. In the proposed approach, the application is formally specified using Logres, a database language which combines object-oriented data modeling and rule-based programming. These specifications are translated into Algres, an extended relational algebra, thus yielding a rapid executable prototype. Finally, Algres programs embedded into a conventional programming language interface may be converted to conventional programs operating on a commercial relational system. This methodology helps automate the conversion from declarative requirements to imperative code, performing several tasks fully automatically and reducing the probability of human errors, while integrity constraints and application specifications are expressed in a declarative language, at a very high level of abstraction. [ABSTRACT FROM AUTHOR]

This paper summarizes our experience in the Programmer's Apprentice project in applying knowledge representation and automated reasoning to support software development. We describe a system, called Cake, that comprises seven layers of knowledge representation and reasoning facilities: truth maintenance, Boolean constraint propagation, equality, types, algebra, frames, and Plan Calculus. We also include sessions with two experimental software development tools implemented using Cake: the Requirements Apprentice and the Debugging Assistant. [ABSTRACT FROM AUTHOR]

Requirements modeling depends on having available the knowledge of what should be modeled. Acquiring, or eliciting, this knowledge is recognized to be a hard problem, and different suggestions have been made to address it. In this paper we examine one such approach-viewpoint resolution. It is based on the fact that software requirements can and should be elicited from different viewpoints, and that examination of the differences resulting from them can be used as a Way of assisting in the early validation of requirements. Our research proposes a language for expressing views from different viewpoints and a set of analogy heuristics to perform a syntacticly oriented analysis of views. This analysis of views is capable of differentiating between missing information and conflicting information, thus providing support for viewpoint resolution. We also present empirical evidence Of the effectiveness of these mechanisms. [ABSTRACT FROM AUTHOR]

The hypergeometric distribution model has been proposed for estimating the number of faults initially resident in a program at the beginning of test/debugging process. However, the parameter values of the hypergeometric distribution necessary for making the estimation were previously determined by the three-dimensional exhaustive search and therefore much time was needed to get the numerical result. In this paper, six ways to estimate parameters of the hypergeometric distribution are investigated and their accuracies are examined comparatively. It is demonstrated that the least-squares sum method is the best one among those we tried and can be well applied to real test/debug data for estimating the number of faults still resident in a program after test/debugging. By this method the estimation time can be reduced greatly. [ABSTRACT FROM AUTHOR]

Data structure diagrams are two-dimensional figures made up of lines that aim to pictorially indicate the interrelationships of the elements of a data structure. This paper collects the various rules and factors of aesthetics that go into the way we draw data structure diagrams. We formulate the various subjective factors into computable objectives and numeric parameters. These are distilled from a large number of data structure drawings as found in various textbooks. We reveal that the rules used have not reached a level of acceptance compared to the relevant rules in engineering graphics. We also outline the internal architecture of a (sub)system that we are building that helps draw data structure diagrams. [ABSTRACT FROM AUTHOR]

While the benefits of modular software development are widely acknowledged, there is little agreement as to what constitutes a good module interface. Computational complexity techniques allow us to evaluate algorithm time and space costs but offer no guidance in the design of the interface to an implementation. Yet, interface design decisions often have a critical effect on the development and maintenance costs of large software systems. In this paper we present criteria that have led us to simple, elegant interfaces. These criteria have been developed and refined through repeated practical application. We present the criteria in detail and illustrate their use with concrete examples. [ABSTRACT FROM AUTHOR]

Software size estimation has been the object of a lot of research in the software engineering community due to the need of reliable size estimates in the utilization of existing software project cost estimation models. This paper discusses the strengths and weaknesses of existing size estimation techniques, considers the nature of software size estimation, and presents a software size estimation model which has the potential for providing more accurate size estimates than existing methods. The proposed method takes advantage of a characteristic of object-oriented systems, the natural correspondence between specification and implementation, in order to enable users to come up with better size estimates at early stages of the software development cycle. Through a statistical approach the method also provides a confidence interval for the derived size estimates. The relation between the presented software sizing model and project cost estimation has also been considered. [ABSTRACT FROM AUTHOR]

The programming tradeoffs between structure-oriented and clause-oriented operations on data structures in Prolog are limited in current implementations of Prolog, because the assertion of clauses that include uninstantiated variables destroys any binding between these variables and those with which they are unified in the execution of the program. In this paper, we propose new built-in predicates for Prolog that allow us to assert predicate variable pointers, which are constants, rather than uninstantiated variables. We show: 1) the possible performance benefits of clause-oriented implementations of data structures over equivalent structure-oriented versions, 2) the logical implications of the proposed built-in predicates, and 3) their practical significance by integrating them in C-Prolog, and evaluating the two different implementations of the symbol table dictionary in Warren's Pseudo-Pascal Compiler example. [ABSTRACT FROM AUTHOR]

This paper addresses the problem of assigning the modules of a distributed program to the processors of a distributed system. The goal of such an assignment is to minimize the total execution and communication costs. A computational model of a distributed program, containing probabilistic branches and loops, is described using a directed graph whose edges represent precedence relations between modules. Efficient algorithms based on shortest path methods are presented to determine the optimum assignment on a distributed system containing N heterogeneous processors. [ABSTRACT FROM AUTHOR]

Over the last decade there has developed an acute awareness of the need to introduce abstraction and mathematical rigor into the programming process. This increased formality allows for the automatic manipulation of software, increasing productivity, and, even more importantly, the manageability of complex systems. Along these lines, attribute grammars constitute a formal mechanism for specifying translations between languages; from a formal description of the translation a translator can be automatically constructed. In this paper we consider taking this process one step further: given an attribute grammar specifying the translation from language L1 to language L2, we address the question of whether the inverse attribute grammar specifying the inverse translation from L2 to L1 can be automatically generated. We show how to solve this problem for a restricted subset of attribute grammars. This inversion process allows for compatible two-way translators to be generated from a single description. To show the practical feasibility of attribute grammar inversion, we relate our experience in inverting an attribute grammar used as an interface for a formal database accessing language, SQL. The attribute grammar is used to paraphrase SQL database queries in English. [ABSTRACT FROM AUTHOR]

There will be a rotation of editors of the periodical "IEEE Transactions on Software Engineering." The periodical is receiving about 25 papers a month, not counting special issue papers. Upon receipt of a paper, the goal is to have the acknowledgment letter to the author and the paper to the editor within five working days.

Presents a letter to the editor concerning the article "Protocol Conversion".

Shankar and Lam propose a projection method for protocol verification. They claim that the method guarantees the faithfulness of the safety and liveness properties of a protocol system. Although not clearly defined, "faithfulness" (as implied in many places in their article) means "the image protocol system is live (respectively, safe) if and only if the original protocol system is live (respectively, safe)." This paper shows that the "only if" part is not true for certain liveness properties and suggests a remedy. [ABSTRACT FROM AUTHOR]

A model for representing and analyzing the design of a distributed software system is presented. The model is based on a modified form of Petri net, and enables one to represent both the structure and the behavior of a distributed software system at a desired level of design. Behavioral properties of the design representation can be verified by translating the modified Petri net into an equivalent ordinary Petri net and then analyzing that resulting Petri net. The model emphasizes the unified representation of control and data flows, partially ordered software components, hierarchical component structure, abstract data types, data objects, local control, and distributed system state. At any design level, the distributed software system is viewed as a collection of software components. Software components are externally described in terms of their input and output control states, abstract data types, data objects, and a set of control and data transfer specifications. They are interconnected through the shared control states and through the shared data objects. A system component can be viewed internally as a collection of subcomponents, local control states, local abstract data types, and local data objects. [ABSTRACT FROM AUTHOR]

A preliminary example of program development demonstrates that the control-independent implementation of data types can lead to very inefficient code. The concept of a data space, which emphasizes the interaction between data and control structures, is introduced as a formal model of virtual machines. The model consists of three components: a state space X, an information structure F, and a control component p. Formally, X is a set of objects, F a set of functions with common domain X mapping the states to the value sets of certain data types, and p a partial function X → X. Two important. points of investigation are the characterization of state space structure and the mechanism of implementation. Good state description is characterized by "completeness" and "orthogonality." Either property plays a prominent role for the concept of implementation which, in turn, is formally defined as a mapping from a "virtual" space to a "real" space, via some "macro" space. These notions are illustrated by means of several examples from the area of programming languages. [ABSTRACT FROM AUTHOR]

A technique for syntactic error correction, called pattern mapping, is developed. A pattern is used to describe how to map or change one string into another. Using a preconstructed list of patterns, for each detected error, the first pattern with successful mapping is found and a correction is made based on this pattern. A new error-correction criterion, called minimum distance correction with k correct lookahead symbols, is presented. A measure on patterns is defined to reflect the costs of corrections obtained using patterns. Based on this measure, a list of patterns can be constructed for meeting the new criterion using pattern mapping. The implementation of pattern mapping correction on SLR(1) parsers is discussed. Heuristics for selecting the best correction and for recovering from the failure of pattern mapping are developed. Experimental results for a subset of Algol are summarized and discussed. [ABSTRACT FROM AUTHOR]

A systematic method of providing software system fault recovery with maximal fault coverage subject to resource constraints of overall recovery cost and additional fault rate is presented. This method is based on a model for software systems which provides a measure of the fault coverage properties of the system in the presence of computer hardware faults. Techniques for system parameter measurements are given. An optimization problem results which is a doubly-constrained 0,1 Knapsack problem. Quantitative results are presented demonstrating the effectiveness of the approach. [ABSTRACT FROM AUTHOR]

A parallel program, Dijkstra's "on-the-fly" garbage collector, is proved correct using analysis along the lines suggested by Francez and Pnueli for cyclic programs. The method is briefly reviewed, and the proof is compared to another proof by D. Gries, based on a method by S. Owicki. The differences between the two approaches are discussed. [ABSTRACT FROM AUTHOR]

Optimizing a computer program is defined as improving the execution time without disturbing the correctness. We show how to use invariants from a proof of correctness in order to change the statements in and around the program's loops. This approach is shown to systematize existing optimization methods, and to sometimes allow stronger optimizations than are possible under the standard transformation approach. [ABSTRACT FROM AUTHOR]