In order to automatically parse message formats of unknown application-layer protocols, this paper proposes an approach to optimally segment the message formats without a priori knowledge. A hidden semi-Markov model (HSMM) is established for the segmentation and its parameters are estimated from a set of message sequences collected from application sessions. By using the estimated HSMM in the maximum most likely segmentation, a message can be optimally divided into segments and keywords that provide semantic information about the segments can be extracted. This approach does not require the training set to be absolutely pure. The noise mixed in the training set can be filtered out based on its likelihood fitting to the HSMM. The experiments conducted in this paper show that the approach is suited to both text and binary protocols. The application-layer signatures constructed from the extracted keywords are highly accurate in identifying the protocols. The noise mixed in the training set can be efficiently detected and automatically filtered out.