Document Open Access Logo

Adaptive Context-sensitive Analysis for JavaScript

Authors Shiyi Wei, Barbara G. Ryder

PDF

File

Thumbnail PDF
PDF
LIPIcs.ECOOP.2015.712.pdf
  • Filesize: 0.76 MB
  • 23 pages

Document Identifiers

Subject Classification

Keywords
  • Context Sensitivity
  • JavaScript
  • Static Program Analysis

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Abstract

Context sensitivity is a technique to improve program analysis precision by distinguishing between function calls. A specific context-sensitive analysis is usually designed to accommodate the programming paradigm of a particular programming language. JavaScript features both the object-oriented and functional programming paradigms. Our empirical study suggests that there is no single context-sensitive analysis that always produces precise results for JavaScript applications. This observation motivated us to design an adaptive analysis, selecting a context-sensitive analysis from multiple choices for each function. Our two-staged adaptive context-sensitive analysis first extracts function characteristics from an inexpensive points-to analysis and then chooses a specialized context-sensitive analysis per function based on the heuristics. The experimental results show that our adaptive analysis achieved more precise results than any single context-sensitive analysis for several JavaScript programs in the benchmarks.

Cite As Get BibTex

Shiyi Wei and Barbara G. Ryder. Adaptive Context-sensitive Analysis for JavaScript. In 29th European Conference on Object-Oriented Programming (ECOOP 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 37, pp. 712-734, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015) https://doi.org/10.4230/LIPIcs.ECOOP.2015.712

Author Details

Shiyi Wei
Barbara G. Ryder

References

  1. Ole Agesen. The cartesian product algorithm: Simple and precise type inference of parametric polymorphism. In Proceedings of the 9th European Conference on Object-Oriented Programming, ECOOP'95, pages 2-26, 1995. Google Scholar
  2. David Grove, Greg DeFouw, Jeffrey Dean, and Craig Chambers. Call graph construction in object-oriented languages. In Proceedings of the 12th ACM SIGPLAN Conference on Object-oriented Programming, Systems, Languages, and Applications, OOPSLA'97, pages 108-124, 1997. Google Scholar
  3. Samuel Z. Guyer and Calvin Lin. Client-driven pointer analysis. In Proceedings of the 10th International Conference on Static Analysis, SAS'03, pages 214-236, 2003. Google Scholar
  4. Simon Holm Jensen, Anders Møller, and Peter Thiemann. Type analysis for JavaScript. In Proceedings of the 16th International Symposium on Static Analysis, SAS'09, pages 238-255, 2009. Google Scholar
  5. Vineeth Kashyap, Kyle Dewey, Ethan A. Kuefner, John Wagner, Kevin Gibbons, John Sarracino, Ben Wiedermann, and Ben Hardekopf. Jsai: A static analysis platform for JavaScript. In Proceedings of the 22Nd ACM SIGSOFT International Symposium on Foundations of Software Engineering, FSE 2014, pages 121-132, 2014. Google Scholar
  6. George Kastrinis and Yannis Smaragdakis. Hybrid context-sensitivity for points-to analysis. In Proceedings of the 34th ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI'13, pages 423-434, 2013. Google Scholar
  7. Ondřej Lhoták and Laurie Hendren. Evaluating the benefits of context-sensitive points-to analysis using a bdd-based implementation. ACM Trans. Softw. Eng. Methodol., 18(1):3:1-3:53, October 2008. Google Scholar
  8. Percy Liang and Mayur Naik. Scaling abstraction refinement via pruning. In Proceedings of the 32Nd ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI'11, pages 590-601, 2011. Google Scholar
  9. Henry Lieberman. Using prototypical objects to implement shared behavior in object-oriented systems. In Conference proceedings on Object-oriented programming systems, languages and applications, OOPLSA'86, pages 214-223, 1986. Google Scholar
  10. Ana Milanova, Atanas Rountev, and Barbara G. Ryder. Parameterized object sensitivity for points-to analysis for Java. ACM Trans. Softw. Eng. Methodol., 14(1):1-41, January 2005. Google Scholar
  11. Hakjoo Oh, Wonchan Lee, Kihong Heo, Hongseok Yang, and Kwangkeun Yi. Selective context-sensitivity guided by impact pre-analysis. In Proceedings of the 35th ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI'14, pages 475-484, 2014. Google Scholar
  12. J. Ross Quinlan. C4.5: Programs for Machine Learning. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 1993. Google Scholar
  13. RedMonk. The RedMonk programming language rankings. http://redmonk.com/sogrady/2014/06/13/language-rankings-6-14/, 2014.
  14. Micha Sharir and Amir Pnueli. Two approaches to interprocedural data flow analysis. Program Flow Analysis: Theory and Applications, pages 189-234, 1981. Google Scholar
  15. Olin Grigsby Shivers. Control-flow Analysis of Higher-order Languages of Taming Lambda. PhD thesis, Carnegie Mellon University, 1991. Google Scholar
  16. Yannis Smaragdakis, Martin Bravenboer, and Ondrej Lhoták. Pick your contexts well: understanding object-sensitivity. In Proceedings of the 38th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages, POPL'11, pages 17-30, 2011. Google Scholar
  17. Yannis Smaragdakis, George Kastrinis, and George Balatsouras. Introspective analysis: Context-sensitivity, across the board. In Proceedings of the 35th ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI'14, pages 485-495, 2014. Google Scholar
  18. Manu Sridharan and Rastislav Bodík. Refinement-based context-sensitive points-to analysis for Java. In Proceedings of the 2006 ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI'06, pages 387-400, 2006. Google Scholar
  19. Manu Sridharan, Julian Dolby, Satish Chandra, Max Schäfer, and Frank Tip. Correlation tracking for points-to analysis of JavaScript. In Proceedings of the 26th European Conference on Object-Oriented Programming, ECOOP'12, pages 435-458, 2012. Google Scholar
  20. Peter Wegner. Dimensions of object-based language design. In Conference proceedings on Object-oriented programming systems, languages and applications, OOPSLA'87, pages 168-182, 1987. Google Scholar
  21. Shiyi Wei and Barbara G. Ryder. Practical blended taint analysis for JavaScript. In Proceedings of the 2013 International Symposium on Software Testing and Analysis, ISSTA 2013, pages 336-346, 2013. Google Scholar
  22. Shiyi Wei and Barbara G. Ryder. State-sensitive points-to analysis for the dynamic behavior of JavaScript objects. In Proceedings of the 28th European Conference on Object-oriented Programming, ECOOP'14, pages 1-26, 2014. Google Scholar
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-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact