Article

Free access

Alias analysis of executable code

Authors:

Matthew WeippertAuthors Info & Claims

POPL '98: Proceedings of the 25th ACM SIGPLAN-SIGACT symposium on Principles of programming languages

Pages 12 - 24

https://doi.org/10.1145/268946.268948

Published: 21 January 1998 Publication History

Abstract

Recent years have seen increasing interest in systems that reason about and manipulate executable code. Such systems can generally benefit from information about aliasing. Unfortunately, most existing alias analyses are formulated in terms of high-level language features, and are unable to cope with features, such as pointer arithmetic, that pervade executable programs. This paper describes a simple algorithm that can be used to obtain aliasing information for executabie code. In order to be practical, the algorithm is carefut to keep its memory requirements low, sacrificing precision where necessary to achieve this goal. Experimental results indicate that it is nevertheless able to provide a reasonable amount of information about memory references across a variety of benchmark programs.

References

[1]

A. V. Aho, P~ Sethi and J. D. Ullman, Compilers- Principles, Techniques and Tools, Addison- Wesley, 1986.

Digital Library

[2]

J. E. Barnes and P. Hut, "A Hierarchical O(NlogN) Force Calculation Algorithm", Nature, 324~ 1986.

[3]

D. R. Chase, M. Wegrnan, and F. K. Zadeck, "Analysis of Pointers and Structures", Proc. SIG- PLAN '90 Con}erence on Programming Languaga Des~Tn and Implementation, June 1990, pp. 296- 310.

Digital Library

[4]

J.-D. Choi, M. Burke, and P. Carini, "Efficient Flow-Sensitive Interprocedural Computation of Pointer-Induced Aliases and Side Effects", Proc. 2Oth A CM Symposium on Principles of Programming Languages, Jan. 1993, pp. 232-245.

Digital Library

[5]

R. Cohn, D. Goodwin, P. G. Lowney~ and N. Rubin, "Spike: An Optimizer for Alpha/NT Executables", Proc. USENIX Windows NT Workshop, Aug. 1997.

Digital Library

[6]

K. D. Cooper and K. Kennedy, "Fast Interprocedural Alias Analysis", Proc. 16th ACM Symposium on Principles of Programming Languages, Jan. 1989, pp. 49-59.

Digital Library

[7]

K. D. Cooper and J. Lu, "Register Promotion in C Programs", Proc. SIGPLAN '97 Conference on Programming Language Design and Implementation, June 1997, pp. 308-319.

Digital Library

[8]

P. Cousot and R. Cousot, "Abstract Interpretation: k Unified Lattice Model for Static Analysis of Programs by Construction or Apporoximation of Fixpoints', Proe. Fourth A CM Symposium on Principles of Programming Languages, 1977, pp. 238-252.

Digital Library

[9]

D. Coutant, "Retargetable High-Level Alias Analysis", Proe. 13th ACId Symposium on Principles of Pro#ramming Langua#es, Jan. 1986, pp. 110- 118.

Digital Library

[10]

K. De Bosschere and S. K. Debray, %ito : A Link-Time Optimizer for the DEC Alpha", Technical Report 96-15, Dept. of Computer Science, The University of Arizona, June 1996.

Digital Library

[11]

A. Deutsch, "On determining lifetime and aliasing of dynamically allocated data in higher-order functional specifications", Proc. 17th ACre Symposium on Principles of Programming Languages, Jan. 1990, pp. 157-168.

Digital Library

[12]

A. Deutseh, "Interproeedural May-Alias Analysis for Pointers: Beyond k-limiting", Proc. SIGPLAN '94 Conference on Programming Language Design and Implementation, June 1994, pp. 230-241.

Digital Library

[13]

A. Diwan, K. S. McKinley and J. E. B. Moss, "Type-Based Alias Analysis", Manuscript, Dept. of Computer Science, University of Massachusetts, Amherst, 1996.

[14]

M. Emami, R. Ghiya and L. J. Hendren, "Context-Sensitive Interproeedural Points-to Analysis in the Presence of Function Pointers", Proe. 8IGPLAN '94 Conference on Programming Language Design and Implementation, June 1994, pp. 242-256.

Digital Library

