Detecting Call Graph Unsoundness without Ground Truth

1. Problem Statement

Java static analysis frameworks (e.g., Soot, WALA, Doop) are critical for security and reliability but are often evaluated under the flawed assumption that analysis algorithms and configurations compose monotonically. In reality, semantic violations—where an analysis produces plausible but incorrect results (e.g., missing call edges)—are subtle, dangerous, and difficult to detect because:

• Lack of Ground Truth: For real-world programs, authoritative "correct" call graphs are unavailable.
• Silent Failures: Unlike crashes or memory leaks, semantic errors (like missing a lambda resolution) do not cause the tool to fail; they simply produce incomplete data, leading to false negatives in vulnerability detection.
• Complex Interactions: Violations often arise not from single algorithmic errors but from complex interactions between analysis algorithms, configuration settings (e.g., field sensitivity, object sensitivity), and modern Java features (lambdas, reflection, invokedynamic).

2. Methodology

The authors propose a ground-truth-free methodology based on metamorphic testing. Instead of comparing results against an external oracle, they validate the internal semantic consistency of frameworks by exploiting expected relationships (partial orders) between analysis variants.

Core Concept: Precision and Soundness Partial Orders

The methodology relies on the theoretical expectation that:

• Precision: A more precise analysis (e.g., Object-Sensitive) should be a subset of a less precise one (e.g., Context-Insensitive) regarding false positives (spurious edges). It should not introduce new edges that were not present in the coarser analysis.
• Soundness: A more sound analysis should be a superset of a less sound one regarding true positives (valid edges). It should not prune valid edges.

The Approach

1. Semantic Contracts: The authors treat partial orders (e.g., $A_{precise} \preceq A_{coarse}$) as testable contracts. A violation occurs if a "more precise" configuration introduces new edges that a "less precise" one missed, or if a "more sound" configuration prunes edges that should be reachable.
2. Implicit Soundness: Since ground truth is unavailable to distinguish true positives from false positives, the authors derive implicit soundness from precision. If $A_1$ is more precise than $A_2$, $A_1$ should not introduce new edges unless they are true positives. If $A_1$ adds edges that $A_2$ lacks, and $A_2$ is theoretically sound, $A_1$ may be unsound (or vice versa).
3. Two-Dimensional Testing:
   • Intra-framework: Testing configurations (e.g., Baseline vs. Field-Sensitive) and algorithms (e.g., CHA vs. RTA) within a single framework.
   • Cross-framework: Comparing equivalent algorithms across different frameworks (e.g., Soot's RTA vs. WALA's RTA) to detect semantic divergence.
4. Normalization: To enable comparison, the authors implemented a pipeline to normalize call graphs (removing memory addresses, resolving internal IDs, and unifying method signatures) to filter out syntactic noise.

3. Key Contributions

• Ground-Truth-Free Detection: A novel methodology to detect semantic inconsistencies in static analysis without requiring labeled ground truth, utilizing partial-order reasoning as an internal oracle.
• Unified Partial-Order Reasoning: Generalizing partial orders to cover not just algorithms, but also algorithm–configuration pairs, exposing synergistic failures where configuration changes amplify algorithmic bugs.
• Large-Scale Empirical Study: The first systematic study of semantic consistency across four major frameworks: Soot, SootUp, WALA, and Doop, using the JCG benchmark (125+ Java programs).
• Identification of Failure Modes: Uncovering that modern Java features (lambdas, reflection, invokedynamic) are primary triggers for semantic violations, often causing frameworks to diverge fundamentally.

4. Key Results

The study evaluated 125+ programs across four frameworks, revealing three major findings:

A. Algorithmic Precision Orders Break Within Frameworks

• Soot: Generally conservative; enabling field/object sensitivity did not significantly alter call graphs compared to the baseline, preserving precision orders.
• WALA: Exhibited significant violations. Enabling Object Sensitivity (OS) introduced ~516 new call edges compared to the baseline, primarily due to speculative reflection handling. WALA's OS mode attempts to infer reflective targets, introducing edges that the baseline (which ignores ambiguous Class.forName) does not, violating the expected precision refinement.
• SootUp: Showed a "soundness inversion" where its RTA implementation resolved valid lambda calls that its CHA implementation missed, contradicting the expectation that CHA is a safe over-approximation of RTA in this context.

B. Configuration Choices Amplify Inconsistencies (Synergistic Failures)

• Interaction Effects: Changing configurations while changing algorithms often produced synergistic failures where the number of violations exceeded the sum of algorithm-only and configuration-only errors.
• Example: In WALA, combining Object Sensitivity (which adds speculative edges) with flow-sensitive analysis (0-CFA) caused data flow to propagate through these speculative edges, reaching methods that were unreachable under the baseline. This created a massive spike in violations (up to 146) that was not present when testing algorithms or configurations in isolation.

C. Irreconcilable Cross-Framework Semantic Gaps

• Fundamental Divergence: Cross-framework comparisons revealed extremely low similarity scores (often <20%) even for "equivalent" algorithms (e.g., Soot RTA vs. WALA RTA).
• Root Causes:
  • Lambda/Invokedynamic: WALA successfully resolves lambda targets via LambdaMetafactory, while Soot and SootUp often treat invokedynamic as opaque or prune the edges, leading to missing execution paths.
  • Reflection: WALA uses heuristics to resolve reflection; Soot treats it conservatively (opaque).
  • Entry Points: Soot includes a broader set of potential entry points (including library code), while WALA is stricter, leading to systematic differences in reachable code.
• Doop: Produced call graphs with ~15,000 edges (due to modeling native/runtime flows) compared to ~150 for others, resulting in near-zero Jaccard similarity, highlighting a fundamental difference in analysis scope rather than just precision.

5. Significance and Implications

• Challenges Evaluation Practices: The paper challenges the prevailing practice of comparing static analysis tools based on single configurations or assuming monotonicity. It demonstrates that "better" configurations can sometimes be less sound or precise in unexpected ways.
• Modern Language Features: Highlights that frameworks are struggling to keep pace with modern Java features (Java 8+), particularly lambdas and reflection, leading to silent semantic failures.
• New Testing Paradigm: Establishes metamorphic testing via partial orders as a viable and necessary approach for validating static analysis tools in the absence of ground truth.
• Practical Ceiling: Reveals a "tractability wall" where higher precision (e.g., 1-Object-Sensitive in Doop) becomes computationally infeasible, meaning theoretical precision lattices often cannot be realized in practice.

In conclusion, the authors argue that assessing static analysis precision and soundness requires a joint reasoning approach that accounts for the complex interplay of algorithms, configurations, and framework-specific semantic models, rather than treating them as independent variables.