Back to search

University of British Columbia

Bo-tree : a dynamic merkle tree for enabling scalable memories

Abstract

dc:description

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%.

Degree

thesis:*
Name thesis:degree_name
Master of Applied Science - MASc
Level thesis:degree_level
master's
Discipline thesis:degree_discipline
Electrical and Computer Engineering
Grantor dc:publisher
University of British Columbia
Year dc:date
2022

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Wang, Bolin
Contributors dc:contributor
  • Nair, Prashant J.

Rights

dc:rights
Statement dc:rights
  • Attribution-NonCommercial-NoDerivatives 4.0 International
Language dc:language
eng

Identifiers

dc:identifier.*
Handle dc:identifier
http://hdl.handle.net/2429/81203

Chain of custody

source
Harvested from
University of British Columbia
Base URL
circle.library.ubc.ca/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Wang, Bolin. Bo-tree : a dynamic merkle tree for enabling scalable memories. master's thesis, University of British Columbia, 2022. http://hdl.handle.net/2429/81203