Skip to contentSkip to conversation

Mitigating unexpected arithmetic overflow

RFC Kees Cook 13 participants 44 messages May 7, 2024 – May 18, 2024

lore
Share & tools
lore

Kees Cook

author
#0 lore raw

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

Signature · 1 line
Kees Cook
#1 lore raw

From: Kees Cook

Quoted 14 lines

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. :)

Quoted 9 lines

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)

author
#2 lore raw
Quoted 2 lines · David Laight

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
Quoted 4 lines

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.

Quoted 6 lines

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

Signature · 1 line
Kees Cook
#3 lore raw
In reply to Kees Cook
Quoted 6 lines · Kees Cook

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

author
#4 lore raw
Quoted 4 lines · Linus Torvalds

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:

Quoted 4 lines
Quoted 4 lines

- 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:

Quoted 14 lines
Quoted 5 lines

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".

Quoted 7 lines

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.

Quoted 2 lines

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.

Quoted 6 lines

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.

Quoted 2 lines

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.

Quoted 3 lines

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.

Quoted 5 lines

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".

Quoted 2 lines

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?

Quoted 2 lines

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

Signature · 1 line
Kees Cook
#5 lore raw
Quoted 9 lines · Kees Cook
Quoted 6 lines · Linus Torvalds

Example:

   static inline u32 __hash_32_generic(u32 val)
   {
        return val * GOLDEN_RATIO_32;
   }
Quoted 6 lines

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".

Quoted 2 lines

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

author
#6 lore raw
Quoted 12 lines · Linus Torvalds
Quoted 11 lines · Kees Cook
Quoted 6 lines · Linus Torvalds

Example:

   static inline u32 __hash_32_generic(u32 val)
   {
        return val * GOLDEN_RATIO_32;
   }

But what about:

Quoted 7 lines
Quoted 4 lines

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.

Quoted 3 lines

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.

Quoted 3 lines

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_.

Quoted 2 lines

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.

Quoted 3 lines

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

Signature · 1 line
Kees Cook
#7 lore raw
Quoted 2 lines · Kees Cook

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.

Quoted 1 line

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

#8 lore raw
Quoted 6 lines · Linus Torvalds

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

#9 lore raw
In reply to Linus Torvalds
Quoted 5 lines · Linus Torvalds

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

author
#10 lore raw
In reply to Linus Torvalds
Quoted 5 lines · Linus Torvalds

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.

Quoted 3 lines

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.

Quoted 4 lines

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.

Quoted 4 lines

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.

Quoted 5 lines

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.

Quoted 2 lines

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.

Quoted 2 lines

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

Quoted 2 lines

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.

Quoted 3 lines

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).

Quoted 4 lines

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.)

Quoted 4 lines

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;
Quoted 8 lines

[...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. :)

Quoted 3 lines

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.

Quoted 4 lines

[...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.

Quoted 1 line

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")

Signature · 1 line
Kees Cook
#11 lore raw
Quoted 7 lines · Kees Cook
Quoted 7 lines

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

#12 lore raw
Quoted 8 lines · Theodore Ts'o
struct ext2_super {
       ...
       __u32    time_lo;
       __u32    time_high;
       ...
}
Quoted 6 lines
        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).

Quoted 10 lines

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

#13 lore raw
Quoted 7 lines · Linus Torvalds

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.

#14 lore raw
Quoted 7 lines · Al Viro
Quoted 4 lines · Linus Torvalds

Going the other way is similar:

        all_bits = low_bits + ((u64) high_bits << 16) << 16);
Quoted 8 lines
Quoted 3 lines

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

#15 lore raw
Quoted 5 lines · Linus Torvalds

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

#16 lore raw
Quoted 5 lines · Linus Torvalds

.. 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.

Quoted 7 lines

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.

#17 lore raw
Quoted 6 lines · Al Viro

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

#18 lore raw
Quoted 19 lines · Linus Torvalds
Quoted 6 lines · Al Viro

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.

Quoted 6 lines

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...

#19 lore raw
In reply to Linus Torvalds

...

Quoted 7 lines

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)

#20 lore raw
In reply to Kees Cook
Quoted 7 lines · Kees Cook
	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 ...

#21 lore raw
In reply to Linus Torvalds

...

Quoted 4 lines

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)

#22 lore raw
In reply to Linus Torvalds

Am Mittwoch, dem 08.05.2024 um 16:47 -0700 schrieb Linus Torvalds:

Quoted 2 lines · Kees Cook
Quoted 1 line

...

Quoted 9 lines

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.

Quoted 8 lines

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

#23 lore raw
Quoted 4 lines · Martin Uecker

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

#24 lore raw

Am Sonntag, dem 12.05.2024 um 09:09 -0700 schrieb Linus Torvalds:

Quoted 34 lines · Martin Uecker
Quoted 4 lines

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

Quoted 8 lines
        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.

Quoted 5 lines

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.

Quoted 8 lines

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.

author
#25 lore raw
In reply to Linus Torvalds
Quoted 10 lines · Linus Torvalds
        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/

Signature · 1 line
Kees Cook
#26 lore raw
In reply to Linus Torvalds
Quoted 5 lines · Linus Torvalds

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.

#27 lore raw

Hi Peter,

Quoted 10 lines · Peter Zijlstra
Quoted 5 lines · Linus Torvalds

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").

Quoted 3 lines

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

#28 lore raw
Quoted 14 lines · Justin Stitt

