text:
\subsection*{Abstract}

While it is compelling to process large streams of IoT data on the cloud edge,
doing so exposes the data to a sophisticated, vulnerable software stack on the edge and hence security threats.
To this end, we advocate isolating the data and its computations in a trusted execution environment (TEE) on the edge, shielding them from the remaining edge software stack which we deem untrusted.

This approach faces two major challenges:
(1) executing high-throughput, low-delay stream analytics in a single TEE, which is constrained by
a low trusted computing base (TCB) and limited physical memory;
(2) verifying execution of stream analytics as the execution involves untrusted software components on the edge.
In response, we present StreamBox-TZ{} (SBT{}), a stream analytics engine for an edge platform that offers strong data security, verifiable results, and good performance.
SBT{} contributes a data plane designed and optimized for a TEE based on ARM TrustZone.
It supports continuous remote attestation for analytics correctness and result freshness while incurring low overhead.
SBT{} only adds 42.5~KB executable to the TCB (16\% of the entire TCB).
On an octa core ARMv8 platform, it delivers the state-of-the-art performance by processing input events up to 140 MB/sec (12M events/sec) with sub-second delay.
The overhead incurred by SBT{}'s security mechanism is less than 25\%.

\begin{comment}
While it is compelling to process IoT data streams at the cloud edge, doing so exposes the data to high security threats.
To this end, we present SBT{}, a stream analytics engine with strong data security on an edge platform.
SBT{} constructs a data plane and isolates it within a trusted execution environment (TEE) enforced by ARM TrustZone, shielding the data plane from the engine's control plane, the rich user libraries, and the underlying OS.

As its key contribution, SBT{} supports data-intensive, parallel computation inside one TEE while keeping low code complexity and compact physical memory footprint.
To do so,
it constructs low-level computation primitives to specifically suit the TEE;
it specializes abstractions and management for secure memory;
it leverages the (untrusted) control plane's performance hints in the TEE.
On an octa core ARMv8 platform,
SBT{} only adds 35KB executable to the trusted computing base (14\% increase);
it processes input events up to 240 MB/sec (20 M events/sec).
Compared to an insecure version of itself, SBT{} incurs throughput loss of 20--30\% in most benchmarks;
compared to commodity, insecure engines on the same platform, its throughput is higher by one order of magnitude.

i) to engineer low-level, protected computations specifically for the TEE;
ii) to specialize abstractions and management for the TEE's memory;
iii) to leverage the (untrusted) control plane's performance hints in the TEE.
Based on ARMv8 TrustZone, our SBT{} implementation only adds 35KB executable to the trusted computing base (14\% increase).
On an octa core Cortex-A53 platform, SBT{} processes input events up to XXX MB/sec (XXX M events/sec), which is only XXX lower than an insecure version of itself and one order of magnitude higher than insecure, commodity engines on the same platform.
\end{comment}

\begin{comment}
\note{unchanged. TBD}
Existing stream processing systems are inadequate for processing of Internet of Things (IoT) events at the cloud edge, showing weak data security and poor performance.
In response, we present SBT{}, a new stream processing engine that provides strong data security and high performance on a single edge platform.
SBT{}'s top structuring principle is to separate its data plane from its control plane as well as the underlying OS, and protect the data plane with a trusted execution environment enforced by ARM TrustZone.

Compared to commodity stream processing engines on the same hardware, SBT{} not only offers strong data confidentiality and integrity, but also increases throughput by 46$\times$.

\end{comment}

\section*{Acknowledgments}

The authors thank the anonymous reviewers and our shepherd, Eyal de Lara, for their insightful comments.
For this project: the authors affiliated with Purdue ECE were supported in part by NSF Award \#1718702, \#1619075, Purdue University CPS/IoT Seed Grant Program, and a Google Faculty Award;
the author affiliated with Northeastern University was supported in part by NSF Award \#1748334.

\section{Attestation for Correctness and Freshness}
\label{sec:attest}

SBT{} collects evidences for cloud consumers to verify two properties:
\textit{correctness}, i.e. all ingested data is processed according to the stream pipeline declaration;
\textit{freshness}, i.e. the pipeline has low output delays.

The above objective has several notable aspects.
i) We verify the behaviors of untrusted control plane, i.e., \textit{which} primitives it invokes on \textit{what} data and at \textit{what} time.
We do not verify trusted primitive{}s, e.g. if a Sort primitive indeed produces ordered data.
ii)
Verifying data lineages at the pipeline's intermediate operators or egress~\cite{data-provenance,ariadne}
is insufficient to guarantee correctness, i.e. all data ingested so far is processed according to the stream pipeline.
iii)
The windows of stream computations and watermarks triggering the computations must be attested, which are keys to stream model
(\S\ref{sec:bkgnd}).
iv) As the volume of evidences can be substantial, evidences must be compacted to save uplink bandwidth~\cite{farmbeats,satellites-iot}.

Therefore, SBT{} provides the following verification mechanism.
Agnostic to the pipeline being executed,
the data plane monitors dataflows among primitive{} instances at the TEE boundary,
and then generates audit records.
For low overhead, it eschews building data lineages on-the-fly unlike much prior work~\cite{ariadne,protracer,vc3}.
The data plane compresses audit records and flushes to the cloud both periodically and upon externalizing any analytics result.
We describe details below.

\input{fig-attest}

\paragraph{Audit records}
As being invoked by the control plane,
the data plane generates \textit{audit records}.
As illustrated in Figure~\ref{fig:attest}, the records track
i) ingested and externalized uArray{}s, ii) associations between uArray{}s and windows,
and iii) primitive{} executions (with optional hints supplied by the control plane) which establish \textit{derived-from}{} relations among uArray{}s.
The records further include ingested watermark values,
which are crucial for determining output delays as will be discussed below.
The data plane timestamps all the records.
It generates monotonically increasing identifiers for recorded uArray{}s.
We will evaluate the overhead of audit records in \sect{eval}.

\paragraph{Attesting analytics correctness}
The cloud verifier checks if all ingested uArray{}s flow through the expected trusted primitive{}s.
Such dataflows are deterministic given the arrivals of input data (including their windows), the watermarks, and the pipeline declaration.
Hence, the verifier replays all ingestion records on its local copy of the same pipeline.
It checks if all the records resulting from the replay match the ones reported by the edge (except timestamps).
The replay is symbolic without actual computations and hence fast.

Note that the verification works for stateful operators as well.
The state of a stream operator (e.g. temporal join) is only determined by all the inputs the operator has ever received.
Since the cloud can verify that all the ingested uArray{}s correctly flow through the expected trusted primitive{}s and thus stream operators, it knows that the operator's current state must be correct, and then all results derived from the operator state must be correct.

\paragraph{Attesting result freshness}
The key for the verifier to calculate the delay of an output result $R$ is to identify the watermark that triggers the externalization of $R$, according to the delay definition in Section~\ref{sec:bkgnd:pipeline}.
From the egress record of $R$, the verifier traces \textit{backward} following the \textit{derived-from}{} chain(s) until it reaches an execution record indicating that a watermark $W$ triggers the execution.
The verifier looks up the ingress record of $W$.
It calculates the difference between $W$'s ingress time and $R$'s egress time to be the delay of $R$.

\begin{comment}
\paragraph{Timed data lineage}
Such a lineage is a timestamped chronology originated from an ingested uArray{} including all uArray{}s deducted from the uArray{} and participating trusted primitive{}s.
A cloud consumer establish time data lineages for all all ingested uArray{}.
To do so, it traces \textit{forward} from one ingress record and follows chains of deduction relations.
The cloud consumer verifies analytics correctness by comparing the lineages against the pipeline's dataflow graph it possesses \note{improve};
To check result freshness, the consumer calculates output delay by forward tracing an ingested watermark.
(the \textbf{watermark} trace)

verifies correctness (i.e answering question i)) by starting from the ingress records and follows \textit{derive-from} relations to validate if all uArray{}s -- either ingested or produced inside the pipeline -- are processed according to the analytics.

By feed the ingress records as symbols through its own copy of the pipeline and compare the resultant compute records. No parallelism etc.

This ensures that all uArray{}s, ingested or produced inside the pipeline, are processed by the pipeline and no data is ignored.
This contrasts to existing data provenance on data deduce streams \cite{XXX} which can only validates the processing history of the pipeline output.

It propagates the \textit{derive-from} relations across primitive{}s in a pipeline, and keeps the relations as auxiliary data affixed to each uArray{}.

consume old data batches and produce
As batches flow through the

For any result uploaded to the cloud server, the data plane provides two evidences: data lineage~\cite{data-provenance}, a chronology of trusted primitive{}s executed in producing this result;
critical path trace, timestamped execution trace for processing the last data batch that contributes to this result.
By verifying the authenticity and correctness of the lineage,
the cloud server is able to verify if the desired computations are executed at the edge.
By examining the critical path trace, the server learns the result's output delay (as defined in \sect{bkgnd:pipeline}) and can assert its freshness, i.e. whether the output delay is under a target threshold.
To capture such lineage,

\end{comment}

\paragraph{Example}
In Listing~\ref{list:attest}, an uArray with identifier 0xF0 is ingested and segmented into two uArray{}s (0xF1 and 0xF2) for window 0 and 1 respectively.
Sort consumes uArray{} 0xF1 and produces uArray{} 0xF3.
A watermark with value 100 arrives and completes window 0.
Triggered by the watermark, SUM consumes uArray{} 0xF3 of window 0 and produces uArray{} 0xF5 as the result of window 0.
\input{list-attest}
The cloud verifier replays the ingress records on its local pipeline copy and learns that uArray{} 0xF1 is processed adhering to the pipeline declaration while uArray{} 0xF2 is yet to be processed.
It will assert analytics incorrectness if 0xF2 remains unprocessed until a future watermark completes window 1 (not shown).
To verify result freshness, the verifier traces result 0xF5 backward to find its trigger watermark 0xF4 and calculates the output delay to be 15 ($30-15$).

\begin{comment}
\paragraph{Columnar compression of records}
The data plane compresses audit records by exploiting rich locality within one record field and known data distribution in each field.
As shown in Figure~\ref{fig:compress},
the data plane produces raw audit records in memory in row format (i.e. one record after the other).
Before uploading a sequence of records, it compresses them by separating the record fields (i.e. columns) and applies different encoding schemes to compress individual columns:
i) Huffman encoding for primitive types (Op) and data counts (Cnt), the two columns likely contain skewed values;
ii) delta encoding for timestamps (Ts), uArray{} identifiers (Data), and window numbers, which increment monotonically.
Our compression is inspired by columnar databases~\cite{c-store}.
We will evaluate the efficacy of compression in \sect{eval}.
\end{comment}

\paragraph{Columnar compression of records}
The data plane compresses audit records by exploiting locality within one record field and known data distribution in each field.
The data plane produces raw audit records in memory (with the format shown in Figure~\ref{fig:attest}) and in a row order, i.e. one record after the other.
Before uploading a sequence of records, it separates the record fields (i.e. columns) and applies different encoding schemes to individual columns:
i) Huffman encoding for primitive types and data counts, the two columns likely contain skewed values;
ii) delta encoding for timestamps, uArray{} identifiers, and window numbers, which increment monotonically.
Our compression is inspired by columnar databases~\cite{c-store}.
We will evaluate the efficacy of compression in \sect{eval}.

\section{Background \& Motivation}
\label{sec:bkgnd}

