1 //===- CastValueChecker - Model implementation of custom RTTIs --*- 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 defines CastValueChecker which models casts of custom RTTIs.
10 //
11 // TODO list:
12 // - It only allows one succesful cast between two types however in the wild
13 //   the object could be casted to multiple types.
14 // - It needs to check the most likely type information from the dynamic type
15 //   map to increase precision of dynamic casting.
16 //
17 //===----------------------------------------------------------------------===//
18 
19 #include "clang/AST/DeclTemplate.h"
20 #include "clang/StaticAnalyzer/Checkers/BuiltinCheckerRegistration.h"
21 #include "clang/StaticAnalyzer/Core/Checker.h"
22 #include "clang/StaticAnalyzer/Core/CheckerManager.h"
23 #include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
24 #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
25 #include "clang/StaticAnalyzer/Core/PathSensitive/DynamicType.h"
26 #include "llvm/ADT/Optional.h"
27 #include <utility>
28 
29 using namespace clang;
30 using namespace ento;
31 
32 namespace {
33 class CastValueChecker : public Checker<check::DeadSymbols, eval::Call> {
34   enum class CallKind { Function, Method, InstanceOf };
35 
36   using CastCheck =
37       std::function<void(const CastValueChecker *, const CallEvent &Call,
38                          DefinedOrUnknownSVal, CheckerContext &)>;
39 
40 public:
41   // We have five cases to evaluate a cast:
42   // 1) The parameter is non-null, the return value is non-null.
43   // 2) The parameter is non-null, the return value is null.
44   // 3) The parameter is null, the return value is null.
45   // cast: 1;  dyn_cast: 1, 2;  cast_or_null: 1, 3;  dyn_cast_or_null: 1, 2, 3.
46   //
47   // 4) castAs: Has no parameter, the return value is non-null.
48   // 5) getAs:  Has no parameter, the return value is null or non-null.
49   //
50   // We have two cases to check the parameter is an instance of the given type.
51   // 1) isa:             The parameter is non-null, returns boolean.
52   // 2) isa_and_nonnull: The parameter is null or non-null, returns boolean.
53   bool evalCall(const CallEvent &Call, CheckerContext &C) const;
54   void checkDeadSymbols(SymbolReaper &SR, CheckerContext &C) const;
55 
56 private:
57   // These are known in the LLVM project. The pairs are in the following form:
58   // {{{namespace, call}, argument-count}, {callback, kind}}
59   const CallDescriptionMap<std::pair<CastCheck, CallKind>> CDM = {
60       {{{"llvm", "cast"}, 1},
61        {&CastValueChecker::evalCast, CallKind::Function}},
62       {{{"llvm", "dyn_cast"}, 1},
63        {&CastValueChecker::evalDynCast, CallKind::Function}},
64       {{{"llvm", "cast_or_null"}, 1},
65        {&CastValueChecker::evalCastOrNull, CallKind::Function}},
66       {{{"llvm", "dyn_cast_or_null"}, 1},
67        {&CastValueChecker::evalDynCastOrNull, CallKind::Function}},
68       {{{"clang", "castAs"}, 0},
69        {&CastValueChecker::evalCastAs, CallKind::Method}},
70       {{{"clang", "getAs"}, 0},
71        {&CastValueChecker::evalGetAs, CallKind::Method}},
72       {{{"llvm", "isa"}, 1},
73        {&CastValueChecker::evalIsa, CallKind::InstanceOf}},
74       {{{"llvm", "isa_and_nonnull"}, 1},
75        {&CastValueChecker::evalIsaAndNonNull, CallKind::InstanceOf}}};
76 
77   void evalCast(const CallEvent &Call, DefinedOrUnknownSVal DV,
78                 CheckerContext &C) const;
79   void evalDynCast(const CallEvent &Call, DefinedOrUnknownSVal DV,
80                    CheckerContext &C) const;
81   void evalCastOrNull(const CallEvent &Call, DefinedOrUnknownSVal DV,
82                       CheckerContext &C) const;
83   void evalDynCastOrNull(const CallEvent &Call, DefinedOrUnknownSVal DV,
84                          CheckerContext &C) const;
85   void evalCastAs(const CallEvent &Call, DefinedOrUnknownSVal DV,
86                   CheckerContext &C) const;
87   void evalGetAs(const CallEvent &Call, DefinedOrUnknownSVal DV,
88                  CheckerContext &C) const;
89   void evalIsa(const CallEvent &Call, DefinedOrUnknownSVal DV,
90                CheckerContext &C) const;
91   void evalIsaAndNonNull(const CallEvent &Call, DefinedOrUnknownSVal DV,
92                          CheckerContext &C) const;
93 };
94 } // namespace
95 
96 static bool isInfeasibleCast(const DynamicCastInfo *CastInfo,
97                              bool CastSucceeds) {
98   if (!CastInfo)
99     return false;
100 
101   return CastSucceeds ? CastInfo->fails() : CastInfo->succeeds();
102 }
103 
104 static const NoteTag *getNoteTag(CheckerContext &C,
105                                  const DynamicCastInfo *CastInfo,
106                                  QualType CastToTy, const Expr *Object,
107                                  bool CastSucceeds, bool IsKnownCast) {
108   std::string CastToName =
109       CastInfo ? CastInfo->to()->getAsCXXRecordDecl()->getNameAsString()
110                : CastToTy->getPointeeCXXRecordDecl()->getNameAsString();
111   Object = Object->IgnoreParenImpCasts();
112 
113   return C.getNoteTag(
114       [=]() -> std::string {
115         SmallString<128> Msg;
116         llvm::raw_svector_ostream Out(Msg);
117 
118         if (!IsKnownCast)
119           Out << "Assuming ";
120 
121         if (const auto *DRE = dyn_cast<DeclRefExpr>(Object)) {
122           Out << '\'' << DRE->getDecl()->getNameAsString() << '\'';
123         } else if (const auto *ME = dyn_cast<MemberExpr>(Object)) {
124           Out << (IsKnownCast ? "Field '" : "field '")
125               << ME->getMemberDecl()->getNameAsString() << '\'';
126         } else {
127           Out << (IsKnownCast ? "The object" : "the object");
128         }
129 
130         Out << ' ' << (CastSucceeds ? "is a" : "is not a") << " '" << CastToName
131             << '\'';
132 
133         return std::string(Out.str());
134       },
135       /*IsPrunable=*/true);
136 }
137 
138 static const NoteTag *getNoteTag(CheckerContext &C,
139                                  SmallVector<QualType, 4> CastToTyVec,
140                                  const Expr *Object,
141                                  bool IsKnownCast) {
142   Object = Object->IgnoreParenImpCasts();
143 
144   return C.getNoteTag(
145       [=]() -> std::string {
146         SmallString<128> Msg;
147         llvm::raw_svector_ostream Out(Msg);
148 
149         if (!IsKnownCast)
150           Out << "Assuming ";
151 
152         if (const auto *DRE = dyn_cast<DeclRefExpr>(Object)) {
153           Out << '\'' << DRE->getDecl()->getNameAsString() << '\'';
154         } else if (const auto *ME = dyn_cast<MemberExpr>(Object)) {
155           Out << (IsKnownCast ? "Field '" : "field '")
156               << ME->getMemberDecl()->getNameAsString() << '\'';
157         } else {
158           Out << (IsKnownCast ? "The object" : "the object");
159         }
160         Out << " is";
161 
162         bool First = true;
163         for (QualType CastToTy: CastToTyVec) {
164           std::string CastToName =
165             CastToTy->getAsCXXRecordDecl() ?
166             CastToTy->getAsCXXRecordDecl()->getNameAsString() :
167             CastToTy->getPointeeCXXRecordDecl()->getNameAsString();
168           Out << ' ' << ((CastToTyVec.size() == 1) ? "not" :
169                          (First ? "neither" : "nor")) << " a '" << CastToName
170               << '\'';
171           First = false;
172         }
173 
174         return std::string(Out.str());
175       },
176       /*IsPrunable=*/true);
177 }
178 
179 //===----------------------------------------------------------------------===//
180 // Main logic to evaluate a cast.
181 //===----------------------------------------------------------------------===//
182 
183 static QualType alignReferenceTypes(QualType toAlign, QualType alignTowards,
184                                     ASTContext &ACtx) {
185   if (alignTowards->isLValueReferenceType() &&
186       alignTowards.isConstQualified()) {
187     toAlign.addConst();
188     return ACtx.getLValueReferenceType(toAlign);
189   } else if (alignTowards->isLValueReferenceType())
190     return ACtx.getLValueReferenceType(toAlign);
191   else if (alignTowards->isRValueReferenceType())
192     return ACtx.getRValueReferenceType(toAlign);
193 
194   llvm_unreachable("Must align towards a reference type!");
195 }
196 
197 static void addCastTransition(const CallEvent &Call, DefinedOrUnknownSVal DV,
198                               CheckerContext &C, bool IsNonNullParam,
199                               bool IsNonNullReturn,
200                               bool IsCheckedCast = false) {
201   ProgramStateRef State = C.getState()->assume(DV, IsNonNullParam);
202   if (!State)
203     return;
204 
205   const Expr *Object;
206   QualType CastFromTy;
207   QualType CastToTy = Call.getResultType();
208 
209   if (Call.getNumArgs() > 0) {
210     Object = Call.getArgExpr(0);
211     CastFromTy = Call.parameters()[0]->getType();
212   } else {
213     Object = cast<CXXInstanceCall>(&Call)->getCXXThisExpr();
214     CastFromTy = Object->getType();
215     if (CastToTy->isPointerType()) {
216       if (!CastFromTy->isPointerType())
217         return;
218     } else {
219       if (!CastFromTy->isReferenceType())
220         return;
221 
222       CastFromTy = alignReferenceTypes(CastFromTy, CastToTy, C.getASTContext());
223     }
224   }
225 
226   const MemRegion *MR = DV.getAsRegion();
227   const DynamicCastInfo *CastInfo =
228       getDynamicCastInfo(State, MR, CastFromTy, CastToTy);
229 
230   // We assume that every checked cast succeeds.
231   bool CastSucceeds = IsCheckedCast || CastFromTy == CastToTy;
232   if (!CastSucceeds) {
233     if (CastInfo)
234       CastSucceeds = IsNonNullReturn && CastInfo->succeeds();
235     else
236       CastSucceeds = IsNonNullReturn;
237   }
238 
239   // Check for infeasible casts.
240   if (isInfeasibleCast(CastInfo, CastSucceeds)) {
241     C.generateSink(State, C.getPredecessor());
242     return;
243   }
244 
245   // Store the type and the cast information.
246   bool IsKnownCast = CastInfo || IsCheckedCast || CastFromTy == CastToTy;
247   if (!IsKnownCast || IsCheckedCast)
248     State = setDynamicTypeAndCastInfo(State, MR, CastFromTy, CastToTy,
249                                       CastSucceeds);
250 
251   SVal V = CastSucceeds ? C.getSValBuilder().evalCast(DV, CastToTy, CastFromTy)
252                         : C.getSValBuilder().makeNull();
253   C.addTransition(
254       State->BindExpr(Call.getOriginExpr(), C.getLocationContext(), V, false),
255       getNoteTag(C, CastInfo, CastToTy, Object, CastSucceeds, IsKnownCast));
256 }
257 
258 static void addInstanceOfTransition(const CallEvent &Call,
259                                     DefinedOrUnknownSVal DV,
260                                     ProgramStateRef State, CheckerContext &C,
261                                     bool IsInstanceOf) {
262   const FunctionDecl *FD = Call.getDecl()->getAsFunction();
263   QualType CastFromTy = Call.parameters()[0]->getType();
264   SmallVector<QualType, 4> CastToTyVec;
265   for (unsigned idx = 0; idx < FD->getTemplateSpecializationArgs()->size() - 1;
266        ++idx) {
267     TemplateArgument CastToTempArg =
268       FD->getTemplateSpecializationArgs()->get(idx);
269     switch (CastToTempArg.getKind()) {
270     default:
271       return;
272     case TemplateArgument::Type:
273       CastToTyVec.push_back(CastToTempArg.getAsType());
274       break;
275     case TemplateArgument::Pack:
276       for (TemplateArgument ArgInPack: CastToTempArg.pack_elements())
277         CastToTyVec.push_back(ArgInPack.getAsType());
278       break;
279     }
280   }
281 
282   const MemRegion *MR = DV.getAsRegion();
283   if (MR && CastFromTy->isReferenceType())
284     MR = State->getSVal(DV.castAs<Loc>()).getAsRegion();
285 
286   bool Success = false;
287   bool IsAnyKnown = false;
288   for (QualType CastToTy: CastToTyVec) {
289     if (CastFromTy->isPointerType())
290       CastToTy = C.getASTContext().getPointerType(CastToTy);
291     else if (CastFromTy->isReferenceType())
292       CastToTy = alignReferenceTypes(CastToTy, CastFromTy, C.getASTContext());
293     else
294       return;
295 
296     const DynamicCastInfo *CastInfo =
297       getDynamicCastInfo(State, MR, CastFromTy, CastToTy);
298 
299     bool CastSucceeds;
300     if (CastInfo)
301       CastSucceeds = IsInstanceOf && CastInfo->succeeds();
302     else
303       CastSucceeds = IsInstanceOf || CastFromTy == CastToTy;
304 
305     // Store the type and the cast information.
306     bool IsKnownCast = CastInfo || CastFromTy == CastToTy;
307     IsAnyKnown = IsAnyKnown || IsKnownCast;
308     ProgramStateRef NewState = State;
309     if (!IsKnownCast)
310       NewState = setDynamicTypeAndCastInfo(State, MR, CastFromTy, CastToTy,
311                                            IsInstanceOf);
312 
313     if (CastSucceeds) {
314       Success = true;
315       C.addTransition(
316           NewState->BindExpr(Call.getOriginExpr(), C.getLocationContext(),
317                              C.getSValBuilder().makeTruthVal(true)),
318           getNoteTag(C, CastInfo, CastToTy, Call.getArgExpr(0), true,
319                      IsKnownCast));
320       if (IsKnownCast)
321         return;
322     } else if (CastInfo && CastInfo->succeeds()) {
323       C.generateSink(NewState, C.getPredecessor());
324       return;
325     }
326   }
327 
328   if (!Success) {
329     C.addTransition(
330         State->BindExpr(Call.getOriginExpr(), C.getLocationContext(),
331                         C.getSValBuilder().makeTruthVal(false)),
332         getNoteTag(C, CastToTyVec, Call.getArgExpr(0), IsAnyKnown));
333   }
334 }
335 
336 //===----------------------------------------------------------------------===//
337 // Evaluating cast, dyn_cast, cast_or_null, dyn_cast_or_null.
338 //===----------------------------------------------------------------------===//
339 
340 static void evalNonNullParamNonNullReturn(const CallEvent &Call,
341                                           DefinedOrUnknownSVal DV,
342                                           CheckerContext &C,
343                                           bool IsCheckedCast = false) {
344   addCastTransition(Call, DV, C, /*IsNonNullParam=*/true,
345                     /*IsNonNullReturn=*/true, IsCheckedCast);
346 }
347 
348 static void evalNonNullParamNullReturn(const CallEvent &Call,
349                                        DefinedOrUnknownSVal DV,
350                                        CheckerContext &C) {
351   addCastTransition(Call, DV, C, /*IsNonNullParam=*/true,
352                     /*IsNonNullReturn=*/false);
353 }
354 
355 static void evalNullParamNullReturn(const CallEvent &Call,
356                                     DefinedOrUnknownSVal DV,
357                                     CheckerContext &C) {
358   if (ProgramStateRef State = C.getState()->assume(DV, false))
359     C.addTransition(State->BindExpr(Call.getOriginExpr(),
360                                     C.getLocationContext(),
361                                     C.getSValBuilder().makeNull(), false),
362                     C.getNoteTag("Assuming null pointer is passed into cast",
363                                  /*IsPrunable=*/true));
364 }
365 
366 void CastValueChecker::evalCast(const CallEvent &Call, DefinedOrUnknownSVal DV,
367                                 CheckerContext &C) const {
368   evalNonNullParamNonNullReturn(Call, DV, C, /*IsCheckedCast=*/true);
369 }
370 
371 void CastValueChecker::evalDynCast(const CallEvent &Call,
372                                    DefinedOrUnknownSVal DV,
373                                    CheckerContext &C) const {
374   evalNonNullParamNonNullReturn(Call, DV, C);
375   evalNonNullParamNullReturn(Call, DV, C);
376 }
377 
378 void CastValueChecker::evalCastOrNull(const CallEvent &Call,
379                                       DefinedOrUnknownSVal DV,
380                                       CheckerContext &C) const {
381   evalNonNullParamNonNullReturn(Call, DV, C);
382   evalNullParamNullReturn(Call, DV, C);
383 }
384 
385 void CastValueChecker::evalDynCastOrNull(const CallEvent &Call,
386                                          DefinedOrUnknownSVal DV,
387                                          CheckerContext &C) const {
388   evalNonNullParamNonNullReturn(Call, DV, C);
389   evalNonNullParamNullReturn(Call, DV, C);
390   evalNullParamNullReturn(Call, DV, C);
391 }
392 
393 //===----------------------------------------------------------------------===//
394 // Evaluating castAs, getAs.
395 //===----------------------------------------------------------------------===//
396 
397 static void evalZeroParamNonNullReturn(const CallEvent &Call,
398                                        DefinedOrUnknownSVal DV,
399                                        CheckerContext &C,
400                                        bool IsCheckedCast = false) {
401   addCastTransition(Call, DV, C, /*IsNonNullParam=*/true,
402                     /*IsNonNullReturn=*/true, IsCheckedCast);
403 }
404 
405 static void evalZeroParamNullReturn(const CallEvent &Call,
406                                     DefinedOrUnknownSVal DV,
407                                     CheckerContext &C) {
408   addCastTransition(Call, DV, C, /*IsNonNullParam=*/true,
409                     /*IsNonNullReturn=*/false);
410 }
411 
412 void CastValueChecker::evalCastAs(const CallEvent &Call,
413                                   DefinedOrUnknownSVal DV,
414                                   CheckerContext &C) const {
415   evalZeroParamNonNullReturn(Call, DV, C, /*IsCheckedCast=*/true);
416 }
417 
418 void CastValueChecker::evalGetAs(const CallEvent &Call, DefinedOrUnknownSVal DV,
419                                  CheckerContext &C) const {
420   evalZeroParamNonNullReturn(Call, DV, C);
421   evalZeroParamNullReturn(Call, DV, C);
422 }
423 
424 //===----------------------------------------------------------------------===//
425 // Evaluating isa, isa_and_nonnull.
426 //===----------------------------------------------------------------------===//
427 
428 void CastValueChecker::evalIsa(const CallEvent &Call, DefinedOrUnknownSVal DV,
429                                CheckerContext &C) const {
430   ProgramStateRef NonNullState, NullState;
431   std::tie(NonNullState, NullState) = C.getState()->assume(DV);
432 
433   if (NonNullState) {
434     addInstanceOfTransition(Call, DV, NonNullState, C, /*IsInstanceOf=*/true);
435     addInstanceOfTransition(Call, DV, NonNullState, C, /*IsInstanceOf=*/false);
436   }
437 
438   if (NullState) {
439     C.generateSink(NullState, C.getPredecessor());
440   }
441 }
442 
443 void CastValueChecker::evalIsaAndNonNull(const CallEvent &Call,
444                                          DefinedOrUnknownSVal DV,
445                                          CheckerContext &C) const {
446   ProgramStateRef NonNullState, NullState;
447   std::tie(NonNullState, NullState) = C.getState()->assume(DV);
448 
449   if (NonNullState) {
450     addInstanceOfTransition(Call, DV, NonNullState, C, /*IsInstanceOf=*/true);
451     addInstanceOfTransition(Call, DV, NonNullState, C, /*IsInstanceOf=*/false);
452   }
453 
454   if (NullState) {
455     addInstanceOfTransition(Call, DV, NullState, C, /*IsInstanceOf=*/false);
456   }
457 }
458 
459 //===----------------------------------------------------------------------===//
460 // Main logic to evaluate a call.
461 //===----------------------------------------------------------------------===//
462 
463 bool CastValueChecker::evalCall(const CallEvent &Call,
464                                 CheckerContext &C) const {
465   const auto *Lookup = CDM.lookup(Call);
466   if (!Lookup)
467     return false;
468 
469   const CastCheck &Check = Lookup->first;
470   CallKind Kind = Lookup->second;
471 
472   Optional<DefinedOrUnknownSVal> DV;
473 
474   switch (Kind) {
475   case CallKind::Function: {
476     // We only model casts from pointers to pointers or from references
477     // to references. Other casts are most likely specialized and we
478     // cannot model them.
479     QualType ParamT = Call.parameters()[0]->getType();
480     QualType ResultT = Call.getResultType();
481     if (!(ParamT->isPointerType() && ResultT->isPointerType()) &&
482         !(ParamT->isReferenceType() && ResultT->isReferenceType())) {
483       return false;
484     }
485 
486     DV = Call.getArgSVal(0).getAs<DefinedOrUnknownSVal>();
487     break;
488   }
489   case CallKind::InstanceOf: {
490     // We need to obtain the only template argument to determinte the type.
491     const FunctionDecl *FD = Call.getDecl()->getAsFunction();
492     if (!FD || !FD->getTemplateSpecializationArgs())
493       return false;
494 
495     DV = Call.getArgSVal(0).getAs<DefinedOrUnknownSVal>();
496     break;
497   }
498   case CallKind::Method:
499     const auto *InstanceCall = dyn_cast<CXXInstanceCall>(&Call);
500     if (!InstanceCall)
501       return false;
502 
503     DV = InstanceCall->getCXXThisVal().getAs<DefinedOrUnknownSVal>();
504     break;
505   }
506 
507   if (!DV)
508     return false;
509 
510   Check(this, Call, *DV, C);
511   return true;
512 }
513 
514 void CastValueChecker::checkDeadSymbols(SymbolReaper &SR,
515                                         CheckerContext &C) const {
516   C.addTransition(removeDeadCasts(C.getState(), SR));
517 }
518 
519 void ento::registerCastValueChecker(CheckerManager &Mgr) {
520   Mgr.registerChecker<CastValueChecker>();
521 }
522 
523 bool ento::shouldRegisterCastValueChecker(const CheckerManager &mgr) {
524   return true;
525 }
526