上下文敏感的横向传播方法.pdf

【上下文敏感的横向传播方法】是一种用于程序静态分析的技术，特别关注于指针分析的效率和准确性。指针分析是静态分析的核心部分，旨在确定程序中的指针可能指向哪些内存对象。传统的上下文无关指针分析方法可以区分不同调用点的相同函数，但可能无法完全捕捉到上下文敏感的信息。 在高度上下文敏感的指针分析中，二元决策图虽然在性能上有优势，但因未执行预定义约束而在扩展性方面存在局限。相比之下，Woongsik Choi等人的工作通过在调用图上进行上下文敏感的指针分析并结合环消除算法，实现了较高的上下文敏感性和可扩展性。然而，这种算法在时间效率方面仍有提升空间。 近年来，针对包含的指针分析改进算法不断涌现，其中Fahndrich、Pearce、Harderkopf和Pereira等人提出的基于约束图的环消除算法各有特色。Pereira的横向传播算法（Wave Propagation，WP）尤为突出，它优化了时间和空间效率，提高了分析的精度。 本文主要贡献在于提出了一种新的上下文敏感的横向传播算法，该算法采用最新的基于包含的指针分析在线改进技术。文章定义了新约束图并进行了初始化。接着，通过实例展示该算法如何精确有效地进行上下文敏感的指针分析。使用CIL（Common Intermediate Language）工具和OCaml语言实现该算法，并对包含20,000到290,000行代码的六个程序进行分析，结果显示，上下文敏感的横向传播算法在处理大规模程序时，相比于环消除算法，平均节省了大约9秒的时间。 该研究对于解决基于调用图的上下文敏感指针分析的时间效率问题具有重要意义，为程序静态分析提供了更为高效的方法。同时，其在CIL框架下的实现也证明了该算法的可行性与实用性，有助于推动安全关键软件测试验证和程序静态分析领域的发展。 关键词：在线改进；横向传播；调用图；上下文敏感指针分析；环消除；约束图