Graph algorithms · how did I get here

Reaching conditions

Not "can execution reach this statement" but "what has to be true about the data for it to." Built up one statement at a time, with the two spots where the real implementation's shortcuts show.

Where this shows up in reverse engineering

Reachability answers "can execution get here at all." This page answers the sharper question underneath almost every real investigation into an unfamiliar program: under what condition on the data does it.

Triaging a crash report or an unexplained log line that points at one specific statement in a program nobody currently reading it wrote: slicing away everything that cannot reach that line, then building the boolean condition over what is left, turns "is this reachable" into "exactly what has to be true about the input for this to run" — a condition that can be checked against the actual input that triggered the problem.
Deciding whether a dangerous statement is really reachable under realistic input, for a security review of legacy code: a statement being structurally present in the source is not the same as it being reachable under any condition a real caller could satisfy — this page's technique is what turns "it's in there somewhere" into a specific, checkable boolean expression.
The control-side counterpart to a backward data slice: where reaching definitions and its Java-side analogs ask "what value reached this read," this page asks the same kind of backward question about control instead of data — same slice-then-combine shape, a different graph underneath it.

The problem

Reachability answers yes or no: can execution get from here to there at all. A sharper question, for a statement guarded by one or more IFs: not just that it can be reached, but under what condition on the data — spelled out as a boolean expression over the program's own fields, true exactly when some path to the statement is the one actually taken.

Two kinds of edge matter to this question. Leaving an ordinary statement, control always goes the one way it can — call that edge always taken. Leaving an IF, there are two edges: one taken exactly when the condition holds, one taken exactly when it does not. Tag each edge with which of the three it is, and the reaching condition of any statement becomes: for each way in, the edge's own condition combined with however that predecessor was reached — and if there is more than one way in, any one of them being true is enough.

First, slice away the dead ends

A real flowgraph has branches that never lead to the statement being asked about at all — error handlers, early STOP RUNs, unrelated sections. None of that is needed to answer the question, so the first step throws it away: keep only the statements and edges that lie on some path from the start to the target, nothing else. What is left is called a slice, and it comes with the start-to-target paths already topologically ordered — every statement after everything that can lead into it, the same order visiting a graph builds for exactly this reason.

Take a start statement A, two nested IFs, and a DISPLAY guarded by both — reusing the shape of a real example from this technique's own source project, with the field conditions written as C1 and C2:

flowchart TD
    A -->|always| B["B: IF C1"]
    B -->|C1| C
    B -->|"not C1"| Stop1["STOP RUN"]
    C -->|always| B2["B2: IF C2"]
    B2 -->|C2| D["D: DISPLAY"]
    B2 -->|"not C2"| Stop2["STOP RUN"]

Both STOP RUN arms never reach D. Sliced from A to D, they disappear entirely:

flowchart TD
    A -->|always| B
    B -->|"then: C1"| C
    C -->|"then: C2"| D

Four statements, three edges, nothing left that doesn't lead somewhere useful.

Building the condition, one statement at a time

Walking the slice in topological order, each statement's condition is built from its predecessors', already known by the time it is needed:

