Repository navigation
Expand file tree
/
Copy pathbpf_filter.c
More file actions
561 lines (518 loc) · 15 KB
/
Copy pathbpf_filter.c
File metadata and controls
561 lines (518 loc) · 15 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
/* LWIP service - bpf_filter.c - Berkeley Packet Filter core implementation */
/*
* This is basically a drop-in replacement of NetBSD's bpf_filter.c, which
* itself can be compiled for either the NetBSD kernel or for userland. On
* MINIX 3, we would like to perform certain checks that NetBSD implements only
* for its kernel (e.g., memory store access validation) while replacing the
* NetBSD kernel specifics with our own (pbuf instead of mbuf, no BPF contexts
* for now, etc.). As a result, it is easier to reimplement the whole thing,
* because there is not all that much to it.
*
* Support for the standard BSD API allows us to run standard tests against
* this module from userland, where _MINIX_SYSTEM is not defined. MINIX 3
* specific extensions are enabled only if _MINIX_SYSTEM is defined.
*/
#include <string.h>
#include <limits.h>
#include <net/bpf.h>
#include <minix/bitmap.h>
#ifdef _MINIX_SYSTEM
#include "lwip.h"
/*
* Obtain an unsigned 32-bit value in network byte order from the pbuf chain
* 'pbuf' at offset 'k'. The given offset is guaranteed to be within bounds.
*/
static uint32_t
bpf_get32_ext(const struct pbuf * pbuf, uint32_t k)
{
uint32_t val;
unsigned int i;
/*
* Find the pbuf that contains the first byte. We expect that most
* filters will operate only on the headers of packets, so that we
* mostly avoid going through this O(n) loop. Since only the superuser
* can open BPF devices at all, we need not be worried about abuse in
* this regard. However, it turns out that this loop is particularly
* CPU-intensive after all, we can probably improve it by caching the
* last visited pbuf, as read locality is likely high.
*/
while (k >= pbuf->len) {
k -= pbuf->len;
pbuf = pbuf->next;
assert(pbuf != NULL);
}
/*
* We assume that every pbuf has some data, but we make no assumptions
* about any minimum amount of data per pbuf. Therefore, we may have
* to take the bytes from anywhere between one and four pbufs.
* Hopefully the compiler will unroll this loop for us.
*/
val = (uint32_t)(((u_char *)pbuf->payload)[k]) << 24;
for (i = 0; i < 3; i++) {
if (k >= (uint32_t)pbuf->len - 1) {
k = 0;
pbuf = pbuf->next;
assert(pbuf != NULL);
} else
k++;
val = (val << 8) | (uint32_t)(((u_char *)pbuf->payload)[k]);
}
return val;
}
/*
* Obtain an unsigned 16-bit value in network byte order from the pbuf chain
* 'pbuf' at offset 'k'. The given offset is guaranteed to be within bounds.
*/
static uint32_t
bpf_get16_ext(const struct pbuf * pbuf, uint32_t k)
{
/* As above. */
while (k >= pbuf->len) {
k -= pbuf->len;
pbuf = pbuf->next;
assert(pbuf != NULL);
}
/*
* There are only two possible cases to cover here: either the two
* bytes are in the same pbuf, or they are in subsequent ones.
*/
if (k < (uint32_t)pbuf->len - 1) {
return ((uint32_t)(((u_char *)pbuf->payload)[k]) << 8) |
(uint32_t)(((u_char *)pbuf->next->payload)[k + 1]);
} else {
assert(pbuf->next != NULL);
return ((uint32_t)(((u_char *)pbuf->payload)[k]) << 8) |
(uint32_t)(((u_char *)pbuf->next->payload)[0]);
}
}
/*
* Obtain an unsigned 8-bit value from the pbuf chain 'pbuf' at offset 'k'.
* The given offset is guaranteed to be within bounds.
*/
static uint32_t
bpf_get8_ext(const struct pbuf * pbuf, uint32_t k)
{
/* As above. */
while (k >= pbuf->len) {
k -= pbuf->len;
pbuf = pbuf->next;
assert(pbuf != NULL);
}
return (uint32_t)(((u_char *)pbuf->payload)[k]);
}
#endif /* _MINIX_SYSTEM */
/*
* Execute a BPF filter program on (the first part of) a packet, and return the
* maximum size of the packet that should be delivered to the filter owner.
*
* The 'pc' parameter points to an array of BPF instructions that together form
* the filter program to be executed. If 'pc' is NULL, the packet is fully
* accepted. Otherwise, the given program MUST have passed a previous call to
* bpf_validate(). Not doing so will allow for arbitrary memory access.
*
* The 'packet' array contains up to the whole packet. The value of 'total'
* denotes the total length of the packet; 'len' contains the size of the array
* 'packet'. Chunked storage of the packet is not supported at this time.
*
* If executing the program succeeds, the return value is the maximum number of
* bytes from the packet to be delivered. The return value may exceed the full
* packet size. If the number of bytes returned is zero, the packet is to be
* ignored. If the program fails to execute properly and return a value, a
* value of zero is returned as well, thus also indicating that the packet
* should be ignored. This is intentional: it saves filter programs from
* having to perform explicit checks on the packet they are filtering.
*/
u_int
bpf_filter(const struct bpf_insn * pc, const u_char * packet, u_int total,
u_int len)
#ifdef _MINIX_SYSTEM
{
return bpf_filter_ext(pc, NULL /*pbuf*/, packet, total, len);
}
u_int
bpf_filter_ext(const struct bpf_insn * pc, const struct pbuf * pbuf,
const u_char * packet, u_int total, u_int len)
#endif /* _MINIX_SYSTEM */
{
uint32_t k, a, x, mem[BPF_MEMWORDS];
/* An empty program accepts all packets. */
if (pc == NULL)
return UINT_MAX;
/*
* We need not clear 'mem': the checker guarantees that each memory
* store word is always written before it is read.
*/
a = 0;
x = 0;
/* Execute the program. */
for (;; pc++) {
k = pc->k;
switch (pc->code) {
case BPF_LD+BPF_W+BPF_IND: /* A <- P[X+k:4] */
if (k + x < k)
return 0;
k += x;
/* FALLTHROUGH */
case BPF_LD+BPF_W+BPF_ABS: /* A <- P[k:4] */
/*
* 'k' may have any value, so check bounds in such a
* way that 'k' cannot possibly overflow and wrap.
*/
if (len >= 3 && k < len - 3)
a = ((uint32_t)packet[k] << 24) |
((uint32_t)packet[k + 1] << 16) |
((uint32_t)packet[k + 2] << 8) |
(uint32_t)packet[k + 3];
#ifdef _MINIX_SYSTEM
else if (total >= 3 && k < total - 3)
a = bpf_get32_ext(pbuf, k);
#endif /* _MINIX_SYSTEM */
else
return 0;
break;
case BPF_LD+BPF_H+BPF_IND: /* A <- P[X+k:2] */
if (k + x < k)
return 0;
k += x;
/* FALLTHROUGH */
case BPF_LD+BPF_H+BPF_ABS: /* A <- P[k:2] */
/* As above. */
if (len >= 1 && k < len - 1)
a = ((uint32_t)packet[k] << 8) |
(uint32_t)packet[k + 1];
#ifdef _MINIX_SYSTEM
else if (total >= 1 && k < total - 1)
a = bpf_get16_ext(pbuf, k);
#endif /* _MINIX_SYSTEM */
else
return 0;
break;
case BPF_LD+BPF_B+BPF_IND: /* A <- P[X+k:1] */
if (k + x < k)
return 0;
k += x;
/* FALLTHROUGH */
case BPF_LD+BPF_B+BPF_ABS: /* A <- P[k:1] */
if (k < len)
a = (uint32_t)packet[k];
#ifdef _MINIX_SYSTEM
else if (k < total)
a = bpf_get8_ext(pbuf, k);
#endif /* _MINIX_SYSTEM */
else
return 0;
break;
case BPF_LD+BPF_W+BPF_LEN: /* A <- len */
a = total;
break;
case BPF_LD+BPF_IMM: /* A <- k */
a = k;
break;
case BPF_LD+BPF_MEM: /* A <- M[k] */
a = mem[k];
break;
case BPF_LDX+BPF_IMM: /* X <- k */
x = k;
break;
case BPF_LDX+BPF_MEM: /* X <- M[k] */
x = mem[k];
break;
case BPF_LDX+BPF_LEN: /* X <- len */
x = total;
break;
case BPF_LDX+BPF_B+BPF_MSH: /* X <- 4*(P[k:1]&0xf) */
if (k < len)
x = ((uint32_t)packet[k] & 0xf) << 2;
#ifdef _MINIX_SYSTEM
else if (k < total)
x = (bpf_get8_ext(pbuf, k) & 0xf) << 2;
#endif /* _MINIX_SYSTEM */
else
return 0;
break;
case BPF_ST: /* M[k] <- A */
mem[k] = a;
break;
case BPF_STX: /* M[k] <- X */
mem[k] = x;
break;
case BPF_ALU+BPF_ADD+BPF_K: /* A <- A + k */
a += k;
break;
case BPF_ALU+BPF_SUB+BPF_K: /* A <- A - k */
a -= k;
break;
case BPF_ALU+BPF_MUL+BPF_K: /* A <- A * k */
a *= k;
break;
case BPF_ALU+BPF_DIV+BPF_K: /* A <- A / k */
a /= k;
break;
case BPF_ALU+BPF_MOD+BPF_K: /* A <- A % k */
a %= k;
break;
case BPF_ALU+BPF_AND+BPF_K: /* A <- A & k */
a &= k;
break;
case BPF_ALU+BPF_OR+BPF_K: /* A <- A | k */
a |= k;
break;
case BPF_ALU+BPF_XOR+BPF_K: /* A <- A ^ k */
a ^= k;
break;
case BPF_ALU+BPF_LSH+BPF_K: /* A <- A << k */
a <<= k;
break;
case BPF_ALU+BPF_RSH+BPF_K: /* A <- A >> k */
a >>= k;
break;
case BPF_ALU+BPF_ADD+BPF_X: /* A <- A + X */
a += x;
break;
case BPF_ALU+BPF_SUB+BPF_X: /* A <- A - X */
a -= x;
break;
case BPF_ALU+BPF_MUL+BPF_X: /* A <- A * X */
a *= x;
break;
case BPF_ALU+BPF_DIV+BPF_X: /* A <- A / X */
if (x == 0)
return 0;
a /= x;
break;
case BPF_ALU+BPF_MOD+BPF_X: /* A <- A % X */
if (x == 0)
return 0;
a %= x;
break;
case BPF_ALU+BPF_AND+BPF_X: /* A <- A & X */
a &= x;
break;
case BPF_ALU+BPF_OR+BPF_X: /* A <- A | X */
a |= x;
break;
case BPF_ALU+BPF_XOR+BPF_X: /* A <- A ^ X */
a ^= x;
break;
case BPF_ALU+BPF_LSH+BPF_X: /* A <- A << X */
if (x >= 32)
return 0;
a <<= x;
break;
case BPF_ALU+BPF_RSH+BPF_X: /* A <- A >> X */
if (x >= 32)
return 0;
a >>= x;
break;
case BPF_ALU+BPF_NEG: /* A <- -A */
a = -a;
break;
case BPF_JMP+BPF_JA: /* pc += k */
pc += k;
break;
case BPF_JMP+BPF_JGT+BPF_K: /* pc += (A > k) ? jt : jf */
pc += (a > k) ? pc->jt : pc->jf;
break;
case BPF_JMP+BPF_JGE+BPF_K: /* pc += (A >= k) ? jt : jf */
pc += (a >= k) ? pc->jt : pc->jf;
break;
case BPF_JMP+BPF_JEQ+BPF_K: /* pc += (A == k) ? jt : jf */
pc += (a == k) ? pc->jt : pc->jf;
break;
case BPF_JMP+BPF_JSET+BPF_K: /* pc += (A & k) ? jt : jf */
pc += (a & k) ? pc->jt : pc->jf;
break;
case BPF_JMP+BPF_JGT+BPF_X: /* pc += (A > X) ? jt : jf */
pc += (a > x) ? pc->jt : pc->jf;
break;
case BPF_JMP+BPF_JGE+BPF_X: /* pc += (A >= X) ? jt : jf */
pc += (a >= x) ? pc->jt : pc->jf;
break;
case BPF_
8000
JMP+BPF_JEQ+BPF_X: /* pc += (A == X) ? jt : jf */
pc += (a == x) ? pc->jt : pc->jf;
break;
case BPF_JMP+BPF_JSET+BPF_X: /* pc += (A & X) ? jt : jf */
pc += (a & x) ? pc->jt : pc->jf;
break;
case BPF_RET+BPF_A: /* accept A bytes */
return a;
case BPF_RET+BPF_K: /* accept K bytes */
return k;
case BPF_MISC+BPF_TAX: /* X <- A */
x = a;
break;
case BPF_MISC+BPF_TXA: /* A <- X */
a = x;
break;
default: /* unknown instruction */
return 0;
}
}
/* NOTREACHED */
}
/*
* In order to avoid having to perform explicit memory allocation, we store
* some validation state on the stack, using data types that are as small as
* possible for the current definitions. The data types, and in fact the whole
* assumption that we can store the state on the stack, may need to be revised
* if certain constants are increased in the future. As of writing, the
* validation routine uses a little over 1KB of stack memory.
*/
#if BPF_MEMWORDS <= 16 /* value as of writing: 16 */
typedef uint16_t meminv_t;
#else
#error "increased BPF_MEMWORDS may require code revision"
#endif
#if BPF_MAXINSNS > 2048 /* value as of writing: 512 */
#error "increased BPF_MAXINSNS may require code revision"
#endif
/*
* Verify that the given filter program is safe to execute, by performing as
* many static validity checks as possible. The program is given as 'insns',
* which must be an array of 'ninsns' BPF instructions. Unlike bpf_filter(),
* this function does not accept empty filter programs. The function returns 1
* if the program was successfully validated, or 0 if the program should not be
* accepted.
*/
int
bpf_validate(const struct bpf_insn * insns, int ninsns)
{
bitchunk_t reachable[BITMAP_CHUNKS(BPF_MAXINSNS)];
meminv_t invalid, meminv[BPF_MAXINSNS];
const struct bpf_insn *insn;
u_int pc, count, target;
int advance;
if (insns == NULL || ninsns <= 0 || ninsns > BPF_MAXINSNS)
return 0;
count = (u_int)ninsns;
memset(reachable, 0, sizeof(reachable[0]) * BITMAP_CHUNKS(count));
memset(meminv, 0, sizeof(meminv[0]) * count);
SET_BIT(reachable, 0);
meminv[0] = (meminv_t)~0;
for (pc = 0; pc < count; pc++) {
/* We completely ignore instructions that are not reachable. */
if (!GET_BIT(reachable, pc))
continue;
invalid = meminv[pc];
advance = 1;
insn = &insns[pc];
switch (insn->code) {
case BPF_LD+BPF_W+BPF_ABS:
case BPF_LD+BPF_H+BPF_ABS:
case BPF_LD+BPF_B+BPF_ABS:
case BPF_LD+BPF_W+BPF_IND:
case BPF_LD+BPF_H+BPF_IND:
case BPF_LD+BPF_B+BPF_IND:
case BPF_LD+BPF_LEN:
case BPF_LD+BPF_IMM:
case BPF_LDX+BPF_IMM:
case BPF_LDX+BPF_LEN:
case BPF_LDX+BPF_B+BPF_MSH:
case BPF_ALU+BPF_ADD+BPF_K:
case BPF_ALU+BPF_SUB+BPF_K:
case BPF_ALU+BPF_MUL+BPF_K:
case BPF_ALU+BPF_AND+BPF_K:
case BPF_ALU+BPF_OR+BPF_K:
case BPF_ALU+BPF_XOR+BPF_K:
case BPF_ALU+BPF_ADD+BPF_X:
case BPF_ALU+BPF_SUB+BPF_X:
case BPF_ALU+BPF_MUL+BPF_X:
case BPF_ALU+BPF_DIV+BPF_X:
case BPF_ALU+BPF_MOD+BPF_X:
case BPF_ALU+BPF_AND+BPF_X:
case BPF_ALU+BPF_OR+BPF_X:
case BPF_ALU+BPF_XOR+BPF_X:
case BPF_ALU+BPF_LSH+BPF_X:
case BPF_ALU+BPF_RSH+BPF_X:
case BPF_ALU+BPF_NEG:
case BPF_MISC+BPF_TAX:
case BPF_MISC+BPF_TXA:
/* Nothing we can check for these. */
break;
case BPF_ALU+BPF_DIV+BPF_K:
case BPF_ALU+BPF_MOD+BPF_K:
/* No division by zero. */
if (insn->k == 0)
return 0;
break;
case BPF_ALU+BPF_LSH+BPF_K:
case BPF_ALU+BPF_RSH+BPF_K:
/* Do not invoke undefined behavior. */
if (insn->k >= 32)
return 0;
break;
case BPF_LD+BPF_MEM:
case BPF_LDX+BPF_MEM:
/*
* Only allow loading words that have been stored in
* all execution paths leading up to this instruction.
*/
if (insn->k >= BPF_MEMWORDS ||
(invalid & (1 << insn->k)))
return 0;
break;
case BPF_ST:
case BPF_STX:
if (insn->k >= BPF_MEMWORDS)
return 0;
invalid &= ~(1 << insn->k);
break;
case BPF_JMP+BPF_JA:
/*
* Make sure that the target instruction of the jump is
* still part of the program, and mark it as reachable.
*/
if (insn->k >= count - pc - 1)
return 0;
target = pc + insn->k + 1;
SET_BIT(reachable, target);
meminv[target] |= invalid;
advance = 0;
break;
case BPF_JMP+BPF_JGT+BPF_K:
case BPF_JMP+BPF_JGE+BPF_K:
case BPF_JMP+BPF_JEQ+BPF_K:
case BPF_JMP+BPF_JSET+BPF_K:
case BPF_JMP+BPF_JGT+BPF_X:
case BPF_JMP+BPF_JGE+BPF_X:
case BPF_JMP+BPF_JEQ+BPF_X:
case BPF_JMP+BPF_JSET+BPF_X:
/*
* Make sure that both target instructions are still
* part of the program, and mark both as reachable.
* There is no chance that the additions will overflow.
*/
target = pc + insn->jt + 1;
if (target >= count)
return 0;
SET_BIT(reachable, target);
meminv[target] |= invalid;
target = pc + insn->jf + 1;
if (target >= count)
return 0;
SET_BIT(reachable, target);
meminv[target] |= invalid;
advance = 0;
break;
case BPF_RET+BPF_A:
case BPF_RET+BPF_K:
advance = 0;
break;
default:
return 0;
}
/*
* After most instructions, we simply advance to the next. For
* one thing, this means that there must be a next instruction
* at all.
*/
if (advance) {
if (pc + 1 == count)
return 0;
SET_BIT(reachable, pc + 1);
meminv[pc + 1] |= invalid;
}
}
/* The program has passed all our basic tests. */
return 1;
}