Formal specs and optimizations in general

language design
41

That would make it depend on optimizations if an overflow error is emitted. This is going to be very confusing for programmers and will make it really easy for different compiler versions or optimization levels to break programs.

If one us using overflow checking for the purpose of determining whether a program would run correctly on all platforms, having such checks optimized out would make it less useful. If, however, the purpose of overflow checks is to guard against the possibility of a program producing seemingly-vallid-but-wrong results as a consequence of overflow, the fact that a program is able to produce correct results on one system in circumstances that would exceed the abilities of another isn't a problem.

Besides, I'd find any confusion caused by the fact that a program works correctly in cases where it wouldn't be required to do so as trifling compared with optimizers like a certain goofy C compiler that will use calls to a function like:

unsigned mul_mod_65536(unsigned short x, unsigned short y)
{ return (x*y) & 0xFFFFu; }

to infer that the value of x within the caller will never exceed 0x7FFFFFFF/y.. Note that the authors of the Standard have indicated that they would expect that commonplace implementations would process functions like the above in a fashion equivalent to using unsigned math whether or not the Standard compelled them to do so, implying to me that the reason such treatment isn't mandated is that the Committee thought the only implementations that would do otherwise would be those where unsigned math would be expensive, which hasn't been the case for decades.

Having a program report precisely when all overflows occur is expensive. Having it report what calculations cannot be regarded as reliable would be much cheaper. The cost difference between precise overflow trapping and lazy (but still reliable) overflow detection is much larger than the cost difference between that and "overflow is allowed to do everything" semantics used by some C compilers.

42

I am thinking about optimizations being able to change x * 10 / 10 from an operation that panics when x * 10 overflows to an operation that just returns x in all cases. I wasn't talking about different machines, but now that I think about it the reduced portability is a big con too.

Behavior of safe programs shouldn't depend on optimizations as much as possible. Things like pointer values is fine as it varies between executions of the same executable anyway, but anything that only changes sometimes, like when a compiler changes an optimization, is just asking for trouble.

1 Like
43

If one regards integer overflow as a form of resource exhaustion (there are many situations where the average size of numbers in a data set is far below the peak, and the maximum size of data that can be handled would be dependent upon the average size of the numbers involved), the fact that some inputs of a program successfully run on some implementations but exceed resource limits on others should hardly be astonishing. If a particular system could perform integer arithmetic using 32-, 64-, or 128-bit types, but 32-bit types were much faster than larger ones, then in many cases it may make sense to feed some inputs to a build of a program that uses 32-bit math and, if that fails, try again with a built that uses 64-bit math and, if that fails, with 128-bit math.

There are times when it would be useful to validate that a particular input would be acceptable to all builds of a program. In such cases, however, one would not only want to enable precise overflow trapping, but also impose artificial constraints on things like the amount of stack space or the amount of storage that can be made available via malloc(). Even when running on a system where every task has 1MiB of stack at its disposal, it may be useful to have a build which will not only squawk if stack usage exceeds 60KiB, but also allocate stack space for all automatic objects even if they're kept in registers. That does not, however, mean that implementations shouldn't attempt to minimize stack usage or maximize the amount of space available to malloc(). Doing so may cause a build to successfully process inputs that would choke other implementations, but if one is trying to build the most efficient application that can accomplish some particular task with some data set, and a build can accomplish a task in cases where a more less efficient build could not, the fact that the latter build can handle a wider range of tasks while being more efficient would be a double win.

44

There do exist compiler optimizations in C++ where the compiler is allowed to change the observable behaviour of the program. For example:

https://en.cppreference.com/w/cpp/language/copy_elision#Non-mandatory_elision_of_copy.2Fmove_.28since_C.2B.2B11.29_operations

So really, the statement should be:

Compiler optimizations must not change the behaviour of programs running on the abstract machine, except where the change is explicitly allowed by the language specification.

However, this doesn't really change anything, and Rust currently has no such exemptions AFAIK. It doesn't change the fact that (aside from such exeptions) we really don't want optimizations to change program behaviour.

