Indirect call signature checks shouldn't be nominal

[AndrewScheidecker]

The design and spec interpreter use an explicit signature table to check call_indirect signatures. This is effectively a nominal type system for function pointers: you can have two signature table entries with the same parameters and return type, and they are distinct types as far as call_indirect is concerned.

This rules out calling a pointer to a function in a different module, since you can't refer to the target module's signature for the function, and in general doesn't work with dynamic linking.

I think that call_indirect signature checks should be defined structurally: that if a call_indirect expects the same parameter types and return type as the function identified by its dynamic index, the signature check should succeed.

The signature table makes sense from an encoding and implementation perspective, but I don't think it's necessary to define WebAssembly semantics. So I think the design shouldn't mention a signature table, and should be explicit that the signature check is structural.

[titzer]

Dynamic linking can be made to work with the current design by adding a label to signatures in the modules' respective signature tables and checking label equivalence across modules. That kind of punts the problem to user space, admittedly.

There was a significant use case envisioned that labels are more fine-grained than structure signature checks, so, e.g. a C++ compiler can also enforce a secondary security property such as a call to a vtable method has to not only be the same signature but from the same method family.

The implication of not having a signature table is that engines have to canonicalize signatures and internally generate the table for fast dynamic checking.

[AndrewScheidecker]

The implication of not having a signature table is that engines have to canonicalize signatures and internally generate the table for fast dynamic checking.

I'm not saying there shouldn't be a signature table, just that it's not necessary to define the semantics of signature checking in terms of table indices. It's necessary right now to distinguish between identical signatures that are in the signature table multiple times, but I don't think that's desirable.

With or without explicit tables, linking two modules needs to canonicalize signatures. I can see why it's useful to have a label to distinguish function types that are otherwise identical, but that implies there is some canonicalization that needs to make that distinction.

@titzer Can we take it that this 'significant use case' is no longer being requested to be accommodated via specific runtime support? If not then can someone please elaborate on the requirements?

I think it would be much cleaner to make these explicit arguments, rather than implicit via the signature tables, so that they are not conflated with function indexes. So the function signature might have as one argument a runtime_managed_index that could not be forged, could not be accessed by the wasm code at runtime, just generated as an argument as a call site, or tested in the callee by reference to this argument in a dedicated test operation. Not sure how you would want them managed, but perhaps someone understanding the requirements could work it out.

[lukewagner]

I think it's really attractive to have an explicit signature table at the binary encoding level and it's actually more work to prevent duplicates while at the same time ruling out finer-grained-than-signature-match CFI, so I think it makes sense to represent the signature table explicitly in the AST/semantics.

However, the common case of dynamic linking will want structural unification. An alternative to labeling (which requires the main module and dylib to agree on a labeling scheme which thus becomes part of the ABI) is to allow the elements of the signature table of dylibs to be marked as "canonicalized" which means they are unified with matches in the main module's sig table. This should preserve the expressive power while keeping the common case simple. It also requires no cooperation between main and dylib modules.

[AndrewScheidecker]

I think it's really attractive to have an explicit signature table at the binary encoding level

I agree.

it's actually more work to prevent duplicates while at the same time ruling out finer-grained-than-signature-match CFI

I don't think that's true if you have to support dynamic linking, which implies finding identical signatures somewhere in the loader.

(which requires the main module and dylib to agree on a labeling scheme which thus becomes part of the ABI)

I don't see how you would implement such a CFI system without affecting the ABI.

allow the elements of the signature table of dylibs to be marked as "canonicalized" which means they are unified with matches in the main module's sig table

What if the main module sig table contains multiple signatures that match it; which one is it unified with? What about dynamic libraries calling functions defined in another dynamic library rather than the main module?

[lukewagner]

Ah, that's a good point: if one wanted to support dynamic linking and the fancy CFI, you would need labels to link signatures point-to-point as @titzer suggested above; the unification can't just pick one. But if labels is the only way to achieve the 99% use case of just unifying same-type signatures, then that's a pretty big wart added to the ABI (and perhaps binary size) to support this fancy-CFI corner case. Now we could just keep the door open and start with:

• same design as in current spec (duplicates allowed)
• unification of same-typed signatures at dynamic linking (just picking the first in cases of dups)

and leave it as a future feature to support labeling (which would support fancy-CFI + dynamic linking). The question is whether we'd later come to regret allowing duplicates, so maybe a more conservative route would be to disallow dups initially (but keep the explicit table) and wait to build up a concrete use case for allowing dups.

[rossberg]

One obvious solution would be to treat the types not as nominal definitions but as structural definitions. That is, duplicates are fine, but they define the same type. Implementations could do some normalisation of type references at module instantiation time to still keep actual runtime type tests a simple comparison. This would extend relatively easily to dynamic linking later.

Or is that the same you are suggesting, @lukewagner?

[lukewagner]

@rossberg-chromium The issue is that if we force normalization, then it locks out this use case of intentionally having duplicates for the purposes of finer-grained CFI (concrete example: you have a separate signature index for void A::foo() (and its overriders) and void B::foo() (and its overriders), despite them having the same signature so that you can catch errors where ((A*)a)->foo() calls something other than an A::foo() override). I don't think this is a critical use case and it could be achieved in different ways, but it almost seemed to come "for free" (just drop the no-duplicates restriction) until we considered dynamic linking. So my proposal was not to force normalization, but to postpone allowing duplicate signatures until post-MVP so we could decide if we really wanted this feature.

[rossberg]

Yeah, I'm not sure it's a low-level type system's role to enforce such nominal typing guarantees. And even if so, making function signatures nominal seems the wrong approach -- in your example, A should naturally be a nominal type, not every function type formed over it (even in C++, typedeffing void A::foo() twice yields the same type; and even nominal types support subtyping). So, if we wanted to support nominal typing for integrity, then it should better be a separate mechanism, and there is quite a design space to consider. Clearly post MVP, I'd say.

[lukewagner]

@rossberg-chromium I agree it's not the low-level type system's role to enforce; this was more like a raw tool to provide to the compiler to use as it chooses.

So any disagreement with changing the MVP to disallow duplicates in the signature table? One could also imagine that we take out the sig table entirely and embed the signatures in all uses, but this seems strictly worse from a size/decoding pov.

[rossberg]

Disallowing duplicates sounds fine. Might be a bit of a nuisance for both producers and consumers, but nothing dramatic, I'd think.