bpf: allow access into map value arrays

Suppose you have a map array value that is something like this

struct foo {
	unsigned iter;
	int array[SOME_CONSTANT];
};

You can easily insert this into an array, but you cannot modify the contents of
foo->array[] after the fact.  This is because we have no way to verify we won't
go off the end of the array at verification time.  This patch provides a start
for this work.  We accomplish this by keeping track of a minimum and maximum
value a register could be while we're checking the code.  Then at the time we
try to do an access into a MAP_VALUE we verify that the maximum offset into that
region is a valid access into that memory region.  So in practice, code such as
this

unsigned index = 0;

if (foo->iter >= SOME_CONSTANT)
	foo->iter = index;
else
	index = foo->iter++;
foo->array[index] = bar;

would be allowed, as we can verify that index will always be between 0 and
SOME_CONSTANT-1.  If you wish to use signed values you'll have to have an extra
check to make sure the index isn't less than 0, or do something like index %=
SOME_CONSTANT.

Signed-off-by: Josef Bacik <jbacik@fb.com>
Acked-by: Alexei Starovoitov <ast@kernel.org>
Signed-off-by: David S. Miller <davem@davemloft.net>

2 files changed, 247 insertions, 4 deletions

diff --git a/samples/bpf/libbpf.h b/samples/bpf/libbpf.h
index 364582b77888..ac6edb61b64a 100644
--- a/samples/bpf/libbpf.h
+++ b/samples/bpf/libbpf.h
@@ -85,6 +85,14 @@ extern char bpf_log_buf[LOG_BUF_SIZE];
                 .off   = 0,                                     \
                 .imm   = IMM })
 
+#define BPF_MOV32_IMM(DST, IMM)                                 \
+        ((struct bpf_insn) {                                    \
+                .code  = BPF_ALU | BPF_MOV | BPF_K,             \
+                .dst_reg = DST,                                 \
+                .src_reg = 0,                                   \
+                .off   = 0,                                     \
+                .imm   = IMM })
+
 /* BPF_LD_IMM64 macro encodes single 'load 64-bit immediate' insn */
 #define BPF_LD_IMM64(DST, IMM)                                  \
         BPF_LD_IMM64_RAW(DST, 0, IMM)
