11institutetext: Monash University, Australia 22institutetext: RMIT
University, Australia 33institutetext: Faculty of Computing and Information
Technology, King Abdulaziz University, Saudi Arabia

# TimeClave: Oblivious In-enclave Time series Processing System

Kassem Bagher 1133 Shujie Cui 11 Xingliang Yuan 11 Carsten Rudolph 11 Xun Yi
22

###### Abstract

Cloud platforms are widely adopted by many systems, such as time series
processing systems, to store and process massive amounts of sensitive time
series data. Unfortunately, several incidents have shown that cloud platforms
are vulnerable to internal and external attacks that lead to critical data
breaches. Adopting cryptographic protocols such as homomorphic encryption and
secure multi-party computation adds high computational and network overhead to
query operations.

We present TimeClave, a fully oblivious in-enclave time series processing
system: TimeClave leverages Intel SGX to support aggregate statistics on time
series with minimal memory consumption inside the enclave. To hide the access
pattern inside the enclave, we introduce a non-blocking read-optimised ORAM
named RoORAM. TimeClave integrates RoORAM to obliviously and securely handle
client queries with high performance. With an aggregation time interval of
$10s$, $2^{14}$ summarised data blocks and 8 aggregate functions, TimeClave
run point query in $0.03ms$ and a range query of 50 intervals in $0.46ms$.
Compared to the ORAM baseline, TimeClave achieves lower query latency by up to
$2.5\times$ and up to $2\times$ throughput, with up to 22K queries per second.

###### Keywords:

Time Series Processing ORAM Intel SGX.

##  1 Introduction

Time series data (TSD) are data points collected over repeated intervals, such
as minutes, hours, or days. Unlike static data, TSD represents the change in
value over time, and analysing it helps understand the cause of a specific
pattern or trend over time. Studies have been conducted in various fields on
TSD to build efficient time series systems, to name a few, healthcare [1, 2],
smart home [1, 3], and smart vehicles [4]. These systems continuously produce
massive amounts of TSD that need to be stored and analysed in a timely manner
[5, 6, 7], which cannot be efficiently met by general relational database
management systems.

For this, time series databases (TSDB) have been designed and deployed on
cloud platforms to provide a high ingest rate and faster insights [8], such as
Amazon TimeStream [9] and InfluxDB [10]. Unfortunately, adopting plaintext
TSDBs on cloud platforms to store and process this massive amount of sensitive
TSD can lead to critical data breaches, as several incidents have shown that
cloud platforms are vulnerable to internal and external attacks [11, 12, 13].

One possible solution to protect TSD in the cloud is to adopt cryptographic
protocols such as homomorphic encryption (HE) and secure multi-party
computation (MPC) to securely store and process TSD [14, 15, 16, 17, 18, 19].
For example, TimeCrypt [18] adopts partial HE to provide real-time analytics
for TSD, while Waldo [19] adopts MPC in a distributed-trust setting.
Unfortunately, those solutions have two key limitations. The first is the high
computational and network communication cost. As demonstrated in Waldo [19],
network communication adds up to $4.4\times$ overhead to query operations.
Similarly, HE is orders of magnitude slower than plaintext processing [20,
21]. The second limitation is that cryptographic protocols, specifically HE,
support limited functionalities such as addition and multiplication on
integers [21], where performing complex computations on floating-point numbers
adds significant overhead and gradually loses accuracy [22]. Furthermore,
basic functionalities in time series systems (such as $max$ and $min$) require
a secure comparison, which is a costly operation using HE and MPC [23].

A more practical solution is to adopt hardware-based approaches such as Intel
SGX [24] to process plaintext TSD in a secure and isolated environment in the
cloud, i.e., an enclave. Inside the enclave, data is decrypted and processed
in plaintext, allowing systems to securely perform arbitrary and complex
computations on the data. However, processing TSD within the enclave is not
straightforward due to the costly context switch and access pattern leakage. A
context switch occurs when a CPU enters or exists the enclave, such as when
the enclave requests encrypted data that reside outside the enclave. Several
studies report that context switch is up to $50\times$ more expensive than a
system call [25, 26]. Although such overhead can be minimised by adopting
Switchless Calls techniques [26], the enclave has to validate the requested
data to prevent the untrusted part from tampering with the query. In addition,
the enclave needs to decrypt the requested data, which adds a costly overhead,
as seen in previous work [27].

SGX-based solutions are also vulnerable to access pattern attacks, where an
attacker performs a page table-based attack [28, 29, 30, 31] to observe which
memory page is accessed inside the enclave. This leakage allows the attacker
to infer which data are being accessed and when [32, 33, 34, 29, 28]. Several
studies have shown that such information can recover search queries or a
portion of encrypted records [35, 34, 36]. A widely adopted approach to hide
access patterns is to store encrypted data in an Oblivious RAM (ORAM). Several
solutions combine Intel SGX with ORAM to hide access patterns inside the
enclave. For example, Oblix [37] and ZeroTrace [38] deploy the ORAM controller
securely inside the enclave while leaving the ORAM tree outside the enclave,
which increases the communication between the enclave and the untrusted part.
Such communication adds additional overhead to the system due to context
switching and additional processing performed by the enclave (e.g., data
decryption and validation), which degrades the system’s performance. Even when
deploying the ORAM inside the enclave, these solutions adopt vanilla ORAMs,
which are not optimised to handle non-blocking clients’ queries that dominate
the workload of read-heavy systems like TSDB.

Motivated by the above challenges, we ask the following question: How can we
build an oblivious SGX-based system capable of securely storing TSD and
answering clients’ queries with high performance while hiding access patterns?

TimeClave. To answer this question, this paper presents TimeClave, an
oblivious in-enclave time series processing system that efficiently stores and
processes TSD inside the enclave. TimeClave resides entirely inside the
enclave and adopts oblivious primitives to provide a fully oblivious in-
enclave time series processing system. TimeClave supports oblivious
statistical point and range queries by employing a wide range of aggregate and
non-aggregate functions on TSD that are widely adopted in the area of time
series processing [9, 10, 39], such as $sum$, $max$, and $stdv$.

To efficiently protect against access pattern leakage inside the enclave, we
introduce Read-optimised ORAM (RoORAM), a non-blocking in-enclave ORAM. As
time series systems need to store and query TSD simultaneously, most ORAMs
fail to meet such requirements. The reason is that ORAMs can perform only one
operation at a time, i.e. read or write. Regardless of the required operation,
ORAM reads and writes data back to the ORAM tree to hide the operation type.
As a result, clients’ queries are blocked during a write operation and delayed
during read operations, especially in read-heavy systems. An efficient
approach to address the previous drawbacks is to decouple read and write
operations to handle non-blocking client queries. Existing solutions follow
different approaches to support non-blocking read operations and parallel
access to the ORAM [40, 41]. However, these solutions require either a proxy
server to synchronise the clients with the cloud server [40] or require the
client to maintain a locally-cached sub-tree that is continuously synchronised
with the cloud server [41]. Such a client or third-party server involvement
degrades the system’s performance and usability, especially in read-heavy
systems like time series processing, which requires real-time and low-latency
query processing. RoORAM adopts and improves PathORAM [42] to handle client
queries with better performance. RoORAM achieves this improvement by having
separate ORAM trees, a read-only and a write-only tree, to decouple read- and
write operations. Unlike previous solutions [41, 40], RoORAM is an in-enclave
and lightweight; hence, it does not require client involvement or a proxy
server. RoORAM adopts oblivious primitives inside the enclave to access the
ORAM controller obliviously.

To avoid the costly context switches, TimeClave integrates RoORAM to
efficiently and obliviously store and access TSD inside the enclave, thus,
eliminating excessive communication with the untrusted part. In detail,
TimeClave leverages the fact that TSD is queried and aggregated in an
approximate manner to store statistical summaries of pre-defined time
intervals inside the enclave. By only storing summarised TSD, TimeClave
reduces the size of the ORAM tree, reducing the consumption of enclave memory
and the cost of ORAM access. Such a design allows TimeClave to store and
process a large amount of TSD data with low memory consumption while providing
low-latency queries.

Performance evaluation We implemented and evaluated TimeClave on an SGX-
enabled machine with 8 cores and 128 GiB RAM §6. With different query ranges
of 8 aggregate functions, TimeClave runs a point query in $0.03ms$ and a range
query of 50 intervals in $0.46ms$. TimeClave achieves lower query latency of
up to $2.5\times$ and up to $2\times$ higher throughout. Finally, TimeClave
achieves up to $17\times$ speed-up when inserting new data compared to the
ORAM baseline.

##  2 Background

###  2.1 Intel SGX

Intel SGX is a set of commands that allow creating an isolated execution
environment, called an enclave. Applications run their critical code and store
sensitive data inside the enclave. The enclave is designed to protect
sensitive code and data from a malicious host. No other process on the same
CPU (except the one that created the enclave), even the privileged one (kernel
or hypervisor), can access or tamper with the enclave. SGX-based applications
are divided into two parts: untrusted and trusted parts. The two parts
communicate with each other using user-defined interface functions, i.e.,
ECALL and OCALL. The ECALL allows the untrusted part to invoke code inside the
trusted part (enclave) and send encrypted data to the enclave. OCALL allows
the enclave to send encrypted data to the untrusted part. In addition, SGX
provides a remote attestation feature, allowing the client to authenticate the
enclave’s identity, verify the integrity of the enclave’s code and data, and
share encryption keys. We refer the readers to [43] for more details about
Intel SGX. During remote attestation, the client and the enclave establish a
secure channel for secure communication and share their encryption keys.

