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
29using namespace clang;
30using namespace ento;
31
32namespace {
33class 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
40public:
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
55private:
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
95static bool isInfeasibleCast(const DynamicCastInfo *CastInfo,
96                             bool CastSucceeds) {
97  if (!CastInfo)
98    return false;
99
100  return CastSucceeds ? CastInfo->fails() : CastInfo->succeeds();
101}
102
103static 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
141static 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
155static 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
216static 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
262static 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
270static void evalNonNullParamNullReturn(const CallEvent &Call,
271                                       DefinedOrUnknownSVal DV,
272                                       CheckerContext &C) {
273  addCastTransition(Call, DV, C, /*IsNonNullParam=*/true,
274                    /*IsNonNullReturn=*/false);
275}
276
277static 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
288void CastValueChecker::evalCast(const CallEvent &Call, DefinedOrUnknownSVal DV,
289                                CheckerContext &C) const {
290  evalNonNullParamNonNullReturn(Call, DV, C, /*IsCheckedCast=*/true);
291}
292
293void CastValueChecker::evalDynCast(const CallEvent &Call,
294                                   DefinedOrUnknownSVal DV,
295                                   CheckerContext &C) const {
296  evalNonNullParamNonNullReturn(Call, DV, C);
297  evalNonNullParamNullReturn(Call, DV, C);
298}
299
300void CastValueChecker::evalCastOrNull(const CallEvent &Call,
301                                      DefinedOrUnknownSVal DV,
302                                      CheckerContext &C) const {
303  evalNonNullParamNonNullReturn(Call, DV, C);
304  evalNullParamNullReturn(Call, DV, C);
305}
306
307void 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
319static 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
327static void evalZeroParamNullReturn(const CallEvent &Call,
328                                    DefinedOrUnknownSVal DV,
329                                    CheckerContext &C) {
330  addCastTransition(Call, DV, C, /*IsNonNullParam=*/true,
331                    /*IsNonNullReturn=*/false);
332}
333
334void CastValueChecker::evalCastAs(const CallEvent &Call,
335                                  DefinedOrUnknownSVal DV,
336                                  CheckerContext &C) const {
337  evalZeroParamNonNullReturn(Call, DV, C, /*IsCheckedCast=*/true);
338}
339
340void 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
350void 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
365void 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
385bool 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
435void ento::registerCastValueChecker(CheckerManager &Mgr) {
436  Mgr.registerChecker<CastValueChecker>();
437}
438
439bool ento::shouldRegisterCastValueChecker(const LangOptions &LO) {
440  return true;
441}
442