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