(不要吐槽和讨论版本,除非你确定这玩意在新版本上没问题,生产环境随便找台机器测的)
这玩意是我们前端同学问 GPT ,如何写一个匹配网址的正则问到的。
(/^( https?:\/\/)?([\da-z\.-]+)\.([a-z\.]{2,6})([\/\w \.-]*)*\/?$/).test('https://foo.com/a-long-url-contains-path-and-query-and-anchor/foo/bar/baz?boo=baa#anchor');
*** (这个真的可以执行,建议新窗口 F12 试下) ***
于是,真的匹配一段文本的时候,就导致浏览器卡死了,无法做后续渲染,在 profiling 的时候查到是这个正则的问题。
function testRegexPerformance(repeatCount) {
var testString = 'a'.repeat(repeatCount) + '#';
var regex = /(\w*)*$/;
var startTime = process.hrtime();
var result = regex.test(testString);
var endTime = process.hrtime(startTime);
var executionTime = endTime[0] * 1000 + endTime[1] / 1000000;
console.log("Repeat Count:", repeatCount);
console.log("Execution Time:", executionTime + " milliseconds");
console.log("-----------------------------------" + result);
}
// 测试从 1 到 50 的重复次数
for (var i = 1; i <= 50; i++) {
testRegexPerformance(i);
}
Repeat Count: 20
Execution Time: 35.191223 milliseconds
-----------------------------------true
Repeat Count: 21
Execution Time: 71.355698 milliseconds
-----------------------------------true
Repeat Count: 22
Execution Time: 140.852157 milliseconds
-----------------------------------true
Repeat Count: 23
Execution Time: 287.687666 milliseconds
-----------------------------------true
Repeat Count: 24
Execution Time: 577.368917 milliseconds
-----------------------------------true
Repeat Count: 25
Execution Time: 1148.243059 milliseconds
-----------------------------------true
Repeat Count: 26
Execution Time: 2297.804939 milliseconds
在i=25
的时候,执行时间就到了秒级,之后都是指数级增长。
*
表示 0 个或者多个,没有任何一个\w 也是没问题的
# 不匹配
> 'a'.match(/(b)/)
null
# 匹配
> 'a'.match(/(b)/)
null
# 匹配
> 'aa'.match(/(a)/)
[ 'a', 'a', index: 0, input: 'aa', groups: undefined ]
# 不那么匹配
> 'aaa#'.match(/(\w*)*$/)
[ '', undefined, index: 4, input: 'aaa#', groups: undefined ]
# 匹配?
> /(\w*)*$/.test('aaa#')
true
>
起因是我旁边的同学说.net 没有 test ,只有 match ,而且结果是 false
所以,js 里面如果用 match 试下,大概有三种结果:
undefined
js:匹配,衰减
PHP: 不匹配,不衰减
Python:None(不匹配),衰减
Go: 匹配,不衰减
F#: 匹配,衰减
二楼放测试程序,不占地儿了
1
phpfpm OP ```
package main import ( "fmt" "regexp" "strings" "time" ) func testRegexPerformance(repeatCount int) { testString := strings.Repeat("a", repeatCount) + "#" regex := regexp.MustCompile(`(\w*)*$`) startTime := time.Now() result := regex.MatchString(testString) endTime := time.Now() executionTime := endTime.Sub(startTime).Milliseconds() fmt.Println("Repeat Count:", repeatCount) fmt.Println("Execution Time:", executionTime, "milliseconds") fmt.Println("-----------------------------------") fmt.Println(result) } func main() { // 测试从 1 到 50 的重复次数 for i := 1; i <= 50; i++ { testRegexPerformance(i) } } ``` ``` function testRegexPerformance(repeatCount) { var testString = 'a'.repeat(repeatCount) + '#'; var regex = /(\w*)*$/; var startTime = process.hrtime(); var result = regex.test(testString); var endTime = process.hrtime(startTime); var executionTime = endTime[0] * 1000 + endTime[1] / 1000000; console.log("Repeat Count:", repeatCount); console.log("Execution Time:", executionTime + " milliseconds"); console.log("-----------------------------------" + result); } // 测试从 1 到 50 的重复次数 for (var i = 1; i <= 50; i++) { testRegexPerformance(i); } ``` <?php function testRegexPerformance($repeatCount) { $testString = str_repeat('a', $repeatCount) . '#'; $regex = '/(\w*)*$/'; $startTime = microtime(true); $result = preg_match($regex, $testString); $endTime = microtime(true); $executionTime = ($endTime - $startTime) * 1000; echo "Repeat Count: $repeatCount\n"; echo "Execution Time: $executionTime milliseconds\n"; echo "-----------------------------------\n"; var_dump($result); } // 测试从 1 到 50 的重复次数 for ($i = 1; $i <= 50; $i++) { testRegexPerformance($i); } ``` ``` import re import time def test_regex_performance(repeat_count): test_string = 'a' * repeat_count + '#' regex = r'(\w*)*$' start_time = time.time() result = re.match(regex, test_string) end_time = time.time() execution_time = (end_time - start_time) * 1000 print("Repeat Count:", repeat_count) print("Execution Time:", execution_time, "milliseconds") print("-----------------------------------") print(result) # 测试从 1 到 50 的重复次数 for i in range(1, 51): test_regex_performance(i) ``` |
2
yumusb 244 天前
确实会卡死,火狐直接 InternalError: too much recursion 。留个言 等大佬解释。
URL 的正则可以用这个 https://github.com/gchq/CyberChef/blob/master/src/core/operations/RegularExpression.mjs#L52 |
3
phpfpm OP |
4
sunfall 244 天前
你搜一下 `regex ReDoS`
|
5
ghjh 244 天前 via Android
|
7
GeruzoniAnsasu 244 天前
在某些正则引擎上存在利用回溯进行 dos 攻击的手段,js 首当其冲(另一个我知道的是 PHP/PCRE ):
https://www.geeksforgeeks.org/understanding-redos-attack/ https://github.com/owasp-modsecurity/ModSecurity/issues/2072 |
8
rrfeng 244 天前 via Android
正则引擎本来就没有严格一致的实现,除非你不同语言引用同一个实现比如 pcre 。
复杂正则的性能一直是个大坑,只能说尽量少用。 |
9
ZE3kr 244 天前 via iPhone 1
楼上说的对。因为大多数编程语言的 Regex 实现时间复杂度可以是指数级的,好处是常熟项小。具体是因为传统 Regex 是用 NFA 实现的
https://swtch.com/~rsc/regexp/regexp1.html Regular Expression Matching Can Be Simple And Fast (but is slow in Java, Perl, PHP, Python, Ruby, ...) /(\w*)*$/ 一看就是有问题的,因为它括号里面有一个*,括号外面也有个*,你细想一下排列组合,其实每一个字符串都可能有指数个匹配方式 如果不写出这种有问题的 Regex 那目前 NFA Regex 没啥问题,>90%的 Regex 也不会遇到这种问题 |