Static-Analysis 12-Pointer Analysis Context Sensitivity II
重点 * 上下文敏感指针分析的完整算法。 * 上下文敏感概念,堆对象的上下文敏感表示,上下文敏感指针分析的规则。 * 上下文的三种选择,以及效率、准确度的对比。
重点 * 上下文敏感指针分析的完整算法。 * 上下文敏感概念,堆对象的上下文敏感表示,上下文敏感指针分析的规则。 * 上下文的三种选择,以及效率、准确度的对比。
什么原因导致了上下文不敏感分析的低精度: - 1. 在动态执行时,对同一个函数的不同调用,往往有着不同的调用上下文(calling contexts),如上一小节的例子中两次对 id 的调用。 - 2. 不同的调用上下文会被混合并传播,进而形成假的数据流。如上一小节的例子中指针 x 和 y 指向两个目标。
承接上一节课程,本文谈谈包含指针分析如何处理函数调用。接下来用指针分析的方式来构建 Call graph。 本课将给出一个包含函数间分析的适用于全程序的算法。
指针分析是在指针间**传递**指向关系。最开始的指向关系都来自于 `new` 语句。 指针分析的关键:当 $pt(x)$ 变化时,也要更新 $x$ 相关的其他指针
目标:分析程序指针可以指向哪些对象 说明:指针分析属于 may analysis,分析的结果是某指针所有可能指向哪些对象,是个 over-approximation 集合。
此前我们讨论的问题都是过程内的,也就是不涉及到方法调用。然而实际程序中方法调用屡见不鲜,继续采用之前的分析方法会丢失精度,这也就是为什么我们需要过程 (间) 分析。
理解函数视角下的迭代算法 对于 lattice 和 complete lattice 的定义 理解不动点定理 知道如何用 lattice 来概述 may 和 must analysis MOP与迭代算法结果之间的关系 常量传播分析 Worklist 算法
重点 Understand the three data flow analyses: reaching definitions live variables available expressions Can tell the differences and similarities of the three data flow analyses Understand the iterative algorithm and can tell why it is able to terminate
重点Compiler and Static AnalysisAST vs. IR3AC ( 三地址码 )Soot: Real Static AnalyzerDo-While LoopMethod CallSSA (Static Single Assignment)Control Flow Analy
本文参考:『南京大学-软件分析』课程笔记 - Theoyu重点What are the differences between static analysis and (dynamic) testing?Understand soundness, completeness, false negati