Corrección automática de errores - Automatic bug fixing

La corrección automática de errores es la reparación automática de errores de software sin la intervención de un programador humano. También se conoce comúnmente como generación automática de parches , reparación automática de errores o reparación automática de programas . El objetivo típico de estas técnicas es generar automáticamente los parches correctos para eliminar errores en los programas de software sin provocar la regresión del software .

Especificación

La corrección automática de errores se realiza de acuerdo con una especificación del comportamiento esperado que puede ser, por ejemplo, una especificación formal o un conjunto de pruebas .

Un conjunto de pruebas: los pares de entrada / salida especifican la funcionalidad del programa, posiblemente capturado en aserciones y se puede usar como un oráculo de prueba para impulsar la búsqueda. De hecho, este oráculo se puede dividir entre el oráculo de errores que expone el comportamiento defectuoso y el oráculo de regresión , que encapsula la funcionalidad que debe preservar cualquier método de reparación de programa. Tenga en cuenta que un conjunto de pruebas suele estar incompleto y no cubre todos los casos posibles. Por lo tanto, a menudo es posible que un parche validado produzca salidas esperadas para todas las entradas en el conjunto de pruebas, pero salidas incorrectas para otras entradas. La existencia de estos parches validados pero incorrectos es un desafío importante para las técnicas de generación y validación. Las técnicas recientes exitosas de corrección automática de errores a menudo se basan en información adicional que no sea el conjunto de pruebas, como la información obtenida de parches humanos anteriores, para identificar aún más los parches correctos entre los parches validados.

Otra forma de especificar el comportamiento esperado es utilizar especificaciones formales. La verificación contra especificaciones completas que especifican todo el comportamiento del programa, incluidas las funcionalidades, es menos común porque tales especificaciones no suelen estar disponibles en la práctica y el costo de cálculo de dicha verificación es prohibitivo. Sin embargo, para clases específicas de errores, a menudo se encuentran disponibles especificaciones parciales implícitas. Por ejemplo, existen técnicas específicas de corrección de errores que validan que el programa parcheado ya no puede desencadenar errores de desbordamiento en la misma ruta de ejecución.

Técnicas

Generar y validar

Los enfoques de generación y validación compilan y prueban cada parche candidato para recopilar todos los parches validados que producen los resultados esperados para todas las entradas en el conjunto de pruebas. Esta técnica normalmente comienza con un conjunto de pruebas del programa, es decir, un conjunto de casos de prueba , al menos uno de los cuales expone el error. Uno de los primeros sistemas de corrección de errores de generación y validación es GenProg. La eficacia de las técnicas de generación y validación sigue siendo controvertida, ya que normalmente no ofrecen garantías de corrección de parches . No obstante, los resultados comunicados de las últimas técnicas de vanguardia son, en general, prometedores. Por ejemplo, en 69 errores del mundo real recopilados sistemáticamente en ocho grandes programas de software C, el sistema de corrección de errores de última generación Prophet genera los parches correctos para 18 de los 69 errores.

Una forma de generar parches candidatos es aplicar operadores de mutación en el programa original. Los operadores de mutación manipulan el programa original, potencialmente a través de su representación de árbol de sintaxis abstracta , o una representación más burda, como operar a nivel de instrucción o nivel de bloque . Los enfoques de mejora genética anteriores operan a nivel de declaración y llevan a cabo operaciones simples de eliminación / reemplazo, como eliminar una declaración existente o reemplazar una declaración existente con otra declaración en el mismo archivo fuente. Los enfoques recientes utilizan operadores más detallados en el nivel del árbol de sintaxis abstracta para generar un conjunto más diverso de parches candidatos.

Otra forma de generar parches candidatos consiste en utilizar plantillas de arreglos. Las plantillas de corrección suelen ser cambios predefinidos para corregir clases específicas de errores. Los ejemplos de plantillas de corrección incluyen insertar una declaración condicional para verificar si el valor de una variable es nulo para corregir la excepción de puntero nulo, o cambiar una constante entera por uno para corregir errores uno por uno. También es posible extraer automáticamente plantillas de arreglos para enfoques de generación y validación.

Muchas técnicas de generación y validación se basan en la información de la redundancia: el código del parche se puede encontrar en otra parte de la aplicación. Esta idea se introdujo en el sistema Genprog, donde dos operadores, la adición y el reemplazo de nodos AST, se basaron en código tomado de otra parte (es decir, agregando un nodo AST existente). Esta idea ha sido validada empíricamente, con dos estudios independientes que han demostrado que una proporción significativa de confirmaciones (3% -17%) se componen de código existente. Más allá del hecho de que el código para reutilizar existe en otro lugar, también se ha demostrado que el contexto de los ingredientes de reparación potenciales es útil: a menudo, el contexto del donante es similar al contexto del receptor.

