Document Open Access Logo

Automatic Root Cause Quantification for Missing Edges in JavaScript Call Graphs

Authors Madhurima Chakraborty, Renzo Olivares, Manu Sridharan, Behnaz Hassanshahi

PDF
Thumbnail PDF

File

LIPIcs.ECOOP.2022.3.pdf
  • Filesize: 1.36 MB
  • 28 pages

Document Identifiers

Author Details

Madhurima Chakraborty
  • University of California, Riverside, CA, USA
Renzo Olivares
  • University of California, Riverside, CA, USA
Manu Sridharan
  • University of California, Riverside, CA, USA
Behnaz Hassanshahi
  • Oracle Labs, Brisbane, Australia

Funding

This research was supported in part by a gift from Oracle Labs and by the National Science Foundation under grant CCF-2007024. This research was partially sponsored by the OUSD(R&E)/RT&L and was accomplished under Cooperative Agreement Number W911NF-20-2-0267. The views and conclusions contained in this document are those of the authors and should not be interpreted as representing the official policies, either expressed or implied, of the ARL and OUSD(R&E)/RT&L or the U.S. Government. The U.S. Government is authorized to reproduce and distribute reprints for Government purposes notwithstanding any copyright notation herein.

Cite AsGet BibTex

Madhurima Chakraborty, Renzo Olivares, Manu Sridharan, and Behnaz Hassanshahi. Automatic Root Cause Quantification for Missing Edges in JavaScript Call Graphs. In 36th European Conference on Object-Oriented Programming (ECOOP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 222, pp. 3:1-3:28, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.ECOOP.2022.3

Abstract

Building sound and precise static call graphs for real-world JavaScript applications poses an enormous challenge, due to many hard-to-analyze language features. Further, the relative importance of these features may vary depending on the call graph algorithm being used and the class of applications being analyzed. In this paper, we present a technique to automatically quantify the relative importance of different root causes of call graph unsoundness for a set of target applications. The technique works by identifying the dynamic function data flows relevant to each call edge missed by the static analysis, correctly handling cases with multiple root causes and inter-dependent calls. We apply our approach to perform a detailed study of the recall of a state-of-the-art call graph construction technique on a set of framework-based web applications. The study yielded a number of useful insights. We found that while dynamic property accesses were the most common root cause of missed edges across the benchmarks, other root causes varied in importance depending on the benchmark, potentially useful information for an analysis designer. Further, with our approach, we could quickly identify and fix a recall issue in the call graph builder we studied, and also quickly assess whether a recent analysis technique for Node.js-based applications would be helpful for browser-based code. All of our code and data is publicly available, and many components of our technique can be re-used to facilitate future studies.

Subject Classification

ACM Subject Classification
  • Theory of computation → Program analysis
Keywords
  • JavaScript
  • call graph construction
  • static program analysis

Metrics

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

Related Versions

Supplementary Materials

References

  1. MDN Web Docs: Object.getOwnPropertyDescriptor(). https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Object/getOwnPropertyDescriptor, 2021. Accessed: 2021-01-11.
  2. MDN Web Docs: with. https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Statements/with, 2021. Accessed: 2021-01-11.
  3. OWASP Juice Shop. https://owasp.org/www-project-juice-shop/, 2021. Accessed: 2021-12-01.
  4. React - a JavaScript library for building user interfaces. https://reactjs.org, 2021. Accessed: 2021-01-11.
  5. Rhino: JavaScript in Java. https://github.com/mozilla/rhino, 2021. Accessed: 2021-01-11.
  6. Angular. https://angular.io, 2022. Accessed: 2022-05-13.
  7. CodeQL for research. https://securitylab.github.com/tools/codeql/, 2022. Accessed: 2022-05-13.
  8. CodeQL library for JavaScript: Call graph. https://codeql.github.com/docs/codeql-language-guides/codeql-library-for-javascript/#call-graph, 2022. Accessed: 2022-05-13.
  9. ESLint. https://eslint.org, 2022. Accessed: 2022-02-25.
  10. jquery. https://jquery.com/, 2022. Accessed: 2022-05-13.
  11. Lodash. https://lodash.com/, 2022. Accessed: 2022-05-13.
  12. MDN Web Docs: Defining Getters and Setters. https://developer.mozilla.org/en-US/docs/Web/JavaScript/Guide/Working_with_Objects#defining_getters_and_setters, 2022. Accessed: 2022-05-13.
  13. MDN Web Docs: Function. https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Function, 2022. Accessed: 2022-05-13.
  14. MDN Web Docs: Object.defineProperty(). https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Object/defineProperty, 2022. Accessed: 2022-05-13.
  15. Puppeteer. https://pptr.dev/, 2022. Accessed: 2022-05-13.
  16. Tern: Intelligent JavaScript Tooling. https://ternjs.net, 2022. Accessed: 2022-02-25.
  17. TodoMVC. https://todomvc.com/, 2022. Accessed: 2022-05-13.
  18. Glenn Ammons, Thomas Ball, and James R. Larus. Exploiting hardware performance counters with flow and context sensitive profiling. In PLDI, pages 85-96, 1997. Google Scholar
  19. Esben Andreasen and Anders Møller. Determinacy in static analysis for jQuery. In Proceedings of the 2014 ACM International Conference on Object Oriented Programming Systems Languages & Applications, part of SPLASH, OOPSLA, pages 17-31, 2014. Google Scholar
  20. Esben Sparre Andreasen, Anders Møller, and Benjamin Barslev Nielsen. Systematic approaches for increasing soundness and precision of static analyzers. In Proceedings of the International Workshop on State Of the Art in Program Analysis, SOAP, pages 31-36, 2017. Google Scholar
  21. Madhurima Chakraborty, Renzo Olivares, Manu Sridharan, and Behnaz Hassanshahi. Artifact for "Automatic Root Cause Quantification for Missing Edges in JavaScript Call Graphs", May 2022. URL: https://doi.org/10.5281/zenodo.6541325.
  22. Madhurima Chakraborty, Renzo Olivares, Manu Sridharan, and Behnaz Hassanshahi. Automatic Root Cause Quantification for Missing Edges in JavaScript Call Graphs (Extended Version). arXiv, 2022. URL: http://arxiv.org/abs/2205.06780.
  23. Satish Chandra, Colin S. Gordon, Jean-Baptiste Jeannin, Cole Schlesinger, Manu Sridharan, Frank Tip, and Young-Il Choi. Type inference for static compilation of JavaScript. In Object-Oriented Programming, Systems, Languages and Applications (OOPSLA), 2016. Google Scholar
  24. Patrick Cousot and Radhia Cousot. Abstract interpretation: A unified lattice model for static analysis of programs by construction or approximation of fixpoints. In Conference Record of the Fourth ACM Symposium on Principles of Programming Languages, POPL, pages 238-252, 1977. Google Scholar
  25. Asger Feldthaus, Max Schäfer, Manu Sridharan, Julian Dolby, and Frank Tip. Efficient construction of approximate call graphs for JavaScript IDE services. In International Conference on Software Engineering, ICSE, pages 752-761, 2013. Google Scholar
  26. Salvatore Guarnieri, Marco Pistoia, Omer Tripp, Julian Dolby, Stephen Teilhet, and Ryan Berg. Saving the world wide web from vulnerable JavaScript. In Proceedings of the 20th International Symposium on Software Testing and Analysis (ISSTA), pages 177-187, 2011. Google Scholar
  27. Behnaz Hassanshahi, Hyunjun Lee, and Paddy Krishnan. Gelato: Feedback-driven and guided security analysis of client-side web applications. In 29th edition of the IEEE International Conference on Software Analysis, Evolution and Reengineering (SANER), 2022. Google Scholar
  28. Nevin Heintze and Olivier Tardieu. Ultra-fast aliasing analysis using CLA: A million lines of C code in a second. In Proceedings of the Conference on Programming Language Design and Implementation, PLDI, pages 254-263, 2001. Google Scholar
  29. Zoltán Herczeg and Gábor Lóki. Evaluation and comparison of dynamic call graph generators for JavaScript. In Ernesto Damiani, George Spanoudakis, and Leszek A. Maciaszek, editors, Proceedings of the 14th International Conference on Evaluation of Novel Approaches to Software Engineering, ENASE 2019, pages 472-479, 2019. Google Scholar
  30. Simon Holm Jensen, Peter A. Jonsson, and Anders Møller. Remedying the eval that men do. In International Symposium on Software Testing and Analysis, ISSTA, pages 34-44, 2012. Google Scholar
  31. 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 ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering, ESEC/FSE, pages 59-69, 2011. Google Scholar
  32. Simon Holm Jensen, Anders Møller, and Peter Thiemann. Type analysis for JavaScript. In Static Analysis, 16th International Symposium, SAS, pages 238-255, 2009. Google Scholar
  33. 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 International Symposium on Foundations of Software Engineering, FSE, pages 121-132, 2014. Google Scholar
  34. Yoonseok Ko, Xavier Rival, and Sukyoung Ryu. Weakly sensitive analysis for JavaScript object-manipulating programs. Softw. Pract. Exp., 49(5):840-884, 2019. Google Scholar
  35. Hongki Lee, Changhee Park, and Sukyoung Ryu. Automatically tracing imprecision causes in JavaScript static analysis. Art Sci. Eng. Program., 4(2), 2020. Google Scholar
  36. Hongki Lee, Sooncheol Won, Joonho Jin, Junhee Cho, and Sukyoung Ryu. Safe: Formal specification and implementation of a scalable analysis framework for ecmascript. In In Proceedings of the International Workshop on Foundations of Object Oriented Languages, FOOL, 2012. Google Scholar
  37. Ondrej Lhoták. Comparing call graphs. In Proceedings of the 7th ACM SIGPLAN-SIGSOFT Workshop on Program Analysis for Software Tools and Engineering, PASTE, pages 37-42, 2007. Google Scholar
  38. Magnus Madsen, Benjamin Livshits, and Michael Fanning. Practical static analysis of JavaScript applications in the presence of frameworks and libraries. In Proceedings of the ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering, ESEC/FSE, pages 499-509, 2013. Google Scholar
  39. Magnus Madsen, Frank Tip, and Ondřej Lhoták. Static analysis of event-driven Node.js JavaScript applications. ACM SIGPLAN Notices, 50(10):505-519, 2015. Google Scholar
  40. Anders Møller, Benjamin Barslev Nielsen, and Martin Toldam Torp. Detecting locations in JavaScript programs affected by breaking library changes. Proc. ACM Program. Lang., 4(OOPSLA):187:1-187:25, 2020. URL: https://doi.org/10.1145/3428255.
  41. Nico Naus and Peter Thiemann. Dynamic flow analysis for JavaScript. In Trends in Functional Programming - 17th International Conference, TFP, pages 75-93, 2016. Google Scholar
  42. Benjamin Barslev Nielsen, Behnaz Hassanshahi, and François Gauthier. Nodest: feedback-driven static analysis of Node.js applications. In Proceedings of the ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering, ESEC/FSE, pages 455-465, 2019. Google Scholar
  43. Benjamin Barslev Nielsen and Anders Møller. Value partitioning: A lightweight approach to relational static analysis for JavaScript. In 34th European Conference on Object-Oriented Programming, ECOOP, pages 16:1-16:28, 2020. Google Scholar
  44. Benjamin Barslev Nielsen, Martin Toldam Torp, and Anders Møller. Modular call graph construction for security scanning of Node.js applications. In Cristian Cadar and Xiangyu Zhang, editors, ISSTA '21: 30th ACM SIGSOFT International Symposium on Software Testing and Analysis, Virtual Event, Denmark, July 11-17, 2021, pages 29-41, 2021. URL: https://doi.org/10.1145/3460319.3464836.
  45. Niels Groot Obbink, Ivano Malavolta, Gian Luca Scoccia, and Patricia Lago. An extensible approach for taming the challenges of JavaScript dead code elimination. In 25th International Conference on Software Analysis, Evolution and Reengineering, SANER, pages 391-401, 2018. Google Scholar
  46. Changhee Park, Hongki Lee, and Sukyoung Ryu. All about the with statement in JavaScript: removing with statements in JavaScript applications. In Proceedings of the 9th Symposium on Dynamic Languages, part of SPLASH, DLS, pages 73-84, 2013. Google Scholar
  47. Changhee Park, Hongki Lee, and Sukyoung Ryu. Static analysis of JavaScript libraries in a scalable and precise way using loop sensitivity. Softw. Pract. Exp., 48(4):911-944, 2018. Google Scholar
  48. 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 Object-Oriented Programming - 25th European Conference, ECOOP, pages 52-78, 2011. Google Scholar
  49. Gregor Richards, Sylvain Lebresne, Brian Burg, and Jan Vitek. An analysis of the dynamic behavior of JavaScript programs. In Proceedings of the Conference on Programming Language Design and Implementation, PLDI, pages 1-12, 2010. Google Scholar
  50. Sukyoung Ryu, Jihyeok Park, and Joonyoung Park. Toward analysis and bug finding in JavaScript web applications in the wild. IEEE Softw., 36(3):74-82, 2019. Google Scholar
  51. Vitalis Salis, Thodoris Sotiropoulos, Panos Louridas, Diomidis Spinellis, and Dimitris Mitropoulos. PyCG: Practical Call Graph Generation in Python. In Proceedings of the 43rd International Conference on Software Engineering (ICSE), 2021. Google Scholar
  52. Max Schäfer, Manu Sridharan, Julian Dolby, and Frank Tip. Dynamic determinacy analysis. In Proceedings of the Conference on Programming Language Design and Implementation, PLDI, pages 165-174, 2013. Google Scholar
  53. Koushik Sen, Swaroop Kalasapur, Tasneem G. Brutch, and Simon Gibbs. Jalangi: a selective record-replay and dynamic analysis framework for JavaScript. In Proceedings of the 2013 9th Joint Meeting on Foundations of Software Engineering, ESEC/FSE, pages 488-498. ACM, 2013. Google Scholar
  54. Manu Sridharan, Satish Chandra, Julian Dolby, Stephen J. Fink, and Eran Yahav. Alias analysis for object-oriented programs. In David Clarke, Tobias Wrigstad, and James Noble, editors, Aliasing in Object-Oriented Programming. Springer, 2013. URL: https://doi.org/10.1007/978-3-642-36946-9_8.
  55. Manu Sridharan, Julian Dolby, Satish Chandra, Max Schäfer, and Frank Tip. Correlation tracking for points-to analysis of JavaScript. In Object-Oriented Programming - 26th European Conference, ECOOP, pages 435-458, 2012. Google Scholar
  56. Stack Overflow 2020 Developer Survey: Web Frameworks. https://insights.stackoverflow.com/survey/2020#technology-web-frameworks, 2020. Accessed: 2022-05-13.
  57. Li Sui, Jens Dietrich, Amjed Tahir, and George Fourtounis. On the recall of static call graph construction in practice. In International Conference on Software Engineering, ICSE, pages 1049-1060, 2020. Google Scholar
  58. T.J. Watson Libraries for Analysis (WALA). URL: http://wala.sourceforge.net.
  59. Shiyi Wei and Barbara G. Ryder. A practical blended analysis for dynamic features in JavaScript. Technical Report TR-12-18, Virginia Tech, 2012. URL: https://vtechworks.lib.vt.edu/handle/10919/19421.
  60. Shiyi Wei, Omer Tripp, Barbara G. Ryder, and Julian Dolby. Revamping JavaScript static analysis via localization and remediation of root causes of imprecision. In Proceedings of the 24th ACM SIGSOFT International Symposium on Foundations of Software Engineering, FSE, pages 487-498, 2016. Google Scholar
  61. Andreas Zeller and Ralf Hildebrandt. Simplifying and isolating failure-inducing input. IEEE Trans. Software Eng., 28(2):183-200, 2002. 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-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact