Bounding walks by crossings, and flagging what was cut

When an exact walk across programs costs too much, stop it after a fixed number of program crossings, keep what it found, and mark every answer the stop cut directly.

Where this shows up in reverse engineering

Cobble's last dataflow stage, cobble-dataflow-combine, answers one question for a CICS corpus: where can each dynamic jump go? EXEC CICS XCTL PROGRAM(WS-NEXT-PGM) names its target through a field, and that field's bytes may have come from another program. The combine walks those bytes backwards across programs until it finds literals.

• On a large CICS corpus (about 3,800 programs and 19,000 jumps) the earlier fixes made each walk cheap: a memo over strongly connected components (explainer 10), a per-program memo, an edge index, and places told apart by their bytes alone. Even so, one cyclic group of walks across links grew past a million places on the stack.
• The goal was narrow. Dynamic targets on that corpus come in three shapes: a literal VALUE in working storage, a MOVE 'LITERAL' TO WS-FIELD, and (about 5%) a field a program reads from its DFHCOMMAREA and then XCTLs to. These need 0, 0 and 1 program crossings. An answer that walks a few crossings and says honestly where it stopped covers all three.

The problem

The walk's unit is a place: a program, a statement in it, and a byte range. A statement reached under many different byte ranges is many places. Where programs hand areas to each other in a ring, every program in the ring can reach every other under many ranges, so one cyclic group holds the product of the two. On the large corpus that group grew past a million places.

The memo already answers each place once per round. The remaining cost is the number of places, which is a property of the corpus. No exact fix could be guaranteed faster without building it and measuring it on the corpus. What was needed was a walk whose cost has a known bound, and whose answers say when they may be incomplete.

The intuition

Inside one program a walk is cheap: the per-program memo answers each position once for the whole run. The expensive part is leaving the program. There are three ways to leave, and each is a crossing:

• RECEIVED — the bytes came in through the linkage section, so go to every caller that jumped here and look at what it handed over.
• RETURNED — the bytes were written back by a program this one LINKed or CALLed, so go to that callee's exits (a read-back).
• RETRIEVED — the bytes came from EXEC CICS RETRIEVE, so go to every program that STARTed this transaction.

Give each place a counter: how many crossings it took to get here. When a place at the limit wants to cross again, it does not. It keeps the values it found in its own program, drops the crossings, and adds the reason hop-limit to what it reports. That reason travels back to the jump that started the walk, the same way every other reason in a value set does.

The cost is now bounded by the programs within N crossings of the jump, not by the size of the corpus. The answer is a subset of the exact answer. A target whose own walk was cut says so; a target shortened only because a cut elsewhere hid a link does not (see what goes wrong).

A second, separate switch, --skip-readbacks, drops one kind of crossing altogether: RETURNED stops are not followed, and the bytes report readback-skipped.

The example

Three programs in a chain. PROGC stamps 'PROGQ' into the first eight bytes of its commarea and XCTLs to PROGP. PROGP and PROGT have the same shape: each picks its next program either from a literal or from the first eight bytes of the commarea it received, and hands that commarea on. Neither PROGQ nor PROGM is in the analysed set.

       IDENTIFICATION DIVISION.
       PROGRAM-ID. PROGC.
       DATA DIVISION.
       WORKING-STORAGE SECTION.
       01  WS-AREA.
           05  WS-FROM          PIC X(8).
           05  WS-REST          PIC X(12).
       PROCEDURE DIVISION.
           MOVE 'PROGQ' TO WS-FROM.
           EXEC CICS XCTL PROGRAM('PROGP')
                COMMAREA(WS-AREA) LENGTH(20) END-EXEC.

       IDENTIFICATION DIVISION.
       PROGRAM-ID. PROGP.
       DATA DIVISION.
       WORKING-STORAGE SECTION.
       01  WS-NEXT              PIC X(8).
       LINKAGE SECTION.
       01  DFHCOMMAREA.
           05  LK-FROM          PIC X(8).
           05  LK-REST          PIC X(12).
       PROCEDURE DIVISION.
           IF EIBCALEN = 0
               MOVE 'PROGT' TO WS-NEXT
           ELSE
               MOVE LK-FROM TO WS-NEXT
           END-IF.
           EXEC CICS XCTL PROGRAM(WS-NEXT)
                COMMAREA(DFHCOMMAREA) LENGTH(20) END-EXEC.

       IDENTIFICATION DIVISION.
       PROGRAM-ID. PROGT.
      *    Same as PROGP, with 'PROGM' in place of 'PROGT'.

