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.2018.24
URN: urn:nbn:de:0030-drops-92290
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9229/
Go to the corresponding LIPIcs Volume Portal

Toman, John ; Grossman, Dan

Legato: An At-Most-Once Analysis with Applications to Dynamic Configuration Updates

pdf-format:
LIPIcs-ECOOP-2018-24.pdf (0.8 MB)

Abstract

Modern software increasingly relies on external resources whose location or content can change during program execution. Examples of such resources include remote network hosts, database entries, dynamically updated configuration options, etc. Long running, adaptable programs must handle these changes gracefully and correctly. Dealing with all possible resource update scenarios is difficult to get right, especially if, as is common, external resources can be modified without prior warning by code and/or users outside of the application's direct control. If a resource unexpectedly changes during a computation, an application may observe multiple, inconsistent states of the resource, leading to incorrect program behavior.
This paper presents a sound and precise static analysis, Legato, that verifies programs correctly handle changes in external resources. Our analysis ensures that every value computed by an application reflects a single, consistent version of every external resource's state. Although consistent computation in the presence of concurrent resource updates is fundamentally a concurrency issue, our analysis relies on the novel at-most-once condition to avoid explicitly reasoning about concurrency. The at-most-once condition requires that all values depend on at most one access of each resource. Our analysis is flow-, field-, and context-sensitive. It scales to real-world Java programs while producing a moderate number of false positives. We applied Legato to 10 applications with dynamically updated configurations, and found several non-trivial consistency bugs.

BibTeX - Entry

@InProceedings{toman_et_al:LIPIcs:2018:9229,
  author =	{John Toman and Dan Grossman},
  title =	{{Legato: An At-Most-Once Analysis with Applications to Dynamic Configuration Updates}},
  booktitle =	{32nd European Conference on Object-Oriented Programming  (ECOOP 2018)},
  pages =	{24:1--24:32},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-079-8},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{109},
  editor =	{Todd Millstein},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9229},
  URN =		{urn:nbn:de:0030-drops-92290},
  doi =		{10.4230/LIPIcs.ECOOP.2018.24},
  annote =	{Keywords: Static Analysis, Dynamic Configuration Updates}
}

Keywords: Static Analysis, Dynamic Configuration Updates
Collection: 32nd European Conference on Object-Oriented Programming (ECOOP 2018)
Issue Date: 2018
Date of publication: 10.07.2018
Supplementary Material: ECOOP Artifact Evaluation approved artifact available at http://dx.doi.org/10.4230/DARTS.4.3.2

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