摘要：如果給你一大堆用戶輸入，里面有大量的中文地名，像是北京成都東莞，不幸的是，其中也混有一些羅馬地名，比如。主教的自我修養(yǎng)看臉北京與成都之間相距再遠(yuǎn)，也可以用歐式距離輕松度量。

給你的入侵檢測(cè)系統(tǒng)提供一個(gè)靈感。

如果給你一大堆用戶輸入，里面有大量的中文地名，像是“北京”、“成都”、“東莞”，不幸的是，其中也混有一些羅馬地名，比如 “Singapore”、“New York”、“Tokyo”。你的任務(wù)是將它們分開(kāi)，你會(huì)如何去做？

當(dāng)然，有很多方法可以輕易做到。

如果是一堆 “good”、“fine”、“not bad”、“amazing”、"nice" 的簡(jiǎn)短反饋里混有 “Fallout 4 is the epitemy of everything wrong with modern gaming, it has a total of 2 compelling quests, its gameplay is worse then the rest, and to top it off they added microtransactions to it. it is the worst of the fallout series.” 這樣的長(zhǎng)篇抱怨呢？

你可能會(huì)想，這不更簡(jiǎn)單了嘛，檢測(cè)字符串長(zhǎng)度甚至標(biāo)點(diǎn)符號(hào)數(shù)目就行呀。

如果是一堆 “12345678”、“5201314”、“password”里混有“password" and (select count(*) from data)>0 and "a"="a”、“>"">” 呢？

或許你已經(jīng)不耐煩了：這點(diǎn)安全素養(yǎng)還是有的！檢測(cè)關(guān)鍵字和特殊符號(hào)呀！

你已經(jīng)不打算讓我再“如果”下去了：沒(méi)有什么是一段正則表達(dá)式搞不定的，如果有，那就該再學(xué)一次。

好，但是現(xiàn)在，我們需要的是，用同一個(gè)模型實(shí)現(xiàn)上述所有場(chǎng)景——當(dāng)字符串有長(zhǎng)有短，它要將長(zhǎng)度異常的字符串分開(kāi)。當(dāng)有常規(guī)字符串和包含特殊符號(hào)的字符串，它能把特殊的那些拎出來(lái)。當(dāng)字符串混有不同的語(yǔ)言，它能進(jìn)行“凈化”。甚至，還有各種不在意料之中的情形。

這段代碼就像是在宗教戰(zhàn)爭(zhēng)中審判異端，無(wú)論是中出了一個(gè)叛徒還是干脆分裂成了兩類，它總是能根據(jù)字符串的長(zhǎng)相，把少數(shù)派給抓出來(lái)。

如果你恰好做過(guò)一些事，例如探索深度學(xué)習(xí)對(duì)網(wǎng)絡(luò)安全的應(yīng)用，相信你看著數(shù)據(jù)集，能很快想到這個(gè)“異端審判器”的實(shí)用價(jià)值。

讓我們默契地眨眨眼。在后文里，我們會(huì)實(shí)現(xiàn)這樣一個(gè)玩具。

北京與成都之間相距再遠(yuǎn)，也可以用歐式距離輕松度量。但 “Beijing” 與 “Chengdu” 之間的距離呢？

我們需要看臉，根據(jù)字符串“外貌”的特征，去定義和量化這樣一種差異。

不難發(fā)現(xiàn)，字符串之間的距離至少應(yīng)該包括如下組分：

字符串長(zhǎng)度差異（如 cat 與miaomiaomiaomiaomiao）

字符集差異（如 123 與 abc）

字符序列差異（如 上海自來(lái)水 與 水來(lái)自海上）

這有什么好說(shuō)的……長(zhǎng)度為5的字符串顯然比長(zhǎng)度為3的字符串多出一個(gè)2……

在此略過(guò)。

def strLengthDiffer(str1, str2):
    return abs(len(str1) - len(str2))

字符集的差異是為了刻畫不同字符串在字符選擇上的差異，我們應(yīng)該對(duì)差異較大的字符串——特別是出現(xiàn)了不同類別的字符時(shí)——進(jìn)行距離上的懲罰。

為了實(shí)現(xiàn)這個(gè)目標(biāo)，首先要定義字符間的距離。這里，我們把相同字符間距離定義為 0, 同類字符（如a與b）間距離定義為 1，不同類字符間距離定義為 10。

字符分類可以為小寫字母、大寫字母、數(shù)字和其他，當(dāng)然讀者也可以根據(jù)自己的實(shí)際用途進(jìn)行分類，把系統(tǒng)需要敏感識(shí)別的差異分為不同的兩類。

有了字符間距離，我們定義字符 A(1) 與字符集 B 的距離為該 A(1) 到 B 中每一個(gè)字符的距離的最小值。

在上述基礎(chǔ)上，我們進(jìn)一步定義字符集 A 到字符集 B 間的距離為：A 中每一個(gè)字符到 B 的距離的算術(shù)和。

顯然：

字符距離(a, b) = 字符距離(b, a)

字符到字符集距離(a, B) = 字符集到字符距離(B, a)

字符集間距離(A, B) = 字符集間距離(B, A)

由此，我們對(duì)字符集間距離完成了符合認(rèn)知的定義。

def charSetDiffer(s1, s2):
    # 由于筆者使用的代碼版本在這里有更復(fù)雜的邏輯，就不提供代碼細(xì)節(jié)了
    # 已經(jīng)講得這么明確了，寫寫看吧
    return s

對(duì)于開(kāi)發(fā)者而言，用戶輸入是 alert("test") 還是 aeelrstt""()，顯然有著完全不同的含義。后面這種意味不明的字符串根本不會(huì)讓人多看一眼，而前者如果被用戶執(zhí)行成功，那么他后續(xù)多半會(huì)再搞些別的破壞，非常邪惡。

這個(gè)故事告訴我們，字符序列的差異不容忽視。

在這里，我們使用 N-Gram 語(yǔ)言模型，借助 N=2 時(shí)的 Gram 數(shù)目來(lái)度量?jī)蓚€(gè)序列的差異。

如果你并不知道我在說(shuō)什么，那么具體而言是像這樣的計(jì)算：

假設(shè)我們有字符串 S1 與 S2。

將字符串 S1 每?jī)蓚€(gè)連續(xù)字符作為一個(gè)元素，構(gòu)成集合 G1，同理也有 G2。

字符串 S1 與 S2 之間的序列差異就是 G1 與 G2 中不同元素的數(shù)目。顯然，你可以通過(guò)他們的交集減去他們的并集取到該值。

def n_grams(a):
    z = (islice(a, i, None) for i in range(2))
    return list(zip(*z))

def groupDiffer(s1, s2):
    len1 = len(list(set(s1).intersection(set(s2))))
    len2 = len(list(set(s1).union(set(s2))))
    return abs((len2 - len1))

到現(xiàn)在為止，我們對(duì)兩個(gè)字符串間三個(gè)形式維度的差異都有了量化，接下來(lái)做的就是通過(guò)精妙絕倫的加權(quán)求和，算出那個(gè)令人拍案叫絕的字符串間距離。

在此，筆者使用的方法是——

def samplesDistance(str1, str2):
    a = strLengthDiffer(str1, str2)
    b = charSetDiffer(str1, str2)
    s1 = n_grams(str1)
    s2 = n_grams(str2)
    c = groupDiffer(s1, s2)
    d = a+b+c
    return d

是的！簡(jiǎn)單相加……

山不在高，有廟則有人送錦旗，算法不在復(fù)雜，有用就行。

你當(dāng)然可以根據(jù)自己的需要，去調(diào)節(jié)系統(tǒng)對(duì)于其中三個(gè)維度的不同敏感度，但筆者認(rèn)為字符集差異的值天然就比另外兩種差異的值要大，已經(jīng)符合我的需要，就不再調(diào)整啦。

