Clang Static Analyzer - BodyFarm

1.一個空指針解引用Bug

CSA不支持跨編譯單元的分析，但是已經有一些關於Cross-Translation-unit的patch，最早的是Summary IPA thoughts，它將符號化的擴展圖（ExplodedGraph）作為函數的摘要信息，然後在函數調用點使用上下文場景信息對這個符號化擴展圖進行實例化。這個機制如下圖所示，左側是函數f()的符號化函數摘要，而右側為實例化過程，其中粉色框為實例化過程中有效的結點。

註：Summary-based inter-unit analysis for Clang Static Analyzer

這個方式有一個限制就是必須能夠得到函數的源碼，有了源碼才能夠得到其符號化的函數摘要，然後才能進一步地進行過程間乃至跨文件的分析。現實生活中很多代碼場景是很難獲得函數源碼的，例如下面代碼test.cpp：

// test.cppn#include <cstring>nusing namespace std;nnint main()n{n const char *target = "Hello World!";n char *str = 0;n strstr(str, target);n return 0;n}n

上述代碼std::strstr()方法中有一個空指針解引用，CSA是掃描不出來這個Bug的。即使為CSA添加上基於符號化函數摘要的跨文件分析能力，依然無法掃描出這個Bug，因為std::strstr()實現在另外一個庫文件中（libc.a，strstr-sse2-unaligned.o），最終是以libc.a靜態庫的形式鏈接成為可執行文件的。使用基於符號化函數摘要的方法由於無法獲得方法std::strstr()的函數體，所以對這種情況也無能為力。

2.BodyFarm機制

BodyFarm提供了另外一種解決上述bug的思路，BodyFarm機制的含義就是在進行代碼分析的過程中，實時構造出一個假的AST，這個AST是人為構建的。BodyFarm的核心是一個ASTMaker類，這個類如下所示。