[15]

M. F. Fernandez, "Simple and Etfeetive Link- Time Optimization of Modula-3 Programs", Proc. SIGPLAN '95 Conference on Programming Language Design and Implementation, June 1995, pp. 103-115.

Digital Library

[16]

D. W. Goodwin, "Interprocedural Datatiow Analysis in an Executable Optimizer", Proc. SIG- PLAN '97 Conference on Programming Language Design and Implementation, June 1997, pp. 122- 133.

Digital Library

[17]

R. L. Graham, D. E. Knuth, and O. Patashnik, Concrete Mathematics, Addison-Wesley, 1989.

Digital Library

[18]

S. Horwitz, P. Pfeiffer, and T. Reps, "Dependence Analysis for Pointer Variables", Proc. SIGPLAN '89 Conference on Programming Language Design and Implementation, June 1989, pp. 28--40.

Digital Library

[19]

J. Hummel, L. J. Hendren, and A. Nieolau, "A General Data Dependence Test for Dynamic, Pointer-Based Data Structures", Proc. SIGPLAN "94 Conference on Programming Language Design and Implementation, June 1994, pp. 218-229.

Digital Library

[20]

M. S. Johnson and T. C. Miller, "Effectiveness of a M~e-Level Global Optimizer", Proc. SIC- PLAN '86 Symposium on Compiler Construction, June 1986, pp. 99-108.

Digital Library

[21]

N. D. Jones and S. S. Muchnick, "Flow analysis and optimization of LISP-like structures", in Program Flow Analysis, eds. S. S. Muehnick and N. D. Jones, Prentice Hall, 1981, pp. 102-131.

[22]

N. D. Jones and S. S. Muehnick, "A flexible approach to interprocedural data flow analysis and programs with recursive data structures", Proc. 9th A UM Symposium on Principles of Programming Languages, Jan. 1982, pp. 66-74

Digital Library

[23]

W. Landi and B. G. Ryder, "Pointer-induced Aliasing: A Problem Classification", Proc. 18th A UM Symposium on Principles of Programming Languages, Jan. 1991, pp. 93-103.

Digital Library

[24]

W. Landi and B. G. Ryder, "A Safe Approximate Algorithm for Interprocedural Pointer Aliasing', Proc. SIGPLAN 'g2 Conference on Programming Language Design and Implementation, June 1992, pp. 235--248.

Digital Library

[25]

J. R. Larus and E. Schnarr, "EEL: Machineindependent Executable Editing", Proc. SIC-" PLAN "95 Conference on Programming Language Design and Implementation, June 1995, pp. 291- 300.

Digital Library

[26]

J. R. Larus and P. N. Hilfinger, "Detecting Conflicts Between Structure Accesses", Proe. SIC,- PLAN '88 Conference on Programming Language Design and Implementation, June 1988, pp. 21- 34.

Digital Library

[27]

T. Romer, G. Voelker, D. Lee, A. Wolman, W. Wong, H. Levy, B. N. Bershad, and J. B. Chen, "Instrumentation and Optimization of Win32/Intel Executables", 1997 USENIX Windows NT Workshop (to appear).

Digital Library

[28]

E. Ruf, "Context-Insensitive Alias Analysis Reconsidered", Proc. SIGPLAN '95 Conference on Programming Language Design and Implementation, June 19953 pp. 13-22.

Digital Library

[29]

M. Shapiro and S. Horwitz, "Fast and Accurate Flow-Insensitive Points-To Analysis", Proc. Mth. A GM Symposium on Principles of Programming Languages, Jan. 1997, pp. 1-14.

Digital Library

[30]

A. Srivastava and D. W. Wall, "A Practical System for Iatermodule Code Optimization at Link-Time", Journal of Programming Languages, pp. 1-18, March 1993.

[31]

A. Srivastava and D. W. Wall, ::Link-time Optimization of Address Calculation on a 64-bit Architecture", Proc. SIGPLAN "9~ Conference Pro- 9ramming Language Design and Implementation, June 1994, pp. 49-60.

Digital Library

[32]

B. Steensgaard, "Points-to Analysis in Almost Linear Time", Proc. 23th. A CM Symposium on Principles of Programming Languages, Jan. 1996, pp. 32-41

