1// Copyright 2019 The go-ethereum Authors 2// This file is part of the go-ethereum library. 3// 4// The go-ethereum library is free software: you can redistribute it and/or modify 5// it under the terms of the GNU Lesser General Public License as published by 6// the Free Software Foundation, either version 3 of the License, or 7// (at your option) any later version. 8// 9// The go-ethereum library is distributed in the hope that it will be useful, 10// but WITHOUT ANY WARRANTY; without even the implied warranty of 11// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 12// GNU Lesser General Public License for more details. 13// 14// You should have received a copy of the GNU Lesser General Public License 15// along with the go-ethereum library. If not, see <http://www.gnu.org/licenses/>. 16 17package trie 18 19import ( 20 "bytes" 21 "encoding/binary" 22 "fmt" 23 24 "github.com/ethereum/go-ethereum/common" 25 "github.com/ethereum/go-ethereum/ethdb/memorydb" 26 "github.com/ethereum/go-ethereum/trie" 27) 28 29// randTest performs random trie operations. 30// Instances of this test are created by Generate. 31type randTest []randTestStep 32 33type randTestStep struct { 34 op int 35 key []byte // for opUpdate, opDelete, opGet 36 value []byte // for opUpdate 37 err error // for debugging 38} 39 40type proofDb struct{} 41 42func (proofDb) Put(key []byte, value []byte) error { 43 return nil 44} 45 46func (proofDb) Delete(key []byte) error { 47 return nil 48} 49 50const ( 51 opUpdate = iota 52 opDelete 53 opGet 54 opCommit 55 opHash 56 opReset 57 opItercheckhash 58 opProve 59 opMax // boundary value, not an actual op 60) 61 62type dataSource struct { 63 input []byte 64 reader *bytes.Reader 65} 66 67func newDataSource(input []byte) *dataSource { 68 return &dataSource{ 69 input, bytes.NewReader(input), 70 } 71} 72func (ds *dataSource) readByte() byte { 73 if b, err := ds.reader.ReadByte(); err != nil { 74 return 0 75 } else { 76 return b 77 } 78} 79func (ds *dataSource) Read(buf []byte) (int, error) { 80 return ds.reader.Read(buf) 81} 82func (ds *dataSource) Ended() bool { 83 return ds.reader.Len() == 0 84} 85 86func Generate(input []byte) randTest { 87 88 var allKeys [][]byte 89 r := newDataSource(input) 90 genKey := func() []byte { 91 92 if len(allKeys) < 2 || r.readByte() < 0x0f { 93 // new key 94 key := make([]byte, r.readByte()%50) 95 r.Read(key) 96 allKeys = append(allKeys, key) 97 return key 98 } 99 // use existing key 100 return allKeys[int(r.readByte())%len(allKeys)] 101 } 102 103 var steps randTest 104 105 for i := 0; !r.Ended(); i++ { 106 107 step := randTestStep{op: int(r.readByte()) % opMax} 108 switch step.op { 109 case opUpdate: 110 step.key = genKey() 111 step.value = make([]byte, 8) 112 binary.BigEndian.PutUint64(step.value, uint64(i)) 113 case opGet, opDelete, opProve: 114 step.key = genKey() 115 } 116 steps = append(steps, step) 117 if len(steps) > 500 { 118 break 119 } 120 } 121 122 return steps 123} 124 125// The function must return 126// 1 if the fuzzer should increase priority of the 127// given input during subsequent fuzzing (for example, the input is lexically 128// correct and was parsed successfully); 129// -1 if the input must not be added to corpus even if gives new coverage; and 130// 0 otherwise 131// other values are reserved for future use. 132func Fuzz(input []byte) int { 133 program := Generate(input) 134 if len(program) == 0 { 135 return 0 136 } 137 if err := runRandTest(program); err != nil { 138 panic(err) 139 } 140 return 1 141} 142 143func runRandTest(rt randTest) error { 144 145 triedb := trie.NewDatabase(memorydb.New()) 146 147 tr, _ := trie.New(common.Hash{}, triedb) 148 values := make(map[string]string) // tracks content of the trie 149 150 for i, step := range rt { 151 switch step.op { 152 case opUpdate: 153 tr.Update(step.key, step.value) 154 values[string(step.key)] = string(step.value) 155 case opDelete: 156 tr.Delete(step.key) 157 delete(values, string(step.key)) 158 case opGet: 159 v := tr.Get(step.key) 160 want := values[string(step.key)] 161 if string(v) != want { 162 rt[i].err = fmt.Errorf("mismatch for key 0x%x, got 0x%x want 0x%x", step.key, v, want) 163 } 164 case opCommit: 165 _, _, rt[i].err = tr.Commit(nil) 166 case opHash: 167 tr.Hash() 168 case opReset: 169 hash, _, err := tr.Commit(nil) 170 if err != nil { 171 return err 172 } 173 newtr, err := trie.New(hash, triedb) 174 if err != nil { 175 return err 176 } 177 tr = newtr 178 case opItercheckhash: 179 checktr, _ := trie.New(common.Hash{}, triedb) 180 it := trie.NewIterator(tr.NodeIterator(nil)) 181 for it.Next() { 182 checktr.Update(it.Key, it.Value) 183 } 184 if tr.Hash() != checktr.Hash() { 185 return fmt.Errorf("hash mismatch in opItercheckhash") 186 } 187 case opProve: 188 rt[i].err = tr.Prove(step.key, 0, proofDb{}) 189 } 190 // Abort the test on error. 191 if rt[i].err != nil { 192 return rt[i].err 193 } 194 } 195 return nil 196} 197