From patchwork Wed Jun 7 12:39:50 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Maxim Mikityanskiy X-Patchwork-Id: 13270648 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id D01D7C7EE23 for ; Wed, 7 Jun 2023 12:41:10 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S240802AbjFGMlK (ORCPT ); Wed, 7 Jun 2023 08:41:10 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:50394 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S240980AbjFGMlH (ORCPT ); Wed, 7 Jun 2023 08:41:07 -0400 Received: from mail-ed1-x52c.google.com (mail-ed1-x52c.google.com [IPv6:2a00:1450:4864:20::52c]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id E3F5D1FCE; Wed, 7 Jun 2023 05:40:38 -0700 (PDT) Received: by mail-ed1-x52c.google.com with SMTP id 4fb4d7f45d1cf-51492ae66a4so1200351a12.1; Wed, 07 Jun 2023 05:40:38 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20221208; t=1686141598; x=1688733598; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=oyRCnZIlgTCZS2k2cmw93gRfUkOIg3FCKHPsHdQmeTI=; b=lTn59UvZK+9m4otDdCVvmwo232X4opAq22YknH/PcMiXVPVtRJoFEl63k3iNbGvIOL j44U9wcpWQ6o+d3+3hshH25V99ElOO+NBe++S80p3y6ZT7/w/ajrGMGZg6tDm8Fide3j em7Gu8NhAyAqwTUD9zaWE154sNNrS0BRQx2WTxnz5LeHT3DzqZNaqg4LhoLcUN3meCdH NGYCT/spStzrJFzLbBsOMPW12aeg1QpoJNxXBe1BgQgMdthROTnuKTg3GX4EnUs7l1g8 F+w0G5ZIV7Tn3fs1/roex23dRpv4KPuaqqbpd//X3eKtIxgBQiuOod2whacm6vQYaFzQ KzUw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1686141598; x=1688733598; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=oyRCnZIlgTCZS2k2cmw93gRfUkOIg3FCKHPsHdQmeTI=; b=hkHdsPME8J6LzPxjkUduVUo5ARD6Bn4wlqg/47o0pf7eIT8/VOwyHlEpwz0OBlpIiD te2cyWnCUbeAly9td0ObsOKRUrntAQi19MH2iwfIWy032lJfsSmCT7sy3ChmBY2cF26S ZAp1pwf7SpWvp13/EW6MorzxokVTjCJxl+14UIwSygYh1EL7aPT3EbN0uFggaxeiuNg4 TwmK82FFdOiMu5pdnSsovI3qbfV8ytKtZCwkqPXDNJgKRQyyBj/ou2o6oyBoPPkb9lm9 hwE1NVQ65hKvx0Qu3NXqaXINRak7TIOGRsEcR6cVvP7dRsET6Vnk+UYt6Efpvd052Q82 zEZw== X-Gm-Message-State: AC+VfDw0YJCmrqGxNYbK9pjzBPKhktQN43Qnh00y+DobohDiNGlkrE7o 7F2pZr3Lrpg46P/TEKF+k9NgfXYwittjtFIklF8= X-Google-Smtp-Source: ACHHUZ6g9G0Sg19PYJ91PERIrVvtJwYa3xtlsNxjuvp5JETX3NxH955Y9/Y7ynmSsxeFpTciUipMsg== X-Received: by 2002:a05:6402:31e2:b0:514:8d9a:386 with SMTP id dy2-20020a05640231e200b005148d9a0386mr4498975edb.30.1686141597690; Wed, 07 Jun 2023 05:39:57 -0700 (PDT) Received: from localhost (tor-exit-48.for-privacy.net. [185.220.101.48]) by smtp.gmail.com with ESMTPSA id c17-20020aa7c751000000b0050bc6d0e880sm5135597eds.61.2023.06.07.05.39.57 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 07 Jun 2023 05:39:57 -0700 (PDT) From: Maxim Mikityanskiy To: bpf@vger.kernel.org Cc: netdev@vger.kernel.org, linux-kselftest@vger.kernel.org, Daniel Borkmann , John Fastabend , Alexei Starovoitov , Andrii Nakryiko , Martin KaFai Lau , Eduard Zingerman , Maxim Mikityanskiy , Song Liu , Yonghong Song , KP Singh , Stanislav Fomichev , Hao Luo , Jiri Olsa , Mykola Lysenko , Shuah Khan , "David S. Miller" , Jakub Kicinski , Jesper Dangaard Brouer Subject: [PATCH bpf v4 1/2] bpf: Fix verifier id tracking of scalars on spill Date: Wed, 7 Jun 2023 15:39:50 +0300 Message-Id: <20230607123951.558971-2-maxtram95@gmail.com> X-Mailer: git-send-email 2.40.1 In-Reply-To: <20230607123951.558971-1-maxtram95@gmail.com> References: <20230607123951.558971-1-maxtram95@gmail.com> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: linux-kselftest@vger.kernel.org From: Maxim Mikityanskiy The following scenario describes a bug in the verifier where it incorrectly concludes about equivalent scalar IDs which could lead to verifier bypass in privileged mode: 1. Prepare a 32-bit rogue number. 2. Put the rogue number into the upper half of a 64-bit register, and roll a random (unknown to the verifier) bit in the lower half. The rest of the bits should be zero (although variations are possible). 3. Assign an ID to the register by MOVing it to another arbitrary register. 4. Perform a 32-bit spill of the register, then perform a 32-bit fill to another register. Due to a bug in the verifier, the ID will be preserved, although the new register will contain only the lower 32 bits, i.e. all zeros except one random bit. At this point there are two registers with different values but the same ID, which means the integrity of the verifier state has been corrupted. 5. Compare the new 32-bit register with 0. In the branch where it's equal to 0, the verifier will believe that the original 64-bit register is also 0, because it has the same ID, but its actual value still contains the rogue number in the upper half. Some optimizations of the verifier prevent the actual bypass, so extra care is needed: the comparison must be between two registers, and both branches must be reachable (this is why one random bit is needed). Both branches are still suitable for the bypass. 6. Right shift the original register by 32 bits to pop the rogue number. 7. Use the rogue number as an offset with any pointer. The verifier will believe that the offset is 0, while in reality it's the given number. The fix is similar to the 32-bit BPF_MOV handling in check_alu_op for SCALAR_VALUE. If the spill is narrowing the actual register value, don't keep the ID, make sure it's reset to 0. Fixes: 354e8f1970f8 ("bpf: Support <8-byte scalar spill and refill") Signed-off-by: Maxim Mikityanskiy Acked-by: Yonghong Song --- kernel/bpf/verifier.c | 3 +++ 1 file changed, 3 insertions(+) diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c index 5871aa78d01a..0dd8adc7a159 100644 --- a/kernel/bpf/verifier.c +++ b/kernel/bpf/verifier.c @@ -3868,6 +3868,9 @@ static int check_stack_write_fixed_off(struct bpf_verifier_env *env, return err; } save_register_state(state, spi, reg, size); + /* Break the relation on a narrowing spill. */ + if (fls64(reg->umax_value) > BITS_PER_BYTE * size) + state->stack[spi].spilled_ptr.id = 0; } else if (!reg && !(off % BPF_REG_SIZE) && is_bpf_st_mem(insn) && insn->imm != 0 && env->bpf_capable) { struct bpf_reg_state fake_reg = {};