Maude-HCS: Model Checking the Undetectability-Performance Tradeoffs in Hidden Communication Systems
Joud Khoury (Paper author · RTX BBN Technologies), Minyoung Kim (Paper author · SRI International), Christophe Merlin (Paper author · RTX BBN Technologies), Jose Meseguer (Paper author · University of Illinois at Urbana-Champaign), Zachary Ratliff (Paper author · Harvard University), Carolyn Talcott (Paper author · SRI International)
Privacy Enhancing Technologies Symposium (PETS) 2026 · Day 2 · Alpaca
Overview
This talk introduces Maude-HCS, a novel formal framework designed to rigorously model and analyze Hidden Communication Systems (HCS). Presented by Joud Khoury from RTX BBN Technologies, on behalf of a collaborative team including researchers from SRI International, the University of Illinois at Urbana-Champaign, and Harvard University, the work addresses a fundamental challenge in covert channels and steganography: the inherent trade-off between a system's performance (e.g., throughput, latency) and its undetectability (the probability of remaining hidden from a monitor). The research, part of the DARPA W Plan program, highlights the limitations of current empirical testing methodologies and proposes a formal, scalable approach to provide verifiable guarantees.

Key moments
- 0:00 What are hidden communications? Example scenario.
- 1:45 Fundamental performance vs. undetectability trade-off.
- 2:40 Need for formal framework: Maude-HCS approach.
- 4:00 Maude-HCS: Formal modeling with rewriting logic.
- 5:30 Defining and auditing detectability using statistical model checking.
- 7:00 Model predictions align with real-world measurements.
- 8:00 Conclusion, future work, and open-source availability.
Maude-HCS: Model Checking the Undetectability-Performance Tradeoffs in Hidden Communication Systems
Speakers: Joud Khoury (Paper author, RTX BBN Technologies); Minyoung Kim (Paper author, SRI International); Christophe Merlin (Paper author, RTX BBN Technologies); Jose Meseguer (Paper author, University of Illinois at Urbana-Champaign); Zachary Ratliff (Paper author, Harvard University); Carolyn Talcott (Paper author, SRI International)
Conference: PETS
YouTube: https://www.youtube.com/watch?v=qkcvx7kZj68
Overview
This talk introduces Maude-HCS, a novel formal framework designed to rigorously model and analyze Hidden Communication Systems (HCS). Presented by Joud Khoury from RTX BBN Technologies, on behalf of a collaborative team including researchers from SRI International, the University of Illinois at Urbana-Champaign, and Harvard University, the work addresses a fundamental challenge in covert channels and steganography: the inherent trade-off between a system's performance (e.g., throughput, latency) and its undetectability (the probability of remaining hidden from a monitor). The research, part of the DARPA W Plan program, highlights the limitations of current empirical testing methodologies and proposes a formal, scalable approach to provide verifiable guarantees.
The core motivation behind Maude-HCS stems from the critical need for formal assurances that align with real-world implementation behavior. Traditional methods of designing and evaluating HCS often rely on strong privacy arguments followed by empirical testing, which can lack the generality and rigor required to account for sophisticated adversaries or diverse operational environments. Maude-HCS aims to overcome these shortcomings by offering a comprehensive framework for formally specifying HCS protocols, embedding mechanisms, background traffic, and adversary models, thereby enabling qualitative and quantitative analysis of their undetectability-performance characteristics.
Ultimately, Maude-HCS provides a robust platform for auditing the privacy claims of hidden communication systems. By translating formal model predictions into real-world guarantees, the framework offers a powerful tool for both system designers seeking to optimize HCS and defenders aiming to understand and detect them. The open-source nature of the project further encourages community engagement and broader adoption in the security and privacy research landscape.
Background
▶ Watch: What are hidden communications? Example scenario. (0:00)
Hidden Communication Systems (HCS) are designed to transmit information covertly, often to exfiltrate data or establish clandestine channels, while evading detection by network monitors. The speaker illustrates this with a common scenario: Alice wants to exfiltrate a file to Bob. Instead of using an obvious channel, Alice might encode the file's bits into the least significant bits (LSBs) of an image. This image could then be uploaded using an ordinary network protocol, such as HTTP, masquerading as legitimate traffic. To inform Bob about the image, Alice might share a hash of the image via another regular protocol like DNS, which Alice uses daily. Bob can then retrieve the image, extract the hidden file, and the communication remains largely unnoticed by the monitor. The essence of HCS lies in leveraging legitimate, everyday network protocols and traffic patterns to conceal illicit activity, making it challenging for a monitor to distinguish covert communication from benign operations.
A fundamental challenge in designing and deploying HCS is the undetectability-performance trade-off. As Alice attempts to send more information, the statistical footprint of her activity tends to increase, making the hidden communication more susceptible to detection. Conversely, highly undetectable systems often achieve this at the cost of lower throughput or higher latency, impacting their practical utility. Users of HCS typically have specific operational requirements that dictate the acceptable balance between these two properties.
Historically, the development and evaluation of HCS have followed a largely empirical path. Designers propose a system, make strong arguments about its privacy properties, implement it, and then test it against classifiers in controlled environments. While some formal verification might be involved, this approach often falls short in providing generalizable guarantees or comprehensively modeling the adversary's capabilities. The speaker emphasizes that this method is "hard to see" (implying difficulty in verifying or trusting the claims) and lacks a formal, general framework that can model the entire system, including the adversary and all underlying assumptions. The critical need is for a scalable way to analyze these trade-offs both qualitatively and quantitatively, with the crucial caveat that any guarantees derived from such models must directly align with and be predictive of real-world implementation behavior. Without this alignment, the utility and trustworthiness of the models are severely compromised.
Key Findings
▶ Watch: Need for formal framework: Maude-HCS approach. (2:40)
The Maude-HCS project introduces a groundbreaking formal modeling framework that significantly advances the state of the art in analyzing Hidden Communication Systems. The primary contribution is the development of Maude-HCS itself, a comprehensive toolset that allows designers to formally specify all critical elements of HCS, including the underlying network protocols, the specific transforms used for embedding hidden data, the application-layer behaviors, and crucially, the adversary's capabilities and assumptions. This holistic modeling capability addresses the limitations of prior empirical approaches by providing a rigorous foundation for analysis.
A key achievement of Maude-HCS is its ability to precisely express and measure quantitative properties such as performance (e.g., latency, throughput) and undetectability within a formal framework. The researchers introduced a novel, distribution-based notion of undetectability defined over observable trace semantics. This concept, grounded in indistinguishability, allows for a more nuanced and accurate assessment of how well an HCS can blend into legitimate traffic, moving beyond simpler binary detection metrics.
The framework demonstrates how to effectively audit undetectability claims made by HCS. By comparing traces from "ordinary" (no hidden communication) and "HCS" (with hidden communication) worlds, Maude-HCS can compute statistical measures like true positive and false positive rates, enabling the potential falsification of overambitious undetectability claims. A particularly compelling finding is the establishment of "sound predictive times," indicating that the guarantees and predictions derived from the Maude-HCS models demonstrably translate to and align with the behavior observed in real-world implementations.
The practical utility of Maude-HCS was showcased through its ability to sweep operating points, illustrating the direct relationship between system parameters (e.g., traffic volume, detector thresholds) and the resulting undetectability or performance metrics. Crucially, the talk presented strong empirical evidence of alignment between the model's predictions (e.g., for latency and throughput) and measurements obtained from an independent, highly qualified testbed. This validation confirms that Maude-HCS is not merely a theoretical exercise but a practical tool capable of providing actionable insights for both the design of robust HCS and the development of effective detection strategies.
Technical Deep Dive
▶ Watch: Maude-HCS: Formal modeling with rewriting logic. (4:00)
At its core, Maude-HCS leverages rewriting logic with its fine and probabilistic extensions as the formal language for specifying distributed concurrent systems. Rewriting logic is particularly well-suited for this task due to its ability to naturally express states as terms and computations as concurrent rule applications, making it ideal for modeling complex interactions within network protocols, application logic, and adversary behaviors. The fine extension likely refers to finer-grained control or expressiveness, while the probabilistic extensions are essential for modeling stochastic elements, such as network delays, message drops, or the adversary's probabilistic strategies.
The formal specification process within Maude-HCS involves several key components:
- Underlying Protocols: Formal descriptions of standard network protocols (e.g., TCP/IP, DNS, HTTP) that HCS leverage.
- Transforms for Embedding: Detailed specifications of how hidden information is embedded into legitimate traffic (e.g., LSB steganography, timing channels).
- Applications: Models of the legitimate application behavior that generates background traffic, providing cover for the hidden communication.
- Adversary: Formal representation of the monitor or attacker, including its capabilities, knowledge, and detection strategies.
Once these elements are formally specified as non-deterministic actors and theories in rewriting logic, they are automatically transformed into probabilistic executable models. This transformation is facilitated by a specialized component or tool within the Maude-HCS framework. A critical aspect of this step is ensuring that the probabilistic models and their observed responses remain aligned with the non-deterministic specifications. This preserves the integrity of the formal reasoning while enabling executable simulations.
With the probabilistic models in place, designers can then formally define performance (e.g., average latency, maximum throughput, jitter) and undetectability properties. The definition of undetectability is central to Maude-HCS and is conceptualized through a "two-world" model:
- Ordinary World: Represents network traffic and system behavior without any hidden communication.
- Hidden Communication System (HCS) World: Represents the same network traffic and system behavior, but with the additional presence of covert communication.
The adversary's goal is to distinguish between these two worlds based on observable network traces. Formally, this distinction is measured using metrics like Kullback-Leibler divergence or other statistical "like versus divergence measures" applied over the distributions of traces generated in each world. A high divergence implies easier detectability, while low divergence indicates greater undetectability.
To audit HCS claims, Maude-HCS employs Monte Carlo statistical model checking. This technique involves simulating the system many times in both the ordinary and HCS worlds, generating a large number of observable traces. By analyzing these trace distributions, the framework can statistically compute true positive rates (correctly identifying hidden communication when it's present) and false positive rates (incorrectly identifying hidden communication when it's not). This statistical analysis allows for the quantitative assessment of an HCS's undetectability claim, providing a robust mechanism to potentially falsify claims that do not hold under rigorous scrutiny. The speaker notes that this process "weighs the other versions of the game," suggesting it can evaluate different adversary models or system configurations.
The ongoing work for Maude-HCS focuses on significantly increasing its scalability and adding interactive analysis capabilities, which would further enhance its utility for complex, large-scale systems. The entire framework is developed as open source, encouraging community contributions and broader adoption.
Demo / Proof of Concept
▶ Watch: Model predictions align with real-world measurements. (7:00)
While the talk did not feature a live, interactive demonstration, the speaker presented compelling results that served as a proof of concept for the Maude-HCS framework's capabilities and its alignment with real-world scenarios. A key aspect demonstrated was the ability to sweep operating points to visualize the inherent trade-offs in HCS. For instance, one graph illustrated how increasing the volume of traffic sent by the client led to "lower and lower binding pieces." This metric, while not explicitly defined, likely represents a measure of the effectiveness or undetectability of the hidden communication. The trend observed—that more traffic correlates with reduced undetectability—is a typical characteristic of HCS and was accurately captured by the model. The framework also allowed for sweeping other parameters, such as the detector's thresholds, enabling an understanding of how changes in detection sensitivity impact the system's overall performance and undetectability.
The most critical aspect of the proof of concept was the strong alignment demonstrated between the model's predictions and empirical measurements from a real-world testbed. The speaker presented a graph comparing model predictions (blue line) against empirical measurements (orange line) obtained from an independent, highly qualified evaluation team. The x-axis represented "different qualities of different initial configurations" of the HCS. The primary metrics measured and compared were latency and throughput, although the speaker noted "many other measures" also showed strong alignment. Latency was specifically highlighted as a "primary concern" in the context of file exfiltration. The visual evidence showed that the blue (model) and orange (empirical) lines tracked each other very closely, indicating that the formal models within Maude-HCS accurately predict the behavior of real-world HCS implementations. This robust validation is crucial, as it instills confidence that the theoretical guarantees derived from the framework are directly applicable and trustworthy in practical deployments. This alignment underscores Maude-HCS's utility not just as a theoretical tool, but as a practical engineering aid for designing and auditing hidden communication systems.
Defensive Implications
▶ Watch: Conclusion, future work, and open-source availability. (8:00)
The Maude-HCS framework offers significant implications for network defenders and security professionals tasked with detecting and mitigating hidden communication systems. By providing a formal, rigorous method to analyze HCS, it moves beyond heuristic-based detection and offers a deeper, more predictive understanding of these covert channels.
Firstly, Maude-HCS enables defenders to audit undetectability claims of various HCS designs. Instead of relying solely on vendors' assertions or limited empirical tests, defenders can use this framework to systematically evaluate how well an HCS truly blends into background traffic under different conditions and against various adversary models. The ability to potentially "falsify" claims means defenders can identify weak points in HCS designs or expose systems that are less undetectable than advertised. This is crucial for making informed decisions about the security posture of their networks and the potential for covert data exfiltration.
Secondly, the framework's capacity to model the adversary and sweep parameters like detector thresholds is invaluable. Defenders can use Maude-HCS to simulate different detection strategies and understand their effectiveness. For example, they could model an HCS and then explore how adjusting the sensitivity of their Intrusion Detection Systems (IDS) or network traffic analysis tools would impact the true positive and false positive rates of detection. This allows for optimization of defensive countermeasures to achieve a desired balance between detection accuracy and acceptable false alarm rates, tailored to specific network environments and threat profiles.
Furthermore, the detailed technical deep dive into how HCS leverage underlying protocols and embedding transforms provides defenders with a granular understanding of covert channel mechanisms. This knowledge can inform the development of more sophisticated and targeted detection techniques. By understanding the formal properties and statistical indicators of hidden communication, defenders can design better feature engineering for machine learning-based detection systems or develop more robust rule-based signatures.
Finally, the strong alignment between model predictions and real-world empirical measurements is perhaps the most impactful defensive implication. It means that the insights gained from Maude-HCS are not just theoretical curiosities but actionable intelligence. Defenders can trust that the vulnerabilities identified or the optimal detection strategies derived from the model will likely hold true in their operational environments. The open-source nature of Maude-HCS further empowers the defensive community by providing a transparent, extensible tool that can be adapted, improved, and shared among security practitioners to collectively enhance capabilities against evolving hidden communication threats.
Key Takeaways
- Formal Framework for HCS Analysis: Maude-HCS is a novel, formal framework that enables rigorous modeling and analysis of Hidden Communication Systems (HCS), addressing the limitations of purely empirical approaches.
- Undetectability-Performance Trade-off: The framework explicitly models and quantifies the fundamental trade-off between the performance (e.g., latency, throughput) and undetectability of HCS.
- Rewriting Logic for Specification: HCS, underlying protocols, embedding transforms, applications, and adversaries are formally specified using rewriting logic with probabilistic extensions, natural for distributed concurrent systems.
- Novel Undetectability Notion: Maude-HCS introduces a distribution-based notion of undetectability, defined over observable trace semantics, using a "two-world" model and statistical divergence measures.
- Empirical Validation and Alignment: The framework demonstrates strong alignment between its model predictions for performance metrics (e.g., latency, throughput) and real-world empirical measurements from an independent testbed.
- Auditing and Optimization Capability: Maude-HCS allows for auditing undetectability claims through Monte Carlo statistical model checking and enables the optimization of HCS design parameters and defensive detection strategies.
About the Speaker(s)
The primary presenter for this talk was Joud Khoury, who leads a small security and privacy group at RTX BBN Technologies. Khoury emphasized that this work is a collaborative effort, undertaken jointly with researchers from SRI International, the University of Illinois at Urbana-Champaign, and Harvard University. The project is also a part of the DARPA W Plan program, focusing on network design and development. The collective expertise of these institutions and individuals underpins the sophisticated formal methods and rigorous validation presented in the Maude-HCS research.
Reviews
Dr. Zero (Offensive Security Researcher) — SOLID
A rigorous, DARPA-backed application of formal methods to covert network channels. Instead of relying on empirical testing to see if an exfiltration method works, they built a mathematical framework to prove whether it's actually undetectable, and validated the math against a real testbed.
Heather Calloway (CISO) — SOLID
This DARPA-backed research introduces a mathematical framework for proving whether a covert communication channel—like data exfiltration hidden in legitimate HTTP traffic—can actually evade detection. While the formal modeling is strictly for academics and tool builders, it highlights a critical reality for enterprise defenders: detecting covert data loss is strictly bound by mathematical limits. Most leadership teams can skip the paper, but network security architects should understand the baseline mechanics of why stealthy exfiltration works.
→ Top-rated talks at Privacy Enhancing Technologies Symposium (PETS) 2026
All talks from Privacy Enhancing Technologies Symposium (PETS) 2026