\subsection{ARM for Cloud Edge}
As typical hardware for IoT gateways~\cite{iot-survey},
recent ARM platforms offer competitive performance at low power, suiting edge well.
Most modern ARM cores are equipped with TrustZone~\cite{arm-trustzone}, a security extension for TEE enforcement.
TrustZone logically partitions a platform's hardware resources, e.g. DRAM and IO, into a normal (insecure) and a secure world.
CPU cores independently switch between two worlds.
A TEE atop TrustZone{} owns dedicated, \textit{trusted IO}, a unique feature that other TEE technologies such as Intel SGX~\cite{intel-sgx} lack.

\noindent \textbf{Trusted IO} is a unique feature of ARM TrustZone, implemented through hardware components including TrustZone Address Space Controller (TZASC) and TrustZone Protection Controller (TZPC).
TZASC allows privilege software to logically partition DRAM between the normal and the secure worlds.
Similarly, TZPC allows to configure IO peripherals accessible to either world.
Any peripheral owned by the secure world is completely enclosed in the secure world.
We use trusted IO to support the trusted source-edge links on the cloud edge (\S\ref{sec:overview:scope}).

\subsection{Stream Analytics}
\label{sec:motiv:data}
\label{sec:bkgnd:pipeline}

\input{fig-pipeline-stacked}

\begin{comment}
\paragraph{High-velocity data}
A large volume of IoT devices will continuously produce large data streams.
For instance, a single refinery is able to generate 1TB of data~\cite{ibm-iiot} per day.
Since the raw data events are likely to be noisy and highly redundant,
they first should be cleansed and summarized at the edge of cloud~\cite{shi16iotj,satya-edge-iot} before being sent to data centers for deeper analysis.
\end{comment}

\paragraph{Stream Model}
We target stream analytics over sensor data.
A data stream consists of sensor events that carry timestamps defined by event occurrence,
as illustrated in Figure~\ref{fig:pipeline-stacked}(a).
Programmers specify a pipeline of continuous computations called \emph{operators}, e.g. \code{Select} and \code{GroupBy}, that are extensively used for telemetry analytics~\cite{sensorbee,smart-power-plugs}.
As data arrives at the edge, a stream analytics engine{} ingests the data at the pipeline ingress, pushes the data through the pipeline, and externalizes the results at the pipeline egress.

We follow a generic stream model~\cite{naiad,sparkstreaming,dataflowAkidau2015,trill,streamscope}.
Operators execute on event-time scopes called \textit{windows}.
Data sources emit special events called \textit{watermarks}.
A watermark guarantees no subsequent events in the stream will have event times earlier than the watermark timestamp.
A pipeline's \textit{output delay} is defined as the elapsed time starting from the moment the ingress receives the watermark signaling the completion of the current window to the moment the egress externalizes the window results~\cite{streambox}.
A pipeline may maintain its internal states organized by windows at different operators.
See prior work~\cite{cql} for a formal stream model.

\paragraph{Analytics example: Power load prediction}
Figure~\ref{fig:pipeline-stacked}(b-c) shows an example derived from an IoT scenario~\cite{smart-power-plugs}:
it predicts future household power loads based on power loads reported by smart power plugs.
The example pipeline ingests a stream of power samples and groups them by 1-second fixed windows and by houses.
For each house in each window, it aggregates all the loads and predicts the next-window load as an exponentially weighted moving average over the recent windows.
At the egress, the pipeline emits a stream of per-house load prediction for each window.

\paragraph{Stream analytics engine{}s}
\label{sec:bkgnd:engine}
Stream pipelines are executed by a runtime framework called a stream analytics engine{}~\cite{esper,sensorbee,msft-azure-edge,cisco-edge-fabric,dell-statistica,streambox}.
A stream analytics engine{} consists of two types of function:
\textit{data functions} for data move and computations;
\textit{control functions} for
resource management and computation orchestration, e.g. creating and scheduling tasks.
The boundary between the two is often blurry.
To amortize overheads, control functions often organize data in \textit{batches} and invoke data functions to operate on the batches.

\subsection{Security Threats \& Design Objectives}

\begin{comment}
Edge platforms face common security threats in IoT deployment.
First, IT expertise is weak.
Edge platforms are likely managed by field experts (such as farmers~\cite{farmbeats}, firefighters~\cite{Wu:2017:ECE:3132465.3132475}, and petroleum engineers~\cite{mckinsey-iot}) rather than IT experts.
Such lack of professional supervision is known to result in weak configurations~\cite{symantec-iot-security,windriver-iot-security}.
Second, the infrastructure is weak.
Deployed in the field (e.g. farms~\cite{farmbeats}, fireground~\cite{Wu:2017:ECE:3132465.3132475}, and offshore oil rigs~\cite{mckinsey-iot}), the edge often experiences slow uplinks to the cloud and hence much delayed software security updates.
For cost saving, edge analytics may need to share OS and hardware with other high-risk, untrusted software~\cite{farmbeats} such as web browsers. \note{compress}
\end{comment}

The edge faces common threats in IoT deployment.
i) IT expertise is weak.
Edge platforms are likely managed by field experts~\cite{farmbeats,Wu:2017:ECE:3132465.3132475,mckinsey-iot} rather than IT experts.
Such lack of professional supervision is known to result in weak configurations~\cite{symantec-iot-security,windriver-iot-security}.
ii) The infrastructure is weak.
Deployed in the field, the edge often sees slow uplinks~\cite{farmbeats,satellites-iot} and hence much delayed software security updates.
For cost saving, edge analytics may need to share OS and hardware with other high-risk, untrusted software such as web browsers~\cite{farmbeats}.

Besides the common threats, existing edge software stacks entrust IoT data with commodity OSes, analytics engines, and language runtimes (e.g. JVM). However, these components are incapable of offering strong security guarantees due to their complexity and wide interfaces. Each of them easily contains more than several hundreds of KSLoC~\cite{relay-ESEC-FSE07}. Exploitable vulnerabilities are constantly discovered~\cite{anatomy-java-exploits, golang-security, CVE-2010-3190, CVE-2008-0171, chen2011linux}, making these components untrusted in recent research~\cite{overshadow, trustvisor, Flicker, inktag}. By exploiting these vulnerabilities, a local adversary as an edge user program may compromise the kernel through the wide user/kernel interfaces~\cite{CVE-2018-8822, CVE-2017-11176} or attack an analytics engine through IPC~\cite{CVE-2009-2493}; a remote adversary, through the edge's network services, may compromise analytics engines~\cite{CVE-2017-12629} or the OS~\cite{CVE-2016-10229}.
A successful adversary may expose IoT data, corrupt the data, or covertly manipulate the data. Taking the application in Figure~\ref{fig:pipeline-stacked}(b) as an example, the adversary gains access to the smart plug readings, which may contain residents' private information, and injects fabricated data.

\paragraph{Objectives}
We aim three objectives for stream analytics over telemetry data on an edge platform:
i) confidentiality and integrity of IoT data, raw or derived;
ii) verifiable correctness and freshness of the analytics results;
iii) modest security overhead and good performance.

\begin{comment}
\begin{myenumerate}
\item
Data confidentiality and integrity: no IoT data (raw or derived) is leaked to untrusted identities; only trusted computations can manipulate the IoT data.
\item
Verifiable correctness and freshness: the cloud consumer is able to attest analytics correctness and edge-incurred delays.
\item
Performance: the analytics achieves good throughput on an edge platform
(capable of saturating Gigabit Ethernet, the edge's typical IO on~\cite{fusisoft-edge, ni-edge}) with sub-second delay~\cite{shi16iotj}.
\end{myenumerate}
\end{comment}

\begin{comment}
\note{Heejin - bring the proposal writing here}
Besides the above threats to IoT data, current edge processing significantly widens the attack surface by exposing the data to an analytics software stack that is much larger and more complex than IoT sensor software.
This is illustrated in Figure~\ref{fig:div}(a).
Of the software stack, a modern stream analytics engine{} contains
a large code base
(e.g. 22K for a research prototype~\cite{streambox} and around 550K for two production engines~\cite{apache-flink,esper}).
Such an engine depends on external third-party libraries, such as Intel TBB (88K SLoC)~\cite{intel-tbb} for parallel algorithms and Facebook folly (200K SLoC)~\cite{folly} for efficient data structures.
Many popular engines~\cite{apache-flink,sensorbee,sparkstreaming} further depend on modern language runtimes such as Go (94K SLoC) and JVM ($\sim$1.2M SLoC).
Beneath the userspace is a commodity OS kernel containing millions of SLoC~\cite{relay-ESEC-FSE07}.
It is difficult for such a sophisticated software stack to provide strong security guarantees.
User libraries and runtimes commonly see exploitable vulnerabilities~\cite{anatomy-java-exploits,golang-security,CVE-2010-3190,CVE-2009-2493,CVE-2008-0171}.
Commodity OS kernels are known to be vulnerable~\cite{Chen:2011:LKV:2103799.2103805} and considered untrusted in recent research~\cite{overshadow,trustvisor,Flicker,inktag}.
A successful attacker compromising \textit{any} layer in the software stack gains full data access.
\end{comment}

\begin{comment}
\paragraph{Consequences}
Current edge processing significantly widens attack surface of IoT data.
A successful attacker compromising \textit{any} layer in the software stack gains full data access.
In the agriculture IoT example (\S\ref{sec:intro}), the attackers may be able to monitor the farm's pest activities, silently drop alarming pest events, and even inject fabricated pest activities that lead to harmful pesticide schedules.
We will discuss the inadequacy of existing protection mechanisms in \sect{motiv:objective}.
\end{comment}

\section{Security Approach Overview}
\label{sec:bkgnd:secmodel}
\label{sec:motiv:objective}

\subsection{Scope}
\label{sec:overview:scope}
\paragraph{IoT scenarios}
We target an edge platform that captures and analyzes telemetry data.
We recognize the significance of mission-critical IoT with tight control loops, but do not target it.
Our target scenario includes source sensors, edge platforms, and a cloud server which we dub ``cloud consumer''.
All the raw IoT data and analytics results are owned by one party.
The sensors produce trusted events, e.g. by using secure sensing techniques~\cite{IamSensor,sw_abstractions,YouProve}.
The cloud consumer is trusted; it installs analytics pipelines to the edge and consumes the results uploaded from the edge.
We consider \textit{untrusted} source-edge links (e.g. public networks) which requires data encryption by the source, as well as \textit{trusted} source-edge links (e.g. direct IO bus or on-premise local networks), and will evaluate the corresponding designs (\S\ref{sec:eval}).
We assume untrusted edge-cloud links, which require encryption of the uploaded data.

\paragraph{In-scope Threats}
We consider malicious adversaries interested in learning IoT data, tampering with edge processing outcome, or obstructing processing progress.
We assume powerful adversaries: by exploiting weak configurations or bugs in the edge software, they already control the entire OS and all applications on the edge.

\paragraph{Out-of-scope Threats}
We do not protect the confidentiality of stream pipelines, in the interest of including only low-level compute primitives in a lean TCB.
We do not defend the following attacks.
\begin{enumerateinline}

\item
Attacks to non-edge components assumed trusted above, e.g. sensors~\cite{walnut}.

\item
Exploitation of TEE kernel bugs~\cite{vtz, CVE-2015-4421, CVE-2015-4422}.

\item
Side channel attacks:
by observing hardware usage outside TEE,
adversaries may learn the properties of protected data, e.g. key skew~\cite{armageddon}.
Note that controlled-channel attack~\cite{controlledChannel} cannot be applied to ARM TrustZone
as it has separate page management within a separate secure OS unlike Intel SGX.

\item
Physical attacks, e.g. sniffing TEE's DRAM access~\cite{tampering,lowCostAttack}.
Many of these attacks are mitigated by prior work~\cite{sel4,opaque,sentry,TZ-CaSE} orthogonal to SBT{}.

\end{enumerateinline}

Note that TEE code authenticity and integrity are already ensured by the TrustZone hardware, i.e. only code trusted by the device vendor can run in TrustZone and its integrity is protected by TrustZone.

\input{sec-analysis}

\section{Key Design Choices}

\section{Design Overview}
\label{sec:overview}

\subsection{Challenges}
\label{sec:overview:challenges}

Our approach raises three challenges.
i) \textbfit{Architecting the engine with a proper protection boundary}.
This hinges on a key trade-off among TEE functional richness, overhead of TEE entry/exit, and TCB size.
ii) \textbfit{Optimizing data functions within a TEE}.
Processing of high-velocity data in a TEE strongly favors simple algorithms and compact memory.
Yet, existing stream engines often operate numerous short-lived objects indexed in hash tables or trees~\cite{sparkstreaming,streambox,sensorbee,trill,streamscope}, e.g. for grouping events by key.
They manage these objects with generic memory allocators~\cite{streambox} or garbage collectors~\cite{facade,sparkstreaming}.
Such designs poorly fit a TEE's small TCB and limited DRAM portion, e.g.
typically tens of MB for TrustZone{} TEE and up to 128 MB for Intel SGX enclave ~\cite{secureKeeper}.
iii) \textbfit{Verifying stream analytics results}.
This requires to track unbounded data flows in stream pipelines,
validate if operators respect the temporal properties, e.g. windows, and minimize the resultant overhead in execution and communication.

