Is there a way to get path analysis for custom nodes and edges?

[ivan-gavran]

I am trying to understand how to define my own nodes and edges predicate to run the flow analysis.

I found this part of the documentation suggesting that it is possible. Is it only possible for DataFlow::PathNode? I was not able to use DataFlow::PathNode because of a circular dependency in my definition of edges, so I had to use DataFlow::Node.

When doing so, and defining query predicate nodes and query predicate edges, I get under edges and nodes everything that I needed to. However, the select ... where .hasFlow(source, sink) does not resemble that graph structure.

What am I misunderstanding here?

Adding my whole query below:

/**
 * @name experiment
 * @description experiment
 * @kind path-problem
 */

import go
import semmle.go.dataflow.DataFlow

// the class that I am using for defining edges relation
class ExtendedCallNode extends DataFlow::CallNode, DataFlow::Node  {
  ExtendedCallNode() {
    this instanceof DataFlow::CallNode
  }
 
  DataFlow::CallNode getParentCallNode (){
    exists(
      Function f |
      this.getTarget() = f
      and
      result = this.asExpr().getEnclosingFunction().getACall()
    )
  }
}


class MyDataFlowConfiguration extends DataFlow::Configuration {
  MyDataFlowConfiguration() { this = "MyDataFlowConfiguration" }

  override predicate isSource(DataFlow::Node source) {
      source instanceof ExtendedCallNode
      and 
      source.asExpr().(CallExpr).getTarget().mustPanic()
  }

  override predicate isSink(DataFlow::Node sink) {       
      sink instanceof ExtendedCallNode
  }
}

query predicate edges(DataFlow::Node a, DataFlow::Node b) {
  a instanceof ExtendedCallNode
  and 
  b instanceof ExtendedCallNode
  and
  a.(ExtendedCallNode).getParentCallNode() = b
}


query predicate nodes(DataFlow::Node a){
  a instanceof ExtendedCallNode
}

from MyDataFlowConfiguration cfg, DataFlow::Node source, DataFlow::Node sink
where cfg.hasFlow(source, sink)
select source, source, sink, "path flow"

[hmakholm]

If you're rolling your own analysis from scratch, and not looking to reuse any of the existing dataflow infrastructure, then you don't need to use any particular type for your nodes, as long as the types of your nodes and edges predicates match the second and third columns of the select result. For the best result display, your node type should have a getLocation() member predicate.

Thus, the type could be just your own ExtendedCallNode type.

But the real problem you're facing is probably the "alert interpretation" computation that runs after the raw QL evaluation. It expects that the source and sink columns of your select output are actually the ends of a path in the graph defined by your edges predicate. If it isn't, the results displayed in Code Scanning might be weird or missing.

It is probably not the case that the nodes that match the cfg.hasFlow(source, sink) condition in your select are also nodes where the sink happens to be an ancestor according to your edges predicate. At least that is not to be expected, since the implementation of Configuration::hasFlow deep inside the Go library doesn't know you've defined your own edges predicate to output from your query.

If you build your own graph by defining your own edges output, you also need to do your own computation of which paths through that graph you want to output alerts from.

In this case it looks like what you'd really like to say would be something like

from MyFlowConfiguration cfg, ExtendedCallNode source, ExtendedCallNode sink
where edges*(source, sink) and cfg.isSource(source) and cfg.isSink(sink)
select source, source, sink, "path flow"

Something like that is what the hasFlow predicate does internally, except it uses its own internal edge relation and does the reachability in a more involved way than edges*(...) that gives better performance on large databases (but is intimately tied to properties of that internal edge relation).

You could even use CallExpr in place of your ExtendedCallNode class; it doesn't look like you're really using any of the functionality you get from inheriting from DataFlow::CallNode. (But then again, I suppose perhaps your example is minimized from something that does use the dataflow machinery).

[ivan-gavran]

Thanks for the answer, @hmakholm !
My main confusion was that I thought predicates edges and nodes to be incorporated by hasFlow. What you described is actually much more straightforward and makes more sense, don't know why I assumed magic where none was necessary :)

[intrigus-lgtm]

Do you want to visualize the control flow graph and find all paths from a given source method to a target method?

If so, you can port my answer for Java to Go:
#5353 (comment)
(Also look at the additional comments from @Marcono1234)
Or you could have a look at this answer for C++:
#10109 (comment)

Hope this helps.
If you need any help with porting the code to Go, let me know :)

[ivan-gavran]

Thanks for the answer, @intrigus-lgtm , it definitely helps!

When porting the answer to Go, the main problem I faced was that there was no the elegant calls predicate in Go (which you use at query predicate edges(Method a, Method b) { a.calls(b) })

Instead, I worked directly with CallNodes and defined a function

DataFlow::CallNode getChildCallNode(){    
    this.getACallee() = result.getRoot()
  }

Is there any potential problem in such definition?
Do you see a way to work on Methods or Functions and capture that same caller/callee relation in Go?

[ivan-gavran]

I would also be curious, if you know, why is a very similar getACaller method (here) private in Go?

[owen-mc]

I am on the codeql-go team at GitHub. I don't think there's a particular reason that that predicate is private. But it is in the customizations for a particular query, so it would only be evaluated if that particular query is being run. You are free to define the same predicate in your own code.