Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 23.128.96.36 as permitted sender) client-ip=23.128.96.36;
Date:   Thu, 12 Oct 2023 16:14:38 +0800
From:   Shung-Hsi Yu <shung-hsi.yu@suse.com>
To:     Alexei Starovoitov <alexei.starovoitov@gmail.com>
Cc:     Hao Sun <sunhao.th@gmail.com>, Alexei Starovoitov <ast@kernel.org>,
        Daniel Borkmann <daniel@iogearbox.net>,
        John Fastabend <john.fastabend@gmail.com>,
        Andrii Nakryiko <andrii@kernel.org>,
        Martin KaFai Lau <martin.lau@linux.dev>,
        Song Liu <song@kernel.org>,
        Yonghong Song <yonghong.song@linux.dev>,
        KP Singh <kpsingh@kernel.org>,
        Stanislav Fomichev <sdf@google.com>,
        Hao Luo <haoluo@google.com>, Jiri Olsa <jolsa@kernel.org>,
        bpf <bpf@vger.kernel.org>, LKML <linux-kernel@vger.kernel.org>
Subject: Re: [PATCH bpf-next v3 1/3] bpf: Detect jumping to reserved code
 during check_cfg()
Message-ID: <ZSeq7ieG7Cq13w67@u94a>
References: <20231011-jmp-into-reserved-fields-v3-0-97d2aa979788@gmail.com>
 <20231011-jmp-into-reserved-fields-v3-1-97d2aa979788@gmail.com>
 <CAADnVQJnhfbALtNkCauS_ZwRfybcb_mryEvZW7Uu1uOSshQ9Ew@mail.gmail.com>
Content-Type: text/plain; charset=utf-8
Content-Disposition: inline
Content-Transfer-Encoding: 8bit
In-Reply-To: <CAADnVQJnhfbALtNkCauS_ZwRfybcb_mryEvZW7Uu1uOSshQ9Ew@mail.gmail.com>
MIME-Version: 1.0
X-MS-Exchange-AntiSpam-MessageData-ChunkCount: 1
X-MS-Exchange-AntiSpam-MessageData-0: =?utf-8?B?NVVXNG1hYUhqL2duQmJWVUVzbENUL1pFa0o4dlNSWDdrM081ZzlKM3RhTXdx?=
 =?utf-8?B?U1ZuS0xkYTNUVGFHUytJcmdqaFZuRWJwUk5Jc05lRjg1MmdOSTRwWWM5OUVW?=
 =?utf-8?B?aWE5OXExT3FGYzYwcCtOWmhCekhwYkU4OTMwOUtkbkt6WGZXSVJQRzlha01r?=
 =?utf-8?B?a1RDMXVNbVBoVjFkdndFbTcyajRKMDNCM3YrMVppU2NwMk1PbHNHbWl0YjZN?=
 =?utf-8?B?NzVoSzRKQ1hWZFJXblpTTzE4ZmxNcjZBTlArWkpWcGZHWDQ5UDAxV2lyYW9R?=
 =?utf-8?B?Rkw3cmJqa2JsSDFqRTBGQVdxLy9hYUhIdFNZZko3cHE0SzJLWm1pM1pIbkRF?=
 =?utf-8?B?M1dsZnFaL0kwYjRvVGlLMlV1SmU3ZFFSVEZNa0pldG1GdERBS1BCOTZxQmk4?=
 =?utf-8?B?Qmd0dVRPbkhqTHNZUTc5TExTRlQzVDd2YzBCMSthL1lWSTRDdHBvUW8vVHpv?=
 =?utf-8?B?UGZjdytDU1NlRUFDY2Q0b3h0VS9zWFVtVWdva2xpSnl4Zkp2a2JSSjN4VG5h?=
 =?utf-8?B?bWJjRWpkckxwTTBvMS9COEgwV0JqWTQ3ZnVlT1lXdEFsYnIzek1HL1MyZ2R6?=
 =?utf-8?B?anpCUnpqZnFaNzlZS3dubCt1OGNhY2ZBMFhCVmZZTGNUeGZpMkZTazJLZktJ?=
 =?utf-8?B?NTk5WS9HdUxzNGtWQ0Z3RitNWTJ0cFFCM0FjYW5xY2dEQjZYZUlDa3lxOUY5?=
 =?utf-8?B?b0N1KzZIay84VnZrK1E5VHo1a3lPNC9GSDRESXdTZGNPb2xTTVhQUVViMktU?=
 =?utf-8?B?c3d5ZHNURjZXaDk0TktNUmJYSXlsTWE1OE1GemFtdmFZWFB0STZiWURnWS82?=
 =?utf-8?B?UUlacUg4M3FEeVBnUHQ3U2drb25mNDNWYmJjblNFL3l5S1dncTNEbm9zM2ZC?=
 =?utf-8?B?MU1YcmhHTUJEbWo5bFZiODhZSDBMS1F6K3pueWNRNWlKVVdobHZMUVB5Zk90?=
 =?utf-8?B?Qk9kay91TlpiNlpTYzVGcGtxT0hhZWNwNldtNXdiMDBvRkJhTjBCYzJJTEpO?=
 =?utf-8?B?YXBaTGNwWHFSSVBpZWNCS25neU1sbXdCVFB1c3BHNjd2NW53ZzBUeURKYmkx?=
 =?utf-8?B?RW1KUXBscmNaRTJHSDA2R0QwWEtMM0JnSnpwcXJ5RFBjUHZMVXg3UWpsZE9s?=
 =?utf-8?B?RERjeWwwbUFMa1lFUUIwTC9QSHFOTmIzRVQzbHhJUk1hU1JjRStnWVFsRnU1?=
 =?utf-8?B?bHo3M096K3k0VmNUNjJvdmdKdjdFbER4eCtzdFMyYnR0QUZaWVpQTGg5RFIr?=
 =?utf-8?B?V291N2pzNU1XS1NralFlakxSUnJDSU1UUmFpODhiLzJtdGlWVHFudk1hSm95?=
 =?utf-8?B?V0ZCaWtQTFArSUR1dHc0VzB4NWhDK0V1SXZIWjNHU0xIU2tya25jamk1MUk2?=
 =?utf-8?B?S2RIemt2RjFpZXk2YU91dzZDZWtUTzM5QTl2SjVVZThGM3gzdjlxRVRrWGxa?=
 =?utf-8?B?VnNRMFZvN3Z4ZXY4MkN3WXdGMFJDelA5UzQ4TWQxNWZzSWR2a1cvajdXU1ZU?=
 =?utf-8?B?eE1wbGxTK01MWXE5bENzZE40Z3VkWS9Cd1VZRlE1MExFa25KY3cwNThsUnkv?=
 =?utf-8?B?REFPSEtsTFV4N2JWZ29DUjNoSUVXUm9nRUtDNXl4MXRKWlo4TEZiYkM2K0tT?=
 =?utf-8?B?aWJZTE1yKzN3UXB6YTR2M3B5MkdTUCtXZFVPejJpZ2IyWWtWaDhLWFd5ZE1L?=
 =?utf-8?B?RVdyTXhLVERMelFoVHZXS1MyNjBSc3N4RjVHVFpqRWl2RHhrQ08xNkVsZm1m?=
 =?utf-8?B?NmdTeG9paEFCQUtrOVl5b3BCOWRndnV4UEJzL1hnQlA1Nk93OFBvK0FJVzA0?=
 =?utf-8?B?UE9mYVg0b0hteGFxRVg3TUp0bHhlKzNZU3RtYVg4RWp6NHYvUmNqWUpMWFpa?=
 =?utf-8?B?NWxkQklhZmIydEV1b1pTUkRRblg0UnRNRzZxWmttNzBkbU43ZVR4cmpLUXd6?=
 =?utf-8?B?U3JrcjM3cWJNdmdxdkRmckxWT3pqSzk0TjhJVDk0eXdrVk9tOTN5TFppUVNS?=
 =?utf-8?B?M3QzZGlkSlpnSEZMZnVUSTROcWZZN1R0WlROVnlHWXUzOU1mOVVSZTh5Qjc2?=
 =?utf-8?B?U00za0M1WDVKWUJrZHZDSmNHc3hTcnE0NDBSMnEvYk5Qa0UvL3lCUFMxdmYy?=
 =?utf-8?Q?PuO54Xc9uUKerqTcGa0ZOK8Az?=
