南京大学李樾、谭添提出新的上下文敏感技术,突破指针分析高效精准的瓶颈

发稿时间:2020-05-22浏览次数:1398

程序分析是保障大规模复杂软件可靠性、安全性、性能等质量指标的关键技术,而指针分析是为程序分析搭建脚手架的基础,几乎所有全程序分析都要依赖于指针分析的结果,如何使得指针分析运行的更快且准确一直是过去40年来该领域公认的研究重点和难点。上下文敏感技术是提升指针分析精度的关键技术,在过去的30年来一直是指针分析方向的学术热点,然而上下文敏感技术给指针分析带来精度提升的同时又带来性能上的很大开销。


计算机软件新技术国家重点实验室、南京大学计算机科学与技术系李樾副教授、谭添助理研究员提出了一项新的选择性上下文敏感技术。该技术将程序中会影响指针分析精度和速度的方法分别定义为精度关键与速度关键方法,并提供了一套理论框架用于有效识别这些关键方法,最终基于一套可解释规则选择为其中哪些关键方法应用上下文,以获得高效、精准的指针分析。


大量实验表明,该技术可大幅度加速指针分析,平均情况下,在保留通用上下文敏感指针分析95%精度的同时可加速25.5倍(最快可加速88倍之多)。此外,对于一些复杂程序,该技术可在取得上下文敏感精度的同时,运行速度甚至能超越非上下文敏感,打破了过去30年指针分析只能在二者之间取舍平衡的局面,改变了关于“上下文敏感指针分析速度无法超越非上下文敏感技术”的认识,为未来快速精准指针分析的研究提供了新的思路和方向。


该成果在2020520日,以“A Principled Approach to Selective Context Sensitivity for Pointer Analysis”为题发表于《ACM Transactions on Programming Languages and Systems》期刊上(TOPLAS 42(2)),南京大学为第一及通讯单位,李樾为第一作者,谭添为通讯作者,丹麦奥胡斯大学Anders Møller教授、希腊雅典大学Yannis Smaragdakis教授为合作者。TOPLAS是程序设计语言领域的顶级国际期刊,也是CCF推荐A类期刊。该论文是TOPLAS自1979年创刊41年来,南京大学首次、我国内地高校和科研机构第三次(近五年唯一)以第一单位名义发表的科研成果。


值得一提的是,该项工作得到“华为-南大下一代程序设计创新实验室”合作项目支持,成果将助力华为公司在关键领域自主创新。




李樾,南京大学计算机科学与技术系副教授(登峰B计划引进),2016年博士毕业于澳大利亚新南威尔士大学,之后先后在新南威尔士大学和丹麦奥胡斯大学从事博士后研究工作。




谭添,南京大学计算机科学与技术系助理研究员,2017年博士毕业于澳大利亚新南威尔士大学,2017-2019年在丹麦奥胡斯大学从事博士后研究工作。



李樾和谭添于20199月共同加入南京大学计算机科学与技术系,隶属于计算机软件研究所团队,研究方向为程序设计语言与程序分析,他们在程序设计语言相关会议和期刊,如TOPLASPLDIOOPSLAECOOPSASFSETOSEM等发表文章。曾获ECOOP 2016 杰出论文奖、CGO 2013最佳论文奖和ISSRE 2017最佳论文提名,曾担任POPLTOPLASTOSEM等会议和期刊审稿人。



论文链接:https://dl.acm.org/doi/10.1145/3381915