Should engines validate the number of instances created by module-linking modules?

[alexcrichton]

While at the spec-level WebAssembly doesn't have any maximum limits on resources outside the u32 index space, most engines practically place limits on wasm modules to avoid them consuming too many resources (e.g. you can't import u32::max() - 2 functions). Today this resource validation is relatively simple, you just check the size of the section and then ensure that everything else is valid relative to that size.

With module linking, however, resource limits may be more difficult to validate. For example with n modules you can force 2^n instances to get created:

(module $PARENT
  (module $m0)
  (module $m1
    (instance (instantiate (module outer $PARENT $m0)))
    (instance (instantiate (module outer $PARENT $m0))))
  (module $m2
    (instance (instantiate (module outer $PARENT $m1)))
    (instance (instantiate (module outer $PARENT $m1))))
  (module $m3
    (instance (instantiate (module outer $PARENT $m2)))
    (instance (instantiate (module outer $PARENT $m2))))
  (module $m4
    (instance (instantiate (module outer $PARENT $m3)))
    (instance (instantiate (module outer $PARENT $m3))))
  (module $m5
    (instance (instantiate (module outer $PARENT $m4)))
    (instance (instantiate (module outer $PARENT $m4))))
  (instance (instantiate $m5))
)

Is it expected that engines should reject a module like this at validation-time? Or is this expected to fail at instantiation with a "resources exhasted" error?

[lukewagner]

Good question! I think it would be reasonable to add some new limits to the Implementation Limitations appendix to cover cases like these. These limits are enforced at validation time, which I think makes sense here too. Off the top of my head, the logical limits seem like:

• maximum number of transitive nested instances of a root module being validated
• maximum instance nesting depth

as both seem like ways to naturally blow up an engine in nonportable ways. I expect we could get away with some fairly conservative limits here, say 10,000 for number-of-children and 100 for nesting depth.

[rossberg]

Good question! I think it would be reasonable to add some new limits to the Implementation Limitations appendix to cover cases like these. These limits are enforced at validation time, which I think makes sense here too. Off the top of my head, the logical limits seem like:

• maximum number of transitive nested instances of a root module being validated
• maximum instance nesting depth

Technically, the Appendix distinguishes between Syntactic limits (static) and Execution limits (dynamic). And static limits primarily help limiting resource usage at compile time, not run time.

It doesn't generally make sense to try to bound dynamic resource usage through static limits. For example, validation cannot know about nested instances in modules that are imported. So ultimately, any limit on transitive nesting etc would have to be dynamic anyway. Moreover, the Appendix already allows reporting exceeded dynamic limits statically if an engine can prove it statically.

Concretely, regarding your example, I don't think it's useful to try to statically distinguish this example from a variation where all instances are of $m0. And dynamically, this is already handled by the existing limit on the number of allocated module instances -- execution limits are fluid and may depend on various variables, so that subsumes variables like nesting depth.

So I think we only need to extend Syntactic Limits with:

• the number of modules in a module
• the number of instances in a module
• the number of aliases in a module
• the nesting depth of modules

For Execution Limits, we may want to add:

• the number of allocated uninstantiated modules

[lukewagner]

Hmm, good point regarding the dynamic nature of module imports. That makes sense to me.

[alexcrichton]

Ah ok I wasn't aware of that appendix, and the difference between static and dynamic limits was exactly what I was wondering about. I wanted to basically confirm that the number of instances created was a dynamic limit rather than expected to be a static one. The syntactic and execution limits in #27 (comment) make sense to me, so I'll close this as answered.