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