公开的协议逆向应用,虽然都取得了较理想的效果,但过度依赖人工分析,耗时巨大,研究如何提高协议逆向的自动化和准确性具有重要的现实意义。只依赖于网络协议数据来推断网络协议的方法,不管是先进行报文粗分类再序列比对定位报文格式,还是先进行序列比对再精细定位报文格式,都离不开的就是序列比对算法,所以本文将针对网络协议逆向的序列比对算法作为主要研究方向。本文对序列比对算法中用于衡量比对结果的替换矩阵和目标函数进行了研究,在实验基础上分析清楚了替换矩阵参数的选取对序列比对结果的影响。对三种常用的双序列比对算法LCS算法、NW算法和SW算法进行了时间复杂度比对实验,得出结论虽然三种算法在理论时间复杂度上相同,但由于实现上的细微差异,导致了时间消耗上存在着差异。针对序列比对实验中发现的两个问题:双序列比对算法中,可能存在多个正确解,而遍历所有正确的解会花费不可预知的时间;渐进比对算法中,进行比对的序列先后选择顺序,会影响到比对的结果。而进行网络协议逆向必须要求序列比对结果准确,因此本文设计了一种针对网络协议逆向的序列比对算法,结合了局部比对算法和贪心算法,实验证明,该算法可以不进行结果遍历就能获取到正确的结果,而且使用渐进比对方法时比对序列的顺序选择对结果也不会产生影响,算法的时间效率也比NW算法更高。