Cited By
View all- Kanvar VTamilselvam SKomondoor R(2022)Handling Memory Pointers in Communication between Microservices2022 IEEE International Conference on Web Services (ICWS)10.1109/ICWS55610.2022.00027(85-90)Online publication date: Jul-2022
"What's in a name?" going beyond allocation site names in heap analysis
Pages 92 - 103
Abstract
A points-to analysis computes a sound abstraction of heap memory conventionally using a name-based abstraction that summarizes runtime memory by grouping locations using the names of allocation sites: All concrete heap locations allocated by the same statement are grouped together. The locations in the same group are treated alike i.e., a pointer to any one location of the group is assumed to point to every location in the group leading to an over-approximation of points-to relations.
We propose an access-based abstraction that partitions each name-based group of locations into equivalence classes at every program point using an additional criterion of the sets of access paths (chains of pointer indirections) reaching the locations in the memory. The intuition is that the locations that are both allocated and accessed alike should be grouped into the same equivalence class. Since the access paths in the memory could reach different locations at different program points, our groupings change flow sensitively unlike the name-based groupings. This creates a more precise view of the memory. Theoretically, it is strictly more precise than the name-based abstraction except in some trivial cases; practically it is far more precise.
Our empirical measurements show the benefits of our tool Access-Based Heap Analyzer (ABHA) on SPEC CPU 2006 and heap manipulating SV-COMP benchmarks. ABHA, which is field-, flow-, and context-sensitive, scales to 20 kLoC and can improve the precision even up to 99% (in terms of the number of aliases). Additionally, ABHA allows any user-defined summarization of an access path to be plugged in; we have implemented and evaluated four summarization techniques. ABHA can also act as a front-end to TVLA, a parametrized shape analyzer, in order to automate its parametrization by generating predicates that capture the program behaviour more accurately.
References
[1]
G. Balakrishnan and T. Reps. Recency-abstraction for heap-allocated storage. In Proceedings of the 13th International Conference on Static Analysis, SAS’06, pages 221–239, Berlin, Heidelberg, 2006. Springer-Verlag.
[2]
I. Bogudlov, T. Lev-Ami, T. Reps, and M. Sagiv. Revamping tvla: Making parametric shape analysis competitive. In Proceedings of the 19th International Conference on Computer Aided Verification, CAV’07, pages 221–225, Berlin, Heidelberg, 2007. Springer-Verlag.
[3]
M. Bozga, R. Iosif, and Y. Lakhnech. Static Analysis: 11th International Symposium, SAS 2004, Verona, Italy, August 26-28, 2004. Proceedings, chapter On Logics of Aliasing, pages 344–360. Springer Berlin Heidelberg, Berlin, Heidelberg, 2004.
[4]
D. R. Chase, M. Wegman, and F. K. Zadeck. Analysis of pointers and structures. In Proceedings of the ACM SIGPLAN 1990 Conference on Programming Language Design and Implementation, PLDI ’90, pages 296–310, New York, NY, USA, 1990. ACM.
[5]
D. Distefano, P. W. O’Hearn, and H. Yang. A local shape analysis based on separation logic. In Proceedings of the 12th International Conference on Tools and Algorithms for the Construction and Analysis of Systems, TACAS’06, pages 287–302, Berlin, Heidelberg, 2006. Springer-Verlag.
[6]
A. Gotsman, J. Berdine, and B. Cook. Interprocedural shape analysis with separated heap abstractions. In Proceedings of the 13th International Conference on Static Analysis, SAS’06, pages 240–260, Berlin, Heidelberg, 2006. Springer-Verlag.
[7]
B. Hardekopf and C. Lin. Flow-sensitive pointer analysis for millions of lines of code. In Proceedings of the 9th Annual IEEE/ACM International Symposium on Code Generation and Optimization, CGO ’11, pages 289–298, Washington, DC, USA, 2011. IEEE Computer Society.
[8]
M. Hind, M. Burke, P. Carini, and J.-D. Choi. Interprocedural pointer alias analysis. ACM Trans. Program. Lang. Syst., 21(4):848–894, July 1999.
[9]
M. Hirzel, A. Diwan, and J. Henkel. On the usefulness of type and liveness accuracy for garbage collection and leak detection. ACM Trans. Program. Lang. Syst., 24(6):593–624, Nov. 2002.
[10]
V. Kanvar and U. P. Khedker. Heap abstractions for static analysis. ACM Comput. Surv., 49(2):29:1–29:47, June 2016.
[11]
U. Khedker, A. Sanyal, and A. Karkare. Heap reference analysis using access graphs. ACM Trans. Program. Lang. Syst., 30(1), Nov. 2007.
[12]
U. Khedker, A. Sanyal, and B. Karkare. Data Flow Analysis: Theory and Practice. CRC Press, Inc., Boca Raton, USA, 1st edition, 2009.
[13]
U. P. Khedker and B. Karkare. Efficiency, precision, simplicity, and generality in interprocedural data flow analysis: Resurrecting the classical call strings method. In Proceedings of the Joint European Conferences on Theory and Practice of Software 17th International Conference on Compiler Construction, CC’08/ETAPS’08, pages 213– 228, Berlin, Heidelberg, 2008. Springer-Verlag.
[14]
U. P. Khedker, A. Mycroft, and P. S. Rawat. Liveness-based pointer analysis. In Proceedings of the 19th International Conference on Static Analysis, SAS’12, pages 265–282, Deauville, France, 2012. Springer-Verlag.
[15]
V. Kuncak, P. Lam, K. Zee, and M. C. Rinard. Modular pluggable analyses for data structure consistency. IEEE Trans. Softw. Eng., 32 (12):988–1005, Dec. 2006.
[16]
W. Landi and B. G. Ryder. A safe approximate algorithm for interprocedural aliasing. In Proceedings of the ACM SIGPLAN 1992 Conference on Programming Language Design and Implementation, PLDI ’92, pages 235–248, New York, NY, USA, 1992. ACM.
[17]
J. R. Larus and P. N. Hilfinger. Detecting conflicts between structure accesses. In Proceedings of the ACM SIGPLAN 1988 Conference on Programming Language Design and Implementation, PLDI ’88, pages 24–31, New York, NY, USA, 1988. ACM.
[18]
C. Lattner, A. Lenharth, and V. Adve. Making context-sensitive points-to analysis with heap cloning practical for the real world. In Proceedings of the 2007 ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI ’07, pages 278–289, New York, NY, USA, 2007. ACM.
[19]
T. Lev-Ami, N. Immerman, and M. Sagiv. Abstraction for shape analysis with fast and precise transformers. In Proceedings of the 18th International Conference on Computer Aided Verification, CAV’06, pages 547–561, Berlin, Heidelberg, 2006. Springer-Verlag.
[20]
A. Loginov, T. Reps, and M. Sagiv. Automated verification of the deutsch-schorr-waite tree-traversal algorithm. In Proceedings of the 13th International Conference on Static Analysis, SAS’06, pages 261– 279, Berlin, Heidelberg, 2006. Springer-Verlag.
[21]
R. Manevich. Tvla: 3-valued logic analysis engine, tvla3+hedec, June 2011.
[22]
R. Manevich, M. Sagiv, G. Ramalingam, and J. Field. Partially Disjunctive Heap Abstraction, pages 265–279. Springer Berlin Heidelberg, Berlin, Heidelberg, 2004.
[23]
I. Matosevic and T. S. Abdelrahman. Efficient bottom-up heap analysis for symbolic path-based data access summaries. In Proceedings of the Tenth International Symposium on Code Generation and Optimization, CGO ’12, pages 252–263, New York, NY, USA, 2012. ACM.
[24]
A. Milanova, A. Rountev, and B. G. Ryder. Parameterized object sensitivity for points-to and side-effect analyses for java. SIGSOFT Softw. Eng. Notes, 27(4):1–11, July 2002.
[25]
A. Møller and M. I. Schwartzbach. The pointer assertion logic engine. In Proceedings of the ACM SIGPLAN 2001 Conference on Programming Language Design and Implementation, PLDI ’01, pages 221–231, New York, NY, USA, 2001. ACM.
[26]
R. Padhye and U. P. Khedker. Interprocedural data flow analysis in soot using value contexts. In Proceedings of the 2Nd ACM SIGPLAN International Workshop on State Of the Art in Java Program Analysis, SOAP ’13, pages 31–36, New York, NY, USA, 2013. ACM.
[27]
J. Reineke. Shape analysis of sets. Master’s thesis, Universität des Saarlandes, Germany, June 2005.
[28]
N. Rinetzky, M. Sagiv, and E. Yahav. Interprocedural shape analysis for cutpoint-free programs. In Proceedings of the 12th International Conference on Static Analysis, SAS’05, pages 284–302, Berlin, Heidelberg, 2005. Springer-Verlag.
[29]
M. Sagiv, T. Reps, and R. Wilhelm. Parametric shape analysis via 3-valued logic. In Proceedings of the 26th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL ’99, pages 105–118, New York, NY, USA, 1999. ACM.
[30]
Y. Smaragdakis, M. Bravenboer, and O. Lhoták. Pick your contexts well: Understanding object-sensitivity. In Proceedings of the 38th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL ’11, pages 17–30, New York, NY, USA, 2011. ACM.
[31]
M. Sridharan, S. Chandra, J. Dolby, S. J. Fink, and E. Yahav. Aliasing in object-oriented programming. In D. Clarke, J. Noble, and T. Wrigstad, editors, Alias Analysis for Object-oriented Programs, pages 196–232. Springer-Verlag, Berlin, Heidelberg, 2013.
[32]
E. Yahav and G. Ramalingam. Verifying safety properties using separation and heterogeneous abstractions. In Proceedings of the ACM SIGPLAN 2004 Conference on Programming Language Design and Implementation, PLDI ’04, pages 25–34, NY, USA, 2004. ACM.
Index Terms
- "What's in a name?" going beyond allocation site names in heap analysis
Recommendations
Heap Abstractions for Static Analysis
Heap data is potentially unbounded and seemingly arbitrary. Hence, unlike stack and static data, heap data cannot be abstracted in terms of a fixed set of program variables. This makes it an interesting topic of study and there is an abundance of ...
"What's in a name?" going beyond allocation site names in heap analysis
ISMM '17A points-to analysis computes a sound abstraction of heap memory conventionally using a name-based abstraction that summarizes runtime memory by grouping locations using the names of allocation sites: All concrete heap locations allocated by the same ...
Efficient and precise points-to analysis: modeling the heap by merging equivalent automata
PLDI 2017: Proceedings of the 38th ACM SIGPLAN Conference on Programming Language Design and ImplementationMainstream points-to analysis techniques for object-oriented languages rely predominantly on the allocation-site abstraction to model heap objects. We present MAHJONG, a novel heap abstraction that is specifically developed to address the needs of an ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
June 2017
127 pages
ISBN:9781450350440
DOI:10.1145/3092255
- General Chair:
- Christoph M. Kirsch,
- Program Chair:
- Ben L. Titzer
September 2017127 pages
Copyright © 2017 ACM.
© 2017 Association for Computing Machinery. ACM acknowledges that this contribution was authored or co-authored by an employee, contractor or affiliate of a national government. As such, the Government retains a nonexclusive, royalty-free right to publish or reproduce this article, or to allow others to do so, for Government purposes only.
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 18 June 2017
Check for updates
Author Tags
Qualifiers
- Research-article
Conference
ISMM '17
Sponsor:
Acceptance Rates
Overall Acceptance Rate 72 of 156 submissions, 46%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 164Total Downloads
- Downloads (Last 12 months)7
- Downloads (Last 6 weeks)0
Reflects downloads up to 20 Sep 2024
Other Metrics
Citations
Cited By
View all- Kanvar VTamilselvam SKomondoor R(2022)Handling Memory Pointers in Communication between Microservices2022 IEEE International Conference on Web Services (ICWS)10.1109/ICWS55610.2022.00027(85-90)Online publication date: Jul-2022
View Options
Get Access
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in