💻 computer science

Security Engineering in IIIf, Part II -- Shadowing the IIIf

This paper extends the security engineering of the Isabelle Insider and Infrastructure framework (IIIf) by introducing Morgan's "Shadow" concept to formalize Information Flow Security, thereby resolving the refinement paradox and establishing conditions for secure refinements illustrated through a flight radar system example.

Original authors: Florian Kammüller

Published 2026-06-30

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Florian Kammüller

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: The "Flight Radar" Problem

Imagine you are looking at a public flight radar app on your phone. You see airplanes moving across the map. Usually, this is harmless. But what if a plane suddenly takes a weird, zig-zag detour around a specific area?

In the real world, planes don't just fly in straight lines for fun. If a plane suddenly swerves around a secret military base or a VIP's location, that "swerving" is a clue. Even though the app doesn't show you the secret base, the pattern of the plane's movement tells you exactly where the danger zone is.

This is the problem the paper tackles: How do we stop secret information from "leaking" through the side effects of a system's behavior?

The Characters and the Setting

The System (IIIf): Think of this as a giant, super-strict rulebook for a digital city. It tracks who is where, what rules they follow, and how things move. The authors use a powerful computer tool called "Isabelle" to write this rulebook so strictly that the computer can prove it's correct.
The Attacker (Eve): Eve is a nosy observer who can see everything the system shows to the public (like the plane's position on the map) but isn't supposed to know the secrets (like the location of a secret base).
The Secret (Critical Location): This is the "forbidden zone" that the system is trying to protect.

The Problem: The "Refinement Paradox"

The authors explain a tricky situation called the Refinement Paradox.

Imagine you design a secure system (the "Abstract" version). You prove to the computer that Eve cannot guess the secret. Great!
Then, you decide to make the system better or more detailed (the "Refined" version). Maybe you add a new feature, like showing the plane's speed.

The Paradox: Even if your new feature seems harmless, it might accidentally create a new "leak."

Analogy: Imagine you are hiding a secret note in a safe. You prove the safe is secure. Then, you decide to add a tiny, decorative handle to the safe. You didn't change the lock, but now, if you shake the safe, the handle rattles differently depending on where the note is inside. Suddenly, the handle gives away the secret.

In the paper's example, if the system calculates the plane's speed based on its real (hidden) path instead of its public path, the speed number will be weird whenever the plane is avoiding a secret zone. Eve sees the weird speed and instantly knows where the secret zone is. The system got "more detailed," but it became less secure.

The Solution: The "Shadow"

To fix this, the authors introduce a concept called a Shadow, inspired by a mathematician named Morgan.

What is a Shadow?
Think of the Shadow as a "Bag of Possibilities" for the secret information.

At the start, the Shadow is a giant bag containing every single possibility of where the secret could be. The attacker is totally confused; they have no idea where the secret is.
As the system runs, the Shadow should stay big. If the Shadow shrinks, it means the attacker has learned something new.

The Goal: A secure system is one where the Shadow never shrinks. If the Shadow stays the same size, the attacker's ignorance is preserved. They still know nothing more than they did at the start.

How They Fixed the Flight Radar

The authors applied this "Shadow" idea to their Flight Radar system:

The Leak: In the original insecure version, the plane's movement revealed the secret location. The Shadow shrank because the attacker could rule out certain locations based on the plane's path.
The Fix: They added a "hiding" mechanism. When a plane needs to avoid a secret zone, the system records the real path in a secret box (the critpos component) but shows the plane as if it flew straight through the secret zone on the public map.
The Result: Because the public map looks normal, the attacker's "Bag of Possibilities" (the Shadow) never gets smaller. The attacker still thinks the secret zone could be anywhere.

The "Magic" Proof

The paper does two main things:

Equivalence: They proved that "The Shadow never shrinking" is exactly the same thing as "Non-Interference" (a fancy technical term meaning "Secrets don't affect what the public sees"). It's like proving that "The bag stays full" is the same as "No one stole any apples."
The Safety Rule for Upgrades: They created a rule (Theorem 2) to check if a future upgrade (refinement) will stay secure.
- The Rule: If you add a new feature, you must check if it depends on the secret. If the new feature depends on the secret, the Shadow will shrink, and the upgrade is unsafe.
- The Catch: If the new feature is totally independent of the secret, the Shadow stays big, and the upgrade is safe.

Summary

The paper solves a problem where making a system more detailed accidentally leaks secrets. They use a "Shadow" (a bag of possibilities) to track what an attacker knows. If the Shadow stays full, the system is secure. They proved that if you follow their specific rules when adding new features, you can upgrade the system without accidentally letting the secrets out.

In short: They built a mathematical "security guard" that checks every time you add a new feature to a system, ensuring that the new feature doesn't accidentally whisper the secrets to the public.

Technical Summary: Shadowing the Isabelle Insider and Infrastructure Framework

Problem Statement
The Isabelle Insider and Infrastructure Framework (IIIf) provides a formal basis for security engineering of systems involving human actors, policies, and physical/logical components, utilizing a Refinement-Risk (RR) cycle. While IIIf supports trace-based refinement and property preservation for standard safety properties (e.g., reachability), it faces a critical limitation regarding Information Flow Control (IFC). Specifically, the property of Noninterference (NI)—which ensures that high-security (secret) states do not influence low-security (public) observations—is not generally preserved under specification refinement. This phenomenon, known as the "refinement paradox," means that a specification satisfying NI may yield a refined implementation that leaks information through implicit flows. Existing model-checking approaches within IIIf are insufficient for verifying such trace-set properties, necessitating a new methodology to characterize and guarantee secure refinements.

Methodology
To address the refinement paradox, the paper introduces a formalization of Morgan's concept of a "Shadow" into the IIIf framework. The methodology proceeds through the following steps:

Case Study Integration: The authors utilize a flight-radar system specification (previously formalized in IIIf) as a running example. This system involves aircraft positions, routes, and critical locations. The initial specification demonstrates how implicit information flows occur when an aircraft circumvents a critical location, revealing the existence of that criticality through observable flight path irregularities.
Formalizing Noninterference (NI): NI is defined within IIIf as an indistinguishability relation over state transitions. Two states are indistinguishable to an attacker (with clearance level $a$ ) if their observable components (those with security labels $\leq a$ ) are identical. NI holds if, for any pair of indistinguishable initial states, their subsequent execution traces remain indistinguishable.
Defining the Shadow: Inspired by Morgan's epistemic logic, a "Shadow" is defined as the set of all possible values a security-critical state component could hold from the attacker's perspective.
- Initialization: A shadow component is initialized to the "universe" of its type (all possible values), representing maximum ignorance.
- Shrinking: During state transitions, the shadow "shrinks" (reduces the set of possible values) only if the transition reveals information about the secret component to the attacker.
- Invariant: A secure system must satisfy the invariant $IFC_a$ , where the shadow of a secret component does not shrink during execution. If the shadow shrinks, it implies the attacker has gained knowledge about the secret, indicating a violation of NI.
Equivalence Proof: The paper formally establishes (on paper, due to type quantification limits in Higher Order Logic) that the shadow invariant $IFC_a$ is equivalent to Noninterference ( $NI_a$ ). Specifically, the negation of NI (existence of an illicit information flow) is shown to be equivalent to the existence of a component whose shadow shrinks.
Secure Refinement Characterization: The authors define a condition for secure refinement. A refinement from an abstract system $A$ to a concrete system $C$ preserves security if the refinement map $E$ , when restricted to the shadow components of $C$ , is injective and compatible with the abstract shadow.

Key Contributions

Shadow Formalization in IIIf: The paper extends IIIf with a formal definition of "Shadow" components for infrastructure states, allowing the tracking of an attacker's uncertainty regarding secret state components.
Equivalence of Shadow and NI: It proves that the shadow invariant ( $IFC_a$ ) is equivalent to the Noninterference property ( $NI_a$ ) within the context of the IIIf state-transition model.
Secure Refinement Theorem (Theorem 2): The primary contribution is a theorem characterizing secure refinement. It states that if a refinement map $E$ is injective on the shadow components of the concrete system and compatible with the abstract shadow, then the shadow invariant (and thus NI) is preserved from the abstract to the concrete system.
Resolution of the Refinement Paradox: The methodology provides a mechanism to verify that a refinement step does not introduce new information flows that would violate NI, addressing a known flaw in the standard IIIf RR-cycle.

Results

Application to Flight-Radar System: The authors apply the shadow definition to the flight-radar case study.
- In an insecure version (without hiding mechanisms), the shadow of the critical location component shrinks when a plane circumvents a critical area, proving the violation of $IFC_a$ and NI.
- In a secured version (using a critpos component to hide the actual circumvention), the shadow invariant holds, confirming the absence of illicit flows.
Refinement Analysis: The paper demonstrates that adding a new component (e.g., "speed") calculated based on hidden positions constitutes an insecure refinement because it causes the shadow to shrink, violating the injectivity/compatibility conditions of Theorem 2. Conversely, it shows that adding components that do not depend on secrets and are handled correctly by the refinement map preserves security.
Meta-Theoretical Limits: The authors note that while the equivalence between Shadow and NI can be reasoned about, the full formalization of the equivalence theorem over all infrastructure types is limited by the type system of Isabelle/HOL, as it requires quantification over differently typed components of the state.

Significance and Claims
The paper claims to extend the security engineering capabilities of the IIIf framework by integrating Information Flow Control. Its significance lies in:

Addressing the Refinement Paradox: It offers a concrete methodology to ensure that security properties (specifically NI) are preserved during the refinement process, a capability previously lacking in the framework.
Bridging Abstraction and Implementation: By using the shadow concept, the framework can now formally reason about the "ignorance" of an attacker and ensure that refinements do not inadvertently reduce this ignorance (i.e., leak information).
Practical Verification: The approach allows for the verification of complex, heterogeneous systems (combining physical and logical aspects) where standard model checking fails.

The authors remain modest regarding the scope, acknowledging that the equivalence proofs are currently established "on paper" due to type-theoretic constraints in Isabelle/HOL, and that the methodology is specifically tailored to the IIIf infrastructure model rather than a general-purpose programming language logic. The work builds upon Morgan's foundational concepts but adapts them to a state-transition system with explicit actors and policies, avoiding the need for a dedicated epistemic logic by leveraging the existing IIIf model of actor access rights.