Reaching conditions

Read first: Visiting a graph

Whether a statement runs is decided by every IF on every path into it: along a path all its guards must hold, where paths merge any one will do, and a branch that never reaches the statement must add nothing. Reachability only says yes or no, and reading guards off by eye across GO TOs misses one or counts a branch that goes elsewhere.

In this page's example, from cobol-rekt's README, an IF WS-NUM1 > 10 jumps to an IF WS-NUM1 = 201 that guards a DISPLAY. The technique slices away the two STOP RUN arms, walks the four statements left in topological order, and gives the DISPLAY the condition AND(C2, C1): WS-NUM1 = 201 and WS-NUM1 > 10. It works on acyclic slices only.

Topological order is explained in Visiting a graph.

The example: a DISPLAY behind two IFs

The page's model of the README program: start A, the IFs as B and C, the DISPLAY as D, a STOP RUN on each arm not taken. The conditions are written C1 and C2:

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

Neither STOP RUN in the graph above leads to D, so the first step throws both away. What is left is the slice from A to D: only the statements and edges on some path from the start to the target. Four statements, three edges:

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

The answer for the slice above, one condition per statement, is what the walk below builds. D's is the one the question was about:

The lines of the README program that the graph models. GO TO SA2 is the then-edge from B to C; the model leaves out the paragraph labels:

SA1.
    IF WS-NUM1 > 10
     THEN
         GO TO SA2.
    STOP RUN.
SA2.
    IF WS-NUM1 = 201
     THEN
         DISPLAY "IT IS DONE".
 STOP RUN.

cobol-rekt's README gives this as the reaching condition it prints for the DISPLAY, reformatted here onto two lines. It is AND(C2, C1), with C2 first, as in the table:

and(eq(ref('WS-NUM1'), primitive(201.0)),
    gt(ref('WS-NUM1'), primitive(10.0)))

       IDENTIFICATION DIVISION.
       PROGRAM-ID.    STOPRUN.
       AUTHOR.        MOJO
       DATE-WRITTEN.  SEP 2024.
       ENVIRONMENT DIVISION.
       DATA DIVISION.
       WORKING-STORAGE SECTION.
            01 WS-NUM1 PIC 9(9) VALUE 5.
       PROCEDURE DIVISION.
       S SECTION.
       SA1.
           IF WS-NUM1 > 10
            THEN
                GO TO SA2.
           STOP RUN.
       SA2.
           IF WS-NUM1 = 201
            THEN
                DISPLAY "IT IS DONE".
        STOP RUN.

Step by step

The walk visits the slice in topological order, so every statement comes after everything that leads into it, and its predecessors' conditions are already known when it needs them. Each step applies this rule once:

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

Step 4 is the rule box in full: one incoming edge, C → D, whose own condition is C2, ANDed with condition(C), which step 3 left as C1. Each statement in this slice has one way in, so the OR line never has more than one operand here. Step 1 is the OR over no edges at all. AND(C2, C1) means D is reached exactly when both guards hold, and it matches the README output above.

Why each edge carries a condition

Reachability on the first graph says only that D can be reached. To get a condition, every edge is tagged with its own. Leaving an ordinary statement, as at A, control goes the one way it can: always taken, condition TRUE. Leaving an IF, the then-edge carries the IF's condition and the else-edge carries its negation. For the five edges of the first graph:

The rule box then reads these off the three rows marked "yes": steps 2, 3 and 4 each took one row's condition and ANDed it with the predecessor's. The two "no" rows would only matter if they led to D; the next example changes the shape so that an else-edge does.

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

Step 4's OR(C1, NOT C1) says reach D when C1 holds, or when it does not: every possible value. The graph above shows the same by inspection, since both of B's arms lead to D. The walk's answer, though, is the literal expression, not the word "always"; the third bullet below shows why.

What goes wrong

Each bullet comes with the small case that shows it. The first three are taken from the two walks above.

