Java : 높은 CPU 사용률을 사용하는 Matcher.find

Question

mod 보안 규칙 https://github.com/SpiderLabs/owasp-modsecurity-crs을 사용하여 사용자 입력 데이터를 살균합니다. 나는 mod 보안 규칙 정규 표현식과 사용자 입력을 일치시키는 데있어 CPU가 고생하고 지연되는 것을 직면하고 있습니다. 전반적으로 그것은 다양한 유형의 공격 (xss, badrobots, generic 및 sql)을 검사하는 500+ 정규 표현식을 포함합니다. 각 요청마다 모든 매개 변수를 살펴보고이 500 개의 정규 표현식을 모두 확인합니다. 나는 Matcher.find을 사용하여 매개 변수를 확인합니다. 이 경우 일부 매개 변수가 무한 루프에 빠지며 아래 기술을 사용하여이 문제를 해결했습니다.

Cancelling a long running regex match?.

사용자 요청을 sanitize하는 데 약 500ms가 걸리고 cpu %가 (가) 발생합니다. 내 test suite 러너와 함께 visualvm.java.net을 사용하여 분석했습니다.

CPU의 프로필 출력

CPU 사용 % 및로드 평균을 줄이기 위해 제발 도와주세요?

Answer 1

않도록 expresions와 :

• 여러 줄
• 대소 문자를 구분하지
• 등

아마 당신이 정규 표현식을 그룹화 고려하고 사용자의 입력에 따라 일반 expresions의 특정 그룹을 적용 할 수 있습니다 .

Answer 2

가능한 경우 을 정규식으로 컴파일하고 반복적으로 (암시 적으로) 컴파일하지 말고 (특히 루프 내부에서) 보관하십시오.
자세한 내용은 java.util.regex - importance of Pattern.compile()?을 참조하십시오.

Answer 3

큰 수의 정규 표현식을 사용하는 경우 트라이 알고리즘 (http://en.wikipedia.org/wiki/Trie)을 사용하여 (적어도 일부는) 그룹화 할 수 있습니다.
아이디어는 당신이 예를 들어있는 경우가 /abc[0-9-]/, /abde/, /another example/, /.something else/ 및 /.I run out of ideas/ 같은 정규 표현식에, 당신은 이런 식으로 하나의 정규식

/a(?:b(?:c[0-9-]|de)|nother example)|.(?:I run out of ideas|something else)/ 

로 결합 할 수있다는 정규 대신 한 번만 실행한다 네 번, 그리고 당신은 일반적인 시작 부분은 위의 정규식에서 작성된 방법 때문에 많은 backtracking 피할 수 있습니다.

Answer 4

나는 당신이이 글을보고 제안 : "Towards Faster String Matching for Intrusion Detection or Exceeding the Speed of Snort"

는 당신이 설명하는 매칭을 할 수있는 더 좋은 방법이 있습니다. 본질적으로 일치시키려는 500 개의 패턴을 가져 와서 한 번에 모든 규칙에 대한 입력을 매우 효율적으로 일치시킬 수있는 단일 접미어 트리로 컴파일합니다.

이 논문은 Dan Gusfield의 "Boyer-Moore Approach to Exact Set Matching"이라고 설명했습니다.

Boyer-Moore는 문자열 일치를위한 잘 알려진 알고리즘입니다. 이 신문은 Set Matching에 대한 Boyer-Moore의 변형을 설명합니다.

Answer 5

이러한 500 사이에 문제가있는 정규 표현식의 하위 집합이 있어야합니다. 그러한 정규식

String s = "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAB"; 

    Pattern.compile("(A+)+").matcher(s).matches(); 

이 완료되는 데 몇 년이 걸릴 것입니다.

그래서 귀하의 경우 문제가있는 입력으로 모든 문제가있는 정규식을 기록 할 것입니다. 이러한 문제가 발견되면 이러한 몇 가지 문제가있는 정규식을 수동으로 다시 작성하고 원본과 비교하여 테스트 할 수 있습니다. Regexes는 항상 더 간단하고 읽기 쉬운 자바 함수로 재 작성 될 수 있습니다.

위의 문제가 해결되지는 않지만 더 빠른 (경우에 따라 x20) 및 제한된 정규식 library을 사용할 수도 있습니다. Maven Central에서 사용할 수 있습니다.

Answer 6

나는이 문제의 뿌리라고 생각하지 정규식 성능은 당 자체 : 각 요청에 대해

, 나는 모든 매개 변수를 통해 이동하고 모든 500 정규 표현식에 대해 확인

얼마나 빨리 정규 표현식이 될지라도 이것은 여전히 ​​많은 작업입니다. 얼마나 많은 매개 변수를 가지고 있는지 알 수는 없지만 몇 개 밖에없는 경우에도 요청 당 수천 개의 정규 표현식을 확인하고 있습니다. 그것은 CPU를 죽일 수 있습니다.

는 별도로 사전 처리 컴파일 및/또는 그 (것)들을 단순화하여 정규식 성능 향상과 같은 명백한 것들에서, 당신은 정규식 검사의 양을 줄이기 위해 다음과 같은 작업을 수행 할 수 있습니다

1. 사용 포지티브 검증 매개 변수 유형에 따라 사용자 입력 예 : 일부 매개 변수가 단순한 숫자 여야한다면 악의적 인 XML 스크립트가 포함되어 있는지 확인하는 시간을 낭비하지 마십시오. 그냥 [0-9] + (또는 비슷하게 간단한 것과) 일치하는지 확인하십시오. 그렇다면 괜찮습니다 - 500 개의 정규 표현식을 모두 건너 뛰십시오.

2. 전체 공격 클래스를 제거 할 수있는 간단한 regexps를 찾으십시오. 정규식에서 일반적인 것을 찾으십시오. 예를 들어 특정 HTML 태그의 존재 여부를 확인하는 100 개의 정규 표현식을 확인하고, 콘텐츠에 적어도 하나 이상의 HTML 태그가 먼저 포함되어 있는지 확인하십시오. 그렇지 않은 경우 즉시 100 개의 정규식을 확인하지 않아도됩니다.

3. 캐시 결과. webapps에서 생성 된 많은 매개 변수가 반복됩니다. 동일한 내용을 반복해서 확인하지 말고 최종 유효성 검사 결과를 기억하십시오. DOS 공격을 피하기 위해 캐시의 최대 크기를 제한하십시오.

음수 유효성 검사는 일반적으로 우회하기 쉽습니다. 누군가가 악의적 인 코드에서 일부 문자를 변경하면 정규식이 일치하지 않습니다. 새로운 공격으로부터 보호하기 위해 정규 표현식의 "데이터베이스"를 확장해야합니다. 긍정적 인 검증 (화이트리스트 작성)은 이러한 단점을 가지지 않으며 훨씬 더 효과적입니다.