Enabling static analysis for partial java programs

ABSTRACT

Software engineering tools often deal with the source code of programs retrieved from the web or source code repositories. Typically, these tools only have access to a subset of a program's source code (one file or a subset of files) which makes it difficult to build a complete and typed intermediate representation (IR). Indeed, for incomplete object-oriented programs, it is not always possible to completely disambiguate the syntactic constructs and to recover the declared type of certain expressions because the declaration of many types and class members are not accessible.

We present a framework that performs partial type inference and uses heuristics to recover the declared type of expressions and resolve ambiguities in partial Java programs. Our framework produces a complete and typed IR suitable for further static analysis. We have implemented this framework and used it in an empirical study on four large open source systems which shows that our system recovers most declared types with a low error rate, even when only one class is accessible.

REFERENCES

• 1: JFreeChart. http://www.object-refinery.com/jfreechart/.
• 2: Jython. http://www.jython.org.
• 3: Lucene. http://lucene.apache.org.
• 4: Spring Framework. http://www.springframework.org.
• 5: Nathaniel Ayewah , William Pugh , J. David Morgenthaler , John Penix , YuQian Zhou, Using FindBugs on production software, Companion to the 22nd ACM SIGPLAN conference on Object oriented programming systems and applications companion, October 21-25, 2007, Montreal, Quebec, Canada [doi>10.1145/1297846.1297897]
• 6: Rolf Bahlke , Gregor Snelting, The PSG system: from formal language definitions to interactive programming environments, ACM Transactions on Programming Languages and Systems (TOPLAS), v.8 n.4, p.547-576, Oct. 1986 [doi>10.1145/6465.20890]
• 7: Nicolas Bettenburg , Rahul Premraj , Thomas Zimmermann , Sunghun Kim, Extracting structural information from bug reports, Proceedings of the 2008 international working conference on Mining software repositories, May 10-11, 2008, Leipzig, Germany [doi>10.1145/1370750.1370757]
• 8: Barthélémy Dagenais , Martin P. Robillard, Recommending adaptive changes for framework evolution, Proceedings of the 30th international conference on Software engineering, May 10-18, 2008, Leipzig, Germany [doi>10.1145/1368088.1368154]
• 9: Evelyn Duesterwald , Rajiv Gupta , Mary Lou Soffa, A practical framework for demand-driven interprocedural data flow analysis, ACM Transactions on Programming Languages and Systems (TOPLAS), v.19 n.6, p.992-1030, Nov. 1997 [doi>10.1145/267959.269970]
• 10: Etienne Gagnon , Laurie J. Hendren , Guillaume Marceau, Efficient Inference of Static Types for Java Bytecode, Proceedings of the 7th International Symposium on Static Analysis, p.199-219, June 29-July 01, 2000
• 11: Rajiv Gupta , Mary Lou Soffa, A Framework for Partial Data Flow Analysis, Proceedings of the International Conference on Software Maintenance, p.4-13, September 01, 1994
• 12: Gregory Knapen , Bruno Laguë , Michel Dagenais , Ettore Merlo, Parsing C++ Despite Missing Declarations, Proceedings of the 7th International Workshop on Program Comprehension, p.114, May 05-07, 1999
• 13: Rainer Koppler, A systematic approach to fuzzy parsing, Software—Practice & Experience, v.27 n.6, p.637-649, June 1997 [doi>10.1002/(SICI)1097-024X(199706)27:6<637::AID-SPE99>3.0.CO;2-3]
• 14: Leon Moonen, Generating Robust Parsers using Island Grammars, Proceedings of the Eighth Working Conference on Reverse Engineering (WCRE'01), p.13, October 02-05, 2001
• 15: Nathaniel Nystrom, Michael R. Clarkson, and Andrew C. Myers. Polyglot: An extensible compiler framework for java. In Proc. of the 12th International Conference on Compiler Construction, pages 138--152, 2003.
• 16: Fragment Class Analysis for Testing of Polymorphism in Java Software, IEEE Transactions on Software Engineering, v.30 n.6, p.372-387, June 2004 [doi>10.1109/TSE.2004.20]
• 17: Atanas Rountev , Barbara G. Ryder , William Landi, Data-flow analysis of program fragments, Proceedings of the 7th European software engineering conference held jointly with the 7th ACM SIGSOFT international symposium on Foundations of software engineering, p.235-252, September 06-10, 1999, Toulouse, France
• 18: Stephen M. Blackburn , Robin Garner , Chris Hoffmann , Asjad M. Khang , Kathryn S. McKinley , Rotem Bentzur , Amer Diwan , Daniel Feinberg , Daniel Frampton , Samuel Z. Guyer , Martin Hirzel , Antony Hosking , Maria Jump , Han Lee , J. Eliot B. Moss , B. Moss , Aashish Phansalkar , Darko Stefanović , Thomas VanDrunen , Daniel von Dincklage , Ben Wiedermann, The DaCapo benchmarks: java benchmarking development and analysis, Proceedings of the 21st annual ACM SIGPLAN conference on Object-oriented programming systems, languages, and applications, October 22-26, 2006, Portland, Oregon, USA
• 19: Suresh Thummalapenta , Tao Xie, Parseweb: a programmer assistant for reusing open source code on the web, Proceedings of the twenty-second IEEE/ACM international conference on Automated software engineering, November 05-09, 2007, Atlanta, Georgia, USA [doi>10.1145/1321631.1321663]
• 20: Raja Vallée-Rai , Phong Co , Etienne Gagnon , Laurie Hendren , Patrick Lam , Vijay Sundaresan, Soot - a Java bytecode optimization framework, Proceedings of the 1999 conference of the Centre for Advanced Studies on Collaborative research, p.13, November 08-11, 1999, Mississauga, Ontario, Canada
• 21: Wei Zhao , Lu Zhang , Yin Liu , Jiasu Sun , Fuqing Yang, SNIAFL: Towards a static noninteractive approach to feature location, ACM Transactions on Software Engineering and Methodology (TOSEM), v.15 n.2, p.195-226, April 2006 [doi>10.1145/1131421.1131424]
• 22: Thomas Zimmermann , Peter Weissgerber , Stephan Diehl , Andreas Zeller, Mining Version Histories to Guide Software Changes, IEEE Transactions on Software Engineering, v.31 n.6, p.429-445, June 2005 [doi>10.1109/TSE.2005.72]

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors

General Terms:
Experimentation, Languages

Keywords:
java, partial programs, type inference