GC Fuzzing

This is a sketch of a series of milestones, roughly estimated to be about one PR each, for GC fuzzing. We don't need to do exactly these milestones in exactly this order. It is okay if, in the process of implementing them, we find reason to do milestone X before Y and decide to swap their order. It is okay if one milestone becomes three PRs, or two milestones become one PR. This is just a sketch to provide some light structure. Also, these milestones represent a lot of work, and while the goal is certainly to get everything here finished during your internship, if it turns out that this is more work that can be completed in that amount of time, that is okay.

Incremental Milestones

• Port the table_ops fuzzer from arbitrary to mutatis

  Details

  • Replacing arbitrary-based generator with a mutatis-based fuzzer
  • Oracle should be able to (largely) remain unmodified
  • Avoid adding new features or changing existing functionality as much as possible
  • Start handling the scenario where:
    • We originally have a valid series of fuzzer ops A,
    • then a random mutation inserts, removes, or changes an op in A to produce fuzzer ops A',
    • but A' is now no longer a valid sequence of fuzzer ops (for example, an initial op whose result was the input for a subsequent op was removed, for example).
    • Now we have to figure out how to handle invalid test cases:
      • Do we throw it away and continue to the next one?
      • Do we "patch up" the test case in a post-processing pass that fixes it up such that it becomes valid?
      • I'm thinking we probably want to do a fix-up pass to avoid wasting cycles on test cases we won't execute, ultimately hurting our overall fuzzing throughput, but I'm not 100% sure that is the right choice, and I am all ears for counter arguments and alternative ideas.
      • As far as mutatis-related prior art goes, the allocator fuzzer handled this stuff in the oracle: it simply avoided performing the fuzzer's allocation operations when they did not make sense (i.e. it ignores the "deallocate pointer with id X" operation if there isn't currently a live allocation with id X): https://github.com/fitzgen/deallocate-zeroed/blob/52c2b9b7305dd1a947b3342128fcf0d03143223e/crates/fuzzing/src/lib.rs#L656
      • We want to always generate valid Wasm, otherwise we can't even execute the subset of ops that are valid, so I think we will need to do the equivalent filtering/fixing up in the generator rather than in the oracle.
      • This fix-up pass could be its own pass, mutating the fuzzer ops AST structure directly, before we generate a Wasm binary from that AST structure. Or, alternatively, it could be integrated into Wasm-binary-from-AST generation step.
  • Goal: Become familiar with mutatis and move the fuzzer towards our north star vision for it

• Add support for empty (rec ...) groups containing zero or more empty struct types.

  Details

  • Add generation support for these (rec ...) groups with zero or more empty struct types
  • Add a fuzzer op that allocates a random one of our struct types. We should avoid emitting this op when we have not defined any struct types.
  • Add a function import that takes a structref argument to our Wasm binary skeleton
  • Add a fuzzer op that calls that new function
  • Add a function import for each defined struct type that takes a reference of that type of struct specifically
  • Add a fuzzer op that calls these new typed functions
  • Add support for generating locals, globals, and tables that contain structrefs and concretely typed struct references
  • Add new or extend existing fuzzer ops for accessing locals/globals/tables of structrefs and concretely typed struct references
  • Define a mutation that adds an empty struct type to an existing (rec ...) group
  • Define a mutation that removes a struct type from an existing (rec ...) group
  • Define a mutation that moves a struct type within an existing (rec ...) group
  • Define a mutation that moves a struct type from an existing (rec ...) group to another
  • Define a mutation that duplicates a (rec ...) group
  • Define a mutation that removes a whole (rec ...) group
  • Define a mutation that merges two (rec ...) groups
  • Define a mutation that splits a (rec ...) group in two, if possible
  • Will need to migrate the abstract representation of the value stack from a couner of how many externrefs are on the stack to an actual stack of types
  • Note: there is a whole lot here, even just exercising empty struct definitions, so it may make sense to split this up into a few PRs
  • Goal: start exercising type canonicalization, lay down initial infrastructure for (rec ...) groups and struct types.

• Add support for exercising subtyping relationships

  Details

  • Add support for on struct type to be a subtype of another struct type
  • Subtypes must be defined after their supertypes, so this will require we do some validation/filtering/fixups in the face of mutations that reorder types. (This restriction prevents cyclic subtyping where A subtypes B and B subtypes A.)
  • Want to think hard about how we represent types, rec groups, and type references in the AST at this point and how we are architecting the program. These choices are going to have a big impact on everything we do from here on out.
    • Do we just have a list of rec groups that directly reflect the order we will put them into the Wasm binary?
    • Do we create arbitrary type graphs and then do a topological sort on them to ensure they are valid? If we do this approach, what happens in the future when we find a cycle that is not within the same rec group? Or do we not even have rec groups here, just types, and then generate rec groups as part of the projection out from the graph?
    • Do we reference types by id and ignore references when there is not type associated with that id?
    • Or do we simply reference types by their type index, as in Wasm? And then ignore invalid references?
  • Goal: Continue to fill out type system features that we exercise, figure out the architecture we want for dealing with references between types.

• Add support for casting and testing references

  Details

  • Add a fuzzer op for casts that should always succeed (from a subtype to a supertype). This should become a ref.cast instruction in the Wasm binary.

  • Add a fuzzer op for fallible downcasts. This should not trap and kill the whole program if the downcast fails. In the fullness of time, we will want to generate blocks that do things with the downcasted value that are only executed if the downcast succeeds, something like this:

    block (param ...)
      ;; Break out of this block if we fail to cast the reference on top of the
      ;; stack to its subtype.
      ref.br_on_cast_fail ...
    
      ;; Do stuff with the subtype reference...
    end
    
    ;; Control joins again here and the program continues.
    

    And we will want to exercise both the br_on_cast_fail and br_on_cast instructions, which will require slightly different shapes of blocks.

    Initially, we can simply downcast to a nullable subtype reference, where we get null if the downcast fails:

    block (param (ref null $my_super)) (result (ref null $my_sub))
      local.tee $my_temp
      ;; Test if the downcast will succeed.
      ref.test ...
      if (result (ref null $my_sub))
        ;; The downcast will succeed, do a downcast-or-trap operation which we
        ;; know will not trap.
        local.get $my_temp
        ref.cast ...
      else
        ;; The downcast would fail, so just create a null reference instead.
        ref.null ...
      end
    end
    

  • Goal: Exercise subtyping checks and casting logic.

• Add support for POD and externref fields in structs

  Details

  • Add generation and mutation support for i8/i16/i32/i64/f32/f64/v128/externref struct fields. Reference fields will be trickier and can be added in another milestone.
  • Add fuzzer ops for struct.get and struct.set
  • Maybe: Add fuzzer ops for creating POD constants? Or should we just create zero constants on demand when necessary in the AST-to-Wasm-binary generation step? We aren't trying to exercise arithmetic in this fuzzer, that is well exercised by other fuzzers already, so the only interesting case for POD data is really when it comes from another struct's field. Other than that interesting case, we just need a some value in order to allocate a struct containing these values.
  • Add mutators to add, remove, and modify a field in a defined struct type
  • Goal: start exercising accessing, reading from, and writing to GC objects

• Add support for concretely-typed references as struct fields

  Details

  • Extend the items from the previous milestone to full type references between different defined struct types
  • Also add support for abstract structref types
  • Non-nullable type references will be tricky: if we have a cycle of non-nullable references, then those types are not currently inhabitable.
    • Can detect and correct this in our fix-up pass, perhaps
    • Okay to punt on this in a first PR, but we definitely would want to start handling them in a closely following PR. This is an important corner of the spec, and we perform optimizations based on non-nullability in the compiler, and one that none of our other fuzzers are exercising this right now (wasm-smith does not support non-nullable references yet).
  • This phase is when we will really start seeing the impact of our architecture choices around how to represent types and references between them in the AST.
  • Goal: start exercising references between GC objects and constructing interesting type- and heap-graphs, exercise non-nullable references

• Add support for i31refs and eqrefs

  Details

  • Support for eqref fields/locals/globals/tables
  • Support for i31ref fields/locals/globals/tables
  • Define new fuzzer ops for upcasting concrete and abstract struct refs and i31refs to abstract eqrefs
  • Define new fuzzer ops for i31.get_s and i31.get_u
  • Add host function imports that take i31refs and eqrefs from Wasm
    • Maybe: make the i31ref-taking host functions also take the results of i31.get_s and i31.get_u and assert that the host's version of those operations matches the inline Wasm versions
  • Goal: continue filling out coverage for the Wasm GC type system, exercise i31refs

