A constraint-weaving approach to points-to analysis for AspectJ

Abstract

Points-to analysis is a static code analysis technique that establishes the relationships between variables of references and allocated objects. A number of points-to analysis algorithms have been proposed for procedural and object-oriented languages like C and Java, while few of them can be used for AspectJ as we know so far. One main reason is that AspectJ is an aspect-oriented language which implements the separation of crosscutting concerns by advices, pointcuts, and inter-type declarations, while a points-to analysis of AspectJ programs may be imprecise because any aspect woven into the base code may change the points-to relations in the program and thus a conservative analysis has to be taken in order to handle the aspects. In this paper, we propose a context-sensitive points-to analysis technique called AJPoints for AspectJ. Similar to the weaving mechanism for AspectJ, AJPoints obtains the constraints and templates on the points-to relations for the base code and the aspects, espectively, but weaves and solves them in an iterative manner in order to cross the boundary between the base code and the aspects. We have implemented AJPoints on abc AspectJ compiler and evaluated it by using twelve AspectJ benchmark programs. The experimental results show that our technique can achieve a high precision about points-to relations in AspectJ programs.

Keywords

points-to analysis / context-sensitive analysis / AspectJ

References

[1] Hind M, Pioli A. Which pointer analysis should I use? In: Proceedings of the 2000 ACM SIGSOFT International Symposium on Software Testing and Analysis. 2000, 113−123

[2] Nguyen P H, Xue J. Interprocedural side-effect analysis and optimisation in the presence of dynamic class loading. In: Proceedings of the 28th Australasian Conference on Computer Science. 2005, 9−18

[3] Zhao J. Slicing aspect-oriented software. In: Proceedings of the 10th International Workshop on Program Comprehension. 2002, 251−260

[4] Sui Y, Ye D, Xue J. Static memory leak detection using full-sparse value-flow analysis. In: Proceedings of the 2012 International Symposium on Software Testing and Analysis. 2012, 254−264

[5] Xie T, Zhao J. A framework and tool supports for generating test inputs of AspectJ programs. In: Proceedings of the 5th International Conference on Aspect-Oriented Software Development. 2006, 190−201

[6] Milanova A, Rountev A, Ryder B G. Parameterized object sensitivity for points-to analysis for Java. ACM Transactions on Software Engineering and Methodology, 2002, 14: 1−41

[7] Lhoták O, Hendren L. Scaling Java points-to analysis using SPARK. In: Proceedings of the 12th International Conference on Compiler Construction. 2003, 153−169

[8] Xu G H, Rountev A. AJANA: a general framework for source-codelevel interprocedural dataflow analysis of AspectJ software. In: Proceedings of the 7th International Conference on Aspect-Oriented Software Development. 2008, 36−47

[9] Chatterjee R, Ryder B G, Landi W A. Complexity of points-to analysis of Java in the presence of exceptions. IEEE Transactions on Software Engineering, 2001, 27(6): 481−512

[10] Whaley J, Lam M S. Cloning-based context-sensitive pointer alias analysis using binary decision diagrams. In: Proceedings of the ACM SIGPLAN 2004 Conference on Programming Language Design and Implementation. 2004, 131−144

[11] Andersen L. Program analysis and specialization for the C programming language. PhD thesis, Denmark: University of Copenhagen, 1994

[12] Smaragdakis Y, Bravenboer M, Lhoták O. Pick your contexts well: understanding object-sensitivity. In: Proceedings of the 38th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages. 2011, 17−30

[13] The AspectJ Programming Guide. The AspectJ Team, 2002

[14] Sridharan M, Bodík R. Refinement-based context-sensitive points-to analysis for Java. In: Proceedings of the ACM SIGPLAN 2006 Conference on Programming Language Design and Implementation. 2006, 387−400

[15] Shang L, Xie X, Xue J. On-demand dynamic summary-based points-to analysis. In: Proceedings of the 10th Annual IEEE/ACM International Symposium on Code Generation and Optimization. 2012, 264−274

[16] Zhang Q, Lyu M R, Yuan H, Su Z. Fast algorithms for Dyck-CFLreachability with applications to alias analysis. In: Proceedings of the 34th ACM SIGPLAN Conference on Programming Language Design and Implementation. 2013, 435−446

[17] Lu Y, Shang L, Xie X, Xue J. Fast and precise points-to analysis with incremental CFL-reachability summarisation: preliminary experience. In: Proceedings of the 27th IEEE/ACM International Conference on Automated Software Engineering. 2013, 270−273

[18] The AspectBench Compiler.

[19] Dufour B, Goard C, Hendren L J, Moor d O, Sittampalam G, Verbrugge C. Measuring the dynamic behaviour of AspectJ programs. In: Proceedings of the 19th Annual ACM SIGPLAN Conference on Object- Oriented Programming, Systems, Languages, and Applications. 2004, 150−169

