利用序列學(xué)習(xí)和變階馬爾可夫鏈保護(hù)API不被濫用

考慮一個(gè)惡意行為者試圖通過(guò)API進(jìn)行數(shù)據(jù)注入、抓取、收集或泄露的情況。這類惡意活動(dòng)通常以行為者以特定順序向API端點(diǎn)發(fā)起請(qǐng)求。此外，僅僅使用容量技術(shù)往往無(wú)法輕易檢測(cè)到這些惡意活動(dòng)，因?yàn)樾袨檎呖赡芄室饩徛貓?zhí)行API請(qǐng)求，以試圖規(guī)避容量濫用保護(hù)。因此，為了可靠地防止這種惡意活動(dòng)，我們需要考慮API請(qǐng)求的順序。我們使用序列濫用這個(gè)術(shù)語(yǔ)來(lái)指代惡意的API請(qǐng)求行為。因此，我們的基本目標(biāo)是區(qū)分惡意和合法的API請(qǐng)求序列。

在本篇文章中，您將了解我們?nèi)绾螒?yīng)對(duì)幫助客戶保護(hù)其API免受序列濫用的挑戰(zhàn)。為此，我們將介紹目前支撐我們序列分析產(chǎn)品的統(tǒng)計(jì)機(jī)器學(xué)習(xí)(ML)技術(shù)。我們將在此前一篇博客文章提供的序列分析概括性介紹基礎(chǔ)上進(jìn)行深入探討。

API會(huì)話

在之前的博客文章中提到過(guò)，我們來(lái)考慮一下由某個(gè)用戶發(fā)起一系列按時(shí)間順序排列的HTTP API請(qǐng)求的概念。發(fā)起請(qǐng)求是因?yàn)樵撚脩襞c一項(xiàng)服務(wù)進(jìn)行交互，例如瀏覽一個(gè)網(wǎng)站或使用一個(gè)移動(dòng)應(yīng)用。我們將用戶按時(shí)間順序發(fā)出的一系列API請(qǐng)求稱為一個(gè)會(huì)話。舉一個(gè)熟悉的例子，客戶與銀行服務(wù)交互的會(huì)話可能如下所示：

我們的目標(biāo)之一是，通過(guò)自動(dòng)建議適用于我們的序列緩解產(chǎn)品的規(guī)則，強(qiáng)制執(zhí)行期望的序列行為，從而幫助客戶保護(hù)他們的API。如果我們強(qiáng)制執(zhí)行預(yù)期的行為，就可以防止不想要的順序行為。在我們的例子中，期望的序列行為可能意味著/api/v1/auth必須始終先于/api/v1/accounts/{account_id}執(zhí)行。

我們必須解決的一個(gè)重要挑戰(zhàn)是，可能的會(huì)話數(shù)量會(huì)隨著會(huì)話長(zhǎng)度的增加而迅速增長(zhǎng)。要理解為什么，我們可以考慮用戶與示例銀行服務(wù)交互的其他方式：例如，用戶可以任何順序執(zhí)行多次轉(zhuǎn)賬，和/或查看多個(gè)賬戶的余額。假設(shè)有3個(gè)可能的端點(diǎn)，下圖說(shuō)明了用戶與銀行服務(wù)交互時(shí)可能的會(huì)話：

由于可能的會(huì)話數(shù)量龐大，建議緩解規(guī)則需要我們解決一個(gè)挑戰(zhàn)，即從過(guò)去的會(huì)話數(shù)據(jù)中總結(jié)序列行為作為中間步驟。在我們的例子中，我們將會(huì)話中一系列連續(xù)端點(diǎn)（例如/api/v1/accounts/{account_id}→/api/v1/transferFunds）稱為序列。具體來(lái)說(shuō)，我們需要解決的一個(gè)挑戰(zhàn)是，創(chuàng)建規(guī)則所需的順序行為并不一定僅從數(shù)量上就能明顯看出：例如，/api/transferFunds幾乎總是發(fā)生在在/api/v1/accounts/{account_id}之后，但與序列/api/v1/auth→/api/v1/accounts/{account_id}相比，序列/api/v1/accounts/{account_id}→/api/v1/transferFunds可能相對(duì)少見。因此，如果我們僅根據(jù)數(shù)量進(jìn)行總結(jié)，可能會(huì)認(rèn)為序列/api/v1/accounts/{account_id}→/api/v1/transferFunds不重要，而實(shí)際上我們應(yīng)該將其作為潛在規(guī)則挖掘出來(lái)。

