一種基于HMM的短波電臺PACTOR協(xié)議識別技術
2014-06-19 08:23:04蘇龍盧選民王劍亮潘勃
現(xiàn)代電子技術 2014年9期
蘇龍 盧選民 王劍亮 潘勃
摘 要： 采用了一種基于HMM的比特流協(xié)議識別技術，首先通過模式匹配算法對原比特流進行分類，然后采用隱式馬爾科夫模型對量化后的數據進行處理和計算。實驗結果表明，它不僅能夠對帶有混淆協(xié)議數據的比特流進行識別，而且可以克服數據包不完整的缺點，并使得協(xié)議識別所需時間大大降低。
關鍵詞： 協(xié)議識別； 模式匹配； KMP算法； 隱式馬爾科夫模型
中圖分類號： TN915?34； TP393 文獻標識碼： A 文章編號： 1004?373X（2014）09?0001?03
在日益激烈的電子對抗中，從偵察截獲的通信比特流序列中進一步識別未知通信協(xié)議是一個重要課題。短波是惟一不受網絡樞鈕和有源中繼體制約的遠程通信手段，一旦發(fā)生戰(zhàn)爭或災害，各種通信網絡都可能受到破壞，衛(wèi)星也可能受到攻擊，在這種情況下，無論哪種通信方式，其抗毀能力和自主通信能力與短波無可相比[1]。PACTOR由于其為短波優(yōu)化了的協(xié)議，可以在惡劣的短波段傳播環(huán)境中提供更快的傳送速度，并且可以方便地使用擴展的ASCII碼，是短波段數據傳送較流行的一種方式[2]。因此，從比特流中快速、準確識別PACTOR協(xié)議具有非常重要的意義。目前國內外對短波電臺協(xié)議的識別主要集中在信號層面上，尚無針對比特流的短波電臺協(xié)議識別方法。本文在大量分析現(xiàn)有的PACTOR協(xié)議的基礎上，提出了一種基于HMM的比特流識別技術。
1 隱式馬爾科夫模型
隱式馬爾科夫模型[3?6]（Hidden Markov models，HMM）是馬爾科夫鏈的一種，它的狀態(tài)不能直接觀察到，但能通過觀測向量序列觀察到，每個觀測向量都是通過某些概率密度分布表示為各種狀態(tài)，每一個觀測向量是由一個具有相應概率密度分布的狀態(tài)序列產生。所以，隱馬爾可夫模型是一個雙重隨機過程，具有一定狀態(tài)數的隱馬爾可夫鏈和顯示隨機函數集。其中，馬爾科夫鏈描述了狀態(tài)的轉移，一般用轉移概率矩陣描述；而一般隨機過程描述狀態(tài)和觀測序列間的關系，用混淆概率矩陣描述。一個完整的隱式馬爾科夫可被定義為一個五元組：[λ=（S，V，Π，A，B），]其定義如下：
有限狀態(tài)集合：[S={s1，s2，…，sN}。]
有限觀察符號集合：[V={v1，v2，…，vM}。]
初始狀態(tài)的概率分布：[Π={πi}，i∈S。]
狀態(tài)轉移概率矩陣：[AN×N={aij}，i，j∈S。]
觀察符號發(fā)射概率分布：[BN×M={bik}，][i∈S，k∈V。]
2 基于HMM的PACTOR協(xié)議比特流識別技術
2.1 PACTOR協(xié)議數據包格式分析
對于一個完整的PACTOR數據包，根據PACTOR協(xié)議[7]的數據單元格式，其最開始的8個比特位是頭字節(jié)，它的值是固定的01010101（0x55）。如果在比特流中有8個比特位值為0x55，那么就代表該比特流中有可能存在使用PACTOR協(xié)議的數據包。同時，PACTOR數據包中第74～76（波特率為100）或170～172（波特率為200）比特位被定義為data type，其作用是標識數據包中DATA的類型。
綜上，可知該字段指定中的內容是可以預期的，因此可以優(yōu)先考慮采用模式匹配算法中的快速模式匹配算法（Knuth?Morris?Pratt Algorithm，KMP）[8?9]，對數據包中的比特流進行預處理。
2.2 數據預處理
根據PACTOR協(xié)議數據包的格式特征，KMP算法首先對源比特流文件進行一次掃描，得到了在原文件中靜態(tài)特征Header出現(xiàn)的位置。并根據這些位置對原比特流進行切割，最終得到多個以0x55開頭的子比特流。
接著，讀取各個子比特流中在位置Status byte字段的Data type上出現(xiàn)的3位比特值。由于該位置的值已由PACTOR幀格式定義，所以為了簡化HMM模型，按照表1所示規(guī)則對各子比特流進行量化。通過特征位的量化值，得到了符合隱式馬爾科夫模型的觀察符號序列。
表1 Data type量化值規(guī)則對照表
[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]。
有限狀態(tài)集合中具有2個元素：0（若該序列采取PACTOR協(xié)議）、1（若該序列未采取PACTOR協(xié)議）；有限觀察符號集合中具有4個元素，具體定義如下所示：
[si=1，若該序列采取PACTOR協(xié)議0，若該序列未采取PACTOR協(xié)議]
[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狀態(tài)、4符號的HMM模型，并采用Visual C++ 6.0編程實現(xiàn)，其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數據包作為訓練數據，另一部分作為測試數據，同時將部分其他協(xié)議數據包作為混淆數據。此外，為了驗證本算法不僅對完整數據包有效，也對抓取到的非完整數據包有效，采取將部分數據包內的數據進行刪減的方法。通過調整混淆比，分別在完整數據包和非完整數據包下進行了7組方案測試。同時，為了避免訓練集對實驗結果帶來影響，每組均選取同等數量的訓練數據和測試數據。測試結果如圖2所示。 圖1 基于HMM的協(xié)議測試主界面 圖2 基于HMM的PACTOR協(xié)議識別技術測試結果 由圖2可以看出，完整數據包情況下，PACTOR數據包的識別率均在80%以上，在非完整數據包情況下，PACTOR協(xié)議的識別率較完整數據包情況的測試結果有所下降，但也達到了70%以上。隨著測試數據樣本中PACTOR協(xié)議所占比重的減小，識別率均略有下降。而且在PACTOR協(xié)議所占比率減小的情況下，測試比率有所波動，這是由于混淆數據中所存在的部分冗余數據影響到預處理時快速模式匹配算法所導致的。同時，在實驗中發(fā)現(xiàn)，它僅需掃描一次源比特流就能得到建立HMM所需的數據，并且不需要記錄特定模式串在源比特流中的位置信息，這就減少了對數據庫的訪問和操作，進而降低了I/O操作的時間消耗。因此該技術是可行并且有效的。 4 結 語 比特流識別未知短波電臺協(xié)議是一個全新的課題。本文提出的基于HMM的比特流協(xié)議識別技術，首先采用KMP對比特流進行處理分類，接著定義了data type數據位量化規(guī)則，從而初始化了HMM模型中各個參數，并將隨機采集到的數據一部分應用到HMM模型的訓練中，隨之將訓練后的模型應用到具體的測試過程中。實驗結果表明，該技術不僅能夠從比特級實現(xiàn)對協(xié)議的分析和識別，而且解決了傳統(tǒng)協(xié)議識別算法面對不完整數據包時遇到的不同瓶頸與難題。因此，具有一定的實用價值。但該技術也有不足，在預處理數據時僅僅采用靜態(tài)的模式識別算法并不可靠，下一步的研究工作可以考慮采用數據挖掘的方法對比特流進行處理，以改進該技術。 參考文獻 [1] 聶東舉，葉進，閆坤，等.基于SVM算法的短波通信協(xié)議識別技術[J].系統(tǒng)工程與電子技術，2013，35（5）：1307?1311. [2] 程磊.短波自適應調制信號的識別技術研究與實現(xiàn)[D].鄭州：信息工程大學，2006. [3] 朱樹永.協(xié)議識別技術研究[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] 王楊德.面向比特流的協(xié)議幀頭結構分析研究[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狀態(tài)、4符號的HMM模型，并采用Visual C++ 6.0編程實現(xiàn)，其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數據包作為訓練數據，另一部分作為測試數據，同時將部分其他協(xié)議數據包作為混淆數據。此外，為了驗證本算法不僅對完整數據包有效，也對抓取到的非完整數據包有效，采取將部分數據包內的數據進行刪減的方法。通過調整混淆比，分別在完整數據包和非完整數據包下進行了7組方案測試。同時，為了避免訓練集對實驗結果帶來影響，每組均選取同等數量的訓練數據和測試數據。測試結果如圖2所示。 圖1 基于HMM的協(xié)議測試主界面 圖2 基于HMM的PACTOR協(xié)議識別技術測試結果 由圖2可以看出，完整數據包情況下，PACTOR數據包的識別率均在80%以上，在非完整數據包情況下，PACTOR協(xié)議的識別率較完整數據包情況的測試結果有所下降，但也達到了70%以上。隨著測試數據樣本中PACTOR協(xié)議所占比重的減小，識別率均略有下降。而且在PACTOR協(xié)議所占比率減小的情況下，測試比率有所波動，這是由于混淆數據中所存在的部分冗余數據影響到預處理時快速模式匹配算法所導致的。同時，在實驗中發(fā)現(xiàn)，它僅需掃描一次源比特流就能得到建立HMM所需的數據，并且不需要記錄特定模式串在源比特流中的位置信息，這就減少了對數據庫的訪問和操作，進而降低了I/O操作的時間消耗。因此該技術是可行并且有效的。 4 結 語 比特流識別未知短波電臺協(xié)議是一個全新的課題。本文提出的基于HMM的比特流協(xié)議識別技術，首先采用KMP對比特流進行處理分類，接著定義了data type數據位量化規(guī)則，從而初始化了HMM模型中各個參數，并將隨機采集到的數據一部分應用到HMM模型的訓練中，隨之將訓練后的模型應用到具體的測試過程中。實驗結果表明，該技術不僅能夠從比特級實現(xiàn)對協(xié)議的分析和識別，而且解決了傳統(tǒng)協(xié)議識別算法面對不完整數據包時遇到的不同瓶頸與難題。因此，具有一定的實用價值。但該技術也有不足，在預處理數據時僅僅采用靜態(tài)的模式識別算法并不可靠，下一步的研究工作可以考慮采用數據挖掘的方法對比特流進行處理，以改進該技術。 參考文獻 [1] 聶東舉，葉進，閆坤，等.基于SVM算法的短波通信協(xié)議識別技術[J].系統(tǒng)工程與電子技術，2013，35（5）：1307?1311. [2] 程磊.短波自適應調制信號的識別技術研究與實現(xiàn)[D].鄭州：信息工程大學，2006. [3] 朱樹永.協(xié)議識別技術研究[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] 王楊德.面向比特流的協(xié)議幀頭結構分析研究[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狀態(tài)、4符號的HMM模型，并采用Visual C++ 6.0編程實現(xiàn)，其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數據包作為訓練數據，另一部分作為測試數據，同時將部分其他協(xié)議數據包作為混淆數據。此外，為了驗證本算法不僅對完整數據包有效，也對抓取到的非完整數據包有效，采取將部分數據包內的數據進行刪減的方法。通過調整混淆比，分別在完整數據包和非完整數據包下進行了7組方案測試。同時，為了避免訓練集對實驗結果帶來影響，每組均選取同等數量的訓練數據和測試數據。測試結果如圖2所示。 圖1 基于HMM的協(xié)議測試主界面 圖2 基于HMM的PACTOR協(xié)議識別技術測試結果 由圖2可以看出，完整數據包情況下，PACTOR數據包的識別率均在80%以上，在非完整數據包情況下，PACTOR協(xié)議的識別率較完整數據包情況的測試結果有所下降，但也達到了70%以上。隨著測試數據樣本中PACTOR協(xié)議所占比重的減小，識別率均略有下降。而且在PACTOR協(xié)議所占比率減小的情況下，測試比率有所波動，這是由于混淆數據中所存在的部分冗余數據影響到預處理時快速模式匹配算法所導致的。同時，在實驗中發(fā)現(xiàn)，它僅需掃描一次源比特流就能得到建立HMM所需的數據，并且不需要記錄特定模式串在源比特流中的位置信息，這就減少了對數據庫的訪問和操作，進而降低了I/O操作的時間消耗。因此該技術是可行并且有效的。 4 結 語 比特流識別未知短波電臺協(xié)議是一個全新的課題。本文提出的基于HMM的比特流協(xié)議識別技術，首先采用KMP對比特流進行處理分類，接著定義了data type數據位量化規(guī)則，從而初始化了HMM模型中各個參數，并將隨機采集到的數據一部分應用到HMM模型的訓練中，隨之將訓練后的模型應用到具體的測試過程中。實驗結果表明，該技術不僅能夠從比特級實現(xiàn)對協(xié)議的分析和識別，而且解決了傳統(tǒng)協(xié)議識別算法面對不完整數據包時遇到的不同瓶頸與難題。因此，具有一定的實用價值。但該技術也有不足，在預處理數據時僅僅采用靜態(tài)的模式識別算法并不可靠，下一步的研究工作可以考慮采用數據挖掘的方法對比特流進行處理，以改進該技術。 參考文獻 [1] 聶東舉，葉進，閆坤，等.基于SVM算法的短波通信協(xié)議識別技術[J].系統(tǒng)工程與電子技術，2013，35（5）：1307?1311. [2] 程磊.短波自適應調制信號的識別技術研究與實現(xiàn)[D].鄭州：信息工程大學，2006. [3] 朱樹永.協(xié)議識別技術研究[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] 王楊德.面向比特流的協(xié)議幀頭結構分析研究[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.
