More Web Proxy on the site http://driver.im/

research-article

Dynamic determinacy analysis

Authors:

Manu Sridharan,

Frank TipAuthors Info & Claims

PLDI '13: Proceedings of the 34th ACM SIGPLAN Conference on Programming Language Design and Implementation

Pages 165 - 174

https://doi.org/10.1145/2491956.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

Laursen MXu WMøller A(2024)Reducing Static Analysis Unsoundness with Approximate InterpretationProceedings of the ACM on Programming Languages10.1145/36564248:PLDI(1165-1188)Online publication date: 20-Jun-2024
https://dl.acm.org/doi/10.1145/3656424
Park JLee HRyu S(2021)A Survey of Parametric Static AnalysisACM Computing Surveys10.1145/346445754:7(1-37)Online publication date: 18-Jul-2021
https://dl.acm.org/doi/10.1145/3464457
Serrano M(2020)JavaScript AOT compilationACM SIGPLAN Notices10.1145/3393673.327695053:8(50-63)Online publication date: 6-Apr-2020
https://dl.acm.org/doi/10.1145/3393673.3276950
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 ...
Determinacy in static analysis for jQuery
OOPSLA '14: Proceedings of the 2014 ACM International Conference on Object Oriented Programming Systems Languages & Applications

Static analysis for JavaScript can potentially help programmers find errors early during development. Although much progress has been made on analysis techniques, a major obstacle is the prevalence of libraries, in particular jQuery, which apply ...
Dynamic determinacy analysis
PLDI '13

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 ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

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

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

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]

Sponsors

SIGPLAN: ACM Special Interest Group on Programming Languages

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 16 June 2013

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

PLDI '13

Sponsor:

SIGPLAN

PLDI '13: ACM SIGPLAN Conference on Programming Language Design and Implementation

June 16 - 19, 2013

Washington, Seattle, USA

Acceptance Rates

PLDI '13 Paper Acceptance Rate 46 of 267 submissions, 17%;

Overall Acceptance Rate 406 of 2,067 submissions, 20%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

62
Total Citations
View Citations
545
Total Downloads

Downloads (Last 12 months)18
Downloads (Last 6 weeks)5

Reflects downloads up to 14 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Laursen MXu WMøller A(2024)Reducing Static Analysis Unsoundness with Approximate InterpretationProceedings of the ACM on Programming Languages10.1145/36564248:PLDI(1165-1188)Online publication date: 20-Jun-2024
https://dl.acm.org/doi/10.1145/3656424
Park JLee HRyu S(2021)A Survey of Parametric Static AnalysisACM Computing Surveys10.1145/346445754:7(1-37)Online publication date: 18-Jul-2021
https://dl.acm.org/doi/10.1145/3464457
Serrano M(2020)JavaScript AOT compilationACM SIGPLAN Notices10.1145/3393673.327695053:8(50-63)Online publication date: 6-Apr-2020
https://dl.acm.org/doi/10.1145/3393673.3276950
Staicu CTorp MSchäfer MMøller APradel MRothermel GBae D(2020)Extracting taint specifications for JavaScript librariesProceedings of the ACM/IEEE 42nd International Conference on Software Engineering10.1145/3377811.3380390(198-209)Online publication date: 27-Jun-2020
https://dl.acm.org/doi/10.1145/3377811.3380390
Naderi-Afooshteh AKwon YNguyen-Tuong ABagheri-Marzijarani MDavidson JBalenson D(2019)CubismoProceedings of the 35th Annual Computer Security Applications Conference10.1145/3359789.3359821(430-443)Online publication date: 9-Dec-2019
https://dl.acm.org/doi/10.1145/3359789.3359821
Naderi-Afooshteh AKwon YNguyen-Tuong ARazmjoo-Qalaei AZamiri-Gourabi MDavidson JCavallaro LKinder JWang XKatz J(2019)MalMaxProceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security10.1145/3319535.3363199(1849-1866)Online publication date: 6-Nov-2019
https://dl.acm.org/doi/10.1145/3319535.3363199
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
Ryu SPark JPark J(2019)Toward Analysis and Bug Finding in JavaScript Web Applications in the WildIEEE Software10.1109/MS.2018.11011340836:3(74-82)Online publication date: May-2019
https://doi.org/10.1109/MS.2018.110113408
Ko YRival XRyu S(2019)Weakly sensitive analysis for JavaScript object‐manipulating programsSoftware: Practice and Experience10.1002/spe.267649:5(840-884)Online publication date: 7-Jan-2019
https://doi.org/10.1002/spe.2676
Serrano MFelgentreff T(2018)JavaScript AOT compilationProceedings of the 14th ACM SIGPLAN International Symposium on Dynamic Languages10.1145/3276945.3276950(50-63)Online publication date: 24-Oct-2018
https://dl.acm.org/doi/10.1145/3276945.3276950
Show More Cited By

View Options

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 Table of Contents