Skip to content

Some C++ example code to demonstrate how to perform code similarity searches using MinHashing of small subgraphs

License

Notifications You must be signed in to change notification settings

balzarot/functionsimsearch

 
 

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

18 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

FunctionSimSearch

FunctionSimSearch - Example C++ code to demonstrate how to do MinHash-based similarity search over CFGs extracted from disassemblies.

Getting Started

These instructions will get you a copy of the project up and running on your local machine for development and testing purposes.

Prerequisites

This code has a few external dependencies. The dependencies are:

Installing

You should be able to build the code by doing the following:

  1. Download, build and install DynInst 9.3
  2. Get the dependencies:
mkdir third_party
cd third_party
git clone https://github.com/okdshin/PicoSHA2.git
git clone https://github.com/trailofbits/pe-parse.git
cd pe-parse
cmake ./CMakeLists
make
cd ../..
make

This should build the relevant executables to try.

Running the tests

There are no tests yet. This will change eventually, most likely using gtest.

Running the tools

At the moment, the following executables will be built:

disassemble

./disassemble ELF /bin/tar
./disassemble PE ~/sources/mpengine/engine/mpengine.dll

Disassemble the specified file and dump the disassembly to stdout. The input file can either be a 32-bit/64-bit ELF, or a 32-bit PE file. Adding support for 64-bit PE is easy and will be done soon.

dotgraphs

./dotgraphs ELF /bin/tar /tmp/graphs
./dotgraphs PE ~/sources/mpengine/engine/mpengine.dll /tmp/graphs

Disassemble the specified file and write the CFGs as dot files to the specified directory.

graphhashes

./graphhashes ELF /bin/tar /tmp/graphs
./graphhashes PE ~/sources/mpengine/engine/mpengine.dll /tmp/graphs

Disassemble the specified file and write a hash of the CFG structure of each disassembled function to stdout. These hashes encode only the graph structure and completely ignore any mnemonic; as such they are not very useful on small graphs.

createfunctionindex

./createfunctionindex ./function_search.index

Creates a new search index to store function fingerprints in. The code currently creates 1 GB file (which should be plenty for the casual reverse engineer). Adjust the source code if you need more / less storage.

addfunctionstoindex

./addfunctionstoindex ELF /bin/tar ./function_search.index 5
./addfunctionstoindex PE ~/sources/mpengine/engine/mpengine.dll ./function_search.index 5

Disassemble the specified input file, and add every function with more than 5 basic blocks to the search index file.

matchfunctionsfromindex

./matchfunctionsfromindex ELF /bin/tar ./function_search.index 5 10 .90
./matchfunctionsfromindex PE ~/sources/mpengine/engine/mpengine.dll ./function_search.index 5 10 .90

Disassemble the specified input file, and for each function with more than 5 basic blocks, retrieve the top-10 most similar functions from the search index. Each match must be at least 90% similar.

Built With

  • DynInst - Used to generate disassemblies
  • Boost - Boost for persistent map and set containers

Authors

License

This project is licensed under the Apache 2.0 License - see the LICENSE file for details

About

Some C++ example code to demonstrate how to perform code similarity searches using MinHashing of small subgraphs

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages

  • C++ 96.7%
  • Makefile 2.5%
  • Shell 0.8%