Memory Tagging and a JS address sanitizer

Attention - this doc is public and shared with the world!

Author: pierre.langlois@arm.com

Contacts: pierre.langlois@arm.com, martyn.capewell@arm.com

Status: Draft | Accepted | Done

LGTMs needed

Abstract & TL;DR

Future Arm CPUs will support memory tagging as an extension to the architecture. We would like to present some ideas on how we could use it to detect exploitation^{[a][b][c][d][e][f]} of the JS heap in the wild.

To that end, we are considering implementing a prototype for a “JS address sanitizer”. It would do a similar job to the C++ address sanitizers by detecting out-of-bounds accesses and use-after-free, but for JS objects. With help from the hardware we think it can be made cheap enough for use in production. The first goal of such a prototype would be to validate this is actually the case.

The project is only at its inception, but we’d like to collect early feedback on the overall idea and direction. We’re only collecting LGTMs to validate the approach, merging an implementation in V8 will be for a future decision when we have more data and a definite design.

Background on memory tagging and MTE

Version 8.5 of the Arm architecture features the Memory Tagging Extension (MTE). It is expected to be deployed on Android for C/C++ code when hardware becomes available. This feature is only available on 64-bit.

It’s an implementation of the concept of memory tagging. You can find a good overview in this paper: https://arxiv.org/pdf/1802.09517.pdf.

In a nutshell, the new architecture extension works as follows:

• Physical memory can store 4 bits of metadata for every 16 bytes, this is the allocation tag.

• New instructions available in userspace can read and write allocation tags associated with an address.

• On existing Arm64 CPUs, the top byte of pointers is available as metadata, this is known as TBI (Top Byte Ignore).^{[g][h][i][j][k][l][m]} With MTE, 4 of those bits are now reserved for the address tag.

• When accessing memory, the address tag in the pointer and the allocation tag have to match. There are two modes of operation called “Precise” and “Imprecise” that dictate if a fault should happen immediately or be delayed for performance reasons.

In memory tagging terms, we have a tag size of 4 bits and a tag granule of 16 bytes which are fixed values defined by the architecture. Other implementations of memory tagging such as HWASAN may have a different size and granule but the concept is the same.

The interface between userspace and the kernel is being worked on. This feature is going to be “opt-in” on a per-page basis and expected to be abstracted by the various C/C++ memory allocators. When it becomes available, V8’s C++ code should get it “for free”, except for the Zone Allocator, which will need to be ported to use it, but that’s for a future design document :-).

You’ll find more information about MTE in the various announcements:

• https://security.googleblog.com/2019/08/adopting-arm-memory-tagging-extension.html

• https://community.arm.com/developer/ip-products/processors/b/processors-ip-blog/posts/enhancing-memory-safety

• https://developer.arm.com/-/media/Arm%20Developer%20Community/PDF/Arm_Memory_Tagging_Extension_Whitepaper.pdf?revision=ef3521b9-322c-4536-a800-5ee35a0e7665&la=en

Main objective and requirements

The ultimate goal is to have a V8 that can detect illegal accesses on the JS heap as they happen.

We want to mitigate against exploiting a heap related bug to build arbitrary read and write primitives. In this document, we assume such primitives have not been obtained already, and the approach is to detect when a bug is being exploited ^{[n][o][p][q][r][s]}in a probabilistic way -  it is not a protection mechanism.

For instance, If we have a compiler bug where it was tricked into removing a bound check, if one tries to use this bug to perform an illegal access on the JS heap we want to be able to detect it. Of course we still need to fix the bug in the compiler to block the attack after it was detected. For this to be cheap enough to be deployed, not all invalid memory accesses will be detected, but as long as it isn’t deterministic then it’ll be effective.

Here are some high-level requirements:

• All JS objects have to be covered. We cannot know in advance where an exploitable bug is going to be.

• It must be cheap enough to run in production with MTE-enabled hardware.

• It must work on hardware without MTE  to help with development and maintenance. As well as optionally using it with fuzzing.

These are long term goals. For now, we are thinking of building prototype to validate that they are attainable.

A “JS address sanitizer” with memory tagging

The idea is the same as what C++ address sanitizers already do: instrument memory accesses to detect overflows, underflows and use-after-free. While our focus is on memory tagging, we think this could have the potential to be abstracted into its own feature, allowing for different implementations that rely on a different mechanism.

Memory tagging with TBI

The general idea is to mimic what HWASAN does by building on top of TBI to implement memory tagging in software. TBI, for Top Byte Ignore, is an Arm64 feature where the top byte of pointers is free to be used by the application.

The general idea is:

• Allocate “shadow memory” for every V8 page on the JS heap. Every addressable slot on the heap needs to have an allocation tag associated with it in the shadow memory. Since objects are aligned to the tagged pointer size, the tag granule has to be 8 bytes with full pointers and 4 bytes with compressed pointers.

• When allocating objects, set a random allocation tag in the shadow memory and return it to the user with the top byte of the pointer set to it. When freeing an object, we should also set a new random tag, to detect use-after-free. Allocation tags will also have to be reset when moving and trimming objects. The tag size can be up to 8 bits wide because we have 8 bits available in pointers.