###  2.2 ORAM

Oblivious RAM (ORAM) was introduced by Goldreich and Ostrovsky [44] to protect
client data on an untrusted remote machine (such as the cloud) against access
pattern attacks. The main idea of ORAM is to hide the user’s access patterns
by hiding the accessed memory addresses on the cloud, hence, making the user’s
access oblivious. To achieve this, ORAM continuously shuffles and re-encrypts
a portion or all of the user’s accessed data in a trusted memory region or on
a trusted third-party machine. Since then, many ORAM schemes have been
proposed, to list a few, [45, 46, 47, 44, 48, 49]. As of writing this paper,
the most notable among them is the widely adopted PathORAM [42].

PathORAM uses a complete binary tree of height
$L=\left[\log_{2}N\right\rceil-1$ to store $N$ encrypted records on untrusted
storage, e.g., an untrusted cloud. Every node in the tree is a bucket, where
each bucket contains a fixed number ($Z$) of encrypted data blocks. The tree
contains real blocks (client’s blocks) and dummy blocks. Each data block is
randomly assigned to a leaf between 0 and $2^{L}-1$. The client maintains a
Position Map that tracks the leaf to which each block points in the tree. To
access a block in the tree, the client retrieves all blocks on the path from
the root node to the leaf node of the required block and stores them in the
stash. The client then assigns a random leaf to the accessed/updated block.
All blocks are then re-encrypted and inserted in buckets where empty buckets
are filled with dummy blocks. The accessed path is then written back to the
tree (cloud). As a result, the cloud cannot tell which block is accessed by
the client or identify the blocks. In RoORAM, we adopt and enhance PathORAM to
support non-blocking queries while achieving high performance with a bit of
relaxation on the security guarantee (See RoORAM §4.9).

###  2.3 Oblivious Primitives

Oblivious primitives are used to access or move data in an oblivious manner,
i.e., without revealing access patterns. For example, accessing the $i$-th
item in an array can reveal the memory address of the item. However, an
oblivious access primitive accesses the item without revealing its address.
Therefore, hiding the memory access patterns. We use a set of data-oblivious
primitives based on previous works [50, 51]. We use the following primitives
from a library of general-purpose oblivious primitives provided in [52]:

– Oblivious comparisons. The following primitives are used to obliviously
compare two variables; oless(x,y), ogreater(x,y) and oequal(x,y).

– Oblivious assignment. The oassign(cond,x,y) is a conditional assignment
primitive, where a value is moved from a source to a destination variable if
the condition is true. Typically, the oassign is used with the oblivious
comparisons primitives to compare values and return a result obliviously.

– Oblivious array access. The oaccess(op, arr, index) primitive is used to
read/write an item in an array without revealing the item’s address.

– Oblivious exists. The oexists(arr,x) primitive is used to obliviously
determine if a giving item exists in a giving array or not. oexists achieves
this by combining oaccess and oequal.

##  3 System Overview

Figure 1: TimeClave architecture. The figure illustrates how TimeClave
securely and obliviously stores time series data (1), and how it handles
clients’ queries (2).

TimeClave consists of 4 entities: data producers, clients, server (referred to
as the cloud or server), and the SGX enclave running on the server. Data
producers, such as sensors or other devices, generate raw time series data and
upload them to the server. Clients send encrypted queries to the server.
Finally, the server (typically deployed in the cloud) stores the time series
data and handles clients’ queries.

###  3.1 Threat Model

We consider a semi-trusted server where an adversary is interested in learning
clients’ data and queries. Furthermore, we consider an adversary who has full
control over the server except for the CPU (Intel SGX). Therefore, the
adversary can obtain the encrypted client queries and data, but cannot examine
them in plaintext. In addition, the adversary can see the entire memory trace,
including the enclave memory (at the page level). We consider trusted data
producers and clients; therefore, only authorised users can submit queries to
the server. We do not consider DoS attacks or other side-channels on the
enclave, e.g., speculative execution [53], voltage changes [54], or cache
attack [55]. We discuss the of security of RoORAM in §4.9 and TimeClave in
§5.3.

###  3.2 Overview of TimeClave

The architecture of TimeClave is depicted in Fig. 1. We can see that TimeClave
is partitioned into two parts on the server: untrusted and trusted. The
untrusted part runs on the host outside Intel SGX while the trusted part runs
inside Intel SGX (referred to as the enclave or enclave code). The role of the
untrusted part is to facilitate communication between the client (including
the data producer) and the enclave. This is achieved by receiving encrypted
requests from the client and sending them to the enclave.

To protect data and queries from the cloud, data producers, clients, and the
enclave share a secret key $k$. The raw time series data and queries are
encrypted with $k$ before being sent to the cloud. Note that clients are
authenticated and $k$ is shared during SGX Remote Attestation (RA). Also,
clients and data producers authenticate the enclave’s identity and verify the
code’s integrity during RA.

As depicted in Figure 1, most of TimeClave components run inside the enclave.
TimeClave stores the data in an ORAM inside the enclave, i.e., RoORAM to
protect against SGX memory access patterns. The reason of deploying TimeClave
entirely inside the enclave is that new generations of SGX support up to 1 TB
of enclave memory, allowing applications to store more data and run larger
applications inside the enclave. TimeClave utilises the enclave’s large memory
to securely store and process data securely within the enclave [56].

The trusted and untrusted components of TimeClave cooperate to perform two
main functionalities: storing time series data and processing client queries.

1) Storing time series data. The data producer generates and encrypts raw time
series data and transmits them to the server. A request handler on the
untrusted part forwards it to the enclave. The enclave then decrypts the data
and stores them temporarily for a pre-defined time interval ($T$). When $T$
elapses, TimeClave (inside the enclave) calculates the aggregated values
(using all supported aggregate functions) for the data points cached in
temporary storage and stores the values in a block. Once the block is
generated, the raw time series data are discarded, and the block is stored in
the ORAM, i.e., RoORAM.

