TL;DR
This paper introduces "abstract slicing," a novel program slicing technique that enhances precision and reduces slice size by incorporating abstract interpretation and model checking. By moving beyond traditional flow graphs to abstract state graphs, it allows for slicing based on specific variable values and execution constraints, offering more targeted and informative program analysis.
What Problem Does This Paper Address?
Program slicing is a powerful technique for understanding and debugging software by identifying program parts relevant to a specific point or condition. Traditional "static slicing" relies on program flow graphs, which are often too coarse. This leads to two main issues:
- Imprecision: Static slicing can't tell you under which variable values a program point affects another. It only tells you if it affects it, leading to potentially large and unhelpful slices.
- Size: Static slicing considers all possible program executions, often resulting in slices that are not significantly smaller than the original program, diminishing their utility.
The authors aim to address these shortcomings by developing a more precise and compact slicing method that can account for specific execution conditions and variable states.
Methods
The paper proposes "abstract slicing," which builds upon static slicing by integrating two key techniques:
- Abstract Interpretation (Predicate Abstraction): Instead of a program's flow graph, abstract slicing uses an "abstract state graph." This graph is generated by applying predicate abstraction to the program. Predicate abstraction uses a set of user-defined predicates (boolean conditions on program variables) to create a finite, sound abstraction of the program's behavior. This allows the analysis to reason about program states in terms of these predicates, rather than concrete values.
- Model Checking (CTL): The core computation for abstract slicing is reduced to a "least fixpoint computation" over formulas in the Computation Tree Logic (CTL). This means that instead of directly computing slices, the problem is translated into a model checking problem. This allows the use of existing symbolic model checkers (like NuSMV) as efficient engines for performing abstract slicing.
The authors define three forms of abstract slicing: backward, forward, and chopping, analogous to their static counterparts but operating on the abstract state graph and incorporating predicates and constraints. Constraints can further limit the scope of analysis to specific execution paths or conditions.
Datasets
Not discussed in the paper. The experiments were conducted using program modules selected from the Collected Algorithms by the ACM (http://www.acm.org/calgo).
Key Insights and Ideas
- Abstract Slicing for Precision: By using predicate abstraction, abstract slicing can answer more nuanced questions like "under which specific predicate values does program point X affect program point Y?" This is a significant improvement over static slicing's binary "yes/no" answer.
- Model Checking as a Computation Engine: Reducing abstract slicing to a CTL fixpoint computation elegantly leverages the power of symbolic model checkers. This offloads the complex fixpoint computation to mature, efficient tools, avoiding the state explosion problem that plagues direct graph-based approaches.
- Constraints for Targeted Analysis: The ability to incorporate constraints (e.g., "only consider executions where y > x") allows users to tailor the slicing process to specific scenarios, further reducing slice size and increasing relevance.
- Static Slicing as a Special Case: The proposed framework naturally encompasses static slicing as a special case where no predicates or constraints are used.
Key Results
The paper demonstrates the feasibility of abstract slicing through a prototype implementation. Key findings include:
- Precision Improvement: Abstract slicing can provide more precise information about program dependencies, as illustrated by examples showing how specific predicates (like
y > x) influence whether one program point affects another. - Performance: Experiments using NuSMV showed that abstract slicing could be performed within reasonable time and memory limits, even with a significant number of predicates. While the number of reachable states in abstract state graphs can grow exponentially, symbolic model checking helps manage this.
- Monolithic vs. Partitioned Fixpoints: The study compared monolithic (single fixpoint computation) and partitioned (multiple fixpoint computations based on program points) approaches. While hypothesized to be more demanding, the experiments showed no significant performance differences between them for the tested programs.
Limitations and Future Work
The authors acknowledge several limitations and suggest future research directions:
- Interprocedural and Object-Oriented Programs: Extending abstract slicing to handle interprocedural calls, global variables, and object-oriented features (like recursion and inheritance) is a significant challenge.
- Requirements Specifications: Applying abstract slicing to higher-level specifications written in languages like Statecharts or SDL, which involve hierarchy, concurrency, and communication, is another promising avenue.
- Language Independence: While the temporal logic approach is generally language-independent, adapting it to the specific constructs of various languages will require further work.
- Completeness: Abstract slicing is sound but not complete, meaning it might miss some affections that occur in actual executions.
Summary updated