Skip to content

Commit 3db9128

Browse files
borkmannborkmann
committed
Merge branch 'bpf-verifier-sec-fixes'
Alexei Starovoitov says: ==================== This patch set addresses a set of security vulnerabilities in bpf verifier logic discovered by Jann Horn. All of the patches are candidates for 4.14 stable. ==================== Signed-off-by: Daniel Borkmann <daniel@iogearbox.net>
2 parents 19c832e + 2255f8d commit 3db9128

File tree

3 files changed

+661
-67
lines changed

3 files changed

+661
-67
lines changed

‎include/linux/bpf_verifier.h

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -15,11 +15,11 @@
1515
* In practice this is far bigger than any realistic pointer offset; this limit
1616
* ensures that umax_value + (int)off + (int)size cannot overflow a u64.
1717
*/
18-
#define BPF_MAX_VAR_OFF (1ULL << 31)
18+
#define BPF_MAX_VAR_OFF (1 << 29)
1919
/* Maximum variable size permitted for ARG_CONST_SIZE[_OR_ZERO]. This ensures
2020
* that converting umax_value to int cannot overflow.
2121
*/
22-
#define BPF_MAX_VAR_SIZ INT_MAX
22+
#define BPF_MAX_VAR_SIZ (1 << 29)
2323

2424
/* Liveness marks, used for registers and spilled-regs (in stack slots).
2525
* Read marks propagate upwards until they find a write mark; they record that

‎kernel/bpf/verifier.c

Lines changed: 126 additions & 49 deletions
Original file line numberDiff line numberDiff line change
@@ -1059,6 +1059,11 @@ static int check_ptr_alignment(struct bpf_verifier_env *env,
10591059
break;
10601060
case PTR_TO_STACK:
10611061
pointer_desc = "stack ";
1062+
/* The stack spill tracking logic in check_stack_write()
1063+
* and check_stack_read() relies on stack accesses being
1064+
* aligned.
1065+
*/
1066+
strict = true;
10621067
break;
10631068
default:
10641069
break;
@@ -1067,6 +1072,29 @@ static int check_ptr_alignment(struct bpf_verifier_env *env,
10671072
strict);
10681073
}
10691074

1075+
/* truncate register to smaller size (in bytes)
1076+
* must be called with size < BPF_REG_SIZE
1077+
*/
1078+
static void coerce_reg_to_size(struct bpf_reg_state *reg, int size)
1079+
{
1080+
u64 mask;
1081+
1082+
/* clear high bits in bit representation */
1083+
reg->var_off = tnum_cast(reg->var_off, size);
1084+
1085+
/* fix arithmetic bounds */
1086+
mask = ((u64)1 << (size * 8)) - 1;
1087+
if ((reg->umin_value & ~mask) == (reg->umax_value & ~mask)) {
1088+
reg->umin_value &= mask;
1089+
reg->umax_value &= mask;
1090+
} else {
1091+
reg->umin_value = 0;
1092+
reg->umax_value = mask;
1093+
}
1094+
reg->smin_value = reg->umin_value;
1095+
reg->smax_value = reg->umax_value;
1096+
}
1097+
10701098
/* check whether memory at (regno + off) is accessible for t = (read | write)
10711099
* if t==write, value_regno is a register which value is stored into memory
10721100
* if t==read, value_regno is a register which will receive the value from memory
@@ -1200,9 +1228,7 @@ static int check_mem_access(struct bpf_verifier_env *env, int insn_idx, u32 regn
12001228
if (!err && size < BPF_REG_SIZE && value_regno >= 0 && t == BPF_READ &&
12011229
regs[value_regno].type == SCALAR_VALUE) {
12021230
/* b/h/w load zero-extends, mark upper bits as known 0 */
1203-
regs[value_regno].var_off =
1204-
tnum_cast(regs[value_regno].var_off, size);
1205-
__update_reg_bounds(&regs[value_regno]);
1231+
coerce_reg_to_size(&regs[value_regno], size);
12061232
}
12071233
return err;
12081234
}
@@ -1282,6 +1308,7 @@ static int check_stack_boundary(struct bpf_verifier_env *env, int regno,
12821308
tnum_strn(tn_buf, sizeof(tn_buf), regs[regno].var_off);
12831309
verbose(env, "invalid variable stack read R%d var_off=%s\n",
12841310
regno, tn_buf);
1311+
return -EACCES;
12851312
}
12861313
off = regs[regno].off + regs[regno].var_off.value;
12871314
if (off >= 0 || off < -MAX_BPF_STACK || off + access_size > 0 ||
@@ -1772,14 +1799,6 @@ static int check_call(struct bpf_verifier_env *env, int func_id, int insn_idx)
17721799
return 0;
17731800
}
17741801

