一种基于HMM的短波电台PACTOR协议识别技术

苏龙　卢选民　王剑亮　潘勃

摘 要： 采用了一种基于HMM的比特流协议识别技术，首先通过模式匹配算法对原比特流进行分类，然后采用隐式马尔科夫模型对量化后的数据进行处理和计算。实验结果表明，它不仅能够对带有混淆协议数据的比特流进行识别，而且可以克服数据包不完整的缺点，并使得协议识别所需时间大大降低。

关键词： 协议识别； 模式匹配； KMP算法； 隐式马尔科夫模型

中图分类号： TN915?34； TP393 文献标识码： A 文章编号： 1004?373X（2014）09?0001?03

在日益激烈的电子对抗中，从侦察截获的通信比特流序列中进一步识别未知通信协议是一个重要课题。短波是惟一不受网络枢钮和有源中继体制约的远程通信手段，一旦发生战争或灾害，各种通信网络都可能受到破坏，卫星也可能受到攻击，在这种情况下，无论哪种通信方式，其抗毁能力和自主通信能力与短波无可相比[1]。PACTOR由于其为短波优化了的协议，可以在恶劣的短波段传播环境中提供更快的传送速度，并且可以方便地使用扩展的ASCII码，是短波段数据传送较流行的一种方式[2]。因此，从比特流中快速、准确识别PACTOR协议具有非常重要的意义。目前国内外对短波电台协议的识别主要集中在信号层面上，尚无针对比特流的短波电台协议识别方法。本文在大量分析现有的PACTOR协议的基础上，提出了一种基于HMM的比特流识别技术。

1 隐式马尔科夫模型

隐式马尔科夫模型[3?6]（Hidden Markov models，HMM）是马尔科夫链的一种，它的状态不能直接观察到，但能通过观测向量序列观察到，每个观测向量都是通过某些概率密度分布表示为各种状态，每一个观测向量是由一个具有相应概率密度分布的状态序列产生。所以，隐马尔可夫模型是一个双重随机过程，具有一定状态数的隐马尔可夫链和显示随机函数集。其中，马尔科夫链描述了状态的转移，一般用转移概率矩阵描述；而一般随机过程描述状态和观测序列间的关系，用混淆概率矩阵描述。一个完整的隐式马尔科夫可被定义为一个五元组：[λ=（S，V，Π，A，B），]其定义如下：

有限状态集合：[S={s1，s2，…，sN}。]

有限观察符号集合：[V={v1，v2，…，vM}。]

初始状态的概率分布：[Π={πi}，i∈S。]

状态转移概率矩阵：[AN×N={aij}，i，j∈S。]

观察符号发射概率分布：[BN×M={bik}，][i∈S，k∈V。]

2 基于HMM的PACTOR协议比特流识别技术

2.1 PACTOR协议数据包格式分析

对于一个完整的PACTOR数据包，根据PACTOR协议[7]的数据单元格式，其最开始的8个比特位是头字节，它的值是固定的01010101（0x55）。如果在比特流中有8个比特位值为0x55，那么就代表该比特流中有可能存在使用PACTOR协议的数据包。同时，PACTOR数据包中第74～76（波特率为100）或170～172（波特率为200）比特位被定义为data type，其作用是标识数据包中DATA的类型。

综上，可知该字段指定中的内容是可以预期的，因此可以优先考虑采用模式匹配算法中的快速模式匹配算法（Knuth?Morris?Pratt Algorithm，KMP）[8?9]，对数据包中的比特流进行预处理。

2.2 数据预处理

根据PACTOR协议数据包的格式特征，KMP算法首先对源比特流文件进行一次扫描，得到了在原文件中静态特征Header出现的位置。并根据这些位置对原比特流进行切割，最终得到多个以0x55开头的子比特流。

接着，读取各个子比特流中在位置Status byte字段的Data type上出现的3位比特值。由于该位置的值已由PACTOR帧格式定义，所以为了简化HMM模型，按照表1所示规则对各子比特流进行量化。通过特征位的量化值，得到了符合隐式马尔科夫模型的观察符号序列。

表1 Data type量化值规则对照表

[b2b3b4（Data type）＼&描述＼&量化值＼&000＼&ASCII 8 b＼&1＼&001＼&Huffman＼&2＼&010＼&Huffman（swapped，‘upper case）＼&2＼&011＼&reserved＼&0＼&100＼&PMC German（normal）＼&3＼&101＼&PMC German（swapped）＼&3＼&110＼&PMC English（normal）＼&3＼&111＼&PMC English（swapped） ＼&3＼&]

2.3 HMM模型的建立

为简化模型，减少计算量，HMM 模型中采用离散型随机变量构建模型参数[10]。

有限状态集合中具有2个元素：0（若该序列采取PACTOR协议）、1（若该序列未采取PACTOR协议）；有限观察符号集合中具有4个元素，具体定义如下所示：

[si=1，若该序列采取PACTOR协议0，若该序列未采取PACTOR协议]

[vi=1，i=02，i=1，23，i=4，5，6，70，i=else]

其余模型参数均为随机生成，并由计算得出。HMM的训练过程在[ΔP（V|λ）<ε=0.01]时完成迭代，训练时每次迭代产生新的调整后重估模型[λ=（Π，A，B），]公式如下：

[πi=α1（i）β1（i）P（O|λ）， aij=t=1T-1αt（i）aijbjot+1βt+1（j）t=1T-1αt（i）βt（i）P（O|λ）]

[bik={t|O（t）=k，1≤t≤T}αt（i）βt（i）P（O|λ）t=1Tαt（i）βt（i）P（O|λ）]

式中[αt（i），][βt（i）]分别为模型在[t]时刻的前向、后向变量。在训练HMM模型时，前向变量、后向变量均可能由于计算值过小而被误认为0，为了解决这个问题，采用取自然对数的方法，以确保训练计算中的变量值均处在可用范围内。

3 实验结果与分析

在试验中，按照前述的识别技术，构造了一个2状态、4符号的HMM模型，并采用Visual C++ 6.0编程实现，其KMP处理程序[11]如下：

// KMP string matching algorithm

private bool KMPSearch（int m， int n， string P， string T）

{ int i， j；

bool found；

int[] b = new int[m]；

b = Overlap（m， P）；

j = 0；

i = 0；

found = false；

while （（i

{while（（j>0）&&（！（P.Substring（j，1）.Equals（T.Substring（i，1）））））

{j=b[j-1]；}

if （P.Substring（j，1）.Equals（T.Substring（i，1）））

{ j++；}

if（j==m）

{found=true；}

else

{i++；}

}

return found；

}

// overlap function supporting KMP string matching algorithm

private int[] Overlap（int m， string P）

{ int k， q；

int[] b=new int[m]；

b[0]=0；

q=1；

k=0；

for （q=1； q

{while（（k>0）&&（！（P.Substring（q，1）.Equals（

P.Substring（k，1）））））

{k=b[k]；}

if（P.Substring（q，1）.Equals（P.Substring（k，1）））

{k++；}

b[q]=k；

}

return b； }

测试主界面如图1所示。

这里选用抓取到的任意一部分PACTOR数据包作为训练数据，另一部分作为测试数据，同时将部分其他协议数据包作为混淆数据。此外，为了验证本算法不仅对完整数据包有效，也对抓取到的非完整数据包有效，采取将部分数据包内的数据进行删减的方法。通过调整混淆比，分别在完整数据包和非完整数据包下进行了7组方案测试。同时，为了避免训练集对实验结果带来影响，每组均选取同等数量的训练数据和测试数据。测试结果如图2所示。

图1 基于HMM的协议测试主界面

图2 基于HMM的PACTOR协议识别技术测试结果

由图2可以看出，完整数据包情况下，PACTOR数据包的识别率均在80%以上，在非完整数据包情况下，PACTOR协议的识别率较完整数据包情况的测试结果有所下降，但也达到了70%以上。随着测试数据样本中PACTOR协议所占比重的减小，识别率均略有下降。而且在PACTOR协议所占比率减小的情况下，测试比率有所波动，这是由于混淆数据中所存在的部分冗余数据影响到预处理时快速模式匹配算法所导致的。同时，在实验中发现，它仅需扫描一次源比特流就能得到建立HMM所需的数据，并且不需要记录特定模式串在源比特流中的位置信息，这就减少了对数据库的访问和操作，进而降低了I/O操作的时间消耗。因此该技术是可行并且有效的。

4 结 语

