Skip to content

Off-by-one memory error in a string fastsearch since 3.11 #105235

Closed
Closed
Off-by-one memory error in a string fastsearch since 3.11#105235
Assignees
sweeneyde
Labels
3.11only security fixes3.12only security fixes3.13only security fixesinterpreter-core(Objects, Python, Grammar, and Parser dirs)type-bugAn unexpected behavior, bug, or error

Description

@bacher09
bacher09
opened on Jun 2, 2023

Bug report

This bug happens in Objects/stringlib/fastsearch.h:589 during matching the last symbol. In some cases, it causes crashes, but it's a bit hard to reproduce since in order this to happen, the last symbol should be the last in this particular memory page and the next page should not be read accessible or have a different non-contiguous address with the previous one.

The simplest script that reproduces the bug for me is:

import mmap

def bug():
    with open("file.tmp", "wb") as f:
        # this is the smallest size that triggers bug for me
        f.write(bytes(8388608))

    with open("file.tmp", "rb") as f:
        with mmap.mmap(f.fileno(), 0, access=mmap.ACCESS_READ) as fm:
            with open("/proc/self/maps", "rt") as f:
                print(f.read())

            # this triggers bug
            res = fm.find(b"fo")

if __name__ == "__main__":
    bug()

But since the result of this script depends on a file system, kernel, and perhaps even a moon phase 😄 , here's a much more reliable way to reproduce it:

import mmap

def read_maps():
    with open("/proc/self/maps", "rt") as f:
        return f.read()

def bug():
    prev_map = frozenset(read_maps().split('\n'))
    new_map = None
    for i in range(0, 2049):
        # guard mmap
        with mmap.mmap(0, 4096 * (i + 1), flags=mmap.MAP_PRIVATE | mmap.MAP_ANONYMOUS, prot=0) as guard:
            with mmap.mmap(0, 8388608 + 4096 * i, flags=mmap.MAP_ANONYMOUS | mmap.MAP_PRIVATE, prot=mmap.PROT_READ) as fm:
                new_map = frozenset(read_maps().split('\n'))
                for diff in new_map.difference(prev_map):
                    print(diff)

                prev_map = new_map
                # this crashes
                fm.find(b"fo")
                print("---")

if __name__ == "__main__":
    bug()

This causes the bug across all Linux environments that I've tried. It uses a trick with inaccessible memory region to increase the chances of this bug happening and no files, to speed it up.
Here's some extra info from GDB:

Program received signal SIGSEGV, Segmentation fault.
0x000055555570ba81 in stringlib_default_find (s=0x7ffff6a00000 "", n=8388608, p=0x7ffff745a3e0 "fo", m=2, maxcount=-1, mode=1)
    at Objects/stringlib/fastsearch.h:589