• When accessing an object on the heap, we load the allocation tag from the shadow memory and compare it with the top byte of the pointer^{[t][u][v][w][x]}. If they don’t match we report an error.

As part of the prototype, we would have to decide which memory access should be checked. We should limit ourselves to what can be directly instrumented from user JS code so we’d cover jitted code, builtins and the interpreter. It’s likely this isn’t going to be practical so we might focus only on code generated by TurboFan and leave C++ code out entirely.

The memory and runtime overhead of this is obviously too high for production use but we’re hoping it can be useful as a debugging feature along with fuzzing. Also, it serves as an implementation that can work on existing hardware so that when MTE is available V8 will be ready for it.

We can identify major challenges with this approach that our prototype would need to find solutions to:

• HW tagged pointers

On Arm64, a pointer with its top byte set to anything other than 0 is called a “tagged pointer^[y][z]” which we’ll refer to as a “HW tagged pointer” in this document to disambiguate with V8’s own tagged object pointers.  

Since using them is a requirement, we need V8 to be able to cope with them. Doing some early prototyping, we identified places in the GC where pointers with different HW tags need to be compared^[aa][ab][ac]. For this to work, the top byte needs to be stripped^[ad][ae]. See the next sections for more details about challenges for the runtime due to HW tagged pointers.

The main challenge is that it’s an Arm64-only feature which will appear in generic code. If we use this as a debugging feature that runs regularly in the CI, then we could make sure V8 keeps working with HW tagged pointers but it’s extra work.^[af][ag] On x86 however, we could still use HW tagged pointers to make sure to also catch errors, but that means we have to always strip the HW tag before use to avoid faults due to non-canonical pointers. This could be a lot of work too.

Instead, in theory, it could be possible to “emulate” HW tagged pointer on x86 using page aliasing. We could dedicate part of the virtual address space as tags, as suggested by the HWASAN paper:

It is theoretically possible to implement HWASAN on architectures that do

not have top-byte-ignore using page aliasing (mmap(MAP_SHARED)) to store the address tag in the meaningful address bits. However, our experiments indicate that such implementation would be impractical due to huge stress on the TLB.

Since our use-case is more limited than for HWASAN where every C++ pointers to the heap is tagged, it could be feasible. We can also note that OpenJDK uses this technique in order to implement a concurrent copying GC where upper bits of the address space encode state about object pointers.

This is still a grey area but one worth investigating.

• Challenges of having HW tagged pointers in the runtime

Essentially, having the top bits of object pointers set means we can no longer trivially compare a HeapObject’s internal representation with any Address. We now have to strip the HW tags unless we know they are identical. So the challenge here is to find all the places where stripping the top bits is required and then design an abstraction so that future code still conforms. We can then measure what the overhead of the extra stripping operations is, especially since an abstraction is likely to strip HW tags more often than needed. Luckily, future hardware with MTE support will provide a “SUBP” instruction that ignores the top byte when comparing pointers so we believe this shouldn’t be an issue if we can re-compile.

So we’ve taken some time to actually prototype it, by setting the top byte of object pointers on allocations and then introducing stripping operations until tests passed. Here’s a summary of our findings:

• Converting a HeapObject or Address to a Page pointer.

The way to get a Page pointer is by aligning an object pointer to the page size. With memory tagging, the header will have a different allocation tag from that of the object so we have to apply the header’s tag to the pointer as well as aligning. To make things simpler, we can leave the header with an allocation tag of zero so all we have to do is strip the tag:

  page = object & ~((0xff << 56) | kPageAlignmentMask)

Which is just as cheap. We can investigate assigning a random allocation tag to the header as well as a future improvement.

• HeapObject and Address comparisons.

There are a few places where we compare a HeapObject’s pointer with an Address that need fixing. They are not hard to fix but show the need for a good abstraction:

• Looking up the markbit of an object.
• Checking if an object is below the age mark for promotion.
• Updating the current allocation pointer (top) from a newly allocated object.
• Maintaining order in the InvalidatedSlots, which are represented as a std::set<HeapObject>.

This is what we’ve currently had to fix when prototyping to get a proof of concept to pass the V8 tests. We might still find more in the future. In general, the easiest way to handle those is to strip the tag when converting a HeapObject’s Address into an Address used by the GC. However, this means that the resulting address cannot be dereferenced unless we read the allocation tag and apply it to the pointer. But we don’t have to do this for pointer comparisons. See the next section for more about places that need to read allocation tags in the GC.

• Challenges of checked memory accesses in the GC

With the JS address sanitizer enabled, checked memory accesses with the wrong HW tag in the pointer will fault. The GC itself is arguably less important to check than JS execution, but if we can check its memory accesses too then we should. In theory, future CPUs supporting memory tagging in hardware will not be able to tell the difference anyway. In practise we might be able to enable a mode that allows stripped pointers, with the HW tag 0, to bypass checks but we would much rather this mode wasn’t enabled. See this section for more details.

