Zhang receives Distinguished Paper Award at OOPSLA'19
12-11-2019
Purdue Computer Science PhD student, Zhuo Zhang (advised by Professor Xiangyu Zhang) and colleagues received a Distinguished Paper Award at the ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA) in October. OOPSLA is one of the top publication venues in the area of programming languages and software systems.
The award paper is led by Purdue CS PhD student Zhuo Zhang and co-authored by Purdue CS PhD students Guanhong Tao and Guannan Wei, Purdue CS Professor Xiangyu Zhang and University of Virginia Assistant Professor Yonghwi Kwon (PhD ’18, Purdue CS) and Renmin University of China Assistant Professor Wei You (former Postdoc, Purdue CS). Their paper, “BDA: Practical Dependence Analysis for Binary Executables by Unbiased Whole-Program Path Sampling and Per-Path Abstract Interpretation," proposes a new binary dependence analysis (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. 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 three times more hidden payloads.
Writer: Emily Kinsell, 765-494-0669, emily@purdue.edu @emilykinsell
Source: Zhuo Zhang, zhan3299@purdue.edu
_____________________________________________________________
Abstract
BDA: Practical Dependence Analysis for Binary Executables by Unbiased Whole-Program Path Sampling and Per-Path Abstract Interpretation
ZHUO ZHANG, Purdue University, USA
WEI YOU∗, Renmin University of China, China
GUANHONG TAO and GUANNAN WEI, Purdue University, USA YONGHWI KWON, University of Virginia, USA
XIANGYU ZHANG, Purdue University, USA
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.