[20] Glassbox. http://glassbox.sourceforge.net/

[21] *J. http://www.sable.mcgill.ca/starj/

[22] AJHSQLDB. http://ajhsqldb.sourceforge.net/

[23] Soot.

[24] Hind M. Pointer analysis: haven’t we solved this problem yet? In: Proceedings of the 2001 ACMSIGPLAN-SIGSOFTWorkshop on Program Analysis for Software Tools and Engineering. 2001, 54−61

[25] Liang D, Pennings M, Harrold M J. Extending and evaluating flowinsensitive and context-insensitive points-to analyses for Java. In: Proceedings of theWorkshop on Program Analysis for Software Tools and Engineering. 2001, 73−79

[26] Steensgaard B. Points-to analysis in almost linear time. In: Proceedings of the 23rd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages. 1996, 32−41

[27] Emami M, Ghiya R, Hendren L J. Context-sensitive interprocedural points-to analysis in the presence of function pointers. In: Proceedings of the ACM SIGPLAN 1994 Conference on Programming Language Design and Implementation. 1994, 242−256

[28] Landi W, Ryder B G, Zhang S. Interprocedural modification side effect analysis with pointer aliasing. In: Proceedings of the ACM SIGPLAN 1993 Conference on Programming Language Design and Implementation. 1993, 56−67

[29] Whaley J, Rinard M. Compositional pointer and escape analysis for Java programs. In: Proceedings of the 14th Annual ACM SIGPLAN Conference on Object-Oriented Programming Systems, Languages and Applications. 1999, 187−206

[30] Wilson R, Lam M S. Efficient context-sensitive pointer analysis for C programs. In: Proceedings of the ACM SIGPLAN 1995 Conference on Programming Language Design and Implementation. 1995, 1−12

[31] Whaley J, Lam M S. An efficient inclusion-based points-to analysis for strictly-typed languages. In: Proceedings of the 9th International Static Analysis Symposium. 2002, 180−195

[32] Sui Y, Ye S, Xue J, Yew P C. SPAS: scalable path-sensitive pointer analysis on full-sparse SSA. In: Proceedings of the 9th Asian Conference on Programming Languages and Systems. 2011, 155−171

[33] Li L, Cifuentes C, Keynes N. Precise and scalable context-sensitive pointer analysis via value flow graph. In: Proceedings of the 2013 International Symposium on Memory Management. 2013, 85−96

[34] Kahlon V. Bootstrapping: a technique for scalable flow and contextsensitive pointer alias analysis. In: Proceedings of the ACM SIGPLAN 2008 conference on Programming Language Design and Implementation. 2008, 249−259

[35] Yu H, Xue J, Huo W, Feng X, Zhang Z. Level by level: making flowand context-sensitive pointer analysis scalable for millions of lines of code. In: Proceedings of the 8th International Symposium on Code Generation and Optimization. 2010, 218−229

[36] Zhu J, Calman S. Symbolic pointer analysis revisited. In: Proceedings of the ACM SIGPLAN 2004 Conference on Programming Language Design and Implementation. 2004, 145−157

[37] Lhoták O, Hendren L J. Context-sensitive points-to analysis: is it worth it? In: Proceedings of the 15th International Conference on Compiler Construction. 2006, 47−64

[38] Sui Y, Li Y, Xue J. Query-directed adaptive heap cloning for optimizing compilers. In: Proceedings of the 2013 IEEE/ACM International Symposium on Code Generation and Optimization. 2013, 1−11

[39] Choi J D, Burke M, Carini P. Efficient flow-sensitive interprocedural computation of pointer-induced aliases and side effects. In: Proceedings of the 20th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages. 1993, 232−245

[40] Hind M, Burke M, Carini P, Choi J D. Interprocedural pointer alias analysis. ACM Transactions on Programming Languages and Systems, 1999, 21(4): 848−894

[41] Hardekopf B, Lin C. Semi-sparse flow-sensitive pointer analysis. In: Proceedings of the 36th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages. 2009, 226−238

[42] Rinard M, Sălcianu A, Bugrara S. A classification system and analysis for aspect-oriented programs. In: Proceedings of the 12th ACM SIGSOFT International Symposium on Foundations of Software Engineering. 2004, 147−158

[43] Sun Q, Zhao J. Aspect-aware points-to analysis. In: Proceedings of the 8th IEEE International Working Conference on Source Code Analysis and Manipulation. 2008, 143−152

[44] Avgustinov P, Christensen A S, Hendren L J, Kuzins S, Lhoták J, Lhoták O , Moor d O, Sereni D, Sittampalam G, Tibble J. Optimising AspectJ. In: Proceedings of the ACM SIGPLAN 2005 Conference on Programming Language Design and Implementation. 2005, 117−128

RIGHTS & PERMISSIONS

2013 Higher Education Press and Springer-Verlag Berlin Heidelberg