Search

In this paper, we first present an exploratory analysis of the aspects of multiple-version software diversity using 36,123 programs written to the same specification. We do so within the framework of the theories of Eckhardt and Lee and Littlewood and Miller. We analyze programming faults made, explore failure regions and difficulty functions, and show how effective 1-out-of-2 diversity is and how language diversity increases this effectiveness. The second part of this paper generalizes the findings about 1-out-of-2 diversity and its special case language diversity by performing statistical analyses of 89,402 programs written to 60 specifications. Most observations in the exploratory analysis are confirmed; however, although the benefit of language diversity can be observed, its effectiveness-appears to be low. [ABSTRACT FROM AUTHOR]

This paper proposes a methodology and instrumentation infrastructure toward the reverse engineering of UML (Unified Modeling Language) sequence diagrams from dynamic analysis. One motivation is, of course, to help people understand the behavior of systems with no (complete) documentation. However, such reverse-engineered dynamic models can also be used for quality assurance purposes, They can, for example, be compared with design sequence diagrams and the conformance of the implementation to the design can thus be verified. Furthermore, discrepancies can also suggest failures in meeting the specifications. Due to size constraints, this paper focuses on the distribution aspects of the methodology we propose. We formally define our approach using metamodels and consistency rules. The instrumentation is based on Aspect-Oriented Programming in order to alleviate the effort overhead usually associated with source code instrumentation. A case study is discussed to demonstrate the applicability of the approach on a concrete example. [ABSTRACT FROM AUTHOR]

The paper on Comments on "An Interval Logic for Real-Time System Specification" presents some remarks on the comparison examples from TILCO and other logics and some slips on the related examples. This paper gives evidence that such issues have no impact on the validity of the TILCO Theory of paper [1] and provides some further clarifications about some aspects of the comparison [ABSTRACT FROM AUTHOR]

Understanding how to implement software process improvement (SRI) successfully is arguably the most challenging issue facing the SPI field today. The SPI literature contains many case studies of successful companies and descriptions of their SRI programs. However, the research efforts to date are limited and inconclusive and without adequate theoretical and psychometric justification. This paper extends and integrates models from prior research by performing an empirical investigation of the key factors for success in SPI. A quantitative survey of 120 software organizations was designed to test the conceptual model and hypotheses of the study. The results indicate that success depends critically on six organizational factors, which explained more than 50 percent of the variance in the outcome variable. The main contribution of the paper is to increase the understanding of the influence of organizational issues by empirically showing that they are at least as important as technology for succeeding with SPI and, thus, to provide researchers and practitioners with important new insights regarding the critical factors of success in SPI. [ABSTRACT FROM AUTHOR]

New compact, low-power implementation technologies for processors and imaging arrays can enable a new generation of portable video products. However, software compatibility with large bodies of existing applications written in C prevents more efficient, higher performance data parallel architectures from being used in these embedded products. If this software could be automatically retargeted explicitly for data parallel execution, product designers could incorporate these architectures into embedded products. The key challenge is exposing the parallelism that is inherent in these applications but that is obscured by artifacts imposed by sequential programming languages. This paper presents a recognition-based approach for automatically extracting a data parallel program model from sequential image processing code and retargeting it to data parallel execution mechanisms. The explicitly parallel model presented, called multidimensional data flow (MDDF), captures a model of how operations on data regions (e.g., rows, columns, and tiled blocks) are composed and interact. To extract an MDDF model, a partial recognition technique is used that focuses on identifying array access patterns in loops, transforming only those program elements that hinder parallelization, while leaving the core algorithmic computations intact. The paper presents results of retargeting a set of production programs to a representative data parallel processor array to demonstrate the capacity to extract parallelism using this technique. The retargeted applications yield a potential execution throughput limited only by the number of processing elements, exceeding thousands of instructions per cycle in massively parallel implementations. [ABSTRACT FROM AUTHOR]

It is desirable for the load in a distributed system to be balanced evenly. A dynamic process migration protocol is needed in order to achieve load balancing in a user transparent manner. A distributed algorithm for load balancing which is network topology independent is proposed in this paper. Different network topologies and low-level communications protocols affect the choice of only some system design parameters. The "drafting" algorithm attempts to compromise two contradictory goals: maximize the processor utilization and minimize the communication overhead. The main objective of this paper is to describe the dynamic process migration protocol based on the proposed drafting algorithm. A sample distributed system is used to further illustrate the drafting algorithm and to show how to define system design parameters. The system performance is measured by simulation experiments based on the sample system. [ABSTRACT FROM AUTHOR]

