Automation of the reverse engineering of unknown binary network protocols

Abstract

In an interconnected world, comprehending communication systems is imperative yet challenging for undisclosed protocols. Protocol reverse engineering (PRE) is the process of inferring the message syntax, message types, and grammar of such an unknown network protocol that lacks a formal specification.

We survey related work addressing PRE via its three types: dynamic entity analysis (DEA), static traffic analysis (STA), and dynamic traffic analysis (DTA). DEA observes the dynamic program flow of the communicating software. STA solely observes traffic traces of communication using that protocol. DTA actively probes the input of communicating entities and interprets their responses.

Our re-implementation of existing methodologies underscores the complexity and expertise needed for DEA. In contrast, STA follows a typical sequence, as we show by deriving a process shared by prior work. Previous research primarily covers human-readable protocols, neglecting tightly packed binary protocols. Grammar inference has reached a mature state in existing research. Consequently, our contributions to proprietary binary network protocols focus on automating the analysis of message syntax, content data types, and message types. In our model, the process to reverse engineer a protocol specification from traces consists of preparation, data collection and preprocessing, feature extraction, message format inference, message type identification, semantic deduction, behavior model reconstruction, and processing of results. Finally, we consider the challenges of DTA as an outlook toward new research opportunities.

Our key contributions include the following: (1) NemeSYS: An analytical method for approximating message field boundaries in feature extraction. It finds byte sub-sequences, so-called segments, of each message. NemePCA refines this segmentation to infer the message formats. We devised a novel measure to determine the correctness of a message format: the Format Match Score (FMS). (2) We introduce the notion of continuous segment similarity measured by the novel Canberra-Ulm dissimilarity. It enables comparison of segments regardless of their length. (3) Our message type identification approach NemeTYL combines the continuous segment similarity measure with sequence alignment by which we achieve a robust clustering of whole messages. The message clusters correspond to specific functions in the protocol state machine serving as input for existing grammar inference methods. Finally, (4) NemeFTR: An algorithm for semantic deduction of field data based on segment similarity and statistical properties.

Our proposed methods reliably infer protocol specifications without requiring access to program flow or source code. The gained knowledge supports network analysis and security tasks, including vulnerability testing, honeypot deployment, botnet analysis, and automated network modeling.