Write a Blog >>
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

11:00 - 12:30: OOPSLA - Abstract Interpretation at Attica
Chair(s): John HughesChalmers University of Technology, Sweden
splash-2019-oopsla11:00 - 11:22
Zhuo ZhangPurdue University, Wei YouPurdue University, Guanhong TaoPurdue University, Guannan WeiPurdue University, Yonghwi KwonUniversity of Virginia, Xiangyu ZhangPurdue University
DOI Pre-print
splash-2019-oopsla11:22 - 11:45
Guannan WeiPurdue University, Yuxuan ChenPurdue University, Tiark RompfPurdue University
splash-2019-oopsla11:45 - 12:07
Benno SteinUniversity of Colorado Boulder, Benjamin Barslev NielsenAarhus University, Bor-Yuh Evan ChangUniversity of Colorado Boulder | Amazon, Anders MøllerAarhus University
splash-2019-oopsla12:07 - 12:30
Sven KeidelJGU Mainz, Sebastian ErdwegJGU Mainz
DOI Pre-print