Search Results

Documents authored by Møller, Anders

Document
DOI: 10.4230/LIPIcs.ECOOP.2024.10
Indirection-Bounded Call Graph Analysis

Authors: Madhurima Chakraborty, Aakash Gnanakumar, Manu Sridharan, and Anders Møller

Published in: LIPIcs, Volume 313, 38th European Conference on Object-Oriented Programming (ECOOP 2024)

Abstract
Call graphs play a crucial role in analyzing the structure and behavior of programs. For JavaScript and other dynamically typed programming languages, static call graph analysis relies on approximating the possible flow of functions and objects, and producing usable call graphs for large, real-world programs remains challenging. In this paper, we propose a simple but effective technique that addresses performance issues encountered in call graph generation. We observe via a dynamic analysis that typical JavaScript program code exhibits small levels of indirection of object pointers and higher-order functions. We demonstrate that a widely used analysis algorithm, wave propagation, closely follows the levels of indirections, so that call edges discovered early are more likely to be true positives. By bounding the number of indirections covered by this analysis, in many cases it can find most true-positive call edges in less time. We also show that indirection-bounded analysis can similarly be incorporated into the field-based call graph analysis algorithm ACG. We have experimentally evaluated the modified wave propagation algorithm on 25 large Node.js-based JavaScript programs. Indirection-bounded analysis on average yields close to a 2X speed-up with only 5% reduction in recall and almost identical precision relative to the baseline analysis, using dynamically generated call graphs for the recall and precision measurements. To demonstrate the robustness of the approach, we also evaluated the modified ACG algorithm on 10 web-based and 4 mobile-based medium sized benchmarks, with similar results.
Cite as

Madhurima Chakraborty, Aakash Gnanakumar, Manu Sridharan, and Anders Møller. Indirection-Bounded Call Graph Analysis. In 38th European Conference on Object-Oriented Programming (ECOOP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 313, pp. 10:1-10:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{chakraborty_et_al:LIPIcs.ECOOP.2024.10,
  author =	{Chakraborty, Madhurima and Gnanakumar, Aakash and Sridharan, Manu and M{\o}ller, Anders},
  title =	{{Indirection-Bounded Call Graph Analysis}},
  booktitle =	{38th European Conference on Object-Oriented Programming (ECOOP 2024)},
  pages =	{10:1--10:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-341-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{313},
  editor =	{Aldrich, Jonathan and Salvaneschi, Guido},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECOOP.2024.10},
  URN =		{urn:nbn:de:0030-drops-208599},
  doi =		{10.4230/LIPIcs.ECOOP.2024.10},
  annote =	{Keywords: JavaScript, call graphs, points-to analysis}
}
Document
Complete Volume
DOI: 10.4230/LIPIcs.ECOOP.2021
LIPIcs, Volume 194, ECOOP 2021, Complete Volume

Authors: Anders Møller and Manu Sridharan

Published in: LIPIcs, Volume 194, 35th European Conference on Object-Oriented Programming (ECOOP 2021)

Abstract
LIPIcs, Volume 194, ECOOP 2021, Complete Volume
Cite as

35th European Conference on Object-Oriented Programming (ECOOP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 194, pp. 1-628, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@Proceedings{mller_et_al:LIPIcs.ECOOP.2021,
  title =	{{LIPIcs, Volume 194, ECOOP 2021, Complete Volume}},
  booktitle =	{35th European Conference on Object-Oriented Programming (ECOOP 2021)},
  pages =	{1--628},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-190-0},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{194},
  editor =	{M{\o}ller, Anders and Sridharan, Manu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECOOP.2021},
  URN =		{urn:nbn:de:0030-drops-140422},
  doi =		{10.4230/LIPIcs.ECOOP.2021},
  annote =	{Keywords: LIPIcs, Volume 194, ECOOP 2021, Complete Volume}
}
Document
Front Matter
DOI: 10.4230/LIPIcs.ECOOP.2021.0
Front Matter, Table of Contents, Preface, Conference Organization

Authors: Anders Møller and Manu Sridharan

Published in: LIPIcs, Volume 194, 35th European Conference on Object-Oriented Programming (ECOOP 2021)

Abstract
Front Matter, Table of Contents, Preface, Conference Organization
Cite as

35th European Conference on Object-Oriented Programming (ECOOP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 194, pp. 0:i-0:xxiv, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{mller_et_al:LIPIcs.ECOOP.2021.0,
  author =	{M{\o}ller, Anders and Sridharan, Manu},
  title =	{{Front Matter, Table of Contents, Preface, Conference Organization}},
  booktitle =	{35th European Conference on Object-Oriented Programming (ECOOP 2021)},
  pages =	{0:i--0:xxiv},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-190-0},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{194},
  editor =	{M{\o}ller, Anders and Sridharan, Manu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECOOP.2021.0},
  URN =		{urn:nbn:de:0030-drops-140438},
  doi =		{10.4230/LIPIcs.ECOOP.2021.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
Document
DOI: 10.4230/LIPIcs.ECOOP.2020.16
Value Partitioning: A Lightweight Approach to Relational Static Analysis for JavaScript

Authors: Benjamin Barslev Nielsen and Anders Møller

Published in: LIPIcs, Volume 166, 34th European Conference on Object-Oriented Programming (ECOOP 2020)

Abstract
In static analysis of modern JavaScript libraries, relational analysis at key locations is critical to provide sound and useful results. Prior work addresses this challenge by the use of various forms of trace partitioning and syntactic patterns, which is fragile and does not scale well, or by incorporating complex backwards analysis. In this paper, we propose a new lightweight variant of trace partitioning named value partitioning that refines individual abstract values instead of entire abstract states. We describe how this approach can effectively capture important relational properties involving dynamic property accesses, functions with free variables, and predicate functions. Furthermore, we extend an existing JavaScript analyzer with value partitioning and demonstrate experimentally that it is a simple, precise, and efficient alternative to the existing approaches for analyzing widely used JavaScript libraries.
Cite as

Benjamin Barslev Nielsen and Anders Møller. Value Partitioning: A Lightweight Approach to Relational Static Analysis for JavaScript. In 34th European Conference on Object-Oriented Programming (ECOOP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 166, pp. 16:1-16:28, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{nielsen_et_al:LIPIcs.ECOOP.2020.16,
  author =	{Nielsen, Benjamin Barslev and M{\o}ller, Anders},
  title =	{{Value Partitioning: A Lightweight Approach to Relational Static Analysis for JavaScript}},
  booktitle =	{34th European Conference on Object-Oriented Programming (ECOOP 2020)},
  pages =	{16:1--16:28},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-154-2},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{166},
  editor =	{Hirschfeld, Robert and Pape, Tobias},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECOOP.2020.16},
  URN =		{urn:nbn:de:0030-drops-131731},
  doi =		{10.4230/LIPIcs.ECOOP.2020.16},
  annote =	{Keywords: JavaScript, dataflow analysis, abstract interpretation}
}
Document
DOI: 10.4230/LIPIcs.ECOOP.2018.7
Type Regression Testing to Detect Breaking Changes in Node.js Libraries

Authors: Gianluca Mezzetti, Anders Møller, and Martin Toldam Torp

Published in: LIPIcs, Volume 109, 32nd European Conference on Object-Oriented Programming (ECOOP 2018)

Abstract
The npm repository contains JavaScript libraries that are used by millions of software developers. Its semantic versioning system relies on the ability to distinguish between breaking and non-breaking changes when libraries are updated. However, the dynamic nature of JavaScript often causes unintended breaking changes to be detected too late, which undermines the robustness of the applications. We present a novel technique, type regression testing, to automatically determine whether an update of a library implementation affects the types of its public interface, according to how the library is being used by other npm packages. By leveraging available test suites of clients, type regression testing uses a dynamic analysis to learn models of the library interface. Comparing the models before and after an update effectively amplifies the existing tests by revealing changes that may affect the clients. Experimental results on 12 widely used libraries show that the technique can identify type-related breaking changes with high accuracy. It fully automatically classifies at least 90% of the updates correctly as either major or as minor or patch, and it detects 26 breaking changes among the minor and patch updates.
Cite as

Gianluca Mezzetti, Anders Møller, and Martin Toldam Torp. Type Regression Testing to Detect Breaking Changes in Node.js Libraries. In 32nd European Conference on Object-Oriented Programming (ECOOP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 109, pp. 7:1-7:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{mezzetti_et_al:LIPIcs.ECOOP.2018.7,
  author =	{Mezzetti, Gianluca and M{\o}ller, Anders and Torp, Martin Toldam},
  title =	{{Type Regression Testing to Detect Breaking Changes in Node.js Libraries}},
  booktitle =	{32nd European Conference on Object-Oriented Programming (ECOOP 2018)},
  pages =	{7:1--7:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-079-8},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{109},
  editor =	{Millstein, Todd},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECOOP.2018.7},
  URN =		{urn:nbn:de:0030-drops-92128},
  doi =		{10.4230/LIPIcs.ECOOP.2018.7},
  annote =	{Keywords: JavaScript, semantic versioning, dynamic analysis}
}
Document
DOI: 10.4230/DARTS.4.3.8
Type Regression Testing to Detect Breaking Changes in Node.js Libraries (Artifact)

Authors: Gianluca Mezzetti, Anders Møller, and Martin Toldam Torp

Published in: DARTS, Volume 4, Issue 3, Special Issue of the 32nd European Conference on Object-Oriented Programming (ECOOP 2018)

Abstract
This artifact provides an implementation of a novel technique, type regression testing, to automatically determine whether an update of a npm library implementation affects the types of its public interface, according to how the library is being used by other npm packages. Type regression testing is implemented in the tool NoRegrets. A run of NoRegrets is parameterized with a pre-update and post-update version of the library, and it consists of three fully automatic phases. First, NoRegrets fetches a list of clients that depend upon the pre-update library, and that have a test suite that succeeds on the pre-update version. Second, NoRegrets uses an ECMAScript 6 proxy instrumentation to generate the API model of both the pre-update and post-update libraries, based on observations of how the client test suites interact with the library. Third, the two models are compared, and inconsistencies are reported as type regressions. This artifact contains the source code and an installation of NoRegrets, with a guide for how to use the tool and reproduce the experimental results presented in the paper.
Cite as

Gianluca Mezzetti, Anders Møller, and Martin Toldam Torp. Type Regression Testing to Detect Breaking Changes in Node.js Libraries (Artifact). In Special Issue of the 32nd European Conference on Object-Oriented Programming (ECOOP 2018). Dagstuhl Artifacts Series (DARTS), Volume 4, Issue 3, pp. 8:1-8:2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@Article{mezzetti_et_al:DARTS.4.3.8,
  author =	{Mezzetti, Gianluca and M{\o}ller, Anders and Torp, Martin Toldam},
  title =	{{Type Regression Testing to Detect Breaking Changes in Node.js Libraries (Artifact)}},
  pages =	{8:1--8:2},
  journal =	{Dagstuhl Artifacts Series},
  ISSN =	{2509-8195},
  year =	{2018},
  volume =	{4},
  number =	{3},
  editor =	{Mezzetti, Gianluca and M{\o}ller, Anders and Torp, Martin Toldam},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DARTS.4.3.8},
  URN =		{urn:nbn:de:0030-drops-92394},
  doi =		{10.4230/DARTS.4.3.8},
  annote =	{Keywords: JavaScript, semantic versioning, dynamic analysis}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact