QuickCheck bug hunting in Rust standard library data structures

Overview

BugHunt, Rust

Build Status

This project is aiming to provide "stateful" QuickCheck models for Rust's standard library. That is, we build up a random list of operations against an abstract data type, an "obviously correct" model of that ADT and apply the operations to both the model and the reference implementation of the data type. If the model and reference implementation differ in any way then that's a good sign there's a bug to be diagnosed and reported. This is different from fuzzing in that we're interested in higher-level behaviour of data structures--their "properties"--and aren't necessarily looking for crashes. (That said, "do not crash the program" is a pretty good property for most data structures.)

We're inspired by the work @jlouis did in the Erlang community to detect subtle bugs in that language's map implementation and @shnatsel's recent work fuzzing Rust crates for crashes.

Running the Suite

Running the tests takes a little leg work. The project performs model-based fuzzing, which means the tests are driven by a fuzzer, cargo-fuzz (libFuzzer) in particular. We've written about the general approach here. Since this post we've switch from AFL to libFuzzer but the broad details remain the same.

The available targets are listed out in [fuzz/Cargo.toml], the binaries of the project. Say you want to run the str::repeat target. Make sure you've got cargo-fuzz installed by running cargo install cargo-fuzz.

> cargo fuzz run str_repeat

A reasonable test run will take hours and as configured the above run will execute forever. Give the flag --help to cargo fuzz to see its options relating to runtime constriction, corpus definition etc.

Why does this run outside of Rust itself?

Well! I'm not sure that bundling these long-running tests into the Rust compiler project is something anyone would go for and, working here as an external project, we can avoid needing to fiddle with toolchains and longish build cycles. Downside is, the std data structures we're testing don't have any sanitizers turned on etc on account of the project is run against the usual Rust release.

Contributing

Writing QuickCheck models can be slow work and contributions are very welcome, either introducing new models into the project or extending existing ones. We have an experimental clusterfuzz setup running and if you have credits to donate that would be most welcome. I intend to document project balances, money needs once they are clear.

Would you take CI help?

Yes! Right now we have a folder ci/ which has the build scripts used in .travis.yml. We're producing test binaries and feeding them directly into the clusterfuzz setup the project has. Speaking of, I'll be adding configuration for that cluster to this repository in the coming days.

Any improvements in the build pipeline, clusterfuzz configuration are most welcome.

Would you take documentation help?

Yes!

Hey, how can I learn more?

Randomized testing is a touch esoteric but there's a lot of reading material available (itself a problem, kind of). In no certain order:

I, blt, am also happy to answer questions over email. I'm [email protected].

