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.
Type de document :
Communication dans un congrès
FTfJP '09 - Proceedings of the 11th International Workshop on Formal Techniques for Java-like Programs, 2009, Genova, Italy. 2009, 〈10.1145/1557898.1557905〉
Liste complète des métadonnées

Littérature citée [11 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00780389
Contributeur : Frédéric Besson <>
Soumis le : lundi 24 novembre 2014 - 11:32:33
Dernière modification le : mercredi 16 mai 2018 - 11:23:28
Document(s) archivé(s) le : mercredi 25 février 2015 - 10:31:00

Fichier

CPA_beats_CFA.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

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. 2009, 〈10.1145/1557898.1557905〉. 〈hal-00780389〉

Partager

Métriques

Consultations de la notice

475

Téléchargements de fichiers

73