Bounded pointer
In computer science, a bounded pointer is a pointer that is augmented with additional information that enable the storage bounds within which it may point to be deduced.[1] This additional information sometimes takes the form of two pointers holding the upper and lower addresses of the storage occupied by the object to which the bounded pointer points.
Use of bound information makes it possible for a compiler to generate code that performs bounds checking, i.e. that tests if a pointer's value lies within the bounds prior to dereferencing the pointer or modifying the value of the pointer. If the bounds are violated some kind of exception may be raised. This is especially useful for data constructs such as arrays in C.
Implementation
[edit]Bounded pointers can be implemented in either software or hardware. SoftBound is an example of a software-based implementation of this data type. It stores the metadata as a separate data structure rather than storing it in the pointer itself. The metadata of a pointer includes the bounds associated with each pointer. Any time a pointer is created, copied, or assigned, the structure is updated. During program execution, SoftBound uses the metadata to check if the pointer operations remain in the allowed bounds.[2]
An example of a hardware-based implementation of this data type is HardBound. It stores the upper and lower bounds of the possible data address in a separate hardware structure, rather than with the pointer. During memory operations, the hardware checks whether the pointer value is in its allowed bounds. If the pointer value is not within the acceptable range, the hardware raises an exception and prevents the operation from continuing.[3]
These implementations are not the only ones; other implementations of bounds-checking have also been developed.
Advantages
[edit]The main advantage of bounded pointers is their ability to detect spatial memory safety violations. The violations can include trying to access memory outside of the allowed bounds. Bounded pointers connect the pointer with bounds of memory which makes it able to detect when a program goes out of bounds in languages that do not do this automatically.[2][3]
It was primarily implemented for C due to the method's ability to find spatial violations, which are common in lower-level programming. Bounds checking is most useful when working with arrays and dynamically allocated memory. With a way to recognize when a pointer is going outside of the allowed bounds, bounded pointers became helpful in preventing errors. When allocating data in C and other lower-level languages, it's easy to write over memory unintentionally, or try to access memory that doesn't exist.[1]
Standard pointers do not check the available data, so it was intentionally the programmer's responsibility to know what was left to be allocated. With bounded pointers there is no longer a need for programmers to manually check if the pointers will remain in the allocated storage. This can make it easier for the programmers to detect and debug memory related errors.[2][3]
Limitations
[edit]Safety
[edit]HardBound does not provide full type safety, rather it provides just enough type safety to enforce full spatial memory safety. HardBound also does not solve temporal memory safety errors; this limitation of primarily focusing on spatial memory safety means that HardBound does not solve a majority of error sources commonplace in C programs, such as type safety violations (via unsafe casts), and temporal memory safety violations (due to dangling pointers, uninitialized reads, and the misuse of free)[3]
Another limitation is that HardBound is a hardware/software approach, and thus only guarantees memory safety if and only if the compiler does too; an incorrect compiler implementation may produce unsafe resulting binary code.[3]
Ambiguity
[edit]Some pointer-bounding situations are ambiguous; this happens when the compiler cannot infer the intended bounds, such as deciding whether to propagate the bounds of an entire array or to shrink to the sub-bounds of what is used within the array.[3] As such, the compiler has to act "conservatively" and not shrink the bounds.
History
[edit]Early Work (1990s)
[edit]The first practical bounded pointer systems appeared in the mid-90s as compiler extensions for C, one of the earliest being Richard Jones and Paul Kelly's work on bounds-checking, which tracked the "intended referent" of pointers while remaining compatible with existing C programs.[4]
Later Developments (Late 1990s - early 2000s)
[edit]In 2002, a new programming language Cyclone (dubbed a "safe dialect of C"), implemented by Trevor Jim et al., added "fat pointers," described as pointers that explicitly carried their bounds as metadata. This method added overhead to programs as the fat pointers took up more space than other pointers due to their inserted bounds checks. However, they ensured safety, "giv[ing] the programmer new capabilities."[5]
Hardware Support (2000s)
[edit]By the mid-2000s, research had moved bounds metadata into hardware to reduce the runtime overhead. This was formalized by HardBound, a hardware implementation of the bounded pointer. Instead of storing the bounds as metadata, HardBound stores the bounds data in a disjoint shadow space, performs implicit checks on the bounds data as it is transferred and referenced throughout the memory, and reduced the overhead by caching and compressing the pointer encodings. This allowed many such bounded pointers to be stored using only a few additional bits.[3]
See also
[edit]References
[edit]- 1 2 Reese, Richard (2013). Understanding and Using C Pointers: Core Techniques for Memory Management. O'Reilly Media, Inc. p. 167. ISBN 9781449344566.
- 1 2 3 Nagarakatte, Santosh; Zhao, Jianzhou; Martin, Milo M.K.; Zdancewic, Steve (2009-05-28). "SoftBound". ACM SIGPLAN Notices. 44 (6): 245–258. doi:10.1145/1543135.1542504. ISSN 0362-1340. Archived from the original on 2025-11-25.
- 1 2 3 4 5 6 7 Devietti, Joe; Blundell, Colin; Martin, Milo M. K.; Zdancewic, Steve (2008-03-25). "Hardbound: architectural support for spatial safety of the C programming language". ACM SIGPLAN Notices. 43 (3): 103–114. doi:10.1145/1353536.1346295. ISSN 0362-1340.
- ↑ Jones, Richard; Kelly, Paul (2002-05-16). "Backwards-compatible bounds checking for arrays and pointers in C programs". Proceedings of the 3rd International Workshop on Automatic Debugging; 1997 (AADEBUG-97).
- ↑ Jim, Trevor; Morrisett, Greg; Grossman, Dan; Hicks, Michael; Cheney, James; Wang, Yanling (2002). "Cyclone: A Safe Dialect of C". Proc. of the 2002 USENIX Annual Technical Conference: 275–288.