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

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

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

本文編號：2728375