자바 정규 표현 식 의 재난 적 역 추적 으로 인 한 높 은 CPU 이상: java. util. regex. Pattern $Loop. match
37228 단어 작업 기록
어느 날 리더 리 포트 는 온라인 CPU 가 이전 버 전이 바 뀐 후부 터 계속 높 은 상태 에 있 었 다. 지도 자 는 이 시간의 곡선 도 를 보면 서 두 개의 스 레 드 가 끊임없이 순환 하고 있다 고 판단 했다.
미 션 을 받 고 AWS 의 클 라 우 드 워 치 를 살 펴 보 니 온라인 CPU 가 계속 높 은 편 이 었 고 사용률 은 거의 두 배 였 다.또한 스 레 드 사용률 이 이전 보다 훨씬 빈번 한 것 으로 나 타 났 다.나중에 회사 의 큰 사내 가 Dump 를 받 은 후에 분석 을 통 해 정규 표현 식 으로 인 한 CPU 의 지속 적 인 높 은 사용률 문제 임 을 발견 했다.
스 택 정 보 는 다음 과 같 습 니 다.
at java.util.regex.Pattern$Loop.match(Pattern.java:4787)
at java.util.regex.Pattern$GroupTail.match(Pattern.java:4719)
at java.util.regex.Pattern$Curly.match0(Pattern.java:4281)
at java.util.regex.Pattern$Curly.match(Pattern.java:4236)
at java.util.regex.Pattern$Curly.match0(Pattern.java:4274)
at java.util.regex.Pattern$Curly.match(Pattern.java:4236)
at java.util.regex.Pattern$GroupCurly.match0(Pattern.java:4487)
at java.util.regex.Pattern$GroupCurly.match(Pattern.java:4407)
at java.util.regex.Pattern$Curly.match0(Pattern.java:4274)
at java.util.regex.Pattern$Curly.match(Pattern.java:4236)
at java.util.regex.Pattern$GroupHead.match(Pattern.java:4660)
at java.util.regex.Pattern$Loop.match(Pattern.java:4787)
at java.util.regex.Pattern$GroupTail.match(Pattern.java:4719)
at java.util.regex.Pattern$Curly.match0(Pattern.java:4281)
at java.util.regex.Pattern$Curly.match(Pattern.java:4236)
at java.util.regex.Pattern$Curly.match0(Pattern.java:4274)
at java.util.regex.Pattern$Curly.match(Pattern.java:4236)
at java.util.regex.Pattern$GroupCurly.match0(Pattern.java:4487)
at java.util.regex.Pattern$GroupCurly.match(Pattern.java:4407)
at java.util.regex.Pattern$Curly.match0(Pattern.java:4274)
at java.util.regex.Pattern$Curly.match(Pattern.java:4236)
at java.util.regex.Pattern$GroupHead.match(Pattern.java:4660)
at java.util.regex.Pattern$Loop.match(Pattern.java:4787)
at java.util.regex.Pattern$GroupTail.match(Pattern.java:4719)
at java.util.regex.Pattern$Curly.match0(Pattern.java:4274)
at java.util.regex.Pattern$Curly.match(Pattern.java:4236)
at java.util.regex.Pattern$Curly.match0(Pattern.java:4274)
at java.util.regex.Pattern$Curly.match(Pattern.java:4236)
at java.util.regex.Pattern$GroupCurly.match0(Pattern.java:4487)
at java.util.regex.Pattern$GroupCurly.match(Pattern.java:4407)
at java.util.regex.Pattern$Curly.match0(Pattern.java:4274)
at java.util.regex.Pattern$Curly.match(Pattern.java:4236)
at java.util.regex.Pattern$GroupHead.match(Pattern.java:4660)
at java.util.regex.Pattern$Loop.matchInit(Pattern.java:4803)
at java.util.regex.Pattern$Prolog.match(Pattern.java:4743)
at java.util.regex.Pattern$GroupCurly.match0(Pattern.java:4487)
at java.util.regex.Pattern$GroupCurly.match(Pattern.java:4407)
at java.util.regex.Pattern$GroupTail.match(Pattern.java:4719)
at java.util.regex.Pattern$BranchConn.match(Pattern.java:4570)
at java.util.regex.Pattern$BmpCharProperty.match(Pattern.java:3800)
at java.util.regex.Pattern$Branch.match(Pattern.java:4606)
at java.util.regex.Pattern$GroupHead.match(Pattern.java:4660)
at java.util.regex.Pattern$Start.match(Pattern.java:3463)
at java.util.regex.Matcher.search(Matcher.java:1248)
at java.util.regex.Matcher.find(Matcher.java:637)
at com.core.cbx.mybatis.plugin.sql.TableAliasParseInjector.getTableAlias(TableAliasParseInjector.java:48)
정규 표현 식 도 이런 문 제 를 일 으 킬 수 있다 는 것 을 처음 알 았 다. 인터넷 에서 자 료 를 찾 아 보 니 똑 같은 문제 에 부 딪 히 는 사람 이 많 았 다.이 문 제 는 정규 표현 식 의 재난 적 역 추적 (Catastrophic Backtracking) 이나 역 추적 함정 으로 인 한 것 이다.
또한 jdk 의 JIRA 에서 도 이 문 제 를 제기 한 것 을 발견 할 수 있 습 니 다. 그러나 아직 이 bug 가 해결 되 지 않 았 습 니 다. 다음은 공식 적 인 issue 링크 입 니 다. Stack Overflow Error in java. util. regex. Pattern.
엔진 과 역 추적
여기 서 다음 형님 의 원문 을 인용 하여 정규 표현 식 의 엔진 과 역 추적 체 제 를 간단하게 소개 합 니 다.
정규 엔진 은 주로 기본적으로 다른 두 가지 로 나 눌 수 있다. 하 나 는 DFA (확정 형 은 가난 한 자동 동기) 이 고 다른 하 나 는 NFA (불확실 형 은 가난 한 자동 동기) 이다.쉽게 말 하면 NFA 는 정규 표현 식 주도 의 일치 에 대응 하고 DFA 는 텍스트 주도 의 일치 에 대응 합 니 다.
DFA 는 일치 하 는 텍스트 에 착안 하여 왼쪽 에서 오른쪽으로 문자 마다 두 번 일치 하지 않 습 니 다. 시간 복잡 도 는 여러 가지 방식 이기 때문에 보통 속도 가 빠 르 지만 지원 하 는 특성 이 적 고 캡 처 그룹, 각종 인용 등 을 지원 하지 않 습 니 다.한편, NFA 는 정규 표현 식 에 착안 하여 문 자 를 계속 읽 고 현재 정규 와 일치 하 는 지, 일치 하지 않 으 면 문 자 를 뱉 어 다시 시도 합 니 다. 보통 속도 가 느 리 고 가장 좋 은 시간 복잡 도 는 여러 가지 이 며 최 악의 경 우 는 지수 급 입 니 다.그러나 NFA 는 더 많은 특성 을 지원 하기 때문에 절대 다수의 프로 그래 밍 장면 (자바, js 포함) 에서 우리 가 직면 하 는 것 은 NFA 이다.
자바 의 정규 표현 식 엔진 은 NFA 알고리즘 을 사용 하여 정규 표현 식 에 따라 텍스트 와 일치 할 때 역 추적 체 제 를 가지 고 있 습 니 다.다음 문 자 를 만 났 을 때 역 추적 이 발생 할 수 있 습 니 다.
? + * {min, max} 상기 네 가지 기본 값 은 탐욕 모드 로 텍스트 와 일치 합 니 다. 즉, 가능 한 한 많은 문자 와 일치 합 니 다.이 일치 하 는 과정 에서 반드시 한 번 씩 텍스트 와 일치 합 니 다. 일치 하지 않 을 때 까지 한 번 거 슬러 올 라 가 정규 표현 식 의 다음 문자 로 거 슬러 올 라 가기 전에 일치 하지 않 는 텍스트 와 일치 합 니 다.
여기 서 말 하 는 것 은 추상 적 이 고 관심 이 있 는 것 은 정규 표현 식 의 역 추적 과 탐욕 모델, 게 으 름 모델 (억지로 모델 이 라 고도 함) 과 독점 모델 (침략 모델 이 라 고도 함) 을 스스로 검색 할 수 있다. 다음은 그림 과 글 이 모두 풍부 한 글 을 첨부 할 수 있다. 정규 표현 식 세 가지 모델: 탐욕 모델, 게 으 름 모델, 독점 모델
한 마디 로 하면 정규 표현 식 의 역 추적 으로 인해 우리 의 정규 표현 식 이 잘 쓰 이지 않 고 일치 하 는 문자열 텍스트 가 매우 길 면 역 추적 을 대량으로 촉발 하여 CPU 가 급증 하고 심지어 스 택 이 넘 칠 수 있 습 니 다.이른바 재난 적 역 추적 이나 역 추적 함정 이다.
말레이시아 의 상점 이름 을 검증 하기 위해 다음 과 같은 정규 표현 식 을 썼 습 니 다.
^([A-Za-z0-9._()&'\\- ]|[aAàÀảẢãÃáÁạẠăĂằẰẳẲẵẴắẮặẶâÂầẦẩẨẫẪấẤậẬbBcCdDđĐeEèÈẻẺẽẼéÉẹẸêÊềỀểỂễỄếẾệỆfFgGhHiIìÌỉỈĩĨíÍịỊjJkKlLmMnNoOòÒỏỎõÕóÓọỌôÔồỒổỔỗỖốỐộỘơƠờỜởỞỡỠớỚợỢpPqQrRsStTuUùÙủỦũŨúÚụỤưƯừỪửỬữỮứỨựỰvVwWxXyYỳỲỷỶỹỸýÝỵỴzZ])+$
이것 은 바로 매우 간단 한
^()+$ 구조 이다. 영문 자모 대소 문자, 숫자, 베트남 어 와 일부 특수 문자, 예 를 들 어 '&', '-', '' 등 을 사용 할 수 있 기 때문에 이 문자 들 을 직접 [] 에 넣 은 다음 에 편리 하 게 보기 위해 베트남 어 를 다른 [] 에 넣 고 마지막 으로 이 두 개 [] 를 | 에 넣 었 다.연결 하 다.보기 에는 매우 간단 한 구조 이지 만 온라인 상에 서 가끔 CPU 가 너무 높 은 문 제 를 일 으 킬 수 있 습 니 다. 아래 의 테스트 유형 으로 간단하게 뛰 어 볼 수 있 습 니 다.
import java.util.regex.Matcher;
import java.util.regex.Pattern;
public class Test {
private static final String REGEX_TABLE_ALIAS = "^([A-Za-z0-9._()&'\\- ]|[aAàÀảẢãÃáÁạẠăĂằẰẳẲẵẴắẮặẶâÂầẦẩẨẫẪấẤậẬbBcCdDđĐeEèÈẻẺẽẼéÉẹẸêÊềỀểỂễỄếẾệỆfFgGhHiIìÌỉỈĩĨíÍịỊjJkKlLmMnNoOòÒỏỎõÕóÓọỌôÔồỒổỔỗỖốỐộỘơƠờỜởỞỡỠớỚợỢpPqQrRsStTuUùÙủỦũŨúÚụỤưƯừỪửỬữỮứỨựỰvVwWxXyYỳỲỷỶỹỸýÝỵỴzZ])+$";
public static void main(final String[] args) {
final String string = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa!";
final Pattern pattern = Pattern.compile(REGEX_TABLE_ALIAS);
final Matcher matcher = pattern.matcher(string);
final boolean result = matcher.find();
System.out.println(result);
}
}
이
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa! 문자열 을 검사 할 때 바로 검사 결 과 를 출력 할 수 없 으 므 로 상당 한 시간 을 기 다 려 야 한 다 는 것 을 알 게 될 것 이다.이 문자열 을 이것 으로 바 꾸 면 !aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa 초 에 결 과 를 낼 수 있 습 니 다.이 두 문자열 은 똑 같이 길다. 차 이 는
! 첫 번 째 와 마지막 에 있 을 뿐 이지 만 검사 할 때 걸 리 는 시간 은 완전히 다르다. 그 이 유 는 ! 불법 문자 이지 만 마지막 에 대량의 역 추적 을 촉발 하기 때문이다. 이 문자열 의 텍스트 가 수백 자리, 수천 자리 가 있 으 면 스 택 이 넘 칠 가능성 이 높다.원문 작가 의 해결 방법 은 원래 의 정규 표현 식 을 독점 모델 로 바 꾸 는 것 이다. 즉,
+ 뒤에 + 을 더 해 ^()+$ 구 조 를 ^()++$ 구조 로 바 꾸 는 것 이다.이런 방법 은 사실 그다지 좋 지 않다 고 생각 합 니 다. 독점 모델 도 가능 한 한 많은 문자 와 일치 하지만 역 추적 이 일어나 지 않 습 니 다. 정규 표현 식 을 잘 쓰 지 못 하면 누락 을 검사 할 수 있 습 니 다.사실은 더 좋 은 개선 방법 이 있 습 니 다. 바로 원래 표현 식 의 두 개
[] 를 하나 [] 로 합 친 것 입 니 다. 다음 과 같 습 니 다.^([A-Za-z0-9._()&'\\- aAàÀảẢãÃáÁạẠăĂằẰẳẲẵẴắẮặẶâÂầẦẩẨẫẪấẤậẬbBcCdDđĐeEèÈẻẺẽẼéÉẹẸêÊềỀểỂễỄếẾệỆfFgGhHiIìÌỉỈĩĨíÍịỊjJkKlLmMnNoOòÒỏỎõÕóÓọỌôÔồỒổỔỗỖốỐộỘơƠờỜởỞỡỠớỚợỢpPqQrRsStTuUùÙủỦũŨúÚụỤưƯừỪửỬữỮứỨựỰvVwWxXyYỳỲỷỶỹỸýÝỵỴzZ])+$
이 럴 때 위의 테스트 클래스 를 달 려 가면 위의 두 문자열 텍스트 를 검사 할 때 검사 결 과 를 초 단위 로 낼 수 있 습 니 다.이 유 는 새로운 표현 식 이 역 추적 기 회 를 줄 였 기 때 문 입 니 다. 자바 의 여러 if 문 구 를 하나 로 합 친 것 과 같 습 니 다. 그러면 분기 가 줄 어 들 고 자 연 스 럽 게 재난 적 인 역 추적 가능성 을 낮 출 수 있 습 니 다.
구체 적 인 사례 와 해결 방안
위 는 다른 사람들 이 만난 사례 로 블 로 거들 이 만난 케이스 와 최종 해결 방안 을 말한다.시스템 에서 우 리 는 자신 이 고 친 my batis 를 사용 합 니 다. 그 중에서 정규 표현 식 은 sql 의 표 별명 을 가 져 오 는 데 사 용 됩 니 다. 다음 과 같 습 니 다.
(FROM|JOIN|,)(\\s)+([A-Z0-9_]+(\\s)+[A-Z0-9_]+(,| )*)+(\\s)+(JOIN|WHERE|INNER|LEFT|OUTER|ON|ORDER)
이것 은 원래 문제 가 없 었 는데, 얼마 전에 시스템 이 바 뀌 었 을 때, 어떤 고객 이 페이지 에서 비교적 긴 문자열 을 검색 했다.이 검색 의 동작 은 db 에 sql 을 보 내 서 여러 필드 에 사용자 가 검색 한 문자열 이 있 는 지 모호 하 게 조회 하 는 것 입 니 다.그리고 이 sql 을 조립 할 때 상기 정규 표현 식 을 사용 하여 표 의 별명 을 가 져 옵 니 다. 구체 적 인 조립 논 리 는 여기 서 말 하지 않 겠 습 니 다.마지막 으로 조립 한 sql 은 비교적 길 고 약 만 여 개의 문자 (이미 간소화 되 었 다).이렇게 긴 이 유 는 사용자 가 입력 한 문자열 을 가지 고 데이터 시트 에 있 는 여러 문자 형식의 열 을 모호 하 게 조회 하기 때 문 입 니 다. 즉, 대량의
like '%xxxx%' 부분 이 있 을 것 입 니 다.이 긴 sql 이 상기 정규 표현 식 과 일치 할 때 재난 적 인 역 추적 이 발생 하여 시스템 이 장시간 가사 하 게 됩 니 다.여기에 구체 적 인 sql 을 붙 이지 않 고 상기 정규 표현 식 에 무슨 문제 가 있 는 지 간단하게 분석 합 니 다.
표현 식 은 세 부분 으로 나 뉘 는데 첫 번 째 부분 은
(FROM|JOIN|,)(\\s)+ 이 고 두 번 째 부분 은 ([A-Z0-9_]+(\\s)+[A-Z0-9_]+(,| )*)+ 이 며 세 번 째 부분 은 (JOIN|WHERE|INNER|LEFT|OUTER|ON|ORDER) 입 니 다.이것 은 이해 하기 쉽다. 바로 다음 표 의 별명 과 간단하게 일치 하 는 것 이다. 예 를 들 어 from Table_A a, Table_B b where ....표현 식 의 첫 번 째 부분 과 두 번 째 부분 은 모두
, 가 있 고 두 번 째 부분의 끝 은 + 한정 을 사용 하여 적어도 한 번 은 일치 해 야 하 며 sql 이 너무 길 고 대량의 쉼표 빈 칸 이 존재 할 때 대량의 역 추적 을 촉발 할 수 있 음 을 알 수 있 습 니 다.이 를 피하 기 위해 서 는 2 부 말미 + 를 최대한 빼 고 가능 하 다 면 * 로 전환 해 야 한다.최종 수정 방안 은 두 부분 으로 나 뉜 다. 첫 번 째 부분 은 sql 을 간소화 하 는 것 이다. 원래 조립 한 sql 을 직접 가 져 와 일치 시 키 는 것 이 었 기 때문에 sql 에 있 는 대량의
like '%xxxx%' 부분 은 의미 가 없다. 목적 은 표 별명 만 얻 는 것 이기 때문이다.그래서 일치 하기 전에 이 모호 하고 일치 하 는 부분 을 직접 지 웠 습 니 다.두 번 째 부분 은 정규 표현 식 을 수정 하 는 것 입 니 다. 테스트 할 때 간단 한 sql 로 일치 합 니 다. 재난 적 인 역 추적 이 발생 하지 않 으 면 통과 합 니 다.최종 수 정 된 모습 은 다음 과 같다.
(FROM|JOIN)(\\s)+([A-Z0-9_]+(\\s)+[A-Z0-9_]+((\\s)*(,|JOIN)(\\s)*[A-Z0-9_]+(\\s)+[A-Z0-9_]+)*)(\\s)+(JOIN|WHERE|INNER|LEFT|OUTER|ON|ORDER)
여기 서 정규 표현 식 이 문자열 텍스트 와 일치 하 는 사 이 트 를 온라인 으로 검사 하 는 것 을 추천 합 니 다. 재난 적 인 역 추적 을 일 으 킬 수 있 는 지 확인 할 수 있 습 니 다. Online regex tester and debugger: PHP, PCR, Python, Golang and JavaScript 이 사이트 의 용법 은 이 문장의 끝 부분 을 볼 수 있 습 니 다. 정규 표현 식 으로 인 한 혈액 사건 으로 온라인 CPU 100% 이상!
높 은 CPU 사용률 을 조사 하 는 방법
top 합 니 다.이 명령 으로 직접 정렬 할 수도 있 습 니 다. CPU 를 많이 사용 하 는 스 레 드 를 쉽게 찾 을 수 있 습 니 다. ps -mp pid -o THREAD,tid,time ps -mp pid -o THREAD,tid,time|uniq -c|sort -nr 예 를 들 어 원래 의 스 레 드 TID 는 28802 이 고 위의 명령 으로 16 진수 7082 printf “%x
” TID또한 전체 스 택 정 보 를 하나의 log 파일 에 입력 할 수 있 습 니 다. 두 가지 방법 이 있 습 니 다.jstack PID|grep TID -A 100 를 사용 하 는데 이런 방법 은 JDK 1.6 이상 버 전 kill -3 PID > threadDump.log 2>&1 다음은 상술 한 명령 의 몇 가지 관건 적 인 매개 변수의 의 미 를 간단하게 소개 한다.
ps ：
-m 。
-p PID， 。
-o 。
unic ：
-c ，
sort ：
-n
-r ， ，
jstack ：
-l long listing. Prints additional information about locks， ，
-m to print both java and native frames (mixed mode), Java ， C/C++ （ Native ）
kill ：
-signal ， ：
-3 ， ；
-9 ， ；
-15 ， 、 ， ， -TERM
참조 링크
좋은 웹페이지 즐겨찾기
