Morphological analysis© is a breakthrough technology for binary code analysis. It is the result of many years of research in LORIA, a research institute in Nancy, France. It is a fast and scalable solution to find similarities between different software.
Some of our secrets :
In order to achieve meaningful results, we strived towards a high level of semantics using Control Flow Graphs.
After applying some graph rewriting rules to normalise them, we tackled the subgraph search problem in a both efficient and convenient way for that perticular kind of graphs.
Considered from algorithm's complexity and on computational models, malicious software are interesting in that they push cybersecurity tools to their limits by placing them in worst-case scenario. For these steps to succeed, some pitfalls needed to be considered.
First, the computation of the control flow graph is an undecidable problem.
Dynamic analysis must be combined with static disassembly in order to get it right in most cases. Second, shared binary code is not always relevant and may be seen as false positives. For instance, very different software may statically embed the same standard libraries. The use of a white list as a parameter for graph rewriting is a way to get an even higher abstraction of the control flow graph.
We are now working on data flows to bring additional useful information to our algorithms.