Optimize to speed up the gadget finder

[lieanu]

A comparison between rop-tool, ROPgadget, BARFgadget when used to find gadgets in libc.so.6.

rop-tools(written in c):
1229 gadgets found.
rop-tool gadget libc.so.6 17.29s user 0.01s system 100% cpu 17.289 total

ROPgadget:
Unique gadgets found: 21240
ROPgadget --binary libc.so.6 72.30s user 10.25s system 99% cpu 1:22.82 total

BARFgadget:
Find Stage : 358.472s
Classification Stage : 854.280s
Verification Stage : 377.223s
Total : 1589.976s

Suggestion:

• BARFgadget should not translate instructions to REIL when finding gadgets, It cost too much time.

[cnheitman]

Hi!

As you mention it takes a while for BARFgadgets to process a file, there are several reasons for that.

Regarding your suggestion, it is not possible to remove translation from the finding stage. The REIL translation (for each gadget) is necessary for the subsequent stages: classification and verification.

However, there's plenty of room for optimizations (in all 3 stages). The finding stage can be improved significantly. The main problem is not the translation itself but some parts of the disassembling process, which can be fixed with a better integration between BARF and Capstone. Also, the process of finding and building gadgets can be improved. The classification stage can be tuned for performance too. The last stage is a bit more complicated as the time is dominated by the solver (you may use CVC4 that, in some cases, performs better than Z3, for example, in memory-related gadgets.)

Performance improvements are in the TODO list, particularly, better integration between BARF and Capstone (I think this can have a significant impact on the time it takes the entire finding stage).

If you are interesting in contributing to any of these issues, let me know. I can explain further each of the above mentioned issues.

[lieanu]

Hey,

I find gadgets in way now as follows, it saved some time, 358s to about 70s:

• Using ROPgadget's way
• Convert gadgets into REIL now.

I am also interesting in optimzing the performance of classification stage. Can you give me some suggestion?
Where is the performance bottleneck of this stage?

[cnheitman]

There is quick way to accelerate the classification stage. The classification of each gadget is done in the following way. The gadget is executed using the REIL emulator with a randomly generated context. After running, the final context is compared to the initial context. This is done in order to know what has changed and in which way. This process is repeated several times. If those changes are consistent then with a certain classification the gadget is ready to move on to the next stage (verification), otherwise it's discarded. Currently, this process is done 10 times (self._emu_iters = 10). This can be tuned in order to increase or decrease precision. If you decrease it to much there's a high change you accept gadgets in the last stage that will be probably rejected (because it was misclassified) and this cost time at the SMT solver level (which can be higher). In conclusion, it a good time to revise this parameter and tune it.

Other improvements include rewriting some of the classification functions. If take a look at the code you'll see that most of them iterates through all registers (in order to guest what operation is computed by a specific gadget) when they can only iterate modified ones. This has no impact when you have just a few gadgets to classify but when you have thousands it can take some time.

Check those two and let me know how it goes. We can then see other options.

Cheers!