Pitch: enable bounds-checking for BufferPointers

glessard · 2024-02-02T15:47:25.433Z

fclout:

Is “unchecked” another term that we should ask [security auditors] to watch for?

My personal opinion is that it would be nice to have a nomenclature for the type of unsafety that is being lifted at any one time.

There are 5 ways to be unsafe with memory:

Temporal safety: that's allocation lifetime, use-after-free, and indicating manual memory management. We don't really have a term for this, but we do use the related terms Unmanaged and the prefix Managed.
Spatial safety: that's bounds checking. We are proposing the term "unchecked" in this pitch.
Definite initialization: the main way uninitialized memory gets exposed in Swift is around manual memory management, and some special initializers that use the term unsafeUninitialized in an argument label.
Type confusion: this is seeing one type of memory as another. We use withMemoryRebound(), withUnsafeBytes and the "raw" particle.
Thread safety: the concurrency effort is coming up with terms here, such as "nonisolated", Sendable (and never-Sendable types), etc.

fclout · 2024-02-02T16:27:00.176Z

In the course of developing -fbounds-safety, we learned that people get confused when “unsafe” can mean both “you might be making a mistake right here” (the unchecked subscript would be that type) and “if you made a mistake somewhere else, this could become dangerous” (an incorrect use of assumingMemoryBound(to:) kind of mistake). I haven’t formed an opinion on whether different categories of memory safety hatches should be identifiable by their name, but at first glance I think it might not square with this (repeated) piece of engineer feedback. The two are linked to some degree, but people are more interested in knowing “when the unsafe is going to hit” than specifically what type it is. (Auditors can go either way as long as they have the signal.)

glessard · 2024-02-02T16:28:36.896Z

That’s valuable information, thank you.

carlynorama · 2024-02-02T16:30:16.121Z

I do think if Swift wants to move into the embedded space being clear as to the size and profile of Unsafe code would be good to add to the documentation?

I had been (erroneously?) assuming that Unsafe* meant it would look like the C code once compiled. I gotta learn to do my own leg work there.

I have an intuitive sense how much heft (size and speed) certain C and C++ structures add. I thought when using Unsafe I could let those kick in.

It's possible some of this can be handled by compiler flags in the future, and that all Swift code (regular or Unsafe) could eventually kick C's ass in the embedded space ;)

++1 for clear language like @glessard (with the caveat by @fclout) says to help both people and linters catch expensive choices.

fclout · 2024-02-02T17:04:24.379Z

When talking about the cost of certain C/C++ structures, it's very important to keep in mind that C and C++, up until very recently, were not equipped to deal with bounds checks. This is because the prevailing wisdom was that if you didn't want one, you would remove it yourself. Languages in which bounds checks don't even have an opt out have more of an incentive to develop these types of optimizations.

There's been LLVM work going into that area in the last few years and it's becoming easier to have bounds checks on by default. For instance, look at the code generated for a sum function that has a bounds-checked pointer structure:

int sum(bc_int_p p, unsigned up_to) {
	if (!bounds_check(p, 0, up_to))
		__builtin_trap();
	
	int sum = 0;
	for (unsigned i = 0; i < up_to; ++i) {
		sum += access(p, i);
	}
	return sum;
}

The access function checks with bounds_check(p, i, i+1). Clang 16 is unable to remove the bounds check inside the loop, but clang 17 does, as LLVM improved and it can now tell that the failure branch can never be taken.

carlynorama · 2024-02-02T17:47:50.249Z

Nice. That's a great example. Avoiding out of bounds errors cheaply in every language is in everyone's best interest.

When I did more work on much smaller systems I could just arbitrarily reach for pointers because I knew what I put where and my code was the only code playing on the chip. For loops (which are a check) wrapping an accessor func that also had a bounds check (like in the full example) would indeed have been spendy on 8 KB ISP Flash, 512B EEPROM, 1 KB SRAM. I never would have written that. It was my job to just never get the ask wrong. Glad to know that now I could write the safer code.

In shared environments, "just don't screw up" is a super dumb and unsafe philosophy. Should be discouraged. Bounds checks for everyone.

But when I have old C (or now C++ code!! Yay!) and I want to interface to it with Swift so I can do as much as possible as safely as possible, or I want to use Swift in small environments in the future, I just am hoping for predictability about what kinds of "helpfulness" will be added where and when.

Adding a bounds check to Unsafe*BufferPointers is not something I would have been expecting. My expectations can be changed, but that requires clear language.

tbkka · 2024-02-02T18:14:10.182Z

+1 for fixing a long-standing inconsistency in Swift Unsafe*Pointer types around the behavior of subscripts. In particular, the fact that UnsafeBufferPointer today is bounds-checked in Debug builds but not Release builds is a real source of confusion. Making it bounds-checked always would address this.

And UnsafePointer still does have a subscript operator (necessarily unchecked) that folks can use for those rare cases where absolutely-never-checked pointers are required.

wadetregaskis · 2024-02-02T19:44:58.206Z

Example where the compiler should remove pointless bounds checks but does not, requiring use of UnsafeBufferPointer (or -Ounchecked).

The proposed [unchecked:] extension to Array would help, but I do worry - especially in light of the aforementioned example, which is about as simple a case as the optimiser could possibly ask for - that it might be more just refining the workaround than fixing the problem.

John_McCall · 2024-02-02T20:59:17.885Z

That benchmark has a mutable global array that starts with 3 elements and only ends up with >= 10 elements because of a specific loop that happens to be run before the main loop, which repeatedly indexes into the array at arbitraryValue % 10. To remove bounds checks from that main code, the optimizer would have to prove that exact global sequence of operations and then prove that the arbitrary value is non-negative. It's not in any way impossible, but it is a whole lot of analysis that's pretty narrowly applicable.

wadetregaskis · 2024-02-02T21:53:39.574Z

The bounds checks are not omitted even if the array is statically defined at compile time.

carlynorama · 2024-02-02T22:00:49.959Z

Out of curiosity what are you using to statically define the array and how does that lead to a promise later in the code that the number used to access the array will never be bigger than array.count?

Would it help the compiler out to make it a "promise" by setting the cache as a let and the magic number 10 replaced by a constant set equal to its count or no? (below)

Or alternatively if one wanted to go back to calculating the values at run time,
cache = [ ] ; cache.reserveCapacity(divisor)

Which is more like a C fixed length single type array?

(I took out the withUnsafe { } because isn't part of the argument for applying bounds checking to UnsafeBuffers that the compiler will eventually be good enough to dismiss unnecessary checks for everyone?)

func benchmark() {
    let MAX: Int = 440_000_000
    let cache: [UInt] = [0, 1, 4, 27, 256, 3_125, 46_656, 823_543, 16_777_216, 387_420_489]
    let divisor:Int = cache.count //as a promise? 

   func is_munchausen(number: Int) -> Bool {
            var n = number
            var total: UInt = 0

            while n > 0 {
                total += cache[Int(n % divisor)]

                if total > number {
                    return false
                }

                n /= divisor;
            }

            return total == number
        }

        for k in 0..<MAX where is_munchausen(number: k) {
            print(k)
        }
    }
}

Karl · 2024-02-03T12:17:37.940Z

Andrew_Trick:

A non-bounds-checked-by-default "Buffer" type is frankly absurd.

This language really doesn't help.

Here's the thing - I sat down intending to explain in detail about how you're missing important details about why LLVM fails to optimise Swift bounds-checking (it also has a lot to do with Swift's use of signed integers as indexes; LLVM isn't half as good at optimising signed numbers as it is unsigned numbers). I intended to explain how a (pointer + length) type which bounds-checks in debug builds but not in release builds is a valuable feature, and how bounds-checking itself is much less able to guarantee safety in a buffer which might not be entirely initialised. I intended to bring this back to the point that unsafe types still have preconditions but trust the developer to ensure they are satisfied manually, so the notion that these types are "broadly, vaguely unsafe" is just completely wrong. I've spent years looking at this issue in-depth, and indeed have written my own bounds-checked buffer type to use what I've learned. Still, I think it remains very valuable to have a true lowest-level, no-nannying buffer type in the standard library.

But here's the other thing - I'm aware that I'm arguing for something that is less easy to explain. It's easy to sell people on the idea of "broad, vague" idea of some kind of safety.

For the last couple of days since you wrote this, I've thought about writing a detailed response which elaborates on the points I briefly mentioned above, and treats this like a serious discussion. But every time I consider doing that, I see that phrase I quoted above - "frankly absurd" - and I just lose all energy and motivation to engage with this process. I've got better things to do with my time than to engage in that kind of discussion which does not welcome the expertise and advice of others.

(EDIT: Updated docs for my UnsafeBoundsCheckedBufferPointer to better-explain how it works)

jim · 2024-02-03T12:48:06.522Z

Karl:

it also has a lot to do with Swift's use of signed integers as indexes; LLVM isn't half as good at optimising signed numbers as it is unsigned numbers

Is been thinking about this a lot lately, too. And this design choice could also be considered “frankly absurd”. Why weren’t unsigned integers used from the start?

ksluder · 2024-02-03T16:38:40.915Z

Karl:

I see that phrase I quoted above - "frankly absurd" - and I just lose all energy and motivation to engage with this process.

I feel very much the same. Once I saw that comment I just decided, “why bother?”

Andrew_Trick · 2024-02-03T17:56:16.811Z

@Karl I apologize for my bluntness. My primary point was that, because bounds checks were disabled in Release, we never made an effort to optimize them. And it would be fairly straightforward to hoist checks out of loops in SIL. Nonethless, I completely agree with you that any programmer who cares about the cost of checks should not need to rely on the optimizer. But, since you quoted the least relevant line from my message, I'll explain and reiterate.

