123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199 |
- // Copyright 2020 The go-ethereum Authors
- // This file is part of the go-ethereum library.
- //
- // The go-ethereum library is free software: you can redistribute it and/or modify
- // it under the terms of the GNU Lesser General Public License as published by
- // the Free Software Foundation, either version 3 of the License, or
- // (at your option) any later version.
- //
- // The go-ethereum library is distributed in the hope that it will be useful,
- // but WITHOUT ANY WARRANTY; without even the implied warranty of
- // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
- // GNU Lesser General Public License for more details.
- //
- // You should have received a copy of the GNU Lesser General Public License
- // along with the go-ethereum library. If not, see <http://www.gnu.org/licenses/>.
- package rangeproof
- import (
- "bytes"
- "encoding/binary"
- "fmt"
- "io"
- "sort"
- "github.com/ethereum/go-ethereum/common"
- "github.com/ethereum/go-ethereum/ethdb/memorydb"
- "github.com/ethereum/go-ethereum/trie"
- )
- type kv struct {
- k, v []byte
- t bool
- }
- type entrySlice []*kv
- func (p entrySlice) Len() int { return len(p) }
- func (p entrySlice) Less(i, j int) bool { return bytes.Compare(p[i].k, p[j].k) < 0 }
- func (p entrySlice) Swap(i, j int) { p[i], p[j] = p[j], p[i] }
- type fuzzer struct {
- input io.Reader
- exhausted bool
- }
- func (f *fuzzer) randBytes(n int) []byte {
- r := make([]byte, n)
- if _, err := f.input.Read(r); err != nil {
- f.exhausted = true
- }
- return r
- }
- func (f *fuzzer) readInt() uint64 {
- var x uint64
- if err := binary.Read(f.input, binary.LittleEndian, &x); err != nil {
- f.exhausted = true
- }
- return x
- }
- func (f *fuzzer) randomTrie(n int) (*trie.Trie, map[string]*kv) {
- trie := new(trie.Trie)
- vals := make(map[string]*kv)
- size := f.readInt()
- // Fill it with some fluff
- for i := byte(0); i < byte(size); i++ {
- value := &kv{common.LeftPadBytes([]byte{i}, 32), []byte{i}, false}
- value2 := &kv{common.LeftPadBytes([]byte{i + 10}, 32), []byte{i}, false}
- trie.Update(value.k, value.v)
- trie.Update(value2.k, value2.v)
- vals[string(value.k)] = value
- vals[string(value2.k)] = value2
- }
- if f.exhausted {
- return nil, nil
- }
- // And now fill with some random
- for i := 0; i < n; i++ {
- k := f.randBytes(32)
- v := f.randBytes(20)
- value := &kv{k, v, false}
- trie.Update(k, v)
- vals[string(k)] = value
- if f.exhausted {
- return nil, nil
- }
- }
- return trie, vals
- }
- func (f *fuzzer) fuzz() int {
- maxSize := 200
- tr, vals := f.randomTrie(1 + int(f.readInt())%maxSize)
- if f.exhausted {
- return 0 // input too short
- }
- var entries entrySlice
- for _, kv := range vals {
- entries = append(entries, kv)
- }
- if len(entries) <= 1 {
- return 0
- }
- sort.Sort(entries)
- var ok = 0
- for {
- start := int(f.readInt() % uint64(len(entries)))
- end := 1 + int(f.readInt()%uint64(len(entries)-1))
- testcase := int(f.readInt() % uint64(6))
- index := int(f.readInt() & 0xFFFFFFFF)
- index2 := int(f.readInt() & 0xFFFFFFFF)
- if f.exhausted {
- break
- }
- proof := memorydb.New()
- if err := tr.Prove(entries[start].k, 0, proof); err != nil {
- panic(fmt.Sprintf("Failed to prove the first node %v", err))
- }
- if err := tr.Prove(entries[end-1].k, 0, proof); err != nil {
- panic(fmt.Sprintf("Failed to prove the last node %v", err))
- }
- var keys [][]byte
- var vals [][]byte
- for i := start; i < end; i++ {
- keys = append(keys, entries[i].k)
- vals = append(vals, entries[i].v)
- }
- if len(keys) == 0 {
- return 0
- }
- var first, last = keys[0], keys[len(keys)-1]
- testcase %= 6
- switch testcase {
- case 0:
- // Modified key
- keys[index%len(keys)] = f.randBytes(32) // In theory it can't be same
- case 1:
- // Modified val
- vals[index%len(vals)] = f.randBytes(20) // In theory it can't be same
- case 2:
- // Gapped entry slice
- index = index % len(keys)
- keys = append(keys[:index], keys[index+1:]...)
- vals = append(vals[:index], vals[index+1:]...)
- case 3:
- // Out of order
- index1 := index % len(keys)
- index2 := index2 % len(keys)
- keys[index1], keys[index2] = keys[index2], keys[index1]
- vals[index1], vals[index2] = vals[index2], vals[index1]
- case 4:
- // Set random key to nil, do nothing
- keys[index%len(keys)] = nil
- case 5:
- // Set random value to nil, deletion
- vals[index%len(vals)] = nil
- // Other cases:
- // Modify something in the proof db
- // add stuff to proof db
- // drop stuff from proof db
- }
- if f.exhausted {
- break
- }
- ok = 1
- //nodes, subtrie
- hasMore, err := trie.VerifyRangeProof(tr.Hash(), first, last, keys, vals, proof)
- if err != nil {
- if hasMore {
- panic("err != nil && hasMore == true")
- }
- }
- }
- return ok
- }
- // The function must return
- // 1 if the fuzzer should increase priority of the
- // given input during subsequent fuzzing (for example, the input is lexically
- // correct and was parsed successfully);
- // -1 if the input must not be added to corpus even if gives new coverage; and
- // 0 otherwise; other values are reserved for future use.
- func Fuzz(input []byte) int {
- if len(input) < 100 {
- return 0
- }
- r := bytes.NewReader(input)
- f := fuzzer{
- input: r,
- exhausted: false,
- }
- return f.fuzz()
- }
|