Certificate parsers, which are critical components of Secure Sockets Layer or Transport Layer Security (SSL/TLS) implementations, parse incomprehensible certificates into comprehensible inputs to certificate validators and humans. Thus, certificate parsers profoundly affect decision-makings of validators and humans, which in turn affect security. To guarantee the correctness of certificate parsers, an approach for search-based differential testing of certificate parsers, namely SBDT, is put forward. SBDT begins with modeling certificate structures, mutation operations, and bounds. Based on the initial model, SBDT searches for the most promising model node and mutation operator that trigger discrepancies, and generates a certificate from the node and operator it finds. Then, SBDT feeds the certificate to certificate parsers, and searches for multiple types of discrepancies after normalizing the results output by parsers. Distinct discrepancies are employed as feedback to update and prune the model. SBDT starts the next iteration from the updated and pruned model, unless all nodes and mutation operators have been pruned due to reaching their upper bounds. Our work has the following contributions: (1) To the best of our knowledge, this is the first time that testing of certificate parsers has been clearly distinguished from testing of certificate validators, which will facilitate accurate testing of certificate parsers and validators; (2) SBDT is the first systematic and efficient approach for differential testing of certificate parsers by searching, updating, and pruning models; and (3) We have implemented an open-source prototype tool of SBDT, and experimental results show that SBDT is effective and efficient in finding new bugs and enhancements of certificate parsers.