2년 2019월 XNUMX일 Cloudflare 중단에 대한 세부 정보

약 9년 전만 해도 Cloudflare는 아주 작은 회사였고 저는 거기서 일하지도 않았고 그저 고객일 뿐이었습니다. Cloudflare가 출시된 지 한 달 후, 내 웹사이트가 삭제되었다는 알림을 받았습니다. jgc.orgDNS가 작동하지 않는 것 같습니다. Cloudflare가 변경했습니다. 프로토콜 버퍼, DNS가 손상되었습니다.

나는 즉시 "내 DNS는 어디에 있습니까?"라는 제목으로 Matthew Prince에게 편지를 썼고 그는 길고 기술적인 답변을 보냈습니다.전체 서신을 여기에서 읽어보세요), 이에 내가 답했습니다:

보낸 사람: John Graham-Cumming
날짜: 7년 2010월 9일, 14:XNUMX
제목: Re: 내 DNS는 어디에 있나요?
받는 사람: 매튜 프린스

훌륭한 보고서 감사합니다. 문제가 생기면 꼭 전화드리겠습니다. 모든 기술적인 정보를 수집한 후에 이에 대한 글을 쓰는 것이 좋을 것 같습니다. 사람들은 솔직하고 공개적인 이야기를 좋아할 거라고 생각해요. 특히 출시 이후 트래픽이 어떻게 증가했는지 보여주는 그래프를 첨부한다면 더욱 그렇습니다.

저는 사이트를 잘 모니터링하고 있으며, 오류가 발생할 때마다 SMS를 받습니다. 모니터링 결과, 장애는 13:03:07부터 14:04:12까지 발생한 것으로 나타났습니다. 검사는 XNUMX분마다 실시됩니다.

당신은 다 알아낼 수 있을 거라고 확신해요. 유럽에 당신의 남자가 필요 없다고 확신해요? 🙂

그리고 그는 대답했다:

보낸 사람: Matthew Prince
날짜: 7년 2010월 9일, 57:XNUMX
제목: Re: 내 DNS는 어디에 있나요?
받는 사람: John Graham-Cumming

감사합니다. 우리는 편지를 쓴 모든 사람에게 답장했습니다. 저는 지금 사무실로 가는 길입니다. 블로그에 글을 쓰거나 게시판에 공식 게시물을 게시하겠습니다. 전적으로 동의합니다. 정직함이 무엇보다 중요합니다.

클라우드플레어는 정말 큰 회사이고, 저는 그곳에서 일하고 있습니다. 그리고 이제 저는 우리의 실수, 그에 따른 결과, 그리고 우리의 행동에 대해 공개적으로 글을 써야 합니다.

2월 XNUMX일의 이벤트

2월 XNUMX일, 우리는 WAF용 관리 규칙에 새로운 규칙을 배포했습니다. CPU 리소스가 부족했습니다 전 세계 Cloudflare 네트워크에서 HTTP/HTTPS 트래픽을 처리하는 모든 CPU 코어에서. 우리는 새로운 취약점과 위협에 대응하여 WAF에 대한 관리 규칙을 지속적으로 개선하고 있습니다. 예를 들어 5월에는 우리는 서두르며 규칙 추가SharePoint의 심각한 취약점으로부터 보호합니다. WAF의 핵심은 규칙을 신속하고 전 세계적으로 배포할 수 있는 기능입니다.

불행히도, 지난 목요일 업데이트에는 백트래킹에 HTTP/HTTPS CPU를 너무 많이 낭비하는 정규 표현식이 포함되어 있었습니다. 이로 인해 핵심 프록시, CDN 및 WAF 기능이 영향을 받았습니다. 그래프는 네트워크의 서버에서 HTTP/HTTPS 트래픽을 처리하는 데 사용되는 CPU 리소스가 거의 100%에 도달했음을 보여줍니다.

사고 발생 중 접속 지점 중 하나의 CPU 사용량

결과적으로, 당사 고객(및 당사 고객의 고객)은 Cloudflare 도메인에서 502 오류 페이지를 접하게 되었습니다. 502 오류는 Cloudflare의 프런트엔드 웹 서버에서 발생했는데, 이 서버에는 여전히 사용 가능한 코어가 있었지만 HTTP/HTTPS 트래픽을 처리하는 프로세스에 접속할 수 없었습니다.

우리는 이 사건으로 인해 고객 여러분께 얼마나 많은 불편을 끼쳐드렸는지 알고 있습니다. 우리는 정말 부끄럽습니다. 이러한 실패로 인해 우리는 사고를 효과적으로 처리할 수 없게 되었습니다.

만약 여러분이 그런 고객 중 한 명이었다면, 아마도 무서움, 분노, 불쾌감을 느꼈을 겁니다. 게다가 우리는 6년 동안 하나도 가지고 있지 않았어요 세계적 실패. CPU 사용량이 높은 이유는 제대로 구성되지 않은 정규 표현식을 사용하는 단일 WAF 규칙으로 인해 과도한 백트래킹이 발생했기 때문입니다. 죄책감을 나타내는 표현은 다음과 같습니다. (?:(?:"|'|]|}||d|(?:nan|infinity|true|false|null|undefined|symbol|math)|`|-|+)+[)]*;?((?:s|-|~|!|{}||||+)*.*(?:.*=.*)))

그 자체로 흥미로운 사실이지만(아래에서 더 자세히 설명하겠습니다) Cloudflare가 27분간 다운된 이유는 잘못된 정규 표현식 때문만은 아니었습니다. 실패에 이르기까지의 일련의 사건을 설명하는 데 시간이 꽤 걸렸기 때문에 대응이 느렸습니다. 글의 마지막 부분에서는 정규 표현식에서의 백트래킹에 대해 설명하고, 이를 어떻게 활용할지 말씀드리겠습니다.

무슨 일이 있었는지

순서대로 시작해 보죠. 여기의 모든 시간은 UTC 기준입니다.

오후 13시 42분, 방화벽 팀의 엔지니어가 탐지 규칙을 약간 변경했습니다. XSS 자동 프로세스를 사용합니다. 이에 따라 변경 요청 티켓이 생성되었습니다. 이러한 티켓은 Jira를 통해 관리합니다(아래 스크린샷 참조).

3분 이내에 첫 번째 PagerDuty 페이지가 나타나 WAF에 문제가 있다는 보고가 나왔습니다. 이는 Cloudflare 외부의 WAF(수백 개가 있음) 기능을 점검하여 제대로 작동하는지 확인하는 종합 테스트였습니다. 그 후 다른 엔드투엔드 Cloudflare 서비스 테스트 실패, 글로벌 트래픽 문제, 광범위한 502 오류, 전 세계 도시에 있는 PoP(Points of Presence)에서 CPU 병목 현상을 나타내는 수많은 보고에 대한 경고 페이지가 빠르게 이어졌습니다.

저는 이러한 알림을 몇 개 받고 회의장을 나와서 회의실로 가던 중 솔루션 책임자가 트래픽의 80%가 손실되었다고 말했습니다. 저는 이미 문제를 해결하기 위해 작업 중이었던 SRE 엔지니어에게 달려갔습니다. 처음에는 알려지지 않은 공격이라고 생각했습니다.

Cloudflare의 SRE 엔지니어는 전 세계에 위치하고 있으며 0시간 내내 상황을 모니터링합니다. 일반적으로 이러한 알림은 범위가 제한된 구체적이고 지역적인 문제를 알리고, 내부 대시보드에서 추적하며, 하루에 여러 번 해결됩니다. 그러나 이러한 페이지와 알림은 매우 심각한 문제를 나타냈고, SRE 엔지니어는 즉시 심각도 수준을 PXNUMX로 선언하고 경영진과 시스템 엔지니어에게 연락했습니다.

그 순간 런던의 엔지니어들은 대강당에서 강의를 듣고 있었습니다. 강의는 중단되어야 했고, 모두가 큰 회의실에 모였으며, 더 많은 전문가들이 불려왔습니다. 이는 SRE가 스스로 처리할 수 있는 일반적인 문제가 아니었습니다. 적합한 전문가를 긴급히 참여시키는 것이 필요했습니다.

14:00에 우리는 문제가 WAF에 있다는 것을 확인했고, 공격은 없었습니다. 성능 팀이 CPU 데이터를 뽑아본 결과, WAF가 원인이라는 사실이 분명해졌습니다. 또 다른 직원은 strace를 사용하여 이 이론을 확인했습니다. 다른 누군가가 로그에서 WAF에 문제가 있음을 확인했습니다. 오후 14시 02분에 전체 팀이 저에게 찾아와서 글로벌 킬을 사용하는 것이 좋겠다는 제안을 했습니다. 글로벌 킬은 Cloudflare에 내장된 메커니즘으로 전 세계에서 하나의 구성 요소를 비활성화합니다.

WAF를 전 세계적으로 성공적으로 운영한 것은 별개의 이야기입니다. 그렇게 간단한 일은 아닙니다. 저희는 저희만의 제품을 사용하고 있으며, 저희의 서비스는 Access 작동하지 않았고, 인증을 받지 못하고 내부 제어판에 로그인할 수 없었습니다(모든 것을 해결하고 나서야 내부 제어판을 장시간 사용하지 않으면 자격 증명을 비활성화하는 보안 기능으로 인해 일부 팀원이 액세스 권한을 잃었다는 사실을 알게 되었습니다).

Jira나 빌드 시스템 같은 내부 서비스에 접근할 수도 없었습니다. 우리가 자주 사용하지 않는 해결책이 필요했습니다(이것 역시 해결해야 할 것입니다). 마침내 한 엔지니어가 14:07에 WAF를 비활성화하는 데 성공했고, 14:09에는 모든 곳의 트래픽과 CPU 수준이 정상으로 돌아왔습니다. Cloudflare의 나머지 보안 메커니즘은 정상적으로 작동했습니다.

그런 다음 WAF를 복구하기 시작했습니다. 상황이 평소와 달랐기 때문에 우리는 별도의 트래픽을 사용하여 한 도시에서 부정적 테스트(이 변경 사항이 정말 문제인지 자문하는 것)와 긍정적 테스트(롤백이 제대로 작동하는지 확인하는 것)를 실행하고, 그곳에서 유료 고객을 이동시켰습니다.

14:52에 우리는 원인을 파악하고 수정 조치를 취한 후 WAF를 다시 활성화했습니다.

클라우드플레어 작동 방식

Cloudflare에는 WAF 관리 규칙을 전담하는 엔지니어 팀이 있습니다. 그들은 탐지율을 높이고, 거짓 양성 판정을 낮추고, 새로운 위협이 나타나면 신속히 대응하기 위해 노력합니다. 지난 60일 동안 WAF 관리 규칙에 대한 변경 요청 476개가 처리되었습니다(평균적으로 3시간마다 XNUMX개).

이 특정 변경 사항은 시뮬레이션 모드에서 배포되어야 하며, 실제 고객 트래픽은 규칙을 통과하지만 아무것도 차단되지 않습니다. 이 모드를 사용하면 규칙의 효과를 테스트하고 거짓 양성 및 거짓 음성의 비율을 측정할 수 있습니다. 하지만 시뮬레이션 모드에서도 규칙을 실제로 실행해야 하며, 이 경우 규칙에 CPU 리소스를 너무 많이 소모하는 정규 표현식이 포함되어 있었습니다.

위의 변경 요청에서 볼 수 있듯이 이러한 유형의 배포에는 배포 계획, 롤백 계획 및 내부 표준 운영 절차(SOP)에 대한 참조가 있습니다. 규칙을 변경하기 위한 SOP(표준운영절차)를 통해 전 세계적으로 공개할 수 있습니다. 사실, Cloudflare에서는 상황이 매우 다르게 설정되어 있으며 SOP에 따르면 먼저 소프트웨어를 테스트 및 내부 사용을 위해 직원이 사용하는 내부 접속 지점(PoP)으로 보낸 다음, 격리된 위치에 있는 소수의 고객에게 보낸 다음, 그런 다음 다수의 고객에게 보낸 후, 그런 다음에야 전 세계로 보냅니다.

이것이 그 모습입니다. 우리는 BitBucket을 통해 내부적으로 git을 사용합니다. 변경 작업을 진행하는 엔지니어는 TeamCity에서 빌드된 코드를 제출하고, 빌드가 통과되면 검토자가 할당됩니다. 풀 리퀘스트가 승인되면 코드가 빌드되고 일련의 테스트가 (다시) 실행됩니다.

빌드와 테스트가 성공적으로 완료되면 Jira에 변경 요청이 생성되고 해당 관리자 또는 리드가 변경 사항을 승인해야 합니다. 승인되면 배치는 소위 "PoP 동물원"인 DOG, PIG로 진행됩니다. 카나리아 (개, 돼지, 카나리아).

DOG PoP는 Cloudflare 직원만 사용하는 Cloudflare PoP(다른 도시와 마찬가지로)입니다. 내부용 PoP를 사용하면 고객 트래픽이 솔루션으로 유입되기 전에 문제를 포착할 수 있습니다. 유용한 정보.

DOG 테스트를 통과하면 코드는 PIG(기니피그) 단계로 이동합니다. 이는 소량의 무료 고객 트래픽이 새로운 코드를 통해 전달되는 Cloudflare PoP입니다.
모든 것이 잘되면 코드는 Canary에 푸시됩니다. 우리는 전 세계 여러 지역에 3개의 Canary PoP를 가지고 있습니다. 이 코드에서는 유료 및 무료 고객의 트래픽이 새로운 코드를 통과하며, 여기서 오류가 있는지 확인하는 최종 검사가 수행됩니다.

Cloudflare의 소프트웨어 릴리스 프로세스

Canary에서 코드가 문제없다면, 우리는 그것을 릴리스합니다. DOG, PIG, Canary, 전 세계 등 모든 단계를 거치는 데는 코드 변경에 따라 몇 시간에서 며칠이 걸립니다. Cloudflare는 다양한 네트워크와 고객을 보유하고 있기 때문에 전 세계 모든 고객에게 출시하기 전에 코드를 철저히 테스트합니다. 하지만 WAF는 위협에 신속히 대응해야 하기 때문에 이러한 프로세스를 특별히 따르지 않습니다.

WAF 위협
최근 몇 년 동안 일반적인 애플리케이션에서 위협이 크게 증가했습니다. 이는 소프트웨어 테스팅 도구의 가용성이 높아졌기 때문입니다. 예를 들어, 우리는 최근에 다음에 대해 썼습니다. 퍼징).

출처 : https://cvedetails.com/

개념 증명이 생성되어 즉시 Github에 게시되는 경우가 매우 많으므로, 애플리케이션을 유지 관리하는 팀이 이를 빠르게 테스트하고 보안이 적절히 유지되는지 확인할 수 있습니다. 따라서 Cloudflare는 고객이 소프트웨어에 패치를 적용할 수 있는 기회를 제공하기 위해 최대한 빨리 새로운 공격에 대응할 수 있어야 합니다.

Cloudflare의 신속한 대응에 대한 좋은 예는 5월에 SharePoint 취약성에 대한 보호 기능을 출시한 것입니다.여기 읽기). 공지 사항을 게시한 직후, 우리는 고객의 SharePoint 설치에서 해당 취약점을 악용하려는 시도가 엄청나게 많았다는 것을 발견했습니다. 우리 직원들은 끊임없이 새로운 위협을 모니터링하고 고객을 보호하기 위해 규칙을 작성합니다.