Comments
  • Use fuzzing to drive property testing

    Use fuzzing to drive property testing

    This series of commits introduces the use of arbitrary and honggfuzz-rs in driving property tests, as discussed briefly by @Shnatsel and myself in #2. The code is now split between the library bits -- the Op, Arbitrary definition etc -- and the interpreter loop, now in the fuzz target called hash_map. If you have honggfuzz-rs installed you can run the fuzz target like:

    > cargo hfuzz run hash_map
    

    Installation instructions for honggfuzz can be found at the above project link.

    In terms of finding bugs, this was effective at finding the panic crash resulting from @llogiq's introduction of Op::Reserve. The problem, as discussed in 9596448, is that we can make very large capacity requests of the HashMap and it will be unable to allocate memory to meet that request, causing a panic. HashMap does not publish its overhead per pair so we cannot determine if a reservation will fail ahead of time. The check we have in place mostly guards against this but fuzzing managed to turn up truly large reservation failures. It was neat.

    The downside to this approach is there's no tooling support for it: no shrinking, failure reports are given as the byte inputs. Dropping into a debugger works well enough but it's not the best.

    opened by blt 12
  • Update README to reflect AFL runner

    Update README to reflect AFL runner

    This commit updates the README to reflect the changes made to use model-based fuzzing, as opposed to straight QuickCheck. This resolves

    Signed-off-by: Brian L. Troutwine [email protected]

    opened by blt 4
  • Adapt bughunt-rust to run in clusterfuzz

    Adapt bughunt-rust to run in clusterfuzz

    Now that clusterfuzz is open-source we can resolve a long-standing issue of bughunt-rust: not having enough CPU time. We should port tests to be runnable in clusterfuzz, setup a build pipeline etc.

    Specific tickets to follow.

    opened by blt 1
  • Introduce ClusterFuzz support

    Introduce ClusterFuzz support

    With this series of commits I've now enabled clusterfuzz support for the project, running at https://bughunt.appspot.com/. The use of AFL is now removed in favor of cargo-fuzz/libFuzzer for easy compatibility with clusterfuzz. This has made the README instructions more straightforward, which hopefully will help new contributors to the project.

    For reasons related, I think, to the travis org/com distinction the branch push builds -- done on org -- fail while the branch builds -- done on com -- succeed. This is a result of the secrets being pegged to com. I'll see after this is merged if I can sort out which domain the project will always run on.

    The clusterfuzz setup consumes actual funds, though for now we're operating out of credits. This project will need to sort out funding at some point, if the clusterfuzz setup proves worth keeping.

    opened by blt 0
  • Introduce more Ops for HashMap

    Introduce more Ops for HashMap

    This commit introduces three new operations against HashMap: ShrinkToFit, CheckCapacity and Clear. The consequences of these operations are documented in the commit itself. I've also updated the travis CI runner to run more tests of larger size by default. This will need to be dialed backward as the number of models grow.

    Signed-off-by: Brian L. Troutwine [email protected]

    opened by blt 0
  • Introduce an initial travis CI configuration

    Introduce an initial travis CI configuration

    This commit introduces a basic Travis CI configuration into the project. QC tests will just fly right on by but our clippy and formatting warnings will be checked. The developer should still run their models on their local machines for long periods.

    Signed-off-by: Brian L. Troutwine [email protected]

    opened by blt 0
  • Collect a list of known defects

    Collect a list of known defects

    Any bug searching technique lives and dies by its ability to find, well, bugs. To judge how well our approach is doing in this project we need a list of known defects. That is:

    • details / bug issue number
    • [optional] method to reproduce
    • impacted version(s) of Rust

    From this we can start to build a table of Time to Discovery for the given issue.

    opened by blt 1
  • Resolve OOM panics

    Resolve OOM panics

    As detailed in this post hunting for bugs is hampered right now because of Rust's panic strategy around allocation failures. We should introduce techniques to avoid these panics, related issues of edge-cases being masked by OOM panics.

    opened by blt 2
  • Thoughts on README in no particular order

    Thoughts on README in no particular order

    Opening an issue because github doesn't provide a better communication mechanism. Hopefully some of these points are actionable.

    Downside is, the std data structures we're testing don't have any sanitizers turned on etc on account of the project is run against the usual Rust releases.

    libdislocator can catch many (but not all) memory errors for black-box binaries, assuming they use the system allocator.

    Rust sanitizer integration lists steps to rebuild stdlib with sanitizer support, but calls it "better backtraces". We might want to get in touch and check how exactly sanitizers can be enabled for stdlib primitives.

    This project will happily take fuzz code. Or, if someone could contrive to combine a fuzzer with a shrinking step this project will jump on that in a heartbeat.

    Both AFL and libfuzzer shrink the inputs as they go along. They have Rust integration as afl.rs and cargo-fuzz respectively. Both have a one-shot testcase minimization command, which doesn't usually do a great job. However, AFL also comes with a crash exploration mode lets you explore alternative crashing inputs and minimize the testcase to your heart's content.

    Also, Rust QuickCheck README mentions proptest as an alternative to QuickCheck that improves on shrinking and links to some comparisons of the two.

    opened by Shnatsel 26
Owner
Brian L. Troutwine
Brian L. Troutwine
A utility like pkg-audit for Arch Linux. Based on Arch Security Team data.

arch-audit pkg-audit-like utility for Arch Linux. Based on data from security.archlinux.org collected by the awesome Arch Security Team. Installation

Andrea Scarpino 316 Nov 22, 2022
Kepler is a vulnerability database and lookup store and API currently utilising National Vulnerability Database and NPM Advisories as data sources

Kepler — Kepler is a vulnerability database and lookup store and API currently utilising National Vulnerability Database and NPM Advisories as data so