\input{inadequacy}

\subsection{StreamBox-TZ{} in a Nutshell}
\label{sec:overview:nutshell}

SBT{} builds on TrustZone~\cite{arm-trustzone} due to ARM's popularity for the edge and trusted IO benefiting stream analytics (\S\ref{sec:bkgnd}).

\paragraph{Programmability}
Programming SBT{} is similar to programming commodity engines such as Spark Streaming~\cite{sparkstreaming} and Flink~\cite{apache-flink}.
Analytics programmers assemble pipelines with high-level, declarative operators as exemplified in Figure~\ref{fig:pipeline-stacked}(c).
SBT{} provides most of the common operators offered by commodity engines, as summarized in Table~\ref{tab:operators}.
These stream operators are widely used for analytics over telemetry data~\cite{sensorbee,smart-power-plugs}.
SBT{} supports User Defined Functions (UDFs) that are certified by a trusted party, which is a common requirement in TEE-based systems~\cite{enclaveDB}.

\paragraph{SBT{} architecture}
As shown in Figure~\ref{fig:arch},
SBT{}'s data plane incarnates as a TrustZone{} module.
SBT{} runs its control plane as a parallel runtime in the normal world{}.
The control plane invokes the data plane through a narrow interface (details in \sect{eval}).
The control plane orchestrates the execution of analytics pipelines.
It creates plentiful parallelism among and within operators.
It elastically maps the parallelism to a pool of threads it maintains.
At a given moment, all threads may simultaneously execute one operator as well as different operators over different data.

\begin{comment}
\paragraph{Control plane}
The control plane orchestrates the execution of analytics pipelines.
It creates plentiful parallelism among and within operators.
It elastically maps the parallelism to a pool of threads it maintains.
At a given moment, all threads may simultaneously execute one operator as well as different operators over different data.
\end{comment}

\paragraph{Data plane \& design choices}
SBT{}'s data plane consists of only the trusted primitive{}s and a runtime for them.

i) Trusted primitive{}s are stateless, single-threaded functions that are oblivious to synchronization.
We do not enclose whole stream pipelines in the data plane, because a stream pipeline must be scheduled dynamically for parallelism and handling high-velocity data.
We do not enclose whole declarative operators in the data plane, because
one operator instance has internal thread-level parallelism and hence requires thread management logic.
Our choice keeps the data plane lean, leaving out all control functions including scheduling and threading.
This contrasts to many other engines pulling whole analytics to TEE as shown in Table~\ref{tab:cmp}.

Although exporting low-level primitives entails more TEE switches,
the costs are lower on modern ARM~\cite{azab14ccs,vtz} and can be amortized by data batching, as will be discussed soon.

ii) The data plane incorporates minimum runtime functions:
memory management and paging, which are critical to TEE integrity;
cache coherence of parallel primitive{}s, which is critical to parallelism.
The data plane is agnostic to declarative operators and pipelines being executed.

For attestation, the data plane generates audit records on data ingress/egress, watermarks, and primitive{} executions.
It reduces overhead via data batching and record compression.

\begin{comment}
The data plane consists of only i) a library of stream computations, called \textit{trusted primitive{}s}, as building blocks for declarative operators summarized in Table~\ref{tab:operators}
and ii) a runtime supporting trusted primitive{}s, including memory management, paging, and support for cache-coherent parallelism.
We will present trusted primitive{}s in Section~\ref{sec:primitive} and memory management in Section~\ref{sec:mm}.

\note{highlight why mm in tcb}
We devise such a compact data plane with two rationales.
First, the data plane should eschew exporting functions for executing whole declarative operators:
as one operator instance has internal thread-level parallelism,
doing so would pull thread management to the data plane and hence add substantial complexity.
Second,
although a lean data plane entails more frequent TEE entries and exits, such costs are becoming lower on modern ARM~\cite{azab14ccs,vtz} and can be  further amortized by data batching, as will be discussed below.
\end{comment}

\begin{comment}
\paragraph{Protected data path}
Stream data and computations always reside in TEE.
As shown in Figure~\ref{fig:arch}, the data plane ingests data through TrustZone{}'s trusted IO.
The data plane batches the ingested stream events, returns the opaque references to these batches to the control plane, hence triggering the control plane to schedule operator execution.
As the execution proceeds, the control plane requests computations on the protected data by invoking trusted primitive{}s in TEE and passing in opaque references.
The invoked trusted primitive{}s further produce new data batches and return their opaque references to the control plane.
At the pipeline egress, the data plane encrypts, signs, and sends the result to the cloud.
We will discuss opaque references and batch sizes in Section~\ref{sec:impl}.
\end{comment}

\begin{comment}
\paragraph{Attestation for result correctness and freshness}
The data plane monitors data ingress/egress, watermarks, and primitive{} executions.
It generates audit records to capture complete and deterministic dataflows as well as execution timing.
It reduces the overhead by data batching and record compression.
By authenticating and replaying these records,
a cloud server verifies if all ingested data is processed by desired computations according to the stream model, and if the edge processing incurs low delay.
We will present attestation in Section~\ref{sec:attest}.
\end{comment}

\begin{comment}
\paragraph{Protecting multiple apps}
One common criticism against TrustZone is that, due to its limited number of ``worlds'', lacks direct hardware support for multiple applications.
However, we do not see this as a major limit for supporting IoT edge analytics:
i) unlike the multi-tenant cloud environment, today's most IoT deployment run one analytics engine owned by one user;
ii) today's trusted OSes governing the secure environment \cite{optee,sierra-tee} are capable of executing secure software components belonging to different applications concurrently, offering isolation similar to a commodity OS, e.g. separate address spaces.
\end{comment}

\begin{comment}
\subsubsection*{(4)~Taking performance hints from the untrusted}

Despite distrusting the engine's control plane,
we devise a narrow interface for the control plane to disclose its runtime knowledge -- the data consumption plan -- to the data plane.
The hints assist the data plane to generate compact memory layout and reclaim memory effectively.
As the hints only affect the secure memory placement \textit{policy},
they do not weaken the targeted data security.
Misleading hints may increase the usage of secure memory but will not compromise the protection for the data.
We will discuss the hints in detail in Section~\ref{sec:mm}.

It is therefore crucial to verify the analytics results and attest the control plane decisions at the cloud servers
\end{comment}

\paragraph{Coping with secure memory shortage}
When compute cost or data ingestion rate is high,
SBT{} may run short of secure memory.
To avoid data loss in such a situation, SBT{} adds backpressure to source sensors, slowing down data ingestion.
In the current implementation, SBT{} triggers backpressure when ingestion exceeds a  user-defined threshold; we leave as future work automatic flow control, i.e. tuning the threshold online per available secure memory and backlog.

\begin{comment}
\hp{
As current SBT{} depends on OP-TEE and TrustZone-enabled ARM devices, improving its portability and compatibility with other TEEs is left as our future work. We believe that SBT{} should not be confined to the ARM architecture as our designs address a generic challenge.

Furthermore, SBT{} currently lacks support for flow control, which may incur data overflow or dropping due to memory pressure.
While SBT{} adds backpressure to sensors by observing task execution time and schedule delay, it should take a receive buffer size and available secure memory into account.
We leave the implementation of dynamic flow control with considerations for the features mentioned above as future work.
}
\end{comment}

\section{Conclusions}
This paper presents StreamBox-TZ{} (SBT{}), a secure stream analytics engine designed and optimized for a TEE on an edge platform.
SBT{} offers strong data security, verifiable results, and competitive performance.
On an octa core ARM machine,
SBT{} processes up to tens of millions of events per second;
its security mechanisms incur less than 25\% overhead.

\section{Evaluation}
\label{sec:eval}

\input{fig-scalability}

We answer the following questions through evaluation:
\begin{smitemize}
\item Does SBT{} result in a small TCB? (\S\ref{sec:eval:source})
\vspace{-2pt}
\item What is SBT{}'s performance and how is it compared to other engines? What is the overhead? (\S\ref{sec:eval:perf})
\vspace{-2pt}
\item How do our key designs impact performance (\S\ref{sec:eval:feature})?
\end{smitemize}

\subsection{TCB Analysis}
\label{sec:eval:source}

\paragraph{TCB size}
Table~\ref{tab:src} shows a breakdown of the SBT{} source code.
Despite a sophisticated control plane,
the data plane only adds 5K SLoC to the TCB.
SBT{}'s memory management is in 740 SLoC, 9$\times$ fewer than glibc's \code{malloc} and 20$\times$ fewer than \code{jemalloc}~\cite{jemalloc}.
The size of data plane is 42.5~KB, a small fraction (16\%) of the entire OP-TEE binary.

\paragraph{TCB interface}
The SBT{}'s data plane exports only four entry functions:
two for data plane initialization/finalization,
one for debugging,
and one shared by all 23 trusted primitive{}s.
The last function accepts and returns opaque references (\S\ref{sec:overview}).
No state is shared across the protection boundary.

\paragraph{Comparison with alternative TCBs}
Compared to enclosing whole applications in TCB~\cite{scone,haven,graphene-sgx},
SBT{} keeps most of the engine out, shrinking the TCB by at least one order of magnitude.
Compared to directly carving out~\cite{glamdring,rubinov16icse} the original StreamBox's data functions for protection, SBT{} completely avoids sophisticated data structures (e.g.  AtomicHashMap~\cite{folly} used by StreamBox)  that mismatch TCB.
Compared to VC3~\cite{vc3} that implements Map/Reduce operators in a TCB with $\sim$9K SLoC, SBT{} supports much richer stream operators within a 2$\times$ smaller TCB.

\subsection{Performance \& Overhead}
\label{sec:eval:perf}

\input{tab-plat}
\input{tab-src}
\paragraph{Methodology}
We evaluate SBT{} on a HiKey board as summarized in Table~\ref{tab:plat}.
We chose HiKey for its good OP-TEE support~\cite{optee} and that it is among the few boards with TrustZone{} programmable by third parties.
We built \textit{Generator}{}, a program sends data streams over ZeroMQ TCP transport~\cite{zmq} to SBT{}.
We run the cloud consumer on an x86 machine.
Data streams are encrypted with 128-bit AES.

In the face of HiKey's platform limitations, we set up the engine ingestion as follows.
i) Although Gigabit Ethernet on edge platforms is common~\cite{marvell-armada-8k,imx7},
Hikey's Ethernet interface (over USB) only has
20MB/sec bandwidth.
We have verified that the interface is saturated by SBT{} with 4 cores.
Hence, we report performance when SBT{} and \textit{Generator}{} both run on HiKey communicating over ZeroMQ TCP, which still fully exercise the TCP/IP stack and data copy.
ii)
\begin{comment}
Despite HiKey's TEE is capable of directly operating the Ethernet interface
our OP-TEE version lacks corresponding device drivers.
Hence, we emulate SBT{}'s direct data ingestion to TEE by running the ingestion in a privileged process in normal world{} and bypassing data copy across the TEE boundary.
\end{comment}
Although HiKey's TEE is capable of directly operating Ethernet interface as trusted IO, our OP-TEE version lacks the needed drivers.
Hence, we emulate SBT{}'s direct data ingestion to TEE by running the ingestion in a privileged process in the normal world{}, and bypassing data copy across the TEE boundary.
Our test harness continuously replays pre-allocated secure memory buffers populated with events.

As summarized in Table~\ref{tab:exp}, we test SBT{} as well as three modified versions:
\textbf{\textit{SBT ClearIngress}{}} ingests data in cleartext; this is allowed if source-edge links are trusted as defined in our threat model (\S\ref{sec:bkgnd:secmodel}).
\textbf{\textit{SBT IOviaOS}{}} does not exploit TrustZone{}'s trusted IO: the untrusted OS ingested (encrypted) data and copies the data across TEE boundary to the data plane.
\textbf{\textit{Insecure}{}} completely runs in the normal world{} with ingress and egress in cleartext, showing native performance.
This is basically StreamBox~\cite{streambox} with SBT{}'s optimized stream computations (\S\ref{sec:primitive}).
We report the engine performance as its maximum input throughput when the pipeline output delay (defined in \S\ref{sec:bkgnd:pipeline}) remains under a target set by us.

\input{tab-exp}
\paragraph{Benchmarks}
\input{exp-benchmarks}

\input{fig-existing}
\paragraph{End-to-end performance}
Figure~\ref{fig:scalability} shows the throughputs of all benchmarks as a function of hardware parallelism.
SBT{} can process up to multiple millions of events within sub-second output delays (labeled atop each plot).
For simpler pipelines such as WinSum{} and Filter{}, SBT{} processes around 12M events/sec (140 MB/sec).
This throughput saturates one GbE link which is common on IoT gateways
~\cite{imx7}.
Overall, SBT{} can use all 8 cores in a scalable manner.

SBT{}'s absolute performance is state of the art.
We test three popular, insecure stream engines:
Flink~\cite{apache-flink}, designed for distributed environment and known for good single-node performance~\cite{flink-single-perf};
Esper~\cite{esper}, designed for a single machine;
SensorBee~\cite{sensorbee}, designed for sensor data processing on a single device.
As shown in Figure~\ref{fig:esper}, on the same hardware (HiKey) and the same benchmark (WinSum{}),
we have measured that SBT{}'s throughput is at least one order of magnitude higher than the others.
This is because i) our \textit{Insecure} baseline has high performance for its rich task parallelism (inherited from StreamBox~\cite{streambox}) and native, vectorized stream computations (new contributions);
ii) SBT{} only imposes modest security overhead, as will be shown later.

\begin{comment}
 engines~\cite{sensorbee,apache-flink,esper}.
SBT{} outperforms popular insecure engines.
Note that orchestrating SBT{}'s ARM vectorized operators with parallel control functions written by native language,
\textit{Insecure}{} (i.e. native performance as StreamBox~\cite{streambox} invoking SBT{}'s stream computations) obtains state-of-the-art throughput already (we will contrast EdgeFlow to \textit{Insecure}{} as security overhead below).

As shown in Figure~\ref{fig:esper}, on the same hardware (HiKey) and the same benchmark (WinSum{}), SBT{} achieves at least 10$\times$ higher throughput than others.
Note that these commodity engines have \textit{no security mechanisms}.
One could create secure variants of these engines by additionally applying generic TEE frameworks~\cite{glamdring}; with the additional overhead, such secure variants will exhibit even lower performance.
\end{comment}

\paragraph{Comparison to secure stream engines}
The comparison is challenged by that TrustZone was rarely exploited for protecting data-intensive computations.
To our knowledge, i) no analytics engines use TrustZone for data protection and ii) no systems can partition an insecure stream engine for TrustZone.
Note that popular secure analytics engines, e.g. VC3~\cite{vc3} and Opaque~\cite{opaque}, not only require SGX but also target batch processing instead of stream analytics.
To this end, we qualitatively compare SBT{} with SecureStreams~\cite{securestreams}, the closest system we are aware of.
Designed for an x86 cluster, SecureStreams uses SGX to protect stream operators and targets strong data security.
On a benchmark similar to WinSum it was reported to achieve 10 MB/sec, one magnitude lower than SBT{} on WinSum.
Furthermore,
SecureStreams achieved such performance on a small x86 cluster which has much richer resource than HiKey: the former has
faster CPUs (8x i7-6700@3.4GHz versus 8x Cortex-A53@1.2GHz), larger DRAM (16~GB versus 2~GB), higher power (130W versus 36W), and higher cost (\$600 versus \$65).

SBT{}'s advantage comes from i) data exchange via coherent memory inside one TEE, instead of exchanging encrypted messages among workers; ii) memory management specialized for streaming, and iii) vectorized computations.

\begin{comment}
\paragraph{Is SBT{}'s performance state of art?}
We further demonstrate that SBT{} performance is state of art.
\hp{
We further compare SBT{} with popular stream engines~\cite{sensorbee,apache-flink,esper}.
With a small security overhead, SBT{} outperforms popular insecure engines.
Note that orchestrating SBT{}'s ARM vectorized operators with parallel control functions written by native language,
\textit{Insecure}{} (i.e. native performance as StreamBox~\cite{streambox} invoking SBT{}'s stream computations) obtains state-of-the-art throughput already (we will contrast EdgeFlow to \textit{Insecure}{} as security overhead below).
}
As shown in Figure~\ref{fig:esper}, on the same hardware (HiKey) and the same benchmark (WinSum{}), SBT{} achieves at least 10$\times$ higher throughput than others.
Note that these commodity engines have \textit{no security mechanisms}.
One could create secure variants of these engines by additionally applying generic TEE frameworks~\cite{glamdring}; with the additional overhead, such secure variants will exhibit even lower performance.

To sum up, SBT{} benefits from
i) data parallelism exploited in its optimized data plane;
ii) task parallelism created by its control plane and supported by the coherent address space in its data plane.

\hpsout{
In summary, on an edge platform SBT{} outperforms a recent secure engine and popular insecure engines.
SBT{} benefits from
i) data parallelism exploited in its optimized data plane;
ii) task parallelism created by its control plane and supported by the coherent address space in its data plane.
The last enables trusted primitive{}s to exchange data via shared memory, instead of using encrypted message-passing as the distributed workers of SecureStreams must do.
}
\end{comment}

