This article is a retrospective reflection on our paper Constraint-Based Automatic Test Data Generation (DeMillo and Offutt, 1991), which was selected by the editorial board of the IEEE Transactions on Software Engineering as one of the most influential papers of the second decade of the journal. Published in 1991, this paper introduced a novel approach to automated test case generation using symbolic execution and constraint-solving techniques, a fundamental shift in how to approach software testing. The retrospective explores the impact of the paper on the development of mutation testing, the creation of the Mothra toolset, the evolution of test automation practices, and the technical innovations that made the paper a cornerstone of modern testing research. Beyond its technical contributions, the article has become known for its role in fostering a culture of rigorous systems-oriented research that continues to influence both academia and industry. This reflection highlights the enduring relevance of Constraint-Based Test Case Generation and its role as a foundational work in the field of software engineering.

Even casual observes have to notice the dramatic changes in the telecommunications industry that have taken place in the last five years. Giant companies split, merge and are sometimes displaced by newer ones that did not exist a decade ago. The business of running the mighty circuit-switched telephone netwok is under constant assault on one side from packet networks and on the other side from the bewildering array of wireless networks. Service providers compete for customer sometimes with no network infrastructure at all.

Most studies of software failures and faults have done little more than classify failures and faults collected from long-term projects. The authors propose a model to analyze failures and faults for debugging purposes. In the model, they define "failure modes" and "failure types" to identify the existence of program failures and the nature of the program failures, respectively. The goal of this research is to achieve a systematic process model to localize faults in debugging. They first examine properties of the proposed model from a theoretical point of view, then use the trityp program as a simple example to illustrate the possible usage of the model for debugging. Further study of the failure mode, a pilot experiment of applying the proposed model, and a way to employ heuristics according to different situations for fault localization are areas of future work.

Developing effective debugging strategies to guarantee the reliability of software is important. By analyzing the debugging process used by experienced programmers, we have found that four distinct tasks are consistently performed: (1) determining statements involved in program failures, (2) selecting suspicious statements that might contain faults, (3) making hypotheses about suspicious faults (variables and locations), and (4) restoring program state to a specific statement for verification. This research focuses support for the second task, reducing the search domain for faults, which we refer to as fault localization.We explored a new approach to enhancing the process of fault localization based on dynamic program slicing and mutation-based testing. In this new approach, we have developed the technique of Critical Slicing to enable debuggers to highlight suspicious statements and thus to confine the search domain to a small region. The Critical Slicing technique is partly based on "statement deletion" mutant operator of the mutation-based testing methodology. We have explored properties of Critical Slicing, such as the relationship among Critical Slicing, Dynamic Program Slicing, and Executable Static Program Slicing; the cost to construct critical slices; and the effectiveness of Critical Slicing. Results of experiments support our conjecture as to the effectiveness and feasibility of using Critical Slicing for fault localization.This paper explains our technique and summarizes some of our findings. From these, we conclude that a debugger equipped with our proposed fault localization method can reduce human interaction time significantly and aid in the debugging of complex software.

Describes our experience with a newly-established international partnership between the Software Engineering Research Center (SERC), a university-based National Science Foundation (NSF) sponsored industrial research organization in the United States and an Italian industry-university team based in Padua, Italy.>

In a recent article by P.G. Frankl and E.J. Weyuker (see ibid., vol.19, no.3, p.962-75, 1993), results are reported that appear to establish a hierarchy of software test methods based on their respective abilities to detect faults. The methods used by Frankl and Weyuker to obtain this hierarchy constitute a new and important addition to their arsenal of tools. These tools were developed specifically to establish simple, useful comparisons of test data generation methods. This is the latest step in an ambitious test method classification program undertaken by the Frankl and Weyuker and their collaborators. The article discusses the method and goes on to present a reply to the critique.>

Abstract Programmers spend considerable time debugging code. Symbolic debuggers provide some help but the task remains complex and difficult. Other than breakpoints and tracing, these tools provide little high‐level help. Programmers must perform many tasks manually that the tools could perform automatically, such as finding which statements in the program affect the value of an output variable for a given test case, and what was the value of a given variable when the control last reached a given program location. If debugging tools provided explicit support for these tasks, the debugging process could be automated to a significant extent. In this paper we present a debugging model, based on dynamic program slicing and execution backtracking techniques, that easily lends itself to automation. This model is based on experience with using these techniques to debug software. We also present a prototype debugging tool, SPYDER, that explicitly supports the proposed model, and with which we are performing further debugging research.

