sp_state_machine/
fuzzing.rs

1// This file is part of Substrate.
2
3// Copyright (C) Parity Technologies (UK) Ltd.
4// SPDX-License-Identifier: Apache-2.0
5
6// Licensed under the Apache License, Version 2.0 (the "License");
7// you may not use this file except in compliance with the License.
8// You may obtain a copy of the License at
9//
10// 	http://www.apache.org/licenses/LICENSE-2.0
11//
12// Unless required by applicable law or agreed to in writing, software
13// distributed under the License is distributed on an "AS IS" BASIS,
14// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15// See the License for the specific language governing permissions and
16// limitations under the License.
17
18//! State machine fuzzing implementation, behind `fuzzing` feature.
19
20use super::{ext::Ext, *};
21use crate::ext::StorageAppend;
22use arbitrary::Arbitrary;
23#[cfg(test)]
24use codec::Encode;
25use hash_db::Hasher;
26use sp_core::{storage::StateVersion, traits::Externalities};
27#[cfg(test)]
28use sp_runtime::traits::BlakeTwo256;
29use sp_trie::PrefixedMemoryDB;
30use std::collections::BTreeMap;
31
32#[derive(Arbitrary, Debug, Clone)]
33enum DataLength {
34	Zero = 0,
35	Small = 1,
36	Medium = 3,
37	Big = 300, // 2 byte scale encode length
38}
39
40#[derive(Arbitrary, Debug, Clone)]
41#[repr(u8)]
42enum DataValue {
43	A = b'a',
44	B = b'b',
45	C = b'c',
46	D = b'd',       // This can be read as a multiple byte compact length.
47	EasyBug = 20u8, // value compact len.
48}
49
50/// Action to fuzz
51#[derive(Arbitrary, Debug, Clone)]
52enum FuzzAppendItem {
53	Append(DataValue, DataLength),
54	Insert(DataValue, DataLength),
55	StartTransaction,
56	RollbackTransaction,
57	CommitTransaction,
58	Read,
59	Remove,
60	// To go over 256 items easily (different compact size then).
61	Append50(DataValue, DataLength),
62}
63
64/// Arbitrary payload for fuzzing append.
65#[derive(Arbitrary, Debug, Clone)]
66pub struct FuzzAppendPayload(Vec<FuzzAppendItem>, Option<(DataValue, DataLength)>);
67
68struct SimpleOverlay {
69	data: Vec<BTreeMap<Vec<u8>, Option<Vec<u8>>>>,
70}
71
72impl Default for SimpleOverlay {
73	fn default() -> Self {
74		Self { data: vec![BTreeMap::new()] }
75	}
76}
77
78impl SimpleOverlay {
79	fn insert(&mut self, key: Vec<u8>, value: Option<Vec<u8>>) {
80		self.data.last_mut().expect("always at least one item").insert(key, value);
81	}
82
83	fn append<H>(
84		&mut self,
85		key: Vec<u8>,
86		value: Vec<u8>,
87		backend: &mut TrieBackend<PrefixedMemoryDB<H>, H>,
88	) where
89		H: Hasher,
90		H::Out: codec::Decode + codec::Encode + 'static,
91	{
92		let current_value = self
93			.data
94			.last_mut()
95			.expect("always at least one item")
96			.entry(key.clone())
97			.or_insert_with(|| {
98				Some(backend.storage(&key).expect("Ext not allowed to fail").unwrap_or_default())
99			});
100		if current_value.is_none() {
101			*current_value = Some(vec![]);
102		}
103		StorageAppend::new(current_value.as_mut().expect("init above")).append(value);
104	}
105
106	fn get(&mut self, key: &[u8]) -> Option<&Vec<u8>> {
107		self.data
108			.last_mut()
109			.expect("always at least one item")
110			.get(key)
111			.and_then(|o| o.as_ref())
112	}
113
114	fn commit_transaction(&mut self) {
115		if let Some(to_commit) = self.data.pop() {
116			let dest = self.data.last_mut().expect("always at least one item");
117			for (k, v) in to_commit.into_iter() {
118				dest.insert(k, v);
119			}
120		}
121	}
122
123	fn rollback_transaction(&mut self) {
124		let _ = self.data.pop();
125	}
126
127	fn start_transaction(&mut self) {
128		let cloned = self.data.last().expect("always at least one item").clone();
129		self.data.push(cloned);
130	}
131}
132
133struct FuzzAppendState<H: Hasher> {
134	key: Vec<u8>,
135
136	// reference simple implementation
137	reference: SimpleOverlay,
138
139	// trie backend
140	backend: TrieBackend<PrefixedMemoryDB<H>, H>,
141	// Standard Overlay
142	overlay: OverlayedChanges<H>,
143
144	// block dropping/commiting too many transaction
145	transaction_depth: usize,
146}
147
148impl<H> FuzzAppendState<H>
149where
150	H: Hasher,
151	H::Out: codec::Decode + codec::Encode + 'static,
152{
153	fn process_item(&mut self, item: FuzzAppendItem) {
154		let mut ext = Ext::new(&mut self.overlay, &mut self.backend, None);
155		match item {
156			FuzzAppendItem::Append(value, length) => {
157				let value = vec![value as u8; length as usize];
158				ext.storage_append(self.key.clone(), value.clone());
159				self.reference.append(self.key.clone(), value, &mut self.backend);
160			},
161			FuzzAppendItem::Append50(value, length) => {
162				let value = vec![value as u8; length as usize];
163				for _ in 0..50 {
164					let mut ext = Ext::new(&mut self.overlay, &mut self.backend, None);
165					ext.storage_append(self.key.clone(), value.clone());
166					self.reference.append(self.key.clone(), value.clone(), &mut self.backend);
167				}
168			},
169			FuzzAppendItem::Insert(value, length) => {
170				let value = vec![value as u8; length as usize];
171				ext.set_storage(self.key.clone(), value.clone());
172				self.reference.insert(self.key.clone(), Some(value));
173			},
174			FuzzAppendItem::Remove => {
175				ext.clear_storage(&self.key);
176				self.reference.insert(self.key.clone(), None);
177			},
178			FuzzAppendItem::Read => {
179				let left = ext.storage(self.key.as_slice());
180				let right = self.reference.get(self.key.as_slice());
181				assert_eq!(left.as_ref(), right);
182			},
183			FuzzAppendItem::StartTransaction => {
184				self.transaction_depth += 1;
185				self.reference.start_transaction();
186				ext.storage_start_transaction();
187			},
188			FuzzAppendItem::RollbackTransaction => {
189				if self.transaction_depth == 0 {
190					return
191				}
192				self.transaction_depth -= 1;
193				self.reference.rollback_transaction();
194				ext.storage_rollback_transaction().unwrap();
195			},
196			FuzzAppendItem::CommitTransaction => {
197				if self.transaction_depth == 0 {
198					return
199				}
200				self.transaction_depth -= 1;
201				self.reference.commit_transaction();
202				ext.storage_commit_transaction().unwrap();
203			},
204		}
205	}
206
207	fn check_final_state(&mut self) {
208		let mut ext = Ext::new(&mut self.overlay, &mut self.backend, None);
209		let left = ext.storage(self.key.as_slice());
210		let right = self.reference.get(self.key.as_slice());
211		assert_eq!(left.as_ref(), right);
212	}
213}
214
215#[test]
216fn fuzz_scenarii() {
217	assert_eq!(codec::Compact(5u16).encode()[0], DataValue::EasyBug as u8);
218	let scenarii = vec![
219		(
220			vec![
221				FuzzAppendItem::Append(DataValue::A, DataLength::Small),
222				FuzzAppendItem::StartTransaction,
223				FuzzAppendItem::Append50(DataValue::D, DataLength::Small),
224				FuzzAppendItem::Read,
225				FuzzAppendItem::RollbackTransaction,
226				FuzzAppendItem::StartTransaction,
227				FuzzAppendItem::Append(DataValue::D, DataLength::Small),
228				FuzzAppendItem::Read,
229				FuzzAppendItem::RollbackTransaction,
230			],
231			Some((DataValue::D, DataLength::Small)),
232		),
233		(
234			vec![
235				FuzzAppendItem::Append(DataValue::B, DataLength::Small),
236				FuzzAppendItem::StartTransaction,
237				FuzzAppendItem::Append(DataValue::A, DataLength::Small),
238				FuzzAppendItem::StartTransaction,
239				FuzzAppendItem::Remove,
240				FuzzAppendItem::StartTransaction,
241				FuzzAppendItem::Append(DataValue::A, DataLength::Zero),
242				FuzzAppendItem::CommitTransaction,
243				FuzzAppendItem::CommitTransaction,
244				FuzzAppendItem::Remove,
245			],
246			Some((DataValue::EasyBug, DataLength::Small)),
247		),
248		(
249			vec![
250				FuzzAppendItem::Append(DataValue::A, DataLength::Small),
251				FuzzAppendItem::StartTransaction,
252				FuzzAppendItem::Append(DataValue::A, DataLength::Medium),
253				FuzzAppendItem::StartTransaction,
254				FuzzAppendItem::Remove,
255				FuzzAppendItem::CommitTransaction,
256				FuzzAppendItem::RollbackTransaction,
257			],
258			Some((DataValue::B, DataLength::Big)),
259		),
260		(
261			vec![
262				FuzzAppendItem::Append(DataValue::A, DataLength::Big),
263				FuzzAppendItem::StartTransaction,
264				FuzzAppendItem::Append(DataValue::A, DataLength::Medium),
265				FuzzAppendItem::Remove,
266				FuzzAppendItem::RollbackTransaction,
267				FuzzAppendItem::StartTransaction,
268				FuzzAppendItem::Append(DataValue::A, DataLength::Zero),
269			],
270			None,
271		),
272		(
273			vec![
274				FuzzAppendItem::StartTransaction,
275				FuzzAppendItem::RollbackTransaction,
276				FuzzAppendItem::RollbackTransaction,
277				FuzzAppendItem::Append(DataValue::A, DataLength::Zero),
278			],
279			None,
280		),
281		(vec![FuzzAppendItem::StartTransaction], Some((DataValue::EasyBug, DataLength::Zero))),
282	];
283
284	for (scenario, init) in scenarii.into_iter() {
285		fuzz_append::<BlakeTwo256>(FuzzAppendPayload(scenario, init));
286	}
287}
288
289/// Test append operation for a given fuzzing payload.
290pub fn fuzz_append<H>(payload: FuzzAppendPayload)
291where
292	H: Hasher,
293	H::Out: codec::Decode + codec::Encode + 'static,
294{
295	let FuzzAppendPayload(to_fuzz, initial) = payload;
296	let key = b"k".to_vec();
297	let mut reference = SimpleOverlay::default();
298	let initial: BTreeMap<_, _> = initial
299		.into_iter()
300		.map(|(v, l)| (key.clone(), vec![v as u8; l as usize]))
301		.collect();
302	for (k, v) in initial.iter() {
303		reference.data[0].insert(k.clone(), Some(v.clone()));
304	}
305	reference.start_transaction(); // level 0 is backend, keep it untouched.
306	let overlay = OverlayedChanges::default();
307
308	let mut state = FuzzAppendState::<H> {
309		key,
310		reference,
311		overlay,
312		backend: (initial, StateVersion::default()).into(),
313		transaction_depth: 0,
314	};
315	for item in to_fuzz {
316		state.process_item(item);
317	}
318	state.check_final_state();
319}
sp_state_machine/fuzzing.rs

sp_state_machine/
fuzzing.rs
