Binary diffing is the problem of determining whether two binary programs originate from the same source code. Binary diffing tools are used to identify malware, plagiarism, or code theft. Many instances of binary diffing assume an adversarial setting, where a malicious actor transforms binary code by changing the compiler. Traditional diffing techniques rely on statistical similarity analysis, often leveraging stochastic models. However, recent studies have shown that these classifiers perform poorly in the face of adversarial code transformations. To mitigate this scenario, this paper introduces a new diffing technique that is resilient against current obfuscation approaches. We propose comparing executables by matching their library signatures (libsig). A program’s library signature is the sequence of calls it makes to functions outside its .text section. The proposed classifier, LibSIG, is faster than off-the-shelf alternatives, such as ltrace, and, like it, works on stripped binaries or binaries running with address space layout randomization (ASLR) enabled. Furthermore, in contrast to ltrace, LibSIG can be engineered to detect even library calls that bypass conventional application binary interface patterns. Our experiments on the GNU Core Utilities demonstrate that LibSIG remains robust against obfuscators like Khaos and ollvm, as well as typical optimization patterns, outperforming binary diffing approaches such as SAFE, BinDiff, or Asm2Vec.

Abstract The automatic recovery of a program's high‐level representation from its binary version is a well‐studied problem in programming languages. However, most of the solutions to this problem are based on purely static approaches: techniques such as dataflow analyses or type inference are used to convert the bytes that constitute the executable code back into a control flow graph (CFG). This article departs from such a modus operandi to show that a dynamic analysis can be effective and useful, both as a standalone technique, and as a way to enhance the precision of static approaches. The experimental results provide evidence that completeness, that is, the ability to conclude that the entire CFG has been discovered, is achievable on many functions that are part of industry‐strong benchmarks. Experiments also indicate that dynamic information greatly enhances the ability of DynInst, a state‐of‐the‐art binary reconstructor, to deal with code stripped of debugging information. These results were obtained with CFGgrind, a new implementation of a dynamic code reconstructor, built on top of Valgrind. When applied to cBench, CFGgrind is 9% faster than callgrind, Valgrind's tool used to track targets of function calls; and 7% faster in Spec Cpu2017. CFGgrind recovers the complete CFG of 40% of all the procedures invoked during the standard execution of programs in Spec Cpu2017, and 37% in cBench. When combined with CFGgrind, DynInst finds 15% more CFGs for cBench, and 7% more CFGs for Spec Cpu2017. Finally, CFGgrind is more than 7 times faster than DCFG, a CFG reconstructor from Intel, and 1.30 times faster than bfTrace, a CFG reconstructor used in research. CFGgrind is also more precise than these two tools, handling operating system signals, shared code in functions, and unaligned instructions; besides supporting multithreaded programs, exact profiling and incremental refinements.

An efficient way to evaluate FCA algorithms is through a comparative analysis of their performance in typical contexts. Comparisons are normally conducted using randomly generated contexts that may contain duplicated attributes and objects and other types of redundancies. Failing to acknowledge the presence of these redundancies in formal contexts could lead to erroneous comparison analysis. This paper proposes a tool named SCGaz (Synthetic Context Generator) that randomly fills synthetic formal contexts ensuring the absence of some type of redundancies. At the same time, the tool is able to keep track of the contexts density, allowing users to select any density in the bounds of the minimum and maximum permitted for a type of context. Thus, this approach allows more controllable and reliable simulation environment. In this work, an analysis of the time spent to generate different types of formal contexts, including large ones, is presented. As a case study, a performance comparison between Object Intersection algorithm and its dual version, Attribute Intersections, with contexts generated by SCGaz is discussed. Contexts produced by SCGaz in conjunction with real world dataset allow a more in-depth comparative analysis of FCA algorithms performance.