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