betaFeedback

WorksComputer Science

Type-Confusion Security

Abstract

Type systems are a lightweight way to obtain formal assurance that code upholds security properties. However, decentralized systems, such as smart contracts and Model Context Protocol ecosystems, have limited ability to constrain the behavior of untrusted code. In such systems, attackers may attempt to confuse trusted code by supplying values that do not behave according to their advertised types, an attack that we call type confusion. Well-known attacks such as confused deputy attacks, reentrancy attacks, and control-flow hijacking can be understood as instances of type confusion. We define type confusion security as the property that unrestricted attackers who need not follow the type system have no more power than limited attackers who fully obey it. We formally define type confusion security as a real–ideal emulation, and in the context of an information-flow-typed core calculus that statically enforces security against well-typed attackers, prove that its run-time checks also enforce security against ill-typed attackers. In this system, programmers can write code while reasoning about security only against well-typed attackers; the security guarantees enforced by the type system still hold. We mechanize a proof of type confusion security in Lean.

Introduction

Static type systems are a powerful way to enforce security. They allow programmers to reason about code in a high-level language and rule out attacks before the code runs, often with little or no run-time overhead. In type systems for information flow control (IFC), labeled types serve as expressive security specifications for code: they describe confidentiality and integrity requirements, identify contexts in which code may execute securely, and also enable enforcement of properties like noninterference [20, 38], reentrancy security[12] and nonmalleable information flow [11].

However, purely static reasoning is fragile in systems where adversaries may not follow the rules. For example, smart contracts, cross-chain protocols, federated systems like Bluesky or OAuth 2.0, and Model Context Protocol (MCP) ecosystems routinely interact across trust boundaries. In such settings, trusted code may receive ill-typed values from an adversarial principal or invoke remote procedures whose implementations are controlled by an adversary. Our name for an adversary-induced mismatch between the expected and actual types is type confusion.

Depending on the type system, type confusion has different security implications. Its most obvious form involves unchecked casts between ordinary types, which can violate memory safety. Further, an integer can be used at run time as a function pointer, leading to vulnerabilities such as control-flow hijacking [1, 31]: calling the function jumps to an invalid or unauthorized address.

Type confusion can be more insidious in security type systems, where labels on types express security requirements for authorization and information flow. As we illustrate, confused-deputy attacks (CDAs) [21] and reentrancy attacks [12] are examples of such phenomena. Such attacks are not merely hypothetical: recent high-profile security breaches in blockchain smart contracts have been attributed to CDAs and reentrancy attacks [14, 15, 16, 17] that exploit mismatched expectations about the behavior of callback code. In both cases, attackers exploit type-confused function pointers to induce insecure control flows. Solutions for such type confusion are unsatisfactory. Existing techniques like gradual typing [9, 13] don’t address adversarial settings: every term is either dynamically or statically typed, the runtime is trusted, and users don’t actively misrepresent types. State-of-the-art language-based IFC systems like SCIF [44] and Fabric [25] partially address these attacks but lack formal guarantees. Prior formal works [12, 34] show that IFC, extended with run-time checks, can enforce security against CDAs and reentrancy attacks independently, but not in a unified framework.

Our core contribution is a unified, extensional, and rigorous description of security for the above attacks, as type confusion security. Further, we construct effective dynamic mechanisms against type confusion, and highlight their semantic principles. Our contributions are summarized below:

Type-confusion security. We define type-confusion security in the style of simulation-based security [10]: attackers gain no advantage by confusing types because such attackers can be simulated by ones who do not. Type-confusion security ensures robust hyperproperty preservation (RHP) [3, 33], a compiler correctness property which requires that whatever properties the type system enforces—for example, memory safety or noninterference—hold even in the presence of real-world attackers. Thus, programmers may reason about security in the simpler, well-typed ideal world, even though deployed code interacts with real-world adversaries that do not respect the type system.

Provable security enforcement of type confusion. We design dynamic mechanisms that provably enforce type-confusion security for an information-flow-typed language. It might seem that it suffices to simply perform a dynamic check that mirrors its static counterpart. However, we show that run-time enforcement must be carefully designed to ensure that the dynamic checks are strong enough, performed only by honest parties, and depend only on trusted run-time information.

Provable enforcement of real-world security. This paper defines novel, simple run-time checks that protect against CDAs. It also extends the authority-lock mechanism of SeRIF [12] to enforce reentrancy security more flexibly.

Language model and formalization. To explore type-confusion security and its enforcement mechanisms, we define a core calculus of a decentralized system with remote procedure calls (RPC). In the setting of this core calculus, we mechanize all of our security results in Lean [28].

The rest of the paper is structured as follows. § 2 introduces motivating examples and the key intuition behind the run-time checks. § 3 provides a formal overview of type-confusion security. § 4 defines the ideal and real calculi. § 5 proves the main simulation theorem. § 6 applies the theorem to prove security against CDA and reentrancy attacks. § 7 discusses related work and concludes.

Background and Motivation

Confused Deputy Attacks

A confused-deputy attack (CDA) [21] happens when an attacker tricks a trusted party (the deputy) into misusing its authority to effectively escalate the attacker’s privileges. Figure 1 shows a simplified version of a CDA against a token exchange service. It captures the spirit of several notorious recent attacks causing millions of dollars in losses [14, 15, 16].

Confused deputy attack on an exchange smart contract, showing honest user, attacker, and exchange code with trusted and untrusted control-flow arrows

Figure 1. Confused deputy attack on an exchange smart contract. The solid green arrows represent a well-typed usage of the service. Dashed red arrows show the control caused by an ill-typed attacker. Run-time checks on line 1 of exchange cannot be trusted because they involve an untrusted caller. On a CDA run, the dynamic check on line 3 happens fully within the trusted parties because both the deputy and the victim are trusted.

Here, the exchange service is the trusted confused deputy. In an honest execution, the user calls the exchange contract with an exchange request, along with the user’s payment function alice.pay() for the exchange service to extract funds. When called, the exchange contract queries a price oracle for the exchange rate, then calls the user’s payment function, and finally pays the user. However, an attacker might pass the exchange’s own payment handle exchange.pay() instead, causing the exchange service to pay the user (line 3) when it should receive payment from the user.

The classic solution to CDA is capabilities [21], but a less error-prone solution can be obtained by viewing CDA through the lens of secure information flow, where it becomes clear that CDA is a form of type confusion.

Assume a simple two-point lattice of information-flow labels in which information is either labeled T for “trusted” or U for “untrusted”. Function types are annotated by labels; in particular, each function type includes an external pc (program counter) label [12] which controls the contexts from which it may be called, as seen in Figure 1. A function labeled T may only be called from trusted contexts. A function labeled U may be called from anywhere and passed untrusted arguments, so a U-function type is a subtype of a T-function type. Although the exchange service is trusted to call any function in a trusted context, we can design our IFC type system so that a call through the untrusted variable receiver (line 3) is necessarily performed in an untrusted context U.

If the static typing rules are enforced, the attack is prevented because line 2 of the attacker code fails to type-check: the attacker passes exchange.pay, a T-function pointer, to a U-labeled function parameter (receiver). Because function subtyping is contravariant on inputs, this argument is rejected. However, in the real world where attackers do not follow static typing rules, run-time checks are needed to prevent CDAs.

Naively we might think to check the type of receiver as soon as exchange.swap is called, but in an open system we do not know this type and cannot trust the attacker to provide it. Therefore, we perform run-time security checks lazily at function calls. On line 3 of exchange.swap, the exchange notifies the callee exchange.pay that it is being called from a U-labeled context. As the trusted callee exchange.pay expects calls only from T-labeled contexts, it rejects the call at run time.

The obvious question is whether this simple dynamic check suffices to prevent CDA. We can show that it does by demonstrating that with this check, the system is secure against type confusion.

Reentrancy Attacks

CDAs are not the only attacks that could happen to the exchange service of Figure 1. Figure 2 shows a reentrancy attack [17], in which the attacker causes the deputy to be called again before it finishes its first call. In this attack, the attacker writes a U-labeled contract that invokes exchange.swap when called. This callback causes the exchange service to be recursively called many times before any call returns, adjusting the exchange rate returned by the price oracle in favor of the attacker.

Reentrancy attack against the exchange service

Figure 2. Reentrancy attack against the exchange service. The exchange service “locks” the trusted control flow level on call #1. Call #2 sends control flow back to untrusted code, but the lock prevents call #3 from reentering trusted control flow.

As observed by Cecchetti et al. [12], a reentrancy attack exploits contracts where invariants over trusted state are expected to hold before and after external function calls. In the example from Figure 2, the (trusted) exchange rate is expected to remain stable from line 2 to line 4. The attacker indirectly influences that trusted state by diverting the control flow to call oracle.quote() multiple times before exchange.pay() is called.

Statically modeling reentrancy attacks requires reasoning about the effects of functions on trusted state. To account for that, we introduce a bounding label on function types, to upper-bound the level of effects during function execution. The function exchange.pay() is a {T▹T}\{\mathrm{T}\mathrel{\triangleright}\mathrm{T}\}-function that can only be called in a trusted context and updates the trusted state of the exchange. Bounding labels are contravariant because a function with an untrusted bounding label also satisfies trusted effect bounds. The function exchange.swap() is an auto-endorsing [12] function,1 which can be called in an untrusted context but updates the trusted state of the exchange. The function adv.reenter() is also an auto-endorsing function because it calls the auto-endorsing function exchange.swap().

Auto-endorsement, like any form of endorsement, carries some danger because it allows an untrusted control-flow context to influence trusted control flow and state. However, such functions are indispensable for building software, including smart contracts. As another example, untrusted code (applications) must be able to influence trusted (kernel) state via operating system calls.

As observed by Cecchetti et al. [12], reentrancy attacks are caused by unconstrained use of auto-endorsing functions. Bounding label annotations on function pointers enable static analysis to identify auto-endorsing functions, which prevents these attacks.

Similar to CDA, reentrancy attacks can be prevented by static checks in the ideal world where attackers are well-typed: on line 2 of Figure 2, the attacker uses adv.reenter, a {U▹T}\{\mathrm{U}\mathrel{\triangleright}\mathrm{T}\}-function, as an argument of type {U▹U}\{\mathrm{U}\mathrel{\triangleright}\mathrm{U}\}. But an ill-typed, real world attacker may lie about its function signature by publishing {U▹U}\{\mathrm{U}\mathrel{\triangleright}\mathrm{U}\} as the signature of adv.reenter. The dynamic check that allows the ideal world and the real world to agree is a dynamic lock mechanism, adapted from Cecchetti et al. [12]: when a function is called, it locks its own level of control flow until it returns. In the example from Figure 2, the exchange service locks its control-flow level T\mathrm{T} from lines 2 to 4. Any function call that enters T\mathrm{T} from U\mathrm{U} is rejected, so execution aborts the first time adv.reenter() tries to invoke exchange.swap().

Control-Flow Hijacking

Figure 3 extends the same exchange code with a validation step. If the validation fails, it executes the error continuation onReject that never returns, preventing the exchange from happening.

Ordinary-type confusion example showing an untyped attacker and an exchange with validation

Figure 3. Ordinary-type confusion bypasses order validation through a returning error continuation. A well-typed argument for onReject is a function that either diverges or aborts, but does not return.

For well-typed attackers, the type of onReject ensures that the exchange is only executed when the order validates. Ill-typed attackers can bypass validation by simply providing a function adv.ignore with a unit return type, so the order keeps executing.

Here, type confusion is used on the ordinary unlabeled part of the type. Reasoning about such attacks requires specifying how values are interpreted at incompatible types—for example, what happens when an integer is used as a function pointer. We keep the cast semantics abstract and assume that honest code can inspect the declared ordinary signatures of function pointers and reject incompatible pointers eagerly at run time. We leave a systematic study of the broader trade-offs among cast semantics, runtime assumptions, and dynamic enforcement to future work.

Type-Confusion Security

The examples from §2 show that an attacker who lies about types can cause program behavior that is not possible for an attacker who obeys the type system. Our proposed dynamic checks abort at run time to ensure that the real attacker cannot introduce new behavior. Type-confusion security requires that all real attackers can be simulated by ideal attackers.

In the ideal world, both the honest party and the attacker are well-typed programs and no run-time checks are inserted. Whatever properties the static type system enforces must hold in the presence of the attacker. In the real world, the attacker is an unrestricted state machine that can produce arbitrary ill-typed values. To protect against this strong attacker, the program must in general be translated, to instrument it with dynamic enforcement mechanisms.

Type-confusion security is defined by quantifying over all valid real attackers, and for each valid real attacker, there must be a valid ideal attacker. We write ⊢RAR\vdash_R \mathcal{A}^R to mean that AR\mathcal{A}^R is a valid real attacker, and ⊢IAI\vdash_I \mathcal{A}^I to mean that AI\mathcal{A}^I is a valid ideal attacker (for example, it needs to type-check).

Definition 3.1 (Type-Confusion Security). Consider the real world R=(⊢R,DynR)R = (\vdash_R, \mathrm{Dyn}_R), and the honest programs’ dynamic checks DynR\mathrm{Dyn}_R. The ideal world is I=(⊢I,DynI)I = (\vdash_I, \mathrm{Dyn}_I), with ideal-program dynamic checks DynI\mathrm{Dyn}_I. Let ⟦P,A,DynW⟧\llbracket\mathcal{P}, \mathcal{A}, \mathrm{Dyn}_W \rrbracket denote the behavior of the program linked with the attacker A\mathcal{A} under DynW\mathrm{Dyn}_W. We define type-confusion security as follows:

R⪯I⟺∀P. ∀AR∣⊢RAR. ∃AI∣⊢IAI. ⟦P,AR,DynR⟧=⟦P,AI,DynI⟧R \preceq I \Longleftrightarrow\forall\mathcal{P}.\ \forall\mathcal{A}^R \mid\vdash_R \mathcal{A}^R.\ \exists\mathcal{A}^I \mid\vdash_I \mathcal{A}^I.\ \llbracket\mathcal{P}, \mathcal{A}^R, \mathrm{Dyn}_R \rrbracket= \llbracket\mathcal{P}, \mathcal{A}^I, \mathrm{Dyn}_I \rrbracket

We write R≈IR \approx I when the worlds simulate each other: that is, R⪯IR \preceq I and I⪯RI \preceq R.

Proving Type Confusion by Composing Simulations

Our proof follows the strategy of context-based backtranslation [18, 30]: for every real attacker, we construct a simulator, which is an ideal attacker that simulates the observable behavior of the real attacker. As simulation-based security is transitive, multiple simulators can be composed to construct a bigger simulator. Figure 4 visualizes our end-to-end type confusion proof, which is built from 3 smaller type confusion proofs connecting 4 worlds: Worlds 0–3.

Figure 4. The four worlds and their attackers.

World 3 is the most “ideal” world. Both programs and attackers are implemented as well-typed code from our core calculus, and no dynamic security enforcement is needed. To avoid restricting the computational power of attackers to dynamically make decisions based on run-time values, such as inspecting security types, we assume ideal attackers can access a set of well-typed pure functions that may arbitrarily transform their input values. In World 0, the most “real” world, an attacker is an arbitrary state machine that does not respect types, and multiple dynamic enforcement mechanisms are needed. Worlds 1 and 2 give the attacker powers intermediate between Worlds 0 and 3. In World 1, the attacker is a state machine that behaves however it wants internally but behaves at its interface in a way that respects ordinary types (but not security labels). In World 2, the attacker is a state machine that behaves however it likes internally but fully respects security types at its interface.

Ultimately, we prove type confusion holds between World 0 and World 3, with Worlds 1 and 2 as stepping stones. The most challenging part of the proof is to show that World 1 simulates World 2; this step turns dynamic IFC enforcement of complex security properties like reentrancy security and CDA security into purely static checks. Simulation between World 2 and World 3 shows that the attacker who is limited to well-typed code (plus additional well-typed pure functions) is just as powerful as a state-machine attacker.

By transitivity, the well-typed code attacker is as powerful as the arbitrary untyped state machine attacker, assuming that the World 0 dynamic enforcement mechanisms of safe casts and authority checks are in place at run time.

While our major result is the simulation from World 0 to World 3, the dynamic checks actually ensure that the backward simulation holds too: World 3 simulates World 0. It might seem trivial that backward simulation holds because the real attacker is strictly stronger. However, the backward simulation result is meaningful because an overly restrictive run-time check that rejects all function calls might make the main bottom-to-top simulation hold vacuously. The top-to-bottom, ideal-to-real simulation shows that the main result is not vacuous.

Threat Model

We consider a decentralized system with principals, some of which are controlled by the attacker. Each principal publishes its claimed public interface, which is a set of function pointers with their signatures. Implementations of functions on well-typed attackers and honest principals comply with the published signatures, but functions implemented by attackers do not follow the signatures.

