Testing Certificate Authorities: An Empirical Study and Stateful Fuzzing Approach

Certificate Authorities (CAs) form a critical component of the web PKI, implementing standardized, stateful workflows for account management, domain validation, certificate issuance, and revocation. Many modern CAs rely on the ACME (Automatic Certificate Management Environment) protocol to automate domain validation and certificate management at scale, supported by related standards such as OCSP (Online Certificate Status Protocol) and CRLs (Certificate Revocation Lists). Although ACME is formally verified for protocol-level correctness [1], real-world CA implementations continue to exhibit behavioral inconsistencies, and correctness issues in practice [2], [3].

These observations raise a fundamental question: how well are CA implementations tested, and do developer-written tests adequately exercise protocol-defined behavior? This paper presents the first empirical study of testing quality of ACME-compliant CAs. We analyze four widely used opensource CA implementations (Boulder, Vault, Smallstep, and Xipki), examining developer-written tests across unit, integration, and end-to-end levels, and measure how effectively they exercise the externally observable certificate management operations defined in the ACME, OCSP, and CRL specifications.

Our study shows that developer-written test suites provide limited protocol coverage, with substantial gaps in stateful workflows and specificationdefined error-handling logic, and that regression tests are rarely added when protocol bugs are fixed. To address these gaps, we introduce CAFUZZ, a protocol-aware stateful black-box test generator that derives behavioral models from RFC specifications and systematically tests CA behavior. CAFUZZ achieves 100% protocol operation coverage and 100% protocol error coverage across four CA implementations, compared to 39.5% and 25.6% for developer-written tests, while also improving code coverage from 15.5% to 37.3%.

Beyond coverage improvements, CAFUZZ detected 3 previously unknown bugs and 43 known protocol-related bugs when replaying historical buggy versions. These results demonstrate that specification-guided, stateaware test generation can effectively improve protocol coverage and expose real-world compliance issues that developer-written tests fail to detect.