retdec-llvmir2hll fails in SimpleCopyPropagationOptimizer due to insufficient stack space

[julupu]

Hello!

Decompiling (retdec-llvmir2hll) Teslacrypt (https://github.com/ytisf/theZoo/tree/master/malwares/Binaries/Ransomware.TeslaCrypt)
fails with a huge stacktrace for reasons I currently don't understand:

Running phase: alias analysis [simple] ( 8.13s )
Running phase: optimizations [normal] ( 8.41s )
 -> running RemoveUselessCastsOptimizer ( 8.41s )
 -> running UnusedGlobalVarOptimizer ( 8.65s )
 -> running DeadLocalAssignOptimizer ( 8.91s )
 -> running SimpleCopyPropagationOptimizer ( 12.34s )
#0 0x000000000096e4c5 llvm::sys::PrintStackTrace(llvm::raw_ostream&) (/usr/local/bin/retdec-llvmir2hll+0x96e4c5)
#1 0x000000000096c29e llvm::sys::RunSignalHandlers() (/usr/local/bin/retdec-llvmir2hll+0x96c29e)
#2 0x000000000096c4d6 SignalHandler(int) (/usr/local/bin/retdec-llvmir2hll+0x96c4d6)
#3 0x00007faa50423f70 __restore_rt (/lib64/libpthread.so.0+0x11f70)
#4 0x000000000050ba1a std::pair<std::_Rb_tree_iterator<std::shared_ptr<retdec::llvmir2hll::Variable> >, bool> std::_Rb_tree<std::shared_ptr<retdec::llvmir2hll::Variable>, std::shared_ptr<retdec::llvmir2hll::Variable>, std::_Identity<std::shared_ptr<retdec::llvmir2hll::Variable> >, std::less<std::shared_ptr<retdec::llvmir2hll::Variable> >, std::allocator<std::shared_ptr<retdec::llvmir2hll::Variable> > >::_M_insert_unique<std::shared_ptr<retdec::llvmir2hll::Variable> const&>(std::shared_ptr<retdec::llvmir2hll::Variable> const&) (/usr/local/bin/retdec-llvmir2hll+0x50ba1a)
#5 0x000000000053370a retdec::llvmir2hll::ValueAnalysis::visit(std::shared_ptr<retdec::llvmir2hll::Variable>) (/usr/local/bin/retdec-llvmir2hll+0x53370a)
#6 0x000000000067d5fa retdec::llvmir2hll::Variable::accept(retdec::llvmir2hll::Visitor*) (/usr/local/bin/retdec-llvmir2hll+0x67d5fa)
#7 0x00000000008ab6e7 retdec::llvmir2hll::OrderedAllVisitor::visit(std::shared_ptr<retdec::llvmir2hll::AddOpExpr>) (/usr/local/bin/retdec-llvmir2hll+0x8ab6e7)
#8 0x000000000053004e retdec::llvmir2hll::ValueAnalysis::visit(std::shared_ptr<retdec::llvmir2hll::AddOpExpr>) (/usr/local/bin/retdec-llvmir2hll+0x53004e)
#9 0x00000000005cafea retdec::llvmir2hll::AddOpExpr::accept(retdec::llvmir2hll::Visitor*) (/usr/local/bin/retdec-llvmir2hll+0x5cafea)
#10 0x000000000052e80f retdec::llvmir2hll::ValueAnalysis::visit(std::shared_ptr<retdec::llvmir2hll::AssignStmt>) (/usr/local/bin/retdec-llvmir2hll+0x52e80f)
#11 0x00000000005d2087 retdec::llvmir2hll::AssignStmt::accept(retdec::llvmir2hll::Visitor*) (/usr/local/bin/retdec-llvmir2hll+0x5d2087)
#12 0x000000000052e659 retdec::llvmir2hll::ValueAnalysis::getValueData(std::shared_ptr<retdec::llvmir2hll::Value>) (/usr/local/bin/retdec-llvmir2hll+0x52e659)
#13 0x000000000058e9a3 retdec::llvmir2hll::OptimFuncInfoCFGTraversal::updateFuncInfo(std::shared_ptr<retdec::llvmir2hll::Statement>) (/usr/local/bin/retdec-llvmir2hll+0x58e9a3)
#14 0x000000000058f1e2 retdec::llvmir2hll::OptimFuncInfoCFGTraversal::visitStmt(std::shared_ptr<retdec::llvmir2hll::Statement>) (/usr/local/bin/retdec-llvmir2hll+0x58f1e2)
#15 0x0000000000582308 retdec::llvmir2hll::CFGTraversal::performTraversalImpl(std::shared_ptr<retdec::llvmir2hll::CFG::Node>, __gnu_cxx::__normal_iterator<std::shared_ptr<retdec::llvmir2hll::Statement> const*, std::vector<std::shared_ptr<retdec::llvmir2hll::Statement>, std::allocator<std::shared_ptr<retdec::llvmir2hll::Statement> > > >) (/usr/local/bin/retdec-llvmir2hll+0x582308)

[...]

#255 0x0000000000582476 retdec::llvmir2hll::CFGTraversal::performTraversalImpl(std::shared_ptr<retdec::llvmir2hll::CFG::Node>, __gnu_cxx::__normal_iterator<std::shared_ptr<retdec::llvmir2hll::Statement> const*, std::vector<std::shared_ptr<retdec::llvmir2hll::Statement>, std::allocator<std::shared_ptr<retdec::llvmir2hll::Statement> > > >) (/usr/local/bin/retdec-llvmir2hll+0x582476)
Stack dump:
0.      Program arguments: /usr/local/bin/retdec-llvmir2hll -target-hll=c -var-renamer=readable -var-name-gen=fruit -var-name-gen-prefix= -call-info-obtainer=optim -arithm-expr-evaluator=c -validate-module -llvmir2bir-converter=orig -o [DIR]/teslacrypt/3372c1edab46837f1e973164fa2d726c5c5e17bcb888828ccd7c4dfcc234a370.c [DIR]/teslacrypt/3372c1edab46837f1e973164fa2d726c5c5e17bcb888828ccd7c4dfcc234a370.c.backend.bc -enable-debug -emit-debug-comments -config-path=[DIR]/teslacrypt/3372c1edab46837f1e973164fa2d726c5c5e17bcb888828ccd7c4dfcc234a370.c.json -max-memory-half-ram 
1.      Running pass 'Decompiler' on module '[DIR]/teslacrypt/3372c1edab46837f1e973164fa2d726c5c5e17bcb888828ccd7c4dfcc234a370.c.backend.bc'.
Error: Decompilation of file [DIR]/teslacrypt/3372c1edab46837f1e973164fa2d726c5c5e17bcb888828ccd7c4dfcc234a370.c.backend.bc failed

[s3rvac]

Thank you for the report. I have managed to reproduce the issue on my PC. The fail is caused by insufficient stack space. The problem is that many of the analyses in retdec-llvmir2hll are implemented recursively and when the generated AST in the back-end is deeply nested, they fail on insufficient stack size (see also #47, in which the analysis fails because of the same reason). After increasing the stack size via

ulimit -s 100000

I was able to decompile the file, although it took 100 minutes, retdec-llvmir2hll run out of memory twice during the decompilation, and the output C file has 138 MB. This suggests that the input file cannot be decompiled by RetDec at the moment. I believe that RetDec failed to decode parts of the file properly or generated hard-to-structure LLVM IR, which caused a huge increase in the size of the output and resulted in the reported issue. We will have to investigate this, though.

At present, there are the following workarounds you can try:

• Run the decompilation with --backend-no-opts, which will disable all optimizations in retdec-llvmir2hll. This will most probably result in a huge output C code, though.
• Try to decompile only a part of the input binary, as suggested here.

[spaceone]

I think I hit this issue, too (or #144).

ulimit -Ss 67108864
python3 retdec-decompiler.py --no-memory-limit ../../aim.exe
…
Running phase: removing functions prefixed with [__decompiler_undefined_function_] ( 101.47s )
Running phase: removing functions from standard libraries ( 108.62s )
 -> removing InterlockedExchangeAdd() ( 108.63s )
Running phase: removing code that is not reachable in a CFG ( 108.63s )
Warning: [NonRecursiveCFGBuilder] there is no node for an edge to `v5_405517 = *(IntToPtrCastExpr<ptr>((v0_405539 + 1)))` -> skipping this edge
Running phase: signed/unsigned types fixing ( 111.61s )
Running phase: converting LLVM intrinsic functions to standard functions ( 119.18s )
Running phase: obtaining debug information ( 120.68s )
Running phase: alias analysis [simple] ( 120.88s )
Running phase: optimizations [normal] ( 121.96s )
 -> running RemoveUselessCastsOptimizer ( 121.96s )
 -> running UnusedGlobalVarOptimizer ( 122.85s )
 -> running DeadLocalAssignOptimizer ( 123.96s )

 -> running SimpleCopyPropagationOptimizer ( 234.29s )
Warning: [NonRecursiveCFGBuilder] there is no node for an edge to `# empty statement` -> skipping this edge
Error: Decompilation of file /root/aim.c.backend.bc failed

I wonder why there is no stack trace displayed in my case?
My input file is only 800kb and it still crashes with having 8GB RAM?

[s3rvac]

@spaceone Could you please attach the binary file that you are trying to decompile (aim.exe)?

[spaceone]

@s3rvac I prefer to send this to you via email, so it doesn't get public available. I'll use your gmail address.

[s3rvac]

@spaceone Thank you for the file. Here is a reaction to your questions:

I wonder why there is no stack trace displayed in my case?

I am not sure. I have tried to decompile the file with both Release and Debug version of RetDec and it has printed a stack trace in both cases.

My input file is only 800kb and it still crashes with having 8GB RAM?

Unfortunately, yes. The decompilation indeed fails because of insufficient stack space as valgrind reports

==28640== Stack overflow in thread #1: can't grow stack to 0x1ffe801000

There may also be an infinite loop. We will have to verify when we get to work on this issues.

[spaceone]

Okay, thank you very much, also for you email reply!

[s3rvac]

There have been several optimizations regarding this issue (most importantly #492, #495, #509). The decompilation of 3372c1edab46837f1e973164fa2d726c5c5e17bcb888828ccd7c4dfcc234a370 (TeslaCrypt) with the latest version of RetDec now succeeds. However, the decompilation of aim.exe still fails inside

Running phase: removing functions prefixed with [__decompiler_undefined_function_] ( 47.37s )

Possibly either insufficient stack space or inifinite recursion in

src/llvmir2hll/support/funcs_with_prefix_remover.cpp:175
src/llvmir2hll/support/visitors/ordered_all_visitor.cpp:582