有了字符串間的距離，進(jìn)一步，就有一個(gè)字符串到另一堆字符串的距離。我們定義如下：

字符串樣本與字符串集合的距離 = 該字符串樣本到字符串集合中每個(gè)字符串樣本的距離的算術(shù)平均值

即：

def sampleClassDistance(sample, class1):
    list_0 = []
    length = len(class1)
    for item in class1:
        list_0.append(samplesDistance(sample, item))
    return sum(list_0)/length

由上一節(jié)的一個(gè)字符串到一堆字符串的距離出發(fā)，我們可以得到一堆字符串到另一堆字符串的距離。它的定義形式很相似：

字符串集合間的距離 = 該字符串集合中的每一樣本到字符串集合的距離的算術(shù)平均值 = 該字符串集合中每一樣本到另一字符串中每一樣本的距離的算術(shù)平均值

即：

def classesDistance(class1, class2):
    list_0 = []
    class1 = flatten(class1)
    class2 = flatten(class2)
    m = len(class1)
    n = len(class2)
    for item1 in class1:
        for item2 in class2:
            list_0.append(sampleDistance(item1, item2))
    return sum(list_0)/(m*n)

同理，也可以定義“類內(nèi)距離”作為一堆字符串內(nèi)部的屬性。它在實(shí)際意義上可能有些接近于方差。我們規(guī)定：

類內(nèi)距離 = 該字符串集合到自己的距離

def innerClassesDistanse(class1):
    return classesDistance(class1, class1)

到這里你可能已經(jīng)暈了，定義這么多距離到底要干嘛？

我們說(shuō)過(guò)，要把兩類不確定的形式不同的字符串分開(kāi)，關(guān)鍵是定義差異，也就是去量化“長(zhǎng)得顯然不同”到底有多不同。

于是我們發(fā)明了一些“距離”作為量化屬性，兩個(gè)字符串之間，有長(zhǎng)度不同、構(gòu)成的字符不同、字符序列不同，那么這兩個(gè)字符串就有可量化的距離。

兩個(gè)字符串有距離，那么一個(gè)字符串到另一類字符串、一類字符串到另一類字符串、同一類字符串內(nèi)部也有距離。

當(dāng)你混跡人群，最重要的事情是弄清誰(shuí)是朋友、誰(shuí)是敵人。而當(dāng)你需要把人群分為兩類，最重要的事情就是知道兩類人有多不同，以及每類人內(nèi)部有多一致。

放在分類字符串的情景，就是要能夠量化類間距離與類內(nèi)距離。

嘿，這不，我們已經(jīng)有了 classesDistance() 與 innerClassesDistanse()。

就到這里，我們下次再會(huì) :)

編者按：

本文未完待續(xù)，敬請(qǐng)期待后續(xù)推送。參考文獻(xiàn)及示例代碼將在完整文章中給出。

作者認(rèn)為清晰的描述能讓不會(huì)寫代碼的人寫出代碼，所以文中代碼來(lái)自并不會(huì)寫 Python 的朋友，代碼風(fēng)格可能有些奇怪。

文 / YvesX
反正你也猜不出我是做什么的
編 / 熒聲

本文已由作者授權(quán)發(fā)布，版權(quán)屬于創(chuàng)宇前端。歡迎注明出處轉(zhuǎn)載本文。本文鏈接：https://knownsec-fed.com/2018...

想要訂閱更多來(lái)自知道創(chuàng)宇開(kāi)發(fā)一線的分享，請(qǐng)搜索關(guān)注我們的微信公眾號(hào)：創(chuàng)宇前端（KnownsecFED）。歡迎留言討論，我們會(huì)盡可能回復(fù)。

歡迎點(diǎn)贊、收藏、留言評(píng)論、轉(zhuǎn)發(fā)分享和打賞支持我們。打賞將被完全轉(zhuǎn)交給文章作者。

感謝您的閱讀。