Using formal specifications to define the abstract machine behaviour, and checking optimizations for correctness against those specifications doesn't prevent us from adding such exceptions in the future, if the motivation was sufficiently strong.

45

we really don't want optimizations to change program behavior.

Consider the function:

int silly(long a, int b)
{
  unsigned char wasteOfSpace[10000];
  wasteOfSpace[0] = b;
  if (a)
    return silly(a-1, a | wasteOfSpace[0]);
  else
    return b;
}

In your view, if the semantics of stack overflow are defined as forcing an abnormal program termination, how should an "ideal optimizer" process that function? If the function simply returned b unconditionally, its behavior would indistinguishable from an unoptimized version which would perform actual recursive calls in any case where the latter wouldn't blow the stack. Of the cases where an unoptimized version of the function would blow the stack, for which ones would you regard that as "observable" behavior? If an implementation were to optimize out 10,000 bytes of stack usage for wasteOfSpace, for example, that would cause function execution to succeed in many circumstances where a version that didn't do so would fail. Should such optimization be considered any less "observable" one that would lead off the function with if (a >= 0) return b;? How about a simplification of the function to simply return b;?

46

The abstract machine doesn't have the concept of a stack overflow. It's an artifact of the target machine, and the compiler process translating from abstract machine to target machine defines what happens when the target machine experiences a stack overflow (which has no connection to what the abstract machine commands are).

4 Likes
47

True. But this is true even for CompCert and CakeML, even though the entire compiler is proven correct there. The thing is:

It is fundamentally impossible to prove anything about anything that happens in the real world.

Programs are physical artifacts that run on real hardware, and there is a possibility for bugs and faults on every level. There will always be assumptions. So there's always a trade-off -- how big do you make your "trusted computing base" (TCB), how many assumptions do you make? CompCert and CameML are great exercises in getting the TCB down to the minimum. That's awesome. But there are other ways to make progress and improve the state of computing and compilation, such as starting with the messy reality of LLVM IR and trying to improve it incrementally, and I think those are worthwhile, too. :slight_smile:

I agree that this is a valid possibility to consider. This is an example of the non-determinism that I mentioned before.

This does not require any fundamental change to how we specify our languages or evaluate compiler correctness.

If one does that, then the program surely should fail in a controlled way when the integer overflows. Having programs randomly misbehave ("Undefined Behavior" / "optimizations can change behavior") on resource exhaustion is a horrible idea and leads to unpredictable behavior.

That's why in Rust, you get a controlled panic or abort when the heap or the stack overflow.

6 Likes
48

The abstract machine doesn't have the concept of a stack overflow.

If a language specification says that operations with various integer types are generally guaranteed to correctly process and store computations within a certain range, but overflow is defined in terms of what values an implementation happens to be unable to process or store correctly, then the only circumstances where the abstract machine would need to have a concept of integer overflow would be those which would require coercing integer types to fixed-format types. If e.g. one has the code:

void outsideFunction(int);
void test(int x, int y, int z)
{
  int temp1 = x*y;
  int temp2 = temp1 >> z;
  outsideFunction(temp2);
}

If the implementation specifies how int values will be passed to outside functions, and temp2 wasn't within the range of values that could be passed, it would be required to regard that as an overflow condition, but the computations that yield temp1 or temp2 could at the compiler's leisure be treated either as computations that the implementation happens to be able to handle correctly (in which case they would not cause an overflow to be flagged), or as computations that it happens to be unable to process correctly (in which case the overflow must be flagged).

49

Having programs randomly misbehave ("Undefined Behavior" / "optimizations can change behavior") on resource exhaustion is a horrible idea and leads to unpredictable behavior.

The vast majority of C implementations used in the real world would "randomly" misbehave if a stack overflow were to occur. In a microcontroller without protected memory, there's not really much else that could happen. Fortunately, most applications have fairly predictable stack usage such that no sequence of events could trigger a stack overflow, but unfortunately relatively few toolsets offer any means of statically validating stack usage. IMHO, languages should put more focus on ways of allowing static validation so as to avoid or minimize the need for run-time checks, while offering assurances that unexpected stack overflows could never occur in a correct program.

