Ämne: Re: [dcdev] adc |
Från: eric |
Datum: 2004-01-22 7:15 |
Till: Direct Connect developers <[email protected]>, [email protected] |
Such protection would be necessary, as
http://www.cs.rice.edu/~scrosby/hash/slides/USENIX-RegexpWIP.2.ppt shows
that even removing backrefs entirely doesn't immunize a RE engine from
attack. 400,000 lines requiring 0.25 seconds would suggest that, for
example, 100,000 lines requires 0.0625 seconds, which allows only 16
searches per second before one reaches 100% CPU usage. Even your example of
0.05 seconds allows only 20/second. I don't want a DC client I run
monopolizing near that much CPU time.
Another factor you haven't mentioned is your CPU: what is it?
As I demonstrated above, not without special support from the RE engine;
that 24-way or'd expression is going to be noticeably slower than the
semantically equivalent multiple substring search. The Perl5 method should
be similar in speed, but requires an NFA RE implementation exhibiting
unbounded-time behaviour and thus potentially vulnerable to the attacks
described above.
Finally, using regular expressions inhibits one from applying many
potential search optimizations, such as Bloom filters (used in Gnutella as
the QRP, or Query Routing Protocol) and suffix array-assisted searches. A
histogram of the speed results of the latter is at
http://opennavel.dnsalias.org/~fusbar/cologic/bmratio2.png ; the y axis
represents how many searches (out of approximately 20,000 total) were
faster or slower under that scheme than DC++'s default search by the
(inverse of natural log of) the x-axis value.