Re: [sarif] Let's talk about nested graphs

[Luke Cartey <luke@semmle.com>]

Hi Larry,

Apologies for not getting back to you sooner on this.

I think nested graphs serve a different potential purpose to nested traversals. Typically, I would consider nested graphs representing a logical or physical hierarchy, rather than a call graph hierarchy or similar. Nested graphs can help describe static structure, whereas I think nested traversals are better at describing or hiding dynamic structure.

After looking in detail at our current graph support (including nested traversals), and looking at the use cases I had in mind, I believe nested graph support is only useful if:

 1. We intend to display the results as a graph (example below); and
 2. We (re-)introduce explicit cross-graph edges.

To explain the use case I had in mind, assume that we re-instated some mechanism for cross-graph dependencies as well as some mechanism for nested graphs. Taking the example you gave, lets also assume function_a and function_b are declared in the same file. We could create a new graph to represent the file itself, and nest the two function graphs underneath it. i.e the hypothetical SARIF would be:

{                 # A result object

  "graphs": [

    {

      "id": "file_a",

      "nodes": [

        {

          "id": "function_a",

          "nestedGraphId": "function_a"  

        },

        {

          "id": "function_b",

          "nestedGraphId": "function_b"

        }

      ],

    },

    {

      "id": "function_a",

      "nodes": [

        {

          "id": "a1",

        },

        {

          "id": "a2",

        },

        {

          "id": "a3"

        }

      ],

      "edges": [

        ...
        {

          "id": "e1",

          "sourceNodeId" : "a2",
          "targetNodeId" : "b1",
          "targetGraphId" : "function_b"

        }

      ]

    },

 

    {

      "id": "function_b",

      "nodes": [

        {

          "id": "b1"

        },

      "edges": [

        ...
        {

          "id": "e1",

          "sourceNodeId" : "b1",
          "targetNodeId" : "a3",
          "targetGraphId" : "function_a"

        }

      ]

      ]

    }

  ],

  ...

}

This could be rendered in graph form like this: 

The edges that are part of a particular traversal could be highlighted in the graph.

A smart viewer could also allow the nested graphs to be collapsed, computing edges inherited from the nested graphs, i.e like this:

To explain my earlier provisos:

 - if viewers are only showing the graph traversal as a flat list of visited nodes, or some sort of path-tree with nested traversals, I don't think nested graphs provide any extra value, because there is no obvious way to include the nested graph information.

 - if there are no cross-graph edges, it's also unclear how the nesting provides any extra value.

Cheers,

Luke

On Tue, Apr 24, 2018 at 1:39 PM Larry Golding (Comcast) <larrygolding@comcast.net> wrote:

Luke, any thoughts on this?

 

From: sarif@lists.oasis-open.org <sarif@lists.oasis-open.org> On Behalf Of Larry Golding (Comcast)
Sent: Thursday, April 19, 2018 2:49 PM
To: Luke Cartey <luke@semmle.com>; sarif@lists.oasis-open.org
Subject: [sarif] Let's talk about nested graphs

 

I’m curious how nested graphs are used. Here’s what I mean:

 

You saw the proposal for “nested traversals”. If an edge has a nestedGraphTraversalId property, then when the user is about to traverse that edge, the viewer can offer them the choice of diving into or stepping over the nested traversal. (A debugger-like F10/F11 experience would be nice.) And since a traversal is single-entry, single-exit, there’s no ambiguity about how to navigate through the nested traversal.

 

Now let’s do something similar for graphs: insides one of the nodes of the graph for function_a, we nest a reference to the graph for function_b (see below).

 

My question is, who consumes this information? What do they do with it? Is this the right representation for these consumers-who-I-don’t-yet-know-anything-about? Or do they need something different, or richer?

 

My point is that, from the point of view of an end user experience, I have a very concrete understanding of why nested traversals are helpful, and I have no understanding of how nested graphs are helpful.

 

Thanks,

Larry

 

{                 # A result object

  "graphs": [

    {

      "id": "function_a",

      "nodes": [

        {

          "id": "a1",

        },

        {

          "id": "a2",

          "nestedGraphId": "function_b"

        },

        {

          "id": "a3"

        }

      ],

      "edges": [

        ...

      ]

    },

 

    {

      "id": "function_b",

      "nodes": [

        {

          "id": "b1"

        },

        ...

      ]

    }

  ],

  ...

}