• The start statement's own condition reads FALSE, not TRUE. It genuinely does, in the real implementation. A statement with no incoming edge in the whole flowgraph (in practice the program's first statement, the start both walks use) gets the OR over nothing, which the implementation starts from FALSE. Step 1 of both walks shows it:

  statement	incoming edges	implementation	correct
  A	none	FALSE	TRUE

  The start is reached unconditionally, so TRUE is what a person would expect. It never surfaces as a wrong final answer for D in either walk, but only because of the next point.
• AND(lhs, rhs) returns lhs if either side is FALSE, which is correct only when lhs is the FALSE one. Also real. In the implementation's AND, abridged, lhs is the edge's own condition and rhs the predecessor's:

  if (isFalse(lhs) || isFalse(rhs)) return lhs;
  else if (isTrue(lhs)) return rhs;
  else if (isTrue(rhs)) return lhs;
  return AND(lhs, rhs);

  The three ANDs of the first walk, run through those lines:

  step	lhs (edge)	rhs (predecessor)	returns	boolean AND
  2, at B	TRUE	FALSE	TRUE	FALSE
  3, at C	C1	TRUE	C1	C1
  4, at D	C2	C1	AND(C2, C1)	AND(C2, C1)

  In step 2, rhs is the false side: 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:

  C1	NOT C1	OR(C1, NOT C1)
  TRUE	FALSE	TRUE
  FALSE	TRUE	TRUE

  But the rule only simplifies an operand that is already the literal constant true or false, not one that is logically guaranteed to be, so step 4 of the merge walk 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 runs once the slice has a cycle. The rule box needs every predecessor's condition known before a statement needs it, which only a topological order guarantees. Give the slice a loop, as below, and there is none: B has to come before C because of B → C, and after it because of C → B. Building the order throws an exception.

  flowchart TD
      A -->|always| B
      B -->|always| C["C: IF C1"]
      C -->|"then: C1"| B
      C -->|"else: NOT C1"| D
      linkStyle 1 stroke:#f5b041,stroke-width:3px
      linkStyle 2 stroke:#f5b041,stroke-width:3px
  

• Predecessors outside the slice count as TRUE. Even for an acyclic slice, the condition pass reads each statement's incoming edges from the whole flowgraph, not the slice. A predecessor outside the slice has no computed condition and silently defaults to TRUE, understating what is actually required rather than raising an error. Below, P also leads into D but is not reached from A, so the slice from A to D is A, B, D:

  flowchart TD
      A -->|always| B["B: IF C1"]
      B -->|"then: C1"| D
      B -->|"else: NOT C1"| Stop["STOP RUN"]
      P["P: not reached from A"] -->|always| D
      linkStyle 3 stroke:#f5b041,stroke-width:3px,stroke-dasharray:4
  

  Worked by the rule and the two quirks above, not run:

  incoming edge of D	AND(edge, predecessor)	gives
  B → D	AND(C1, TRUE)	C1
  P → D	AND(TRUE, TRUE: P's default)	TRUE
  OR of both	OR(C1, TRUE)	TRUE

  From A, D runs only when C1 holds, but the reported condition is TRUE: the one edge from P wipes out the guard.

Where this shows up in reverse engineering

• Triaging a crash report or a log line that points at one statement, like the DISPLAY in the listing: the answer becomes WS-NUM1 = 201 and WS-NUM1 > 10, checkable against the input that triggered it.
• Security review of legacy code: a dangerous statement in the source may be reachable under no condition a real caller can satisfy; D's row in the table at the top is what to check.
• The control-side counterpart to a backward data slice: the data version asks "what value reached this read"; this asks the same backward question about control, with the same slice-then-combine shape.

Where this is used

The slice does most of the narrowing: in the example both STOP RUNs were gone before any condition was built.

The same idea, under the same name, drives control-flow structuring in decompilers: Yakdan et al. compute reaching conditions over acyclic regions to turn a recovered flowgraph back into if/else without pattern matching.^[1]

References

1. K. Yakdan, S. Eschweiler, E. Gerhards-Padilla, and M. Smith. "No More Gotos: Decompilation Using Pattern-Independent Control-Flow Structuring and Semantics-Preserving Transformations." Network and Distributed System Security Symposium (NDSS 2015), 2015. Reaching conditions over acyclic regions as the basis for pattern-independent structuring.