Prevent over-deep type hierarchies in wasm-smith #2143
Conversation
Currently wasm-smith can produce invalid GC modules because there's no limit placed on subtyping depth. This commit keeps track of subtyping depth and appropriately manages the `can_subtype` list as a result.
|
I don't know why it took fuzzing in Wasmtime to find this. |
|
Well I'm flummoxed. This is fixing a preexisting bug which by all means should have been discovered by fuzzing of just this repo, fuzzing in Wasmtime shouldn't be necessary. Ever since #1793, landed 6 months ago, this should have been discoverable by the validate-valid-module fuzzer. I double-checked all configuration options Wasmtime is using/setting are at least possible to configure from this fuzzer. Given that I guess it just requires a relatively specific shape of fuzz input and that didn't crop up until later... |
There was a problem hiding this comment.
Rather than calculating this on-demand, and potentially repeating the traversal up the parent chain which could lead to quadratic behavior or worse, I think we want to have a side table and compute the subtyping depth for each type as we generate each type.
More concretely, I'm thinking we want to have a side table similar to super_to_sub_types that maps from a type to its subtyping depth, and we eagerly insert an entry in this table when generating a type. This way, we only ever have to add one to the super type's depth, rather than calculate the whole depth and traverse the whole hierarchy every time.
Huh. I don't have a good answer for this mystery either, other than we just got "lucky" in Wasmtime, or maybe it was somehow rewarding the fuzzer with additional coverage for deeper subtyping in a way that just the parser and validator was not. |
|
Given the maximum recursion depth here is fixed I figured there was no need for quadratic bits, but sure it's not too bad to do that too. |
Currently wasm-smith can produce invalid GC modules because there's no limit placed on subtyping depth. This commit keeps track of subtyping depth and appropriately manages the
can_subtypelist as a result.