\paragraph{Security overhead}
We investigate the overhead of the new security mechanism contributed by SBT{} -- its isolated data plane.
We assess the overhead as the throughput loss of \textit{SBT ClearIngress}{} as compared to \textit{Insecure}{} (i.e. native performance as StreamBox~\cite{streambox} invoking SBT{}'s stream computations), both paying same costs for data ingress.
The target output delays are the same (labeled atop each plot in Figure~\ref{fig:scalability}).
The security overhead is less than 25\% in all benchmarks.
This is similar to or lower than the reported overhead (20--70\%) in recent TEE systems~\cite{glamdring,graphene-sgx,scone}.
\textit{\textbf{Overhead analysis:}}
The security overhead mostly comes from world switch, among operators and inside each operator.
To understand the switch cost within an operator,
we profile \code{GroupBy}, one of the most costly operators.
We test different input batch sizes, which have a strong impact on TEE entry/exit rates and hence isolation overhead (\S\ref{sec:overview}).
Figure~\ref{fig:overhead} shows a run time breakdown.
When each input batch contains 128K (close to the value we set for SBT{}) or more events,
more than 90\% of the CPU time is spent on actual computations in TEE.
The CPU usage of TEE memory management is as low as 1--2\%.
In the extreme case where each input batch contains as few as 8K events, the overhead of world switch starts to dominate.
Most of the world switch overhead comes from OP-TEE instead of the CPU hardware (a few thousand cycles per switch),
suggesting room for OP-TEE optimization.

\paragraph{Impact of decrypting ingress data}
Decrypting ingress data
is needed
if source-edge links are untrusted (\S\ref{sec:bkgnd:secmodel}) and source must send encrypted data.
It has substantial performance impact.
By comparing SBT{} to \textit{SBT ClearIngress}{},
turning on/off ingress decryption leads to 4\% -- 35\% throughput difference when all 8 cores are in use.
The performance gap is more pronounced for simple pipelines, which has higher ingestion throughput leading to  higher decryption cost.

\begin{comment}
\sysenc{}, on the other hand, incurs much higher overhead as shown in Figure~\ref{fig:scalability}.
Its throughput is capped around 30MB/s, resulting in  30\%--90\% throughput loss compared to \textit{Insecure}{} (note the throughput is still higher than commodity engines, as we will show below).
This is because the ingestion pays high cost for decryption and cross-world data move, which limits the whole engine scalability.
It is worth noting that the cost of data move is non-trivial, contributing 20--30\% throughput loss.
The comparison between \textit{\sys{}}{} and \textit{SBT IOviaOS}{} highlights the advantage of TrustZone{}'s IO protection, which allows data to directly flow into the TEE without extra decryption or copy.
\end{comment}

\paragraph{TEE memory usage}
While sustaining high throughput, SBT{} consumes a moderate amount of physical memory, ranging from 20~MB to 130~MB as shown in Figure~\ref{fig:scalability}.
The memory usage is as low as 1--6\% of the total system DRAM.
The virtual memory usage is also low,
often 1--5\% of the entire virtual address space in OP-TEE.
The memory usage increases with the throughput, since there will be more in-flight data.
On the same platform, Flink's memory consumption is 3$\times$ higher, due to its hash-based data structures and the use of JVM.
This validates our choice of uArray{}s.

\paragraph{Attestation overhead}
Attestation incurs minor overhead to both the edge and the cloud.
We measured that SBT{} produces 300--400 audit records per second across all our benchmarks, and spends a few hundred cycles on producing each record.
Compressing such record streams on HiKey consumes 0.2\% of total CPU time.
Our consumer written in Python on a 4-core i7-4790 machine replays 57K records per second with a single core,
suggesting a capability of attesting near 500 SBT{} instances simultaneously.
We will evaluate the efficacy of record compression in Section~\ref{sec:eval:feature}.

\begin{comment}
\subsection{Overhead Analysis}
\label{sec:overhead}

To gain comprehensive understanding of the SBT{} overhead, we show a detailed runtime breakdown for \code{GroupBy}, one of the most costly operators.
\code{GroupBy} internally invokes the \code{Sort} primitive{} as shown in Table~\ref{tab:operators}.
In the experiment, the control plane runs 8 worker threads to repeatedly executes \code{GroupBy} in parallel.
As shown in Figure~\ref{fig:overhead}, a majority (more than 90\%) of the CPU time is spent on the computation in the secure world{} when each input uArray{} contains 128K or more events.
The CPU time consumed by secure memory management (including page fault handler and allocator) is as low as 1--2\%, despite that numerous temporary uArray{}s (in \code{Sort}) and streaming uArray{}s are generated in the experiment.
Switches between normal/secure worlds, each taking around a few thousand cycles, incur negligible overhead.
In extreme cases where each input contains as few as 8K events, the overhead of OP-TEE starts to dominate.
\end{comment}

\subsection{Validation of Key Design Features}
\label{sec:eval:feature}

\paragraph{Exploitation of trusted IO}
As shown in Figure~\ref{fig:scalability}, a comparison between SBT{} and \textit{SBT IOviaOS}{} demonstrates the advantage of directly ingesting data into TEE and bypassing the OS:
SBT{} outperforms the latter by up to 20\% in throughput due to reduction in moving ingested data.

\paragraph{Trusted primitive{} vectorization} (\S\ref{sec:opt})
Our optimizations with ARM vector instructions are crucial.
To show this, we examine \code{GroupBy}, one of the top hotspot operators.
When we replace the vectorized Sort that underpins \code{GroupBy} with two popular implementations (qsort() from the the OP-TEE's libc and std::sort() from the standard C++ library),
we measured the throughput of \code{GroupBy} drops by up to 7$\times$ and 2$\times$, respectively.
We have similar observation on other operators.

\begin{comment}
We replace the Sort with two popular implementations:
qsort() from the the OP-TEE's libc and
std::sort() from the standard C++ library.
When the input contains XXX key/value tuples \note{fix},
we measure that SBT{}'s \code{GroupBy} outperforms the versions using qsort and std::sort by up to 7$\times$ and 2$\times$, respectively.
The performance gap increases as the input size grows.
Given the central role of Sort in trusted primitive{}s, the vectorization contributes to the overall good performance significantly.
\end{comment}

\paragraph{Efficacy of hint-guided memory placement} (\S\ref{sec:mm:placement})
We compare to an alternative design:
the modified allocator acts based on the heuristics that all the uArray{}s produced by the same primitive{} belong to the same \textit{generation} and are likely to be reclaimed altogether.
Accordingly, the modified allocator places these uArray{}s in the same uGroup{}.
As shown in Figure~\ref{fig:hint}, in three benchmarks, the modified allocator increases memory usage by up to 35\%.
This is because, without hints, it cannot place uArray{}s based on future consumption.

\paragraph{uArray{} on-demand growth}
(\S\ref{sec:mm:abs})
We compare uArray to std::vector, a widely used C++ sequence container with on-demand growth.
We run a microbenchmark of N-way merge, an intensive procedure in trusted primitive{}s.
It iteratively merges 128 buffers (uArray{}s or vectors), each containing 512 KB (128K 32-bit random integers) until obtaining a monolithic buffer;
as merge proceeds, buffers grow dynamically.
As shown in Figure~\ref{fig:vector}, uArray{}s is 4$\times$ faster than std::vector,
because the allocation and paging in TEE that back uArray{} growth is much faster than that of a commodity OS.

\paragraph{Compression of audit records} (\S\ref{sec:attest})
The compression significantly saves the uplink bandwidth.
We test two benchmarks (WinSum and Power) on two extremes of the spectrum of computation cost, and test two very different input batch sizes.
This is because simpler computations and smaller batch sizes generate audit records at higher rates.
Figure~\ref{fig:attest-exp} shows that SBT{} compresses audit records by 5$\times$--6.7$\times$.
In an offline test using gzip to compress the same records, we find our compression ratios are 1.9$\times$ higher than gzip.
2--40 KB/sec of uplink bandwidth is saved, which is significant compared to the uploaded analytics results, which are 144 bytes/sec for WinSum and 400 bytes/sec for Power.

\section{\@startsection {section}{1}{\z@}%

\newcommand*\circled[1]{\tikz[baseline=(char.base)]{
		\node[shape=circle,fill=black,draw,text=white,inner sep=1pt] (char) {#1};}}

\newcommand{\Paragraph}[1]{\vskip 3pt\noindent\textbf{#1 }}
\newcommand\paratitle[1]{\textit{\textbf{#1}} \hspace{1mm}}

\renewcommand{\paragraph}[1]{\vskip 3pt\noindent\textbf{#1 }}

\newenvironment{smitemize}%
  {\begin{list}{$\bullet$}%
     {\setlength{\parsep}{0pt}%
      \setlength{\topsep}{0pt}%
      \setlength{\itemsep}{2pt}}}%
  {\end{list}}

\newcommand\note[1]{\sethlcolor{yellow} \hl{#1}}

\newcommand\noted[1]{}

\newcommand\ksm[1]{{\color{blue}{ksm: #1}}}
\newcommand\ksmD[1]{{\color{lightgray}{ksm: #1}}}

\newcommand\gena[1]{{\color{red}{gena: #1}}}
\newcommand\genaD[1]{{\color{lightgray}{gena: #1}}}

\newcommand\xzl[1]{\sethlcolor{Dandelion} \hl{xzl: #1}}

\newcommand\mj[1]{{\color{ForestGreen}{mj: #1}}}
\newcommand\mjD[1]{{\color{lightgray}{mj: #1}}}

\newcommand\hp[1]{{\color{blue}{#1}}}
\newcommand\hpsout[1]{{\color{red}\sout{hp: #1}}}
\newcommand\sz[1]{{\color{violet}{sz: #1}}}

\newcommand\sect[1]{Section~\ref{sec:#1}}

\newenvironment{myitemize}%
  {\begin{itemize}
	[leftmargin=0cm,
		itemindent=.3cm,
		labelwidth=\itemindent,
		labelsep=0pt,
		parsep=3pt,
		topsep=2pt,
		itemsep=1pt,
		align=left]
  }%
  {\end{itemize}}

\newenvironment{myenumerate}%
  {\begin{enumerate}
	[leftmargin=0cm,itemindent=.5cm,labelwidth=\itemindent,
		labelsep=0pt,
		parsep=1pt,
		topsep=1pt,
		itemsep=3pt,
		align=left]
  }%
  {\end{enumerate}}

\newenvironment{enumerateinline}%
  {\begin{enumerate*}
	[label=\roman*)]
  }%
  {\end{enumerate*}}

\newcommand\textbfit[1]{\textit{\textbf{#1}}}

\newcommand{\scenario}[1]{\texttt{#1}}

\newcommand{\state}[1]{\textsc{#1}}

\newcommand{\system}[1]{\textsf{#1}}

\newcommand{\code}[1]{\texttt{\small{#1}}}

\newcommand{\queue}[1]{\textit{#1}}

\input{terms}

\makeatletter
\def\@copyrightspace{\relax}
\makeatother

\section{Implementation}
\label{sec:impl}

We build SBT{} for ARMv8 and atop OP-TEE~\cite{optee} (v2.3).
SBT{} reuses most control functions of StreamBox~\cite{streambox}, an open-source research stream engine for x86 servers.
Yet, as StreamBox mismatches a TEE (\S\ref{sec:overview:challenges}), SBT{} contributes a new architecture and a new data plane.
\begin{comment}
SBT{}'s architecture and data plane are completely different from that of StreamBox;
Crucial to our design objectives,
SBT{}'s architecture and data plane are completely different from that of StreamBox;
the latter heavily depends on hash tables, trees, and a sophisticated memory allocator~\cite{jemalloc} in a variety of libraries~\cite{intel-tbb,folly,jemalloc}, hence mismatching TEE (\S\ref{sec:bkgnd:engine}).
\end{comment}
SBT{} communicates with source sensors and cloud consumers over ZeroMQ TCP transport~\cite{zmq} which is known for good performance.
The new implementation of SBT{} includes 12.4K SLoC.

\begin{comment}
\paragraph{TEE choice}
We built SBT{}'s data plane atop OP-TEE~\cite{optee} (v2.3), a popular TEE kernel for TrustZone{}.
In the TEE, the SBT{} code runs on the least privileged level (EL0), isolated from the TEE kernel on EL1.
SBT{} relies on OP-TEE for secure key storage.
We modify OP-TEE's exception handling to implement on-demand paging.
\end{comment}

\noindent
\textbf{Input batch size}, a key parameter of SBT{}, trades off between delays in executing individual primitive{}s, the rate of TEE entry/exit, and attestation cost.
We empirically determine it as 100K events and will evaluate its impact (\S\ref{sec:eval}).
\begin{comment}
\paragraph{Memory mapping granularity}
An ARMv8 CPU has three levels of page tables, corresponding to page sizes of 1GB, 2MB, and 4KB, respectively.
To save TEE physical pages needed for storing the page tables, we choose to map each uGroup{} with a dedicated, pre-allocated level-2 page table, giving each uGroup{} a virtual region of 1 GB.
As the uGroup{} grows, the page fault handler installs one level-2 entry at a time, appending 2MB to the uGroup{}.
Using smaller 4KB pages (i.e. installing a level-3 entry at a time) results in frequent page faults and hence 2--7$\times$ lower engine throughput.
\note{remove -- cut}
\end{comment}
\noindent
\textbf{Opaque references} for uArray{}s are 64-bit random integers generated by the data plane.
It keeps the mappings from references to uArray{} addresses in a table, and
validates opaque references by table lookup.
This incurs minor overhead, as live opaque references are often no more than a few thousands.

\begin{comment}
We have implemented SBT{} based on StreamBox~\cite{streambox}, an open-source stream processing engine designed for multicores.
Reusing much of StreamBox's control plane, SBT{} is able to create abundant parallelism in out-of-order stream processing, and elastically maps the parallelism to all the CPU cores.
Yet, StreamBox encapsulates pipeline data in standard C++ data structures in normal world{}, which contrasts to SBT{}'s key design.
As a result, for SBT{} we implement a new data plane, its interface to the control plane, and a new event type system.
The new addition includes 12K SLoC in total.

\paragraph{Trusted execution environment}
We built SBT{}'s data plane atop OP-TEE~\cite{optee}, a popular open-source tiny OS kernel that manages the secure world{} resources.
OP-TEE provides a lean, multiprogrammed environment, and its binary is as small as 260KB.
OP-TEE, together with its companion Linux driver and normal world utility, provide mechanisms for communication between normal world{} and secure world{}.
SBT{} relies on OP-TEE for secure key storage.
We have modified OP-TEE's exception handling in order to implement on-demand paging for uArray{}s.

\paragraph{Memory mapping}
Since the official release of OP-TEE only reserves 15 MB for the secure world{}, we increase the static memory reservation to 768 MB to accommodate data-intensive processing.
We do so by modifying the source code of UEFI bootloader.
The ARMv8 architecture we target can have up to three levels of page tables.
Each entry in level 1, level 2, and level 3 page tables covers a virtual address range of 1GB, 2MB, and 4KB, respectively.
To minimize the overhead in managing the page frames that back the page tables themselves, we choose to map each uGroup{} with a dedicated, pre-allocated level 2 page table, giving each uGroup{} a maximum size of 1GB.
When a uGroup{} is initialized, the data plane clears all the entries on the corresponding level 2 page table.
As the uGroup{} grows, the data plane's page fault handler maps memory to the end of uGroup{} at a granularity of 2MB (one level 2 entry).

We have also implemented more fine-grained on-demand paging by growing at 4KB (one level 3 entry), which requires to use level 3 page tables.
Since the level 3 page table themselves require substantial backing pages (4KB every 2MB virtual address range), we manage a global, dynamic pool of backing pages as a list.
Although finer-grained paging may reduce internal fragmentation, our experience show that it poorly fits data-intensive stream processing, as will be shown in Section~\ref{sec:eval}.
\end{comment}

\subsection{Why are existing systems inadequate?}
\paragraph{Why are existing systems inadequate?}
First,
many TEE-based systems~\cite{scone,graphene-sgx,haven} pull entire user applications
and libraries to the TCB, as shown in Figure~\ref{fig:div}(a).
However, as we described in \sect{bkgnd:engine}, a modern analytics engine and its libraries are large, complex, and potentially vulnerable.
Second,
partitioning applications to suit a TEE, as shown in Figure~\ref{fig:div}(b)~\cite{glamdring,panoply,rubinov16icse}, is unsuitable for existing stream engines: partitioning does not change their hash-based data structures and algorithms, which by design mismatch a TEE.
Similarly, recent secure processing engines disfavor partitioning~\cite{enclaveDB,safebricks}.
Third,
recent systems use TEE to protect data in analytics or in network packet processing.
As summarized in Table~\ref{tab:cmp},
they lack support for stream analytics, key computation optimizations, or specialized memory allocation, which we will demonstrate as vital to our objective.

Attesting TEE integrity~\cite{sgx-tor,enclaveDB} is insufficient to assert analytics correctness.
VC3~\cite{vc3} and Opaque~\cite{opaque} verify correctness of \textit{batch} analytics by checking the history of compute results, i.e. their data lineage~\cite{data-provenance,ariadne}.
Without tracking data being continuously ingested and lacking a stream model, data lineages cannot assert whether \textit{all} ingested data is processed according to pipeline declarations, watermarks, and temporal windows, which are critical to stream analytics.

\section{Introduction}
\label{sec:intro}

Many key applications of Internet of Things (IoT) process a large influx of sensor\footnote{Recognizing that IoT data sources range from small sensors to large equipment, we refer to them all as \textit{sensors} for brevity.} data, i.e. telemetry.
Smart grid aggregates power telemetry to detect supply/demand imbalance and power disturbances~\cite{smart-grid}, where a power sensor is reported to produce up to 140 million samples per day~\cite{distil, btrdb};
oil producers monitor pump pressure, tank status, and fluid temperatures to determine if wells work at ideal operating points~\cite{intel-oil, hortonworks}, where an oil rig is reported to produce 1--2 TB of data per day~\cite{cisco-oil};
manufacturers continuously monitor vibration and ultrasonic energy of industrial equipment for detecting equipment anomaly and predictive maintenance~\cite{oracle-predictive, worx}, where
a monitored machine is reported to generate PBs of data in a few days~\cite{dell-manufacturing}.

The large telemetry data streams must be processed in time.
The high cost and long delay in transmitting data necessitate edge processing~\cite{shi16iotj,satya-edge-iot}:
sensors send the data to nearby gateways dubbed ``cloud edge'';
the edge runs a pipeline of continuous computations to cleanse and summarize the  telemetry data and reports the results to cloud servers for deeper analysis.
Edge hardware is often optimized for cost and efficiency.
According to a 2018 survey~\cite{iot-survey}, modern ARM machines are typical choices for edge platforms.
Such a platform often has 2--8 CPU cores and several GB DRAM.

\begin{comment}
While IoT data promises high value, their security is a pressing concern~\cite{eu-iot-security,acm-iot-security, acm-iot-challenges,iot-survey}.
Specifically, users often demand data \textit{confidentiality}, i.e. data is only accessible to trusted parties; and data \textit{integrity}, i.e. data is only created and modified by trusted parties.
Despite the demands, IoT is known weak on security.
Deployed in the field, IoT devices (e.g. sensors) often lack professional supervision~\cite{mckinsey-iot,Wu:2017:ECE:3132465.3132475}, are weakly configured~\cite{symantec-iot-security,windriver-iot-security}, and see long delays in receiving software security updates~\cite{farmbeats,mckinsey-iot}.
\end{comment}

\input{fig-overview}

Unfortunately, edge processing exposes IoT data to high security threats.
i)
Deployed in the wild, the edge suffers from common IoT weaknesses,
 including lack of professional supervision~\cite{mckinsey-iot,Wu:2017:ECE:3132465.3132475}, weak configurations~\cite{symantec-iot-security,windriver-iot-security}, and long delays in receiving security updates~\cite{farmbeats,mckinsey-iot}.
ii)
On the edge, the IoT data flows through a set of sophisticated components that expose a wide attack surface.
These components include a commodity OS (e.g. Linux or Windows), a variety of user libraries, and a runtime framework called \textit{stream analytics engine{}}~\cite{msft-azure-edge,cisco-edge-fabric,dell-statistica}.
They reuse much code developed for servers and workstations.
Their exploitable misconfigurations \cite{misconfig-sosp11} and vulnerabilities~\cite{anatomy-java-exploits,chen2011linux,tan2014bug} are not uncommon.
iii) With data aggregated from multiple sources, the edge is a high-value target to adversaries.
For these reasons, edge is even more vulnerable than sensors, which run much simpler software with narrower attack surfaces.
Once attackers compromise the edge, they not only access confidential data but also may delete or fabricate data sent to the cloud, threatening the integrity of an entire IoT deployment.

\begin{comment}
On one hand, the edge faces existing threats to IoT security, including lack of professional supervision~\cite{mckinsey-iot,Wu:2017:ECE:3132465.3132475}, weak configurations~\cite{symantec-iot-security,windriver-iot-security}, and long delays in receiving security updates~\cite{farmbeats,mckinsey-iot}.
On the other hand, the edge's architecture and role further amplify these threats.
i) The edge exposes a much larger attack surface than smart things.
It processes data with a sophisticated software stack, which typically consists of a runtime framework called a \textit{stream analytics engine{}}~\cite{sensorbee,msft-azure-edge,cisco-edge-fabric,dell-statistica,sparkstreaming},
rich user libraries~\cite{intel-tbb,folly,jemalloc}, and a commodity OS.
Each of these components often consists of hundreds of thousands of SLoC,
for which misconfiguration \cite{misconfig-sosp11} and vulnerabilities are not uncommon~\cite{anatomy-java-exploits,Chen:2011:LKV:2103799.2103805}.
ii) For cost saving, edge processing jobs may co-run with untrusted programs.
iii)
As the edge aggregates data from many sources,
it incentivizes attackers.
Once attackers compromise the edge, they not only obtain confidential data from multiple sources (e.g. a smart farm's pest activities from all monitors) but also may delete or fabricate data sent to the cloud (e.g. silently dropping alarming pest events), threatening the integrity of entire IoT deployment.
\end{comment}

Towards secure stream analytics on an edge platform,
our goal is to safeguard IoT data confidentiality and integrity, support verifiable results, and ensure high throughput with low output delay.
Following the principle of least privilege~\cite{least-privilege},
we protect the analytics data and computations in a trusted execution environment{} (TEE) and limit their interface;
we leave out the remaining edge software stack which we deem untrusted.
By doing so, we shrink the trusted computing base (TCB) to only the protected  functionalities, the TEE, and the hardware. We hence significantly enhance data security.

We face three challenges:
i) what functionalities should be protected in TEE and behind what interfaces?
ii) how to execute stream analytics on a TEE's low TCB and limited physical memory while still delivering high throughput and low delay?
iii) as both trusted and untrusted edge components participate in stream analytics,
how to verify the outcome?

Existing solutions are inadequate:
pulling entire stream analytics engines to TEE~\cite{scone,graphene-sgx,haven}
 would result in a large TCB with a wide attack surface;
the systems securing distributed operators~\cite{vc3,opaque,securestreams}
often lack stream semantics or optimizations for efficient execution in a single TEE, which are crucial to the edge;
only attesting TEE integrity~\cite{sgx-tor} or data lineages~\cite{vc3,opaque,ariadne,data-provenance} is inadequate for verifying stream analytics.
We will show more evidences in the paper.

Our response is StreamBox-TZ{} (SBT{}), a secure engine for analyzing telemetry data streams.
As shown in Figure~\ref{fig:overview}, SBT{} builds on ARM TrustZone{}~\cite{arm-trustzone} on an edge platform.

SBT{} contributes the following notable designs:

\noindent
\textit{(1) Architecting a data plane for protection} \hspace{1mm}
SBT{} provides a data plane exposing narrow, shared-nothing interfaces to untrusted software.
SBT{}'s data plane encloses i) all the analytics data;
ii) a new library of low-level stream algorithms called \textit{trusted primitive{}s} as the only allowed computations on the data;
iii) key runtime functions, including memory management and cache-coherent parallel execution of trusted primitive{}s.
SBT{} leaves thread scheduling and synchronization out of TEE.

\noindent
\textit{(2) Optimizing data plane performance within a TEE} \hspace{1mm}
In contrast to many TEE-oblivious stream engines that operate numerous small objects, hash tables, and generic memory allocators~\cite{sparkstreaming,streambox,trill},
SBT{} embraces unconventional design decisions for its data plane.
i) SBT{} implements trusted primitive{}s with array-based algorithms and contributes new optimizations with handwritten ARMv8 vector instructions.
ii)
To process high-velocity data in TEE,
SBT{} provides a new abstraction called uArray{}s, which are contiguous, virtually unbounded buffers for encapsulating all the analytics data;
SBT{} backs uArray{}s with on-demand paging in TEE and manages uArray{}s with a specialized allocator.
The allocator leverages hints from untrusted software for compacting memory layout.
iii)
SBT{} exploits TrustZone{}'s lesser-explored hardware features:
ingesting data straightly through trusted IO without a detour through the untrusted OS;
avoiding relocating streaming data by leveraging the large virtual address space dedicated to a TEE.

\noindent
\textit{(3) Verifying edge analytics execution} \hspace{1mm}
SBT{} supports cloud verifiers to attest analytics \textit{correctness}, result \textit{freshness}, and the untrusted hints received during execution.
SBT{} captures coarse-grained dataflows and generates audit records.
A cloud verifier replays the audit records for attestation.
To minimize overhead in the edge-cloud uplink bandwidth,
SBT{} compresses the records with domain-specific encoding.

Our implementation of SBT{} supports a generic stream model~\cite{beam} with a broad arsenal of stream operators.
The TCB of SBT{} contains as little as 267.5~KB of executable code, of which SBT{} only constitutes 16\%.
On an octa core ARMv8 platform, SBT{} processes up to 12M events (144 MB) per second at sub-second output delays.
Its throughput on this platform is an order of magnitude higher than an SGX-based secure stream engine running on a small x86 cluster with richer hardware resources~\cite{securestreams}.
The security mechanisms contributed by SBT{} incur less than 25\% throughput loss with the same output delay;
decrypting ingress data, when needed, incurs 4\%--35\% throughput loss with the same output delay.
While sustaining high throughput, SBT{} uses up to 130 MB of physical memory in most benchmarks.

The key contributions of SBT{} are:
i) a stream engine architecture with strongly isolated data and a lean TCB;
ii) a data plane built from the ground up with computations and memory management optimized for a single TrustZone-based TEE;
iii) remote attestation for stream analytics on the edge with domain-specific compression of audit records.
To our knowledge,
SBT{} is the first system designed and optimized for data-intensive, parallel computations inside ARM TrustZone.
Beyond stream analytics, the SBT{} architecture should help secure other important analytics on the edge, e.g. machine learning inference.
The SBT{} source can be found at \code{http://xsel.rocks/p/streambox}.

\section{Secure Memory Management}
\section{TEE Memory Management}
\label{sec:mm}

\begin{comment}
\note{moved from design choice}
We devise contiguous, virtually unbounded arrays as the universal containers for all the streaming data and operator state in TEE.
To manage unbounded arrays, we build a specialized, lightweight allocator (\S\ref{sec:mm}).
These contrast to hash-based data structures managed by generic, sophisticated allocators in existing engines (Section~\ref{sec:bkgnd:engine}, \ref{item:mm}).
Our rationales are two.
First, serving frequent allocation requests with scalable performance requires sophisticated allocators~\cite{intel-tbb,jemalloc} that often adds tens of KSLoC to TCB.
Second, the hash table's rationale of trading space for time mismatches the limited capacity of secure memory, as mentioned in design choice (1).
\note{moved from choice}
\end{comment}

Facing high-velocity streams in a TEE,
SBT{}'s memory allocator addresses two challenges:
\textit{space efficiency}: it must create compact memory layout and reclaim memory timely due to limited physical memory;
\textit{lightweight}: the allocator must be simple to suit a low TCB.
The challenges disqualify popular engines that organize events in hash tables (e.g. for grouping events by key) and rely on generic memory allocators~\cite{sparkstreaming,streambox,sensorbee,trill,streamscope}.
The reasons are two: a hash table's principle of trading space for time mismatches TEE's limited memory;
generic allocators often feature sophisticated optimizations, adding tens of KSLoC to TCB ~\cite{intel-tbb,jemalloc}.

SBT{} specializes memory management for stream computations:
it supports unbounded buffers as the universal memory abstraction (\S\ref{sec:mm:ubuf});
it places data by using (untrusted) consumption hints and large virtual address space (\S\ref{sec:mm:placement}).

\subsection{Unbounded Array}
\label{sec:mm:abs}
\label{sec:mm:ubuf}

We devise contiguous, virtually unbounded arrays called \textit{uArray{}}s, a new abstraction as the universal data containers used by computations in TEE.
uArray{}s encapsulate all the data in a pipeline, including data flowing among trusted primitive{}s as well as operator states traditionally kept in hash tables.

An uArray{} is an append-only buffer in a contiguous memory region for same-type data objects.
Their lifecycles closely map to the producer/consumer pattern in streaming computations.
One uArray{} can be in three states.
\textit{Open}: after an uArray{} is created, it dynamically grows as the producer primitive{} appends data objects to it.
\textit{Produced}: the data production completes and the end position of the uArray{} is finalized. uArray{} becomes read-only and no data can be appended.
\textit{Retired}: the uArray{} is no longer needed and its memory is subject to reclamation.
The memory allocator places and reclaims uArray{}s regarding their states, as will be discussed in Section~\ref{sec:mm:placement}.

\paragraph{Types}
uArray{}s fall into different types depending on their scopes and enclosed data.
A \textit{streaming uArray{}} encapsulates data flowing from a producer primitive{} to a consumer primitive{}.
A \textit{state uArray{}} encapsulates operator state that outlives the lifespans of individual primitive{}s.
A \textit{temporary uArray{}} live within a trusted primitive{}'s scope.

\begin{comment}
\paragraph{Scope}
uArray{}s may be passed around among primitives.
They have different scopes depending on the enclosed data.
i) A \textit{streaming uArray{}} encapsulates data flowing from a producer primitive{} to a consumer primitive{}.
Its opaque reference (see Section~\ref{sec:impl} for details) is passed from the producer to the consumer.
ii) A \textit{state uArray{}} encapsulates operator state that outlives the lifespans of individual primitive{}s.
After being produced, the uArray{}'s reference is returned to the control plane, which keeps the uArray{} as part of a temporal window.
Upon the completion of the window, the control plane dispatches the state uArray{} for consumption and then for retirement.
iii) A \textit{temporary uArray{}} live within a trusted primitive{}'s scope. Its reference never escapes the primitive{}.
\end{comment}

\begin{comment}
\begin{myitemize}
\item
A \textit{streaming uArray{}} encapsulates data flowing from a producer primitive{} to a consumer primitive{}.
A opaque reference (see Section~\ref{sec:impl} for details) to this uArray{} is passed from the producer to the consumer by the control plane.

\item
A \textit{state uArray{}} encapsulates operator state that outlives the lifespans of individual primitive{}s.
After being produced, the uArray{}'s reference is returned to the control plane, which keeps the uArray{} as part of a temporal window.
Upon the completion of the window, the control plane dispatches the state uArray{} for consumption and then for retirement.

\item
A \textit{temporary uArray{}} live within a trusted primitive{}'s scope. Its reference never escapes the primitive{}.
\end{myitemize}
\end{comment}

\begin{comment}
\paragraph{Ownership}
The data plane keeps the notion of uArray{} ownership to prevent data race in concurrent uArray{} access.
Only the owner may modify the uArray{} and change the uArray{}'s lifecycle state.
i) the ownership of a streaming uArray{} transfers from the producer primitive{} to the consumer;
ii) the ownership of a state uArray{} transfers from the producer primitive{} to the control plane, which keeps the ownership until it closes the enclosing temporary window and retires the uArray{};
iii) a temporary uArray{} is always owned by the enclosing primitive{}.
\end{comment}

\begin{comment}
To prevent data race in concurrent uArray{} accesses, the data plane associates an uArray{} with its owner, the only entity that may append to the uArray{} and change the uArray{}'s lifecycle state.
The data plane determines uArray{} ownership as follows:
i) the ownership of a streaming uArray{} moves from the producer primitive{} to the consumer;
ii) the ownership of a state uArray{} moves from the producer primitive{} to the control plane, which keeps the ownership until it closes the enclosing temporary window and retires the uArray{};
iii) a temporary uArray{} is always owned by the enclosing primitive{}.
\note{improve}
\end{comment}

\paragraph{Low abstraction overhead}
An uArray{} spans a contiguous virtual memory region and grows transparently.
The growth is backed by the data plane's on-demand paging that completely happens in the TEE.
For most of the time, growing an uArray{} only requires updating an integer index.
Compared to manually managed buffers, this mechanism waives bounds checking of uArray{} in computation code and hence allows the compiler to generate more compact loops.
uArray{}s always grow in place.
This contrasts to common sequence containers (e.g. C++ \code{std::vector} and \code{java.util.ArrayList}) that grow transparently but require expensive relocation.
We will experimentally compare uArray{} with \code{std::vector} in Section~\ref{sec:eval}.

\subsection{Placing uArray{}s in uGroup{}s}
\label{sec:mm:placement}

\paragraph{Co-locating uArray{}s}
The memory allocator co-locates multiple uArray{}s as a uGroup{} in order to reclaim them consecutively.
Spanning a contiguous virtual memory region, a uGroup{} consists of multiple \textit{produced} or \textit{retired} uArray{}s and optionally an \textit{open} uArray{} at its end, as shown in Figure~\ref{fig:uarray}.
The grouping is purely physical:
it is at the discretion of the allocator, orthogonal to stream computations, and therefore transparent to the trusted primitive{}s and the control plane.

\input{fig-uarray}
With the grouping, the allocator reclaims \textit{consumed} uArray{}s by always starting from the beginning of an uGroup{}, as shown in Figure~\ref{fig:uarray}.
To place a new uArray{}, the allocator decides whether to create a new uGroup{} for the uArray{}, or append the uArray{} to an existing uGroup{}.
In doing so, the allocator seeks to
i) ensure that each uGroup{} holds a sequence of uArray{}s to be consumed consecutively in the future;
ii) minimize the total number of live uGroup{}s, in order to compact TEE memory layout and minimizes the cost in tracking uGroup{}s.
To this end, our key is to guide placement with the control plane's data consumption plan, as will be presented below.

\paragraph{Consumption hints}
Upon invoking a trusted primitive{} $T$, the control plane may provide two optional hints concerning
the future consumption order for the output of $T$:

\begin{myitemize}
\vspace{-1mm}
\item
\textit{Consumed-in-parallel} ($\parallel_k$): the control plane will schedule $k$ worker threads to consume a set of uArray{}s in parallel.
\vspace{-1mm}
\item
\textit{Consumed-after} ($b_1{\Leftarrow}b_2$): the control plane will schedule worker threads for consuming uArray{} $b_2$ after uArray{} $b_1$.
The \textit{consumed-after} relation is transitive.
uArray{}s may form multiple \textit{consumed-after} chains.
\vspace{-1mm}
\end{myitemize}

The control plane may specify these relations between new output uArray{}s (yet to be created) and existing uArray{}s.

\begin{comment}
Figure~\ref{fig:placement} shows an example.
The control plane invokes \code{Join} to produce a sliding window of two state uArray{}s, $w_1$ and $w_2$.
It indicates that $w_2$ will be consumed after $w_1$.
Later, it invokes \code{Join} over an incoming uArray{} $s$ and the sliding window.
\code{Join} outputs uArray{} $m$, which is dispatched to a downstream \code{Sort} that groups the results by key.
In invoking \code{Sort}, the control plane requests to produce four uArray{}s, $d_1..d_4$, as partially sorted results.
It indicates that $d_1..d_4$ will be consumed in parallel, and $d_1..d_4$ will be consumed after $m$.
\end{comment}

\paragraph{Hint-guided placement}
The hints assist the data plane to generate compact memory layout and reclaim memory effectively.
Upon allocating a uArray{}, the allocator examines the existing hints regarding to the uArray{}.

\noindent
($\Leftarrow$) prompts the allocator to place the uArray{}s on the same \textit{consumed-after} chain in the same uGroup{}.
Starting from the new uArray{} $b$ under question,
the allocator tracks back on its consumed-after chain, and places $b$ after the first uArray{} that is both in state \textit{produced} (i.e. its growth has finished) and is located at the end of an uGroup{}.
If no such uArray{} is available on the chain, the allocator creates a new uGroup{} for $b$.

\noindent
($\parallel_k$) prompts the allocator to place uArray{}s $b_{1..k}$ in separate uGroup{}s, so that delay in consuming any of the uArray{}s will not block the allocator from reclaiming the other uArray{}s.
Our rationale is that despite $b_{1..k}$ are created at the same time, they are often consumed at different moments in the future:
i) since SBT{}'s control plane threads independently fetch new uArray{}s for processing as they become available (\S\ref{sec:overview}),
the starting moments for processing $b_{1..k}$ may vary widely, especially when the engine load is high;
ii) even when $k$ worker threads start processing $b_{1..k}$ simultaneously, straggling workers are not uncommon, due to non-determinism of a modern multicore's thread scheduling and memory hierarchy~\cite{Aviram:2012:ESD:2160718.2160742}.

\paragraph{The impacts of misleading hints}
SBT{} detects misleading hints in retrospect through remote attestation (\S\ref{sec:attest}).
As the hints only affect TEE memory placement \textit{policy} on the edge,
misleading hints never result in data loss (\S\ref{sec:overview:nutshell}) or violation of data security and TEE integrity.
Yet, such hints may slow down analytics and therefore violate result freshness.

\begin{comment}
\paragraph{Will misleading hints compromise security?}

i) Such hints will be detected by remote attestation (\S\ref{sec:attest}).
ii) As the hints only affect TEE memory placement \textit{policy}, incorrect ones may lead to excessive TEE memory usage but do not compromise data security or TEE integrity, e.g. by introducing data races.
\end{comment}

\begin{comment}
In the example of Figure~\ref{fig:placement}, as \code{Join} creates $w_2$, the allocator places $w_2$ after $w_1$ in the same uGroup{}.
Similarly, when \code{Join} creates $m$ the allocator places $m$ right after $s$ in the uGroup{} of $s$.
Assuming \code{Sort} creates $d_1$ before $d_2..d_4$, the allocator further places $d_1$ right after $m$.
For $d_2..d_4$ which are created subsequently, based on $({\parallel} d_1..d_4)$, the allocator will create a new uGroup{} for each of them.
Later, $d_1$, $m$, and $s$ will be reclaimed consecutively, which happens independently of the reclamation of $d_{2..4}$.
\end{comment}

\paragraph{Managing virtual addresses}
All uGroup{}s grow \textit{in place} within one virtual address space.
To avoid collision and expensive relocation, the allocator places them far apart by leveraging the large virtual address space dedicated to a TrustZone{} TEE.
The space is 256TB on ARMv8, 10,000$\times$ larger than the physical DRAM (a few GBs).
Hence, the allocator simply reserves for each uGroup{} a virtual address range as large as the total TEE DRAM. We will validate this choice in \sect{eval}.

\begin{comment}
\subsection{Managing Memory Resources}
\label{sec:mm:resource}
\label{sec:mm:virt}
\paragraph{Virtual Address Space}
All uGroup{}s grow \textit{in place} within one virtual address space.
To avoid collision and expensive relocation, the allocator places them far apart by leveraging the large virtual address space dedicated to a TrustZone{} TEE.
The space is 256TB on ARMv8, 10,000$\times$ larger than the total physical DRAM which is often several GBs.
Hence, the allocator simply reserves for each uGroup{} a virtual address range as large as the total TEE DRAM. We will validate this choice in \sect{eval}.

\input{mm-phys}

\end{comment}

\section{Optimizing Secure task performance}

\section{Trusted Primitive{}s and Optimizations}
\label{sec:primitive}
\label{sec:opt}

\begin{comment}
\end{comment}

\paragraph{Parallel execution inside a TEE}
SBT{} exploits task parallelism without bloating the TEE with a threading library.
The control plane invokes multiple primitive{}s from multiple worker threads, which then enter the TEE to execute the primitive{}s in parallel.
All trusted primitive{}s share one cache-coherent memory address space in TEE, which simplifies data sharing and avoids copy cost.
This contrasts to existing secure analytics engines that leave task parallelism untapped in a single TEE~\cite{vc3,securestreams}.

\paragraph{Array-based algorithms to suit TEE}
Unlike many popular stream engines using hash-based algorithms for lower algorithmic complexity, we make a new design decision.
We strongly favor algorithms with simple logic and low memory overhead, despite that they may incur higher algorithmic complexity.
Corresponding to contiguous arrays as the universal data containers in TEE,
most primitive{}s use sequential-access algorithms over contiguous arrays, e.g. executing Merge-Sort over event arrays and scanning the resultant array to calculate the average value per key.

\paragraph{Trusted primitive{}s and vectorization}
SBT{}'s trusted primitive{}s are generic. They constitute most declarative stream operators, often referred to as Select-Projection-Join-GroupBy (SPJG) families, shown in Table~\ref{tab:operators}.
These operators are considered representative in prior research~\cite{mondrian}.

To speed up the array-based algorithms inside TEE without TCB bloat,
our insight is to map their internal data parallelism to vector instructions of ARM~\cite{arm-neon}.
Despite their well-known performance benefit, vector instructions are rarely used to accelerate data analytics \textit{within} TEEs, to our knowledge.
Vectorization incurs low code complexity as the performance gain comes from a CPU feature that is already part of the TCB.

Our optimization focuses on Sort and Merge, two core primitives that dominate the execution of stream analytics according to our observation.
Inspired by vectorized sort and merge on x86 ~\cite{sort-vs-hash-2009,sort-vs-hash-2013}, we build new implementations for SBT{} by hand-writing ARMv8 NEON vector instructions.
Our sort outperforms the ones in the C/C++ standard libraries by more than 2$\times$, as will be shown in evaluation.
This optimization is crucial to the overall engine performance.

\section{Related Work}
\label{sec:related}

\input{fig-attest-exp}

\paragraph{Secure data analytics}
DARKLY~\cite{DARKLY} protects sensor data by isolating computations in an OS process, resulting in a large TCB.
VC3~\cite{vc3} and SecureStreams~\cite{securestreams} use SGX to protect the operators in distributed analytics.
They lack optimizations for parallel execution in one TEE on the edge.
To process data confidentiality, STYX~\cite{styx} computes over encrypted data, a method likely prohibitively expensive to edge platforms.
Opaque~\cite{opaque} protects data access patterns of distributed operators, targeting a threat out of our scope.

\begin{comment}
Many systems support attestation of TEE integrity~\cite{sgx-tor}.
Data provenance~\cite{data-provenance,ariadne} provides full history of output data.
To verify analytics correctness, VC3~\cite{vc3} propagates work summaries among mappers/reducers;
Opaque~\cite{opaque} has each computation task check its input data lineage.
Lacking notions of stream watermarks and windows, they are insufficient to verify whether all ingested data is processed according to the stream model and pipeline.
Furthermore, unlike Opaque, SBT{}'s TEE remains agnostic to the executed pipeline for simplicity.
\end{comment}

\paragraph{TCB minimization}
Minimizing TCB is a proven approach towards a trustworthy system.
Flicker~\cite{Flicker} directly executes security-sensitive code on baremetal hardware.
Trustvisor~\cite{trustvisor} shrinks its TCB to a specialized hypervisor.
Sharing a similar goal, SBT{} addresses unique challenges in supporting data-intensive computation on a minimal TCB.

\paragraph{Trusted Execution Environments}
Much work isolates security-sensitive software components.
Terra~\cite{Terra} supports isolation with a virtual machine.
Many systems used TrustZone{} and SGX~\cite{intel-sgx} for TEE.
Some systems enclose in TEE whole applications~\cite{haven,scone,graphene-sgx,trustshadow},
while others partition existing programs for TEE~\cite{panoply,glamdring,rubinov16icse}.
These approaches often result in larger TCBs and/or higher overhead than SBT{} and are thus less desirable for SBT{}.
TEE also sees various novel usage, including protecting mobile app classes~\cite{tlr}, enforcing security policies~\cite{TZ-Regulating}, remote attestation of application control flows~\cite{c-flat}, and controlling data access~\cite{Graduated}.
None addresses data-intensive computation as SBT{} does.

\noindent \textbf{Edge processing} evolves from a vision~\cite{shi16iotj,satya-edge-iot} to practice~\cite{msft-azure-edge,cisco-edge-fabric,dell-statistica}.
Most works focused on programming paradigms~\cite{spanedge}, developing and deploying application~\cite{farmbeats,wearable-assistance,airbox}, and resource management~\cite{7774351}.
Complementary to them, SBT{} focuses on secure analytics on the edge.

\noindent \textbf{Stream processing systems}, in response to big data challenges, evolve from single-threaded~\cite{thies2002streamit,streambase,chandrasekaran2003telegraphcq,maier2005semantics,cranor2003gigascope} to massive parallel systems~\cite{sparkstreaming,timestream,naiad,dataflowAkidau2015,heron,timestream,streamscope}.
The existing systems focus on challenges, such as fault tolerance~\cite{sparkstreaming}, fast reconfiguration~\cite{drizzle}, high parallelism~\cite{trill,streambox}, and the use of GPUs~\cite{saber}.
Few systems achieve data security and performance simultaneously as SBT{} does.

\subsection{Security Benefits}
\input{fig-arch}
\input{fig-div}
\subsection{Approach and Security Benefits}
As shown in Figure~\ref{fig:arch},
SBT{} protects its data functions in a trusted \textit{data plane} in TEE.
SBT{} runs its untrusted \textit{control plane} in the normal world{}.
The control plane invokes the data plane through narrow, shared-nothing interfaces.
The engine's TCB thus only consists of the TEE (including the data plane) and the hardware.

Streaming data always flows in TEE.
The data plane ingests the data through TrustZone{}'s trusted IO.
After ingestion, it returns \textit{opaque references} of the data batches to the control plane.
In turn, the control plane requests computations on the protected data by invoking the data plane with the opaque references.
The data plane generates opaque references as long, random integers.
It tracks all live opaque references, validates incoming opaque references, and only accepts ones that exist.
At the pipeline egress, the data plane encrypts, signs, and sends the result to the cloud.

The analytics execution is continuously attested.
SBT{} captures complete and deterministic dataflows of the stream analytics as well as execution timing, and periodically reports to the cloud server.
The cloud server verifies if all ingested data is processed according to the pipeline (correctness), and if the edge incurs low delay (freshness).

\paragraph{Thwarted attacks}
SBT{} defeats the following attacks.
\textbfit{i) Breaking IoT data confidentiality or integrity.}
As the raw and derived data enters and leaves the edge TEE through trusted IOs,
adversaries on the edge cannot touch, drop, or inject data.
When the data is off the edge transmitted over untrusted networks,
it is protected by encryption against network-level adversaries.
ii) \textbfit{Breaking the data plane integrity.}
Any fabricated opaque reference passed to the data plane will be rejected, since all opaque references are validated before use.
Through the data plane's interface, an adversary may exploit bugs in the data plane and compromise it.
By minimizing the date plane codebase and hardening its interface, SBT{} substantially reduces the data plane's attack surface and potential bugs that can be exploited.
iii) \textbfit{Breaking analytics correctness.}
A compromised control plane may request computations
deviating from pipeline declarations or the stream model.
For instance, it may invoke trusted computations on partial data, wrong windows, or valid but undesirable opaque references.
SBT{} defeats these attacks through attestation: since the cloud verifier possesses complete knowledge on ingested data and pipelines, it detects such correctness violation and rejects the edge analytics results.
\textbfit{iv) Attacks on analytics performance or availability.}
A compromised control plane may delay or pause invoking of trusted computations, violating the freshness guarantee.
As the execution timing of trusted computations is attested, the cloud verifier detects the attacks and can choose to prompt further investigation.
\textbfit{v) Attempting to trigger data race or deadlock.}
By design, data race and deadlocks will never happen inside the data plane:
the trusted computations do not share state concurrently and all locking happens outside of the TEE.

\begin{comment}
i) Exploitation of TEE kernel bugs.
Although designed for security, TEE kernels still have bugs that may be exploited~\cite{vtz, CVE-2015-4421, CVE-2015-4422}. SBT{} does not strengthen TEE kernel security.
ii) Side channel attacks.
Adversaries out of TEE may still learn properties (e.g. data skew) of TEE-protected data by
observing hardware usage such as memory access pattern~\cite{armageddon}.
iii) Physical attacks, e.g. sniffing TEE's DRAM access~\cite{tampering,lowCostAttack}.
Note that many of these attacks are mitigated by prior work~\cite{sel4,opaque,sentry,TZ-CaSE} orthogonal to SBT{}.
\end{comment}

redpajama_set_name: RedPajamaArXiv