Taming reflection: Aiding static analysis in the presence of reflection and custom class loaders

ABSTRACT

Static program analyses and transformations for Java face many problems when analyzing programs that use reflection or custom class loaders: How can a static analysis know which reflective calls the program will execute? How can it get hold of classes that the program loads from remote locations or even generates on the fly? And if the analysis transforms classes, how can these classes be re-inserted into a program that uses custom class loaders?

In this paper, we present TamiFlex, a tool chain that offers a partial but often effective solution to these problems. With TamiFlex, programmers can use existing static-analysis tools to produce results that are sound at least with respect to a set of recorded program runs. TamiFlex inserts runtime checks into the program that warn the user in case the program executes reflective calls that the analysis did not take into account. TamiFlex further allows programmers to re-insert offline-transformed classes into a program.

We evaluate TamiFlex in two scenarios: benchmarking with the DaCapo benchmark suite and analysing large-scale interactive applications. For the latter, TamiFlex significantly improves code coverage of the static analyses, while for the former our approach even appears complete: the inserted runtime checks issue no warning. Hence, for the first time, TamiFlex enables sound static whole-program analyses on DaCapo. During this process, TamiFlex usually incurs less than 10% runtime overhead.

References

1. B. Alpern, C. R. Attanasio, J. J. Barton, M. G. Burke, P. Cheng, J.-D. Choi, A. Cocchi, S. J. Fink, D. Grove, M. Hind, S. F. Hummel, D. Lieber, V. Litvinov, M. F. Mergen, T. Ngo, J. R. Russell, V. Sarkar, M. J. Serrano, J. C. Shepherd, S. E. Smith, V. C. Sreedhar, H. Srinivasan, and J. Whaley. The Jalapeno virtual machine. IBM Systems Journal, 39(1):211--238, 2000.
2. Lars Ole Andersen. Program Analysis and Specialization for the C Programming Language. PhD thesis, University of Copenhagen, 1994. DIKU report 94/19.
3. Shay Artzi, Adam Kiezun, David Glasser, and Michael D. Ernst. Combined static and dynamic mutability analysis. In ASE'07, pages 104--113. ACM, 2007.
4. Al Bessey, Ken Block, Ben Chelf, Andy Chou, Bryan Fulton, Seth Hallem, Charles Henri-Gros, Asya Kamsky, Scott McPeak, and Dawson Engler. A few billion lines of code later: using static analysis to find bugs in the real world. CACM, 53(2):66--75, 2010.
5. S. M. Blackburn, R. Garner, C. Hoffman, A. M. Khan, K. S. McKinley, R. Bentzur, A. Diwan, D. Feinberg, D. Frampton, S. Z. Guyer, M. Hirzel, A. Hosking, M. Jump, H. Lee, J. E. B. Moss, A. Phansalkar, D. Stefanovic, T. VanDrunen, D. von Dincklage, and B. Wiedermann. The DaCapo benchmarks: Java benchmarking development and analysis. In OOPSLA'06, pages 169--190. ACM, 2006.
6. Eric Bodden. Efficient Hybrid Typestate Analysis by Determining Continuation-Equivalent States. In ICSE'10, pages 5--14. ACM, 2010.
7. Eric Bodden, Patrick Lam, and Laurie Hendren. Finding Programming Errors Earlier by Evaluating Runtime Monitors Ahead-of-Time. In FSE'08, pages 36--47, 2008.
8. Eric Bodden, Andreas Sewe, Jan Sinschek, and Mira Mezini. Taming Reflection (Extended version). Technical Report TUD-CS-2010-0066, CASED, March 2010. http://cased.de/.
9. Michael D. Bond and Kathryn S. McKinley. Probabilistic calling context. In OOPSLA'07, pages 97--112. ACM, 2007.
10. Guillaume Brat and Willem Visser. Combining static analysis and model checking for software analysis. In ASE'01, page 262. IEEE, 2001.
11. Mathias Braux and Jacques Noyé. Towards partially evaluating reflection in java. In PEPM'99, pages 2--11. ACM, 1999.
12. Aske Christensen, Anders Møller, and Michael Schwartzbach. Precise analysis of string expressions. In SAS'03, volume 2694 of LNCS, pages 1--18. Springer, 2003.
13. Coverity static-analysis tool. http://coverity.com/.
14. Bruno Dufour, Barbara G. Ryder, and Gary Sevitsky. Blended analysis for performance understanding of framework-based applications. In ISSTA'07, pages 118--128. ACM, 2007.
15. Matthew B. Dwyer and Rahul Purandare. Residual dynamic typestate analysis: Exploiting static analysis results to reformulate and reduce the cost of dynamic analysis. In ASE'07, pages 124--133, 2007.
16. Stephen Fink, Eran Yahav, Nurit Dor, G. Ramalingam, and Emmanual Geay. Effective typestate verification in the presence of aliasing. In ISSTA'06, pages 133--144. ACM, 2006.
17. Michael Furr, Jong-hoon (David) An, and Jeffrey S. Foster. Profile-guided static typing for dynamic scripting languages. In OOPSLA'09, pages 283--300. ACM, 2009.
18. Mary W. Hall and Ken Kennedy. Efficient call graph analysis. ACM Letters on Programming Languages and Systems (LOPLAS), 1(3):227--242, 1992.
19. Martin Hirzel, Daniel Von Dincklage, Amer Diwan, and Michael Hind. Fast online pointer analysis. TOPLAS, 29(2):11, 2007.
20. Martin Hirzel, Amer Diwan, Michael Hind, Martin Hirzel, Amer Diwan, and Michael Hind. Pointer analysis in the presence of dynamic class loading. In ECOOP'04, pages 96--122. Springer, 2004.
21. Java Virtual Machine Tool Interface (JVM TI). Version 6. http://download.oracle.com/javase/6/docs/technotes/guides/jvmti/index.html.
22. Ondřrej Lhoták. Comparing call graphs. In PASTE'07, pages 37--42. ACM, 2007.
23. Ondřrej Lhoták and Laurie Hendren. Scaling Java points-to analysis using Spark. In CC'03, volume 2622 of LNCS, pages 153--169. Springer, 2003.
24. Benjamin Livshits, John Whaley, and Monica S. Lam. Reflection analysis for java. In Kwangkeun Yi, editor, APLAS'05, volume 3780 of LNCS, pages 139--160. Springer, 2005.
25. Gail C. Murphy, David Notkin, William G. Griswold, and Erica S. Lan. An empirical study of static call graph extractors. TOSEM, 7(2):158--191, 1998.
26. Nomair A. Naeem and Ondřrej Lhoták. Extending typestate analysis to multiple interacting objects. Technical report, University of Waterloo, 04 2008. CS-2008-04.
27. National Institute of Standards and Technology, Information Technology Laboratory. Secure Hash Signature Standard (SHS), 2008. FIPS PUB 180--3.
28. Venkatesh Ranganath and John Hatcliff. Slicing concurrent Java programs using Indus and Kaveri. STTT, 9:489--504, 2007.
29. Shmuel Sagiv, Thomas W. Reps, and Reinhard Wilhelm. Solving shape-analysis problems in languages with destructive updating. TOPLAS, 20(1):1--50, 1998.
30. R. E. Strom and S. Yemini. Typestate: A programming language concept for enhancing software reliability. TSE, 12(1):157--171, 1986.
31. Peter F. Sweeney and Frank Tip. Extracting library-based object-oriented applications. In FSE'00, pages 98--107. ACM, 2000.
32. Frank Tip, Peter F. Sweeney, Chris Laffra, Aldo Eisma, and David Streeter. Practical extraction techniques for java. TOPLAS, 24(6):625--666, 2002.
33. Raja Vallée-Rai, Phong Co, Etienne Gagnon, Laurie Hendren, Patrick Lam, and Vijay Sundaresan. Soot - a Java bytecode optimization framework. In CASCON'99, page 13. IBM, 1999.

Index Terms

• Theory of computation

  • Semantics and reasoning

    • Program reasoning

      • Program analysis

    • Program semantics