Este artículo proviene de un motor de traducción automática.

Pinceladas sobre seguridad

Defensas y ataques de denegación de servicio de expresión regular

Bryan Sullivan

En el número de noviembre de 2009, escribí un artículo titulado “XML denegación de servicio ataques y defensa” (MSDN.Microsoft.com/magazine/ee335713), en el que describí algunos denegación especialmente eficaz de técnicas de ataque de servicio (DoS) contra los analizadores XML. Mucha de correo electrónico acerca de este artículo he recibido de los lectores que deseen saber más, que me personas comprenden cómo grave los ataques pueden ser de denegación de servicio fomenta realmente.

Creo que en los próximos años de cuatro a cinco, como la elevación de privilegios se convierten los ataques en más difíciles de ejecutar debido a una mayor adopción de protecciones de memoria, como los atacantes de prevención de ejecución de datos (DEP), selección aleatoria de dirección de diseño de espacio (ASLR) y aislamiento y técnicas de reducción de privilegios, cambiará su enfoque a los ataques de denegación de servicio blackmail. Los desarrolladores pueden seguir proteger sus aplicaciones mediante mantenerse por delante de la curva de tendencia de ataque y direccionamiento de hoy en día los vectores posibles de denegación de servicio futuros.

Uno de esos vectores de denegación de servicio futuros potenciales es la denegación de servicio de expresión regular. En la conferencia de Israel Open Web Application Security Project (OWASP) de 2009, Chief Checkmarx Architect Alex Roichman y Senior programador Adar Weidman presenta algunos investigación excelente en el tema de la expresión regular denegación de servicio o “ rehace. ” Su investigación reveló que una expresión regular mal escrita puede ser aprovechada para que pueda tener una cadena de ataque relativamente corto (menos de 50 caracteres) horas o más para evaluar. En el peor de los casos, el tiempo de procesamiento es realmente exponencial al número de caracteres en la cadena de entrada, lo que significa que agregar un solo carácter a la cadena duplica el tiempo de procesamiento.

En este artículo, describiré lo que hace que un regex que sea vulnerable a estos ataques. También presentaré código para un comprobador aleatorio de Regex, una utilidad de prueba diseñada para identificar regexes vulnerable por evaluar frente a miles de entradas aleatorias y marcar si cualquiera de las entradas tardar un tiempo inaceptablemente largo para finalizar el procesamiento.

(Nota: En este artículo, supongo que estén familiarizados con la sintaxis de expresiones regulares. Si no es el caso, es posible que desee de pincel, lea el artículo “ expresiones regulares de .NET Framework ” en MSDN.Microsoft.com/library/hs600312, o para profundizar más profundo, lea libro de referencia excelente de Jeffrey Friedl, “ Mastering Regular Expressions 3rd Edition ” [O’Reilly, 2006].)

RETROCESO: La raíz de un problema de

Existen básicamente dos tipos diferentes de motores de expresión regular: Los motores de búsqueda DFA (autómatas finitos) determinista y motores de búsqueda NFA (autómata finito no determinista). Un análisis exhaustivo de las diferencias entre estos tipos de motor de dos queda fuera del alcance de este artículo; sólo necesitamos centrarse en dos factores:

1. Motores de búsqueda NFA son los motores de retroceso. A diferencia de DFAs que evaluación cada carácter en una cadena de entrada como mucho una vez, motores de búsqueda NFA pueden evaluar cada carácter en una cadena de entrada varias veces. (Más adelante mostraré cómo funciona este algoritmo de evaluación de retroceso.) El enfoque de retroceso tiene ventajas, en que estos motores pueden procesar expresiones regular más compleja, como las que contengan referencias inversas o paréntesis de captura. También tiene desventajas, que ahora puede superar su tiempo de procesamiento DFAs.
2. Las clases de Microsoft .NET Framework System.Text.RegularExpression utilizan motores de búsqueda NFA.