A subtle but important difference between our threat model and those of prior work in gradual typing [9, 13] and dynamic IFC [12, 25, 34] is the degree of trust in the runtime system. Prior work designs dynamic mechanisms for a trusted runtime that also governs the attacker’s behavior. In contrast, we model a system with a minimalist runtime that cannot control the attacker, and instead ensure that security checks happen exclusively in honest code. Specifically, we assume that the following. First, the callee in a remote call learns who the caller is, what the arguments are, and nothing else. Second, all function pointers are publicly callable, so there is no mechanism for restricting the visibility of function pointers. Finally, all static analysis is modularly enforced per function and may refer to the potentially incorrect function signature table.

Information Flow Labels

Intuition for why CDA and reentrancy attacks are the only kinds of IFC type confusion can be obtained by taking a closer look at IFC labels and the subtyping lattice of IFC types.

IFC Label Model

In an IFC type system, each type τ\tau includes a label that governs the use of values of that type [37]. In this paper, we adopt the label model of Arden et al. [6], Ren et al. [35], where each principal p∈Pp \in\mathbb{P} is also a security policy label ℓ\ell. A value annotated by pp is trusted by the principal pp. Labels form a bounded distributive lattice, where join ⊔\sqcup and meet ⊓\sqcap take the greatest common integrity and least combined integrity respectively. The attacker controls a prime filter [35] of the lattice.2 Given a type τ\tau, we write lbl⁡(τ)\operatorname{lbl}(\tau) to denote the label of the type. We do not consider confidentiality.

The flows-to order ⊑\sqsubseteq between labels represents the direction of secure information flow. Ordering ℓ1⊑ℓ2\ell_1 \sqsubseteq\ell_2 holds when ℓ1\ell_1 is at least as trusted as ℓ2\ell_2. The bottom element ⊥\bot represents the most trusted label never controlled by the attacker, and the top element ⊤\top represents the least trusted label always controlled by the attacker.

IFC Function Signatures

Function signatures have the form τi→pcex▹pcmaxτo\tau_i \xrightarrow{pc_{\mathrm{ex}}\mathrel{\triangleright}pc_{\mathrm{max}}} \tau_o, where τi\tau_i is the input type and τo\tau_o is the output type. As introduced in § 2, the external pc pcexpc_{\mathrm{ex}} upper-bounds the contexts in which the function may be called; the bounding pc pcmaxpc_{\mathrm{max}} upper-bounds the effect of the function starting from its invocation to its return. Like other types, function types τ=(τi→pcex▹pcmaxτo)ℓ\tau= (\tau_i \xrightarrow{pc_{\mathrm{ex}}\mathrel{\triangleright}pc_{\mathrm{max}}} \tau_o)_{\ell} include an extra label ℓ\ell, the label of the function pointer itself.

In a decentralized system, an IFC-labeled function type is a security specification. As certain security specifications can be self-contradictory, such function types are considered ill-formed. Let pp be the principal on which this function is defined. A well-formed function type is one where pcmax⊑p⊑pcex⊑lbl⁡(τi)pc_{\mathrm{max}} \sqsubseteq p \sqsubseteq pc_{\mathrm{ex}} \sqsubseteq\operatorname{lbl}(\tau_i). First, because each function runs at its own control-flow integrity, the upper bound on effects pcmaxpc_{\mathrm{max}} needs to be at least as trusted as pp itself. Second, a principal should be allowed to call its own function, so pp needs to be no less trusted than pcexpc_{\mathrm{ex}}. Finally, pcex⊑lbl⁡(τi)pc_{\mathrm{ex}} \sqsubseteq\operatorname{lbl}(\tau_i) should hold; if not, this function would take trusted input from an untrusted context that taints any value it holds, causing a contradiction. Figure 5 shows the subtyping lattice of IFC function types. As the lattice shows, the output label τo\tau_o is covariant; the input type τi\tau_i, external pc pcexpc_{\mathrm{ex}}, and bounding pc pcmaxpc_{\mathrm{max}} are all contravariant.

The subtyping lattice of well-formed function types

Figure 5. The subtyping lattice of well-formed function types. Type confusion occurs when a down-cast happens to a fully untrusted pointer.

Type Confusion of IFC Function Types

In trusted code, the only way to statically type a useful function pointer received from an attacker is the type (U→U◃UU)U(U \xrightarrow{U \triangleleft U} U)_{U}. To see why, first observe that all pointers from the attackers are UU-labeled. This label taints all labels except pcmax⁡pc_{\max} in a function pointer [12, 46]. Therefore, the type system gives all attacker-controlled pointers the type (U→U◃UU)U(U \xrightarrow{U \triangleleft U} U)_{U} or (U→U◃TU)U(U \xrightarrow{U \triangleleft T} U)_{U}.

In a trusted context, pointers of the second type can be passed or returned, but cannot be directly invoked because invoking them leads to a potential reentrancy attack. Thus only the first kind can be used in a trusted context.

Therefore, IFC-type confusion only happens when an attacker performs a down-cast to a (U→U◃UU)U(U \xrightarrow{U \triangleleft U} U)_{U}-typed pointer, and then passes the pointer to the honest principal (deputy). As shown in Figure 5, there are three possible down-casts, one for each contravariant label. CDAs and reentrancy attacks are the cases where down-casts happen on pcexpc_{ex} and pcmax⁡pc_{\max}. Type confusion on primitive (non-function) input types can be statically enforced because the deputy treats inputs of such pointers as untrusted. In the case where the input type is itself another function type, well-formedness of IFC types statically ensures that no such type confusion is possible.

A Core Calculus for Type Confusion

We define a core calculus to formally model a decentralized system that supports first-class function pointers and remote function calls. We represent honest principals by their program code and the attacker by an interactive state machine, which is linked to the program at run time.

Syntax for the Honest Party

Figure 6 defines the syntax of the core calculus. This language models a decentralized system with multiple principals p∈Pp \in\mathbb{P}. Each principal pp can also be interpreted as a label ℓ\ell, which can be used to describe the integrity of values. Principals own functions and memory cells. We write p.fp.f for the identifier, or pointer, of the function ff owned by principal pp.

Syntax of the core calculus

Figure 6. Syntax of the core calculus. Principals and labels range over the same lattice P\mathbb{P}.

A program P=(I,body,T.entry)\mathcal{P} = (\mathcal{I}, \mathit{body}, \mathit{T.entry}) consists of an interface, a body table and an entry function belonging to principal T\mathsf{T}. The interface I=(sig,cell)\mathcal{I} = (\mathit{sig}, \mathit{cell}) pairs a signature table sig:P×FunName→finSignature\mathit{sig} : \mathbb{P} \times\mathit{FunName} \to_{\mathrm{fin}} \mathit{Signature}, which maps each declared function to a signature, with a cell table cell:P×RefName→finType\mathit{cell} : \mathbb{P} \times\mathit{RefName} \to_{\mathrm{fin}} \mathit{Type}, which maps each cell to the type of its contents. The body table body:P×FunName→finBody\mathit{body} : \mathbb{P} \times\mathit{FunName} \to_{\mathrm{fin}} \mathit{Body} maps each implemented function to a closed lambda term (i.e., λ x.e\lambda\ x.e), where →fin\to_{\mathrm{fin}} denotes a finite partial map. We use p.fp.f and p.hp.h to range over elements of P×FunName\mathbb{P} \times\mathit{FunName} and P×RefName\mathbb{P} \times\mathit{RefName}respectively. respectively. Every execution starts at ⊤.entry\top.\mathrm{entry}, which belongs to the least trusted principal ⊤\top with signature 1→111 \xrightarrow{1} 1. Thus, all executions are initiated by the attacker.

Programs must satisfy two well-formedness conditions. First, all three tables have finite domains, because a program is a finite artifact. Second, dom⁡(body)⊆dom⁡(sig)\operatorname{dom}(\mathrm{body}) \subseteq\operatorname{dom}(\mathrm{sig}), so every implemented function has a published signature. Note that the converse need not hold, an honest party does not know the implementation of an attacker in general (§ 4.3).

Types are equipped with information-flow labels in the standard way [37, 47]. Booleans, natural numbers, and function pointers each carry a label ℓ\ell denoting the integrity policy of the label. The unit type 11 and the empty type 00 have at most one inhabitant, and thus do not require labeling.

Values and expressions are mostly standard and written in A-normal form [19]. The language aims to be practical, and thus supports endorsement [24] of non-function-pointer values v↓ℓv \downarrow\ell as strict noninterference is too restrictive. Endorsement of function pointers is disallowed because it does not add meaningful expressiveness, and it adds a new surface for type-confusion attacks.

A principal can only read directly from and write directly to a cell hh that it owns; remote read and write must be provided by “getter” and “setter” functions. A function application v1[ℓ]v2v_1[\ell]v_2 is annotated with the pc ℓ\ell used for this function call. In well-typed code, ℓ\ell can be inferred and is equal to the external pc of pointer v1v_1’s function type. We add it to the syntax explicitly because it is used by run-time checks.

As a program executes, it produces a trace η⃗\vec{\eta} of events η\eta. We write :: for list concatenation, treating individual elements as singleton lists. A write event (p.h:=v)(p.h := v) records that pp writes vv to its cell hh, and a call event call⁡ℓ(p.f)\operatorname{call}_{\ell}(p.f) records a call to p.fp.f together with its calling pc ℓ\ell, the caller’s label joined with the call’s annotation. A return event ret⁡(p)\operatorname{ret}(p) records that a function owned by pp returns. Finally, ↓\downarrow records that the run aborts, and ✓\checkmark records that it exits gracefully once the entry returns.

Static Semantics

IFC typing. Figure 7 defines the judgments Γ;pc;p;pcmax⁡self⊢W2e:τ\Gamma; pc; p; pc_{\max}^{self} \vdash_{\mathrm{W2}} e : \tau and τ⪯τ′\tau\preceq\tau'. The former checks an expression ee, run by principal pp at pc pcpc with bounding pc pcmax⁡selfpc_{\max}^{self}, against type τ\tau.3 The latter gives IFC subtyping rules which are standard.

Figure 7. Full IFC subtyping and selected expression typing rules.

Figure 7 shows selected rules, and §B gives the full type system. Most rules are standard [45, 46]. Well-typed code can access only addresses declared by cell. TI-READ and TI-WRITE access only the declared cells of pp, and pc⊑lbl⁡(τ)pc \sqsubseteq\operatorname{lbl}(\tau) ensures that the cell’s label covers the control flow that reaches the access. TI-DOWNGRADE applies to values that are not function-typed and sets its label to ℓ\ell. In particular, function pointers cannot be endorsed, so their types retain all taints to them.

Function pointers require more care. Since the owner qq controls how q.fq.f behaves, a pointer to it is trusted only as much as qq is, so TI-FUN requires q⊑ℓq \sqsubseteq\ell. Combined with the well-formedness conditions of signatures from § 3.3.2, well-formedness of types, written ⊢W2 τ\vdash_{\mathrm{W2}}\ \tau, is given by:

⊢W2(τi→pcex⊑pcmax⁡τo)iff⊢W2τi∧⊢W2τo∧pcmax⁡⊑ℓ\vdash_{\mathrm{W2}}\left(\tau_i \xrightarrow{pc_{\mathrm{ex}}\sqsubseteq pc_{\max}} \tau_o\right)\quad\text{iff}\quad\vdash_{\mathrm{W2}}\tau_i \land\vdash_{\mathrm{W2}}\tau_o \land pc_{\max}\sqsubseteq\ell

TI-APP enforces the static discipline of function calls through three constraints. First, pc⊔ℓ⊑pcexpc \sqcup\ell\sqsubseteq pc_{\mathrm{ex}} allows a call only when the external pc covers both the caller’s pc and the influence over which function the pointer selects. Second, pcex⊑pcmax⁡⊔ppc_{\mathrm{ex}} \sqsubseteq pc_{\max} \sqcup p ensures that a call enters at an untrusted level only to the extent that the callee stays that untrusted throughout or the caller already was, which forbids the control-flow endorsement behind reentrancy [12]. Third, the caller’s bounding pc constrains every function it calls, so the constraint pcmax⁡self⊑pcmax⁡pc_{\max}^{self} \sqsubseteq pc_{\max} accepts only calls within such a bound. The result type τo⊔ℓ\tau_o \sqcup\ell joins the label of τo\tau_o with ℓ\ell (see §B.1 for formal definitions), since the resulting value reveals which function the pointer selected.

Ordinary typing. Ordinary typing follows the standard type system of the simply-typed lambda calculus, and is isomorphic to IFC typing over the one-point label model {∙}\{\bullet\}. For brevity, we write σ::=bool∣nat∣1∣0∣σ→σ\sigma::= \mathrm{bool} \mid\mathrm{nat} \mid1 \mid0 \mid\sigma\to\sigma, and Γ;p⊢W1e:σ\Gamma; p \vdash_{\mathrm{W1}} e : \sigma for ordinary typing rules. We write ⌊τ⌋\lfloor\tau\rfloor for the unlabeled type that results when every label and pc annotation is erased from τ\tau. With the one-point label, every label premise in ⊢W2\vdash_{\mathrm{W2}} trivially holds, so only the ordinary-type premises remain. We show TR-Fun, TR-App and TR-Down, and the rest of the type system can be found in Figure 16.

Figure 16. Ordinary expression typing.

sig⁡(q.f)=τi→pcex▹pcmaxτoΓ;p⊢W1q.f:⌊τi⌋→⌊τo⌋\begin{aligned} &\operatorname{sig}(q.f)=\tau_i \xrightarrow{pc_{\mathrm{ex}}\triangleright pc_{\mathrm{max}}} \tau_o\\ &\Gamma; p \vdash_{\mathrm{W1}} q.f : \lfloor\tau_i\rfloor\to\lfloor\tau_o\rfloor \end{aligned}
Γ;p⊢W1v1:σi→σoΓ;p⊢W1v2:σσ⪯σiΓ;p⊢W1v1[pcex]v2:σo\begin{aligned} &\Gamma; p \vdash_{\mathrm{W1}} v_1 : \sigma_i \to\sigma_o\\ &\Gamma; p \vdash_{\mathrm{W1}} v_2 : \sigma\qquad\sigma\preceq\sigma_i\\ &\Gamma; p \vdash_{\mathrm{W1}} v_1[pc_{\mathrm{ex}}]v_2 : \sigma_o \end{aligned}
σ∈{bool,nat,0}Γ;p⊢W1v:σΓ;p⊢W1v↓ℓ:σ\begin{aligned} &\sigma\in\{\mathrm{bool},\mathrm{nat},0\}\\ &\Gamma; p \vdash_{\mathrm{W1}} v : \sigma\\ &\Gamma; p \vdash_{\mathrm{W1}} v \mathbin{\downarrow}\ell: \sigma \end{aligned}

Note that an IFC-typed expression is also ordinarily typed (Γ;pc;p;pcmaxself⊢W2e:τ⟹⌊Γ⌋;p⊢W1e:⌊τ⌋)(\Gamma; pc; p; pc_{\mathrm{max}}^{\mathrm{self}} \vdash_{\mathrm{W2}} e : \tau\Longrightarrow\lfloor\Gamma\rfloor; p \vdash_{\mathrm{W1}} e : \lfloor\tau\rfloor).

Program typing. An interface is well formed when every cell type and every signature is well formed (§ 3.3.2).

⊢W2Iiff∀p,f. sig⁡(p.f)=τi→pcex▹pcmaxτo⟹⊢W2τi∧⊢W2τo∧pcmax⊑p⊑pcex⊑lbl⁡(τi)\vdash_{\mathrm{W2}} I \quad\mathrm{iff}\quad\forall p,f.\ \operatorname{sig}(p.f)=\tau_i \xrightarrow{pc_{\mathrm{ex}}\triangleright pc_{\mathrm{max}}} \tau_o \Longrightarrow\vdash_{\mathrm{W2}}\tau_i \land\vdash_{\mathrm{W2}}\tau_o \land pc_{\mathrm{max}}\sqsubseteq p\sqsubseteq pc_{\mathrm{ex}}\sqsubseteq\operatorname{lbl}(\tau_i)
∧ ∀p,h. cell⁡(p,h)=τ⟹⊢W2τ\land\ \forall p,h.\ \operatorname{cell}(p,h)=\tau\Longrightarrow\vdash_{\mathrm{W2}}\tau
a∈Action::=call⁡(vf,ℓ,v)∣ret⁡(v)∣abort⁡m∈Message::=invoke⁡(p.f,v)∣result⁡(v)M=(State,sAinit,ρ,δ)where sAinit∈Stateρ:State×Message→Stateδ:State→State+(Action×State)\begin{aligned} a &\in\mathrm{Action} ::= \operatorname{call}(v_f,\ell,v)\mid\operatorname{ret}(v)\mid\operatorname{abort} \\ m &\in\mathrm{Message} ::= \operatorname{invoke}(p.f,v)\mid\operatorname{result}(v) \\ \mathcal{M} &= (\mathrm{State},s_{\mathcal{A}}^{\mathrm{init}},\rho,\delta)\quad\text{where }s_{\mathcal{A}}^{\mathrm{init}}\in\mathrm{State} \\ \rho&: \mathrm{State}\times\mathrm{Message}\to\mathrm{State}\qquad\delta:\mathrm{State}\to\mathrm{State}+(\mathrm{Action}\times\mathrm{State}) \end{aligned}

