Root Crash Consistency of SGX-style Integrity Trees in Secure Non-Volatile Memory Systems

Data integrity is important for non-volatile memory (NVM) systems that maintain data even without power. The data integrity in NVM may be compromised by integrity attacks, which can be defended against by integrity verification via integrity trees. After NVM system failures and reboots, the integrity tree root is responsible for providing a trusted execution environment. However, updating the root incurs latency to propagate the modifications from leaf nodes to the root. If system crashes occur during the propagation process, the root is inconsistent with the updated leaf nodes, resulting in misreporting the attacks after the system reboots. In this paper, we propose a ShortCut UpdatE scheme, called SCUE, which is an efficient and low-latency scheme to instantaneously update the root on the SGX-style integrity tree (SIT) by judiciously overlooking the updates upon most intermediate tree nodes. The idea behind SCUE explores and exploits the observation that consistent leaf nodes and root are enough to ensure data integrity after system failures and reboots. Moreover, SIT is difficult to be reconstructed from the leaf nodes since updating one tree node needs its parent node as input. Root in SIT thus cannot verify the data after the system crashes and reboots even though the root is correctly updated. To provide the ability of verification via root in SIT, we use a counter-summing approach to efficiently reconstructing the SIT from leaf nodes. Extensive evaluation results show that compared with the state-of-the-art integrity tree update schemes, our SCUE delivers high performance while ensuring data integrity.