UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Bo-tree : a dynamic merkle tree for enabling scalable memories Wang, Bolin


Securing off-chip main-memories is an integral component of trusted-execution environments like Intel SGX. Unfortunately, secure memories that offer replay protection face performance overheads due to the additional memory accesses from traversing multiple levels of the counter integrity tree. While recent works try to reduce these overheads by enabling shorter, higher-arity trees, these approaches do not scale with memory capacities and tree heights. Thus, as we to develop efficient techniques that will continue to maintain short tree-heights and sustain low performance overheads as memory sizes grow. In this thesis, we propose Bo-Tree, an efficient integrity tree design that achieves near-zero traversal overheads. Unlike prior works that are restricted to static tree structures, Bo-Tree dynamically detects “hot” data blocks and collects their counters in a logically separate, smaller tree that can efficiently take advantage of the on-chip metadata cache. A hardware mechanism dynamically adds and removes counters to this hot tree, making the optimization transparent to software. To track frequently accessed blocks with minimal overhead, Bo-Tree uses a probabilistic counting mechanism. We experiment on a 32GB DDR4 secure memory, Bo-Tree on average provides a speedup of 17.1% over prior work SC-64 over all SPEC-2006 and GAP workloads, while incurring a memory capacity overhead of <1.6%.

Item Media

Item Citations and Data


Attribution-NonCommercial-NoDerivatives 4.0 International