เอนจิน Regex ของ Rust ได้รับการสนับสนุน Lookbehind แบบเวลาเชิงเส้น ขจัดช่องโหว่ DoS

ทีมชุมชน BigGo
เอนจิน Regex ของ Rust ได้รับการสนับสนุน Lookbehind แบบเวลาเชิงเส้น ขจัดช่องโหว่ DoS

นักวิจัยได้ประสบความสำเร็จในการพัฒนา lookbehind assertions ในเอนจิน regex ของ Rust โดยยังคงรักษาการรับประกันประสิทธิภาพแบบเวลาเชิงเส้นที่สำคัญไว้ ความก้าวหน้านี้แก้ไขข้อจำกัดที่มีมานานซึ่งบังคับให้นักพัฒนาต้องเลือกระหว่างฟีเจอร์ regex ขั้นสูงกับการป้องกันการโจมตีแบบ denial-of-service

Rust regex crate มักให้ความสำคัญกับความปลอดภัยมากกว่าฟีเจอร์ โดยตัดการสนับสนุน lookbehind ออกไปโดยเจตนาเพื่อรักษาการรับประกันการทำงานแบบเวลาเชิงเส้น การออกแบบนี้ป้องกันสถานการณ์ catastrophic backtracking ที่อาจทำให้บริการทั้งหมดล่มได้ เช่นที่เกิดขึ้นกับ Cloudflare ในปี 2019 อย่างไรก็ตาม มันยังทำให้นักพัฒนาที่ต้องการเครื่องมือ pattern-matching อันทรงพลังเหล่านี้สำหรับงานประมวลผลข้อความที่ซับซ้อนรู้สึกหงุดหงิด

ทำลายอุปสรรคด้านประสิทธิภาพ

การพัฒนาใหม่ใช้เทคนิค finite automaton ที่เป็นนวัตกรรมเพื่อสนับสนุน unbounded lookbehinds โดยไม่เสียสละการรับประกันประสิทธิภาพของเอนจิน ไม่เหมือนกับเอนจิน regex แบบดั้งเดิมที่อาจแสดงความซับซ้อนของเวลาแบบเลขชี้กำลังกับรูปแบบบางอย่าง วิธีการนี้รับประกันว่าเวลาในการทำงานจะยังคงเป็นสัดส่วนกับความยาวของ input โดยไม่คำนึงถึงความซับซ้อนของรูปแบบ

ความก้าวหน้านี้มีความสำคัญเป็นพิเศษสำหรับแอปพลิเคชันที่ประมวลผล input ที่ไม่น่าเชื่อถือ เว็บเซิร์ฟเวอร์ ตัววิเคราะห์ log และเครื่องมือความปลอดภัยสามารถใช้รูปแบบ regex ที่ซับซ้อนได้โดยไม่ต้องกลัวว่าจะถูกครอบงำด้วยสตริงที่สร้างขึ้นอย่างมุ่งร้ายเพื่อกระตุ้น excessive backtracking

Finite automaton: แบบจำลองทางคณิตศาสตร์ที่ใช้ในวิทยาการคอมพิวเตอร์เพื่อจดจำรูปแบบในข้อความ ประกอบด้วยสถานะและการเปลี่ยนผ่านระหว่างสถานะเหล่านั้น

การเปรียบเทียบประสิทธิภาพ:

  • เอนจิ้น backtracking แบบดั้งเดิม: อาจแสดงความซับซ้อนของเวลาแบบเลขชี้กำลัง O(2^n)
  • Rust regex พร้อมการรับประกันเวลาเชิงเส้น: เวลาในการประมวลผล O(n) โดยไม่คำนึงถึงความซับซ้อนของรูปแบบ
  • การทดสอบ Snort-2 และ Snort-3 : เอนจิ้นเชิงเส้นทำงานเร็วกว่าโมดูล re ของ Python ถึง 70-80 เท่า
  • การทดสอบทั่วไป: Python re โดยทั่วไปเร็วกว่า 2-5 เท่าในกรณีที่ไม่ใช่ปัญหาร้ายแรง

การตอบสนองและการยอมรับจากชุมชน

การพัฒนานี้ได้สร้างความตื่นเต้นอย่างมากในชุมชน Rust โดยนักพัฒนาหลายคนแสดงความโล่งใจที่ในที่สุดก็ได้เข้าถึงฟังก์ชัน lookbehind ฟีเจอร์นี้แก้ไขข้อจำกัดในทางปฏิบัติที่บังคับให้ใช้วิธีแก้ปัญหาชั่วคราวหรือทางเลือกอื่นในแอปพลิเคชันในโลกจริงมานาน

