Clangの静的解析コードであるCheckerのひとつ、 MallocOverflowSecurityCheckerを試してみる。
1. Checkerの実行方法
どんなCheckerがあるかを確認するには-analyzer-checker-helpを使用する。
$ clang -cc1 -analyzer-checker-help OVERVIEW: Clang Static Analyzer Checkers List USAGE: -analyzer-checker <CHECKER or PACKAGE,...> CHECKERS: <snip> alpha.security.MallocOverflow Check for overflows in the arguments to malloc() <snip>
今回試すMallocOverflowSecurityCheckerを-analyzer-checkerで指定する。
$ clang -cc1 -analyzer-checker=alpha.security.MallocOverflow \ -analyze <target>.c
2. MallocOverflowSecurityCheckerが対象とする対象
MallocOverflowSecurityChecker.cppに記載されているコメントによれば、以 下の環境と手順で発生するヒープ領域操作を対象としている。
2.1. 環境
* 外部から入力可能なunsigned int nがある * 'malloc (n * 4)'のようなヒープ領域確保がある
2.2. 手順
* 攻撃者はunsigned int nを'UINT_MAX/4 + 2'にする * unsigned intで値が丸められ8Byteしかヒープ領域が確保されない * 8Byteより後のヒープ領域に不正な値を書き込まれる
よって、malloc(sizeof(int) * n)などの呼び出しにおいて、nが不正な値でヒー プ領域操作の問題があるかどうかを検出する。
3. 実装
ASTCodeBodyを継承している。
class MallocOverflowSecurityChecker : public Checker<check::ASTCodeBody> {
<snip>
void checkASTCodeBody(const Decl *D, AnalysisManager &mgr,
BugReporter &BR) const;
ASTCodeBodyのドキュメント。
/// rief Check every declaration in the AST. /// /// An AST traversal callback, which should only be used when the checker is /// not path sensitive. It will be called for every Declaration in the AST and /// can be specialized to only be called on subclasses of Decl, for example, /// FunctionDecl. /// /// check::ASTDecl<FunctionDecl>
path sensitiveでない（前後関係やif文の分岐などによる遷移を見ない） Checkerに使用する。以下、ソースコードに#でコメントを記載していく。
3.1. checkASTCodeBody
ASTから得られるCFGを辿り、mallocの引数をCheckMallocArgumentで確認し、 問題がある場合はベクタに積んでいく。ベクタをOutputPossibleOverflowsで 精査し、問題がある場合はwarning出力する。
void MallocOverflowSecurityChecker::checkASTCodeBody(const Decl *D,
AnalysisManager &mgr,
BugReporter &BR) const {
# CFGを取得する（ASTは関数単位なので、CFGも関数単位になる）
CFG *cfg = mgr.getCFG(D);
if (!cfg)
return;
// A list of variables referenced in possibly overflowing malloc operands.
# ベクタの定義
SmallVector<MallocOverflowCheck, 2> PossibleMallocOverflows;
# CFGを辿る
for (CFG::iterator it = cfg->begin(), ei = cfg->end(); it != ei; ++it) {
CFGBlock *block = *it;
# CFGBlockを辿る
for (CFGBlock::iterator bi = block->begin(), be = block->end();
bi != be; ++bi) {
if (Optional<CFGStmt> CS = bi->getAs<CFGStmt>()) {
# 関数呼び出しかどうか
if (const CallExpr *TheCall = dyn_cast<CallExpr>(CS->getStmt())) {
// Get the callee.
const FunctionDecl *FD = TheCall->getDirectCallee();
if (!FD)
return;
// Get the name of the callee. If it's a builtin, strip off the prefix.
IdentifierInfo *FnInfo = FD->getIdentifier();
if (!FnInfo)
return;
# 関数がmalloc/_MALLOCかどうか
if (FnInfo->isStr ("malloc") || FnInfo->isStr ("_MALLOC")) {
# 引数が一つか
if (TheCall->getNumArgs() == 1)
# mallocの引数を確認
CheckMallocArgument(PossibleMallocOverflows, TheCall->getArg(0),
mgr.getASTContext());
}
}
}
}
}
# EvaluatedExprVisitorを用いて、ベクタに積まれた二項演算子と
# non-const valueを精査し、問題がある場合はwarningを出力する
OutputPossibleOverflows(PossibleMallocOverflows, D, BR, mgr);
}
CFGは以下の方法でdumpできる。
$ cat hello.c
#include <stdio.h>
int main(int argc, char *argv[])
{
printf("Hello, world\n");
if (argc < 1)
{
fprintf(stdout, "0");
}
else if (argc < 2)
{
fprintf(stdout, "1");
}
else
{
fprintf(stdout, "%d", argc);
}
puts("");
return 0;
}
$ clang -cc1 -analyzer-checker=debug.ViewCFG -analyze hello.c
Writing '/<path-to-cfg>/CFG-533571.dot'... done.
if文による分岐毎のブロックがツリー構造で出力される。出力したCFGは Graphvizで閲覧できる。
3.2. CheckMallocArgument
malloc引数を確認する処理。malloc(non-const value * const value)のパター ンを見つけてnon-const valueと二項演算子をベクタに積む。
void MallocOverflowSecurityChecker::CheckMallocArgument(
SmallVectorImpl<MallocOverflowCheck> &PossibleMallocOverflows,
const Expr *TheArgument,
ASTContext &Context) const {
/* Look for a linear combination with a single variable, and at least
one multiplication.
Reject anything that applies to the variable: an explicit cast,
conditional expression, an operation that could reduce the range
of the result, or anything too complicated :-). */
const Expr * e = TheArgument;
const BinaryOperator * mulop = NULL;
# 二項演算子を再帰的に辿る為にループを用いる、例えばa * b + cなどの
# 場合に根が*、ノードに+を持つ二項演算子が設定されている
for (;;) {
e = e->IgnoreParenImpCasts();
# 二項演算子の場合
if (isa<BinaryOperator>(e)) {
const BinaryOperator * binop = dyn_cast<BinaryOperator>(e);
BinaryOperatorKind opc = binop->getOpcode();
// TODO: ignore multiplications by 1, reject if multiplied by 0.
# malloc(lhs * rhs)かどうか（malloc(lhs * rhs + a)の場合は演算子
# の順序で*が大元の二項演算子となる）
if (mulop == NULL && opc == BO_Mul)
mulop = binop;
# 比較演算子や等価演算子がある場合はやめる
if (opc != BO_Mul && opc != BO_Add && opc != BO_Sub && opc != BO_Shl)
return;
const Expr *lhs = binop->getLHS();
const Expr *rhs = binop->getRHS();
# isEvaluatbleはconstな場合にtrueになる、右辺が定数の場合はfor文
# の先頭に戻り、左辺を辿っていく
if (rhs->isEvaluatable(Context))
e = lhs;
# malloc(lhs + rhs)あるいは malloc(lhs * rhs)で、かつlhsがconst
# な変数の場合
else if ((opc == BO_Add || opc == BO_Mul)
&& lhs->isEvaluatable(Context))
e = rhs;
# constでない変数同士の場合
else
return;
}
# 変数/メンバ変数の場合
else if (isa<DeclRefExpr>(e) || isa<MemberExpr>(e))
# これ以上展開する必要はないのでbreak
break;
# 二項演算子/変数/メンバでない場合（例えば関数呼び出し）
else
# チェックをやめる（諦める）
return;
}
# malloc(const value * ...)があったかどうか
if (mulop == NULL)
return;
// We've found the right structure of malloc argument, now save
// the data so when the body of the function is completely available
// we can check for comparisons.
// TODO: Could push this into the innermost scope where 'e' is
// defined, rather than the whole function.
# ベクタに二項演算子とnon-const valueを積む
PossibleMallocOverflows.push_back(MallocOverflowCheck(mulop, e));
}
3.3. OutputPossibleOverflows
ベクタに積まれたnon-const valueが比較演算子でレンジチェックされている かを確認する処理。チェックされていない場合は二項演算子にwarningを出力 する。
void MallocOverflowSecurityChecker::OutputPossibleOverflows(
SmallVectorImpl<MallocOverflowCheck> &PossibleMallocOverflows,
const Decl *D, BugReporter &BR, AnalysisManager &mgr) const {
// By far the most common case: nothing to check.
# ベクタが空かどうか
if (PossibleMallocOverflows.empty())
return;
// Delete any possible overflows which have a comparison.
# EvaluatedExprVisitorを用いてベクタの中身を精査する、
# malloc(non-const value * const value)の場合にnon-const valueの値が比
# 較演算子でチェックされている場合は、warning対象から外す（ベクタに積
# まれているDecRefExprの変数定義と比較演算子の左辺/右辺の変数定義を比
# 較する）、ただし0をもちいて比較している場合は対象から外す、unsigned
# int > 0などは無意味な為
# またfor文/while文/Do文の条件式での比較は見ない
CheckOverflowOps c(PossibleMallocOverflows, BR.getContext());
# ASTの根から再帰的に辿り、比較の二項演算子を見つけて処理をする（対
# 象となる二項演算子は*, +, -, <<ではない）
c.Visit(mgr.getAnalysisDeclContext(D)->getBody());
// Output warnings for all overflows that are left.
# ベクタを辿る
for (CheckOverflowOps::theVecType::iterator
i = PossibleMallocOverflows.begin(),
e = PossibleMallocOverflows.end();
i != e;
++i) {
# warningを出力する
BR.EmitBasicReport(D, "malloc() size overflow", categories::UnixAPI,
"the computation of the size of the memory allocation may overflow",
PathDiagnosticLocation::createOperatorLoc(i->mulop,
BR.getSourceManager()),
i->mulop->getSourceRange());
}
}
EvaluatedExprVisitorはVisit()にあたえられたStmtを再帰的に辿っていく。 Stmt/Exprの種類によって、Visit##Stmtが呼ばれる。これらは下位のStmtや引 数のStmtを辿るように定義されている。EvaluatedExprVisitorを継承したクラ スでVisit##Stmtを独自定義することで、任意の処理を追加できる（その処理 の中でスーパークラスのVisit##Stmtを呼べば再帰処理は続く）。
4. 実験
malloc(size * mul)というmalloc呼び出しの検出を試す。mulは常にconstで、 sizeをレンジチェックするかどうかで5パターン試す。
4.1. レンジチェックが正常な場合
sizeが一定値以上の場合はreturnする。
$ cat malloc1.c
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
int main(void)
{
unsigned int size = UINT_MAX / 4 + 2;
char *buffer;
if (size >= 10)
return 1;
buffer = (char *) malloc(4 * size);
if (buffer == NULL)
return 1;
free(buffer);
return 0;
}
$ clang -cc1 -analyzer-checker=alpha.security.MallocOverflow -analyze malloc1.c
$ # warningは出力されない
4.2. レンジチェックがない場合
sizeのレンジチェックがない。
$ cat malloc2.c
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
int main(void)
{
unsigned int size = UINT_MAX / 4 + 2;
char *buffer;
buffer = (char *) malloc(4 * size);
if (buffer == NULL)
return 1;
free(buffer);
return 0;
}
$ clang -cc1 -analyzer-checker=alpha.security.MallocOverflow -analyze malloc2.c
malloc2.c:10:30: warning: the computation of the size of the memory allocation may overflow
buffer = (char *) malloc(4 * size);
~~^~~~~~
1 warning generated.
$ # 期待通りwarningが出力される。
4.3. for文でレンジチェック
for文でレンジチェックするケースはないと思うが。
$ cat malloc3.c
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
int main(void)
{
unsigned int size;
char *buffer;
for (size = 0; size < 10; size++)
;
buffer = (char *) malloc(4 * size);
if (buffer == NULL)
return 1;
free(buffer);
return 0;
}
$ clang -cc1 -analyzer-checker=alpha.security.MallocOverflow -analyze malloc3.c
malloc3.c:13:30: warning: the computation of the size of the memory allocation may overflow
buffer = (char *) malloc(4 * size);
~~^~~~~~
1 warning generated.
$ # for文のレンジチェックはレンジチェックとして扱われない
4.4. レンジチェックが不正な場合
sizeが10より小さい場合はreturnする。malloc引数の大きさを計算していない ことが分かる（静的解析では計算が困難であるけれどできればしたいところ）。
$ cat malloc4.c
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
int main(void)
{
unsigned int size = UINT_MAX / 4 + 2;
char *buffer;
if (size < 10)
return 1;
buffer = (char *) malloc(4 * size);
if (buffer == NULL)
return 1;
free(buffer);
return 0;
}
$ clang -cc1 -analyzer-checker=alpha.security.MallocOverflow -analyze malloc4.c
$ # warning出力されない
4.5. レンジチェックが後にある場合
sizeが10以上の場合にreturnするが、malloc確保よりも後にある場合。path sensitiveなCheckerでない故に前後関係を把握していない。ただし、レンジ チェックがmallocよりも後にあること自体がおかしいので、検出しなくても良 いと思う。
$ cat malloc5.c
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
int main(void)
{
unsigned int size = UINT_MAX / 4 + 2;
char *buffer;
buffer = (char *) malloc(4 * size);
if (buffer == NULL)
return 1;
if (size >= 10) {
free(buffer);
return 1;
}
free(buffer);
return 0;
}
$ clang -cc1 -analyzer-checker=alpha.security.MallocOverflow -analyze malloc4.c
$ # warning出力されない
5. まとめ
path sensitiveなCheckerではないので、それほど複雑な処理にはなっていな い。パターンマッチングに近い。いくつか期待値通りにならないコードも紹介 したが、ほぼありえないコードなので問題ではないだろう。const value * non-const valueがオーバフローするかどうかの計算もできると検出精度が上 がると思う。
ASTを辿るのにCFGを用いる方法とEvaluatedExprVisitorを用いる方法が実装さ れているので参考になる。
