Document Open Access Logo

Value Partitioning: A Lightweight Approach to Relational Static Analysis for JavaScript

Authors Benjamin Barslev Nielsen, Anders Møller

PDF
Thumbnail PDF

File

LIPIcs.ECOOP.2020.16.pdf
  • Filesize: 0.65 MB
  • 28 pages

Document Identifiers

Author Details

Benjamin Barslev Nielsen
  • Aarhus University, Denmark
Anders Møller
  • Aarhus University, Denmark

Funding

This work was supported by the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation program (grant agreement No 647544).

Cite AsGet BibTex

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 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 166, pp. 16:1-16:28, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.ECOOP.2020.16

Abstract

In static analysis of modern JavaScript libraries, relational analysis at key locations is critical to provide sound and useful results. Prior work addresses this challenge by the use of various forms of trace partitioning and syntactic patterns, which is fragile and does not scale well, or by incorporating complex backwards analysis. In this paper, we propose a new lightweight variant of trace partitioning named value partitioning that refines individual abstract values instead of entire abstract states. We describe how this approach can effectively capture important relational properties involving dynamic property accesses, functions with free variables, and predicate functions. Furthermore, we extend an existing JavaScript analyzer with value partitioning and demonstrate experimentally that it is a simple, precise, and efficient alternative to the existing approaches for analyzing widely used JavaScript libraries.

Subject Classification

ACM Subject Classification
  • Theory of computation → Program analysis
Keywords
  • JavaScript
  • dataflow analysis
  • abstract interpretation

Metrics

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

