Message-ID: <bc4e05a5-5d97-2da0-0f18-b7fa55799158@fb.com>
Date:   Thu, 6 Jan 2022 17:19:36 -0800
User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.15; rv:91.0)
 Gecko/20100101 Thunderbird/91.4.1
Subject: Re: A slab-out-of-bounds Read bug in
 __htab_map_lookup_and_delete_batch
Content-Language: en-US
To:     butt3rflyh4ck <butterflyhuangxx@gmail.com>,
        Alexei Starovoitov <alexei.starovoitov@gmail.com>
CC:     Alexei Starovoitov <ast@kernel.org>,
        Daniel Borkmann <daniel@iogearbox.net>,
        Andrii Nakryiko <andrii@kernel.org>,
        Martin KaFai Lau <kafai@fb.com>,
        Song Liu <songliubraving@fb.com>,
        John Fastabend <john.fastabend@gmail.com>,
        KP Singh <kpsingh@kernel.org>,
        Networking <netdev@vger.kernel.org>, bpf <bpf@vger.kernel.org>,
        LKML <linux-kernel@vger.kernel.org>
References: <CAFcO6XMpbL4OsWy1Pmsnvf8zut7wFXdvY_KofR-m0WK1Bgutpg@mail.gmail.com>
 <CAADnVQJK5mPOB7B4KBa6q1NRYVQx1Eya5mtNb6=L0p-BaCxX=w@mail.gmail.com>
 <CAFcO6XMxZqQo4_C7s0T2dv3JRn4Vq4RDFqJO6ZQFr6kZzsnx9g@mail.gmail.com>
