[cfe-dev] Path explosion Problem

[章磊]

Hi clang,

While testing the UncheckedReturn Checker, i got a path explosion problem
while clang static-analyzer analyze a giant function that has a huge mounts
of paths.

For example the function BZ2_decompress in "bzip2.c". The source code of
"bzip2.c" can be found here http://pastebin.com/BzzPEWrs.

When i executed static-analyzer with the command line "-cc1 -analyze
-analyzer-checker=core.
experimental.UncheckedReturn -analyzer-store region
/home/polo/test/largetest/bzip2.c", it worked OK. But the result was not
exactly what i want, since the analyzer reached the maximum number of
exploded nodes. So i added "-analyzer-max-nodes 0" to the command line,
after a while the static-analyzer crashed because exhausted all my
memory(about 3G).

I thought it was my fault in the UncheckedReturn checker, but after i tried
some other checkers with the same command line i found it was a path
explotion. And i found with "-analyze-function BZ2_decompress" the analyzer
still crashed.

terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc
0  clang          0x09fc26a7
1  clang          0x09fc2434
2                 0x007c3400 __kernel_sigreturn + 0
3  libc.so.6      0x0021aa82 abort + 386
4  libstdc++.so.6 0x009e152f __gnu_cxx::__verbose_terminate_handler() + 335
5  libstdc++.so.6 0x009df465
6  libstdc++.so.6 0x009df4a2
7  libstdc++.so.6 0x009df5e1
8  libstdc++.so.6 0x009dfc5f operator new(unsigned int) + 127
9  clang          0x092a7da0
10 clang          0x092a7345
11 clang          0x092a648d
12 clang          0x092a53da
13 clang          0x092a4489
14 clang          0x092a39b0
15 clang          0x092a1ece
16 clang          0x092a2895
17 clang          0x0927546f
clang::ento::GRStateManager::removeDeadBindings(clang::ento::GRState const*,
clang::StackFrameContext const*, clang::ento::SymbolReaper&) + 239
18 clang          0x092577fb
clang::ento::ExprEngine::ProcessStmt(clang::CFGStmt,
clang::ento::StmtNodeBuilder&) + 371
19 clang          0x09257610
clang::ento::ExprEngine::processCFGElement(clang::CFGElement,
clang::ento::StmtNodeBuilder&) + 150
20 clang          0x092474ae
clang::ento::CoreEngine::HandlePostStmt(clang::CFGBlock const*, unsigned
int, clang::ento::ExplodedNode*) + 266
21 clang          0x092468a0
clang::ento::CoreEngine::ExecuteWorkList(clang::LocationContext const*,
unsigned int, clang::ento::GRState const*) + 1102
22 clang          0x0917e9e0
clang::ento::ExprEngine::ExecuteWorkList(clang::LocationContext const*,
unsigned int) + 54
23 clang          0x0917d1c6
24 clang          0x0917d2bd
25 clang          0x0917d343
26 clang          0x0917d090
27 clang          0x0917ca97
28 clang          0x0917cd31
29 clang          0x08e6698f clang::ParseAST(clang::Sema&, bool) + 617
30 clang          0x08bcdf63 clang::ASTFrontendAction::ExecuteAction() + 253
31 clang          0x08bcdbbe clang::FrontendAction::Execute() + 328
32 clang          0x08bb5fe7
clang::CompilerInstance::ExecuteAction(clang::FrontendAction&) + 779
33 clang          0x08b5ccb7
clang::ExecuteCompilerInvocation(clang::CompilerInstance*) + 835
34 clang          0x08b4f485 cc1_main(char const**, char const**, char
const*, void*) + 1014
35 clang          0x08b588d7 main + 521
36 libc.so.6      0x00203bd6 __libc_start_main + 230
37 clang          0x08b4eb61
Stack dump:
0.    Program arguments: clang -cc1 -analyze
-analyzer-checker=unix.experimental.Chroot -analyzer-store region
-analyze-function BZ2_decompress -analyzer-max-nodes 0
/home/polo/test/largetest/bzip2.c
1.    <eof> parser at end of file
2.    /home/polo/test/largetest/bzip2.c:3443:4: Error evaluating statement
[1]-  Killed                  emacs
Aborted

So here's my problem, if we want to gather path-sensitive statistical
infomation, we probably need to analyze all the paths. But the upper problem
didn't allow us to do so.

IMO, there may be several ways overcome this:

   1. Increase my computer's memory...but i think it may not solve the
   problem.
   2. Change the worklist Algorithm form BFS to DFS, and after a path was
   analyzed, release the memory generated in current path analyze. Is this
   feasible or useful?
   3. Or is there any other way to compromise?

ps:  We should not let clang crashed even if the memory exhausted, right?

-- 
Best regards!

Lei Zhang
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/cfe-dev/attachments/20110519/4e6dc37e/attachment.html>