1// Copyright 2020 The Go Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style
3// license that can be found in the LICENSE file.
4
5package fuzz
6
7import (
8	"encoding/binary"
9	"fmt"
10	"math"
11	"unsafe"
12)
13
14type mutator struct {
15	r       mutatorRand
16	scratch []byte // scratch slice to avoid additional allocations
17}
18
19func newMutator() *mutator {
20	return &mutator{r: newPcgRand()}
21}
22
23func (m *mutator) rand(n int) int {
24	return m.r.intn(n)
25}
26
27func (m *mutator) randByteOrder() binary.ByteOrder {
28	if m.r.bool() {
29		return binary.LittleEndian
30	}
31	return binary.BigEndian
32}
33
34// chooseLen chooses length of range mutation in range [1,n]. It gives
35// preference to shorter ranges.
36func (m *mutator) chooseLen(n int) int {
37	switch x := m.rand(100); {
38	case x < 90:
39		return m.rand(min(8, n)) + 1
40	case x < 99:
41		return m.rand(min(32, n)) + 1
42	default:
43		return m.rand(n) + 1
44	}
45}
46
47// mutate performs several mutations on the provided values.
48func (m *mutator) mutate(vals []any, maxBytes int) {
49	// TODO(katiehockman): pull some of these functions into helper methods and
50	// test that each case is working as expected.
51	// TODO(katiehockman): perform more types of mutations for []byte.
52
53	// maxPerVal will represent the maximum number of bytes that each value be
54	// allowed after mutating, giving an equal amount of capacity to each line.
55	// Allow a little wiggle room for the encoding.
56	maxPerVal := maxBytes/len(vals) - 100
57
58	// Pick a random value to mutate.
59	// TODO: consider mutating more than one value at a time.
60	i := m.rand(len(vals))
61	switch v := vals[i].(type) {
62	case int:
63		vals[i] = int(m.mutateInt(int64(v), maxInt))
64	case int8:
65		vals[i] = int8(m.mutateInt(int64(v), math.MaxInt8))
66	case int16:
67		vals[i] = int16(m.mutateInt(int64(v), math.MaxInt16))
68	case int64:
69		vals[i] = m.mutateInt(v, maxInt)
70	case uint:
71		vals[i] = uint(m.mutateUInt(uint64(v), maxUint))
72	case uint16:
73		vals[i] = uint16(m.mutateUInt(uint64(v), math.MaxUint16))
74	case uint32:
75		vals[i] = uint32(m.mutateUInt(uint64(v), math.MaxUint32))
76	case uint64:
77		vals[i] = m.mutateUInt(v, maxUint)
78	case float32:
79		vals[i] = float32(m.mutateFloat(float64(v), math.MaxFloat32))
80	case float64:
81		vals[i] = m.mutateFloat(v, math.MaxFloat64)
82	case bool:
83		if m.rand(2) == 1 {
84			vals[i] = !v // 50% chance of flipping the bool
85		}
86	case rune: // int32
87		vals[i] = rune(m.mutateInt(int64(v), math.MaxInt32))
88	case byte: // uint8
89		vals[i] = byte(m.mutateUInt(uint64(v), math.MaxUint8))
90	case string:
91		if len(v) > maxPerVal {
92			panic(fmt.Sprintf("cannot mutate bytes of length %d", len(v)))
93		}
94		if cap(m.scratch) < maxPerVal {
95			m.scratch = append(make([]byte, 0, maxPerVal), v...)
96		} else {
97			m.scratch = m.scratch[:len(v)]
98			copy(m.scratch, v)
99		}
100		m.mutateBytes(&m.scratch)
101		vals[i] = string(m.scratch)
102	case []byte:
103		if len(v) > maxPerVal {
104			panic(fmt.Sprintf("cannot mutate bytes of length %d", len(v)))
105		}
106		if cap(m.scratch) < maxPerVal {
107			m.scratch = append(make([]byte, 0, maxPerVal), v...)
108		} else {
109			m.scratch = m.scratch[:len(v)]
110			copy(m.scratch, v)
111		}
112		m.mutateBytes(&m.scratch)
113		vals[i] = m.scratch
114	default:
115		panic(fmt.Sprintf("type not supported for mutating: %T", vals[i]))
116	}
117}
118
119func (m *mutator) mutateInt(v, maxValue int64) int64 {
120	var max int64
121	for {
122		max = 100
123		switch m.rand(2) {
124		case 0:
125			// Add a random number
126			if v >= maxValue {
127				continue
128			}
129			if v > 0 && maxValue-v < max {
130				// Don't let v exceed maxValue
131				max = maxValue - v
132			}
133			v += int64(1 + m.rand(int(max)))
134			return v
135		case 1:
136			// Subtract a random number
137			if v <= -maxValue {
138				continue
139			}
140			if v < 0 && maxValue+v < max {
141				// Don't let v drop below -maxValue
142				max = maxValue + v
143			}
144			v -= int64(1 + m.rand(int(max)))
145			return v
146		}
147	}
148}
149
150func (m *mutator) mutateUInt(v, maxValue uint64) uint64 {
151	var max uint64
152	for {
153		max = 100
154		switch m.rand(2) {
155		case 0:
156			// Add a random number
157			if v >= maxValue {
158				continue
159			}
160			if v > 0 && maxValue-v < max {
161				// Don't let v exceed maxValue
162				max = maxValue - v
163			}
164
165			v += uint64(1 + m.rand(int(max)))
166			return v
167		case 1:
168			// Subtract a random number
169			if v <= 0 {
170				continue
171			}
172			if v < max {
173				// Don't let v drop below 0
174				max = v
175			}
176			v -= uint64(1 + m.rand(int(max)))
177			return v
178		}
179	}
180}
181
182func (m *mutator) mutateFloat(v, maxValue float64) float64 {
183	var max float64
184	for {
185		switch m.rand(4) {
186		case 0:
187			// Add a random number
188			if v >= maxValue {
189				continue
190			}
191			max = 100
192			if v > 0 && maxValue-v < max {
193				// Don't let v exceed maxValue
194				max = maxValue - v
195			}
196			v += float64(1 + m.rand(int(max)))
197			return v
198		case 1:
199			// Subtract a random number
200			if v <= -maxValue {
201				continue
202			}
203			max = 100
204			if v < 0 && maxValue+v < max {
205				// Don't let v drop below -maxValue
206				max = maxValue + v
207			}
208			v -= float64(1 + m.rand(int(max)))
209			return v
210		case 2:
211			// Multiply by a random number
212			absV := math.Abs(v)
213			if v == 0 || absV >= maxValue {
214				continue
215			}
216			max = 10
217			if maxValue/absV < max {
218				// Don't let v go beyond the minimum or maximum value
219				max = maxValue / absV
220			}
221			v *= float64(1 + m.rand(int(max)))
222			return v
223		case 3:
224			// Divide by a random number
225			if v == 0 {
226				continue
227			}
228			v /= float64(1 + m.rand(10))
229			return v
230		}
231	}
232}
233
234type byteSliceMutator func(*mutator, []byte) []byte
235
236var byteSliceMutators = []byteSliceMutator{
237	byteSliceRemoveBytes,
238	byteSliceInsertRandomBytes,
239	byteSliceDuplicateBytes,
240	byteSliceOverwriteBytes,
241	byteSliceBitFlip,
242	byteSliceXORByte,
243	byteSliceSwapByte,
244	byteSliceArithmeticUint8,
245	byteSliceArithmeticUint16,
246	byteSliceArithmeticUint32,
247	byteSliceArithmeticUint64,
248	byteSliceOverwriteInterestingUint8,
249	byteSliceOverwriteInterestingUint16,
250	byteSliceOverwriteInterestingUint32,
251	byteSliceInsertConstantBytes,
252	byteSliceOverwriteConstantBytes,
253	byteSliceShuffleBytes,
254	byteSliceSwapBytes,
255}
256
257func (m *mutator) mutateBytes(ptrB *[]byte) {
258	b := *ptrB
259	defer func() {
260		if unsafe.SliceData(*ptrB) != unsafe.SliceData(b) {
261			panic("data moved to new address")
262		}
263		*ptrB = b
264	}()
265
266	for {
267		mut := byteSliceMutators[m.rand(len(byteSliceMutators))]
268		if mutated := mut(m, b); mutated != nil {
269			b = mutated
270			return
271		}
272	}
273}
274
275var (
276	interesting8  = []int8{-128, -1, 0, 1, 16, 32, 64, 100, 127}
277	interesting16 = []int16{-32768, -129, 128, 255, 256, 512, 1000, 1024, 4096, 32767}
278	interesting32 = []int32{-2147483648, -100663046, -32769, 32768, 65535, 65536, 100663045, 2147483647}
279)
280
281const (
282	maxUint = uint64(^uint(0))
283	maxInt  = int64(maxUint >> 1)
284)
285
286func init() {
287	for _, v := range interesting8 {
288		interesting16 = append(interesting16, int16(v))
289	}
290	for _, v := range interesting16 {
291		interesting32 = append(interesting32, int32(v))
292	}
293}
294