From:   Yonghong Song <yhs@fb.com>
In-Reply-To: <CAFcO6XMxZqQo4_C7s0T2dv3JRn4Vq4RDFqJO6ZQFr6kZzsnx9g@mail.gmail.com>
Content-Type: text/plain; charset="UTF-8"; format=flowed
Content-Transfer-Encoding: 7bit
MIME-Version: 1.0
X-MS-Exchange-AntiSpam-MessageData-ChunkCount: 1
X-MS-Exchange-AntiSpam-MessageData-0: =?utf-8?B?ZXpCY0xMMFhHMmZKVHNUNFFLa3MzMFNGWHJTUGwxTnNERkE4WHE4N3BvRDJ3?=
 =?utf-8?B?R1gyY256blBFMjlpSzlIdVc0a2JPTHVzbWRQdDBPSGgwbGxEdnUxRnNqUnd3?=
 =?utf-8?B?WFFORjdGaTlOcXhLMHdIZWc1eHRKYU1uaEtsT0hRQkJ6cWg1Q25Fa2piRVVp?=
 =?utf-8?B?em54aDFsZU10QXZhRzBSZW1NS1BhQkZzUkNnNG1UY3dzMERuS0Z1RWtNenIv?=
 =?utf-8?B?Q2Z4d1I0Y0twbkNJOVF3STc4WWVkSXplZDg5eGNXTmpxcVJmQ2c4Y0FKTUc0?=
 =?utf-8?B?T1prUTdVRks2MWxFa2M3bENaMVhRT1ZYcjE4T2xhdmhDMldram5uS3NKdFVT?=
 =?utf-8?B?K1h3VEdPemFiYjRvNTVNNER4RnFVdXRiK0VEV1h2UCtuZzhRN3Q5WHNMUkwy?=
 =?utf-8?B?dFBOM3lxQmYydzN3Snh5eDh2YlNBRHlYTGZUcS9oTWk3dXpKbUpOU2d1QTlR?=
 =?utf-8?B?aFJGYm4rUDB2TitYYnNoRC80UUNwZ1JOejRrRmJWUkphbm10VjUwSHRpRkJY?=
 =?utf-8?B?MUhoeE5ldFQzVzlQQ2JEOXhseFlmSWFLcEt4dzV2Mi9LN3REc3FsOTY2aDF5?=
 =?utf-8?B?T2RpaHdJSUJNU3V1cEwwYmdjTjVVaFB0Rk1rVXB5Qy9Rcmo5cURXaE9QbWR4?=
 =?utf-8?B?bzQvcHhTN2RZVGs1MlZaamp0QWR4aUlldzMzaFFmTUQwVE1xWE8xYWd0N3oy?=
 =?utf-8?B?WnlLRDJaR1Q0dDlWa0FSbm9iSzVEcUQvQW8vZkJETHJlOVJlWmJLWVVaTjBB?=
 =?utf-8?B?TTd5ZkNXSXNYd2U1aEFBcFJjWjNabm4raUVQSjBkdUowL0FvRFlvZW05aDhW?=
 =?utf-8?B?QUNMR2VWbDRXQlliSGhxek16Zm40UUU3SUo4WmFJa3Z0VUdkeS90Sm1xZXg1?=
 =?utf-8?B?SGVjMzVVQ0ZSTFRHbVpBa2hWaXdsaGUzOVIrd0lHN3ZrcnBqa0t0Qk1MSnFY?=
 =?utf-8?B?bE0zWGw0THJlbmUvYk02TnE4cDlVMXQ5c080NmxwOVRJUlRpdFFDV0ppWmc0?=
 =?utf-8?B?eXVwdnUreWVzYkpxbjlpMjNzY0d2RlpzZCtxdkU5WDhLWjE3eXc2Y1ppSHBX?=
 =?utf-8?B?ODMvUzZNb2RaRUpvMFp4RkhNdkU0MWt0Y292RkZHbjN5SmsxU0M1UWVRM0J3?=
 =?utf-8?B?QU5MN0NvUk9MdjdWaXZ0YUh3TkMxb3UvN2s1bmhGMkpETDFmMjIrTlY4cmF1?=
 =?utf-8?B?NFNUUDdFanVwc2NhNUh1QzJHbFVsYXJpS1ltSnd5U3JzN1pmWjBkbCtmMEU1?=
 =?utf-8?B?bVFKYnNKbW1RbHNUL2JEY2FOMkpoTzhjbjRDKzNjOEU4Qm1rM0dNN2k1WVlh?=
 =?utf-8?B?cFdpNm0vZUo5ZXlmKzRSTVVSTWtSTmdsWkhVOU92L29wWFlBR3V1L1IvazBU?=
 =?utf-8?B?Y0R6cEFuK1FqbWI0SVRaOHJhTEgvZlpvZ2ZrTkJaTE9UUkdtY3ZEb3BKcW1y?=
 =?utf-8?B?QkxjNk8xa0N6NERlMVROMGFkVUdqeVRQYzRrbEZsdExkeU5RRVhyNGVVRXdO?=
 =?utf-8?B?ZFhhbDg3L3c5SENXUE5UVXpTYy9tdGJDbDVwWnAyS3BDcGFWMTdRMXBxK1lz?=
 =?utf-8?B?SWVjUlpKVGZBNkE2OUwxMkcwaVVtZE1EQ3A2Y1YzZXEvbG5UM2Q2d3U5Q1kw?=
 =?utf-8?B?dytEb0xXSnNiNDBMdWJTTUZ6ZC9MckRzdjZ1MXdpMWcwQUZmbms0VmFjdFBo?=
 =?utf-8?B?L01VSGpUa3V3dGVuTUs0NEVXT2NlRkViUjgwNW9sUGZ4RWd1VEpMc1dXMndZ?=
 =?utf-8?B?UExNajhZd3IvK0pQYW05clRpeXo1NzdnbkEvMjBDUCtnWmNFRnNVbTdqc1Yr?=
 =?utf-8?B?cXlia29DekM3WkVsdnpubDVONWR3ZlhVeVgydkZHZTU4SzFKR2VFN3FSK0tH?=
 =?utf-8?B?ZFZJcVRkaFNqWUtmZmo0TFVOMlozbklwcm5yd3RGZ25IUmZmbjdMYTFvV0Fu?=
 =?utf-8?B?YnFEdm5YS0FWbE5tcmVIcmF6NWtOZDZGdE1FeEhlRzJnazhvMVZaZkkyNldK?=
 =?utf-8?B?U0tQSEdkVFFnUWZ0bWFDN29KM3NHelM5SmdGUDNwR1JNOEJncG9MMG9NWHBW?=
 =?utf-8?B?KytIZXVVaFcvWXhjVTBsZ2RIa3A0SG4xNFpMSEZidFN1cmhjVGtPUG12cDBW?=
 =?utf-8?B?bmN2bXp6VDN2OFArbXplaVlrSy9UUkJnbzY2dm0xYTdxSkxLSU4rUHJUT1k0?=
 =?utf-8?B?Y1E9PQ==?=
