Workshop on Binary Analysis Research (BAR) 2019
Sunday, 24 February
Dustin Fraze, Program Manager, DARPA I2O
Minkyu Jung (KAIST), Soomin Kim (KAIST), HyungSeok Han (KAIST), Jaeseung Choi (KAIST), Sang Kil Cha (KAIST)
Current binary analysis research focuses mainly on the back-end, but not on the front-end. However, we note that there are several key design points in the front-end that can greatly improve the efﬁciency of binary analyses. To demonstrate our idea, we design and implement B2R2, a new binary analysis platform that is fast with regard to lifting binary code and evaluating the corresponding IR. Our platform is written purely in F#, a functional programming language, without any external dependencies. Thus, it naturally supports pure parallelism. B2R2’s IR embeds metadata in its language for speeding up dataﬂow analyses, and it is designed to be efﬁcient for evaluation. Therefore, any binary analysis technique can beneﬁt from our IR design. We discuss our design decisions to build an efﬁcient binary analysis front-end, and summarize lessons learned. We also make our source code public on GitHub.
Andrea Gussoni (Politecnico di Milano), Alessandro Di Federico (Politecnico di Milano), Pietro Fezzardi (Politecnico di Milano), Giovanni Agosta (Politecnico di Milano)
Binary translation is the process of taking a program compiled for a given CPU architecture and translate it to run on another platform without compromising its functionality. This paper describes a technique for improving runtime performance of statically translated programs.
First, the program to be translated is analyzed to detect function boundaries. Then, each function is cloned, isolated and disentangled from the rest of the executable code. This process is called function isolation, and it divides the code in two separate portions: the isolated realm and the non-isolated realm.
Isolated functions have a simpler control-ﬂow, allowing much more aggressive compiler optimizations to increase performance, but possibly compromising functional correctness. To prevent this risk, this work proposes a mechanism based on stack unwinding to allow seamless transition between the two realms while preserving the semantics, whenever an isolated function unexpectedly jumps to an unforeseen target. In this way, the program runs in the isolated realm with improved performance for most of the time, falling back to the non-isolated realm only when necessary to preserve semantics.
The here proposed stack unwinding mechanism is portable across multiple CPU architectures. The binary translation and the function isolation passes are based on state-of-the-art industry proven open source components – QEMU and LLVM – making them very stable and ﬂexible. The presented technique is very robust, working independently from the quality of the functions boundaries detection. We measure the performance improvements on the SPECint 2006 benchmarks , showing an average of42%improvement,while still passing the functional correctness tests.
Sushma Kalle (University of New Orleans), Nehal Ameen (University of New Orleans), Hyunguk Yoo (University of New Orleans), Irfan Ahmed (Virginia Commonwealth University)
This paper presents CLIK, a new remote attack on the control logic of a programmable logic controller (PLC) in industrial control systems. The control logic deﬁnes how a PLC controls a physical process such as a nuclear plant. A full control logic attack faces two critical challenges: 1) infecting the control logic in a PLC at a ﬁeld site and, 2) hiding the infection from engineering software at a control center since the software can obtain the infected logic from the PLC and reveal it to a control engineer. The existing academic efforts only (partially) address the former. CLIK is a ﬁrst practical control-logic attack that deals with both challenges successfully. It modiﬁes the control logic running in a remote target PLC automatically to disrupt a physical process. CLIK also employs a new virtual PLC approach that hides the malicious modiﬁcations by engaging the engineering software with a captured network trafﬁc of the original (uninfected) control logic. It is fully implemented on real hardware/software used in industrial settings and is made publicly available for academic research on control logic attacks1. CLIK consists of four phases and takes less than a minute to complete an attack cycle. As part of the implementation, we found a critical (zero-day) vulnerability in the password authentication mechanism of a target PLC, which allows the attacker to overwrite password hash in the PLC during the authentication process and gain access to the (protected) control logic. We have disclosed the vulnerability responsibly to the PLC vendor who has already patched the vulnerability2.
Kristopher Micinski (Haverford College), Thomas Gilray (University of Alabama, Birmingham), Daniel Votipka (University of Maryland), Michelle L. Mazurek (University of Maryland), Jeffrey S. Foster (Tufts University)
Understanding whether Android apps are safe requires, among other things, knowing what dynamically triggers an app to use its permissions, and under what conditions. For example, an app might access contacts after a button click, but only if a certain setting is enabled. Automatically inferring such conditional trigger information is difﬁcult because Android is callback-oriented and reasoning about conditions requires analysis of program paths. To address these issues, we introduce Hogarth, an Android app analysis tool that constructs trigger diagrams, which show, post hoc, what sequence of callbacks, under what conditions, led to a permission use observed at run time. Hogarth works by instrumenting apps to produce a trace of relevant events. Then, given a trace, it performs symbolic path tracing—symbolic execution restricted to path segments from that trace—to infer path conditions at key program locations, and path splicing to combine the per-segment information into a trigger diagram. We validated Hogarth by showing its results match those of a manual reverse-engineering effort on ﬁve small apps. Then, in a case study, we applied Hogarth to 12 top apps from Google Play. We found that Hogarth provided more precise information about triggers than prior related work, and was able successfully generate a trigger diagram for all but one permission use in our case study. Hogarth’s performance was generally good, taking at most a few minutes on most of our subject apps. In sum,Hogarth provides a new approach to discovering conditional trigger information for permission uses on Android.
Zhen Huang (Pennsylvania State University), Gang Tan (Pennsylvania State University)
The existence of pre-patch windows allows adversaries to exploit vulnerabilities before they are patched. Prior work has proposed to harden programs with security workarounds to enable users to mitigate vulnerabilities before a patch is available. However, it requires access to the source code of the programs. This paper introduces RVM, an approach to automatically hardening binary code with security workarounds. RVM statically analyzes binary code of programs to identify error-handling code in the programs, in order to synthesize security workarounds. We designed and implemented a prototype of RVM for Windows and Linux binaries. We evaluate the coverage and performance of RVM on binaries of popular Windows and Linux applications containing real-world vulnerabilities.
Aravind Machiry (UC Santa Barbara), Nilo Redini (UC Santa Barbara), Eric Gustafson (UC Santa Barbara), Hojjat Aghakhani (UC Santa Barbara), Christopher Kruegel (UC Santa Barbara), Giovanni Vigna (UC Santa Barbara)
Binary static analysis has seen a recent surge in interest, due to a rise in analysis targets for which no other method is appropriate, such as, embedded ﬁrmware. This has led to the proposal of a number of binary static analysis tools and techniques, handling various kinds of programs, and answering different research questions. While static analysis tools that focus on binaries inherit the undecidability of static analysis, they bring with them other challenges, particularly in dealing with the aliasing of code and data pointers. These tools may tackle these challenges in different ways, but unfortunately, there is currently no concrete means of comparing their effectiveness at solving these central, problem-independent aspects of static analysis.
In this paper, we propose a new method for creating a dataset of real-world programs, paired with the ground truth for static analysis. Our approach involves the injection of synthetic “facts” into a set of open-source programs, consisting of new variables and their possible values. The analyses’ goal is then to evaluate the possible values of these facts at certain program points. As the facts are injected randomly within an arbitrarily-large set of programs, the kinds of data ﬂows that can be measured are widely-varied in size and complexity. We implemented this idea as a prototype system, AUTOFACTS, and used it to create a ground truth dataset of 29 programs, with various types and number of facts, resulting in a total of 2,088 binaries (with 72 versions for each program). To our knowledge, this is the ﬁrst dataset aimed at the problem-independent evaluation of static analysis tools, and we contribute all code and the dataset itself to the community as open-source.
Navid Emamdoost (University of Minnesota), Vaibhav Sharma (University of Minnesota), Taejoon Byun (University of Minnesota), Stephen McCamant (University of Minnesota)
Good tests are important in software development, but it can be hard to tell whether tests will reveal future faults that are themselves unknown. Mutation analysis, which checks whether tests reveal inserted changes in a program, is a strong measure of test suite adequacy, but common source- or compilerlevelapproachestomutationtestingarenotapplicabletosoftware available only in binary form. We explore mutation analysis as an application of the reassembleable disassembly approach to binary rewriting, building a tool for x86 binaries on top of the previously-developed Uroboros system, and apply it to the C benchmarks from SPEC CPU 2006 and to ﬁve examples of embedded control software. The results demonstrate that our approach works effectively across these software domains: as expected, tests designed for performance benchmarking reveal fewer mutants than tests generated to achieve high code coverage, but mutation scores indicate differences in test origins and features such as code size and fault-tolerance. Our binary-level tool also achieves comparable results to source-level mutation analysis despite supporting a more limited set of mutation operators. More generally we also argue that our experience shows how reassembleable disassembly is a valuable approach for constructing novel binary rewriting tools.
Investigating Graph Embedding Neural Networks with Unsupervised Features Extraction for Binary Analysis
Luca Massarelli (Sapienza University of Rome), Giuseppe A. Di Luna (CINI - National Laboratory of Cybersecurity), Fabio Petroni (Independent Researcher), Leonardo Querzoni (Sapienza University of Rome), Roberto Baldoni (Italian Presidency of Ministry Council)
In this paper we investigate the use of graph embedding networks, with unsupervised features learning, as neural architecture to learn over binary functions.
We propose several ways of automatically extract features from the control ﬂow graph (CFG) and we use the structure2vec graph embedding techniques to translate a CFG to a vectors of real numbers. We train and test our proposed architectures on two different binary analysis tasks: binary similarity, and, compiler provenance. We show that the unsupervised extraction of features improves the accuracy on the above tasks, when compared with embedding vectors obtained from a CFG annotated with manually engineered features (i.e., ACFG proposed in ).
We additionally compare the results of graph embedding networks based techniques with a recent architecture that do not make use of the structural information given by the CFG, and we observe similar performances. We formulate a possible explanation of this phenomenon and we conclude identifying important open challenges.
Sheng-Han Wen (National Taiwan University), Wei-Loon Mow (National Taiwan University), Wei-Ning Chen (National Taiwan University), Chien-Yuan Wang (National Taiwan University), Hsu-Chun Hsiao (National Taiwan University)
Constraint solving creates a serious performance bottleneck in symbolic execution. Examining a plethora of SMT solvers with diverse capabilities, we address the following research questions: How can the performance of symbolic execution improve if it can pick a priori the best solver for a given path constraint? How can such a prediction oracle be practically implemented? In this work, we ﬁrst deﬁne the solver selection problem in symbolic execution and its evaluation metrics, and perform a preliminary study to gauge potential performance improvement through solver selection. We then present the design and implementation of Path Constraint Classiﬁer (PCC), a machine learning based meta-solver that aims to reduce overall constraint solving latency by dynamically selecting a solver per query. Using machine learning seems straightforward, yet surprisingly underexplored; one main technical challenge is how to avoid excessive overhead introduced by feature extraction. We address this challenge by taking advantage of the structural characteristics of symbolic execution. Our experiments conﬁrm that the overall solver time can be reduced by 10.3% in the KLEE dataset and 46% in the benchmark dataset, while the solver prediction procedure only accounts for 2% to 10% of overall solving time.
A Cross-Architecture Instruction Embedding Model for Natural Language Processing-Inspired Binary Code Analysis
Kimberly Redmond (University of South Carolina), Lannan Luo (University of South Carolina), Qiang Zeng (University of South Carolina)
Given a closed-source program, such as most of proprietary software and viruses, binary code analysis is indispensable for many tasks, such as code plagiarism detection and malware analysis. Today, source code is very often compiled for various architectures, making cross-architecture binary code analysis increasingly important. A binary, after being disassembled, is expressed in an assembly language. Thus, recent work starts exploring Natural Language Processing (NLP) inspired binary code analysis. In NLP, words are usually represented in high-dimensional vectors (i.e., embeddings) to facilitate further processing, which is one of the most common and critical steps in many NLP tasks. We regard instructions as words in NLP-inspired binary code analysis, and aim to represent instructions as embeddings as well.
To facilitate cross-architecture binary code analysis, our goal is that similar instructions, regardless of their architectures, have embeddings close to each other. To this end, we propose a joint learning approach to generating instruction embeddings that capture not only the semantics of instructions within an architecture, but also their semantic relationships across architectures. To the best of our knowledge, this is the ﬁrst work on building cross-architecture instruction embedding model. As a showcase, we apply the model to resolving one of the most fundamental problems for binary code similarity comparison—semantics-based basic block comparison, and the solution outperforms the code statistics based approach. It demonstrates that it is promising to apply the model to other cross-architecture binary code analysis tasks.
Ryo Ichikawa, Captain of CTF Team TokyoWesterns
Zoya Yeprem (University of Virginia)
Xiaozhu Meng (University of Wisconsin-Madison)