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<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 
55 private:
56   // These are known in the LLVM project. The pairs are in the following form:
57   // {{{namespace, call}, argument-count}, {callback, kind}}
58   const CallDescriptionMap<std::pair<CastCheck, CallKind>> CDM = {
59       {{{"llvm", "cast"}, 1},
60        {&CastValueChecker::evalCast, CallKind::Function}},
61       {{{"llvm", "dyn_cast"}, 1},
62        {&CastValueChecker::evalDynCast, CallKind::Function}},
63       {{{"llvm", "cast_or_null"}, 1},
64        {&CastValueChecker::evalCastOrNull, CallKind::Function}},
65       {{{"llvm", "dyn_cast_or_null"}, 1},
66        {&CastValueChecker::evalDynCastOrNull, CallKind::Function}},
67       {{{"clang", "castAs"}, 0},
68        {&CastValueChecker::evalCastAs, CallKind::Method}},
69       {{{"clang", "getAs"}, 0},
70        {&CastValueChecker::evalGetAs, CallKind::Method}},
71       {{{"llvm", "isa"}, 1},
72        {&CastValueChecker::evalIsa, CallKind::InstanceOf}},
73       {{{"llvm", "isa_and_nonnull"}, 1},
74        {&CastValueChecker::evalIsaAndNonNull, CallKind::InstanceOf}}};
75 
76   void evalCast(const CallEvent &Call, DefinedOrUnknownSVal DV,
77                 CheckerContext &C) const;
78   void evalDynCast(const CallEvent &Call, DefinedOrUnknownSVal DV,
79                    CheckerContext &C) const;
80   void evalCastOrNull(const CallEvent &Call, DefinedOrUnknownSVal DV,
81                       CheckerContext &C) const;
82   void evalDynCastOrNull(const CallEvent &Call, DefinedOrUnknownSVal DV,
83                          CheckerContext &C) const;
84   void evalCastAs(const CallEvent &Call, DefinedOrUnknownSVal DV,
85                   CheckerContext &C) const;
86   void evalGetAs(const CallEvent &Call, DefinedOrUnknownSVal DV,
87                  CheckerContext &C) const;
88   void evalIsa(const CallEvent &Call, DefinedOrUnknownSVal DV,
89                CheckerContext &C) const;
90   void evalIsaAndNonNull(const CallEvent &Call, DefinedOrUnknownSVal DV,
91                          CheckerContext &C) const;
92 };
93 } // namespace
94 
95 static bool isInfeasibleCast(const DynamicCastInfo *CastInfo,
96                              bool CastSucceeds) {
97   if (!CastInfo)
98     return false;
99 
100   return CastSucceeds ? CastInfo->fails() : CastInfo->succeeds();
101 }
102 
103 static const NoteTag *getNoteTag(CheckerContext &C,
104                                  const DynamicCastInfo *CastInfo,
105                                  QualType CastToTy, const Expr *Object,
106                                  bool CastSucceeds, bool IsKnownCast) {
107   std::string CastToName =
108       CastInfo ? CastInfo->to()->getPointeeCXXRecordDecl()->getNameAsString()
109                : CastToTy->getPointeeCXXRecordDecl()->getNameAsString();
110   Object = Object->IgnoreParenImpCasts();
111 
112   return C.getNoteTag(
113       [=]() -> std::string {
114         SmallString<128> Msg;
115         llvm::raw_svector_ostream Out(Msg);
116 
117         if (!IsKnownCast)
118           Out << "Assuming ";
119 
120         if (const auto *DRE = dyn_cast<DeclRefExpr>(Object)) {
121           Out << '\'' << DRE->getDecl()->getNameAsString() << '\'';
122         } else if (const auto *ME = dyn_cast<MemberExpr>(Object)) {
123           Out << (IsKnownCast ? "Field '" : "field '")
124               << ME->getMemberDecl()->getNameAsString() << '\'';
125         } else {
126           Out << (IsKnownCast ? "The object" : "the object");
127         }
128 
129         Out << ' ' << (CastSucceeds ? "is a" : "is not a") << " '" << CastToName
130             << '\'';
131 
132         return Out.str();
133       },
134       /*IsPrunable=*/true);
135 }
136 
137 //===----------------------------------------------------------------------===//
138 // Main logic to evaluate a cast.
139 //===----------------------------------------------------------------------===//
140 
141 static QualType alignReferenceTypes(QualType toAlign, QualType alignTowards,
142                                     ASTContext &ACtx) {
143   if (alignTowards->isLValueReferenceType() &&
144       alignTowards.isConstQualified()) {
145     toAlign.addConst();
146     return ACtx.getLValueReferenceType(toAlign);
147   } else if (alignTowards->isLValueReferenceType())
148     return ACtx.getLValueReferenceType(toAlign);
149   else if (alignTowards->isRValueReferenceType())
150     return ACtx.getRValueReferenceType(toAlign);
151 
152   llvm_unreachable("Must align towards a reference type!");
153 }
154 
155 static void addCastTransition(const CallEvent &Call, DefinedOrUnknownSVal DV,
156                               CheckerContext &C, bool IsNonNullParam,
157                               bool IsNonNullReturn,
158                               bool IsCheckedCast = false) {
159   ProgramStateRef State = C.getState()->assume(DV, IsNonNullParam);
160   if (!State)
161     return;
162 
163   const Expr *Object;
164   QualType CastFromTy;
165   QualType CastToTy = Call.getResultType();
166 
167   if (Call.getNumArgs() > 0) {
168     Object = Call.getArgExpr(0);
169     CastFromTy = Call.parameters()[0]->getType();
170   } else {
171     Object = cast<CXXInstanceCall>(&Call)->getCXXThisExpr();
172     CastFromTy = Object->getType();
173     if (CastToTy->isPointerType()) {
174       if (!CastFromTy->isPointerType())
175         return;
176     } else {
177       if (!CastFromTy->isReferenceType())
178         return;
179 
180       CastFromTy = alignReferenceTypes(CastFromTy, CastToTy, C.getASTContext());
181     }
182   }
183 
184   const MemRegion *MR = DV.getAsRegion();
185   const DynamicCastInfo *CastInfo =
186       getDynamicCastInfo(State, MR, CastFromTy, CastToTy);
187 
188   // We assume that every checked cast succeeds.
189   bool CastSucceeds = IsCheckedCast || CastFromTy == CastToTy;
190   if (!CastSucceeds) {
191     if (CastInfo)
192       CastSucceeds = IsNonNullReturn && CastInfo->succeeds();
193     else
194       CastSucceeds = IsNonNullReturn;
195   }
196 
197   // Check for infeasible casts.
198   if (isInfeasibleCast(CastInfo, CastSucceeds)) {
199     C.generateSink(State, C.getPredecessor());
200     return;
201   }
202 
203   // Store the type and the cast information.
204   bool IsKnownCast = CastInfo || IsCheckedCast || CastFromTy == CastToTy;
205   if (!IsKnownCast || IsCheckedCast)
206     State = setDynamicTypeAndCastInfo(State, MR, CastFromTy, CastToTy,
207                                       CastSucceeds);
208 
209   SVal V = CastSucceeds ? C.getSValBuilder().evalCast(DV, CastToTy, CastFromTy)
210                         : C.getSValBuilder().makeNull();
211   C.addTransition(
212       State->BindExpr(Call.getOriginExpr(), C.getLocationContext(), V, false),
213       getNoteTag(C, CastInfo, CastToTy, Object, CastSucceeds, IsKnownCast));
214 }
215 
216 static void addInstanceOfTransition(const CallEvent &Call,
217                                     DefinedOrUnknownSVal DV,
218                                     ProgramStateRef State, CheckerContext &C,
219                                     bool IsInstanceOf) {
220   const FunctionDecl *FD = Call.getDecl()->getAsFunction();
221   QualType CastFromTy = Call.parameters()[0]->getType();
222   QualType CastToTy = FD->getTemplateSpecializationArgs()->get(0).getAsType();
223   if (CastFromTy->isPointerType())
224     CastToTy = C.getASTContext().getPointerType(CastToTy);
225   else if (CastFromTy->isReferenceType())
226     CastToTy = alignReferenceTypes(CastToTy, CastFromTy, C.getASTContext());
227   else
228     return;
229 
230   const MemRegion *MR = DV.getAsRegion();
231   const DynamicCastInfo *CastInfo =
232       getDynamicCastInfo(State, MR, CastFromTy, CastToTy);
233 
234   bool CastSucceeds;
235   if (CastInfo)
236     CastSucceeds = IsInstanceOf && CastInfo->succeeds();
237   else
238     CastSucceeds = IsInstanceOf || CastFromTy == CastToTy;
239 
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 || CastFromTy == CastToTy;
247   if (!IsKnownCast)
248     State = setDynamicTypeAndCastInfo(State, MR, CastFromTy, CastToTy,
249                                       IsInstanceOf);
250 
251   C.addTransition(
252       State->BindExpr(Call.getOriginExpr(), C.getLocationContext(),
253                       C.getSValBuilder().makeTruthVal(CastSucceeds)),
254       getNoteTag(C, CastInfo, CastToTy, Call.getArgExpr(0), CastSucceeds,
255                  IsKnownCast));
256 }
257 
258 //===----------------------------------------------------------------------===//
259 // Evaluating cast, dyn_cast, cast_or_null, dyn_cast_or_null.
260 //===----------------------------------------------------------------------===//
261 
262 static void evalNonNullParamNonNullReturn(const CallEvent &Call,
263                                           DefinedOrUnknownSVal DV,
264                                           CheckerContext &C,
265                                           bool IsCheckedCast = false) {
266   addCastTransition(Call, DV, C, /*IsNonNullParam=*/true,
267                     /*IsNonNullReturn=*/true, IsCheckedCast);
268 }
269 
270 static void evalNonNullParamNullReturn(const CallEvent &Call,
271                                        DefinedOrUnknownSVal DV,
272                                        CheckerContext &C) {
273   addCastTransition(Call, DV, C, /*IsNonNullParam=*/true,
274                     /*IsNonNullReturn=*/false);
275 }
276 
277 static void evalNullParamNullReturn(const CallEvent &Call,
278                                     DefinedOrUnknownSVal DV,
279                                     CheckerContext &C) {
280   if (ProgramStateRef State = C.getState()->assume(DV, false))
281     C.addTransition(State->BindExpr(Call.getOriginExpr(),
282                                     C.getLocationContext(),
283                                     C.getSValBuilder().makeNull(), false),
284                     C.getNoteTag("Assuming null pointer is passed into cast",
285                                  /*IsPrunable=*/true));
286 }
287 
288 void CastValueChecker::evalCast(const CallEvent &Call, DefinedOrUnknownSVal DV,
289                                 CheckerContext &C) const {
290   evalNonNullParamNonNullReturn(Call, DV, C, /*IsCheckedCast=*/true);
291 }
292 
293 void CastValueChecker::evalDynCast(const CallEvent &Call,
294                                    DefinedOrUnknownSVal DV,
295                                    CheckerContext &C) const {
296   evalNonNullParamNonNullReturn(Call, DV, C);
297   evalNonNullParamNullReturn(Call, DV, C);
298 }
299 
300 void CastValueChecker::evalCastOrNull(const CallEvent &Call,
301                                       DefinedOrUnknownSVal DV,
302                                       CheckerContext &C) const {
303   evalNonNullParamNonNullReturn(Call, DV, C);
304   evalNullParamNullReturn(Call, DV, C);
305 }
306 
307 void CastValueChecker::evalDynCastOrNull(const CallEvent &Call,
308                                          DefinedOrUnknownSVal DV,
309                                          CheckerContext &C) const {
310   evalNonNullParamNonNullReturn(Call, DV, C);
311   evalNonNullParamNullReturn(Call, DV, C);
312   evalNullParamNullReturn(Call, DV, C);
313 }
314 
315 //===----------------------------------------------------------------------===//
316 // Evaluating castAs, getAs.
317 //===----------------------------------------------------------------------===//
318 
319 static void evalZeroParamNonNullReturn(const CallEvent &Call,
320                                        DefinedOrUnknownSVal DV,
321                                        CheckerContext &C,
322                                        bool IsCheckedCast = false) {
323   addCastTransition(Call, DV, C, /*IsNonNullParam=*/true,
324                     /*IsNonNullReturn=*/true, IsCheckedCast);
325 }
326 
327 static void evalZeroParamNullReturn(const CallEvent &Call,
328                                     DefinedOrUnknownSVal DV,
329                                     CheckerContext &C) {
330   addCastTransition(Call, DV, C, /*IsNonNullParam=*/true,
331                     /*IsNonNullReturn=*/false);
332 }
333 
334 void CastValueChecker::evalCastAs(const CallEvent &Call,
335                                   DefinedOrUnknownSVal DV,
336                                   CheckerContext &C) const {
337   evalZeroParamNonNullReturn(Call, DV, C, /*IsCheckedCast=*/true);
338 }
339 
340 void CastValueChecker::evalGetAs(const CallEvent &Call, DefinedOrUnknownSVal DV,
341                                  CheckerContext &C) const {
342   evalZeroParamNonNullReturn(Call, DV, C);
343   evalZeroParamNullReturn(Call, DV, C);
344 }
345 
346 //===----------------------------------------------------------------------===//
347 // Evaluating isa, isa_and_nonnull.
348 //===----------------------------------------------------------------------===//
349 
350 void CastValueChecker::evalIsa(const CallEvent &Call, DefinedOrUnknownSVal DV,
351                                CheckerContext &C) const {
352   ProgramStateRef NonNullState, NullState;
353   std::tie(NonNullState, NullState) = C.getState()->assume(DV);
354 
355   if (NonNullState) {
356     addInstanceOfTransition(Call, DV, NonNullState, C, /*IsInstanceOf=*/true);
357     addInstanceOfTransition(Call, DV, NonNullState, C, /*IsInstanceOf=*/false);
358   }
359 
360   if (NullState) {
361     C.generateSink(NullState, C.getPredecessor());
362   }
363 }
364 
365 void CastValueChecker::evalIsaAndNonNull(const CallEvent &Call,
366                                          DefinedOrUnknownSVal DV,
367                                          CheckerContext &C) const {
368   ProgramStateRef NonNullState, NullState;
369   std::tie(NonNullState, NullState) = C.getState()->assume(DV);
370 
371   if (NonNullState) {
372     addInstanceOfTransition(Call, DV, NonNullState, C, /*IsInstanceOf=*/true);
373     addInstanceOfTransition(Call, DV, NonNullState, C, /*IsInstanceOf=*/false);
374   }
375 
376   if (NullState) {
377     addInstanceOfTransition(Call, DV, NullState, C, /*IsInstanceOf=*/false);
378   }
379 }
380 
381 //===----------------------------------------------------------------------===//
382 // Main logic to evaluate a call.
383 //===----------------------------------------------------------------------===//
384 
385 bool CastValueChecker::evalCall(const CallEvent &Call,
386                                 CheckerContext &C) const {
387   const auto *Lookup = CDM.lookup(Call);
388   if (!Lookup)
389     return false;
390 
391   const CastCheck &Check = Lookup->first;
392   CallKind Kind = Lookup->second;
393 
394   Optional<DefinedOrUnknownSVal> DV;
395 
396   switch (Kind) {
397   case CallKind::Function: {
398     // We only model casts from pointers to pointers or from references
399     // to references. Other casts are most likely specialized and we
400     // cannot model them.
401     QualType ParamT = Call.parameters()[0]->getType();
402     QualType ResultT = Call.getResultType();
403     if (!(ParamT->isPointerType() && ResultT->isPointerType()) &&
404         !(ParamT->isReferenceType() && ResultT->isReferenceType()))
405       return false;
406 
407     DV = Call.getArgSVal(0).getAs<DefinedOrUnknownSVal>();
408     break;
409   }
410   case CallKind::InstanceOf: {
411     // We need to obtain the only template argument to determinte the type.
412     const FunctionDecl *FD = Call.getDecl()->getAsFunction();
413     if (!FD || !FD->getTemplateSpecializationArgs())
414       return false;
415 
416     DV = Call.getArgSVal(0).getAs<DefinedOrUnknownSVal>();
417     break;
418   }
419   case CallKind::Method:
420     const auto *InstanceCall = dyn_cast<CXXInstanceCall>(&Call);
421     if (!InstanceCall)
422       return false;
423 
424     DV = InstanceCall->getCXXThisVal().getAs<DefinedOrUnknownSVal>();
425     break;
426   }
427 
428   if (!DV)
429     return false;
430 
431   Check(this, Call, *DV, C);
432   return true;
433 }
434 
435 void ento::registerCastValueChecker(CheckerManager &Mgr) {
436   Mgr.registerChecker<CastValueChecker>();
437 }
438 
439 bool ento::shouldRegisterCastValueChecker(const LangOptions &LO) {
440   return true;
441 }
442