A program is IFC-typed when its interface is well-formed, and every function body is typed against the corresponding signature.

⊢W2Piff⊢W2I∧∀p,f.sig⁡(p.f)=τi→pcex⊵pcmaxτo∧body⁡(p.f)=λx.e⟹[τi];p;p;pcmax⊢W2e:τo⊔p\vdash_{\mathrm{W}_2}\mathcal{P}\quad\text{iff}\quad\vdash_{\mathrm{W}_2}\mathcal{I}\land\forall p,f.\quad\operatorname{sig}(p.f)=\tau_i\xrightarrow{p_{\mathrm{cex}}\mathrel{\trianglerighteq}p_{\mathrm{cmax}}}\tau_o\quad\land\quad\operatorname{body}(p.f)=\lambda x.e\quad\Longrightarrow\quad[\tau_i];p;p;p_{\mathrm{cmax}}\vdash_{\mathrm{W}_2}e:\tau_o\sqcup p

The body runs at pc pp with result τo⊔p\tau_o\sqcup p, which models auto-endorsement on entry and is exactly the trust that pcex⊑pcmax⊔pp_{\mathrm{cex}}\sqsubseteq p_{\mathrm{cmax}}\sqcup p in TI-App guards. Interfaces in World 1 are trivially well-formed, so ⊢W1P\vdash_{\mathrm{W}_1}\mathcal{P} holds when every body satisfies the ordinary typing judgment [⌊τi⌋];p⊢W1e:⌊τo⌋[\lfloor\tau_i\rfloor];p\vdash_{\mathrm{W}_1}e:\lfloor\tau_o\rfloor. From above, every IFC-typed program is also ordinarily typed (⊢W2P⟹⊢W1P\vdash_{\mathrm{W}_2}\mathcal{P}\Longrightarrow\vdash_{\mathrm{W}_1}\mathcal{P}).

Attackers

State Machine Attacker. Figure 8 presents the definition of a state machine attacker A=(A,sig⁡A,M)\mathcal{A}=(A,\operatorname{sig}_{\mathcal{A}},\mathcal{M}), which controls a set of principals A⊆PA\subseteq\mathcal{P} that forms a prime filter, as explained in § 3.3.1. The attacker’s behavior is given by an interactive state machine M\mathcal{M} with private state State [32]. Whenever control passes to the attacker, the receive function ρ\rho updates the state with the incoming message, which either invokes an attacker-owned function p.fp.f on an argument vv or returns a result vv from an earlier call. The transition function δ\delta then either takes an internal step or emits an action, calling a function vfv_f at label ℓ\ell, returning a value vv, or aborting. Because δ\delta is total, an attacker can spin by only taking internal steps. The state machine can model attacker code written in a different language.

Definition of a state machine attacker

Figure 8. An attacker A=(A,sig⁡A,M)\mathcal{A}=(A,\operatorname{sig}_{\mathcal{A}},\mathcal{M}) controls the principals AA, declares the signatures sig⁡A\operatorname{sig}_{\mathcal{A}}, and behaves as the state machine M\mathcal{M}, which receives messages via ρ\rho and emits actions via δ\delta.

Linking an attacker A\mathcal{A} with a program P\mathcal{P} is denoted by P⋈A\mathcal{P}\bowtie\mathcal{A}. The attacker contributes a finite signature table sig⁡A\operatorname{sig}_{\mathcal{A}}, which declares functions owned by principals in AA. The linked interface sig⁡⋈sig⁡A\operatorname{sig}\bowtie\operatorname{sig}_{\mathcal{A}} extends sig⁡\operatorname{sig} but never overrides the program’s own,

