陳遠武

東莞市電子科技學校

改進的安全協(xié)議自適應(yīng)分析算法研究

陳遠武

東莞市電子科技學校

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

安全協(xié)議；自適應(yīng)；分析算法

1 前言

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

2 L＊學習算法

2.1 算法背景

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

2.2 算法過程

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

（1）初始化。對S和E進行初始化，使其成為空串λ，并以λ和字母表A的各個字母進行成員資格詢問，對初始化觀察表（S，E，T）進行構(gòu)建。（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。借助成員資格詢問實現(xiàn)T到（S∪SA）的擴展。（3）假定（S，E，T）完備且一致，對狀態(tài)機M進行構(gòu)建，構(gòu)成等價詢問。如果教師將一個反例ce返回，在S中對該反倒和全部前綴進行添加，并應(yīng)用成員資格對T到（S∪SA）的擴展進行詢問。再回歸到步驟（2），校驗其一致性和完備性，達標后，做步驟（3）的等價詢問，直至回歸到M=L（U）停止，輸出M[1]。

3 修正學習算法

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

3.1 缺乏經(jīng)驗教師

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

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

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

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

定理1能夠終止修正學習算法，并實現(xiàn)最小的符號自動機，它能夠?qū)Α?和∠2進行有效區(qū)分。

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

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

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

4 結(jié)語

安全協(xié)議能夠保障網(wǎng)絡(luò)安全。學習算法在安全協(xié)議自適應(yīng)分析框架中尤為重要。改進的安全協(xié)議自適應(yīng)算法能夠?qū)Σ糠纸處熃?jīng)驗缺乏問題進行有效解決，并實現(xiàn)字符集擴展。修正學習算法能夠提高安全協(xié)議自適應(yīng)模型檢測效率，控制分析和設(shè)計成本，不斷提高自適應(yīng)防御能力。

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

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