As a programmer, it does seem absurd to me that I would ask for a pointer-with-bounds, then still be required to write my own bounds checks. My own former perspective on maximum-performance-by-default also seems absurd in hindsight now that know how prevalent and severe bounds violations are, and now that I know that these bugs typically won't show up in Debug testing.

I think that, to most programmers, the "Unsafe" in Unsafe*BufferPointer means that they can only use it within the current scope. You're correct that failure to initialize memory is another implicit form of unsafety. The most common uses of UnsafeBufferPointer provide a view into another data structure that does enforce initialization, so we normally want to think about it as an initialized buffer.

In fact, I think a far superior approach to unsafe API design is to explicitly refer to the type of unsafety being exposed at the point where it is relevant. We should use 'unchecked' on a subcript that doesn't check its index. We should use Unmanaged on a type that requires a separately managed lifetime. We should use 'uninitialized' in either the type name or label whenever relevant. @glessard outlined this well above.

Joe_Groff · 2024-02-03T18:06:20.602Z

Karl:

Here's the thing - I sat down intending to explain in detail about how you're missing important details about why LLVM fails to optimise Swift bounds-checking (it also has a lot to do with Swift's use of signed integers as indexes; LLVM isn't half as good at optimising signed numbers as it is unsigned numbers).

There are things that signed integers do make harder to optimize, but I don't think bounds checking is fundamentally one of them. It'd be good to hear what sorts of missed optimizations you're seeing with signed integers so we can hopefully generalize them in LLVM.

Andrew_Trick · 2024-02-03T18:30:24.316Z

Karl:

Here's the thing - I sat down intending to explain in detail about how you're missing important details about why LLVM fails to optimise Swift bounds-checking (it also has a lot to do with Swift's use of signed integers as indexes; LLVM isn't half as good at optimising signed numbers as it is unsigned numbers).

I'm also confused by this statement, and my original intent was to encourage exactly this kind of feedback (probably best detailed in a bug report)

Andrew_Trick:

If anyone has important uses cases where the optimizer fails to remove bounds checking on Unsafe*Pointer, this is a good time to file those bugs.

My experience was that LLVM was great at optimizing bounds checks for signed indices, but often failed at unsigned indices. This is because the representation of induction variables was designed around undefined behavior rules in C. But a lot of new bounds checking optimizations have been added to LLVM since then.

fclout · 2024-02-04T02:20:27.254Z

For security context: an extremely substantial number of security issues have been caused in the past by checks like assert(index < count) being compiled out of release builds. It's on every security auditor's checklist that a bounds check that only exists in a debug build is a red flag. In fact, all security people faced with the fact that Swift doesn't bounds-check buffer pointers are baffled.

I've definitely seen open-source Swift code insufficiently checking its buffer pointer accesses. This raises the question: who actually knows that Unsafe*BufferPointer bounds-checking depends on your build configuration? I expect that if you asked Swift developers who aren't part of this discussion, many/most would guess wrong. This is a serious problem.

I have no doubt that bounds-checking Unsafe*BufferPointer is the right thing to do. I wish that ensuring bounds safety was at the top of everyone's mind and that this discussion would turn to "OK, these checks are actually important and we should have them, but how can we reduce the impact on our software?"

I think that the proposed plan is already sensible:

measure impact on benchmarks and find it to be small;
fix standard library uses where the check adds a lot of overhead (as this will impact every program, regardless of whether they use buffer pointers themselves or not);
encourage people to file performance bugs when they believe a bounds check should have been removed but has stuck around.

One additional tool that we have with -fbounds-safety is that the compiler tags the automatically-added bounds-checking instructions, so you can use optimization remarks to run the pipeline and see where are the checks that weren't optimized away. For Swift, this could help engineers be confident that their expectations are met, and when they aren't, it helps them file issues and use unchecked: judiciously, rather than systematically. (Inversely, one might be able to devise a scheme where the compiler remarks where unchecked: is actually removing a check, which security people would love to see!)

In an ideal world, engineers would collate their use cases for unsafe pointers, and when significant categories are identified, the community could step up with abstractions that remove the need for them. This is out of scope for this proposal, of course.

jrose · 2024-02-04T08:21:31.360Z

I'm torn on this, but I do agree that we might have different feelings in a year, when the non-Copyable ScopedBufferPointer or whatever exists.

Andrew_Trick · 2024-02-09T21:16:02.260Z

@Karl is right about the current optimization deficiency (I had honestly forgotten about the bugs). In 2021, a lot of great work was done in LLVM to remove "range checks", but that was specifically targetted at unsigned comparisons. The Swift library team could not have foreseen that, and there's no reason the same optimizations can't be done for signed comparisons.

Again, I don't think this is directly relevant to the proposal, because anyone who wants to avoid bounds checks within their own project can trivially accomplish that. This proposal is about the type that appears in public APIs. The relevant question is whether every developer who uses your API would naturally assume they need to write their own explicit checks when they access the buffer you give them. We give them the opposite feedback by supporting bounds checks in debug builds.