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

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

文件已经过预处理。

出于安全原因，该代码相当“老派”，因此没有诸如函数指针之类的奇特东西，只有传递变量的函数和一些执行相同操作的函数宏。

检测递归的最自然的方法是创建一个有向调用图，将每个函数视为一个节点，其边缘指向它调用的所有其他函数。如果图有循环，那么就有递归。

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

PyCParser 很好，但它抱怨很多事情，例如未定义的变量或未定义源类型或在不同文件中定义的 typedef，这些与我的用例完全无关。该项目使用自定义依赖管理系统，因此一些包含内容会自动添加，因此我需要 PyCParser 不关心anything以外FuncCall and FuncDef节点，我认为没有办法将解析过程本身限制于此。

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

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

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

为什么不直接使用objdump在您编译的代码上然后解析生成的程序集来构建您的图？

测试1.c文件：

extern void test2();

void test1()
{
   test2();
}

测试2.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 来后处理你的反汇编并构建一个 function=>calls 的字典：

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分析技术也用于呼叫捕捉器 http://www.skynet.ie/~caolan/Packages/callcatcher.html检测未使用的 C 函数（这里也可以通过检查不在任何集合中的键以及对编译器符号进行一些过滤来轻松完成）