Skip to Main content Skip to Navigation
Conference papers

Fast as a shadow, expressive as a tree: Hybrid memory monitoring for C.

Abstract : One classical approach to ensuring memory safety of C programs is based on storing block metadata in a tree-like datastructure. However it becomes relatively slow when the number of memory locations in the tree becomes high. Another solution, based on shadow memory, allows very fast constant-time access to metadata and led to development of several highly optimized tools for detection of memory safety errors. However, this solution appears to be insufficient for evaluation of complex memory-related properties of an expressive specification language. In this work, we address memory monitoring in the context of runtime assertion checking of C programs annotated in E-ACSL, an expressive specification language offered by the FRAMA-C framework for analysis of C code. We present an original combination of a tree-based and a shadow-memory-based techniques that reconciles both the efficiency of shadow memory with the higher expressiveness of annotations whose runtime evaluation can be ensured by a tree of metadata. Shadow memory with its instant access to stored metadata is used whenever small shadow metadata suffices to evaluate required annotations, while richer metadata stored in a compact prefix tree (Patricia trie) is used for evaluation of more complex memory annotations supported by E-ACSL. This combined monitoring technique has been implemented in the runtime assertion checking tool for E-ACSL. Our initial experiments confirm that the proposed hybrid approach leads to a significant speedup with respect to an earlier implementation based on a Patricia trie alone without any loss of precision.
Document type :
Conference papers
Complete list of metadata
Contributor : Léna Le Roy <>
Submitted on : Thursday, July 12, 2018 - 11:00:06 AM
Last modification on : Friday, April 30, 2021 - 9:53:02 AM




A. Jakobsson, N. Kosmatov, J. Signoles. Fast as a shadow, expressive as a tree: Hybrid memory monitoring for C.. SAC '15 Proceedings of the 30th Annual ACM Symposium on Applied Computing, Apr 2015, Salamanca, Spain. pp.1765-1772, ⟨10.1145/2695664.2695815⟩. ⟨cea-01836267⟩



Record views