Deciding Type-Based Partial-Order Constraints for Path-Sensitive Analysis

Elena Sherman

doi:10.1145/2755971

Return

Deciding Type-Based Partial-Order Constraints for Path-Sensitive Analysis

2015-05-13

PRE

DOI：10.1145/2755971

Original request for help

Save

Abstract

En 中文

The precision and scalability of path-sensitive program analyses depend on their ability to distinguish feasible and infeasible program paths. Analyses express path feasibility as the satisfiability of conjoined branch conditions, which is then decided by cooperating decision procedures such as those in satisfiability modulo theory (SMT) solvers. Consequently, efficient underlying decision procedures are key to precise, scalable program analyses. When we investigate the branch conditions accumulated by inter-procedural path-sensitive analyses of object-oriented programs, we find that many relate to an object's dynamic type. These conditions arise from explicit type tests and the branching implicit in dynamic dispatch and type casting. These conditions share a common form that comprises a fragment of the theory of partial orders, which we refer to as type-based partial orders (TPO). State-of-the-art SMT solvers can heuristically instantiate the quantified formulae that axiomatize partial orders, and thereby support TPO constraints. We present two custom decision procedures with significantly better performance. On benchmarks that reflect inter-procedural path-sensitive analyses applied to significant Java systems, the custom procedures run three orders of magnitude faster. The performance of the two decision procedures varies across benchmarks, which suggests that a portfolio approach may be beneficial for solving constraints generated by program analyses.

Keywords:

Algorithms

Experimentation

Verification

SMT

decision procedure

type hierarchy

subtyping

path-sensitive analysis

AI Summary

Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.