Digital Library

[33]

D. W. Wall, "Global Register Allocation at Link Time", Proc. SIGPLAN '86 Symposium on Compiler Construction, July 1986, pp. 264-275.

Digital Library

[34]

W. E. Weihl, "Interprocedural data flow analysis in the presence of pointers, procedure variables, and label variables", Proc. A GM Symposium on Principles of Programming Languages, Jan. 1980, pp. 83-94.

Digital Library

[35]

R. P. Wilson and M. S. Lain, "Efficient Context- Sensitive Pointer Analysis for C Programs", Proc. SIGPLAN "95 Conference on Profframming Language Design and Implementation, June 1995, pp. 1-12.

Digital Library

[36]

M. Wolfe, Optimizing Supercampilers for Supercomputers, M'IT Press, Cambridge, Mass., 1989.

Digital Library

[37]

S. Wu and U. Manber, "Agrep- A Fast Approximate Pattern-Matching Tool", Usenix Winter 1992 Technical Conference, San Francisco, Jan. 1992, pp. 153-162.

[38]

H. Zima and B. Chapman, Supercompilers for Parallel and Vector Gomputer% ACM Press, New York, 1991.

Cited By

He DXie DWang YYou WLiang BHuang JShi WZhang ZZhang XChristakis MPradel M(2024)Define-Use Guided Path Exploration for Better Forced ExecutionProceedings of the 33rd ACM SIGSOFT International Symposium on Software Testing and Analysis10.1145/3650212.3652128(287-299)Online publication date: 11-Sep-2024
https://dl.acm.org/doi/10.1145/3650212.3652128
Frantz MXiao YPias TMeng NYao D(2024)Methods and Benchmark for Detecting Cryptographic API Misuses in PythonIEEE Transactions on Software Engineering10.1109/TSE.2024.337718250:5(1118-1129)Online publication date: May-2024
https://doi.org/10.1109/TSE.2024.3377182
Cheng KZheng YLiu TGuan LLiu PLi HZhu HYe KSun LJust RFraser G(2023)Detecting Vulnerabilities in Linux-Based Embedded Firmware with SSE-Based On-Demand Alias AnalysisProceedings of the 32nd ACM SIGSOFT International Symposium on Software Testing and Analysis10.1145/3597926.3598062(360-372)Online publication date: 12-Jul-2023
https://dl.acm.org/doi/10.1145/3597926.3598062
Show More Cited By

Index Terms

Alias analysis of executable code
1. Computer systems organization
  1. Architectures
    1. Parallel architectures
      1. Very long instruction word
    2. Serial architectures
      1. Complex instruction set computing
      2. Reduced instruction set computing
2. Software and its engineering
  1. Software notations and tools
    1. Compilers
    2. General programming languages
      1. Language features
        Procedures, functions and subroutines

Recommendations

Demand-driven alias analysis for C
POPL '08: Proceedings of the 35th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages

This paper presents a demand-driven, flow-insensitive analysisalgorithm for answering may-alias queries. We formulate thecomputation of alias queries as a CFL-reachability problem, and use this formulation to derive a demand-driven analysis algorithm. ...
Interprocedural pointer alias analysis

We present practical approximation methods for computing and representing interprocedural aliases for a program written in a language that includes pointers, reference parameters, and recursion. We present the following contributions: (1) a framework ...
Speculative Alias Analysis for Executable Code
PACT '02: Proceedings of the 2002 International Conference on Parallel Architectures and Compilation Techniques

Optimizations performed at link time or directly applied to final program executables have received increased attention in recent years. Such low-level optimizations can benefit greatly from pointer alias information. However, as almost all existing ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

POPL '98: Proceedings of the 25th ACM SIGPLAN-SIGACT symposium on Principles of programming languages

January 1998

403 pages

ISBN:0897919793

DOI:10.1145/268946

Chairmen:
David B. MacQueen
Bell Labs
,
Luca Cardelli
Digital Equipment Corp.

Copyright © 1998 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 21 January 1998

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

POPL98

Sponsor:

POPL98: Symposium on Principles of Programming Languages

January 19 - 21, 1998

