From e64b5d9d2e6252954dce095989c1d55e7003299a Mon Sep 17 00:00:00 2001 From: Matt Corallo Date: Thu, 19 Jan 2023 20:24:22 +0000 Subject: [PATCH] Add a fuzzer to check that `IndexedMap` is equivalent to `BTreeMap` --- fuzz/src/bin/gen_target.sh | 1 + fuzz/src/bin/indexedmap_target.rs | 113 +++++++++++++++++ fuzz/src/bin/msg_channel_details_target.rs | 113 +++++++++++++++++ fuzz/src/indexedmap.rs | 137 +++++++++++++++++++++ fuzz/src/lib.rs | 1 + fuzz/targets.h | 1 + 6 files changed, 366 insertions(+) create mode 100644 fuzz/src/bin/indexedmap_target.rs create mode 100644 fuzz/src/bin/msg_channel_details_target.rs create mode 100644 fuzz/src/indexedmap.rs diff --git a/fuzz/src/bin/gen_target.sh b/fuzz/src/bin/gen_target.sh index 95e65695e..fa29540f9 100755 --- a/fuzz/src/bin/gen_target.sh +++ b/fuzz/src/bin/gen_target.sh @@ -14,6 +14,7 @@ GEN_TEST peer_crypt GEN_TEST process_network_graph GEN_TEST router GEN_TEST zbase32 +GEN_TEST indexedmap GEN_TEST msg_accept_channel msg_targets:: GEN_TEST msg_announcement_signatures msg_targets:: diff --git a/fuzz/src/bin/indexedmap_target.rs b/fuzz/src/bin/indexedmap_target.rs new file mode 100644 index 000000000..238566d54 --- /dev/null +++ b/fuzz/src/bin/indexedmap_target.rs @@ -0,0 +1,113 @@ +// This file is Copyright its original authors, visible in version control +// history. +// +// This file is licensed under the Apache License, Version 2.0 or the MIT license +// , at your option. +// You may not use this file except in accordance with one or both of these +// licenses. + +// This file is auto-generated by gen_target.sh based on target_template.txt +// To modify it, modify target_template.txt and run gen_target.sh instead. + +#![cfg_attr(feature = "libfuzzer_fuzz", no_main)] + +#[cfg(not(fuzzing))] +compile_error!("Fuzz targets need cfg=fuzzing"); + +extern crate lightning_fuzz; +use lightning_fuzz::indexedmap::*; + +#[cfg(feature = "afl")] +#[macro_use] extern crate afl; +#[cfg(feature = "afl")] +fn main() { + fuzz!(|data| { + indexedmap_run(data.as_ptr(), data.len()); + }); +} + +#[cfg(feature = "honggfuzz")] +#[macro_use] extern crate honggfuzz; +#[cfg(feature = "honggfuzz")] +fn main() { + loop { + fuzz!(|data| { + indexedmap_run(data.as_ptr(), data.len()); + }); + } +} + +#[cfg(feature = "libfuzzer_fuzz")] +#[macro_use] extern crate libfuzzer_sys; +#[cfg(feature = "libfuzzer_fuzz")] +fuzz_target!(|data: &[u8]| { + indexedmap_run(data.as_ptr(), data.len()); +}); + +#[cfg(feature = "stdin_fuzz")] +fn main() { + use std::io::Read; + + let mut data = Vec::with_capacity(8192); + std::io::stdin().read_to_end(&mut data).unwrap(); + indexedmap_run(data.as_ptr(), data.len()); +} + +#[test] +fn run_test_cases() { + use std::fs; + use std::io::Read; + use lightning_fuzz::utils::test_logger::StringBuffer; + + use std::sync::{atomic, Arc}; + { + let data: Vec = vec![0]; + indexedmap_run(data.as_ptr(), data.len()); + } + let mut threads = Vec::new(); + let threads_running = Arc::new(atomic::AtomicUsize::new(0)); + if let Ok(tests) = fs::read_dir("test_cases/indexedmap") { + for test in tests { + let mut data: Vec = Vec::new(); + let path = test.unwrap().path(); + fs::File::open(&path).unwrap().read_to_end(&mut data).unwrap(); + threads_running.fetch_add(1, atomic::Ordering::AcqRel); + + let thread_count_ref = Arc::clone(&threads_running); + let main_thread_ref = std::thread::current(); + threads.push((path.file_name().unwrap().to_str().unwrap().to_string(), + std::thread::spawn(move || { + let string_logger = StringBuffer::new(); + + let panic_logger = string_logger.clone(); + let res = if ::std::panic::catch_unwind(move || { + indexedmap_test(&data, panic_logger); + }).is_err() { + Some(string_logger.into_string()) + } else { None }; + thread_count_ref.fetch_sub(1, atomic::Ordering::AcqRel); + main_thread_ref.unpark(); + res + }) + )); + while threads_running.load(atomic::Ordering::Acquire) > 32 { + std::thread::park(); + } + } + } + let mut failed_outputs = Vec::new(); + for (test, thread) in threads.drain(..) { + if let Some(output) = thread.join().unwrap() { + println!("\nOutput of {}:\n{}\n", test, output); + failed_outputs.push(test); + } + } + if !failed_outputs.is_empty() { + println!("Test cases which failed: "); + for case in failed_outputs { + println!("{}", case); + } + panic!(); + } +} diff --git a/fuzz/src/bin/msg_channel_details_target.rs b/fuzz/src/bin/msg_channel_details_target.rs new file mode 100644 index 000000000..cb5021aed --- /dev/null +++ b/fuzz/src/bin/msg_channel_details_target.rs @@ -0,0 +1,113 @@ +// This file is Copyright its original authors, visible in version control +// history. +// +// This file is licensed under the Apache License, Version 2.0 or the MIT license +// , at your option. +// You may not use this file except in accordance with one or both of these +// licenses. + +// This file is auto-generated by gen_target.sh based on target_template.txt +// To modify it, modify target_template.txt and run gen_target.sh instead. + +#![cfg_attr(feature = "libfuzzer_fuzz", no_main)] + +#[cfg(not(fuzzing))] +compile_error!("Fuzz targets need cfg=fuzzing"); + +extern crate lightning_fuzz; +use lightning_fuzz::msg_targets::msg_channel_details::*; + +#[cfg(feature = "afl")] +#[macro_use] extern crate afl; +#[cfg(feature = "afl")] +fn main() { + fuzz!(|data| { + msg_channel_details_run(data.as_ptr(), data.len()); + }); +} + +#[cfg(feature = "honggfuzz")] +#[macro_use] extern crate honggfuzz; +#[cfg(feature = "honggfuzz")] +fn main() { + loop { + fuzz!(|data| { + msg_channel_details_run(data.as_ptr(), data.len()); + }); + } +} + +#[cfg(feature = "libfuzzer_fuzz")] +#[macro_use] extern crate libfuzzer_sys; +#[cfg(feature = "libfuzzer_fuzz")] +fuzz_target!(|data: &[u8]| { + msg_channel_details_run(data.as_ptr(), data.len()); +}); + +#[cfg(feature = "stdin_fuzz")] +fn main() { + use std::io::Read; + + let mut data = Vec::with_capacity(8192); + std::io::stdin().read_to_end(&mut data).unwrap(); + msg_channel_details_run(data.as_ptr(), data.len()); +} + +#[test] +fn run_test_cases() { + use std::fs; + use std::io::Read; + use lightning_fuzz::utils::test_logger::StringBuffer; + + use std::sync::{atomic, Arc}; + { + let data: Vec = vec![0]; + msg_channel_details_run(data.as_ptr(), data.len()); + } + let mut threads = Vec::new(); + let threads_running = Arc::new(atomic::AtomicUsize::new(0)); + if let Ok(tests) = fs::read_dir("test_cases/msg_channel_details") { + for test in tests { + let mut data: Vec = Vec::new(); + let path = test.unwrap().path(); + fs::File::open(&path).unwrap().read_to_end(&mut data).unwrap(); + threads_running.fetch_add(1, atomic::Ordering::AcqRel); + + let thread_count_ref = Arc::clone(&threads_running); + let main_thread_ref = std::thread::current(); + threads.push((path.file_name().unwrap().to_str().unwrap().to_string(), + std::thread::spawn(move || { + let string_logger = StringBuffer::new(); + + let panic_logger = string_logger.clone(); + let res = if ::std::panic::catch_unwind(move || { + msg_channel_details_test(&data, panic_logger); + }).is_err() { + Some(string_logger.into_string()) + } else { None }; + thread_count_ref.fetch_sub(1, atomic::Ordering::AcqRel); + main_thread_ref.unpark(); + res + }) + )); + while threads_running.load(atomic::Ordering::Acquire) > 32 { + std::thread::park(); + } + } + } + let mut failed_outputs = Vec::new(); + for (test, thread) in threads.drain(..) { + if let Some(output) = thread.join().unwrap() { + println!("\nOutput of {}:\n{}\n", test, output); + failed_outputs.push(test); + } + } + if !failed_outputs.is_empty() { + println!("Test cases which failed: "); + for case in failed_outputs { + println!("{}", case); + } + panic!(); + } +} diff --git a/fuzz/src/indexedmap.rs b/fuzz/src/indexedmap.rs new file mode 100644 index 000000000..795d6175b --- /dev/null +++ b/fuzz/src/indexedmap.rs @@ -0,0 +1,137 @@ +// This file is Copyright its original authors, visible in version control +// history. +// +// This file is licensed under the Apache License, Version 2.0 or the MIT license +// , at your option. +// You may not use this file except in accordance with one or both of these +// licenses. + +use lightning::util::indexed_map::{IndexedMap, self}; +use std::collections::{BTreeMap, btree_map}; +use hashbrown::HashSet; + +use crate::utils::test_logger; + +fn check_eq(btree: &BTreeMap, indexed: &IndexedMap) { + assert_eq!(btree.len(), indexed.len()); + assert_eq!(btree.is_empty(), indexed.is_empty()); + + let mut btree_clone = btree.clone(); + assert!(btree_clone == *btree); + let mut indexed_clone = indexed.clone(); + assert!(indexed_clone == *indexed); + + for k in 0..=255 { + assert_eq!(btree.contains_key(&k), indexed.contains_key(&k)); + assert_eq!(btree.get(&k), indexed.get(&k)); + + let btree_entry = btree_clone.entry(k); + let indexed_entry = indexed_clone.entry(k); + match btree_entry { + btree_map::Entry::Occupied(mut bo) => { + if let indexed_map::Entry::Occupied(mut io) = indexed_entry { + assert_eq!(bo.get(), io.get()); + assert_eq!(bo.get_mut(), io.get_mut()); + } else { panic!(); } + }, + btree_map::Entry::Vacant(_) => { + if let indexed_map::Entry::Vacant(_) = indexed_entry { + } else { panic!(); } + } + } + } + + const STRIDE: u8 = 16; + for k in 0..=255/STRIDE { + let lower_bound = k * STRIDE; + let upper_bound = lower_bound + (STRIDE - 1); + let mut btree_iter = btree.range(lower_bound..=upper_bound); + let mut indexed_iter = indexed.range(lower_bound..=upper_bound); + loop { + let b_v = btree_iter.next(); + let i_v = indexed_iter.next(); + assert_eq!(b_v, i_v); + if b_v.is_none() { break; } + } + } + + let mut key_set = HashSet::with_capacity(256); + for k in indexed.unordered_keys() { + assert!(key_set.insert(*k)); + assert!(btree.contains_key(k)); + } + assert_eq!(key_set.len(), btree.len()); + + key_set.clear(); + for (k, v) in indexed.unordered_iter() { + assert!(key_set.insert(*k)); + assert_eq!(btree.get(k).unwrap(), v); + } + assert_eq!(key_set.len(), btree.len()); + + key_set.clear(); + for (k, v) in indexed_clone.unordered_iter_mut() { + assert!(key_set.insert(*k)); + assert_eq!(btree.get(k).unwrap(), v); + } + assert_eq!(key_set.len(), btree.len()); +} + +#[inline] +pub fn do_test(data: &[u8]) { + if data.len() % 2 != 0 { return; } + let mut btree = BTreeMap::new(); + let mut indexed = IndexedMap::new(); + + // Read in k-v pairs from the input and insert them into the maps then check that the maps are + // equivalent in every way we can read them. + for tuple in data.windows(2) { + let prev_value_b = btree.insert(tuple[0], tuple[1]); + let prev_value_i = indexed.insert(tuple[0], tuple[1]); + assert_eq!(prev_value_b, prev_value_i); + } + check_eq(&btree, &indexed); + + // Now, modify the maps in all the ways we have to do so, checking that the maps remain + // equivalent as we go. + for (k, v) in indexed.unordered_iter_mut() { + *v = *k; + *btree.get_mut(k).unwrap() = *k; + } + check_eq(&btree, &indexed); + + for k in 0..=255 { + match btree.entry(k) { + btree_map::Entry::Occupied(mut bo) => { + if let indexed_map::Entry::Occupied(mut io) = indexed.entry(k) { + if k < 64 { + *io.get_mut() ^= 0xff; + *bo.get_mut() ^= 0xff; + } else if k < 128 { + *io.into_mut() ^= 0xff; + *bo.get_mut() ^= 0xff; + } else { + assert_eq!(bo.remove_entry(), io.remove_entry()); + } + } else { panic!(); } + }, + btree_map::Entry::Vacant(bv) => { + if let indexed_map::Entry::Vacant(iv) = indexed.entry(k) { + bv.insert(k); + iv.insert(k); + } else { panic!(); } + }, + } + } + check_eq(&btree, &indexed); +} + +pub fn indexedmap_test(data: &[u8], _out: Out) { + do_test(data); +} + +#[no_mangle] +pub extern "C" fn indexedmap_run(data: *const u8, datalen: usize) { + do_test(unsafe { std::slice::from_raw_parts(data, datalen) }); +} diff --git a/fuzz/src/lib.rs b/fuzz/src/lib.rs index 2238a9702..462307d55 100644 --- a/fuzz/src/lib.rs +++ b/fuzz/src/lib.rs @@ -17,6 +17,7 @@ pub mod utils; pub mod chanmon_deser; pub mod chanmon_consistency; pub mod full_stack; +pub mod indexedmap; pub mod onion_message; pub mod peer_crypt; pub mod process_network_graph; diff --git a/fuzz/targets.h b/fuzz/targets.h index cff3f9bdb..5bfee07da 100644 --- a/fuzz/targets.h +++ b/fuzz/targets.h @@ -7,6 +7,7 @@ void peer_crypt_run(const unsigned char* data, size_t data_len); void process_network_graph_run(const unsigned char* data, size_t data_len); void router_run(const unsigned char* data, size_t data_len); void zbase32_run(const unsigned char* data, size_t data_len); +void indexedmap_run(const unsigned char* data, size_t data_len); void msg_accept_channel_run(const unsigned char* data, size_t data_len); void msg_announcement_signatures_run(const unsigned char* data, size_t data_len); void msg_channel_reestablish_run(const unsigned char* data, size_t data_len); -- 2.39.5