Using DNS query stream feedback to improve a DNSBL

Carl Byington
510 Software Group


Suppose we have an existing IPv4 DNSBL blackholes.example.com that is commonly used for spam filtering. It may contain entries such as: IN A

We can analyze the DNS query stream to detect new ip addresses used by spammers. We can then automatically add those new ip addresses to the DNSBL which improves the effectiveness of the DNSBL.


We have some DNS servers for this zone, and a population of client mail systems using this for spam filtering. AUTH is one of the authoritative servers for this zone. CLIENT is the ip address of some mail server using this zone for spam filtering. TARGET is the ip address of some system that has connected to CLIENT on port 25 and is trying to send email. CLIENTDNS is the ip address of a system running a recursive DNS resolver that is used by CLIENT for DNS resolution. CLIENT sends a query to CLIENTDNS for a name in our zone composed of the reversed IPv4 octets prepended to the zone name. CLIENTDNS either answers that query from cache, or sends that query to the authoritative servers for the zone, possibly including AUTH. IGNORE is a mostly static list of /24 blocks containing mail servers about which we expect to see a high volume of queries. These are blocks containing the outbound mail servers of Yahoo, Gmail, etc. IGNORERDNS is a corresponding list of reverse dns names of those machines in IGNORE.

Phase one - observe the query stream

tcpdump -s0 -vv -i $IFC -nn -l udp dst port domain

Running on AUTH, we use tcpdump to convert the binary DNS queries seen on the network interface into a text form. We now have a stream of text lines that contain CLIENTDNS and TARGET (encoded in the query name). In other words, we have a stream of (CLIENTDNS,TARGET) pairs, where each one represents some unknown number of queries from CLIENT machines that happen to use the same CLIENTDNS recursive resolver.

For any given CLIENTDNS machine, we don't know how many CLIENT mail servers are using it for DNS resolution. For any given query observed at AUTH, we don't know how many other such queries were answered by CLIENTDNS from cache. Our counts of such events, (CLIENTDNS,TARGET) pairs seen at AUTH, are not counts of email messages sent by any individual machine or even a group of machines.

We observe the query stream until we have collected 1M samples. Depending on the query rate, we sample every Nth query, trying to keep the sampled query rate no higher than 200 queries per second. So our 1M queries should cover about 90 minutes.

Phase two - compute statistics

We remove TARGETs that are in IGNORE. For each remaining (CLIENTDNS,TARGET) pair in our sample, we use the GeoIP database to determine if both are in the same country, or if this is a cross border query. TARGET24 is the /24 network containing TARGET. For each TARGET and TARGET24 in the sample, we compute:

Phase three - filtering

We look at the top 50 TARGET24s ordered by their QUERIES, where their CLIENTS count is greater than 25. If (QUERIES > 200) or (CLIENTS > 50) or (CROSS > 70%) we add the TARGET24 to our inspection list.

We look at the top 50 TARGETS ordered by their QUERIES, where their CLIENTS count is greater than 25. If (RDNS is in IGNORERDNS) and (CROSS < 30%), we add the enclosing TARGET24 and RDNS to our IGNORE list. For example, we are already ignoring /24 blocks of gmail servers, and we see a new /24 with a high volume of queries, but the reverse dns name indicates this is gmail again, so we update our IGNORE lists. Otherwise, we add the TARGET to our inspection list.

Phase four - neighborhood inspection

For each /24 on our inspection list, we look at sendmail logs for the current week to see if we have ever received a mail delivery attempt from any ip address in that /24 where the MAIL FROM domain name was already listed on the DBL, SURBL or URIBL lists. If so, those ip addresses get added to our inspection list.

For each /24 on our inspection list, we have a lower and upper bound on the range of addresses in that /24 that we will inspect. If we find any evidence of spam in that range, we expand the range in both direction by 10 ip addresses, and then expand again to the smallest containing CIDR block. If we find any evidence of spam in the expanded range, we expand it again. The final range is the smallest CIDR containing all ip addresses in that /24 for which we have found some evidence of spam. If that CIDR is not empty, we can add it to our DNSBL.

Single IP address detailed inspection

Some of the tests of an ip address involve its reverse dns name, shortened to the effective TLD plus one component. For example, a name like a.b.c.example.com would be shortened to example.com. In the following we use RDNS for the full reverse dns name, and SRDNS for the shortened reverse dns name.

We consider an ip address to be spammy for any of the following:

SPF processing

As part of the investigation of an ip address, we may discover a name that is listed on any of the DBL, SURBL and URIBL lists. For such names, we look for a TXT v=spf1 record, and if found we add the ip addresses from that record to our inspection list. Some spammers are nice enough to tell us what ip addresses they will use to send more spam.