article

Open access

The undecidability of aliasing

Editor: Andrew W. Appel Author:

G. RamalingamAuthors Info & Claims

ACM Transactions on Programming Languages and Systems (TOPLAS), Volume 16, Issue 5

Pages 1467 - 1471

https://doi.org/10.1145/186025.186041

Published: 01 September 1994 Publication History

PDF eReader

Abstract

Alias analysis is a prerequisite for performing most of the common program analyses such as reaching-definitions analysis or live-variables analysis. Landi [1992] recently established that it is impossible to compute statically precise alias information—either may-alias or must-alias—in languages with if statements, loops, dynamic storage, and recursive data structures: more precisely, he showed that the may-alias relation is not recursive, while the must-alias relation is not even recursively enumerable. This article presents simpler proofs of the same results.

References

[1]

CHOI, J.-D., BURKE, M. G. AND CARINI, P. 1993. Efficient flow-sensitive interprocedural computation of pointer-induced aliases and side effects. In Conference Record of the 20th ACM Symposium on Principles of Programming Languages (Charleston, S. Carolina). ACM, New York, 232-245.

Crossref

Google Scholar

[2]

HOPCROFT, J. E. AND ULLMAN, J.D. 1979. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, Reading, Mass.

Crossref

Google Scholar

[3]

KAM, J. B. AND ULLMAN, Z. D. 1977. Monotone data flow analysis frameworks. In Acta Informatica 7, 305-317.

Google Scholar

[4]

LANDI, W. 1992. Undecidability of static analysis. 1992. Lett. Program. Lang. Syst. 1, 4 (Dec.).

Crossref

Google Scholar

[5]

LANDI, W. 1991. Interprocedural aliasing in the presence of pointers. Ph.D. thesis, Dept. of Computer Science, Rutgers Univ., New Brunswick, N.J.

Crossref

Google Scholar

[6]

LANDI, W. AND RYDER, B.G. 1992. A safe approximate algorithm for pointer-induced aliasing. SIGPLAN Not. 27, 7 (July), 235-248.

Crossref

Google Scholar

[7]

LARUS, J.R. 1989. Restructuring symbolic programs for concurrent execution on multiprocessors. Ph.D. thesis, Univ. of California, Berkeley, Calif. (May).

Crossref

Google Scholar

[8]

LARUS, J. R. AND HILFINGER, P. N.1988. Detecting conflicts between structure accesses. SIGPLAN Not. 23, 7 (July), 21-34.

Crossref

Google Scholar

[9]

MYERS, E. 1981. A precise inter-procedural data flow algorithm. In Conference Record of the 8th ACM Symposium on Principles of Programming Languages (Williamsburg, Va., Jan. 26-28). ACM, New York.

Crossref

Google Scholar

[10]

PFEIFFER, P. 1991. Dependence-based representations for programs with reference variables. Ph.D. dissertation and Tech. Rep. TR-1037, Computer Sciences Dept., Univ. of Wisconsin, Madison, Wis. (Aug.).

Crossref

Google Scholar

Cited By

View all

Lee SBinkley DFeldt RGold NYoo S(2025)Causal program dependence analysisScience of Computer Programming10.1016/j.scico.2024.103208240(103208)Online publication date: Feb-2025
https://doi.org/10.1016/j.scico.2024.103208
McMichen TGreiner NZhong PSossai FPatel ACampanoni SGrosser TDubach CSteuwer MXue JOttoni GQuintão Pereira F(2024)Representing Data Collections in an SSA FormProceedings of the 2024 IEEE/ACM International Symposium on Code Generation and Optimization10.1109/CGO57630.2024.10444817(308-321)Online publication date: 2-Mar-2024
https://dl.acm.org/doi/10.1109/CGO57630.2024.10444817
Gaidis AMoreira JSun KMilburn AAtlidakis VKemerlis V(2023)FineIBT: Fine-grain Control-flow Enforcement with Indirect Branch TrackingProceedings of the 26th International Symposium on Research in Attacks, Intrusions and Defenses10.1145/3607199.3607219(527-546)Online publication date: 16-Oct-2023
https://dl.acm.org/doi/10.1145/3607199.3607219
Show More Cited By

Index Terms

Recommendations

Undecidability of static analysis

Static analysis of programs is indispensable to any software tool, environment, or system that requires compile-time information about the semantics of programs. With the emergence of languages like C and LISP, static analysis of programs with dynamic ...
Precise flow-insensitive may-alias analysis is NP-hard

Determining aliases is one of the foundamental static analysis problems, in part because the precision with which this problem is solved can affect the precision of other analyses such as live variables, available expressions, and constant propagation. ...
Semi-sparse flow-sensitive pointer analysis
POPL '09

Pointer analysis is a prerequisite for many program analyses, and the effectiveness of these analyses depends on the precision of the pointer information they receive. Two major axes of pointer analysis precision are flow-sensitivity and context-...

