stringtranslate.com

Ingeniería de software basada en búsquedas

La ingeniería de software basada en búsquedas ( SBSE ) aplica técnicas de búsqueda metaheurística , como algoritmos genéticos , recocido simulado y búsqueda tabú , a problemas de ingeniería de software . Muchas actividades de 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, suelen ser poco prácticas para problemas de ingeniería de software a gran escala debido a su complejidad computacional o sus suposiciones sobre la estructura del problema. Los investigadores y profesionales utilizan técnicas de búsqueda metaheurística , que imponen pocas suposiciones sobre la estructura del problema, para encontrar soluciones casi óptimas o "suficientemente buenas". [1]

Los problemas de SBSE se pueden dividir en dos tipos:

Definición

SBSE convierte un problema de ingeniería de software en un problema de búsqueda computacional que puede abordarse con una metaheurística . Esto implica definir un espacio de búsqueda, o el conjunto de posibles soluciones. Este espacio suele ser demasiado grande para ser explorado exhaustivamente, lo que sugiere un enfoque metaheurístico . Luego se utiliza una métrica [3] (también llamada función de aptitud, función de costo, 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. [4]

El término " aplicación basada en búsqueda ", 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 . [5] 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. [6] El término SBSE fue utilizado por primera vez en 2001 por Harman y Jones. [7] La ​​comunidad de investigación creció hasta incluir más de 800 autores en 2013, abarcando aproximadamente 270 instituciones en 40 países. [8]

Á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. [9] Las técnicas de búsqueda se han aplicado a otras actividades de ingeniería de software , por ejemplo, análisis de requisitos , [10] [11] diseño , [12] [13] refactorización , [14] desarrollo , [15] y mantenimiento . [16]

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 del entorno de un software. Se han utilizado métodos basados ​​en búsquedas para la selección y optimización de requisitos con el objetivo de encontrar el mejor subconjunto posible de requisitos que se ajuste a las solicitudes de los usuarios en medio de limitaciones como recursos limitados e interdependencias entre requisitos. Este problema se suele abordar como un problema de toma de decisiones con múltiples criterios y, por lo general, implica presentar al responsable de la toma de decisiones un conjunto de buenos compromisos entre el coste y la satisfacción del usuario, así como el riesgo de los requisitos. [17] [18] [19] [20]

Depuración y mantenimiento

Identificar un error de software (o un olor extraño en el código ) y luego depurarlo (o refactorizarlo ) es en gran medida una tarea manual y laboriosa, aunque el proceso está respaldado por 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 de programas alterando unas pocas líneas de código fuente. El software GenProg Evolutionary Program Repair reparó 55 de 105 errores por aproximadamente 8 dólares cada uno en una prueba. [21]

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 entre sí. [22]

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. [23] 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. [24] En un caso, un programa de 50.000 líneas fue mejorado genéticamente, lo que resultó en un programa 70 veces más rápido en promedio. [25] 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 CPU por separado. [26]

Gestión de proyectos

Una serie de decisiones que normalmente toma un director de proyectos se pueden realizar automáticamente, por ejemplo, la programación del proyecto. [27]

Herramientas

Las herramientas disponibles para SBSE incluyen OpenPAT, [28] EvoSuite , [29] y Coverage, una herramienta de medición de cobertura de código para Python. [30]

Métodos y técnicas

Hay varios métodos y técnicas disponibles, entre ellos:

Aceptación de la industria

Como área de investigación relativamente nueva, SBSE aún no experimenta una amplia aceptación en la industria.

Las aplicaciones exitosas de SBSE en la industria se pueden encontrar principalmente en las pruebas de software, donde la capacidad de generar automáticamente entradas de prueba aleatorias para descubrir errores a gran escala resulta atractiva para las empresas. En 2017, Facebook adquirió la startup de software Majicke Limited, que desarrolló Sapienz, una aplicación de búsqueda para encontrar errores. [32]

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 que son diferentes a las que producen los humanos. [33] 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 genere un comportamiento inesperado fuera del alcance de los requisitos y el entorno de prueba de un sistema. Considerando que aún no se ha logrado la programación completamente automatizada, una propiedad deseable de tales modificaciones sería que deben ser fácilmente entendidas por los humanos para respaldar las actividades de mantenimiento. [34]

Otra preocupación es que el SBSE podría hacer que el ingeniero de software fuera redundante. Los partidarios afirman que la motivación del SBSE es mejorar la relación entre el ingeniero y el programa. [35]

Véase también

Referencias

  1. ^ Mohan, M.; Greer, D. (1 de agosto de 2019). "Uso de un enfoque multiobjetivo para investigar la refactorización automatizada". Tecnología de la información y el software . 112 : 83–101. doi :10.1016/j.infsof.2019.04.009. ISSN  0950-5849.
  2. ^ Harman, Mark (2010). "Por qué el análisis y la manipulación del código fuente siempre serán importantes". 10.ª Conferencia de trabajo del IEEE sobre análisis y manipulación del código fuente (SCAM 2010) . 10.ª Conferencia de trabajo del IEEE sobre análisis y manipulación del código fuente (SCAM 2010). págs. 7–19. doi :10.1109/SCAM.2010.28.
  3. ^ Harman, Mark; John A. Clark (2004). "Las métricas también son funciones de aptitud". Actas del 10.º Simposio Internacional sobre Métricas de Software, 2004. 10.º Simposio Internacional sobre Métricas de Software, 2004. págs. 58–69. doi :10.1109/METRIC.2004.1357891.
  4. ^ 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). "Reformulando la ingeniería de software como un problema de búsqueda". Actas del IEE - Software . 150 (3): 161–175. CiteSeerX 10.1.1.144.3059 . doi :10.1049/ip-sen:20030559. ISSN  1462-5970. 
  5. ^ Miller, Webb; Spooner, David L. (1976). "Generación automática de datos de prueba de punto flotante". IEEE Transactions on Software Engineering . SE-2 (3): 223–226. doi :10.1109/TSE.1976.233818. ISSN  0098-5589. S2CID  18875300.
  6. ^ 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 5.ª Conferencia internacional sobre ingeniería de software y sus aplicaciones , Toulouse, Francia, 1992, págs. 625-636
  7. ^ 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. 
  8. ^ 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 informática de la ACM . 45 (1): 1–61. doi :10.1145/2379776.2379787. S2CID  207198163.
  9. ^ McMinn, Phil (2004). "Generación de datos de pruebas de software basada en búsquedas: una encuesta". Pruebas de software, verificación y confiabilidad . 14 (2): 105–156. CiteSeerX 10.1.1.122.33 . doi :10.1002/stvr.294. ISSN  1099-1689. S2CID  17408871. 
  10. ^ Greer, Des; Ruhe, Guenther (15 de marzo de 2004). "Planificación de la versión 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. S2CID  710923. 
  11. ^ Colares, Felipe; Souza, Jerffeson; Carmo, Raphael; Pádua, Clarindo; Mateus, Geraldo R. (2009). "Un nuevo enfoque para la planificación de la liberación 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. pp. doi :10.1109/SBES.2009.23.
  12. ^ 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. 
  13. ^ Räihä, Outi (1 de noviembre de 2010). "Una encuesta sobre el diseño de software basado en búsquedas" (PDF) . Computer Science Review . 4 (4): 203–249. CiteSeerX 10.1.1.188.9036 . doi :10.1016/j.cosrev.2010.06.001. ISSN  1574-0137. 
  14. ^ Mariani, Thainá; Vergilio, Silvia Regina (1 de marzo de 2017). "Una revisión sistemática sobre refactorización basada en búsqueda". Tecnología de la información y el software . 83 : 14–34. doi :10.1016/j.infsof.2016.11.009. ISSN  0950-5849.
  15. ^ Alba, Enrique; Chicano, J. Francisco (1 de junio de 2007). "Gestión de proyectos de software con AG". Ciencias de la Información . 177 (11): 2380–2401. doi :10.1016/j.ins.2006.12.020. hdl : 10630/8145 . ISSN  0020-0255.
  16. ^ 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. 
  17. ^ 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.
  18. ^ Y. Zhang y M. Harman y S. L. Lim, "Optimización basada en búsqueda de la gestión de interacción de requisitos", Departamento de Ciencias de la Computación, University College London, Nota de investigación RN/11/12, 2011.
  19. ^ Li, Lingbo; Harman, Mark; Letier, Emmanuel; Zhang, Yuanyuan (2014). "Problema de próxima versión robusta". 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.S2CID8423690  .​
  20. ^ Li, L.; Harman, M.; Wu, F.; Zhang, Y. (2017). "El valor del análisis exacto en la selección de requisitos" (PDF) . IEEE Transactions on Software Engineering . 43 (6): 580–596. doi :10.1109/TSE.2016.2615100. ISSN  0098-5589. S2CID  8398275.
  21. ^ Le Goues, Claire; Dewey-Vogt, Michael; Forrest, Stephanie; Weimer, Westley (2012). "Un estudio sistemático de la reparación automatizada de programas: reparación de 55 de 105 errores por 8 dólares cada uno". 2012 34.ª Conferencia Internacional sobre Ingeniería de Software (ICSE) . 2012 34.ª Conferencia Internacional sobre Ingeniería de Software (ICSE). págs. 3–13. doi :10.1109/ICSE.2012.6227211.
  22. ^ Arcuri, Andrea; Yao, Xin (2008). "Un nuevo enfoque coevolutivo 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). pp. 162–168. CiteSeerX 10.1.1.159.7991 . doi :10.1109/CEC.2008.4630793. 
  23. ^ 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. pp. 1–12. CiteSeerX 10.1.1.686.7418 . doi :10.1109/ICST.2015.7102580. ISBN  978-1-4799-7125-1. Número de identificación  S2C15272060.
  24. ^ Memeti, Suejb; Pllana, Sabri; Binotto, Alecio; Kolodziej, Joanna; Brandic, Ivona (2018). "Uso de metaheurísticas y aprendizaje automático para la optimización de software de sistemas de computación paralela: una revisión sistemática de la literatura". Computing . 101 (8): 893–936. arXiv : 1801.09444 . Bibcode :2018arXiv180109444M. doi :10.1007/s00607-018-0614-9. S2CID  13868111.
  25. ^ Langdon, William B.; Harman, Mark. "Optimización de software existente con programación genética" (PDF) . Transacciones IEEE sobre computación evolutiva .
  26. ^ 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". Ingeniería de software basada en búsquedas (PDF) . Apuntes de clase en informática. Vol. 10452. págs. 161–167. doi :10.1007/978-3-319-66299-2_14. ISBN 978-3-319-66298-5.
  27. ^ 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 computación genética y evolutiva . GECCO '12. Nueva York, NY, EE. UU.: ACM. págs. 1221–1228. doi :10.1145/2330163.2330332. ISBN . 978-1-4503-1177-9.
  28. ^ Mayo, M.; Spacey, S. (2013). "Predicción de fallas en pruebas de regresión mediante métricas de análisis de rendimiento dinámico seleccionadas por algoritmos genéticos" (PDF) . Ingeniería de software basada en búsquedas . Apuntes de clase en informática. Vol. 8084. págs. 158–171. doi :10.1007/978-3-642-39742-4_13. hdl : 10289/7763 . ISBN 978-3-642-39741-7.
  29. ^ "Inicio". evosuite.org .
  30. ^ Otros, Ned Batchelder y 100, Cobertura: Medición de cobertura de código para Python , consultado el 14 de marzo de 2018{{citation}}: CS1 maint: nombres numéricos: lista de autores ( enlace )
  31. ^ "Perfiladores de código abierto en Java".
  32. ^ "Sapienz: el impulso de Facebook para automatizar las pruebas de software". VentureBeat . 30 de diciembre de 2018 . Consultado el 29 de septiembre de 2020 .
  33. ^ Jones, Derek (18 de octubre de 2013). "Programación mediante algoritmos genéticos: ¿no es eso lo que ya hacen los humanos ;-)" The Shape of Code . Consultado el 31 de octubre de 2013 .
  34. ^ 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. 
  35. ^ Simons, Christopher L. (mayo de 2013). ¿Hacia dónde se dirigen los ingenieros de software en SBSE?. Primer taller internacional sobre la combinación de modelado con ingeniería de software basada en búsquedas, Primer taller internacional sobre la combinación de modelado con ingeniería de software basada en búsquedas. San Francisco, EE. UU.: IEEE Press. pp. 49–50 . Consultado el 31 de octubre de 2013 .

Enlaces externos