diff options
Diffstat (limited to '')
-rw-r--r-- | src/rocksdb/fuzz/.gitignore | 5 | ||||
-rw-r--r-- | src/rocksdb/fuzz/Makefile | 67 | ||||
-rw-r--r-- | src/rocksdb/fuzz/README.md | 165 | ||||
-rw-r--r-- | src/rocksdb/fuzz/db_fuzzer.cc | 172 | ||||
-rw-r--r-- | src/rocksdb/fuzz/db_map_fuzzer.cc | 107 | ||||
-rw-r--r-- | src/rocksdb/fuzz/proto/db_operation.proto | 28 | ||||
-rw-r--r-- | src/rocksdb/fuzz/sst_file_writer_fuzzer.cc | 209 | ||||
-rw-r--r-- | src/rocksdb/fuzz/util.h | 29 |
8 files changed, 782 insertions, 0 deletions
diff --git a/src/rocksdb/fuzz/.gitignore b/src/rocksdb/fuzz/.gitignore new file mode 100644 index 000000000..9dab42105 --- /dev/null +++ b/src/rocksdb/fuzz/.gitignore @@ -0,0 +1,5 @@ +db_fuzzer +db_map_fuzzer +sst_file_writer_fuzzer + +proto/gen/* diff --git a/src/rocksdb/fuzz/Makefile b/src/rocksdb/fuzz/Makefile new file mode 100644 index 000000000..b83040504 --- /dev/null +++ b/src/rocksdb/fuzz/Makefile @@ -0,0 +1,67 @@ +# Copyright (c) 2011-present, Facebook, Inc. All rights reserved. +# This source code is licensed under both the GPLv2 (found in the +# COPYING file in the root directory) and Apache 2.0 License +# (found in the LICENSE.Apache file in the root directory). + +ROOT_DIR = $(abspath $(shell pwd)/../) + +include $(ROOT_DIR)/make_config.mk + +PROTOBUF_CFLAGS = `pkg-config --cflags protobuf` +PROTOBUF_LDFLAGS = `pkg-config --libs protobuf` + +PROTOBUF_MUTATOR_CFLAGS = `pkg-config --cflags libprotobuf-mutator` +PROTOBUF_MUTATOR_LDFLAGS = `pkg-config --libs libprotobuf-mutator` + +ROCKSDB_INCLUDE_DIR = $(ROOT_DIR)/include +ROCKSDB_LIB_DIR = $(ROOT_DIR) + +PROTO_IN = $(ROOT_DIR)/fuzz/proto +PROTO_OUT = $(ROOT_DIR)/fuzz/proto/gen + +ifneq ($(FUZZ_ENV), ossfuzz) +CC = $(CXX) +CCFLAGS += -Wall -fsanitize=address,fuzzer +CFLAGS += $(PLATFORM_CXXFLAGS) $(PROTOBUF_CFLAGS) $(PROTOBUF_MUTATOR_CFLAGS) -I$(PROTO_OUT) -I$(ROCKSDB_INCLUDE_DIR) -I$(ROCKSDB_LIB_DIR) +LDFLAGS += $(PLATFORM_LDFLAGS) $(PROTOBUF_MUTATOR_LDFLAGS) $(PROTOBUF_LDFLAGS) -L$(ROCKSDB_LIB_DIR) -lrocksdb +else +# OSS-Fuzz sets various environment flags that are used for compilation. +# These environment flags depend on which type of sanitizer build is being +# used, however, an ASan build would set the environment flags as follows: +# CFLAGS="-O1 -fno-omit-frame-pointer -gline-tables-only \ + -DFUZZING_BUILD_MODE_UNSAFE_FOR_PRODUCTION -fsanitize=address \ + -fsanitize-address-use-after-scope -fsanitize=fuzzer-no-link" +# CXXFLAGS="-O1 -fno-omit-frame-pointer -gline-tables-only \ + -DFUZZING_BUILD_MODE_UNSAFE_FOR_PRODUCTION -fsanitize=address \ + -fsanitize-address-use-after-scope -fsanitize=fuzzer-no-link \ + -stdlib=libc++" +# LIB_FUZZING_ENGINE="-fsanitize=fuzzer" +CC = $(CXX) +CCFLAGS = $(CXXFLAGS) +CFLAGS += $(PROTOBUF_CFLAGS) $(PROTOBUF_MUTATOR_CFLAGS) -I$(PROTO_OUT) -I$(ROCKSDB_INCLUDE_DIR) -I$(ROCKSDB_LIB_DIR) +LDFLAGS += $(PLATFORM_LDFLAGS) $(LIB_FUZZING_ENGINE) $(PROTOBUF_MUTATOR_LDFLAGS) $(PROTOBUF_LDFLAGS) -L$(ROCKSDB_LIB_DIR) -lrocksdb +endif + +.PHONY: gen_proto clean + +# Set PROTOC_BIN when invoking `make` if a custom protoc is required. +PROTOC_BIN ?= protoc + +gen_proto: + mkdir -p $(PROTO_OUT) + $(PROTOC_BIN) \ + --proto_path=$(PROTO_IN) \ + --cpp_out=$(PROTO_OUT) \ + $(PROTO_IN)/*.proto + +clean: + rm -rf db_fuzzer db_map_fuzzer sst_file_writer_fuzzer $(PROTO_OUT) + +db_fuzzer: db_fuzzer.cc + $(CC) $(CCFLAGS) -o db_fuzzer db_fuzzer.cc $(CFLAGS) $(LDFLAGS) + +db_map_fuzzer: gen_proto db_map_fuzzer.cc proto/gen/db_operation.pb.cc + $(CC) $(CCFLAGS) -o db_map_fuzzer db_map_fuzzer.cc proto/gen/db_operation.pb.cc $(CFLAGS) $(LDFLAGS) + +sst_file_writer_fuzzer: gen_proto sst_file_writer_fuzzer.cc proto/gen/db_operation.pb.cc + $(CC) $(CCFLAGS) -o sst_file_writer_fuzzer sst_file_writer_fuzzer.cc proto/gen/db_operation.pb.cc $(CFLAGS) $(LDFLAGS) diff --git a/src/rocksdb/fuzz/README.md b/src/rocksdb/fuzz/README.md new file mode 100644 index 000000000..238b283a2 --- /dev/null +++ b/src/rocksdb/fuzz/README.md @@ -0,0 +1,165 @@ +# Fuzzing RocksDB + +## Overview + +This directory contains [fuzz tests](https://en.wikipedia.org/wiki/Fuzzing) for RocksDB. +RocksDB testing infrastructure currently includes unit tests and [stress tests](https://github.com/facebook/rocksdb/wiki/Stress-test), +we hope fuzz testing can catch more bugs. + +## Prerequisite + +We use [LLVM libFuzzer](http://llvm.org/docs/LibFuzzer.html) as the fuzzying engine, +so make sure you have [clang](https://clang.llvm.org/get_started.html) as your compiler. + +Some tests rely on [structure aware fuzzing](https://github.com/google/fuzzing/blob/master/docs/structure-aware-fuzzing.md). +We use [protobuf](https://developers.google.com/protocol-buffers) to define structured input to the fuzzer, +and use [libprotobuf-mutator](https://github.com/google/libprotobuf-mutator) as the custom libFuzzer mutator. +So make sure you have protobuf and libprotobuf-mutator installed, and make sure `pkg-config` can find them. +On some systems, there are both protobuf2 and protobuf3 in the package management system, +make sure protobuf3 is installed. + +If you do not want to install protobuf library yourself, you can rely on libprotobuf-mutator to download protobuf +for you. For details about installation, please refer to [libprotobuf-mutator README](https://github.com/google/libprotobuf-mutator#readme) + +## Example + +This example shows you how to do structure aware fuzzing to `rocksdb::SstFileWriter`. + +After walking through the steps to create the fuzzer, we'll introduce a bug into `rocksdb::SstFileWriter::Put`, +then show that the fuzzer can catch the bug. + +### Design the test + +We want the fuzzing engine to automatically generate a list of database operations, +then we apply these operations to `SstFileWriter` in sequence, +finally, after the SST file is generated, we use `SstFileReader` to check the file's checksum. + +### Define input + +We define the database operations in protobuf, each operation has a type of operation and a key value pair, +see [proto/db_operation.proto](proto/db_operation.proto) for details. + +### Define tests with the input + +In [sst_file_writer_fuzzer.cc](sst_file_writer_fuzzer.cc), +we define the tests to be run on the generated input: + +``` +DEFINE_PROTO_FUZZER(DBOperations& input) { + // apply the operations to SstFileWriter and use SstFileReader to verify checksum. + // ... +} +``` + +`SstFileWriter` requires the keys of the operations to be unique and be in ascending order, +but the fuzzing engine generates the input randomly, so we need to process the generated input before +passing it to `DEFINE_PROTO_FUZZER`, this is accomplished by registering a post processor: + +``` +protobuf_mutator::libfuzzer::PostProcessorRegistration<DBOperations> +``` + +### Compile and link the fuzzer + +In the rocksdb root directory, compile rocksdb library by `make static_lib`. + +Go to the `fuzz` directory, +run `make sst_file_writer_fuzzer` to generate the fuzzer, +it will compile rocksdb static library, generate protobuf, then compile and link `sst_file_writer_fuzzer`. + +### Introduce a bug + +Manually introduce a bug to `SstFileWriter::Put`: + +``` +diff --git a/table/sst_file_writer.cc b/table/sst_file_writer.cc +index ab1ee7c4e..c7da9ffa0 100644 +--- a/table/sst_file_writer.cc ++++ b/table/sst_file_writer.cc +@@ -277,6 +277,11 @@ Status SstFileWriter::Add(const Slice& user_key, const Slice& value) { + } + + Status SstFileWriter::Put(const Slice& user_key, const Slice& value) { ++ if (user_key.starts_with("!")) { ++ if (value.ends_with("!")) { ++ return Status::Corruption("bomb"); ++ } ++ } + return rep_->Add(user_key, value, ValueType::kTypeValue); + } +``` + +The bug is that for `Put`, if `user_key` starts with `!` and `value` ends with `!`, then corrupt. + +### Run fuzz testing to catch the bug + +Run the fuzzer by `time ./sst_file_writer_fuzzer`. + +Here is the output on my machine: + +``` +Corruption: bomb +==59680== ERROR: libFuzzer: deadly signal + #0 0x109487315 in __sanitizer_print_stack_trace+0x35 (libclang_rt.asan_osx_dynamic.dylib:x86_64+0x4d315) + #1 0x108d63f18 in fuzzer::PrintStackTrace() FuzzerUtil.cpp:205 + #2 0x108d47613 in fuzzer::Fuzzer::CrashCallback() FuzzerLoop.cpp:232 + #3 0x7fff6af535fc in _sigtramp+0x1c (libsystem_platform.dylib:x86_64+0x35fc) + #4 0x7ffee720f3ef (<unknown module>) + #5 0x7fff6ae29807 in abort+0x77 (libsystem_c.dylib:x86_64+0x7f807) + #6 0x108cf1c4c in TestOneProtoInput(DBOperations&)+0x113c (sst_file_writer_fuzzer:x86_64+0x100302c4c) + #7 0x108cf09be in LLVMFuzzerTestOneInput+0x16e (sst_file_writer_fuzzer:x86_64+0x1003019be) + #8 0x108d48ce0 in fuzzer::Fuzzer::ExecuteCallback(unsigned char const*, unsigned long) FuzzerLoop.cpp:556 + #9 0x108d48425 in fuzzer::Fuzzer::RunOne(unsigned char const*, unsigned long, bool, fuzzer::InputInfo*, bool*) FuzzerLoop.cpp:470 + #10 0x108d4a626 in fuzzer::Fuzzer::MutateAndTestOne() FuzzerLoop.cpp:698 + #11 0x108d4b325 in fuzzer::Fuzzer::Loop(std::__1::vector<fuzzer::SizedFile, fuzzer::fuzzer_allocator<fuzzer::SizedFile> >&) FuzzerLoop.cpp:830 + #12 0x108d37fcd in fuzzer::FuzzerDriver(int*, char***, int (*)(unsigned char const*, unsigned long)) FuzzerDriver.cpp:829 + #13 0x108d652b2 in main FuzzerMain.cpp:19 + #14 0x7fff6ad5acc8 in start+0x0 (libdyld.dylib:x86_64+0x1acc8) + +NOTE: libFuzzer has rudimentary signal handlers. + Combine libFuzzer with AddressSanitizer or similar for better crash reports. +SUMMARY: libFuzzer: deadly signal +MS: 7 Custom-CustomCrossOver-InsertByte-Custom-ChangeBit-Custom-CustomCrossOver-; base unit: 90863b4d83c3f994bba0a417d0c2ee3b68f9e795 +0x6f,0x70,0x65,0x72,0x61,0x74,0x69,0x6f,0x6e,0x73,0x20,0x7b,0xa,0x20,0x20,0x6b,0x65,0x79,0x3a,0x20,0x22,0x21,0x22,0xa,0x20,0x20,0x76,0x61,0x6c,0x75,0x65,0x3a,0x20,0x22,0x21,0x22,0xa,0x20,0x20,0x74,0x79,0x70,0x65,0x3a,0x20,0x50,0x55,0x54,0xa,0x7d,0xa,0x6f,0x70,0x65,0x72,0x61,0x74,0x69,0x6f,0x6e,0x73,0x20,0x7b,0xa,0x20,0x20,0x6b,0x65,0x79,0x3a,0x20,0x22,0x2b,0x22,0xa,0x20,0x20,0x74,0x79,0x70,0x65,0x3a,0x20,0x50,0x55,0x54,0xa,0x7d,0xa,0x6f,0x70,0x65,0x72,0x61,0x74,0x69,0x6f,0x6e,0x73,0x20,0x7b,0xa,0x20,0x20,0x6b,0x65,0x79,0x3a,0x20,0x22,0x2e,0x22,0xa,0x20,0x20,0x74,0x79,0x70,0x65,0x3a,0x20,0x50,0x55,0x54,0xa,0x7d,0xa,0x6f,0x70,0x65,0x72,0x61,0x74,0x69,0x6f,0x6e,0x73,0x20,0x7b,0xa,0x20,0x20,0x6b,0x65,0x79,0x3a,0x20,0x22,0x5c,0x32,0x35,0x33,0x22,0xa,0x20,0x20,0x74,0x79,0x70,0x65,0x3a,0x20,0x50,0x55,0x54,0xa,0x7d,0xa, +operations {\x0a key: \"!\"\x0a value: \"!\"\x0a type: PUT\x0a}\x0aoperations {\x0a key: \"+\"\x0a type: PUT\x0a}\x0aoperations {\x0a key: \".\"\x0a type: PUT\x0a}\x0aoperations {\x0a key: \"\\253\"\x0a type: PUT\x0a}\x0a +artifact_prefix='./'; Test unit written to ./crash-a1460be302d09b548e61787178d9edaa40aea467 +Base64: b3BlcmF0aW9ucyB7CiAga2V5OiAiISIKICB2YWx1ZTogIiEiCiAgdHlwZTogUFVUCn0Kb3BlcmF0aW9ucyB7CiAga2V5OiAiKyIKICB0eXBlOiBQVVQKfQpvcGVyYXRpb25zIHsKICBrZXk6ICIuIgogIHR5cGU6IFBVVAp9Cm9wZXJhdGlvbnMgewogIGtleTogIlwyNTMiCiAgdHlwZTogUFVUCn0K +./sst_file_writer_fuzzer 5.97s user 4.40s system 64% cpu 16.195 total +``` + +Within 6 seconds, it catches the bug. + +The input that triggers the bug is persisted in `./crash-a1460be302d09b548e61787178d9edaa40aea467`: + +``` +$ cat ./crash-a1460be302d09b548e61787178d9edaa40aea467 +operations { + key: "!" + value: "!" + type: PUT +} +operations { + key: "+" + type: PUT +} +operations { + key: "." + type: PUT +} +operations { + key: "\253" + type: PUT +} +``` + +### Reproduce the crash to debug + +The above crash can be reproduced by `./sst_file_writer_fuzzer ./crash-a1460be302d09b548e61787178d9edaa40aea467`, +so you can debug the crash. + +## Future Work + +According to [OSS-Fuzz](https://github.com/google/oss-fuzz), +`as of June 2020, OSS-Fuzz has found over 20,000 bugs in 300 open source projects.` + +RocksDB can join OSS-Fuzz together with other open source projects such as sqlite. diff --git a/src/rocksdb/fuzz/db_fuzzer.cc b/src/rocksdb/fuzz/db_fuzzer.cc new file mode 100644 index 000000000..e6d5bb63c --- /dev/null +++ b/src/rocksdb/fuzz/db_fuzzer.cc @@ -0,0 +1,172 @@ +// Copyright (c) Meta Platforms, Inc. and affiliates. +// +// This source code is licensed under both the GPLv2 (found in the +// COPYING file in the root directory) and Apache 2.0 License +// (found in the LICENSE.Apache file in the root directory). + +#include <fuzzer/FuzzedDataProvider.h> + +#include "rocksdb/db.h" + +enum OperationType { + kPut, + kGet, + kDelete, + kGetProperty, + kIterator, + kSnapshot, + kOpenClose, + kColumn, + kCompactRange, + kSeekForPrev, + OP_COUNT +}; + +constexpr char db_path[] = "/tmp/testdb"; + +// Fuzzes DB operations by doing interpretations on the data. Both the +// sequence of API calls to be called on the DB as well as the arguments +// to each of these APIs are interpreted by way of the data buffer. +// The operations that the fuzzer supports are given by the OperationType +// enum. The goal is to capture sanitizer bugs, so the code should be +// compiled with a given sanitizer (ASan, UBSan, MSan). +extern "C" int LLVMFuzzerTestOneInput(const uint8_t* data, size_t size) { + ROCKSDB_NAMESPACE::DB* db; + ROCKSDB_NAMESPACE::Options options; + options.create_if_missing = true; + ROCKSDB_NAMESPACE::Status status = + ROCKSDB_NAMESPACE::DB::Open(options, db_path, &db); + if (!status.ok()) { + return 0; + } + FuzzedDataProvider fuzzed_data(data, size); + + // perform a sequence of calls on our db instance + int max_iter = static_cast<int>(data[0]); + for (int i = 0; i < max_iter && i < size; i++) { + OperationType op = static_cast<OperationType>(data[i] % OP_COUNT); + + switch (op) { + case kPut: { + std::string key = fuzzed_data.ConsumeRandomLengthString(); + std::string val = fuzzed_data.ConsumeRandomLengthString(); + db->Put(ROCKSDB_NAMESPACE::WriteOptions(), key, val); + break; + } + case kGet: { + std::string key = fuzzed_data.ConsumeRandomLengthString(); + std::string value; + db->Get(ROCKSDB_NAMESPACE::ReadOptions(), key, &value); + break; + } + case kDelete: { + std::string key = fuzzed_data.ConsumeRandomLengthString(); + db->Delete(ROCKSDB_NAMESPACE::WriteOptions(), key); + break; + } + case kGetProperty: { + std::string prop; + std::string property_name = fuzzed_data.ConsumeRandomLengthString(); + db->GetProperty(property_name, &prop); + break; + } + case kIterator: { + ROCKSDB_NAMESPACE::Iterator* it = + db->NewIterator(ROCKSDB_NAMESPACE::ReadOptions()); + for (it->SeekToFirst(); it->Valid(); it->Next()) { + } + delete it; + break; + } + case kSnapshot: { + ROCKSDB_NAMESPACE::ReadOptions snapshot_options; + snapshot_options.snapshot = db->GetSnapshot(); + ROCKSDB_NAMESPACE::Iterator* it = db->NewIterator(snapshot_options); + db->ReleaseSnapshot(snapshot_options.snapshot); + delete it; + break; + } + case kOpenClose: { + db->Close(); + delete db; + status = ROCKSDB_NAMESPACE::DB::Open(options, db_path, &db); + if (!status.ok()) { + ROCKSDB_NAMESPACE::DestroyDB(db_path, options); + return 0; + } + + break; + } + case kColumn: { + ROCKSDB_NAMESPACE::ColumnFamilyHandle* cf; + ROCKSDB_NAMESPACE::Status s; + s = db->CreateColumnFamily(ROCKSDB_NAMESPACE::ColumnFamilyOptions(), + "new_cf", &cf); + s = db->DestroyColumnFamilyHandle(cf); + db->Close(); + delete db; + + // open DB with two column families + std::vector<ROCKSDB_NAMESPACE::ColumnFamilyDescriptor> column_families; + // have to open default column family + column_families.push_back(ROCKSDB_NAMESPACE::ColumnFamilyDescriptor( + ROCKSDB_NAMESPACE::kDefaultColumnFamilyName, + ROCKSDB_NAMESPACE::ColumnFamilyOptions())); + // open the new one, too + column_families.push_back(ROCKSDB_NAMESPACE::ColumnFamilyDescriptor( + "new_cf", ROCKSDB_NAMESPACE::ColumnFamilyOptions())); + std::vector<ROCKSDB_NAMESPACE::ColumnFamilyHandle*> handles; + s = ROCKSDB_NAMESPACE::DB::Open(ROCKSDB_NAMESPACE::DBOptions(), db_path, + column_families, &handles, &db); + + if (s.ok()) { + std::string key1 = fuzzed_data.ConsumeRandomLengthString(); + std::string val1 = fuzzed_data.ConsumeRandomLengthString(); + std::string key2 = fuzzed_data.ConsumeRandomLengthString(); + s = db->Put(ROCKSDB_NAMESPACE::WriteOptions(), handles[1], key1, + val1); + std::string value; + s = db->Get(ROCKSDB_NAMESPACE::ReadOptions(), handles[1], key2, + &value); + s = db->DropColumnFamily(handles[1]); + for (auto handle : handles) { + s = db->DestroyColumnFamilyHandle(handle); + } + } else { + status = ROCKSDB_NAMESPACE::DB::Open(options, db_path, &db); + if (!status.ok()) { + // At this point there is no saving to do. So we exit + ROCKSDB_NAMESPACE::DestroyDB(db_path, ROCKSDB_NAMESPACE::Options()); + return 0; + } + } + break; + } + case kCompactRange: { + std::string slice_start = fuzzed_data.ConsumeRandomLengthString(); + std::string slice_end = fuzzed_data.ConsumeRandomLengthString(); + + ROCKSDB_NAMESPACE::Slice begin(slice_start); + ROCKSDB_NAMESPACE::Slice end(slice_end); + ROCKSDB_NAMESPACE::CompactRangeOptions options; + ROCKSDB_NAMESPACE::Status s = db->CompactRange(options, &begin, &end); + break; + } + case kSeekForPrev: { + std::string key = fuzzed_data.ConsumeRandomLengthString(); + auto iter = db->NewIterator(ROCKSDB_NAMESPACE::ReadOptions()); + iter->SeekForPrev(key); + delete iter; + break; + } + case OP_COUNT: + break; + } + } + + // Cleanup DB + db->Close(); + delete db; + ROCKSDB_NAMESPACE::DestroyDB(db_path, options); + return 0; +} diff --git a/src/rocksdb/fuzz/db_map_fuzzer.cc b/src/rocksdb/fuzz/db_map_fuzzer.cc new file mode 100644 index 000000000..ed9df8f84 --- /dev/null +++ b/src/rocksdb/fuzz/db_map_fuzzer.cc @@ -0,0 +1,107 @@ +// Copyright (c) 2011-present, Facebook, Inc. All rights reserved. +// This source code is licensed under both the GPLv2 (found in the +// COPYING file in the root directory) and Apache 2.0 License +// (found in the LICENSE.Apache file in the root directory). + +#include <algorithm> +#include <iostream> +#include <map> +#include <string> + +#include "proto/gen/db_operation.pb.h" +#include "rocksdb/db.h" +#include "rocksdb/file_system.h" +#include "src/libfuzzer/libfuzzer_macro.h" +#include "util.h" + +protobuf_mutator::libfuzzer::PostProcessorRegistration<DBOperations> reg = { + [](DBOperations* input, unsigned int /* seed */) { + const ROCKSDB_NAMESPACE::Comparator* comparator = + ROCKSDB_NAMESPACE::BytewiseComparator(); + auto ops = input->mutable_operations(); + // Make sure begin <= end for DELETE_RANGE. + for (DBOperation& op : *ops) { + if (op.type() == OpType::DELETE_RANGE) { + auto begin = op.key(); + auto end = op.value(); + if (comparator->Compare(begin, end) > 0) { + std::swap(begin, end); + op.set_key(begin); + op.set_value(end); + } + } + } + }}; + +// Execute randomly generated operations on both a DB and a std::map, +// then reopen the DB and make sure that iterating the DB produces the +// same key-value pairs as iterating through the std::map. +DEFINE_PROTO_FUZZER(DBOperations& input) { + if (input.operations().empty()) { + return; + } + + const std::string kDbPath = "/tmp/db_map_fuzzer_test"; + auto fs = ROCKSDB_NAMESPACE::FileSystem::Default(); + if (fs->FileExists(kDbPath, ROCKSDB_NAMESPACE::IOOptions(), /*dbg=*/nullptr) + .ok()) { + std::cerr << "db path " << kDbPath << " already exists" << std::endl; + abort(); + } + + std::map<std::string, std::string> kv; + ROCKSDB_NAMESPACE::DB* db = nullptr; + ROCKSDB_NAMESPACE::Options options; + options.create_if_missing = true; + CHECK_OK(ROCKSDB_NAMESPACE::DB::Open(options, kDbPath, &db)); + + for (const DBOperation& op : input.operations()) { + switch (op.type()) { + case OpType::PUT: { + CHECK_OK( + db->Put(ROCKSDB_NAMESPACE::WriteOptions(), op.key(), op.value())); + kv[op.key()] = op.value(); + break; + } + case OpType::MERGE: { + break; + } + case OpType::DELETE: { + CHECK_OK(db->Delete(ROCKSDB_NAMESPACE::WriteOptions(), op.key())); + kv.erase(op.key()); + break; + } + case OpType::DELETE_RANGE: { + // [op.key(), op.value()) corresponds to [begin, end). + CHECK_OK(db->DeleteRange(ROCKSDB_NAMESPACE::WriteOptions(), + db->DefaultColumnFamily(), op.key(), + op.value())); + kv.erase(kv.lower_bound(op.key()), kv.lower_bound(op.value())); + break; + } + default: { + std::cerr << "Unsupported operation" << static_cast<int>(op.type()); + return; + } + } + } + CHECK_OK(db->Close()); + delete db; + db = nullptr; + + CHECK_OK(ROCKSDB_NAMESPACE::DB::Open(options, kDbPath, &db)); + auto kv_it = kv.begin(); + ROCKSDB_NAMESPACE::Iterator* it = + db->NewIterator(ROCKSDB_NAMESPACE::ReadOptions()); + for (it->SeekToFirst(); it->Valid(); it->Next(), kv_it++) { + CHECK_TRUE(kv_it != kv.end()); + CHECK_EQ(it->key().ToString(), kv_it->first); + CHECK_EQ(it->value().ToString(), kv_it->second); + } + CHECK_TRUE(kv_it == kv.end()); + delete it; + + CHECK_OK(db->Close()); + delete db; + CHECK_OK(ROCKSDB_NAMESPACE::DestroyDB(kDbPath, options)); +} diff --git a/src/rocksdb/fuzz/proto/db_operation.proto b/src/rocksdb/fuzz/proto/db_operation.proto new file mode 100644 index 000000000..20a55eaa5 --- /dev/null +++ b/src/rocksdb/fuzz/proto/db_operation.proto @@ -0,0 +1,28 @@ +// Copyright (c) 2011-present, Facebook, Inc. All rights reserved. +// This source code is licensed under both the GPLv2 (found in the +// COPYING file in the root directory) and Apache 2.0 License +// (found in the LICENSE.Apache file in the root directory). + +// Defines database operations. +// Each operation is a key-value pair and an operation type. + +syntax = "proto2"; + +enum OpType { + PUT = 0; + MERGE = 1; + DELETE = 2; + DELETE_RANGE = 3; +} + +message DBOperation { + required string key = 1; + // value is ignored for DELETE. + // [key, value] is the range for DELETE_RANGE. + optional string value = 2; + required OpType type = 3; +} + +message DBOperations { + repeated DBOperation operations = 1; +} diff --git a/src/rocksdb/fuzz/sst_file_writer_fuzzer.cc b/src/rocksdb/fuzz/sst_file_writer_fuzzer.cc new file mode 100644 index 000000000..e93b9a3f5 --- /dev/null +++ b/src/rocksdb/fuzz/sst_file_writer_fuzzer.cc @@ -0,0 +1,209 @@ +// Copyright (c) 2011-present, Facebook, Inc. All rights reserved. +// This source code is licensed under both the GPLv2 (found in the +// COPYING file in the root directory) and Apache 2.0 License +// (found in the LICENSE.Apache file in the root directory). + +#include <algorithm> +#include <iostream> +#include <memory> +#include <string> + +#include "proto/gen/db_operation.pb.h" +#include "rocksdb/file_system.h" +#include "rocksdb/sst_file_writer.h" +#include "src/libfuzzer/libfuzzer_macro.h" +#include "table/table_builder.h" +#include "table/table_reader.h" +#include "util.h" + +using ROCKSDB_NAMESPACE::BytewiseComparator; +using ROCKSDB_NAMESPACE::Comparator; +using ROCKSDB_NAMESPACE::EnvOptions; +using ROCKSDB_NAMESPACE::ExternalSstFileInfo; +using ROCKSDB_NAMESPACE::FileOptions; +using ROCKSDB_NAMESPACE::FileSystem; +using ROCKSDB_NAMESPACE::ImmutableCFOptions; +using ROCKSDB_NAMESPACE::ImmutableOptions; +using ROCKSDB_NAMESPACE::InternalIterator; +using ROCKSDB_NAMESPACE::IOOptions; +using ROCKSDB_NAMESPACE::kMaxSequenceNumber; +using ROCKSDB_NAMESPACE::Options; +using ROCKSDB_NAMESPACE::ParsedInternalKey; +using ROCKSDB_NAMESPACE::ParseInternalKey; +using ROCKSDB_NAMESPACE::RandomAccessFileReader; +using ROCKSDB_NAMESPACE::ReadOptions; +using ROCKSDB_NAMESPACE::SstFileWriter; +using ROCKSDB_NAMESPACE::Status; +using ROCKSDB_NAMESPACE::TableReader; +using ROCKSDB_NAMESPACE::TableReaderCaller; +using ROCKSDB_NAMESPACE::TableReaderOptions; +using ROCKSDB_NAMESPACE::ValueType; + +// Keys in SST file writer operations must be unique and in ascending order. +// For each DBOperation generated by the fuzzer, this function is called on +// it to deduplicate and sort the keys in the DBOperations. +protobuf_mutator::libfuzzer::PostProcessorRegistration<DBOperations> reg = { + [](DBOperations* input, unsigned int /* seed */) { + const Comparator* comparator = BytewiseComparator(); + auto ops = input->mutable_operations(); + + // Make sure begin <= end for DELETE_RANGE. + for (DBOperation& op : *ops) { + if (op.type() == OpType::DELETE_RANGE) { + auto begin = op.key(); + auto end = op.value(); + if (comparator->Compare(begin, end) > 0) { + std::swap(begin, end); + op.set_key(begin); + op.set_value(end); + } + } + } + + std::sort(ops->begin(), ops->end(), + [&comparator](const DBOperation& a, const DBOperation& b) { + return comparator->Compare(a.key(), b.key()) < 0; + }); + + auto last = std::unique( + ops->begin(), ops->end(), + [&comparator](const DBOperation& a, const DBOperation& b) { + return comparator->Compare(a.key(), b.key()) == 0; + }); + ops->erase(last, ops->end()); + }}; + +TableReader* NewTableReader(const std::string& sst_file_path, + const Options& options, + const EnvOptions& env_options, + const ImmutableCFOptions& cf_ioptions) { + // This code block is similar to SstFileReader::Open. + + uint64_t file_size = 0; + std::unique_ptr<RandomAccessFileReader> file_reader; + std::unique_ptr<TableReader> table_reader; + const auto& fs = options.env->GetFileSystem(); + FileOptions fopts(env_options); + Status s = options.env->GetFileSize(sst_file_path, &file_size); + if (s.ok()) { + s = RandomAccessFileReader::Create(fs, sst_file_path, fopts, &file_reader, + nullptr); + } + if (s.ok()) { + ImmutableOptions iopts(options, cf_ioptions); + TableReaderOptions t_opt(iopts, /*prefix_extractor=*/nullptr, env_options, + cf_ioptions.internal_comparator); + t_opt.largest_seqno = kMaxSequenceNumber; + s = options.table_factory->NewTableReader(t_opt, std::move(file_reader), + file_size, &table_reader, + /*prefetch=*/false); + } + if (!s.ok()) { + std::cerr << "Failed to create TableReader for " << sst_file_path << ": " + << s.ToString() << std::endl; + abort(); + } + return table_reader.release(); +} + +ValueType ToValueType(OpType op_type) { + switch (op_type) { + case OpType::PUT: + return ValueType::kTypeValue; + case OpType::MERGE: + return ValueType::kTypeMerge; + case OpType::DELETE: + return ValueType::kTypeDeletion; + case OpType::DELETE_RANGE: + return ValueType::kTypeRangeDeletion; + default: + std::cerr << "Unknown operation type " << static_cast<int>(op_type) + << std::endl; + abort(); + } +} + +// Fuzzes DB operations as input, let SstFileWriter generate a SST file +// according to the operations, then let TableReader read and check all the +// key-value pairs from the generated SST file. +DEFINE_PROTO_FUZZER(DBOperations& input) { + if (input.operations().empty()) { + return; + } + + std::string sstfile; + { + auto fs = FileSystem::Default(); + std::string dir; + IOOptions opt; + CHECK_OK(fs->GetTestDirectory(opt, &dir, nullptr)); + sstfile = dir + "/SstFileWriterFuzzer.sst"; + } + + Options options; + EnvOptions env_options(options); + ImmutableCFOptions cf_ioptions(options); + + // Generate sst file. + SstFileWriter writer(env_options, options); + CHECK_OK(writer.Open(sstfile)); + for (const DBOperation& op : input.operations()) { + switch (op.type()) { + case OpType::PUT: { + CHECK_OK(writer.Put(op.key(), op.value())); + break; + } + case OpType::MERGE: { + CHECK_OK(writer.Merge(op.key(), op.value())); + break; + } + case OpType::DELETE: { + CHECK_OK(writer.Delete(op.key())); + break; + } + case OpType::DELETE_RANGE: { + CHECK_OK(writer.DeleteRange(op.key(), op.value())); + break; + } + default: { + std::cerr << "Unsupported operation" << static_cast<int>(op.type()) + << std::endl; + abort(); + } + } + } + ExternalSstFileInfo info; + CHECK_OK(writer.Finish(&info)); + + // Iterate and verify key-value pairs. + std::unique_ptr<TableReader> table_reader( + ::NewTableReader(sstfile, options, env_options, cf_ioptions)); + ReadOptions roptions; + CHECK_OK(table_reader->VerifyChecksum(roptions, + TableReaderCaller::kUncategorized)); + std::unique_ptr<InternalIterator> it( + table_reader->NewIterator(roptions, /*prefix_extractor=*/nullptr, + /*arena=*/nullptr, /*skip_filters=*/true, + TableReaderCaller::kUncategorized)); + it->SeekToFirst(); + for (const DBOperation& op : input.operations()) { + if (op.type() == OpType::DELETE_RANGE) { + // InternalIterator cannot iterate over DELETE_RANGE entries. + continue; + } + CHECK_TRUE(it->Valid()); + ParsedInternalKey ikey; + CHECK_OK(ParseInternalKey(it->key(), &ikey, /*log_err_key=*/true)); + CHECK_EQ(ikey.user_key.ToString(), op.key()); + CHECK_EQ(ikey.sequence, 0); + CHECK_EQ(ikey.type, ToValueType(op.type())); + if (op.type() != OpType::DELETE) { + CHECK_EQ(op.value(), it->value().ToString()); + } + it->Next(); + } + CHECK_TRUE(!it->Valid()); + + // Delete sst file. + remove(sstfile.c_str()); +} diff --git a/src/rocksdb/fuzz/util.h b/src/rocksdb/fuzz/util.h new file mode 100644 index 000000000..97011823a --- /dev/null +++ b/src/rocksdb/fuzz/util.h @@ -0,0 +1,29 @@ +// Copyright (c) Meta Platforms, Inc. and affiliates. +// +// This source code is licensed under both the GPLv2 (found in the +// COPYING file in the root directory) and Apache 2.0 License +// (found in the LICENSE.Apache file in the root directory). + +#pragma once + +#define CHECK_OK(expression) \ + do { \ + auto status = (expression); \ + if (!status.ok()) { \ + std::cerr << status.ToString() << std::endl; \ + abort(); \ + } \ + } while (0) + +#define CHECK_EQ(a, b) \ + if (a != b) { \ + std::cerr << "(" << #a << "=" << a << ") != (" << #b << "=" << b << ")" \ + << std::endl; \ + abort(); \ + } + +#define CHECK_TRUE(cond) \ + if (!(cond)) { \ + std::cerr << "\"" << #cond << "\" is false" << std::endl; \ + abort(); \ + } |