Article

Memory safety without runtime checks or garbage collection

Authors:

Dinakar Dhurjati,

Sumant Kowshik,

Chris LattnerAuthors Info & Claims

LCTES '03: Proceedings of the 2003 ACM SIGPLAN conference on Language, compiler, and tool for embedded systems

Pages 69 - 80

https://doi.org/10.1145/780732.780743

Published: 11 June 2003 Publication History

Abstract

Traditional approaches to enforcing memory safety of programs rely heavily on runtime checks of memory accesses and on garbage collection, both of which are unattractive for embedded applications. The long-term goal of our work is to enable 100% static enforcement of memory safety for embedded programs through advanced compiler techniques and minimal semantic restrictions on programs. The key result of this paper is a compiler technique that ensures memory safety of dynamically allocated memory without programmer annotations, runtime checks, or garbage collection, and works for a large subclass of type-safe C programs. The technique is based on a fully automatic pool allocation (i.e., region-inference) algorithm for C programs we developed previously, and it ensures safety of dynamically allocated memory while retaining explicit deallocation of individual objects within regions (to avoid garbage collection). For a diverse set of embedded C programs (and using a previous technique to avoid null pointer checks), we show that we are able to statically ensure the safety of pointer and dynamic memory usage in all these programs. We also describe some improvements over our previous work in static checking of array accesses. Overall, we achieve 100% static enforcement of memory safety without new language syntax for a significant subclass of embedded C programs, and the subclass is much broader if array bounds checks are ignored. Overall, these techniques greatly expand the class of embedded programs for which 100% static enforcement of memory safety is possible, and furthermore can be achieved without new language support.

References

[1]

T. M. Austin, S. E. Breach, and G. S. Sohi. Efficient detection of all pointer and array access errors. In Proc. SIGPLAN '94 Conf. on Programming Language Design and Implementation, Orlando, FL, June 1994.

Digital Library

[2]

D. Bacon, P. Cheng, and V. Rajan. A real-time garbage collector with low overhead and consisitent utilization. In Proc. 30th ACM Symp. Principles of Programming Languages (POPL03), Jan. 2003.

Digital Library

[3]

R. Bodik, R. Gupta, and V. Sarkar. ABCD: eliminating array bounds checks on demand. In SIGPLAN Conf. on Prog. Lang. Design and Implementation, June 2000.

Digital Library

[4]

G. Bollella and J. Gosling. The real-time specification for Java. Computer, 33(6):47--54, 2000.

Digital Library

[5]

C. Boyapati, A. Salcianu, W. Beebee, and M. Rinard. Ownership types for safe region-based memory management in real-time java. In SIGPLAN Conference on Programming Language Design and Implementation, 2003.

Digital Library

[6]

K. Crary, D. Walker, and G. Morrisett. Typed memory management in a calculus of capabilities. In Conference Record of POPL 99: The 26th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, San Antonio, Texas, pages 262--275, New York, NY, 1999.

Digital Library

[7]

R. DeLine and M. Fahndrich. Enforcing high-level protocols in low-level software. In Proc. SIGPLAN Conf. on Programming Language Design and Implementation, Snowbird, UT, June 2001.

Digital Library

[8]

M. Fahndrich and R. DeLine. Adoption and focus: Practical linear types for imperative programming. In Proc. SIGPLAN Conference on Programming Language Design and Implementation, June 2002.

Digital Library

[9]

D. Gay and A. Aiken. Memory management with explicit regions. In SIGPLAN Conference on Programming Language Design and Implementation, pages 313--323, Montreal, Canada, June 1998.

Digital Library

[10]

J. Gosling, B. Joy, G. Steele, and G. Bracha. The Java Language Specification. Sun Microsystems, 2000.

Digital Library

[11]

D. Grossman, G. Morrisett, T. Jim, M. Hicks, Y. Wang, and J. Cheney. Region-based memory management in cyclone. In Proc. SIGPLAN Conf. on Programming Language Design and Implementation, June 2002.

Digital Library

[12]

M. R. Guthaus, J. S. Ringenberg, D. Ernst, T. M. Austin, T. Mudge, and R. B. Brown. Mibench: A free, commercially representative embedded benchmark suite. In IEEE 4th Annual Workshop on Workload Characterization, Austin, TX, Dec. 2001.

Digital Library

[13]

T. Jim, G. Morrisett, D. Grossman, M. Hicks, J. Cheney, and Y. Wang. Cyclone: A safe dialect of c. In Proc. USENIX Annual Technical Conference, June 2002.

Digital Library

[14]

W. Kelly, V. Maslov, W. Pugh, E. Rosser, T. Shpeisman, and D. Wonnacott. The Omega Library Interface Guide. Technical report, Computer Science Dept., U. Maryland, College Park, Apr. 1996.

Digital Library

[15]

