P ueba de Mu ación E olu i a Aplicada a
Sis emas O ien ados a Obje os
Ped o Delgado-Pé ez1, Inmaculada Medina-Bulo1, Se gio Segu a2, An onio
Ga cía-Domínguez3y Juan José Domínguez-Jiménez1
1Depa amen o de Ingenie ía In o má ica, Uni e sidad de Cádiz, España
{ped o.delgado, inmaculada.medina, juanjose.dominguez}@uca.es
2Depa amen o de Ingenie ía In o má ica, Uni e sidad de Se illa, España
[email p o ec ed]
3Depa men o Compu e Science, Uni e si y o Yo k, Uni ed Kingdom
[email p o ec ed]
Resumen A pesa del bene icio que puede epo a la p ueba de mu a-
ciones en el p oceso de p ueba de so wa e, el cos e que supone su apli-
cación siemp e ha sido is o como un obs áculo pa a una mayo acogida
po pa e de la indus ia. Po es a azón, se han desa ollado di e sas
écnicas que a an de palia el p oblema, p incipalmen e median e la
educción del núme o de mu an es que son gene ados. En e ellas se en-
cuen a la P ueba de Mu ación E olu i a (PME), que p opone el empleo
de algo i mos e olu i os pa a encon a un subconjun o de mu an es que
p esen a mayo posibilidad de ayuda a e ina el conjun o de casos de
p ueba empleado. La écnica solo había sido p obada con éxi o en ope-
ado es pa a el lenguaje de p og amación WS-BPEL. En es e a ículo se
p esen an los expe imen os lle ados a cabo aplicando la écnica de PME
con mu an es gene ados po ope ado es de mu ación pa a C++ elacio-
nados con la o ien ación a obje os. Los esul ados ob enidos, usando los
pa áme os conside ados como más ap opiados pa a la con igu ación del
algo i mo, e elan que la écnica ambién es más e ec i a que una es a-
egia alea o ia con ope ado es de clase pa a sis emas en C++.
Palab as cla e: P ueba de so wa e, p ueba de mu aciones, algo i mos
e olu i os, C++, o ien ación a obje os.
1. In oducción
La p ueba de mu aciones es una écnica de p ueba de so wa e que se emplea
an o pa a e alua como pa a mejo a la habilidad que p esen a un conjun o de
casos de p ueba de ec ando allos en el código [22]. La écnica se basa en c ea
e siones modi icadas del p og ama o iginal, que se conocen como mu an es. Ca-
da mu an e con iene un simple cambio sin ác ico que es inse ado en el código
median e los ope ado es de mu ación de inidos pa a cada lenguaje de p og ama-
ción. Una ez gene ados los mu an es, es os son ejecu ados con a el conjun o
de casos de p ueba, al igual que el p og ama o iginal. Como esul ado de es e
p oceso, podemos ob ene mu an es que han sido ma ados po que la salida pa a
alguno de los casos de p ueba di e ía de la p oducida po el p og ama o iginal, o,
po el con a io, mu an es que pe manecen i os po que no se obse a ninguna
di e encia. Es os úl imos pueden ayuda nos a gene a nue os casos de p ueba
pa a consegui de ec a esas mu aciones, pudiendo ambién ocu i que algunas
de las mu aciones no hayan en ealidad cambiado la semán ica del p og ama y
los mu an es gene ados sean, po an o, equi alen es al p og ama o iginal.
Debido a la g an can idad de mu an es que se pueden de i a de un p o-
g ama, la p ueba de mu aciones es conocida po se una écnica de al o cos e
compu acional. Es e p oblema unido a la a dua a ea de de e mina qué mu-
an es de los que pe manecen i os son equi alen es suponen una aba pa a su
aplicación. Pa a educi el ele ado cos e que p esen a la p ueba de mu aciones,
se han p opues o di e en es écnicas a los la go de los años, p incipalmen e pa a
educi el núme o de mu an es a gene a . En e es as écnicas cabe des aca la
mu ación selec i a [21], la mu ación po mues eo [1], la mu ación po ag upa-
mien o [11] o la mu ación de o den supe io [13]. Una no edosa écnica pa a la
educción del núme o de mu an es a gene a pe o man eniendo un al o po en-
cial pa a e ina el conjun o de casos de p ueba es la conocida como P ueba de
Mu ación E olu i a [9] (PME de aho a en adelan e). Es a écnica se basa en el
uso de un algo i mo gené ico pa a guia la búsqueda hacia la ob ención de un
subconjun o de mu an es ú iles pa a la mejo a del conjun o de casos de p ueba.
Es e a ículo iene como obje i o mos a los esul ados que o ece la PME en
sis emas o ien ados a obje os en lenguaje C++. La écnica había sido empleada
an e io men e con composiciones WS-BPEL con buenos esul ados en compa a-
ción con el uso de una selección pu amen e alea o ia. Sin emba go, no se habían
lle ado a cabo es udios pos e io es sob e la aplicabilidad de la PME en di e en es
con ex os. Los esul ados expe imen ales sob e es p og amas eales de di e -
sos amaños mues an que la écnica ob iene buenos esul ados con ope ado es
o ien ados a obje os pa a C++, alidando su uso en di e en es ámbi os.
El o o obje i o p incipal de es e a ículo es p esen a la he amien a desa-
ollada pa a uni el sis ema de mu aciones en C++ [3] con el algo i mo gené ico
implemen ado en la he amien a GAme a [8]. Asimismo, se explican los cambios
que han sido lle ados a cabo pa a pone en p ác ica la écnica debido a las
pa icula idades del lenguaje y los ope ado es de mu ación es udiados.
El es o del a ículo se es uc u a de la siguien e mane a. En la siguien e
sección se comen an los an eceden es y el abajo elacionado. En la Sección 3
se mues a el uncionamien o del algo i mo gené ico y se p esen an las pecu-
lia idades de la he amien a desa ollada que conec a el algo i mo gené ico con
el sis ema de mu aciones en C++. En la Sección 4 se mues an y discu en los
esul ados ob enidos en el expe imen o lle ado a cabo. En la úl ima sección, se
exponen las conclusiones y el abajo u u o a ealiza .
2. An eceden es y T abajo Relacionado
2.1. P ueba de Mu ación E olu i a
La PME [9] es una de las écnicas más ecien emen e p esen adas de educ-
ción de mu an es y consecuen e educción del cos e compu acional. El obje i o
de es a écnica es la de gene a an solo un subconjun o del o al de mu an es
que con enga un g an po cen aje de los mu an es que ealmen e pe mi en e ina
el conjun o de casos de p ueba u ilizado, de mane a que no se incu a en una
pé dida signi ica i a de la e ec i idad de la p ueba de mu aciones. La ob ención
de mu an es con capacidad de mejo a el conjun o de p uebas se lle a a cabo a
a és de un algo i mo gené ico, el cual, median e su unción de ap i ud, a o ece
a los mu an es que los au o es de la écnica denominan como mu an es ue es,
que pueden se de dos ipos a su ez:
Mu an es po encialmen e equi alen es: Son aquellos que, con el ac ual
conjun o de casos de p ueba, pe manecen i os. Es os mu an es pueden o
bien suge i la c eación de nue os casos de p ueba pa a ma a los, o bien
pueden esul a inalmen e en mu an es equi alen es (condición que solo se
conoce as la inspección de los mismos).
Mu an es di íciles de ma a : Son aquellos mu an es que son ma ados po
un único caso de p ueba que, además, solo ma a a ese mu an e.
La PME ue empleada pa a educi el cos e de la p ueba de mu aciones en
composiciones WS-BPEL. Pa a ello, se desa olló la he amien a GAme a [8],
que implemen aba el algo i mo gené ico p opues o po los au o es. Como esul-
ado del uso de GAme a en las es composiciones analizadas pa a alcanza un
po cen aje de mu an es ue es, se ob u o en odas ellas una educción mayo
del núme o de mu an es que si los mu an es uesen elegidos de mane a alea o ia.
También se demos ó que el impac o del uso del algo i mo en el iempo global
e a ma ginal. Po úl imo, se es ablecie on cie os pa áme os de con igu ación
pa a op imiza los esul ados del algo i mo gené ico.
2.2. P ueba de Mu aciones pa a C++
La p ueba de mu aciones ha sido aplicada desde sus inicios a una g an a ie-
dad de lenguajes de p og amación, ales como Ja a [15], SQL [20] o más ecien-
emen e Py hon [6]. G an pa e de las he amien as desa olladas y lenguajes
de p og amación a los que se ha aplicado es án ecogidos en un abajo de Jia
y Ha man [12]. Sin emba go, has a hace unos años no había sido p ác icamen e
abo dada en elación a C++. Respec o a es e lenguaje, un conjun o de ope a-
do es de mu ación a ni el de clase ue on de inidos en cuan o a ca ac e ís icas
del pa adigma de o ien ación a obje os como la he encia, el polimo ismo y la
sob eca ga de mé odos [4,5]. Pos e io men e se es ablecie on unas pau as pa a la
co ec a gene ación de mu an es a la ho a de implemen a los ope ado es de mu-
ación [2]. Finalmen e, se p esen ó la he amien a que aplicaba un subconjun o
de los ope ado es de clase de inidos pa a es e lenguaje [3]. Po su pa e, Kusano
y Wang [14] ambién desa olla on una he amien a de mu aciones en ocada a
la concu encia en aplicaciones mul ihilo en C++.
El sis ema de mu aciones pa a C++ desa ollado po los au o es de es e a-
bajo admi e las mismas ó denes de ejecución que MuBPEL pa a composiciones
WS-BPEL [10]. MuBPEL es la he amien a subyacen e empleada po GAme a
pa a el análisis, gene ación y ejecución de mu an es. El hecho de usa la misma
a qui ec u a pe mi e que podamos eu iliza con mayo acilidad el algo i mo
gené ico implemen ado en GAme a pa a aplica lo a iche os de código C++.
3. Funcionamien o de la P ueba de Mu ación E olu i a
3.1. Algo i mo Gené ico
GAme a [8] iden i ica a un mu an e de o ma uní oca median e es campos
( e Figu a 1):
Ope ado : Código ep esen a i o del ope ado que gene a el mu an e.
Localización: O den en el cual el ope ado de mu ación inse a las di e en es
mu aciones den o del código analizado.
A ibu o: O den en el cual el ope ado inse a las di e en es mu aciones en
una misma localización.
Figu a 1. Codi icación de un mu an e
El algo i mo gené ico implemen ado p oduce una p ime a gene ación de indi-
iduos (mu an es) alea o iamen e. El amaño de la población en cada gene ación
iene dado po un pa áme o a es ablece al inicio. A pa i de ahí, p oduce su-
cesi as gene aciones en las que los nue os indi iduos p o ienen de dos e ien es:
1. Indi iduos gene ados alea o iamen e: Tal y como sucede en la p ime-
a gene ación, se p oduce un po cen aje de indi iduos alea o ios que iene
ma cado po un pa áme o a con igu a an es de la ejecución.
2. Indi iduos p oducidos po mu ación o po c uce: El es o de indi-
iduos de la gene ación se p oducen po es a ama. Se seleccionan de la
an e io gene ación los indi iduos necesa ios median e el sis ema de selec-
ción po ule a (p opo cionalmen e a la unción de ap i ud del indi iduo):
Mu ación: Se mu a uno de los campos (ope ado , localización o a ibu-
o) del mu an e ac ual pa a gene a uno nue o. La mu ación del campo
ealizada se limi a pa a p oduci un mu an e que pueda se gene ado.
Po ejemplo, si un ope ado gene a mu an es en es localizaciones, no
es posible mu a la localización a cua o.
C uce: Se seleccionan dos indi iduos que ac úan como pad es y se se-
lecciona un pun o de c uce. Si el pun o de c uce se es ablece en e los
campos ope ado -localización, los pad es in e cambian el ope ado man-
eniendo los campos localización-a ibu o. Si, po el con a io, el pun o
de c uce es á en e localización-a ibu o, los pad es in e cambian el a i-
bu o ( e Figu a 2).
La p obabilidad con la que la he amien a u iliza mu ación o c uce ambién
es con igu able. Más adelan e, en la Sección 3.2, e emos que se á necesa io
modi ica es os ope ado es.
Figu a 2. C uce de mu an es
La unción de ap i ud pa a un mu an e cuen a el núme o de casos de p ueba
que lo ma an, así como el núme o de mu an es que esos casos de p ueba ma an
a su ez. Cuan o mayo sea la suma o al de ambas cuen as, peo se á la unción
de ap i ud asociada al mu an e, pues los casos de p ueba que se pueden llega
a gene a con ese mu an e esul an poco especí icos. De es a mane a, espec o a
los mu an es ue es ( e Sección 2.1):
Los mu an es po encialmen e equi alen es eciben el alo más al o al no se
ma ados po ningún caso de p ueba.
Los mu an es di íciles de ma a eciben el segundo mejo alo , al se ma ados
po un solo caso de p ueba.
Po el con a io, los mu an es que son ma ados po odos los casos de p ueba
son los que eciben las alo aciones más bajas de la unción de ap i ud. Además
de lo dicho, es impo an e des aca las siguien es ca ac e ís icas del algo i mo:
Uso de segunda población: El algo i mo u iliza los mu an es gene ados
has a el momen o pa a es ima de mane a más p ecisa el alo de la ap i ud
de cada indi iduo, de mane a que la ap i ud de un mu an e puede a ia de
una gene ación a o a.
No malización de alo es: Dado que cada ope ado gene a un núme o
de mu an es dis in os en el sis ema, pa a que odos los mu an es engan la
misma p obabilidad de se seleccionados, el sis ema no maliza/desno maliza
los alo es de los campos localización y a ibu o.
3.2. P ueba de Mu ación E olu i a pa a Sis emas O ien ados a
Obje os en C++
La p ueba de mu aciones es una écnica de caja blanca que equie e de ma cos
de abajo pa icula es pa a cada lenguaje de p og amación. En es e sen ido, se