So we’ve added checked memory accesses in our prototype, comparing allocation tags with tags in the pointer for heap accesses. We’ve done this in code generated by TurboFan as well as in C++ and as a result found a few places in the GC that need special handling to support this.

• The marking bitmap and remembered sets do not preserve HW tags.

By design, these data-structures only store offsets from the start of the page, as bitmaps. So when iterating through the slots in a remembered set, or through live objects in a page, the pointers we get back will lack the HW tag and accessing them will trigger faults. In these instances the trivial thing to do is to read the allocation tags and apply them to the pointer.

Even though with hardware support reading and applying the tag is a single instruction, we do not know how expensive it will be. So we want to keep the possibility to optimize the GC for this use-case in the future:

• Adapt slot sets to also store tags for every pointer.

Here we would have a trade-off between memory and cycles. As opposed to the marking bitmap, the slots sets are dynamic so we could investigate increasing the number of bits for each slot so store the tag.

• Avoid reading the tags in LiveObjectVisit::RecomputeLiveBytes()

We cannot realistically change the marking bitmap to store tags for every live object, as its size would increase exponentially. But when computing how many live bytes we have on a page, we do not need to reconstruct valid pointers.

• We need to be able to iterate through all objects in a page.

The various HeapObject iterators need to be ported so that they read the allocation tags to construct valid HeapObjects. When prototyping, we saw this was mainly required for debugging, profiling and the --verify-heap option. However, we also need to iterate through objects in the to-space when updating pointers in live objects during mark-compact.

• Checking for a memento object is technically an out-of-bound access.

Our early prototype detected we were doing and out-of-bound access when checking if an object is followed by a Memento object. Since the memento is allocated together with its object, it will have the same allocation tag. When checking for its presence, we can read the allocation tag and if it differs from that of the object then it’s not there. I don’t think this is an optimisation though :-).

To conclude this section, the performance impact of these is still left to estimate and measure. We’re hoping it will be small enough, however if it isn’t this is a place with the “match-all” mode of the hardware can help. It is a mode where any pointer with it’s HW tag set to 0 will bypass any checks. We would rather this mode only be used as a last resort, as we’re concerned the security mitigations that the address sanitizer brings will be weaker because of it.

• Compressed HW tagged pointers

It’s very likely that compressed pointers will be the default in the near future. And with them, we’ll have to find a way to preserve tags which will add unavoidable extra overhead and complexity.

Our current thinking is that we’ll have to:

1. Reduce the tag size at the expense of lower probability of catching exploits. MTE supports a tag size of 4 bits^{[ah][ai][aj][ak]} so we could pick this number or go lower.

2. Find space to fit the tag in a compressed pointer, which is more problematic. We have two places we can find extra bits:

• Low bits: If we align objects to a higher granule, we can save some bits. Since the MTE tag granule is 16 bytes anyway, we can free 2 bits if we align objects to 16 bytes.

• High bits: We could reduce the maximum size of the heap to get extra bits at the top.

We haven’t investigated this further yet. One of the goals of writing a prototype implementation will be to measure what the memory and cycle overhead is. We need to find what the best tagging scheme is, taking into account the impact of object alignment and more complex compression/decompression routines.

• More complex allocation routines

Having to do extra work when allocating objects is going to be challenging. V8 doesn’t have a single point where objects are allocated:

• When allocating is just about bumping a pointer in a contiguous space, the allocation may be inlined^[al] in a builtin or jitted code. We’ll have to teach the compiler how to set allocation tags.

• TurboFan has an optimisation that folds allocations together. We need to allocate different tags for consecutive objects otherwise this is a major hole. We’ll have to either adapt the optimisation to also tag those objects separately, or disable^[am] it all-together when the sanitizer is on.

  ---

Running in production with MTE

When compared to the HWASAN approach in Memory tagging with TBI, MTE removes the need for a per-page shadow memory and explicit checks, those are now done in hardware. Here is what it will roughly look like:

Object allocations

We have new instructions that can create, read and write allocation tags. These instructions are not backwards-compatible so we’ll have to be careful how we use them depending on if we go for a compile-time or runtime option. There are intrinsics already available in the clang used by V8.

The basic use-case is to create a new tag for each allocation and write it to the corresponding allocation tags associated with that memory:

For this to work, the underlying pages need to be configured by the kernel as making use of MTE, otherwise the operations will have no effect. The proposed way to do this is likely to be with a new “PROT_MTE” flag passed to mmap.

For regular objects, the overhead of setting the allocation tag will be minimal. However, concerning large objects which get their own V8 page there can be a concern. We are currently reviewing the option to set a “background tag” that could be passed as a hint to mmap. It would instruct the kernel to set the allocation tag itself when lazily mapping pages, so that we do not have to do it in userspace.

This way, the impact should also be minimal, the kernel would set the tags as it’s zeroing pages before mapping them in the process.

Note that this interface is in very early stages, patches should be on the kernel mailing list shortly for discussion.

Aligning objects to 16 bytes

