obliv-clang: Real-World Oblivious Programming in C++ (Extended Version) Yunqian Luo1[0009−0000−3366−3722] and Mingyu Gao1,2[0000−0001−8433−7281]
arXiv:2606.16187v1 [cs.PL] 15 Jun 2026
1
2
Tsinghua University, Beijing, China Shanghai Qi Zhi Institute, Shanghai, China
[email protected], [email protected]
Abstract. Side-channel vulnerabilities, particularly timing and accesspattern-based attacks, have become critical issues for confidential data processing in trusted environments. Oblivious programming is an effective approach to alleviate these attacks by making program execution not leak any secret through execution time and data access traces. To facilitate oblivious programming in practice, we propose a compilation-time checking tool, obliv-clang, which can comprehensively check the obliviousness of a program written in C++. It is designed to support the rich language features in C++, including the complicated concept of arbitrarily nested pointers, in order to seamlessly work with existing industry-level codebases and produce high-performance compiled binaries with minimum compilation overheads. We design a set of rules in obliv-clang and formally prove their soundness in the presence of complicated C++ language features. We also implement several non-trivial oblivious algorithms as case studies to demonstrate the expressiveness of obliv-clang, and show that programs compiled using obliv-clang can outperform previous solutions. Keywords: Compiler · Trusted Execution Environment · Oblivious Programming
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.
2
Yunqian Luo and Mingyu Gao
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 [15], OS-controlled page tables [6,32], hardware branch predictors [18], speculative execution [42], 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 [11, 17, 21, 29, 44], or using software techniques [1, 7, 22, 24, 27, 32, 34]. 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 [7,23,24,45] 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 [35, 47] 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 [29, 34] 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
obliv-clang: Real-World Oblivious Programming in C++
3
minimum porting effort, eliminating the extra burden of using a new domainspecific 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 Example 2 in Section 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 [12], which ensure end-to-end obliviousness. We have implemented several non-trivial oblivious algorithms, including PathORAM [39] and Oblivious BFS [4], 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 [1] and 66.9% faster than FaCT [7] on average. The implementation of obliv-clang has been open sourced at github.com/tsinghuaideal/obliv-clang. Our contributions in this paper are summarized below: – The design and implementation of a program obliviousness check tool, oblivclang, 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. Section 2 provides background and discusses prior tools’ limitations. Sections 3 and 4 present our design and
4
Yunqian Luo and Mingyu Gao
describe implementation details. Section 5 gives the soundness proof. Section 6 discusses how to suppress backend optimization passes to avoid break obliviousness. Section 7 illustrates several case studies and evaluates our design. Section 8 discusses related work and Section 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 (Section 2.1), and then discuss the limitations of existing approaches to motivate our work (Section 2.2). We next describe our high-level approach and summarize the key challenges (Section 2.3). Lastly, we specify our security model by formally defining properties that oblivious programs must satisfy (Section 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 [6, 15, 32]. 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 [39], oblivious BFS [4], and oblivious data structures [43]. 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 [1, 30, 35], while others actively transform programs to hide non-oblivious branches and memory accesses [7,22,24,29,33,34]. 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 [7, 22, 34, 35], while others work on low-level intermediate representations (IRs), particularly LLVM IR, in the backend [29, 33]. Frontend approaches preserve more source code information, facilitating high-level analysis to achieve
obliv-clang: Real-World Oblivious Programming in C++
5
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 [40], 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 [9,10], 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 (Section 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 [2]. 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 Section 3 addresses these challenges.
6
Yunqian Luo and Mingyu Gao
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 [15], and page-table [6, 32] 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 [20], electromagnetism [31], speculative execution [42], rowhammer [16], 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 [36, 46]. To ensure security under these assumptions, programs must satisfy the following properties in Theorems 1 and 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 Section 3. Theorem 1 (Secrecy). For a program P with no undefined behaviors, and any external input x, let vpub (x) be the set of values of its public objects during execution, Trace(P, x) be the execution trace. There exists a probabilistic polynomial time (p.p.t.) simulator Simu such that no p.p.t. adversary A can distinguish Trace(P, x) and Simu(vpub (x)). Formally: ∀x, Pr[ A(vpub (x), Trace(P, x)) ] − Pr[ A(vpub (x), Simu(vpub )) ] < ϵ(n),
(1)
where n is a security parameter, and ϵ is a negligible function. Theorem 2 (Dataflow (informal)). There is no data flow from secret objects to public objects.
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, oblivclang’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.
obliv-clang: Real-World Oblivious Programming in C++
3.1
7
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. oblivclang requires secret variables to be annotated with the custom obliv attribute. C++ specifications allow compilers to define custom attributes as language extensions [40, Chapter 9.12], 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 (Section 4). To satisfy the Secrecy and Dataflow properties from Section 2.4, the following rules are required: Rule 1 (Basic Arithmetic) Any expression depending on an oblivious object is also oblivious. Note that we only consider value dependencies; comma expressions, compilation-time constant expressions (e.g., sizeof, alignof), and take-address operations are not considered dependencies. Rule 2 (Basic Casting) It is forbidden to cast an oblivious expression to a non-oblivious expression. Rule 3 (Basic Dereference) It is forbidden to dereference an oblivious pointer. Similarly, it is forbidden to take an oblivious object as the base address or index in an array subscript expression. Rule 4 (Allocation) It is forbidden to create an object whose size is oblivious (e.g., new[] with oblivious length). Rule 5 (Condition) The condition in any conditional clause (if, while, for, switch, ternary expressions, short-circuit boolean expressions) must not be an oblivious expression. Note that “cast” in Rule 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: Example 1. #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
8
Yunqian Luo and Mingyu Gao
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 % 16];
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 multilevel 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 Example 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. Example 2. 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
obliv-clang: Real-World Oblivious Programming in C++
9
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 Theorem 2 as two theorems: Theorem 3 (Dataflow of Assignment). There is no execution of an assignment statement whose assignee (which must be an lvalue) is aliasing a nonoblivious lvalue, but the assigner is an oblivious value. Theorem 4 (Dataflow of Value Dependency). An expression whose value depends on oblivious values is also oblivious. Notation 41 We use the notations below for convenience: – For an lvalue x and a non-negative integer k, denote by x ↓k the expression obtained by indirecting x by k times. In other words, x ↓0 is x, and x ↓k+1 is *(x ↓k ). Similarly, we denote by x ↑k the expression obtained by takingaddress (i.e., the unary & operator) on x by k times. – For two lvalues x, y and time t, if at time t, the expressions x and y correspond to the same memory cell, we say that x and y are aliased at t, denoted t by x ∼ y. The superscript t may be omitted when the context is clear. t – For an lvalue x, an expression e, and time t, denote by x ← e that x is assigned with e at time t (may come with an implicit casting). Similarly, t may be omitted. – For an expression x, denote by const(x) and obliv(x) its obliviousness and constantness, whose value is either 0 or 1. Now we specify the olevel rules to satisfy Theorem 3. The danger in Example 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 “nonoblivious to oblivious” assignments by ensuring the ancestors in the pointer hierarchy are constant: Rule 6 (Casting) Consider two expressions, a and b. b can be implicitly cast to a if and only if, in addition to C++’s cast rules, the following oblivious cast rules hold:
10
Yunqian Luo and Mingyu Gao
1. For a k > 0, if const(a ↓k ) = 0, for any k ′ ≥ k, ′
′
k′
k′
const(a ↓k ) = const(b ↓k )
(2)
obliv(a ↓ ) = obliv(b ↓ ).
(3)
obliv(a ↓k ) ≥ obliv(b ↓k ).
(4)
2. For any k ≥ 0,
For an assignment a ← b, if a is a reference type, the assignment is allowed when b can be implicitly converted to the olevel and type of a according to the above casting rules. If a is a value type, b only needs to be converted to the olevel and type of constant a, i.e., with const(a) set to 1 but other olevel and type unchanged. Intuitively, condition 2 in Rule 6 prevents assigning oblivious values to nonoblivious targets, e.g., assigning an oblivious b to a non-oblivious a. Condition 1 parallels C++’s implicit conversion rule for const-modifiers [40, Chapter 7.3.6], preventing inherent-constant memory from being overwritten. When const(a ↓k ′ ′ ) = 0 and obliv(a ↓k ) ̸= obliv(b ↓k ) for some k ′ ≥ k, assigning an oblivious ′ ′ value to a ↓k would also assign it to the non-oblivious b ↓k , violating the dataflow theorem. We prove the soundness of Rule 6 in Section 5. To satisfy Theorem 4, we have: Rule 7 (Arithmetic) For an arithmetic operator expression, if any operands are oblivious, the total expression is also oblivious. Note that we only consider arithmetic expressions; comma expressions, compilation-time constant expressions (e.g., sizeof, alignof), and pointer reference/dereference operators are not considered dependencies. Rule 8 (Dereference) It is forbidden to dereference an oblivious pointer (the array indexing expression p[i] is interpreted as *(p + i)). The result of a dereference operator shifts the olevel right by one digit, while the result of a take-address operator shifts the olevel left by one digit. Rule 9 (Pointer Arithmetic) For the arithmetic of pointers, the only allowed type is the addition of a pointer p and an integer i (including the equivalent &p[i]). The 0th digit of the result olevel is the logical-OR of the operands’ obliviousnesses, and the remaining digits are the same as p. These rules ensure the theorems stated earlier. Note that Rules 6 to 8 replace their “basic” versions (Rules 1 to 3). The following example demonstrates how oblivious assignment rules work: Example 3.
obliv-clang: Real-World Oblivious Programming in C++
11
// [[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: Rule 10 (Function Call) When checking a function, the following rules should be enforced: 1. Each parameter of a function can be annotated with an olevel. 2. When checking the function body, the parameters are treated as variables with their annotated olevels. 3. The function itself can be annotated with an olevel, which indicates the olevel of its return value. 4. When checking the function body, every expression returned in a return statement should be able to be cast to the annotated olevel of the function, according to Rule 6. 5. When calling a function, for each parameter, the given argument should be able to be cast to the olevel of the declared parameter, according to Rule 6. 3.4
Classes
C++ classes (struct, union) declare compound types with methods, inheritance, and polymorphism, requiring additional rules: Rule 11 (Class) For a class type (struct and union types also included), the following rules are enforced: 1. In the declaration of a class type, its members can be annotated with an olevel. The difference from a normal olevel declaration is that the last digit of class member olevel can be "x" besides 0 and 1. If not specified, a class member has an "x" olevel. 2. In a class member access expression (e.g., c.member or c->member), if the olevel of the member declaration ends with "x", the olevel of the expression is the olevel of the member declaration with the last digit changed to the olevel of the class instance (c or *c). Otherwise the olevel of the expression is the same as the member declaration.
12
Yunqian Luo and Mingyu Gao
3. A method can be annotated with obliv this. In the presence of this annotation, this is interpreted as a pointer to an oblivious instance. An oblivious instance can only call obliv this methods. A public instance can call all methods. 4. When a method is overridden during inheritance, the olevel annotations should be identical to the annotations in the original declaration. 5. Virtual methods should not be called from a pointer to an oblivious polymorphic pointer. 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
obliv-clang: Real-World Oblivious Programming in C++
13
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 Section 3. That is to prove, if a program passes the check of obliv-clang according to all the rules specified in Section 3 (except Rules 1 to 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 [40] 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:
14
Yunqian Luo and Mingyu Gao
– 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 useafter-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 [8, 25], 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 Theorems 1, 3 and 4. It should be noticed that these theorems are independent. Theorem 1 prevents the secrets from being leaked via the execution trace; Theorem 3 prevents programmers from leaking the secrets “unexpectedly”; Theorem 4 prevents leaking the secrets with computations. Theorem 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 Rules 5 and 8. Therefore, the execution trace can be simulated solely with public objects.
obliv-clang: Real-World Oblivious Programming in C++
15
Theorem 4 is guaranteed by the olevel deduction rule of C++ operators, described in Rule 7. The non-trivial part is Theorem 3. It requires knowledge about in which cases two lvalues can aliasing with each other. We first have the following lemma. Lemma 1. For any expression a, denote by K(a) the minimum positive integer t k such that const(a ↓k ) = 0 (let K(a) = +∞ if such k does not exist). If a ∼ b, and b is a primitive expression, then at time t, ( ′ ′ const(a ↓k ) = const(b ↓k ) ′ (5) ∀ k ≥ K(a), ′ ′ obliv(a ↓k ) = obliv(b ↓k ), ∀ k ′ ≥ 0,
′
′
obliv(a ↓k ) ≥ obliv(b ↓k )
(6) ′
Note that the above relations imply that for any k ′ ≥ 0, const(a ↓k ) ≥ ′ const(b ↓k ) t
Proof. Assume there exist some tuples (a, b, t) such that a ∼ b, b is primitive, but K(a) does not satisfy the relations in the lemma. Among all such tuples, pick the tuple (a, b, t) with the minimum t. Clearly a ̸= b, otherwise for any ′ ′ ′ ′ k ′ ≥ 0, const(a ↓k ) = const(b ↓k ) and also obliv(a ↓k ) = obliv(b ↓k ). The lemma is satisfied. Notice that the relations given by the lemma only depend on the types of a and b, so these relations do not vary by time given a and b, and they also do not hold at time t′ = t − 1. But since t is the minimum time that the lemma fails, the only possibility is that at time t′ , the precondition does not hold, i.e., t′
we have a ∼ ̸ b, and an assignment transforms non-aliasing a and b into aliasing. For this to happen, there exist some expressions c and d, such that at time t′ for some k > 0 t′
c ← d,
t′
a ↑k ∼ c,
t′
d ↓k ∼ b
(7)
t′
Because a ↑k ∼ c, there exists some primitive p such that t′
a ↑k ∼ p
(8)
t′
c∼p
(9)
Since t is the minimum time that the lemma fails for any tuple (a, b, t), at time t′ , K(a ↑k ) and K(c) satisfy the lemma. According to (8) we have ( ′ ′ const(a ↓k −k ) = const(p ↓k ) ′ k ∀ k ≥ K(a ↑ ), (10) ′ ′ obliv(a ↓k −k ) = obliv(p ↓k ), ′
′
∀ k ′ ≥ 0, obliv(a ↓k −k ) ≥ obliv(p ↓k )
(11)
16
Yunqian Luo and Mingyu Gao
We rewrite (10) into ( ′
k
∀ k ≥ K(a ↑ ) − k,
′
′
const(a ↓k ) = const(p ↓k +k ) ′ ′ obliv(a ↓k ) = obliv(p ↓k +k )
(12)
Since c is assigned with d, c is not constant, i.e. K(c) = 0. According to (9) we have ( ′ ′ const(c ↓k ) = const(p ↓k ) ′ (13) ∀ k ≥ 0, ′ ′ obliv(c ↓k ) = obliv(p ↓k ) t′
Similarly, since d ↓k ∼ b and b is primitive, ( ′ ′ const(d ↓k+k ) = const(b ↓k ) ′ k ∀ k ≥ K(d ↓ ), ′ ′ obliv(d ↓k+k ) = obliv(b ↓k ), ′
(14)
′
∀ k ′ ≥ 0, obliv(d ↓k+k ) ≥ obliv(b ↓k )
(15) t′
Consider the implicit conversion during the assignment c ← d. According 1 to the rule of assignment (Rule 6), and notice that const(c ↓K(c↓ )+1 ) = 0 by definition, we have ( ′ ′ const(c ↓k ) = const(d ↓k ) ′ 1 ∀ k ≥ K(c ↓ )+1, (16) ′ ′ obliv(c ↓k ) = obliv(d ↓k ), ′
′
∀ k ′ ≥ 0, obliv(c ↓k ) ≥ obliv(d ↓k )
(17)
We rewrite (16) into ( ′
1
∀ k ≥ K(c ↓ ) − (k − 1),
′
′
const(c ↓k +k ) = const(d ↓k +k ) ′ ′ obliv(c ↓k +k ) = obliv(d ↓k +k )
(18)
Letting k ′ = 1 + K(c ↓1 ) in (16), we have 1
1
const(d ↓1+K(c↓ ) ) = const(c ↓1+K(c↓ ) ) = 0.
(19)
K(d ↓1 ) ≤ K(c ↓1 )
(20)
Hence
Similarly letting k ′ = K(c ↓k ) in (18), we have K(c ↓k ) ≥ K(d ↓k ).
(21)
K(a) ≥ K(a ↑k ) − k.
(22)
We know that
obliv-clang: Real-World Oblivious Programming in C++
17
For any k ′ ≥ 0, ′
′
const(a ↓k ) ≥ const(p ↓k+k ) k+k′
= const(c ↓
(23)
)
by (13)
(24)
The inequality in (23) holds because, when k ′ ≥ K(a ↑k ) − k, the two sides are equal by (12); when k ′ < K(a ↑k ) − k ≤ K(a), the left side is always 1 by the definition of K(a). Hence by letting k ′ = K(a) in (24), we have K(a) ≥ K(c ↓k ) ≥ K(c ↓1 ) − (k − 1)
(25)
And also K(a) ≥ K(c ↓k ) ≥ K(d ↓k )
by (21)
(26)
by (12) and (22)
(27)
by (13)
(28)
by (18) and (25)
(29)
by (14) and (26)
(30)
′
Now for any k ≥ K(a), ′
′
obliv(a ↓k ) = obliv(p ↓k+k ) ′
= obliv(c ↓k+k ) k+k′
= obliv(d ↓
)
k′
= obliv(b ↓ ) Similarly for any k ′ ≥ K(a), ′
′
const(a ↓k ) = const(c ↓k )
(31)
For any k ′ ≥ 0, ′
′
obliv(a ↓k ) ≥ obliv(p ↓k+k ) ′
= obliv(c ↓k+k ) k+k′
≥ obliv(d ↓
k′
≥ obliv(b ↓ )
)
by (11)
(32)
by (13)
(33)
by (17)
(34)
by (15)
(35)
Therefore a and b satisfy the relations in the lemma, leading to a contradiction. t
Corollary 1. If a ∼ b and b is not constant, then obliv(a) ≥ obliv(b). t
Proof. Since a ∼ b, assume a and b are aliasing with a common primitive p. Since b is not constant, K(b) = 0. According to Lemma 1, obliv(b) = obliv(p) and obliv(a) ≥ obliv(p). Hence obliv(a) ≥ obliv(b). Now we can establish Theorem 3. Assume the contrary that there is an t assignment a ← b where b is an oblivious expression, and a is aliasing with a non-oblivious expression a′ . According to (4) in Rule 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 Corollary 1, obliv(a′ ) ≥ obliv(a), hence a′ is also oblivious, leading to a contradiction. The proof of Theorem 3 is complete.
18
6
Yunqian Luo and Mingyu Gao
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 [37]: // 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 obliviousnessaware 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 Section 7.2 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 [12]. 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.
obliv-clang: Real-World Oblivious Programming in C++
7
19
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 [39] is a simple and efficient ORAM implementation with O(log3 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
20
Yunqian Luo and Mingyu Gao
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 [4] 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 ∼ 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 [28] and tree-based data structures [43]. 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
obliv-clang: Real-World Oblivious Programming in C++
21
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 Section 6 are disabled. Compilation Overheads We evaluate compilation overheads on five benchmarks: PathORAM (251 LOCs, Section 7.1), Oblivious BFS (251 LOCs, Section 7.1), tiny jpeg (1306 LOCs, JPEG encoding) [14], monocypher (3277 LOCs, cryptography library) [41], and sqlite3 (250815 LOCs) [38]. All these programs are compiled (but not linked) with and without our oblivclang plugin. The compilation time slowdown results are shown in Fig. 1a. We take the average time of 10 runs after 3 warm-up runs. When not enabling the extra double-check step (Section 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.
Slowdown (%)
PathORAM moncypher
Oblivious BFS sqlite3
tiny jpeg Testcase PathORAM Oblivious BFS tiny jpeg lz4
15 10 5 0 W/o Double-Check W/ Double-Check
Slowdown 29.5% 0.91% 1.27% −2.72%
(b) Optimization suppression overheads.
(a) Compilation time overheads.
Fig. 1: Overheads from compilation process and optimization suppression.
22
Yunqian Luo and Mingyu Gao
Optimization Suppression Overheads We measure execution time with and without suppression on: PathORAM with randomly generated operations on size 220 , Oblivious BFS on a 4096-node graph, tiny jpeg encoding a 1000 × 1000 image, and lz4 [26] with compression level 3. Fig. 1b 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. Section 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 [7] 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 [1] 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 [3]), and PathORAM (block eviction logic). For the first three cryptogrpahic algorithms, the Jasmin implementation is from libjade [13], 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 [19], 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 Fig. 2. Among these test cases, oblivclang 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.
Normalized Time
obliv-clang: Real-World Oblivious Programming in C++ 8
23
obliv-clang Jasmin FaCT
6 4 2 1 0 AES128 poly1305 salsa20 secretbox siphashPathORAM
Fig. 2: Performance comparison of oblivious programs using different tools.
8
Related Work
Researchers have proposed several DSLs that provide compile-time obliviousness guarantees. Jasmin [1] 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 [24] includes a language and compiler that not only checks behaviors but also enforces controlflow 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 [45] extends C by adapting the CIL frontend to translate obliv-c into C, but supports only singlelevel obliviousness, making it insufficiently expressive for real-world programs, and its rules lack formal security analysis. FaCT [7] 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 [35] 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 [29] transforms compiled LLVM IR from C source code, obfuscating nonoblivious memory operations using cmove instructions to hide dependencies on secret information. Constantine [5] 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. [22] take a different approach, separating variables into ORAM banks based on access patterns, and leveraging the ORAM properties to achieve oblivious memory accesses. EncLang [34] 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:
24
Yunqian Luo and Mingyu Gao
First, we develop semantics for oblivious programming in a modern industrystandard 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. Acknowledgments. The authors thank the anonymous reviewers for their valuable suggestions, and the Tsinghua IDEAL group members for constructive discussion. The technical solution and experimental design presented in this paper were independently completed by the authors. AI tools were used solely for language polishing and formatting optimization, and did not participate in the development of the research ideas or core content.
References 1. Almeida, J.B., Barbosa, M., Barthe, G., Blot, A., Grégoire, B., Laporte, V., Oliveira, T., Pacheco, H., Schmidt, B., Strub, P.Y.: Jasmin: High-Assurance and High-Speed Cryptography. In: ACM SIGSAC Conference on Computer and Communications Security (CCS). pp. 1807–1823 (Oct 2017) 2. aturon: Tracking Issue for Plugin Stabilization (‘plugin‘, ‘plugin registrar‘ Features) · Issue #29597 · Rust-Lang/Rust. https://github.com/rustlang/rust/issues/29597 (Nov 2015) 3. Aumasson, J.P., Bernstein, D.J.: SipHash: A Fast Short-Input PRF. In: Progress in Cryptology - INDOCRYPT 2012. pp. 489–508 (2012)
obliv-clang: Real-World Oblivious Programming in C++
25
4. Blanton, M., Steele, A., Alisagari, M.: Data-Oblivious Graph Algorithms for Secure Computation and Outsourcing. In: ACM SIGSAC Symposium on Information, Computer and Communications Security (ASIA CCS). p. 207 (2013) 5. Borrello, P., D’Elia, D.C., Querzoni, L., Giuffrida, C.: Constantine: Automatic Side-Channel Resistance Using Efficient Control and Data Flow Linearization. In: ACM SIGSAC Conference on Computer and Communications Security (CCS). pp. 715–733 (Nov 2021) 6. Bulck, J.V., Weichbrodt, N., Kapitza, R., Piessens, F., Strackx, R.: Telling Your Secrets Without Page Faults: Stealthy Page Table-Based Attacks on Enclaved Execution. In: USENIX Security Symposium. pp. 1041–1056 (Aug 2017) 7. Cauligi, S., Soeller, G., Johannesmeyer, B., Brown, F., Wahby, R.S., Renner, J., Grégoire, B., Barthe, G., Jhala, R., Stefan, D.: FaCT: A DSL for Timing-Sensitive Computation. In: ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI). pp. 174–189 (Jun 2019) 8. Clang: UndefinedBehaviorSanitizer — Clang 16.0.0git Documentation. https://clang.llvm.org/docs/UndefinedBehaviorSanitizer.html (2022) 9. Clang-Tidy — Extra Clang Tools 18.0.0git Documentation. https://clang.llvm.org/extra/clang-tidy/ (2023) 10. What is Clangd? https://clangd.llvm.org/ (2023) 11. Deutsch, P.W., Yang, Y., Bourgeat, T., Drean, J., Emer, J.S., Yan, M.: DAGguise: Mitigating Memory Timing Side Channels. In: ACM International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS). pp. 329–343 (Feb 2022) 12. Disselkoen, C., Cauligi, S., Tullsen, D., Stefan, D.: Finding and Eliminating Timing Side-Channels in Crypto Code with Pitchfork. In: SRC TECHCON (2020) 13. formosa-crypto: Libjade. formosa-crypto (Oct 2023) 14. Gonzalez, S.: TinyJPEG (Aug 2022) 15. Götzfried, J., Eckert, M., Schinzel, S., Müller, T.: Cache Attacks on Intel SGX. In: European Workshop on Systems Security (EuroSec). pp. 1–6 (Apr 2017) 16. Jang, Y., Lee, J., Lee, S., Kim, T.: SGX-Bomb: Locking Down the Processor via Rowhammer Attack. In: Workshop on System Software for Trusted Execution (SysTEX). pp. 1–6 (Oct 2017) 17. Kim, T., Peinado, M., Mainar-Ruiz, G.: STEALTHMEM: System-Level Protection Against Cache-Based Side Channel Attacks in the Cloud. In: USENIX Security Symposium. pp. 189–204 (Aug 2012) 18. Lee, S., Shih, M.W., Gera, P., Kim, T., Kim, H., Peinado, M.: Inferring Finegrained Control Flow Inside SGX Enclaves with Branch Shadowing. In: USENIX Security Symposium. pp. 557–574 (2017) 19. Libsodium. https://doc.libsodium.org/ (2023) 20. Lipp, M., Kogler, A., Oswald, D., Schwarz, M., Easdon, C., Canella, C., Gruss, D.: PLATYPUS: Software-based Power Side-Channel Attacks on X86. In: IEEE Symposium on Security and Privacy (S&P). pp. 355–371 (May 2021) 21. Liu, C., Harris, A., Maas, M., Hicks, M., Tiwari, M., Shi, E.: GhostRider: A Hardware-Software System for Memory Trace Oblivious Computation. In: International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS). p. 87–101 (2015) 22. Liu, C., Hicks, M., Shi, E.: Memory Trace Oblivious Program Execution. In: IEEE Computer Security Foundations Symposium (CSF). pp. 51–65 (Jun 2013) 23. Liu, C., Huang, Y., Shi, E., Katz, J., Hicks, M.: Automating Efficient RAM-Model Secure Computation. In: IEEE Symposium on Security and Privacy (S&P). pp. 623–638. IEEE, San Jose, CA (May 2014)
26
Yunqian Luo and Mingyu Gao
24. Liu, C., Wang, X.S., Nayak, K., Huang, Y., Shi, E.: ObliVM: A Programming Framework for Secure Computation. In: IEEE Symposium on Security and Privacy (S&P). pp. 359–376 (May 2015) 25. LLVM: Available Checkers. https://clang-analyzer.llvm.org/available checks.html (2022) 26. LZ4 - Extremely Fast Compression. https://lz4.org/ (2023) 27. Mood, B., Gupta, D., Carter, H., Butler, K., Traynor, P.: Frigate: A Validated, Extensible, and Efficient Compiler and Interpreter for Secure Computation. In: IEEE European Symposium on Security and Privacy (EuroS&P). pp. 112–127 (Mar 2016) 28. Ohrimenko, O., Goodrich, M.T., Tamassia, R., Upfal, E.: The Melbourne Shuffle: Improving Oblivious Storage in the Cloud (Feb 2014) 29. Rane, A., Lin, C., Tiwari, M.: Raccoon: Closing Digital Side-Channels Through Obfuscated Execution. In: USENIX Security Symposium. pp. 431–446 (2015) 30. Reparaz, O., Balasch, J., Verbauwhede, I.: Dude, is My Code Constant Time? (2016) 31. Sayakkara, A., Le-Khac, N.A., Scanlon, M.: A Survey of Electromagnetic SideChannel Attacks and Discussion on Their Case-Progressing Potential for Digital Forensics. Digital Investigation 29(1), 43–54 (Jun 2019) 32. Shih, M.W., Lee, S., Kim, T., Peinado, M.: T-SGX: Eradicating ControlledChannel Attacks Against Enclave Programs. In: Network and Distributed System Security Symposium (NDSS). Internet Society, San Diego, CA (2017) 33. Shinde, S., Chua, Z.L., Narayanan, V., Saxena, P.: Preventing Page Faults from Telling Your Secrets. In: ACM Asia Conference on Computer and Communications Security (ASIA CCS). pp. 317–328 (May 2016) 34. Sinha, R., Rajamani, S., Seshia, S.A.: A Compiler and Verifier for Page Access Oblivious Computation. In: Joint Meeting on Foundations of Software Engineering (ESEC/FSE). pp. 649–660 (Aug 2017) 35. Son, J., Prechter, G., Poddar, R., Popa, R.A., Sen, K.: ObliCheck: Efficient Verification of Oblivious Algorithms with Unobservable State. In: USENIX Security Symposium (2021) 36. Son, M., Park, H., Ahn, J., Yoo, S.: Making DRAM Stronger Against Row Hammering. In: Design Automation Conference (DAC). pp. 1–6 (Jun 2017) 37. Sprenkels, D.: LLVM Provides No Side-Channel Resistance. https://dsprenkels.com/cmov-conversion.html (Oct 2019) 38. SQLite Home Page. https://www.sqlite.org/index.html (Oct 2023) 39. Stefanov, E., Dijk, M.V., Shi, E., Chan, T.H.H., Fletcher, C., Ren, L., Yu, X., Devadas, S.: Path ORAM: An Extremely Simple Oblivious RAM Protocol. Journal of the ACM (JACM) 65(4), 1–26 (2018) 40. The C++ Standards Committee: C++ Standard Draft Sources. https://github.com/cplusplus/draft (Oct 2022) 41. Vaillant, L.: Monocypher. https://monocypher.org/ (2023) 42. Van Bulck, J., Minkin, M., Weisse, O., Genkin, D., Kasikci, B., Piessens, F., Silberstein, M., Wenisch, T.F., Yarom, Y., Strackx, R.: Foreshadow: Extracting the Keys to the Intel SGX Kingdom with Transient Out-of-Order Execution. In: USENIX Security Symposium. pp. 991–1008 (Aug 2018) 43. Wang, X.S., Nayak, K., Liu, C., Chan, T.H., Shi, E., Stefanov, E., Huang, Y.: Oblivious Data Structures. In: ACM SIGSAC Conference on Computer and Communications Security (CCS). pp. 215–226 (2014)
obliv-clang: Real-World Oblivious Programming in C++
27
44. Yu, J., Hsiung, L., El’Hajj, M., Fletcher, C.W.: Data Oblivious ISA Extensions for Side Channel-Resistant and High Performance Computing. In: Network and Distributed System Security Symposium (NDSS) (2019) 45. Zahur, S., Evans, D.: Obliv-C: A Language for Extensible Data-Oblivious Computation (2015) 46. Zhang, L., Vega, L., Taylor, M.: Power Side Channels in Security ICs: Hardware Countermeasures. arXiv:1605.00681 (Aug 2015) 47. Zhang, Z., Barthe, G.: CT-LLVM: Automatic Large-Scale Constant-Time Analysis. Cryptology ePrint Archive, Report 2025/338 (2025)