La ingeniería de software basada en búsquedas ( SBSE ) aplica técnicas de búsqueda metaheurísticas como algoritmos genéticos , recocido simulado y búsqueda tabú a problemas de ingeniería de software . Muchas actividades de la ingeniería de software pueden definirse como problemas de optimización . Las técnicas de optimización de la investigación de operaciones , como la programación lineal o la programación dinámica, a menudo no son prácticas para problemas de ingeniería de software a gran escala debido a su complejidad computacional.o sus supuestos sobre la estructura del problema. Los investigadores y profesionales utilizan técnicas de búsqueda metaheurísticas , que imponen pequeñas suposiciones sobre la estructura del problema, para encontrar soluciones casi óptimas o "suficientemente buenas".
Los problemas de SBSE se pueden dividir en dos tipos:
- Problemas de optimización de caja negra, por ejemplo, asignar personas a tareas (un problema típico de optimización combinatoria ).
- Problemas de caja blanca en los que es necesario considerar las operaciones sobre el código fuente. [1]
Definición
SBSE convierte un problema de ingeniería de software en un problema de búsqueda computacional que se puede abordar con una metaheurística . Se trata de definir un espacio de búsqueda o el conjunto de posibles soluciones. Este espacio suele ser demasiado grande para explorarlo exhaustivamente, lo que sugiere un enfoque metaheurístico . A continuación, se utiliza una métrica [2] (también denominada función de adecuación, función de coste, función objetivo o medida de calidad) para medir la calidad de las posibles soluciones. Muchos problemas de ingeniería de software pueden reformularse como un problema de búsqueda computacional. [3]
El término " aplicación basada en búsquedas ", por el contrario, se refiere al uso de tecnología de motor de búsqueda , en lugar de técnicas de búsqueda, en otra aplicación industrial.
Breve historia
Uno de los primeros intentos de aplicar la optimización a un problema de ingeniería de software fue informado por Webb Miller y David Spooner en 1976 en el área de pruebas de software . [4] En 1992, S. Xanthakis y sus colegas aplicaron una técnica de búsqueda a un problema de ingeniería de software por primera vez. [5] El término SBSE fue utilizado por primera vez en 2001 por Harman y Jones. [6] La comunidad de investigación creció hasta incluir más de 800 autores en 2013, abarcando aproximadamente 270 instituciones en 40 países. [7]
Áreas de aplicación
La ingeniería de software basada en búsquedas es aplicable a casi todas las fases del proceso de desarrollo de software . Las pruebas de software han sido una de las principales aplicaciones. [8] Las técnicas de búsqueda se han aplicado a otras actividades de ingeniería de software , por ejemplo, análisis de requisitos , [9] [10] diseño , [11] [12] refactorización , [13] desarrollo , [14] y mantenimiento . [15]
Ingeniería de requisitos
La ingeniería de requisitos es el proceso mediante el cual se determinan y gestionan las necesidades de los usuarios y el entorno de un software. Se han utilizado métodos basados en búsqueda para la selección y optimización de requisitos con el objetivo de encontrar el mejor subconjunto posible de requisitos que coincida con las solicitudes de los usuarios en medio de restricciones como recursos limitados e interdependencias entre requisitos. Este problema a menudo se aborda como un problema de toma de decisiones de múltiples criterios y, generalmente, implica presentar al tomador de decisiones un conjunto de buenos compromisos entre el costo y la satisfacción del usuario, así como el riesgo de los requisitos. [16] [17] [18] [19]
Depuración y mantenimiento
Identificar un error de software (o un olor a código ) y luego depurar (o refactorizar ) el software es en gran medida un esfuerzo manual y laborioso, aunque el proceso es compatible con herramientas. Uno de los objetivos de SBSE es identificar y corregir errores automáticamente (por ejemplo, mediante pruebas de mutación ).
La programación genética , una técnica de inspiración biológica que implica la evolución de programas mediante el uso de cruces y mutaciones, se ha utilizado para buscar reparaciones en programas mediante la alteración de algunas líneas de código fuente. El software de reparación del programa evolutivo GenProg reparó 55 de 105 errores por aproximadamente $ 8 cada uno en una prueba. [20]
La coevolución adopta una metáfora de "depredador y presa" en la que un conjunto de programas y un conjunto de pruebas unitarias evolucionan juntos y se influyen mutuamente. [21]
Pruebas
La ingeniería de software basada en búsquedas se ha aplicado a las pruebas de software, incluida la generación automática de casos de prueba (datos de prueba), la minimización de casos de prueba y la priorización de casos de prueba. [22] Las pruebas de regresión también han recibido cierta atención.
Optimización de software
El uso de SBSE en la optimización de programas , o la modificación de un software para hacerlo más eficiente en términos de velocidad y uso de recursos, ha sido objeto de una investigación exitosa. [23] En un caso, se mejoró genéticamente un programa de 50.000 líneas, lo que resultó en un programa 70 veces más rápido en promedio. [24] Un trabajo reciente de Basios et al. muestra que al optimizar la estructura de datos, Google Guava encontró una mejora del 9% en el tiempo de ejecución, una mejora del 13% en el consumo de memoria y una mejora del 4% en el uso de la CPU por separado. [25]
Gestión de proyectos
Varias decisiones que normalmente toma un director de proyecto se pueden tomar automáticamente, por ejemplo, la programación del proyecto. [26]
Herramientas
Las herramientas disponibles para SBSE incluyen OpenPAT. [27] y EvoSuite [28] y Cobertura , una herramienta de medición de cobertura de código para Python [29]
Métodos y técnicas
Hay varios métodos y técnicas disponibles, que incluyen:
- Elaboración de perfiles [30] mediante instrumentación para supervisar determinadas partes de un programa a medida que se ejecuta.
- Obtener un árbol de sintaxis abstracto asociado con el programa, que se puede examinar automáticamente para obtener información sobre su estructura.
- Las aplicaciones de la división de programas relevantes para SBSE incluyen el mantenimiento , la optimización y el análisis de programas de software .
- La cobertura de código permite medir la cantidad de código que se ejecuta con un conjunto dado de datos de entrada.
- Análisis de programa estático
Aceptación de la industria
Como área de investigación relativamente nueva, SBSE aún no ha experimentado una amplia aceptación en la industria.
Las aplicaciones exitosas de SBSE en la industria se pueden encontrar principalmente dentro de las pruebas de software, donde la capacidad de generar automáticamente entradas de prueba aleatorias para descubrir errores a gran escala es atractiva para las empresas. En 2017, Facebook adquirió la startup de software Majicke Limited que desarrolló Sapienz, una aplicación de búsqueda de errores basada en búsquedas. [31]
En otros escenarios de aplicación, los ingenieros de software pueden mostrarse reacios a adoptar herramientas sobre las que tienen poco control o que generan soluciones diferentes a las que producen los humanos. [32] En el contexto del uso de SBSE para corregir o mejorar programas, los desarrolladores deben estar seguros de que cualquier modificación producida automáticamente no genera un comportamiento inesperado fuera del alcance de los requisitos del sistema y el entorno de prueba. Teniendo en cuenta que aún no se ha logrado la programación completamente automatizada, una propiedad deseable de tales modificaciones sería que deben ser entendidas fácilmente por los humanos para respaldar las actividades de mantenimiento. [33]
Otra preocupación es que SBSE podría hacer que el ingeniero de software sea superfluo. Los partidarios afirman que la motivación de SBSE es mejorar la relación entre el ingeniero y el programa. [34]
Ver también
- Análisis de programas (informática)
- Análisis dinámico de programas
- Mejora genética
Referencias
- ^ Harman, Mark (2010). "Por qué el análisis y la manipulación del código fuente siempre serán importantes". Décima Conferencia de Trabajo de IEEE sobre Análisis y Manipulación de Código Fuente (SCAM 2010) . Décima Conferencia de Trabajo de IEEE sobre Análisis y Manipulación de Código Fuente (SCAM 2010). págs. 7-19. doi : 10.1109 / SCAM.2010.28 .
- ^ Harman, Mark; John A. Clark (2004). "Las métricas también son funciones de fitness". Actas del X Simposio Internacional sobre Métricas de Software, 2004 . Décimo Simposio Internacional sobre Métricas de Software, 2004. págs. 58–69. doi : 10.1109 / METRIC.2004.1357891 .
- ^ Clark, John A .; Dolado, José Javier; Harman, Mark; Hierons, Robert M .; Jones, Bryan F .; Lumkin, M .; Mitchell, Brian S .; Mancoridis, Spiros; Rees, K .; Roper, Marc; Shepperd, Martin J. (2003). "Reformular la ingeniería de software como problema de búsqueda". Actas de la IEE - Software . 150 (3): 161-175. CiteSeerX 10.1.1.144.3059 . doi : 10.1049 / ip-sen: 20030559 . ISSN 1462-5970 .
- ^ Miller, Webb; Spooner, David L. (1976). "Generación automática de datos de prueba de punto flotante". Transacciones IEEE sobre ingeniería de software . SE-2 (3): 223–226. doi : 10.1109 / TSE.1976.233818 . ISSN 0098-5589 . S2CID 18875300 .
- ^ S. Xanthakis, C. Ellis, C. Skourlas, A. Le Gall, S. Katsikas y K. Karapoulios, "Aplicación de algoritmos genéticos a las pruebas de software", en Actas de la Quinta Conferencia Internacional sobre Ingeniería de Software y sus Aplicaciones , Toulouse, Francia, 1992, págs. 625–636
- ^ Harman, Mark; Jones, Bryan F. (15 de diciembre de 2001). "Ingeniería de software basada en búsquedas". Tecnología de la información y el software . 43 (14): 833–839. CiteSeerX 10.1.1.143.9716 . doi : 10.1016 / S0950-5849 (01) 00189-6 . ISSN 0950-5849 .
- ^ Harman, Mark; Mansouri, S. Afshin; Zhang, Yuanyuan (1 de noviembre de 2012). "Ingeniería de software basada en búsquedas: tendencias, técnicas y aplicaciones" . Encuestas de computación ACM . 45 (1): 1–61. doi : 10.1145 / 2379776.2379787 . S2CID 207198163 .
- ^ McMinn, Phil (2004). "Generación de datos de prueba de software basado en búsquedas: una encuesta". Pruebas, verificación y confiabilidad de software . 14 (2): 105-156. CiteSeerX 10.1.1.122.33 . doi : 10.1002 / stvr.294 . ISSN 1099-1689 .
- ^ Greer, Des; Ruhe, Guenther (15 de marzo de 2004). "Planificación de lanzamiento de software: un enfoque evolutivo e iterativo". Tecnología de la información y el software . 46 (4): 243-253. CiteSeerX 10.1.1.195.321 . doi : 10.1016 / j.infsof.2003.07.002 . ISSN 0950-5849 .
- ^ Colares, Felipe; Souza, Jerffeson; Carmo, Rafael; Pádua, Clarindo; Mateus, Geraldo R. (2009). "Un nuevo enfoque para la planificación del lanzamiento de software". XXIII Simposio Brasileño de Ingeniería de Software, 2009. SBES '09 . XXIII Simposio Brasileño de Ingeniería de Software, 2009. SBES '09. págs. 207–215. doi : 10.1109 / SBES.2009.23 .
- ^ Clark, John A .; Jacob, Jeremy L. (15 de diciembre de 2001). "Los protocolos también son programas: la búsqueda metaheurística de protocolos de seguridad". Tecnología de la información y el software . 43 (14): 891–904. CiteSeerX 10.1.1.102.6016 . doi : 10.1016 / S0950-5849 (01) 00195-1 . ISSN 0950-5849 .
- ^ Räihä, Outi (1 de noviembre de 2010). "Una encuesta sobre el diseño de software basado en búsquedas" (PDF) . Revisión de Ciencias de la Computación . 4 (4): 203–249. doi : 10.1016 / j.cosrev.2010.06.001 . ISSN 1574-0137 .
- ^ Mariani, Thainá; Vergilio, Silvia Regina (1 de marzo de 2017). "Una revisión sistemática sobre la refactorización basada en búsquedas". Tecnología de la información y el software . 83 : 14–34. doi : 10.1016 / j.infsof.2016.11.009 . ISSN 0950-5849 .
- ^ Alba, Enrique; Chicano, J. Francisco (1 de junio de 2007). "Gestión de proyectos de software con GAs". Ciencias de la información . 177 (11): 2380–2401. doi : 10.1016 / j.ins.2006.12.020 . hdl : 10630/8145 . ISSN 0020-0255 .
- ^ Antoniol, Giuliano; Di Penta, Massimiliano; Harman, Mark (2005). "Técnicas basadas en búsquedas aplicadas a la optimización de la planificación de proyectos para un proyecto de mantenimiento masivo". Actas de la 21ª Conferencia Internacional IEEE sobre Mantenimiento de Software, 2005. ICSM'05 . Actas de la 21ª Conferencia Internacional IEEE sobre Mantenimiento de Software, 2005. ICSM'05. págs. 240–249. CiteSeerX 10.1.1.63.8069 . doi : 10.1109 / ICSM.2005.79 .
- ^ Zhang, Yuanyuan (febrero de 2010). Selección y optimización de requisitos basados en búsquedas multiobjetivo (PhD). Strand, Londres, Reino Unido: Universidad de Londres.
- ^ Y. Zhang y M. Harman y S. L. Lim, " Optimización basada en búsquedas de gestión de interacción de requisitos ", Departamento de informática, University College London, Nota de investigación RN / 11/12, 2011.
- ^ Li, Lingbo; Harman, Mark; Letier, Emmanuel; Zhang, Yuanyuan (2014). Problema robusto de la próxima versión: manejo de la incertidumbre durante la optimización . Actas de la Conferencia Anual de 2014 sobre Computación Genética y Evolutiva . Gecco '14. págs. 1247-1254. doi : 10.1145 / 2576768.2598334 . ISBN 9781450326629. S2CID 8423690 .
- ^ Pequeño.; Harman, M .; Wu, F .; Zhang, Y. (2017). "El valor del análisis exacto en la selección de requisitos" (PDF) . Transacciones IEEE sobre ingeniería de software . 43 (6): 580–596. doi : 10.1109 / TSE.2016.2615100 . ISSN 0098-5589 . S2CID 8398275 .
- ^ Le Goues, Claire; Dewey-Vogt, Michael; Forrest, Stephanie; Weimer, Westley (2012). "Un estudio sistemático de reparación de programas automatizados: corrección de 55 de 105 errores por $ 8 cada uno". 2012 34º Congreso Internacional de Ingeniería de Software (ICSE) . 2012 34º Congreso Internacional de Ingeniería de Software (ICSE). págs. 3-13. doi : 10.1109 / ICSE.2012.6227211 .
- ^ Arcuri, Andrea; Yao, Xin (2008). "Un enfoque coevolutivo novedoso para la corrección automática de errores de software". Congreso IEEE sobre Computación Evolutiva, 2008. CEC 2008. (Congreso Mundial IEEE sobre Inteligencia Computacional) . Congreso IEEE sobre Computación Evolutiva, 2008. CEC 2008. (Congreso Mundial IEEE sobre Inteligencia Computacional). págs. 162-168. doi : 10.1109 / CEC.2008.4630793 .
- ^ Harman, Mark; Jia, Yue; Zhang, Yuanyuan (abril de 2015). "Logros, problemas abiertos y desafíos para las pruebas de software basadas en búsquedas". 2015 IEEE 8th International Conference on Software Testing, Verification and Validation (ICST) . Graz, Austria: IEEE: 1–12. CiteSeerX 10.1.1.686.7418 . doi : 10.1109 / ICST.2015.7102580 . ISBN 978-1-4799-7125-1. S2CID 15272060 .
- ^ Memeti, Suejb; Pllana, Sabri; Binotto, Alecio; Kolodziej, Joanna; Brandic, Ivona (2018). "Uso de metaheurística y aprendizaje automático para la optimización de software de sistemas informáticos paralelos: una revisión sistemática de la literatura". Computación . 101 (8): 893–936. arXiv : 1801.09444 . Código bibliográfico : 2018arXiv180109444M . doi : 10.1007 / s00607-018-0614-9 . S2CID 13868111 .
- ^ Langdon, William B .; Harman, Mark. "Optimización del software existente con programación genética" (PDF) . Transacciones IEEE sobre Computación Evolutiva .
- ^ Basios, Michail; Li, Lingbo; Wu, Fan; Kanthan, Leslie; Barr, Earl T. (9 de septiembre de 2017). Optimización de estructuras de datos darwinianas en Google Guava (PDF) . Ingeniería de software basada en búsquedas . Apuntes de conferencias en Ciencias de la Computación. 10452 . págs. 161-167. doi : 10.1007 / 978-3-319-66299-2_14 . ISBN 978-3-319-66298-5.
- ^ Minku, Leandro L .; Sudholt, Dirk; Yao, Xin (2012). "Algoritmos evolutivos para el problema de programación de proyectos: análisis en tiempo de ejecución y diseño mejorado". Actas de la decimocuarta conferencia internacional sobre genética y computación evolutiva . GECCO '12. Nueva York, NY, EE.UU .: ACM. págs. 1221-1228. doi : 10.1145 / 2330163.2330332 . ISBN 978-1-4503-1177-9.
- ^ Mayo, M .; Spacey, S. (2013). Predicción de fallas en las pruebas de regresión mediante métricas de análisis de rendimiento dinámico seleccionadas por algoritmos genéticos (PDF) . Actas del 5º Simposio Internacional sobre Ingeniería de Software basada en búsquedas (SSBSE) . 8084 . págs. 158-171. doi : 10.1007 / 978-3-642-39742-4_13 . hdl : 10289/7763 .
- ^ ( http://www.evosuite.org/ )
- ^ otros, Ned Batchelder y 100, cobertura: medición de cobertura de código para Python , consultado el 14 de marzo de 2018
- ^ "Perfiladores de código abierto en Java" .
- ^ "Sapienz: el impulso de Facebook para automatizar las pruebas de software" . VentureBeat . 30 de diciembre de 2018 . Consultado el 29 de septiembre de 2020 .
- ^ Jones, Derek (18 de octubre de 2013). "Programar usando algoritmos genéticos: ¿no es eso lo que ya hacen los humanos ?-)" . La forma del código . Consultado el 31 de octubre de 2013 .
- ^ Le Goues, Claire; Forrest, Stephanie; Weimer, Westley (1 de septiembre de 2013). "Desafíos actuales en la reparación automática de software". Revista de calidad de software . 21 (3): 421–443. CiteSeerX 10.1.1.371.5784 . doi : 10.1007 / s11219-013-9208-0 . ISSN 1573-1367 . S2CID 16435531 .
- ^ Simons, Christopher L. (mayo de 2013). ¿Adónde (lejos) los ingenieros de software en SBSE? . Primer taller internacional sobre la combinación del modelado con la ingeniería de software basada en búsquedas, primer taller internacional sobre la combinación del modelado con la ingeniería de software basada en la búsqueda. San Francisco, Estados Unidos: IEEE Press. págs. 49–50 . Consultado el 31 de octubre de 2013 .
enlaces externos
- Repositorio de publicaciones sobre SBSE
- Ingeniería de software y metaheurística
- Repositorio de infraestructura de artefactos de software
- Congreso Internacional de Ingeniería de Software
- Computación genética y evolutiva (GECCO)
- Página de Google Académico sobre ingeniería de software basada en búsquedas