From 9fe8aa42c5bd11e2eb6952a16da6287205d7bf97 Mon Sep 17 00:00:00 2001 From: Dmitry Vyukov Date: Sat, 24 Feb 2018 14:33:36 +0100 Subject: prog: add arbitrary mutation of complex structs Squash complex structs into flat byte array and mutate this array with generic blob mutations. This allows to mutate what we currently consider as paddings and add/remove paddings from structs, etc. --- prog/mutation.go | 323 ++++++++++++++++++++++++++++++++++--------------------- 1 file changed, 198 insertions(+), 125 deletions(-) (limited to 'prog/mutation.go') diff --git a/prog/mutation.go b/prog/mutation.go index dff40a8ec..7d521dd03 100644 --- a/prog/mutation.go +++ b/prog/mutation.go @@ -19,6 +19,34 @@ outer: for stop := false; !stop || retry; stop = r.oneOf(3) { retry = false switch { + case r.oneOf(5): + // Not all calls have anything squashable, + // so this has lower priority in reality. + complexPtrs := p.complexPtrs() + if len(complexPtrs) == 0 { + retry = true + continue + } + ptr := complexPtrs[r.Intn(len(complexPtrs))] + if !p.Target.isAnyPtr(ptr.Type()) { + p.Target.squashPtr(ptr, true) + } + var blobs []*DataArg + ForeachSubArg(ptr, func(arg Arg, _ *ArgCtx) { + if data, ok := arg.(*DataArg); ok && arg.Type().Dir() != DirOut { + blobs = append(blobs, data) + } + }) + if len(blobs) == 0 { + retry = true + continue + } + // TODO(dvyukov): we probably want special mutation for ANY. + // E.g. merging adjacent ANYBLOBs (we don't create them, + // but they can appear in future); or replacing ANYRES + // with a blob (and merging it with adjacent blobs). + arg := blobs[r.Intn(len(blobs))] + arg.data = mutateData(r, arg.Data(), 0, maxBlobLen) case r.nOutOf(1, 100): // Splice with another prog from corpus. if len(corpus) == 0 || len(p.Calls) == 0 { @@ -311,31 +339,9 @@ func mutateData(r *randGen, data []byte, minLen, maxLen uint64) []byte { loop: for stop := false; !stop || retry; stop = r.oneOf(3) { retry = false - switch r.Intn(14) { + // TODO(dvyukov): duplicate part of data. + switch r.Intn(7) { case 0: - // Append byte. - if uint64(len(data)) >= maxLen { - retry = true - continue loop - } - data = append(data, byte(r.rand(256))) - case 1: - // Remove byte. - if len(data) == 0 || uint64(len(data)) <= minLen { - retry = true - continue loop - } - i := r.Intn(len(data)) - copy(data[i:], data[i+1:]) - data = data[:len(data)-1] - case 2: - // Replace byte with random value. - if len(data) == 0 { - retry = true - continue loop - } - data[r.Intn(len(data))] = byte(r.rand(256)) - case 3: // Flip bit in byte. if len(data) == 0 { retry = true @@ -344,122 +350,49 @@ loop: byt := r.Intn(len(data)) bit := r.Intn(8) data[byt] ^= 1 << uint(bit) - case 4: - // Swap two bytes. - if len(data) < 2 { - retry = true - continue loop - } - i1 := r.Intn(len(data)) - i2 := r.Intn(len(data)) - data[i1], data[i2] = data[i2], data[i1] - case 5: - // Add / subtract from a byte. - if len(data) == 0 { - retry = true - continue loop - } - i := r.Intn(len(data)) - delta := byte(r.rand(2*maxInc+1) - maxInc) - if delta == 0 { - delta = 1 - } - data[i] += delta - case 6: - // Add / subtract from a uint16. - if len(data) < 2 { - retry = true - continue loop - } - i := r.Intn(len(data) - 1) - p := (*uint16)(unsafe.Pointer(&data[i])) - delta := uint16(r.rand(2*maxInc+1) - maxInc) - if delta == 0 { - delta = 1 - } - if r.bin() { - *p += delta - } else { - *p = swap16(swap16(*p) + delta) - } - case 7: - // Add / subtract from a uint32. - if len(data) < 4 { - retry = true - continue loop - } - i := r.Intn(len(data) - 3) - p := (*uint32)(unsafe.Pointer(&data[i])) - delta := uint32(r.rand(2*maxInc+1) - maxInc) - if delta == 0 { - delta = 1 - } - if r.bin() { - *p += delta - } else { - *p = swap32(swap32(*p) + delta) - } - case 8: - // Add / subtract from a uint64. - if len(data) < 8 { + case 1: + // Insert random bytes. + if len(data) == 0 || uint64(len(data)) >= maxLen { retry = true continue loop } - i := r.Intn(len(data) - 7) - p := (*uint64)(unsafe.Pointer(&data[i])) - delta := r.rand(2*maxInc+1) - maxInc - if delta == 0 { - delta = 1 - } - if r.bin() { - *p += delta - } else { - *p = swap64(swap64(*p) + delta) + n := r.Intn(16) + 1 + if r := int(maxLen) - len(data); n > r { + n = r } - case 9: - // Set byte to an interesting value. - if len(data) == 0 { - retry = true - continue loop + pos := r.Intn(len(data)) + for i := 0; i < n; i++ { + data = append(data, 0) } - data[r.Intn(len(data))] = byte(r.randInt()) - case 10: - // Set uint16 to an interesting value. - if len(data) < 2 { - retry = true - continue loop + copy(data[pos+n:], data[pos:]) + for i := 0; i < n; i++ { + data[pos+i] = byte(r.Int31()) } - i := r.Intn(len(data) - 1) - value := uint16(r.randInt()) if r.bin() { - value = swap16(value) + data = data[:len(data)-n] // preserve original length } - *(*uint16)(unsafe.Pointer(&data[i])) = value - case 11: - // Set uint32 to an interesting value. - if len(data) < 4 { + case 2: + // Remove bytes. + if uint64(len(data)) <= minLen { retry = true continue loop } - i := r.Intn(len(data) - 3) - value := uint32(r.randInt()) - if r.bin() { - value = swap32(value) + n := r.Intn(16) + 1 + if n > len(data) { + n = len(data) } - *(*uint32)(unsafe.Pointer(&data[i])) = value - case 12: - // Set uint64 to an interesting value. - if len(data) < 8 { - retry = true - continue loop + pos := 0 + if n < len(data) { + pos = r.Intn(len(data) - n) } - i := r.Intn(len(data) - 7) - value := r.randInt() + copy(data[pos:], data[pos+n:]) + data = data[:len(data)-n] if r.bin() { - value = swap64(value) + for i := 0; i < n; i++ { + data = append(data, 0) // preserve original length + } } - *(*uint64)(unsafe.Pointer(&data[i])) = value - case 13: + case 3: // Append a bunch of bytes. if uint64(len(data)) >= maxLen { retry = true @@ -473,6 +406,146 @@ loop: for i := 0; i < n; i++ { data = append(data, byte(r.rand(256))) } + case 4: + // Replace int8/int16/int32/int64 with a random value. + switch r.Intn(4) { + case 0: // int8 + if len(data) == 0 { + retry = true + continue loop + } + data[r.Intn(len(data))] = byte(r.rand(1 << 8)) + case 1: // int16 + if len(data) < 2 { + retry = true + continue loop + } + i := r.Intn(len(data) - 1) + p := (*uint16)(unsafe.Pointer(&data[i])) + *p = uint16(r.rand(1 << 16)) + case 2: // int32 + if len(data) < 4 { + retry = true + continue loop + } + i := r.Intn(len(data) - 3) + p := (*uint32)(unsafe.Pointer(&data[i])) + *p = uint32(r.rand(1 << 32)) + case 3: // int64 + if len(data) < 8 { + retry = true + continue loop + } + i := r.Intn(len(data) - 7) + p := (*uint64)(unsafe.Pointer(&data[i])) + *p = r.Uint64() + } + case 5: + // Add/subtract from an int8/int16/int32/int64. + switch r.Intn(4) { + case 0: // int8 + if len(data) == 0 { + retry = true + continue loop + } + i := r.Intn(len(data)) + delta := byte(r.rand(2*maxInc+1) - maxInc) + if delta == 0 { + delta = 1 + } + data[i] += delta + case 1: // int16 + if len(data) < 2 { + retry = true + continue loop + } + i := r.Intn(len(data) - 1) + p := (*uint16)(unsafe.Pointer(&data[i])) + delta := uint16(r.rand(2*maxInc+1) - maxInc) + if delta == 0 { + delta = 1 + } + if r.oneOf(10) { + *p = swap16(swap16(*p) + delta) + } else { + *p += delta + } + case 2: // int32 + if len(data) < 4 { + retry = true + continue loop + } + i := r.Intn(len(data) - 3) + p := (*uint32)(unsafe.Pointer(&data[i])) + delta := uint32(r.rand(2*maxInc+1) - maxInc) + if delta == 0 { + delta = 1 + } + if r.oneOf(10) { + *p = swap32(swap32(*p) + delta) + } else { + *p += delta + } + case 3: // int64 + if len(data) < 8 { + retry = true + continue loop + } + i := r.Intn(len(data) - 7) + p := (*uint64)(unsafe.Pointer(&data[i])) + delta := r.rand(2*maxInc+1) - maxInc + if delta == 0 { + delta = 1 + } + if r.oneOf(10) { + *p = swap64(swap64(*p) + delta) + } else { + *p += delta + } + } + case 6: + // Set int8/int16/int32/int64 to an interesting value. + switch r.Intn(4) { + case 0: // int8 + if len(data) == 0 { + retry = true + continue loop + } + data[r.Intn(len(data))] = byte(r.randInt()) + case 1: // int16 + if len(data) < 2 { + retry = true + continue loop + } + i := r.Intn(len(data) - 1) + value := uint16(r.randInt()) + if r.oneOf(10) { + value = swap16(value) + } + *(*uint16)(unsafe.Pointer(&data[i])) = value + case 2: // int32 + if len(data) < 4 { + retry = true + continue loop + } + i := r.Intn(len(data) - 3) + value := uint32(r.randInt()) + if r.oneOf(10) { + value = swap32(value) + } + *(*uint32)(unsafe.Pointer(&data[i])) = value + case 3: // int64 + if len(data) < 8 { + retry = true + continue loop + } + i := r.Intn(len(data) - 7) + value := r.randInt() + if r.oneOf(10) { + value = swap64(value) + } + *(*uint64)(unsafe.Pointer(&data[i])) = value + } default: panic("bad") } -- cgit mrf-deployment