X-OriginatorOrg: suse.com
X-MS-Exchange-CrossTenant-Network-Message-Id: 61886939-aae4-463b-ac07-08dbcafb4fa4
X-MS-Exchange-CrossTenant-AuthSource: AS8PR04MB9510.eurprd04.prod.outlook.com
X-MS-Exchange-CrossTenant-AuthAs: Internal
X-MS-Exchange-CrossTenant-OriginalArrivalTime: 12 Oct 2023 08:14:52.6268
 (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: 6W3IRv5sjLipZ27lsd8xGuEEjqAiAoo2S79CSezuzWD9w8TJxfPdZMO/K/7fVIA/rFzA/Lx7eUj6WT9U1grvvw==
X-MS-Exchange-Transport-CrossTenantHeadersStamped: AM9PR04MB8383
X-Spam-Status: No, score=-0.8 required=5.0 tests=DKIM_SIGNED,DKIM_VALID,
	DKIM_VALID_AU,HEADER_FROM_DIFFERENT_DOMAINS,MAILING_LIST_MULTI,
	SPF_HELO_NONE,SPF_PASS autolearn=unavailable autolearn_force=no
	version=3.4.6
X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on pete.vger.email
Precedence: bulk
List-ID: <linux-kernel.vger.kernel.org>
X-Mailing-List: linux-kernel@vger.kernel.org
X-Greylist: Sender passed SPF test, not delayed by milter-greylist-4.6.4 (pete.vger.email [0.0.0.0]); Thu, 12 Oct 2023 01:15:10 -0700 (PDT)

On Wed, Oct 11, 2023 at 06:38:56AM -0700, Alexei Starovoitov wrote:
> On Wed, Oct 11, 2023 at 2:01 AM Hao Sun <sunhao.th@gmail.com> wrote:
> >
> > Currently, we don't check if the branch-taken of a jump is reserved code of
> > ld_imm64. Instead, such a issue is captured in check_ld_imm(). The verifier
> > gives the following log in such case:
> >
> > func#0 @0
> > 0: R1=ctx(off=0,imm=0) R10=fp0
> > 0: (18) r4 = 0xffff888103436000       ; R4_w=map_ptr(off=0,ks=4,vs=128,imm=0)
> > 2: (18) r1 = 0x1d                     ; R1_w=29
> > 4: (55) if r4 != 0x0 goto pc+4        ; R4_w=map_ptr(off=0,ks=4,vs=128,imm=0)
> > 5: (1c) w1 -= w1                      ; R1_w=0
> > 6: (18) r5 = 0x32                     ; R5_w=50
> > 8: (56) if w5 != 0xfffffff4 goto pc-2
> > mark_precise: frame0: last_idx 8 first_idx 0 subseq_idx -1
> > mark_precise: frame0: regs=r5 stack= before 6: (18) r5 = 0x32
> > 7: R5_w=50
> > 7: BUG_ld_00
> > invalid BPF_LD_IMM insn
> >
> > Here the verifier rejects the program because it thinks insn at 7 is an
> > invalid BPF_LD_IMM, but such a error log is not accurate since the issue
> > is jumping to reserved code not because the program contains invalid insn.
> > Therefore, make the verifier check the jump target during check_cfg(). For
> > the same program, the verifier reports the following log:
> >
> > func#0 @0
> > jump to reserved code from insn 8 to 7
> >
> > Signed-off-by: Hao Sun <sunhao.th@gmail.com>
> > ---
> >  kernel/bpf/verifier.c | 7 +++++++
> >  1 file changed, 7 insertions(+)
> >
> > diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> > index eed7350e15f4..725ac0b464cf 100644
> > --- a/kernel/bpf/verifier.c
> > +++ b/kernel/bpf/verifier.c
> > @@ -14980,6 +14980,7 @@ static int push_insn(int t, int w, int e, struct bpf_verifier_env *env,
> >  {
> >         int *insn_stack = env->cfg.insn_stack;
> >         int *insn_state = env->cfg.insn_state;
> > +       struct bpf_insn *insns = env->prog->insnsi;
> >
> >         if (e == FALLTHROUGH && insn_state[t] >= (DISCOVERED | FALLTHROUGH))
> >                 return DONE_EXPLORING;
> > @@ -14993,6 +14994,12 @@ static int push_insn(int t, int w, int e, struct bpf_verifier_env *env,
> >                 return -EINVAL;
> >         }
> >
> > +       if (e == BRANCH && insns[w].code == 0) {
> > +               verbose_linfo(env, t, "%d", t);
> > +               verbose(env, "jump to reserved code from insn %d to %d\n", t, w);
> > +               return -EINVAL;
> > +       }
> 
> I don't think we should be changing the verifier to make
> fuzzer logs more readable.

Taking fuzzer out of consideration, giving users clearer explanation for
such verifier rejection could save a lot of head scratching.

Compiler shouldn't generate such program, but its plausible to forget to
account that BPF_LD_IMM64 consists of two instructions when writing
assembly (especially with filter.h-like macros) and have it jump to the 2nd
part of BPF_LD_IMM64.

> Same with patch 2. The code is fine as-is.

The only way BPF_SIZE(insn->code) != BPF_DW conditional in check_ld_imm()
can be met right now is when we have a jump to the 2nd part of LD_IMM64; but
what this conditional actually guard against is not straight-forward and
quite confusing[1].


Shung-Hsi

1: https://lore.kernel.org/bpf/0cf50c32-ab67-ef23-7b84-ef1d4e007c33@fb.com/