https://www.mdu.se/

Program slicing identifies the program parts that may affect certain properties of the program, such as the outcomes of conditions affecting the program flow. Ottenstein’s Program Dependence Graph (PDG) based algorithm is the state-of-practice for static slicing today: it is well-suited in applications where many slices are computed, since the cost of building the PDG then can be amortized over the slices. But there are applications that require few slices of a given program, and where computing all the dependencies may be unnecessary. We present a light-weight interprocedural algorithm for backward static slicing where the data dependence analysis is done using a variant of the Strongly Live Variables (SLV) analysis. This allows us to avoid building the Data Dependence Graph, and to slice program statements “on-the-fly” during the SLV analysis which is potentially faster for computing few slices. Furthermore we use an abstract interpretation-based value analysis to extend our slicing algorithm to slice low-level code, where data dependencies are not evident due to dynamically calculated addresses. Our algorithm computes slices as sets of Control Flow Graph nodes: we show how to adapt existing techniques to generate executable slices that correspond to semantically correct code, where jump statements have been inserted at appropriate places. We have implemented our slicing algorithms, and made an experimental evaluation comparing them with the standard PDG-based algorithm for a number of example programs. We obtain the same accuracy as for PDG-based slicing, sometimes with substantial improvements in performance.

Static program slicing is a technique to detect the program parts (i.e. the “slice”) of the given program possibly affecting a given property. The technique is of interest for analysing safety-critical software, since it can identify the program parts that may affect various safety properties. Verification efforts can then be directed towards those parts, leading to a more efficient verification process. We have developed a novel method for static backward program slicing. The method works for well-structured programs, as commonly demanded by coding standards for safety-critical software. It utilises the program structure to obtain a highly efficient slicing process, where control dependencies are inferred from the program structure, and the slicing is done on-the-fly concurrently with the data dependence analysis. We have evaluated our method experimentally. For applications that require few slices to be taken, like checking for a set of safety properties, we obtain large speedups as compared with the standard method for static backward program slicing. We have also investigated how the speedup varies with various parameters such as code size, size of the slice relative to the full program, and relative frequency of conditions in the code.

Backward program slicing identifies the program parts that might influence a particular variable at a program point. A program part (e.g., a statement) can be directly influenced by another part due to its data or control dependence on the later. The classical program slicing approaches are designed to find in advance all the data and control dependencies in the program. This design entails a considerable amount of unnecessary computations because not all the dependencies are required for computing the slice. Demand-driven program slicing approaches try to raise the analysis performance by avoiding the unnecessary computations. However, these approaches cannot address unstructured programs in a demand-driven fashion. On the other hand, the existing techniques that compute the control dependencies in unstructured programs are based on fixed-point iterations, which limits their integration to the demand-driven slicing approaches. Program slicing based on Predicate Code Block (PCB) is a new demand-driven slicing approach that can address only structured programs. This paper presents the first demand-driven technique to compute the control dependencies in unstructured programs. In this regard, the technique uses flow information, location-based information and syntactic structure of the source code. Further, the paper shows how the new technique can be integrated to the PCB-based slicing approach to address unstructured programs.

State-of-practice techniques in static program analysis mainly depend on constructing intermediate data structures, primarily graphs, to facilitate various analyses. However, these structures introduce significant computational overhead in terms of time and space. One key static analysis technique is the computation of control dependencies,which plays a crucial role in optimizing compilers, program slicing, debugging, and parallelization by determining the execution order of statements based on conditional branches. In this paper, we present an improved technique for computing control dependencies without requiring any intermediate graph-based representations. Our approach eliminates unnecessary computations, significantly reducing resource consumption while maintaining accuracy. Experimental evaluations demonstrate that our method not only outperforms classical techniques in terms of execution speed but also exhibits superior scalability and stability when applied to large-scale programs. These findings suggest that our approachis a viable alternative to conventional methods, offering a more efficient solution for static program analysis in modern software engineering.