diff --git a/samples/bpf/test_verifier.c b/samples/bpf/test_verifier.c
index ac590d4b7f02..369ffaad3799 100644
--- a/samples/bpf/test_verifier.c
+++ b/samples/bpf/test_verifier.c
@@ -29,6 +29,7 @@ struct bpf_test {
         struct bpf_insn insns[MAX_INSNS];
         int fixup[MAX_FIXUPS];
         int prog_array_fixup[MAX_FIXUPS];
+        int test_val_map_fixup[MAX_FIXUPS];
         const char *errstr;
         const char *errstr_unpriv;
         enum {
@@ -39,6 +40,19 @@ struct bpf_test {
         enum bpf_prog_type prog_type;
 };
 
+/* Note we want this to be 64 bit aligned so that the end of our array is
+ * actually the end of the structure.
+ */
+#define MAX_ENTRIES 11
+struct test_val {
+        unsigned index;
+        int foo[MAX_ENTRIES];
+};
+
+struct other_val {
+        unsigned int action[32];
+};
+
 static struct bpf_test tests[] = {
         {
                 "add+sub+mul",
@@ -2163,6 +2177,212 @@ static struct bpf_test tests[] = {
                 .errstr = "invalid access to packet",
                 .prog_type = BPF_PROG_TYPE_SCHED_CLS,
         },
+        {
+                "valid map access into an array with a constant",
+                .insns = {
+                        BPF_ST_MEM(BPF_DW, BPF_REG_10, -8, 0),
+                        BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
+                        BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),
+                        BPF_LD_MAP_FD(BPF_REG_1, 0),
+                        BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_lookup_elem),
+                        BPF_JMP_IMM(BPF_JEQ, BPF_REG_0, 0, 1),
+                        BPF_ST_MEM(BPF_DW, BPF_REG_0, 0, offsetof(struct test_val, foo)),
+                        BPF_EXIT_INSN(),
+                },
+                .test_val_map_fixup = {3},
+                .errstr_unpriv = "R0 leaks addr",
+                .result_unpriv = REJECT,
+                .result = ACCEPT,
+        },
+        {
+                "valid map access into an array with a register",
+                .insns = {
+                        BPF_ST_MEM(BPF_DW, BPF_REG_10, -8, 0),
+                        BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
+                        BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),
+                        BPF_LD_MAP_FD(BPF_REG_1, 0),
+                        BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_lookup_elem),
+                        BPF_JMP_IMM(BPF_JEQ, BPF_REG_0, 0, 4),
+                        BPF_MOV64_IMM(BPF_REG_1, 4),
+                        BPF_ALU64_IMM(BPF_LSH, BPF_REG_1, 2),
+                        BPF_ALU64_REG(BPF_ADD, BPF_REG_0, BPF_REG_1),
+                        BPF_ST_MEM(BPF_DW, BPF_REG_0, 0, offsetof(struct test_val, foo)),
+                        BPF_EXIT_INSN(),
+                },
+                .test_val_map_fixup = {3},
+                .errstr_unpriv = "R0 leaks addr",
+                .result_unpriv = REJECT,
+                .result = ACCEPT,
+        },
+        {
+                "valid map access into an array with a variable",
+                .insns = {
+                        BPF_ST_MEM(BPF_DW, BPF_REG_10, -8, 0),
+                        BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
+                        BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),
+                        BPF_LD_MAP_FD(BPF_REG_1, 0),
+                        BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_lookup_elem),
+                        BPF_JMP_IMM(BPF_JEQ, BPF_REG_0, 0, 5),
+                        BPF_LDX_MEM(BPF_W, BPF_REG_1, BPF_REG_0, 0),
+                        BPF_JMP_IMM(BPF_JGE, BPF_REG_1, MAX_ENTRIES, 3),
+                        BPF_ALU64_IMM(BPF_LSH, BPF_REG_1, 2),
+                        BPF_ALU64_REG(BPF_ADD, BPF_REG_0, BPF_REG_1),
+                        BPF_ST_MEM(BPF_DW, BPF_REG_0, 0, offsetof(struct test_val, foo)),
+                        BPF_EXIT_INSN(),
+                },
+                .test_val_map_fixup = {3},
+                .errstr_unpriv = "R0 leaks addr",
+                .result_unpriv = REJECT,
+                .result = ACCEPT,
+        },
+        {
+                "valid map access into an array with a signed variable",
+                .insns = {
+                        BPF_ST_MEM(BPF_DW, BPF_REG_10, -8, 0),
+                        BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
+                        BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),
+                        BPF_LD_MAP_FD(BPF_REG_1, 0),
+                        BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_lookup_elem),
+                        BPF_JMP_IMM(BPF_JEQ, BPF_REG_0, 0, 9),
+                        BPF_LDX_MEM(BPF_W, BPF_REG_1, BPF_REG_0, 0),
+                        BPF_JMP_IMM(BPF_JSGT, BPF_REG_1, 0xffffffff, 1),
+                        BPF_MOV32_IMM(BPF_REG_1, 0),
+                        BPF_MOV32_IMM(BPF_REG_2, MAX_ENTRIES),
+                        BPF_JMP_REG(BPF_JSGT, BPF_REG_2, BPF_REG_1, 1),
+                        BPF_MOV32_IMM(BPF_REG_1, 0),
+                        BPF_ALU32_IMM(BPF_LSH, BPF_REG_1, 2),
+                        BPF_ALU64_REG(BPF_ADD, BPF_REG_0, BPF_REG_1),
+                        BPF_ST_MEM(BPF_DW, BPF_REG_0, 0, offsetof(struct test_val, foo)),
+                        BPF_EXIT_INSN(),
+                },
+                .test_val_map_fixup = {3},
+                .errstr_unpriv = "R0 leaks addr",
+                .result_unpriv = REJECT,
+                .result = ACCEPT,
+        },
+        {
+                "invalid map access into an array with a constant",
+                .insns = {
+                        BPF_ST_MEM(BPF_DW, BPF_REG_10, -8, 0),
+                        BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
+                        BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),
+                        BPF_LD_MAP_FD(BPF_REG_1, 0),
+                        BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_lookup_elem),
+                        BPF_JMP_IMM(BPF_JEQ, BPF_REG_0, 0, 1),
+                        BPF_ST_MEM(BPF_DW, BPF_REG_0, (MAX_ENTRIES + 1) << 2,
+                                   offsetof(struct test_val, foo)),
+                        BPF_EXIT_INSN(),
+                },
+                .test_val_map_fixup = {3},
+                .errstr = "invalid access to map value, value_size=48 off=48 size=8",
+                .result = REJECT,
+        },
+        {
+                "invalid map access into an array with a register",
+                .insns = {
+                        BPF_ST_MEM(BPF_DW, BPF_REG_10, -8, 0),
+                        BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
+                        BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),
+                        BPF_LD_MAP_FD(BPF_REG_1, 0),
+                        BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_lookup_elem),
+                        BPF_JMP_IMM(BPF_JEQ, BPF_REG_0, 0, 4),
+                        BPF_MOV64_IMM(BPF_REG_1, MAX_ENTRIES + 1),
+                        BPF_ALU64_IMM(BPF_LSH, BPF_REG_1, 2),
+                        BPF_ALU64_REG(BPF_ADD, BPF_REG_0, BPF_REG_1),
+                        BPF_ST_MEM(BPF_DW, BPF_REG_0, 0, offsetof(struct test_val, foo)),
+                        BPF_EXIT_INSN(),
+                },
+                .test_val_map_fixup = {3},
+                .errstr = "R0 min value is outside of the array range",
+                .result = REJECT,
+        },
+        {
+                "invalid map access into an array with a variable",
+                .insns = {
+                        BPF_ST_MEM(BPF_DW, BPF_REG_10, -8, 0),
+                        BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
+                        BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),
+                        BPF_LD_MAP_FD(BPF_REG_1, 0),
+                        BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_lookup_elem),
+                        BPF_JMP_IMM(BPF_JEQ, BPF_REG_0, 0, 4),
+                        BPF_LDX_MEM(BPF_W, BPF_REG_1, BPF_REG_0, 0),
+                        BPF_ALU64_IMM(BPF_LSH, BPF_REG_1, 2),
+                        BPF_ALU64_REG(BPF_ADD, BPF_REG_0, BPF_REG_1),
+                        BPF_ST_MEM(BPF_DW, BPF_REG_0, 0, offsetof(struct test_val, foo)),
+                        BPF_EXIT_INSN(),
+                },
+                .test_val_map_fixup = {3},
+                .errstr = "R0 min value is negative, either use unsigned index or do a if (index >=0) check.",
+                .result = REJECT,
+        },
+        {
+                "invalid map access into an array with no floor check",
+                .insns = {
+                        BPF_ST_MEM(BPF_DW, BPF_REG_10, -8, 0),
+                        BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
+                        BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),
+                        BPF_LD_MAP_FD(BPF_REG_1, 0),
+                        BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_lookup_elem),
+                        BPF_JMP_IMM(BPF_JEQ, BPF_REG_0, 0, 7),
+                        BPF_LDX_MEM(BPF_W, BPF_REG_1, BPF_REG_0, 0),
+                        BPF_MOV32_IMM(BPF_REG_2, MAX_ENTRIES),
+                        BPF_JMP_REG(BPF_JSGT, BPF_REG_2, BPF_REG_1, 1),
+                        BPF_MOV32_IMM(BPF_REG_1, 0),
+                        BPF_ALU32_IMM(BPF_LSH, BPF_REG_1, 2),
+                        BPF_ALU64_REG(BPF_ADD, BPF_REG_0, BPF_REG_1),
+                        BPF_ST_MEM(BPF_DW, BPF_REG_0, 0, offsetof(struct test_val, foo)),
+                        BPF_EXIT_INSN(),
+                },
+                .test_val_map_fixup = {3},
+                .errstr = "R0 min value is negative, either use unsigned index or do a if (index >=0) check.",
+                .result = REJECT,
+        },
+        {
+                "invalid map access into an array with a invalid max check",
+                .insns = {
+                        BPF_ST_MEM(BPF_DW, BPF_REG_10, -8, 0),
+                        BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
+                        BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),
+                        BPF_LD_MAP_FD(BPF_REG_1, 0),
+                        BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_lookup_elem),
+                        BPF_JMP_IMM(BPF_JEQ, BPF_REG_0, 0, 7),
+                        BPF_LDX_MEM(BPF_W, BPF_REG_1, BPF_REG_0, 0),
+                        BPF_MOV32_IMM(BPF_REG_2, MAX_ENTRIES + 1),
+                        BPF_JMP_REG(BPF_JGT, BPF_REG_2, BPF_REG_1, 1),
+                        BPF_MOV32_IMM(BPF_REG_1, 0),
+                        BPF_ALU32_IMM(BPF_LSH, BPF_REG_1, 2),
+                        BPF_ALU64_REG(BPF_ADD, BPF_REG_0, BPF_REG_1),
+                        BPF_ST_MEM(BPF_DW, BPF_REG_0, 0, offsetof(struct test_val, foo)),
+                        BPF_EXIT_INSN(),
+                },
+                .test_val_map_fixup = {3},
+                .errstr = "invalid access to map value, value_size=48 off=44 size=8",
+                .result = REJECT,
+        },
+        {
+                "invalid map access into an array with a invalid max check",
+                .insns = {
+                        BPF_ST_MEM(BPF_DW, BPF_REG_10, -8, 0),
+                        BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
+                        BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),
+                        BPF_LD_MAP_FD(BPF_REG_1, 0),
+                        BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_lookup_elem),
+                        BPF_JMP_IMM(BPF_JEQ, BPF_REG_0, 0, 10),
+                        BPF_MOV64_REG(BPF_REG_8, BPF_REG_0),
+                        BPF_ST_MEM(BPF_DW, BPF_REG_10, -8, 0),
+                        BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
+                        BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),
+                        BPF_LD_MAP_FD(BPF_REG_1, 0),
+                        BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_lookup_elem),
+                        BPF_JMP_IMM(BPF_JEQ, BPF_REG_0, 0, 2),
+                        BPF_ALU64_REG(BPF_ADD, BPF_REG_0, BPF_REG_8),
+                        BPF_LDX_MEM(BPF_W, BPF_REG_0, BPF_REG_0, offsetof(struct test_val, foo)),
+                        BPF_EXIT_INSN(),
+                },
+                .test_val_map_fixup = {3, 11},
+                .errstr = "R0 min value is negative, either use unsigned index or do a if (index >=0) check.",
+                .result = REJECT,
+        },
 };
 
 static int probe_filter_length(struct bpf_insn *fp)
