Feature Extraction Optimization for Bitstream Communication Protocol Format Reverse Analysis

The unknown format bitstream network communication protocol not merely brings the challenge to the safe and efficient network management, but also provides the possibility for the security audit and data disclosure of the network communication content. Feature extraction of unknown protocol is an indispensable part of the network protocol reverse. In dealing with this problem, the number of elements in the feature candidate set increases exponentially with the increase of time and the length of frequent items in the existing algorithms such as Apriori and AC(Aho-Corasick). This makes the algorithm have high time and space complexity. In this paper, CFI(Combined Frequent Items) algorithm first employs AC algorithm to generate frequent byte items, then applies Apriori algorithm to perform frequent item matching, and uses location identification to ensure the completeness of feature candidate sets. The experimental results show that compared with the Apriori and AC algorithms, the CFI algorithm can reduce the time complexity by 78% and the space complexity by 60% in time, and can accurately and fleetly analyze the reverse message format from unknown protocols.