Re: A Famous Security Bug

On 22/03/2024 16:50, Kaz Kylheku wrote:

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

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

On 2024-03-21, David Brown <david.brown@hesbynett.no> wrote:

On 20/03/2024 19:54, Kaz Kylheku wrote:

On 2024-03-20, Stefan Ram <ram@zedat.fu-berlin.de> wrote:

    A "famous security bug":
>
void f( void )
{ char buffer[ MAX ];
    /* . . . */
    memset( buffer, 0, sizeof( buffer )); }
>
    . Can you see what the bug is?

>
I don't know about "the bug", but conditions can be identified under
which that would have a problem executing, like MAX being in excess
of available automatic storage.
>
If the /*...*/ comment represents the elision of some security sensitive
code, where the memset is intended to obliterate secret information,
of course, that obliteration is not required to work.
>
After the memset, the buffer has no next use, so the all the assignments
performed by memset to the bytes of buffer are dead assignments that can
be elided.
>
To securely clear memory, you have to use a function for that purpose
that is not susceptible to optimization.
>
If you're not doing anything stupid, like link time optimization, an
external function in another translation unit (a function that the
compiler doesn't recognize as being an alias or wrapper for memset)
ought to suffice.

>
Using LTO is not "stupid".  Relying on people /not/ using LTO, or not
using other valid optimisations, is "stupid".

>
LTO is a nonconforming optimization. It destroys the concept that
when a translation unit is translated, the semantic analysis is
complete, such that the only remaining activity is resolution of
external references (linkage), and that the semantic analysis of one
translation unit deos not use information about another translation
unit.
>
This has not yet changed in last April's N3096 draft, where
translation phases 7 and 8 are:
>
   7. White-space characters separating tokens are no longer significant.
      Each preprocessing token is converted into a token. The resulting
      tokens are syntactically and semantically analyzed and translated
      as a translation unit.
>
   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.
>
and before that, the Program Structure section says:
>
   The separate translation units of a program communicate by (for
   example) calls to functions whose identifiers have external linkage,
   manipulation of objects whose identifiers have external linkage, or
   manipulation of data files. Translation units may be separately
   translated and then later linked to produce an executable program.
>
LTO deviates from the the model that translation units are separate,
and the conceptual steps of phases 7 and 8.

[...]
>
Link time optimization is as valid as cross-function optimization *as
long as* it doesn't change the defined behavior of the program.

 It always does; the interaction of a translation unit with another
is an externally visible aspect of the C program.

The C standards don't define a term "externally visible".  They define "observable behaviour", and require that a conforming implementation generates a program that matches the "observable behaviour".  This is in 5.1.2.2.2p6.  Interaction between translation units is not part of the observable behaviour of a program, because it is not relevant to the concept of /running/ a program - it is only relevant when translating the source to the program image.
Thus the "as if" rules apply - the compiler can do whatever it wants - up to and including asking ChatGPT for an exe file - as long as the result is a /program/ that gives the same "observable behaviour" as you would get from an abstract machine.
You should read the footnotes to 5.1.1.2 "Translation phases". Footnotes are not normative, but they are helpful in explaining the meaning of the text.  They note that compilers don't have to follow the details of the translation phases, and that source files, translation units, and translated translation units don't have to have one-to-one correspondences.
The standard also does not say what the output of "translation" is - it does not have to be assembly or machine code.  It can happily be an internal format, as used by gcc and clang/llvm.  It does not define what "linking" is, or how the translated translation units are "collected into a program image" - combining the partially compiled units, optimising, and then generating a program image is well within that definition.

(That can be inferred
from the rules which forbid semantic analysis across translation
units, only linkage.)

The rules do not forbid semantic analysis across translation units - they merely do not /require/ it.  You are making an inference without any justification that I can see.

 That's why we can have a real world security issue caused by zeroing
being optimized away.

No, it is not.  We have real-world security issues for all sorts of reasons, including people mistakenly thinking they can force particular types of code generation by calling functions in different source files.
(To be clear here, before LTO became common, that was a strategy that worked.  There is a long history in C programming of dilemmas between writing code that you know works efficiently on current tools, or writing code that you know is guaranteed correct by the standards but is inefficient with current tools.)

 The rules spelled out in ISO C allow us to unit test a translation
unit by linking it to some harness, and be sure it has exactly the
same behaviors when linked to the production program.
 

No, they don't.
If the unit you are testing calls something outside that unit, you may get different behaviours when testing and when used in production.  The only thing you can be sure of from testing is that if you find a bug during testing, you have a bug in the code.  You can never use testing to be sure that the code works (with the exception of exhaustive testing of all possible inputs, which is rarely practical).

If I have some translation unit in which there is a function foo, such
that when I call foo, it then calls an external function bar, that's
observable.

5.1.2.2.1p6 lists the three things that C defines as "observable behaviour".  Function calls - internal or external - are not amongst these.

I can link that unit to a program which supplies bar,
containing a printf call, then call foo and verify that the printf call
is executed.

Yes, you can.  The printf call - or, more exactly, the "input and output dynamics" - are observable behaviour.  The call to "bar", however, is not.
The compiler, when compiling the source of "foo", will include a call to "bar" when it does not have the source code (or other detailed semantic information) for "bar" available at the time.  But you are mistaken to think it does so because the call is "observable" or required by the C standard.  It does so because it cannot prove that /running/ the function "bar" contains no observable behaviour, or otherwise affects the observable behaviour of the program.  The compiler cannot skip the call unless it can be sure it is safe to do so - and if it knows nothing about the implementation of "bar", it must assume the worst.
Sometimes the compiler may have additional information - such as if it is declared the gcc "const" or "pure" attributes (or the standardised "unsequenced" and "reproducible" attributes in the draft for the next C version after C23).  This may allow a compiler to re-arrange calls, duplicating them, eliminating them, or re-ordering them in various ways.   (The C2y draft includes running such functions once at startup for each input value, and preserving the results for later use, as a permissible optimisation.  It does this without having changed the description of translation phases or observable behaviour.  But of course it is still just a draft.)

 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.

No, we can't - see above.  Nothing in the C standards forbids any additional analysis, or using other information in code generation.

 

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.
 

Can you give examples?
You already mentioned "-fast-math" (and by implication, its various subflags in gcc, clang and icc).  These are clearly documented as allowing some violations of the C standards (and not least, the IEEE floating point standards, which are stricter than those of C).

If you have LTO turned on, you might be programming in GNU C or Clang C
or whatever, not standard C.

You might be programming in GNU C.  You might be programming in a standard C version (modulo bugs in the compiler).

 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.
 

(While I don't much like an "appeal to authority" argument, I think it's worth noting that the major C / C++ compilers, gcc, clang/llvm and MSVC, all support link-time optimisation.  They also all work together with both the C and C++ standards committees.  It would be quite the scandal if there were any truth in your claims and these compiler vendors were all breaking the rules of the languages they help to specify!)