Document Open Access Logo

Deep Static Modeling of invokedynamic

Authors George Fourtounis, Yannis Smaragdakis

PDF
Thumbnail PDF

File

LIPIcs.ECOOP.2019.15.pdf
  • Filesize: 0.63 MB
  • 28 pages

Document Identifiers

Author Details

George Fourtounis
  • University of Athens, Department of Informatics and Telecommunications, Greece
Yannis Smaragdakis
  • University of Athens, Department of Informatics and Telecommunications, Greece

Funding

We gratefully acknowledge funding by the European Research Council, grants 307334 (SPADE) and 790340 (PARSE), a Facebook Research and Academic Relations award, and an Oracle Labs collaborative research grant.

Cite AsGet BibTex

George Fourtounis and Yannis Smaragdakis. Deep Static Modeling of invokedynamic. In 33rd European Conference on Object-Oriented Programming (ECOOP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 134, pp. 15:1-15:28, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.ECOOP.2019.15

Abstract

Java 7 introduced programmable dynamic linking in the form of the invokedynamic framework. Static analysis of code containing programmable dynamic linking has often been cited as a significant source of unsoundness in the analysis of Java programs. For example, Java lambdas, introduced in Java 8, are a very popular feature, which is, however, resistant to static analysis, since it mixes invokedynamic with dynamic code generation. These techniques invalidate static analysis assumptions: programmable linking breaks reasoning about method resolution while dynamically generated code is, by definition, not available statically. In this paper, we show that a static analysis can predictively model uses of invokedynamic while also cooperating with extra rules to handle the runtime code generation of lambdas. Our approach plugs into an existing static analysis and helps eliminate all unsoundness in the handling of lambdas (including associated features such as method references) and generic invokedynamic uses. We evaluate our technique on a benchmark suite of our own and on third-party benchmarks, uncovering all code previously unreachable due to unsoundness, highly efficiently.

Subject Classification

ACM Subject Classification
  • Software and its engineering → Compilers
  • Theory of computation → Program analysis
  • Software and its engineering → General programming languages
Keywords
  • static analysis
  • invokedynamic

Metrics

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

Supplementary Materials

References

  1. Eric Allen, David Chase, Joe Hallett, Victor Luchangco, Jan-Willem Maessen, Sukyoung Ryu, Guy L Steele Jr, Sam Tobin-Hochstadt, Joao Dias, Carl Eastlund, et al. The Fortress language specification. Sun Microsystems, 139:140, 2005. Google Scholar
  2. Malte Appeltauer, Michael Haupt, and Robert Hirschfeld. Layered Method Dispatch with INVOKEDYNAMIC: An Implementation Study. In Proceedings of the 2nd International Workshop on Context-Oriented Programming, COP '10, pages 4:1-4:6, New York, NY, USA, 2010. ACM. URL: http://dx.doi.org/10.1145/1930021.1930025.
  3. Shashank Bharadwaj. Optimizing Jython using invokedynamic and Gradual Typing. Master’s thesis, University of Colorado at Boulder, 2012. Google Scholar
  4. Eric Bodden. Develop transformer that gets rid of indy calls for lambda capture #226, 2014. URL: https://github.com/Sable/soot/issues/226.
  5. Norris Boyd et al. Rhino: Javascript for Java. Mozilla Foundation, 2007. Google Scholar
  6. Martin Bravenboer and Yannis Smaragdakis. Strictly Declarative Specification of Sophisticated Points-to Analyses. In Proceedings of the 24th Annual ACM SIGPLAN Conference on Object Oriented Programming, Systems, Languages, and Applications, OOPSLA '09, New York, NY, USA, 2009. ACM. Google Scholar
  7. Cristina Cifuentes, Andrew Gross, and Nathan Keynes. Understanding Caller-sensitive Method Vulnerabilities: A Class of Access Control Vulnerabilities in the Java Platform. In Proceedings of the 4th ACM SIGPLAN International Workshop on State Of the Art in Program Analysis, SOAP 2015, pages 7-12, New York, NY, USA, 2015. ACM. URL: http://dx.doi.org/10.1145/2771284.2771286.
  8. L. Peter Deutsch and Allan M. Schiffman. Efficient Implementation of the Smalltalk-80 System. In Proceedings of the 11th ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages, POPL '84, pages 297-302, New York, NY, USA, 1984. ACM. URL: http://dx.doi.org/10.1145/800017.800542.
  9. Jens Dietrich, Henrik Schole, Li Sui, and Ewan D. Tempero. XCorpus - an executable corpus of Java programs. Journal of Object Technology, 16(4):1:1-24, 2017. URL: http://dx.doi.org/10.5381/jot.2017.16.4.a1.
  10. Julian Dolby, Stephen J. Fink, and Manu Sridharan. T.J. Watson libraries for analysis (WALA). URL: http://wala.sourceforge.net.
  11. Sebastian Erdweg, Vlad Vergu, Mira Mezini, and Eelco Visser. Finding Bugs in Program Generators by Dynamic Analysis of Syntactic Language Constraints. In Proceedings of the Companion Publication of the 13th International Conference on Modularity, MODULARITY '14, pages 17-20, New York, NY, USA, 2014. ACM. URL: http://dx.doi.org/10.1145/2584469.2584474.
  12. Rémi Forax. JSR 292 / PHP.reboot. https://www.lrde.epita.fr/dload/seminar/2010-12-08/forax.pdf, 2010.
  13. George Fourtounis, George Kastrinis, and Yannis Smaragdakis. Static Analysis of Java Dynamic Proxies. In Proceedings of the 27th ACM SIGSOFT International Symposium on Software Testing and Analysis, ISSTA 2018, pages 209-220, New York, NY, USA, 2018. ACM. URL: http://dx.doi.org/10.1145/3213846.3213864.
  14. Brian Goetz. One VM, Many Languages. https://gotocon.com/dl/jaoo-aarhus-2010/slides/BrianGoetz_OneVMManyLanguages.pdf, 2010. GOTO Aarhus 2010 Conference.
  15. Brian Goetz. From lambdas to bytecode. http://wiki.jvmlangsummit.com/images/1/1e/2011_Goetz_Lambda.pdf, 2011. JVM Language Summit.
  16. Brian Goetz. Implementing lambda expressions in Java. http://wiki.jvmlangsummit.com/images/7/7b/Goetz-jvmls-lambda.pdf, 2012. JVM Language Summit.
  17. Brian Goetz. Lambda: A peek under the hood. https://www.slideshare.net/jaxlondon2012/lambda-a-peek-under-the-hood-brian-goetz, 2012. JAX London 2012.
  18. Brian Goetz. Translation of Lambda Expressions, April 2012. Accessed: June 11, 2019. URL: http://cr.openjdk.java.net/~briangoetz/lambda/lambda-translation.html.
  19. Brian Goetz. State of the Lambda, September 2013. Accessed: June 11, 2019. URL: http://cr.openjdk.java.net/~briangoetz/lambda/lambda-state-final.html.
  20. Brian Goetz. Project Valhalla Update. https://www.oracle.com/technetwork/java/jvmls2016-goetz-3126134.pdf, 2016. JVM Language Summit.
  21. Brian Goetz. JEP 303: Intrinsics for the LDC and INVOKEDYNAMIC Instructions, 2018. URL: https://openjdk.java.net/jeps/303.
  22. Brian Gorenc and Jasiel Spelman. Java Every-Days - Exploiting Software Running on 3 Billion Devices. https://media.blackhat.com/us-13/US-13-Gorenc-Java-Every-Days-Exploiting-Software-Running-on-3-Billion-Devices-WP.pdf. HP Security Research Zero Day Initiative.
  23. James Gosling, Bill Joy, Guy Steele, Gilad Bracha, and Alex Buckley. The Java Language Specification, Java SE 8 Edition (Java Series), 2014. Google Scholar
  24. Stuart Halloway. Programming Clojure. Pragmatic Bookshelf, 1st edition, 2009. Google Scholar
  25. Anders Hejlsberg, Scott Wiltamuth, and Peter Golde. C#Language Specification. Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA, 2003. Google Scholar
  26. Philipp Holzinger, Stefan Triller, Alexandre Bartel, and Eric Bodden. An In-Depth Study of More Than Ten Years of Java Exploitation. In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, CCS '16, pages 779-790, New York, NY, USA, 2016. ACM. URL: http://dx.doi.org/10.1145/2976749.2978361.
  27. Vladimir Ivanov. Invokedynamic: Deep Dive. http://cr.openjdk.java.net/~vlivanov/talks/2015-Indy_Deep_Dive.pdf. Accessed: June 11, 2019.
  28. Kamil Jezek and Jens Dietrich. Magic with Dynamo - Flexible Cross-Component Linking for Java with Invokedynamic. In Shriram Krishnamurthi and Benjamin S. Lerner, editors, 30th European Conference on Object-Oriented Programming (ECOOP 2016), volume 56 of Leibniz International Proceedings in Informatics (LIPIcs), pages 12:1-12:25, Dagstuhl, Germany, 2016. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: http://dx.doi.org/10.4230/LIPIcs.ECOOP.2016.12.
  29. Chanwit Kaewkasi. Towards Performance Measurements for the Java Virtual Machine’s Invokedynamic. In Virtual Machines and Intermediate Languages, VMIL '10, pages 3:1-3:6, New York, NY, USA, 2010. ACM. URL: http://dx.doi.org/10.1145/1941054.1941057.
  30. Davy Landman, Alexander Serebrenik, and Jurgen J. Vinju. Challenges for Static Analysis of Java Reflection - Literature Review and Empirical Study. In Proceedings of the 39th International Conference on Software Engineering, ICSE 2017, Buenos Aires, Argentina, May 20-28, 2017, 2017. Google Scholar
  31. Jim Laskey. Adventures in JSR-292 or How To Be A Duck Without Really Trying. http://wiki.jvmlangsummit.com/images/c/ce/Nashorn.pdf, 2011. JVM Language Summit.
  32. Licel. DexProtector. URL: https://dexprotector.com/docs.
  33. Tim Lindholm, Frank Yellin, Gilad Bracha, and Alex Buckley. The Java Virtual Machine Specification, Java SE 8 Edition. Addison-Wesley Professional, 1st edition, 2014. Google Scholar
  34. Baptiste Maingret, Frédéric Le Mouël, Julien Ponge, Nicolas Stouls, Jian Cao, and Yannick Loiseau. Towards a Decoupled Context-Oriented Programming Language for the Internet of Things. In Proceedings of the 7th International Workshop on Context-Oriented Programming, COP'15, pages 7:1-7:6, New York, NY, USA, 2015. ACM. URL: http://dx.doi.org/10.1145/2786545.2786552.
  35. Davood Mazinanian, Ameya Ketkar, Nikolaos Tsantalis, and Danny Dig. Understanding the Use of Lambda Expressions in Java. Proceedings of the ACM on Programming Languages, 1(OOPSLA):85:1-85:31, October 2017. URL: http://dx.doi.org/10.1145/3133909.
  36. Erik Meijer, Brian Beckman, and Gavin Bierman. LINQ: Reconciling object, relations and XML in the .NET framework. In Proceedings of the 2006 ACM SIGMOD International Conference on Management of Data, SIGMOD '06, pages 706-706, New York, NY, USA, 2006. ACM. URL: http://dx.doi.org/10.1145/1142473.1142552.
  37. Microsoft. DynamicMethod Class. URL: https://msdn.microsoft.com/en-us/library/system.reflection.emit.dynamicmethod(v=vs.110).aspx.
  38. Behrooz Nobakht and Frank S. de Boer. Programming with Actors in Java 8. In Tiziana Margaria and Bernhard Steffen, editors, Leveraging Applications of Formal Methods, Verification and Validation. Specialized Techniques and Applications: 6th International Symposium, ISoLA 2014, Imperial, Corfu, Greece, October 8-11, 2014, Proceedings, Part II, pages 37-53. Springer Berlin Heidelberg, Berlin, Heidelberg, 2014. URL: http://dx.doi.org/10.1007/978-3-662-45231-8_4.
  39. S. Nopnipa and C. Kaewkasi. Aspect-aware bytecode combinators for a dynamic AOP system with invokedynamic. In The 2013 10th International Joint Conference on Computer Science and Software Engineering (JCSSE), pages 246-251, May 2013. URL: http://dx.doi.org/10.1109/JCSSE.2013.6567353.
  40. Charles Nutter. A First Taste of InvokeDynamic. URL: http://blog.headius.com/2008/09/first-taste-of-invokedynamic.html.
  41. Charles Nutter. The Power of the JVM. URL: http://blog.headius.com/2008/05/power-of-jvm.html.
  42. Charles Nutter. invokedynamic: You Ain't Seen Nothing Yet, 2012. Proceedings of the JAX Conference (JAX 12). URL: https://www.slideshare.net/CharlesNutter/jax-2012-invoke-dynamic-keynote.
  43. Charles Nutter. GOTO Night with Charles Nutter Slides, 2014. GOTO 2014. URL: https://www.slideshare.net/AlexandraMasterson/goto-night-with-charles-nutter-slides.
  44. Charles O. Nutter, Thomas Enebo, Nick Sieger, Ola Bini, and Ian Dees. Using JRuby: Bringing Ruby to Java. Pragmatic Bookshelf, 1st edition, 2011. Google Scholar
  45. Martin Odersky and Tiark Rompf. Unifying Functional and Object-oriented Programming with Scala. Communications of the ACM, 57(4):76-86, April 2014. URL: http://dx.doi.org/10.1145/2591013.
  46. OpenJDK Compiler Team. Bound method handles - HotSpot - OpenJDK Wiki. URL: https://wiki.openjdk.java.net/display/HotSpot/Bound+method+handles.
  47. Oracle. java.lang.invoke (Java Platform SE 7). URL: https://docs.oracle.com/javase/7/docs/api/java/lang/invoke/package-summary.html.
  48. Oracle. JEP 160: Lambda-form representation for method handles. URL: http://openjdk.java.net/jeps/160.
  49. Oracle. JSR 335: Lambda Expressions for the Javatrademark Programming Language. URL: https://jcp.org/en/jsr/detail?id=335.
  50. Oracle. LambdaMetafactory (Java Platform SE 8). URL: https://docs.oracle.com/javase/8/docs/api/java/lang/invoke/LambdaMetafactory.html.
  51. Oracle. Method References (The Java™ Tutorials > Learning the Java Language > Classes and Objects), 2017. URL: https://docs.oracle.com/javase/tutorial/java/javaOO/methodreferences.html.
  52. Oracle. MethodHandle (Java Platform SE 8), 2018. URL: https://docs.oracle.com/javase/8/docs/api/java/lang/invoke/MethodHandle.html.
  53. Oracle. MethodHandles (Java Platform SE 8), 2018. URL: https://docs.oracle.com/javase/8/docs/api/java/lang/invoke/MethodHandles.html.
  54. Oracle. MethodType (Java Platform SE 8 ), 2018. URL: https://docs.oracle.com/javase/8/docs/api/java/lang/invoke/MethodType.html.
  55. F. Ortin, P. Conde, D. Fernandez-Lanvin, and R. Izquierdo. The Runtime Performance of invokedynamic: An Evaluation with a Java Library. IEEE Software, 31(4):82-90, July 2014. URL: http://dx.doi.org/10.1109/MS.2013.46.
  56. Samuele Pedroni and Noel Rappin. Jython Essentials: Rapid Scripting in Java. O'Reilly & Associates, Inc., Sebastopol, CA, USA, 1 edition, 2002. Google Scholar
  57. Jerome Pilliet, Remi Forax, and Gilles Roussel. DualStack: Improvement of invokedynamic implementation on Android. In Proceedings of the 13th International Workshop on Java Technologies for Real-time and Embedded Systems, JTRES '15, pages 4:1-4:8, New York, NY, USA, 2015. ACM. URL: http://dx.doi.org/10.1145/2822304.2822310.
  58. Julien Ponge, Frédéric Le Mouël, and Nicolas Stouls. Golo, a Dynamic, Light and Efficient Language for Post-invokedynamic JVM. In Proceedings of the 2013 International Conference on Principles and Practices of Programming on the Java Platform: Virtual Machines, Languages, and Tools, PPPJ '13, pages 153-158, New York, NY, USA, 2013. ACM. URL: http://dx.doi.org/10.1145/2500828.2500844.
  59. Julien Ponge and Frédéric Le Mouël. JooFlux: Hijacking Java 7 invokedynamic to support live code modifications. CoRR, abs/1210.1039, 2012. URL: http://arxiv.org/abs/1210.1039.
  60. M. Reif, F. Kübler, M. Eichberg, and M. Mezini. Systematic evaluation of the unsoundness of call graph construction algorithms for Java. In Proceedings of SOAP 2018. ACM, 2018. Google Scholar
  61. John R. Rose. Anonymous classes in the VM, January 2008. URL: https://blogs.oracle.com/jrose/entry/anonymous_classes_in_the_vm.
  62. John R. Rose. Bytecodes Meet Combinators: Invokedynamic on the JVM. In Proceedings of the Third Workshop on Virtual Machines and Intermediate Languages, VMIL '09, pages 2:1-2:11, New York, NY, USA, 2009. ACM. URL: http://dx.doi.org/10.1145/1711506.1711508.
  63. John R. Rose. Method Handles and Beyond... Some basis vectors. http://wiki.jvmlangsummit.com/images/8/88/Rose-2011-FutureDirections.pdf, 2011. JVM Summit.
  64. Gilles Roussel, Remi Forax, and Jerome Pilliet. Android 292: Implementing Invokedynamic in Android. In Proceedings of the 12th International Workshop on Java Technologies for Real-time and Embedded Systems, JTRES '14, pages 76:76-76:86, New York, NY, USA, 2014. ACM. URL: http://dx.doi.org/10.1145/2661020.2661032.
  65. Security Explorations. Security Vulnerabilities in Java SE. http://www.security-explorations.com/materials/se-2012-01-report.pdf. Technical Report.
  66. Yannis Smaragdakis and George Balatsouras. Pointer Analysis. Foundations and Trends in Programming Languages, 2(1):1-69, 2015. URL: http://dx.doi.org/10.1561/2500000014.
  67. Yannis Smaragdakis, George Balatsouras, George Kastrinis, and Martin Bravenboer. More Sound Static Handling of Java Reflection. In Proceedings of the Asian Symposium on Programming Languages and Systems, APLAS '15. Springer, 2015. Google Scholar
  68. L. Sui, J. Dietrich, M. Emery, S. Rasheed, and A. Tahir. On the Soundness of Call Graph Construction in the Presence of Dynamic Language Features - A Benchmark and Tool Evaluation. https://sites.google.com/site/jensdietrich/publications/preprints/On%20the%20Soundness%20of%20Call%20Graph%20Construction%20in%20the%20Presence%20of%20Dynamic%20Language%20Features.pdf?attredirects=0&d=1. Accepted for APLAS'18.
  69. Josef Svenningsson and Emil Axelsson. Combining Deep and Shallow Embedding of Domain-specific Languages. Computer Languages, Systems and Structures, 44(PB):143-165, December 2015. URL: http://dx.doi.org/10.1016/j.cl.2015.07.003.
  70. Attila Szegedi. Dynalink - Dynamic Linker Framework for JVM Languages. http://medianetwork.oracle.com/video/player/1113272541001, July 2011. JVM Language Summit.
  71. The Apache Groovy Project. Invoke dynamic support. URL: http://groovy-lang.org/indy.html.
  72. Trifork. erjang. URL: https://github.com/trifork/erjang/wiki.
  73. TypeLead. The Eta Programming Language. URL: http://eta-lang.org/.
  74. Raoul-Gabriel Urma. Processing Data with Java SE 8 Streams, Part 1. Java Magazine, 2014. URL: http://www.oracle.com/technetwork/articles/java/ma14-java-se-8-streams-2177646.html.
  75. Raja Vallée-Rai, Phong Co, Etienne Gagnon, Laurie Hendren, Patrick Lam, and Vijay Sundaresan. Soot - a Java Bytecode Optimization Framework. In Proceedings of the 1999 Conference of the Centre for Advanced Studies on Collaborative Research, CASCON '99, pages 13-. IBM Press, 1999. URL: http://dl.acm.org/citation.cfm?id=781995.782008.
  76. Ingo Wechsung. The Frege Programming Language (Draft). http://www.frege-lang.org/doc/Language.pdf, 2014.
  77. Thomas Würthinger, Christian Wimmer, Andreas Wöß, Lukas Stadler, Gilles Duboscq, Christian Humer, Gregor Richards, Doug Simon, and Mario Wolczko. One VM to Rule Them All. In Proceedings of the 2013 ACM International Symposium on New Ideas, New Paradigms, and Reflections on Programming & Software, Onward! 2013, pages 187-204, New York, NY, USA, 2013. ACM. URL: http://dx.doi.org/10.1145/2509578.2509581.
  78. Shijie Xu, David Bremner, and Daniel Heidinga. Mining Method Handle Graphs for Efficient Dynamic JVM Languages. In Proceedings of the Principles and Practices of Programming on The Java Platform, PPPJ '15, pages 159-169, New York, NY, USA, 2015. ACM. URL: http://dx.doi.org/10.1145/2807426.2807440.
  79. Shijie Xu, David Bremner, and Daniel Heidinga. MHDeS: Deduplicating method handle graphs for efficient dynamic JVM language implementations. In Proceedings of the 11th Workshop on Implementation, Compilation, Optimization of Object-Oriented Languages, Programs and Systems, ICOOOLPS '16, pages 4:1-4:10, New York, NY, USA, 2016. ACM. URL: http://dx.doi.org/10.1145/3012408.3012412.
  80. Shijie Xu, David Bremner, and Daniel Heidinga. Fusing Method Handle Graphs for Efficient Dynamic JVM Language Implementations. In Proceedings of the 9th ACM SIGPLAN International Workshop on Virtual Machines and Intermediate Languages, VMIL 2017, pages 18-27, New York, NY, USA, 2017. ACM. URL: http://dx.doi.org/10.1145/3141871.3141874.
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