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]

Regression testing is an expensive, but important, process. Unfortunately, there may be insufficient resources to allow for the reexecution of all test cases during regression testing. In this situation, test case prioritization techniques aim to improve the effectiveness of regression testing by ordering the test cases so that the most beneficial are executed first. Previous work on regression test case prioritization has focused on Greedy Algorithms. However. it is known that these algorithms may produce suboptimal results because they may construct results that denote only local minima within the search space. By contrast, metaheuristic and evolutionary search algorithms aim to avoid such problems. This paper presents results from an empirical study of the application of several greedy, metaheuristic, and evolutionary search algorithms to six programs, ranging from 374 to 11,148 lines of code for three choices of fitness metric. The paper addresses the problems of choice of fitness metric, characterization of landscape modality, and determination of the most suitable search technique to apply. The empirical results replicate previous results concerning Greedy Algorithms. They shed light on the nature of the regression testing search space, indicating that it is multimodal. The results also show that Genetic Algorithms perform well, although Greedy approaches are surprisingly effective, given the multimodal nature of the landscape. [ABSTRACT FROM AUTHOR]

Conventional database design techniques rely heavily on the designer's skill and experience, which are neither efficient nor effective for large, realistic design problems. A computer design aid can help by storing many design parameters and performing simple pre- processing before design decisions are made. In this paper, we report on the development of such a system. The system is based on a data model called the Functional Data Model (FDM), and on a transaction (or process) model which is specified via the Transaction Specification Language (TASL). FDM is used to define data entities and the relationships between them. TASL is used to capture application processing intent and performance parameters that are relevant to the database design. Logical database design involves two major steps. First, local (or application) views are modeled using FDM and TASL. Second, in order to achieve an integrated database design, these local views are combined and transformed to produce a global conceptual view (schema). This paper describes FDM and TASL; in addition, a set of operations for integrating and transforming local views is presented. A unique feature of these transformations is that they apply to TASL processes as well as FDM schema Finally, an algorithm is given for view integration. This algorithm, along with heuristics and some user-supplied subset assertions, enables the database design system to automatically identify and filter out redundancies. [ABSTRACT FROM AUTHOR]

Numerous algorithms for computationally intensive tasks have been developed by researchers that are suitable for execution on hypercube multiprocessors. One characteristic of many of these algorithms is that they are extremely structured and are tuned for the highest performance to execute on hypercube architectures. In this paper, we have looked at parallel algorithm design from a different perspective. In many cases, it may be possible to redesign the parallel algorithms using software techniques so as to provide a low-cost on-line scheme for hardware error detection without any hardware modifications. This approach is called Algorithm-based error detection. In the past, we have applied algorithm-based techniques for on-line error detection on the hypercube and have reported some preliminary results of one specific implementation on some applications. In this paper, we provide an in-depth study of the various issues and tradeoffs available in Algorithm-based error detection, as well as a general methodology for evaluating the schemes. We have illustrated the approach on an extremely useful computation in the field of numerical linear algebra: QR factorization. We have implemented and investigated numerous ways of applying algorithm-based error detection using different system-level encoding strategies for QIZ factorization. Different schemes have been observed to result in varying error coverages and time overheads. We have reported the results of our studies performed on a 16 processor Intel iPSC-2/D4/MX hypercube multiprocessor. [ABSTRACT FROM AUTHOR]

In this paper, we have investigated the efficient evaluation of branch-and-bound algorithms in a system with a two-level memory hierarchy. An efficient implementation depends on the disparities in the numbers of subproblems expanded between the depth-first and best-first searches as well as the relative speeds of the main and secondary memories. A best-first search should be used when it expands a much smaller number of subproblems than that of a depth-first search, and the secondary memory is relatively fast. In contrast, a depth-first search should be used when the number of expanded subproblems is close to that of a best-first search. The choice is not as clear for cases in between. The Iterative Deepening A* (IDA*) algorithm has been shown to be asymptotically optimal in space, time, and cost. However, for the conditions that we have assumed, 1DM does not result in the optimal space-time tradeoff for minimizing the completion time. In this paper, we study the space-time tradeoff by proposing and analyzing two strategies: a specialized virtual-memory system that matches the architectural design with the characteristics of the existing algorithm, and a modified branch-and-bound algorithm that can be tuned to the characteristic of the problem and the architecture. The latter strategy illustrates that designing a better algorithm is sometimes more effective than tuning the architecture alone. Guidelines have also been developed to select appropriate a priori values for the parameters of the modified B&B algorithm. [ABSTRACT FROM AUTHOR]

