betaFeedback

WorksComputer Science

Demystifying Information Flow Downgrading using the Real–Ideal Paradigm

Abstract

The real–ideal paradigm, an approach to security specification developed in the cryptography community, has the benefit that it can express sophisticated confidentiality and integrity requirements, even for decentralized systems. We show that this paradigm is the basis for a powerful and intuitive new semantic framework for language-based security. Our new framework cleanly and extensionally captures existing security definitions, including not only noninterference but also less understood information flow properties that involve downgrading, such as robust declassification and nonmalleable information flow. Past semantics for these properties have relied on intensional downgrading events. Further, we show that all of these properties can be enforced by a practical information-flow type system for a while-language that supports downgrading. Surprisingly, correctness of this type system is also characterized as a real–ideal simulation, with an important implication: the security of heterogeneous, decentralized systems with a strong (real) attacker can be understood by reasoning about a weak (ideal) attacker whose power is restricted to interaction with downgrading. This result explains the usefulness of nonmalleable information flow and related security properties. The results are fully formalized using the Rocq prover and are publicly available.

ACM Reference Format:

Suraaj Kanniwadi and Andrew C. Myers. 2026. Demystifying Information Flow Downgrading using the Real–Ideal Paradigm. 1, 1 (November 2026), 28 pages. https://doi.org/10.1145/nnnnnnn.nnnnnnn

Introduction

Building secure systems is difficult: they must provide some degree of functional correctness despite the presence of adversaries who may try to subvert their functioning or learn unauthorized secrets. A serious obstacle to designing systems that are secure is that we lack security specifications: precise descriptions of what it means for the system to be secure. Without such specifications, arguments about whether the system is secure have no solid foundation, and we have no way to prove that systems are secure. In the current era where automated AI-driven attacks pose a growing threat, security proofs may be the best hope for trustworthy computing systems.

Defining security becomes even more challenging in decentralized systems, which are implemented by principals who may not trust each other. Here, specification and enforcement of security needs to be done for all such principals. For example, a secure system implemented by an Alice–Bob protocol not only upholds guarantees when Alice and Bob

Authors’ Contact Information: Suraaj Kanniwadi, Department of Computer Science Cornell University, Ithaca, New York, United States of America, [email protected]; Andrew C. Myers, Department of Computer Science Cornell University, Ithaca, New York, United States of America, [email protected].

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

© 2026 Copyright held by the owner/author(s). Publication rights licensed to ACM.

Manuscript submitted to ACM follow the protocol; it continues to uphold reasonable guarantees for Alice even when Bob is malicious and violates the protocol, and conversely for Bob when Alice is malicious.

Of course, there is a storied history of useful techniques for specifying and enforcing functional correctness. However, classic specification techniques aim only to enforce safety or liveness properties [5], and therefore do not capture important security requirements such as the absence of information leakage.

A desirable property for any specification is to be extensional, meaning that the specification constrains the externally observable behavior of the system rather than how the system is expressed as code. The classic example of an extensional security property is noninterference [34], the E. coli of information-flow security properties—highly studied but too simple. Unfortunately, noninterference does not capture the nuances of real computer systems, which need to allow controlled release of information and in which confidentiality and integrity requirements interact. More expressive power is needed to capture their subtle security requirements.

Therefore, our work advocates for a new framework for extensionally specifying language-based security, adapted from the cryptographic real–ideal paradigm [16, 35, 45, 46]. We demonstrate how several existing information-flow properties are given simple, intuitive descriptions in this framework. Noninterference is neatly captured by this framework, but so are less-understood properties such as robust declassification [63] (RD) and nonmalleable information flow (NMIF) [21]. This approach improves on the existing specification of NMIF as a 4-hyperproperty, because that specification is intensional, requiring both a semantics instrumented with syntactic downgrading events and a complex exclusion of inept attackers. The new formal description captures NMIF’s informal characterization more directly and extensionally.

In fact, we argue that even the soundness statements for practical information flow type systems must be given as real–ideal statements. Practical information flow type systems allow downgrading, which breaks noninterference. Still, these type systems give programmers useful informal assurance that program security is primarily tied to these downgrading statements, which can then be manually audited to detect security vulnerabilities [32]. We formalize this sentiment as a real–ideal statement, and show that it is a useful high-level specification. In fact, we show, surprisingly, how previously defined information flow properties (RD, NMIF, etc.) can be enforced as corollaries of this single real–ideal statement.

We formalize this new security framework by constructing a simple imperative language ImpThreat, which is the classic Imp while-language with an operational semantics enriched with adversary interactions. Our real–ideal emulation definition for ImpThreat allows simple and extensional definitions of information flow security properties. Additionally, we demonstrate our real–ideal security type soundness theorem by proving it for an information flow type system that extends ImpThreat with support for downgrading. In addition, the type system enforces heterogeneous security: a generalization ensuring security for systems implemented by mutually untrusting principals.

In summary, we make the following contributions:

  • We identify a need for better security specifications and motivate the real–ideal paradigm (§ 2).

  • We discuss how to apply the real–ideal paradigm in the language-based setting (§ 3).

  • We discuss information flow properties for which we develop real–ideal specifications (§ 4).

  • We give a language-based formalization of the real–ideal paradigm using ImpThreat, a while language enriched with adversarial semantics, and use this framework to give simple and extensional definitions of less-understood security properties such as robust declassification and transparent endorsement (§ 5).

  • We argue for a real–ideal type soundness theorem for information flow type systems and demonstrate its usefulness (§ 6).

  • We construct the first formally verified information flow type system with a real–ideal type soundness theorem that captures security concerns such as privacy (§ 7).

  • We extend the type system to also handle heterogeneous security of decentralized systems implemented by mutually untrusting principals (§ 8).

All formalization is fully mechanized and verified in the Rocq theorem prover.

Motivation

Specifying and enforcing security requirements

Trace properties [5, 40] are the most commonly used way to specify allowed system behavior. A trace property is a collection of permitted single executions; an implementation satisfies a specification if each individual execution of the implementation is permitted by the specification. In other words, the implementation behaviors refine the behaviors allowed by the specification. Such specifications are very useful when reasoning about functional correctness but are not expressive enough to capture security requirements.

The main reason is that many natural security properties (especially those involving privacy) talk about causality or information flow, and cannot be captured by trace properties [56]. Admittedly, the notion of hyperproperties [26] addresses this limitation of trace refinement, and generalizes the notion of what specifications are and what it means for an implementation to satisfy a specification by defining a specification to simply be a set of implementations (trace sets) that satisfy it. Hyperproperties are a general description of allowed behavior—too general, perhaps, because they encompass behavioral restrictions that we do not normally think of as being about security. There is a burgeoning literature on techniques for logically specifying and model checking hyperproperties [27, 28, 33], but there are real gaps both between translating human-understandable security requirements into these logics and between these logics and their practical enforcement.

The cryptography community offers another solution to the problem of stating and enforcing security specifications: the real–ideal paradigm. In this paradigm, systems are enriched with an explicit, operational threat model: back-door interfaces via which adversaries can learn information and influence the system. A specification is also modeled as such a system—the ideal system—which is simpler and has more-constrained adversary interfaces. The goal is then to demonstrate that this ideal system is emulated by the real system, by demonstrating that every attack on the real system is equivalent to some attack on the ideal system.

While the details are made precise in § 3, it is important to understand that this equivalence includes not only regular system input–output (I/O) but also adversary leakage: information that the adversary learns. System I/O equivalence captures integrity requirements, and adversary leakage equivalence captures confidentiality requirements. Crucially, real–ideal emulation can capture realistic system specifications which intertwine integrity and confidentiality requirements, such as nonmalleable information flow (NMIF) [21] and robust declassification (RD) [63].

Nonmalleable information flow as real–ideal emulation

Nonmalleable information flow (NMIF) was originally motivated [21] using a sealed-bid auction (Figure 1). Here, Alice and Bob engage in a two-party sealed-bid auction implemented by auctioneer. They both trust auctioneer to take their bids independently and to reveal the winner. The labels AA and BB denote the trust levels of Alice and Bob respectively, and thus the input bids that they supply, alice_bid and bob_bid, have those integrity labels. Since auctioneer is written using a language that enforces information flow control, it must endorse (trust) these untrusted input bids.

An insecure sealed-bid auction and its attack trace under Bob’s mauling

Figure 1. An insecure sealed-bid auction (top) and its attack trace under Bob’s mauling (bottom).

An auctioneer that violates NMIF allows an attack where a malicious Bob sets his bid based on Alice’s: bob_bid := alice_bid + 1, thereby winning the auction with a minimal winning bid. This insecure program has the confidentiality labels of the input bids set to A∧BA \mathbin{\wedge} B—a highly restrictive confidentiality label that neither Alice nor Bob can read—which permits the assignment bob_bid := alice_bid + 1 without violating the rules for secure information flow. To satisfy NMIF, auctioneer lowers the confidentiality label for the input bids as shown in the figure, and bob_bid := alice_bid + 1 is no longer permitted because AA confidentiality data (alice_bid) is assigned into a BB confidentiality variable (bob_bid). The higher confidentiality label for the bids makes the program less secure!

The original paper pins this program’s violation of NMIF to insecure endorse statements, where the source variables of the endorsement contain confidential information inaccessible to the provider. The insecure auctioneer endorses bob_bid containing information about alice_bid, which is inaccessible to Bob. NMIF is then formalized using endorsement events and declassification events that explicitly appear in the program trace. Because it depends on these program events, the original NMIF formalization is not fully extensional. Extensional definitions—like noninterference—are preferable because they depend only on the behavior of the system and not on how the program is expressed.

We can formulate NMIF extensionally. Our insight is that the program’s insecurity arises from the advantage an adversary gains by mauling—changing untrusted state as a function of other (possibly secret) system state. Bob updates the variable bob_bid using state (alice_bid) that he cannot see, letting him win the auction with a minimal winning bid.

A secure program satisfying NMIF should not give such maulers any advantage. We can state this as an extensional security requirement: programs satisfy NMIF if an adversary that can maul is equivalent in power to one that cannot. This is a real–ideal statement where ideal adversaries cannot maul and real adversaries may.

Information flow type soundness as real–ideal emulation

Practical information flow type systems [14, 48, 54] allow downgrading. Unfortunately, with downgrading, noninterference is lost. Despite losing this formal guarantee, in practice, such type systems seem to provide some informal security assurance to programmers by tying program vulnerabilities primarily to these downgrading statements. Empirical studies of using such information-flow type systems equipped with downgrading suggest that this assurance is real [32]. It seems to suffice to reason about adversarial interaction with only program downgrading statements, despite real-world adversaries seemingly having more power.

It is an attractive goal to formalize and provably enforce the informal sentiment above, to obtain strong guarantees that hold up against determined attackers. It is thus crucial to have a building block for specifying security of systems with downgrading. Furthermore, as we show in § 6.1, this security requirement is a good abstraction, as it suffices to reason about these hypothetical adversaries to prove program properties such as NMIF.

The real–ideal paradigm again naturally captures the requirement that it suffices to reason about downgrade-constrained adversaries: ideal adversaries are downgrade-constrained, while real adversaries are not. We formally specify this requirement of downgrade-constrained adversaries in § 6. Additionally, we demonstrate a mechanically verified enforcement (§ 7 and § 8) for a static information flow type system that permits controlled downgrading. Well-typed programs satisfy a real–ideal soundness theorem: powerful real-world adversaries are simulated by downgrade-constrained ideal-world adversaries. This type system is also designed with the goal of heterogeneous security, where mutual distrust between principals requires us to consider and enforce security for multiple adversarial scenarios.

The Viaduct system [3, 4] builds on a similar insight about the value of real–ideal emulation in the setting of language-based security, but for a limited language that does not permit secret or untrusted control flow. The Viaduct proof of correctness is phrased as real–ideal emulation connecting its source language to a distributed, concurrent, cryptographic target language. The proof relies on the fact that the Viaduct source language subjects downgrading to a similar typing discipline, but the role of this restriction is not made clear. The present work has a more general source language, and its real–ideal emulation clarifies the role of information-flow typing in Viaduct (§ 8.1).