In 1980, System Development Corporation (SDC) delivered software for a modern air defense system (ADS) for a foreign country. Development of the ADS software was a successful SCD project where all products were delivered within budget and within an ambitious 25 month schedule. This paper describes SDC's approach and experience in developing ADS software. SDC's software development approach included the first time use of an oft-the-shelf operating system for a major air defense system, the application of a selective set of modern software development techniques, and use of a matrix management structure. SDC's successful application on ADS of a commercial (`pent- log system, a higher order language, a Program Design Language, a Pro- gram Production Library, structured walk-throughs, structured programming techniques, incremental build implementation and test procedures, interactive development, and word processing is described. A discussion of the advantages realized and difficulties encountered in the ADS matrix management structure is presented. The paper concludes with a summary of how SDC will develop software on future projects as a result of its experience on ADS. [ABSTRACT FROM AUTHOR]

This paper reports results obtained from a static analysis of the NAG Mark 4 Fortran numerical algorithms library. The analysis consists of two components. We rust record the gross features, such as the frequency with which language constructs occur, interpret our findings in terms of the NAG coding standards and properties of the Fortran compilers on which the library normally runs. The second component is a more detailed analysis of the routines' logical structure. This part of the paper is an attempt to determine some of the fundamental characteristics of good software. [ABSTRACT FROM AUTHOR]

This paper considers the role of run-time diagnostic checking in enforcing the rules of the Pascal programming language. Run- time diagnostic checks must be both complete (covering all language requirements) and efficient. Further, such checks should be implemented so that the cost of enforcing the correct use of a given construct is borne by users of that construct. This paper describes simple and efficient mechanisms currently in use with a diagnostic Pascal compiler that monitor the run-time behavior of such sensitive Pascal constructs as pointers, variant records, reference (i.e., vat) parameters, and with statements. The use of these mechanisms with related constructs in other languages is considered. Language modifications that simplify run-time checking are also noted. [ABSTRACT FROM AUTHOR]

In this paper we: 1) discuss the need for quantitatively reproducible experiments in the study of top-down design; 2) propose the design and writing of tutorial papers as a suitably general and in- expensive vehicle; 3) suggest the software science parameters as appropriate metrics; 4) report two experiments validating the use of these metrics on outlines and prose; and 5) demonstrate that the experiments tended toward the same optimal modularity. The last point appears to offer a quantitative approach to the estimation of the total length or volume (and the mental effort required to produce it) from an early stage of the top-down design process. If results of these experiments are validated elsewhere, then they will provide basic guidelines for the design process. [ABSTRACT FROM AUTHOR]

This paper describes a procedure for analyzing unbalanced datasets that include many nominal- and ordinal-scale factors. Such datasets are often found in company datasets used for benchmarking and productivity assessment. The two major problems caused by lack of balance are that the impact of factors can be concealed and that spurious impacts can be observed. These effects are examined with the help of two small artificial datasets. The paper proposes a method of forward pass residual analysis to analyze such datasets. The analysis procedure is demonstrated on the artificial datasets and then applied to the COCOMO dataset. The paper ends with a discussion of the advantages and limitations of the analysis procedure. [ABSTRACT FROM AUTHOR]

The technologies, architecures, and methodologies traditionally used to develop distributed applications exhibit a variety of limitations and drawbacks when applied to large scale distributed settlings (e.g., the Internet). In particular, they fail in providing the desired degree of configurability, scalability, and customizability. To address these issues, researchers are investigating a varity of innovative approaches. The most promising and intriguing ones are those based on the ability of moving code across the nodes of a network, expoloiting the notion of mobile code. As an emerging research field, code mobility is generating a growing body of scientific literature and industrial developments. Nevertheless, the field is still characterized by the lack of a sound and comprehensive body of concepts and terms. As a consequence, it is rather difficult to understand, assess, and compare the existing approaches. In turn, this limits our ability to fully exploit them in practice, and to further promote the research work on mobile code. Indeed, a significant symptom of this situation is the lack of a commonly accepted and sound definition of the term "mobile code" itself. This paper presents a conceptual framework for understanding code mobility. The framework is centered around a classification that introduces three dimensions: technologies, design paradigms, and applications. The contribution of the paper is two-fold. First, it provides a set of terms and concepts to understand and compare the approaches based on the notion of mobile code. Second, it introduces criteria and guidelines that support the developer in the identification of the classes of applications that can leverage off of mobile code, in the design of these applications, and finally, in the selection of the most appropriate implemention technlogies. The presentation of the classification is interwined with a review of state-of-the-art in the field. Finally, the use of the classification is exemplified in a case study. Mobile code, mobile agent, distributed application, design paradigm. [ABSTRACT FROM AUTHOR]

