Static Analysis for Asynchronous JavaScript Programs

Authors Thodoris Sotiropoulos, Benjamin Livshits



PDF
Thumbnail PDF

File

LIPIcs.ECOOP.2019.8.pdf
  • Filesize: 0.79 MB
  • 29 pages

Document Identifiers

Author Details

Thodoris Sotiropoulos
  • Athens University of Economics and Business, Greece
Benjamin Livshits
  • Imperial College London, UK
  • Brave Software, London, UK

Acknowledgements

We would like to thank the anonymous ECOOP reviewers, as well as Max Schlueter and Dimitris Mitropoulos for their insightful comments and feedback.

Cite AsGet BibTex

Thodoris Sotiropoulos and Benjamin Livshits. Static Analysis for Asynchronous JavaScript Programs. In 33rd European Conference on Object-Oriented Programming (ECOOP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 134, pp. 8:1-8:29, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.ECOOP.2019.8

Abstract

Asynchrony has become an inherent element of JavaScript, as an effort to improve the scalability and performance of modern web applications. To this end, JavaScript provides programmers with a wide range of constructs and features for developing code that performs asynchronous computations, including but not limited to timers, promises, and non-blocking I/O. However, the data flow imposed by asynchrony is implicit, and not always well-understood by the developers who introduce many asynchrony-related bugs to their programs. Worse, there are few tools and techniques available for analyzing and reasoning about such asynchronous applications. In this work, we address this issue by designing and implementing one of the first static analysis schemes capable of dealing with almost all the asynchronous primitives of JavaScript up to the 7th edition of the ECMAScript specification. Specifically, we introduce the callback graph, a representation for capturing data flow between asynchronous code. We exploit the callback graph for designing a more precise analysis that respects the execution order between different asynchronous functions. We parameterize our analysis with one novel context-sensitivity flavor, and we end up with multiple analysis variations for building callback graph. We performed a number of experiments on a set of hand-written and real-world JavaScript programs. Our results show that our analysis can be applied to medium-sized programs achieving 79% precision, on average. The findings further suggest that analysis sensitivity is beneficial for the vast majority of the benchmarks. Specifically, it is able to improve precision by up to 28.5%, while it achieves an 88% precision on average without highly sacrificing performance.

Subject Classification

ACM Subject Classification
  • Theory of computation → Program analysis
  • Software and its engineering → Semantics
Keywords
  • static analysis
  • asynchrony
  • JavaScript

Metrics

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

References

  1. Saba Alimadadi, Di Zhong, Magnus Madsen, and Frank Tip. Finding Broken Promises in Asynchronous JavaScript Programs. Proc. ACM Program. Lang., 2(OOPSLA):162:1-162:26, 2018. URL: http://dx.doi.org/10.1145/3276532.
  2. Gogul Balakrishnan and Thomas Reps. Recency-Abstraction for Heap-allocated Storage. In Proceedings of the 13th International Conference on Static Analysis, SAS'06, pages 221-239, 2006. URL: http://dx.doi.org/10.1007/11823230_15.
  3. Patrick Cousot and Radhia Cousot. Abstract Interpretation: A Unified Lattice Model for Static Analysis of Programs by Construction or Approximation of Fixpoints. In Proceedings of the 4th ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages, POPL '77, pages 238-252, 1977. URL: http://dx.doi.org/10.1145/512950.512973.
  4. Frank Dabek, Nickolai Zeldovich, Frans Kaashoek, David Mazières, and Robert Morris. Event-driven programming for robust software. In Proceedings of the 10th workshop on ACM SIGOPS European workshop, pages 186-189. ACM, 2002. Google Scholar
  5. James Davis, Arun Thekumparampil, and Dongyoon Lee. Node.Fz: Fuzzing the server-side event-driven architecture. In Proceedings of the Twelfth European Conference on Computer Systems, EuroSys '17, pages 145-160, 2017. URL: http://dx.doi.org/10.1145/3064176.3064188.
  6. Asger Feldthaus, Todd Millstein, Anders Møller, Max Schäfer, and Frank Tip. Tool-supported Refactoring for JavaScript. In Proceedings of the 2011 ACM International Conference on Object Oriented Programming Systems Languages and Applications, OOPSLA '11, pages 119-138, 2011. URL: http://dx.doi.org/10.1145/2048066.2048078.
  7. Asger Feldthaus and Anders Møller. Semi-automatic Rename Refactoring for JavaScript. In Proceedings of the 2013 ACM SIGPLAN International Conference on Object Oriented Programming Systems Languages & Applications, OOPSLA '13, pages 323-338, 2013. URL: http://dx.doi.org/10.1145/2509136.2509520.
  8. Asger Feldthaus, Max Schäfer, Manu Sridharan, Julian Dolby, and Frank Tip. Efficient Construction of Approximate Call Graphs for JavaScript IDE Services. In Proceedings of the 2013 International Conference on Software Engineering, ICSE '13, pages 752-761, 2013. URL: http://dx.doi.org/10.1109/ICSE.2013.6606621.
  9. Matthias Felleisen, Robert Bruce Findler, and Matthew Flatt. Semantics engineering with PLT Redex. Mit Press, 2009. Google Scholar
  10. Mattias Felleisen and D. P. Friedman. A Calculus for Assignments in Higher-order Languages. In Proceedings of the 14th ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages, POPL '87, pages 314-, 1987. URL: http://dx.doi.org/10.1145/41625.41654.
  11. K. Gallaba, Q. Hanam, A. Mesbah, and I. Beschastnikh. Refactoring Asynchrony in JavaScript. In 2017 IEEE International Conference on Software Maintenance and Evolution (ICSME), pages 353-363, 2017. URL: http://dx.doi.org/10.1109/ICSME.2017.83.
  12. K. Gallaba, A. Mesbah, and I. Beschastnikh. Don't Call Us, We'll Call You: Characterizing Callbacks in Javascript. In 2015 ACM/IEEE International Symposium on Empirical Software Engineering and Measurement (ESEM), pages 1-10, 2015. URL: http://dx.doi.org/10.1109/ESEM.2015.7321196.
  13. Philippa Anne Gardner, Sergio Maffeis, and Gareth David Smith. Towards a Program Logic for JavaScript. In Proceedings of the 39th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL '12, pages 31-44, 2012. URL: http://dx.doi.org/10.1145/2103656.2103663.
  14. Github. GitHub Octoverse 2017 | Highlights from the last twelve months. https://octoverse.github.com/, 2017. [Online; accessed 08-January-2019].
  15. Salvatore Guarnieri and Benjamin Livshits. GATEKEEPER: Mostly static enforcement of security and reliability policies for Javascript code. In Proceedings of the 18th Conference on USENIX Security Symposium, SSYM'09, pages 151-168, 2009. Google Scholar
  16. Arjun Guha, Claudiu Saftoiu, and Shriram Krishnamurthi. The Essence of Javascript. In Proceedings of the 24th European Conference on Object-oriented Programming, ECOOP'10, pages 126-150, 2010. Google Scholar
  17. Ben Hardekopf, Ben Wiedermann, Berkeley Churchill, and Vineeth Kashyap. Widening for Control-Flow. In Kenneth L. McMillan and Xavier Rival, editors, Verification, Model Checking, and Abstract Interpretation, pages 472-491. Springer Berlin Heidelberg, 2014. URL: http://dx.doi.org/10.1007/978-3-642-54013-4_26.
  18. Simon Holm Jensen, Magnus Madsen, and Anders Møller. Modeling the HTML DOM and Browser API in Static Analysis of JavaScript Web Applications. In Proceedings of the 19th ACM SIGSOFT Symposium and the 13th European Conference on Foundations of Software Engineering, ESEC/FSE '11, pages 59-69, 2011. URL: http://dx.doi.org/10.1145/2025113.2025125.
  19. 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. URL: http://dx.doi.org/10.1007/978-3-642-03237-0_17.
  20. Simon Holm Jensen, Anders Møller, and Peter Thiemann. Interprocedural Analysis with Lazy Propagation. In Radhia Cousot and Matthieu Martel, editors, Static Analysis, pages 320-339. Springer Berlin Heidelberg, 2010. Google Scholar
  21. 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. URL: http://dx.doi.org/10.1145/2635868.2635904.
  22. Y. Ko, H. Lee, J. Dolby, and S. Ryu. Practically Tunable Static Analysis Framework for Large-Scale JavaScript Applications (T). In 2015 30th IEEE/ACM International Conference on Automated Software Engineering (ASE), pages 541-551, 2015. URL: http://dx.doi.org/10.1109/ASE.2015.28.
  23. Hongki Lee, Sooncheol Won, Joonho Jin, Junhee Cho, and Sukyoung Ryu. SAFE: Formal specification and implementation of a scalable analysis framework for ECMAscript. In FOOL 2012: 19th International Workshop on Foundations of Object-Oriented Languages, page 96, 2012. Google Scholar
  24. 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, 2008. URL: http://dx.doi.org/10.1145/1391984.1391987.
  25. Matthew C. Loring, Mark Marron, and Daan Leijen. Semantics of Asynchronous JavaScript. In Proceedings of the 13th ACM SIGPLAN International Symposium on on Dynamic Languages, DLS 2017, pages 51-62, 2017. URL: http://dx.doi.org/10.1145/3133841.3133846.
  26. Magnus Madsen, Ondřej Lhoták, and Frank Tip. A Model for Reasoning About JavaScript Promises. Proc. ACM Program. Lang., 1(OOPSLA):86:1-86:24, 2017. URL: http://dx.doi.org/10.1145/3133910.
  27. Magnus Madsen, Frank Tip, and Ondřej Lhoták. Static Analysis of Event-driven Node.Js JavaScript Applications. In Proceedings of the 2015 ACM SIGPLAN International Conference on Object-Oriented Programming, Systems, Languages, and Applications, OOPSLA 2015, pages 505-519, 2015. URL: http://dx.doi.org/10.1145/2814270.2814272.
  28. S. Maffeis and A. Taly. Language-Based Isolation of Untrusted JavaScript. In 2009 22nd IEEE Computer Security Foundations Symposium, pages 77-91, 2009. URL: http://dx.doi.org/10.1109/CSF.2009.11.
  29. Sergio Maffeis, John C. Mitchell, and Ankur Taly. An Operational Semantics for JavaScript. In Proceedings of the 6th Asian Symposium on Programming Languages and Systems, APLAS '08, pages 307-325, 2008. URL: http://dx.doi.org/10.1007/978-3-540-89330-1_22.
  30. 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, 2005. URL: http://dx.doi.org/10.1145/1044834.1044835.
  31. Erdal Mutlu, Serdar Tasiran, and Benjamin Livshits. Detecting JavaScript Races That Matter. In Proceedings of the 2015 10th Joint Meeting on Foundations of Software Engineering, ESEC/FSE 2015, pages 381-392, 2015. URL: http://dx.doi.org/10.1145/2786805.2786820.
  32. Node.js. The Node.js Event Loop, Timers, and process.nextTick(). https://nodejs.org/en/docs/guides/event-loop-timers-and-nexttick/, 2018. [Online; accessed 04-June-2018].
  33. C. Park, S. Won, J. Jin, and S. Ryu. Static Analysis of JavaScript Web Applications in the Wild via Practical DOM Modeling (T). In 2015 30th IEEE/ACM International Conference on Automated Software Engineering (ASE), pages 552-562, 2015. URL: http://dx.doi.org/10.1109/ASE.2015.27.
  34. Boris Petrov, Martin Vechev, Manu Sridharan, and Julian Dolby. Race Detection for Web Applications. In Proceedings of the 33rd ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI '12, pages 251-262, 2012. URL: http://dx.doi.org/10.1145/2254064.2254095.
  35. J. C. Reynolds. Separation logic: a logic for shared mutable data structures. In Proceedings 17th Annual IEEE Symposium on Logic in Computer Science, pages 55-74, 2002. URL: http://dx.doi.org/10.1109/LICS.2002.1029817.
  36. Gregor Richards, Sylvain Lebresne, Brian Burg, and Jan Vitek. An Analysis of the Dynamic Behavior of JavaScript Programs. In Proceedings of the 31st ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI '10, pages 1-12, 2010. URL: http://dx.doi.org/10.1145/1806596.1806598.
  37. Cristian-Alexandru Staicu, Michael Pradel, and Benjamin Livshits. SYNODE: understanding and automatically preventing injection attacks on Node.Js. In 25th Annual Network and Distributed System Security Symposium, NDSS 2018, San Diego, California, USA, February 18-21, 2018, 2018. Google Scholar
  38. Kwangwon Sun and Sukyoung Ryu. Analysis of JavaScript Programs: Challenges and Research Trends. ACM Comput. Surv., 50(4):59:1-59:34, 2017. URL: http://dx.doi.org/10.1145/3106741.
  39. J. Wang, W. Dou, Y. Gao, C. Gao, F. Qin, K. Yin, and J. Wei. A comprehensive study on real world concurrency bugs in Node.js. In 2017 32nd IEEE/ACM International Conference on Automated Software Engineering (ASE), pages 520-531, 2017. URL: http://dx.doi.org/10.1109/ASE.2017.8115663.
  40. Yunhui Zheng, Tao Bao, and Xiangyu Zhang. Statically Locating Web Application Bugs Caused by Asynchronous Calls. In Proceedings of the 20th International Conference on World Wide Web, WWW '11, pages 805-814, 2011. URL: http://dx.doi.org/10.1145/1963405.1963517.
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