The real–ideal paradigm

Informally, the real–ideal paradigm can be thought of as a generalization of trace refinement [1, 44]. While the refinement paradigm aims to show how a system implementation refines a more abstract specification, the real–ideal paradigm requires an emulation from a more abstract specification along with a more abstract threat model. In the abstract threat model, the adversary lacks some power that the real adversary possesses; the emulation shows that the real adversary gains no advantage from possessing that power.

Definition 3.1 (Real–ideal emulation). A real system srs_r emulates an ideal system sis_i (denoted sr→emulatessis_r \xrightarrow{\text{emulates}} s_i) if every (real) attack on srs_r is equivalent to some (ideal) attack on sis_i:

sr→emulatessi≜∀Ar. ∃Ai. [sr∣Ar]≈[si∣Ai]s_r \xrightarrow{\text{emulates}} s_i \quad\triangleq\quad\forall A_r.\ \exists A_i.\ [s_r \mid A_r] \approx[s_i \mid A_i]

Here, ArA_r ranges over allowed attackers on real programs, AiA_i ranges over allowed ideal program attackers, and the relation ≈\approx denotes behavioral equivalence.

For every real attack ArA_r, it must be possible to construct an ideal attack AiA_i that simulates it: the ideal attack AiA_i is the simulator for the real attack ArA_r. Consequently, the real–ideal paradigm is also known as simulation-based security.

As stated in § 2.1, the notion of behavior [ ⁣[⋅] ⁣][\![\cdot]\!] includes both system input–output (I/O) as well as adversary leakage, which models information that the adversary learns. The former is useful for capturing system integrity requirements, while the latter captures system confidentiality requirements.

We present an illustrative example for confidentiality. Suppose a real system adversary ArA_r can learn and leak the value of a variable vleakv_{\mathrm{leak}}. However, the real system srs_r ensures that vleakv_{\mathrm{leak}} is always equal to 42. In this situation, srs_r emulates an sis_i that does not let its adversaries read any information. This is because, although ArA_r can read vleakv_{\mathrm{leak}} and leak it, this behavior can be simulated by an AiA_i that leaks 42 instead of vleakv_{\mathrm{leak}}. On the other hand, if srs_r did store some secret data in vleakv_{\mathrm{leak}}—a confidentiality violation—it would be impossible to construct a real–ideal emulation. When ArA_r leaks vleakv_{\mathrm{leak}}, AiA_i cannot simulate it by leaking the same value because vleakv_{\mathrm{leak}} contains secret data unknown to AiA_i.

Behavioral equivalence of system I/O corresponds to the well-known notion of trace refinement. A trace refinement specification is nondeterministic and specifies all allowed executions; a conforming implementation must ensure that all its own executions are allowed by the specification. The real–ideal paradigm captures this nondeterminism as adversarial influence. As execution proceeds, this adversarial influence may cause different program behavior, which is what (demonic) nondeterminism is! Requiring that an ideal adversary exist for every real adversary is then exactly equivalent to the refinement requirement. In this way, the real–ideal paradigm gives a satisfactory explanation of demonic nondeterminism [30].

Behavioral equivalence

Definition 3.1 is parameterized by a notion of behavioral equivalence: the relation ≈\approx, the precise instantiation of which depends on the use case. For instance, the original formulation of the real–ideal paradigm [16, 35] formulates this equivalence of behaviors as an indistinguishability game between the real and ideal worlds, where we can choose among information-theoretic, statistical, or computational indistinguishability.

For this work, we use a simple version of information-theoretic (perfect) indistinguishability: the semantic function ⟦⋅⟧\llbracket\cdot\rrbracket gives the trace of events that occurs for each initial input. In these traces, some events might be empty stutters.

For behavioral equivalence, termination sensitivity [8, 64] warrants strong trace equivalence, while termination insensitivity requires (only) weak trace equivalence.

Definition 3.2 (Strong trace equivalence). Traces τ1\tau_1 and τ2\tau_2 are strongly equal (denoted τ1≈stτ2\tau_1 \mathrel{\approx^{t}_{s}} \tau_2) if they are equal after stripping all stuttering events.

Definition 3.3 (Weak trace equivalence). Traces τ1\tau_1 and τ2\tau_2 are weakly equal (denoted τ1≈wtτ2\tau_1 \mathrel{\approx^{t}_{w}} \tau_2) if they are strongly equal, or if they have strongly equal prefixes, after which one of them stutters forever.

To rule out pathological ideal attackers which might halt system execution by blocking progress—making the real and ideal trace trivially weakly equal—we formulate an additional fairness restriction on ideal attackers.

Definition 3.4 (Fair ideal attacker). An attacker AiA_i is fair for an srs_r, sis_i, and an attacker ArA_r iff it never takes a step without one of srs_r, sis_i or ArA_r also taking a step. A fair ideal attacker can thus never block progress alone.

In this paper, this fairness restriction is required for all real–ideal statements that use weak trace equivalence. Note that by making the ideal attacker weaker, we strengthen the security guarantee offered by real–ideal emulation: the real attacker is shown equivalent in power to a weaker attacker.

Single program properties

Definition 3.1 defines →emulates\xrightarrow{\text{emulates}} as a binary predicate over srs_r and sis_i. It is also valuable to tweak this definition to be a unary predicate over a single program pp, by only restricting the collection of ideal attackers. That is, if Atkreal\mathrm{Atk}_{\mathrm{real}} is the set

Manuscript submitted to ACM of real attackers, we define another Atkideal\mathrm{Atk}_{\mathrm{ideal}} which contains very restricted attackers. Such an ideal attack restriction defines a unary predicate over pp.

Definition 3.5 (Unary real–ideal emulation). A program pp with a real attacker set Atkreal\mathrm{Atk}_{\mathrm{real}} emulates a simpler Atkideal\mathrm{Atk}_{\mathrm{ideal}} when every Ar∈AtkrealA_r \in\mathrm{Atk}_{\mathrm{real}} is equivalent to some Ai∈AtkidealA_i \in\mathrm{Atk}_{\mathrm{ideal}}.

∀Ar∈Atkreal. ∃Ai∈Atkideal. ⟦p∣Ar⟧≈⟦p∣Ai⟧\forall A_r \in\mathrm{Atk}_{\mathrm{real}}.\ \exists A_i \in\mathrm{Atk}_{\mathrm{ideal}}.\ \llbracket p \mid A_r \rrbracket\approx\llbracket p \mid A_i \rrbracket

All security properties considered in this work are formulated as unary real–ideal statements.

Information flow security

Information flow security seeks to defend against a powerful threat model. Adversaries are given intimate read and write access to some part of the system state. For example, adversaries are assumed to be able to read the state of all public variables, often even at any point during execution, and similarly they can freely modify untrusted variables. Such adversaries are arguably more powerful than any real-world adversary in a wide range of scenarios, from applications using untrusted libraries to even distributed systems implemented by principals with mutual distrust.

Noninterference [34] is the best-known information flow security property. Applied to both confidentiality and integrity, it requires an adversary to be completely prevented both from learning secret data and from corrupting trusted data. Noninterference is simple, can be formulated extensionally, and is fairly straightforward to enforce. However, the nuanced security requirements of realistic systems typically violate noninterference. Additionally, while noninterference for confidentiality and integrity can be factored into two independent noninterference statements, realistic security requirements intertwine these two aspects.

Security properties beyond noninterference

There have been a few prior attempts to formulate useful security properties that capture more realistic system security concerns. A well-known example is the following family of properties: robust declassification (RD), transparent endorsement (TE), and nonmalleable information flow (NMIF). They attempt to define secure violations of noninterference for confidentiality (RD), integrity (TE), or both (NMIF).

Robust declassification. Robust declassification informally says that an active attacker cannot learn more by interfering than a passive attacker (one that only observes) could. Equivalently, the attacker cannot exploit its power to corrupt information to cause the program to declassify more (or different) secret information than it would have leaked anyway.

The statement p:=u∗sp := u * s violates robust declassification. Here pp is a public variable visible to the attacker, while ss is secret and not visible. Untrusted variable uu is initially zero, so the passive attacker does not learn ss from seeing pp. Since uu is untrusted, the attacker controls its value; by changing the value of uu to be non-zero, an active attacker learns the value of ss.

Transparent endorsement. Transparent endorsement informally says that a value can only be endorsed (raised in integrity) if the principal supplying the value to be endorsed can already read it. The endorsed value contains nothing that its supplier didn’t already know—hence “transparent”. Equivalently, values that could have been mauled should not be endorsed.

Our example in § 2.2 is actually an example of a transparent endorsement violation. Bob supplies bob_bid\mathtt{bob\_bid}, whose value is endorsed despite it not being transparent to Bob.

Varx,yValvBoolbBinOp⊕∈Val→Val→ValTestt∈Val→BoolStoreσ∈Var→ValValExpev::=x⊕yBoolExpeb::=t(x)Commandc::=x:=ev∣if eb then p else p∣while eb do p∣output xProgramp::=ε∣c;p\begin{aligned} \mathrm{Var}\quad&x,y \qquad\mathrm{Val}\quad v \qquad\mathrm{Bool}\quad b\\ \mathrm{BinOp}\quad&\oplus\in\mathrm{Val}\to\mathrm{Val}\to\mathrm{Val}\\ \mathrm{Test}\quad&t \in\mathrm{Val}\to\mathrm{Bool}\\ \mathrm{Store}\quad&\sigma\in\mathrm{Var}\to\mathrm{Val}\\ \mathrm{ValExp}\quad&e_v ::= x\oplus y\\ \mathrm{BoolExp}\quad&e_b ::= t(x)\\ \mathrm{Command}\quad&c ::= x:=e_v\mid\mathrm{if}\ e_b\ \mathrm{then}\ p\ \mathrm{else}\ p\\ &\qquad\mid\mathrm{while}\ e_b\ \mathrm{do}\ p\mid\mathrm{output}\ x\\ \mathrm{Program}\quad&p ::= \varepsilon\mid c;p \end{aligned}
Substepssubsteps∈NatPreCmdcmdpre∈Stateadv→Store→StorePostCmdcmdpost∈Stateadv→Store→Stateadv×SubstepsInitadvinit∈Store→StateadvNextadvnext::=⟨cmdpre,cmdpost⟩Adversaryadv::=⟨Stateadv,advinit,advnext⟩(subject to restriction (definition 5.1))\begin{aligned} \mathrm{Substeps}\quad&substeps\in\mathrm{Nat}\\ \mathrm{PreCmd}\quad&cmd_{pre}\in\mathrm{State}_{adv}\to\mathrm{Store}\to\mathrm{Store}\\ \mathrm{PostCmd}\quad&cmd_{post}\in\mathrm{State}_{adv}\to\mathrm{Store}\to\mathrm{State}_{adv}\times\mathrm{Substeps}\\ \mathrm{Init}\quad&adv_{init}\in\mathrm{Store}\to\mathrm{State}_{adv}\\ \mathrm{Next}\quad&adv_{next}::=\langle cmd_{pre},cmd_{post}\rangle\\ \mathrm{Adversary}\quad&adv::=\langle\mathrm{State}_{adv},adv_{init},adv_{next}\rangle\\ &\text{(subject to restriction (definition 5.1))} \end{aligned}

Nonmalleable information flow. Nonmalleable information flow can be informally thought of as a mixture of RD and TE. RD still enforces integrity noninterference while ensuring confidentiality downgrading, while TE still enforces confidentiality noninterference while ensuring integrity downgrading. NMIF relaxes both: mauled values may affect neither confidentiality nor integrity.

Limitations. The original state-machine based formalization [63] of robust declassification elegantly formulates RD as a requirement that every attacker learn at most as much as a passive version of itself which removes all of its adversarial actions. Thus, every active attacker learns no more than a passive attacker. The restriction on learning information is formulated using the Lattice of Information [41]. Unfortunately, this formalism does not seem to generalize well in later works that extend it for programming languages and in nonmalleable information flow [20, 21, 50, 62]. These definitions are intensional: they require instrumenting the run-time semantics of programs with downgrade events. Additionally, the formalism has a complicated exclusion of inept attackers, defined as attackers who do not use their ability fully.

A real–ideal intuition. All of the above properties seek to effectively eliminate an aspect of the real adversary’s powers. Nonmalleable information flow seeks to eliminate an adversary’s ability to maul data, while robust declassification takes a step further and seeks to eliminate its entire ability to corrupt data. Equivalently, we would like to reason about programs as if all adversaries had these limitations. As we show in § 5.2, the real–ideal paradigm makes these statements precise. Such limited adversaries will be our ideal adversaries, and we will require that seemingly more powerful real adversaries can be simulated by these weaker adversaries.

Semantic framework

Threat models, which define the power of adversaries running concurrently with programs, are crucial for defining security properties. The security offered by a system depends on the power of the adversary attacking it. Any system can defend against an adversary that does and observes nothing; no system can defend against an omnipotent adversary. The correctness of a defense is always defined with respect to the threat model it was designed for.

We model computation in the presence of an adversary using ImpThreat, an imperative while-language enriched with adversarial semantics. Language syntax (Figure 2) is presented by defining the syntax of commands and programs mutually inductively. ImpThreat’s syntax is fairly standard. It has assignments, conditionals (if), unbounded loops (while), and output statements to generate observations. Program state consists of a store: a map from variables to values.

ImpThreat syntax

Figure 2. ImpThreat syntax

In ImpThreat, resources that need protection are variables. A program runs along with an adversary advadv, which may interact with it. The limits of the adversary’s influence are defined using its adversarial power (definition 5.1).

Definition 5.1 (Adversarial Power). Adversarial power is a pair ⟨P,U⟩\langle P, U \rangle where P,U⊆VarP, U \subseteq\mathrm{Var} are the public and untrusted sets of variables, respectively.

An adversary can read public variables and corrupt untrusted variables. Not only can they corrupt by providing new values for variables, they can maul by supplying a transformation strategy for untrusted variables. The new values of mauled variables may depend on their old values or on other variables. Modeling mauling is necessary as realistic adversaries do have this ability. For instance, a UNIX process that has write but no read permission for a file can selectively zero out its first page. Another example comes from cryptography: when a malleable encryption scheme is used, adversaries can apply a known transformation on an otherwise inaccessible secret message.

The adversary itself is defined as a deterministic state machine (Figure 3), a triple consisting of a set of states, advinitadv_{\mathrm{init}} (its initial state construction), and advnextadv_{\mathrm{next}} (its next-step semantics). The initial state construction allows the adversary to initialize its state from the public variables of the initial program state, and the next-step transformation describes how the adversary runs beside the system.

Structure of an ImpThreat adversary with state space Stateadv

Figure 3. Structure of an ImpThreat adversary with state space Stateadv

ImpThreat’s operational semantics are defined as a small-step relation over system configurations (Figure 4). A configuration is a triple ⟨σ,ast,k⟩\langle\sigma, ast, k \rangle consisting of the program store σ\sigma, the adversary’s state astast and the system continuation kk, which describes the rest of the computation. A system continuation kk can be thought of as a generalization of a program; whereas a program is just a list of commands, continuations are lists of optional commands, which may be marked by ∗\ast, which indicates whether the adversary runs at that point. It is thus possible for the adversary and the program to execute independently.

Run-time configurations of ImpThreat

Figure 4. Run-time configurations of ImpThreat (* represents an active adversary)

We define how a configuration steps by composing our stepping semantics for commands with the adversary’s next-step transformation. Figure 5 illustrates selected stepping rules for commands. →store\xrightarrow{\mathrm{store}} denotes how commands transform the program store, while →cont\xrightarrow{\mathrm{cont}} denotes new program branches that need to run. Trivial rules, like if’s empty →store\xrightarrow{\mathrm{store}} behavior, are omitted.

Selected stepping rules for ImpThreat commands

Figure 5. Selected stepping rules for ImpThreat commands

These rules are sandwiched between adversary execution when a system continuation runs. More precisely, before a current command cc runs, the adversary may corrupt the store’s untrusted variables, and after cc runs, the adversary computes its next state by possibly learning the store’s public variables. Figure 6 shows an illustrative example.

Illustration of command execution composed with adversary execution

Figure 6. Illustration of command execution composed with adversary execution

Computing the next system continuation requires careful thought: in general, branches of if commands have different lengths, and we do not want to bake in hidden information channels that allow adversaries to learn which branch was taken by counting the number of commands in each branch. We avoid this problem by introducing a novel zipping substep semantics (Figure 7): at every step, an adversary explicitly chooses any number of substeps it wishes to run for, independent of whatever conditional branch is taken by a command. If the number of substeps chosen is fewer than the branch length, the adversary does not run when the branch’s excess commands do. If the number of substeps chosen is greater than the branch length, the adversary runs alone with no command executing after all the branch commands are complete. This new technique allows us to handle secret and untrusted control flow, which was out of reach of prior related work [4].

Zipping substep semantics

Figure 7. Zipping substep semantics

Real–ideal emulation

Recall the definition of unary real–ideal emulation (definition 3.5):

∀Ar∈Atkreal. ∃Ai∈Atkideal. ⟦p∣Ar⟧≈⟦p∣Ai⟧\forall A_r \in\mathrm{Atk}_{\mathrm{real}}.\ \exists A_i \in\mathrm{Atk}_{\mathrm{ideal}}.\ \llbracket p \mid A_r \rrbracket\approx\llbracket p \mid A_i \rrbracket

In order to instantiate this definition for ImpThreat, we are left with the following three questions: For a given ImpThreat program pp with attacker AA,

  1. How do you construct the initial configuration (p∣A)(p \mid A)?

  2. What is the notion of behavior ⟦⋅⟧\llbracket\cdot\rrbracket?

  3. When are two behaviors b1b_1 and b2b_2 equivalent (b1≈b2)(b_1 \approx b_2)?

The initial configuration. We describe the starting configuration (Figure 4) for a given ImpThreat program pp, when run with AA. The initial configuration κinit\kappa_{\mathrm{init}} is constructed from a given input store σinp\sigma_{\mathrm{inp}} with the σ\sigma component of κinit\kappa_{\mathrm{init}} equal to σinp\sigma_{\mathrm{inp}}. The adversary initializes its initial using advinitadv_{\mathrm{init}}. That is, the astast component of κinit\kappa_{\mathrm{init}} is equal to advinit(σinp)adv_{\mathrm{init}}(\sigma_{\mathrm{inp}}). Finally, the system continuation kk is constructed from the program pp. In kk, the adversary gets to run at every one of pp’s commands.

Defining behavior. The behavior for a given program pp when run with AA is given by the trace of events produced by κinit\kappa_{\mathrm{init}} for every input σinp\sigma_{\mathrm{inp}}. Figure 8 presents the syntax of an event. An event is a pair evcev_c and evaev_a, where evcev_c represents system I/O, and evaev_a is an adversarially leaked value.

ImpThreat events

Figure 8. ImpThreat events

A system I/O event evcev_c is a variable–value pair, and represents the output of a variable xx along with its value. It only makes sense to consider system I/O for honest variables. Adversarially corrupted variables represent a deviation from the guarantees the program was designed for. Formally then, only trusted variable outputs are recorded. Figure 9 shows the precise semantics. In addition to evcev_c, the adversary may leak an evaev_a, depending on its state. In general, an adversary that knows more is able to leak more.

Selected command events

Figure 9. Selected command events

An event with both evcev_c and evaev_a equal to ϵ\epsilon is a stutter, and represents a silent step. Our notions of behavioral equivalence are stutter-invariant: stutter steps are erased during comparison.

Behavioral equivalence is now the following.

⟦p∣Ar⟧≈⟦p∣Ai⟧≜∀σinp.⟦p∣Ar⟧(σinp)≈t⟦p∣Ai⟧(σinp)\llbracket p \mid A_r \rrbracket\approx\llbracket p \mid A_i \rrbracket\triangleq\forall\sigma_{\mathrm{inp}}.\llbracket p \mid A_r \rrbracket(\sigma_{\mathrm{inp}}) \approx^{t} \llbracket p \mid A_i \rrbracket(\sigma_{\mathrm{inp}})

Again, equivalence can be strong (definition 3.2) or weak (definition 3.3). We write ≈s\approx_s when using ≈st\approx^t_s and ≈w\approx_w when using ≈wt\approx^t_w respectively.

Semantic characterization of information flow properties

Our formalization of ImpThreat and its definition of real–ideal emulation (§ 5.1) give the necessary tools to formulate simple and extensional security property definitions. Here, we describe how to formalize the security properties described in § 4.1, namely nonmalleable information flow, robust declassification, transparent endorsement, and noninterference.

The security definitions of all these properties are presented as restrictions on ideal adversary abilities. For this, we require the following building blocks.

Definition 5.2 (Passive adversary). An adversary is passive when it does not use its corruption power. While it may learn and thus leak the store’s public view, it leaves the store’s untrusted view unchanged.

Definition 5.3 (Incurious adversary). An adversary is incurious when it does not read anything from the program store. In other words, its next state depends only on its current state.

Definition 5.4 (Nonmauling adversary). An adversary is nonmauling when it does not use its ability to maul. While it may corrupt untrusted variables, their updated values are supplied explicitly by the adversary.

Armed with these definitions, we now give semantic security definitions in real–ideal style.

Definition 5.5 (Nonmalleable information flow). A program pp satisfies nonmalleable information flow if any adversary has an equivalent adversary that cannot maul.

∀Ar∈Atkreal. ∃Ai∈Atknmif. ⟦p∣Ar⟧≈⟦p∣Ai⟧\forall A_r \in\mathrm{Atk}_{\mathrm{real}}.\ \exists A_i \in\mathrm{Atk}_{\mathrm{nmif}}.\ \llbracket p \mid A_r \rrbracket\approx\llbracket p \mid A_i \rrbracket

Definition 5.6 (Transparent endorsement). A program pp satisfies transparent endorsement if any adversary has an equivalent adversary that is both incurious and cannot maul.

∀Ar∈Atkreal. ∃Ai∈Atkte. ⟦p∣Ar⟧≈⟦p∣Ai⟧\forall A_r \in\mathrm{Atk}_{\mathrm{real}}.\ \exists A_i \in\mathrm{Atk}_{\mathrm{te}}.\ \llbracket p \mid A_r \rrbracket\approx\llbracket p \mid A_i \rrbracket

Definition 5.7 (Robust declassification). A program pp satisfies robust declassification if any adversary has an equivalent adversary that is passive.

∀Ar∈Atkreal. ∃Ai∈Atkrd. ⟦p∣Ar⟧≈⟦p∣Ai⟧\forall A_r \in\mathrm{Atk}_{\mathrm{real}}.\ \exists A_i \in\mathrm{Atk}_{\mathrm{rd}}.\ \llbracket p \mid A_r \rrbracket\approx\llbracket p \mid A_i \rrbracket

Definition 5.8 (Noninterference). A program pp satisfies noninterference if any adversary has an equivalent adversary that is both passive and incurious.

∀Ar∈Atkreal. ∃Ai∈Atkni. ⟦p∣Ar⟧≈⟦p∣Ai⟧\forall A_r \in\mathrm{Atk}_{\mathrm{real}}.\ \exists A_i \in\mathrm{Atk}_{\mathrm{ni}}.\ \llbracket p \mid A_r \rrbracket\approx\llbracket p \mid A_i \rrbracket

