2 年 2019 月 XNUMX 日 Cloudflare 中斷的詳細信息

2 年 2019 月 XNUMX 日 Cloudflare 中斷的詳細信息

大約 9 年前,Cloudflare 還是一家小公司,我沒有為它工作,我只是一個客戶。啟動 Cloudflare 一個月後,我收到一封通知,我的網站 jgc.orgDNS 似乎不起作用。 Cloudflare 已更改為 協議緩衝區,並且 DNS 損壞。

我立即寫信給馬修·普林斯,標題是“我的 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 託管規則中推出了一項新規則,因此 CPU 資源即將耗盡 在全球 Cloudflare 網路上處理 HTTP/HTTPS 流量的每個處理器核心上。我們不斷改進 WAF 的託管規則,以應對新的漏洞和威脅。以五月為例,我們匆匆忙忙 添加規則以防範 SharePoint 中的嚴重漏洞。我們 WAF 的重點是能夠在全球範圍內快速部署規則。

不幸的是,上週四的更新包含一個正規表示式,在回溯上浪費了太多的 HTTP/HTTPS CPU 資源。我們的核心代理、CDN 和 WAF 功能因此受到影響。此圖顯示,我們網路中的伺服器上用於服務 HTTP/HTTPS 流量的處理器資源幾乎達到 100%。

2 年 2019 月 XNUMX 日 Cloudflare 中斷的詳細信息
事件期間某一地點的 CPU 使用率

因此,我們的客戶(以及我們客戶的客戶)最終在 Cloudflare 網域上出現 502 錯誤頁面。 502 錯誤是由 Cloudflare 前端 Web 伺服器產生的,這些伺服器仍然具有可用核心,但無法與處理 HTTP/HTTPS 流量的進程進行通訊。

2 年 2019 月 XNUMX 日 Cloudflare 中斷的詳細信息

我們知道這給我們的客戶帶來了多少不便。我們感到非常羞愧。而這次失敗讓我們無法有效處理該事件。

