TL;DR
This paper introduces CONDPOR, a novel algorithm that combines concolic execution with dynamic partial order reduction (DPOR) to efficiently find bugs in concurrent Java programs. By simultaneously handling both concurrency and data nondeterminism, CONDPOR significantly outperforms existing methods, offering an exponential speedup on complex concurrent data structures.
What Problem Does This Paper Address?
Concurrent software is notoriously difficult to test due to two main sources of nondeterminism: concurrency (the order in which threads execute) and data (the possible values variables can take). While existing techniques like Dynamic Partial Order Reduction (DPOR) excel at exploring concurrency nondeterminism, they often struggle with data nondeterminism, typically resorting to brute-force enumeration of possible values. This leads to an explosion of the state space, making it infeasible to find bugs in many real-world concurrent programs. This paper addresses the challenge of efficiently exploring both sources of nondeterminism simultaneously to achieve optimal bug detection.
Methods
CONDPOR's core innovation lies in its integration of concolic execution with optimal dynamic partial order reduction (DPOR).
- Dynamic Partial Order Reduction (DPOR): This technique systematically explores different thread interleavings while avoiding redundant explorations. It maintains "scheduling constraints" to ensure that only distinct, non-equivalent executions are explored. The paper leverages an existing optimal DPOR algorithm (TRUST) as a foundation.
- Concolic Execution (CT): This technique combines concrete execution with symbolic execution. It instruments the program to track symbolic constraints on data values encountered during a concrete run. When a symbolic constraint is encountered, CT uses a Satisfiability Modulo Theories (SMT) solver to explore different paths based on the constraint's satisfiability.
- CONDPOR's Integration: CONDPOR maintains symbolic constraints within the execution graphs used by DPOR. This allows it to backtrack not only on scheduling choices but also on data nondeterminism. Crucially, CONDPOR offloads the manipulation of symbolic expressions to the underlying Java runtime by providing symbolic types that "carry" the symbolic path constraint. This avoids the need for a custom interpreter and integrates seamlessly with the JVM.
Datasets
The paper evaluates CONDPOR on:
- Synthetic benchmarks: Derived from SV-COMP's pthread category and two handcrafted benchmarks, designed to highlight the differences between explicit and symbolic handling of data nondeterminism.
- Real-world concurrent data structures: Categorized into data-independent, data-dependent, and nondeterminism-based structures. These include examples like queues, stacks, lists, and elimination-backoff stacks.
Key Insights and Ideas
- Data and Concurrency Bugs are Intertwined: The paper argues that many modern concurrent data structures inherently require reasoning about both concurrency and data nondeterminism to achieve efficiency (e.g., using timestamps or random identifiers). Treating them as orthogonal is insufficient.
- Symbolic Types for Seamless Integration: By using symbolic types that carry path constraints, CONDPOR avoids complex interpreter development and integrates naturally with the JVM. This allows arithmetic and logical operations on symbolic variables to directly influence the exploration.
- Optimality is Preserved: CONDPOR extends the notion of maximal extensions from DPOR to account for constraint evaluation events, ensuring that the combined approach remains optimal and avoids redundant explorations.
- Significant Performance Gains: The combination of concolic execution and DPOR leads to exponential speedups compared to approaches that rely on explicit enumeration of data values.
Key Results
- Exponential Speedup: CONDPOR is shown to be exponentially faster than DPOR with small-domain enumeration, especially for benchmarks with significant data nondeterminism. For instance, in some cases, CONDPOR explores only a few executions while EXEN (an explicit enumeration approach) times out.
- Scalability: CONDPOR scales well to a larger number of threads and complex concurrent data structures, outperforming EXEN in most benchmarks.
- Minimal Overhead: For data-independent tests, CONDPOR adds no significant overhead over vanilla DPOR, demonstrating the efficiency of its symbolic handling. The overhead for data-dependent tests is primarily due to execution graph enumeration rather than constraint solving.
- Sound, Complete, and Optimal: The paper formally proves that CONDPOR is sound (no false positives), complete (explores all behaviors), and optimal (explores each distinct behavior exactly once).
Limitations and Future Work
- Memory Consistency Model: The current implementation of CONDPOR only supports Sequential Consistency (SC). While the algorithm is parametric to memory models, extending the implementation to support weaker models like TSO and PSO is a direction for future work.
- Manual Symbolic API Usage: Users currently need to manually subclass certain input types to capture data nondeterminism. The authors suggest that this could potentially be lifted by data-flow analysis over bytecode.
- Tooling: The implementation is provided as a tool for concurrent Java programs. Further development could focus on broader language support or more advanced features.
Summary updated