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

給你的入侵檢測系統提供一個靈感。

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

當然，有很多方法可以輕易做到。

如果是一堆 “good”、“fine”、“not bad”、“amazing”、"nice" 的簡短反饋里混有 “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.” 這樣的長篇抱怨呢？

你可能會想，這不更簡單了嘛，檢測字符串長度甚至標點符號數目就行呀。

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

或許你已經不耐煩了：這點安全素養還是有的！檢測關鍵字和特殊符號呀！

你已經不打算讓我再“如果”下去了：沒有什么是一段正則表達式搞不定的，如果有，那就該再學一次。

好，但是現在，我們需要的是，用同一個模型實現上述所有場景——當字符串有長有短，它要將長度異常的字符串分開。當有常規字符串和包含特殊符號的字符串，它能把特殊的那些拎出來。當字符串混有不同的語言，它能進行“凈化”。甚至，還有各種不在意料之中的情形。

這段代碼就像是在宗教戰爭中審判異端，無論是中出了一個叛徒還是干脆分裂成了兩類，它總是能根據字符串的長相，把少數派給抓出來。

如果你恰好做過一些事，例如探索深度學習對網絡安全的應用，相信你看著數據集，能很快想到這個“異端審判器”的實用價值。

讓我們默契地眨眨眼。在后文里，我們會實現這樣一個玩具。

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

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

不難發現，字符串之間的距離至少應該包括如下組分：

字符串長度差異（如 cat 與miaomiaomiaomiaomiao）

字符集差異（如 123 與 abc）

字符序列差異（如 上海自來水 與 水來自海上）

這有什么好說的……長度為5的字符串顯然比長度為3的字符串多出一個2……

在此略過。

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

字符集的差異是為了刻畫不同字符串在字符選擇上的差異，我們應該對差異較大的字符串——特別是出現了不同類別的字符時——進行距離上的懲罰。

為了實現這個目標，首先要定義字符間的距離。這里，我們把相同字符間距離定義為 0, 同類字符（如a與b）間距離定義為 1，不同類字符間距離定義為 10。

字符分類可以為小寫字母、大寫字母、數字和其他，當然讀者也可以根據自己的實際用途進行分類，把系統需要敏感識別的差異分為不同的兩類。

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

在上述基礎上，我們進一步定義字符集 A 到字符集 B 間的距離為：A 中每一個字符到 B 的距離的算術和。

顯然：

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

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

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

由此，我們對字符集間距離完成了符合認知的定義。

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

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

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

在這里，我們使用 N-Gram 語言模型，借助 N=2 時的 Gram 數目來度量兩個序列的差異。

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

假設我們有字符串 S1 與 S2。

將字符串 S1 每兩個連續字符作為一個元素，構成集合 G1，同理也有 G2。

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

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))

到現在為止，我們對兩個字符串間三個形式維度的差異都有了量化，接下來做的就是通過精妙絕倫的加權求和，算出那個令人拍案叫絕的字符串間距離。

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

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

是的！簡單相加……

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

你當然可以根據自己的需要，去調節系統對于其中三個維度的不同敏感度，但筆者認為字符集差異的值天然就比另外兩種差異的值要大，已經符合我的需要，就不再調整啦。

有了字符串間的距離，進一步，就有一個字符串到另一堆字符串的距離。我們定義如下：

字符串樣本與字符串集合的距離 = 該字符串樣本到字符串集合中每個字符串樣本的距離的算術平均值

即：

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

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

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

即：

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)

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

類內距離 = 該字符串集合到自己的距離

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

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

我們說過，要把兩類不確定的形式不同的字符串分開，關鍵是定義差異，也就是去量化“長得顯然不同”到底有多不同。

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

兩個字符串有距離，那么一個字符串到另一類字符串、一類字符串到另一類字符串、同一類字符串內部也有距離。

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

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

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

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

編者按：

本文未完待續，敬請期待后續推送。參考文獻及示例代碼將在完整文章中給出。

作者認為清晰的描述能讓不會寫代碼的人寫出代碼，所以文中代碼來自并不會寫 Python 的朋友，代碼風格可能有些奇怪。

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

本文已由作者授權發布，版權屬于創宇前端。歡迎注明出處轉載本文。本文鏈接：https://knownsec-fed.com/2018...

想要訂閱更多來自知道創宇開發一線的分享，請搜索關注我們的微信公眾號：創宇前端（KnownsecFED）。歡迎留言討論，我們會盡可能回復。

歡迎點贊、收藏、留言評論、轉發分享和打賞支持我們。打賞將被完全轉交給文章作者。

感謝您的閱讀。