Embedded assertions have been recognized as a potentially powerful tool for automatic runtime detection of software faults during debugging, testing, maintenance and even production versions of software systems. Yet despite the richness of the notations and the maturity of the techniques and tools that have been developed for programming with assertions, assertions are a development tool that has seen little widespread use in practice. The main reasons seem to be that (1) previous assertion processing tools did not integrate easily with existing programming environments, and (2) it is not well understood what kinds of assertions are most effective at detecting software faults. This paper describes experience using an assertion processing tool that was built to address the concerns of ease-of-use and effectiveness. The tool is called APP, an Annotation PreProcessor for C programs developed in UNIX-based development environments. APP has been used in the development of a variety of software systems over the past five years. Based on this experience, the paper presents a classification of the assertions that were most effective at detecting faults. While the assertions that are described guard against many common kinds of faults and errors, the very commonness of such faults demonstrates the need for an explicit, high-level, automatically checkable specification of required behavior. It is hoped that the classification presented in this paper will prove to be a useful first step in developing a method of programming with assertions. [ABSTRACT FROM AUTHOR]

Non-Uniform Memory Access (NUMA) architectures make it possible to build large-scale, shared-memory multiprocessor systems, in comparison with nonscalable Uniform Memory Access (UMA) architectures. Most NUMA multiprocessor operations such as scheduling and synchronizing processes, accessing data from processors to memory modules and allocating distributed memory space to different processors, are performed through interconnection networks such as a multistage switching network The efficiency of these basic operations determines the parallel processing performance on a NUMA multiprocessor. This paper presents several analytical models to predict and evaluate the overhead of interprocessor communication, process scheduling, process synchronization, and remote memory access where network contention and memory contention are considered. Performance measurements to support the models and analyses through several numerical examples have been done on the BBN GP1000, a NUMA shared-memory multiprocessor. Both analytical and experimental results give a comprehensive and clear understanding of the various effects, which are important for the effective use of a NUMA shared-memory multiprocessor. The results in this paper may be used to determine optimal strategies in developing an efficient programming environment for a NUMA system. [ABSTRACT FROM AUTHOR]

The Larch family of specification languages supports a two-tiered definitional approach to specification. Each specification has components written in two languages: one designed for a specific programming language and another independent of any programming language. The former are called Larch interface languages, and the latter the Larch Shared Language (LSL). The Larch style of specification emphasizes brevity and clarity rather than executability. To make it possible to test specifications without executing or implementing them, Larch permits specifiers to make claims about logical properties of specifications and to check these claims at specification time. Since these claims are undecidable in the general case, it is impossible to build a tool that will automatically certify claims about arbitrary specifications. However, it is feasible to build tools that assist specifiers in checking claims as they debug specifications. This paper describes the checkability designed into LSL and discusses two tools that help perform the checking. This paper is a revised and expanded version of a paper presented at the April 1990 IFIP Working Conference on Programming Concepts and Methods [7]. [ABSTRACT FROM AUTHOR]

This paper describes a proof system suitable for the mechanical verification of concurrent programs. Mechanical verification, which uses a computer program to validate a formal proof, increases one's confidence in the correctness of the validated proof. This proof system is based on Unity [12], and may be used to specify and verify both safety and liveness properties. However, it is defined with respect to an operational semantics of the transition system model of concurrency. Proof rules are simply theorems of this operational semantics. This methodology makes a clear distinction between the theorems in the proof system and the logical inference rules and syntax which define the underlying logic. Since this proof system essentially encodes Unity in another sound logic, and this encoding has been mechanically verified, this encoding proves the soundness of this formalization of Unity. This proof system has been mechanically verified by the Boyer-Moore prover, a computer program mechanizing the Boyer-Moore logic [7]. This proof system has been used to mechanically verify the correctness of a distributed algorithm that computes the minimum node value in a tree. This paper also describes this algorithm and its correctness theorems, and presents the key lemmas that aided the mechanical verification. The mechanized proof closely resembles a hand proof, but is longer, since all concepts are defined from first principles. This proof system is suitable for the mechanical verification of a wide class of programs, since the underlying prover, though automatic, is guided by the user. [ABSTRACT FROM AUTHOR]

An important advantage of a database system is that it provides each application with a custom view of the data. The issue addressed in this paper is how to provide such custom views to applications that access multiple databases. The paper describes a formal method that generates such superviews, In an interactive process of schema editing operations. A mapping of the superview into the individual databases is derived from the editing process, and is stored together with the superview as a virtual database. When this database is interrogated, the mapping is used to decompose each query into a set of queries against the individual databases, and recompose the answers to form an answer to the original query. As this process is transparent to the user, virtual databases may be regarded as a more general type of databases. A prototype database system, that allows users to construct virtual databases and interrogate them, has been developed. [ABSTRACT FROM AUTHOR]

In a paper by Hawthorn and DeWitt, the projected performance of several proposed database machines was examined for three relational database queries. The present paper investigates the performance of a massively parallel machine called NON-VON for the same queries under comparable assumptions. In the case of simple queries, a NON-VON machine of comparable size to those considered by Hawthorn and DeWitt is found to be somewhat faster than the fast- est machines examined in their study; for a more complex database operation, NON-VON is shown to be five to ten times faster than the fastest of these machines. [ABSTRACT FROM AUTHOR]

