WebAssembly
Newtypes for stronger control flow integrity
A newtype is a (mostly) zero-cost wrapper for an existing type. When it comes to the type stack, a newtype and its underlying type are indistinguishable. When it comes to certain interactions, they are very much distinguishable. In particular:
- On a call_indirect, newtypes of the expected function (as per type of the call_indirect) and of the passed function (as per type in function table) must match.
- Imports must also match newtypes.
So for example, a string-ptr newtype (i32) is just an i32 and can be manipulated and used like an i32, but a function that takes a string-ptr and a function that takes an i32 are not compatible.
Thoughts?
important notes:
- elems don't have types (elem segments do but they're not useful), only table entries do, so we need the newtypes on the imports
- ~~(tentatively) you can allegedly compare arbitrary function pointers in C if you first cast them to the same function type (this rules out using multiple tables)~~ (it is tricky to interpret the C standard with regards to this but it may well be UB, however see next point)
- cast pointers between tables of the same underlying type (e.g. i32 vs string) are valid but behave incorrectly, while cast pointers between newtypes are invalid and guaranteed to trap. (this is a point in favor of newtypes over using multiple tables)
You are proposing a form of abstract data type, which generally is a valuable feature for general-purpose programming languages. However, in the context of Wasm, it raises a few questions:
-
What is their use case in Wasm? What is the threat model? That is, what is it supposed to protect and against whom? Wasm's type system isn't intended to provide any sort of protection for client code against itself (which would only be possible at extreme complexity cost in a machine-like language), its function solely is to protect the integrity of the engine. Protection within a single client language is the producer's problem. Protection between multiple runtimes otoh is delegated to higher layers like the component system. Hence, such a feature would only seem relevant to enable passing references across runtimes, e.g., as a representation of resource types in the component system.
-
How are values of this type created and accessed? Are there explicit conversion instructions? Are you proposing to add implicit conversions to Wasm?
-
In a language with casts, having the same representation for an abstract type and its underlying type is not viable, because the cast operation needs to be able to distinguish them. If it wasn't, type abstraction could not provide actual protection and would be pointless, at least for a language with Wasm's design goals.
FWIW, there is a brief discussion of private types and accompanying design constraints in the type imports proposal. It sketches a concrete design for such a mechanism, but is not "zero-cost" for the reasons mentioned.
- indeed the point is to enable control flow integrity in e.g. C.
wasm has limited support for control flow integrity, for example both a void f(int); and void g(char *) have the same wasm type (param i32). it is possible for a guest language to do extra runtime checks for control flow integrity, but we don't think any guest languages support that today, and it would be very costly (requiring extra runtime checks). on the other hand, this newtype proposal doesn't introduce new stack types, but merely makes use of the way wasm engines execute instructions like call_indirect today. for example, in wasm2c, we globally allocate unique identifiers for different function types, which makes call_indirect type checking basically free. we could take advantage of the existing mechanism to provide guest language control flow integrity at no extra cost.
-
there is no need for conversions. newtypes don't exist in the value stack. instructions cannot produce or consume newtypes, and in the case of function calls, they stand in for their underlying type. newtypes are only relevant during linking and
call_indirect. -
newtypes aren't meant to provide that kind of protection. they're meant to provide a sort of "hardware-accelerated" control flow integrity, akin to similar instructions in various silicon ISAs. (but in wasm, unlike silicon, they are zero-cost.)
private types does sound similar, but we want something with less cost. rejecting subtyping and requiring exact match is very useful, as exact match can be implemented almost entirely in validation.
Re 1: Okay, I see, but it is not obvious to me that would work and benefit security in sufficient generality to be worthwhile. Not saying it isn't, but that needs highly non-trivial design and validation effort.
Re 2: Well, what is your notion of type equivalence? Either the new types are equivalent to their underlying type, then they are indistinguishable everywhere. Or they are not equivalent, but without further functionality the new types would then be uninhabited, i.e., useless. You want neither of that, so you necessarily need some form of (explicit or implicit) conversion rules in the type system that define where exactly one can be viewed as the other. For example, you probably want to allow an i32 to be passed to a function that takes a newtype over i32. But that would be an implicit type conversion, even if it doesn't change the representation.
Typically abstract types achieve that by only exposing the type equivalence local to a certain scope (e.g., the module that defines them). However, this "standard" approach would defeat your specific use case.
Not sure what the alternative is and what you mean with "newtypes are only relevant during linking and call_indirect." For example, there is nothing special about call_indirect, it's equivalent to table.get + ref.cast + call_ref, i.e., performs a regular cast. And presumably, a cast from $t to (newtype $t) would still need to succeed, while (func (ref $t)) to (func (ref (newtype $t))) would not, so the effect on dynamic casts would need to be as special as that on static types. Unclear what that would mean in terms of runtime types.
Re 3: Even if you didn't need it to hold for your purpose, allowing casts to succeed between statically incompatible types would introduce a semantic inconsistency between static and dynamic typing that seems highly undesirable.
-
yeah, we could use input from folks who know more about CFI than we do.
-
so our idea is that newtypes don't participate in subtyping and thus don't match any other types, but only for the purposes of uh, semi-static type checking? thus, a cast from $t to (newtype $t) always fails (also because newtypes can't exist on the stack), likewise a cast from (func (ref $t)) to (func (ref (newtype $t))) always fails. on the other hand, a call_ref or a call will type-check the value stack as if newtypes were their underlying type. (including subtyping requirements of the underlying type, if wasm even has implicit conversions between subtypes. we will however note that our experience with wasm is mainly limited to wabt, which still has neither GC nor typed function references support.) you could argue this is a "type check hack" but it is a very useful one. it allows us to introduce CFI without doing any actual casts or additional type checking at runtime beyond those we would already have to do without the existence of newtypes.
-
we don't believe we are allowing casts to succeed between statically incompatible types?
An object can only have one runtime type. So, not all of the following statements can be true at the same time:
- Objects of type $t and (newtype $t) have the same representation.
- Objects of static type $t can be cast to $t.
- Objects of static type (newtype $t) can be cast to (newtype $t).
- Objects of static type $t can not be cast to (newtype $t) nor vice versa.
Of these, (2) and (3) are not negotiable, since their absence would break basic properties of casts. Consequently, you have to give up either (1) or (4).
You might be mixing objects and types.
Objects of type (newtype $t) don't exist.
(but objects of type (func (param (newtype $t))) or (func (result (newtype $t))) or a combination thereof do)
(2) and (3) are non-negotiable, but we can give up both (1) and (4)
Objects that statically have type (newtype $t) certainly must exist. Otherwise the type would be unusable, e.g., you could never call a function which has that as a parameter type. That their dynamic type would then be incompatible with their static type is part of the problem I'm getting at, as that would be breaking (3).
well, we want it so we can do
(func $strlen (param $string) (result i32))
(func $malloc (param i32) (result $pointer))
and have them have incompatible types, but at the same time being able to do something akin to
i32.const 1
call $malloc
local.tee $whatever
i32.const 0
i32.store8
local.get $whatever
call $strlen
and having it work. how does this break (3)?
btw this blog post contains a pretty good overview of control flow integrity https://maskray.me/blog/2022-12-18-control-flow-integrity
I don't see the connection between CFI strategies (thanks for the link) and newtype. As for CFI, this has been viewed as being important, but not part of wasm per se -- but more part of the implementation strategy/constraints for wasm engine developers.
some of the CFI strategies are "hardware-assisted". now, wasm is technically not hardware, but we think wasm could adopt some concept of "hardware-assisted" CFI, and we think it can be done without adding additional runtime cost.
Your example has no casts, so is unrelated to (3).
Not sure how it is supposed to type-check, though, if $pointer and $string are (supposedly) different newtypes? Or how the functions themselves would be implemented and type-check internally?
Look, I can only point out likely contradictions with your suggestion. It is difficult to pinpoint them more concretely as long as the semantics you're imagining remains so vague. The second-guessing on my part doesn't appear to be successful. I encourage you to work out more details and then we can have a constructive discussion.
to channel Andreas: why? The primary security aim behind the design of wasm is to protect the engine/host from malicious code. As such, the design of wasm is already strong: the only operations that a wasm program can perform are gated by imports. This means that, so long as calls to host code are properly verified (at run time), a wasm program cannot corrupt the host. Techniques like return-oriented programming and stack smashing are not possible in wasm. Having said that, IMO, we are a long way from providing security guarantees to users of wasm programs. Some forms of buffer overrun are still possible, SQL injection is still possible etc. etc.
indeed, overflowing a buffer and corrupting/replacing function pointers is perfectly legal. CFI limits the damage such replacements can do, by restricting the function pointers you can replace.
wasm has limited CFI.
as a example, you can replace a pointer to strlen (aka (i32) -> i32) with a pointer to malloc (also (i32) -> i32), or vice-versa, and the call_indirect will still work.
the proposed newtypes would make such replacement trap at runtime, using the same mechanism that traps today if you replace a pointer to malloc with one for fwrite (aka (i32, i32, i32, i32) -> i32).
we want to take advantage of the trap mechanism of incompatible types without introducing real runtime types with real representations. newtypes are fake types that only exist during validation and when comparing function signatures, but don't exist during type checking and subtyping. (you also can't have object-of-newtype but you can have object-of-function-that-takes-newtype)
Differentiating between (func $malloc_t (param i32) (result i32)) and (func $strlen_t (param i32) (result i32)) and having call_indirect of the wrong one trap is actually already possible today:
(rec
(func $malloc_t (param i32) (result i32))
(func $strlen_t (param i32) (result i32))
)
This example defines the two function types, but puts them in the same recursion group (introduced by the GC proposal), which means they have different, incompatible type identities. If recursion groups were supported by wasm2c, for example, it would assign different type identifiers to $malloc_t and $strlen_t. Doing a call_indirect $malloc_t, but passing it the address of strlen in the table would trap.
Imported functions have to say which of the two types they have and it is a linking error if a function of the wrong type is supplied at instantiation, just like for any pair of different function types.
Basically deduplicating types based on their structure becomes really expensive once you have recursive and mutually recursive types. So we deduplicate based on the structure of entire recursion groups instead. Types can be mutually recursive inside a recursion group, but recursion groups cannot be mutually recursive with other recursion groups, so deduplicating on the level of recursion groups is still efficient. As a side effect, the different types within a single recursion group are always distinct from each other, even if they have the same structure.
ah interesting.
... but hmm, so it's a closed group, right? that seems like it would make things annoying.
... but hmm, we guess this gives us named function types. if we use lambda calculus to represent type names, then we can pad the recursive type with the type name (represented in lambda calculus). we don't know anything about lambda calculus but it should be possible to represent strings in lambda calculus yeah? (that's basically newtypes but with strings as names instead of unique objects)
we suppose rec + private = newtypes
something like
(type $t (private))
(rec
(func $ignoreme (param $t))
(func $strlen_t (param i32) (result i32))
)
would be unique for each instance of the module?
but if $t were exported, then another module could do
(import "foo" "bar" (type $t (private)))
(rec
(func $ignoreme (param $t))
(func $strlen_t (param i32) (result i32))
)
(not sure how type import syntax but anyway)
and the $strlen_t would be equivalent?
if this is the case, then yeah, this is functionally equivalent to newtypes.
Maybe! I don't have a good understanding of how private types are intended to interact with nontrivial recursion groups.
what happens if you have a recursion group like
(rec
(type $t i32)
(type $u i64)
)
what do these types mean
That wouldn't be valid. Only heap type types (i.e. function, struct, and array types) can be defined in recursion groups. You can learn more about this from the GC overview or spec.
ahh!
so, instead of applying newtypes to the parameters and results, we could be applying newtypes to the function types themselves? that makes sense
really we just wanna have function newtypes outside of the GC proposal. :p this would allegedly enable some new optimizations in emscripten too...
so, rough idea:
(newtype $t $heaptype)
is sugar for
(rec
(type (private))
(type $t $heaptype)
)
(or thereabouts. not entirely sure about the syntax.) and this can be imported and exported somehow.
then we can work backwards from there to define a GCless version of this idea, particularly when $heaptype is a function type. this would mean newtypes + typed function references would require GC if we wanna support recursion, but that's probably okay.
how does it sound now?
(or maybe we can just... move rec to typed function references? or somehow extend typed function references with rec, moving rec out of GC?)
What proposal the feature is in shouldn't matter. GC and typed function references are both phase 4 and part of the spec, so compliant engines have to implement them. There's an idea of introducing profiles, and if we ever have a "GC-less" profile, perhaps it can include recursion groups but not struct or array types. But the spec doesn't have profiles yet.