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// 1087d948ecccffea9e9e37d0d053b246e2d6d6c47bPirama Arumuga Nainar// 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; 33176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines enum VLASize_Kind { VLA_Garbage, VLA_Zero, VLA_Tainted, VLA_Negative }; 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. 4987d948ecccffea9e9e37d0d053b246e2d6d6c47bPirama Arumuga Nainar ExplodedNode *N = C.generateErrorNode(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; 70176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines case VLA_Negative: 71176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines os << "has negative size"; 72176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines break; 733bfd6d701ee297bd062967e11400daae51b36eb2Anna Zaks } 743bfd6d701ee297bd062967e11400daae51b36eb2Anna Zaks 7587d948ecccffea9e9e37d0d053b246e2d6d6c47bPirama Arumuga Nainar auto report = llvm::make_unique<BugReport>(*BT, os.str(), N); 763bfd6d701ee297bd062967e11400daae51b36eb2Anna Zaks report->addRange(SizeE->getSourceRange()); 77a1f81bb0e55749a1414b1b5124bb83b9052ff2acJordan Rose bugreporter::trackNullOrUndefValue(N, SizeE, *report); 7887d948ecccffea9e9e37d0d053b246e2d6d6c47bPirama Arumuga Nainar C.emitReport(std::move(report)); 793bfd6d701ee297bd062967e11400daae51b36eb2Anna Zaks} 803bfd6d701ee297bd062967e11400daae51b36eb2Anna Zaks 813ce2b48461115af047ee1e957e1892af255bf120Argyrios Kyrtzidisvoid VLASizeChecker::checkPreStmt(const DeclStmt *DS, CheckerContext &C) const { 82ae1623345aed43dcd2e069970a00618378a37b34Ted Kremenek if (!DS->isSingleDecl()) 83ae1623345aed43dcd2e069970a00618378a37b34Ted Kremenek return; 8487d948ecccffea9e9e37d0d053b246e2d6d6c47bPirama Arumuga Nainar 85ae1623345aed43dcd2e069970a00618378a37b34Ted Kremenek const VarDecl *VD = dyn_cast<VarDecl>(DS->getSingleDecl()); 86ae1623345aed43dcd2e069970a00618378a37b34Ted Kremenek if (!VD) 87ae1623345aed43dcd2e069970a00618378a37b34Ted Kremenek return; 8852e04c537633377fb14cfa4fa3c95e3e510fc942Jordy Rose 8952e04c537633377fb14cfa4fa3c95e3e510fc942Jordy Rose ASTContext &Ctx = C.getASTContext(); 9052e04c537633377fb14cfa4fa3c95e3e510fc942Jordy Rose const VariableArrayType *VLA = Ctx.getAsVariableArrayType(VD->getType()); 91ae1623345aed43dcd2e069970a00618378a37b34Ted Kremenek if (!VLA) 92ae1623345aed43dcd2e069970a00618378a37b34Ted Kremenek return; 93ae1623345aed43dcd2e069970a00618378a37b34Ted Kremenek 94ae1623345aed43dcd2e069970a00618378a37b34Ted Kremenek // FIXME: Handle multi-dimensional VLAs. 959c378f705405d37f49795d5e915989de774fe11fTed Kremenek const Expr *SE = VLA->getSizeExpr(); 968bef8238181a30e52dea380789a7e2d760eac532Ted Kremenek ProgramStateRef state = C.getState(); 975eca482fe895ea57bc82410222e6426c09e63284Ted Kremenek SVal sizeV = state->getSVal(SE, C.getLocationContext()); 98ae1623345aed43dcd2e069970a00618378a37b34Ted Kremenek 99ae1623345aed43dcd2e069970a00618378a37b34Ted Kremenek if (sizeV.isUndef()) { 1003bfd6d701ee297bd062967e11400daae51b36eb2Anna Zaks reportBug(VLA_Garbage, SE, state, C); 101ae1623345aed43dcd2e069970a00618378a37b34Ted Kremenek return; 10205a2338f7ba1c8a0136e120502f80a38cf0e9fd3Zhongxing Xu } 10352e04c537633377fb14cfa4fa3c95e3e510fc942Jordy Rose 10452e04c537633377fb14cfa4fa3c95e3e510fc942Jordy Rose // See if the size value is known. It can't be undefined because we would have 10552e04c537633377fb14cfa4fa3c95e3e510fc942Jordy Rose // warned about that already. 10652e04c537633377fb14cfa4fa3c95e3e510fc942Jordy Rose if (sizeV.isUnknown()) 10752e04c537633377fb14cfa4fa3c95e3e510fc942Jordy Rose return; 10887d948ecccffea9e9e37d0d053b246e2d6d6c47bPirama Arumuga Nainar 1093bfd6d701ee297bd062967e11400daae51b36eb2Anna Zaks // Check if the size is tainted. 1103bfd6d701ee297bd062967e11400daae51b36eb2Anna Zaks if (state->isTainted(sizeV)) { 1116bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines reportBug(VLA_Tainted, SE, nullptr, C); 1123bfd6d701ee297bd062967e11400daae51b36eb2Anna Zaks return; 1133bfd6d701ee297bd062967e11400daae51b36eb2Anna Zaks } 1143bfd6d701ee297bd062967e11400daae51b36eb2Anna Zaks 115ae1623345aed43dcd2e069970a00618378a37b34Ted Kremenek // Check if the size is zero. 1165251abea41b446c26e3239c8dd6c7edea6fc335dDavid Blaikie DefinedSVal sizeD = sizeV.castAs<DefinedSVal>(); 117ae1623345aed43dcd2e069970a00618378a37b34Ted Kremenek 1188bef8238181a30e52dea380789a7e2d760eac532Ted Kremenek ProgramStateRef stateNotZero, stateZero; 119651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines std::tie(stateNotZero, stateZero) = state->assume(sizeD); 120ae1623345aed43dcd2e069970a00618378a37b34Ted Kremenek 121ae1623345aed43dcd2e069970a00618378a37b34Ted Kremenek if (stateZero && !stateNotZero) { 1223bfd6d701ee297bd062967e11400daae51b36eb2Anna Zaks reportBug(VLA_Zero, SE, stateZero, C); 123ae1623345aed43dcd2e069970a00618378a37b34Ted Kremenek return; 12405a2338f7ba1c8a0136e120502f80a38cf0e9fd3Zhongxing Xu } 12587d948ecccffea9e9e37d0d053b246e2d6d6c47bPirama Arumuga Nainar 126ae1623345aed43dcd2e069970a00618378a37b34Ted Kremenek // From this point on, assume that the size is not zero. 12752e04c537633377fb14cfa4fa3c95e3e510fc942Jordy Rose state = stateNotZero; 12852e04c537633377fb14cfa4fa3c95e3e510fc942Jordy Rose 129b2242d1b6fe4ae073361e6d8f3db751c95159ca5Jordy Rose // VLASizeChecker is responsible for defining the extent of the array being 130b2242d1b6fe4ae073361e6d8f3db751c95159ca5Jordy Rose // declared. We do this by multiplying the array length by the element size, 131b2242d1b6fe4ae073361e6d8f3db751c95159ca5Jordy Rose // then matching that with the array region's extent symbol. 132b2242d1b6fe4ae073361e6d8f3db751c95159ca5Jordy Rose 133176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines // Check if the size is negative. 134c8413fd03f73084a5c93028f8b4db619fc388087Ted Kremenek SValBuilder &svalBuilder = C.getSValBuilder(); 135176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines 136176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines QualType Ty = SE->getType(); 137176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines DefinedOrUnknownSVal Zero = svalBuilder.makeZeroVal(Ty); 138176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines 139176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines SVal LessThanZeroVal = svalBuilder.evalBinOp(state, BO_LT, sizeD, Zero, Ty); 140176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines if (Optional<DefinedSVal> LessThanZeroDVal = 141176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines LessThanZeroVal.getAs<DefinedSVal>()) { 142176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines ConstraintManager &CM = C.getConstraintManager(); 143176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines ProgramStateRef StatePos, StateNeg; 144176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines 145176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines std::tie(StateNeg, StatePos) = CM.assumeDual(state, *LessThanZeroDVal); 146176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines if (StateNeg && !StatePos) { 147176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines reportBug(VLA_Negative, SE, state, C); 148176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines return; 149176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines } 150176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines state = StatePos; 151176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines } 152176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines 153176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines // Convert the array length to size_t. 15452e04c537633377fb14cfa4fa3c95e3e510fc942Jordy Rose QualType SizeTy = Ctx.getSizeType(); 1555251abea41b446c26e3239c8dd6c7edea6fc335dDavid Blaikie NonLoc ArrayLength = 1565251abea41b446c26e3239c8dd6c7edea6fc335dDavid Blaikie svalBuilder.evalCast(sizeD, SizeTy, SE->getType()).castAs<NonLoc>(); 15752e04c537633377fb14cfa4fa3c95e3e510fc942Jordy Rose 15852e04c537633377fb14cfa4fa3c95e3e510fc942Jordy Rose // Get the element size. 15952e04c537633377fb14cfa4fa3c95e3e510fc942Jordy Rose CharUnits EleSize = Ctx.getTypeSizeInChars(VLA->getElementType()); 160c8413fd03f73084a5c93028f8b4db619fc388087Ted Kremenek SVal EleSizeVal = svalBuilder.makeIntVal(EleSize.getQuantity(), SizeTy); 16152e04c537633377fb14cfa4fa3c95e3e510fc942Jordy Rose 16252e04c537633377fb14cfa4fa3c95e3e510fc942Jordy Rose // Multiply the array length by the element size. 1635251abea41b446c26e3239c8dd6c7edea6fc335dDavid Blaikie SVal ArraySizeVal = svalBuilder.evalBinOpNN( 1645251abea41b446c26e3239c8dd6c7edea6fc335dDavid Blaikie state, BO_Mul, ArrayLength, EleSizeVal.castAs<NonLoc>(), SizeTy); 16552e04c537633377fb14cfa4fa3c95e3e510fc942Jordy Rose 16628f47b92e760ccf641ac91cb0fe1c12d9ca89795Ted Kremenek // Finally, assume that the array's extent matches the given size. 16739ac1876f6f9a1a8e0070f0df61036c7ba05202bAnna Zaks const LocationContext *LC = C.getLocationContext(); 168c8413fd03f73084a5c93028f8b4db619fc388087Ted Kremenek DefinedOrUnknownSVal Extent = 169c8413fd03f73084a5c93028f8b4db619fc388087Ted Kremenek state->getRegion(VD, LC)->getExtent(svalBuilder); 1705251abea41b446c26e3239c8dd6c7edea6fc335dDavid Blaikie DefinedOrUnknownSVal ArraySize = ArraySizeVal.castAs<DefinedOrUnknownSVal>(); 171c8413fd03f73084a5c93028f8b4db619fc388087Ted Kremenek DefinedOrUnknownSVal sizeIsKnown = 172c8413fd03f73084a5c93028f8b4db619fc388087Ted Kremenek svalBuilder.evalEQ(state, Extent, ArraySize); 173c8413fd03f73084a5c93028f8b4db619fc388087Ted Kremenek state = state->assume(sizeIsKnown, true); 17452e04c537633377fb14cfa4fa3c95e3e510fc942Jordy Rose 175e4f5d72a504be32483aebdeb48fd2effce6756f2Zhongxing Xu // Assume should not fail at this point. 176e4f5d72a504be32483aebdeb48fd2effce6756f2Zhongxing Xu assert(state); 177e4f5d72a504be32483aebdeb48fd2effce6756f2Zhongxing Xu 17852e04c537633377fb14cfa4fa3c95e3e510fc942Jordy Rose // Remember our assumptions! 1790bd6b110e908892d4b5c8671a9f435a1d72ad16aAnna Zaks C.addTransition(state); 18005a2338f7ba1c8a0136e120502f80a38cf0e9fd3Zhongxing Xu} 1813ce2b48461115af047ee1e957e1892af255bf120Argyrios Kyrtzidis 1823ce2b48461115af047ee1e957e1892af255bf120Argyrios Kyrtzidisvoid ento::registerVLASizeChecker(CheckerManager &mgr) { 1833ce2b48461115af047ee1e957e1892af255bf120Argyrios Kyrtzidis mgr.registerChecker<VLASizeChecker>(); 1843ce2b48461115af047ee1e957e1892af255bf120Argyrios Kyrtzidis} 185