TL;DR
SMTrap introduces a highly cost-effective, model-feedback-free Denial-of-Service (DoS) attack paradigm against Large Reasoning Models (LRMs). By using cheap, CPU-side symbolic solver conflict counts as a proxy for combinatorial difficulty, it synthesizes benign-looking logic puzzles that force LRMs into extensive trial-and-backtracking loops. This "search amplification" exhausts the model's token budget and computational resources at near-zero cost to the attacker.
What Problem Does This Paper Address?
Modern Large Reasoning Models (LRMs)—such as DeepSeek-R1 or OpenAI's o1/o3 series—rely on generating long Chain-of-Thought (CoT) trajectories to solve complex problems. This introduces a severe computational asymmetry: a very short user query can trigger thousands of tokens of internal reasoning on the provider's side. Attackers can exploit this to launch LRM-Denial-of-Service (LRM-DoS) attacks to exhaust provider resources.
However, existing black-box DoS attacks are highly inefficient. They either require iteratively querying the target model to optimize prompt perturbations or training an expensive surrogate model via reinforcement learning. This heavy reliance on model feedback means attackers must spend significant GPU compute time just to craft an attack payload, severely weakening their adversarial leverage. SMTrap addresses this gap by generating highly disruptive queries completely offline, without any model queries or GPU training.
Methods
The core innovation of this paper is search amplification. The authors discovered a fascinating parallel between symbolic Satisfiability Modulo Theories (SMT) solvers and neural LRMs: when forced to solve Constraint Satisfaction Problems (CSPs) like Sudoku or Zebra puzzles, both systems rely on a similar trial-and-backtracking process. They propose assignments, check constraints, hit contradictions, and revise failed branches.
SMTrap leverages this insight through a lightweight, CPU-only framework:
- CSP Initialization: It starts with a valid, fully solved CSP instance and randomly hides clues to create an initial puzzle state.
- Clue State Branching and Pruning: It iteratively modifies the puzzle by adding and removing clues, exploring neighboring puzzle configurations while strictly maintaining unique solvability.
- Conflict-Guided Acceptance: Each candidate puzzle is encoded as an SMT formula and run through the Z3 solver on a CPU. SMTrap tracks the solver's internal conflict count and greedily selects the puzzles that cause the most solver conflicts.
- Shortcut Suppression: To prevent web-facing LRMs from simply executing Python code to solve the puzzle, SMTrap appends strict system prompts instructing the model to reason purely manually, step-by-step.
Datasets
The authors evaluated SMTrap by synthesizing hard instances of two classic CSP families:
- Sudoku: Standard 9×9 grids.
- Zebra Puzzles: Logic grid puzzles scaled to 9 houses and 9 attribute categories.
- Graph Coloring: Used as a secondary task to demonstrate generalization.
These generated puzzles were tested against seven frontier LRMs (including Claude-Opus-4.7, GPT-5.5, Gemini-3.1-pro, and DeepSeek-v4-pro) via APIs and official web interfaces. SMTrap was compared against state-of-the-art DoS baselines (AutoDoS, CatAttack, and ReasoningBomb) as well as static human-designed stress tests (Sudoku-Bench and Pencil Puzzle Bench).
Key Insights and Ideas
- Symbolic-Neural Behavioral Alignment: Despite completely different underlying architectures, SMT solvers and LRMs scale similarly in response to combinatorial pressure. A high conflict count in Z3 reliably predicts extensive natural-language backtracking in an LRM.
- Task-Side vs. Prompt-Side Optimization: Instead of trying to optimize surface-level prompt wording or adversarial triggers, it is far more effective to optimize the intrinsic mathematical difficulty of the task itself.
- Asymmetric Leverage: SMTrap shifts the computational burden entirely. The attacker uses negligible CPU cycles (seconds) to generate a puzzle that forces the victim's massive GPU clusters to grind for minutes.
Key Results
- State-of-the-Art Token Exhaustion: In API evaluations, SMTrap-Zebra achieved an average of 76,362 completion tokens across seven frontier models, outperforming the strongest baseline (AutoDoS) by 2.74×.
- Extreme Web Delays: On official web interfaces, SMTrap forced models into massive over-reasoning loops. SMTrap-Sudoku caused GPT-5.5 to reason for 314.97 seconds (an 8.67× amplification over baselines), while SMTrap-Zebra forced GPT-5.4 to grind for over 21 minutes (1,308.33 seconds).
- Negligible Synthesis Cost: SMTrap generated these high-impact payloads on a standard desktop CPU (Intel Core Ultra 9) in just 35 to 46 seconds on average.
- High Stealthiness: SMTrap achieved an 83.33% stealthiness rate against a GPT-4o-based malicious prompt detector, as the queries look like entirely benign, standard logic puzzles.
- Effective Mitigation: The authors demonstrated that routing recognized CSP queries to a local symbolic solver via tool-calling (and returning the direct output) successfully neutralized the attack, reducing LRM token consumption by 90.15% on average.
Limitations and Future Work
While highly effective, the authors note that SMTrap is currently focused on structured, CSP-style reasoning tasks that easily map to SMT formulas. It does not cover all possible forms of LRM resource-amplification vulnerabilities. Furthermore, Z3 conflict counts are highly dependent on the specific SMT encoding and solver heuristics used, meaning it isn't a universal metric of combinatorial hardness.
Future work includes exploring how this symbolic search pressure applies to broader, less structured reasoning domains, and investigating how changing solver heuristics impacts LRM behavior.
Summary updated