Un efecto secundario importante de retroceso es que mientras el motor de búsqueda regex puede confirmar bastante rápidamente una coincidencia positiva (es decir, una cadena de entrada coincide con un regex determinado), confirmando una coincidencia negativa (la cadena de entrada no coincide con el regex) puede tardar bastante un poco más. De hecho, el motor debe confirmar ninguno de los posibles “ rutas ” a través de la cadena de entrada coincide con el regex, lo que significa que deben de todas las rutas de acceso que se va a probar.

Con una expresión regular no agrupación simple, el tiempo dedicado a confirmar a coincidencias negativos no es un gran problema. Por ejemplo, supongamos que la expresión regular con el que se compara es:

^\d+$

Se trata de un regex bastante sencillo que coincide con si toda la cadena de entrada está formada por caracteres numéricos solamente. El ^ y $ caracteres representan el principio y el final de la cadena, respectivamente, \d expresión representa un carácter numérico y + indica que coincida con uno o más caracteres. Probar Let’s esta expresión utilizando 123456X como una cadena de entrada.

Esta cadena de entrada no es obviamente una coincidencia porque X no es un carácter numérico. Pero ¿cuántas rutas de acceso tendría el regex de ejemplo evaluar llegado a esta conclusión? Se podría iniciar su evaluación al principio de la cadena y ver que el carácter 1 es un carácter numérico válido y que coincide con el regex. A continuación, haría mueva al carácter 2, que también encontraría una coincidencia. Por lo tanto, el regex ha asociado la cadena de 12 en este momento. A continuación lo haría pruebe 3 (y coincide con 123), y así sucesivamente hasta que se obtuvo a X, que no coincidirá.

Sin embargo, dado que nuestro motor es un motor de búsqueda NFA retroceso, no ofrece este momento. En su lugar, realiza una copia de seguridad de su coincidencia actual (123456) en su última coincidencia buena conocida (12345) y intenta de nuevo desde allí. Dado que el carácter siguiente después de 5 no es el final de la cadena, el regex no es una coincidencia y realiza una copia de seguridad a su última conocido buena coincidencia anterior (1234) y intenta de nuevo. Esto va totalmente hasta que el motor obtiene su primera coincidencia (1) y encuentra que el carácter de después 1 no es el final de la cadena. En este punto, el regex ofrece; se ha encontrado ninguna coincidencia.

Después de todo, el motor evalúa seis rutas de acceso: 123456, 12345, 1234, 123, 12 y 1. Si la cadena de entrada hubiera sido un carácter más largo, el motor ha evaluarían una ruta de acceso más. Por lo que esta expresión regular es un algoritmo lineal con respecto a la longitud de la cadena y no está en riesgo de causar una denegación de servicio. Un objeto System.Text.RegularExpressions.Regex utilizando ^ \d+$ para su patrón es lo suficientemente rápido como para romper prácticamente al instante mediante cadenas de entrada incluso enormes (más de 10.000 caracteres).

Ahora let’s cambie la expresión regular al grupo de caracteres numéricos:

^(\d+)$

Esto no cambia sustancialmente el resultado de las evaluaciones; simplemente permite al programador tener acceso a cualquier coincidencia como un grupo capturado. (Esta técnica puede resultar útil en expresiones regulares más complicadas donde desea aplicar los operadores de repetición, pero en este caso concreto no tiene ningún valor.) Agregar paréntesis de agrupación en este caso no sustancialmente cambia la velocidad de ejecución de la expresión, o bien. Probar el modelo de entrada 123456X aún hace que el motor evaluar sólo seis diferentes rutas de acceso. Sin embargo, la situación es considerablemente distinta si realizamos un cambio pequeño más para el regex:

^(\d+)+$

El adicional + carácter después de la expresión de grupo (\d+) indica al motor de regex para hacer coincidir cualquier número de grupos capturados. El motor continúa como antes, llegar a 123456 antes de retroceso a 12345.