Aspect-oriented software development has become an important development and maintenance approach to software engineering across requirements, design and implementation phases. However, discovering early aspects from requirements for a better integration of crosscutting concerns into a target system is still not well addressed in the existing works. In this paper, we propose a Goal-driven Early Aspect approach (called GEA) to discovering early aspects by means of a clustering algorithm in which relationships among goals and use cases are utilized to explore similarity degrees of clustering goals, and total interaction degrees are devised to check the validity of the formation of each cluster. Introducing early aspects not only enhances the goal-driven requirements modeling to manage crosscutting concerns, but also provides modularity insights into the analysis and design of software development. Moreover, relationships among goals represented numerically are more informative to discover early aspects and more easily to be processed computationally than qualitative terms. The proposed approach is illustrated by using two problem domains: a meeting scheduler system and a course enrollment system. An experiment is also conducted to evaluate the benefits of the proposed approach with Mann-Whitney U-test to show that the difference between with GEA and without GEA is statistically significant. [ABSTRACT FROM PUBLISHER]

Algebraic specifications have been used in the testing of object-oriented programs and received much attention since the 1990s. It is generally believed that class-level testing based on algebraic specifications involves two independent aspects: the testing of equivalent and nonequivalent ground terms. Researchers have cited intuitive examples to illustrate the philosophy that even if an implementation satisfies all the requirements specified by the equivalence of ground terms, it may still fail to satisfy some of the requirements specified by the nonequivalence of ground terms. Thus, both the testing of equivalent ground terms and the testing of nonequivalent ground terms have been considered as significant and cannot replace each other. In this paper, we present an innovative finding that, given any canonical specification of a class with proper imports, a complete implementation satisfies all the observationally equivalent ground terms if and only if it satisfies all the observationally nonequivalent ground terms. As a result, these two aspects of software testing cover each other and can therefore replace each other. These findings provide a deeper understanding of software testing based on algebraic specifications, rendering the theory more elegant and complete. We also highlight a couple of important practical implications of our theoretical results. [ABSTRACT FROM PUBLISHER]

Several recent studies indicate that many industrial applications exhibit poor quality in the design of exception-handling. To improve the quality of error-handling, we need to understand the problems and obstacles that developers face when designing and implementing exception-handling. In this paper, we present our research on understanding the viewpoint of developers--novices and experts--toward exception-handling. First, we conducted a study with novice developers in industry. The study results reveal that novices tend to ignore exceptions because of the complex nature of exception-handling. Then, we conducted a second study with experts in industry to understand their perspective on exception-handling. The study results show that, for experts, exception-handling is a crucial part in the development process. Experts also confirm the novices' approach of ignoring exception-handling and provide insights as to why novices do so. After analyzing the study data, we identified factors that influence experts' strategy selection process for handling exceptions and then built a model that represents a strategy selection process experts use to handle exceptions. Our model is based on interacting modules and fault scope. We conclude with some recommendations to help novices improve their understanding of exception-handling. [ABSTRACT FROM AUTHOR]

Synthesis of behavior models from software development artifacts such as scenario-based descriptions or requirements specifications helps reduce the effort of model construction. However, the models favored by existing synthesis approaches are not sufficiently expressive to describe both universal constraints provided by requirements and existential statements provided by scenarios. In this paper, we propose a novel synthesis technique that constructs behavior models in the form of Modal Transition Systems (MTS) from a combination of safety properties and scenarios. MTSs distinguish required, possible, and proscribed behavior, and their elaboration not only guarantees the preservation of the properties and scenarios used for synthesis but also supports further elicitation of new requirements. [ABSTRACT FROM AUTHOR]

Based on 1) research into mutation testing for general-purpose programming languages and 2) spreadsheet errors that have been reported in the literature, we have developed a suite of mutation operators for spreadsheets. We present an evaluation of the mutation adequacy of definition-use adequate test suites generated by a constraint-based automatic test-case generation system we have developed in previous work. The results of the evaluation suggest additional constraints that can be incorporated into the system to target mutation adequacy. In addition to being useful in mutation testing of spreadsheets, the operators can be used in the evaluation of error-detection tools and also for seeding spreadsheets with errors for empirical studies. We describe two case studies where the suite of mutation operators helped us carry out such empirical evaluations. The main contribution of this paper is a suite of mutation operators for spreadsheets that can be used for performing empirical evaluations of spreadsheet tools to indicate ways in which the tools can be improved. [ABSTRACT FROM AUTHOR]

Researchers have explored the application of combinatorial interaction testing (CIT) methods to construct samples to drive systematic testing of software system configurational Applying CIT to highly-configurable software systems is complicated by the fact that, in many such systems, there are constraints between specific configuration parameters that render certain combinations invalid. Many CIT algorithms lack a mechanism to avoid these. In recent work, automated constraint solving methods have been combined with search-based CIT construction methods to address the constraint problem with promising results. However, these techniques can incur a nontrivial overhead. In this paper, we build upon our previous work to develop a family of greedy CIT sample generation algorithms that exploit calculations made by modern Boolean satisfiability (SAT) solvers to prune the search space of the CIT problem. We perform a comparative evaluation of the cost effectiveness of these algorithms on four real-world highly-configurable software systems and on a population of synthetic examples that share the characteristics of these systems. In combination, our techniques reduce the cost of CIT in the presence of constraints to 30 percent of the cost of widely used unconstrained CIT methods without sacrificing the quality of the solutions. [ABSTRACT FROM AUTHOR]

Many techniques for detecting duplicated source code (software clones) have been proposed in the past. However, it is not yet clear how these techniques compare in terms of recall and precision as well as space and time requirements. This paper presents an experiment that evaluates six clone detectors based on eight large C and Java programs (altogether almost 850 KLOC). Their clone candidates were evaluated by one of the authors as an independent third party. The selected techniques cover the whole spectrum of the state-of-the-art in clone detection, The techniques work on text, lexical and syntactic information, software metrics, and program dependency graphs. [ABSTRACT FROM AUTHOR]

Design by contract is a lightweight technique for embedding elements of formal specification (such as invariants, pre and postconditions) into an object-oriented design. When Contracts are made executable, they can play the role of embedded, online oracles. Executable contracts allow components to be responsive to erroneous states and, thus, may help in detecting and locating faults. In this paper, we define Vigilance as the degree to which a program is able to detect an erroneous state at runtime. Diagnosability represents the effort needed to locate a fault once it has been detected. In order to estimate the benefit of using Design by Contract, we formalize both notions of Vigilance and Diagnosability as software quality measures. The main steps of measure elaboration are given, from informal definitions of the factors to be measured to the mathematical model of the measures. As is the standard in this domain, the parameters are then fixed through actual measures, based on a mutation analysis in our case. Several measures are presented that reveal and estimate the contribution of contracts to the overall quality of a system in terms of vigilance and diagnosability. [ABSTRACT FROM AUTHOR]

This paper describes a method and a tool for validating nonfunctional requirements in complex socio-technical systems. The System Requirements Analyzer (SRA) tool validates system reliability and operational performance requirements using scenario- based testing. Scenarios are transformed into sequences of task steps and the reliability of human agents performing tasks with computerized technology is assessed using Bayesian Belief Network (BN) models. The tool tests system performance within an envelope of environmental variations and reports the number of tests that pass a benchmark threshold. The tool diagnoses problematic areas in scenarios representing pathways through system models, assists in the identification of their causes, and supports comparison of alternative requirements specifications and system designs. It is suitable for testing socio-technical systems where operational scenarios are sequential and deterministic, in domains where designs are incrementally modified so set up costs of the BNs can be defrayed over multiple tests. [ABSTRACT FROM AUTHOR]

Calculating with graphs and relations has many applications in the analysis of software systems, for example, the detection of design patterns or patterns of problematic design and the computation of design metrics. These applications require an expressive query language, in particular, for the detection of graph patterns, and an efficient evaluation of the queries even for large graphs. In this paper, we introduce RML, a simple language for querying and manipulating relations based on predicate calculus, and CrocoPat, an interpreter for RML programs. RML is general because it enables the manipulation not only of graphs (i.e., binary relations), but of relations of arbitrary arity. CrocoPat executes RML programs efficiently because it internally represents relations as binary decision diagrams, a data structure that is well-known as a compact representation of large relations in computer-aided verification. We evaluate RML by giving example programs for several software analyses and CrocoPat by comparing its performance with calculators for binary relations, a Prolog system, and a relational database management system. [ABSTRACT FROM AUTHOR]

In this paper, we present an FP-like approach, named Class Point, which was conceived to estimate the size of object-oriented products. In particular, two measures are proposed, which are theoretically validated showing that they satisfy well-known properties necessary for size measures. An initial empirical validation is also performed, meant to assess the usefulness and effectiveness of the proposed measures to predict the development effort of object-oriented systems. Moreover, a comparative analysis is carried out, taking into account several other size measures. [ABSTRACT FROM AUTHOR]

Information Systems are situated in and are representations of some business or organizational domain. Hence, understanding the application domain is critical to the success of information systems development. To support domain understanding, the application domain is represented in conceptual models. The correctness of conceptual models can affect the development outcome and prevent costly rework during later development stages. This paper proposes a method to restrict the syntax of a modeling language to ensure that only possible configurations of a domain can be modeled, thus increasing the likelihood of creating correct domain models. The proposed method, based on domain ontologies, captures relationships among domain elements via constraints on the language metamodel, thus restricting the set of statements about the domain that can be generated with the language. In effect, this method creates domain specific modeling languages from more generic ones. The method is demonstrated using the Unified Modeling Language (UML). Specifically, it is applied to the subset of UML dealing with object behavior and its applicability is demonstrated on a specific modeling example. [ABSTRACT FROM AUTHOR]