Constraint-based testing is a novel way of generating test data to detect specific types of common programming faults. The conditions under which faults will be detected are encoded as mathematical systems of constraints in terms of program symbols. A set of tools, collectively called Godzilla, has been implemented that automatically generates constraint systems and solves them to create test cases for use by the Mothra testing system. Experimental results from using Godzilla show that the technique can produce test data that is very close in terms of mutation adequacy to test data that is produced manually, and at substantially reduced cost. Additionally, these experiments have suggested a new procedure for unit testing, where test cases are viewed as throw-away items rather than scarce resources.

A method for integrating support for program mutation into a compiler is presented. The method is both efficient and sufficiently powerful to support program mutation software testing. Moreover, existing research suggests that this approach appears to be essential for the cost-effective application of program mutation to testing large commercial software systems. It is believed that a compiler-integrated approach will provide a significant increase in the efficiency of several existing testing tools and allow program mutation to be effectively used to test commercial software systems.>

A simple proof is given, showing that for every operational description of a software system expressed as a discrete state transition function on a virtual machine, there is a continuous smooth function on the reals that agrees with the state transition function on all legal states and has exactly the same complexity. It is suggested that an implication of this result is that there is no reason, in principle, that the methods of classical analysis cannot be used in software engineering.>

A novel technique for automatically generating test data is presented. The technique is based on mutation analysis and creates test data that approximate relative adequacy. It is a fault-based technique that uses algebraic constraints to describe test cases designed to find particular types of faults. A set of tools (collectively called Godzilla) that automatically generates constraints and solves them to create test cases for unit and module testing has been implemented. Godzilla has been integrated with the Mothra testing system and has been used as an effective way to generate test data that kill program mutants. The authors present an initial list of constraints and discuss some of the problems that have been solved to develop the complete implementation of the technique.>

Summary form only given. The management of test and evaluation programs for life-critical software, particularly within the US Department of Defense, is largely fragmented and ineffective. As a result, software remains a significant and uncontrolled risk element in major systems. Some problems yet to be adequately addressed are identified.>

No abstract available.

The use of experimental methods and statistical analysis techniques to study factors influencing operational survivability in gracefully degrading systems is investigated. Survivability data are generated using a statistically designed experiment in conjunction with a simulation model of network survivability. Thirty two factors having stable regression coefficients are used to identify ten regression models explaining survivability. Influential factors include the distributed system network, the application system, and the distribution policy. Nine factors are found in all models: the number of nodes in the distribution system, distributed system connectivity, module memory requirements, module-to-module interaction frequency, distribution policy, percent of nodes lost, initial assignment results, available processing capacity at the end of the subcase, and the interaction of all application-related variables. Models that are acceptable from both an estimation and prediction viewpoint are developed. Possible commercial and military applications are suggested.

A cryptographic transformation is a mapping f from a set of cleartext messages, M, to a set of ciphertext messages. Since for m e M, f(m) should hide the contents of m from an enemy, f-1 should, in a certain technical sense, be difficult to infer from f(m) and public knowledge about f.

In testing for program correctness, the standard approaches [11,13,21,22,23,24,34] have centered on finding data D, a finite subset of all possible inputs to program P, such that

In this paper, we present a scheme for distributing a key to n users in such a way as to require at least k of them (k < n) to be present to construct the original key. The scheme has the property that up to k - 1 defections can be tolerated. It can be implemented simply and efficiently.

Technology that allows significant sharing of computer resources carries with it an increased responsibility to protect these resources from un-authorized, malicioua, irresponsible, or unintended use or disclosure. The years have seen a progression of increasingly sensitive information made available in increasingly less supervised modes to a variety of users. Commercial users routinely store valuable financial information and conduct cashless transactions electronically. University professors maintain class grading forms and examinations on departmental computers. Government agencies keep extensive databases of sensitive information regarding employees, foreign nationals, U.S. citizens. The military and intelligence communities continue to press for more powerful techniques to enhance their information gathering and processing capabilities. In spite of the clear need for guarantees of security, all practical schemes to protect information stored or manipulated by such systems are either seriously flawed or reduce ultimately to a collection of physical security protocols (ace [1] for an overview of the state of the art).

