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 <optional>
28#include <utility>
29
30using namespace clang;
31using namespace ento;
32
33namespace {
34class 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
41public:
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
57private:
58 // These are known in the LLVM project. The pairs are in the following form:
59 // {{match-mode, {namespace, call}, argument-count}, {callback, kind}}
60 const CallDescriptionMap<std::pair<CastCheck, CallKind>> CDM = {
61 {{CDM::SimpleFunc, {"llvm", "cast"}, 1},
62 {&CastValueChecker::evalCast, CallKind::Function}},
63 {{CDM::SimpleFunc, {"llvm", "dyn_cast"}, 1},
64 {&CastValueChecker::evalDynCast, CallKind::Function}},
65 {{CDM::SimpleFunc, {"llvm", "cast_or_null"}, 1},
66 {&CastValueChecker::evalCastOrNull, CallKind::Function}},
67 {{CDM::SimpleFunc, {"llvm", "dyn_cast_or_null"}, 1},
68 {&CastValueChecker::evalDynCastOrNull, CallKind::Function}},
69 {{CDM::CXXMethod, {"clang", "castAs"}, 0},
70 {&CastValueChecker::evalCastAs, CallKind::Method}},
71 {{CDM::CXXMethod, {"clang", "getAs"}, 0},
72 {&CastValueChecker::evalGetAs, CallKind::Method}},
73 {{CDM::SimpleFunc, {"llvm", "isa"}, 1},
74 {&CastValueChecker::evalIsa, CallKind::InstanceOf}},
75 {{CDM::SimpleFunc, {"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
97static bool isInfeasibleCast(const DynamicCastInfo *CastInfo,
98 bool CastSucceeds) {
99 if (!CastInfo)
100 return false;
101
102 return CastSucceeds ? CastInfo->fails() : CastInfo->succeeds();
103}
104
105static 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 Cb: [=]() -> 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>(Val: Object)) {
123 Out << '\'' << DRE->getDecl()->getDeclName() << '\'';
124 } else if (const auto *ME = dyn_cast<MemberExpr>(Val: 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
139static 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 Cb: [=]() -> 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>(Val: Object)) {
154 Out << '\'' << DRE->getDecl()->getNameAsString() << '\'';
155 } else if (const auto *ME = dyn_cast<MemberExpr>(Val: 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
184static QualType alignReferenceTypes(QualType toAlign, QualType alignTowards,
185 ASTContext &ACtx) {
186 if (alignTowards->isLValueReferenceType() &&
187 alignTowards.isConstQualified()) {
188 toAlign.addConst();
189 return ACtx.getLValueReferenceType(T: toAlign);
190 } else if (alignTowards->isLValueReferenceType())
191 return ACtx.getLValueReferenceType(T: toAlign);
192 else if (alignTowards->isRValueReferenceType())
193 return ACtx.getRValueReferenceType(T: toAlign);
194
195 llvm_unreachable("Must align towards a reference type!");
196}
197
198static 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(Cond: DV, Assumption: 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(Index: 0);
212 CastFromTy = Call.parameters()[0]->getType();
213 } else {
214 Object = cast<CXXInstanceCall>(Val: &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(toAlign: CastFromTy, alignTowards: CastToTy, ACtx&: 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, Pred: 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 IsCastSucceeds: CastSucceeds);
251
252 SVal V = CastSucceeds ? C.getSValBuilder().evalCast(V: DV, CastTy: CastToTy, OriginalTy: CastFromTy)
253 : C.getSValBuilder().makeNullWithType(type: CastToTy);
254 C.addTransition(
255 State: State->BindExpr(S: Call.getOriginExpr(), LCtx: C.getLocationContext(), V, Invalidate: false),
256 Tag: getNoteTag(C, CastInfo, CastToTy, Object, CastSucceeds, IsKnownCast));
257}
258
259static 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: idx);
270 switch (CastToTempArg.getKind()) {
271 default:
272 return;
273 case TemplateArgument::Type:
274 CastToTyVec.push_back(Elt: CastToTempArg.getAsType());
275 break;
276 case TemplateArgument::Pack:
277 for (TemplateArgument ArgInPack: CastToTempArg.pack_elements())
278 CastToTyVec.push_back(Elt: ArgInPack.getAsType());
279 break;
280 }
281 }
282
283 const MemRegion *MR = DV.getAsRegion();
284 if (MR && CastFromTy->isReferenceType())
285 MR = State->getSVal(LV: 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(T: CastToTy);
292 else if (CastFromTy->isReferenceType())
293 CastToTy = alignReferenceTypes(toAlign: CastToTy, alignTowards: CastFromTy, ACtx&: 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 IsCastSucceeds: IsInstanceOf);
313
314 if (CastSucceeds) {
315 Success = true;
316 C.addTransition(
317 State: NewState->BindExpr(S: Call.getOriginExpr(), LCtx: C.getLocationContext(),
318 V: C.getSValBuilder().makeTruthVal(b: true)),
319 Tag: getNoteTag(C, CastInfo, CastToTy, Object: Call.getArgExpr(Index: 0), CastSucceeds: true,
320 IsKnownCast));
321 if (IsKnownCast)
322 return;
323 } else if (CastInfo && CastInfo->succeeds()) {
324 C.generateSink(State: NewState, Pred: C.getPredecessor());
325 return;
326 }
327 }
328
329 if (!Success) {
330 C.addTransition(
331 State: State->BindExpr(S: Call.getOriginExpr(), LCtx: C.getLocationContext(),
332 V: C.getSValBuilder().makeTruthVal(b: false)),
333 Tag: getNoteTag(C, CastToTyVec, Object: Call.getArgExpr(Index: 0), IsKnownCast: IsAnyKnown));
334 }
335}
336
337//===----------------------------------------------------------------------===//
338// Evaluating cast, dyn_cast, cast_or_null, dyn_cast_or_null.
339//===----------------------------------------------------------------------===//
340
341static 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
349static void evalNonNullParamNullReturn(const CallEvent &Call,
350 DefinedOrUnknownSVal DV,
351 CheckerContext &C) {
352 addCastTransition(Call, DV, C, /*IsNonNullParam=*/true,
353 /*IsNonNullReturn=*/false);
354}
355
356static void evalNullParamNullReturn(const CallEvent &Call,
357 DefinedOrUnknownSVal DV,
358 CheckerContext &C) {
359 if (ProgramStateRef State = C.getState()->assume(Cond: DV, Assumption: false))
360 C.addTransition(State: State->BindExpr(S: Call.getOriginExpr(),
361 LCtx: C.getLocationContext(),
362 V: C.getSValBuilder().makeNullWithType(
363 type: Call.getOriginExpr()->getType()),
364 Invalidate: false),
365 Tag: C.getNoteTag(Note: "Assuming null pointer is passed into cast",
366 /*IsPrunable=*/true));
367}
368
369void CastValueChecker::evalCast(const CallEvent &Call, DefinedOrUnknownSVal DV,
370 CheckerContext &C) const {
371 evalNonNullParamNonNullReturn(Call, DV, C, /*IsCheckedCast=*/true);
372}
373
374void CastValueChecker::evalDynCast(const CallEvent &Call,
375 DefinedOrUnknownSVal DV,
376 CheckerContext &C) const {
377 evalNonNullParamNonNullReturn(Call, DV, C);
378 evalNonNullParamNullReturn(Call, DV, C);
379}
380
381void CastValueChecker::evalCastOrNull(const CallEvent &Call,
382 DefinedOrUnknownSVal DV,
383 CheckerContext &C) const {
384 evalNonNullParamNonNullReturn(Call, DV, C);
385 evalNullParamNullReturn(Call, DV, C);
386}
387
388void 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
400static 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
408static void evalZeroParamNullReturn(const CallEvent &Call,
409 DefinedOrUnknownSVal DV,
410 CheckerContext &C) {
411 addCastTransition(Call, DV, C, /*IsNonNullParam=*/true,
412 /*IsNonNullReturn=*/false);
413}
414
415void CastValueChecker::evalCastAs(const CallEvent &Call,
416 DefinedOrUnknownSVal DV,
417 CheckerContext &C) const {
418 evalZeroParamNonNullReturn(Call, DV, C, /*IsCheckedCast=*/true);
419}
420
421void 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
431void CastValueChecker::evalIsa(const CallEvent &Call, DefinedOrUnknownSVal DV,
432 CheckerContext &C) const {
433 ProgramStateRef NonNullState, NullState;
434 std::tie(args&: NonNullState, args&: NullState) = C.getState()->assume(Cond: DV);
435
436 if (NonNullState) {
437 addInstanceOfTransition(Call, DV, State: NonNullState, C, /*IsInstanceOf=*/true);
438 addInstanceOfTransition(Call, DV, State: NonNullState, C, /*IsInstanceOf=*/false);
439 }
440
441 if (NullState) {
442 C.generateSink(State: NullState, Pred: C.getPredecessor());
443 }
444}
445
446void CastValueChecker::evalIsaAndNonNull(const CallEvent &Call,
447 DefinedOrUnknownSVal DV,
448 CheckerContext &C) const {
449 ProgramStateRef NonNullState, NullState;
450 std::tie(args&: NonNullState, args&: NullState) = C.getState()->assume(Cond: DV);
451
452 if (NonNullState) {
453 addInstanceOfTransition(Call, DV, State: NonNullState, C, /*IsInstanceOf=*/true);
454 addInstanceOfTransition(Call, DV, State: NonNullState, C, /*IsInstanceOf=*/false);
455 }
456
457 if (NullState) {
458 addInstanceOfTransition(Call, DV, State: NullState, C, /*IsInstanceOf=*/false);
459 }
460}
461
462//===----------------------------------------------------------------------===//
463// Main logic to evaluate a call.
464//===----------------------------------------------------------------------===//
465
466bool 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 std::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(Index: 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(Index: 0).getAs<DefinedOrUnknownSVal>();
499 break;
500 }
501 case CallKind::Method:
502 const auto *InstanceCall = dyn_cast<CXXInstanceCall>(Val: &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
517void CastValueChecker::checkDeadSymbols(SymbolReaper &SR,
518 CheckerContext &C) const {
519 C.addTransition(State: removeDeadCasts(State: C.getState(), SR));
520}
521
522void ento::registerCastValueChecker(CheckerManager &Mgr) {
523 Mgr.registerChecker<CastValueChecker>();
524}
525
526bool ento::shouldRegisterCastValueChecker(const CheckerManager &mgr) {
527 return true;
528}
529