Path Feasibility Analysis¶

Why It Matters¶

Naive analysis considers all syntactic paths, wasting effort on impossible cases and flagging spurious problems. Feasibility analysis focuses attention on real paths, eliminating false alarms. It also exposes hidden assumptions - a path you thought was feasible might be logically impossible, or vice versa.

The Key Move¶

For any path through a system, collect the conditions required to follow that path. Check if these conditions are consistent - can they all be true simultaneously? If yes, the path is feasible and must be considered. If no, the path is infeasible and can be ignored. Look for surprising results in both directions.

Classic Application¶

Symbolic execution. Rather than running code with concrete inputs, symbolically execute with variables, tracking path conditions. When you reach a branch "if (x > 10)", split into two paths with conditions "x > 10" and "x ≤ 10". If a path accumulates contradictory conditions like "x > 10 AND x < 5", it's infeasible and pruned.

Surprising Application¶

Career path planning. You want to be a "senior engineer at a FAANG company with strong work-life balance and rapid promotion." Check feasibility: FAANG companies have defined promotion timelines (slow), and work-life balance varies (often intense). The path might be infeasible as stated - the conditions contradict. Revise the goal or accept tradeoffs.

Failure Modes¶

Missing implicit conditions - declaring a path feasible because you didn't capture all constraints. Computational intractability - checking consistency is undecidable in general, so approximations may be wrong. Over-pruning - declaring paths infeasible based on assumptions that might not hold. Ignoring probabilities - treating unlikely paths as equivalent to impossible ones.

Go Deeper¶

King, "Symbolic Execution and Program Testing" (1976); Cadar & Sen, "Symbolic Execution for Software Testing: Three Decades Later" (2013)