llvm dev - Mar 2017 - Functions accessible from a function

Hello everybody,

I am trying to do some static analysis, e.g. find which other functions
accessible from a function.
Current naive implementation goes over each instruction and whether it is a call
site or not.
It works great so far, but there are some cases where it doesn’t work. For
example:

  declare no_source(function: f) // uses f internally
  define foo() { ... }
  define bar() { ... }

  define buzz() {
    call foo()
    call no_source(&bar)
    ret
  }

In this case, my implementation catches 'foo' but not 'bar.'
There are must be less trivial but also detectable cases.

Can anybody give a hint or advice on how to do such kind of analysis?

Cheers,
Alex.
-- 
AlexDenisov
Software Engineer, https://lowlevelbits.org

A simple solution is to analyze the argument list of function no_source, if
an argument is a function pointer(assume the function type is fTy), draw
control dependence edges from this working callInst to all the candidate
callee functions with the same function type fTy, some approximations are
required here, since you are doing type-based analysis, this approximation
is unavoidable.

On Tue, Mar 21, 2017 at 2:21 AM, Alex Denisov via llvm-dev <
llvm-dev at lists.llvm.org> wrote:
> Hello everybody,
>
> I am trying to do some static analysis, e.g. find which other functions
> accessible from a function.
> Current naive implementation goes over each instruction and whether it is
> a call site or not.
> It works great so far, but there are some cases where it doesn’t work. For
> example:
>
>   declare no_source(function: f) // uses f internally
>   define foo() { ... }
>   define bar() { ... }
>
>   define buzz() {
>     call foo()
>     call no_source(&bar)
>     ret
>   }
>
> In this case, my implementation catches 'foo' but not
'bar.'
> There are must be less trivial but also detectable cases.
>
> Can anybody give a hint or advice on how to do such kind of analysis?
>
> Cheers,
> Alex.
> --
> AlexDenisov
> Software Engineer, https://lowlevelbits.org
>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170321/c13322b5/attachment.html>

On 3/21/17 1:21 AM, Alex Denisov via llvm-dev wrote:
> Hello everybody,
>
> I am trying to do some static analysis, e.g. find which other functions
accessible from a function.
In other words, you're trying to compute the call graph (a graph that 
shows which functions call other functions), correct?

> Current naive implementation goes over each instruction and whether it is a
call site or not.
> It works great so far, but there are some cases where it doesn’t work. For
example:
>
>    declare no_source(function: f) // uses f internally
>    define foo() { ... }
>    define bar() { ... }
>
>    define buzz() {
>      call foo()
>      call no_source(&bar)
>      ret
>    }
>
> In this case, my implementation catches 'foo' but not
'bar.'
> There are must be less trivial but also detectable cases.
>
> Can anybody give a hint or advice on how to do such kind of analysis?
LLVM already has a call graph analysis pass 
(http://llvm.org/doxygen/classllvm_1_1CallGraphAnalysis.html) which can 
compute a call graph for you.

In your example above, a function escapes to external code.  The call 
graph has an externalCalledNode and an externalCallNode which represents 
functions called by external code and functions calling external code, 
respectively.  You should examine these nodes to understand how external 
code affects the call graph.

The call graph analysis within LLVM does not really handle function 
pointers (the results are correct but a very conservative).  If you need 
to analyze function pointers, you might try DSA.

Regards,

John Criswell
>
> Cheers,
> Alex.

-- 
John Criswell
Assistant Professor
Department of Computer Science, University of Rochester
http://www.cs.rochester.edu/u/criswell

> In other words, you're trying to compute the call graph (a graph that
shows which functions call other functions), correct?
I called it Call Tree in my head, but yes, this is exactly what I need.
> LLVM already has a call graph analysis pass
(http://llvm.org/doxygen/classllvm_1_1CallGraphAnalysis.html) which can compute
a call graph for you.
> 
> In your example above, a function escapes to external code.  The call graph
has an externalCalledNode and an externalCallNode which represents functions
called by external code and functions calling external code, respectively.  You
should examine these nodes to understand how external code affects the call
graph.
> 
> The call graph analysis within LLVM does not really handle function
pointers (the results are correct but a very conservative).  If you need to
analyze function pointers, you might try DSA.
Thanks a lot, I will look into. If the algorithm doesn’t cover all cases then it
is still better than my naive approach.
Could you also tell what’s the DSA is? The most relevant finding I see is the
“data structure analysis”.
> On 21 Mar 2017, at 22:05, John Criswell <jtcriswel at gmail.com>
wrote:
> 
> On 3/21/17 1:21 AM, Alex Denisov via llvm-dev wrote:
>> Hello everybody,
>> 
>> I am trying to do some static analysis, e.g. find which other functions
accessible from a function.
> 
> In other words, you're trying to compute the call graph (a graph that
shows which functions call other functions), correct?
> 
> 
>> Current naive implementation goes over each instruction and whether it
is a call site or not.
>> It works great so far, but there are some cases where it doesn’t work.
For example:
>> 
>>   declare no_source(function: f) // uses f internally
>>   define foo() { ... }
>>   define bar() { ... }
>> 
>>   define buzz() {
>>     call foo()
>>     call no_source(&bar)
>>     ret
>>   }
>> 
>> In this case, my implementation catches 'foo' but not
'bar.'
>> There are must be less trivial but also detectable cases.
>> 
>> Can anybody give a hint or advice on how to do such kind of analysis?
> 
> LLVM already has a call graph analysis pass
(http://llvm.org/doxygen/classllvm_1_1CallGraphAnalysis.html) which can compute
a call graph for you.
> 
> In your example above, a function escapes to external code.  The call graph
has an externalCalledNode and an externalCallNode which represents functions
called by external code and functions calling external code, respectively.  You
should examine these nodes to understand how external code affects the call
graph.
> 
> The call graph analysis within LLVM does not really handle function
pointers (the results are correct but a very conservative).  If you need to
analyze function pointers, you might try DSA.
> 
> Regards,
> 
> John Criswell
> 
>> 
>> Cheers,
>> Alex.
> 
> 
> -- 
> John Criswell
> Assistant Professor
> Department of Computer Science, University of Rochester
> http://www.cs.rochester.edu/u/criswell