1 Introduction↩︎

The rapid development of artificial intelligence and big data analytics applications has substantially promoted the profit of high-quality data. Consequently, it has also raised the issue of data privacy protection. The typical way to handle confidential data without leaking sensitive secrets is to process them in a trusted environment. An organization could maintain its own computing servers and control all the hardware and system software, e.g., the operating system (OS). Alternatively, with cloud computing and outsourced computing, they can leverage hardware processors equipped with trusted execution environments (TEEs), which can isolate sensitive execution from untrusted environments. TEEs allow computing on even untrusted machines to become trusted.

However, even in a trusted environment, without careful programming, an attacker can still obtain partial or complete information about the secrets by performing various side-channel attacks. Researchers have published a wide range of such attacks, utilizing shared caches [1], OS-controlled page tables [2], [3], hardware branch predictors [4], speculative execution [5], etc. Such attacks are possible because while the sensitive data are isolated at the architecture level, certain properties of the execution could still be leaked through timing observation and shared hardware units. If these side-channel properties depend on the secret values, the attacker can infer valid information from external observation without breaking the architecture isolation.

Various approaches have been proposed to alleviate side-channel attacks, either with extra hardware support [6]–[10], or using software techniques [3], [11]–[16]. Hardware methods may provide more fundamental solutions and less performance loss. But applying hardware changes is quite expensive and usually takes long time. In addition, the required fixes may sometimes conflict with microarchitecture-level performance optimizations and sacrifice the speed of non-sensitive execution. On the other hand, software solutions focus on making the side-channel information (such as execution time and I/O signals) of a trusted program execution not reveal any secret. This property of a program is called “obliviousness,” and oblivious programming aims to write the code in a way to achieve such obliviousness. Today, hardware and software defenses can be used together to target different side channels; timing and I/O pattern-related issues are best avoided by software, while hardware vulnerabilities like speculation execution require hardware modifications.

This work aims to design better toolchain support for oblivious programming. Existing methods for implementing oblivious programs can be classified into several categories, each with its own drawbacks. Some solutions [12], [16]–[18] propose domain-specific languages for obliviousness, but integrating a new language and its toolchain into existing codebases and development workflow is expensive, if not impractical, especially in an industrial environment with complicated software projects. Others [19], [20] rely on separate modeling tools to check program obliviousness without impacting the original compilation flow. But ensuring the consistency between the descriptive model and the actual implementation of a program is challenging and highly error-prone. The last direction [9], [14] is to modify the compilers and apply automatic program transformations during compilation. However, without knowing the high-level application semantics, code transformations can only be done conservatively and result in significant performance degradation, or simply cannot be done at all in complex cases.

In this work,

we present obliv-clang, a compiler plugin for the widely used, industry-class C++ language, which checks the obliviousness of a program statically at the compilation time. It is implemented using the popular clang and LLVM infrastructure. As the key principle, obliv-clang is designed to work directly with C++ and support its rich language features, including pointers and references, function calls, compound types, object-oriented programming, templates, and more. Therefore, it can seamlessly work with existing codebases with minimum porting effort, eliminating the extra burden of using a new domain-specific language in previous work. In addition, obliv-clang is implemented directly in the compiler, so it avoids the consistency issue between separate modeling and implementation. Finally, using a familiar, mature, and industry-class language like C++ allows developers to conveniently write their code, and also able to retain high performance for the developed oblivious programs.

The key challenge of designing a compilation-time checker like obliv-clang is its soundness, meaning that the check must be comprehensive so that if a program passes, it should be considered safe to execute. The major difficulty is to handle the arbitrarily nested pointers (like “a pointer to a pointer to a pointer”) in C++, which can be dereferenced, taken-address, and assigned in many ways. In particular, we find that assigning a secret pointer with a public pointer value, which seems benign, could sometimes be unsafe and leak sensitive data (see 2 in 3.2). To address this problem, obliv-clang formally introduces the concept of oblivious levels (olevels), together with a set of rules to deduce each variable’s olevel along the program dataflow and to forbid unsafe operations accordingly. These rules are extended beyond simple operations to support also function calls, compound types, and templates. In such a way, obliv-clang is able to provide verifiable security with formal proofs.

Since obliv-clang is a front-end checker, we also need to ensure that the backend compiler optimization passes do not break the obliviousness property. We thoroughly analyze the relevant optimization passes in LLVM and suppress the ones that may compromise obliviousness. Furthermore, we apply an extra double-check on the generated assembly code using existing tools [21], which ensure end-to-end obliviousness.

We have implemented several non-trivial oblivious algorithms, including PathORAM [22] and Oblivious BFS [23], using our obliv-clang tool, in order to demonstrate its good expressiveness. We also quantitatively evaluate obliv-clang, showing that the extra obliviousness check incurs minor overheads (less than 18%) to the compilation time, and it produces relatively high-performance compiled binaries. When compared to previous tools, the programs compiled with obliv-clang run 27.8% faster than Jasmin [13] and 66.9% faster than FaCT [12] on average. The implementation of obliv-clang has been open sourced at github.com/tsinghua-ideal/obliv-clang.

