基于自動(dòng)機(jī)的用戶(hù)名合法性檢測(cè)方法

劉帆， 趙亞慧,， 崔榮一

( 1.延邊大學(xué) 融合學(xué)院, 吉林 延吉 133002； 2.延邊大學(xué) 工學(xué)院, 吉林 延吉 133002 )

0 引言

用戶(hù)名合法性檢測(cè)問(wèn)題的本質(zhì)是字符串匹配問(wèn)題.與傳統(tǒng)的字符串匹配不同，合法性檢測(cè)問(wèn)題只需保證字符類(lèi)別匹配成功即可.合法的用戶(hù)名字符串需同時(shí)含有數(shù)字、特殊字符、大寫(xiě)字母且其長(zhǎng)度需大于8位.傳統(tǒng)的字符匹配算法主要有暴力匹配(BF)算法[1]、Rabin - Karp(RK)算法[2]、字符串查找(KMP)算法[3]以及正則表達(dá)式[4].其中： BF算法雖然簡(jiǎn)單，但耗時(shí)較大； RK算法是基于哈希函數(shù)的一種對(duì)BF算法改進(jìn)的算法，在正常情況下該算法的效率雖然優(yōu)于BF算法，但當(dāng)哈希產(chǎn)生沖突時(shí)該算法的效率仍然較低； KMP算法是一種采用消除主串指針回溯的方法對(duì)BF算法進(jìn)行優(yōu)化的算法，該算法雖然能夠彌補(bǔ)BF算法在主針回溯后需重新開(kāi)始進(jìn)行比較的缺點(diǎn)，但在重復(fù)率很高的文本中其效率低于BF算法；正則表達(dá)式與上述方法相比，雖然時(shí)間效率有所提高，但存在空間復(fù)雜度高和易出錯(cuò)等缺點(diǎn)[5].近年來(lái)，一些研究者基于上述方法又提出了BM算法[6]和Sunday算法[7]，這兩種方法雖大幅提高了字符串匹配的效率，但二者過(guò)于依賴(lài)于輔助數(shù)據(jù)結(jié)構(gòu)，且預(yù)處理時(shí)間過(guò)長(zhǎng).

1956年， Moore等首次提出了有限狀態(tài)自動(dòng)機(jī)的概念[8]，并在后續(xù)的研究中針對(duì)字符串匹配問(wèn)題提出了有限狀態(tài)自動(dòng)機(jī)算法—Aho - Corasick(AC)算法[9].該算法與上述傳統(tǒng)算法相比，只需掃描一遍字符串即可，且其時(shí)間復(fù)雜度與模式串的規(guī)模無(wú)關(guān)，因此該算法受到學(xué)者們的關(guān)注.目前利用該方法雖然可以檢測(cè)用戶(hù)名字符串中包含的類(lèi)別，但無(wú)法檢測(cè)用戶(hù)名長(zhǎng)度，因此其應(yīng)用性受到一定限制.為此，本文提出了一種新有限狀態(tài)自動(dòng)機(jī)，并通過(guò)分析驗(yàn)證了該自動(dòng)機(jī)的有效性.

1 有限狀態(tài)自動(dòng)機(jī)

傳統(tǒng)的有限狀態(tài)自動(dòng)機(jī)由一個(gè)五元組組成[10]：

M=(Q,Σ,δ,q0,F).

(1)

其中：Q是包含自動(dòng)機(jī)中所有狀態(tài)的非空集合；Σ是字母表，自動(dòng)機(jī)接收的任意字符均為該集合元素；δ是狀態(tài)轉(zhuǎn)移函數(shù)，其中δ：Q×Σ→Q, 對(duì)?(q,a)∈Q×Σ, ?p∈Q有δ(q,a)=p，它表示自動(dòng)機(jī)M在狀態(tài)q時(shí)讀入字符a之后，狀態(tài)q隨即轉(zhuǎn)向狀態(tài)p；q0為M的初始狀態(tài)，q0∈Q；F為終止?fàn)顟B(tài)集合，F(xiàn)?Q，?q∈F，q稱(chēng)為M的一個(gè)終態(tài).

對(duì)于?x∈Σ*, 若有δ(q0,x)∈F， 則稱(chēng)x被M所接受；對(duì)于?x∈Σ*， 若有δ(q0,x)?F, 則稱(chēng)x不被M所接受[11].所有可以被M接受的x的集合稱(chēng)為M可接受的語(yǔ)言,表示為：

L(M)={x|x∈Σ*且δ(q0,x)∈F}.

(2)

