Explosión de trayectoria

En informática , la explosión de rutas es un problema fundamental que limita la escalabilidad y/o la completitud de ciertos tipos de análisis de programas , incluyendo el fuzzing , la ejecución simbólica y el análisis estático sensible a rutas . La explosión de rutas se refiere al hecho de que el número de rutas de flujo de control en un programa crece exponencialmente ("explota") con el aumento del tamaño del programa e incluso puede ser infinito en el caso de programas con iteraciones de bucle ilimitadas. ^{[ 1 ] [ 2 ]} Por lo tanto, cualquier análisis de programa que intente explorar las rutas de flujo de control a través de un programa tendrá un tiempo de ejecución exponencial en la longitud del programa (o potencialmente incluso fallará al terminar con ciertas entradas), o tendrá que optar por analizar solo un subconjunto de todas las rutas posibles. Cuando un análisis solo explora un subconjunto de todas las rutas, la decisión de qué rutas analizar a menudo se toma heurísticamente . ^{[ 3 ]}