From Automata Learning to Model Checking: Formal Security Verification of Black-Box Protocols

arXiv:2509.22215 · cs.CR, cs.FL · Submitted 2025-09-26 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: Next we'll be talking about the paper "From Automata Learning to Model Checking: Formal Security Verification of Black-Box Protocols".

Jane: The paper was written by Stefan Marksteiner, Mikael Sjödin and Marjan Sirjani from AVL List GmbH and Mälardalen University.

Tom: Stay tuned as we take you through the paper and discuss its implications.

Paper discussion segment 1: Tom: We’re looking at a paper titled "From Automata Learning to Model Checking: Formal Security Verification of Black-Box Protocols" by Stefan Marksteiner and his colleagues from AVL List and Mälardalen University. Jane, this sounds like it's targeting those systems where we just don't have the blueprints, right?

Jane: Exactly, Tom. Usually, if you want to prove a protocol is secure, you need the internal logic written down in a model. But these authors are dealing with "black boxes," meaning the actual code or design is proprietary and hidden away.

Tom: So we're basically trying to find flaws in something we aren't allowed to see?

Jane: That’s the challenge! It’s like trying to figure out how a complex lock works just by rattling it and seeing when it clicks, without ever opening the casing.

Lu: That rattling is actually a very sophisticated mathematical process called active automata learning. Instead of random guessing, they use algorithms to systematically probe the system until they can map out its entire behavioral logic.

Meng: I’m wondering how that works in a real production environment, though. If you're testing an automotive ECU or an NFC chip, you can't just run infinite queries without potentially causing issues or needing specialized hardware interfaces.

Lu: You're right, Meng, and that's why they use these "adapters" to bridge the gap between the mathematical learner and the physical device. It’s a way to turn real-world signals into formal data that an AI or an algorithm can actually digest.

Meng: That makes sense for an engineer because it means we can use their method on actual hardware, like a Proxmark3 for NFC or a CAN interface for cars. It moves the theory into the realm of actual diagnostic tools.

Lalam: This is fascinating because it bridges the gap between raw physical interaction and high-level logical reasoning. By turning physical signals into mathematical models, we are essentially teaching machines to understand the "grammar" of security protocols. This capability could eventually allow automated systems to autonomously audit global infrastructure for vulnerabilities without needing human experts to manually write out every single rule.

Tom: It sounds like we're moving from manual inspection to something much more systematic. Let's talk about what they actually do once they have that map of the system's behavior.

Paper discussion segment 2: Jane: Now that we know they can build these maps, let’s talk about how they actually find the security holes in "From Automata Learning to Model Checking: Formal Security Verification of Black-Box Protocols." They use something called Context-based Proposition Maps to add meaning to the map.

Tom: Wait, Jane, if the learner just gives us a map of inputs and outputs, how does that tell us anything about security? A map showing "if I send A, I get B" doesn't inherently say "this is insecure."

Jane: You hit the nail on the head. The map itself is just a bunch of transitions. So, they use these Proposition Maps to say, "When this specific sequence happens, it means the user is now 'authenticated' or 'has high privileges'."

Tom: So they are essentially labeling the states of the machine with security concepts?

Jane: Yes! They turn a simple Mealy machine into an "Annotated Mealy Machine," which is basically a hybrid that includes these logical labels. Once you have those labels, you can use "model checking" to ask questions like, "Is there any way to reach a state where we have access without being authenticated?"

Lu: It’s quite brilliant because they've created a bridge between two different mathematical worlds. They take the learned behavior and inject semantic information into it, which allows for formal verification that was previously impossible for black-box systems.

Meng: From a practical standpoint, the way they handle "implicit states" is what interests me. Sometimes a security property isn't just about being in a state, but about something that happens during the transition itself—like a specific error code being sent.

Lu: They actually solve that by splitting those transitions into two parts to create an "implicit state," which gives that specific moment its own logical label. It’s a very clever way to ensure no detail is lost when moving from the real world into the mathematical model.

Lalam: This ability to assign meaning to transient events is what makes this approach so powerful for cultural security standards. We are seeing a shift where we can mathematically prove that an electronic passport or a car component follows international safety protocols, even when we don't own the manufacturing secrets. It creates a layer of trust in the digital tools that shape our daily lives.

Tom: It’s essentially turning a "black box" into a "gray box" that we can actually reason about. But how do they make sure this whole automated pipeline doesn't just make mistakes?

Paper discussion segment 3: Jane: That's the part where the automation really shines in this paper. They don't just stop at finding a model; they’ve built an entire pipeline that translates those annotated models into a language called Rebeca.

Tom: So, once the model is learned and labeled, it gets converted into code that can be run through a formal checker automatically?

Jane: Exactly. This removes the human error of someone having to manually write out the Rebeca code or misinterpreting what an input means. The paper shows how they use templates for generic security properties like confidentiality and privilege levels, so you don't have to reinvent the wheel every time.

