MS Edge CTree­Pos­Gap::Partition­Pointers use-after-free (Mem­GC)

A specially crafted Javascript inside an HTML page can trigger a use-after-free bug in the CTree­Pos­Gap::Partition­Pointers function of edgehtml.dll in Microsoft Edge. This use-after-free bug is mitigated by Mem­GC by default: with Mem­GC enabled the memory is never actually freed. This mitigation is considered sufficient to make this a non-security issue as explained by Microsoft SWIAT in their blog post Triaging the exploitability of IE/Edge crashes.

Since this is not considered a security issue, I have the opportunity to share details about the issue with you before the issue has been fixed. And since Microsoft are unlikely to provide a fix for this issue on short notice, you should be able to reproduce this issue for some time after publication of this post. I will try to explain how I analyzed this issue using Bug­Id and Edge­Dbg, so that you can reproduce what I did and see for yourself.

Known affected software, attack vectors and mitigations

• Microsoft Edge 11.0.10240.16384-16724 (earlier versions may also be affected)

  An attacker would need to get a target user to open a specially crafted web page. Disabling Javascript should prevent an attacker from triggering the vulnerable code path.

Repro

The following html can be used to reproduce this issue:

<script>
  onload = function() {
    x.append­Child(h)
    x.offset­Top;
    x.insert­Before(h,h);
  };
</script>
<br id=h>
<select id=x>
x

I've attached the repro file at the end of this post for you to download as well.

Prerequisites

I normally start a simple web server listening on port 28876 on the local computer that serves the repro. That way I can load it by opening the URL http://%COMPUTERNAME%:28876 in my browser. The rest of this article assumes you have done the same.

I will be using two tools that I created myself: Bug­Id to automatically analyze crashes and Edge­Dbg to start Microsoft Edge on demand and have it open the URL that serves the repro.

In order to reliably reproduce use-after-free issues, you will need to enable Page Heap for Microsoft Edge using gflags.exe. I won't explain the details of page heap and gflags.exe here - there are plenty of pages that do so already available on the internet. Instead, let's use the Page­Heap.cmd script provided with Bug­Id to enable page heap with the right settings required for running Bug­Id reliably. The first argument to Page­Heap.cmd is the file name of the binary that you want to enable Page Heap for. The second argument is either "ON" or "OFF". Page­Heap.cmd must be run as an administrator because it will run gflags.exe which requires administrative privileges to work. To enable Page Heap in all of Microsoft Edge, there are four binaries that you will want to enable Page Heap for. The following four commands, run in an administrator command prompt, will do this:

Page­Heap.cmd Microsoft­Edge.exe ON
Page­Heap.cmd Microsoft­Edge­CP.exe ON
Page­Heap.cmd browser_­broker.exe ON
Page­Heap.cmd Runtime­Broker.exe ON

Once you have enabled Page Heap, we're ready to run Microsoft Edge using Bug­Id.

Detection and analysis using Bug­Id

Let's start with Mem­GC still enabled to see if the issue is indeed mitigated by Mem­GC. You can use the Edge­Bug­Id.cmd script that comes with Edge­Dbg to run Edge in Bug­Id. The first argument to Edge­Bug­Id.cmd is the URL that Edge should load once started. This conveniently defaults to http://%COMPUTERNAME%:28876, so you only need to run the following command to start Edge in Bug­Id and load the repro:

Edge­Bug­Id.cmd

Once Edge has started and loaded the repro, Bug­Id will detect an access violation exception and analyze it. After analysis it will output information about the crash and save a HTML report in the current working directory. I've attached the Bug­Id report for this crash below.

The most important information that Bug­Id reports is shown in the summary above. It consists of:

• Id: AVR:NULL 484.a53

  This is a unique identification code for this crash. Every time you run this (or any other repro that hits the same bug), Bug­Id should give you the same value - even in a different build of the same application on a different platform. This code consists of two parts separated by a space:

  • AVR:NULL

    The first part describes the type of crash (Access Violation while Reading memory using a NULL pointer).

  • 484.a53

    The second part describes the location in the code where the crash happened. It consists of the first three hexadecimal digits of the MD5 hashes of the two most relevant functions on the stack, separated by a dot. In this case, the hash for CTree­Pos­Gap::Partition­Pointers is 484 and the hash for CSplice­Tree­Engine::Init is a53. A high-tech algorithm based on dark magic determines which functions in the stack are the most relevant for a bug, but in this case they are simply the top two functions.

