💻 computer science

Evaluating the Effectiveness of LLMs in Aiding Compliance Testing of PKCS#1-v1.5

This paper evaluates the effectiveness of combining grammar-level mutation with LLM-based code synthesis for compliance testing of PKCS#1 v1.5 implementations, finding that while the approach successfully reproduces known vulnerabilities and discovers new discrepancies, its utility is severely limited by high rates of LLM hallucination that create a significant gap between operational reliability and semantic fidelity.

Original authors: Polina Kozyreva, Endadul Hoque

Published 2026-06-19

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Polina Kozyreva, Endadul Hoque

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

Imagine you are a strict building inspector. Your job is to check if every house built in a city follows the exact same blueprint. The blueprint (the "specification") says: "The front door must be 3 feet wide, the roof must be red, and the chimney must be exactly 10 feet tall."

In the world of computer security, these "houses" are software programs that handle encrypted messages (like digital signatures). The "blueprint" is a complex set of rules called PKCS#1 v1.5. If a program builds a house that doesn't match the blueprint perfectly, it might have a hidden backdoor that hackers can use to break in.

The Problem: Checking is Hard

Checking these houses is incredibly difficult.

Random guessing doesn't work: If you just throw random bricks at a house, you'll almost never accidentally build a door that is exactly 3 feet wide. You need a very specific plan.
Expert tools are slow: There are tools made by human experts that can check every possible variation of the blueprint, but building these tools takes years of deep study and manual work. They are like hiring a team of master architects to inspect every single house.

The New Idea: The "AI Architect"

The researchers in this paper asked a simple question: Can we use a Large Language Model (an AI) to act as a "translator" that turns a broken blueprint into a test?

Here is their process:

The Original Blueprint: They took the official rules for the house.
The Mutator (The "What-If" Machine): They used a computer program to intentionally break the blueprint in 13 different ways. For example, they might say, "What if the door is 4 feet wide?" or "What if the roof is blue?" or "What if we remove the chimney entirely?"
The AI Translator: They handed these broken blueprints to an AI and said, "Write a computer program that builds a house exactly according to this broken blueprint."
The Test: They ran the AI's program to build the house and then tried to feed that house to 48 different software programs (the "builders") to see if the builders accepted the broken house. If a builder accepted a broken house, that builder had a security flaw.

The Results: A Tale of Two Numbers

The results were a mix of great news and a major warning.

The Good News (Operational Reliability):
The AI was amazing at following instructions to start the job.

99.8% of the time, the AI successfully wrote a program that ran without crashing. It was like an architect who always managed to hand you a set of blueprints that didn't have any typos or missing pages.

The Bad News (Semantic Fidelity):
However, the AI was terrible at actually following the broken blueprint.

Only 17.5% of the time did the AI actually build the house the way the broken blueprint asked.
In 82.5% of cases, the AI "hallucinated." It looked at the broken blueprint, thought, "Oh, that looks wrong," and secretly fixed it back to the original perfect blueprint before building the house.

The Analogy:
Imagine you ask the AI: "Build a house with a blue door."

Success: The AI builds a house with a blue door.
Hallucination: The AI builds a house with a red door because it "knows" doors are usually red, even though you specifically asked for blue. It ignored your specific instruction.

What Did They Find?

They found the big bugs: The approach successfully recreated 10 out of 13 known security flaws (including the most dangerous ones that allow hackers to forge signatures). This proves the idea works.
They found a new bug: They discovered a new security issue in a library called LibTomCrypt that no one had reported before. This happened because the AI successfully built a house missing a specific part (the leading zero byte), and the library accepted it.
The Bottleneck is the AI, not the Plan: The researchers found that the "Mutator" (the machine breaking the blueprints) was doing a great job. The problem was entirely the AI's inability to stick to the broken rules.

The "Hallucination" Types

The researchers categorized how the AI failed, like a doctor diagnosing a patient:

