Modern network security rests on the Secure Sockets Layer (SSL) and Transport Layer Security (TLS) protocols. Distributed systems, mobile and desktop applications, embedded devices, and all of secure Web rely on SSL/TLS implementations such as OpenSSL, NSS, CyaSSL, GnuTLS, PolarSSL, MatrixSSL, etc. for protection against active and passive network attacks. This protection critically depends on whether SSL/TLS clients correctly validate the X.509 certificate presented by the server during the SSL/TLS handshake protocol. Certificate validation is extremely complex, involving dozens of checks on various certificate constraints, extensions, certificate authorities, etc. We design, implement, and apply the first methodology for large-scale adversarial testing of certificate validation logic in SSL/TLS implementations. Our first contribution is 'frankencerts', synthetic certificates randomly mutated from parts of real certificates. By construction, frankencerts include unusual combinations of extensions, constraints, and certificate authorities, rare and malformed extension values, etc. Testing SSL/TLS implementations with millions of frankencerts elicits behaviors that do not manifest during conventional testing. Our second ingredient is differential testing: if one SSL/TLS implementation accepts a certificate while another rejects the same certificate, one of them must be wrong. We use such discrepancies as an oracle for finding flaws in individual implementations. Testing with frankencerts uncovered many serious vulnerabilities in SSL/TLS implementations. For example, any server with a valid X.509 version 1 certificate (we observed thousands of such certificates 'in the wild') can act as a rogue certificate authority and issue fake certificates for any domain, enabling man-in-the-middle attacks against MatrixSSL. Another, very subtle bug causes GnuTLS, too, to unintentionally accept rogue version 1 certificate authorities. GnuTLS also accepts certificate authorities created by issuers who are not authorized to create such authorities. Code signing certificates, not intended for server authentication, are accepted by GnuTLS, CyaSSL, and PolarSSL. Our differential mutation testing discovered a total of 208 discrepancies between SSL/TLS implementations. We also found serious vulnerabilities in how SSL/TLS implementations and Web browsers warn users about certificate validation errors. When presented with an expired, self-signed certificate, NSS, Safari, and Chrome (on Linux) report that the certificate has expired — a low-risk, often ignored error — but not that the connection is insecure against a man-in-the-middle attack. These results demonstrate that automated adversarial testing with frankencerts is a powerful methodology for discovering deep security flaws in SSL/TLS implementations.