Reviews

Reviewer: Danny B. Lange

Common static program analyses such as reaching-definition analysis and live-variables analysis require alias information. Two names (L-valued expressions) are said to alias each other at a particular point during program execution if both may, or must, have the same value. Landi [1] recently established that “may” and “must” alias problems are undecidable for languages that permit “if” statements, loops, dynamic storage, and recursive data structures. Ramalingam presents a simpler and very elegant proof of the same result. The approach taken is to reduce Post's Correspondence Problem (PCP), which is undecidable, to the “may” and “must” alias problems. The proof is supported by a program example in C. I f you are working in the field of static program analysis, be sure to take a look at this short and easy-to-read paper.

Access critical reviews of Computing literature here

Become a reviewer for Computing Reviews.

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 September 1994

Published in TOPLAS Volume 16, Issue 5

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

208
Total Citations
View Citations
1,853
Total Downloads

Downloads (Last 12 months)257
Downloads (Last 6 weeks)36

Reflects downloads up to 02 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Lee SBinkley DFeldt RGold NYoo S(2025)Causal program dependence analysisScience of Computer Programming10.1016/j.scico.2024.103208240(103208)Online publication date: Feb-2025
https://doi.org/10.1016/j.scico.2024.103208
McMichen TGreiner NZhong PSossai FPatel ACampanoni SGrosser TDubach CSteuwer MXue JOttoni GQuintão Pereira F(2024)Representing Data Collections in an SSA FormProceedings of the 2024 IEEE/ACM International Symposium on Code Generation and Optimization10.1109/CGO57630.2024.10444817(308-321)Online publication date: 2-Mar-2024
https://dl.acm.org/doi/10.1109/CGO57630.2024.10444817
Gaidis AMoreira JSun KMilburn AAtlidakis VKemerlis V(2023)FineIBT: Fine-grain Control-flow Enforcement with Indirect Branch TrackingProceedings of the 26th International Symposium on Research in Attacks, Intrusions and Defenses10.1145/3607199.3607219(527-546)Online publication date: 16-Oct-2023
https://dl.acm.org/doi/10.1145/3607199.3607219
Hueckelheim JDoerfert J(2023)ORAQL — Optimistic Responses to Alias Queries in LLVMProceedings of the 52nd International Conference on Parallel Processing10.1145/3605573.3605644(655-664)Online publication date: 7-Aug-2023
https://dl.acm.org/doi/10.1145/3605573.3605644
Fan SHua ZXia YChen HZang BSolihin YHeinrich M(2023)ISA-Grid: Architecture of Fine-grained Privilege Control for Instructions and RegistersProceedings of the 50th Annual International Symposium on Computer Architecture10.1145/3579371.3589050(1-15)Online publication date: 17-Jun-2023
https://dl.acm.org/doi/10.1145/3579371.3589050
Rajagopalan VKleftogiorgos KGöktas EXu JPortokalidis GMeng WJensen CCremers CKirda E(2023)SysPart: Automated Temporal System Call Filtering for BinariesProceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security10.1145/3576915.3623207(1979-1993)Online publication date: 15-Nov-2023
https://dl.acm.org/doi/10.1145/3576915.3623207
Siddiqui AYadav K(2023)A Novel Approach to Pointer Analysis2022 OPJU International Technology Conference on Emerging Technologies for Sustainable Development (OTCON)10.1109/OTCON56053.2023.10113963(1-5)Online publication date: 8-Feb-2023
https://doi.org/10.1109/OTCON56053.2023.10113963
Song SSuneja SLe MTak B(2023)On the Value of Sequence-Based System Call Filtering for Container Security2023 IEEE 16th International Conference on Cloud Computing (CLOUD)10.1109/CLOUD60044.2023.00043(296-307)Online publication date: Jul-2023
https://doi.org/10.1109/CLOUD60044.2023.00043
Song SSuneja SLe MTak B(2023)Sequence-based System Call Filtering for Enhanced Container Security, is it beneficial?2023 IEEE/ACM 23rd International Symposium on Cluster, Cloud and Internet Computing Workshops (CCGridW)10.1109/CCGridW59191.2023.00057(278-280)Online publication date: May-2023
https://doi.org/10.1109/CCGridW59191.2023.00057
Park MLee D(2023)BGCFI: Efficient Verification in Fine-Grained Control-Flow Integrity Based on Bipartite GraphIEEE Access10.1109/ACCESS.2023.323418411(4291-4305)Online publication date: 2023
https://doi.org/10.1109/ACCESS.2023.3234184
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Abstract

References

Cited By

Index Terms

Recommendations

Undecidability of static analysis

Precise flow-insensitive may-alias analysis is NP-hard

Semi-sparse flow-sensitive pointer analysis

Reviews

Access critical reviews of Computing literature here

Comments

Information

Published In

Publisher

Publication History

Permissions

Check for updates

Author Tags

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Get Access

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations