Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) client-ip=2620:137:e000::1:20;
Date:   Fri, 2 Sep 2022 11:52:19 +0800
From:   Shung-Hsi Yu <shung-hsi.yu@suse.com>
To:     Daniel Borkmann <daniel@iogearbox.net>
Cc:     bpf@vger.kernel.org, linux-kernel@vger.kernel.org,
        Alexei Starovoitov <ast@kernel.org>,
        John Fastabend <john.fastabend@gmail.com>
Subject: Re: [RFC bpf-next 1/2] bpf: tnums: warn against the usage of
 tnum_in(tnum_range(), ...)
Message-ID: <YxF984GIloJWnV9x@syu-laptop>
References: <20220831031907.16133-1-shung-hsi.yu@suse.com>
 <20220831031907.16133-2-shung-hsi.yu@suse.com>
 <0f6d7f97-8cd9-d513-368b-39706dd6b06a@iogearbox.net>
Content-Type: text/plain; charset=utf-8
Content-Disposition: inline
In-Reply-To: <0f6d7f97-8cd9-d513-368b-39706dd6b06a@iogearbox.net>
MIME-Version: 1.0
X-MS-Exchange-AntiSpam-MessageData-ChunkCount: 1
X-MS-Exchange-AntiSpam-MessageData-0: =?utf-8?B?RmtGcGdzSUN4YjVoUmJNK0NMdjBGK1Q4UkwvZ0RXeVMydlFYNVFtTWVWRDlv?=
 =?utf-8?B?QmJIek1RQjJTSE82VTA2WnhaY3FMWVFCN2hDNDkxUXozQ3M3clRYb3Z1SitC?=
 =?utf-8?B?ME5haWhHSVJERHJ0MTh5d0VMZWRDWlY2enhUMWk2Y2QwaG5ISllZRDI0REky?=
 =?utf-8?B?OVBWU0g0OHBzMytOdlgyMWFvcjJNVUR1dnF1TGZZaXBBNEl4TlJVQ053M3oz?=
 =?utf-8?B?ZHBqWUJyZzNhbzY4b2JTd0xJYzFkbTlsNXpGdkJ6M2l3NW9XYUdNak1BSTVV?=
 =?utf-8?B?eFI0S1AvN2ZuVGJZc1RHYUhaV3ZnVlRqL3hMRlg2TlA5R0xkaVZ6RFVWZjIz?=
 =?utf-8?B?MHErS1IvaGlqeTNnZDBLNm9McFljNkhReStBMXlyaUUrQk95UkxaSkFzMTFU?=
 =?utf-8?B?b1F2WXEya2tUcVpJM29PMTA2UnluQkwyQlJFRFNQeTIyeU1PTXVLOU1FWGd4?=
 =?utf-8?B?SWdUNjRYZWxEOXczd2tEb3JXTUx6UWYzQnNrbG5CRXk2SDZhRXN1YlNnc1ly?=
 =?utf-8?B?Rzkzb2czOGZXOHlGdjZjQ3dqdUxGY2hNaDZBRWZYNUtIcVNXcnBLR1UwUUt2?=
 =?utf-8?B?bTUvZVhydUZLS3F6REpucXNLcWc5aGVXQUxrMHd6c0lSK0tJTXZZaU9id0NV?=
 =?utf-8?B?VGpFem5mREtsRXlSWnhWd29GVzBjZzNxZUV0c0VUNmRuZXMrSmZUdUxoallW?=
 =?utf-8?B?L3BzWXJiSEJkNERMMDBuOVJqQmx1RzNQcDhzRVpBNytKWWNIRllCcVdIVFlU?=
 =?utf-8?B?Vm9Kc3JGeVVWZ1JrMWJMdTBOQUE1RW8ybU1oQWEyZERDandhUnVtQW1uSEpM?=
 =?utf-8?B?ZXNzcmhKdFNPS1RXUWFqc1Flb1UrdXMvQXk3bGhadHFyZWNmbE0rbWVwZXA0?=
 =?utf-8?B?Wjg1RDRxd0Jzd0R4RVVad0xENkVwc3JWbmFxOUh5ZFk0UTJjRXg4TWplc3cw?=
 =?utf-8?B?YnZjQkZjZXgrRWxqZnc3YmVLaUl0TUpuei9RSDlGVXF3MlN1and6cGlqeUox?=
 =?utf-8?B?MHIvcHorUXgyK0lPc0ZlaDNYQ3JmOTVLU3JKZVYxdEJVQlV3eko1U3B3Smxm?=
 =?utf-8?B?L3lzZFg4WGVCVzFUZ0dReDdYRHFPQmxOU3FzYkFzUFdMWXZJNHJjeGZHaW5T?=
 =?utf-8?B?aTdQdXpQQ0VJTUN3SkpmN05CWC9Lajd1Um02TG1BR2hES1ZxNGNVTWIyRGRW?=
 =?utf-8?B?UGVHVHJ1aC84R0QrcFpoc29qaEtCdHRQOHF2ei9pQXgzcHg3WEhqaUtoanVK?=
 =?utf-8?B?cVNER0Y3Z0t5cFBHNmhDaHI1d1VsL0Y5QzVKNXA3QVg0NndIOEtsRVlqTGk4?=
 =?utf-8?B?MSs0TzNUWlZkbjVubGVqbHFnblc1dWRRMzhYTU1kTVZYM0dPbzJSN05pSGgz?=
 =?utf-8?B?Y25kUXZNVnBFcU4zV2d1VFJGUitoS2IxMlhzRkFvTzgvUWZQbmRNUEU1YzZZ?=
 =?utf-8?B?S0srbm54aHJ2UWFhYkk4aE9NOEt3WWlVaW5FbUVRck41SXc4SGIzbk5FOTU3?=
 =?utf-8?B?djNmbVB6amp1d3hvdmRGb250bGtOdUl4bTVKcjBUemRvUFJCN2RPcUFWVDcx?=
 =?utf-8?B?dHc5cndJWFNLTDl6bjhmTG9ibUJpMCtkUDFxemg4OW1RQ09GSzUyRXlVMnlY?=
 =?utf-8?B?TlZ3ZXdNYzZFd2o3WUVkcjRGL2xnWkFoZFdVbXJySi83Sjc3dFRIY0l3eXhr?=
 =?utf-8?B?eGQ4OWFDVkV0ZURiT1gwUThNbWRNOTRKZTgvS0phd0RmbWU4blcwSEp1OGV0?=
 =?utf-8?B?RTFXTWJrc0oycS9TWURQdTN3cEZ2Z2pXbDVDcVJEQUIwOGZwNFp5d0xxaEkv?=
 =?utf-8?B?TUdzVERxR0lDNHg3aWN1SVdXT211eGhZbWFXTERPRTNEQkpzTm5QRStBT1k3?=
 =?utf-8?B?VEJkSjNCd3kzaFVBcmFDZ1NMc0dVTkNJV3lvTFBOandYT3hiUllrWUpIZEIw?=
 =?utf-8?B?N0did0ZGeG4wcjBHSHF3bkxDOHB3ZXYyRDNTR2FnYlFTZjJhVUR1K3M2OUxp?=
 =?utf-8?B?RnZsSStYV0tvbi9VNFh4Q2M0SThPbkdBYXpCM2FnRkZHVUFpMGx2dE9sbnZD?=
 =?utf-8?B?TXVFMTd3LzIveldBZ21iSnk5aDJaZTFxRlV0V0JRNkVKbTNmanR0cFFjV09P?=
 =?utf-8?Q?iiQwGXjLzUxeAgfJF1B4bc8Pm?=
X-OriginatorOrg: suse.com
X-MS-Exchange-CrossTenant-Network-Message-Id: d8ce39f5-4141-4544-fd8a-08da8c968c63
X-MS-Exchange-CrossTenant-AuthSource: DB9PR04MB8107.eurprd04.prod.outlook.com
X-MS-Exchange-CrossTenant-AuthAs: Internal
X-MS-Exchange-CrossTenant-OriginalArrivalTime: 02 Sep 2022 03:52:26.0641
 (UTC)
X-MS-Exchange-CrossTenant-FromEntityHeader: Hosted
X-MS-Exchange-CrossTenant-Id: f7a17af6-1c5c-4a36-aa8b-f5be247aa4ba
X-MS-Exchange-CrossTenant-MailboxType: HOSTED
X-MS-Exchange-CrossTenant-UserPrincipalName: 7KOs/r//+7MJ7T8zrgfPeeDKLulQZU64R1l0vnrPCdR0ujXIFhvpEkmGXebnIx+pIJEeoLZZZ1X2ofn2E8fCaQ==
X-MS-Exchange-Transport-CrossTenantHeadersStamped: VI1PR04MB7072
X-Spam-Status: No, score=-2.1 required=5.0 tests=BAYES_00,DKIM_SIGNED,
        DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,RCVD_IN_DNSWL_NONE,
        RCVD_IN_MSPIKE_H2,SPF_HELO_PASS,SPF_PASS,T_SCC_BODY_TEXT_LINE
        autolearn=ham autolearn_force=no version=3.4.6
