lua-users home
lua-l archive

[Date Prev][Date Next][Thread Prev][Thread Next] [Date Index] [Thread Index]


Note that resistance against collisions is not a minor problem (and specially not the resistance against predictable collisions): see how this caused severe security problems on the Internet, allowing time-based side-channel attacks to reveal private data with littel efforts (for example the leakage of private data by implementation bugs in processors for managing its internal caches or for allocating internal computing units shared by concurrent threads or processes; similar leakage also occured in web services, allowing external attacks to spy on other users of the service, such as detecting their presence or actions in the service or finding their access passwords or other private data, or to create collisions to attack network protocols with specially crafted usage of the service by malicious third parties, using side-channels that are difficult to detect but were acting like "man-in-the-middle" spiers; some of these defects did not require any user action from the owner of the private data or any intrusion in the service or direct or indirect cooperation by a worker or manager of the service).

All hash tables (in Lua or any other language or system) are good candidates for such attacks trying to predict the collisions detectable by time-based side-channel attacks. It should be remembered that hash tables are used instead of lookups only as an optimization that works well for 95% of initial cases, but that may be abused later for the remaining 5% of cases (notably worst cases). This consideration applies to all other optimization technics (notably the implementation of caches, many of them also using hash tables internally, the situation becoming even worse when the cache uses a simple but poor "cache eviction policy", such as LRU).


Le lun. 27 avr. 2020 à 15:36, Roberto Ierusalimschy <roberto@inf.puc-rio.br> a écrit :
>  > I spent a bit of time worrying that in use cases where many keys are
>  > inserted and removed from a table while the size of the table remains
>  > more or less the same, like the hash table attached to a heap that
>  > supports update-key in A* or Dijkstra or an LRU cache, the performance
>  > may degrade. My mind was put at ease when Roberto shared that all this
>  > won't matter anyway, because for use cases like these the table will
>  > be regularly rehashed even if it does not change size.
>
> What triggers the rehash?  Is it the movement of the `lastfree` pointer?

Yes. 'lastfree' only moves in one direction (from the end of the table
to its beginning). Although it may have to skip several slots to find
a free one, the amortized cost is O(1), as it will pass N slots to
insert N keys. When 'lastfree' hits the beginning of the table, and
therefore it cannot find a free slot, there is a rehash.

When doing a rehash, Lua counts the number of slots actually in use,
that is, with non-nil values, and computes the new size for the table.
(That computation includes the size of the array part, too.) This
new size can be larger (the typical case), smaller, or equal to the
previous size. After the rehash, 'lastfree' is reset to the end of
the table abain.

-- Roberto
_______________________________________________
lua-l mailing list -- lua-l@lists.lua.org
To unsubscribe send an email to lua-l-leave@lists.lua.org
_______________________________________________
lua-l mailing list -- lua-l@lists.lua.org
To unsubscribe send an email to lua-l-leave@lists.lua.org