mutator.go

     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  
     5  package fuzz
     6  
     7  import (
     8  	"encoding/binary"
     9  	"fmt"
    10  	"math"
    11  	"unsafe"
    12  )
    13  
    14  type mutator struct {
    15  	r       mutatorRand
    16  	scratch []byte // scratch slice to avoid additional allocations
    17  }
    18  
    19  func newMutator() *mutator {
    20  	return &mutator{r: newPcgRand()}
    21  }
    22  
    23  func (m *mutator) rand(n int) int {
    24  	return m.r.intn(n)
    25  }
    26  
    27  func (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.
    36  func (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.
    48  func (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  
   119  func (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  
   150  func (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  
   182  func (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  
   234  type byteSliceMutator func(*mutator, []byte) []byte
   235  
   236  var 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  
   257  func (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  
   275  var (
   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  
   281  const (
   282  	maxUint = uint64(^uint(0))
   283  	maxInt  = int64(maxUint >> 1)
   284  )
   285  
   286  func 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
View as plain text