Datalog-based scalable semantic diffing of concurrent programs

Chungha Sung, Shuvendu K. Lahiri, Constantin Enea, Chao Wang

Introduction

Concurrent programming is notoriously difficult because thread interactions are non-deterministic. When a developer modifies a program to fix a race condition or optimize a lock, they must ensure the "semantic difference" between the old and new versions matches their intent. Traditional semantic diffing techniques rely on model checking, which explores every possible thread interleaving. However, this approach suffers from the "state-space explosion" problem, making it prohibitively slow for real-world applications. For instance, prior state-of-the-art tools could take 30 minutes to analyze fewer than 600 lines of code.

Presented at ISSTA 2018, EC-Diff is a tool designed to bridge this gap. By trading absolute precision for speed through Datalog-based static analysis, EC-Diff identifies synchronization differences 10x to 1000x faster than traditional methods, often completing in seconds where prior tools took hours.

The EC-Diff Framework

The core innovation of EC-Diff is the shift from exhaustive state exploration to approximate static analysis powered by Datalog. The framework converts a program's control flow into Datalog "facts" and applies custom inference rules to derive concurrency relations.

The EC-Diff Framework architecture.

As shown in Figure 1, the process begins by lowering programs $P_1$ and $P_2$ into LLVM IR, which is then translated into Datalog facts. These facts, along with predefined inference rules, are processed by the $\mu Z$ Datalog engine in Z3. The engine computes relations such as must-happen-before (mustHB) and may-happen-before (mayHB) to identify semantic differences.

Semantic Diffing via Read-From Edges

EC-Diff defines a semantic difference based on "read-from" (RF) edges—identifying which specific write operation provides the value for a given load operation. A difference exists if an RF edge is possible in one version but not the other.

Semantic difference illustrated by Read-From (RF) edges.

Figure 2 illustrates this concept. In the "Before change" version (a), a load at line 2 might read from a write at line 5. After introducing locks in version (b), this specific interaction may be prevented, creating a semantic difference that EC-Diff can detect. To manage complexity, the authors employ rank-k analysis, which bounds the number of concurrent interactions considered. Since most concurrency bugs involve only a few context switches, low-rank analysis (rank 1-3) is typically sufficient.

Evaluation

The authors evaluated EC-Diff using two primary benchmarks:

  1. Bug Patterns: 41 multithreaded C programs featuring common concurrency issues (locks, condition variables, thread ordering).
  2. Real-world Applications: 6 medium-sized open-source applications (e.g., pbzip2, pfscan) totaling approximately 13,500 lines of code.

Key Results

  • Performance: EC-Diff demonstrated massive speedups, consistently performing 10x to 1000x faster than model-checking baselines. For the rtl8169 benchmark, EC-Diff finished in under a second, while previous tools required nearly 40 minutes.
  • Accuracy and Scalability: Despite its approximate nature, EC-Diff correctly identified human-verified differences in almost all cases. It analyzed the 13,500-line dataset in just 140 seconds, marking a significant milestone for concurrent static analysis.

Discussion and Limitations

The utility of EC-Diff lies in its "Precision vs. Utility" trade-off. While the tool is approximate and may report occasional false positives, it is far more practical for developer workflows than waiting hours for a precise model checker. By using Datalog, the authors express complex concurrency semantics—such as signal-wait pairs—as simple recursive rules, leveraging the power of modern solvers like Z3.

However, EC-Diff has limitations. It currently focuses on data-flow (RF) edges and may miss differences that are purely deadlocks, as seen in the rtl8169-3 benchmark. Furthermore, as an approximate tool, it does not provide formal guarantees of soundness. Future work includes extending Datalog rules to handle deadlocks and more complex synchronization primitives in languages like C++ or Java.

Summary updated

BibTeX
@inproceedings{sung2018datalog,
  author = {Chungha Sung and Shuvendu K. Lahiri and Constantin Enea and Chao Wang},
  title = {{Datalog-based scalable semantic diffing of concurrent programs}},
  booktitle = {ASE},
  year = {2018},
  doi = {10.1145/3238147.3238211},
}
Figure