Our contributions in this paper are summarized below:

• The design and implementation of a program obliviousness check tool, obliv-clang, as a compiler plugin working seamlessly with the C++ language.

• A set of obliviousness check rules that support the rich set of C++ language features, including arbitrarily nested pointers, function calls, compound types, templates, etc.

• A formal proof about the soundness of our obliviousness check rules.

• The case studies and evaluation experiments to demonstrate the expressiveness and performance advantages of obliv-clang.

The rest of this paper is organized as follows. 2 provides background and discusses prior tools’ limitations. [sec:semantics] [sec:impl] present our design and describe implementation details. 5 gives the soundness proof. 6 discusses how to suppress backend optimization passes to avoid break obliviousness. 7 illustrates several case studies and evaluates our design. 8 discusses related work and 9 concludes the paper.

2 Background and Motivation↩︎

In this section, we first introduce the concept of oblivious programming and how it mitigates timing- and access-pattern-based information leakage in trusted hardware (2.1), and then discuss the limitations of existing approaches to motivate our work (2.2). We next describe our high-level approach and summarize the key challenges (2.3). Lastly, we specify our security model by formally defining properties that oblivious programs must satisfy (2.4).

2.1 Oblivious Programming↩︎

Program obliviousness prevents attackers from learning sensitive information through execution traces (timing, memory, and I/O patterns). Attackers extract traces either directly (through privileged access) or indirectly via shared hardware [1]–[3]. Oblivious programming requires branch conditions, memory, and I/O patterns to remain independent of sensitive data. Common techniques include redundant branch execution, oblivious memory scanning, and cmove-like instructions. Researchers have developed efficient algorithms including ORAM [22], oblivious BFS [23], and oblivious data structures [24].

Oblivious programming is tricky and subtle—developers can easily break obliviousness through overlooked details. Thus, automatic tools are essential to facilitate correct oblivious programming.

2.2 Tradeoffs and Limitations of Existing Tools↩︎

Previous work on compilation-time obliviousness guarantees can be classified along two dimensions. The first considers whether program behaviors are modified: some tools only perform checks [13], [19], [25], while others actively transform programs to hide non-oblivious branches and memory accesses [9], [11], [12], [14], [16], [26]. Automatic transformations simplify programming but introduce complexity, as generating dummy versions for program segments is not always straightforward. In many cases the compiler either has to apply general, conservative transformations that result in unnecessary performance overheads, or simply cannot handle irregular patterns.

The second dimension involves the level at which checks or transformations occur. Some tools target abstract syntax tree (AST) structures in the compiler frontend [11], [12], [14], [19], while others work on low-level intermediate representations (IRs), particularly LLVM IR, in the backend [9], [26]. Frontend approaches preserve more source code information, facilitating high-level analysis to achieve better efficiency. But in these tools, the unchanged backend optimizers may later alter the supposed-to-be oblivious behaviors and thus undermine security.

Besides the above tradeoffs, existing approaches for oblivious programming also have other key limitations. Many existing designs propose domain-specific languages (DSLs) to simplify compilation-time transformations. However, DSLs require costly toolchain development and lack standard features (editor support, build management, debugging tools, extensive libraries). Additionally, most DSL-based tools focus on small computation kernels, lacking expressiveness for complex systems.

2.3 Our Approach↩︎

We build upon C++ and the clang compiler, verifying obliviousness directly on source code at compilation time. C++ is widely used in industry. It offers well-defined semantics in its specification [27], a minimal runtime with close hardware control, and compatibility with numerous software interfaces and libraries. The clang compiler offers a friendly, extensible plugin interface used by many tools [28], [29], enabling non-intrusive checker implementation. The clang frontend processes C++ and C code in a unified AST format, allowing obliv-clang to handle C code seamlessly—important since many system and cryptographic libraries are written in C. While our tool is a checker, we also implement backend mechanisms to guarantee obliviousness during code generation (6).

Rust might also seem attractive given its memory safety guarantees. Nevertheless, we chose C++ for two reasons. First, Rust’s behavior lacks comprehensive specification—C++ has a detailed specification describing program semantics, while Rust relies on the latest rustc implementation as its standard. Second, rustc currently lacks a stable plugin interface, having deprecated its previous interfaces in 2018 [30].

Challenges. Working directly with C++ presents several challenges due to the necessity of comprehensively handling its rich and flexible semantics. First, a primary difficulty involves handling pointers and references, where expressing secrecy requirements for objects with arbitrarily nested pointers requires a generic, precise, and concise scheme. Second, function calls present another challenge, as implementations and call sites typically reside in different translation units compiled separately, necessitating obliviousness-aware interfaces to ensure consistency. Third, supporting object-oriented programming requires consideration of relationships between compound class objects, their members, and methods. Fourth, templates could generate multiple declarations from a common template, in which some may work on sensitive data and have oblivious requirements, while others do not. Finally, some cases require external knowledge that cannot be analyzed solely from code, such as calls to external libraries. Our design in 3 addresses these challenges.

2.4 Security Model↩︎

Our security model focuses on timing and access-pattern-related attacks in two scenarios:

1. The victim program executes in a TEE enclave, where adversaries with hardware access can perform access-pattern-based attacks, including timing, cache [1], and page-table [2], [3] attacks.

2. The victim program executes on normal hardware, where adversaries without hardware access can interact with the program and observe timing.

Side-channel attacks based on power [31], electromagnetism [32], speculative execution [5], rowhammer [33], and similar vectors are beyond our scope.

Preventing these vulnerabilities solely through oblivious programming is generally considered impossible or prohibitively expensive. Corresponding countermeasures are studied in orthogonal work [34], [35].

To ensure security under these assumptions, programs must satisfy the following properties in 1 2.

The first property ensures adversaries cannot learn secret information from execution traces, while the second prevents secret leakage to the public domain.

Formal definitions of object secrecy will be provided in 3.

3 Design↩︎

We designed obliv-clang, a C++ compiler plugin for clang that verifies program obliviousness directly on source code at compilation time. As a checker, obliv-clang’s primary goal is soundness: programs passing its checks should be considered safe. This section details obliv-clang’s semantics, including the required programmer annotations to indicate protected data and the comprehensive rules enforced to ensure obliviousness. We focus on addressing challenges of supporting flexible C++ semantics—pointers, references, function calls, and compound types—while maintaining compatibility with external libraries.

3.1 Getting Started: Oblivious Variables↩︎

The basic information required by obliv-clang is the knowledge of which variables should be treated as secret. Since a compiler cannot inherently determine which objects are sensitive, we require programmer annotations in the source code to provide this information. We believe such annotations only add moderate burden to programmers, as programmers typically well understand the purposes and secrecy requirements of their variables.

Beginning with a minimal language subset (no references, no nested pointers, only plain values), an object’s secrecy can be described by a boolean flag. obliv-clang requires secret variables to be annotated with the custom obliv attribute. C++ specifications allow compilers to define custom attributes as language extensions [27], which can be applied to declarations, statements, translation units, and other elements. Furthermore, with the clang toolchain, parsing attributes can be easily done using plugins, without intrusive changes to the compiler’s internal core logic (4).

To satisfy the Secrecy and Dataflow properties from 2.4, the following rules are required:

Note that “cast” in 2 refers to both explicit and implicit casting. In assignments, the right side is first cast into the target type before assignment to the left side, so this can also be considered as an assignment rule.

