XCSG Compendium — Control Flow

Find the index for the Compendium here.

In this article, we will cover the parts of the XCSG schema related to Control Flow.

• XCSG.ControlFlow_Node: A node representing an executable statement in a code. Atlas chooses to represent individual statements as nodes instead of a basic block as a node providing finer granularity for Control Flow analysis.
• XCSG.ControlFlow_Edge: An edge representing the successor relation as defined by Frances Allen. It connects two XCSG.ControlFlow_Nodes a->b where b is executed after a on some execution behavior.
• XCSG.controlFlowRoot: An XCSG.ControlFlow_Node that represents the first statement executed within a function. Every function possesses a unique XCSG.controlFlowRoot node.
• XCSG.controlFlowExit: An XCSG.ControlFlow_Node that represents one of the return statements within a function.

Query example:
var cfg = <function>.contained().nodes(XCSG.ControlFlow_Node).induce(universe.edges(XCSG.ControlFlow_Edge))
This query computes the Control Flow Graph (CFG) for the function <function> .

Let’s look at tags and attributes for conditional statements.

• XCSG.ControlFlowCondition: A XCSG.ControlFlow_Node node representing a conditional statement.
• XCSG.ControlFlowIfCondition: A XCSG.ControlFlowCondition node representing an IF statement.
• XCSG.ControlFlowSwitchCondition: A XCSG.ControlFlowCondition node representing a Switch statement.
• XCSG.conditionValue: An attribute possessed by an XCSG.ControlFlow_Edge that represents an outgoing edge of a XCSG.ControlFlowCondition node. As the name suggests, it represents the value of the condition captured by the XCSG.ControlFlowCondition node for which that particular edge is taken at runtime. For outgoing edges from an IF statement it is either true or false For a switch statement it represents the case value of the statement represented by the head of the outgoing edge.

Query examples:
var num_conditions = <cfg>.nodes(XCSG.ControlFlowCondition).eval().nodes().size()
- This query counts the number of conditional statements in a given cfg. XCSG.ControlFlowCondition can be replaced with XCSG.ControlFlowIfCondition or XCSG.ControlFlowSwitchCondition to count only IF or Switch statements.
var trueEdges = <condition>.out().selectEdge(XCSG.conditionValue,"true")
- This query returns a set of edges that represent only the ‘true’ edges for a given <condition>. This set can then be used to simulate only a particular execution path (corresponding to the condition being true) and can be utilized to write a path-sensitive analyzer depending upon your use case.

Let’s look at Loop related tags.

• XCSG.Loop: A XCSG.ControlFlow_Node node representing a loop header. If the loop is a while loop or for loop, then it is also an XCSG.ControlFlowCondition node.
• XCSG.DoWhileLoop: A XCSG.Loop node that represents a do-while loop. The while statement is tagged as XCSG.ControlFlowCondition.
• XCSG.LoopChild: An edge a->b between an XCSG.Loop node and an XCSG.ControlFlow_Node where b is part of the loop body of a. If b is also a XCSG.Loop node then this edge captures the loop nesting relation.

Query example:
var nested_loops = <cfg>.nodes(XCSG.Loop).induce(universe.edges(XCSG.LoopChild))
This query returns a subgraph that captures the nesting structure of loops within a given <cfg>.

Let’s look at special kinds of Control Flow statements

• XCSG.GotoStatement: An XCSG.ControlFlow_Node that represents a Goto statement.
• XCSG.Break: An XCSG.ControlFlow_Node that represents a break statement.
• XCSG.Continue: An XCSG.ControlFlow_Node that represents a continue statement.

Query example:
var num_gotos = universe.nodes(XCSG.GotoStatement).eval().nodes().size()
— This query counts the number of goto statements in the entire codebase indexed. If you want to restrict the count to a particular file or a function, then replace universe with a node representing that file or function.

This concludes a brief overview of Control Flow related concepts in XCSG schema.