# Making Your Program Oblivious: a Comparative Study for Side-channel-safe
Confidential Computing

A K M Mubashwir Alam  Computer Science
Marquette University
Milwaukee, WI, USA
<EMAIL_ADDRESS>Keke Chen  Computer Science
Marquette University
Milwaukee, WI, USA
<EMAIL_ADDRESS>
###### Abstract

Trusted Execution Environments (TEEs) are gradually adopted by major cloud
providers, offering a practical option of _confidential computing_ for users
who don’t fully trust public clouds. TEEs use CPU-enabled hardware features to
eliminate direct breaches from compromised operating systems or hypervisors.
However, recent studies have shown that side-channel attacks are still
effective on TEEs. An appealing solution is to convert applications to be
_data oblivious_ to deter many side-channel attacks. While a few research
prototypes on TEEs have adopted specific data oblivious operations, the
general conversion approaches have never been thoroughly compared against and
tested on benchmark TEE applications. These limitations make it difficult for
researchers and practitioners to choose and adopt a suitable data oblivious
approach for their applications. To address these issues, we conduct a
comprehensive analysis of several representative conversion approaches and
implement benchmark TEE applications with them. We also perform an extensive
empirical study to provide insights into their performance and ease of use.

###### Index Terms:

Access-Pattern, TEE, SGX, Obliviousness, Side-Channel, Confidential Computing

##  I Introduction

Confidential computing enables users to enjoy public clouds without the need
to trust cloud providers’ security infrastructure. Researchers are actively
developing cryptographic approaches to secure processing in untrusted
platforms, such as Homomorphic Encryption [5] and Secure Multiparty
Computation (SMC) [20, 25]. While recent cryptographic methods, e.g., hybrid
protocols [26, 25, 39], are getting more efficient, pure software-based
solutions are still too expensive to be practical for complex computational
tasks or data-intensive applications [35].

More recently, Trusted Execution Environment (TEE) [13] emerges as a more
practical solution for confidential computing. TEE utilizes CPUs’ new hardware
features to securely isolate a user’s application from the cloud system.
Therefore, even if an entire system, including the operating system or
hypervisor, is compromised, the adversary cannot access the application. Major
CPU manufacturers have implemented the TEE concept in their recent CPUs, e.g.,
Intel SGX and AMD SEV. Correspondingly, TEE-enabled servers are increasingly
available in major public clouds, e.g., Azure provides SGX-enabled servers,
and Google adopts AMD SEV.

While TEE performs much more efficiently than software-based cryptographic
approaches, recent studies have also identified several side-channel attacks
[47, 40, 8, 44, 11]. Although the _TEE enclave_ cannot be directly breached,
side channels are still there – The enclave interacts with untrusted memories
and file systems, and the CPU cache is still shared among processes/virtual
machines owned by different users. Thus, attackers can utilize such controlled
channel attacks, e.g., manipulating page faults and page-table entries and
exploiting the flaws of modern CPU’s micro-architecture execution
optimization. Powerful attacks like Foreshadow [7] and Load Value Injection
[43] can combine memory/cache footprints and CPU speculative execution to
extract the secrets in TEE execution.

So far, countermeasures on side-channel attacks are limited to specific
applications [2, 28] or firmware fixes at the micro-architectural [43]. Among
the candidate solutions, data-oblivious algorithms and applications appear
attractive and promising. Regular programs’ data flow and execution paths vary
according to input data, i.e., a specific input value may trigger different
steps to execute. In contrast, data-oblivious algorithms’ data flow and
execution paths are invariant to the input. This data obliviousness property
can potentially help address many side-channel issues, as we will discuss in
Section II-B.

Nevertheless, it is challenging for users to develop an oblivious solution for
the following reasons. First, it’s unclear how complex to compose an oblivious
data program manually. Although recent TEE-related studies [29, 36, 12] have
indicated some oblivious primitives that one can use to compose an oblivious
solution, the complexity and the efforts to develop such a solution are
unclear. Second, automated approaches can help convert regular programs to
oblivious ones, but it’s unclear how practical they are for TEE applications.
Third, the quality of automatically generated oblivious solutions is also a
concern. Oblivious programs generally cost more than their non-oblivious
equivalent in terms of performance and memory. Low-quality conversion may also
result in a higher performance penalty. There is no systematic study to answer
these questions for TEE-based applications.

Contributions. We conduct a comprehensive analysis and empirical study to
compare several data oblivious solutions for TEE applications. The result will
help researchers and practitioners understand the benefits and limitations of
current solutions, possibly identify new research topics and assess the
strategies for adopting the side-channel-safe TEE solutions.

Specifically, we first analyze whether and how data obliviousness can address
side-channel attacks. Then, we summarize four representative solutions: the
manual composition approach, the compiler approach, the circuit approach, and
the application-framework approach and their characteristics in terms of
performance, ease of use, and maturity for application.

Finally, we develop an evaluation benchmark that includes basic oblivious
operations, compute-intensive tasks, and data-intensive tasks. Then, we apply
different oblivious program conversion approaches to the benchmark and
evaluate the resulting oblivious programs’ performance and ease of use. Our
study reveals the strengths and weaknesses of different oblivious solutions
and provides guidelines for selecting suitable techniques under different
scenarios.

In the remaining sections, we will first present the background knowledge for
our approach (Section II), then dive in the details of how data oblivious
solutions help to protect side-channels (Section III), then discuss different
oblivious approaches (Section IV), and, finally, perform the experimental
evalution (Section V) and conclusion (Section VI).

##  II Preliminaries

This section presents the necessary preliminaries for understanding the paper.
We will give the related background knowledge before analyzing oblivious
solutions. In the following, we will introduce the concept of Trusted
Execution Environments (TEE), the status of TEE development and deployment,
and the effect of side-channel attacks in TEEs.

###  II-A Trusted Execution Environment

Trusted Execution Environment (TEE) is a hardware-based solution for executing
code in a secure environment where powerful adversaries cannot access code or
data within this secure area. Using TEEs, a user can run their sensitive
computations in a TEE called Enclave, which uses a hardware-assisted mechanism
to preserve the privacy and integrity of enclave memory. With TEEs, users can
pass encrypted data into the Enclave, decrypt it, compute with plaintext data,
encrypt the result, and return it to the untrusted cloud components. TEEs
isolate private reserved memory for secure applications from other system
components, such as operating systems and hypervisors. When the operating
system or other system applications want to access the dedicated private
memory, the CPU restricts the access and redirects to some abort memory page.
Therefore, TEE applications can perform plaintext calculations without
compromising privacy and security.

However, without verifying the correctness of the cloud hardware and the user
binary, the remote user still cannot trust the TEE. The Remote Attestation
procedure establishes the trust between the TEE hardware and the user. Using
remote attestation, the user can verify if the cloud provider is using
certified TEE hardware and if the program running in an enclave is from a
digitally signed binary. During remote attestation, a secret key is generated
by Diffie-Hellman key exchange between the Enclave and the remote user to
establish a secure channel for the follow-up communication between the user
and the Enclave.

Major cloud platforms have provided different types of TEE-enabled servers.
Intel SGX is one of the popular TEE implementations. Since 2015, SGX has been
available in most Intel CPUs. Unlike Intel SGX, the other two major TEEs, such
as ARM TrustZone and AMD PSP, rely on secure hardware and a secure operating
system. As AMD integrated ARM TrustZone as an extension of CPU [17] and later
renamed it Platform Security Processor (PSP), the underlying technology of
both systems remains similar. While all TEE implementations feature complete
memory isolations from the system components and remote attestation to
establish trust, they still suffer from side-channel attacks.

###  II-B Side Channel Attacks on TEEs

Since the advent of TEEs, many studies have explored the weaknesses of TEE
side channels. While passive adversaries can exploit some attacks [10, 50, 34]
by only observing interactions between TEEs and other system components, the
assumption of TEEs enables more powerful attacks to be performed, some of
which can even retrieve plaintext information directly from the Enclave. Based
on the attack strategies, these attacks can be categorized as (i)
memory/cache-targeted attacks and (ii) microarchitecture-level attacks. In
memory/cache-targeted attacks, the attacker exploits the interactions between
TEEs and untrusted memory or applications and observes enclave memory page
loading and CPU cache usages. Microarchitecture-level attacks utilize modern
CPU features, such as CPU transient memory execution [7], to retrieve fine-
grained information from the low-level cache lines. We will discuss more
details in the next section.

##  III Data Oblivious Solutions for Side Channel Protection

###  III-A Threat Model

Users may run confidential computation tasks in an untrusted cloud server,
where the server’s OS or hypervisor can be compromised. The goal is to
preserve data and program’s integrity and confidentiality while availability
is out of concern. A typical TEE, such as Intel SGX, provides a hardware-
protected memory area, i.e., the _enclave_ [13], and guarantees the integrity
of the data and computation running inside the enclave. While adversaries
cannot directly access the enclave, they can still glean information via side
channels, such as memory access patterns and CPU caches. However, cache-based
attacks target all CPUs (regardless of having TEEs or not) and thus need
manufacturers’ micro-architecture level fixes. In contrast, the exposure of
memory access patterns is inevitable as enclaves have to interact with the
untrusted memory area. It’s also reasonable to assume that attackers cannot
access the cloud server physically, e.g., attaching a device to the server or
touching the motherboard, which excludes all attacks based on physical
accesses. Figure 1 illustrates the threat model.

Figure 1: TEE, side channels, and the threat model.

###  III-B Data Obliviousness

Definition. The execution path and data flow of a (data) oblivious program do
not change with different input data and parameter settings. When all the
steps of an algorithm or mechanism do not depend on input data, one cannot
determine the nature of the data by observing the steps of that algorithm.
Thus, oblivious solutions can effectively protect from attacks depending on
data-dependent access patterns.

Oblivious Primitives.  The goal of developing data oblivious programs is to
eliminate any data-dependent operations. We list the primitives that data
oblivious programs heavily depend on.

  * •

Address-based Access. This operation includes array element access or data
block access. Exposing the position of accessed data is the fundamental access
pattern. A naive solution is to iterate over the whole data structure to hide
the actual accessed position. In contrast, Oblivious RAM (ORAM) [18] has been
a well-accepted primitive for more efficiently hiding accessed addresses. It
can effectively reduce the cost of oblivious access to $O(\log N)$ for a
structure of $N$ data items. ORAM has been used in a few TEE-based solutions
to hide access patterns.

  * •

Data-dependent Branching. Most programs contain data-dependent branching
statements. Depending on the different inputs, a program execution may choose
different paths, resulting in distinct access patterns. The following code
snippet shows how an attacker can utilize the branching access pattern.

⬇

if (a >= b){

// swap a and b, and

// the page access can be observed.

}else{

// no page access.

}

The common method uses the CPU’s conditional move (CMOV) instructions to
eliminate the branching statements. A simplified example is shown as follows:

⬇

//if (a < b) x = a else x = b

CMOVL x, a

CMOVGE x, b

A few studies [30, 33, 3] have used CMOV instructions to provide code-level
obliviousness for branching statements. Without specific conditional jumps,
CMOV instructions move the source operand to the destination when a
conditional flag is set. However, regardless the flag is set or not, it reads
the source operand. Therefore, the access to the source operand cannot be used
to infer whether the source is copied to the destination or not. Ohrimenko et
al. [30] also designed library functions _omove_ and _ogreater_ to wrap up the
CMOV instructions for conveniently converting the branching statements.
Notably, a completely oblivious branching execution needs to run both branches
and select the desired result with the above method, which often leads to very
high costs.

  * •

