contrib/llvm/tools/clang/lib/StaticAnalyzer/Checkers/PointerArithChecker.cpp

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