The way I'd like to see languages accommodate stack would be with a __STACK_SAFE intrinsic which would always be allowed to return 0, but should when practical yield 1 in cases where doing so could not result in a stack overflow (if an implementation cannot prove that yielding 1 couldn't cause a stack overflow, it would have to return 0). Programs would in turn be required to be written in such a way that no functions would be invoked recursively if the intrinsic were to always yield zero. Given such constraints, an implementation could compute what the worst-case stack usage of every function would be if the intrinsic were to always yield zero, and the determine at each point where the intrinsic is evaluated, how what the worst-case stack usage would be if the intrinsic returned 1 once and thereafter returned zero. This would allow a function like:

int okay;
void inorder_tree_traverse(NODE *node)
{
  if (okay && __STACK_SAFE)
  {
    if (node->left)
      inorder_tree_traverse(node->left);
    process_tree_node(node);
    if (node->right)
      inorder_tree_traverse(node->right);
  }
  else
    okay=0;        
}

to support trees of whatever depth would be accommodated by available stack space, and bow out gracefully for trees deeper than that, without the code ever actually hitting the stack limit.

Returning to the subject of integer overflow, I still think it makes sense to view it as somewhat analogous to resource exhaustion, in that some data sets that might be just beyond the range of what some implementations can handle, might be barely within the range of what some others could handle.

Also, as I've said before, a paradigm which is common enough to merit language support is that a program will receive what may be a mix of valid and invalid (possibly malicious) data, should process data usefully when practical, and must refrain from certain worse-than-useless behaviors when data can't be processed usefully. If integer overflows only occur in situations where a multiple behaviors would be equally acceptable, why should one care if optimization causes the compiler to replace one acceptable behavior with a different one? To be sure, present language specs don't do a great job of allowing programmers to indicate what ranges of behaviors are acceptable or unacceptable in different cases, but allowing programmers to write code that gives compilers the freedom to make such substitutions seems much better than trying to aggressively optimize based upon assumptions that programs will never receive inputs that could cause "Undefined Behavior".

50

Lucky enough, Rust doesn't. So I do not consider it terribly relevant what the vast majority of C implementations do. Sure, not all platforms can easily detect stack overflows, but that is no excuse to just ignore the problem on platforms that can.

Regarding your other points, as I keep saying, the "UB paradigm" can express all that just fine. By proposing to move language correctness to a different (and from all I can see, rather shaky) foundation, you are throwing out the baby with the bathwater. Yes, the way C uses UB is bad (mostly). But the underlying idea of UB is great, and when UB is being used properly and responsibly, it is a great tool for language and compiler designers alike. Sadly, many people are bewildered by how C uses UB and conclude that UB itself is a fundamentally flawed concept -- which it is not.

12 Likes
51

Sure, not all platforms can easily detect stack overflows, but that is no excuse to just ignore the problem on platforms that can.

Is it better to say that Rust is unsuitable for any platform that can't efficiently trap stack overflow, or to recognize categories of limited-functionality implementations that would be supportable on such platforms but would lack some of the semantic guarantees that full-featured implementations should be expected to support?

Sadly, many people are bewildered by how C uses UB and conclude that UB itself is a fundamentally flawed concept -- which it is not.

The way in which optimizers use UB is suitable for tasks which will only receive input from trustworthy sources, or where even giving the control to a malicious entity that supplies input would not allow them to do anything harmful. It is unsuitable for tasks where a wide but not quite unlimited range of tolerably useless actions would be acceptable in cases where they cannot behave usefully. The fact that something is only suitable for a narrow range of tasks doesn't mean it's "fundamentally flawed", but the fact that there are some tasks for which it is suitable doesn't mean it should be regarded as "generally useful".