Aquí es donde las cosas obtener “ interesantes ” (como en horribly peligrosas). En lugar de simplemente comprobar que el carácter siguiente después de 5 no es el final de la cadena, el motor trata el carácter siguiente, 6, como una nueva captura agrupar e inicia la segunda verificación desde allí. Una vez que se produce un error en esa ruta, realiza seguridad 1234 hasta y, a continuación, intente 56 como un grupo de captura independiente y, a continuación, 5 y 6 cada como grupos de captura independiente. El resultado final es que el motor realmente termina evaluar 32 paths diferentes.

Si agregamos ahora sólo un carácter numérico situado más a la cadena de evaluación, el motor tendrá que evaluar 64 trazados: doble de la cantidad: para determinar que no es una coincidencia. Se trata de un aumento exponencial en la cantidad de trabajo que se está realizado por el motor de búsqueda regex. Un atacante podría proporcionar una cadena de entrada relativamente corta: 30 caracteres o lo — y forzar el motor de proceso de cientos de millones de rutas de acceso, vinculación para horas o días.

Emitiendo la ropa Dirty

Es erróneo lo suficientemente cuando tiene una aplicación capaz de denegación de servicio regexes exponencial apartada ausente en el código del servidor. Es incluso peor cuando una aplicación anuncia sus vulnerabilidades en el código de cliente. Muchos de los controles de validación ASP.NET derivados System.Web.UI.WebControls.BaseValidator incluidos RegularExpressionValidator, ejecutará automáticamente la misma lógica de validación en el cliente en JavaScript como lo hacen en el servidor en el código. NET.

La mayoría de las veces, esto es algo bueno. Es conveniente guardar el tiempo de ida y vuelta de un envío de formulario al servidor sólo para que se rechazó un validador porque el usuario ha escrito incorrectamente un campo de entrada del usuario. Es conveniente guardar el servidor el tiempo de procesamiento demasiado. Sin embargo, si la aplicación está utilizando un regex incorrecto en su código de servidor, ese regex incorrecto también se va a utilizar en su código de cliente y ahora le resultará muy fácil para que un atacante encontrar ese regex y desarrollar una cadena de ataque para él.

Por ejemplo, cree un nuevo formulario Web Forms y agregue un control TextBox y un control RegularExpressionValidator a ese formulario. Establece la propiedad ControlToValidate del control de validación en el nombre del cuadro de texto y establezca su ValidationExpression en uno de los regexes defectuosos que he tratado:

this.RegularExpressionValidator1.ControlToValidate = "TextBox1";

this.RegularExpressionValidator1.ValidationExpression = @"^(\d+)+$";

Si ahora se abra esta página en un explorador y ver su código fuente, ver el código de JavaScript siguiente cerca a la parte inferior de la página:

<scripttype="text/javascript">

//< ![CDATA[

var RegularExpressionValidator1 = document.all ? 

  document.all["RegularExpressionValidator1"] : 

  document.getElementById("RegularExpressionValidator1");

RegularExpressionValidator1.controltovalidate = "TextBox1";

RegularExpressionValidator1.validationexpression = "^(\\d+)+$";

//]] >

</script>

Ahí está, para que todo el mundo ver: regex exponencial en la vista normal en la última línea del bloque de secuencias de comandos.

Más tramas de problemas

Por supuesto, ^(\d+)+$ is not the only bad regular expression in the world. Básicamente, cualquier expresión regular que contiene una expresión de agrupación con repetición es en sí mismo repite va a ser vulnerable. Esto incluye regexes como:

^(\d+)*$
^(\d*)*$
^(\d+|\s+)*$

Además, cualquier grupo que contiene la alternancia donde las subexpresiones alternativas solapan también es vulnerable:

^ (\d|\d\d)+$
^(\d|\d?)+$

Si vio una expresión como el ejemplo anterior en el código ahora, es llevaría probablemente pueda identificarla como vulnerable sólo desde examina. Pero podrían pasar por alto una vulnerabilidad en una mayor expresión más complicada (y más realista):