목요일에 문제를 일으킨 규칙은 XSS(교차 사이트 스크립팅)를 방지하기 위한 것이었습니다. 최근 몇 년 동안 이런 공격이 훨씬 더 빈번해졌습니다.

출처 : https://cvedetails.com/

WAF의 관리 규칙을 변경하기 위한 표준 절차는 글로벌 배포에 앞서 CI(지속적인 통합) 테스트를 수행하는 것입니다. 지난 목요일에 우리는 이를 실행하고 규칙을 발표했습니다. 오후 13시 31분에 한 엔지니어가 변경 사항을 담은 승인된 풀 리퀘스트를 제출했습니다.

13:37에 TeamCity는 규칙을 수집하고 테스트를 실행한 후 승인을 내렸습니다. WAF 테스트 모음은 WAF의 핵심 기능을 검사하며 개별 기능에 대한 다수의 단위 테스트로 구성되어 있습니다. 단위 테스트 후, 우리는 엄청난 수의 HTTP 요청을 통해 WAF 규칙을 테스트했습니다. HTTP 요청은 WAF에서 어떤 요청을 차단해야 하는지(공격을 가로채기 위해)와 어떤 요청을 허용해야 하는지(모든 것을 차단하고 거짓 긍정을 방지하기 위해) 확인합니다. 하지만 과도한 CPU 사용률에 대한 테스트는 하지 않았고, 이전 WAF 빌드의 로그를 살펴보면 규칙을 적용한 테스트 실행 시간이 증가하지 않았으며, 리소스가 충분하지 않을 것이라고 의심하기 어려웠습니다.

테스트가 통과되었고 TeamCity는 오후 13시 42분에 자동으로 변경 사항을 배포하기 시작했습니다.

수은

WAF 규칙은 위협을 즉시 해결하도록 설계되었으므로 Quicksilver의 분산 키-값 저장소를 사용하여 규칙을 배포하면 몇 초 만에 변경 사항이 전역으로 전파됩니다. 모든 고객은 대시보드나 API를 통해 구성을 변경할 때 이 기술을 사용하고 있으며, 이 기술 덕분에 당사는 번개처럼 빠른 속도로 변경 사항에 대응할 수 있습니다.

우리는 퀵실버에 대해 별로 이야기하지 않았습니다. 우리는 사용하곤 했어요 교토 타이쿤 전 세계에 분산된 키-값 저장소였지만 운영상의 문제가 있었기 때문에 180개 이상의 도시에 복제된 자체 저장소를 작성했습니다. 이제 Quicksilver를 사용하여 클라이언트 구성 변경 사항을 푸시하고, WAF 규칙을 업데이트하고, 클라이언트가 작성한 JavaScript를 Cloudflare Workers에 배포합니다.

대시보드에서 버튼을 클릭하거나 API를 호출하는 것부터 전 세계적으로 구성을 변경하는 데 걸리는 시간은 불과 몇 초입니다. 고객들은 이러한 설정 속도를 좋아했습니다. 그리고 Workers는 그들에게 거의 즉각적인 글로벌 소프트웨어 배포를 제공합니다. 평균적으로 Quicksilver는 초당 약 350개의 변경 사항을 전파합니다.

그리고 퀵실버는 매우 빠르게 작동합니다. 평균적으로 전 세계 모든 컴퓨터에 변경 사항이 전파되는 데 걸리는 99% 시간은 2,29초였습니다. 속도는 대개 좋은 것입니다. 결국, 어떤 기능을 켜거나 캐시를 지우면 그 일은 거의 즉시 모든 곳에서 일어납니다. Cloudflare Workers를 통한 코드 전송은 동일한 속도로 진행됩니다. Cloudflare는 고객에게 필요할 때 빠른 업데이트를 제공할 것을 약속합니다.

하지만 이번 경우, 속도는 우리에게 잔인한 장난을 쳤고, 몇 초 만에 모든 곳의 규칙이 바뀌었습니다. WAF 코드가 Lua를 사용한다는 것을 눈여겨보셨을 겁니다. Cloudflare는 프로덕션에서 Lua를 광범위하게 사용하고 세부 정보를 제공합니다. WAF의 Lua 우리 이미 논의. Lua WAF는 다음을 사용합니다. PCRE 내부에서 역추적을 사용하여 일치시킵니다. 통제 불능의 표현을 방지할 수 있는 메커니즘이 없습니다. 아래에서 이 문제와 이에 대한 우리의 대응 방안에 대해 더 자세히 설명하겠습니다.

