Answering every walk once: strongly connected components and a memo

Thousands of jumps each ask what their target bytes can hold, and their walks back through the programs keep reaching the same places. Answer each place once, and let every walk that reaches it stop there.

Where this shows up in reverse engineering

The last stage of cobble's field dataflow, the combine, resolves dynamic call targets across programs: CALL WS-PGM, EXEC CICS XCTL PROGRAM(WS-NEXT-PGM). When the name was put into the field in another program and handed over in a commarea, the answer is only found by walking back through the program that sent it, and the one that sent it there.

• CICS programs hand control in rings. A menu transfers to a screen, the screen transfers back to the menu, and the commarea goes round with them. Walked backwards, the graph of "where could these bytes have come from" is full of cycles, and every program on a ring sees the same handful of commarea bytes.
• Many questions, one graph. On a large CICS corpus (about 3,800 programs, about 19,000 jumps) each jump started its own walk. One walk alone reached about 311,000 vertices at about 850 program positions, and the jumps next to it walked the same commarea chains again.
• The same shape appears whenever many starts ask a reachability question of one fixed graph: which sources can taint this sink, which allocation sites can this variable point to. Solving the graph once and sharing the answers is the standard way out.

The problem

A place is a program, a node in it (a statement), and a byte range. The combine's question for a jump is: what values can the jump's target bytes hold? It answers by walking back from the jump's place. Each step looks at one place, collects any literal values written there, and lists the places the bytes were copied from: a MOVE inside the program, or, at the top of a program's linkage section, the caller that handed the commarea in.

The walk's answer is everything found at every place it reaches, joined. Done once per jump, the cost is the number of jumps times the number of places each one reaches. When most jumps reach the same few hundred places, almost all of that work is repeated.

The intuition

A place's answer does not depend on who is asking. It is the join of what the place finds itself and the answers of every place it leads to. So work it out once, keep it, and when another walk arrives at an answered place, take the answer and go no further.

Cycles get in the way of "work out the successors first". If A leads to C, C to B, and B back to A, none of them can be finished before the others. But they do not need to be: every place on a cycle reaches every other, so they all reach exactly the same set of places and all have the same answer. A maximal set of places that all reach each other is a strongly connected component. Solve the component as one unit: its answer is the join of what each member finds itself, plus the answers of the places the component leads out to.

Tarjan's algorithm finds the components during one depth-first walk, and it finishes each component only after every component it leads to. That is exactly the order the answers need. It numbers places in the order it first visits them (the index), and keeps for each the lowest index it can get back to through places still in play (the low value). Visited places go on a stack. When the walk backs out of a place whose low equals its own index, nothing below it reaches anything older, so that place and everything above it on the stack form one component. Pop them, give them their shared answer, and move on.

The textbook version is recursive, one call per place on the current path. Cobble keeps the path in explicit lists instead: the combine had already crashed once on Python's recursion limit when it recursed once per program, and a walk across a corpus can be millions of places deep.

Two smaller changes make each step cheaper. A step that reaches the top of a program asks which links lead into it; it used to scan every link the round knew, and a profiler showed every sample inside that scan. The links are now indexed by what each step looks them up by. And a place is told apart by its bytes alone: the same bytes reached under a group name, an elementary name or a REDEFINES name are one place, since the walk never reads the name.

The example

Four programs hand an 8-byte commarea round. PROGA transfers to PROGB, PROGB to PROGC, PROGC back to PROGA: a 3-program ring. PROGD enters the ring from outside, with 'PROGE' in the first 8 bytes. PROGB and PROGC each have a dynamic XCTL to whatever name the commarea carries. Those two dynamic jumps are what the combine has to answer.

       IDENTIFICATION DIVISION.
       PROGRAM-ID. PROGA.
       DATA DIVISION.
       WORKING-STORAGE SECTION.
       01  WS-AREA.
           05  WS-NEXT-PGM      PIC X(8).
       LINKAGE SECTION.
       01  DFHCOMMAREA.
           05  CA-NEXT-PGM      PIC X(8).
       PROCEDURE DIVISION.
       MAIN-PARA.
           MOVE DFHCOMMAREA TO WS-AREA.
           EXEC CICS XCTL PROGRAM('PROGB') COMMAREA(WS-AREA) END-EXEC.

       IDENTIFICATION DIVISION.
       PROGRAM-ID. PROGB.
      *    Same data division as PROGA.
       PROCEDURE DIVISION.
       MAIN-PARA.
           MOVE DFHCOMMAREA TO WS-AREA.
           IF CA-NEXT-PGM NOT = SPACES
               EXEC CICS XCTL PROGRAM(CA-NEXT-PGM) END-EXEC
           END-IF.
           EXEC CICS XCTL PROGRAM('PROGC') COMMAREA(WS-AREA) END-EXEC.

       IDENTIFICATION DIVISION.
       PROGRAM-ID. PROGC.
      *    Same data division as PROGA.
       PROCEDURE DIVISION.
       MAIN-PARA.
           MOVE DFHCOMMAREA TO WS-AREA.
           IF CA-NEXT-PGM NOT = SPACES
               EXEC CICS XCTL PROGRAM(CA-NEXT-PGM) END-EXEC
           END-IF.
           EXEC CICS XCTL PROGRAM('PROGA') COMMAREA(WS-AREA) END-EXEC.

       IDENTIFICATION DIVISION.
       PROGRAM-ID. PROGD.
       DATA DIVISION.
       WORKING-STORAGE SECTION.
       01  WS-AREA.
           05  WS-NEXT-PGM      PIC X(8).
       PROCEDURE DIVISION.
       MAIN-PARA.
           MOVE 'PROGE' TO WS-NEXT-PGM.
           EXEC CICS XCTL PROGRAM('PROGA') COMMAREA(WS-AREA) END-EXEC.

