OASIS Mailing List ArchivesView the OASIS mailing list archive below
or browse/search using MarkMail.

sarif message

[Date Prev] | [Thread Prev] | [Thread Next] | [Date Next] -- [Date Index] | [Thread Index] | [List Home]

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

• From: Luke Cartey <luke@semmle.com>
• To: "Larry Golding (Comcast)" <larrygolding@comcast.net>
• Date: Wed, 02 May 2018 03:26:16 +0000

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"

},

...

]

}

],

...

}

[Date Prev] | [Thread Prev] | [Thread Next] | [Date Next] -- [Date Index] | [Thread Index] | [List Home]