Project

Back to overview

PersiST: In-Memory Persistent Data Structures for High-Performance Secure Computing

English title PersiST: In-Memory Persistent Data Structures for High-Performance Secure Computing
Applicant Felber Pascal
Number 178822
Funding scheme Project funding (Div. I-III)
Research institution Institut d'informatique Université de Neuchâtel
Institution of higher education University of Neuchatel - NE
Main discipline Information Technology
Start/End 01.09.2018 - 31.08.2022
Approved amount 766'106.00
Show all

Keywords (6)

Concurrency; Data stores; NVRAM; Persistence; Security; Dependability

Lay Summary (French)

Lead
La mémoire vive non volatile (NVRAM) adressable par octet est une technologie émergente qui est persistante lors d'une interruption de l'alimentation (au contraire de la DRAM), qui propose un accès rapide et fin à la mémoire (au contraire des disques durs), et qui promet d'excellentes performances (supérieures de plusieurs ordres de grandeur à la mémoire flash). Elle est particulièrement intéressante pour les structures de données en mémoire partagée qui sont au cœur de nombreux composants clés d’infrastructure. Cependant la plupart des structures de données ne sont pas persistantes et, par conséquent, elles n’ont pas été conçues pour tolérer des défaillances ou des altérations, qu’elles soient accidentelles ou malveillantes. Les techniques traditionnelles comme la journalisation sur une unité de stockage engendrent un surcoût important en termes de performance, tant lors de l’exécution normale que lors d’une reprise après défaillance.
Lay summary
L’objectif du projet PersiST est de concevoir et mettre en œuvre des structures de données et des algorithmes performants, concurrents et sécurisés à même de tirer profit des capacités de la mémoire vive non volatile (NVRAM). La principale cible de telles structures est de favoriser le stockage et le traitement de grandes masses de données (« big data »).

Nous explorerons plus précisément trois axes de recherche complémentaires qui seront menés en parallèle durant le projet et évalués conjointement dans le contexte du stockage de données volumineuses.

Dans le premier axe, nous examinerons, concevrons et mettrons en œuvre des structures de données persistantes (ou PDTs pour « Persistent Data Types »), ainsi que des algorithmes appropriés permettant d’exploiter le potentiel de la NVRAM. L’objectif est de développer un ensemble de PDTs proposant divers compromis en termes de performance et de robustesse, et qui soient directement utilisables par des applications exigeantes en données. Ces PDTs iront de structures simples et polyvalentes comme des listes, des queues ou des tables de hachage, en passant par des structures spécialisées pour certains types de données comme des arbres ou des graphes.

Dans le deuxième axe, nous nous concentrerons sur la performance et le passage à l’échelle en étudiant comment les PDTs peuvent être accédées de manière concurrente par un grand nombre de fils d’exécution dans les systèmes multi-cœurs. Ce problème est loin d’être trivial car les structures de données doivent rester cohérentes en tout temps et dans leur intégralité—pas uniquement au niveau des emplacements de mémoire individuels—malgré les accès concurrents, de manière à permettre une récupération après un défaillance. Dans le cas contraire, les fils d’exécution pourraient ne pas observer le même état avant et après le redémarrage car les effets d’une opération partiellement exécutée en NVRAM persistent au-delà des défaillances, à la différence de la mémoire volatile.

Dans le troisième axe, nous sécuriserons ces PDTs en mémoire en les protégeant des attaques, même dans le cas où des logiciels malveillants essaieraient d’altérer des logiciels système authentiques afin d’acquérir des niveaux de privilège plus élevés. Ce problème est particulièrement préoccupant pour la NVRAM car les données sont préservées même lorsque le système est arrêté brutalement. Cela permettrait à un attaquant d’accéder facilement aux données sensibles en lisant le contenu de la NVRAM d’un système qui aurait été arrêté intentionnellement avant qu’une quelconque mesure de sécurité ne soit appliquée (p.ex. le chiffrement). Il nous faut par conséquent des mécanismes permettant de préserver la confidentialité des données (contre la divulgation) et leur intégrité (contre la falsification), mais sans pour autant compromettre la performance.
Direct link to Lay Summary Last update: 03.06.2018

