.NET Regex 클래스에서 무한 루프를 피하는 방법은 무엇입니까?

StackOverflow https://stackoverflow.com/questions/1200655

  •  05-07-2019
  •  | 
  •  

문제

XPath 표현식을 얻고 선택한 노드의 부모와 일치하는 접두사를 반환하는 간단한 작업을 받았습니다.

예시:

/aaa/bbb       =>   /aaa
/aaa/bbb/ccc   =>   /aaa/bbb
/aaa/bbb/ccc[@x='1' and @y="/aaa[name='z']"] => /aaa/bbb

정사각형 괄호 안에있는 패턴은 인용문 내에 괄호가 포함되어 있기 때문에 정규 표현식을 사용하여이를 달성하기로 결정했습니다. 코드 스 니펫은 다음과 같습니다.

string input =
    "/aaa/bbb/ccc[@x='1' and @y=\"/aaa[name='z'] \"]";
                                            //  ^-- remove space for no loop
string pattern = @"/[a-zA-Z0-9]+(\[([^]]*(]"")?)+])?$";

System.Text.RegularExpressions.Regex re =
    new System.Text.RegularExpressions.Regex(pattern);
bool ismatch = re.IsMatch(input); // <== Infinite loop in here
// some code based on the match

패턴은 다소 규칙적이기 때문에 '/'를 찾은 다음 Indentifier 뒤에 문자열의 끝에서 일치하는 옵션 그룹을 찾았습니다 (....).

코드는 작동하는 것처럼 보이지만 입력 문자열에 대해 다른 값을 가지고 재생하면, 단순히 공간을 삽입하면 (주석에 표시된 위치) .net ismatch 함수가 무한 루프로 들어가서 모든 CPU를 가져옵니다. .

이제이 정규 표현 패턴이 가장 좋은지 여부에 관계없이 (더 복잡했지만 문제를 보여주기 위해 단순화했습니다), 이것은 사소한 것과 Regex를 사용하는 것이 매우 위험 할 수 있음을 보여줍니다.

내가 뭔가를 놓치고 있습니까? 정규 표현식 경기에서 무한 루프를 보호하는 방법이 있습니까?

도움이 되었습니까?

해결책

알겠습니다.

Input: /aaa/bbb/ccc[@x='1' and @y="/aaa[name='z'] "]
Pattern: /[a-zA-Z0-9]+(\[([^]]*(]")?)+])?$

(나는 당신이 "당신의 c#-escaped string에서" ""... vb.net의 번역을 의미한다고 가정합니까?)

첫 번째, /[a-za-z0-9]+ 첫 번째 정사각형 브래킷을 통해 경향이 있습니다.

Input: [@x='1' and @y="/aaa[name='z'] "]

( [[^]]*(] "))))의 외부 그룹은 EOL 전에 0 또는 1 인스턴스가 있으면 일치해야합니다. 따라서 내부를 끊고 어떤 것이 일치하는지 확인합시다.

[["는 바로 멍청이가되어 우리를 남겨 둡니다.

Input: @x='1' and @y="/aaa[name='z'] "]
Pattern: ([^]]*(]")?)+]

패턴 분해 : 0 이상 일치하지 않는] 캐릭터와 일치합니다 "] 0 또는 1 번, 할 수 없을 때까지 계속하십시오. 그런 다음 찾아서 gobble a ] 기후.

패턴은 일치합니다 [^]]* 그것이 도달 할 때까지 ].

사이에 공간이 있기 때문에 ] 그리고 ", 그것은 그 캐릭터 중 하나를 고갈 할 수는 없지만 ? ~ 후에 (]") 어쨌든 진실을 반환 할 수 있습니다.

이제 우리는 성공적으로 일치했습니다 ([^]]*(]")?) 한 번,하지만 + 우리는 우리가 할 수있는 횟수를 여러 번 계속 일치 시키려고 노력해야한다고 말합니다.

이것은 우리를 남겨 둡니다.

Input: ] "]

여기서 문제는이 입력이 일치 할 수 있다는 것입니다 ([^]]*(]")?) an 무한 때때로 겨울을 치르지 않고 "+"는 계속 노력하도록 강요 할 것입니다.

당신은 본질적으로 "0 또는 1"의 "0 또는 1", "0 또는 1"의 "0 또는 1"과 일치 할 수있는 "1 이상"상황과 일치합니다. 나머지 입력에 두 개의 소환자 중 어느 것도 존재하지 않기 때문에 0의 0은 계속 일치합니다. [^]]\* 그리고 0의 0 (]")? 끝없는 루프에서.

입력은 결코 굽지 않으며 "+"이후의 나머지 패턴은 평가되지 않습니다.

(바로 바로 위의 엑스 레피스 에스케이프를 얻었기를 바랍니다.)

다른 팁

여기서 문제는이 입력이 ([^]]*(] ") 일치 할 수 있다는 것입니다.

그것은 .NET의 Regex 구현에서 버그의 지옥입니다. 정규 표현은 그렇게 작동하지 않습니다. 그것들을 오토마타로 바꾸면 빈 문자열의 무한 반복이 여전히 빈 문자열이라는 사실을 자동으로 얻습니다.

다시 말해, 비 버그 리그 즈 엔진은이 무한 루프를 즉시 실행하고 나머지 정규식을 계속합니다.

원한다면 정규 표현식은 제한된 언어로, 그러한 무한 루프를 감지하고 피할 수있는 (그리고 쉽게) 가능합니다.

사용을 보여줍니다 암호 사소하지 않은 것은 위험 할 수 있습니다. 무한 루프를 초래할 수있는 코드를 만들었고 Regex 컴파일러가 의무화되었습니다. x = 0이면 처음 20 이후에 수행되지 않은 새로운 것은 없습니다.

특정 엣지 케이스에서 이것에 대해 걱정이된다면 Regex를위한 스레드를 스폰 한 다음 합리적인 실행 시간 후에 죽일 수 있습니다.

원래의 질문에 답하기 위해 (예 : Regex가있는 무한 루프를 피하는 방법). REGEX 방법으로 시간을 전달할 수 있으므로 .NET 4.5에서는 쉬워졌습니다. 타임 아웃이 만료 될 때 Regex 루프를 중지하고 RegexMatchTimeOutException을 높이는 내부 타이머가 있습니다.

예를 들어, 다음을 수행합니다

string input = "/aaa/bbb/ccc[@x='1' and @y=\"/aaa[name='z'] \"]";
string pattern = @"/[a-zA-Z0-9]+(\[([^]]*(]"")?)+])?$";
bool ismatch = Regex.IsMatch(input, pattern, RegexOptions.None, TimeSpan.FromSeconds(5));

체크 아웃 할 수 있습니다 MSDN 자세한 사항은

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top