For each of a number of naming deviation types, the number of deviations within a domain name of a domain is determined. Each naming deviation type is a different type of deviation from domain name naming rules. For each naming deviation type for which the number of deviations is non-zero, first benign and malicious probabilities that benign and malicious domains, respectively, have the naming deviation type are estimated. Second benign and malicious probabilities that any given domain is respectively benign and malicious are estimated. Probabilities that the domain is benign and malicious are estimated based on the number of deviations for each naming deviation type and based on the estimated first and second benign and malicious probabilities. Whether the domain is benign or malicious is determined based on the estimated probabilities that the domain is benign and malicious.