python - 使用 Python 检测 C 文件中的递归

Question

我需要在相当大的 (5-15,000) 组 C(不是 C++)文件中检测直接和间接递归。

文件已经过预处理。

出于安全原因，该代码非常“老派”，因此其中没有函数指针等花哨的东西，只有传递变量的函数和一些做同样事情的函数宏。

检测递归最自然的方法是制作一个有向调用图，将每个函数视为一个节点，其边连接到它调用的所有其他函数。如果图有任何循环，则我们有递归。

查找函数调用的正则表达式很简单，但我还需要知道调用的是哪个函数。

PyCParser 很好，但它会提示很多事情，例如 undefined variable 或未定义源类型或在不同文件中定义的 typedef，这与我的用例完全无关。该项目使用自定义依赖管理系统，因此一些包含和此类自动添加，所以我需要 PyCParser 不关心 任何东西 除了 FuncCall 和 FuncDef 节点，我认为没有办法将解析过程本身限制到此。

我宁愿不实现解析器，因为我没有时间去学习如何在 python 中执行此操作，然后再实现解决方案。

回到问题，我将如何解析C文件中的函数？基本上得到一个以字符串(文件中定义的函数名称)作为键，以字符串列表(每个函数调用的函数)作为值的字典？正则表达式似乎是最自然的解决方案。

遗憾的是，使用 python 不是可选的。

Answer 1

为什么不对编译后的代码使用 objdump，然后解析生成的程序集来构建图表？

test1.c 文件:

extern void test2();

void test1()
{
   test2();
}

test2.c 文件:

extern void test1();

void test2()
{
   test1();
}


int main()
{
   test2();
}

现在构建它:

gcc -g test1.c test2.c -o myprog

现在拆解

objdump -d myprog > myprog.asm

使用几个简单的正则表达式查找所有函数调用，同时记住您所在的上下文。反汇编示例向您展示了它应该是多么容易:

00401630 <_test1>:
  401630:   55                      push   %ebp
  401631:   89 e5                   mov    %esp,%ebp
  401633:   83 ec 08                sub    $0x8,%esp
  401636:   e8 05 00 00 00          call   401640 <_test2>
  40163b:   c9                      leave  
  40163c:   c3                      ret    
  40163d:   90                      nop
  40163e:   90                      nop
  40163f:   90                      nop

00401640 <_test2>:
  401640:   55                      push   %ebp
  401641:   89 e5                   mov    %esp,%ebp
  401643:   83 ec 08                sub    $0x8,%esp
  401646:   e8 e5 ff ff ff          call   401630 <_test1>
  40164b:   c9                      leave  
  40164c:   c3                      ret    

然后使用 python 对反汇编进行后处理并构建一个函数=>调用字典:

import re
import collections

calldict = collections.defaultdict(set)

callre = re.compile(".*\scall\s+.*<(.*)>")
funcre = re.compile("[0-9a-f]+\s<(.*)>:")

current_function = ""

with open("myprog.asm") as f:
    for l in f:
        m = funcre.match(l)
        if m:
            current_function = m.group(1)
        else:
            m = callre.search(l)
            if m:
                called = m.group(1)
                calldict[current_function].add(called)

我没有编写完整的图搜索，但您可以使用如下简单代码检测“乒乓”递归:

for function,called_set in calldict.items():
    for called in called_set:
        callset = calldict.get(called)
        if callset and function in callset:
            print(function,called)

这给了我:

_test2 _test1
_test1 _test2

此符号/asm 分析技术也用于 callcatcher检测未使用的 C 函数(这也可以通过检查不在任何集合中的键以及对编译器符号的一些过滤来非常容易地完成)