S. Kowshik, D. Dhurjati, and V. Adve. Ensuring code safety without runtime checks for real-time control systems. In Proc. 2002 Conference on Compilers, Architecture and Synthesis for Embedded Systems, Grenoble, Oct 2002.

Digital Library

[16]

C. Lattner. LLVM: An infrastructure for multi-stage optimization. Master's thesis, Computer Science Dept., University of Illinois at Urbana-Champaign, Urbana, IL, Dec 2002. See http://llvm.cs.uiuc.edu.

[17]

C. Lattner and V. Adve. Automatic Pool Allocation for Disjoint Data Structures. In Proc. ACM SIGPLAN Workshop on Memory System Performance, Berlin, Germany, Jun 2002.

Digital Library

[18]

C. Lattner and V. Adve. Data structure analysis: An efficient context-sensitive heap analysis. Tech. Report UIUCDCS-R-2003-2340, Computer Science Dept., Univ. of Illinois at Urbana-Champaign, Apr 2003.

[19]

C. Lee, M. Potkonjak, and W. H. Mangione-Smith. Mediabench: A tool for evaluating and synthesizing multimedia and communicatons systems. In International Symposium on Microarchitecture, pages 330--335, 1997.

Digital Library

[20]

P. Levis and D. Culler. Mate: A tiny virtual machine for sensor networks. In International Conference on Architectural Support for Programming Languages and Operating Systems, San Jose, CA, USA, Oct. 2002.

Digital Library

[21]