從API會(huì)話中學(xué)習(xí)重要的序列

馬爾可夫鏈（Markov chain）是一種適用于序列數(shù)據(jù)的廣泛建模方法，其中我們會(huì)話數(shù)據(jù)中每個(gè)端點(diǎn)的概率僅取決于先行端點(diǎn)的固定數(shù)量。首先，我們將展示如何將標(biāo)準(zhǔn)馬爾可夫鏈應(yīng)用于會(huì)話數(shù)據(jù)，同時(shí)指出它們的一些局限性。其次，我們將展示如何使用一種不太知名但強(qiáng)大的馬爾可夫鏈來(lái)確定重要的序列。

為便于說(shuō)明，我們假設(shè)我們的會(huì)話數(shù)據(jù)中有3個(gè)可能的端點(diǎn)。我們將使用字母a、b和c來(lái)表示這些端點(diǎn)：

-a:/api/v1/auth

-b:/api/v1/accounts/{account_id}

-c:/api/v1/transferFunds

在最簡(jiǎn)單的形式下，馬爾可夫鏈不過(guò)是一個(gè)表格，它告訴我們?cè)谥狼耙粋€(gè)字母的情況下，下一個(gè)字母的概率。如果我們使用最簡(jiǎn)單的馬爾可夫鏈為過(guò)去的會(huì)話數(shù)據(jù)建模，我們最終可能會(huì)得到這樣的表：

表1

表1列出了馬爾可夫鏈的參數(shù)，即在已知會(huì)話中前一個(gè)端點(diǎn)的情況下，觀察到a、b或c作為會(huì)話中下一個(gè)端點(diǎn)的估計(jì)概率。例如，第3行值為0.67的格表示：在已知前一個(gè)端點(diǎn)為c的情況下，觀察到b作為會(huì)話中的下一個(gè)端點(diǎn)的估計(jì)概率為67%，無(wú)論c之前是否有任何端點(diǎn)。因此，表中的每個(gè)條目對(duì)應(yīng)于兩個(gè)端點(diǎn)的序列。括號(hào)中的值是我們?cè)谶^(guò)去的會(huì)話數(shù)據(jù)中看到每個(gè)雙端點(diǎn)序列的次數(shù)，用于計(jì)算表中的概率。例如，值0.01是計(jì)算分?jǐn)?shù)169/(1555+13718+169)的結(jié)果。這種估計(jì)概率的方法稱為最大似然估計(jì)。

為了確定重要的序列，我們依賴于可信區(qū)間（而非最大似然估計(jì)）來(lái)估計(jì)概率?？尚艆^(qū)間不產(chǎn)生單點(diǎn)估計(jì)（如上所述），而是表示一個(gè)合理的概率范圍。這個(gè)范圍反映了可用的數(shù)據(jù)量，即每行中序列出現(xiàn)的總數(shù)。數(shù)據(jù)越多，可信區(qū)間越窄（反映確定性程度較高），數(shù)據(jù)越少，可信區(qū)間越寬（反映確定性程度較低）。因此，根據(jù)上表中括號(hào)內(nèi)的值，我們可能會(huì)獲得以下可信區(qū)間（粗體條目將在下文中進(jìn)一步解釋）：

表2

為簡(jiǎn)潔起見，我們不會(huì)在這里演示如何手動(dòng)計(jì)算出可信區(qū)間（它們涉及評(píng)估beta分布的分位數(shù)函數(shù)）。盡管如此，修訂后的表格顯示更多數(shù)據(jù)導(dǎo)致可信區(qū)間縮小：注意第一行總共出現(xiàn)15442次，而第二行總共出現(xiàn)328084次。

為了確定重要的序列，我們使用比上述稍微復(fù)雜一些的馬爾可夫鏈。作為中間步驟，我們先考慮每個(gè)表項(xiàng)對(duì)應(yīng)三個(gè)端點(diǎn)序列的情況（而不是上面提到的兩個(gè)），以下是一個(gè)示例表格：

表3

表3再次列出觀察到a、b或c作為會(huì)話中下一個(gè)端點(diǎn)的估計(jì)概率，但基于已知會(huì)話中的前兩個(gè)端點(diǎn)。也就是說(shuō)，第3行區(qū)間值為0.09-0.13的格意味著，已知前兩個(gè)端點(diǎn)為ca時(shí)，觀察到a作為下一個(gè)端點(diǎn)的概率具有從9%到13%的可信區(qū)間，無(wú)論ca之前是否有任何端點(diǎn)。用行話來(lái)說(shuō)，我們說(shuō)上表代表一個(gè)二階馬爾可夫鏈。這是因?yàn)楸碇械捻?xiàng)表示，在知道前兩個(gè)端點(diǎn)作為上下文的情況下觀察到下一個(gè)端點(diǎn)的概率。

