In this paper, we investigate opportunities to be gained from broadening the definition of program slicing. A major inspiration for our work comes from the field of partial evaluation, in which a wide repertoire of techniques have been developed for specializing programs. While slicing can also be harnessed for specializing programs, the kind of specialization obtainable via slicing has heretofore been quite restricted, compared to the kind of specialization allowed in partial evaluation. In particular, most slicing algorithms are what the partial-evaluation community calls monovariant: each program element of the original program generates at most one element in the answer. In contrast, partial-evaluation algorithms can be polyvariant, i.e., one program element in the original program may correspond to more than one element in the specialized program.

This paper defines a new variant of program slicing, called specialization slicing , and presents an algorithm for the specialization-slicing problem that creates an optimal output slice. An algorithm for specialization slicing is polyvariant : for a given procedure р, the algorithm may create multiple specialized copies of р. In creating specialized procedures, the algorithm must decide for which patterns of formal parameters a given procedure should be specialized and which program elements should be included in each specialized procedure. We formalize the specialization-slicing problem as a partitioning problem on the elements of the possibly infinite unrolled program. To manipulate possibly infinite sets of program elements, the algorithm makes use of automata-theoretic techniques originally developed in the model-checking community. The algorithm returns a finite answer that is optimal (with respect to a criterion defined in the article). In particular, (i) each element replicated by the specialization-slicing algorithm provides information about specialized patterns of program behavior that are intrinsic to the program, and (ii) the answer is of minimal size (i.e., among all possible answers with property (i), there is no smaller one). The specialization-slicing algorithm provides a new way to create executable slices. Moreover, by combining specialization slicing with forward slicing, we obtain a method for removing unwanted features from a program. While it was previously known how to solve the feature-removal problem for single-procedure programs, it was not known how to solve it for programs with procedure calls.

Four research-supported teaching methods can make your computing courses more effective through improved student learning, comprehension, and motivation.

Debugging often involves 1) finding the point of failure (the first statement that produces bad output) and 2) finding and fixing the actual bug. Print statements and debugger break points can help with step 1. Slicing the program back from values used at the point of failure can help with step 2. However, neither approach is ideal: Debuggers and print statements can be clumsy and time-consuming and backward slices can be almost as large as the original program. This paper addresses both problems. We present callstack-sensitive slicing, which reduces slice sizes by leveraging the series of calls active when a program fails. We also show how slice intersections may further reduce slice sizes. We then describe a set of tools that identifies points of failure for programs that produce bad output. Finally, we apply our point-of-failure tools to a suite of buggy programs and evaluate callstack-sensitive slicing and slice intersection as applied to debugging. Callstack-sensitive slicing is very effective: On average, a callstack-sensitive slice is about 0.31 time the size of the corresponding full slice, down to just 0.06 time in the best case. Slice intersection is less impressive, on average, but may sometimes prove useful in practice.

This paper describes the implementation and evaluation of a program that uses active recruiting and peer-led team learning to try to increase the participation and success of women and minority students in undergraduate computer science. These strategies were applied at eight universities starting in the fall of 2004. There have been some impressive results: We succeeded in attracting under-represented students who would not otherwise have taken a CS course.Evaluation shows that participation in our program significantly improves retention rates and grades, especially for women.Students in the program, as well as the students who served as peer leaders, are uniformly enthusiastic about their experience.

Exceptions are the preferred method for error handling in object-oriented languages like Java. Current program-slicing algorithms do not correctly deal with exception-handling constructs, because they do not account for the additional control and data dependences introduced by exceptions. This paper extends previous work on program slicing using the system dependence graph (SDG) to support slicing programs with exceptions.

Writes via unchecked pointer dereferences rank high among vulnerabilities most often exploited by malicious code. The most common attacks use an unchecked string copy to cause a buffer overrun, thereby overwriting the return address in the function's activation record. Then, when the function "returns", control is actually transferred to the attacker's code. Other attacks may overwrite function pointers, setjmp buffers, system-call arguments, or simply corrupt data to cause a denial of service.A number of techniques have been proposed to address such attacks. Some are limited to protecting the return address only; others are more general, but have undesirable properties such as having a high runtime overhead, requiring manual changes to the source code, or forcing programmers to give up control of data representations and memory management.This paper describes the design and implementation of a security tool for C programs that addresses all these issues: it has a low runtime overhead, does not require source code modification by the programmer, does not report false positives, and provides protection against a wide range of attacks via bad pointer dereferences, including but not limited to buffer overruns and attempts to access previously freed memory. The tool uses static analysis to identify potentially dangerous pointer dereferences, and memory locations that are legitimate targets of these pointers. Dynamic checks are then inserted; if at runtime the target of an unsafe dereference is not in the legitimate set, a potential security violation is reported, and the program is halted.

