Exception analysis and points-to analysis: better together

ABSTRACT

Exception analysis and points-to analysis are typically done in complete separation. Past algorithms for precise exception analysis (e.g., pairing throw clauses with catch statements) use pre-computed points-to information. Past points-to analyses either unsoundly ignore exceptions, or conservatively compute a crude approximation of exception throwing (e.g., considering an exception throw as an assignment to a global variable, accessible from any catch clause). We show that this separation results in significant slowdowns or vast imprecision. The two kinds of analyses are interdependent: neither can be performed accurately without the other. The interdependency leads us to propose a joint handling for performance and precision. We show that our exception analysis is expressible highly elegantly in a declarative form, and can apply to points-to analyses of varying precision. In fact, our specification of exception analysis is "fully precise", as it models closely the Java exception handling semantics. The necessary approximation is provided only through whichever abstractions are used for contexts and objects in the base points-to analysis. Our combined approach achieves similar precision relative to exceptions (exception-catch links) as the best past precise exception analysis, with a runtime of seconds instead of tens of minutes. At the same time, our analysis achieves much higher precision of points-to information (an average of half as many values for each reachable variable for most of the DaCapo benchmarks) than points-to analyses that treat exceptions conservatively, all at a fraction of the execution time.

REFERENCES

• 1: M. Bravenboer and Y. Smaragdakis. Strictly declarative specification of sophisticated points-to analyses. In submission to OOPSLA '09: 24th annual ACM SIGPLAN conference on Object Oriented Programming, Systems, Languages, and Applications, 2009.
• 2: Raymond P.L. Buse , Westley R. Weimer, Automatic documentation inference for exceptions, Proceedings of the 2008 international symposium on Software testing and analysis, July 20-24, 2008, Seattle, WA, USA [doi>10.1145/1390630.1390664]
• 3: Ramkrishna Chatterjee , Barbara G. Ryder , William A. Landi, Complexity of Points-To Analysis of Java in the Presence of Exceptions, IEEE Transactions on Software Engineering, v.27 n.6, p.481-512, June 2001 [doi>10.1109/32.926173]
• 4: Jong-Deok Choi , David Grove , Michael Hind , Vivek Sarkar, Efficient and precise modeling of exceptions for the analysis of Java programs, ACM SIGSOFT Software Engineering Notes, v.24 n.5, p.21-31, Sept. 1999
• 5: Steven Dawson , C. R. Ramakrishnan , David S. Warren, Practical program analysis using general purpose logic programming systems—a case study, Proceedings of the ACM SIGPLAN 1996 conference on Programming language design and implementation, p.117-126, May 21-24, 1996, Philadelphia, Pennsylvania, United States
• 6: Michael Eichberg , Sven Kloppenburg , Karl Klose , Mira Mezini, Defining and continuous checking of structural program dependencies, Proceedings of the 30th international conference on Software engineering, May 10-18, 2008, Leipzig, Germany [doi>10.1145/1368088.1368142]
• 7: S. J. Fink. T. J. Watson libraries for analysis (WALA). http://wala.sourceforge.net.
• 8: Chen Fu , Ana Milanova , Barbara Gershon Ryder , David G. Wonnacott, Robustness Testing of Java Server Applications, IEEE Transactions on Software Engineering, v.31 n.4, p.292-311, April 2005 [doi>10.1109/TSE.2005.51]
• 9: Chen Fu , Barbara G. Ryder, Exception-Chain Analysis: Revealing Exception Handling Architecture in Java Server Applications, Proceedings of the 29th international conference on Software Engineering, p.230-239, May 20-26, 2007 [doi>10.1109/ICSE.2007.35]
• 10: Chen Fu , Barbara G. Ryder , Ana Milanova , David Wonnacott, Testing of java web services for robustness, Proceedings of the 2004 ACM SIGSOFT international symposium on Software testing and analysis, July 11-14, 2004, Boston, Massachusetts, USA
• 11: E. Hajiyev, M. Verbaere, and O. de Moor. Codequest: Scalable source code queries with Datalog. In ECOOP'06: Proceedings of the 20th European Conference on Object-Oriented Programming, 2006.
• 12: N. Immerman. Descriptive Complexity. Springer, 1998.
• 13: Jang-Wu Jo , Byeong-Mo Chang , Kwangkeun Yi , Kwang-Moo Choe, An uncaught exception analysis for Java, Journal of Systems and Software, v.72 n.1, p.59-69, June 2004 [doi>10.1016/S0164-1212(03)00057-8]
• 14: J. Jorgensen. Improving the precision and correctness of exception analysis in Soot. Technical Report 2003-3, McGill University, 2004.
• 15: Xavier Leroy , François Pessaux, Type-based analysis of uncaught exceptions, ACM Transactions on Programming Languages and Systems (TOPLAS), v.22 n.2, p.340-377, March 2000 [doi>10.1145/349214.349230]
• 16: O. Lhoták. Program Analysis using Binary Decision Diagrams. PhD thesis, McGill University, 2006.
• 17: O. Lhoták and L. Hendren. Scaling Java points-to analysis using Spark. In Compiler Construction, 12th International Conference, 2003.
• 18: Ondřej Lhoták , Laurie Hendren, Jedd: a BDD-based relational extension of Java, Proceedings of the ACM SIGPLAN 2004 conference on Programming language design and implementation, June 09-11, 2004, Washington DC, USA
• 19: Ondřej Lhoták , Laurie Hendren, Evaluating the benefits of context-sensitive points-to analysis using a BDD-based implementation, ACM Transactions on Software Engineering and Methodology (TOSEM), v.18 n.1, p.1-53, September 2008 [doi>10.1145/1391984.1391987]
• 20: Ju Qian , Baowen Xu, Thread-Sensitive Pointer Analysis for Inter-Thread Dataflow Detection, Proceedings of the 11th IEEE International Workshop on Future Trends of Distributed Computing Systems, p.157-163, March 21-23, 2007 [doi>10.1109/FTDCS.2007.34]
• 21: T. Reps. Demand interprocedural program analysis using logic databases. In Applications of Logic Databases, 1994.
• 22: Martin P. Robillard , Gail C. Murphy, Static analysis to support the evolution of exception structure in object-oriented systems, ACM Transactions on Software Engineering and Methodology (TOSEM), v.12 n.2, p.191-221, April 2003 [doi>10.1145/941566.941569]
• 23: S. Ryu , K. Yi, Exception Analysis for Multithreaded Java Programs, Proceedings of the Second Asia-Pacific Conference on Quality Software, p.23, December 10-11, 2001
• 24: Saurabh Sinha , Mary Jean Harrold, Analysis and Testing of Programs with Exception Handling Constructs, IEEE Transactions on Software Engineering, v.26 n.9, p.849-871, September 2000 [doi>10.1109/32.877846]
• 25: J. Whaley, D. Avots, M. Carbin, and M. S. Lam. Using Datalog with binary decision diagrams for program analysis. In Proc. of the 3rd Asian Symposium on Programming Languages and Systems, 2005.
• 26: John Whaley , Monica S. Lam, Cloning-based context-sensitive pointer alias analysis using binary decision diagrams, Proceedings of the ACM SIGPLAN 2004 conference on Programming language design and implementation, June 09-11, 2004, Washington DC, USA
• 27: Kwangkeun Yi , Sukyoung Ryu, Towards a Cost-Effective Estimation of Uncaught Exceptions in SML Programs, Proceedings of the 4th International Symposium on Static Analysis, p.98-113, September 08-10, 1997

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.2 Semantics of Programming Languages
          Subjects: Program analysis

Additional Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.6 Logic Programming

General Terms:
Algorithms, Languages, Performance

Keywords:
context-sensitive, exception handling, points-to analysis, precision