Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Replace hashmap by radixtree/linkedlist #209

Open
Gottox opened this issue Jan 11, 2024 · 0 comments
Open

Replace hashmap by radixtree/linkedlist #209

Gottox opened this issue Jan 11, 2024 · 0 comments

Comments

@Gottox
Copy link
Owner

Gottox commented Jan 11, 2024

Currently libsqsh uses a hashmap to cache deflated artifacts of the archive. This is prone to hash collisions and can exploited by well crafted squashfs archives to influence to both increase the time of search and memory usage.

The idea is to replace the hashmap with radix trees, which on its own would waste memory as we need a 1-byte resolution. What we can actually do is to use a combination of radix trees, that resolves only to the lower 8 kbyte and safe the rest of the data in a linked list. The actual parameters need to be tuned.

Radix trees have constant runtime behavior and in combination with linked list, the worst case is that we have a lookup time of O(log(n/r/m)+m), I guess. Which looks pretty okay. And more important is not prone to attacks.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant