Access beyond variable bounds

[jaimefrites]

Hi! Looks like BIT_TEST_SEARCH tests bit beyond prefix.add in the macro. Because nobe->bit can be 128 for IPv6 (or 32 for IPv4), but valid index range for prefix.add is [0, 127] (or [0, 31]).

#define RADIX_SEARCH_FOREACH_INCLUSIVE(node, head, prefix) \
        for ((node) = (head); \
             (node) != NULL && (node)->bit <= (prefix)->bitlen; \
             (node) = BIT_TEST_SEARCH(prefix_touchar(prefix), node) ? (node)->r : (node)->l)

[sorc1]

If the code has a bug the could you please reproduce it?

[rk-xyz]

With the following patch, the new test fails in the added assertion, which means that there is a buffer overflow. The message is:

assertion failed at ... in radix_node_t radix_search_worst2(radix_tree_t , prefix_t *, int): (node)->bit < 128

$ git diff
diff --git a/radix/_radix/radix.c b/radix/_radix/radix.c
index 107ff7b..d12af9d 100644
--- a/radix/_radix/radix.c
+++ b/radix/_radix/radix.c
@@ -72,7 +72,7 @@
  */
 #define BIT_TEST(f, b)  ((f) & (b))
 #define BIT_TEST_SEARCH_BIT(addr, bit) \
-        BIT_TEST((addr)[(bit) >> 3], 0x80 >> ((bit) & 0x07))
+        BIT_TEST((assert(bit < 128), (addr)[(bit) >> 3]), 0x80 >> ((bit)&0x07))
 #define BIT_TEST_SEARCH(addr, node) BIT_TEST_SEARCH_BIT(addr, (node)->bit)

 /*
diff --git a/tests/test_regression.py b/tests/test_regression.py
index 2b173e3..53738e2 100644
--- a/tests/test_regression.py
+++ b/tests/test_regression.py
@@ -531,6 +531,12 @@ class TestRadix(unittest.TestCase):
         expected = ['91.187.124.0/23', '91.187.124.0/24', '91.187.125.0/24']
         self.assertEqual(expected, [n.prefix for n in tree])

+    def test_33_oops(self):
+        tree = radix.Radix()
+        prefix = "2001:db8::/128"
+        tree.add(prefix)
+        tree.search_worst(prefix)
+

 def main():
     unittest.main()

[rk-xyz]

I don't fully understand all the logic, but a patch like this one should prevent accessing beyond the prefix->add variable:

diff --git a/radix/_radix/radix.c b/radix/_radix/radix.c
index 107ff7b..a891463 100644
--- a/radix/_radix/radix.c
+++ b/radix/_radix/radix.c
@@ -72,7 +72,7 @@
  */
 #define BIT_TEST(f, b)  ((f) & (b))
 #define BIT_TEST_SEARCH_BIT(addr, bit) \
-        BIT_TEST((addr)[(bit) >> 3], 0x80 >> ((bit) & 0x07))
+        ((bit) < 128 && BIT_TEST((addr)[(bit) >> 3], 0x80 >> ((bit)&0x07)))
 #define BIT_TEST_SEARCH(addr, node) BIT_TEST_SEARCH_BIT(addr, (node)->bit)

 /*