จากมุมมองของผู้ใช้ สิ่งนี้มีคุณค่าอย่างมาก ช่างเป็นการปรับปรุงที่น่าทึ่ง โดยเฉพาะ unbounded ฉันหวังว่าสิ่งนี้จะได้เข้าสู่ RE2 และ go จริงๆ

การพัฒนานี้ขยายไปเกิน Rust เอง อาจเป็นประโยชน์ต่อระบบนิเวศที่กว้างขึ้นของเครื่องมือที่สร้างบน regex crate แอปพลิเคชันยอดนิยมอย่าง ripgrep และ Visual Studio Code ซึ่งพึ่งพาเอนจินนี้สำหรับการค้นหาข้อความ อาจได้รับการปรับปรุงเหล่านี้เมื่อการเปลี่ยนแปลงถูกรวมเข้าสู่รุ่นที่เสถียร

ผลกระทบต่อระบบนิเวศ:

  • ripgrep: เครื่องมือค้นหาข้อความที่ใช้ Rust regex engine
  • Visual Studio Code: ใช้ ripgrep สำหรับฟังก์ชันการค้นหาข้อความ
  • RE2 Engine: regex engine ของ Google ที่มีเป้าหมายด้านประสิทธิภาพคล้ายกัน
  • ภาษา Go: ใช้ RE2 engine อาจได้รับประโยชน์จากเทคนิคที่คล้ายกัน

ข้อจำกัดทางเทคนิคและการแลกเปลี่ยน

แม้ว่าการสนับสนุน lookbehind ใหม่จะเป็นก้าวสำคัญไปข้างหน้า แต่ก็มาพร้อมกับข้อจำกัดบางประการ การพัฒนานี้ไม่สนับสนุน capture groups ภายในนิพจน์ lookbehind ซึ่งจำกัดกรณีการใช้งานขั้นสูงบางอย่าง อย่างไรก็ตาม นักวิจัยสังเกตว่าสถานการณ์เช่นนี้ค่อนข้างไม่ธรรมดาในทางปฏิบัติและมักบ่งชี้ถึงการออกแบบ regex ที่ไม่เหมาะสม

งานนี้สร้างบนความก้าวหน้าทางทฤษฎีล่าสุดใน automaton theory แสดงให้เห็นว่าการวิจัยทางวิชาการสามารถแก้ไขความท้าทายทางวิศวกรรมในทางปฏิบัติได้ การรับประกันเวลาเชิงเส้นยังคงเป็นลักษณะเฉพาะที่กำหนดของเอนจิน รับประกันว่าประสิทธิภาพจะยังคงคาดเดาได้แม้ว่าความซับซ้อนของรูปแบบจะเพิ่มขึ้น

ข้อจำกัดของฟีเจอร์:

  • นิพจน์ lookbehind ไม่สามารถมีกลุ่มจับ (capture groups) ได้
  • รองรับ unbounded lookbehind (การปรับปรุงที่สำคัญเมื่อเทียบกับข้อกำหนดความยาวที่จำกัดของ PCRE2 )
  • รักษาการรับประกันการทำงานในเวลาเชิงเส้น
  • เข้ากันได้กับ API ของ Rust regex crate ที่มีอยู่

ผลกระทบในอนาคต

การพัฒนานี้อาจมีอิทธิพลต่อการพัฒนา regex อื่นๆ โดยเฉพาะเอนจิน RE2 ของ Google ซึ่งมีเป้าหมายการออกแบบที่คล้ายกัน เทคนิคที่พัฒนาสำหรับ Rust regex crate อาจให้แผนที่สำหรับการเพิ่มฟีเจอร์ขั้นสูงให้กับเอนจิน regex ที่เน้นประสิทธิภาพอื่นๆ โดยไม่กระทบต่อการรับประกันความปลอดภัย

ความสำเร็จของการพัฒนานี้พิสูจน์ว่าการแลกเปลี่ยนแบบดั้งเดิมระหว่างฟีเจอร์ regex และการรับประกันประสิทธิภาพไม่ใช่สิ่งที่แน่นอน เมื่อเทคนิคเหล่านี้พัฒนาและแพร่กระจายไปยังเอนจินอื่นๆ นักพัฒนาอาจไม่จำเป็นต้องเลือกระหว่าง pattern matching ที่ทรงพลังกับความน่าเชื่อถือของระบบอีกต่อไป

อ้างอิง: Backtracking NFA