Points-to Analysis

This analysis computes the set of objects or components that a pointer can reference to. There are a lot of different categories of methods. The method described here is based on:

• flow-sensitive analysis: control-flow information is considered during analysis;
• context-sensitive analysis: when calling a function, values flow from one call through the function and return to another caller;
• heap modeling: objects named by allocation site
• aggregate modeling: elements of struct/array are distinguished

Definitions

• obj(p): the set of objects that p may reference to;
• obj(e): the set of objects that e may represent, where e has pointer type, or composite type of pointer type (e.g., array of pointers);

• Conditional Object Set of a pointer p:
  • cobj(p)={c0->O0, c1->O1, c2->O2, ...} where O1, O2, ... are all set of objects
  • c0->O0 denotes that when c0 is satisfied the objects set that p could refer to is O0

Expressions

let e be an expression, let le be an left-hand-side expression, let impact(e) be the set of impact memory units of e. letmu(e) be a function to convert an expression, of pointer type or being a left-hand-side expression, to a memory unit.

1. abstract function call: f(e0,e1, ...)

???

2. address-of: &le

obj(&le)={le}

3. array literal: {e0, e1, ...} where e0, .. e1 all have pointer types

obj({e0, e1, ...}) = obj(e0) U obj(e1) ...

4. pointer addition: e0 + e1

obj(e0 + e1) = offset(e0, e1)

5. cast expression: (T)e (where T is pointer type)

obj((T)e)=obj(e)

6. conditional expression: e0 ? e1 : e2

obj(e0 ? e1 : e2) = e0 ? obj(e1) : obj(e2)

7. dereference expression: *e where e has type pointer-to-pointer of T

obj(*e) = **???** the impact memory units of *e include the memory unit refers to by e, and the impact memory units of the sub-expressions of e. e.g., the impact memory units of *(p+i) is {mu(p+5), impact(i)}, because p is of pointer type and sub(p+i) is {i}.

8. dot expression: e.k where e.k has pointer type

obj(e.k) = {e.k}

9. subscript expression: ea[ei]

obj(ea[ei])={ea[ei]}

Sub-expressions

let e be an expression, let sub(e) be the set of sub-expressions of e.

1. abstract function call: f(e0,e1, ...)

sub(f(e0,e1, ...)) = {e0, e1, ...}

2. address-of: &le

sub(&le)={le} U sub(le)

3. array literal: {e0, e1, ...}

sub({e0, e1, ...}) = {e0, e1, ...}`

4. binary expression: e0 op e1 sub(e0 op e1) = e0.type== pointer ? {e1} : {e0, e1}

5. bound variable expression: eb

sub(eb)=\empty

6. cast expression: (T)e

sub((T)e)={e}