California, San Diego, USA

Acceptance Rates

POPL '98 Paper Acceptance Rate 32 of 175 submissions, 18%;

Overall Acceptance Rate 824 of 4,130 submissions, 20%

Upcoming Conference

POPL '25

Sponsor:
sigplan

The 52nd Annual ACM SIGPLAN Symposium on Principles of Programming Languages

January 19 - 25, 2025

Denver , CO , USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

139
Total Citations
View Citations
301
Total Downloads

Downloads (Last 12 months)171
Downloads (Last 6 weeks)17

Reflects downloads up to 02 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

He DXie DWang YYou WLiang BHuang JShi WZhang ZZhang XChristakis MPradel M(2024)Define-Use Guided Path Exploration for Better Forced ExecutionProceedings of the 33rd ACM SIGSOFT International Symposium on Software Testing and Analysis10.1145/3650212.3652128(287-299)Online publication date: 11-Sep-2024
https://dl.acm.org/doi/10.1145/3650212.3652128
Frantz MXiao YPias TMeng NYao D(2024)Methods and Benchmark for Detecting Cryptographic API Misuses in PythonIEEE Transactions on Software Engineering10.1109/TSE.2024.337718250:5(1118-1129)Online publication date: May-2024
https://doi.org/10.1109/TSE.2024.3377182
Cheng KZheng YLiu TGuan LLiu PLi HZhu HYe KSun LJust RFraser G(2023)Detecting Vulnerabilities in Linux-Based Embedded Firmware with SSE-Based On-Demand Alias AnalysisProceedings of the 32nd ACM SIGSOFT International Symposium on Software Testing and Analysis10.1145/3597926.3598062(360-372)Online publication date: 12-Jul-2023
https://dl.acm.org/doi/10.1145/3597926.3598062
Khan AXu DTian D(2023)Low-Cost Privilege Separation with Compile Time Compartmentalization for Embedded Systems2023 IEEE Symposium on Security and Privacy (SP)10.1109/SP46215.2023.10179388(3008-3025)Online publication date: May-2023
https://doi.org/10.1109/SP46215.2023.10179388
Hu XBurgstaller BScholz B(2023)EVMTracer: Dynamic Analysis of the Parallelization and Redundancy Potential in the Ethereum Virtual MachineIEEE Access10.1109/ACCESS.2023.326727711(47159-47178)Online publication date: 2023
https://doi.org/10.1109/ACCESS.2023.3267277
Sun RGuo YWang ZZeng Q(2023)AttnCall: Refining Indirect Call Targets in Binaries with AttentionComputer Security – ESORICS 202310.1007/978-3-031-51482-1_20(391-409)Online publication date: 25-Sep-2023
https://dl.acm.org/doi/10.1007/978-3-031-51482-1_20
Pei KShe DWang MGeng SXuan ZDavid YYang JJana SRay BRoychoudhury ACadar CKim M(2022)NeuDep: neural binary memory dependence analysisProceedings of the 30th ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering10.1145/3540250.3549147(747-759)Online publication date: 7-Nov-2022
https://dl.acm.org/doi/10.1145/3540250.3549147
Gupta SRose ABansal S(2020)Counterexample-guided correlation algorithm for translation validationProceedings of the ACM on Programming Languages10.1145/34282894:OOPSLA(1-29)Online publication date: 13-Nov-2020
https://dl.acm.org/doi/10.1145/3428289
Abrath BCoppens BBroeck JWyseur BCabutto AFalcarin PSutter B(2020)Code Renewability for Native Software ProtectionACM Transactions on Privacy and Security10.1145/340489123:4(1-31)Online publication date: 25-Aug-2020
https://dl.acm.org/doi/10.1145/3404891
Altinay ANash JKroes TRajasekaran PZhou DDabrowski AGens DNa YVolckaert SGiuffrida CBos HFranz MBilas AMagoutis KMarkatos EKostic DSeltzer M(2020)BinRecProceedings of the Fifteenth European Conference on Computer Systems10.1145/3342195.3387550(1-16)Online publication date: 15-Apr-2020
https://dl.acm.org/doi/10.1145/3342195.3387550
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Get Access

Login options

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

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents