Tuesday, December 18, 2018

Searching statically-linked vulnerable library functions in executable code

Helping researchers find 0ld days

Posted by Thomas Dullien, Project Zero

Executive summary

Software supply chains are increasingly complicated, and it can be hard to detect statically-linked copies of vulnerable third-party libraries in executables. This blog post discusses cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 technical details of an Apache-licensed open-source library to detect code from ocá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365r open-source libraries in executables, along with some real-world findings of forked open-source libraries in real-world software.

Technical blog post

Permissive open-source licenses have been a great benefit for cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 IT industry: Most common problems can be addressed using high-quality libraries under permissive licenses (such as BSD or Apache) which can be easily re-used and integrated.
This has been great for everybody.
Nevercá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365less, statically linking third-party code requires special care: Vulnerabilities in third-party code are discovered regularly, and this implies updating your binaries. Things get harder when changes in upstream libraries need to be merged into local forks of cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 code. Not all organisations get this right, and even companies with mature secure development processes fumble sometimes.
For cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 reverse engineer and offensive researcher, identifying vulnerable statically linked software libraries is both an opportunity and a challenge:
  • An opportunity since it can provide a way to obtain a vulnerability in a target without having to do cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 hard work of identifying a new one.
  • A challenge since cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 available tooling for performing this task is exceptionally poor: The standard way is usually a combination of “searching for known strings”, “educated guess”, and sometimes cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 use of BinDiff (a tool that was designed for a very different purpose).
The technical problem can be phrased as “efficiently performing a fuzzy search into a relatively large space of possible functions”. Fuzzy search is a requirement because compiler differences, optimization changes, and code changes contribute to add “noise” to cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 code in question.
On cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 side of academic research, several interesting papers (CCS ‘16, CCS ‘17 have proposed sophisticated machine-learning-based methods to combine code embeddings with approximate nearest neighbor searches. They calculate a representation of code in R^n, and cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365n search for nearby points to identify good candidates. While cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365se approaches look powerful and sophisticated, public implementations do not exist, and adoption among practitioners has not happened. On cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 practical side, real-world use has been derived from CFG-focused algorithms such as MACHOC - but with cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 downside of being not tolerant to structural changes and not allowing for any “learning” of distances. Recently at (SSTIC ‘18) a neural-network based approach has been presented, with an announcement of making cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 code available in cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 next months.
This file describes FunctionSimSearch - an Apache-licensed C++ toolkit with Python bindings which provides three things:
  1. 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 cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 hamming distance between two hashes - which translates to two XOR and two POPCNT instructions on x64).
  2. An efficient search index to allow approximate nearest neighbor search for 128-bit hashes.
  3. Some supervised machine learning code that can be used to “learn” a good hash function from human-provided examples - given a set of functions that should be similar according to cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 hash, and a set of functions that should be dissimilar, cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 code learns a hash function that attempts to respect cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365se examples.

The need for good fuzzy matching

Every reverse engineer has encountered that different compilers and compiler settings can generate drastically different pieces of assembly. Compilers can alter cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 CFG significantly, move code around, and even when cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365y do not inline aggressively or unroll loops, decisions about code duplication, instruction movement and scheduling etc. lead to very different disassemblies:

(Visual Studio 2015 unrar code vs. gcc 6.4.0 O1 optimized code)

(Visual Studio 2015 unrar code vs. gcc 6.4.0 O1 optimized code)

It is obvious that a good method to identify a function in cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 presence of changes is needed, and that both instruction-level and graph-level changes need to be dealt with.

Understanding cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 SimHash algorithm and what it provides

SimHashing was introduced in a paper by Moses Charikar, originally in cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 context of web page de-duplication. It is part of a family of algorithms and concepts called “locality-sensitive hashing”; a concept we will return to later.

The algorithm itself helps condense a set of values into a hash, with cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 property that cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 Hamming distance between cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 two hashes approximates cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 set similarity between cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 original sets. This makes estimating cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 set similarity between two sets blazingly fast (just an XOR and a POPCOUNT operation).

How does it work? Given a set of features as input (which are random 128-bit vectors cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365mselves - if cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365y are not, hash cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365m), calculate a final hash output as follows:

  1. Initialize a vector of 128 floating-point values to all zeroes.
  2. For each feature in cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 input set, do:
    1. If bit n of cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 feature is 0, subtract 1 from cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 n-th floating-point value
    2. If bit n of cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 feature is 1, add 1 to cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 n-th floating point value
  3. Convert cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 vector of floats to a 128-bit vector by mapping positive values to 1, negative values to 0.

Why does this produce a similarity-preserving hash? The intuition can be obtained by imagining what a minor change in cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 input set would do to cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 vector of floats: The values of cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365se vectors will be approximately normally distributed with mean 0 and variance ¼ times cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 number of features.


Some of cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 values will be close to zero, eicá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365r negative or positive. By changing cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 sets slightly (adding or removing a few features), cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365re is some probability of individual values crossing over from positive into negative territory or vice versa. This probability goes up as more of cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 set changes; for small changes, cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 odds of many bits flipping is comparatively low.

It is important to note that cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 result will always be a 128-bit vector, irrespective of cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 size of cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 set-of-features from which it was calculated.

What is a good set of input features for our comparison? Ideally we would want to extract features that are representative of what we deem “similar”; e.g. two functions that are compiled from cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 same source code should have similar (overlapping) sets of features. It is somewhat involved to algorithmically design such features, so for cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 moment, cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 features in question are extremely simple: Subgraphs of cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 control-flow graph, n-grams of mnemonics of disassembled instructions, and constants from operands. In a naive implementation, all features have unit weight - e.g. every feature contributes cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 same to cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 final hash. This is clearly not ideal - a function prologue is not very indicative of cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 similarity between two functions - and we will improve this later in this post. Ocá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365r non-implemented ideas for more features will be discussed at cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 end of cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 document.

A simple approximate nearest-neighbor search for hashes

With a way of calculating a similarity-preserving hash for a given input function, how do we search non-trivially sized corpora of such hashes for cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 “most similar” hash?

The answer lies in a second application of locality-sensitive hashing. If one can construct a family of hash functions so that cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 probability of two nearby points getting hashed into cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 same hash bucket is higher than cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 probability of two distant points getting hashed into cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 same bucket, one can construct a relatively efficient nearest-neighbor search: Simply use k different hash functions of cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 family to map inputs to buckets of candidates and process cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 candidates.

Choosing random bits as locality-sensitive hashes

Since our inputs are bit vectors, cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 easiest way to build such a hash function is to simply subsample bits from cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 vector. This has cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 nice property that a single random bit-level permutation of cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 input is enough to construct a hash family: In order to construct k different hashes, apply cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 bit-level permutation k times to your input and take cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 first few bits. Bitwise permutations on 128 bits are cheap-ish in software and close to free in hardware; cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 permutation chosen in cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 codebase should execute in ~65 cycles on a modern CPU.

Choice of data structures

The underlying data structure is an ordered collection of tuples of cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 form:

                       

Performing a binary search using cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 tuple will give us cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 hash bucket for a given permutation index and input value. We perform k such searches, and for each hash bucket we add all elements to a candidate list. The hamming distance between each candidate and cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 input hash is calculated, and cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 results can be returned in cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 order of cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365ir hamming distance.

A maximally memory- and cache-efficient version of this would simply use a sorted flat array / vector of such tuples; for our purposes (and for efficient insertion) cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 existing C++ code uses cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 equivalent of a std::set container, made persistent using a memory-mapped file as storage.

Learning a SimHash from examples

One of cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 problems with cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 described approach can immediately be identified: Every feature in cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 input set is treated with equal importance. In reality, though, features have vastly different importance. Luckily, it is easy to incorporate cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 importance of individual features into cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 calculation of a SimHash: Instead of adding +1 or -1 into cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 vector of floats, one could add or subtract a feature-specific weight.

But how does one infer good weights from cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 training data? Can we automatically “learn” what features will be preserved across compiler changes, with some predictive power?

Using cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 cheap gradient principle

The workhorse of modern machine learning is automatic differentiation. In simple terms, automatic differentiation provides cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 “cheap gradient principle” -- which can be paraphrased as “if you can calculate a function from R^n to R, you can calculate cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 gradient of this function with moderate overhead”. This means that if we can specify a loss function involving our weights, we can try to minimize this loss function. While we won’t have any guarantees of convergence, odds are we can learn weights from examples.

So what we need is a bunch of labelled data (ideally pairs of functions labelled “same” or “not cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 same”), and a good loss function.

Choosing a loss function for cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 SimHash distance

Building a loss function for our distance requires a slight bit of care. Since our final distance is a Hamming distance between two bit vectors, cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 gradient of this distance is likely to be zero - stepwise functions have many “flat sections” for which we cannot get a useful gradient.

The simplest idea would be to remove cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 last step of cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 hash calculation - instead of comparing cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 hashes that we derive from cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 vector-of-floats, one could measure cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 Euclidian distance on cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 final vectors-of-floats. Unfortunately, this creates “perverse incentives” for cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 optimizer: The simplest way to make two “similar” functions close to each ocá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365r would be to shrink weights that occur in both to zero.

So ideally we want something that “penalizes” when pairs of similar functions with large distance and pairs of dissimilar functions with low distance.

We need a function that is positive when two real values do not have cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 same sign, and zero (or negative) if cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 two real values that have cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 same sign. Ideally, it should also provide a slope / incentive to move inputs in cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 direction of “same sign”.

We start with a simple smoocá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365d step function g(x,y) := - xyx2y2+1.0+1.0:



This function has high loss when cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 sign of x and y is different, and zero loss when it is cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 same. Unfortunately, it is also flat on most of cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 surface, so we need to somehow skew cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 flat regions to point into cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 right direction. So we multiply with d(x,y) :=(x-y)2+0.01


This function satisfies our requirements: It provides a way to move parameters in cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 desired direction, punishes unequal signs, and has zero loss if x and y have equal sign.

In summary: For a given pair of real vectors (each obtained by calculating cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 hash function without cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 last step of converting to a binary hash) we can simply sum cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 loss for each vector entry. We now have a loss function that we can use to adjust our parameters from examples.

Generating training data

Generating training data should - at least in cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365ory - be simple. It should be sufficient to compile some open-source code with a number of different compilers and compiler settings, and cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365n parse cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 symbol information to create groups of “function variants” - e.g. multiple different compiler outputs for cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 same C/C++ function. Similarly, known-dissimilar-pairs can be generated by simply taking two random functions with different symbols.

Unfortunately, cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365ory is not practice, and a number of grimy implementation issues come up, mostly around symbol parsing and CFG reconstruction.

Real-world problems: Symbols

One problem arises from cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 non-availability of good cross-platform tooling for parsing different versions of cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 PDB file format - which naturally arise when many different versions of Visual Studio are used - and cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 difficulty of reliably building cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 same open-source codebase for many different compilers. While GCC and CLANG are often drop-in-replaceable, projects that build without intervention on both Visual Studio, GCC, and CLANG are much more rare.

The (unfortunate) solution to cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 PDB parsing issue is “giving up” - cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 codebase expects cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 PDB information to have been dumped to a text file. More on this below.

The (equally unfortunate) solution to cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 issue of building cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 same codebase reliably with Visual Studio and GCC is also “giving up” - it is up to cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 user of FunctionSimSearch to get things built.

Ocá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365r problems arise by different mangling conventions for C++ code, and different conventions in different compilers affecting how exactly a function is named. This is solved by a hackish small tool that removes type information from symbols and tries to “unify” between GCC/CLANG and Visual Studio notation.

Real-world problems: Reliably generating CFGs, and polluted data sets

Obtaining CFGs for functions should be simple. In practice, none of cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 tested disassemblers correctly disassembles switch statements across different compilers and platforms: Functions get truncated, basic blocks mis-assigned etc. The results particularly dire for GCC binaries compiled using -fPIC of -fPIE, which, due to ASLR, is cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 default on modern Linux systems.

The net result is polluted training data and polluted search indices, leading to false positives, false negatives, and general frustration for cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 practitioner.
While cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 ideal fix would be more reliable disassembly, in practice cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 fix is careful investigation of extreme size discrepancies between functions that should be cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 same, and ensuring that training examples are compiled without PIC and PIE (-fno-pie -fno-PIE -fno-pic -fno-PIC is a useful set of build flags).

Data generation in practice

In practice, training data can be generated by doing:

cd ./testdata
     ./generate_training_data.py --work_directory=/mnt/training_data

The script parses all ELF and PE files it can find in cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 ./testdata/ELF and ./testdata/PE directories. For ELF files with DWARF debug information, it uses objdump to extract cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 names of cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 relevant functions. For PE files, I was unfortunately unable to find a good and reliable way of parsing a wide variety of PDB files from Linux. As a result, cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 script expects a text file with cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 format “.debugdump” to be in cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 same directory as each PE executable. This text file is expected to contain cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 output of cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 DIA2Dump sample file that ships with Visual Studio.

The format of cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 generated data is as follows:

./extracted_symbols_.txt
./functions_.txt
     ./[training|validation]_data_[seen|unseen]/attract.txt
     ./[training|validation]_data_[seen|unseen]/repulse.txt
     ./[training|validation]_data_[seen|unseen]/functions.txt

Let’s walk through cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365se files to understand what we are operating on:

  1. The ./extracted_symbols_.txt files:
    Every executable is assigned an executable ID - simply cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 first 64 bit of it’s SHA256. Each such file describes cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 functions in cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 executable for which symbols are available, in cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 format:
    [exe ID] [exe path] [function address] [base64 encoded symbol] false
  2. The ./functions_.txt files:
    These files contain cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 hashes of cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 extracted features for each function in cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 executable in question. The format of cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365se files is:
    [exe ID]:[function address] [sequence of 128-bit hashes per feature]
  3. The ./[training|validation]_data_[seen|unseen]/attract.txt and ./repulse.txt files:
    These files contain pairs of functions that should repulse / attract, cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 format is simply
    [exe ID]:[function address] [exe ID]:[function address]
  4. The ./[training|validation]_data_[seen|unseen]/functions.txt files:
    A file in cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 same format as cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 ./functions_.txt files with just cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 functions referenced in cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 corresponding attract.txt and repulse.txt.

Two ways of splitting cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 training / validation data

What are cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 mysterious training_data_seen and training_data_unseen directories? Why does cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 code generate multiple different training/validation splits? The reason for this is that cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365re are two separate questions we are interested in:

  1. Does cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 learning process improve our ability to detect variants of a function we have trained on?
  2. Does cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 learning process improve our ability to detect variants of a function, even if no version of that function was available at training time?

While (2) would be desirable, it is unlikely that we can achieve this goal. For our purposes (detection of statically linked vulnerable libraries), we can probably live with (1). But in order to answer cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365se questions meaningfully, we need to split our training and validation data differently.

If we wish to check for (2), we need to split our training and validation data along “function group” lines: A “function group” being a set of variant implementations of cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 same function. We cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365n need to split off a few function groups, train on cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 ocá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365rs, and use cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 groups we split off to validate.

On cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 ocá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365r hand, if we wish to check for (1), we need to split away random variants of functions, train on cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 remainder, and cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365n see if we got better at detecting cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 split-off functions.

The differences in how cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 training data is split is best illustrated as follows:



Implementation issues of cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 training
The industry-standard approaches for performing machine learning are libraries such as TensorFlow or specialized languages such as Julia with AutoDiff packages. These come with many advantages -- most importantly, automated parallelization and offloading of computation to your GPU.
Unfortunately, I am very stubborn -- I wanted to work in C++, and I wanted to keep cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 dependencies extremely limited; I also wanted to specify my loss function directly in C++. As a result, I chose to use a C++ library called SPII which allows a developer to take an arbitrary C++ function and minimize it. While this offers a very clean and nice programming model, cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 downside is “CPU-only” training. This works, but is uncomfortably slow, and should be replaced with a GPU-based version.

Running cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 actual training process

Once cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 training data is available, running cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 training process is pretty straightforward:

thomasdullien@machine-learning-training:~/sources/functionsimsearch/bin$ ./trainsimhashweights -data=/mnt/training_data/training_data_seen/ --weights=weights_seen.txt
[!] Parsing training data.
[!] Mapping functions.txt
[!] About to count cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 entire feature set.
[!] Parsed 1000 lines, saw 62601 features ...
[!] Parsed 2000 lines, saw 104280 features ...
(...)
[!] Parsed 12000 lines, saw 270579 features ...
[!] Processed 12268 lines, total features are 271653
[!] Iterating over input data for cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 2nd time.
[!] Loaded 12268 functions (271653 unique features)
[!] Attraction-Set: 218460 pairs
[!] Repulsion-Set: 218460 pairs
[!] Training data parsed, beginning cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 training process.
Itr       f deltaf   max|g_i| alpha     H0 rho
  0 +7.121e+04       nan 4.981e+02 2.991e-06 1.000e+00 0.000e+00
  1 +7.119e+04 2.142e+01 5.058e+02 1.000e+00 1.791e-06 3.114e-01
  2 +7.101e+04 1.792e+02 3.188e+02 1.000e+00 2.608e-05 5.735e-03
  3 +7.080e+04 2.087e+02 2.518e+02 1.000e+00 4.152e-05 4.237e-03
  4 +7.057e+04 2.271e+02 2.757e+02 1.000e+00 5.517e-05 4.469e-03
   ...

A few days later, cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 training process will have performed 500 iterations of L-BFGS while writing snapshots of cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 training results every 20 steps into our current directory (20.snapshot … 480.snapshot). We can evaluate cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 results of our training:

$ for i in *.snapshot; do foo=$(./evalsimhashweights --data /mnt/june2/validation_data_seen/ --weights $i | grep \(trained\)); echo $i $foo; done

This provides us with cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 “difference in average distance between similar and dissimilar pairs” in cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 validation data: cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 code calculates cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 average distance between similar pairs and between dissimilar pairs in cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 validation data, and shows us cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 difference between cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 two. If our training works, cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 difference should go up.


We can see that somewhere around 420 training steps we begin to over-train - our difference-of-means on cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 validation set starts inching down again, so it is a good idea to stop cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 optimization process. We can also see that cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 difference-in-average-distance between cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 “similar” and “dissimilar” pairs has gone up from a bit more than 10 bits to almost 25 bits - this seems to imply that our training process is improving our ability to recognize variants of functions that we are training on.

Understanding cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 results of training

There are multiple ways of understanding cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 results of cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 training procedure:

  1. Given that we can easily calculate distance matrices for a set of functions, and given that cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365re are popular ways of visualizing high-dimensional distances (t-SNE and MDS), we can see cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 effects of our training visually.
  2. Several performance metrics exist for information-retrieval tasks (Area-under-ROC-curve).
  3. Nothing builds confidence like understanding what is going on, and since we obtain per-feature weights, we can manually inspect cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 feature weights and features to see what exactly cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 learning algorithm learnt.

The next sections will go through steps 1 and 2. For step 3, please refer to cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 documentation of cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 tool.

Using t-SNE as visualisation

A common method to visualize high-dimensional data from pairwise distances is t-SNE -- a method that ingests a matrix of distances and attempts to create a low-dimensional (2d or 3d) embedding of cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365se points that attempts to respect distances. The code comes with a small Python script that can be used to visualize

We will create two search indices: One populated with cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 “learnt feature weights”, and one populated with cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 “unit feature weight”:

# Create and populate an index with cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 ELF unrar samples with cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365
# learnt features.
./createfunctionindex --index=learnt_features.index; ./growfunctionindex --index=learnt_features.index --size_to_grow=256; for i in $(ls ../testdata/ELF/unrar.5.5.3.builds/*); do echo $i; ./addfunctionstoindex --weights=420.snapshot --index=learnt_features.index --format=ELF --input=$i; done
# Add cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 PE files
for i in $(find ../testdata/PE/ -iname *.exe); do echo $i; ./addfunctionstoindex --weights=420.snapshot --index=learnt_features.index --format=PE --input=$i; done

# Create and populate an index with unit weight features.
./createfunctionindex --index=unit_features.index; ./growfunctionindex --index=unit_features.index --size_to_grow=256; for i in $(ls ../testdata/ELF/unrar.5.5.3.builds/*); do echo $i; ./addfunctionstoindex --index=unit_features.index --format=ELF --input=$i; done
# Add cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 PE files
for i in $(find ../testdata/PE/ -iname *.exe); do echo $i; ./addfunctionstoindex --index=unit_features.index --format=PE --input=$i; done

# Dump cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 contents of cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 search index into a text file.
./dumpfunctionindex --index=learnt_features.index > learnt_index.txt
./dumpfunctionindex --index=unit_features.index > unit_index.txt

# Process cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 training data to create a single text file with symbols for
# all functions in cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 index.
cat /mnt/training_data/extracted_*.txt > ./symbols.txt

# Generate cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 visualisation
cd ../testdata
./plot_function_groups.py  ../bin/symbols.txt ../bin/learn_index.txt /tmp/learnt_features.html
./plot_function_groups.py  ../bin/symbols.txt ../bin/learnt_index.txt /tmp/learnt_features.html

We now have two HTML files that use d3.js to render cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 results:

Unit weights:


Learned weights:


Mouse-over on a point will display cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 function symbol and file-of-origin. It is visible to cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 naked eye that our training had cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 effect of moving groups of functions “more closely togecá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365r”.

We can see here that cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 training does have some effect, but does not produce cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 same good effect for all functions: Some functions seem to benefit much more from cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 training than ocá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365rs, and it remains to be investigated why this is cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 case.

Examining TPR, FPR, IRR, and cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 ROC-curve


When evaluating information retrieval systems, various metrics are important: The true positive rate (how many of cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 results we were supposed to find did we find?), cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 false positive rate (how many of cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 results we were not supposed to find did we find?), cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 irrelevant result rate (what percentage of cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 results we returned were irrelevant? This is cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 complement to cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 precision), and cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 ROC curve (a plot of cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 TPR against cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 FPR).
This is helpful in both making informed choices about cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 right distance threshold, but also in order to quantify how much we are losing by performing approximate vs. precise search. It also helps us choose how many "hash buckets" we want to use for approximate searching.
There is a Python script in cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 git repository that can be used to generate cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 data for cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 ROC curve. The script requires a file with cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 symbols for all elements of cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 search index, a textual representation of cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 search index (obtained with dumpsearchindex, and access to cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 actual search index file.
# Create a search index to work with.
./createfunctionindex --index=/media/thomasdullien/roc/search.index
# Make it big enough to contain cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 data we are adding.
./growfunctionindex --index=/media/thomasdullien/roc/search.index --size_to_grow=1024
# Add all cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 functions from our training directories to it:
for filename in $(find ../testdata/ELF/ -iname *.ELF); do echo $filename; ./addfunctionstoindex --format=ELF --input=$filename --index=/media/thomasdullien/roc/search.index; done
for filename in $(find ../testdata/PE/ -iname *.exe); do echo $filename; ./addfunctionstoindex --format=PE --input=$filename --index=/media/thomasdullien/roc/search.index; done
# Now dump cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 search index into textual form for cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 Python script:
./dumpfunctionindex --index /media/thomasdullien/roc/search.index  > /media/thomasdullien/roc/search.index.txt
# The file "symbols.txt" is just a concatenation of cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 symbols extracted during
# cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 run of cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 ./generate_training_data.py script.
cat /media/thomasdullien/training_data/extracted_symbols_*.txt > /media/thomasdullien/roc/symbols.txt

In order to obtain cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 data for cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 curve, we can use cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 following Python script:
testdata/evaluate_ROC_curve.py --symbols=/media/thomasdullien/roc/symbols.txt --dbdump=/media/thomasdullien/roc/search.index.txt --index=/media/thomasdullien/roc/search.index

The output of cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 script is a 7-column output:
  1. The maximum distance between two SimHash values to consider.
  2. The true positive rate for exact (non-approximate-search-index) search.
  3. The false positive rate for exact (non-approximate-search-index) search.
  4. The true positive rate for search using cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 approximate search index.
  5. The false positive rate for using cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 approximate search index.
  6. The percentage of irrelevant results returned using exact search.
  7. The percentage of irrelevant results returned using approximate search.
We can generate cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 curves for both cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 trained and untrained data, and cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365n plot cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 results using gnuplot:
gnuplot -c ./testdata/plot_results_of_evaluate_ROC_curve.gnuplot ./untrained_roc.txt
gnuplot -c ./testdata/tpr_fpr_curve.gnuplot ./untrained_roc.txt ./trained_roc.txt

So let us examine this plots for cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 untrained results first:


The first diagram shows that if we want a TPR of more than 50%, we will have to incur about 20% of cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 returned results being irrelevant to our search; cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 cut-off distance we should take for this is somewhere around 25 bits.
We also see that we will pay a heavy price for increasing cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 cut-off: At 35 bits, where our TPR hits 55%, half of our results are irrelevant. This is a weakness of cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 set-up at cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 moment, and we will see if it can be improved by learning weights.
The second diagram shows that we only pay in TPR for cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 approximate search for very high cut-offs - cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 TPR and FPR flatten off, which is a symptom of us missing more and more of cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 search space as we expand cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 number of bits we consider relevant.
The lower-left diagram shows how quickly our precision deteriorates as we try to improve cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 recall.
How are cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365se curves affected by cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 training process?

So in cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 top-left curve, we can see that cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 rate of irrelevant results at 10 bits distance has dropped significantly: Down to approximately 5% from about 15%. Unfortunately, cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 true-positive-rate has also dropped - instead of about 45% of cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 results we want to get, we only achieve about 33%. So cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 training works in cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 sense that it improves cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 ratio of good results to irrelevant results significantly, but at cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 cost of lowering cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 overall rate of results that we find.
If we are willing to tolerate approximately 15% irrelevant results, we will get about 45% of cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 results we desire in cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 non-trained version. Sadly, in cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 trained version, for cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 same level of irrelevant results, we only get about 40% of cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 results we desire.
In summary: In cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 current form, cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 training is useful for lowering cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 irrelevant result rate below what is achievable without training - but for any acceptable rate of irrelevant results that can be achieved without training, cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 untrained version appears to achieve better results.

Does this generalize to out-of-sample functions?

In cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 section about splitting our training/validation data, we posed two questions - and cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 more interesting question is (2). Is cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365re anything we are learning about cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 compilers ?
Plotting cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 difference-in-mean-distance that we plotted for question (1) also for question (2) yields cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 following image:

The red curve implies that cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365re is a faint but non-zero signal - after about 80 training steps we have increased cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 mean-difference-in-means from 11.42 bits to 12.81 bits; overtraining appears to begin shortly cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365reafter.
It is unclear how much signal could be extracted using more powerful models; cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 fact that our super-simple linear model extracts something is encouraging.

Practical searching

Using FunctionSimSearch from any Python-enabled RE tool

The command-line tools mostly rely on DynInst for disassembly - but reverse engineers work with a bewildering plethora of different tools: IDA, Radare, Binary Ninja, Miasm etc. etc.

Given cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 development effort to build integration for all cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365se tools, I decided that cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 simplest thing would be to provide Python bindings -- so any tool that can interact with a Python interpreter can use FunctionSimSearch via cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 same API. In order to get cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 tool installed into your Python interpreter, run:

python ./setup.py --install user

The easiest way to use cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 API from python is via JSON-based descriptions of flowgraphs:

 jsonstring = (... load cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 JSON ... )
 fg = functionsimsearch.FlowgraphWithInstructions()
 fg.from_json(jsonstring)
 hasher = functionsimsearch.SimHasher("../testdata/weights.txt")
 function_hash = hasher.calculate_hash(fg)

This yields a Python tuple with cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 hash of cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 function. The JSON graph format used as input looks as follows:

{
 "edges": [ { "destination": 1518838580, "source": 1518838565 }, (...) ],
 "name": "CFG",
 "nodes": [
   {
     "address": 1518838565,
     "instructions": [
       { "mnemonic": "xor", "operands": [ "EAX", "EAX" ] },
       { "mnemonic": "cmp", "operands": [ "[ECX + 4]", "EAX" ] },
       { "mnemonic": "jnle", "operands": [ "5a87a334" ] } ]
   }, (...)  ]
}

More details on how to use cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 Python API can be found in this example Python-based IDA Plugin. The plugin registers hotkeys to “save cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 current function in IDA into cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 hash database” and hotkeys to “search for similar functions to cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 current IDA function in cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 hash database”. It also provides hotkeys to save cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 entire IDB into cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 Database, and to try to match every single function in a given disassembly against cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 search index.

For people that prefer using Binary Ninja, a plugin with similar functionality is available (thanks carstein@ :-).

Searching for unrar code in mpengine.dll

As a first use case, we will use IDA to populate a search index with symbols from unrar, and cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365n search through mpengine.dll (also from Binary Ninja) for any functions that we may recognize.
We can populate a search index called '''/var/tmp/ida2/simhash.index''' from a set of existing disassemblies using cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 following command line:
# Create cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 file for cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 search index.
/home/thomasdullien/Desktop/sources/functionsimsearch/bin/createfunctionindex --index=/var/tmp/ida2/simhash.index
# Populate using all 32-bit UnRAR.idb in a given directory.
for i in $(find /media/thomasdullien/unrar.4.2.4.builds.idbs/unrar/ -iname UnRAR.idb); do ./ida -S"/usr/local/google/home/thomasdullien/sources/functionsimsearch/pybindings/ida_example.py export /var/tmp/ida2/" $i; done
# Populate using all 64-bit UnRAR.i64 in a given directory.
for i in $(find /media/thomasdullien/unrar.4.2.4.builds.idbs/unrar/ -iname UnRAR.i64); do ./ida64 -S"/usr/local/google/home/thomasdullien/sources/functionsimsearch/pybindings/ida_example.py export /var/tmp/ida2/" $i; done
Once this is done, we can open mpengine.dll in IDA, go to File->Script File and load ida_example.py, cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365n hit "Shift-M".
The IDA message window will get flooded with results like cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 text below:
(...)
6f4466b67afdbf73:5a6c8da1 f3f964313d8c559e-e6196c17e6c230b4 Result is 125.000000 - 72244a754ba4796d:42da24 x:\shared_win\library_sources\unrar\unrarsrc-4.2.4\unrar\build.VS2015\unrar32\Release\UnRAR.exe 'memcpy_s' (1 in inf searches)
6f4466b67afdbf73:5a6c8da1 f3f964313d8c559e-e6196c17e6c230b4 Result is 125.000000 - ce2a2aa885d1a212:428234 x:\shared_win\library_sources\unrar\unrarsrc-4.2.4\unrar\build.VS2015\unrar32\MinSize\UnRAR.exe 'memcpy_s' (1 in inf searches)
6f4466b67afdbf73:5a6c8da1 f3f964313d8c559e-e6196c17e6c230b4 Result is 125.000000 - 69c2ca5e6cb8a281:42da88 x:\shared_win\library_sources\unrar\unrarsrc-4.2.4\unrar\build.VS2015\unrar32\FullOpt\UnRAR.exe 'memcpy_s' (1 in inf searches)
--------------------------------------
6f4466b67afdbf73:5a6f7dee e6af83501a8eedd8-6cdba61793e9a840 Result is 108.000000 - ce2a2aa885d1a212:419301 x:\shared_win\library_sources\unrar\unrarsrc-4.2.4\unrar\build.VS2015\unrar32\MinSize\UnRAR.exe '?RestartModelRare@ModelPPM@@AAEXXZ' (1 in 12105083908.189119 searches)
6f4466b67afdbf73:5a6f7dee e6af83501a8eedd8-6cdba61793e9a840 Result is 107.000000 - 86bc6fc88e1453e8:41994b x:\shared_win\library_sources\unrar\unrarsrc-4.2.4\unrar\build.VS2013\unrar32\MinSize\UnRAR.exe '?RestartModelRare@ModelPPM@@AAEXXZ' (1 in 3026270977.047280 searches)
6f4466b67afdbf73:5a6f7dee e6af83501a8eedd8-6cdba61793e9a840 Result is 107.000000 - eb42e1fc45b05c7e:417030 x:\shared_win\library_sources\unrar\unrarsrc-4.2.4\unrar\build.VS2010\unrar32\MinSize\UnRAR.exe '?RestartModelRare@ModelPPM@@AAEXXZ' (1 in 3026270977.047280 searches)
--------------------------------------
6f4466b67afdbf73:5a6fa46b f0b5a76c7eee2882-62d6c234a16c5b68 Result is 106.000000 - d4f4aa5dd49097be:414580 x:\shared_win\library_sources\unrar\unrarsrc-4.2.4\unrar\build.VS2010\unrar32\Release\UnRAR.exe '?Execute@RarVM@@QAEXPAUVM_PreparedProgram@@@Z' (1 in 784038800.726675 searches)
6f4466b67afdbf73:5a6fa46b f0b5a76c7eee2882-62d6c234a16c5b68 Result is 106.000000 - 50bbba3fc643b153:4145c0 x:\shared_win\library_sources\unrar\unrarsrc-4.2.4\unrar\build.VS2010\unrar32\FullOpt\UnRAR.exe '?Execute@RarVM@@QAEXPAUVM_PreparedProgram@@@Z' (1 in 784038800.726675 searches)
6f4466b67afdbf73:5a6fa46b f0b5a76c7eee2882-62d6c234a16c5b68 Result is 105.000000 - eb42e1fc45b05c7e:410717 x:\shared_win\library_sources\unrar\unrarsrc-4.2.4\unrar\build.VS2010\unrar32\MinSize\UnRAR.exe '?Execute@RarVM@@QAEXPAUVM_PreparedProgram@@@Z' (1 in 209474446.235050 searches)
--------------------------------------
6f4466b67afdbf73:5a6fa59a c0ddbe744a832340-d7d062fe42fd5a60 Result is 106.000000 - eb42e1fc45b05c7e:40fd39 x:\shared_win\library_sources\unrar\unrarsrc-4.2.4\unrar\build.VS2010\unrar32\MinSize\UnRAR.exe '?ExecuteCode@RarVM@@AAE_NPAUVM_PreparedCommand@@I@Z' (1 in 784038800.726675 searches)
--------------------------------------
6f4466b67afdbf73:5a7ac980 c03968c6fad84480-2b8a2911b1ba1e40 Result is 105.000000 - 17052ba379b56077:140069170 x:\shared_win\library_sources\unrar\unrarsrc-4.2.4\unrar\build.VS2015\unrar64\Debug\UnRAR.exe 'strrchr' (1 in 209474446.235050 searches)
6f4466b67afdbf73:5a7ac980 c03968c6fad84480-2b8a2911b1ba1e40 Result is 105.000000 - 4e07df225c1cf59c:140064590 x:\shared_win\library_sources\unrar\unrarsrc-4.2.4\unrar\build.VS2013\unrar64\Debug\UnRAR.exe 'strrchr' (1 in 209474446.235050 searches)
6f4466b67afdbf73:5a7ac980 c03968c6fad84480-2b8a2911b1ba1e40 Result is 105.000000 - a754eed77d0059ed:1400638f0 x:\shared_win\library_sources\unrar\unrarsrc-4.2.4\unrar\build.VS2012\unrar64\Debug\UnRAR.exe 'strrchr' (1 in 209474446.235050 searches)
--------------------------------------
Let us examine some of cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365se results a bit more in-depth. The first result claims to have found a version of memcpy_s, with a 125 out of 128 bits matching. This implies a very close match. The corresponding disassemblies are:


Aside from a few minor changes on cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 instruction-level, cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 two functions are clearly cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 same - even cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 CFG structure stayed identical.
The next result claims to have found a variant ppmii::ModelPPM::RestartModelRare with 108 of cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 128 bits matching.


The disassembly (and all structure offsets in cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 code) seems to have changed quite a bit, but cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 overall CFG structure is mostly intact: The first large basic block was broken up by cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 compiler, so cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 graphs are not identical, but cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365y are definitely still highly similar.

The next example is a much larger function - cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 result claims to have identified RarVM::ExecuteCode with 106 of 128 bits of cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 hash matching. What does cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 graph (and cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 disassembly) look like?


In this example, cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 graph has changed substantially, but a few subgraphs seem to have remained stable. Furcá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365rmore, cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 code contains magic constants (such as 0x17D7840, or cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 0x36) that will have factored into cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 overall hash. This is a nontrivial find, so ... yay!
This blog post would not be complete without showing an example of a false positive: Our search also brings up a match for ``RarTime::operator==```. The match is very high-confidence -- 125 out of 128 bits match, but it turns out that - while cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 code is very similar - cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 functions do not actually have any relationship on cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 source-code level.

Both functions check a number of data members of a structure, and return eicá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365r true or false if all cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 values are as expected. Such a construct can arise easily - especially in operator==-style constructs.

Searching for libtiff code in Adobe Reader

It is well-documented that Adobe Reader has been bitten by using outdated versions of libtiff in cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 past. This means that running a search through AcroForm.dll should provide us with a number of good hits from libtiff, and failure to achieve this should raise some eyebrows.

We populate a database with a variety of libtiff builds, run cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 plugin as we did previously, and examine cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 results. In comparison to cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 mpengine case, we get dozens of high-likelihood-results -- cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 codebase inside AcroForm.dll has not diverged from upstream quite as heavily as cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 Unrar fork inside mpengine.

Searching for libtiff code through all my Windows DLLs

Searching for code that we already know is present is not terribly interesting. How about searching for traces of libtiff across an entire harddisk with Windows 10 installed?
In order to do this from cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 command line (e.g. without any real third-party disassembler), we need a few things:
  1. A directory in which we have compiled libtiff with a variety of different versions of Visual Studio and a variety of different compiler settings.
  2. Debug information from cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 PDB files in a format we can easily parse. The current tooling expects a .debugdump file in cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 same directory as cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 PDB file, obtained by using Microsofts DIA2Dump tool and redirecting cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 output to a text file.
Let's create a new search index and populate it:
# Create cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 file for cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 search index.
/home/thomasdullien/Desktop/sources/functionsimsearch/bin/createfunctionindex --index=/var/tmp/work/simhash.index
# Populate it.
for i in $(find /media/thomasdullien/storage/libtiff/PE/ -name tiff.dll); do ./addfunctionstoindex --input=$i --format=PE --index=/var/tmp/work/simhash.index; done
We also want some metadata so we know cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 symbols of cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 files in cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 search index.
We can generate a metadata file to be used with a search index by running cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 same script that generates training data:
~/Desktop/sources/functionsimsearch/testdata/generate_training_data.py --work_directory=/var/tmp/work/ --executable_directory=/media/thomasdullien/storage/libtiff/ --generate_fingerprints=True --generate_json_data=False
cat /var/tmp/work/extracted_symbols* > /var/tmp/work/simhash.index.meta
Allright, finally we can scan through cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 DLLs in a directory:
for i in $(find /media/DLLs -iname ./*.dll); do echo $i; ./matchfunctionsindex --index=/var/tmp/work/simhash.index --input $i; done
We will get commandline output similar to cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 following:
/home/thomasdullien/Desktop/sources/adobe/binaries/AGM.dll
[!] Executable id is 8ce0e5a0e1324b15
[!] Loaded search index, starting disassembly.
[!] Done disassembling, beginning search.
[!] (1231/7803 - 8 branching nodes) 0.843750: 8ce0e5a0e1324b15.608033d matches 36978e7b9d396c8d.10021978 /home/thomasdullien/Desktop/tiff-3.9.5-builds/PE/vs2013.32bits.O1/libtiff.dll std::basic_string, std::allocator >::_Copy(unsigned int, unsigned int)
[!] (1231/7803 - 8 branching nodes) 0.820312: 8ce0e5a0e1324b15.608033d matches 53de1ce877c8fedd.10020e8b /home/thomasdullien/Desktop/tiff-3.9.5-builds/PE/vs2012.32bits.O1/libtiff.dll std::basic_string, std::allocator >::_Copy(unsigned int, unsigned int)
[!] (1236/7803 - 7 branching nodes) 0.828125: 8ce0e5a0e13i24b15.608056e matches 36978e7b9d396c8d.100220d4 /home/thomasdullien/Desktop/tiff-3.9.5-builds/PE/vs2013.32bits.O1/libtiff.dll std::basic_string, std::allocator >::assign( std::basic_string, std::allocator > const&, unsigned int, unsigned int)
(...)
/home/thomasdullien/Desktop/sources/adobe/binaries/BIBUtils.dll
[!] Executable id is d7cc3ee987ba897f
[!] Loaded search index, starting disassembly.
[!] Done disassembling, beginning search.
(...)
/media/dlls/Windows/SysWOW64/WindowsCodecs.dll
[!] Executable id is cf1cc98bead49abf
[!] Loaded search index, starting disassembly.
[!] Done disassembling, beginning search.
[!] (3191/3788 - 23 branching nodes) 0.851562: cf1cc98bead49abf.53135c10 matches 39dd1e8a79a9f2bc.1001d43d /home/thomasdullien/Desktop/tiff-3.9.5-builds/PE/vs2015.32bits.O1/libtiff.dll PackBitsEncode( tiff*, unsigned char*, int, unsigned short)
[!] (3192/3788 - 23 branching nodes) 0.804688: cf1cc98bead49abf.53135c12 matches 4614edc967480a0d.1002329a /home/thomasdullien/Desktop/tiff-3.9.5-builds/PE/vs2013.32bits.O2/libtiff.dll
[!] (3192/3788 - 23 branching nodes) 0.804688: cf1cc98bead49abf.53135c12 matches af5e68a627daeb0.1002355a /home/thomasdullien/Desktop/tiff-3.9.5-builds/PE/vs2013.32bits.Ox/libtiff.dll
[!] (3192/3788 - 23 branching nodes) 0.804688: cf1cc98bead49abf.53135c12 matches a5f4285c1a0af9d9.10017048 /home/thomasdullien/Desktop/tiff-3.9.5-builds/PE/vs2017.32bits.O1/libtiff.dll PackBitsEncode( tiff*, unsigned char*, int, unsigned short)
[!] (3277/3788 - 13 branching nodes) 0.828125: cf1cc98bead49abf.5313b08e matches a5f4285c1a0af9d9.10014477 /home/thomasdullien/Desktop/tiff-3.9.5-builds/PE/vs2017.32bits.O1/libtiff.dll
This is pretty interesting. Let's load WindowsCodecs.dll and cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 libtiff.dll with cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 best match into IDA, and examine cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 results:

At this zoom level, cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 two functions do not necessarily look terribly similar, but zooming in, it becomes apparent that cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365y do share a lot of similarities, both structural and in terms of instruction sequences:


What really gives us confidence in cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 non-spuriousness of cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 result is (...drumroll...) cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 name that IDA obtained for this function from cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 Microsoft-provided PDB debug symbols: PackBitsEncode.
Closer examination of WindowsCodecs.dll reveals that it contains a fork of libtiff version 3.9.5, which Microsoft changed significantly. We have not investigated how Microsoft deals with backporting security and reliability fixes from upstream. Since libtiff links against libjpeg, it should perhaps not surprise us that cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 same DLL also contains a modified libjpeg fork.

Summary, Future Directions, Next Steps

What has been learnt on this little adventure? Aside from many details about building similarity-preserving hashes and search indices for cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365m, I learnt a few interesting lessons:

Lessons Learnt

The search index vs linear sweep - modern CPUs are fast at XOR

It turns out that modern CPUs are extremely fast at simply performing a linear sweep through large areas of memory. A small C program with a tight inner loop which loads a hash, XORs it against a value, counts cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 resulting bits, and remembers cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 index of cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 "closest" value will search through hundreds of millions of hashes on a single core.
The algorithmic break-even for cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 locality-sensitive-hashing index is not reached until way north of a few hundred million hashes; it is unclear how many people will even have that many hashes to compare against.
It is possible that cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 clever search index was over-engineered, and a simple linear sweep would do just as well (and be more storage-efficient).

Competing with simple string search

For cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 stated problem of finding statically linked libraries, it turns out that in cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 vast majority of cases (personally guess 90%+), searching for particularly expressive strings which are part of cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 library will be cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 most effective method: Compilers generally do not change strings, and if cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 string is sufficiently unusual, one will obtain a classifier with almost zero irrelevant results and a reasonably high true positive rate.
The heavy machinery that we explored here is hence most useful in situations where individual snippets of code have been cut & pasted between open-source libraries. Of cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 real-world cases we examined, only mpengine.dll fits cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 bill; it is an open question how prevalent cutting-and-pasting-without-strings is.
An interesting research question with regards to existing published results is also: What added value does cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 method provide over simple string search?

The problem is still hard

Even with all cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 engineering performed here, we can only reliably find about 40% of cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 cases we care about - and likely even fewer if a compiler is involved to which we do not have access. There is a lot of room to improve cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 method - I optimistically thinks it should be possible to reach a true positive rate of 90%+ with a small number of irrelevant results.
It sounds like an interesting question for cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 ML and RE community: Can embeddings from disassemblies into Hamming-space be learnt that achieve much better results than cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 simple linear model here? At what computational cost?

Future directions / next steps

There are a number of directions into which this research could (and should) be expanded:
  1. Re-writing cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 machine learning code in TensorFlow or Julia (or any ocá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365r setup that allows efficient execution on cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 GPU). The current code takes days to train with 56-core server machines mainly because my desire to write cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 loss function directly in C++. While this is elegant in cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 framework of a single-language codebase, using a language that allows easy parallelization of cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 training process onto a GPU would make future experimentation much easier.
  2. Swapping L-BFGS for cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 usual SGD variants used in modern machine learning. As cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 quantity of training data increases, L-BFGS scales poorly; cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365re are good reasons why almost nobody uses it any more for training on massive quantities of data.
  3. Triplet and quadruplet training. Various recent papers that deal with learning embeddings from data [Triplet]. From an intuitive perspective this makes sense, and cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 training code should be adapted to allow such training.
  4. Better features. The set of features that are currently used are very poor - mnemonic-tuples, graphlets, and large constants that are not divisible by 4 are all that we consider at cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 moment; and operands, structure offsets, strings etc. are all ignored. There is clearly a lot of valuable information to be had here.
  5. Experiments with Graph-NNs. A lot of work on 'learning on graphs' has been performed and published in cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 ML community. Exciting results in that area allow learning of (very simple) graph algorithms (such as shortest path) from examples, it is plausible that cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365se models can beat cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 simple linear model explored here. CCS ‘17 uses such a model, and even if it is hard for me to judge what part of cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365ir performance is due to string matching and what part is cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 rest of cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 model, cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 approach sounds both promising and valid.
  6. Using adjacency information. Functions that were taken from anocá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365r library tend to be adjacent in binaries; a group of functions that come from cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 same binary should provide much stronger evidence that a third-party library is used than an isolated hit.
  7. Replacing cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 ANN tree data-structure with a flat array. Given cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 speed of modern CPUs at linearly sweeping through memory, it is likely that cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 vast majority of users (with less than 100m hashes) does not require cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 complex data structure for ANN search (and cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 resulting storage overhead. For cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 majority of use-cases, a simple linear sweep should be superior to cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 use of bit-permutations as LSH family.

The end (for now).

If you have questions, recommendations, or (ideally) pull requests: Please do not hesitate to contact cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 authors on cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 relevant github repository here.

Thursday, December 13, 2018

Adventures in Video Conferencing Part 5: Where Do We Go from Here?

Posted by Natalie Silvanovich, Project Zero

Overall, our video conferencing research found a total of 11 bugs in WebRTC, FaceTime and WhatsApp. The majority of cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365se were found through less than 15 minutes of mutation fuzzing RTP. We were surprised to find remote bugs so easily in code that is so widely distributed. There are several properties of video conferencing that likely led to cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 frequency and shallowness of cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365se issues.

WebRTC Bug Reporting

When we started looking at WebRTC, we were surprised to discover that cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365ir website did not describe how to report vulnerabilities to cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 project. They had an open bug tracker, but no specific guidance on how to flag or report vulnerabilities. They also provided no security guidance for integrators, and cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365re was no clear way for integrators to determine when cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365y needed to update cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365ir source for security fixes. Many integrators seem to have branched WebRTC without consideration for applying security updates. The combination of cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365se factors make it more likely that vulnerabilities did not get reported, vulnerabilities or fixes got ‘lost’ in cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 tracker, fixes regressed or fixes did not get applied to implementations that use cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 source in part.

We worked with cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 WebRTC team to add this guidance to cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 site, and to clarify cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365ir vulnerability reporting process. Despite cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365se changes, several large software vendors reached out to our team with questions about how to fix cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 vulnerabilities we reported. This shows cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365re is still a lack of clarity on how to fix vulnerabilities in WebRTC.

Video Conferencing Test Tools

We also discovered that most video conferencing solutions lack adequate test tools. In most implementations, cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365re is no way to collect data that allows for problems with an RTP stream to be diagnosed. The vendors we asked did not have such a tool, even internally.  WebRTC had a mostly complete tool that allows streams to be recorded in cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 browser and replayed, but it did not work with streams that used non-default settings. This tool has now been updated to collect enough data to be able to replay any stream. The lack of tooling available to test RTP implementations likely contributed to cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 ease of finding vulnerabilities, and certainly made reproducing and reporting vulnerabilities more difficult

Video Conferencing Standards

The standards that comprise video conferencing such as RTP, RTCP and FEC introduce a lot of complexity in achieving cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365ir goal of enabling reliable audio and video streams across any type of connection. While cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 majority of this complexity provides value to cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 end user, it also means that it is inherently difficult to implement securely.

The Scope of Video Conferencing

WebRTC has billions of users. While it was originally created for use in cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 Chrome browser, it is now integrated by at least two Android applications that eclipse Chrome in terms of users: Facebook and WhatsApp (which only uses part of WebRTC). It is also used by Firefox and Safari. It is likely that most mobile devices run multiple copies of cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 WebRTC library. The ubiquity of WebRTC coupled with cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 lack of a clear patch strategy make it an especially concerning target for attackers.

Recommendations for Developers

This section contains recommendations for developers who are implementing video conferencing based on our observations from this research.

First, it is a good idea to use an existing solution for video conferencing (eicá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365r WebRTC or PJSIP) as opposed to implementing a new one. Video conferencing is very complex, and every implementation we looked at had vulnerabilities, so it is unlikely a new implementation would avoid cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365se problems. Existing solutions have undergone at least some security testing and would likely have fewer problems.

It is also advisable to avoid branching existing video conferencing code. We have received questions from vendors who have branched WebRTC, and it is clear that this makes patching vulnerabilities more difficult. While branching can solve problems in cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 short term, integrators often regret it in cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 long term.

It is important to have a patch strategy when implementing video conferencing, as cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365re will inevitably be vulnerabilities found in any implementation that is used. Developers should understand how security patches are distributed for any third-party library cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365y integrate, and have a plan for applying cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365m as soon as cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365y are available.

It is also important to have adequate test tools for a video conferencing application, even if a third-party implementation is used. It is a good idea to have a way to reproduce a call from end to end. This is useful in diagnosing crashes, which could have a security impact, as well as functional problems.

Several mobile applications we looked at had unnecessary attack surface. Specifically codecs and ocá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365r features of cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 video conferencing implementation were enabled and accessible via RTP even though no legitimate call would ever use cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365m. WebRTC and PJSIP support disabling specific features such as codecs and FEC. It is a good idea to disable cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 features that are not being used.

Finally, video conferencing vulnerabilities can generally be split into those that require cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 target to answer cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 incoming call, and those that do not. Vulnerabilities that do not require cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 call to be answered are more dangerous. We observed that some video conferencing applications perform much more parsing of untrusted data before a call is answered than ocá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365rs. We recommend that developers put as much functionality after cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 call is answered as possible.

Tools


In order to open up cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 most popular video conferencing implementations to more security research, we are releasing cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 tools we developed to do this research. Street Party is a suite of tools that allows cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 RTP streams of video conferencing implementations to be viewed and modified. It includes:

  • WebRTC: instructions for recording and replaying RTP packets using WebRTC’s existing tools
  • FaceTime: hooks for recording and replaying FaceTime calls
  • WhatsApp: hooks for recording and replaying WhatsApp calls on Android

We hope cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365se tools encourage even more investigation into cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 security properties of video conferencing. Contributions are welcome.

Conclusion


We reviewed WebRTC, FaceTime and WhatsApp and found 11 serious vulnerabilities in cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365ir video conferencing implementations. Accessing and altering cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365ir encrypted content streams required substantial tooling. We are releasing this tooling to enable additional security research on cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365se targets. There are many properties of video conferencing that make it susceptible to vulnerabilities. Adequate testing, conservative design and frequent patching can reduce cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 security risk of video conferencing implementations.