규칙이 배포되기 전에는 모든 것이 순조롭게 진행되었습니다. 풀 리퀘스트가 생성되어 승인되었고, CI/CD 파이프라인이 코드를 빌드하고 테스트했으며, 배포 및 롤백을 규정하는 SOP에 따라 변경 요청이 제출되었고, 배포가 완료되었습니다.

Cloudflare WAF 배포 프로세스

무엇이 잘못 되었습니까?
제가 말씀드린 것처럼, 우리는 매주 수십 개의 새로운 WAF 규칙을 배포하고 이러한 배포의 부정적인 결과를 처리하기 위해 많은 보호 시스템을 갖추고 있습니다. 그리고 무엇인가 잘못될 때는 보통 여러가지 상황이 복합적으로 얽혀 발생합니다. 단 하나의 이유를 찾으면 확실히 안심이 되지만, 항상 현실과 일치하는 것은 아닙니다. HTTP/HTTPS 서비스가 실패하는 이유는 다음과 같습니다.

1. 엔지니어가 과도한 결과를 초래할 수 있는 정규 표현식을 작성했습니다. 후퇴하다.
2. 몇 주 전 WAF 리팩토링 중에 정규 표현식이 CPU를 너무 많이 사용하는 것을 방지할 수 있는 기능이 실수로 제거되었습니다. 이 리팩토링은 WAF가 리소스를 덜 소모하도록 하기 위해 필요했습니다.
3. 정규 표현식 엔진은 복잡성을 보장하지 않습니다.
4. 테스트 모음은 과도한 CPU 사용량을 감지하지 못했습니다.
5. SOP 절차를 사용하면 여러 단계의 과정 없이 긴급하지 않은 규칙 변경 사항을 전 세계에 배포할 수 있습니다.
6. 롤백 계획을 실행하려면 전체 WAF 빌드를 두 번 실행해야 하므로 시간이 많이 걸립니다.
7. 세계적 교통 문제에 대한 첫 번째 경고는 너무 늦게 나왔습니다.
8. 상태 페이지 업데이트가 느렸습니다.
9. 결함으로 인해 시스템에 접근하는 데 문제가 발생했으며 해결 절차가 제대로 개발되지 않았습니다.
10. 보안상의 이유로 SRE 엔지니어의 자격 증명이 만료되어 일부 시스템에 액세스할 수 없게 되었습니다.
11. 저희 고객은 Cloudflare 지역을 거치기 때문에 Cloudflare 대시보드나 API에 액세스할 수 없었습니다.

지난 목요일 이후로 무엇이 바뀌었나요?

첫째, WAF 릴리스 작업을 모두 완전히 중단했으며 다음 작업을 진행하고 있습니다.

1. 과도한 프로세서 리소스 소비를 방지하기 위해 제거했던 보호 기능을 다시 도입합니다. (준비가 된)
2. WAF의 관리 규칙에 있는 3868개 규칙을 모두 수동으로 검토하여 과도한 역추적의 다른 잠재적 사례를 찾아 수정합니다. (확인 완료)
3. 우리는 테스트 모음의 모든 규칙에 대해 성능 프로파일링을 포함했습니다. (예정: 19월 XNUMX일)
4. 정규 표현식 엔진으로 이동 re2 또는 녹 - 둘 다 실행 환경에서 보장을 제공합니다. (예상 : 31월 XNUMX일)
5. Cloudflare의 다른 소프트웨어처럼 단계적으로 규칙을 배포하기 위해 SOP를 다시 작성 중이지만, 공격이 이미 시작된 경우에는 비상 글로벌 배포를 수행할 수 있는 기능을 여전히 갖추고 있습니다.
6. 우리는 Cloudflare 지역에서 Cloudflare 대시보드와 API를 긴급하게 출시할 수 있는 역량을 개발하고 있습니다.
7. 페이지 새로 고침 자동화 클라우드플레어 상태.

장기적으로 저희는 몇 년 전에 제가 작성한 Lua WAF에서 벗어나고 있습니다. WAF를 다음으로 이동 중입니다. 새로운 방화벽 시스템. 이렇게 하면 WAF가 더 빨라지고 보호 수준도 한 단계 높아집니다.

결론

이번 서비스 중단으로 인해 저희와 저희 고객에게 문제가 발생했습니다. 저희는 상황을 해결하기 위해 신속히 대응했으며, 현재는 중단을 일으킨 프로세스의 결함을 해결하기 위해 노력하고 있으며, 새로운 기술로 이전하면서 정규 표현식과 관련하여 발생할 수 있는 향후 문제를 방지하기 위해 더욱 심층적으로 노력하고 있습니다.

