Aprendizaje automático con programación genética gramatical para la detección de patrones de diseño

Please download to get full document.

View again

of 6
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Published
Aprendizaje automático con programación genética gramatical para la detección de patrones de diseño Rafael Barbudo, José Raúl Romero, Sebastián Ventura Dpto. de Informática y Análisis Numérico, Universidad
Aprendizaje automático con programación genética gramatical para la detección de patrones de diseño Rafael Barbudo, José Raúl Romero, Sebastián Ventura Dpto. de Informática y Análisis Numérico, Universidad de Córdoba {rbarbudo, jrromero, Resumen Las técnicas de aprendizaje automático han sido ampliamente utilizadas en diversos dominios. En el caso del desarrollo de software, la exploración de repositorios de código puede ayudar a descubrir buenas prácticas empleadas por otros desarrolladores. En este contexto, la detección automática de patrones de diseño puede generar múltiples beneficios relacionados con la mantenibilidad y la escalabilidad del software. Estos patrones son soluciones generales y reutilizables, aplicables a la resolución de un problema de diseño. No obstante, la falta de documentación suele dificultar su trazabilidad, provocando que sus implementaciones se pierdan entre miles de líneas de código. Este trabajo propone un modelo de aprendizaje en dos fases para la detección automática de patrones de diseño. En primer lugar, un algoritmo de programación genética gramatical extrae aquellas propiedades que mejor describen al patrón. El uso de la gramática dota a la propuesta de una gran flexibilidad. A continuación, se construye el clasificador que permita detectar las implementaciones de dichos patrones. La propuesta ha sido empíricamente validada para tres patrones. Además, los resultados demuestran la competitividad del modelo frente a las propuestas actuales. Keywords detección de patrones de diseño, programación genética gramatical, clasificación asociativa, ingeniería inversa I. INTRODUCCIÓN Un patrón de diseño (DP, Design Pattern) [1] es una solución efectiva y reutilizable, aplicable a la resolución de un determinado problema de diseño del software. Estos patrones no son soluciones definitivas que puedan ser directamente codificadas, pero proporcionan una plantilla sobre cómo solucionar dicho problema. Su uso da lugar a una serie de beneficios como (1) proporcionar un lenguaje y un marco de desarrollo común; (2) mejorar la legibilidad y la mantenibilidad del código; y (3) aportar soluciones probadas y demostradamente útiles. Esto ha propiciado que su aplicación se haya estandarizado para cualquier tipo de sistema software. A pesar de ello, los DPs no suelen aparecer explícitamente documentados y, por lo tanto, sus implementaciones quedan ocultas entre miles de líneas de código. Desde la perspectiva del mantenimiento del software, la identificación de estos patrones puede aportar varios beneficios. Por ejemplo, puede facilitar la comprensión y reusabilidad del código. En este contexto, la detección de patrones de diseño (DPD) se posiciona como una tarea de gran importancia en el campo de la ingeniería inversa del software. Dado que la inspección manual de código es una Trabajo financiado por el Ministerio de Economía y Competitivad, proyecto TIN P labor subjetiva que requiere de un gran esfuerzo, la definición de métodos automáticos ha recibido un gran interés por la comunidad científica. La mayoría de propuestas actuales tienen un punto en común: en mayor o menor medida, todas requieren de la inyección de conocimiento sobre la estructura y propiedades del DP a detectar. Este conocimiento representa la visión particular de un grupo de expertos y podría no ser suficiente para detectar las implementaciones o versiones realizadas por otros desarrolladores. Para paliar este problema, algunos métodos han introducido cierto grado de flexibilidad a la hora de llevar a cabo la detección. En este contexto, varios autores han propuesto el uso de técnicas de aprendizaje automático (ML, Machine Learning) que, a diferencia de otras, permiten analizar las implementaciones ya conocidas para inferir cuáles son las propiedades que mejor las describen. Estos métodos analizan el código en base a, o bien, una serie de métricas software, o de propiedades estructurales y categóricas. En este trabajo se propone un modelo de dos fases que aplica técnicas de computación evolutiva y ML en el ámbito de la DPD. La primera fase es responsable de aprender cuáles son las propiedades que mejor describen a un patrón. Estas propiedades pueden referirse a (1) métricas software, como el acoplamiento entre clases; (2) propiedades de comportamiento, como la invocación de métodos; y (3) propiedades estructurales, como la relación de herencia entre clases. El encargado de realizar este aprendizaje es un algoritmo de programación genética gramatical [2] (G3P, Grammar Guided Genetic Programming). Dicho conocimiento se representa como un conjunto de reglas de asociación (AR, Association Rule) cuya estructura es conforme a una gramática libre de contexto (CFG, Context-Free Grammar). A continuación, en la segunda fase, se construye el detector a partir de dichas reglas. Para ello, antes es necesario definir un mecanismo de poda que asegure el uso exclusivo de las mejores reglas, así como de una estrategia que defina cómo emplearlas para llevar a cabo la detección. La propuesta ha sido empíricamente validada para 3 tipos de DPs (Singleton, Adapter y Factory Method). Además, los resultados obtenidos se han comparado con los de la herramienta MARPLE [3] para los datos del repositorio DPB [4] (Design Pattern detection Benchmark Platform), el cual contiene implementaciones de DPs de 9 proyectos reales. Los resultados experimentales demuestran como, además de la flexibilidad y escalabilidad que otorga la gramática, el modelo propuesto 157 alcanza un gran rendimiento en términos de detección, siendo altamente competitivo frente a las propuestas actuales. El resto del trabajo se organiza como sigue. La Sección II presenta el problema de la DPD. En la Sección III se presenta una visión general del modelo propuesto. A continuación, en la Sección IV, se describe la primera fase de la propuesta, es decir, el algoritmo de G3P para la extracción de ARs. La segunda fase, responsable de generar el detector, se explica en la Sección V. En la Sección VI la propuesta es validada empíricamente y comparada con otra propuesta actual. Por último, las conclusiones se recogen en la Sección VII. II. MARCO CONCEPTUAL Los patrones de diseño se clasifican en función del tipo de problema de diseño que solucionan [1]: los patrones de comportamiento se centran en las interacciones entre clases y objetos; los patrones creacionales proporcionan una forma de crear objetos mientras se oculta la complejidad del proceso; y los patrones estructurales simplifican la composición de clases y objetos. El Adapter es un ejemplo del último grupo, cuyo objetivo es el de permitir el uso de una clase ya existente cuya interfaz no coincide con la requerida por el sistema. Cada DP describe un número fijo de roles. Un rol representa una determinada tarea que debe desempeñar un elemento del patrón. En sistemas software orientados a objeto, estos roles son desempeñados por clases o por sus instancias, o incluso interfaces en el caso de lenguajes como Java. Por ejemplo, el Adapter define cuatro roles diferentes: adaptee, target, client y adapter. El rol adaptee es desempañado por la interfaz que necesita ser adaptada, mientras que target se refiere a la interfaz requerida por el sistema (client). Finalmente, el adapter define la correspondiente adaptación de los servicios proveídos por adaptee al formato requerido por target. Es importante destacar que estos roles podrían ser desempeñados por más de un elemento, dificultando el proceso de detección. Un DP es una plantilla de una solución y, en consecuencia, pueden existir distintas implementaciones para un mismo patrón dependiendo del programador, requisitos del sistema, etc. Esto dificulta que una descripción estática de las propiedades de un patrón pueda detectar sus posibles variantes. En este contexto, un gran número de propuestas se basan en el uso de técnicas de similarity scoring [5], las cuales suelen representar la información estructural del patrón y del proyecto en forma de grafos. Por lo general, estos métodos buscan subestructuras que se correspondan con la del patrón dentro del grafo del proyecto. En contraposición, las técnicas de ML aprenden cuáles son las propiedades que mejor describen a dichos patrones mediante el análisis de repositorios de código. En [6], se construye un clasificador para llevar a cabo la detección mediante el análisis de una serie de implementaciones de patrones. Estos patrones se representan como vectores de características que están formados por n*k elementos, donde n es el número de métricas software consideradas y k es el número de roles. Por otra parte, MARPLE [3] usa propiedades estructurales y de comportamiento como entrada de las técnicas de ML. Como ya se mencionó, no existe ninguna Gramática de contexto libre Algoritmo G3P4DPD Reglas de asociación clasificativas Repositorio DPB Filtrado de reglas y generación del modelo Modelo de detección Figura 1: Modelo para la detección de patrones de diseño propuesta que considere tanto métricas software, como ambos tipos de propiedades simultáneamente durante el aprendizaje. III. MODELO PARA LA DPD En este trabajo se presenta un modelo en dos fases para la DPD que combina el análisis de métricas software y de propiedades estructurales y de comportamiento del código (véase la Figura 1). El objetivo de la primera fase es aprender el conjunto de propiedades software que mejor describen al DP que se está estudiando. Para ello, se analiza el repositorio de código que alberga implementaciones de diversos patrones. Más concretamente, se ha empleado como caso de estudio el repositorio DPB ya que, a diferencia de otros repositorios como P-mart [7], DPB no solo contiene implementaciones correctas de patrones (instancias positivas), sino también implementaciones que no deberían ser consideradas patrones (instancias negativas). Estas últimas son similares a los patrones y, por lo tanto, podrían dar lugar a una detección errónea. Un algoritmo basado en G3P (G3P4DPD) se encarga de aprender las propiedades que mejor describen a un DP y a sus variantes. Este algoritmo genera un conjunto de reglas conformes a la CFG y las evoluciona aplicando una serie de operadores genéticos. Esta CFG declara la sintaxis del lenguaje que permite expresar las propiedades del software y las restricciones que describen dichas instancias en forma de ARs [8]. Sea I = {i 1,..., i n } un conjunto de items, una regla de asociación es una implicación del tipo A C donde A I, C I, y A C =. El uso de esta CFG dota a la propuesta de una gran flexibilidad al permitir combinar propiedades software de diferente tipo como métricas software y propiedades estructurales y de comportamiento. Las reglas, que se obtienen en base a esta gramática se denominan reglas de asociación clasificativas [9] (CAR, Class Association Rule). Una CAR es un tipo de AR cuyo consecuente se limita a identificar la clase (implementar o no un DP). Debido a su carácter descriptivo, estas reglas no se pueden utilizar directamente para llevar a cabo la detección. Además, dado que su número puede llegar a ser muy elevado, produciendo reglas redundantes y de baja calidad, hay que garantizar que únicamente se empleen las mejores reglas. Para ello se ha integrado un método de filtrado conocido como database coverage [9]. Por otra parte, es necesario definir una estrategia que establezca cómo utilizar dichas reglas para determinar si 158 catcmptor delegate antc cmp catcmp rule consq apattern role role boolvalue adapter adaptee (a) Ejemplo de genotipo true (= delegate adapter adaptee true) (apattern) rule : : = antc consq antc : : = cmp and antc cmp cmp : : = numcmp catcmp numcmp : : = numcmptor numop role const catcmp : : = catcmptor isfinal role boolvalue catcmptor typeof r o l e typeofvalue ... numcmptor : : = catcmptor : : = =! = numop : : = DIT NOC CBO NOM r o l e : : = adapter adaptee target boolvalue : : = true false typeofvalue : : = class absclass intface enum... consq : : = apattern notapattern Figura 3: Reglas de producción de la gramática (b) Ejemplo de fenotipo Figura 2: Ejemplo de representación de un individuo una nueva instancia implementa o no un patrón. Para esta tarea se ha utilizado la estrategia definida por el algoritmo de clasificación asociativa CMAR [10]. IV. ALGORITMO DE G3P PARA LA GENERACIÓN DE AR En esta sección se describe en detalle el algoritmo para la extracción de CARs. En primer lugar, se explica la CFG y la codificación de los individuos. IV-A. Codificación de los individuos Cada individuo del evolutivo se compone de dos elementos: (1) un genotipo, expresado en forma de árbol sintáctico, y (2) un fenotipo que representa la CAR. La Figura 2a muestra un genotipo de ejemplo, mientras que la Figura 2b muestra su correspondiente fenotipo, esto es, la regla. La Figura 3 muestra las reglas de producción de la CFG, donde los símbolos no terminales se representan entre .. y los terminales en cursiva. El símbolo raíz, a partir del cual se inicia el proceso de derivación, es rule y se deriva en ant y consq , los cuales representan al antecedente y consecuente de la regla, respectivamente. El antecedente está formado por una serie de comparaciones ( cmp ) que pueden ser numéricas ( numcmp ) o categóricas ( catcmp ). Independientemente del tipo, cada comparación está formada por un comparador, un operador, un conjunto de argumentos y un valor. Más concretamente, las comparaciones numéricas están formadas por un comparador numérico ( , , o ), un operador numérico (p.ej. NOC), un rol como argumento del operador, y un valor constante (const). Nótese como estos operadores se corresponden con métricas software. Un ejemplo de comparación numérica podría ser NOC(target) 1, la cual indica que la clase que desempeña el rol target no tiene hijos (subclases). Por otra parte, las comparaciones categóricas se componen de un comparador categórico (= o!=), un operador categórico (p.ej. typeof ), un número variable de roles como argumentos, y un posible valor asociado a dicho operador. En este caso, un ejemplo podría ser typeof(target)=intface, la cual indica que el elemento que desempeña el rol target es una interfaz. El conjunto completo de operadores se recoge en la Tabla I. En relación al consecuente ( consq ), este solo puede ser derivado en apattern o notapattern para indicar si la regla hace referencia o no a un DP, respectivamente. Es importante destacar como la mayoría de operadores categóricos se basan en los patrones de diseño elementales (en inglés, elemental design patterns) [11], micro patrones (en inglés, micro patterns) [12] y pruebas de patrones de diseño (en inglés, design pattern clues) [3], los cuales pueden ser vistos como operadores categóricos que comprueban si un fragmento de código satisface o no una determinada propiedad en base a valores de true o false. Por ejemplo, Abstract Interface es un patrón de diseño elemental que comprueba si un artefacto del código es abstracto o no. En algunos lenguajes como Java, un artefacto no solo puede ser una clase abstracta o concreta sino también una interfaz. Esto se podría solucionar añadiendo diferentes operadores como isabstract, isconcrete o isinterface. No obstante, los predicados resultantes estarían fuertemente correlados y podrían introducir ruido al proceso de aprendizaje. En este contexto, la CFG permite el uso de operadores categóricos que pueden devolver múltiples valores. Por ejemplo, typeof analiza un artefacto del código y devuelve un valor diferente según se trate de una clase concreta o abstracta, una interfaz o una enumeración. Este operador englobaría a los anteriores y, además de solucionar los problemas ya citados, su uso da lugar a reglas más compactas e interpretables. IV-B. Descripción del algoritmo El Algoritmo 1 muestra el esquema general del evolutivo. Como se puede apreciar, recibe cinco entradas: el número de iteraciones (maxgen), el tamaño de la población (popsize), el número de reglas a devolver (extpopsize), la gramática (grammar) y el repositorio de patrones (repo). Este repositorio está compuesto por un conjunto de instancias de DPs (positivas y negativas) y su código fuente. Cada una de estas instancias define los elementos que componen el patrón, así como los roles que desempeñan. El algoritmo devuelve una población externa (extpop) compuesta por las mejores reglas. 159 Tabla I: Operadores numéricos y categóricos Operadores numéricos Signatura Descripción NOM(R 1 ) Número de métodos de R 1 NOC(R 1 ) Número de subclases directas de R 1 DIT(R 1 ) Profundidad en el árbol de herencia de R 1 RFC(R 1 ) Número de métodos que pueden ser invocados cuando una instancia de R 1 recibe un mensaje Operadores categóricos Signatura Descripción issubclass(r 1 ) true si R 1 es una subclase, false en caso contrario isfinal(r 1 ) true si R 1 no puede ser heredado controlledinit(r 1 ) true si R 1 se instancia así mismo dentro de un bloque if o while staticfield(r 1 ) true si R 1 tiene un campo estático staticflag(r 1 ) true si R 1 tiene un campo estático y booleano conglomeration(r 1 ) true si R 1 declara algún método que llame al menos a otros 2 métodos de R 1 returned(r 1,R 2 ) true si algún método declarado en R 1 devuelve un elemento del tipo R 2 received(r 1,R 2 ) true si algún método declarado en R 1 recibe un elemento del tipo R 2 como argumento createobj(r 1,R 2 ) true si R 1 instancia a R 2 delegate(r 1,R 2 ) true si R 1 invoca algún método de R 2 sameelem(r 1,R 2 ) true si R 1 y R 2 son el mismo artefacto typeof(r 1 ) Devuelve el tipo del artefacto que implementa a R 1 (class, absclass, enum o intface) linkmethod(r 1,R 2 ) Devuelve directover, indirover, directimpl o indirimpl si R 1 directa o indirectamente sobrescribe o implementa un método de R 2, nolink en cualquier otro caso linkartefact(r 1,R 2 ) Devuelve directinherit, indirinherit, directimpl, indirimpl si R 1 directa o indirectamente extiende o implementa a R 2, nolink en cualquier otro caso ctorvisibility(r 1 ) Devuelve la visibilidad del constructor menos restrictivo de R 1, i.e. private, protected, package o public aggregation(r 1,R 2 ) Devuelve información de un atributo del tipo de R 2 declarado en R 1 en términos de su visibilidad y de su instanciabilidad. adapter(r 1,R 2,R 3 ) Devuelve si un método declarado (decl) o heredado (inhr) de R 1, implementado de R 3, delega en un método de R 2, nolink en cualquier otro caso Se comienza generando, de manera aleatoria, popsize individuos en base a las restricciones definidas por grammar. La población externa (extpop) es inicializada al conjunto vacío. A continuación, se evalúan los individuos de pop en base al soporte (Ecuación 1). Esta métrica mide la frecuencia de aparición de una determinada regla en el conjunto de datos, siendo t el conjunto de transacciones en el conjunto de datos T que contiene al itemset X. supp(x) = {t T;X t} T A partir de este punto, el algoritmo, a lo largo de maxgen iteraciones, evoluciona a los individuos mediante la aplicación de operadores genéticos. En primer lugar, el operador de selección escoge popsize individuos de la unión entre pop y extpop. A continuación, el operador de cruce es aplicado, con una probabilidad prefijada, sobre pares de individuos para combinar sus genotipos. Por último, se aplica uno de dos posibles operadores de mutación. La selección se realiza de manera aleatoria, siendo ambos operadores equiprobables. (1) Algoritmo 1: Extracción de reglas de asociación Entrada: maxgen, popsize, extpopsize, grammar, repo Salida : extpop pop generaterules(popsize, grammar) extpop evaluate(pop, repo) while generation maxgen do pop select(pop extpop, popsize) pop crossover(pop) if random() 0,5 then pop diversitymutator(pop); else pop dpdmutator(pop); end evaluate(pop, repo) extpop update(pop extpop, extpopsize) generation++ end El primero (diversitymutator) es un operador genérico que promueve la diversidad entre los individuos,
Similar documents
View more...
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks
SAVE OUR EARTH

We need your sign to support Project to invent "SMART AND CONTROLLABLE REFLECTIVE BALLOONS" to cover the Sun and Save Our Earth.

More details...

Sign Now!

We are very appreciated for your Prompt Action!

x