X-MS-Exchange-CrossTenant-Network-Message-Id: a7838404-4d4b-4bc2-2024-08d9d17bc73b
X-MS-Exchange-CrossTenant-AuthSource: SN6PR1501MB2064.namprd15.prod.outlook.com
X-MS-Exchange-CrossTenant-AuthAs: Internal
X-MS-Exchange-CrossTenant-OriginalArrivalTime: 07 Jan 2022 01:19:40.5702
 (UTC)
X-MS-Exchange-CrossTenant-FromEntityHeader: Hosted
X-MS-Exchange-CrossTenant-Id: 8ae927fe-1255-47a7-a2af-5f3a069daaa2
X-MS-Exchange-CrossTenant-MailboxType: HOSTED
X-MS-Exchange-CrossTenant-UserPrincipalName: R3Nc8Huj9lubcqWJA26Fe/9PrgcESW3kjCBm1oaX6XiRqWd9z3RBO4ns/grqf2bp
X-MS-Exchange-Transport-CrossTenantHeadersStamped: SA1PR15MB4436
X-OriginatorOrg: fb.com
X-Proofpoint-GUID: j2eJG3jEBN8rJ1_b5oYOyBs0tpGtj9ec
X-Proofpoint-ORIG-GUID: j2eJG3jEBN8rJ1_b5oYOyBs0tpGtj9ec
X-Proofpoint-Virus-Version: vendor=baseguard
 engine=ICAP:2.0.205,Aquarius:18.0.790,Hydra:6.0.425,FMLib:17.11.62.513
 definitions=2022-01-06_10,2022-01-06_01,2021-12-02_01
X-Proofpoint-Spam-Details: rule=fb_outbound_notspam policy=fb_outbound score=0 impostorscore=0
 priorityscore=1501 clxscore=1031 lowpriorityscore=0 mlxscore=0 spamscore=0
 phishscore=0 suspectscore=0 mlxlogscore=864 adultscore=0 bulkscore=0
 malwarescore=0 classifier=spam adjust=0 reason=mlx scancount=1
 engine=8.12.0-2110150000 definitions=main-2201070007
X-FB-Internal: deliver
Precedence: bulk
List-ID: <linux-kernel.vger.kernel.org>
X-Mailing-List: linux-kernel@vger.kernel.org


