105a2338f7ba1c8a0136e120502f80a38cf0e9fd3Zhongxing Xu//=== VLASizeChecker.cpp - Undefined dereference checker --------*- C++ -*-===// 205a2338f7ba1c8a0136e120502f80a38cf0e9fd3Zhongxing Xu// 305a2338f7ba1c8a0136e120502f80a38cf0e9fd3Zhongxing Xu// The LLVM Compiler Infrastructure 405a2338f7ba1c8a0136e120502f80a38cf0e9fd3Zhongxing Xu// 505a2338f7ba1c8a0136e120502f80a38cf0e9fd3Zhongxing Xu// This file is distributed under the University of Illinois Open Source 605a2338f7ba1c8a0136e120502f80a38cf0e9fd3Zhongxing Xu// License. See LICENSE.TXT for details. 705a2338f7ba1c8a0136e120502f80a38cf0e9fd3Zhongxing Xu// 805a2338f7ba1c8a0136e120502f80a38cf0e9fd3Zhongxing Xu//===----------------------------------------------------------------------===// 905a2338f7ba1c8a0136e120502f80a38cf0e9fd3Zhongxing Xu// 10d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis// This defines VLASizeChecker, a builtin check in ExprEngine that 1105a2338f7ba1c8a0136e120502f80a38cf0e9fd3Zhongxing Xu// performs checks for declaration of VLA of undefined or zero size. 12b2242d1b6fe4ae073361e6d8f3db751c95159ca5Jordy Rose// In addition, VLASizeChecker is responsible for defining the extent 13b2242d1b6fe4ae073361e6d8f3db751c95159ca5Jordy Rose// of the MemRegion that represents a VLA. 1405a2338f7ba1c8a0136e120502f80a38cf0e9fd3Zhongxing Xu// 1505a2338f7ba1c8a0136e120502f80a38cf0e9fd3Zhongxing Xu//===----------------------------------------------------------------------===// 1605a2338f7ba1c8a0136e120502f80a38cf0e9fd3Zhongxing Xu 173ce2b48461115af047ee1e957e1892af255bf120Argyrios Kyrtzidis#include "ClangSACheckers.h" 1855fc873017f10f6f566b182b70f6fc22aefa3464Chandler Carruth#include "clang/AST/CharUnits.h" 1955fc873017f10f6f566b182b70f6fc22aefa3464Chandler Carruth#include "clang/StaticAnalyzer/Core/BugReporter/BugType.h" 20ec8605f1d7ec846dbf51047bfd5c56d32d1ff91cArgyrios Kyrtzidis#include "clang/StaticAnalyzer/Core/Checker.h" 213ce2b48461115af047ee1e957e1892af255bf120Argyrios Kyrtzidis#include "clang/StaticAnalyzer/Core/CheckerManager.h" 223ce2b48461115af047ee1e957e1892af255bf120Argyrios Kyrtzidis#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h" 2300bd44d5677783527d7517c1ffe45e4d75a0f56fBenjamin Kramer#include "llvm/ADT/STLExtras.h" 2455fc873017f10f6f566b182b70f6fc22aefa3464Chandler Carruth#include "llvm/ADT/SmallString.h" 25a93d0f280693b8418bc88cf7a8c93325f7fcf4c6Benjamin Kramer#include "llvm/Support/raw_ostream.h" 2605a2338f7ba1c8a0136e120502f80a38cf0e9fd3Zhongxing Xu 2705a2338f7ba1c8a0136e120502f80a38cf0e9fd3Zhongxing Xuusing namespace clang; 289ef6537a894c33003359b1f9b9676e9178e028b7Ted Kremenekusing namespace ento; 2905a2338f7ba1c8a0136e120502f80a38cf0e9fd3Zhongxing Xu 3084b3595729d249d89b8b67a547e0992797e19793Ted Kremeneknamespace { 31ec8605f1d7ec846dbf51047bfd5c56d32d1ff91cArgyrios Kyrtzidisclass VLASizeChecker : public Checker< check::PreStmt<DeclStmt> > { 32651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines mutable std::unique_ptr<BugType> BT; 333bfd6d701ee297bd062967e11400daae51b36eb2Anna Zaks enum VLASize_Kind { VLA_Garbage, VLA_Zero, VLA_Tainted }; 343bfd6d701ee297bd062967e11400daae51b36eb2Anna Zaks 353bfd6d701ee297bd062967e11400daae51b36eb2Anna Zaks void reportBug(VLASize_Kind Kind, 363bfd6d701ee297bd062967e11400daae51b36eb2Anna Zaks const Expr *SizeE, 378bef8238181a30e52dea380789a7e2d760eac532Ted Kremenek ProgramStateRef State, 383bfd6d701ee297bd062967e11400daae51b36eb2Anna Zaks CheckerContext &C) const; 3984b3595729d249d89b8b67a547e0992797e19793Ted Kremenekpublic: 403ce2b48461115af047ee1e957e1892af255bf120Argyrios Kyrtzidis void checkPreStmt(const DeclStmt *DS, CheckerContext &C) const; 4184b3595729d249d89b8b67a547e0992797e19793Ted Kremenek}; 4284b3595729d249d89b8b67a547e0992797e19793Ted Kremenek} // end anonymous namespace 4384b3595729d249d89b8b67a547e0992797e19793Ted Kremenek 443bfd6d701ee297bd062967e11400daae51b36eb2Anna Zaksvoid VLASizeChecker::reportBug(VLASize_Kind Kind, 453bfd6d701ee297bd062967e11400daae51b36eb2Anna Zaks const Expr *SizeE, 468bef8238181a30e52dea380789a7e2d760eac532Ted Kremenek ProgramStateRef State, 473bfd6d701ee297bd062967e11400daae51b36eb2Anna Zaks CheckerContext &C) const { 483bfd6d701ee297bd062967e11400daae51b36eb2Anna Zaks // Generate an error node. 493bfd6d701ee297bd062967e11400daae51b36eb2Anna Zaks ExplodedNode *N = C.generateSink(State); 503bfd6d701ee297bd062967e11400daae51b36eb2Anna Zaks if (!N) 513bfd6d701ee297bd062967e11400daae51b36eb2Anna Zaks return; 523bfd6d701ee297bd062967e11400daae51b36eb2Anna Zaks 533bfd6d701ee297bd062967e11400daae51b36eb2Anna Zaks if (!BT) 54651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines BT.reset(new BuiltinBug( 55651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines this, "Dangerous variable-length array (VLA) declaration")); 563bfd6d701ee297bd062967e11400daae51b36eb2Anna Zaks 57f7ccbad5d9949e7ddd1cbef43d482553b811e026Dylan Noblesmith SmallString<256> buf; 583bfd6d701ee297bd062967e11400daae51b36eb2Anna Zaks llvm::raw_svector_ostream os(buf); 593bfd6d701ee297bd062967e11400daae51b36eb2Anna Zaks os << "Declared variable-length array (VLA) "; 603bfd6d701ee297bd062967e11400daae51b36eb2Anna Zaks switch (Kind) { 613bfd6d701ee297bd062967e11400daae51b36eb2Anna Zaks case VLA_Garbage: 623bfd6d701ee297bd062967e11400daae51b36eb2Anna Zaks os << "uses a garbage value as its size"; 633bfd6d701ee297bd062967e11400daae51b36eb2Anna Zaks break; 643bfd6d701ee297bd062967e11400daae51b36eb2Anna Zaks case VLA_Zero: 653bfd6d701ee297bd062967e11400daae51b36eb2Anna Zaks os << "has zero size"; 663bfd6d701ee297bd062967e11400daae51b36eb2Anna Zaks break; 673bfd6d701ee297bd062967e11400daae51b36eb2Anna Zaks case VLA_Tainted: 683bfd6d701ee297bd062967e11400daae51b36eb2Anna Zaks os << "has tainted size"; 693bfd6d701ee297bd062967e11400daae51b36eb2Anna Zaks break; 703bfd6d701ee297bd062967e11400daae51b36eb2Anna Zaks } 713bfd6d701ee297bd062967e11400daae51b36eb2Anna Zaks 723bfd6d701ee297bd062967e11400daae51b36eb2Anna Zaks BugReport *report = new BugReport(*BT, os.str(), N); 733bfd6d701ee297bd062967e11400daae51b36eb2Anna Zaks report->addRange(SizeE->getSourceRange()); 74a1f81bb0e55749a1414b1b5124bb83b9052ff2acJordan Rose bugreporter::trackNullOrUndefValue(N, SizeE, *report); 75785950e59424dca7ce0081bebf13c0acd2c4fff6Jordan Rose C.emitReport(report); 763bfd6d701ee297bd062967e11400daae51b36eb2Anna Zaks return; 773bfd6d701ee297bd062967e11400daae51b36eb2Anna Zaks} 783bfd6d701ee297bd062967e11400daae51b36eb2Anna Zaks 793ce2b48461115af047ee1e957e1892af255bf120Argyrios Kyrtzidisvoid VLASizeChecker::checkPreStmt(const DeclStmt *DS, CheckerContext &C) const { 80ae1623345aed43dcd2e069970a00618378a37b34Ted Kremenek if (!DS->isSingleDecl()) 81ae1623345aed43dcd2e069970a00618378a37b34Ted Kremenek return; 82ae1623345aed43dcd2e069970a00618378a37b34Ted Kremenek 83ae1623345aed43dcd2e069970a00618378a37b34Ted Kremenek const VarDecl *VD = dyn_cast<VarDecl>(DS->getSingleDecl()); 84ae1623345aed43dcd2e069970a00618378a37b34Ted Kremenek if (!VD) 85ae1623345aed43dcd2e069970a00618378a37b34Ted Kremenek return; 8652e04c537633377fb14cfa4fa3c95e3e510fc942Jordy Rose 8752e04c537633377fb14cfa4fa3c95e3e510fc942Jordy Rose ASTContext &Ctx = C.getASTContext(); 8852e04c537633377fb14cfa4fa3c95e3e510fc942Jordy Rose const VariableArrayType *VLA = Ctx.getAsVariableArrayType(VD->getType()); 89ae1623345aed43dcd2e069970a00618378a37b34Ted Kremenek if (!VLA) 90ae1623345aed43dcd2e069970a00618378a37b34Ted Kremenek return; 91ae1623345aed43dcd2e069970a00618378a37b34Ted Kremenek 92ae1623345aed43dcd2e069970a00618378a37b34Ted Kremenek // FIXME: Handle multi-dimensional VLAs. 939c378f705405d37f49795d5e915989de774fe11fTed Kremenek const Expr *SE = VLA->getSizeExpr(); 948bef8238181a30e52dea380789a7e2d760eac532Ted Kremenek ProgramStateRef state = C.getState(); 955eca482fe895ea57bc82410222e6426c09e63284Ted Kremenek SVal sizeV = state->getSVal(SE, C.getLocationContext()); 96ae1623345aed43dcd2e069970a00618378a37b34Ted Kremenek 97ae1623345aed43dcd2e069970a00618378a37b34Ted Kremenek if (sizeV.isUndef()) { 983bfd6d701ee297bd062967e11400daae51b36eb2Anna Zaks reportBug(VLA_Garbage, SE, state, C); 99ae1623345aed43dcd2e069970a00618378a37b34Ted Kremenek return; 10005a2338f7ba1c8a0136e120502f80a38cf0e9fd3Zhongxing Xu } 10152e04c537633377fb14cfa4fa3c95e3e510fc942Jordy Rose 10252e04c537633377fb14cfa4fa3c95e3e510fc942Jordy Rose // See if the size value is known. It can't be undefined because we would have 10352e04c537633377fb14cfa4fa3c95e3e510fc942Jordy Rose // warned about that already. 10452e04c537633377fb14cfa4fa3c95e3e510fc942Jordy Rose if (sizeV.isUnknown()) 10552e04c537633377fb14cfa4fa3c95e3e510fc942Jordy Rose return; 106ae1623345aed43dcd2e069970a00618378a37b34Ted Kremenek 1073bfd6d701ee297bd062967e11400daae51b36eb2Anna Zaks // Check if the size is tainted. 1083bfd6d701ee297bd062967e11400daae51b36eb2Anna Zaks if (state->isTainted(sizeV)) { 1096bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines reportBug(VLA_Tainted, SE, nullptr, C); 1103bfd6d701ee297bd062967e11400daae51b36eb2Anna Zaks return; 1113bfd6d701ee297bd062967e11400daae51b36eb2Anna Zaks } 1123bfd6d701ee297bd062967e11400daae51b36eb2Anna Zaks 113ae1623345aed43dcd2e069970a00618378a37b34Ted Kremenek // Check if the size is zero. 1145251abea41b446c26e3239c8dd6c7edea6fc335dDavid Blaikie DefinedSVal sizeD = sizeV.castAs<DefinedSVal>(); 115ae1623345aed43dcd2e069970a00618378a37b34Ted Kremenek 1168bef8238181a30e52dea380789a7e2d760eac532Ted Kremenek ProgramStateRef stateNotZero, stateZero; 117651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines std::tie(stateNotZero, stateZero) = state->assume(sizeD); 118ae1623345aed43dcd2e069970a00618378a37b34Ted Kremenek 119ae1623345aed43dcd2e069970a00618378a37b34Ted Kremenek if (stateZero && !stateNotZero) { 1203bfd6d701ee297bd062967e11400daae51b36eb2Anna Zaks reportBug(VLA_Zero, SE, stateZero, C); 121ae1623345aed43dcd2e069970a00618378a37b34Ted Kremenek return; 12205a2338f7ba1c8a0136e120502f80a38cf0e9fd3Zhongxing Xu } 123ae1623345aed43dcd2e069970a00618378a37b34Ted Kremenek 124ae1623345aed43dcd2e069970a00618378a37b34Ted Kremenek // From this point on, assume that the size is not zero. 12552e04c537633377fb14cfa4fa3c95e3e510fc942Jordy Rose state = stateNotZero; 12652e04c537633377fb14cfa4fa3c95e3e510fc942Jordy Rose 127b2242d1b6fe4ae073361e6d8f3db751c95159ca5Jordy Rose // VLASizeChecker is responsible for defining the extent of the array being 128b2242d1b6fe4ae073361e6d8f3db751c95159ca5Jordy Rose // declared. We do this by multiplying the array length by the element size, 129b2242d1b6fe4ae073361e6d8f3db751c95159ca5Jordy Rose // then matching that with the array region's extent symbol. 130b2242d1b6fe4ae073361e6d8f3db751c95159ca5Jordy Rose 13152e04c537633377fb14cfa4fa3c95e3e510fc942Jordy Rose // Convert the array length to size_t. 132c8413fd03f73084a5c93028f8b4db619fc388087Ted Kremenek SValBuilder &svalBuilder = C.getSValBuilder(); 13352e04c537633377fb14cfa4fa3c95e3e510fc942Jordy Rose QualType SizeTy = Ctx.getSizeType(); 1345251abea41b446c26e3239c8dd6c7edea6fc335dDavid Blaikie NonLoc ArrayLength = 1355251abea41b446c26e3239c8dd6c7edea6fc335dDavid Blaikie svalBuilder.evalCast(sizeD, SizeTy, SE->getType()).castAs<NonLoc>(); 13652e04c537633377fb14cfa4fa3c95e3e510fc942Jordy Rose 13752e04c537633377fb14cfa4fa3c95e3e510fc942Jordy Rose // Get the element size. 13852e04c537633377fb14cfa4fa3c95e3e510fc942Jordy Rose CharUnits EleSize = Ctx.getTypeSizeInChars(VLA->getElementType()); 139c8413fd03f73084a5c93028f8b4db619fc388087Ted Kremenek SVal EleSizeVal = svalBuilder.makeIntVal(EleSize.getQuantity(), SizeTy); 14052e04c537633377fb14cfa4fa3c95e3e510fc942Jordy Rose 14152e04c537633377fb14cfa4fa3c95e3e510fc942Jordy Rose // Multiply the array length by the element size. 1425251abea41b446c26e3239c8dd6c7edea6fc335dDavid Blaikie SVal ArraySizeVal = svalBuilder.evalBinOpNN( 1435251abea41b446c26e3239c8dd6c7edea6fc335dDavid Blaikie state, BO_Mul, ArrayLength, EleSizeVal.castAs<NonLoc>(), SizeTy); 14452e04c537633377fb14cfa4fa3c95e3e510fc942Jordy Rose 14528f47b92e760ccf641ac91cb0fe1c12d9ca89795Ted Kremenek // Finally, assume that the array's extent matches the given size. 14639ac1876f6f9a1a8e0070f0df61036c7ba05202bAnna Zaks const LocationContext *LC = C.getLocationContext(); 147c8413fd03f73084a5c93028f8b4db619fc388087Ted Kremenek DefinedOrUnknownSVal Extent = 148c8413fd03f73084a5c93028f8b4db619fc388087Ted Kremenek state->getRegion(VD, LC)->getExtent(svalBuilder); 1495251abea41b446c26e3239c8dd6c7edea6fc335dDavid Blaikie DefinedOrUnknownSVal ArraySize = ArraySizeVal.castAs<DefinedOrUnknownSVal>(); 150c8413fd03f73084a5c93028f8b4db619fc388087Ted Kremenek DefinedOrUnknownSVal sizeIsKnown = 151c8413fd03f73084a5c93028f8b4db619fc388087Ted Kremenek svalBuilder.evalEQ(state, Extent, ArraySize); 152c8413fd03f73084a5c93028f8b4db619fc388087Ted Kremenek state = state->assume(sizeIsKnown, true); 15352e04c537633377fb14cfa4fa3c95e3e510fc942Jordy Rose 154e4f5d72a504be32483aebdeb48fd2effce6756f2Zhongxing Xu // Assume should not fail at this point. 155e4f5d72a504be32483aebdeb48fd2effce6756f2Zhongxing Xu assert(state); 156e4f5d72a504be32483aebdeb48fd2effce6756f2Zhongxing Xu 15752e04c537633377fb14cfa4fa3c95e3e510fc942Jordy Rose // Remember our assumptions! 1580bd6b110e908892d4b5c8671a9f435a1d72ad16aAnna Zaks C.addTransition(state); 15905a2338f7ba1c8a0136e120502f80a38cf0e9fd3Zhongxing Xu} 1603ce2b48461115af047ee1e957e1892af255bf120Argyrios Kyrtzidis 1613ce2b48461115af047ee1e957e1892af255bf120Argyrios Kyrtzidisvoid ento::registerVLASizeChecker(CheckerManager &mgr) { 1623ce2b48461115af047ee1e957e1892af255bf120Argyrios Kyrtzidis mgr.registerChecker<VLASizeChecker>(); 1633ce2b48461115af047ee1e957e1892af255bf120Argyrios Kyrtzidis} 164