Averroes: Whole-program analysis without the whole program

Karim Ali, Ondřej Lhoták

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Call graph construction for object-oriented programs is often difficult and expensive. Most sound and precise algorithms analyze the whole program including all library dependencies. The separate compilation assumption makes it possible to generate sound and reasonably precise call graphs without analyzing libraries. We investigate whether the separate compilation assumption can be encoded universally in Java bytecode, such that all existing whole-program analysis frameworks can easily take advantage of it. We present and evaluate Averroes, a tool that generates a placeholder library that overapproximates the possible behaviour of an original library. The placeholder library can be constructed quickly without analyzing the whole program, and is typically in the order of 80 kB of class files (comparatively, the Java standard library is 25 MB). Any existing whole-program call graph construction framework can use the placeholder library as a replacement for the actual libraries to efficiently construct a sound and precise application call graph. Averroes improves the analysis time of whole-program call graph construction by a factor of 4.3x to 12x, and reduces memory requirements by a factor of 8.4x to 13x. In addition, Averroes makes it easier for whole-program frameworks to handle reflection soundly in two ways: it is based on a conservative assumption about all behaviour within the library, including reflection, and it provides analyses and tools to model reflection in the application. The call graphs built with Averroes and existing whole-program frameworks are as precise and sound as those built with Cgc. While Cgc is a specific implementation of the separate compilation assumption in the Doop framework, Averroes is universal to all Java program analysis frameworks.

Original languageEnglish (US)
Title of host publicationECOOP 2013, Object-Oriented Programming - 27th European Conference, Proceedings
PublisherSpringer Verlag
Pages378-400
Number of pages23
ISBN (Print)9783642390371
DOIs
StatePublished - 2013
Event27th European Conference on Object-Oriented Programming, ECOOP 2013 - Montpellier, France
Duration: Jul 1 2013Jul 5 2013

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume7920 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference27th European Conference on Object-Oriented Programming, ECOOP 2013
Country/TerritoryFrance
CityMontpellier
Period7/1/137/5/13

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

Dive into the research topics of 'Averroes: Whole-program analysis without the whole program'. Together they form a unique fingerprint.

Cite this