¿Es seguro usar la entrada del usuario para las expresiones regulares de Python?

Question

Me gustaría dejar que mis usuarios usen expresiones regulares para algunas funciones. Tengo curiosidad por las implicaciones de pasar la información del usuario a re.compile(). Supongo que no hay forma de que un usuario me dé una cadena que podría permitirle ejecutar código arbitrario. Los peligros que he pensado son:

1. El usuario podría pasar la entrada que genera una excepción.
   • El usuario podría pasar la entrada que hace que el motor de expresiones regulares tome mucho tiempo o que use mucha memoria.

La solución a 1. es fácil: capturar excepciones. No estoy seguro de si hay una buena solución para 2. Quizás limitar la longitud de la expresión regular funcionaría.

¿Hay algo más de lo que deba preocuparme?

Answer 1

He trabajado en un programa que permite a los usuarios ingresar su propia expresión regular y tienen razón; pueden (y lo hacen) ingresar expresiones regulares que pueden tardar mucho tiempo en finalizar, a veces más que la duración del universo. Lo que es peor, al procesar una expresión regular Python contiene el GIL, por lo que no solo bloqueará el hilo que está ejecutando la expresión regular, sino todo el programa.

Limitar la longitud de la expresión regular no funcionará, ya que el problema es retroceder. Por ejemplo, emparejar la expresión regular r"(\S+)+x" en una cadena de longitud N que no contenga una "x" retrocederá 2 ** N veces. En mi sistema esto toma alrededor de un segundo para coincidir con "a"*21 y el tiempo se duplica para cada carácter adicional, por lo que una cadena de 100 caracteres tardaría aproximadamente 19167393131891000 años en completarse (esta es una estimación, no la he sincronizado).

Para obtener más información, lea el libro de O'Reilly "Dominio de expresiones regulares"; esto tiene un par de capítulos sobre el rendimiento.

edición Para evitar esto escribimos una función de análisis de expresiones regulares que trataba de recuperar y rechazar algunos de los casos degenerados más obvios, pero es imposible conseguir todos ellos.

Otra cosa que vimos fue parchar el módulo re para generar una excepción si retrocede demasiadas veces. Esto es posible, pero requiere cambiar la fuente de Python C y volver a compilar, por lo que no es portátil. También enviamos un parche para liberar el GIL cuando se combina con cadenas de python, pero no creo que haya sido aceptado en el núcleo (python solo contiene el GIL porque el regex se puede ejecutar contra los búferes mutables).

Answer 2

Realmente no creo que sea posible ejecutar código simplemente pasándolo a re.compile. Tal como lo entiendo, re.compile (o cualquier sistema regex en cualquier idioma) convierte la cadena de expresiones regulares en finite automaton (DFA o NFA) y, a pesar del siniestro nombre 'compilar', no tiene nada que ver con la ejecución de ningún código .

Answer 3

Técnicamente no necesita utilizar re.compile() para realizar una operación de expresión regular en una cadena. De hecho, el método de compilación a menudo puede ser más lento si solo está ejecutando la operación una vez, ya que hay gastos generales asociados con la compilación inicial.

Si le preocupa la palabra "compilar", evítelo todo junto y simplemente pase la expresión sin formato a match, search, etc. Puede terminar mejorando el rendimiento de su código de todos modos.

Answer 4

No es necesario usar compile() excepto cuando necesite reutilizar muchas expresiones regulares diferentes. El módulo ya almacena en caché las últimas expresiones.

El punto 2 (en ejecución) podría ser muy difícil si permite que el usuario ingrese cualquier expresión regular. Puede hacer una expresión regular compleja con pocos caracteres, como la famosa (x+x+)+y. Creo que es un problema aún por resolver de una manera general. Una solución temporal podría estar iniciando un subproceso diferente y supervisándolo, si supera el tiempo permitido, elimine el subproceso y devuelva con un error.

Answer 5

La compilación de la expresión regular debe ser razonablemente segura. Aunque en lo que se compila no es estrictamente un NFA (las referencias posteriores significan que no es tan limpio) todavía debería ser algo sencillo de compilar.

Ahora, en cuanto a las características de rendimiento, este es otro problema por completo. Incluso una pequeña expresión regular puede tener características de tiempo exponencial debido al retroceso. Podría ser mejor definir un cierto subconjunto de características y solo admitir expresiones muy limitadas que usted mismo traduzca.

Si realmente desea admitir expresiones regulares generales, debe confiar en sus usuarios (a veces una opción) o limitar la cantidad de espacio y tiempo utilizado. I crea que el espacio utilizado está determinado solo por la longitud de la expresión regular.

editar: Como señala Dave, aparentemente el bloqueo del intérprete global se mantiene durante la coincidencia de expresiones regulares, lo que dificultaría la configuración de ese tiempo de espera.Si ese es el caso, su única opción para establecer un tiempo de espera es ejecutar la coincidencia en un proceso separado. Si bien no es exactamente ideal, es factible. Me olvidé por completo de multiprocessing. El punto de interés es this section en el intercambio de objetos. Si realmente necesita las restricciones difíciles, los procesos separados son el camino a seguir aquí.

Answer 6

Es mucho más simple para los usuarios ocasionales darles un lenguaje de subconjunto. Las reglas de globbing del shell en fnmatch, por ejemplo. Las reglas de condición SQL LIKE son otro ejemplo.

Traducir el idioma del usuario en una expresión regular adecuada para la ejecución en tiempo de ejecución.