Revamping JavaScript static analysis via localization and remediation of root causes of imprecision

ABSTRACT

Static analysis is challenged by the dynamic language constructs of JavaScript which often lead to unacceptable performance and/or precision results. We describe an approach that focuses on improving the practicality and accuracy of points-to analysis and call graph construction for JavaScript programs. The approach first identifies program constructs which are sources of imprecision (i.e., root causes) through monitoring the static analysis process. We then examine and suggest specific context-sensitive analyses to apply. Our technique is able to to find that the root causes comprise less than 2% of the functions in JavaScript library applications. Moreover, the specialized analysis derived by our approach finishes within a few seconds, even on programs which can not complete within 10 minutes with the original analysis.

References

1. L. O. Andersen. Program Analysis and Specialization for the C Programming Language. PhD thesis, University of Copenhagen, 1994.
2. E. Andreasen and A. Møller. Determinacy in static analysis for jQuery. In Proceedings of the 2014 ACM International Conference on Object Oriented Programming Systems Languages & Applications, OOPSLA ’14, pages 17–31, New York, NY, USA, 2014. ACM.
3. R. Cytron, J. Ferrante, B. K. Rosen, M. N. Wegman, and F. K. Zadeck. Efficiently computing static single assignment form and the control dependence graph. ACM Trans. Program. Lang. Syst., 13(4):451–490, Oct. 1991.
4. A. Feldthaus, M. Schäfer, M. Sridharan, J. Dolby, and F. 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, Piscataway, NJ, USA, 2013. IEEE Press.
5. S. Guarnieri and B. 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, Berkeley, CA, USA, 2009. USENIX Association.
6. S. Guarnieri, M. Pistoia, O. Tripp, J. Dolby, S. Teilhet, and R. Berg. Saving the world wide web from vulnerable JavaScript. In Proceedings of the 2011 International Symposium on Software Testing and Analysis, ISSTA ’11, pages 177–187, New York, NY, USA, 2011. ACM.
7. S. Z. Guyer and C. Lin. Client-driven pointer analysis. In Proceedings of the 10th International Conference on Static Analysis, SAS’03, pages 214–236, 2003.
8. B. Hackett and S.-y. Guo. Fast and precise hybrid type inference for JavaScript. In Proceedings of the 33rd ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI ’12, pages 239–250, New York, NY, USA, 2012. ACM.
9. V. Kashyap, K. Dewey, E. A. Kuefner, J. Wagner, K. Gibbons, J. Sarracino, B. Wiedermann, and B. 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, New York, NY, USA, 2014. ACM.
10. P. Liang, O. Tripp, and M. Naik. Learning minimal abstractions. In Proceedings of the 38th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL ’11, pages 31–42, New York, NY, USA, 2011. ACM.
11. M. Madsen, F. Tip, and O. 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, New York, NY, USA, 2015. ACM.
12. A. Milanova, A. Rountev, and B. G. Ryder. Precise call graphs for c programs with function pointers. Automated Software Engg., 11(1):7–26, Jan. 2004.
13. A. Milanova, A. Rountev, and B. G. Ryder. Parameterized object sensitivity for points-to analysis for Java. ACM Trans. Softw. Eng. Methodol., 14(1):1–41, Jan. 2005.
14. C. Park and S. Ryu. Scalable and precise static analysis of JavaScript applications via loop-sensitivity. In 29th European Conference on Object-Oriented Programming, ECOOP 2015, July 5-10, 2015, Prague, Czech Republic, pages 735–756, 2015.
15. M. Schäfer, M. Sridharan, J. Dolby, and F. Tip. Dynamic determinacy analysis. In Proceedings of the 34th ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI ’13, pages 165–174, New York, NY, USA, 2013. ACM.
16. M. Sharir and A. Pnueli. Two approaches to interprocedural data flow analysis. Program Flow Analysis: Theory and Applications, pages 189–234, 1981.
17. O. G. Shivers. Control-flow Analysis of Higher-order Languages of Taming Lambda. PhD thesis, Carnegie Mellon University, 1991.
18. Y. Smaragdakis, G. Kastrinis, and G. 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.
19. M. Sridharan and R. 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.
20. M. Sridharan, J. Dolby, S. Chandra, M. Schäfer, and F. 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.
21. W 3 Techs. W 3 Techs web technologies surveys: usage of JavaScript libraries for websites. http://w3techs.com/ technologies/overview/javascript library/all, 2016.
22. WALA. T. J. Watson Libraries for Analysis. http: //wala.sourceforge.net/wiki/index.php/Main Page.
23. S. Wei and B. G. Ryder. Adaptive context-sensitive analysis for JavaScript. In 29th European Conference on Object-Oriented Programming, ECOOP 2015, July 5-10, 2015, Prague, Czech Republic, pages 712–734, 2015.

Index Terms

• Software and its engineering

  • Software creation and management

    • Software verification and validation

      • Software defect analysis

        • Software testing and debugging

• Theory of computation

  • Semantics and reasoning

    • Program reasoning

      • Program analysis