【摘要】：正則表達(dá)式是當(dāng)今最流行的字符串處理工具之一,在爬蟲(chóng)、文本編輯器、Web應(yīng)用、搜索引擎、數(shù)據(jù)庫(kù)、命令行工具等場(chǎng)景中廣泛應(yīng)用。然而,設(shè)計(jì)不合理的正則表達(dá)式的匹配時(shí)間復(fù)雜度為超線性甚至指數(shù),容易被攻擊者利用造成系統(tǒng)的拒絕服務(wù)(又稱(chēng)ReDoS問(wèn)題,Regular Expression Denial-of-Service)。ReDoS是一種常見(jiàn)的算法復(fù)雜度攻擊,目前已得到研究者的廣泛關(guān)注。ReDoS檢測(cè)技術(shù)包括靜態(tài)的Pumping分析技術(shù)、匹配過(guò)程轉(zhuǎn)換分析技術(shù)、NFA不確定性分析技術(shù)、對(duì)抗自動(dòng)機(jī)構(gòu)造技術(shù)和動(dòng)態(tài)的黑盒模糊測(cè)試技術(shù)。然而,已有的靜態(tài)、動(dòng)態(tài)ReDoS檢測(cè)技術(shù)在現(xiàn)代擴(kuò)展正則表達(dá)式上存在重大缺陷,針對(duì)需要復(fù)雜長(zhǎng)前綴的攻擊字符串,要么無(wú)法生成,要么需要耗費(fèi)無(wú)法承受的計(jì)算資源。為了實(shí)現(xiàn)高效、有效的ReDoS檢測(cè),本文提出了一種用于描述擴(kuò)展正則表達(dá)式匹配過(guò)程的e-NFA模型,并在此模型的基礎(chǔ)上提出一種三階段的ReDoS檢測(cè)方法。在前兩個(gè)階段中,使用不同的評(píng)估函數(shù)分別針對(duì)e-NFA的覆蓋率和匹配代價(jià)進(jìn)行優(yōu)化;在第三階段中,利用正則表達(dá)式的PumpingLemma高效地得到能夠?qū)嵤㏑eDoS攻擊的字符串。本文將所提出的三階段ReDoS檢測(cè)方法實(shí)現(xiàn)為自動(dòng)化檢測(cè)工具RESCUE。在基準(zhǔn)數(shù)據(jù)和實(shí)際開(kāi)源項(xiàng)目實(shí)驗(yàn)結(jié)果表明RESCUE的ReDoS效果相比于先有的最好技術(shù)提升了49%。在實(shí)際開(kāi)源項(xiàng)目中,RESCUE檢出了10個(gè)前所未知的ReDoS問(wèn)題,在將這些新檢出的安全問(wèn)題報(bào)告給開(kāi)發(fā)者后,部分問(wèn)題得到了修復(fù)。
【學(xué)位授予單位】：南京大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2019
【分類(lèi)號(hào)】：TP309;TP311.1
【圖文】：

則表達(dá)式解析成一種類(lèi)似于ＮＦＡ的結(jié)構(gòu)（后文中的的字符串，在ｅ－ＮＦＡ上執(zhí)行回溯搜索，如果搜索到一徑，則匹配成功，如果所有可能的匹配路徑都無(wú)法到失敗。這種簡(jiǎn)單而原始的通用正則匹配實(shí)現(xiàn)模式使得于維護(hù)，但它基于搜索的實(shí)現(xiàn)方式也為正則表達(dá)式帶正則表達(dá)式為例，逡逑Ａｈ（ｅｌｌｏ｜ｉ｜ａｙ｜ｏｏ丨ｏｌａ），ｗｏｒｌｄ￥逡逑字符串ｈｅｌｌｏ，ｗｏｒｌｄ時(shí)，它只需要檢查第一個(gè)分到匹配結(jié)果：逡逑Ａｈ（ｅｌｌｏ｜ｉ｜ａｙ｜ｏｏ｜ｏｌａ），ｗｏｒｌｄ￥逡逑

３－２：解析ｉＬ則及達(dá)式Ａ（？＝ｈｅｌｌｏ）邋［ａ－ｚ］邋｛５｝獲得的ｅ－Ｎｍ含Ｈ題）給定字符串．Ｖ和語(yǔ)，穿Ｌ（ｒ），判斷字符集合，即判斷．ｖ邋ｅ邋Ｌ（ｒ）是否成立。逡逑則匹配問(wèn)題）給定字符串ｓ和…個(gè)正則表達(dá)式ｒ，Ｆ串．＾／）S藏「茫椋仍蜢鍤剿ㄒ宓姆醚�，紖豺匹配中的—ＮＦｂ徚x霞蛞性謔迪質(zhì)比勻蛔裱缺嘁牒篤ヅ淶姆絞劍蟣澩鍤澆馕齔傘隼嗨憑湔蟣澩鍤狡ヅ涫牽疲粒┙峁梗疚某浦┱溝姆僑范ㄐ雜星鈄遠(yuǎn)�。辶x

本文編號(hào)：2728375