As we mentioned, the tag granule for MTE is 16 bytes. This means objects using it will have to be 16-bytes aligned instead of 8 or 4 depending on pointer compression.

As a result, running with MTE will have a memory overhead. We have conducted some investigation to measure the impact such an alignment would have by prototyping it. You’ll find more details in this section of the document.

Our hope is that the memory overhead will not be too bad compared to the benefit of being able to detect heap exploitation. However if it is, we can consider using MTE on a random subset of objects which we discuss later.

Match-all mode

MTE provides a mode where tag 0 is treated as a special tag that bypasses checks. So regardless of what the allocation tag is, you may strip the 4 bit tag from the pointer and access the memory. It is meant as a way for software that cannot deal with having the top byte of pointers to be ported more easily.

However, the plan is for this mode not to be enabled by default. As things stand currently, we’re thinking the kernel may not even expose it to userspace, at least not in the first version. Although this isn’t set in stone yet and the work done in V8 in this area could help making this decision. If it is to be enabled though, it would be a configuration done per-thread but we don’t know the exact details yet.

We fear we would lose on some security mitigation by having it on:

• We have one fewer tag to use. A higher probability of detecting bugs is always good to have.

• We could accidently leave a stripped JS object pointer on the heap.

In theory, a bug in the GC could accidently leave a stripped pointer behind. With 0 as its tag, accessing it would be unchecked and could be used to build an arbitrary read/write primitive undetected. With match-all disabled, we would catch such a bug in the GC when that pointer is used.

• Even with the JS address sanitizer defeated, MTE limits what you can do with an arbitrary read/write primitive.

This time assuming an attacker somehow managed to defeat the JS address sanitizer and built an arbitrary read/write primitive undetected. Even then, MTE could still acts as a mitigation since the primitive can only be used to dereference pointers it has access to. So for example, we could assign a random tag to page headers and this way, malicious code cannot try to access the page header from an object pointer without having to guess the tag.

So if we can, it’s preferable to have V8 work without match-all. But if the overhead of the JS address sanitizer is too high and it turns out it can help, we could consider it. For example, we could investigate turning it on only for GC threads and when the main thread performs a GC. It would help mitigate the concern of the GC accidently leaving an untagged pointer behind but we don’t know the cost of turning it on and off at this point.

Compile-time or runtime option?

Ideally, turning on the JS address sanitizer would be a decision made at runtime on startup. We want to be able to turn it on after we’ve checked that the hardware supports MTE, so that the same binary can work on existing and future CPUs.

After startup though, we don’t need to support turning it off, the option should be constant.

Challenges of a runtime option

It will bring a lot of complexity which might make a runtime option impractical:

• We’ll have multiple allocation routines to choose from.

This touches the generated builtins as well as jitted code because of inlined and folded allocations. Since the option will be constant after startup, we don’t think this will be a big problem.^{[an][ao][ap][aq][ar]}

• With pointer compression, we need a compression scheme that preserves tags.

This is the main issue, pointer compression was never designed to be a runtime option so changing the compression routines at runtime isn’t practical. We could rely on the option being constant to minimize the dispatch overhead but it will prevent inlining in both C++ and TurboFan code which is likely to have too big an impact. We could investigate having two sets of embedded builtins that we choose from on startup but doubling the size of the builtins may not be acceptable either.

A more realistic runtime approach would be to change the compression routines to preserve tags all the time. We can then measure the impact to see if it’s something we can work with since a mechanism to allow changing them at runtime is likely to be more expensive anyway.

So with this in mind, we’re wondering if a compile-time option would be more suitable, but it means different binaries will have to be shipped to devices equipped with MTE hardware in order to run in production^{[as][at][au][av][aw]}.

We’ll have to do some experiments to find the optimal tag preserving compression routines. And then see if using them all the time would be such a bad thing to do so we can make an informed decision. We would be interested to know if shipping different binaries would ever be an option though.^[ax][ay]

Security consideration

From a security perspective, if we have a runtime option an attacker with read/write primitives could try and turn the feature off even if we don’t support it.

That’s OK since, as mentioned in the requirements, our approach is to detect when an attack is happening in a probabilistic way, this is not a protection mechanism. If the attack succeeded and is undetected there’s not much we can do. For example, with a read and write primitive the attacker can potentially create another primitive that reads the allocation tags to bypass MTE entirely.

We can make the attacker’s life harder even after they’ve acquired read and write primitives but that’s outside the scope of this document.

Measuring and prototyping 16-bytes object alignment

As mentioned, object allocations need to be aligned to the tag granule, which is 16 bytes, in order to be checked in HW using MTE. We’ve prototyped it so we could measure the potential memory impact this would have for both full and compressed pointer builds.

Approaches to object alignment

Our experiment takes an inefficient approach in that it inserts filler objects between every allocation. So on allocation, if the pointer isn’t aligned we insert an additional object that will either be a “OnePointerFiller”, “TwoPointerFiller” or “FreeSpace”.

