Re: A Famous Security Bug

On 2024-03-22, Keith Thompson <Keith.S.Thompson+u@gmail.com> wrote:

Kaz Kylheku <433-929-6894@kylheku.com> writes:

Since ISO C says that the semantic analysis has been done (that
unit having gone through phase 7), we can take it for granted as a
done-and-dusted property of that translation unit that it calls bar
whenever its foo is invoked.

>
We can take it for granted that the output performed by the printf call
will be performed, because output is observable behavior.  If the
external function bar is modified, the LTO step has to be redone.

That's what undeniably has to be done in the LTO world. Nothing that
is done brings that world into conformance, though.

Say I have a call to foo in main, and the definition of foo is in
another translation unit.  In the absence of LTO, the compiler will have
to generate a call to foo.  If LTO is able to determine that foo doesn't
do anything, it can remove the code for the function call, and the
resulting behavior of the linked program is unchanged.

>
There always situations in which optimizations that have been forbidden
don't cause a problem, and are even desirable.
>
If you have LTO turned on, you might be programming in GNU C or Clang C
or whatever, not standard C.
>
Sometimes programs have the same interpretation in GNU C and standard
C, or the same interpretation to someone who doesn't care about certain
differences.

>
Are you claiming that a function call is observable behavior?

Yes. It is the observable behavior of an unlinked translation unit.

It can be observed by linking a harness to it, with a main() function
and all else that is required to make it a complete program.

That harness becomes an instrument for observation.

Consider:
>
main.c:
#include "foo.h"
int main(void) {
    foo();
}
>
>
foo.h:
#ifndef FOO_H
#define FOO_H
void foo(void);
#endif
>
>
foo.c:
void foo(void) {
    // do nothing
}
>
>
Are you saying that the "call" instruction generated for the function
call is *observable behavior*?

Of course; it can be observed externally, without doing any reverse
engineering on the translated unit.

External linkage is called "external" for a reason!

If an implementation doesn't generate
that "call" instruction because it's able to determine at link time that
the call does nothing, that optimization is forbidden?

The text says so. Translation units are separate; semantic analysis is
finished in translation phase 7; linking in 8.

Out of translation phases 1-7 we get a concrete artifact: the translated
unit. That has externally visible features, like what symbols it
requires. Its behavior with regard to those symbols can be empirically
observed, validated by tests and expected to hold thereafter.

Since semantic analysis is complete, any observable behavior can be
taken to be a fact about that translated unit, a property of it, which
will not change when it is subject to linkage. The truth cannot be
clawed back, according to the way things are defined in the standard,
and this is a good thing.

I presume you'd agree that omitting the "call" instruction is allowed if
the call and the function definition are in the same translation unit.

Yes.

And that's a way to get the effect of LTO portably, in a conforming
way, in any implementation going back decades. Instead of linkage use
#include "foo.c", #include "bar.c" (taking steps to ensure your internal
names don't clash).

LTO is more convenient in that you don't have to use an unusual
program structure, and keeps your internal linkage scopes separate.
Just don't pretend it's conforming to standard C, any more than
-ffast-math.

LTO is "vooodoo" though. The translation units contain intermediate
code, not target code. The intermediate code continues to be subject
to compiler passes when the translation units are brought together.
Thus translation is going on, but the units are gone.

What wording in the standard requires a "call" instruction to be
generated if they're in different translation units?
>
That's a trivial example, but other link time optimizations that don't
change a program's observable behavior (insert weasel words about
unspecified behavior) are also allowed.

An example would be the removal of material that is not referenced,
like functions not called anywhere, or entire translation units
whose external names are not referenced. That can cause issues too,
and I've run into them, but I can't call that nonconforming.
Nothing is semantically analyzed across translation units, only the
linkage graph itself, which may be found to be disconnected.

In phase 8:
    All external object and function references are resolved. Library
    components are linked to satisfy external references to functions
    and objects not defined in the current translation. All such
    translator output is collected into a program image which contains
    information needed for execution in its execution environment.
>
I don't see anything about required CPU instructions.

I don't see anything about /removing/ instructions that have to be
there according to the semantic analysis performed in order to
translate those units from phases 1 - 7, and that can be confirmed
to be present with a test harness.

--
TXR Programming Language: http://nongnu.org/txr
Cygnal: Cygwin Native Application Library: http://kylheku.com/cygnal
Mastodon: @Kazinator@mstdn.ca