• Description: Access violation while reading memory at 0x0 using a NULL ptr

  This describes the type of crash Bug­Id detected in an easier-to-read format than AVR:NULL. It also provides the exact address. This is useful because the Id value will not contain the exact address: if, for instance, the access violation would have been an attempt to read memory at address 0x30, the Bug­Id would have been AVR:NULL+4*N 484.a53. This indicates that the address was a NULL pointer + an offset that is a multiple of 4. Bug­Id does not use the exact offset in the Id because that value may change between builds and can depend on the platform (x86 vs x64) the application was build for. But the alignment of an offset is almost always the same - even for different builds on 32- or 64-bit platforms. Using the alignment rather than the offset allows Bug­Id to give you the same Id value for a crash in two different builds for two different platforms.

• Location: microsoftedgecp.exe!edgehtml.dll!CTree­Pos­Gap::Partition­Pointers

  This consists of two or three parts, separated by a "!": the binary for the process in which the crash was detected (in this case microsoftedgecp.exe), the module in or address at which the crash happened (edgehtml.dll) and (if the crash happened in a module) the function symbol or code offset at which the crash happened (CTree­Pos­Gap::Partition­Pointers).

• Security impact: None

  This indicates that Bug­Id doubts this is a security issue, which in this case is correct. Obviously, this is a guess: if Bug­Id says that something is exploitable, it may not be practically exploitable and if Bug­Id says that a crash has no security impact, the underlying issue may still be a security issue, it's just not obvious from the crash Bug­Id analyzed.

Let's turn Mem­GC off and try again. You can do this by modifying the registry, but I prefer using the Mem­GC.cmd script that I recently added to Bug­Id. The only argument to Mem­GC.cmd is "ON" or "OFF", but it must be run as an administrator in order to change the registry. Simply run the following command in an administrator command prompt to disable Mem­GC:

Mem­GC.cmd OFF

Now let's run Edge in Bug­Id again using the same Edge­Bug­Id.cmd command as before. Bug­Id will again detect an access violation exception and analyze it. After analysis it will output slightly different information. Here's the new Bug­Id report for this crash:

The most relevant changes from the previous report are the following:

• Id: AVR:Free 484.a53

  The part that describes the type of crash (AVR:Free) has changed to indicate the access violation happened while attempting to read from memory that was previously Freed. The part containing the stack hashes has not changed, so the crash is in the same code area.

• Description: Access violation while reading freed memory at 0x­E8990B3F50

  The description changed to explain this is no longer a NULL pointer, but a use-after-free bug.

• Security impact: Potentially exploitable security issue

  Bug­Id believes this issue is a security issue (which it would be if not for Mem­GC).

If you look at the HTML report created by Bug­Id for this second crash, you will notice that it has an extra section titled Page heap. In this section you can find information reported by Page Heap about the memory at the location where the exception happened. It shows that the memory was freed and provides the call stack at the time it was freed. Here's part of that information:

Page heap report for address 0x­E8990B3F50:
    address 000000e8990b3f50 found in
    _DPH_­HEAP_­ROOT @ e899001000
    in free-ed allocation (  DPH_­HEAP_­BLOCK:         Virt­Addr         Virt­Size)
                                 e899002208:       e8990b3000             2000
    00007ffa23bacc13 ntdll!Rtl­Debug­Free­Heap+0x0000000000000047
    00007ffa23b653d9 ntdll!Rtlp­Free­Heap+0x0000000000079519
    00007ffa23aeaa16 ntdll!Rtl­Free­Heap+0x0000000000000106
    00007ffa1089366c EDGEHTML!Memory­Protection::Heap­Free+0x00000000003736dc
    00007ffa105e5807 EDGEHTML!CTree­Node::Node­Release+0x0000000000000057
    00007ffa10ec66d6 EDGEHTML!Tree::Tree­Writer::Unwrap­Internal+0x000000000000002e
    00007ffa1064939f EDGEHTML!Tree::Tree­Writer::Unwrap+0x0000000000000133
    00007ffa105e38ea EDGEHTML!CTree­Pos­Gap::Partition­Pointers+0x000000000000040a
    00007ffa105e320a EDGEHTML!CSplice­Tree­Engine::Init+0x000000000000017a

At the top of this stack are a few heap manager functions, which we can ignore. After these functions we can see that the order to free the memory came from CTree­Node::Node­Release. This function was called, through two other functions, by CTree­Pos­Gap::Partition­Pointers. This later function happens to be the same function in which the re-used happened. If you compare the stack at the time of the access violation to the stack at the time of the free, you may notice that CTree­Pos­Gap::Partition­Pointers is called by CSplice­Tree­Engine::Init in both cases, but that the offsets from which these two calls are made in CSplice­Tree­Engine::Init differ. The rest of the stack is exactly the same. This appears to indicate that there is one call to CSplice­Tree­Engine::Init, in which there are (at least) two calls to CTree­Pos­Gap::Partition­Pointers. One of these two calls results in freeing some memory and a subsequent call results in re-use of that freed memory.

Note that I am speculation at this point: it may also be that a function higher up the stack is running a loop and that there were two calls made from the same offset in the code, making it look the same. So we ned to check if our assumption is true. At the same time, we can should try to find more information on the memory being freed. Bug­Id is useful for automated detection and analysis of crashes, but it cannot provide much information about what happened before the crash that may have caused it or contributed to it. To gather this information, we'll have to debug Edge manually.

Analyzing the use-after-free using a debugger.

You can start Edge and attach a debugger using Edge­Dbg. I will be using Win­Dbg as my debugger and the Edge­Win­Dbg.cmd script that comes with Edge­Dbg in order to start Edge and attach Win­Dbg. The first argument to Edge­Win­Dbg.cmd is the URL that Edge should load once started. Again, this conveniently defaults to http://%COMPUTERNAME%:28876. Simply run the following command to start Edge and load the repro:

Edge­Win­Dbg.cmd

In order to be able to see what happens before the crash and find out how big the block of memory was that was freed, we'll could set a breakpoint at some point in the code that is executed before the memory is freed, and then step through the code to the point where CTree­Node::Node­Release is called. We could set such a breakpoint at the moment Edge is started, but whatever function we set the breakpoint in may be called numerous times before the call that we're interested in. It may be difficult to determine which of these calls is the one in which the free happens and cumbersome (not to mention error prone) to manually check them. To set a breakpoint on a function at the last possible moment before the memory is freed, we can put an alert() in the script right before the part of the script that causes it.

As we learned from the stack in the Bug­Id report, CSplice­Tree­Engine::Init is a good location to start our analysis, because both the free and re-use happen in functions called by it. The stack also indicates that this happens during execution of the function Tree::Tree­Writer::Insert­Before, so it's a pretty safe bet that we can put the alert right before the line x.insert­Before(h,h); in our repro, like so:

    <script>
      onload = function() {
        x.append­Child(h)
        x.offset­Top;
        alert();
        x.insert­Before(h,h);
      };
    </script>
    <br id=h>
    <select id=x>
    x

When you've started Edge in Win­Dbg and see the popup, please break into the debugger, select the process that is running the microsoftedgecp.exe binary, and execute the following command to set a breakpoint at CSplice­Tree­Engine::Init:

1:050> |
#  0    id: 56c    attach    name: C:\Windows\System­Apps\Microsoft.Microsoft­Edge_8wekyb3d8bbwe\Microsoft­Edge.exe
.  1    id: 1364    attach    name: C:\Windows\System­Apps\Microsoft.Microsoft­Edge_8wekyb3d8bbwe\microsoftedgecp.exe
   2    id: 1030    attach    name: C:\Windows\system32\browser_­broker.exe
   3    id: f2c    attach    name: C:\Windows\System32\Runtime­Broker.exe
