Validating structural properties of nested objects

Darrell Reimer, Edith Schonberg, Kavitha Srinivas, Harini Srinivasan, Julian Dolby, Aaron Kershenbaum, Larry KovedOOPSLA Companion 2004 · DOI

TL;DR

This paper introduces SABER, a static analysis tool that uses a customizable "bad store template" to detect subtle runtime errors in J2EE applications. By focusing on structural violations of data storage rules within nested objects, SABER identifies critical defects that often evade traditional testing, leading to significant improvements in software reliability.

What Problem Does This Paper Address?

Modern enterprise applications heavily rely on frameworks like J2EE to accelerate development and promote code reuse. However, these frameworks introduce complex rules and assumptions about how data structures should be used. Programmers, even experienced ones, can inadvertently violate these rules, leading to hard-to-diagnose runtime errors such as data loss, corruption, or race conditions. These errors are particularly insidious because they often manifest infrequently, only appearing under specific load conditions or after extended operation, making them difficult to catch during development and testing. Existing static analysis tools often lack the specificity to enforce these framework-specific structural rules, leaving a critical gap in ensuring the robustness of these complex systems.

Methods

The core of SABER's approach is a generic, customizable "bad store template." This template defines a class of rules that prohibit storing objects with certain properties into data structures rooted at other objects with specific properties. Individual rules are created by instantiating this template with concrete properties for objects (O), fields (F), and methods (M).

The analysis itself relies on:

  • Call Graph (CG): To understand program execution flow and identify reachable methods.
  • Field-Sensitive Points-to Graph (PTG): To track object references and their relationships, crucial for understanding nested data structures.
  • Store Operations Mapping: To identify where data is being written to fields.
  • Store Values Mapping: To determine what objects are being stored.

The algorithm traverses the PTG, starting from "root fields" (fields that match the rule's properties) and identifies "bad objects" (objects that match the rule's object properties) reachable from these root fields. It then traces the indirect stores to "leaf fields" and the corresponding "leaf operations" (the actual assignment statements).

To combat false positives, SABER employs:

  • Filtering: Rules can specify properties to exclude certain objects or fields.
  • Callback Filters: Custom code can be written to implement more complex filtering logic.
  • Context Sensitivity: The analysis can be made more precise by distinguishing between different calls to methods (method sensitivity) and different allocations of the same class (class sensitivity), including receiver-based sensitivity for container classes.

Datasets

Not discussed in the paper. The paper focuses on applying its analysis to four commercially deployed J2EE applications.

Key Insights and Ideas

  • Frameworks introduce subtle but critical structural rules: The paper highlights that many runtime errors stem not from basic Java syntax errors, but from violating implicit or explicit rules of the frameworks used.
  • A generic template is powerful for rule definition: The "bad store template" provides a flexible and understandable way to define a wide range of structural constraints, making the analysis tool adaptable to different frameworks and custom rules.
  • Static analysis can be effective for deep nesting: By using a field-sensitive points-to graph, SABER can analyze deeply nested object structures, which are common in enterprise applications and often hide defects.
  • False positives are a major challenge, and filtering is key: The paper emphasizes the importance of sophisticated filtering techniques (including custom callbacks and context sensitivity) to make static analysis practical and useful.
  • Context sensitivity is crucial for accuracy: Differentiating between various allocation sites and receiver objects (especially for container classes) significantly reduces false positives by providing a more precise view of object relationships.

Key Results

  • SABER identified over 200 "bad stores" across four commercially deployed J2EE applications.
  • These defects were found in applications with object nesting depths of up to 78 levels.
  • The analysis detected both non-serializable data stored in HttpSessions and race conditions due to inappropriate stores to shared state (Servlet instance fields and static fields).
  • The false positive rate was reduced to an average of 22% using various filtering techniques.
  • Adding selective context sensitivity for specific classes (like java.math.BigDecimal) could further reduce false positives by up to 53.
  • For race conditions, 80% occurred in code without explicit synchronization, highlighting the need for static analysis even in seemingly safe code.

Limitations and Future Work

  • Soundness vs. Scalability: The authors acknowledge that their algorithm is not perfectly sound (i.e., it might miss some errors) due to the use of filtering heuristics, prioritizing scalability for large J2EE applications.
  • False Positives from Container Patterns: While receiver-based sensitivity helps, container patterns in certain J2EE classes can still lead to false positives. The paper suggests that automatically identifying where to apply this precision is an open challenge.
  • Application Usage Knowledge: Some false positives arise from a lack of understanding of how an application specifically uses certain components (e.g., a thread-safe class used in a single-threaded context).
  • Synchronization Approximation: The analysis of synchronization is not perfect, leading to some false positives in race condition detection.
  • Future Work: The authors suggest that their technique can be applied to other frameworks beyond J2EE. They also implicitly point to the need for better automatic context sensitivity selection and more sophisticated synchronization analysis.

Summary updated

BibTeX
@inproceedings{reimer2004validating,
  author = {Darrell Reimer and Edith Schonberg and Kavitha Srinivas and Harini Srinivasan and Julian Dolby and Aaron Kershenbaum and Larry Koved},
  title = {{Validating structural properties of nested objects}},
  booktitle = {OOPSLA Companion},
  year = {2004},
  doi = {10.1145/1028664.1028774},
}
Figure