-
-
[翻译]clang-analyzer-guide-v0.1
-
2022-11-1 18:13 18786
-
分享的是CSA guide的简单翻译,请大佬们指正,可以直接看附件的文件
Clang static analyze是开源编译器clang上的静态检测工具,可用于源代码的缺陷检测
添加一个简单的checker(检查函数有没有调用main()函数)
1 2 3 4 5 6 | typedef int ( * main_t)( int ,char * * ); int main( int argc,char * * argv){ main_t foo = main; int exit_code = foo(argc,argv); / / 调用了main() return exit_code; } |
checker位置lib/StaticAnalyzer/Checkers/Checkers.td
将checker的源代码名添加到lib/StaticAnalyzer/Checkers/CMakeLists.txt 这样重建clang的时候就会被添加进去
源代码放于lib/StaticAnalyzer/Checkers/MainCallChecker.cpp
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 | #include"ClangSACheckers.h" #include"clang/StaticAnalyzer/Core/BugReporter/BugType.h" #include"clang/StaticAnalyzer/Core/Checker.h" #include"clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h" #include"clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h" using namespace clang; using namespace clang::ento; namespace{ class MainCallChecker: public Checker<check::PreCall>{ / / csa的checker是继承Checker<...>的类模板来实现的 mutable std::unique_ptr<BugType> BT; public: void checkPreCall(const CallEvent&Call,CheckerContext &C)const; }; } / / Checker类定义通常放在匿名命名空间中,以避免在将多个checker加载到分析器时发生命名冲突 void MainCallChecker::checkPreCall(const CallEvent &Call, / / CallEvent结构体中包含分析器收集的关于函数调用上的所有数据 尤其是被调用函数的信息和参数值 CheckerContext &C) const{ / / CheckerContext 包含各种功能检查器可以用来分析中的信息和影响分析流程 if (constIdentifierInfo * II = Call.getCalleeIdentifier()) / / 从CallEvent结构中获取IdentitierInfo 函数标识符信息,如果getCalleeIdentifier函数返回NULL就返回然后继续向下分析 if (II - >isStr( "main" )){ / / 查看被调用函数的标识符里是否有main if (!BT) BT.reset(new BugType(this, "Call to main" , "Example checker" )); / / BT中包含不同的错误类型,可以被储存和重用,在此处被初始化为“Call to main” ExplodedNode * N = C.generateErrorNode(); / / 生成一个sink节点 意味着程序可能会崩溃,如果该缺陷不重要,就不用停止分析 auto Report = llvm::make_unique<BugReport>( * BT,BT - >getName(),N); / / 创建了一个新的BugReport对象,将sink抛出并包含警告消息 C.emitReport(std::move(Report)); / / 使用emitReport()方法将报告传回CheckerContext,报告将会被整合去重复,显示的给用户 } } void ento::registerMainCallChecker(CheckerManager &Mgr){ / / 可以早分析开始时实际创建检查实例,可以使用此部分禁用整个翻译单元的某些检查程序 Mgr.registerChecker<MainCallChecker>(); / / 创建了MainCallChecker实例 } |
可以将checker编译为一个共享插件库,这样就不用去修改Checkers.td和CMakeLists.txt,编译成独立的库,运行时加载它
将头文件从ClangSACheckers.h换成CheckerRegistry.h
1 | # include "clang/StaticAnalyzer/Core/CheckerRegistry.h" |
然后在库中定义一个外部可见的函数,在分析器的CheckerRegistry中动态注册checker
1 2 3 4 | extern "C" void clang_registerCheckers( CheckerRegistry ®istry ) { registry . addChecker < MainCallChecker >( "alpha.core.MainCallChecker" , " Checks for calls to main" ); } |
clang API版本需要和插件API版本匹配,checker需要将它的版本字符串存储在外部可见的clang_analyzerAPIVersionString变量中,以便进行兼容性检查:
1 2 | extern "C" const char clang_analyzerAPIVerionString[] = CLANG_ANALYZER_API_VERSION_STRING; |
通过clang -cc1 -load Checker.so插件语法加载checker后,会显示在-analyzer-checker-help列表中
AST 抽象语法树
1 2 3 4 5 6 7 | void foo ( int x ) { int y , z ; if ( x = = 0 ) y = 5 ; if (! x ) z = 6 ; } |
1 2 | clang - cc1 - ast - dump test . c clang - cc1 - ast - dump - fcolor - diagnostics TestFD.c |
抽象语法树很容易检查类似‘’y = x / 0‘这样的错误,但很难检查出‘’z = 0;,,,,;y = x / z’这样的错误’
CFG 控制流图
1 | clang - cc1 - analyze - analyzer - checker = debug.ViewCFG test.c |
CFG不能立即提供数据流分析,需要额外的代码来实现,clang提供了一些现成的基于CFG的解决方案,例如livenessAnalysis deadcode.DeadStores
deadcode.UnreachableCode将CFG和路径敏感分析结合的checker
CFG效率有限,如上图,要么同时走[B3],[B1],否则都不走
Exploded graph 爆炸图 爆炸图由分析器在CFG中探索的所有路径组成,并在每个语句的每个路径上携带有关程序状态的信息
clang -cc1 -analyze -analyzer-checker = debug.ViewExplodedGraph test.c
爆炸图占内存很大
checker首先模拟第一个操作,即比较运算符x == 0。因为x的值在分析的这一点是未知的(事实上,永远也不会知道),所以这个值被表示为符号reg$0<x>。(在分析开始时存储在参数变量x的内存区域中的值)
因为不确定选择哪个分支,所以我们将爆炸图分成两种可能的路径。创建新节点在每个路径,通过假设象征reg $0<x>把值限定到一定范围:
真正的分支,它被认为是一个整数的范围0,0,
虚假的分支,它被认为属于[21417483648,−1]∪[1,21417483647]。
y在[B3]中被绑定值5,[B1]中z被绑定值为6,此时y绑定的5不会出现在程序状态中(y不再被引用),此时它被回收
最后到达[B0]程序结束
爆炸图中存储的信息是详尽的,与基于AST和CFG的分析不同,对路径敏感的CSA checker很少被动的使用爆炸图,而是积极的参与爆炸图的构建,添加自己的节点、绑定、假设、留下特定于检查的标记,并按照意愿咋爆炸图中分割路径。
AST-based checker不参与它们所分析的数据结构的构造,没有立即触发路径敏感引擎的最有用的回调函数是
check::EndOfTranslationUnit 和 check::ASTCodeBody
1 2 | void checkEndOfTranslationUnit (const TranslationUnitDecl * TU , AnalysisManager &AM , BugReporter &BR ) const ; / / TU AST整个翻译单元的声明 |
在这个回调中,可以分析程序的完整AST
当不仅需要检查可执行代码,而且需要检查声明时,通常使用这种回调。
1 | void checkASTCodeBody (const Decl * D ,AnalysisManager &AM , BugReporter &BR ) const ; |
在这个回调函数中,每次调用都会提供函数的声明,分析器通常会分析函数的代码本体。
需要分析的函数体可以作为D->getBody()使用。当只需要分析可执行代码时,这种回调很方便。
1 | void checkASTDecl (const T * D, AnalysisManager &Mgr, BugReporter &BR) const ; |
这个回调函数被叫做所有AST定义的声明
AST visitors
ConstStmtVisitor 被广泛用于检查代码体
ConstDeclVisitor 有时用于检查代码体外的声明(如全局变量)。
为了使用访问器,您需要从它继承一个类,并为不同类型的AST节点实现访问器回调。当一个回调没有为一个特定的节点实现时,一个更通用的节点的回调将被调用:
1 2 3 4 | VisitCXXOperatorCallExpr(...), VisitCallExpr(...), VisitExpr(...), VisitStmt(...), |
VisitCXXOperatorCallExpr()将在下列回调中被访问( 第一个被定义的)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 | namespace { class WalkAST : public ConstStmtVisitor<WalkAST>{ BugReporter &BR; AnalysisDeclContext * ADC; void VisitChildren(const Stmt * S); public: WalkAST(BugReporter &Reporter,AnalysisDeclContext * Context) : BR(Reporter), ADC(Context){} void VisitStmt (const Stmt * S); / / 用于访问其他类型的语句 void VisitCallExpr (const CallExpr * CE); / / 用于函数表达式的特殊处理 }; } void WalkAST::VisitChildren(const Stmt * S){ for (Stmt::const_child_iterator I = S - >child_begin(),E = S - >child_end();I! = E; + + I) if (const Stmt * Child = * I) Visit(Child); } / / 访问完声明后再去访问其子声明 void WalkAST::VisitStmt(const Stmt * S){ VisitChildren(S); } void WalkAST::VisitCallExpr(const CallExpr * CE){ / / 大多数检查逻辑都写到VisitCallExpr if (const FunctionDecl * FD = CE - >getDirectCallee()) if (const IdentifierInfo * II = FD - >getIdentifier()) if (II - >isStr( "main" )){ SourceRange R = CE - >getSourceRange(); PathDiagnosticLocation ELoc = PathDiagnosticLocation::createBegin(CE,BR.getSourceManager(),ADC); BR.EmitBasicReport(ADC - >getDecl(), "Call to main" , "Example checker" , "Call to main" ,ELoc,R); } VisitChildren(CE); } namespace{ class MainCallCheckerAST:public Checker<check::ASTCodeBody>{ public: void checkASTCodyBody(const Decl * D,AnalysisManager &AM, BugReporter &B)const; }; } void MainCallCheckerAST::checkASTCodeBody(const Decl * D,AnalysisManager &AM,BugReporter &BR) const{ WalkAST Walker(BR,AM.getAnalysisDeclContext(D)); Walker.visit(D - >getBody()); } |
访问者从表示函数体的复合语句开始,然后下降到子语句
有时为了同时访问状态和声明,会将那个visit合并到一起,这种情况下可以让两个visit继承过来
1 2 3 4 5 6 7 8 | class WalkAST : public ConstStmtVisitor<WalkAST>, public ConstDeclVisitor<WalkAST> { / * ... * / public: using ConstStmtVisitor<WalkAST>::Visit; using ConstDeclVisitor<WalkAST>::Visit; / * ... * / }; |
3.3. AST matcher
1 | callExpr(callee(functionDecl(hasName( "main" )))).bind( "call" ) |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 | namespace{ class Callback : public MatchFinder::MatchCallback{ BugReporter &BR; AnalysisDeclContext * ADC; public: void run(const MatchFinder::MatchResult &Result); Callback(BugReporter &Reporter, AnalysisDeclContext * Context) : BR(Reporter), ADC(Context){} }; } void Callback::run(const MatchFinder::MatchResult &result){ const CallExpr * CE = Result.Nodes.getStmtAs<CallExpr>( "call" ); / / call在bind()定义,通过他来获取调用表达式 assert (CE); SourceRange R = CE - >getSourceRange(); PathDiagnosticLocation ELoc = PathDiagnosticLocation::createBegin(CE,BR.getSourceManger(),ADC); BR.EmitBasicReport(ADC - >getDecl(), "Call to main" , "Example checker" , "Call to main" ,Eloc,R); } namespace{ / / 定义checker,全翻译单元匹配 class MainCallCheckerMatchers : public Checker<check::EndOfTranslationUnit>{ public: void checkEndOfTranslationUnit(const TranslationUnitDecl * TU, AnalysisManager &AM, BugReporter &B) const; }; } void MainCallCheckerMatchers::checkEndOfTranslationUnit( const TranslationUnitDecl * TU,AnalysisManager &AM, BugReporter &B)const{ MatchFinder F; / / MatchFinder的matchAST()让它匹配翻译单元的整个AST Callback CB(B,AM.getAnalysisDeclContext(TU)); F.addMatcher( stmt(hasDescendant(callExpr(callee(functionDecl(hasName( "main" )))).bind( "call" ))), &CB); F.matchAST(AM.getASTContext()); / / 从AnalysisManager中获得getASTContext结构,里面包含了整个程序的AST以及各种元信息 } |
重用匹配器
1 2 3 | TypeMatcher TypeM = templateSpecializationType(). bind ( "type" ); DeclarationMatcher VarDeclM = varDecl (hasType (TypeM )). bind ( "decl" ); StatementMatcher TempObjM = temporaryObjectExpr(hasType(TypeM)).bind ( "stmt" ); |
在checker中实现一个自定义的AST matcher时,要将它放到clang::ast_matchers的命名空间中
1 2 3 4 5 6 7 8 | namespace clang { namespace ast_matchers { AST_MATCHER (RecordDecl ,isUnion) { return Node.isUnion(); } } / / end namespace clang } / / end namespace ast_matchers |
匹配特定的语句
MatchFinder的matchAST(…)方法匹配翻译单元的整个AST
match(...)方法来匹配AST的特定部分
1 2 3 4 5 6 7 8 9 10 | void MainCallCheckerMatchers::checkASTCodeBody(const Decl * D,AnalysisManger &AM, BugReporter &BR)const{ MatchFinder F; Callback CB(BR,AM.getAnalysisDeclContext(D)); F.addMatcher( stmt(hasDescendant( callExpr(callee(functionDecl(hasName( "main" )))).bind( "call" ))), &CB); F.matchAST( * (D - >getBody()),AM.getASTContext()); } |
match(…)的语义与matchAST(…)的语义不同:前者试图匹配语句本身,后者也试图匹配其子语句
3.4表达式折叠
从表达式的AST中很难看出表达式实际上表示的一个常量值(表达式可能包含对常数变量的类型转换和引用)
Expr的EvaluateAsInt(...)方法有现成的解决方案
1 2 3 4 5 6 7 8 9 | const Expr * E = / * some AST expression you are interested in * / llvm::APSInt Result ; if (E - >EvaluateAsInt(Result, ACtx, Expr::SE _ AllowSideEffects)) { / * we managed to obtain the value of the expression * / uint64_t IntResult = Result.getLimitedValue(); / * ... * / } else { / * the expression doesn ’t fold to into a constant value * / } |
4 Path-sensitive analysis 路径敏感分析
程序状态(ProgramState)是路径敏感分析的基本结构之一。它保存着被分析程序的瞬时状态的完整信息。通过查看程序状态,您可以获得存储在内存区域中的变量的符号值,以及在当前位置上下文中定义的表达式。
程序状态是不可变的,一旦创建,就不可修改,只能创建一个在某种意义上不同于原始状态的新状态。而且不能直接访问或管理。它们总是被包装成称为ProgramStateRef的引用计数智能指针。
在大多数路径敏感的检查器回调中,你都有一个可用的CheckerContext对象。它携带当前程序状态
1 2 3 4 | void checkEndFunction (CheckerContext &C) const { ProgramStateRef State = C.getState (); / * ... * / } |
程序状态由以下特征构成
— “Environment”: 活动表达式的符号值
— “Region Store”: 内存区域的符号值
— “Range Constraints”: 符号值可取的范围
— “Taint”: 污点 从不安全数据源获得的符号值注册表
— “Generic Data Map”: checker-specific information. checker特性信息
分析记住当前需要的所有表达式的符号值,每当一个表达式离开当前上下文时,它就会被垃圾回收并不再可用。从表达式到其符号值的映射称为环境。如果一个表达式在环境中可用,则始终可以获得它的值
1 2 3 | const Expr * E = / * some AST expression you are interested in * / ; const LocationContext * LC = C.getLocationContext(); SVal Val = State - >getSVal (E ,LC); |
如果表达式E在环境中可用,Val将是它的符号值。如果E不在当前环境中,则返回一个UnknownVal。环境不会尝试计算任何AST表达式的值;它只会返回已经存在的值。可以在里面找到在分析整个表达式前获得子表达式的值
内存区域能在分析过程中通过获取指针的符号值而得到
1 2 | const Expr * E = / * an pointer expression * / ; const MemRegion * Reg = State - >getSVal(E,LC).getAsRegion(); |
内存区域也可以通过声明变量直接获得
1 2 | const VarDecl * D = / * a declaration of a variable * / ; const MemRegion * Reg = State - > getLValue(D,LC).getAsRegion(); |
在这两种情况下,如果获得的值不代表任何内存区域,getAsRegion()将返回一个空指针
内存区域可以包含符号值;获取这样的值可以像解引用指针一样对内存区域进行引用。解引用内存区域的机制称为区域存储。每个ProgramState包含一个存储的实例,它携带已知的符号值到内存区域的绑定
1 | SVal Val = State - >getSVal(Reg); / / 获取程序状态到区域的绑定 |
区域存储会尝试生成合理的绑定,即使当前存储中没有可用的直接绑定。在这种情况下,它将构造并返回一个表示该区域未知值的符号。
迭代内存区域绑定
在StoreManager类(它维护区域存储实例的所有权)中,有一种在特定程序状态下迭代绑定的机制,称为BindingsHandler。
1 2 3 4 5 6 7 8 9 10 11 12 | class Callback : public StoreManager::BindingsHandler{ public: bool HandleBinding (StoreManager &SM, Store St, const MemRegion * Region , SVal Val ) { / * ... * / } }; / / 当需要停止迭代时,回调函数应该返回false。定义了回调函数,就可以开始迭代了 Callback CB ; StoreManager &SM = C.getStoreManager(); SM.iterBindings (State - >getStore(),CB); |
如果确定是一个已定义的值 就可以用assume()来获取状态
1 2 3 4 5 6 7 8 9 10 | SVal Val = / * a certain symbolic value * / ; Optional<DefinedOrUnknownSVal>DVal = Val.getAs<DefinedOrUnknownSVal>(); if (!DVal) return ; if (State - >assume( * DVal,true)) { / * things to do if Val can possibly be true * / } if (State - >assume( * DVal,false)) { / * things to do if Val can possibly be false * / } |
操作符号值 使用SValBuilder创建一个新的符号值
1 2 3 4 5 | SVal A = / * a certain symbolic value * / ; SVal B = / * the other symbolic value * / ; ASTContext &ACtx = C.getASTContext(); SValBuilder &SVB = C.getSValBuilder(); SVal C = SVB.evalBinOp(State,BO_GT,A,B,ACtx.BoolTy ); |
使用污点分析
1 2 3 4 5 | ProgramStateRef State = C.getState(); SVal Val = / * a certain symbolic value * / ; if (State - >isTainted (Val)) { / * ... * / } |
为了使污点分析有效,分析器需要知道哪些事件产生了污点值,以及污点如何通过不同的事件传播到其他符号值。这两项任务都可以在checker的帮助下进行扩展。
为了添加污染数据,添加任何适合捕获所需事件的检查器回调,并使用ProgramState的addTaint(…)方法。该方法有三个重写,允许向不同类型的符号值添加污点。
在当前环境中的表达式添加污染:
1 2 3 4 5 6 | LocationContext * LC = C.getLocationContext(); ProgramStateRef State = C.getState(); const Expr * E = / * Obtain an expression value of which is untrusted * / ; ProgramStateRef NewState = State - >addTaint(E,LC); if (NewState ! = State) / / avoid loops in the exploded graph C.addTransition(NewState); |
污染一个数据的值
1 2 3 4 5 6 7 | ProgramStateRef State = C.getState (); SVal V = / * Obtain a numeric symbol from an untrusted source * / ; if (SymbolRef Sym = V.getAsSymbol()) { ProgramStateRef NewState = State - >addTaint(Sym); if (NewState ! = State) C.addTransition (NewState); } |
向指向不受信任数据的指针添加污点
1 2 3 4 5 | ProgramStateRef State = C.getState (); SVal V = / * Obtain a symbolic location from an untrusted source * / ; ProgramStateRef NewState = State - >addTaint (V.getAsRegion()); if (NewState! = State ) C.addTransition (NewState); |
默认情况下,如果某个符号值被标记为污染,那么对其进行算术运算的结果也会被标记为污染。如果一个区域被污染,那么从该区域派生的所有值也被污染;然而,如果一个不相关的值被写入一个受污染的区域,那么这种值当然不再被认为是受污染的。此外,具有受污染符号元素索引的数组元素的区域也会自动受到污染。
路径敏感的checker不仅由分析器内核对其进行 符号执行,还积极参与程序行为的建模
检查器可能会向程序状态添加自己的特征,修改区域存储绑定或范围约束,或拆分状态,这意味着某个操作可能会有多个不同的结果,最终会使程序采用不同的执行路径
在爆炸图中,不能修改现有节点、程序点或程序状态;它们是不变的。然而,您可以做的是生成一个新的程序状态或一个新的辅助程序点(或两者),并利用CheckerContext对象向这个新状态或新点添加一个转换。
1 2 3 | ProgramStateRef State = C.getState (); State = modifyState(State); / / do stuff C.addTransition(State); |
如果要向多个备选节点添加转换
1 2 3 4 5 | ProgramStateRef State = C.getState (); ProgramStateRef State1 = modifyState(State); / / do stuff ProgramStateRef State2 = modifyState(State); / / do other stuff C.addTransition(State1); C.addTransition(State2); |
创建一个单一的转换序列,而不是多个并行的独立分支。在这种情况下,可以使用接受前置节点的重写方法
1 2 3 4 5 | ProgramStateRef State = C.getState (); State = modifyState1(State); / / do stuff ExplodedNode * N = C.addTransition(State); State = modifyState2(State,N); / / do other stuff C.addTransition(State2,N); |
根据约束范围拆分状态
ProgramState 的assume(...)返回一个新的程序状态和施加的假设来运行,如果不能满足该假设,则返回一个空的ProgramStateRef(因为它与已经施加的其他假设相矛盾。此外,不仅可以用bool来判断是否满足,还可以转换到新创建的状态。
例如,如果检查器需要通知分析器某个函数不能返回0,则可以假定其符号返回值为非零,并在调用该函数后添加到假定状态的转换
1 2 3 4 5 6 7 | SVal Val = Call.getReturnValue (); Optional<DefinedOrUnknownSVal> DVal = Val.getAs<DefinedOrUnknownSVal(); if (!DVal) return ; ProgramStateRef State = C.getState (); State = State - >assume ( * DVal ,true); C.addTransition(State); |
符号执行的基本理念是分裂状态
创建区域存储绑定 过将符号值绑定到某个位置来修改程序状态
典型的例子是手动模拟分析器无法建模的函数调用,比如无法获取某个函数的源代码, 仍然可以将对其规范的理解放入检查程序中,并尝试模拟其行为。
1 2 3 4 5 | ProgramStateRef State = C.getState(); SVal Loc = / * Obtain a location * / ; SVal Val = / * Obtain a value * / ; State = State - >bindLoc(Loc,Val); C.addTransition(State); |
使用程序状态特征
checkers 允许添加用户自定义的程序特征。这些特征存储在程序状态内部的一个特殊结构中,称为通用数据映射(generic data map,GDM)。
创建一个从对象的符号标识符到检查器看到的状态(unknown, live, deleted)的映射,并将此类映射存储在GDM中。
与程序状态一样,GDM的也是不变的,使用llvm不可变容器:llvm::ImmutableList、llvm::ImmutableSet、llvm::ImmutableMap
向程序状态中注入一个新的特征,您需要在checker代码的全局范围 使用四个预定义宏中的一个。
1 | REGISTER_TRAIT_WITH_PROGRAMSTATE(TraitName, Type ) |
使程序状态带有类型的特征。您可以通过调用state->get()来访问trait并在当前状态下获取其值,或者通过调用state->set(NewValue)来获取具有修改的trait值的新状态。此外TraitNameTy现在是Type的同义词。
1 | REGISTER_LIST_WITH_PROGRAMSTATE(ListName,ElementType) |
使程序状态具有ListNameTy类型的特征,这是ElementType类型元素的LLVM immutable list 。除了通过get<>()和set<>()处理整个列表外,还可以通过调用State->add(NewItem)轻松附加项目,或者通过调用State->contains<ListName>(Item)方法模板扫描列表中的项目。
1 | REGISTER_SET_WITH_PROGRAMSTATE(SetName,ElementType) |
使程序状态具有SetNameTy类型的特征,这是ElementType类型的LLVM immutable set。set trait支持add<>()和contains<>()类似于list trait,还可以从set中删除项(对于immutable list来说,这是一个过于繁重的操作),并通过调用state->remove<SetName>(Element)从集合中删除这些项来获得新的程序状态。
1 | REGISTER_MAP_WITH_PROGRAMSTATE(MapName,KeyType,ValueType) |
使程序状态具有MapNameTy类型的特性,这是从KeyType类型的对象到ValueType类型的对象的LLVMimmutable map。此特性支持remove<>(),不支持add<>(),还可以方便地重写set<>()和get<>():State->get<MapName>(key)方法查找key键的值,还可以调用State->set<MapName>(key,value)方法来获取一个新的程序状态 Key set to Value。
如果这些宏中的类型、ElementType、KeyType、ValueType中的任何一个不是整数类型,例如int或bool,或指针类型,那么对这些类型有一定的编译时要求,它们必须符合不可变容器的条件。 最重要的,他们需要提供一个Profile()方法,该方法允许他们作为 LLVM folding-set nodes
例如不能将std::string或者llvm::StringRef放到一个容器中 ,但是可以通过一个简单的封装:
1 2 3 4 5 6 7 8 9 10 11 | class StringWrapper { const std::string Str ; public : StringWrapper(const std::string &S) : Str (S) {} const std::string &get() const { return Str ; } void Profile ( llvm :: FoldingSetNodeID & ID ) const { ID .AddString( Str ); } bool operator = = ( const StringWrapper &RHS ) const { return Str = = RHS. Str ; } bool operator <( const StringWrapper &RHS ) const { return Str < RHS. Str ; } }; |
使用方法
1 2 3 4 5 6 7 8 9 10 11 12 | REGISTER_SET_WITH_PROGRAMSTATE(MyStringSet,StringWrapper) void MyChecker::checkPreCall(const CallEvent & Call , CheckerContext &C) { ProgramStateRef State = C.getState(); if (const IdentifierInfo * II = Call.getCalleeIdentifier()) { std::string Str = II - >getName(); State = State - >add<MyStringSet>(StringWrapper( Str )); C.addTransition(State); } if (State - >contains<MyStringSet>(StringWrapper( "main" ))) { / * ... * / } } |
如果要储存一个复杂的结构可以使用Profile(...)
1 2 3 4 | void MyStructure::Profile(llvm::FoldingSetNodeID & ID ) const { ID .AddPointer(Sym); Val.Profile ( ID ); } |
Path-sensitive checker callbacks
1 | void checkPreStmt(const T * S,CheckerContext &C) const; |
为任何AST语句类T定义的回调模板,每当分析引擎要分析类T的语句时都会触发该模板。在该回调中,可以从环境中获取语句T的子语句的值。
CFG上没有控制语句,(if、switch)要找这类分支语句,check::BranchCondition 在core.DivideZero中可以查到
1 2 3 4 5 6 7 | void DivZeroChecker::checkPreStmt (const BinaryOperator * B , CheckerContext &C ) const{ BinaryOperator::Opcode Op = B - >getOpcode(); / / 它观察二进制运算符的AST / * ... * / SVal Denom = C.getState() - >getSVal(B - >getRHS(),C.getLocationContext()); / / 从环境中获得分母的符号值 / * ... * / } |
1 | void checkPostStmt(const T * S ,CheckerContext &C) const ; |
这个回调不同的是,他的状态是已经建模完成时的,这个回调允许获取S本身的符号值 子表达式的值可能已经在环境中被删除
在unix.Malloc的check::PostStmt<T>检查leck或者double free ,这个check被订阅在check::PostStmt<CXXNewExpr>上,跟踪每次执行new,new[]时的符号值
1 | void checkPreCall(const CallEvent &Call , CheckerContext &C) const ; |
这个回调是check::PreStmt<CallExpr>的一个简便版本,他会在执行程序调用前触发,而不管是否使用过程间分析
不同于check::Precall的是你拥有CallEvent结构,可以轻易获取调用者的符号值,所有参数和C++隐式的this
在这个回调中,通常会尝试找出调用的函数。获取被调用方标识符的名称,并将其与给定字符串进行比较。然而,字符串比较是一项繁重的操作;存储我们想要的函数的标识符,然后比较标识符指针
alpha.unix.SimpleStreamChecker的check::PreCall
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | void SimpleStreamChecker::initIdentifierInfo(ASTContext &ACtx) const { if (IIfclose) return ; IIfclose = &ACtx.Idents.get( "fclose" ); } / / 从标识符表通过字符串名称查找标识符,然后存下来 void SimpleStreamChecker::checkPreCall (const CallEvent &Call , CheckerContext &C) const { initIdentifierInfo( C.getASTContext()); if (!Call.isGlobalCFunction()) return ; if (Call.getCalleeIdentifier()! = IIfclose ) return ; if ( Call.getNumArgs() ! = 1 ) return ; SymbolRef FileDesc = Call.getArgSVal( 0 ).getAsSymbol(); / * ... * / } |
check::PostCall
1 | void checkPreCall (const CallEvent &Call,CheckerContext &C)const ; |
与check::PreCall类似,这个是check::PostStmt<CallExpr>的快捷回调, 他在函数调用后触发 可以使用Call.getReturnValue()来获取函数返回值
alpha.unix.SimpleStreamChecker检查malloc和free
check::Location
1 2 | void checkLocation( SVal L , bool IsLoad,const Stmt * S,CheckerContext &C) const; |
每次被分析的程序寻址某个内存位置时,都会触发该回调,无论是从中读取值还是将值写入其中。 符号追L将被检查成投资的l-value(一片内存区域)
如果L是只读的,就设置IsLoad 如果想获得语句的入口,则需要查看他的父语句,可能会使用ParentMap,只要您想验证位置而不是值,也就是说,只要访问位置是您感兴趣的“事件”,就可以使用此回调。
在core,NullDereference中 有check::Location的例子
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 | void DereferenceChecker::checkLocation (SVal L , bool IsLoad , const Stmt * S , CheckerContext &C ) const { / / Check for dereference of an undefined value . if (L.isUndef()) { if (ExplodedNode * N = C.generateSink()) { / * ... * / } return ; } DefinedOrUnknownSVal Location = L.castAs<DefinedOrUnknownSVal>(); / / Check for null dereferences . if (!Location.getAs<Loc>()) return ; ProgramStateRef State = C.getState(); ProgramStateRef NotNullState, NullState; llvm::tie (NotNullState, NullState) = State - >assume(Location); if (NullState) { if (!NotNullState) { / * ... * / } / * ... * / } / * ... * / } |
首先检测未定义的位置值(捕获UndefinedVal),然后尝试在当前程序状态下假定位置为null或非null,并基于此做出决策。如果两种变体都有可能,检查程序还会分割程序状态,以便区分空位置和非空位置。
check::Bind
1 | void checkBind(SVal L,SVal V, const Stmt * S, CheckerContext &C) const; |
这个回调有点类似于check::Location。每当一个值绑定到一个位置,并且位置和值分别作为符号值L和V可用时,就会调用它。与check::Location不同,check::Bind不会在从位置加载时被调用;只有当由于程序的写入操作而出现区域绑定( region binding)时,才会在写入时调用它。
alpha.core.BoolAssignment 检查是否将0或1以外的值赋给布尔类型变量。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 | void BoolAssignmentChecker::checkBind (SVal L , SVal V , const Stmt * S , CheckerContext & C ) const { / / We are only interested in stores into Booleans . const TypedValueRegion * TR = dyn_cast_or_null<TypedValueRegion>(L.getAsRegion()); if (!TR) return ; QualType valTy = TR - >getValueType(); if (!isBooleanType(valTy)) return ; Optional<DefinedSVal> DV = V.getAs<DefinedSVal>(); if (! DV ) return ; ProgramStateRef State = C.getState(); SValBuilder & SVB = C.getSValBuilder(); DefinedSVal ZeroVal = SVB.makeIntVal( 0 ,valTy); SVal GreaterThanOrEqualToZeroVal = SVB.evalBinOp(State, BO_GE, * DV, ZeroVal, SVB.getConditionType()); / * ... * / DefinedSVal OneVal = SVB . makeIntVal ( 1 , valTy ); SValLessThanEqToOneVal = SVB.evalBinOp(State,BO_LE, * DV, OneVal, SVB.getConditionType()); / * ... * / } |
该检查器首先检查该位置,以查看该位置是否为布尔类型。并不是每个内存区域都有一个类型;例如,任何空指针都指向某个内存区域,但分析器无法假设存储在该区域中的值的类型。
包含显式已知类型值的区域是MemRegion的一个子类,称为TypedValueRegion。除非L指向的区域确实是布尔类型,否则检查程序将中止。
check::EndAnalysis
1 | void checkEndAnalysis(ExplodedGraph &G , BugReporter &BR , ExprEngine &Eng) const; |
每当路径敏感的分析器完成对某个函数代码体的分析时,这个回调函数就会触发一次。一个函数体已经完全被分析,分析重置并且调用check::EndAnalysis。因此,在分析单个翻译单元时,这个回调可能会被调用多次(在Checker的生命周期里会不止一次的运行,同样的在clang运行期间也不止一次)
每个代码体只触发一次,而不是对函数的每个分支都触发,这就是为什么CheckerContext在这个回调中不可用,并且您无法获得当前的ProgramState。相反,在这有这个爆炸图可以用。还可以访问BugReporter以抛出错误报告,还可以访问ExpreEngine对象(分析器引擎的唯一实例).
check::EndAnalysis在整个分析运行过程中收集统计数据时很有用。
在deadcode.UnreachableCode中用check::EndAnalysis分析死代码
1 2 3 4 5 6 7 8 9 10 11 | void UnreachableCodeChecker::checkEndAnalysis(ExplodedGraph &G , BugReporter &BR, ExprEngine & Eng ) const { / * ... * / if (Eng.hasWorkRemaining()) return ; / * ... * / for (ExplodedGraph::node_iterator I = G.nodes_begin(), E = G.nodes_end(); I ! = E ; + + I ) { / * ... * / } / * ... * / } |
这个路径敏感的checker通过解释引擎在函数的符号执行期间执行了哪些路径来查找死代码。有时函数会因为太复杂而被删除;在这种情况下,hasWorkRemaining()将返回true,并且检查器将避免跳转到结论。然后,检查程序通过遍历ExplodedGraph来查找到达了哪些CFG块。
1 2 3 4 5 6 7 8 9 | void bar ( int a, int b, int c){ if (b){} foo(a); if (c){} } void foo( int a) { if (a){} } |
check::EndFunction在顶层结构分析foo()触发了两次,在foo()被bar()调用时,触发了四次,在分析bar()的时候出发了8次
check::EndAnalysis会被foo()调用一次,bar()调用一次;它不会在bar()内部通过foo()调用。
可以订阅这个回调当你想要知道在分析结束时,找出函数上下文中还剩下什么
core.StackAddressEscape 该检查器遍历所有区域存储绑定,以便在函数结束时找到存储在全局变量中的局部变量指针。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 | void StackAddrEscapeChecker::checkEndFunction(CheckerContext &C)const { class CallBack : public StoreManager::BindingsHandler { private: CheckerContext &C; const StackFrameContext * CurSFC; public: SmallVector<std::pair<const MemRegion * ,const MemRegion * >, 10 > V; CallBack(CheckerContext &CC): C( CC ), CurSFC(CC.getLocationContext() - >getCurrentStackFrame()) {} bool HandleBinding(StoreManager &SMgr, Store Store, const MemRegion * Region , SVal Val ) { if (!isa<GlobalsSpaceRegion>(Region - >getMemorySpace())) return true ; const MemRegion * VR = Val.getAsRegion(); if (!VR ) return true ; / * ... * / if (const StackSpaceRegion * SSR = dyn_cast<StackSpaceRegion>(VR - >getMemorySpace())){ if (SSR - >getStackFrame() = = CurSFC ) V.push_back (std::make_pair(Region, VR)); } return true; } }; ProgramStateRef State = C.getState(); CallBack CB(C); C.getStoreManager().iterBindings(State - >getStore(),CB); / * ... * / } |
通过比较当前堆栈信息和堆栈区域的堆栈信息,检查器可以了解堆栈内存区域是属于相同的还是不同的堆栈。
check::BranchCondition
1 | void checkBranchCondition(const Stmt * S, CheckerContext &C)const; |
这个回调在程序分析期间发生的每个控制流分支上都被调用。不像check::PreStmt和check::PostStmt回调函数会针对每个CFG基本块中的每条语句触发,check::BranchCondition会针对每个CFG终止符触发。这些终止符可以包括if语句、循环条件,甚至逻辑操作||、和&&。
官方的core.uninitialized.Branch检查器用这个回调函数来查找依赖于未定义值的分支条件:
1 2 3 4 5 6 7 8 | void UndefBranchChecker::checkBranchCondition(const Stmt * S , CheckerContext &C ) const { SVal Val = C.getState() - >getSVal(S,C.getLocationContext()); if ( Val.isUndef ()) { / * ... * / } / * ... * / } |
check::LiveSymbols
1 | void checkLiveSymbols(ProgramStateRef State, SymbolReaper &SR) const ; |
这个回调允许checker手动管理符号表达式范围约束的垃圾收集。SymbolReaper对象负责符号的垃圾收集;您还可以访问这个回调中的当前程序状态。
大多数时候,除非您真的知道自己在做什么,则这个回调只对元数据符号(metadata symbols)有用。SymbolMetadata是一种特殊的符号表达式,它是由checker自己创建和管理的,这个回调函数是管理这些符号生命周期所必需的。
alpha.unix.cstring.OutOfBounds依赖于这个回调来将表示字符串长度的元数据符号标记为live的
1 2 3 4 5 6 7 8 9 10 11 | void CStringChecker::checkLiveSymbols(ProgramStateRef State, SymbolReaper &SR ) const { CStringLengthTy Entries = State - >get<CStringLength>(); for (CStringLengthTy::iterator I = Entries.begin(), E = Entries.end(); I ! = E ; + + I ) { SVal Len = I.getData(); for (SymExpr::symbol_iterator SI = Len .symbol_begin(), SE = Len .symbol_end(); SI ! = SE ; + + SI) SR.markInUse ( * SI); } } |
表示字符串长度的符号在字符串相同时处于活动状态(live),将空结束符处的值改为非空字符(或在其前面插入一个空字符)将改变c风格字符串的长度,表示旧长度的符号将不再需要,可以释放以进行垃圾收集。
这并不意味着符号会被立即删除;例如,只要它仍然存储在区域存储中的另一个变量中,它就不会被删除,即使被检查器释放。
check::DeadSymbols
1 | void checkDeadSymbols(SymbolReaper &SymReaper, CheckerContext &C) const; |
这个回调函数在符号被垃圾回收并且check::LiveSymbols没有阻止时被调用
在这个回调中,您的检查器将被通知,在进一步的分析中不会再次遇到该符号,并且您可以停止在您的检查特定的数据结构中跟踪它。这很可能是假设从程序状态的GDM中删除符号信息。
这也意味着符号所代表的值不再存储在被分析程序的任何地方;这个价值永远失去了。例如,如果该符号是在分析过程中分配但没有释放的内存地址,那么此类符号的死亡就是内存泄漏:一旦该符号死亡,程序就没有办法释放它。
alpha.unix.SimpleStreamChecker。它使用check::DeadSymbols来清理GDM和查找文件描述符泄漏
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | void SimpleStreamChecker::checkDeadSymbols(SymbolReaper &SymReaper, CheckerContext &C) const { ProgramStateRef State = C.getState(); SymbolVector LeakedStreams; StreamMapTy TrackedStreams = State - >get<StreamMap>(); for ( StreamMapTy::iterator I = TrackedStreams.begin(), E = TrackedStreams.end(); I ! = E ; + + I ) { SymbolRef Sym = I - >first ; bool IsSymDead = SymReaper.isDead(Sym); if (isLeaked(Sym,I - >second,IsSymDead,State)) LeakedStreams.push_back(Sym); if (IsSymDead) State = State - >remove<StreamMap>(Sym); } ExplodedNode * N = C.addTransition(State); reportLeaks(LeakedStreams,C,N); } |
check::RegionChanges
1 | bool wantsRegionChangeUpdate(ProgramStateRef State) const; |
1 2 3 4 5 | ProgramStateRef checkRegionChanges (ProgramStateRef State, const InvalidatedSymbols * Invalidated, ArrayRef<const MemRegion * > ExplicitRegions, ArrayRef<const MemRegion * > Regions, const CallEvent * Call) const; |
这对回调允许检查器监视区域存储中的所有更改。与check::Bind和check::Location不同,这个回调函数在失效时也会被调用,提供相关信息,比如可选的调用事件。
check::RegionChanges被调用的次数比check::Location或check::Bind更多,以确保对存储中的所有更改进行详尽的监控。这个回调函数调用的代价也很高,因为会显示出更改符号和区域的完整列表。
在alpha.unix.cstring.OutOfBounds中wantsRegionChangeUpdate()返回true,当checker跟踪至少一个C字符串的长度时。
1 2 3 4 5 6 | REGISTER_MAP_WITH_PROGRAMSTATE(CStringLength, const MemRegion * , SVal) / * ... * / bool CStringChecker::wantsRegionChangeUpdate(ProgramStateRef State)const{ CStringLengthTy Entries = State - >get<CStringLength>(); return !Entries.isEmpty(); } |
然后,检查器继续遍历Regions数组,以删除或更改其区域及其子区域(sub-regions)和超级区域(super-regions)。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 | ProgramStateRef CStringChecker::checkRegionChanges(ProgramStateRef State, const InvalidatedSymbols * Invalidated, ArrayRef<const MemRegion * > ExplicitRegions, ArrayRef<const MemRegion * > Regions, const CallEvent * Call) const{ llvm::SmallPtrSet<const MemRegion * , 8 >InvalidatedRegions; llvm::SmallPtrSet<const MemRegion * , 32 > SuperRegions; for (ArrayRef<const MemRegion * >::iterator I = Regions.begin(), E = Regions.end(); I! = E; + + I){ const MemRegion * MR = * I; InvalidatedRegions.insert(MR); SuperRegions.insert(MR); while (const SubRegion * SR = dyn_cast<SubRegion>(MR)) { MR = SR - >getSuperRegion(); SuperRegions.insert(MR); } } CStringLengthTy::Factory &F = State - >get_context<CStringLength>(); for (CStringLengthTy::iterator I = Entries.begin(), E = Entries.end(); I ! = E ; + + I) { const MemRegion * MR = I.getKey(); if (SuperRegions.count(MR)) { Entries = F.remove(Entries,MR); continue ; } const MemRegion * Super = MR ; while (const SubRegion * SR = dyn_cast<SubRegion>( Super )){ Super = SR - >getSuperRegion(); if (InvalidatedRegions.count( Super )){ Entries = F.remove(Entries,MR); break ; } } } return State - > set <CStringLength>(Entries); } |
为了获得更好的性能,无效区域的超级区域(super-regions of invalidated regions)存储在llvm::SmallPtrSet中,这当然与子区域有关。还要注意检查器如何避免为每个区域删除创建多个中间程序状态,直接处理immutable map。
check::PointerEscape
1 2 3 4 | ProgramStateRef checkPointerEscape(ProgramStateRef State, const InvalidatedSymbols &Escaped, const CallEvent * Call, PointerEscapeKind Kind) const; |
当一个指针值被赋给一个全局变量,或者传递给一个分析器不能建模的函数时,指针就被称为“转义”。这样的指针不能再被可靠地跟踪了。
当指针转义时,会调用check::PointerEscape,以便通知检查程序转义它们感兴趣的指针。如果指针在失效期间发生转义,则提供关于调用事件的信息。
类似于check::DeadSymbols检测资源泄漏,check::PointerEscape可以用来消除此类检查中的误报:一个转义的指针可以在我们不知道的情况下被释放,或者超出它的值可能被改变了(value beyond it may have been changed)。
alpha.unix.SimpleStreamChecker 这个回调函数用于查找转义的文件描述符
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | ProgramStateRef SimpleStreamChecker::checkPointerEscape(ProgramStateRef State, const InvalidatedSymbols &Escaped, const CallEvent * Call, PointerEscapeKind Kind) const{ if (Kind = = PSK_DirectEscapeOnCall && guaranteedNotToCloseFile( * Call)){ return State; } for (InvalidatedSymbols::const_iterator I = Escaped.begin(), E = Escaped.end(); I ! = E; + + I) { SymbolRef Sym = * I; State = State - >remove<StreamMap>(Sym); } return State; } eval ::Assume ProgramStateRef evalAssume(ProgramStateRef State, SVal Cond, bool Assumption) const; |
每当程序状态中出现一个新的范围约束时,这个回调函数就会触发。通过这个回调,检查器可以在它们内部存储的符号被施加上新的约束时得到通知,或者在让他们帮助分析器“评估”假设,以及约束管理器,修改程序状态时。在使用这个回调之前,看看check::BranchCondition是否足够满足你的目的。
例如unix.Malloc使用这个回调来查找指向已分配内存的符号是否被约束为空指针值。一旦符号分解为具体的值,再去追踪这样的符号就没有意义了:
1 2 3 4 5 6 7 8 9 10 11 | ProgramStateRef MallocChecker::evalAssume(ProgramStateRef State, SVal Cond, bool Assumption) const{ RegionStateTy RS = State - >get<RegionState>(); for (RegionStateTy::iterator I = RS.begin(), E = RS.end(); I ! = E; + + I){ ConstraintManager &CMgr = State - >getConstraintManager(); ConditionTruthValAllocFailed = CMgr.isNull(State, I.getKey()); if (AllocFailed.isConstrainedTrue()) State = State - >remove<RegionState>(I.getKey()); } / * ... * / return State ; } |
eval::Call
1 | bool evalCall(const CallExpr * CE, CheckerContext &C) const; |
这个检查器回调允许检查器建模一个函数调用,覆盖通常的过程间分析机制。当函数的源代码不能用于分析时,它对于建模领域特定的库函数(第三方库 domain-specific)可能是有用的。
如果检查器已经成功地对函数调用建模,回调函数应该返回true,如果检查器更好地依赖于分析器核心或其他检查器来评估此调用,则返回false。
这个回调是不鼓励使用的,因为只有一个检查器可以评估任何调用事件(only one checker may evaluate any call event);如果两个或更多的检查程序(可能是由不同的人开发的)偶然评估了相同的函数,分析器的行为是未定义的。因此,如果可能的话,应该考虑check::PreCall和check::PostCall,而且在大多数情况下,它们足够灵活,可以模拟调用对程序状态的影响。
官方的core. builtinfunctions检查器使用这个回调函数来模拟某些编译器内置函数的行为
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | bool BuiltinFunctionChecker::evalCall(const CallExpr * CE, CheckerContext &C) const{ const FunctionDecl * FD = C.getCalleeDecl(CE); if (!FD) return false; ProgramStateRef State = C.getState(); const LocationContext * LCtx = C.getLocationContext(); switch(FD - >getBuiltinID()) { / * ... * / case Builtin::BI__builtin_addressof:{ assert (CE - >arg_begin() ! = CE - >arg_end()); SVal X = State - >getSVal( * (CE - >arg_begin()),LCtx); C.addTransition(State - >BindExpr(CE, LCtx,X)); return true; } / * ... * / } / * ... * / } |
Implementing bug reporter visitors
通常,BugReporter在解释如何准确发现路径敏感的bug方面做得相当好,它沿着符号执行路径向用户显示所有事件。但是,有时您可能希望它标记和显示其他事件。
例如,当报告一个doulefree的bug时,您可能希望让用户知道第一个bug何时出现。在本例中,您需要实现一个bug报告访问器,它将以ExplodedNode列表的形式从头到尾遍历bug报告路径,并在此过程中注入路径诊断片段。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | class MyVisitor : public BugReporterVisitorImpl<MyVisitor> { void Profile (llvm::FoldingSetNodeID & ID ) const { / * ... * / } PathDiagnosticPiece * VisitNode (const ExplodedNode * N, const ExplodedNode * PrevN, BugReporterContext &BRC, BugReport &BR){ / * ... * / if (const Stmt * S = / * Obtain a statement for diagnostic * / ) { PathDiagnosticLocationPos(S ,BRC.getSourceManager(), N - >getLocationContext()); return new PathDiagnosticEventPiece(Pos, "Message" ); } return NULL; } }; |
需要实现Profile(…)方法,因为错误访问器将存储在路径诊断回调的LLVM折叠集(folding set)中。然后你需要实现VisitNode(…)。它应该标识感兴趣的节点,为它构造一个路径诊断并返回它,或者如果应该跳过该节点,则返回一个空指针。
通过程序点中的语句来标识节点是很常见的。在这种情况下,PathDiagnosticLocation类的静态辅助方法getStmt(…)应该是有用的:
1 | const Stmt * S = PathDiagnosticLocation::getStmt(N); |
理解过程间分析
当调用的内联和检查端计算都失败时,分析程序退回到保守计算。这样的评估相对简单,因为没有任何东西真正得到评估。相反,分析器需要删除所有以前已知且可能已经失效的信息。删除这些信息的过程称为无效。失效主要由区域存储处理。函数可以将未知值写入所有可用的位置,比如作为参数传递给它的全局变量或区域。为了表示这些值,我们创建了新的、无约束的符号表达式SymbolConjured,并将其绑定到区域存储区中无效的区域。
有两个检查器回调,让你在检查器中捕获失效事件并采取行动:
check::PointerEscape 允许您处理将指针符号传递给保守计算函数的事件
check::RegionChanges 让您观察无效的全部后果,包括无效区域的列表。
Inlining and stack frames
对分析器来说,inline函数调用是一个繁重的操作。每个函数调用需要建模的一次又一次的在每一个新的背景下,和上下文相关的爆炸图(这可能不同的上下文变量的值,以及缺乏分支不可到达的上下文中)的被成为爆炸图的子图指出当前的分析。
发生内联需要多个先决条件,包括:
被调用函数体的源代码需要可用
任何检查器都不应该通过eval:: call对函数调用求值
如果对被调用者的分析达到最大爆炸节点限制,则被调用者将永远不会内联,而是保守地评估
即使支持递归,也只会执行有限数量的嵌套递归调用
每当分析器内联一个函数并下降到其中时,就会创建一个新的StackFrameContext。这个结构是一种LocationContext,它描述在过程间分析期间下降到函数的位置。你可以通过CheckerContext的getStackFrame()方法获取当前堆栈帧。通常你只需要知道如果我们在一个内联函数中或者在顶帧中;在这种情况下,可以使用CheckerContext的一个方便的inTopFrame()方法。
需要使用堆栈帧的常见情况之一是check::EndFunction checker回调。这个回调会在函数的每次返回时触发,但是您需要查看它是分析的结束,还是仅仅是堆栈帧中的弹出。
您可能希望在检查器逻辑中依赖符号值层次结构。表示函数参数值的符号值VarRegion类型用SymbolRegionValue,用于decl的ParmVarDecl类型。
The symbolic value hierarchy
符号值是CSA用于描述在程序符号执行期间遇到的已知和未知值的符号。CSA有非常复杂的符号值层次结构。
表示各种符号值的基本类是SVal类。它有不同的子类,代表不同种类的符号值。还有两个辅助类MemRegion和SymExpr,分别专门处理内存区域和符号表达式。
SymExpr类的对象通常也被称为符号,代表未知的数值;如果在分析过程中已知一个值,则称之为具体值concrete value。MemRegion对象——“regions”——用于两个目的:作为分析器内存模型中区域存储绑定的位置,以及用于表示指针值。
这三个类之间有很大的联系。例如,区域可以“基于”符号和具体值(例如,指针符号指向的区域,或具有已知或未知索引的数组元素的区域),符号可以“基于”区域(例如,定义为区域初始值的符号)。
此外,SVal子类分为两大类:左值(l-values)的Loc和右值(r-values)的NonLoc
只有约束符号才有意义;具体的值是已知的,进一步给它们分配整数范围约束是没有意义的,而且在编译时内存区域地址从来没有真正定义过。 区域存储通过为区域指定任意值来工作也是很自然的 环境通过为AST表达式指定任意值来工作。
这张表的第5行可能会让你感到惊讶,正如上面我们已经讨论了受污染的内存区域,一些处理受污染内存区域的方法会接受任意的SVal。然而,当污点分析与符号以外的值一起工作时,它只是试图找到其中的符号。
Constructing symbolic values
SValBuilder类提供了构造SVal对象的方法。它允许构造各种SVal和各种SymExpr(必要时将后者表示为SVal)。它还允许对符号值进行运算。但是,要构建内存区域,应该使用MemRegionManager对象。有时,能够构造子区域(例如,具有已知声明的结构区域的字段区域,以便稍后获得字段值)是有用的。
几乎不用不到构建一个SymExpr。 当您想要构造符号时,包括在某种eval::Call期间创建某种符号,以及在检查器使用此机制时构造符号元数据(SymbolMetadata)。 有几种罕见的情况。大多数时候,你会从环境或地区商店收到所有必要的符号,甚至几乎不用关心它们的种类。
在任何情况下,都应该使用SValBuilder的方法,而不是直接访问SymbolManager对象,来构建各种SymExpr。
如果请求的符号是整型的,这些方法将返回一个包含符号的nonloc::SymbolVal;如果请求的是指针类型,这些方法将返回一个包含符号区域的loc::MemRegionVal
在这两种情况下,都可以调用生成的SVal的getAsSymbol()方法来获取SymExpr本身。
Memory model of the analyzer
MemRegion是内存的一部分。
当它存储在指针类型的SVal中时,它表示段的第一个字节的地址;但是,您仍然应该将MemRegion对象想象为承载了关于整个段的信息。
SVal类的getAsRegion()方法适用于以下SVal类型
loc::MemRegionVal 一种指针值,被描述为给定区域的第一个字节的地址。
nonloc::LocAsInteger 一个类似的指针值,只存储在一个整数中。这种SVal表示指向整数强制转换的指针的结果。
一些存储区域是其他区域的子区域。 子区域是段内的子段(A sub-region is a sub-segment inside a segment.)。Sub-regions继承于类SubRegion。 每个子区域都有一个length (“extent”),可以通过SubRegion的getExtent(…)方法获得,范围可以是具体的,也可以是象征性的。
其他区域称为内存空间(memory spaces),不属于任何其他区域。每个子区域(SubRegion)正好有一个通过getSuperRegion()方法获得的直接超区域(super-region)。 以存储空间作为其直接超级区域的存储区域称为基区域。
如果一个区域既不是内存空间也不是基区, 那么在其超级区域链的末端必有一个基区。
有一个单独的类家族用于表示基本区域:通过只查看区域的类,可以确定它是内存空间内的基本区域,还是位于另一个基本区域内。
可以使用getMemorySpace()方法获取该区域所属的内存空间,并使用getBaseRegion()获取任何子区域的基本区域。
Base regions — the direct sub-regions of memory spaces — can be either typed or untyped
有类型区域是保存已知类型值的区域。 无类型化区域是具有未知类型值的区域,即使你可能大致知道存储在那里的内容或其来源。
1 2 3 4 5 6 7 8 9 10 11 12 13 | struct A { int x,y; }; struct B: A { int u,v; }; struct C { int t; B * b; }; void foo (C c) { c.b[ 5 ].y ; / / < - - that } |
如果你在分析挡住使用dump()到stderr你会看到
FieldRegion for declaration of member variable y,
inside CXXBaseRegion for declaration of class A,
inside ElementRegion for element number 5 of type B,
inside SymbolicRegion for the pointer symbol of SymbolRegionValue kind,
which represents the initial value of:
FieldRegion for declaration of member variable b,
VarRegion for declaration of a local variable c.
Memory spaces
1 2 3 4 5 6 7 8 9 10 11 12 13 | 内存空间继承自MemSpaceRegion类。大多数内存空间都是“单例的”(“singletons”) GlobalsSpaceRegion 四个不同内存空间的基类: NonStaticGlobalSpaceRegion 所有非静态全局变量的单一内存空间,分为三个 GlobalImmutableSpaceRegion 由不能修改的全局变量组成 GlobalSystemSpaceRegion 其中包括最有可能仅由系统调用修改的变量,例如errno GlobalInternalSpaceRegion 由其他全局变量组成 StaticGlobalSpaceRegion 所有静态全局变量的内存空间 HeapSpaceRegion 堆上分配的所有区域 StackSpaceRegion 两个不同内存空间的基类 StackArgumentsSpaceRegion 函数调用参数的内存空间 StackLocalsSpaceRegion 局部变量的存储空间 与其他内存空间不同,可能有多个StackSpaceRegion实例——每个StackFrameContext一个。 UnknownSpaceRegion 当分析器不知道该区域实际存储在哪里时。 |
内存空间很重要,因为如果区域位于不同的内存空间中,即使这些区域的所有其他特征都相同,它们也会被认为是不同的。例如,函数参数变量在不同调用中的区域是不同的,因为它们的内存空间由不同的堆栈帧上下文定义,即使变量声明是相同的。
Untyped base regions
有三种类型的非类型区域
AllocaRegion 通过调用标准C库的alloca()函数在堆栈上分配的区域。此区域是非类型化的,因为此函数分配原始数据。
AllocareRegion始终位于StackLocalsSpaceRegion中
SymbolicRegion
指针指向的区域,其值是一个符号表达式。这个区域是非类型化的,因为指针可以在C中自由映射,并且不能确保它指向的数据类型与指针类型匹配。