1

I am trying to write a BPF TC program to filter network packets based on its payload. I extract first few bytes of the payload into a buffer and try to do a substring search in that buffer. However my BPF program fails verification with error: invalid access to memory, mem_size=1 off=1 size=1 R3 min value is outside of the allowed memory range

Here is the common.h

#define MAX_RULES 50
#define MAX_RULE_NAME 20
#define MAX_BYTE_PATTERN 11

struct filter_rule
{
   char rule_name[MAX_RULE_NAME];
   char byte_pattern[MAX_BYTE_PATTERN];
};

unsigned char mystrlen(const char *s, unsigned char max_len)
{
    unsigned char i = 0;
    if(s == NULL)
       return 0;
    for (i = 0; i < max_len; i++)
    {
       if (s[i] == '\0')
          return i;
    }
    return i;
}

bool find_substring(const char *str, const char *search)
{
   if(str != NULL && search != NULL)
   {
      unsigned char l1 = mystrlen(str,50);
      unsigned char l2 = mystrlen(search, MAX_BYTE_PATTERN);
      unsigned char i = 0, j = 0;
      unsigned char flag = 0;
      if(l1 == 0 || l2 == 0)
         return false;
      for (i = 0; i <= l1 - l2; i++)
      {
         for (j = i; j < i + l2; j++)
         {
            flag = 1;
            if (str[j] != search[j - i])
            {
               flag = 0;
               break;
            }
         }
         if (flag == 1)
         {
            break;
         }
      }
      if(flag == 1)
         return true;
      else
         return false;
   }
   else
   {
      return false;
   }
}

Here is logic of my bpf.c file:

unsigned long long load_byte(void *skb, unsigned long long off) asm("llvm.bpf.load.byte");

struct {
    __uint(type, BPF_MAP_TYPE_ARRAY);
    __uint(key_size, sizeof(int));
    __uint(value_size, sizeof(struct filter_rule));
    __uint(max_entries, MAX_RULES);
} filter_rules SEC(".maps");

SEC("tc")
int ingress_hndlr(struct __sk_buff *ctx)
{
   //Extract the TCP packet payload into buff
   unsigned char buff[51] = {0};
   for(int i = 0; i<tcp_payload_length && i<50; ++i)
   {
       buff[i] = load_byte(ctx, payload_offset+i);
       //bpf_printk("%x", buff[i]);
   }

   unsigned int key = 0;
   struct filter_rule *rule = bpf_map_lookup_elem(&filter_rules, &key);
   if(rule)
   {
       bool ret = find_substring((const char*)buff, rule->byte_pattern);
       if(ret)
       {
          ++drop_cnt;
          return TC_ACT_SHOT;
       }
   }
}

The error I get

Validating find_substring() func#1...
; bool find_substring(const char *str, const char *search)
189: (b7) r0 = 0
; if(str != NULL && search != NULL)
190: (15) if r1 == 0x0 goto pc+55
 R0_w=invP0 R1=mem(id=0,ref_obj_id=0,off=0,imm=0) R2=mem_or_null(id=4,ref_obj_id=0,off=0,imm=0) R10=fp0
191: (15) if r2 == 0x0 goto pc+54
 R0_w=invP0 R1=mem(id=0,ref_obj_id=0,off=0,imm=0) R2=mem(id=0,ref_obj_id=0,off=0,imm=0) R10=fp0
192: (b7) r4 = 0
; if (s[i] == '\0')
193: (bf) r3 = r1
194: (0f) r3 += r4
195: (71) r3 = *(u8 *)(r3 +0)
 R0_w=invP0 R1=mem(id=0,ref_obj_id=0,off=0,imm=0) R2=mem(id=0,ref_obj_id=0,off=0,imm=0) R3_w=mem(id=0,ref_obj_id=0,off=0,imm=0) R4_w=invP0 R10=fp0
; if (s[i] == '\0')
196: (15) if r3 == 0x0 goto pc+4
 R0=invP0 R1=mem(id=0,ref_obj_id=0,off=0,imm=0) R2=mem(id=0,ref_obj_id=0,off=0,imm=0) R3=invP(id=0,umax_value=255,var_off=(0x0; 0xff)) R4=invP0 R10=fp0
197: (b7) r3 = 50
; for (i = 0; i < max_len; i++)
198: (07) r4 += 1
; for (i = 0; i < max_len; i++)
199: (15) if r4 == 0x32 goto pc+2
200: (05) goto pc-8
; if (s[i] == '\0')
193: (bf) r3 = r1
194: (0f) r3 += r4
195: (71) r3 = *(u8 *)(r3 +0)
 R0=invP0 R1=mem(id=0,ref_obj_id=0,off=0,imm=0) R2=mem(id=0,ref_obj_id=0,off=0,imm=0) R3_w=mem(id=0,ref_obj_id=0,off=1,imm=0) R4_w=invP1 R10=fp0
invalid access to memory, mem_size=1 off=1 size=1
R3 min value is outside of the allowed memory range
processed 15 insns (limit 1000000) max_states_per_insn 0 total_states 1 peak_states 1 mark_read 1
-- END PROG LOAD LOG --
libbpf: prog 'ingress_hndlr': failed to load: -13
libbpf: failed to load object 'minimal_bpf'
libbpf: failed to load BPF skeleton 'minimal_bpf': -13
Failed to load and verify BPF skeleton

Can someone please guide me what this error means and how to solve this. I have tried applying checks everywhere in my code and also used unsigned variables.

unmukt jain
  • 11
  • 2

1 Answers1

1

The compiler generates a separate BPF function (aka subprog) for find_substring and attempts to validate it separately from the rest of your program. So the only thing it sees is a function that reads up to 50 bytes from a pointer, but it has no proof that that much memory is actually allocated since that is only evident if you regard the program as a whole.

The "fix" in this case is quite simple. Add __always_inline to the find_substring function like so: bool __always_inline find_substring(const char *str, const char *search).

This will inline the function, thus the verifier will always see that the pointers passed in are save to read from.

Dylan Reimerink
  • 5,874
  • 2
  • 15
  • 21