The relationships between coupling and external quality factors of object-oriented software have been studied extensively for the past few years. For example, several, studies have identified clear empirical relationships between class-level coupling and class fault-proneness. A common way to define and measure coupling is through structural properties and static code analysis. However, because of polymorphism, dynamic binding, and the common presence of unused ("dead") code in commercial software, the resulting coupling measures are imprecise as they do not perfectly reflect the actual coupling taking place among classes at runtime. For example, when using static analysis to measure coupling, it is difficult and sometimes impossible to determine what actual methods can be invoked from a client class if those methods are overridden in the subclasses of the server classes. Coupling measurement has traditionally been performed using static code analysis, because most of the existing work was done on nonobject oriented code and because dynamic code analysis is more expensive and complex to perform. For modem software systems, however, this focus on static analysis can be problematic because although dynamic binding existed before the advent of object-orientation, its usage has increased significantly in the last decade. This paper describes how coupling can be defined and precisely measured based on dynamic analysis of systems. We refer to this type of coupling as dynamic coupling. An empirical evaluation of the proposed dynamic coupling measures is reported in which we study the relationship of these measures with the change proneness of classes. Data from maintenance releases of a large Java system are used for this purpose. Preliminary results suggest that some dynamic coupling measures are significant indicators of change proneness and that they complement existing coupling measures based on static analysis. [ABSTRACT FROM AUTHOR]

Over the last decade, a lot of research has been directed toward integrating performance analysis into the software development process. Traditional software development methods focus on software correctness, introducing performance issues later in the development process. This approach does not take into account the fact that performance problems may require considerable changes in design, for example, at the software architecture level, or even worse at the requirement analysis level. Several approaches were proposed in order to address early software performance analysis. Although some of them have been successfully applied, we are still far from seeing performance analysis integrated into ordinary software development. In this paper, we present a comprehensive review of recent research in the field of model-based performance prediction at software development time in order to assess the maturity of the field and point out promising research directions. [ABSTRACT FROM AUTHOR]

While empirical studies in software engineering are beginning to gain recognition in the research community, this subarea is also entering a new level of maturity by beginning to address the human aspects of software development. This added focus has added a new layer of complexity to an already challenging area of research. Along with new research questions, new research methods are needed to study nontechnical aspects of software engineering. In many other disciplines, qualitative research methods have been developed and are commonly used to handle the complexity of issues involving human behavior. This paper presents several qualitative methods for data collection and analysis and describes them in terms of how they might be incorporated into empirical studies of software engineering, in particular how they might be combined with quantitative methods. To illustrate this use of qualitative methods, examples from real software engineering studies are used throughout. [ABSTRACT FROM AUTHOR]

Although prior research has compared modeling performance using different systems development methods, there has been little research examining the comprehensibility of models generated by those methods. In this paper, we report the results of an empirical study comparing user comprehension of object-oriented (OO) and process-oriented (PO) models. The fundamental difference is that while OO models tend to focus on structure, PO models tend to emphasize behavior or processes. Proponents of the OO modeling approach argue that it lends itself naturally to the way humans think. However, evidence from research in cognitive psychology and human factors suggests that human problem solving is innately procedural. Given these conflicting viewpoints, we investigate empirically if OO models are in fact easier to understand than PO models. But, as suggested by the theory of cognitive fit, model comprehension may be influenced by task-specific characteristics. We, therefore, compare OO and PO models based on whether the comprehension activity involves: 1) only structural aspects, 2) only behavioral aspects, or 3) a combination of structural and behavioral aspects. We measure comprehension through subjects' responses to questions designed along these three dimensions. Two experiments were conducted, each with a different application and a different group of subjects. Each subject was first trained in both methods, and then participated in one of the two experiments, answering several questions relating to his or her comprehension of an OO or a PO model of a business application. The comprehension questions ranged in complexity from relatively simple (addressing either structural or behavioral aspects) to more complex ones (addressing both structural and behavioral aspects). Results show that for most of the simple questions, no significant difference was observed insofar as model comprehension is concerned. For most of the complex questions, however, the PO model was found to be easier to understand than the OO model. In addition to describing the process and the outcomes of the experiments, we present the experimental method employed as a viable approach for conducting research into various phenomena related to the efficacy of alternative systems analysis and design methods. We also identify areas where future research is necessary, along with a recommendation of appropriate research methods for empirical examination. [ABSTRACT FROM AUTHOR]

Many distributed scheduling algorithms have been developed and reported in the current literature. However, very few of them explicitly treat stability issues. This paper first discusses stability issues for distributed scheduling algorithms in general terms. Two very different distributed scheduling algorithms which contain explicit mechanisms for stability are then presented and evaluated with respect to individual specific stability issues. One of the algorithms is based on stochastic learning automata and the other on bidding. The results indicate how very specific the treatment of stability is to the algorithm and environment under consideration. [ABSTRACT FROM AUTHOR]

