Systems and methods are disclosed for detecting covert DNS tunnels using n-grams. The majority of legitimate DNS requests originate from network content itself, for example, through hyperlinks in websites. So, comparing data from incoming network communications to a hostname included in a DNS request can give an indication on whether the DNS request is a legitimate request or associated with a covert DNS tunnel. This process can be made computationally efficient by extracting n-grams from incoming network content and storing the n-grams in an efficient data structure, such as a Bloom filter. The stored n-grams are compared with n-grams extracted from outgoing DNS requests. If n-grams from an outgoing DNS request are not found in the data structure, the domain associated with the DNS request is determined to be associated with a suspected covert DNS tunnel.