commit 8905789170269d29ad87530642ecc2a6a891219b Author: Nick Mathewson nickm@torproject.org Date: Tue Oct 23 17:12:37 2012 -0400

Fix binary search on lists of 0 or 1 element.

The implementation we added has a tendency to crash with lists of 0 or one element. That can happen if we get a consensus vote, v2 consensus, consensus, or geoip file with 0 or 1 element. There's a DOS opportunity there that authorities could exploit against one another, and which an evil v2 authority could exploit against anything downloading v2 directory information..

This fix is minimalistic: It just adds a special-case for 0- and 1-element lists. For 0.2.4 (the current alpha series) we'll want a better patch.

This is bug 7191; it's a fix on 0.2.0.10-alpha. --- src/common/container.c | 23 ++++++++++++++++++++++- 1 files changed, 22 insertions(+), 1 deletions(-)

diff --git a/src/common/container.c b/src/common/container.c index 5f53222..c047562 100644 --- a/src/common/container.c +++ b/src/common/container.c @@ -572,7 +572,28 @@ smartlist_bsearch_idx(const smartlist_t *sl, const void *key, int (*compare)(const void *key, const void **member), int *found_out) { - int hi = smartlist_len(sl) - 1, lo = 0, cmp, mid; + const int len = smartlist_len(sl); + int hi, lo, cmp, mid; + + if (len == 0) { + *found_out = 0; + return 0; + } else if (len == 1) { + cmp = compare(key, (const void **) &sl->list[0]); + if (cmp == 0) { + *found_out = 1; + return 0; + } else if (cmp < 0) { + *found_out = 0; + return 0; + } else { + *found_out = 0; + return 1; + } + } + + hi = smartlist_len(sl) - 1; + lo = 0;

while (lo <= hi) { mid = (lo + hi) / 2;