_gnutls_hostname_compare: exponential slowdown with multiple wildcards

[Kalle Olavi Niemitalo]

I tried a few _gnutls_hostname_compare calls in GnuTLS 2.8.6.
The implementation in 2.10.5 is identical.

_gnutls_hostname_compare("*************a", 14, "bbbbbbbbbbbbbbb")
  returns 0 in 1 second.

_gnutls_hostname_compare("**************a", 15, "bbbbbbbbbbbbbbbb")
  returns 0 in 5 seconds.

_gnutls_hostname_compare("***************a", 16, "bbbbbbbbbbbbbbbbb")
  returns 0 in 15 seconds.

_gnutls_hostname_compare("****************a", 17, "bbbbbbbbbbbbbbbbbb")
  returns 0 in 63 seconds.

_gnutls_hostname_compare("*****************a", 18, "bbbbbbbbbbbbbbbbbbb")
  returns 0 in 243 seconds.

As you can see, the time grows exponentially as more characters
and wildcards are added.

I think the worst case of this function could be made a lot faster.
After a wildcard has been reached, there is never any need to
backtrack to a previous wildcard.  I'll probably implement such
an algorithm in ELinks, for use with OpenSSL.

Alternatively, I suppose you could just reject the whole pattern
if it has more than ten wildcards.  :)
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 197 bytes
Desc: not available
URL: </pipermail/attachments/20110504/17abbafb/attachment.pgp>