@@ -2176,12 +2396,12 @@ static int probe_filter_length(struct bpf_insn *fp)
         return len + 1;
 }
 
-static int create_map(void)
+static int create_map(size_t val_size, int num)
 {
         int map_fd;
 
         map_fd = bpf_create_map(BPF_MAP_TYPE_HASH,
-                                sizeof(long long), sizeof(long long), 1024, 0);
+                                sizeof(long long), val_size, num, 0);
         if (map_fd < 0)
                 printf("failed to create map '%s'\n", strerror(errno));
 
@@ -2211,12 +2431,13 @@ static int test(void)
                 int prog_len = probe_filter_length(prog);
                 int *fixup = tests[i].fixup;
                 int *prog_array_fixup = tests[i].prog_array_fixup;
+                int *test_val_map_fixup = tests[i].test_val_map_fixup;
                 int expected_result;
                 const char *expected_errstr;
-                int map_fd = -1, prog_array_fd = -1;
+                int map_fd = -1, prog_array_fd = -1, test_val_map_fd = -1;
 
                 if (*fixup) {
-                        map_fd = create_map();
+                        map_fd = create_map(sizeof(long long), 1024);
 
                         do {
                                 prog[*fixup].imm = map_fd;
@@ -2231,6 +2452,18 @@ static int test(void)
                                 prog_array_fixup++;
                         } while (*prog_array_fixup);
                 }
+                if (*test_val_map_fixup) {
+                        /* Unprivileged can't create a hash map.*/
+                        if (unpriv)
+                                continue;
+                        test_val_map_fd = create_map(sizeof(struct test_val),
+                                                     256);
+                        do {
+                                prog[*test_val_map_fixup].imm = test_val_map_fd;
+                                test_val_map_fixup++;
+                        } while (*test_val_map_fixup);
+                }
+
                 printf("#%d %s ", i, tests[i].descr);
 
                 prog_fd = bpf_prog_load(prog_type ?: BPF_PROG_TYPE_SOCKET_FILTER,
@@ -2277,6 +2510,8 @@ fail:
                         close(map_fd);
                 if (prog_array_fd >= 0)
                         close(prog_array_fd);
+                if (test_val_map_fd >= 0)
+                        close(test_val_map_fd);
                 close(prog_fd);
 
         }