Skip to content

Out-of-bounds read in integrated mimalloc (fixed upstream) #134070

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom
Open
fuhsnn opened this issue May 15, 2025 · 1 comment · May be fixed by #134149
Open

Out-of-bounds read in integrated mimalloc (fixed upstream) #134070

fuhsnn opened this issue May 15, 2025 · 1 comment · May be fixed by #134149
Assignees
@colesbury
Labels
3.13 bugs and security fixes 3.14 bugs and security fixes 3.15 new features, bugs and security fixes interpreter-core (Objects, Python, Grammar, and Parser dirs) type-bug An unexpected behavior, bug, or error

Comments

@fuhsnn
Copy link

fuhsnn commented May 15, 2025 •
edited by bedevere-app bot
Loading

Bug report

Bug description:

The integrated mimalloc has out-of-bounds bug in the generic implementation of ctz/clz:

cpython/Include/internal/mimalloc/mimalloc/internal.h

Lines 847 to 870 in 6a22963

static inline size_t mi_ctz32(uint32_t x) {
// de Bruijn multiplication, see <http://supertech.csail.mit.edu/papers/debruijn.pdf>
static const unsigned char debruijn[32] = {
0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,
31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
};
if (x==0) return 32;
return debruijn[((x & -(int32_t)x) * 0x077CB531UL) >> 27];
}
static inline size_t mi_clz32(uint32_t x) {
// de Bruijn multiplication, see <http://supertech.csail.mit.edu/papers/debruijn.pdf>
static const uint8_t debruijn[32] = {
31, 22, 30, 21, 18, 10, 29, 2, 20, 17, 15, 13, 9, 6, 28, 1,
23, 19, 11, 3, 16, 14, 7, 24, 12, 4, 8, 25, 5, 26, 27, 0
};
if (x==0) return 32;
x |= x >> 1;
x |= x >> 2;
x |= x >> 4;
x |= x >> 8;
x |= x >> 16;
return debruijn[(uint32_t)(x * 0x07C4ACDDUL) >> 27];
}

On platforms with 64-bit UL, the multiplication in index calculation can grow much larger than array debruijn[].

It has been fixed in this upstream commit:
microsoft/mimalloc@ed31847

CPython versions tested on:

3.14, CPython main branch, 3.13, 3.15

Operating systems tested on:

Linux

Linked PRs
@fuhsnn fuhsnn added the type-bug An unexpected behavior, bug, or error label May 15, 2025
@picnixz picnixz added the interpreter-core (Objects, Python, Grammar, and Parser dirs) label May 15, 2025
@picnixz
Copy link
Member

picnixz commented May 15, 2025

cc @colesbury

@colesbury colesbury added 3.13 bugs and security fixes 3.14 bugs and security fixes 3.15 new features, bugs and security fixes labels May 16, 2025
@colesbury colesbury self-assigned this May 16, 2025
vedant713 added a commit to vedant713/cpython that referenced this issue May 17, 2025
@vedant713
Fix: Prevent out-of-bounds read in mi_clz32 and mi_ctz32 (python#134070)
6a5b559
vedant713 added a commit to vedant713/cpython that referenced this issue May 17, 2025
@vedant713
Fix: Prevent out-of-bounds read in mi_clz32 and mi_ctz32 (python#134070)
e8466b0
@vedant713 vedant713 linked a pull request May 17, 2025 that will close this issue
Open
vedant713 added a commit to vedant713/mimalloc that referenced this issue May 17, 2025
@vedant713
Fix: Prevent out-of-bounds read in mi_ctz_generic32 and mi_clz_generic32
7ec98ef 
This patch ensures that both mi_ctz_generic32 and mi_clz_generic32 perform safe indexing into the de Bruijn lookup tables by masking the computed index with `& 31`.

On platforms where unsigned long is 64-bit, the result of the de Bruijn multiplication and shift could exceed the valid index range (0–31), leading to an out-of-bounds read.

This change applies a bitwise AND mask to the final index:
- `mi_ctz_generic32`: debruijn[(((x & -(int32_t)x) * 0x077CB531U) >> 27) & 31]
- `mi_clz_generic32`: debruijn[((x * 0x07C4ACDDU) >> 27) & 31]

This matches the fix applied in python/cpython#134070 to its integrated mimalloc copy.

Fixes: python/cpython#134070
@vedant713 vedant713 mentioned this issue May 17, 2025
Closed
vedant713 added a commit to vedant713/cpython that referenced this issue May 17, 2025
@vedant713
pythongh-134070: Fix mi_clz32/mi_ctz32 to prevent out-of-bounds read (p…
960e266 
…ythonGH-134149)
@bedevere-app bedevere-app bot mentioned this issue May 17, 2025
Closed
vedant713 added a commit to vedant713/cpython that referenced this issue May 17, 2025
@vedant713
pythongh-134070: Add news entry for mi_clz32/mi_ctz32 out-of-bounds fix
eb1f908
vedant713 added a commit to vedant713/cpython that referenced this issue May 17, 2025
@vedant713
pythongh-134070: Add news entry for mimalloc out-of-bounds fix
64e9718
vedant713 added a commit to vedant713/cpython that referenced this issue May 17, 2025
@vedant713
pythongh-134070: Add news entry for mimalloc out-of-bounds fix
c961fa0
vedant713 added a commit to vedant713/cpython that referenced this issue May 17, 2025
@vedant713
pythongh-134070: Add news entry for mimalloc out-of-bounds fix
911c128
vedant713 added a commit to vedant713/cpython that referenced this issue May 17, 2025
@vedant713
pythongh-134070: Add news entry for mimalloc out-of-bounds fix
bce07b2
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@colesbury colesbury

Labels
3.13 bugs and security fixes 3.14 bugs and security fixes 3.15 new features, bugs and security fixes interpreter-core (Objects, Python, Grammar, and Parser dirs) type-bug An unexpected behavior, bug, or error
Projects
None yet
Milestone
No milestone
3 participants
@colesbury @picnixz @fuhsnn