Toward Principled LLM Safety Testing: Solving the Jailbreak Oracle Problem

Computer Science > Cryptography and Security [Submitted on 17 Jun 2025 (v1), last revised 24 Apr 2026 (this version, v2)] Toward Principled LLM Safety Testing: Solving the Jailbreak Oracle Problem Shuyi Lin, Anshuman Suri, Alina Oprea, Cheng Tan As large language models (LLMs) become increasingly deployed in safety-critical applications, the lack of systematic methods to assess their vulnerability to jailbreak attacks presents a critical security gap. We introduce the jailbreak oracle problem: given a model, prompt, and decoding strategy, determine whether a jailbreak response can be generated with likelihood exceeding a specified threshold. This formalization enables a principled study of jailbreak vulnerabilities. Answering the jailbreak oracle problem poses significant computational challenges, as the search space grows exponentially with response length. We present Boa, the first system designed for efficiently solving the jailbreak oracle problem. Boa employs a two-phase search strategy: (1) breadth-first sampling to identify easily accessible jailbreaks, followed by (2) depth-first priority search guided by fine-grained safety scores to systematically explore promising yet low-probability paths. Boa enables rigorous security assessments including systematic defense evaluation, standardized comparison of red team attacks, and model certification under extreme adversarial conditions. Code is available at this https URL Comments: Accepted to MLSys 2026 Subjects: Cryptography and Security (cs.CR); Artificial Intelligence (cs.AI); Machine Learning (cs.LG) Cite as: arXiv:2506.17299 [cs.CR]   (or arXiv:2506.17299v2 [cs.CR] for this version)   https://doi.org/10.48550/arXiv.2506.17299 Focus to learn more Submission history From: Anshuman Suri [view email] [v1] Tue, 17 Jun 2025 20:37:29 UTC (358 KB) [v2] Fri, 24 Apr 2026 04:36:54 UTC (785 KB) Access Paper: HTML (experimental) view license Current browse context: cs.CR < prev   |   next > new | recent | 2025-06 Change to browse by: cs cs.AI cs.LG References & Citations NASA ADS Google Scholar Semantic Scholar Export BibTeX Citation Bookmark Bibliographic Tools Bibliographic and Citation Tools Bibliographic Explorer Toggle Bibliographic Explorer (What is the Explorer?) Connected Papers Toggle Connected Papers (What is Connected Papers?) Litmaps Toggle Litmaps (What is Litmaps?) scite.ai Toggle scite Smart Citations (What are Smart Citations?) Code, Data, Media Demos Related Papers About arXivLabs Which authors of this paper are endorsers? | Disable MathJax (What is MathJax?)