@ Consistency results represent an approach to the lower bound problems of complexity theory which points to a number of interesting lines of inquiry. Our ultimate goal is to make precise the difficulty of proving certain nontrivial lower bounds. Among the possibilities which follow from this approach are: (1) that logical techniques may help us resolve the P e NP question, (2) that showing why certain arguments must fail may lead to mathematical tools capable of resolving the problems, and (3) that the special character of model theoretic methods in complexity theory may lead to new results which are of purely logical interest. We will address these possibilities below.

AnSTRACT Let G and G* be programs represented by directed graphs There is defined a relation ~-s.r between G and G* that formahzes the notton of G* simulating G with Sffold loss of space efficiency and T-fold loss of time efficiency, ~t is proved that ff G - lo B n + O(Iog2 logz n) KEY WORDS AND PHRASES ancestor tree, complexity, control structure, dtrected graph, embedding CR CATEGORIES 4 22, 4 34, 5 24, 5 32 IntroducttonIn a previous paper [1] we made precise some intuitwe observations concerning the efficiency of structured programs by defining a combinatorial relation that corresponds to the notion of uniform szrnulatton between programs.Informally, we say that a program G* uniformly simulates a program G ff G* carries out the computation of G (and possibly addRlonal computation which might be regarded as "bookkeeping") in such a way that the space-time efficiency of G is degraded by a factor that is independent of the size of G.The main results of [ 1] indicate that the nonexistence of uniform simulations among many well-known classes of control structures is at least in part due to the combinatorial aspects of program structure and not to such details of program orgamzation as choice of data structures or limitations on the form of Boolean expressions.Indeed, the main result of [1, Th. 5.1] provides a nontrivml lower bound on the loss of space-time efficiency in any structured simulation of a goto program.This short note extends that result, improving the space-time inequality of [1, Th. 5.1] by an exponentml.Thus we now show that there are goto programs with n statements such that for any structured simulation either Pernnsslon to copy wtthout fee all or part of this matenal is granted provided that the copies are not made or distnbuted for direct commercial advantage, the ACM copyright notice and the tttle of the pubhcation and Rs date appear, and notice is gwen that copying ts by permission of the AssoclaUon for Computing Machinery To copy otherwise, or to republish, requires a fee and/or specific permission These results were announced at the 1976 Johns Hopkins Conference on Information Sciences and Systems

However difficult the fundamental problems of theoretical computer science may seem, there is very little to suggest that they are anything more than knotty combinatorial problems. So, when we look for reasons for our inability to resolve P = NP and related questions, we most likely find them dealing with a lack of understanding of particular computational problems and their lower bounds. This is the sense of Hopcroft's prediction: “...within the next five years, nobody will prove that any of these problems takes more than let's say n2 time. I think that's a reasonably safe conjecture and it also illustrates how little we know about lower bounds.” [MT]. Hopcroft's guess is uncanny in its accuracy—after six years and considerable effort by many researchers, his conjecture remains unchallenged.

Computer security has been an important issue since the first computer was developed. However, with the advent of faster and more accessible machines used by many users and large quantities of shared data, this issue has achieved far greater importance. It is no longer sufficient to rely on a system of password control through which a user is protected by having a 7-letter code known only to himself, since while this may, in the best case, prevent other users from directly accessing the users area, it does little to prevent indirect access. The potential dangers from such indirect access increase manyfold. In this survey, we shall discuss protection in three forms. The first is the privacy-certification problem for digital information. To maintain the privacy and authenticity of information cryptosystems and digitalized "signature" algorithms have been devised. The second involves the problems of unauthorized users gaining access to restricted data. In this case, it is necessary to discuss access control mechanisms that can be brought to bear in order to protect each users security. A third and far more subtle method of compromising a system is through what is called "statistical inference". Here, the user obtains information that is available to him legally and uses this information to infer information to which he has no access privileges. As more secure access-control mechanisms are proposed to guard from illegal access to protected data, it is this problem which looms as the major important problem of data security. And, this problem can never be totally solved since we must grant to authorized users access to data of this type. As an illustration of this problem, consider a problem faced by the census bureau ( or any other creator of administrative databases). In such a database, sensitive information is collected about a group of individuals while guaranteeing each individual that data collected about him will not be made available to users at large. However, in order to do research on large segments of the population, it is necessary for aggregated forms of this data to be made available to certain users. Suppose that a sociologist wishes to study correlations among a population with respect to various characteristics. Then, it might be necessary to give this sociologist access to the data. However, in order to guarantee each individual's privacy, we will wish to do this in a statistical manner. That is, we will refuse to answer questions about an individual or small set of individuals, but will make available information about larger segments of society in a manner that does not give information about any individual. And the problem arises as to how to insure that no malicious user can use this information in order to determine the characteristics of a single individual. A common method that has been proposed is to refuse access to information about any set of individuals which consists of too few people and in this manner restrict access to individual data. When data is given about a set of individuals, it will then be given in an aggregated form consisting of mean or median characteristics or counts of the number of people having a certain characteristic. However, as shown below, such a limitation is often not sufficient to guarantee individual privacy. Furthermore, refusing to answer a question often gives as much information as an aggregated answer since one might be able to infer information from the reason for a non-answer. Another area where this problem is of great significance is in the problem of medical record-keeping. Here, we may wish to track a set of people having a certain ailment in their early life (or people who have been exposed to certain phenomena) in order to determine long range effects of medications or exposures. In so doing, we want to make the data as helpful as possible to medical researchers while guaranteeing individual privacy. Because of the nature of such data, it is of great value to malicious users.