^ ([0-9a-zA-Z]([-. \w]*[0-9a-zA-Z])*@(([0-9a-zA-Z])+([-\w]*[0-9a-zA-Z])*\.)+ [a-zA-Z] {2,9}) $

Se trata de una expresión regular que se encuentran en el sitio Web de la biblioteca de expresiones regulares (regexlib.com) que está destinado a utilizarse para validar una dirección de correo electrónico. Sin embargo, también es vulnerable a ataques. Es posible que encuentre esta vulnerabilidad mediante la inspección de manuales de código o puede que no. Se requiere una técnica mejor para buscar estos problemas, y eso es lo que voy a explicar a continuación.

Buscar Regexes incorrecta en el código

Lo ideal sería una forma de encontrar regexes exponenciales en el código en tiempo de compilación y avisarle sobre ellos. Presumiblemente, para analizar una cadena de regex y analizarlos para posibles puntos débiles, necesitaría otra regex. En este punto, me siento como un addict regex: “ Yo Don necesita ayuda, sólo necesito más regexes! ” Por desgracia, mis habilidades de regex no son la tarea de escribir regex para analizar regexes. Si cree que tiene el trabajo de código para esto, envíe a mí y gusto dar crédito en la columna de pinceladas sobre seguridad del mes siguiente. Mientras tanto, porque I Don tienen una forma de detectar regexes incorrecto en tiempo de compilación, lo haré mejor lo siguiente: Escribiré a un comprobador aleatorio de regex.

Las pruebas aleatorias es el proceso de suministrar datos aleatorios, con formato incorrecto a entradas de la aplicación para intentar convertirlo en un error. Las iteraciones más pruebas aleatorias ejecutar, mejor será la oportunidad, encontrará un error, por lo que es frecuente que los equipos ejecutar miles o millones de iteraciones por entrada. Los equipos de seguridad de Microsoft han encontrado trata de un modo increíblemente eficaz de encontrar errores, por lo que el equipo de ciclo de vida de desarrollo de seguridad ha realizado las pruebas aleatorias un requisito para todos los equipos de productos y servicios.

Mi comprobador aleatorio, quiero aproximación de las cadenas de entrada aleatorias a mi expresión regular. Comenzaré por definir una cadena const para mi regex, un método testInputValue que comprueba el regex y un método de runTest recopilará aleatorio entrada cadenas de suministro testInputValue.

const string regexToTest = @"^(\d+)+$";



static void testInputValue(string inputToTest)

{

  System.Text.RegularExpressions.Regex.Match(inputToTest, regexToTest);

}



void runTest()

{

  string[] inputsToTest = {};



  foreach (string inputToTest in inputsToTest)

  testInputValue(inputToTest);

}

Tenga en cuenta que no hay ningún código aún para generar los valores de entrada fuzzed; familiarizará con la en breve. También debe tener en cuenta que no se molesta en el código para comprobar el valor devuelto desde Regex.Match. Esto es porque realmente sin importar si la entrada coincide con el patrón o no. Todo lo que me interesa en esta situación es si tarda mucho tiempo para decidir si la entrada coincide con el motor de búsqueda regex.

Normalmente se utilizan fuzzers para intentar encontrar vulnerabilidades de elevación de privilegio aprovechable, pero de nuevo, en este caso, estoy sólo interesado en buscar vulnerabilidades de denegación de servicio. Simplemente no avance Mis datos de aplicación de prueba para ver si se bloquea; tiene que ser capaz de detectar si está bloqueado. Aunque no puede ser el método científico mayoría, puedo ello eficazmente ejecutar cada prueba regex secuencialmente en un subproceso de trabajo independiente y cómo establecer un valor de tiempo de espera de finalización del subproceso. Si el subproceso no completar su procesamiento dentro de un plazo razonable de tiempo, cinco segundos para probar una única entrada dice, asumimos que ha sido la expresión regular ' d denegación de servicio. Lo almacenaré agregar un evento ManualResetEvent y modificar los métodos testInputValue y runTest en consecuencia, tal y como se muestra en La figura 1.

