标签：回溯

为什么不能在字符组中使用反向引用

为什么不能在字符组中使用反向引用

有个网友，发一封邮件给我，让我帮看下一段“加密”字符串的解密问题，在线解密的解密不了。代码大约如下：看到代码后，不禁惊讶起来，现在坏人们的想法真猥琐。利用preg_replace函数的e修饰符(e修饰符在php5.5里，被取消了)，来执行第二个参数里的内容，而第二个参数里的内容，不是常规的函数组成的字符串，其函数名都是ASCII码十六进制形式。从而避开了基于字符串形式正则匹配的“简易木马扫描器”的扫描。2010年时的在线解密功能，只支持eval gzinflate base64_decode三个函数的任意组合形式的字符串解密，且格式很严格，必须以<?php开头，以?>结尾，不支持嵌套解密。到了2012年，发现有好多网友在陆续使用，并反馈给我。我再次做了改进，支持嵌套解密，编码转换等功能。这次，看到这个加密方式，索性直接写一个支持任意以eval函数执行的合法php字符串解密，且支持同一份代码的多次出现、循环嵌套解密，格式也不用那么严格，只要被解密部分是合法的php代码即可，其他地方，可以有任意字符串，提高易用程度。方向定了，实现起来，也应该没什么难度，目的也是基于字符串处理，正则匹配php语法函数，提取加密部分，解密，替换到原文本中。所有的难点，就是正则匹配php语法了。我在匹配eval(base64_decode('xxxxxxx'))遇到了一个问题。因为不能确定代码使用的是单引号还是双引号，故我打算捕获分组，再反向引用一下，那正则表达式就是(['"]).+?\1，正则捕获的第一个分组里的内容会是',那么\1的反向引用将是'，看上去，匹配完成了，但会产生大量回溯，回溯次数取决于中间字符串长度。作为性能洁癖的码农，不能接受正则里出现大量无用的回溯，决定使用字符组的脱字符^来对字符取非匹配。那么，表达式就是 regexbuddy的测试结果却是这样：如图，调试信息中所示，绿色线条画出的部分，都是正常正确的匹配，表达式(['"])匹配字符串'，并且分配到group 1中；表达式最后的\1反向引用，也匹配到了'，这个可以在debug截图中得到确认。但红色部分，让我产生了疑惑，表达式[^\1]为何匹配到了字符串1230'''''cfc4n(解释一下：+为量词，先匹配，再将转动权交给表达式后的'，再去匹配，其发现后面没有字符，那么再回溯到前一位。。一直到匹配到字符')，匹配到字符串1230跟cfc4n倒是正常，但group 1就是'，[^\1]匹配到'''''实在不能理解。暂时改用其他办法实现，比如(['"]).*\1，但性能差，且不精确。或者用环视lookaround（也叫零宽断言）解决([\'"])(?:(?!\1).)+\1。对于这个问题，我困惑很久，在stackoverflow上找到一个相似的案例General approach for (equivalent of) “backreferences within character class”?问题也是跟我类似的问题，解决方案，也是用环视解决，其实，环视的效率，比非贪婪的方式还多一个回溯。但回答者只是给了解决方案，也没说出真正的原因。然后，又看到了另一个相似案例Negating a backreference in Regular Expressions，解决方案也是一样，正则环视解决，回答中，还说了原理： Instead of a negated character class, you have to use a negative lookahead: \bvalue\s*=\s*(["'])(?:(?!\1).)*\1 (?:(?!\1).)* consumes one character at a time, after the lookahead has confirmed that the character is not whatever was matched by the capturing group, (["'']). A character class, negated or not, can only match one character at a time. As far as the regex engine knows, \1 could represent any number of characters, and there's no way to convince it that \1 will only contain " or ' in this case. So you have to go with the more general (and less readable) solution. 但这个原理说的是环视匹配的原理，并没有说“为什么字符组中反向引用匹配的字符串不正确”的真正原因。对于我的好奇心，显然不能轻易放过这个疑问，继续google中搜索，终于在regexbuddy的另一个官网找到了介绍：Parentheses and Backreferences Cannot Be Used Inside Character Classes，刚打开这个页面时，被配色、布局震惊了一下，这跟regexbuddy官网出奇的相似，仔细看了下，才发现这也是他们的网站之一。这里给出了说明： Round brackets cannot be used inside character classes, at least not as metacharacters. When you put a round bracket in a character class, it is treated as a literal character. So the regex [(a)b] matches a, b, ( and ). Backreferences also cannot be used inside a character class. The \1 in regex like (a)[\1b] will be interpreted as an octal escape in most regex flavors. So this regex will match an a followed by either \x01 or a b. 这里提到，正则表达式中，不能在字符组中使用反向引用，原因是正则表达式的\1在字符组中[\1]，在大多数的正则流派中，会被正则引擎作为八进制转义，实际上的匹配结果将变成\x01。知道这个原因之后，就很好理解为什么之前的表达式[^\1]匹配到' ' ' ' '了。因为，这里的取非，是对字符\x01的取非，而不是对字符'的取非，我之前还天真的以为，取非的字符串是'呢。除了不能在字符组中使用反向引用，还不能使用捕获分组，这里也提到了，正则表达式的元字符括号()在字符组中将被理解为普通的字符()，也就是说，在字符组character class中，不用再转义了，即[()]是合法的表达式，且可以匹配到(或者)。比如文章中给的例子：表达式[(a)b]匹配结果并不是a或者b，如果a匹配到，再将a分配到group 1中，而是可以匹配到a或b或(或)四个字符。所以，在字符组中使用反向引用，是不能实现的了。如图：最后，解密的程序也写好了，支持eval base64_decode preg_replace gzinflate等各种函数的在线，目前除了自定义函数、字符串不支持解密以外，其他均支持，只要用eval函数执行的代码。跟http://ddecode.com/phpdecoder/相比，我的解密程序不支持变量函数、变量字符串解密，这是缺点。同时，优点是支持一段代码多个eval函数解密，且替换还原到原文。而phpdecoder中，只会保留最后解密的那个eval内代码解密情况，其他的都没了。其实，基于字符串匹配的解密方式，都肯定存在不严谨、不正确的解密行为，最准确的，莫过于写一个php拓展，劫持eval函数，并且执行被解密代码，使用加密代码内原有变量，来实现最准确，严谨的解密。 PS：如果你对这里的正则表达式的术语有疑惑，请阅读这个PPT《正则表达式》PPT-匹配原理 PPS:后来，无意中看到360网站安全检测的后门查杀代码里的正则的写法实在说不过去，作为国内一线安全厂商，这正则准确性、严谨性、误报、性能都有较大提升空间，忍不住的唱起“放只乌龟到处爬，放只螃蟹有点Zha，有点Zha”...如果他们不嫌弃的话，可以参考下《如何精确查找PHP WEBSHELL木马？》里的python版的webshell检测的正则，三年前的了，可能有很多东西已经变了。 2013/09/14更新：我自己开发了一个项目，PHP版本的webshell扫描，基于语法分析的，名字叫 Pecker Scanner，欢迎使用。

2013-08-30 2 0

PHP正则表达式的效率：回溯与固化分组

PHP正则表达式的效率：回溯与固化分组

上文中，我们聊到了一点关于PHP中（NFA PCRE）正则表达式匹配优先量词，忽略优先量词的匹配原理了。那么上文留下的问题，您的答案是什么呢？先来看下问题。字符串正则表达式为这三个正则，分别会造成几次回溯呢？？答案：对于第一种贪婪匹配的匹配规则，回溯的9次是正则【】对字符串“”匹配时，构成的回溯，回溯的次数，恰好是字符串的长度。第二种非贪婪匹配规则，回溯5次，是正则【.+?】对字符串“123456”匹配时构成的回溯。回溯的次数，为字符串长度减去最小次数。也就是6-1=5次。如果正则表达式为【.*?】那么，回溯次数就是6次了。第三种正则是零宽断言，或者叫环视。（暂且不说。）在NFA正则引擎中，回溯是他的灵魂，所以，不管是贪婪，非贪婪，环视等写法中肯定会有回溯的出现的，这个我们无法避免（用词不太准确），但是，我们可以减少回溯的次数，或者保护其中一部分匹配的规则不进行回溯。对于上篇BLOG上提到的鸟哥谈到一个非贪婪引起的大量回溯问题，大家可以知道，回溯，确实是浪费资源的罪魁祸首，那么，我们能否不让其回溯呢？答案是肯定的，NFA引擎中，有个概念，叫固化分组。引用一下书上的概念具体来说，使用「(?>…)」的匹配与正常的匹配并无差别，但是如果匹配进行到此结构之后（也就是，进行到闭括号之后），那么此结构体中的所有备用状态都会被放弃。也就是说，在固化分组匹配结束时，它已经匹配的文本已经固化为一个单元，只能作为整体而保留或放弃。括号内的子表达式中未尝试过的备用状态都不复存在了，所以回溯永远也不能选择其中的状态（至少是，当此结构匹配完成时，“锁定（locked in）”在其中的状态）。那么，固化分组到底有什么用处呢？我们来举个例子。（找不到合适的例子，俺只好借用一下书上的例子了）比如要处理一批数据，原来格式为123.456，后来因为浮点数显示问题，部分数据格式变为123.456000000789这种，，要求做到只保留小数点后面2-3位，但是，最后一位不能为0，这个正则如何写呢？（下面直接考虑小数点后面的数字），写出正则之后，我们还要用这个正则去匹配数据，把原来的数据替换成匹配的结果。首先，我们可以立刻写出这样的正则【\.\d\d[1-9]?\d*】，PHP代码为很明显，这种写法，对于部分数据格式为123.456的这种格式，白白的处理了一遍，为了提高效率，我们还要对这个正则进行处理。从123.456这个字符串跟其他的比较一下，我们发现，是疑问123.456这个数据后面没数字了，所以，白白处理一遍。那好办，我们对这个正则改造一下，把后面的量词*改成+，这样对于123.45 小数点后面1，2位数字的，不会去白白处理，而且，对三位以上数字的，处理正常。其PHP代码为好了，这个正则真的没问题吗？？确定吗？上篇博文，我们了解了匹配原理，那么，我们也分析一下这个正则的匹配过程吧。字符串"123.456",正则表达式为【\.(\d\d[1-9]?)\d+】，我们来看下首先（小数点前123不说了），【\.】匹配"."，匹配成功，把控制权给下一个【\d】，【\d】匹配“4”成功，把控制权给第二个【\d】，这个【\d】匹配“5”成功，然后，把控制权给了【[1-9]?】，由于量词是【?】，正则表达式遵循“量词优先匹配”，而且，此处是【?】，还会留下一个回溯点。然后匹配"6"成功，然后把控制权给【\d+】，【\d+】发现后面没字符了，最遵循“后进先出”规则，回到上一个回溯点，进行匹配，这时，【[1-9]?】会交还出其匹配的字符“6”，【[1-9]?】匹配“6”成功。匹配完成了。大家发现【(\d\d[1-9]?)】匹配的结果确是"45",并不是我们想要的“456”，“6”被【\d+】匹配去了。那么，我们该如何办呢？能否让【[1-9]?】匹配一旦成功，不进行回溯呢？这就用到了我们上面说的"固化分组", PHP（preg_replace函数）中使用的正则引擎支持固化分组，我们根据固化分组的写法，可以把代码改成如下方式改成这样的话，那字符串“123.456“是不符合要求，不会被匹配的。那我们就可以实现我们的要求了。从上面的例子中，知道了固化分组的作用，那么对于鸟哥BLOG上写的那个非贪婪的回溯问题，我们能否也对其改造，使得其不回溯呢？先看下鸟哥给的答案鸟哥写的很精悍。排除“

2010-06-21

+10 14 0

小议正则表达式效率：贪婪、非贪婪与回溯

小议正则表达式效率：贪婪、非贪婪与回溯

前几天看了鸟哥的BLOG上写的关于正则表达式的回溯与递归的限制时，对贪婪、非贪婪产生的回溯有疑问，遂近段时间，仔细的学习研究了一下，现在把经验心得与大家分享一下。（我日，这里好像被左侧的图挡着了，换行换行凑字数，换行换行凑字数，换行换行凑字数，换行换行凑字数，换行换行凑字数，换行换行凑字数，换行换行凑字数，换行换行凑字数，换行换行凑字数，换行换行凑字数，换行换行凑字数，换行换行凑字数，换行换行凑字数，换行换行凑字数，换行换行凑字数）先扫盲一下什么是正则表达式的贪婪，什么是非贪婪？或者说什么是匹配优先量词，什么是忽略优先量词？好吧，我也不知道概念是什么，来举个例子吧。某同学想过滤之间的内容，那是这么写正则以及程序的。看起来，好像没什么问题，其实则不然。若那么经过上面的程序处理，其结果为仍然达不到他想要的效果。上面的就是非贪婪，也有的叫惰性。其标志非贪婪的标识为量数元字符后面加? ，比如 +?、*?、??(比较特殊，以后的BLOG中，我会写到)等。即标识非贪婪，如果不写?就是贪婪。比如以上为贪婪，非贪婪的区别介绍。下面，聊下贪婪、非贪婪引起的回溯问题。先看个小例子。正则表达式为\w*(\d+)，字符串为cfc456n，那么，这个正则匹配的$1是多少？？如果您回答是 456,那么，恭喜你，回答错了，其结果不是456，而是6，您知道为什么吗？ CFC4N来解释一下，当正则引擎用正则\w*(\d+)去匹配字符串cfc456n时，会先用\w*去匹配字符串cfc456n，首先，\w*会匹配字符串cfc456n的所有字符，然后再交给\d+去匹配剩下的字符串，而剩下的没了，这时，\w*规则会不情愿的吐出一个字符，给\d+去匹配，同时，在吐出字符之前，记录一个点，这个点，就是用于回溯的点，然后\d+去匹配n，发现并不能匹配成功，会再次要求\w*再吐出一个字符，\w*会先再次记录一个回溯的点，再吐出一个字符。这时，\w* 匹配的结果只有cfc45了，已经吐出6n了，\d+再去匹配6，发现匹配成功，则会通知引擎，匹配成功了，就直接显示出来了。所以，(\d+)的结果是6，而不是456。当上面的正则表达式改为 \w*?(\d+)（注意，此处为非贪婪），字符串仍然为cfc456n，那么，这时候，正则匹配的$1是多少？？甲同学回答：结果是 456。嗯，是的，正确，是456，CFC4N弱弱的问下，为什么是456 呢？我在来解释一下为什么是456 正则表达式有条规则，是量词优先匹配，所以\w*?会先去匹配字符串cfc456，由于\w*?是非贪婪，正则引擎会用表达式\w+?每次仅匹配一个字符串,然后再将控制权交给后面的\d+去匹配下一个字符，同时，记录一个点，用于在匹配不成功的时候，返回这里，再次匹配，也就是回溯点。由于\w后面是量词是*，*表示0到无数次，所以，首先是0次，也就是\w*?匹配个空，记录回溯点，将控制权交给\d+,\d+去匹配cfc456n的第一个字符c,然后，匹配失败，于是乎，接着讲控制权交给\w*?去匹配cfc456n的c，\w*?匹配c成功，由于是非贪婪，所以，他每次只匹配一个字符，记录回溯点，然后再将控制权交给\d+匹配f,接着，\d+匹配f再失败，再把控制权给\w*?，\w*?再匹配c,记录回溯点（这时\w*?匹配结果是cfc了），再把控制权给\d+，\d+去匹配4，匹配成功，然后，由于量词是+，就是1到无数次，所以，接着往后匹配，再匹配5，成功，再接着，再匹配6，成功，再接着，继续匹配操作，下一个字符是n，匹配失败，这时，\d+会吧控制权交出去。由于\d+后面已经没有正则表达式了，所以，整个正则表达式宣告匹配完成，其结果就是 cfc456, 其中第一组结果是456。亲爱的同学，您明白刚刚的题目的结果，为什么是456了吗？好了，您是否从上面的例子了解了贪婪，非贪婪的匹配原理了？那您是否明白您在什么时候需要使用贪婪，非贪婪去处理您的字符串了？鸟哥的文章里讲到针对表达式、程序为其原因就是回溯太多了，直到造成耗尽栈空间爆栈。再来看个例子。字符串正则表达式为这三个正则，分别会造成几次回溯呢？？答案见下篇 PHP正则表达式的效率：回溯与固化分组

2010-06-18

+8 12 0

最新评论

jeffrey

支持抓取emqx的tls报文么？

w3b5h3ll

不抛弃，不放弃

Zz

可以认为是代理功能吗？最近也在调研这个功能。大鹅项目好像是有类似的逻辑，dns配置 fallback 默认走代理。《ht

CFC4N

参考： https://github.com/gojue/ecapture/discussions/308

Wayne

你好，安卓上想使用eCapture,需要linux内额版本>=5.5 ,目前手上设备只有pixel 5 ,看官方的