It was easier to do it this way because we already use this mechanism to make sure doubles are 64-bit aligned on 32-bit architectures. Indeed this solution is suitable if only a subset of objects are aligned. But for all allocations a better solution would be to align up object’s instance sizes. However that’s a lot more work to prototype.

So for the purpose of measuring memory consumption, using fillers is good enough. That being said, if later we decide to only check a random subset of objects in order to reduce the memory overhead, as described later, then using fillers should be acceptable.

Before looking into memory measurements, our prototype has a few caveats which could be useful to understand the results:

• Objects in the read-only space are not aligned. This is a little tricky since in order to add a filler object, you need a filler map pointer. And these maps live in the read-only space so we have a chicken and egg problem.
• --turbo-allocation-folding is turned off.
• --move-object-start is turned off.
• We’ve had to revert a JSON parser optimization that folds together a large number of HeapNumber allocations.
• Code objects are not aligned, as our target is primarily regular JS objects.

You may find a CL for this prototype here: https://chromium-review.googlesource.com/c/v8/v8/+/2280092.

Initial memory impact measured on v8.4

We’ve measured against V8 version 8.4, and also made sure we measure against our CL with a default alignment. That way we can see any memory impact that our “caveats” may have introduced.

We have three d8 shells:

• v8.4
• patched with default alignment
• patched with 16-bytes alignment

We’ve sampled the size taken by live objects on the heap at every GC, young and old. More specifically, we’ve sampled the used_heap_size statistic but the other values can be made available on request of course :-). So for a given run, we have as many values as the number of GCs that ran. Note that we haven’t collected benchmark scores during this investigation.

We’ve gathered results in a spreadsheet and plotted the raw values as well displayed the mean and standard deviation. The idea is to compare the statistics with the raw values to make sure they indeed reflect a trend to validate the result.

The experiment was done on an Odroid-N2 board with 4G of RAM running linux. And finally, you can find the results here: https://docs.google.com/spreadsheets/d/1vC-xDBU2kLBFX1iekJU40QT5A6HTsOd3se_7a1aadXM

Overall, we see the following:

• Compressed pointers: Memory consumption increases from 5 to 10%, with a few outliers that go up to 15%.
• Full pointers: Memory consumption increases from 2 to 5%, with a few outliers that go up to 10%.

That being said, there are quite a lot of outliers that indicate we may have corner cases to fix if we’re to implement this in the future. We may also have issues with our prototype itself. More investigation is needed to get to the bottom of those, hopefully we can identify solutions as well.

ARES6

Overall, the Basic, Babylon and ML benchmarks seem to be good indicators except for Babylon with full pointers which looks like we’ve hit a corner case or a bug. Something to investigate! The Air benchmark is not very reliable however.

We see a 6 to 12% increase in memory consumption with compressed pointers, whereas with full pointers results are from 2 to 4%.

Web-tooling

Web-tooling is harder to analyse so results here should be taken with a grain of salt. Only a few benchmarks show measurable differences with a 2% increase with full pointers and a 4 % increase with compressed pointers, except for babel which can go up to 7%.

The rest of the benchmarks are not very conclusive.

Octane

Results for octane vary a lot, but they can be pretty clear. Overall, most benchmarks show a 10 to 15% increase with compressed pointers while with full pointers the range is between 7 and 10%. The differences in octane are higher than with ARES6 and Web-tooling. It would be interesting to investigate PdfJS.

Compressed pointers approaches

This section is a WIP still, here be dragons :-)

We have a few different options when it comes to supporting compressed pointers which we’ll describe in this section. For each approach, our aim is to prototype it to a point where we can safely say if it’s doable or not. And if it is, we should evaluate what impact it would have.

Storing tags within objects

The general idea here is that instead of storing a tag in object pointers we store it in memory within objects themselves. Then we have to decide where exactly the tag should be stored, and when it should be applied to the top byte of a pointer.

Lazy vs eager tag application

If we focus on when the tag should be applied first, we can roughly position approaches between:

• Lazy tag application, where we apply the tag to the pointer just as we’re about to access the memory.

