Sparse Dataflow Analysis with Pointers and Reachability

Magnus Madsen; Anders Møller

doi:10.1007/978-3-319-10936-7_13

Sparse Dataflow Analysis with Pointers and Reachability

Magnus Madsen, Anders Møller

Department of Computer Science

Research output: Contribution to book/anthology/report/proceeding › Article in proceedings › Research › peer-review

15 Citations (Scopus)

Abstract

Many static analyzers exploit sparseness techniques to reduce the amount of information being propagated and stored during analysis. Although several variations are described in the literature, no existing technique is suitable for analyzing JavaScript code. In this paper, we point out the need for a sparse analysis framework that supports pointers and reachability. We present such a framework, which uses static single assignment form for heap addresses and computes def-use information on-the-fly. We also show that essential information about dominating definitions can be maintained efficiently using quadtrees. The framework is presented as a systematic modification of a traditional dataflow analysis algorithm.

Our experimental results demonstrate the effectiveness of the technique for a suite of JavaScript programs. By also comparing the performance with an idealized staged approach that computes pointer information with a pre-analysis, we show that the cost of computing def-use information on-the-fly is remarkably small.

Original language	English
Title of host publication	Static Analysis : 21st International Symposium, SAS 2014, Munich, Germany, September 11-13, 2014. Proceedings
Editors	Markus Müller-Olm , Helmut Seidl
Number of pages	18
Publisher	Springer VS
Publication date	2014
Pages	201-218
ISBN (Print)	978-3-319-10935-0
ISBN (Electronic)	978-3-319-10936-7
DOIs	https://doi.org/10.1007/978-3-319-10936-7_13
Publication status	Published - 2014
Event	International Static Analysis Symposium (SAS) - Munich, Germany Duration: 11 Sept 2014 → 13 Sept 2014

Conference

Conference	International Static Analysis Symposium (SAS)
Country/Territory	Germany
City	Munich
Period	11/09/2014 → 13/09/2014

Series	Lecture Notes in Computer Science
Volume	8723
ISSN	0302-9743

Access to Document

10.1007/978-3-319-10936-7_13

http://cs.au.dk/~amoeller/papers/sparse/

Cite this

@inproceedings{a56c91db1a4b4abb84218f13fb6bdf8d,

title = "Sparse Dataflow Analysis with Pointers and Reachability",

abstract = " Many static analyzers exploit sparseness techniques to reduce the amount of information being propagated and stored during analysis. Although several variations are described in the literature, no existing technique is suitable for analyzing JavaScript code. In this paper, we point out the need for a sparse analysis framework that supports pointers and reachability. We present such a framework, which uses static single assignment form for heap addresses and computes def-use information on-the-fly. We also show that essential information about dominating definitions can be maintained efficiently using quadtrees. The framework is presented as a systematic modification of a traditional dataflow analysis algorithm.Our experimental results demonstrate the effectiveness of the technique for a suite of JavaScript programs. By also comparing the performance with an idealized staged approach that computes pointer information with a pre-analysis, we show that the cost of computing def-use information on-the-fly is remarkably small. ",

author = "Magnus Madsen and Anders M{\o}ller",

year = "2014",

doi = "10.1007/978-3-319-10936-7_13",

language = "English",

isbn = "978-3-319-10935-0",

series = "Lecture Notes in Computer Science",

publisher = "Springer VS",

pages = "201--218",

editor = "{ M{\"u}ller-Olm }, {Markus } and { Seidl}, {Helmut }",

booktitle = "Static Analysis",

note = "International Static Analysis Symposium (SAS) ; Conference date: 11-09-2014 Through 13-09-2014",

}

Madsen, M & Møller, A 2014, Sparse Dataflow Analysis with Pointers and Reachability. in M Müller-Olm & H Seidl (eds), Static Analysis: 21st International Symposium, SAS 2014, Munich, Germany, September 11-13, 2014. Proceedings. Springer VS, Lecture Notes in Computer Science, vol. 8723, pp. 201-218, International Static Analysis Symposium (SAS), Munich, Germany, 11/09/2014. https://doi.org/10.1007/978-3-319-10936-7_13

Sparse Dataflow Analysis with Pointers and Reachability. / Madsen, Magnus ; Møller, Anders.
Static Analysis: 21st International Symposium, SAS 2014, Munich, Germany, September 11-13, 2014. Proceedings. ed. / Markus Müller-Olm ; Helmut Seidl. Springer VS, 2014. p. 201-218 (Lecture Notes in Computer Science, Vol. 8723).

Research output: Contribution to book/anthology/report/proceeding › Article in proceedings › Research › peer-review

TY - GEN

T1 - Sparse Dataflow Analysis with Pointers and Reachability

AU - Madsen, Magnus

AU - Møller, Anders

PY - 2014

Y1 - 2014

N2 - Many static analyzers exploit sparseness techniques to reduce the amount of information being propagated and stored during analysis. Although several variations are described in the literature, no existing technique is suitable for analyzing JavaScript code. In this paper, we point out the need for a sparse analysis framework that supports pointers and reachability. We present such a framework, which uses static single assignment form for heap addresses and computes def-use information on-the-fly. We also show that essential information about dominating definitions can be maintained efficiently using quadtrees. The framework is presented as a systematic modification of a traditional dataflow analysis algorithm.Our experimental results demonstrate the effectiveness of the technique for a suite of JavaScript programs. By also comparing the performance with an idealized staged approach that computes pointer information with a pre-analysis, we show that the cost of computing def-use information on-the-fly is remarkably small.

AB - Many static analyzers exploit sparseness techniques to reduce the amount of information being propagated and stored during analysis. Although several variations are described in the literature, no existing technique is suitable for analyzing JavaScript code. In this paper, we point out the need for a sparse analysis framework that supports pointers and reachability. We present such a framework, which uses static single assignment form for heap addresses and computes def-use information on-the-fly. We also show that essential information about dominating definitions can be maintained efficiently using quadtrees. The framework is presented as a systematic modification of a traditional dataflow analysis algorithm.Our experimental results demonstrate the effectiveness of the technique for a suite of JavaScript programs. By also comparing the performance with an idealized staged approach that computes pointer information with a pre-analysis, we show that the cost of computing def-use information on-the-fly is remarkably small.

U2 - 10.1007/978-3-319-10936-7_13

DO - 10.1007/978-3-319-10936-7_13

M3 - Article in proceedings

SN - 978-3-319-10935-0

T3 - Lecture Notes in Computer Science

SP - 201

EP - 218

BT - Static Analysis

A2 - Müller-Olm , Markus

A2 - Seidl, Helmut

PB - Springer VS

T2 - International Static Analysis Symposium (SAS)

Y2 - 11 September 2014 through 13 September 2014

ER -

Sparse Dataflow Analysis with Pointers and Reachability

Abstract

Conference

Access to Document

Fingerprint

Cite this