Lay Summary (English)

Lead
Non-volatile byte-addressable memory (NVRAM) is an emerging technology that is persistent upon power loss (unlike DRAM), provides fast and fine-granular access to memory (unlike disk), and promises high performance (orders of magnitude faster than flash memory). It combines the best features of traditional RAM and disk storage, but it cannot readily be used as a drop-in replacement and therefore also introduces a paradigm shift for developers. NVRAM is of particular interest for shared-memory data structures, which are at the core of many key infrastructure components, such as in-memory databases, key-value stores, and graph processing engines. Yet, most shared-memory data structures are not persistent and, hence, not designed to tolerate failures or corruption (accidental or malicious). Traditional techniques such as logging to storage come with significant performance overheads, both during normal-case operations and during recovery.
Lay summary
The objective of the PersiST project is to design and implement high-performance, concurrent and secure data structures and algorithms that can leverage the capabilities of NVRAM. The primary target of such structures is to support big-data storage and processing.

We will specifically explore three complementary research directions, which will be conducted in parallel during the course of the project and will be jointly evaluated in the context of big data stores.

First, we will investigate, design, and implement persistent data structures/types (PDTs) and associated algorithms that leverage efficiently the capabilities of NVRAM. The objective is to provide a collection of PDTs that provide different trade-offs in terms of performance and robustness, and are readily applicable for data-intensive applications. These PDTs will range from simple, general-purpose structures such as lists, queues, or hash tables to specialized data-oriented structures like search trees or graphs. We will also identify the challenges and devise guidelines for transforming traditional algorithms designed for volatile memory so that they can best exploit NVRAM.

Second, we will focus on performance and scalability by investigating how PDTs can be safely accessed concurrently by large number of threads in multi-core systems. This is far from being trivial as data structures must be maintained consistent at all time as a whole—not just at the level of individual memory locations—despite concurrent accesses, in order to support safe recovery after a failure. Otherwise threads might not see the same state before and after power loss, because the effects of a partially-executed operation in NVRAM persist across failures unlike with volatile memory. To address this challenge, we will in particular study the notion of transactional persistence by leveraging the principles of "transactional memory", which is supported in hardware in recent processors.

Third, we will secure these PDTs in-memory, guarding them from attacks, even in the case where rogue software would be able to subvert legitimate system software to gain amplified privilege levels. This is of particular concern for NVRAM as data is kept persistent even if the system is abruptly turned off. This would allow an attacker to easily gain access to sensitive data by reading the state of NVRAM of a system that was intentionally terminated before any security measure was applied (e.g., encryption). Hence one need mechanisms to preserve data confidentiality (against disclosure) and integrity (against tampering), but without compromising performance. To that end, we will notably study the use of hardware extensions like Intel's software guard extensions (SGX) or AMD's secure memory encryption (SME).
Direct link to Lay Summary Last update: 03.06.2018

Responsible applicant and co-applicants

Employees

Abstract

Non-volatile byte-addressable memory (NVRAM) is an emerging technology that is persistent upon power loss (unlike DRAM), provides fast and fine-granular access to memory (unlike disk), and promises high performance (orders of magnitude faster than flash memory). It combines the best features of traditional RAM and disk storage, but it cannot readily be used as a drop-in replacement and therefore also introduces a paradigm shift for developers. NVRAM is of particular interest for shared-memory data structures, which are at the core of many key infrastructure components, such as in-memory databases, key-value stores, and graph processing engines. Yet, most shared-memory data structures are not persistent and, hence, not designed to tolerate failures or corruption (accidental or malicious). Traditional techniques such as logging to storage come with significant performance overheads, both during normal-case operations and during recovery. At the light of these observations, the objective of the PersiST project is to design and implement high-performance, concurrent and secure data structures and algorithms that can leverage the capabilities of NVRAM. The primary target of such structures is to support big-data storage and processing.
-