RE: [sarif] The "nested edge traversal" design

[Michael Fanning <Michael.Fanning@microsoft.com>]

My question about this it to wonder why we need to inline the nested traversal here.  i.e., why isn’t nestedGraphTraversal an id that points to another edgeTraversal (which provides the isolated detail). The model below would potentially require edge traversals to duplicate information which, is nested because it is potentially copious and non-essential.

 

{

  "edgeId": "ea2",

 

  "nestedGraphTraversal": {

    "graphId": "FunctionB",

    "edgeTraversals": [

      { "edgeId": "eb1"},

      { "edgeId": "eb2"},

      { "edgeId": "eb3"},

      { "edgeId": "eb6"}

   ]

  }

}

 

 

From: sarif@lists.oasis-open.org <sarif@lists.oasis-open.org> On Behalf Of Larry Golding (Comcast)
Sent: Wednesday, April 4, 2018 12:17 PM
To: sarif@lists.oasis-open.org
Subject: [sarif] The "nested edge traversal" design
Importance: High

 

Here’s a design for nested graphs that uses “nested edge traversals.” It’s one of three possible nested graph designs we’ve considered so far. I wanted to show it because Michael asked for more information about it this morning.

 

Suppose we have a graph of code locations in function A:

 

na1 --ea1--> na2 --ea2--> na3 --ea3--> na4

 

Here, na1 is a node and --ea1--> is an edge. Node na1 is the function entry point, node na3 represents a call to function B, and node na4 is the function exit point.

 

Suppose we also have a graph of function B:

 

nb1 --eb1--> nb2 --eb2--> nb3 –-eb4--> nb4 -–eb5--> nb5 –-eb6--> nb6

                           |                         ^

                           |                         |

                           >-----------eb3------------

 

Node nb3 represents a branch such as an if statement.

 

Now for the traversals. Remember: in the current design an “edge traversal” specifies an edge id, and an edge in turn specifies a source node id and a target node id, for example:

 

{                           # An edgeTraversal object

 "edgeId": "ea2"

  ...                       # other properties

}

 

{                           # An edge object

  "id": "ea2",

  "sourceNodeId": "na2",

  "targetNodeId": "na3"

}

 

A top-level graph traversal of function A would look like this:

 

{                           # A graphTraversal object

  "graphId": "FunctionA",

 

  "edgeTraversals": [

    { "edgeId": "ea1"},

    { "edgeId": "ea2"},

    { "edgeId": "ea3"}

  ]

}

 

Suppose you’ve used your SARIF viewer to traverse edges ea1 and ea2, you’re sitting on node na3 (the function call), and you want to dive in and see the path through function B before you continue on to traverse edge ea3.

 

To support this, we add a new property nestedGraphTraversal to the edgeTraversal object. One possible traversal of function B is [ eb1, eb2, eb3, eb6 ]. The JSON representation of edge ea2 becomes:

 

{

  "edgeId": "ea2",

 

  "nestedGraphTraversal": {

    "graphId": "FunctionB",

    "edgeTraversals": [

      { "edgeId": "eb1"},

      { "edgeId": "eb2"},

      { "edgeId": "eb3"},

      { "edgeId": "eb6"}

   ]

  }

}

 

The presence of edgeTraversal.nestedGraphTraversal allows the SARIF viewer to provide a visual cue telling the user that before she proceeds to the next edge traversal (ea3), she can first traverse the nested traversal. The nested traversal starts at the source node of its first edge traversal (nb1) and ends at the target node of its last edge traversal (nb6).

 

If the user decided to dive in, her full path through the graph would be:

 

[ ea1, ea2, eb1, eb2, eb3, eb6, ea3 ]

 

As a result, she would visit the following nodes, in this order:

 

[ na1, na2, na3*, nb1, nb2, nb3, nb5, nb6, na4 ]

 

* Remember, node na3 is the site of the function call.

 

Larry