This paper proposes a model or paradigm for the development of parallel algorithms, gives an example of the proposed paradigm, and displays algorithms developed by application of the technique. The algorithm for the merge of two ordered fists developed through application of this technique is thought to be original. The paradigm proposed is to create composite unit operations which combine data movement between data structures with a conventional operation such as compare or add. The composite operation constructed for this study is based upon partitioning the data elements into two linear lists. Exchange of data between adjacent elements in each list are then combined with compares and adds to complete the composite operations. This composite operation can be implemented on at least the following computational architectures. 1) SIMD with all processors sharing a common memory. 2) SIMD with local memories and a linear interconnection (circular pipeline or ring network of processors). 3) Vector processor with common memory, such as a CDC CYBER 205 or a Cray Research CRAY-1. The algorithms developed all have the property of linear speed-up with the number of processing elements. The algorithms developed include sorting, merging, selection among sets, set interconnection, set difference, subset testing, and string matching. [ABSTRACT FROM AUTHOR]

This paper discusses axiomatic and functional models of the semantics of structured programming. The models are presented together with their respective methodologies (or proving program correctness and for denying correct programs. Examples using these methodologies are given. Finally, the models are compared and contrasted. [ABSTRACT FROM AUTHOR]

In this paper, we present an approximate solution for the asymptotic behavior of relatively general queueing networks. In the particular case of networks with general service time distributions (i.e., fixed routing matrix, one or many servers per station, FIFO discipline), the application of the method gives relatively accurate results in a very short time. The approximate stationary state probabilities are identified with the solution of a nonlinear system. The proposed method is applicable to a larger class of queueing networks (dependent routing matrix, stations with finite capacity, etc.). In this case, the structure of the network studied must satisfy certain decomposability conditions. [ABSTRACT FROM AUTHOR]

The configuration spaces of modern software systems are too large to test exhaustively. Combinatorial interaction testing (CIT) approaches, such as covering arrays, systematically sample the configuration space and test only the selected configurations by using a battery of test cases. Traditional covering arrays, while taking system-wide interoption constraints into account, do not provide a systematic way of handling test case-specific interoption constraints. The basic justification for $(t)$-way covering arrays is that they can cost effectively exercise all system behaviors caused by the settings of $(t)$ or fewer options. In this paper, we hypothesize, however, that in the presence of test case-specific interoption constraints, many such behaviors may not be tested due to masking effects caused by the overlooked test case-specific constraints. For example, if a test case refuses to run in a configuration due to an unsatisfied test case-specific constraint, none of the valid option setting combinations appearing in the configuration will be tested by that test case. To account for test case-specific constraints, we introduce a new combinatorial object, called a test case-aware covering array. A $(t)$-way test case-aware covering array is not just a set of configurations, as is the case in traditional covering arrays, but a set of configurations, each of which is associated with a set of test cases such that all test case-specific constraints are satisfied and that, for each test case, each valid combination of option settings for every combination of $(t)$ options appears at least once in the set of configurations that the test case is associated with. We furthermore present three algorithms to compute test case-aware covering arrays. Two of the algorithms aim to minimize the number of configurations required (one is fast, but produces larger arrays, the other is slower, but produces smaller arrays), whereas the remaining algorithm aims to minimize the number of test runs required. The results of our empirical studies conducted on two widely used highly configurable software systems suggest that test case-specific constraints do exist in practice, that traditional covering arrays suffer from masking effects caused by ignorance of such constraints, and that test case-aware covering arrays are better than other approaches in handling test case-specific constraints, thus avoiding masking effects. [ABSTRACT FROM PUBLISHER]

Search-Based Test Data Generation reformulates testing goals as fitness functions so that test input generation can be automated by some chosen search-based optimization algorithm. The optimization algorithm searches the space of potential inputs, seeking those that are “fit for purpose,” guided by the fitness function. The search space of potential inputs can be very large, even for very small systems under test. Its size is, of course, a key determining factor affecting the performance of any search-based approach. However, despite the large volume of work on Search-Based Software Testing, the literature contains little that concerns the performance impact of search space reduction. This paper proposes a static dependence analysis derived from program slicing that can be used to support search space reduction. The paper presents both a theoretical and empirical analysis of the application of this approach to open source and industrial production code. The results provide evidence to support the claim that input domain reduction has a significant effect on the performance of local, global, and hybrid search, while a purely random search is unaffected. [ABSTRACT FROM PUBLISHER]

The identification of design patterns as part of the reengineering process can convey important information to the designer. However, existing pattern detection methodologies generally have problems in dealing with one or more of the following issues: Identification of modified pattern versions, search space explosion for large systems and extensibility to novel patterns. In this paper, a design pattern defection methodology is proposed that is based on similarity scoring between graph vertices. Due to the nature of the underlying graph algorithm, this approach has the ability to also recognize patterns that are modified from their standard representation. Moreover, the approach exploits the fact that patterns reside in one or more inheritance hierarchies, reducing the size of the graphs to which the algorithm is applied. Finally, the algorithm does not rely on any pattern-specific heuristic, facilitating the extension to novel design structures. Evaluation on three open-source projects demonstrated the accuracy and the efficiency of the proposed method. [ABSTRACT FROM AUTHOR]

The majority of the algorithms in the software clustering literature utilize structural information to decompose large software systems. Approaches using other attributes, such as file names or ownership information, have also demonstrated merit. At the same time, existing algorithms commonly deem all attributes of the software artifacts being clustered as equally important, a rather simplistic assumption. Moreover, no method that can assess the usefulness of a particular attribute for clustering purposes has been presented in the literature. In this paper, we present an approach that applies information theoretic techniques in the context of software clustering. Our approach allows for weighting schemes that reflect the importance of various attributes to be applied. We introduce LIMBO, a scalable hierarchical clustering algorithm based on the minimization of information loss when clustering a software system. We also present a method that can assess the usefulness of any nonstructural attribute in a software clustering context. We applied LIMBO to three large software systems in a number of experiments. The results indicate that this approach produces clusterings that come close to decompositions prepared by system experts. Experimental results were also used to validate our usefulness assessment method. Finally, we experimented with well-established weighting schemes from information retrieval, web search, and data clustering. We report results as to which weighting schemes show merit in the decomposition of software systems. [ABSTRACT FROM AUTHOR]

This paper describes the design and implementation of an intelligent tutoring system for the Dijkstra-Gries programming methodology as defined by Cries in "The Science of Programming"[12]. The first part of the paper identifies the requirements of intelligent tutoring systems in general and those of the methodology in particular. It shows the suitability of the Smalltalk environment for developing expandable intelligent systems and the compatibility of Smalltalk's object-oriented paradigm with the Gries methodology's goal/plan approach to programming. We then describe how these requirements are met: an overview of the system's support of the methodology and the modules that enable the system to respond intelligently. As an example, a reusable tutorial part is presented, first from a student's perspective, then from an author's perspective. Finally the results of an evaluation of the system drawn from actual student experience are presented. [ABSTRACT FROM AUTHOR]

This paper studies and compares the performance of several algorithms suitable for processing an important class of recursive queries, the so-called instantiated transitive closure (TC) queries. These algorithms are the two well known algorithms wavefront and .5-wavefront and a newly proposed generic algorithm called super-TC. During the evaluation of a TC query, the first two algorithms may read a given disk page more than once, whereas super-TC reads the disk page at most once. This paper also presents a comprehensive performance evaluation of these three algorithms using rigorous analytical and simulation models. Such a study reveals that the relative performance of the algorithms is a strong function of the parameters which characterize the processed TC query and the relation referenced by that query. Furthermore, it points out the superiority of one of the super-TC variants over all of the other presented algorithms. [ABSTRACT FROM AUTHOR]

The analysis and execution of partial algorithm descriptions is an important part of the algorithm design process (as is borne out by studying the behavior of human algorithm designers). In this paper, we describe a language for representing partially designed algorithms and a process, developmental evaluation, that can discover useful knowledge to guide design. Using these and other results from our research in artificial intelligence, we are building a system, DESIGNER, that automatically designs algorithms. This paper also compares developmental evaluation to execution and analysis techniques used for testing complete programs and for validation of abstract specifications; concepts similar to those found in developmental evaluation are thus shown to apply to all stages of the software life cycle. [ABSTRACT FROM AUTHOR]

A collection of design patterns was described by Gamma, Helm, Johnson, and Vlissides in 1994. Each pattern ensures that a certain system aspect can vary over time, for example the operations that can be applied to an object or the algorithm of a method. The patterns are described by constructs such as the inheritance and reference relations, attempting to emulate more dynamic relationships. As a result, the design patterns demonstrate how awkward it is to program natural concepts of evolution when using a traditional object- oriented language. In this paper, we present a new relation between classes: the context relation. It directly models dynamic evolution, and it is meaningful at both the design and implementation level. At the design level we extend the Unified Modeling Language (UML) to include the context relation as a new form of arrow between classes. At the implementation level we present a small extension of Java. The context relation introduces a new form of dynamic binding that serves as a replacement to delegation. We demonstrate how the context relation can be used to easily model and program numerous design patterns. [ABSTRACT FROM AUTHOR]

Software libraries are repositories which contain software components; as such, they represent a precious resource for the software engineer. As software libraries grow in size, it becomes increasingly difficult to maintain adequate precision and recall with informal retrieval algorithms. In this paper, we discuss the design and implementation of a storage and retrieval structure for software components that is based on formal specifications and on the refinement ordering between specifications. [ABSTRACT FROM AUTHOR]

Modifying and then validating a program with many interacting modules, such as procedures, is an expensive and complex task: maintenance activities must be performed for changed procedures and for those procedures that directly or indirectly interact with the changed procedure. The problem is further compounded because the maintainer is rarely the author of the code and usually lacks an understanding of the program. Thus, a maintenance environment containing an efficient program representation and tools that access the representation to assist the user in understanding, modifying, analyzing, reengineering, testing, and debugging a program are needed. This paper presents our unified interprocedural graph, UIG, that extracts the important features of existing program representations, and adds new information, to provide an integrated representation for maintenance tasks. We adapt previous interprocedural techniques to use the UIG, and we provide sufficient information to accommodate development of new interprocedural techniques. Algorithms that were developed for previous representations were adapted to use the UIG by identifying the subset of nodes and edges in the UIG required for that computation. Newly developed algorithms can use the UIG since it contains data flow, control flow, data dependence, and control dependence information. The main benefits of our approach are the reduction in storage space since individual representations are not kept, the savings in maintenance time of a single representation over the individual representations, and the convenience of accessing a single program representation without increase in access time. A single program representation also assists in program understanding since relationships among program elements are incorporated into one graph. [ABSTRACT FROM AUTHOR]

We explain why pre-run-time scheduling is essential if one wishes to guarantee that timing constraints will be satisfied in a large complex hard-real-time system. We examine some of the major concerns in pre-run-time scheduling and consider what formulations of mathematical scheduling problems can be used to address those concerns. This paper provides a guide to the available algorithms. [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]

Incremental data flow analysis algorithms have been designed to deal efficiently with change in evolving software systems. These algorithms document the current state of a software system, by incorporating change effects into previously derived information describing the definition and use of data in the system. Unfortunately, the performance of these algorithms cannot, in general, be characterized by analytic predictions of their expected behavior. We can, however, observe their performance empirically and predict their on the average behavior. This paper reports on experiments which are the first empirical profiling a general-purpose, incremental data flow analysis algorithm. Our dominator-based, incremental algorithm coded in C, was applied to statistically significant numbers of feasible, random software systems of moderate size (e.g., 100 functions with 400 or 600 function calls). Our experimental results, with quantifiable confidence limits, substantiate the claim that incremental analyses are viable and grow more valuable as a software system grows in size. [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]

In this paper we compare the performance of virtual memory allocation algorithms. The primary measure of performance is the space-time product of primary memory occupancy, or space-time cost, used by a program during its execution. Using DMIN, an optimal dynamic allocation algorithm, we compute the minimum space-time cost achievable for some benchmark program runs. We compare the DMIN space-time cost with the space-time cost from: MIN, an optimal static allocation algorithm, VMIN, an optimal variable space algorithm, and two heuristic dynamic allocation algorithms: the page fault frequency algorithm and the damped working set algorithm. [ABSTRACT FROM AUTHOR]

This paper presents a detailed algorithm derivation scenario, using correctness preserving source-to-source transformations. The algorithm derived is the Cocke-Younger nodal spans parsing algorithm. We describe a high-level SETL-like specification language. and give a partial correctness formalism and a set of transformation rules which enable the combination of algorithms whose partial correctness has already been established. [ABSTRACT FROM AUTHOR]

Most current systems for mechanical program verification are not fully automatic, since the user himself must provide the intermediate inductive assertions. This paper describes an interactive computer program, called ADI, which automatically generates the needed inductive assertions. ADI is also able to extend partial loop assertions supplied by the user to form complete assertions. The implementation (written in QLISP and INTERLISP) is based on both the algorithmic and the heuristic approaches introduced by Katz and Manna in "Logical Analysis of Programs" [25]. For the algorithmic subsystem ADI includes: Difference Equations Constructor, Difference Equations Solver, and Invariants from Conditional Statements Generator. The heuristic subsystem includes: Exit Rules Package, Bounding Variables Component, Strengthening Executer, Weakening Executer, and a Heuristic Invariant Matcher-which is the actual implementation of two new heuristics, MATCHPQ and MATCHPT. ADI is a small step toward interactive, practical program verification. [ABSTRACT FROM AUTHOR]

In this paper various path cover problems, arising in program testing, are discussed. Dilworth's theorem for acyclic digraphs is generalized. Two methods for finding a minimum set of paths (minimum path cover) that covers the vertices (or the edges) of a digraph are given. To model interactions among code segments, the notions of required pairs and required paths are introduced. It is shown that finding a minimum path cover for a set of required pairs is NP-hard. An efficient algorithm is given for finding a minimum path cover for a set of required paths. Other constrained path problems are considered and their complexities are discussed. [ABSTRACT FROM AUTHOR]

Trees are extremely common data structures, both as internal objects and as models for program output. But it is unusual to see a program actually draw trees for visual inspection. Although part of the difficulty lies in programming graphics devices, most of the problem arises because naive algorithms to draw trees use too much drawing space and sophisticated algorithms are not obvious. We survey two naive tree drawers, formalize aesthetics for tidy trees, and describe two algorithms which thaw tidy trees. One of the algorithms may be shown to require the minimum possible paper width. Along with the algorithms proper, we discuss the reasoning behind the algorithm development. [ABSTRACT FROM AUTHOR]

This paper contains an exposition of the method of programming with verification conditions. Although this method has much in common with the one discussed by Dijkstra in A Discipline of Programming, it is shown to have the advantage in simplicity and flexibility. The simplicity is the result of the method's being directly based on Floyd's inductive assertions. The method is flexible because of the way in which the program is constructed in two stages. In the first stage, a set of verification conditions is collected which corresponds to a program in "flowgraph" form. In this stage sequencing control is of no concern to the programmer. Control is introduced in the second stage, which consists of automatable applications of translation and optimization rules, resulting in conventional code. Although our method has no use for the sequencing primitives of "structured programming," it is highly secure and systematic. [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]

This paper describes a method for increasing the batch-processing efficiency of medium and large scale scientific compute, systems with a small main memory. A program-replacement algorithm, RESEP, is defined whose goal is to always keep the CPU busy. RESEP temporarily transfers selected programs from main memory to the secondary storage. Reallocation of such programs is also performed by this algorithm. We will compare throughput using the RESEP strategy with that using the well-known FCFS strategy by means of simple queueing networks. This comparison shows the increase in throughput achieved by RESEP over FCFS as a function of the workload parameters. We will show that a two-disk channel system running under FCFS is less efficient than a one-channel system running under RESEP. [ABSTRACT FROM AUTHOR]

In a distributed computing system a modular program must have its modules assigned among the processors so as to avoid excessive interprocessor communication while taking advantage of specific efficiencies of some processors in executing some program modules. In this paper we show that this program module assignment problem can be solved efficiently by making use of the well-known Ford-Fulkerson algorithm for finding maximum flows in commodity networks as modified by Edmonds and Karp, Dinic, and Karzanov. A solution to the two-processor problem is given, and extensions to three and n-processors are considered with partial results given without a complete efficient solution. [ABSTRACT FROM AUTHOR]

In this paper, we present a case study in deriving an algorithm from a formal specification via FermaT transformations. The general method (which is presented in a separate paper) is extended to a method for deriving an implementation of a program transformation from a specification of the program transformation. We use program slicing as an example transformation since this is of interest outside the program transformation community. We develop a formal specification for program slicing in the form of a WSL specification statement which is refined into a simple slicing algorithm by applying a sequence of general purpose program transformations and refinements. Finally, we show how the same methods can be used to derive an algorithm for semantic slicing. The main novel contributions of this paper are: 1) developing a formal specification for slicing, 2) expressing the definition of slicing in terms of a WSL specification statement, and 3) by applying correctness preserving transformations to the specification, we can derive a simple slicing algorithm. [ABSTRACT FROM AUTHOR]