G. C. Necula. Proof-carrying code. In Proc. of the 24th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Langauges (POPL '97), Paris, Jan. 1997.

Digital Library

[22]

G. C. Necula, S. McPeak, and W. Weimer. Ccured: Type-safe retrofitting of legacy code. In Proc. 29th ACM Symp. Principles of Programming Languages (POPL02), London, Jan. 2002.

Digital Library

[23]

L. Sha. Dependable system upgrades. In Proceedings of IEEE Real Time System Symposium, 1998.

Digital Library

[24]

L. Sha. Using simplicity to control complexity. IEEE Software, July/August 2001.

Digital Library

[25]

M. Tofte and L. Birkedal. A region inference algorithm. ACM Trans. Prog. Lang. Sys., 20(1), 1998.

Digital Library

[26]

M. Tofte and J.-P. Talpin. Region-based memory management. Information and Computation, pages 132(2):109--176, Feb. 1997.

Digital Library

[27]

D. Wagner, J. S. Foster, E. A. Brewer, and A. Aiken. A first step towards automated detection of buffer overrun vulnerabilities. In Network and Distributed System Security Symposium, pages 3--17, San Diego, CA, February 2000.

[28]

D. Walker and G. Morrisett. Alias types for recursive data structures. Lecture Notes in Comp. Sci., vol. 2071, 2001.

Digital Library

Cited By

Ullah SRashid A(2024)Porting to Morello: An In-depth Study on Compiler Behaviors, CERT Guideline Violations, and Security Implications2024 IEEE 9th European Symposium on Security and Privacy (EuroS&P)10.1109/EuroSP60621.2024.00028(381-397)Online publication date: 8-Jul-2024
https://doi.org/10.1109/EuroSP60621.2024.00028
Wang RXu MAsokan N(2024)S2malloc: Statistically Secure Allocator for Use-After-Free Protection and MoreDetection of Intrusions and Malware, and Vulnerability Assessment10.1007/978-3-031-64171-8_2(23-43)Online publication date: 9-Jul-2024
https://doi.org/10.1007/978-3-031-64171-8_2
Chen HChen HSun MLi KChen ZWang XCalandrino JTroncoso C(2023)A verified confidential computing as a service framework for privacy preservationProceedings of the 32nd USENIX Conference on Security Symposium10.5555/3620237.3620502(4733-4750)Online publication date: 9-Aug-2023
https://dl.acm.org/doi/10.5555/3620237.3620502
Show More Cited By

Index Terms

Memory safety without runtime checks or garbage collection

Recommendations

Memory safety without garbage collection for embedded applications

Traditional approaches to enforcing memory safety of programs rely heavily on run-time checks of memory accesses and on garbage collection, both of which are unattractive for embedded applications. The goal of our work is to develop advanced compiler ...
Memory safety without runtime checks or garbage collection
Special Issue: Proceedings of the 2003 ACM SIGPLAN conference on Language, compiler, and tool support for embedded systems (San Diego, CA).

Traditional approaches to enforcing memory safety of programs rely heavily on runtime checks of memory accesses and on garbage collection, both of which are unattractive for embedded applications. The long-term goal of our work is to enable 100% static ...
Garbage collection without paging
Proceedings of the 2005 ACM SIGPLAN conference on Programming language design and implementation

Garbage collection offers numerous software engineering advantages, but interacts poorly with virtual memory managers. Existing garbage collectors require far more pages than the application's working set and touch pages without regard to which ones are ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

LCTES '03: Proceedings of the 2003 ACM SIGPLAN conference on Language, compiler, and tool for embedded systems

June 2003

304 pages

ISBN:1581136471

DOI:10.1145/780732

General Chair:
Frank Mueller
North Carolina State University
,
Publications Chair:
Uli Kremer
Rutgers University

ACM SIGPLAN Notices Volume 38, Issue 7
Special Issue: Proceedings of the 2003 ACM SIGPLAN conference on Language, compiler, and tool support for embedded systems (San Diego, CA).
July 2003
293 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/780731
Issue’s Table of Contents

Copyright © 2003 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: 11 June 2003

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

LCTES03

Sponsor:

LCTES03: ACM SIGPLAN Symposium on Languages, Compilers, and Tools for Embedded Systems

June 11 - 13, 2003

California, San Diego, USA

Acceptance Rates

LCTES '03 Paper Acceptance Rate 29 of 128 submissions, 23%;

Overall Acceptance Rate 116 of 438 submissions, 26%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

93
Total Citations
View Citations
1,350
Total Downloads

Downloads (Last 12 months)60
Downloads (Last 6 weeks)6

Reflects downloads up to 30 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Ullah SRashid A(2024)Porting to Morello: An In-depth Study on Compiler Behaviors, CERT Guideline Violations, and Security Implications2024 IEEE 9th European Symposium on Security and Privacy (EuroS&P)10.1109/EuroSP60621.2024.00028(381-397)Online publication date: 8-Jul-2024
https://doi.org/10.1109/EuroSP60621.2024.00028
Wang RXu MAsokan N(2024)S2malloc: Statistically Secure Allocator for Use-After-Free Protection and MoreDetection of Intrusions and Malware, and Vulnerability Assessment10.1007/978-3-031-64171-8_2(23-43)Online publication date: 9-Jul-2024
https://doi.org/10.1007/978-3-031-64171-8_2
Chen HChen HSun MLi KChen ZWang XCalandrino JTroncoso C(2023)A verified confidential computing as a service framework for privacy preservationProceedings of the 32nd USENIX Conference on Security Symposium10.5555/3620237.3620502(4733-4750)Online publication date: 9-Aug-2023
https://dl.acm.org/doi/10.5555/3620237.3620502
Klimt JKröning MLankes SMonti A(2023)On the Challenge of Sound Code for Operating SystemsProceedings of the 12th Workshop on Programming Languages and Operating Systems10.1145/3623759.3624554(83-90)Online publication date: 23-Oct-2023
https://dl.acm.org/doi/10.1145/3623759.3624554
Leonardi SAromolo FFara PSerra GCasini DBiondi AButtazzo G(2023)Maximizing the Security Level of Real-Time Software While Preserving Temporal ConstraintsIEEE Access10.1109/ACCESS.2023.326467111(35591-35607)Online publication date: 2023
https://doi.org/10.1109/ACCESS.2023.3264671
Bernhard LRodler MHolz TDavit L(2022)xTag: Mitigating Use-After-Free Vulnerabilities via Software-Based Pointer Tagging on Intel x86-642022 IEEE 7th European Symposium on Security and Privacy (EuroS&P)10.1109/EuroSP53844.2022.00038(502-519)Online publication date: Jun-2022
https://doi.org/10.1109/EuroSP53844.2022.00038
Banerjee SDevecsery DChen PNarayanasamy S(2020)Sound garbage collection for C using pointer provenanceProceedings of the ACM on Programming Languages10.1145/34282444:OOPSLA(1-28)Online publication date: 13-Nov-2020
https://dl.acm.org/doi/10.1145/3428244
Palit TMonrose FPolychronakis M(2020)Mitigating Data-only Attacks by Protecting Memory-resident Sensitive DataDigital Threats: Research and Practice10.1145/34194751:4(1-26)Online publication date: 22-Dec-2020
https://dl.acm.org/doi/10.1145/3419475
Palit TMonrose FPolychronakis MBalenson D(2019)Mitigating data leakage by protecting memory-resident sensitive dataProceedings of the 35th Annual Computer Security Applications Conference10.1145/3359789.3359815(598-611)Online publication date: 9-Dec-2019
https://dl.acm.org/doi/10.1145/3359789.3359815
Das SUnnithan RMenon ARebeiro CVeezhinathan KChen JShrivastava A(2019)SHAKTI-MS: a RISC-V processor for memory safety in CProceedings of the 20th ACM SIGPLAN/SIGBED International Conference on Languages, Compilers, and Tools for Embedded Systems10.1145/3316482.3326356(19-32)Online publication date: 23-Jun-2019
https://dl.acm.org/doi/10.1145/3316482.3326356
Show More Cited By

View Options

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

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents