Complejidad ciclomática

Hay varias formas de definir la complejidad ciclomática de una sección de código fuente . Una forma común es el número de rutas linealmente independientes dentro de ella. Un conjunto${\displaystyle S}$de caminos es linealmente independiente si el conjunto de aristas de cualquier camino${\displaystyle P}$en${\displaystyle S}$no es la unión de conjuntos de aristas de los caminos en algún subconjunto de${\displaystyle S/P}$Si el código fuente no contiene instrucciones de control de flujo (condicionales o puntos de decisión), la complejidad sería 1, ya que solo habría una ruta a través del código. Si el código tuviera una instrucción IF de una sola condición , habría dos rutas a través del código: una donde la instrucción IF es VERDADERA y otra donde es FALSA. En este caso, la complejidad sería 2. Dos instrucciones IF anidadas de una sola condición, o una instrucción IF con dos condiciones, producirían una complejidad de 3.

Otra forma de definir la complejidad ciclomática de un programa es observar su grafo de flujo de control , un grafo 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 ].}

$${\displaystyle M=E-N+2P,}$$

dónde

• E = el número de aristas del grafo.
• N = el número de nodos del grafo.
• P = el número de componentes conectadas .

Una formulación alternativa de esto, como se propuso originalmente, es usar un grafo en el que cada punto de salida está conectado de vuelta al punto de entrada. En este caso, el grafo es fuertemente conexo . Aquí, la complejidad ciclomática del programa es igual al número ciclomático de su grafo (también conocido como el primer número de Betti ), que se define como ^{[ 2 ].}$${\displaystyle M=E-N+P.}$$

Esto puede interpretarse como el cálculo del número de ciclos linealmente independientes que existen en el grafo: aquellos ciclos que no contienen otros ciclos en su interior. Dado que cada punto de salida regresa al punto de entrada, existe 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 ].}$${\displaystyle M=E-N+2.}$$

La complejidad ciclomática puede aplicarse a varios programas o subprogramas simultáneamente (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 solo punto de salida es igual al número de puntos de decisión (sentencias "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, se deben 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 $${\displaystyle \pi -s+2,}$$ dónde${\displaystyle \pi }$es el número de puntos de decisión en el programa y s es el número de puntos de salida. ^{[ 5 ] [ 6 ]}

En su presentación " Métricas de calidad de software para identificar riesgos" ^{[ 7 ]} para el Departamento de Seguridad Nacional, Tom McCabe introdujo la siguiente categorización de complejidad ciclomática:

• 1–10: Procedimiento sencillo, poco riesgo.
• 11–20: Más complejo, riesgo moderado
• 21–50: Complejo, de alto riesgo
• > 50: Código imposible de probar, riesgo muy alto

Una de las aplicaciones originales de McCabe fue limitar la complejidad de las rutinas durante el desarrollo de programas. Recomendó que los programadores calcularan la complejidad de los módulos que estaban desarrollando y los dividieran en módulos más pequeños cuando 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 evidencia corroborativa sustancial. Sin embargo, también señaló que, en algunas circunstancias, podría ser apropiado flexibilizar la restricción y permitir módulos con una complejidad de hasta 15. Dado que la metodología reconoció que existían razones ocasionales para superar el 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 trata sobre cómo son los grafos de flujo de control (GFC) de los programas no estructurados en términos de sus subgrafos, que McCabe identificó. (Para más detalles, véase el teorema del programa estructurado ). McCabe concluyó esa sección proponiendo una medida numérica de cuán cerca está un programa dado del ideal de programación estructurada, es decir, su "estructuralidad". McCabe denominó complejidad esencial a la medida que ideó para este propósito . ^{[ 2 ]}

Para calcular esta medida, el CFG original se reduce iterativamente identificando subgrafos con un único punto de entrada y salida, que luego se reemplazan por un único nodo. Esta reducción corresponde a lo que haría un humano si extrajera una subrutina del fragmento de código más grande. (Actualmente, este proceso se englobarí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, ya que se consideraba una generalización de la condensación a componentes utilizados en la teoría de grafos . ^{[ 10 ]} Si un programa está estructurado, 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 consiste en determinar el número de casos de prueba necesarios para lograr una cobertura de prueba exhaustiva de un módulo en particular.

Resulta útil debido a dos propiedades de la complejidad ciclomática, M , para un módulo específico:

• M es un límite superior para el número de casos de prueba necesarios para lograr una cobertura completa de las ramas .
• M es un límite inferior para el número de rutas a través del grafo de flujo de control (GFC). Suponiendo que cada caso de prueba toma una ruta, el número de casos necesarios para lograr la cobertura de rutas es igual al número de rutas que realmente se pueden tomar. Pero algunas rutas pueden ser imposibles, por lo que, si bien el número de rutas a través del GFC es claramente un límite superior para el número de casos de prueba necesarios para la cobertura de rutas, este último número (de rutas posibles ) a veces es menor que M.

Los tres números anteriores pueden ser iguales: cobertura de sucursales${\displaystyle \leq }$complejidad ciclomática${\displaystyle \leq }$número de caminos.

Por ejemplo, consideremos un programa que consta de dos sentencias if-then-else secuenciales.

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 ramas, mientras que cuatro son necesarios para una cobertura completa de rutas. La complejidad ciclomática del programa es 3 (ya que el grafo fuertemente conectado para el programa contiene 8 aristas, 7 nodos y 1 componente conectado) ( 8 − 7 + 2 ).

En general, para probar completamente un módulo, se deben probar todas las rutas de ejecución a través del mismo. Esto implica que un módulo con un número de complejidad alto requiere más esfuerzo de prueba que un módulo con un valor menor, ya que un 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 dichas rutas. ^{[ 11 ]} La complejidad ciclomática captura solo un aspecto del software, por lo que basarse únicamente en ella puede proporcionar una representación incompleta de la complejidad general de un programa.

Desafortunadamente, no siempre es práctico probar todas las rutas posibles en un programa. En el ejemplo anterior, cada vez que se agrega una instrucción if-then-else, el número de rutas posibles se duplica. A medida que el programa crece de esta manera, rápidamente llega un punto en el que probar todas las rutas se vuelve inviable.

Una estrategia de prueba común, defendida, por ejemplo, por la metodología de Pruebas Estructuradas del NIST, consiste en utilizar la complejidad ciclomática de un módulo para determinar el número de pruebas de caja blanca necesarias para obtener una cobertura suficiente del módulo. En casi todos los casos, según esta metodología, un módulo debería tener al menos tantas pruebas como su complejidad ciclomática. En la mayoría de los casos, este número de pruebas es suficiente para probar todas las rutas relevantes de la función. ^{[ 9 ]}

Como ejemplo de una función que requiere más que una simple cobertura de ramas para probarse con precisión, reconsideremos la función anterior. Sin embargo, supongamos que para evitar que se produzca un error, cualquier código que llame a una f1()u f3()otra función también debe llamar a la otra. ^{[ a ]} ​​Suponiendo que los resultados de c1()ambas funciones c2()son independientes, la función presentada anteriormente contiene un error. La cobertura de ramas permite probar el método con solo dos pruebas, como los siguientes casos de prueba:

• c1()devuelve verdadero y c2()devuelve verdadero
• c1()devuelve falso y c2()devuelve falso

Ninguno 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 falso
• c1()devuelve falso y c2()devuelve verdadero

Cualquiera de estas pruebas revelará el error.

Múltiples estudios han investigado la correlación entre el número de complejidad ciclomática de McCabe y la frecuencia de defectos que ocurren en una función o método. ^{[ 12 ]} Algunos estudios ^{[ 13 ]} encuentran una correlación positiva entre la complejidad ciclomática y los defectos; las funciones y los métodos que tienen la mayor complejidad tienden también a contener la mayor cantidad de defectos. Sin embargo, la correlación entre la complejidad ciclomática y el tamaño del programa (generalmente medido en líneas de código ) se ha demostrado muchas veces. ^{[ 14 ]} Les Hatton ha afirmado ^{[ 15 ]} 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, comparando módulos que tienen diferentes complejidades pero tamaño similar) son generalmente menos concluyentes, ya que muchos no encuentran una 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. ^{[ 16 ]} Aunque es probable que esta relación exista, no es fácil de usar en la práctica. ^{[ 17 ]} Dado que el tamaño del programa no es una característica controlable del software comercial , la utilidad del número de McCabe ha sido cuestionada. ^{[ 12 ]} 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 reducir la complejidad ciclomática del código reduzca la cantidad de errores o fallos en dicho código. Sin embargo, las normas internacionales de seguridad, como la ISO 26262 , exigen directrices de codificación que recomiendan supervisar y procurar reducir la complejidad del código; cuando la complejidad es alta, se esperan medidas adicionales, incluido el escrutinio de las actividades de verificación y validación más difíciles , incluidas las pruebas. ^{[ 18 ]}