Table 1 summarizes restrictions for Atknmif\mathrm{Atk}_{\mathrm{nmif}}, Atkrd\mathrm{Atk}_{\mathrm{rd}}, Atkte\mathrm{Atk}_{\mathrm{te}}, and Atkni\mathrm{Atk}_{\mathrm{ni}}. Notably, these definitions are extensional and only depend on a program’s observable behavior.

AdversaryPropertyRestrictint_{\mathrm{int}}Restrictconf_{\mathrm{conf}}
AtkniAtk_{\mathrm{ni}}NoninterferencePassiveIncurious
AtkrdAtk_{\mathrm{rd}}Robust declassificationPassive—
AtkteAtk_{\mathrm{te}}Transparent endorsementNonmaulingIncurious
AtknmifAtk_{\mathrm{nmif}}Nonmalleable information flowNonmauling—

Table 1. Adversary restrictions for information flow properties

It is instructive to compare the original formulation of NMIF [21] with ours. The original definition is intensional, relying on the operational semantics to instrument the trace with downgrading events. Both the original definition and ours agree that the auction example (Figure 1) violates NMIF. Our definition rejects the example because for an adversarial Bob, who mauls using bob_bid := alice_bid + 1, there is no equivalent nonmauling ideal Bob. However, the two formulations differ on some examples. Suppose that the code of Figure 1 were modified so that the function always returns 0. In this case, the code satisfies our extensional definition of NMIF because a constant function cannot be affected by a mauler. In the original intensional definition, however, the endorses add events to the trace that cause the modified code to be considered in violation of NMIF—even though no observer can distinguish this function from a constant function that always returns 0.

Another important difference between the two definitions is that the original definition includes a complex restriction to exclude inept attackers who do not use all their adversarial abilities. In our framework, inept real attackers are handled trivially because they can be simulated by similarly inept ideal attackers. For example, consider this program adapted from the original paper: if s then p := u1 else p := 1 − u2, where ss is secret, pp is public, and the uu variables are untrusted and initially zero. This program satisfies robust declassification according to both definitions. In our new definition, the passive ideal attacker learns the secret ss and can thus simulate any active real attacker. A naive version of the original 4-hyperproperty definition would require the output value of pp to be independent of the value of the uu variables, which is mostly true except for the edge cases where u1+u2=1u_1 + u_2 = 1. This is an inept attack that learns nothing. Ruling out such irrelevant inputs requires additional, complex conditions.

Heterogeneous security

Our discussion so far has fixed a single adversarial power. While this model might be acceptable for reasoning about single-user programs, it limits the ability to faithfully model decentralized systems with mutually untrusted interacting principals.

In order to facilitate such reasoning, we generalize our real–ideal formalism (definition 3.1) to quantify over all reasonable adversarial powers P\mathcal{P}.

Formally, in the unary case, we require:

∀Ar∈P-Atkreal. ∃Ai∈P-Atkideal. ⟦p∣Ar⟧≈⟦p∣Ai⟧\forall A_r \in\mathcal{P}\text{-}\mathrm{Atk}_{\mathrm{real}}.\ \exists A_i \in\mathcal{P}\text{-}\mathrm{Atk}_{\mathrm{ideal}}.\ \llbracket p \mid A_r \rrbracket\approx\llbracket p \mid A_i \rrbracket

That is, for a real attack at some particular level, there must exist an ideal attacker at the same level. For instance, a corrupted real Bob in an Alice–Bob protocol must be simulated by a corrupted ideal Bob, and not some other principal.

This lets us capture quite expressive security concerns. Our NMIFC type system, which we present in § 8, offers such guarantees.

Real–ideal soundness for information flow types

Practical information flow type systems with downgrading [14, 48, 54] seem to have the guarantee that it suffices to simply audit downgrading statements in our programs. In particular, their syntax is extended with endorse and declassify statements. The former relaxes integrity noninterference, while the latter relaxes confidentiality noninterference. The informal guarantee allows programmers to only reason about adversarial interaction with program downgrading statements, despite real-world adversaries being much more powerful.

We make this statement precise for ImpThreat. The first step is to extend its syntax with downgrading statements (Figure 10). Syntactically, downgrading statements are a kind of assignment, and their →store\xrightarrow{\mathrm{store}}, →cont\xrightarrow{\mathrm{cont}}, and →event\xrightarrow{\mathrm{event}} rules match assignments.

Figure 10. Extending ImpThreat syntax with downgrading

We formalize the requirement of it being sufficient to reason about adversaries constrained only to interact with endorse and declassify statements using the real–ideal paradigm. We define the set of ideal, downgrade-restricted adversaries.

Definition 6.1 (Downgrade-restricted adversary). For a program pp, an adversary is downgrade-restricted when its influence is only restricted to downgrading points in pp. Precisely, the adversary may only corrupt (without mauling) the source variable of a currently running endorse statement, and can only read the destination variable of a currently running declassify statement. In fact, our restriction is stronger: the adversary does not have influence over all downgrades. In particular, harmless, noninterfering downgrades do not allow any adversarial interaction. We denote this set of adversaries by Atkdgrst\mathrm{Atk}_{\mathrm{dgrst}}.

Strengthening definition 6.1 by disallowing harmless noninterfering downgrade interactions is useful when giving heterogeneous security guarantees, as downgrades may be noninterfering for some attackers.

Definition 6.2 (Downgrade-restricted real–ideal emulation). Program pp satisfies downgrade-restricted real–ideal emulation if every attack ArA_r is equivalent to a downgrade-restricted attack AiA_i:

∀Ar∈Atkreal. ∃Ai∈Atkdgrst. ⟦p∣Ar⟧≈⟦p∣Ai⟧\forall A_r \in\mathrm{Atk}_{\mathrm{real}}.\ \exists A_i \in\mathrm{Atk}_{\mathrm{dgrst}}.\ \llbracket p \mid A_r \rrbracket\approx\llbracket p \mid A_i \rrbracket

Implications

Definition 6.2 is a good abstraction to reason against, and pays off immediately. By restricting system behavior to an abstract realm with weakened adversaries, we only have to reason about these abstract adversaries. Emulation ensures that we are still sound for powerful real-world adversaries.

As an example, we show how programs that satisfy definition 6.2 can enforce the security properties defined in § 5.2, namely nonmalleable information flow (NMIF), robust declassification (RD), transparent endorsement (TE), and noninterference (NI).

Enforcing NMIF. NMIF (definition 5.5) requires that a real-world adversary ArA_r is no more powerful than an AiA_i that is not able to maul. Definition 6.2 constrains AiA_i further! Corruption is only allowed at endorse statements, and the new values of endorsed variables are explicitly supplied by the ideal adversary, so every AiA_i in Atkdgrst\mathrm{Atk}_{\mathrm{dgrst}} is also in Atknmif\mathrm{Atk}_{\mathrm{nmif}}.

Enforcing RD. RD (definition 5.7) requires that a real-world adversary ArA_r is no more powerful than a passive AiA_i. Definition 6.2 constrains an AiA_i’s corruption behavior to only (non-noninterfering) endorse statements, so a program pp that satisfies definition 6.2 and has no such endorse statements satisfies RD.

Enforcing TE. TE (definition 5.6) requires that a real-world adversary ArA_r is no more powerful than an AiA_i that is incurious and cannot maul. Definition 6.2 constrains all AiA_i’s corruptions to be nonmauling, and the only channels via which AiA_i can learn are (non-noninterfering) declassify statements. So, a program pp that satisfies definition 6.2 and has no such declassify statements satisfies TE.

Enforcing NI. NI (definition 5.8) requires that a real-world adversary ArA_r is no more powerful than an AiA_i that is incurious and passive. Definition 6.2 constrains all AiA_i’s interactions to (non-noninterfering) downgrade statements. So, a program pp that satisfies definition 6.2 and has no such downgrading statements satisfies NI.

Enforcement

Section 7 and section 8 illustrate how one can statically enforce that a program satisfies definition 6.2 using NMIFC, an information flow type system for ImpThreat. As ImpThreat has while loops whose termination behavior cannot be determined statically, our notion of trace equivalence is weak (definition 3.3). We thus show: ∀Ar∈Atkreal. ∃Ai∈Atkdgrst. Jp∣ArK≈wJp∣AiK\forall A_r \in\mathrm{Atk}_{\mathrm{real}}.\ \exists A_i \in\mathrm{Atk}_{\mathrm{dgrst}}.\ Jp \mid A_rK \approx_w Jp \mid A_iK.

Section 7 presents a simplified treatment that is sufficient to capture all key ideas. Section 8 presents the full type system that enforces heterogeneous security.

Simplified NMIFC

Before presenting our full NMIFC type system (Figure 18), we elucidate core ideas with a simplified version of NMIFC (Figure 11). The simplification is that we fix an adversarial power (definition 5.1) Φ\Phi, which partitions the set of variables into one of four classes: {PT,PU,ST,SU}\{\mathrm{PT}, \mathrm{PU}, \mathrm{ST}, \mathrm{SU}\}, which stand for public–trusted, public–untrusted, secret–trusted, and secret–untrusted, respectively. As explained in definition 5.1, a public variable is readable by the adversary, while an untrusted variable can be corrupted by mauling.

NMIFC typing rules for adversarial power

Figure 11. NMIFC typing rules for adversarial power \thorn

Figure 18. Heterogeneous NMIFC typing rules

Following standard information flow literature, these four classes enjoy a partial order structure [11, 12, 29], with a binary flows to (⊑\sqsubseteq) relation. Trusted variables can flow to untrusted variables, and public variables can flow to secret variables. We can thus define ⊑\sqsubseteq for these four classes pointwise. In fact, this partial order is a lattice, which means that we can define the binary operators meet (⊓\sqcap) and join (⊔\sqcup).

Figure 11 is a fairly standard four-point static information flow type system. It defines two mutually inductively defined typing judgments pc \vdash_{\thorn} c and pc \vdash_{\thorn} p, which can be read as saying, “the program pp / command cc is well typed in context pcpc.” Here pcpc represents how the current control-flow was influenced. For instance, the two program branches of an if command with a secret guard are type-checked (rule ST-If) with a secret pcpc (either ST or SU). Initially, the program pp is public and trusted, and we define \vdash_{\thorn} p to be PT \vdash_{\thorn} p.

Rule ST-Declassify and rule ST-Endorse are the main rules constraining downgrading statements. They are the only rules where noninterference may be broken, and the only program locations where the soundness statement (definition 6.2) allows ideal-adversary influence. Harmless noninterfering downgrades are also allowed by our type system (rule ST-Assign). They are glorified assignment statements; our soundness statement does not give the ideal adversary access to them.

While this is a simpler type system, and only states static requirements for a particular adversarial power \thorn, it captures all required key ideas. In fact, our soundness proof for the full type system (Figure 18) boils down to proving that projecting the full type system down to a four-point case is still well-typed for all reasonable adversarial powers.

Real–ideal soundness

The soundness theorem for our type system is a real–ideal statement that constrains ideal adversaries to only downgrading interactions (definition 6.2).

Theorem 7.1 (Real–ideal soundness for simple NMIFC). A well-typed program pp satisfies definition 6.2.

\vdash_{\thorn} p \mathrel{\Longrightarrow} \forall A_r \in\mathrm{Atk}_{\mathrm{real}}.\ \exists A_i \in\mathrm{Atk}_{\mathrm{dgrst}}.\ \llbracket p \mid A_r \rrbracket\mathrel{\approx_w} \llbracket p \mid A_i \rrbracket

Intuitive argument. Suppose we have a pp such that \vdash_{\thorn} p. The type system (Figure 11) ensures noninterference for most commands, which enforces strict constraints on the integrity of trusted variables and the privacy of secret variables. In this case, anything that the real attacker ArA_r can leak by reading public variables at any point in the program can by simulated and leaked by an AiA_i, by just computing from σinp\sigma_{\mathrm{inp}}’s initial public input. Additionally, as only trusted events appear on the traces, AiA_i’s lack of corruption power does not hurt us, and we can ensure that ⟦p∣Ar⟧≈w⟦p∣Ai⟧\llbracket p \mid A_r \rrbracket\approx_w \llbracket p \mid A_i \rrbracket.

