Abstract
Model checking is a rigorous technique for verifying concurrent object-oriented software, yet its scalability is often hampered by the "state-space explosion" problem. While static program slicing has been proposed as a model reduction strategy, its practical effectiveness on realistic systems has remained largely unquantified. This paper presents a systematic study of slicing for model reduction, utilizing the Indus slicer within the Bandera framework. Our results demonstrate that slicing is a low-overhead, high-impact technique that significantly reduces state space and verification time, often acting independently of other reduction methods like Partial Order Reduction (POR).
Introduction
The primary challenge in software model checking is the exponential growth of possible thread interleavings as program complexity increases. To make verification feasible for non-trivial systems, researchers employ model reduction techniques to simplify the program before analysis. Static program slicing—a method that automatically removes parts of the code that do not affect the specific property being checked (such as a deadlock or an assertion)—is a leading candidate for such reduction.
Despite its theoretical promise, empirical evidence for slicing's efficacy in concurrent Java environments has historically been mixed or based on small examples. This study addresses this gap by evaluating slicing across a diverse suite of concurrent Java applications, ranging from classic synchronization benchmarks to large-scale internet systems.
Methodology: The Indus-Bandera Pipeline
The authors integrated Indus, a sophisticated program slicer, into the Bandera model-checking toolset. The verification workflow follows a structured path:
- Translation: Java source or bytecode is converted into Jimple, a 3-address intermediate representation.
- Property-Directed Slicing: Indus performs a static backward slice starting from a "slicing criterion" (e.g., a specific assertion). It traverses data and control flow dependencies to identify all code segments that could potentially influence that criterion.
- Concurrency-Aware Analysis: Unlike standard slicers, Indus accounts for Java’s complex memory model, including heap-allocated data, object aliasing, and inter-thread interference.
- Model Checking: The reduced program is converted into a model and verified using Bogor, a state-of-the-art model checker.
The study compares slicing against two primary baselines: simple call-graph reachability (removing uncalled methods) and Partial Order Reduction (POR), a standard technique that prunes redundant execution paths.
Experimental Evaluation
The approach was tested on ten multi-threaded Java programs, categorized by complexity:
- Standard Benchmarks: Classic problems like
BBuffer(Bounded Buffer),SBarber(Sleeping Barber), andDining Philosophers. - Simulators:
DiskSchedulerandAlarmClock. - Production-Scale Systems:
RepWorker(data distribution),RayTracer(Java Grande benchmark), andSiena(an Internet-scale event notification system).
These programs included up to 50,000 lines of bytecode, providing a rigorous testbed far beyond the "textbook" examples used in prior research.
Key Insights and Analysis
The "Junk" Factor in Large Systems
A significant finding was that slicing is often more effective on large, realistic programs than on small benchmarks. In small programs, almost every line of code is essential to the core logic. In contrast, large-scale systems contain significant amounts of code—such as logging, complex data processing, or UI logic—that are irrelevant to specific concurrency properties. Slicing effectively strips this away, sometimes reducing the codebase by two orders of magnitude; for instance, the RAX system was reduced from over 34,000 bytecodes to just 101.
Orthogonality with Partial Order Reduction
The study confirms that slicing and POR are "orthogonal" techniques. Slicing reduces the size of the state and the number of transitions by removing irrelevant variables and statements. POR reduces the number of paths explored by avoiding redundant interleavings. Because they target different aspects of the state-space explosion, their benefits are additive, providing a compounding reduction in verification effort.
The Synchronization Skeleton
The researchers observed that slicing for "local" properties (like a single assertion) was not significantly more effective than slicing for "global" properties (like deadlock). In concurrent Java, code is often tightly coupled to the "synchronization skeleton." Once a lock or thread management primitive is included in the slice, the dependencies often pull in a large portion of the related thread logic, regardless of the specific property being checked.
Performance Results
The computational cost of slicing was found to be remarkably low. Even for the largest programs in the dataset, Indus completed the slicing process in under 40 seconds. This overhead is negligible compared to the potential hours or days saved during the model-checking phase. On average, slicing yielded a 4x improvement in total verification time and outperformed simple call-graph pruning by a factor of 2.5x.
Conclusion
This systematic study validates static program slicing as a highly effective and efficient technique for model reduction in concurrent Java software. By removing irrelevant code and reducing state complexity, slicing enables the verification of systems that would otherwise be intractable. Future work will explore more aggressive abstraction techniques to simplify the "synchronization skeleton" and extend slicing methodologies to complex temporal logic properties.
Summary updated