作為一個(gè)特例，零階馬爾可夫鏈僅僅表示會(huì)話中接口的分布。我們可以將“空上下文”對(duì)應(yīng)的一行的概率列表如下：

表4

請(qǐng)注意，表4中的概率并不僅僅代表會(huì)話中沒有先行端點(diǎn)的情況。相反，概率是會(huì)話中端點(diǎn)出現(xiàn)的情況，適用于一般情況下，我們不知道前面的端點(diǎn)，也不管以前出現(xiàn)了多少個(gè)端點(diǎn)。

回到我們識(shí)別重要序列的任務(wù)，一種可能的方法可能是簡(jiǎn)單地使用某個(gè)固定階數(shù)N的馬爾可夫鏈。例如，如果我們將表3中可信區(qū)間下限的閾值設(shè)為0.85，則總共會(huì)保留3個(gè)序列。另一方面，這種方法有兩個(gè)值得注意的限制：

1.我們需要一種方法為模型階數(shù)N選擇合適的值。

2.由于模型階保持固定，則已識(shí)別序列均具有相同的長(zhǎng)度N+1。

變階馬爾可夫鏈

變階馬爾可夫鏈（VOMC）是上述固定階馬爾可夫鏈的更強(qiáng)大擴(kuò)展，它解決了上述限制。VOMC利用這樣一個(gè)事實(shí)，即對(duì)于固定階數(shù)N的馬爾可夫鏈的某些選定值，概率表可能包括統(tǒng)計(jì)冗余信息：讓我們比較一下上面的表3和表2，并考慮表3中對(duì)應(yīng)上下文aa、ba、ca（這3個(gè)上下文共享a作為后綴）的粗體行。

對(duì)于所有3個(gè)可能的下一個(gè)端點(diǎn)a,b,c，這些行給出了可信區(qū)間，這些區(qū)間與表2中對(duì)應(yīng)上下文a的各自估計(jì)重疊（也以粗體表示）。我們可以將這些重疊的區(qū)間解釋為，在已知a為先行端點(diǎn)的情況下，概率估計(jì)之間不存在明顯的差異。由于a的先行端點(diǎn)是什么對(duì)下一個(gè)端點(diǎn)的概率沒有明顯影響，我們可以認(rèn)為表3中的這3行是冗余的：我們可以通過(guò)替換成表2中對(duì)應(yīng)于上下文a的行來(lái)“折疊”它們。

按所述修改表3的結(jié)果如下（新行以粗體表示）：

表5

表5代表一個(gè)VOMC，因?yàn)樯舷挛拈L(zhǎng)度可變：在示例中，上下文長(zhǎng)度為1和2。由此可見，表中的條目表示長(zhǎng)度在2到3個(gè)端點(diǎn)之間變化的序列，具體取決于上下文長(zhǎng)度。對(duì)所述折疊上下文的方法進(jìn)行推廣，可以得到如下在離線環(huán)境中學(xué)習(xí)一種VOMC的算法草圖：

(1)定義包含會(huì)話中下一個(gè)端點(diǎn)的估計(jì)概率的表T，給定會(huì)話中可選的0,1,2,…,N_max個(gè)端點(diǎn)。也就是說(shuō)，通過(guò)連接對(duì)應(yīng)于固定階數(shù)0,1,2,…,N_max的馬爾可夫鏈的行來(lái)形成一個(gè)表。

(2)is_modified:=true

(3)DO WHILE is_modified

(4)D:=T中不是T中至少1個(gè)其他上下文后綴的所有上下文

(5)is_modified=false

(6)FOR ctx IN C

(7)IF length(ctx)>0

(8)parent_ctx:=通過(guò)刪除ctx中最左邊端點(diǎn)而獲得的上下文。

(9)IF is_collapsible(ctx,parent_ctx)

(10)修改T，丟棄ctx

(11)is_modified=true

在以上偽代碼中，length(ctx)是上下文ctx的長(zhǎng)度。在第9行，is_colrapsible()涉及比較上下文ctx和parent_ctx，按照生成表5所描述的方式：is_colrapsible()評(píng)估為true，當(dāng)且僅當(dāng)在我們?yōu)槊恳粋€(gè)可能的下一個(gè)端點(diǎn)比較上下文ctx和parent_ctx時(shí)，觀察到所有可信區(qū)間重疊。最大序列長(zhǎng)度為N_max+1，其中N_max是某個(gè)常量。在第4行，如果我們可以通過(guò)在上下文q前添加零個(gè)或多個(gè)端點(diǎn)來(lái)構(gòu)成另一個(gè)上下文p，則q是p的后綴。（根據(jù)這個(gè)定義，上面提到的0階模型的“空上下文”是T中所有上下文的后綴。）上述算法草圖是Rissanen【1】和Ron等人首先提出的想法的一個(gè)變體?！?】。

最后，我們將結(jié)果表T中的條目作為我們的重要序列。因此，應(yīng)用VOMC的結(jié)果是一組我們認(rèn)為重要的序列。然而，對(duì)于序列分析，我們認(rèn)為對(duì)序列進(jìn)行排名也很有用。我們通過(guò)計(jì)算一個(gè)0.0到1.0之間的“優(yōu)先級(jí)分?jǐn)?shù)”來(lái)做到這一點(diǎn)，即序列中出現(xiàn)的次數(shù)除以序列中最后一個(gè)端點(diǎn)的出現(xiàn)次數(shù)。因此，優(yōu)先順序分?jǐn)?shù)接近1.0表示給定端點(diǎn)幾乎總是在序列中的其余端點(diǎn)之前。通過(guò)這種方式，手動(dòng)檢查最高分序列就成為了在我們的序列緩解產(chǎn)品中創(chuàng)建優(yōu)先規(guī)則的一種半自動(dòng)啟發(fā)式方法。

大規(guī)模學(xué)習(xí)序列

以上內(nèi)容是我們?cè)谛蛄蟹治鲋惺褂玫慕y(tǒng)計(jì)機(jī)器學(xué)習(xí)技術(shù)的高層概述。實(shí)際上，我們?cè)O(shè)計(jì)了一種高效的算法，它不需要事先的訓(xùn)練步驟，而是隨著數(shù)據(jù)到達(dá)不斷更新模型，并生成重要序列的頻繁更新摘要。這種方法使我們能夠克服在此博客文章中未涉及的內(nèi)存成本等額外挑戰(zhàn)。最重要的是，上述算法草圖的簡(jiǎn)單實(shí)現(xiàn)仍會(huì)導(dǎo)致表中的行數(shù)（上下文）隨著最大序列長(zhǎng)度的增加而激增。我們需要解決的另一個(gè)挑戰(zhàn)是確保我們的系統(tǒng)能夠處理海量API，而不會(huì)對(duì)CPU負(fù)載產(chǎn)生不利影響。我們?cè)谇捌谑褂昧艘环N水平可擴(kuò)展的自適應(yīng)采樣策略，以便對(duì)海量API進(jìn)行更激進(jìn)的采樣。我們的算法隨后處理這些采樣的API請(qǐng)求流。在客戶入駐后，序列會(huì)隨著時(shí)間的推移進(jìn)行組裝和學(xué)習(xí)，因此重要序列的當(dāng)前摘要表示一個(gè)大約24小時(shí)的回顧區(qū)間。序列分析進(jìn)一步將序列存儲(chǔ)在Clickhouse中，并通過(guò)一個(gè)GraphQL API和Cloudflare儀表板顯示它們。希望實(shí)施序列規(guī)則的客戶可以使用序列分析來(lái)執(zhí)行此操作。序列分析負(fù)責(zé)確保規(guī)則在Cloudflare的全球網(wǎng)絡(luò)上以分布式方式共享和匹配，這是另外一個(gè)令人興奮的話題，我們將在未來(lái)的博客文章中討論。

下一步

現(xiàn)在，您已經(jīng)對(duì)我們?nèi)绾谓沂局匾腁PI請(qǐng)求序列有了更好的理解，請(qǐng)繼續(xù)關(guān)注本系列后續(xù)的博客文章，我們將描述我們?nèi)绾伟l(fā)現(xiàn)客戶可能想要阻止的異常API請(qǐng)求序列。目前，API Gateway客戶可以通過(guò)兩種方式開始：使用序列分析來(lái)探索重要的API請(qǐng)求序列，使用序列緩解來(lái)強(qiáng)制執(zhí)行API請(qǐng)求序列。