假設(shè)Q={q0,q1,q2},Σ={0,1},F={q2}，δ(q0,0)=q1,δ(q0,1)=q0,δ(q1,0)=q2,δ(q1,1)=q0,δ(q2,0)=q2，δ(q2,1)=q0, 則此時(shí)的自動(dòng)機(jī)M如圖1所示，其狀態(tài)轉(zhuǎn)移函數(shù)如表1所示.在圖1中，單圓圈代表自動(dòng)機(jī)中的中間狀態(tài)，雙圓圈代表終止?fàn)顟B(tài)，標(biāo)有字符的有向箭頭代表轉(zhuǎn)移函數(shù)，箭頭S所指向的單圓圈代表初始狀態(tài).

圖1 M的狀態(tài)轉(zhuǎn)移圖

表1 M的狀態(tài)轉(zhuǎn)移函數(shù)

2 自動(dòng)機(jī)模型的構(gòu)建

為了便于檢測(cè)用戶(hù)名的合法性，本文設(shè)計(jì)了一種可計(jì)數(shù)的有限狀態(tài)自動(dòng)機(jī)，其檢測(cè)流程如下：①用戶(hù)提交需檢測(cè)的用戶(hù)名.②系統(tǒng)利用同態(tài)映射對(duì)用戶(hù)名進(jìn)行字符分類(lèi)(屬于同一類(lèi)的字符被映射為同一個(gè)字符，同時(shí)用戶(hù)名字符串映射為對(duì)應(yīng)類(lèi)別字符串)；若某類(lèi)別字符串可以被該自動(dòng)機(jī)正確識(shí)別，則對(duì)應(yīng)的用戶(hù)名字符串為合法，否則為不合法.由于自動(dòng)機(jī)每次只能輸出一個(gè)字符，不能直接輸出用戶(hù)名是否合法，因此本文設(shè)計(jì)了一個(gè)解碼函數(shù).該解碼函數(shù)可根據(jù)自動(dòng)機(jī)最后的狀態(tài)輸出用戶(hù)名不合法的原因.用戶(hù)名映射、自動(dòng)機(jī)識(shí)別以及狀態(tài)解碼的過(guò)程如圖2所示.

圖2 用戶(hù)名映射、自動(dòng)機(jī)識(shí)別和狀態(tài)解碼的過(guò)程

2.1 映射函數(shù)和解碼函數(shù)

用戶(hù)名字符分類(lèi)是一個(gè)同態(tài)映射過(guò)程.設(shè)D是初始用戶(hù)名字符串，E是分類(lèi)字符串，f:D→E為映射，對(duì)于?d1,d2∈D有f(d1d2)=f(d1)f(d2), 則稱(chēng)f是D到E的同態(tài)映射.本文將用戶(hù)名字符分類(lèi)的映射函數(shù)定義為：

(3)

其中x是原始用戶(hù)名字符串中的字符.

輸出不合法原因的解碼函數(shù)是一個(gè)映射過(guò)程，即當(dāng)?a∈A,?b∈B, 且有h(a)=b, 稱(chēng)h是A到B的映射.本文將解碼函數(shù)定義為：

(4)

其中，x是指自動(dòng)機(jī)在接收一個(gè)字符串后跳轉(zhuǎn)到的最終狀態(tài).

2.2 自動(dòng)機(jī)模型的構(gòu)建

本文建立的自動(dòng)機(jī)模型G由一個(gè)六元組組成：

G=(Q,Σ,δ,q0,F,n).

(5)

其中：Q、Σ、δ、q0、F與有限狀態(tài)自動(dòng)機(jī)的定義一致；n為計(jì)數(shù)器(自動(dòng)機(jī)每接受1個(gè)字符時(shí)，n減1).G的狀態(tài)轉(zhuǎn)移函數(shù)如表2所示.本文算法的具體步驟如下：

輸入：字符串s

輸出：用戶(hù)名是否合法

Step 1 對(duì)字符串s進(jìn)行映射，得到映射串s′;

Step 2 根據(jù)狀態(tài)轉(zhuǎn)移函數(shù)表初始化狀態(tài)轉(zhuǎn)移字典trans， 同時(shí)將n初始化為8;

Step 3 設(shè)初始狀態(tài)為q0， 即設(shè)待匹配字符串的首位為i=0;

表2 G的狀態(tài)轉(zhuǎn)移函數(shù)

Step 4 讀完字符串時(shí)，若n≤0時(shí)則算法結(jié)束，否則跳轉(zhuǎn)到Step 5;

Step 5 依據(jù)最終狀態(tài)進(jìn)行解碼并輸出字符中不合法的原因，算法結(jié)束.

