Recent eBPF verifier rejects program that was accepted by 6.8 eBPF verifier

Recent eBPF verifier rejects program that was accepted by 6.8 eBPF verifier

[Francis Deslauriers]

Hi all,
I'd like to report what I think is a eBPF verifier regression. I have a eBPF
program that is accepted by the 6.8 eBPF verifier but is rejected on 6.9 and 
later. It's my understanding that a eBPF program that is accepted by one
version of the verifier should be accepted on all subsequent versions.

I added a stripped down libbpf reproducer based on the libbpf-bootstrap repo to
showcase this issue (see below). Note that if I change the RULE_LIST_SIZE from
380 to 30, the verifier accepts the program.

I bisected the issue down to this commit:
	commit 8ecfc371d829bfed75e0ef2cab45b2290b982f64
	Author: Maxim Mikityanskiy <maxim@isovalent.com>
	Date:   Mon Jan 8 22:52:02 2024 +0200

    	bpf: Assign ID to scalars on spill

	
Before commit 8ecfc371d82
	$ uname -r 
	6.7.0-12291-g87e51ac6cb19

	$ sudo ./tc
	loads succesfully

After commit 8ecfc371d82
	$ uname -r
	6.7.0-12292-g8ecfc371d829

	$ sudo ./tc  2>&1 | grep -A4 "too large"
	BPF program is too large. Processed 1000001 insn
	processed 1000001 insns (limit 1000000) max_states_per_insn 26 total_states 62473 peak_states 5456 mark_read 162
	-- END PROG LOAD LOG --
	libbpf: prog 'tc_ingress': failed to load: -7
	libbpf: failed to load object 'tc_bpf'

I confirmed the issue affects master as well.
	$ uname -r
	6.12.0-rc7-00125-gcfaaa7d010d1

	$ sudo ./tc 2>&1 | grep -A4 "too large" 
	BPF program is too large. Processed 1000001 insn
	processed 1000001 insns (limit 1000000) max_states_per_insn 26 total_states 62473 peak_states 5456 mark_read 162
	-- END PROG LOAD LOG --
	libbpf: prog 'tc_ingress': failed to load: -7
	libbpf: failed to load object 'tc_bpf'


I'm investigating how this commit affects how instructions are counted
 and why it leads to such a drastic change for this particular program.
I wanted to share my findings early in case someone has any hints for me.

To reproduce, use the following file as a drop in replacement of 
libbpf-boostrap's examples/c/tc.bpf.c:
--->8---
#include <vmlinux.h>
#include <bpf/bpf_core_read.h>
#include <bpf/bpf_helpers.h>
#include <bpf/bpf_endian.h>

char LICENSE[] SEC("license") = "GPL";

typedef enum : uint8_t {
	CONN_DIR_OUTBOUND = 0,
	CONN_DIR_INBOUND = 1,
	CONN_DIR_NEITHER = 2,
} connection_dir_t;

typedef enum : uint8_t {
	ACTION_ALLOW = 0,
	ACTION_DENY = 1,
} rule_action_t;


#define TC_ACT_UNSPEC   (-1)
#define TC_ACT_OK       0
#define TC_ACT_RECLASSIFY   1
#define TC_ACT_SHOT     2

#define AF_UNSPEC     0
#define AF_INET     2
#define ETH_P_IP 0x0800
#define ETH_P_IPV6 0x86DD

#define RULE_LIST_SIZE 380
#define RULE_CONTROLS 0x00000001

struct connection_tuple_v4 {
	uint32_t saddr;
	uint32_t daddr;
};

typedef struct pkt_info {
	struct connection_tuple_v4 ip4;
	uint16_t family;
	uint16_t ip_protocol;
	uint16_t eth_protocol;
	rule_action_t action;
	bool ip_proto_udp_or_tcp;
	uint8_t pad[7];
} pkt_info_t;

typedef struct pkt_info_rule {
	pkt_info_t info;
	uint32_t pad;
	struct connection_tuple_v4 ip4_mask;
} pkt_info_rule_t;

struct {
	__uint(type, BPF_MAP_TYPE_HASH);
	__uint(max_entries, 2);
	__type(key, u32);
	__type(value, pkt_info_rule_t[RULE_LIST_SIZE]);
	__uint(map_flags, BPF_F_RDONLY_PROG | BPF_F_WRONLY);
} rules_map SEC(".maps");

