ACL Bug: Bitmasks Break Binary Search

[s0lst1c3]

Description

The use of bitmasks appears to break the binary search which is found within the hostapd_maclist_found function within src/ap/ap_config.c (lines 627-664).

To Reproduce

Start hostapd-mana using the following configuration file and hostapd.accept file (make sure to enable debug output using the -d flag:

hostapd.conf

enable_mana=0
mana_loud=0
mana_macacl=1
interface=wlan0
logger_syslog=-1
logger_syslog_level=2
logger_stdout=-1
logger_stdout_level=2
ssid=testnetwork
hw_mode=g
channel=1
macaddr_acl=1
accept_mac_file=./hostapd.accept
ignore_broadcast_ssid=0

hostapd.accept

00:11:22:33:44:55 00:ff:00:ff:00:ff
00:66:77:88:99:aa
00:00:22:33:44:55
a4:83:e7:02:1a:9c 00:00:00:ff:ff:ff

Observe that when hostapd-mana receives a probe request from a6:83:e7:02:1a:9c, the mac address a6:83:e7:02:1a:9c is checked against 00:00:22:33:44:55/ff:ff:ff:ff:ff:ff, 00:11:22:33:44:55/00:ff:00:ff:00:ff, and 00:66:77:88:99:aa/ff:ff:ff:ff:ff:ff. However, a6:83:e7:02:1a:9c is not compared against a6:83:e7:02:1a:9c/00:00:00:ff:ff:ff, causing it to fail:

Algorithmic Code Trace

I've translated the relevant function into pseudocode to make it easier to follow.

(skipping vlan related code for brevity)

set start = 0
set end = num_entries - 1

match_found = False
while start <= end:

    next_addr = list[middle].addr
    masked_test_value = test_value & list[middle].mask

    if next_addr == masked_test_value:
        match_found = True
        break

    # implicitly, we know that we can't get here unless mac1 != mac2
    if next_addr < test_value:
        start = middle + 1
    else:
        end = middle - 1

Let's assume that we have the following hostapd.accept file:

00:11:22:33:44:55 00:ff:00:ff:00:ff
00:66:77:88:99:aa
00:00:22:33:44:55
a4:83:e7:02:1a:9c 00:00:00:ff:ff:ff

If we translate these mac addresses into decimal format and include their masked transformations, this gives us:

# mac address & mask == transformed
73588229205  & 1095233372415 == 73017786453
440092105130 & 281474976710655 == 440092105130
573785173 & 281474976710655 == 573785173
180886423345820 & 16777215 == 137884

This gives us the following sorted array of transformed MAC addresses (in decimal format):

list = [137884, 573785173, 73017786453, 440092105130]

The length of our array is 4, so we set start to 0 and end to 3.

We then set middle to 3 / 2 which is 1 (integer division).

We then set next_addr to list[middle] which is list[1] which is 573785173.

Our masked_test_value is 137884. Since 137884 is not equal to 573785173 (value of next_addr), we move on.

We next check to see if next_add 573785173 is less than test_value 180886423345820. Since it is, we set start to middle + 1 which is 2.

This shrinks our array from [137884, 573785173, 73017786453, 440092105130] to [73017786453, 440092105130]. Since the next array does not contain our target value 137884, indicating that the algorithm has failed.

Comments

It's possible that a different search algorithm (and possibly a different data structure) is needed to accommodate anything more efficient than a linear search (which is O(n)) when
bitmasks are used. I'm not sure what those would be. I didn't think about this too hard (this stuff makes my head hurt).

I'm guessing this problem may have gone unnoticed due to #40.