Challenges. The intuitive argument sweeps several tricky details under the rug. Unlike traditional program refinement proofs, which often just involve some sort of bisimulation between two programs, this proof is more akin to a compiler correctness proof. We compile the real attack ArA_r and program pp to explicitly construct the simulator, which we denote using AsimA_{\mathrm{sim}}. Although AsimA_{\mathrm{sim}} has to “just simulate” ArA_r’s leakage behavior, this requires that it can independently compute the values of variables that ArA_r leaks, which in turn requires that it keep in its memory a version of the system continuation that will run, because it needs this memory for mental computations it performs.

After the AsimA_{\mathrm{sim}} construction, showing the equivalence ≈w\approx_w requires the construction of another bisimulation relation relating the real and ideal worlds. This is nontrivial, for we are dealing with four concurrently executing processes: the real program, the real attacker, the ideal program, and the ideal attacker. We need to show that this bisimulation relation is preserved as the two systems execute. We also need to show that Asim∈AtkdgrstA_{\mathrm{sim}} \in\mathrm{Atk}_{\mathrm{dgrst}}, while also ensuring that AsimA_{\mathrm{sim}} is fair (definition 3.4).

Proof strategy. Our proof thus requires the following components:

  1. The simulator construction (§ 7.2).

  2. Proving behavioral equivalence using bisimulation (sections 7.3 to § 7.6).

  3. Demonstrating that the simulator is in Atkdgrst\mathrm{Atk}_{\mathrm{dgrst}} (§ 7.7).

  4. Showing fairness for our simulator construction (§ 7.8).

The simulator construction

Theorem 7.1 is a ∀p. ∀Ar. ∃Ai.…\forall p.\ \forall A_r.\ \exists A_i.\ldots statement, which requires that we construct the simulator AsimA_{\mathrm{sim}} from pp and ArA_r.

Recall that an adversary is defined (Figure 3) as a triple: ⟨Stateadv, advinit, advnext⟩\langle\mathrm{State}_{\mathrm{adv}},\ \mathrm{adv}_{\mathrm{init}},\ \mathrm{adv}_{\mathrm{next}}\rangle. We now describe how these three components are constructed for our simulator.

The state space. Figure 12 shows the state space of the simulator AsimA_{\mathrm{sim}}. AsimA_{\mathrm{sim}}’s state wraps the state space of the real adversary ArA_r with two extra components σsim\sigma_{\mathrm{sim}} and πsim\pi_{\mathrm{sim}}.

Simulator data for a real adversary

Figure 12. Simulator data for a real adversary with state space Stateadv\mathrm{State}_{\mathrm{adv}}

σsim\sigma_{\mathrm{sim}} is the simulator’s version of the program store. While ArA_r is able to learn from the program store’s public view (Figure 3) using its cmdpost\mathrm{cmd}_{\mathrm{post}} function, the simulator is subject to the ideal attacker restriction (definition 6.1), and cannot learn from the program store (except during declassify statements). Thus, AsimA_{\mathrm{sim}} maintains σsim\sigma_{\mathrm{sim}} as a simulator-only store copy as part of its state, which it reads as it tries to emulate the real adversary. As we show in § 7.4, AsimA_{\mathrm{sim}} ensures that σsim\sigma_{\mathrm{sim}}’s public view matches with the real program store’s public view at all times.

AsimA_{\mathrm{sim}} also maintains πsim\pi_{\mathrm{sim}}, which can be thought of as its own copy of the currently executing system continuation kk (Figure 4). Like kk, πsim\pi_{\mathrm{sim}} elements also contain an optional command along with a bit describing whether the real adversary runs at that point. However, in general, k≠πsimk \ne\pi_{\mathrm{sim}}. πsim\pi_{\mathrm{sim}} only contains entries when AsimA_{\mathrm{sim}} is active. Even when active,

πsim\pi_{sim}’s entries may be ϵ\epsilon if not required by AsimA_{sim}. The attacker bit ⋆\star marks if the real adversary ArA_r is active at that point, which is required for both computation of σsim\sigma_{sim} as well as adversarial information leaking.

Finally, the simulator maintains a copy of the real attacker ArA_r’s state astast, for a blackbox simulation [43] strategy. The goal here is to ensure that the simulator’s astast matches with the real system astast at all times by feeding it σsim\sigma_{sim}. Maintaining astast thus lets AsimA_{sim} leak information exactly how the real attacker ArA_r would have.

The initial state construction advinitadv_{init}. The astast component of the initial state triple ⟨ast,σsim,πsim⟩\langle ast,\sigma_{sim},\pi_{sim}\rangle is constructed exactly how ArA_r would have. σsim\sigma_{sim} is constructed by copying all the initial store’s public variables, which AsimA_{sim} is required to do in order to simulate the rest of ArA_r’s interactions. Finally, AsimA_{sim} constructs πsim\pi_{sim} from pp, with all commands marked with ⋆\star, since ArA_r is active in all commands of the initial configuration (§ 5.1).

The next-step computation advnextadv_{next}. Figure 13 depicts the key components of how AsimA_{sim} performs its next-step computations. AsimA_{sim} uses πsim\pi_{sim} as its internal model of what the true system continuation kk is doing, and performs the computations required for simulation as required by the commands cc in πsim\pi_{sim}.

Simulator algorithm

Figure 13. Simulator algorithm

For a non-downgrade cc, non_downgrade_step describes AsimA_{sim}’s behavior. More precisely, AsimA_{sim} simulates the command–attacker sandwiched semantics (Figure 6) to compute the new value of its σsim\sigma_{sim}. Similarly, AsimA_{sim} computes πsim\pi_{sim} by simulating how ArA_r’s requested substeps (Figure 7) are zipped. We want AsimA_{sim} to run whenever ArA_r does. Zipping is done with a pp that cc would have stepped using →cont\xrightarrow{\mathrm{cont}} to, except for when cc has a secret guard; if cc is an if / while with a boolean test t(x)t(x) and xx is secret, AsimA_{sim} does not simulate pp’s branch (which is impossible in general).

When cc is a non-noninfering downgrade however, AsimA_{sim} gets to exert more influence on σidl\sigma_{idl}, the ideal program store. But this influence is very controlled: explicit corruptions of endorse sources, and reading of only declassify destinations. corrupt_endorse shows how AsimA_{sim} does corruption by returning transformation for σidl\sigma_{idl} that only updates the endorse source. Similarly, learn_declassify depicts how AsimA_{sim} learns σidl\sigma_{idl}’s declassify destinations.

PCpc∈{PT,PU,ST,SU}Cmdcmbcmdcmb::=⟨cr,ci,pc⟩∣⟨cr,ci?,pc⟩⋆Contcmbkcmb::=ϵ∣cmdcmb::kcmbStatecmbstcmb::=⟨σr,σi,σs,ast⟩Cfgcmbκcmb::=⟨stcmb,kcmb⟩\begin{aligned} \mathrm{PC}\quad p_c &\in\{\mathrm{PT},\mathrm{PU},\mathrm{ST},\mathrm{SU}\}\\ \mathrm{Cmd}_{\mathrm{cmb}}\quad cmd_{\mathrm{cmb}} &::= \langle c_r,c_i,p_c\rangle\mid\langle c_r,c_i^{?},p_c\rangle^{\star}\\ \mathrm{Cont}_{\mathrm{cmb}}\quad k_{\mathrm{cmb}} &::= \epsilon\mid cmd_{\mathrm{cmb}} :: k_{\mathrm{cmb}}\\ \mathrm{State}_{\mathrm{cmb}}\quad st_{\mathrm{cmb}} &::= \langle\sigma_r,\sigma_i,\sigma_s,ast\rangle\\ \mathrm{Cfg}_{\mathrm{cmb}}\quad\kappa_{\mathrm{cmb}} &::= \langle st_{\mathrm{cmb}},k_{\mathrm{cmb}}\rangle \end{aligned}

It is important to note that Figure 13 is specialized to when the real attacker ArA_r runs (that is, ⋆\star is present). If ⋆\star is absent, AsimA_{sim} adjusts correspondingly. For example, cmdprecmd_{pre} and cmdpostcmd_{post} steps are not performed by it, and nothing is leaked. Moreover, while AsimA_{sim} ‘runs’ πsim\pi_{sim}, kk is the ground truth, and we need to make sure that they match appropriately. We show this in § 7.4 and § 7.5.

Behavioral equivalence (≈w\approx_w)

We now need to show ⟦p∣Ar⟧≈w⟦p∣Asim⟧\llbracket p \mid A_r \rrbracket\approx_w \llbracket p \mid A_{sim} \rrbracket. Proving this requires weak bisimulation. Let us denote the set of real and ideal configurations (Figure 4) using Cfgreal\mathrm{Cfg}_{real} and Cfgideal\mathrm{Cfg}_{ideal} respectively. Showing weak bisimulation means constructing a bisimulation relation R⊆Cfgreal×CfgidealR \subseteq\mathrm{Cfg}_{real} \times\mathrm{Cfg}_{ideal}, and showing that RR agrees with both the initial configurations of Cfgreal\mathrm{Cfg}_{real} and Cfgideal\mathrm{Cfg}_{ideal}, as well as how they step, which we denote using steprealstep_{real} and stepidealstep_{ideal}. For the former, we simply have to show that the initial configurations are related by RR.

For the latter we show that, if κreal\kappa_{real} and κideal\kappa_{ideal} are related, denoted (κreal) R (κideal)(\kappa_{real})\ R\ (\kappa_{ideal}), then only one of three things can happen:

  1. (stepreal κreal) R (stepideal κideal)(step_{real}\ \kappa_{real})\ R\ (step_{ideal}\ \kappa_{ideal})

  2. (stepreal κreal) R (κideal)(step_{real}\ \kappa_{real})\ R\ (\kappa_{ideal})

  3. (κreal) R (stepideal κideal)(\kappa_{real})\ R\ (step_{ideal}\ \kappa_{ideal})

That is, while one configuration steps, the other may stutter. Additionally, we must also ensure that the generated events (§ 5.1) match when both configurations step, and that a stutter step on one side is matched by an ϵ\epsilon event on the other.

Cfgreal×Cfgideal\mathrm{Cfg}_{real} \times\mathrm{Cfg}_{ideal} is a complex object, and consists of the real program, the real adversary, the ideal program, and the ideal adversary executing concurrently. In order to tame this complexity, we construct a combined configuration from which all necessary components are extracted. In essence, we reduce the binary problem of bisimulation into a unary problem of invariant preservation.

Combined configurations

An elegant way to construct the bisimulation relation RR between Cfgreal\mathrm{Cfg}_{real} and Cfgideal\mathrm{Cfg}_{ideal} is to think of κreal\kappa_{real} and κideal\kappa_{ideal} as being extracted from a single combined object κcmb\kappa_{cmb}. In our case, this pays off because, although κreal\kappa_{real} and κideal\kappa_{ideal} could be fairly different in general, they share many similarities for all reachable configurations. This is for two main reasons. First, both κreal\kappa_{real} and κideal\kappa_{ideal} are constructed from the same program pp. Additionally, AsimA_{sim} itself is functionally derived from pp and ArA_r, and shares a lot of state with them. The structure of a combined configuration κcmb\kappa_{cmb} is shown in Figure 14. On a high level, it is similar to a single configuration (Figure 4), and contains a combined state stcmbst_{cmb} and a *combined command list kcmbk_{cmb}. A combined state stcmbst_{cmb} is a 4-tuple containing the real system store (σr\sigma_r), the ideal system store (σi\sigma_i), the simulator private store (σs\sigma_s), and the real adversary state (astast).

Combined configuration

Figure 14. Combined configuration

On the other hand, kcmbk_{cmb} is a list of combined commands cmdcmbcmd_{cmb}. A combined command may be marked with a ∗\ast, which shows that it is attacked. This single bit suffices to derive both whether ArA_r is active as well as AsimA_{sim} is active. Additionally, a cmdcmbcmd_{cmb} also contains the currently running real (crrc_r^r) and ideal (circ_i^r) commands. The final piece is pcpc, a ghost variable [6, 52], which we use to require that crrc_r^r and circ_i^r are well-typed (fig. 11).

Combined configuration extraction. A combined configuration kcmbk_{cmb} gets extracted into the real configuration (krealk_{real}) and the ideal configuration (kidealk_{ideal}), as shown in Figure 15. We first use extractpairextract_{pair} to obtain a configuration pair ∈Cfgpair\in\mathrm{Cfg}_{pair}, which then gets split into the real and ideal configurations using extractrealextract_{real} and extractidealextract_{ideal}. A configuration in Cfgpair\mathrm{Cfg}_{pair} is a pair of krealk_{real} and kidealk_{ideal}, except that their krealk_{real} and kidealk_{ideal} are padded to have the same length. Cfgpair\mathrm{Cfg}_{pair} is constructed so that we don’t have to deal with the weakness of bisimulation until the very end of our proof.

Figure 15. Configuration extraction

The extraction is straightforward except for the construction of AsimA_{sim}. To extract AsimA_{sim}, we need to answer two questions: when does AsimA_{sim} get to run, and what is its state?

Simulator AsimA_{sim} runs whenever the real attack ArA_r runs (encoded by marking cmdcmbcmd_{cmb} with ∗\ast), in order to simulate its corruption and leakage behaviors. Additionally, it also runs whenever there is a real command crc_r with a public pcpc running. This is required as crc_r can update public variables, and AsimA_{sim} must update its personal σsim\sigma_{sim} to match them appropriately.

To explain AsimA_{sim}’s state extraction, it suffices to only explain the construction of its πsim\pi_{sim}, as the other components are straightforward. πsim\pi_{sim} is AsimA_{sim}’s mental model of the real system continuation krealk_{real}, and is very similar to it. The main difference is that every real command crc_r with a secret pcpc is erased during extraction; AsimA_{sim} does not need to know it and cannot know it in general.

Cfgcmb_{cmb} invariant. Not all configurations in Cfgcmb\mathrm{Cfg}_{cmb} are relevant. We describe the subset of relevance using a predicate, which is then shown to be an invariant.

Definition 7.2 (Cfgcmb_{cmb} invariant). Our invariant, InvcombInv_{comb}, requires the following to hold:

  • State invariant: The public view (σ∣public\sigma|_{public}) of σr\sigma_r and σs\sigma_s agree, and the trusted view (σ∣trusted\sigma|_{trusted}) of σr\sigma_r and σi\sigma_i agree, where a view of a store restricts its domain in the obvious way. That is, (σr∣trusted=σi∣trusted)∧(σr∣public=σs∣public)(\sigma_r|_{trusted} = \sigma_i|_{trusted}) \land(\sigma_r|_{public} = \sigma_s|_{public}).

  • Command invariant: For every crrc_r^r in kcmbk_{cmb}, pc⊢crrpc \vdash c_r^r. As for circ_i^r, if pcpc is trusted, crr=circ_r^r = c_i^r. For an untrusted pcpc, circ_i^r must still be well-typed in a public context. That is, PU⊢Φcir\mathrm{PU} \vdash_{\Phi} c_i^r.

Maintaining this invariant (definition 7.2) is the heart of the ≈w\approx_w proof. (σr∣trusted=σi∣trusted)(\sigma_r|_{trusted} = \sigma_i|_{trusted}) is necessary for system I/O equivalence, while (σr∣public=σs∣public)(\sigma_r|_{public} = \sigma_s|_{public}) ensures equivalence of adversary leakage. Additionally, requiring that crr=circ_r^r = c_i^r in every trusted pcpc ensures the right order of events.

The stepcomb\mathit{step}_{comb} function. A configuration κcmb\kappa_{cmb} in Cfgcmb\mathrm{Cfg}_{cmb} steps using stepcomb\mathit{step}_{comb}. Like regular configuration stepping (Figure 5 to Figure 7), the head command cmdcmb\mathit{cmd}_{cmb} of κcmb\kappa_{cmb} is run at each step. cmdcmb\mathit{cmd}_{cmb} updates σr\sigma_r using its cr′c'_r, and updates σi\sigma_i using its ci′c'_i. Finally, updates to σs\sigma_s are done exactly how the simulator would have (Figure 13). Computing the new κcmb\kappa_{cmb} is done by zipping together (Figure 7) three things: the real continuation, the ideal continuation, and the real attacker substeps.

We now prove that definition 7.2 is really an invariant when stepping with stepcomb\mathit{step}_{comb}.

Lemma 7.3 (Stepping invariant preservation). stepcomb\mathit{step}_{comb} preserves Invcomb\mathit{Inv}_{comb}. That is,

∀κcmb. Invcomb(κcmb)⇒Invcomb(stepcomb(κcmb))\forall\kappa_{cmb}.\ \mathit{Inv}_{comb}(\kappa_{cmb}) \Rightarrow\mathit{Inv}_{comb}(\mathit{step}_{comb}(\kappa_{cmb}))

While finding the right invariant was a challenge, the proof of the above lemma is fairly straightforward. From this point on, we only consider configurations κcmb\kappa_{cmb} that satisfy Invcomb\mathit{Inv}_{comb}. We redefine Cfgcmb≜{κcmb∈Cfgcmb∣Invcomb(κcmb)}\mathrm{Cfg}_{cmb} \triangleq\{\kappa_{cmb} \in\mathrm{Cfg}_{cmb} \mid\mathit{Inv}_{comb}(\kappa_{cmb})\}.

Extraction commutativity

Cfgcmb\mathrm{Cfg}_{cmb} and stepcomb\mathit{step}_{comb} are very different from Cfgreal\mathrm{Cfg}_{real}, Cfgideal\mathrm{Cfg}_{ideal}, stepreal\mathit{step}_{real}, and stepideal\mathit{step}_{ideal}. To show that they are still faithful, we prove the commutativity of Figure 16 and Figure 17.

Figure 16. Extraction and step commute

Figure 17. Two-step extraction commutativity (Both 1 and 2 cannot be idid simultaneously).

Figure 16 asserts the commutativity of the step and extract functions that involve Cfgcmb\mathrm{Cfg}_{cmb} and Cfgpair\mathrm{Cfg}_{pair}. steppair\mathit{step}_{pair} describes how configuration pairs in Cfgpair\mathrm{Cfg}_{pair} step. It ensures that the continuations of κreal\kappa_{real} and κideal\kappa_{ideal} have the same lengths by zipping them together.

Lemma 7.4 (Strong extract–step commutativity). Figure 16 commutes.

We deal with the weakness of bisimulation in Figure 17, which asserts that whenever a κpair\kappa_{pair} steps, either both of its extracted κreal\kappa_{real} and κideal\kappa_{ideal} step, or one stutters while the other steps.

Lemma 7.5. One of the three possibilities of Figure 17 commutes.

These possibilities match up exactly with the possibilities mentioned in section 7.3.

The bisimulation relation

We now have all the required machinery to construct the bisimulation relation RR:

