Finding a path of calls between two functions in C++

[dalao1337]

Hi,

I am pretty new to codeql and logic programming in general. I am trying to come up with a query that can find the path (list of calls) between to functions. So essentially the query answers two questions:

1. Does Function A reach Function B ?
2. If 1. is true, what is the sequence of calls from A to B (for example A calls D which calls E ... which calls B).

In my current solution I am trying to accomplish this through recursion but it's a bit of a hassle to be honest and I have a feeling there might be some built in solution for this already ? I tried looking at Global Data flow and such but it seems like that might not be applicable to this problem ? Since the only thing I am trying to get is if A reaches B and how, without caring about the parameters.

[MathiasVP]

Hi @dalao1337,

You can use something like what I wrote in this issue:

/**
 * @kind path-problem
 */
import cpp
import semmle.code.cpp.ir.dataflow.ResolveCall

// `edges(a, b)` holds whenever there's a call inside function `a` that may target function `b`.
query predicate edges(Function a, Function b) {
  // resolve any calls inside the `a` function.
  resolveCall(any(Call call | call.getEnclosingFunction() = a)) = b
}

// This predicate holds if there's a path of calls from `start` to `end`, where the name of `start` is `startName` and the name of `end` is `endName`.
predicate getCallGraph(Function start, Function end, string startName, string endName) {
  edges+(start, end) and
  start.hasName(startName) and
  end.hasName(endName)
}

from Function start, Function end
where getCallGraph(start, end, "main", end.getName()) // `end` are all the functions reachable from `main`.
select end, start, end, "A sequence that starts at 'main' and ends at " + end.getName()

This will render a graph due to the @kind path-problem in the top of the query. See more info about such metadata here.

I hope that helps!

[dalao1337]

Hi @MathiasVP thanks for help! However I just tried this query and it didn't seem to work for me... It is returning no results, what I have tried is changing the line

where getCallGraph(start, end, "main", end.getName())

with

where getCallGraph(start, end, "function_a", "function_b")

and I am not getting any results although function_a calls function_b. I picked these two functions as a test and function_b is actually called directly by function_a (depth of 0)

[dalao1337]

Just to clarify what I am trying to accomplish, if we take a look at the sample program below:

void func_b(){
    func_c();
}

void func_a(){
    func_b();
}

void func_c(){
    func_d();
}

void func_d(){
}

int main(){
    func_a();
    return 0;
}

I would like to have a query that can give me the path between main() and func_d() so essentially, main() -> func_a() -> func_b() -> func_c() -> func_d(). Currently, starting from function func_d() I am able to back-track all the way to main() by using a recursive predicate that uses getACallToThisFunction() and getEnclosingFunction(). Although this is capable of asserting whether function_d() is reachable from main(), that's all that it does and I don't have a way to "log" the paths if that makes sense.

[dalao1337]

Actually it seems like all I was looking for is this here.
The issue that remains though is that I don't have anything in the alerts tab although the "#select" tab has results indicating the query did find a path. I am not sure if this is related to the fact that I copied the ql database from another machine or not...

[hussien89aa]

Something like this should work

 predicate hasPath(Function srcF, Function desF) {
    exists( Function fc |  srcF.calls*(fc)  and fc = desF)
 }
 from Function srcF, Function desF
 where 
 srcF.getQualifiedName() = "main" and
 desF. getQualifiedName() = "func_d" and 
 hasPath( srcF,   desF)
 select srcF,desF