The goal of an "optimization-friendly" language should be to maximize the efficiency with which it can accomplish any of the tasks for which it is supposed to be suitable, and a "general purpose" language should seek to be suitable for tasks that require program execution to stay at least loosely on the rails even in cases where it would be impossible for a program to behave usefully. A general-purpose language that seeks to be optimization-friendly should allow programmers to meet the requirements for application requirements without having to tie optimizers' hands.

I'm completely failing to see how it's somehow better to say that programmers must either perform integer computations in a way that forces compilers to use precise trapping or wrapping semantics, or in a way that would require that programmers avoid integer overflow at all costs and deny compilers any freedom regarding corner case semantics, rather than allowing programmers to perform integer math in ways that would treat a number of possible results as equally acceptable consequences of integer overflow without "allow a supplier of malicious data to execute arbitrary code" being one of them.

Perhaps the misunderstanding stems from the fact that what I'm seeking is not so much to give optimizers the ability to change the behavior of code which would otherwise have a precisely-defined meaning, but rather to have some language constructs defined as yielding Unspecified choice from among a number of behaviors, some of which may involve the existence of values that behave non-deterministically, some (though not all!) of which would require that a compiler be able to "see the future", and some of which may be allowed or disallowed based on aspects of program structure rather than the sequence of side-effect producing steps executed. For example, consider the optimization implications of a form of break which, if executed within a for loop, would invite a compiler to skip the iteration of the loop body for any convenient subset of iterations, past or future, upon which the present iteration has no data dependencies beyond those implied by the second and third arguments of the for statement. Such a construct would allow a compiler to generate code that would execute multiple loop iterations in parallel, and use a flag with moderately weak semantics to let all threads executing the loop that they might as well stop. If e.g. a compiler were to parallelize a loop that's used to compute values and store them to sequential spots in an array, and it were to early exit, the subset of array values that were written versus left unchanged might be inconsistent with sequential program execution, but if all subsets of processed values would be essentially equally useful (or, more likely, useless) a compiler shouldn't be limited to processing things purely sequentially. The construct wouldn't give a compiler general permission to reorder everything in the program arbitrarily, but would instead give a compiler broad control over how it orders the iterations of one particular loop.

52

You can place the stack before everything else if it grows down or after everything else if it grows up. This will ensure that the stack will overflow into a non-existent part of the address space. One of the micro-controller frameworks for rust does exactly this.

1 Like
53

I disagree, and I don't understand your reasoning here. Whether or not a program takes inputs, and from where, is entirely unrelated. Sure, the presence of UB makes handling untrusted inputs more tricky, but that doesn't make it "unsuitable". I don't see how whether or not a program takes inputs change the discussion in any way.

I will say it one last time: your integer overflow example is a total red herring. It is easy to use non-determinism instead of UB to get something along the lines of what you are proposing. But that approach only works in very few cases, of which you picked one. It doesn't help at all for things like UB-enabled alias analysis.

You keep suggesting that somehow, using UB in a spec inadvertently implies something about how integer overflow works. That's just not the case.

This is non-determinism. That's exactly what I keep replying to you ever since you got started with this.^^

:thinking:

3 Likes
54

