Reasoning about the unknown in static analysis

Isil Dillig, Thomas Dillig, Alex AikenCommunications of the ACM 2010 · DOI

TL;DR

This paper introduces a novel method for static program analysis that precisely handles "unknown" values (like user input or network data) by representing them as non-deterministic choices. The key innovation is a technique to eliminate these choice variables at function boundaries, enabling scalable and precise analysis of large programs, including operating systems, by transforming complex recursive constraints into simpler, equisatisfiable boolean formulas.

What Problem Does This Paper Address?

Static program analysis aims to detect errors by reasoning about all possible program executions. However, a major challenge is dealing with values that are not known at analysis time, such as user inputs, network data, or results from external system calls. Treating these as completely arbitrary non-deterministic choices can lead to overly imprecise analyses and a flood of false positives. Existing approaches often struggle to balance precision, soundness, and scalability when faced with these pervasive unknowns. This paper tackles the problem of how to precisely reason about these unknown values without sacrificing scalability or introducing excessive false alarms.

Methods

The core of the paper's contribution lies in a systematic approach to handling unknown values, which are modeled as "choice variables."

  • Choice Variables: Initially, unknown values are represented by choice variables. This allows for precise reasoning within a function's scope, as distinct unknown values are represented by distinct variables.
  • Recursive Constraint Systems: The analysis generates recursive systems of equations (constraints) that capture program behavior, including these choice variables.
  • Eliminating Choice Variables: The crucial step is eliminating these choice variables at function boundaries. This is achieved by computing "strongest necessary" and "weakest sufficient" conditions. These conditions are derived such that they preserve the satisfiability (for "may" queries) and validity (for "must" queries) of the original constraints, but are expressed solely in terms of observable variables (function inputs).
  • Booleanization and Fixed-Point Computation: The generated constraints are translated into boolean logic. Recursion is then eliminated using standard fixed-point computation over a finite lattice. This process yields a pair of equisatisfiable and equivalid systems of equations over observable variables.
  • Decision Procedure: Finally, a boolean SAT solver is used to answer the "may" and "must" queries based on these simplified, non-recursive constraints.

Datasets

Not discussed in the paper. The paper focuses on a theoretical framework and experimental evaluation on existing software projects.

Key Insights and Ideas

  • Choice variables are powerful but problematic: While choice variables offer precision by distinguishing between different unknown values, they lead to unmanageable recursive constraints and scalability issues when not handled carefully.
  • The power of "strongest necessary" and "weakest sufficient" conditions: These concepts are key to abstracting away choice variables. They provide tight bounds on the original constraints using only observable variables, preserving the ability to answer "may" and "must" queries precisely.
  • Separating "may" and "must" queries: The method is designed to efficiently answer these two fundamental types of program properties, which are naturally mapped to satisfiability and validity queries, respectively.
  • Scalability through abstraction: By transforming complex, choice-variable-laden constraints into simpler boolean formulas over observable variables, the technique achieves significant scalability improvements, allowing analysis of very large codebases.

Key Results

  • The proposed method can precisely handle unknown values in static analysis.
  • It successfully eliminates choice variables from recursive constraint systems, yielding non-recursive formulas over observable variables.
  • Experimental results on large programs like the Linux kernel, OpenSSH, and Samba show that the generated necessary and sufficient conditions are concise in practice (typically fewer than five boolean connectives).
  • The technique significantly reduces false positives in null dereference analysis (by nearly an order of magnitude) without compromising soundness.

Limitations and Future Work

  • Termination Assumption: The results are qualified by the assumption that the analyzed program terminates. The method might not precisely capture non-termination scenarios when translating to boolean logic.
  • Combining Properties: The technique is not directly suited for combining reasoning about multiple distinct properties simultaneously, as strongest necessary conditions do not distribute over conjunctions, and weakest sufficient conditions do not distribute over disjunctions. Analyzing combined properties requires computing conditions for the combined property.
  • Finite Domains: While the technique works for finite domains and finitary abstractions, it is not complete for arbitrary non-finite domains.
  • Orthogonal Imprecision: False positives can still arise from other sources of imprecision not addressed by this method, such as sophisticated shape analysis for unbounded data structures.

Future work could explore extending the method to handle non-termination more robustly and to better combine reasoning about multiple properties.

Summary updated

BibTeX
@article{dillig2010reasoning,
  author = {Isil Dillig and Thomas Dillig and Alex Aiken},
  title = {{Reasoning about the unknown in static analysis}},
  journal = {Communications of the ACM},
  year = {2010},
  doi = {10.1145/1787234.1787259},
}
Figure