Messages of complex protocols usually have long byte sequences and many structure types, which pose serious challenges to protocol reverse analysis. A recursive clustering based method for message structure extraction was proposed. Firstly, the method recursively clustered the messages through progressive multiple sequence alignment in blocks, which separated messages of different structures with smaller scale of sequence alignment. Then, it identified field boundaries according to the rates of change of aligned bytes. Moreover, a new backtracking policy for hierarchical message structure extraction was applied to extract message structures by identifying format distinguisher fields. Experiments on several public protocols showed that the proposed method can derive message formats in BNF form and improve the accuracy of field identification with less time overhead.
