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(E: Call.getOriginExpr(), SF: C.getStackFrame(), 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(State: NewState->BindExpr(E: Call.getOriginExpr(),
317 SF: C.getStackFrame(),
318 V: C.getSValBuilder().makeTruthVal(b: true)),
319 Tag: getNoteTag(C, CastInfo, CastToTy, Object: Call.getArgExpr(Index: 0),
320 CastSucceeds: true, 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(State: State->BindExpr(E: Call.getOriginExpr(), SF: C.getStackFrame(),
331 V: C.getSValBuilder().makeTruthVal(b: false)),
332 Tag: getNoteTag(C, CastToTyVec, Object: Call.getArgExpr(Index: 0), IsKnownCast: IsAnyKnown));
333 }
334}
335
336//===----------------------------------------------------------------------===//
337// Evaluating cast, dyn_cast, cast_or_null, dyn_cast_or_null.
338//===----------------------------------------------------------------------===//
339
340static 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
348static void evalNonNullParamNullReturn(const CallEvent &Call,
349 DefinedOrUnknownSVal DV,
350 CheckerContext &C) {
351 addCastTransition(Call, DV, C, /*IsNonNullParam=*/true,
352 /*IsNonNullReturn=*/false);
353}
354
355static void evalNullParamNullReturn(const CallEvent &Call,
356 DefinedOrUnknownSVal DV,
357 CheckerContext &C) {
358 if (ProgramStateRef State = C.getState()->assume(Cond: DV, Assumption: false))
359 C.addTransition(State: State->BindExpr(E: Call.getOriginExpr(), SF: C.getStackFrame(),
360 V: C.getSValBuilder().makeNullWithType(
361 type: Call.getOriginExpr()->getType()),
362 Invalidate: false),
363 Tag: C.getNoteTag(Note: "Assuming null pointer is passed into cast",
364 /*IsPrunable=*/true));
365}
366
367void CastValueChecker::evalCast(const CallEvent &Call, DefinedOrUnknownSVal DV,
368 CheckerContext &C) const {
369 evalNonNullParamNonNullReturn(Call, DV, C, /*IsCheckedCast=*/true);
370}
371
372void CastValueChecker::evalDynCast(const CallEvent &Call,
373 DefinedOrUnknownSVal DV,
374 CheckerContext &C) const {
375 evalNonNullParamNonNullReturn(Call, DV, C);
376 evalNonNullParamNullReturn(Call, DV, C);
377}
378
379void CastValueChecker::evalCastOrNull(const CallEvent &Call,
380 DefinedOrUnknownSVal DV,
381 CheckerContext &C) const {
382 evalNonNullParamNonNullReturn(Call, DV, C);
383 evalNullParamNullReturn(Call, DV, C);
384}
385
386void CastValueChecker::evalDynCastOrNull(const CallEvent &Call,
387 DefinedOrUnknownSVal DV,
388 CheckerContext &C) const {
389 evalNonNullParamNonNullReturn(Call, DV, C);
390 evalNonNullParamNullReturn(Call, DV, C);
391 evalNullParamNullReturn(Call, DV, C);
392}
393
394//===----------------------------------------------------------------------===//
395// Evaluating castAs, getAs.
396//===----------------------------------------------------------------------===//
397
398static void evalZeroParamNonNullReturn(const CallEvent &Call,
399 DefinedOrUnknownSVal DV,
400 CheckerContext &C,
401 bool IsCheckedCast = false) {
402 addCastTransition(Call, DV, C, /*IsNonNullParam=*/true,
403 /*IsNonNullReturn=*/true, IsCheckedCast);
404}
405
406static void evalZeroParamNullReturn(const CallEvent &Call,
407 DefinedOrUnknownSVal DV,
408 CheckerContext &C) {
409 addCastTransition(Call, DV, C, /*IsNonNullParam=*/true,
410 /*IsNonNullReturn=*/false);
411}
412
413void CastValueChecker::evalCastAs(const CallEvent &Call,
414 DefinedOrUnknownSVal DV,
415 CheckerContext &C) const {
416 evalZeroParamNonNullReturn(Call, DV, C, /*IsCheckedCast=*/true);
417}
418
419void CastValueChecker::evalGetAs(const CallEvent &Call, DefinedOrUnknownSVal DV,
420 CheckerContext &C) const {
421 evalZeroParamNonNullReturn(Call, DV, C);
422 evalZeroParamNullReturn(Call, DV, C);
423}
424
425//===----------------------------------------------------------------------===//
426// Evaluating isa, isa_and_nonnull.
427//===----------------------------------------------------------------------===//
428
429void CastValueChecker::evalIsa(const CallEvent &Call, DefinedOrUnknownSVal DV,
430 CheckerContext &C) const {
431 ProgramStateRef NonNullState, NullState;
432 std::tie(args&: NonNullState, args&: NullState) = C.getState()->assume(Cond: DV);
433
434 if (NonNullState) {
435 addInstanceOfTransition(Call, DV, State: NonNullState, C, /*IsInstanceOf=*/true);
436 addInstanceOfTransition(Call, DV, State: NonNullState, C, /*IsInstanceOf=*/false);
437 }
438
439 if (NullState) {
440 C.generateSink(State: NullState, Pred: C.getPredecessor());
441 }
442}
443
444void CastValueChecker::evalIsaAndNonNull(const CallEvent &Call,
445 DefinedOrUnknownSVal DV,
446 CheckerContext &C) const {
447 ProgramStateRef NonNullState, NullState;
448 std::tie(args&: NonNullState, args&: NullState) = C.getState()->assume(Cond: DV);
449
450 if (NonNullState) {
451 addInstanceOfTransition(Call, DV, State: NonNullState, C, /*IsInstanceOf=*/true);
452 addInstanceOfTransition(Call, DV, State: NonNullState, C, /*IsInstanceOf=*/false);
453 }
454
455 if (NullState) {
456 addInstanceOfTransition(Call, DV, State: NullState, C, /*IsInstanceOf=*/false);
457 }
458}
459
460//===----------------------------------------------------------------------===//
461// Main logic to evaluate a call.
462//===----------------------------------------------------------------------===//
463
464bool CastValueChecker::evalCall(const CallEvent &Call,
465 CheckerContext &C) const {
466 const auto *Lookup = CDM.lookup(Call);
467 if (!Lookup)
468 return false;
469
470 const CastCheck &Check = Lookup->first;
471 CallKind Kind = Lookup->second;
472
473 std::optional<DefinedOrUnknownSVal> DV;
474
475 switch (Kind) {
476 case CallKind::Function: {
477 // We only model casts from pointers to pointers or from references
478 // to references. Other casts are most likely specialized and we
479 // cannot model them.
480 QualType ParamT = Call.parameters()[0]->getType();
481 QualType ResultT = Call.getResultType();
482 if (!(ParamT->isPointerType() && ResultT->isPointerType()) &&
483 !(ParamT->isReferenceType() && ResultT->isReferenceType())) {
484 return false;
485 }
486
487 DV = Call.getArgSVal(Index: 0).getAs<DefinedOrUnknownSVal>();
488 break;
489 }
490 case CallKind::InstanceOf: {
491 // We need to obtain the only template argument to determinte the type.
492 const FunctionDecl *FD = Call.getDecl()->getAsFunction();
493 if (!FD || !FD->getTemplateSpecializationArgs())
494 return false;
495
496 DV = Call.getArgSVal(Index: 0).getAs<DefinedOrUnknownSVal>();
497 break;
498 }
499 case CallKind::Method:
500 const auto *InstanceCall = dyn_cast<CXXInstanceCall>(Val: &Call);
501 if (!InstanceCall)
502 return false;
503
504 DV = InstanceCall->getCXXThisVal().getAs<DefinedOrUnknownSVal>();
505 break;
506 }
507
508 if (!DV)
509 return false;
510
511 Check(this, Call, *DV, C);
512 return true;
513}
514
515void CastValueChecker::checkDeadSymbols(SymbolReaper &SR,
516 CheckerContext &C) const {
517 C.addTransition(State: removeDeadCasts(State: C.getState(), SR));
518}
519
520void ento::registerCastValueChecker(CheckerManager &Mgr) {
521 Mgr.registerChecker<CastValueChecker>();
522}
523
524bool ento::shouldRegisterCastValueChecker(const CheckerManager &mgr) {
525 return true;
526}
527