比特流识别未知短波电台协议是一个全新的课题。本文提出的基于HMM的比特流协议识别技术，首先采用KMP对比特流进行处理分类，接着定义了data type数据位量化规则，从而初始化了HMM模型中各个参数，并将随机采集到的数据一部分应用到HMM模型的训练中，随之将训练后的模型应用到具体的测试过程中。实验结果表明，该技术不仅能够从比特级实现对协议的分析和识别，而且解决了传统协议识别算法面对不完整数据包时遇到的不同瓶颈与难题。因此，具有一定的实用价值。但该技术也有不足，在预处理数据时仅仅采用静态的模式识别算法并不可靠，下一步的研究工作可以考虑采用数据挖掘的方法对比特流进行处理，以改进该技术。

参考文献

[1] 聂东举，叶进，闫坤，等.基于SVM算法的短波通信协议识别技术[J].系统工程与电子技术，2013，35（5）：1307?1311.

[2] 程磊.短波自适应调制信号的识别技术研究与实现[D].郑州：信息工程大学，2006.

[3] 朱树永.协议识别技术研究[D].长沙：国防科学技术大学，2008.

[4] CHANDGOTIA N， HAN G Y， MARCUS B， et al. One?dimensional Markov random fields， Markov chains and topological Markov fields [J]. Proceedings of the American Mathematical Society， 2013， 142（1）： 227?242.

[5] LI Xiao?bin， QIAN Jian?sheng， ZHAO Zhi?kai. Special event time predication for mine belt conveyor based on hidden Markov model [J]. Journal of Software， 2013， 8（1）： 142?150.

[6] LI X G. speech recognition approach based on speech feature clustering and HMM [J]. Journal of Computers， 2012， 7（9）： 221?231.

[7] FORD Steve.HF/VHF数字通信手册[M].北京：人民邮电出版社，2010.

[8] KNUTH D E， MORRIS JR J H， PRATT V R. Fast pattern matching in strings [J]. SIAM Journal on Computing， 1977， 6（2）： 323?350.

[9] SUNDAY D M. A very fast substring search algorithm [J]. Communications of the ACM， 1990， 33（8）： 132?142.

[10] 王杨德.面向比特流的协议帧头结构分析研究[D].上海：上海交通大学，2013.

[11] AHMED F. A study on local binary pattern for automated weed classification using template matching and support vector machine [C]// 2011 IEEE 12th International Symposium on Computational Intelligence and Informatics. Budapest， Hungary： CINTI， 2011： 329?334.

式中[αt（i），][βt（i）]分别为模型在[t]时刻的前向、后向变量。在训练HMM模型时，前向变量、后向变量均可能由于计算值过小而被误认为0，为了解决这个问题，采用取自然对数的方法，以确保训练计算中的变量值均处在可用范围内。

3 实验结果与分析

在试验中，按照前述的识别技术，构造了一个2状态、4符号的HMM模型，并采用Visual C++ 6.0编程实现，其KMP处理程序[11]如下：

// KMP string matching algorithm

private bool KMPSearch（int m， int n， string P， string T）

{ int i， j；

bool found；

int[] b = new int[m]；

b = Overlap（m， P）；

j = 0；

i = 0；

found = false；

while （（i

{while（（j>0）&&（！（P.Substring（j，1）.Equals（T.Substring（i，1）））））

{j=b[j-1]；}

if （P.Substring（j，1）.Equals（T.Substring（i，1）））

{ j++；}

if（j==m）

{found=true；}

else

{i++；}

}

return found；

}

// overlap function supporting KMP string matching algorithm

private int[] Overlap（int m， string P）

{ int k， q；

int[] b=new int[m]；

b[0]=0；

q=1；

k=0；

for （q=1； q

{while（（k>0）&&（！（P.Substring（q，1）.Equals（

P.Substring（k，1）））））

{k=b[k]；}

if（P.Substring（q，1）.Equals（P.Substring（k，1）））

{k++；}

b[q]=k；

}

return b； }

测试主界面如图1所示。

这里选用抓取到的任意一部分PACTOR数据包作为训练数据，另一部分作为测试数据，同时将部分其他协议数据包作为混淆数据。此外，为了验证本算法不仅对完整数据包有效，也对抓取到的非完整数据包有效，采取将部分数据包内的数据进行删减的方法。通过调整混淆比，分别在完整数据包和非完整数据包下进行了7组方案测试。同时，为了避免训练集对实验结果带来影响，每组均选取同等数量的训练数据和测试数据。测试结果如图2所示。

图1 基于HMM的协议测试主界面