Databases that are mainly used for statistical analysis are called statistical databases (SDB). A statistical database management system (SDBMS) may be defined as a database management system that provides capabilities 1) to model, store, and manipulate data in a manner suitable for the needs of SDB users, and 2) to apply statistical data analysis techniques that range from simple summary statistics to advanced procedures. This paper surveys the existing and proposed SDB data definition and data manipulation (i.e., query) languages. [ABSTRACT FROM AUTHOR]

The purpose of this paper is to summarize the research issues of statistical and scientific databases (SSDB's). It organizes the issues into four major groups: physical organization and access methods, operators, logical organization and user interfaces, and miscellaneous issues. It emphasizes the differences between SSDB's and traditional database applications, and motivates the need for new and innovative techniques for the support of SSDB's. In addition to describing current work in this field, it discusses open research areas and proposes possible approaches to their solution. [ABSTRACT FROM AUTHOR]

When using MIMD (multiple instruction, multiple data) parallel computers, one is often confronted with solving a task composed of many independent subtasks where it is necessary to synchronize the processors after all the subtasks have been completed. This paper studies how the subtasks should be allocated to the processors in order to minimize the expected time it takes to finish all the subtasks (sometimes called the makespan). We assume that the running times of the subtasks are independent, identically distributed, increasing fail- ure rate random variables, and that assigning one or more subtasks to a processor entails some overhead, or communication time, that is in- dependent of the number of subtasks allocated. Our analyses, which use ideas from renewal theory, reliability theory, order statistics, and the theory of large deviations, are valid for a wide class of distributions. We show that allocating an equal number of subtasks to each processor all at once has good efficiency. This appears as a consequence of a rather general theorem which shows how some consequences of the central limit theorem hold even when we cannot prove that the central limit theorem applies. Our methods of analysis permit the determination of an optimal strategy subject to the constraint that each processor must take a fixed number of subtasks at any given time. We show that this strategy can give results remarkably close to an unrestrictedly optimal one. Our analysis is asymptotic as the number of subtasks and processors become large. [ABSTRACT FROM AUTHOR]

In this paper we introduce two classes of program testing strategies that consist of specifying a set of required elements for the program and then covering those elements with appropriate test inputs. In general, a required element has a structural and a functional component and is covered by a test case if the test case causes the features specified in the structural component to be executed under the conditions specified in the functional component. Data flow analysis is used to specify the structural component and data flow interactions are used as a basis for developing the functional component. The strategies are illustrated with examples and some experimental evaluations of their effectiveness are presented. [ABSTRACT FROM AUTHOR]

It is well known that algebraic specification methods are promising for specifying programs and for verifying their various properties formally. In this paper, an algebraic specification of information transfer procedures of high-level data link control (HDLC) procedures is presented and some of the main properties of the specification arc shown. First, we introduce abstract states, state transition functions, and output functions corresponding to elementary notions extracted from the description of HDLC procedures in ISO 3309-1979 (F) and ISO 4335-1979 (E). Second, we show axioms which represent the relations between the values of functions before and after the state transitions. Then, it is proved that the specification is "consistent," "sufficiently complete," and "nonredundant." Also it is shown that an implementation which realizes the specification is naturally derived. In the last section, verification of various properties of HDLC procedures is formulated in the same framework as the algebraic specification, and some verification examples are presented. [ABSTRACT FROM AUTHOR]

The problem of providing efficient concurrent access for independent processes to a dynamic search structure is the topic of this paper. We develop concurrent algorithms for search, update, insert, and delete in a simple variation of binary search trees, called external trees. The algorithm for deletion, which is usually the most difficult operation, is relatively easy in this data structure. The advantages of the data structure and the algorithms are that they are simple, flexible, and efficient, so that they can be used as a part in the design of more complicated concurrent algorithms where maintaining a dynamic search structure is necessary. In order to increase the efficiency of the algorithms we introduce maintenance processes that independently reorganize the data structure and relieve the user processes of nonurgent operations. We also discuss questions of transactions in a dynamic environment and replicated copies of the data structure. [ABSTRACT FROM AUTHOR]

Compact interactive control consoles are replacing traditional control rooms as operator interfaces for physical processes. In the first major application of concurrent programming outside the area of operating systems, this paper presents a design for a general purpose operator interface which uses a color graphics terminal with a touch-sensitive screen as the control console. Operators interact with a process through a collection of application-dependent displays generated interactively by users familiar with the physical process. The use of concurrent programming results in a straightforward and reliable design which may easily be extended to support multiple devices of varying types in the control console. An implementation of tile Operator Interface in Concurrent Pascal currently in progress is also discussed. [ABSTRACT FROM AUTHOR]

An experimental data flow analyzer for PL/I programs has been implemented within the PROBE system developed at the GM Research Laboratories. PROSE is an experimental software package that examines the internal structure of PL/I programs in order to expose error-prone design and programming features. This paper describes 1) the algorithms and data structures used by the data flow analyzer, 2) the salient aspects of PL/I usage in the analyzed production-level programs, and 3) the results of the data. flow analysis. [ABSTRACT FROM AUTHOR]

