《程序静态分析》 - 南京大学 李樾、谭添

课程笔记

<aside> 💡 从个人角度来说我不太想花太多精力在程序分析上面，所以记得笔记大多是为了以后能快速有个参考，写的和流水账一样。但经常参考别人的笔记的时候就会发现，有的人能够以更易于回忆理解的角度重构 PPT 里的内容，并能重点突出地提炼出其中的精华。 这里给出一个不错的博客地址，有很多地方可以向 Fernweh 哥继续学习。

</aside>

Pointer Analysis Introduction

<aside> 💡 “Pointer analysis is one of the most fundamental static program analyses, on which virtually all others are built.”

</aside>

Introduction

Pointer analysis is a fundamental static analysis for object-oriented programs and is regarded as a may-analysis.

Two closely related but different concepts:

• Pointer analysis: which objects a pointer can point to?
• Alias analysis: can two pointers point to the same object?

Key Factors in Pointer Analysis

• Heap Abstraction

  To ensure termination, heap abstraction models dynamically allocated, unbounded concrete objects as finite abstract objects for static analysis

  • Allocation-site: One abstract object per allocation site

• Context Sensitivity

  • Context-sensitive: Distinguish different calling contexts of a method, Analyze each method multiple times, once for each context
  • Context-insensitive (more precise): Merge all calling contexts of a method and analyze each method once

• Flow sensitivity

  • Flow-sensitive: Respect the execution order of the statements. Maintain a map of points-to relations at each program location.

    The data analyses we implemented before are flow-sensitive.

  • Flow-insensitive (effective): Ignore the control-flow order, treat the program as a set of unordered statements, and Maintain one map of points-to relations for the whole program.

• Analysis Scope

  • Whole-program: Compute points-to information for all pointers in the program

  • Demand-driven: Only compute points-to information for the pointers that may affect specific sites of interest (on demand)

    This may lead to duplicate analysis when applying demand-driven analysis for multiple clients.

Concerned Statements

Pointers in JAVA

• Local variable: x

• Static field: C.f

  referred as global variable

• Instance field: x.f

• Array element: array[i]

  Ignore indexes. Modeled as an object (pointed by array) with a single field

We only focus on pointer-affecting statements

• New
• Assign
• Store
• Load
• Call (Virtual Call)

Rules

Domain and Notations

Variables: x, y ∈ V
Fields: f, g ∈ F
Objects: oi, oj ∈ O
Instance fields: oi.f, oj.g ∈ O × F
Pointers: Pointer = V ⋃ (O × F)

Points-to relation: pt : Pointer → 𝒫(O)

𝒫(O) denotes the powerset of O, pt(p) denotes the points-to set of p

Rules

For example: for x = y, it means for every Oi belongs to pt(y), add it to pt(x) also.