A substantial amount of work has shed light on whether random testing is actually a useful testing technique. Despite its simplicity, several successful real-world applications have been reported in the literature. Although it is not going to solve all possible testing problems, random testing appears to be an essential tool in the hands of software testers. In this paper, we review and analyze the debate about random testing. Its benefits and drawbacks are discussed. Novel results addressing general questions about random testing are also presented, such as how long does random testing need, on average, to achieve testing targets (e.g., coverage), how does it scale, and how likely is it to yield similar results if we rerun it on the same testing problem (predictability). Due to its simplicity that makes the mathematical analysis of random testing tractable, we provide precise and rigorous answers to these questions. Results show that there are practical situations in which random testing is a viable option. Our theorems are backed up by simulations and we show how they can be applied to most types of software and testing criteria. In light of these results, we then assess the validity of empirical analyzes reported in the literature and derive guidelines for both practitioners and scientists. [ABSTRACT FROM PUBLISHER]

Randomized testing is an effective method for testing software units. The thoroughness of randomized unit testing varies widely according to the settings of certain parameters, such as the relative frequencies with which methods are called. In this paper, we describe Nighthawk, a system which uses a genetic algorithm (GA) to find parameters for randomized unit testing that optimize test coverage. Designing GAs is somewhat of a black art. We therefore use a feature subset selection (FSS) tool to assess the size and content of the representations within the GA. Using that tool, we can reduce the size of the representation substantially while still achieving most of the coverage found using the full representation. Our reduced GA achieves almost the same results as the full system, but in only 10 percent of the time. These results suggest that FSS could significantly optimize metaheuristic search-based software engineering tools. [ABSTRACT FROM AUTHOR]

