大約 9 年前,Cloudflare 還是一家小公司,我沒有為它工作,我只是一個客戶。啟動 Cloudflare 一個月後,我收到一封通知,我的網站
我立即寫信給馬修·普林斯,標題是“我的 DNS 在哪裡?”,他發回了一份充滿技術細節的長回复(
作者:約翰‧格雷厄姆-卡明
日期:7年2010月9日 14:XNUMX
主題:回覆:我的 DNS 在哪裡?
致:馬修‧普林斯很酷的報告,謝謝。如果有問題我一定會打電話。一旦您收集了所有技術信息,可能值得寫一篇關於此的文章。我認為人們會喜歡一個開放而誠實的故事。特別是如果您附上圖表來顯示自發布以來流量的成長。
我的網站有良好的監控,每次失敗我都會收到一封簡訊。監控顯示故障發生時間為13:03:07至14:04:12。每五分鐘進行一次測試。
我相信你會明白的。您確定您在歐洲不需要自己的人嗎? 🙂
他回答說:
作者:馬修‧普林斯
日期:7年2010月9日 57:XNUMX
主題:回覆:我的 DNS 在哪裡?
致:約翰·格雷厄姆-卡明謝謝。我們回覆了所有來信的人。我現在正在去辦公室的路上,我們將在博客上寫一些東西,或者在我們的公告板上釘上官方帖子。我完全同意,誠實就是一切。
現在 Cloudflare 是一家非常大的公司,我為它工作,現在我必須公開寫下我們的錯誤、其後果和我們的行動。
2 月 XNUMX 日活動
2 月 XNUMX 日,我們在 WAF 託管規則中推出了一項新規則,因此
不幸的是,上週四的更新包含一個正規表示式,在回溯上浪費了太多的 HTTP/HTTPS CPU 資源。我們的核心代理、CDN 和 WAF 功能因此受到影響。此圖顯示,我們網路中的伺服器上用於服務 HTTP/HTTPS 流量的處理器資源幾乎達到 100%。
因此,我們的客戶(以及我們客戶的客戶)最終在 Cloudflare 網域上出現 502 錯誤頁面。 502 錯誤是由 Cloudflare 前端 Web 伺服器產生的,這些伺服器仍然具有可用核心,但無法與處理 HTTP/HTTPS 流量的進程進行通訊。
我們知道這給我們的客戶帶來了多少不便。我們感到非常羞愧。而這次失敗讓我們無法有效處理該事件。
如果您是這些顧客之一,您可能會感到害怕、憤怒和不安。此外,我們還沒有 (?:(?:"|'|]|}||d|(?:nan|infinity|true|false|null|undefined|symbol|math)|`|-|+)+[)]*;?((?:s|-|~|!|{}||||+)*.*(?:.*=.*)))
雖然這本身就很有趣(我將在下面更詳細地討論它),但 Cloudflare 服務停機 27 分鐘不僅僅是因為正規表達式錯誤。我們花了一段時間來描述導致失敗的事件順序,因此我們反應緩慢。在文章的最後,我將用正規表示式描述回溯並告訴您如何處理它。
發生了什麼事
讓我們按順序開始。這裡的所有時間均採用 UTC 時間。
下午13點42分,防火牆團隊的工程師對偵測規則做了一個小改動
3分鐘後,出現第一個PagerDuty頁面,報告WAF出現問題。這是一項綜合測試,用於測試 Cloudflare 以外的 WAF(我們有數百個)的功能以監控正常運作。緊隨其後的是有關其他 Cloudflare 端到端服務測試失敗、全球流量問題、廣泛的 502 錯誤以及來自我們位於世界各地城市的存在點 (PoP) 的大量報告的警報頁面,這些報告表明存在缺陷CPU資源。
我收到了幾條這樣的警報,然後憤然離開了會議,在我走向談判桌的路上,我們的解決方案開發部門負責人說我們已經損失了 80% 的流量。我跑去找我們的 SRE 工程師,他們已經在解決這個問題了。起初我們以為這是某種未知的攻擊。
Cloudflare SRE 工程師分散在世界各地,全天候監控情況。通常,這些警報會通知您範圍有限的特定本地問題,在內部儀表板上進行跟踪,並每天多次解決。但這些頁面和通知表明事情確實很嚴重,SRE 工程師立即宣布嚴重級別 P0 並聯繫管理和系統工程師。
那時我們倫敦的工程師正在主廳聽講座。講座不得不中斷,大家聚集在一個大會議室裡,並召集了更多的專家。這不是 SRE 可以自行處理的典型問題。迫切需要合適的專家參與。
14:00,我們確定問題出在WAF上,沒有發生攻擊。效能團隊提取了 CPU 數據,很明顯 WAF 是罪魁禍首。另一位員工使用 strace 證實了這個理論。還有人在日誌中看到WAF有問題。下午 14:02,當有人提議使用全域終止(Global Kill)時,整個團隊來找我,這是 Cloudflare 中內建的一種機制,可以在全球範圍內關閉一個元件。
我們如何為 WAF 進行全球殺戮是一個不同的故事。事情沒那麼簡單。我們使用我們自己的產品,並且由於我們的服務
我們無法存取內部服務,例如 Jira 或建置系統。我們需要一個我們很少使用的解決機制(這也需要解決)。最終,一名工程師於 14:07 成功禁用了 WAF,並於 14:09 各地的流量和 CPU 等級恢復正常。 Cloudflare 的其餘保護機制正常運作。
然後我們開始恢復WAF。這種情況不同尋常,因此我們在一個城市使用單獨的流量進行了負面測試(詢問自己更改是否真的是問題所在)和正面測試(確保回滾有效),從那裡轉移付費客戶。
14點52分,我們確信我們理解了原因並進行了更正,並再次啟用了WAF。
Cloudflare 的工作原理
Cloudflare 擁有一支致力於管理 WAF 規則的工程師團隊。他們努力提高檢測率、減少誤報並在新威脅出現時快速回應。在過去 60 天內,已處理 476 個針對 WAF 託管規則的變更請求(平均每 3 小時 XNUMX 個)。
這項特定的變更需要在模擬模式下部署,其中真實的客戶端流量通過規則,但不會阻止任何內容。我們使用這種模式來測試規則的有效性並測量誤報率和漏報率。但即使在類比模式下,規則也必須實際執行,在這種情況下,規則包含消耗過多處理器資源的正規表示式。
正如您從上面的變更請求中看到的,我們有一個部署計劃、一個回滾計劃以及指向此類部署的內部標準操作程序 (SOP) 的連結。用於更改規則的 SOP 允許其在全球範圍內發布。實際上,在 Cloudflare,事情的處理方式完全不同,SOP 規定我們首先將用於測試和內部使用的軟體發送到內部存在點 (PoP)(我們的員工使用),然後發送給少數客戶一個偏僻的地方,然後到大量的客戶,然後才到整個世界。
這就是它的樣子。我們透過 BitBucket 在內部使用 git。負責變更的工程師提交程式碼,該程式碼建置到 TeamCity 中,建置通過後,將分配審閱者。當拉取請求獲得批准時,將組裝程式碼並(再次)執行一系列測試。
如果建置和測試成功完成,則會在 Jira 中建立變更請求,並且相應的經理或領導者必須批准變更。批准後,部署到所謂的「PoP 動物園」:DOG、PIG 和
DOG PoP 是一個 Cloudflare PoP(與我們其他城市一樣),僅供 Cloudflare 員工使用。供內部使用的 PoP 可讓您在客戶流量開始流入解決方案之前發現問題。有用的東西。
如果 DOG 測試成功,程式碼將進入 PIG(豚鼠)階段。這就是 Cloudflare PoP,少量免費客戶流量透過新程式碼流動。
如果一切順利,程式碼將進入 Canary。我們在世界不同地區擁有三個金絲雀 PoP。其中,付費和免費客戶端的流量都會通過新代碼,這是最後一次錯誤檢查。
如果程式碼在 Canary 中沒問題,我們就會發布它。經歷所有階段 - DOG、PIG、Canary、整個世界 - 需要幾個小時或幾天,具體取決於程式碼變更。由於 Cloudflare 網路和客戶的多樣性,我們在向全球所有客戶發布程式碼之前對其進行徹底測試。但WAF並沒有特別遵循這個流程,因為需要快速回應威脅。
WAF 威脅
在過去的幾年中,常見應用程式中的威脅顯著增加。這是由於軟體測試工具的可用性更高。例如,我們最近寫過
通常,會建立概念驗證並立即在 Github 上發布,以便維護應用程式的團隊可以快速測試它並確保它得到充分的保護。因此,Cloudflare 需要能夠盡快回應新的攻擊,以便客戶有機會修復他們的軟體。
Cloudflare 快速回應的一個很好的例子是 5 月部署的 SharePoint 漏洞保護(
週四引發問題的規則原本是為了防止跨站腳本(XSS)。近年來,此類攻擊也變得更加頻繁。
更改 WAF 託管規則的標準程序是在全球部署之前進行持續整合 (CI) 測試。上週四我們做到了這一點並推出了規則。下午 13:31,一名工程師提交了一份已批准的帶有更改的拉取請求。
13:37,TeamCity 收集了規則,進行了測試並獲得批准。 WAF測試套件測試WAF的核心功能,由大量針對各個功能的單元測試組成。經過單元測試,我們使用大量的HTTP請求測試了WAF的規則。 HTTP 請求檢查 WAF 應阻止哪些請求(以攔截攻擊)以及允許哪些請求通過(以免阻止所有內容並避免誤報)。但我們沒有測試CPU使用率是否過高,檢查先前WAF建置的日誌顯示規則測試執行時間並沒有增加,很難懷疑資源不足。
測試通過,TeamCity 於下午 13:42 開始自動部署變更。
水銀
WAF 規則專注於立即威脅補救,因此我們使用 Quicksilver 的分散式鍵值儲存來部署它們,該儲存可以在幾秒鐘內將變更傳播到全球。我們所有的客戶在儀表板或透過 API 更改配置時都使用這項技術,而正是有了它,我們才能以閃電般的速度回應變化。
我們還沒有過多談論快銀。之前我們用過
從點擊儀表板上的按鈕或呼叫 API 到在全球範圍內進行配置更改,只需幾秒鐘。客戶喜歡這種設定速度。 Workers 為他們提供了幾乎即時的全球軟體部署。平均而言,Quicksilver 每秒傳播約 350 次更改。
而且快銀的速度非常快。平均而言,我們實現了將變更傳播到全球每台電腦的第 99 個百分位數為 2,29 秒。速度通常是件好事。畢竟,當您啟用某個功能或清除快取時,它幾乎會立即發生並且無所不在。透過 Cloudflare Workers 發送程式碼的速度相同。 Cloudflare 向客戶承諾在適當的時間快速更新。
但在這種情況下,速度給我們開了一個殘酷的玩笑,幾秒鐘的時間規則就變了。您可能已經注意到WAF代碼使用Lua。 Cloudflare 在生產和細節方面廣泛使用 Lua
在部署規則之前,一切都很順利:拉取請求已建立並獲得批准,CI/CD 管道收集並測試程式碼,根據管理部署和回滾的 SOP 提交變更請求,然後部署完成。
出了點問題
正如我所說,我們每週部署數十條新的 WAF 規則,並且我們有許多系統來防止此類部署的負面後果。當出現問題時,通常是多種情況同時發生的。如果你只找到一個原因,這當然會令人放心,但事實並非總是如此。這些都是共同導致我們的HTTP/HTTPS服務失敗的原因。
- 工程師編寫了一個正規表示式,可能會導致過多的結果
回溯 . - 在幾週前的 WAF 重構中,一個原本可以防止正規表示式浪費過多 CPU 的功能被錯誤地刪除了——重構是為了讓 WAF 消耗更少的資源。
- 正規表示式引擎沒有複雜性保證。
- 測試套件無法偵測到 CPU 消耗過多。
- SOP 允許在全球範圍內推出非緊急規則更改,而無需執行多步驟流程。
- 回滾計劃需要運行完整的 WAF 建置兩次,這需要很長時間。
- 關於全球交通問題的第一個警報觸發得太晚了。
- 我們花了一些時間來更新狀態頁面。
- 由於故障,我們在存取系統時遇到了問題,而且旁路程式也沒有很好地建立。
- SRE 工程師無法存取某些系統,因為他們的憑證由於安全原因而過期。
- 我們的客戶無法存取 Cloudflare 儀表板或 API,因為他們要經過 Cloudflare 區域。
自上週四以來發生了什麼變化
首先,我們完全停止了 WAF 版本的所有工作,並正在執行以下操作:
- 我們正在重新引入已刪除的 CPU 過度使用保護。 (準備好)
- 手動檢查 WAF 託管規則中的所有 3868 條規則,以尋找並修正其他潛在的過度回溯情況。 (驗證完成)
- 我們在測試集中包含所有規則的效能分析。 (預計:19 月 XNUMX 日)
- 切換到正規表示式引擎
re2 或銹 - 兩者都提供運行時保證。 (預估:31 月 XNUMX 日) - 我們正在重寫 SOP,以分階段部署規則,就像 Cloudflare 中的其他軟體一樣,但同時能夠在攻擊已經開始時緊急進行全球部署。
- 我們正在開發從 Cloudflare 區域緊急刪除 Cloudflare 儀表板和 API 的功能。
- 自動頁面更新
Cloudflare 狀態 .
從長遠來看,我們正在遠離我幾年前寫的 Lua WAF。將 WAF 移至
結論
這次故障給我們和我們的客戶帶來了麻煩。我們迅速採取行動糾正了這種情況,現在正在解決導致崩潰的流程中的缺陷,並進行更深入的挖掘,以防止將來在遷移到新技術時出現正則表達式的潛在問題。
我們對這次中斷感到非常尷尬,並向我們的客戶致歉。我們希望這些改變能確保類似的事情不會再發生。
應用。回溯正規表示式
要理解如何表達:
(?:(?:"|'|]|}||d
(?:nan|infinity|true|false|null|undefined|symbol|math)|`|-
|+)+[)]*;?((?:s|-|~|!|{}||||+)*.*(?:.*=.*)))
佔用了所有的CPU資源,你需要了解一點標準正規表示式引擎是如何運作的。這裡的問題是模式 .*(?:.*=.*)
. (?:
以及相應的 )
是非捕獲組(即,括號中的表達式被分組為單一表達式)。
在CPU消耗過多的情況下,這種模式可以描述為 .*.*=.*
。在這種形式下,圖案看起來不必要地複雜。但更重要的是,在現實世界中,要求引擎匹配一個片段後面跟著另一個片段的表達式(如 WAF 規則中的複雜表達式)可能會導致災難性的回溯。這就是原因。
在正規表示式中 .
意味著你需要匹配一個字符, .*
- 「貪婪地」匹配零個或多個字符,即捕獲最多的字符,以便 .*.*=.*
表示匹配零個或多個字符,然後匹配零個或多個字符,找到字面=字符,匹配零個或多個字符。
我們來測試一下線 x=x
。它對應於表達式 .*.*=.*. .*.*
在等號與第一個等號匹配之前 x
(其中一組 .*
對應於 x
,第二個 - 零字元)。 .*
after = 最後匹配 x
.
此比較需要 23 個步驟。第一組 .*
в .*.*=.*
貪婪地行動並匹配整個字串 x=x
。引擎移至下一組 .*
。我們沒有更多的字元可以匹配,所以第二組 .*
匹配零個字元(這是允許的)。然後引擎移動到標誌處 =
。沒有更多符號(第一組 .*
使用了整個表達式 x=x
),不會發生比較。
然後正規表示式引擎回到開頭。他進入第一組 .*
並比較它 с x=
(反而 x=x
),然後進行第二組 .*
。第二組 .*
與第二個相比 x
,我們又沒有剩下任何字元了。當引擎再次到達 =
в .*.*=.*
,沒有任何效果。然後他又退縮了。
這次的團 .*
仍然匹配 x=
,但第二組 .*
不再 x
和零個字元。引擎正在嘗試尋找文字字符 =
在圖案中 .*.*=.*
,但是就是不出來(畢竟第一組已經佔領了 .*
)。然後他又退縮了。
這次是第一組 .*
只取第一個 x。但第二組 .*
「貪婪」地捕捉 =x
。你已經猜到會發生什麼事了嗎?引擎嘗試匹配文字 =
,失敗並再次回溯。
第一組 .*
仍然匹配第一個 x
。第二 .*
只需要 =
。當然,引擎無法匹配字面意思 =
,因為第二組已經這樣做了 .*
。又再一次回溯。我們正在嘗試匹配一個由三個字元組成的字串!
結果,第一組 .*
僅匹配第一個 x
, 第二 .*
- 零個字符,引擎最終匹配文字 =
在表達中 с =
排隊。接下來是最後一組 .*
與上一個相比 x
.
23步驟僅用於 x=x
。觀看有關使用 Perl 的短視頻
這已經是很多工作了,但是如果相反呢? x=x
我們將有 x=xx
?那是 33 步。而如果 x=xxx
? 45. 這種關係不是線性的。該圖顯示了比較 x=x
對 x=xxxxxxxxxxxxxxxxxxxx
(20 x
後 =
)。如果我們有 20 x 之後 =
,引擎花了555步就完成了配對! (此外,如果我們輸了 x=
該字串僅由 20 組成 x
,引擎將執行 4067 個步驟來了解沒有匹配項)。
該視頻顯示了所有回溯以進行比較 x=xxxxxxxxxxxxxxxxxxxx
:
問題在於,隨著字串大小的增加,匹配時間會超線性增長。但如果正規表示式稍作修改,情況可能會變得更糟。假設我們有 .*.*=.*
; (也就是說,模式末端有一個分號)。例如,要符合這樣的表達式 foo=bar;
.
在這裡,回溯將是一場真正的災難。用於比較 x=x
需要 90 步,而不是 23 步。比較 x=
和20 x
,需要5353步。這是圖表。查看軸值 Y
與之前的圖表相比。
如果您有興趣,請查看所有 5353 個失敗的配對步驟 x=xxxxxxxxxxxxxxxxxxxx
и .*.*=.*;
透過使用惰性匹配而不是貪婪匹配,可以控制回溯的程度。如果我們把原來的表達式改成 .*?.*?=.*?
,用於比較 x=x
需要 11 個步驟(而不是 23 個)。至於 x=xxxxxxxxxxxxxxxxxxxx
。都是因為 ?
後 .*
告訴引擎在繼續之前匹配最少數量的字元。
但惰性映射並不能完全解決回溯問題。如果我們取代災難性的例子 .*.*=.*;
上 .*?.*?=.*?;
,執行時間將維持不變。 x=x
仍需 555 個步驟,且 x=
和20 x
- 5353。
唯一可以做的事情(除了完全重寫模式以獲得更大的特異性之外)是放棄正規表示式引擎及其回溯機制。這就是我們在接下來的幾週內要做的事情。
自 1968 年 Kent Thompson 寫了一篇文章以來,這個問題的解決方案就已為人所知
程式設計方法
正規表示式搜尋演算法
肯湯普森
貝爾電話實驗室公司,新澤西州默里山它描述了一種在文本中搜尋特定字串的方法,並討論了該方法以編譯器形式的實現。編譯器將正規表示式作為原始程式碼,並產生 IBM 7094 程式作為目標程式碼。目標程式以搜尋文字的形式取得輸入,並在每次文字字串與給定正規表示式相符時發出訊號。文章提供了範例、問題和解決方案。
算法
如果部分成功的搜尋未能產生結果,先前的搜尋演算法會導致回溯。在編譯模式下,此演算法不適用於符號。它將指令傳遞給編譯後的程式碼。執行速度非常快 - 將資料傳遞到目前清單的頂部後,它會自動搜尋正規表示式中所有可能的連續字元。
編譯和搜尋演算法作為上下文搜尋包含在分時文字編輯器中。當然,這遠非此類搜尋程式的唯一應用。例如,該演算法的一個變體被用作彙編器表中的符號搜尋。
假設讀者熟悉正規表示式和 IBM 7094 電腦程式語言。編譯器
編譯器由並行運行的三個階段組成。第一階段是語法過濾,只允許語法正確的正規表示式通過。此步驟也會插入「·」運算子來符合正規表示式。第二步,將正規表示式轉換為後綴形式。在第三階段,建立目標程式碼。前兩個階段是顯而易見的,我們不會詳細討論它們。
Thompson 的文章沒有討論非確定性有限狀態機,但它確實很好地解釋了線性時間演算法,並提出了一個為 IBM 60 生成彙編語言程式碼的 ALGOL-7094 程式。
目前搜尋路徑。它由 ⊕ 圖示表示,具有一個輸入和兩個輸出。
圖 1 顯示了轉換正規表示式範例時第三編譯步驟的功能。範例中的前三個字元是 a、b、c,每個字元建立一個堆疊條目 S[i] 和一個 NNODE 欄位。NNODE 到現有程式碼以在單一堆疊條目中產生結果正規表示式(請參閱圖 5)
這就是正規表示式的樣子 .*.*=.*
,如果你把它想像成湯普森文章中的圖片。
在圖中。 0從0開始有3個狀態,從狀態1、2、3開始有XNUMX個週期。 .*
在正規表示式中。 3 個帶點的橢圓對應 XNUMX 個符號。帶有標誌的橢圓形 =
匹配文字字符 =
。狀態 4 是最終狀態。如果我們到達它,那麼正規表示式就匹配了。
看看這樣的狀態圖如何用於正規表示式匹配 .*.*=.*
,我們將查看字串匹配 x=x
。程序從狀態0開始,如圖所示。 1.
為了使該演算法起作用,狀態機必須同時處於多個狀態。非確定性有限機器將同時進行所有可能的轉換。
在它有時間讀取輸入資料之前,它會進入第一個狀態(1 和 2),如圖 2 所示。 XNUMX.
在圖中。 2 顯示了當他看第一個時會發生什麼 x
в x=x
. x
可以映射到頂點,從狀態 1 回到狀態 1。 x
可以映射到下面的點,從狀態 2 回到狀態 2。
匹配第一個後 x
в x=x
我們仍然處於狀態 1 和 2。 =
.
然後該演算法考慮 =
в x=x
。與先前的 x 一樣,它可以匹配從狀態 1 到狀態 1 或從狀態 2 到狀態 2 的前兩個循環中的任一個,但該演算法可以匹配文字 =
並從狀態 2 轉移到狀態 3(並立即轉移到狀態 4)。這如圖所示。 3.
然後演算法繼續到最後一個 x
в x=x
。從狀態 1 和 2 可以進行相同的轉換回到狀態 1 和 2。 x
可以匹配右邊的點並回到狀態3。
在這個階段,每個角色 x=x
考慮到,由於我們已經到達狀態 4,所以正規表示式與該字串相符。每個字元都被處理一次,因此演算法與輸入字串的長度呈線性關係。並且沒有回頭路。
顯然,到達狀態 4 後(當演算法匹配 x=
) 整個正則表達式都被匹配,並且演算法可能根本不考慮它就終止 x
.
此演算法線性依賴於輸入字串的大小。
來源: www.habr.com