Una condición de carrera o un riesgo de carrera es una condición de un sistema electrónico , de software u otro sistema en la que el comportamiento sustancial del sistema depende de la secuencia o el momento de otros eventos incontrolables, lo que genera resultados inesperados o inconsistentes. Se convierte en un error cuando uno o más de los comportamientos posibles son indeseables.
El término condición de carrera ya se utilizaba en 1954, por ejemplo en la tesis doctoral de David A. Huffman "La síntesis de circuitos de conmutación secuencial". [1]
Las condiciones de carrera pueden ocurrir especialmente en circuitos lógicos o programas de software distribuidos o multiproceso . El uso de la exclusión mutua puede evitar las condiciones de carrera en sistemas de software distribuidos.
Un ejemplo típico de una condición de carrera puede ocurrir cuando una compuerta lógica combina señales que han viajado por diferentes caminos desde la misma fuente. Las entradas a la compuerta pueden cambiar en momentos ligeramente diferentes en respuesta a un cambio en la señal de la fuente. La salida puede, por un breve período, cambiar a un estado no deseado antes de volver al estado diseñado. Algunos sistemas pueden tolerar tales fallas , pero si esta salida funciona como una señal de reloj para otros sistemas que contienen memoria, por ejemplo, el sistema puede desviarse rápidamente de su comportamiento diseñado (en efecto, la falla temporal se convierte en una falla permanente).
Consideremos, por ejemplo, una compuerta AND de dos entradas alimentada con la siguiente lógica: Una señal lógica en una entrada y su negación, (el ¬ es una negación booleana ), en otra entrada en teoría nunca emiten un valor verdadero: . Sin embargo, si los cambios en el valor de tardan más en propagarse a la segunda entrada que a la primera cuando cambia de falso a verdadero, se producirá un breve período durante el cual ambas entradas serán verdaderas, y por lo tanto la salida de la compuerta también será verdadera. [2]
Un ejemplo práctico de una condición de carrera puede ocurrir cuando se utilizan circuitos lógicos para detectar determinadas salidas de un contador. Si todos los bits del contador no cambian exactamente de manera simultánea, habrá patrones intermedios que pueden generar coincidencias falsas.
Una condición de carrera crítica ocurre cuando el orden en el que se cambian las variables internas determina el estado final en el que terminará la máquina de estados .
Una condición de carrera no crítica ocurre cuando el orden en el que se cambian las variables internas no determina el estado final en el que terminará la máquina de estados.
Una condición de carrera estática ocurre cuando una señal y su complemento se combinan.
Una condición de carrera dinámica ocurre cuando da como resultado múltiples transiciones cuando solo se pretende una. Se deben a la interacción entre puertas. Se puede eliminar utilizando no más de dos niveles de puertas.
Una condición de carrera esencial ocurre cuando una entrada tiene dos transiciones en un tiempo menor que el tiempo total de propagación de la retroalimentación. A veces, se solucionan utilizando elementos de línea de retardo inductivos para aumentar de manera efectiva la duración de una señal de entrada.
Las técnicas de diseño como los mapas de Karnaugh alientan a los diseñadores a reconocer y eliminar las condiciones de carrera antes de que causen problemas. A menudo, se puede agregar redundancia lógica para eliminar algunos tipos de carreras.
Además de estos problemas, algunos elementos lógicos pueden entrar en estados metaestables , lo que crea más problemas para los diseñadores de circuitos.
Una condición de carrera puede surgir en un software cuando un programa informático tiene varias rutas de código que se ejecutan al mismo tiempo. Si las distintas rutas de código tardan un tiempo distinto al esperado, pueden finalizar en un orden distinto al esperado, lo que puede provocar errores de software debido a un comportamiento imprevisto. También puede producirse una carrera entre dos programas, lo que da lugar a problemas de seguridad (consulte a continuación).
Las condiciones de carrera críticas provocan ejecuciones no válidas y errores de software . Las condiciones de carrera críticas suelen ocurrir cuando los procesos o subprocesos dependen de algún estado compartido. Las operaciones sobre estados compartidos se realizan en secciones críticas que deben ser mutuamente excluyentes . El incumplimiento de esta regla puede dañar el estado compartido.
Una carrera de datos es un tipo de condición de carrera. Las carreras de datos son partes importantes de varios modelos de memoria formales . El modelo de memoria definido en los estándares C11 y C++11 especifica que un programa C o C++ que contiene una carrera de datos tiene un comportamiento indefinido . [3] [4]
Una condición de carrera puede ser difícil de reproducir y depurar porque el resultado final no es determinista y depende del tiempo relativo entre los subprocesos que interfieren. Por lo tanto, los problemas de esta naturaleza pueden desaparecer al ejecutar en modo de depuración, agregar registros adicionales o adjuntar un depurador. Un error que desaparece de esta manera durante los intentos de depuración a menudo se conoce como " Heisenbug ". Por lo tanto, es mejor evitar las condiciones de carrera mediante un diseño de software cuidadoso.
Supongamos que dos subprocesos incrementan cada uno el valor de una variable entera global en 1. Idealmente, se produciría la siguiente secuencia de operaciones:
En el caso que se muestra arriba, el valor final es 2, como se esperaba. Sin embargo, si los dos subprocesos se ejecutan simultáneamente sin bloqueo ni sincronización (a través de semáforos ), el resultado de la operación podría ser incorrecto. La secuencia alternativa de operaciones que se muestra a continuación demuestra este escenario:
En este caso, el valor final es 1 en lugar del resultado esperado de 2. Esto ocurre porque aquí las operaciones de incremento no son mutuamente excluyentes. Las operaciones mutuamente excluyentes son aquellas que no se pueden interrumpir mientras se accede a algún recurso como una ubicación de memoria.
No todos consideran las carreras de datos como un subconjunto de las condiciones de carrera. [5] La definición precisa de carrera de datos es específica del modelo de concurrencia formal que se utiliza, pero normalmente se refiere a una situación en la que una operación de memoria en un hilo podría intentar acceder a una ubicación de memoria al mismo tiempo que una operación de memoria en otro hilo está escribiendo en esa ubicación de memoria, en un contexto en el que esto es peligroso. Esto implica que una carrera de datos es diferente de una condición de carrera, ya que es posible tener no determinismo debido al tiempo incluso en un programa sin carreras de datos, por ejemplo, en un programa en el que todos los accesos a la memoria utilizan solo operaciones atómicas .
Esto puede ser peligroso porque en muchas plataformas, si dos subprocesos escriben en una ubicación de memoria al mismo tiempo, puede ser posible que la ubicación de memoria termine conteniendo un valor que sea una combinación arbitraria y sin sentido de los bits que representan los valores que cada subproceso estaba intentando escribir; esto podría resultar en corrupción de memoria si el valor resultante es uno que ninguno de los subprocesos intentó escribir (a veces esto se llama una "escritura rota"). De manera similar, si un subproceso lee desde una ubicación mientras otro subproceso está escribiendo en él, puede ser posible que la lectura devuelva un valor que sea una combinación arbitraria y sin sentido de los bits que representan el valor que la ubicación de memoria tenía antes de la escritura, y de los bits que representan el valor que se está escribiendo.
En muchas plataformas, se proporcionan operaciones de memoria especiales para el acceso simultáneo; en tales casos, el acceso simultáneo mediante estas operaciones especiales suele ser seguro, pero el acceso simultáneo mediante otras operaciones de memoria es peligroso. A veces, estas operaciones especiales (que son seguras para el acceso simultáneo) se denominan operaciones atómicas o de sincronización , mientras que las operaciones ordinarias (que no son seguras para el acceso simultáneo) se denominan operaciones de datos . Probablemente, por eso se utiliza el término carrera de datos ; en muchas plataformas, donde existe una condición de carrera que involucra solo operaciones de sincronización , dicha carrera puede ser no determinista, pero segura; pero una carrera de datos podría provocar una corrupción de la memoria o un comportamiento indefinido.
La definición precisa de carrera de datos difiere entre los distintos modelos de concurrencia formal. Esto es importante porque el comportamiento concurrente suele ser poco intuitivo y, por lo tanto, a veces se aplica el razonamiento formal.
El estándar C++ , en el borrador N4296 (19-11-2014), define la carrera de datos de la siguiente manera en la sección 1.10.23 (página 14) [6]
Dos acciones son potencialmente concurrentes si
- Se realizan mediante subprocesos diferentes, o
- No están secuenciados y al menos uno lo realiza un manejador de señales.
La ejecución de un programa contiene una carrera de datos si contiene dos acciones conflictivas potencialmente concurrentes, al menos una de las cuales no es atómica y ninguna sucede antes que la otra, excepto en el caso especial de los controladores de señales que se describe a continuación [omitido]. Cualquier carrera de datos de este tipo da como resultado un comportamiento indefinido.
Las partes de esta definición relacionadas con los manejadores de señales son idiosincrásicas de C++ y no son típicas de las definiciones de carrera de datos .
El artículo Detecting Data Races on Weak Memory Systems [7] ofrece una definición diferente:
"Dos operaciones de memoria entran en conflicto si acceden a la misma ubicación y al menos una de ellas es una operación de escritura..." Dos operaciones de memoria, x e y, en una ejecución secuencialmente consistente forman una carrera 〈x,y〉, si y solo si x e y entran en conflicto, y no están ordenadas por la relación hb1 de la ejecución. La carrera 〈x,y〉, es una carrera de datos si y solo si al menos una de x o y es una operación de datos.
Aquí tenemos dos operaciones de memoria que acceden a la misma ubicación, una de las cuales es una escritura.
La relación hb1 se define en otra parte del artículo y es un ejemplo de una relación típica de " sucede antes "; intuitivamente, si podemos demostrar que estamos en una situación en la que se garantiza que una operación de memoria X se ejecutará hasta su finalización antes de que comience otra operación de memoria Y, entonces decimos que "X sucede antes que Y". Si ni "X sucede antes que Y" ni "Y sucede antes que X", entonces decimos que X e Y "no están ordenados por la relación hb1". Por lo tanto, la cláusula "...y no están ordenados por la relación hb1 de la ejecución" se puede traducir intuitivamente como "...y X e Y son potencialmente concurrentes".
El artículo considera peligrosas sólo aquellas situaciones en las que al menos una de las operaciones de memoria es una "operación de datos"; en otras partes de este artículo, el artículo también define una clase de "operaciones de sincronización" que son seguras para el uso potencialmente simultáneo, en contraste con las "operaciones de datos".
La especificación del lenguaje Java [8] proporciona una definición diferente:
Se dice que dos accesos a (lecturas o escrituras) la misma variable son conflictivos si al menos uno de los accesos es una escritura... Cuando un programa contiene dos accesos conflictivos (§17.4.1) que no están ordenados por una relación de "ocurrencia anterior", se dice que contiene una carrera de datos... una carrera de datos no puede causar un comportamiento incorrecto, como devolver la longitud incorrecta para una matriz.
Una diferencia crítica entre el enfoque de C++ y el de Java es que en C++, una carrera de datos es un comportamiento indefinido, mientras que en Java, una carrera de datos simplemente afecta a las "acciones entre subprocesos". [8] Esto significa que en C++, un intento de ejecutar un programa que contenga una carrera de datos podría (mientras sigue cumpliendo la especificación) bloquearse o podría exhibir un comportamiento inseguro o extraño, mientras que en Java, un intento de ejecutar un programa que contenga una carrera de datos puede producir un comportamiento de concurrencia no deseado pero es por lo demás (asumiendo que la implementación se adhiere a la especificación) seguro.
Una faceta importante de las carreras de datos es que, en algunos contextos, se garantiza que un programa que no tenga carreras de datos se ejecutará de manera secuencialmente consistente , lo que facilita enormemente el razonamiento sobre el comportamiento concurrente del programa. Se dice que los modelos de memoria formal que brindan dicha garantía exhiben una propiedad de "consistencia secuencial para libertad de carrera de datos" (SC for DRF, por sus siglas en inglés). Se dice que este enfoque ha logrado un consenso reciente (presumiblemente en comparación con los enfoques que garantizan la consistencia secuencial en todos los casos, o los enfoques que no la garantizan en absoluto). [9]
Por ejemplo, en Java, esta garantía se especifica directamente: [8]
Un programa está correctamente sincronizado si y sólo si todas las ejecuciones secuencialmente consistentes están libres de carreras de datos.
Si un programa está correctamente sincronizado, entonces todas las ejecuciones del programa parecerán ser secuencialmente consistentes (§17.4.3).
Esta es una garantía extremadamente sólida para los programadores. Los programadores no necesitan razonar sobre reordenamientos para determinar que su código contiene carreras de datos. Por lo tanto, no necesitan razonar sobre reordenamientos al determinar si su código está correctamente sincronizado. Una vez que se determina que el código está correctamente sincronizado, el programador no necesita preocuparse de que los reordenamientos afecten a su código.
Un programa debe estar correctamente sincronizado para evitar los tipos de comportamientos contraintuitivos que se pueden observar cuando se reordena el código. El uso de una sincronización correcta no garantiza que el comportamiento general de un programa sea correcto. Sin embargo, su uso permite a un programador razonar sobre los posibles comportamientos de un programa de una manera sencilla; el comportamiento de un programa correctamente sincronizado depende mucho menos de posibles reordenamientos. Sin una sincronización correcta, son posibles comportamientos muy extraños, confusos y contraintuitivos.
Por el contrario, un borrador de especificación de C++ no requiere directamente un SC para la propiedad DRF, sino que simplemente observa que existe un teorema que lo establece:
[Nota: Se puede demostrar que los programas que usan correctamente los mutex y las operaciones memory_order_seq_cst para evitar todas las carreras de datos y no usan otras operaciones de sincronización se comportan como si las operaciones ejecutadas por sus hilos constituyentes estuvieran simplemente intercaladas, y cada cálculo de valor de un objeto se tomara del último efecto secundario sobre ese objeto en esa intercalación. Esto normalmente se conoce como “coherencia secuencial”. Sin embargo, esto se aplica solo a programas sin carreras de datos, y los programas sin carreras de datos no pueden observar la mayoría de las transformaciones de programas que no cambian la semántica de programas de un solo hilo. De hecho, la mayoría de las transformaciones de programas de un solo hilo continúan estando permitidas, ya que cualquier programa que se comporte de manera diferente como resultado debe realizar una operación indefinida.— nota final
Cabe señalar que el borrador de especificación de C++ admite la posibilidad de que existan programas válidos pero que utilicen operaciones de sincronización con un memory_order distinto de memory_order_seq_cst, en cuyo caso el resultado puede ser un programa correcto pero para el que no se ofrece garantía alguna de consistencia secuencial. En otras palabras, en C++, algunos programas correctos no son secuencialmente consistentes. Se cree que este enfoque da a los programadores de C++ la libertad de elegir una ejecución más rápida del programa a costa de renunciar a la facilidad de razonamiento sobre su programa. [9]
Existen varios teoremas, a menudo presentados en forma de modelos de memoria, que proporcionan SC para garantías DRF dados varios contextos. Las premisas de estos teoremas normalmente imponen restricciones tanto al modelo de memoria (y por lo tanto a la implementación) como al programador; es decir, normalmente ocurre que hay programas que no cumplen las premisas del teorema y que no se puede garantizar que se ejecuten de manera secuencialmente consistente.
El modelo de memoria DRF1 [10] proporciona SC para DRF y permite las optimizaciones de los modelos WO (ordenamiento débil), RCsc ( consistencia de liberación con operaciones especiales secuencialmente consistentes), modelo de memoria VAX y modelos de memoria data-race-free-0. El modelo de memoria PLpc [11] proporciona SC para DRF y permite las optimizaciones de los modelos TSO (orden de almacenamiento total), PSO, PC ( consistencia del procesador ) y RCpc ( consistencia de liberación con operaciones especiales de consistencia del procesador). DRFrlx [12] proporciona un esbozo de un teorema SC para DRF en presencia de atómicos relajados.
Muchas condiciones de carrera de software tienen implicaciones asociadas para la seguridad informática . Una condición de carrera permite que un atacante con acceso a un recurso compartido provoque un mal funcionamiento de otros actores que utilizan ese recurso, lo que da lugar a efectos como la denegación de servicio [13] y la escalada de privilegios . [14] [15]
Un tipo específico de condición de carrera implica la verificación de un predicado (por ejemplo, autenticación ) y luego actuar sobre el predicado, mientras que el estado puede cambiar entre el momento de la verificación y el momento del uso . Cuando este tipo de error existe en un código sensible a la seguridad, se crea una vulnerabilidad de seguridad denominada error de tiempo de verificación a tiempo de uso ( TOCTTOU ).
Las condiciones de carrera también se utilizan intencionalmente para crear generadores de números aleatorios de hardware y funciones físicamente no clonables . [16] [ cita requerida ] Las PUF se pueden crear diseñando topologías de circuitos con rutas idénticas a un nodo y confiando en variaciones de fabricación para determinar aleatoriamente qué rutas se completarán primero. Al medir el conjunto específico de resultados de condiciones de carrera de cada circuito fabricado, se puede recopilar un perfil para cada circuito y mantenerlo en secreto para verificar más tarde la identidad de un circuito.
Dos o más programas pueden colisionar en sus intentos de modificar o acceder a un sistema de archivos, lo que puede provocar la corrupción de datos o la escalada de privilegios. [14] El bloqueo de archivos proporciona una solución de uso común. Un remedio más engorroso implica organizar el sistema de tal manera que un único proceso (que ejecute un demonio o similar) tenga acceso exclusivo al archivo, y todos los demás procesos que necesiten acceder a los datos de ese archivo lo hagan solo a través de la comunicación entre procesos con ese proceso. Esto requiere sincronización a nivel de proceso.
Existe una forma diferente de condición de carrera en los sistemas de archivos, donde programas no relacionados pueden afectarse entre sí al utilizar repentinamente recursos disponibles, como espacio en disco, espacio de memoria o ciclos de procesador. El software que no está diseñado cuidadosamente para anticipar y manejar esta situación de carrera puede volverse impredecible. Tal riesgo puede pasarse por alto durante mucho tiempo en un sistema que parece muy confiable. Pero eventualmente se pueden acumular suficientes datos o se puede agregar suficiente otro software para desestabilizar críticamente muchas partes de un sistema. Un ejemplo de esto ocurrió con la casi pérdida del Mars Rover "Spirit" poco después del aterrizaje, que ocurrió debido a que las entradas de archivo eliminadas hicieron que la biblioteca del sistema de archivos consumiera todo el espacio de memoria disponible. [17] Una solución es que el software solicite y reserve todos los recursos que necesitará antes de comenzar una tarea; si esta solicitud falla, entonces la tarea se pospone, evitando los muchos puntos en los que podría haber ocurrido un fallo. Alternativamente, cada uno de esos puntos puede estar equipado con manejo de errores, o se puede verificar el éxito de toda la tarea después, antes de continuar. Un enfoque más común es simplemente verificar que haya suficientes recursos del sistema disponibles antes de comenzar una tarea; Sin embargo, esto puede no ser adecuado porque en sistemas complejos las acciones de otros programas en ejecución pueden ser impredecibles.
En el ámbito de las redes, pensemos en una red de chat distribuida como IRC , en la que un usuario que inicia un canal adquiere automáticamente privilegios de operador de canal. Si dos usuarios de servidores diferentes, en extremos diferentes de la misma red, intentan iniciar el canal con el mismo nombre al mismo tiempo, el servidor respectivo de cada usuario concederá privilegios de operador de canal a cada usuario, ya que ninguno de los servidores habrá recibido aún la señal del otro servidor de que ha asignado ese canal. (Este problema se ha solucionado en gran medida mediante varias implementaciones de servidores IRC).
En este caso de una condición de carrera, el concepto de " recurso compartido " cubre el estado de la red (qué canales existen, así como qué usuarios los iniciaron y, por lo tanto, tienen qué privilegios), que cada servidor puede cambiar libremente siempre que indique a los demás servidores de la red sobre los cambios para que puedan actualizar su concepción del estado de la red. Sin embargo, la latencia en toda la red hace posible el tipo de condición de carrera descrita. En este caso, evitar las condiciones de carrera imponiendo una forma de control sobre el acceso al recurso compartido (por ejemplo, designando a un servidor para que controle quién tiene qué privilegios) significaría convertir la red distribuida en una red centralizada (al menos para esa parte de la operación de la red).
También pueden existir condiciones de carrera cuando un programa de computadora está escrito con sockets no bloqueantes , en cuyo caso el rendimiento del programa puede depender de la velocidad del enlace de red.
Los fallos de software en sistemas vitales pueden ser desastrosos. Las condiciones de carrera fueron uno de los fallos en la máquina de radioterapia Therac-25 , que provocaron la muerte de al menos tres pacientes y heridas a varios más. [18]
Otro ejemplo es el sistema de gestión de energía proporcionado por GE Energy y utilizado por FirstEnergy Corp, con sede en Ohio (entre otras instalaciones eléctricas). Existía una condición de carrera en el subsistema de alarma; cuando tres líneas eléctricas caídas se activaron simultáneamente, la condición impidió que se enviaran alertas a los técnicos de monitoreo, lo que retrasó su conocimiento del problema. Esta falla de software finalmente llevó al apagón norteamericano de 2003. [ 19] GE Energy desarrolló más tarde un parche de software para corregir el error previamente no descubierto.
Existen muchas herramientas de software que ayudan a detectar condiciones de carrera en el software. Se pueden clasificar en dos grupos: herramientas de análisis estático y herramientas de análisis dinámico .
Thread Safety Analysis es una herramienta de análisis estático para el análisis estático intraprocedimental basado en anotaciones, originalmente implementada como una rama de gcc y ahora reimplementada en Clang , compatible con PThreads. [20] [ se necesita una fuente no primaria ]
Las herramientas de análisis dinámico incluyen:
Existen varios puntos de referencia diseñados para evaluar la eficacia de las herramientas de detección de carreras de datos.
La neurociencia está demostrando que las condiciones raciales también pueden darse en los cerebros de los mamíferos. [25] [26]
En la señalización ferroviaria del Reino Unido , se produciría una condición de carrera en el cumplimiento de la regla 55. Según esta regla, si un tren se detenía en una vía en marcha debido a una señal, el fogonero de la locomotora se dirigía a la cabina de señales para recordarle que el tren estaba presente. En al menos un caso, en Winwick en 1934, se produjo un accidente porque el fogonero aceptó otro tren antes de que llegara el fogonero. La práctica de señalización moderna elimina la condición de carrera al hacer posible que el conductor se ponga en contacto instantáneamente con la cabina de señales por radio.
