Memory safety without garbage collection for embedded applications
- 1 February 2005
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Embedded Computing Systems
- Vol. 4 (1), 73-111
- https://doi.org/10.1145/1053271.1053275
Abstract
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 techniques for enforcing memory safety with minimal run-time overheads. In this paper, we describe a set of compiler techniques that, together with minor semantic restrictions on C programs and no new syntax, ensure memory safety and provide most of the error-detection capabilities of type-safe languages, without using garbage collection, and with no run-time software checks, (on systems with standard hardware support for memory management). The language permits arbitrary pointer-based data structures, explicit deallocation of dynamically allocated memory, and restricted array operations. One of the key results of this paper is a compiler technique that ensures that dereferencing dangling pointers to freed memory does not violate memory safety, without annotations, run-time checks, or garbage collection , and works for arbitrary type-safe C programs. Furthermore, we present a new interprocedural analysis for static array bounds checking under certain assumptions. For a diverse set of embedded C programs, we show that we are able to ensure memory safety of pointer and dynamic memory usage in all these programs with no run-time software checks (on systems with standard hardware memory protection), requiring only minor restructuring to conform to simple type restrictions. Static array bounds checking fails for roughly half the programs we study due to complex array references, and these are the only cases where explicit run-time software checks would be needed under our language and system assumptions.Keywords
This publication has 14 references indexed in Scilit:
- Region inference for an object-oriented languageACM SIGPLAN Notices, 2004
- Using simplicity to control complexityIEEE Software, 2001
- Typing a multi-language intermediate codeACM SIGPLAN Notices, 2001
- The real-time specification for JavaComputer, 2000
- A region inference algorithmACM Transactions on Programming Languages and Systems, 1998
- Region-Based Memory ManagementInformation and Computation, 1997
- Efficient software-based fault isolationACM SIGOPS Operating Systems Review, 1993
- Optimizing array bound checks using flow analysisACM Letters on Programming Languages and Systems, 1993
- A practical algorithm for exact array dependence analysisCommunications of the ACM, 1992
- Modula-3 language definitionACM SIGPLAN Notices, 1992