condition(v) = OR, over every incoming edge (u → v):
AND(that edge's own condition, condition(u))

Diagrams below mark the statement whose condition a step is computing in amber.

Computing the condition at each of A, B, C, D (4 steps)

Nothing computed yet.

flowchart TD
    A -->|always| B
    B -->|"then: C1"| C
    C -->|"then: C2"| D

A has no incoming edge in the slice at all — it is the start. With nothing to combine, its condition is the empty case.

flowchart TD
    A -->|always| B
    B -->|"then: C1"| C
    C -->|"then: C2"| D
    class A changed
    classDef changed fill:#f5b041,stroke:#f5b041,color:#000

condition(A)

FALSE

B's only way in: the always-taken edge from A. Combine that edge's own condition (always true) with A's condition.

flowchart TD
    A -->|always| B
    B -->|"then: C1"| C
    C -->|"then: C2"| D
    class B changed
    classDef changed fill:#f5b041,stroke:#f5b041,color:#000

condition(B)

TRUE

C's only way in: the then-edge from B, carrying C1. Combined with B's (true) condition, C1 survives unchanged.

flowchart TD
    A -->|always| B
    B -->|"then: C1"| C
    C -->|"then: C2"| D
    class C changed
    classDef changed fill:#f5b041,stroke:#f5b041,color:#000

condition(C)

D's only way in: the then-edge from C, carrying C2. Combined with C's condition, C1: both now have to hold.

flowchart TD
    A -->|always| B
    B -->|"then: C1"| C
    C -->|"then: C2"| D
    class D changed
    classDef changed fill:#f5b041,stroke:#f5b041,color:#000

condition(D)

AND(C2, C1)

AND(C2, C1) — reach D exactly when both guards hold. That is the literal answer this technique's own source project documents for the real COBOL this shape is drawn from.

A branch that merges back

One statement can have more than one way in. Change the shape so both of B's arms lead to D instead of one of them being a dead end:

flowchart TD
    A -->|always| B["B: IF C1"]
    B -->|C1| C
    B -->|"not C1"| X
    C -->|always| D
    X -->|always| D

Computing the condition with two ways into D (5 steps)

Nothing computed yet.

flowchart TD
    A -->|always| B
    B -->|C1| C
    B -->|"not C1"| X
    C -->|always| D
    X -->|always| D

A: no incoming edge. Same empty case as before.

flowchart TD
    A -->|always| B
    B -->|C1| C
    B -->|"not C1"| X
    C -->|always| D
    X -->|always| D
    class A changed
    classDef changed fill:#f5b041,stroke:#f5b041,color:#000

condition(A)

FALSE

B: always-taken from A. Same as before.

flowchart TD
    A -->|always| B
    B -->|C1| C
    B -->|"not C1"| X
    C -->|always| D
    X -->|always| D
    class B changed
    classDef changed fill:#f5b041,stroke:#f5b041,color:#000

condition(B)

TRUE

C: then-edge from B, carrying C1. X: else-edge from B, carrying NOT C1.

flowchart TD
    A -->|always| B
    B -->|C1| C
    B -->|"not C1"| X
    C -->|always| D
    X -->|always| D
    class C changed
    classDef changed fill:#f5b041,stroke:#f5b041,color:#000

condition(C)

condition(X)

NOT C1

D: two ways in, both always-taken, from C and from X. Combine each edge with its source's condition, then take either being enough.

flowchart TD
    A -->|always| B
    B -->|C1| C
    B -->|"not C1"| X
    C -->|always| D
    X -->|always| D
    class D changed
    classDef changed fill:#f5b041,stroke:#f5b041,color:#000
    linkStyle 3 stroke:#f5b041,stroke-width:3px
    linkStyle 4 stroke:#f5b041,stroke-width:3px

condition(D)

OR(C1, NOT C1)

Reach D when C1 holds, or when it does not — which is every possible value C1 could have. D is unconditionally reached once B is, which is exactly what the diagram shows by inspection: both of B's only two arms lead to D. The answer the walk produces, though, is the literal expression OR(C1, NOT C1), not the word "always" — see below.

What goes wrong

The start statement's own condition reads FALSE, not TRUE. It genuinely does, in the real implementation — a statement with no incoming slice edge gets the empty case of the rule above, and OR of nothing is false, not true. Looked at on its own, that reads backward: the start is reached unconditionally, so TRUE is the answer a person would expect. It never surfaces as a wrong final answer in either walk above, but only because of the next point.
AND with a false operand returns the other operand, not false, when that operand sits on the left. Also real: the actual rule returns lhs whenever either side is false, which is correct boolean AND only when lhs itself is the false one. When rhs is the false side instead — exactly the shape at B above, combining the always-true edge with A's wrongly-false condition — the result comes back as the (non-false) lhs, which happens to be the right answer for an always-taken edge out of the start. The two quirks cancel out for every statement directly off the start; nothing here checks that they always will.
OR(C1, NOT C1) is never recognised as TRUE. It is a tautology — true for every value C1 could hold — but the rule only simplifies an operand that is already the literal constant true or false, not one that is logically guaranteed to be. The merged-branch example above reports the unsimplified expression. This is a known, stated limitation of the real implementation, not an oversight found by reading between the lines of the code.
None of this holds once the slice has a cycle. The rule above assumes every predecessor's condition is already known by the time a statement needs it — true only when the slice is a DAG, which a slice containing a loop is not. A predecessor not yet computed silently defaults to TRUE, understating what is actually required rather than raising an error.

Where this is used

Answering "what has to be true for this line to run at all" for a specific statement someone has pointed at — a crash report, a line a debugger stopped on, a DISPLAY whose output someone is trying to explain. The slice step already does most of the narrowing: everything not on some path to the statement in question is gone before the condition work even starts, so the condition itself only ever has to describe the guards that are actually relevant.