Basado en síntesis

Existen técnicas de reparación que se basan en la ejecución simbólica. Por ejemplo, Semfix usa la ejecución simbólica para extraer una restricción de reparación. Angelix introdujo el concepto de bosque angelical para tratar los parches de varias líneas.

Bajo ciertos supuestos, es posible plantear el problema de reparación como un problema de síntesis. SemFix y Nopol utilizan síntesis basada en componentes. Dynamoth utiliza síntesis dinámica. S3 se basa en síntesis guiada por sintaxis. SearchRepair convierte los parches potenciales en una fórmula SMT y consulta los parches candidatos que permiten que el programa parcheado pase todos los casos de prueba suministrados.

Basado en datos

Las técnicas de aprendizaje automático pueden mejorar la eficacia de los sistemas automáticos de corrección de errores. Un ejemplo de tales técnicas se aprende de los parches anteriores exitosos de desarrolladores humanos recopilados de repositorios de código abierto en GitHub y SourceForge . Luego, utiliza la información aprendida para reconocer y priorizar los parches potencialmente correctos entre todos los parches candidatos generados. Alternativamente, los parches se pueden extraer directamente de fuentes existentes. Los enfoques de ejemplo incluyen la extracción de parches de aplicaciones de donantes o de sitios web de control de calidad. El aprendizaje se puede realizar en línea, también conocido como aprendizaje continuo, con el precedente conocido del aprendizaje en línea de parches del flujo de resultados de compilación de código abierto de la integración continua.

SequenceR usa el aprendizaje secuencia a secuencia en el código fuente para generar parches de una línea. Define una arquitectura de red neuronal que funciona bien con el código fuente, con el mecanismo de copia que permite producir parches con tokens que no están en el vocabulario aprendido. Esos tokens se toman del código de la clase Java en reparación.

Getafix es un enfoque independiente del lenguaje desarrollado y utilizado en la producción en Facebook . Dada una muestra de confirmaciones de código donde los ingenieros corrigieron cierto tipo de error, aprende patrones de corrección similares a los humanos que se aplican a errores futuros del mismo tipo. Además de utilizar los propios repositorios de código de Facebook como datos de entrenamiento, Getafix aprendió algunas correcciones de los repositorios de código abierto de Java. Cuando se detectan nuevos errores, Getafix aplica sus patrones previamente aprendidos para producir posibles correcciones y las clasifica en segundos. Presenta solo la solución mejor clasificada para la validación final por parte de herramientas o un ingeniero, con el fin de ahorrar recursos y, idealmente, ser tan rápido que aún no se haya dedicado tiempo humano a corregir el mismo error.

Otro

Las técnicas de corrección de errores automáticas dirigidas generan reparaciones para clases específicas de errores, como desbordamiento de enteros de excepción de puntero nulo , desbordamiento de búfer , pérdida de memoria , etc. Estas técnicas a menudo utilizan plantillas de corrección empírica para corregir errores en el alcance objetivo. Por ejemplo, inserte una declaración condicional para verificar si el valor de una variable es nulo o inserte declaraciones de desasignación de memoria que faltan. En comparación con las técnicas de generación y validación, las técnicas dirigidas tienden a tener una mejor precisión en la corrección de errores, pero un alcance mucho más reducido.

Usar

Existen múltiples usos de la corrección automática de errores:

  • En un entorno de desarrollo: cuando encuentra un error, el desarrollador activa una función para buscar un parche (por ejemplo, haciendo clic en un botón). Esta búsqueda también puede ocurrir en segundo plano, cuando el IDE busca de forma proactiva soluciones a problemas potenciales, sin esperar una acción explícita del desarrollador.
  • En un servidor de integración continua: cuando una compilación falla durante la integración continua, se puede intentar una búsqueda de parches tan pronto como la compilación haya fallado. Si la búsqueda tiene éxito, se le proporciona el parche al desarrollador. Cuando se sugiere a los desarrolladores un parche sintetizado como solicitud de extracción, se debe proporcionar una explicación además de los cambios de código (por ejemplo, un título y una descripción de la solicitud de extracción). Un experimento ha demostrado que los desarrolladores de código abierto pueden aceptar los parches generados y fusionarlos en el repositorio de código.
  • En tiempo de ejecución: cuando ocurre una falla en tiempo de ejecución, se puede buscar un parche binario y aplicarlo en línea . Un ejemplo de un sistema de reparación de este tipo es ClearView, que repara en código x86, con parches binarios x86. El sistema Itzal es diferente de Clearview: mientras que la búsqueda de reparación ocurre en tiempo de ejecución, en producción, los parches producidos están en el nivel del código fuente. El sistema BikiniProxy repara en línea los errores de JavaScript que ocurren en el navegador.