图2 基于HMM的PACTOR协议识别技术测试结果

由图2可以看出，完整数据包情况下，PACTOR数据包的识别率均在80%以上，在非完整数据包情况下，PACTOR协议的识别率较完整数据包情况的测试结果有所下降，但也达到了70%以上。随着测试数据样本中PACTOR协议所占比重的减小，识别率均略有下降。而且在PACTOR协议所占比率减小的情况下，测试比率有所波动，这是由于混淆数据中所存在的部分冗余数据影响到预处理时快速模式匹配算法所导致的。同时，在实验中发现，它仅需扫描一次源比特流就能得到建立HMM所需的数据，并且不需要记录特定模式串在源比特流中的位置信息，这就减少了对数据库的访问和操作，进而降低了I/O操作的时间消耗。因此该技术是可行并且有效的。

4 结 语

比特流识别未知短波电台协议是一个全新的课题。本文提出的基于HMM的比特流协议识别技术，首先采用KMP对比特流进行处理分类，接着定义了data type数据位量化规则，从而初始化了HMM模型中各个参数，并将随机采集到的数据一部分应用到HMM模型的训练中，随之将训练后的模型应用到具体的测试过程中。实验结果表明，该技术不仅能够从比特级实现对协议的分析和识别，而且解决了传统协议识别算法面对不完整数据包时遇到的不同瓶颈与难题。因此，具有一定的实用价值。但该技术也有不足，在预处理数据时仅仅采用静态的模式识别算法并不可靠，下一步的研究工作可以考虑采用数据挖掘的方法对比特流进行处理，以改进该技术。

参考文献

[1] 聂东举，叶进，闫坤，等.基于SVM算法的短波通信协议识别技术[J].系统工程与电子技术，2013，35（5）：1307?1311.

[2] 程磊.短波自适应调制信号的识别技术研究与实现[D].郑州：信息工程大学，2006.

[3] 朱树永.协议识别技术研究[D].长沙：国防科学技术大学，2008.

[4] CHANDGOTIA N， HAN G Y， MARCUS B， et al. One?dimensional Markov random fields， Markov chains and topological Markov fields [J]. Proceedings of the American Mathematical Society， 2013， 142（1）： 227?242.

[5] LI Xiao?bin， QIAN Jian?sheng， ZHAO Zhi?kai. Special event time predication for mine belt conveyor based on hidden Markov model [J]. Journal of Software， 2013， 8（1）： 142?150.

[6] LI X G. speech recognition approach based on speech feature clustering and HMM [J]. Journal of Computers， 2012， 7（9）： 221?231.

[7] FORD Steve.HF/VHF数字通信手册[M].北京：人民邮电出版社，2010.

[8] KNUTH D E， MORRIS JR J H， PRATT V R. Fast pattern matching in strings [J]. SIAM Journal on Computing， 1977， 6（2）： 323?350.

[9] SUNDAY D M. A very fast substring search algorithm [J]. Communications of the ACM， 1990， 33（8）： 132?142.

[10] 王杨德.面向比特流的协议帧头结构分析研究[D].上海：上海交通大学，2013.

[11] AHMED F. A study on local binary pattern for automated weed classification using template matching and support vector machine [C]// 2011 IEEE 12th International Symposium on Computational Intelligence and Informatics. Budapest， Hungary： CINTI， 2011： 329?334.

式中[αt（i），][βt（i）]分别为模型在[t]时刻的前向、后向变量。在训练HMM模型时，前向变量、后向变量均可能由于计算值过小而被误认为0，为了解决这个问题，采用取自然对数的方法，以确保训练计算中的变量值均处在可用范围内。

3 实验结果与分析

在试验中，按照前述的识别技术，构造了一个2状态、4符号的HMM模型，并采用Visual C++ 6.0编程实现，其KMP处理程序[11]如下：

// KMP string matching algorithm

private bool KMPSearch（int m， int n， string P， string T）

{ int i， j；

bool found；

int[] b = new int[m]；

b = Overlap（m， P）；

j = 0；

i = 0；

found = false；

while （（i

{while（（j>0）&&（！（P.Substring（j，1）.Equals（T.Substring（i，1）））））

{j=b[j-1]；}

if （P.Substring（j，1）.Equals（T.Substring（i，1）））

{ j++；}

if（j==m）

{found=true；}

else

{i++；}

}

return found；

}

