MykolaFedurko
A binary search tree with one malformed branch under inspection
View source on GitHubB1Z0N/RustBSTSoftwareSecurity

labsecuritysystemsacademic

Rust BST Software Security

Rust correctness and fuzzing laboratory.
  • Rust
  • AFL++
  • Fuzzing
  • Testing
Date
April 2023
Status
Historical
Visibility
Public

This is my Rust software security assignment from my major at the University of Twente. I was supposed to write, test and secure by all means my implementation of a binary search tree and its CLI interface.

I had done basic BSTs before, during my bachelor and further career, but this time it was Rust and security specific — so it was interesting to grasp Rust’s approach of drastically limiting the range of possible programs with its type system, eliminating the malicious ones along the way.

The interface

The tree folder holds the tree itself; main reads instructions from stdin and updates or dumps it. The command language is small:

i <age:int> <name:string>   insert an element
e <age:int> <name:string>   erase the element with equal data
c <age:int> <name:string>   print "y" if the element exists, "n" otherwise
p                           dump the tree as [<data>,<left>,<right>], nulls included
x                           reset to a fresh empty tree
q                           exit

A dump prints each element as {"<age>":"<name>"}, so a small tree comes out as [{"5":"foo"},[{"3":"bar"},null,null],null], and an empty one as null.

Testing and fuzzing

Beyond cargo test and the two shell test scripts, the interesting part was fuzzing. I built the binary for AFL++ with ./afl.build.sh and let ./afl.sh run against the command interface. Almost 10 hours of fuzzing found no bugs:

Almost ten hours of AFL++ fuzzing with no crashes or hangs found

I also fuzzed it for a couple of minutes with AFL_USE_MSAN=1 — no errors found there either. The fuzzing output lives in the repo’s /fuzz/output directory.