查找函数输出的输入依赖关系
Finding the input dependencies of a functions outputs
我一直在使用 pycparser 开发一个 python 程序,它应该生成一个 JSON 文件,其中包含给定函数及其输出的依赖项。
对于示例函数:
int Test(int testInput)
{
int b = testInput;
return b;
}
这里我希望 b 依赖于 testInput。但是当然,如果使用结构和 if 语句等,它会变得更加复杂。我正在测试的文件也具有特定形式的函数,这些函数被视为输入和输出,如:
int Test(int testInput)
{
int anotherInput = DatabaseRead(VariableInDatabase);
int b = testInput;
int c;
c = anotherInput + 1;
DatabaseWrite(c);
return b;
}
这里 c 会依赖于 VariableInDatabase,和 b 一样。
我已经 运行 在 pycparser 中进行了这种分析,因为大多数结构和指针对我来说真的很难处理,而且似乎有更好的方法。我已经阅读了 ASTs 和 CFGs,以及其他分析工具,如 Frama-C,但我似乎无法找到一个明确的答案,即使这是一件事。
是否有已知的方法来进行这种分析,如果有,我应该研究什么?
它应该有数千个文件,并且能够将这些依赖项输出到 JSON,因此编辑器插件似乎不是我要找的东西。
您需要对代码进行数据流分析,然后您希望跟踪数据流从结果到源的反向流动,直到某个停止点(在您的情况下,您在函数参数处停止,但您可能也想在任何全局变量处停止)。
这在文献中叫做program slicing。
计算数据流非常困难,尤其是如果您使用复杂的语言(C 很有趣:您可以让数据流通过间接调用的读取值的函数;现在您需要间接指向分析来支持您的数据流,反之亦然)。
这是一个有趣的例子:
// ocean of functions:
...
int a(){ return b; }
...
int p(){ return q; }
...
void foo( int()* x )
{ return (*x)(); }
foo 是否依赖于 b?在q?除非你知道,否则你无法知道
foo 调用 a 或 b。但是 foo 被赋予了一个函数指针......并且
这可能指向什么?
仅使用 AST 和 CFG 是必要的,但还不够;数据流分析算法很难,特别是如果你有规模(正如你建议的那样);你需要很多机器来做这个不容易建造
[我们已经在 1600 万行的 C 程序上完成了这项工作]。请参阅我关于 Life After Parsing.
的文章
我一直在使用 pycparser 开发一个 python 程序,它应该生成一个 JSON 文件,其中包含给定函数及其输出的依赖项。 对于示例函数:
int Test(int testInput)
{
int b = testInput;
return b;
}
这里我希望 b 依赖于 testInput。但是当然,如果使用结构和 if 语句等,它会变得更加复杂。我正在测试的文件也具有特定形式的函数,这些函数被视为输入和输出,如:
int Test(int testInput)
{
int anotherInput = DatabaseRead(VariableInDatabase);
int b = testInput;
int c;
c = anotherInput + 1;
DatabaseWrite(c);
return b;
}
这里 c 会依赖于 VariableInDatabase,和 b 一样。 我已经 运行 在 pycparser 中进行了这种分析,因为大多数结构和指针对我来说真的很难处理,而且似乎有更好的方法。我已经阅读了 ASTs 和 CFGs,以及其他分析工具,如 Frama-C,但我似乎无法找到一个明确的答案,即使这是一件事。
是否有已知的方法来进行这种分析,如果有,我应该研究什么? 它应该有数千个文件,并且能够将这些依赖项输出到 JSON,因此编辑器插件似乎不是我要找的东西。
您需要对代码进行数据流分析,然后您希望跟踪数据流从结果到源的反向流动,直到某个停止点(在您的情况下,您在函数参数处停止,但您可能也想在任何全局变量处停止)。
这在文献中叫做program slicing。
计算数据流非常困难,尤其是如果您使用复杂的语言(C 很有趣:您可以让数据流通过间接调用的读取值的函数;现在您需要间接指向分析来支持您的数据流,反之亦然)。
这是一个有趣的例子:
// ocean of functions:
...
int a(){ return b; }
...
int p(){ return q; }
...
void foo( int()* x )
{ return (*x)(); }
foo 是否依赖于 b?在q?除非你知道,否则你无法知道 foo 调用 a 或 b。但是 foo 被赋予了一个函数指针......并且 这可能指向什么?
仅使用 AST 和 CFG 是必要的,但还不够;数据流分析算法很难,特别是如果你有规模(正如你建议的那样);你需要很多机器来做这个不容易建造 [我们已经在 1600 万行的 C 程序上完成了这项工作]。请参阅我关于 Life After Parsing.
的文章