  Reverse engineers benefit from the presence of identifiers such as function
names in a binary, but usually these are removed for release. Training a
machine learning model to predict function names automatically is promising but
fundamentally hard: unlike words in natural language, most function names occur
only once. In this paper, we address this problem by introducing eXtreme
Function Labeling (XFL), an extreme multi-label learning approach to selecting
appropriate labels for binary functions. XFL splits function names into tokens,
treating each as an informative label akin to the problem of tagging texts in
natural language. We relate the semantics of binary code to labels through
DEXTER, a novel function embedding that combines static analysis-based features
with local context from the call graph and global context from the entire
binary. We demonstrate that XFL/DEXTER outperforms the state of the art in
function labeling on a dataset of 10,047 binaries from the Debian project,
achieving a precision of 83.5%. We also study combinations of XFL with
alternative binary embeddings from the literature and show that DEXTER
consistently performs best for this task. As a result, we demonstrate that
binary function labeling can be effectively phrased in terms of multi-label
learning, and that binary function embeddings benefit from including explicit
semantic features.
