| lists.openwall.net | lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC | |
|
Open Source and information security mailing list archives
| ||
|
Message-ID: <bb80f378-d1ee-5d28-70d9-410106d1f854@fb.com>
Date: Fri, 26 Jan 2018 08:50:31 -0800
From: Yonghong Song <yhs@...com>
To: Eric Dumazet <eric.dumazet@...il.com>, <ast@...com>,
<daniel@...earbox.net>, <netdev@...r.kernel.org>
CC: <kernel-team@...com>
Subject: Re: [PATCH bpf-next 1/2] bpf: implement MAP_GET_NEXT_KEY command for
LPM_TRIE map
On 1/25/18 8:47 PM, Eric Dumazet wrote:
> On Thu, 2018-01-18 at 15:08 -0800, Yonghong Song wrote:
>
>> +find_leftmost:
>> + /* Find the leftmost non-intermediate node, all intermediate nodes
>> + * have exact two children, so this function will never return NULL.
>> + */
>
> syzbot [1] disagrees violently with this comment.
>
>> + for (node = rcu_dereference(*root); node;) {
>> + if (!(node->flags & LPM_TREE_NODE_FLAG_IM))
>> + next_node = node;
>> + node = rcu_dereference(node->child[0]);
>> + }
>> +do_copy:
>> + next_key->prefixlen = next_node->prefixlen;
>> + memcpy((void *)next_key + offsetof(struct bpf_lpm_trie_key, data),
>> + next_node->data, trie->data_size);
Thanks for reporting the issue. I looked at the update and delete code
in lpm_trie.c, it looks the comment that each intermediate node has two
children still holds. But I do find a problem:
616 /* Empty trie */
617 if (!rcu_dereference(trie->root))
618 return -ENOENT;
619
620 /* For invalid key, find the leftmost node in the trie */
621 if (!key || key->prefixlen > trie->max_prefixlen) {
622 root = &trie->root;
623 goto find_leftmost;
624 }
......
672 find_leftmost:
673 /* Find the leftmost non-intermediate node, all intermediate
nodes
674 * have exact two children, so this function will never
return NULL.
675 */
676 for (node = rcu_dereference(*root); node;) {
677 if (!(node->flags & LPM_TREE_NODE_FLAG_IM))
678 next_node = node;
679 node = rcu_dereference(node->child[0]);
680 }
It is possible that at line 617, trie->root is not NULL, but
later at line 676 is NULL. This will lead to next_node is NULL.
Will write a test to demonstrate this and examine intermediate node
property and propose a fix soon.
>
> [1]
>
> syzbot hit the following crash on e9dcd80b9d77a92bfae6ce42a451f5c5fd318832
> git://git.kernel.org/pub/scm/linux/kernel/git/bpf/bpf-next.git master
> config: https://urldefense.proofpoint.com/v2/url?u=https-3A__syzkaller-2Dbuganizer.googleplex.com_text-3Ftag-3DConfig-26id-3Db2216f04db2aa337e2bbf5ebd233919c3e2aa05f&d=DwICaQ&c=5VD0RTtNlTh3ycd41b3MUw&r=i6WobKxbeG3slzHSIOxTVtYIJw7qjCE6S0spDTKL-J4&m=RlBFk8FZhgGNl21aXGyx6UTYgjRdx0JLPJJXuREGo_c&s=aHeuptD-ytpgZCGZK_koCI1pUdJBACYveZ3RmN35g90&e=
> compiler: gcc (GCC) 7.1.1 20170620
>
>
> Unfortunately, I don't have any reproducer for this bug yet.
> raw crash log: https://urldefense.proofpoint.com/v2/url?u=https-3A__syzkaller-2Dbuganizer.googleplex.com_text-3Ftag-3DCrashLog-26id-3D4f78be02e2cd37040b8796322e02b147caae6024&d=DwICaQ&c=5VD0RTtNlTh3ycd41b3MUw&r=i6WobKxbeG3slzHSIOxTVtYIJw7qjCE6S0spDTKL-J4&m=RlBFk8FZhgGNl21aXGyx6UTYgjRdx0JLPJJXuREGo_c&s=RS0jaMd3n5ipeDtuFCL8B0152mZoHBx0b8xNq9AjDes&e=
> dashboard link: https://urldefense.proofpoint.com/v2/url?u=https-3A__syzkaller.appspot.com_bug-3Fextid-3D148b56534d9269ab7433&d=DwICaQ&c=5VD0RTtNlTh3ycd41b3MUw&r=i6WobKxbeG3slzHSIOxTVtYIJw7qjCE6S0spDTKL-J4&m=RlBFk8FZhgGNl21aXGyx6UTYgjRdx0JLPJJXuREGo_c&s=6L_1a0P1zZJmhAN49_cgfs8_LjnBW7h4L-SXEFF4orc&e=
>
> See https://urldefense.proofpoint.com/v2/url?u=http-3A__go_syzbot&d=DwICaQ&c=5VD0RTtNlTh3ycd41b3MUw&r=i6WobKxbeG3slzHSIOxTVtYIJw7qjCE6S0spDTKL-J4&m=RlBFk8FZhgGNl21aXGyx6UTYgjRdx0JLPJJXuREGo_c&s=iajwDJDDZzMqC0CxPLANoybk0lVIpuh2r7pz0rcD8kI&e= for details on how to handle this bug.
>
> kasan: CONFIG_KASAN_INLINE enabled
> kasan: GPF could be caused by NULL-ptr deref or user memory access
> general protection fault: 0000 [#1] SMP KASAN
> Dumping ftrace buffer:
> (ftrace buffer empty)
> Modules linked in:
> CPU: 1 PID: 8033 Comm: syz-executor3 Not tainted 4.15.0-rc8+ #4
> Hardware name: Google Google Compute Engine/Google Compute Engine, BIOS Google 01/01/2011
> RIP: 0010:trie_get_next_key+0x3c2/0xf10 kernel/bpf/lpm_trie.c:682
> RSP: 0018:ffff8801aa44f628 EFLAGS: 00010202
> RAX: dffffc0000000000 RBX: 0000000000000000 RCX: ffffffff81829a9d
> RDX: 0000000000000004 RSI: ffffc90003b7b000 RDI: 0000000000000020
> RBP: ffff8801aa44f8b0 R08: ffffffff817e8f95 R09: 0000000000000002
> R10: ffff8801aa44f790 R11: 0000000000000000 R12: 0000000000000000
> R13: 1ffff10035489f01 R14: fffffffffffffff4 R15: 0000000000000000
> FS: 00007fbb3b39b700(0000) GS:ffff8801db300000(0000) knlGS:0000000000000000
> CS: 0010 DS: 0000 ES: 0000 CR0: 0000000080050033
> CR2: 000000002057a000 CR3: 00000001c26e4005 CR4: 00000000001606e0
> DR0: 0000000000000000 DR1: 0000000000000000 DR2: 0000000000000000
> DR3: 0000000000000000 DR6: 00000000fffe0ff0 DR7: 0000000000000400
> Call Trace:
> map_get_next_key kernel/bpf/syscall.c:842 [inline]
> SYSC_bpf kernel/bpf/syscall.c:1881 [inline]
> SyS_bpf+0x11b4/0x4860 kernel/bpf/syscall.c:1846
> entry_SYSCALL_64_fastpath+0x29/0xa0
> RIP: 0033:0x452f19
> RSP: 002b:00007fbb3b39ac58 EFLAGS: 00000212 ORIG_RAX: 0000000000000141
> RAX: ffffffffffffffda RBX: 000000000071bea0 RCX: 0000000000452f19
> RDX: 0000000000000018 RSI: 0000000020daf000 RDI: 0000000000000004
> RBP: 000000000000003e R08: 0000000000000000 R09: 0000000000000000
> R10: 0000000000000000 R11: 0000000000000212 R12: 00000000006ef670
> R13: 00000000ffffffff R14: 00007fbb3b39b6d4 R15: 0000000000000000
> Code: 19 d3 ff e8 81 98 ed ff 4d 85 e4 0f 85 30 ff ff ff e8 73 98 ed ff 49 8d 7f 20 48 b8 00 00 00 00 00 fc ff df 48 89 fa 48 c1 ea 03 <0f> b6 04 02 84 c0 74 08 3c 03 0f 8e f2 0a 00 00 48 8b b5 98 fd
> RIP: trie_get_next_key+0x3c2/0xf10 kernel/bpf/lpm_trie.c:682 RSP: ffff8801aa44f628
> ---[ end trace b4eb675edf4c4059 ]---
> Kernel panic - not syncing: Fatal exception
> Dumping ftrace buffer:
> (ftrace buffer empty)
> Kernel Offset: disabled
> Rebooting in 86400 seconds..
>
Powered by blists - more mailing lists