From patchwork Tue Mar 24 17:37:54 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: John Fastabend X-Patchwork-Id: 221956 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-6.8 required=3.0 tests=DKIM_SIGNED,DKIM_VALID, DKIM_VALID_AU,FREEMAIL_FORGED_FROMDOMAIN,FREEMAIL_FROM, HEADER_FROM_DIFFERENT_DOMAINS, INCLUDES_PATCH, MAILING_LIST_MULTI, SIGNED_OFF_BY, SPF_HELO_NONE, SPF_PASS autolearn=ham autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id AA4C5C41621 for ; Tue, 24 Mar 2020 17:38:11 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.kernel.org (Postfix) with ESMTP id 86F3920714 for ; Tue, 24 Mar 2020 17:38:11 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="CBRtrL9n" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727560AbgCXRiL (ORCPT ); Tue, 24 Mar 2020 13:38:11 -0400 Received: from mail-pj1-f66.google.com ([209.85.216.66]:40010 "EHLO mail-pj1-f66.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1727223AbgCXRiK (ORCPT ); Tue, 24 Mar 2020 13:38:10 -0400 Received: by mail-pj1-f66.google.com with SMTP id kx8so1778158pjb.5; Tue, 24 Mar 2020 10:38:09 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=subject:from:to:cc:date:message-id:in-reply-to:references :user-agent:mime-version:content-transfer-encoding; bh=jyjUeD6zuoXyhDLMSL9cDCavDT6zPCUdtuDCvs0xSJc=; b=CBRtrL9nVmoJgfeqndPjSJJlxNOcupvUQqCEG3UKI9QGIEEJxsiHFEU81GBjE0RQ3s Q8M9kFhJ5KBnocrqtjomGRTRO2y8cpVHfoFo75BvFigdkVsijuA/wD+f5VeS/cn9Eesy PPbCiXf1DnKOhOrDcLcirFcLy24NdBeTLYLd/YVd936+oCxyE854Iqt1pK9+iMb5NbEu TSlFtPyeZ9kMPFwD+jj4l6KP13/+jHBoJ9L9KgeK06uvhLheOsGOSrfGVWm8iJ0obnrA jVmuTKm+5ASTuXqGdciItQyZeXtzzPHux2EC2BuAF+/HDQ62IkeWOU8lh/OFj6EYs8cd DiGw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:subject:from:to:cc:date:message-id:in-reply-to :references:user-agent:mime-version:content-transfer-encoding; bh=jyjUeD6zuoXyhDLMSL9cDCavDT6zPCUdtuDCvs0xSJc=; b=GWrwgD5os+DqVXLWT41+tT/MUd1mTeb3IGYak2ui49qIsThDm0q7jwlDYroVoaA4MT 9H4Y1jYUmaWSDHb1a15PErAuj60h61GmvOOvUpDiREiVeWPg1xHhLreW3g5fYMe1pYRt vO5u9TH5E58LXnJKInA7trV6n7IJK0JHiAh03B6UsE09vUf+jO/TtyaWPD4ETJWa4Ahf GViVJZRauqKIjaZwbnlFI8Zh4zRy+YfOwIGCxeORHM0yRxMFGEN+oI+rmYoXbK5cVMY3 7gYSryG5zB3oCTZpTxOY6OpZSCIQwLS86uAKk23HIW7shy3LAyHHC8tqyWdnqM5XbWAm f4Ug== X-Gm-Message-State: ANhLgQ3OVbHKrA8X2nX9Cs2j7Dk4Epm/3TzXEUWji3+M2m7DbAKAQZf8 FBh6zcWLw4dNCajqQngH4hA= X-Google-Smtp-Source: ADFU+vslUzmlB9AI4iTqG9J52w4DCNiuO97FpQC7Nvrg0YEc99CNFz987dZB36DvVshtJNNAU5lvqg== X-Received: by 2002:a17:90b:3d1:: with SMTP id go17mr6012724pjb.99.1585071489030; Tue, 24 Mar 2020 10:38:09 -0700 (PDT) Received: from [127.0.1.1] ([184.63.162.180]) by smtp.gmail.com with ESMTPSA id s137sm13574105pfs.45.2020.03.24.10.37.59 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Tue, 24 Mar 2020 10:38:08 -0700 (PDT) Subject: [bpf-next PATCH 01/10] bpf: verifier, do_refine_retval_range may clamp umin to 0 incorrectly From: John Fastabend To: ecree@solarflare.com, yhs@fb.com, alexei.starovoitov@gmail.com, daniel@iogearbox.net Cc: netdev@vger.kernel.org, bpf@vger.kernel.org, john.fastabend@gmail.com Date: Tue, 24 Mar 2020 10:37:54 -0700 Message-ID: <158507147386.15666.12903539309039973826.stgit@john-Precision-5820-Tower> In-Reply-To: <158507130343.15666.8018068546764556975.stgit@john-Precision-5820-Tower> References: <158507130343.15666.8018068546764556975.stgit@john-Precision-5820-Tower> User-Agent: StGit/0.17.1-dirty MIME-Version: 1.0 Sender: netdev-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: netdev@vger.kernel.org do_refine_retval_range() is called to refine return values from specified helpers, probe_read_str and get_stack at the moment, the reasoning is because both have a max value as part of their input arguments and because the helper ensure the return value will not be larger than this we can set smax values of the return register, r0. However, the return value is a signed integer so setting umax is incorrect It leads to further confusion when the do_refine_retval_range() then calls, __reg_deduce_bounds() which will see a umax value as meaning the value is unsigned and then assuming it is unsigned set the smin = umin which in this case results in 'smin = 0' and an 'smax = X' where X is the input argument from the helper call. Here are the comments from _reg_deduce_bounds() on why this would be safe to do. /* Learn sign from unsigned bounds. Signed bounds cross the sign * boundary, so we must be careful. */ if ((s64)reg->umax_value >= 0) { /* Positive. We can't learn anything from the smin, but smax * is positive, hence safe. */ reg->smin_value = reg->umin_value; reg->smax_value = reg->umax_value = min_t(u64, reg->smax_value, reg->umax_value); But now we incorrectly have a return value with type int with the signed bounds (0,X). Suppose the return value is negative, which is possible the we have the verifier and reality out of sync. Among other things this may result in any error handling code being falsely detected as dead-code and removed. For instance the example below shows using bpf_probe_read_str() causes the error path to be identified as dead code and removed. >>From the 'llvm-object -S' dump, r2 = 100 call 45 if r0 s< 0 goto +4 r4 = *(u32 *)(r7 + 0) But from dump xlate (b7) r2 = 100 (85) call bpf_probe_read_compat_str#-96768 (61) r4 = *(u32 *)(r7 +0) <-- dropped if goto Due to verifier state after call being R0=inv(id=0,umax_value=100,var_off=(0x0; 0x7f)) To fix omit setting the umax value because its not safe. The only actual bounds we know is the smax. This results in the correct bounds (SMIN, X) where X is the max length from the helper. After this the new verifier state looks like the following after call 45. R0=inv(id=0,smax_value=100) Then xlated version no longer removed dead code giving the expected result, (b7) r2 = 100 (85) call bpf_probe_read_compat_str#-96768 (c5) if r0 s< 0x0 goto pc+4 (61) r4 = *(u32 *)(r7 +0) Note, bpf_probe_read_* calls are root only so we wont hit this case with non-root bpf users. v3: comment had some documentation about meta set to null case which is not relevant here and confusing to include in the comment. v2 note: In original version we set msize_smax_value from check_func_arg() and propagated this into smax of retval. The logic was smax is the bound on the retval we set and because the type in the helper is ARG_CONST_SIZE we know that the reg is a positive tnum_const() so umax=smax. Alexei pointed out though this is a bit odd to read because the register in check_func_arg() has a C type of u32 and the umax bound would be the normally relavent bound here. Pulling in extra knowledge about future checks makes reading the code a bit tricky. Further having a signed meta data that can only ever be positive is also a bit odd. So dropped the msize_smax_value metadata and made it a u64 msize_max_value to indicate its unsigned. And additionally save bound from umax value in check_arg_funcs which is the same as smax due to as noted above tnumx_cont and negative check but reads better. By my analysis nothing functionally changes in v2 but it does get easier to read so that is win. Fixes: 849fa50662fbc ("bpf/verifier: refine retval R0 state for bpf_get_stack helper") Signed-off-by: John Fastabend --- kernel/bpf/verifier.c | 19 +++++++++++-------- 1 file changed, 11 insertions(+), 8 deletions(-) diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c index 745f3cfd..57d3351 100644 --- a/kernel/bpf/verifier.c +++ b/kernel/bpf/verifier.c @@ -228,8 +228,7 @@ struct bpf_call_arg_meta { bool pkt_access; int regno; int access_size; - s64 msize_smax_value; - u64 msize_umax_value; + u64 msize_max_value; int ref_obj_id; int func_id; u32 btf_id; @@ -3577,11 +3576,15 @@ static int check_func_arg(struct bpf_verifier_env *env, u32 regno, } else if (arg_type_is_mem_size(arg_type)) { bool zero_size_allowed = (arg_type == ARG_CONST_SIZE_OR_ZERO); - /* remember the mem_size which may be used later - * to refine return values. + /* This is used to refine r0 return value bounds for helpers + * that enforce this value as an upper bound on return values. + * See do_refine_retval_range() for helpers that can refine + * the return value. C type of helper is u32 so we pull register + * bound from umax_value however, if negative verifier errors + * out. Only upper bounds can be learned because retval is an + * int type and negative retvals are allowed. */ - meta->msize_smax_value = reg->smax_value; - meta->msize_umax_value = reg->umax_value; + meta->msize_max_value = reg->umax_value; /* The register is SCALAR_VALUE; the access check * happens using its boundaries. @@ -4124,10 +4127,10 @@ static void do_refine_retval_range(struct bpf_reg_state *regs, int ret_type, func_id != BPF_FUNC_probe_read_str)) return; - ret_reg->smax_value = meta->msize_smax_value; - ret_reg->umax_value = meta->msize_umax_value; + ret_reg->smax_value = meta->msize_max_value; __reg_deduce_bounds(ret_reg); __reg_bound_offset(ret_reg); + __update_reg_bounds(ret_reg); } static int From patchwork Tue Mar 24 17:38:37 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: John Fastabend X-Patchwork-Id: 221955 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-6.8 required=3.0 tests=DKIM_SIGNED,DKIM_VALID, DKIM_VALID_AU,FREEMAIL_FORGED_FROMDOMAIN,FREEMAIL_FROM, HEADER_FROM_DIFFERENT_DOMAINS, INCLUDES_PATCH, MAILING_LIST_MULTI, SIGNED_OFF_BY, SPF_HELO_NONE, SPF_PASS autolearn=unavailable autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id 85AD7C41621 for ; Tue, 24 Mar 2020 17:38:51 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.kernel.org (Postfix) with ESMTP id 61C642074D for ; Tue, 24 Mar 2020 17:38:51 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="pZIZWiNT" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727647AbgCXRiv (ORCPT ); Tue, 24 Mar 2020 13:38:51 -0400 Received: from mail-pg1-f195.google.com ([209.85.215.195]:34309 "EHLO mail-pg1-f195.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1727223AbgCXRiu (ORCPT ); Tue, 24 Mar 2020 13:38:50 -0400 Received: by mail-pg1-f195.google.com with SMTP id t3so9395995pgn.1; Tue, 24 Mar 2020 10:38:50 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=subject:from:to:cc:date:message-id:in-reply-to:references :user-agent:mime-version:content-transfer-encoding; bh=k3CEfxk16dpPoeXIJ4gQHapRgGSMbuvWPkC6OnFy/lo=; b=pZIZWiNTS6NiC1osiWqClGip4xTNcwQT5Ogh6khQdui9Yp/pbvPSRe03aw6Y/OtEXG ky7ITlKI/JPXbqDL5TeAuHwcmLQtAw1Mv2Vn5IAZLDgogrG5dmzMt0vOrTBIUYDEkGOu 2uBmpIZRzTGR2qcTkX06DrdkdswBTkB5bJuhpfIeIAO9k2VQ3rCUFV27hgFbb37QHD4N Xddk++7YDUBJZvLtk2G3RpKbxBwaFbEseazCXys0QJcQ/2WWb7yKWRDFXfJjF7MFyToY F7csBu9F1PKCEA6bE8NQt7zF+mmVwfC29SpZahzYpl3suhnPvRDruPojs8ZU76tBD7TD pc0w== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:subject:from:to:cc:date:message-id:in-reply-to :references:user-agent:mime-version:content-transfer-encoding; bh=k3CEfxk16dpPoeXIJ4gQHapRgGSMbuvWPkC6OnFy/lo=; b=Cea+1E2dzNTxt2J1bZSqh+0Uw1G/rknP8Gx1dkOGcub5WMNYH3XMRXTxvTBVkilOny Sp8YaVIa5daaur1rHdCNseax1S5rmGCi3mupTdPt0DKRQF9vohj3fcoArhccx2wRkIvT YDNKeF7sLldeBtqTCJKM+1s+7LhvP8ZMxOuZJTT0rnUWe2NrdPrZZ1EfKdDrW50XzU4U nBVg62NzUsldY1HOfvsaV5l0NQyhqn6XD22UmmIhTPL6gmuG1y6s4V/YxjthvvekhtRb qIm+QWvI4SsrgIUcuWW4RrLRTGJAhxWua/lKEu67I8NocX3mqBCbJNMk90jvVidjjkfa /zmQ== X-Gm-Message-State: ANhLgQ2rl3v/HXkweasdwuVKGkQ3NgNnATKARd3f/u9JecUGuKqTVcKt zfcTwd0HdNle8sy1BWcPJ3g= X-Google-Smtp-Source: ADFU+vtBnHvUpgsQivZuxIpV5esK6HtLRx/vSvdoXjO4GbWtEC+fFVqNGQSb9OFHIXRSlDopktx4RA== X-Received: by 2002:a62:fc07:: with SMTP id e7mr31479408pfh.299.1585071529668; Tue, 24 Mar 2020 10:38:49 -0700 (PDT) Received: from [127.0.1.1] ([184.63.162.180]) by smtp.gmail.com with ESMTPSA id x27sm16815505pfj.74.2020.03.24.10.38.42 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Tue, 24 Mar 2020 10:38:49 -0700 (PDT) Subject: [bpf-next PATCH 03/10] bpf: verifer, adjust_scalar_min_max_vals to always call update_reg_bounds() From: John Fastabend To: ecree@solarflare.com, yhs@fb.com, alexei.starovoitov@gmail.com, daniel@iogearbox.net Cc: netdev@vger.kernel.org, bpf@vger.kernel.org, john.fastabend@gmail.com Date: Tue, 24 Mar 2020 10:38:37 -0700 Message-ID: <158507151689.15666.566796274289413203.stgit@john-Precision-5820-Tower> In-Reply-To: <158507130343.15666.8018068546764556975.stgit@john-Precision-5820-Tower> References: <158507130343.15666.8018068546764556975.stgit@john-Precision-5820-Tower> User-Agent: StGit/0.17.1-dirty MIME-Version: 1.0 Sender: netdev-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: netdev@vger.kernel.org Currently, for all op verification we call __red_deduce_bounds() and __red_bound_offset() but we only call __update_reg_bounds() in bitwise ops. However, we could benefit from calling __update_reg_bounds() in BPF_ADD, BPF_SUB, and BPF_MUL cases as well. For example, a register with state 'R1_w=invP0' when we subtract from it, w1 -= 2 Before coerce we will now have an smin_value=S64_MIN, smax_value=U64_MAX and unsigned bounds umin_value=0, umax_value=U64_MAX. These will then be clamped to S32_MIN, U32_MAX values by coerce in the case of alu32 op as done in above example. However tnum will be a constant because the ALU op is done on a constant. Without update_reg_bounds() we have a scenario where tnum is a const but our unsigned bounds do not reflect this. By calling update_reg_bounds after coerce to 32bit we further refine the umin_value to U64_MAX in the alu64 case or U32_MAX in the alu32 case above. Signed-off-by: John Fastabend --- kernel/bpf/verifier.c | 1 + 1 file changed, 1 insertion(+) diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c index f7a34b1..fea9725 100644 --- a/kernel/bpf/verifier.c +++ b/kernel/bpf/verifier.c @@ -5202,6 +5202,7 @@ static int adjust_scalar_min_max_vals(struct bpf_verifier_env *env, coerce_reg_to_size(dst_reg, 4); } + __update_reg_bounds(dst_reg); __reg_deduce_bounds(dst_reg); __reg_bound_offset(dst_reg); return 0; From patchwork Tue Mar 24 17:39:16 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: John Fastabend X-Patchwork-Id: 221954 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-6.8 required=3.0 tests=DKIM_SIGNED,DKIM_VALID, DKIM_VALID_AU,FREEMAIL_FORGED_FROMDOMAIN,FREEMAIL_FROM, HEADER_FROM_DIFFERENT_DOMAINS, INCLUDES_PATCH, MAILING_LIST_MULTI, SIGNED_OFF_BY, SPF_HELO_NONE, SPF_PASS autolearn=unavailable autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id 66DB9C2BAEE for ; Tue, 24 Mar 2020 17:39:32 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.kernel.org (Postfix) with ESMTP id 4130F20714 for ; Tue, 24 Mar 2020 17:39:32 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="D613SQE6" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727705AbgCXRjb (ORCPT ); Tue, 24 Mar 2020 13:39:31 -0400 Received: from mail-pg1-f194.google.com ([209.85.215.194]:34373 "EHLO mail-pg1-f194.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1727223AbgCXRjb (ORCPT ); Tue, 24 Mar 2020 13:39:31 -0400 Received: by mail-pg1-f194.google.com with SMTP id t3so9396920pgn.1; Tue, 24 Mar 2020 10:39:30 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=subject:from:to:cc:date:message-id:in-reply-to:references :user-agent:mime-version:content-transfer-encoding; bh=vzoGBdCQrWjbiBxQI1MbFOzqtYhJmJc0P7ozXlXz9qI=; b=D613SQE6h7Cw/TSLnVvPAAD97YGFHq6MsQAszfYdOtXXHssa/oLBp5YQCF2PiQnHnr 4JfBNiQMgPJqxE4SkSoEN76HUWOuCJiwrpUuR8wh9M0Dg0spD878Res/CK+Q2ARv+cym V52waf6yQHfcQoXAUifeE9Yrfsl98wAuLPSINYbtnXK2hJEV3ROom2IOctyZcSlmFv30 OyTB6vT7xPQjDIG89oblYENUAUldLWFI+/q3Vizkm1YhTcdo3u0doaksZEvM5teKHZ3A nZSAmGY/54qchKVd2HQbhJ3+g1oHQxAcxC75L7HuYAsYJ+D6DCT+BnWf1RLu5OVjm1zH LRTg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:subject:from:to:cc:date:message-id:in-reply-to :references:user-agent:mime-version:content-transfer-encoding; bh=vzoGBdCQrWjbiBxQI1MbFOzqtYhJmJc0P7ozXlXz9qI=; b=t3hFsjGZGq7RnD0TVk/xmCBRZRxB/NTgS3bE8+suUxCCDroxsilmGq7ahhZ5WDdMWm pnBf9n7nSM53YMfZ2YgDBcAxXeY8emNsIlhLeQHEXzAQlo34pzIt7lA1AV7PnSkh5AMW IeJDH9KKxEFW7vkK44UUbC6KdF8h674HuVJHypBr6wKj0+KnA9eLGXOkhNsECd2PS2SB I5wwV1vRJUxYeMPoO6NxY9XK0bf5fMTdBIQcaz+PWISUBSV7ZL/U+OYtqKwuJNVN2tUQ wSmV/SoH+wsZFfOCBD5P14KR8gpiHlNz5R8WLEffgUPIsbixH+OLALmhqyXueHW9uep7 ggzg== X-Gm-Message-State: ANhLgQ2uVo4C5+a2QLRZRoQ3IoZAz2XEQ/z+pgHNtl0kE2L9Ng3mSWEN mJMCFcy9WX/46XtB8TF7RdI= X-Google-Smtp-Source: ADFU+vv+MY6NBAIiW2RtGB/J/MW8LwgTbsvqVKhBWuImsJmomCVSPMpNm316aCx+PmH2IhOgJRwT7Q== X-Received: by 2002:a63:f447:: with SMTP id p7mr28447554pgk.326.1585071569892; Tue, 24 Mar 2020 10:39:29 -0700 (PDT) Received: from [127.0.1.1] ([184.63.162.180]) by smtp.gmail.com with ESMTPSA id y131sm16657505pfg.25.2020.03.24.10.39.22 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Tue, 24 Mar 2020 10:39:29 -0700 (PDT) Subject: [bpf-next PATCH 05/10] bpf: verifier, return value is an int in do_refine_retval_range From: John Fastabend To: ecree@solarflare.com, yhs@fb.com, alexei.starovoitov@gmail.com, daniel@iogearbox.net Cc: netdev@vger.kernel.org, bpf@vger.kernel.org, john.fastabend@gmail.com Date: Tue, 24 Mar 2020 10:39:16 -0700 Message-ID: <158507155667.15666.4189866174878249746.stgit@john-Precision-5820-Tower> In-Reply-To: <158507130343.15666.8018068546764556975.stgit@john-Precision-5820-Tower> References: <158507130343.15666.8018068546764556975.stgit@john-Precision-5820-Tower> User-Agent: StGit/0.17.1-dirty MIME-Version: 1.0 Sender: netdev-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: netdev@vger.kernel.org Mark 32-bit subreg region with max value because do_refine_retval_range() catches functions with int return type (We will assume here that int is a 32-bit type). Marking 64-bit region could be dangerous if upper bits are not zero which could be possible. Two reasons to pull this out of original patch. First it makes the original fix impossible to backport. And second I've not seen this as being problematic in practice unlike the other case. Fixes: 849fa50662fbc ("bpf/verifier: refine retval R0 state for bpf_get_stack helper") Signed-off-by: John Fastabend --- kernel/bpf/verifier.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c index 6372fa4..3731109 100644 --- a/kernel/bpf/verifier.c +++ b/kernel/bpf/verifier.c @@ -4328,7 +4328,7 @@ static void do_refine_retval_range(struct bpf_reg_state *regs, int ret_type, func_id != BPF_FUNC_probe_read_str)) return; - ret_reg->smax_value = meta->msize_max_value; + ret_reg->s32_max_value = meta->msize_max_value; __reg_deduce_bounds(ret_reg); __reg_bound_offset(ret_reg); __update_reg_bounds(ret_reg); From patchwork Tue Mar 24 17:39:55 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: John Fastabend X-Patchwork-Id: 221953 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-6.8 required=3.0 tests=DKIM_SIGNED,DKIM_VALID, DKIM_VALID_AU,FREEMAIL_FORGED_FROMDOMAIN,FREEMAIL_FROM, HEADER_FROM_DIFFERENT_DOMAINS, INCLUDES_PATCH, MAILING_LIST_MULTI, SIGNED_OFF_BY, SPF_HELO_NONE, SPF_PASS autolearn=unavailable autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id 24B41C41621 for ; Tue, 24 Mar 2020 17:40:12 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.kernel.org (Postfix) with ESMTP id 0184120714 for ; Tue, 24 Mar 2020 17:40:12 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="GB8cQNXy" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727729AbgCXRkL (ORCPT ); Tue, 24 Mar 2020 13:40:11 -0400 Received: from mail-pg1-f195.google.com ([209.85.215.195]:46062 "EHLO mail-pg1-f195.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1727223AbgCXRkL (ORCPT ); Tue, 24 Mar 2020 13:40:11 -0400 Received: by mail-pg1-f195.google.com with SMTP id o26so2874295pgc.12; Tue, 24 Mar 2020 10:40:09 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=subject:from:to:cc:date:message-id:in-reply-to:references :user-agent:mime-version:content-transfer-encoding; bh=SRgQi1yMuseYBwVWxPnOfPzlkltS46MTnR9winZRfXY=; b=GB8cQNXyunz4yMh8d2IqEkh4LuVaFet36SwZEMAlqlBEItLF1oxF0TaWZ3AtyON1C9 nJgXpcyvn5e9K2e+MFHLVAwYJH0Wl3747sRzmDwLeO9NFAZO+bOmwTHSPjXNJkZr0PLM 9+8YfPXpjUU02+7oZXB8+AWjkiFtxh7+Am/vU1UJDTxkWaQu2v9DhA9oTyLIbd1VCQVa By0eLa2qMXk0gET89rYpsBkf8valh/BOXHj9HTjTLdWkL1bz8cKLDmokP/YKtrinZTbx q6ZJ6kBb1XqRSOXnrr/Q7w8U4kbWdbTb/Zu856i0RPsdGSuNFKTgOZItpMcLt5O/NDws tFpw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:subject:from:to:cc:date:message-id:in-reply-to :references:user-agent:mime-version:content-transfer-encoding; bh=SRgQi1yMuseYBwVWxPnOfPzlkltS46MTnR9winZRfXY=; b=I2uCJVKvU+2bgcG1C0MSDvDvP5Pw/pipnVtkkBnqs3vpJ0Kq9elRA4yUx1eqtSykcW UNW3Kxaf6Ou7GCAPPhTq0++4K9bexgP/bwZtdpjBGKON6KOiEOYuH9LbuOi+l0kghfMt h+vJGLye85BsLsXVYncTJkuZG13By7G9JUGjDQYrPpSoalunuTg0EpQ/gGHYtiFPXZZz 9PhrrErO6BobX+JNbx4Ai1O7A5Gpr8sWDobXZbywuVGqExlM9gtkA5zbAQ9/8SJ2pvyj bUDV1sDeUyBnJDBGzaetlC5Vv6FqC2+7Na8M8lXvUQ5SBwfNgXuBOuXz+p6cRATmbxd/ NX6Q== X-Gm-Message-State: ANhLgQ3ofHNW6XklfNNMJ9MmZeibMa0o+x5sYezCDzNrCXEuasfUWz/x gWwWMPsdl1uwVJbWlvfSMl4= X-Google-Smtp-Source: ADFU+vsNolvOt+10m4bsspjEIdaNryGz3+LTNygFWIRuXyeVgChpPLG8trPAv5YhQxwGM0G8hkYeew== X-Received: by 2002:a63:2e49:: with SMTP id u70mr27843237pgu.202.1585071608594; Tue, 24 Mar 2020 10:40:08 -0700 (PDT) Received: from [127.0.1.1] ([184.63.162.180]) by smtp.gmail.com with ESMTPSA id ck23sm2828948pjb.14.2020.03.24.10.40.00 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Tue, 24 Mar 2020 10:40:08 -0700 (PDT) Subject: [bpf-next PATCH 07/10] bpf: test_verifier, bpf_get_stack return value add <0 From: John Fastabend To: ecree@solarflare.com, yhs@fb.com, alexei.starovoitov@gmail.com, daniel@iogearbox.net Cc: netdev@vger.kernel.org, bpf@vger.kernel.org, john.fastabend@gmail.com Date: Tue, 24 Mar 2020 10:39:55 -0700 Message-ID: <158507159511.15666.6943798089263377114.stgit@john-Precision-5820-Tower> In-Reply-To: <158507130343.15666.8018068546764556975.stgit@john-Precision-5820-Tower> References: <158507130343.15666.8018068546764556975.stgit@john-Precision-5820-Tower> User-Agent: StGit/0.17.1-dirty MIME-Version: 1.0 Sender: netdev-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: netdev@vger.kernel.org With current ALU32 subreg handling and retval refine fix from last patches we see an expected failure in test_verifier. With verbose verifier state being printed at each step for clarity we have the following relavent lines [I omit register states that are not necessarily useful to see failure cause], #101/p bpf_get_stack return R0 within range FAIL Failed to load prog 'Success'! [..] 14: (85) call bpf_get_stack#67 R0_w=map_value(id=0,off=0,ks=8,vs=48,imm=0) R3_w=inv48 15: R0=inv(id=0,smax_value=48,var32_off=(0x0; 0xffffffff)) 15: (b7) r1 = 0 16: R0=inv(id=0,smax_value=48,var32_off=(0x0; 0xffffffff)) R1_w=inv0 16: (bf) r8 = r0 17: R0=inv(id=0,smax_value=48,var32_off=(0x0; 0xffffffff)) R1_w=inv0 R8_w=inv(id=0,smax_value=48,var32_off=(0x0; 0xffffffff)) 17: (67) r8 <<= 32 18: R0=inv(id=0,smax_value=48,var32_off=(0x0; 0xffffffff)) R1_w=inv0 R8_w=inv(id=0,smax_value=9223372032559808512, umax_value=18446744069414584320, var_off=(0x0; 0xffffffff00000000), s32_min_value=0, s32_max_value=0, u32_max_value=0, var32_off=(0x0; 0x0)) 18: (c7) r8 s>>= 32 19 R0=inv(id=0,smax_value=48,var32_off=(0x0; 0xffffffff)) R1_w=inv0 R8_w=inv(id=0,smin_value=-2147483648, smax_value=2147483647, var32_off=(0x0; 0xffffffff)) 19: (cd) if r1 s< r8 goto pc+16 R0=inv(id=0,smax_value=48,var32_off=(0x0; 0xffffffff)) R1_w=inv0 R8_w=inv(id=0,smin_value=-2147483648, smax_value=0, var32_off=(0x0; 0xffffffff)) 20: R0=inv(id=0,smax_value=48,var32_off=(0x0; 0xffffffff)) R1_w=inv0 R8_w=inv(id=0,smin_value=-2147483648, smax_value=0, R9=inv48 20: (1f) r9 -= r8 21: (bf) r2 = r7 22: R2_w=map_value(id=0,off=0,ks=8,vs=48,imm=0) 22: (0f) r2 += r8 value -2147483648 makes map_value pointer be out of bounds After call bpf_get_stack() on line 14 and some moves we have at line 16 an r8 bound with max_value 48 but an unknown min value. This is to be expected bpf_get_stack call can only return a max of the input size but is free to return any negative error in the 32-bit register space. And further C signature returns 'int' which provides no guarantee on the upper 32-bits of the register. Lines 17 and 18 clear the top 32 bits with a left/right shift but use ARSH so we still have worst case min bound before line 19 of -2147483648. At this point the signed check 'r1 s< r8' meant to protect the addition on line 22 where dst reg is a map_value pointer may very well return true with a large negative number. Then the final line 22 will detect this as an invalid operation and fail the program. To fix add a signed less than check to ensure r8 is greater than 0 at line 19 so the bounds check works as expected. Programs _must_ check for negative return codes or they will fail to load now. But on the other hand they were buggy before so for correctness the check really is needed. Signed-off-by: John Fastabend --- .../testing/selftests/bpf/verifier/bpf_get_stack.c | 3 ++- 1 file changed, 2 insertions(+), 1 deletion(-) diff --git a/tools/testing/selftests/bpf/verifier/bpf_get_stack.c b/tools/testing/selftests/bpf/verifier/bpf_get_stack.c index f24d50f..24aa6a0 100644 --- a/tools/testing/selftests/bpf/verifier/bpf_get_stack.c +++ b/tools/testing/selftests/bpf/verifier/bpf_get_stack.c @@ -7,7 +7,7 @@ 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, 28), + BPF_JMP_IMM(BPF_JEQ, BPF_REG_0, 0, 29), BPF_MOV64_REG(BPF_REG_7, BPF_REG_0), BPF_MOV64_IMM(BPF_REG_9, sizeof(struct test_val)), BPF_MOV64_REG(BPF_REG_1, BPF_REG_6), @@ -16,6 +16,7 @@ BPF_MOV64_IMM(BPF_REG_4, 256), BPF_EMIT_CALL(BPF_FUNC_get_stack), BPF_MOV64_IMM(BPF_REG_1, 0), + BPF_JMP32_REG(BPF_JSLT, BPF_REG_0, BPF_REG_1, 20), BPF_MOV64_REG(BPF_REG_8, BPF_REG_0), BPF_ALU64_IMM(BPF_LSH, BPF_REG_8, 32), BPF_ALU64_IMM(BPF_ARSH, BPF_REG_8, 32), From patchwork Tue Mar 24 17:40:36 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: John Fastabend X-Patchwork-Id: 221952 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-6.8 required=3.0 tests=DKIM_SIGNED,DKIM_VALID, DKIM_VALID_AU,FREEMAIL_FORGED_FROMDOMAIN,FREEMAIL_FROM, HEADER_FROM_DIFFERENT_DOMAINS, INCLUDES_PATCH, MAILING_LIST_MULTI, SIGNED_OFF_BY, SPF_HELO_NONE, SPF_PASS autolearn=unavailable autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id D5BDEC41621 for ; Tue, 24 Mar 2020 17:40:52 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.kernel.org (Postfix) with ESMTP id B1A9120714 for ; Tue, 24 Mar 2020 17:40:52 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="EM+JwBde" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727656AbgCXRkw (ORCPT ); Tue, 24 Mar 2020 13:40:52 -0400 Received: from mail-pf1-f195.google.com ([209.85.210.195]:36419 "EHLO mail-pf1-f195.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1727266AbgCXRkw (ORCPT ); Tue, 24 Mar 2020 13:40:52 -0400 Received: by mail-pf1-f195.google.com with SMTP id i13so9670719pfe.3; Tue, 24 Mar 2020 10:40:49 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=subject:from:to:cc:date:message-id:in-reply-to:references :user-agent:mime-version:content-transfer-encoding; bh=YhiLqIoYtWaeo+b59KQvNZJFmnotR12vApEKv2KkKKg=; b=EM+JwBdey2hknC7bLTtzQl1Gkj8zTWw8cxLe5zOafCUMGRY2mNZflhndxpY7byFLUQ cKbCv6JsZUPBJb8HNvIcmUHOcgHw+5MRp/0YkSBxSSI0I51McejKS+LbX3RDoHNqCuSH evybQRKemfJ1yxY9mvAEd0H9B7Rz/BbHDIOG1UbZmYHQ8C0et5bZWhV9hdNNPgP7J78x NJlyiQKfHXbgtFIz/JgfPD/fz7kVcpqTxoMBIv4NlHhwBa8TUbSMC5nLbKElO+1puaUM 6jJgkrqhN6AsLnDU/43Iw0SywqZ21KgaNLWSYq8y/8vONWAK+cV7kAOnmsreDEg4bPgx r85Q== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:subject:from:to:cc:date:message-id:in-reply-to :references:user-agent:mime-version:content-transfer-encoding; bh=YhiLqIoYtWaeo+b59KQvNZJFmnotR12vApEKv2KkKKg=; b=ipZ7F5nPTRMhVteDFBpLn44nvPiuOo3Z06s4giPmfJSSINthX5Y+EC69PnleWrGAFo 7mIjVR74eF/NtHEuEmNG6x3fzlOTDIa2dc4hXo7RLs+KkAM8I71U4MaT3ljBJkR/3xfr lHPuwIqzH54JjGwHavqIFr5ax3XnMX4kCzxVGMSH0A73lcdiyN8g2rERyKSUnbkiMqpL a1LddpCPCcDg6FyGzY0I7SBY2YdE0UXFpYdghESphXOdSEUOGuvltkcPrOR3elwQ7LWJ lfNeYZb9naaf84iIgnqunTmrBIGGepoNooOAmA5bqXBsuHLOIc6/UFpYDYJ0nDHL/stg Lr7g== X-Gm-Message-State: ANhLgQ1zB3fu862nDr2t9ovnZSbm6PPILUjT0sII0smpYzngk/E2IK2j iDWWMZEULxXWb9MvUxOqBXI= X-Google-Smtp-Source: ADFU+vtQ5tWlbp2xnRTVvbFc1FtLI4jC/qujGDZZnESfOmNtHv7bshjQqe+0U3iDil9e55aWVDMV9A== X-Received: by 2002:a63:b04f:: with SMTP id z15mr27494569pgo.58.1585071649390; Tue, 24 Mar 2020 10:40:49 -0700 (PDT) Received: from [127.0.1.1] ([184.63.162.180]) by smtp.gmail.com with ESMTPSA id o11sm2860572pjb.18.2020.03.24.10.40.42 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Tue, 24 Mar 2020 10:40:49 -0700 (PDT) Subject: [bpf-next PATCH 09/10] bpf: test_verifier, #65 error message updates for trunc of boundary-cross From: John Fastabend To: ecree@solarflare.com, yhs@fb.com, alexei.starovoitov@gmail.com, daniel@iogearbox.net Cc: netdev@vger.kernel.org, bpf@vger.kernel.org, john.fastabend@gmail.com Date: Tue, 24 Mar 2020 10:40:36 -0700 Message-ID: <158507163638.15666.12642752583323152341.stgit@john-Precision-5820-Tower> In-Reply-To: <158507130343.15666.8018068546764556975.stgit@john-Precision-5820-Tower> References: <158507130343.15666.8018068546764556975.stgit@john-Precision-5820-Tower> User-Agent: StGit/0.17.1-dirty MIME-Version: 1.0 Sender: netdev-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: netdev@vger.kernel.org After changes to add update_reg_bounds after ALU ops and 32-bit bounds tracking truncation of boundary crossing range will fail earlier and with a different error message. Now the test error trace is the following 11: (17) r1 -= 2147483584 12: R0_w=map_value(id=0,off=0,ks=8,vs=8,imm=0) R1_w=invP(id=0,smin_value=-2147483584,smax_value=63) R10=fp0 fp-8_w=mmmmmmmm 12: (17) r1 -= 2147483584 13: R0_w=map_value(id=0,off=0,ks=8,vs=8,imm=0) R1_w=invP(id=0, umin_value=18446744069414584448,umax_value=18446744071562068095, var_off=(0xffffffff00000000; 0xffffffff)) R10=fp0 fp-8_w=mmmmmmmm 13: (77) r1 >>= 8 14: R0_w=map_value(id=0,off=0,ks=8,vs=8,imm=0) R1_w=invP(id=0, umin_value=72057594021150720,umax_value=72057594029539328, var_off=(0xffffffff000000; 0xffffff), s32_min_value=-16777216,s32_max_value=-1, u32_min_value=-16777216) R10=fp0 fp-8_w=mmmmmmmm 14: (0f) r0 += r1 value 72057594021150720 makes map_value pointer be out of bounds Because we have 'umin_value == umax_value' instead of previously where 'umin_value != umax_value' we can now fail earlier noting that pointer addition is out of bounds. Signed-off-by: John Fastabend --- tools/testing/selftests/bpf/verifier/bounds.c | 12 ++++-------- 1 file changed, 4 insertions(+), 8 deletions(-) diff --git a/tools/testing/selftests/bpf/verifier/bounds.c b/tools/testing/selftests/bpf/verifier/bounds.c index 7c9b659..cf72fcc 100644 --- a/tools/testing/selftests/bpf/verifier/bounds.c +++ b/tools/testing/selftests/bpf/verifier/bounds.c @@ -257,17 +257,15 @@ * [0x00ff'ffff'ff00'0000, 0x00ff'ffff'ffff'ffff] */ BPF_ALU64_IMM(BPF_RSH, BPF_REG_1, 8), - /* no-op or OOB pointer computation */ + /* error on OOB pointer computation */ BPF_ALU64_REG(BPF_ADD, BPF_REG_0, BPF_REG_1), - /* potentially OOB access */ - BPF_LDX_MEM(BPF_B, BPF_REG_0, BPF_REG_0, 0), /* exit */ BPF_MOV64_IMM(BPF_REG_0, 0), BPF_EXIT_INSN(), }, .fixup_map_hash_8b = { 3 }, /* not actually fully unbounded, but the bound is very high */ - .errstr = "R0 unbounded memory access", + .errstr = "value 72057594021150720 makes map_value pointer be out of bounds", .result = REJECT }, { @@ -299,17 +297,15 @@ * [0x00ff'ffff'ff00'0000, 0x00ff'ffff'ffff'ffff] */ BPF_ALU64_IMM(BPF_RSH, BPF_REG_1, 8), - /* no-op or OOB pointer computation */ + /* error on OOB pointer computation */ BPF_ALU64_REG(BPF_ADD, BPF_REG_0, BPF_REG_1), - /* potentially OOB access */ - BPF_LDX_MEM(BPF_B, BPF_REG_0, BPF_REG_0, 0), /* exit */ BPF_MOV64_IMM(BPF_REG_0, 0), BPF_EXIT_INSN(), }, .fixup_map_hash_8b = { 3 }, /* not actually fully unbounded, but the bound is very high */ - .errstr = "R0 unbounded memory access", + .errstr = "value 72057594021150720 makes map_value pointer be out of bounds", .result = REJECT }, {