static __always_inline bool
match_ipaddr_with_mask_ipv4(const uint32_t *rule_addr,
			    const uint32_t *rule_addr_mask,
			    const uint32_t *data_packet_addr)
{
	if ((*rule_addr == 0) || (*data_packet_addr == 0)) {
		return true;
	}
	else if ((*rule_addr_mask == 0) && (*rule_addr == *data_packet_addr)) {
		return true;
	}
	else if ((*rule_addr_mask != 0) &&
		 ((*rule_addr & *rule_addr_mask) ==
		  (*data_packet_addr & *rule_addr_mask))) {
		return true;
	}
	return false;
}

static __always_inline bool protocol_match(int rule_protocol,
					   int packet_protocol)
{
	return (rule_protocol == 0 || rule_protocol == packet_protocol);
}

struct match_ipv4_pkt {
	uint32_t local_addr;
	uint32_t remote_addr;
};

static __always_inline bool match_ipv4(const pkt_info_rule_t *rule,
				       pkt_info_t *pkt,
				       const struct match_ipv4_pkt *cmp,
				       int *output)
{
	if (protocol_match(rule->info.ip_protocol, pkt->ip_protocol) &&
	    (match_ipaddr_with_mask_ipv4(&rule->info.ip4.saddr,
					 &rule->ip4_mask.saddr,
					 &cmp->local_addr)) &&
	    (match_ipaddr_with_mask_ipv4(&rule->info.ip4.daddr,
					 &rule->ip4_mask.daddr,
					 &cmp->remote_addr))) {
		if (pkt->ip_proto_udp_or_tcp) {
			return false;
		}

		*output = rule->info.action;
		return true;
	}

	return false;
}

static __always_inline int apply_rules_ipv4(pkt_info_t *pkt,
					    const pkt_info_rule_t *rules)
{
	if ((pkt == NULL) || (rules == NULL)) {
		return TC_ACT_UNSPEC;
	}

	int output = ACTION_ALLOW;
	struct match_ipv4_pkt dir_cmp;

	dir_cmp.local_addr = pkt->ip4.daddr;
	dir_cmp.remote_addr = pkt->ip4.saddr;

	for (int i = 0; i < RULE_LIST_SIZE; i++) {
		const pkt_info_rule_t rule = rules[i];

		bool ret;
		ret = match_ipv4(&rule, pkt, &dir_cmp, &output);
		if (ret) {
			break;
		}
	}

	if (output == ACTION_ALLOW) {
		return TC_ACT_UNSPEC;
	} else {
		return TC_ACT_SHOT;
	}
}

#define HEADER_BOUNDS_CHECK(hdr, skb) \
	((unsigned long)(hdr + 1) > (unsigned long)skb->data_end)

static __always_inline bool get_tuple(const struct __sk_buff *skb,
				      const struct ethhdr *eth, pkt_info_t *pkt)
{
	pkt->eth_protocol = bpf_ntohs(BPF_CORE_READ(eth, h_proto));

	if ((pkt->eth_protocol == ETH_P_IP) ||
	    ((skb->protocol == __bpf_constant_htons(ETH_P_IP)))) {
		struct iphdr *iph = (struct iphdr *)(skb->data + sizeof(*eth));

		if (HEADER_BOUNDS_CHECK(iph, skb)) {
			return false;
		}

		pkt->family = AF_INET;

		pkt->ip4.saddr = BPF_CORE_READ(iph, saddr);
		pkt->ip4.daddr = BPF_CORE_READ(iph, daddr);

		pkt->ip_protocol = BPF_CORE_READ(iph, protocol);

		pkt->ip_proto_udp_or_tcp = (pkt->ip_protocol == IPPROTO_TCP) ||
					   (pkt->ip_protocol == IPPROTO_UDP);

		return true;

	} else {
		pkt->family = AF_UNSPEC;
		return false;
	}
}

static __always_inline bool populate_pkt_info(const struct __sk_buff *skb,
					      pkt_info_t *pkt)
{
	struct ethhdr *eth = (struct ethhdr *)(unsigned long)(skb->data);

	if (HEADER_BOUNDS_CHECK(eth, skb)) {
		return false;
	}

	return get_tuple(skb, eth, pkt);
}

