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, StateVersion::default());
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(
165						&mut self.overlay,
166						&mut self.backend,
167						None,
168						StateVersion::default(),
169					);
170					ext.storage_append(self.key.clone(), value.clone());
171					self.reference.append(self.key.clone(), value.clone(), &mut self.backend);
172				}
173			},
174			FuzzAppendItem::Insert(value, length) => {
175				let value = vec![value as u8; length as usize];
176				ext.set_storage(self.key.clone(), value.clone());
177				self.reference.insert(self.key.clone(), Some(value));
178			},
179			FuzzAppendItem::Remove => {
180				ext.clear_storage(&self.key);
181				self.reference.insert(self.key.clone(), None);
182			},
183			FuzzAppendItem::Read => {
184				let left = ext.storage(self.key.as_slice());
185				let right = self.reference.get(self.key.as_slice());
186				assert_eq!(left.as_ref(), right);
187			},
188			FuzzAppendItem::StartTransaction => {
189				self.transaction_depth += 1;
190				self.reference.start_transaction();
191				ext.storage_start_transaction();
192			},
193			FuzzAppendItem::RollbackTransaction => {
194				if self.transaction_depth == 0 {
195					return;
196				}
197				self.transaction_depth -= 1;
198				self.reference.rollback_transaction();
199				ext.storage_rollback_transaction().unwrap();
200			},
201			FuzzAppendItem::CommitTransaction => {
202				if self.transaction_depth == 0 {
203					return;
204				}
205				self.transaction_depth -= 1;
206				self.reference.commit_transaction();
207				ext.storage_commit_transaction().unwrap();
208			},
209		}
210	}
211
212	fn check_final_state(&mut self) {
213		let mut ext = Ext::new(&mut self.overlay, &mut self.backend, None, StateVersion::default());
214		let left = ext.storage(self.key.as_slice());
215		let right = self.reference.get(self.key.as_slice());
216		assert_eq!(left.as_ref(), right);
217	}
218}
219
220#[test]
221fn fuzz_scenarii() {
222	assert_eq!(codec::Compact(5u16).encode()[0], DataValue::EasyBug as u8);
223	let scenarii = vec![
224		(
225			vec![
226				FuzzAppendItem::Append(DataValue::A, DataLength::Small),
227				FuzzAppendItem::StartTransaction,
228				FuzzAppendItem::Append50(DataValue::D, DataLength::Small),
229				FuzzAppendItem::Read,
230				FuzzAppendItem::RollbackTransaction,
231				FuzzAppendItem::StartTransaction,
232				FuzzAppendItem::Append(DataValue::D, DataLength::Small),
233				FuzzAppendItem::Read,
234				FuzzAppendItem::RollbackTransaction,
235			],
236			Some((DataValue::D, DataLength::Small)),
237		),
238		(
239			vec![
240				FuzzAppendItem::Append(DataValue::B, DataLength::Small),
241				FuzzAppendItem::StartTransaction,
242				FuzzAppendItem::Append(DataValue::A, DataLength::Small),
243				FuzzAppendItem::StartTransaction,
244				FuzzAppendItem::Remove,
245				FuzzAppendItem::StartTransaction,
246				FuzzAppendItem::Append(DataValue::A, DataLength::Zero),
247				FuzzAppendItem::CommitTransaction,
248				FuzzAppendItem::CommitTransaction,
249				FuzzAppendItem::Remove,
250			],
251			Some((DataValue::EasyBug, DataLength::Small)),
252		),
253		(
254			vec![
255				FuzzAppendItem::Append(DataValue::A, DataLength::Small),
256				FuzzAppendItem::StartTransaction,
257				FuzzAppendItem::Append(DataValue::A, DataLength::Medium),
258				FuzzAppendItem::StartTransaction,
259				FuzzAppendItem::Remove,
260				FuzzAppendItem::CommitTransaction,
261				FuzzAppendItem::RollbackTransaction,
262			],
263			Some((DataValue::B, DataLength::Big)),
264		),
265		(
266			vec![
267				FuzzAppendItem::Append(DataValue::A, DataLength::Big),
268				FuzzAppendItem::StartTransaction,
269				FuzzAppendItem::Append(DataValue::A, DataLength::Medium),
270				FuzzAppendItem::Remove,
271				FuzzAppendItem::RollbackTransaction,
272				FuzzAppendItem::StartTransaction,
273				FuzzAppendItem::Append(DataValue::A, DataLength::Zero),
274			],
275			None,
276		),
277		(
278			vec![
279				FuzzAppendItem::StartTransaction,
280				FuzzAppendItem::RollbackTransaction,
281				FuzzAppendItem::RollbackTransaction,
282				FuzzAppendItem::Append(DataValue::A, DataLength::Zero),
283			],
284			None,
285		),
286		(vec![FuzzAppendItem::StartTransaction], Some((DataValue::EasyBug, DataLength::Zero))),
287	];
288
289	for (scenario, init) in scenarii.into_iter() {
290		fuzz_append::<BlakeTwo256>(FuzzAppendPayload(scenario, init));
291	}
292}
293
294/// Test append operation for a given fuzzing payload.
295pub fn fuzz_append<H>(payload: FuzzAppendPayload)
296where
297	H: Hasher,
298	H::Out: codec::Decode + codec::Encode + 'static,
299{
300	let FuzzAppendPayload(to_fuzz, initial) = payload;
301	let key = b"k".to_vec();
302	let mut reference = SimpleOverlay::default();
303	let initial: BTreeMap<_, _> = initial
304		.into_iter()
305		.map(|(v, l)| (key.clone(), vec![v as u8; l as usize]))
306		.collect();
307	for (k, v) in initial.iter() {
308		reference.data[0].insert(k.clone(), Some(v.clone()));
309	}
310	reference.start_transaction(); // level 0 is backend, keep it untouched.
311	let overlay = OverlayedChanges::default();
312
313	let mut state = FuzzAppendState::<H> {
314		key,
315		reference,
316		overlay,
317		backend: (initial, StateVersion::default()).into(),
318		transaction_depth: 0,
319	};
320	for item in to_fuzz {
321		state.process_item(item);
322	}
323	state.check_final_state();
324}
sp_state_machine/fuzzing.rs

sp_state_machine/
fuzzing.rs
