RPKClust: region-partitioned keywords inference for binary protocol reverse

Abstract Protocol reverse engineering is a critical technology for analyzing unknown binary protocols. Message clustering serves as a fundamental and widely adopted step, playing a pivotal role in inferring both protocol format and state machine. Currently, most methods use multiple sequence alignment as a core technique for message clustering, where the degree of difference between messages is calculated. This may lead to the loss of valuable information and incur relatively high costs. To address this issue, we propose a novel binary protocol message clustering method, named RPKClust, based on region-based keyword positioning. By leveraging the characteristics of field offsets in messages, this method divides protocol messages into the fixed-offset region and the non-fixed-offset region. RPKClust adopts different keyword candidate generation strategies in these two regions. Subsequently, keyword fields are inferred through two-stage probability constraints, thus completing the clustering of protocol messages. We evaluated eight widely used protocols, and the results show that RPKClust outperforms the state-of-the-art methods (i.e. Netplier, MDIplier, ProInfer, NEMETYL). Its clustering results achieve a homogeneity of 0.959, a completeness of 0.941, and a V-measure of 0.949, and it significantly reduces the overhead. Furthermore, we validated the effectiveness of RPKClust on two specialized protocols and further verified its significant role in state machine inference.