如果您是這些顧客之一,您可能會感到害怕、憤怒和不安。此外,我們還沒有 全球混亂。 CPU 消耗過高是由於一項 WAF 規則使用了措辭不當的正規表示式,導致過度回溯。愧疚的表情是這樣的: (?:(?:"|'|]|}||d|(?:nan|infinity|true|false|null|undefined|symbol|math)|`|-|+)+[)]*;?((?:s|-|~|!|{}||||+)*.*(?:.*=.*)))

雖然這本身就很有趣(我將在下面更詳細地討論它),但 Cloudflare 服務停機 27 分鐘不僅僅是因為正規表達式錯誤。我們花了一段時間來描述導致失敗的事件順序,因此我們反應緩慢。在文章的最後,我將用正規表示式描述回溯並告訴您如何處理它。

發生了什麼事

讓我們按順序開始。這裡的所有時間均採用 UTC 時間。

下午13點42分,防火牆團隊的工程師對偵測規則做了一個小改動 XSS 使用自動過程。因此,創建了變更請求票。我們透過 Jira 管理此類票證(下面的螢幕截圖)。

3分鐘後,出現第一個PagerDuty頁面,報告WAF出現問題。這是一項綜合測試,用於測試 Cloudflare 以外的 WAF(我們有數百個)的功能以監控正常運作。緊隨其後的是有關其他 Cloudflare 端到端服務測試失敗、全球流量問題、廣泛的 502 錯誤以及來自我們位於世界各地城市的存在點 (PoP) 的大量報告的警報頁面,這些報告表明存在缺陷CPU資源。

2 年 2019 月 XNUMX 日 Cloudflare 中斷的詳細信息

2 年 2019 月 XNUMX 日 Cloudflare 中斷的詳細信息

我收到了幾條這樣的警報,然後憤然離開了會議,在我走向談判桌的路上,我們的解決方案開發部門負責人說我們已經損失了 80% 的流量。我跑去找我們的 SRE 工程師,他們已經在解決這個問題了。起初我們以為這是某種未知的攻擊。

2 年 2019 月 XNUMX 日 Cloudflare 中斷的詳細信息

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

這項特定的變更需要在模擬模式下部署,其中真實的客戶端流量通過規則,但不會阻止任何內容。我們使用這種模式來測試規則的有效性並測量誤報率和漏報率。但即使在類比模式下,規則也必須實際執行,在這種情況下,規則包含消耗過多處理器資源的正規表示式。

2 年 2019 月 XNUMX 日 Cloudflare 中斷的詳細信息

正如您從上面的變更請求中看到的,我們有一個部署計劃、一個回滾計劃以及指向此類部署的內部標準操作程序 (SOP) 的連結。用於更改規則的 SOP 允許其在全球範圍內發布。實際上,在 Cloudflare,事情的處理方式完全不同,SOP 規定我們首先將用於測試和內部使用的軟體發送到內部存在點 (PoP)(我們的員工使用),然後發送給少數客戶一個偏僻的地方,然後到大量的客戶,然後才到整個世界。

這就是它的樣子。我們透過 BitBucket 在內部使用 git。負責變更的工程師提交程式碼,該程式碼建置到 TeamCity 中,建置通過後,將分配審閱者。當拉取請求獲得批准時,將組裝程式碼並(再次)執行一系列測試。

如果建置和測試成功完成,則會在 Jira 中建立變更請求,並且相應的經理或領導者必須批准變更。批准後,部署到所謂的「PoP 動物園」:DOG、PIG 和 金絲雀 (狗、豬和金絲雀)。

DOG PoP 是一個 Cloudflare PoP(與我們其他城市一樣),僅供 Cloudflare 員工使用。供內部使用的 PoP 可讓您在客戶流量開始流入解決方案之前發現問題。有用的東西。

如果 DOG 測試成功,程式碼將進入 PIG(豚鼠)階段。這就是 Cloudflare PoP,少量免費客戶流量透過新程式碼流動。
如果一切順利,程式碼將進入 Canary。我們在世界不同地區擁有三個金絲雀 PoP。其中,付費和免費客戶端的流量都會通過新代碼,這是最後一次錯誤檢查。

2 年 2019 月 XNUMX 日 Cloudflare 中斷的詳細信息
Cloudflare 的軟體發布流程

如果程式碼在 Canary 中沒問題,我們就會發布它。經歷所有階段 - DOG、PIG、Canary、整個世界 - 需要幾個小時或幾天,具體取決於程式碼變更。由於 Cloudflare 網路和客戶的多樣性,我們在向全球所有客戶發布程式碼之前對其進行徹底測試。但WAF並沒有特別遵循這個流程,因為需要快速回應威脅。

WAF 威脅
在過去的幾年中,常見應用程式中的威脅顯著增加。這是由於軟體測試工具的可用性更高。例如,我們最近寫過 模糊測試).

2 年 2019 月 XNUMX 日 Cloudflare 中斷的詳細信息
來源: https://cvedetails.com/

通常,會建立概念驗證並立即在 Github 上發布,以便維護應用程式的團隊可以快速測試它並確保它得到充分的保護。因此,Cloudflare 需要能夠盡快回應新的攻擊,以便客戶有機會修復他們的軟體。

Cloudflare 快速回應的一個很好的例子是 5 月部署的 SharePoint 漏洞保護(讀到這裡)。幾乎在發佈公告後不久,我們就注意到在客戶的 SharePoint 安裝中存在大量利用該漏洞的嘗試。我們的人員不斷監控新威脅並編寫規則來保護我們的客戶。

週四引發問題的規則原本是為了防止跨站腳本(XSS)。近年來,此類攻擊也變得更加頻繁。

2 年 2019 月 XNUMX 日 Cloudflare 中斷的詳細信息
來源: https://cvedetails.com/

更改 WAF 託管規則的標準程序是在全球部署之前進行持續整合 (CI) 測試。上週四我們做到了這一點並推出了規則。下午 13:31,一名工程師提交了一份已批准的帶有更改的拉取請求。

2 年 2019 月 XNUMX 日 Cloudflare 中斷的詳細信息

13:37,TeamCity 收集了規則,進行了測試並獲得批准。 WAF測試套件測試WAF的核心功能,由大量針對各個功能的單元測試組成。經過單元測試,我們使用大量的HTTP請求測試了WAF的規則。 HTTP 請求檢查 WAF 應阻止哪些請求(以攔截攻擊)以及允許哪些請求通過(以免阻止所有內容並避免誤報)。但我們沒有測試CPU使用率是否過高,檢查先前WAF建置的日誌顯示規則測試執行時間並沒有增加,很難懷疑資源不足。

測試通過,TeamCity 於下午 13:42 開始自動部署變更。

2 年 2019 月 XNUMX 日 Cloudflare 中斷的詳細信息

水銀

WAF 規則專注於立即威脅補救,因此我們使用 Quicksilver 的分散式鍵值儲存來部署它們,該儲存可以在幾秒鐘內將變更傳播到全球。我們所有的客戶在儀表板或透過 API 更改配置時都使用這項技術,而正是有了它,我們才能以閃電般的速度回應變化。

我們還沒有過多談論快銀。之前我們用過 京都大亨 作為一個全球分佈的鍵值存儲,但它存在運營問題,我們編寫了自己的存儲,並在 180 多個城市進行了複製。我們現在使用 Quicksilver 將設定變更推送到客戶端、更新 WAF 規則並將客戶端編寫的 JavaScript 程式碼分發到 Cloudflare Workers。

從點擊儀表板上的按鈕或呼叫 API 到在全球範圍內進行配置更改,只需幾秒鐘。客戶喜歡這種設定速度。 Workers 為他們提供了幾乎即時的全球軟體部署。平均而言,Quicksilver 每秒傳播約 350 次更改。

而且快銀的速度非常快。平均而言,我們實現了將變更傳播到全球每台電腦的第 99 個百分位數為 2,29 秒。速度通常是件好事。畢竟,當您啟用某個功能或清除快取時,它幾乎會立即發生並且無所不在。透過 Cloudflare Workers 發送程式碼的速度相同。 Cloudflare 向客戶承諾在適當的時間快速更新。

但在這種情況下,速度給我們開了一個殘酷的玩笑,幾秒鐘的時間規則就變了。您可能已經注意到WAF代碼使用Lua。 Cloudflare 在生產和細節方面廣泛使用 Lua WAF 中的 Lua 我們 已經討論過了。 Lua WAF 使用 PCRE 內部並應用回溯進行匹配。它沒有機制來防止表達式失控。下面我將詳細討論這一點以及我們正在採取的措施。

2 年 2019 月 XNUMX 日 Cloudflare 中斷的詳細信息

在部署規則之前,一切都很順利:拉取請求已建立並獲得批准,CI/CD 管道收集並測試程式碼,根據管理部署和回滾的 SOP 提交變更請求,然後部署完成。

2 年 2019 月 XNUMX 日 Cloudflare 中斷的詳細信息
Cloudflare WAF 部署流程

出了點問題
正如我所說,我們每週部署數十條新的 WAF 規則,並且我們有許多系統來防止此類部署的負面後果。當出現問題時,通常是多種情況同時發生的。如果你只找到一個原因,這當然會令人放心,但事實並非總是如此。這些都是共同導致我們的HTTP/HTTPS服務失敗的原因。

  1. 工程師編寫了一個正規表示式,可能會導致過多的結果 回溯.
  2. 在幾週前的 WAF 重構中,一個原本可以防止正規表示式浪費過多 CPU 的功能被錯誤地刪除了——重構是為了讓 WAF 消耗更少的資源。
  3. 正規表示式引擎沒有複雜性保證。
  4. 測試套件無法偵測到 CPU 消耗過多。
  5. SOP 允許在全球範圍內推出非緊急規則更改,而無需執行多步驟流程。
  6. 回滾計劃需要運行完整的 WAF 建置兩次,這需要很長時間。
  7. 關於全球交通問題的第一個警報觸發得太晚了。
  8. 我們花了一些時間來更新狀態頁面。
  9. 由於故障,我們在存取系統時遇到了問題,而且旁路程式也沒有很好地建立。
  10. SRE 工程師無法存取某些系統,因為他們的憑證由於安全原因而過期。
  11. 我們的客戶無法存取 Cloudflare 儀表板或 API,因為他們要經過 Cloudflare 區域。

自上週四以來發生了什麼變化

首先,我們完全停止了 WAF 版本的所有工作,並正在執行以下操作:

  1. 我們正在重新引入已刪除的 CPU 過度使用保護。 (準備好)
  2. 手動檢查 WAF 託管規則中的所有 3868 條規則,以尋找並修正其他潛在的過度回溯情況。 (驗證完成)
  3. 我們在測試集中包含所有規則的效能分析。 (預計:19 月 XNUMX 日)
  4. 切換到正規表示式引擎 re2 - 兩者都提供運行時保證。 (預估:31 月 XNUMX 日)
  5. 我們正在重寫 SOP,以分階段部署規則,就像 Cloudflare 中的其他軟體一樣,但同時能夠在攻擊已經開始時緊急進行全球部署。
  6. 我們正在開發從 Cloudflare 區域緊急刪除 Cloudflare 儀表板和 API 的功能。
  7. 自動頁面更新 Cloudflare 狀態.

從長遠來看,我們正在遠離我幾年前寫的 Lua WAF。將 WAF 移至 新的防火牆系統。這樣,WAF 將更快並獲得更高等級的保護。

結論

這次故障給我們和我們的客戶帶來了麻煩。我們迅速採取行動糾正了這種情況,現在正在解決導致崩潰的流程中的缺陷,並進行更深入的挖掘,以防止將來在遷移到新技術時出現正則表達式的潛在問題。

我們對這次中斷感到非常尷尬,並向我們的客戶致歉。我們希望這些改變能確保類似的事情不會再發生。

應用。回溯正規表示式

要理解如何表達:

(?:(?:"|'|]|}||d
(?:nan|infinity|true|false|null|undefined|symbol|math)|`|-
|+)+[)]*;?((?:s|-|~|!|{}||||+)*.*(?:.*=.*)))

佔用了所有的CPU資源,你需要了解一點標準正規表示式引擎是如何運作的。這裡的問題是模式 .*(?:.*=.*). (?: 以及相應的 ) 是非捕獲組(即,括號中的表達式被分組為單一表達式)。

在CPU消耗過多的情況下,這種模式可以描述為 .*.*=.*。在這種形式下,圖案看起來不必要地複雜。但更重要的是,在現實世界中,要求引擎匹配一個片段後面跟著另一個片段的表達式(如 WAF 規則中的複雜表達式)可能會導致災難性的回溯。這就是原因。

2 年 2019 月 XNUMX 日 Cloudflare 中斷的詳細信息

在正規表示式中 . 意味著你需要匹配一個字符, .* - 「貪婪地」匹配零個或多個字符,即捕獲最多的字符,以便 .*.*=.* 表示匹配零個或多個字符,然後匹配零個或多個字符,找到字面=字符,匹配零個或多個字符。

我們來測試一下線 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 的短視頻 正規表示式::調試器,它顯示了步驟和回溯是如何發生的。

2 年 2019 月 XNUMX 日 Cloudflare 中斷的詳細信息

這已經是很多工作了,但是如果相反呢? x=x 我們將有 x=xx?那是 33 步。而如果 x=xxx? 45. 這種關係不是線性的。該圖顯示了比較 x=xx=xxxxxxxxxxxxxxxxxxxx (20 x=)。如果我們有 20 x 之後 =,引擎花了555步就完成了配對! (此外,如果我們輸了 x= 該字串僅由 20 組成 x,引擎將執行 4067 個步驟來了解沒有匹配項)。

2 年 2019 月 XNUMX 日 Cloudflare 中斷的詳細信息

該視頻顯示了所有回溯以進行比較 x=xxxxxxxxxxxxxxxxxxxx:

2 年 2019 月 XNUMX 日 Cloudflare 中斷的詳細信息

問題在於,隨著字串大小的增加,匹配時間會超線性增長。但如果正規表示式稍作修改,情況可能會變得更糟。假設我們有 .*.*=.*; (也就是說,模式末端有一個分號)。例如,要符合這樣的表達式 foo=bar;.

在這裡,回溯將是一場真正的災難。用於比較 x=x 需要 90 步,而不是 23 步。比較 x= 和20 x,需要5353步。這是圖表。查看軸值 Y 與之前的圖表相比。

2 年 2019 月 XNUMX 日 Cloudflare 中斷的詳細信息

如果您有興趣,請查看所有 5353 個失敗的配對步驟 x=xxxxxxxxxxxxxxxxxxxx и .*.*=.*;

2 年 2019 月 XNUMX 日 Cloudflare 中斷的詳細信息

透過使用惰性匹配而不是貪婪匹配,可以控制回溯的程度。如果我們把原來的表達式改成 .*?.*?=.*?,用於比較 x=x 需要 11 個步驟(而不是 23 個)。至於 x=xxxxxxxxxxxxxxxxxxxx。都是因為 ?.* 告訴引擎在繼續之前匹配最少數量的字元。

但惰性映射並不能完全解決回溯問題。如果我們取代災難性的例子 .*.*=.*;.*?.*?=.*?;,執行時間將維持不變。 x=x 仍需 555 個步驟,且 x= 和20 x - 5353。

唯一可以做的事情(除了完全重寫模式以獲得更大的特異性之外)是放棄正規表示式引擎及其回溯機制。這就是我們在接下來的幾週內要做的事情。

自 1968 年 Kent Thompson 寫了一篇文章以來,這個問題的解決方案就已為人所知 程式設計技術:正規表示式搜尋演算法 (“程式方法:正規表示式搜尋演算法”)。本文描述了一種機制,可讓您將正規表示式轉換為非確定性有限狀態機,並且在非確定性有限狀態機中狀態變更後,使用執行時間線性依賴於匹配字串的演算法。

2 年 2019 月 XNUMX 日 Cloudflare 中斷的詳細信息

程式設計方法
正規表示式搜尋演算法
肯湯普森

貝爾電話實驗室公司,新澤西州默里山

它描述了一種在文本中搜尋特定字串的方法,並討論了該方法以編譯器形式的實現。編譯器將正規表示式作為原始程式碼,並產生 IBM 7094 程式作為目標程式碼。目標程式以搜尋文字的形式取得輸入,並在每次文字字串與給定正規表示式相符時發出訊號。文章提供了範例、問題和解決方案。

算法
如果部分成功的搜尋未能產生結果,先前的搜尋演算法會導致回溯。

在編譯模式下,此演算法不適用於符號。它將指令傳遞給編譯後的程式碼。執行速度非常快 - 將資料傳遞到目前清單的頂部後,它會自動搜尋正規表示式中所有可能的連續字元。
編譯和搜尋演算法作為上下文搜尋包含在分時文字編輯器中。當然,這遠非此類搜尋程式的唯一應用。例如,該演算法的一個變體被用作彙編器表中的符號搜尋。
假設讀者熟悉正規表示式和 IBM 7094 電腦程式語言。

編譯器
編譯器由並行運行的三個階段組成。第一階段是語法過濾,只允許語法正確的正規表示式通過。此步驟也會插入「·」運算子來符合正規表示式。第二步,將正規表示式轉換為後綴形式。在第三階段,建立目標程式碼。前兩個階段是顯而易見的,我們不會詳細討論它們。

Thompson 的文章沒有討論非確定性有限狀態機,但它確實很好地解釋了線性時間演算法,並提出了一個為 IBM 60 生成彙編語言程式碼的 ALGOL-7094 程式。

2 年 2019 月 XNUMX 日 Cloudflare 中斷的詳細信息

目前搜尋路徑。它由 ⊕ 圖示表示,具有一個輸入和兩個輸出。
圖 1 顯示了轉換正規表示式範例時第三編譯步驟的功能。範例中的前三個字元是 a、b、c,每個字元建立一個堆疊條目 S[i] 和一個 NNODE 欄位。

NNODE 到現有程式碼以在單一堆疊條目中產生結果正規表示式(請參閱圖 5)

這就是正規表示式的樣子 .*.*=.*,如果你把它想像成湯普森文章中的圖片。

2 年 2019 月 XNUMX 日 Cloudflare 中斷的詳細信息

在圖中。 0從0開始有3個狀態,從狀態1、2、3開始有XNUMX個週期。 .* 在正規表示式中。 3 個帶點的橢圓對應 XNUMX 個符號。帶有標誌的橢圓形 = 匹配文字字符 =。狀態 4 是最終狀態。如果我們到達它,那麼正規表示式就匹配了。

看看這樣的狀態圖如何用於正規表示式匹配 .*.*=.*,我們將查看字串匹配 x=x。程序從狀態0開始,如圖所示。 1.

2 年 2019 月 XNUMX 日 Cloudflare 中斷的詳細信息

為了使該演算法起作用,狀態機必須同時處於多個狀態。非確定性有限機器將同時進行所有可能的轉換。

在它有時間讀取輸入資料之前,它會進入第一個狀態(1 和 2),如圖 2 所示。 XNUMX.

2 年 2019 月 XNUMX 日 Cloudflare 中斷的詳細信息

在圖中。 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.

2 年 2019 月 XNUMX 日 Cloudflare 中斷的詳細信息

然後演算法繼續到最後一個 x в x=x。從狀態 1 和 2 可以進行相同的轉換回到狀態 1 和 2。 x 可以匹配右邊的點並回到狀態3。

在這個階段,每個角色 x=x 考慮到,由於我們已經到達狀態 4,所以正規表示式與該字串相符。每個字元都被處理一次,因此演算法與輸入字串的長度呈線性關係。並且沒有回頭路。

顯然,到達狀態 4 後(當演算法匹配 x=) 整個正則表達式都被匹配,並且演算法可能根本不考慮它就終止 x.

此演算法線性依賴於輸入字串的大小。

來源: www.habr.com

添加評論