VW resistance to algorithmic complexity attacks?
Locked
Re: VW resistance to algorithmic complexity attacks?
 
|
On 1/5/2012 11:48 PM, Jon Paynter wrote:
That would handle merely one collection that is exposed. It assumes the use of Seaside and web requests. I envisage this attack would work with *any* hashed collection open to manipulation by mutually distrustful users of a system (not necessarily web based). R -
_______________________________________________ vwnc mailing list [hidden email] http://lists.cs.uiuc.edu/mailman/listinfo/vwnc |
Re: VW resistance to algorithmic complexity attacks?
|
|
Re: VW resistance to algorithmic complexity attacks?
|
|
In reply to this post by Reinout Heeck-2
Or, as I suggested
previously and Travis re-suggested. Don't use hashing. These are all
strings. Use a sorted collection with binary search or a search tree. No
pathological worst-cases to exploit.
_______________________________________________ vwnc mailing list [hidden email] http://lists.cs.uiuc.edu/mailman/listinfo/vwnc |
Re: VW resistance to algorithmic complexity attacks?
|
|
On Mon, Jan 9, 2012 at 11:32 AM, Alan Knight <[hidden email]> wrote:
Bar a huge quantity of strings, which was where I pitched in at the beginning. Surely one wants to limit the stress a request can put on a server? If one puts a bound on request size and/or complexity then in this example hashed collections could work better than search trees. But if one doesn't protect against overload both approaches are vulnerable, no?
best, Eliot _______________________________________________ vwnc mailing list [hidden email] http://lists.cs.uiuc.edu/mailman/listinfo/vwnc |
Re: VW resistance to algorithmic complexity attacks?
|
|
Re: VW resistance to algorithmic complexity attacks?
|
|
In reply to this post by Eliot Miranda-2
No, a huge quantity of
strings doesn't make any difference. Well, it's slower than handling a
small quantity of strings, but if you do it with a hash table it's
orders of magnitude worse, because hash tables have bad worst-case
performance and we're assuming an adversary who is deliberately
provoking the worst case. Trees (if balanced) or sorted collections will
work roughly the same regardless of the specifics of the input. A
billion strings will be very roughly 20 million times worse than a
thousand strings, but they won't be a quadrillion times worse.
Filtering out things with a billion post variables in the first place is also not a bad idea, but as Michael points out, probably faster and more reliably done at the front-end before the application has to deal with it.
_______________________________________________ vwnc mailing list [hidden email] http://lists.cs.uiuc.edu/mailman/listinfo/vwnc |
Re: VW resistance to algorithmic complexity attacks?
|
|
In reply to this post by Steven Kelly
Thanks Steven. Hashed collections that use physical buckets are better when collections are long-lived or very large. The VW collections (with logical buckets) are faster
to create and dispose of. I'd implemented and shared physical bucket designs a dozen different ways. I'd be surprised if that Cincom resolution didn't have my name associated with a resolution like you've mentioned. Approaches that increase the hash range
won out. The need for faster implementations becomes even more limited once you have that. Some big performance problems with Store caches could have been fixed with a better hash collection design. Those store-specific performance problems had been reported
to Cincom but I recall they believed that their redesign of Store would address those problems. Here is an answer for the main topic: >> Question 2: can we generically counter such an attack? Yes. With a change to one method that actually increases performance. A generic fix would need to work when there are fewer hash buckets than hash values (like when indexing 28-bit string hash values to a 100 position hash table)
and when there are more hash buckets than hash values (like with 14-bit identityHash).
"Default" #(0.333333 1.0 #(3->5461)) "table was 33% of hash value range; distribution range was 100% of hash value; distribution was even" #(1.74998 1.0 #(1->16383)) "table was 175% of hash value range; distribution range was 100% of hash value; distribution was even" The goal we'd want for these numbers is for the first to test to stay " #(0.333333 1.0 #(3->5461))" and for the second test to increase the second column (to
be above 1.0) and the number of pairs shown in the third column. String>>hash is said to answer a 28-bit value. SmallInteger maxBits is 29. Variance (that still has SmallInteger efficiency) can be added by shifting the bits
up 1 (or multiplying the hashValue by 2). " bitShift: 1 " #(0.333333 1.0 #(3->5461)) #(1.74998 1.14287 #(1->12287 2->2048)) It is resistant to an algorithmic complexity attack when the maximum hash value is greater than the number of buckets (which would always be the case with strings).
There is still a even distribution when there are fewer buckets than hash values. When there are more buckets than hash values then the distribution is into 14% more index positions than there were hash values. A meaningful variance is created and average
bucket size was lower. This trick increases the variance of all the hash values such that VW hashing is more efficient even when constrained to the traditional VW 14-bit identityHash value. I've added the implementation to the latest version (currently 1.6) of ICXVwHashTuning. If you want to give it a try then load version 1.6 (or later) and then
read the Set class>>hashTuning_documentation method. Thanks for the kind words. Regards, Paul Baumann From: Steven Kelly [mailto:[hidden email]]
Thanks Paul, I always learn something new from your posts! I just spotted VW support Resolution 100401, which “implements Dictionaries using buckets to resolve
hash collisions”. The resolution talks about improving the performance of finalization, which uses IdentityDictionary and is subject to the consecutive slot problem. It looks like the resolution just provides the new Dictionary classes, without actually changing
existing code to use them. Hopefully still some use to others, and maybe a foundation to build on for a future solution integrated in VW – e.g. to replace IdentityDictionary. All the best, Steve From: [hidden email] [mailto:[hidden email]]
On Behalf Of Paul Baumann >> I lack the time to parse this in relation to VW Sorry, but the explanation I'd give for how this relates to VW will take longer to parse... :) Hash collisions typically happen due to a combination of hash range and hash table size. The smallest of either of these typically determines the number of
collisions; however, VW is different. The example in the document shows a hash->bucket design in which the hash value is used to find a sequence that is slowly searched. The attack is to add unequal
objects of equal hash value to maximize the amount of linear search and growth in each hash bucket. An example of hash->bucket implementation in VW is the class-side behavior Symbol uses to intern strings. The trick would also be to minimize the hash variance
of the data added to reduce the chance that a rehash will increase the size of the hash table and that distribution into buckets will not be improved once the hash table size is increased.
VW hashed collections have logical hash buckets with search indexes that are determined by the size of the hash table. VW grows the ENTIRE hash table after
an addition when #fullCheck notices there are less than 25% free slots. VW uses the hash value as a starting point for doing a linear search that is limited only by the discovery of a nil slot or equal object. VW is more affected by the distribution of empty
slots than it is by hash table size. VW needs to have the free slots because without them the #find*OrNil: methods would have the cost of searching an increasing percentage of the hash table as items are added. The free slots serve as a stop that a separate
physical bucket would normally provide. This is more costly (like #fixCollisionsFrom:) than a physical hash bucket design that can manage buckets individually. VW attempts to expand the distribution range in methods like #initialIndexFor:boundedBy:, but that
would have little benefit when there are many equal hash values for unequal objects. VW has the linear search costs that the attack exploits, searches more than once for some operations, has a larger scope of growth, and searches through objects that would
otherwise belong to another bucket. The VW implementation would be more susceptible to a hash collision attack than the hash->bucket design that the document describes how to exploit. "This artificially forces a highly saturated hash table to simulate lookup cost alone that could be incurred with a hash collision attack ." | normalSet normalResults slowerSet slowerResults notIncluded | normalSet := Set new: Symbol tableSize. notIncluded := Set new: Symbol tableSize. Symbol table size to: 1 by: -1 do: [:bucketIndex |
(bucketIndex < 6 ifTrue: [notIncluded] ifFalse: [normalSet])
addAll: (Symbol table at: bucketIndex). ]. notIncluded := notIncluded asArray. normalResults := Array
with: normalSet basicSize
with: normalSet size
with: (normalSet basicSize / normalSet size) asFloat
with: (Time millisecondsToRun: [10 timesRepeat: [notIncluded do: [:ea | normalSet includes: ea]]]). slowerSet := normalSet copyEmpty: normalSet size + 1. normalSet do: [:each | slowerSet noCheckAdd: each]. slowerResults := Array
with: slowerSet basicSize
with: slowerSet size
with: (slowerSet basicSize / slowerSet size) asFloat with: (Time millisecondsToRun: [10 timesRepeat: [notIncluded do: [:ea | slowerSet includes: ea]]]). Array with: normalResults with: slowerResults #(#(280277 128057 2.18869 1) #(128431 128057 1.00292 1936)) The performance difference was 1 ms vs. 1936 ms. A hash collision attack would cause inefficient searches through a long series of overlapping "buckets" much like this code simulates. Because VW overlaps logical
buckets, a search that happens in a logical bucket position after an attacked bucket position would experience some of the cost that would otherwise be isolated to just one physical bucket. It wouldn't matter how many free slots VW grows the collection for
because the free spaces would be clustered distant from the start of the search from colliding items. Others have mentioned that the 28 bit computed hash range from a VW string may be of sufficient range to make it extremely difficult to do a string-based collision
attack. I agree it would be difficult to simulate an actual hash collision attack using a hashed collection of strings with 28 bits of hash value range; however, I suspect the assumption is being made that the hash values from other languages have less range
than 28 bits. I couldn't say one way or another. If 28 bits is enough range to be considered attack resistant then other languages could compute a 28 bit hash value from a string just like VW does.
Only a small variance of the hash value is needed to reduce a distributed "meet in the middle" collision attack. VW gets some automatic variance from the size
of the hash table. A physical buckets design doesn't need to adjust the size of the hash table as frequently as VW collections do but VW's more frequent growth of the hash table frequently can reduce some of the computed collisions from #initialIndexFor:boundedBy:.
Assuming that VW string's 28-bit hash range avoids the problem... The hash values for non-strings are not externally controllable in a way that could cause
a hash collision through passing data. For some, that will be the answer they are looking for, case closed. But hold on... While VW is generally safe from direct external attack by data, the performance problems that the attack hopes to exploit are so common
in VW that it is accepted as normal. Most objects in VW default to the 14 bit (16,383) range of values (#maximumIdentityHashValue) from #identityHash. This narrow range causes many smaller/distributed hash collisions. Many now recognize that the inefficiency
of VW hashed collections becomes more pronounced once it contains more than 16K items. Few recognize that the collision costs exist for smaller collections--because the slowness is pervasive and consistent.
In a sense, VW comes pre-attacked with the performance impact of the "meet in the middle" approach of the document. If VW's 28-bit hash range is exploitable
then the design VW uses for hashed collections would likely crash harder and faster than a design that doesn't have the problems I've described. The main difference is that VW would crash in acquiring more memory to grow collections while others might just
get very slow but linger on. The limited range that VW returns for #identityHash is one of the biggest performance problems that 32-bit VW has because it causes poor distribution into the
logical hash buckets. There are many ways to fix the problem by changing the collections or computations. One way to avoid the problem is to use a 64-bit VM that can offer a greater #maximumIdentityHashValue. Upgrading to 64-bit is easier than reimplementing
VW's hashed collections so it is the option Cincom would encourage. Regards, Paul Baumann From: [hidden email] [mailto:[hidden email]]
On Behalf Of Reinout Heeck
--
This message may contain confidential information and is intended for specific recipients unless explicitly noted otherwise. If you have reason to believe you are
not an intended recipient of this message, please delete it and notify the sender. This message may not represent the opinion of IntercontinentalExchange, Inc. (ICE), its subsidiaries or affiliates, and does not constitute a contract or guarantee. Unencrypted
electronic mail is not secure and the recipient of this message is expected to provide safeguards from viruses and pursue alternate means of communication where privacy or a binding message is desired. This message may contain confidential information and is intended for specific recipients unless explicitly noted otherwise. If you have reason to believe you are not an intended recipient of this message, please delete it and notify the sender. This message may not represent the opinion of IntercontinentalExchange, Inc. (ICE), its subsidiaries or affiliates, and does not constitute a contract or guarantee. Unencrypted electronic mail is not secure and the recipient of this message is expected to provide safeguards from viruses and pursue alternate means of communication where privacy or a binding message is desired. _______________________________________________ vwnc mailing list [hidden email] http://lists.cs.uiuc.edu/mailman/listinfo/vwnc |
Re: VW resistance to algorithmic complexity attacks?
|
|
Re: VW resistance to algorithmic complexity attacks?
|
|
Re: VW resistance to algorithmic complexity attacks?
|
|
IRC server
|
|
Re: IRC server
|
|
Re: IRC server
|
|
| Free forum by Nabble | Edit this page |