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

Out of bounds access in CritBitTree #11344

Closed
c-blake opened this issue May 28, 2019 · 2 comments

Comments

Projects
None yet
3 participants
@c-blake
Copy link
Contributor

commented May 28, 2019

If the requested prefix is longer than a key, the library accesses past the end of string. E.g.:

import critbits
var cb: CritBitTree[string]
cb.incl("help", "help")
for k in cb.keysWithPrefix("helpp"):
  echo k

Current Output

critbits.nim(270)        cbBug
critbits.nim(256)        allprefixedAux
fatal.nim(39)            sysFatal
Error: unhandled exception: index 4 not in 0 .. 3 [IndexError]

Expected Output

Should print nothing since "helpp" is not the prefix of any string in the CritBitTree.

Possible Solution

Changing the offending line of code from

if p.key[i] != key[i]: return

to

if i >= p.key.len or p.key[i] != key[i]: return

seems to work for me. It may also be possible to do an earlier check of p.key.len vs key.len instead.

I believe this is a very old bug.

@Araq

This comment has been minimized.

Copy link
Member

commented May 28, 2019

I believe this is a very old bug.

Well it used to be no bug because of the zero termination, I think.

@Araq Araq closed this in 4a9e636 May 28, 2019

@c-blake

This comment has been minimized.

Copy link
Contributor Author

commented May 28, 2019

Sounds plausible (former no bug-wise). Thanks.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.