• Add support for defining array types

  Details

  • Extend everything we have done so far to array types
  • Should be relatively easy at this point, since we already laid down all the infrastructure
  • Will want to take care that we don't generate out-of-bounds array accesses very often (we do want to exercise the out-of-bounds paths, but we don't want 99% of test cases failing to actually run most of the generated program because of traps)
  • Goal: complete our coverage of the Wasm GC type system, exercise array accesses and their bounds checks

• Enumerate Wasm GC instructions and ensure that the fuzzer exercises each of them

  Details

  • There are a number of misc instructions that we still won't exercise at this point in time, things like array.copy and array.new_elem
  • We should go through each of them and add support for exercising those instructions, if we don't already
  • Goal: complete our coverage of the Wasm GC execution semantics

Additional Ideas and Misc. Items

• Rename the fuzz target to gc_ops or something, it has already grown / will continue to grow way past just exercising table.{get,set} and etc...

• Add GC-after-N-allocations and OOM-after-N-allocations counters to our runtime, generate values for those counters in our test case generator, and then configure them based on those values in our oracle

  Details

  • I remember that SpiderMonkey's fuzzing has something similar with its OOM after N allocations and then their JS helper that sets that to 0, runs a closure, then 1, runs the closer, etc... It was incredibly effective at finding improperly-handled OOM bugs.
  • Would exercise the we-need-to-GC-before-satisfying-the-current-allocation path in our raw GC allocation libcalls
  • Will probably want to gate these counters' compilation on #[cfg(fuzzing)]
  • Will need to have a plan to avoid timeouts in the face of frequent GCs because of small counter values. Might need to make GCs consume fuel. Or might just make the counter not auto-reset and instead go to "infinity" after it triggers once. Or something.

• Generalize the host functions that create and take GC refs to arbitrary numbers of params and results

  Details

  • Right now, they always take 3 arguments or return 3 arguments
  • They should take an arbitrary number of arguments and/or return an arbitrary number of arguments, controlled by the fuzzer/mutator

• Investigate moving from a operand stack paradigm to a "places" paradigm

  Details

  • That is, instead of each GC op saying "here are my operand types that I pop from the stack, and result types that I push onto the stack" we instead have them say "here is where I get operands from (and their types) and here is where I put results (and their types)".

    Something like this:

    enum SimplePlace {
        /// The `i`th local.
        Local(u32),
        /// The `i`th global.
        Global(u32),
        /// The `i`th table's `j`th element.
        Table(u32, u32),
    }
    
    enum Place {
        Simple(SimplePlace),
        /// The `i`th field of the struct at the given simple place.
        StructField(SimplePlace, u32),
        /// The `i`th element of the array at the given simple place.
        ArrayElement(SimplePlace, u32),
    }
    
    impl GcOp {
        pub(crate) fn operands(&self) -> &[(Type, Place)] {
            // ...
        }
        pub(crate) fn results(&self) -> &[(Type, Place)] {
            // ...
        }
    }

    And we would fixup a GC op's places rather than fixing up the stack. And encoding each GC op would always be stack-neutral (not pop any incoming stack operands, not push any outgoing stack operands)

  • This is probably easier to fixup than the stack stuff, while still reusing as many existing operands as possible (never have to insert drops)

  • This probably gets us more-interesting DFGs and liveness

  • Hopefully would ultimately lead to more-interesting heap graphs as well

• Use partial evaluation to emit expected-value assertions

  Details

  • Do some abstract interpretation (possibly during fixup) to partially evaluate our GC ops (but not optimize the emitted Wasm code based on the results, just track it)
  • Add a new GcOp::Assert instruction, that does something like this at encoding time:

    for (place, abstract_value) in partial_eval_results_at_current_program_point {
        if let Some(concrete_value) = abstract_value.as_concrete() {
            // []
            place.emit_get();
            // [t]
            concrete_value.emit();
            // [t t]
            emit_call_assert_equal();
            // []
        }
    }

  • The goal is to find heap corruption where values are overwritten or incorrect.

• Generate arbitrary numbers of {eqref,i31ref,structref,arrayref,(ref null? $idx), ...} locals, globals, and tables (clamped to within reasonable ranges). Right now we always generate just a single local, global, and table of each of those types. This would allow for more interesting data-flow graphs and interactions with alias analysis.

+cc @khagankhan