On 12/29/21 7:23 PM, butt3rflyh4ck wrote:
> Hi, the attachment is a reproducer. Enjoy it.
> 
> Regards,
>     butt3rflyh4ck.
> 
> 
> On Thu, Dec 30, 2021 at 10:23 AM Alexei Starovoitov
> <alexei.starovoitov@gmail.com> wrote:
>>
>> On Wed, Dec 29, 2021 at 2:10 AM butt3rflyh4ck
>> <butterflyhuangxx@gmail.com> wrote:
>>>
>>> Hi, there is a slab-out-bounds Read bug in
>>> __htab_map_lookup_and_delete_batch in kernel/bpf/hashtab.c
>>> and I reproduce it in linux-5.16.rc7(upstream) and latest linux-5.15.11.
>>>
>>> #carsh log
>>> [  166.945208][ T6897]
>>> ==================================================================
>>> [  166.947075][ T6897] BUG: KASAN: slab-out-of-bounds in _copy_to_user+0x87/0xb0
>>> [  166.948612][ T6897] Read of size 49 at addr ffff88801913f800 by
>>> task __htab_map_look/6897
>>> [  166.950406][ T6897]
>>> [  166.950890][ T6897] CPU: 1 PID: 6897 Comm: __htab_map_look Not
>>> tainted 5.16.0-rc7+ #30
>>> [  166.952521][ T6897] Hardware name: QEMU Standard PC (i440FX + PIIX,
>>> 1996), BIOS 1.13.0-1ubuntu1 04/01/2014
>>> [  166.954562][ T6897] Call Trace:
>>> [  166.955268][ T6897]  <TASK>
>>> [  166.955918][ T6897]  dump_stack_lvl+0x57/0x7d
>>> [  166.956875][ T6897]  print_address_description.constprop.0.cold+0x93/0x347
>>> [  166.958411][ T6897]  ? _copy_to_user+0x87/0xb0
>>> [  166.959356][ T6897]  ? _copy_to_user+0x87/0xb0
>>> [  166.960272][ T6897]  kasan_report.cold+0x83/0xdf
>>> [  166.961196][ T6897]  ? _copy_to_user+0x87/0xb0
>>> [  166.962053][ T6897]  kasan_check_range+0x13b/0x190
>>> [  166.962978][ T6897]  _copy_to_user+0x87/0xb0
>>> [  166.964340][ T6897]  __htab_map_lookup_and_delete_batch+0xdc2/0x1590
>>> [  166.965619][ T6897]  ? htab_lru_map_update_elem+0xe70/0xe70
>>> [  166.966732][ T6897]  bpf_map_do_batch+0x1fa/0x460
>>> [  166.967619][ T6897]  __sys_bpf+0x99a/0x3860
>>> [  166.968443][ T6897]  ? bpf_link_get_from_fd+0xd0/0xd0
>>> [  166.969393][ T6897]  ? rcu_read_lock_sched_held+0x9c/0xd0
>>> [  166.970425][ T6897]  ? lock_acquire+0x1ab/0x520
>>> [  166.971284][ T6897]  ? find_held_lock+0x2d/0x110
>>> [  166.972208][ T6897]  ? rcu_read_lock_sched_held+0x9c/0xd0
>>> [  166.973139][ T6897]  ? rcu_read_lock_bh_held+0xb0/0xb0
>>> [  166.974096][ T6897]  __x64_sys_bpf+0x70/0xb0
>>> [  166.974903][ T6897]  ? syscall_enter_from_user_mode+0x21/0x70
>>> [  166.976077][ T6897]  do_syscall_64+0x35/0xb0
>>> [  166.976889][ T6897]  entry_SYSCALL_64_after_hwframe+0x44/0xae
>>> [  166.978027][ T6897] RIP: 0033:0x450f0d
>>>
>>>
>>> In hashtable, if the elements' keys have the same jhash() value, the
>>> elements will be put into the same bucket.
>>> By putting a lot of elements into a single bucket, the value of
>>> bucket_size can be increased to overflow.
>>>   but also we can increase bucket_cnt to out of bound Read.

I tried the attachment (reproducer) and cannot reproduce the issue
with latest bpf-next tree.
My config has kasan enabled. Could you send the matching .config file
as well so I could reproduce?

>>
>> Can you be more specific?
>> If you can send a patch with a fix it would be even better.
>>
>>> the out of bound Read in  __htab_map_lookup_and_delete_batch code:
>>> ```
>>> ...
>>> if (bucket_cnt && (copy_to_user(ukeys + total * key_size, keys,
>>> key_size * bucket_cnt) ||
>>>      copy_to_user(uvalues + total * value_size, values,
>>>      value_size * bucket_cnt))) {
>>> ret = -EFAULT;
>>> goto after_loop;
>>> }
>>> ...
>>> ```
>>>
>>> Regards,
>>>   butt3rflyh4ck.
>>>
>>>
>>> --
>>> Active Defense Lab of Venustech
> 
> 
>