Re: Adding Older Versions of GCC To The Tool Chain ... safely?!?!

Rainer Weikusat <rweikusat@xxxxxxxxxxx> writes:

Måns Rullgård <mans@xxxxxxxxx> writes:
Rainer Weikusat <rweikusat@xxxxxxxxxxx> writes:

[...]

The theory here is that such a check would be used to check for
overflow, which is obviously non-sense, since most buffers are not
aligned with the end of the address space.

That Heise has managed to come up with a wrong code example
does not change the underlying issue. A 'real' this would be used
would be adding two signed integers, testing that the result would be
larger than the first value and smaller than a third one, usually
giving some maximum size. At least some versions of Linux, of
MIT-Kerberos and of OpenSSL have been using such checks.

The original "vulnerability" report, not just the Heise article, uses
the flawed example.

Which changes exactly nothing, assuming it is true.

It invalidates your assertion that "Heise has managed to come up with"
something.

A test like that can be used to check for integer overflow in an
unsigned addition, where the wraparound will produce a smaller
value.

There is by definition (C) no such thing as 'an unsigned overflow',
because (C) unsigned arithmetic operates on 'mod N' (N being one more
than the maximum representable value), which is a different set than
'the set of integers >= 0'.

Fine, so what would you have me call the case where the sum of two
unsigned numbers is greater than the maximum value for their type?

The operation + is an operation defined on certain sets of integers.
The set of 'integers modulo N' is such a set and + has different
properties when defined on this set than it has when defined on, eg,
the set integers >= 0.

Show me where the C standard defines the + operator to use modulus
arithmetic. In fact, it says something quite different. First we
have section 2.6.5 Types, where paragraph 9, second sentence reads
thus:

A computation involving unsigned operands can never overflow,
because a result that cannot be represented by the resulting
unsigned integer type is reduced modulo the number that is one
greater than the largest value that can be represented by the
resulting type.

It says that *the result* is reduced to fit. This implies that the
result, prior to the modulus reduction, is computed using normal
arithmetic. That actual hardware usually combines the two steps is
irrelevant.

Continuing with the spec, we reach 6.2.6.2 Integer types:

For signed integer types, the bits of the object representation
shall be divided into three groups: value bits, padding bits, and
the sign bit. [...] If the sign bit is one, the value shall be
modified in one of the following ways:

- the corresponding value with sign bit 0 is negated (sign and magnitude);
- the sign bit has the value -(2^N) (two's complement);
- the sign bit has the value -(2^N - 1) (one's complement).

Which of these applies is implementation-defined, as is whether the
value with sign bit 1 and all value bits zero (for the first two),
or with sign bit and all value bits 1 (for one's complement), is a
trap representation or a normal value.

Here we learn that, even on two's complement implementations, a value
with the leftmost bit 1 and the rest 0 may be a trap representation.
Again, that most hardware assigns it the value -2^N is irrelevant. It
is *allowed* to be a trap representation, so portable code needs to be
prepared to deal with this.

Next, we reach 6.3 Conversions wherein we find 6.3.1.2 Signed and
unsigned integers:

When a value with integer type is converted to another integer type
other than _Bool, if the value can be represented by the new type,
it is unchanged.

Otherwise, if the new type is unsigned, the value is converted by
repeatedly adding or subtracting one more than the maximum value
that can be represented in the new type until the value is in the
range of the new type.49)

Otherwise, the new type is signed and the value cannot be
represented in it; either the result is implementation-defined or
an implementation-defined signal is raised.

49) The rules describe arithmetic on the mathematical value, not the
value of a given type of expression.

This section only applies to type conversions, whether implicit or
explicit, and is thus irrelevant to the issue under discussion.
Nevertheless, notice that footnote 49 explicitly defines the process
for conversion to an unsigned type to be performed on mathematical
(i.e. unlimited) values, not values of some particular type.

We proceed to 6.5 Expressions, where paragraph 5 states:

If an exceptional condition occurs during the evaluation of an
expression (that is, if the result is not mathematically defined or
not in the range of representable values for its type), the behavior
is undefined.

Read that again, and note how it mentions "not in the range of
representable values for its type". What this means is, that this
clause applies when an operation produces a value outside the range of
the type of the expression (and on division by zero, etc.). In other
words, if A and B are signed integers such that the sum of their
values is greater than INT_MAX, evaluating the expression A+B invokes
undefined behaviour. For unsigned integers, the behaviour is defined
in 2.6.5.

Finally, section 6.5.6 Additive operators states that

The result of the binary + operator is the sum of the operands.

No mention of modulus arithmetic here either.

For signed addition, the result of overflow is undefined,
and can thus not be relied upon.

The C-standard states that 'either the result is
implementation-defined or an implementation defined signal
is raised' (I have quoted this in an another posting), implementation

This in reference to type conversions from an integer type to a
narrower, or from unsigned to signed of the same width.

Yet it is exactly the same part of the standard which defines the
behaviour regarding unsigned types, too.

Please see above. That section defines conversion to signed and
unsigned integer types from other integer types, nothing else.

Regarding the result of expressions, the standard says this:

If an exceptional condition occurs during the evaluation of an
expression (that is, if the result is not mathematically defined or
not in the range of representable values for its type), the behavior
is undefined.

No exceptional condition occurs during evaluation of the expression.
At worst, these two parts contradict each other, because the one you
quoted above (6.5|5) should 'magically' applies to signed integers,
despite the conversion semantics defined in 6.3.1.3|3 'because that
suits yous', while it, as magically, doesn't apply to unsigned
conversions, defined a paragraph earlier (because it presently doesn't
suit you).

You fail to see the distinction between type conversion and the
evaluation of expressions using a single type. The rules are not the
same.

The more reasonable assumption would be that this is supposed to apply
to situation where 'arithmetic exception' actually occur, not to the
implementation defined behaviour of additions.

The spec doesn't say "arithmetic exception". It says "exceptional
condition", and proceeds to define this to include integer overflow.

The behaviours assumed by GCC is neither one of possible results of a
'signed overflow', according to the three possible representations,
nor does it cause a signal to be raised.

Still wrong part of the spec.

See above.

Not to mention that the operation is well-defined on all
architectures supported by Linux and extensively relied upon in
existing code.

If it is undefined in the C standard;

You have failed to demontrate this, see above. You may have found an
error in the standard or at least one where careless wording allows an
opportunity for 'semantic terrorists' to justify some random fib of
them, eg according to you

unsigned a;
int b;

a = INT_MAX;
b = a + 1;

would be 'implementation defined behaviours' (a conversion), while

Yes.

the same operation with two int variables would be undefined behaviour

Yes.

and the same operation with two unsigned variables and UINT_MAX would
again trigger a conversion.

No. With both variables unsigned, there is no conversion, simply
because only a single type is involved.

architectures are irrelevant. Most CPUs doing something predictable
has nothing to do with the C language, and a C compiler is still
free to do whatever it chooses.

Architectures are relevant for applications, and the architectures
supported by Linux are relevant for Linux applications.

Architectures should be irrelevant to portable applications, and C
compilers exist for other operating systems than Linux.

You might want to take a look at the ST20 CPU. It does trap if
certain arithmetic operations overflow.

So, for the ST20-CPU, the effect is now 'magically' a conversion

No, still no conversion.

again, because 'an implementation defined signal is raised'

No, undefined behaviour is triggered.

--
Måns Rullgård
mans@xxxxxxxxx
.

Relevant Pages

  • Re: Adding Older Versions of GCC To The Tool Chain ... safely?!?!
    ... would be adding two signed integers, testing that the result would be ... At least some versions of Linux, ... There is by definition no such thing as 'an unsigned overflow', ... would be 'implementation defined behaviours' (a conversion), ...
    (comp.os.linux.development.apps)
  • Re: Question re. integral promotion, signed->unsigned
    ... >>Why is it OK to reinterpret a signed integral type as ... > but such a conversion isn't well defined if the value of the unsigned ... regardless of the representation of negative values. ... > While this conversion is well defined and yields the same result, ...
    (comp.lang.c)
  • Re: [LogoForum] Re: item & setItem bitwise?
    ... representation should be encoded in the "visual representation" of the ... At least in Logo. ... So in this cases there should be another way to make the conversion ... compiled by Lhogho => users will start to use more advanced technology ...
    (comp.lang.logo)
  • Re: Singles to Doubles
    ... number then we could provide some optimisation to the binary conversion ... If you're saying an internal representation of 1.11 should be ... the external representation arises, ... whether one is extending zeros in the external or internal representation. ...
    (microsoft.public.vb.general.discussion)
  • Re: canonical conversion of float/double to strings
    ... decimal string which, when converted back with Double.parseDouble, ... the specification of that conversion is constrained so ... The specification mostly states that the decimal representation ... specification which is considered as better in the comments of the bug ...
    (comp.lang.java.programmer)