Có an toàn khi sử dụng đầu vào của người dùng cho các cụm từ thông dụng của Python không?

Question

Tôi muốn cho phép người dùng của mình sử dụng cụm từ thông dụng cho một số tính năng. Tôi tò mò về ý nghĩa của việc truyền đầu vào của người dùng tới re.compile(). Tôi cho rằng không có cách nào để người dùng đưa cho tôi một chuỗi có thể cho phép họ thực thi mã tùy ý. Những mối nguy hiểm mà tôi đã nghĩ đến là:

1. Người dùng có thể chuyển đầu vào làm tăng ngoại lệ.
   • Người dùng có thể truyền đầu vào làm cho công cụ regex mất nhiều thời gian hoặc sử dụng nhiều bộ nhớ.

Giải pháp cho 1. thật dễ dàng: bắt ngoại lệ. Tôi không chắc chắn nếu có một giải pháp tốt để 2. Có lẽ chỉ giới hạn chiều dài của regex sẽ làm việc.

Có điều gì khác mà tôi cần phải lo lắng không?

Answer 1

Tôi đã làm việc trên một chương trình cho phép người dùng nhập regex của riêng mình và bạn đúng - họ có thể (và làm) nhập regex có thể mất nhiều thời gian để hoàn thành - đôi khi dài hơn tuổi thọ của vũ trụ. Điều gì là tồi tệ hơn, trong khi xử lý một regex Python giữ GIL, do đó, nó sẽ không chỉ treo thread đang chạy regex, nhưng toàn bộ chương trình.

Hạn chế độ dài của regex sẽ không hoạt động, vì sự cố xảy ra ngược dòng. Ví dụ: khớp với regex r"(\S+)+x" trên một chuỗi có độ dài N không chứa dấu "x" sẽ quay lại 2 ** N lần. Trên hệ thống của tôi mất khoảng một giây để so khớp với "a"*21 và thời gian tăng gấp đôi cho mỗi ký tự bổ sung, do đó, một chuỗi gồm 100 ký tự sẽ mất khoảng 19167393131891000 năm để hoàn thành (đây là ước tính, tôi chưa hẹn giờ).

Để biết thêm thông tin, hãy đọc cuốn sách O'Reilly "Làm chủ biểu thức chính quy" - điều này có một vài chương về hiệu suất.

chỉnh sửa Để có được vòng này chúng tôi đã viết một hàm regex phân tích đã cố gắng để bắt và từ chối một số trường hợp thoái hóa rõ ràng hơn, nhưng nó là không thể để có được tất cả trong số họ.

Một điều khác chúng tôi đã xem xét là vá mô-đun lại để tăng ngoại lệ nếu nó lùi lại quá nhiều lần. Điều này là có thể, nhưng đòi hỏi phải thay đổi nguồn Python C và biên dịch lại, do đó, không phải là di động. Chúng tôi cũng đã gửi một bản vá để giải phóng GIL khi kết hợp với chuỗi python, nhưng tôi không nghĩ rằng nó được chấp nhận vào lõi (python chỉ giữ GIL vì regex có thể chạy với bộ đệm có thể thay đổi).

Answer 2

Tôi thực sự không nghĩ rằng có thể thực thi mã đơn giản bằng cách chuyển nó vào re.compile. Cách tôi hiểu nó, re.compile (hoặc bất kỳ hệ thống regex nào trong bất kỳ ngôn ngữ nào) chuyển đổi chuỗi regex thành finite automaton (DFA hoặc NFA), và mặc dù tên đáng ngại 'biên dịch' nó không liên quan gì đến việc thực thi bất kỳ mã nào .

Answer 3

Bạn về mặt kỹ thuật không cần sử dụng re.compile() để thực hiện thao tác biểu thức chính quy trên một chuỗi. Trong thực tế, phương thức biên dịch thường có thể chậm hơn nếu bạn chỉ thực hiện thao tác một lần vì có phí trên được kết hợp với việc biên dịch ban đầu.

Nếu bạn lo lắng về từ "biên dịch" thì hãy tránh tất cả lại với nhau và chỉ cần chuyển biểu thức thô sang match, search, v.v. Bạn có thể nâng cao hiệu suất của mã của bạn một chút.

Answer 4

Không cần thiết phải sử dụng biên dịch() trừ khi bạn cần sử dụng lại nhiều cụm từ thông dụng khác nhau. Module đã lưu trữ các biểu thức cuối cùng.

Điểm 2 (khi thực hiện) có thể là điểm rất khó nếu bạn cho phép người dùng nhập bất kỳ cụm từ thông dụng nào. Bạn có thể tạo một regexp phức tạp với một vài ký tự, giống như một ký tự nổi tiếng (x+x+)+y. Tôi nghĩ rằng đó là một vấn đề chưa được giải quyết một cách tổng quát. Cách giải quyết có thể là khởi chạy một luồng khác và theo dõi nó, nếu nó vượt quá thời gian cho phép, hãy hủy chuỗi và trả lại bằng một lỗi.

Answer 5

Việc biên dịch cụm từ thông dụng phải an toàn hợp lý. Mặc dù những gì nó biên dịch vào không phải là nghiêm chỉnh một NFA (backreferences có nghĩa là nó không phải là khá sạch sẽ) nó vẫn nên được loại đơn giản để biên dịch vào.

Bây giờ là đặc điểm hiệu suất, đây là một vấn đề khác hoàn toàn. Ngay cả một biểu thức chính quy nhỏ cũng có thể có các đặc điểm thời gian theo hàm mũ vì ngược lại. Nó có thể là tốt hơn để xác định một tập con của các tính năng và chỉ hỗ trợ các biểu thức rất hạn chế mà bạn dịch chính mình.

Nếu bạn thực sự muốn hỗ trợ cụm từ thông dụng chung, bạn phải tin tưởng người dùng của bạn (đôi khi là tùy chọn) hoặc giới hạn lượng không gian và thời gian sử dụng. Tôi tin rằng không gian đó được sử dụng chỉ được xác định bởi độ dài của cụm từ thông dụng.

chỉnh sửa: Như Dave lưu ý, dường như khóa thông dịch toàn cầu được giữ trong quá trình so khớp regex, điều này sẽ khiến việc đặt thời gian chờ khó hơn.Nếu đúng như vậy, tùy chọn duy nhất của bạn để đặt thời gian chờ là chạy khớp trong một quy trình riêng biệt. Trong khi không chính xác lý tưởng nó là doable. Tôi hoàn toàn quên mất khoảng multiprocessing. Điểm ưa thích là this section trên các đối tượng chia sẻ. Nếu bạn thực sự cần những khó khăn khó khăn, các quá trình riêng biệt là cách để đi đến đây.

Answer 6

Đơn giản hơn nhiều đối với người dùng thông thường để cung cấp cho họ ngôn ngữ tập hợp con. Ví dụ: quy tắc tổng quát của vỏ trong ví dụ fnmatch. Các quy tắc điều kiện LIKE của SQL là một ví dụ khác.

Dịch ngôn ngữ của người dùng thành một regex phù hợp để thực thi khi chạy.