正则表达式复杂度攻击自动化检测技术研究
发布时间：2020-06-24 21:29
【摘要】：正则表达式是当今最流行的字符串处理工具之一,在爬虫、文本编辑器、Web应用、搜索引擎、数据库、命令行工具等场景中广泛应用。然而,设计不合理的正则表达式的匹配时间复杂度为超线性甚至指数,容易被攻击者利用造成系统的拒绝服务(又称ReDoS问题,Regular Expression Denial-of-Service)。ReDoS是一种常见的算法复杂度攻击,目前已得到研究者的广泛关注。ReDoS检测技术包括静态的Pumping分析技术、匹配过程转换分析技术、NFA不确定性分析技术、对抗自动机构造技术和动态的黑盒模糊测试技术。然而,已有的静态、动态ReDoS检测技术在现代扩展正则表达式上存在重大缺陷,针对需要复杂长前缀的攻击字符串,要么无法生成,要么需要耗费无法承受的计算资源。为了实现高效、有效的ReDoS检测,本文提出了一种用于描述扩展正则表达式匹配过程的e-NFA模型,并在此模型的基础上提出一种三阶段的ReDoS检测方法。在前两个阶段中,使用不同的评估函数分别针对e-NFA的覆盖率和匹配代价进行优化;在第三阶段中,利用正则表达式的PumpingLemma高效地得到能够实施ReDoS攻击的字符串。本文将所提出的三阶段ReDoS检测方法实现为自动化检测工具RESCUE。在基准数据和实际开源项目实验结果表明RESCUE的ReDoS效果相比于先有的最好技术提升了49%。在实际开源项目中,RESCUE检出了10个前所未知的ReDoS问题,在将这些新检出的安全问题报告给开发者后,部分问题得到了修复。
【学位授予单位】：南京大学
【学位级别】：硕士
【学位授予年份】：2019
【分类号】：TP309;TP311.1
【图文】：
则表达式解析成一种类似于ＮＦＡ的结构（后文中的的字符串，在ｅ－ＮＦＡ上执行回溯搜索，如果搜索到一径，则匹配成功，如果所有可能的匹配路径都无法到失败。这种简单而原始的通用正则匹配实现模式使得于维护，但它基于搜索的实现方式也为正则表达式带正则表达式为例，逡逑Ａｈ（ｅｌｌｏ｜ｉ｜ａｙ｜ｏｏ丨ｏｌａ），ｗｏｒｌｄ￥逡逑字符串ｈｅｌｌｏ，ｗｏｒｌｄ时，它只需要检查第一个分到匹配结果：逡逑Ａｈ（ｅｌｌｏ｜ｉ｜ａｙ｜ｏｏ｜ｏｌａ），ｗｏｒｌｄ￥逡逑
３－２：解析ｉＬ则及达式Ａ（？＝ｈｅｌｌｏ）邋［ａ－ｚ］邋｛５｝获得的ｅ－Ｎｍ含Ｈ题）给定字符串．Ｖ和语，穿Ｌ（ｒ），判断字符集合，即判断．ｖ邋ｅ邋Ｌ（ｒ）是否成立。逡逑则匹配问题）给定字符串ｓ和…个正则表达式ｒ，Ｆ串．＾／）S藏「茫椋仍蜢锸剿ㄒ宓姆醚裕丛蚱ヅ渲械摹危疲铃义霞蛞性谑迪质比匀蛔裱缺嘁牒笃ヅ涞姆绞剑虮泶锸浇馕龀伞隼嗨凭湔虮泶锸狡ヅ涫牵疲粒┙峁梗疚某浦┱沟姆侨范ㄐ杂星钭远ｅ义
本文编号：2728375
【学位授予单位】：南京大学
【学位级别】：硕士
【学位授予年份】：2019
【分类号】：TP309;TP311.1
【图文】：
则表达式解析成一种类似于ＮＦＡ的结构（后文中的的字符串，在ｅ－ＮＦＡ上执行回溯搜索，如果搜索到一径，则匹配成功，如果所有可能的匹配路径都无法到失败。这种简单而原始的通用正则匹配实现模式使得于维护，但它基于搜索的实现方式也为正则表达式带正则表达式为例，逡逑Ａｈ（ｅｌｌｏ｜ｉ｜ａｙ｜ｏｏ丨ｏｌａ），ｗｏｒｌｄ￥逡逑字符串ｈｅｌｌｏ，ｗｏｒｌｄ时，它只需要检查第一个分到匹配结果：逡逑Ａｈ（ｅｌｌｏ｜ｉ｜ａｙ｜ｏｏ｜ｏｌａ），ｗｏｒｌｄ￥逡逑
３－２：解析ｉＬ则及达式Ａ（？＝ｈｅｌｌｏ）邋［ａ－ｚ］邋｛５｝获得的ｅ－Ｎｍ含Ｈ题）给定字符串．Ｖ和语，穿Ｌ（ｒ），判断字符集合，即判断．ｖ邋ｅ邋Ｌ（ｒ）是否成立。逡逑则匹配问题）给定字符串ｓ和…个正则表达式ｒ，Ｆ串．＾／）S藏「茫椋仍蜢锸剿ㄒ宓姆醚裕丛蚱ヅ渲械摹危疲铃义霞蛞性谑迪质比匀蛔裱缺嘁牒笃ヅ涞姆绞剑虮泶锸浇馕龀伞隼嗨凭湔虮泶锸狡ヅ涫牵疲粒┙峁梗疚某浦┱沟姆侨范ㄐ杂星钭远ｅ义
本文编号：2728375
本文链接：https://www.wllwen.com/kejilunwen/sousuoyinqinglunwen/2728375.html