// overlap function supporting KMP string matching algorithm

private int[] Overlap（int m， string P）

{ int k， q；

int[] b=new int[m]；

b[0]=0；

q=1；

k=0；

for （q=1； q

{while（（k>0）&&（！（P.Substring（q，1）.Equals（

P.Substring（k，1）））））

{k=b[k]；}

if（P.Substring（q，1）.Equals（P.Substring（k，1）））

{k++；}

b[q]=k；

}

return b； }

测试主界面如图1所示。

这里选用抓取到的任意一部分PACTOR数据包作为训练数据，另一部分作为测试数据，同时将部分其他协议数据包作为混淆数据。此外，为了验证本算法不仅对完整数据包有效，也对抓取到的非完整数据包有效，采取将部分数据包内的数据进行删减的方法。通过调整混淆比，分别在完整数据包和非完整数据包下进行了7组方案测试。同时，为了避免训练集对实验结果带来影响，每组均选取同等数量的训练数据和测试数据。测试结果如图2所示。

图1 基于HMM的协议测试主界面

图2 基于HMM的PACTOR协议识别技术测试结果

由图2可以看出，完整数据包情况下，PACTOR数据包的识别率均在80%以上，在非完整数据包情况下，PACTOR协议的识别率较完整数据包情况的测试结果有所下降，但也达到了70%以上。随着测试数据样本中PACTOR协议所占比重的减小，识别率均略有下降。而且在PACTOR协议所占比率减小的情况下，测试比率有所波动，这是由于混淆数据中所存在的部分冗余数据影响到预处理时快速模式匹配算法所导致的。同时，在实验中发现，它仅需扫描一次源比特流就能得到建立HMM所需的数据，并且不需要记录特定模式串在源比特流中的位置信息，这就减少了对数据库的访问和操作，进而降低了I/O操作的时间消耗。因此该技术是可行并且有效的。

4 结 语

比特流识别未知短波电台协议是一个全新的课题。本文提出的基于HMM的比特流协议识别技术，首先采用KMP对比特流进行处理分类，接着定义了data type数据位量化规则，从而初始化了HMM模型中各个参数，并将随机采集到的数据一部分应用到HMM模型的训练中，随之将训练后的模型应用到具体的测试过程中。实验结果表明，该技术不仅能够从比特级实现对协议的分析和识别，而且解决了传统协议识别算法面对不完整数据包时遇到的不同瓶颈与难题。因此，具有一定的实用价值。但该技术也有不足，在预处理数据时仅仅采用静态的模式识别算法并不可靠，下一步的研究工作可以考虑采用数据挖掘的方法对比特流进行处理，以改进该技术。

参考文献

[1] 聂东举，叶进，闫坤，等.基于SVM算法的短波通信协议识别技术[J].系统工程与电子技术，2013，35（5）：1307?1311.

[2] 程磊.短波自适应调制信号的识别技术研究与实现[D].郑州：信息工程大学，2006.

[3] 朱树永.协议识别技术研究[D].长沙：国防科学技术大学，2008.

[4] CHANDGOTIA N， HAN G Y， MARCUS B， et al. One?dimensional Markov random fields， Markov chains and topological Markov fields [J]. Proceedings of the American Mathematical Society， 2013， 142（1）： 227?242.

[5] LI Xiao?bin， QIAN Jian?sheng， ZHAO Zhi?kai. Special event time predication for mine belt conveyor based on hidden Markov model [J]. Journal of Software， 2013， 8（1）： 142?150.

[6] LI X G. speech recognition approach based on speech feature clustering and HMM [J]. Journal of Computers， 2012， 7（9）： 221?231.

[7] FORD Steve.HF/VHF数字通信手册[M].北京：人民邮电出版社，2010.

[8] KNUTH D E， MORRIS JR J H， PRATT V R. Fast pattern matching in strings [J]. SIAM Journal on Computing， 1977， 6（2）： 323?350.

[9] SUNDAY D M. A very fast substring search algorithm [J]. Communications of the ACM， 1990， 33（8）： 132?142.

[10] 王杨德.面向比特流的协议帧头结构分析研究[D].上海：上海交通大学，2013.

[11] AHMED F. A study on local binary pattern for automated weed classification using template matching and support vector machine [C]// 2011 IEEE 12th International Symposium on Computational Intelligence and Informatics. Budapest， Hungary： CINTI， 2011： 329?334.