[analyzer][NFC] Migrate nonloc::ConcreteInt to use APSIntPtr (2/4) (#120436)

[analyzer] Improve bug report hashing, merge similar reports (#98621)

Previously there were certain situations where
alpha.security.ArrayBoundV2 produced lots of very similar and redundant
reports

[analyzer] Improve bug report hashing, merge similar reports (#98621)

Previously there were certain situations where
alpha.security.ArrayBoundV2 produced lots of very similar and redundant
reports that only differed in their full `Description` that contained
the (negative) byte offset value. (See
https://github.com/llvm/llvm-project/issues/86969 for details.)

This change updates the `Profile()` method of `PathSensitiveBugReport`
to ensure that it uses `getShortDescription()` instead of the full
`Description` so the standard report deduplication eliminates most of
these redundant reports.

Note that the effects of this change are very limited because there are
very few checkers that specify a separate short description, and so
`getShortDescription()` practically always defaults to returning the
full `Description`.

For the sake of consistency `BasicBugReport::Profile()` is also updated
to use the short description. (Right now there are no checkers that use
`BasicBugReport` with separate long and short descriptions.)

This commit also includes some small code quality improvements in
`ArrayBoundV2` that are IMO too trivial to be moved into a separate
commit.

show more ...

[analyzer] Mention possibility of underflow in array overflow errors (#84201)

The checker alpha.security.ArrayBoundV2 performs bounds checking in two
steps: first it checks for underflow, and if it

[analyzer] Mention possibility of underflow in array overflow errors (#84201)

The checker alpha.security.ArrayBoundV2 performs bounds checking in two
steps: first it checks for underflow, and if it isn't guaranteed then it
assumes that there is no underflow. After this, it checks for overflow,
and if that's guaranteed or the index is tainted then it reports it.

This meant that in situations where overflow and underflow are both
possible (but the index is either tainted or guaranteed to be invalid),
the checker was reporting just an overflow error.

This commit modifies the messages printed in these cases to mention the
possibility of an underflow.

---------

Co-authored-by: Balazs Benics <benicsbalazs@gmail.com>

show more ...

[analyzer] Improve some comments in ArrayBoundCheckerV2 (NFC) (#83545)

This comment-only change fixes a typo, clarifies some comments and
includes some thoughts about the difficulties in resolving

[analyzer] Improve some comments in ArrayBoundCheckerV2 (NFC) (#83545)

This comment-only change fixes a typo, clarifies some comments and
includes some thoughts about the difficulties in resolving a certain
FIXME.

show more ...

[analyzer] Improve handling of unsigned values in ArrayBoundCheckerV2 (#81034)

A memory access is an out of bounds error if the offset is < the extent
of the memory region. Notice that here "<" is

[analyzer] Improve handling of unsigned values in ArrayBoundCheckerV2 (#81034)

A memory access is an out of bounds error if the offset is < the extent
of the memory region. Notice that here "<" is a _mathematical_
comparison between two numbers and NOT a C/C++ operator that compares
two typed C++ values: for example -1 < 1000 is true in mathematics, but
if the `-1` is an `int` and the `1000` is a `size_t` value, then
evaluating the C/C++ operator `<` will return false because the `-1`
will be converted to `SIZE_MAX` by the automatic type conversions.

This means that it's incorrect to perform a bounds check with
`evalBinOpNN(State, BO_LT, ...)` which performs automatic conversions
and can produce wildly incorrect results.

ArrayBoundsCheckerV2 already had a special case where it avoided calling
`evalBinOpNN` in a situation where it would have performed an automatic
conversion; this commit replaces that code with a more general one that
covers more situations. (It's still not perfect, but it's better than
the previous version and I think it will cover practically all
real-world code.)

Note that this is not a limitation/bug of the simplification algorithm
defined in `getSimplifedOffsets()`: the simplification is not applied in
the test case `test_comparison_with_extent_symbol` (because the `Extent`
is not a concrete int), but without the new code it would still run into
a `-1 < UNSIGNED` comparison that evaluates to false because
`evalBinOpNN` performs an automatic type conversion.

show more ...

[analyzer] Support interestingness in ArrayBoundV2 (#78315)

This commit improves alpha.security.ArrayBoundV2 in two connected areas:
(1) It calls `markInteresting()` on the symbolic values that are

[analyzer] Support interestingness in ArrayBoundV2 (#78315)

This commit improves alpha.security.ArrayBoundV2 in two connected areas:
(1) It calls `markInteresting()` on the symbolic values that are
responsible for the out of bounds access.
(2) Its index-is-in-bounds assumptions are reported in note tags if they
provide information about the value of an interesting symbol.

This commit is limited to "display" changes: it introduces new
diagnostic pieces (potentially to bugs found by other checkers), but
ArrayBoundV2 will make the same assumptions and detect the same bugs
before and after this change.

As a minor unrelated change, this commit also updates/removes some very
old comments which became obsolete due to my previous changes.

show more ...

[analyzer] Switch to PostStmt callbacks in ArrayBoundV2 (#72107)

...instead of the currently used, more abstract Location callback. The
main advantage of this change is that after it the checker wi

[analyzer] Switch to PostStmt callbacks in ArrayBoundV2 (#72107)

...instead of the currently used, more abstract Location callback. The
main advantage of this change is that after it the checker will check
`array[index].field` while the previous implementation ignored this
situation (because here the ElementRegion is wrapped in a FieldRegion
object). This improvement fixes PR #70187.

Note that after this change `&array[idx]` will be handled as an access
to the `idx`th element of `array`, which is technically incorrect but
matches the programmer intuitions. In my opinion it's more helpful if
the report points to the source location where the indexing happens
(instead of the location where a pointer is finally dereferenced).

As a special case, this change allows code that forms the past-the-end
pointer of an array as `&arr[size]` (but still rejects code like
`if (idx >= size) return &array[idx];` and code that dereferences a
past-the-end pointer).

In addition to this primary improvement, this change tweaks the message
for the tainted index/offset case (using the more concrete information
that's available now) and clarifies/improves a few testcases.

The main change of this commit (replacing `check::Location` with
`check::PostStmt<...>` callbacks) was already proposed in my change
https://reviews.llvm.org/D150446 and https://reviews.llvm.org/D159107 by
steakhal. Those reviews were both abandoned, but the problems that led
to abandonment were unrelated to the change that is introduced in this
PR.

show more ...

[analyzer] Improve diagnostics from ArrayBoundCheckerV2 (#70056)

Previously alpha.security.ArrayBoundV2 produced very spartan bug
reports; this commit ensures that the relevant (and known) details

[analyzer] Improve diagnostics from ArrayBoundCheckerV2 (#70056)

Previously alpha.security.ArrayBoundV2 produced very spartan bug
reports; this commit ensures that the relevant (and known) details are
reported to the user.

The logic for detecting bugs is not changed, after this commit the
checker will report the same set of issues, but with better messages.

To test the details of the message generation this commit adds a new
test file 'out-of-bounds-diagnostics.c'. Three of the testcases are
added with FIXME notes because they reveal shortcomings of the existing
modeling and bounds checking code. I will try to fix them in separate
follow-up commits.

show more ...

[analyzer][NFC] Simplifications in ArrayBoundV2 (#67572)

I'm planning to improve diagnostics generation in `ArrayBoundCheckerV2`
but before that I'm refactoring the source code to clean up some
ov

[analyzer][NFC] Simplifications in ArrayBoundV2 (#67572)

I'm planning to improve diagnostics generation in `ArrayBoundCheckerV2`
but before that I'm refactoring the source code to clean up some
over-complicated code and an inaccurate comment.

Changes in this commit:
- Remove the `mutable std::unique_ptr<BugType>` boilerplate, because
it's no longer needed.
- Remove the code duplication between the methods `reportOOB()` and
`reportTaintedOOB()`.
- Eliminate the class `RegionRawOffsetV2` because it's just a "reinvent
the wheel" version of `std::pair` and it was used only once, as a
temporary object that was immediately decomposed. (I suspect that
`RegionRawOffset` in MemRegion.cpp could also be eliminated.)
- Flatten the code of `computeOffset()` which had contained six nested
indentation levels before this commit.
- Ensure that `computeOffset()` returns `std::nullopt` instead of a
`{Region, <zero array index>}` pair in the case when it encounters a
`Location` that is not an `ElementRegion`. This ensures that the
`checkLocation` callback returns early when it handles a memory access
where it has "nothing to do" (no subscript operation or equivalent
pointer arithmetic). Note that this is still NFC because zero is a
valid index everywhere, so the old logic without this shortcut
eventually reached the same conclusion.
- Correct a wrong explanation comment in `getSimplifiedOffsets()`.

show more ...

[analyzer][NFC] Remove useless class BuiltinBug

...because it provides no useful functionality compared to its base
class `BugType`.

A long time ago there were substantial differences between `BugT

[analyzer][NFC] Remove useless class BuiltinBug

...because it provides no useful functionality compared to its base
class `BugType`.

A long time ago there were substantial differences between `BugType` and
`BuiltinBug`, but they were eliminated by commit 1bd58233 in 2009 (!).
Since then the only functionality provided by `BuiltinBug` was that it
specified `categories::LogicError` as the bug category and it stored an
extra data member `desc`.

This commit sets `categories::LogicError` as the default value of the
third argument (bug category) in the constructors of BugType and
replaces use of the `desc` field with simpler logic.

Note that `BugType` has a data member `Description` and a non-virtual
method `BugType::getDescription()` which queries it; these are distinct
from the member `desc` of `BuiltinBug` and the identically named method
`BuiltinBug::getDescription()` which queries it. This confusing name
collision was a major motivation for the elimination of `BuiltinBug`.

As this commit touches many files, I avoided functional changes and left
behind FIXME notes to mark minor issues that should be fixed later.

Differential Revision: https://reviews.llvm.org/D158855

show more ...

[analyzer] Improve underflow handling in ArrayBoundV2

This minor change ensures that underflow errors are reported on memory
regions that are in unknown space but have a well-defined beginning.

As

[analyzer] Improve underflow handling in ArrayBoundV2

This minor change ensures that underflow errors are reported on memory
regions that are in unknown space but have a well-defined beginning.

As a concrete example, the following test case did not produce a warning
previously, but will produce a warning after this patch:

typedef struct {
int id;
char name[256];
} user_t;

user_t *get_symbolic_user(void);
char test_underflow_symbolic_2() {
user_t *user = get_symbolic_user();
return user->name[-1];
}

Differential Revision: https://reviews.llvm.org/D157104

show more ...

[analyzer][NFC] Use std::optional instead of custom "empty" state

This commit eliminates the uninitialized error state from the class
RegionRawOffsetV2 (which is locally used by the Clang Static Ana

[analyzer][NFC] Use std::optional instead of custom "empty" state

This commit eliminates the uninitialized error state from the class
RegionRawOffsetV2 (which is locally used by the Clang Static Analyzer
checker alpha.security.ArrayBoundV2) and replaces its use with
std::optional.

Motivated by https://reviews.llvm.org/D148355#inline-1437928

Moreover, the code of RegionRawOffsetV2::computeOffset() is rearranged
to clarify its behavior. The helper function getValue() was eliminated
by picking a better initial value for the variable Offset; two other
helper functions were replaced by the lambda function Calc() because
this way it doesn't need to take the "context" objects as parameters.

This reorganization revealed some surprising (but not outright buggy)
behavior that's marked by a FIXME and will be revisited in a separate
commit.

Differential Revision: https://reviews.llvm.org/D149259

show more ...

[analyzer] ArrayBoundCheckerV2: suppress false positives from ctype macros

The checker alpha.security.ArrayBoundV2 created bug reports in
situations when the (tainted) result of fgetc() or getchar()

[analyzer] ArrayBoundCheckerV2: suppress false positives from ctype macros

The checker alpha.security.ArrayBoundV2 created bug reports in
situations when the (tainted) result of fgetc() or getchar() was passed
to one of the isXXXXX() macros from ctype.h.

This is a common input handling pattern (within the limited toolbox of
the C language) and several open source projects contained code where it
led to false positive reports; so this commit suppresses ArrayBoundV2
reports generated within the isXXXXX() macros.

Note that here even true positive reports would be difficult to
understand, as they'd refer to the implementation details of these
macros.

Differential Revision: https://reviews.llvm.org/D149460

show more ...

[analyzer] Fix comparison logic in ArrayBoundCheckerV2

The prototype checker alpha.security.ArrayBoundV2 performs two
comparisons to check that in an expression like Array[Index]
0 <= Index < le

[analyzer] Fix comparison logic in ArrayBoundCheckerV2

The prototype checker alpha.security.ArrayBoundV2 performs two
comparisons to check that in an expression like Array[Index]
0 <= Index < length(Array)
holds. These comparisons are handled by almost identical logic: the
inequality is first rearranged by getSimplifiedOffsets(), then evaluated
with evalBinOpNN().

However the simplification used "naive" elementary mathematical
schematics, but evalBinOpNN() performed the signed -> unsigned
conversions described in the C/C++ standards, and this confusion led to
wildly inaccurate results: false positives from the lower bound check
and false negatives from the upper bound check.

This commit eliminates the code duplication by moving the comparison
logic into a separate function, then adds an explicit check to this
unified code path, which handles the problematic case separately.

In addition to this, the commit also cleans up a testcase that was
demonstrating the presence of this problem. Note that while that
testcase was failing with an overflow error, its actual problem was in
the underflow handler logic:
(0) The testcase introduces a five-element array "char a[5]" and an
unknown argument "size_t len"; then evaluates "a[len+1]".
(1) The underflow check tries to determine whether "len+1 < 0" holds.
(2) This inequality is rearranged to "len < -1".
(3) evalBinOpNN() evaluates this with the schematics of C/C++ and
converts -1 to the size_t value SIZE_MAX.
(4) The engine concludes that len == SIZE_MAX, because otherwise we'd
have an underflow here.
(5) The overflow check tries to determine whether "len+1 >= 5".
(6) This inequality is rearranged to "len >= 4".
(7) The engine substitutes len == SIZE_MAX and reports that we have
an overflow.

Differential Revision: https://reviews.llvm.org/D135375

show more ...

[analyzer] Show taint origin and propagation correctly

This patch improves the diagnostics of the alpha.security.taint.TaintPropagation
checker and taint related checkers by showing the "Taint origi

[analyzer] Show taint origin and propagation correctly

This patch improves the diagnostics of the alpha.security.taint.TaintPropagation
checker and taint related checkers by showing the "Taint originated here" note
at the correct place, where the attacker may inject it. This greatly improves
the understandability of the taint reports.

In the baseline the taint source was pointing to an invalid location, typically
somewhere between the real taint source and sink.

After the fix, the "Taint originated here" tag is correctly shown at the taint
source. This is the function call where the attacker can inject a malicious data
(e.g. reading from environment variable, reading from file, reading from
standard input etc.).

This patch removes the BugVisitor from the implementation and replaces it with 2
new NoteTags. One, in the taintOriginTrackerTag() prints the "taint originated
here" Note and the other in taintPropagationExplainerTag() explaining how the
taintedness is propagating from argument to argument or to the return value
("Taint propagated to the Xth argument"). This implementation uses the
interestingess BugReport utility to track back the tainted symbols through
propagating function calls to the point where the taintedness was introduced by
a source function call.

The checker which wishes to emit a Taint related diagnostic must use the
categories::TaintedData BugType category and must mark the tainted symbols as
interesting. Then the TaintPropagationChecker will automatically generate the
"Taint originated here" and the "Taint propagated to..." diagnostic notes.

show more ...

[clang] Use std::optional instead of llvm::Optional (NFC)

This patch replaces (llvm::|)Optional< with std::optional<. I'll post
a separate patch to remove #include "llvm/ADT/Optional.h".

This is p

[clang] Use std::optional instead of llvm::Optional (NFC)

This patch replaces (llvm::|)Optional< with std::optional<. I'll post
a separate patch to remove #include "llvm/ADT/Optional.h".

This is part of an effort to migrate from llvm::Optional to
std::optional:

https://discourse.llvm.org/t/deprecating-llvm-optional-x-hasvalue-getvalue-getvalueor/63716

show more ...

[clang] Add #include <optional> (NFC)

This patch adds #include <optional> to those files containing
llvm::Optional<...> or Optional<...>.

I'll post a separate patch to actually replace llvm::Option

[clang] Add #include <optional> (NFC)

This patch adds #include <optional> to those files containing
llvm::Optional<...> or Optional<...>.

I'll post a separate patch to actually replace llvm::Optional with
std::optional.

This is part of an effort to migrate from llvm::Optional to
std::optional:

https://discourse.llvm.org/t/deprecating-llvm-optional-x-hasvalue-getvalue-getvalueor/63716

show more ...

[analyzer][NFC] Prefer using isa<> instead getAs<> in conditions

Depends on D125709

Reviewed By: martong

Differential Revision: https://reviews.llvm.org/D127742

[analyzer] Expose Taint.h to plugins

Reviewed By: NoQ, xazax.hun, steakhal

Differential Revision: https://reviews.llvm.org/D123155

[analyzer] DynamicSize: Rename 'size' to 'extent'

[analyzer][NFC] Change LangOptions to CheckerManager in the shouldRegister* functions

Some checkers may not only depend on language options but also analyzer options.
To make this possible this patc

[analyzer][NFC] Change LangOptions to CheckerManager in the shouldRegister* functions

Some checkers may not only depend on language options but also analyzer options.
To make this possible this patch changes the parameter of the shouldRegister*
function to CheckerManager to be able to query the analyzer options when
deciding whether the checker should be registered.

Differential Revision: https://reviews.llvm.org/D75271

show more ...

[analyzer] DynamicSize: Remove 'getExtent()' from regions

Summary:
This patch introduces a placeholder for representing the dynamic size of
regions. It also moves the `getExtent()` method of `SubReg

[analyzer] DynamicSize: Remove 'getExtent()' from regions

Summary:
This patch introduces a placeholder for representing the dynamic size of
regions. It also moves the `getExtent()` method of `SubRegions` to the
`MemRegionManager` as `getStaticSize()`.

Reviewed By: NoQ

Differential Revision: https://reviews.llvm.org/D69540

show more ...

[analyzer] NFC: Introduce sub-classes for path-sensitive and basic reports.

Checkers are now required to specify whether they're creating a
path-sensitive report or a path-insensitive report by cons

[analyzer] NFC: Introduce sub-classes for path-sensitive and basic reports.

Checkers are now required to specify whether they're creating a
path-sensitive report or a path-insensitive report by constructing an
object of the respective type.

This makes BugReporter more independent from the rest of the Static Analyzer
because all Analyzer-specific code is now in sub-classes.

Differential Revision: https://reviews.llvm.org/D66572

llvm-svn: 371450

show more ...

[Clang] Migrate llvm::make_unique to std::make_unique

Now that we've moved to C++14, we no longer need the llvm::make_unique
implementation from STLExtras.h. This patch is a mechanical replacement
o

[Clang] Migrate llvm::make_unique to std::make_unique

Now that we've moved to C++14, we no longer need the llvm::make_unique
implementation from STLExtras.h. This patch is a mechanical replacement
of (hopefully) all the llvm::make_unique instances across the monorepo.

Differential revision: https://reviews.llvm.org/D66259

llvm-svn: 368942

show more ...

[analyzer] Move taint API from ProgramState to a separate header. NFC.

It is now an inter-checker communication API, similar to the one that
connects MallocChecker/CStringChecker/InnerPointerChecker

[analyzer] Move taint API from ProgramState to a separate header. NFC.

It is now an inter-checker communication API, similar to the one that
connects MallocChecker/CStringChecker/InnerPointerChecker: simply a set of
setters and getters for a state trait.

Differential Revision: https://reviews.llvm.org/D59861

llvm-svn: 357326

show more ...