research-article

Dynamic determinacy analysis

Authors:

Manu Sridharan,

Frank TipAuthors Info & Claims

ACM SIGPLAN Notices, Volume 48, Issue 6

Pages 165 - 174

https://doi.org/10.1145/2499370.2462168

Published: 16 June 2013 Publication History

Abstract

We present an analysis for identifying determinate variables and expressions that always have the same value at a given program point. This information can be exploited by client analyses and tools to, e.g., identify dead code or specialize uses of dynamic language constructs such as eval, replacing them with equivalent static constructs. Our analysis is completely dynamic and only needs to observe a single execution of the program, yet the determinacy facts it infers hold for any execution. We present a formal soundness proof of the analysis for a simple imperative language, and a prototype implementation that handles full JavaScript. Finally, we report on two case studies that explored how static analysis for JavaScript could leverage the information gathered by dynamic determinacy analysis. We found that in some cases scalability of static pointer analysis was improved dramatically, and that many uses of runtime code generation could be eliminated.

References

[1]

Umut A. Acar. Self-Adjusting Computation. Ph.D. thesis, Carnegie Mellon University, 2005.

Digital Library

[2]

Shay Artzi, Julian Dolby, Simon Holm Jensen, Anders Møller, and Frank Tip. A Framework for Automated Testing of JavaScript Web Applications. In ICSE, 2011.

Digital Library

[3]

Thomas H. Austin and Cormac Flanagan. Efficient Purely-Dynamic Information Flow Analysis. In PLAS, 2009.

Digital Library

[4]

Thomas H. Austin and Cormac Flanagan. Multiple Facets for Dynamic Information Flow. In POPL, 2012.

Digital Library

[5]

Eric Bodden, Andreas Sewe, Jan Sinschek, Hela Oueslati, and Mira Mezini. Taming Reflection: Aiding Static Analysis in the Presence of Reflection and Custom Class Loaders. In ICSE, 2011.

Digital Library

[6]

Yan Chen, Joshua Dunfield, and Umut A. Acar. Type-Directed Automatic Incrementalization. In PLDI, 2012.

Digital Library

[7]

Yan Chen, Joshua Dunfield, Matthew Hammer, and Umut Acar. Implicit Self-Adjusting Computation for Purely Functional Programs. In ICFP, 2011.

Digital Library

[8]

Aske Simon Christensen, Anders Møller, and Michael I. Schwartzbach. Precise Analysis of String Expressions. In SAS, 2003.

[9]

Ravi Chugh, Jeffrey A. Meister, Ranjit Jhala, and Sorin Lerner. Staged Information Flow for JavaScript. In PLDI, 2009.

Digital Library

[10]

Charles Consel. Polyvariant Binding-Time Analysis For Applicative Languages. In PEPM, 1993.

Digital Library

[11]

Douglas Crockford. JavaScript: The Good Parts. O'Reilly, 2008.

Digital Library

[12]

Bruno Dufour, Barbara G. Ryder, and Gary Sevitsky. Blended Analysis for Performance Understanding of Framework-based Applications. In ISSTA, 2007.

Digital Library

[13]

Michael Furr, Jong-hoon An, and Jeffrey S. Foster. Profile-guided Static Typing for Dynamic Scripting Languages. In OOPSLA, 2009.

Digital Library

[14]

Salvatore Guarnieri and V. Benjamin Livshits.textscGatekeeper: Mostly Static Enforcement of Security and Reliability Policies for JavaScript Code. In USENIX Security Symposium, 2009.

Digital Library

[15]

Arjun Guha, Claudiu Saftoiu, and Shriram Krishnamurthi. The Essence of JavaScript. In ECOOP, 2010.

Digital Library

[16]

Brian Hackett and Shu-yu Guo. Fast and Precise Hybrid Type Inference for JavaScript. In PLDI, 2012.

Digital Library

[17]

Simon Holm Jensen, Peter A. Jonsson, and Anders Møller. Remedying the Eval That Men Do. In ISSTA, 2012.

Digital Library

[18]

Simon Holm Jensen, Anders Møller, and Peter Thiemann. Type Analysis for JavaScript. In SAS, 2009.

Digital Library

[19]

Neil D. Jones, Carsten K. Gomard, and Peter Sestoft. Partial evaluation and automatic program generation. Prentice-Hall, Inc., 1993.

Digital Library

[20]

James C. King. Symbolic Execution and Program Testing. Communications of the ACM, 19(7), July 1976.

Digital Library

[21]

Etienne Kneuss, Philippe Suter, and Viktor Kuncak. Runtime Instrumentation for Precise Flow-Sensitive Type Analysis. In RV, 2010.

Digital Library

[22]

Xavier Leroy and Hervé Grall. Coinductive Big-Step Operational Semantics. Inf. Comput., 207(2):284--304, 2009.

Digital Library

[23]

Fadi Meawad, Gregor Richards, Floréal Morandat, and Jan Vitek. Eval Begone! Semi-Automated Removal of Eval from JavaScript Programs. In OOPSLA, 2012.

Digital Library

[24]

Thomas W. Reps, Stefan Schwoon, Somesh Jha, and David Melski. Weighted Pushdown Systems and Their Application to Interprocedural Dataflow Analysis. Sci. Comput. Program., 58(1--2):206--263, 2005.

Digital Library

[25]

Thomas W. Reps and Tim Teitelbaum. The Synthesizer Generator. In SDE, 1984.

Digital Library

[26]

Gregor Richards, Christian Hammer, Brian Burg, and Jan Vitek. The Eval That Men Do--A Large-Scale Study of the Use of Eval in JavaScript Applications. In ECOOP, 2011.

Digital Library

[27]

Gregor Richards, Sylvain Lebresne, Brian Burg, and Jan Vitek. An Analysis of the Dynamic Behavior of JavaScript Programs. In PLDI, 2010.

Digital Library

[28]

David A. Schmidt. Trace-Based Abstract Interpretation of Operational Semantics. Lisp and Symbolic Computation, 10(3):237--271, 1998.

Digital Library

[29]

O. Shivers. Control Flow Analysis in Scheme. In PLDI, 1988.

Digital Library

[30]

Manu Sridharan, Julian Dolby, Satish Chandra, Max Schäfer, and Frank Tip. Correlation Tracking for Points-To Analysis of JavaScript. In ECOOP, 2012.

Digital Library

[31]

Shiyi Wei and Barbara G. Ryder. A Practical Blended Analysis for Dynamic Features in JavaScript. TR 12--18, Virginia Tech, 2012.

[32]

Steve Zdancewic. Programming Languages for Information Security. PhD thesis, Cornell University, 2002.

Digital Library

Cited By

Park JYoun DLee KRyu S(2023)Feature-Sensitive Coverage for Conformance Testing of Programming Language ImplementationsProceedings of the ACM on Programming Languages10.1145/35912407:PLDI(493-515)Online publication date: 6-Jun-2023
https://dl.acm.org/doi/10.1145/3591240
Liu XZiarek LBissyandé TKlein JBird CSarro F(2023)PTdetector: An Automated JavaScript Front-End Library DetectorProceedings of the 38th IEEE/ACM International Conference on Automated Software Engineering10.1109/ASE56229.2023.00049(649-660)Online publication date: 11-Nov-2023
https://dl.acm.org/doi/10.1109/ASE56229.2023.00049
Park JAn SRyu SRoychoudhury ACadar CKim M(2022)Automatically deriving JavaScript static analyzers from specifications using Meta-level static analysisProceedings of the 30th ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering10.1145/3540250.3549097(1022-1034)Online publication date: 7-Nov-2022
https://dl.acm.org/doi/10.1145/3540250.3549097
Show More Cited By

Index Terms

Dynamic determinacy analysis
1. Theory of computation
  1. Semantics and reasoning
    1. Program reasoning
      1. Program analysis
    2. Program semantics

Recommendations

Accelerating JavaScript static analysis via dynamic shortcuts
ESEC/FSE 2021: Proceedings of the 29th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering

JavaScript has become one of the most widely used programming languages for web development, server-side programming, and even micro-controllers for IoT. However, its extremely functional and dynamic features degrade the performance and precision of ...
Dynamic determinacy analysis
PLDI '13: Proceedings of the 34th ACM SIGPLAN Conference on Programming Language Design and Implementation

We present an analysis for identifying determinate variables and expressions that always have the same value at a given program point. This information can be exploited by client analyses and tools to, e.g., identify dead code or specialize uses of ...
Combined Static and Dynamic Analysis