The following code snippet demonstrates these rules:

    #define OBLIV [[obliv]]  // to make it look less cumbersome

    // declare an oblivious variable
    OBLIV int x = 1729;
    // error: cannot assign oblivious value to public variable
    int y = x + 3;
    // ok
    OBLIV int z = x * 10;
    // error: cannot take oblivious value as control-flow condition
    if (x > 0) x = x - 1;
    // error: cannot take oblivious value as array subscript
    int *arr = new int[16]; int w = arr[x 

3.2 Obliviousness Levels↩︎

For a pointer, obliviousness has dual meanings: the pointer’s own value (which memory address it points to) and its dereferenced value (content at that address). With arbitrarily nested pointers in C++, this becomes increasingly complex.

We propose the concept of obliviousness level (olevel) to describe multi-level obliviousness. An expression’s olevel is a binary string where the \(i\)-th digit (counting from the right, starting from 0) represents the obliviousness after dereferencing it \(i\) times. An expression whose olevel ends with 1 is considered oblivious. In our discussion, an expression is less/more oblivious if its last olevel digit is less/more than another’s; an expression has no greater/smaller olevel if every digit of its olevel is no greater/smaller than the corresponding digit of another; “greater/smaller” is defined as the contrary of “no greater/smaller.”

Dataflow occurs with assignment expressions. To satisfy the dataflow property, we should not allow assigning an expression with another of a greater olevel. However, assignments with smaller olevel can also be dangerous. In 2, ppc of olevel``100 is assigned with &public_c of smaller olevel``0:

While assignments between different olevels appear unsafe, some cases with smaller olevels seem benign. For example, assigning a public value to a secret value, is clearly safe — we can not pass any secret information into public by this assignment. But when pointer nests get deeper, it is much less oblivious whether an assignment is safe.

  char public_c = 'p';
  [[obliv("1")]] char secret_c = 'x';
  [[obliv("10")]] char *pc = &secret_c;
  [[obliv("100")]] char **ppc = &pc;

  // if obliv("00") to obliv("10") is allowed
  *ppc = &public_c;
  *pc = secret_c;  // 'x' flows to public_c!

To determine permissible assignments, we must rigorously define our dataflow theorem. Undesired dataflow occurs when oblivious values flow into non-oblivious memory cells. Since we allow casting/assignments between different olevels, we must distinguish between the olevel embedded in the expression type and the actual olevel carried at runtime.

In C++, expressions are classified as lvalues (can be taken address and can appear on an assignment left side if not constant) or rvalues (cannot be taken address or appear on an assignment left side). Since every lvalue corresponds to a memory area, its “actual” olevel—the inherent olevel—is defined as the olevel of its corresponding memory allocation. For stack/static allocations, this is the olevel of the corresponding variable; for heap allocations, it is the olevel of the corresponding new expression.

We call lvalue expressions corresponding to memory allocations (local/global variables, dereferences of new expressions) primitive lvalues. Two lvalues can alias each other, meaning they correspond to the same memory area. In a well-formed program, every expression corresponds to allocated memory, thus aliasing with a primitive lvalue.

For rvalues, obliviousness depends on the operator and operands according to rules we will elaborate below. We do not define inherent olevel for rvalues, but for a pointer rvalue p, we can define the inherent olevel of *p since *p is a lvalue.

With these concepts, we formally describe 2 as two theorems:

Now we specify the olevel rules to satisfy 3. The danger in 2 occurs because an oblivious expression **ppc aliases with a non-oblivious expression public_c, but *ppc is not constant and can be assigned a secret value which flows to the non-oblivious public_c. To avoid this, we restrict “non-oblivious to oblivious” assignments by ensuring the ancestors in the pointer hierarchy are constant:

Intuitively, condition 2 in 6 prevents assigning oblivious values to non-oblivious targets, e.g., assigning an oblivious \(b\) to a non-oblivious \(a\). Condition 1 parallels C++’s implicit conversion rule for const-modifiers [27], preventing inherent-constant memory from being overwritten. When \(\texttt{const}(a\downarrow^{k}) = 0\) and \(\texttt{obliv}(a \downarrow^{k'}) \neq \texttt{obliv}(b \downarrow^{k'})\) for some \({k'} \geq k\), assigning an oblivious value to \(a \downarrow^{k'}\) would also assign it to the non-oblivious \(b \downarrow^{k'}\), violating the dataflow theorem.

We prove the soundness of 6 in 5.

To satisfy 4, we have:

These rules ensure the theorems stated earlier. Note that 6 7 8 replace their “basic” versions (2 1 3). The following example demonstrates how oblivious assignment rules work:

    // [[obliv]] is the abbreviation of [[obliv("1")]]
    [[obliv]] int x = 1;
    [[obliv("10")]] int *xp = &x;
    [[obliv("100")]] int **xpp = &xp;
    // error, 2nd digit of olevel differs
    [[obliv("110")]] int **ypp = xpp;
    // ok, 2nd level is constant
    [[obliv("110")]] int *const *const ypp = xpp;  
    // ok, the first level is passed by value
    [[obliv("101")]] int **ypp = xpp;        

3.3 Function Calls↩︎

Since callers typically only see function declarations in headers while their implications could exist in other translation units, obliviousness must be expressed in function signatures. We interpret function calls as series of assignments:

3.4 Classes↩︎

C++ classes (struct, union) declare compound types with methods, inheritance, and polymorphism, requiring additional rules:

By default, a member’s obliviousness inherits from the instance (olevel ending with "x"), analogous to C++’s const/mutable distinction. Virtual calls on oblivious polymorphic pointers are forbidden as the VPTR would be oblivious.

3.5 Templates↩︎

A single template could generate multiple instantiations. Since template parameters may carry olevel information (via function return values or parameters), obliv-clang checks each instantiation rather than the template declaration itself. This is straightforward as clang generates separate AST for each instantiation.

3.6 Unsafe Code Blocks↩︎

We provide the obliv_unsafe attribute to mark code blocks as unsafe, bypassing obliviousness checks. This approach, inspired by Rust’s unsafe keyword, is necessary in several cases:

• Inspecting internal secret values when debugging;

• Implementing subroutines whose obliviousness requires sophisticated mathematics beyond automatic checking (e.g., extracting public values from oblivious variables through encryption/hashing with secret keys, or asserting on execution paths that should not trigger);

• Working with third-party libraries whose implementations are in separate translation units invisible to the compiler.

Like Rust’s unsafe blocks, this feature indicates areas requiring special programmer attention and human auditing. We anticipate that in the future, more expressive semantics will reduce the need for unsafe blocks.

3.7 Known Limitations↩︎

When using external libraries, since the compiler can only see their header files, it cannot determine the obliviousness of external symbols unless we have the header file annotated with olevels. To use external libraries to process objects with olevels, the headers must be modified with appropriate annotations—an unavoidable effort for programmers. Fortunately, this typically only involves adding olevel annotations into the headers, a moderate burden.

Another limitation of obliv-clang involves function overloading. C++ allows multiple functions with the same name but different argument types, which will be given distinct mangled names during compilation. Since the olevel is not part of the C++ types, declaring overloaded functions with identical argument types but different olevels is prohibited unless the ABI encodes olevels in the mangled names. For external libraries supporting arguments with different olevels, multiple wrapper functions with different names may be required.

4 Implementation↩︎

obliv-clang is implemented in approximately 800 lines of C++ code. It registers an annotation handler to parse obliv-related annotations and a frontend plugin that executes after clang parses the source code into an AST. The plugin scans the AST and raises compilation errors for code violating our rules.

obliv-clang works like other clang plugins: it compiles into a dynamic library loaded during compilation, requiring only one additional compiler option to load the plugin. Our implementation targets a wide range of LLVM monorepo versions (tested on both LLVM 13 and LLVM 20). clang’s AST data structure remains relatively stable, so minimal maintenance is needed to support newer versions.

5 Soundness↩︎

In this section, we aim to prove the soundness of the obliv-clang design described in 3. That is to prove, if a program passes the check of obliv-clang according to all the rules specified in 3 (except 2 1 3 that have been replaced), it should be considered safe.

5.1 Execution Model↩︎

Before discussing the soundness, it is necessary to accurately specify well-defined semantics for programs. For C++, there is an ISO specification [27] curated by the C++ Standard Committee that stipulates the behaviors of C++ programs. In the specification, the available memory consists of one or more sequences of contiguous bytes. The behavior of a C++ program is described as creating, destroying, referring to, accessing, and manipulating objects. An object occupies a region of memory (maybe empty) within its lifetime. An object may contain other objects, called subobjects, in three forms: member subobjects, base class subobjects, and array subobjects. An object that is an array of unsigned char and std::byte can provide storage for other objects. The execution of a C++ program is interpreted as a sequence of expression evaluations. A list of rules are specified to define the relation between expressions and subexpressions and restrict the order of evaluations.

However, the specification only cares about “observable” effects, such as I/O and the final state, but leaves out the execution process that leads to the final state. Since we focus on analyzing the information leaked during the execution process, additional assumptions are required to specify these behaviors. Recall that the program execution is interpreted as a sequence of evaluations. Here, we classify the evaluation steps into the following categories:

• Create an object, implicitly or explicitly, which is evaluated on each object declaration. Note that this only includes the action of allocating memory and does not include initialization.

• Free an object, which terminates the lifetime of an object. Similarly, the execution of the destructor is not included.

• Read an object, which evaluates a reference to an object.

• Write an object, which evaluates an assignment to an object.

• Evaluate an expression, where the expression can be an operator expression, a function-call expression, an implicit/explicit casting expression, etc. All sub-components of the expression should be already evaluated. Note that all syntax sugars are desugared. For example, templates and overloading are resolved, operator expressions are resolved to the corresponding function calls if they are not built-in, and constructors and destructors of temporary objects are also resolved to the corresponding function calls.

For our purpose, we stipulate that any evaluation steps come with an evaluation trace. Two sequences of evaluation steps would produce the same evaluation trace if they (1) perform the same kind of operation; and (2) lie in the same memory position if the evaluation is creating, freeing, reading, or writing an object. Furthermore, we require that the evaluation order does not depend on the values of the operands. Recall that in C++, the evaluation order of operands is an unspecified behavior. For example, in an expression f(x) + g(y), the compiler can arbitrarily swap the order that f and g are executed. We also grant the compiler the freedom to choose the order, but it should not depend on the operand values.

We only consider programs with well-defined behaviors, i.e. without undefined behaviors (UBs). The C++ standard gives rigorous definitions of UBs, including pointer reinterpretation, out-of-bound memory accesses, pointer use-after-free, etc. The compilers do not give any guarantee for a program with UBs, and neither does obliv-clang. Fortunately, the functionality to detect UBs is already included in most C++ compilers and sanitizers [36], [37], so we can rely on them to report errors when encountering UBs.

5.2 Soundness Proof↩︎

To prove the soundness of our tool, we need to prove that any program that passes the check rules of obliv-clang should satisfy 1 3 4. It should be noticed that these theorems are independent. 1 prevents the secrets from being leaked via the execution trace; 3 prevents programmers from leaking the secrets “unexpectedly”; 4 prevents leaking the secrets with computations.

1 clearly holds. According to our C++ modeling, given the program content, the execution trace is solely determined by the values in the conditional clauses and the pointer dereferences (including array accesses). At the same time, all the values in conditional clauses and array indexing are public values, according to 5 8. Therefore, the execution trace can be simulated solely with public objects.

4 is guaranteed by the olevel deduction rule of C++ operators, described in 7.

The non-trivial part is 3. It requires knowledge about in which cases two lvalues can aliasing with each other. We first have the following lemma.

Now we can establish 3. Assume the contrary that there is an assignment \(a \stackrel{t}{\gets} b\) where \(b\) is an oblivious expression, and \(a\) is aliasing with a non-oblivious expression \(a'\). According to ?? in 6, \(a\) must be oblivious because it is assigned with an oblivious expression \(b\). Now that \(a\) is assigned, it cannot be constant. According to 1, \(\texttt{obliv}(a') \geq \texttt{obliv}(a)\), hence \(a'\) is also oblivious, leading to a contradiction. The proof of 3 is complete.

6 Compiler Optimization Suppression↩︎

Modern compilers perform aggressive performance optimizations that reorganize program structures. While obliv-clang ensures obliviousness at the AST level, the LLVM optimizer may apply transformations that undermine these guarantees.

Consider this example from [38]:

    // Select an element from an array in constant time
    uint64_t constant_time_lookup(
            const size_t secret_idx, const uint64_t table[16]) {
        uint64_t result = 0;
        for (size_t i = 0; i < 16; i++) {
            const bool cond = i == secret_idx;
            const uint64_t mask = (-(int64_t)cond);
            result |= table[i] & mask;
        }
        return result;
    }

This function uses bit operations to extract table[secret_idx], without revealing secret_idx through side channels. However, LLVM’s optimizer can detect this pattern and bypass the protection. When compiled with clang 21.1.0 targeting x86-64 Linux using -O3 -fno-unroll-loops -fno-vectorize, the compiler generates a branch depending on whether i equals to secret_idx, allowing attackers to learn information about secret_idx by observing control flow, violating the intended obliviousness.

This issue arises because current compiler optimizers prioritize correctness without considering obliviousness. Reconstructing LLVM to be obliviousness-aware would require enormous engineering effort. Instead, we adopt a simpler approach. When our plugin loads, it disables optimization passes that could produce unsafe changes. We manually inspected all clang optimization passes to determine their safety. Here is the list: ReassociatePass, LoopInstSimplifyPass, LoopSimplifyCFGPass, LoopRotatePass, IndVarSimplifyPass, LoopDeletionPass, LoopInterchangePass, LoopFlattenPass, X86CmovConverterPass.

However, this approach is imperfect. On one hand, by disabling compiler optimization passes, there may be negative performance impact in the resultant code. On the other hand, manual inspection may not discover all relevant passes that need to be disabled, potentially leaving security vulnerabilities.

For the performance impact, we evaluate the impact in [sec:eval:optim-perf] using representative programs. We find there will be only minor slowdown for most programs, and moderate performance degradation (up to 30%) for complex cases. We regard such slowdown as unavoidable cost to achieve security, and believe the small overheads are acceptable in reality.

For stronger security guarantees, we provide an extra double-check step in our tool. With this step enabled, obliv-clang applies rigorous obliviousness verification to the generated assembly code using existing tools. Our current implementation uses pitchfork [21]. If the verification fails, the compiler falls back to recompile the translation unit with the failed functions, using the optnone (no optimization) option to avoid any problematic compiler optimizations.

7 Evaluation↩︎

In this section, we evaluate obliv-clang from two aspects in order to show that obliv-clang(1) is sufficiently expressive and flexible to support non-trivial oblivious algorithm implementations; (2) has minor overheads during compilation and leads to good performance for the compiled programs.

7.1 Case Studies↩︎

To demonstrate the expressiveness of obliv-clang, we have implemented several oblivious algorithms in C++ and used obliv-clang to process them. All the implementations can successfully pass the check of obliv-clang.

PathORAM ORAM is a type of protocol that provides an array-like random access interface but keeps all addresses, data, and operations (read or write) oblivious. It is a useful and general primitive since random array access is a frequently used programming pattern. PathORAM [22] is a simple and efficient ORAM implementation with \(O(\log^3 N)\) time overhead for each access, where \(N\) is the array length.

To show obliv-clang’s expressiveness, we write a non-recursive local version of PathORAM, 251 lines of code (LOCs). The implementation is wrapped in a template class with the following public interface:

    #define OBLIV [[obliv]]
    #define OBLIV_PTR [[obliv("10")]]

    template<typename DataType>
    class PathORAM {
    public:
        PathORAM(size_t N, size_t stashLen);
        ~PathORAM();
        DataType Access(OBLIV AddrType addr, OBLIV DataType data, OBLIV bool isWrite);
    }

In writing oblivious algorithms, cmove is a key utility that obliviously copies bytes based on a condition. We implement it via bit operations for cross-platform compatibility.

    template <typename T>
    void cmove(OBLIV bool cond, OBLIV_PTR const T *src, OBLIV_PTR T *dst);

The tricky part is handling PathORAM’s position map structure. Recall that PathORAM stores data in a binary tree, where each data element is assigned with an position corresponding to a path in the binary tree. On each access to PathORAM, the position corresponding to the accessed address is read out, and then re-assigned to a freshly sampled random value. The map between data logical addresses and tree path positions, namely the position map, is either stored in an array and accessed with brute-force scanning, or stored in another smaller PathORAM recursively. The content of the position map should be annotated as secret since an attacker aware of the position map can infer the address being accessed from the memory trace. However, when a position is read out from the position map, it should become a public value since it is used to access memory later. To bridge the gap, we should wrap the subroutine of accessing the position map with an unsafe block as below. The security here is guaranteed by the PathORAM theory beyond simple oblivious accesses.

template<typename DataType>
AddrType PathORAM<DataType>::accessPosMap(OBLIV size_t addr, OBLIV size_t data) {
    OBLIV_UNSAFE { /* return the position and insert random value */ }
}

In our current implementation, there are some other uses of unsafe blocks, but they could be optionally removed. One usage is the assertion of failure. PathORAM is proved to fail with a negligible probability under properly chosen parameters. An assertion can be used to abort the program when it fails. However, since the failure would expose secret information, the assertion code should be wrapped in an unsafe block. Another usage is the call of library functions, such as std::memcpy, which can be avoided with hand-written counterparts but with inferior performance.

Oblivious BFS Oblivious BFS [23] performs BFS traversals such that an attacker cannot learn the graph structure from the execution trace. It shuffles the graph randomly and chooses each next vertex with equal probability. Our implementation uses 158 LOCs.

Real-World Cryptographic Vulnerabilities

CVE-2024-13176 (the Minerva attack) is a timing side channel in OpenSSL’s ECDSA implementation: a \(\sim\) 300 ns timing signal leaks when the top word of the inverted nonce is zero, allowing private key recovery on NIST P-521. The vulnerability occurs in ec_field_inverse_mod_ord(), which computes \(k^{-1}\) using BN_mod_exp_mont().

The root cause was flawed developer reasoning. The original code commented: “Exponent \(e\) is public. No need for constant-time protection.” While OpenSSL’s BN_FLG_CONSTTIME flag protects the exponent, it ignores the secret base \(x\) (the nonce) and secret result \(r\) (the nonce inverse). The leak came from result normalization via bn_correct_top(), which adjusts bignum word count based on the actual value.

With obliv-clang, this flaw is caught automatically:

int BN_mod_exp_mont(BIGNUM *r, const BIGNUM *a, const BIGNUM *p,
                    const BIGNUM *m, BN_CTX *ctx, BN_MONT_CTX *m_ctx);
static int ec_field_inverse_mod_ord(const EC_GROUP *group,
        OBLIV_PTR BIGNUM *r, OBLIV_PTR const BIGNUM *x, BN_CTX *ctx) {
    if (!BN_mod_exp_mont(r, x, ...))  // ERROR: OBLIV_PTR to non-OBLIV_PTR
        goto err;
}

obliv-clang’s explicit dataflow tracking catches secret values flowing into unannotated functions, demonstrating robustness over naming conventions alone.

Others We have also tested obliv-clang on several other algorithms, including oblivious shuffle [39] and tree-based data structures [24]. We also write some standard library wrappers to assist in using standard libraries. The adoption of these programs is straightforward. The only requirement is to mark variables and function parameters with appropriate olevels.

To quantify the migration effort, we measure the LOCs requiring [[obliv]] annotations compared to the total LOCs. For example, we annotated 32 out of 190 LOCs in PathORAM, 10 out of 94 LOCs in Oblivious BFS, and 25 out of 311 LOCs in Poly1305 (see later). This demonstrates that the annotation burden is modest — typically just 8% to 17% of the codebase requires modifications, and these modifications are localized to variable declarations and function signatures involving secret data.

7.2 Performance↩︎

In the following experiments, we evaluate the performance of obliv-clang from three aspects. First, we demonstrate that the check in obliv-clang introduces minor overheads to the compilation time. Second, we justify that the compiler optimization suppression in obliv-clang does not significantly degrade the performance of the compiled program. Finally, we compare obliv-clang with prior solutions to oblivious programming and show its superior performance.

All experiments use an Intel Xeon Gold 5218R machine with 256 GB DDR4 memory, running Ubuntu 22.04. Single-threaded programs are compiled with clang 13.0.1 at -O3; with obliv-clang, optimization passes mentioned in 6 are disabled.

Compilation Overheads We evaluate compilation overheads on five benchmarks: PathORAM (251 LOCs, [sec:eval:expr:pathoram]), Oblivious BFS (251 LOCs, [sec:eval:expr:obfs]), tiny_jpeg (1306 LOCs, JPEG encoding) [40], monocypher (3277 LOCs, cryptography library) [41], and sqlite3 (250815 LOCs) [42].

All these programs are compiled (but not linked) with and without our obliv-clang plugin. The compilation time slowdown results are shown in 1. We take the average time of 10 runs after 3 warm-up runs. When not enabling the extra double-check step (6), the compilation time overheads are less than 11% for all test cases. Even with the double-check, there are less than 18% overheads. Among different test cases, the overheads are smaller for large programs, in which the cost is dwarfed by that of other compilation actions. Therefore, obliv-clang is particularly suitable for real-world complex oblivious programs.

Optimization Suppression Overheads We measure execution time with and without suppression on: PathORAM with randomly generated operations on size \(2^{20}\), Oblivious BFS on a 4096-node graph, tiny_jpeg encoding a \(1000\times 1000\) image, and lz4 [43] with compression level 3. [tab:overhead-optim-suppression] shows the results. Most benchmarks see negligible slowdown, with lz4 even slightly faster. PathORAM slows down by 29.5%, likely because the suppressed passes could reorganize its loops for better performance.

Runtime Performance Comparison Researchers have proposed some other solutions providing oblivious programming utilities. 8 summarizes these designs in great details. Compared with previous solutions, obliv-clang directly uses the middle-end and backend provided by the mature and heavily optimized clang and LLVM frameworks, thus achieving superior performance in most cases.

To demonstrate the performance advantages, we consider the following two competitors. FaCT [12] is a domain-specific language (DSL) that verifies and transforms the obliviousness of source code. It translates the source code into the LLVM IR and relies on clang to compile to object files. Jasmin [13] is also a DSL that ensures the constant-time property. It has a formally verified frontend, optimizer, and codegen in order to translate source code into assembly files.

We evaluate the performance of the above tools and obliv-clang on six algorithms: AES128, poly1305 (one-time authentication), salsa20 (stream cipher), secretbox (authenticated encryption), siphash (pseudorandom function [44]), and PathORAM (block eviction logic). For the first three cryptogrpahic algorithms, the Jasmin implementation is from libjade [45], a cryptography library providing libsodium-like interfaces written in Jasmin. The implementations in obliv-clang and FaCT are directly translated from the implementation of libsodium [46], except that the implementation of poly1305 in obliv-clang is translated from libjade. The implemtations of siphash and PathORAM are all hand-written that take identical control flow and operations. All these algorithms are used to process a 4096-byte message, and we measured the average execution time.

During the implementation, we found that both FaCT and Jasmin are lacking some usability features currently. For example, FaCT has no loop clauses other than ranged for loops over contingent integers; Jasmin requires manually allocating local variables to registers or the stack. Both of them cannot handle type conversion from boolean values to integers easily, and the compiler error messages are quite vague and hard to locate. These deficiencies make writing complicated programs on them difficult, if not impossible. Therefore, our comparison in this part is limited to a few simple microbenchmarks.

The evaluation results are shown in 2. Among these test cases, obliv-clang is 27.8% faster than Jasmin and 66.9% faster than FaCT on average. For poly1305, the obliv-clang implementation is 29.8% slower than Jasmin. The reason might be that the main body of poly1305 calculation is 128-bit integer arithmetic, and the code generation of 128-bit arithmetic in Jasmin is more optimized.

8 Related Work↩︎

Researchers have proposed several DSLs that provide compile-time obliviousness guarantees. Jasmin [13] targets constant-time cryptographic code: programmers annotate secret variables and supply loop invariants, and the compiler uses formal verification tools to check constant-time behavior and invariants; importantly, it offers a fully verified end-to-end compilation flow. ObliVM [16] includes a language and compiler that not only checks behaviors but also enforces control-flow obliviousness by transforming programs and inserting dummy operations for secret-dependent branches; it also introduces an rnd type that restricts use before declassification, but this alone cannot ensure strict security (e.g., it cannot prevent nonce reuse across multiple encryptions). Obliv-c [17] extends C by adapting the CIL frontend to translate obliv-c into C, but supports only single-level obliviousness, making it insufficiently expressive for real-world programs, and its rules lack formal security analysis. FaCT [12] generates constant-time code via more aggressive control-flow transformations than ObliVM, automatically rewriting all if statements and range-based for loops.

Other prior works focus on checks or transformations on IRs or binaries. ObliCheck [19] focuses solely on static analysis of memory trace obliviousness, not control-flow obliviousness. Recognizing that previous taint analysis methods were too coarse-grained for accurate checking, ObliCheck employs symbolic execution with sophisticated state merging to accelerate its verification. Raccoon [9] transforms compiled LLVM IR from C source code, obfuscating non-oblivious memory operations using cmove instructions to hide dependencies on secret information. Constantine [47] performas IR-level transformation that lineraizes control flow, with support of JIT transformations and advanced optimizations.

Some works handles a more relaxed model. Liu et al. [11] take a different approach, separating variables into ORAM banks based on access patterns, and leveraging the ORAM properties to achieve oblivious memory accesses. EncLang [14] addresses page-table attacks by making page access patterns oblivious through data layout and memory access rearrangement during machine code generation.

Our obliv-clang makes several contributions compared to previous designs:

First, we develop semantics for oblivious programming in a modern industry-standard language, supporting important features that previous oblivious DSLs failed to address, including nested references/pointers, compound types, function parameter passing, and templates.

Second, we propose a workflow requiring minimal modification to existing codebases and toolchains while reliably creating oblivious programs. Programmers need only add necessary annotations and compiler options. The workflow flexibly accommodates structures that cannot be automatically checked, with annotations clearly indicating which program parts require manual auditing.

Third, our evaluation shows that obliv-clang adds negligible compilation overhead, and our optimization suppression approach has minimal performance impact. Leveraging LLVM and clang’s mature ecosystem, our implementations of oblivious algorithms achieve better performance compared to previous tools.

9 Conclusion↩︎

We present obliv-clang, a compiler plugin for the C++ language that performs static checks for oblivious programming. It is specifically implemented using the clang and LLVM infrastructures. Compared to previous work, obliv-clang aims to provide natural semantics and maximum compatibility with widely used industry-level programming languages and workflow while being able to provide a verifiable soundness guarantee even in the presence of complex language features. Our experiments show that obliv-clang leads to low compilation overheads and can achieve better performance on the compiled oblivious programs compared to previous tools.

References↩︎