Procedure extraction is an important program transformation that can be used to make programs easier to understand and maintain, to facilitate code reuse, and to convert “monolithic” code to modular or object-oriented code. Procedure extraction involves the following steps:

Type casting allows a program to access an object as if it had a type different from its declared type. This complicates the design of a pointer-analysis algorithm that treats structure fields as separate objects; therefore, some previous pointer-analysis algorithms "collapse" a structure into a single variable. The disadvantage of this approach is that it can lead to very imprecise points-to information. Other algorithms treat each field as a separate object based on its offset and size. While this approach leads to more precise results, the results are not portable because the memory layout of structures is implementation dependent. This paper first describes the complications introduced by type casting, then presents a tunable pointer-analysis framework for handling structures in the presence of casting. Different instances of this framework produce algorithms with different levels of precision, portability, and efficiency. Experimental results from running our implementations of f...

A pointer-analysis algorithm can be either flow-sensitive or flow-insensitive. While flow-sensitive analysis usually provides more precise information, it is also usually considerably more costly in terms of time and space. The main contribution of this paper is the presentation of another option in the form of an algorithm that can be 'tuned' to provide a range of results that fall between the results of flow-insensitive and flow-sensitive analysis. The algorithm combines a flow-insensitive pointer analysis with static single assignment (SSA) form and uses an iterative process to obtain progressively better results.

In order to analyze a program that involves pointers, it is necessary to have (safe) information about what each pointer points to. There are many different approaches to computing points-to information. This paper addresses techniques for flow- and context-insensitive interprocedural analysis of stack-based storage.The paper makes two contributions to work in this area: - The first contribution is a set of experiments that explore the trade-offs between techniques previously defined by Lars Andersen and Bjarne Steensgaard. The former has a cubic worst-case running time, while the latter is essentially linear. However, the former may be much more precise than the latter. We have found that in practice, Andersen's algorithm is consistently more precise than Steensgaard's. For small programs, there is very little difference in the times required by the two approaches; however, for larger programs, Andersen's algorithm can be much slower than Steensgaard's. - The second contribution is the definition of two new algorithms. The first algorithm can be "tuned" so that its worst-case time and space requirements, as well as its accuracy range from those of Steensgaard to those of Andersen. We have experimented with several versions of this algorithm; one version provided a significant increase in accuracy over Steensgaard's algorithm, while keeping the running time within a factor of two. The second algorithm uses the first as a subroutine. Its worst-case time and space requirements are a factor of log N (where N is the number of variables in the program) worse than those of Steensgaard's algorithm. In practice, it appears to run about ten times slower than Steensgaard's algorithm; however it is significantly more accurate than Steensgaard's algorithm, and significantly faster than Andersen's algorithm on large programs.

Determining aliases is one of the foundamental static analysis problems, in part because the precision with which this problem is solved can affect the precision of other analyses such as live variables, available expressions, and constant propagation. Previous work has investigated the complexity of flow-sensitive alias analysis. In this article we show that precise flow- insensitive may-alias analysis is NP-hard given arbitrary levels of pointers and arbitrary pointer dereferencing.

The paper shows how a large class of interprocedural dataflow-analysis problems can be solved precisely in polynomial time by transforming them into a special kind of graph-reachability problem. The only restrictions are that the set of dataflow facts must be a finite set, and that the dataflow functions must distribute over the confluence operator (either union or intersection). This class of probable problems includes—but is not limited to—the classical separable problems (also known as “gen/kill” or “bit-vector” problems)—e.g., reaching definitions, available expressions, and live variables. In addition, the class of problems that our techniques handle includes many non-separable problems, including truly-live variables, copy constant propagation, and possibly-uninitialized variables.

article Demand interprocedural dataflow analysis Share on Authors: Susan Horwitz Computer Sciences Department, Univ. of Wisconsin, 1210 W. Dayton Street, Madison, WI Computer Sciences Department, Univ. of Wisconsin, 1210 W. Dayton Street, Madison, WIView Profile , Thomas Reps Computer Sciences Department, Univ. of Wisconsin, 1210 W. Dayton Street, Madison, WI Computer Sciences Department, Univ. of Wisconsin, 1210 W. Dayton Street, Madison, WIView Profile , Mooly Sagiv Computer Sciences Department, Univ. of Wisconsin, 1210 W. Dayton Street, Madison, WI and IBM Scientific Center, Haifa, Israel Computer Sciences Department, Univ. of Wisconsin, 1210 W. Dayton Street, Madison, WI and IBM Scientific Center, Haifa, IsraelView Profile Authors Info & Claims ACM SIGSOFT Software Engineering NotesVolume 20Issue 4Oct. 1995 pp 104–115https://doi.org/10.1145/222132.222146Online:01 October 1995Publication History 150citation853DownloadsMetricsTotal Citations150Total Downloads853Last 12 Months37Last 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 AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