Run to the end, the combine knows two edges: PROGC → PROGP (a literal) and PROGP → PROGT (from PROGP's own MOVE 'PROGT', so it is found at every limit). The question is the target of PROGT's XCTL. Exactly, it is PROGM or PROGQ: PROGQ travels from PROGC through PROGP's commarea untouched and into PROGT.

Step by step

The walk from PROGT's XCTL meets three places. Each row is a place, what its own program gives, and where it would cross next. The last column is the place's hop count.

The second place is PROGP's commarea at the moment PROGP hands it on. PROGP never writes LK-FROM, so the bytes there are what PROGP received, and the walk must cross again.

PROGP's own target needs one crossing fewer: its walk starts at its XCTL with {PROGT} found locally and reaches PROGC at hops 1. These are the rows the test asserts:

Read the first two rows for PROGT together: the answer at 0 and at 1 is the same, yet both still carry hop-limit, and at 2 it grows. That is why the reason matters more than the comparison.

The rule

Why hops are counted only when a limit is set: the hop count is part of the place. With no limit, a cycle across programs would come back to the same program, statement and bytes with a larger count — a new place on every lap, and the walk would never end. With the count held at 0, the lap returns to a place already seen and the memo closes the cycle. With a limit N, a place can appear under at most N + 1 counts, so laps run out.

Why a target without hop-limit is exact: expansion depends on the hop count only through the cut. If no place reached from a jump was cut, each was expanded exactly as it would be with no limit, so the walk reaches the same programs, statements and bytes, and joins the same values and reasons. (This holds within a round, given the same edges; see below.)

What goes wrong

• Cut targets are subsets. A hop-limit row keeps every value it found, and they are all real, but there may be more. It is never silent: the reason is on the row in targets.jsonl.
• Choosing N is empirical. Raise N until targets.jsonl and links.jsonl stop changing between N and N + 1. Rows carrying hop-limit can change, and so can rows that depend on a link a cut hid. On the large corpus, 3 hops took about 1 s, 4 about 10 s, 5 about a minute; the targets at 3 and 4 were identical, but 3 targets still carried hop-limit, so 5 was chosen. On CardDemo, the targets were identical with no limit, with --max-hops 1, and with both flags.
• Identical at N and N + 1 is not proof. The example shows it: PROGT's target is the same at 0 and 1 and grows at 2, because the middle program only relays bytes. Every relay program in a chain is one more crossing that finds nothing. The hop-limit reason is the honest signal; the comparison is a heuristic.
• Rounds couple targets. The combine runs in rounds: a target's values become new edges, and edges feed other walks. A cut that hides a program name hides the edge to that program too, and a walk into that program then sees fewer callers without itself being cut. This follows from reading the code; it was not reproduced. The cut target that hid the name does carry hop-limit, so the trail starts at a flagged row.
• Cost is per program, not per statement. N bounds how many programs a walk enters, not how big they are. Under a limit a place can also exist under up to N + 1 hop counts, so the memo may hold that many copies of it.
• --skip-readbacks loses a whole shape. A program that LINKs to a routine which writes the next program's name into the commarea, and then XCTLs to that name, resolves to nothing with the flag set: the row says readback-skipped and has no candidate.

In cobble

The combine (cobble-dataflow-combine) applies the limit when --max-hops is set; with no limit, a walk follows links as far as they go. A walk cut at the limit carries the reason hop-limit. --skip-readbacks leaves RETURNED stops unfollowed, and the bytes report readback-skipped. Each place is answered once per round, as memoised reachability explains. Both flags are in the field dataflow reference.