Abstract
A joint points-to and exception analysis has been shown to yield benefits in both precision and performance. Treating exceptions as regular objects, however, incurs significant and rather unexpected overhead. We show that in a typical joint analysis most of the objects computed to flow in and out of a method are due to exceptional control-flow and not normal call-return control-flow. For instance, a context-insensitive analysis of the Antlr benchmark from the DaCapo suite computes 4-5 times more objects going in or out of a method due to exceptional control-flow than due to normal control-flow. As a consequence, the analysis spends a large amount of its time considering exceptions.
We show that the problem can be addressed both effectively and elegantly by coarsening the representation of exception objects. An interesting find is that, instead of recording each distinct exception object, we can collapse all exceptions of the same type, and use one representative object per type, to yield nearly identical precision (loss of less than 0.1%) but with a boost in performance of at least 50% for most analyses and benchmarks and large space savings (usually 40% or more).
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Bravenboer, M., Smaragdakis, Y.: Exception analysis and points-to analysis: Better together. In: Dillon, L. (ed.) ISSTA 2009: Proceedings of the 2009 International Symposium on Software Testing and Analysis, New York, NY, USA (July 2009)
Bravenboer, M., Smaragdakis, Y.: Strictly declarative specification of sophisticated points-to analyses. In: OOPSLA 2009: 24th Annual ACM SIGPLAN Conference on Object Oriented Programming, Systems, Languages, and Applications. ACM, New York (2009)
Chatterjee, R., Ryder, B.G., Landi, W.A.: Complexity of points-to analysis of Java in the presence of exceptions. IEEE Trans. Softw. Eng. 27(6), 481–512 (2001)
Choi, J.D., Grove, D., Hind, M., Sarkar, V.: Efficient and precise modeling of exceptions for the analysis of Java programs. SIGSOFT Softw. Eng. Notes 24(5), 21–31 (1999)
Eichberg, M., Kloppenburg, S., Klose, K., Mezini, M.: Defining and continuous checking of structural program dependencies. In: ICSE 2008: Proc. of the 30th Int. Conf. on Software Engineering, pp. 391–400. ACM, New York (2008)
Fink, S.J., et al.: T.J. Watson libraries for analysis (WALA), http://wala.sourceforge.net
Fu, C., Milanova, A., Ryder, B.G., Wonnacott, D.G.: Robustness testing of Java server applications. IEEE Trans. Softw. Eng. 31(4), 292–311 (2005)
Fu, C., Ryder, B.G.: Exception-chain analysis: Revealing exception handling architecture in Java server applications. In: ICSE 2007: Proceedings of the 29th International Conference on Software Engineering, pp. 230–239. IEEE Computer Society, Washington, DC (2007)
Fu, C., Ryder, B.G., Milanova, A., Wonnacott, D.: Testing of Java web services for robustness. In: ISSTA 2004: Proceedings of the 2004 ACM SIGSOFT International Symposium on Software Testing and Analysis, pp. 23–34. ACM, New York (2004)
Guarnieri, S., Livshits, B.: GateKeeper: mostly static enforcement of security and reliability policies for Javascript code. In: Proceedings of the 18th USENIX Security Symposium, SSYM 2009, pp. 151–168. USENIX Association, Berkeley (2009), http://dl.acm.org/citation.cfm?id=1855768.1855778
Hajiyev, E., Verbaere, M., de Moor, O.: codeQuest: Scalable Source Code Queries with Datalog. In: Thomas, D. (ed.) ECOOP 2006. LNCS, vol. 4067, pp. 2–27. Springer, Heidelberg (2006)
Hardekopf, B., Lin, C.: The ant and the grasshopper: fast and accurate pointer analysis for millions of lines of code. In: PLDI 2007: Proc. ACM SIGPLAN Conf. on Programming Language Design and Implementation, pp. 290–299. ACM, New York (2007)
Hardekopf, B., Lin, C.: Semi-sparse flow-sensitive pointer analysis. In: POPL 2009: Proceedings of the 36th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pp. 226–238. ACM, New York (2009)
Jo, J.-W., Chang, B.-M.: Constructing Control Flow Graph for Java by Decoupling Exception Flow from Normal Flow. In: Laganá, A., Gavrilova, M.L., Kumar, V., Mun, Y., Tan, C.J.K., Gervasi, O. (eds.) ICCSA 2004. LNCS, vol. 3043, pp. 106–113. Springer, Heidelberg (2004)
Jo, J.W., Chang, B.M., Yi, K., Choe, K.M.: An uncaught exception analysis for Java. Journal of Systems and Software 72(1), 59–69 (2004)
Jorgensen, J.: Improving the precision and correctness of exception analysis in Soot. Tech. Rep. 2003-3, McGill University (September 2004)
Lam, M.S., Whaley, J., Livshits, V.B., Martin, M.C., Avots, D., Carbin, M., Unkel, C.: Context-sensitive program analysis as database queries. In: PODS 2005: Proc. of the Twenty-Fourth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, pp. 1–12. ACM, New York (2005)
Lhoták, O.: Program Analysis using Binary Decision Diagrams. Ph.D. thesis, McGill University (January 2006)
Lhoták, O., Hendren, L.: Scaling Java Points-to Analysis Using SPARK. In: Hedin, G. (ed.) CC 2003. LNCS, vol. 2622, pp. 153–169. Springer, Heidelberg (2003)
Lhoták, O., Hendren, L.: Evaluating the benefits of context-sensitive points-to analysis using a BDD-based implementation. ACM Trans. Softw. Eng. Methodol. 18(1), 1–53 (2008)
Madsen, M., Livshits, B., Fanning, M.: Practical static analysis of Javascript applications in the presence of frameworks and libraries. Tech. Rep. MSR-TR-2012-66, Microsoft Research (Jully 2012)
Might, M., Smaragdakis, Y., Van Horn, D.: Resolving and exploiting the k-CFA paradox: Illuminating functional vs. object-oriented program analysis. In: Conf. on Programming Language Design and Implementation (PLDI), pp. 305–315. ACM (June 2010)
Milanova, A., Rountev, A., Ryder, B.G.: Parameterized object sensitivity for points-to analysis for Java. ACM Trans. Softw. Eng. Methodol. 14(1), 1–41 (2005)
Reps, T.: Demand interprocedural program analysis using logic databases. In: Ramakrishnan, R. (ed.) Applications of Logic Databases, pp. 163–196. Kluwer Academic Publishers (1994)
Sharir, M., Pnueli, A.: Two approaches to interprocedural data flow analysis. In: Muchnick, S.S., Jones, N.D. (eds.) Program Flow Analysis, pp. 189–233. Prentice-Hall, Inc., Englewood Cliffs (1981)
Shivers, O.: Control-Flow Analysis of Higher-Order Languages. Ph.D. thesis, Carnegie Mellon University (May 1991)
Sinha, S., Harrold, M.J.: Analysis and testing of programs with exception handling constructs. IEEE Trans. Softw. Eng. 26(9), 849–871 (2000)
Smaragdakis, Y., Bravenboer, M., Lhoták, O.: Pick your contexts well: Understanding object-sensitivity (the making of a precise and scalable pointer analysis). In: ACM Symposium on Principles of Programming Languages (POPL), pp. 17–30. ACM Press (January 2011)
Whaley, J., Avots, D., Carbin, M., Lam, M.S.: Using Datalog with Binary Decision Diagrams for Program Analysis. In: Yi, K. (ed.) APLAS 2005. LNCS, vol. 3780, pp. 97–118. Springer, Heidelberg (2005)
Whaley, J., Lam, M.S.: Cloning-based context-sensitive pointer alias analysis using binary decision diagrams. In: PLDI 2004: Proc. of the ACM SIGPLAN 2004 Conf. on Programming Language Design and Implementation, pp. 131–144. ACM, New York (2004)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Kastrinis, G., Smaragdakis, Y. (2013). Efficient and Effective Handling of Exceptions in Java Points-to Analysis. In: Jhala, R., De Bosschere, K. (eds) Compiler Construction. CC 2013. Lecture Notes in Computer Science, vol 7791. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-37051-9_3
Download citation
DOI: https://doi.org/10.1007/978-3-642-37051-9_3
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-37050-2
Online ISBN: 978-3-642-37051-9
eBook Packages: Computer ScienceComputer Science (R0)