La complejidad ciclomática es una métrica de software que se utiliza para indicar la complejidad de un programa . Es una medida cuantitativa del número de rutas linealmente independientes a través del código fuente de un programa . Fue desarrollada por Thomas J. McCabe, Sr. en 1976.
La complejidad ciclomática se calcula utilizando el gráfico de flujo de control del programa. Los nodos del gráfico corresponden a grupos indivisibles de comandos de un programa, y una arista dirigida conecta dos nodos si el segundo comando se puede ejecutar inmediatamente después del primero. La complejidad ciclomática también se puede aplicar a funciones , módulos , métodos o clases individuales dentro de un programa.
Una estrategia de prueba , llamada prueba de ruta básica por McCabe, quien la propuso por primera vez, consiste en probar cada ruta linealmente independiente a través del programa. En este caso, la cantidad de casos de prueba será igual a la complejidad ciclomática del programa. [1]
Existen múltiples formas de definir la complejidad ciclomática de una sección de código fuente . Una forma común es el número de caminos linealmente independientes dentro de él. Un conjunto de caminos es linealmente independiente si el conjunto de aristas de cualquier camino en no es la unión de los conjuntos de aristas de los caminos en algún subconjunto de . Si el código fuente no contuviera declaraciones de flujo de control (condicionales o puntos de decisión), la complejidad sería 1, ya que solo habría un único camino a través del código. Si el código tuviera una declaración IF de condición única , habría dos caminos a través del código: uno donde la declaración IF es VERDADERA y otro donde es FALSA. Aquí, la complejidad sería 2. Dos IF de condición única anidados, o un IF con dos condiciones, producirían una complejidad de 3.
Otra forma de definir la complejidad ciclomática de un programa es observar su gráfico de flujo de control , un gráfico dirigido que contiene los bloques básicos del programa, con una arista entre dos bloques básicos si el control puede pasar del primero al segundo. La complejidad M se define entonces como [2]
dónde
Una formulación alternativa de esto, como se propuso originalmente, es utilizar un gráfico en el que cada punto de salida está conectado de nuevo al punto de entrada. En este caso, el gráfico está fuertemente conectado . Aquí, la complejidad ciclomática del programa es igual al número ciclomático de su gráfico (también conocido como el primer número de Betti ), que se define como [2]
Esto puede verse como el cálculo del número de ciclos linealmente independientes que existen en el gráfico: aquellos ciclos que no contienen otros ciclos dentro de sí mismos. Debido a que cada punto de salida vuelve al punto de entrada, hay al menos un ciclo de este tipo para cada punto de salida.
Para un solo programa (o subrutina o método), P siempre es igual a 1; una fórmula más simple para una sola subrutina es [3]
La complejidad ciclomática puede aplicarse a varios programas o subprogramas de este tipo al mismo tiempo (por ejemplo, a todos los métodos de una clase). En estos casos, P será igual al número de programas en cuestión y cada subprograma aparecerá como un subconjunto desconectado del grafo.
McCabe demostró que la complejidad ciclomática de un programa estructurado con un solo punto de entrada y un punto de salida es igual al número de puntos de decisión (declaraciones "if" o bucles condicionales) contenidos en ese programa más uno. Esto es cierto solo para los puntos de decisión contados en las instrucciones de nivel de máquina más bajas. [4] Las decisiones que involucran predicados compuestos como los que se encuentran en lenguajes de alto nivel como IF cond1 AND cond2 THEN ...deben contarse en términos de las variables de predicado involucradas. En este ejemplo, uno debe contar dos puntos de decisión porque a nivel de máquina es equivalente a IF cond1 THEN IF cond2 THEN .... [2] [5]
La complejidad ciclomática puede extenderse a un programa con múltiples puntos de salida. En este caso, es igual a donde es el número de puntos de decisión en el programa y s es el número de puntos de salida. [5] [6]
Un subgrafo par de un grafo (también conocido como subgrafo euleriano ) es aquel en el que cada vértice incide con un número par de aristas. Dichos subgrafos son uniones de ciclos y vértices aislados. Los subgrafos se identificarán con sus conjuntos de aristas, lo que equivale a considerar únicamente aquellos subgrafos pares que contienen todos los vértices del grafo completo.
El conjunto de todos los subgrafos pares de un grafo es cerrado bajo la diferencia simétrica y, por lo tanto, puede considerarse como un espacio vectorial sobre GF(2) . Este espacio vectorial se denomina espacio cíclico del grafo. El número ciclomático del grafo se define como la dimensión de este espacio. Como GF(2) tiene dos elementos y el espacio cíclico es necesariamente finito, el número ciclomático también es igual al logaritmo 2 del número de elementos en el espacio cíclico.
Se construye fácilmente una base para el espacio de ciclos fijando primero un bosque de expansión del grafo y luego considerando los ciclos formados por una arista que no está en el bosque y el camino en el bosque que conecta los puntos finales de esa arista. Estos ciclos forman una base para el espacio de ciclos. El número ciclomático también es igual al número de aristas que no están en un bosque de expansión máxima de un grafo. Dado que el número de aristas en un bosque de expansión máxima de un grafo es igual al número de vértices menos el número de componentes, la fórmula define el número ciclomático. [7]
La complejidad ciclomática también se puede definir como un número de Betti relativo , el tamaño de un grupo de homología relativa :
que se lee como "el rango del primer grupo de homología del grafo G en relación con los nodos terminales t ". Esta es una forma técnica de decir "la cantidad de caminos linealmente independientes a través del grafo de flujo desde una entrada hasta una salida", donde:
Esta complejidad ciclomática se puede calcular. También se puede calcular a través del número Betti absoluto identificando los nodos terminales en un componente dado, o dibujando caminos que conecten las salidas con la entrada. El nuevo gráfico ampliado obtiene
También se puede calcular mediante homotopía . Si un gráfico de flujo de control (conectado) se considera un complejo CW unidimensional llamado , el grupo fundamental de será . El valor de es la complejidad ciclomática. El grupo fundamental cuenta cuántos bucles hay a través del gráfico hasta la homotopía, alineándose como se esperaba.
En su presentación "Métricas de calidad de software para identificar riesgos" [8] para el Departamento de Seguridad Nacional, Tom McCabe presentó la siguiente categorización de la complejidad ciclomática:
Una de las aplicaciones originales de McCabe fue limitar la complejidad de las rutinas durante el desarrollo de programas. Recomendó que los programadores contaran la complejidad de los módulos que estaban desarrollando y los dividieran en módulos más pequeños siempre que la complejidad ciclomática del módulo superara 10. [2] Esta práctica fue adoptada por la metodología de pruebas estructuradas del NIST , que observó que desde la publicación original de McCabe, la cifra de 10 había recibido pruebas corroborativas sustanciales. Sin embargo, también señaló que en algunas circunstancias puede ser apropiado relajar la restricción y permitir módulos con una complejidad de hasta 15. Como la metodología reconoció que había razones ocasionales para ir más allá del límite acordado, formuló su recomendación como "Para cada módulo, limite la complejidad ciclomática a [el límite acordado] o proporcione una explicación escrita de por qué se superó el límite". [9]
La sección VI del artículo de McCabe de 1976 se ocupa de determinar cómo se ven los gráficos de flujo de control (GFC) de programas no estructurados en términos de sus subgráficos, que McCabe identificó. (Para más detalles, consulte el teorema del programa estructurado ). McCabe concluyó esa sección proponiendo una medida numérica de cuán cerca del ideal de programación estructurada está un programa dado, es decir, su "estructurabilidad". McCabe llamó a la medida que ideó para este propósito complejidad esencial . [2]
Para calcular esta medida, el CFG original se reduce iterativamente identificando subgrafos que tienen un único punto de entrada y un único punto de salida, que luego se reemplazan por un único nodo. Esta reducción corresponde a lo que haría un humano si extrajera una subrutina de la pieza de código más grande. (Hoy en día, un proceso de este tipo caería bajo el término general de refactorización ). El método de reducción de McCabe se denominó posteriormente condensación en algunos libros de texto, porque se consideraba una generalización de la condensación a los componentes utilizados en la teoría de grafos . [10] Si un programa está estructurado, entonces el proceso de reducción/condensación de McCabe lo reduce a un único nodo CFG. Por el contrario, si el programa no está estructurado, el proceso iterativo identificará la parte irreducible. La medida de complejidad esencial definida por McCabe es simplemente la complejidad ciclomática de este grafo irreducible, por lo que será precisamente 1 para todos los programas estructurados, pero mayor que uno para los programas no estructurados. [9] : 80
Otra aplicación de la complejidad ciclomática es determinar la cantidad de casos de prueba que son necesarios para lograr una cobertura de prueba exhaustiva de un módulo en particular.
Es útil debido a dos propiedades de la complejidad ciclomática, M , para un módulo específico:
Los tres números anteriores pueden ser iguales: cobertura de rama, complejidad ciclomática y número de rutas.
Por ejemplo, considere un programa que consta de dos declaraciones secuenciales if-then-else.
si ( c1 ()) f1 (); de lo contrario f2 (); si ( c2 ()) f3 (); de lo contrario f4 (); 
En este ejemplo, dos casos de prueba son suficientes para lograr una cobertura completa de la rama, mientras que cuatro son necesarios para una cobertura completa de la ruta. La complejidad ciclomática del programa es 3 (ya que el gráfico fuertemente conectado del programa contiene 9 aristas, 7 nodos y 1 componente conectado) ( 9 − 7 + 1 ).
En general, para probar completamente un módulo, se deben probar todas las rutas de ejecución a través del módulo. Esto implica que un módulo con un número de complejidad alto requiere un mayor esfuerzo de prueba que un módulo con un valor más bajo, ya que el número de complejidad más alto indica más rutas a través del código. Esto también implica que un módulo con mayor complejidad es más difícil de entender, ya que el programador debe comprender las diferentes rutas y los resultados de esas rutas.
Lamentablemente, no siempre es práctico probar todas las rutas posibles a través de un programa. Teniendo en cuenta el ejemplo anterior, cada vez que se agrega una instrucción if-then-else adicional, la cantidad de rutas posibles crece en un factor de 2. A medida que el programa crece de esta manera, llega rápidamente al punto en que probar todas las rutas se vuelve poco práctico.
Una estrategia de prueba común, adoptada por ejemplo por la metodología de Pruebas Estructuradas del NIST, es utilizar la complejidad ciclomática de un módulo para determinar la cantidad de pruebas de caja blanca que se requieren para obtener una cobertura suficiente del módulo. En casi todos los casos, según dicha metodología, un módulo debería tener al menos tantas pruebas como su complejidad ciclomática. En la mayoría de los casos, esta cantidad de pruebas es suficiente para ejercitar todas las rutas relevantes de la función. [9]
Como ejemplo de una función que requiere más que una simple cobertura de rama para realizar pruebas con precisión, reconsidere la función anterior. Sin embargo, suponga que para evitar que se produzca un error, cualquier código que llame a f1()o f3()también debe llamar al otro. [a] Suponiendo que los resultados de c1()y c2()son independientes, la función presentada anteriormente contiene un error. La cobertura de rama permite probar el método con solo dos pruebas, como los siguientes casos de prueba:
c1()devuelve verdadero y c2()devuelve verdaderoc1()devuelve falso y c2()devuelve falsoNinguno de estos casos expone el error. Sin embargo, si utilizamos la complejidad ciclomática para indicar el número de pruebas que necesitamos, el número aumenta a 3. Por lo tanto, debemos probar una de las siguientes rutas:
c1()devuelve verdadero y c2()devuelve falsoc1()devuelve falso y c2()devuelve verdaderoCualquiera de estas pruebas expondrá el error.
Múltiples estudios han investigado la correlación entre el número de complejidad ciclomática de McCabe con la frecuencia de defectos que ocurren en una función o método. [11] Algunos estudios [12] encuentran una correlación positiva entre la complejidad ciclomática y los defectos; las funciones y métodos que tienen la complejidad más alta tienden a contener también la mayor cantidad de defectos. Sin embargo, la correlación entre la complejidad ciclomática y el tamaño del programa (normalmente medido en líneas de código ) se ha demostrado muchas veces. Les Hatton ha afirmado [13] que la complejidad tiene la misma capacidad predictiva que las líneas de código. Los estudios que controlaron el tamaño del programa (es decir, comparar módulos que tienen diferentes complejidades pero tamaño similar) son generalmente menos concluyentes, y muchos no encuentran correlación significativa, mientras que otros sí la encuentran. Algunos investigadores cuestionan la validez de los métodos utilizados por los estudios que no encuentran correlación. [14] Aunque es probable que esta relación exista, no se utiliza fácilmente en la práctica. [15] Dado que el tamaño del programa no es una característica controlable del software comercial, se ha cuestionado la utilidad del número de McCabe. [11] La esencia de esta observación es que los programas más grandes tienden a ser más complejos y a tener más defectos. No se ha demostrado que la reducción de la complejidad ciclomática del código reduzca la cantidad de errores o fallos en ese código. Sin embargo, las normas de seguridad internacionales como la ISO 26262 exigen pautas de codificación que imponen una baja complejidad del código. [16]
f1se asigne algún recurso que f3se libere.Para calcular una representación gráfica de un código, podemos simplemente desensamblar su código ensamblador y crear un gráfico siguiendo las reglas: ...