Repository: tetratelabs/wazero
Pull request #481 (2022-04-19 04:03:34)

Adds random module generator for fuzzing the compiler
This commit adds the random module generator for compiler testing.
Notably, it only generates valid and (supposedly) compilable Wasm modules.
Generating such random sources/programs and using them for testing or 
fuzzing compilers is the widely known way of securing and hardening them [1,2].

This commit only creates random modules where functions do not have
any meaningful body. That will be resolved in a subsequent commit
as the implementation for generating random function body could be
huge.

Note that the implementation has already found a bug #485, and can be
easily integrated with the [fuzzing feature of Go 1.18](https://tip.golang.org/doc/fuzz/):


```go
func FuzzCompiler(f *testing.F) {
	r := wazero.NewRuntimeWithConfig(wazero.NewRuntimeConfig().
		WithFeatureMultiValue(true))
	f.Fuzz(func(t *testing.T, seed []byte, numTypes, numFunctions, numImports, numExports, numGlobals, numElements, numData uint32, needStartSection bool) {
		// Generate a random WebAssembly module.
		m := Gen(seed, wasm.FeaturesFinished, numTypes, numFunctions, numImports, numExports, numGlobals, numElements, numData, needStartSection)
		// Encode the generated module (*wasm.Module) as binary.
		bin := binary.EncodeModule(m)
		// Pass the generated binary into our compilers.
		_, err := r.CompileModule(context.Background(), bin)
		require.NoError(t, err)
	})
}

```

[1] https://dl.acm.org/doi/fullHtml/10.1145/3363562
[2] https://en.wikipedia.org/wiki/Compiler_correctness

mathetake: ok the left is to adds tests for dataSection generator. 
mathetake: changed Gen signature so that it accepts not only Feature Flags but also it accepts the explicit size of each section (which makes it possible for fuzzer to work better).

Patch:
diff --git a/internal/modgen/modgen.go b/internal/modgen/modgen.go
new file mode 100644
index 00000000..6ce9731a
--- /dev/null
+++ b/internal/modgen/modgen.go
@@ -0,0 +1,447 @@
+package modgen
+
+import (
+	"crypto/sha256"
+	"encoding/binary"
+	"fmt"
+	"math"
+	"math/rand"
+	"strconv"
+
+	"github.com/tetratelabs/wazero/internal/leb128"
+	"github.com/tetratelabs/wazero/internal/wasm"
+)
+
+// Gen generates a pseudo random compilable module based on `seed`.
+// The size of each section is controlled by the corresponding params.
+// For example, `numImports` controls the number of segment in the import section.
+//
+// Note: "pseudo" here means the determinism of the generated results,
+// e.g. giving same seed returns exactly the same module for
+// the same code base in Gen.
+//
+// Note: this is only used for testing wazero runtime.
+func Gen(seed []byte, enabledFeature wasm.Features,
+	numTypes, numFunctions, numImports, numExports, numGlobals, numElements, numData uint32,
+	needStartSection bool,
+) *wasm.Module {
+	if len(seed) == 0 {
+		return &wasm.Module{}
+	}
+
+	checksum := sha256.Sum256(seed)
+	g := &generator{
+		// Use 4 randoms created from the unique sha256 hash value of the seed.
+		size: len(seed), rands: make([]random, 4), enabledFeature: enabledFeature,
+		numTypes:         numTypes,
+		numFunctions:     numFunctions,
+		numImports:       numImports,
+		numExports:       numExports,
+		numGlobals:       numGlobals,
+		numElements:      numElements,
+		numData:          numData,
+		needStartSection: needStartSection,
+	}
+	for i := 0; i < 4; i++ {
+		g.rands[i] = rand.New(rand.NewSource(
+			int64(binary.LittleEndian.Uint64(checksum[i*8 : (i+1)*8]))))
+	}
+	return g.gen()
+}
+
+type generator struct {
+	// rands holds random sources for generating a module.
+	rands         []random
+	nextRandIndex int
+
+	// size holds the original size of the seed.
+	size int
+
+	// m is the resulting module.
+	m *wasm.Module
+
+	enabledFeature wasm.Features
+	numTypes, numFunctions, numImports, numExports,
+	numGlobals, numElements, numData uint32
+	needStartSection bool
+}
+
+// random is the interface over methods of rand.Rand which are used by our generator.
+// This is only for testing the generator implmenetation.
+type random interface {
+	// See rand.Intn.
+	Intn(n int) int
+
+	// See rand.Read
+	Read(p []byte) (n int, err error)
+}
+
+func (g *generator) nextRandom() (ret random) {
+	ret = g.rands[g.nextRandIndex]
+	g.nextRandIndex = (g.nextRandIndex + 1) % len(g.rands)
+	return
+}
+
+// gen generates a random Wasm module.
+func (g *generator) gen() *wasm.Module {
+	g.m = &wasm.Module{}
+	g.genTypeSection()
+	g.genImportSection()
+	g.genFunctionSection()
+	g.genTableSection()
+	g.genMemorySection()
+	g.genGlobalSection()
+	g.genExportSection()
+	g.genStartSection()
+	g.genElementSection()
+	g.genCodeSection()
+	g.genDataSection()
+	return g.m
+}
+
+// genTypeSection creates random types each with a random number of parameters and results.
+func (g *generator) genTypeSection() {
+	for i := uint32(0); i < g.numTypes; i++ {
+		var resultNumCeil = g.size
+		if !g.enabledFeature.Get(wasm.FeatureMultiValue) {
+			resultNumCeil = 2
+		}
+		ft := g.newFunctionType(g.nextRandom().Intn(g.size), g.nextRandom().Intn(resultNumCeil))
+		g.m.TypeSection = append(g.m.TypeSection, ft)
+	}
+}
+
+func (g *generator) newFunctionType(params, results int) *wasm.FunctionType {
+	ret := &wasm.FunctionType{}
+	for i := 0; i < params; i++ {
+		ret.Params = append(ret.Params, g.newValueType())
+	}
+	for i := 0; i < results; i++ {
+		ret.Results = append(ret.Results, g.newValueType())
+	}
+	return ret
+}
+
+func (g *generator) newValueType() (ret wasm.ValueType) {
+	switch g.nextRandom().Intn(4) {
+	case 0:
+		ret = wasm.ValueTypeI32
+	case 1:
+		ret = wasm.ValueTypeI64
+	case 2:
+		ret = wasm.ValueTypeF32
+	case 3:
+		ret = wasm.ValueTypeF64
+	default:
+		panic("BUG")
+	}
+	return
+}
+
+// genImportSection creates random import descriptions, including memory and table.
+func (g *generator) genImportSection() {
+	var memoryImported, tableImported int
+	for i := uint32(0); i < g.numImports; i++ {
+		imp := &wasm.Import{
+			Name:   fmt.Sprintf("%d", i),
+			Module: fmt.Sprintf("module-%d", i),
+		}
+		g.m.ImportSection = append(g.m.ImportSection, imp)
+
+		r := g.nextRandom().Intn(4 - memoryImported - tableImported)
+		if r == 0 && len(g.m.TypeSection) > 0 {
+			imp.Type = wasm.ExternTypeFunc
+			imp.DescFunc = uint32(g.nextRandom().Intn(len(g.m.TypeSection)))
+			continue
+		}
+
+		if r == 0 || r == 1 {
+			imp.Type = wasm.ExternTypeGlobal
+			imp.DescGlobal = &wasm.GlobalType{
+				ValType: g.newValueType(),
+				Mutable: g.nextRandom().Intn(2) == 0,
+			}
+			continue
+		}
+
+		if memoryImported == 0 {
+			min := g.nextRandom().Intn(4) // Min in reality is relatively small like 4.
+			max := g.nextRandom().Intn(int(wasm.MemoryMaxPages)-min) + min
+
+			imp.Type = wasm.ExternTypeMemory
+			imp.DescMem = &wasm.Memory{
+				Min:          uint32(min),
+				Max:          uint32(max),
+				IsMaxEncoded: true,
+			}
+			memoryImported = 1
+			continue
+		}
+
+		if tableImported == 0 {
+			min := g.nextRandom().Intn(4) // Min in reality is relatively small like 4.
+			max := uint32(g.nextRandom().Intn(int(wasm.MemoryMaxPages)-min) + min)
+
+			imp.Type = wasm.ExternTypeTable
+			tableImported = 1
+			imp.DescTable = &wasm.Table{
+				Min: uint32(min),
+				Max: &max,
+			}
+			continue
+		}
+
+		panic("BUG")
+	}
+}
+
+// genFunctionSection generates random function declarations whose type is randomly chosen
+// from already generated type section.
+func (g *generator) genFunctionSection() {
+	numTypes := len(g.m.TypeSection)
+	if numTypes == 0 {
+		return
+	}
+	for i := uint32(0); i < g.numFunctions; i++ {
+		typeIndex := g.nextRandom().Intn(numTypes)
+		g.m.FunctionSection = append(g.m.FunctionSection, uint32(typeIndex))
+	}
+}
+
+// genTableSection generates random table definition if there's no import fot table.
+func (g *generator) genTableSection() {
+	if g.m.ImportTableCount() != 0 {
+		return
+	}
+
+	min := g.nextRandom().Intn(4) // Min in reality is relatively small like 4.
+	max := uint32(g.nextRandom().Intn(int(wasm.MemoryMaxPages)-min) + min)
+	g.m.TableSection = &wasm.Table{Min: uint32(min), Max: &max}
+}
+
+// genTableSection generates random memory definition if there's no import fot table.
+func (g *generator) genMemorySection() {
+	if g.m.ImportMemoryCount() != 0 {
+		return
+	}
+	min := g.nextRandom().Intn(4) // Min in reality is relatively small like 4.
+	max := g.nextRandom().Intn(int(wasm.MemoryMaxPages)-min) + min
+	g.m.MemorySection = &wasm.Memory{Min: uint32(min), Max: uint32(max), IsMaxEncoded: true}
+}
+
+// genTableSection generates random globals.
+func (g *generator) genGlobalSection() {
+	for i := uint32(0); i < g.numGlobals; i++ {
+		expr, t := g.newConstExpr()
+		mutable := g.nextRandom().Intn(2) == 0
+		global := &wasm.Global{
+			Type: &wasm.GlobalType{ValType: t, Mutable: mutable},
+			Init: expr,
+		}
+		g.m.GlobalSection = append(g.m.GlobalSection, global)
+	}
+}
+
+func (g *generator) newConstExpr() (*wasm.ConstantExpression, wasm.ValueType) {
+	importedGlobalCount := g.m.ImportGlobalCount()
+	importedGlobalsNotExist := 1
+	if importedGlobalCount > 0 {
+		importedGlobalsNotExist = 0
+	}
+	var opcode wasm.Opcode
+	var data []byte
+	var valueType wasm.ValueType
+	switch g.nextRandom().Intn(5 - importedGlobalsNotExist) {
+	case 0:
+		opcode = wasm.OpcodeI32Const
+		v := g.nextRandom().Intn(math.MaxInt32)
+		if g.nextRandom().Intn(2) == 0 {
+			v = -v
+		}
+		data = leb128.EncodeInt32(int32(v))
+		valueType = wasm.ValueTypeI32
+	case 1:
+		opcode = wasm.OpcodeI64Const
+		v := g.nextRandom().Intn(math.MaxInt64)
+		if g.nextRandom().Intn(2) == 0 {
+			v = -v
+		}
+		data = leb128.EncodeInt64(int64(v))
+		valueType = wasm.ValueTypeI64
+	case 2:
+		opcode = wasm.OpcodeF32Const
+		data = make([]byte, 4)
+		_, err := g.nextRandom().Read(data)
+		if err != nil {
+			panic(err)
+		}
+		valueType = wasm.ValueTypeF32
+	case 3:
+		opcode = wasm.OpcodeF64Const
+		data = make([]byte, 8)
+		_, err := g.nextRandom().Read(data)
+		if err != nil {
+			panic(err)
+		}
+		valueType = wasm.ValueTypeF64
+	case 4:
+		opcode = wasm.OpcodeGlobalGet
+		// Constexpr can only reference imported globals.
+		globalIndex := g.nextRandom().Intn(int(importedGlobalCount))
+		data = leb128.EncodeUint32(uint32(globalIndex))
+		// Find the value type of the imported global.
+		var cnt int
+		for _, imp := range g.m.ImportSection {
+			if imp.Type == wasm.ExternTypeGlobal {
+				if cnt == globalIndex {
+					valueType = imp.DescGlobal.ValType
+					break
+				} else {
+					cnt++
+				}
+			}
+		}
+	default:
+		panic("BUG")
+	}
+	return &wasm.ConstantExpression{Opcode: opcode, Data: data}, valueType
+}
+
+// genTableSection generates random export descriptions from previously generated functions, globals, table and memory declarations.
+func (g *generator) genExportSection() {
+	funcs, globals, table, memory, err := g.m.AllDeclarations()
+	if err != nil {
+		panic("BUG:" + err.Error())
+	}
+
+	var possibleExports []wasm.Export
+	for i := range funcs {
+		possibleExports = append(possibleExports, wasm.Export{Type: wasm.ExternTypeFunc, Index: uint32(i)})
+	}
+	for i := range globals {
+		possibleExports = append(possibleExports, wasm.Export{Type: wasm.ExternTypeGlobal, Index: uint32(i)})
+	}
+	if table != nil {
+		possibleExports = append(possibleExports, wasm.Export{Type: wasm.ExternTypeTable, Index: 0})
+	}
+	if memory != nil {
+		possibleExports = append(possibleExports, wasm.Export{Type: wasm.ExternTypeMemory, Index: 0})
+	}
+
+	for i := uint32(0); i < g.numExports; i++ {
+		target := possibleExports[g.nextRandom().Intn(len(possibleExports))]
+
+		g.m.ExportSection = append(g.m.ExportSection, &wasm.Export{
+			Type:  target.Type,
+			Index: target.Index,
+			Name:  strconv.Itoa(int(i)),
+		})
+	}
+}
+
+// genStartSection generates start section whose function is randomly chosen from previously declared function.
+func (g *generator) genStartSection() {
+	if !g.needStartSection {
+		return
+	}
+	funcs, _, _, _, err := g.m.AllDeclarations()
+	if err != nil {
+		panic("BUG:" + err.Error())
+	}
+
+	var candidates []wasm.Index
+	for funcIndex, typeIndex := range funcs {
+		sig := g.m.TypeSection[typeIndex]
+		// Start function must have the empty signature.
+		if sig.EqualsSignature(nil, nil) {
+			candidates = append(candidates, wasm.Index(funcIndex))
+		}
+	}
+
+	if len(candidates) > 0 {
+		g.m.StartSection = &candidates[g.nextRandom().Intn(len(candidates))]
+		return
+	}
+}
+
+// genStartSection generates random element section if table and functions exist.
+func (g *generator) genElementSection() {
+	funcs, _, _, table, err := g.m.AllDeclarations()
+	if err != nil {
+		panic("BUG:" + err.Error())
+	}
+
+	numFuncs := len(funcs)
+	if table == nil || numFuncs == 0 {
+		return
+	}
+
+	min := table.Min
+	for i := uint32(0); i < g.numElements; i++ {
+		// Elements can't exceed min of table.
+		indexes := make([]uint32, g.nextRandom().Intn(int(min)+1))
+		for i := range indexes {
+			indexes[i] = uint32(g.nextRandom().Intn(numFuncs))
+		}
+
+		offset := g.nextRandom().Intn(int(min) - len(indexes) + 1)
+		elem := &wasm.ElementSegment{
+			OffsetExpr: &wasm.ConstantExpression{
+				// TODO: support global.get expression.
+				Opcode: wasm.OpcodeI32Const,
+				Data:   leb128.EncodeInt32(int32(offset)),
+			},
+			Init: indexes,
+		}
+		g.m.ElementSection = append(g.m.ElementSection, elem)
+	}
+}
+
+// genCodeSection generates random code section for functions defined in this module.
+func (g *generator) genCodeSection() {
+	codeSectionSize := len(g.m.FunctionSection)
+	for i := 0; i < codeSectionSize; i++ {
+		g.m.CodeSection = append(g.m.CodeSection, g.newCode())
+	}
+}
+
+func (g *generator) newCode() *wasm.Code {
+	// TODO: generate random body.
+	return &wasm.Code{Body: []byte{wasm.OpcodeUnreachable, // With unreachable allows us to make this body valid for any signature.
+		wasm.OpcodeEnd}}
+}
+
+// genDataSection generates random data section if memory is declared and its minums is not zero.
+func (g *generator) genDataSection() {
+	_, _, mem, _, err := g.m.AllDeclarations()
+	if err != nil {
+		panic("BUG:" + err.Error())
+	}
+
+	if mem == nil || mem.Min == 0 || g.numData == 0 {
+		return
+	}
+
+	min := int(mem.Min * wasm.MemoryPageSize)
+	for i := uint32(0); i < g.numData; i++ {
+		offset := g.nextRandom().Intn(min)
+		expr := &wasm.ConstantExpression{
+			Opcode: wasm.OpcodeI32Const,
+			Data:   leb128.EncodeInt32(int32(offset)),
+		}
+
+		init := make([]byte, g.nextRandom().Intn(min-offset+1))
+		if len(init) == 0 {
+			continue
+		}
+		_, err := g.nextRandom().Read(init)
+		if err != nil {
+			panic(err)
+		}
+
+		g.m.DataSection = append(g.m.DataSection, &wasm.DataSegment{
+			OffsetExpression: expr,
+			Init:             init,
+		})
+	}
+}
diff --git a/internal/wasm/module.go b/internal/wasm/module.go
index 3d8a6931..b9cba9e6 100644
--- a/internal/wasm/module.go
+++ b/internal/wasm/module.go
@@ -436,7 +436,8 @@ func validateConstExpression(globals []*GlobalType, expr *ConstantExpression, ex
 	}
 
 	if actualType != expectedType {
-		return fmt.Errorf("const expression type mismatch")
+		return fmt.Errorf("const expression type mismatch expected %s but got %s",
+			ValueTypeName(expectedType), ValueTypeName(actualType))
 	}
 	return nil
 }