class ASTMaker {npublic:n ASTMaker(ASTContext &C) : C(C) {}nn /// Create a new BinaryOperator representing a simple assignment.n BinaryOperator *makeAssignment(const Expr *LHS, const Expr *RHS, QualType Ty);n /// Create a compound stmt using the provided statements.n CompoundStmt *makeCompound(ArrayRef<Stmt*>);n /// ...n};n

上面提供的構造AST結點的介面其實是對BinaryOperator和CompoundStmt構造函數的封裝，我們可以向ASTMaker類添加自己想要的介面，用於夠構造出符合要求的AST。CSA構造了一些針對Obj-C函數的AST，如下所示。

/// Create a fake body for dispatch_once.nstatic Stmt *create_dispatch_once(ASTContext &C, const FunctionDecl *D);n/// Create a fake body for dispatch_sync.nstatic Stmt *create_dispatch_sync(ASTContext &C, const FunctionDecl *D);n

這些方法會在靜態分析的過程中被調用，CSA的過程間分析使用的是inline方法，在遇到外部函數調用時會首先判斷是否可以inline，這個判斷函數就是shouldInlineCall()，然後判斷這個函數是否存在「Fake Body」。所以只要我們在BodyFarm.cpp中構造std::strstr()對應的AST，在遇到std::strstr()的調用時，就會調用我們偽造的AST，然後構造CFG，進行inline，最終進行過程間的分析，發現這個Bug。

3.解決過程

首先需要為std::strstr()偽造一個AST，這裡我們不需要關心std::strstr()的實現（std::strstr的實現有很多，並且完整構造其AST也很麻煩）。我們的目的在於檢測出空指針解引用，並且能夠做到std::strstr()幾乎對上下文環境沒有什麼影響，就像下面Ted Kremenek所說的，如果將std::strstr()方法對應的AST全部構造出來，可能給analyzer帶來額外的負擔。所以我們可以將std::strstr()的AST構造成為一個指針解引用語句。

註：Ted Kremenek - "Moreover, the synthesized body can be optimized more for the task of static analysis, and less on the actual implementation details which can contribute additional complexity for the analyzer to reason about."

但是如果只添加一個個空指針解引用語句，又會帶來額外的問題，現在的CSA在面對無法inline的函數調用時，會執行conservativeEvalCall()，由於"pointer escape"CSA此時會調用invalidateRegion()對非const的傳址參數指向的內存區域進行失效操作，參見clang static analyzer源碼分析（番外篇）：RegionStore以及evalCall()中的conservativeEvalCall。

如下代碼示例所示：

char *my_strstr(char *str, const char *target);nint main()n{n char str[] = "Hello";n const char *target = "lo";n // 鬼知道my_strstr()會對我的"Hello"做什麼，所以clang在得不到my_strstrn // 的函數體的時候，會使str指向的內存區域失效，也就是str會指向一個n // SymbolicRegionn my_strstr(str, target);n return 0;n}n

而std::strstr()的函數原型如下所示，第二個方法的第一個參數是非const傳址調用，所以我們需要對這塊內存進行失效操作。

const char* strstr( const char* str, const char* target );ttn char* strstr( char* str, const char* target );n

對第一個非const參數指向的內存區域進行失效操作，最簡單的方法是在構造AST的時候，額外添加一個無關函數，將這個非const參數作為這個無關函數的參數，構造出一個"pointer escape"場景。所以最終我們偽造的std::strstr()函數體如下所示：

void strstr(char* str, const char* target)n{n void AuxiliaryFakeFunc(char*);n char c;n c = *str;n AuxiliaryFakeFunc(str);n}n

下面我們在BodyFarm.cpp中添加的create_std_strstr()方法如下。

/// Create a fake body for std::strstr.nstatic Stmt *create_std_strstr(ASTContext &C, const FunctionDecl *D) {n // Check is we have at least one parameters.n if (D->param_size() != 2)n return nullptr;nn // Check if the first parameter is a pointer to char type.n const ParmVarDecl *firstParmDecl = D->getParamDecl(0);n QualType firstParmType = firstParmDecl->getType();n const PointerType *firstParmPointerType = firstParmType->getAs<PointerType>();n if (!firstParmPointerType)n return nullptr;n QualType firstParmPointeeType = firstParmPointerType->getPointeeType();n if (!firstParmPointeeType->isCharType())n return nullptr;nn // Check if the second parameter is a pointer to char type.n const ParmVarDecl *secondParmDecl = D->getParamDecl(1);n QualType secondParmType = secondParmDecl->getType();n const PointerType *secondParmPointerType = secondParmType->getAs<PointerType>();n if (!secondParmPointerType)n return nullptr;n QualType secondParmPointeeType = secondParmPointerType->getPointeeType();n if (!secondParmPointeeType->isCharType())n return nullptr;nn ASTMaker M(C);n // (1) Create the FunctionDecl.n FunctionDecl *FD = M.makeAuxiliaryFakeFunc(DeclarationName(),ntconst_cast<DeclContext*>(D->getDeclContext()), C.CharTy,ntD->getTypeSourceInfo());nn // (2) Create the CallExpr.n CallExpr *CE = M.makeCallExpr(ntM.makeLvalueToRvalue(M.makeDeclRefExpr(FD), FD->getType()),ntM.makeDeclRefExpr(firstParmDecl), C.VoidTy);nn // (3) Create the Assignment.n IntegerLiteral *IL =n IntegerLiteral::Create(C, llvm::APInt(C.getTypeSize(C.CharTy), 0),n C.CharTy, SourceLocation());nn BinaryOperator *BO = new(C) BinaryOperator(n M.makeDereference(nt M.makeLvalueToRvalue(nttM.makeDeclRefExpr(firstParmDecl), firstParmType),n firstParmPointeeType),nt M.makeIntegralCast(IL, firstParmPointeeType), n BO_Assign, firstParmPointeeType, VK_RValue, OK_Ordinary,nt firstParmDecl->getLocStart(), false);n Stmt *Stmts[] = {BO, CE};n CompoundStmt *CS = M.makeCompound(Stmts);n return CS;n}n

構造出來的AST如下所示：

CompoundStmt 0x5614484119a8n|-BinaryOperator 0x561448411980 const char =n| |-UnaryOperator 0x561448411948 const char lvalue prefix *n| | `-ImplicitCastExpr 0x561448411930 const char * <LValueToRValue>n| | `-DeclRefExpr 0x561448411908 const char * lvalue ParmVar 0x5614484052c0 __haystack const char *n| `-ImplicitCastExpr 0x561448411968 const char <IntegralCast>n| `-IntegerLiteral 0x5614484118e8 char 0n`-CallExpr 0x5614484118b8 voidn |-ImplicitCastExpr 0x5614484118a0 char <LValueToRValue>n | `-DeclRefExpr 0x561448411878 char lvalue Function 0x5614484117b8 charn `-DeclRefExpr 0x561448411850 const char * lvalue ParmVar 0x5614484052c0 __haystack const char *n

最終Clang Static Analyzer在遇到std::strstr()函數調用的時候，會走defaultEvalCall() -> getRuntimeDefinition() -> getBody()，最終會得到我們偽造的AST，這個AST目的只有一個，即在不影響原有狀態的情況下，將空指針解引用的Bug報出來。下面是我們的測試用例及測試結果。

// 測試用例n#include <cstring>nint main()n{ntconst char *target = "Hello World!";ntchar *str = 0;ntstrstr(str, target);ntreturn 0;n}n

測試環境，ubuntu-17.04/clang-4.0/gcc-6.0，測試結果如下，下面報出了"Dereference of null pointer"的Bug。

// ubuntu-17.04/clang-4.0/gcc-6nnscan-build --use-analyzer=/usr/local/bin/clang++ -enable-checker core.NullDereference -disable-checker nullability.NullPassedToNonnull -disable-checker core.NonNullParamChecker clang++ test.cpp -cnscan-build: Using /usr/local/bin/clang++ for static analysisntest.cpp:14:2: warning: ignoring return value of function declared with pure attribute [-Wunused-value]n strstr(str, target);n ^~~~~~ ~~~~~~~~~~~n1 warning generated.nstrstrnwarning: Path diagnostic report is not generated. Current output format does not support diagnostics that cross file boundaries. Refer to --analyzer-output for valid output formatsnIn file included from test.cpp:1:nIn file included from /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/c++/6.3.0/cstring:42:n/usr/include/string.h:337:22: warning: Dereference of null pointer (loaded from variable __haystack)nextern char *strstr (const char *__haystack, const char *__needle)n ^n1 warning generated.nscan-build: Removing directory /tmp/scan-build-2017-08-03-165127-2673-1 because it contains no reports.nscan-build: No bugs found.n

其實這個測試用例，用的不太好，因為這裡調用的"std::strstr(str, target)"匹配的是std::strstr(const char *, const char*)，其實這裡是個誤報，誤報的原因在於我們判斷是否是std::strstr(char*, const char*)時，沒有判斷兩個形式參數的const限定符，如果添加上這個判斷，其實是不會使用我們偽造的AST的，但是這並不影響我們說明BodyFarm的機制，我們就默認這裡匹配的是std::strstr(char*, const char*)好了，: )。

對於另外一種按照std::strstr()實現精確偽造AST的做法，自己水平有限，就沒有做，確實很複雜。但是這種做法會使整個分析更加精確，相當於函數體在這裡進行了展開。

4.總結

BodyFarm在Clang Static Analyzer中的狀態如下，

• BodyFarm機制是Clang Static Analyzer的Open Projects之一，貌似在進展中。
• 鑒於現在源代碼中很多這樣的庫函數，而且庫函數的實現都是以鏈接的形式提供的，所以BodyFarm機制可以作為全程序分析的一種補充手段。
• 使用BodyFarm合成的函數體，在現有機制中是默認inline的，所以函數如果很複雜，就不要使用BodyFarm了，一是分析時間增加，二是編碼難度提高
• 偽造複雜的AST，需要對Clang AST有一定程度的了解。
• 由於是偽造的AST，就沒有相應的SourceLocation信息，所以如何對SourceLocation進行設置，報錯的時候報錯位置如何展示也是一個問題。
• 現階段，Clang Static Analyzer對於在偽造AST中的報錯，是直接丟棄掉的，具體見BugReporter.cpp
• 現階段CSA對於庫函數帶來的空指針問題使用CStringChecker和實現。

總之，如果源代碼中有大量的簡單的庫函數，使用BodyFarm也是一種不錯的選擇。

參考：

1.How to give hint on path execution？

2.StaticAnalyzer: Implementing checks for std::string.

3.Lazily parsing additional source files.

4.clang static analyzer源碼分析（番外篇）：RegionStore以及evalCall()中的conservativeEvalCall.