5 ms·

Searching statically-linked vulnerable library functions in executable code

150 points by matt_d 8y ago

a-dub 8y ago
I always wondered if AV databases were just minhashing/lsh on binaries... guess not!
- loeg 8y ago
  Hah, no. AV databases are just real dumb tries of whole-file MD5s, or a similar level of sophistication (i.e., not very). Usually combined with an unnecessarily privileged and unsandboxed parser for arbitrary weird file formats.
  - a-dub 8y ago
    Looking for vulny binary code in terms of jaccard similarity is interesting.
  - landr0id 8y ago
    ssdeep is also used https://www.forensicswiki.org/wiki/Ssdeep https://www.forensicswiki.org/wiki/Ssdeep
Jacoe 8y ago
What am I reading haha.
- puzzle 8y ago
  The article makes more sense if you consider that Google is notorious for statically linking (almost) all its production binaries, something that the Go toolchain supported early on for related reasons.
  - CaliforniaKarl 8y ago
    I’m guessing it’s also related to the recent SQLite zero-day. SQLite is public-domain, and so it’s not unusual for projects to simply include the code directly in their source distributions, which will either build it in or will provide a `./configure` option to use an already-built form (this is used by distro packagers). When the “build it in” option is used, then it’s statically linked.
    - tptacek 8y ago
      I think Thomas Dullien has been working on this stuff for a very long time; his company, Zynamics, which Google acquired ages ago, was the author of BinDiff.
  - devereaux 8y ago
    There I many things I disagree about with Google, but statically linking binaries is a good practice if you know what you are doing and have a central repository where you handle your own versions of everything. You can not always rely on linux distribution to not mess up with a lib, especially if it "obscure" with few users.
RobLach 8y ago
Very cool.
tomjakubowski 8y ago
> An efficient implementation of a hash function (based on SimHashing) which calculates a 128-bit hash from disassembled functions - and which preserves similarity (e.g. “distance” of two functions can be calculated by simply calculating the hamming distance between two hashes - which translates to two XOR and two POPCNT instructions on x64). Huh! This obviously desirable property of a good hash function for this application is one of the classic undesirable properties of a good hash function for cryptography. I don't think that I was previously familiar with this sort of hash function, very cool. Are space-filling curves related to these hash functions?
- viraptor 8y ago
  Another hash with a similar property uses close pronunciation as distance: https://en.m.wikipedia.org/wiki/Soundex https://en.m.wikipedia.org/wiki/Soundex
  - simcop2387 8y ago
    Soundex however is only designed for English names. Take a look at Metaphone or Double-Metaphone for a more generic version of the same idea. https://en.wikipedia.org/wiki/Metaphone https://en.wikipedia.org/wiki/Metaphone
- tylersmith 8y ago
  Not all hashes are intended for cryptographic applications or want the Avalanche effect. Some are simply succinct digests of data and some attempt to retain important information like the hash described here.
- livueta 8y ago
  Another example of this sort of hash function (where the hamming distance between the hashes of similar inputs will be small) is pHash[1]. I've been playing with it recently for deduping bit-different but perceptually-identical images, and it works pretty well and the low hamming distance property makes it dead simple to use. --- [1] https://www.phash.org/ https://www.phash.org/
- 8y ago
nineteen999 8y ago
This is probably a good thing, given the recent trend in languages like Golang and Rust to statically link binaries by default.
- devereaux 8y ago
  I do not understand the hate towards statically linked binaries. It has its place for mission critical tools.
  - regecks 8y ago
    I feel like it's pretty easy to understand the hate. For example, the recent x.509 verification DoS patched in <Go1.11.3 required me to recompile, tag and redeploy bunch of services. And then also push an RPM to thousands of customer servers, which costs me CDN money :(. I would have preferred for myself, and my customers to just upgrade openssl. I am still a big fan of static binaries though, they more than make up for their downsides.
  - viraptor 8y ago
    Very specific tools, sure. If you have the time, people, and skills to keep your own list of baked-in dependencies and monitor it for issues - great. But for a random person downloading something from the internet, it's a dangerous thing to default to.
    - devereaux 8y ago
      I agree. It is a double edge sword. It requires skill and proper analysis. I should have been more specific. I explained my reason below on https://news.ycombinator.com/item?id=18713442 https://news.ycombinator.com/item?id=18713442
      - ex_amazon_sde 8y ago
        Even FAANG companies rely on distributions and other companies to spot vulnerabilities, rebuild libraries, test and validate them. Even if the company rebuilds everything, there's a huge benefit in knowing that you are using a well tested release instead of a less popular one or an internal fork. Also: security teams hate big security patches.
devereaux 8y ago
The zlib vulnerability was a huge wakeup call. Years ago I used to be in favor of statically linked, to limit dependency creep. Disk space is cheap so large binaries were never a concern. My favorite approach was single repository compiling optimized binaries with the specific versions of the libs wanted (in case of weird regression) and pushing these static binaries to the rest of the network. After the zlib debacle, no more: I only use that approach for very specific mission critical tools, where I do not trust ansible or even linux distributions. The sqlite 0 day may have reignited the same fears in those too young to remember grepping various zlib signatures on binaries -not just yours (you central repository can easily push new version to your network) but the other tools you don't necessary control.
- flukus 8y ago
  Unfortunately outside of linux distros static linking seems to be becoming more and more then new norm, especially if you include what is effectively "soft" static linking of bundling all dependencies, which suffer from the same problems. Rust is only suitable for static linking, .net core statically links and most .net projects will have all sorts of out of date dependencies, npm bundles huge dependency chains that may not be upgraded. Even in the linux distro world there is movement towards tools like docker where dependencies will often not be patched. Even the idea of stable versions of libraries with security patches seems to be a dieing one.
  - whyever 8y ago
    > Rust is only suitable for static linking This is incorrect, Rust supports dynamic linking. https://doc.rust-lang.org/reference/linkage.html https://doc.rust-lang.org/reference/linkage.html
    - flukus 8y ago
      It supports it terribly. Since there's no stable ABI you have to use the same compiler version. That or be limited by the C ABI and give up most of the safety features.
