From patchwork Mon Dec 4 17:03:14 2017 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jann Horn X-Patchwork-Id: 844326 X-Patchwork-Delegate: bpf@iogearbox.net Return-Path: X-Original-To: patchwork-incoming@ozlabs.org Delivered-To: patchwork-incoming@ozlabs.org Authentication-Results: ozlabs.org; spf=none (mailfrom) smtp.mailfrom=vger.kernel.org (client-ip=209.132.180.67; helo=vger.kernel.org; envelope-from=netdev-owner@vger.kernel.org; receiver=) Authentication-Results: ozlabs.org; dkim=pass (2048-bit key; unprotected) header.d=google.com header.i=@google.com header.b="GfwNB7p3"; dkim-atps=neutral Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by ozlabs.org (Postfix) with ESMTP id 3yrB6d64xVz9sNr for ; Tue, 5 Dec 2017 04:03:53 +1100 (AEDT) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1753197AbdLDRDl (ORCPT ); Mon, 4 Dec 2017 12:03:41 -0500 Received: from mail-ot0-f193.google.com ([74.125.82.193]:41220 "EHLO mail-ot0-f193.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1753285AbdLDRDg (ORCPT ); Mon, 4 Dec 2017 12:03:36 -0500 Received: by mail-ot0-f193.google.com with SMTP id b54so15314024otd.8 for ; Mon, 04 Dec 2017 09:03:36 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20161025; h=mime-version:from:date:message-id:subject:to:cc; bh=ZSkXuHjFD7Lv6ksOnZTd/ZQpew9ZTQi77HAcxDvYygc=; b=GfwNB7p3Ufb92DusvNibJauf7QJ2i8Q+/uZz4H9dYM+Q/hHNe9avcY5OQemjg3E4J0 BF4KLMXQQeeWD+FB0VHxhsUbMU3oBiMD4yPzc5NzL5cBXM4tKtf8tosza4Ukvrk4s6B1 yZ4cqOBn5oaVx5ICes2ENjx76SdNVOEbJAM1o1peKOjStkPnt40XBN4Y25YwmukIWihK y1WC/nYM5kXdEkbom+MAmW7aH28tkn0dEoOYrcE6OCM28cE5xCnpyfbaMfoZHAhU/Uyh lW+IC+jj2rhaAiL4kQedoEj7c5W77ODRPNpsmJHKGA6N0tWzJV0vWH42ZelSthZu3fcB EqnA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:from:date:message-id:subject:to:cc; bh=ZSkXuHjFD7Lv6ksOnZTd/ZQpew9ZTQi77HAcxDvYygc=; b=E6f98bFL8fWg6ZRqIhyxvM2J+VqMMCFs8KiKHz5BaQxUnVC3DR05LwZe0GhAAh/Xe4 0QUmu1vjeyMOa11bq8LzMdrDQII0X4jk+irgfLRl/doGGA6e613mpsRMn92ztdWUb1Dt uyGL53OTUPCCM7VoNEBxaUzGFc1CmI15uEF2tVyAncn4ppj9UeRdRtxuBZEgS3ekvb5+ gLMowkeGnAbnBwTBlNuE3kcWzuGbvEcRrxLaXWhtrE8mFhDeWLtPPlxAIDb6PNacbXwv S+POaQOJ09prdI/TWJgH5H9hkLCP9k29WUQlP8odgPrEVMjjqSxFiPGaJ3o3aE3CmnWE G4gw== X-Gm-Message-State: AJaThX6lsUZS4dOYp4W+aj7dxgk/JvXhdAitlebseXZMl5fOKn69HDTI msPlDrug45SdJ/I6A8J5S5tL9LGLIeWbzqAe5UOOag== X-Google-Smtp-Source: AGs4zMbQyOljGrPks3pNnSPHvThMYdaBxOOmLSukAjS+iVLRSSsaoZ9QptXU0FRTauus7QxGG+KDabQpR1ycVK5fA9w= X-Received: by 10.157.9.234 with SMTP id 39mr15550966otz.323.1512407015443; Mon, 04 Dec 2017 09:03:35 -0800 (PST) MIME-Version: 1.0 Received: by 10.74.166.3 with HTTP; Mon, 4 Dec 2017 09:03:14 -0800 (PST) From: Jann Horn Date: Mon, 4 Dec 2017 18:03:14 +0100 Message-ID: Subject: BPF: bug without effect in BPF_RSH case of adjust_scalar_min_max_vals() To: Alexei Starovoitov , Daniel Borkmann , Edward Cree Cc: Network Development , kernel list Sender: netdev-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: netdev@vger.kernel.org As far as I can tell, commit b03c9f9fdc37 ("bpf/verifier: track signed and unsigned min/max values") introduced the following effectless bug in the BPF_RSH case of adjust_scalar_min_max_vals() (unless that's intentional): `dst_reg->smax_value` is only updated in the case where `dst_reg->smin_value < 0` and `umin_val == 0`. This is obviously harmless if `dst_reg->smax_value >= 0`, but if `dst_reg->smax_value < 0`, this will temporarily result in a state where the signed upper bound of `dst_reg` is lower than the signed lower bound (which will be set to 0). I don't think this should ever happen. Luckily, this doesn't have any effect because of the inter-representation information propagation that happens immediately afterwards: __update_reg_bounds() neither modifies nor propagates the incorrect `reg->smax_value` (the assignment is a no-op in this case), then `__reg_deduce_bounds` takes the first branch and resets `reg->smax_value` to `reg->umax_value`, which is correct. To test this, I applied this patch to the kernel: + pr_warn("BPF_RSH point B: smin=%lld, smax=%lld, umin=%llx, umax=%llx, tribits=%llx, trimask=%llx\n", dst_reg->smin_value, dst_reg->smax_value, dst_reg->umin_value, dst_reg->umax_value, dst_reg->var_off.value, dst_reg->var_off.mask); break; default: mark_reg_unknown(env, regs, insn->dst_reg); @@ -2214,7 +2216,11 @@ static int adjust_scalar_min_max_vals(struct bpf_verifier_env *env, } __reg_deduce_bounds(dst_reg); + if (opcode == BPF_RSH) + pr_warn("BPF_RSH point C: smin=%lld, smax=%lld, umin=%llx, umax=%llx, tribits=%llx, trimask=%llx\n", dst_reg->smin_value, dst_reg->smax_value, dst_reg->umin_value, dst_reg->umax_value, dst_reg->var_off.value, dst_reg->var_off.mask); __reg_bound_offset(dst_reg); + if (opcode == BPF_RSH) + pr_warn("BPF_RSH point D: smin=%lld, smax=%lld, umin=%llx, umax=%llx, tribits=%llx, trimask=%llx\n", dst_reg->smin_value, dst_reg->smax_value, dst_reg->umin_value, dst_reg->umax_value, dst_reg->var_off.value, dst_reg->var_off.mask); return 0; } ======================= Then I attempted to load the following eBPF bytecode with verbosity level 2: ======================= BPF_LD_MAP_FD(BPF_REG_ARG1, mapfd), BPF_MOV64_REG(BPF_REG_TMP, BPF_REG_FP), BPF_ALU64_IMM(BPF_ADD, BPF_REG_TMP, -4), // allocate 4 bytes stack BPF_MOV32_IMM(BPF_REG_ARG2, 1), BPF_STX_MEM(BPF_W, BPF_REG_TMP, BPF_REG_ARG2, 0), BPF_MOV64_REG(BPF_REG_ARG2, BPF_REG_TMP), BPF_EMIT_CALL(BPF_FUNC_map_lookup_elem), BPF_JMP_IMM(BPF_JNE, BPF_REG_0, 0, 2), BPF_MOV64_REG(BPF_REG_0, 0), // prepare exit BPF_EXIT_INSN(), // exit BPF_LDX_MEM(BPF_W, BPF_REG_3, BPF_REG_0, 0), BPF_ALU64_IMM(BPF_AND, BPF_REG_3, 0xf), BPF_MOV64_IMM(BPF_REG_1, -42), BPF_ALU64_REG(BPF_ADD, BPF_REG_1, BPF_REG_3), BPF_MOV64_IMM(BPF_REG_2, 2), BPF_ALU64_REG(BPF_RSH, BPF_REG_1, BPF_REG_2), BPF_EXIT_INSN() ======================= dmesg output: ======================= [ 145.423122] BPF_RSH point A: smin=0, smax=-27, umin=3ffffffffffffff5, umax=3ffffffffffffff9, tribits=3ffffffffffffff0, trimask=f [ 145.423129] BPF_RSH point B: smin=4611686018427387888, smax=-27, umin=3ffffffffffffff5, umax=3ffffffffffffff9, tribits=3ffffffffffffff0, trimask=f [ 145.423133] BPF_RSH point C: smin=4611686018427387893, smax=4611686018427387897, umin=3ffffffffffffff5, umax=3ffffffffffffff9, tribits=3ffffffffffffff0, trimask=f [ 145.423136] BPF_RSH point D: smin=4611686018427387893, smax=4611686018427387897, umin=3ffffffffffffff5, umax=3ffffffffffffff9, tribits=3ffffffffffffff0, trimask=f ======================= Signed-off-by: Jann Horn ======================= diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c index d4593571c404..bcf6a4aa25cd 100644 --- a/kernel/bpf/verifier.c +++ b/kernel/bpf/verifier.c @@ -2205,8 +2205,10 @@ static int adjust_scalar_min_max_vals(struct bpf_verifier_env *env, dst_reg->var_off = tnum_rshift(tnum_unknown, umin_val); dst_reg->umin_value >>= umax_val; dst_reg->umax_value >>= umin_val; + pr_warn("BPF_RSH point A: smin=%lld, smax=%lld, umin=%llx, umax=%llx, tribits=%llx, trimask=%llx\n", dst_reg->smin_value, dst_reg->smax_value, dst_reg->umin_value, dst_reg->umax_value, dst_reg->var_off.value, dst_reg->var_off.mask); /* We may learn something more from the var_off */ __update_reg_bounds(dst_reg);