Espacio de búsqueda

En esencia, la corrección automática de errores es una actividad de búsqueda, ya sea de base deductiva o heurística. El espacio de búsqueda de la corrección automática de errores se compone de todas las ediciones que se pueden realizar en un programa. Se han realizado estudios para comprender la estructura de este espacio de búsqueda. Qi y col. demostró que la función de aptitud original de Genprog no es mejor que la búsqueda aleatoria para impulsar la búsqueda. Martinez y col. exploró el desequilibrio entre posibles acciones de reparación, mostrando su impacto significativo en la búsqueda. El estudio de Long et al. Indicó que los parches correctos pueden considerarse escasos en el espacio de búsqueda y que los parches de sobreajuste incorrectos son mucho más abundantes (ver también la discusión sobre sobreajuste a continuación).

Si uno enumera explícitamente todas las variantes posibles en un algoritmo de reparación, esto define un espacio de diseño para la reparación del programa. Cada variante selecciona un algoritmo involucrado en algún punto del proceso de reparación (por ejemplo, el algoritmo de localización de fallas), o selecciona una heurística específica que produce diferentes parches. Por ejemplo, en el espacio de diseño de la reparación de programas de generación y validación, hay un punto de variación sobre la granularidad de los elementos del programa que se van a modificar: una expresión, una declaración, un bloque, etc.

Sobreajuste

A veces, en la reparación de programas basada en el conjunto de pruebas, las herramientas generan parches que pasan el conjunto de pruebas, pero en realidad son incorrectos, esto se conoce como el problema de "sobreajuste". "Sobreajuste" en este contexto se refiere al hecho de que el parche se adapta a las entradas de prueba. Hay diferentes tipos de sobreajuste: la reparación incompleta significa que solo se corrigen algunas entradas con errores, la introducción de regresión significa que algunas características que funcionaban anteriormente se rompen después del parche (porque no se probaron correctamente). Los primeros prototipos para la reparación automática sufrieron mucho por el sobreajuste: en el banco de pruebas Manybugs C, Qi et al. informó que 104/110 de los parches GenProg plausibles estaban sobreajustados; en el banco de pruebas Defects4J Java, Martinez et al. informó que 73/84 parches plausibles como sobreajustados. En el contexto de la reparación basada en síntesis, Le et al. obtuvo más del 80% de parches de sobreajuste.

Una forma de evitar el sobreajuste es filtrar los parches generados. Esto se puede hacer en base a un análisis dinámico o un análisis de código estático de los parches generados. Cuando un parche de referencia está disponible, una técnica de vanguardia es generar pruebas basadas en la versión parcheada, de modo que las pruebas generadas capturen el comportamiento esperado. Si bien el muestreo del dominio de entrada por generación de prueba está incompleto por construcción, se ha demostrado que es eficaz para detectar parches de sobreajuste e incluso para encontrar errores humanos cometidos durante la clasificación manual de parches.

Limitaciones de la corrección automática de errores

Las técnicas automáticas de corrección de errores que se basan en un conjunto de pruebas no ofrecen garantías de corrección de parches, porque el conjunto de pruebas está incompleto y no cubre todos los casos. Un conjunto de pruebas débil puede hacer que las técnicas de generación y validación produzcan parches validados pero incorrectos que tienen efectos negativos, como eliminar funcionalidades deseables, causar pérdidas de memoria e introducir vulnerabilidades de seguridad. Un enfoque posible es ampliar el conjunto de pruebas fallidas generando automáticamente más casos de prueba que luego se etiquetan como aprobados o fallidos. Para minimizar el esfuerzo de etiquetado humano, se puede entrenar un oráculo de prueba automático que aprende gradualmente a clasificar automáticamente los casos de prueba como aprobados o reprobados y solo involucra al usuario que informa de errores para los casos inciertos.

Una limitación de los sistemas de reparación de generación y validación es la explosión del espacio de búsqueda. Para un programa, hay una gran cantidad de declaraciones para cambiar y para cada declaración hay una gran cantidad de modificaciones posibles. Los sistemas de vanguardia abordan este problema asumiendo que una pequeña modificación es suficiente para corregir un error, lo que resulta en una reducción del espacio de búsqueda.

