Presento aquí el resultado de mi trabajo colectivo de mutación de código para testing. Digo "colectivo" por las horas que invertí en análisis y diseño viajando en colectivo[1]. Seguramente estoy reinventando la rueda[2], pero no me importa, el camino avasalla en importancia al destino.
If you need an english version, ask me and I will add it to the top of my backlog
He utilizado bastante TDD pues de no ser así hubiese incurrido en pecado mortal. Hay que predicar con el ejemplo. Es más, el proceso fue reflexivo, se aplicó contra su mismo codigo fuente. Con respecto a este tema, me interesa aclarar que para mi TDD es tan sólo una técnica más, un recurso en nuestra valijita de herramientas. No significa que uno se sienta con la mente en blanco y tira un test y el código y así avanza. Me parece correcto hacerlo así en un taller de TDD, pero si nos detenemos ahí, es como quedarse con la idea de que la danza clásica son las posiciones de los pies y agarrarse de una barra frente a un espejo, que tocar el piano son unas escalas, boxear es saltar la soga y perseguir gallinas o programar es implementar sort() y search().
Mi idea original fue utilizar php que tiene un tokenizador[3] y es lo que más conozco, para mi desgracia. Cuando en los primeros viajes comencé a percibir que podía haber mucha recursividad pensé en erlang, el cual necesito practicar para recupera mi autoestima. Inmediatamente rechacé la idea, KISS[4]. Dos viajes después, tras haber visto que python tambien tiene un sencillo tokenizador[5] (y quizas ruby[6] y cobol[7]) y percibiendo el potencial de utilizar multicores en múltiples máquinas, había reincorporado erlang y en lugar de un mutador de código para php tenía en mente un framework para usar con cualquier lenguaje que alguien se tomara la molestia en preparar. Bueno, ese era el plan.
Testing por mutación
El testing por mutación de código se basa en la idea de que si los test están bien hechos, deberían detectar cualquier cambio en el código fuente. Entonces, hay que modificar arbitrariamente el código respetando las reglas del lenguaje y ejecutar los tests, alguno tiene que fallar. Si no es así, falta cobertura o faltan casos.
Las mutaciones sobre las que decidí trabajar son las más sencillas: cambiar operadores aritméticos y de comparación, no mucho más que eso. Para hacer cambios más complejos hay dos opciones: usar un AST[8] y ver como manipularlo o generar más mutaciones que serán eliminadas por el compilador (o interprete en la primera etapa).
El proceso consiste en tomar un archivo fuente, obtener los tokens, generar un archivo fuente variando un token, luego otro y así, siempre ejecutando los tests y esperando que no falle, en cuyo caso, se corta y avisa al humano para que mejore los tests.
En [9] cuento superficialmente mi experiencia académica de uso con Jumble, un mutador de código para java y otras técnicas de automatización de test. Este proyecto es resultado de haber tomado el curso "Generación Automática de Tests Unitarios" (ECI 2012 N2) [10] a cargo de
Nazareno Aguirre [11], Universidad Nacional de Río Cuarto, Argentina
Alcance
Mis metas fueron haciéndose cada vez más ambiciosas:
- mutador de codigo para php
- framework para varios lenguajes
- usando erlang
- con procesamiento paralelo y distribuido
- comprender el trasfondo teórico
- para poder usar otros lenguajes que no tienen el tokenizador tan accesible y hacer mutaciones más complejas
He decido que hay tres etapas y sólo transitar la primera, quizás la segunda. Eventualmente, si surge la necesidad, la tercera.
Loops
Un problemas interesante que intuí es que si tocás la condición de un loop, podés entrar en infinito. Esto produce que haya que darle un tiempo máximo de ejecución a cada test. Lo que debe hacer al comienzo el framework es una ejecución normal de referencia en cada nodo para tomar el tiempo y usarlo como base para el timeout de las ejecuciones sobre el código mutado. Si hay timeout, considero que el test falló, o sea que esta ok.
Código original:
for ($i = 0; $i < 5; $i++)
Mutaciones:
for ($i = 0; $i <= 5; $i++) -> debería fallar el test
for ($i = 0; $i <= 5; $i--) -> loop infinito
Aunque luego exploro la posibilidad de controlar de modo selectivo algunas mutaciones, lo que implementé fue ejecutar un test de referencia para tomar el tiempo y luego usar
timeout para cortar en caso de anomalía.
Combinatoria
Otro problema es la combinatoria. Si para cada token que es mutable se hace toda la combinatoria con los otros, el número puede llegar a ser muy, muy alto. No sé por que esa fué mi primera idea, pero pronto caí en cuenta de mi error y sólo se hacen las combinatorias para cada token independiente de los otros.
Dado
if a + b == c
tenemos
if a (+,-,*,/,%,^) b (<,>,<=,>=,!=,==) c
Si combinara todo tendría 6 x 6 = 36 ejecuciones, pero sólo hago 6 + 6 = 12. Con dos tokens mutables parece poca diferencia, pero si fueran cien tokens tendriamos 6
100 = 6
100 en lugar de 6 x 100 = 600. Unos pocos segundos contra algunos millones de años.
Falsos positivos
El siguiente código tiene una mutación que es inocua ya que produce el mismo comportamiento y sin embargo parece un error:
<?php
$i = 0;
while ($i != 5) {
print "$i\n";
$i++;
} | <?php
$i = 0;
while ($i < 5) {
print "$i\n";
$i++;
} |
Queda un criterio humano final para decidir.
Concurrencia
Otro problema más, relacionado a la ejecución simultánea de los tests es la concurrencia sobre las distintas versiones del código. Una manera es replicar el ambiente para cada instancia. Dije "instancia", no "nodo", o sea que en una misma máquina con N cores hay N instancias. La otra es... tuve un esbozo pero lo olvidé, ya volverá cuando haga falta.
Arquitectura
La comunicación entre el componente del lenguaje y el core es mediante un mensaje json[12]. El componente del lenguaje debe identificar cada token con su valor y su clase. Había pensado que los tokens no mutables se simplifiquen en uno solo, de modo tal que:
if a + b == c {
printf("hola");
}
se tokeniza:
if
a
+
b
==
c
{
printf
(
"hola"
)
;
}
y se simplica:
"if a"
+ operadorAritmético
b
+ operadorComparación
c { printf("hola"); }
pero esto es optimización prematura, y le da a cada componente de lenguaje la responsabilidad duplicada de simplificar, así que decidí que el core se encargue de simplificar, aun así es responsabilidad del componente del lenguaje identificar la clase:
if -> inmutable
a -> inmutable
+ -> operadorAritmético
b -> inmutable
== -> operadorComparación
c -> inmutable
{ -> inmutable
printf -> inmutable
( -> inmutable
"hola" -> inmutable
) -> inmutable
; -> inmutable
} -> inmutable
y definirla:
operadorAritmético extiende simétrica
mutaciones: +,-,/,%,*
habiendo dos tipos de clases, las simétricas y las asimétricas, esto es porque hay elementos completamente intercambiables y otros que no:
operadorControl extiende asimétrica
elemento: break
mutaciones: continue, exit, blanco
elemento: exit
mutaciones: blanco
elemento: continue
mutaciones: break, exit, blanco
Por ejemplo,
clone se puede reemplazar por
=, pero no al revés.
El mensaje en json se parece a esto:
{
"header": [
{"version":"1.0"},
{"language":"php"}
],
"classes": [
{ "name":"assignment",
"type":"symmetric",
"pool":[ "+=","-=","*=","/=",".=","="]
},
{ "name":"clone",
"type":"asymmetric",
"genes": [ {"gene":"clone",
{"pool":["="]
]
},
...
],
"tokens: [ {
"class":"inmutable",
"value": "<?php"
},
{
"class":"inmutable",
"value": "$a"
},
{
"class":"assignment",
"value": "="
},
....
]
}
Aunque firmemente empeñado en no hacer el componente de python y mantener el alcance del proyecto reducido, recordé que hay un framework de unit testing de python llamado doctests [13] que tiene el código embebido en el mismo archivo fuente, como comentarios. Era lo que se usaba en w3af[14], pero me ha dicho Andrés, el papaito de w3af, que no escala.
Si el mutador mutara el código de testeo estariamos en problemas, ¿no? Hay que inventar algún mecanismo para lidiar con esto. Me imaginé, no probé, que el tokenizador lo consideraría comentario y no habría inconvenientes. Pero un segundo antes, ya había hallado la solución, que por casualidad sirve para
lidiar con los falsos positivos y los loops.
La idea es usar una nueva clase "signal", que indique al core si debe mutar o no. Por ejemplo
<?php
se convertiría en:
{
"class":"signal",
"value":"<?php",
"action":"start"
}
o en dos tokens, el normal de "<?php" y el signal, al que le podríamos quitar "value". Me gusta más la segunda opción, así tenemos dos canales, el de datos y el de control.
El componente python debería insertar como primer elemento:
{
"class":"signal",
"action":"start"
}
Luego, en el código, habría que insertar comentarios con una etiqueta arbitraria, a gusto de quién implemente. En php será #code_mutator_start|stop.
while... /*#code_mutator_stop*/ ) {
...
#code_mutator_start
...
}
Esto es feo, pero simple.
Uno puede sentir la tentación de usar tambien "action":"pause", como para que el core tenga un comportamiento distinto según sea "pause" (sigue aplicando la lógica) o "stop" (concatena todo el resto), pero sería optimización prematura.
La precaución que hay que tener es como procesar en el componente el manejo de estas etiquetas, ya que el código del componente debe ser mutable.
Por ejemplo,
if ($value == "#code_mutator_stop" )
provocaría que el core deje de mutar no siendo esa nuestra intención.
Se soluciona asi:
if ($value == "#code_mutator"."_stop" )
Esta técnica para falsos positivos abre la puerta a solucionar los loops infinitos, usando una nueva
action:
{
"class":"signal",
"action":"restrict",
"genes":["-=","/="]
}
Esto le avisa al core que no puede usar esos genes en los próximos pools, hasta que venga una nueva restricción, que puede ser vacía. Por ahora, dejemos esta puerta cerrada.
Otra puerta que tampoco quiero abrir es una clase para poder mutar valores enteros.
Por fortuna, justo me puse a leer Domain Specific Languajes[15] de Fowler, lo cual me ayudó a reflexionar mucho acerca de este mensaje que circula desde los componentes hasta el core. No califica de DSL, pero sí aplican muchos conceptos.
En algún momento, había resuelto simplificar la estructura de los
token:
"tokens: [ {
"signal": "start"
},
{
"inmutable": "<?php"
},
{
"inmutable": "$a"
},
.... ]
pero me encontré con un inconveniente. ¿Qué pasa si quiero pasar metadata, como por ejemplo la linea y columna del token en el archivo fuente? Esto es algo indispensable para python:
"tokens: [ {
"signal": "start"
},
{ "inmutable": "<?php"
},
{
"metadata": [{ "row":"1"},{"col":"0"}]
},
{
"inmutable": "$a"
},
{
"metadata": [{ "row":"1"},{"col":"6"}]
},
.... ]
No me gusta, me complica el procesamiento, asi que mejor conservo la estructura original que permite procesar de modo mucho más sencillo elementos adicionales y le agrego un campo "info".
"tokens: [ {
"class":"signal",
"action":"start"
}
{
"class":"inmutable",
"value": "<?php",
"info": [{ "row":"1"},{"col":"6"}]
},
{
"class":"inmutable",
"value": "$a",
"info": [{ "row":"1"},{"col":"6"}]
},
{
"class":"assignment",
"value": "=",
"info": [{ "row":"1"},{"col":"6"}]
},
....
]
Este ejemplo es una ilusión en php, que sólo provee información de lineas y lo hace mal. Python da más información.
Seguridad
Más por disciplina que por una necesidad real:
Los puntos de ataque son mensajes json mal formados y el resultado de la ejecución.
Resultado de la ejecución: el proceso se agota cuando se hacen todas las mutaciones o no falla alguna, asi que no hay denegación de servicio por ahí.
json: no hay loops, no hay denegación de servicio por ahi. Quizás si
hay muchos tokens o tienen valores muy largos haya que tomar alguna
precaución.
Lo que si podría ocurrir es que el componente inyecte código malicioso para que sea ejecutado luego por xUnit. Pero esto no afecta al core, no me importa.
Como Tom Lehrer le hizo decir a von Braun: "'Once the rockets are up, who cares where they come down? That's not my department', says Wernher von Braun."[16]
Ahora en serio, el componente podría por si mismo ejecutar el código malicioso. Sólo tendría valor en caso de que este sistema progresara a la arquitectura multinodo, para propagarse a otros nodos.
Alcance de la primera etapa
Me contento con que funcione una sola
instancia que entienda php y python. Esto es para respetar el espíritu
agile: sólo implemento lo que produce valor tangible. Yo no necesito
ahora los componentes para otros lenguajes ni necesito analizar tanto
código que justifique múltiples instancias. Si bien me vendría bien ver
como funcionan otros tokenizadores, estaría invirtiendo trabajo en algo
que quizás nunca desarrolle.
Esta visión
aparentemente de corto alcance no se contradice con mirar al horizonte y
hacer una apuesta, es por eso que el framework de ejecución tiene su
core en erlang:
- Es más sencillo pasar luego a una versión concurrente y distribuida
- Me sirve para practicar. Aunque no al proyecto, me da valor a mi.
No es que me haya lanzado a codear con la mente en blanco, tuve
casi dos semanas de análisis "colectivo" hasta que pude ponerme frente a
una máquina
Como mencioné antes, los componentes han sido mutados, no así el core en erlang y bash, al que sólo apliqué eunit[17] y sshunit2[18].
El código completo está disponible en
https://github.com/cpantel/codeMutator, hay un Makefile que corre diversos tests, pero antes hay que instalar unas dependencias, lee REAME.md
Me faltan varias refactorizaciones como poner la definición de las clases (las de los tokens) en modo composición para poder modificarlas sin tener que rehacer los tests. Tambien que los .sh sean más generales.
[1]
http://es.wikipedia.org/wiki/Colectivos_de_Buenos_Aires
[2]
http://stackoverflow.com/questions/246495/what-mutation-testing-frameworks-exist
[3]
http://php.net/manual/en/book.tokenizer.php
[4]
http://en.wikipedia.org/wiki/KISS_principle
[5]
http://docs.python.org/2/library/tokenize.html
[6]
http://pic.dhe.ibm.com/infocenter/pdthelp/v1r1/index.jsp?topic=%2Fcom.ibm.debugtool.doc_11.1%2Fvrmu1mst109.htm
[7]
http://www.ruby-doc.org/stdlib-1.9.3/libdoc/ripper/rdoc/Ripper.html
[8]
http://en.wikipedia.org/wiki/Abstract_syntax_tree
[9]
http://seguridad-agile.blogspot.com.ar/2012/09/automatizacion-de-test-eci-2012.html
[10]
http://www.dc.uba.ar/events/eci/2012/cursos/aguirre
[11]
http://dc.exa.unrc.edu.ar/staff/naguirre/Pagina_personal_de_Nazareno_Aguirre/Principal.html
[12]
http://www.json.org/
[13]
http://docs.python.org/library/doctest.html
[14]
http://w3af.org
[15]
http://martinfowler.com/books/dsl.html
[16]
http://en.wikipedia.org/wiki/Tom_Lehrer
[17]
http://www.erlang.org/doc/apps/eunit/chapter.html
[18]
http://code.google.com/p/shunit2/