senderista 8y ago
Nit: simhash approximates cosine distance, not Jaccard distance (that would be minhash).
gammateam 8y ago
“0ld days” lol I like it kinda Marriott breach: someone executed an 0ld day.
TACIXAT 8y ago
It is totally awesome that function similarity is seeing the light of day. Google bought Zynamics way back when and their work has evolved a lot since then. This sort of work has big implications in signature generation for malware samples, for clustering families of samples as well as finding common functions to generate detections on. You couldn't necessarily throw this into a detection engine, because we don't have a fast (dedicated) function recovery tool for binaries, but you can absolutely use it to generate byte based detection from a seed of a few samples. Rather than having hash based signatures you could generate signatures that cover many samples (and likely new ones) in bulk. Normally a good signature like that requires manual effort from an analyst, this is a step toward machines doing it. As well, a central authoritative name database that could say "this is Petya" could force some sane naming convention on the industry (every AV wouldn't just be like "it's Zbot lol"). This stuff can even aid manual reverse engineering. You could build a function naming database that uses this. Maybe a new engine for Talos FIRST. [1] Then if you opened up a file without debug symbols this could match it to known functions and really speed up reverse engineering efforts. I look forward to reading it in more detail tomorrow. Thanks to Halvar for putting this out. 1. https://www.talosintelligence.com/first https://www.talosintelligence.com/first
motohagiography 8y ago
The treatment of their ROC curve is precisely the problem I encountered in product for a closely related tech. This is a great way to do vulnerability research, surprisingly good malware detection, but a less good way to provide an assurance service. Great post, and a good step towards the general problem of code reputation.

150 points by matt_d 8y ago

a-dub 8y ago

I always wondered if AV databases were just minhashing/lsh on binaries... guess not!

loeg 8y ago
Hah, no. AV databases are just real dumb tries of whole-file MD5s, or a similar level of sophistication (i.e., not very). Usually combined with an unnecessarily privileged and unsandboxed parser for arbitrary weird file formats.
- a-dub 8y ago
  Looking for vulny binary code in terms of jaccard similarity is interesting.
- landr0id 8y ago
  ssdeep is also used https://www.forensicswiki.org/wiki/Ssdeep https://www.forensicswiki.org/wiki/Ssdeep

Jacoe 8y ago

What am I reading haha.

puzzle 8y ago
The article makes more sense if you consider that Google is notorious for statically linking (almost) all its production binaries, something that the Go toolchain supported early on for related reasons.
- CaliforniaKarl 8y ago
  I’m guessing it’s also related to the recent SQLite zero-day. SQLite is public-domain, and so it’s not unusual for projects to simply include the code directly in their source distributions, which will either build it in or will provide a `./configure` option to use an already-built form (this is used by distro packagers). When the “build it in” option is used, then it’s statically linked.
  - tptacek 8y ago
    I think Thomas Dullien has been working on this stuff for a very long time; his company, Zynamics, which Google acquired ages ago, was the author of BinDiff.
- devereaux 8y ago
  There I many things I disagree about with Google, but statically linking binaries is a good practice if you know what you are doing and have a central repository where you handle your own versions of everything. You can not always rely on linux distribution to not mess up with a lib, especially if it "obscure" with few users.

RobLach 8y ago

Very cool.

tomjakubowski 8y ago

> An efficient implementation of a hash function (based on SimHashing) which calculates a 128-bit hash from disassembled functions - and which preserves similarity (e.g. “distance” of two functions can be calculated by simply calculating the hamming distance between two hashes - which translates to two XOR and two POPCNT instructions on x64). Huh! This obviously desirable property of a good hash function for this application is one of the classic undesirable properties of a good hash function for cryptography. I don't think that I was previously familiar with this sort of hash function, very cool. Are space-filling curves related to these hash functions?

viraptor 8y ago
Another hash with a similar property uses close pronunciation as distance: https://en.m.wikipedia.org/wiki/Soundex https://en.m.wikipedia.org/wiki/Soundex
- simcop2387 8y ago
  Soundex however is only designed for English names. Take a look at Metaphone or Double-Metaphone for a more generic version of the same idea. https://en.wikipedia.org/wiki/Metaphone https://en.wikipedia.org/wiki/Metaphone
tylersmith 8y ago
Not all hashes are intended for cryptographic applications or want the Avalanche effect. Some are simply succinct digests of data and some attempt to retain important information like the hash described here.
livueta 8y ago
Another example of this sort of hash function (where the hamming distance between the hashes of similar inputs will be small) is pHash[1]. I've been playing with it recently for deduping bit-different but perceptually-identical images, and it works pretty well and the low hamming distance property makes it dead simple to use. --- [1] https://www.phash.org/ https://www.phash.org/
8y ago

nineteen999 8y ago

This is probably a good thing, given the recent trend in languages like Golang and Rust to statically link binaries by default.

devereaux 8y ago
I do not understand the hate towards statically linked binaries. It has its place for mission critical tools.
- regecks 8y ago
  I feel like it's pretty easy to understand the hate. For example, the recent x.509 verification DoS patched in <Go1.11.3 required me to recompile, tag and redeploy bunch of services. And then also push an RPM to thousands of customer servers, which costs me CDN money :(. I would have preferred for myself, and my customers to just upgrade openssl. I am still a big fan of static binaries though, they more than make up for their downsides.
- viraptor 8y ago
  Very specific tools, sure. If you have the time, people, and skills to keep your own list of baked-in dependencies and monitor it for issues - great. But for a random person downloading something from the internet, it's a dangerous thing to default to.
  - devereaux 8y ago
    I agree. It is a double edge sword. It requires skill and proper analysis. I should have been more specific. I explained my reason below on https://news.ycombinator.com/item?id=18713442 https://news.ycombinator.com/item?id=18713442
    - ex_amazon_sde 8y ago
      Even FAANG companies rely on distributions and other companies to spot vulnerabilities, rebuild libraries, test and validate them. Even if the company rebuilds everything, there's a huge benefit in knowing that you are using a well tested release instead of a less popular one or an internal fork. Also: security teams hate big security patches.

devereaux 8y ago

The zlib vulnerability was a huge wakeup call. Years ago I used to be in favor of statically linked, to limit dependency creep. Disk space is cheap so large binaries were never a concern. My favorite approach was single repository compiling optimized binaries with the specific versions of the libs wanted (in case of weird regression) and pushing these static binaries to the rest of the network. After the zlib debacle, no more: I only use that approach for very specific mission critical tools, where I do not trust ansible or even linux distributions. The sqlite 0 day may have reignited the same fears in those too young to remember grepping various zlib signatures on binaries -not just yours (you central repository can easily push new version to your network) but the other tools you don't necessary control.

flukus 8y ago
Unfortunately outside of linux distros static linking seems to be becoming more and more then new norm, especially if you include what is effectively "soft" static linking of bundling all dependencies, which suffer from the same problems. Rust is only suitable for static linking, .net core statically links and most .net projects will have all sorts of out of date dependencies, npm bundles huge dependency chains that may not be upgraded. Even in the linux distro world there is movement towards tools like docker where dependencies will often not be patched. Even the idea of stable versions of libraries with security patches seems to be a dieing one.
- whyever 8y ago
  > Rust is only suitable for static linking This is incorrect, Rust supports dynamic linking. https://doc.rust-lang.org/reference/linkage.html https://doc.rust-lang.org/reference/linkage.html
  - flukus 8y ago
    It supports it terribly. Since there's no stable ABI you have to use the same compiler version. That or be limited by the C ABI and give up most of the safety features.

senderista 8y ago

Nit: simhash approximates cosine distance, not Jaccard distance (that would be minhash).

gammateam 8y ago

“0ld days” lol I like it kinda Marriott breach: someone executed an 0ld day.

TACIXAT 8y ago

It is totally awesome that function similarity is seeing the light of day. Google bought Zynamics way back when and their work has evolved a lot since then. This sort of work has big implications in signature generation for malware samples, for clustering families of samples as well as finding common functions to generate detections on. You couldn't necessarily throw this into a detection engine, because we don't have a fast (dedicated) function recovery tool for binaries, but you can absolutely use it to generate byte based detection from a seed of a few samples. Rather than having hash based signatures you could generate signatures that cover many samples (and likely new ones) in bulk. Normally a good signature like that requires manual effort from an analyst, this is a step toward machines doing it. As well, a central authoritative name database that could say "this is Petya" could force some sane naming convention on the industry (every AV wouldn't just be like "it's Zbot lol"). This stuff can even aid manual reverse engineering. You could build a function naming database that uses this. Maybe a new engine for Talos FIRST. [1] Then if you opened up a file without debug symbols this could match it to known functions and really speed up reverse engineering efforts. I look forward to reading it in more detail tomorrow. Thanks to Halvar for putting this out. 1. https://www.talosintelligence.com/first https://www.talosintelligence.com/first

motohagiography 8y ago

The treatment of their ROC curve is precisely the problem I encountered in product for a closely related tech. This is a great way to do vulnerability research, surprisingly good malware detection, but a less good way to provide an assurance service. Great post, and a good step towards the general problem of code reputation.