1:050> |1s
ntdll!Nt­Wait­For­Work­Via­Worker­Factory+0xa:
1:050> bp EDGEHTML!CSplice­Tree­Engine::Init
1:050> g

Note that I am using .prompt_­allow -dis to suppress the disassembly normally shown before the prompt, as I feel this makes for a much cleaner output. Also note that Win­Dbg always attaches to these four processes in the same order, so you can always use |1s to switch to the microsoftedgecp.exe process.

After this you can resume Edge in the debugger and dismiss the alert() in Edge. The debugger should report that the breakpoint was hit almost immediately. If you look at the stack, you will notice that CSplice­Tree­Engine::Init is executed during Tree::Tree­Writer::Insert­Before.

1:050> g
Breakpoint 0 hit
EDGEHTML!CSplice­Tree­Engine::Init:
1:050> kc 5
Call Site
EDGEHTML!CSplice­Tree­Engine::Init
EDGEHTML!Tree::Tree­Writer::Splice­Tree­Internal
EDGEHTML!Tree::Tree­Writer::Cut­Copy­Move­Legacy
EDGEHTML!Tree::Tree­Writer::Move­Node­Legacy
EDGEHTML!Tree::Tree­Writer::Insert­Before
1:050>

If you resume Edge, you will hit the access violation.

1:050> g
(2d8.974): Access violation - code c0000005 (first chance)
First chance exceptions are reported before any exception handling.
This exception may be expected and handled.
EDGEHTML!CTree­Pos­Gap::Partition­Pointers+0x68:

This proves that we've set the breakpoint before the re-use of freed memory, but we still need to find out if we've set it before the free as well.

Finding the exact point where the memory is freed

We know from the Bug­Id analysis that the memory will be freed during a call to CTree­Node::Node­Release. Let's see how many calls there are from this point until the access violation. If there is only one, that call should be the one that frees the memory. So, let's restart Edge, and put the breakpoint on CSplice­Tree­Engine::Init like before and run Edge until we hit this breakpoint. We can then set a breakpoint on CTree­Node::Node­Release to detect each call:

1:050> g
Breakpoint 0 hit
EDGEHTML!CSplice­Tree­Engine::Init:
1:050> bp EDGEHTML!CTree­Node::Node­Release
1:050> g
Breakpoint 1 hit
EDGEHTML!CTree­Node::Node­Release:
1:050> g
(fa8.e48): Access violation - code c0000005 (first chance)
First chance exceptions are reported before any exception handling.
This exception may be expected and handled.
EDGEHTML!CTree­Pos­Gap::Partition­Pointers+0x68:
1:050>

So there is only one call to CTree­Node::Node­Release, which makes it easy for us to check if that call is the one that frees the memory.

Let's restart Edge again and run right up to the CTree­Node::Node­Release breakpoint. A convenient way to do this is to execute this command in Win­Dbg once you've broken into the debugger during the alert():

|1s; bp EDGEHTML!CSplice­Tree­Engine::Init "bp EDGEHTML!CTree­Node::Node­Release; g"; g

It does everything we've done previously in one go; after you have execute the command, Edge will be running again so you can dismiss the alert() and hit the breakpoint in CTree­Node::Node­Release.

To find out if any memory is freed during this call, and whether it is the same memory that will be re-used, we will want to put a breakpoint on ntdll!Rtl­Free­Heap. However, you may find that it gets called a lot from other threads as well, which is terribly confusing. Luckily, you can avoid this problem by setting the breakpoint on ntdll!Rtl­Free­Heap only for the current thread before resuming Edge:

Breakpoint 1 hit
EDGEHTML!CTree­Node::Node­Release:
1:050> ~. bp ntdll!Rtl­Free­Heap
1:050> g
Breakpoint 2 hit
ntdll!Rtl­Free­Heap:
1:050>

The documentation for Rtl­Free­Heap informs us that it takes three arguments, the third of which contains a pointer to the memory to be freed. As I am debugging an x64 version of Edge and the x64 calling convention says the third argument is passed using the r8 register, we can ask Page Heap for information about the memory being freed:

