6 ms·

Neural Nets Can Learn Function Type Signatures from Binaries [pdf]

213 points by bmc7505 9y ago

dmix 9y ago
TLDR: > In this paper, we present a new system called EKLAVYA which trains a recurrent neural network to recover function type signatures from disassembled binary code. EKLAVYA assumes no knowledge of the target instruction set semantics to make such inference. > [..] we find by analyzing its model that it auto-learns relationships between instructions, compiler conventions, stack frame setup instructions, use-before-write patterns, and operations relevant to identifying types directly from binaries. > In our evaluation on Linux binaries compiled with clang and gcc, for two different architectures (x86 and x64), EKLAVYA exhibits accuracy of around 84% and 81% for function argument count and type recovery tasks respectively.
- self_awareness 9y ago
  > "On our x86 and x64 datasets, EKLAVYA exhibits comparable accuracy with traditional heuristics-based methods"
ma2rten 9y ago
I've long had this idea to build a decompiler (a program that maps binaries back to source code) using machine learning. The problem in decompilation is that you loose information when you compile source code. Machine learning could help even recover things like most likely variable names. There is also tons of training data that can be easily generated.
- arnioxux 9y ago
  > recover things like most likely variable names This is already being researched! See http://jsnice.org/ http://jsnice.org/ for recovering variable names from minified javascript. I remember testing it by coding a binary search with single letter variable names. It managed to rename them to the more canonical "lo"/"mid"/"hi" names just by recognizing that the code pattern is typically used for a binary search.
  - fapjacks 9y ago
    I was just about to post a link! Very interesting project, and the folks behind jsnice are super cool, too.
- jayajay 9y ago
  It would be interesting to automatically generate the training data and feed it to the ML module in real time. You could hard-code an interactive agent that periodically peeked and coerced the input (between itself and the ML function). This way the ML module is coercible. It would even be more cool if the ML function itself learned the interactive agent function as part of itself.
- noonespecial 9y ago
  I've had the same idea, but instead it could "decompile" spaghetti code with horrible variable names into something readable. It seems like a reasonable (almost believable even) first stage to software finally coming to eat the jobs of its creators.
  - Swizec 9y ago
    Our jobs will just move an abstraction level higher. We used to have to worry about registers and stuff, then we automated that. We used to worry about memory, then we automated that. We used to worry about CPU stuff, then we automated that for most applocations. Eventually we're going to become technical PMs. As long as there will be fuzzy unclear problem descriptions, there will be jobs for people who can codify and standardize processes.
    - haikuginger 9y ago
      "First they came for the assembly programmers..."
      - Filligree 9y ago
        "And then they ate the universe, and there was no-one left to care." Plenty of paperclips, though.
    - jhayward 9y ago
      > Our jobs will just move an abstraction level higher. This seems a little optimistic in terms of the average software developer's ability to think at higher and higher levels of abstraction. It's not an easy skill, and not that many people are very strong in it. Just look at how programmers today react to mathematical paradigms and explanations (category theory, anyone) in any practical setting.
    - wbl 9y ago
      You say that, but I've written software unrolled loops in assembler on ARM because that's what we needed.
- moyix 9y ago
  Cast it as a reinforcement learning problem: you produce a candidate decompilation, try to compile it, and score it based on the similarity to the initial binary.
- visarga 9y ago
  In a completely different approach, a neural net was trained on input-output pairs and stack traces of a program. The neural net learned the algorithm. The advantage is that all algorithms could be "neuralized".
  - nradov 9y ago
    How is that an advantage?
    - 0xdeadbeefbabe 9y ago
      The neuralized algorithms become really hard to debug? I think of it as a magicians curtain.
- jameshart 9y ago
  Neural nets can't magically create information that's not there; all it can do is combine the data in the binary with its learned 'experience', and make what amounts to educated guesses about what the decompiled code might be. That has value, obviously, but it's not 'recovering' anything, really, it's 'assuming'.
  - scarmig 9y ago
    Or possibly improving upon. A variable being badly named isn't rare.
    - devdoomari 9y ago
      yep that with a auto-spell checker would make a darn good tool! something like MS word spell checker that goes suggestion-by-suggestion and clicking yes/no/manual for var names :)
- UncleMeat 9y ago
  There's been dozens of such projects at this point. http://apk-deguard.com/ http://apk-deguard.com/ is one example.
