Write a Blog >>
SPLASH 2019
Sun 20 - Fri 25 October 2019 Athens, Greece
Wed 23 Oct 2019 11:00 - 11:22 at Attica - Abstract Interpretation Chair(s): John Hughes

Binary program dependence analysis determines dependence between instructions and hence is important for many applications that have to deal with executables without any symbol information. A key challenge is to identify if multiple memory read/write instructions access the same memory location. The state-of-the-art solution is the value set analysis (VSA) that uses abstract interpretation to determine the set of addresses that are possibly accessed by memory instructions. However, VSA is conservative and hence leads to a large number of bogus dependences and then substantial false positives in downstream analyses such as malware behavior analysis. Furthermore, existing public VSA implementations have difficulty scaling to complex binaries. In this paper, we propose a new binary dependence analysis called BDA enabled by a randomized abstract interpretation technique. It features a novel whole program path sampling algorithm that is not biased by path length, and a per-path abstract interpretation avoiding precision loss caused by merging paths in traditional analyses. It also provides probabilistic guarantees. Our evaluation on SPECINT2000 programs shows that it can handle complex binaries such as gcc whereas VSA implementations from the-state-of-art platforms have difficulty producing results for many SPEC binaries. In addition, the dependences reported by BDA are 75 and 6 times smaller than Alto, a scalable binary dependence analysis tool, and VSA, respectively, with only 0.19% of true dependences observed during dynamic execution missed (by BDA). Applying BDA to call graph generation and malware analysis shows that BDA substantially supersedes the commercial tool IDA in recovering indirect call targets and outperforms a state-of-the-art malware analysis tool Cuckoo by disclosing 3 times more hidden payloads.

Wed 23 Oct

Displayed time zone: Beirut change

11:00 - 12:30
Abstract InterpretationOOPSLA at Attica
Chair(s): John Hughes Chalmers University of Technology, Sweden
11:00
22m
Talk
BDA: Practical Dependence Analysis for Binary Executables by Unbiased Whole-Program Path Sampling and Per-Path Abstract InterpretationACM SIGPLAN Distinguished Paper Award
OOPSLA
Zhuo Zhang Purdue University, Wei You Purdue University, Guanhong Tao Purdue University, Guannan Wei Purdue University, Yonghwi Kwon University of Virginia, Xiangyu Zhang Purdue University
DOI Pre-print
11:22
22m
Talk
Staged Abstract Interpreters: Fast and Modular Whole-Program Analysis via Meta-programming
OOPSLA
Guannan Wei Purdue University, Yuxuan Chen Purdue University, Tiark Rompf Purdue University
DOI
11:45
22m
Talk
Static Analysis with Demand-Driven Value Refinement
OOPSLA
Benno Stein University of Colorado Boulder, Benjamin Barslev Nielsen Aarhus University, Bor-Yuh Evan Chang University of Colorado Boulder | Amazon, Anders Møller Aarhus University
DOI Pre-print
12:07
22m
Talk
Sound and Reusable Components for Abstract Interpretation
OOPSLA
Sven Keidel JGU Mainz, Sebastian Erdweg JGU Mainz
DOI