1:050> !heap -p -a @r8
    address 00000010810bdf10 found in
    _DPH_­HEAP_­ROOT @ 1081001000
    in busy allocation (  DPH_­HEAP_­BLOCK:         User­Addr         User­Size -         Virt­Addr         Virt­Size)
                              1081002000:       10810bdf10               e8 -       10810bd000             2000
    00007ffa23bac1fb ntdll!Rtl­Debug­Allocate­Heap+0x0000000000000047
    00007ffa23b66582 ntdll!Rtlp­Allocate­Heap+0x0000000000075a22
    00007ffa23aeef52 ntdll!Rtlp­Allocate­Heap­Internal+0x0000000000000292
    00007ffa1094f98e EDGEHTML!Memory­Protection::Heap­Alloc­Clear<1>+0x000000000032fa7e
    00007ffa1061feca EDGEHTML!_Mem­Isolated­Alloc­Clear<1>+0x000000000000001a
    00007ffa1064aa82 EDGEHTML!Tree::Tree­Writer::Create­Element­Node+0x000000000000002a
***snipped*for*brevity***
    00007ffa10691856 EDGEHTML!CElement::get_­offset­Top+0x0000000000000056
    00007ffa10691e45 EDGEHTML!CFast­DOM::CHTMLElement::Trampoline_­Get_­offset­Top+0x0000000000000065
***snipped*for*brevity***
1:050>

This tells us that the memory about to be freed is a block of 0xe8 bytes that was allocated during a call to the Tree::Tree­Writer::Create­Element­Node function, which happened during a call to CElement::get_­offset­Top. We can safely assume this corresponds to x.offset­Top; in the repro. You can check if this is true in the same way we're checking where the free happens, but I'll leave that as an exercises to the reader.

Let's resume Edge so we hit the access violation and find out if this memory being freed is the memory being re-used. But we should clear the breakpoint on ntdll!Rtl­Free­Heap first, as it gets called a lot and we're not interested in any more calls.

1:050> bc 2
1:050> g
(c60.e60): Access violation - code c0000005 (first chance)
First chance exceptions are reported before any exception handling.
This exception may be expected and handled.
EDGEHTML!CTree­Pos­Gap::Partition­Pointers+0x68:
1:050> .exr -1
Exception­Address: 00007ffa105e3548 (EDGEHTML!CTree­Pos­Gap::Partition­Pointers+0x0000000000000068)
   Exception­Code: c0000005 (Access violation)
  Exception­Flags: 00000000
Number­Parameters: 2
   Parameter[0]: 0000000000000000
   Parameter[1]: 00000010810bdf50
Attempt to read from address 00000010810bdf50
1:050>

The address 0x10810bdf50 falls inside the 0xe8 byte memory block at address 0x10810bdf10 we saw getting freed earlier. This proves that the call to CTree­Node::Node­Release we put a breakpoint on is the one that frees the memory that gets re-used later.

Conclusion

We now know the following about this issue:

• A block of 0xe8 bytes of memory gets allocated when Edge attempts to determine the value of x.offset­Top.
• This block is freed and reused when Edge executes x.insert­Before(h,h).
• Since the free and the (first) re-use happen during execution of one Javascript method, there does not appear to be an obvious way to reallocate the freed memory and fill it with data of our choosing before the re-use.

The fact that we cannot execute any Javascript between the free and reuse makes this very hard, if not impossible to exploit in practise. This is why I've not attempted to do so here. But in case you want to take a shot at it, here are some things you could try:

• DOM events can allow you to execute Javascript while a DOM method is being executed. However, when I tested this in this case, the event handlers were fired after the re-use.
• There may be ways to reallocate the freed memory from another thread, but I am not aware of a practical way to do this at this point.
• It may be that the memory can be re-used again later, which would allow Javascript to be executed in the mean time. To find out, you would have to reverse engineer the code to determine if the pointer to the freed memory is discarded or not and how one might get the code to reuse it later.

If you decide to try and exploit this issue, do let me know how far you get!