minimize.go

     1  // Copyright 2021 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  	"reflect"
     9  )
    10  
    11  func isMinimizable(t reflect.Type) bool {
    12  	return t == reflect.TypeOf("") || t == reflect.TypeOf([]byte(nil))
    13  }
    14  
    15  func minimizeBytes(v []byte, try func([]byte) bool, shouldStop func() bool) {
    16  	tmp := make([]byte, len(v))
    17  	// If minimization was successful at any point during minimizeBytes,
    18  	// then the vals slice in (*workerServer).minimizeInput will point to
    19  	// tmp. Since tmp is altered while making new candidates, we need to
    20  	// make sure that it is equal to the correct value, v, before exiting
    21  	// this function.
    22  	defer copy(tmp, v)
    23  
    24  	// First, try to cut the tail.
    25  	for n := 1024; n != 0; n /= 2 {
    26  		for len(v) > n {
    27  			if shouldStop() {
    28  				return
    29  			}
    30  			candidate := v[:len(v)-n]
    31  			if !try(candidate) {
    32  				break
    33  			}
    34  			// Set v to the new value to continue iterating.
    35  			v = candidate
    36  		}
    37  	}
    38  
    39  	// Then, try to remove each individual byte.
    40  	for i := 0; i < len(v)-1; i++ {
    41  		if shouldStop() {
    42  			return
    43  		}
    44  		candidate := tmp[:len(v)-1]
    45  		copy(candidate[:i], v[:i])
    46  		copy(candidate[i:], v[i+1:])
    47  		if !try(candidate) {
    48  			continue
    49  		}
    50  		// Update v to delete the value at index i.
    51  		copy(v[i:], v[i+1:])
    52  		v = v[:len(candidate)]
    53  		// v[i] is now different, so decrement i to redo this iteration
    54  		// of the loop with the new value.
    55  		i--
    56  	}
    57  
    58  	// Then, try to remove each possible subset of bytes.
    59  	for i := 0; i < len(v)-1; i++ {
    60  		copy(tmp, v[:i])
    61  		for j := len(v); j > i+1; j-- {
    62  			if shouldStop() {
    63  				return
    64  			}
    65  			candidate := tmp[:len(v)-j+i]
    66  			copy(candidate[i:], v[j:])
    67  			if !try(candidate) {
    68  				continue
    69  			}
    70  			// Update v and reset the loop with the new length.
    71  			copy(v[i:], v[j:])
    72  			v = v[:len(candidate)]
    73  			j = len(v)
    74  		}
    75  	}
    76  
    77  	// Then, try to make it more simplified and human-readable by trying to replace each
    78  	// byte with a printable character.
    79  	printableChars := []byte("012789ABCXYZabcxyz !\"#$%&'()*+,.")
    80  	for i, b := range v {
    81  		if shouldStop() {
    82  			return
    83  		}
    84  
    85  		for _, pc := range printableChars {
    86  			v[i] = pc
    87  			if try(v) {
    88  				// Successful. Move on to the next byte in v.
    89  				break
    90  			}
    91  			// Unsuccessful. Revert v[i] back to original value.
    92  			v[i] = b
    93  		}
    94  	}
    95  }
    96
View as plain text