Hi,
Over the last decade or so, our work hardening against weaknesses
in various kernel APIs and eliminating the ambiguities in C language
semantics have traditionally been somewhat off in one corner or another
of the Linux codebase. This topic is going to be much different as
it is ultimately about the C type system, which is rather front and
center. So, hold on to your hats while I try to explain what's desired
here. Please try to reserve judgement until the end; as we've explored
the topic we've found a lot of nuances, which I've tried to touch on
below. I'm hoping folks can have an open mind about all this and not
jump to any conclusions without first hearing me out. :)
Problem to Solve
================
The Linux kernel has consistently suffered from unexpected arithmetic
overflow bugs. These lead to any number of exploitable conditions[0].
Our continuing efforts to improve things (refcount_t, alloc_size(),
etc) have helped in some specific areas, but on the whole, we've had a
relatively unchanged count of serious arithmetic overflow flaws over the
life of the project[1]. This is not tolerable, and we should, all of us,
make the effort needed to put an end to it in a systematic way.
Terminology Considerations
==========================
When I say "overflow", I mean "overflow and underflow", but more
specifically I mean "wrap-around". This is not about "undefined
behavior". We already demand from our compilers that all our arithmetic
uses a well-defined overflow resolution strategy; overflow results in
wrap-around (thanks to "-fno-strict-overflow").
Root Cause Analysis
===================
The condition we need to catch is the case of unexpected wrap-around. We
have plenty of places in the kernel where we _expect_ wrap-around,
and many places in the kernel where we attempt to _manually check_
for wrap-around. What is not covered are the cases where a check is
missing or poorly implemented. Some of the more insidious bugs come from
places where assumptions about the possible value ranges of variables are
wrong, or got changed, or were never considered in the first place. But
fundamentally the exceptional condition is the wrap-around: most bounds
checks associated with a given calculation are prepared for a non-wrapping
value range. Having a calculation wrap-around is what ends up knocking
the rest of the logic on its head.
This is what is meant through-out by "ambiguous": the _intent of the
author_ can be ambiguous as it relates to whether a calculation is
meant to wrap-around. That it wraps around on overflow is not ambiguous:
it will wrap-around. :) See "Terminology Considerations".
This is the corner stone of the problem: even though the behavior of
overflow is well-defined, so many authors so often don't correctly handle
it that the results threaten the integrity of Linux as a whole. C makes
it too easy to get it wrong, so we are left needing to fix this at a
fundamental level. This is not a developer education problem; it is a
problem with C language semantics. "Just do it correctly" has not worked.
Mitigation Considerations
=========================
When making large scale changes to Linux where we're adding a check
that didn't exist before, we must not break the old behavior as we're
migrating to a new behavior/expectation. This has served us well
across many hardening transitions we've made. Most recently this has
been exemplified by the array bounds checking, where new checks are
effectively phased in as a WARN[2], and once they've had sufficient
bake time (usually measured in years), the check becomes more strongly
enforced. All the while, there is a steady stream of refactoring going
on to adopt the new behavior/pattern.
Coverage Considerations
=======================
Just like any other kind of filtering, coverage for an exceptional
state is best done with an allowlist, not a blocklist. Using a blocklist
requires one to know _in advance_ which instances need to be caught. As
mentioned above, we've spent decades proving we don't adequately know
where we need to catch overflows. Therefore, we need to take an allowlist
approach: we must identify the places where wrap-around _is_ expected,
so that what remains is where it is _not_ expected. That which has not
yet been identified therefore remains suspect, and we can incrementally
grow the allowlist, since any not-yet-identified false positives will
not break any existing behaviors (see "Mitigation Considerations").
All of our hardening efforts have tried to follow this allowlist
approach. Early on, one of the times we didn't do it was with
refcount_t. We created a separate type to catch the overflow state and
used it where we thought things might go wrong. This turned out to be
a mistake: we've had a long tail of atomic_t overflows that turned into
real bugs that would have been caught had we detected atomic_t overflows
by default and instead created a separate type for the atomic_t cases
that were meant to wrap around.
The integer overflow situation is, as you may observe, very similar to
the atomic_t situation, and so we must make sure we don't repeat the
same mistake here. (Though just as an example about different overflow
resolution strategies, it's worth noting that the major difference with
atomic_t was that the desired strategy was saturation, not wrap-around.)
Language Considerations
=======================
C has no formal exception handling system, and standard arithmetic was
never designed to "fail". This is similar to the many problematic Standard
C Library routines (e.g. memcpy), which were also never designed to
have a "failure" case. This puts us in the uncomfortable (but familiar)
situation where overflow mitigation becomes all-or-nothing, and this
is what informs the approach detailed in Mitigation Considerations:
warn but allow wrap-around until we find all false positives.
The lack of unambiguous arithmetic intent in C has been recognized and
addressed in more modern languages[3], but we're faced with needing to
solve it in C, for Linux, today. As it happens, this is actually already
starting to come up in other areas[4] now that we're trying to interface
Rust with Linux's C internals. Being able to unambiguously describe
wrapping vs non-wrapping expectations will stop an entire class of flaws,
but will also help with the continuing Rust integration.
C has no operator overloading, and the only practical way to change types
is via attributes, which is additive in nature. Whatever the solution,
we'll need to create new wrapping types that are separate from the
existing types (as per Coverage Considerations), and the existing types
will become the non-wrapping types.
C also performs implicit integer promotion and implicit integer
truncation, so things that look like they would overflow don't overflow
until they get stored. For example: in "u8 var=255; ...; var++;"
during what is "var = var + 1", the "var + 1" part doesn't overflow
because it has been promoted to "int", which happily holds "256" without
overflow. But the resulting "var = 256" gets truncated to 0 (effectively
wrapping around). So to properly mitigate integer overflows in C, we
must deal with both overflowing calculations and truncated assignments.
Codebase Considerations
=======================
It's become clear from our investigatory efforts with arithmetic overflow
mitigation that Linux has very few intentional overflows involving
signed calculations. These overflows tend to either be legitimate bugs
(many harmless), or are using an signed type when an unsigned type was
intended (e.g. expecting to operate above INT_MAX, and possibly
expecting wrap-around).
For unsigned calculations, though, many places are expecting to be
wrapping (hashes, counters, etc). As a result, there will be much more
work involved to deal with unsigned calculations, but these are _also_ the
calculations that have led to most of our wrap-around flaws (e.g. sizes,
indexes, etc).
Practical Considerations
========================
While simultaneously taking into account Mitigation, Coverage, Language,
and Codebase Considerations, we must additionally continue to be able
to build Linux with multiple version of GCC and Clang; we must remain
"backward compatible" with our existing toolchains. We need to be able
to make changes incrementally; the proven successful development strategy
of Linux generally. We cannot have a "flag day".
Potential Solution #1: Use sanitizers
=====================================
There already exists, for both GCC[5] and Clang, several sanitizers that
were created specifically for handling integer overflow (and implicit
truncation, the fun sibling to integer overflow[6]). These, today,
already handle the unexpected overflow conditions we need to catch.
Needed on compiler side:
- create attribute that can be applied to typedefs and variable
definitions to indicate "expected to wrap" types. (Clang has this
at the ready[7].)
- allow for common idioms to bypass sanitizers:
- explicit wrap-around tests: if (var + offset < var)
- loop iterator wrap-around during post-decrement: while (var--)
- negative unsigned constants: -1UL
Needed on Linux side:
- create "expected to wrap" typedefs
- replace all expected-to-wrap variables with their appropriate wrapping
type over the next several years (yes, there's a lot)
Changes to binary when mitigation is enabled:
- All cases where non-wrapping types may overflow gain instrumentation
that checks for wrap-around and when found call (via cold branch) to
the sanitizer handler, and then continue on (if so configured).
Example:
#define __wraps __attribute__((__wraps__))
typedef unsigned int __wraps u32_wrap;
...
u16 area;
u32_wrap crc;
...
area = x * y; /* Sanitizer will check for overflow. */
...
crc += word; /* Wrap-around ignored by sanitizer */
...
Pros:
- Much of the compiler work is done
- Sanitizer semantics are well defined
- Binary changes are well understood (other sanitizers have been in
production use for several years now)
- Bootable proof of concept already exists[8]
Potential Solution #2: Operator overloading
===========================================
Among some recent[9] C standards proposals was "Operator Overloading
Without Name Mangling"[10]. This could allow for the redefinition of
the basic arithmetic operators, overloaded via small static inline
helpers. This could allow for arbitrary handling of overflows within
those helpers, using typedefs to distinguish the wrapping types.
Needed on compiler side:
- Actually implement it
- Handle all the idioms from solution #1 somehow, but without a clear
way to approach it
Needed on Linux side:
- create "expected to wrap" typedefs
- create operator overflow functions
- implement exception handling
- replace all expected-to-wrap variables over the next several years
Changes to binary when mitigation is enabled:
- Unknown, but in theory similar to solution #1, though impact of redefining
all arithmetic in terms of static inlines is unclear.
Example (in theory -- semantics aren't fully defined yet):
int int_mul_int(int a, int b)
{
int result;
if (__builtin_mul_overflow(a, b, &result))
__builtin_trap();
return result;
}
_Operator * int_mul_int;
typedef int int_wrap;
int int_mul_int_wrap(int_wrap a, int b)
{
return a * b;
}
_Operator * int_wrap_eq_int_mul_int;
int area = x * y; /* Traps on overflow */
...
int_wrap counter = x;
counter = counter * y; /* Wraps around */
Pros:
- Flexibility of overflow resolution strategy (though this is currently
a non-goal)
Cons:
- Semantics not fully defined
- Amount of compiler work needed is unknown
- More work on the Linux side than solution #1
- May not handle implicit integer truncation
- Unknown impact on binary output (e.g. does the compiler handle composing
the overloaded operators sanely? Is optimization trashed due to using
inlines for everything? etc)
Conclusion
==========
I'm seeking some general consensus on taking approach #1 above. Any
solution that actually gains us meaningful coverage is going to require
pretty extensive changes to Linux's types so that's a universal pain
point. But I've been beating the "make Linux safer" drum for a long time
now, and I hope I can convince folks that we need to actually make a
change here. The status quo isn't good enough, and we can do better. I
just need to find a common solution we can agree on and realistically
apply over the coming years.
I'll go get my asbestos suit now... What are your thoughts, suggestions,
alternatives?
Thanks,
-Kees
[0] I may be a broken record on this topic, but we have to do better.
These attacks range from script kiddies sneaking bitcoin miners onto
systems, to ransomware criminals locking healthcare providers out of all
of their patient records, to fascist regimes tracking and disappearing
dissidents and their families. We can't pretend Linux's flaws are just
some academic consideration; there are real-world consequences to our
use of C.
[1] Looking through the last 10 years of medium and high CVEs (not a
terrific metric, but it's been a relatively stable one over the same
time period), we've averaged about 6 major integer overflow flaws a
year. https://outflux.net/slides/2024/lss-na/#/2
[2] This also lets early adopters of hardening mitigations use things
like the "warn_limit" sysctl to get enforcement immediately once they've
validated their workloads.
[3] e.g. Rust has explicitly wrapping and non-wrapping types, C++ has
operator overloading, etc.
[4] https://lore.kernel.org/lkml/[email protected]/
[5] Things are more fully developed on the Clang side, so more work
would be needed on GCC to reach parity, but the bulk of the
infrastructure exists there. Compared to Clang, GCC needs:
- unsigned integer overflow sanitizer
- implicit truncation sanitizer
- decouple "undefined" from "overflow" (i.e. allow sanitizers to work with
-fno-strict-overflow)
[6] https://outflux.net/slides/2024/lss-na/#/30 and the next few slides
[7] https://github.com/llvm/llvm-project/pull/86618
[8] It's not pretty and totally not upstreamable as-is, but it does
basically work. Many coverage areas are excluded, but the scope of what's
needed is observable. Notably, this has not been updated to use the
"wraps" attribute, which should make refactoring much less ugly:
https://git.kernel.org/pub/scm/linux/kernel/git/kees/linux.git/log/?h=wip/v6.9-rc2/unsigned-overflow-sanitizer
[9] https://lore.kernel.org/all/9162660e-2d6b-47a3-bfa2-77bfc55c817b@paulmck-laptop/
[10] https://www.open-std.org/jtc1/sc22/wg14/www/docs/n3201.pdf
--
Kees Cook
From: Kees Cook
> Sent: 08 May 2024 00:28
>
> Over the last decade or so, our work hardening against weaknesses
> in various kernel APIs and eliminating the ambiguities in C language
> semantics have traditionally been somewhat off in one corner or another
> of the Linux codebase. This topic is going to be much different as
> it is ultimately about the C type system, which is rather front and
> center. So, hold on to your hats while I try to explain what's desired
> here. Please try to reserve judgement until the end; as we've explored
> the topic we've found a lot of nuances, which I've tried to touch on
> below. I'm hoping folks can have an open mind about all this and not
> jump to any conclusions without first hearing me out. :)
>
>
> Problem to Solve
> ================
> The Linux kernel has consistently suffered from unexpected arithmetic
> overflow bugs. These lead to any number of exploitable conditions[0].
> Our continuing efforts to improve things (refcount_t, alloc_size(),
> etc) have helped in some specific areas, but on the whole, we've had a
> relatively unchanged count of serious arithmetic overflow flaws over the
> life of the project[1]. This is not tolerable, and we should, all of us,
> make the effort needed to put an end to it in a systematic way.
Is it April 1?
Have you estimated the performance cost of checking the result of
all integer arithmetic.
If you have a cpu with 'signed/unsigned add(etc) with trap on overflow'
instructions then maybe you could use them to panic the kernel.
But otherwise you'll need a conditional branch after pretty much
every arithmetic instruction.
As well as the code bloat there is likely to be a 50% chance they
are mis-predicted slowing things down a lot more.
IIRC at least some x86 cpu do not default to static prediction (eg
backwards taken forwards not) but always use data from the branch
prediction logic - so the first time a branch is seen it is predicted
randomly.
David
-
Registered Address Lakeside, Bramley Road, Mount Farm, Milton Keynes, MK1 1PT, UK
Registration No: 1397386 (Wales)
On Tue, 7 May 2024 at 16:27, Kees Cook <[email protected]> wrote:
>
> When I say "overflow", I mean "overflow and underflow", but more
> specifically I mean "wrap-around". This is not about "undefined
> behavior". We already demand from our compilers that all our arithmetic
> uses a well-defined overflow resolution strategy; overflow results in
> wrap-around (thanks to "-fno-strict-overflow").
I'm still entirely unconvinced.
The thing is, wrap-around is not only well-defined, it's *common*, and
*EXPECTED*.
Example:
static inline u32 __hash_32_generic(u32 val)
{
return val * GOLDEN_RATIO_32;
}
and dammit, I absolutely DO NOT THINK we should annotate this as some
kind of "special multiply".
I have no idea how many of these exist. But I am 100% convinced that
making humans annotate this and making the source code worse is
absolutely the wrong approach.
Basically, unsigned arithmetic is well-defined as wrapping around, and
it is so for a good reason.
So I'm going to have a HARD REQUIREMENT that any compiler complaints
need to be really really sane. They need to detect when people do
things like this on purpose, and they need to SHUT THE ^&% UP about
the fact that wrap-around happens.
Any tool that is so stupid as to complain about wrap-around in the
above is a BROKEN TOOL THAT NEEDS TO BE IGNORED.
Really. This is non-negotiable.
This is similar to the whole
unsigned int a, b;
if (a+b < a) ..
kind of pattern: a tool that complains about wrap-around in the above
is absolutely broken sh*t and needs to be ignored.
So I think you need to limit your wrap-around complaints, and really
think about how to limit them. If you go "wrap-around is wrong" as
some kind of general; rule, I'm going to ignore you, and I'm going to
tell people to ignore you, and refuse any idiotic patches that are the
result of such idiotic rules.
Put another way the absolute first and fundamental thing you should
look at is to make sure tools don't complain about sane behavior.
Until you have done that, and taken this seriously, this discussion is
not going to ever result in anything productive.
Linus
On Wed, May 08, 2024 at 10:52:44AM -0700, Linus Torvalds wrote:
> On Tue, 7 May 2024 at 16:27, Kees Cook <[email protected]> wrote:
> [...]
> Put another way the absolute first and fundamental thing you should
> look at is to make sure tools don't complain about sane behavior.
Agreed, and I explicitly called this out in the proposals, including
adding several idioms that have been found besides the case you mention:
> > - allow for common idioms to bypass sanitizers:
> > - explicit wrap-around tests: if (var + offset < var)
> > - loop iterator wrap-around during post-decrement: while (var--)
> > - negative unsigned constants: -1UL
What I need, though, is for _intent_ to be captured at the source level.
Unfortunately neither compilers nor humans are omniscient. Wrapping vs
non-wrapping intent can only rarely be unambiguously determined. I tried
to explain that here:
> > This is what is meant through-out by "ambiguous": the _intent of the
> > author_ can be ambiguous as it relates to whether a calculation is
> > meant to wrap-around. That it wraps around on overflow is not ambiguous:
> > it will wrap-around. :) See "Terminology Considerations".
> >
> > This is the corner stone of the problem: even though the behavior of
> > overflow is well-defined, so many authors so often don't correctly handle
> > it that the results threaten the integrity of Linux as a whole. C makes
> > it too easy to get it wrong, so we are left needing to fix this at a
> > fundamental level. This is not a developer education problem; it is a
> > problem with C language semantics. "Just do it correctly" has not
> > worked.
> The thing is, wrap-around is not only well-defined, it's *common*, and
> *EXPECTED*.
Yes, common, but that still means "sometimes unexpected". The fact that
when wrap-around is wanted, an author does nothing different from when
it is unwanted is the core of the problem: C doesn't provide a way for
us to see intent. We need to fix this.
> Example:
>
> static inline u32 __hash_32_generic(u32 val)
> {
> return val * GOLDEN_RATIO_32;
> }
But what about:
static inline u32 __item_offset(u32 val)
{
return val * ITEM_SIZE_PER_UNIT;
}
All I did was change the names of things and now we have to wonder if
the result is going to be used for indexing or sizing, and maybe it
never considered that there might be a way for val to be greater than
UINT_MAX / ITEM_SIZE_PER_UNIT.
So instead, how about:
static inline u32_wrap __hash_32_generic(u32_wrap val)
{
return val * GOLDEN_RATIO_32;
}
Now intent is clear.
> and dammit, I absolutely DO NOT THINK we should annotate this as some
> kind of "special multiply".
Yes, I agree, annotating the calculations individually seems like it would
make things much less readable. And this matches the nearly universal
feedback from developers. The solution used in other languages, with
much success, is to tie wrapping intent to types. We can do the same.
> I have no idea how many of these exist. But I am 100% convinced that
> making humans annotate this and making the source code worse is
> absolutely the wrong approach.
I'd like to make the source better, not worse. :) But if we're going
to solve this, and do it incrementally, I think progressively updating
types is the way to go. We have used types in plenty of places where we
want the compiler to help with checking (gfp_t, pid_t, etc), or with
specific behaviors (atomic_t, refcount_t, etc). This would be more of
that, though, yes, to a greater degree.
> So I think you need to limit your wrap-around complaints, and really
> think about how to limit them. If you go "wrap-around is wrong" as
> some kind of general; rule, I'm going to ignore you, and I'm going to
> tell people to ignore you, and refuse any idiotic patches that are the
> result of such idiotic rules.
This doesn't take into account the reality of deployments worldwide that
are getting exploited by unexpected wrap-around. There's no problem with
wrap-around per se, it's that we have no source-level way to indicate
when it is _intended_. I would phrase the rule as "ambiguous intent of
wrap-around is wrong".
> Put another way the absolute first and fundamental thing you should
> look at is to make sure tools don't complain about sane behavior.
What do you see as the solution for the ambiguous intent problem?
> Until you have done that, and taken this seriously, this discussion is
> not going to ever result in anything productive.
I think I've shown pretty clearly that I take this seriously. We have
been working out feasibility and potential directions for some time now,
engaging with compiler communities, building the tooling needed to do
this with as minimal impact as possible, etc. I didn't send this RFC
for fun. :)
But let me make sure we're on the same page: do you agree that we need
to protect Linux from classes of bugs? That there is value in protecting
our billions of users from avoidable and exploitable flaws that have
literally life-threatening consequences? If we don't agree that there
is a problem here worth solving, then yes, it will be hard to have a
productive discussion.
And please remember that I'm not saying "let's fix it overnight", I'm
looking to coordinate a best way forward. I want to make a plan. Neither
human nor compiler omniscience has manifested, so what's the next step?
-Kees
--
Kees Cook
On Wed, 8 May 2024 at 12:45, Kees Cook <[email protected]> wrote:
>
> On Wed, May 08, 2024 at 10:52:44AM -0700, Linus Torvalds wrote:
> > Example:
> >
> > static inline u32 __hash_32_generic(u32 val)
> > {
> > return val * GOLDEN_RATIO_32;
> > }
>
> But what about:
>
> static inline u32 __item_offset(u32 val)
> {
> return val * ITEM_SIZE_PER_UNIT;
> }
What about it? I'm saying that your tool NEEDS TO BE SMART ENOUGH to
see the "what about".
> All I did was change the names of things and now we have to wonder if
> the result is going to be used for indexing or sizing
Exactly. Your tool needs to take that into account.
Any kind of mindless "this can wrap around" is inexcusable.
It needs to be smarter than that. And yes, that means exactly taking
into account how the result of the possible wrap-around is actually
used.
If it's used as a size or as an array index, it might be a problem.
But if it's used for masking and then a *masked* version is used for
an index, it clearly is NOT a problem.
IOW, exactly the same as "a+b < a". Yes, "a+b" might wrap around, but
if the use is to then compare it with one of the addends, then clearly
such a wrap-around is fine.
A tool that doesn't look at how the result is used, and just blindly
says "wrap-around error" is a tool that I think is actively
detrimental.
And no, the answer is ABSOLUTELY NOT to add cognitive load on kernel
developers by adding yet more random helper types and/or functions.
We already expect a lot of kernel developers. We should not add on to
that burden because of your pet project.
Put another way: I'm putting the onus on YOU to make sure your pet
project is the "Yogi Bear" of pet projects - smarter than the average
bear.
As long as you are approaching this from a "this puts the onus on
others", *YOU* are the problem.
Be the solution, not the problem.
Linus
On Wed, May 08, 2024 at 01:07:38PM -0700, Linus Torvalds wrote:
> On Wed, 8 May 2024 at 12:45, Kees Cook <[email protected]> wrote:
> >
> > On Wed, May 08, 2024 at 10:52:44AM -0700, Linus Torvalds wrote:
> > > Example:
> > >
> > > static inline u32 __hash_32_generic(u32 val)
> > > {
> > > return val * GOLDEN_RATIO_32;
> > > }
> >
> > But what about:
> >
> > static inline u32 __item_offset(u32 val)
> > {
> > return val * ITEM_SIZE_PER_UNIT;
> > }
>
> What about it? I'm saying that your tool NEEDS TO BE SMART ENOUGH to
> see the "what about".
This is verging on omniscience, though. Yes, some amount of additional
reasoning can be applied under certain conditions (though even that would
still require some kind of annotation), but GCC can't even reliably figure
out if a variable is unused in a single function. We're not going to be
able to track overflow tainting throughout the code base in a useful
fashion.
> IOW, exactly the same as "a+b < a". Yes, "a+b" might wrap around, but
> if the use is to then compare it with one of the addends, then clearly
> such a wrap-around is fine.
Yes, but it is an absolutely trivial example: it's a single expression
with only 2 variables. Proving that the value coming in from some
protocol that is passed through and manipulated by countless layers of the
kernel before it gets used inappropriately is not a reasonably solvable
problem. But we can get at the root cause: the language (and our use of
it) needs to change to avoid the confused calculation in the first place.
> A tool that doesn't look at how the result is used, and just blindly
> says "wrap-around error" is a tool that I think is actively
> detrimental.
I do hear what you're saying here. I think you're over-estimating the
compiler's abilities. And as I mentioned in the RFC, finding known bad
cases to protect is the reverse of what we want for coverage: we want
to _not_ cover the things we know to be _safe_. So we want to find
(via compiler or annotation) the cases where overflow is _expected_.
> We already expect a lot of kernel developers. We should not add on to
> that burden because of your pet project.
I think it's a misunderstanding to consider this a pet project. C's lack
of overflow intent has spawned entire language ecosystems in reaction.
There are entire classes of flaws that exist specifically because of this
kind of confusion in C. It is the topic of countless PhD research efforts.
People who care about catching overflows can slowly add the type
annotations over the next many years, and we'll reach reasonable coverage
soon enough. It doesn't seem onerous: I'm not asking that people even
do it themselves (though I'd love the help), I'm just trying to find
acceptance for annotations about where the sanitizer can ignore overflow.
> Put another way: I'm putting the onus on YOU to make sure your pet
> project is the "Yogi Bear" of pet projects - smarter than the average
> bear.
Sure, but if the bar is omniscience, that's not a path forward.
I haven't really heard a viable counterproposal here. Let me try something
more concrete: how would you propose we systemically solve flaws like
the one fixed below? And note that the first fix was incomplete and it
took 8 years before it got fully fixed:
a723968c0ed3 ("perf: Fix u16 overflows") (v4.3)
382c27f4ed28 ("perf: Fix perf_event_validate_size()") (v6.7)
Because the kernel didn't catch when the u16 overflowed, it allowed for
kernel memory content exposure to userspace. And that's just the place
that it got noticed. With the struct holding the u16 is referenced in
360 different source files, it's not always a trivial analysis. But,
for example, the sanitizer not finding a "wraps" annotation on the
perf_event::read_size variable would have caught it immediately on
overflow.
And I mean this _kind_ of bug; not this bug in particular. I'm just
using it as a hopefully reasonable example of the complexity level we
need to solve under.
-Kees
--
Kees Cook
On Wed, May 08, 2024 at 12:22:38PM +0000, David Laight wrote:
> Have you estimated the performance cost of checking the result of
> all integer arithmetic.
I hadn't included that in my already very long email as performance is
somewhat secondary to the correctness goals. Perhaps that was a mistake,
as it is going to be everyone's first question anyway. :) But yes,
I did have an initial analysis:
Performance Considerations
==========================
Adding arithmetic overflow checks, regardless of implementation,
will add more cycles. The good news is that the overflow outcome can
be pessimized, and checking the overflow bit on most architectures is
extraordinarily fast. Regardless, for many Linux deployments, the cost
of this correctness is seen as acceptable, though all users will benefit
from the fixing of bugs that the mitigation will find.
Looking specifically at proposal #1 below, we can do some estimations. For
a defconfig+kvm+FORTIFY config on v6.9-rc2 x86_64, the signed integer
overflow (SIO) checking is added in 21,552 places. The unsigned integer
overflow (UIO) checking is around 55,000 (though I would expect a good
portion of these to be eliminated as they are shown to be "wrap-around
expected"). Running with SIO enabled is mostly flawless, though a long
tail of false positives is expected. Running with UIO is not ready for
general consumption, and performing benchmarking there is not going to
give useful numbers. However, we can at least attempt to extrapolate from
an SIO build how a full SIO+UIO build would behave. For example, based
on instance counts, we could maybe assume SIO+UIO to be ~3x compared to
SIO. This could easily be an over or under estimation, though. Regardless,
some rough draft comparisons:
Image size
Stock 60197540
SIO,warn 60299436 +0.169%
SIO,trap 60195567 -0.003% (trap mode probably found code to drop)
Kernel build 10x benchmark Avg(s) Std Dev
Stock 439.58 1.68
SIO,warn 444.20 (+1.00%) 1.35
SIO,trap 442.10 (+0.57%) 1.52
> If you have a cpu with 'signed/unsigned add(etc) with trap on overflow'
> instructions then maybe you could use them to panic the kernel.
> But otherwise you'll need a conditional branch after pretty much
> every arithmetic instruction.
Yes. This would be true for any implementation. Thankfully in some
places where bounds checking has already happened manually, the added
instrumentation checks will have been optimized away. But yes, turning
such a mitigation on isn't without impact. :) But a significant install
base is interested in correctness within a reasonable performance
budget. And some will take correctness over all other considerations.
> As well as the code bloat there is likely to be a 50% chance they
> are mis-predicted slowing things down a lot more.
> IIRC at least some x86 cpu do not default to static prediction (eg
> backwards taken forwards not) but always use data from the branch
> prediction logic - so the first time a branch is seen it is predicted
> randomly.
Sure, though I think the nuances of CPU design are somewhat tangential
to the overall topic: how do we provide a way for Linux to gain this
correctness coverage? It's accepted that there will be a non-trivial
impact, and I agree we can start to consider how to optimize
implementations. But for now I'd like to solve for how to even represent
arithmetic overflow intent at the source level.
-Kees
--
Kees Cook
On Wed, 8 May 2024 at 15:54, Kees Cook <[email protected]> wrote:
>
> Sure, but if the bar is omniscience, that's not a path forward.
I really don't think there's a lot of omniscience involved at all.
> I haven't really heard a viable counterproposal here.
So let me make the counter-proposal that you actually concentrate on
very limited cases.
Baby steps, in other words.
For example, the most common case of overflow we've ever had has very
much been array indexing. Now, sometimes that has actually been actual
undefined behavior, because it's been overflow in signed variables,
and those are "easy" to find in the sense that you just say "no, can't
do that". UBSAN finds them, and that's good.
So I'd suggest seeing if we can catch the cases that *technically*
aren't UB, but match dangerous overflow situations. IOW, start with
very limited and very targeted things to look out for.
For example: some of the "this is not UB" may actually be trivial
mistakes that come about because of the silent C type casting rules:
overflow in unsigned arithmetic isn't UB, but it's actually very easy
to make arithmetic unsigned "by mistake".
IOW, a pattern to look out for might be
int a;
...
a * sizeof(xyz);
where "sizeof" obviously is unsigned, and then the C integer
promotions end up making this a well-defined operation that probably
really *is* dangerous, because the integer promotion basically adds an
implicit cast from "int" to "size_t" in there.
End result: it's not UB, but maybe it is not-*accidentally*-UB, and
thus maybe worth a warning? See what I'm saying?
So *that* I feel could be something where you can warn without a ton
of compiler smarts at all. If you see an *implicit* cast to unsigned
and then the subsequent operations wraps around, it's probably worth
being a lot more worried about.
Now, another thing to do might be to treat assignments (and again,
implicit casts) to 'size_t' specially. In most compilers (certainly in
gcc), "size_t" is a special type.
Now, in the kernel, we don't actually use __builtin_size_t (the kernel
started out with a very standalone type system, and I think it
actually predated gcc's __builtin_size_t or maybe I just wasn't aware
of it). But we certainly _could_ - or we could at least use some
special marked type for our own 'size_t'.
And basically try to catch cases where arithmetic is explicitly used
for a size calculation: things like 'kmalloc()' etc are the obvious
things. And yes, the result will then have an (implicit) cast to
'size_t' as part of the calling convention.
That's another "pattern that sounds relevant and easy to notice for a compiler".
And, finally, simply pointer arithmetic. Again, this is *not* some
"omniscience required". This is something very obvious where the
compiler is *very* aware of it being pointer arithmetic, because
pointer arithmetic has that implicit (and important) "take size of
object into account".
So again, if you see an integer expression that leads to pointer
arithmetic, at that point the overflow very much is relevant.
See? Three very *targeted* things where
(a) the compiler is very much aware of the use
(b) you can fairly confidently say "integer arithmetic wraparound is
a dangerous thing even when not UB".
So what I object to - loudly - is some completely bogus argument of
"integer wraparound is always wrong".
And dammit, I have seen you state something that sounds very much like
that several times, most recently in just this thread where you were
arguing for a special "u32_wrap" type just to allow wrapping without
complaints.
And I think it's that overly-generic "wrap-around is wrong" argument
that is completely bogus and needs to be nipped in the bud.
Wrap-around is not only well-defined, it's *useful*, and it's *used*,
and I find tools that warn about good code (like our existing hash
functions) to be *HORRIBLE*.
False positive warnings make real warnings worthless.
And so I think warning about wrap-around in general is mindless and
wrong and actively counter-productive. If people then just "fix" the
warning by casting it to "u32_wrap", you have only caused problems.
But catching wrap-around in *specific* cases, if you can argue for why
it's wrong in *those* cases: that sounds fine.
And I tried to give three examples of such specific cases above - I'm
sure there are many others.
To conclude: I think the path forward is not at all omniscience. It's
"limit yourself to cases that matter". Don't think of wrap-around as
some "global evil" like you seem to do. Think of it as wrong in
_specific_ cases, and see if you can target those cases.
Start small, in other words.
Now, to take the specific example you brought up: commits a723968c0ed3
and 382c27f4ed28. Honestly, I think you'll find that that one wouldn't
have been caught by some arithmetic wrap-around issue, because the
*arithmetic* was actually done in a type that didn't even wrap around.
IOW, in that case, you had "int size", and none of the arithmetic on
the size actually wrapped.
No, the only point where that actually failed was then when a
(non-overflowing, non-wrapping) final value was assigned to a 16-bit
field, ie the problem only ever happened at the final assignment:
event->read_size = size;
where no overflow had ever happened before that.
So in *that* case, you actually have a much more interesting
situation. Not wrap-around, not overflow, but "implicit cast drops
significant bits".
And yes, I do think implicit integer casts are dangerous. Often *more*
dangerous than arithmetic overflow and wrapping. We've had absolutely
tons of them. Some of our most traditional bugs have very much been
about implicit casting losing bits and causing problems as a result.
In fact, that's the reason we have MAX_RW_COUNT - because we used to
have too many places where various drivers or filesystems ended up
casting a "size_t" count argument down to "int count". So we are
literally violating POSIX semantics for some of the most important
system calls (read() and write()) as a safety measure against hidden
implicit truncating casts.
I think that would be a completely different area that might be worth
looking at: instrumenting implicit casts for "drops bits". I'm afraid
that it's just *so* common than we might not be able to do that
sanely.
But again, maybe it would be worth looking into, at least for some
limited cases. To go back to your particular example, it might be
worth trying to limit it for unusual type sizes like implicit casts to
'u16' or bitfields: not because those type sizes are magical, but
because it might be a way to limit the pain.
Summary: targeted baby steps, not some draconian "wrap-around is wrong".
Linus
On Wed, 8 May 2024 at 16:47, Linus Torvalds
<[email protected]> wrote:
>
> But again, maybe it would be worth looking into, at least for some
> limited cases. To go back to your particular example, it might be
> worth trying to limit it for unusual type sizes like implicit casts to
> 'u16' or bitfields: not because those type sizes are magical, but
> because it might be a way to limit the pain.
I think it would be interesting in general to have some kind of
warning for "implicit cast drops bits".
I fear that we'd have an enormous about of them, and maybe they'd be
unsolvable without making the code *much* uglier (and sometimes the
fix might be to add an explicit cast to document intentionally dropped
bits, but explicit casts have their own issues).
So that's why I feel like it might be interesting to see if limiting
such checks to only "unusual" types might give us a manageable list of
worrisome places.
I think it *would* have flagged the perf u16 overflow case. Again: I
don't think that was actually ever overflow or wrap-around in the
arithmetic sense, and it was purely a "assignment to smaller field
truncated bits" issue.
Which again is most definitely not undefined behavior, but I would not
be at all surprised if it was a much more common issue than actual
arithmetic overflow is.
Linus
On Wed, 8 May 2024 at 16:47, Linus Torvalds
<[email protected]> wrote:
>
> So *that* I feel could be something where you can warn without a ton
> of compiler smarts at all. If you see an *implicit* cast to unsigned
> and then the subsequent operations wraps around, it's probably worth
> being a lot more worried about.
Side note on this part: quite often, because of C promotion rules, you
have "int" as an "intermediate" type.
IOW, while I had that example of
int a;
...
a * sizeof(xyz);
being questionably not-UB (because "int a" gets promoted to unsigned
as part of C integer promotion, and thus you really had a signed value
that was involved in unsigned wrap-around), if you have
unsigned short a;
...
a * sizeof(xyz);
then technically that 'a' is first promoted to 'int' (because all
arithmetic on types smaller than int get promoted to int), and then it
gets promoted to size_t because the multiply gets done in the bigger
type.
So in one sense that unsigned multiply may actually have involved a
cast from a signed type, but at the same time it's not at all in that
kind of "accidentally not UB" class.
I suspect most compilers would have combined the two levels of
implicit casts into just one, so at no point outside of perhaps some
very intermediate stage will it show as a signed int cast to unsigned,
but I thought I'd mention it anyway. Implicit casts get nasty not just
in assignments, but also in these kinds of situations.
I still suspect the "implicit truncating cast at assignment" is likely
a much more common case of loss of information than actual arithmetic
wrap-around, but clearly the two have commonalities.
Linus
On Wed, May 08, 2024 at 04:47:25PM -0700, Linus Torvalds wrote:
> For example, the most common case of overflow we've ever had has very
> much been array indexing. Now, sometimes that has actually been actual
> undefined behavior, because it's been overflow in signed variables,
> and those are "easy" to find in the sense that you just say "no, can't
> do that". UBSAN finds them, and that's good.
Yes, the array bounds checking work has been going well. It's been
about 5 years now, plucking out all the weird compiler behaviors,
refactoring code to get rid of ambiguous patterns, etc. It's turtles
and compiler extensions all the way down. It's been a real education on
"this will be easy: the compiler already has all the information". Only
to find, no, it's not, because no one has tried to make any of it work
together sanely in 50 years. But we're finally at the tail end of it,
with clear and unambiguous semantics and mitigations now.
> So I'd suggest seeing if we can catch the cases that *technically*
> aren't UB, but match dangerous overflow situations. IOW, start with
> very limited and very targeted things to look out for.
Yes, exactly. What I'd said in the RFC was that from a terminology
perspective I don't want to focus on "undefined behavior", this means
a very specific thing to the compiler folks. I'm focused on what
_unexpected_ things actually happens in the real world that lead to
exploitable flaws.
> So *that* I feel could be something where you can warn without a ton
> of compiler smarts at all. If you see an *implicit* cast to unsigned
> and then the subsequent operations wraps around, it's probably worth
> being a lot more worried about.
I agree, implicit casts are worth exploring. It's a more limited set of
behaviors, but I remain skeptical about the utility of catching them since
the visibility of those kinds of promotions can quickly go out of scope.
> And basically try to catch cases where arithmetic is explicitly used
> for a size calculation: things like 'kmalloc()' etc are the obvious
> things. And yes, the result will then have an (implicit) cast to
> 'size_t' as part of the calling convention.
We've been doing this kind of static analysis of allocation size
mistakes for a while, but it remains not very well introspected by the
compiler, making it a long game of whack-a-mole. And generally speaking
all the wrapping around has already happened way before it hits the
allocator. We've mostly dealt with all the low hanging code pattern fruit
in this area, but it could be a place to add type-based compiler smarts.
> And, finally, simply pointer arithmetic. Again, this is *not* some
> "omniscience required". This is something very obvious where the
> compiler is *very* aware of it being pointer arithmetic, because
> pointer arithmetic has that implicit (and important) "take size of
> object into account".
Yes, that is already in progress too. Now that we've got __counted_by for
flex arrays, the next addition is __counted_by for pointers. Coverage
there will continue to grow. There is, unfortunately, a rather lot of
alloc-and-forget going on in the kernel where object sizes are just
thrown away. We've done some refactoring in places to add it, but I
suspect the need for that will become more common once we gain coverage
for pointer offsets.
> So again, if you see an integer expression that leads to pointer
> arithmetic, at that point the overflow very much is relevant.
Right, and we've already been doing all of these things. They do all share
the common root cause, though: unexpected wrap-around. But I hear you:
don't go after the root cause, find high-signal things that are close to
it.
> So what I object to - loudly - is some completely bogus argument of
> "integer wraparound is always wrong".
Just so it's not mistaken, I didn't say "always": I said "can be". This
was never a proposal to outlaw all wrap-around. :P
> But catching wrap-around in *specific* cases, if you can argue for why
> it's wrong in *those* cases: that sounds fine.
Right. I mean, that is basically what I proposed. It was just over a
much larger class than it seems you'll tolerate. :P You're asking to keep
the scope smaller, and aimed at places where we know it can go wrong. I
still think this is backwards from what would be best coverage. For the
highest level of flaw mitigation, we want to exclude that which is proven
safe, not try to catch things that might be unsafe. But I do try to be
pragmatic, and it doesn't sound like that approach will be accepted here.
> So in *that* case, you actually have a much more interesting
> situation. Not wrap-around, not overflow, but "implicit cast drops
> significant bits".
Yup! This is what I was talking about in the RFC: implicit integer
truncation. It *is* very nasty, I agree. We can get started on this next
then. I poked around at it earlier this year[1]. My plan was to tackle
it after finishing signed integer overflows (which is well underway).
> And yes, I do think implicit integer casts are dangerous. Often *more*
> dangerous than arithmetic overflow and wrapping. We've had absolutely
> tons of them. Some of our most traditional bugs have very much been
> about implicit casting losing bits and causing problems as a result.
I really started screaming when I saw this one:
https://git.kernel.org/linus/6311071a056272e1e761de8d0305e87cc566f734
u8 num_elems = 0;
...
nla_for_each_nested(nl_elems, attrs, rem_elems)
num_elems++; /* Whoops */
elems = kzalloc(struct_size(elems, elem, num_elems), GFP_KERNEL);
...
nla_for_each_nested(nl_elems, attrs, rem_elems) {
elems->elem[i].data = nla_data(nl_elems);
...
(The good news for this particular case is that the fix for this bug
almost literally crossed paths with the wave of __counted_by annotations
we landed[2], after which overflows of the elems->elem[] array would
have been noticed by CONFIG_UBSAN_BOUNDS.)
> I think that would be a completely different area that might be worth
> looking at: instrumenting implicit casts for "drops bits". I'm afraid
> that it's just *so* common than we might not be able to do that
> sanely.
During the initial investigation, I tripped over several idioms we'll
need to deal with (possibly in the compiler). (2 are basically variations
of ones from the overflow calculation cases.)
- truncation of constant expressions:
u8 var = ~(1 << 3);
This becomes int, and then all the high bits are thrown away. But
intention is nearly universally that the expression should be
applied only to the variable width. i.e. what is meant is:
u8 var = (u8)~(1 << 3);
Allowing this from the compiler side makes sense since it's a constant
expression. There may be cases where it is NOT intended, though, if
there is some mismatch of type widths hiding in macros that resolve
to a constant expression. But refactoring all these instances to
include an explicit cast seems prone to inducing maintainer rage.
- basically all cases where the assigned variable is smaller than u32:
...checksum(const u8 *buf, u8 len)
...
u8 sum;
int a;
for (a = 0; a < len; a++)
sum += buf[a];
buf[a] goes from u8 to int, then added to a u8 value (no
overflow), but then written back and truncated.
This gets immediately to the ambiguity case, though. This is
nearly indistinguishable from the "num_elems++" example above.
So what do we do? We can add the "wraps" attribute to "sum"?
We can use a helper for the "+="?
Or even just simple math between u8s:
while (xas->xa_offset == 255) {
xas->xa_offset = xas->xa_node->offset - 1;
Is it expecting to wrap (truncate)? How is it distinguished from
the "num_elems++" case?
- "while (var--)" when var is a smaller type than u32: the final
post-decrement gets truncated from the promoted "0 - 1" int expression.
Ignore post decrements only when the variable is not read again?
Ignore it only in "while" cases?
- ERR_PTR() returns long. But all cases of its assignment are into int
variables. I need to spend more time looking at this. There
shouldn't be any loss of information here, since it's all low negative
values. The sanitizer may be upset that 0xffffffffffffffff being
converted to 0xffffffff is "losing bits" but they're both just -1.
We might also just be able to change ERR_PTR() to return int, and add
the cast directly:
- return (long) ptr;
+ return (int)(long) ptr;
>[...thread merge...]
> I think it would be interesting in general to have some kind of
> warning for "implicit cast drops bits".
>
> I fear that we'd have an enormous about of them, and maybe they'd be
> unsolvable without making the code *much* uglier (and sometimes the
> fix might be to add an explicit cast to document intentionally dropped
> bits, but explicit casts have their own issues).
This is immediately the place we find ourselves. :)
> So that's why I feel like it might be interesting to see if limiting
> such checks to only "unusual" types might give us a manageable list of
> worrisome places.
Well, we'd want to catch the "num_elems++" case, and that's not
involving any unusual types. How do you propose we distinguish that from
the u8 checksum case, etc? I had been planning to use the "wraps"
attribute on the variable. I.e. mark all the places where we expect
truncation.
>[...thread merge...]
> I still suspect the "implicit truncating cast at assignment" is likely
> a much more common case of loss of information than actual arithmetic
> wrap-around, but clearly the two have commonalities.
Both of the "real world" examples we had in this thread were due
to implicit truncation. I do think it's less noisy than the unsigned
arithmetic cases, but it does have significant commonalities. So much so
that it still looks to me like using the "wraps" attribute makes sense
for this.
> Summary: targeted baby steps, not some draconian "wrap-around is wrong".
I still think we should bite the bullet, but let's finish up signed
overflow (this just keeps finding accidental but mostly harmless
overflows), and then dig into implicit integer truncation next.
Thank you for spending the time to look at all of this. It's a big topic
that many people feel very strongly about, so it's good to get some
"approved" direction on it. :)
-Kees
[1] These are NOT meant to be upstreamed as-is. We have idiom exclusions
to deal with, etc, but here's the tree I haven't refreshed yet:
https://git.kernel.org/pub/scm/linux/kernel/git/kees/linux.git/log/?h=dev/v6.8-rc2/signed-trunc-sanitizer
[2] c14679d7005a ("wifi: cfg80211: Annotate struct cfg80211_mbssid_elems with __counted_by")
--
Kees Cook
On Wed, May 08, 2024 at 11:11:35PM -0700, Kees Cook wrote:
> > I think it would be interesting in general to have some kind of
> > warning for "implicit cast drops bits".
> >
> > I fear that we'd have an enormous about of them, and maybe they'd be
> > unsolvable without making the code *much* uglier (and sometimes the
> > fix might be to add an explicit cast to document intentionally dropped
> > bits, but explicit casts have their own issues).
Seapking of which, I recently had to work around an overactive
compiler UBSAN which complained about this:
struct ext2_super {
...
__u32 time_lo;
__u32 time_high;
...
}
time_t now;
sb->time_low = now;
sb->time_high = now >> 32;
This is obviously (to a human) correct, but because of stupid compiler
tricks, in order to silence compiler-level and ubsan complaints, this
got turned into:
sb->time_low = now & 0xffffffff;
#if (SIZEOF_TIME_T > 4)
sb->time_high = (now >> 32) & EXT4_EPOCH_MASK;
#else
sb->time_high = 0;
#endif
and in the opposite case, I was forced to write:
#if (SIZEOF_TIME_T == 4)
return *lo;
#else
return ((time_t)(*hi) << 32) | *lo;
#endif
.. and this made me very sad. Grumble....
- Ted
On Thu, 9 May 2024 at 07:09, Theodore Ts'o <[email protected]> wrote:
>
> struct ext2_super {
> ...
> __u32 time_lo;
> __u32 time_high;
> ...
> }
>
> time_t now;
>
> sb->time_low = now;
> sb->time_high = now >> 32;
>
> This is obviously (to a human) correct,
Actually, it's not correct at all.
If time_t is 32-bit, that "now >> 32" is broken due to how C shifts
are defined. For a 32-bit type, only shifts of 0-31 bits are
well-defined (due to hardware differences).
> but because of stupid compiler
> tricks, in order to silence compiler-level and ubsan complaints, this
> got turned into:
>
> sb->time_low = now & 0xffffffff;
> #if (SIZEOF_TIME_T > 4)
> sb->time_high = (now >> 32) & EXT4_EPOCH_MASK;
> #else
> sb->time_high = 0;
> #endi
This is the wrong solution.
But the solution to the undefined shift isn't some #ifdef.
The idiomatic C solution is to do
high_bits = (all_bits >> 16) >> 16;
which works even if 'all_bits' is 32 bit, and the compiler will know
this idiom, and turn it into just 0.
Going the other way is similar:
all_bits = low_bits + ((u64) high_bits << 16) << 16);
and again, the compiler will recognize this idiom and do the right
thing (and if 'all_bits' is only 32-bit, the compiler will optimize
the high bit noise away).
And yes, this is not great, but there you have it: C was designed to
be a high-level assembler, and you see the effects of "this is how
many hardware shifters work". The shift instructions on many (most?)
architectures end up being limited to the word width.
We actually have some helpers for this in <linux/wordpart.h>:
#define upper_32_bits(n) ((u32)(((n) >> 16) >> 16))
#define lower_32_bits(n) ((u32)((n) & 0xffffffff))
but we don't have that "combine 32 bits into 64 bits" helper. Maybe
worth adding.
Linus
On Thu, 9 May 2024 at 10:54, Al Viro <[email protected]> wrote:
>
> On Thu, May 09, 2024 at 08:38:28AM -0700, Linus Torvalds wrote:
>
> > Going the other way is similar:
> >
> > all_bits = low_bits + ((u64) high_bits << 16) << 16);
> >
> > and again, the compiler will recognize this idiom and do the right
> > thing (and if 'all_bits' is only 32-bit, the compiler will optimize
> > the high bit noise away).
>
> Umm... That would make sense if it was
> all_bits = low_bits + ((T) high_bits << 16) << 16);
> with possibly 32bit T. But the way you wrote that (with u64) it's
> pointless - u64 _can_ be shifted by 32 just fine.
Casting to 'T' is probably a clearer option but doesn't work very well
in a helper functions that may not know what the final type is.
Any half-way decent compiler will end up optimizing away the shifts
and adds for the high bits because they see the assignment to
'all_bits'. There's no point in generating high bits that just get
thrown away.
Linus
On Thu, 9 May 2024 at 11:08, Linus Torvalds
<[email protected]> wrote:
>
> Any half-way decent compiler will end up optimizing away the shifts
> and adds for the high bits because they see the assignment to
> 'all_bits'. There's no point in generating high bits that just get
> thrown away.
. it might also actually be a good idea *IF* we were to have some
kind of "implicit cast drops bits" warning, in that the compiler for
that case wouldn't remove the upper bits calculation, but would
trigger a warning if they are non-zero.
So there are actually potential advantages to just always apparently
doing the full 64-bit arithmetic.
Without debug warnings, it's a no-op that the compiler will just skip.
And with some hypothetical debug flag, it would be a "you are now
losing the high bits of the time value when assigning the result to a
limited 32-bit time_t" warning.
Linus
On Thu, May 09, 2024 at 11:39:04AM -0700, Linus Torvalds wrote:
> .. it might also actually be a good idea *IF* we were to have some
> kind of "implicit cast drops bits" warning, in that the compiler for
> that case wouldn't remove the upper bits calculation, but would
> trigger a warning if they are non-zero.
>
> So there are actually potential advantages to just always apparently
> doing the full 64-bit arithmetic.
>
> Without debug warnings, it's a no-op that the compiler will just skip.
> And with some hypothetical debug flag, it would be a "you are now
> losing the high bits of the time value when assigning the result to a
> limited 32-bit time_t" warning.
FWIW, the thing that somewhat worries me about having a helper along
the lines of combine_to_u64(low, high) is that
foo->splat = combine_to_u64(something, something_else);
would be inviting hard-to-catch brainos -
foo->splat = combine_to_u64(something_else, something);
would be very hard to catch on RTFS, especially when you'd been
staring at that code for a long time. Explicitly spelled out
it would be obvious which goes into bits 0..31 and which in 32..64.
On Thu, 9 May 2024 at 11:48, Al Viro <[email protected]> wrote:
>
> FWIW, the thing that somewhat worries me about having a helper along
> the lines of combine_to_u64(low, high) is that
> foo->splat = combine_to_u64(something, something_else);
> would be inviting hard-to-catch brainos -
> foo->splat = combine_to_u64(something_else, something);
Yeah, we'd have to be very clear about naming and ordering. So it
would probably have to be something like
result = combine_to_u64_hi_lo(high, low);
to be easy to use.
The good news is that if you *do* get it wrong despite clear naming,
the resulting value will be so obviously wrong that it's generally a
"Duh!" thing if you do any testing what-so-ever.
Of course, I say that as somebody who always points out that I haven't
tested my own patches at all, and they are "something like this,
perhaps?".
But having "hi_lo" kind of naming would hopefully make it really
obvious even when just looking at the source code.
Linus
On Thu, May 09, 2024 at 12:15:40PM -0700, Linus Torvalds wrote:
> On Thu, 9 May 2024 at 11:48, Al Viro <[email protected]> wrote:
> >
> > FWIW, the thing that somewhat worries me about having a helper along
> > the lines of combine_to_u64(low, high) is that
> > foo->splat = combine_to_u64(something, something_else);
> > would be inviting hard-to-catch brainos -
> > foo->splat = combine_to_u64(something_else, something);
>
> Yeah, we'd have to be very clear about naming and ordering. So it
> would probably have to be something like
>
> result = combine_to_u64_hi_lo(high, low);
>
> to be easy to use.
>
> The good news is that if you *do* get it wrong despite clear naming,
> the resulting value will be so obviously wrong that it's generally a
> "Duh!" thing if you do any testing what-so-ever.
>
> Of course, I say that as somebody who always points out that I haven't
> tested my own patches at all, and they are "something like this,
> perhaps?".
>
> But having "hi_lo" kind of naming would hopefully make it really
> obvious even when just looking at the source code.
Or something like
result = to_high32(high) | to_low32(low);
perhaps? ;-)
Re amusing things found by grepping:
unsafe_get_user(lo, &__c->sig[1], label); \
unsafe_get_user(hi, &__c->sig[0], label); \
__s->sig[0] = hi | (((long)lo) << 32); \
(compat.h, be64 unsafe_get_compat_sigset())
It is correct, actually, but here 'hi' is 'signals in range 0..31' and
'lo' - 'signals in range 32..63'. Introduced in fb05121fd6a2
"signal: Add unsafe_get_compat_sigset()", looks like nobody had read
it carefully enough for a WTF moment - at least no replies along the
lines of 'might be a good idea to use less confusing names' anywhere
on lore...
On Thu, May 09, 2024 at 08:38:28AM -0700, Linus Torvalds wrote:
> Going the other way is similar:
>
> all_bits = low_bits + ((u64) high_bits << 16) << 16);
>
> and again, the compiler will recognize this idiom and do the right
> thing (and if 'all_bits' is only 32-bit, the compiler will optimize
> the high bit noise away).
Umm... That would make sense if it was
all_bits = low_bits + ((T) high_bits << 16) << 16);
with possibly 32bit T. But the way you wrote that (with u64) it's
pointless - u64 _can_ be shifted by 32 just fine.
...
> Going the other way is similar:
>
> all_bits = low_bits + ((u64) high_bits << 16) << 16);
>
> and again, the compiler will recognize this idiom and do the right
> thing (and if 'all_bits' is only 32-bit, the compiler will optimize
> the high bit noise away).
On a 32bit system the compiler might not do the expected thing.
I had terrible trouble with the 32bit div_u64_u32() code I was
playing with getting the compiler to do 'something sensible' for
that.
I just couldn't get it to stop generating two 64bit values
(in two register pairs) and then oring them together.
I didn't try using a union - that might work.
On x64 the asm "A" (edx:eax) and "a" and "d" constraints will DTRT
but force the values into edx:eax which is ok if you are doing divides.
David
-
Registered Address Lakeside, Bramley Road, Mount Farm, Milton Keynes, MK1 1PT, UK
Registration No: 1397386 (Wales)
...
> I think that would be a completely different area that might be worth
> looking at: instrumenting implicit casts for "drops bits". I'm afraid
> that it's just *so* common than we might not be able to do that
> sanely.
Things like:
buf[0] = val;
buf[1] = val >>= 8;
buf[2] = val >>= 8;
buf[3] = val >>= 8;
for writing a value little-endian and potentially misaligned.
Really doesn't want any annotation.
I've also seen code like:
buf[0] = (unsigned char)(val & 0xff);
not only ugly by it got compiled to:
val &= 0xff // for the &
val &= 0xff // for the cast
byte write to memory.
Modern gcc doesn't do that, but...
There are some spurious casts that drop bits.
I found plenty of dubious min_t(u8/u16,...) examples.
(Well they are dubious, some are just a lot more dubious than others.)
The problem is that every one needs careful inspection just in case
the strange behaviour is required like min_t(u8, val - 1, lo_lim - 1)
which treats lo_lim of zero as 'not a limit' and I think was ok.
A slow, concerted effort to remove min_t() calls wouldn't be a bad thing.
David
-
Registered Address Lakeside, Bramley Road, Mount Farm, Milton Keynes, MK1 1PT, UK
Registration No: 1397386 (Wales)
I'm pretty sure we've tried using a sanitizer before and it had too many
false positives. So your solution is to annotate all the false
positives?
There are two main issue which make integer overflows complicated from
a static analysis perspective. 1) Places where it's intentional or
we don't care. 2) Places where the integer overflow is harmless for
one reason or another. Btw, integer overflows are a lot more common on
32 bit CPUs because obviously it's easier to overflow 4 billion than
whatever number U64_MAX is.
Here are is a sample of ten integer overflows that the user can trigger.
Maybe pick a couple and walk us through how they would be annotated?
drivers/usb/dwc3/gadget.c:3064 dwc3_gadget_vbus_draw() warn: potential integer overflow from user '1000 * mA'
3052 static int dwc3_gadget_vbus_draw(struct usb_gadget *g, unsigned int mA)
3053 {
3054 struct dwc3 *dwc = gadget_to_dwc(g);
3055 union power_supply_propval val = {0};
3056 int ret;
3057
3058 if (dwc->usb2_phy)
3059 return usb_phy_set_power(dwc->usb2_phy, mA);
3060
3061 if (!dwc->usb_psy)
3062 return -EOPNOTSUPP;
3063
3064 val.intval = 1000 * mA;
^^^^^^^^^^
mA comes from the user and we only know that it's a multiple of 2.
So here we would annotate that val.intval can store integer overflows?
Or we'd annotate mA?
3065 ret = power_supply_set_property(dwc->usb_psy, POWER_SUPPLY_PROP_INPUT_CURRENT_LIMIT, &val);
3066
3067 return ret;
3068 }
drivers/usb/class/usbtmc.c:852 usbtmc_generic_read() warn: potential integer overflow from user 'max_transfer_size + 1'
842 * wMaxPacketSize – 1) to avoid sending a zero-length
843 * packet
844 */
845 remaining = transfer_size;
846 if ((max_transfer_size % data->wMaxPacketSize) == 0)
847 max_transfer_size += (data->wMaxPacketSize - 1);
848 } else {
849 /* round down to bufsize to avoid truncated data left */
850 if (max_transfer_size > bufsize) {
851 max_transfer_size =
852 roundup(max_transfer_size + 1 - bufsize,
^^^^^^^^^^^^^^^^^^^^^
This can overflow. We should make it a rule that all size variables
have to be unsigned long. That would have made this safe on 64 bit
systems.
853 bufsize);
854 }
855 remaining = max_transfer_size;
drivers/usb/misc/usbtest.c:1994 iso_alloc_urb() warn: potential integer overflow from user 'bytes + maxp'
1974 static struct urb *iso_alloc_urb(
1975 struct usb_device *udev,
1976 int pipe,
1977 struct usb_endpoint_descriptor *desc,
1978 long bytes,
1979 unsigned offset
1980 )
1981 {
1982 struct urb *urb;
1983 unsigned i, maxp, packets;
1984
1985 if (bytes < 0 || !desc)
1986 return NULL;
1987
1988 maxp = usb_endpoint_maxp(desc);
1989 if (udev->speed >= USB_SPEED_SUPER)
1990 maxp *= ss_isoc_get_packet_num(udev, pipe);
1991 else
1992 maxp *= usb_endpoint_maxp_mult(desc);
1993
1994 packets = DIV_ROUND_UP(bytes, maxp);
^^^^^
The issue here is on a 32 bit system when bytes is INT_MAX.
1995
1996 urb = usb_alloc_urb(packets, GFP_KERNEL);
1997 if (!urb)
1998 return urb;
drivers/usb/storage/uas.c:324 uas_stat_cmplt() warn: potential integer overflow from user 'idx + 1'
322 idx = be16_to_cpup(&iu->tag) - 1;
The "- 1" makes this UINT_MAX
323 if (idx >= MAX_CMNDS || !devinfo->cmnd[idx]) {
324 dev_err(&urb->dev->dev,
325 "stat urb: no pending cmd for uas-tag %d\n", idx + 1);
^^^^^^^
Harmless integer overflow in printk.
326 goto out;
327 }
drivers/mtd/parsers/tplink_safeloader.c:101 mtd_parser_tplink_safeloader_parse() warn: potential integer overflow from user 'bytes + 1'
97 for (idx = 0, offset = TPLINK_SAFELOADER_DATA_OFFSET;
98 idx < TPLINK_SAFELOADER_MAX_PARTS &&
99 sscanf(buf + offset, "partition %64s base 0x%llx size 0x%llx%zn\n",
100 name, &parts[idx].offset, &parts[idx].size, &bytes) == 3;
I think this buffer comes from the partition table?
101 idx++, offset += bytes + 1) {
^^^^^^^^^
102 parts[idx].name = kstrdup(name, GFP_KERNEL);
103 if (!parts[idx].name) {
104 err = -ENOMEM;
drivers/char/ppdev.c:344 pp_set_timeout() warn: potential integer overflow from user 'tv_sec * 100'
343 static int pp_set_timeout(struct pardevice *pdev, long tv_sec, int tv_usec)
344 {
345 long to_jiffies;
346
347 if ((tv_sec < 0) || (tv_usec < 0))
348 return -EINVAL;
349
350 to_jiffies = usecs_to_jiffies(tv_usec);
^^^^^^^
351 to_jiffies += tv_sec * HZ;
^^^^^^^^^^^
Both of these can overflow
352 if (to_jiffies <= 0)
^^^^^^^^^^^^^^^
But they're checked here.
353 return -EINVAL;
354
355 pdev->timeout = to_jiffies;
356 return 0;
357 }
drivers/char/ipmi/ipmi_plat_data.c:70 ipmi_platform_add() warn: potential integer overflow from user 'r[0]->start + p->regsize'
69 r[0].start = p->addr;
70 r[0].end = r[0].start + p->regsize - 1;
^^^^^^^^^^^^^^^^^^^^^^^
I think this is root only so it's safe? Or it could be a false
positive.
71 r[0].name = "IPMI Address 1";
72 r[0].flags = flags;
drivers/i2c/i2c-dev.c:485 i2cdev_ioctl() warn: potential integer overflow from user (local copy) 'arg * 10'
478 case I2C_TIMEOUT:
479 if (arg > INT_MAX)
480 return -EINVAL;
481
482 /* For historical reasons, user-space sets the timeout
483 * value in units of 10 ms.
484 */
485 client->adapter->timeout = msecs_to_jiffies(arg * 10);
^^^^^^^^^
This can overflow and then the msecs_to_jiffies() conversion also has
an integer overflow in it.
486 break;
drivers/i2c/busses/i2c-bcm2835.c:93 clk_bcm2835_i2c_calc_divider() warn: potential integer overflow from user 'parent_rate + rate'
90 static int clk_bcm2835_i2c_calc_divider(unsigned long rate,
91 unsigned long parent_rate)
92 {
93 u32 divider = DIV_ROUND_UP(parent_rate, rate);
94
95 /*
96 * Per the datasheet, the register is always interpreted as an even
97 * number, by rounding down. In other words, the LSB is ignored. So,
98 * if the LSB is set, increment the divider to avoid any issue.
99 */
100 if (divider & 1)
101 divider++;
102 if ((divider < BCM2835_I2C_CDIV_MIN) ||
103 (divider > BCM2835_I2C_CDIV_MAX))
104 return -EINVAL;
Again, math first then check the result later. Integer overflow is
basically harmless.
105
106 return divider;
107 }
drivers/hwmon/nct6775-core.c:2265 store_temp_offset() warn: potential integer overflow from user '__x + (__d / 2)'
2251 static ssize_t
2252 store_temp_offset(struct device *dev, struct device_attribute *attr,
2253 const char *buf, size_t count)
2254 {
2255 struct nct6775_data *data = dev_get_drvdata(dev);
2256 struct sensor_device_attribute *sattr = to_sensor_dev_attr(attr);
2257 int nr = sattr->index;
2258 long val;
2259 int err;
2260
2261 err = kstrtol(buf, 10, &val);
2262 if (err < 0)
2263 return err;
2264
2265 val = clamp_val(DIV_ROUND_CLOSEST(val, 1000), -128, 127);
^^^^^^^^^^
Overflow and then clamp.
2266
2267 mutex_lock(&data->update_lock);
regards,
dan carpenter
Am Mittwoch, dem 08.05.2024 um 16:47 -0700 schrieb Linus Torvalds:
> On Wed, 8 May 2024 at 15:54, Kees Cook <[email protected]> wrote:
> >
..
>
> No, the only point where that actually failed was then when a
> (non-overflowing, non-wrapping) final value was assigned to a 16-bit
> field, ie the problem only ever happened at the final assignment:
>
> event->read_size = size;
>
> where no overflow had ever happened before that.
>
> So in *that* case, you actually have a much more interesting
> situation. Not wrap-around, not overflow, but "implicit cast drops
> significant bits".
>
> And yes, I do think implicit integer casts are dangerous. Often *more*
> dangerous than arithmetic overflow and wrapping. We've had absolutely
> tons of them. Some of our most traditional bugs have very much been
> about implicit casting losing bits and causing problems as a result.
In principle, GCC has -Wconversions which looks like that it is
meant to catch this. It seems not entirely stupid, e.g. it warns
about the first assignment and not the second (x86):
void f(int i)
{
unsigned short y = i;
unsigned short x = i & 0xFFF;
}
But I guess it still could be smarter. Or does it have to be a
sanitizer because compile-time will always have too many false
positives?
Martin
On Sun, 12 May 2024 at 01:03, Martin Uecker <[email protected]> wrote:
>
> But I guess it still could be smarter. Or does it have to be a
> sanitizer because compile-time will always have too many false
> positives?
Yes, there will be way too many false positives.
I'm pretty sure there will be a ton of "intentional positives" too,
where we do drop bits, but it's very much intentional. I think
somebody already mentioned the "store little endian" kind of things
where code like
unsigned chat *p;
u32 val;
p[0] = val;
p[1] = val >> 8;
p[2] = val >> 16;
p[3] = val >> 24;
kind of code is both traditional and correct, but obviously drops bits
very much intentionally on each of those assignments.
Now, obviously, in a perfect world the compiler would see the above as
"not really dropping bits", but that's not the world we live in.
So the whole "cast drops bits" is not easy to deal with.
In the case of the above kind of byte-wise behavior, I do think that
we could easily make the byte masking explicit, and so in *some* cases
it might actually be a good thing to just make these things more
explicit, and write it as
p[0] = val & 0xff;
p[1] = (val >> 8) & 0xff;
...
and the above doesn't make the source code worse: it arguably just
makes things more explicit both for humans and for the compiler, with
that explicit bitwise 'and' operation making it very clear that we're
just picking a particular set of bits out of the value.
But I do suspect the "implicit cast truncates value" is _so_ common
that it might be very very painful. Even with a run-time sanitizer
check.
And statically I think it's entirely a lost cause - it's literally
impossible to avoid in C. Why? Because there are no bitfield
variables, only fields in structures/unions, so if you pass a value
around as an argument, and then end up finally assigning it to a
bitfield, there was literally no way to pass that value around as the
"right type" originally. The final assignment *will* drop bits from a
static compiler standpoint.
Linus
Am Sonntag, dem 12.05.2024 um 09:09 -0700 schrieb Linus Torvalds:
> On Sun, 12 May 2024 at 01:03, Martin Uecker <[email protected]> wrote:
> >
> > But I guess it still could be smarter. Or does it have to be a
> > sanitizer because compile-time will always have too many false
> > positives?
>
> Yes, there will be way too many false positives.
>
> I'm pretty sure there will be a ton of "intentional positives" too,
> where we do drop bits, but it's very much intentional. I think
> somebody already mentioned the "store little endian" kind of things
> where code like
>
> unsigned chat *p;
> u32 val;
>
> p[0] = val;
> p[1] = val >> 8;
> p[2] = val >> 16;
> p[3] = val >> 24;
>
> kind of code is both traditional and correct, but obviously drops bits
> very much intentionally on each of those assignments.
>
> Now, obviously, in a perfect world the compiler would see the above as
> "not really dropping bits", but that's not the world we live in.
>
> So the whole "cast drops bits" is not easy to deal with.
>
> In the case of the above kind of byte-wise behavior, I do think that
> we could easily make the byte masking explicit, and so in *some* cases
> it might actually be a good thing to just make these things more
> explicit, and write it as
>
> p[0] = val & 0xff;
> p[1] = (val >> 8) & 0xff;
> ...
>
> and the above doesn't make the source code worse: it arguably just
> makes things more explicit both for humans and for the compiler, with
> that explicit bitwise 'and' operation making it very clear that we're
> just picking a particular set of bits out of the value.
Adding versions of the -Wconversions warning which triggers only
in very specific cases should not be too difficult, if something
like this is useful, i.e. restricting the warning to assignments.
>
> But I do suspect the "implicit cast truncates value" is _so_ common
> that it might be very very painful. Even with a run-time sanitizer
> check.
>
> And statically I think it's entirely a lost cause - it's literally
> impossible to avoid in C. Why? Because there are no bitfield
> variables, only fields in structures/unions, so if you pass a value
> around as an argument, and then end up finally assigning it to a
> bitfield, there was literally no way to pass that value around as the
> "right type" originally. The final assignment *will* drop bits from a
> static compiler standpoint.
>
If one wanted to, one could always pass bitfields inside a struct
typedef struct { unsigned int v:12; } b12;
int f(b12 x)
{
int i = x.v;
return i & (1 << 13);
}
the compiler is then smart enough to know how many bits are
relevant and track this to some degree inside the function.
https://godbolt.org/z/o8P3adnEK
But using this information for warnings would be more difficult
because the information is not computed in the front end. (but
here also other warnings generated by the backend, so not
impossible). And, of course, the additional wrapping and
unwrapping makes the code more ugly (*)
C23 then also has bit-precise integers.
Martin
(*) ...but compared to what some other languages require the
programmer to write, even this seems relatively benign.
On Sun, May 12, 2024 at 09:09:08AM -0700, Linus Torvalds wrote:
> unsigned char *p;
> u32 val;
>
> p[0] = val;
> p[1] = val >> 8;
> p[2] = val >> 16;
> p[3] = val >> 24;
>
> kind of code is both traditional and correct, but obviously drops bits
> very much intentionally on each of those assignments.
The good news here is that the integer implicit truncation sanitizers
are already split between "signed" and "unsigned". So the 2 cases of
exploitable flaws mentioned earlier:
u8 num_elems;
...
num_elems++; /* int promotion stored back to u8 */
and
int size;
u16 read_size;
...
read_size = size; /* large int stored to u16 */
are both confusions across signed/unsigned types, which the signed
sanitizer would catch. The signed sanitizer would entirely ignore
the quoted example at the top: everything is unsigned and no int
promotion is happening.
So, I think we can start with just the "signed integer implicit
truncation" sanitizer. The compiler will still need to deal with the
issues I outlined in [1], where I think we need some consideration
specifically on how to handle things like this (that have a
smaller-than-int size and trip the sanitizer due to int promotion):
u8 checksum(const u8 *buf)
{
u8 sum = 0;
for (int i = 0; i < 4; i++)
sum += buf[i]; /* int promotion */
return sum;
}
We want "sum" to wrap. We could avoid the "implicit" truncation by
explicitly truncating with something eye-bleedingly horrible like:
sum = (u8)(sum + buf[i]);
Adding a wrapper for the calculation could work but repeats "sum", and
needs to be explicitly typed, making it just as unfriendly:
sum = truncate(u8, sum + buf[i]);
Part of the work I'd done in preparation for all this was making the
verbosely named wrapping_assign_add() helper which handles all the
types by examining the arguments and avoids repeating the destination
argument. So this would become:
wrapping_assign_add(sum, buf[i]);
Still not as clean as "+=", but at least more readable than the
alternatives and leaves no question about wrapping intent.
-Kees
[1] https://lore.kernel.org/lkml/202405081949.0565810E46@keescook/
--
Kees Cook
On Sat, May 11, 2024 at 07:19:49PM +0300, Dan Carpenter wrote:
> I'm pretty sure we've tried using a sanitizer before and it had too many
> false positives. So your solution is to annotate all the false
> positives?
That was the plan, yes. Based on current feedback, we'll be taking an
even more incremental approach, though.
> There are two main issue which make integer overflows complicated from
> a static analysis perspective. 1) Places where it's intentional or
> we don't care. 2) Places where the integer overflow is harmless for
> one reason or another. Btw, integer overflows are a lot more common on
> 32 bit CPUs because obviously it's easier to overflow 4 billion than
> whatever number U64_MAX is.
Agreed on all counts. :)
> Here are is a sample of ten integer overflows that the user can trigger.
> Maybe pick a couple and walk us through how they would be annotated?
Sure, I will answer this from the perspective of the original proposal
(enabling signed-integer-overflow, unsigned-integer-overflow,
signed-integer-implicit-truncation, and
unsigned-integer-implicit-truncation).
>
> drivers/usb/dwc3/gadget.c:3064 dwc3_gadget_vbus_draw() warn: potential integer overflow from user '1000 * mA'
> 3052 static int dwc3_gadget_vbus_draw(struct usb_gadget *g, unsigned int mA)
> 3053 {
> 3054 struct dwc3 *dwc = gadget_to_dwc(g);
> 3055 union power_supply_propval val = {0};
> 3056 int ret;
> 3057
> 3058 if (dwc->usb2_phy)
> 3059 return usb_phy_set_power(dwc->usb2_phy, mA);
> 3060
> 3061 if (!dwc->usb_psy)
> 3062 return -EOPNOTSUPP;
> 3063
> 3064 val.intval = 1000 * mA;
> ^^^^^^^^^^
> mA comes from the user and we only know that it's a multiple of 2.
> So here we would annotate that val.intval can store integer overflows?
> Or we'd annotate mA?
Do we _want_ it to overflow? This seems like a case where we don't? I
would expect this to need:
int intval;
if (check_mul_overflow(1000, mA, &intval))
return -EINVAL;
val.intval = intval;
>
> 3065 ret = power_supply_set_property(dwc->usb_psy, POWER_SUPPLY_PROP_INPUT_CURRENT_LIMIT, &val);
> 3066
> 3067 return ret;
> 3068 }
>
>
> drivers/usb/class/usbtmc.c:852 usbtmc_generic_read() warn: potential integer overflow from user 'max_transfer_size + 1'
> 842 * wMaxPacketSize – 1) to avoid sending a zero-length
> 843 * packet
> 844 */
> 845 remaining = transfer_size;
> 846 if ((max_transfer_size % data->wMaxPacketSize) == 0)
> 847 max_transfer_size += (data->wMaxPacketSize - 1);
> 848 } else {
> 849 /* round down to bufsize to avoid truncated data left */
> 850 if (max_transfer_size > bufsize) {
> 851 max_transfer_size =
> 852 roundup(max_transfer_size + 1 - bufsize,
> ^^^^^^^^^^^^^^^^^^^^^
> This can overflow. We should make it a rule that all size variables
> have to be unsigned long. That would have made this safe on 64 bit
> systems.
>
> 853 bufsize);
> 854 }
> 855 remaining = max_transfer_size;
Again, do we _want_ this to overflow? It looks like not. I'm not sure
what this code is trying to do, though. The comment doesn't seem to
match the code. Why isn't this just roundup(max_transfer_size, bufsize) ?
> drivers/usb/misc/usbtest.c:1994 iso_alloc_urb() warn: potential integer overflow from user 'bytes + maxp'
> 1974 static struct urb *iso_alloc_urb(
> 1975 struct usb_device *udev,
> 1976 int pipe,
> 1977 struct usb_endpoint_descriptor *desc,
> 1978 long bytes,
> 1979 unsigned offset
> 1980 )
> 1981 {
> 1982 struct urb *urb;
> 1983 unsigned i, maxp, packets;
> 1984
> 1985 if (bytes < 0 || !desc)
> 1986 return NULL;
> 1987
> 1988 maxp = usb_endpoint_maxp(desc);
> 1989 if (udev->speed >= USB_SPEED_SUPER)
> 1990 maxp *= ss_isoc_get_packet_num(udev, pipe);
> 1991 else
> 1992 maxp *= usb_endpoint_maxp_mult(desc);
> 1993
> 1994 packets = DIV_ROUND_UP(bytes, maxp);
> ^^^^^
> The issue here is on a 32 bit system when bytes is INT_MAX.
All of these examples seem to be cases that should be mitigated. The
earlier check should be expanded:
if (bytes < 0 || bytes >= INT_MAX || !desc)
>
> 1995
> 1996 urb = usb_alloc_urb(packets, GFP_KERNEL);
> 1997 if (!urb)
> 1998 return urb;
>
>
> drivers/usb/storage/uas.c:324 uas_stat_cmplt() warn: potential integer overflow from user 'idx + 1'
> 322 idx = be16_to_cpup(&iu->tag) - 1;
>
> The "- 1" makes this UINT_MAX
>
> 323 if (idx >= MAX_CMNDS || !devinfo->cmnd[idx]) {
> 324 dev_err(&urb->dev->dev,
> 325 "stat urb: no pending cmd for uas-tag %d\n", idx + 1);
> ^^^^^^^
> Harmless integer overflow in printk.
>
> 326 goto out;
> 327 }
Again, this doesn't look like we want it overflowing. "idx" isn't
reported correctly. It can just use "idx": that's what's being examined
in the "if" statement.
> drivers/mtd/parsers/tplink_safeloader.c:101 mtd_parser_tplink_safeloader_parse() warn: potential integer overflow from user 'bytes + 1'
> 97 for (idx = 0, offset = TPLINK_SAFELOADER_DATA_OFFSET;
> 98 idx < TPLINK_SAFELOADER_MAX_PARTS &&
> 99 sscanf(buf + offset, "partition %64s base 0x%llx size 0x%llx%zn\n",
> 100 name, &parts[idx].offset, &parts[idx].size, &bytes) == 3;
>
> I think this buffer comes from the partition table?
>
> 101 idx++, offset += bytes + 1) {
> ^^^^^^^^^
>
> 102 parts[idx].name = kstrdup(name, GFP_KERNEL);
> 103 if (!parts[idx].name) {
> 104 err = -ENOMEM;
Again, we don't want it wrapping. The whole loop needs to be expanded to
be readable, and bounds checking needs to be performed.
>
>
> drivers/char/ppdev.c:344 pp_set_timeout() warn: potential integer overflow from user 'tv_sec * 100'
> 343 static int pp_set_timeout(struct pardevice *pdev, long tv_sec, int tv_usec)
> 344 {
> 345 long to_jiffies;
> 346
> 347 if ((tv_sec < 0) || (tv_usec < 0))
> 348 return -EINVAL;
> 349
> 350 to_jiffies = usecs_to_jiffies(tv_usec);
> ^^^^^^^
>
> 351 to_jiffies += tv_sec * HZ;
> ^^^^^^^^^^^
> Both of these can overflow
>
> 352 if (to_jiffies <= 0)
> ^^^^^^^^^^^^^^^
> But they're checked here.
>
> 353 return -EINVAL;
> 354
> 355 pdev->timeout = to_jiffies;
> 356 return 0;
> 357 }
This doesn't look like a wrapping-desired case either, but just for fun,
let's assume we want it. (And why are any of these signed?) Annotation
is added to the variables:
static int pp_set_timeout(struct pardevice *pdev, long __wraps tv_sec, int __wraps tv_usec)
{
long __wraps to_jiffies;
>
> drivers/char/ipmi/ipmi_plat_data.c:70 ipmi_platform_add() warn: potential integer overflow from user 'r[0]->start + p->regsize'
> 69 r[0].start = p->addr;
> 70 r[0].end = r[0].start + p->regsize - 1;
> ^^^^^^^^^^^^^^^^^^^^^^^
> I think this is root only so it's safe? Or it could be a false
> positive.
>
> 71 r[0].name = "IPMI Address 1";
> 72 r[0].flags = flags;
We don't want this to wrap, yes? I don't know what is expected when regsize == 0,
but ignoring that, I'd expect:
if (check_add_overflow(r[0].start, p->regsize - 1, &r[0].end))
error...
>
>
> drivers/i2c/i2c-dev.c:485 i2cdev_ioctl() warn: potential integer overflow from user (local copy) 'arg * 10'
> 478 case I2C_TIMEOUT:
> 479 if (arg > INT_MAX)
> 480 return -EINVAL;
> 481
> 482 /* For historical reasons, user-space sets the timeout
> 483 * value in units of 10 ms.
> 484 */
> 485 client->adapter->timeout = msecs_to_jiffies(arg * 10);
> ^^^^^^^^^
> This can overflow and then the msecs_to_jiffies() conversion also has
> an integer overflow in it.
If we want these wrapping:
unsigned long __wraps timeout = arg * 10;
client->adapter->timeout = msecs_to_jiffies(timeout);
and:
static inline unsigned long _msecs_to_jiffies(const unsigned int __wraps m)
>
> 486 break;
>
>
> drivers/i2c/busses/i2c-bcm2835.c:93 clk_bcm2835_i2c_calc_divider() warn: potential integer overflow from user 'parent_rate + rate'
> 90 static int clk_bcm2835_i2c_calc_divider(unsigned long rate,
> 91 unsigned long parent_rate)
> 92 {
> 93 u32 divider = DIV_ROUND_UP(parent_rate, rate);
> 94
> 95 /*
> 96 * Per the datasheet, the register is always interpreted as an even
> 97 * number, by rounding down. In other words, the LSB is ignored. So,
> 98 * if the LSB is set, increment the divider to avoid any issue.
> 99 */
> 100 if (divider & 1)
> 101 divider++;
> 102 if ((divider < BCM2835_I2C_CDIV_MIN) ||
> 103 (divider > BCM2835_I2C_CDIV_MAX))
> 104 return -EINVAL;
>
> Again, math first then check the result later. Integer overflow is
> basically harmless.
Either fix the check or:
u32 __wraps divider = ...
>
> 105
> 106 return divider;
> 107 }
>
>
> drivers/hwmon/nct6775-core.c:2265 store_temp_offset() warn: potential integer overflow from user '__x + (__d / 2)'
> 2251 static ssize_t
> 2252 store_temp_offset(struct device *dev, struct device_attribute *attr,
> 2253 const char *buf, size_t count)
> 2254 {
> 2255 struct nct6775_data *data = dev_get_drvdata(dev);
> 2256 struct sensor_device_attribute *sattr = to_sensor_dev_attr(attr);
> 2257 int nr = sattr->index;
> 2258 long val;
> 2259 int err;
> 2260
> 2261 err = kstrtol(buf, 10, &val);
> 2262 if (err < 0)
> 2263 return err;
> 2264
> 2265 val = clamp_val(DIV_ROUND_CLOSEST(val, 1000), -128, 127);
> ^^^^^^^^^^
> Overflow and then clamp.
Looks like DIV_ROUND_CLOSEST() needs to be made sane and use more modern
helpers (it appears to be doing open-coded is_signed(), wants
check_*_overflow(), etc).
>
> 2266
> 2267 mutex_lock(&data->update_lock);
>
> regards,
> dan carpenter
-Kees
--
Kees Cook
Snipped all the bits where you are clearly correct.
On Mon, May 13, 2024 at 12:43:37PM -0700, Kees Cook wrote:
> > drivers/usb/class/usbtmc.c:852 usbtmc_generic_read() warn: potential integer overflow from user 'max_transfer_size + 1'
> > 842 * wMaxPacketSize – 1) to avoid sending a zero-length
> > 843 * packet
> > 844 */
> > 845 remaining = transfer_size;
> > 846 if ((max_transfer_size % data->wMaxPacketSize) == 0)
> > 847 max_transfer_size += (data->wMaxPacketSize - 1);
> > 848 } else {
> > 849 /* round down to bufsize to avoid truncated data left */
> > 850 if (max_transfer_size > bufsize) {
> > 851 max_transfer_size =
> > 852 roundup(max_transfer_size + 1 - bufsize,
> > ^^^^^^^^^^^^^^^^^^^^^
> > This can overflow. We should make it a rule that all size variables
> > have to be unsigned long. That would have made this safe on 64 bit
> > systems.
> >
> > 853 bufsize);
> > 854 }
> > 855 remaining = max_transfer_size;
>
> Again, do we _want_ this to overflow? It looks like not. I'm not sure
> what this code is trying to do, though. The comment doesn't seem to
> match the code. Why isn't this just roundup(max_transfer_size, bufsize) ?
>
roundup() has an integer overflow in it.
> > drivers/usb/misc/usbtest.c:1994 iso_alloc_urb() warn: potential integer overflow from user 'bytes + maxp'
> > 1974 static struct urb *iso_alloc_urb(
> > 1975 struct usb_device *udev,
> > 1976 int pipe,
> > 1977 struct usb_endpoint_descriptor *desc,
> > 1978 long bytes,
> > 1979 unsigned offset
> > 1980 )
> > 1981 {
> > 1982 struct urb *urb;
> > 1983 unsigned i, maxp, packets;
> > 1984
> > 1985 if (bytes < 0 || !desc)
> > 1986 return NULL;
> > 1987
> > 1988 maxp = usb_endpoint_maxp(desc);
> > 1989 if (udev->speed >= USB_SPEED_SUPER)
> > 1990 maxp *= ss_isoc_get_packet_num(udev, pipe);
> > 1991 else
> > 1992 maxp *= usb_endpoint_maxp_mult(desc);
> > 1993
> > 1994 packets = DIV_ROUND_UP(bytes, maxp);
> > ^^^^^
> > The issue here is on a 32 bit system when bytes is INT_MAX.
>
> All of these examples seem to be cases that should be mitigated. The
> earlier check should be expanded:
>
> if (bytes < 0 || bytes >= INT_MAX || !desc)
This doesn't work on 32bit systems.
>
> >
> > 1995
> > 1996 urb = usb_alloc_urb(packets, GFP_KERNEL);
> > 1997 if (!urb)
> > 1998 return urb;
> >
> >
> > drivers/char/ppdev.c:344 pp_set_timeout() warn: potential integer overflow from user 'tv_sec * 100'
> > 343 static int pp_set_timeout(struct pardevice *pdev, long tv_sec, int tv_usec)
> > 344 {
> > 345 long to_jiffies;
> > 346
> > 347 if ((tv_sec < 0) || (tv_usec < 0))
> > 348 return -EINVAL;
> > 349
> > 350 to_jiffies = usecs_to_jiffies(tv_usec);
> > ^^^^^^^
> >
> > 351 to_jiffies += tv_sec * HZ;
> > ^^^^^^^^^^^
> > Both of these can overflow
> >
> > 352 if (to_jiffies <= 0)
> > ^^^^^^^^^^^^^^^
> > But they're checked here.
> >
> > 353 return -EINVAL;
> > 354
> > 355 pdev->timeout = to_jiffies;
> > 356 return 0;
> > 357 }
>
> This doesn't look like a wrapping-desired case either, but just for fun,
> let's assume we want it.
The original programmer assumed it would wrap so it was intentional/desired.
> (And why are any of these signed?) Annotation
> is added to the variables:
>
> static int pp_set_timeout(struct pardevice *pdev, long __wraps tv_sec, int __wraps tv_usec)
> {
> long __wraps to_jiffies;
Sure.
> > drivers/i2c/i2c-dev.c:485 i2cdev_ioctl() warn: potential integer overflow from user (local copy) 'arg * 10'
> > 478 case I2C_TIMEOUT:
> > 479 if (arg > INT_MAX)
> > 480 return -EINVAL;
> > 481
> > 482 /* For historical reasons, user-space sets the timeout
> > 483 * value in units of 10 ms.
> > 484 */
> > 485 client->adapter->timeout = msecs_to_jiffies(arg * 10);
> > ^^^^^^^^^
> > This can overflow and then the msecs_to_jiffies() conversion also has
> > an integer overflow in it.
>
> If we want these wrapping:
>
> unsigned long __wraps timeout = arg * 10;
> client->adapter->timeout = msecs_to_jiffies(timeout);
>
> and:
>
> static inline unsigned long _msecs_to_jiffies(const unsigned int __wraps m)
>
>
Here we don't care about wrapping, but I wouldn't go so far as to say it
was intentional... I guess this silences the warning.
> > drivers/hwmon/nct6775-core.c:2265 store_temp_offset() warn: potential integer overflow from user '__x + (__d / 2)'
> > 2251 static ssize_t
> > 2252 store_temp_offset(struct device *dev, struct device_attribute *attr,
> > 2253 const char *buf, size_t count)
> > 2254 {
> > 2255 struct nct6775_data *data = dev_get_drvdata(dev);
> > 2256 struct sensor_device_attribute *sattr = to_sensor_dev_attr(attr);
> > 2257 int nr = sattr->index;
> > 2258 long val;
> > 2259 int err;
> > 2260
> > 2261 err = kstrtol(buf, 10, &val);
> > 2262 if (err < 0)
> > 2263 return err;
> > 2264
> > 2265 val = clamp_val(DIV_ROUND_CLOSEST(val, 1000), -128, 127);
> > ^^^^^^^^^^
> > Overflow and then clamp.
>
> Looks like DIV_ROUND_CLOSEST() needs to be made sane and use more modern
> helpers (it appears to be doing open-coded is_signed(), wants
> check_*_overflow(), etc).
>
Sounds good.
regards,
dan carpenter
On Wed, May 08, 2024 at 04:47:25PM -0700, Linus Torvalds wrote:
> For example, the most common case of overflow we've ever had has very
> much been array indexing. Now, sometimes that has actually been actual
> undefined behavior, because it's been overflow in signed variables,
> and those are "easy" to find in the sense that you just say "no, can't
> do that". UBSAN finds them, and that's good.
We build with -fno-strict-overflow, which implies -fwrapv, which removes
the UB from signed overflow by mandating 2s complement.
With the exception of an UBSAN bug prior to GCC-8, UBSAN will not, and
should not, warn about signed overflow when using either of these flags.
On Wed, May 08, 2024 at 04:47:25PM -0700, Linus Torvalds wrote:
> Now, another thing to do might be to treat assignments (and again,
> implicit casts) to 'size_t' specially. In most compilers (certainly in
> gcc), "size_t" is a special type.
>
> Now, in the kernel, we don't actually use __builtin_size_t (the kernel
> started out with a very standalone type system, and I think it
> actually predated gcc's __builtin_size_t or maybe I just wasn't aware
> of it). But we certainly _could_ - or we could at least use some
> special marked type for our own 'size_t'.
So I've been arguing that since unsigned (and signed too when -fwrapv)
have well defined wrapping semantics and people rely on them, you cannot
go around and assume that wrapping is bad.
You're arguing much the same.
I've proposed that Kees instead adds a type qualifier to explicitly mark
no-overflow / no-wrap types. That way __buildin_size_t is no longer
magical, and it along with all the other __builtin_*_overflow() muck can
go away. You'd end up with things like:
typedef nowrap unsigned int __kernel_size_t;
or perhaps:
nowrap int idx = j * sizeof(foo);
etc. To indeed annotate these baby steps, without making code needlessly
ugly with all these __builtin_*_overflow() wrappers.
Hi Peter,
On Wed, May 15, 2024 at 12:36 AM Peter Zijlstra <[email protected]> wrote:
>
> On Wed, May 08, 2024 at 04:47:25PM -0700, Linus Torvalds wrote:
> > For example, the most common case of overflow we've ever had has very
> > much been array indexing. Now, sometimes that has actually been actual
> > undefined behavior, because it's been overflow in signed variables,
> > and those are "easy" to find in the sense that you just say "no, can't
> > do that". UBSAN finds them, and that's good.
>
> We build with -fno-strict-overflow, which implies -fwrapv, which removes
> the UB from signed overflow by mandating 2s complement.
FWIW,
Clang-19 allows -fwrapv and -fsanitize=signed-integer-overflow to work
together [1]
And the sanitizer was re-introduced with Commit 557f8c582a9ba8ab
("ubsan: Reintroduce signed overflow sanitizer").
>
> With the exception of an UBSAN bug prior to GCC-8, UBSAN will not, and
> should not, warn about signed overflow when using either of these flags.
[1]: https://clang.llvm.org/docs/ReleaseNotes.html#sanitizers
Thanks
Justin
On Wed, May 15, 2024 at 10:12:20AM -0700, Justin Stitt wrote:
> Hi Peter,
>
> On Wed, May 15, 2024 at 12:36 AM Peter Zijlstra <[email protected]> wrote:
> >
> > On Wed, May 08, 2024 at 04:47:25PM -0700, Linus Torvalds wrote:
> > > For example, the most common case of overflow we've ever had has very
> > > much been array indexing. Now, sometimes that has actually been actual
> > > undefined behavior, because it's been overflow in signed variables,
> > > and those are "easy" to find in the sense that you just say "no, can't
> > > do that". UBSAN finds them, and that's good.
> >
> > We build with -fno-strict-overflow, which implies -fwrapv, which removes
> > the UB from signed overflow by mandating 2s complement.
>
> FWIW,
>
> Clang-19 allows -fwrapv and -fsanitize=signed-integer-overflow to work
> together [1]
>
> And the sanitizer was re-introduced with Commit 557f8c582a9ba8ab
> ("ubsan: Reintroduce signed overflow sanitizer").
Urgh, that's the exact kind of drugs we don't need. I detest that
commit. Both unsigned and signed have well defined semantics.
And since (with -fwrapv) there is no UB, UBSAN is not the right place.
> > With the exception of an UBSAN bug prior to GCC-8, UBSAN will not, and
> > should not, warn about signed overflow when using either of these flags.
>
> [1]: https://clang.llvm.org/docs/ReleaseNotes.html#sanitizers
That link doesn't seem to work for me...
On May 15, 2024 12:36:36 AM PDT, Peter Zijlstra <[email protected]> wrote:
>On Wed, May 08, 2024 at 04:47:25PM -0700, Linus Torvalds wrote:
>> For example, the most common case of overflow we've ever had has very
>> much been array indexing. Now, sometimes that has actually been actual
>> undefined behavior, because it's been overflow in signed variables,
>> and those are "easy" to find in the sense that you just say "no, can't
>> do that". UBSAN finds them, and that's good.
>
>We build with -fno-strict-overflow, which implies -fwrapv, which removes
>the UB from signed overflow by mandating 2s complement.
I am a broken record. :) This is _not_ about undefined behavior.
This is about finding a way to make the intent of C authors unambiguous. That overflow wraps is well defined. It is not always _desired_. C has no way to distinguish between the two cases.
-Kees
--
Kees Cook
On Thu, May 16, 2024 at 06:30:32AM -0700, Kees Cook wrote:
>
>
> On May 15, 2024 12:36:36 AM PDT, Peter Zijlstra <[email protected]> wrote:
> >On Wed, May 08, 2024 at 04:47:25PM -0700, Linus Torvalds wrote:
> >> For example, the most common case of overflow we've ever had has very
> >> much been array indexing. Now, sometimes that has actually been actual
> >> undefined behavior, because it's been overflow in signed variables,
> >> and those are "easy" to find in the sense that you just say "no, can't
> >> do that". UBSAN finds them, and that's good.
> >
> >We build with -fno-strict-overflow, which implies -fwrapv, which removes
> >the UB from signed overflow by mandating 2s complement.
>
> I am a broken record. :) This is _not_ about undefined behavior.
And yet you introduced CONFIG_UBSAN_SIGNED_WRAP... *UB*san, get it?
> This is about finding a way to make the intent of C authors
> unambiguous. That overflow wraps is well defined. It is not always
> _desired_. C has no way to distinguish between the two cases.
The current semantics are (and have been for years, decades at this
point) that everything wraps nicely and code has been assuming this. You
cannot just change this.
So what you do is do a proper language extension and add a type
qualifier that makes overflows trap and annotate all them cases where
people do not expect overflows (so that we can put the
__builtin_*_overflow() things where the sun don't shine).
And pretty please, also do a qualifier modification extension, because
that's totally painful already.
Hi,
On Thu, May 16, 2024 at 7:09 AM Peter Zijlstra <[email protected]> wrote:
>
> On Thu, May 16, 2024 at 06:30:32AM -0700, Kees Cook wrote:
> >
> > I am a broken record. :) This is _not_ about undefined behavior.
>
> And yet you introduced CONFIG_UBSAN_SIGNED_WRAP... *UB*san, get it?
We should think of UBSAN as an "Unexpected Behavior" Sanitizer. Clang
has evolved to provide instrumentation for things that are not
*technically* undefined behavior.
Go to [1] and grep for some phrases like "not undefined behavior" and
see that we have quite a few sanitizers that aren't *technically*
handling undefined behavior.
>
> > This is about finding a way to make the intent of C authors
> > unambiguous. That overflow wraps is well defined. It is not always
> > _desired_. C has no way to distinguish between the two cases.
>
> The current semantics are (and have been for years, decades at this
> point) that everything wraps nicely and code has been assuming this. You
> cannot just change this.
Why not :>)
Lots and lots of exploits are caused by unintentional arithmetic overflow [2].
>
> So what you do is do a proper language extension and add a type
> qualifier that makes overflows trap and annotate all them cases where
> people do not expect overflows (so that we can put the
> __builtin_*_overflow() things where the sun don't shine).
It is incredibly important that the exact opposite approach is taken;
we need to be annotating (or adding type qualifiers to) the _expected_
overflow cases. The omniscience required to go and properly annotate
all the spots that will cause problems would suggest that we should
just fix the bug outright. If only it was that easy.
I don't think we're capable of identifying every single problematic
overflow/wraparound case in the kernel, this is pretty obvious
considering we've had decades to do so. Instead, it seems much more
feasible that we annotate (very, very minimally so as not to disrupt
code readability and style) the spots where we _know_ overflow should
happen.
[1]: https://clang.llvm.org/docs/UndefinedBehaviorSanitizer.html#ubsan-checks
[2]: https://cwe.mitre.org/data/definitions/190.html
Thanks
Justin
On Thu, May 16, 2024 at 12:48:47PM -0700, Justin Stitt wrote:
> I don't think we're capable of identifying every single problematic
> overflow/wraparound case in the kernel, this is pretty obvious
> considering we've had decades to do so. Instead, it seems much more
> feasible that we annotate (very, very minimally so as not to disrupt
> code readability and style) the spots where we _know_ overflow should
> happen.
For the baby steps Linus wants, we can walk this path:
- Finish the *signed* integer overflow refactoring/annotation.
This is nearly done already, and every case we've found is either
a legitimate bug (thankfully rare), or happens in code that is
either accidentally correct (thanks to no UB), or the correctness is
very unclear. Refactoring these cases improves readability for
everyone and doesn't change the behavior.
- Begin *signed* integer implicit truncation refactoring/annotation.
As Linus suggested, dealing with this will catch a bunch of the flaws
we've seen recently. Handling the false positives here will need some
investigation and some compiler support, and that'll happen in
parallel.
- Tackle *unsigned* integer overflow on a per-type basis: we can start
with the place Linus called out: size_t. This will let us focus on the
first of the unsigned types that is not commonly wrapping, and is a
regular place that unexpected overflow gets the kernel into big
trouble.
What we learn from these three steps should inform us what further steps
down this path can look like.
-Kees
--
Kees Cook
On Thu, May 16, 2024 at 12:48:47PM -0700, Justin Stitt wrote:
>
> It is incredibly important that the exact opposite approach is taken;
> we need to be annotating (or adding type qualifiers to) the _expected_
> overflow cases. The omniscience required to go and properly annotate
> all the spots that will cause problems would suggest that we should
> just fix the bug outright. If only it was that easy.
It certainly isn't easy, yes. But the problem is when you dump a huge
amount of work and pain onto kernel developers, when they haven't
signed up for it, when they don't necessarily have the time to do all
of the work themselves, and when their corporate overlords won't given
them the headcount to handle unfunded mandates which folks who are
looking for a bright new wonderful future --- don't be surprised if
kernel developers push back hard.
One of the big problems that we've seen with many of these security
initiatives is that the teams create these unfunded mandates get their
performance reviews based on how many "bug reports" that they file,
regardless of whether they are real problems or not. This has been a
problem with syzkaller, and with clusterfuzz. Let's not make this
problem worse with new and fancy sanitizers, please.
Unfortunately, I don't get funding from my employer to clear these
kinds of reports, so when I do the work, it happens on the weekends or
late at night, on my own time, which is probably why I am so grumpy
about this. Whether you call this "sharpening our focus", or "year of
efficiency", or pick your corporate buzzwords, it really doesn't
matter. The important thing is that the figure of merit must NOT be
"how many security bugs that are found", but how much bullsh*t noise
do these security features create, and how do you decrease overhead by
upstream developers to deal with the fuzzing/ubsan/security tools
find.
Cheers,
- Ted
Am 5/8/2024 um 10:07 PM schrieb Linus Torvalds:
> And no, the answer is ABSOLUTELY NOT to add cognitive load on kernel
> developers by adding yet more random helper types and/or functions.
Just to show an option without "more types and helper functions", one
could also instead add a coverage requirement:
Every arithmetic operation should either:
- have a test case where the wrap around happens, or
- have a static analyser say that overflow can not happen, or
- have a static analyser say that overflow is fine (e.g., your a+b < a case)
Then the answer to safe wrap situations isn't to make the kernel code
less readable, but to have a component-level test that shows that the
behavior on overflow (in at least one case :)) ) is what the developer
expected.
For static analysis to prove that overflow can not happen, one sometimes
would need to add BUG_ON() assertions to let the analyser know the
assumptions on surrounding code, which has its own benefits.
static inline u32 __item_offset(u32 val)
{
BUG_ON(val > INT_MAX / ITEM_SIZE_PER_UNIT);
return val * ITEM_SIZE_PER_UNIT;
}
Obviously, the effort involved is still high. Maybe if someone as a pet
project proves first that something in this direction is actually worth
the effort (by uncovering a heap of bugs), one could offer this kind of
check as an opt-in.
Best wishes,
jonas
On Thu, May 16, 2024 at 02:51:34PM -0600, Theodore Ts'o wrote:
> On Thu, May 16, 2024 at 12:48:47PM -0700, Justin Stitt wrote:
> >
> > It is incredibly important that the exact opposite approach is taken;
> > we need to be annotating (or adding type qualifiers to) the _expected_
> > overflow cases. The omniscience required to go and properly annotate
> > all the spots that will cause problems would suggest that we should
> > just fix the bug outright. If only it was that easy.
>
> It certainly isn't easy, yes. But the problem is when you dump a huge
> amount of work and pain onto kernel developers, when they haven't
> signed up for it, when they don't necessarily have the time to do all
> of the work themselves, and when their corporate overlords won't given
> them the headcount to handle unfunded mandates which folks who are
> looking for a bright new wonderful future --- don't be surprised if
> kernel developers push back hard.
I never claimed this to be some kind of "everyone has to stop and make
these changes" event. I even talked about how it would be gradual and
not break existing code (all "WARN and continue anyway"). This is what
we've been doing with the array bounds work. Lots of people are helping
with that, but a lot of those patches have been from Gustavo and me; we
tried to keep the burden away from other developers as much as we could.
> One of the big problems that we've seen with many of these security
> initiatives is that the teams create these unfunded mandates get their
> performance reviews based on how many "bug reports" that they file,
> regardless of whether they are real problems or not. This has been a
> problem with syzkaller, and with clusterfuzz. Let's not make this
> problem worse with new and fancy sanitizers, please.
Are you talking about *my* security initiatives? I've been doing this
kind work in the kernel for 10 years, and at no time has "bug report
count" been a metric. In fact, the whole goal is making it _impossible_
to have a bug. (e.g. VLA removal, switch fallthrough, etc). My drive has
been to kill entire classes of bugs.
The use of sanitizers isn't to just bolster fuzzers (though they're
helpful for finding false positives). It's to use the sanitizers _in
production_, to stop flaws from being exploitable. Android has enabled
the array bounds sanitizer in trap mode for at least 2 years now. We
want the kernel to be self-protective; pro-actively catching flaws.
> Unfortunately, I don't get funding from my employer to clear these
> kinds of reports, so when I do the work, it happens on the weekends or
> late at night, on my own time, which is probably why I am so grumpy
As for the work itself, like I mentioned before, most of these get fixed
my Gustavo, me, and now Justin too. And many other folks step up to help
out, which is great. Some get complex and other maintainers get involved
too, but it's slow and steady. We're trying to reduce the frequency of
the "fires" people have to scramble to deal with.
The "not getting paid by Google to [fix syzkaller bugs]" part, I'm
surprised by. A big part of my Google job role is the upstream work I do
not only on security hardening but also on seccomp, pstore, execve/binfmt,
strings, etc. I'll reach out offline to find out more details.
> about this. Whether you call this "sharpening our focus", or "year of
> efficiency", or pick your corporate buzzwords, it really doesn't
> matter. The important thing is that the figure of merit must NOT be
> "how many security bugs that are found", but how much bullsh*t noise
> do these security features create, and how do you decrease overhead by
> upstream developers to deal with the fuzzing/ubsan/security tools
> find.
I guess I *do* worry about bug counts, but only in that I want them to
be _zero_. I know other folks aren't as adamant about eliminating bug
classes, but it's really not hyperbole that bugs in Linux kill people.
If you think I'm engaging in corporate buzzword shenanigans, then I have
a lot more work to do on explaining the rationale behind the security
hardening efforts.
All this said, yes, I hear what you (and Linus and others) have been
saying about minimizing the burden on other developers. I have tried my
best to keep it limited, but some things are more front-and-center (like
unexpected integer overflows), so that's why I wanted to get feedback on
how to roll it out -- I didn't see a way to make these changes in a way
that would be as unintrusive(?) as our prior efforts.
It has felt like the biggest pain point has been helping developers
shift their perspective about C: it has been more than a fancy assembler
for several decades, and we can lean on those features (and create new
ones) that shift the burden of correctness to the compiler from the
human. This does mean we need to change some styles to be more
"observable" (and unambiguous) for the compiler, though.
I think a great example recently was Peter's work creating "cleanup.h".
This feature totally changes how people have to read a function (increase
in burden), leans heavily on compiler behaviors, and shifts the burden
of correctness away from the human. It's great! But it's also _very
different_ from traditional/old-school C.
-Kees
--
Kees Cook
On Thu, May 16, 2024 at 12:49 PM Justin Stitt <[email protected]> wrote:
>
> Hi,
>
> On Thu, May 16, 2024 at 7:09 AM Peter Zijlstra <[email protected]> wrote:
> >
> > On Thu, May 16, 2024 at 06:30:32AM -0700, Kees Cook wrote:
> > >
> > > I am a broken record. :) This is _not_ about undefined behavior.
> >
> > And yet you introduced CONFIG_UBSAN_SIGNED_WRAP... *UB*san, get it?
>
> We should think of UBSAN as an "Unexpected Behavior" Sanitizer. Clang
> has evolved to provide instrumentation for things that are not
> *technically* undefined behavior.
>
> Go to [1] and grep for some phrases like "not undefined behavior" and
> see that we have quite a few sanitizers that aren't *technically*
> handling undefined behavior.
>
> >
> > > This is about finding a way to make the intent of C authors
> > > unambiguous. That overflow wraps is well defined. It is not always
> > > _desired_. C has no way to distinguish between the two cases.
> >
> > The current semantics are (and have been for years, decades at this
> > point) that everything wraps nicely and code has been assuming this. You
> > cannot just change this.
>
> Why not :>)
>
> Lots and lots of exploits are caused by unintentional arithmetic overflow [2].
>
> >
> > So what you do is do a proper language extension and add a type
> > qualifier that makes overflows trap and annotate all them cases where
> > people do not expect overflows (so that we can put the
> > __builtin_*_overflow() things where the sun don't shine).
>
> It is incredibly important that the exact opposite approach is taken;
> we need to be annotating (or adding type qualifiers to) the _expected_
> overflow cases. The omniscience required to go and properly annotate
> all the spots that will cause problems would suggest that we should
> just fix the bug outright. If only it was that easy.
>
> I don't think we're capable of identifying every single problematic
> overflow/wraparound case in the kernel, this is pretty obvious
> considering we've had decades to do so. Instead, it seems much more
> feasible that we annotate (very, very minimally so as not to disrupt
> code readability and style) the spots where we _know_ overflow should
> happen.
>
> [1]: https://clang.llvm.org/docs/UndefinedBehaviorSanitizer.html#ubsan-checks
> [2]: https://cwe.mitre.org/data/definitions/190.html
>
> Thanks
> Justin
FWIW I have made -fsanitize=undefined -fwrapv not imply
-fsanitize=signed-integer-overflow in
https://github.com/llvm/llvm-project/pull/85501 .
The change is not included in the LLVM 18.1.* releases.
This might encourage projects using both -fwrapv and
-fsanitize=undefined to re-evaluate whether -fwrapv aligns with their
needs.
The description of #85501 contains more information about my
understanding of kernel security folks' mind:
> Linux kernel uses -fwrapv to change signed integer overflows from undefined behaviors to defined behaviors. However, the security folks still want -fsanitize=signed-integer-overflow diagnostics. Their intention can be expressed with -fwrapv -fsanitize=signed-integer-overflow (#80089). This mode by default reports recoverable errors while still making signed integer overflows defined (most UBSan checks are recoverable by default: you get errors in stderr, but the program is not halted).
--
宋方睿
On Fri, May 17, 2024 at 02:15:01PM -0700, Kees Cook wrote:
> On Thu, May 16, 2024 at 02:51:34PM -0600, Theodore Ts'o wrote:
> > On Thu, May 16, 2024 at 12:48:47PM -0700, Justin Stitt wrote:
> > >
> > > It is incredibly important that the exact opposite approach is taken;
> > > we need to be annotating (or adding type qualifiers to) the _expected_
> > > overflow cases. The omniscience required to go and properly annotate
> > > all the spots that will cause problems would suggest that we should
> > > just fix the bug outright. If only it was that easy.
> >
> > It certainly isn't easy, yes. But the problem is when you dump a huge
> > amount of work and pain onto kernel developers, when they haven't
> > signed up for it, when they don't necessarily have the time to do all
> > of the work themselves, and when their corporate overlords won't given
> > them the headcount to handle unfunded mandates which folks who are
> > looking for a bright new wonderful future --- don't be surprised if
> > kernel developers push back hard.
>
> I never claimed this to be some kind of "everyone has to stop and make
> these changes" event. I even talked about how it would be gradual and
> not break existing code (all "WARN and continue anyway"). This is what
> we've been doing with the array bounds work. Lots of people are helping
> with that, but a lot of those patches have been from Gustavo and me; we
> tried to keep the burden away from other developers as much as we could.
Kees, sorry, I wasn't intending to be criticism of your work; I know
you've been careful. What I was reacting was Justin's comment that
it's important to annotate every single expected overflow case. This
sounded like the very common attitude of "type II errors must be
avoided at all costs", even in that means a huge number of "type I
errors". And false positive errors invariably end up requiring work
on the part of over-worked maintainers.
From my perspective, it's OK if we don't find all possible security
bugs if we can keep the false negative rate down to near-zero.
Because if it's too high, I will just start ignoring all of the
"security reports", just out of self-defense. This is now the case
with clusterfuzz reports example. The attemp[t to shame/pressure me
with "fix this RIGHT NOW or we will make the report public in 30 days"
no longer works on me, because the vast majority of the reports
against e2fsprogs are bullshit. And there are many syzkaller reports
which are also bullshit, and when they are reported against our data
center kernels, they get down-prioritized to P3 and ignored, because
they can't happen in real life. But they still get reported to
upstream (me).
This is why I am worried when there are proposals to add new
sanitizers; even if they are used responsibly by you, I can easily see
them resulting in more clusterfuzz reports (for example) that I will
have to ignore as bullshit. So please considerr this a plea to
**really** seriously reduce the false positive rate of sanitizers
whenever possible.
Cheers,
- Ted
On Wed, May 08, 2024 at 11:11:35PM -0700, Kees Cook wrote:
> Or even just simple math between u8s:
>
> while (xas->xa_offset == 255) {
> xas->xa_offset = xas->xa_node->offset - 1;
>
> Is it expecting to wrap (truncate)? How is it distinguished from
> the "num_elems++" case?
Hi ;-)
This looks to me like it's walking up the tree, looking to go to the
'prev' element. So yes, the wrapping from 0 to 255 is intentional,
because once we find an offset that's not 0, we've set offset to the
right one. Just to give more context, here's the few lines around it:
if (xas->xa_offset != get_offset(xas->xa_index, xas->xa_node))
xas->xa_offset--;
while (xas->xa_offset == 255) {
xas->xa_offset = xas->xa_node->offset - 1;
xas->xa_node = xa_parent(xas->xa, xas->xa_node);
if (!xas->xa_node)
return set_bounds(xas);
}
So it's kind of nasty. I don't want to write it as:
while (xas->xa_offset == 0) {
xas->xa_offset = xas->xa_node->offset;
xas->xa_node = xa_parent(xas->xa, xas->xa_node);
}
xas->xa_offset--;
because there's that conditional subtraction before the loop starts.
The xarray test-suite is pretty good if anyone thinks they have a clearer
way to write this loop ...
From: Kees Cook
> Sent: 16 May 2024 14:31
>
> On May 15, 2024 12:36:36 AM PDT, Peter Zijlstra <[email protected]> wrote:
> >On Wed, May 08, 2024 at 04:47:25PM -0700, Linus Torvalds wrote:
> >> For example, the most common case of overflow we've ever had has very
> >> much been array indexing. Now, sometimes that has actually been actual
> >> undefined behavior, because it's been overflow in signed variables,
> >> and those are "easy" to find in the sense that you just say "no, can't
> >> do that". UBSAN finds them, and that's good.
> >
> >We build with -fno-strict-overflow, which implies -fwrapv, which removes
> >the UB from signed overflow by mandating 2s complement.
>
> I am a broken record. :) This is _not_ about undefined behavior.
>
> This is about finding a way to make the intent of C authors unambiguous.
> That overflow wraps is well defined. It is not always _desired_.
> C has no way to distinguish between the two cases.
I'm pretty sure that the 'undefined' behaviour of signed overflow
it so that cpu can do saturating arithmetic (useful on analogue data)
or can fault (and maybe generate a signal) and still be compliant.
The Linux kernel (and pretty much all userspace) doesn't want either
behaviour.
(Unexpected saturation leads to very confusing bugs that are as bad
as wrapping but much less obvious.)
I do wonder whether trying to remove all arithmetic on char/short
variables should be an aim.
The only reason to have char/short is to reduce the size of a structure.
A first stage would removing all short locals, function parameters
and function returns.
There will be some (sensible) false positives for char.
If you breath on a char/short it becomes 'signed int',
even (x ? 'a' : 'b') is 'signed int'.
David
-
Registered Address Lakeside, Bramley Road, Mount Farm, Milton Keynes, MK1 1PT, UK
Registration No: 1397386 (Wales)
From: Dan Carpenter
> Sent: 14 May 2024 09:45
>
> Snipped all the bits where you are clearly correct.
>
> On Mon, May 13, 2024 at 12:43:37PM -0700, Kees Cook wrote:
> > > drivers/usb/class/usbtmc.c:852 usbtmc_generic_read() warn: potential integer overflow from user
> 'max_transfer_size + 1'
> > > 842 * wMaxPacketSize – 1) to avoid sending a zero-length
> > > 843 * packet
> > > 844 */
> > > 845 remaining = transfer_size;
> > > 846 if ((max_transfer_size % data->wMaxPacketSize) == 0)
> > > 847 max_transfer_size += (data->wMaxPacketSize - 1);
> > > 848 } else {
> > > 849 /* round down to bufsize to avoid truncated data left */
> > > 850 if (max_transfer_size > bufsize) {
> > > 851 max_transfer_size =
> > > 852 roundup(max_transfer_size + 1 - bufsize,
> > > ^^^^^^^^^^^^^^^^^^^^^
> > > This can overflow. We should make it a rule that all size variables
> > > have to be unsigned long. That would have made this safe on 64 bit
> > > systems.
> > >
> > > 853 bufsize);
> > > 854 }
> > > 855 remaining = max_transfer_size;
> >
> > Again, do we _want_ this to overflow? It looks like not. I'm not sure
> > what this code is trying to do, though. The comment doesn't seem to
> > match the code. Why isn't this just roundup(max_transfer_size, bufsize) ?
> >
Isn't it just max_transfer_size / bufsize * bufsize?
> roundup() has an integer overflow in it.
Which is a generic problem with these 'helpers'.
If the function is open coded any overflow is obvious.
But hide it in a wrapper and it is just 'assumed to work'.
DIV_ROUNDUP(x, y) can be either (x + y - 1)/y or (x - 1)/y + 1.
The first is valid for 0 but can overflow, the second is valid for x != 0.
(Who knows what is expected for negative values!)
In most places one of the pair will always be correct.
Obfuscating the code tend to stop readers (and the kernel code does get some)
spotting things in passing.
David
-
Registered Address Lakeside, Bramley Road, Mount Farm, Milton Keynes, MK1 1PT, UK
Registration No: 1397386 (Wales)