Tom: I noticed they also mentioned that if the model checker finds a violation, it doesn't just say "error"—it provides a trace.

Jane: Right! It gives you the exact sequence of commands that led to the failure. You can then take that sequence and run it on the actual physical device to see if it actually fails in real life.

Lu: This creates a feedback loop where the model checker acts as a high-level debugger for hardware protocols. If the test fails on the real device, you just feed that trace back into the learner to refine your model. It’s an iterative process of perfecting our understanding of the system.

Meng: I really appreciate that they address how to handle non-determinism too. In their Rebeca implementation, they can introduce things like timeouts or faults to see if the security properties still hold up when things aren't going perfectly in the real world.

Lu: That’s a huge leap forward because real-world systems are rarely perfect; they have delays and random errors all the time. By simulating those "maximum credible accident" scenarios, they make their security guarantees much more robust.

Lalam: This level of automation could fundamentally change how we approach software and hardware certification globally. Imagine a world where every new smart device must pass through an automated formal verification pipeline before it can even be sold to the public. We are looking at a future where "security by design" is not just a slogan, but a mathematically proven reality for every connected object in our homes and cars.

Tom: It’s an incredible vision of automated trust. Let's wrap this up before we get too carried away with the possibilities!

Conclusion: Jane: We've covered a lot of ground today, from using automata learning to map out mysterious black boxes to using model checking to prove they are secure. This paper, "From Automata Learning to Model Checking: Formal Security Verification of Black-Box Protocols," really shows how we can bridge that gap between physical hardware and formal mathematical proofs.

Tom: It's a massive step toward making the security of our most critical systems—like our cars and even our passports—something we can verify without needing to see every line of proprietary code.

Lu: It’s truly a paradigm shift in how we view digital trust!

Meng: And it’s a tool that engineers can actually use in the field, not just theorists in an office.

Lalam: Ultimately, it empowers us to build a more resilient and verifiable digital culture for everyone.

Tom: Thanks for joining us on this deep dive. We'll see you next time when we tackle another fascinating paper!

Jane: Goodbye everyone!--- END OF SCRIPT ------

Stefan Marksteiner, Mikael Sjödin, Marjan Sirjani

AVL List GmbH · Mälardalen University

cs.CR, cs.FL

Submitted: 2025-09-26

Updated: 2026-09-11

Comments: 27 pages, 9 figures, 4 tables, preprint accepted for publication in Elsevier Computers & Security - Original abstract shortened to comply to the arXiv requirements

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Importance score: 60/100

The gist: This paper presents a method for the "formal verification of communication protocols" that addresses the challenge of analyzing proprietary systems that are "accessible only as black boxes." By

Key concepts

Active Automata Learning
This is a sophisticated mathematical process used to systematically probe a system's behavior. Instead of random guessing, algorithms use this method to map out the entire behavioral logic of a black-box protocol by interacting with it.
Context-based Proposition Maps
These maps are used after learning the system's behavior. They add meaning to the input/output data by labeling states with security concepts, such as whether a user is authenticated or has high privileges, turning simple transitions into meaningful logical statements.
Model Checking
This is a formal verification technique used to ask questions about the learned model. It allows researchers to check if there is any sequence of events that leads to an insecure state, providing mathematical proof of security properties for black-box systems.
Rebeca Language
This is a language used in the paper's pipeline to translate annotated models into code for a formal checker. It removes human error by using templates for generic security properties, allowing automated checking of complex protocols.

Terminology

Summary

This paper presents a method for the formal verification of communication protocols that addresses the challenge of analyzing proprietary systems that are accessible only as black boxes. By combining active automata learning with model checking, the authors provide a scalable and systematic way to discover security vulnerabilities without requiring internal system models, thereby reducing modeling effort and improving automation in industrial and safety-critical domains.

The Proposed Methodology

The proposed approach bridges the gap between learned behavior and property verification by introducing Annotated Mealy Machines (AMMs) through Context-based Proposition Maps (CPMs). First, behavioral models are inferred from system interactions using active automata learning via the LearnLib library. Because these learned Mealy machines do not intrinsically contain semantic information, CPMs—which are simple, tabular rule sets—are used to enrich the models with security-relevant propositions. These maps define when specific propositions become true or false based on actions on transitions between states.

The resulting AMMs serve as hybrid structures between Mealy machines and Kripke structures, allowing them to be automatically transformed into verifiable models in the Rebeca modeling language. This automated tool chain enables the model-checking of generic security properties, while also allowing for the introduction of non-deterministic behavior, such as timeouts or faults, to examine if properties hold under different conditions. The key contributions include:

** A method for augmenting learned protocol models with security-relevant propositions;**

** A fully automated transformation pipeline from learned models to model-checking artifacts;**

** Reusable, generic security property templates that are instantiated in protocol-specific models; and,**

** Empirical validation through case studies demonstrating applicability in different protocols and domains.**

Generic Security Requirements

