Lightweight Structured Visualization of Assembler Control-Flow based on Regular Expressions

Control Flow Graphs (CFG) constitute a program visualization technique commonly used when analyzing the possible flow of control between the basic blocks of a program during its execution. As such, many software analysis tools offer a feature for the automatic generation of control flow graphs for given program code.

For large program functions, however, the resulting control flow graphs do become rather huge, sometimes to the extent that they do not fit on the computer screen. The viewer needs to scroll left or right, up or down to display the portion of the control flow graph of interest. This makes it difficult to keep track of the flow of control, especially while reading the code details. Thus, control flow graphs can be impractical to use.

We propose an alternative control flow visualization, called Control Flow Blocks(CFB). The basic idea behind it is to use the property of containment instead of linkage to visualize the flow of control between the basic blocks of a program: The visualization is basically a folded control flow graph, in which all possible sequences of basic blocks composing an execution path are mapped to one dimension. Meanwhile, the control flow is abstracted to explicit control flow structures like choice, loop and optional execution, which are represented by box-like constructs enclosing the basic blocks that they apply to in the resulting overlay of execution paths.

This control flow visualization is based on Regular Expressions (RE): Describing the set of all possible execution paths within a control flow graph by means of a regular expression over its basic blocks yields a one-dimensional representation. As for the information about the control flow between the basic blocks, it is embodied in the regular expression operators for concatenation, alternation and quantification; they stand for sequence, choice and iteration in the execution respectively. These operators correspond to the box-like constructs, which they are mapped to once the regular expression is derived in order to create the control flow visualization.

The resulting visualization makes it possible for the viewer to display and examine an execution path of interest, while hiding all other information that are not of focal interest. Moreover, fitting the height of the visualization to the screen space limits the scrolling necessary to see other portions of a currently displayed execution path to one direction only, making it as a whole easier navigatable compared to a control flow graph.