Performance issue with large A and AAAA answers

[darkk]

dns.Set code is O(n^2) and it may be bad for some use-cases.

One of automation toolkits feeding Roskomnadzor blacklist into tables of network equipment uses berserker_resolver module that relies on dnspython. dnspython itself uses significant amount of CPU while handling replies with large amount of RRs. Flame graph suggest that the reason of major slowdown is non-cached to_digestable() calls that can't be easily made cached due Rdata class being mutable.

Attacker controlling some small number of "blacklisted" domains may cause significant consumption of CPU by automation toolkit and make the toolkit miss deadlines.

Following test against dnspython==1.15.0 shows non-linear increase of runtime (172.19.0.53 is address of my pdns_recursor):

for i in 125  250 500 1000 2000 4000; do
  dig -t A $i.rnd.darkk.net.ru @172.19.0.53 >/dev/null # fill cache
  time python2.7 -c 'from dns import resolver; r = resolver.Resolver(); r.nameservers = ["172.19.0.53"]; print len(r.query("'${i}'.rnd.darkk.net.ru", "A"))'
done

len(answer)	user time
125	0m0.120s
250	0m0.332s
500	0m1.400s
1000	0m4.420s
2000	0m21.064s
4000	1m22.964s

Same is true for AAAA queries:

len(answer)	user time
125	0m0.168s
250	0m0.448s
500	0m1.672s
1000	0m6.036s
2000	0m25.664s

[pspacek]

Generic problem is that changing Sets to immutable is a major API change

[wheelerlaw]

Couldn't we just change the dns.Setto be a proxy for a Python set?

[rthalley]

We haven't just changed to the Python set because that would require that rdata be immutable to be safe, as otherwise the hash could change. We're pondering what to do still.

[rthalley]

This is fixed by the new set code.