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

Article

Correlation tracking for points-to analysis of javascript

Authors:

Manu Sridharan,

Satish Chandra,

Frank TipAuthors Info & Claims

ECOOP'12: Proceedings of the 26th European conference on Object-Oriented Programming

Pages 435 - 458

https://doi.org/10.1007/978-3-642-31057-7_20

Published: 11 June 2012 Publication History

Abstract

JavaScript poses significant challenges for points-to analysis, particularly due to its flexible object model in which object properties can be created and deleted at run-time and accessed via first-class names. These features cause an increase in the worst-case running time of field-sensitive Andersen-style analysis, which becomes O(N⁴), where N is the program size, in contrast to the O(N³) bound for languages like Java. In practice, we found that a standard implementation of the analysis was unable to analyze popular JavaScript frameworks.

We identify correlated dynamic property accesses as a common code pattern that is analyzed very imprecisely by the standard analysis, and show how a novel correlation tracking technique enables us to handle this pattern more precisely, thereby making the analysis more scalable. In an experimental evaluation, we found that correlation tracking often dramatically improved analysis scalability and precision on popular JavaScript frameworks, though in some cases scalability challenges remain.

References

[1]

Agesen, O.: The Cartesian Product Algorithm: Simple and Precise Type Inference of Parametric Polymorphism. In: Olthoff, W. (ed.) ECOOP 1995. LNCS, vol. 952, pp. 2-26. Springer, Heidelberg (1995)

Digital Library

[2]

An, D., Chaudhuri, A., Foster, J. S., Hicks, M.: Dynamic Inference of Static Types for Ruby. In: POPL (2011)

Digital Library

[3]

Andersen, L. O.: Program Analysis and Specialization for the C Programming Language. PhD thesis, University of Copenhagen, DIKU (1994)

[4]

Balakrishnan, G., Reps, T.: Recency-Abstraction for Heap-Allocated Storage. In: Yi, K. (ed.) SAS 2006. LNCS, vol. 4134, pp. 221-239. Springer, Heidelberg (2006)

Digital Library

[5]

Blackshear, S., Chang, B.-Y. E., Sankaranarayanan, S., Sridharan, M.: The Flow-Insensitive Precision of Andersen's Analysis in Practice. In: Yahav, E. (ed.) SAS 2011. LNCS, vol. 6887, pp. 60-76. Springer, Heidelberg (2011)

Digital Library

[6]

Chaudhuri, S.: Subcubic Algorithms for Recursive State Machines. In: POPL (2008)

Digital Library

[7]

ECMA. ECMAScript Language Specification, 5th edn., ECMA-262 (2009)

[8]

Feldthaus, A., Millstein, T., Møller, A., Schäfer, M., Tip, F.: Tool-supported Refactoring for JavaScript. In: OOPSLA (2011)

Digital Library

[9]

Grove, D., Chambers, C.: A Framework for Call Graph Construction Algorithms. TOPLAS 23(6) (2001)

Digital Library

[10]

Guarnieri, S., Livshits, V. B.: Gatekeeper: Mostly Static Enforcement of Security and Reliability Policies for JavaScript Code. In: USENIX Security Symposium (2009)

Digital Library

[11]

Guarnieri, S., Livshits, V. B.: Gulfstream: Incremental Static Analysis for Streaming JavaScript Applications. In: WebApps (2010)

Digital Library

[12]

Guarnieri, S., Pistoia, M., Tripp, O., Dolby, J., Teilhet, S., Berg, R.: Saving the World Wide Web from Vulnerable JavaScript. In: ISSTA (2011)

Digital Library

[13]

Guha, A., Saftoiu, C., Krishnamurthi, S.: The Essence of JavaScript. In: D'Hondt, T. (ed.) ECOOP 2010. LNCS, vol. 6183, pp. 126-150. Springer, Heidelberg (2010)

Digital Library

[14]

Jensen, S. H., Møller, A., Thiemann, P.: Type Analysis for JavaScript. In: Palsberg, J., Su, Z. (eds.) SAS 2009. LNCS, vol. 5673, pp. 238-255. Springer, Heidelberg (2009)

[15]

Jensen, S. H., Møller, A., Thiemann, P.: Interprocedural Analysis with Lazy Propagation. In: Cousot, R., Martel, M. (eds.) SAS 2010. LNCS, vol. 6337, pp. 320-339. Springer, Heidelberg (2010)

Digital Library

[16]

Lhoták, O., Hendren, L.: Scaling Java Points-to Analysis Using SPARK. In: Hedin, G. (ed.) CC 2003. LNCS, vol. 2622, pp. 153-169. Springer, Heidelberg (2003)

Digital Library

[17]

Maffeis, S., Mitchell, J.C., Taly, A.: An Operational Semantics for JavaScript. In: Ramalingam, G. (ed.) APLAS 2008. LNCS, vol. 5356, pp. 307-325. Springer, Heidelberg (2008)

Digital Library

[18]

Milanova, A., Rountev, A., Ryder, B. G.: Parameterized Object Sensitivity for Points-to Analysis for Java. TOSEM 14(1) (2005)

Digital Library

[19]

Schäfer, M., Verbaere, M., Ekman, T., de Moor, O.: Stepping Stones over the Refactoring Rubicon. In: Drossopoulou, S. (ed.) ECOOP 2009. LNCS, vol. 5653, pp. 369-393. Springer, Heidelberg (2009)

Digital Library

[20]

Smaragdakis, Y., Bravenboer, M., Lhoták, O.: Pick Your Contexts Well: Understanding Object-sensitivity. In: POPL (2011)