This paper presents a comprehensive design methodology for guaranteeing end-to-end requirements of real-time systems. Applications are structured as a set of process components connected by asynchronous channels, in which the end- points are the system's external inputs and outputs. Timing constraints are then postulated between these inputs and outputs; they express properties such as end-to-end propagation delay, temporal input-sampling correlation, and allowable separation times between updated output values. The automated design method works as follows: First new tasks are created to correlate related inputs, and an optimization algorithm, whose objective is to minimize CPU utilization, transforms the end-to-end requirements into a set of intermediate rate constraints on the tasks. If the algorithm fails, a restructuring tool attempts to eliminate bottlenecks by transforming the application, which is then re-submitted into the assignment algorithm. The final result is a schedulable set of fully periodic tasks, which collaboratively maintain the end-to-end constraints. [ABSTRACT FROM AUTHOR]

Existing algorithms for update synchronization in replicated database systems follow a semidistributed model of update execution because only one site completely executes an update and other sites just commit its writes. In this paper, we present a fully-distributed approach to update synchronization where each site completely executes every update. This approach has several features-higher resiliency to different kinds of failures, higher parallelism, improved response to user requests, and low communication overhead. We present a fully-distributed algorithm for concurrency control which is obtained by rehashing the semi distributed algorithm of [32] into the fully-distributed model of update execution. We present a performance model of replicated database systems and use it to study the performance of the proposed algorithm and its semidistributed version. The results of the performance study reveal that the proposed approach can substantially improve the performance at the cost of moderate I/O overhead. [ABSTRACT FROM AUTHOR]

A state constraint is a new programming construct designed to restrict the domain of definition of a program. It can be used to decompose a program pathwise, i.e., to divide the program into subprograms along the control How, as opposed to divide the program across the control flow when the program is decomposed into functions and procedures. As a result one can now construct and manipulate a program consisting of one or more execution paths of another program. This paper describes the idea involved, examines the properties of state constraints, establishes a formal basis for pathwise decomposition, and discusses their utilities in program simplification, testing, and verification. [ABSTRACT FROM AUTHOR]

This paper presents a flexible and general mechanism for specifying problems relating to the sequencing of events and mechanically translating them into dataflow analysis algorithms capable of solving those problems. Dataflow analysis has been used for quite sonic time in compiler code optimization. It has recently gained increasing attention as a way of statically checking for the presence or absence of errors and as a way of guiding the test case selection process. Most static analyzers, however, have been custom-built to search for fixed, and often quite limited, classes of dataflow conditions. We show that the range of sequences for which it is interesting and worthwhile to search is actually quite broad and diverse. We create a formalism for specifying this diversity of conditions. We then show that these conditions can be modeled essentially as dataflow analysis problems for which effective solutions are known and further show how these solutions can be exploited to serve as the basis for mechanical creation of analyzers for these conditions. [ABSTRACT FROM AUTHOR]

A distributed system is an interconnected network of computing elements or nodes, each of which has its own storage. A distributed program is a collection of processes which execute asynchronously, possibly in different nodes of a distributed system, and they communicate with each other in order to realize a common goal. In such an environment, a group of processes may sometimes get involved in a communication deadlock. This is a situation in which each member process of the group is waiting for some member to communicate with it, but no member is attempting communication with it. In this paper, we present an algorithm for detecting such communication deadlocks. The algorithm is distributed, i.e., processes detect deadlocks during the course of their communication, without the aid of a central controller. The detection scheme does not presume any a priori structure among processes, and detection is made "on the fly" without freezing normal activities. The scheme does not require any storage whose size is determined by the size of the network, and hence is suitable also for an environment where processes are created dynamically. [ABSTRACT FROM AUTHOR]

A recent trend in program methodologies is to derive efficient parallel programs from sequential programs. This paper explores the question of transforming a sequential algorithm into an efficient parallel algorithm by considering the problem of balancing binary search trees. The derivation of the parallel algorithm makes use of stepwise refinement. We first derive a new iterative balancing algorithm that exploits the similarity of point restructuring required at all the nodes at the same level. From this we derive a parallel algorithm that has time complexity O(1) on an N-processor configuration. This achieves the theoretical limit of speedup possible in a multiprocessor configuration. [ABSTRACT FROM AUTHOR]