X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on
        lindbergh.monkeyblade.net
Precedence: bulk
List-ID: <linux-kernel.vger.kernel.org>
X-Mailing-List: linux-kernel@vger.kernel.org

On Thu, Sep 01, 2022 at 05:00:58PM +0200, Daniel Borkmann wrote:
> On 8/31/22 5:19 AM, Shung-Hsi Yu wrote:
> > Commit a657182a5c51 ("bpf: Don't use tnum_range on array range checking
> > for poke descriptors") has shown that using tnum_range() as argument to
> > tnum_in() can lead to misleading code that looks like tight bound check
> > when in fact the actual allowed range is much wider.
> > 
> > Document such behavior to warn against its usage in general, and suggest
> > some scenario where result can be trusted.
> > 
> > Link: https://lore.kernel.org/bpf/984b37f9fdf7ac36831d2137415a4a915744c1b6.1661462653.git.daniel@iogearbox.net/
> > Link: https://www.openwall.com/lists/oss-security/2022/08/26/1
> > Signed-off-by: Shung-Hsi Yu <shung-hsi.yu@suse.com>
> 
> Any objections from your side if I merge this? Thanks for adding doc. :)

There is a small typo I meant to fix with s/including/include below.

Other than that, none at all, thanks! :)

> > ---
> >   include/linux/tnum.h | 20 ++++++++++++++++++--
> >   1 file changed, 18 insertions(+), 2 deletions(-)
> > 
> > diff --git a/include/linux/tnum.h b/include/linux/tnum.h
> > index 498dbcedb451..0ec4cda9e174 100644
> > --- a/include/linux/tnum.h
> > +++ b/include/linux/tnum.h
> > @@ -21,7 +21,12 @@ struct tnum {
> >   struct tnum tnum_const(u64 value);
> >   /* A completely unknown value */
> >   extern const struct tnum tnum_unknown;
> > -/* A value that's unknown except that @min <= value <= @max */
> > +/* An unknown value that is a superset of @min <= value <= @max.
> > + *
> > + * Could including values outside the range of [@min, @max].
              ^^^^^^^^^
              include

> > + * For example tnum_range(0, 2) is represented by {0, 1, 2, *3*}, rather than
> > + * the intended set of {0, 1, 2}.
> > + */
> >   struct tnum tnum_range(u64 min, u64 max);
> >   /* Arithmetic and logical ops */
> > @@ -73,7 +78,18 @@ static inline bool tnum_is_unknown(struct tnum a)
> >    */
> >   bool tnum_is_aligned(struct tnum a, u64 size);
> > -/* Returns true if @b represents a subset of @a. */
> > +/* Returns true if @b represents a subset of @a.
> > + *
> > + * Note that using tnum_range() as @a requires extra cautions as tnum_in() may
> > + * return true unexpectedly due to tnum limited ability to represent tight
> > + * range, e.g.
> > + *
> > + *   tnum_in(tnum_range(0, 2), tnum_const(3)) == true
> > + *
> > + * As a rule of thumb, if @a is explicitly coded rather than coming from
> > + * reg->var_off, it should be in form of tnum_const(), tnum_range(0, 2**n - 1),
> > + * or tnum_range(2**n, 2**(n+1) - 1).
> > + */
> >   bool tnum_in(struct tnum a, struct tnum b);
> >   /* Formatting functions.  These have snprintf-like semantics: they will write
> > 
>