License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ECOOP.2019.11
URN: urn:nbn:de:0030-drops-108038
Go to the corresponding LIPIcs Volume Portal

Bastani, Osbert ; Sharma, Rahul ; Clapp, Lazaro ; Anand, Saswat ; Aiken, Alex

Eventually Sound Points-To Analysis with Specifications

LIPIcs-ECOOP-2019-11.pdf (0.7 MB)


Static analyses make the increasingly tenuous assumption that all source code is available for analysis; for example, large libraries often call into native code that cannot be analyzed. We propose a points-to analysis that initially makes optimistic assumptions about missing code, and then inserts runtime checks that report counterexamples to these assumptions that occur during execution. Our approach guarantees eventual soundness, which combines two guarantees: (i) the runtime checks are guaranteed to catch the first counterexample that occurs during any execution, in which case execution can be terminated to prevent harm, and (ii) only finitely many counterexamples ever occur, implying that the static analysis eventually becomes statically sound with respect to all remaining executions. We implement Optix, an eventually sound points-to analysis for Android apps, where the Android framework is missing. We show that the runtime checks added by Optix incur low overhead on real programs, and demonstrate how Optix improves a client information flow analysis for detecting Android malware.

BibTeX - Entry

  author =	{Osbert Bastani and Rahul Sharma and Lazaro Clapp and Saswat Anand and Alex Aiken},
  title =	{{Eventually Sound Points-To Analysis with Specifications}},
  booktitle =	{33rd European Conference on Object-Oriented Programming (ECOOP 2019)},
  pages =	{11:1--11:28},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-111-5},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{134},
  editor =	{Alastair F. Donaldson},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{},
  URN =		{urn:nbn:de:0030-drops-108038},
  doi =		{10.4230/LIPIcs.ECOOP.2019.11},
  annote =	{Keywords: specification inference, static points-to analysis, runtime monitoring}

Keywords: specification inference, static points-to analysis, runtime monitoring
Collection: 33rd European Conference on Object-Oriented Programming (ECOOP 2019)
Issue Date: 2019
Date of publication: 10.07.2019

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI