Path explosion

<p>In <a href="/facts/Computer_science/lN3pEyPz">computer science</a>, path explosion is a fundamental problem that limits the <a href="/facts/Scalability/jh7JomPa">scalability</a> and/or <a href="/facts/Completeness_(logic)/GzK9zLnu">completeness</a> of certain kinds of <a href="/facts/Program_analysis/oaJTAjhH">program analyses</a>, including <a href="/facts/Fuzzing/I1GK5kxr">fuzzing</a>, <a href="/facts/Symbolic_execution/EvcoXl9m">symbolic execution</a>, and path-sensitive <a href="/facts/Static_analysis/YkJEVPxs">static analysis</a>. Path explosion refers to the fact that the number of <a href="/facts/Control_flow/2XTDfErC">control-flow</a> paths in a program <a href="/facts/Exponential_growth/m4yEqKJ7">grows exponentially</a> ("explodes") with an increase in program size and can even be infinite in the case of programs with unbounded loop iterations. Therefore, any program analysis that attempts to explore control-flow paths through a program will either have <a href="/facts/Computational_complexity/Qenh22Ja">exponential runtime</a> in the length of the program (or potentially even <a href="/facts/Divergence_(computer_science)/RmN14Gft">failure to terminate</a> on certain inputs), or will have to choose to analyze only a subset of all possible paths. When an analysis only explores a subset of all paths, the decision of which paths to analyze is often made <a href="/facts/Heuristic/BcBEkv9c">heuristically</a>.
</p>

Path explosion open-in-new

Path explosion