Assuming the "stack" is a concept in the AM, defining stack overflow as not UB is almost easy:

  • If calling a function would result in a stack overflow in a hosted implementation (IE. when #![no_std] is not used), an implementation-defined diagnostic message shall be displayed at runtime and the program shall terminate execution, or an implementation defined signal shall be raised. Otherwise, it is implementation-defined if stack overflow is detected, and whether a diagnostic message is displayed. If stack overflow is not detected, the behaviour of such a call is undefined.

I'd note that without mandating detection of stack overflow, which may be prohibitively difficult to implement in an embedded environment, having undefined behaviour on stack overflow would be impossible to avoid (and yes, it makes such implementations unsound).

1 Like
55

Integer overflow is interesting because it's a case where C/C++ did UB badly. They opted to define unsigned integer overflow and undefine signed integer overflow, so UB is dependent on sign. Integer overflow is usually undesirable behavior, whether or not the type is signed or unsigned--although there are clear cases where modulo 2^N arithmetic is acceptable or desirable (these are not the majority of cases there!). I haven't done a thorough scouring of CVEs, but my recollection is that most integer overflow CVEs are actually triggered by unsigned rather than signed integers, again highlighting that well-defined is not the same as correct. What makes C's decision here really daft, though, is that the most efficient way to detect overflow is to do it and observe if the result makes sense, and there is no way to do that with signed integers, not even a mechanism to tell you if an operation overflows (although Clang and later GCC did provide a builtin for detecting overflow).

The problem with integer overflow is that it provides a very poor basis for understanding how UB actually works, and it's the worst example to use to motivate discussing anything about UB. In the context of compilers, we have to discuss separately what the hardware will do for naĆÆve translations of code and what the optimizer is permitted to do for code. For most UB--at least, those that don't involve compiler hints (such as core::intrinsics::assume or core::hint::unreachable_unchecked)--the actual hardware semantics are generally insane, hard to specify, and hard to reason about. Scribbling on random memory can mean scribbling over variables on the stack, or even stack return pointers. Permitting anything less than "execute arbitrary code" as semantics would prohibit compilation to most architecture! Integer overflow (whose naĆÆve machine translation is modular arithmetic) is the exception, not the rule here.

But from the optimizer's perspective, UB largely manifests as inconsistency: part of the program acts as if x were 1, the other part acts as if x were 2, but nowhere was the value of x changed. And it's easy to see why even something so pedestrian as undefined values necessitate this inconsistency behavior for the optimizer.

Now, historically, UB wasn't about permitting the optimizer to optimize code. As I understand it, for some processors at the time, traps were not promptly delivered, so the semantics of hardware traps needed to account for "and some amount of code following this will also be executed if it traps, at least for some machine"--hence why UB looks reasonable rather than appealing to implementation-defined behavior instead. But as optimizers develop and gain in capability, the flexibility implied by UB becomes a major asset for the compiler: the compiler can move around, or even delete, potentially-trapping instructions (i.e., memory instructions, which are the most common expensive instruction) without first having to assure itself that the instruction cannot trap. That the compiler can, and will, do this means that the compiler is no longer a naĆÆve translator into assembly, and therefore that C cannot be a portable assembler. Consequently, a lot of the material about UB from compiler developers is focused about why "benign" UB doesn't really exist, and that the naĆÆve translation that portable assembly programmers expect is not forthcoming, instead of discussing how UB is used inside the compiler and what different kinds of UB (yes, there are different kinds!) actually do, and which source-level UB matches to which internal UB kind.

7 Likes
56

You can place the stack before everything else if it grows down or after everything else if it grows up. This will ensure that the stack will overflow into a non-existent part of the address space. One of the micro-controller frameworks for rust does exactly this.

Some microcontrollers and microcomputers trap on attempts to access non-existent parts of the address space, but such behavior is not universal. Further, some systems either have a stack pointer which is smaller than the address size and wraps around, or and even some systems that trap out-of-range accesses force certain critical data (such as the interrupt vector table) to be placed at the bottom of RAM. Having an out-of-bounds access trigger an NMI through a RAM-based vector isn't terribly useful. I worked on a 16-bit system which would tend to fail in such a way that every interrupt would push a few bytes and then immediately trigger another interrupt. Since I/O was memory mapped, this tended to cause the I/O on the device to go berzerk. Somewhat annoyingly, this would cause an instant reboot of an attacked 80386sx-based PC running Windows 3.1 whose only connection to the target was via the COM port on the CPU emulator board. I don't know if the Windows COM driver got clobbered by excessively-fast wiggling on the handshake wires, or the flailing I/O somehow caused enough ground bounce to glitch things, but it did make development a nuisance.

I'm glad to hear that at least one controller framework tries to exploit even a minimalist memory subsystem to guard against stack overrun. I wonder why that isn't an almost-universal practice?

57

I disagree, and I don't understand your reasoning here. Whether or not a program takes inputs, and from where, is entirely unrelated. Sure, the presence of UB makes handling untrusted inputs more tricky, but that doesn't make it "unsuitable". I don't see how whether or not a program takes inputs change the discussion in any way.

Many programs receive input from untrustworthy sources, and as part of their requirements, must guarantee that maliciously-constructed inputs must not cause them to behave in a manner that is contrary to design and intolerably worse than useless. A program cannot be relied upon to uphold such a guarantee, and thus cannot meet requirements, if any inputs would invoke unbounded Undefined Behavior.

A rule which would allow a compiler to select from among multiple ways of treating some corner case may facilitate optimization without requiring that a programmer do anything special to handle such a corner case, if all of the permissible ways of treating that corner case would meet application requirements. Expanding the range of permissible behaviors beyond those that would meet requirements requires that a programmer simultaneously do more work, and in most cases tie the compiler's hands more tightly, than would have been required without such expansion.

I will say it one last time: your integer overflow example is a total red herring. It is easy to use non-determinism instead of UB to get something along the lines of what you are proposing. But that approach only works in very few cases, of which you picked one. It doesn't help at all for things like UB-enabled alias analysis.

From a Rust perspective, I can see how you would view integer overflow as a red herring, since Rust specifies integer-overflow behaviors precisely. On the other hand, specifying such behaviors more tightly than needed blocks what would otherwise be a number of useful optimizations. Even if one were to simply allow temporary results to behave as though processed with longer-than-specified types at the compiler's convenience (as was historically often done with floats) that would allow quite a few optimizations while keeping program behavior firmly grounded.

On the other hand, aliasing analysis is one of the situations where an approach which considers program structure would be more suitable than one which treats every sequentially-executed step as though it affects program state. The primary purpose of aliasing analysis is to allow compilers to reorder and consolidate or eliminate memory operations. Specifying rules in terms of when compilers are and are not required to process operations in logical execution order would make it easier for compilers to recognize when they may regard various optimizations as safe, without having to unduly restrict programmers' ability to access things in unusual ways.

There are many situations where it would be useful for a compiler that knows that a section of code won't be executed unless some pointer P is equal to another pointer that can't be used to access object X, to generate code that assumes P won't be used to access X. Although one could avoid any complexities that would result from such cases by simply not having any form of comparison operator that would invite such assumptions, the maintainers of both LLVM and gcc both appear to value such optimizations, and it would thus seem that an optimization-friendly language should try to accommodate them. Can you suggest any of including in a language spec a form of comparison that would invite that optimization, in a way that is described purely in terms of sequential operations acting upon the abstract machine state, and would clearly and unambiguously make clear what programmers and compilers are allowed to do?

58

Integer overflow is interesting because it's a case where C/C++ did UB badly. They opted to define unsigned integer overflow and undefine signed integer overflow, so UB is dependent on sign. Integer overflow is usually undesirable behavior, whether or not the type is signed or unsigned--although there are clear cases where modulo 2^N arithmetic is acceptable or desirable (these are not the majority of cases there!).

There are times when programmers need a type that behave as members of a wrapping algebraic ring of integers congruent mod 2**n. Were it not for the C89 Committee's mandate that merely standardize existing practices rather than invent new ones, the best way to handle that would IMHO have been to add two new kinds of unsigned types--one which was specified as being intended for wrapping algebraic use, and one of which was intended to represent numerical quantities. Implementations could thus treat each pre-existing unsigned types as whichever of the others would best serve its customers, but the use of the pre-existing types would be deprecated within portable code in favor of the types which had implementation-independent semantics.

The problem with integer overflow is that it provides a very poor basis for understanding how UB actually works, and it's the worst example to use to motivate discussing anything about UB.

Actually, integer overflow can provide a very good basis if for understanding if one looks at a function like:

unsigned mul_mod_65536(unsigned short x, unsigned short y)
{
    return (x*y) & 0xFFFFu;
}

unsigned values[100];
unsigned test(unsigned short n)
{
    unsigned total;
    for (unsigned short i=0x8000; i<n; i++)
      values[i-0x8000] = mul_mod_65536(i,65535);
    return total;
}

and compares what the published Rationale for the C Coding Standard had to say about unsigned short promotion with the way gcc processes the code.

mul_mod_65536:
        imul    esi, edi
        movzx   eax, si
        ret
test:
        cmp     di, -32768
        jbe     .L3
        mov     DWORD PTR values[rip], 32768
.L3:
        xor     eax, eax
        ret
values:
        .zero   400

According to the Rationale, the authors of the C Standard saw no need to mandate that an expression which coerces the product of two unsigned short numbers to an unsigned type must behave as though performing an unsigned multiply, since they expected commonplace implementations to do so with or without a mandate. I think they'd be rather astonished at how gcc treats the above code.

But as optimizers develop and gain in capability, the flexibility implied by UB becomes a major asset for the compiler: the compiler can move around, or even delete, potentially-trapping instructions (i.e., memory instructions, which are the most common expensive instruction) without first having to assure itself that the instruction cannot trap.

It is useful to allow compilers to select freely from among different ways of processing a construct that will yield different corner case behaviors, in cases where all such ways would meet application requirements. Expanding the set to include ways that would not meet application requirements, however, is counter-productive, and the there is zero evidence that the authors of the C Standard intended it to be interpreted as inviting such treatment. The existence of N1570 Annex L implies a recognition that there should be different kinds of Undefined Behavior, but since Annex L fails to specify anything about what "Bounded Undefined Behavior" means, it's unclear in what cases starting a program with

#ifndef __STDC_ANALYZABLE__` doesn't really mean much.
#error Don't be silly
#endif

would relieve programmers of any needless burdens.

59

There is a very simple solution to this problem: validate your inputs. If your program will happily read however much memory an incoming packet will tell you to, that is a problem, independent of whether or not UB is involved. (Indeed, Heartbleed actually wasn't UB because it used a custom allocator, so the out-of-bounds reads were still in-bounds for an excessively-sized memory object as far as C's memory semantics are concerned. This was a factor in why it was hard to discover the issues with analyzers to catch memory issues.) Allowing untrusted inputs to do bad things is always a problem, and the potential consequences of UB is merely a subset of those problems.

What you are trying to do, I think, is insist that UB be made defined so that the resulting behavior (e.g., traps) can be used in lieu of validation. This approach has been generally rejected by specification writers and compiler developers (for C and languages that generally compete with C). The code that compilers work with, by the time it reaches the guts of the main optimizer, is a representation that only vaguely resembles the original source code. Constraining the UB as you would have it would, in some cases, forbid the use of that representation entirely. While some languages do have these kinds of heavily-defined specifications, it should also be noted that these come with significant barriers to optimization, generally to the point that ahead-of-time compilation to native assembly isn't really practical.

In practice, a lot of UB involved in the optimizer manifests itself in the form of inconsistent results--effectively saying that the value of x is sometimes 1 and sometimes 2, depending on where you are in the program, without x ever being modified in the intervening period. This isn't really a situation that programmers can cope with; you see similar situations crop up when tackling hardware data races, and even the expert academics who wrote the memory model screwed up here (as relaxed atomics essentially attempts to codify a limited subset of hardware data races). I get the feeling here that you're trying to use integer overflow (which is very atypical for C's UB) to motivate generic UB handling, without considering what effect that would have for the more serious memory safety UB issues.

Since you seem to keep harping on this approach so fervently, I'd like to try a little experiment. Consider this simple program, which should hopefully have very self-evident potential undefined behavior:

float f(float *p, float v) {
  return *p = v;
}

Using your favored approach of describing semantics in terms of "allow[ing] compilers to select freely from among different ways of processing a construct that will yield different corner case behaviors," please exhaustively list all of those different ways.

4 Likes
60

True. No problem here. Rust has many great tools to help programmers avoid UB.

This basically requires you to formalize the application requirements in a way that the compiler can understand them. And then the compiler would have to do some code synthesis or automatic theorem proving or so to make sure that this specification is always upheld. I don't think anything like this is even remotely realistic with the current state of the art.

2 Likes