Figura 1 Las pruebas mediante subprocesos de trabajo independientes

static ManualResetEvent threadComplete = new ManualResetEvent(false);



static void testInputValue(object inputToTest)

{

  System.Text.RegularExpressions.Regex.Match((string)inputToTest, 

    regexToTest);

  threadComplete.Set();

}



void runTest()

{

  string[] inputsToTest = {};



  foreach (string inputToTest in inputsToTest)

  {

    Thread thread = new Thread(testInputValue);

    thread.Start(inputToTest);



    if (!threadComplete.WaitOne(5000))

    {

      Console.WriteLine("Regex exceeded time limit for input " + 

        inputToTest);

      return;

    }



    threadComplete.Reset();

  }



  Console.WriteLine("All tests succeeded within the time limit.");

}

Ahora es el tiempo necesario para generar los valores de entrada. Esto es realmente más difícil de lo que parece. Si sólo puedo generar datos completamente aleatorios, es poco probable de ella coincidiría con suficiente de regex para revelar una vulnerabilidad. Por ejemplo, si se prueba el regex ^ \d+)+$ (con la entrada XdO(*iLy@Lm4p$, the regex will instantly not match and the problem will remain hidden. Necesito generar entrada es bastante cerca para la aplicación espera para que la prueba sea útil y que necesito una manera de generar datos aleatorios que coincida con un regex determinado.

Planes de generación de datos al rescate

Afortunadamente, es una característica en proyectos de base de datos de Visual Studio que puede hacer justamente eso: Planear la generación de datos. Si está utilizando Visual Studio Team Suite, también tiene acceso a esta función. Los planes de generación de datos se utilizan para rellenar rápidamente las bases de datos con datos de prueba. Lo pueden llenar tablas con valores numéricos o cadenas aleatorias o (por suerte para nosotros) cadenas de coincidencia especifican expresiones regulares.

Primero deba crear una tabla en SQL Server 2005 o 2008 base de datos en el que puede generar datos de prueba. Una vez hecho esto, vuelva a Visual Studio y cree un nuevo proyecto de base de datos de SQL Server. Editar las propiedades de proyecto de base de datos para proporcionar una cadena de conexión a la base de datos. Una vez que ha escrito una cadena de conexión y probado para asegurarse de que funciona, vuelva al explorador de soluciones y agregue un nuevo elemento plan de generación de datos al proyecto. En este momento, debe ver algo parecido a Figura 2.

Figura 2 Un elemento de plan de generación de datos en Visual Studio

Ahora elija la tabla y columna que desea rellenar con datos de entrada del comprobador aleatorio. En la sección de tabla, establezca el número de prueba los valores generan (filas para insertar columna). Escribí anteriormente que fuzzers generalmente probar cientos de miles o millones de iteraciones para intentar encontrar problemas. Aunque normalmente aprobar este nivel de rigor, es una exageración este comprobador aleatorio regex en lo que respecta. Si un regex se va a bloquear, se va a hacerlo dentro de un par iteraciones de prueba cientos. Sugerir si las filas en Insertar valor a 200, pero si desea probar más, no dude.

En la sección columna, ahora establece el generador en expresión regular y escriba el valor de patrón de regex que desea probar como el valor de la propiedad Expression en la ficha de propiedades de la columna. Es importante tener en cuenta que la propiedad Expression no son compatibles con cada carácter de expresión regular legal. No se puede especificar los delimitadores de comienzo y fin de línea ^ y $ (o con más precisión, se puede escribir pero el generador generará un literal ^ o carácter $ en la prueba de entrada). Deje estos caracteres. Encontrará una lista completa de los operadores compatibles con el generador de expresiones regulares en MSDN.Microsoft.com/library/aa833197(VS.80).

Es un problema mayor que la propiedad Expression también no admite las notaciones abreviada comunes como \d para dígitos numéricos o \w para caracteres de palabra. Si su regex utiliza estos, deberá reemplazarlos con sus equivalentes de la clase de carácter: [0-9] en lugar de \d, [a-zA-Z0-9_] en lugar de \w y así sucesivamente. Si necesita reemplazar \s (carácter de espacio en blanco), puede introducir un espacio literal en su lugar.

La última tarea en el proyecto de base de datos es realmente rellenar la base de datos con los datos de prueba de acuerdo con sus especificaciones. Para ello, eligiendo los datos | DataGenerator | elemento de menú Generar datos o simplemente presione F5.

Adición de un ataque

En el código comprobador aleatorio, modifique el método runTest por lo que extrae datos de prueba generado de la base de datos. Quizás piense que haya terminado una vez hecho esto, pero en realidad hay un cambio más importante para realizar. Si ejecuta al comprobador aleatorio ahora, incluso contra un regex defectuoso conocido como ^(\d+)+$, it will fail to find any problems and report that all tests succeeded. Esto es porque todos los datos de prueba que ha generado es una coincidencia válida para su regex.

Recuerde anteriormente afirmé que los motores de búsqueda NFA regex pueden bastante rápidamente confirmar una coincidencia positiva y que problemas realmente sólo ocurren en coincidencias negativos. Además, debido a naturaleza ’ NFAs retroceso, sólo producirse problemas en cuando hay un gran número de caracteres coincidentes al principio de la entrada y el carácter incorrecto aparece al final. Si un carácter erróneo aparecía en la parte frontal de la cadena de entrada, la prueba podría finalizar instantáneamente.

El cambio final a realizar en el código del comprobador aleatorio es anexar caracteres incorrectos en los extremos de las entradas de prueba. Hacen una matriz de cadenas que contiene alfabético, numérico, puntuación y caracteres de espacio en blanco:

 

string[] attackChars = { "0", "1", "9", "X", "x", "+", 

"-", "@", "!", "(", ")", "[", "]", "\\", "/", 

"?", "<", ">", ".", ",", ":", ";", " ", "" };

Ahora modifique el código para que cada cadena de entrada que se recuperan de la base de datos se ha probado con cada uno de estos caracteres de ataque anexados al mismo. Por lo que la primera cadena de entrada se debería probar con un carácter 0 anexada al mismo, a continuación, con un 1 carácter anexado al mismo y así sucesivamente. Una vez esa cadena de entrada se ha probado con cada uno de los caracteres de ataque, mover a la siguiente cadena de entrada y pruebe con cada uno de los caracteres de ataque.

foreach (string inputToTest in inputsToTest)

{

  foreach (string attackChar in attackChars)

  {

    Threadthread = new Thread(testInputValue);

    thread.Start(inputToTest + attackChar);

...

Ahora tiene dos problemas

Hay una oferta famosa por Netscape ex ingeniería Zawinski Pablo relativas a expresiones regulares:

“ Algunas personas, cuando se enfrentan con un problema, cree, ‘ sé, voy a utilizar expresiones regulares. ’ Ahora tienen dos problemas. ”

Mientras estoy en ninguna parte cerca como cínicos sobre regexes como SR.. Zawinski, se admitir que puede ser bastante difícil sólo para escribir un regex correcto, mucho menos un regex correcto que es seguro frente a ataques de denegación de servicio. Le animo a que para que examine todos su regexes exponencial grado de complejidad y utilizar técnicas de pruebas aleatorias para comprobar sus conclusiones.

Bryan Sullivan es un administrador de programas de seguridad para el equipo de ciclo de vida de desarrollo de seguridad de Microsoft donde especializado en aplicación Web y .NET problemas de seguridad. Es autor de la seguridad en AJAX (Addison-Wesley, 2007).

Gracias a los siguientes expertos técnicos por su ayuda en la revisión de este artículo: Barclay Hill, Michael Howard, Ron Petrusha y Justin van Patten