BPF size limitation

[strasharo]

Is there any size limitation for the maximum size of the bpf used for filtering? At 1291 characters it appears to work fine. At 1365 characters it fails with:

scan frequencies: frequency [channel] of Regulatory Domain: 00
2412 [ 1] 2437 [ 6] 2462 [ 11]
failed to open raw packet socket
[?25h1 ERROR(s) during runtime
Possible reasons:
driver is broken
driver is busy (misconfigured system, other services access the INTERFACE)
1 Packet(s) captured by kernel
0 Packet(s) dropped by kernel
Warning: too less packets received (monitor mode may not work as expected)
Possible reasons:
driver is broken (most likely)
no transmitter in range
frames are filtered out by BPF
1 SHB written to pcapng dumpfile
1 IDB written to pcapng dumpfile
1 ECB written to pcapng dumpfile
0 EPB written to pcapng dumpfile

It's not driver specific, fails on all with the same error. Took me a while to realize the reason, I thought I broke something with the drivers. That's on OpenWRT latest compiled from source.

[ZerBea]

The maximum number of instructions (BPF_MAXINSNS) that the unprivileged BPF program can have is limited to 4096.
Q: What are the verifier limits?

Both tools check the length:
https://github.com/ZerBea/hcxdumptool/blob/master/hcxdumptool.c#L4440
https://github.com/ZerBea/wifi_laboratory/blob/main/hcxlabtool.c#L4709

If that failed, both tools show an error:
fprintf(stderr, "failed to read BPF\n");

Instrucitons is not equal to characters. FIltereing a single MAC and setting the snaplen are 16 instructions:

$ hcxdumptool --bpfc="not wlan addr3 111111111111" | wc
     16      64     157

The more MAC to be filtered, the instructions increase:

$ hcxdumptool --bpfc="not wlan addr3 111111111111 and not wlan addr3 222222222222" | wc
     19      76     196

$ hcxdumptool --bpfc="not wlan addr3 111111111111 and not wlan addr1 222222222222" | wc
     20      80     204

$ hcxdumptool --bpfc="not wlan addr1 111111111111 and not wlan addr2 222222222222" | wc
     26     104     267

[ZerBea]

I just made an attempt.
This code generates a command line of 501 MACs to be filtered:

#define _GNU_SOURCE
#include <ctype.h>
#include <dirent.h>
#include <fcntl.h>
#include <ftw.h>
#include <libgen.h>
#include <stdarg.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/stat.h>
#include <sys/types.h>
#include <unistd.h>
#include <utime.h>
#include <inttypes.h>

/*===========================================================================*/
int main()
{
int a = 0;

uint64_t mac = 0x112233445566;

fprintf(stdout,"hcxdumptool --bpfc=\"not wlan addr3 112233445566");
for(a = 0; a < 500; a++)
	fprintf(stdout, " and not wlan addr3 %012" PRIx64, mac + a);
fprintf(stdout,"\"\n");
return EXIT_SUCCESS;
}

It compiles as expected (hcxdumptool/hcxlabtool) and the size of the BPF is 760 instructions:

$ wc test.bpf
  760  3040 11492 test.bpf

Driver is rtl8xxxu:

$ hcxdumptool -l
  10	 13	5ce931984b44	980ee4b8cd3b	+	wlp5s0f3u2      	rtl8xxxu	NETLINK

Everything is as expected:

$ sudo hcxdumptool -i wlp5s0f3u2 --rcascan=active --bpf=test.bpf
...
^C
265 Packet(s) captured by kernel
0 Packet(s) dropped by kernel
77 PROBERESPONSE(s) captured

How many instructions does your bpf contain?

[strasharo]

This is the sample bpf which fails it for me when being ran (last three octets swapped with FF just for the sample):

not wlan addr1 D8:07:B6:FF:FF:FF and not wlan addr2 D8:07:B6:FF:FF:FF and not wlan addr3 D8:07:B6:FF:FF:FF and not wlan addr1 AC:8B:A9:FF:FF:FF and not wlan addr2 AC:8B:A9:FF:FF:FF and not wlan addr3 AC:8B:A9:FF:FF:FF and not wlan addr1 AC:8B:A9:FF:FF:FF and not wlan addr2 AC:8B:A9:FF:FF:FF and not wlan addr3 AC:8B:A9:FF:FF:FF and not wlan addr1 B2:8B:A9:FF:FF:FF and not wlan addr2 B2:8B:A9:FF:FF:FF and not wlan addr3 B2:8B:A9:FF:FF:FF and not wlan addr1 AC:15:A2:FF:FF:FF and not wlan addr2 AC:15:A2:FF:FF:FF and not wlan addr3 AC:15:A2:FF:FF:FF and not wlan addr1 F0:B4:29:FF:FF:FF and not wlan addr2 F0:B4:29:FF:FF:FF and not wlan addr3 F0:B4:29:FF:FF:FF and not wlan addr1 A4:7E:39:FF:FF:FF and not wlan addr2 A4:7E:39:FF:FF:FF and not wlan addr3 A4:7E:39:FF:FF:FF and not wlan addr1 30:05:05:FF:FF:FF and not wlan addr2 30:05:05:FF:FF:FF and not wlan addr1 DC:4F:22:FF:FF:FF and not wlan addr2 DC:4F:22:FF:FF:FF and not wlan addr1 5C:CF:7F:FF:FF:FF and not wlan addr2 5C:CF:7F:FF:FF:FF and not wlan addr1 64:90:C1:FF:FF:FF and not wlan addr2 64:90:C1:FF:FF:FF and not wlan addr1 5C:E5:0C:FF:FF:FF and not wlan addr2 5C:E5:0C:FF:FF:FF and not wlan addr1 8C:C8:4B:FF:FF:FF and not wlan addr2 8C:C8:4B:FF:FF:FF and not wlan addr1 70:03:9F:FF:FF:FF and not wlan addr2 70:03:9F:FF:FF:FF and not wlan addr1 00:E0:4C:FF:FF:FF and not wlan addr2 00:E0:4C:FF:FF:FF
That would be 37 instructions I guess.

[ZerBea]

BTW:
APs appear as addr1,addr2 and addr3. Clients appear as addr1 and addr2.
It depends on the frame types:

• frames only with addr1, e.g. ACK
• frames only with addr1 and addr2, e.g. REQUEST_TO_SEND
• frames with addr1, addr2 and addr3, e.g. BEACON
• frames with addr1, addr2, addr3 and addr4, e.g. mesh data frames
  https://howiwifi.com/2020/07/13/802-11-frame-types-and-formats/

hcxdumptool/hcxlabtool only works on frames which are mandatory to retrieve a hash. All other frames are ignored (due to performance reason).

If you want to filter an AP it is enough to filter ADDR3.

If you want to filter a CLIENT it is enough to filter ADDR2. This will fail if the CLIENT is running MAC randomization.
hcxdumptool/hcxlabtool runs MAC randomization. If the CLIENT runs MAC randomization too, the filter can't prevent that we get an EAPOL M1M2ROGUE.

To improve your filter, I suggest to use tshark (live capturing):

$ sudo hcxdumptool -m INTERFACE_NAME -c 1a
$ tshark -i INTERFACE_NAME (for unfiltered traffic)
$ tshark -i INTERFACE_NAME -f "....." (for filtered traffic), e.g. -f "wlan addr3 111111111111"

BTW:
I found an interesting description here (especially the MAPS section):
https://docs.cilium.io/en/latest/reference-guides/bpf/architecture/#maps
The maximum instruction limit per program is restricted to 4096 BPF instructions, which, by design, means that any program will terminate quickly. For kernel newer than 5.1 this limit was lifted to 1 million BPF instructions.

And in the MAPS section:
A single BPF program can currently access up to 64 different maps directly.
It looks like your filter exceeds this limit and the kernel reports ERRNO "out of memory".

[strasharo]

Thanks a lot for the detailed explanation. Something's weird though, it started failing with just one statement with the latest build:

root@zerowrt:~/dump# service hcxdump start 
Sleeping for 10 seconds before starting the service...
Starting service with retry interval 10 and max retries 5.
PHY phy0 already has an interface. Skipping.
PHY phy1 already has an interface. Skipping.
Wireless device found: archer
Preparing BPF filter.
Generated BPF filter: not wlan addr3 D8:07:B6:XX:XX:XX 
Starting /usr/sbin/hcxdumptool on device archer.
root@zerowrt:~/dump# cat hcxdumptool.log 
SO_ATTACH_FILTER failed: No error information
root@zerowrt:~/dump# 

It's running fine without a BPF set.

[ZerBea]

Thanks. That should be fixed now (by latest commit).
The debug code (to hunt for the problem) has now been completely removed. Attaching a BPF always caused a message and hcxdumptool terminates regardless if it is an ERROR or not.

[strasharo]

Thanks a lot, it works perfectly now. With your guidance I've reduced my bpf by a few times. Here's the routine is use to generate it in my init script in case someone might find it useful to borrow. It's looking for both ap/client black/whitelists and generates a bpf with them if they're being present.

    echo "Preparing BPF filter."

    # Step 1: Remove the old filter file
    /bin/rm -f /root/dump/filter.bpf

    # Step 2: Initialize BPF filter variable
    bpf_filter=""

    # Step 3: Process blacklist_ap if available
    if [ -f /root/dump/blacklist_ap ]; then
        while read -r line; do
            mac_address=$(echo "$line" | awk '{print $1}')
            if [ -n "$mac_address" ]; then
                bpf_filter="${bpf_filter}not wlan addr3 $mac_address and "
            fi
        done < /root/dump/blacklist_ap
    fi

    # Step 4: Process blacklist_client if available
    if [ -f /root/dump/blacklist_client ]; then
        while read -r line; do
            mac_address=$(echo "$line" | awk '{print $1}')
            if [ -n "$mac_address" ]; then
                bpf_filter="${bpf_filter}not wlan addr2 $mac_address and "
            fi
        done < /root/dump/blacklist_client
    fi

    # Step 5: Process target_ap if available
    if [ -f /root/dump/target_ap ]; then
        while read -r line; do
            mac_address=$(echo "$line" | awk '{print $1}')
            if [ -n "$mac_address" ]; then
                bpf_filter="${bpf_filter}wlan addr3 $mac_address or "
            fi
        done < /root/dump/target_ap
    fi

    # Step 6: Process target_client if available
    if [ -f /root/dump/target_client ]; then
        while read -r line; do
            mac_address=$(echo "$line" | awk '{print $1}')
            if [ -n "$mac_address" ]; then
                bpf_filter="${bpf_filter}wlan addr2 $mac_address or "
            fi
        done < /root/dump/target_client
    fi

    # Remove trailing "and " or "or " from the BPF filter
    bpf_filter=${bpf_filter%and }
    bpf_filter=${bpf_filter%or }

    # Step 7: Generate filter.bpf if BPF filter is non-empty
    use_bpf_arg=""
    if [ -n "$bpf_filter" ]; then
        $PROG --bpfc="$bpf_filter" > /root/dump/filter.bpf
        echo "Generated BPF filter: $bpf_filter"
        use_bpf_arg="--bpf=/root/dump/filter.bpf"
    else
        echo "No filters generated. Running without BPF filter."
    fi

    # Step 8: Start hcxdumptool
    echo "Starting $PROG on device $WLANDEV."
    /usr/sbin/screen -AmdS dump -L -Logfile /root/dump/screen.out \
        $PROG $use_bpf_arg -i "$WLANDEV" -w /root/dump/"$ARCHIVENAME".pcapng --rds=1

[ZerBea]

You're welcome. Glad to hear that it is working now and thanks for sharing your script.

Sorting by MAC ADDR field reduce the list of instructions and loops.

BTW:
To reduce workload, some control frame types (type ctl / subtype ack and type ctl / subtype cts) can be filtered out too:
$ hcxdumptool --bpfc="not type ctl subtype ack and not type ctl subtype cts not wlan addr3 D807B6FFFFFF and not wlan addr3 ..."
This prevents that this frames types reach hcxdumptools/hcxlabtools man packet loop.