Digital Library

[21]

Sridharan, M., Fink, S. J.: The Complexity of Andersen's Analysis in Practice. In: Palsberg, J., Su, Z. (eds.) SAS 2009. LNCS, vol. 5673, pp. 205-221. Springer, Heidelberg (2009)

Digital Library

[22]

Sridharan, M., Gopan, D., Shan, L., Bodík, R.: Demand-Driven Points-To Analysis for Java. In: OOPSLA (2005)

Digital Library

[23]

Tripp, O., Pistoia, M., Fink, S. J., Sridharan, M., Weisman, O.: TAJ: Effective Taint Analysis of Web Applications. In: PLDI (2009)

Digital Library

[24]

Tripp, O., Weisman, O.: Hybrid Analysis for JavaScript Security Assessment. In: ESEC/FSE 2011, Industrial Track (2011)

[25]

Vardoulakis, D., Shivers, O.: CFA2: A Context-Free Approach to Control-Flow Analysis. In: Gordon, A. D. (ed.) ESOP 2010. LNCS, vol. 6012, pp. 570-589. Springer, Heidelberg (2010)

Digital Library

[26]

Watson, T. J.: Libraries for Analysis (WALA), http://wala.sf.net

[27]

Web Technology Surveys. Usage of JavaScript libraries for websites, http://w3techs.com/technologies/overview/javascript_library/all (accessed March 30, 2012)

[28]

Zheng, Y., Bao, T., Zhang, X.: Statically Locating Web Application Bugs Caused by Asynchronous Calls. In: WWW (2011)

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
Ferreira MMonteiro MBrito TCoimbra MSantos NJia LSantos J(2024)Efficient Static Vulnerability Analysis for JavaScript with Multiversion Dependency GraphsProceedings of the ACM on Programming Languages10.1145/36563948:PLDI(417-441)Online publication date: 20-Jun-2024
https://dl.acm.org/doi/10.1145/3656394
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

Correlation tracking for points-to analysis of javascript
1. Theory of computation
  1. Semantics and reasoning
    1. Program reasoning

Recommendations

Evaluating the benefits of context-sensitive points-to analysis using a BDD-based implementation

We present Paddle, a framework of BDD-based context-sensitive points-to and call graph analyses for Java, as well as client analyses that use their results. Paddle supports several variations of context-sensitive analyses, including call site strings ...
Points-to analysis for JavaScript
SAC '09: Proceedings of the 2009 ACM symposium on Applied Computing

JavaScript is widely used by web developers and the complexity of JavaScript programs has increased over the last year. Therefore, the need for program analysis for JavaScript is evident. Points-to analysis for JavaScript is to determine the set of ...
On-demand dynamic summary-based points-to analysis
CGO '12: Proceedings of the Tenth International Symposium on Code Generation and Optimization

Static analyses can be typically accelerated by reducing redundancies. Modern demand-driven points-to or alias analysis techniques rest on the foundation of Context-Free Language (CFL) reachability. These techniques achieve high precision efficiently ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

ECOOP'12: Proceedings of the 26th European conference on Object-Oriented Programming

June 2012

763 pages

ISBN:9783642310560

Editor:
James Noble
School of Engineering and Computer Science, Victoria University of Wellington, Wellington, New Zealand

Sponsors

Adobe
Microsoft Reasearch: Microsoft Reasearch
ORACLE: ORACLE
AITO: Association Internationale pour les Technologies Objets
Purdue University: Purdue University

In-Cooperation

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 11 June 2012

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

67
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 03 Mar 2025

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
Ferreira MMonteiro MBrito TCoimbra MSantos NJia LSantos J(2024)Efficient Static Vulnerability Analysis for JavaScript with Multiversion Dependency GraphsProceedings of the ACM on Programming Languages10.1145/36563948:PLDI(417-441)Online publication date: 20-Jun-2024
https://dl.acm.org/doi/10.1145/3656394
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
Jeon MOh H(2022)Return of CFA: call-site sensitivity can be superior to object sensitivity even for object-oriented programsProceedings of the ACM on Programming Languages10.1145/34987206:POPL(1-29)Online publication date: 12-Jan-2022
https://dl.acm.org/doi/10.1145/3498720
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
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
Karakochev AZhang G(2021)Static Analysis of Large-Scale JavaScript Front EndWeb Engineering10.1007/978-3-030-74296-6_36(483-489)Online publication date: 18-May-2021
https://dl.acm.org/doi/10.1007/978-3-030-74296-6_36
Stein BNielsen BChang BMøller A(2019)Static analysis with demand-driven value refinementProceedings of the ACM on Programming Languages10.1145/33605663:OOPSLA(1-29)Online publication date: 10-Oct-2019
https://dl.acm.org/doi/10.1145/3360566
Nielsen BHassanshahi BGauthier FDumas MPfahl DApel SRusso A(2019)Nodest: feedback-driven static analysis of Node.js applicationsProceedings of the 2019 27th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering10.1145/3338906.3338933(455-465)Online publication date: 12-Aug-2019
https://dl.acm.org/doi/10.1145/3338906.3338933
Almashfi NLu LPicker KMaldonado C(2019)Precise String Analysis for JavaScript Programs Using AutomataProceedings of the 2019 8th International Conference on Software and Computer Applications10.1145/3316615.3316662(159-166)Online publication date: 19-Feb-2019
https://dl.acm.org/doi/10.1145/3316615.3316662
Show More Cited By

View Options

View options

Figures

Tables

Media

View Table of Conten