The literal transfers resolve on their own, so by the round shown here the combine knows four links: A→B, B→C, C→A and D→A. Six places matter. Each dynamic jump starts at its own node, on CA-NEXT-PGM (linkage bytes 0 to 8). Each literal transfer is a place on WS-AREA (working-storage bytes 0 to 8) at that XCTL.

Read a row like this: the bytes at B-xctl were copied from DFHCOMMAREA by the MOVE, and PROGB's commarea is handed in by PROGA's transfer, so B-xctl leads to A-xctl. The ring of places A-xctl → C-xctl → B-xctl → A-xctl runs the opposite way to the ring of transfers, because the walk goes backwards. The jump at PROGB reads CA-NEXT-PGM and the link from PROGA hands over DFHCOMMAREA: two names, the same bytes, so one place.

Step by step

The combine answers programs in name order, so PROGB's jump goes first. Two naive walks would expand 5 places each: B-jump, A-xctl, C-xctl, D-xctl, B-xctl, then C-jump, B-xctl, A-xctl, C-xctl, D-xctl. That is 10 expansions. The memo makes 6.

The path is the depth-first walk's current route; the stack is Tarjan's stack of places not yet in a finished component. A-xctl's two successors are taken C-xctl first here; the other order changes the visits, not the answers.

A third jump starting at any of these six places would expand nothing: the memo returns the stored answer straight away. Both answers are what the naive walks give: {PROGE}, and both walks would meet a place twice going round the ring.

The gap grows with the ring. A walk from inside a ring of n places expands all n; n jumps on it expand about n² between them. With the memo the ring is expanded once. On a test of a 15-program XCTL ring, vertex expansions went from 480 to 60, with identical output.

The rule

The first line is the naive walk's answer written per place. It holds for every member of a component at once, because they all reach the same places. Tarjan settles a component only after every component it leads to, so the answers the second line needs are always there.

The join has to be the walk's join, and it must not care about order or repetition: here, set unions of values, reasons and outside callers, and an "or" of the cycled flag. That is what lets a stored answer stand in for walking again.

The revisit flag. Besides values, the combine asks whether a walk from a place would reach some place twice. That is true exactly when what the place reaches is not a tree hanging from it: a tree on k places has k − 1 edges. Most places settle it when their component settles. A component of two or more places is a cycle, so every member revisits. A single place with an edge to itself, the same successor twice, or a successor that revisits, revisits. A single place with at most one successor, which does not revisit, does not. What is left is a single place with several successors that do not revisit, like the top of a diamond: their reach may overlap. That one is decided on demand by walking the successor lists the memo already keeps, counting edges against places. Nothing is expanded.

The combine reads the flag in one case only: when a jump's answer has no values and no reasons. A walk that went round a ring and found nothing is reporting that the bytes come from whoever first started the ring, so the target is marked as received from outside (inbound-linkage) rather than left empty with no explanation. In the example, without PROGD, both jumps would end that way.

What goes wrong

• The graph must not change while the memo lives. A stored answer is only right for the links it was computed with. Each round of the combine finds new links (see rounds across programs), so the cross-program memo is built per round and dropped. Inside one program the facts and copies never change, so the second memo, over positions inside a program, lives for the whole run. Keeping the cross-program memo across rounds would give stale answers.
• The memo only shares places that are equal. The same node reached under bytes 0 to 8 and under bytes 0 to 4 is two places, each expanded. Copies that move part of a field, and links whose windows line up on different lengths, narrow the range, so one node can turn into many places. Telling places apart by bytes rather than field name removed the duplicates that were only names; it does nothing for real byte-range fragmentation.
• One component can be most of the corpus. On the large corpus the links joined into one cyclic group, and one solve grew past a million places on the stack before anything settled. The memo makes each place cost once; it does not make the set of places small. Hop limits bound that. A hop limit also puts the crossing count into the place, so the same bytes reached after 1 crossing and after 2 are separate places, and the memo shares less.
• A component's answer is all-or-nothing. Every member gets the full join. That is exact for reachability, since every member does reach it all, but it means one wide entry into a ring widens every jump on the ring.
• The revisit check can still walk. For diamond-shaped starts it walks the stored successor lists. That is cheap compared to expanding, but it is not free on a large reach, and its result is cached per start.
• The memo is mutable. It is the one place in the combine that mutates state, and is excluded from the functional-style lint for that reason: threading the memo and the stack through as values would copy them at every step.

In cobble

The combine (cobble-dataflow-combine) holds two memos. The first answers jumps across programs. Each round builds one over the places it reaches: it resolves a place inside its program and follows each stop across links. A place met again on a cycle is flagged, and an empty answer so flagged becomes inbound-linkage. Links are found through an index by (callee, parameter), (caller, node, parameter) and (callee, node), not by a scan. The second memo works inside one program and lasts the whole run. Both tell places apart by their bytes alone, not by the field name that reached them.

The command and its options are in the field dataflow reference. Related pages: fixpoints, traversal orders, hop limits.