Skip to Main content Skip to Navigation
Conference papers

CPA beats oo-CFA

Frédéric Besson 1
1 CELTIQUE - Software certification with semantic analysis
Inria Rennes – Bretagne Atlantique , IRISA-D4 - LANGAGE ET GÉNIE LOGICIEL
Abstract : Context-sensitive points-to analysis is the current most scalable technology for constructing a precise control-flow graph for large object-oriented programs. One appealing feature of this framework is that it is parametric thus allowing to trade time for precision. Typical instances of this framework are k-CFAs and Agesen's Cartesian Product Algorithm (CPA). It is common sense that k-CFAs (for increasing ks) form a hierarchy. Yet, what is the relative precision of k-CFA and CPA? Grove and Chambers [2] conjecture that CPA is more precise than oo-CFA. For a core object-oriented language, we formally compare the precision of oo-CFA and CPA. We prove that CPA is indeed strictly more precise than oo-CFA. On a theoretical level, this result confirms the findings of empiric studies concluding the superiority of object-sensitivity with respect to call-string sensitivity.
Document type :
Conference papers
Complete list of metadatas

Cited literature [11 references]  Display  Hide  Download

https://hal.inria.fr/hal-00780389
Contributor : Frédéric Besson <>
Submitted on : Monday, November 24, 2014 - 11:32:33 AM
Last modification on : Thursday, January 7, 2021 - 4:33:55 PM
Long-term archiving on: : Wednesday, February 25, 2015 - 10:31:00 AM

File

CPA_beats_CFA.pdf
Files produced by the author(s)

Identifiers

Citation

Frédéric Besson. CPA beats oo-CFA. FTfJP '09 - Proceedings of the 11th International Workshop on Formal Techniques for Java-like Programs, 2009, Genova, Italy. ⟨10.1145/1557898.1557905⟩. ⟨hal-00780389⟩

Share

Metrics

Record views

674

Files downloads

162