Byte-Taint Resonance Imaging (ByteRI)

Byte-Taint Resonance Imaging (ByteRI) for Binary Executables is a dynamic taint-analysis based technique that individually taints each input byte and traces the flow of these bytes through the program, much like an MRI scan with contrast. For each instruction within the program, ByteRI keeps a record of the taints of the input bytes that were seen to impact the instruction’s execution.  These accumulated taints at each instruction can be used to automatically identify modules in a program, determine which bytes of the input affect which branches, and, most importantly, automatically discover the syntactic structure of the input. In other words, just as MRI scans construct detailed pictures of its soft tissues, providing substantial diagnostic and prognostic information to a doctor, ByteRI scans a binary executable to construct detailed pictures to aid a reverse engineer in identifying the program’s ‘organs’ and ‘tissues’, to diagnose a program for vulnerabilities, and to prognosticate exploits.  ByteRI may be integrated with disassemblers like GHIDRA or IDA Pro to drastically decrease the time it takes to reverse engineer unknown binaries. It may also be integrated with the American Fuzzy Lop (AFL) fuzzer to enable effective fuzzing of programs that have structured input forms – a key challenge for the current generation of fuzzers – without requiring the use of complex theorem provers to solve constraints on the data and execution paths.