Vulnerability: Out-of-bounds read/write and invalid free with `externref`s and GC safepoints in Wasmtime  ### Impact

There was an invalid free and out-of-bounds read and write bug when running Wasm that uses `externref`s in Wasmtime.

To trigger this bug, Wasmtime needs to be running Wasm that uses `externref`s, the host creates non-null `externrefs`, Wasmtime performs a garbage collection (GC), and there has to be a Wasm frame on the stack that is at a GC safepoint where

* there are no live references at this safepoint, and
* there is a safepoint with live references earlier in this frame's function.

Under this scenario, Wasmtime would incorrectly use the GC stack map for the safepoint from earlier in the function instead of the empty safepoint. This would result in Wasmtime treating arbitrary stack slots as `externref`s that needed to be rooted for GC. At the *next* GC, it would be determined that nothing was referencing these bogus `externref`s (because nothing could ever reference them, because they are not really `externref`s) and then Wasmtime would deallocate them and run `<ExternRef as Drop>::drop` on them. This results in a free of memory that is not necessarily on the heap (and shouldn't be freed at this moment even if it was), as well as potential out-of-bounds reads and writes.

Even though support for `externref`s (via the reference types proposal) is enabled by default, unless you are creating non-null `externref`s in your host code or explicitly triggering GCs, you cannot be affected by this bug.

We have reason to believe that the effective impact of this bug is relatively small because usage of `externref` is currently quite rare.

### Patches

This bug has been patched and users should upgrade to Wasmtime version 0.30.0.

Additionally, we have updated [our primary `externref` fuzz target](https://github.com/bytecodealliance/wasmtime/blob/37c094faf53f1b356aab3c79d451395e4f7edb34/fuzz/fuzz_targets/table_ops.rs) such that it better exercises these code paths and we can have greater confidence in their correctness going forward.

### Workarounds

If you cannot upgrade Wasmtime at this time, you can avoid this bug by disabling the reference types proposal by passing `false` to [`wasmtime::Config::wasm_reference_types`](https://docs.rs/wasmtime/0.29.0/wasmtime/struct.Config.html#method.wasm_reference_types)

### References

* [The Wasm reference types proposal, which introduces `externref`](https://github.com/WebAssembly/reference-types/)

### For more information

If you have any questions or comments about this advisory:

* Reach out to us on [the Bytecode Alliance Zulip chat](https://bytecodealliance.zulipchat.com/#narrow/stream/217126-wasmtime)
* Open an issue in [the `bytecodealliance/wasmtime` repository](https://github.com/bytecodealliance/wasmtime/)
Vulnerability ID: GHSA-4873-36h9-wv49
CWE: CWE-787
Severity score: 6.3
Project: https://github.com/bytecodealliance/wasmtime
Published: 2021-09-20
File: crates/wasmtime/src/module/registry.rs
Commit message: Merge pull request from GHSA-4873-36h9-wv49

Stop doing fuzzy search for stack maps
Commit author: Nick Fitzgerald

Vulnerable version (before fix):
 impl ModuleInfo for RegisteredModule {         let info = self.module.func_info(index);          // Do a binary search to find the stack map for the given offset.         //         // Because GC safepoints are technically only associated with a single         // PC, we should ideally only care about `Ok(index)` values returned         // from the binary search. However, safepoints are inserted right before         // calls, and there are two things that can disturb the PC/offset         // associated with the safepoint versus the PC we actually use to query         // for the stack map:         //         // 1. The `backtrace` crate gives us the PC in a frame that will be         //    *returned to*, and where execution will continue from, rather than         //    the PC of the call we are currently at. So we would need to         //    disassemble one instruction backwards to query the actual PC for         //    the stack map.         //         //    TODO: One thing we *could* do to make this a little less error         //    prone, would be to assert/check that the nearest GC safepoint         //    found is within `max_encoded_size(any kind of call instruction)`         //    our queried PC for the target architecture.         //         // 2. Cranelift's stack maps only handle the stack, not         //    registers. However, some references that are arguments to a call         //    may need to be in registers. In these cases, what Cranelift will         //    do is:         //         //      a. spill all the live references,         //      b. insert a GC safepoint for those references,         //      c. reload the references into registers, and finally         //      d. make the call.         //         //    Step (c) adds drift between the GC safepoint and the location of         //    the call, which is where we actually walk the stack frame and         //    collect its live references.         //         //    Luckily, the spill stack slots for the live references are still         //    up to date, so we can still find all the on-stack roots.         //    Furthermore, we do not have a moving GC, so we don't need to worry         //    whether the following code will reuse the references in registers         //    (which would not have been updated to point to the moved objects)         //    or reload from the stack slots (which would have been updated to         //    point to the moved objects).          let index = match info             .stack_maps             .binary_search_by_key(&func_offset, |i| i.code_offset)         {             // Exact hit.             Ok(i) => i,              // `Err(0)` means that the associated stack map would have been the             // first element in the array if this pc had an associated stack             // map, but this pc does not have an associated stack map. This can             // only happen inside a Wasm frame if there are no live refs at this             // pc.             Err(0) => return None,              Err(i) => i - 1,         }; 

Fixed version (after fix):
 impl ModuleInfo for RegisteredModule {         let info = self.module.func_info(index);          // Do a binary search to find the stack map for the given offset.         let index = match info             .stack_maps             .binary_search_by_key(&func_offset, |i| i.code_offset)         {             // Found it.             Ok(i) => i,              // No stack map associated with this PC.             //             // Because we know we are in Wasm code, and we must be at some kind             // of call/safepoint, then the Cranelift backend must have avoided             // emitting a stack map for this location because no refs were live.             #[cfg(not(feature = "old-x86-backend"))]             Err(_) => return None,              // ### Old x86_64 backend specific code.             //             // Because GC safepoints are technically only associated with a             // single PC, we should ideally only care about `Ok(index)` values             // returned from the binary search. However, safepoints are inserted             // right before calls, and there are two things that can disturb the             // PC/offset associated with the safepoint versus the PC we actually             // use to query for the stack map:             //             // 1. The `backtrace` crate gives us the PC in a frame that will be             //    *returned to*, and where execution will continue from, rather than             //    the PC of the call we are currently at. So we would need to             //    disassemble one instruction backwards to query the actual PC for             //    the stack map.             //             //    TODO: One thing we *could* do to make this a little less error             //    prone, would be to assert/check that the nearest GC safepoint             //    found is within `max_encoded_size(any kind of call instruction)`             //    our queried PC for the target architecture.             //             // 2. Cranelift's stack maps only handle the stack, not             //    registers. However, some references that are arguments to a call             //    may need to be in registers. In these cases, what Cranelift will             //    do is:             //             //      a. spill all the live references,             //      b. insert a GC safepoint for those references,             //      c. reload the references into registers, and finally             //      d. make the call.             //             //    Step (c) adds drift between the GC safepoint and the location of             //    the call, which is where we actually walk the stack frame and             //    collect its live references.             //             //    Luckily, the spill stack slots for the live references are still             //    up to date, so we can still find all the on-stack roots.             //    Furthermore, we do not have a moving GC, so we don't need to worry             //    whether the following code will reuse the references in registers             //    (which would not have been updated to point to the moved objects)             //    or reload from the stack slots (which would have been updated to             //    point to the moved objects).             #[cfg(feature = "old-x86-backend")]             Err(0) => return None,             #[cfg(feature = "old-x86-backend")]             Err(i) => i - 1,         }; 

Patch:
patch: @@ -122,61 +122,65 @@ impl ModuleInfo for RegisteredModule {
         let info = self.module.func_info(index);
 
         // Do a binary search to find the stack map for the given offset.
-        //
-        // Because GC safepoints are technically only associated with a single
-        // PC, we should ideally only care about `Ok(index)` values returned
-        // from the binary search. However, safepoints are inserted right before
-        // calls, and there are two things that can disturb the PC/offset
-        // associated with the safepoint versus the PC we actually use to query
-        // for the stack map:
-        //
-        // 1. The `backtrace` crate gives us the PC in a frame that will be
-        //    *returned to*, and where execution will continue from, rather than
-        //    the PC of the call we are currently at. So we would need to
-        //    disassemble one instruction backwards to query the actual PC for
-        //    the stack map.
-        //
-        //    TODO: One thing we *could* do to make this a little less error
-        //    prone, would be to assert/check that the nearest GC safepoint
-        //    found is within `max_encoded_size(any kind of call instruction)`
-        //    our queried PC for the target architecture.
-        //
-        // 2. Cranelift's stack maps only handle the stack, not
-        //    registers. However, some references that are arguments to a call
-        //    may need to be in registers. In these cases, what Cranelift will
-        //    do is:
-        //
-        //      a. spill all the live references,
-        //      b. insert a GC safepoint for those references,
-        //      c. reload the references into registers, and finally
-        //      d. make the call.
-        //
-        //    Step (c) adds drift between the GC safepoint and the location of
-        //    the call, which is where we actually walk the stack frame and
-        //    collect its live references.
-        //
-        //    Luckily, the spill stack slots for the live references are still
-        //    up to date, so we can still find all the on-stack roots.
-        //    Furthermore, we do not have a moving GC, so we don't need to worry
-        //    whether the following code will reuse the references in registers
-        //    (which would not have been updated to point to the moved objects)
-        //    or reload from the stack slots (which would have been updated to
-        //    point to the moved objects).
-
         let index = match info
             .stack_maps
             .binary_search_by_key(&func_offset, |i| i.code_offset)
         {
-            // Exact hit.
+            // Found it.
             Ok(i) => i,
 
-            // `Err(0)` means that the associated stack map would have been the
-            // first element in the array if this pc had an associated stack
-            // map, but this pc does not have an associated stack map. This can
-            // only happen inside a Wasm frame if there are no live refs at this
-            // pc.
+            // No stack map associated with this PC.
+            //
+            // Because we know we are in Wasm code, and we must be at some kind
+            // of call/safepoint, then the Cranelift backend must have avoided
+            // emitting a stack map for this location because no refs were live.
+            #[cfg(not(feature = "old-x86-backend"))]
+            Err(_) => return None,
+
+            // ### Old x86_64 backend specific code.
+            //
+            // Because GC safepoints are technically only associated with a
+            // single PC, we should ideally only care about `Ok(index)` values
+            // returned from the binary search. However, safepoints are inserted
+            // right before calls, and there are two things that can disturb the
+            // PC/offset associated with the safepoint versus the PC we actually
+            // use to query for the stack map:
+            //
+            // 1. The `backtrace` crate gives us the PC in a frame that will be
+            //    *returned to*, and where execution will continue from, rather than
+            //    the PC of the call we are currently at. So we would need to
+            //    disassemble one instruction backwards to query the actual PC for
+            //    the stack map.
+            //
+            //    TODO: One thing we *could* do to make this a little less error
+            //    prone, would be to assert/check that the nearest GC safepoint
+            //    found is within `max_encoded_size(any kind of call instruction)`
+            //    our queried PC for the target architecture.
+            //
+            // 2. Cranelift's stack maps only handle the stack, not
+            //    registers. However, some references that are arguments to a call
+            //    may need to be in registers. In these cases, what Cranelift will
+            //    do is:
+            //
+            //      a. spill all the live references,
+            //      b. insert a GC safepoint for those references,
+            //      c. reload the references into registers, and finally
+            //      d. make the call.
+            //
+            //    Step (c) adds drift between the GC safepoint and the location of
+            //    the call, which is where we actually walk the stack frame and
+            //    collect its live references.
+            //
+            //    Luckily, the spill stack slots for the live references are still
+            //    up to date, so we can still find all the on-stack roots.
+            //    Furthermore, we do not have a moving GC, so we don't need to worry
+            //    whether the following code will reuse the references in registers
+            //    (which would not have been updated to point to the moved objects)
+            //    or reload from the stack slots (which would have been updated to
+            //    point to the moved objects).
+            #[cfg(feature = "old-x86-backend")]
             Err(0) => return None,
-
+            #[cfg(feature = "old-x86-backend")]
             Err(i) => i - 1,
         };
path: crates/wasmtime/src/module/registry.rs