To reduce the workload of defining meaningful security properties, the paper provides reusable, generic security property templates that can be instantiated for concrete protocols. These templates are represented by a composition of propositions defined through CPMs. The authors define four fundamental requirements:

  1. Authentication: Requiring authentication before accessing protected resources.

  2. Confidentiality: Ensuring an unsecured access operation on a protected resource does not return a positive response.

  3. Privilege Levels: Verifying that access to critical resources requires a sufficient level of privilege.

  4. Key Validity: Ensuring that if an invalid key is provided, then the key MUST NOT be accepted.

By using CPMs to populate these generic properties with protocol-specific propositions, engineers can adapt the framework to diverse systems with minimal manual effort.

Empirical Validation and Testing

The approach was validated through case studies involving two distinct communication protocols: Near Field Communication (NFC) used in eMRTDs and Unified Diagnostic Services (UDS) used in automotive ECUs. In the NFC case study, the tool chain successfully verified that the scrutinized Austrian passports implemented authentication, confidentiality, privilege levels, and key validity.

In contrast, the UDS case study on an automotive electronic control unit revealed a security vulnerability. Specifically:

** The model found a violation of property P4 (Key Validity);**

** In the authenticated state, the system accepted a wrong key with a success return code;**

The authors note that if a property violation is found, the trace can be concretized via the learner’s interface and be used as a test case for verification on the live system. This creates an automated loop of learning, checking, and testing real-world examples. Moving from model checking to physical testing allows researchers to confirm if a violation is a true issue or merely a counterexample for further model refinement.

Improvements for AI systems

To improve AI systems using the methodologies presented in this paper, we must transition from purely probabilistic/statistical safety measures to a hybrid architecture that integrates active automata learning and formal model checking.

The following are specific improvements and the resulting capabilities of an improved AI system:

  1. Improvement: Implementation of a Formal Behavioral Verification Engine for Autonomous Agents

Instead of relying on Reinforcement Learning (RL) reward functions—which are notoriously difficult to align with complex human values—the AI architecture would incorporate an active learning loop using the paper's approach to treat the agent as a System-under-learning (SUL).

What the improved AI can do:

  • Construct a verifiable Behavioral Mealy Machine: The system will automatically infer a state machine representing its own tool-use and API interaction patterns through membership and equivalence queries.

  • Enforce LTL (Linear Temporal Logic) Safety Constraints: The agent will be able to check its proposed action sequences against formal properties before execution. For example, it could guarantee that it is never the case that a sensitive data retrieval (PROT) occurs without a prior successful authentication (AUTH), expressed as:

Constructed Property: □(¬AUTH ∧ PROT → ¬ACCESSOK).

  • Verify Multi-Agent Protocol Compliance: In multi-agent environments, the system can model other agents as Rebecs (actors) and use Context-based Proposition Maps (CPMs) to ensure that agent interactions do not violate global security protocols or privilege hierarchies.
  1. Improvement: Automated Adversarial Red-Teaming via Counterexample Concretization

Current LLM red-teaming is largely manual or relies on heuristic prompt engineering. We can implement the paper’s Learn-Check-Test pipeline to automate the discovery of vulnerabilities (e.g., prompt injection or jailbreaking).

What the improved AI can do:

  • Automated Vulnerability Discovery: The system will learn a model of a target application, use model checking to find LTL property violations (e.g., finding a sequence of inputs that leads to an unauthorized state), and—crucially—convert those abstract violations into concrete test traces.

  • Self-Correcting Adversarial Loops: If a discovered violation is found to be a false positive during testing on the live system, the AI will automatically use that trace as a counterexample to refine its learned model, creating an increasingly accurate map of the target's attack surface.

  1. Improvement: Semantic Safety Layer via Context-Based Proposition Maps (CPMs)

Current AI safety layers (like guardrails) are often shallow and look for specific keywords or patterns. We would replace these with a Semantic Safety Layer that uses CPMs to bridge the gap between raw token/action output and high-level security semantics.

What the improved AI can do:

  • Context-Aware Decision Making: Instead of just blocking a word, the system will evaluate if an action gains or loses a specific security proposition (e.g., Privilege Level).

  • Bridging Symbolic and Sub-symbolic Reasoning: The system can map high-dimensional neural outputs to discrete, checkable propositions (e.g., mapping a specific API call to the proposition ACCESSOK). This allows the AI to reason about its own security state using formal logic rather than just probability.

  1. Improvement: Non-Deterministic Stress-Testing via Model Alteration

The paper describes altering models to introduce non-determinism (like timeouts or faults). We can integrate this into the training/evaluation phase of AI agents.

What the improved AI can do:

  • Robustness Verification under Uncertainty: The system will not just be trained for perfect conditions but will be formally tested against maximum credible accident scenarios. It will simulate non-deterministic failures (e.g., network latency, API timeouts, or corrupted inputs) within its Rebeca-based model to ensure that its safety properties hold even when the environment is unstable.

Related papers