有声小说打包下载,欢乐颂小说

正則表達(dá)式設(shè)計(jì)和開(kāi)發(fā)中避免ReDoS漏洞的原理、示例與應(yīng)對(duì)

當(dāng)前位置：點(diǎn)晴教程→知識(shí)管理交流 →『技術(shù)文檔交流』

admin

2024年3月25日 0:30 本文熱度 1739

日常開(kāi)發(fā)過(guò)程中，開(kāi)發(fā)人員經(jīng)常需要從一大段復(fù)雜的字符串中快速匹配特殊規(guī)律的字符串，比如，在用戶(hù)輸入手機(jī)號(hào)、身份證號(hào)等字符后，提醒用戶(hù)是否輸入規(guī)范。通常，這些功能的實(shí)現(xiàn)需要依賴(lài)叫做“正則表達(dá)式”的方法，當(dāng)在它在處理一些復(fù)雜的、嵌套的或者具有多個(gè)重復(fù)的模式字符串時(shí)就會(huì)造成程序卡死，即造成ReDoS。

正則表達(dá)式簡(jiǎn)介

正則表達(dá)式是一種用單個(gè)字符串來(lái)表示各種字符串的表達(dá)方式，通常用于在文本中搜索和提取字符串。例如，在工作中需要編寫(xiě)一個(gè)從文章中提取電話號(hào)碼的程序，可以使用圖1所示的正則表達(dá)式來(lái)表示“電話號(hào)碼”這個(gè)字符串的特征，就可以方便快速地進(jìn)行檢查。

圖1 表示電話號(hào)碼的正則表達(dá)式字符串

表1 正則表達(dá)式基礎(chǔ)語(yǔ)法

圖1中，第一個(gè)[0-9]表示數(shù)字0到9中的一個(gè)字符，緊接著的{2,3}表示重復(fù)出現(xiàn)兩次或三次的字符串，短橫杠字符后是[0-9]{4}-[0-9]{4}，表示電話號(hào)碼的“中間4位數(shù)-后4位數(shù)”的正則表達(dá)式。

正則表達(dá)式的語(yǔ)法有很多種，本文內(nèi)容基于Python語(yǔ)言編寫(xiě)，所以筆者使用Python中使用的正則表達(dá)式語(yǔ)法來(lái)進(jìn)行解釋。

基于以上正則表達(dá)式可以寫(xiě)一個(gè)簡(jiǎn)單的匹配電話號(hào)碼的Python程序：

圖2 Python電話號(hào)碼的正則表達(dá)式字符串

這段代碼導(dǎo)入的re正則模塊，使用compile定義正則表達(dá)式[0-9]{3}-[0-9]{4}-[0-9]{4}并賦予rx對(duì)象，然后使用search方法查找目標(biāo)字符串target中匹配的手機(jī)號(hào)，最后成功匹配到188-8888-8888。

ReDoS的基礎(chǔ)原理及示例

正則表達(dá)式在匹配字符串時(shí)會(huì)使用到大量的“回溯”，比如正則表達(dá)式ab{1,3}c匹配字符串a(chǎn)babbbcbbbccc的過(guò)程：

當(dāng)前字符a與正則匹配成功，繼續(xù)；

當(dāng)前字符b嘗試匹配b{1,3}貪婪模式的1個(gè)b，匹配內(nèi)容是ab，繼續(xù)；

當(dāng)前字符a嘗試匹配正則的c，匹配失敗；

回到字符串第3個(gè)字符a重新匹配正則，與a匹配成功，繼續(xù)；

連續(xù)匹配成功b{1,3}貪婪模式的3個(gè)b，捕獲abbb字符串，繼續(xù)；

當(dāng)前字符c匹配成功，捕獲abbbc字符串，繼續(xù)；

后續(xù)六個(gè)字符均無(wú)法與正則中的a匹配，退出。

也就是，正則表達(dá)式會(huì)在字符串匹配中嘗試所有可能的匹配，直到匹配失敗。而當(dāng)正則中出現(xiàn)類(lèi)似{}、+、*這類(lèi)表示匹配數(shù)量的含義時(shí)會(huì)發(fā)生回溯（backtracking），如果正則表達(dá)式在匹配字符串的時(shí)候發(fā)生數(shù)量巨大的回溯，便會(huì)導(dǎo)致災(zāi)難性回溯（catastrophic backtracking），從而消耗程序大量的計(jì)算資源，造成拒絕服務(wù)攻擊（Denial of Service）。同時(shí)也說(shuō)明，相同匹配規(guī)則的正則表達(dá)式用不同的寫(xiě)法有不同的匹配次數(shù)，良好的正則表達(dá)式可以降低匹配次數(shù)，提升匹配效率，比如相比上述正則的一種更差寫(xiě)法a(b|bb|bbb)c。

下圖中的代碼是利用回溯消耗計(jì)算資源的一個(gè)示例。由于正則解釋器是不同的開(kāi)發(fā)語(yǔ)言?xún)?nèi)置的，因此選擇不同開(kāi)發(fā)語(yǔ)言做正則匹配的效率也不同，下圖中代碼如果用Python 2.*運(yùn)行，可能需要將近一個(gè)小時(shí)才能完成這個(gè)匹配。

圖3 通過(guò)控制“回溯”數(shù)量來(lái)控制匹配時(shí)間

圖4 通過(guò)控制“*”數(shù)量來(lái)控制回溯數(shù)量來(lái)增加匹配時(shí)長(zhǎng)

通過(guò)改變逗號(hào)的數(shù)量來(lái)查看程序運(yùn)行的時(shí)長(zhǎng)，結(jié)果見(jiàn)圖4。如果有10個(gè)逗號(hào)，程序執(zhí)行0.011秒，而逗號(hào)的數(shù)量改為25，則需要293秒(4.8分鐘)才能完成運(yùn)行。

攻擊Python服務(wù)示例

筆者以圖3的正則表達(dá)式為基礎(chǔ)，構(gòu)建了一個(gè)有Web Basic身份驗(yàn)證機(jī)制的Python服務(wù)，并使用該正則表達(dá)式檢測(cè)HTTP響應(yīng)中的身份認(rèn)證信息。

圖5 通過(guò)HTTP響應(yīng)代碼中的WWW-Authenticate值驗(yàn)證用戶(hù)身份

圖6 構(gòu)造一個(gè)虛假的請(qǐng)求頭信息，在其中添加正則匹配的部分

該請(qǐng)求可以讓正在運(yùn)行的Python服務(wù)中的urllib.request去校驗(yàn)登錄請(qǐng)求，從而對(duì)其請(qǐng)求頭信息進(jìn)行正則匹配，造成無(wú)限制的正則表達(dá)式的回溯匹配，達(dá)到拒絕服務(wù)的效果。

另外，某些應(yīng)用在用戶(hù)登錄功能邏輯中，會(huì)在后端檢測(cè)用戶(hù)口令中是否有包含用戶(hù)名，從而檢測(cè)口令的強(qiáng)度。

圖7 登錄過(guò)程中判斷口令是否包含賬戶(hù)名

上述邏輯中，由于用戶(hù)名和口令是由用戶(hù)輸出，且用戶(hù)名被當(dāng)作正則表示編譯和匹配，那么假如攻擊者輸入的用戶(hù)名是^(([a-z])+.)+[A-Z]([a-z])+$，口令是aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa，會(huì)導(dǎo)致該程序的匹配次數(shù)飆升，從而造成CPU占用率的上升。

圖8 CPU占用率在程序執(zhí)行后上升到15%

正則匹配的原理

正則表達(dá)式的“解釋正則表達(dá)式字符串”和“判斷輸入字符串是否匹配的部分”是利用有限狀態(tài)機(jī)來(lái)實(shí)現(xiàn)的。

有限狀態(tài)機(jī)（FSM，F(xiàn)inite State Automaton）是指對(duì)于給定的一系列輸入序列，內(nèi)部狀態(tài)根據(jù)其輸入轉(zhuǎn)換，并根據(jù)輸入結(jié)束時(shí)的狀態(tài)(接受還是拒絕)輸出(確定)的數(shù)學(xué)模型。有限狀態(tài)機(jī)的特征之一是它內(nèi)部定義的狀態(tài)數(shù)，顧名思義，限定為有限的狀態(tài)。

比如，要查看二進(jìn)制數(shù)中是否有偶數(shù)數(shù)量的0，則可以使用有限狀態(tài)機(jī)。下方的圖9用狀態(tài)轉(zhuǎn)換圖表示確定是否有偶數(shù)數(shù)量0的有限狀態(tài)機(jī)。

圖9 二進(jìn)制中檢測(cè)0的數(shù)量是否為偶數(shù)的有限狀態(tài)機(jī)的狀態(tài)轉(zhuǎn)換圖

狀態(tài)轉(zhuǎn)換圖中每個(gè)圓圈表示一種狀態(tài)，圓圈中的“q0(偶數(shù))”和“q1(奇數(shù))”表示這些狀態(tài)中的一種。粗箭頭所指的圓圈是開(kāi)始時(shí)的狀態(tài)，雙圈表示“受理”的狀態(tài)（本例中受理狀態(tài)是指偶數(shù)個(gè)0的狀態(tài)）。然后，從每個(gè)圓圈延伸出來(lái)的細(xì)箭頭上的數(shù)字表示每個(gè)輸入，箭頭指向的方向是與該輸入相對(duì)應(yīng)的轉(zhuǎn)換目標(biāo)的狀態(tài)（本例中輸入是0和1）。

如果輸入是1010，從左到右讀取字符，第一個(gè)輸入字符是1，它從q0指向q0，下一個(gè)輸入是0，狀態(tài)機(jī)從q0指向q1。接下來(lái)是1，從q1指向q1，最后一個(gè)輸入是0，從 q1指向q0。

開(kāi)始狀態(tài)q0→q0→q1→q1→q0（結(jié)束: 接受結(jié)果，偶數(shù)個(gè)0）

最終結(jié)果如上所述，用雙圈表示的q0成為此次處理的受理狀態(tài)（偶數(shù)），因此判定“1010中有偶數(shù)個(gè)0”。

Cloudflare的ReDoS攻擊事件

2019年7月2日，Cloudflare在WAF管理規(guī)則中部署一條新規(guī)則，該規(guī)則中的正則表達(dá)式能夠產(chǎn)生災(zāi)難性回溯，造成HTTP/HTTPS服務(wù)所在服務(wù)器CPU資源消耗劇增，同時(shí)也影響了Cloudflare的核心代理、CDN和WAF功能。

圖10 事件發(fā)生的半個(gè)小時(shí)內(nèi)，CPU占用率飆升至100%

產(chǎn)生的后果是，包括Cloudflare公司在內(nèi)的所有使用Cloudflare域名解析服務(wù)的網(wǎng)站訪問(wèn)頁(yè)面都是502 Bad Gateway。而在此之前，Cloudflare已經(jīng)6年未發(fā)生過(guò)全球性事故了，對(duì)于公司的品牌和聲譽(yù)影響可見(jiàn)一斑。

事故是當(dāng)天的13:42一名工程師提交的WAF規(guī)則變更導(dǎo)致，由于WAF規(guī)則更新的及時(shí)性特性，WAF規(guī)則更新無(wú)需經(jīng)過(guò)灰度發(fā)布，且集成測(cè)試中也無(wú)關(guān)于CPU性能的測(cè)試，故導(dǎo)致錯(cuò)誤的規(guī)則被發(fā)布上線。事故處理時(shí)Cloudflare一度將全球的WAF功能停用，最終在14:52修復(fù)問(wèn)題并恢復(fù)WAF。其中涉及的正則表達(dá)式如下：

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

問(wèn)題出自該正則中非捕獲分組（non-capturing group）.*(?:.*=.*)，簡(jiǎn)化之后事.*.*=.*，上文說(shuō)過(guò)在諸如*出沒(méi)的正則中要注意回溯的問(wèn)題，這里的連續(xù)三個(gè).*表達(dá)式，意味著字符串越長(zhǎng)，回溯的次數(shù)越多，正則匹配需要花費(fèi)的時(shí)間越長(zhǎng)。比如下圖中的匹配時(shí)間對(duì)比。