  Determining whether multiple instructions can access the same memory location
is a critical task in binary analysis. It is challenging as statically
computing precise alias information is undecidable in theory. The problem
aggravates at the binary level due to the presence of compiler optimizations
and the absence of symbols and types. Existing approaches either produce
significant spurious dependencies due to conservative analysis or scale poorly
to complex binaries.
  We present a new machine-learning-based approach to predict memory
dependencies by exploiting the model's learned knowledge about how binary
programs execute. Our approach features (i) a self-supervised procedure that
pretrains a neural net to reason over binary code and its dynamic value flows
through memory addresses, followed by (ii) supervised finetuning to infer the
memory dependencies statically. To facilitate efficient learning, we develop
dedicated neural architectures to encode the heterogeneous inputs (i.e., code,
data values, and memory addresses from traces) with specific modules and fuse
them with a composition learning strategy.
  We implement our approach in NeuDep and evaluate it on 41 popular software
projects compiled by 2 compilers, 4 optimizations, and 4 obfuscation passes. We
demonstrate that NeuDep is more precise (1.5x) and faster (3.5x) than the
current state-of-the-art. Extensive probing studies on security-critical
reverse engineering tasks suggest that NeuDep understands memory access
patterns, learns function signatures, and is able to match indirect calls. All
these tasks either assist or benefit from inferring memory dependencies.
Notably, NeuDep also outperforms the current state-of-the-art on these tasks.
