Maestría de Cs. Computación

SEARCH BASED SOFTWARE ENGINEERING(INGENIERIA DE SOFTWARE BASADA EN

BUSQUEDA)

Glen RodríguezUNI

AGENDA

● Conceptos Generales

● Campo de aplicación

● Ejemplo: testing

● Ejemplo: requerimientos

● Ejemplo: diseño arquitectural

● Casos de éxito

● Conclusiones

CONCEPTOS GENERALES

● Ingeniería de Software: “The application of a systematic, disciplined, quantifiable approach to the development, operation and maintenance of software; that is, the application of engineering to software“ [IEEE 2010].

● Retos de la disciplina:

– El producto software es complejo (crisis del software). – Las técnicas y procesos no escalan bien: costos

aumentan muy rápido (crisis del software).– Tecnología avanza rápido (obsolescencia)– Falta de profesionales

Por qué INGENIERIA?

● Conferencia de la OTAN (1968): "software engineering should use the philosophies and paradigms of established engineering disciplines, to solve the problem of software crisis."

● Y esos paradigmas de la ingeniería, cuáles son?

– Teoría – Simulación / Pruebas– Optimización

Ing. Civil vs. Ing. de Sofware

Teoría Simulación/pruebas

Optimización Artefacto entregado

Ing. de puentes

Mecánica, estática, resistencia de materiales

Programa CAD/CAE,Maquetas

MatemáticasComputaciónPrueba y error

Puente (artefacto real)

Ing. software

Mejores prácticas

Modelado? Prueba y error?

Artefacto digital

CONCEPTOS GENERALES

● Búsqueda: dado un conjunto de instancias ({i}) y uno de soluciones posibles ({s}) y un predicado lógico P(i,s) que determina si s es una solución de i. Dada una instancia i el problema de búsqueda consiste en encontrar, si es que existe, una solución s de i. Es decir, buscar el elemento s que haga verdadera la proposición P(i,s). Cuando se fija el valor de i y la solución es única, se dice que es un problema matemático.

● Si hay varias soluciones s ϵ S y se quiere “la mejor de todas“ se llama problema de optimización. Hay una función g(s) que determina la calidad de la solución

CONCEPTOS GENERALES

● Existen métodos que pueden resolver problemas de optimización pequeños de forma exacta, sin embargo, para problemas reales, cuyo tamaño es generalmente grande, el tiempo de ejecución de estos métodos se incrementa de forma considerable. Esta es la razón principal por la cual este tipo de problemas se resuelven mediante métodos heurísticos, los cuales, a pesar de no ofrecer una garantía de desempeño, usualmente encuentran soluciones buenas y prácticas

● Heurística: fuerza bruta y/o reglas vagamente definidas (prueba y error inteligentemente).

● Metaheurística: heurística no específica a un problema.

CONCEPTOS GENERALES

● Ing. de software basada en búsqueda, o Search-Based Software Engineering (SBSE): conversión de un problema de Ingeniería de Software en un problema de búsqueda que puede ser atacado con metaheurísticas.

● Harman 2001

● Un problema de optimización considera una o más variables de decisión, cuyos valores definen el espacio de búsqueda. Este espacio se explora con el fin de encontrar aquellos valores que ofrecen la mejor evaluación de la o las funciones objetivo que queremos minimizar o maximizar. Estas funciones objetivo comúnmente están en conflicto, es decir, la optimización de una de ellas implica la degradación de las otras

¿Qué problemas abarca?

● Cuál es la mejor forma de estructurar cierta arquitectura para mejorar la mantenibilidad del sistema?

● Qué nuevos requerimientos implemento en la siguiente versión de mi software para balancear costo y satisfacción de los clientes (next release problem)?

● Cuál es la mejor distribución de recursos humanos para N proyectos en una empresa desarrolladora de SW (workgroup formation problem)?

● Cómo "parcho" un bug en un programa en una emergencia?

● Cuál es el menor número de casos de prueba que cubren todas las bifurcaciones de un programa?

● Cuál es la mejor secuencia de pasos para refactorizar un sistema?

● Todos se pueden expresar como problemas de búsqueda

Ventajas

● Automatización total o parcial de alguna tareas de SE (si es parcial, llegar a un punto en el que el humano puede completar la tarea con poco esfuerzo)

● Ganar una nueva comprensión del dominio del problema de SE, especialmente si el dominio es complicado o muy grande para que el humano lo entienda intiutivamente.

● Soporte a la toma de decisiones basada en datos (objetivo, no subjetivo ni intuitivo)

Elementos clave

● Elementos claves en la SBSE:

1)¿Cómo representar el problema y las soluciones?

2)¿Cuál(es) es(son) la(s) función(es) de fitness? Esta función generalmente representa alguna métrica de calidad del artefacto de software en cuestión.

3)Restricciones

4)La elección de la metaheurística

5)Fuente de la data, dataset, testbed (sintética vs. real, real académica vs real industrial).

6)Fitness (métrica) no es lo mismo con calidad percibida.

Cualidades deseables

● Según Harman & Clark, un problema de SBSE debe tener 4 cualidades para ser solucionado exitosamente:

1) No hay un método directo / sencillo de obtener la mejor solución

2) El espacio de búsqueda debe ser grande para justificar el uso de búsqueda automatizada.

3) La función de fitness debe ser “suficientemente contínua“ para que las metaheurísticas funcionen bien.

4) La función de fitness debe ser por lo menos ordinal (no es necesario que sea un número real o entero, pero por lo menos que tenga un orden, o sea que se pueda conocer: fitness(s1) OPCOMP fitness(s2), donde OPCOMP: <,>,=.

Campo de aplicación

● Requerimientos / Especificaciones: analisis y negociación, reuso.

● Técnicas y herramientas de diseño: creación de arquitecturas basadas en patrones, composición de web services, tolerancia a fallas.

● Verificación / validación de modelos y programas. Crear casos de prueba, reducir suites de casos de prueba, chequear si un modelo de computación concurrente se bloquea, crear “oráculos“.

● Distribución y mantenimiento: refactorización, predicción de calidad, modularización.

● Gestión de proyectos: cronograma, asignación de recursos, estimación del costo.

● Gestión de líneas de producto: selección de características (features), encontrar inconsistencias entre las características escogidas y la arquitectura, test de regresión en líneas de producto.

SBSE por áreas al 2012

Técnicas más usadas

EA= algoritmos evolutivos. SA= recocido simulado. HC= hill climbing. ACO= colonia de hormigas. GS= greedy. IP= prog. Entera. TS= busq.tabú. AIS= sistemas inmunesArtificiales. MA= alg.meméticos. SQP: programación cuadrática secuencial

Ejemplo: Testing

● Posibles artefactos input:

– Código fuente– Ejecutable– Estructura del programa– Modelos de diseño– Información extra: espacio de la data de input y de

output, información de corridas del programa● Posibles artefactos output: casos de test, suites de casos

de test, suite de métodos de test.

Ejemplo: Testing

● Pruebas de navegación en una GUI (elementos: menús, botones de control, íconos). Cada elemento tiene dos estados (activo, inactivo) que dependen de la secuencia de operaciones. Ejemplo: Puedo ejecutar “Archivo/Leer“ en cualquier momento pero no “Pegar“ (Debo haber hecho “Copiar“ o “Cortar“ antes)

● Representación de la situación: la navegación en una GUI se puede representar como un Grafo dirigido. Cada nodo es un elemento (evento) y cada arista dirigida significa que es válido ir de un elemento a otro (o sea el segundo elemento está activo). A esto se llama “event flow model“.

Event flow model

Ejemplo: Testing

● Creación de casos de prueba: pruebas “largas“, o sea, con muchos elementos de la GUI (objetivo) pero que no repitan el mismo elemento (restricción blanda). Sólo ciertos elementos se pueden escojer al inicio y no se puede repetir el mismo elemento consecutivamente (restricciones duras). Se usó ACO. Fitness: longitud.

● Minimización de la suite de dichos casos de prueba: buscar un conjunto de casos de prueba de menor tamaño que cubra por lo menos N=1 vez cada elemento de la interfase. Se usó un método Greedy. Fitness: tamaño de la suite de casos de prueba.

Creación de casos de prueba

Minimización de la suite

Ejemplo: Testing

● Resultados: se crearon casos de prueba para MS Windows Wordpad (no todo el menú, solo parte del mismo). Hay 73 eventos y 154 aristas dirigidas. Se decidieron los parámetros de ACO por prueba y error.

● La mejor solución fueron 26 casos de prueba en una suite.

● No se probó para N>1, pero se puede adaptar este trabajo para dicha cobertura múltiple. Algunos expertos en testing de GUIs sugieren N=5 para software con GUIs complejas.

● Más detalles: J.Rodríguez, G.Rodríguez, “Automatic generation of GUI test cases using Ant Colony Optimization and Greedy algorithm“, XVIII Ibero-American Conference on Software Engineering, Cibse 2015, Lima, Perú, pp.209-221

Ejemplo: Requerimientos

● Se acaba de elicitar y analizar los requerimientos de un nuevo software. Es hora de especificarlos.

● La especificación es propensa a errores (personal con poca experiencia, el que elicita no es el mismo que especifica), es cara y lenta.

● Pero muchas empresas ya tienen un histórico de viejos proyectos de software, con especificaciones ya validadas (libreria de casos). Por qué no usarlas como template para las especificaciones de nuevos sistemas?

● Se usó k-NN. Fitness: similitud (distancia)

Modelo para reuso de especificaciones

Representación de un requerimiento

Ejemplo: Requerimientos

● Resultados: se comparó tiempo de especificar un requerimiento desde cero vs tiempo de encontrar el más parecido entre la libreria de casos y modificarlo. Dos sistemas: uno de RR.HH., otro de punto de venta.

● Ver: L.Wong, D.Mauricio, E.Papa, "Un modelo de Razonamiento Basado en Casos para la captación de requisitos en el desarrollo de proyectos de software", RISI 6(2), 2011, pp.27-36

Ejemplo: Diseño arquitectural

● Tenemos una composición de servicios web, y se cae uno de ellos.

● Si hay un servicio idéntico al caído, se reemplaza directamente.

● Pero si no hay? Si sólo hay servicios que reemplazan parcialmente al servicio caído?

● Como re-componer la composición? = Reconfiguración

● Restricción dura: los servicios web que reemplacen al caído deben realizar las mismas acciones en conjunto que el caído, ni más ni menos.

● Fitness: La calidad del servicio (tpo.respuesta, costo, etc.)

Casos de éxito

● Estas técnicas automáticas ofrecen al ingeniero soluciones computacionales que reducen el esfuerzo y coste de recursos humanos requeridos para su resolución.

● Pero su adopción en la industría ha sido lenta. Los ingenieros de software no confían en técnicas relativamente nuevas.

● Las herramientas de SBSE aún no son suficientemene amigables al usuario.

● Además, las técnicas de SBSE aparecen como “cajas negras“, muchas veces con componentes aleatorios.

Casos de éxito

● Como en muchas otras áreas de investigación, la gran mayoría de trabajos son puramente académicos, sin embargo, el interés por aplicar la SBSE en la industria del software se ha incrementado en los últimos años.

● En Chrysler, una de las primeras empresas en utilizar la SBSE, experimentaron con estas técnicas para las pruebas funcionales de un sistema de estacionamiento y para las pruebas temporales de los controladores de las bolsas de aire.

● Microsoft utilizó la SBSE para la incorporación de cálculos de punto flotante en PeX, su herramienta de pruebas de software.

● Google integró la SBSE para la optimización de pruebas de regresión en su proceso de pruebas.

● La NASA, Motorola y Ericsson han hecho experimentos con la SBSE para el análisis y la optimización de requisitos.

Casos de éxito

● Bombardier Transportation de Suecia: testing de software y hardware

● EvoSuite: genera suite de tests para programas Java. Corre usando Junit. Recibió apoyo económico de Google.

● Austin SBST para generar casos de prueba para C.

● Randoop: genera casos de prueba para Java.

● IntelliTest de Microsoft, para Visual Studio .NET

● AgitarOne (comercial). Usado por la National Institutes of Health, Cisco, GAP, HP, Tata.

Casos de éxito

● En el paper de de Souza, Maia, Freitas y Coutinho, The Human Competitiveness of Search Based Software Engineering, 2nd International Symposium on Search Based Software Engineering, pp. 143 - 152, 2010, se comparó SBSE vs humanos en 4 problemas (dos de next release, uno de workgroup formation y uno de generación de casos de prueba). SBSE es en promedio igual o más efectiva que los humanos y 1000 veces más rápida.

● Pero en otro paper de Fraser, Staats, McMinn, Arcuri y Padberg, Does automated unit test generation really help software testers? a controlled empirical study, ACM Transactions on Software Engineering and Methodology (TOSEM), 2015, 24(4), p.23:1-23:49, se muestra que si bien SBSE mejora indicadores técnicos (cobertura del código), no mejora la cantidad de errores hallados y hace un poco más dificil la evolución de los casos de prueba.

Casos de éxito

● Tradicionalmente, las áreas de Ingeniería de software nacieron independientemente unas de otras, y se han vuelto silos con poca conección entre sí.

● Pero la SBSE proporciona un marco conceptual que unifica áreas: problemas de requerimientos y de testing de regresión aparecen como problemas análogos.

Casos de éxito

● Se complementa con los paradigmas de algunas metodologías ágiles (TDD, BDD): primero los casos de prueba, luego el código fuente. Dado nuevos casos de prueba para la siguiente versión del programa, buscar un programa modificado que pase las pruebas

Conclusiones

● En sus 18 años formales de existencia, la SBSE se ha posicionado como un campo interesante para investigar.

● Como en otros campos de Ingeniería de Software, el traspaso de la academía a la industría ha sido lento. La industría prefiere esperar a que una propuesta esté bien madura para adoptarla, y que las herramientas sean fáciles de usar. Y a veces, cuando la solución académica empieza a madurar, un paradigma industrial cambia y hay que comenzar de cero. Ejemplo: GUIs desktop y el auge de aplicaciones móbiles.

● Falta datasets de la industría. Y los que hay se obsoletan con el tiempo. Problemas con la confidencialidad.

Conclusiones

● SBSE es parte de la ola por automatizar las actividades de ingeniería de software. Otros campos que buscan automatizar la SE serían el MDE (Ingeniería dirigida por modelos), el uso de NLP (procesamiento de lenguaje natural) para crear especificaciones, etc.

● Es un campo evolutivo / incremental. No se crean nuevos procesos o arquitecturas, se crean técnicas para mejorar los procesos o arquitecturas existentes.

● No es el único campo que junta “computación dura“ con ingeniería de software. Hay nuevos matrimonios (machine learning + SE, bautizado como Learning Based Software Engineering, data science + SE o Data Based SE)