該算法中，輸入是需驗(yàn)證合法性的原始用戶(hù)名s； 輸出是該用戶(hù)名s是否合法.若合法，不輸出錯(cuò)誤；若不合法，輸出不合法并給出原因.映射串s′是輸入字符串s經(jīng)函數(shù)f(x)同態(tài)映射得到的分類(lèi)字符串，字典trans是依據(jù)表2進(jìn)行初始化的狀態(tài)轉(zhuǎn)移函數(shù)，n賦值為8表示合法用戶(hù)名至少是9位字符；end表示自動(dòng)機(jī)為終態(tài)，end∈F.

3 算法分析

3.1 算法有效性證明

對(duì)于任意的一個(gè)輸入字符串a(chǎn)1a2…an， 根據(jù)文獻(xiàn)[10]中的定理1可知：對(duì)于?q∈Q,ω∈Σ*,a∈Σ, 有δ(q,wa)=δ(δ(q,w),a).由此可得：

δ(q0,a1a2…an)=δ(δ(q0,a1a2…an -1),an)=δ(δ(…δ(q0,a1)…),an).

(6)

再根據(jù)表2可得：

δ(q0,a1a2…an)=δ(δ(q0,a1a2…an -1),an)=δ(δ(…δ(q0,a1)…),an)=end.

(7)

依據(jù)計(jì)數(shù)器的定義，此時(shí)接收到的字符串a(chǎn)1a2…an的值為：

n=8-|a1a2…an|.

(8)

公式(8)中的|a1a2…an|表示字符串a(chǎn)1a2…an的長(zhǎng)度.當(dāng)式(8)中求得的n大于0時(shí)，自動(dòng)機(jī)在end(終態(tài))處跳轉(zhuǎn)至下一狀態(tài)，即表示用戶(hù)名不合法.因此，只有當(dāng)自動(dòng)機(jī)最后到達(dá)的狀態(tài)是終態(tài)時(shí)，該用戶(hù)名才是合法的，否則為不合法.根據(jù)本文算法構(gòu)造的用于檢驗(yàn)用戶(hù)名合法性的可計(jì)數(shù)自動(dòng)機(jī)如圖3所示.

圖3 可計(jì)數(shù)自動(dòng)機(jī)的狀態(tài)轉(zhuǎn)移圖

本文以輸入字符串s和t為例驗(yàn)證本文構(gòu)造的自動(dòng)機(jī)的有效性，其中假設(shè)s為‘a(chǎn)bA*’和t為‘2B&’， 映射串s1(‘a(chǎn)aAT’)和t1(‘1AT’)由s和t經(jīng)映射函數(shù)f(x)得到.圖4和圖5分別是s1和t1的狀態(tài)轉(zhuǎn)移圖，圖中的虛線為字符串在自動(dòng)機(jī)中的轉(zhuǎn)移路線.由圖可知，s1和t1經(jīng)自動(dòng)機(jī)轉(zhuǎn)移到的最終狀態(tài)分別是q4和q8.由于q4和q8均不是終態(tài)，因此這兩個(gè)字符串是不合法的.此時(shí)解碼函數(shù)h(x)輸出的是：“該用戶(hù)名缺少數(shù)字，不合法”和“該用戶(hù)名長(zhǎng)度不夠，不合法”.上述實(shí)例證明本文提出的算法可以有效驗(yàn)證用戶(hù)名的合法性，且具有簡(jiǎn)單、穩(wěn)定的優(yōu)點(diǎn).

圖4 s1的狀態(tài)轉(zhuǎn)移圖

圖5 t1的狀態(tài)轉(zhuǎn)移圖

3.2 算法復(fù)雜度分析

表3為傳統(tǒng)有限自動(dòng)機(jī)模型(DFA)與本文所提模型(N - DFA)的復(fù)雜度，其中n為需要滿(mǎn)足的條件個(gè)數(shù)，m為用戶(hù)名長(zhǎng)度.由表3可知，本文所提模型在時(shí)間復(fù)雜度和空間復(fù)雜度方面均優(yōu)于傳統(tǒng)模型.

表3 不同模型的復(fù)雜度

4 結(jié)論

研究表明，本文設(shè)計(jì)的模型可實(shí)現(xiàn)有限狀態(tài)自動(dòng)機(jī)的計(jì)數(shù)和設(shè)置輸入字符串的長(zhǎng)度，且具有檢測(cè)效率高、性能穩(wěn)定等優(yōu)點(diǎn)，因此本文方法可用于用戶(hù)名的合法性檢驗(yàn).本文算法未能實(shí)現(xiàn)計(jì)數(shù)器和終態(tài)的完全分離，擬在今后的研究中通過(guò)調(diào)整計(jì)數(shù)器和終態(tài)的關(guān)系使二者相互獨(dú)立，以使本文算法達(dá)到更好的檢測(cè)效果.