Users can compromise data bases by asking a series of questions, even when the data bases are allowed to lie.

Article Free Access Share on Social processes and proofs of theorems and programs Authors: Richard A. DeMillo Georgia Institute of Technology Georgia Institute of TechnologyView Profile , Richard J. Lipton Yale University Yale UniversityView Profile , Alan J. Perlis Yale University Yale UniversityView Profile Authors Info & Claims POPL '77: Proceedings of the 4th ACM SIGACT-SIGPLAN symposium on Principles of programming languagesJanuary 1977 Pages 206–214https://doi.org/10.1145/512950.512970Online:01 January 1977Publication History 22citation680DownloadsMetricsTotal Citations22Total Downloads680Last 12 Months16Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my Alerts New Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

A formal framework for studying the scheduling problem for task systems with multiple outcome operations and independent control structure is presented Models of sequential programs and their parallel representa tlons (schedules) are developed.Schedules are seen to be restrictions of the parallel program schema of Karp and Mdler The restrictions are that the operations are synchronous and of fixed duration Interpretations of schedules are provided, and it as shown that the schedules are determinate and preserve the results of sequential computations in various senses Various equivalence properties of schedules and their relationships are studied.A number of decldablhty questions are answered by using the notion of "parallel derivatives" introduced by Mlllen Optamallty of schedules IS defined m terms of minimal tame executions, and parallel derivatives are used to generate optimal schedules.Finally, the finite representation of optimal schedules as considered

Control structures and data structures are modeled by directed graphs. In the control case nodes represent executable statements and arcs represent possible flow of control; in the data case nodes represent memory locations and arcs represent logical adjacencies in the data structure. Classes of graphs are compared by a relation ≤ S.T where G ≤ S.T H if G can be embedded in H with at most a T -fold increase in distance between embedded nodes by making at most S “copies” of any node in G . For both control structures and data structures, S and T are interpreted as space and time constants, respectively. Results are presented that establish hierarchies with respect to ≤ S.T for (1) data structures, (2) sequential program schemata normal forms, and (3) sequential control structures.

The parallel scheduling of a partially ordered set of tasks has received great attention. The partially ordered tasks can be viewed as components of a straight-line program. In this note, we discuss some aspects of the nonpreemptive parallel scheduling of a program with more general control structures. We examine the existence of optimal k-processor schedules, and in line with recent interest in the complexity of computer computations and algorithms, we study the complexity of constructing optimal k-processor schedules. In particular we show that, for every k > 1, any algorithm that would yield an optimal k-processor schedule of a loop-free program, when such a schedule exists, will be of exponential-time complexity.

The running time or computational complexity of a sequential process is usually determined by summing weights attached to the basic operations from which the process is derived. In practice, however, the complexity is often limited by how efficiently it can access its data structures and how efficiently it can control program flow. Furthermore, it has been extensively argued [4] that certain limitations on the process sequencing mechanisms available to the programmer result in more “efficient” representations for the underlying processes. In this paper we will examine these issues in an attempt to assess the “power” of various data and control structures.

The purpose of this paper is to present the basis of an automata-theoretic model which treats the concept of “schedule” for programs which admit a (predefined) degree of parallelism.