2) Clients’ Query. The client first generates a query $\mathcal{Q}=\langle
f,(t_{a},t_{b})\rangle$, where $f$ is the aggregate function, $t_{a}$ and
$t_{b}$ are the time range. The client then encrypts the query, i.e.,
$\mathcal{Q^{\prime}}=\mathcal{E}_{k}(\mathcal{Q})$, where $\mathcal{E}$ is a
symmetric encryption scheme. The encrypted query is then transmitted to the
server. Once the request handler receives the query, it sends it to the
enclave. The enclave first decrypts the query by computing
$\mathcal{Q}=\mathcal{D}_{k}(\mathcal{Q^{\prime}})$, and then sends it to the
query optimiser. The query optimiser is responsible for optimising the number
of accessed blocks in the ORAM tree by efficiently accessing and merging
blocks from different aggregation intervals (For more details refer to 5.2.
The results are encrypted using the client’s key and returned to the client
through a secure channel established through RA.

Supported Aggregate Functions: TimeClave supports a set of additives
aggregates, i.e., sum, count, mean, variance and standard deviation. In
addition, TimeClave supports a set of more complex non-additive aggregates,
i.e., max and min. TimeClave uses the previous functions on a set of data
points to generate summarised blocks for a pre-defined time interval (see
§5.1). These functions are used to answer simple and complex queries, where
multiple aggregated values are used in the calculations instead of raw data
points (see §5.2).

##  4 RoORAM

In this section, we introduce our proposed ORAM, namely RoORAM, which is
integrated into TimeClave to provide oblivious data storage inside the enclave
capable of handling non-blocking read-operations (i.e., clients’ queries).
Later, we describe how TimeClave efficiently stores time series data in RoORAM
and how it is used to realise clients’ queries.

###  4.1 Overview

The main idea of RoORAM is to decouple the eviction process from the
read/write operation. This separation allows RoORAM to evict the accessed
paths without blocking clients’ queries. Inspired by [41], RoORAM performs
read-operations (queries) on a read-only tree and write-operations (writing
data and eviction) on a write-only tree. However, unlike [41], RoORAM stores
and obliviously accesses the controller and components inside the enclave (as
illustrated in Figure 2). Further, RoORAM does not require clients’
involvement to maintain a locally-cached sub-tree nor requires synchronisation
with the server. Such a lightweight design makes RoORAM tailored for in-
enclave read-heavy time series processing systems, which require real-time and
low-latency query processing.

RoORAM uses the dedicated read-only tree to perform query operations only
(read operation). This allows RoORAM to perform multiple read-operations on
the read-only tree (reading multiple paths) before evicting the accessed
paths. The retrieved blocks are stored in the stash. After $\mathcal{R}$ read-
operations, RoORAM evicts the blocks from the stash to the write-only tree and
then synchronises both trees. RoORAM notations are defined in Table 1.

Figure 2: RoORAM structure and components. The position map ($pos$) and the
temporary position map ($pos_{tmp}$) are stored in recursive PathORAM. $S$,
$S_{tmp}$, $S_{L}$ and $\mathcal{P}_{L}$ are stored in an array and are
accessed using oblivious primitives §2.3.

###  4.2 Structure and Components

Table 1: RoORAM notations. ∗ Represents notations introduced by RoORAM. Notation |  Meaning
---|---
$N$ |  Total number of blocks on the server
$L$ |  Height of binary tree. $L=\left[\log_{2}N\right\rceil-1$).
$B$ |  Block size in bytes
$Z$ |  Bucket capacity (in blocks)
$\mathcal{P}(x)$ |  Path from leaf node $x$ to the root
$\mathcal{P}(x,\ell)$ |  The bucket at level $\ell$ along the path $\mathcal{P}(x)$
$\mathcal{P_{L}}$∗ |  Path lookup, a list of accessed paths’ IDs by the read operation
$\mathcal{R}$∗ |  Eviction frequency, number of read operations before batch eviction
$S$ |  Read stash
$S_{tmp}$∗ |  Write Stash, a temporary stash used during eviction.
$S_{L}$∗ |  Stash blocks lookup
$pos$ |  Position map used for read operations
$pos_{tmp}$∗ |  Temporary position map used during batch eviction.
$Tr_{R}$ |  Read-only tree, used for read operations
$Tr_{W}$∗ |  Write-only tree, used during batch eviction

Binary tree. Similar to PathORAM, RoORAM stores data in a binary tree data
structure of height $L=\left\lceil\log_{2}(N)\right\rceil-1$ and $2^{L}$
leafs.

Bucket. Each node in the tree contains a bucket, where each bucket contains
$Z$ real data blocks. Buckets containing less than $Z$ blocks are filled with
dummy data.

Path. A path represents a set of buckets from the leaf node $x$ to the root
node. $\mathcal{P}(x)$ denotes the path from leaf node $x$ to the root and
$\mathcal{P}(x,\ell)$ denotes the bucket at level $\ell$ along the path
$\mathcal{P}(x)$.

Block. A block contains summarised data for a specific pre-defined time
interval. Each block is assigned a random path in the tree between 0 and
$2^{L}-1$. Accessing a block is achieved by accessing a path $\mathcal{P}(x)$
on the read-only tree $Tr_{R}$.

Stash $S$. When a path is accessed, blocks are stored and kept in the stash
$S$ until batch eviction. During batch eviction, the items in the stash $S$
are moved to a temporary stash $S_{tmp}$, allowing query operations to insert
blocks into $S$. Stash and temporary stash has a size of
$O(\log_{2}N)\cdot\mathcal{R}$. Notice that the stash avoids block duplication
by storing unique blocks only while replacing duplicated blocks with dummy
data to avoid information leakage.

Stash lookup $S_{L}$. Stash lookup $S_{L}$ contains only the IDs of the
retrieved blocks and is used to answer whether a block is in the stash or not.
The cost of accessing $S_{L}$ is lower than $S$ as $S_{L}$ contains smaller-
sized data than $S$. Similar to $S$, $S_{L}$ has a worst case size of
$O(\log_{2}N)\cdot\mathcal{R}$.

Position map $pos$. The position map stores the path to which each block
belongs. The position map is updated every time a block is accessed. RoORAM
stores the position map in a recursive PathORAM [42] instead of an array to
achieve obliviousness. The reason is that the position map contains large
number of items, therefore, storing these items and accessing them linearly
has a high cost compared to a recursive PathORAM.

Path lookup $\mathcal{P}_{L}$. It stores the list of accessed paths
$\mathcal{P}_{L}$ (leaf nodes’ IDs) that have been accessed during read-
operations (query). $\mathcal{P}_{L}$ is used during a batch eviction to write
the accessed paths back to the tree. RoORAM clears the list after each batch
eviction; thus, the maximum size of the list is $\mathcal{R}$.

###  4.3 Initialisation

Both read- and write-trees are initialised with height
$L=\left[\log_{2}N\right\rceil-1$. Therefore, each tree contains $2^{L+1}-1$
buckets, where each bucket is filled with dummy blocks. Position maps are
initialised with an independent random number between 0 and $2^{L}-1$. Stash,
temporary stash, and stash lookup are initialised with empty data. Path lookup
$\mathcal{P}_{L}$ is initialised with empty data with size $\mathcal{R}$.

###  4.4 Read Operation

Algorithm 1 Read Operation

1:$b_{id}$ \- Block id

2:Summarised data block

3:function ReadAccess($b_{id}$)

4: $x\leftarrow pos[b_{id}]$

5: $pos_{tmp}[b_{id}]\leftarrow$

6: $UniformRandom(0...2^{L}-1)$

7: if oexists$(b_{id},S_{L}$) then

8: $ReadPath(Tr_{R},dummy)$

9: oaccess$(write,\mathcal{P}_{L},dummy$)

10: else

11: $ReadPath(Tr_{R},x)$

12: oaccess$(write,\mathcal{P}_{L},x$)

13: end if

14: oassign$(true,d^{\prime},$ oaccess($read,S,b_{id}$))

15: return $d^{\prime}$

16:end function

1:

2:function ReadPath($ORAM,x$)

3: for $l\in$ { $L,L-1...0$ } do

4: oaccess$(write,S,$ $GetBucket(P(x,l))$

5: oaccess$(write,S_{L},$

6: $GetBucket(P(x,l)).b_{id}$

7: end for

8:end function

The details of READACCESS are shown in Algorithm 1. It is worth noting that,
aside from the distinct design variations between TimeClave and PathORAM, the
algorithmic distinctions are also demonstrated in Algorithm 1, 2, and 3, which
are highlighted in red. To access block $a$, given its block ID $b_{id}$,
RoORAM first accesses the position map to retrieve the block’s position in
$Tr_{R}$, such that $x:=pos[b_{id}]$. Second, a new random path is assigned to
block $a$ and stored in the temporary position map ($pos_{tmp}$). RoORAM
updates $pos_{tmp}$ instead of $pos$ as the accessed block will not be evicted
before $\mathcal{R}$ read operations. Thus, avoiding inconsistent block
position for subsequent queries before a batch eviction.

The next step is to check whether block $a$ is stored in the stash or not by
searching $S_{L}$ with the oblivious primitive oexists §2.3. If $S_{L}$
contains $a$, a dummy path will be accessed; otherwise, path $x$ is accessed.
By doing so, the adversary cannot infer whether block $a$ is located in the
stash ($S$) or in the ORAM tree ($Tr_{R}$). In both cases, the retrieved
blocks of the accessed path are stored in the stash $S$, and its path ID is
tracked in $\mathcal{P}_{L}$. Finally, block $a$ is obliviously retrieved from
the stash $S$ with oaccess and assigned to $d^{\prime}$ with oassign.

###  4.5 Write Operation

Algorithm 2 Write Operation

1:$data*$ \- Block data, $time$ \- block time interval

2:function WriteAccess($data*,time$)

3: $\underline{QueryLock.lock}$

4: $x\leftarrow UniformRandom(0...2^{L}-1)$

5: $b_{id}\leftarrow time$

6: $pos_{tmp}[b_{id}]\leftarrow x$

7: oaccess($write,S,data*$)

8: oaccess($write,S_{L},b_{id}$)

9: $\underline{QueryLock.unlock}$

10:end function

The details of WRITEACCESS is given in Algorithm 2. The data block to be
written $data*$ is associated with a time interval $time$, and will be used as
the ID of $data*$. Since the stash is accessed by both read and write
operations, adding a block to the stash requires synchronisation using a mutex
(i.e., query lock). Therefore, queries are blocked during a write operation.
However, a write operation requires few operations only, such as adding the
block to stash and updating the position map, which adds a negligible
overhead. Note that if the stash is full, RoORAM will automatically evict the
blocks (see §4.6).

To write $data*$ to the tree, RoORAM assigns a random path $x$ to it by
setting $pos[time]\leftarrow x$ and obliviously adds the block to the stash
$S$ with Oaccess. Meanwhile, the block ID $time$ is added to $S_{L}$, as
$data*$ is stored in the stash. Unlike other tree-based ORAMs, stash items in
RoORAM are not evicted after a write operation. Instead, stash items are
evicted in batches after $\mathcal{R}$ read operations §4.6.

###  4.6 Batch Eviction and Trees Synchronisation

Algorithm 3 Batch Eviction

1:function Evict()

2: let $eBuckets$ be the IDs of evicted buckets

3: $\underline{QueryLock.lock}$

4: $swap(S,S_{tmp})$

5: $S_{L}.clear()$

6: $\underline{QueryLock.unlock}$

7: for each $p\in\mathcal{P}_{L}$ do

8: for $l\in$ { $L,L-1...0$ } do

9: if !oexists($\mathcal{P}(p,l).id,eBuckets$) then

10: $S^{\prime}\leftarrow(a^{\prime},data^{\prime})\in
S_{tmp}:\mathcal{P}(pos_{tmp}[a^{\prime}],l)$

11: $S^{\prime}\leftarrow$ Select $min(|S^{\prime}|,Z)$ blocks from
$S^{\prime}$

12: $S_{tmp}\leftarrow S_{tmp}-S^{\prime}$

13: $eBuckets=eBuckets\cup\mathcal{P}(p,L).id$

14: end if

15: end for

16: end for

17: eBuckets.clear()

18: $\underline{QueryLock.lock}$

19: Copy changes from $Tr_{W}$ to $Tr_{R}$

20: Copy changes from $pos_{tmp}$ to $pos$

21: $S\leftarrow S\cup S_{tmp}$

22: Clear $S_{tmp}$

23: Clear $\mathcal{P}_{L}$

24: $\underline{QueryLock.unlock}$

25:end function

RoORAM performs $\mathcal{R}$ read operations on the read-only tree prior to a
batch eviction. As a result, RoORAM needs to write multiple paths at once in a
single non-blocking batch eviction. It is known that eviction in PathORAM is
an expensive process; hence, it can degrade the query performance. RoORAM
addresses this issue by blocking only queries during the execution of critical
sections in batch evictions. Note that there are a few steps during eviction
where RoORAM needs to block queries. However, these steps have a negligible
impact on query performance, making the batch eviction a non-blocking process.
As shown in Algorithm 3, RoORAM splits the batch eviction into two phases:

Path Writing Phase (lines 3-17, Algorithm 3). During the eviction phase,
RoORAM starts by acquiring a mutex for a short period to swap $S$ and
$S_{tmp}$. Swapping stash items allows query operations (read operations on
the ORAM) to insert blocks into $S$ while batch eviction is in process. Note
that moving stash items is achieved by a simple reference swap instead of
swapping data. The eviction process writes all the accessed paths recorded in
$\mathcal{P}_{L}$ to the write-only tree (lines 7 to 17). Specifically, for
each path $p$ in $\mathcal{P}_{L}$, RoORAM greedily fills the path’s buckets
with blocks from $S_{tmp}$ in the order from leaf to root. This order ensures
that the blocks are pushed into $Tr_{W}$ as deep as possible. All non-evicted
blocks remain in $S_{tmp}$ to be evicted in subsequent batch evictions.

When RoORAM writes multiple paths to $Tr_{W}$, there can be an intersection
between two paths, at least at the root level. A bucket may be written several
times during a batch eviction (e.g., the root node’s bucket), causing a
buckets collision. RoORAM avoids that by writing every bucket only once. Such
an approach can improve performance by reducing the number of evicted buckets.
However, it leaks the number of intersected buckets to the adversary. RoORAM
prevents such leakage by performing fake access to all buckets in the
intersected paths.

Synchronisation Phase (lines 18-24, Algorithm 3). At this point, $Tr_{R}$
needs to be synchronised with $Tr_{W}$ to reflect the new changes. To
synchronise the two trees with minimal query blocking (Lines 18 to 24), RoORAM
copies only the written changes (i.e., paths) from $Tr_{W}$ to $Tr_{R}$
instead of copying the entire tree. In addition, RoORAM copies the changes
from $pos_{tmp}$ to $pos$ and any non-evicted blocks in $S_{tmp}$ to $S$.

###  4.7 Memory Consumption

RoORAM uses two separate ORAM trees to handle non-blocking queries. As a
result, it consumes twice the data as the ORAM baseline. In detail, TimeClave
maintains two separate ORAM trees to store the data blocks, two stashes, two
position maps and the list of accessed paths. Each tree will have a height
$L=\left[\log_{2}N\right\rceil-1$. Therefore, each tree will be able to store
up to $2^{L+1}-1$ buckets. Since each bucket contains $Z$ blocks, the number
of blocks stored in the tree is $2^{L+1}-1\cdot Z$. Therefore, each tree will
require $2^{L+1}-1\cdot Z\cdot B$ bytes. Stash ($S$) and Stash Lookup
($S_{L}$) require $O(\log_{2}N)\cdot\mathcal{R}\cdot B$ bytes. Path Lookup
($\mathcal{P_{L}}$) requires $\mathcal{R}\cdot 4$ bytes (since each path
requires 4-bytes).

###  4.8 RoORAM Efficiency Analysis

RoORAM’s operation overheads involve four main operations: accessing and
updating the temporary position map $pos_{tmp}$, stash lookup table access
$S_{L}$, read-only tree $Tr_{R}$ path reading, and path lookup access
$\mathcal{P}_{L}$. Each of these operations is associated with a computational
cost. For read operations §4.4, accessing and updating $pos_{tmp}$ and the
path reading from $Tr_{R}$ both involve an asymptotic cost of $O(\log N)$ due
to recursive PathORAM and its position map inside the enclave. Accessing
$S_{L}$ costs $O(\log N)\cdot\mathcal{R}$, while accessing $\mathcal{P}_{L}$
costs $O(\mathcal{R})$. Therefore, the overall cost for a read operation is
$O(logN)$, yielding similar asymptotic complexity to PathORAM. Nevertheless,
RoORAM shows higher performance up to 2.5 times §6. This enhancement is due to
RoORAM’s design of decoupling the non-blocking read operations from the non-
blocking eviction process.The write operation §4.5 accesses $pos_{tmp}$, $S$,
and $S_{L}$. I.e., $O(\log N)$ \+ $O(\log N)\cdot\mathcal{R}$ \+ $O(\log
N)\cdot\mathcal{R}$ where $\mathcal{R}$ is a constant. Consequently, the
overall cost is $O(logN)$. Finally, path writing during batch eviction
requires $O(\log N)$, and tree synchronization, which involves copying $O(\log
N)\textperiodcentered R$ items, leads to an overall cost of $O(\log N)$.

###  4.9 Security of RoORAM

To prove the security of RoORAM, we adopt the standard security definition for
ORAMs from [57]. An ORAM is said to be secure if, for any two data request
sequences, their access patterns are computationally indistinguishable by
anyone but the client. RoORAM is similar to PathORAM but excludes two main
points: 1) RoORAM stores all components in the enclave, whereas PathORAM
stores the stash and position map in the client; 2) PathORAM evicts the stash
data after each access, while RoORAM performs batch eviction after $R$ read
operations. Therefore, the security definition of RoORAM is captured in the
following theorem.

###### Theorem 4.1

RoORAM is said to be secure if, for any two data request sequences
$\vec{y_{1}}$ and $\vec{y_{2}}$ of the same length, their access patterns
$A(\vec{y_{1}})$ and $A(\vec{y_{2}})$ are computationally indistinguishable by
anyone but the enclave.

###### Proof

To prove the security of RoORAM, we now provide the following analysis.

Storing and accessing the stash, position map, and other components of RoORAM
within the enclave do not leak additional information to the adversary because
they are all accessed with oblivious primitives. Based on the security of
oblivious primitives, the adversary cannot infer which item is accessed in the
position map $pos$, the temporary position map $pos_{tmp}$, the stash $S$,
temporary stash $S_{tmp}$, stash lookup $S_{L}$, and path lookup
$\mathcal{P}_{L}$.

Evicting the stash after $R$ reads can improve the performance of RoORAM with
a bit of relaxation on the security guarantee, compared to the security of
Path ORAM. Note that the security of RoORAM can reach the standard security
via extra dummy access, which will be explained later. Let
$\vec{y}=(a_{R-1},...,a_{1})$ be a sequence of read-access of size
$\mathcal{R}$. The adversary sees a sequence $A(\vec{y})=\left(\right.$
$pos_{\mathcal{R}}\left[\mathrm{a}_{\mathcal{R}}\right]$,
$pos_{\mathcal{R}-1}\left[\mathrm{a}_{\mathcal{R}-1}\right],\ldots$,
$pos\left.{}_{1}\left[\mathrm{a}_{1}\right]\right)$. It is possible for the
adversary to distinguish some read-accesses based on the access pattern, e.g.,
$\vec{y_{1}}=(a_{1},a_{1},...,a_{1})$ and
$\vec{y_{2}}=(a_{1},a_{2},...,a_{R})$ (here we assume that $a_{1}$, $a_{2}$,
…, and $a_{R}$ are stored in different leaf nodes). Recall that within
$\mathcal{R}$ reads, if the required block is stored in the stash, a random
path will be accessed; otherwise, the required path will be accessed. Assume
that the tree contains $M=2^{L}$ paths. In the example, $pos[a_{1}]$,
$pos[a_{2}]$, …, and $pos[a_{R}]$ must be different. For $\vec{y_{1}}$, any
two paths are the same with a probability of $1/M$. However, as long as
$A(\vec{y})$ contains one pair of the same path $\vec{y}$ must be
$\vec{y}_{1}$, and the probability of that is
$1-C_{M}^{\mathcal{R}}/M^{\mathcal{R}}$, which is $0$ for $\vec{y_{2}}$. In
other words, if $A(\vec{y})$ does not contain any path repetition, there is a
higher probability that $\vec{y}$ is $\vec{y_{2}}$, otherwise it must be
$\vec{y_{1}}$. This issue can be avoided by always accessing a path that has
not been accessed after a round of eviction when the required block is stored
in the stash. In this case, $A(\vec{y})$ never contains repeated paths no
matter what $\vec{y}$ contains, and we just need to ensure $R<M$, which is
always the case in practice. As a result, with the extra dummy access for each
read, the adversary cannot distinguish between one sequence and the other.

##  5 TimeClave

In this section, we first describe how TimeClave efficiently generates
summarized time series data blocks and how these blocks are stored inside
RoORAM. Then, we describe how TimeClave utilizes these blocks to efficiently
answer clients’ queries.

In TimeClave, a system administrator is responsible for initialising the
system by setting the system parameters, including the block size $B$, bucket
capacity $Z$, block generation interval $T$, and eviction frequency $R$.
Subsequently, TimeClave continuously receives data points from the data
producer, generates data blocks, and answers the client’s queries.

###  5.1 Block Generation

TimeClave stores the TSD as summarised data blocks based on the supported
aggregate functions instead of the raw data points. The block summarises raw
data points of a pre-defined time interval i.e., $\left[t_{i},t_{i+1}\right)$
with a fixed interval $T=t_{i+1}-t_{i}$. Larger intervals provide lower query
accuracy but high performance with less storage. To support multiple accuracy
levels and higher query performance, TimeClave generates blocks at different
time intervals, i.e, aggregation intervals $V$, where $V=[T_{1},T_{2},....]$
(See §5.2). The generated data blocks are stored in RoORAM. Each block
contains the aggregated values for the supported aggregate functions for
$\left[t_{i},t_{i+1}\right)$. A block is represented by an array, where each
item in the array contains all the aggregated values. By storing summarised
blocks, TimeClave reduces the ORAM tree size and the query latency.

###  5.2 Query Realisation

TimeClave receives encrypted queries from clients in the form $Q=E_{k}(\langle
f,(t_{a},t_{b})\rangle)$ for a range query and $Q=E_{k}(\langle
f,t_{a}\rangle)$ for a point query, where $f$ is the aggregate function to be
executed over the time interval from $t_{a}$ to $t_{b}$. In the following
subsections, we describe how TimeClave handles point and range queries and how
they can be extended to support complex analytics.

Point Queries: When TimeClave receives a query, it first decrypts the query,
i.e., $Q^{\prime}=D_{k}(Q)$ where $k$ is the client’s private key. TimeClave
then extracts $t_{a}$ from $Q^{\prime}$ and retrieves the data block using
RoORAM. Once the block is retrieved, TimeClave uses the aggregates position
map to find the location of the requested $f$’s value. For example, assume
that $f=AVG$, TimeClave will access the $avg$ value at index 0 (assuming that
$avg$ is located at index 0) of the retrieved block. Finally, the results are
encrypted using the client’s private key and sent back to the client.

Range Queries TimeClave follows the same approach that is used with point
queries to answer range queries. However, range queries involve retrieving
multiple blocks and multiple aggregated values, instead of one. The retrieved
values must be fed into the aggregation function to return the final result to
the client. Notice that for functions such as min or max, using the retrieved
values to calculate the final results is a straightforward process. The reason
is that the maximum value for the aggregated values (summarised values)
represents the maximum value for the underlying data points. However, this is
not valid for other functions, such as the average and variance. To find the
average for multiple aggregated values, we use the weighted average, which is
given by the formula,

$avg=\frac{\sum_{i=1}^{n}bw_{i}\cdot bx_{i}}{\sum_{i=1}^{n}bw_{i}}$

where $bw$ is the number of data points in the block (count), $bx$ is the
aggregated average value for the block, and $n$ is the number of blocks
retrieved by the query.

The above formula uses only the count and average values from each retrieved
block and performs the calculations in a single pass. TimeClave adopts similar
approaches for all supported aggregation functions to answer range queries to
achieve high performance without compromising accuracy.

Complex Analytics TimeClave can also combine several aggregate values to
answer complex range queries. This is possible because TimeClave retrieves all
blocks within the queried time interval $(t_{a},t_{b})$. Unlike cryptographic
approaches, blocks’ values are stored in plaintext inside the enclave. Hence,
one can easily combine and perform arithmetic operations on the aggregate
values. TimeClave can also in principle support sketch algorithms such as
Count-Min, Bloom filter and HyperLogLog. A single- or multi-dimensional sketch
table can be flattened and represented by a one-dimensional array. This allows
TimeClave to store a sketch table inside the data block as a range of values
(instead of a single aggregate value).

Query Optimisation In RoORAM, query latency increases linearly with the number
of accessed blocks in range queries. The reason is that each block access in
RoORAM is independent of the preceding and subsequent access. Such an approach
allows RoORAM to offer a stronger leakage profile but degrades query
performance. To prevent this performance drawback, RoORAM optimises queries by
reducing the number of accessed blocks. RoORAM achieves this by maintaining
multiple ORAM trees with different time intervals $V$ =
$[T_{0},T_{1},T_{2},...]$, where $T_{i-1}<T_{i}<T_{i+1}$, with $T_{i}\in V$.

Query optimiser works by examining the client’s query $Q=\langle
SUM,(t_{1},t_{6})\rangle$ and determining the optimal combination of
aggregation intervals to minimise the total number of accessed blocks. For
example, assume that $T_{1}=60s$ and $T_{2}=10s$, hence, every block in the
$T_{1}$ tree summarises 6 blocks of $T_{2}$ tree. Assume that $Q=\langle
SUM,(0,70)\rangle$. Processing this query without optimisation requires
accessing 7 blocks in $T_{2}$ tree, while with query optimisation, TimeClave
will access 1 block from each tree, totalling 2 blocks. As each aggregation
interval requires a separate ORAM tree; therefore, $T_{i}$ will determine the
size of the tree. Note that a larger $T_{i}$ offers high query performance
with lower accuracy and less storage. Therefore, such a parameter can be
optimised as per the application’s requirements.

###  5.3 Security of TimeClave

TimeClave handles input parameters and queries securely inside the enclave,
i.e., parameters and queries are encrypted using the clients’ key and can only
be decrypted by the enclave. In addition, TimeClave adopts and integrates
RoORAM to obliviously store and access time series data inside the enclave.
Therefore, the security definition of TimeClave is captured in the following
theorem.

###### Theorem 5.1

TimeClave §5 is secure giving that RoORAM §4 is proven to be secure in Theorem
4.1.

###### Proof

Giving that TimeClave handles data security inside the enclave, therefore, the
adversary cannot examine the system parameters or client queries in plaintext.
In detail, the adversary cannot examine the following: block size, bucket size
$Z$, the total number of blocks $N$, eviction frequency $\mathcal{R}$ and
query function. Although the adversary can observe which tree is accessed
during quqry optimisation §5.2, this will only reveal $T$ but not the exact
query range (i.e., $(t_{a},t_{b})$). The reason that TimeClave does not
protect the block generation time-interval $T$ is that the adversary can
easily observe such an access pattern during block generation. In addition,
TimeClave does not protect the tree, stash, path lookup, or stash lookup
sizes, as the adversary can monitor the memory pages and infer them. Finally,
reading and writing blocks from/into RoORAM is oblivious and secure, as
discussed in §4.9. Furthermore, all other operations performed by TimeClave,
i.e., block generation and the access to the of the required aggregated values
from blocks accessed, are also oblivious as they are performed with oblivious
primitives §2.3. Therefore, TimeClave does not leak any memory access pattern
to the server.

##  6 Evaluation

In this section, we evaluate TimeClave while asking the following questions:

  1. 1.

What is the performance of TimeClave compared to the non-oblivious version and
ORAM Baseline?

  2. 2.

How do the internal components of RoORAM and the levels of aggregation affect
its performance?

Implementation. We implemented TimeClave and RoORAM in $\sim$4,000 lines of
code. Inside the enclave (server-side), we use the trusted cryptography
library provided by SGX SDK, i.e., sgx_tcrypto [58]. As mentioned earlier in
Section §3.2, we implemented different aggregate functions where the value of
each function is represented by a single item in the data block. We store
values in an array of floating-point numbers (4-bytes per number) in the data
blocks.

Expiremental Setup We evaluated TimeClave on a local network. For the server,
we use an SGX-enabled server running on Intel ®Xeon CPU ®E-2288G @ 3.70 GHz
with 8 cores and 128 GiB RAM. The enclave size is 256 MB. We simulate a client
with 1 vCPU and 3.75 GB memory. We do not include the network latency in our
evaluation as our goal is to measure the performance of TimeClave on the most
critical part, i.e., the server-side.

Dataset. We use the time series benchmark suite [59] to generate CPU
utilization dataset. The dataset contains a single attribute (i.e., CPU
usage). We initialise TimeClave to store 24 hours of readings (i.e., CPU
usage), where each data block in the ORAM tree represents 10s of readings
(i.e., $T=10s$). Each block stores 10 aggregate values, each value consumes
4-bytes ($B=40$ bytes). Each bucket in the tree stores 4 blocks ($Z=4$).
Therefore, the height of each tree in RoORAM is $L=13$.

###  6.1 Baselines

ORAM baseline. In this paper, we introduce and integrate our RoORAM into
TimeClave to achieve obliviousness with minimal query blocking inside the
enclave. We evaluated RoORAM against the widely adopted ORAM, i.e., PathORAM
[42]. We integrate both PathORAM and RoORAM into TimeClave for evaluation. For
a fair comparison, as done in RoORAM, we stored the stash, position map, and
the tree in plaintext inside the enclave for PathORAM. Moreover, we store 4
blocks in each bucket ($Z=4$) for both ORAMs. However, PathORAM performs the
eviction after each read/write access.

Non-oblivious baseline. To understand the overhead of oblivious operations, we
evaluate TimeClave without RoORAM and oblivious operations (referred to as
non-oblivious). In detail, TimeClave generates data blocks and stores them
inside the enclave in a non-oblivious data structure. Thus, we replace RoORAM
with non-oblivious storage. For the position map, TimeClave stores block IDs
in a key-value structure with a pointer to the block’s physical address. To
answer clients’ queries, TimeClave retrieves the required block id from the
position map and accesses (and aggregates) data blocks using non-oblivious
operations. Such a setup allows us to evaluate the overhead of obliviousness
in TimeClave, i.e., RoORAM and oblivious operations.

###  6.2 Evaluation Results

####  6.2.1 Query latency

To understand TimeClave’s performance, Table 2 shows the query latency for
different query ranges and block sizes. We evaluated TimeClave using
reasonable small block sizes, since the size represents the number of
supported aggregates, where a block size of $2^{7}$ can store up to 32
aggregate values. As expected, the query latency increases linearly with the
query range. The reason is that for each queried time interval, TimeClave
needs to access one path in RoORAM and retrieves $(L+1)\cdot Z$ blocks from
the ORAM. Similarly, the larger the block size is, the more overhead it will
add to the query performance, which is expected in a tree-based ORAM.

Table 2: TimeClave Query latency (ms) for point and different range queries and B block sizes. Note that $R_{T}$ is a range of intervals, where each interval represents a single aggregated data block.  Range ($R_{T}$) |  – Block size (bytes) –
---|---
|  $B=2^{3}$ |  $B=2^{4}$ |  $B=2^{5}$ |  $B=2^{6}$ |  $B=2^{7}$
1 |  0.03 |  0.03 |  0.03 |  0.03 |  0.04
10 |  0.12 |  0.12 |  0.12 |  0.13 |  0.15
20 |  0.19 |  0.2 |  0.21 |  0.22 |  0.26
30 |  0.28 |  0.28 |  0.29 |  0.31 |  0.38
40 |  0.37 |  0.36 |  0.38 |  0.41 |  0.49
50 |  0.46 |  0.46 |  0.46 |  0.5 |  0.59

Fig. 3(a) shows the query latency breakdown with a block size $B=2^{7}$. The
majority of the overhead is due to ORAM and oblivious operations for point and
range queries. By omitting the SGX overhead (as it is consistent with
different query ranges), the ORAM operations overhead comprises between 80-85%
of the query latency. On the other hand, the overhead of oblivious operations
comprises between 15-20% of the query latency. Note that the ORAM overhead is
reduced in TimeClave by query optimisation as shown in Section §3.

(a) Latency breakdown

(b) Query latency

Figure 3: A) Query latency breakdown with different query ranges ($R_{T}$).
SGX overhead includes context switch and memory allocation inside the enclave.
B) Query latency with different eviction frequencies ($\mathcal{R}$) and query
range = 32 intervals.

Eviction frequency. TimeClave evicts the blocks from the stash for every
$\mathcal{R}$ read-operation. Fig. 3(b) demonstrates how $\mathcal{R}$ affects
the query latency. With a fixed query range of 32, the query has a negligible
higher latency when the value of $\mathcal{R}$ is smaller than the query
range, i.e, $t_{b}-t_{a}\leq\mathcal{R}$. However, the latency drops
significantly when $\mathcal{R}$ is larger than the query range. This is
because RoORAM performs read-operations from the ORAM with less evictions.

Aggregation Intervals . In Fig. 4, we show how aggregation levels reduce query
latency in TimeClave. We set $T=1$s as the baseline in this evaluation, i.e.,
TimeClave generates 1 block per second. Noticeably, query latency decreases
with larger aggregation intervals as less accesses occur to the ORAM. When
$T=20$s, the speedup achieved in the query latency is $67\times$ with
$20\times$ less memory consumption (compared to $T=1$s). Note that TimeClave
supports multiple aggregation levels by maintaining a separate ORAM tree for
each level. Despite the fact that TimeClave consumes less memory for higher
aggregation levels, such an overhead can be neglected due to the large EPC
size in SGX v2.

Figure 4: Query latency of different aggregation intervals.

Comparison with baselines. Fig. 5(b) illustrates how TimeClave’s query latency
compares to the baselines. The latency grows linearly with the query range for
TimeClave and the baselines. For point queries, the latency overhead of
TimeClave and ORAM baseline compared to the non-oblivious TimeClave is
$1.5\times$ and $2.5\times$ respectively. RoORAM achieves higher performance
than the ORAM baseline due to its non-blocking read operations and efficient
batch eviction design. For range queries, TimeClave and ORAM baseline adds up
to $12\times$ overhead to the query latency compared to non-oblivious
TimeClave. As discussed earlier, the majority of the overhead is due to the
ORAM access and the oblivious operations in TimeClave and ORAM baseline.
However, TimeClave remains substantially faster than the ORAM baseline by
$1.7-2\times$ for both range and point queries.

(a) Query throughput

(b) Query latency

Figure 5: TimeClave query latency and throughput compared to baselines.

####  6.2.2 Query Throughput

In Fig. 5(a), we compare TimeClave query throughput with the baselines. For
point queries, TimeClave achieves up to 22K ops/s compared to the ORAM
baselines which achieves up to 12K ops/s. For range queries, TimeClave
achieves higher throughput than ORAM baseline by up to $2\times$, i.e., 1.5K
ops/s for $R_{T}\geq 20$. Similar to the query latency both TimeClave and ORAM
baseline add up to $6\times$ overhead compared to non-oblivious TimeClave. As
mentioned in Section §6.2.1, the majority of the overhead is caused by ORAM
access and oblivious operations. Such overhead can be reduced in TimeClave by
maintaining multiple aggregation intervals, which reduces the number of
accessed paths in RoORAM. For this, we avoid large query ranges in our
evaluation as the main goal of TimeClave is to summarise TSD and maintain
multiple aggregation intervals to achieve low query latency.

####  6.2.3 Memory Consumption

Table 3: Memory consumption using different aggregation intervals with the expected query latency speedup when the same time interval is queried. $V$ |  Memory (MB) |  Speedup
---|---|---
$[10s]$ |  5.0 |  up to $1\times$
$[10s,60s]$ |  5.6 |  up to $6\times$
$[10s,120s]$ |  5.3 |  up to $12\times$

RoORAM uses two separate ORAM trees to handle non-blocking queries. As a
result, it consumes twice the data as the ORAM baseline. In detail, TimeClave
maintains two separate ORAM trees to store the data blocks, two stashes, two
position maps, and the list of accessed paths. For example, assume $T=10s$,
$\mathcal{R}=4$ and $B=40$ bytes.To store 24h of time-series data, TimeClave
will generate $N=8,640$ blocks. Recall from §4.7, RoORAM initialises two ORAM
trees, each tree requires $2^{L+1}-1\cdot Z\cdot B$ bytes., i.e., $\sim$5MB
for both trees to store a single attribute (e.g., CPU, memory). To maintain
multiple aggregation intervals, e.g., $V=[10s,60s]$, RoORAM will consume
$\sim$5.6MB while achieving up to $6x$ query speedup with only $0.12\times$
memory overhead. Although TimeClave offers a low memory overhead, TimeClave
utilises the new generation of SGX-enabled processors support up to 1TB of
enclave memory [56].

####  6.2.4 TimeClave Compared to Cryptographic Approaches

We evaluate TimeClave against the cryptographic solutions TimeCrypt [18],
which supports aggregate functions over encrypted time-series data. Without
query optimization, TimeClave achieves up to $16x$ lower query latency when
the number of queried blocks is below 6,000. TimeCrypt exhibits an almost
constant latency of around 185$ms$. However, with query optimization using
multiple aggregations intervals, TimeClave demonstrates a significant
improvement in performance in comparison to TimeCrypt by orders of magnitude.
Although the query latency for TimeClave increases with the number of queried
blocks, querying 8,000 blocks results in a query latency that is approximately
$200x$ lower than TimeCrypt.

Without query optimisation, TimeClave achieves better performance when the
number of queried blocks is smaller than 6,000, while TimeCrypt shows almost a
constant latency of around 185$ms$. Nevertheless, it is clear that TimeClave
can achieve up to $16x$ better performance than TimeCrypt without the query
optimiser when the number for small range queries. With query optimisation,
TimeClave achieves better performance than TimeCrypt by orders of magnitude.
Although the query latency for TimeClave increases with the number of queried
blocks, querying 8,000 blocks has around $200x$ lower query latency.

##  7 Related work

###  7.1 Secure Time Series Processing

Cryptographic protocols have been widely adopted in building secure databases
[60, 61, 62] to execute expressive queries on encrypted data, while another
line of work leverages SGX, such as Oblidb [63], EncDBDB [64], EnclaveDB [65]
and Oblix [37]. However, these solutions either incur significant performance
overhead or are not optimised for time series processing. The most related
works to TimeClave in the secure time series processing systems are TimeCrypt
[18], Zeph and Waldo [19]. TimeCrypt and Zeph employ additive homomorphic
encryption to support aggregated queries on encrypted data. However, both
solutions are non-oblivious, allowing the adversary to learn sensitive
information by recovering search queries or a portion of the encrypted records
[34, 36]. On the other hand, Waldo [19] offers a stronger security guarantee
than [18, 19] by hiding query access patterns. As Waldo adopts MPC, the
network bandwidth adds significant overhead to the query latency. TimeClave
eliminates such overhead while providing fully-oblivious query processing.
Unlike previous solutions, TimeClave can be easily scaled to support complex
analytics as it processes TSD in plaintext inside the enclave.

###  7.2 ORAM with Intel SGX

Another line of prior work has explored and combined SGX and ORAM to build
secure storage. For example, ZeroTrace [38] develops a generic oblivious
block-level ORAM controller inside the enclave that supports multiple ORAMs.
Additionally, ZeroTrace focuses on hiding memory access patterns inside the
enclave while leaving ORAM storage outside the enclave. Similarly, Oblix [37]
builds an oblivious search index for encrypted data by using SGX and Path
ORAM. Oblix designs a novel data structure (ORAM controller) to hide access
patterns inside the enclave. Likewise, Oblix stores the ORAM storage on the
server in unprotected memory (outside the enclave). Moreover, Obliviate [66]
and POSUP [67] adopt SGX and ORAM to develop a secure and oblivious filesystem
to read and write data from a file within an enclave. Obliviate is optimised
for ORAM write operations by parallelising the write-back process to improve
performance. MOSE [68] adopts Circuit-ORAM for a multi-user oblivious storage
system with access control. Like previous solutions, MOSE stores the ORAM
controller inside the enclave while leaving the ORAM tree outside. Although
MOSE parallelises the ORAM read process, clients’ queries are blocked until
the accessed blocks are evicted. Unlike TimeClave, previous solutions are not
optimised for handling multi-user, non-blocking queries in the time series
context.

###  7.3 Plaintext Time Series Processing

Many solutions have been proposed to store and process TSD in the plaintext
domain, to name a few, such as Amazon TimeStream [9], InfluxDB [10], Monarch
[69], Gorilla [70]. These solutions focus mainly on delivering low-latency
real-time queries and efficient storage. For example, Gorilla [70] is an in-
memory database for TSD that is optimised for heavy read and write operations.
It introduces a new compression scheme for timestamps and floating point
values for efficient TSD storage and achieves up to $70\times$ lower query
latency than on-disk storage. Monarch [69] is used to monitor and process time
series data in a geo-distributed architecture. In addition, it supports in-
memory data aggregation for higher query performance. Unfortunately, adopting
these solutions for sensitive time series systems on cloud platforms can lead
to critical data breaches [12].

##  8 Conclusion and Future Work

In this work, we presented TimeClave, a secure in-enclave time series
processing system. While previous works [19, 18] adopt cryptographic
protocols, TimeClave leverages Intel SGX to store and process ttime series
data efficiently inside the enclave. To hide the access pattern inside the
enclave, we introduce an in-enclave read-optimised ORAM named RoORAM capable
of handling non-blocking client queries. RoORAM decouples the eviction process
from the read/write operations. TimeClave achieves a lower query latency of up
to $2.5\times$ compared to our ORAM baseline and up to $5.7-12\times$ lower
query latency than previous works.

While TimeClave supports a wide range of aggregate functions that are
supported by time series processing systems [9, 10, 39], it does not support
all the functionalities (e.g., filtering, grouping, and joining). Note that
TimeClave can be easily extended to support such functionalities and
expressive queries. This is because TimeClave stores and processes data inside
the enclave in plaintext, allowing it to perform complex operations
efficiently. However, such a direction requires careful implementation and
optimisation to maintain TimeClave’s obliviousness inside the enclave.
Finally, TimeClave can further improve its query performance by parallelising
each ORAM read access, which can be a valuable direction for future work.

## Acknowledgement

The authors would like to thank the anonymous reviewers for their valuable
comments and constructive suggestions. The work was supported in part by the
ARC Discovery Project (DP200103308) and the ARC Linkage Project (LP180101062).

## References

  * [1] H. L. Li-wei, R. P. Adams, L. Mayaud, G. B. Moody, A. Malhotra, R. G. Mark, and S. Nemati, “A physiological time series dynamics-based approach to patient monitoring and outcome prediction,” _IEEE journal of biomedical and health informatics_ , vol. 19, no. 3, pp. 1068–1076, 2014.
  * [2] B. Liu, J. Li, C. Chen, W. Tan, Q. Chen, and M. Zhou, “Efficient motif discovery for large-scale time series in healthcare,” _IEEE Transactions on Industrial Informatics_ , vol. 11, no. 3, pp. 583–590, 2015.
  * [3] S. Aminikhanghahi, T. Wang, and D. J. Cook, “Real-time change point detection with application to smart home time series data,” _IEEE Transactions on Knowledge and Data Engineering_ , vol. 31, no. 5, pp. 1010–1023, 2018.
  * [4] A. Gupta, H. P. Gupta, B. Biswas, and T. Dutta, “An early classification approach for multivariate time series of on-vehicle sensors in transportation,” _IEEE Transactions on Intelligent Transportation Systems_ , vol. 21, no. 12, pp. 5316–5327, 2020.
  * [5] D. Ketan, L. Jinhua, G. Dhruv, and F.-O. Philip, “Scaling time series data storage,” 2018. [Online]. Available: https://netflixtechblog.com/scaling-time-series-data-storage-part-i-ec2b6d44ba39
  * [6] D. Vasisht, Z. Kapetanovic, J. Won, X. Jin, R. Chandra, S. Sinha, A. Kapoor, M. Sudarshan, and S. Stratman, “$\\{$FarmBeats$\\}$: An $\\{$IoT$\\}$ platform for $\\{$Data-Driven$\\}$ agriculture,” in _USENIX NSDI_ , 2017, pp. 515–529.
  * [7] T. Gupta, R. P. Singh, A. Phanishayee, J. Jung, and R. Mahajan, “Bolt: Data management for connected homes,” in _USENIX NSDI_ , 2014, pp. 243–256.
  * [8] M. P. Andersen and D. E. Culler, “$\\{$BTrDB$\\}$: Optimizing storage system design for timeseries processing,” in _USENIX FAST_ , 2016, pp. 39–52.
  * [9] “Amazon Timestream,” https://aws.amazon.com/timestream/[online].
  * [10] InfluxData., “Influxdb,” 2020. [Online]. Available: https://influxdata.com
  * [11] C. Quintin, “HealthCare.gov Sends Personal Data to Dozens of Tracking Websites,” https://www.eff.org/deeplinks/2015/01/healthcare.gov-sends-personal-data[online], 2015\.
  * [12] I. is Beautiful, “World’s Biggest Data Breaches & Hacks,” https://www.informationisbeautiful.net/visualizations/worlds-biggest-data-breaches-hacks/[online], 2020\.
  * [13] C. Osborne, “Fortune 500 company leaked 264GB in client, payment data,” https://www.zdnet.com/article/veteran-fortune-500-company-leaked-264gb-in-client-payment-data/[online], 2019\.
  * [14] V. Pappas, F. Krell, B. Vo, V. Kolesnikov, T. Malkin, S. G. Choi, W. George, A. Keromytis, and S. Bellovin, “Blind seer: A scalable private dbms,” in _2014 IEEE Symposium on Security and Privacy_. IEEE, 2014, pp. 359–374.
  * [15] R. A. Popa, C. M. Redfield, N. Zeldovich, and H. Balakrishnan, “Cryptdb: protecting confidentiality with encrypted query processing,” in _Proceedings of the Twenty-Third ACM Symposium on Operating Systems Principles_ , 2011, pp. 85–100.
  * [16] B. Fuller, M. Varia, A. Yerukhimovich, E. Shen, A. Hamlin, V. Gadepally, R. Shay, J. D. Mitchell, and R. K. Cunningham, “Sok: Cryptographically protected database search,” in _2017 IEEE Symposium on Security and Privacy (SP)_. IEEE, 2017, pp. 172–191.
  * [17] V. Vo, X. Yuan, S. Sun, J. K. Liu, S. Nepal, and C. Wang, “Shielddb: An encrypted document database with padding countermeasures,” _IEEE Transactions on Knowledge and Data Engineering_ , 2021.
  * [18] L. Burkhalter, A. Hithnawi, A. Viand, H. Shafagh, and S. Ratnasamy, “Timecrypt: Encrypted data stream processing at scale with cryptographic access control,” in _USENIX NSDI_ , 2020, pp. 835–850.
  * [19] E. Dauterman, M. Rathee, R. A. Popa, and I. Stoica, “Waldo: A private time-series database from function secret sharing,” _Cryptology ePrint Archive_ , 2021.
  * [20] S. D. Tetali, M. Lesani, R. Majumdar, and T. Millstein, “Mrcrypt: Static analysis for secure cloud computations,” in _Proceedings of the 2013 ACM SIGPLAN international conference on Object oriented programming systems languages & applications_, 2013, pp. 271–286.
  * [21] R. Poddar, C. Lan, R. A. Popa, and S. Ratnasamy, “$\\{$SafeBricks$\\}$: Shielding network functions in the cloud,” in _USENIX NSDI_ , 2018, pp. 201–216.
  * [22] A. Viand, P. Jattke, and A. Hithnawi, “Sok: Fully homomorphic encryption compilers,” in _IEEE S &P_, 2021, pp. 1092–1108.
  * [23] S. S. Sathya, P. Vepakomma, R. Raskar, R. Ramachandra, and S. Bhattacharya, “A review of homomorphic encryption libraries for secure computation,” _arXiv preprint arXiv:1812.02428_ , 2018.
  * [24] F. McKeen, I. Alexandrovich, A. Berenzon, C. V. Rozas, H. Shafi, V. Shanbhogue, and U. R. Savagaonkar, “Innovative instructions and software model for isolated execution.” _Hasp@ isca_ , vol. 10, no. 1, 2013.
  * [25] N. Weichbrodt, P.-L. Aublin, and R. Kapitza, “sgx-perf: A performance analysis tool for intel sgx enclaves,” in _Proceedings of the 19th International Middleware Conference_ , 2018, pp. 201–213.
  * [26] H. Tian, Q. Zhang, S. Yan, A. Rudnitsky, L. Shacham, R. Yariv, and N. Milshten, “Switchless calls made practical in intel sgx,” in _Proceedings of the 3rd Workshop on System Software for Trusted Execution_ , 2018, pp. 22–27.
  * [27] Y. Sun, S. Wang, H. Li, and F. Li, “Building enclave-native storage engines for practical encrypted databases,” _Proceedings of the VLDB Endowment_ , vol. 14, no. 6, pp. 1019–1032, 2021.
  * [28] Y. Xu, W. Cui, and M. Peinado, “Controlled-channel attacks: Deterministic side channels for untrusted operating systems,” in _2015 IEEE Symposium on Security and Privacy_. IEEE, 2015, pp. 640–656.
  * [29] J. Van Bulck, N. Weichbrodt, R. Kapitza, F. Piessens, and R. Strackx, “Telling your secrets without page faults: Stealthy page $\\{$Table-Based$\\}$ attacks on enclaved execution,” in _USENIX Security_ , 2017, pp. 1041–1056.
  * [30] W. Wang, G. Chen, X. Pan, Y. Zhang, X. Wang, V. Bindschaedler, H. Tang, and C. A. Gunter, “Leaky cauldron on the dark land: Understanding memory side-channel hazards in sgx,” in _Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security_ , 2017, pp. 2421–2434.
  * [31] D. Moghimi, J. Van Bulck, N. Heninger, F. Piessens, and B. Sunar, “$\\{$CopyCat$\\}$: Controlled $\\{$Instruction-Level$\\}$ attacks on enclaves,” in _USENIX Security_ , 2020, pp. 469–486.
  * [32] D. Cash, P. Grubbs, J. Perry, and T. Ristenpart, “Leakage-abuse attacks against searchable encryption,” in _Proceedings of the 22nd ACM SIGSAC conference on computer and communications security_ , 2015, pp. 668–679.
  * [33] M. S. Islam, M. Kuzu, and M. Kantarcioglu, “Access pattern disclosure on searchable encryption: ramification, attack and mitigation.” in _NDSS_ , vol. 20. Citeseer, 2012, p. 12.
  * [34] Y. Zhang, J. Katz, and C. Papamanthou, “All your queries are belong to us: The power of $\\{$File-Injection$\\}$ attacks on searchable encryption,” in _USENIX Security_ , 2016, pp. 707–720.
  * [35] M. Giraud, A. Anzala-Yamajako, O. Bernard, and P. Lafourcade, “Practical passive leakage-abuse attacks against symmetric searchable encryption,” in _14th International Conference on Security and Cryptography SECRYPT 2017_. SCITEPRESS-Science and Technology Publications, 2017.
  * [36] C. Liu, L. Zhu, M. Wang, and Y.-a. Tan, “Search pattern leakage in searchable encryption: Attacks and new construction,” _Information Sciences_ , vol. 265, pp. 176–188, 2014.
  * [37] P. Mishra, R. Poddar, J. Chen, A. Chiesa, and R. A. Popa, “Oblix: An efficient oblivious search index,” in _IEEE S &P_. IEEE, 2018, pp. 279–296.
  * [38] S. Sasy, S. Gorbunov, and C. W. Fletcher, “Zerotrace: Oblivious memory primitives from intel sgx,” _Cryptology ePrint Archive_ , 2017.
  * [39] “Timescale.com,” 2020. [Online]. Available: https://timescale.com
  * [40] C. Sahin, V. Zakhary, A. El Abbadi, H. Lin, and S. Tessaro, “Taostore: Overcoming asynchronicity in oblivious data storage,” in _IEEE S &P_. IEEE, 2016, pp. 198–217.
  * [41] A. Chakraborti and R. Sion, “Concuroram: High-throughput stateless parallel multi-client oram,” _arXiv preprint arXiv:1811.04366_ , 2018.
  * [42] E. Stefanov, M. V. Dijk, E. Shi, T.-H. H. Chan, C. Fletcher, L. Ren, X. Yu, and S. Devadas, “Path oram: an extremely simple oblivious ram protocol,” _Journal of the ACM (JACM)_ , vol. 65, no. 4, pp. 1–26, 2018.
  * [43] V. Costan and S. Devadas, “Intel sgx explained,” _Cryptology ePrint Archive_ , 2016.
  * [44] O. Goldreich and R. Ostrovsky, “Software protection and simulation on oblivious rams,” _Journal of the ACM (JACM)_ , vol. 43, no. 3, pp. 431–473, 1996.
  * [45] D. Boneh, D. Mazieres, and R. A. Popa, “Remote oblivious storage: Making oblivious ram practical,” 2011.
  * [46] I. Damgård, S. Meldgaard, and J. B. Nielsen, “Perfectly secure oblivious ram without random oracles,” in _Theory of Cryptography Conference_. Springer, 2011, pp. 144–163.
  * [47] C. Gentry, K. A. Goldman, S. Halevi, C. Julta, M. Raykova, and D. Wichs, “Optimizing oram and using it efficiently for secure computation,” in _International Symposium on Privacy Enhancing Technologies Symposium_. Springer, 2013, pp. 1–18.
  * [48] M. T. Goodrich and M. Mitzenmacher, “Privacy-preserving access of outsourced data via oblivious ram simulation,” in _International Colloquium on Automata, Languages, and Programming_. Springer, 2011, pp. 576–587.
  * [49] R. Ostrovsky, “Efficient computation on oblivious rams,” in _Proceedings of the twenty-second annual ACM symposium on Theory of computing_ , 1990, pp. 514–523.
  * [50] O. Ohrimenko, F. Schuster, C. Fournet, A. Mehta, S. Nowozin, K. Vaswani, and M. Costa, “Oblivious $\\{$Multi-Party$\\}$ machine learning on trusted processors,” in _USENIX Security_ , 2016, pp. 619–636.
  * [51] R. Poddar, G. Ananthanarayanan, S. Setty, S. Volos, and R. A. Popa, “Visor:$\\{$Privacy-Preserving$\\}$ video analytics as a cloud service,” in _USENIX Security_ , 2020, pp. 1039–1056.
  * [52] A. Law, C. Leung, R. Poddar, R. A. Popa, C. Shi, O. Sima, C. Yu, X. Zhang, and W. Zheng, “Secure collaborative training and inference for xgboost,” in _PPMLP_ , 2020, pp. 21–26.
  * [53] J. V. Bulck, M. Minkin, O. Weisse, D. Genkin, B. Kasikci, F. Piessens, M. Silberstein, T. F. Wenisch, Y. Yarom, and R. Strackx, “Foreshadow: Extracting the Keys to the Intel SGX Kingdom with Transient Out-of-Order Execution,” in _USENIX Security_ , 2018.
  * [54] Z. Chen, G. Vasilakis, K. Murdock, E. Dean, D. Oswald, and F. D. Garcia, “Voltpillager: Hardware-based fault injection attacks against intel sgx enclaves using the svid voltage scaling interface,” in _USENIX Security_ , 2021.
  * [55] D. Gullasch, E. Bangerter, and S. Krenn, “Cache games–bringing access-based cache attacks on aes to practice,” in _IEEE S &P_, 2011, pp. 490–505.
  * [56] Intel, “What technology change enables 1 terabyte (tb) enclave page cache (epc) size in 3rd generation intel® xeon® scalable processor platforms?” 2021\.
  * [57] E. Stefanov, E. Shi, and D. Song, “Towards practical oblivious ram,” _arXiv preprint arXiv:1106.3652_ , 2011.
  * [58] Intel, “Intel® Software Guard Extensions for Linux* OS,” 2020\. [Online]. Available: https://download.01.org/intel-sgx/sgx-linux/2.9.1/docs/Intel˙SGX˙Developer˙Reference˙Linux˙2.9.1˙Open˙Source.pdf
  * [59] Timescale, “Time series benchmark suite.” [Online]. Available: https://github.com/timescale/tsbs
  * [60] I. Demertzis, D. Papadopoulos, C. Papamanthou, and S. Shintre, “$\\{$SEAL$\\}$: Attack mitigation for encrypted databases via adjustable leakage,” in _USENIX Security_ , 2020, pp. 2433–2450.
  * [61] A. Papadimitriou, R. Bhagwan, N. Chandran, R. Ramjee, A. Haeberlen, H. Singh, A. Modi, and S. Badrinarayanan, “Big data analytics over encrypted datasets with seabed,” in _USENIX OSDI_ , 2016, pp. 587–602.
  * [62] R. Poddar, T. Boelter, and R. A. Popa, “Arx: an encrypted database using semantically secure encryption,” _Cryptology ePrint Archive_ , 2016.
  * [63] S. Eskandarian and M. Zaharia, “Oblidb: Oblivious query processing for secure databases,” _arXiv preprint arXiv:1710.00458_ , 2017.
  * [64] B. Fuhry, H. J. Jain, and F. Kerschbaum, “Encdbdb: Searchable encrypted, fast, compressed, in-memory database using enclaves,” in _IEEE/IFIP DSN_ , 2021, pp. 438–450.
  * [65] C. Priebe, K. Vaswani, and M. Costa, “Enclavedb: A secure database using sgx,” in _IEEE SP_. IEEE, 2018, pp. 264–278.
  * [66] A. Ahmad, K. Kim, M. I. Sarfaraz, and B. Lee, “Obliviate: A data oblivious filesystem for intel sgx.” in _NDSS_ , 2018.
  * [67] T. Hoang, M. O. Ozmen, Y. Jang, and A. A. Yavuz, “Hardware-supported oram in effect: Practical oblivious search and update on very large dataset,” _Proceedings on Privacy Enhancing Technologies_ , vol. 2019, no. 1, 2019.
  * [68] T. Hoang, R. Behnia, Y. Jang, and A. A. Yavuz, “Mose: Practical multi-user oblivious storage via secure enclaves,” in _ACM CODASPY_ , 2020, pp. 17–28.
  * [69] C. Adams, L. Alonso, B. Atkin, J. Banning, S. Bhola, R. Buskens, M. Chen, X. Chen, Y. Chung, Q. Jia _et al._ , “Monarch: Google’s planet-scale in-memory time series database,” _Proceedings of the VLDB Endowment_ , vol. 13, no. 12, pp. 3181–3194, 2020.
  * [70] T. Pelkonen, S. Franklin, J. Teller, P. Cavallaro, Q. Huang, J. Meza, and K. Veeraraghavan, “Gorilla: A fast, scalable, in-memory time series database,” _Proceedings of the VLDB Endowment_ , vol. 8, no. 12, pp. 1816–1827, 2015.