[Paper] Type-Based Enforcement of Non-Interference for Choreographic Programming

Source: arXiv - 2602.21630v1

Overview

The paper introduces a type‑based static analysis for choreographic programming that guarantees non‑interference—i.e., no secret (high‑security) data can leak to public (low‑security) observers, even through subtle implicit flows. By embedding security policies directly into the type system, developers can synthesize distributed protocol implementations that are provably free of information‑flow bugs, without writing any extra runtime checks.

Key Contributions

• Policy‑parametric type system for choreographies that enforces termination‑insensitive non‑interference, covering both explicit data flows and implicit (control‑flow) leaks.
• Program‑counter (PC) discipline integrated into the type system, enabling precise tracking of implicit flows across conditional branches and loops.
• Support for recursive procedures via a procedure context reconstructed through a constraint‑generation phase, allowing realistic, modular protocol specifications.
• Formal proof of soundness: the type system guarantees non‑interference with respect to a standard small‑step operational semantics for choreographies.
• Constraint‑based type inference that can be automated, making the approach practical for real‑world development pipelines.

Methodology

1. Choreography Language – The authors start from a core choreographic language that describes global interactions (who talks to whom, what messages are exchanged).
2. Security Lattice – A simple two‑level lattice (High ⊒ Low) is used to label data and participants. The type system is policy‑parametric, meaning the same framework can be instantiated with richer lattices if needed.
3. Typing Rules – Each choreography construct (message send, receive, conditional, recursion) gets a typing rule that propagates security labels and updates a program‑counter label representing the current control‑flow context.
4. Constraint Generation – While type‑checking, the system generates a set of constraints (e.g., “label of expression ≤ PC label”). These constraints are solved to infer the minimal security levels for all program elements.
5. Procedure Context Reconstruction – Recursive procedures are typed using a context that records the assumed security levels of parameters and the PC. The context is iteratively refined until a fixed point is reached.
6. Soundness Proof – Using a small‑step semantics for choreographies, the authors prove that any well‑typed choreography satisfies termination‑insensitive non‑interference: low‑security observers cannot distinguish runs that differ only in high‑security data.

Results & Findings

• The type system rejects choreographies that could cause covert channels (e.g., branching on secret data that influences public messages).
• Recursive protocols (e.g., repeated authentication handshakes) are accepted when they respect the PC discipline, demonstrating that the approach scales beyond trivial examples.
• The constraint‑based inference runs in polynomial time for typical choreographies, indicating that the analysis can be integrated into existing build tools without prohibitive overhead.
• Formal proof shows no false negatives: any accepted choreography is guaranteed to be non‑interfering under the defined semantics.

Practical Implications

• Secure‑by‑design microservices: Teams can write a single global choreography for a distributed API, automatically obtain local service code, and be confident that no secret data leaks across service boundaries.
• Compliance‑ready code generation: Regulations (e.g., GDPR, HIPAA) often require proof that personal data never flows to unauthorized components. The type system provides a machine‑checkable artifact for auditors.
• Reduced testing burden: Since many information‑flow bugs are caught at compile‑time, developers spend less time writing and maintaining complex security‑testing harnesses.
• Tooling integration: The constraint‑generation phase can be hooked into existing IDEs or CI pipelines, delivering immediate feedback as developers evolve their choreographies.
• Foundation for language extensions: The approach can be adapted to richer security lattices (multi‑level clearance, role‑based policies) or to incorporate declassification mechanisms, paving the way for more expressive secure protocol DSLs.

Limitations & Future Work

• The current non‑interference guarantee is termination‑insensitive; it does not protect against leaks via termination behavior (e.g., a secret‑dependent infinite loop).
• The security model assumes a static two‑level lattice; extending to dynamic or more granular policies would require additional machinery.
• Performance evaluation on large‑scale industrial choreographies is not provided; empirical studies are needed to confirm scalability.
• Future research directions include integration with declassification, support for asynchronous communication primitives, and formal verification of the generated local code to close the gap between global guarantees and actual deployed services.

Authors

• Marco Bertoni
• Saverio Giallorenzo
• Marco Peressotti

Paper Information

• arXiv ID: 2602.21630v1
• Categories: cs.PL, cs.CR, cs.DC
• Published: February 25, 2026
• PDF: Download PDF