call_indirect versus abstraction

[RossTate]

call_indirect has been a very useful feature for WebAssembly. However, the efficiency and good behavior of the instruction has implicitly relied on the simplicity of wasm's type system. In particular, every wasm value has exactly one (static) type it belongs to. This property conveniently avoids a number of known problems with untyped function calls in typed languages. But now that wasm is extending beyond numeric types, it has gotten to the point where we need to understand these problems and keep them in mind.

call_indirect fundamentally works by comparing the caller's expected signature against the callee's defined signature. With just numeric types, WebAssembly had the property that these signatures were equal if and only if a direct call to the function referenced by the corresponding funcref would have type-checked. But there are two reasons that will soon not be true:

1. With subtyping, a direct call would work so long as the actual function's defined signature is a "sub-signature" of the expected signature, meaning all the input types are subtypes of the function's parameter types and all the output types are supertypes of the function's result types. This means that an equality check between an indirect call's expected signature and the function's defined signature would trap in a number of perfectly safe situations, which might be problematic for supporting languages with heavy use of subtyping and indirect calls (as was raised during the discussion on deferring subtyping). It also means that, if a module intentionally exports a function with a weaker signature than the function was defined with, then call_indirect can be used to access the function with its private defined signature rather than just its weaker public signature (an issue that was just discovered and so has not yet been discussed).
2. With type imports, a module can export a type without exporting the definition of that type, providing abstraction that systems like WASI plan to heavily rely upon. That abstraction prevents other modules from depending on its particular definition at compile time. But at run time the abstract exported type is simply replaced with its definition. This is important, for example, for enabling call_indirect to work properly on exported functions whose exported signatures reference that exported type. However, if a malicious module knows what the definition of that exported type is, they can use call_indirect to convert back and forth between the exported type and its intended-to-be-secret definition because call_indirect only compares signatures at run time, when the two types are indeed the same. Thus a malicious module can use call_indirect to access secrets meant to be abstracted by the exported type, and can use call_indirect to forge values of the exported type that may violate security-critical invariants not captured in the definition of the type itself.

In both of the above situations, call_indirect can be used to bypass the abstraction of a module's exported signature. As I mentioned, so far this hasn't been a concern because wasm only had numeric types. And originally I thought that, by deferring subtyping, all concerns regarding call_indirect had also effectively been deferred. But what I recently realized is that, by removing subtyping, the "new" type (named externref in WebAssembly/reference-types#87) is effectively a stand-in for an abstract type import. If that's what people would like it to actually be, then unfortunately we need to take into consideration the above interaction between call_indirect and type imports.

Now there are many potential ways to address the above issues with call_indirect, but each has its tradeoffs, and it is simply much too large a design space to be able to come to a decision on quickly. So I am not suggesting that we solve this problem here and now. Rather, the decision to be made at the moment is whether to buy time to solve the problem properly with respect to externref. In particular, if we for now restrict call_indirect and func.ref to only type-check when the associated signature is entirely numeric, then we serve all the core-wasm use cases of indirect calls and at the same time leave room for all the potential solutions to the above issues. However, I do not know if this restriction is practical, both in terms of implementation effort and in terms of whether it obstructs the applications of externref that people are waiting for. The alternative is to leave call_indirect and func.ref as is. It is just possible that this means that, depending on the solution we arrive at, externref might not be instantiable like a true type import would be, and/or that externref might (ironically) not be able to have any supertypes (e.g. might not be able to be a subtype of anyref if we do eventually decide to add anyref).

I, speaking for just myself, consider both options manageable. While I do have a preference, I am not strongly pushing the decision to go one way or the other, and I believe y'all have better access to the information necessary to come to a well-informed decision. I just wanted y'all to know that there is a decision to be made, and at the same time I wanted to establish awareness of the overarching issue with call_indirect. If you would like a more thorough explanation of that issue than what the summary above provides, please read the following.

call_indirect versus Abstraction, in Detail

I'll use the notation call_indirect[ti*->to*](func, args), where [ti*] -> [to*] is the expected signature of the function, func is simply a funcref (rather that a funcref table and an index), and args are the to* values to pass to the function. Similarly, I'll use call($foo, args) for a direct call of the function with index $foo passing arguments args.

Now suppose $foo is the index of a function with declared input types ti* and output types to*. You might expect that call_indirect[ti*->to*](ref.func($foo), args) is equivalent to call($foo, args). Indeed, that is the case right now. But it's not clear that we can maintain that behavior.

call_indirect and Subtyping

One example potential problem came up in the discussion of subtyping. Suppose the following:

• tsub is a subtype of tsuper
• module instance IA exports a function $fsub that was defined with type [] -> [tsub]
• module MB imports a function $fsuper with type [] -> [tsuper]
• module instance IB is module MB instantiated with IA's $fsub as $fsuper (which is sound to do—even if it's not possible now, this issue is about potential upcoming problems)

Now consider what should happen if IB executes call_indirect[ -> tsuper](ref.func($fsuper)). Here are the two outcomes that seem most plausible:

1. The call succeeds because the expected signature and defined signature are compatible.
2. The call traps because the two signatures are distinct.

If we were to choose outcome 1, realize that we would likely need to employ one of two techniques to make this possible:

1. For imported functions, have call_indirect compare with the import signature rather than the definition signature.
2. Do an at-least-linear-time run-time check for subtype-compatibility of the expected signature and the definition signature.

If you prefer technique 1, realize that it won't work once we add Typed Function References (with variant subtyping). That is, func.ref($fsub) will be a ref ([] -> [tsub]) and also a ref ([] -> [tsuper]), and yet technique 1 will not be sufficient to keep call_indirect[ -> super](ref.func($fsub)) from trapping. This means outcome 1 likely requires technique 2, which has concerning performance implications.

So let's consider outcome 2 a bit more. The implementation technique here is to check if the expected signature of the call_indirect in IB is equal to the signature of the definition of $fsub in IA. At first the major downside of this technique might seem to be that it traps on a number of calls that are safe to execute. However, another downside is that it potentially introduces a security leak for IA.

To see how, let's switch up our example a bit and suppose that, although instance IA internally defines $fsub to have type [] -> [tsub], instance IA only exports it with type [] -> [tsuper]. Using the technique for outcome 2, instance IB can (maliciously) execute call_indirect[ -> tsub]($fsuper) and the call will succeed. That is, IB can use call_indirect to circumvent the narrowing IA did to its function's signature. At best, that means IB is dependent on an aspect of IA that is not guaranteed by IA's signature. At worst, IB can use this to access internal state that IA might have intentionally been concealing.

call_indirect and Type Imports

Now let's put subtyping aside and consider type imports. For convenience, I am going to talk about type imports, rather than just reference-type imports, but that detail is inconsequential. For the running example here, suppose the following:

• module instance IC defines a type capability and exports the type but not its definition as $handle

• module instance IC exports a function $do_stuff that was defined with type [capability] -> [] but exported with type [$handle] -> []

• module MD imports a type $extern and a function $run with type [$extern] -> []

• module instance ID is module MD instantiated with IA's exported $handle as $extern and with IA's exported $do_stuff as $run

What this example sets up is two modules where one module does stuff with the other module's values without knowing or being allowed to know what those values are. For example, this pattern is the planned basis for interacting with WASI.

Now let's suppose instance ID has managed to get a value e of type $extern and executes call_indirect[$extern -> ](ref.func($run), e). Here are the two outcomes that seem most plausible:

1. The call succeeds because the expected signature and defined signature are compatible.
2. The call traps because the two signatures are distinct.

Outcome 2 makes call_indirect pretty much useless with imported types. So for outcome 1, realize that the input type $extern is not the defined input type of $do_stuff (which instead is capability), so we would likely need to use one of two techniques to bridge this gap:

1. For imported functions, have call_indirect compare with the import signature rather than the definition signature.
2. Recognize that at run time the type $extern in instance ID represents capability.

If you prefer technique 1, realize that it once again won't work once we add Typed Function References. (The fundamental reason is the same as with subtyping, but it'd take even more text to illustrate the analog here.)

That leaves us with technique 2. Unfortunately, once again this presents a potential security issue. To see why, suppose ID is malicious and wants to get at the contents of $handle that IC had kept secret. Suppose further that ID has a good guess as to what $handle really represents, namely capability. ID can define the identity function $id_capability of type [capability] -> [capability]. Given a value e of type $extern, ID can then execute call_indirect[$extern -> capability](ref.func($id_capability), e). Using technique 2, this indirect call will succeed because $extern represents capability at run time, and ID will get the raw capability that e represents back. Similarly, given a value c of type capability, ID can execute call_indirect[capability -> $extern](ref.func($id_capability), c) to forge c into an $extern.

Conclusion

Hopefully I've made it clear that call_indirect has a number of significant upcoming performance, semantic, and/or security/abstraction issues—issues that WebAssembly has been fortunate to have avoided so far. Unfortunately, due to call_indirect being part of core WebAssembly, these issues crosscut a number of proposals in progress. At the moment, I think it would be best to focus on the most pressing such proposal, Reference Types, where we need to decide whether or not to restrict call_indirect and func.ref to only numeric types for now—a restriction we might be able to relax depending on how we eventually end up solving the overarching issues with call_indirect.

(Sorry for the long post. I tried my best to explain complex interactions of cross-module compile-time-typing-meets-run-time-typing features and demonstrate the importance of those interactions as concisely as possible.)

[tlively]

Thanks for this detailed writeup, Ross! I have small question: in the "call_indirect and Type Imports" section you write,

If you prefer technique 1, realize that it once again won't work once we add Typed Function References.

Is this also subject to the caveat from the the previous section that the problem is only present once we add variant subtyping to the typed function references?

[RossTate]

It is not. All the issues in the subtyping section are independent of type imports, and all the issues in the type imports section are independent of subtyping. With respect to the particular issue you're asking about, consider that a value of type ref ([] -> [capability]) can be returned by an exported function as a value of type ref ([] -> [$handle]), which then can be turned into a funcref and indirectly called to. Unlike with the exported function, this change-in-perspective of the value happens at run time rather than link time, so we cannot resolve it by comparing against the import signature since the function reference was never itself imported.

[ngzhian]

module instance IC defines a type capability and exports the type but not its definition as $handle
How will this work? There needs to be something that connects capability and $handle so that IC will know how to deal with it?
Also based on https://github.com/WebAssembly/proposal-type-imports/blob/master/proposals/type-imports/Overview.md#exports, imported types are completely abstract. So even if $capability is exported, it is abstract. Perhaps I am misunderstanding something.

Similar question for the exporting for module instance IC exports a function $do_stuff that was defined with type [capability] -> [] but exported with type [$handle] -> [].

I can imagine some sort of subtyping relation used for this, e.g. if $capability <: $handle, then we can export $capability as $handle. But the start of this section it was mentioned to put subtyping aside, so I'm putting that aside... But I also thought a bit more about it:
If: $capability <: $handle, we can export $capability as $handle, but export ([$capability] -> []) as ([$handle] -> []) should "fail" because functions are contravariant in the argument.

[RossTate]

With type exports, a module specifies a signature, like type $handle; func $do_stuff_export : [$handle] -> [], and then instantiates the signature, like type $handle := capability; func $do_stuff_export := $do_stuff. (Ignore the specific syntax entirely.) The type-checker then checks "given that $handle represents capability in this module, is the export func $do_stuff_export := $do_stuff valid in this module?". Since the type of $do_stuff is [capability] -> [], its signature lines up exactly with that of $do_stuff_export after instantiating $handle with capability, so the check succeeds. (There's no subtyping involved here, just variable substitution.)

Note, though, that the signature itself says nothing about $handle. This means that everyone else is supposed to treat $handle as an abstract type. That is, the signature intentionally abstracts details of the module's implementation, and everyone else is supposed to respect that abstraction. The purpose of this issue is to illustrate that call_indirect can be used to circumvent that abstraction.

Hopefully that clarifies the issue a bit!

[ngzhian]

Thanks, that clarifies things. I'll have a question about the subtyping section (sorry to jump around):

I'm following the scenario where we want IB executing call_indirect[ -> tsuper](ref.func($fsuper)) to succeed, by having call_indirect "compare with the import signature rather than the definition signature."

And you added that (due to the typed function references) we also need

2. Do an at-least-linear-time run-time check for subtype-compatibility of the expected signature and the definition signature.

Should this be compatibility between "expected signature and the import signature"? Since we are assuming we have made call_indirect compare import signature with expected signature.

If the compatibility is checked between expected and import, then later, call_indirect[ -> tsub]($fsuper) should fail.

[RossTate]

Techniques 1 and 2 are given as two orthogonal ways to get that indirect call to work. Unfortunately, technique 1 is incompatible with typed function references, and technique 2 is likely too expensive. So neither of these seem likely to work out. Thus the rest of the section considers what happens if we use neither of these and just stick with simple equality-comparison between the expected and defined signature. Sorry for the confusion; not having a planned semantics means I have to discuss three potential semantics.

[rossberg]

Be careful not to jump to too many conclusions. ;)