1775-
static void coerce_reg_to_32(struct bpf_reg_state *reg)
1776-
{
1777-
/* clear high 32 bits */
1778-
reg->var_off = tnum_cast(reg->var_off, 4);
1779-
/* Update bounds */
1780-
__update_reg_bounds(reg);
1781-
}
1782-
17831802
static bool signed_add_overflows(s64 a, s64 b)
17841803
{
17851804
/* Do the add in u64, where overflow is well-defined */
@@ -1800,6 +1819,41 @@ static bool signed_sub_overflows(s64 a, s64 b)
18001819
return res > a;
18011820
}
18021821

1822+
static bool check_reg_sane_offset(struct bpf_verifier_env *env,
1823+
const struct bpf_reg_state *reg,
1824+
enum bpf_reg_type type)
1825+
{
1826+
bool known = tnum_is_const(reg->var_off);
1827+
s64 val = reg->var_off.value;
1828+
s64 smin = reg->smin_value;
1829+
1830+
if (known && (val >= BPF_MAX_VAR_OFF || val <= -BPF_MAX_VAR_OFF)) {
1831+
verbose(env, "math between %s pointer and %lld is not allowed\n",
1832+
reg_type_str[type], val);
1833+
return false;
1834+
}
1835+
1836+
if (reg->off >= BPF_MAX_VAR_OFF || reg->off <= -BPF_MAX_VAR_OFF) {
1837+
verbose(env, "%s pointer offset %d is not allowed\n",
1838+
reg_type_str[type], reg->off);
1839+
return false;
1840+
}
1841+
1842+
if (smin == S64_MIN) {
1843+
verbose(env, "math between %s pointer and register with unbounded min value is not allowed\n",
1844+
reg_type_str[type]);
1845+
return false;
1846+
}
1847+
1848+
if (smin >= BPF_MAX_VAR_OFF || smin <= -BPF_MAX_VAR_OFF) {
1849+
verbose(env, "value %lld makes %s pointer be out of bounds\n",
1850+
smin, reg_type_str[type]);
1851+
return false;
1852+
}
1853+
1854+
return true;
1855+
}
1856+
18031857
/* Handles arithmetic on a pointer and a scalar: computes new min/max and var_off.
18041858
* Caller should also handle BPF_MOV case separately.
18051859
* If we return -EACCES, caller may want to try again treating pointer as a
@@ -1868,6 +1922,10 @@ static int adjust_ptr_min_max_vals(struct bpf_verifier_env *env,
18681922
dst_reg->type = ptr_reg->type;
18691923
dst_reg->id = ptr_reg->id;
18701924

1925+
if (!check_reg_sane_offset(env, off_reg, ptr_reg->type) ||
1926+
!check_reg_sane_offset(env, ptr_reg, ptr_reg->type))
1927+
return -EINVAL;
1928+
18711929
switch (opcode) {
18721930
case BPF_ADD:
18731931
/* We can take a fixed offset as long as it doesn't overflow
@@ -1998,12 +2056,19 @@ static int adjust_ptr_min_max_vals(struct bpf_verifier_env *env,
19982056
return -EACCES;
19992057
}
20002058

2059+
if (!check_reg_sane_offset(env, dst_reg, ptr_reg->type))
2060+
return -EINVAL;
2061+
20012062
__update_reg_bounds(dst_reg);
20022063
__reg_deduce_bounds(dst_reg);
20032064
__reg_bound_offset(dst_reg);
20042065
return 0;
20052066
}
20062067

2068+
/* WARNING: This function does calculations on 64-bit values, but the actual
2069+
* execution may occur on 32-bit values. Therefore, things like bitshifts
2070+
* need extra checks in the 32-bit case.
2071+
*/
20072072
static int adjust_scalar_min_max_vals(struct bpf_verifier_env *env,
20082073
struct bpf_insn *insn,
20092074
struct bpf_reg_state *dst_reg,
@@ -2014,19 +2079,21 @@ static int adjust_scalar_min_max_vals(struct bpf_verifier_env *env,
20142079
bool src_known, dst_known;
20152080
s64 smin_val, smax_val;
20162081
u64 umin_val, umax_val;
2082+
u64 insn_bitness = (BPF_CLASS(insn->code) == BPF_ALU64) ? 64 : 32;
20172083

2018-
if (BPF_CLASS(insn->code) != BPF_ALU64) {
2019-
/* 32-bit ALU ops are (32,32)->64 */
2020-
coerce_reg_to_32(dst_reg);
2021-
coerce_reg_to_32(&src_reg);
2022-
}
20232084
smin_val = src_reg.smin_value;
20242085
smax_val = src_reg.smax_value;
20252086
umin_val = src_reg.umin_value;
20262087
umax_val = src_reg.umax_value;
20272088
src_known = tnum_is_const(src_reg.var_off);
20282089
dst_known = tnum_is_const(dst_reg->var_off);
20292090

2091+
if (!src_known &&
2092+
opcode != BPF_ADD && opcode != BPF_SUB && opcode != BPF_AND) {
2093+
__mark_reg_unknown(dst_reg);
2094+
return 0;
2095+
}
2096+
20302097
switch (opcode) {
20312098
case BPF_ADD:
20322099
if (signed_add_overflows(dst_reg->smin_value, smin_val) ||
@@ -2155,9 +2222,9 @@ static int adjust_scalar_min_max_vals(struct bpf_verifier_env *env,
21552222
__update_reg_bounds(dst_reg);
21562223
break;
21572224
case BPF_LSH:
2158-
if (umax_val > 63) {
2159-
/* Shifts greater than 63 are undefined. This includes
2160-
* shifts by a negative number.
2225+
if (umax_val >= insn_bitness) {
2226+
/* Shifts greater than 31 or 63 are undefined.
2227+
* This includes shifts by a negative number.
21612228
*/
21622229
mark_reg_unknown(env, regs, insn->dst_reg);
21632230
break;
@@ -2183,27 +2250,29 @@ static int adjust_scalar_min_max_vals(struct bpf_verifier_env *env,
21832250
__update_reg_bounds(dst_reg);
21842251
break;
21852252
case BPF_RSH:
2186-
if (umax_val > 63) {
2187-
/* Shifts greater than 63 are undefined. This includes
2188-
* shifts by a negative number.
2253+
if (umax_val >= insn_bitness) {
2254+
/* Shifts greater than 31 or 63 are undefined.
2255+
* This includes shifts by a negative number.
21892256
*/
21902257
mark_reg_unknown(env, regs, insn->dst_reg);
21912258
break;
21922259
}
2193-
/* BPF_RSH is an unsigned shift, so make the appropriate casts */
2194-
if (dst_reg->smin_value < 0) {
2195-
if (umin_val) {
2196-
/* Sign bit will be cleared */
2197-
dst_reg->smin_value = 0;
2198-
} else {
2199-
/* Lost sign bit information */
2200-
dst_reg->smin_value = S64_MIN;
2201-
dst_reg->smax_value = S64_MAX;
2202-
}
2203-
} else {
2204-
dst_reg->smin_value =
2205-
(u64)(dst_reg->smin_value) >> umax_val;
2206-
}
2260+
/* BPF_RSH is an unsigned shift. If the value in dst_reg might
2261+
* be negative, then either:
2262+
* 1) src_reg might be zero, so the sign bit of the result is
2263+
* unknown, so we lose our signed bounds
2264+
* 2) it's known negative, thus the unsigned bounds capture the
2265+
* signed bounds
2266+
* 3) the signed bounds cross zero, so they tell us nothing
2267+
* about the result
2268+
* If the value in dst_reg is known nonnegative, then again the
2269+
* unsigned bounts capture the signed bounds.
2270+
* Thus, in all cases it suffices to blow away our signed bounds
2271+
* and rely on inferring new ones from the unsigned bounds and
2272+
* var_off of the result.
2273+
*/
2274+
dst_reg->smin_value = S64_MIN;
2275+
dst_reg->smax_value = S64_MAX;
22072276
if (src_known)
22082277
dst_reg->var_off = tnum_rshift(dst_reg->var_off,
22092278
umin_val);
@@ -2219,6 +2288,12 @@ static int adjust_scalar_min_max_vals(struct bpf_verifier_env *env,
22192288
break;
22202289
}
22212290

2291+
if (BPF_CLASS(insn->code) != BPF_ALU64) {
2292+
/* 32-bit ALU ops are (32,32)->32 */
2293+
coerce_reg_to_size(dst_reg, 4);
2294+
coerce_reg_to_size(&src_reg, 4);
2295+
}
2296+
22222297
__reg_deduce_bounds(dst_reg);
22232298
__reg_bound_offset(dst_reg);
22242299
return 0;
@@ -2396,17 +2471,20 @@ static int check_alu_op(struct bpf_verifier_env *env, struct bpf_insn *insn)
23962471
return -EACCES;
23972472
}
23982473
mark_reg_unknown(env, regs, insn->dst_reg);
2399-
/* high 32 bits are known zero. */
2400-
regs[insn->dst_reg].var_off = tnum_cast(
2401-
regs[insn->dst_reg].var_off, 4);
2402-
__update_reg_bounds(&regs[insn->dst_reg]);
2474+
coerce_reg_to_size(&regs[insn->dst_reg], 4);
24032475
}
24042476
} else {
24052477
/* case: R = imm
24062478
* remember the value we stored into this reg
24072479
*/
24082480
regs[insn->dst_reg].type = SCALAR_VALUE;
2409-
__mark_reg_known(regs + insn->dst_reg, insn->imm);
2481+
if (BPF_CLASS(insn->code) == BPF_ALU64) {
2482+
__mark_reg_known(regs + insn->dst_reg,
2483+
insn->imm);
2484+
} else {
2485+
__mark_reg_known(regs + insn->dst_reg,
2486+
(u32)insn->imm);
2487+
}
24102488
}
24112489

24122490
} else if (opcode > BPF_END) {
@@ -3437,15 +3515,14 @@ static bool regsafe(struct bpf_reg_state *rold, struct bpf_reg_state *rcur,
34373515
return range_within(rold, rcur) &&
34383516
tnum_in(rold->var_off, rcur->var_off);
34393517
} else {
3440-
/* if we knew anything about the old value, we're not
3441-
* equal, because we can't know anything about the
3442-
* scalar value of the pointer in the new value.
3518+
/* We're trying to use a pointer in place of a scalar.
3519+
* Even if the scalar was unbounded, this could lead to
3520+
* pointer leaks because scalars are allowed to leak
3521+
* while pointers are not. We could make this safe in
3522+
* special cases if root is calling us, but it's
3523+
* probably not worth the hassle.
34433524
*/
3444-
return rold->umin_value == 0 &&
3445-
rold->umax_value == U64_MAX &&
3446-
rold->smin_value == S64_MIN &&
3447-
rold->smax_value == S64_MAX &&
3448-
tnum_is_unknown(rold->var_off);
3525+
return false;
34493526
}
34503527
case PTR_TO_MAP_VALUE:
34513528
/* If the new min/max/var_off satisfy the old ones and

0 commit comments

Comments
 (0)