(sig⁡⋈sig⁡A)(p.f)={sig⁡(p.f)if p.f∈dom⁡(sig⁡)sig⁡A(p.f)otherwise(\operatorname{sig}\bowtie\operatorname{sig}_{\mathcal{A}})(p.f)= \begin{cases} \operatorname{sig}(p.f) & \text{if }p.f\in\operatorname{dom}(\operatorname{sig})\\ \operatorname{sig}_{\mathcal{A}}(p.f) & \text{otherwise} \end{cases}

Thus besides declaring new functions, the attacker can also replace an existing function, without changing its signature, if that function belongs to an attacker-controlled principal. Signatures of attacker functions are merely claims, because M\mathcal{M} is free to break them.

Attacker Boundary. The attacker and the program interact only across the boundary between them, where control enters M\mathcal{M} as a message and leaves it as an action. Each world admits a different class of attackers, and the classes differ only in the typing that M\mathcal{M} must respect at this boundary. The rest of this subsection defines the IFC-typed boundary for World 2 and the ordinarily typed boundary for World 1. Attackers in World 0 are unconstrained and attackers in World 3 are programs but not state machines. They are described in sections 5.2 and 5.3, respectively.

Reachable configurations of an attacker under typed messages

Figure 9. Reachable configurations of an attacker under typed messages.

A message mm or action aa is typed in a world W ∈{W1,W2}\in\{\mathrm{W}_1,\mathrm{W}_2\} against the signature of the function p.fp.f it concerns in the linked interface sig⋈sigA\mathrm{sig} \bowtie\mathrm{sig}_{\mathcal{A}}, written (sig⋈sigA)(p.f)=τi→pcmax⁡pcexτo(\mathrm{sig} \bowtie\mathrm{sig}_{\mathcal{A}})(p.f)=\tau_i \xrightarrow[\mathit{pc}_{\max}]{\mathit{pc}_{\mathrm{ex}}} \tau_o.

W = W₂W = W₁
⊢Winvoke⁡(p.f,v)\vdash_{\mathrm{W}} \operatorname{invoke}(p.f,v)p∈A∧∅;p;p;pcmax⁡⊢W2v:τip \in\mathcal{A} \land\varnothing;p;p;\mathit{pc}_{\max} \vdash_{\mathrm{W}_2} v:\tau_ip∈A∧∅;p⊢W1v:⌊τi⌋p \in\mathcal{A} \land\varnothing;p \vdash_{\mathrm{W}_1} v:\lfloor\tau_i\rfloor
p.f⊢Wresult⁡(v)p.f \vdash_{\mathrm{W}} \operatorname{result}(v)∅;p;p;pcmax⁡⊢W2v:τo⊔p\varnothing;p;p;\mathit{pc}_{\max} \vdash_{\mathrm{W}_2} v:\tau_o \sqcup p∅;p⊢W1v:⌊τo⌋\varnothing;p \vdash_{\mathrm{W}_1} v:\lfloor\tau_o\rfloor

An action emitted by p.fp.f is well typed when

W = W₂W = W₁
p.f⊢Wcall⁡(vf,ℓ,v)p.f \vdash_{\mathrm{W}} \operatorname{call}(v_f,\ell,v)∃pc,τ. p⊑pc∧∅;pc;p;pcmax⁡⊢W2vf[ℓ]v:τ\exists pc,\tau.\ p \sqsubseteq pc \land\varnothing;pc;p;\mathit{pc}_{\max} \vdash_{\mathrm{W}_2} v_f[\ell]v:\tau∃σ. ∅;p⊢W1vf[ℓ]v:σ\exists\sigma.\ \varnothing;p \vdash_{\mathrm{W}_1} v_f[\ell]v:\sigma
p.f⊢Wret⁡(v)p.f \vdash_{\mathrm{W}} \operatorname{ret}(v)∅;p;p;pcmax⁡⊢W2v:τo⊔p\varnothing;p;p;\mathit{pc}_{\max} \vdash_{\mathrm{W}_2} v:\tau_o \sqcup p∅;p⊢W1v:⌊τo⌋\varnothing;p \vdash_{\mathrm{W}_1} v:\lfloor\tau_o\rfloor
p.f⊢Wabort⁡p.f \vdash_{\mathrm{W}} \operatorname{abort}alwaysalways

A call is thus one that the attacker function could have made from some program point of a well-typed body, and a return delivers what a well-typed body of p.fp.f would produce. The World 1 judgments ⊢W1\vdash_{\mathrm{W}_1} use ordinary typing against ⌊τi⌋\lfloor\tau_i\rfloor and ⌊τo⌋\lfloor\tau_o\rfloor.

In Figure 9, a configuration (s,r,K)(s,r,K) pairs the state ss of M\mathcal{M} with the running attacker function rr, or r=−r=- when control is outside, and with a stack KK of pending calls. A pair (p.f,q.g)(p.f,q.g) in KK records that p.fp.f called q.gq.g and awaits its result. R-Invoke and R-Result are the only rules that receive messages, and both require those messages to be well-typed with respect to W. R-Result delivers a result only to the innermost pending call, which makes the run well-bracketed in the sense of game semantics [4]. No rule continues after an abort.

Definition 4.1 (Boundary typing). An attacker A\mathcal{A} is boundary-typed in W, written ⊢WA\vdash_{\mathrm{W}}\mathcal{A}, when A⊢W(s,p.f,K)\mathcal{A}\vdash_{\mathrm{W}}(s,p.f,K) and δ(s)=(a,s′)\delta(s)=(a,s') imply p.f⊢Wap.f\vdash_{\mathrm{W}}a.

A boundary-typed attacker is never the first to break typing [2]. The condition constrains A\mathcal{A} only after messages that a well-typed program can send.

Dynamic Semantics

Figure 10 gives the semantics of honest code in the standard style of evaluation contexts [43]. This semantics leaves every interaction with other principals to the linked semantics, which ensures that honest code runs the same way in every world (except for dynamic checks).

Since expressions are in A-normal form, an evaluation context EE is either a hole or a let whose bound expression is in focus, so EE serves naturally as a call frame. The store Σ\Sigma is the run-time state. The judgment ⟨e,Σ⟩⟶e⟨N,Σ′,η⃗⟩\langle e,\Sigma\rangle\longrightarrow_e \langle N,\Sigma',\vec{\eta}\rangle steps ee under principal pp to an outcome NN with a trace η⃗\vec{\eta} of at most one event. The outcome either continues as an expression e′e' or yields an action aa for

E::=[⋅]∣let⁡ x=E in⁡ eevaluation contextsE ::= [\cdot] \mid\operatorname{let}\ x = E\ \operatorname{in}\ e \qquad\text{evaluation contexts}
N::=e∣emit⁡(a;E)outcomesN ::= e \mid\operatorname{emit}(a;E) \qquad\text{outcomes}
⟨e,Σ⟩→pe⟨N,Σ′,η⃗⟩\langle e,\Sigma\rangle\xrightarrow{p}_{e} \langle N,\Sigma',\vec{\eta}\rangle
⟨v1⊗v2,Σ⟩→pe⟨v1⟦⊗⟧v2,Σ,ϵ⟩R-Op\frac{\langle v_1 \otimes v_2,\Sigma\rangle\xrightarrow{p}_{e} \langle v_1\llbracket\otimes\rrbracket v_2,\Sigma,\epsilon\rangle}{\text{R-Op}}
⟨if⁡ b then⁡ etrue else⁡ efalse,Σ⟩→pe⟨eb,Σ,ϵ⟩R-If\frac{\langle\operatorname{if}\ b\ \operatorname{then}\ e_{\mathrm{true}}\ \operatorname{else}\ e_{\mathrm{false}},\Sigma\rangle\xrightarrow{p}_{e} \langle e_b,\Sigma,\epsilon\rangle}{\text{R-If}}
⟨v↓ℓ,Σ⟩→pe⟨v,Σ,ϵ⟩R-Down\frac{\langle v\mathbin{\downarrow}\ell,\Sigma\rangle\xrightarrow{p}_{e} \langle v,\Sigma,\epsilon\rangle}{\text{R-Down}}
⟨let⁡ x=v in⁡ e,Σ⟩→pe⟨e{v/x},Σ,ϵ⟩R-Let\frac{\langle\operatorname{let}\ x=v\ \operatorname{in}\ e,\Sigma\rangle\xrightarrow{p}_{e} \langle e\{v/x\},\Sigma,\epsilon\rangle}{\text{R-Let}}
Σ(p,h)=v⟨read⁡h,Σ⟩→pe⟨v,Σ,ϵ⟩R-Read\frac{\Sigma(p,h)=v}{\langle\operatorname{read}_{h},\Sigma\rangle\xrightarrow{p}_{e} \langle v,\Sigma,\epsilon\rangle} \quad\text{R-Read}
Σ′=Σ[(p,h)↦v]⟨write⁡h(v),Σ⟩→pe⟨(),Σ′,(p.h:=obs⁡(v))⟩R-Write\frac{\Sigma'=\Sigma[(p,h)\mapsto v]}{\langle\operatorname{write}_{h}(v),\Sigma\rangle\xrightarrow{p}_{e} \langle(),\Sigma',(p.h:=\operatorname{obs}(v))\rangle} \quad\text{R-Write}
⟨vf[ℓ]v,Σ⟩→pe⟨emit⁡(call⁡(vf,ℓ,v);[⋅]),Σ,ϵ⟩R-Call\frac{\langle v_f[\ell]v,\Sigma\rangle\xrightarrow{p}_{e} \langle\operatorname{emit}(\operatorname{call}(v_f,\ell,v);[\cdot]),\Sigma,\epsilon\rangle}{\text{R-Call}}
⟨e,Σ⟩⟶⟨N,Σ′,η⃗⟩\langle e,\Sigma\rangle\longrightarrow\langle N,\Sigma',\vec{\eta}\rangle
⟨e,Σ⟩→pe⟨e′,Σ′,η⃗⟩⟨E[e],Σ⟩⟶⟨E[e′],Σ′,η⃗⟩S-Internal\frac{\langle e,\Sigma\rangle\xrightarrow{p}_{e} \langle e',\Sigma',\vec{\eta}\rangle}{\langle E[e],\Sigma\rangle\longrightarrow\langle E[e'],\Sigma',\vec{\eta}\rangle} \quad\text{S-Internal}
⟨e,Σ⟩→pe⟨emit⁡(a;[⋅]),Σ′,η⃗⟩⟨E[e],Σ⟩⟶⟨emit⁡(a;E),Σ′,η⃗⟩S-Emit\frac{\langle e,\Sigma\rangle\xrightarrow{p}_{e} \langle\operatorname{emit}(a;[\cdot]),\Sigma',\vec{\eta}\rangle}{\langle E[e],\Sigma\rangle\longrightarrow\langle\operatorname{emit}(a;E),\Sigma',\vec{\eta}\rangle} \quad\text{S-Emit}
⟨v,Σ⟩⟶⟨emit⁡(ret⁡(v);[⋅]),Σ,ϵ⟩S-Ret\frac{\langle v,\Sigma\rangle\longrightarrow\langle\operatorname{emit}(\operatorname{ret}(v);[\cdot]),\Sigma,\epsilon\rangle}{\text{S-Ret}}
⟨E[abort⁡],Σ⟩⟶⟨emit⁡(abort⁡;E),Σ,ϵ⟩S-Abort\frac{\langle E[\operatorname{abort}],\Sigma\rangle\longrightarrow\langle\operatorname{emit}(\operatorname{abort};E),\Sigma,\epsilon\rangle}{\text{S-Abort}}

Fig. 10. Operational semantics of honest code.

linked semantics together with an evaluation context. The judgment ⟶\longrightarrow lifts →pe\xrightarrow{p}_{e} through evaluation contexts, where S-Internal covers internal steps and the remaining rules cover interactions.

Most rules for the honest program’s operational semantics are standard. R-Op, R-If and R-Let reduce operators, branches and lets as usual, and R-Down leaves its value unchanged since a downgrade affects only the static type. R-Read and R-Write access only the running principal’s cell (p,h)(p,h), and as is standard we treat each write as an effect and record its update as an event. The event shows obs⁡(v)\operatorname{obs}(v), with obs⁡(q.g)=()\operatorname{obs}(q.g)=() and obs⁡(v)=v\operatorname{obs}(v)=v otherwise, since a pointer is observable only by calling it.

Calls, returns and aborts are the only ways to interact with other principals. R-Call turns a call into a call action, and S-Emit passes this action to the linked semantics along with its call frame EE, so the caller resumes as E[v]E[v] once the call returns vv. A body that reduces to a value hands it back to its caller through S-Ret, and an abort anywhere in the body ends the whole run through S-Abort.

Linked Semantics. Honest code and the attacker machine M\mathcal{M} are each an open system whose interactions with the other side remain unresolved. The linked semantics accounts for the interaction of two heterogeneous parties [23], and closes the system by running both over one shared call stack

ϕ::=toH⁡(p.f,e)∣toA⁡(p.f,F)S::=∅∣ϕ::S\phi::= \operatorname{toH}(p.f,e) \mid\operatorname{toA}(p.f,F) \qquad S ::= \varnothing\mid\phi:: S

The call stack’s head is the running frame, and its tail holds the awaited callers. An honest frame holds the expression that p.fp.f evaluates, and an attacker frame holds an abstract frame FF whose form depends on the attacker; for the state machine M\mathcal{M}, which keeps its continuation in its state, FF is trivially the unit value and we write toA⁡(p.f)\operatorname{toA}(p.f) for convenience. We write ϕ.fn\phi.\mathit{fn} for the function that a frame ϕ\phi runs.

A configuration C=⟨sA,Σ,S⟩C = \langle s_{\mathcal{A}}, \Sigma, S\rangle holds the attacker state sAs_{\mathcal{A}}, the store Σ\Sigma and the stack SS. A run halts on an empty stack. Each world WW defines a step relation C⟶W⟨C′,η⃗⟩C \mathrel{\longrightarrow_W} \langle C', \vec{\eta}\rangle that emits a trace η⃗\vec{\eta} of at most one event, and its reflexive, transitive closure C⟶W∗⟨C′,η⃗⟩C \mathrel{\longrightarrow_W^*} \langle C', \vec{\eta}\rangle concatenates the emitted events. Linking requires an implementation for every honest function declared in sig\mathit{sig}. A run starts from an initial store Σinit\Sigma_{\mathrm{init}}, with M\mathcal{M} running the attacker-owned entry ⊤.entry\top.\mathit{entry} on the unit value.

Cinit=⟨ρ(sAinit,invoke⁡(⊤.entry,())),Σinit,toA⁡(⊤.entry)::∅⟩C_{\mathrm{init}} = \langle\rho(s_{\mathcal{A}}^{\mathrm{init}}, \operatorname{invoke}(\top.\mathit{entry}, ())), \Sigma_{\mathrm{init}}, \operatorname{toA}(\top.\mathit{entry}) :: \varnothing\rangle

Figure 11 defines the linked semantics in two layers. The frame step ⟶W\mathrel{\longrightarrow_W} advances the top frame in isolation and produces either an updated frame or an action a∈Actiona \in\mathit{Action}. An honest frame running p.fp.f steps its expression under the honest semantics at principal pp. Specifically, an internal step updates the frame (F-Honest), and an action leaves the frame in place to await a return (F-Honest-Act), both of which may modify the store Σ\Sigma. Similarly, an attacker frame steps by δ\delta to a new state (F-Attacker) or an action (F-Attacker-Act).

Frame and linked steps

Figure 11. Frame and linked steps.

The linked step ⟶W\mathrel{\longrightarrow_W} advances the whole configuration according to the outcome of ⟶W\mathrel{\longrightarrow_W}. L-Step replaces the top frame with the result of one internal step. L-Call requires the called value vfv_f to be a pointer declared in the linked signature table sig⊳sigA\mathit{sig} \rhd\mathit{sig}_{\mathcal{A}}. The rule then calls vfv_f at pc  p⊔ℓpc\;p \sqcup\ell,

callW⁡(sA,S,pc,vf,v)={⟨ρ(sA,invoke⁡(q.g,v)),toA⁡(q.g)::S,ϵ⟩if q∈A⟨sA,toH⁡(q.g,e{v′/x})::S,call⁡obs⁡(pc)(q.g)⟩if dynCheck⁡W(S,pc,q.g,pcex),admit⁡W(τi,v)=v′and body⁡(q.g)=λx.e⟨sA,∅,ζ⟩otherwise\operatorname{callW}(s_{\mathcal{A}}, S, pc, v_f, v) = \begin{cases} \langle\rho(s_{\mathcal{A}}, \operatorname{invoke}(q.g,v)), \operatorname{toA}(q.g) :: S, \epsilon\rangle& \text{if } q \in A \\ \langle s_{\mathcal{A}}, \operatorname{toH}(q.g,e\{v'/x\}) :: S, \operatorname{call}^{\operatorname{obs}(pc)}(q.g) \rangle& \text{if } \operatorname{dynCheck}_{W}(S,pc,q.g,pc_{\mathrm{ex}}),\\ & \quad\operatorname{admit}_{W}(\tau_i,v)=v'\\ & \quad\text{and } \operatorname{body}(q.g)=\lambda x.e\\ \langle s_{\mathcal{A}},\varnothing,\zeta\rangle& \text{otherwise} \end{cases}

where vf=q.gv_f=q.g and (sig⁡⋈sig⁡A)(q.g)=τi→pcex◃pcmax⁡τo(\operatorname{sig}\bowtie\operatorname{sig}_{\mathcal{A}})(q.g)=\tau_i \xrightarrow{pc_{\mathrm{ex}}\triangleleft pc_{\max}} \tau_o

retW⁡(sA,ϕ,S,p.f,v)={⟨ρ(sA,result⁡(v)),toA⁡(q.g)::S,η⃗p⟩if ϕ=toA⁡(q.g)⟨sA,toH⁡(q.g,E[v′])::S,η⃗p⟩if ϕ=toH⁡(q.g,E[vf[ℓ]u])⟨sA,∅,ζ⟩otherwise\operatorname{retW}(s_{\mathcal{A}},\phi,S,p.f,v)= \begin{cases} \langle\rho(s_{\mathcal{A}},\operatorname{result}(v)),\operatorname{toA}(q.g)::S,\vec{\eta}_p\rangle& \text{if } \phi=\operatorname{toA}(q.g)\\ \langle s_{\mathcal{A}},\operatorname{toH}(q.g,E[v'])::S,\vec{\eta}_p\rangle& \text{if } \phi=\operatorname{toH}(q.g,E[v_f[\ell]u])\\ \langle s_{\mathcal{A}},\varnothing,\zeta\rangle& \text{otherwise} \end{cases}

where (sig⁡⋈sig⁡A)(p.f)=τi→pcex◃pcmax⁡τo(\operatorname{sig}\bowtie\operatorname{sig}_{\mathcal{A}})(p.f)=\tau_i \xrightarrow{pc_{\mathrm{ex}}\triangleleft pc_{\max}} \tau_o and η⃗p={ϵif p∈Aret⁡(p)otherwise\vec{\eta}_p = \begin{cases} \epsilon& \text{if } p\in A\\ \operatorname{ret}(p) & \text{otherwise} \end{cases}

which implies that no call is more trusted than its caller. L-Ret pops the returning frame and passes the result vv to ret⁡W\operatorname{ret}_{W} together with the caller’s frame ϕ1\phi_1, as vv is treated differently for honest and adversarial callers, as indicated below.

The helper functions call⁡W\operatorname{call}_{W} and ret⁡W\operatorname{ret}_{W} share the same structure. The former pushes a frame for the callee q.gq.g and records call⁡obs⁡(pc)(q.g)\operatorname{call}^{\operatorname{obs}(pc)}(q.g), and the latter resumes the caller and records η⃗p\vec{\eta}_p. The events record only what the trusted party sees [7], namely the activations of honest code, with each call event marking an honest frame’s entry and each return its exit. Calls into the attacker and returns from it are therefore silent, and obs⁡(pc)\operatorname{obs}(pc) replaces an attacker label with ⊤\top.

The attacker accepts every value without checks. On a message, either invoke⁡(q.g,v)\operatorname{invoke}(q.g,v) or result⁡(v)\operatorname{result}(v), the attacker steps into a new state via ρ\rho. In contrast, a value can be passed into the honest party only after it has been vetted by the run-time check in that world. A call must pass dynCheck⁡W\operatorname{dynCheck}_{W}, and admit⁡W\operatorname{admit}_{W} converts the argument at the callee’s input type τi\tau_i and the result at its output type τo\tau_o. If any check fails, the run aborts.

Dynamic Checks. Figure 12 shows the semantics of call and return. The dynamic checks are defined in dynCheck⁡W\operatorname{dynCheck}_{W}. The partial function admit⁡W(τ,v)\operatorname{admit}_{W}(\tau,v) converts a value vv entering honest code at type τ\tau and is undefined on values the world intends to reject. The total function use⁡W(p.f,e)\operatorname{use}_{W}(p.f,e) converts the values that the next step of ee uses, before F-Honest and F-Honest-Act take that step. For instance, World 2 permits every call and passes every value unchanged:

Call and return semantics

Figure 12. Call and return semantics. The function dynCheck⁡W\operatorname{dynCheck}_{W} defines the run-time checks.

dynCheck⁡W2(S,pc,q.g,pcex) always holdsadmit⁡W2(τ,v)=vuse⁡W2(p.f,e)=e\operatorname{dynCheck}_{W_2}(S,pc,q.g,pc_{\mathrm{ex}})\ \text{always holds} \qquad \operatorname{admit}_{W_2}(\tau,v)=v \qquad \operatorname{use}_{W_2}(p.f,e)=e

World 1 also passes every value unchanged, but checks each call at run time:

dynCheck⁡W1(S,pc,q.g,pcex)iffpc⊑pcex∧∀L∈locks⁡(S). pc⊑q⊔L\operatorname{dynCheck}_{W_1}(S,pc,q.g,pc_{\mathrm{ex}}) \quad\text{iff}\quad pc\sqsubseteq pc_{\mathrm{ex}}\land\forall L\in\operatorname{locks}(S).\ pc\sqsubseteq q\sqcup L

where locks⁡(S)\operatorname{locks}(S) is the set of principals with an honest frame on SS. The condition pc⊑pcexpc\sqsubseteq pc_{\mathrm{ex}} enforces the callee’s external pcpc, and pc⊑q⊔Lpc\sqsubseteq q\sqcup L enforces the reentrancy lock that each honest principal LL on the stack holds until it returns. Intuitively, an attacker pcpc lies in AA and, by primality, never flows to q⊔Lq\sqcup L for honest qq and LL, so the attacker cannot call honest code at all once an honest frame is on the stack.

Type-Confusion Security via Simulation

We now show that the type-confusion security definition from §3 holds for worlds W0W_0 and W3W_3.

The behavior of a linked system is what an observer sees over an entire run. Since runs are deterministic, the traces reachable from the initial configuration CinitC_{\mathrm{init}} form a chain under the prefix order, and the behavior is their least upper bound, a (possibly infinite) trace. When linking a trusted open program P\mathcal{P} with an attacker A\mathcal{A} succeeds—namely, when every honest function declared in sig is defined—the behavior of running the linked system in world WW from store Σ\Sigma is:

⟦P⋈A⟧W(Σ)=⨆{η⃗∣Cinit⟶W∗⟨C,η⃗⟩}.\llbracket\mathcal{P} \bowtie\mathcal{A} \rrbracket_W(\Sigma) = \bigsqcup\left\{ \vec{\eta} \mid C_{\mathrm{init}} \mathrel{\longrightarrow^{*}_{W}} \langle C,\vec{\eta}\rangle\right\}.

Note that a run that halts ends its trace with ✓ or ⊥. Equivalently, we can describe the behavior as the set of finite prefixes of traces.

We compare behaviors only from initial stores whose trusted cells hold values of their declared types under IFC typing, since the trusted program is IFC-typed. A store is well typed for a cell table cell when every cell declared in cell holds a value of its type,

cell⊢Σiff∀p,h,pc,pcmax⁡. cell(p,h)=τ⟹∅;pc;p;pcmax⁡⊢W2Σ(p,h):τ\mathrm{cell} \vdash\Sigma\quad\text{iff}\quad\forall p,h,pc,pc_{\max}.\ \mathrm{cell}(p,h)=\tau\Longrightarrow\varnothing;pc;p;pc_{\max}\vdash_{W_2}\Sigma(p,h):\tau

and we write ⊢Σ\vdash\Sigma for cell↾Aˉ⊢Σ\mathrm{cell}\mathbin{\upharpoonright}_{\bar{A}}\vdash\Sigma, the restriction of cell to the principals outside AA.

It remains to refine type-confusion security.

Definition 5.1 (Simulation). Consider worlds WW and W′W' and a trusted program P\mathcal{P} with ⊢W2P\vdash_{W_2}\mathcal{P}. World W′W' simulates WW, written W⪯W′W \preceq W', meaning that WW’s attackers are no stronger than W′W'’s, iff

∀AW. ⊢WAW⟹∃AW′. ⊢W′AW′∧∀Σ. ⊢Σ⟹⟦P⋈AW⟧W(Σ)=⟦P⋈AW′⟧W′(Σ)\forall\mathcal{A}_W.\ \vdash_W\mathcal{A}_W \Longrightarrow\exists\mathcal{A}_{W'}.\ \vdash_{W'}\mathcal{A}_{W'}\land\forall\Sigma.\ \vdash\Sigma\Longrightarrow\llbracket\mathcal{P}\bowtie\mathcal{A}_W\rrbracket_W(\Sigma)=\llbracket\mathcal{P}\bowtie\mathcal{A}_{W'}\rrbracket_{W'}(\Sigma)

Theorem 5.2 (Type-Confusion Security). If ⊢W2P\vdash_{W_2}\mathcal{P}, then W0≈W1≈W2≈W3W_0\approx W_1\approx W_2\approx W_3. That is, Figure 4 holds.

Simulation between Worlds 1 and 2

Worlds 1 and 2 are equivalent for IFC-typed programs. World 1’s weaker type system lets attackers confuse IFC labels, and the run-time check removes exactly this power.

The direction W2⪯W1W_2\preceq W_1 is almost trivial. Consider an attacker AW2=(A,sigA,M)\mathcal{A}_{W_2}=(A,\mathrm{sig}_{\mathcal{A}},\mathcal{M}) that is boundary-typed in W2W_2. Against an IFC-typed program, AW2\mathcal{A}_{W_2} emits only actions well typed in W2W_2, which pass the run-time check, so AW2\mathcal{A}_{W_2} behaves the same in both worlds. The only complication arises when reasoning about AW2\mathcal{A}_{W_2}’s boundary typing in W1W_1, which also covers messages that are typed in W1W_1 but not in W2W_2, on which AW2\mathcal{A}_{W_2} may emit an action ill typed in W1W_1. The simulator AW1\mathcal{A}_{W_1} therefore runs M\mathcal{M} behind a guard. Its transition function δW1\delta_{W_1} follows δ\delta, except that an action aa with p.f̸⊢W1ap.f\not\vdash_{W_1}a is replaced by an internal step that leaves the state unchanged, where p.fp.f is the running function. Against an IFC-typed program, δW1\delta_{W_1} coincides with δ\delta.

For W1⪯W2W_1\preceq W_2, the simulator runs AW1\mathcal{A}_{W_1} unchanged in W2W_2 since such an attacker respects ordinary types but not labels. Moreover, both the functions a W1W_1 attacker passes to honest code and the calls it makes may carry labels that IFC typing rejects.

Figure 13 sketches the simulator AW2\mathcal{A}_{W_2} for AW1\mathcal{A}_{W_1}. First, a call between two functions owned by AW1\mathcal{A}_{W_1} emits no observable event, but the labels of the passed arguments may not be IFC-typed, which violates boundary typing. AW2\mathcal{A}_{W_2} therefore emulates such a call in-house (Figure 13a) instead of explicitly emitting such a call.

Simulator between worlds

Figure 13. Simulator AW2\mathcal{A}_{W_2} for AW1\mathcal{A}_{W_1}. Shaded boxes contain attacker functions; gg is honest. Dashed arrows denote internal simulation steps.

Then, AW1\mathcal{A}_{W_1} may hand a pointer to one of its functions ff to honest code, which expects a type τ=(τi pcexppcmax⁡τo)ℓ\tau=(\tau_i\ \frac{pc_{\mathrm{exp}}}{pc_{\max}}\tau_o)_\ell. Ordinary typing, however, checks ff only against [τ][\tau], so a label mismatch may leave ∅;pc;p′;pcmax⁡̸⊢W2f:τ\varnothing;pc;p';pc_{\max}\not\vdash_{W_2}f:\tau for all allowed labels. In this case, AW2\mathcal{A}_{W_2} instead hands over a pointer to an adapter fτf^\tau (Figure 13b), a fresh function whose signature is derived from τ\tau. Specifically, pointer to fτf^\tau has type (τi⊔⊤→pcex⊔p▹pcmax⊓pτo)p(\tau_i \sqcup\top\xrightarrow{pcex \sqcup p \triangleright pcmax \sqcap p} \tau_o)_p, which is a subtype of τ\tau at label pp. Since a pointer is labeled by the owner of its function, AW2\mathcal{A}_{W_2} picks p=ℓ⊔qp = \ell\sqcup q, which is an attacker principal by upward closure of AA. Here qq is the owner of the function of AW1\mathcal{A}_{W_1} that returns the pointer, because a returned value also carries the label of its function, and q=⊥q = \bot when the pointer is passed as an argument instead. The adapter has no behavior of its own; when honest code calls fτf^\tau, AW2\mathcal{A}_{W_2} runs AW1\mathcal{A}_{W_1} at ff. Honest code may also hand this pointer back, and AW2\mathcal{A}_{W_2} then replaces it by the pointer to ff, which is what AW1\mathcal{A}_{W_1} would receive in W1W_1.

Finally, AW1\mathcal{A}_{W_1} may call an honest function gg with external pc pcexpcex, which the run-time check of W1W_1 (§ 4.4) permits only when no honest frame is on the stack. IFC typing, however, rejects this call from the outermost frame of AW2\mathcal{A}_{W_2}, which runs at ⊤\top. AW2\mathcal{A}_{W_2} therefore detours through a trampoline trpcextr_{pcex} (Figure 13c), a fresh function declared at 1→⊤⊑111 \xrightarrow{\top\sqsubseteq1} 1, which any frame may call. The trampoline then completes the call of gg at pcexpcex, which is an attacker principal due to upward closure of AA. Because trpcextr_{pcex} serves every call with external pc pcexpcex, it takes only a unit argument, so the actual argument travels through the private state of AW2\mathcal{A}_{W_2}, with each function pointer replaced by its adapter at τi\tau_i, and the result returns the same way. The program mentions only finitely many types and labels, so AW2\mathcal{A}_{W_2} declares only finitely many adapters and trampolines.

AW2\mathcal{A}_{W_2} must abort whenever W1W_1 refuses a call. This happens when a call of AW1\mathcal{A}_{W_1} into honest code fails the run-time check, and when honest code calls a pointer to an honest function that AW1\mathcal{A}_{W_1} handed over. That pointer carries an attacker label, so in W1W_1 honest code calls it at an attacker pc above its own frame, which the run-time check refuses, whereas in W2W_2 the call reaches an adapter. As in the proof of W2≈W1W_2 \approx W_1, a guard for W2W_2 makes AW2\mathcal{A}_{W_2} boundary-typed by construction.

The proof relates each configuration of W1W_1 running AW1\mathcal{A}_{W_1} to one of W2W_2 running AW2\mathcal{A}_{W_2}, where both hold the same state of AW1\mathcal{A}_{W_1} and their honest code and cells agree once adapters are renamed back. Each step in World 1 is matched by one step in World 2, or by two through a trampoline, where the extra step is silent since the trampoline belongs to the attacker. When W1W_1 is stuck, AW2\mathcal{A}_{W_2} spins silently, and on related runs the guard never intervenes. Therefore, both runs produce the same behavior, and we can conclude that W1≈W2W_1 \approx W_2.

Simulation between Worlds 0 and 1

In reality, an attacker need not respect even ordinary types. It may hand honest code a number or a pointer where a boolean is expected, and the honest code must somehow interpret that value. This interpretation is modeled by a function castcast, where cast(v,σ)cast(v,\sigma) is ν\nu reinterpreted at an unlabeled type σ\sigma. We assume that a cast to a data type boolbool, natnat or 11 yields a value of that type, while a to a pointer type may not. Honest code normalizes such a value using coerce⁡(v,σ)\operatorname{coerce}(v,\sigma), which returns vv if it has type σ\sigma, and cast⁡(v,σ)\operatorname{cast}(v,\sigma) otherwise. The result is therefore well typed at every data type.

Like World 1, World 0 changes only the run-time checks (§ 4.4). It keeps the lock check, dynCheck⁡W0=dynCheck⁡W1\operatorname{dynCheck}_{W_0}=\operatorname{dynCheck}_{W_1}, and applies coerce⁡\operatorname{coerce} to pointers and data at different points. A pointer is coerced eagerly as it crosses the boundary. If σ=⌊τ⌋\sigma=\lfloor\tau\rfloor is not a data type, then admit⁡W0(τ,v)\operatorname{admit}_{W_0}(\tau,v) is coerce⁡(v,σ)\operatorname{coerce}(v,\sigma) when that value has type σ\sigma, and the run aborts otherwise. When σ\sigma is a data type, vv passes unchanged. Intuitively, since the signature table is fixed at compile time, an ill-typed pointer cannot be repaired, so honest code must reject it before running.

Data is instead coerced lazily. The check use⁡W0\operatorname{use}_{W_0} coerces such a value at the type of that use and leaves every other expression unchanged,

use⁡W0(p.f,E[if v then e1 else e2])=E[if coerce⁡(v,bool) then e1 else e2]use⁡W0(p.f,E[v1⊗v2])=E[coerce⁡(v1,σ⊗)⊗coerce⁡(v2,σ⊗)]use⁡W0(p.f,E[write⁡h(v)])=E[write⁡h(coerce⁡(v,⌊cell⌋(p,h)))]use⁡W0(p.f,E[q.g[ℓ]v])=E[q.g[ℓ]coerce⁡(v,σi)]use⁡W0(p.f,v)=coerce⁡(v,σo′)\begin{aligned} \operatorname{use}_{W_0}(p.f,E[\text{if }v\text{ then }e_1\text{ else }e_2]) &= E[\text{if }\operatorname{coerce}(v,\mathrm{bool})\text{ then }e_1\text{ else }e_2] \\ \operatorname{use}_{W_0}(p.f,E[v_1\mathbin{\otimes}v_2]) &= E[\operatorname{coerce}(v_1,\sigma_{\otimes})\mathbin{\otimes}\operatorname{coerce}(v_2,\sigma_{\otimes})] \\ \operatorname{use}_{W_0}(p.f,E[\operatorname{write}_{h}(v)]) &= E[\operatorname{write}_{h}(\operatorname{coerce}(v,\lfloor\mathrm{cell}\rfloor(p,h)))] \\ \operatorname{use}_{W_0}(p.f,E[q.g[\ell]v]) &= E[q.g[\ell]\operatorname{coerce}(v,\sigma_i)] \\ \operatorname{use}_{W_0}(p.f,v) &= \operatorname{coerce}(v,\sigma'_o) \end{aligned}

where σ⊗\sigma_{\otimes} is the operand type of ⊗\otimes, σi\sigma_i is the input type of ⌊sig⌋(q.g)\lfloor\mathrm{sig}\rfloor(q.g) and σo′\sigma'_o is the output type of ⌊sig⌋(p.f)\lfloor\mathrm{sig}\rfloor(p.f). A return also counts as a use, so a confused value never leaves honest code.

As in § 5.1, we prove W0≈W1W_0\approx W_1 by showing that each world simulates the other (theorem 5.1). The direction W1⪯W0W_1\preceq W_0 is immediate. An attacker boundary-typed in W1W_1 is also an attacker in W0W_0. By the boundary typing of AW1\mathcal{A}_{W_1}, every value that reaches honest code is well typed. As a consequence, admit⁡W0\operatorname{admit}_{W_0} and use⁡W0\operatorname{use}_{W_0} do not change values, and the two worlds run in lockstep.

Conversely, an attacker AW0\mathcal{A}_{W_0} of W0W_0 may send ill-typed values, which no boundary-typed attacker in W1W_1 can. As a result, we construct the simulator AW1\mathcal{A}_{W_1} to run AW0\mathcal{A}_{W_0} and cast eagerly. The simulator replaces each value vv that AW0\mathcal{A}_{W_0} sends to honest code at type σ\sigma by the value that W0W_0 eventually uses (i.e., coerce⁡(v,σ)\operatorname{coerce}(v,\sigma)), and aborts whenever W0W_0 rejects an ill-typed pointer.

A call of AW0\mathcal{A}_{W_0} to its own function hh raises a further problem, since AW0\mathcal{A}_{W_0} may pass hh an argument of any type, which W0W_0 hands to hh unchanged. Coercing it would change what hh receives, so, as in the proof of W1≈W2W_1\approx W_2 (§ 5.1), AW1\mathcal{A}_{W_1} instead calls a fresh trampoline of hh, declared at 1→11\to1, with ()(), and the actual argument and result travel through the private state of AW1\mathcal{A}_{W_1}. Every action of AW1\mathcal{A}_{W_1} is therefore boundary-typed in W1W_1, and the two worlds run in lockstep, so W0≈W1W_0\approx W_1.

Simulation between Worlds 2 and 3

An attacker in World 2 is an arbitrary state machine, whose state and transitions need not be expressible in our language. We show that this generality gives the attacker no additional power by expressing every World 2 attacker as well-typed code with stateless external functions.

World 3 Attacker. Attacker code A=(A,IA,body⁡A,XA,ΣA)\mathcal{A}=(A,I_{\mathcal{A}},\operatorname{body}_{\mathcal{A}},X_{\mathcal{A}},\Sigma_{\mathcal{A}}) consists of an interface IA=(sig⁡A,cell⁡A)I_{\mathcal{A}}=(\operatorname{sig}_{\mathcal{A}},\operatorname{cell}_{\mathcal{A}}) at principals in AA, a body table body⁡A\operatorname{body}_{\mathcal{A}}, a table XA:P×FunName→fin(Value→Value)X_{\mathcal{A}}:\mathbb{P}\times\mathrm{FunName}\to_{\mathrm{fin}}(\mathrm{Value}\to\mathrm{Value}) of stateless external functions private to the attacker, and a store ΣA\Sigma_{\mathcal{A}}. Unlike a state machine, whose frame FF into toA⁡(p.f,F)\operatorname{toA}(p.f,F) is trivial (§ 4.4), attacker code follows honest code and takes FF to be the expression ee that p.fp.f evaluates. World 3 keeps the linked semantics and changes only the rules for attacker frames, which now step by the operational semantics of the honest party on ΣA\Sigma_{\mathcal{A}} without emitting any events. That is, we replace F-Attacker and F-Attacker-Act with the following rules:

F-Code

⟨e,ΣA⟩→p⟨e′,ΣA′,η⟩⟨toA⁡(p.f,e),ΣA,Σ⟩→W3⟨toA⁡(p.f,e′),ΣA′,Σ,ϵ⟩\frac{\langle e,\Sigma_{\mathcal{A}}\rangle\xrightarrow{p} \langle e',\Sigma'_{\mathcal{A}},\eta\rangle}{\langle\operatorname{toA}(p.f,e),\Sigma_{\mathcal{A}},\Sigma\rangle\to_{W_3}\langle\operatorname{toA}(p.f,e'),\Sigma'_{\mathcal{A}},\Sigma,\epsilon\rangle}

F-Code-Act

⟨e,ΣA⟩→p⟨emit⁡(a;E),ΣA′,ϵ⟩⟨toA⁡(p.f,e),ΣA,Σ⟩→W3⟨a,ΣA′,Σ⟩\frac{\langle e,\Sigma_{\mathcal{A}}\rangle\xrightarrow{p} \langle\operatorname{emit}(a;E),\Sigma'_{\mathcal{A}},\epsilon\rangle}{\langle\operatorname{toA}(p.f,e),\Sigma_{\mathcal{A}},\Sigma\rangle\to_{W_3}\langle a,\Sigma'_{\mathcal{A}},\Sigma\rangle}

Consequently, calls into and returns to attacker code no longer pass through ρ\rho, the receive function of the state machine. As with honest code, a call to q.gq.g with vv pushes the frame toA(q.g,e{v/x})_{\mathcal{A}}(q.g,e\{v/x\}) when body⁡A(q.g)=λx.e\operatorname{body}_{\mathcal{A}}(q.g)=\lambda x.e, or toA(q.g,XA(q.g)(v))_{\mathcal{A}}(q.g,X_{\mathcal{A}}(q.g)(v)) when q.gq.g is external, and a result returned to an attacker frame is plugged into its suspended expression.

Attacker code is well typed when its interface agrees with the program’s, its bodies and cells are well typed against the linked interface, and its external functions are private and respect their signatures,

⊢W3A⟺I≃IA∧I⋈IA⊢W2body⁡A∧cell⁡A⊢ΣA∧∀p.f∈dom⁡(XA). p.f∉dom⁡(sig⁡)∧∀p.f∈dom⁡(XA),v. v⊢W2invoke⁡(p.f,v)⟹p.f⊢W2result⁡(XA(p.f)(v))\begin{aligned} \vdash_{\mathrm{W}_{3}}\mathcal{A} &\Longleftrightarrow I \mathrel{\simeq} I_{\mathcal{A}} \land I \mathrel{\bowtie} I_{\mathcal{A}}\vdash_{\mathrm{W}_{2}}\operatorname{body}_{\mathcal{A}} \land\operatorname{cell}_{\mathcal{A}}\vdash\Sigma_{\mathcal{A}}\\ &\quad\land\forall p.f\in\operatorname{dom}(X_{\mathcal{A}}).~p.f\notin\operatorname{dom}(\operatorname{sig})\\ &\quad\land\forall p.f\in\operatorname{dom}(X_{\mathcal{A}}),v.~v\vdash_{\mathrm{W}_{2}}\operatorname{invoke}(p.f,v)\Longrightarrow p.f\vdash_{\mathrm{W}_{2}}\operatorname{result}(X_{\mathcal{A}}(p.f)(v)) \end{aligned}

where I≃IAI \mathrel{\simeq} I_{\mathcal{A}} means the two interfaces agree on every function and cell they both declare (§B.1), and I⋈IAI \mathrel{\bowtie} I_{\mathcal{A}} is their componentwise link (sig⁡⋈sig⁡A\operatorname{sig}\mathrel{\bowtie}\operatorname{sig}_{\mathcal{A}}, cell⁡⋈cell⁡A\operatorname{cell}\mathrel{\bowtie}\operatorname{cell}_{\mathcal{A}}). cell⁡⋈cell⁡A\operatorname{cell}\mathrel{\bowtie}\operatorname{cell}_{\mathcal{A}} is defined the same way as linking in § 4.3 (§B.1).

As before, W3≈W2W_{3}\approx W_{2} follows from two simulations. The direction W3⪯W2W_{3}\preceq W_{2} holds by type safety. Given well-typed code A\mathcal{A}, we construct a state machine simulator whose state is ΣA\Sigma_{\mathcal{A}} and the frames of A\mathcal{A}. The simulator has the same behaviors as A\mathcal{A}, since its receive function ρ\rho starts the body of A\mathcal{A} on each invocation and continues the waiting call on each result, and its transition δ\delta steps that call by F-Code and F-Code-Act. The simulator is boundary-typed in W2W_{2}, since by progress and preservation every action that well-typed code emits is well typed.

The converse direction W2⪰W3W_{2}\succeq W_{3} is harder, since M\mathcal{M} may be any state machine, while attacker code has only typed cells and stateless external functions. Given an attacker AW2=(A,sig⁡A,M)\mathcal{A}_{W_{2}}=(\mathcal{A},\operatorname{sig}_{\mathcal{A}},\mathcal{M}), we construct code AW3\mathcal{A}_{W_{3}} that runs M\mathcal{M} step by step. The code keeps the execution history of M\mathcal{M} in a single cell hhisth_{\mathrm{hist}} of type nat⁡⊤\operatorname{nat}_{\top}, which records every invocation and every result that M\mathcal{M} receives and every step that M\mathcal{M} takes. For each function ff of AW2\mathcal{A}_{W_{2}}, the code of ff in AW3\mathcal{A}_{W_{3}} records the invocation in hhisth_{\mathrm{hist}} and then repeatedly obtains the next step of M\mathcal{M} from an external function that replays the history, recording and performing each such step.

The code AW3\mathcal{A}_{W_{3}} has the same behavior as AW2\mathcal{A}_{W_{2}}, since AW3\mathcal{A}_{W_{3}} performs every step of M\mathcal{M} with only silent bookkeeping steps in between. The code AW3\mathcal{A}_{W_{3}} is also well typed, since the external functions of AW3\mathcal{A}_{W_{3}} return a default value of the declared type on any input whose replay yields an ill-typed value, and the code of ff would diverge on a call to a function that ff may not call. Neither fallback occurs, since every history in hhisth_{\mathrm{hist}} arises from a run of M\mathcal{M} and AW2\mathcal{A}_{W_{2}} is boundary-typed.

Applications

We can now prove that well-typed programs are free of confused deputy and reentrancy attacks in all worlds, W0W_{0} to W3W_{3}. Each property is proved in a single world and transfers to the other worlds by theorem 5.2.

Confused Deputy Attacks

A CDA happens when an attacker calls a trusted function from a context less trusted than the function’s external pc admits.

Definition 6.1 (CDA Security). Consider a program P\mathcal{P} and a world W. We say that P\mathcal{P} is free from confused-deputy attacks in W if, for all attackers AW\mathcal{A}_{W} and stores Σ\Sigma such that ⊢WAW\vdash_{W}\mathcal{A}_{W} and ⊢Σ\vdash\Sigma and η⃗=⟦P⋈AW⟧W(Σ)\vec{\eta}=\llbracket\mathcal{P}\mathbin{\Join}\mathcal{A}_{W}\rrbracket_{W}(\Sigma), the following holds.

∀call⁡pc(q.g)∈η⃗. (pc∈A⟹pcex∈A)∧(pc∉A⟹pc⊆pcex)\forall\operatorname{call}^{pc}(q.g)\in\vec{\eta}.~(pc\in A\Longrightarrow pc_{\mathrm{ex}}\in A)\land(pc\notin A\Longrightarrow pc\subseteq pc_{\mathrm{ex}})

where sig⁡(q.g)=τi pcex▹pcmax( τo\operatorname{sig}(q.g)=\tau_i\ \frac{pc_{\mathrm{ex}}\mathrel{\triangleright}pc_{\mathrm{max}}}{\mathstrut}\ \tau_o and AA is the set of attacker-controlled labels.

For an attacker call, theorem 6.1 requires only pex∈Ap_{ex} \in A. This is because the trace shows the attacker’s pc as ⊤\top and, by upward closure of AA, an attacker pc that flows to pexp_{ex} places pexp_{ex} in AA.

Theorem 6.2 (CDA Security). If ⊢W2P\vdash_{W_2} P, then PP is free of confused-deputy attacks in W0W_0 to W3W_3.

Proof. We prove the theorem for W2W_2, and the result for the other worlds follows from theorem 5.2. In W2W_2, TI-App types every call into honest code, including the calls of the boundary-typed attacker. The premise pc⊔ℓ⊑pexpc \sqcup\ell\sqsubseteq p_{ex} of TI-App gives pc⊑pexpc \sqsubseteq p_{ex}. If pc∉Apc \notin A, the second case holds. If pc∈Apc \in A, then pex∈Ap_{ex} \in A by upward closure of AA, which proves the first case. □\square

Reentrancy Attacks

A reentrancy attack, as in Figure 2, calls back into trusted code while a trusted function waits on an untrusted call. We write ∣η⃗∣call\lvert\vec{\eta}\rvert_{\mathrm{call}} and ∣η⃗∣ret\lvert\vec{\eta}\rvert_{\mathrm{ret}} for the numbers of call and return events in a trace η⃗\vec{\eta}, and η⃗′⪯η⃗\vec{\eta}' \preceq\vec{\eta} when η⃗′\vec{\eta}' is a prefix of η⃗\vec{\eta}.

Definition 6.3 (Reentrancy Security). We say that PP is free from reentrancy attacks in WW if, for all attackers AWA_W and stores Σ\Sigma such that ⊢WAW\vdash_W A_W and ⊢Σ\vdash\Sigma, and η⃗=⟦P⋈AW⟧W(Σ)\vec{\eta} = \llbracket P \bowtie A_W \rrbracket_W(\Sigma), and for all traces η⃗1\vec{\eta}_1 and η⃗2\vec{\eta}_2, functions p.fp.f and q.gq.g, and labels pcpc and pc′pc', the following holds.

η⃗1::call⁡pc′(p.f)::η⃗2::call⁡pc(q.g)⪯η⃗∧(∀η⃗′⪯η⃗2. ∣η⃗′∣ret≤∣η⃗′∣call)⟹pc⊑q⊔p.\vec{\eta}_1 :: \operatorname{call}_{pc'}(p.f) :: \vec{\eta}_2 :: \operatorname{call}_{pc}(q.g) \preceq\vec{\eta} \land\left(\forall\vec{\eta}' \preceq\vec{\eta}_2.\ \lvert\vec{\eta}'\rvert_{\mathrm{ret}} \le\lvert\vec{\eta}'\rvert_{\mathrm{call}}\right) \Longrightarrow pc \sqsubseteq q \sqcup p.

The second premise states that p.fp.f has not returned when q.gq.g is called. Note that the attacker calls no honest code while an honest function waits, since the trace shows the attacker’s pc as ⊤\top, which by primality never flows to q⊔pq \sqcup p.

Theorem 6.4 (Reentrancy Security). If ⊢W2P\vdash_{W_2} P, then PP is free of reentrancy attacks in W0W_0 to W3W_3.

Proof. We prove the theorem for W1W_1, and the result for the other worlds follows from theorem 5.2. In W1W_1, when pp is a lock on the call stack when q.gq.g is called, the dynamic check dynCheck⁡W1\operatorname{dynCheck}_{W_1} ensures that the calling pc flows to q⊔pq \sqcup p. An honest calling pc appears unchanged in the trace, and an attacker pc fails the check by primality. □\square

Related Work

At a high level, our proof follows the standard context-based backtranslation strategy [18, 30, 30], where the attackers are contexts. Instead of defining a translation of calculus terms, we use a technique standard in the tradition of state-machine refinement [26] to separate the argument about boundary typing from the language implementing the attacker.

Hennessy et al. [22], Riely and Hennessy [36] aim to provide secure execution in a decentralized system in which not all code is well-typed. They have a different system setting: instead of RPC calls, principals send code blocks to each other. Besides, their major result is subject reduction, while we define and prove a novel security objective.

Rajani et al. [34] formally characterize CDA vulnerabilities and show that capabilities cannot prevent all CDAs. Compared to their setting, our system supports first-class function pointers, and we assume a weaker runtime. They showed that CDAs are only prevented when Full Provenance is enforced. This is the same insight as using information flow control for both control flow and data flow in our work. Our major theoretical result is a simulation theorem that generalizes to other kinds of attacks, and CDA security is just an instance of our results.

Our approach to reentrancy is inspired by SeRIF [12], a core calculus that enforces secure reentrancy using a combination of both static and dynamic IFC. World 1’s dynamic check is similar to that of SeRIF, but SeRIF does not handle type confusion.

The topic of our work resembles that of gradual typing [39, 42], but we have different settings and goals. At a high level, gradual typing studies how static type checking and dynamic type checking can be combined in a complementary way; type confusion is interested in providing assurance when code is linked to untrusted code that is neither statically nor dynamically typed. As a result, the two approaches yield different theorems [40, 42]. Gradual IFC languages [8, 9, 13, 41] are not fully decentralized; they rely on a system-wide runtime that enforces IFC on both the attacker and the honest parties.

Our enforcement against ordinary-type confusion and reentrancy mirrors the idea of Control Flow Integrity (CFI) [1, 31], a security policy that requires that all executions follow paths in a predetermined control-flow graph. This current work is more general: the above attacks are only a subset of attacks that our framework handles.

Conclusion

Although IFC type systems provide a well-studied approach to end-to-end security, their adoption remains challenging. This paper develops type-confusion security for IFC type systems, supporting modular enforcement of both data-flow and control-flow security. A promising future direction is to use type confusion as the security objective to guide the development of systems that modularly adopt new type systems.

AI Use

Codex and Claude Code assisted with Lean [28] development under human guidance, including assisting in the translation of pen-and-paper definitions and proofs, auditing proofs, and mechanizing the motivating examples. We designed the structure of the mechanization, including the language design, state-machine formulation, and the right abstractions, and we audited the result.

Data-Availability Statement

The supplementary material for this paper includes two artifacts: an appendix in PDF format and a Lean 4 [28] mechanization of the paper’s results. We will submit the Lean artifact for evaluation.

The Lean 4 mechanization includes all of the results, including the examples, from the paper as well as a file called README.md, which maps each result of the paper to its definition in the Lean artifact. The Lean artifact also contains some results that were not extensively discussed in the paper, such as type safety of both the honest programs and the system. The artifact contains no sorry and every result depends only on the standard classical axioms of Lean, namely propositional extensionality (propext), quotient soundness (Quot.sound), and choice (Classical.choice), which can be checked by running make axiom (AxiomsAudit.lean). The artifact uses Lean 4 and Mathlib [27].

The appendix includes more examples on CDA attacks, and missing definitions referred to by the main text.

Additional Examples: Model Context Protocol and Webhost

As we suggested in the introduction, the threat model is not exclusive to smart contracts. Figure 14 shows two additional applications that are subject to the same attacks.

MCP tool host and webhost code

Figure 14. The MCP host (left) executes the action associated with an unused user approval and delivers the result to the conversation through a custom callback sendToChat. The website host (right) calls the client’s archiveBuild callback to save a copy of the built artifact before verification and publication; substituting publish for that callback publishes before verification.

The code on the left implements an MCP (Model Context Protocol) host. The Model Context Protocol (MCP) connects AI applications to external tools, such as file editors and deployment services. The threat model of this MCP host is very similar to that of a smart contract: the actions and callbacks are often provided by third-party libraries with no standard way for specifying permission policies, and callbacks and callers are built using heterogeneous toolchains. A CDA substitutes the privileged tool executor for sendToChat, violating the executor’s external-pc restriction and executing a tool-generated proposal without separate approval. A reentrant callback violates its bounding pc by invoking the host again before the approval is marked as used, allowing one authorization to execute the action multiple times. A CFI attack supplies data in place of sendToChat, causing that data to be interpreted as a function pointer and redirecting execution to an unintended function. These attacks follow the same patterns as the exchange-service attacks explained above.

A cloud website service builds source code into deployable sites. As the service evolves, it may adopt IFC typing incrementally while retaining callbacks from older components. The host cannot assume that these callbacks obey its new security discipline, even when they are maintained by the same organization. The host in Figure 14 calls the client’s archiveBuild callback to upload the artifact to the client’s repository before verifying and publishing the site. Archiving also retains rejected builds for diagnosis. A CDA substitutes the privileged publisher for archiveBuild, violating the publisher’s external-pc restriction and publishing a site before verification. If builds share a mutable staging slot, a reentrant callback can violate its bounding pc by starting a nested trusted build that overwrites the pending release’s artifact. A CFI attack supplies data in place of archiveBuild, causing that data to be interpreted as a function pointer and redirecting execution to an unintended function. These attacks likewise follow the patterns of the exchange-service attacks.

Complete Definitions

Helper notations

We overload ⊔\sqcup and write τ⊔ℓ\tau\sqcup\ell to join ℓ\ell with the label of τ\tau, and ↓\downarrow to set the label of τ\tau to ℓ\ell.

(τi→pcex▹pcmaxτo)ℓ⊔ℓ′=(τi→pcex▹pcmaxτo)ℓ⊔ℓ′boolℓ⊔ℓ′=boolℓ⊔ℓ′natℓ⊔ℓ′=natℓ⊔ℓ′\begin{aligned} (\tau_i \xrightarrow{pc_{\mathrm{ex}}\triangleright pc_{\mathrm{max}}} \tau_o)_\ell\sqcup\ell' &= (\tau_i \xrightarrow{pc_{\mathrm{ex}}\triangleright pc_{\mathrm{max}}} \tau_o)_{\ell\sqcup\ell'} & \mathrm{bool}_\ell\sqcup\ell' &= \mathrm{bool}_{\ell\sqcup\ell'} & \mathrm{nat}_\ell\sqcup\ell' &= \mathrm{nat}_{\ell\sqcup\ell'} \end{aligned}
boolℓ′↓ℓ=boolℓnatℓ′↓ℓ=natℓ1↓ℓ=10↓ℓ=0.\mathrm{bool}_{\ell'} \downarrow\ell= \mathrm{bool}_\ell \qquad \mathrm{nat}_{\ell'} \downarrow\ell= \mathrm{nat}_\ell \qquad 1 \downarrow\ell= 1 \qquad 0 \downarrow\ell= 0.

We also define I≃I′\mathcal{I} \simeq\mathcal{I}', where I=(sig,cell)\mathcal{I} = (\mathrm{sig},\mathrm{cell}) and I′=(sig′,cell′)\mathcal{I}' = (\mathrm{sig}',\mathrm{cell}'), to mean the two interfaces agree on every function and cell they both declare. That is,

∀p.f,s,s′. sig(p.f)=s∧sig′(p.f)=s′⟹s=s′(functions agree)\forall p.f,s,s'.\ \mathrm{sig}(p.f)=s \land\mathrm{sig}'(p.f)=s' \Longrightarrow s=s' \qquad\text{(functions agree)}
∧ ∀p,h,τ,τ′. cell(p,h)=τ∧cell′(p,h)=τ′⟹τ=τ′(cells agree)\land\ \forall p,h,\tau,\tau'.\ \mathrm{cell}(p,h)=\tau\land\mathrm{cell}'(p,h)=\tau' \Longrightarrow\tau=\tau' \qquad\text{(cells agree)}

We also define linking the signature sig⋈sigA\mathrm{sig} \bowtie\mathrm{sig}_{\mathcal{A}} and cell table cell⋈cellA\mathrm{cell} \bowtie\mathrm{cell}_{\mathcal{A}} as follows:

(sig⋈sigA)(p.f)={sig(p.f)if p.f∈dom⁡(sig)sigA(p.f)otherwise(\mathrm{sig} \bowtie\mathrm{sig}_{\mathcal{A}})(p.f)= \begin{cases} \mathrm{sig}(p.f) & \text{if } p.f \in\operatorname{dom}(\mathrm{sig})\\ \mathrm{sig}_{\mathcal{A}}(p.f) & \text{otherwise} \end{cases}
(cell⋈cellA)(p,h)={cell(p,h)if (p,h)∈dom⁡(sig)cellA(p,h)otherwise(\mathrm{cell} \bowtie\mathrm{cell}_{\mathcal{A}})(p,h)= \begin{cases} \mathrm{cell}(p,h) & \text{if } (p,h) \in\operatorname{dom}(\mathrm{sig})\\ \mathrm{cell}_{\mathcal{A}}(p,h) & \text{otherwise} \end{cases}

IFC typing

Figure 15 gives the full IFC expression typing, which, as stated in the main text, is mostly standard [45, 46]. Besides the rules of Figure 7, the figure contains the standard rules for values, variables, operators, let bindings, conditionals and subsumption. TI-Abort gives abort every well-formed type. TI-If checks each branch at pc⊔ℓpc \sqcup\ell, where ℓ\ell is the label of the guard, and joins ℓ\ell into the result type, since the result reveals which branch ran.

Figure 15. Full IFC expression typing.

An ordinary type σ=⌊τ⌋\sigma= \lfloor\tau\rfloor drops every label and both pc annotations of τ\tau,

⌊boolℓ⌋=bool⌊natℓ⌋=nat⌊1⌋=1⌊0⌋=0⌊(τi→pcex▹pcmaxτo)ℓ⌋=⌊τi⌋→⌊τo⌋,\lfloor\mathrm{bool}_\ell\rfloor=\mathrm{bool} \qquad \lfloor\mathrm{nat}_\ell\rfloor=\mathrm{nat} \qquad \lfloor1\rfloor=1 \qquad \lfloor0\rfloor=0 \qquad \left\lfloor\left(\tau_i \xrightarrow{pc_{\mathrm{ex}}\triangleright pc_{\mathrm{max}}} \tau_o\right)_\ell\right\rfloor = \lfloor\tau_i\rfloor\to\lfloor\tau_o\rfloor,

and ⌊Γ⌋\lfloor\Gamma\rfloor replaces each τ\tau in Γ\Gamma by ⌊τ⌋\lfloor\tau\rfloor. Figure 16 gives the full ordinary expression typing. This typing is isomorphic to IFC typing over the one-point label model, so each rule TR-X is TI-X of Figure 15 with every label premise removed and every type replaced by its erasure. The mechanization defines ordinary typing as this instance of IFC typing, which highlights the correspondence between the two typings.

World 3 semantics

Besides F-Code and F-Code-Act, World W3_3 replaces the attacker cases of callW\mathrm{call}_{W} and retW\mathrm{ret}_{W} in Figure 11 with the following, and keeps all other rules of World W2_2.

callW3(ΣA,S,pc,vf,v)={⟨ΣA,toA(q.g,e{v/x})::S,ϵ⟩if q∈A and bodyA(q.g)=λx.e⟨ΣA,toA(q.g,XA(q.g)(v))::S,ϵ⟩if q∈A and XA(q.g) is definedcallW(ΣA,S,pc,vf,v)if q∉A⟨ΣA,∅,ζ⟩otherwise\mathrm{call}_{W_3}(\Sigma_{\mathcal{A}},S,pc,v_f,v)= \begin{cases} \langle\Sigma_{\mathcal{A}},\mathrm{to}_{\mathcal{A}}(q.g,e\{v/x\})::S,\epsilon\rangle & \text{if }q\in A\text{ and }\mathrm{body}_{\mathcal{A}}(q.g)=\lambda x.e\\ \langle\Sigma_{\mathcal{A}},\mathrm{to}_{\mathcal{A}}(q.g,X_{\mathcal{A}}(q.g)(v))::S,\epsilon\rangle & \text{if }q\in A\text{ and }X_{\mathcal{A}}(q.g)\text{ is defined}\\ \mathrm{call}_{W}(\Sigma_{\mathcal{A}},S,pc,v_f,v) & \text{if }q\notin A\\ \langle\Sigma_{\mathcal{A}},\varnothing,\zeta\rangle & \text{otherwise} \end{cases}
retW3(ΣA,ϕ,S,p.f,v)={⟨ΣA,toA(q.g,E[v])::S,ηp⟩if ϕ=toA(q.g,E[vf[ℓ]u])retW(ΣA,ϕ,S,p.f,v)otherwise\mathrm{ret}_{W_3}(\Sigma_{\mathcal{A}},\phi,S,p.f,v)= \begin{cases} \langle\Sigma_{\mathcal{A}},\mathrm{to}_{\mathcal{A}}(q.g,E[v])::S,\eta_p\rangle & \text{if }\phi=\mathrm{to}_{\mathcal{A}}(q.g,E[v_f[\ell]u])\\ \mathrm{ret}_{W}(\Sigma_{\mathcal{A}},\phi,S,p.f,v) & \text{otherwise} \end{cases}

Complete Definitions

where vf=q.gv_f = q.g and η⃗p\vec{\eta}_p is as in Figure 11. To emphasize the correspondence among the worlds, the mechanization adds an abstraction layer that generalizes the attacker’s behavior. This layer runs the heterogeneous system of the honest party and the attacker on one unified semantics. F-Code

Γ;p⊢W1e:σTR-UnitΓ;p⊢W1():1TR-BoolΓ;p⊢W1b:boolTR-NatΓ;p⊢W1n:natTR-VarΓ(x)=σ,Γ;p⊢W1x:σTR-Funsig⁡(q.f)=τi→pcmax⁡pcexτo,Γ;p⊢W1q.f:[τi]→[τo]TR-AbortΓ;p⊢W1abort⁡:σTR-Op⊢⊗:σ1×σ2→σ,Γ;p⊢W1vi:σi (i∈{1,2}),Γ;p⊢W1v1⊗v2:σTR-DownΓ;p⊢W1v:σ,σ∈{bool,nat,0},Γ;p⊢W1v↓ℓ:σTR-LetΓ;p⊢W1e1:σ1,σ1::Γ;p⊢W1e2:σ2,Γ;p⊢W1let⁡x=e1in⁡e2:σ2TR-SubΓ;p⊢W1e:σ′,σ′⪯σ,Γ;p⊢W1e:σTR-IfΓ;p⊢W1v:bool,Γ;p⊢W1ei:σi,σi⪯σ (i∈{1,2}),Γ;p⊢W1if⁡vthen⁡e1else⁡e2:σTR-Readcell⁡(p,h)=τ,Γ;p⊢W1read⁡h:[τ]TR-Writecell⁡(p,h)=τ,Γ;p⊢W1v:σ′,σ′⪯[τ],Γ;p⊢W1write⁡h(v):1TR-AppΓ;p⊢W1v1:σi→σo,Γ;p⊢W1v2:σ,σ⪯σi,Γ;p⊢W1v1[pcex]v2:σo\begin{aligned} &\Gamma; p \vdash_{\mathrm{W}_1} e : \sigma\\ &\text{TR-Unit}\qquad\Gamma; p \vdash_{\mathrm{W}_1} () : 1\\ &\text{TR-Bool}\qquad\Gamma; p \vdash_{\mathrm{W}_1} b : \mathrm{bool}\\ &\text{TR-Nat}\qquad\Gamma; p \vdash_{\mathrm{W}_1} n : \mathrm{nat}\\ &\text{TR-Var}\qquad\Gamma(x)=\sigma,\quad\Gamma; p \vdash_{\mathrm{W}_1} x : \sigma\\ &\text{TR-Fun}\qquad\operatorname{sig}(q.f)=\tau_i \xrightarrow[p c_{\max}]{p c_{\mathrm{ex}}} \tau_o,\quad\Gamma; p \vdash_{\mathrm{W}_1} q.f : [\tau_i]\to[\tau_o]\\ &\text{TR-Abort}\qquad\Gamma; p \vdash_{\mathrm{W}_1} \operatorname{abort} : \sigma\\ &\text{TR-Op}\qquad\vdash\otimes: \sigma_1\times\sigma_2\to\sigma,\quad\Gamma; p \vdash_{\mathrm{W}_1} v_i : \sigma_i\ (i\in\{1,2\}),\quad\Gamma; p \vdash_{\mathrm{W}_1} v_1\otimes v_2 : \sigma\\ &\text{TR-Down}\qquad\Gamma; p \vdash_{\mathrm{W}_1} v:\sigma,\quad\sigma\in\{\mathrm{bool},\mathrm{nat},0\},\quad\Gamma; p \vdash_{\mathrm{W}_1} v\mathbin{\downarrow}\ell:\sigma\\ &\text{TR-Let}\qquad\Gamma; p \vdash_{\mathrm{W}_1} e_1:\sigma_1,\quad\sigma_1::\Gamma; p\vdash_{\mathrm{W}_1}e_2:\sigma_2,\quad\Gamma;p\vdash_{\mathrm{W}_1}\operatorname{let}x=e_1\operatorname{in}e_2:\sigma_2\\ &\text{TR-Sub}\qquad\Gamma;p\vdash_{\mathrm{W}_1}e:\sigma',\quad\sigma'\preceq\sigma,\quad\Gamma;p\vdash_{\mathrm{W}_1}e:\sigma\\ &\text{TR-If}\qquad\Gamma;p\vdash_{\mathrm{W}_1}v:\mathrm{bool},\quad\Gamma;p\vdash_{\mathrm{W}_1}e_i:\sigma_i,\quad\sigma_i\preceq\sigma\ (i\in\{1,2\}),\\ &\hspace{5em}\Gamma;p\vdash_{\mathrm{W}_1}\operatorname{if}v\operatorname{then}e_1\operatorname{else}e_2:\sigma\\ &\text{TR-Read}\qquad\operatorname{cell}(p,h)=\tau,\quad\Gamma;p\vdash_{\mathrm{W}_1}\operatorname{read}_h:[\tau]\\ &\text{TR-Write}\qquad\operatorname{cell}(p,h)=\tau,\quad\Gamma;p\vdash_{\mathrm{W}_1}v:\sigma',\quad\sigma'\preceq[\tau],\quad\Gamma;p\vdash_{\mathrm{W}_1}\operatorname{write}_h(v):1\\ &\text{TR-App}\qquad\Gamma;p\vdash_{\mathrm{W}_1}v_1:\sigma_i\to\sigma_o,\quad\Gamma;p\vdash_{\mathrm{W}_1}v_2:\sigma,\quad\sigma\preceq\sigma_i,\\ &\hspace{5em}\Gamma;p\vdash_{\mathrm{W}_1}v_1[p c_{\mathrm{ex}}]v_2:\sigma_o \end{aligned}

and F-Code-Act instantiate the attacker abstraction with attacker code, while F-Attacker and F-Attacker-Act instantiate it with interactive state machines.

Type Safety

As a sanity check, we show that a well-typed program linked with a well-typed (either IFC-typed or ordinarily typed) attacker never gets stuck. The proof lifts the standard progress and preservation lemmas for expressions to linked configurations. Both lemmas hold for IFC typing over any label lattice, so they also hold for ordinary typing, which is IFC typing over the one-point label model.

World 2

Progress states that a closed, IFC-typed expression never gets stuck. A value steps to a return action by S-Ret, and an expression that reaches abort steps to an abort action by S-Abort.

Lemma C.1 (IFC Progress). Consider a principal pp, labels pcpc and pcmax⁡pc_{\max}, an expression ee and a type τ\tau such that ∅;pc;p;pcmax⁡⊢W2e:τ\emptyset; pc; p; pc_{\max}\vdash_{\mathrm{W}_2}e:\tau. Then for every store Σ\Sigma,

∃N,Σ′,η⃗. ⟨e,Σ⟩→p⟨N,Σ′,η⃗⟩\exists N,\Sigma',\vec{\eta}.\ \langle e,\Sigma\rangle\xrightarrow{p} \langle N,\Sigma',\vec{\eta}\rangle

Preservation states that an internal step keeps the expression that p.fp.f runs at the result type of p.fp.f and keeps the cells of every principal well typed. We write cell⁡∣q\operatorname{cell}|_q for the restriction of cell to the cells of principal qq.

Lemma C.2 (IFC Preservation). Consider an interface I=(sig,cell)I = (\mathrm{sig}, \mathrm{cell}), a function p.fp.f, an expression ee and a store Σ\Sigma such that ⊢W2I\vdash_{W_2} I, cell∣p⊢Σ\mathrm{cell}|_p \vdash\Sigma and ∅;p;p;pcmax⁡⊢W2e:τo⊔p\emptyset; p; p; pc_{\max} \vdash_{W_2} e : \tau_o \sqcup p. Then for every expression e′e', store Σ′\Sigma' and trace η⃗\vec{\eta},

⟨e,Σ⟩→p⟨e′,Σ′,η⃗⟩⟹(∅;p;p;pcmax⁡⊢W2e′:τo⊔p)∧(∀q. cell∣q⊢Σ⟹cell∣q⊢Σ′)\langle e, \Sigma\rangle\xrightarrow{p} \langle e', \Sigma', \vec{\eta} \rangle\quad\Longrightarrow\quad(\emptyset; p; p; pc_{\max} \vdash_{W_2} e' : \tau_o \sqcup p) \land(\forall q.\ \mathrm{cell}|_q \vdash\Sigma\Longrightarrow\mathrm{cell}|_q \vdash\Sigma')

where sig(p.f)=τi→pcex◃pcmax⁡τo\mathrm{sig}(p.f) = \tau_i \xrightarrow{pc_{\mathrm{ex}} \triangleleft pc_{\max}} \tau_o.

Type safety lifts both lemmas to linked runs. Every configuration that a run reaches has well-typed honest cells and a well-typed running honest frame, and it either has halted or takes another step.

Theorem C.3 (Type Safety in World 2). Consider a program P\mathcal{P}, an attacker A\mathcal{A} and a store Σinit\Sigma_{\mathrm{init}} such that ⊢W2P\vdash_{W_2} \mathcal{P}, ⊢W2A\vdash_{W_2} \mathcal{A} and ⊢Σinit\vdash\Sigma_{\mathrm{init}}. Then for every configuration C=⟨sA,Σ,S⟩C = \langle s_{\mathcal{A}}, \Sigma, S \rangle and trace η⃗\vec{\eta},

Cinit→∗W2⟨C,η⃗⟩⟹⊢ΣC_{\mathrm{init}} \xrightarrow{*}_{W_2} \langle C, \vec{\eta} \rangle\quad\Longrightarrow\quad\vdash\Sigma
∧ ∀p.f,e,S′. S=toH⁡(p.f,e)::S′⟹∅;p;p;pcmax⁡⊢W2e:τo⊔p\land\ \forall p.f,e,S'.\ S = \operatorname{toH}(p.f,e) :: S' \Longrightarrow\emptyset; p; p; pc_{\max} \vdash_{W_2} e : \tau_o \sqcup p
∧ (S=∅∨∃C′,η⃗′. C→W2⟨C′,η⃗′⟩)\land\ (S = \emptyset\lor\exists C', \vec{\eta}'.\ C \xrightarrow{}_{W_2} \langle C', \vec{\eta}' \rangle)

where (sig⋈sigA)(p.f)=τi→pcex◃pcmax⁡τo(\mathrm{sig} \bowtie\mathrm{sig}_{\mathcal{A}})(p.f) = \tau_i \xrightarrow{pc_{\mathrm{ex}} \triangleleft pc_{\max}} \tau_o.

World 1

World 1 satisfies the same three results with ordinary typing in place of IFC typing. In this subsection, the store typing ⊢\vdash checks each cell against its ordinary type with ordinary typing. Ordinary preservation needs no well-formed interface, since every erased interface is well formed.

Lemma C.4 (Ordinary Progress). Consider a principal pp, an expression ee and an ordinary type σ\sigma such that ∅;p⊢W1e:σ\emptyset; p \vdash_{W_1} e : \sigma. Then for every store Σ\Sigma,

∃N,Σ′,η⃗. ⟨e,Σ⟩→p⟨N,Σ′,η⃗⟩\exists N, \Sigma', \vec{\eta}.\ \langle e, \Sigma\rangle\xrightarrow{p} \langle N, \Sigma', \vec{\eta} \rangle

Lemma C.5 (Ordinary Preservation). Consider an interface I=(sig,cell)I = (\mathrm{sig}, \mathrm{cell}), a function p.fp.f, an expression ee and a store Σ\Sigma such that cell∣p⊢Σ\mathrm{cell}|_p \vdash\Sigma and ∅;p⊢W1e:⌊τo⌋\emptyset; p \vdash_{W_1} e : \lfloor\tau_o \rfloor. Then for every expression e′e', store Σ′\Sigma' and trace η⃗\vec{\eta},

⟨e,Σ⟩⟶⟨e′,Σ′,η⃗⟩⟹(∅;p⊢W1e′:⌊τo⌋)∧(∀q. cell∣q⊢Σ⟹cell∣q⊢Σ′)\langle e, \Sigma\rangle\longrightarrow\langle e', \Sigma', \vec{\eta} \rangle\quad\Longrightarrow\quad(\emptyset; p \vdash_{W_1} e' : \lfloor\tau_o \rfloor) \land(\forall q.\ \mathrm{cell}|_q \vdash\Sigma\Longrightarrow\mathrm{cell}|_q \vdash\Sigma')

where sig(p.f)=τi→pcex◃pcmax⁡τo\mathrm{sig}(p.f) = \tau_i \xrightarrow{pc_{\mathrm{ex}} \triangleleft pc_{\max}} \tau_o.

Theorem C.6 (Type Safety in World 1). Consider a program P\mathcal{P}, an attacker A\mathcal{A} and a store Σinit\Sigma_{\mathrm{init}} such that ⊢W1P\vdash_{W_1} \mathcal{P}, ⊢W1A\vdash_{W_1} \mathcal{A} and ⊢Σinit\vdash\Sigma_{\mathrm{init}}. Then for every configuration C=⟨sA,Σ,S⟩C = \langle s_{\mathcal{A}}, \Sigma, S \rangle and trace η⃗\vec{\eta},

Cinit→∗W1⟨C,η⃗⟩⟹⊢ΣC_{\mathrm{init}} \xrightarrow{*}_{W_1} \langle C, \vec{\eta} \rangle\quad\Longrightarrow\quad\vdash\Sigma
∧ ∀p.f,e,S′. S=toH⁡(p.f,e)::S′⟹∅;p⊢W1e:⌊τo⌋\land\ \forall p.f,e,S'.\ S = \operatorname{toH}(p.f,e) :: S' \Longrightarrow\emptyset; p \vdash_{W_1} e : \lfloor\tau_o \rfloor
∧ (S=∅∨∃C′,η⃗′. C→W1⟨C′,η⃗′⟩)\land\ (S = \emptyset\lor\exists C', \vec{\eta}'.\ C \xrightarrow{}_{W_1} \langle C', \vec{\eta}' \rangle)

where (sig⋈sigA)(p.f)=τi→pcex◃pcmax⁡τo(\mathrm{sig} \bowtie\mathrm{sig}_{\mathcal{A}})(p.f) = \tau_i \xrightarrow{pc_{\mathrm{ex}} \triangleleft pc_{\max}} \tau_o.

World 3

Type safety in world W3W_3 is syntactic. The judgment ⊢W3A\vdash_{W_3} \mathcal{A} types the attacker code itself rather than the actions that the attacker emits, so the invariant also types the running attacker frame and the attacker store. The attacker code is typed in world W2W_2, so the invariant uses IFC typing.

Theorem C.7 (Type Safety in World 3). Consider a program P\mathcal{P}, attacker code A\mathcal{A} and a store Σinit\Sigma_{\mathrm{init}} such that ⊢W2P\vdash_{W_2}\mathcal{P}, ⊢W3A\vdash_{W_3}\mathcal{A} and ⊢Σinit\vdash\Sigma_{\mathrm{init}}. Then for every configuration C=⟨ΣA,Σ,S⟩C = \langle\Sigma_{\mathcal{A}},\Sigma,S\rangle and trace η⃗\vec{\eta},

Cinit⟶W3∗⟨C,η⃗⟩⟹⊢Σ∧cellA⊢ΣAC_{\mathrm{init}} \longrightarrow_{W_3}^{*} \langle C,\vec{\eta}\rangle\Longrightarrow\vdash\Sigma\land\mathrm{cell}_{\mathcal{A}}\vdash\Sigma_{\mathcal{A}}
∧ ∀p.f,e,S′. (S=toH⁡(p.f,e)::S′∨S=toA⁡(p.f,e)::S′)\land\ \forall p.f,e,S'.\ \left(S=\operatorname{toH}(p.f,e)::S' \lor S=\operatorname{toA}(p.f,e)::S'\right)
⟹∅;p;p;pcmax⁡⊢W2e:τo⊔p\Longrightarrow\varnothing;p;p;pc_{\max}\vdash_{W_2}e:\tau_o\sqcup p
∧ (S=∅∨∃C′,η⃗′. C⟶W3⟨C′,η⃗′⟩)\land\ \left(S=\varnothing\lor\exists C',\vec{\eta}'.\ C\longrightarrow_{W_3}\langle C',\vec{\eta}'\rangle\right)

where (sig⁡⋈sig⁡A)(p.f)=τi→pcex▹pcmax⁡τo(\operatorname{sig}\mathbin{\bowtie}\operatorname{sig}_{\mathcal{A}})(p.f)=\tau_i\xrightarrow{pc_{\mathrm{ex}}\mathrel{\triangleright}pc_{\max}}\tau_o.

Type safety in world W3W_3 also holds in the traditional form of initialization, preservation and progress. This form uses a typing judgment on configurations that also types the suspended frames.

Definition C.8 (Configuration Typing). Consider a program P\mathcal{P} and attacker code A\mathcal{A}. A configuration C=⟨ΣA,Σ,S⟩C=\langle\Sigma_{\mathcal{A}},\Sigma,S\rangle is well typed, written ⊢W3C\vdash_{W_3}C, if ⊢Σ\vdash\Sigma, cellA⊢ΣA\mathrm{cell}_{\mathcal{A}}\vdash\Sigma_{\mathcal{A}} and either S=∅S=\varnothing or S=ϕ::S′S=\phi::S' with

(ϕ=toH⁡(p.f,e)∧p∉A∨ϕ=toA⁡(p.f,e)∧p∈A)(where p belongs)\left(\phi=\operatorname{toH}(p.f,e)\land p\notin A\lor\phi=\operatorname{toA}(p.f,e)\land p\in A\right)\qquad\text{(where }p\text{ belongs)}
∧ ∅;p;p;pcmax⁡⊢W2e:τo⊔p(running frame is well-typed)\land\ \varnothing;p;p;pc_{\max}\vdash_{W_2}e:\tau_o\sqcup p\qquad\text{(running frame is well-typed)}
∧ p.f⊢S′(suspended frames are well-typed)\land\ p.f\vdash S'\qquad\text{(suspended frames are well-typed)}

The judgment q.g⊢Sq.g\vdash S states that each frame of SS resumes well typed on a well-typed result of the frame above it. It holds for S=∅S=\varnothing and for S=ϕ::S′S=\phi::S' with

(ϕ=toH⁡(p.f,E[vf[ℓ]u])∧p∉A∨ϕ=toA⁡(p.f,E[vf[ℓ]u])∧p∈A)(where p belongs)\left(\phi=\operatorname{toH}(p.f,E[v_f[\ell]u])\land p\notin A\lor\phi=\operatorname{toA}(p.f,E[v_f[\ell]u])\land p\in A\right)\qquad\text{(where }p\text{ belongs)}
∧ ∀v. ∅;q;q;pcmax⁡′⊢W2v:τo′⊔q⟹∅;p;p;pcmax⁡⊢W2E[v]:τo⊔p(resumption is well-typed)\land\ \forall v.\ \varnothing;q;q;pc'_{\max}\vdash_{W_2}v:\tau'_o\sqcup q\Longrightarrow\varnothing;p;p;pc_{\max}\vdash_{W_2}E[v]:\tau_o\sqcup p \qquad\text{(resumption is well-typed)}
∧ p.f⊢S′(suspended frames are well-typed)\land\ p.f\vdash S'\qquad\text{(suspended frames are well-typed)}

where (sig⁡⋈sig⁡A)(p.f)=τi→pcex▹pcmax⁡τo(\operatorname{sig}\mathbin{\bowtie}\operatorname{sig}_{\mathcal{A}})(p.f)=\tau_i\xrightarrow{pc_{\mathrm{ex}}\mathrel{\triangleright}pc_{\max}}\tau_o and (sig⁡⋈sig⁡A)(q.g)=τi′→pcex′▹pcmax⁡′τo′(\operatorname{sig}\mathbin{\bowtie}\operatorname{sig}_{\mathcal{A}})(q.g)=\tau'_i\xrightarrow{pc'_{\mathrm{ex}}\mathrel{\triangleright}pc'_{\max}}\tau'_o.

Theorem C.9 (Configuration Safety in World 3). Consider a program P\mathcal{P}, attacker code A\mathcal{A} and a store Σinit\Sigma_{\mathrm{init}} such that ⊢W2P\vdash_{W_2}\mathcal{P}, ⊢W3A\vdash_{W_3}\mathcal{A} and ⊢Σinit\vdash\Sigma_{\mathrm{init}}. Then ⊢W3Cinit\vdash_{W_3}C_{\mathrm{init}}, and for all configurations CC and C′C' and traces η⃗\vec{\eta},

⊢W3C∧C⟶W3⟨C′,η⃗⟩⟹⊢W3C′(preservation)\vdash_{W_3}C\land C\longrightarrow_{W_3}\langle C',\vec{\eta}\rangle\Longrightarrow\vdash_{W_3}C' \qquad\text{(preservation)}
Cinit⟶W3∗⟨C,η⃗⟩⟹S=∅∨∃C′′,η⃗′. C⟶W3⟨C′′,η⃗′⟩(progress)C_{\mathrm{init}}\longrightarrow_{W_3}^{*}\langle C,\vec{\eta}\rangle\Longrightarrow S=\varnothing\lor\exists C'',\vec{\eta}'.\ C\longrightarrow_{W_3}\langle C'',\vec{\eta}'\rangle \qquad\text{(progress)}

where C=⟨ΣA,Σ,S⟩C=\langle\Sigma_{\mathcal{A}},\Sigma,S\rangle.

Theorem C.9 implies Theorem C.7. Initialization and preservation give ⊢W3C\vdash_{W_3}C for every reachable configuration CC, and ⊢W3C\vdash_{W_3}C contains the store and running-frame conditions of Theorem C.7.

References

  1. [1]Martín Abadi, Mihai Budiu, Úlfar Erlingsson, and Jay Ligatti. 2005. Control-flow integrity. In Proceedings of the 12th ACM Conference on Computer and Communications Security (Alexandria, VA, USA), (CCS ’05). Association for Computing Machinery, New York, NY, USA, 340–353. doi:10.1145/1102120.1102165DOI
  2. [2]Martín Abadi and Leslie Lamport. 1995. Conjoining specifications. ACM Trans. Program. Lang. Syst. 17, 3 (May 1995), 507–535. doi:10.1145/203095.201069DOI
  3. [3]Carmine Abate, Roberto Blanco, Deepak Garg, Catalin Hritcu, Marco Patrignani, and Jérémy Thibault. 2019. Journey Beyond Full Abstraction: Exploring Robust Property Preservation for Secure Compilation. In 32nd IEEE Computer Security Foundations Symp. (CSF). IEEE Computer Society, 256–271. doi:10.1109/CSF.2019.00025DOI
  4. [4]Samson Abramsky and Guy McCusker. 1999. Game Semantics. In Computational Logic, Ulrich Berger and Helmut Schwichtenberg (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 1–55.
  5. [5]Coşku Acay, Rolph Recto, Joshua Gancher, Andrew Myers, and Elaine Shi. 2021. Viaduct: An Extensible, Optimizing Compiler for Secure Distributed Programs. In 42nd ACM SIGPLAN Conf. on Programming Language Design and Implementation (PLDI). ACM, 740–755. doi:10.1145/3453483.3454074DOI
  6. [6]Owen Arden, Jed Liu, and Andrew C. Myers. 2015. Flow-Limited Authorization. In 28th IEEE Computer Security Foundations Symp. (CSF). 569–583. doi:10.1109/CSF.2015.42DOI
  7. [7]Aslan Askarov and Andrew C. Myers. 2011. Attacker Control and Impact for Confidentiality and Integrity. Logical Methods in Computer Science 7, 3 (Sept. 2011). http://www.cs.cornell.edu/andru/ papers/robknowledge-lmcs.pdf
  8. [8]Abhishek Bichhawat, McKenna McCall, and Limin Jia. 2021. Gradual Security Types and Gradual Guarantees. In 2021 IEEE 34th Computer Security Foundations Symposium (CSF). 1–16. doi:10.1109/CSF51468.2021.00015DOI
  9. [9]Pablo Buiras, Dimitrios Vytiniotis, and Alejandro Russo. 2015. HLIO: Mixing Static and Dynamic Typing for Information-Flow Control in Haskell. In 20th ACM SIGPLAN Int’l Conf. on Functional Programming. ACM, 289–301. doi:10.1145/2784731.2784758DOI
  10. [10]Ran Canetti. 2001. Universally Composable Security: A New Paradigm for Cryptographic Protocols. In 42nd Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society, 136–145. doi:10.1109/SFCS.2001.959888
  11. [11]Ethan Cecchetti, Andrew C. Myers, and Owen Arden. 2017. Nonmalleable Information Flow Control. In 24th ACM Conf. on Computer and Communications Security (CCS) (Dallas, TX). ACM, 1875–1891. doi:10.1145/3133956.3134054
  12. [12]Ethan Cecchetti, Siqiu Yao, Haobin Ni, and Andrew C. Myers. 2021. Compositional Security for Reentrant Applications. In IEEE Symp. on Security and Privacy. doi:10.1109/SP40001.2021.00084DOI
  13. [13]Tianyu Chen and Jeremy G. Siek. 2024. Quest Complete: The Holy Grail of Gradual Security. Proc. ACM Program. Lang. 8, PLDI, Article 212 (June 2024), 24 pages. doi:10.1145/3656442DOI
  14. [14]CoinDesk. 2021. Cross-Chain DeFi Site Poly Network Hacked; Hundreds of Millions Potentially Lost. https://www.coindesk.com/markets/2021/08/10/cross-chain-defi-site-poly-network-hacked-hundreds-of-millions-potentially-lost. Accessed August 2023.
  15. [15]CoinDesk. 2024. DeFi Protocol LI.FI Struck by $11M Exploit. https://www.coindesk.com/business/2024/07/16/defi-protocol-lifi-struck-by-8m-exploit/. Accessed October 2024.
  16. [16]Cointelegraph. 2023. Dexible aggregator hacked for $2M via ‘selfSwap’ function. https://cointelegraph.com/news/dexibleapp-aggregator-hacked-for-2m-via-selfswap-function. Accessed August 2023.
  17. [17]Phil Daian. 2016. Analysis of the DAO exploit. https://hackingdistributed.com/2016/06/18/analysis-of-the-dao-exploit/. Accessed March 2021.
  18. [18]Dominique Devriese, Marco Patrignani, Frank Piessens, and Steven Keuchel. 2017. Modular, Fully-abstract Compilation by Approximate Back-translation. Logical Methods in Computer Science Volume 13, Issue 4 (Oct. 2017). doi:10.23638/ lmcs-13(4:2)2017DOI
  19. [19]Cormac Flanagan, Amr Sabry, Bruce F. Duba, and Matthias Felleisen. 1993. The Essence of Compiling With Continuations. In ACM SIGPLAN Conf. on Programming Language Design and Implementation (PLDI) (Albuquerque, New Mexico, USA) (PLDI ’93). 237–247. doi:10.1145/155090.155113
  20. [20]Joseph A. Goguen and José Meseguer. 1982. Security Policies and Security Models. In IEEE Symp. on Security and Privacy. 11–20. doi:10.1109/SP.1982.10014DOI
  21. [21]Norm Hardy. 1988. The Confused Deputy: (or Why Capabilities Might Have Been Invented). SIGOPS Oper. Syst. Rev. 22, 4 (Oct. 1988), 36–38. http://dl.acm.org/citation.cfm?id=54289.871709
  22. [22]Matthew Hennessy, Julian Rathke, and Nobuko Yoshida. 2005. SAFEᴰPI: A Language for Controlling Mobile Code. Acta Informatica 42, 4 (2005), 227–290.
  23. [23]Jérémie Koenig and Zhong Shao. 2021. CompCertO: compiling certified open C components. In Proceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation (Virtual, Canada) (PLDI 2021). Association for Computing Machinery, New York, NY, USA, 1095–1109. doi:10.1145/3453483.3454097DOI
  24. [24]Eliza Kozyri, Stephen Chong, and Andrew C. Myers. 2022. Expressing Information Flow Properties. Foundations and Trends in Privacy and Security 3, 1 (2022), 1–102. doi:10.1561/3300000008DOI
  25. [25]Jed Liu, Michael D. George, K. Vikram, Xin Qi, Lucas Waye, and Andrew C. Myers. 2009. Fabric: A Platform For Secure Distributed Computation and Storage. In 22nd ACM Symp. on Operating System Principles (SOSP). 321–334. http://www.cs.cornell.edu/andru/papers/fabric-sosp09.html
  26. [26]Nancy A. Lynch and Mark R. Tuttle. 1987. Hierarchical Correctness Proofs for Distributed Algorithms. In 6th ACM Symp. on Principles of Distributed Computing. Fred B. Schneider (Ed.). ACM, 137–151. doi:10.1145/41840.41852DOI
  27. [27]The mathlib Community. 2020. The lean mathematical library. In Proceedings of the 9th ACM SIGPLAN International Conference on Certified Programs and Proofs (New Orleans, LA, USA) (CPP 2020). Association for Computing Machinery, New York, NY, USA, 367–381. doi:10.1145/3372885.3373824DOI
  28. [28]Leonardo de Moura and Sebastian Ullrich. 2021. The Lean 4 Theorem Prover and Programming Language. In Automated Deduction – CADE 28: 28th International Conference on Automated Deduction, Virtual Event, July 12–15, 2021, Proceedings. Springer-Verlag, Berlin, Heidelberg, 625–635. doi:10.1007/978-3-030-79876-5_37DOI
  29. [29]Andrew C. Myers. 1999. JFlow: Practical Mostly-Static Information Flow Control. In 26th ACM Symp. on Principles of Programming Languages (POPL). 228–241. doi:10.1145/292540.292561DOI
  30. [30]Max S. New, William J. Bowman, and Amal Ahmed. 2016. Fully abstract compilation via universal embedding. In Proceedings of the 21st ACM SIGPLAN International Conference on Functional Programming (Nara, Japan) (ICFP 2016). Association for Computing Machinery, New York, NY, USA, 103–116. doi:10.1145/2951913.2951941
  31. [31]Ben Niu and Gang Tan. 2014. Modular control-flow integrity. SIGPLAN Not. 49, 6 (June 2014), 577–587. doi:10.1145/2666356.2594295DOI
  32. [32]Marco Patrignani, Robert Künnemann, and Riad S. Wahby. 2022. Universal Composability is Robust Compilation. ACM Transactions on Programming Languages and Systems (2022). doi:10.1145/3436809
  33. [33]Marco Patrignani, Riad S. Wahby, and Robert Künnemann. 2019. Universal Composability is Secure Compilation. arXiv ePrint 1910.08634. doi:10.48550/arXiv.1910.08634DOI
  34. [34]Vineet Rajani, Deepak Garg, and Tamara Rezk. 2016. On Access Control, Capabilities, Their Equivalence, and Confused Deputy Attacks. In 2016 IEEE 29th Computer Security Foundations Symposium (CSF), 150–163. doi:10.1109/CSF.2016.18DOI
  35. [35]Silei Ren, Coşku Acay, and Andrew C. Myers. 2025. An Algebraic Approach to Asymmetric Delegation and Polymorphic Label Inference. In European Symposium on Research in Computer Security (ESORICS).DOI
  36. [36]James Riely and Matthew Hennessy. 2003. Trust and Partial Typing in Open Systems of Mobile Agents. J. Automated Reasoning 31, 3 (2003), 335–370.
  37. [37]Andrei Sabelfeld and Andrew C. Myers. 2003. Language-Based Information-Flow Security. IEEE Journal on Selected Areas in Communications 21, 1 (Jan. 2003), 5–19. doi:10.1109/JSAC.2002.806121
  38. [38]Fred B. Schneider. 2001. Enforceable Security Policies. ACM Transactions on Information and System Security 3, 1 (2001), 30–50. Also available as TR 99-1759, Computer Science Department, Cornell University, Ithaca, New York.
  39. [39]Jeremy Siek and Walid Taha. 2007. Gradual Typing for Objects. In 21st European Conf. on Object-Oriented Programming, 2–27.
  40. [40]Jeremy G. Siek, Michael M. Vitousek, Matteo Cimini, and John Tang Boyland. 2015. Refined Criteria for Gradual Typing. In Summit on Advances in Programming Languages. https://api.semanticscholar.org/CorpusID:15383644DOI
  41. [41]Matías Toro, Ronald Garcia, and Éric Tanter. 2018. Type-Driven Gradual Security with References. ACM Transactions on Programming Languages and Systems 40, 4, Article 16 (2018). doi:10.1145/3229061DOI
  42. [42]Philip Wadler and Robert Bruce Findler. 2009. Well-typed programs can’t be blamed. In European Symposium on Programming.
  43. [43]Andrew K. Wright and Matthias Felleisen. 1994. A Syntactic Approach to Type Soundness. Information and Computation 115, 1 (1994), 38–94. doi:10.1006/inco.1994.1093DOI
  44. [44]Siqiu Yao, Haobin Ni, Andrew C. Myers, and Ethan Cecchetti. 2024. SCIF: A Language for Compositional Smart Contract Security. Technical Report abs/2407.01204. arXiv. https://arxiv.org/abs/2407.01204
  45. [45]Steve Zdancewic and Andrew C. Myers. 2001. Robust Declassification. In 14th IEEE Computer Security Foundations Workshop (CSFW) (Cape Breton, Nova Scotia, Canada), 15–23. doi:10.1109/CSFW.2001.903133
  46. [46]Steve Zdancewic and Andrew C. Myers. 2001. Secure Information Flow and CPS. In 10th European Symposium on Programming (Lecture Notes in Computer Science, Vol. 2028), David Sands (Ed.). Springer Berlin Heidelberg, 46–61. doi:10.1007/3-540-45309-1_4DOI
  47. [47]Steve Zdancewic and Andrew C. Myers. 2003. Observational Determinism for Concurrent Program Security. In 16th IEEE Computer Security Foundations Workshop (CSFW) (Pacific Grove, California), 29–43. doi:10.1109/CSFW.2003.1212703DOI

Paper details

vlnc:W_zn8babht
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Codex, Claude Code

View statement
Looking for related papers…
Contents