References

  1. Roberto Amadini, Alexander Jordan, Graeme Gange, François Gauthier, Peter Schachte, Harald Søndergaard, Peter J. Stuckey, and Chenyi Zhang. Combining string abstract domains for JavaScript analysis: An evaluation. In Tools and Algorithms for the Construction and Analysis of Systems - 23rd International Conference, TACAS 2017, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2017, Uppsala, Sweden, April 22-29, 2017, Proceedings, Part I, volume 10205 of Lecture Notes in Computer Science, pages 41-57, 2017. Google Scholar
  2. Esben Andreasen and Anders Møller. Determinacy in static analysis for jQuery. In Proc. ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications, pages 17-31, 2014. Google Scholar
  3. Esben Sparre Andreasen, Anders Møller, and Benjamin Barslev Nielsen. Systematic approaches for increasing soundness and precision of static analyzers. In Proceedings of the 6th ACM SIGPLAN International Workshop on State Of the Art in Program Analysis, SOAP@PLDI 2017, Barcelona, Spain, June 18, 2017, pages 31-36, 2017. URL: https://doi.org/10.1145/3088515.3088521.
  4. Bruno Blanchet, Patrick Cousot, Radhia Cousot, Jérôme Feret, Laurent Mauborgne, Antoine Miné, David Monniaux, and Xavier Rival. A static analyzer for large safety-critical software. In Proceedings of the ACM SIGPLAN 2003 Conference on Programming Language Design and Implementation 2003, San Diego, California, USA, June 9-11, 2003, pages 196-207. ACM, 2003. Google Scholar
  5. Cristiano Calcagno, Dino Distefano, Peter W. O'Hearn, and Hongseok Yang. Compositional shape analysis by means of bi-abduction. J. ACM, 58(6):26:1-26:66, 2011. Google Scholar
  6. David R. Chase, Mark N. Wegman, and F. Kenneth Zadeck. Analysis of pointers and structures. In Proceedings of the ACM SIGPLAN'90 Conference on Programming Language Design and Implementation (PLDI), White Plains, New York, USA, June 20-22, 1990, pages 296-310. ACM, 1990. Google Scholar
  7. 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, New York, NY, USA, 1977. ACM. Google Scholar
  8. Patrick Cousot and Radhia Cousot. Modular static program analysis. In Compiler Construction, 11th International Conference, CC 2002, Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2002, Grenoble, France, April 8-12, 2002, Proceedings, volume 2304 of Lecture Notes in Computer Science, pages 159-178. Springer, 2002. Google Scholar
  9. Arlen Cox, Bor-Yuh Evan Chang, and Xavier Rival. Automatic analysis of open objects in dynamic language programs. In Static Analysis - 21st International Symposium, SAS 2014, Munich, Germany, September 11-13, 2014. Proceedings, pages 134-150, 2014. URL: https://doi.org/10.1007/978-3-319-10936-7_9.
  10. Arjun Guha, Claudiu Saftoiu, and Shriram Krishnamurthi. Typing local control and state using flow analysis. In Programming Languages and Systems - 20th European Symposium on Programming, ESOP 2011, Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2011, Saarbrücken, Germany, March 26-April 3, 2011. Proceedings, volume 6602 of Lecture Notes in Computer Science, pages 256-275. Springer, 2011. Google Scholar
  11. Simon Holm Jensen, Anders Møller, and Peter Thiemann. Type analysis for JavaScript. In Proc. 16th International Static Analysis Symposium, pages 238-255, 2009. Google Scholar
  12. John B. Kam and Jeffrey D. Ullman. Monotone data flow analysis frameworks. Acta Inf., 7(3):305-317, September 1977. Google Scholar
  13. 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 Proc. 22nd ACM SIGSOFT International Symposium on Foundations of Software Engineering, pages 121-132, 2014. Google Scholar
  14. Vineeth Kashyap, John Sarracino, John Wagner, Ben Wiedermann, and Ben Hardekopf. Type refinement for static analysis of JavaScript. In DLS'13, Proceedings of the 9th Symposium on Dynamic Languages, part of SPLASH 2013, Indianapolis, IN, USA, October 26-31, 2013, pages 17-26. ACM, 2013. Google Scholar
  15. Gary A. Kildall. A unified approach to global program optimization. In Conference Record of the ACM Symposium on Principles of Programming Languages, Boston, Massachusetts, USA, October 1973, pages 194-206. ACM Press, 1973. Google Scholar
  16. Yoonseok Ko, Xavier Rival, and Sukyoung Ryu. Weakly sensitive analysis for JavaScript object-manipulating programs. Softw., Pract. Exper., 49(5):840-884, 2019. Google Scholar
  17. Hongki Lee, Sooncheol Won, Joonho Jin, Junhee Cho, and Sukyoung Ryu. SAFE: formal specification and implementation of a scalable analysis framework for ECMAScript. In Proc. International Workshop on Foundations of Object Oriented Languages, 2012. Google Scholar
  18. Magnus Madsen and Esben Andreasen. String analysis for dynamic field access. In Proc. 23rd International Conference on Compiler Construction, volume 8409 of Lecture Notes in Computer Science. Springer, 2014. Google Scholar
  19. Antoine Miné. The octagon abstract domain. Higher-Order and Symbolic Computation, 19(1):31-100, 2006. Google Scholar
  20. Erik M. Nystrom, Hong-Seok Kim, and Wen-mei W. Hwu. Importance of heap specialization in pointer analysis. In Proceedings of the 2004 ACM SIGPLAN-SIGSOFT Workshop on Program Analysis For Software Tools and Engineering, PASTE'04, Washington, DC, USA, June 7-8, 2004, pages 43-48. ACM, 2004. Google Scholar
  21. Changhee Park, Hyeonseung Im, and Sukyoung Ryu. Precise and scalable static analysis of jquery using a regular expression domain. In Proceedings of the 12th Symposium on Dynamic Languages, DLS 2016, pages 25-36, New York, NY, USA, 2016. ACM. Google Scholar
  22. Changhee Park and Sukyoung Ryu. Scalable and precise static analysis of JavaScript applications via loop-sensitivity. In Proc. 29th European Conference on Object-Oriented Programming, pages 735-756, 2015. Google Scholar
  23. Xavier Rival and Laurent Mauborgne. The trace partitioning abstract domain. ACM Trans. Program. Lang. Syst., 29(5), August 2007. Google Scholar
  24. Max Schäfer, Manu Sridharan, Julian Dolby, and Frank Tip. Dynamic determinacy analysis. In ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI '13, Seattle, WA, USA, June 16-19, 2013, pages 165-174. ACM, 2013. Google Scholar
  25. Manu Sridharan, Julian Dolby, Satish Chandra, Max Schäfer, and Frank Tip. Correlation tracking for points-to analysis of JavaScript. In Proc. 26th European Conference on Object-Oriented Programming, 2012. Google Scholar
  26. Benno Stein, Benjamin Barslev Nielsen, Bor-Yuh Evan Chang, and Anders Møller. Static analysis with demand-driven value refinement. Proceedings of the ACM on Programming Languages (PACMPL), 3:140:1-140:29, 2019. Google Scholar
  27. Mark N. Wegman and F. Kenneth Zadeck. Constant propagation with conditional branches. ACM Trans. Program. Lang. Syst., 13(2):181-210, 1991. Google Scholar
  28. 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 2016, Seattle, WA, USA, November 13-18, 2016, pages 487-498. ACM, 2016. 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