Explicit and symbolic techniques for fast and scalable points-to analysis

Research output: Contribution to conferencePaper

Abstract

Points-to analysis that scales to large programs is still an open area of research and there are several trade-offs between speed and precision. In this paper, we report advances in achieving extremely fast and scalable analysis for fieldsensitive inclusion-based points-to analysis. The first algorithm is based on an explicit representation, sparse bit-vector set representation. The second algorithm is a refinement of the first using symbolic set representations using binary decision diagrams. The first algorithm scales extremely well when compared with the state-of-the-Art points-to analysis problems solving the same problem, while the second reduces the memory footprint tremendously, using, on average, 4.6x less memory than the first, and even performs slightly faster points-to set propagation. The techniques that we introduce are a judicious combination of several heuristics involving sparse bit-vector set representations, prioritized processing of worklists for efficient iteration while computing fixed-points, and usage of binary decision diagrams for storing (but not propagating) points-to sets. The implementation of our approaches scales to large real life Java applications. We evaluated our implementation on benchmark applications from two recent releases of DaCapo benchmark suite using a recent version of Java Standard Library (JRE 1.7 03). Using our techniques we can propagate points-to information on all the benchmarks in less than a minute, using at most 2GB of memory for explicit representation and, at most 600MB for symbolic representation. Comparison with the fastest and the most closely related explicit and symbolic approaches reveals that our techniques are more scalable than related explicit approaches, and in terms of time, on average 4x times faster than the current state-of-the-Art.

Original languageEnglish (US)
DOIs
StatePublished - Jun 12 2014
Event3rd ACM SIGPLAN International Workshop on the State of the Art in Java Program Analysis, SOAP 2014 - Co-located with PLDI 2014 - Edinburgh, United Kingdom
Duration: Jun 12 2014 → …

Other

Other3rd ACM SIGPLAN International Workshop on the State of the Art in Java Program Analysis, SOAP 2014 - Co-located with PLDI 2014
CountryUnited Kingdom
CityEdinburgh
Period6/12/14 → …

Fingerprint

Binary decision diagrams
Data storage equipment
Processing

ASJC Scopus subject areas

  • Software

Cite this

Pek, E., & Parthasarathy, M. (2014). Explicit and symbolic techniques for fast and scalable points-to analysis. Paper presented at 3rd ACM SIGPLAN International Workshop on the State of the Art in Java Program Analysis, SOAP 2014 - Co-located with PLDI 2014, Edinburgh, United Kingdom. https://doi.org/10.1145/2614628.2614632

Explicit and symbolic techniques for fast and scalable points-to analysis. / Pek, Edgar; Parthasarathy, Madhusudan.

2014. Paper presented at 3rd ACM SIGPLAN International Workshop on the State of the Art in Java Program Analysis, SOAP 2014 - Co-located with PLDI 2014, Edinburgh, United Kingdom.

Research output: Contribution to conferencePaper

Pek, E & Parthasarathy, M 2014, 'Explicit and symbolic techniques for fast and scalable points-to analysis' Paper presented at 3rd ACM SIGPLAN International Workshop on the State of the Art in Java Program Analysis, SOAP 2014 - Co-located with PLDI 2014, Edinburgh, United Kingdom, 6/12/14, . https://doi.org/10.1145/2614628.2614632
Pek E, Parthasarathy M. Explicit and symbolic techniques for fast and scalable points-to analysis. 2014. Paper presented at 3rd ACM SIGPLAN International Workshop on the State of the Art in Java Program Analysis, SOAP 2014 - Co-located with PLDI 2014, Edinburgh, United Kingdom. https://doi.org/10.1145/2614628.2614632
Pek, Edgar ; Parthasarathy, Madhusudan. / Explicit and symbolic techniques for fast and scalable points-to analysis. Paper presented at 3rd ACM SIGPLAN International Workshop on the State of the Art in Java Program Analysis, SOAP 2014 - Co-located with PLDI 2014, Edinburgh, United Kingdom.
@conference{5960e5ec9e054cc1b2aba54411a0a81c,
title = "Explicit and symbolic techniques for fast and scalable points-to analysis",
abstract = "Points-to analysis that scales to large programs is still an open area of research and there are several trade-offs between speed and precision. In this paper, we report advances in achieving extremely fast and scalable analysis for fieldsensitive inclusion-based points-to analysis. The first algorithm is based on an explicit representation, sparse bit-vector set representation. The second algorithm is a refinement of the first using symbolic set representations using binary decision diagrams. The first algorithm scales extremely well when compared with the state-of-the-Art points-to analysis problems solving the same problem, while the second reduces the memory footprint tremendously, using, on average, 4.6x less memory than the first, and even performs slightly faster points-to set propagation. The techniques that we introduce are a judicious combination of several heuristics involving sparse bit-vector set representations, prioritized processing of worklists for efficient iteration while computing fixed-points, and usage of binary decision diagrams for storing (but not propagating) points-to sets. The implementation of our approaches scales to large real life Java applications. We evaluated our implementation on benchmark applications from two recent releases of DaCapo benchmark suite using a recent version of Java Standard Library (JRE 1.7 03). Using our techniques we can propagate points-to information on all the benchmarks in less than a minute, using at most 2GB of memory for explicit representation and, at most 600MB for symbolic representation. Comparison with the fastest and the most closely related explicit and symbolic approaches reveals that our techniques are more scalable than related explicit approaches, and in terms of time, on average 4x times faster than the current state-of-the-Art.",
author = "Edgar Pek and Madhusudan Parthasarathy",
year = "2014",
month = "6",
day = "12",
doi = "10.1145/2614628.2614632",
language = "English (US)",
note = "3rd ACM SIGPLAN International Workshop on the State of the Art in Java Program Analysis, SOAP 2014 - Co-located with PLDI 2014 ; Conference date: 12-06-2014",

}

TY - CONF

T1 - Explicit and symbolic techniques for fast and scalable points-to analysis

AU - Pek, Edgar

AU - Parthasarathy, Madhusudan

PY - 2014/6/12

Y1 - 2014/6/12

N2 - Points-to analysis that scales to large programs is still an open area of research and there are several trade-offs between speed and precision. In this paper, we report advances in achieving extremely fast and scalable analysis for fieldsensitive inclusion-based points-to analysis. The first algorithm is based on an explicit representation, sparse bit-vector set representation. The second algorithm is a refinement of the first using symbolic set representations using binary decision diagrams. The first algorithm scales extremely well when compared with the state-of-the-Art points-to analysis problems solving the same problem, while the second reduces the memory footprint tremendously, using, on average, 4.6x less memory than the first, and even performs slightly faster points-to set propagation. The techniques that we introduce are a judicious combination of several heuristics involving sparse bit-vector set representations, prioritized processing of worklists for efficient iteration while computing fixed-points, and usage of binary decision diagrams for storing (but not propagating) points-to sets. The implementation of our approaches scales to large real life Java applications. We evaluated our implementation on benchmark applications from two recent releases of DaCapo benchmark suite using a recent version of Java Standard Library (JRE 1.7 03). Using our techniques we can propagate points-to information on all the benchmarks in less than a minute, using at most 2GB of memory for explicit representation and, at most 600MB for symbolic representation. Comparison with the fastest and the most closely related explicit and symbolic approaches reveals that our techniques are more scalable than related explicit approaches, and in terms of time, on average 4x times faster than the current state-of-the-Art.

AB - Points-to analysis that scales to large programs is still an open area of research and there are several trade-offs between speed and precision. In this paper, we report advances in achieving extremely fast and scalable analysis for fieldsensitive inclusion-based points-to analysis. The first algorithm is based on an explicit representation, sparse bit-vector set representation. The second algorithm is a refinement of the first using symbolic set representations using binary decision diagrams. The first algorithm scales extremely well when compared with the state-of-the-Art points-to analysis problems solving the same problem, while the second reduces the memory footprint tremendously, using, on average, 4.6x less memory than the first, and even performs slightly faster points-to set propagation. The techniques that we introduce are a judicious combination of several heuristics involving sparse bit-vector set representations, prioritized processing of worklists for efficient iteration while computing fixed-points, and usage of binary decision diagrams for storing (but not propagating) points-to sets. The implementation of our approaches scales to large real life Java applications. We evaluated our implementation on benchmark applications from two recent releases of DaCapo benchmark suite using a recent version of Java Standard Library (JRE 1.7 03). Using our techniques we can propagate points-to information on all the benchmarks in less than a minute, using at most 2GB of memory for explicit representation and, at most 600MB for symbolic representation. Comparison with the fastest and the most closely related explicit and symbolic approaches reveals that our techniques are more scalable than related explicit approaches, and in terms of time, on average 4x times faster than the current state-of-the-Art.

UR - http://www.scopus.com/inward/record.url?scp=84954557457&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84954557457&partnerID=8YFLogxK

U2 - 10.1145/2614628.2614632

DO - 10.1145/2614628.2614632

M3 - Paper

AN - SCOPUS:84954557457

ER -