ha desa ollado una he amien a que pe mi e aplica la PME a aplicaciones
codi icadas en lenguaje C++. El p incipal come ido de es a he amien a es la
de coo dina la acción en e o os dos sis emas exis en es:
GAme a [8]: Es a aplicación implemen a el algo i mo e olu i o p opues o
po los c eado es de la écnica [9].
Sis ema de mu aciones pa a C++ [3]: Es a he amien a aplica la p ueba
de mu aciones al lenguaje C++ median e ope ado es a ni el de clase [5].
GAme a ue u ilizada pa a la ob ención de esul ados expe imen ales con
composiciones en lenguaje WS-BPEL. No obs an e, la he amien a es á modu-
la izada de mane a que el algo i mo gené ico es independien e del lenguaje al
que se quie a aplica . De es a mane a, la he amien a que se ha desa ollado
hace co esponde los da os en e GAme a y el sis ema de mu aciones pa a que
la conexión en e es os dos sis emas sea posible. La nue a he amien a lle a a
cabo las siguien es acciones:
T ans o ma las ó denes de ejecución que GAme a equie e pa a su unciona-
mien o (análisis, gene ación y ejecución de mu an es) en ó denes en endibles
pa a el sis ema de mu aciones en C++.
T aduci la salida gene ada po el sis ema de mu aciones al o ma o de en-
ada pa a GAme a y, al con a io, o ma ea la salida de GAme a como
en ada del sis ema de mu aciones.
Debido a las ca ac e ís icas de los dos sis emas a los que es a he amien a
conec a, ha sido necesa io lle a a cabo a ias modi icaciones espec o al plan-
eamien o inicial de la écnica. Es os cambios, sin emba go, pueden a ec a al
uncionamien o del algo i mo gené ico, al y como se explica a con inuación:
1. Como se comen ó en la sección an e io , GAme a iden i ica a un mu an e
median e es campos: ope ado , localización y a ibu o. El campo a ibu o
depende de cada ope ado de mu ación conc e o. En es e sen ido, podemos
encon a las siguien es opciones:
A ibu o ijo: El núme o de posibles mu aciones a inse a es conoci-
do de an emano. Po ejemplo, un ope ado que eemplaza un ope ado
a i mé ico puede eemplaza el ope ado po un conjun o de ope ado es
a i mé icos conocido.
A ibu o a iable: El núme o de posibles mu aciones depende po com-
ple o de la localización exac a den o del código. A modo de ejemplo, un
ope ado de mu ación que eemplaza una llamada a un mé odo po o o
mé odo que sea compa ible (a in de que no gene e un mu an e in álido)
depende á del núme o de mé odos compa ibles que exis an.
Cuando el algo i mo gené ico elige el campo “a ibu o” de un indi iduo pa a
se mu ado, es necesa io que el a ibu o sea ijo pa a que el algo i mo pueda
selecciona con igualdad de posibilidades el campo a ibu o que end á el
nue o indi iduo gene ado. Es po ello que, cuando un ope ado de mu ación
p esen a un a ibu o a iable, el a ibu o se ma ca siemp e como “1” y las di-
e en es a iaciones que se pueden inse a en esa localización se con abilizan
simplemen e como nue as localizaciones.
Dicho es o, los ope ado es de clase implemen ados en el sis ema de mu acio-
nes pa a C++ o bien solo ienen la posibilidad de gene a un único mu an e
po localización o bien su a ibu o es a iable. Es o quie e deci que, en
caso de que el algo i mo gené ico elija el campo a ibu o pa a se mu ado
y gene a un nue o indi iduo, como el campo a ibu o siemp e iene alo
“1”, nunca se gene a ía un indi iduo di e en e a pa i de la mu ación de ese
campo. Es po ello po lo que, pa a ealiza los expe imen os, se ha añadido
una nue a opción a GAme a pa a pe mi i la posibilidad de que el campo
a ibu o no sea mu ado pa a una ejecución dada. Es o ambién se aplica a
la mu ación po c uce que in e cambia el a ibu o.
Figu a 3. Ejemplo de aducción de mu an es en e el sis ema de mu aciones pa a
C++ y GAme a de un ope ado “op1” aplicado a dos iche os “ iche o1” y “ iche o2”.
2. Las composiciones WS-BPEL que ecibe la he amien a MuBPEL [10] es án
codi icadas en un único iche o uen e. Sin emba go, las aplicaciones en C++
suelen compone se de a ios iche os. El sis ema de mu aciones pa a C++
pe mi e la posibilidad de mu a más de un iche o en la misma ejecución.
Pa a ello, la he amien a añade un campo adicional a la 3- upla (ope ado ,
localización, a ibu o) pa a iden i ica uní ocamen e cada mu an e: el nom-
b e del iche o al que pe enece. GAme a solo es á con igu ado pa a a a
los campos (ope ado , localización, a ibu o), de mane a que ha sido nece-
sa io ealiza una aducción en e la salida del sis ema de mu aciones y
la en ada de GAme a. Es a aducción consis e en hace co esponde los
mu an es en e ambas he amien as median e la codi icación/decodi icación
del nomb e del iche o a a és de la localización. Es e p oceso se de alla
g á icamen e en la Figu a 3.
No obs an e, el hecho de pe mi i que más de un iche o de código sea mu-
ado en la misma ejecución p oduce un e ec o en el algo i mo gené ico no
con emplado en los expe imen os o iginales con espec o a WS-BPEL. Tan-
o la mu ación del campo “ope ado ” como del campo “localización” puede
p o oca que el nue o indi iduo gene ado co esponda a una clase que es é
en un iche o de código di e en e al del indi iduo que ue mu ado. Aunque
las clases de un mismo p og ama suelen usa un mismo pa ón de diseño y
es a in e elacionadas, el compo amien o de un ope ado en clases di e en-
es puede a ia , p incipalmen e cuando se encuen an en iche os de código
dis in os. Po an o, es e hecho puede a ec a al algo i mo gené ico pun ual-
men e, pe o ambién puede supone una en aja al pe mi i al algo i mo
ab i se hacia nue os espacios de búsqueda.
4. Expe imen os
4.1. Casos de es udio
Pa a los expe imen os conducidos en es e a ículo, se ha hecho uso de es
p og amas eales de código abie o:
1. Dolphin [7]: Adminis ado de a chi os en aplicaciones de esc i o io de KDE
po de ec o.
2. Tinyxml2 [19]: Analizado sencillo y e icien e de código XML.
3. QTDom [16]: Módulo de Q que o ece una implemen ación en C++ del
es ánda DOM.
En cada aplicación, los mu an es que se pueden gene a con los ope ado es
de mu ación implemen ados en el sis ema de mu aciones son siemp e los mismos,
es deci , los mu an es no a ían en di e en es ejecuciones. Po lo an o, a pa i
del esul ado de una ejecución p e ia de odos los mu an es en cada aplicación,
es posible conoce el núme o o al de mu an es ue es exis en es. Tal y como
puede e se en el Cuad o 1, es as aplicaciones p oducen un núme o di e en e
de mu an es o ales así como de mu an es ue es, lo cual nos pe mi e obse a
el uncionamien o de la écnica en elación a la can idad de mu an es que se
gene a. Además, en es a abla ambién puede obse a se el amaño del conjun o
de casos de p ueba empleado pa a cada uno de los p og amas, el cual es el que
o iginalmen e iene dis ibuido con cada aplicación.
Cuad o 1. Mu an es y conjun o de casos de p ueba de las aplicaciones del es udio
Dolphin Tinyxml2 Q Dom To al
Mu an es o ales 219 614 1,146 1,979
V´alidos 208 433 681 1,322
Fue es 103 159 348 610
% Mu an es ue es 49.5% 36.7% 51.1% 46.1%
Casos de p ueba 61 57 46 164
Cuad o 2. Pa áme os u ilizados en la ejecución del algo i mo e olu i o
Pa ´ame o Valo
Tama˜no poblaci´on 5%
Indi iduos gene ados alea o iamen e 10%
Indi iduos gene ados po mu aci´on o c uce 90%
-P obalididad de mu aci´on 30%
-P obabilidad de c uce 70%
4.2. Con igu ación del Expe imen o
El expe imen o lle ado a cabo busca analiza el esul ado ob enido po la
PME en compa ación con una écnica alea o ia:
1. Alea o ia: Consis e en o dena alea o iamen e los mu an es al inicio y des-
pués i seleccionándolos de uno en uno has a llega a la condición de pa ada.
2. PME: A pa i de la población inicial, se i án p oduciendo nue as gene acio-
nes de mu an es en base a los pa áme os es ablecidos pa a el uncionamien o
del algo i mo e olu i o. Los pa áme os empleados son los que se pueden ob-
se a en el Cuad o 2, los cuales son los que en los expe imen os ealizados
en el a ículo en el que se p esen a la écnica ue on hallados como los más
adecuados [9]. El amaño de la población se e ie e al núme o de mu an es
que se án p oducidos en cada gene ación, el cual es un po cen aje espec o
del o al de mu an es en cada aplicación. Como puede obse a se, la suma
del po cen aje de mu an es gene ados alea o iamen e y po mu ación/c uce
es de 100 %, pues a a és de es as dos e ien es se c ean odos los mu an es
de una gene ación.
En es e expe imen o se busca localiza a los mu an es ue es, po lo cual se
han es ablecido dos condiciones de pa ada: al llega al 75 % y al 90 % del o al
de mu an es ue es. Como se mencionó an e io men e, es e c i e io es posible
es ablece lo ya que, debido a una ejecución p e ia, conocemos el núme o de
mu an es ue es exis en es. La he amien a ha sido con igu ada pa a medi an o
el po cen aje de mu an es gene ados has a el momen o de llega a los lími es de
pa ada como el iempo o al necesa io pa a la ejecución de los casos de p ueba en
es os mu an es. Pa a e i a el sesgo que puede p oduci se en una única ejecución
de las écnicas (debido al componen e alea o io que ambas conlle an), se han
ealizado 30 ejecuciones con di e en es semillas de pa ida. De es a mane a, los
cálculos a mos a se ob ienen a pa i de los da os de es as 30 ejecuciones.
Es necesa io ema ca que, pa a sabe si un mu an e es o no ue e, es ne-
cesa ia la ejecución de odos los casos de p ueba (po lo que no bas a pa a la
ejecución al p ime caso de p ueba que ma a al mu an e). Asimismo, el algo i mo
e olu i o u iliza á es a in o mación pa a el cálculo de la unción de ap i ud.
4.3. Resul ados
Los esul ados del expe imen o se ecogen en el Cuad o 3 y 4. En el Cuad o 3
se mues a la media, mediana, alo es mínimos y máximo y des iación es ánda