The DOI matches its Crossref record; 34 of the 34 references it cites were found in a registry or an index.
Interprocedural may-alias analysis for pointers: beyond k -limiting
Abstract
Existing methods for alias analysis of recursive pointer data structures are based on two approximation techniques: k-limiting, and store-based (or equivalently location or region-based) approximations, which blur distinction between elements of recursive data structures. Although notable progress in inter-procedural alias analysis has been recently accomplished, very little progress in the precision of analysis of recursive pointer data structures has been seen since the inception of these approximation techniques by Jones and Muchnick a decade ago. As a result, optimizing, verifying and parallelizing programs with pointers has remained difficult.We present a new parametric framework for analyzing recursive pointer data structures which can express a new natural class of alias information not accessible to existing methods. The key idea is to represent alias information by pairs of symbolic access paths which are qualified by symbolic descriptions of the positions for which the alias pair holds.Based on this result, we present an algorithm for interprocedural may-alias analysis with pointers which on numerous examples that occur in practice is much more precise than recently published algorithms [CWZ90, He90, LR92, CBC93].
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Compilers: Principles, Techniques, and Tools
Aho, A. V., Sethi, R., & Ullman, J. D. (1986) · Cited by 8,448
Cousot, P., & Cousot, R. (1977) · Proceedings of the 4th ACM SIGACT-SIGPLAN symposium on Principles of programming languages - POPL '77 · doi:10.1145/512950.512973 · Cited by 6,279
Automata, Languages, and Machines
(1974) · Pure and applied mathematics · doi:10.1016/s0079-8169(08)x6055-6 · Cited by 1,897
Systematic design of program analysis frameworks
Cousot, P., & Cousot, R. (1979) · Proceedings of the 6th ACM SIGACT-SIGPLAN symposium on Principles of programming languages - POPL '79 · doi:10.1145/567752.567778 · Cited by 1,621
Automatic discovery of linear restraints among variables of a program
Cousot, P., & Halbwachs, N. (1978) · Proceedings of the 5th ACM SIGACT-SIGPLAN symposium on Principles of programming languages - POPL '78 · doi:10.1145/512760.512770 · Cited by 1,614
Derivatives of Regular Expressions
Brzozowski, J. A. (1964) · Journal of the ACM · doi:10.1145/321239.321249 · Cited by 923
A unified approach to global program optimization
Kildall, G. A. (1973) · Proceedings of the 1st annual ACM SIGACT-SIGPLAN symposium on Principles of programming languages - POPL '73 · doi:10.1145/512927.512945 · Cited by 916
Parikh, R. (1966) · Journal of the ACM · doi:10.1145/321356.321364 · Cited by 808
Affine relationships among variables of a program
Karr, M. (1976) · Acta Informatica · doi:10.1007/bf00268497 · Cited by 439
Analysis of pointers and structures
Chase, D., Wegman, M., & Zadeck, F. K. (2004) · ACM SIGPLAN Notices · doi:10.1145/989393.989429 · Cited by 433
Cited by
Points-to analysis in almost linear time
Steensgaard, B. (1996) · Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages - POPL '96 · doi:10.1145/237721.237727 · Cited by 1,088
Watermarking, tamper-proofing, and obfuscation - tools for software protection
Collberg, C. S., & Thomborson, C. (2002) · IEEE Transactions on Software Engineering · doi:10.1109/tse.2002.1027797 · Cited by 735
Miné, A. (2006) · Higher-Order and Symbolic Computation · doi:10.1007/s10990-006-8609-1 · Cited by 720
Ownership types for flexible alias protection
Clarke, D. G., Potter, J. M., & Noble, J. (1998) · Proceedings of the 13th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications · doi:10.1145/286936.286947 · Cited by 580
Efficient context-sensitive pointer analysis for C programs
Wilson, R. P., & Lam, M. S. (1995) · ACM SIGPLAN Notices · doi:10.1145/223428.207111 · Cited by 539
Manufacturing cheap, resilient, and stealthy opaque constructs
Collberg, C., Thomborson, C., & Low, D. (1998) · Proceedings of the 25th ACM SIGPLAN-SIGACT symposium on Principles of programming languages - POPL '98 · doi:10.1145/268946.268962 · Cited by 535
Efficient context-sensitive pointer analysis for C programs
Wilson, R. P., & Lam, M. S. (1995) · Proceedings of the ACM SIGPLAN 1995 conference on Programming language design and implementation · doi:10.1145/207110.207111 · Cited by 458
A Survey of Automated Techniques for Formal Software Verification
D'Silva, V., Kroening, D., & Weissenbacher, G. (2008) · IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems · doi:10.1109/tcad.2008.923410 · Cited by 378
Solving shape-analysis problems in languages with destructive updating
Sagiv, M., Reps, T., & Wilhelm, R. (1998) · ACM Transactions on Programming Languages and Systems · doi:10.1145/271510.271517 · Cited by 322
A brief survey of program slicing
Xu, B., Qian, J., Zhang, X., Wu, Z., & Chen, L. (2005) · ACM SIGSOFT Software Engineering Notes · doi:10.1145/1050849.1050865 · Cited by 313
Escape analysis for object-oriented languages: application to Java
Blanchet, B. (1999) · Proceedings of the 14th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications · doi:10.1145/320384.320387 · Cited by 294
Is it a tree, a DAG, or a cyclic graph? A shape analysis for heap-directed pointers in C
Ghiya, R., & Hendren, L. J. (1996) · Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages - POPL '96 · doi:10.1145/237721.237724 · Cited by 287
Observational determinism for concurrent program security
Zdancewic, S., & Myers, A. C. (2004) · 16th IEEE Computer Security Foundations Workshop, 2003. Proceedings. · doi:10.1109/csfw.2003.1212703 · Cited by 270
Typed memory management in a calculus of capabilities
Crary, K., Walker, D., & Morrisett, G. (1999) · Proceedings of the 26th ACM SIGPLAN-SIGACT symposium on Principles of programming languages · doi:10.1145/292540.292564 · Cited by 252
(2004) · OpenGrey (Institut de l'Information Scientifique et Technique) · Cited by 126
Metadata
- Authors
- Deutsch, A.
- Venue
- Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation
- Publisher
- ACM
- Published
- 1994-06
- Pages
- 230-241
- ISSN
- 1531-7102 (ISSN-L)
- OpenAlex
- W2102440514
- Cited by
- 328
- References
- 34
- FWCI
- 18.32
- Type
- conference paper
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.