Hi Peter,

Quoted 10 lines · Peter Zijlstra
Quoted 5 lines · Linus Torvalds

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.

Quoted 7 lines

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.

Quoted 4 lines
Quoted 2 lines

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...

#29 lore raw
In reply to Peter Zijlstra
Quoted 9 lines · Peter Zijlstra
Quoted 5 lines · Linus Torvalds

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

Signature · 1 line
Kees Cook
#30 lore raw
Quoted 10 lines · Kees Cook
Quoted 7 lines · Peter Zijlstra
Quoted 5 lines · Linus Torvalds

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.

Quoted 4 lines
Quoted 2 lines

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?

Quoted 3 lines

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.

#31 lore raw

Hi,

Quoted 6 lines · Peter Zijlstra
Quoted 2 lines · Kees Cook

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.

Quoted 8 lines
Quoted 4 lines

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].

Quoted 5 lines

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

author
#32 lore raw
Quoted 6 lines · Justin Stitt

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

Signature · 1 line
Kees Cook
#33 lore raw
In reply to Justin Stitt
Quoted 6 lines · Justin Stitt

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

author
#34 lore raw
Quoted 8 lines · Theodore Ts'o
Quoted 6 lines · Justin Stitt

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.

Quoted 7 lines

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.

Quoted 6 lines

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.

Quoted 3 lines

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.

Quoted 7 lines

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

Signature · 1 line
Kees Cook
#35 lore raw
Quoted 17 lines · Kees Cook
Quoted 8 lines · Theodore Ts'o
Quoted 6 lines · Justin Stitt

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.

Quoted 7 lines

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.

Quoted 6 lines

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

#36 lore raw
In reply to Justin Stitt
Quoted 51 lines · Justin Stitt

Hi,

Quoted 6 lines · Peter Zijlstra
Quoted 2 lines · Kees Cook

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.

Quoted 8 lines
Quoted 4 lines

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].

Quoted 5 lines

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.

Quoted 5 lines

[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:

Quoted 1 line

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).

Signature · 1 line
宋方睿
#37 lore raw
In reply to Kees Cook

From: Kees Cook

Quoted 10 lines

Sent: 16 May 2024 14:31

Quoted 7 lines · Peter Zijlstra
Quoted 5 lines · Linus Torvalds

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.

Quoted 8 lines
Quoted 2 lines

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)

#38 lore raw
In reply to Linus Torvalds
Quoted 9 lines · Linus Torvalds

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.

#39 lore raw
In reply to Linus Torvalds

Am 5/8/2024 um 10:07 PM schrieb Linus Torvalds:

Quoted 2 lines

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

#40 lore raw
In reply to Kees Cook

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

author
#41 lore raw
Quoted 3 lines · Dan Carpenter

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.

Quoted 6 lines

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. :)

Quoted 2 lines

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).

Quoted 16 lines

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;
                             ^^^^^^^^^^
Quoted 3 lines

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;
Quoted 20 lines
  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,
                                                ^^^^^^^^^^^^^^^^^^^^^
Quoted 7 lines

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) ?

Quoted 23 lines

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);
                                       ^^^^^
Quoted 1 line

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)
Quoted 12 lines
  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

Quoted 8 lines
   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.

Quoted 6 lines

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;

Quoted 8 lines

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.

Quoted 19 lines

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)
                    ^^^^^^^^^^^^^^^
Quoted 7 lines

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;
Quoted 10 lines

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...
Quoted 12 lines

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);
                                                                    ^^^^^^^^^
Quoted 2 lines

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)

Quoted 16 lines
   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)

Quoted 7 lines
   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 = ...
Quoted 23 lines
   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);
                                                  ^^^^^^^^^^
Quoted 1 line

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).

Quoted 6 lines
  2266  
  2267          mutex_lock(&data->update_lock);

regards,
dan carpenter

-Kees

Signature · 1 line
Kees Cook
#42 lore raw

Snipped all the bits where you are clearly correct.

Quoted 17 lines · Kees Cook
Quoted 17 lines

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.

Quoted 8 lines
Quoted 3 lines
   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.

Quoted 25 lines
Quoted 23 lines

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);
                                       ^^^^^
Quoted 1 line

The issue here is on a 32 bit system when bytes is INT_MAX.

Quoted 4 lines

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.

Quoted 27 lines
Quoted 27 lines

  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.

Quoted 8 lines
Quoted 5 lines
   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.

Quoted 6 lines

(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.

Quoted 13 lines
Quoted 10 lines

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);
                                                                    ^^^^^^^^^
Quoted 2 lines

This can overflow and then the msecs_to_jiffies() conversion also has an integer overflow in it.

Quoted 10 lines

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.

Quoted 19 lines
Quoted 17 lines

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);
                                                  ^^^^^^^^^^
Quoted 1 line

Overflow and then clamp.

Quoted 4 lines

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

#43 lore raw

From: Dan Carpenter

Quoted 31 lines

Sent: 14 May 2024 09:45

Snipped all the bits where you are clearly correct.

Quoted 1 line · Kees Cook
Quoted 1 line

drivers/usb/class/usbtmc.c:852 usbtmc_generic_read() warn: potential integer overflow from user

'max_transfer_size + 1'

Quoted 24 lines
Quoted 12 lines
   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,
                                                ^^^^^^^^^^^^^^^^^^^^^
Quoted 7 lines

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?

Quoted 1 line

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)