κrealRκideal⟺∃κcmb.{κreal=extract⁡real(extract⁡pair(κcmb))κideal=extract⁡ideal(extract⁡pair(κcmb))\kappa_{real} R \kappa_{ideal} \Longleftrightarrow\exists\kappa_{cmb}.\begin{cases} \kappa_{real} = \operatorname{extract}_{real}(\operatorname{extract}_{pair}(\kappa_{cmb}))\\ \kappa_{ideal} = \operatorname{extract}_{ideal}(\operatorname{extract}_{pair}(\kappa_{cmb})) \end{cases}

Every κcmb\kappa_{cmb} step gives a new existential witness κcmb′=step⁡comb(κcmb)\kappa'_{cmb} = \operatorname{step}_{comb}(\kappa_{cmb}). By lemmas 7.4 and 7.5, we can show that exactly one of the three weak bisimulation possibilities (section 7.3) holds. Moreover, although we have not explicitly defined Cfgcmb\mathrm{Cfg}_{cmb}’s event behavior, it is not very surprising, and does not cause much complication. Similarly, showing that the initial configurations are related by RR is straightforward. This concludes our proof sketch for ≈w\approx_w.

The simulator is downgrade-restricted

We need to prove that AsimA_{sim}’s influence is restricted to only program downgrading points (definition 6.1). The simulator algorithm (Figure 13) is very constrained, and only interacts with pp during functions corrupt_endorse and learn_declassify at downgrading points. However, the subtlety is ensuring that AsimA_{sim}’s beliefs about downgrading (in πsim\pi_{sim}) match with reality (κideal\kappa_{ideal}).

This requires an invariant. While we could construct a new invariant, our proof reuses the existing machinery from section 7.3. We use κcmb\kappa_{cmb} to construct the following invariant:

∃κcmb. κideal=extract⁡ideal(extract⁡pair(κcmb))\exists\kappa_{cmb}.\ \kappa_{ideal} = \operatorname{extract}_{ideal}(\operatorname{extract}_{pair}(\kappa_{cmb}))

Unfortunately, we cannot use the step⁡comb\operatorname{step}_{comb} function to make κcmb\kappa_{cmb} step in this case. This is because it does not necessarily make κideal\kappa_{ideal} step; it could cause κreal\kappa_{real} to step instead. Instead, we use step⁡comb∘filter⁡ideal\operatorname{step}_{comb} \circ\operatorname{filter}_{ideal}, where filter⁡ideal\operatorname{filter}_{ideal} filters out all cmdcmb\mathrm{cmd}_{cmb} with a non-running circ_i^r from κcmb\kappa_{cmb}.

Lemma 7.6 (Simulator downgrade-restriction). AsimA_{sim} only interacts with pp *at downgrade points. That is, Asim∈AtkdgrstA_{sim} \in\mathrm{Atk}_{dgrst}.

Simulator fairness

Fairness (definition 3.4) requires that AsimA_{sim} takes no unnecessary steps. This is ensured by our combined configuration extraction function extract⁡pair\operatorname{extract}_{pair}. AsimA_{sim} is active only in two cases: when ArA_r is active, or when circ_i^r is present with a public pcpc. This thus implies no reachable configuration where AsimA_{sim} is active but no other component is running.

Lemma 7.7 (Simulator fairness). AsimA_{sim} is fair (definition 3.4) for (real) pp, (ideal) pp, and ArA_r.

Heterogeneous NMIFC

Figure 11 describes the static obligations a program must satisfy to enjoy our real–ideal emulation (definition 6.2), but only against a particular adversary Φ\mathbf{\Phi}. In decentralized systems, however, defending against such single adversarial power does not suffice; a secure system must provide satisfactory guarantees across all reasonable adversarial scenarios.

In order to achieve this, we first need a way to describe different adversarial scenarios. Following standard practice, we do this using security labels drawn from a lattice of principals PP [7, 49]. Principals in PP are ordered by the authority relation ⪯\preceq. When p1⪰p2p_1 \succeq p_2, we say that p1p_1 acts for p2p_2. This intuitively means that p1p_1 can do everything that p2p_2 can. Finally, we assume that PP is bounded: ⊤\top is the principal with the most authority and ⊥\bot is the principal with the least authority.

Data elements—variables in our case—are annotated with labels. A label ℓ\ell is a pair of principals denoting minimal read and write requirements for data. For a label ℓ\ell, we write ℓ←\ell^{\leftarrow} for its write requirements, and ℓ→\ell^{\rightarrow} for its read requirements. Read and write permissions in UNIX are a good real-world example of what such labels can encode. We write ℓx\ell_x for the label of a variable xx.

In this setup, an adversarial power is also a label ☠. ☠ partitions variables into the four classes {PT, PU, ST, SU} in the obvious way. If ☠ has the authority to read a variable, it is public, and if it has the authority to write a variable, it is untrusted. Additionally, we assume ☠ to be reasonable.

Definition 8.1 (Reasonable adversarial power). An adversarial power ☠ is reasonable when ☠→⪰^{\rightarrow} \succeq ☠←^{\leftarrow}: the adversary’s read power is at least as strong as its write power; further, it cannot control ⊤\top.

Intuitively, a reasonable adversary can only corrupt what it can also observe. This assumption is standard [3, 21, 55, 61], and suffices to encode the well-known malicious and honest-but-curious models from cryptography. The absurd adversary that cannot read its own data is excluded.

In Figure 18, we show our full NMIFC type system for a given principal lattice PP and a labeling of variables ℓ□\ell_{\square}. Like the simplified system (Figure 11), it defines pc⊢cpc \vdash c and pc⊢ppc \vdash p mutually inductively, and has very similar rules when there is no downgrading.

Its downgrading rules (rules T-Endorse and T-Declassify) generalize their simplified counterparts: rather than fixing destinations to be PT in a PT context, their labels have to be uncompromised.

Definition 8.2 (Uncompromised label). A label ℓ\ell is uncompromised, denoted ▼ℓ\blacktriangledown\ell, when ℓ←⪰ℓ→\ell^{\leftarrow} \succeq\ell^{\rightarrow}: the integrity component is at least as strong as the confidentiality component [61].

▼ℓ≜ℓ←⪰ℓ→\blacktriangledown\ell\mathrel{\triangleq} \ell^{\leftarrow} \succeq\ell^{\rightarrow}

A principal that can write to a ▼ℓ\blacktriangledown\ell variable can also read it, and these variables cannot have mauled data. We now prove that a well-typed NMIFC program projects on to a well-typed four point case. We write ⊢p\vdash p to mean pc⊢ppc \vdash p, where pc←=⊤pc^{\leftarrow} = \top, and pc→=⊥pc^{\rightarrow} = \bot. That is, it is well-typed in the most public and trusted context.

Lemma 8.3 (NMIFC projection). For all reasonable attackers, a well-typed program pp remains well-typed in the four-point case.

\forall\thorn.\ \vdash_{\thorn} p \Longrightarrow\vdash_{\thorn} p

Here, \thorn ranges over the collection of reasonable adversarial powers.

The key idea in this proof is to recognize that almost every single typing rule in Figure 18 maps exactly to its corresponding four-point rule in Figure 11. A minor exception is the pair of rules T-Endorse and T-Declassify. In addition to mapping onto rules ST-Endorse and ST-Declassify, they might be noninterfering and thus also map onto rule ST-Assign. We can now prove our final heterogeneous real–ideal soundness theorem.

Theorem 8.4 (NMIFC heterogeneous real–ideal soundness). A well-typed program pp satisfies definition 6.2 for all reasonable adversarial powers \thorn.

\vdash p \Longrightarrow\forall A_r \in\thorn\text{-}\mathrm{Atk}_{\mathrm{real}}.\ \exists A_i \in\thorn\text{-}\mathrm{Atk}_{\mathrm{dgrst}}.\ \llbracket p \mid A_r \rrbracket\approx_w \llbracket p \mid A_i \rrbracket

Connection to Viaduct

This NMIFC type system is a generalization of the information flow type system used in Viaduct [3, 4], which only permitted public and trusted control flow. Viaduct’s correctness statement is a real–ideal emulation connecting its sequential source language to a distributed, concurrent, cryptographic target language. This work sheds light on the precise role that NMIFC plays in Viaduct. Their source language only allows adversarial access to downgrading, which is exactly definition 6.1. It is because of theorem 8.4 that NMIFC implies that Viaduct is able to connect this source threat model to a more powerful real-world adversary.

Proof mechanization

We formalize and prove all our theorems using the Rocq [60] proof assistant. As described in section 7.3, proving soundness for NMIFC needed a fairly involved bisimulation proof, and we believe that this proof is the first formally verified real–ideal emulation result for a core programming language calculus with realistic security concerns that interleave confidentiality and integrity. Our total development sums up to ~5K lines of code. The proofs have no admits, and only use the axiom for function extensionality. The longest proofs are for lemmas 7.3, 7.4 and 7.6, which required machinery for handling our zipping semantics. We believe that these techniques will be useful and straightforward to build upon in the future. The Claude AI aided in proving a few minor lemmas and writing tactics, but all lemma and theorem statements were written by hand.

All proofs are available at https://github.com/kssuraaj28/demystify-ifc-rocq.

Discussion

We discuss some apparent and real limitations of our approach.

Probability. The real–ideal paradigm’s original formulation is in terms of probabilistic interactive Turing machines, so dealing with only deterministic adversaries in IMPThreat might seem like a limitation. It is not. It is known that defending against deterministic adversaries suffices for deterministic programs [25]: a probabilistic adversary is a randomized mixture of deterministic adversaries, and we consider all deterministic adversaries. This insight is similar to the well-known dummy-adversary theorem [16] in cryptography.

Manuscript submitted to ACM

Termination sensitivity. The type system only ensures equivalence while being insensitive to termination. While termination insensitivity is standard in the literature, it is not what we want for compositional security, because the resulting notion of equivalence is not transitive. The standard fix is to assume that all (well-typed) programs terminate, which might be relaxed to only disallow nontermination with untrusted control flow, but we leave this for future work. Additionally, to require termination sensitivity subsumes our fair ideal attacker (definition 3.4) requirement.

Alternative label models. Our label model (§ 8) is deliberately simple. Richer label models incorporate logical formulas, computational specifications, and delegation (e.g., [13, 23, 24, 42]). Regardless, lemma 8.3 is a good soundness theorem for other label models; any model satisfying that lemma enjoys our real–ideal result.

Related work

The real–ideal paradigm arose as an alternative to traditional cryptographic game-based security definitions [57]. Goldwasser and Micali [36] introduced it to give a semantic security definition for encryption. Canetti [15] introduced its standalone model, and Canetti [16] introduced its universally composable variant. Since then, several other variants have been defined [10, 17, 19, 37, 39, 45, 46] to target simplicity [19, 39, 46] and expressiveness [17, 37]. Maurer et al. [45, 46] advocate against low-level Turing-machine–style frameworks in favor of a more abstract presentation of the theory.

Beyond cryptography, several existing security specifications have been given (mostly implicit) real–ideal style definitions. Athalye et al. [9] presents a information-preserving refinement as the security specification for secure hardware security modules (HSMs), a formal verification framework for enforcement, along with a few case studies. Their work is limited to that domain, with mechanized proofs hand-written for each system. Canetti et al. [18] give the security specification for a file system in a real–ideal style. Their main concern is defending against pathname manipulation attacks [22]. Their description is informal, and they do not consider confidentiality requirements, essentially doing trace refinement. Dongol et al. [31] describe relative security, a formally verified framework for security specification and enforcement of Spectre-like attacks [38]. Their framework is specialized to adversarial knowledge in the presence of speculative execution, and does not deal with more general security concerns. Stoughton et al. [59] also argue for real–ideal style security specifications with a case study that presents an informal real–ideal specification for the game Battleship and their implementation experience using various enforcement mechanisms. Their correctness argument is informal.

Our work builds on top of a rich history of language-based security research. The original formulation of robust declassification [63] gives it an elegant semantic definition quite similar to ours. While we require that an active attack is equivalent to some passive attack, the original definition gives an explicit construction of a passive attack. Unfortunately this approach does not seem to generalize as one introduces transparent endorsement and nonmalleable information flow [21], where this definition becomes intensional and must exclude “inept” attacks, attacks too weak to be relevant, from consideration. Soloviev et al. [58] give a framework based on epistemic logic for defining robust declassification and transparent endorsement. Their treatment is fairly complex and not mechanized, and it is unclear whether it generalizes to nonmalleable information flow. We believe that the real–ideal paradigm is the better characterization of security, even when the security properties involve “knowledge,” much like the state-of-the-art security specifications for zero-knowledge proofs (ZKPs) [43]. Cecchetti [20] introduces nonmalleable progress leakage, a generalization of NMIF to include progress sensitivity. Unfortunately, their definition is also intensional, requiring endorse events. Acay et al. [4] served as a major inspiration for this paper. They present Viaduct, a compiler for secure distributed cryptographic implementations, where the security requirement is given as a real–ideal specification. Their paper uses many techniques: an information-flow control type system, choreographic projections [47], UC-emulation, etc. We believe that our real–ideal soundness guarantees for a related type system better explains why their proof works. Moreover, the language they consider is much more limited. Pottier and Simonet [54] present information flow analysis for an ML language. Our proof technique that reduces bisimulation to invariant preservation is similar to theirs.

Robust hyperproperty preservation (RHP) [2] advocates for secure compilers to preserve hyperproperties between the source and target programs in all contexts. Patrignani et al. [53] recognizes the equivalence between RHP and the real–ideal paradigm (UC in particular). New et al. [51] present a RHP compiler for a source language without exceptions to a target language with exceptions. Their proof is not mechanically verified. Importantly, all existing RHP work focuses on ensuring system integrity and does not formalize more complex scenarios where threats may learn secrets, or heterogeneous security scenarios with mutually untrusting principals.

Conclusion

This work presents the real–ideal paradigm as a simple, widely applicable, and useful framework for specifying and reasoning about language-based security. While we are not the first to argue for this paradigm, we believe that this work is the most general and convincing language-based demonstration of the idea, showing that it works for reasoning about both confidentiality and integrity, and their interactions, for all programs written in a language allowing both secret and untrusted control flow. We show several applications of this paradigm, from elegant reformulations of existing security properties to a novel real–ideal soundness theorem for information flow type systems. Formulating information flow type soundness in the real–ideal paradigm yields important insights about why it is useful for building distributed systems with heterogeneous security. We implement and formally verify a NMIFC type system offering such guarantees. The generality of the language and the properties being considered required development of new proof techniques, which are all fully mechanized in the Rocq prover.

AI is making it cheaper to produce high-quality—even formally verified—software. But formal verification is far more useful when we know the right specifications to verify the software against. We believe this work is an important step in this direction.

There are many future directions for extensions to this work. We do not consider probabilistic programs here, but adding probability as a first class primitive to ImpThreat would be a good step in this direction. The universal composability [16] variant of the real–ideal paradigm comes with strong compositionality theorems, enabling designers to build larger systems from simpler ones. It would be interesting to explore how to connect this notion of compositionality with existing language-based compositionality mechanisms. Our heterogeneous security definition assumes static corruption and static trust in which adversarial power and trust relationships among principals are fixed at the start of execution. It would be interesting to generalize our approach to dynamic corruption and dynamic delegation, where adversarial power and trust evolve as the system runs.

References

  1. [1]M. Abadi and L. Lamport. Composing specifications. ACM Trans. on Programming Languages and Systems, 15(1):73–132, Jan. 1993.
  2. [2]C. Abate, R. Blanco, D. Garg, C. Hritcu, M. Patrignani, and J. Thibault. Journey beyond full abstraction: Exploring robust property preservation for secure compilation. In 32nd IEEE Computer Security Foundations Symp. (CSF), pages 256–271. IEEE Computer Society, 2019.
  3. [3]C. Acay, R. Recto, J. Gancher, A. Myers, and E. Shi. Viaduct: An extensible, optimizing compiler for secure distributed programs. In 42nd ACM SIGPLAN Conf. on Programming Language Design and Implementation (PLDI), pages 740–755. ACM, June 2021.DOI
  4. [4]C. Acay, J. Gancher, R. Recto, and A. C. Myers. Secure synthesis of distributed cryptographic applications. In IEEE Computer Security Foundations Symp. (CSF), July 2024.DOI
  5. [5]B. Alpern and F. B. Schneider. Defining liveness. Information Processing Letters, 21(4):181–185, Oct. 1985.
  6. [6]T. Amtoft and A. Banerjee. Information flow analysis in logical form. In The Eleventh International Symposium on Static Analysis Proceedings, pages 100–115, 2004.DOI
  7. [7]O. Arden, J. Liu, and A. C. Myers. Flow-limited authorization. In 28th IEEE Computer Security Foundations Symp. (CSF), pages 569–583, July 2015.DOI
  8. [8]A. Askarov, S. Hunt, A. Sabelfeld, and D. Sands. Termination-insensitive noninterference leaks more than just a bit. In ESORICS, pages 333–348, Oct. 2008.
  9. [9]A. Athalye, M. F. Kashoek, and N. Zeldovich. Verifying hardware security modules with {Information-Preserving} refinement. In 16th USENIX Symposium on Operating Systems Design and Implementation (OSDI 22), pages 503–519, 2022.
  10. [10]M. Backes, B. Pfitzmann, and M. Waidner. The reactive simulatability (RSIM) framework for asynchronous systems. Information and Computation, 205(12):1685–1720, 2007.
  11. [11]D. E. Bell and L. J. LaPadula. Secure computer systems: mathematical foundations and model. Technical Report M74-244, MITRE Corp., Bedford, MA, 1973.
  12. [12]K. J. Biba. Integrity considerations for secure computer systems. Technical Report ESD-TR-76-372, USAF Electronic Systems Division, Bedford, MA, Apr. 1977. (Also available through National Technical Information Service, Springfield Va., NTIS AD-A039324.).
  13. [13]N. Broberg and D. Sands. Flow locks: Towards a core calculus for dynamic flow policies. In Programming Languages and Systems, pages 180–196. Springer, 2004.
  14. [14]N. Broberg, B. van Delft, and D. Sands. Paragon for practical programming with information-flow control. In 11th ASIAN Symposium on Programming Languages and Systems, APLAS 2013, pages 217–232. Springer, 2013.DOI
  15. [15]R. Canetti. Security and composition of multiparty cryptographic protocols. Journal of Cryptology, pages 143–202, 2000.
  16. [16]R. Canetti. Universally composable security: A new paradigm for cryptographic protocols. In 42nd Symposium on Foundations of Computer Science (FOCS), pages 136–145. IEEE Computer Society, 2001.
  17. [17]R. Canetti and T. Rabin. Universal composition with joint state. Cryptology ePrint Archive, Paper 2002/047, 2002.
  18. [18]R. Canetti, S. Chari, S. Halevi, B. Pfitzmann, A. Roy, M. Steiner, and W. Venaema. Composable security analysis of os services. In Applied Cryptography and Network Security: 9th International Conference, ACNS 2011, Nerja, Spain, June 7-10, 2011. Proceedings 9, pages 431–448. Springer, 2011.
  19. [19]R. Canetti, A. Cohen, and Y. Lindell. A simpler variant of universally composable security for standard multiparty computation. Cryptology ePrint Archive, Report 2014/553, 2014.
  20. [20]E. Cecchetti. Nonmalleable Progress Leakage . In 2025 IEEE 38th Computer Security Foundations Symposium (CSF), pages 537–552, Los Alamitos, CA, USA, June 2025. IEEE Computer Society.DOI
  21. [21]E. Cecchetti, A. C. Myers, and O. Arden. Nonmalleable information flow control. In 24th ACM Conf. on Computer and Communications Security (CCS), pages 1875–1891. ACM, Oct. 2017.DOI
  22. [22]S. Chari, S. Halevi, and W. Z. Venema. Where do you want to go today? escalating privileges by pathname manipulation. In NDSS Citeseer, 2010.
  23. [23]S. Chong and A. C. Myers. Security policies for downgrading. In 11th ACM Conf. on Computer and Communications Security (CCS), pages 198–209, Oct. 2004.DOI
  24. [24]S. Chong and A. C. Myers. Language-based information erasure. In 18th IEEE Computer Security Foundations Workshop (CSFW), pages 241–254, June 2005.DOI
  25. [25]D. Clark and S. Hunt. Non-interference for deterministic interactive programs. In 5th Workshop on Formal Aspects in Security and Trust (FAST), volume 5491 of Lecture Notes in Computer Science, pages 50–66. Springer, 2008.DOI
  26. [26]M. R. Clarkson and F. B. Schneider. Hyperproperties. In 21st IEEE Computer Security Foundations Symp. (CSF), pages 51–65, June 2008.
  27. [27]M. R. Clarkson, B. Finkbeiner, M. Kolēini, K. K. Micinski, M. N. Rabe, and C. Sánchez. Temporal logics for hyperproperties. In International Conference on Principles of Security and Trust, pages 265–284. Springer, 2014.arxiv.org/abs/1401.4492
  28. [28]T. Dardinier and P. Müller. Hyper Hoare logic:(dis-) proving program hyperproperties. Proc. ACM on Programming Languages, 8(PLDI):1485–1509, 2024.DOI
  29. [29]D. E. Denning. A lattice model of secure information flow. Comm. of the ACM, 19(5):236–243, 1976.DOI
  30. [30]E. W. Dijkstra. A Discipline of Programming. Prentice-Hall, Englewood Cliffs, NJ, 1976.
  31. [31]B. Dongol, M. Griffin, A. Popescu, and J. Wright. Relative security: Formally modeling and (dis) proving resilience against semantic optimization vulnerabilities. In 2024 IEEE 37th Computer Security Foundations Symposium (CSF), pages 403–418. IEEE, 2024.DOI
  32. [32]M. D. Ernst, R. Just, S. Millstein, W. Dietl, S. Pernsteiner, F. Roesner, K. Koscher, P. Barros, R. Bhoraskar, S. Han, P. Vines, and E. X. Wu. Collaborative verification of information flow for a high-assurance app store. In 21st ACM Conf. on Computer and Communications Security (CCS), pages 1092–1104, Nov. 2014.
  33. [33]B. Finkbeiner, M. N. Rabe, and C. Sánchez. Algorithms for model checking HyperLTL and HyperCTL. In Int’l Conf. on Computer Aided Verification (CAV), pages 30–48, July 2015.DOI
  34. [34]J. A. Goguen and J. Meseguer. Security policies and security models. In IEEE Symp. on Security and Privacy, pages 11–20, Apr. 1982.DOI
  35. [35]O. Goldreich, S. Micali, and A. Wigderson. How to play any mental game. In A. V. Aho, editor, 19th Annual ACM Symposium on Theory of Computing, pages 218–229, 1987.DOI
  36. [36]S. Goldwasser and S. Micali. Probabilistic encryption. J. Comput. Syst. Sci., 28(2):270–299, 1984.DOI
  37. [37]D. Hofheinz and V. Shoup. GNUC: A new universal composability framework. J. Cryptol., 28(3):423–508, 2015.
  38. [38]P. Kocher, J. Horn, A. Fogh, D. Genkin, D. Gruss, W. Haas, M. Hamburg, M. Lipp, S. Mangard, T. Prescher, et al. Spectre attacks: Exploiting speculative execution. Comm. of the ACM, 63(7):93–101, 2020.arxiv.org/abs/1801.01203
  39. [39]R. Kusters, M. Tuengerthal, and D. Rausch. The IITM model: A simple and expressive model for universal composability. J. Cryptol., 33(4):1461–1584, 2020.
  40. [40]L. Lamport. The temporal logic of actions. ACM Trans. on Programming Languages and Systems, 16(3):872–923, 1994.DOI
  41. [41]J. Landauer and T. Redmond. A lattice of information. In 6th IEEE Computer Security Foundations Workshop (CSFW), pages 65–70. IEEE Computer Society Press, June 1993.
  42. [42]P. Li and S. Zdancewic. Downgrading policies and relaxed noninterference. In 32nd ACM Symp. on Principles of Programming Languages (POPL), Long Beach, CA, Jan. 2005.DOI
  43. [43]Y. Lindell. How to simulate it – A tutorial on the simulation proof technique. In Tutorials on the Foundations of Cryptography, pages 277–346. Springer International Publishing, 2017.DOI
  44. [44]N. Lynch and M. Tuttle. Hierarchical correctness proofs for distributed algorithms. In Proceedings of 6th ACM Symposium on Principles of Distributed Computation, pages 137–151, Aug. 1987.DOI
  45. [45]U. Maurer. Secure multi-party cryptography – A new paradigm for security definitions and proofs. In S. Mödersheim and C. Palamidessi, editors, Theory of Security and Applications, volume 6993 of Lecture Notes in Computer Science, pages 33–56. Springer, 2011.
  46. [46]U. Maurer and R. Renner. Abstract cryptography. In Innovations in Computer Science, 2011.
  47. [47]F. Montesi. Choreographic Programming. PhD thesis, IT University of Copenhagen, 2013.
  48. [48]A. C. Myers. JFlow: Practical mostly-static information flow control. In 26th ACM Symp. on Principles of Programming Languages (POPL), pages 228–241, Jan. 1999.
  49. [49]A. C. Myers and B. Liskov. A decentralized model for information flow control. In 16th ACM Symp. on Operating System Principles (SOSP), pages 129–142, Oct. 1997.
  50. [50]A. C. Myers, A. Sabelfeld, and S. Zdancewic. Enforcing robust declassification and qualified robustness. Journal of Computer Security, 14(2):157–196, 2006.DOI
  51. [51]M. S. New, W. J. Bowman, and A. Ahmed. Fully abstract compilation via universal embedding. In Proceedings of the 21st ACM SIGPLAN International Conference on Functional Programming, ICFP 2016, page 103–116, New York, NY, USA, 2016. Association for Computing Machinery.
  52. [52]S. Owicki and D. Gries. Verifying properties of parallel programs: An axiomatic approach. Commun. ACM, 19(5):279–285, May 1976.DOI
  53. [53]M. Patrignani, R. S. Wahby, and R. Künnemann. Universal composability is secure compilation. arXiv ePrint 1910.08634, 2019.DOI
  54. [54]F. Pottier and V. Simonet. Information flow inference for ML. ACM Trans. on Programming Languages and Systems, 25(1), Jan. 2003.
  55. [55]S. Ren, C. Acay, and A. C. Myers. An algebraic approach to asymmetric delegation and polymorphic label inference. In European Symposium on Research in Computer Security (ESORICS), Sept. 2025.DOI
  56. [56]F. B. Schneider. Enforceable security policies. ACM Transactions on Information and System Security, 3(1):30–50, 2001. Also available as TR 99-1759, Computer Science Department, Cornell University, Ithaca, New York.
  57. [57]V. Shoup. Sequences of games: a tool for taming complexity in security proofs. cryptology eprint archive, 2004.
  58. [58]M. Soloviev, M. Balliu, and R. Guanciale. Security properties through the lens of modal logic, 2023.arxiv.org/abs/2309.09542
  59. [59]A. Stoughton, A. Johnson, S. Beller, K. Chadha, D. Chen, K. Foner, and M. Zhivich. You sank my battleship! a case study in secure programming. In Proceedings of the Ninth Workshop on Programming Languages and Analysis for Security, PLAS’14, pages 2–14, New York, NY, USA, 2014. Association for Computing Machinery.DOI
  60. [60]The Rocq Development Team. The Rocq prover, 2025.DOI
  61. [61]D. Zagieblo, G. E. Suh, and A. C. Myers. Using information flow to design an ISA that controls timing channels. In 32nd IEEE Computer Security Foundations Symp. (CSF), June 2019.
  62. [62]S. Zdancewic. A type system for robust declassification. Electronic Notes in Theoretical Computer Science, 83(0):263–277, Mar. 2003.DOI
  63. [63]S. Zdancewic and A. C. Myers. Robust declassification. In 14th IEEE Computer Security Foundations Workshop (CSFW), pages 15–23, June 2001.
  64. [64]S. Zdancewic and A. C. Myers. Observational determinism for concurrent program security. In 16th IEEE Computer Security Foundations Workshop (CSFW), pages 29–43, June 2003.DOI

Paper details

vlnc:W_6uw7hdz5
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

Not recorded for this paper

View statement
Looking for related papers…
Contents