Newtypes for stronger control flow integrity

[SoniEx2]

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:

1. 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.
2. 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?

[SoniEx2]

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)

[rossberg]

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:

1. 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.

2. How are values of this type created and accessed? Are there explicit conversion instructions? Are you proposing to add implicit conversions to Wasm?

3. 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.

[SoniEx2]

1. 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.

2. 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.

3. 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.)

[SoniEx2]

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.

[rossberg]

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.

[SoniEx2]

1. yeah, we could use input from folks who know more about CFI than we do.

2. 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.

3. we don't believe we are allowing casts to succeed between statically incompatible types?

[rossberg]

An object can only have one runtime type. So, not all of the following statements can be true at the same time:

1. Objects of type $t and (newtype $t) have the same representation.
2. Objects of static type $t can be cast to $t.
3. Objects of static type (newtype $t) can be cast to (newtype $t).
4. 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).

[SoniEx2]

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)

[rossberg]

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).

[SoniEx2]

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)?

[SoniEx2]

btw this blog post contains a pretty good overview of control flow integrity https://maskray.me/blog/2022-12-18-control-flow-integrity

[fgmccabe]

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.

[SoniEx2]

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.

[rossberg]

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.

[fgmccabe]

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.