Points-To Analysis

The Flow-Insensitive Representation

• AssignmentIF : A flow-insensitive representation of a program is a set of AssignmentIF. An AssignmentIF instance represents an assignment in the program which is one of the following forms:
  • Base: lhs = &rhs
  • Simple: lhs = rhs
  • Complex 1: *lhs = rhs
  • Complex 2: lhs = *rhs

For the case of *lhs = *rhs , an auxiliary variable tmp is introduced: tmp = *rhs , *rhs = tmp .

For now, structs and array elements are all invisible for the flow-insensitive representation: so expr.id is abstracted to expr; expr->id is abstracted to *expr; a[I] is abstracted to a; *(p + i), where I is an integer, is abstracted to *p.

For the case of lhs = a op b (or *lhs = a op b), it is abstracted to lhs = a (or *lhs = a) and lhs = b (or *lhs = b)

Intra-Procedural Points-To Analysis

• Reference : Ben Hardekopf & Calvin Lin "The ant and the grasshopper: fast and accurate pointer analysis for millions of lines of code"
• PointsToGraph : A points-to graph represents an over-approximation of "what pointers are point to" information in a function.
  • In the graph, nodes are the objects that are reachable from the function associated with the points-to graph.
  • The graph also maintains a set of objects, which is the "points-to set" of a node, for every node.
  • In the graph, edges are the subset-of relations between different nodes.
  • A client of PointsToGraph can
    1. ask answers for the question "what a variable points to ?"
    2. add additional points-to information to the graph. Modification to a graph will cause a re-computation of the graph.

Inter-Procedural Points-To Analysis

• Reference: Emami, Maryam and Ghiya, Rakesh and Hendren, Laurie J. "Context-sensitive inter-procedural points-to analysis in the presence of function pointers"
• InvocationGraphNode

Read / Write Analysis