A model of distributed computation is proposed in which processes may fail by not sending or receiving the messages specified by a protocol. The solution to the Byzantine Generals Problem for this model is presented. Our algorithm exhibits early stopping under conditions of less than maximum failure and is as efficient as the algorithms developed for the more restrictive crash-fault model in terms of time, message, and bit complexity. We show extant models to underestimate resiliency when faults in the communication medium are considered; the model of this paper is more accurate in this regard. [ABSTRACT FROM AUTHOR]

We present a practical extension to typestate checking which is capable of proving programs free of uninitialized variable errors even when these programs contain conditionally initialized variables where the initialization of a variable depends upon the equality of one or more "tag" variables to a constant. The user need not predeclare the relationship between a conditionally initialized variable and its tags, and this relationship may change from one point in the program to another. Our technique generalizes liveness analysis to conditional liveness analysis. Like typestate checking, our technique incorporates a dataflow analysis algorithm in which each point in a program is labeled with a lattice point describing statically tracked information, including the initialization of variables. The labeling is then used to check for programming errors such as referencing a variable which may be uninitialized. Our technique incorporates a more expressive lattice, including predicates of the form: "x is initialized if y equals 2." Because the number of tags per variable is small, the added complexity of the analysis is usually small. The efficiency of our technique is due, to a large extent, to the fact that we use a backwards analysis of the program (instead of the forward analysis used in the original typestate checking algorithm). Our results suggest that backwards analysis—tracking only those properties which need to hold to make the subsequent statements correct—can be more efficient than forward analysis—tracking all properties which are made true by the preceding statements. We conclude with some additional applications of our techniques to program checking. [ABSTRACT FROM AUTHOR]

A trace-driven simulation study of dynamic load balancing in homogeneous distributed systems supporting broadcasting is presented. We use information about job CPU and I/O demands collected from production system as input to a simulation model that includes a representative CPU scheduling policy and considers the message exchange and job transfer costs explicitly. Seven load balancing algorithms are simulated and their performances compared. We find that load balancing is capable of significantly reducing the mean and standard deviation of job response times, especially under heavy system load, and for jobs with high resource demands. Algorithms based on periodic or nonperiodic load information exchange provide similar performance, and, among the periodic policies, the algorithms that use a distinguished agent to collect and distribute load information cut down the overhead and scale better. With initial job placements only, source initiative algorithms were found to perform better than server initiative algorithms. The performances of all hosts, even those originally with tight loads, are generally improved by load balancing. The reduction of the mean response time increases with the number of hosts, but levels off at around 30 hosts. Load balancing is still very effective when a large fraction of the eligible jobs have to be executed locally. [ABSTRACT FROM AUTHOR]

This editorial introduces the January 1993 issue of the periodical "IEEE Transactions on Software Engineering" which focuses on software for critical systems. The issue contains a selection of significant papers from the SIGSOFT '91 conference. Papers by Ricky Butler and George Finelly, John Rushby and Friedrich von Henke, and others address different aspects of the topic. [ABSTRACT FROM AUTHOR]

The assignment algorithms proposed in the above paper may not minimize the total communication and execution costs as stated. This correspondence gives an example where the proposed restricted assignment algorithm fails to find an optimal assignment and proposes modifications to the algorithm to properly consider execution costs. Additional changes needed to correctly model communication costs in many assignment problems are also discussed. [ABSTRACT FROM AUTHOR]

In an earlier paper [1], a distributed scheme for detecting communication deadlocks and a correctness proof of the algorithm were given. It is shown in this correspondence that the proof in [1] is not strict. [ABSTRACT FROM AUTHOR]

We attack the problem of incremental attribute evaluation for multiple asynchronous subtree replacements applicable to arbitrary noncircular attribute grammars. Our algorithm supports multiple independent editing cursors. Concurrent evaluation processes proceed independently as long as they cover disjoint regions of the derivation tree. Evaluation processes are merged when they overlap, to prevent unnecessary attribute evaluations. The algorithm ensures that when evaluation terminates, the tree is consistently attributed. Our results solve two open problems in the original algorithm for asynchronous subtree replacements reported by Kaplan and Kaiser. [ABSTRACT FROM AUTHOR]

The Kestrel Interactive Development System (KIDS) provides automated support for the development of correct and efficient programs from formal specifications. The system has components for performing algorithm design, deductive inference, program simplification, partial evaluation, finite differencing optimizations, data type refinement, compilation, and other development operations. Although their application is interactive, all of the KIDS operations are automatic except the algorithm design tactics which require some interaction at present. Dozens of programs have been derived using the system and we believe that KIDS could be developed to the point that it becomes economical to use for routine programming. To illustrate the use of KIDS, we trace the derivation of an algorithm for enumerating solutions to the k-queens problem. The initial algorithm that KIDS designs takes about 60 minutes on a SUN-4/110 to find all 92 solutions to the 8-queens problem instance. The final optimized version finds the same solutions in under one second. [ABSTRACT FROM AUTHOR]

We report our experience in developing a simulator, called Véda. Véda is a software tool to support designers in protocol modeling and validation. It is basically oriented towards the rapid prototyping of distributed algorithms, and has been available for more than two years. Algorithms are described using an ISO formal description technique, called Estelle. We first give an external view of Véda, and particularly how one can describe service properties and tracing, using a specific feature of Véda, called observation. Then, the development of Véda and its internal structure is presented, emphasizing the use of Prolog as a software engineering tool. Typical uses of Véda that have been made in the relatively large community of its users are sketched. We conclude with a critical analysis of the main features of Véda and how they may have contributed to its success. [ABSTRACT FROM AUTHOR]

Let T(U) be the set of words in the dictionary H which contains U as a substring. The problem considered here is the estimation of the set T(U) when U is not known, but Y, a noisy version of U is available. The suggested set estimate S*(Y) of T(U) is a proper subset of H such that its every element contains at least one substring which resembles Y most according to the Levenshtein metric. The proposed algorithm for the computation of S*(Y) requires cubic time. The algorithm uses the recursively computable dissimilarity measure Dk(X, Y), termed as the kth distance between two strings X and Y which is a dissimilarity measure between Y and a certain subset of the set of contiguous substrings of X. Another estimate of T(U), namely SM(Y) is also suggested. The accuracy of SM(Y) is only slightly less than that of S*(Y), but the computation time of SM(Y) is substantially less than that of S*(Y). Experimental results involving 1900 noisy substrings and dictionaries which are subsets of 1023 most common English words [11] indicate that the accuracy of the estimate S*(Y) is around 99 percent and that of SM(Y) is about 98 percent. [ABSTRACT FROM AUTHOR]