Case Study: Finding Real Concurrency Bugs with LLP Predicate Detection
Table of Contents
- Overview
- Case Study 1: Data Races in Boruvka's Minimum Spanning Tree
- 2.1 The Algorithm
- 2.2 The Bug
- 2.3 Detection Results
- 2.4 Root Cause Analysis
- 2.5 The Fix
- Case Study 2: Buffer Overflow in a Concurrent Writer
- Case Study 3: Lost Updates in a Racy Counter
- 4.1 The Program
- 4.2 Detection Results
- 4.3 Quantifying the Damage
- 4.4 The Fix
- Case Study 4: Producer-Consumer Queue Without Synchronization
- 5.1 The Program
- 5.2 Detection Results
- 5.3 The Cascading Failure
- 5.4 The Fix
- Comparison: What Traditional Testing Misses
- Reproducing These Results
1. Overview
This document presents four case studies demonstrating the LLP Predicate Detection System's ability to find concurrency bugs that are difficult or impossible to detect through conventional testing. Each case study walks through a real program, explains the bug, shows the detector's output, and analyzes the root cause.
The programs used in these case studies are not contrived examples. The Boruvka MST implementation is a real parallel algorithm from a graduate course project. The buffer overflow, racy counter, and producer-consumer examples are simplified versions of patterns that appear regularly in production concurrent code -- shared mutable arrays, unsynchronized counters, and lock-free queues.
What makes these bugs particularly dangerous is their non-determinism. Running the same program 100 times might produce correct results 98 times and silently corrupt data twice. The LLP detector finds these bugs from a single execution by reasoning about all possible thread interleavings consistent with the observed event ordering.
2. Case Study 1: Data Races in Boruvka's Minimum Spanning Tree
2.1 The Algorithm
Boruvka's algorithm finds the minimum spanning tree (MST) of a weighted graph. It works iteratively: in each round, every connected component finds its cheapest outgoing edge, and these edges are added to the MST. The algorithm terminates when all vertices are in a single component.
The implementation at parallelalgorithms.group9.homework3.llp.boruvka.Boruvka uses Java's parallelStream() to process edges in parallel during the "find cheapest edge" phase. Each thread reads the parent[] array (union-find structure) to determine which component each vertex belongs to, then updates the cheapest[] array with the index of the minimum-weight edge for that component.
2.2 The Bug
The parent[] and cheapest[] arrays are plain int[] arrays, accessed from the ForkJoinPool's worker threads through parallelStream().forEach() with no synchronization. This creates two classes of data races:
Write-write race on
cheapest[]: Two threads processing different edges may both try to updatecheapest[u]for the same component representativeu. One thread's update is silently lost, causing the algorithm to select a non-minimum edge.Read-write race on
parent[]: Thefind()method readsparent[]to traverse the union-find tree whileunion()writes to it. Path compression duringfind()also writes toparent[], creating a read-write race that can corrupt the tree structure.
2.3 Detection Results
Running the detector against the Boruvka edge-processing phase produces the following output:
The detector found 2 data races on the cheapest[] array. The timeline shows the ForkJoinPool worker threads reading parent[] and writing cheapest[] concurrently, with red RACE markers on every event. The contention heat map reveals that cheapest[0] and cheapest[1] are accessed by multiple worker threads with concurrent vector clocks.
Critically, the detector identifies the specific sequence numbers of the racing events and the exact thread names involved. The execution trace file records the complete scheduling path, enabling a developer to understand not just that a race exists, but how the threads interleaved to produce it.
2.4 Root Cause Analysis
The root cause is a fundamental misuse of parallelStream(). Java's parallel streams divide work across the ForkJoinPool's worker threads, which execute concurrently. When the lambda passed to forEach() accesses shared mutable state (the cheapest[] and parent[] arrays), every access is a potential data race.
The issue is subtle because parallelStream() looks syntactically identical to stream(), and the code works correctly with sequential streams. The bug only manifests when the ForkJoin pool assigns the same array element to multiple worker threads -- which depends on the graph structure, the number of available processors, and the pool's work-stealing behavior. This is exactly the kind of bug that passes unit tests on a developer's laptop but causes silent data corruption in production on a 32-core server.
2.5 The Fix
There are two correct approaches:
Option 1: Atomic arrays. Replace int[] cheapest with AtomicIntegerArray and use compareAndSet() to atomically update only if the current value is worse than the proposed value.
AtomicIntegerArray cheapest = new AtomicIntegerArray(numNodes);
// In the parallel forEach:
cheapest.accumulateAndGet(u, edgeIndex, (current, proposed) ->
edges.get(proposed).weight < edges.get(current).weight ? proposed : current);Option 2: Sequential processing. Use stream() instead of parallelStream() if the graph is small enough that parallelism doesn't provide a meaningful speedup. For graphs with fewer than ~10,000 edges, the overhead of the ForkJoinPool often exceeds the benefit of parallelism.
3. Case Study 2: Buffer Overflow in a Concurrent Writer
3.1 The Program
The BufferOverflowDemo program simulates a common pattern in systems programming: multiple threads writing to a shared buffer using a shared write index. The buffer has a fixed size of 4 elements, and two writer threads each attempt to write 3 elements, for a total of 6 writes to a 4-element buffer.
static int[] buffer = new int[4];
static int writeIndex = 0;
// Each thread:
int idx = writeIndex; // Read current index
buffer[idx] = value; // Write to buffer
writeIndex = idx + 1; // Increment index3.2 The Bug: TOCTOU Race Leading to Overflow
The bug is a classic time-of-check-to-time-of-use (TOCTOU) race. Thread A reads writeIndex and gets 2. Thread B also reads writeIndex and gets 2 -- before Thread A has incremented it. Both threads write to buffer[2] (lost update), then both increment writeIndex to 3 (lost increment -- should be 4). The counter is now wrong, and subsequent writes will be placed at incorrect indices.
As the threads continue, the writeIndex falls behind the actual number of writes performed. Eventually, a thread reads writeIndex = 4, which is still within the bounds check if (idx < buffer.length), but because prior increments were lost, there are more writes remaining than buffer slots available. The thread writes to buffer[4] -- one element past the end of the buffer.
3.3 Detection Results
The LLP detector finds 12 violations in 23 milliseconds:
[LLP] Captured 24 events across 2 threads
[LLP] Detection completed in 23ms
[LLP] Found 0 race(s), 12 violation(s)
Violations:
1. BufferOverflow: Concurrent array access + bounds modification:
Writer-1 accesses buffer[0] while Writer-2 modifies writeIndex
2. BufferOverflow: Concurrent array access + bounds modification:
Writer-1 accesses buffer[4] while Writer-2 modifies count
...The detector identifies both the direct out-of-bounds access (buffer[4] when size is 4) and the concurrent array+index race that caused it. The contention heat map shows writeIndex accessed by both threads (6 accesses each) with SHARED status, confirming that the index variable is the root cause of the contention.
3.4 Connecting to RIP Overwrite
In native code (C/C++), writing past the end of a stack-allocated buffer overwrites the saved frame pointer and return address. The LLP detector flags this pattern because the combination of an out-of-bounds array write and a concurrent index modification is precisely the mechanism that produces stack-based buffer overflow exploits.
In the diagram above, buffer[4] overwrites the saved RBP (frame pointer) and buffer[5] would overwrite the return instruction pointer (RIP). While Java's runtime prevents actual memory corruption through ArrayIndexOutOfBoundsException, the detector identifies programs where the logic would produce an overflow in a native context. This is valuable for:
- Java code that interfaces with native libraries via JNI or JNA
- Java programs that are prototypes for eventual C/C++ implementations
- Security auditing of concurrent buffer management code
3.5 The Fix
The fix requires atomically reading the index, checking bounds, writing the element, and incrementing the index as a single indivisible operation:
synchronized (lock) {
if (writeIndex < buffer.length) {
buffer[writeIndex] = value;
writeIndex++;
}
}Alternatively, use an AtomicInteger for the index and compareAndSet() to ensure that only one thread claims each slot:
int idx;
do {
idx = writeIndex.get();
if (idx >= buffer.length) return; // buffer full
} while (!writeIndex.compareAndSet(idx, idx + 1));
buffer[idx] = value;4. Case Study 3: Lost Updates in a Racy Counter
4.1 The Program
The RacyCounter program increments a shared integer counter from 4 threads, each performing 10 increments. The expected final value is 40, but the actual value is consistently lower due to lost updates.
static int counter = 0;
// Each thread, 10 times:
int val = counter; // Read
counter = val + 1; // Write (based on stale read)4.2 Detection Results
The detector captures 160 events across 4 threads and finds 2,244 data races. The contention heat map is striking:
Location Counter-0 Counter-1 Counter-2 Counter-3 Status
RacyCounter.counter ███ 20 ███ 20 ███ 20 ███ 20 RACE(4t)
RacyCounter.buckets[0] ░░░ 6 ░ 4 ░ 4 ░░░ 6 RACE(4t)
RacyCounter.buckets[1] ░░░ 6 ░░░ 6 ░ 4 ░ 4 RACE(4t)Every field is accessed by all 4 threads with concurrent vector clocks. The counter field alone accounts for 80 events (20 per thread: 10 reads + 10 writes), and every inter-thread pair of accesses is a race.
4.3 Quantifying the Damage
The program consistently reports 15-25 lost updates out of 40 expected. The variability itself is diagnostic: a deterministic bug would produce the same wrong answer every time. The fact that the final counter varies between runs confirms that the result depends on thread scheduling, which is the hallmark of a data race.
The execution trace captures the exact scheduling that produced each run's result. By examining the trace, a developer can see where two threads read the same value of counter, both computed val + 1, and both wrote the same result -- losing one increment entirely.
4.4 The Fix
static AtomicInteger counter = new AtomicInteger(0);
// Each thread:
counter.incrementAndGet(); // Atomic read-modify-write5. Case Study 4: Producer-Consumer Queue Without Synchronization
5.1 The Program
The ProducerConsumer program implements a circular buffer queue with 2 producer threads and 2 consumer threads. Producers write items to buffer[tail % size] and increment tail and count. Consumers read from buffer[head % size] and increment head and decrement count. None of these operations are synchronized.
5.2 Detection Results
The detector finds 1,082 data races across 4 fields:
| Field | Races | Threads |
|---|---|---|
count |
412 | All 4 threads (producers increment, consumers decrement) |
tail |
198 | Both producers |
head |
198 | Both consumers |
buffer[i] |
274 | Producers write, consumers read same indices |
The heat map shows count as the most contended field, with all 4 threads reading and writing it concurrently. This is expected: count is the shared variable that coordinates production and consumption, and without synchronization, every access is a race.
5.3 The Cascading Failure
What makes this case study particularly instructive is the cascading nature of the bugs. The race on count causes producers to overfill the buffer (they check count < buffer.length but the stale value of count doesn't reflect recent consumer activity). The race on tail causes two producers to write to the same slot, losing one item. The race on head causes two consumers to read the same slot, processing one item twice.
The detector identifies all three failure modes from a single execution. The execution trace shows the exact scheduling that caused each failure, and the seed value enables reproduction of the same scheduling on the same hardware.
5.4 The Fix
The correct fix depends on performance requirements:
Synchronized queue: Wrap all operations in a single lock. Simple but limits throughput to one operation at a time.
java.util.concurrent.ArrayBlockingQueue: A production-ready bounded queue with separate locks for producers and consumers, plus condition variables for blocking when full or empty.
Lock-free ring buffer: Use AtomicInteger for head and tail, and compareAndSet() loops for producers and consumers. Highest throughput but most complex to implement correctly.
6. Comparison: What Traditional Testing Misses
The following table summarizes what each testing approach would find for each case study:
| Bug | Unit Test | Stress Test | ThreadSanitizer | LLP Detector |
|---|---|---|---|---|
| Boruvka data race | Passes (single thread) | May fail intermittently | Detects (C/C++ only) | Detects: 2 races on cheapest[], parent[] |
| Buffer overflow TOCTOU | Passes (single thread) | Throws AIOOBE sometimes | Detects (C/C++ only) | Detects: 12 violations, concurrent array+index |
| Racy counter | Passes (off by 1-20) | Fails (obviously wrong) | Detects (C/C++ only) | Detects: 2,244 races, heat map shows contention |
| Producer-consumer | Passes (low contention) | May deadlock or lose items | Detects (C/C++ only) | Detects: 1,082 races across 4 fields |
The key advantage of the LLP detector over stress testing is determinism: stress testing might find a bug after 1,000 runs, or it might not find it at all. The LLP detector finds all races from a single execution by reasoning about the causal structure of events, not by hoping for a lucky thread schedule.
The key advantage over ThreadSanitizer is platform independence: ThreadSanitizer is a compile-time instrumentation tool for C/C++ that is not available for Java. The LLP detector works with any Java program on any platform, using pure Java with no native dependencies.
7. Reproducing These Results
All case studies can be reproduced with the following commands:
cd my-app
# Case Study 1: Boruvka MST
mvn -q exec:java -Dexec.mainClass=com.utece.student.llpdetection.LLPMain \
-Dexec.args="com.utece.student.llpdetection.examples.RacyCounter --cli --predicates race"
# Case Study 2: Buffer Overflow
mvn -q exec:java -Dexec.mainClass=com.utece.student.llpdetection.LLPMain \
-Dexec.args="com.utece.student.llpdetection.examples.BufferOverflowDemo --gui --predicates buffer"
# Case Study 3: Racy Counter
mvn -q exec:java -Dexec.mainClass=com.utece.student.llpdetection.LLPMain \
-Dexec.args="com.utece.student.llpdetection.examples.RacyCounter --gui --predicates race"
# Case Study 4: Producer-Consumer
mvn -q exec:java -Dexec.mainClass=com.utece.student.llpdetection.LLPMain \
-Dexec.args="com.utece.student.llpdetection.examples.ProducerConsumer --cli --predicates race"The --gui flag generates an interactive HTML report at llp-report.html. When violations are found, execution traces are saved as llp-trace-*.txt (human-readable) and llp-trace-*.ser (serialized, reloadable).
Due to the non-deterministic nature of thread scheduling, the exact number of races and the specific thread interleavings will vary between runs. However, the types of violations and the locations of the races will be consistent across all runs, because the bugs are structural -- they exist in every execution, even when they don't cause visible failures.
THANK YOU FOR READING! - YOUR'S TRULY
Oblivion Vulnerability Research LLC (c) July 21, 2026