Given a program Base and two variants, A and B, each created by modifying separate copies of Base, the goal of program integration is to determine whether the modifications interfere, and if they do not, to create an integrated program that incorporates both sets of changes as well as the portions of Base preserved in both variants. Text-based integration techniques, such as the one used by the Unix diff3 utility, are obviously unsatisfactory because one has no guarantees about how the execution behavior of the integrated program relates to the behaviors of Base, A, and B. The first program integration algorithm to provide such guarantees was developed by Horwitz, Prins, and Reps. However, a limitation of that algorithm is that it only applied to programs written in a restricted language—in particular, the algorithm does not handle programs with procedures. This article describes a generalization of the Horwitz-Prins-Reps algorithm that handles programs that consist of multiple (and possibly mutually recursive) procedures. We show that two straightforward generalizations of the Horwitz-Prins-Reps algorithm yield unsatisfactory results. The key issue in developing a satisfactory algorithm is how to take into account different calling contexts when determining what has changed in the variants A and B. Our solution to this problem involves identifying two different kinds of affected components of A and B: those affected regardless of how the procedure is called, and those affected by a changed or new calling context. The algorithm makes use of interprocedural program slicing to identify these components, as well as components in Base, A, and B with the same behavior.

Program slicing is a fundamental operation for many software engineering tools. Currently, the most efficient algorithm for interprocedural slicing is one that uses a program representation called the system dependence graph. This paper defines a new algorithm for slicing with system dependence graphs that is asymptotically faster than the previous one. A preliminary experimental study indicates that the new algorithm is also significantly faster in practice, providing roughly a 6-fold speedup on examples of 348 to 757 lines.

Program dependence graphs have been proposed for use in optimizing, vectorizing, and parallelizing compilers, and for program integration. This paper proposes their use as the basis for incremental program testing when using test data adequacy criteria. Test data adequacy is commonly used to provide some confidence that a particular test suite does a reasonable job of testing a program. Incremental program testing using test data adequacy criteria addresses the problem of testing a modified program given an adequate test suite for the original program. Ideally, one would like to create an adequate test suite for the modified program that reuses as many files from the old test suite as possible. Furthermore, one would like to know, for every file that is in both the old and the new test suites, whether the program components exercised by that file have been affected by the program modification; if no components have been affected, then it is not necessary to rerun the program using that file.In this paper we define adequacy criteria based on the program dependence graph, and propose techniques based on program slicing to identify components of the modified program that can be tested using files from the old test suite, and components that have been affected by the modification. This information can be used to reduce the time required to create new test files, and to avoid unproductive retesting of unaffected components. Although exact identification of the components listed above is, in general, undecidable, we demonstrate that our techniques provide safe approximations.

Article The use of program dependence graphs in software engineering Share on Authors: Susan Horwitz View Profile , Thomas Reps View Profile Authors Info & Claims ICSE '92: Proceedings of the 14th international conference on Software engineeringJune 1992 Pages 392–411https://doi.org/10.1145/143062.143156Online:01 June 1992Publication History 107citation1,247DownloadsMetricsTotal Citations107Total Downloads1,247Last 12 Months31Last 6 weeks3 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 AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

Given a program Base and two variants, A and B , each created by modifying separate copies of Base , the goal of program integration is to determine whether the modifications interfere, and if they do not, to create an integrated program that includes both sets of changes as well as the portions of Base preserved in both variants. Text-based integration techniques, such as the one used by the Unix diff 3 utility, are obviously unsatisfactory because one has no guarantees about how the execution behavior of the integrated program relates to the behaviors of Base , A , and B . The first program-integration algorithm to provide such guarantees was developed by Horwitz et al.[13]. However, a limitation of that algorithm is that it incorporates no notion of semantics-preserving transformations. This limitation causes the algorithm to be overly conservative in its definition of interference. For example, if one variant changes the way a computation is performed (without changing the values computed) while the other variant adds code that uses the result of the computation, the algorithm would classify those changes as interfering. This paper describes a new integration algorithm that is able to accommodate semantics-preserving transformations.