static __always_inline int allow_pkt(pkt_info_t *pkt)
{
	uint32_t key = pkt->family;
	const pkt_info_rule_t *rules = bpf_map_lookup_elem(&rules_map, &key);
	if (rules == NULL) {
		return TC_ACT_UNSPEC;
	}

	switch (pkt->family) {
	case AF_INET:
		return apply_rules_ipv4(pkt, rules);
	default:
		return TC_ACT_UNSPEC;
	}
}

SEC("tc")
int tc_ingress(struct __sk_buff *skb)
{
	pkt_info_t pkt ={0};

	bool ret = populate_pkt_info(skb, &pkt);
	if (ret != true) {
		return TC_ACT_UNSPEC;
	}

	return allow_pkt(&pkt);
}

--->8---


Thank you,
Francis

Re: Recent eBPF verifier rejects program that was accepted by 6.8 eBPF verifier

[Maxim Mikityanskiy]

Hi Francis,

On Fri, 15 Nov 2024 at 22:59, Francis Deslauriers
<francis.deslauriers@crowdstrike.com> wrote:
> I added a stripped down libbpf reproducer based on the libbpf-bootstrap repo to
> showcase this issue (see below). Note that if I change the RULE_LIST_SIZE from
> 380 to 30, the verifier accepts the program.
>
> I bisected the issue down to this commit:
>         commit 8ecfc371d829bfed75e0ef2cab45b2290b982f64
>         Author: Maxim Mikityanskiy <maxim@isovalent.com>
>         Date:   Mon Jan 8 22:52:02 2024 +0200
>
>         bpf: Assign ID to scalars on spill

This commit was part of a series with a few new features that are
indeed expected to raise the complexity with some programs. To
compensate for it, a patch by Eduard was submitted within the same
series. Could you please test your program on this kernel commit?

6efbde200bf3 bpf: Handle scalar spill vs all MISC in stacksafe()

I.e. whether it passes or fails, and If it fails, what's the biggest
RULE_LIST_SIZE that passes. Let's see if Eduard's patch helps
partially or doesn't address this issue at all (or helps fully, but
there is another regression after his commit).

> It's my understanding that a eBPF program that is accepted by one
> version of the verifier should be accepted on all subsequent versions.

That's basically the goal. Obviously, some new features will increase
the verification complexity, but we are trying to compensate for it or
to make it insignificant.