An abstract requirements specification states system requirements precisely without describing a real or a paradigm implementation. Although such specifications have important advantages, they are difficult to produce for complex systems and hence are seldom seen in the "real" programming world. This paper introduces an approach to producing abstract requirements specifications that applies to a significant class of real-world systems, including any system that must reconstruct data that have undergone a sequence of transformations. It also describes how the approach was used to produce a requirements document for SCP, a small, but nontrivial Navy communications system. The specification techniques used in the SCP requirements document are introduced and illustrated with examples. [ABSTRACT FROM AUTHOR]

-c_Halstead proposed a methodology for studying the process of programming known as software science. This methodology merges theories from cognitive psychology with theories from computer science. There is evidence that some of the assumptions of software science incorrectly apply the results of cognitive psychology studies. Halstead proposed theories relative to human memory models that appear to be without support from psychologists. Other software scientists, however, report empirical evidence that may support some of those theories. This anomaly places aspects of software science in a precarious position. The three conflicting issues discussed in this paper are 1) limitations of short-term memory and number of subroutine parameters, 2) searches in human memory and programming effort, and 3) psychological time and programming time. [ABSTRACT FROM AUTHOR]

-c_The theory of software science was developed by the late M. H. Halstead of Purdue University during the early 1970's. It was first presented in unified form in the monograph Elements of Software Science published by Elsevier North-Holland in 1977. Since it claimed to apply scientific methods to the very complex and important problem of software production, and since experimental evidence supplied by Halstead and others seemed to support the theory, it drew widespread attention from the computer science community. Some researchers have raised serious questions about the underlying theory of software science. At the same time, experimental evidence supporting some of the metrics continue to be presented. This paper is a critique of the theory as presented by Halstead and a review of experimental results concerning software science metrics published since 1977. [ABSTRACT FROM AUTHOR]

The purpose of this paper is to develop a method for designing and verifying data abstractions using the functional approach. Before doing so, the existing techniques for designing and verifying procedure and data abstractions will be surveyed briefly. These techniques will then be modified and extended to verify data abstractions. By using the concept of a mathematical function, one can model the behavior of a procedure abstraction and give a more uniform and clearer meaning to the stepwise refinement and verification of procedure abstractions. The concept of a state machine is then used as a basis to specify data abstractions. Using state machine specification, a technique for expressing the design of a data abstraction is then given. A method is then developed to verify the design of a data abstraction with respect to its specifications. [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]

The need for programming environments which support different phases of the software life cycle using responsive tools is well established. This paper presents a method for developing automatic analyzers which analyze programs and provide programmers with a variety of messages for the purpose of validating these programs in the early stages of program development. We show using an example, that such analyzers can be systematically constructed using an extension of the Attribute Grammar model which reflects the fact that a prop-am analyzer should perform a static analysis of the program as well as monitor its dynamic behavior efficiently. One of the advantages of the model is that a systematic interaction is allowed between the static and dynamic attributes of the program. We illustrate that an advantage of this interaction is selective program instrumentation. That is, the analyzer is responsive to the programmer's needs by providing a selective analysis of the program's behavior rather than an exhaustive analysis which is difficult to comprehend. [ABSTRACT FROM AUTHOR]

It is known that not all paths are possible in the run time control flow of many programs. It is also known that data flow analysis cannot restrict attention to exactly those paths that are possible. It is, therefore, usual for analytic methods to consider all paths. Sharper information can be obtained by considering a recursive set of paths that is large enough to include all possible paths, but small enough to exclude many of the impossible ones. This paper presents a simple uniform methodology for sharpening data flow information by considering certain recursive path sets of practical importance. Associated with each control flow arc there is a relation on a finite set C). The paths that qualify to be considered are (essentially) those for which the com- position of the relations encountered is nonempty. For example, Q might be the set of all assignments of values to each of several bit variables used by a program to remember some facts about the past and branch accordingly in the future. Given any data flow problem together with qualifying relations on Q associated with the control flow arcs, we construct a new problem. Considering all paths in the new problem is equivalent to considering only qualifying paths in the old one. Preliminary experiments (with a small set of real programs) Indicate that qualified analysis is feasible and substantially more informative than ordinary analysis. The methodology also ban beneficial feedback effect on the delicate task of passing from programs to meaningful data flow analysis problems. Even when all paths qualify, unusually sharp information can be obtained by passing from programs to problems in ways suggested by theorems proved here. [ABSTRACT FROM AUTHOR]