The "Fixer" (Most Common): The AI saw a broken rule (like "padding must be less than 16 bytes") and thought, "That's impossible," so it silently fixed it back to the normal rule.
The "Math Whiz Who Forgot Math": The AI tried to follow the rules but messed up the simple math (like calculating how much padding to add), resulting in a house that was the wrong size.
The "Ignore": The AI completely ignored the broken part of the blueprint and built a standard house.

The Bottom Line

This paper shows that using AI to help test computer security is promising but currently unreliable.

The AI is great at writing code that runs (it doesn't crash), but it is very bad at writing code that means what you said. It has a habit of "correcting" your intentional mistakes because it thinks it knows better.

The researchers conclude that if you want to use AI for this kind of testing, you can't just trust the code it writes. You have to have a second layer of checking to make sure the AI actually followed your specific, broken instructions and didn't just "fix" them back to normal. Until then, the AI is a helpful intern who is very eager to please but often ignores your specific orders to do things the "right" way.

Technical Summary: Evaluating the Effectiveness of LLMs in Aiding Compliance Testing of PKCS#1-v1.5

Problem Statement

Testing binary protocol implementations for specification compliance requires generating inputs that satisfy both structural constraints (e.g., Type-Length-Value encoding, hierarchical nesting) and semantic constraints (e.g., length-value consistency, padding rules). Purely random generation is insufficient for exploring semantically meaningful behaviors in complex protocols like PKCS#1 v1.5. Conversely, existing domain-specific tools (e.g., Morpheus) require deep protocol expertise and significant manual effort to construct formal models, limiting their generalizability. General-purpose fuzzers lack semantic awareness, making them unable to systematically test specification compliance.

This work investigates whether grammar-level mutation combined with Large Language Model (LLM)-based code synthesis can serve as a viable, generalizable approach to specification compliance testing. Specifically, it asks if an LLM can reliably translate mutated formal grammars (targeting both structural rules and semantic constraints) into executable input generators that expose specification violations in cryptographic libraries.

Methodology

The authors designed a four-stage pipeline to evaluate this approach on the PKCS#1 v1.5 signature verification scheme, a widely deployed standard with a formally verified testing oracle (Morpheus).

Grammar Representation: A grammar describing PKCS#1 v1.5 was manually constructed from RFC 8017 in Backus-Naur Form (BNF), augmented with semantic constraints (arithmetic and relational expressions). This includes production rules for the TLV structure and constraints enforcing padding lengths and total message sizes.
Grammar Mutation: A mutator operates on the grammar tree to produce $N$ $N$ structurally distinct variants. The authors designed 13 mutation operators across three categories:
- Structural (TLV-Ignorant): Modifies composition or values without regard to TLV relationships (e.g., remove_component, swap_order, add_garbage).
- Structural (TLV-Aware): Modifies TLV components while preserving internal length-value consistency (e.g., change_length_change_value).
- Constraint Mutations: Targets semantic constraints directly (e.g., remove_constr, flip_signs, exchange_subexpressions).
  The process uses an adaptive algorithm to maintain diversity, increasing mutation intensity if duplicates are detected.
LLM-Based Code Synthesis: Each mutated grammar is serialized into a prompt for an LLM (OpenAI GPT-5-nano), instructing it to generate a standalone Python script that produces binary test cases conforming to the mutated specification. If the script fails to execute, an error traceback is fed back to the LLM for repair in a bounded loop.
Test Case Generation & Evaluation: The driver executes the generated scripts to produce test cases, which are run against 48 cryptographic library implementations. The results are compared against the Morpheus oracle to detect specification violations (Signature Forgery, Minor Leniency, Buffer Overflow, Incompatibility).

Key Contributions

Empirical Investigation: A systematic evaluation of grammar-level mutation combined with LLM code synthesis for binary protocol compliance testing, instantiated through 13 mutation operators across structural and constraint dimensions.
Reproduction of Known Vulnerabilities: Evidence that the approach reproduces 10 of 13 (76.9%) non-trivial violation categories identified by Morpheus, including all 5 signature forgery categories, across 48 implementations.
Discovery of New Discrepancies: Identification of a previously unreported discrepancy in LibTomCrypt v1.18.2 regarding the acceptance of missing leading bytes in PKCS#1 v1.5 structures.
Hallucination Taxonomy: A quantitative characterization of LLM hallucination in specification-constrained code generation. The study identifies five distinct hallucination types and reveals a systematic variation in their distribution across mutation categories.

Results

Compliance Testing Effectiveness

Reproduction Rate: The pipeline successfully reproduced 10 out of 13 known violation categories (76.9%). Crucially, it reproduced all 5 signature forgery categories, which are the most security-critical.
New Findings: The approach uncovered a new discrepancy in LibTomCrypt (and its derivative CryptX) where the library accepted inputs missing the leading 0x00 byte, a violation of RFC 8017. This was triggered by the remove_component operator, demonstrating that grammar-level mutations can explore input regions missed by combinatorial approaches.
Missed Violations: Three violation categories (ML#2, ML#5, ML#7) were not reproduced. Analysis confirmed these were not due to limitations in the mutation operators but were caused by LLM hallucination, where the generated scripts failed to faithfully implement the mutated grammar.

LLM Reliability and Hallucination

The study reveals a striking gap between operational reliability and semantic fidelity:

Operational Reliability: 99.8% of generated scripts executed successfully (96.1% on the first attempt, 3.7% after repair).
Semantic Fidelity: Only 17.5% of scripts correctly implemented the mutated specification. 82.5% exhibited some form of hallucination.

Hallucination Taxonomy:

H1 (Padding Miscalculation, 26.8%): Correctly implements the mutation but computes padding length incorrectly (e.g., using hardcoded values instead of deriving it from total length).
H2 (Mutation Fully Ignored, 1.1%): Produces standard-compliant structures despite the mutated grammar, overriding the specification with prior knowledge.
H3 (Partial/Contradictory, 29.3%): Partially implements the mutation but drops constraints because the mutated grammar contains contradictions (e.g., conflicting length and padding constraints).
H4 (Partial/No Reason, 18.0%): Partially implements the mutation despite the grammar being satisfiable, ignoring specific constraints without justification.
H5 (Degenerate Output, 7.1%): Produces random strings with no structural resemblance to the grammar.

Correlation with Mutation Types:

Constraint-only mutations had the highest correctness rate (30.3%) but also the highest rate of being fully ignored (H2, 8.1%).
Structural (TLV-ignorant) mutations had the highest rates of H3 (32.4%) and H4 (21.5%).
Mixed mutations (combining structural and constraint operators) showed the lowest correctness (4.8%).

Significance and Claims

The paper claims that grammar-level mutation combined with LLM code synthesis is a viable approach for specification compliance testing that reduces the need for deep domain-specific engineering. It successfully reproduces the majority of known critical vulnerabilities and can discover new discrepancies.

However, the primary contribution is the identification of LLM semantic fidelity as the primary bottleneck, rather than the mutation strategy. The authors emphasize that high operational success rates (99.8%) mask low semantic correctness (17.5%), a gap that is difficult to detect without semantic analysis due to high output variation in hallucinated scripts.

The findings provide actionable guidance for future tools:

H3 (Contradictory Grammars) can be mitigated by pre-synthesis satisfiability checks.
H4 (Unexplained Deviations) represents an irreducible reliability issue requiring post-generation verification.
H1 (Arithmetic Errors) reflects a general weakness in LLMs regarding multi-step arithmetic derivation.

The authors conclude that any approach using LLMs to generate code from formal specifications must contend with this fidelity gap, and that operational metrics alone are insufficient for assessing the effectiveness of such testing pipelines.