haberman 9y ago
This would only be useful for binaries where you don't have corresponding source, but the binary does still have symbols. Is this a common situation?
- jdblair 9y ago
  Its usually all you get if you are reverse engineering someone else's executable or firmware image.
  - haberman 9y ago
    But they leave symbols in? They don't strip those also?
    - sillysaurus3 9y ago
      Indeed. If you start Emacs on OSX and run `symbols Emacs`, you get a lot of info: 100139190 ( 0x90) verror [FUNC, EXT... 100139220 ( 0x210) Fcommandp [FUNC, ... 100139430 ( 0xf0) Fautoload [FUNC, ... 100139520 ( 0x90) un_autoload [FUNC... 1001395b0 ( 0x80) Feval [FUNC, EXT,... 100139630 ( 0x50) record_in_backtra... 100139680 ( 0x1d0) apply_lambda [FUN... 100139850 ( 0x390) Fapply [FUNC, EXT... 100139be0 ( 0x5c0) Ffuncall [FUNC, E... 10013a1a0 ( 0x90) Frun_hooks [FUNC,... 10013a230 ( 0x1d0) run_hook_with_arg... 10013a400 ( 0x20) funcall_nil [FUNC... 10013a420 ( 0x20) Frun_hook_with_ar... 10013a440 ( 0x20) Frun_hook_with_ar... 10013a460 ( 0x30) Frun_hook_with_ar... 10013a490 ( 0x30) funcall_not [FUNC... So why not strip these? Well, you can't. But the reason is interesting. Most programs run by using shared libraries, and these libraries need to provide a standard API that other programs can use. Hence the function names. Which of course is exactly the info that a hypothetical bad guy needs to make sense of the program. But it goes beyond this. You could imagine statically linking a program against all of its dependencies, then stripping all possible symbols. The thing is, there is plenty of info in the binary to make sense of the program. Strings, for example. Error messages. Every piece of data you want to show to the user is an indication of what the surrounding function is doing. IDA Pro is pretty incredible in that situation. Each time you figure out what a function is doing, you just give it whatever name you want. IDA updates the whole interface so that it uses that name everywhere, instead of the hex address. You end up with a neat, perfectly sensible program. Entire game engines have been meticulously reverse engineered this way. However, viruses use a crafty technique to prevent analysis. You encrypt your program like an onion. Your outer program runs, and everyone can see that. But it's carrying around a blob of functionality that was encrypted using the target's information. E.g. their MAC address, or a subset of their list of installed programs, or anything that would uniquely identify your target separately from everyone else. Any time the virus is installed anywhere, it tries to decrypt itself using this information, which only succeeds when it's installed on the target machine. This defeats all attempts at analysis. You can't analyze what you can't decrypt.
placebo 9y ago
I've often wondered about the theoretical limit of a neural net to learn from examples - seems like a fascinating subject with a lots of implications. From a quick search, I found this paper: https://experts.illinois.edu/en/publications/computational-limitations-on-learning-from-examples https://experts.illinois.edu/en/publications/computational-l... which is already very interesting. Are there any other good pointers on this?
- bmc7505 9y ago
  According to the universal approximation theorem [1], a multilayer feedforward net with a single hidden layer can approximate any continuous function on R^n. There's also a nice visual proof. [2] [1]: http://www.sciencedirect.com/science/article/pii/0893608089900208 http://www.sciencedirect.com/science/article/pii/08936080899... [2]: http://neuralnetworksanddeeplearning.com/chap4.html http://neuralnetworksanddeeplearning.com/chap4.html
  - drdeca 9y ago
    Are there also theorems about what functions can be learned, or how quickly they can be learned, by a multilayer feed forward neural net using backpropagation?
    - jackpirate 9y ago
      Yes, they use what's called the VC-dimension. Chapter 20 of the book Understanding Machine Learning (available for free online http://www.cs.huji.ac.il/~shais/UnderstandingMachineLearning/ http://www.cs.huji.ac.il/~shais/UnderstandingMachineLearning...) has a good introduction to the basics of this theory. The short story is that VC dimension describes "worst case" behavior of a learning algorithm. This is a good predictor of performance on really hard problems, but lots of modern problems turn out to be theoretically easy. For example, neural networks trained on images work much better than we would guess based on the VC dimension of neural networks. This is because the distribution of images is closer to a best case scenario than a worst case scenario. Lots of research is being done to determine when we are in a best case scenario. The "simplest" is called the Rademacher complexity. (See Chapter 26 of the UML book.) Simplest is in quotes because most phd-level students in machine learning that I've met don't even understand what a rademacher complexity is unless they are specializing in theory. And the rademacher complexity doesn't really even come close to capturing why neural networks work well on images either.
incompatible 9y ago
COTS = "Common off the shelf", in case anyone is equally mystified. Google wasn't immediately helpful.
- w_t_payne 9y ago
  Commercial Off The Shelf, I thought.
  - vog 9y ago
    Indeed, it is "Commercial Off The Shelf". I sometimes saw this in marketing speech, too.
    - incompatible 9y ago
      Apparently "Consumer Off-The-Shelf" is another variant.
deleted 9y ago
[deleted]
deleted 9y ago
[deleted]
therandomoracle 9y ago
The authors have put out the datasets: https://github.com/shensq04/EKLAVYA https://github.com/shensq04/EKLAVYA

213 points by bmc7505 9y ago

dmix 9y ago

TLDR: > In this paper, we present a new system called EKLAVYA which trains a recurrent neural network to recover function type signatures from disassembled binary code. EKLAVYA assumes no knowledge of the target instruction set semantics to make such inference. > [..] we find by analyzing its model that it auto-learns relationships between instructions, compiler conventions, stack frame setup instructions, use-before-write patterns, and operations relevant to identifying types directly from binaries. > In our evaluation on Linux binaries compiled with clang and gcc, for two different architectures (x86 and x64), EKLAVYA exhibits accuracy of around 84% and 81% for function argument count and type recovery tasks respectively.

self_awareness 9y ago
> "On our x86 and x64 datasets, EKLAVYA exhibits comparable accuracy with traditional heuristics-based methods"

ma2rten 9y ago

I've long had this idea to build a decompiler (a program that maps binaries back to source code) using machine learning. The problem in decompilation is that you loose information when you compile source code. Machine learning could help even recover things like most likely variable names. There is also tons of training data that can be easily generated.

arnioxux 9y ago
> recover things like most likely variable names This is already being researched! See http://jsnice.org/ http://jsnice.org/ for recovering variable names from minified javascript. I remember testing it by coding a binary search with single letter variable names. It managed to rename them to the more canonical "lo"/"mid"/"hi" names just by recognizing that the code pattern is typically used for a binary search.
- fapjacks 9y ago
  I was just about to post a link! Very interesting project, and the folks behind jsnice are super cool, too.
jayajay 9y ago
It would be interesting to automatically generate the training data and feed it to the ML module in real time. You could hard-code an interactive agent that periodically peeked and coerced the input (between itself and the ML function). This way the ML module is coercible. It would even be more cool if the ML function itself learned the interactive agent function as part of itself.
noonespecial 9y ago
I've had the same idea, but instead it could "decompile" spaghetti code with horrible variable names into something readable. It seems like a reasonable (almost believable even) first stage to software finally coming to eat the jobs of its creators.
- Swizec 9y ago
  Our jobs will just move an abstraction level higher. We used to have to worry about registers and stuff, then we automated that. We used to worry about memory, then we automated that. We used to worry about CPU stuff, then we automated that for most applocations. Eventually we're going to become technical PMs. As long as there will be fuzzy unclear problem descriptions, there will be jobs for people who can codify and standardize processes.
  - haikuginger 9y ago
    "First they came for the assembly programmers..."
    - Filligree 9y ago
      "And then they ate the universe, and there was no-one left to care." Plenty of paperclips, though.
  - jhayward 9y ago
    > Our jobs will just move an abstraction level higher. This seems a little optimistic in terms of the average software developer's ability to think at higher and higher levels of abstraction. It's not an easy skill, and not that many people are very strong in it. Just look at how programmers today react to mathematical paradigms and explanations (category theory, anyone) in any practical setting.
  - wbl 9y ago
    You say that, but I've written software unrolled loops in assembler on ARM because that's what we needed.
moyix 9y ago
Cast it as a reinforcement learning problem: you produce a candidate decompilation, try to compile it, and score it based on the similarity to the initial binary.
visarga 9y ago
In a completely different approach, a neural net was trained on input-output pairs and stack traces of a program. The neural net learned the algorithm. The advantage is that all algorithms could be "neuralized".
- nradov 9y ago
  How is that an advantage?
  - 0xdeadbeefbabe 9y ago
    The neuralized algorithms become really hard to debug? I think of it as a magicians curtain.
jameshart 9y ago
Neural nets can't magically create information that's not there; all it can do is combine the data in the binary with its learned 'experience', and make what amounts to educated guesses about what the decompiled code might be. That has value, obviously, but it's not 'recovering' anything, really, it's 'assuming'.
- scarmig 9y ago
  Or possibly improving upon. A variable being badly named isn't rare.
  - devdoomari 9y ago
    yep that with a auto-spell checker would make a darn good tool! something like MS word spell checker that goes suggestion-by-suggestion and clicking yes/no/manual for var names :)
UncleMeat 9y ago
There's been dozens of such projects at this point. http://apk-deguard.com/ http://apk-deguard.com/ is one example.

haberman 9y ago

This would only be useful for binaries where you don't have corresponding source, but the binary does still have symbols. Is this a common situation?

jdblair 9y ago
Its usually all you get if you are reverse engineering someone else's executable or firmware image.
- haberman 9y ago
  But they leave symbols in? They don't strip those also?
  - sillysaurus3 9y ago
    Indeed. If you start Emacs on OSX and run `symbols Emacs`, you get a lot of info: 100139190 ( 0x90) verror [FUNC, EXT... 100139220 ( 0x210) Fcommandp [FUNC, ... 100139430 ( 0xf0) Fautoload [FUNC, ... 100139520 ( 0x90) un_autoload [FUNC... 1001395b0 ( 0x80) Feval [FUNC, EXT,... 100139630 ( 0x50) record_in_backtra... 100139680 ( 0x1d0) apply_lambda [FUN... 100139850 ( 0x390) Fapply [FUNC, EXT... 100139be0 ( 0x5c0) Ffuncall [FUNC, E... 10013a1a0 ( 0x90) Frun_hooks [FUNC,... 10013a230 ( 0x1d0) run_hook_with_arg... 10013a400 ( 0x20) funcall_nil [FUNC... 10013a420 ( 0x20) Frun_hook_with_ar... 10013a440 ( 0x20) Frun_hook_with_ar... 10013a460 ( 0x30) Frun_hook_with_ar... 10013a490 ( 0x30) funcall_not [FUNC... So why not strip these? Well, you can't. But the reason is interesting. Most programs run by using shared libraries, and these libraries need to provide a standard API that other programs can use. Hence the function names. Which of course is exactly the info that a hypothetical bad guy needs to make sense of the program. But it goes beyond this. You could imagine statically linking a program against all of its dependencies, then stripping all possible symbols. The thing is, there is plenty of info in the binary to make sense of the program. Strings, for example. Error messages. Every piece of data you want to show to the user is an indication of what the surrounding function is doing. IDA Pro is pretty incredible in that situation. Each time you figure out what a function is doing, you just give it whatever name you want. IDA updates the whole interface so that it uses that name everywhere, instead of the hex address. You end up with a neat, perfectly sensible program. Entire game engines have been meticulously reverse engineered this way. However, viruses use a crafty technique to prevent analysis. You encrypt your program like an onion. Your outer program runs, and everyone can see that. But it's carrying around a blob of functionality that was encrypted using the target's information. E.g. their MAC address, or a subset of their list of installed programs, or anything that would uniquely identify your target separately from everyone else. Any time the virus is installed anywhere, it tries to decrypt itself using this information, which only succeeds when it's installed on the target machine. This defeats all attempts at analysis. You can't analyze what you can't decrypt.

placebo 9y ago

I've often wondered about the theoretical limit of a neural net to learn from examples - seems like a fascinating subject with a lots of implications. From a quick search, I found this paper: https://experts.illinois.edu/en/publications/computational-limitations-on-learning-from-examples https://experts.illinois.edu/en/publications/computational-l... which is already very interesting. Are there any other good pointers on this?

bmc7505 9y ago
According to the universal approximation theorem [1], a multilayer feedforward net with a single hidden layer can approximate any continuous function on R^n. There's also a nice visual proof. [2] [1]: http://www.sciencedirect.com/science/article/pii/0893608089900208 http://www.sciencedirect.com/science/article/pii/08936080899... [2]: http://neuralnetworksanddeeplearning.com/chap4.html http://neuralnetworksanddeeplearning.com/chap4.html
- drdeca 9y ago
  Are there also theorems about what functions can be learned, or how quickly they can be learned, by a multilayer feed forward neural net using backpropagation?
  - jackpirate 9y ago
    Yes, they use what's called the VC-dimension. Chapter 20 of the book Understanding Machine Learning (available for free online http://www.cs.huji.ac.il/~shais/UnderstandingMachineLearning/ http://www.cs.huji.ac.il/~shais/UnderstandingMachineLearning...) has a good introduction to the basics of this theory. The short story is that VC dimension describes "worst case" behavior of a learning algorithm. This is a good predictor of performance on really hard problems, but lots of modern problems turn out to be theoretically easy. For example, neural networks trained on images work much better than we would guess based on the VC dimension of neural networks. This is because the distribution of images is closer to a best case scenario than a worst case scenario. Lots of research is being done to determine when we are in a best case scenario. The "simplest" is called the Rademacher complexity. (See Chapter 26 of the UML book.) Simplest is in quotes because most phd-level students in machine learning that I've met don't even understand what a rademacher complexity is unless they are specializing in theory. And the rademacher complexity doesn't really even come close to capturing why neural networks work well on images either.

incompatible 9y ago

COTS = "Common off the shelf", in case anyone is equally mystified. Google wasn't immediately helpful.

w_t_payne 9y ago
Commercial Off The Shelf, I thought.
- vog 9y ago
  Indeed, it is "Commercial Off The Shelf". I sometimes saw this in marketing speech, too.
  - incompatible 9y ago
    Apparently "Consumer Off-The-Shelf" is another variant.

deleted 9y ago

[deleted]

deleted 9y ago

[deleted]

therandomoracle 9y ago

The authors have put out the datasets: https://github.com/shensq04/EKLAVYA https://github.com/shensq04/EKLAVYA