Circuit. Circuits are considered a natural way to hide access patterns, as the
circuit execution activates the gates in a certain order regardless of the
input values [19]. The branching statement is readily implemented with a
bitwise multiplexer. However, oblivious memory access imposes significant
challenges. Many solutions implement linear scan so far [41, 32, 9], which
incurs very high costs.

  * •

Oblivious algorithms. Task-specific oblivious algorithms are methods
specifically designed to work with a specific task or a data structure. They
work more efficiently than solutions composed of general primitives such as
ORAM. For example, MergeSort can be converted to be oblivious by simply
replacing every memory interaction of the merge phase with ORAM and unwinding
data-dependent loops with fixed iteration loops. However, this direct
conversion can be much more expensive than a specially designed oblivious
sorting algorithm, such as BitonicSort [4]. Similarly, frequently used data-
intensive operations, such as _join_ and _group by_ , can have more efficient
dedicated oblivious versions.

###  III-C Can Data Obliviousness Address TEE Side-channel Attacks?

Against Memory Targeted Attacks. Memory-targeted attacks glean and utilize
access patterns within the system memory. TEE applications store data in an
encrypted form outside the TEE. When encrypted messages are accessed from
memory, i.e., between TEE and untrusted memory and even within TEE, an
adversary who controls the operating system can observe the data access
patterns and possibly extract sensitive information by manipulating page-fault
interrupts [10, 40]. Page-table entries [8]. For distributed data-intensive
applications, Ohrimenko et al. [34] also demonstrated how sensitive
information, such as age group, birthplace, and marital status, can be
extracted from MapReduce programs by only observing the network flow and
memory skew.

These attacks all depend on the differential access patterns observed via the
side channels. For example, an important step in KMeans clustering is to find
the nearest centroid and update the temporal cluster information for each
training data. A straightforward way of accessing cluster information creates
data-dependent branching based on cluster ids. If each cluster object resides
in separate memory pages, an attacker can exploit cluster id-dependent
branches by observing memory page access patterns. Thus, the adversary can
estimate the cluster size, which may be sensitive to the user. However, a
simplified oblivious version of this step hides the secret dependent branch by
accessing each cluster object with a CMOV operation. Thus, the attacker cannot
distinguish which cluster-id is being updated for the training data.

Against Cache Attacks. Cache-based side-channel attacks [27] had been long
exploited before TEE became popular. The basic mechanism of cache attacks
remains the same for systems with or without TEE. The main idea of the cache
attack is to load the system memory into the CPU cache and perform a time
analysis by loading different byte values to retrieve the value of the
previously loaded memory, such as _Prime+Probe_ [24] and _Flush+Reload_ [48]
methods.

Like regular applications, TEE is also vulnerable to cache-based side-channel
attacks. Since the last level cache (LLC) is a shared resource, an attacker
can exploit fine-grained information at a specific stage of the program by
probing the data access time in each cache line. However, in a data-oblivious
algorithm, all the steps and data accesses are fixed. Thus, an attacker cannot
distinguish the secret value and dummy access from the cache-level timing at a
given time. For example, a cache attack cannot distinguish the secret-
dependent block IDs or block data from dummy ones if accessed through
oblivious RAM [36, 2].

Against Micro-architectural Attacks. Some powerful attacks exploit the CPU’s
micro-architecture to retrieve secrets from TEE applications. Foreshadow [7]
exploits meltdown-type [22] attacks on TEE applications. Load Value Injection
(LVI) [43] is the most recent attack on Intel SGX that successfully retrieves
the secrets from the victim’s Enclave within the victim’s address space. The
CPU’s micro-architectural buffer must be prepared with some attacker-
controlled secret value to perform the LVI attack. These attacks are powerful
enough to extract plain text information from the TEE without physical access.
Manufacturers have issued microarchitectural-level firmware patches for some
[43, 7] of these attacks.

However, not all micro-architectural attacks can be prevented from firmware-
level patches. Some micro-architectural-level attacks still utilize access
patterns. For example, Bulck et al. [45] show that, by exploiting the timing
of micro-architectural instructions, attackers can observe secret-dependent
branches at the CPU instruction level. This type of micro-architectural-level
attacks cannot succeed if the application developer hides the data-dependent
branches with oblivious solutions. Therefore, oblivious programs can still
help mitigate these attacks.

##  IV Making Your Program Oblivious

While the fundamentals of data-oblivious operations are clear, developing a
practical solution is challenging for several reasons. First, it requires the
developer to have basic knowledge of every data-dependent part of their
programs and the risk of leaking a particular access pattern. Second,
converting the program to an oblivious one can be complex and error-prone. We
investigate the existing candidate approaches and summarize the following four
most representative ones for developing oblivious solutions: (i) manual
composition (or manual approach), (ii) compiler approach, (iii) circuit
approach, and (iv) framework approach.

###  IV-A Manual Composition

In manual composition, developers need to learn all the knowledge of sensitive
access patterns and the methods of converting them to be oblivious. These
approaches may vary depending on the applications’ related access pattern
problems. The key challenges of this approach are to manually analyze the
access pattern problem for every line of the code and replace the vulnerable
parts with their oblivious alternatives. Developers may also need to
experiment with different oblivious primitives to determine the most efficient
one. It’s also necessary to verify whether the conversion is complete with a
tool such as ObliCheck [42].

Several problem-specific manual compositions have been reported to address the
access-pattern based attacks on TEE applications. To protect the random access
over block data in untrusted memory, the developer can implement Oblivious RAM
that works with TEE, e.g., ZeroTrace [36, 2], that hides which block is read
or written by shuffling memory blocks during each access. Other problem-
specific algorithms have also been used to hide access patterns of specific
tasks, such as Oblivious Sorting [4], Oblivious Filter [50], Oblivious Join
[21], etc. CMOV-based oblivious branching is also actively applied in
developing specific machine algorithms [29] and addressing the in-enclave
access patterns [36, 3], with wrapped functions such as oblivious move,
greater, swap, etc.

Manually applying oblivious solutions enables the designing of both memory and
performance-efficient application. However, manually analyzing sensitive data
access and code vulnerabilities and applying oblivious solution is time-
consuming, domain-expertise demanding, and sometimes error prone. Developers
may utilize existing oblivious libraries [12] to reduce manual efforts.

###  IV-B Compiler Approach

Compiler techniques (e.g., static code analysis) can be used to minimize
manual efforts. The current compiler approaches for generating oblivious code
follow two directions: automate the manual composition approach, and hide code
and data access patterns via randomization.

The first category of approaches includes Raccoon[33] and Ghostrider [23] for
automating the manual process. They utilize static code analysis to detect
vulnerabilities, i.e., the primitive operations that need to be obfuscated,
and then apply suitable oblivious measures, as we have discussed in the manual
approach. They also use a few methods to optimize performance. For example,
they often provide an option to allow developers to annotate the parts to be
obfuscated; based on the array size, the compiler can decide to use linear
scan or ORAM to hide the accessed element.

Another compiler approach is to randomize access patterns and program
execution paths [31, 1, 6] by using primitives like ORAMs. For example,
Obfuscuro [1] divides the memory and code pages into two classes and achieves
obliviousness via ORAM. Similarly, Dr. SGX [6] and CoSMIX [31] also use data
randomization techniques to achieve fully automated memory obfuscation. The
non-deterministic run-time access patterns successfully hinder the adversary
from extracting any information.

These approaches are mostly experimental, not fully achieving the design goal
yet. First, while the compiler approach avoids most manual efforts, it may not
generate the most efficient oblivious solution. In particular, the
randomization approach often results in significantly high costs. Second,
since the compilers depend on static analysis to identify the sensitive code
blocks, they may apply unnecessary obfuscation due to a lack of context
awareness and the limitation of static analysis tools. Son et al.[42] showed
how static analysis-based methods failed to recognize standard oblivious
algorithms and were marked as non-oblivious, leading to unnecessary
obfuscation in the mitigation phase.

The ultimate goal of the compiler approach is to entirely free developers from
complex and expensive manual efforts, which is appealing. Unfortunately,
existing compilers have not reached the goal yet. In fact, we could not find a
stable open-source implementation for any of the mentioned approaches.
Nevertheless, we still believe this is a promising direction.

###  IV-C Circuit Approach

In many cryptographic approaches [20, 25], circuits have been used as a
building block for secure evaluation. Boolean circuits are naturally oblivious
as they execute all the paths [41, 32]. Since automated program-to-circuit
conversion tools have been built for the cryptographic approaches, such as
ObliVM [23], CircC [32], and HyCC [9], we wonder whether this approach can
also be a candidate for TEE-based applications.

Cryptographic circuit compilers ensure many things, including variable
mutations, conditional branching, loops, loops with breaks, early returns, and
random array access, are oblivious. We briefly describe some of the key
features:

  * •

Variable Mutations. In a regular program, the value of a variable can be
updated; however, in Boolean circuits, values are mutation free. When required
to update a variable, it uses versions of the variable. For example, if the
previous value of x was zero and then assigned to ten, it will be converted to
$x_{0}=0$, $x_{1}=10$.

  * •

Branching. To protect the branching attack, researchers implement guarded
execution, executing both branches and selecting the result based on
condition.

  * •

Loops. In circuits, each gate is executed only once. Thus, circuits do not
have any loops. Compilers unroll the loops to linear execution for bounded
iterations. If you do not provide a bound, it will unroll the loop up to the
size of data types. For example, a byte-type loop variable will unroll for 256
iterations.

  * •

Loops with breaks. Loops with breaks are common in programming. While older
compilers do not support break statements, modern compilers support
break/continue commands. In short, compilers use a similar approach that
resolves conditional branching. Expressly, compilers turn the loop into a
breakable block. When there is a breakable block, it will execute all
iterations, except it will use guarded execution to hide which value will be
chosen last.

  * •

Random Array access. That array access depends on the input. It requires O(n)
operations. Since the value is not constant, array access is implemented using
an n-sized multiplexer with the index as the multiplexer selector.

Cryptographic circuit compilers such as CircC [32] and HyCC [9] can convert
regular C programs to executable C circuit programs. However, very few TEE-
related studies [38, 16] have applied circuits as an access pattern protection
mechanism. We show in experiments that the performance can be a significant
concern due to three reasons (1) the extensive uses of the above methods to
ensure obliviousness; (2) the size of the generated circuit is large,
proportional to the input data size; (3) executing a circuit in a software
mode is inherently slow.

###  IV-D Framework Approach

For TEE-based data-intensive applications, the framework approach can be a
valid candidate [37, 29, 15, 50, 3]. We refer “framework” here to the well-
known big data processing frameworks, such as MapReduce [14] and Spark [49].
We have witnessed two types of framework approaches.

The first type aims to extend the big data frameworks to take advantage of
TEEs, which will have to handle side-channel attacks, as well. VC3 [37]
applied this strategy for modifying the Hadoop [46] system. M2R [15] targets
the problem of access-pattern leakage in the shuffling phase of VC3 and
proposes to use the oblivious schemes for shuffling. Another significant work,
Opaque [50], tries to revise Spark for SGX. They focus on the data access
patterns between computing nodes, illustrate how adversaries can use these to
infer sensitive information in the encrypted data and design data-oblivious
methods to address these attacks. These frameworks have a shared weakness:
only a few data processing components of the framework were moved to the TEE,
leaving most parts of the framework in untrusted areas under serious threats.
However, re-implementing the frameworks with the data obliviousness guarantee
is too expensive to be practical.

The second type of framework approach utilizes a data-intensive framework to
simplify the development of data oblivious solutions. Specifically, the
framework serves as the middleware to hide the complexity of data-oblivious
processing. The developer only needs to spend much less effort implementing
data-oblivious TEE applications. SGX-MR [3] utilizes the MapReduce processing
model to regulate application dataflow so that the framework can integrate the
application-independent data-oblivious protection mechanisms in the framework
code to protect any data mining algorithms that can be cast to the MapReduce
framework. Developers only need to handle a much smaller number of and often
simpler access patterns in the application-specific map and reduce functions.

This framework approach has a few unique benefits: (1) It significantly
reduces the complexity of the manual approach for data-intensive processing;
(2) It can integrate both the latest big-data processing techniques and data-
oblivious solutions at the framework level, which is transparent to
developers; (3) It can incorporate data-intensive optimization techniques in
the framework implementation, e.g., most block-based operations. Thus it can
be more efficient than directly applying fully automated compiler or circuit
approaches that are unaware of data-intensive features.

We use Table I to summarize the four approaches qualitatively in terms of ease
of use, performance, and unique features. In experiments, we will see more
quantitative results.

TABLE I: Summary of existing data oblivious solutions.  Method | Easy use | Performance | Other features
---|---|---|---
Manual | Low | High | Require expertise,
|  |  | time consuming
Compiler | High | Mid | May incur unnecessary
|  |  | obfuscation
Circuit | Mid | Low | compilation very slow,
|  |  | circuit size greater than data
F/W | High | High | only domain specific
|  |  | functionalities

##  V Experimental Evaluations

The experimental evaluation has the following goals.

  * •

Observe how different conversion approaches perform on the primitive
operations, which are the building blocks of an oblivious program. These
operations include (i) oblivious data access, (ii) oblivious branching, and
(iii) basic oblivious algorithms, such as sorting. The primitive operations
will be discussed under compute-intensive and data-intensive workloads.

  * •

Understand how the oblivious programs generated with different approaches
perform. We evaluate the performance with compute-intensive and data-intensive
benchmark applications.

  * •

Investigate the ease of use, i.e., the developers’ efforts, via multiple
measures, e.g., the line of code (LOC), the number of sensitive code blocks
susceptible to access pattern leakages, and LOC overhead to achieve mitigation
techniques.

###  V-A Experiment Setup

The experiments were conducted on a Linux machine with an Intel(R) Core(TM)
i7-8700K CPU of a 3.70GHz processor and 16 GB of DRAM. The TEE environment is
Intel SGX v1.0, and the Linux version is Ubuntu 22.04.

Approach Implementation. The _unprotected_ approach is the simple
implementation without considering obliviousness. The _manual_ composition
approach has used the following primitive operations: linear scan and ORAM for
random array accesses, the omove/ogreater functions [29, 36, 3] for oblivious
branching, and BitonicSort for sorting, to convert the implementation. We used
ZeroTrace’s open-source implementation for ORAM on SGX, and the HyCC circuit
generator [9] to convert a plain implementation to a circuit for the circuit-
based evaluation. For data-intensive applications, we adopted the SGX-MR
framework in the evaluation. Unfortunately, we could not find a working open-
source implementation for the published compiler approaches. Due to the sheer
complexity of implementing such a compiler, we have not included the compiler
approach in the evaluation.

  * •

_Oblivious Operations._ We evaluate the three basic oblivious operations:
random array access (block access in data-intensive workloads), branching, and
sorting. This evaluation should help understand the performance of each
approach at low-level operations.

  * •

_Sample Applications._ In addition to the basic oblivious operations, we also
include four applications for compute-intensive and data-intensive workloads,
two for each category respectively. Each application will be a certain blend
of primitive oblivious operations. (1) The compute-intensive applications
include the Edit Distance computation for varying lengths of strings, which
has a complexity of $O(N^{2})$ for the string length $N$, and the All-Pair
Shortest Path algorithm, Floyd-Warshall, with a complexity of $O(N^{3})$ for
$N$ nodes in the graph. (2) The data-intensive applications include the
WordCount and KMeans clustering algorithms.

In the following, we will organize the results in terms of compute-intensive
and data-intensive workloads. The primitive operations are discussed under
each category correspondingly.

###  V-B Results for Compute-Intensive Workloads

Compute-intensive workloads use a relatively small dataset that can be fit
into the TEE memory. We choose three basic operations and then two well-known
applications to evaluate the performance of different oblivious methods.

Random Array Access. Accessing array elements is one of the basic operations
of most applications. Figure 2(a) shows the execution time of various
oblivious implementation methods. First, the expenses of all oblivious
solutions are significantly higher than the unprotected version. ORAM shows
performance advantages over linear scans for larger sizes. For smaller sizes,
ORAM’s maintenance cost becomes relatively high, resulting in higher overall
costs than linear scans. The circuit version of array access also uses linear
scans. However, executing a circuit at the software level is clearly very
inefficient regardless of the array size.

$10^{1}$$10^{2}$$10^{3}$$10^{4}$$10^{5}$$10^{-3}$$10^{-2}$$10^{-1}$$10^{0}$$10^{1}$$10^{2}$$10^{3}$$10^{4}$$10^{5}$Number of recordsExecution time (ms)UnprotectedManual-Linear ScanManual-ORAMCircuit (a) Oblivious array access. Record size 8 bytes. |  UnprotectedManualCircuit$10^{-2}$$10^{-1}$$10^{0}$$10^{1}$$10^{2}$Execution Time (ms) (b) Oblivious branching. |  $2^{4}$$2^{5}$$2^{6}$$2^{7}$$2^{8}$$10^{-2}$$10^{-1}$$10^{0}$$10^{1}$$10^{2}$$10^{3}$$10^{4}$$10^{5}$$10^{6}$Number of recordsExecution time (ms)CircuitManualUnprotected (c) Oblivious sorting. Record size 8 bytes.
---|---|---

Figure 2: Performance evaluation of in-memory core operations.

Branching. We design a benchmark program to evaluate the impact of oblivious
branching. In a loop, a branching statement decides to execute one of the two
functions: one with a low cost and the other with a high cost. We repeated the
experiments a few times. Naturally, the unprotected version’s performance
varies over different runs. Figure 2(b) shows that the manual approach, which
uses CMOV instructions, is relatively efficient. However, the circuit approach
shows multiple orders of magnitude higher costs.

Sorting. The manual approach adopts BitonicSort. Since the circuit approach
can convert any algorithm to its oblivious version, we have considered
different sorting algorithms for the circuit approach. It turns out
BitonicSort is also the most efficient one in circuit form. Figure 2(c) shows
the manual approach is much faster than the circuit approach on BitonicSort.

Edit Distance. Edit distance uses dynamic programming to compute the distance
between two sequences, whose complexity is $O(N^{2})$ for sequences of length
$N$. It’s a typical high-complexity algorithm working with a relatively small
amount of memory. In Figure 3(a), we notice that the manual method is close to
the unprotected version, but again the circuit approach is much more expensive
than others.

$10$$20$$40$$60$$80$$100$$10^{-1}$$10^{0}$$10^{1}$$10^{2}$$10^{3}$$10^{4}$$10^{5}$$10^{6}$Sequence lengthsExecution time (ms)UnprotectedManualCircuit (a) Edit distance. |  $0$$50$$100$$200$$300$$400$$10^{-2}$$10^{-1}$$10^{0}$$10^{1}$$10^{2}$$10^{3}$$10^{4}$Number of NodesExecution time (ms)UnprotectedManualCircuit (b) Floyd-Warshall all-pair shortest path.
---|---

Figure 3: Performance evaluation of compute-intensive applications.

All-pair shortest path. The all-pair shortest path Floyd-Warshall algorithm is
expensive with a complexity of $O(N^{3})$ for $N$ nodes. Figure 3(b) shows the
manual approach is significantly slower than the unprotected one, but at a
manageable scale. In contrast, the circuit approach is too expensive to handle
larger $N$.

###  V-C Results for Data-intensive Workloads

For data-intensive workloads, we evaluate two basic operations: block-level
random access and block-based external sorting. In application-based
evaluations, we also include the framework approach: SGX-MR.

Random block access. Similar to the evaluation on array access, we include
linear scan and ORAM methods for the manual approach. Figure 4(a) clearly
shows the manual-ORAM approach performs much better. However, due to the large
data size, the gap between oblivious approaches and the unprotected is also
large.

$3{,}000$$9{,}000$$15{,}000$$21{,}000$$10^{7}$$10^{6}$$10^{5}$$10^{4}$$10^{3}$$10^{2}$$10^{1}$$10^{0}$$10^{-1}$$10^{-2}$$10^{-3}$Number of blocksExecution time (ms)CircuitManual-Linear ScanManual-ORAMUnprotected (a) Comparing random Access over blocks. Block size 1KB. |  $250$$500$$1{,}000$$1{,}500$$2{,}000$$10^{0}$$10^{1}$$10^{2}$$10^{3}$$10^{4}$$10^{5}$Number of blocksExecution time (s)CircuitManualUnprotected (b) Block-based oblivious sorting. Block size 1KB with 75 words (records) per block.
---|---

Figure 4: Performance evaluation of core operations for data-intensive
applications.

Block-based External Sorting. Next, we implement block-level sorting to
understand the sorting cost in block-level operations. We used 1-KB blocks
filled with string data. The manual approach adopts a block-level BitonicSort
algorithm with oblivious in-block operations [3], while the circuit approach
converts the block-level BitonicSort algorithm. In Figure 4(b), we observe
that the circuit approach is still orders of magnitude higher than the manual
approach, while the manual approach is about ten times slower than the
unprotected one.

WordCount. For application-level evaluation, we take a fixed amount of input,
500 1KB blocks, each of which is filled with random text. As the MapReduce-
based solution is the most efficient one for the WordCount problem, the manual
approach essentially duplicates the processing encoded in the framework of
SGX-MR, which uses BitonicSort for the intermediate sorting of word-count
pairs. As a result, the manual approach has an almost identical cost to the
SGX-MR approach. Certainly, SGX-MR significantly simplifies the developer’s
coding efforts. Again, the circuit approach is too expensive to be a practical
solution.

ManualSGX-MRCircuit$10^{1}$$10^{2}$$10^{3}$$10^{4}$Execution Time (s) (a) Application-level perfromance for Wordcount. Number of blocks 500 with 75 words/block. |  ManualSGX-MRCircuit$10^{0}$$10^{1}$$10^{2}$$10^{3}$$10^{4}$$10^{5}$Execution Time (s) (b) Application-level performance for KMeans. 4000 1KB-Blocks with eight bytes per record, and five clusters.
---|---
Figure 5: Performance evaluation of data-intensive applications.

KMeans. We use 4000 1k data blocks consisting of $34\times 10^{4}$ records and
five clusters. Due to the small number of clusters, we use hash and ORAM for
aggregation (check Appendix A), which appears more efficient than sorting-
based aggregation in SGX-MR. Figure 5(b) shows this manual approach performs
best among the candidate techniques.

###  V-D Developers’ effort to achieve data oblivious solutions

We are also curious about how easy a developer can use each of these
approaches. This evaluation does not include the extra time learning the
different approaches – apparently, developers need to take a significant
amount of time to learn the manual approach and the framework approach.

Instead, we look at the result of developing the evaluated applications to
understand the difficulty levels of using different approaches. We also assume
developers will use a library of oblivious primitives, e.g., ORAM, oblivious
branching, and oblivious sorting. The use of library will also significantly
reduce the line of code (LOC) for the manual and framework approaches.

TABLE II: Summary of developers’ effort to implement the oblivious solutions. The table represents the total line of code as LOC and the number of access-pattern sensitive segment in the code as AP. LOC-overhead means the lines used to achieve data obliviousness. Application | Manual | Circuit | Framework
---|---|---|---
| LOC | LOC-Overhead | AP | LOC | LOC-Overhead | AP | LOC | LOC-Overhead | AP
Edit Distance | 58 | 28 | 4 | 48 | 0 | - | - | - | -
All-Pair Shortest Path | 47 | 15 | 1 | 36 | 0 | - | - | - | -
Word Count | 277 | 21 | 6 | 155 | 0 | - | 22 | 0 | 0
KMeans | 330 | 24 | 4 | 263 | 0 | - | 58 | 6 | 1

Table II summarizes the additional effort a developer need to achieve data
oblivious applications. In the following we will discuss the compared data
oblivious strategies.

  * •

Manual Composition. Manual composition requires domain knowledge on TEE side
channels. The table shows the manual approach requires identifying one to six
sensitive code segments and hiding the access pattern with data-oblivious
alternatives. This approach requires the developer to write more lines of code
than other approaches, even when the oblivious library is used.

  * •

Circuit. The circuit approach is fully automated, and the developer does not
need to do any additional work.

  * •

Framework. With a framework like SGX-MR, the developer only focuses on small
pieces of application-specific code, such as the map and reduce functions,
dramatically reducing the developer’s burden compared to the manual approach.
The framework software contains fully optimized oblivious code that is
transparent to developers and shared by all SGX-MR applications. Table II
shows by using SGX-MR for framework-level protection, the developer does not
require any LOC overhead for word count, and for KMeans developer only needs
to add six lines of code to solve one access pattern issue.

Overall, the circuit approach is the easiest to use as it does not require any
additional effort from the developer. The manual approach involves a lot of
efforts in analyzing the original code and conducting the conversion. In
contrast, the framework approach hides many details with the framework
implementation and minimizes the developer’s efforts. However, it does require
the developer to learn to use the framework first.

##  VI Conclusion

Data oblivious programs provide excellent defenses against several side-
channel attacks targeting TEE applications. However, developing oblivious
programs is challenging. We have analyzed four representative approaches that
can help developers convert non-oblivious programs to oblivious ones. Among
these approaches, we consider performance and ease of use (and possibly
readiness to use) are critical measures. Our experimental results show that:
(1) The manual composition approach gives the best performance guarantee,
while developers must fully understand the access pattern of every part of
their code and learn the corresponding conversion method; (2) The framework
approach for data-intensive applications achieves a good balance between
performance and ease of use; (3) The circuit approach is theoretically sound,
but extremely expensive in practice; and (4) the compiler approach is
promising, but not mature enough for practical use. We hope our analysis and
evaluation will help both practitioners to decide their solutions and
researchers to explore potential issues.

We consider a few promising research directions. (1) The compiler approach is
the most appealing one, as it aims to make the conversion process fully
transparent to developers and the converted program to have a good performance
close to the manual composition approach. (2) Another direction is data
oblivious libraries/frameworks and software tools to automate the conversion
process as possible and minimize the developers’ manual efforts. The framework
approach is an excellent example of this direction.

## References

  * [1] A. Ahmad, B. Joe, Y. Xiao, Y. Zhang, I. Shin, and B. Lee.  Obfuscuro: A commodity obfuscation engine on intel sgx.  In Network and Distributed System Security Symposium, 2019.
  * [2] A. Ahmad, K. Kim, M. I. Sarfaraz, and B. Lee.  Obliviate: A data oblivious file system for intel sgx.  In the Network and Distributed System Security Symposium, 2018.
  * [3] A. K. M. M. Alam, S. Sharma, and K. Chen.  Sgx-mr: Regulating dataflows for protecting access patterns of data-intensive sgx applications.  Proceedings on Privacy Enhancing Technologies, 2021(1):5 – 20, 01 Jan. 2021.
  * [4] K. E. Batcher.  Sorting networks and their applications.  In Proceedings of the April 30–May 2, 1968, Spring Joint Computer Conference, AFIPS ’68 (Spring), pages 307–314, New York, NY, USA, 1968\. ACM.
  * [5] Z. Brakerski and V. Vaikuntanathan.  Fully homomorphic encryption from ring-lwe and security for key dependent messages.  In Proceedings of the 31st Annual Conference on Advances in Cryptology, CRYPTO’11, pages 505–524, Berlin, Heidelberg, 2011. Springer-Verlag.
  * [6] F. Brasser, S. Capkun, A. Dmitrienko, T. Frassetto, K. Kostiainen, and A.-R. Sadeghi.  Dr. sgx: Hardening sgx enclaves against cache attacks with data location randomization.  arXiv preprint arXiv:1709.09917, 2017.
  * [7] J. V. Bulck, M. Minkin, O. Weisse, D. Genkin, B. Kasikci, F. Piessens, M. Silberstein, T. F. Wenisch, Y. Yarom, and R. Strackx.  Foreshadow: Extracting the keys to the intel SGX kingdom with transient out-of-order execution.  In 27th USENIX Security Symposium (USENIX Security 18), page 991–1008, Baltimore, MD, Aug. 2018. USENIX Association.
  * [8] J. V. Bulck, N. Weichbrodt, R. Kapitza, F. Piessens, and R. Strackx.  Telling your secrets without page faults: Stealthy page table-based attacks on enclaved execution.  In 26th USENIX Security Symposium (USENIX Security 17), pages 1041–1056, Vancouver, BC, Aug. 2017. USENIX Association.
  * [9] N. Büscher, D. Demmler, S. Katzenbeisser, D. Kretzmer, and T. Schneider.  Hycc: Compilation of hybrid protocols for practical secure computation.  In Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security, pages 847–861, 2018.
  * [10] D. Cash, P. Grubbs, J. Perry, and T. Ristenpart.  Leakage-abuse attacks against searchable encryption.  In Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security, CCS ’15, page 668–679, New York, NY, USA, 2015. Association for Computing Machinery.
  * [11] K. Chen and S. Guo.  Rasp-boost: Confidential boosting-model learning with perturbed data in the cloud.  IEEE Transactions on Cloud Computing, 6(2):584–597, 2018.
  * [12] S. D. Constable and S. Chapin.  libOblivious: A c++ library for oblivious data structures and algorithms.  In Electrical Engineering and Computer Science - Technical Reports. 184, 2018.
  * [13] V. Costan and S. Devadas.  Intel sgx explained.  IACR Cryptology ePrint Archive, 2016:86, 2016.
  * [14] J. Dean and S. Ghemawat.  Mapreduce: Simplified data processing on large clusters.  In OSDI, pages 137–150, 2004.
  * [15] T. T. A. Dinh, P. Saxena, E. Chang, B. C. Ooi, and C. Zhang.  M2R: enabling stronger privacy in mapreduce computation.  In USENIX Security Symposium, pages 447–462. USENIX Association, 2015.
  * [16] S. Felsen, Á. Kiss, T. Schneider, and C. Weinert.  Secure and private function evaluation with intel sgx.  In Proceedings of the 2019 ACM SIGSAC Conference on Cloud Computing Security Workshop, pages 165–181, 2019.
  * [17] Freundschafter.  About amd trustzone, amd platform security processor (psp), amd secure technology. accessed: Jan. 13, 2020.  [Online].
  * [18] O. Goldreich and R. Ostrovsky.  Software protection and simulation on oblivious ram.  Journal of the ACM, 43:431–473, 1996.
  * [19] D. A. Heath.  New Directions in Garbled Circuits.  PhD thesis, Georgia Institute of Technology, 2022.
  * [20] Y. Huang, D. Evans, J. Katz, and L. Malka.  Faster secure two-party computation using garbled circuits.  In USENIX Conference on Security, pages 35–35, 2011.
  * [21] S. Krastnikov, F. Kerschbaum, and D. Stebila.  Efficient oblivious database joins.  Proc. VLDB Endow., 13(12):2132–2145, jul 2020.
  * [22] M. Lipp, M. Schwarz, D. Gruss, T. Prescher, W. Haas, A. Fogh, J. Horn, S. Mangard, P. Kocher, D. Genkin, Y. Yarom, and M. Hamburg.  Meltdown: Reading kernel memory from user space.  In 27th USENIX Security Symposium (USENIX Security 18), 2018\.
  * [23] C. Liu, X. S. Wang, K. Nayak, Y. Huang, and E. Shi.  Oblivm: A programming framework for secure computation.  In 2015 IEEE Symposium on Security and Privacy, pages 359–376, May 2015.
  * [24] F. Liu, Y. Yarom, Q. Ge, G. Heiser, and R. B. Lee.  Last-level cache side-channel attacks are practical.  In Proceedings of the 2015 IEEE Symposium on Security and Privacy, SP ’15, page 605–622, USA, 2015. IEEE Computer Society.
  * [25] P. Mohassel and Y. Zhang.  Secureml: A system for scalable privacy-preserving machine learning.  In 2017 IEEE Symposium on Security and Privacy (SP), pages 19–38, 2017.
  * [26] V. Nikolaenko, U. Weinsberg, S. Ioannidis, M. Joye, D. Boneh, and N. Taft.  Privacy-preserving ridge regression on hundreds of millions of records.  In IEEE Symposium on Security and Privacy, pages 334–348, 2013\.
  * [27] A. Nilsson, P. N. Bideh, and J. Brorsson.  A survey of published attacks on intel sgx.  arXiv preprint arXiv:2006.13598, 2020.
  * [28] O. Ohrimenko, M. Costa, C. Fournet, C. Gkantsidis, M. Kohlweiss, and D. Sharma.  Observing and preventing leakage in mapreduce.  In Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security, CCS ’15, page 1570–1581, New York, NY, USA, 2015\. Association for Computing Machinery.
  * [29] O. Ohrimenko, F. Schuster, C. Fournet, A. Mehta, S. Nowozin, K. Vaswani, and M. Costa.  Oblivious multi-party machine learning on trusted processors.  In T. Holz and S. Savage, editors, 25th USENIX Security Symposium, USENIX Security 16, Austin, TX, USA, August 10-12, 2016, pages 619–636. USENIX Association, 2016.
  * [30] O. Ohrimenko, F. Schuster, C. Fournet, A. Mehta, S. Nowozin, K. Vaswani, and M. Costa.  Oblivious multi-party machine learning on trusted processors.  In 25th USENIX Security Symposium, USENIX Security 16, Austin, TX, USA, August 10-12, 2016., pages 619–636, 2016.
  * [31] M. Orenbach, Y. Michalevsky, C. Fetzer, and M. Silberstein.  Cosmix: A compiler-based system for secure memory instrumentation and execution in enclaves.  In USENIX Annual Technical Conference, pages 555–570, 2019.
  * [32] A. Ozdemir, F. Brown, and R. S. Wahby.  Circ: Compiler infrastructure for proof systems, software verification, and more.  In 2022 IEEE Symposium on Security and Privacy (SP), pages 2248–2266. IEEE, 2022.
  * [33] A. Rane, C. Lin, and M. Tiwari.  Raccoon: Closing digital side-channels through obfuscated execution.  In Proceedings of the 24th USENIX Conference on Security Symposium, SEC’15, page 431–446, USA, 2015. USENIX Association.
  * [34] O. Russakovsky, J. Deng, H. Su, J. Krause, S. Satheesh, S. Ma, Z. Huang, A. Karpathy, A. Khosla, M. Bernstein, A. C. Berg, and L. Fei-Fei.  ImageNet Large Scale Visual Recognition Challenge.  International Journal of Computer Vision (IJCV), 115(3):211–252, 2015.
  * [35] S. Sagar and C. Keke.  Confidential machine learning on untrusted platforms: a survey.  Cybersecurity, 4(1):1–19, 2021.
  * [36] S. Sasy, S. Gorbunov, and C. W. Fletcher.  Zerotrace : Oblivious memory primitives from intel SGX.  In 25th Annual Network and Distributed System Security Symposium, NDSS 2018, San Diego, California, USA, February 18-21, 2018, 2018\.
  * [37] F. Schuster, M. Costa, C. Fournet, C. Gkantsidis, M. Peinado, G. Mainar-Ruiz, and M. Russinovich.  Vc3: Trustworthy data analytics in the cloud using sgx.  In 36th IEEE Symposium on Security and Privacy, 2015.
  * [38] O. A. Selo, M. H. Rachid, A. Shikfa, Y. Wang, and Q. Malluhi.  Private function evaluation using intel’s sgx.  Security and Communication Networks, 2020:1–10, 2020.
  * [39] S. Sharma and K. Chen.  Confidential boosting with random linear classifiers for outsourced user-generated data.  In Computer Security - ESORICS 2019 - 24th European Symposium on Research in Computer Security, Luxembourg, September 23-27, 2019, Proceedings, Part I, pages 41–65, 2019.
  * [40] S. Shinde, Z. L. Chua, V. Narayanan, and P. Saxena.  Preventing page faults from telling your secrets.  In Proceedings of the 11th ACM on Asia Conference on Computer and Communications Security, ASIACCS16, page 317–328, New York, NY, USA, 2016\. Association for Computing Machinery.
  * [41] R. L. Simon.  Fair play: The ethics of sport.  Routledge, 2018.
  * [42] J. Son, G. Prechter, R. Poddar, R. A. Popa, and K. Sen.  ObliCheck: Efficient verification of oblivious algorithms with unobservable state.  In 30th USENIX Security Symposium (USENIX Security 21), 2021.
  * [43] J. Van Bulck, D. Moghimi, M. Schwarz, M. Lipp, M. Minkin, D. Genkin, Y. Yuval, B. Sunar, D. Gruss, and F. Piessens.  LVI: Hijacking Transient Execution through Microarchitectural Load Value Injection.  In 41th IEEE Symposium on Security and Privacy (S&P’20), 2020.
  * [44] J. Van Bulck, F. Piessens, and R. Strackx.  Sgx-step: A practical attack framework for precise enclave execution control.  In Proceedings of the 2nd Workshop on System Software for Trusted Execution, SysTEX’17, New York, NY, USA, 2017. Association for Computing Machinery.
  * [45] J. Van Bulck, F. Piessens, and R. Strackx.  Nemesis: Studying microarchitectural timing leaks in rudimentary cpu interrupt logic.  In Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security, pages 178–195, 2018.
  * [46] T. White.  Hadoop: The Definitive Guide.  O’Reilly Media, 2009.
  * [47] Y. Xu, W. Cui, and M. Peinado.  Controlled-channel attacks: Deterministic side channels for untrusted operating systems.  In 2015 IEEE Symposium on Security and Privacy, pages 640–656, May 2015.
  * [48] Y. Yarom and K. Falkner.  Flush+reload: A high resolution, low noise, l3 cache side-channel attack.  In Proceedings of the 23rd USENIX Conference on Security Symposium, SEC’14, page 719–732, USA, 2014. USENIX Association.
  * [49] M. Zaharia, M. Chowdhury, M. J. Franklin, S. Shenker, and I. Stoica.  Spark: Cluster computing with working sets.  In Proceedings of the 2Nd USENIX Conference on Hot Topics in Cloud Computing, HotCloud’10, pages 10–10, Berkeley, CA, USA, 2010. USENIX Association.
  * [50] W. Zheng, A. Dave, J. G. Beekman, R. A. Popa, J. E. Gonzalez, and I. Stoica.  Opaque: An oblivious and encrypted distributed analytics platform.  In USENIX Symposium on Networked Systems Design and Implementation, 2017.

##  Appendix A Sample ORAM-Hash algorithms

Algorithm 1 Buffer Management for ORAM-Hash algorithms

1: Buffer contains a working block $B$ for new records, and a cache of $m$
blocks $C$.

2: Function $\mathrm{GetBlock}(block\\_id)$

3: if $block\\_id$ not in the cache $C$ then

4: decide a block to overwrite with an algorithm like LRU; the victim block is
written back to the output file.

5: $new\\_block\leftarrow$ $request\\_oram\\_block(block\\_id)$

6: add $new\\_block$ to the cache

7: end if

8: $block\\_reference$ $\leftarrow$ find the $block\\_id$ in the cache

9: return $block\\_reference$

1: Function $\mathrm{AddRecordToBlock}(record)$

2: if working block $B$ is full then

3: evict LRU and write out the victim block

4: copy $B$ to the cache

5: clear the working block

6: end if

7: add $record$ to the working block

8: return $working\\_block\\_id$

Algorithm 2 HashMap-based KMeans in Enclave

1: Function $\mathrm{KMeans}(centroid\\_file,coordinates\\_file)$

2: initialize $ORAM$ and $Cache$ block

3: load initial $centroids$ from $centroid\\_file$

4: for all $block$ in $coordinates\\_file$ do

5: $points$ $\leftarrow$ ParseCoordinates($block$)

6: for each $pt$ in $points$ do

7: $centroid\\_index$ $\leftarrow$ FindNearestCentroid($pt$, $centroids$)

8: LocalMap[ $centroid\\_index$ ] $\leftarrow$ $pt$

9: end for

10: $combined\\_points$ $\leftarrow$ aggregate points under same centroid

11: for each ($centroid\\_index$, $point$) in $combined\\_points$ do

12: if $centroid\\_index$ not not in $HashMap$ then

13: $record$ $\leftarrow$ ($centroid\\_index$, $point$)

14: $id$ $\leftarrow$ AddRecordToBlock($centroid\\_index$)

15: $HashMap[$centroid_index$]$ $\leftarrow$ $id$

16: else

17: $id$ $\leftarrow$ $HashMap[$centroid_index$]$

18: $block\\_reference$ $\leftarrow$ GetBlock($id$)

19: update block in $block\\_reference$ with ($centroid\\_index$, $point$)

20: Write($block$)

21: end if

22: end for

23: end for

24: write all blocks from $ORAM$ to $centroid\\_file$


# Posterior Predictive Propensity Scores and $p$-Values

Peng Ding<EMAIL_ADDRESS>
Department of Statistics
University of California
Berkeley CA 94720 U.S.A.
Tianyu Guo<EMAIL_ADDRESS>
School of Mathematical Sciences
Peking University
No.5 Yiheyuan Road Beijing 100871 P.R.China

###### Abstract

Rosenbaum and Rubin (1983) introduced the notion of propensity score and
discussed its central role in causal inference with observational studies.
Their paper, however, causes a fundamental incoherence with an early paper by
Rubin (1978), which showed that the propensity score does not play any role in
the Bayesian analysis of unconfounded observational studies if the priors on
the propensity score and outcome models are independent. Despite the serious
efforts made in the literature, it is generally difficult to reconcile these
contradicting results. We offer a simple approach to incorporating the
propensity score in Bayesian causal inference based on the posterior
predictive $p$-value for the model with the strong null hypothesis of no
causal effects for any units whatsoever. Computationally, the proposed
posterior predictive $p$-value equals the classic $p$-value based on the
Fisher randomization test averaged over the posterior predictive distribution
of the propensity score. Moreover, using the studentized doubly robust
estimator as the test statistic, the proposed $p$-value inherits the doubly
robust property and is also asymptotically valid for testing the weak null
hypothesis of zero average causal effect. Perhaps surprisingly, this
Bayesianly motivated $p$-value can have better frequentist’s finite-sample
performance than the frequentist’s $p$-value based on the asymptotic
approximation especially when the propensity scores can take extreme values.

Keywords: Bayesian causal inference; doubly robust; frequentist’s property;
observational study; pivotal quantity; randomization test

##  1 Causal inference with observational studies

We focus on the canonical setting of causal inference with observational
studies. We assume exchangeability of the units and thus drop the index $i$
for the $i$th unit $(i=1,\ldots,n)$. Let $Z$ denote the binary treatment, $Y$
denote the outcome of interest, and $X$ denote the pretreatment covariates.
Under the potential outcomes framework (Neyman, 1923; Rubin, 1974; Rosenbaum
and Rubin, 1983), let $Y(1)$ and $Y(0)$ denote the hypothetical outcome under
the treatment and control, respectively. This framework allows us to define
individual causal effect $Y(1)-Y(0)$ and the average causal effect

$\tau=E\\{Y(1)-Y(0)\\}.$

A fundamental difficulty of causal inference is that we cannot simultaneously
observe both $Y(1)$ and $Y(0)$ for the same unit. The observed outcome equals
$Y=ZY(1)+(1-Z)Y(0)$.

Following Rosenbaum and Rubin (1983), we assume unconfoundedness and overlap
throughout:

$Z\begin{picture}(9.0,8.0)\put(0.0,0.0){\line(1,0){9.0}}
\put(3.0,0.0){\line(0,1){8.0}} \put(6.0,0.0){\line(0,1){8.0}}
\end{picture}\\{Y(1),Y(0)\\}\mid X,\quad 0<e(X)<1,$ (1)

where

$e(X)=P(Z=1\mid X)$

is the propensity score (PS). Under (1), the average causal effect can be
identified by

$\displaystyle\tau$ $\displaystyle=$ $\displaystyle
E\left\\{\frac{ZY}{e(X)}-\frac{(1-Z)Y}{1-e(X)}\right\\}$ (2) $\displaystyle=$
$\displaystyle E\\{\mu_{1}(X)-\mu_{0}(X)\\}$ (3)

where $\mu_{z}(X)=E(Y\mid Z=z,X)$ is the outcome mean conditional on
covariates under treatment $z$ $(z=0,1)$. The identification formula (2)
motivates the inverse PS weighting estimator (Rosenbaum, 1987)

$\hat{\tau}^{\textup{ipw}}=\frac{\sum_{i=1}^{n}Z_{i}Y_{i}/\hat{e}(X_{i})}{\sum_{i=1}^{n}Z_{i}/\hat{e}(X_{i})}-\frac{\sum_{i=1}^{n}(1-Z_{i})Y_{i}/\\{1-\hat{e}(X_{i})\\}}{\sum_{i=1}^{n}(1-Z_{i})/\\{1-\hat{e}(X_{i})\\}}$

where $\hat{e}(X_{i})$ denotes the estimated PS for unit $i$. Here we use the
Hajek form instead of the Horvitz–Thompson form due to its superior finite-
sample properties (Lunceford and Davidian, 2004). The identification formula
(3) motivates the outcome regression estimator

$\hat{\tau}^{\textup{reg}}=n^{-1}\sum_{i=1}^{n}\\{\hat{\mu}_{1}(X_{i})-\hat{\mu}_{0}(X_{i})\\}$

where $\hat{\mu}_{1}(X_{i})$ and $\hat{\mu}_{0}(X_{i})$ denote the estimated
conditional means of the outcomes under the treatment and control,
respectively. The estimator $\hat{\tau}^{\textup{ipw}}$ is consistent for
$\tau$ if the PS model is correct, whereas the estimator
$\hat{\tau}^{\textup{reg}}$ is consistent if the outcome model is correct.
Motivated by the semiparametric efficiency theory (Bickel et al., 1993;
Tsiatis, 2006), the doubly robust estimator combines both models (Bang and
Robins, 2005):

$\hat{\tau}^{\textup{dr}}=\hat{\tau}^{\textup{reg}}+n^{-1}\sum_{i=1}^{n}\left\\{\frac{Z_{i}R_{i}}{\hat{e}(X_{i})}-\frac{(1-Z_{i})R_{i}}{1-\hat{e}(X_{i})}\right\\}$

where $R_{i}=Y_{i}-\hat{\mu}_{Z_{i}}(X_{i})$ denotes the residual from outcome
modeling. The estimator $\hat{\tau}^{\textup{dr}}$ is consistent if either the
PS or the outcome model is correct, justifying its name “doubly robust.”

With parametric PS and outcome models, it is straightforward to construct
estimators for the variances of these estimators based on the theory of
M-estimation or the nonparametric bootstrap; see Lunceford and Davidian (2004)
and Yang and Ding (2020) for reviews. The recent literature has also extended
these estimators to allow for more flexible nonparametric or machine learning
estimation of the outcome model (Hahn, 1998), or the PS model (Hirano et al.,
2003), or both (Chernozhukov et al., 2018). We focus on estimators based on
parametric models but conjecture that similar results extend to estimators
based on more flexible models under some regularity conditions.

##  2 The role of the propensity score in Bayesian causal inference

###  2.1 The propensity score is ignorable in Bayesian causal inference

Let $\theta_{X}$, $\theta_{Z}$, and $\theta_{Y}$ represent, respectively, the
parameters for the models for the covariate distribution, the PS, the outcome
conditional on the treatment and covariates. Rewrite the identification
formula (3) of $\tau$ as

$\tau=\int\\{\mu_{1}(x;\theta_{Y})-\mu_{0}(x;\theta_{Y})\\}f(x;\theta_{X})\text{d}x$

which depends only on the unknown parameters $\theta_{X}$ and $\theta_{Y}$.
Assuming independent priors on the parameters $\theta_{X}$, $\theta_{Z}$ and
$\theta_{Y}$, the posterior distribution based on exchangeable data
$(X_{i},Z_{i},Y_{i})_{i=1}^{n}$ factors into three independent components:

$\displaystyle P(\theta_{X},\theta_{Z},\theta_{Y}\mid\cdot)$
$\displaystyle\propto$ $\displaystyle
P(\theta_{X})\prod_{i=1}^{n}P(X_{i};\theta_{X})\cdot
P(\theta_{Z})\prod_{i=1}^{n}P(Z_{i}\mid X_{i};\theta_{Z})\cdot
P(\theta_{Y})\prod_{i=1}^{n}P(Y_{i}\mid Z_{i},X_{i};\theta_{Y})$

The posterior distributions of $\theta_{X}$ and $\theta_{Y}$ do not depend on
the second component corresponding to the PS. Therefore, Bayesian inference of
$\tau$ does not depend on the PS. Saarela et al. (2016) gave a similar
discussion as above.

One might wonder whether the conclusions above will change if we use the
identification formula (2) based on the inverse PS weighting. We can verify
that under (1), the formula (2) reduces to the formula (3). The PS again does
not play any role in Bayesian causal inference.

The above discussion focuses on $\tau$, the average causal effect of a super
population. Rubin (1978) focused on the finite-sample average causal effect

$\tau_{\text{fs}}=n^{-1}\sum_{i=1}^{n}\\{Y_{i}(1)-Y_{i}(0)\\},$

and reduced the problem of causal inference to imputing the missing potential
outcomes based on their posterior predictive distributions. He also showed
that the PS can be ignored in the finite-sample Bayesian causal inference. By
Rubin (1978), the PS is ignorable. Hill (2011) and Ding and Li (2018)
discussed other parameters and reached the same conclusion.

###  2.2 Existing strategies to use the propensity score in Bayesian causal
inference

The PS is central in frequentist’s causal inference. Section 1 above reviews
its role in constructing the inverse PS and doubly robust estimators. In
contrast, Section 2 dismisses the role of the PS in Bayesian causal inference.
A parallel discussions appeared in survey sampling (Rubin, 1985; Pfeffermann,
1993).

Nevertheless, completely ignoring the PS seems worrisome. Because the PS
characterizes the treatment assignment mechanism, it is intuitive to use it in
one way or another in analyzing observational data. Below I will review some
strategies to use the PS in Bayesian causal inference, with the last one being
the proposal of this article.

#### Use the PS in the design phase

Rubin (1985) provided a heuristic argument based on robustness for the
importance of using the PS in Bayesian causal inference. Robins and Ritov
(1997) provided more theoretical discussion of this issue. Rubin (2007) later
argued that observational studies should have two stages: the design stage and
the analysis stage. Based on this, even the analysis stage is purely Bayesian
in the sense of Section 2.1, the PS plays a central role in the design stage
to make the observational study as close as possible to a randomized
experiment . This view highlights the role of the PS in designing
observational studies but still cannot incorporate the PS in the Bayesian
analysis reviewed in Section 2.

#### Use dependent priors

Section 2 assumes independent priors on the parameters $\theta_{X}$,
$\theta_{Z}$ and $\theta_{Y}$. Consequently, the posterior distribution
factors into three independent components, and then the PS is ignorable for
inferring $\tau$. The independence of the posterior distributions, however,
does not hold with dependent priors on $\theta_{X}$, $\theta_{Z}$ and
$\theta_{Y}$. Wang et al. (2012) used dependent prior for variable selection
in both the PS and outcome models. Ritov et al. (2014) constructed a dependent
prior that yielded frequentist’s properties. Their prior for the outcome model
depended on the PS, and they only focused on some special cases. In general,
this strategy may not be easy to implement to achieve desired frequentist’s
properties.

#### Use the PS as a covariate in the outcome model

Zigler et al. (2013), An (2010), Zigler and Dominici (2014), Zigler (2016),
and Hahn et al. (2020) forced the PS to enter the outcome model in Bayesian
computation. However, this strategy may be controversial. Arguably, the
outcome model that reflects the natural of the potential outcome generating
process should not be dependent on the PS model that reflects the treatment
assignment mechanism. Overall, while this strategy can be useful to improve
robustness of causal inference, it relies on a somewhat unnatural
factorization of the joint likelihood.

#### Posterior predictive estimation

Based on the Bayesian posterior predictive perspective, Saarela et al. (2016)
proposed to use the posterior distribution of the doubly robust estimator
$\hat{\tau}^{\textup{dr}}$, with the PS and outcome models drawn from their
posterior distributions. Antonelli et al. (2021) extended this idea to the
setting with high dimension covariates. This is a powerful idea to integrating
frequentist’s procedures in Bayesian causal inference.

#### Posterior predictive $p$-value

Closely related to Saarela et al. (2016) and Antonelli et al. (2021), the
proposal in the next section is based on the posterior predictive $p$-value
(PPP) for the model of the strong null hypothesis of no causal effects for any
units whatsoever. The PPP is a natural extension of the classic Fisher
randomization test (FRT) developed for randomized experiments. In
observational studies, the proposed PPP equals the $p$-value based on the FRT
averaged over the posterior predictive distribution of the PS. We present the
details below.

##  3 The PPP depends on the propensity score

###  3.1 General formulation of the PPP

We first show that the PS naturally enters Bayesian causal inference if we use
the PPP for the model with the strong null hypothesis (Rubin, 1980):

$H_{0\textsc{f}}:Y_{i}(1)=Y_{i}(0)=Y_{i}\text{ for all }i.$

The PS plays a central role in the PPP although it is ignorable in standard
Bayesian inference reviewed in Section 2.1. We will give a general formulation
of the PPP for $H_{0\textsc{f}}$ below.

Focus on the finite samples at hand. Under the strong null hypothesis
$H_{0\textsc{f}}$, the covariates and outcomes are all fixed, and the only
random component is the treatment indicators. Under (1), the posterior
distribution of $\theta_{Z}$ is

$P(\theta_{Z}\mid\cdot)\propto P(\theta_{Z})\prod_{i=1}^{n}P(Z_{i}\mid
X_{i},Y_{i};\theta_{Z})=P(\theta_{Z})\prod_{i=1}^{n}P(Z_{i}\mid
X_{i};\theta_{Z}).$

It only depends on the PS model and reduces to a basic problem in Bayesian
modeling. For instance, if $P(Z_{i}\mid X_{i};\theta_{Z})$ follows a logistic
model, then $P(\theta_{Z}\mid\cdot)$ is the corresponding posterior
distribution, which can be easily obtained using the MCMClogit function in the
MCMCpack package in R (Martin et al., 2011).

Define the statistic as $T=T(\bm{Z},\bm{X},\bm{Y})$, where
$\bm{Z},\bm{X},\bm{Y}$ are the concatenated treatments, covariates, outcomes
for all observed units. Define

$\textup{PPP}=P^{\textup{pred}}\left\\{T(\bm{Z}^{\textup{pred}},\bm{X},\bm{Y})\geq
T(\bm{Z},\bm{X},\bm{Y})\right\\}$

where $P^{\textup{pred}}$ is the probability measure over the posterior
predictive distribution of $Z^{\textup{pred}}$ given the data:

$P(\bm{Z}^{\textup{pred}}\mid\cdot)=\int\prod_{i=1}^{n}P(Z_{i}^{\textup{pred}}\mid
X_{i},\theta_{Z})P(\theta_{Z}\mid\cdot)\textup{d}\theta_{Z}.$

It is clear that the PS plays a central role in defining the Bayesian PPP.

The PPP was proposed for general Bayesian inference (Rubin, 1984; Meng, 1994;
Gelman et al., 1996). It has also been applied to many other Bayesian causal
inference problems (e.g., Rubin, 1984, 1998; Mattei et al., 2013; Espinosa et
al., 2016; Jiang et al., 2016; Forastiere et al., 2018; Zeng et al., 2020).

###  3.2 Implementation

We then show how to implement the generic PPP introduced above. The first
implementation follows the definition of the PPP closely: we simulation the
test statistic by first drawing $\theta_{Z}$ from its posterior distribution
and then drawing the treatment indicators conditional on $\theta_{Z}$. The
detailed algorithm is below:

  1. A1

draw $\theta_{Z}^{r}$ based on $P(\theta_{Z}\mid\cdot)$, draw $Z_{i}^{r}$
based on $P(Z_{i}=1\mid X_{i},\theta_{Z}^{r})$ for all units, and compute the
statistic $T^{r}=T^{r}(\bm{Z}^{r},\bm{X},\bm{Y})$;

  2. A2

repeat the above step to obtain $T^{r}\ (r=1,\ldots,R)$;

  3. A3

calculate

$\displaystyle\textup{PPP}\stackrel{{\scriptstyle\cdot}}{{=}}R^{-1}\sum_{r=1}^{R}\mathcal{I}(T^{r}\geq
T).$ (4)

Computationally, the above algorithm is straightforward. We use it to compute
the PPP in simulation in Section 4.

Moreover, an alternative implementation below can provide more insights into
the PPP. By swapping the integral in the definition of the PPP, we can rewrite
the PPP as the FRT averaged over the posterior predictive distribution of the
PS. We give the details below. Equivalently, we can also obtain the PPP based
on

$\displaystyle\textup{PPP}=\int
p(\theta_{Z})P(\theta_{Z}\mid\cdot)\textup{d}\theta_{Z}$ (5)

where $p(\theta_{Z})$ is the $p$-value for a fixed $\theta_{Z}$ defined below:

  1. B1

draw $Z_{i}^{s}(\theta_{Z})$ based on $P(Z_{i}=1\mid X_{i};\theta_{Z})$ for
all units, and compute the statistic
$T^{s}(\theta_{Z})=T^{s}(\bm{Z}^{s}(\theta_{Z}),\bm{X},\bm{Y})$;

  2. B2

repeat the above step to obtain $T^{s}(\theta_{Z})$ $(s=1,\ldots,S)$;

  3. B3

calculate

$p(\theta_{Z})\stackrel{{\scriptstyle\cdot}}{{=}}S^{-1}\sum_{s=1}^{S}\mathcal{I}(T^{s}(\theta_{Z})\geq
T).$

For a fixed $\theta_{Z}$, the $p$-value $p(\theta_{Z})$ is justified by the
standard FRT because the treatment assignment is known. The PPP equals the
average of $p(\theta_{Z})$ over the posterior distribution of $\theta_{Z}$ by
(5). Meng (1994) and Gelman et al. (1996) re-formulated the PPP as (5) and
motivated the above procedure B1–B3.

As a side comment, the FRT interpretation of the PPP is natural in causal
inference with observational studies. This interpretation cannot be
generalized to the survey sampling setting although the existing literature
focused more on the commonality of causal inference and survey sampling (e.g.,
Rubin, 1985; Bang and Robins, 2005). They differ in this aspect.

###  3.3 Choice of the test statistic: studentized estimators are superior

We now discuss the choice of the test statistic. The generic PPP introduced in
Section 3.1 allows for using any test statistic. However, practitioners may
find the strong null hypothesis restrictive. Moreover, frequentist’s
statisticians may completely dismiss the PPP due to its Bayesian nature. To
address these concerns, we propose to use the studentized doubly robust
statistic in the PPP, which yields an asymptotically valid $p$-value for the
weak null hypothesis

$H_{0\textsc{n}}:\tau=0$

for the average causal effect. This guarantee is under the frequentist’s
paradigm (cf. Robins et al., 2000) even though the original PPP is motivated
by Bayesian thinking.

Even though Section 1 has a completely different motivation from the Bayesian
PPP, the estimators there can provide important insights into choosing the
test statistic. If $H_{0\textsc{n}}$ is of interest, then intuitively, we can
choose $T$ as the absolute value of $\hat{\tau}^{\textup{ipw}}$,
$\hat{\tau}^{\textup{reg}}$ or $\hat{\tau}^{\textup{dr}}$. Previous results
for the FRT (Chung and Romano, 2013; Wu and Ding, 2021; Zhao and Ding, 2021),
however, suggest that using them in the PPP does not ensure correct type one
error rate even in large samples. Better choices are the absolute value of the
studentized estimators, that is, $\hat{\tau}^{\textup{ipw}}$,
$\hat{\tau}^{\textup{reg}}$ and $\hat{\tau}^{\textup{dr}}$ divided by the
corresponding consistent standard errors. Our simulation below will
demonstrate the superiority of the studentized estimators, especially the one
based on the doubly robust estimator. We focus on the empirical evaluation of
the PPP and leave the rigorous frequentist’s theory to another report.

###  3.4 Special case: FRT

With a randomized experiment, $P(Z_{i},\ldots,Z_{n}\mid X_{1},\ldots,X_{n})$
is determined by the designer of the experiment without any unknown parameter.
In this case, $\theta_{Z}$ is empty and we do not need to simulate its
posterior distribution. In calculating the PPP, we simply simulate the
treatment indicators from $P(Z_{i},\ldots,Z_{n}\mid X_{1},\ldots,X_{n})$,
following the same rule as the initial randomized experiment. This is
precisely the FRT, as pointed out by Rubin (1984, Section 5.6) and Rubin
(2005, Section 4).

Rubin pointed out the Bayesian interpretation of the FRT and thus hinted at
the idea in this article. However, he did not pursue the general form of the
PPP proposed above for observational studies.

##  4 Simulation

In this section, we evaluate the finite-sample performance of the PPP via
simulation. The results suggest that the PPP using the studentized doubly
robust estimator has the most desirable properties.

For the frequentist’s evaluation, we repeatedly generate the data for 3000
times. In each replication, we follow the procedures A1–A3 in Section 3.2 to
calculate the PPP. We use the function MCMClogit in the MCMCpack to simulate
the posterior distribution of the coefficients of the logistic PS model, with
an improper uniform prior on $\theta_{Z}$, 1000 burn-in iterations, and 2000
draws of the $\theta_{Z}^{r}$’s.

###  4.1 Data generating process and model specification

We choose the sample size as $n=1000$. We consider two different types of data
generating process (DGP).

#### DGP with regular PS

We first generate four covariates from

$\displaystyle X_{i1}=W_{i1},\quad X_{i2}=W_{i2}+0.3X_{i1},$ $\displaystyle
X_{i3}=W_{i3}+0.2(X_{i1}X_{i2}-X_{i2}),\quad
X_{i4}=W_{i4}+0.1(X_{i1}+X_{i3}+X_{i2}X_{i3}),$

with

$W_{i1}\sim\text{Bernoulli}(0.5),\quad W_{i2}\sim\text{Uniform}(0,2),\quad
W_{i3}\sim\text{Exponential}(1),\quad W_{i4}\sim\chi^{2}(4).$

The PS follows the logistic model

$P(Z_{i}=1\mid
X_{i};\theta_{Z})=\\{1+\exp(-X_{i}^{\scriptscriptstyle\text{T}}\theta_{Z})\\}^{-1}\quad\text{
with }\theta_{Z}=(-1,0.5,-0.25,-0.1)^{\scriptscriptstyle\text{T}}.$

The outcomes follow the linear models:

$Y_{i}(0)=\
\mu_{0}+({X}_{i}-\mu)^{\scriptscriptstyle\text{T}}{\beta}_{1}+\epsilon_{i}(0),\quad
Y_{i}(1)=\
\mu_{1}+({X}_{i}-\mu)^{\scriptscriptstyle\text{T}}{\beta}_{0}+\epsilon_{i}(1),$

with $\epsilon_{i}(0)\sim\mathcal{N}(0,5^{2})$,
$\epsilon_{i}(1)\sim\mathcal{N}(0,1^{2})$, and

$\mu_{1}=\mu_{0}=1,\quad\mu=\mathbb{E}(X),\quad\beta_{1}=(0.1,-0.2,-0.2,-0.2)^{\scriptscriptstyle\text{T}},\quad\beta_{0}=(-0.1,0.3,0.1,-0.2)^{\scriptscriptstyle\text{T}}.$

So $\tau=\mathbb{E}\\{Y(1)\\}-\mathbb{E}\\{Y(0)\\}=\mu_{1}-\mu_{0}=0$.

#### DGP with extreme PS

We first generate two covariates

$X_{i1}=\exp(W_{i1}),\quad X_{i2}=\exp(W_{i2})\quad\text{ with
}(W_{i1},W_{i2})^{\scriptscriptstyle\text{T}}\sim\mathcal{N}(0,I_{2}).$

The PS model is

$P(Z_{i}=1\mid
X_{i};\theta_{Z})=\\{1+\exp(1-X_{i}^{\scriptscriptstyle\text{T}}\theta_{Z})\\}^{-1}\quad\text{
with }\theta_{Z}=(1,-1)^{\scriptscriptstyle\text{T}}.$

The coefficients of the outcome models change to
$\mu_{0}=\mu_{1}=-1+0.1\sqrt{e}$,
$\beta_{1}=(-0.2,0.1)^{\scriptscriptstyle\text{T}}$ and
$\beta_{0}=(0.2,-0.1)^{\scriptscriptstyle\text{T}}$. So again $\tau=0$.

For each DGP, we consider four combinations of model specifications:

  1. (i)

Both the PS and the outcome models are correctly specified.

  2. (ii)

The PS model is correctly specified but the outcome model is misspecified. In
particular, for the DGP without extreme PS, we regress $Y$ on $W_{2}$ and and
$W_{3}$; for the DGP with extreme PS, we regress $Y$ on $W_{1}$ and $W_{2}$.

  3. (iii)

The outcome model is correctly specified but the PS model is misspecified. In
particular, for the DGP without extreme PS, we regress $Z$ on $W_{2}$ and
$W_{3}$; for the DGP with extreme PS, we regress $Z$ on $W_{1}$ and $W_{2}$.

  4. (iv)

Both the PS and the outcome models are misspecified.

###  4.2 Simulation under the weak null hypothesis

We first show that the problem of using the unstudentized statistics under the
weak null hypothesis. The original DGP without extreme PS yields conservative
PPP. Once we flip the treatment and the control group, we can get anti-
conservative PPP, as shown in Figure 1.

Figure 1: PPP using the unstudentized test statistics under $H_{0\textsc{n}}$
and the DGP without extreme PS. To obtain the anti-conservative PPP, we change
$Z_{i}$ to $1-Z_{i}$. The densities are truncated at $2$.

We then show the superiority of using the studentized statistics under weak
null hypothesis. For computational simplicity, we use the estimated standard
errors based on the theory of M-estimation. Figure 2(a) shows the distribution
of the PPP under the DGP without extreme PS. The PPP has uniform distributions
with correctly specified models. The PPP with the studentized double robust
estimator is doubly robust since it is uniform if either the PS or the outcome
model is correctly specified. It is our final recommendation.

Under the DGP with extreme PS, the superiority of our recommendation becomes
clearer, as shown in Figure 2(b).

(a) DGP without extreme PS

(b) DGP with extreme PS

Figure 2: PPP using studentized test statistics under $H_{0\textsc{n}}$. The
densities are truncated at $2$.

###  4.3 Comparison of the PPP with normal approximation

We now compare the performance of PPP and the normal approximation based on
the studentized doubly robust estimator. We use the standard errors based on
both the asymptotic expansion and the bootstrap by resampling the data 2000
times. So in total, we compare four $p$-values.

We first compare them under the weak null hypothesis. Under the DGP without
extreme PS, they have similar performance, so we omit the results. Under the
DGP with extreme PS, the bootstrap or PPP alone has superior performance
compared to the normal approximation based on the asymptotic standard error;
their combination does not yield further improvement. Figure 3(a) shows the
histograms of the four $p$-values under four scenarios.

We then compare their power under an alternative hypothesis. We use the DGP
without extreme PS for this case. Let $\mu_{1}=1.1$ and $\mu_{0}=1$ so that
$\tau=\mu_{1}-\mu_{0}=0.1$. In this scenario, all $p$-values have similar
power as shown in Figure 3(b).

(a) under the DGP with extreme PS and the weak null hypothesis

(b) under the DGP without extreme PS and an alternative hypothesis

Figure 3: Comparison of the PPP with normal approximation based on the
studentized doubly robust estimator (densities truncated at 2)

###  4.4 Replication files and data analysis

The replication files of this article can be found at Harvard Dataverse:

> https://doi.org/10.7910/DVN/QPOS31

There we post the R code for the simulation studies as well as two data
analysis examples.

##  5 Discussion

###  5.1 Summary

We first reviewed the conceptual difficulty of using the PS in Bayesian causal
inference in Section 2. We then build upon Rubin (1984) to proposed a PPP in
Section 3, which naturally uses the PS and extends the classic FRT by
averaging over the posterior predictive distribution of the PS. Moreover, we
recommend using the studentized doubly robust estimator in the PPP, which
yields superior finite-sample properties even from the frequentist’s
perspective under the weak null hypothesis, as illustrated by the simulation
studies in Section 4.

###  5.2 Frequentist’s properties

We have used simulation in Section 4 to evaluate the frequentist’s properties
of the PPP via simulation which leads to the following conjecture:

Conjecture: Assume $\tau=0$ and regularity conditions. The PPP with the
studentized doubly robust estimator, $\text{PPP}^{\text{dr}}$, has the
following asymptotic property:

$\text{PPP}^{\text{dr}}\stackrel{{\scriptstyle\text{d}}}{{\longrightarrow}}\text{Uniform}(0,1),\qquad\text{
as }n\rightarrow\infty$

if either the PS or the outcome model is correctly specified.

The conjecture is a frequentist’s statement although $\text{PPP}^{\text{dr}}$
is motivated by a Bayesian procedure. Intuitively, it holds because the
studentized doubly robust estimator is asymptotically pivotal if either the PS
or the outcome model is correctly specified. It ensures that we can use
$\text{PPP}^{\text{dr}}$ as a standard frequentist’s $p$-value for testing the
weak null hypothesis of $\tau=0.$ We leave the proof of the conjecture to
future work.

###  5.3 Epilogue: Did Rosenbaum and Rubin (1983) mention the Bayesian
propensity score?

Yes, they did. In Rosenbaum and Rubin (1983, Section 1.3), they wrote:

> To a Bayesian, estimates of these probabilities are posterior predictive
> probabilities of assignment to treatment $1$ for a unit with vector $x$ of
> covariates.

However, they did not provide any further discussion on the role of the PS in
Bayesian causal inference perhaps due to the incoherence with Rubin (1978).
The existing literature has clearly documented the difficulty of using the PS
in standard Bayesian causal inference. We argue that a natural approach to
incorporate the PS in Bayesian causal inference is the PPP, which can be
viewed as the FRT averaged over the posterior predictive distribution of the
PS.

Acknowledgments

Peng Ding thanks the National Science Foundation (# 1945136) for support, Fan
Li for insightful discussion, Zhichao Jiang and Avi Feller for helpful
comments.

## References

  * An (2010) W. An.  Bayesian propensity score estimators: Incorporating uncertainties in propensity scores into causal inference.  _Sociological Methodology_ , 40:151–189, 2010.
  * Antonelli et al. (2021) J. Antonelli, G. Papadogeorgou, and F. Dominici.  Causal Inference in high dimensions: A marriage between Bayesian modeling and good frequentist properties.  _Biometrics_ , page in press, 2021.
  * Bang and Robins (2005) H. Bang and J. M. Robins.  Doubly robust estimation in missing data and causal inference models.  _Biometrics_ , 61:962–972, 2005.
  * Bickel et al. (1993) P. J. Bickel, C. A. J. Klaassen, Y. Ritov, and J. A. Wellner.  _Efficient and Adaptive Estimation for Semiparametric Models_.  Baltimore : Johns Hopkins University Press, 1993.
  * Chernozhukov et al. (2018) V. Chernozhukov, D. Chetverikov, M. Demirer, E. Duflo, C. Hansen, W. Newey, and J. Robins.  Double/debiased machine learning for treatment and structural parameters.  _The Econometrics Journal_ , 21:C1–C68, 2018.
  * Chung and Romano (2013) E. Y. Chung and J. P. Romano.  Exact and asymptotically robust permutation tests.  _Annals of Statistics_ , 41:484–507, 2013.
  * Ding and Li (2018) P. Ding and F. Li.  Causal inference: A missing data perspective.  _Statistical Science_ , 33:214–237, 2018.
  * Espinosa et al. (2016) V. Espinosa, T. Dasgupta, and D. B. Rubin.  A Bayesian perspective on the analysis of unreplicated factorial experiments using potential outcomes.  _Technometrics_ , 58:62–73, 2016.
  * Forastiere et al. (2018) L. Forastiere, F. Mealli, and L. Miratrix.  Posterior predictive p-values with Fisher randomization tests in noncompliance settings: Test statistics vs discrepancy variables.  _Bayesian Analysis_ , 13:681–701, 2018.
  * Gelman et al. (1996) A. E. Gelman, X.-L. Meng, and H. S. Stern.  Posterior predictive assessment of model fitness via realized discrepancies (with discussion).  _Statistica Sinica_ , 6:733–807, 1996.
  * Hahn (1998) J. Hahn.  On the role of the propensity score in efficient semiparametric estimation of average treatment effects.  _Econometrica_ , 66:315–331, 1998.
  * Hahn et al. (2020) P. R. Hahn, J. S. Murray, and C. M. Carvalho.  Bayesian regression tree models for causal inference: Regularization, confounding, and heterogeneous effects (with discussion).  _Bayesian Analysis_ , 15:965–1056, 2020.
  * Hill (2011) J. L. Hill.  Bayesian nonparametric modeling for causal inference.  _Journal of Computational and Graphical Statistics_ , 20:217–240, 2011.
  * Hirano et al. (2003) K. Hirano, G. W. Imbens, and G. Ridder.  Efficient estimation of average treatment effectss using the estimated propensity score.  _Econometrica_ , 71:1161–1189, 2003.
  * Jiang et al. (2016) Z. Jiang, P. Ding, and Z. Geng.  Principal causal effect identification and surrogate end point evaluation by multiple trials.  _Journal of the Royal Statistical Society: Series B (Statistical Methodology)_ , 78:829–848, 2016.
  * Lunceford and Davidian (2004) J. K. Lunceford and M. Davidian.  Stratification and weighting via the propensity score in estimation of causal treatment effects: A comparative study.  _Statistics in Medicine_ , 23:2937–2960, 2004.
  * Martin et al. (2011) A. D. Martin, K. M. Quinn, and J. H. Park.  MCMCpack: Markov chain Monte Carlo in R.  _Journal of Statistical Software_ , 42:1–21, 2011.
  * Mattei et al. (2013) A. Mattei, F. Li, and F. Mealli.  Exploiting multiple outcomes in Bayesian principal stratification analysis with application to the evaluation of a job training program.  _Annals of Applied Statistics_ , 7:2336–2360, 2013.
  * Meng (1994) X.-L. Meng.  Posterior predictive $p$-values.  _Annals of Statistics_ , 22:1142–1160, 1994.
  * Neyman (1923) J. Neyman.  On the application of probability theory to agricultural experiments: Essay on principles, Section 9. Masters Thesis. Portions translated into english by D. Dabrowska and T. Speed (1990).  _Statistical Science_ , 5:465–472, 1923.
  * Pfeffermann (1993) D. Pfeffermann.  The role of sampling weights when modeling survey data.  _International Statistical Review_ , 61:317–337, 1993.
  * Ritov et al. (2014) Y. Ritov, P. J. Bickel, A. C. Gamst, and B. J. K. Kleijn.  The Bayesian analysis of complex, high-dimensional models: Can it be CODA?  _Statistical Science_ , 29:619–639, 2014.
  * Robins and Ritov (1997) J. M. Robins and Y. Ritov.  Toward a curse of dimensionality appropriate (coda) asymptotic theory for semi-parametric models.  _Statistics in Medicine_ , 16:285–319, 1997.
  * Robins et al. (2000) J. M. Robins, A. van der Vaart, and V. Ventura.  Asymptotic distribution of P values in composite null models.  _Journal of the American Statistical Association_ , 95:1143–1156, 2000.
  * Rosenbaum (1987) P. R. Rosenbaum.  Model-based direct adjustment.  _Journal of the American Statistical Association_ , 82:387–394, 1987.
  * Rosenbaum and Rubin (1983) P. R. Rosenbaum and D. B. Rubin.  The central role of the propensity score in observational studies for causal effects.  _Biometrika_ , 70:41–55, 1983.
  * Rubin (1974) D. B. Rubin.  Estimating causal effects of treatments in randomized and nonrandomized studies.  _Journal of Educational Psychology_ , 66:688–701, 1974\.
  * Rubin (1978) D. B. Rubin.  Bayesian inference for causal effects: The role of randomization.  _Annals of Statistics_ , 6:34–58, 1978.
  * Rubin (1980) D. B. Rubin.  Comment on ‘Randomization analysis of experimental data: The Fisher randomization test’ by D. Basu.  _Journal of the American Statistical Association_ , 75:591–593, 1980.
  * Rubin (1984) D. B. Rubin.  Bayesianly justifiable and relevant frequency calculations for the applied statistician.  _Annals of Statistics_ , 12:1151–1172, 1984.
  * Rubin (1985) D. B. Rubin.  The use of propensity score in applied Bayesian inference.  In J. M. Bernardo, M. H. DeGroot, D. V. Lindley, and A. F. M. Smith, editors, _Bayesian Statistics_ , pages 463–472. Elsevier Science Publisher B.V., North-Holland, 1985.
  * Rubin (1998) D. B. Rubin.  More powerful randomization-based $p$-values in double-blind trials with non-compliance.  _Statistics in Medicine_ , 17:371–385, 1998.
  * Rubin (2005) D. B. Rubin.  Causal inference using potential outcomes: Design, modeling, decisions.  _Journal of the American Statistical Association_ , 100:322–331, 2005.
  * Rubin (2007) D. B. Rubin.  The design versus the analysis of observational studies for causal effects: Parallels with the design of randomized trials.  _Statistics in Medicine_ , 26:20–36, 2007.
  * Saarela et al. (2016) O. Saarela, L. R. Belzile, and D. A. Stephens.  A Bayesian view of doubly robust causal inference.  _Biometrika_ , 103:667–681, 2016.
  * Tsiatis (2006) A. A. Tsiatis.  _Semiparametric Theory and Missing Data_.  New York: Springer, 2006.
  * Wang et al. (2012) C. Wang, G. Parmigiani, and F. Dominici.  Bayesian effect estimation accounting for adjustment uncertainty.  _Biometrics_ , 68:661–671, 2012.
  * Wu and Ding (2021) J. Wu and P. Ding.  Randomization tests for weak null hypotheses in randomized experiments.  _Journal of the American Statistical Association_ , 116:1898–1913, 2021.
  * Yang and Ding (2020) S. Yang and P. Ding.  Combining multiple observational data sources to estimate causal effects.  _Journal of the American Statistical Association_ , 115:1540–1554, 2020.
  * Zeng et al. (2020) S. Zeng, F. Li, and P. Ding.  Is being an only child harmful to psychological health?: evidence from an instrumental variable analysis of China’s one-child policy.  _Journal of the Royal Statistical Society: Series A (Statistics in Society)_ , 183:1615–1635, 2020.
  * Zhao and Ding (2021) A. Zhao and P. Ding.  Covariate-adjusted Fisher randomization tests for the average treatment effect.  _Journal of Econometrics_ , 225:278–294, 2021.
  * Zigler (2016) C. M. Zigler.  The central role of Bayes’ theorem for joint estimation of causal effects and propensity scores.  _The American Statistician_ , 70:47–54, 2016.
  * Zigler and Dominici (2014) C. M. Zigler and F. Dominici.  Uncertainty in propensity score estimation: Bayesian methods for variable selection and model averaged causal effects.  _Journal of the American Statistical Association_ , 109:95–107, 2014.
  * Zigler et al. (2013) C. M. Zigler, K. Watts, R. W. Yeh, Y. Wang, B. A. Coull, and F. Dominici.  Model feedback in Bayesian propensity score estimation.  _Biometrics_ , 69:263–273, 2013.