Linux Kernel
Fuzzing under the cave: hunting bugs in batman-adv
We went looking for an under-tested corner of the Linux kernel and landed on batman-adv, the mesh networking subsystem, whose routing.c sat at 0% coverage on Syzbot. This post walks through how we wired Syzkaller up to fuzz the Ethernet frame reception path — including the Syzlang grammar we had to write from scratch — and the three bugs that came out of it: a 16-bit integer overflow in OGM fragmentation (now patched in mainline), a use-after-free race in the throughput meter, and an integer truncation leading to an out-of-bounds read in the translation table TVLV handler.
Research during a grace period
We had some spare time to conduct vulnerability research on an open subject. We needed to find an interesting target where we could learn something new and related to the Linux kernel. Thus, we searched through Linux subsystems to find our happiness. While looking at Syzbot‘s coverage, we noticed that the subsystem batman had a file called routing.c with 0% of coverage:
We determined there was an opportunity to fuzz the ethernet frames receival logic.
What is BATMAN-ADV?
B.A.T.M.A.N. for Better Approach To Mobile Ad hoc Networking is a routing protocol designed by the Freifunk community for multi-hop ad-hoc mesh networks. The batman-adv implementation works on the Data-link layer (L2) of the OSI model and is implemented as a Linux kernel module.
We can think of a batman-adv as a big switch where we have devices that can be inter-connected as peers. The protocol uses Originator Messages and Echo Location Protocol (on batman-adv V) to maintain routing information. There are also other utilities but we will not describe them as they are already well documented by the maintainers.
Fuzzing batman-adv
Fuzzing Methodology
We used Syzkaller which is a coverage-guided kernel fuzzer. We had experience using it and since Syzbot is based on it, we could reach the same code paths using the existing batman-adv grammar that ensures we can trigger messages to manage the subsystem through a netlink socket (This is a common pattern used to communicate through kernel subsystems).
We already worked on the nftables subsystem, which also involved fuzzing the network reception part. During this work, we discovered the blog post from xairy.io that uses TUN/TAP to send network traffic to the VM’s network stack.
TUN/TAP is a subsystem that provides virtual network devices. The goal is to have a mechanism to communicate network traffic through userland programs. It is a tool often used by VPN applications to encapsulate the network frames/packets:
Syzkaller provides a pseudo-syscall named syz_emit_ethernet for these use cases. However, we needed to adapt some parts of the executor code to initialize the bat0 interface correctly.
Fuzzing implementation
Since we managed to setup Syzkaller to fuzz the frame receival logic, we needed to make sure the grammar for the different types of messages exist. Syzkaller uses Syzlang language to define grammars for syscalls. There is the sys/linux/vnet.txt file to describe the network protocol messages. There was no existing grammar for the batman-adv messages so we had to implement them directly in this file. To provide correct Syzlang descriptions for each message, we based ourselves on the include/uapi/linux/batadv_packet.h file.
eth2_packet [
...
+ batman_adv eth2_packet_t[ETH_P_BATMAN, batman_packet]
+] [varlen]
[...]
+include <uapi/linux/batadv_packet.h>
+
+batman_packet [
+ batman_packet_ogm batman_packet_ogm_t
+ batman_packet_ogm2 batman_packet_ogm2_t
+ batman_packet_elp batman_packet_elp_t
+ batman_packet_multicast batman_packet_multicast_t
+ batman_packet_icmp batman_packet_icmp_t
+ batman_packet_coded batman_packet_coded_t
+ batman_packet_unicast_tvlv batman_packet_unicast_tvlv_t
+ batman_packet_icmp_tp batman_packet_icmp_tp_t
+ batman_packet_icmp_rr batman_packet_icmp_rr_t
+ batman_packet_unicast batman_packet_unicast_t
+ batman_packet_unicast_ext batman_packet_unicast_ext_t
+ batman_packet_fragmented_unicast batman_packet_fragmented_unicast_t
+ batman_packet_broadcast batman_packet_broadcast_t
+] [varlen]
[...]
+batman_packet_ogm_t {
+ hdr batman_header_t[const[BATADV_IV_OGM, int8]]
+ ttl int8
+ flags const[0, int8]
+ seqno int32be
+ orig mac_addr
+ prev_sender mac_addr
+ reserved const[0, int8]
+ tq int8
+ tvlv_len int16be
+} [packed]
Vulnerabilities discovered
Bug 1: Integer Overflow during frame fragmentation
With the complete setup, we quickly found our first bug in batman-adv.
We searched why the bug was triggered and here is our analysis. There is a function call to batadv_iv_ogm_send_to_if to send the OGM message to a given interface. It also handles the fragmentation.
/* send a batman ogm to a given interface */
static void batadv_iv_ogm_send_to_if(struct batadv_forw_packet *forw_packet,
struct batadv_hard_iface *hard_iface)
{
struct batadv_priv *bat_priv = netdev_priv(hard_iface->soft_iface);
const char *fwd_str;
u8 packet_num;
s16 buff_pos;
struct batadv_ogm_packet *batadv_ogm_packet;
struct sk_buff *skb;
u8 *packet_pos;
if (hard_iface->if_status != BATADV_IF_ACTIVE)
return;
packet_num = 0;
buff_pos = 0;
packet_pos = forw_packet->skb->data;
batadv_ogm_packet = (struct batadv_ogm_packet *)packet_pos;
/* adjust all flags and log packets */
while (batadv_iv_ogm_aggr_packet(buff_pos, forw_packet->packet_len,
batadv_ogm_packet)) {
[...]
buff_pos += BATADV_OGM_HLEN;
buff_pos += ntohs(batadv_ogm_packet->tvlv_len);
packet_num++;
packet_pos = forw_packet->skb->data + buff_pos;
batadv_ogm_packet = (struct batadv_ogm_packet *)packet_pos;
}
[...]
}
We found out that there is a variable named buff_pos that stores the current buffer position to separate the OGM messages from the forward packet. We noted that the variable stores this information on a signed integer of 16 bits. There is a size check that is done on this variable in the batadv_iv_ogm_aggr_packet function that can be called in the previous function multiple times.
/**
* batadv_iv_ogm_aggr_packet() - checks if there is another OGM attached
* @buff_pos: current position in the skb
* @packet_len: total length of the skb
* @ogm_packet: potential OGM in buffer
*
* Return: true if there is enough space for another OGM, false otherwise.
*/
static bool
batadv_iv_ogm_aggr_packet(int buff_pos, int packet_len,
const struct batadv_ogm_packet *ogm_packet)
{
int next_buff_pos = 0;
/* check if there is enough space for the header */
next_buff_pos += buff_pos + sizeof(*ogm_packet);
if (next_buff_pos > packet_len)
return false;
/* check if there is enough space for the optional TVLV */
next_buff_pos += ntohs(ogm_packet->tvlv_len);
return next_buff_pos <= packet_len;
}
However, this function compares our buff_pos variable against a signed 32 bits integer. After some debugging, we noticed the variable signed on 16 bits can overflow with large frames, which caused the condition to still pass since we are below the packet_len with a negative value.
The patch was fairly simple as we simply needed to change buff_pos into a signed 32 bits integer variable in the batadv_iv_ogm_send_to_if function. Since it was an unknown bug, we were able to send the patch to the maintainers. The patch is now merged into the Linux kernel mainline.
Bug 2: Race condition on throughput meter when interface is deleted
Syzkaller showed us a slab use-after-free bug on the batadv_find_router function. We analyzed the KASAN trace and started to understand why the bug occurred. We understood that we needed to initiate a ThroughputMeter (TP) which is a tool to calculate the bandwidth in the mesh network. It can be triggered through a netlink socket using the BATADV_CMD_TP_METER message.
This action creates a kthread in the batadv_tp_start_kthread function.
static void batadv_tp_start_kthread(struct batadv_tp_sender *tp_vars)
{
struct task_struct *kthread;
struct batadv_priv *bat_priv = tp_vars->common.bat_priv;
u32 session_cookie;
kref_get(&tp_vars->common.refcount);
kthread = kthread_create(batadv_tp_send, tp_vars, "kbatadv_tp_meter");
[...]
wake_up_process(kthread);
}
We also checked where the use-after-free occurred. After reading the code, we determined it happened in batadv_find_router when trying to access an attribute of the batadv_priv structure. This is interesting because it contains information about the mesh interface. This helped determine that there was a race condition because of the kthread trying to access data when the interface was already deleted.
However, the bug was already known and patches were already implemented in the mailing lists.
Bug 3: Integer truncation when computing the VLAN size when receiving a unicast packet with a TT TVLV
A TVLV (Type Version Length Value) is a “container” that can be appended to some packets (such as OGM or Unicast) to send information to other nodes. For this bug, we will have a look at the Translation Table (TT) TVLV (see the open-mesh documentation). Its objective is to advertise local non-mesh clients. Here is the format of the TVLV:
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| TVLV 0x04 | Version | Length |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| TT Flags | TTVN | Number of VLANs |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| CRC32_vlan1 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| VID_vlan1 | reserved_vlan1 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| CRC32_vlan2 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| VID_vlan2 | reserved_vlan2 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| ................... |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| CRC32_vlanN |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| VID_vlanN | reserved_vlanN |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| flags_change1 | reserved_change1 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| mac_addr_change1... |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| ...mac_addr_change1 | vid_change1 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| flags_change2 | reserved_change2 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| mac_addr_change2... |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| ...mac_addr_change2 | vid_change2 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| ................... |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| flags_changeM | reserved_changeM |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| mac_addr_changeM... |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| ...mac_addr_changeM | vid_changeM |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
The bug is in batadv_tt_tvlv_unicast_handler_v1 when computing the size of the vlans:
/**
* batadv_tt_tvlv_unicast_handler_v1() - process incoming (unicast) tt tvlv
* container
* @bat_priv: the bat priv with all the mesh interface information
* @src: mac address of tt tvlv sender
* @dst: mac address of tt tvlv recipient
* @tvlv_value: tvlv buffer containing the tt data
* @tvlv_value_len: tvlv buffer length
*
* Return: NET_RX_DROP if the tt tvlv is to be re-routed, NET_RX_SUCCESS
* otherwise.
*/
static int batadv_tt_tvlv_unicast_handler_v1(struct batadv_priv *bat_priv,
u8 *src, u8 *dst,
void *tvlv_value,
u16 tvlv_value_len)
{
struct batadv_tvlv_tt_data *tt_data;
u16 tt_num_entries;
u16 tt_vlan_len;
char tt_flag;
bool ret;
if (tvlv_value_len < sizeof(*tt_data))
return NET_RX_SUCCESS;
tt_data = tvlv_value;
tvlv_value_len -= sizeof(*tt_data);
tt_vlan_len = flex_array_size(tt_data, vlan_data,
ntohs(tt_data->num_vlan));
if (tvlv_value_len < tt_vlan_len)
return NET_RX_SUCCESS;
tvlv_value_len -= tt_vlan_len;
tt_num_entries = batadv_tt_entries(tvlv_value_len);
[...]
}
The function flex_array_size returns a size_t, which will be truncated when assigned to tt_vlan_len which is a u16. This bug will later cause an out-of-bounds read.
Conclusion
This work showed us the importance of analyzing what was already done and what was not well explored. With this first analysis, we identified the routing spot in batman-adv. Using existing solutions like Syzkaller with its networking utilities and our custom made Syzlang grammar, we managed to find and report an unknown bug. There are also other opportunities to explore in the batman-adv subsystem since we can tweak some parameters such as the protocol version (e.g. this changes the routing algorithm). This ensures that we explore other code paths that could be complex for the fuzzer to setup directly through the normal grammar since mutation of the corpus can take some time.
Sources
Patrick Ventuzelo / @Pat_Ventuzelo
About Us
Founded in 2021, FuzzingLabs is an offensive security company specializing in fuzzing, vulnerability research and reverse engineering on firmware, binaries and embedded systems. Our team of 20 has published 20+ CVEs, found over 1,500 bugs and won three Pwn2Own competitions. We also build FuzzForge, an autonomous offensive security platform for continuous validation of firmware, binaries and embedded systems.Contact us for an audit, a FuzzForge evaluation or a long term partnership.
Get Your Free Security Quote!
Let’s work together to ensure your peace of mind.