Static analysis is usually faster than dynamic analysis but less precise. Therefore it is often desirable to retain information from static analysis for run-time verification, or to compare the results of both techniques. However, this requires writing ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGPLAN Notices

ACM SIGPLAN Notices Volume 48, Issue 6

PLDI '13

June 2013

515 pages

ISSN:0362-1340

EISSN:1558-1160

DOI:10.1145/2499370

Issue’s Table of Contents

PLDI '13: Proceedings of the 34th ACM SIGPLAN Conference on Programming Language Design and Implementation
June 2013
546 pages
ISBN:9781450320146
DOI:10.1145/2491956
General Chair:
Hans-J. Boehm
HP Labs
,
Program Chair:
Cormac Flanagan
University of California, Santa Cruz

Copyright © 2013 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 16 June 2013

Published in SIGPLAN Volume 48, Issue 6

Check for updates

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

61
Total Citations
View Citations
542
Total Downloads

Downloads (Last 12 months)21
Downloads (Last 6 weeks)4

Reflects downloads up to 12 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Park JYoun DLee KRyu S(2023)Feature-Sensitive Coverage for Conformance Testing of Programming Language ImplementationsProceedings of the ACM on Programming Languages10.1145/35912407:PLDI(493-515)Online publication date: 6-Jun-2023
https://dl.acm.org/doi/10.1145/3591240
Liu XZiarek LBissyandé TKlein JBird CSarro F(2023)PTdetector: An Automated JavaScript Front-End Library DetectorProceedings of the 38th IEEE/ACM International Conference on Automated Software Engineering10.1109/ASE56229.2023.00049(649-660)Online publication date: 11-Nov-2023
https://dl.acm.org/doi/10.1109/ASE56229.2023.00049
Park JAn SRyu SRoychoudhury ACadar CKim M(2022)Automatically deriving JavaScript static analyzers from specifications using Meta-level static analysisProceedings of the 30th ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering10.1145/3540250.3549097(1022-1034)Online publication date: 7-Nov-2022
https://dl.acm.org/doi/10.1145/3540250.3549097
Park JPark JYoun DRyu SSpinellis DGousios GChechik MDi Penta M(2021)Accelerating JavaScript static analysis via dynamic shortcutsProceedings of the 29th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering10.1145/3468264.3468556(1129-1140)Online publication date: 20-Aug-2021
https://dl.acm.org/doi/10.1145/3468264.3468556
Zhang MMeng WDevanbu PCohen MZimmermann T(2020)Detecting and understanding JavaScript global identifier conflicts on the webProceedings of the 28th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering10.1145/3368089.3409747(38-49)Online publication date: 8-Nov-2020
https://dl.acm.org/doi/10.1145/3368089.3409747
Tomasdottir KAniche Mvan Deursen A(2020)The Adoption of JavaScript Linters in Practice: A Case Study on ESLintIEEE Transactions on Software Engineering10.1109/TSE.2018.287105846:8(863-891)Online publication date: 1-Aug-2020
https://doi.org/10.1109/TSE.2018.2871058
Welearegai GSchlueter MHammer CHung CPapadopoulos G(2019)Static security evaluation of an industrial web applicationProceedings of the 34th ACM/SIGAPP Symposium on Applied Computing10.1145/3297280.3297471(1952-1961)Online publication date: 8-Apr-2019
https://dl.acm.org/doi/10.1145/3297280.3297471
Tómasdóttir KAniche MDeursen ARosu GDi Penta MNguyen T(2017)Why and how JavaScript developers use lintersProceedings of the 32nd IEEE/ACM International Conference on Automated Software Engineering10.5555/3155562.3155634(578-589)Online publication date: 30-Oct-2017
https://dl.acm.org/doi/10.5555/3155562.3155634
Pan JMao X(2017)Detecting DOM-Sourced Cross-Site Scripting in Browser Extensions2017 IEEE International Conference on Software Maintenance and Evolution (ICSME)10.1109/ICSME.2017.11(24-34)Online publication date: Sep-2017
https://doi.org/10.1109/ICSME.2017.11
Tomasdottir KAniche Mvan Deursen A(2017)Why and how JavaScript developers use linters2017 32nd IEEE/ACM International Conference on Automated Software Engineering (ASE)10.1109/ASE.2017.8115668(578-589)Online publication date: Oct-2017
https://doi.org/10.1109/ASE.2017.8115668
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents