1 //=== PointerArithChecker.cpp - Pointer arithmetic checker -----*- C++ -*--===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 // 10 // This files defines PointerArithChecker, a builtin checker that checks for 11 // pointer arithmetic on locations other than array elements. 12 // 13 //===----------------------------------------------------------------------===// 14 15 #include "ClangSACheckers.h" 16 #include "clang/AST/DeclCXX.h" 17 #include "clang/AST/ExprCXX.h" 18 #include "clang/StaticAnalyzer/Core/BugReporter/BugType.h" 19 #include "clang/StaticAnalyzer/Core/Checker.h" 20 #include "clang/StaticAnalyzer/Core/CheckerManager.h" 21 #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h" 22 #include "llvm/ADT/SmallVector.h" 23 24 using namespace clang; 25 using namespace ento; 26 27 namespace { 28 enum class AllocKind { 29 SingleObject, 30 Array, 31 Unknown, 32 Reinterpreted // Single object interpreted as an array. 33 }; 34 } // end namespace 35 36 namespace llvm { 37 template <> struct FoldingSetTrait<AllocKind> { 38 static inline void Profile(AllocKind X, FoldingSetNodeID &ID) { 39 ID.AddInteger(static_cast<int>(X)); 40 } 41 }; 42 } // end namespace llvm 43 44 namespace { 45 class PointerArithChecker 46 : public Checker< 47 check::PreStmt<BinaryOperator>, check::PreStmt<UnaryOperator>, 48 check::PreStmt<ArraySubscriptExpr>, check::PreStmt<CastExpr>, 49 check::PostStmt<CastExpr>, check::PostStmt<CXXNewExpr>, 50 check::PostStmt<CallExpr>, check::DeadSymbols> { 51 AllocKind getKindOfNewOp(const CXXNewExpr *NE, const FunctionDecl *FD) const; 52 const MemRegion *getArrayRegion(const MemRegion *Region, bool &Polymorphic, 53 AllocKind &AKind, CheckerContext &C) const; 54 const MemRegion *getPointedRegion(const MemRegion *Region, 55 CheckerContext &C) const; 56 void reportPointerArithMisuse(const Expr *E, CheckerContext &C, 57 bool PointedNeeded = false) const; 58 void initAllocIdentifiers(ASTContext &C) const; 59 60 mutable std::unique_ptr<BuiltinBug> BT_pointerArith; 61 mutable std::unique_ptr<BuiltinBug> BT_polyArray; 62 mutable llvm::SmallSet<IdentifierInfo *, 8> AllocFunctions; 63 64 public: 65 void checkPreStmt(const UnaryOperator *UOp, CheckerContext &C) const; 66 void checkPreStmt(const BinaryOperator *BOp, CheckerContext &C) const; 67 void checkPreStmt(const ArraySubscriptExpr *SubExpr, CheckerContext &C) const; 68 void checkPreStmt(const CastExpr *CE, CheckerContext &C) const; 69 void checkPostStmt(const CastExpr *CE, CheckerContext &C) const; 70 void checkPostStmt(const CXXNewExpr *NE, CheckerContext &C) const; 71 void checkPostStmt(const CallExpr *CE, CheckerContext &C) const; 72 void checkDeadSymbols(SymbolReaper &SR, CheckerContext &C) const; 73 }; 74 } // end namespace 75 76 REGISTER_MAP_WITH_PROGRAMSTATE(RegionState, const MemRegion *, AllocKind) 77 78 void PointerArithChecker::checkDeadSymbols(SymbolReaper &SR, 79 CheckerContext &C) const { 80 // TODO: intentional leak. Some information is garbage collected too early, 81 // see http://reviews.llvm.org/D14203 for further information. 82 /*ProgramStateRef State = C.getState(); 83 RegionStateTy RegionStates = State->get<RegionState>(); 84 for (RegionStateTy::iterator I = RegionStates.begin(), E = RegionStates.end(); 85 I != E; ++I) { 86 if (!SR.isLiveRegion(I->first)) 87 State = State->remove<RegionState>(I->first); 88 } 89 C.addTransition(State);*/ 90 } 91 92 AllocKind PointerArithChecker::getKindOfNewOp(const CXXNewExpr *NE, 93 const FunctionDecl *FD) const { 94 // This checker try not to assume anything about placement and overloaded 95 // new to avoid false positives. 96 if (isa<CXXMethodDecl>(FD)) 97 return AllocKind::Unknown; 98 if (FD->getNumParams() != 1 || FD->isVariadic()) 99 return AllocKind::Unknown; 100 if (NE->isArray()) 101 return AllocKind::Array; 102 103 return AllocKind::SingleObject; 104 } 105 106 const MemRegion * 107 PointerArithChecker::getPointedRegion(const MemRegion *Region, 108 CheckerContext &C) const { 109 assert(Region); 110 ProgramStateRef State = C.getState(); 111 SVal S = State->getSVal(Region); 112 return S.getAsRegion(); 113 } 114 115 /// Checks whether a region is the part of an array. 116 /// In case there is a dericed to base cast above the array element, the 117 /// Polymorphic output value is set to true. AKind output value is set to the 118 /// allocation kind of the inspected region. 119 const MemRegion *PointerArithChecker::getArrayRegion(const MemRegion *Region, 120 bool &Polymorphic, 121 AllocKind &AKind, 122 CheckerContext &C) const { 123 assert(Region); 124 while (Region->getKind() == MemRegion::Kind::CXXBaseObjectRegionKind) { 125 Region = Region->getAs<CXXBaseObjectRegion>()->getSuperRegion(); 126 Polymorphic = true; 127 } 128 if (Region->getKind() == MemRegion::Kind::ElementRegionKind) { 129 Region = Region->getAs<ElementRegion>()->getSuperRegion(); 130 } 131 132 ProgramStateRef State = C.getState(); 133 if (const AllocKind *Kind = State->get<RegionState>(Region)) { 134 AKind = *Kind; 135 if (*Kind == AllocKind::Array) 136 return Region; 137 else 138 return nullptr; 139 } 140 // When the region is symbolic and we do not have any information about it, 141 // assume that this is an array to avoid false positives. 142 if (Region->getKind() == MemRegion::Kind::SymbolicRegionKind) 143 return Region; 144 145 // No AllocKind stored and not symbolic, assume that it points to a single 146 // object. 147 return nullptr; 148 } 149 150 void PointerArithChecker::reportPointerArithMisuse(const Expr *E, 151 CheckerContext &C, 152 bool PointedNeeded) const { 153 SourceRange SR = E->getSourceRange(); 154 if (SR.isInvalid()) 155 return; 156 157 ProgramStateRef State = C.getState(); 158 const MemRegion *Region = 159 State->getSVal(E, C.getLocationContext()).getAsRegion(); 160 if (!Region) 161 return; 162 if (PointedNeeded) 163 Region = getPointedRegion(Region, C); 164 if (!Region) 165 return; 166 167 bool IsPolymorphic = false; 168 AllocKind Kind = AllocKind::Unknown; 169 if (const MemRegion *ArrayRegion = 170 getArrayRegion(Region, IsPolymorphic, Kind, C)) { 171 if (!IsPolymorphic) 172 return; 173 if (ExplodedNode *N = C.generateNonFatalErrorNode()) { 174 if (!BT_polyArray) 175 BT_polyArray.reset(new BuiltinBug( 176 this, "Dangerous pointer arithmetic", 177 "Pointer arithmetic on a pointer to base class is dangerous " 178 "because derived and base class may have different size.")); 179 auto R = llvm::make_unique<BugReport>(*BT_polyArray, 180 BT_polyArray->getDescription(), N); 181 R->addRange(E->getSourceRange()); 182 R->markInteresting(ArrayRegion); 183 C.emitReport(std::move(R)); 184 } 185 return; 186 } 187 188 if (Kind == AllocKind::Reinterpreted) 189 return; 190 191 // We might not have enough information about symbolic regions. 192 if (Kind != AllocKind::SingleObject && 193 Region->getKind() == MemRegion::Kind::SymbolicRegionKind) 194 return; 195 196 if (ExplodedNode *N = C.generateNonFatalErrorNode()) { 197 if (!BT_pointerArith) 198 BT_pointerArith.reset(new BuiltinBug(this, "Dangerous pointer arithmetic", 199 "Pointer arithmetic on non-array " 200 "variables relies on memory layout, " 201 "which is dangerous.")); 202 auto R = llvm::make_unique<BugReport>(*BT_pointerArith, 203 BT_pointerArith->getDescription(), N); 204 R->addRange(SR); 205 R->markInteresting(Region); 206 C.emitReport(std::move(R)); 207 } 208 } 209 210 void PointerArithChecker::initAllocIdentifiers(ASTContext &C) const { 211 if (!AllocFunctions.empty()) 212 return; 213 AllocFunctions.insert(&C.Idents.get("alloca")); 214 AllocFunctions.insert(&C.Idents.get("malloc")); 215 AllocFunctions.insert(&C.Idents.get("realloc")); 216 AllocFunctions.insert(&C.Idents.get("calloc")); 217 AllocFunctions.insert(&C.Idents.get("valloc")); 218 } 219 220 void PointerArithChecker::checkPostStmt(const CallExpr *CE, 221 CheckerContext &C) const { 222 ProgramStateRef State = C.getState(); 223 const FunctionDecl *FD = C.getCalleeDecl(CE); 224 if (!FD) 225 return; 226 IdentifierInfo *FunI = FD->getIdentifier(); 227 initAllocIdentifiers(C.getASTContext()); 228 if (AllocFunctions.count(FunI) == 0) 229 return; 230 231 SVal SV = State->getSVal(CE, C.getLocationContext()); 232 const MemRegion *Region = SV.getAsRegion(); 233 if (!Region) 234 return; 235 // Assume that C allocation functions allocate arrays to avoid false 236 // positives. 237 // TODO: Add heuristics to distinguish alloc calls that allocates single 238 // objecs. 239 State = State->set<RegionState>(Region, AllocKind::Array); 240 C.addTransition(State); 241 } 242 243 void PointerArithChecker::checkPostStmt(const CXXNewExpr *NE, 244 CheckerContext &C) const { 245 const FunctionDecl *FD = NE->getOperatorNew(); 246 if (!FD) 247 return; 248 249 AllocKind Kind = getKindOfNewOp(NE, FD); 250 251 ProgramStateRef State = C.getState(); 252 SVal AllocedVal = State->getSVal(NE, C.getLocationContext()); 253 const MemRegion *Region = AllocedVal.getAsRegion(); 254 if (!Region) 255 return; 256 State = State->set<RegionState>(Region, Kind); 257 C.addTransition(State); 258 } 259 260 void PointerArithChecker::checkPostStmt(const CastExpr *CE, 261 CheckerContext &C) const { 262 if (CE->getCastKind() != CastKind::CK_BitCast) 263 return; 264 265 const Expr *CastedExpr = CE->getSubExpr(); 266 ProgramStateRef State = C.getState(); 267 SVal CastedVal = State->getSVal(CastedExpr, C.getLocationContext()); 268 269 const MemRegion *Region = CastedVal.getAsRegion(); 270 if (!Region) 271 return; 272 273 // Suppress reinterpret casted hits. 274 State = State->set<RegionState>(Region, AllocKind::Reinterpreted); 275 C.addTransition(State); 276 } 277 278 void PointerArithChecker::checkPreStmt(const CastExpr *CE, 279 CheckerContext &C) const { 280 if (CE->getCastKind() != CastKind::CK_ArrayToPointerDecay) 281 return; 282 283 const Expr *CastedExpr = CE->getSubExpr(); 284 ProgramStateRef State = C.getState(); 285 SVal CastedVal = State->getSVal(CastedExpr, C.getLocationContext()); 286 287 const MemRegion *Region = CastedVal.getAsRegion(); 288 if (!Region) 289 return; 290 291 if (const AllocKind *Kind = State->get<RegionState>(Region)) { 292 if (*Kind == AllocKind::Array || *Kind == AllocKind::Reinterpreted) 293 return; 294 } 295 State = State->set<RegionState>(Region, AllocKind::Array); 296 C.addTransition(State); 297 } 298 299 void PointerArithChecker::checkPreStmt(const UnaryOperator *UOp, 300 CheckerContext &C) const { 301 if (!UOp->isIncrementDecrementOp() || !UOp->getType()->isPointerType()) 302 return; 303 reportPointerArithMisuse(UOp->getSubExpr(), C, true); 304 } 305 306 void PointerArithChecker::checkPreStmt(const ArraySubscriptExpr *SubsExpr, 307 CheckerContext &C) const { 308 ProgramStateRef State = C.getState(); 309 SVal Idx = State->getSVal(SubsExpr->getIdx(), C.getLocationContext()); 310 311 // Indexing with 0 is OK. 312 if (Idx.isZeroConstant()) 313 return; 314 reportPointerArithMisuse(SubsExpr->getBase(), C); 315 } 316 317 void PointerArithChecker::checkPreStmt(const BinaryOperator *BOp, 318 CheckerContext &C) const { 319 BinaryOperatorKind OpKind = BOp->getOpcode(); 320 if (!BOp->isAdditiveOp() && OpKind != BO_AddAssign && OpKind != BO_SubAssign) 321 return; 322 323 const Expr *Lhs = BOp->getLHS(); 324 const Expr *Rhs = BOp->getRHS(); 325 ProgramStateRef State = C.getState(); 326 327 if (Rhs->getType()->isIntegerType() && Lhs->getType()->isPointerType()) { 328 SVal RHSVal = State->getSVal(Rhs, C.getLocationContext()); 329 if (State->isNull(RHSVal).isConstrainedTrue()) 330 return; 331 reportPointerArithMisuse(Lhs, C, !BOp->isAdditiveOp()); 332 } 333 // The int += ptr; case is not valid C++. 334 if (Lhs->getType()->isIntegerType() && Rhs->getType()->isPointerType()) { 335 SVal LHSVal = State->getSVal(Lhs, C.getLocationContext()); 336 if (State->isNull(LHSVal).isConstrainedTrue()) 337 return; 338 reportPointerArithMisuse(Rhs, C); 339 } 340 } 341 342 void ento::registerPointerArithChecker(CheckerManager &mgr) { 343 mgr.registerChecker<PointerArithChecker>(); 344 } 345