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