For every memory accesses, we would access the object’s tag and apply it:

    ;; Load tag from object.

    ldrb x16, [object, #(tag_offset - 1)]

    ;; Apply it to the top byte.

    orr x16, x16, object, lsl #56

    ;; Only then access the memory.

    ldr w0, [x16, #index]

This is quite straight-forward to implement in the backend. But, the big challenge is that at the moment the compiler isn’t always able to tell us if a given memory access has an object pointer at its base address. To implement this, we’ve had to annotate Load and Store operations, so applying the HW tag is effectively opt-in.

This is quite intrusive in V8, but isn’t as difficult as it sounds, especially thanks to the TNode<> type system that we can leverage to automatically opt-in nodes with Tagged inputs in builtins. Then both Torque and optimised JS also have this information. The rest of the memory accesses will be raw pointers which may or may not use memory tagging depending on their allocators. Then checking stack-allocated buffers is out-of-scope of this document.

Finally, as you’d expect, this approach is going to have a big impact on both code size and performance. However, it’s still useful to prototype it  to model what the worst case scenario would be. Then we can work on different approaches to speed things up.

• Eager tag application, where we apply the tag on decompression.

This approach applies the tag much earlier and would be combined with the decompression operation:

    ;; Read a compressed pointer from the heap and decompress

    ;; it.

    ldr w0, [object, #index]

    add x0, root, x0

    ;; Then load its tag and apply it to the top byte.

    ldrb x16, [x0, #(tag_offset - 1)]

    orr x0, x0, x16, lsl #56

However, we’ll also need to have a version of this that can work for both tagged pointers and SMIs:

      ;; Read a compressed pointer from the heap an

      ;; decompress it.

      ldr w0, [object, #index]

      tbz w0, #0, <skip>

      add x0, root, x0

      ;; Then load its tag and apply it to the top byte.

      ldrb x16, [x0, #(tag_offset - 1)]

      orr x0, x0, x16, lsl #56

    skip:

Which is a shame since it defeats the idea of smi-corruption where it does not matter what the top 32 bits of a SMI value is.

Another thing to note with this approach is that we now may have HW tagged pointers on the stack that the GC will need to visit as full pointers rather than compressed. Otherwise, if the GC only updates the low 32-bits, the new object will inherit the old tag which wouldn’t match.

At this time we haven’t yet investigated this approach.

• Somewhere in between.

The two opposite approaches are both not ideal although it seems an eager approach is the most sensible of the two. However, we could go further and investigate teaching the compiler about the tag application operation so that it would be able to place it at a more efficient place in between the decompression and the memory access.

This is somewhat similar to the pointer compression optimization work that was done in TurboFan, where V8 tried to place decompression operations itself to generate better code. In the end it was deemed better to eagerly decompress pointers as soon as they are read from the heap so we might face similar complexity issues here.

Storing a tag in object headers

The natural place we would store a tag within an object is its header, and in V8 that’s the Map word. In the next section we go into details on how it’s possible to “steal” bits from the Map word to place a tag and what challenges that brings, but first let’s consider the possibility of making object headers bigger so both a Map word and a tag can fit.

Since MTE requires 16-bytes granules, we can consider making the object header the size of a granule. We could have the following layout for example:

So that any space that isn’t the map word can be interpreted as a Smi by the GC and ignored.

The idea would be to have all object headers have the same HW memory tag assigned which would match with the pointer HW tag in the root address, which could be 0 for example. Then the rest of the object allocation would be assigned a different and random tag.

With this layout we can efficiently read and apply the tag:

    ;; Read a compressed object from the heap.

    ldr object, [slot, #index]

    add object, root, object

    ;; Apply the tag, which could be done immediately (eagerly) or

    ;; later before accessing the memory (lazily).

    ldr x16, [object, #(8 - 1)]

    orr object, object, x16

If this becomes an issue with regards to memory consumption, we could consider making it more compact by making the header 8 bytes instead of 16. However to do this we would have to enable “match-all” mode where the hardware allows unchecked memory accesses with a tag of 0. Otherwise it wouldn’t be possible to access the tag to begin with.

Challenges of updating tags in headers

When prototyping, we quickly saw that initialising the tag isn’t trivial. It needs to be done for all paths related to object initialisation, it cannot be done solely in the allocator where the tag itself is generated. Some of the issues faced are:

• The GC can no longer just “CopyBlock()” objects, it needs to either write the new tag, or make sure they skip over the words where the tag is placed by the allocator.
• There are places in the builtins that manually initialise an object which need to be adapted.
• Array left trimming in the GC needs to be adapted to copy the tag over to the new object.

For our prototyping needs, we’ve solved this problem in a somewhat inefficient way by writing the tag to the object on every map store operation. It simplifies things since it gives us a single place that writes the tag in the object that we can build upon.

So storing the map word becomes its own dedicated operation in V8 and again, here there are two approaches depending on the lazy vs eager tag application decision:

• With a lazy approach, where each memory access reads and applies the tag to the top byte of the pointer, our `object` pointer would never have a HW tag in its top byte to begin with. So we would initialise its header like this:

    ;; Store the map word in the header.

    str w0, [object, #-1]

    ;; Using a new MTE instruction, read the HW memory tag

    ;; for “object” into x1.

    ldg x1, [object]

    ;; The `ldg` instruction copies the input address and

    ;; adds a tag in bits 59-56, but we only want the tag.

    and x1, x1, #~(0xf << 56)

    ;; And store the tag in the header.

    str x1, [object, #(8 - 1)]

We can validate that this can work on existing hardware by replacing the `ldg` instruction with a regular memory access to shadow memory where we can store tags for every page on the JS heap. Of course this comes at a very high cost, similar to C++ address sanitizers.

This can be optimised further by having the allocator return the HW tag that it used for the allocation instead of accessing it using `ldg`. But doing so we have to make sure that we strip this tag from the pointer when converting it to a HeapObject pointer. Otherwise the GC’s pointer-updating phases will need to be adapted to replace full pointers on the stack rather than compressed ones.

Finally, this approach also results in issues with the compiler, since it mandates that any memory accesses beyond the header must happen after we’ve written the HW tag into the header. Since those accesses will be reading it in order to check for a match. When prototyping we’ve had to fix cases where memory accesses were modified in incompatible ways:

• The instruction scheduler can no longer re-order memory accesses around a map write.
• The store-store elimination pass needs to be adapted to either not delete redundant map writes, or be smarter and make sure the dominating map write happens first.

• With an eager approach, where we keep the HW tag in the top byte of the pointer immediately after decompression, our `object` pointer, just like all other heap object pointers, would have a tag in its top byte given by the allocator. Then we would initialise the header like this:

    ;; Strip the top of object so that it uses 0 as a HW tag which

    ;; would match the memory tag of the header. This could also

    ;; apply a specific non-zero HW tag used for all headers.    

    and x16, object, #~(0xf << 56)

    ;; Write the map word.

    str w0, [x16, #-1]

    ;; Now extract only the HW tag from the object and store it.

    and x17, object, #(0xf << 56)

    str x17, [x16, #(8 - 1)]

To conclude, so far we’ve prototyped a lazy approach and it’s allowed us to identify challenges but it does look like an eager approach would be more suited. We’ll do some investigation and update this document with our findings.

Re-using bits from map words

We’ve gone further in our prototype and investigated a more compact way to store a HW tag per object by “stealing” 4 bits from map words. We were inspired by research done in this area recently to think we should attempt to make it work.

Building on top of “match-all” mode

As mentioned earlier, if we keep the object header to be a single word, and so smaller than the MTE 16-byte granule, we may have to enable “match-all” mode in the architecture. In this mode any memory access can bypass HW checks if they use HW tag 0. This allows us to write the map word without knowing the tag. Alternatively, we can also directly read the correct tag manually.

For instance, if we were to implement an “eager” approach, we would do the following on decompression:

    ;; Read an object compressed pointer from the heap.

    ldr w0, [object, #index]

    add x0, root, x0

    ;; Load the map word and extract the tag from the top

    ;; 4 bits. This access needs to bypass hardware checks!

    ldr w16, [x0, #-1]

    ;; Apply it to the object pointer.

    and w16, w16, #(0xf << 28)

    orr x0, x0, x16, lsl #28

But this only works if we can make sure any pointer with a HW tag of 0, provided the root pointer’s top byte is also 0, bypasses checks in hardware. Although enabling “match-all” mode itself weakens security so we’ll have to be careful here.

Limiting the size of the map and read-only spaces.

In order to reserve bits from map words we can either align all map objects or restrict their allocation. We’ve settled with the latter approach, since map objects live in both the map and read-only spaces, and implementing mixed alignments in the read-only space can be tricky as we saw during our alignment investigation.

So when prototyping we’ve used the bounded allocator to make sure all maps are allocated within a 16MB space. We picked this size since in our benchmarks we never saw the map space go over 12MB, although if we need to implement this for real we might need to allow a bigger space.

Tag-preserving compression and decompression

TODO :-)

An even more probabilistic approach

Ideally, we would like to check all JS objects on the heap but we’re worried the potential memory and runtime overhead may be too high. Since the memory tagging approach is already probabilistic, we could trade some of the overhead for a lower probability of detecting exploits. If this can be deployed over a very high number of users, then a lower probability isn’t so bad.

So instead of using memory tagging for all JS objects, we could do it only for a fraction of allocations chosen at random^[az].

This idea was in fact inspired by the GWP-Asan allocator used in Chromium, later adopted by Firefox as PHC for “Probabilistic Heap Checker”.

With this proposal, we would have a mix of “checked” and “unchecked” objects. All unchecked objects will have their top-byte set to the same tag. It could be zero for example, or even chosen at random. Checked objects will have their top-byte set to one of the remaining tags.

We’ll have to be very careful that:

• Which object gets checked isn’t deterministic. If the attacker can predict it then we’re ineffective.

• There is no way for a JS program to detect if an object is checked. Otherwise the attacker would just throw the object away and get a new one until it’s unchecked.

• An overflow from a checked object into an unchecked one should be detected.

For these requirements to be fulfilled, we need all of V8 to be able to cope with both checked and unchecked objects seamlessly.

Where to place checked objects

Where should checked objects live on the heap? There are multiple options to consider, the end result will probably be a mix of them.

• A fixed-size space for checked objects.

In the same way as for GWP-Asan, we could place all checked objects in a new fixed-size space on the heap. However, if it cannot grow it would be possible for an attacker to make sure the space is full before mounting an attack.

So this solution isn’t suitable for us. It was designed for use with guarded pages which reserves a lot of address space. We do not have this problem with memory tagging.

• Dedicated spaces^[ba][bb][bc] for checked objects.

We could place all checked objects in their own dedicated space. If we do this we also need dedicated spaces for large objects and maps so that’s at least 3 new spaces.

However, if we’re missing a space for young checked objects we will effectively “pre-tenure” them. If we go with a high percentage of checked objects this is likely to introduce needless stress on the GC. So we might have to also introduce new spaces for checked objects, which would of course start off much smaller than the regular new spaces.

• Mixed checked and unchecked pages.^[bd][be][bf]

We could port existing spaces to have both checked and unchecked pages. This is conceptually the same thing as having dedicated spaces but it might be better to move the logic of managing checked and unchecked regions into the spaces themselves.

If partitioning the new spaces in “checked” and “unchecked” areas isn’t practical, we could have a dedicated new space for checked objects and use page flags to describe checked pages in paged spaces.

• Mixed checked and unchecked objects.

Finally, we could decide to mix checked and unchecked objects in the same pages. Since MTE is to be configured per call to mmap we’ll have to enable it for the entire JS heap. We can configure it to have the same “background tag” which all unchecked objects will have in their top byte.

We might also do this in the other cases, otherwise we might not detect overflows that cross over page boundaries.

Where can we reduce the MTE overhead?

By sampling a fraction of allocations we can:

• Only align sampled allocations to 16-bytes, reducing the memory overhead.

• Skip expensive allocation routines. We are concerned tagging objects could have a performance impact when allocation is made cheap by just bumping a pointer from generated code. Whereas the general case shouldn’t be a problem. We’ll have to make sure that the runtime check to choose the allocation routine isn’t more expensive than the tagging overhead.

• Reduce the overhead of checking memory accesses in hardware. At this time we don’t know what this overhead would be as it depends on the implementation. We expect it to be minimal in “imprecise” mode.

But we cannot:

• Change the impact of more complex pointer compression routines. Everywhere an object is handled, we need to be able to pass checked and unchecked objects seamlessly.

We expect the main advantage would be to reduce memory consumption from alignment.

Conclusion and next steps

We would appreciate some feedback on this approach to make sure that we’re not going in the wrong direction when prototyping this. We want to know if the long term goal of running a JS address sanitizer in production is something that can even be considered, even if at this time we don’t know exactly what the overhead would be^[bg][bh].

Our plan is to start prototyping and do some measurements. And we’ll update this document with those findings, or create additional documents.

Our prototyping work needs to answer a few questions:

• What would be the overhead of aligning all objects to 16 bytes?^{[bi][bj][bk][bl]} If it’s too high, what would be the percentage of objects that would need to be checked to reduce the overhead to an acceptable level?

We prototyped V8 so it would align every allocation on the JS heap to 16 bytes and gathered some results. With benchmarks such as ARES6, web-tooling and octane we see an overall impact of 2 to 5% when using full pointers, and 5 to 10% with compressed pointers. As can be expected the impact with compressed pointers is larger than we’d like, although we think the benchmarks that we chose give us a worse-case scenario and we should also look into running this within the browser so we can get results from Speedometer for instance.

Given these results, we believe it would be worthwhile to investigate partial object tagging to see if we can reduce the memory overhead.

• Is it possible to support HW tagged pointers in V8? And can we emulate them on x86?

• Can we store tags in compressed pointers? We need to figure out what tagging scheme has the smallest overhead.

• Can this be a runtime option? Otherwise can we ship a different binary per device? If we have to go with a compile-time option, we can also consider only supporting full pointers.

Alternatives and other ideas

Finally, as we were investigating mitigating heap attacks, other interesting ideas came up in the same area. We thought we’d mention them here as potential future work, even though we’re not planning on working on them at the moment.

• Memory tagging and JS fuzzing

The main use-case of a JS address sanitizer is to catch exploits in production, but can we also use it along with fuzzing JavaScript? We’re not convinced it would be possible to find bugs this way but we would be curious to know what V8 developers think.

• A V8 port of GWP-Asan.

It looks like GWP-Asan has been very successful at finding bugs in Chromium. We’re wondering if there are plans to port the idea to V8, for both the JS heap and the Zone allocator. The latter being an easier target to start with.

• Using memory tagging for specific fields.

Sometimes we know what part of the JS heap is an easy target for exploits. Obvious ones being lengths and base pointers in array implementations. We could use memory tagging for those fields in particular to mitigate exploiting known targets.

• Only detecting page header access.

The V8 page headers on the heap have sensitive information such as the current Isolate pointer (through the Heap pointer). The JS address sanitizer already naturally includes this case since JS objects will get a different random tag than unallocated space, which the header can be considered part of. However, it’s also something that could be done independently. It would be a lot less effective as a mitigation as it doesn’t detect building read and write primitives from a JS heap overflow, it instead just detects using such primitives to access data in the header.

The GC needs to be able to create a valid MemoryChunk pointer from any heap object pointer. So in principle, that tag is a key and only the GC should have it. We could have:

• The same tag for all page headers chosen at random when the heap is setup, and have it available in memory for the GC to use.

• A random tag for each page header. However, this means the GC will either have to read the tag using the new MTE instructions or maintain a map of tags.

We’re worried that an attacker would be able to find a way to extract the tags from the GC’s memory, or find data to corrupt elsewhere.

Finally, we’d also have to allow access to some page flags from jitted code for the write barrier, so part of the header would need a fixed tag, probably zero to avoid more expensive barrier checks.