Exein.io 101 Nov 12, 2022
Rust library for building and running BPF/eBPF modules

RedBPF A Rust eBPF toolchain. Overview The redbpf project is a collection of tools and libraries to build eBPF programs using Rust. It includes: redbp

foniod 1.5k Jan 1, 2023
Rust library for developing safe canisters.

IC Kit This library provides an alternative to ic-cdk that can help developers write canisters and unit test them in their Rust code. Install Add this

Psychedelic 26 Nov 28, 2022
Advanced Fuzzing Library - Slot your Fuzzer together in Rust! Scales across cores and machines. For Windows, Android, MacOS, Linux, no_std, ...

LibAFL, the fuzzer library. Advanced Fuzzing Library - Slot your own fuzzers together and extend their features using Rust. LibAFL is written and main

Advanced Fuzzing League ++ 1.2k Jan 6, 2023
Mundane is a Rust cryptography library backed by BoringSSL that is difficult to misuse, ergonomic, and performant (in that order).

Mundane Mundane is a Rust cryptography library backed by BoringSSL that is difficult to misuse, ergonomic, and performant (in that order). Issues and

Google 1.1k Jan 3, 2023
A simple rust library for working with ZIP archives

rust-zip A simple rust library to read and write Zip archives, which is also my pet project for learning Rust. At the moment you can list the files in

Jorge Gorbe Moya 11 Aug 6, 2022
An attempt to rewrite lite-client for TON Blockchain in Rust using ton-labs-adnl library.

An attempt to rewrite lite-client for TON Blockchain in Rust using ton-labs-adnl library.

TonStack 4 Nov 9, 2022
A new shellcode injection technique. Given as C++ header, standalone Rust program or library.

FunctionStomping Description This is a brand-new technique for shellcode injection to evade AVs and EDRs. This technique is inspired by Module Stompin

Ido Veltzman 608 Jan 4, 2023
Extended precision integer Rust library. Provides signed/unsigned integer 256 to 2048.

Extended precision integer Rust library. Provides signed/unsigned integer 256 to 2048.

Mohanson 4 Jul 28, 2022
Linux anti-debugging and anti-analysis rust library

DebugOff Library Linux anti-analysis Rust library The goal of this library is to make both static and dynamic (debugging) analysis more difficult. The

null 65 Jan 7, 2023
An R interface to Rust's h3o library

h3o h3o is a system-dependency free package to interact with the H3 Geospatial Indexing system by Uber. h3o utilizes the Rust library h3o with is a pu

Josiah Parry 5 Mar 27, 2023
A rust library for sharing and updating arbitrary slices between threads, optimized for wait-free reads

atomicslice A Rust library for thread-safe shared slices that are just about as fast as possible to read while also being writable. Overview Use Atomi

Tim Straubinger 5 Dec 6, 2023
unfuck is a utility and library for deobfuscating obfuscated Python 2.7 bytecode

unfuck is a utility and library for deobfuscating obfuscated Python 2.7 bytecode. It is essentially a reimplementation of the Python VM with taint tracking.

Lander Brandt 171 Dec 14, 2022
Xori is an automation-ready disassembly and static analysis library for PE32, 32+ and shellcode

Xori - Custom disassembly framework Xori is an automation-ready disassembly and static analysis library that consumes shellcode or PE binaries and pro

ENDGAME 712 Nov 28, 2022
Cross-platform async library for system information fetching 🦀

heim Cross-platform library for system information fetching heim is an ongoing attempt to create the best tool for system information fetching (ex., C

null 782 Jan 2, 2023
Memory hacking library for windows.

Memory hacking library for windows.

sy1ntexx 40 Jan 3, 2023
A library for building tools to determine if vulnerabilities are reachable in a code base.

Overview Vuln Reach is a library for developing tools that determine if a given vulnerability is reachable. Provided to the open source community by P

Phylum 3 May 5, 2023
Detects usage of unsafe Rust in a Rust crate and its dependencies.

cargo-geiger ☢️ Looking for maintainer: https://github.com/rust-secure-code/cargo-geiger/issues/210 A program that lists statistics related to the usa

Rust Secure Code Working Group 1.1k Jan 4, 2023