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" 18ec8605f1d7ec846dbf51047bfd5c56d32d1ff91cArgyrios Kyrtzidis#include "clang/StaticAnalyzer/Core/Checker.h" 193ce2b48461115af047ee1e957e1892af255bf120Argyrios Kyrtzidis#include "clang/StaticAnalyzer/Core/CheckerManager.h" 203ce2b48461115af047ee1e957e1892af255bf120Argyrios Kyrtzidis#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h" 219b663716449b618ba0390b1dbebc54fa8e971124Ted Kremenek#include "clang/StaticAnalyzer/Core/BugReporter/BugType.h" 223ce2b48461115af047ee1e957e1892af255bf120Argyrios Kyrtzidis#include "clang/AST/CharUnits.h" 238fe83e1df954d72c0f4ffc15d20a5222ec151c21Benjamin Kramer#include "llvm/ADT/SmallString.h" 2400bd44d5677783527d7517c1ffe45e4d75a0f56fBenjamin Kramer#include "llvm/ADT/STLExtras.h" 2505a2338f7ba1c8a0136e120502f80a38cf0e9fd3Zhongxing Xu 2605a2338f7ba1c8a0136e120502f80a38cf0e9fd3Zhongxing Xuusing namespace clang; 279ef6537a894c33003359b1f9b9676e9178e028b7Ted Kremenekusing namespace ento; 2805a2338f7ba1c8a0136e120502f80a38cf0e9fd3Zhongxing Xu 2984b3595729d249d89b8b67a547e0992797e19793Ted Kremeneknamespace { 30ec8605f1d7ec846dbf51047bfd5c56d32d1ff91cArgyrios Kyrtzidisclass VLASizeChecker : public Checker< check::PreStmt<DeclStmt> > { 316f42b62b6194f53bcbc349f5d17388e1936535d7Dylan Noblesmith mutable OwningPtr<BugType> BT; 323bfd6d701ee297bd062967e11400daae51b36eb2Anna Zaks enum VLASize_Kind { VLA_Garbage, VLA_Zero, VLA_Tainted }; 333bfd6d701ee297bd062967e11400daae51b36eb2Anna Zaks 343bfd6d701ee297bd062967e11400daae51b36eb2Anna Zaks void reportBug(VLASize_Kind Kind, 353bfd6d701ee297bd062967e11400daae51b36eb2Anna Zaks const Expr *SizeE, 368bef8238181a30e52dea380789a7e2d760eac532Ted Kremenek ProgramStateRef State, 373bfd6d701ee297bd062967e11400daae51b36eb2Anna Zaks CheckerContext &C) const; 3884b3595729d249d89b8b67a547e0992797e19793Ted Kremenekpublic: 393ce2b48461115af047ee1e957e1892af255bf120Argyrios Kyrtzidis void checkPreStmt(const DeclStmt *DS, CheckerContext &C) const; 4084b3595729d249d89b8b67a547e0992797e19793Ted Kremenek}; 4184b3595729d249d89b8b67a547e0992797e19793Ted Kremenek} // end anonymous namespace 4284b3595729d249d89b8b67a547e0992797e19793Ted Kremenek 433bfd6d701ee297bd062967e11400daae51b36eb2Anna Zaksvoid VLASizeChecker::reportBug(VLASize_Kind Kind, 443bfd6d701ee297bd062967e11400daae51b36eb2Anna Zaks const Expr *SizeE, 458bef8238181a30e52dea380789a7e2d760eac532Ted Kremenek ProgramStateRef State, 463bfd6d701ee297bd062967e11400daae51b36eb2Anna Zaks CheckerContext &C) const { 473bfd6d701ee297bd062967e11400daae51b36eb2Anna Zaks // Generate an error node. 483bfd6d701ee297bd062967e11400daae51b36eb2Anna Zaks ExplodedNode *N = C.generateSink(State); 493bfd6d701ee297bd062967e11400daae51b36eb2Anna Zaks if (!N) 503bfd6d701ee297bd062967e11400daae51b36eb2Anna Zaks return; 513bfd6d701ee297bd062967e11400daae51b36eb2Anna Zaks 523bfd6d701ee297bd062967e11400daae51b36eb2Anna Zaks if (!BT) 533bfd6d701ee297bd062967e11400daae51b36eb2Anna Zaks BT.reset(new BuiltinBug("Dangerous variable-length array (VLA) declaration")); 543bfd6d701ee297bd062967e11400daae51b36eb2Anna Zaks 55f7ccbad5d9949e7ddd1cbef43d482553b811e026Dylan Noblesmith SmallString<256> buf; 563bfd6d701ee297bd062967e11400daae51b36eb2Anna Zaks llvm::raw_svector_ostream os(buf); 573bfd6d701ee297bd062967e11400daae51b36eb2Anna Zaks os << "Declared variable-length array (VLA) "; 583bfd6d701ee297bd062967e11400daae51b36eb2Anna Zaks switch (Kind) { 593bfd6d701ee297bd062967e11400daae51b36eb2Anna Zaks case VLA_Garbage: 603bfd6d701ee297bd062967e11400daae51b36eb2Anna Zaks os << "uses a garbage value as its size"; 613bfd6d701ee297bd062967e11400daae51b36eb2Anna Zaks break; 623bfd6d701ee297bd062967e11400daae51b36eb2Anna Zaks case VLA_Zero: 633bfd6d701ee297bd062967e11400daae51b36eb2Anna Zaks os << "has zero size"; 643bfd6d701ee297bd062967e11400daae51b36eb2Anna Zaks break; 653bfd6d701ee297bd062967e11400daae51b36eb2Anna Zaks case VLA_Tainted: 663bfd6d701ee297bd062967e11400daae51b36eb2Anna Zaks os << "has tainted size"; 673bfd6d701ee297bd062967e11400daae51b36eb2Anna Zaks break; 683bfd6d701ee297bd062967e11400daae51b36eb2Anna Zaks } 693bfd6d701ee297bd062967e11400daae51b36eb2Anna Zaks 703bfd6d701ee297bd062967e11400daae51b36eb2Anna Zaks BugReport *report = new BugReport(*BT, os.str(), N); 713bfd6d701ee297bd062967e11400daae51b36eb2Anna Zaks report->addRange(SizeE->getSourceRange()); 72a1f81bb0e55749a1414b1b5124bb83b9052ff2acJordan Rose bugreporter::trackNullOrUndefValue(N, SizeE, *report); 733bfd6d701ee297bd062967e11400daae51b36eb2Anna Zaks C.EmitReport(report); 743bfd6d701ee297bd062967e11400daae51b36eb2Anna Zaks return; 753bfd6d701ee297bd062967e11400daae51b36eb2Anna Zaks} 763bfd6d701ee297bd062967e11400daae51b36eb2Anna Zaks 773ce2b48461115af047ee1e957e1892af255bf120Argyrios Kyrtzidisvoid VLASizeChecker::checkPreStmt(const DeclStmt *DS, CheckerContext &C) const { 78ae1623345aed43dcd2e069970a00618378a37b34Ted Kremenek if (!DS->isSingleDecl()) 79ae1623345aed43dcd2e069970a00618378a37b34Ted Kremenek return; 80ae1623345aed43dcd2e069970a00618378a37b34Ted Kremenek 81ae1623345aed43dcd2e069970a00618378a37b34Ted Kremenek const VarDecl *VD = dyn_cast<VarDecl>(DS->getSingleDecl()); 82ae1623345aed43dcd2e069970a00618378a37b34Ted Kremenek if (!VD) 83ae1623345aed43dcd2e069970a00618378a37b34Ted Kremenek return; 8452e04c537633377fb14cfa4fa3c95e3e510fc942Jordy Rose 8552e04c537633377fb14cfa4fa3c95e3e510fc942Jordy Rose ASTContext &Ctx = C.getASTContext(); 8652e04c537633377fb14cfa4fa3c95e3e510fc942Jordy Rose const VariableArrayType *VLA = Ctx.getAsVariableArrayType(VD->getType()); 87ae1623345aed43dcd2e069970a00618378a37b34Ted Kremenek if (!VLA) 88ae1623345aed43dcd2e069970a00618378a37b34Ted Kremenek return; 89ae1623345aed43dcd2e069970a00618378a37b34Ted Kremenek 90ae1623345aed43dcd2e069970a00618378a37b34Ted Kremenek // FIXME: Handle multi-dimensional VLAs. 919c378f705405d37f49795d5e915989de774fe11fTed Kremenek const Expr *SE = VLA->getSizeExpr(); 928bef8238181a30e52dea380789a7e2d760eac532Ted Kremenek ProgramStateRef state = C.getState(); 935eca482fe895ea57bc82410222e6426c09e63284Ted Kremenek SVal sizeV = state->getSVal(SE, C.getLocationContext()); 94ae1623345aed43dcd2e069970a00618378a37b34Ted Kremenek 95ae1623345aed43dcd2e069970a00618378a37b34Ted Kremenek if (sizeV.isUndef()) { 963bfd6d701ee297bd062967e11400daae51b36eb2Anna Zaks reportBug(VLA_Garbage, SE, state, C); 97ae1623345aed43dcd2e069970a00618378a37b34Ted Kremenek return; 9805a2338f7ba1c8a0136e120502f80a38cf0e9fd3Zhongxing Xu } 9952e04c537633377fb14cfa4fa3c95e3e510fc942Jordy Rose 10052e04c537633377fb14cfa4fa3c95e3e510fc942Jordy Rose // See if the size value is known. It can't be undefined because we would have 10152e04c537633377fb14cfa4fa3c95e3e510fc942Jordy Rose // warned about that already. 10252e04c537633377fb14cfa4fa3c95e3e510fc942Jordy Rose if (sizeV.isUnknown()) 10352e04c537633377fb14cfa4fa3c95e3e510fc942Jordy Rose return; 104ae1623345aed43dcd2e069970a00618378a37b34Ted Kremenek 1053bfd6d701ee297bd062967e11400daae51b36eb2Anna Zaks // Check if the size is tainted. 1063bfd6d701ee297bd062967e11400daae51b36eb2Anna Zaks if (state->isTainted(sizeV)) { 1073bfd6d701ee297bd062967e11400daae51b36eb2Anna Zaks reportBug(VLA_Tainted, SE, 0, C); 1083bfd6d701ee297bd062967e11400daae51b36eb2Anna Zaks return; 1093bfd6d701ee297bd062967e11400daae51b36eb2Anna Zaks } 1103bfd6d701ee297bd062967e11400daae51b36eb2Anna Zaks 111ae1623345aed43dcd2e069970a00618378a37b34Ted Kremenek // Check if the size is zero. 11252e04c537633377fb14cfa4fa3c95e3e510fc942Jordy Rose DefinedSVal sizeD = cast<DefinedSVal>(sizeV); 113ae1623345aed43dcd2e069970a00618378a37b34Ted Kremenek 1148bef8238181a30e52dea380789a7e2d760eac532Ted Kremenek ProgramStateRef stateNotZero, stateZero; 11528f47b92e760ccf641ac91cb0fe1c12d9ca89795Ted Kremenek llvm::tie(stateNotZero, stateZero) = state->assume(sizeD); 116ae1623345aed43dcd2e069970a00618378a37b34Ted Kremenek 117ae1623345aed43dcd2e069970a00618378a37b34Ted Kremenek if (stateZero && !stateNotZero) { 1183bfd6d701ee297bd062967e11400daae51b36eb2Anna Zaks reportBug(VLA_Zero, SE, stateZero, C); 119ae1623345aed43dcd2e069970a00618378a37b34Ted Kremenek return; 12005a2338f7ba1c8a0136e120502f80a38cf0e9fd3Zhongxing Xu } 121ae1623345aed43dcd2e069970a00618378a37b34Ted Kremenek 122ae1623345aed43dcd2e069970a00618378a37b34Ted Kremenek // From this point on, assume that the size is not zero. 12352e04c537633377fb14cfa4fa3c95e3e510fc942Jordy Rose state = stateNotZero; 12452e04c537633377fb14cfa4fa3c95e3e510fc942Jordy Rose 125b2242d1b6fe4ae073361e6d8f3db751c95159ca5Jordy Rose // VLASizeChecker is responsible for defining the extent of the array being 126b2242d1b6fe4ae073361e6d8f3db751c95159ca5Jordy Rose // declared. We do this by multiplying the array length by the element size, 127b2242d1b6fe4ae073361e6d8f3db751c95159ca5Jordy Rose // then matching that with the array region's extent symbol. 128b2242d1b6fe4ae073361e6d8f3db751c95159ca5Jordy Rose 12952e04c537633377fb14cfa4fa3c95e3e510fc942Jordy Rose // Convert the array length to size_t. 130c8413fd03f73084a5c93028f8b4db619fc388087Ted Kremenek SValBuilder &svalBuilder = C.getSValBuilder(); 13152e04c537633377fb14cfa4fa3c95e3e510fc942Jordy Rose QualType SizeTy = Ctx.getSizeType(); 132c8413fd03f73084a5c93028f8b4db619fc388087Ted Kremenek NonLoc ArrayLength = cast<NonLoc>(svalBuilder.evalCast(sizeD, SizeTy, 133c8413fd03f73084a5c93028f8b4db619fc388087Ted Kremenek SE->getType())); 13452e04c537633377fb14cfa4fa3c95e3e510fc942Jordy Rose 13552e04c537633377fb14cfa4fa3c95e3e510fc942Jordy Rose // Get the element size. 13652e04c537633377fb14cfa4fa3c95e3e510fc942Jordy Rose CharUnits EleSize = Ctx.getTypeSizeInChars(VLA->getElementType()); 137c8413fd03f73084a5c93028f8b4db619fc388087Ted Kremenek SVal EleSizeVal = svalBuilder.makeIntVal(EleSize.getQuantity(), SizeTy); 13852e04c537633377fb14cfa4fa3c95e3e510fc942Jordy Rose 13952e04c537633377fb14cfa4fa3c95e3e510fc942Jordy Rose // Multiply the array length by the element size. 140c8413fd03f73084a5c93028f8b4db619fc388087Ted Kremenek SVal ArraySizeVal = svalBuilder.evalBinOpNN(state, BO_Mul, ArrayLength, 141c8413fd03f73084a5c93028f8b4db619fc388087Ted Kremenek cast<NonLoc>(EleSizeVal), SizeTy); 14252e04c537633377fb14cfa4fa3c95e3e510fc942Jordy Rose 14328f47b92e760ccf641ac91cb0fe1c12d9ca89795Ted Kremenek // Finally, assume that the array's extent matches the given size. 14439ac1876f6f9a1a8e0070f0df61036c7ba05202bAnna Zaks const LocationContext *LC = C.getLocationContext(); 145c8413fd03f73084a5c93028f8b4db619fc388087Ted Kremenek DefinedOrUnknownSVal Extent = 146c8413fd03f73084a5c93028f8b4db619fc388087Ted Kremenek state->getRegion(VD, LC)->getExtent(svalBuilder); 14752e04c537633377fb14cfa4fa3c95e3e510fc942Jordy Rose DefinedOrUnknownSVal ArraySize = cast<DefinedOrUnknownSVal>(ArraySizeVal); 148c8413fd03f73084a5c93028f8b4db619fc388087Ted Kremenek DefinedOrUnknownSVal sizeIsKnown = 149c8413fd03f73084a5c93028f8b4db619fc388087Ted Kremenek svalBuilder.evalEQ(state, Extent, ArraySize); 150c8413fd03f73084a5c93028f8b4db619fc388087Ted Kremenek state = state->assume(sizeIsKnown, true); 15152e04c537633377fb14cfa4fa3c95e3e510fc942Jordy Rose 152e4f5d72a504be32483aebdeb48fd2effce6756f2Zhongxing Xu // Assume should not fail at this point. 153e4f5d72a504be32483aebdeb48fd2effce6756f2Zhongxing Xu assert(state); 154e4f5d72a504be32483aebdeb48fd2effce6756f2Zhongxing Xu 15552e04c537633377fb14cfa4fa3c95e3e510fc942Jordy Rose // Remember our assumptions! 1560bd6b110e908892d4b5c8671a9f435a1d72ad16aAnna Zaks C.addTransition(state); 15705a2338f7ba1c8a0136e120502f80a38cf0e9fd3Zhongxing Xu} 1583ce2b48461115af047ee1e957e1892af255bf120Argyrios Kyrtzidis 1593ce2b48461115af047ee1e957e1892af255bf120Argyrios Kyrtzidisvoid ento::registerVLASizeChecker(CheckerManager &mgr) { 1603ce2b48461115af047ee1e957e1892af255bf120Argyrios Kyrtzidis mgr.registerChecker<VLASizeChecker>(); 1613ce2b48461115af047ee1e957e1892af255bf120Argyrios Kyrtzidis} 162