微信服务号

微信订阅号

2025-5-15- 23
Home > Archive>Volume 33, Issue 1, 2022 >78-101. DOI:10.13328/j.cnki.jos.006345
PDF HTML XML Export Cite reminder
Context-sensitive Pointer Analysis for Object-oriented Programs: A Systematic Literature Review
Author:
Affiliation:

Clc Number:

TP311

Fund Project:

National Natural Science Foundation of China (61872043)

  • Article
    • | |
  • Metrics
    • |
  • Reference [125]
    • |
  • Related [20]
    • | | |
  • Comments
    Abstract:

    Pointer analysis is the basis of compiler optimization and static analysis, and a lot of applications are based on pointer analysis. Low-precision pointer analysis brings high false positive rate and false negative rate to these applications, and adding context sensitive information is an important means to improve accuracy. Since the object-oriented concept was put forward, it has been widely used. Some mainstream languages, such as Java, C++, .NET and C#, support object-oriented features. Therefore, pointer analysis for object-oriented language is getting more and more attention. This study investigates context-sensitive pointer analysis for object-oriented language by using systematic literature review (SLR) method. After analyzing and categorizing the relevant literature, five questions are summarized about context-sensitive pointer analysis for object-oriented language.

    Reference
    [1] Horwitz S. Precise flow-insensitive may-alias analysis is NP-hard. ACM Transactions on Programming Languages and Systems, 1997, 19(1): 1–6. [doi: 10.1145/239912.239913]
    [2] Landi W, Ryder BG. A safe approximate algorithm for interprocedural aliasing. In: Proc. of the ACM SIGPLAN 1992 Conf. on Programming Language Design and Implementation. San Francisco: ACM, 1992. 235–248. [doi: 10.1145/143095.143137]
    [3] Ramalingam G. The undecidability of aliasing. ACM Transactions on Programming Languages and Systems, 1994, 16(5): 1467–1471. [doi: 10.1145/186025.186041]
    [4] Landi W. 1992. Undecidability of static analysis. ACM Letters on Programming Languages and Systems, 1992, 1(4): 323–337. [doi: 10.1145/161494.161501]
    [5] Hind M. Pointer analysis: Haven’t we solved this problem yet? In: Proc. of the 2001 ACM SIGPLAN-SIGSOFT Workshop on Program Analysis for Software Tools and Engineering. Snowbird: ACM, 2001. 54–61. [doi: 10.1145/379605.379665]
    [6] Ryder BG. Dimensions of precision in reference analysis of object-oriented programming languages. In: Proc. of the 12th Int’l Conf. on Compiler Construction. Warsaw: Springer, 2003. 126–137. [doi: 10.1007/3-540-36579-6_10]
    [7] Steensgaard B. Points-to analysis in almost linear time. In: Proc. of the 23rd ACM SIGPLAN-SIGACT Symp. on Principles of Programming Languages. St. Petersburg Beach: ACM, 1996. 32–41. [doi: 10.1145/237721.237727]
    [8] Andersen LO. Program analysis and specialization for the C programming language [Ph.D. Thesis]. Copenhagen: University of Copenhagen, 1994.
    [9] Lhoták O, Hendren L. Scaling Java points-to analysis using spark. In: Proc. of the 12th Int’l Conf. on Compiler Construction. Warsaw: Springer, 2003. 153–169. [doi: 10.1007/3-540-36579-6_12]
    [10] Rountev A, Milanova A, Ryder BG. Points-to analysis for Java using annotated constraints. ACM SIGPLAN Notices, 2001, 36(11): 43–55. [doi: 10.1145/504311.504286]
    [11] Whaley J, Lam MS. An efficient inclusion-based points-to analysis for strictly-typed languages. In: Proc. of the 9th Int’l Static Analysis Symp. Madrid: Springer, 2002. 180–195. [doi: 10.1007/3-540-45789-5_15]
    [12] Sridharan M, Fink SJ. The complexity of Andersen’s analysis in practice. In: Proc. of the 16th Int’l Static Analysis Symp. Los Angeles: Springer, 2009. 205–221. [doi: 10.1007/978-3-642-03237-0_15]
    [13] Razafimahefa C. A study of side-effect analyses for Java [MS. Thesis]. Montreal: McGill University, 1999.
    [14] Streckenbach M, Snelting G. Points-to for Java: A general framework and an empirical comparison. Universität Passau, 2000.
    [15] Liang DL, Pennings M, Harrold MJ. Extending and evaluating flow-insenstitive and context-insensitive points-to analyses for Java. In: Proc. of 2001 ACM SIGPLAN-SIGSOFT Workshop on Program Analysis for Software Tools and Engineering. Snowbird: ACM, 2001. 73–79. [doi: 10.1145/379605.379676]
    [16] Kitchenham B. Procedures for performing systematic reviews. Technical Report, Australia: Keele University and National ICT, 2004.
    [17] Nguyen P H, Kramer M, Klein J, Traon YL. An extensive systematic review on the Model-Driven Development of secure systems. Information and Software Technology, 2015, 68: 62–81. [doi: 10.1016/j.infsof.2015.08.006]
    [18] Li L, Bissyandé TF, Papadakis M, Rasthofer S, Bartel A, Octeau D, Klein J, Traon L. Static analysis of android apps: A systematic literature review. Information and Software Technology, 2017, 88: 67–95. [doi: 10.1016/j.infsof.2017.04.001]
    [19] Aho AV, Lam MS, Sethi R, Ullman JD. Compilers: Principles, Techniques, and Tools. 2nd ed., Boston: Addison Wesley, 2006.
    [20] Sharir M, Pnueli A. Two approaches to interprocedural data flow analysis. New York: New York University, 1978.
    [21] Shivers O. Control-flow analysis of higher-order languages [Ph.D. Thesis]. Pittsburgh: Carnegie Mellon University, 1991.
    [22] Grove D, DeFouw G, Dean J, Chambers C. Call graph construction in object-oriented languages. ACM SIGPLAN Notices, 1997, 32(10): 108–124. [doi: 10.1145/263700.264352]
    [23] Milanova A, Rountev A, Ryder BG. Parameterized object sensitivity for points-to analysis for Java. ACM Transactions on Software Engineering and Methodology, 2005, 14(1): 1–41. [doi: 10.1145/1044834.1044835]
    [24] Milanova A, Rountev A, Ryder BG. Parameterized object sensitivity for points-to and side-effect analyses for Java. ACM SIGSOFT Software Engineering Notes, 2002, 27(4): 1–11. [doi: 10.1145/566171.566174]
    [25] Smaragdakis Y, Bravenboer M, Lhoták O. Pick your contexts well: Understanding object-sensitivity. ACM SIGPLAN Notices, 2011, 46(1): 17–30. [doi: 10.1145/1925844.1926390]
    [26] Lhoták O. Program analysis using binary decision diagrams [Ph.D. Thesis]. Montreal: McGill University, 2006.
    [27] Lhoták O, Hendren L. Relations as an abstraction for BDD-based program analysis. ACM Transactions on Programming Languages and Systems, 2008, 30(4): 19. [doi: 10.1145/1377492.1377494]
    [28] Lundberg J, Gutzmann T, Edvinsson M, Löwe W. Fast and precise points-to analysis. Information and Software Technology, 2009, 51(10): 1428–1439. [doi: 10.1016/j.infsof.2009.04.012]
    [29] Liang DL, Pennings M, Harrold MJ. Evaluating the impact of context-sensitivity on Andersen's algorithm for Java programs. ACM SIGSOFT Software Engineering Notes, 2006, 31(1): 6–12. [doi: 10.1145/1108768.1108797]
    [30] Lhoták O, Hendren L. Context-sensitive points-to analysis: Is it worth it? In: Proc. of the 15th Int’l Conf. on Compiler Construction. Vienna: Springer, 2006. 47–64. [doi: 10.1007/11688839_5]
    [31] Lhoták O, Hendren L. Evaluating the benefits of context-sensitive points-to analysis using a BDD-based implementation. ACM Transactions on Software Engineering and Methodology, 2008, 18(1): 3. [doi: 10.1145/1391984.1391987]
    [32] Lundberg J, Löwe W. Points-to analysis: A fine-grained evaluation. Journal of Universal Computer Science, 2012, 18(20): 2851–2878. [doi: 10.3217/jucs-018-20-2851]
    [33] Padhye R, Khedker UP. Interprocedural data flow analysis in soot using value contexts. In: Proc. of the 2nd ACM SIGPLAN Int’l Workshop on State of the Art in Java Program Analysis. Seattle: ACM, 2013. 31–36. [doi: 10.1145/2487568.2487569]
    [34] Petrashko D, Ureche V, Lhoták O, Odersky M. Call graphs for languages with parametric polymorphism. ACM SIGPLAN Notices, 2016, 51(10): 394–409. [doi: 10.1145/3022671.2983991]
    [35] Kastrinis G, Smaragdakis Y. Hybrid context-sensitivity for points-to analysis. ACM SIGPLAN Notices, 2013, 48(6): 423–434. [doi: 10.1145/2499370.2462191]
    [36] Liang DL, Harrold MJ. Efficient points-to analysis for whole-program analysis. In: Proc. of the 7th ACM SIGSOFT Symp. on Foundations of Software Engineering. Toulouse: Springer, 1999. 199–215. [doi: 10.1007/3-540-48166-4_13]
    [37] Lattner C, Lenharth A, Adve V. Making context-sensitive points-to analysis with heap cloning practical for the real world. ACM SIGPLAN Notices, 2007, 42(6): 278–289. [doi: 10.1145/1273442.1250766]
    [38] O’Callahan R. Generalized aliasing as a basis for program analysis tools [Ph.D. Thesis]. Pittsburgh: Carnegie Mellon University, 2001.
    [39] Feng Y, Wang XY, Dillig I, Dillig T. Bottom-up context-sensitive pointer analysis for Java. In: Proc. of the 13th Asian Symp. on Programming Languages and Systems. Springer, 2015. 465–484. [doi: 10.1007/978-3-319-26529-2_25]
    [40] Xu GQ, Rountev A. Merging equivalent contexts for scalable heap-cloning-based context-sensitive points-to analysis. In: Proc. of the 2008 Int’l Symp. on Software Testing and Analysis. Seattle: ACM, 2008. 225–236. [doi: 10.1145/1390630.1390658]
    [41] Li Q, Zhao JH, Li XD. Optimize context-sensitive Andersen-style points-To analysis by method summarization and cycle-elimination. In: Proc. of the 4th Int’l Symp. on Leveraging Applications of Formal Methods, Verification and Validation. Heraklion: Springer, 2010. 564–578. [doi: 10.1007/978-3-642-16558-0_46]
    [42] 李倩, 汤恩义, 戴雪峰, 王林章, 赵建华. Java指针指向分析优化. 软件学报, 2011, 22(6): 1140-1154. http://www.jos.org.cn/1000-9825/4025.htm
    Li Q, Tang E Y, Dai XF, Wang LZ, Zhao JH. Optimization of points-to analysis for Java. Ruan Jian Xue Bao/Journal of Software, 2011, 22(6): 1140-1154 (in Chinese with English abstract). http://www.jos.org.cn/1000-9825/4025.htm
    [43] Mangal R, Naik M, Yang H. A correspondence between two approaches to interprocedural analysis in the presence of join. In: Proc. of the 23rd European Symp. on Programming Languages and Systems. Grenoble: Springer, 2014. 513–533. [doi: 10.1007/978-3-642-54833-8_27]
    [44] Kanvar V, Khedker UP. Heap abstractions for static analysis. ACM Computing Surveys, 2016, 49(2): 29. [doi: 10.1145/2931098]
    [45] Lerch J, Hermann B, Bodden E, Mezini M. FlowTwist: Efficient context-sensitive inside-out taint analysis for large codebases. In: Proc. of the 22nd ACM SIGSOFT Int’l Symp. on Foundations of Software Engineering. Hong Kong: ACM, 2014. 98–108. [doi: 10.1145/2635868.2635878]
    [46] Arzt S, Rasthofer S, Fritz C, Bodden E, Bartel A, Klein J, Traon YL, Octeau D, McDaniel P. FlowDroid: Precise context, flow, field, object-sensitive and lifecycle-aware taint analysis for Android apps. ACM SIGPLAN Notices, 2014, 49(6): 259–269.
    [47] Späth J, Ali K, Bodden E. IDEal: Efficient and precise alias-aware dataflow analysis. Proceedings of the ACM on Programming Languages, 2017, 1(OOPSLA): 99. [doi: 10.1145/3133923] (查阅所有网上资料, 请联系作者确认期号信息)
    [48] Sridharan M, Chandra S, Dolby J, Fink SJ, Yahav E. Alias analysis for object-oriented programs. In: Clarke D, Noble J, Wrigstad T, eds. Aliasing in Object-oriented Programming. Types, Analysis and Verification. Berlin, Heidelberg: Springer, 2013. 196–232. [doi: 10.1007/978-3-642-36946-9_8]
    [49] Wu DY, Gao DB, Deng RH, Chang RKC. When program analysis meets bytecode search: Targeted and efficient inter-procedural analysis of modern android apps in BackDroid. arXiv: 2005.11527, 2020.
    [50] Reps T. Program analysis via graph reachability. Information and Software Technology, 1998, 40(11–12): 701–726. [doi: 10.1016/S0950-5849(98)00093-7]
    [51] Reps T, Horwitz S, Sagiv M. Precise interprocedural dataflow analysis via graph reachability. In: Proc. of the 22nd ACM SIGPLAN-SIGACT Symp. on Principles of Programming Languages. San Francisco: ACM, 1995. 49–61. [doi: 10.1145/199448.199462]
    [52] Heintze N, Tardieu O. Demand-driven pointer analysis. ACM SIGPLAN Notices, 2001, 36(5): 24–34. [doi: 10.1145/381694.378802]
    [53] Zheng X, Rugina R. Demand-driven alias analysis for C. ACM SIGPLAN Notices, 2008, 43(1): 197–208. [doi: 10.1145/1328897.1328464]
    [54] Lam MS, Whaley J, Livshits VB, Martin MC, Avots D, Carbin C, Unkel C. Context-sensitive program analysis as database queries. In: Proc. of the 24th ACM SIGMOD-SIGACT-SIGART Symp. on Principles of Database Systems. Baltimore: ACM, 2005. 1–12. [doi: 10.1145/1065167.1065169]
    [55] Bravenboer M, Smaragdakis Y. Strictly declarative specification of sophisticated points-to analyses. ACM SIGPLAN Notices, 2009, 44(10): 243–262. [doi: 10.1145/1639949.1640108]
    [56] Smaragdakis Y, Bravenboer M. Using datalog for fast and easy program analysis. In: Proc. of the 1st Int’l Datalog 2.0 Workshop. Oxford: Springer, 2010. 245–251. [doi: 10.1007/978-3-642-24206-9_14]
    [57] Smaragdakis Y, Balatsouras G. Pointer analysis. Foundations and Trends in Programming Languages, 2015, 2(1): 1–69.
    [58] Naik M. Chord: A program analysis platform for Java. 2006.
    [59] Petablox. https://github.com/petablox/petablox
    [60] Zhu JW. Symbolic pointer analysis. In: Proc. of the 2002 IEEE/ACM Int’l Conf. on Computer-aided Design. San Jose: ACM, 2002. 150–157. [doi: 10.1145/774572.774594]
    [61] Zhu JW, Calman S. Symbolic pointer analysis revisited. ACM SIGPLAN Notices, 2004, 39(6): 145–157. [doi: 10.1145/996893.996860]
    [62] Whaley J, Lam M S. Cloning-based context-sensitive pointer alias analysis using binary decision diagrams. ACM SIGPLAN Notices, 2004, 39(6): 131–144. [doi: 10.1145/996893.996859]
    [63] Lhoták O, Curial S, Amaral JN. Using ZBDDs in points-to analysis. In: Proc. of the 20th Int’l Workshop on Languages and Compilers for Parallel Computing. Urbana: Springer, 2007. 338–352. [doi: 10.1007/978-3-540-85261-2_23]
    [64] Lhoták O, Curial S, Amaral JN. Using XBDDs and ZBDDs in points‐to analysis. Software: Practice and Experience, 2009, 39(2): 163-188. [doi: 10.1002/spe.895]
    [65] Whaley J, Avots D, Carbin M, Lam MS. Using datalog with binary decision diagrams for program analysis. In: Proc. of the 3rd Asian Symp. on Programming Languages and Systems. Tsukuba: Springer, 2005. 97–118. [doi: 10.1007/11575467_8]
    [66] Xiao X, Zhang C. Geometric encoding: Forging the high performance context sensitive points-to analysis for Java. In: Proc. of the 2011 Int’l Symp. on Software Testing and Analysis. Toronto: ACM, 2011. 188–198. [doi: 10.1145/2001420.2001443]
    [67] Naeem NA, Lhoták O. Faster alias set analysis using summaries. In: Proc. of the 20th Int’l Conf. on Compiler Construction. Saarbrücken: Springer, 2011. 82–103. [doi: 10.1007/978-3-642-19861-8_6]
    [68] Ali K, Lhoták O. Averroes: Whole-program analysis without the whole program. In: Proc. of the 27th European Conf. on Object-oriented Programming. Montpellier: Springer, 2013. 378–400. [doi: 10.1007/978-3-642-39038-8_16]
    [69] Ali K, Lhoták O. Application-only call graph construction. In: Proc. of the 26th European Conf. on Object-Oriented Programming. Beijing: Springer, 2012. 688–712. [doi: 10.1007/978-3-642-31057-7_30]
    [70] Kulkarni S, Mangal R, Zhang X, Naik M. Accelerating program analyses by cross-program training. ACM SIGPLAN Notices, 2016, 51(10): 359–377. [doi: 10.1145/3022671.2984023]
    [71] Madhavan R, Ramalingam G, Vaswani K. Modular heap analysis for higher-order programs. In: Proc. of the 19th Int’l Static Analysis Symp. Deauville: Springer, 2012. 370–387. [doi: 10.1007/978-3-642-33125-1_25]
    [72] Tang H, Wang D, Xiong YF, Zhang LM, Wang XY, Zhang L. Conditional Dyck-CFL reachability analysis for complete and efficient library summarization. In: Proc. of the 26th European Symp. on Programming. Uppsala: Springer, 2017. 880–908. [doi: 10.1007/978-3-662-54434-1_33]
    [73] Smaragdakis Y, Kastrinis G, Balatsouras G. Introspective analysis: Context-sensitivity, across the board. ACM SIGPLAN Notices, 2014, 49(6): 485–495. [doi: 10.1145/2666356.2594320]
    [74] Hassanshahi B, Ramesh RK, Krishnan P, Scholz B, Lu Y. An efficient tunable selective points-to analysis for large codebases. In: Proc. of the 6th ACM SIGPLAN Int’l Workshop on State of the Art in Program Analysis. Barcelona: ACM, 2017. 13–18. [doi: 10.1145/3088515.3088519]
    [75] Liang P, Tripp O, Naik M. Learning minimal abstractions. ACM SIGPLAN Notices, 2011, 46(1): 31–42. [doi: 10.1145/1925844.1926391]
    [76] Jeong S, Jeon M, Cha S, Oh H. Data-driven context-sensitivity for points-to analysis. Proceedings of the ACM on Programming Languages, 2017, 1(OOPSLA): 100. [doi: 10.1145/3133924] (查阅所有网上资料, 请联系作者确认期号信息)
    [77] Jeon M, Jeong S, Oh H. Precise and scalable points-to analysis via data-driven context tunneling. Proceedings of the ACM on Programming Languages, 2018, 2(OOPSLA): 140. [doi: 10.1145/3276510] (查阅所有网上资料, 请联系作者确认期号信息)
    [78] Li Y, Tan T, Møller A, Smaragdakis Y. Precision-guided context sensitivity for pointer analysis. Proceedings of the ACM on Programming Languages, 2018, 2(OOPSLA): 141. [doi: 10.1145/3276511] (查阅所有网上资料, 请联系作者确认期号信息)
    [79] Li Y, Tan T, Møller A, Smaragdakis Y. Scalability-first pointer analysis with self-tuning context-sensitivity. In: Proc. of the 26th ACM Joint Meeting on European Software Engineering Conf. and Symp. on the Foundations of Software Engineering. Lake Buena Vista: ACM, 2018. 129–140. [doi: 10.1145/3236024.3236041]
    [80] Tan T, Li Y, Xue JL. Making k-object-sensitive pointer analysis more precise with still k-limiting. In: Proc. of the 23rd Int’l Static Analysis Symp. Edinburgh: Springer, 2016. 489–510. [doi: 10.1007/978-3-662-53413-7_24]
    [81] Sridharan M, Gopan D, Shan LX, Bodík R. Demand-driven points-to analysis for Java. ACM SIGPLAN Notices, 2005, 40(10): 59–76. [doi: 10.1145/1103845.1094817]
    [82] Sridharan M, Bodík R. Refinement-based context-sensitive points-to analysis for Java. ACM SIGPLAN Notices, 2006, 41(6): 387–400. [doi: 10.1145/1133255.1134027]
    [83] Xu GQ, Rountev A, Sridharan M. Scaling CFL-reachability-based points-to analysis using context-sensitive must-not-alias analysis. In: Proc. of the 23rd European Conf. on Object-oriented Programming. Genoa: Springer, 2009. 98–122. [doi: 10.1007/978-3-642-03013-0_6]
    [84] Yan DC, Xu GQ, Rountev A. Demand-driven context-sensitive alias analysis for Java. In: Proc. of the 2011 Int’l Symp. on Software Testing and Analysis. Toronto: ACM, 2011. 155–165. [doi: 10.1145/2001420.2001440]
    [85] Shang L, Xie XW, Xue JL. On-demand dynamic summary-based points-to analysis. In: Proc. of the 10th Int’l Symp. on Code Generation and Optimization. San Jose: ACM, 2012. 264–274. [doi: 10.1145/2259016.2259050]
    [86] Naeem NA, Lhoták O, Rodriguez J. Practical extensions to the IFDS algorithm. In: Proc. of the 19th Int’l Conf. on Compiler Construction. Paphos: Springer, 2010. 124–144. [doi: 10.1007/978-3-642-11970-5_8]
    [87] Sagiv M, Reps T, Horwitz S. Precise interprocedural dataflow analysis with applications to constant propagation. Theoretical Computer Science, 1996, 167(1–2): 131–170. [doi: 10.1016/0304-3975(96)00072-2]
    [88] Guyer SZ, Lin C. Client-driven pointer analysis. In: Proc. of the 10th Int’l Static Analysis Symp. San Diego: Springer, 2003. 214–236. [doi: 10.1007/3-540-44898-5_12]
    [89] Zhang X, Mangal R, Grigore R, Naik M, Yang H. On abstraction refinement for program analyses in Datalog. ACM SIGPLAN Notices, 2014, 49(6): 239–248. [doi: 10.1145/2666356.2594327]
    [90] Allen N, Scholz B, Krishnan P. Staged points-to analysis for large code bases. In: Proc. of the 24th Int’l Conf. on Compiler Construction. London: Springer, 2015. 131–150. [doi: 10.1007/978-3-662-46663-6_7]
    [91] Rama GM, Komondoor R, Sharma H. Refinement in object-sensitivity points-to analysis via slicing. Proceedings of the ACM on Programming Languages, 2018, 2(OOPSLA): 142. [doi: 10.1145/3276512] (查阅所有网上资料, 请联系作者确认期号信息)
    [92] Sun CG, Midkiff S. Demand-driven refinement of points-to analysis. In: Proc. of the 41st Int’l Conf. on Software Engineering: Companion Proc. Montreal: IEEE, 2019. 264–265. [doi: 10.1109/ICSE-Companion.2019.00106]
    [93] Liang P, Naik M. Scaling abstraction refinement via pruning. ACM SIGPLAN Notices, 2011, 46(6): 590–601. (查阅所有网上资料, 未找到本条文献信息, 请联系作者确认)
    [94] Tan T, Li Y, Xue JL. Efficient and precise points-to analysis: Modeling the heap by merging equivalent automata. ACM SIGPLAN Notices, 2017, 52(6): 278–291. [doi: 10.1145/3140587.3062360]
    [95] Hirzel M, Von Dincklage D, Diwan A, Hind M. Fast online pointer analysis. ACM Transactions on Programming Languages and Systems, 2007, 29(2): 11. [doi: 10.1145/1216374.1216379]
    [96] Shang L, Lu Y, Xue JL. Fast and precise points-to analysis with incremental CFL-reachability summarisation: Preliminary experience. In: Proc. of the 27th IEEE/ACM Int’l Conf. on Automated Software Engineering. Essen: ACM, 2012. 270–273. [doi: 10.1145/2351676.2351720]
    [97] Lu Y, Shang L, Xie XW, Xue JL. An incremental points-to analysis with CFL-reachability. In: Proc. of the 22nd Int’l Conf. on Compiler Construction. Rome: Springer, 2013. 61–81. [doi: 10.1007/978-3-642-37051-9_4]
    [98] Vivien F, Rinard M. Incrementalized pointer and escape analysis. In: Proc. of the ACM SIGPLAN 2001 Conf. on Programming Language Design and Implementation. Snowbird: ACM, 2001. 35–46. [doi: 10.1145/378795.378804]
    [99] Whaley J, Rinard M. Compositional pointer and escape analysis for Java programs. ACM SIGPLAN Notices, 1999, 34(10): 187–206. [doi: 10.1145/320385.320400]
    [100] Li X, Ogawa M. An ahead-of-time yet context-sensitive points-to analysis for Java. Electronic Notes in Theoretical Computer Science, 2009, 253(5): 31–46. [doi: 10.1016/j.entcs.2009.11.013]
    [101] Li X, Ogawa M. Stacking-based context-sensitive points-to analysis for Java. In: Proc. of the 5th Int’l Haifa Verification Conf. on Hardware and Software: Verification and Testing. Haifa: Springer, 2009. 133–149.
    [102] Späth J, Ali K, Bodden E. Context-, flow-, and field-sensitive data-flow analysis using synchronized Pushdown systems. Proceedings of the ACM on Programming Languages, 2019, 3(POPL): 48. [doi: 10.1145/3290361] (查阅所有网上资料, 请联系作者确认期号信息)
    [103] Li X, Ogawa M. Conditional weighted pushdown systems and applications. In: Proc. of the 2010 ACM SIGPLAN Workshop on Partial Evaluation and Program Manipulation. Madrid: ACM, 2010. 141–150. [doi: 10.1145/1706356.1706382]
    [104] Zhang QR, Su ZD. Context-sensitive data-dependence analysis via linear conjunctive language reachability. ACM SIGPLAN Notices, 2017, 52(1): 344–358. (查阅所有网上资料, 未找到本条文献信息, 请联系作者确认)
    [105] Wang K, Hussain A, Zuo ZQ, Xu GQ, Sani AA. Graspan: A single-machine disk-based graph system for interprocedural static analyses of large-scale systems code. ACM SIGOPS Operating Systems Review, 2017, 51(2): 389–404.
    [106] Zhang QR, Lyu MR, Yuan H, Su ZD. Fast algorithms for Dyck-CFL-reachability with applications to alias analysis. ACM SIGPLAN Notices, 2013, 48(6): 435–446. [doi: 10.1145/2499370.2462159]
    [107] Thiessen R, Lhoták O. Context transformations for pointer analysis. ACM SIGPLAN Notices, 2017, 52(6): 263–277. [doi: 10.1145/3140587.3062359]
    [108] Hollingum N, Scholz B. Towards a scalable framework for context-free language reachability. In: Proc. of the 24th Int’l Conf. on Compiler Construction. London: Springer, 2015. 193–211. [doi: 10.1007/978-3-662-46663-6_10]
    [109] Thakur M, Nandivada V K. Compare less, defer more: Scaling value-contexts based whole-program heap analyses. In: Proc. of the 28th Int’l Conf. on Compiler Construction. Washington: ACM, 2019. 135–146. [doi: 10.1145/3302516.3307359]
    [110] Milanova A. Light context-sensitive points-to analysis for Java. In: Proc. of the 7th ACM SIGPLAN-SIGSOFT Workshop on Program Analysis for Software Tools and Engineering. San Diego: ACM, 2007. 25–30. [doi: 10.1145/1251535.1251540]
    [111] Méndez-Lojo M, Mathew A, Pingali K. Parallel inclusion-based points-to analysis. In: Proc. of the ACM Int’l Conf. on Object Oriented Programming Systems Languages and Applications. Reno: ACM, 2010. 428–443. [doi: 10.1145/1869459.1869495]
    [112] Putta S, Nasre R. Parallel replication-based points-to analysis. In Proc. of the 21st Int’l Conf. on Compiler Construction. Tallinn: Springer, 2012. 61–80. [doi: 10.1007/978-3-642-28652-0_4]
    [113] Su Y, Ye D, Xue JL, Liao XK. An efficient GPU implementation of inclusion-based pointer analysis. IEEE Transactions on Parallel and Distributed Systems, 2016, 27(2): 353–366. [doi: 10.1109/TPDS.2015.2397933]
    [114] Mendez-Lojo M, Burtscher M, Pingali K. A GPU implementation of inclusion-based points-to analysis. In: Proc. of the 17th ACM SIGPLAN Symp. on Principles and Practice of Parallel Programming. New Orleans: ACM, 2012. 107–116. [doi: 10.1145/2145816.2145831]
    [115] Su Y, Ye D, Xue JL. Accelerating inclusion-based pointer analysis on heterogeneous CPU-GPU systems. In: Proc. of the 20th Int’l Conf. on High Performance Computing. Bengaluru: IEEE, 2013. 149–158. [doi: 10.1109/HiPC.2013.6799110]
    [116] Smaragdakis Y, Balatsouras G, Kastrinis G. Set-based pre-processing for points-to analysis. In: Proc. of the 2013 ACM SIGPLAN Int’l Conf. on Object Oriented Programming Systems Languages & Applications. Indianapolis: Association for Computing Machinery, 2013. 253–270. [doi: 10.1145/2509136.2509524]
    [117] 陈聪明, 霍玮, 于洪涛, 冯晓兵. 基于包含的指针分析优化技术综述. 计算机学报, 2011, 34(7): 1224–1238. [doi: 10.3724/SP.J.1016.2011.01224]
    Chen CM, Huo W, Yu HT, Feng XB. A survey of optimization technology of inclusion-based pointer analysis. Chinese Journal of Computers, 2011, 34(7): 1224–1238 (in Chinese with English abstract). [doi: 10.3724/SP.J.1016.2011.01224]
    [118] Balatsouras G, Ferles K, Kastrinis G, Smaragdakis Y. A Datalog model of must-alias analysis. In: Proc. of the 6th ACM SIGPLAN Int’l Workshop on State of the Art in Program Analysis. Barcelona: ACM, 2017. 7–12. [doi: 10.1145/3088515.3088517]
    [119] Deutsch A. Interprocedural may-alias analysis for pointers: Beyond k-limiting. ACM SIGPLAN Notices, 1994, 29(6): 230–241. [doi: 10.1145/773473.178263]
    [120] Khedker U P, Sanyal A, Karkare A. Heap reference analysis using access graphs. ACM Transactions on Programming Languages and Systems, 2007, 30(1): 1–40. [doi: 10.1145/1290520.1290521] (查阅所有网上资料, 请联系作者核对页码信息)
    [121] Kastrinis G, Balatsouras G, Ferles K, Prokopaki-Kostopoulou N, Smaragdakis Y. An efficient data structure for must-alias analysis. In: Proc. of the 27th Int’l Conf. on Compiler Construction. Vienna: ACM, 2018: 48–58. [doi: 10.1145/3178372.3179519]
    [122] Landi W, Ryder BG, Zhang S. Interprocedural modification side effect analysis with pointer aliasing. In: Proc. of the ACM SIGPLAN 1993 Conf. on Programming Language Design and Implementation. Albuquerque: ACM, 1993. 56–67. [doi: 10.1145/155090.155096]
    [123] Diwan A, McKinley KS, Moss JEB. Type-based alias analysis. ACM SIGPLAN Notices, 1998, 33(5): 106–117. [doi: 10.1145/277652.277670]
    Cited by
    Comments
    Comments
    分享到微博
    Submit
Get Citation

李昊峰,孟海宁,郑恒杰,曹立庆,李炼.面向对象程序的上下文敏感指针分析研究.软件学报,2022,33(1):78-101

Copy
Share
Article Metrics
  • Abstract:2085
  • PDF: 5978
  • HTML: 5471
  • Cited by: 0
History
  • Received:November 27,2019
  • Revised:September 12,2020
  • Online: May 21,2021
  • Published: January 06,2022
Links:Institute of Software, CASChina Computer FederationCASNSFC
You are the first2044763Visitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address：4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code：100190
Phone：010-62562563 Fax：010-62562533 Email：jos@iscas.ac.cn
Technical Support：Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063