Static Analysis with Demand-driven Value Refinement

Benno Stein; Benjamin Barslev Nielsen; Bor-Yuh Evan Chang; Anders Møller

doi:10.1145/3360566

Static Analysis with Demand-driven Value Refinement

Benno Stein, Benjamin Barslev Nielsen, Bor-Yuh Evan Chang, Anders Møller

Department of Computer Science

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaper › Journal article › Research › peer-review

12 Citations (Scopus)

89 Downloads (Pure)

Abstract

Static analysis tools for JavaScript must strike a delicate balance, achieving the level of precision required by the most complex features of target programs without incurring prohibitively high analysis time. For example, reasoning about dynamic property accesses sometimes requires precise relational information connecting the object, the dynamically-computed property name, and the property value. Even a minor precision loss at such critical program locations can result in a proliferation of spurious dataflow that renders the analysis results useless. We present a technique by which a conventional non-relational static dataflow analysis can be combined soundly with a value refinement mechanism to increase precision on demand at critical locations. Crucially, our technique is able to incorporate relational information from the value refinement mechanism into the non-relational domain of the dataflow analysis. We demonstrate the feasibility of this approach by extending an existing JavaScript static analysis with a demand-driven value refinement mechanism that relies on backwards abstract interpretation. Our evaluation finds that precise analysis of widely used JavaScript utility libraries depends heavily on the precision at a small number of critical locations that can be identified heuristically, and that backwards abstract interpretation is an effective mechanism to provide that precision on demand.

Original language	English
Article number	140
Journal	Proceedings of the ACM on Programming Languages
Volume	3
Issue	OOPSLA
Number of pages	29
ISSN	2475-1421
DOIs	https://doi.org/10.1145/3360566
Publication status	Published - 2019

Access to Document

10.1145/3360566

3360566Final published version, 457 KBLicence: CC BY

Cite this

@article{0a065659828841228fb65ff6a0583e32,

title = "Static Analysis with Demand-driven Value Refinement",

abstract = "Static analysis tools for JavaScript must strike a delicate balance, achieving the level of precision required by the most complex features of target programs without incurring prohibitively high analysis time. For example, reasoning about dynamic property accesses sometimes requires precise relational information connecting the object, the dynamically-computed property name, and the property value. Even a minor precision loss at such critical program locations can result in a proliferation of spurious dataflow that renders the analysis results useless. We present a technique by which a conventional non-relational static dataflow analysis can be combined soundly with a value refinement mechanism to increase precision on demand at critical locations. Crucially, our technique is able to incorporate relational information from the value refinement mechanism into the non-relational domain of the dataflow analysis. We demonstrate the feasibility of this approach by extending an existing JavaScript static analysis with a demand-driven value refinement mechanism that relies on backwards abstract interpretation. Our evaluation finds that precise analysis of widely used JavaScript utility libraries depends heavily on the precision at a small number of critical locations that can be identified heuristically, and that backwards abstract interpretation is an effective mechanism to provide that precision on demand.",

keywords = "JavaScript, abstract interpretation, dataflow analysis",

author = "Benno Stein and Nielsen, {Benjamin Barslev} and Chang, {Bor-Yuh Evan} and Anders M{\o}ller",

year = "2019",

doi = "10.1145/3360566",

language = "English",

volume = "3",

journal = "Proceedings of the ACM on Programming Languages ",

issn = "2475-1421",

publisher = "Association for Computing Machinery",

number = "OOPSLA",

}

TY - JOUR

T1 - Static Analysis with Demand-driven Value Refinement

AU - Stein, Benno

AU - Nielsen, Benjamin Barslev

AU - Chang, Bor-Yuh Evan

AU - Møller, Anders

PY - 2019

Y1 - 2019

N2 - Static analysis tools for JavaScript must strike a delicate balance, achieving the level of precision required by the most complex features of target programs without incurring prohibitively high analysis time. For example, reasoning about dynamic property accesses sometimes requires precise relational information connecting the object, the dynamically-computed property name, and the property value. Even a minor precision loss at such critical program locations can result in a proliferation of spurious dataflow that renders the analysis results useless. We present a technique by which a conventional non-relational static dataflow analysis can be combined soundly with a value refinement mechanism to increase precision on demand at critical locations. Crucially, our technique is able to incorporate relational information from the value refinement mechanism into the non-relational domain of the dataflow analysis. We demonstrate the feasibility of this approach by extending an existing JavaScript static analysis with a demand-driven value refinement mechanism that relies on backwards abstract interpretation. Our evaluation finds that precise analysis of widely used JavaScript utility libraries depends heavily on the precision at a small number of critical locations that can be identified heuristically, and that backwards abstract interpretation is an effective mechanism to provide that precision on demand.

AB - Static analysis tools for JavaScript must strike a delicate balance, achieving the level of precision required by the most complex features of target programs without incurring prohibitively high analysis time. For example, reasoning about dynamic property accesses sometimes requires precise relational information connecting the object, the dynamically-computed property name, and the property value. Even a minor precision loss at such critical program locations can result in a proliferation of spurious dataflow that renders the analysis results useless. We present a technique by which a conventional non-relational static dataflow analysis can be combined soundly with a value refinement mechanism to increase precision on demand at critical locations. Crucially, our technique is able to incorporate relational information from the value refinement mechanism into the non-relational domain of the dataflow analysis. We demonstrate the feasibility of this approach by extending an existing JavaScript static analysis with a demand-driven value refinement mechanism that relies on backwards abstract interpretation. Our evaluation finds that precise analysis of widely used JavaScript utility libraries depends heavily on the precision at a small number of critical locations that can be identified heuristically, and that backwards abstract interpretation is an effective mechanism to provide that precision on demand.

KW - JavaScript

KW - abstract interpretation

KW - dataflow analysis

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

U2 - 10.1145/3360566

DO - 10.1145/3360566

M3 - Journal article

SN - 2475-1421

VL - 3

JO - Proceedings of the ACM on Programming Languages

JF - Proceedings of the ACM on Programming Languages

IS - OOPSLA

M1 - 140

ER -

Static Analysis with Demand-driven Value Refinement

Abstract

Access to Document

Other files and links

Fingerprint

Cite this