Gần 9 năm trước Cloudflare là một công ty nhỏ và tôi không làm việc cho nó mà chỉ là khách hàng. Một tháng sau khi ra mắt Cloudflare, tôi nhận được thông báo rằng trang web của tôi DNS dường như không hoạt động. Cloudflare đã thực hiện một thay đổi đối với và có một DNS bị hỏng.
Tôi ngay lập tức viết thư cho Matthew Prince với tiêu đề “DNS của tôi ở đâu?” và anh ấy đã gửi lại một câu trả lời dài chứa đầy các chi tiết kỹ thuật (), tôi đã trả lời:
Từ: John Graham-Cumming
Ngày: 7 tháng 2010 năm 9, 14:XNUMX
Chủ đề: Re: DNS của tôi ở đâu?
Kính gửi: Hoàng tử MatthewBáo cáo tuyệt vời, cảm ơn. Tôi chắc chắn sẽ gọi nếu có vấn đề. Có lẽ bạn nên viết một bài về vấn đề này sau khi đã thu thập tất cả thông tin kỹ thuật. Tôi nghĩ mọi người sẽ thích một câu chuyện cởi mở và trung thực. Đặc biệt nếu bạn đính kèm biểu đồ vào đó để hiển thị lưu lượng truy cập đã tăng như thế nào kể từ khi ra mắt.
Tôi có khả năng giám sát tốt trên trang web của mình và tôi nhận được SMS về mọi lỗi. Giám sát cho thấy sự cố xảy ra từ 13:03:07 đến 14:04:12. Các bài kiểm tra được thực hiện cứ năm phút một lần.
Tôi chắc chắn bạn sẽ tìm ra nó. Bạn có chắc là bạn không cần người của riêng mình ở Châu Âu không? 🙂
Và anh ấy trả lời:
Từ: Hoàng tử Matthew
Ngày: 7 tháng 2010 năm 9, 57:XNUMX
Chủ đề: Re: DNS của tôi ở đâu?
Kính gửi: John Graham-CummingCảm ơn. Chúng tôi đã trả lời tất cả những người đã viết. Bây giờ tôi đang trên đường đến văn phòng và chúng tôi sẽ viết gì đó trên blog hoặc ghim một bài đăng chính thức lên bảng thông báo của chúng tôi. Tôi hoàn toàn đồng ý, sự trung thực là tất cả.
Bây giờ Cloudflare là một công ty thực sự lớn, tôi làm việc cho nó và bây giờ tôi phải viết một cách cởi mở về sai lầm của chúng tôi, hậu quả của nó và hành động của chúng tôi.
Sự kiện ngày 2 tháng XNUMX
Vào ngày 2 tháng XNUMX, chúng tôi đã triển khai quy tắc mới trong Quy tắc được quản lý dành cho WAF. trên mọi lõi bộ xử lý xử lý lưu lượng HTTP/HTTPS trên mạng Cloudflare trên toàn thế giới. Chúng tôi không ngừng cải tiến các quy tắc được quản lý cho WAF để ứng phó với các lỗ hổng và mối đe dọa mới. Chẳng hạn, vào tháng Năm, chúng tôi vội vã để bảo vệ khỏi lỗ hổng nghiêm trọng trong SharePoint. Toàn bộ mục đích của WAF của chúng tôi là khả năng triển khai các quy tắc một cách nhanh chóng và toàn cầu.
Thật không may, bản cập nhật thứ Năm tuần trước có chứa một biểu thức chính quy làm lãng phí quá nhiều tài nguyên CPU HTTP/HTTPS khi quay lui. Kết quả là các chức năng proxy, CDN và WAF cốt lõi của chúng tôi bị ảnh hưởng. Biểu đồ cho thấy tài nguyên bộ xử lý để phục vụ lưu lượng HTTP/HTTPS đạt gần như 100% trên các máy chủ trong mạng của chúng tôi.
Mức sử dụng CPU tại một thời điểm hiện diện trong khi xảy ra sự cố
Kết quả là khách hàng của chúng tôi (và khách hàng của khách hàng của chúng tôi) gặp phải trang lỗi 502 trong miền Cloudflare. Lỗi 502 được tạo ra bởi các máy chủ web ngoại vi của Cloudflare vẫn còn lõi trống nhưng không thể giao tiếp với các quy trình xử lý lưu lượng HTTP/HTTPS.
Chúng tôi biết điều này đã gây ra bao nhiêu bất tiện cho khách hàng của chúng tôi. Chúng tôi vô cùng xấu hổ. Và thất bại này đã khiến chúng tôi không thể giải quyết sự việc một cách hiệu quả.
Nếu bạn là một trong những khách hàng này, chắc chắn bạn sẽ sợ hãi, tức giận và khó chịu. Hơn nữa, chúng tôi chưa có . Mức tiêu thụ CPU cao là do một quy tắc WAF có biểu thức chính quy được diễn đạt kém dẫn đến việc quay lui quá mức. Đây là biểu hiện tội lỗi: (?:(?:"|'|]|}||d|(?:nan|infinity|true|false|null|undefined|symbol|math)|`|-|+)+[)]*;?((?:s|-|~|!|{}||||+)*.*(?:.*=.*)))
Mặc dù điều này thú vị theo đúng nghĩa của nó (và tôi sẽ nói chi tiết hơn về nó bên dưới), nhưng dịch vụ Cloudflare đã ngừng hoạt động trong 27 phút không chỉ vì biểu thức chính quy không tốt. Chúng tôi phải mất một thời gian mới mô tả được chuỗi sự kiện dẫn đến thất bại nên phản hồi chậm. Ở cuối bài đăng, tôi sẽ mô tả việc quay lui bằng biểu thức chính quy và cho bạn biết phải làm gì với nó.
Chuyện gì đã xảy ra
Hãy bắt đầu theo thứ tự. Tất cả thời gian ở đây đều tính bằng UTC.
Vào lúc 13:42 chiều, một kỹ sư của nhóm tường lửa đã thực hiện một thay đổi nhỏ đối với quy tắc phát hiện sử dụng quy trình tự động. Theo đó, một phiếu yêu cầu thay đổi đã được tạo. Chúng tôi quản lý các vé như vậy thông qua Jira (ảnh chụp màn hình bên dưới).
Sau 3 phút, trang đầu tiên của PagerDuty xuất hiện, báo cáo sự cố với WAF. Đây là một thử nghiệm tổng hợp nhằm kiểm tra chức năng của WAF (chúng tôi có hàng trăm WAF) bên ngoài Cloudflare để theo dõi hoạt động bình thường. Ngay sau đó là các trang cảnh báo về việc các thử nghiệm dịch vụ đầu cuối khác của Cloudflare không thành công, các vấn đề về lưu lượng truy cập toàn cầu, lỗi 502 phổ biến và rất nhiều báo cáo từ Điểm hiện diện (PoP) của chúng tôi ở các thành phố trên khắp thế giới cho thấy sự thiếu hụt. của tài nguyên CPU.
Tôi đã nhận được một số cảnh báo như vậy, xông ra khỏi cuộc họp và đang trên đường đến bàn thì người đứng đầu bộ phận phát triển giải pháp của chúng tôi nói rằng chúng tôi đã mất 80% lưu lượng truy cập. Tôi chạy đến gặp các kỹ sư SRE của chúng tôi, những người đang giải quyết vấn đề. Lúc đầu chúng tôi nghĩ đó là một kiểu tấn công không xác định nào đó.
Các kỹ sư của Cloudflare SRE sống rải rác trên khắp thế giới và theo dõi tình hình suốt ngày đêm. Thông thường, những cảnh báo này thông báo cho bạn về các vấn đề cục bộ cụ thể có phạm vi giới hạn, được theo dõi trên bảng thông tin nội bộ và được giải quyết nhiều lần mỗi ngày. Nhưng những trang và thông báo này cho thấy điều gì đó thực sự nghiêm trọng và các kỹ sư của SRE đã ngay lập tức tuyên bố mức độ nghiêm trọng P0 và liên hệ với các kỹ sư quản lý và hệ thống.
Vào lúc đó, các kỹ sư London của chúng tôi đang nghe bài giảng ở hội trường chính. Bài giảng phải gián đoạn, mọi người tập trung trong một phòng họp lớn và nhiều chuyên gia khác được gọi đến. Đây không phải là vấn đề điển hình mà SRE có thể tự giải quyết. Điều cấp thiết là phải có sự tham gia của các chuyên gia phù hợp.
Vào lúc 14 giờ, chúng tôi xác định rằng vấn đề là do WAF và không có cuộc tấn công nào. Nhóm hiệu suất đã lấy dữ liệu CPU và rõ ràng là WAF phải chịu trách nhiệm. Một nhân viên khác đã xác nhận lý thuyết này bằng cách sử dụng strace. Một người khác nhìn thấy trong nhật ký rằng có vấn đề với WAF. Vào lúc 00:14 chiều, toàn bộ nhóm đã đến gặp tôi khi được đề xuất sử dụng tính năng tiêu diệt toàn cầu, một cơ chế được tích hợp trong Cloudflare để tắt một thành phần trên toàn thế giới.
Cách chúng tôi thực hiện tiêu diệt toàn cầu cho WAF lại là một câu chuyện khác. Nó không đơn giản như vậy. Chúng tôi sử dụng sản phẩm của chính mình và vì dịch vụ của chúng tôi không hoạt động, chúng tôi không thể xác thực và đăng nhập vào bảng điều khiển nội bộ (khi mọi thứ đã được khắc phục, chúng tôi được biết rằng một số thành viên trong nhóm đã mất quyền truy cập do tính năng bảo mật vô hiệu hóa thông tin đăng nhập nếu bảng điều khiển nội bộ không được sử dụng cho một thời gian dài).
Và chúng tôi không thể truy cập các dịch vụ nội bộ của mình, như Jira hoặc hệ thống xây dựng. Chúng tôi cần một cơ chế giải quyết vấn đề mà chúng tôi không thường xuyên sử dụng (điều này cũng cần phải được giải quyết). Cuối cùng, một kỹ sư đã vô hiệu hóa được WAF lúc 14:07 và vào lúc 14:09, lưu lượng truy cập và mức CPU đã trở lại bình thường ở mọi nơi. Các cơ chế bảo vệ còn lại của Cloudflare hoạt động như bình thường.
Sau đó, chúng tôi bắt đầu khôi phục WAF. Tình huống không bình thường nên chúng tôi đã tiến hành các thử nghiệm tiêu cực (tự hỏi liệu thay đổi có thực sự là vấn đề hay không) và thử nghiệm tích cực (đảm bảo việc khôi phục có hiệu quả) ở một thành phố sử dụng lưu lượng truy cập riêng biệt, chuyển khách hàng trả tiền từ đó.
Vào lúc 14:52, chúng tôi tin rằng chúng tôi đã hiểu lý do và đã sửa lỗi, đồng thời kích hoạt lại WAF.
Cloudflare hoạt động như thế nào
Cloudflare có một đội ngũ kỹ sư chuyên quản lý các quy tắc cho WAF. Họ cố gắng cải thiện tỷ lệ phát hiện, giảm kết quả dương tính giả và nhanh chóng ứng phó với các mối đe dọa mới khi chúng xuất hiện. Trong 60 ngày qua, đã có 476 yêu cầu thay đổi được xử lý đối với các quy tắc được quản lý cho WAF (trung bình cứ 3 giờ lại có một yêu cầu).
Thay đổi cụ thể này cần được triển khai ở chế độ mô phỏng, trong đó lưu lượng khách hàng thực đi qua quy tắc nhưng không có gì bị chặn. Chúng tôi sử dụng chế độ này để kiểm tra tính hiệu quả của các quy tắc và đo lường tỷ lệ dương tính giả và âm tính giả. Nhưng ngay cả trong chế độ mô phỏng, các quy tắc thực sự phải được thực thi và trong trường hợp này quy tắc chứa một biểu thức chính quy tiêu tốn quá nhiều tài nguyên bộ xử lý.
Như bạn có thể thấy từ yêu cầu thay đổi ở trên, chúng tôi có kế hoạch triển khai, kế hoạch khôi phục và liên kết đến quy trình vận hành tiêu chuẩn nội bộ (SOP) cho loại hình triển khai này. SOP để thay đổi quy tắc cho phép nó được xuất bản trên toàn cầu. Trên thực tế, tại Cloudflare, mọi thứ được thực hiện hoàn toàn khác và SOP quy định rằng trước tiên chúng tôi gửi phần mềm để thử nghiệm và sử dụng nội bộ tới điểm hiện diện nội bộ (PoP) (mà nhân viên của chúng tôi sử dụng), sau đó đến một số ít khách hàng ở một địa điểm biệt lập, sau đó đến một số lượng lớn khách hàng và chỉ sau đó đến toàn thế giới.
Đây là những gì nó trông giống như. Chúng tôi sử dụng git nội bộ thông qua BitBucket. Các kỹ sư thực hiện các thay đổi sẽ gửi mã được xây dựng cho TeamCity và khi quá trình xây dựng hoàn tất, người đánh giá sẽ được chỉ định. Sau khi yêu cầu kéo được phê duyệt, mã sẽ được tập hợp và một loạt thử nghiệm sẽ được chạy (một lần nữa).
Nếu quá trình xây dựng và kiểm tra hoàn tất thành công, yêu cầu thay đổi sẽ được tạo trong Jira và người quản lý hoặc lãnh đạo phù hợp phải phê duyệt thay đổi. Sau khi được phê duyệt, việc triển khai sẽ diễn ra vào cái gọi là “đội quân PoP”: DOG, PIG và (chó, lợn và chim hoàng yến).
DOG PoP là Cloudflare PoP (giống như mọi thành phố khác của chúng tôi) chỉ được sử dụng bởi nhân viên của Cloudflare. PoP để sử dụng nội bộ cho phép bạn nắm bắt các vấn đề trước khi lưu lượng truy cập của khách hàng bắt đầu chảy vào giải pháp. Thứ hữu ích.
Nếu kiểm tra DOG thành công, mã sẽ chuyển sang giai đoạn PIG (chuột lang). Đây là Cloudflare PoP, nơi một lượng nhỏ lưu lượng truy cập miễn phí của khách hàng chảy qua mã mới.
Nếu mọi việc đều ổn, mã sẽ được chuyển vào Canary. Chúng tôi có ba Canary PoP ở những nơi khác nhau trên thế giới. Trong đó, lưu lượng truy cập của khách hàng trả phí và miễn phí sẽ đi qua mã mới và đây là lần kiểm tra lỗi cuối cùng.
Quy trình phát hành phần mềm tại Cloudflare
Nếu mã ở Canary ổn, chúng tôi sẽ phát hành nó. Đi qua tất cả các giai đoạn - CHÓ, LỢN, Canary, cả thế giới - mất vài giờ hoặc vài ngày, tùy thuộc vào việc thay đổi mã. Do tính đa dạng của mạng và khách hàng của Cloudflare, chúng tôi đã kiểm tra mã kỹ lưỡng trước khi phát hành mã đó trên toàn cầu cho tất cả khách hàng. Nhưng WAF không tuân thủ cụ thể quy trình này vì các mối đe dọa cần được ứng phó nhanh chóng.
Các mối đe dọa WAF
Trong vài năm qua, các mối đe dọa trong các ứng dụng phổ biến đã gia tăng đáng kể. Điều này là do sự sẵn có lớn hơn của các công cụ kiểm thử phần mềm. Ví dụ: gần đây chúng tôi đã viết về ).
Nguồn:
Rất thường xuyên, một bằng chứng về khái niệm được tạo và xuất bản ngay lập tức trên Github để các nhóm duy trì ứng dụng có thể nhanh chóng kiểm tra nó và đảm bảo rằng nó được bảo mật đầy đủ. Vì vậy, Cloudflare cần có khả năng ứng phó với các cuộc tấn công mới nhanh nhất có thể để khách hàng có cơ hội sửa chữa phần mềm của mình.
Một ví dụ tuyệt vời về phản ứng nhanh của Cloudflare là việc triển khai các biện pháp bảo vệ lỗ hổng SharePoint vào tháng XNUMX (). Gần như ngay lập tức sau khi thông báo được đưa ra, chúng tôi nhận thấy có rất nhiều nỗ lực nhằm khai thác lỗ hổng trong bản cài đặt SharePoint của khách hàng. Người của chúng tôi liên tục theo dõi các mối đe dọa mới và viết ra các quy tắc để bảo vệ khách hàng của mình.
Quy tắc gây ra sự cố hôm thứ Năm được cho là để bảo vệ chống lại tập lệnh chéo trang (XSS). Những cuộc tấn công như vậy cũng trở nên thường xuyên hơn nhiều trong những năm gần đây.
Nguồn:
Quy trình chuẩn để thay đổi quy tắc được quản lý cho WAF là tiến hành thử nghiệm tích hợp (CI) liên tục trước khi triển khai toàn cầu. Thứ Năm tuần trước chúng tôi đã làm điều này và đưa ra các quy tắc. Vào lúc 13:31 chiều, một kỹ sư đã gửi yêu cầu kéo đã được phê duyệt kèm theo một thay đổi.
Lúc 13:37 TeamCity thu thập các quy tắc, chạy thử nghiệm và cho phép. Bộ kiểm tra WAF kiểm tra chức năng cốt lõi của WAF và bao gồm một số lượng lớn các bài kiểm tra đơn vị cho từng chức năng. Sau khi kiểm tra đơn vị, chúng tôi đã kiểm tra các quy tắc cho WAF bằng cách sử dụng một số lượng lớn yêu cầu HTTP. Yêu cầu HTTP kiểm tra yêu cầu nào sẽ bị WAF chặn (để chặn cuộc tấn công) và yêu cầu nào có thể được cho phép đi qua (để không chặn mọi thứ và tránh kết quả dương tính giả). Nhưng chúng tôi đã không kiểm tra mức sử dụng CPU quá mức và việc kiểm tra nhật ký của các bản dựng WAF trước đó cho thấy thời gian thực hiện kiểm tra quy tắc không tăng và khó có thể nghi ngờ rằng sẽ không có đủ tài nguyên.
Các thử nghiệm đã vượt qua và TeamCity bắt đầu tự động triển khai thay đổi lúc 13:42 chiều.
Thủy ngân
Các quy tắc WAF tập trung vào việc khắc phục mối đe dọa ngay lập tức, vì vậy chúng tôi triển khai chúng bằng cách sử dụng kho lưu trữ khóa-giá trị phân tán của Quicksilver, giúp phổ biến các thay đổi trên toàn cầu chỉ trong vài giây. Tất cả khách hàng của chúng tôi đều sử dụng công nghệ này khi họ thay đổi cấu hình trong bảng điều khiển hoặc thông qua API và nhờ đó mà chúng tôi phản hồi các thay đổi với tốc độ cực nhanh.
Chúng ta chưa nói nhiều về Quicksilver. Trước đây chúng tôi đã sử dụng là một cửa hàng khóa-giá trị được phân phối trên toàn cầu, nhưng có vấn đề về vận hành với nó và chúng tôi đã xây dựng cửa hàng của riêng mình, nhân rộng ở hơn 180 thành phố. Hiện tại, chúng tôi sử dụng Quicksilver để đẩy các thay đổi cấu hình tới máy khách, cập nhật quy tắc WAF và phân phối mã JavaScript do máy khách viết cho Cloudflare Workers.
Chỉ mất vài giây từ việc nhấp vào nút trên trang tổng quan hoặc gọi API để thực hiện thay đổi cấu hình trên toàn thế giới. Khách hàng yêu thích tốc độ thiết lập này. Và Công nhân mang lại cho họ khả năng triển khai phần mềm toàn cầu gần như ngay lập tức. Trung bình, Quicksilver truyền tải khoảng 350 thay đổi mỗi giây.
Và Quicksilver rất nhanh. Trung bình, chúng tôi đã đạt được phân vị thứ 99 là 2,29 giây để truyền bá các thay đổi đến mọi máy tính trên toàn thế giới. Tốc độ thường là một điều tốt. Rốt cuộc, khi bạn kích hoạt một chức năng hoặc xóa bộ nhớ đệm, nó sẽ diễn ra gần như ngay lập tức và ở mọi nơi. Việc gửi mã thông qua Cloudflare Workers diễn ra ở cùng tốc độ. Cloudflare hứa hẹn với khách hàng những cập nhật nhanh chóng vào đúng thời điểm.
Nhưng trong trường hợp này, tốc độ đã chơi một trò đùa độc ác với chúng tôi và các quy tắc thay đổi ở mọi nơi chỉ trong vài giây. Bạn có thể nhận thấy rằng mã WAF sử dụng Lua. Cloudflare sử dụng Lua rộng rãi trong sản xuất và chi tiết chúng tôi . Sử dụng Lua WAF nội bộ và áp dụng quay lui để khớp. Nó không có cơ chế bảo vệ khỏi những biểu hiện vượt quá tầm kiểm soát. Dưới đây tôi sẽ nói nhiều hơn về điều này và những gì chúng tôi đang làm về nó.
Trước khi triển khai các quy tắc, mọi thứ đều diễn ra suôn sẻ: yêu cầu kéo được tạo và phê duyệt, quy trình CI/CD được thu thập và kiểm tra mã, yêu cầu thay đổi được gửi theo SOP quản lý việc triển khai và khôi phục, và quá trình triển khai đã hoàn tất.
Quy trình triển khai WAF của Cloudflare
Đã xảy ra sự cố
Như tôi đã nói, chúng tôi triển khai hàng tá quy tắc WAF mới mỗi tuần và chúng tôi có sẵn nhiều hệ thống để bảo vệ khỏi những hậu quả tiêu cực của việc triển khai đó. Và khi có sự cố xảy ra, nó thường là sự kết hợp của nhiều tình huống cùng một lúc. Tất nhiên, nếu bạn chỉ tìm thấy một lý do thì điều này khiến bạn yên tâm nhưng không phải lúc nào cũng đúng. Đây là những lý do dẫn đến sự thất bại của dịch vụ HTTP/HTTPS của chúng tôi.
- Một kỹ sư đã viết một biểu thức chính quy có thể gây ra quá nhiều .
- Một tính năng có thể ngăn biểu thức chính quy lãng phí quá nhiều CPU đã bị loại bỏ do nhầm lẫn trong quá trình tái cấu trúc WAF vài tuần trước đó—việc tái cấu trúc là cần thiết để làm cho WAF tiêu thụ ít tài nguyên hơn.
- Công cụ biểu thức chính quy không có sự đảm bảo về độ phức tạp.
- Bộ thử nghiệm không thể phát hiện mức tiêu thụ CPU quá mức.
- SOP cho phép triển khai các thay đổi quy tắc không khẩn cấp trên toàn cầu mà không cần quy trình gồm nhiều bước.
- Kế hoạch khôi phục yêu cầu chạy bản dựng WAF đầy đủ hai lần, việc này mất nhiều thời gian.
- Cảnh báo đầu tiên về vấn đề giao thông toàn cầu được đưa ra quá muộn.
- Chúng tôi mất một lúc để cập nhật trang trạng thái.
- Chúng tôi gặp sự cố khi truy cập hệ thống do trục trặc và quy trình bỏ qua không được thiết lập tốt.
- Các kỹ sư của SRE mất quyền truy cập vào một số hệ thống vì thông tin đăng nhập của họ đã hết hạn vì lý do bảo mật.
- Khách hàng của chúng tôi không có quyền truy cập vào bảng điều khiển hoặc API của Cloudflare vì họ đi qua khu vực Cloudflare.
Điều gì đã thay đổi kể từ thứ Năm tuần trước
Đầu tiên, chúng tôi đã dừng hoàn toàn mọi công việc phát hành cho WAF và đang thực hiện những việc sau:
- Chúng tôi đang giới thiệu lại tính năng bảo vệ việc lạm dụng CPU mà chúng tôi đã loại bỏ. (Sẵn sàng)
- Kiểm tra thủ công tất cả 3868 quy tắc trong các quy tắc được quản lý để WAF tìm và sửa các trường hợp quay lui quá mức tiềm ẩn khác. (Xác minh hoàn tất)
- Chúng tôi bao gồm hồ sơ hiệu suất cho tất cả các quy tắc trong bộ kiểm tra. (Dự kiến: 19/XNUMX)
- Chuyển sang công cụ biểu thức chính quy hoặc - cả hai đều cung cấp đảm bảo thời gian chạy. (Dự kiến: 31/XNUMX)
- Chúng tôi đang viết lại SOP để triển khai các quy tắc theo từng giai đoạn, giống như các phần mềm khác trong Cloudflare, nhưng đồng thời có khả năng triển khai khẩn cấp trên toàn cầu nếu các cuộc tấn công đã bắt đầu.
- Chúng tôi đang phát triển khả năng xóa khẩn cấp bảng điều khiển và API của Cloudflare khỏi khu vực Cloudflare.
- Tự động cập nhật trang .
Về lâu dài, chúng tôi sẽ rời xa Lua WAF mà tôi đã viết cách đây vài năm. Di chuyển WAF tới . Bằng cách này, WAF sẽ nhanh hơn và nhận được mức độ bảo vệ bổ sung.
Kết luận
Thất bại này đã gây rắc rối cho chúng tôi và khách hàng của chúng tôi. Chúng tôi đã hành động nhanh chóng để khắc phục tình trạng này và hiện đang khắc phục các sai sót trong quy trình gây ra sự cố, cũng như tìm hiểu sâu hơn nữa để đề phòng các vấn đề tiềm ẩn với biểu thức chính quy trong tương lai khi chuyển sang công nghệ mới.
Chúng tôi rất xấu hổ về sự cố ngừng hoạt động này và xin lỗi khách hàng. Chúng tôi hy vọng những thay đổi này sẽ đảm bảo những điều tương tự sẽ không xảy ra nữa.
Ứng dụng. Quay lại biểu thức chính quy
Để hiểu cách biểu đạt:
(?:(?:"|'|]|}||d
(?:nan|infinity|true|false|null|undefined|symbol|math)|`|-
|+)+[)]*;?((?:s|-|~|!|{}||||+)*.*(?:.*=.*)))đã sử dụng hết tài nguyên CPU, bạn cần biết một chút về cách hoạt động của công cụ biểu thức chính quy tiêu chuẩn. Vấn đề ở đây là mẫu .*(?:.*=.*). (?: và tương ứng ) là một nhóm không bắt giữ (nghĩa là biểu thức trong ngoặc đơn được nhóm thành một biểu thức duy nhất).
Trong bối cảnh tiêu thụ CPU quá mức, mẫu này có thể được mô tả là .*.*=.*. Ở dạng này, mẫu trông có vẻ phức tạp không cần thiết. Nhưng quan trọng hơn, trong thế giới thực, các biểu thức (như các biểu thức phức tạp trong quy tắc WAF) yêu cầu công cụ khớp một đoạn theo sau bởi một đoạn khác có thể dẫn đến việc quay lui thảm khốc. Và đó là lý do tại sao.
Trong biểu thức chính quy . có nghĩa là bạn cần khớp một ký tự, .* - khớp XNUMX hoặc nhiều ký tự một cách "tham lam", nghĩa là bắt được tối đa các ký tự, sao cho .*.*=.* có nghĩa là khớp XNUMX hoặc nhiều ký tự, sau đó khớp XNUMX hoặc nhiều ký tự, tìm ký tự = bằng chữ, khớp XNUMX hoặc nhiều ký tự.
Chúng ta hãy đi vào dòng thử nghiệm x=x. Nó tương ứng với biểu thức .*.*=.*. .*.* trước dấu bằng khớp với dấu đầu tiên x (một trong những nhóm .* phù hợp với xvà ký tự thứ hai - XNUMX). .* sau = trận đấu cuối cùng x.
Sự so sánh này đòi hỏi 23 bước. Nhóm đầu tiên .* в .*.*=.* hành động tham lam và khớp toàn bộ chuỗi x=x. Động cơ chuyển sang nhóm tiếp theo .*. Chúng tôi không còn ký tự nào để khớp nữa nên nhóm thứ hai .* không khớp với ký tự nào (điều này được cho phép). Sau đó động cơ di chuyển đến biển báo =. Không còn ký hiệu nào nữa (nhóm đầu tiên .* đã sử dụng toàn bộ biểu thức x=x), không có sự so sánh nào xảy ra.
Và sau đó công cụ biểu thức chính quy quay lại từ đầu. Anh ấy chuyển sang nhóm đầu tiên .* và so sánh nó с x= (thay vì x=x), rồi vào nhóm thứ hai .*. Nhóm thứ hai .* được so sánh với thứ hai x, và chúng ta lại không còn ký tự nào nữa. Và khi động cơ đạt lại = в .*.*=.*, không có gì hoạt động. Và anh ấy lại quay lại.
Lần này nhóm .* vẫn phù hợp x=, nhưng nhóm thứ hai .* không còn nữa xvà không có ký tự nào. Động cơ đang cố gắng tìm một ký tự theo nghĩa đen = trong khuôn mẫu .*.*=.*, nhưng không xuất hiện (dù sao thì nhóm đầu tiên đã chiếm được rồi .*). Và anh ấy lại quay lại.
Lần này nhóm đầu tiên .* chỉ lấy x đầu tiên. Nhưng nhóm thứ hai .* “tham lam” bắt giữ =x. Bạn đã đoán được điều gì sẽ xảy ra chưa? Động cơ cố gắng khớp với nghĩa đen =, thất bại và thực hiện một lần quay lại khác.
Nhóm đầu tiên .* vẫn khớp với cái đầu tiên x. Thứ hai .* chỉ mất =. Tất nhiên, động cơ không thể phù hợp với nghĩa đen =, vì nhóm thứ hai đã làm điều này rồi .*. Và một lần nữa quay lại. Và chúng tôi đang cố gắng khớp một chuỗi gồm ba ký tự!
Kết quả là nhóm đầu tiên .* chỉ khớp với cái đầu tiên x, thứ hai .* - không có ký tự và công cụ cuối cùng khớp với nghĩa đen = trong biểu thức с = trong dòng. Tiếp theo là nhóm cuối cùng .* được so sánh với cái cuối cùng x.
23 bước chỉ dành cho x=x. Xem đoạn video ngắn về cách sử dụng Perl , cho biết các bước và quay lui diễn ra như thế nào.
Việc này đã có rất nhiều việc rồi, nhưng thay vào đó thì sao x=x chúng ta sẽ có x=xx? Đó là 33 bước. Và nếu x=xxx? 45. Mối quan hệ không tuyến tính. Biểu đồ thể hiện sự so sánh từ x=x để x=xxxxxxxxxxxxxxxxxxxx (20 x sau khi =). Nếu chúng ta có 20 x sau =, động cơ hoàn thành việc khớp trong 555 bước! (Hơn nữa, nếu chúng ta thua x= và chuỗi chỉ bao gồm 20 x, động cơ sẽ thực hiện 4067 bước để hiểu rằng không có kết quả trùng khớp).
Video này hiển thị tất cả các đoạn quay lại để so sánh x=xxxxxxxxxxxxxxxxxxxx:
Vấn đề là khi kích thước chuỗi tăng lên, thời gian khớp sẽ tăng siêu tuyến tính. Nhưng mọi thứ có thể còn tệ hơn nếu biểu thức chính quy bị sửa đổi một chút. Hãy nói rằng chúng tôi đã có .*.*=.*; (nghĩa là có một dấu chấm phẩy ở cuối mẫu). Ví dụ: để khớp với một biểu thức như foo=bar;.
Và ở đây việc quay lại sẽ là một thảm họa thực sự. Để so sánh x=x nó sẽ mất 90 bước chứ không phải 23. Và con số đó đang tăng lên nhanh chóng. Để so sánh x= và 20 x, cần 5353 bước. Đây là biểu đồ. Nhìn vào các giá trị trục Y so với biểu đồ trước đó.
Nếu bạn quan tâm, hãy xem tất cả 5353 bước khớp không thành công x=xxxxxxxxxxxxxxxxxxxx и .*.*=.*;
Bằng cách sử dụng kết hợp lười biếng thay vì kết hợp tham lam, mức độ quay lui có thể được kiểm soát. Nếu chúng ta thay đổi biểu thức ban đầu thành .*?.*?=.*?, để so sánh x=x nó sẽ mất 11 bước (không phải 23). Đối với x=xxxxxxxxxxxxxxxxxxxx... Tất cả vì ? sau khi .* yêu cầu công cụ khớp số lượng ký tự tối thiểu trước khi tiếp tục.
Nhưng ánh xạ lười biếng không giải quyết được hoàn toàn vấn đề quay lui. Nếu chúng ta thay thế ví dụ thảm khốc .*.*=.*; trên .*?.*?=.*?;, thời gian thực hiện sẽ giữ nguyên. x=x vẫn cần 555 bước và x= và 20 x - 5353.
Điều duy nhất có thể làm (ngoài việc viết lại hoàn toàn mẫu để có độ đặc hiệu cao hơn) là từ bỏ công cụ biểu thức chính quy với cơ chế quay lui của nó. Đây là những gì chúng tôi sẽ làm trong vài tuần tới.
Giải pháp cho vấn đề này đã được biết đến từ năm 1968, khi Kent Thompson viết một bài báo (“Phương pháp lập trình: Thuật toán tìm kiếm biểu thức chính quy”). Bài viết mô tả một cơ chế cho phép bạn chuyển đổi một biểu thức chính quy thành các máy trạng thái hữu hạn không xác định và sau khi thay đổi trạng thái trong các máy trạng thái hữu hạn không xác định, hãy sử dụng thuật toán có thời gian thực hiện phụ thuộc tuyến tính vào chuỗi khớp.
Phương pháp lập trình
Thuật toán tìm kiếm biểu thức chính quy
Ken Thompson
Phòng thí nghiệm điện thoại Bell, Inc., Murray Hill, New JerseyNó mô tả một phương pháp tìm kiếm một chuỗi ký tự cụ thể trong văn bản và thảo luận về việc triển khai phương pháp này ở dạng trình biên dịch. Trình biên dịch lấy biểu thức chính quy làm mã nguồn và tạo ra chương trình IBM 7094 làm mã đối tượng. Chương trình đối tượng nhận đầu vào dưới dạng văn bản tìm kiếm và phát ra tín hiệu mỗi khi một chuỗi văn bản khớp với một biểu thức chính quy nhất định. Bài viết cung cấp các ví dụ, vấn đề và giải pháp.
Thuật toán
Các thuật toán tìm kiếm trước đó dẫn đến việc quay lại nếu tìm kiếm thành công một phần không mang lại kết quả.Trong chế độ biên dịch, thuật toán không hoạt động với các ký hiệu. Nó chuyển hướng dẫn tới mã được biên dịch. Việc thực thi rất nhanh - sau khi chuyển dữ liệu lên đầu danh sách hiện tại, nó sẽ tự động tìm kiếm tất cả các ký tự liên tiếp có thể có trong biểu thức chính quy.
Thuật toán biên dịch và tìm kiếm được bao gồm trong trình soạn thảo văn bản chia sẻ thời gian dưới dạng tìm kiếm theo ngữ cảnh. Tất nhiên, đây không phải là ứng dụng duy nhất của thủ tục tìm kiếm như vậy. Ví dụ: một biến thể của thuật toán này được sử dụng làm tìm kiếm ký hiệu trong bảng trong trình biên dịch mã.
Giả định rằng người đọc đã quen thuộc với các biểu thức chính quy và ngôn ngữ lập trình máy tính IBM 7094.Trình biên dịch
Trình biên dịch bao gồm ba giai đoạn chạy song song. Giai đoạn đầu tiên là lọc cú pháp, giai đoạn này chỉ cho phép các biểu thức chính quy đúng về mặt cú pháp đi qua. Bước này cũng chèn toán tử "·" để khớp với các biểu thức chính quy. Ở bước thứ hai, biểu thức chính quy được chuyển đổi sang dạng hậu tố. Ở giai đoạn thứ ba, mã đối tượng được tạo. 2 giai đoạn đầu tiên là hiển nhiên và chúng tôi sẽ không tập trung vào chúng.
Bài viết của Thompson không nói về các máy trạng thái hữu hạn không xác định, nhưng nó giải thích rõ thuật toán thời gian tuyến tính và trình bày chương trình ALGOL-60 tạo mã hợp ngữ cho IBM 7094. Việc triển khai rất phức tạp nhưng ý tưởng lại rất đơn giản.
đường tìm kiếm hiện tại. Nó được biểu thị bằng biểu tượng ⊕ với một đầu vào và hai đầu ra.
Hình 1 cho thấy các chức năng của bước biên dịch thứ ba khi chuyển đổi một ví dụ về biểu thức chính quy. Ba ký tự đầu tiên trong ví dụ là a, b, c và mỗi ký tự tạo ra một mục nhập ngăn xếp S[i] và một trường NNODE.NNODE vào mã hiện có để tạo biểu thức chính quy thu được trong một mục ngăn xếp duy nhất (xem Hình 5)
Đây là giao diện của một biểu thức chính quy .*.*=.*, nếu bạn tưởng tượng nó như trong những bức ảnh trong bài viết của Thompson.
Trong bộ lễ phục. 0 có năm trạng thái bắt đầu từ 0 và 3 chu kỳ bắt đầu từ trạng thái 1, 2 và 3. Ba chu kỳ này tương ứng với ba chu kỳ .* trong một biểu thức chính quy. 3 hình bầu dục có dấu chấm tương ứng với một biểu tượng. Hình bầu dục có dấu hiệu = khớp với một ký tự chữ =. Trạng thái 4 là cuối cùng. Nếu chúng ta đạt được nó thì biểu thức chính quy sẽ khớp.
Để xem cách sử dụng sơ đồ trạng thái như vậy để khớp biểu thức chính quy .*.*=.*, chúng ta sẽ xem xét việc so khớp chuỗi x=x. Chương trình bắt đầu từ trạng thái 0, như trong Hình 1. XNUMX.
Để thuật toán này hoạt động, máy trạng thái phải ở nhiều trạng thái đồng thời. Một máy hữu hạn không xác định sẽ thực hiện đồng thời tất cả các chuyển đổi có thể có.
Trước khi có thời gian đọc dữ liệu đầu vào, nó sẽ chuyển sang cả hai trạng thái đầu tiên (1 và 2), như trong Hình 2. XNUMX.
Trong bộ lễ phục. 2 cho thấy điều gì xảy ra khi anh ta nhìn vào cái đầu tiên x в x=x. x có thể ánh xạ tới điểm trên cùng, đi từ trạng thái 1 và quay lại trạng thái 1. Hoặc x có thể ánh xạ tới điểm bên dưới, đi từ trạng thái 2 và quay lại trạng thái 2.
Sau khi khớp cái đầu tiên x в x=x chúng ta vẫn đang ở trạng thái 1 và 2. Chúng ta không thể đạt đến trạng thái 3 hoặc 4 vì chúng ta cần một ký tự chữ =.
Thuật toán sau đó xem xét = в x=x. Giống như x trước nó, nó có thể được so khớp với một trong hai vòng lặp trên cùng từ trạng thái 1 đến trạng thái 1 hoặc từ trạng thái 2 đến trạng thái 2, nhưng thuật toán có thể khớp với nghĩa đen = và chuyển từ trạng thái 2 sang trạng thái 3 (và ngay lập tức là 4). Điều này được thể hiện trong hình. 3.
Thuật toán sau đó chuyển sang thuật toán cuối cùng x в x=x. Từ trạng thái 1 và 2, có thể chuyển đổi tương tự trở lại trạng thái 1 và 2. Từ trạng thái 3 x có thể khớp với điểm bên phải và quay lại trạng thái 3.
Ở giai đoạn này, mỗi nhân vật x=x được xem xét và vì chúng tôi đã đạt đến trạng thái 4 nên biểu thức chính quy khớp với chuỗi đó. Mỗi ký tự được xử lý một lần nên thuật toán này tuyến tính theo độ dài của chuỗi đầu vào. Và không quay lại.
Rõ ràng, sau khi đạt đến trạng thái 4 (khi thuật toán đã khớp x=) toàn bộ biểu thức chính quy được khớp và thuật toán có thể kết thúc mà không cần xem xét đến nó x.
Thuật toán này phụ thuộc tuyến tính vào kích thước của chuỗi đầu vào.
Nguồn: www.habr.com