For example, when I introduced my changes (with Eduard's patch), I
tested the complexity before and after on the set of BPF programs that
included kernel selftests and Cilium:

https://patchwork.kernel.org/project/netdevbpf/cover/20240108205209.838365-1-maxtram95@gmail.com/
https://patchwork.kernel.org/project/netdevbpf/cover/20240127175237.526726-1-maxtram95@gmail.com/

As you can see, Eduard's patch really helped with most regressions,
and the whole picture looked good enough. Apparently (if this series
is indeed the culprit), your program uses some pattern that wasn't
covered by the set of programs that I checked.

> I'm investigating how this commit affects how instructions are counted
>  and why it leads to such a drastic change for this particular program.

I'd guess, most likely, something inside the loop body became more
complex to verify, and it's repeated 380 times, further increasing the
total complexity.

I wonder where 380 comes from. Is it just the maximum number of
iterations that the old verifier could handle? Or does it have a
deeper meaning?

Is bpf_loop an option for you?

> I wanted to share my findings early in case someone has any hints for me.
>
> To reproduce, use the following file as a drop in replacement of
> libbpf-boostrap's examples/c/tc.bpf.c:

I reproduced the issue on 6.11.6, the highest RULE_LIST_SIZE that
works for me is 35, but I currently lack time to take a deeper look.
Do you have any new findings in the meanwhile?

Re: Re: Recent eBPF verifier rejects program that was accepted by 6.8 eBPF verifier

[Francis Deslauriers]

Hi Maxim,

On Wed, 2024-11-20 at 22:33 +0200, Maxim Mikityanskiy wrote:
> Hi Francis,
> 
> On Fri, 15 Nov 2024 at 22:59, Francis Deslauriers
> <francis.deslauriers@crowdstrike.com> wrote:
> > I added a stripped down libbpf reproducer based on the libbpf-
> > bootstrap repo to
> > showcase this issue (see below). Note that if I change the
> > RULE_LIST_SIZE from
> > 380 to 30, the verifier accepts the program.
> > 
> > I bisected the issue down to this commit:
> >         commit 8ecfc371d829bfed75e0ef2cab45b2290b982f64
> >         Author: Maxim Mikityanskiy <maxim@isovalent.com>
> >         Date:   Mon Jan 8 22:52:02 2024 +0200
> > 
> >         bpf: Assign ID to scalars on spill
> 
> This commit was part of a series with a few new features that are
> indeed expected to raise the complexity with some programs. To
> compensate for it, a patch by Eduard was submitted within the same
> series. Could you please test your program on this kernel commit?
> 
> 6efbde200bf3 bpf: Handle scalar spill vs all MISC in stacksafe()
That commit was included in the commit from master that I tested.
> 
> I.e. whether it passes or fails, and If it fails, what's the biggest
> RULE_LIST_SIZE that passes. Let's see if Eduard's patch helps
> partially or doesn't address this issue at all (or helps fully, but
> there is another regression after his commit).
> 
> > It's my understanding that a eBPF program that is accepted by one
> > version of the verifier should be accepted on all subsequent
> > versions.
> 
> That's basically the goal. Obviously, some new features will increase
> the verification complexity, but we are trying to compensate for it
> or
> to make it insignificant.
> 
> For example, when I introduced my changes (with Eduard's patch), I
> tested the complexity before and after on the set of BPF programs
> that
> included kernel selftests and Cilium:
> 
> https://urldefense.com/v3/__https://patchwork.kernel.org/project/netdevbpf/cover/20240108205209.838365-1-maxtram95@gmail.com/__;!!BmdzS3_lV9HdKG8!0PQcMqrhQi11Pcrc3XFRWe8ktC7OEKTEQaqrNJU-Bs7nIYJZBsLBS7SUJh13nWpCApaZhIAmVrFy8kl9s2FW6puJcTE$
>  
> https://urldefense.com/v3/__https://patchwork.kernel.org/project/netdevbpf/cover/20240127175237.526726-1-maxtram95@gmail.com/__;!!BmdzS3_lV9HdKG8!0PQcMqrhQi11Pcrc3XFRWe8ktC7OEKTEQaqrNJU-Bs7nIYJZBsLBS7SUJh13nWpCApaZhIAmVrFy8kl9s2FWW01r49Y$
>  
> 
> As you can see, Eduard's patch really helped with most regressions,
> and the whole picture looked good enough. Apparently (if this series
> is indeed the culprit), your program uses some pattern that wasn't
> covered by the set of programs that I checked.
> 
> > I'm investigating how this commit affects how instructions are
> > counted
> >  and why it leads to such a drastic change for this particular
> > program.
> 
> I'd guess, most likely, something inside the loop body became more
> complex to verify, and it's repeated 380 times, further increasing
> the
> total complexity.
> 
> I wonder where 380 comes from. Is it just the maximum number of
> iterations that the old verifier could handle? Or does it have a
> deeper meaning?

That's it. It was the largest number of iterations that was accepted by
all the kernel verifier versions we support.
> 
> Is bpf_loop an option for you?

We are exploring new approaches for our future releases but our past
releases can't be changed.
> 
> > I wanted to share my findings early in case someone has any hints
> > for me.
> > 
> > To reproduce, use the following file as a drop in replacement of
> > libbpf-boostrap's examples/c/tc.bpf.c:
> 
> I reproduced the issue on 6.11.6, the highest RULE_LIST_SIZE that
> works for me is 35, but I currently lack time to take a deeper look.
> Do you have any new findings in the meanwhile?

No, I haven't found anything obvious. My current hypothesis is that
because we new assign IDs we lost some opportunities for state pruning.
In other words, states that were considered identical before the commit
are now considered distinct because of the IDs and thus can't be
pruned. This is a wild guess; I'm not very familiar with the verifier.

What's really odd is how big the jump is: from 380 to 35.

Cheers,
Francis