이번 서비스 중단에 대해 진심으로 사과드리며, 고객 여러분께 사과드립니다. 이러한 변화를 통해 이런 일이 다시 일어나지 않기를 바랍니다.

애플리케이션. 정규 표현식 백트래킹

다음 표현을 이해하려면:

(?:(?:"|'|]|}||d
(?:nan|infinity|true|false|null|undefined|symbol|math)|`|-
|+)+[)]*;?((?:s|-|~|!|{}||||+)*.*(?:.*=.*)))

CPU 리소스를 모두 소모하므로 표준 정규 표현식 엔진의 작동 방식에 대해 조금 알아야 합니다. 여기서 문제는 패턴에 있습니다. .*(?:.*=.*). (?: 그리고 해당 ) — 이것은 캡처링 그룹이 아닙니다. (즉, 괄호 안의 표현식은 단일 표현식으로 그룹화됩니다.)

과도한 CPU 소모의 맥락에서 이 패턴은 다음과 같이 설명될 수 있습니다. .*.*=.*. 이 형태에서는 패턴이 지나치게 복잡해 보인다. 하지만 더 중요한 점은, 실제 세계에서는 WAF 규칙의 복잡한 표현식과 같이 엔진에 조각을 매칭한 다음 다른 조각을 매칭하도록 요청하는 표현식은 치명적인 역추적을 초래할 수 있다는 것입니다. 그 이유는 다음과 같습니다.

정규 표현식에서 . 한 문자만 일치해야 한다는 의미입니다. .* — 가능한 한 많은 문자를 캡처하여 0개 이상의 문자를 탐욕적으로 일치시킵니다. .*.*=.* 0개 이상의 문자와 일치하고, 0개 이상의 문자와 일치하고, 리터럴 = 문자를 찾고, 0개 이상의 문자와 일치합니다.

테스트 문자열을 가져와 보자 x=x. 이는 표현과 일치합니다 .*.*=.*. .*.* 등호가 첫 번째에 대응하기 전에 x (그룹 중 하나 .* 일치 x, 두 번째는 0개의 문자). .* after = 마지막과 일치합니다 x.

이 비교에는 23단계가 필요합니다. 첫 번째 그룹 .* в .*.*=.* "탐욕스럽게" 행동하고 전체 줄과 일치합니다. x=x. 엔진이 다음 그룹으로 이동합니다. .*. 더 이상 일치시킬 문자가 없으므로 두 번째 그룹 .* 0개의 문자와 일치합니다(허용됩니다). 그런 다음 엔진이 표지판으로 이동합니다. =. 더 이상 심볼이 없습니다(첫 번째 그룹) .* 표현 전체를 사용했다 x=x), 일치가 발생하지 않습니다.

여기서 정규 표현식 엔진은 처음으로 돌아갑니다. 그는 첫 번째 그룹으로 이동합니다. .* 그리고 그것을 비교한다 с x= (대신 x=x), 그리고 두 번째 그룹을 맡습니다. .*. 두 번째 그룹 .* 두 번째와 비교된다 x, 그리고 우리는 더 이상 상징을 남기지 않았습니다. 그리고 엔진이 다시 속도에 도달하면 = в .*.*=.*, 아무것도 작동하지 않습니다. 그리고 그는 다시 후퇴하고 있습니다.

이번에는 그룹 .* 아직도 맞다 x=, 하지만 두 번째 그룹 .* 더 이상은 없어 x, 그리고 0개의 문자. 엔진이 문자 그대로의 문자를 찾으려고 합니다. = 패턴에서 .*.*=.*, 하지만 작동하지 않습니다. (결국 첫 번째 그룹은 이미 그것을 가져갔습니다. .*). 그리고 그는 다시 후퇴하고 있습니다.

이번에는 첫 번째 그룹 .* 첫 번째 x만 사용합니다. 하지만 두 번째 그룹은 .* "탐욕스럽게" 포착하다 =x. 무슨 일이 일어날지 이미 추측하셨나요? 엔진은 문자 그대로의 의미와 일치하려고 합니다. =, 실패하고 또 다시 후퇴합니다.

의 첫 번째 그룹 .* 아직도 첫 번째와 일치합니다 x. 두번째 .* 만 걸립니다 =. 물론 엔진은 문자 그대로의 의미와 일치할 수 없습니다. =, 두 번째 그룹은 이미 그것을 했기 때문입니다. .*. 그리고 또 후퇴합니다. 그리고 우리는 세 문자로 구성된 문자열을 일치시키려고 합니다!

그 결과, 첫 번째 그룹은 .* 첫 번째와만 일치합니다 x, 두번째 .* — 문자가 0개이고 엔진이 마침내 리터럴과 일치합니다. = 표현에서 с = 줄을 서서. 다음은 마지막 그룹입니다 .* 마지막 것과 비교된다 x.

23단계만 가능 x=x. Perl 사용에 대한 짧은 비디오를 시청하세요 정규 표현식::디버거이는 단계와 후퇴가 어떻게 발생하는지 보여줍니다.

이미 많은 작업이지만 대신 x=x 우리는 가질 것이다 x=xx? 33걸음이에요. 그리고 만약 x=xxx? 45. 종속성은 선형적이지 않습니다. 그래프는 다음의 비교를 보여줍니다. x=x 에 x=xxxxxxxxxxxxxxxxxxxx (20 x 후 =). 만약 우리가 20 x를 가지고 있다면 =엔진은 555단계로 매칭을 수행합니다! (그뿐만 아니라 우리가 졌다면 x= 그리고 그 라인은 단 20개로 구성되어 있습니다 x엔진은 일치하는 항목이 없음을 파악하기 위해 4067단계를 거칩니다).

이 비디오는 비교를 위해 모든 백트래킹을 보여줍니다. x=xxxxxxxxxxxxxxxxxxxx:

문제는 문자열 크기가 커질수록 매칭 시간이 초선형적으로 증가한다는 것입니다. 하지만 정규 표현식을 조금만 바꾸면 상황이 더 나빠질 수 있습니다. 우리가 가지고 있다고 가정해 보자 .*.*=.*; (즉, 패턴의 끝에 세미콜론이 문자 그대로 있었습니다). 예를 들어, 다음과 같은 표현식과 일치하려면 foo=bar;.

여기서 후퇴하면 정말 재앙이 될 것입니다. 비교를 위해 x=x 90걸음 대신 23걸음이 걸릴 것입니다. 그리고 그 숫자는 빠르게 늘어나고 있습니다. 비교하다 x= 및 20 x, 5353개의 단계가 필요합니다. 그래프는 다음과 같습니다. 축의 값을 살펴보세요 Y 이전 그래프와 비교해서.

관심이 있으시다면 실패한 매칭의 5353단계를 모두 확인해보세요. x=xxxxxxxxxxxxxxxxxxxx и .*.*=.*;

탐욕적 매칭보다는 게으른 매칭을 사용하면 백트래킹 범위를 제어할 수 있습니다. 원래 표현을 다음과 같이 바꾸면 .*?.*?=.*?, 비교를 위해 x=x 11걸음이 필요합니다(23걸음이 아닙니다). 에 관해서는 x=xxxxxxxxxxxxxxxxxxxx. 그것은 모두 때문에 ? 후 .* 엔진에 최소한의 문자 수를 일치시킨 후에 다음 단계로 넘어가라고 지시합니다.

하지만 "게으른" 비교로는 역추적 문제가 완전히 해결되지 않습니다. 우리가 재앙적인 예를 대체한다면 .*.*=.*; 에 .*?.*?=.*?;실행 시간은 동일하게 유지됩니다. x=x 여전히 555단계가 필요하지만 x= 및 20 x - 5353.

(패턴을 더 구체적으로 완전히 다시 작성하는 것 외에) 할 수 있는 유일한 일은 백트래킹 메커니즘을 갖춘 정규 표현식 엔진을 버리는 것입니다. 우리는 앞으로 몇 주 동안 이런 일을 할 것입니다.

이 문제에 대한 해결책은 1968년 Kent Thompson이 기사를 쓴 이후로 알려져 왔습니다. 프로그래밍 기술: 정규 표현식 검색 알고리즘 ("프로그래밍 방법: 정규 표현식 검색 알고리즘"). 이 논문에서는 정규 표현식을 비결정적 유한 오토마타로 변환하는 메커니즘과, 비결정적 유한 오토마타에서 상태가 변경된 후, 일치하는 문자열에 따라 실행 시간이 선형적으로 달라지는 알고리즘을 설명합니다.

프로그래밍 방법
정규 표현식 검색 알고리즘
켄 톰슨
벨 전화 연구소(Bell Telephone Laboratories, Inc.), 뉴저지 주 머레이힐

이 문서에서는 텍스트에서 특정 문자열을 찾는 방법을 설명하고 컴파일러 형태로 이 방법을 구현하는 방법에 대해 논의합니다. 컴파일러는 정규 표현식을 소스 코드로 받아서 IBM 7094 프로그램을 개체 코드로 생성합니다. 개체 프로그램은 검색할 텍스트 형태의 입력을 받고, 텍스트 문자열이 주어진 정규 표현식과 일치할 때마다 신호를 내보냅니다. 이 기사에서는 예제, 문제, 해결책을 제공합니다.

연산
이전 검색 알고리즘은 부분적으로 성공적인 검색을 수행해도 결과가 나오지 않으면 뒤로 되돌아가는 결과를 낳았습니다.

컴파일 모드에서는 알고리즘이 기호와 함께 작동하지 않습니다. 컴파일된 코드에 지침을 전달합니다. 실행은 매우 빠릅니다. 데이터를 현재 목록의 맨 위로 전달한 후 정규 표현식에서 연속된 모든 문자를 자동으로 검색합니다.
컴파일 및 검색 알고리즘은 상황별 검색으로 시분할 텍스트 편집기에 포함되어 있습니다. 물론, 이런 검색 절차가 적용된 사례는 이번이 처음은 아니다. 예를 들어, 이 알고리즘의 변형은 어셈블리에서 심볼 테이블 검색으로 사용됩니다.
독자는 정규 표현식과 IBM 7094 컴퓨터 프로그래밍 언어에 익숙하다고 가정합니다.

컴파일러
컴파일러는 병렬로 실행되는 세 단계로 구성됩니다. 첫 번째 단계는 구문 필터링으로, 구문적으로 올바른 정규 표현식만 통과시킵니다. 이 단계에서는 정규 표현식 일치를 위해 "·" 연산자도 삽입됩니다. 두 번째 단계에서는 정규 표현식이 접미사 형태로 변환됩니다. 세 번째 단계에서는 개체 코드가 생성됩니다. 처음 두 단계는 너무나 명확해서 여기서는 자세히 설명하지 않겠습니다.

톰슨의 논문은 비결정적 유한 오토마타를 논의하지 않지만 선형 시간 알고리즘을 잘 설명하고 IBM 60에 대한 어셈블리 언어 코드를 생성하는 ALGOL-7094 프로그램을 제공합니다. 구현은 까다롭지만 아이디어는 매우 간단합니다.

현재 검색 경로. 이는 한 개의 입력과 두 개의 출력을 가진 ⊕ 아이콘으로 표현됩니다.
그림 1은 예제 정규 표현식을 변환할 때 컴파일의 세 번째 단계의 기능을 보여줍니다. 이 예에서 처음 세 문자는 a, b, c이며 각각 스택 항목 S[i]와 필드 NNODE를 생성합니다.

기존 코드에 NNODE를 추가하여 단일 스택 항목에서 최종 정규 표현식을 생성합니다(그림 5 참조)

정규 표현식은 다음과 같습니다. .*.*=.*톰슨의 기사에 나온 사진과 같이 상상해 보세요.

그림 0에는 0에서 시작하는 3개의 상태와 1, 2, 3의 상태로부터 시작하는 XNUMX개의 사이클이 있습니다. 이 XNUMX개의 사이클은 XNUMX개의 .* 정규 표현식에서. 점이 있는 타원 3개는 하나의 기호에 대응합니다. 표지판이 있는 타원 = 리터럴 문자와 일치합니다 =. 상태 4가 최종입니다. 여기에 도달하면 정규 표현식이 일치한 것입니다.

이러한 상태 다이어그램이 정규 표현식 일치에 어떻게 사용될 수 있는지 알아보려면 .*.*=.*, 우리는 문자열 매칭을 살펴볼 것입니다 x=x. 그림 0에 표시된 대로, 프로그램은 상태 1에서 시작합니다.

이 알고리즘이 작동하려면 상태 머신이 동시에 여러 상태에 있어야 합니다. 비결정적 유한 상태 머신은 가능한 모든 전환을 동시에 수행합니다.

그림 1에서 보듯이 입력 데이터를 읽을 시간도 없이 첫 번째 상태(2과 2)로 전환됩니다.

그림 2에서 그가 첫 번째 것을 볼 때 무슨 일이 일어나는지 볼 수 있습니다. x в x=x. x 상태 1에서 상태 1로 돌아가서 최상위 지점과 일치할 수 있습니다. 또는 x 상태 2에서 상태 2로 돌아가면 아래 지점과 일치할 수 있습니다.

첫 번째를 비교한 후 x в x=x 우리는 여전히 상태 1과 2에 있습니다. 우리는 문자적 기호가 필요하기 때문에 상태 3이나 4에 도달할 수 없습니다. =.

그런 다음 알고리즘은 다음을 고려합니다. = в x=x. 이전 x와 마찬가지로 상태 1에서 상태 1로 또는 상태 2에서 상태 2로 전환되는 상위 두 사이클 중 하나와 일치할 수 있지만 알고리즘은 리터럴과 일치할 수 있습니다. = 그리고 상태 2에서 상태 3으로 이동합니다(그리고 즉시 상태 4로 이동합니다). 이는 그림 3에 나타나 있다.

그런 다음 알고리즘은 마지막 항목으로 이동합니다. x в x=x. 상태 1과 2에서 동일한 전환이 상태 1과 2로 다시 가능합니다. 상태 3에서 x 오른쪽의 지점과 일치하여 상태 3으로 돌아갈 수 있습니다.

이 단계에서는 각 기호 x=x 고려되었고, 상태 4에 도달했으므로 정규 표현식은 이 문자열과 일치합니다. 각 문자가 한 번씩 처리되므로 이 알고리즘은 입력 문자열의 길이에 따라 선형적입니다. 그리고 후퇴는 없습니다.

상태 4에 도달한 후(알고리즘이 일치한 경우)에는 분명합니다. x=) 전체 정규 표현식이 일치하고 알고리즘은 어떤 것도 고려하지 않고 종료될 수 있습니다. x.

이 알고리즘은 입력 문자열의 크기에 선형적으로 의존합니다.

출처 : habr.com