I need to find the dominance tree or a dominance of a program function

[anzosasuke]

There is a '''public static <V,​E extends GEdge<V>> GDirectedGraph<V,​GEdge<V>> API on Graph Algorithm. Is it possible to get the dominance tree in headless? it says V,E of the graph, what are these? Can a function dominance be found out by the following API, or basicblock's dominance tree?
Oh man! I'm probably not gonna get answer for this!

[dragonmacher]

You should be able to use the API you mentioned after first creating a graph of all functions, with edges connecting functions via calls (it should work in headless).

The 'V,E' represent 'vertex' and 'edge' type of your choosing. In your case, the V is a ghidra Function object. The edge can be one of our DefaultGEdges, with a V of Function.

Most of our code uses dominance based on code blocks. For an example, see the DominanceModularizationCmd:

	@Override
	protected void applyModel() throws CancelledException {
		GDirectedGraph<CodeBlockVertex, CodeBlockEdge> callGraph = createCallGraph();
		CodeBlockVertex root = createRoot(callGraph, "Dominance");

		GDirectedGraph<CodeBlockVertex, GEdge<CodeBlockVertex>> dominanceGraph =
			GraphAlgorithms.findDominanceTree(callGraph, monitor);

		rebuildProgramTree(dominanceGraph, root, destinationModule);
	}

[anzosasuke]

I did that.
graph = GraphAlgorithms.findDominanceTree(digraph, monitor)
But I got this error.

    graph = GraphAlgorithms.findDominanceTree(digraph, monitor)
	at edu.uci.ics.jung.graph.util.Pair.<init>(Pair.java:42)
	at edu.uci.ics.jung.graph.AbstractGraph.addEdge(AbstractGraph.java:60)
	at edu.uci.ics.jung.graph.AbstractGraph.addEdge(AbstractGraph.java:55)
	at ghidra.graph.jung.JungDirectedGraph.addEdge(JungDirectedGraph.java:27)
	at ghidra.graph.algo.ChkDominanceAlgorithm.getDominanceTree(ChkDominanceAlgorithm.java:236)
	at ghidra.graph.GraphAlgorithms.findDominanceTree(GraphAlgorithms.java:306)
	at java.base/jdk.internal.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
	at java.base/jdk.internal.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:62)
	at java.base/jdk.internal.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43)
	at java.base/java.lang.reflect.Method.invoke(Method.java:566)
java.lang.IllegalArgumentException: java.lang.IllegalArgumentException: Pair cannot contain null values```

[dragonmacher]

Based on that trace, it seems like there is a flaw in the algorithm. It is attempting to create an edge where at least one of the vertices for the edge is null. It looks like V dominator = getImmediateDominator(v); may return null, which this code is not checking for.

[anzosasuke]

So, Should I make some changes? how do I fix this? Is something wrong with the code?

[dragonmacher]

So, Should I make some changes? how do I fix this? Is something wrong with the code?

My guess is that the graph fed to the algorithm is created in a way that allowed this to happen. I can't say for sure without being able to debug the issue. My guess is that you added a null vertex to an edge you created in this code:

 edge = DefaultGEdge(func, fm.getFunctionAt(getAddress(target_addr)))

This fm.getFunctionAt(getAddress(target_addr)) can return null.

[anzosasuke]

So i have made basicblockmodel's Gdirected graph and fed it into the findDominanceTree() from GraphAlgorithms. But I don't know why the output is not what it should be. This is my whole code.

from ghidra.program.model.block.graph import CodeBlockEdge
from ghidra.graph import GraphAlgorithms
from ghidra.app.cmd.module import DominanceModularizationCmd
from ghidra.program.model.block import BasicBlockModel
from ghidra.graph import GraphFactory


    
digraph = GraphFactory.createDirectedGraph()

bbm = BasicBlockModel(currentProgram)
blocks = bbm.getCodeBlocks(monitor)
block = blocks.next()

while block:
	vert = CodeBlockVertex(block)
	digraph.addVertex(vert)

	block = blocks.next()
	vert_next = CodeBlockVertex(block)
	edge = CodeBlockEdge(vert, vert_next)
	digraph.addEdge(edge)
print(digraph)
dominancegraph = GraphAlgorithms.findDominanceTree(digraph, monitor)
print(graph)
from_vertex = "innocuous"
dom = GraphAlgorithms.findDominance(digraph, from_vertex ,monitor)
print(dom)

And the output I get is same with digraph and dominancegraph. To get the dominance right, what am i missing? please help me.

[dragonmacher]

You appear to no be creating the edges correctly. You are not using the destinations of the code blocks to create edges. As I referenced before, you can see an example of this in DominanceModularizationCmd in the addEdgesForDestinations() method:

private void addEdgesForDestinations(GDirectedGraph<CodeBlockVertex, CodeBlockEdge> graph,
			CodeBlockVertex fromVertex, CodeBlock sourceBlock,
			Map<CodeBlock, CodeBlockVertex> instanceMap) throws CancelledException {

		CodeBlockReferenceIterator iterator = sourceBlock.getDestinations(monitor);
		while (iterator.hasNext()) {
			monitor.checkCanceled();

			CodeBlockReference destination = iterator.next();
			CodeBlock targetBlock = getDestinationBlock(destination);
			if (targetBlock == null) {
				continue; // no block found
			}

			CodeBlockVertex targetVertex = instanceMap.get(targetBlock);
			if (targetVertex == null) {
				targetVertex = new CodeBlockVertex(targetBlock);
				instanceMap.put(targetBlock, targetVertex);
			}

			graph.addVertex(targetVertex);
			graph.addEdge(new CodeBlockEdge(fromVertex, targetVertex));
		}
	}

I suggest use use that class as a guide to setup your graph.

[anzosasuke]

Thanks. I made my graph according to above mentioned class. This is my whole script.

from ghidra.program.model.block.graph import CodeBlockVertex
from ghidra.program.model.block.graph import CodeBlockEdge
from ghidra.graph import GraphAlgorithms
from ghidra.program.model.block import BasicBlockModel
from ghidra.graph import GraphFactory
from ghidra.graph import GDirectedGraph
from ghidra.program.model.address import *
from ghidra.program.model.block import *
from ghidra.program.model.listing import *
from ghidra.program.util import GroupPath


def getDestinationBlock(destination):
	targetAddress = destination.getDestinationAddress()
	targetBlock = bbm.getFirstCodeBlockContaining(targetAddress, monitor)
	if targetBlock == None:
		return None
	blockAddress = targetBlock.getFirstStartAddress()
	return targetBlock

digraph = GraphFactory.createDirectedGraph()

bbm = BasicBlockModel(currentProgram)
blocks = bbm.getCodeBlocks(monitor)

while blocks.hasNext():

	block = blocks.next()
	fromVertex = CodeBlockVertex(block)
	digraph.addVertex(fromVertex)
	iterator = block.getDestinations(monitor)
	while (iterator.hasNext()):
		destination = iterator.next()
		print(destination)
		targetBlock = getDestinationBlock(destination)
		print(targetBlock)
		if targetBlock == None:
			continue
		targetVertex = CodeBlockVertex(targetBlock)

		digraph.addVertex(targetVertex)
		edge = CodeBlockEdge(fromVertex, targetVertex)
		digraph.addEdge(edge)

print(digraph)
graph = GraphAlgorithms.findDominanceTree(digraph, monitor)
print(graph)
from_vertex = "innocuous"
dom = GraphAlgorithms.findDominance(digraph, from_vertex ,monitor)
print(dom)

But I get the error which i got before:

	at edu.uci.ics.jung.graph.util.Pair.<init>(Pair.java:42)
	at edu.uci.ics.jung.graph.AbstractGraph.addEdge(AbstractGraph.java:60)
	at edu.uci.ics.jung.graph.AbstractGraph.addEdge(AbstractGraph.java:55)
	at ghidra.graph.jung.JungDirectedGraph.addEdge(JungDirectedGraph.java:27)
	at ghidra.graph.algo.ChkDominanceAlgorithm.getDominanceTree(ChkDominanceAlgorithm.java:236)
	at ghidra.graph.GraphAlgorithms.findDominanceTree(GraphAlgorithms.java:306)
	at java.base/jdk.internal.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
	at java.base/jdk.internal.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:62)
	at java.base/jdk.internal.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43)
	at java.base/java.lang.reflect.Method.invoke(Method.java:566)
java.lang.IllegalArgumentException: java.lang.IllegalArgumentException: Pair cannot contain null values

Is there a way to get over this problem>??

[dragonmacher]

I do not see any obvious flaw in your script. My guess is that the structure of your graph is such that you do not have a single source and/or a single sink in the graph. The algorithm will create dummy source/sink vertices as needed in this case. The algorithm appears to not handle the case where a dummy node is a dominator. I am surpised by this, as I think we would have seen this already in our code.

Unfortunately, for you to work around this issue, you will have to change our source code. You can do this if you setup a developer environment using our github repo. Alternatively, you could copy our class(es) as needed, writing them in Python, which would allow you to fix the bug. (Admittedly, this is not a nice solution.)

The fix we need is in ChkDominanceAlgorithm in this method:

	public GDirectedGraph<V, GEdge<V>> getDominanceTree() {
		GDirectedGraph<V, GEdge<V>> dg = GraphFactory.createDirectedGraph();

		// note: we use the source graph here and not the one we mutated for calculating dominance
		Collection<V> vertices = sourceGraph.getVertices();
		Set<V> sources = navigator.getSources(sourceGraph);
		for (V v : vertices) {
			if (sources.contains(v)) {
				continue;
			}

			V dominator = getImmediateDominator(v);
			if (!Objects.equals(dominator, v)) {
				dg.addEdge(new DefaultGEdge<>(dominator, v));
			}
		}
		return dg;
	}

Specifically, the code adding an edge needs to be changed to this:

	if (!Objects.equals(dominator, v) && dominator != null) {
		dg.addEdge(new DefaultGEdge<>(dominator, v));
	}

I intend to fix this, but I don't know how long it will be before you can access the updated code.

[anzosasuke]

Thanks so much. About the sources, I checked with my graph and I seem to have it(more than one).
I think I will try changing the source code and then build it to check whether it works that way. If it doesn't, ahhhhh.... lets hope it does..

[anzosasuke]

Thanks so much. I was able to get over the error after changing the source code as you suggested. The graph I made had some vertices without edges which I am not sure why. I think that's why the error was triggered. I am still trying to figure out correct way to interpret the output though.

[dragonmacher]

You're welcome. I'm sure you will be able to figure out the issue with some debugging of how you create your vertices and edges from the code blocks.

[anzosasuke]

So I got the output for dominance tree. But i am perplexed on why the dominance tree graph and the Gdirected graph looks the same and I used the API GraphAlgorithms.findDominance(digraph, fromVertex, monitor) and the output is same as fromVertex everytime. I do not think the output is correct.

fromVertex = "get_count"
 dom = GraphAlgorithms.findDominance(digraph, fromVertex, monitor)

the output will be "get_count". Which should clearly be "main".

So i tried getting dominance of the basic block in a function. output snippets looks like this all the way similar.

GdirectedGraph
Vertices:FUN_00403444,FUN_00403450
Edges:[FUN_00403444, FUN_00403450][FUN_00403444,FUN_00403450] 
Dominance Tree
Vertices:FUN_00403444,FUN_00403450
Edges:[FUN_00403444, FUN_00403450][FUN_00403444,FUN_00403450] ```

[dragonmacher]

I believe the issue is that your example is too simple. I suggest you look at the ghidra.graph.GraphAlgorithmsTest. It has many examples of finding dominance with different graph setups. As a bonus, it has some ascii depictions of the graphs.