5 ms·

So I've always been curious, does anybody have a writeup of how DNS servers like unbound etc are able to handle evaluating these massive blocklists? Like the al

by gh02t 4y ago

So I've always been curious, does anybody have a writeup of how DNS servers like unbound etc are able to handle evaluating these massive blocklists? Like the algorithms and data structures they use to evaluate queries against these lists efficiently. My pfsense+pfblocker unbound instance has something like 400K hosts blocked and I've always been amazed that it doesn't even break a sweat scanning that many hosts with every query.

dsr_ 4y ago
Here's Tony Finch's discussion of the data structures he's working on for ISC's BIND: https://dotat.at/prog/qp/README.html https://dotat.at/prog/qp/README.html
justsomehnguy 4y ago
> My pfsense+pfblocker unbound instance has something like 400K hosts blocked But it is not 400k hosts to search: com facebook www ad google ad ads notadswepromise googletagmanager tags ads to block ad.facebook.com you only need to scan 10-100k of .com domains in your block list and only a couple of records in facebook.com. Don't forget, DNS is a hierarchical system. And we, humans, actually record, use and remember all the DNS records in the wrong, reverse direction ;-) > 400K hosts I bet 30% of those hosts are don't resolve anymore and another 30% resolve to domain parking/404 hosts. Eg: see my comment about "TOP 10M SITES" https://news.ycombinator.com/item?id=33150554 https://news.ycombinator.com/item?id=33150554
- LinuxBender 4y ago
  I bet 30% of those hosts are don't resolve anymore I've seen some evidence of this. I periodically dig all the blocked domains and noticed that some of them come and go so I assume people cycle them in and out to evade blocking. A handful of the domains just change the A record so I just block the apex domain which makes it a little harder to keep the block lists optimized but does reduce the size a little. I should add that blocking the apex of some domains includes risk of dropping legit traffic but if I see more than {n} badware domains on the apex, I write it off as compromised or at very least poorly implemented and poorly secured.
- deusum 4y ago
  I suspect parent meant the way the list is processed and how the structure resides in memory. We'd optimally want, e.g., aaa.ai to resolve as fast as zzz.zx. If we just loaded the file for every query and ran down the list linearly we'd probably see a large disparity with the former being much quicker than the latter. So, the question would be: how is it done in an efficient way? Is it loaded into a btree, is each domain broken into various parts, are certain domains prioritized, threading, compression? Plus, there's the queries for dns updates, and how the results get integrated.
  - sph 4y ago
    Some combination of tries, B-trees and Bloom filters would get you most of the way there.
bluedino 4y ago
https://news.ycombinator.com/item?id=20148457 https://news.ycombinator.com/item?id=20148457 Not sure how out of date that is

by gh02t 4y ago

dsr_ 4y ago

Here's Tony Finch's discussion of the data structures he's working on for ISC's BIND: https://dotat.at/prog/qp/README.html https://dotat.at/prog/qp/README.html

justsomehnguy 4y ago

> My pfsense+pfblocker unbound instance has something like 400K hosts blocked But it is not 400k hosts to search: com facebook www ad google ad ads notadswepromise googletagmanager tags ads to block ad.facebook.com you only need to scan 10-100k of .com domains in your block list and only a couple of records in facebook.com. Don't forget, DNS is a hierarchical system. And we, humans, actually record, use and remember all the DNS records in the wrong, reverse direction ;-) > 400K hosts I bet 30% of those hosts are don't resolve anymore and another 30% resolve to domain parking/404 hosts. Eg: see my comment about "TOP 10M SITES" https://news.ycombinator.com/item?id=33150554 https://news.ycombinator.com/item?id=33150554

LinuxBender 4y ago
I bet 30% of those hosts are don't resolve anymore I've seen some evidence of this. I periodically dig all the blocked domains and noticed that some of them come and go so I assume people cycle them in and out to evade blocking. A handful of the domains just change the A record so I just block the apex domain which makes it a little harder to keep the block lists optimized but does reduce the size a little. I should add that blocking the apex of some domains includes risk of dropping legit traffic but if I see more than {n} badware domains on the apex, I write it off as compromised or at very least poorly implemented and poorly secured.
deusum 4y ago
I suspect parent meant the way the list is processed and how the structure resides in memory. We'd optimally want, e.g., aaa.ai to resolve as fast as zzz.zx. If we just loaded the file for every query and ran down the list linearly we'd probably see a large disparity with the former being much quicker than the latter. So, the question would be: how is it done in an efficient way? Is it loaded into a btree, is each domain broken into various parts, are certain domains prioritized, threading, compression? Plus, there's the queries for dns updates, and how the results get integrated.
- sph 4y ago
  Some combination of tries, B-trees and Bloom filters would get you most of the way there.

bluedino 4y ago

https://news.ycombinator.com/item?id=20148457 https://news.ycombinator.com/item?id=20148457 Not sure how out of date that is