Text-based file comparators (e.g., the Unix utility diff), are very general tools that can be applied to arbitrary files. However, using such tools to compare programs can be unsatisfactory because their only notion of change is based on program text rather than program behavior. This paper describes a technique for comparing two versions of a program, determining which program components represents changes, and classifying each changed component as representing either a semantic or a textual change.

The notion of a program slice , originally introduced by Mark Weiser, is useful in program debugging, automatic parallelization, and program integration. A slice of a program is taken with respect to a program point p and a variable x ; the slice consists of all statements of the program that might affect the value of x at point p . This paper concerns the problem of interprocedural slicing—generating a slice of an entire program, where the slice crosses the boundaries of procedure calls. To solve this problem, we introduce a new kind of graph to represent programs, called a system dependence graph , which extends previous dependence representations to incorporate collections of procedures (with procedure calls) rather than just monolithic programs. Our main result is an algorithm for interprocedural slicing that uses the new representation. (It should be noted that our work concerns a somewhat restricted kind of slice: rather than permitting a program to b e sliced with respect to program point p and an arbitrary variable, a slice must be taken with respect to a variable that is defined or used at p .) The chief difficulty in interprocedural slicing is correctly accounting for the calling context of a called procedure. To handle this problem, system dependence graphs include some data dependence edges that represent transitive dependences due to the effects of procedure calls, in addition to the conventional direct-dependence edges. These edges are constructed with the aid of an auxiliary structure that represents calling and parameter-linkage relationships. This structure takes the form of an attribute grammar. The step of computing the required transitive-dependence edges is reduced to the construction of the subordinate characteristic graphs for the grammar's nonterminals.

Our concern is how to determine data dependencies between program constructs in programming languages with pointer variables. We are particularly interested in computing data dependencies for languages that manipulate heap-allocated storage, such as Lisp and Pascal. We have defined a family of algorithms that compute safe approximations to the flow, output, and anti-dependencies of a program written in such a language. Our algorithms account for destructive updates to fields of a structure and thus are not limited to the cases where all structures are trees or acyclic graphs; they are applicable to programs that build cyclic structures.

The need to integrate several versions of a program into a common one arises frequently, but it is a tedious and time consuming task to integrate programs by hand. To date, the only available tools for assisting with program integration are variants of text-based differential file comparators; these are of limited utility because one has no guarantees about how the program that is the product of an integration behaves compared to the programs that were integrated. This paper concerns the design of a semantics-based tool for automatically integrating program versions. The main contribution of the paper is an algorithm that takes as input three programs A , B , and Base , where A and B are two variants of Base . Whenever the changes made to Base to create A and B do not “interfere” (in a sense defined in the paper), the algorithm produces a program M that integrates A and B . The algorithm is predicated on the assumption that differences in the behavior of the variant programs from that of Base , rather than differences in the text , are significant and must be preserved in M . Although it is undecidable whether a program modification actually leads to such a difference, it is possible to determine a safe approximation by comparing each of the variants with Base . To determine this information, the integration algorithm employs a program representation that is similar (although not identical) to the dependence graphs that have been used previously in vectorizing and parallelizing compilers. The algorithm also makes use of the notion of a program slice to find just those statements of a program that determine the values of potentially affected variables. The program-integration problem has not been formalized previously. It should be noted, however, that the integration problem examined here is a greatly simplified one; in particular, we assume that expressions contain only scalar variables and constants, and that the only statements used in programs are assignment statements, conditional statements, and while-loops.

The need to integrate several versions of a program into a common one arises frequently, but it is a tedious and time consuming task to integrate programs by hand. The main contribution of this paper is an algorithm, called integrate, that takes as input three programs A, B, and Base, where A and B are two variants of Base. Whenever the changes made to Base to create A and B do not “interfere” (in a sense defined in the paper), Integrate produces a program M that integrates A and B.

Program dependence graphs were introduced by Kuck as an intermediate program representation well suited for performing optimizations, vectorization, and parallelization. There are also additional applications for them as an internal program representation in program development environments.

The ability to generate language-based editors depends on the existence of a powerful, language-independent model of editing. A model is proposed in which programs are represented as attributed abstract-syntax trees with an associated relational database. Relations can depend on the state of the attributed tree, and attributes can depend on the values in relations, provided there are no circular dependencies. The power and the limitations of relational operations are demonstrated with respect to the support of static-semantic checking, anomaly detection, an interrogation facility, and the ability to define alternative program displays. The advantages of the hybrid system over both the purely relational and purely attribute-based systems are presented, and new algorithms are given for query evaluation and incremental view updating motivated by the efficiency requirements of interactive editing under the defined model. A prototype implementation of an editor generator is described, and suggestions for future research are made.