Finding Feasible Counter-examples when Model Checking Abstracted Java Programs

Corina S. Pasareanu, Matthew B. Dwyer, Willem Visser

Abstract

Model checking Java programs often requires "abstracting" the code to avoid state explosion, but this introduces "spurious" counter-examples (false alarms). This paper introduces two automated techniques—choose-free search and guided concrete simulation—to filter out these fakes and pinpoint real, feasible bugs in complex, multi-threaded Java applications.

The Challenge of Abstraction

Model checking is a powerful way to prove a program is correct, but it faces a massive hurdle: the state explosion problem. For any non-trivial program, the number of possible states is so astronomical that a computer can't check them all.

To solve this, researchers use abstraction. By simplifying data (e.g., treating all positive integers as just "positive"), they create a smaller, "over-approximated" model. If this simplified model is safe, the original program is safe.

An example of an abstraction table for sign-based arithmetic.

However, as shown in the abstraction table above, operations like adding a positive and negative number result in a set of possible values {zero, pos, neg}. This introduces non-determinism. If the model checker finds an error (a "counter-example"), it might be a spurious one—a behavior that exists in the simplified model but is physically impossible in the real Java code. Manually figuring out if a bug is real or just a side effect of abstraction is tedious and error-prone. This paper aims to automate that "reality check."

Methodology: The Integrated Framework

The authors integrated two main techniques into Java PathFinder (JPF), an explicit-state model checker, working alongside the Bandera abstraction toolset.

The integrated framework for abstraction, model checking, and simulation.

The framework follows a structured path as illustrated in the flowchart above. Bandera creates an abstract program and property, which JPF then checks. If a counter-example is found, the system uses "Choose-free" search or "Guided Simulation" to determine if the bug is real or if the abstraction needs refinement.

Key Techniques

When programs are abstracted, specific values are often replaced with nondeterministic choices (using a function like Verify.choose()). The authors proved a key theorem: if a path in the abstracted program contains no nondeterministic choices, that path is guaranteed to exist in the real program. They modified JPF to perform a "choose-free" search, which ignores any path that hits a nondeterministic branch, effectively hunting only for "guaranteed real" bugs.

2. Abstract Counter-example Guided Concrete Simulation

If the model checker finds an error in the abstracted program, it produces a "trace" (a sequence of executed lines and thread schedules). The authors use this abstract trace as a map to guide a simulation of the original, concrete Java program. If the concrete program can follow that exact map and hit the same error, the bug is confirmed as feasible. If the concrete program hits a "mismatch" (e.g., a branch goes left when the map says go right), the counter-example is flagged as spurious.

Evaluation and Results

The authors evaluated their approach on four multi-threaded Java systems: RAX (NASA spacecraft control), Pipeline, RWVSN, and DEOS (avionics kernel). The techniques were highly effective at reducing the manual effort of debugging:

  • Efficiency: In the DEOS example, the standard abstract search found an error in 471 steps, but the choose-free search found a shorter, guaranteed-feasible error in just 312 steps.
  • Feasibility Confirmation: For the RAX system, the tool initially found a spurious 39-step error. By refining the abstraction and using guided simulation, they eventually found a 128-step feasible counter-example that represented a real deadlock.
  • Shorter Traces: Choose-free searches consistently produced shorter, more readable counter-examples, making it easier for engineers to understand the root cause of the failure.

Conclusion

The "Choose-Free" shortcut and automated guided simulation represent a significant step toward making model checking practical for real-world Java development. By specifically looking for paths where the abstraction didn't lose information, developers can find real bugs much faster. While future work remains in automating abstraction refinement, these tools allow the model checker to "double-check" itself against the source code, significantly reducing the burden on human engineers.

Summary updated

BibTeX
@inproceedings{pasareanu2001finding,
  author = {Corina S. Pasareanu and Matthew B. Dwyer and Willem Visser},
  title = {{Finding Feasible Counter-examples when Model Checking Abstracted Java Programs}},
  booktitle = {TACAS},
  year = {2001},
  doi = {10.1007/3-540-45319-9\_20},
}

Loading related content...

Figure