Pointer analysis

<h2 id="example">Example</h2>
<p>Consider the following C program:
</p>
int *id(int* p) {
  return p;
}
void main(void) {
  int x;
  int y;
  int *u = id(&x);
  int *v = id(&y);
}

<p>A pointer analysis computes a mapping from pointer expressions to a set of allocation sites of objects they may point to. For the above program, an idealized, fully precise analysis would compute the following results:
</p>
<table><tbody><tr><th>Pointer expression</th><th>Allocation site</th></tr><tr><td>&x</td><td>main::x</td></tr><tr><td>&y</td><td>main::y</td></tr><tr><td>u</td><td>main::x</td></tr><tr><td>v</td><td>main::y</td></tr><tr><td>p</td><td>main::x, main::y</td></tr></tbody></table>
<p>(Where X::Y represents the stack allocation holding the local variable Y in the function X.)
</p><p>However, a context-insensitive analysis such as Andersen's or Steensgaard's algorithm would lose precision when analyzing the calls to id, and compute the following result:
</p>
<table><tbody><tr><th>Pointer expression</th><th>Allocation site</th></tr><tr><td>&x</td><td>main::x</td></tr><tr><td>&y</td><td>main::y</td></tr><tr><td>u</td><td>main::x, main::y</td></tr><tr><td>v</td><td>main::x, main::y</td></tr><tr><td>p</td><td>main::x, main::y</td></tr></tbody></table>
<h2 id="introduction">Introduction</h2>
<p>As a form of static analysis, fully precise pointer analysis can be shown to be <a href="/facts/Undecidable_problem/QBxmXBbY">undecidable</a>.<a class="footnote-ref" id="fnref:1" href="#fn:1"><sup>1</sup></a> Most approaches are <a href="/facts/Soundness/ndpamd2A">sound</a>, but range widely in performance and precision. Many design decisions impact both the precision and performance of an analysis; often (but not always) lower precision yields higher performance. These choices include:<a class="footnote-ref" id="fnref:2" href="#fn:2"><sup>2</sup></a><a class="footnote-ref" id="fnref:3" href="#fn:3"><sup>3</sup></a>
</p>
<ul><li><i>Field sensitivity</i> (also known as <i>structure sensitivity</i>): An analysis can either treat each field of a <a href="/facts/Record_(computer_science)/1fvSgenB">struct</a> or <a href="/facts/Object_(computer_science)/eX99dtAw">object</a> separately, or merge them.</li>
<li><i>Array sensitivity</i>: An array-sensitive pointer analysis models each index in an array separately. Other choices include modelling just the first entry separately and the rest together, or merging all array entries.</li>
<li><i>Context sensitivity</i> or <i><a href="/facts/Polyvariance/f51CzLnK">polyvariance</a></i>: Pointer analyses may qualify points-to information with a summary of the control flow leading to each program point.</li>
<li><i>Flow sensitivity</i>: An analysis can model the impact of intraprocedural control flow on points-to facts.</li>
<li><i>Heap modeling</i>: Run-time allocations may be abstracted by:
<ul><li>their allocation sites (the statement or instruction that performs the allocation, e.g., a call to malloc or an object constructor),</li>
<li>a more complex model based on a <a href="/facts/Shape_analysis_(software)/EMHwTDrX">shape analysis</a>,</li>
<li>the type of the allocation, or</li>
<li>one single allocation (this is called <i>heap-insensitivity</i>).</li></ul></li>
<li><i>Heap cloning</i>: Heap- and context-sensitive analyses may further qualify each allocation site by a summary of the control flow leading to the instruction or statement performing the allocation.</li>
<li><i>Subset constraints</i> or <i>equality constraints</i>: When propagating points-to facts, different program statements may induce different constraints on a variable's points-to sets. Equality constraints (like those used in <a href="/facts/Steensgaard%27s_algorithm/SLkwXp5Q">Steensgaard's algorithm</a>) can be tracked with a <a href="/facts/Union-find_data_structure/QnFQNedE">union-find data structure</a>, leading to high performance at the expense of the precision of a subset-constraint based analysis (e.g., Andersen's algorithm).</li></ul>
<h2 id="context-insensitive-flow-insensitive-algorithms">Context-insensitive, flow-insensitive algorithms</h2>
<p>Pointer analysis algorithms are used to convert collected raw pointer usages (assignments of one pointer to another or assigning a pointer to point to another one) to a useful graph of what each pointer can point to.<a class="footnote-ref" id="fnref:4" href="#fn:4"><sup>4</sup></a> 
</p><p><a href="/facts/Steensgaard%27s_algorithm/SLkwXp5Q">Steensgaard's algorithm</a> and Andersen's algorithm are common context-insensitive, flow-insensitive algorithms for pointer analysis. They are often used in compilers, and have implementations in <a href="https://github.com/SVF-tools/SVF">SVF</a>
<a class="footnote-ref" id="fnref:5" href="#fn:5"><sup>5</sup></a>
and <a href="/facts/LLVM/nPmcspQN">LLVM</a>.
</p>
<h2 id="flow-insensitive-approaches">Flow-insensitive approaches</h2>
<p>Many approaches to flow-insensitive pointer analysis can be understood as forms of <a href="/facts/Abstract_interpretation/cj6wjzu1">abstract interpretation</a>, where heap allocations are abstracted by their allocation site (i.e., a program location).<a class="footnote-ref" id="fnref:6" href="#fn:6"><sup>6</sup></a>
</p>

<p>Many flow-insensitive algorithms are specified in <a href="/facts/Datalog/67jbYWDb">Datalog</a>, including those in the Soot analysis framework for Java.<a class="footnote-ref" id="fnref:7" href="#fn:7"><sup>7</sup></a>
</p><p>Context-sensitive, flow-sensitive algorithms achieve higher precision, generally at the cost of some performance, by analyzing each procedure several times, once per <i>context</i>.<a class="footnote-ref" id="fnref:8" href="#fn:8"><sup>8</sup></a> Most analyses use a "context-string" approach, where contexts consist of a list of entries (common choices of context entry include call sites, allocation sites, and types).<a class="footnote-ref" id="fnref:9" href="#fn:9"><sup>9</sup></a> To ensure termination (and more generally, scalability), such analyses generally use a <i>k</i>-limiting approach, where the context has a fixed maximum size, and the least recently added elements are removed as needed.<a class="footnote-ref" id="fnref:10" href="#fn:10"><sup>10</sup></a> Three common variants of context-sensitive, flow-insensitive analysis are:<a class="footnote-ref" id="fnref:11" href="#fn:11"><sup>11</sup></a>
</p>
<ul><li>Call-site sensitivity</li>
<li>Object sensitivity</li>
<li>Type sensitivity</li></ul>
<h3>Call-site sensitivity</h3>
<p>In call-site sensitivity, the points-to set of each variable (the set of abstract heap allocations each variable could point to) is further qualified by a context consisting of a list of callsites in the program. These contexts abstract the control-flow of the program.
</p><p>The following program demonstrates how call-site sensitivity can achieve higher precision than a flow-insensitive, context-insensitive analysis.
</p>
int *id(int* p) {
  return p;
}
void main(void) {
  int x;
  int y;
  int *u = id(&x);  // main.3
  int *v = id(&y);  // main.4
}

<p>For this program, a context-insensitive analysis would (soundly but imprecisely) conclude that p can point to either the allocation holding x or that of y, so u and v may alias, and both could point to either allocation:
</p>
<table><tbody><tr><th>Pointer expression</th><th>Allocation site</th></tr><tr><td>&x</td><td>main::x</td></tr><tr><td>&y</td><td>main::y</td></tr><tr><td>u</td><td>main::x, main::y</td></tr><tr><td>v</td><td>main::x, main::y</td></tr><tr><td>p</td><td>main::x, main::y</td></tr></tbody></table>
<p>A callsite-sensitive analysis would analyze id twice, once for main.3 and once for main.4, and the points-to facts for p would be qualified by the call-site, enabling the analysis to deduce that when main returns, u can only point to the allocation holding x and v can only point to the allocation holding y:
</p>
<table><tbody><tr><th>Context</th><th>Pointer expression</th><th>Allocation site</th></tr><tr><td>[]</td><td>&x</td><td>main::x</td></tr><tr><td>[]</td><td>&y</td><td>main::y</td></tr><tr><td>[]</td><td>u</td><td>main::x</td></tr><tr><td>[]</td><td>v</td><td>main::y</td></tr><tr><td>[main.3]</td><td>p</td><td>main::x</td></tr><tr><td>[main.4]</td><td>p</td><td>main::y</td></tr></tbody></table>
<h3>Object sensitivity</h3>
<p>In an object sensitive analysis, the points-to set of each variable is qualified by the abstract heap allocation of the receiver object of the method call. Unlike call-site sensitivity, object-sensitivity is <i>non-syntactic</i> or <i>non-local</i>: the context entries are derived during the points-to analysis itself.<a class="footnote-ref" id="fnref:12" href="#fn:12"><sup>12</sup></a>
</p>
<h3>Type sensitivity</h3>
<p>Type sensitivity is a variant of object sensitivity where the allocation site of the receiver object is replaced by the class/type containing the method containing the allocation site of the receiver object.<a class="footnote-ref" id="fnref:13" href="#fn:13"><sup>13</sup></a> This results in strictly fewer contexts than would be used in an object-sensitive analysis, which generally means better performance.
</p>

<h2 id="bibliography">Bibliography</h2>
<ul><li>Zyrianov, Vlas; Newman, Christian D.; Guarnera, Drew T.; Collard, Michael L.; Maletic, Jonathan I. (2019). <a href="https://www.zyrianov.org/papers/ICPC19.pdf">"srcPtr: A Framework for Implementing Static Pointer Analysis Approaches"</a> (PDF). <i>ICPC '19: Proceedings of the 27th IEEE International Conference on Program Comprehension</i>. Montreal, Canada: IEEE.</li>
<li>Smaragdakis, Yannis; Balatsouras, George (2015). <a href="https://yanniss.github.io/points-to-tutorial15.pdf">"Pointer Analysis"</a> (PDF). <i>Foundations and Trends in Programming Languages</i>. 2 (1): 1–69. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1561%2F2500000014">10.1561/2500000014</a>. <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:207179267">207179267</a>. Retrieved May 30, 2019.</li>
<li>Li, Yue; Tan/, Tian; Møller, Anders; Smaragdakis, Yannis (2020-05-18). <a href="https://doi.org/10.1145/3381915">"A Principled Approach to Selective Context Sensitivity for Pointer Analysis"</a>. <i>ACM Transactions on Programming Languages and Systems</i>. 42 (2): 10:1–10:40. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1145%2F3381915">10.1145/3381915</a>. <a href="/facts/ISSN_(identifier)/DPAflDvU">ISSN</a> <a href="https://search.worldcat.org/issn/0164-0925">0164-0925</a>. <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:214812357">214812357</a>.</li>
<li>Michael Hind (2001). <a href="http://www.cs.trinity.edu/~mlewis/CSCI3294-F01/Papers/p54-hind.pdf">"Pointer analysis: haven't we solved this problem yet?"</a> (PDF). <i>PASTE '01: Proceedings of the 2001 ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering</i>. ACM. pp. 54–61. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 1-58113-413-4.</li>
<li>Steensgaard, Bjarne (1996). <a href="http://cms.dc.uba.ar/materias/aap/2008/c2/descargas/pointsTo.pdf">"Points-to analysis in almost linear time"</a> (PDF). <i>POPL '96: Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages</i>. New York, NY, USA: ACM. pp. 32–41. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1145%2F237721.237727">10.1145/237721.237727</a>. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 0-89791-769-3.</li>
<li>Andersen, Lars Ole (1994). <a href="http://www.cs.cornell.edu/courses/cs711/2005fa/papers/andersen-thesis94.pdf"><i>Program Analysis and Specialization for the C Programming Language</i></a> (PDF) (PhD thesis).</li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1"><p>Reps, Thomas (2000-01-01). "Undecidability of context-sensitive data-dependence analysis". ACM Transactions on Programming Languages and Systems. 22 (1): 162–186. doi:10.1145/345099.345137. ISSN 0164-0925. S2CID 2956433. <a href="https://doi.org/10.1145%2F345099.345137" target="_blank">https://doi.org/10.1145%2F345099.345137</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li>
<li id="fn:2"><p>Barbara G. Ryder (2003). "Dimensions of Precision in Reference Analysis of Object-Oriented Programming Languages". Compiler Construction, 12th International Conference, CC 2003 Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2003 Warsaw, Poland, April 7–11, 2003 Proceedings. pp. 126–137. doi:10.1007/3-540-36579-6_10. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li>
<li id="fn:3"><p>(Hind) harv error: no target: CITEREFHind (help) <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li>
<li id="fn:4"><p>Zyrianov, Vlas; Newman, Christian D.; Guarnera, Drew T.; Collard, Michael L.; Maletic, Jonathan I. (2019). "srcPtr: A Framework for Implementing Static Pointer Analysis Approaches" (PDF). ICPC '19: Proceedings of the 27th IEEE International Conference on Program Comprehension. Montreal, Canada: IEEE. <a href="https://www.zyrianov.org/papers/ICPC19.pdf" target="_blank">https://www.zyrianov.org/papers/ICPC19.pdf</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li>
<li id="fn:5"><p>Sui, Yulei; Xue, Jingling (2016). "SVF: interprocedural static value-flow analysis in LLVM" (PDF). CC'16: Proceedings of the 25th international conference on compiler construction. ACM. <a href="https://yuleisui.github.io/publications/cc16.pdf" target="_blank">https://yuleisui.github.io/publications/cc16.pdf</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></p></li>
<li id="fn:6"><p>Smaragdakis, Yannis; Bravenboer, Martin; Lhoták, Ondrej (2011-01-26). "Pick your contexts well". Proceedings of the 38th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages. POPL '11. Austin, Texas, USA: Association for Computing Machinery. pp. 17–30. doi:10.1145/1926385.1926390. ISBN 978-1-4503-0490-0. S2CID 6451826. <a href="978-1-4503-0490-0" target="_blank">978-1-4503-0490-0</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></p></li>
<li id="fn:7"><p>Antoniadis, Tony; Triantafyllou, Konstantinos; Smaragdakis, Yannis (2017-06-18). "Porting doop to Soufflé". Proceedings of the 6th ACM SIGPLAN International Workshop on State of the Art in Program Analysis. SOAP 2017. Barcelona, Spain: Association for Computing Machinery. pp. 25–30. doi:10.1145/3088515.3088522. ISBN 978-1-4503-5072-3. S2CID 3074689. <a href="978-1-4503-5072-3" target="_blank">978-1-4503-5072-3</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></p></li>
<li id="fn:8"><p>(Smaragdakis & Balatsouras, p. 29) harv error: no target: CITEREFSmaragdakisBalatsouras (help) <a href="#fnref:8" class="footnote-back-ref">↩</a></p></li>
<li id="fn:9"><p>Thiessen, Rei; Lhoták, Ondřej (2017-06-14). "Context transformations for pointer analysis". ACM SIGPLAN Notices. 52 (6): 263–277. doi:10.1145/3140587.3062359. ISSN 0362-1340. <a href="https://doi.org/10.1145/3140587.3062359" target="_blank">https://doi.org/10.1145/3140587.3062359</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></p></li>
<li id="fn:10"><p>(Li et al., pp. 1:4) harv error: no target: CITEREFLiTanMøllerSmaragdakis (help) <a href="#fnref:10" class="footnote-back-ref">↩</a></p></li>
<li id="fn:11"><p>(Smaragdakis & Balatsouras) harv error: no target: CITEREFSmaragdakisBalatsouras (help) <a href="#fnref:11" class="footnote-back-ref">↩</a></p></li>
<li id="fn:12"><p>(Smaragdakis & Balatsouras, p. 37) harv error: no target: CITEREFSmaragdakisBalatsouras (help) <a href="#fnref:12" class="footnote-back-ref">↩</a></p></li>
<li id="fn:13"><p>(Smaragdakis & Balatsouras, p. 39) harv error: no target: CITEREFSmaragdakisBalatsouras (help) <a href="#fnref:13" class="footnote-back-ref">↩</a></p></li>
</ol>

Pointer analysis open-in-new

Pointer analysis