[Crash] torch.searchsorted with out-of-bound sorter

[ganler]

🐛 Describe the bug

import torch

torch.searchsorted(
    torch.tensor([1, 2, 3]),
    2.5,  # when it becomes <= 2, it won't crash.
    sorter=torch.tensor(
        [0, 1, 2**22]
    ),  # when the last element < 2**21 + 1275831, it may not crash on my machine.
) # crash

torch.searchsorted should check the integrity of sorter where all elements (which represent indices) should be smaller than sorted_sequence's inner-most dimension size (3 here). Otherwise this is a out-of-bound read which leads to either:

1. crash;
2. silently returned with undefined resutls (which could potientially result in data leakage).

In numpy, the elements of sorter will be checked to make sure the data integrity:

import numpy as np

np.searchsorted(
    np.array([1, 2, 3]),
    3.5,  # when it becomes <= 2, it won't crash.
    sorter=np.array(
        [0, 1, 3]
    ),  # 3 is out-of-bound.
)
"""
  File "test.py", line 3, in <module>
    np.searchsorted(
  File "<__array_function__ internals>", line 180, in searchsorted
  File "/miniconda3/lib/python3.9/site-packages/numpy/core/fromnumeric.py", line 1387, in searchsorted
    return _wrapfunc(a, 'searchsorted', v, side=side, sorter=sorter)
  File "/miniconda3/lib/python3.9/site-packages/numpy/core/fromnumeric.py", line 57, in _wrapfunc
    return bound(*args, **kwds)
ValueError: Sorter index out of range.
"""

Versions

Env [click to expand]

"""
Collecting environment information...
PyTorch version: 1.14.0.dev20221202+cu117
Is debug build: False
CUDA used to build PyTorch: 11.7
ROCM used to build PyTorch: N/A

OS: Ubuntu 22.04.1 LTS (x86_64)
GCC version: (Ubuntu 11.3.0-1ubuntu1~22.04) 11.3.0
Clang version: Could not collect
CMake version: version 3.25.0
Libc version: glibc-2.35

Python version: 3.9.12 (main, Apr  5 2022, 06:56:58)  [GCC 7.5.0] (64-bit runtime)
Python platform: Linux-5.15.0-56-generic-x86_64-with-glibc2.35
Is CUDA available: True
CUDA runtime version: 11.6.124
CUDA_MODULE_LOADING set to: LAZY
GPU models and configuration: 
GPU 0: NVIDIA GeForce RTX 3090
GPU 1: NVIDIA GeForce RTX 3090
GPU 2: NVIDIA GeForce RTX 3090

Nvidia driver version: 515.86.01
cuDNN version: Probably one of the following:
/usr/lib/x86_64-linux-gnu/libcudnn.so.8.4.1
/usr/lib/x86_64-linux-gnu/libcudnn_adv_infer.so.8.4.1
/usr/lib/x86_64-linux-gnu/libcudnn_adv_train.so.8.4.1
/usr/lib/x86_64-linux-gnu/libcudnn_cnn_infer.so.8.4.1
/usr/lib/x86_64-linux-gnu/libcudnn_cnn_train.so.8.4.1
/usr/lib/x86_64-linux-gnu/libcudnn_ops_infer.so.8.4.1
/usr/lib/x86_64-linux-gnu/libcudnn_ops_train.so.8.4.1
HIP runtime version: N/A
MIOpen runtime version: N/A
Is XNNPACK available: True

Versions of relevant libraries:
[pip3] mypy-extensions==0.4.3
[pip3] numpy==1.22.4
[pip3] onnx2torch==1.5.3
[pip3] torch==1.14.0.dev20221202+cu117
[pip3] torchaudio==0.14.0.dev20221203+cu117
[pip3] torchtriton==2.0.0+0d7e753227
[pip3] torchvision==0.15.0.dev20221203+cpu
[conda] numpy                     1.22.4                   pypi_0    pypi
[conda] onnx2torch                1.5.3                    pypi_0    pypi
[conda] torch                     1.14.0.dev20221202+cu117          pypi_0    pypi
[conda] torchaudio                0.14.0.dev20221203+cu117          pypi_0    pypi
[conda] torchtriton               2.0.0+0d7e753227          pypi_0    pypi
[conda] torchvision               0.15.0.dev20221203+cpu          pypi_0    pypi
"""

[ganler]

I am happy to send a PR to fix this issue. However, it seems to safely use searchsorted, a checker for checking the integrity of sorter is needed (e.g., sorter.max() < sorter.numel()). However, it will compromise the performance by incurring an O(N) operation. Not sure if it is acceptable. Or a tradeoff is to add an option to disable such checking for best performance.

[ganler]

BTW, it seems the first link in https://github.com/pytorch/pytorch/security/policy is currently invalid (maybe I should report this case there if it becomes available).

[malfet]

BTW, it seems the first link in https://github.com/pytorch/pytorch/security/policy is currently invalid (maybe I should report this case there if it becomes available).

Hmm, what do you see when you are trying to access it?

[ganler]

By clicking https://github.com/pytorch/pytorch/security/advisories/new

I got page not found:

[malfet]

But you can access https://github.com/pytorch/pytorch/security/advisories, right?
And is there a button to file new security advisory?

[ganler]

Not really...

[malfet]

Hmm, and you can not follow https://docs.github.com/en/code-security/security-advisories/guidance-on-reporting-and-writing/privately-reporting-a-security-vulnerability ?

[ganler]

OK, I will try. I just hid the POC in #91606 (comment) in public for now.

[ganler]

Oh, I can do a private report now. It seems the green block now appears.

[malfet]

I've just tweaked the settings, but I'm curious, is the link correct?

[ganler]

Yes, I think the link is alive now. Thanks!

[malfet]

@ganler if you have the change that adds a boundary check, please do not hesitate to send a PR

[ganler]

Sure, but just want to confirm with you that the "boundary check" will be applied to every element in the sorter to see if it is within 0-sorter.size() (incurs O(N) complexity which I am afraid would hurt the performance a bit). But you can see that NumPy adds the check as well.