Test patch:
diff --git a/internal/modgen/modgen_test.go b/internal/modgen/modgen_test.go
new file mode 100644
index 00000000..17c4b2a4
--- /dev/null
+++ b/internal/modgen/modgen_test.go
@@ -0,0 +1,726 @@
+package modgen
+
+import (
+	"context"
+	"encoding/hex"
+	"math/rand"
+	"strconv"
+	"testing"
+
+	"github.com/tetratelabs/wazero"
+	"github.com/tetratelabs/wazero/internal/leb128"
+	"github.com/tetratelabs/wazero/internal/testing/require"
+	"github.com/tetratelabs/wazero/internal/wasm"
+	"github.com/tetratelabs/wazero/internal/wasm/binary"
+)
+
+const (
+	i32 = wasm.ValueTypeI32
+	i64 = wasm.ValueTypeI64
+	f32 = wasm.ValueTypeF32
+	f64 = wasm.ValueTypeF64
+)
+
+// TestModGen is like a end-to-end test and verifies that our module generator only generates valid compilable modules.
+func TestModGen(t *testing.T) {
+	tested := map[string]struct{}{}
+	rand := rand.New(rand.NewSource(0)) // use deterministic seed source for easy debugging.
+	runtime := wazero.NewRuntimeWithConfig(wazero.NewRuntimeConfig().WithFinishedFeatures())
+	for _, size := range []int{1, 2, 5, 10, 50, 100} {
+		for i := 0; i < 100; i++ {
+			seed := make([]byte, size)
+			_, err := rand.Read(seed)
+			require.NoError(t, err)
+			encoded := hex.EncodeToString(seed)
+			if _, ok := tested[encoded]; ok {
+				continue
+			}
+			t.Run(encoded, func(t *testing.T) {
+				numTypes, numFunctions, numImports, numExports, numGlobals, numElements, numData :=
+					rand.Intn(size), rand.Intn(size), rand.Intn(size), rand.Intn(size), rand.Intn(size), rand.Intn(size), rand.Intn(size)
+				needStartSection := rand.Intn(2) == 0
+
+				// Generate a random WebAssembly module.
+				m := Gen(seed, wasm.FeatureMultiValue,
+					uint32(numTypes), uint32(numFunctions), uint32(numImports), uint32(numExports), uint32(numGlobals), uint32(numElements), uint32(numData), needStartSection)
+				// Encode the generated module (*wasm.Module) as binary.
+				bin := binary.EncodeModule(m)
+				// Pass the generated binary into our compilers.
+				code, err := runtime.CompileModule(context.Background(), bin)
+				require.NoError(t, err)
+				code.Close()
+			})
+		}
+	}
+}
+
+// testRand implements randm for testing.
+type testRand struct {
+	ints   []int
+	intPos int
+	bufs   [][]byte
+	bufPos int
+}
+
+var _ random = &testRand{}
+
+func (tr *testRand) Intn(n int) int {
+	ret := tr.ints[tr.intPos] % n
+	tr.intPos = (tr.intPos + 1) % len(tr.ints)
+	return ret
+}
+
+func (tr *testRand) Read(p []byte) (n int, err error) {
+	buf := tr.bufs[tr.bufPos]
+	copy(p, buf)
+	tr.bufPos = (tr.bufPos + 1) % len(tr.bufs)
+	return
+}
+
+func newGenerator(size int, ints []int, bufs [][]byte) *generator {
+	return &generator{size: size,
+		rands: []random{&testRand{ints: ints, bufs: bufs}},
+		m:     &wasm.Module{},
+	}
+}
+
+func TestGenerator_newFunctionType(t *testing.T) {
+	for _, tc := range []struct {
+		params, results int
+		exp             *wasm.FunctionType
+	}{
+		{params: 1, results: 1, exp: &wasm.FunctionType{
+			Params: []wasm.ValueType{i32}, Results: []wasm.ValueType{i64}}},
+		{params: 1, results: 2, exp: &wasm.FunctionType{
+			Params: []wasm.ValueType{i32}, Results: []wasm.ValueType{i64, f32}}},
+		{params: 2, results: 2, exp: &wasm.FunctionType{
+			Params: []wasm.ValueType{i32, i64}, Results: []wasm.ValueType{f32, f64}}},
+		{params: 0, results: 2, exp: &wasm.FunctionType{
+			Results: []wasm.ValueType{i32, i64}}},
+		{params: 2, results: 0, exp: &wasm.FunctionType{
+			Params: []wasm.ValueType{i32, i64}}},
+		{params: 6, results: 6, exp: &wasm.FunctionType{
+			Params:  []wasm.ValueType{i32, i64, f32, f64, i32, i32},
+			Results: []wasm.ValueType{i64, f32, f64, i32, i32, i64},
+		},
+		},
+	} {
+		t.Run(tc.exp.String(), func(t *testing.T) {
+			g := newGenerator(0, []int{0, 1, 2, 3, 4}, nil)
+			actual := g.newFunctionType(tc.params, tc.results)
+			require.Equal(t, tc.exp.String(), actual.String())
+		})
+	}
+}
+
+func TestGenerator_newValueType(t *testing.T) {
+	g := newGenerator(0, []int{0, 1, 2, 3, 4, 5}, nil)
+	require.Equal(t,
+		[]wasm.ValueType{i32, i64, f32, f64, i32},
+		[]wasm.ValueType{g.newValueType(), g.newValueType(), g.newValueType(), g.newValueType(), g.newValueType()},
+	)
+}
+
+func TestGenerator_typeSection(t *testing.T) {
+	g := newGenerator(100, []int{
+		// Params = 1, Reults = 1, i32, i32
+		1, 1, 0, 0,
+		// Params = 2, Results = 2, i32f32, i64f64
+		2, 2, 0, 2, 1, 3,
+		// Params = 0, Results = 4, f64f32i64i32
+		0, 4, 3, 2, 1, 0,
+	}, nil)
+	g.enabledFeature = wasm.FeatureMultiValue
+	g.numTypes = 3
+	g.genTypeSection()
+
+	expected := []*wasm.FunctionType{
+		{Params: []wasm.ValueType{i32}, Results: []wasm.ValueType{i32}},
+		{Params: []wasm.ValueType{i32, f32}, Results: []wasm.ValueType{i64, f64}},
+		{Params: []wasm.ValueType{}, Results: []wasm.ValueType{f64, f32, i64, i32}},
+	}
+
+	require.Equal(t, len(expected), len(g.m.TypeSection))
+	for i := range expected {
+		require.Equal(t, expected[i].String(), g.m.TypeSection[i].String())
+	}
+}
+
+func TestGenerator_importSection(t *testing.T) {
+	five := uint32(5)
+	for i, tc := range []struct {
+		ints       []int
+		numImports uint32
+		types      []*wasm.FunctionType
+		exp        []*wasm.Import
+	}{
+		{
+			types:      []*wasm.FunctionType{{}},
+			numImports: 2,
+			ints: []int{
+				// function type with type of index = 0  x 2
+				0, 0,
+				0, 0,
+			},
+			exp: []*wasm.Import{
+				{Type: wasm.ExternTypeFunc, DescFunc: 0, Module: "module-0", Name: "0"},
+				{Type: wasm.ExternTypeFunc, DescFunc: 0, Module: "module-1", Name: "1"},
+			},
+		},
+		{
+			types:      []*wasm.FunctionType{{}, {}},
+			numImports: 2,
+			ints: []int{
+				// function type with type of index = 1
+				0, 1,
+				// function type with type of index = 0
+				0, 0,
+			},
+			exp: []*wasm.Import{
+				{Type: wasm.ExternTypeFunc, DescFunc: 1, Module: "module-0", Name: "0"},
+				{Type: wasm.ExternTypeFunc, DescFunc: 0, Module: "module-1", Name: "1"},
+			},
+		},
+		{
+			types:      []*wasm.FunctionType{{}, {}},
+			numImports: 2,
+			ints: []int{
+				// function type with type of index = 1
+				0, 1,
+				// global type with type f32, and mutable
+				1, 2, 0,
+			},
+			exp: []*wasm.Import{
+				{Type: wasm.ExternTypeFunc, DescFunc: 1, Module: "module-0", Name: "0"},
+				{Type: wasm.ExternTypeGlobal, DescGlobal: &wasm.GlobalType{
+					Mutable: true, ValType: f32,
+				}, Module: "module-1", Name: "1"},
+			},
+		},
+		{
+			types:      []*wasm.FunctionType{{}, {}},
+			numImports: 2,
+			ints: []int{
+				// function type with type of index = 1
+				0, 1,
+				// global type with type f64, and immutable
+				1, 3, 1,
+			},
+			exp: []*wasm.Import{
+				{Type: wasm.ExternTypeFunc, DescFunc: 1, Module: "module-0", Name: "0"},
+				{Type: wasm.ExternTypeGlobal, DescGlobal: &wasm.GlobalType{
+					Mutable: false, ValType: f64,
+				}, Module: "module-1", Name: "1"},
+			},
+		},
+		{
+			numImports: 2,
+			ints: []int{
+				// global type with type i32, and mutable
+				0 /* func types are not given so 0 should be global */, 0, 0,
+				// global type with type f64, and immutable
+				1, 3, 1,
+			},
+			exp: []*wasm.Import{
+				{Type: wasm.ExternTypeGlobal, DescGlobal: &wasm.GlobalType{
+					Mutable: true, ValType: i32,
+				}, Module: "module-0", Name: "0"},
+				{Type: wasm.ExternTypeGlobal, DescGlobal: &wasm.GlobalType{
+					Mutable: false, ValType: f64,
+				}, Module: "module-1", Name: "1"},
+			},
+		},
+		{
+			types:      []*wasm.FunctionType{{}, {}},
+			numImports: 3,
+			ints: []int{
+				// Memory import with min=1,max=3,
+				2, 1, 2, /* max is rand + min = 2 + 1 = 3 */
+				// Table import with min=1,max=5
+				2, 1, 4, /* max is rand + min = 4 + 1 = 5 */
+				// function type with type of index = 1
+				2, 1,
+			},
+			exp: []*wasm.Import{
+				{Type: wasm.ExternTypeMemory, DescMem: &wasm.Memory{
+					Min: 1, Max: 3, IsMaxEncoded: true,
+				}, Module: "module-0", Name: "0"},
+				{Type: wasm.ExternTypeTable, DescTable: &wasm.Table{
+					Min: 1, Max: &five,
+				}, Module: "module-1", Name: "1"},
+				{Type: wasm.ExternTypeFunc, DescFunc: 1, Module: "module-2", Name: "2"},
+			},
+		},
+	} {
+		t.Run(strconv.Itoa(i), func(t *testing.T) {
+			g := newGenerator(100, tc.ints, nil)
+			g.numImports = uint32(tc.numImports)
+			g.m.TypeSection = tc.types
+
+			g.genImportSection()
+			require.Equal(t, len(tc.exp), len(g.m.ImportSection))
+
+			for i := range tc.exp {
+				require.Equal(t, tc.exp[i], g.m.ImportSection[i])
+			}
+		})
+	}
+}
+
+func TestGenerator_functionSection(t *testing.T) {
+	t.Run("with types", func(t *testing.T) {
+		types := make([]*wasm.FunctionType, 10)
+		g := newGenerator(100, []int{
+			100001, 105, 102, 100000003, 104, 6, 9, 8, 7, 10000,
+		}, nil)
+		g.numFunctions = 10
+		g.m.TypeSection = types
+		g.genFunctionSection()
+		require.Equal(t, []uint32{1, 5, 2, 3, 4, 6, 9, 8, 7, 0}, g.m.FunctionSection)
+	})
+	t.Run("without types", func(t *testing.T) {
+		g := newGenerator(100, []int{10}, nil)
+		g.genFunctionSection()
+		require.Equal(t, []uint32(nil), g.m.FunctionSection)
+	})
+}
+
+func TestGenerator_tableSection(t *testing.T) {
+	t.Run("with table import", func(t *testing.T) {
+		g := newGenerator(100, []int{10}, nil)
+		g.m.ImportSection = append(g.m.ImportSection, &wasm.Import{Type: wasm.ExternTypeTable})
+
+		g.genTableSection()
+		require.Nil(t, g.m.TableSection)
+	})
+	t.Run("without table import", func(t *testing.T) {
+		g := newGenerator(100, []int{1, 100}, nil)
+		g.genTableSection()
+		expMax := uint32(101)
+		require.Equal(t, &wasm.Table{Min: 1, Max: &expMax}, g.m.TableSection)
+	})
+}
+
+func TestGenerator_memorySection(t *testing.T) {
+	t.Run("with memory import", func(t *testing.T) {
+		g := newGenerator(100, []int{10}, nil)
+		g.m.ImportSection = append(g.m.ImportSection, &wasm.Import{Type: wasm.ExternTypeMemory})
+
+		g.genMemorySection()
+		require.Nil(t, g.m.MemorySection)
+	})
+	t.Run("without memory import", func(t *testing.T) {
+		g := newGenerator(100, []int{1, 100}, nil)
+		g.genMemorySection()
+		require.Equal(t, &wasm.Memory{Min: 1, Max: 101, IsMaxEncoded: true}, g.m.MemorySection)
+	})
+}
+
+func TestGenerator_newConstExpr(t *testing.T) {
+	for i, tc := range []struct {
+		ints    []int
+		bufs    [][]byte
+		imports []*wasm.Import
+		exp     *wasm.ConstantExpression
+		expType wasm.ValueType
+	}{
+		{
+			ints: []int{
+				0,   // i32.const
+				100, // 100 literal
+				1,   // non-negative
+			},
+			exp:     &wasm.ConstantExpression{Opcode: wasm.OpcodeI32Const, Data: leb128.EncodeInt32(100)},
+			expType: i32,
+		},
+		{
+			ints: []int{
+				0,   // i2.const
+				100, // 100 literal
+				0,   // negative
+			},
+			exp:     &wasm.ConstantExpression{Opcode: wasm.OpcodeI32Const, Data: leb128.EncodeInt32(-100)},
+			expType: i32,
+		},
+		{
+			ints: []int{
+				1,   // i64.const
+				100, // 100 literal
+				1,   // non-negative
+			},
+			exp:     &wasm.ConstantExpression{Opcode: wasm.OpcodeI64Const, Data: leb128.EncodeInt64(100)},
+			expType: i64,
+		},
+		{
+			ints: []int{
+				1,   // i64.const
+				100, // 100 literal
+				0,   // negative
+			},
+			exp:     &wasm.ConstantExpression{Opcode: wasm.OpcodeI64Const, Data: leb128.EncodeInt64(-100)},
+			expType: i64,
+		},
+		{
+			ints:    []int{2}, // f32.const
+			bufs:    [][]byte{{1, 2, 3, 4}},
+			exp:     &wasm.ConstantExpression{Opcode: wasm.OpcodeF32Const, Data: []byte{1, 2, 3, 4}},
+			expType: f32,
+		},
+		{
+			ints:    []int{3}, // f64.const
+			bufs:    [][]byte{{1, 2, 3, 4, 5, 6, 7, 8}},
+			exp:     &wasm.ConstantExpression{Opcode: wasm.OpcodeF64Const, Data: []byte{1, 2, 3, 4, 5, 6, 7, 8}},
+			expType: f64,
+		},
+		{
+			ints: []int{
+				4, // globa.get
+				1, // 2nd global.
+			},
+			imports: []*wasm.Import{
+				{},
+				{Type: wasm.ExternTypeGlobal, DescGlobal: &wasm.GlobalType{ValType: i32}},
+				{},
+				{Type: wasm.ExternTypeGlobal, DescGlobal: &wasm.GlobalType{ValType: f32}},
+			},
+			exp:     &wasm.ConstantExpression{Opcode: wasm.OpcodeGlobalGet, Data: []byte{1}},
+			expType: f32,
+		},
+		{
+			ints: []int{
+				4, // globa.get
+				0, // 1st global.
+			},
+			imports: []*wasm.Import{
+				{},
+				{Type: wasm.ExternTypeGlobal, DescGlobal: &wasm.GlobalType{ValType: i32}},
+				{},
+				{Type: wasm.ExternTypeGlobal, DescGlobal: &wasm.GlobalType{ValType: f32}},
+			},
+			exp:     &wasm.ConstantExpression{Opcode: wasm.OpcodeGlobalGet, Data: []byte{0}},
+			expType: i32,
+		},
+		{
+			ints: []int{
+				4,   // there's no imports, so this should result in i32.const.
+				100, // 100 literal
+				1,   // non-negative
+			},
+			exp:     &wasm.ConstantExpression{Opcode: wasm.OpcodeI32Const, Data: leb128.EncodeInt32(100)},
+			expType: i32,
+		},
+	} {
+		tc := tc
+		t.Run(strconv.Itoa(i), func(t *testing.T) {
+			g := newGenerator(100, tc.ints, tc.bufs)
+			g.m.ImportSection = tc.imports
+			actualExpr, actualType := g.newConstExpr()
+			require.Equal(t, tc.expType, actualType)
+			require.Equal(t, tc.exp, actualExpr)
+		})
+	}
+}
+
+func TestGenerator_globalSection(t *testing.T) {
+	g := newGenerator(100,
+		[]int{
+			// i32.const 123, mutable
+			0 /* i32.const */, 123, 1 /* non negative */, 0, /* mutable */
+			3 /* f64.const */, 1, /* immutable */
+			4 /* global.get */, 0 /* global index */, 1, /* immutable */
+		},
+		[][]byte{{1, 2, 3, 4, 5, 6, 7, 8}},
+	)
+
+	g.m.ImportSection = []*wasm.Import{{}, {},
+		{Type: wasm.ExternTypeGlobal, DescGlobal: &wasm.GlobalType{ValType: f32}},
+	}
+	g.numGlobals = 3
+
+	g.genGlobalSection()
+
+	expected := []*wasm.Global{
+		{
+			Type: &wasm.GlobalType{ValType: i32, Mutable: true},
+			Init: &wasm.ConstantExpression{
+				Opcode: wasm.OpcodeI32Const,
+				Data:   leb128.EncodeInt32(123),
+			},
+		},
+		{
+			Type: &wasm.GlobalType{ValType: f64, Mutable: false},
+			Init: &wasm.ConstantExpression{
+				Opcode: wasm.OpcodeF64Const,
+				Data:   []byte{1, 2, 3, 4, 5, 6, 7, 8},
+			},
+		},
+		{
+			Type: &wasm.GlobalType{ValType: f32, Mutable: false},
+			Init: &wasm.ConstantExpression{
+				Opcode: wasm.OpcodeGlobalGet,
+				Data:   []byte{0},
+			},
+		},
+	}
+
+	actual := g.m.GlobalSection
+	require.Equal(t, len(expected), len(actual))
+
+	for i := range actual {
+		require.Equal(t, expected[i], actual[i])
+	}
+}
+
+func TestGenerator_exportSection(t *testing.T) {
+	m := &wasm.Module{
+		FunctionSection: make([]uint32, 10),
+		GlobalSection: []*wasm.Global{
+			{Type: &wasm.GlobalType{}},
+			{Type: &wasm.GlobalType{}},
+			{Type: &wasm.GlobalType{}},
+			{Type: &wasm.GlobalType{}},
+			{Type: &wasm.GlobalType{}},
+		},
+		TableSection:  &wasm.Table{},
+		MemorySection: &wasm.Memory{},
+	}
+
+	g := newGenerator(100, []int{
+		2,  // funcs[2]
+		13, // globals[3]
+		15, // table
+		16, // memory
+		7,  // funcs[7]
+	}, nil)
+	g.m = m
+
+	g.numExports = 5
+	g.genExportSection()
+
+	expected := []*wasm.Export{
+		{Type: wasm.ExternTypeFunc, Index: 2, Name: "0"},
+		{Type: wasm.ExternTypeGlobal, Index: 3, Name: "1"},
+		{Type: wasm.ExternTypeTable, Index: 0, Name: "2"},
+		{Type: wasm.ExternTypeMemory, Index: 0, Name: "3"},
+		{Type: wasm.ExternTypeFunc, Index: 7, Name: "4"},
+	}
+
+	actual := g.m.ExportSection
+
+	require.Equal(t, len(expected), len(actual))
+	for i := range actual {
+		require.Equal(t, expected[i], actual[i])
+	}
+}
+
+func TestGenerator_startSection(t *testing.T) {
+	t.Run("with cand", func(t *testing.T) {
+
+		m := &wasm.Module{
+			ImportSection: []*wasm.Import{
+				{Type: wasm.ExternTypeFunc, DescFunc: 0},
+				{Type: wasm.ExternTypeFunc, DescFunc: 1}, // candidate
+				{Type: wasm.ExternTypeFunc, DescFunc: 2},
+				{Type: wasm.ExternTypeFunc, DescFunc: 1}, // candidate
+			},
+			FunctionSection: []uint32{
+				0, 0, 1 /* candidate */, 0,
+			},
+			TypeSection: []*wasm.FunctionType{
+				{Params: []wasm.ValueType{i32}},
+				{},
+				{Params: []wasm.ValueType{f32}},
+				{Params: []wasm.ValueType{f64}},
+			},
+		}
+
+		takePtr := func(v uint32) *uint32 { return &v }
+
+		for i, tc := range []struct {
+			ints []int
+			exp  *wasm.Index
+		}{
+			{ints: []int{0}, exp: takePtr(1)},
+			{ints: []int{1}, exp: takePtr(3)},
+			{ints: []int{2}, exp: takePtr(6)},
+			{ints: []int{3}, exp: takePtr(1)},
+		} {
+			tc := tc
+			t.Run(strconv.Itoa(i), func(t *testing.T) {
+				g := newGenerator(100, tc.ints, nil)
+				g.needStartSection = true
+				g.m = m
+
+				g.genStartSection()
+				require.Equal(t, tc.exp, g.m.StartSection)
+			})
+		}
+	})
+
+	t.Run("no cand", func(t *testing.T) {
+		m := &wasm.Module{
+			ImportSection: []*wasm.Import{
+				{Type: wasm.ExternTypeFunc, DescFunc: 0},
+				{Type: wasm.ExternTypeFunc, DescFunc: 1},
+				{Type: wasm.ExternTypeFunc, DescFunc: 2},
+				{Type: wasm.ExternTypeFunc, DescFunc: 1},
+			},
+			FunctionSection: []uint32{
+				0, 1, 2, 0, 1, 2,
+			},
+			TypeSection: []*wasm.FunctionType{
+				{Params: []wasm.ValueType{i32}},
+				{Params: []wasm.ValueType{f32}},
+				{Params: []wasm.ValueType{f64}},
+			},
+		}
+		g := newGenerator(100, []int{0}, nil)
+		g.m = m
+
+		g.genStartSection()
+		require.Nil(t, g.m.StartSection)
+	})
+}
+
+func TestGenerator_elementSection(t *testing.T) {
+	t.Run("without table", func(t *testing.T) {
+		g := newGenerator(100, nil, nil)
+		g.genElementSection()
+		require.Nil(t, g.m.ElementSection)
+	})
+	t.Run("without function", func(t *testing.T) {
+		g := newGenerator(100, nil, nil)
+		g.m.TableSection = &wasm.Table{}
+		g.genElementSection()
+		require.Nil(t, g.m.ElementSection)
+	})
+	t.Run("ok", func(t *testing.T) {
+		for i, tc := range []struct {
+			ints        []int
+			numElements uint32
+			exps        []*wasm.ElementSegment
+		}{
+			{
+				numElements: 1,
+				ints: []int{
+					2 /* number of inedxes */, 0, 50, 98, /* offset */
+				},
+				exps: []*wasm.ElementSegment{
+					{
+						OffsetExpr: &wasm.ConstantExpression{Opcode: wasm.OpcodeI32Const, Data: leb128.EncodeInt32(98)},
+						Init:       []wasm.Index{0, 50},
+					},
+				},
+			},
+			{
+				numElements: 3,
+				ints: []int{
+					2 /* number of inedxes */, 25, 75, 0, /* offset */
+					1 /* number of inedxes */, 3, 99, /* offset */
+					10 /* number of inedxes */, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 /* offset */, 90,
+				},
+				exps: []*wasm.ElementSegment{
+					{
+						OffsetExpr: &wasm.ConstantExpression{Opcode: wasm.OpcodeI32Const, Data: leb128.EncodeInt32(0)},
+						Init:       []wasm.Index{25, 75},
+					},
+					{
+						OffsetExpr: &wasm.ConstantExpression{Opcode: wasm.OpcodeI32Const, Data: leb128.EncodeInt32(99)},
+						Init:       []wasm.Index{3},
+					},
+					{
+						OffsetExpr: &wasm.ConstantExpression{Opcode: wasm.OpcodeI32Const, Data: leb128.EncodeInt32(90)},
+						Init:       []wasm.Index{1, 2, 3, 4, 5, 6, 7, 8, 9, 10},
+					},
+				},
+			},
+		} {
+			tc := tc
+			t.Run(strconv.Itoa(i), func(t *testing.T) {
+				g := newGenerator(100, tc.ints, nil)
+				g.m = &wasm.Module{
+					TableSection:    &wasm.Table{Min: 100},
+					FunctionSection: make([]uint32, 100),
+				}
+				g.numElements = tc.numElements
+
+				g.genElementSection()
+				actual := g.m.ElementSection
+				require.Equal(t, len(tc.exps), len(actual))
+				for i := range actual {
+					require.Equal(t, tc.exps[i], actual[i])
+				}
+			})
+		}
+	})
+}
+
+func TestGenerator_dataSection(t *testing.T) {
+	t.Run("without memory", func(t *testing.T) {
+		g := newGenerator(100, nil, nil)
+		g.genDataSection()
+		require.Nil(t, g.m.DataSection)
+	})
+	t.Run("min=0", func(t *testing.T) {
+		g := newGenerator(100, nil, nil)
+		g.m.MemorySection = &wasm.Memory{Min: 0}
+		g.genDataSection()
+		require.Nil(t, g.m.DataSection)
+	})
+	t.Run("ok", func(t *testing.T) {
+		for i, tc := range []struct {
+			ints    []int
+			bufs    [][]byte
+			numData uint32
+			exps    []*wasm.DataSegment
+		}{
+			{
+				numData: 1,
+				ints: []int{
+					5, // offset
+					2, // size of inits
+				},
+				bufs: [][]byte{{0x1, 0x2}},
+				exps: []*wasm.DataSegment{
+					{
+						OffsetExpression: &wasm.ConstantExpression{
+							Opcode: wasm.OpcodeI32Const,
+							Data:   leb128.EncodeUint32(5),
+						},
+						Init: []byte{0x1, 0x2},
+					},
+				},
+			},
+			{
+				numData: 1,
+				ints: []int{
+					int(wasm.MemoryMaxPages) - 1, // offset
+					1,                            // size of inits
+				},
+				bufs: [][]byte{{0x1}},
+				exps: []*wasm.DataSegment{
+					{
+						OffsetExpression: &wasm.ConstantExpression{
+							Opcode: wasm.OpcodeI32Const,
+							Data:   leb128.EncodeUint32(uint32(wasm.MemoryMaxPages) - 1),
+						},
+						Init: []byte{0x1},
+					},
+				},
+			},
+		} {
+			tc := tc
+			t.Run(strconv.Itoa(i), func(t *testing.T) {
+				g := newGenerator(100, tc.ints, tc.bufs)
+				g.m.MemorySection = &wasm.Memory{Min: 1}
+				g.numData = tc.numData
+				g.genDataSection()
+				actual := g.m.DataSection
+				require.Equal(t, len(tc.exps), len(actual))
+				for i := range actual {
+					require.Equal(t, tc.exps[i], actual[i])
+				}
+			})
+		}
+	})
+}