589                 if (!STRINGLIB_BLOOM(mask, ss[i+1])) {
(gdb) pipe info proc mappings | grep -A 1 -B 1 file.tmp
      0x555555cb4000     0x555555d66000    0xb2000        0x0  rw-p   [heap]
      0x7ffff6a00000     0x7ffff7200000   0x800000        0x0  r--s   /home/slava/src/cpython/python_bug/file.tmp
      0x7ffff7400000     0x7ffff7600000   0x200000        0x0  rw-p   
(gdb) p &ss[i]
$1 = 0x7ffff71fffff ""
(gdb) p &ss[i + 1]
$2 = 0x7ffff7200000 <error: Cannot access memory at address 0x7ffff7200000>
(gdb) p i
$3 = 8388606
(gdb) p ss
$4 = 0x7ffff6a00001 ""
(gdb) p s
$5 = 0x7ffff6a00000 ""

Your environment

  • CPython 3.11.3
  • OS: Linux 6.1 (but it should be OS independent)

I've also tried a bit modified version of a script on OS X, and it crashes there as well.

cc @sweeneyde (since you are the author of d01dceb and 6ddb09f).

Linked PRs

Activity

  1. bacher09
    added
    type-bugAn unexpected behavior, bug, or error
    on Jun 2, 2023
  2. AlexWaygood
    changed the title [-]Of-by-one memory error in a string fastsearch since 3.11[/-] [+]Off-by-one memory error in a string fastsearch since 3.11[/+] on Jun 2, 2023

  3. bacher09 commented on Jun 2, 2023

    @bacher09
    bacher09
    on Jun 2, 2023
    Author

    Also wanted to add that this bug happens not only with mmap, it's very easy to see if you add a few extra assert statements into fastsearch.h.

  4. arhadthedev
    added
    interpreter-core(Objects, Python, Grammar, and Parser dirs)
    on Jun 2, 2023

  5. bacher09 commented on Jun 2, 2023

    @bacher09
    bacher09
    on Jun 2, 2023
    Author

    The simplest fix would be just doing bounds checks, but this could eat away some performance improvements from a fastsearch and perhaps someone who is more familiar with the intricacies of this search algorithm would be able to come up with something better.

    diff --git a/Objects/stringlib/fastsearch.h b/Objects/stringlib/fastsearch.h
index 7403d8a3f7..785407fbf6 100644
--- a/Objects/stringlib/fastsearch.h
+++ b/Objects/stringlib/fastsearch.h
@@ -577,7 +577,8 @@ STRINGLIB(default_find)(const STRINGLIB_CHAR* s, Py_ssize_t n,
                 continue;
             }
             /* miss: check if next character is part of pattern */
-            if (!STRINGLIB_BLOOM(mask, ss[i+1])) {
+            if ((i != w) && !STRINGLIB_BLOOM(mask, ss[i+1])) {
                 i = i + m;
             }
             else {
@@ -586,7 +587,8 @@ STRINGLIB(default_find)(const STRINGLIB_CHAR* s, Py_ssize_t n,
         }
         else {
             /* skip: check if next character is part of pattern */
-            if (!STRINGLIB_BLOOM(mask, ss[i+1])) {
+            if ((i != w) && !STRINGLIB_BLOOM(mask, ss[i+1])) {
                 i = i + m;
             }
         }
@@ -650,7 +652,8 @@ STRINGLIB(adaptive_find)(const STRINGLIB_CHAR* s, Py_ssize_t n,
                 }
             }
             /* miss: check if next character is part of pattern */
-            if (!STRINGLIB_BLOOM(mask, ss[i+1])) {
+            if ((i != w) && !STRINGLIB_BLOOM(mask, ss[i+1])) {
                 i = i + m;
             }
             else {
@@ -659,7 +662,8 @@ STRINGLIB(adaptive_find)(const STRINGLIB_CHAR* s, Py_ssize_t n,
         }
         else {
             /* skip: check if next character is part of pattern */
-            if (!STRINGLIB_BLOOM(mask, ss[i+1])) {
+            if ((i != w) && !STRINGLIB_BLOOM(mask, ss[i+1])) {
                 i = i + m;
             }
         }

  6. sweeneyde commented on Jun 2, 2023

    @sweeneyde
    sweeneyde
    on Jun 2, 2023
    Member

    Thanks for the report. We might be able to keep fastsearch.h the way it is (reading one past the end of the haystack, which is safe for null-terminated strings including python bytes objects), and instead alter the call for the mmap module to add a special-case to check for haystack[-len(needle):] == needle with one memcmp. I can look into this today.

  7. sweeneyde
    self-assigned this
    on Jun 2, 2023
  8. AlexWaygood
    added
    3.11only security fixes
    3.12only security fixes
    3.13only security fixes
    on Jun 3, 2023
  9. sweeneyde
    added a commit that references this issue on Jul 13, 2023

    gh-105235: Prevent reading outside buffer during mmap.find() (#105252)

    ab86426
  10. miss-islington
    added a commit that references this issue on Jul 13, 2023

    pythongh-105235: Prevent reading outside buffer during mmap.find() (p…

    7807061
  11. sweeneyde
    added 2 commits that reference this issue on Jul 15, 2023

    [3.12] gh-105235: Prevent reading outside buffer during mmap.find() (G…

    4f3edd6

    [3.11] gh-105235: Prevent reading outside buffer during mmap.find() (… (

    d488970
  12. sweeneyde
    closed this as completedon Jul 15, 2023
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

Labels

3.11only security fixes3.12only security fixes3.13only security fixesinterpreter-core(Objects, Python, Grammar, and Parser dirs)type-bugAn unexpected behavior, bug, or error

Projects

No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions