微信服务号

微信订阅号

2025年5月11日 13:58 星期日
首页 > 过刊浏览>2022年第33卷第1期 >78-101. DOI:10.13328/j.cnki.jos.006345
PDF HTML阅读 XML下载 导出引用 引用提醒
面向对象程序的上下文敏感指针分析研究
作者:
作者简介:

李昊峰(1994－), 男, 博士生, CCF学生会员，主要研究领域为程序分析.
孟海宁(1995－), 女, 博士生, CCF学生会员，主要研究领域为程序分析.
郑恒杰(1996－), 男, 硕士, 主要研究领域为程序分析.
曹立庆(1997－), 男, 博士生, CCF学生会员, 主要研究领域为程序分析.
李炼(1977－), 男, 博士, 研究员，博士生导师, CCF专业会员, 主要研究领域为程序分析, 软件安全.

通讯作者:

李炼，lianli@ict.ac.cn

中图分类号:

TP311

基金项目:

国家自然科学基金 (61872043)


Context-sensitive Pointer Analysis for Object-oriented Programs: A Systematic Literature Review
Author:
Fund Project:

National Natural Science Foundation of China (61872043)

  • 摘要
    • | |
  • 访问统计
    • |
  • 参考文献 [125]
    • |
  • 相似文献 [20]
    • | | |
  • 文章评论
    摘要:

    指针分析是编译优化、程序静态分析中的基础, 很多应用都需要基于指针分析, 低精度的指针分析会给这些应用带来高误报率和漏报率, 通过添加上下文敏感信息是提高指针分析的精度的一个重要手段. 自从面向对象的概念被提出来之后, 该概念得到了广泛的应用, Java、C++、.NET、C#等主流语言都支持面向对象的特性, 面向对象程序的指针分析越来越受关注. 做了一个系统文献综述(SLR), 通过对索引到的相关文献进行分析和归类, 总结了面向对象程序的上下文敏感指针分析研究的5个主要问题, 并对这5个问题中用到的方法进行了分析讨论.

    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.

    参考文献
    [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]
    引证文献
    网友评论
    网友评论
    分享到微博
    发 布
引用本文

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

复制
分享
文章指标
  • 点击次数:2083
  • 下载次数: 5961
  • HTML阅读次数: 5456
  • 引用次数: 0
历史
  • 收稿日期:2019-11-27
  • 最后修改日期:2020-09-12
  • 在线发布日期: 2021-05-21
  • 出版日期: 2022-01-06
文章二维码
友情链接:中国科学院软件研究所中国计算机学会中国科学院国家自然科学基金委员会CCF数字图书馆Int'l J of Softw Info计算机系统应用
您是第19923337位访问者
版权所有：中国科学院软件研究所 京ICP备05046678号-3
地址：北京市海淀区中关村南四街4号,邮政编码：100190
电话：010-62562563 传真：010-62562533 Email：jos@iscas.ac.cn
技术支持：北京勤云科技发展有限公司

京公网安备 11040202500063号