改進的安全協議自適應分析算法研究

陳遠武

東莞市電子科技學校

改進的安全協議自適應分析算法研究

陳遠武

東莞市電子科技學校

修正學習算法La?屬于改進的安全協議自適應分析算法，它能夠避免教師經驗不足，并實現字符集擴展。立足于正確性和復雜度方面，對修正學習算法進行分析和證明，其為安全協議自適應模型檢測提供助力，實現成本控制，有效緩解狀態空間爆炸，使協議對環境和各種攻擊方法極具防御性。

安全協議；自適應；分析算法

1 前言

安全協議的形式化分析方法包括形式邏輯方法、模型檢測方法和定理證明三類。修正學習算法La*屬于改進的安全協議自適應分析算法，從兩個方面對La*學習算法進行修正。一方面可以將大字符集作為字母表，對符號自動機進行應用，并對觀察表進行擴展，使之成為符號觀察表；與此同時，對教師進行修正。其能夠使安全協議自適應模型達到良好的監測效果，實現成本控制，對狀態空間爆炸進行有效緩解，實現協議對環境和各攻擊方法的自適應防御。

2 L＊學習算法

2.1 算法背景

從單個集合的成員和非成員中對未知正則語言集合進行識別。最小勝任教師教師給定正則語言集合，繼而接收集合成員的資格詢問，對假定集合進行判定，看其是否與未知集合等同，如果不同則給出反例。正確集合和假設集合的對稱差即為反例。L*學習算法可以JFLAP的DFA工具為基礎實現。多項式時間內，L*算法依從于最小勝任教師，對正則語言進行學習。假定背景為比較隨機，可應用隨機采樣語言機對假設測試能力進行替代。

2.2 算法過程

學習者L*對觀察表（S，E，T）進行維護，S代表前綴封閉集合，E代表后綴封閉集合，其分別是狀態集合和區分狀態的集合。T是一個函數，在中的元素字符串進行映射。假定se∈U，則T（s,e）=1；反之，T（s,e）=0。具體流程如下：

（1）初始化。對S和E進行初始化，使其成為空串λ，并以λ和字母表A的各個字母進行成員資格詢問，對初始化觀察表（S，E，T）進行構建。（2）檢驗完備性和一致性：假定（S，E，T）不具備一致性，需找出S中的s1和s2，a∈A，e∈E，使row（s1）和row（s2）相同，且T（s1ae）≠T（s2ae），在E中對ae進行添加，詢問成員資格將T擴展為（S∪SA）。如果（S，E，T）不完備，需分別找到s1∈S、s2∈S使對于任意a∈A，row（s1a）和row（s）不相同，在S中添加s1a。借助成員資格詢問實現T到（S∪SA）的擴展。（3）假定（S，E，T）完備且一致，對狀態機M進行構建，構成等價詢問。如果教師將一個反例ce返回，在S中對該反倒和全部前綴進行添加，并應用成員資格對T到（S∪SA）的擴展進行詢問。再回歸到步驟（2），校驗其一致性和完備性，達標后，做步驟（3）的等價詢問，直至回歸到M=L（U）停止，輸出M[1]。

3 修正學習算法

安全協議呈現發送者、接受者、加密、認證等諸多狀態，很多應用背景下，教師或許不能對部分成員的資格詢問做出解答。故而借助修正學習算法，對符號自動機進行應用。教師的定位是經驗不足的教師，進行大字符集學習。

3.1 缺乏經驗教師

受學習對象的不完全具體性或不可觀察性限制，這些詢問有可能得不到具體回答。最小勝任教師不能夠滿足這種實際需求，對缺乏經驗教師進行引入，并向其學習，以獲得所需知識。缺乏經驗的教師有權對兩個不相交的語言集進行詢問，并對成員資格詢問和包含關系詢問進行回答。

對缺乏經驗教師進行設定，通過資格詢問和等價詢問，對可行的符號自動機進行獲取。具體而言，學習者的任務是分別對∠1的超集和∠2的符號自動機進行接受和拒絕。語言集分別為∠1和，呈不相交狀態。具體情況有三種：（1）假定∠1和∠2都是正則語言，會有極具可行性的DFA。例如，可對∠1進行精確接受。（2）假定∠1和∠2都能夠對上下文無關語言進行確定，該判定性問題能否被判定，無從得知。（2）假定∠1和∠2都是非確定性上下文無關語言，該判定性問題不具備可判定性。借助簡單的歸類對上下文無關語言是否為正則語言進行判定。

該算法能夠在大字符集場景中進行應用，經驗不足教師無法回答相關問題，需改進之前算法。它屬于主動學習算法，能夠對正則語言進行識別。假定教師能夠對成員資格詢問和包含關系詢問進行回答。通過候選生成器對候選生成步驟進行操作，并對擴展的L*算法和符號學習算法進行運用，生成一系列候選自動機，其目標是3DFA C。繼而進行完備性校驗。完成操作后，對最小化符號自動機進行計算。最后校驗其可行性。應用修正學習算法對最小化符號自動機進行計算，并通過集合包含關系詢問，對∠1和∠2的區分度進行驗證。如果驗證成功，即對正確結果進行輸入。反之，在第一步中輸入反例，不斷循環，直到輸出正確結果。

3.3 證明正確性和分析復雜度

定理1能夠終止修正學習算法，并實現最小的符號自動機，它能夠對∠1和∠2進行有效區分。

引理1將Bi假定為Li的最小化符號自動機，能夠對正則語言進行接受i=1,2。最小化的對∠1中所有字符串進行接受，并對所有字符串的C(3DFA)大小不超過|B1|×|B2|進行拒絕。

定理2與引理1的假設條件相同，修正學習算法對∠1和∠2的最小化符號自動機所需成員資格詢問數目進行區分[2]。

證明將C假定為最小化的3DFA，能夠分別對∠1和∠2中的所有字符串接受和拒絕。候選生成器所需要的成員資格詢問數目最多為，錯誤假設背景下C（3DFA）的大小不超過經過一系列證明，修正學習算法需要2次包含關系詢問對完備性和可行性進行檢驗。

4 結語

安全協議能夠保障網絡安全。學習算法在安全協議自適應分析框架中尤為重要。改進的安全協議自適應算法能夠對部分教師經驗缺乏問題進行有效解決，并實現字符集擴展。修正學習算法能夠提高安全協議自適應模型檢測效率，控制分析和設計成本，不斷提高自適應防御能力。

[1]楊京,范丹,等.改進的安全協議自適應分析算法[J].通信學報,2015,(S1):266-276.

[2]王虎強，李東.一種基于自適應能力改進的AFSA算法研究[J].信息通信，2015,(10):47-49