A technique includes processing domain name system queries generated by a host to identify a subset of the queries for which domain names were not resolved. The technique includes using a time-based analysis to detect domain generation algorithm-based malware communications by the host, including detecting malicious communications by the host based at least in part on a number of the queries of the identified subset and a time span within which the queries of the subset were generated.