My assumption is that call_indirect should remain as fast as today and therefore only ever require a type equivalence test, no matter how much subtyping we add to the language. At the same time, the runtime check needs to be coherent with the static type system, i.e., it has to respect the subtyping relation.

Now, these seemingly contradictive requirements can actually be reconciled fairly easily, as long as we make sure that the types usable with call_indirect are always at the leafs of the subtype hierarchy.

One established way of enforcing that is to introduce the notion of exact types into the type system. An exact type has no subtypes, only supertypes, and we'd have (exact T) <: T.

With that, we can require the target type at call_indirect to be an exact type. Furthermore, the type of functions themselves naturally is that function's exact type already.

A module could also require exact types on function imports, if it wanted to make sure that it can only be instantiated with functions that succeed an intended runtime check.

That's all that's needed to ensure that the current implementation technique of a simple pointer comparison on canonicalised function types remains valid. It's independent of what other subtyping there is, or how fancy we make function subtyping. (FWIW, I discussed this with Luke a while ago, and planned to create a PR, but it was blocked on pending changes to the subtyping story, and which proposal that now moves to.)

(One downside is that refining a function definition to a subtype is no longer a backwards-compatible change in general, at least not if its exact type has been used anywhere. But that drawback is unavoidable under our constraints, regardless of how exactly we enforce them.)

A couple of asides:

The alternative is to leave call_indirect and func.ref as is.

AFAICS, it's not feasible to disallow ref.func on functions that involve reference types. That would severely cripple many use cases, i.e., everything involving first-class functions operating on externref (callbacks, hooks, etc.).

It is just possible that this means that, depending on the solution we arrive at, externref might not be instantiable like a true type import would be, and/or that externref might (ironically) not be able to have any supertypes (e.g. might not be able to be a subtype of anyref if we do eventually decide to add anyref).

Can you elaborate? I don't see the connection.

[RossTate]

Be careful not to jump to too many conclusions. ;)

I'm not sure what conclusion you're referring to. My stated conclusion is that there are a number of issues with call_indirect that we need to be aware of and should start planning for. Your seem to be suggesting that these issues are inconsequential because you have a solution in mind. But that solution has not been reviewed or accepted by the CG, and we should not plan for it until it has. I specifically requested to not discuss solutions because it will take a while to evaluate and compare them and there are decisions we need to make before we have time to do those evaluations and comparisons properly. But, in order to prevent people forming the perception that this problem is solved and consequently avoid the pressing decision, I'll take a sec to quickly discuss your solution.

One established way of enforcing that is to introduce the notion of exact types into the type system.

Exact types are hardly an established solution. If anything, exact types have established problems that its proponents are still working to address. Interestingly, here is a thread where the TypeScript team originally saw how exact types of the form you're proposing could solve some problems, but then they eventually [realized)(https://github.com/microsoft/TypeScript/issues/12936#issuecomment-284590083) that exact types introduced more problems than they solved. (Note for context: that discussion was prompted by Flow's exact object types, which are not actually a form of exact type (in the theoretical sense) but instead simply disallow the object-analog of prefix subtyping.) I could imagine us replaying that thread here.

As an example of how these sorts of problems could play out for WebAssembly, suppose we had not deferred subtyping. The type of ref.null would be exact nullref using exact types. But exact nullref would not be a subtype of exact anyref. In fact, according to the usual semantics of exact types, likely no values would belong to exact anyref because likely no value's run-time type is exactly anyref. This would make call_indirect completely unusable for anyrefs.

Now maybe you have some different version of exact types in mind, but it would take a while to check that this different version somehow addresses the many open problems with exact types. So my point here is not to throw out this solution, but to recognize that it's not obvious that this is the solution and to not make decisions with that expectation.

