A progressive learning method on unknown protocol behaviors

Reverse analyzing of unknown protocol behaviors keeps being a tough nut in Protocol Reverse Engineering (PRE), which infers specifications of unknown protocols by observable information, especially when only transmitted messages are available. This paper proposes a novel protocol state machine model Stochastic Protocol finite-state Transducer (SPT) to describe the message interaction rules between communicating terminals in a probabilistic way attempting to simulate behavior rules of unknown protocols in certain implementation. Together with a state related field recognition and compensation method, a progressive SPT learning algorithm of unknown protocols named Sptia-PL, is designed and implemented to reconstruct the SPT of target protocol with the ability to predict succeeding behaviors. By updating the SPT progressively, the proposed method is able to learn continuously in linear time and remain the established model in optimal condition during the whole learning process. This strategy thoroughly avoids the state explosion problem existing in most state machine learning methods of PRE. Experiments on two open and three local collected datasets of FTP, SMTP and POP3 prove the rationality of SPT model and effectiveness of Sptia-PL algorithm by an average Accuracy over 0.94 and a Coverage close to 0.99. The small computing cost O(N) of this method and high confidence of results outperforms all the known state-of-the-art methods significantly.