La limitación de los enfoques basados ​​en el análisis simbólico es que los programas del mundo real a menudo se convierten en fórmulas increíblemente grandes, especialmente para modificar declaraciones con efectos secundarios .

Benchmarks

Los puntos de referencia de errores suelen centrarse en un lenguaje de programación específico. En C, el punto de referencia Manybugs recopilado por los autores de GenProg contiene 69 defectos del mundo real y se usa ampliamente para evaluar muchas otras herramientas de corrección de errores para C.

En Java, el punto de referencia principal es Defects4J, inicialmente explorado por Martinez et al., Y ahora ampliamente utilizado en la mayoría de los trabajos de investigación sobre reparación de programas para Java. Existen puntos de referencia alternativos, como el punto de referencia Quixbugs, que contiene errores originales para la reparación del programa. Otros puntos de referencia de errores de Java incluyen Bugs.jar, basado en confirmaciones pasadas, y BEARS, que es un punto de referencia de fallas de compilación de integración continua.

Herramientas de ejemplo

La corrección automática de errores es un tema de investigación activo en informática. Hay muchas implementaciones de varias técnicas de corrección de errores, especialmente para programas C y Java. Tenga en cuenta que la mayoría de estas implementaciones son prototipos de investigación para demostrar sus técnicas, es decir, no está claro si sus implementaciones actuales están listas para uso industrial o no.

C

  • ClearView: una herramienta de generación y validación para generar parches binarios para sistemas implementados. Se evalúa en 10 casos de vulnerabilidad de seguridad. Un estudio posterior muestra que genera parches correctos para al menos 4 de los 10 casos.
  • GenProg: una herramienta fundamental para la corrección de errores de generación y validación. Se ha estudiado extensamente en el contexto del punto de referencia ManyBugs.
  • SemFix: la primera herramienta de corrección de errores basada en solucionador para C.
  • CodePhage: la primera herramienta de corrección de errores que transfiere directamente código entre programas para generar un parche para el programa C. Tenga en cuenta que aunque genera parches C, puede extraer código de programas binarios sin código fuente.
  • LeakFix: una herramienta que corrige automáticamente las pérdidas de memoria en los programas C.
  • Prophet: la primera herramienta de generación y validación que utiliza técnicas de aprendizaje automático para aprender conocimientos útiles de parches humanos anteriores para reconocer los parches correctos. Se evalúa con el mismo punto de referencia que GenProg y genera parches correctos (es decir, equivalentes a parches humanos) para 18 de 69 casos.
  • SearchRepair: una herramienta para reemplazar código defectuoso usando fragmentos de código de otra parte. Se evalúa en el punto de referencia IntroClass y genera parches de calidad mucho más alta en ese punto de referencia que GenProg, RSRepair y AE.
  • Angelix: una herramienta mejorada de corrección de errores basada en el solucionador. Se evalúa en el punto de referencia GenProg. Para 10 de los 69 casos, genera parches equivalentes a parches humanos.
  • Learn2Fix: la primera herramienta de reparación semiautomática "human-in-the-loop". Extiende GenProg para conocer la condición bajo la cual se observa un error semántico mediante consultas sistemáticas al usuario que informa el error. Solo funciona para programas que toman y producen números enteros.

Java

  • PAR: una herramienta de generación y validación que utiliza un conjunto de plantillas de arreglos definidas manualmente. Un estudio posterior planteó inquietudes sobre la posibilidad de generalizar las plantillas de corrección en PAR.
  • NOPOL: una herramienta basada en un solucionador que se centra en modificar las declaraciones de condiciones.
  • QACrashFix: una herramienta que corrige errores de bloqueo de Java mediante la extracción de correcciones del sitio web de preguntas y respuestas.
  • Astor: una biblioteca de reparación automática para Java, que contiene jGenProg, una implementación Java de GenProg.
  • ARJA: Una herramienta de reparación para Java basada en programación genética multiobjetivo.
  • NpeFix: una herramienta de reparación automática para NullPointerException en Java, disponible en Github .

Otros idiomas

  • AutoFixE: una herramienta de corrección de errores para el lenguaje Eiffel . Se basa en los contratos (es decir, una forma de especificación formal) en los programas Eiffel para validar los parches generados.
  • Getafix: opera exclusivamente en transformaciones AST y, por lo tanto, solo requiere un analizador y un formateador. En Facebook se ha aplicado a Hack , Java y Objective-C .

Propiedad

Referencias

enlaces externos

  • conjuntos de datos, herramientas, etc. de program-repair .org , relacionados con la investigación de reparación automatizada de programas.