Can you elaborate? I don't see the connection.

You're referencing a long sentence. Which part of it would you like me to elaborate on? One guess is that you might be missing the overall issue with call_indirect and type imports. Your exact-types suggestion only addresses problems with subtyping, but we established above that call_indirect has problems even without any subtyping.

That would severely cripple many use cases, i.e., everything involving first-class functions operating on externref (callbacks, hooks, etc.).

Yeah, so this is something I was hoping to get more information on. My understanding is that the primary use case of call_indirect is to support C/C++ function pointers and C++ virtual methods. My understanding is also that this use case is currently restricted to numeric signatures. I know of more potential uses of call_indirect, but as I mentioned I was suggesting a temporary restriction, so what matters is what are the current uses of call_indirect. Given that call_indirect still requires a table and index rather than simply a funcref, it doesn't seem particularly well designed for supporting callbacks. I didn't know if that was because currently it's not being used for this purpose.

Y'all know the code bases targeting this feature far better than I, so if y'all know of some real programs needing this functionality now, it'd be very helpful to provide a few examples of the usage patterns in need here. Besides being useful for figuring out if we need to support this functionality right now, if the functionality is needed now then these examples would be helpful in informing how best to quickly provide it while addressing the issues above.

[rossberg]

@RossTate:

If anything, exact types have established problems that its proponents are still working to address. Interestingly, here is a thread where the TypeScript team originally saw how exact types of the form you're proposing could solve some problems, but then they eventually realized that exact types introduced more problems than they solved. (Note for context: that discussion was prompted by Flow's exact object types, which are not actually a form of exact type (in the theoretical sense) but instead simply disallow the object-analog of prefix subtyping.) I could imagine us replaying that thread here.

The parentheses are key here. I'm not sure what exactly they have in mind in that thread, but it doesn't seem to be the same thing. Otherwise, statements like "it's assumed that a type T & U is always assignable to T, but this fails if T is an exact type" would make no sense (this doesn't fail, because T & U would be invalid or bottom). The other questions are mainly about pragmatics, i.e., where would a programmer want to use them (for objects), which don't apply in our case.

For low-level type systems, weren't exact types a crucial ingredient even in some of your own papers?

As an example of how these sorts of problems could play out for WebAssembly, suppose we had not deferred subtyping. The type of ref.null would be exact nullref using exact types. But exact nullref would not be a subtype of exact anyref.

No disagreement here. Not having subtypes is the purpose of exact types.

In fact, according to the usual semantics of exact types, likely no values would belong to exact anyref because likely no value's run-time type is exactly anyref.

Right, the combination (exact anyref) is not a useful type, given that the only purpose of anyref is to be a supertype. But why is that a problem?

This would make call_indirect completely unusable for anyrefs.

Are you sure that you aren't confusing levels now? A function type (exact (func ... -> anyref)) is perfectly useful. It's just not compatible with a type, say, (func ... -> (ref $T)). That is, exact prevents non-trivial subtyping on function types. But that's the whole point!

Maybe you are mixing up (exact (func ... -> anyref)) with (func ... -> exact anyref)? These are unrelated types.

Your exact-types suggestion only addresses problems with subtyping, but we established above that call_indirect has problems even without any subtyping.

You are somehow assuming that you'll be able to export a type without its definition as a means to define an abstract data type. Clearly, that approach doesn't work in the presence of dynamic type casts (call_indirect or otherwise). That's why I keep saying that we'll need newtype-style type abstraction, not ML-style type abstraction.

My understanding is that the primary use case of call_indirect is to support C/C++ function pointers

Yes, but that's not the sole use case of ref.func, which I was referring to, because you included it in your suggested restriction (maybe unnecessarily so?). In particular, there will be call_ref, which does not involve type checks.

[RossTate]

You are somehow assuming that you'll be able to export a type without its definition as a means to define an abstract data type. Clearly, that approach doesn't work in the presence of dynamic type casts (call_indirect or otherwise). That's why I keep saying that we'll need newtype-style type abstraction, not ML-style type abstraction.

Okay, so you seem to be agreeing that exact types do nothing to address the issue with call_indirect and type import. But you are also saying that there's no point in addressing that problem because it will be a problem anyways due to run-time casts. There is an easy way to prevent that problem: do not allow people to perform run-time casts on abstract types (unless the abstract type explicitly says it's castable). After all, it's an opaque type, so we should not be able to assume it exhibits the structure necessary to perform a cast. So even if there is a possibility that exact types address the subtyping problem, it is premature to disregard the other half of the problem.

As I said, every solution has tradeoffs. You seem to be presuming that your solution has only the tradeoffs you yourself have identified, and you seem to be presuming that the CG would prefer your solution over others. I, too, have a potential solution to this problem. It guarantees constant-time checks, is based on a technology already used in virtual machines, addresses all the problems here (I believe), doesn't require adding any new types, and actually adds additional functionality to WebAssembly with known applications. However, I am not presuming that it works as I expect and that I have not overlooked some shortcoming because you and others have not had a chance to look it over. I am also not presuming that the CG would prefer its tradeoffs over those of alternative options. Instead, I am trying to figure out what we can do to give us time to analyze the options so that the CG, rather than just me, can be the one who makes an informed decision on this cross-cutting topic.

In particular, there will be call_ref, which does not involve type checks.

The key word in your sentence is will. I am fully aware that there are applications of call_indirect with non-numeric types that people will want to have supported. And I expect that we will come up with a design that supports that functionality and addresses the issues above. But, as I said, ideally we can have some time to develop that design so that we're not quickly shipping a feature with cross-cutting implications before we have had a chance to investigate those implications. So my question is are there major programs that need that functionality now. If there is, there's no need to hypothesize; just point to some and illustrate how they currently rely on this functionality.

[tlively]

You are somehow assuming that you'll be able to export a type without its definition as a means to define an abstract data type. Clearly, that approach doesn't work in the presence of dynamic type casts (call_indirect or otherwise). That's why I keep saying that we'll need newtype-style type abstraction, not ML-style type abstraction.

This seems like a fundamental issue to me. Is enabling the confidentiality of the definitions of exported types a goal of the type imports proposal? I gather from this thread that @RossTate thinks it should be a goal and @rossberg thinks it is not currently a goal. Lets discuss and agree on this question before discussing solutions so that we can all work from the same set of assumptions.

[rossberg]

@RossTate:

Okay, so you seem to be agreeing that exact types do nothing to address the issue with call_indirect and type import.

Yes, if by that you mean the question of how to add a feature for defining abstract data types. There are a number of ways how type abstraction can work consistently, but such a feature is further down the road.

The key word in your sentence is will. I am fully aware that there are applications of call_indirect with non-numeric types that people will want to have supported.

The call_ref instruction is in the function ref proposal, so fairly close, in any case before any potential abstract data type mechanism. Are you suggesting that we put it on hold until then?

@tlively:

Is enabling the confidentiality of the definitions of exported types a goal of the type imports proposal? I gather from this thread that @RossTate thinks it should be a goal and @rossberg thinks it is not currently a goal.

It is a goal, but an abstract data type mechanism is a separate feature. And such a mechanism must be designed such that it does not affect the design of imports. If it did, then we would be doing it very wrong -- abstraction has to be ensured at the definition site, not the use site. Fortunately, though, this is not rocket science, and the design space is fairly well-expored.

[tlively]

Thanks, @rossberg, that makes sense. Adding abstraction primitives in a follow-up proposal after type imports and exports sounds fine to me, but it would be great if we could write down the details of how we plan to do that somewhere soon. The design of type imports and exports constrains and informs the design of abstract type imports and exports, so it is important that we have a good idea of how the abstraction will work down the road before we finalize the initial design.

[RossTate]

In addition to detailing that plan, since this issue with call_indirect is demonstrating that it affects pressing decisions, can you explain why you seem to be rejecting my suggestion that abstract types should not be castable (unless explicitly constrained to be castable)? They are opaque, so that suggestion seems to be in line with common practices of abstract types.

[rossberg]

@tlively, yes, agreed. Plus various other things I meant to write up for a while. Will do once I've worked through all the fallout from #69. ;)

@RossTate, because that would make abstract data types incompatible with casts. Just because I want to prevent others from seeing through an abstract type, I don't necessarily want to prevent them (or myself) from casting to an abstract type. Creating such a false dichotomy would break central use cases of casts. For example, of course I want to be able to pass a value of abstract type to a polymorphic function.