陳遠(yuǎn)武

東莞市電子科技學(xué)校

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

陳遠(yuǎn)武

東莞市電子科技學(xué)校

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

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

1 前言

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

2 L＊學(xué)習(xí)算法

2.1 算法背景

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

2.2 算法過程

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

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

3 修正學(xué)習(xí)算法

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

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

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

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

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

3.3 證明正確性和分析復(fù)雜度

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

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

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

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

4 結(jié)語

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

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

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