-
Notifications
You must be signed in to change notification settings - Fork 13.1k
/
Copy pathStdLibraryFunctionsChecker.cpp
3962 lines (3586 loc) · 173 KB
/
StdLibraryFunctionsChecker.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
//=== StdLibraryFunctionsChecker.cpp - Model standard functions -*- C++ -*-===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
// This checker improves modeling of a few simple library functions.
//
// This checker provides a specification format - `Summary' - and
// contains descriptions of some library functions in this format. Each
// specification contains a list of branches for splitting the program state
// upon call, and range constraints on argument and return-value symbols that
// are satisfied on each branch. This spec can be expanded to include more
// items, like external effects of the function.
//
// The main difference between this approach and the body farms technique is
// in more explicit control over how many branches are produced. For example,
// consider standard C function `ispunct(int x)', which returns a non-zero value
// iff `x' is a punctuation character, that is, when `x' is in range
// ['!', '/'] [':', '@'] U ['[', '\`'] U ['{', '~'].
// `Summary' provides only two branches for this function. However,
// any attempt to describe this range with if-statements in the body farm
// would result in many more branches. Because each branch needs to be analyzed
// independently, this significantly reduces performance. Additionally,
// once we consider a branch on which `x' is in range, say, ['!', '/'],
// we assume that such branch is an important separate path through the program,
// which may lead to false positives because considering this particular path
// was not consciously intended, and therefore it might have been unreachable.
//
// This checker uses eval::Call for modeling pure functions (functions without
// side effects), for which their `Summary' is a precise model. This avoids
// unnecessary invalidation passes. Conflicts with other checkers are unlikely
// because if the function has no other effects, other checkers would probably
// never want to improve upon the modeling done by this checker.
//
// Non-pure functions, for which only partial improvement over the default
// behavior is expected, are modeled via check::PostCall, non-intrusively.
//
//===----------------------------------------------------------------------===//
#include "ErrnoModeling.h"
#include "clang/StaticAnalyzer/Checkers/BuiltinCheckerRegistration.h"
#include "clang/StaticAnalyzer/Core/BugReporter/BugType.h"
#include "clang/StaticAnalyzer/Core/Checker.h"
#include "clang/StaticAnalyzer/Core/CheckerManager.h"
#include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerHelpers.h"
#include "clang/StaticAnalyzer/Core/PathSensitive/DynamicExtent.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SmallString.h"
#include "llvm/ADT/StringExtras.h"
#include "llvm/Support/FormatVariadic.h"
#include <optional>
#include <string>
using namespace clang;
using namespace clang::ento;
namespace {
class StdLibraryFunctionsChecker
: public Checker<check::PreCall, check::PostCall, eval::Call> {
class Summary;
/// Specify how much the analyzer engine should entrust modeling this function
/// to us.
enum InvalidationKind {
/// No \c eval::Call for the function, it can be modeled elsewhere.
/// This checker checks only pre and post conditions.
NoEvalCall,
/// The function is modeled completely in this checker.
EvalCallAsPure
};
/// Given a range, should the argument stay inside or outside this range?
enum RangeKind { OutOfRange, WithinRange };
static RangeKind negateKind(RangeKind K) {
switch (K) {
case OutOfRange:
return WithinRange;
case WithinRange:
return OutOfRange;
}
llvm_unreachable("Unknown range kind");
}
/// The universal integral type to use in value range descriptions.
/// Unsigned to make sure overflows are well-defined.
typedef uint64_t RangeInt;
/// Describes a single range constraint. Eg. {{0, 1}, {3, 4}} is
/// a non-negative integer, which less than 5 and not equal to 2.
typedef std::vector<std::pair<RangeInt, RangeInt>> IntRangeVector;
/// A reference to an argument or return value by its number.
/// ArgNo in CallExpr and CallEvent is defined as Unsigned, but
/// obviously uint32_t should be enough for all practical purposes.
typedef uint32_t ArgNo;
/// Special argument number for specifying the return value.
static const ArgNo Ret;
/// Get a string representation of an argument index.
/// E.g.: (1) -> '1st arg', (2) - > '2nd arg'
static void printArgDesc(ArgNo, llvm::raw_ostream &Out);
/// Print value X of the argument in form " (which is X)",
/// if the value is a fixed known value, otherwise print nothing.
/// This is used as simple explanation of values if possible.
static void printArgValueInfo(ArgNo ArgN, ProgramStateRef State,
const CallEvent &Call, llvm::raw_ostream &Out);
/// Append textual description of a numeric range [RMin,RMax] to
/// \p Out.
static void appendInsideRangeDesc(llvm::APSInt RMin, llvm::APSInt RMax,
QualType ArgT, BasicValueFactory &BVF,
llvm::raw_ostream &Out);
/// Append textual description of a numeric range out of [RMin,RMax] to
/// \p Out.
static void appendOutOfRangeDesc(llvm::APSInt RMin, llvm::APSInt RMax,
QualType ArgT, BasicValueFactory &BVF,
llvm::raw_ostream &Out);
class ValueConstraint;
/// Pointer to the ValueConstraint. We need a copyable, polymorphic and
/// default initializable type (vector needs that). A raw pointer was good,
/// however, we cannot default initialize that. unique_ptr makes the Summary
/// class non-copyable, therefore not an option. Releasing the copyability
/// requirement would render the initialization of the Summary map infeasible.
/// Mind that a pointer to a new value constraint is created when the negate
/// function is used.
using ValueConstraintPtr = std::shared_ptr<ValueConstraint>;
/// Polymorphic base class that represents a constraint on a given argument
/// (or return value) of a function. Derived classes implement different kind
/// of constraints, e.g range constraints or correlation between two
/// arguments.
/// These are used as argument constraints (preconditions) of functions, in
/// which case a bug report may be emitted if the constraint is not satisfied.
/// Another use is as conditions for summary cases, to create different
/// classes of behavior for a function. In this case no description of the
/// constraint is needed because the summary cases have an own (not generated)
/// description string.
class ValueConstraint {
public:
ValueConstraint(ArgNo ArgN) : ArgN(ArgN) {}
virtual ~ValueConstraint() {}
/// Apply the effects of the constraint on the given program state. If null
/// is returned then the constraint is not feasible.
virtual ProgramStateRef apply(ProgramStateRef State, const CallEvent &Call,
const Summary &Summary,
CheckerContext &C) const = 0;
/// Represents that in which context do we require a description of the
/// constraint.
enum DescriptionKind {
/// Describe a constraint that was violated.
/// Description should start with something like "should be".
Violation,
/// Describe a constraint that was assumed to be true.
/// This can be used when a precondition is satisfied, or when a summary
/// case is applied.
/// Description should start with something like "is".
Assumption
};
/// Give a description that explains the constraint to the user. Used when
/// a bug is reported or when the constraint is applied and displayed as a
/// note. The description should not mention the argument (getArgNo).
/// See StdLibraryFunctionsChecker::reportBug about how this function is
/// used (this function is used not only there).
virtual void describe(DescriptionKind DK, const CallEvent &Call,
ProgramStateRef State, const Summary &Summary,
llvm::raw_ostream &Out) const {
// There are some descendant classes that are not used as argument
// constraints, e.g. ComparisonConstraint. In that case we can safely
// ignore the implementation of this function.
llvm_unreachable(
"Description not implemented for summary case constraints");
}
/// Give a description that explains the actual argument value (where the
/// current ValueConstraint applies to) to the user. This function should be
/// called only when the current constraint is satisfied by the argument.
/// It should produce a more precise description than the constraint itself.
/// The actual value of the argument and the program state can be used to
/// make the description more precise. In the most simple case, if the
/// argument has a fixed known value this value can be printed into \p Out,
/// this is done by default.
/// The function should return true if a description was printed to \p Out,
/// otherwise false.
/// See StdLibraryFunctionsChecker::reportBug about how this function is
/// used.
virtual bool describeArgumentValue(const CallEvent &Call,
ProgramStateRef State,
const Summary &Summary,
llvm::raw_ostream &Out) const {
if (auto N = getArgSVal(Call, getArgNo()).getAs<NonLoc>()) {
if (const llvm::APSInt *Int = N->getAsInteger()) {
Out << *Int;
return true;
}
}
return false;
}
/// Return those arguments that should be tracked when we report a bug about
/// argument constraint violation. By default it is the argument that is
/// constrained, however, in some special cases we need to track other
/// arguments as well. E.g. a buffer size might be encoded in another
/// argument.
/// The "return value" argument number can not occur as returned value.
virtual std::vector<ArgNo> getArgsToTrack() const { return {ArgN}; }
/// Get a constraint that represents exactly the opposite of the current.
virtual ValueConstraintPtr negate() const {
llvm_unreachable("Not implemented");
};
/// Check whether the constraint is malformed or not. It is malformed if the
/// specified argument has a mismatch with the given FunctionDecl (e.g. the
/// arg number is out-of-range of the function's argument list).
/// This condition can indicate if a probably wrong or unexpected function
/// was found where the constraint is to be applied.
bool checkValidity(const FunctionDecl *FD) const {
const bool ValidArg = ArgN == Ret || ArgN < FD->getNumParams();
assert(ValidArg && "Arg out of range!");
if (!ValidArg)
return false;
// Subclasses may further refine the validation.
return checkSpecificValidity(FD);
}
/// Return the argument number (may be placeholder for "return value").
ArgNo getArgNo() const { return ArgN; }
protected:
/// Argument to which to apply the constraint. It can be a real argument of
/// the function to check, or a special value to indicate the return value
/// of the function.
/// Every constraint is assigned to one main argument, even if other
/// arguments are involved.
ArgNo ArgN;
/// Do constraint-specific validation check.
virtual bool checkSpecificValidity(const FunctionDecl *FD) const {
return true;
}
};
/// Check if a single argument falls into a specific "range".
/// A range is formed as a set of intervals.
/// E.g. \code {['A', 'Z'], ['a', 'z'], ['_', '_']} \endcode
/// The intervals are closed intervals that contain one or more values.
///
/// The default constructed RangeConstraint has an empty range, applying
/// such constraint does not involve any assumptions, thus the State remains
/// unchanged. This is meaningful, if the range is dependent on a looked up
/// type (e.g. [0, Socklen_tMax]). If the type is not found, then the range
/// is default initialized to be empty.
class RangeConstraint : public ValueConstraint {
/// The constraint can be specified by allowing or disallowing the range.
/// WithinRange indicates allowing the range, OutOfRange indicates
/// disallowing it (allowing the complementary range).
RangeKind Kind;
/// A set of intervals.
IntRangeVector Ranges;
/// A textual description of this constraint for the specific case where the
/// constraint is used. If empty a generated description will be used that
/// is built from the range of the constraint.
StringRef Description;
public:
RangeConstraint(ArgNo ArgN, RangeKind Kind, const IntRangeVector &Ranges,
StringRef Desc = "")
: ValueConstraint(ArgN), Kind(Kind), Ranges(Ranges), Description(Desc) {
}
const IntRangeVector &getRanges() const { return Ranges; }
ProgramStateRef apply(ProgramStateRef State, const CallEvent &Call,
const Summary &Summary,
CheckerContext &C) const override;
void describe(DescriptionKind DK, const CallEvent &Call,
ProgramStateRef State, const Summary &Summary,
llvm::raw_ostream &Out) const override;
bool describeArgumentValue(const CallEvent &Call, ProgramStateRef State,
const Summary &Summary,
llvm::raw_ostream &Out) const override;
ValueConstraintPtr negate() const override {
RangeConstraint Tmp(*this);
Tmp.Kind = negateKind(Kind);
return std::make_shared<RangeConstraint>(Tmp);
}
protected:
bool checkSpecificValidity(const FunctionDecl *FD) const override {
const bool ValidArg =
getArgType(FD, ArgN)->isIntegralType(FD->getASTContext());
assert(ValidArg &&
"This constraint should be applied on an integral type");
return ValidArg;
}
private:
/// A callback function that is used when iterating over the range
/// intervals. It gets the begin and end (inclusive) of one interval.
/// This is used to make any kind of task possible that needs an iteration
/// over the intervals.
using RangeApplyFunction =
std::function<bool(const llvm::APSInt &Min, const llvm::APSInt &Max)>;
/// Call a function on the intervals of the range.
/// The function is called with all intervals in the range.
void applyOnWithinRange(BasicValueFactory &BVF, QualType ArgT,
const RangeApplyFunction &F) const;
/// Call a function on all intervals in the complementary range.
/// The function is called with all intervals that fall out of the range.
/// E.g. consider an interval list [A, B] and [C, D]
/// \code
/// -------+--------+------------------+------------+----------->
/// A B C D
/// \endcode
/// We get the ranges [-inf, A - 1], [D + 1, +inf], [B + 1, C - 1].
/// The \p ArgT is used to determine the min and max of the type that is
/// used as "-inf" and "+inf".
void applyOnOutOfRange(BasicValueFactory &BVF, QualType ArgT,
const RangeApplyFunction &F) const;
/// Call a function on the intervals of the range or the complementary
/// range.
void applyOnRange(RangeKind Kind, BasicValueFactory &BVF, QualType ArgT,
const RangeApplyFunction &F) const {
switch (Kind) {
case OutOfRange:
applyOnOutOfRange(BVF, ArgT, F);
break;
case WithinRange:
applyOnWithinRange(BVF, ArgT, F);
break;
};
}
};
/// Check relation of an argument to another.
class ComparisonConstraint : public ValueConstraint {
BinaryOperator::Opcode Opcode;
ArgNo OtherArgN;
public:
ComparisonConstraint(ArgNo ArgN, BinaryOperator::Opcode Opcode,
ArgNo OtherArgN)
: ValueConstraint(ArgN), Opcode(Opcode), OtherArgN(OtherArgN) {}
ArgNo getOtherArgNo() const { return OtherArgN; }
BinaryOperator::Opcode getOpcode() const { return Opcode; }
ProgramStateRef apply(ProgramStateRef State, const CallEvent &Call,
const Summary &Summary,
CheckerContext &C) const override;
};
/// Check null or non-null-ness of an argument that is of pointer type.
class NotNullConstraint : public ValueConstraint {
using ValueConstraint::ValueConstraint;
// This variable has a role when we negate the constraint.
bool CannotBeNull = true;
public:
NotNullConstraint(ArgNo ArgN, bool CannotBeNull = true)
: ValueConstraint(ArgN), CannotBeNull(CannotBeNull) {}
ProgramStateRef apply(ProgramStateRef State, const CallEvent &Call,
const Summary &Summary,
CheckerContext &C) const override;
void describe(DescriptionKind DK, const CallEvent &Call,
ProgramStateRef State, const Summary &Summary,
llvm::raw_ostream &Out) const override;
bool describeArgumentValue(const CallEvent &Call, ProgramStateRef State,
const Summary &Summary,
llvm::raw_ostream &Out) const override;
ValueConstraintPtr negate() const override {
NotNullConstraint Tmp(*this);
Tmp.CannotBeNull = !this->CannotBeNull;
return std::make_shared<NotNullConstraint>(Tmp);
}
protected:
bool checkSpecificValidity(const FunctionDecl *FD) const override {
const bool ValidArg = getArgType(FD, ArgN)->isPointerType();
assert(ValidArg &&
"This constraint should be applied only on a pointer type");
return ValidArg;
}
};
/// Check null or non-null-ness of an argument that is of pointer type.
/// The argument is meant to be a buffer that has a size constraint, and it
/// is allowed to have a NULL value if the size is 0. The size can depend on
/// 1 or 2 additional arguments, if one of these is 0 the buffer is allowed to
/// be NULL. This is useful for functions like `fread` which have this special
/// property.
class NotNullBufferConstraint : public ValueConstraint {
using ValueConstraint::ValueConstraint;
ArgNo SizeArg1N;
std::optional<ArgNo> SizeArg2N;
// This variable has a role when we negate the constraint.
bool CannotBeNull = true;
public:
NotNullBufferConstraint(ArgNo ArgN, ArgNo SizeArg1N,
std::optional<ArgNo> SizeArg2N,
bool CannotBeNull = true)
: ValueConstraint(ArgN), SizeArg1N(SizeArg1N), SizeArg2N(SizeArg2N),
CannotBeNull(CannotBeNull) {}
ProgramStateRef apply(ProgramStateRef State, const CallEvent &Call,
const Summary &Summary,
CheckerContext &C) const override;
void describe(DescriptionKind DK, const CallEvent &Call,
ProgramStateRef State, const Summary &Summary,
llvm::raw_ostream &Out) const override;
bool describeArgumentValue(const CallEvent &Call, ProgramStateRef State,
const Summary &Summary,
llvm::raw_ostream &Out) const override;
ValueConstraintPtr negate() const override {
NotNullBufferConstraint Tmp(*this);
Tmp.CannotBeNull = !this->CannotBeNull;
return std::make_shared<NotNullBufferConstraint>(Tmp);
}
protected:
bool checkSpecificValidity(const FunctionDecl *FD) const override {
const bool ValidArg = getArgType(FD, ArgN)->isPointerType();
assert(ValidArg &&
"This constraint should be applied only on a pointer type");
return ValidArg;
}
};
// Represents a buffer argument with an additional size constraint. The
// constraint may be a concrete value, or a symbolic value in an argument.
// Example 1. Concrete value as the minimum buffer size.
// char *asctime_r(const struct tm *restrict tm, char *restrict buf);
// // `buf` size must be at least 26 bytes according the POSIX standard.
// Example 2. Argument as a buffer size.
// ctime_s(char *buffer, rsize_t bufsz, const time_t *time);
// Example 3. The size is computed as a multiplication of other args.
// size_t fread(void *ptr, size_t size, size_t nmemb, FILE *stream);
// // Here, ptr is the buffer, and its minimum size is `size * nmemb`.
class BufferSizeConstraint : public ValueConstraint {
// The concrete value which is the minimum size for the buffer.
std::optional<llvm::APSInt> ConcreteSize;
// The argument which holds the size of the buffer.
std::optional<ArgNo> SizeArgN;
// The argument which is a multiplier to size. This is set in case of
// `fread` like functions where the size is computed as a multiplication of
// two arguments.
std::optional<ArgNo> SizeMultiplierArgN;
// The operator we use in apply. This is negated in negate().
BinaryOperator::Opcode Op = BO_LE;
public:
BufferSizeConstraint(ArgNo Buffer, llvm::APSInt BufMinSize)
: ValueConstraint(Buffer), ConcreteSize(BufMinSize) {}
BufferSizeConstraint(ArgNo Buffer, ArgNo BufSize)
: ValueConstraint(Buffer), SizeArgN(BufSize) {}
BufferSizeConstraint(ArgNo Buffer, ArgNo BufSize, ArgNo BufSizeMultiplier)
: ValueConstraint(Buffer), SizeArgN(BufSize),
SizeMultiplierArgN(BufSizeMultiplier) {}
ProgramStateRef apply(ProgramStateRef State, const CallEvent &Call,
const Summary &Summary,
CheckerContext &C) const override;
void describe(DescriptionKind DK, const CallEvent &Call,
ProgramStateRef State, const Summary &Summary,
llvm::raw_ostream &Out) const override;
bool describeArgumentValue(const CallEvent &Call, ProgramStateRef State,
const Summary &Summary,
llvm::raw_ostream &Out) const override;
std::vector<ArgNo> getArgsToTrack() const override {
std::vector<ArgNo> Result{ArgN};
if (SizeArgN)
Result.push_back(*SizeArgN);
if (SizeMultiplierArgN)
Result.push_back(*SizeMultiplierArgN);
return Result;
}
ValueConstraintPtr negate() const override {
BufferSizeConstraint Tmp(*this);
Tmp.Op = BinaryOperator::negateComparisonOp(Op);
return std::make_shared<BufferSizeConstraint>(Tmp);
}
protected:
bool checkSpecificValidity(const FunctionDecl *FD) const override {
const bool ValidArg = getArgType(FD, ArgN)->isPointerType();
assert(ValidArg &&
"This constraint should be applied only on a pointer type");
return ValidArg;
}
};
/// The complete list of constraints that defines a single branch.
using ConstraintSet = std::vector<ValueConstraintPtr>;
/// Define how a function affects the system variable 'errno'.
/// This works together with the \c ErrnoModeling and \c ErrnoChecker classes.
/// Currently 3 use cases exist: success, failure, irrelevant.
/// In the future the failure case can be customized to set \c errno to a
/// more specific constraint (for example > 0), or new case can be added
/// for functions which require check of \c errno in both success and failure
/// case.
class ErrnoConstraintBase {
public:
/// Apply specific state changes related to the errno variable.
virtual ProgramStateRef apply(ProgramStateRef State, const CallEvent &Call,
const Summary &Summary,
CheckerContext &C) const = 0;
/// Get a description about what happens with 'errno' here and how it causes
/// a later bug report created by ErrnoChecker.
/// Empty return value means that 'errno' related bug may not happen from
/// the current analyzed function.
virtual const std::string describe(CheckerContext &C) const { return ""; }
virtual ~ErrnoConstraintBase() {}
protected:
ErrnoConstraintBase() = default;
/// This is used for conjure symbol for errno to differentiate from the
/// original call expression (same expression is used for the errno symbol).
static int Tag;
};
/// Reset errno constraints to irrelevant.
/// This is applicable to functions that may change 'errno' and are not
/// modeled elsewhere.
class ResetErrnoConstraint : public ErrnoConstraintBase {
public:
ProgramStateRef apply(ProgramStateRef State, const CallEvent &Call,
const Summary &Summary,
CheckerContext &C) const override {
return errno_modeling::setErrnoState(State, errno_modeling::Irrelevant);
}
};
/// Do not change errno constraints.
/// This is applicable to functions that are modeled in another checker
/// and the already set errno constraints should not be changed in the
/// post-call event.
class NoErrnoConstraint : public ErrnoConstraintBase {
public:
ProgramStateRef apply(ProgramStateRef State, const CallEvent &Call,
const Summary &Summary,
CheckerContext &C) const override {
return State;
}
};
/// Set errno constraint at failure cases of standard functions.
/// Failure case: 'errno' becomes not equal to 0 and may or may not be checked
/// by the program. \c ErrnoChecker does not emit a bug report after such a
/// function call.
class FailureErrnoConstraint : public ErrnoConstraintBase {
public:
ProgramStateRef apply(ProgramStateRef State, const CallEvent &Call,
const Summary &Summary,
CheckerContext &C) const override {
SValBuilder &SVB = C.getSValBuilder();
NonLoc ErrnoSVal =
SVB.conjureSymbolVal(&Tag, Call.getOriginExpr(),
C.getLocationContext(), C.getASTContext().IntTy,
C.blockCount())
.castAs<NonLoc>();
return errno_modeling::setErrnoForStdFailure(State, C, ErrnoSVal);
}
};
/// Set errno constraint at success cases of standard functions.
/// Success case: 'errno' is not allowed to be used because the value is
/// undefined after successful call.
/// \c ErrnoChecker can emit bug report after such a function call if errno
/// is used.
class SuccessErrnoConstraint : public ErrnoConstraintBase {
public:
ProgramStateRef apply(ProgramStateRef State, const CallEvent &Call,
const Summary &Summary,
CheckerContext &C) const override {
return errno_modeling::setErrnoForStdSuccess(State, C);
}
const std::string describe(CheckerContext &C) const override {
return "'errno' becomes undefined after the call";
}
};
/// Set errno constraint at functions that indicate failure only with 'errno'.
/// In this case 'errno' is required to be observed.
/// \c ErrnoChecker can emit bug report after such a function call if errno
/// is overwritten without a read before.
class ErrnoMustBeCheckedConstraint : public ErrnoConstraintBase {
public:
ProgramStateRef apply(ProgramStateRef State, const CallEvent &Call,
const Summary &Summary,
CheckerContext &C) const override {
return errno_modeling::setErrnoStdMustBeChecked(State, C,
Call.getOriginExpr());
}
const std::string describe(CheckerContext &C) const override {
return "reading 'errno' is required to find out if the call has failed";
}
};
/// A single branch of a function summary.
///
/// A branch is defined by a series of constraints - "assumptions" -
/// that together form a single possible outcome of invoking the function.
/// When static analyzer considers a branch, it tries to introduce
/// a child node in the Exploded Graph. The child node has to include
/// constraints that define the branch. If the constraints contradict
/// existing constraints in the state, the node is not created and the branch
/// is dropped; otherwise it's queued for future exploration.
/// The branch is accompanied by a note text that may be displayed
/// to the user when a bug is found on a path that takes this branch.
///
/// For example, consider the branches in `isalpha(x)`:
/// Branch 1)
/// x is in range ['A', 'Z'] or in ['a', 'z']
/// then the return value is not 0. (I.e. out-of-range [0, 0])
/// and the note may say "Assuming the character is alphabetical"
/// Branch 2)
/// x is out-of-range ['A', 'Z'] and out-of-range ['a', 'z']
/// then the return value is 0
/// and the note may say "Assuming the character is non-alphabetical".
class SummaryCase {
ConstraintSet Constraints;
const ErrnoConstraintBase &ErrnoConstraint;
StringRef Note;
public:
SummaryCase(ConstraintSet &&Constraints, const ErrnoConstraintBase &ErrnoC,
StringRef Note)
: Constraints(std::move(Constraints)), ErrnoConstraint(ErrnoC),
Note(Note) {}
SummaryCase(const ConstraintSet &Constraints,
const ErrnoConstraintBase &ErrnoC, StringRef Note)
: Constraints(Constraints), ErrnoConstraint(ErrnoC), Note(Note) {}
const ConstraintSet &getConstraints() const { return Constraints; }
const ErrnoConstraintBase &getErrnoConstraint() const {
return ErrnoConstraint;
}
StringRef getNote() const { return Note; }
};
using ArgTypes = ArrayRef<std::optional<QualType>>;
using RetType = std::optional<QualType>;
// A placeholder type, we use it whenever we do not care about the concrete
// type in a Signature.
const QualType Irrelevant{};
bool static isIrrelevant(QualType T) { return T.isNull(); }
// The signature of a function we want to describe with a summary. This is a
// concessive signature, meaning there may be irrelevant types in the
// signature which we do not check against a function with concrete types.
// All types in the spec need to be canonical.
class Signature {
using ArgQualTypes = std::vector<QualType>;
ArgQualTypes ArgTys;
QualType RetTy;
// True if any component type is not found by lookup.
bool Invalid = false;
public:
// Construct a signature from optional types. If any of the optional types
// are not set then the signature will be invalid.
Signature(ArgTypes ArgTys, RetType RetTy) {
for (std::optional<QualType> Arg : ArgTys) {
if (!Arg) {
Invalid = true;
return;
} else {
assertArgTypeSuitableForSignature(*Arg);
this->ArgTys.push_back(*Arg);
}
}
if (!RetTy) {
Invalid = true;
return;
} else {
assertRetTypeSuitableForSignature(*RetTy);
this->RetTy = *RetTy;
}
}
bool isInvalid() const { return Invalid; }
bool matches(const FunctionDecl *FD) const;
private:
static void assertArgTypeSuitableForSignature(QualType T) {
assert((T.isNull() || !T->isVoidType()) &&
"We should have no void types in the spec");
assert((T.isNull() || T.isCanonical()) &&
"We should only have canonical types in the spec");
}
static void assertRetTypeSuitableForSignature(QualType T) {
assert((T.isNull() || T.isCanonical()) &&
"We should only have canonical types in the spec");
}
};
static QualType getArgType(const FunctionDecl *FD, ArgNo ArgN) {
assert(FD && "Function must be set");
QualType T = (ArgN == Ret)
? FD->getReturnType().getCanonicalType()
: FD->getParamDecl(ArgN)->getType().getCanonicalType();
return T;
}
using SummaryCases = std::vector<SummaryCase>;
/// A summary includes information about
/// * function prototype (signature)
/// * approach to invalidation,
/// * a list of branches - so, a list of list of ranges,
/// * a list of argument constraints, that must be true on every branch.
/// If these constraints are not satisfied that means a fatal error
/// usually resulting in undefined behaviour.
///
/// Application of a summary:
/// The signature and argument constraints together contain information
/// about which functions are handled by the summary. The signature can use
/// "wildcards", i.e. Irrelevant types. Irrelevant type of a parameter in
/// a signature means that type is not compared to the type of the parameter
/// in the found FunctionDecl. Argument constraints may specify additional
/// rules for the given parameter's type, those rules are checked once the
/// signature is matched.
class Summary {
const InvalidationKind InvalidationKd;
SummaryCases Cases;
ConstraintSet ArgConstraints;
// The function to which the summary applies. This is set after lookup and
// match to the signature.
const FunctionDecl *FD = nullptr;
public:
Summary(InvalidationKind InvalidationKd) : InvalidationKd(InvalidationKd) {}
Summary &Case(ConstraintSet &&CS, const ErrnoConstraintBase &ErrnoC,
StringRef Note = "") {
Cases.push_back(SummaryCase(std::move(CS), ErrnoC, Note));
return *this;
}
Summary &Case(const ConstraintSet &CS, const ErrnoConstraintBase &ErrnoC,
StringRef Note = "") {
Cases.push_back(SummaryCase(CS, ErrnoC, Note));
return *this;
}
Summary &ArgConstraint(ValueConstraintPtr VC) {
assert(VC->getArgNo() != Ret &&
"Arg constraint should not refer to the return value");
ArgConstraints.push_back(VC);
return *this;
}
InvalidationKind getInvalidationKd() const { return InvalidationKd; }
const SummaryCases &getCases() const { return Cases; }
const ConstraintSet &getArgConstraints() const { return ArgConstraints; }
QualType getArgType(ArgNo ArgN) const {
return StdLibraryFunctionsChecker::getArgType(FD, ArgN);
}
// Returns true if the summary should be applied to the given function.
// And if yes then store the function declaration.
bool matchesAndSet(const Signature &Sign, const FunctionDecl *FD) {
bool Result = Sign.matches(FD) && validateByConstraints(FD);
if (Result) {
assert(!this->FD && "FD must not be set more than once");
this->FD = FD;
}
return Result;
}
private:
// Once we know the exact type of the function then do validation check on
// all the given constraints.
bool validateByConstraints(const FunctionDecl *FD) const {
for (const SummaryCase &Case : Cases)
for (const ValueConstraintPtr &Constraint : Case.getConstraints())
if (!Constraint->checkValidity(FD))
return false;
for (const ValueConstraintPtr &Constraint : ArgConstraints)
if (!Constraint->checkValidity(FD))
return false;
return true;
}
};
// The map of all functions supported by the checker. It is initialized
// lazily, and it doesn't change after initialization.
using FunctionSummaryMapType = llvm::DenseMap<const FunctionDecl *, Summary>;
mutable FunctionSummaryMapType FunctionSummaryMap;
const BugType BT_InvalidArg{this, "Function call with invalid argument"};
mutable bool SummariesInitialized = false;
static SVal getArgSVal(const CallEvent &Call, ArgNo ArgN) {
return ArgN == Ret ? Call.getReturnValue() : Call.getArgSVal(ArgN);
}
static std::string getFunctionName(const CallEvent &Call) {
assert(Call.getDecl() &&
"Call was found by a summary, should have declaration");
return cast<NamedDecl>(Call.getDecl())->getNameAsString();
}
public:
void checkPreCall(const CallEvent &Call, CheckerContext &C) const;
void checkPostCall(const CallEvent &Call, CheckerContext &C) const;
bool evalCall(const CallEvent &Call, CheckerContext &C) const;
CheckerNameRef CheckName;
bool AddTestFunctions = false;
bool DisplayLoadedSummaries = false;
bool ModelPOSIX = false;
bool ShouldAssumeControlledEnvironment = false;
private:
std::optional<Summary> findFunctionSummary(const FunctionDecl *FD,
CheckerContext &C) const;
std::optional<Summary> findFunctionSummary(const CallEvent &Call,
CheckerContext &C) const;
void initFunctionSummaries(CheckerContext &C) const;
void reportBug(const CallEvent &Call, ExplodedNode *N,
const ValueConstraint *VC, const ValueConstraint *NegatedVC,
const Summary &Summary, CheckerContext &C) const {
assert(Call.getDecl() &&
"Function found in summary must have a declaration available");
SmallString<256> Msg;
llvm::raw_svector_ostream MsgOs(Msg);
MsgOs << "The ";
printArgDesc(VC->getArgNo(), MsgOs);
MsgOs << " to '" << getFunctionName(Call) << "' ";
bool ValuesPrinted =
NegatedVC->describeArgumentValue(Call, N->getState(), Summary, MsgOs);
if (ValuesPrinted)
MsgOs << " but ";
else
MsgOs << "is out of the accepted range; It ";
VC->describe(ValueConstraint::Violation, Call, C.getState(), Summary,
MsgOs);
Msg[0] = toupper(Msg[0]);
auto R = std::make_unique<PathSensitiveBugReport>(BT_InvalidArg, Msg, N);
for (ArgNo ArgN : VC->getArgsToTrack()) {
bugreporter::trackExpressionValue(N, Call.getArgExpr(ArgN), *R);
R->markInteresting(Call.getArgSVal(ArgN));
// All tracked arguments are important, highlight them.
R->addRange(Call.getArgSourceRange(ArgN));
}
C.emitReport(std::move(R));
}
/// These are the errno constraints that can be passed to summary cases.
/// One of these should fit for a single summary case.
/// Usually if a failure return value exists for function, that function
/// needs different cases for success and failure with different errno
/// constraints (and different return value constraints).
const NoErrnoConstraint ErrnoUnchanged{};
const ResetErrnoConstraint ErrnoIrrelevant{};
const ErrnoMustBeCheckedConstraint ErrnoMustBeChecked{};
const SuccessErrnoConstraint ErrnoMustNotBeChecked{};
const FailureErrnoConstraint ErrnoNEZeroIrrelevant{};
};
int StdLibraryFunctionsChecker::ErrnoConstraintBase::Tag = 0;
const StdLibraryFunctionsChecker::ArgNo StdLibraryFunctionsChecker::Ret =
std::numeric_limits<ArgNo>::max();
static BasicValueFactory &getBVF(ProgramStateRef State) {
ProgramStateManager &Mgr = State->getStateManager();
SValBuilder &SVB = Mgr.getSValBuilder();
return SVB.getBasicValueFactory();
}
} // end of anonymous namespace
void StdLibraryFunctionsChecker::printArgDesc(
StdLibraryFunctionsChecker::ArgNo ArgN, llvm::raw_ostream &Out) {
Out << std::to_string(ArgN + 1);
Out << llvm::getOrdinalSuffix(ArgN + 1);
Out << " argument";
}
void StdLibraryFunctionsChecker::printArgValueInfo(ArgNo ArgN,
ProgramStateRef State,
const CallEvent &Call,
llvm::raw_ostream &Out) {
if (const llvm::APSInt *Val =
State->getStateManager().getSValBuilder().getKnownValue(
State, getArgSVal(Call, ArgN)))
Out << " (which is " << *Val << ")";
}
void StdLibraryFunctionsChecker::appendInsideRangeDesc(llvm::APSInt RMin,
llvm::APSInt RMax,
QualType ArgT,
BasicValueFactory &BVF,
llvm::raw_ostream &Out) {
if (RMin.isZero() && RMax.isZero())
Out << "zero";
else if (RMin == RMax)
Out << RMin;
else if (RMin == BVF.getMinValue(ArgT)) {
if (RMax == -1)
Out << "< 0";
else
Out << "<= " << RMax;
} else if (RMax == BVF.getMaxValue(ArgT)) {
if (RMin.isOne())
Out << "> 0";
else
Out << ">= " << RMin;
} else if (RMin.isNegative() == RMax.isNegative() &&
RMin.getLimitedValue() == RMax.getLimitedValue() - 1) {
Out << RMin << " or " << RMax;
} else {
Out << "between " << RMin << " and " << RMax;
}
}
void StdLibraryFunctionsChecker::appendOutOfRangeDesc(llvm::APSInt RMin,
llvm::APSInt RMax,
QualType ArgT,
BasicValueFactory &BVF,
llvm::raw_ostream &Out) {
if (RMin.isZero() && RMax.isZero())
Out << "nonzero";
else if (RMin == RMax) {
Out << "not equal to " << RMin;
} else if (RMin == BVF.getMinValue(ArgT)) {
if (RMax == -1)
Out << ">= 0";
else
Out << "> " << RMax;
} else if (RMax == BVF.getMaxValue(ArgT)) {
if (RMin.isOne())
Out << "<= 0";
else
Out << "< " << RMin;
} else if (RMin.isNegative() == RMax.isNegative() &&
RMin.getLimitedValue() == RMax.getLimitedValue() - 1) {
Out << "not " << RMin << " and not " << RMax;
} else {
Out << "not between " << RMin << " and " << RMax;
}
}
void StdLibraryFunctionsChecker::RangeConstraint::applyOnWithinRange(
BasicValueFactory &BVF, QualType ArgT, const RangeApplyFunction &F) const {
if (Ranges.empty())
return;
for (auto [Start, End] : getRanges()) {
const llvm::APSInt &Min = BVF.getValue(Start, ArgT);
const llvm::APSInt &Max = BVF.getValue(End, ArgT);
assert(Min <= Max);
if (!F(Min, Max))
return;
}
}
void StdLibraryFunctionsChecker::RangeConstraint::applyOnOutOfRange(