Flow-Sensitive Pointer Analysis
Flow-insensitive pointer analysis, andersen's analysis, steensgaard's analysis, shapiro's analysis, das's analysis, efficiency of das's algorithm, experimental results.
Welcome to the new UNSWorks platform – content is currently being migrated.
Search for theses and datasets below. Until further notice, other research outputs can be found on Primo UNSWorks .
Publication: Efficient and Precise Pointer Analysis with Fine-Grained Context Sensitivity
Resource type.
International Workshop on Structured Object-Oriented Formal Language and Method
SOFL+MSVL 2014: Structured Object-Oriented Formal Language and Method pp 164–178 Cite as
Incremental Points-to Analysis for Java via Edit Propagation
- Yuting Chen 15 ,
- Qiuwei Shi 15 , 16 &
- Weikai Miao 16
- Conference paper
- First Online: 01 January 2015
489 Accesses
Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 8979))
Points-to analysis is a static analysis technique which computes the relationships between the program variables and the heap references. It has been widely used in program optimization, program understanding, and error detection. Inclusion-based points-to analysis computes the points-to sets in a program by translating the program into a set of inclusion constraints on the points-to sets and then solving them to yield the desired results. Yet the analysis faces a difficulty in that a program can be frequently changed in its development, and great efforts may be exhausted to re-generate the inclusion constraints and re-solve them. In this paper, we extend the inclusion-based points-to analysis to an incremental one called Inc-PTA . The essential idea of Inc-PTA is to sum up the program changes into an editscript of a sequence of successive edits, and then to propagate the edits to the constraints followed by taking a demand-driven points-to analysis of the program. We also discuss about the correctness of Inc-PTA, and believe that Inc-PTA can provide with a cost-effective solution to incremental points-to analysis.
This is a preview of subscription content, log in via an institution .
Buying options
- Available as PDF
- Read on any device
- Instant download
- Own it forever
- Available as EPUB and PDF
- Compact, lightweight edition
- Dispatched in 3 to 5 business days
- Free shipping worldwide - see info
Tax calculation will be finalised at checkout
Purchases are for personal use only
Steensgaard, B.: Points-to analysis in almost linear time. In: Boehm Jr., H.J., Shackle, G.L.S. (eds.) POPL, pp. 32–41. ACM Press, New York (1996)
Google Scholar
Andersen, L.O.: Program analysis and specialization for the c programming language. Master’s thesis, University of Copenhagen (1994)
Méndez-Lojo, M., Mathew, A., Pingali, K.: Parallel inclusion-based points-to analysis. In: Cook, W.R., Clarke, S., Rinard, M.C. (eds.) OOPSLA, pp. 428–443. ACM, New York (2010)
Méndez-Lojo, M., Burtscher, M., Pingali, K.: A gpu implementation of inclusion-based points-to analysis. In: Ramanujam, J., Sadayappan, P. (eds.) PPOPP, p. 107. ACM, New York (2012)
Lhoták, O., Smaragdakis, Y., Sridharan, M.: Pointer analysis (dagstuhl seminar 13162). Dagstuhl Rep. 3 (4), 91–113 (2013)
Rountev, A., Kagan, S., Marlowe, T.: Interprocedural dataflow analysis in the presence of large libraries. In: Mycroft, A., Zeller, A. (eds.) CC 2006. LNCS, vol. 3923, pp. 2–16. Springer, Heidelberg (2006)
Chapter Google Scholar
Chase, D.R., Wegman, M.N., Zadeck, F.K.: Analysis of pointers and structures. In: Fischer, B.N. (ed.) PLDI, pp. 296–310. ACM, New York (1990)
Hardekopf, B., Lin, C.: Flow-sensitive pointer analysis for millions of lines of code. In: IEEE CGO, pp. 289–298 (2011)
Lu, Y., Shang, L., Xie, X., Xue, J.: An incremental points-to analysis with CFL-reachability. In: Jhala, R., De Bosschere, K. (eds.) Compiler Construction. LNCS, vol. 7791, pp. 61–81. Springer, Heidelberg (2013)
Jenista, J., Eom, Y., Demsky, B.: Using disjoint reachability for parallelization. In: Knoop, J. (ed.) CC 2011. LNCS, vol. 6601, pp. 198–224. Springer, Heidelberg (2011)
Vallee-Rai, R., Hendren, L.J.: Jimple: Simplifying java bytecode for analyses and transformations (1998)
Lhoták, O., Hendren, L.: Scaling java points-to analysis using SPARK. In: Hedin, G. (ed.) CC 2003. LNCS, vol. 2622, pp. 153–169. Springer, Heidelberg (2003)
Gall, H., Fluri, B., Pinzger, M.: Change analysis with evolizer and changedistiller. IEEE Softw. 26 (1), 26–33 (2009)
Article Google Scholar
Fluri, B., Würsch, M., Pinzger, M., Gall, H.: Change distilling: tree differencing for fine-grained source code change extraction. IEEE Trans. Softw. Eng. 33 (11), 725–743 (2007)
Vallée-Rai, R.C.P., Gagnon, E., Hendren, L.J., Lam, P., Sundaresan, V.: CASCON. In: MacKay, S.A., Johnson, J.H. (eds.) Soot-A Java Bytecode Optimization Framework, p. 13. IBM, San Diego (1999)
Hardekopf, B., Lin, C.: The ant and the grasshopper: fast and accurate pointer analysis for millions of lines of code. In: Ferrante, J., McKinley, K.S. (eds.) PLDI, pp. 290–299. ACM, New York (2007)
Tok, T.B., Guyer, S.Z., Lin, C.: Efficient flow-sensitive interprocedural data-flow analysis in the presence of pointers. In: Mycroft, A., Zeller, A. (eds.) CC 2006. LNCS, vol. 3923, pp. 17–31. Springer, Heidelberg (2006)
Hardekopf, B., Lin, C.: Semi-sparse flow-sensitive pointer analysis. In: Shao, Z., Pierce, B.C. (eds.) POPL, pp. 226–238. ACM, New York (2009)
Gulwani, S., Srivastava, S., Venkatesan, R.: Program analysis as constraint solving. In: Gupta, R., Amarasinghe, S.P. (eds.) PLDI, pp. 281–292. ACM, New York (2008)
Visser, W., Geldenhuys, J., Dwyer, M.B.: Green: reducing, reusing and recycling constraints in program analysis. In: Tracz, W., Robillard, M.P., Bultan, T. (eds.) SIGSOFT FSE, p. 58. ACM, New York (2012)
Allen, J.R., Kennedy, K., Porterfield, C., Warren, J.D.: Conversion of control dependence to data dependence. In: Wright, J.R., Landweber, L., Demers, A.J., Teitelbaum, T. (eds.) POPL, pp. 177–189. ACM, New York (1983)
Pollock, L.L., Soffa, M.L.: An incremental version of iterative data flow analysis. IEEE Trans. Soft. Eng. 15 (12), 1537–1549 (1989)
Burke, M.G., Ryder, B.G.: A critical analysis of incremental iterative data flow analysis algorithms. IEEE Trans. Soft. Eng. 16 (7), 723–728 (1990)
Carroll, S., Polychronopoulos, C.D.: A framework for incremental extensible compiler construction. Int. J. Parallel Program. 32 (4), 289–316 (2004)
Article MATH Google Scholar
Carroll, S., Polychronopoulos, C.D.: A framework for incremental extensible compiler construction. In: Banerjee, U., Gallivan, K., González, A. (eds.) ICS, pp. 53–62. ACM, New York (2003)
Yur, J.S., Ryder, B.G., Landi, W.: An incremental flow- and context-sensitive pointer aliasing analysis. In: Boehm, B.W., Garlan, D., Kramer, J. (eds.) ICSE, pp. 442–451. ACM, New York (1999)
Vivien, F., Rinard, M.C.: Incrementalized pointer and escape analysis. In: Burke, M., Soffa, M.L. (eds.) PLDI, pp. 35–46. ACM, New York (2001)
Saha, D., Ramakrishnan, C.R.: Incremental and demand-driven points-to analysis using logic programming. In: Barahona, P., Felty, A.P. (eds.) PPDP, pp. 117–128. ACM, New York (2005)
Kodumal, J., Aiken, A.: Banshee: a scalable constraint-based analysis toolkit. In: Hankin, C., Siveroni, I. (eds.) SAS 2005. LNCS, vol. 3672, pp. 218–234. Springer, Heidelberg (2005)
Download references
Acknowledgments
We would like to thank the anonymous reviewers for their valuable and thorough comments. This work is supported by the National Natural Science Foundation of China (Grant No. 91118004 and 61100051).
Author information
Authors and affiliations.
School of Software, Shanghai Jiao Tong University, Shanghai, 200240, China
Yuting Chen & Qiuwei Shi
School of Software, East China Normal University, Shanghai, 200062, China
Qiuwei Shi & Weikai Miao
You can also search for this author in PubMed Google Scholar
Corresponding author
Correspondence to Yuting Chen .
Editor information
Editors and affiliations.
Hosei University, Tokyo, Japan
Shaoying Liu
Xidian University, Xi’an, China
Zhenhua Duan
Rights and permissions
Reprints and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper.
Chen, Y., Shi, Q., Miao, W. (2015). Incremental Points-to Analysis for Java via Edit Propagation. In: Liu, S., Duan, Z. (eds) Structured Object-Oriented Formal Language and Method. SOFL+MSVL 2014. Lecture Notes in Computer Science(), vol 8979. Springer, Cham. https://doi.org/10.1007/978-3-319-17404-4_11
Download citation
DOI : https://doi.org/10.1007/978-3-319-17404-4_11
Published : 17 April 2015
Publisher Name : Springer, Cham
Print ISBN : 978-3-319-17403-7
Online ISBN : 978-3-319-17404-4
eBook Packages : Computer Science Computer Science (R0)
Share this paper
Anyone you share the following link with will be able to read this content:
Sorry, a shareable link is not currently available for this article.
Provided by the Springer Nature SharedIt content-sharing initiative
- Publish with us
Policies and ethics
- Find a journal
- Track your research
Help | Advanced Search
Computer Science > Machine Learning
Title: fip: a fixed-point approach for causal generative modeling.
Abstract: Modeling true world data-generating processes lies at the heart of empirical science. Structural Causal Models (SCMs) and their associated Directed Acyclic Graphs (DAGs) provide an increasingly popular answer to such problems by defining the causal generative process that transforms random noise into observations. However, learning them from observational data poses an ill-posed and NP-hard inverse problem in general. In this work, we propose a new and equivalent formalism that do not require DAGs to describe them, viewed as fixed-point problems on the causally ordered variables, and show three important cases where they can be uniquely recovered given the topological ordering (TO). To the best of our knowledge, we obtain the most general recovery results when the TO is known. Based on our theoretical findings, we design a two-stage causal generative model that first infers the causal order from observations in a zero-shot manner, thus by-passing the search, and then learns the generative fixed-point SCM on the ordered variables. To infer TOs from observations, we propose to amortize the learning of TOs on generated datasets by sequentially predicting the leaves of graphs seen during training. To learn fixed-point SCMs, we design a transformer-based architecture that exploits a new attention mechanism enabling the modeling of causal structures, and show that this parameterization is consistent with our formalism. Finally, we conduct an extensive evaluation of each method individually, and show that when combined, our model outperforms various baselines on generated out-of-distribution problems.
Submission history
Access paper:.
- HTML (experimental)
- Other Formats
References & Citations
- Google Scholar
- Semantic Scholar
BibTeX formatted citation
Bibliographic and Citation Tools
Code, data and media associated with this article, recommenders and search tools.
- Institution
arXivLabs: experimental projects with community collaborators
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs .
IMAGES
VIDEO
COMMENTS
Pointer Assignment Graph abstraction L1 Abstract object node: A Tour of Pointer Analysis| OndrejLhotak| University of Waterloo Java: L1: x = new Object() C: L1: x = malloc(42) Represents some set of run-time objects (targets of pointers). e.g. all objects allocated at a given allocation site e.g. all objects of a given dynamic type
Pointer-Assignment Graph (PAG) Nodes Allocation Variable Field reference Edges Allocation Assignment Field store Field load One for eachlocal variable,parameter, static eld, andthrown exception Represents a memory location holding pointers to objects May be typed (depends on setting) p. 39 - 4 Pointer-Assignment Graph (PAG) Nodes
The points-to graphs shown are actually slightly simplified; we will see the missing parts below. In the graphs, points-to edges are shown as plain arrows, and flow edges are shown as arrows with stars above them. Like Steensgaard, Das processes each assignment in the program just once, building a points-to graph with both points-to and flow edges.
The execution of SPARK can be divided into three stages: pointer assignment graph construction, pointer assignment graph simplification, an d points-to set propagation. These stages are described in the following subsections. 3.2 Pointer Assignment Graph SPARK uses a pointer assignment graph as its internal representation of the program being ...
CPv p: ywp ˙q r zÞÑ ˙p zq\ ˙p yqs ˙ where may-point-top p;zq 2 Andersen's Points-To Analysis Two common kinds of pointer analysis are alias analysis and points-to anal-ysis. Alias analysis computes a set Sholding pairs of variables p p;qq , where pand qmay (or must) point to the same location. On the other hand, points-
Pointer-Assignment Graph (PAG) Nodes Allocation Variable Field reference Edges Allocation Assignment Field store Field load One for eachlocal variable,parameter, static eld, andthrown exception Represents a memory location holding pointers to objects May be typed (depends on setting) p. 36 - 4 Pointer-Assignment Graph (PAG) Nodes
Pointer Analysis Prof. Gennady Pekhimenko University of Toronto Winter 2019 ... • For each statement, build the points-to graph: • Iterate until graph no longer changes • Worst case complexity: O(n3), where n = program size 18 y = &x y points-to x y = x if x points-to w
may point to either variable using a single points-to relationship. For example, consider the program below: 1 : p: &x 2 : r: &p 3 : q: &y 4 : s: &q 5 : r: s Andersen's points-to analysis would produce the following graph: x p r y q s But in Steensgaard's setting, when we discover that rcould point both to qand to p, we must merge qand ...
Analysis and Object-Oriented Call Graph Construction 17-355/17-665/17-819: Program Analysis (Spring 2020) Claire Le Goues ... the rules above by treating any field dereference or field assignment to p:fas a pointer dereference p. Essentially, you can think of this as just considering all fields to be named .
- Need a control flow graph - Must store results for each program point - Improves accuracy • Path sensitive - Each path in a control flow graph is considered 15-745: Pointer Analysis 11 Todd C. Mowry Carnegie Mellon Flow Sensitivity Example (assuming allocation-site heap modeling) 15-745: Pointer Analysis 12 Todd C. Mowry
Table 1 summarizes the rules of Andersen's analysis for computing the points-to constraints corresponding to diferent types of program statements. For each type, the points-to sets of the related variables are updated as follows: [Base] x new C(): Add a new object o to pts(x). =. [Simple] x y: Add pts(y) to pts(x).
The pointer assignment graph consists of three types of nodes.Allocation site nodes represent allocation sites in the source program, and are used to model heap locations. Simple variable nodes represent local variables, method parameters and return values, and static fields. Field dereference nodes represent field access expressions in the ...
When analyzing a pointer assignment, a new method called expression expansion is used to calculate both the left targets and the right targets. The integration of recursive data structure analysis into pointer analysis is a significant originality of this paper, which uniforms the pointer analysis for heap variables and the pointer analysis for ...
Spark [7] is a framework for doing various kinds of points-to analyses within Soot [11]. Spark works by first constructing a Pointer Assignment Graph (PAG), which captures the structure of which ...
of which points-to relationships are represented by a pointer assignment graph (PAG) [Lhoták 2002] and calling relationships between methods are represented by a call graph (CG). There are ive types of statements that determine the points-to relationships in the table. New
At the LLVM level, a field assignment like w.x = &u (that is, a reference to a field on the left-hand side of an assignment) gets split into two instructions, ... The for.inc block has no effect on the points-to graph, so we've computed the fixed point and we're done! Phew! Conclusion. Pointer analysis is a foundational static analysis. We ...
Unlike traditional approaches, which apply context-sensitivity either uniformly to all methods or selectively to a subset of methods in a program, we go one step further by applying context-sensitivity only to a subset of precision-critical variables and objects so that we can reduce significantly the scale of Pointer Assignment Graph (PAG ...
Inclusion-based points-to analysis defines and solves a set of inclusion constraints on the points-to relations. Lhoták has introduced PAG (Pointer Assignment Graph) as the internal representation of the program being analyzed [].A PAG is defined as a directed graph \(<V,E>\) where \(V\) contains a set of vertices. A PAG uses four types of vertices (allocation vertices, variable vertices ...
Now we have two variables x and y: int *p = &x; int *q = &y; There are declared another two variables, pointer p which points to variable x and contains its address and pointer q which points to variable y and contains its address: x = 35; y = 46; Here you assign values to the variables, this is clear: p = q;
Desmos Graphing Calculator Untitled Graph is a powerful and interactive tool for creating and exploring graphs of any function, equation, or inequality. You can customize your graph with colors, labels, sliders, tables, and more. You can also share your graph with others or export it to different formats. Whether you are a student, teacher, or enthusiast, Desmos Graphing Calculator Untitled ...
The execution of Sparkcan be divided into three stages: pointer assignment graph construction, pointer assignment graph simplification, and points-to set propagation. These stages are described in the following subsections. 3.2 Pointer Assignment Graph Spark uses a pointer assignment graph as its internal representation of the program being ...
Interactive, free online graphing calculator from GeoGebra: graph functions, plot data, drag sliders, and much more!
Modeling true world data-generating processes lies at the heart of empirical science. Structural Causal Models (SCMs) and their associated Directed Acyclic Graphs (DAGs) provide an increasingly popular answer to such problems by defining the causal generative process that transforms random noise into observations. However, learning them from observational data poses an ill-posed and NP-hard ...
US consumer prices picked up again last month, vaulting to a 3.5% increase for the 12 months ended in March, according to the latest Consumer Price Index data released Wednesday by the Bureau of ...