473,854 Members | 1,449 Online
Bytes | Software Development & Data Engineering Community
+ Post

Home Posts Topics Members FAQ

Making Fatal Hidden Assumptions

We often find hidden, and totally unnecessary, assumptions being
made in code. The following leans heavily on one particular
example, which happens to be in C. However similar things can (and
do) occur in any language.

These assumptions are generally made because of familiarity with
the language. As a non-code example, consider the idea that the
faulty code is written by blackguards bent on foulling the
language. The term blackguards is not in favor these days, and for
good reason. However, the older you are, the more likely you are
to have used it since childhood, and to use it again, barring
specific thought on the subject. The same type of thing applies to
writing code.

I hope, with this little monograph, to encourage people to examine
some hidden assumptions they are making in their code. As ever, in
dealing with C, the reference standard is the ISO C standard.
Versions can be found in text and pdf format, by searching for N869
and N1124. [1] The latter does not have a text version, but is
more up-to-date.

We will always have innocent appearing code with these kinds of
assumptions built-in. However it would be wise to annotate such
code to make the assumptions explicit, which can avoid a great deal
of agony when the code is reused under other systems.

In the following example, the code is as downloaded from the
referenced URL, and the comments are entirely mine, including the
'every 5' linenumber references.

/* Making fatal hidden assumptions */
/* Paul Hsiehs version of strlen.
http://www.azillionmonkeys.com/qed/asmexample.html

Some sneaky hidden assumptions here:
1. p = s - 1 is valid. Not guaranteed. Careless coding.
2. cast (int) p is meaningful. Not guaranteed.
3. Use of 2's complement arithmetic.
4. ints have no trap representations or hidden bits.
5. 4 == sizeof(int) && 8 == CHAR_BIT.
6. size_t is actually int.
7. sizeof(int) is a power of 2.
8. int alignment depends on a zeroed bit field.

Since strlen is normally supplied by the system, the system
designer can guarantee all but item 1. Otherwise this is
not portable. Item 1 can probably be beaten by suitable
code reorganization to avoid the initial p = s - 1. This
is a serious bug which, for example, can cause segfaults
on many systems. It is most likely to foul when (int)s
has the value 0, and is meaningful.

He fails to make the valid assumption: 1 == sizeof(char).
*/

#define hasNulByte(x) ((x - 0x01010101) & ~x & 0x80808080)
#define SW (sizeof (int) / sizeof (char))

int xstrlen (const char *s) {
const char *p; /* 5 */
int d;

p = s - 1;
do {
p++; /* 10 */
if ((((int) p) & (SW - 1)) == 0) {
do {
d = *((int *) p);
p += SW;
} while (!hasNulByte (d)); /* 15 */
p -= SW;
}
} while (*p != 0);
return p - s;
} /* 20 */

Let us start with line 1! The constants appear to require that
sizeof(int) be 4, and that CHAR_BIT be precisely 8. I haven't
really looked too closely, and it is possible that the ~x term
allows for larger sizeof(int), but nothing allows for larger
CHAR_BIT. A further hidden assumption is that there are no trap
values in the representation of an int. Its functioning is
doubtful when sizeof(int) is less that 4. At the least it will
force promotion to long, which will seriously affect the speed.

This is an ingenious and speedy way of detecting a zero byte within
an int, provided the preconditions are met. There is nothing wrong
with it, PROVIDED we know when it is valid.

In line 2 we have the confusing use of sizeof(char), which is 1 by
definition. This just serves to obscure the fact that SW is
actually sizeof(int) later. No hidden assumptions have been made
here, but the usage helps to conceal later assumptions.

Line 4. Since this is intended to replace the systems strlen()
function, it would seem advantageous to use the appropriate
signature for the function. In particular strlen returns a size_t,
not an int. size_t is always unsigned.

In line 8 we come to a biggie. The standard specifically does not
guarantee the action of a pointer below an object. The only real
purpose of this statement is to compensate for the initial
increment in line 10. This can be avoided by rearrangement of the
code, which will then let the routine function where the
assumptions are valid. This is the only real error in the code
that I see.

In line 11 we have several hidden assumptions. The first is that
the cast of a pointer to an int is valid. This is never
guaranteed. A pointer can be much larger than an int, and may have
all sorts of non-integer like information embedded, such as segment
id. If sizeof(int) is less than 4 the validity of this is even
less likely.

Then we come to the purpose of the statement, which is to discover
if the pointer is suitably aligned for an int. It does this by
bit-anding with SW-1, which is the concealed sizeof(int)-1. This
won't be very useful if sizeof(int) is, say, 3 or any other
non-poweroftwo. In addition, it assumes that an aligned pointer
will have those bits zero. While this last is very likely in
todays systems, it is still an assumption. The system designer is
entitled to assume this, but user code is not.

Line 13 again uses the unwarranted cast of a pointer to an int.
This enables the use of the already suspicious macro hasNulByte in
line 15.

If all these assumptions are correct, line 19 finally calculates a
pointer difference (which is valid, and of type size_t or ssize_t,
but will always fit into a size_t). It then does a concealed cast
of this into an int, which could cause undefined or implementation
defined behaviour if the value exceeds what will fit into an int.
This one is also unnecessary, since it is trivial to define the
return type as size_t and guarantee success.

I haven't even mentioned the assumption of 2's complement
arithmetic, which I believe to be embedded in the hasNulByte
macro. I haven't bothered to think this out.

Would you believe that so many hidden assumptions can be embedded
in such innocent looking code? The sneaky thing is that the code
appears trivially correct at first glance. This is the stuff that
Heisenbugs are made of. Yet use of such code is fairly safe if we
are aware of those hidden assumptions.

I have cross-posted this without setting follow-ups, because I
believe that discussion will be valid in all the newsgroups posted.

[1] The draft C standards can be found at:
<http://www.open-std.org/jtc1/sc22/wg14/www/docs/>

--
"If you want to post a followup via groups.google.c om, don't use
the broken "Reply" link at the bottom of the article. Click on
"show options" at the top of the article, then click on the
"Reply" at the bottom of the article headers." - Keith Thompson
More details at: <http://cfaj.freeshell. org/google/>
Also see <http://www.safalra.com/special/googlegroupsrep ly/>

Mar 6 '06
351 13236
In article <sl************ **********@rand om.yi.org> Jordan Abel <ra*******@gmai l.com> writes:
On 2006-03-23, Michael Wojcik <mw*****@newsgu y.com> wrote:

....
No, there is not. The "trap" (a machine check, actually) can be
caught, and it can be responded to, by application code; but ignoring
it is not one of the options.


You can't "catch it and do nothing"? What are you expected to _do_ about
an invalid or protected address being loaded [not dereferenced], anyway?
What _can_ you do, having caught the machine check? What responses are
typical?


Consider:
int a[10], *p;

p = a - 1;
p = p + 1;

The first line of code traps, you want to ignore that trap, so what
is p after that line of code? Nothing useful, because nothing was
assigned to it. Well, the second line also traps, but what is the
sense in doing nothing here? If you do nothing p is still just as
undefined as before that line.
--
dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924131
home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/
Mar 23 '06 #291
On Thu, 23 Mar 2006 12:33:51 +0000, Dik T. Winter wrote:
Consider:
int a[10], *p;

p = a - 1;
p = p + 1;
How about:

int a[10];
foo(a + 1);

where

foo(int *p)
{
p -= 1;
/* do something with p[0]..p[9] */
}
The first line of code traps, you want to ignore that trap, so what
is p after that line of code? Nothing useful, because nothing was
assigned to it. Well, the second line also traps, but what is the
sense in doing nothing here? If you do nothing p is still just as
undefined as before that line.


Does p -= 1 still trap, in the first line of foo, given the way that it's
called in the main routine?

If not, how could foo() be compiled in a separate unit, in the AS/400
scenario that you described earlier?

If it does trap, why? It's not forming an "illegal" pointer, even for the
AS/400 world.

If it doesn't trap, why should p -= 1 succeed, but p -= 2 fail?

What if my algorithm's natural expression is to refer to p[0]..p[-9], and
expects to be handed a pointer to the last element of a[]?

The significant difference of C, to other languages (besides the
assembly language of most architectures) is that you can form, store, and
use as arguments pointers into the middle of "objects". Given that
difference, the memory model is obvious, and the constraint imposed by the
"undefined" elements of the standard (laboured in this thread)
unreasonably onerous. IMO. YMMV.

Cheers,

--
Andrew

Mar 23 '06 #292
In article <pa************ *************** *@areilly.bpc-users.org> Andrew Reilly <an************ *@areilly.bpc-users.org> writes:
On Thu, 23 Mar 2006 12:33:51 +0000, Dik T. Winter wrote: .... How about:
int a[10];
foo(a + 1);
where

foo(int *p)
{
p -= 1;
/* do something with p[0]..p[9] */
} .... Does p -= 1 still trap, in the first line of foo, given the way that it's
called in the main routine?
Why should it?
If not, how could foo() be compiled in a separate unit, in the AS/400
scenario that you described earlier?
It was not me who described it, but I see no reason why that should be
impossible. Consider a pointer as a combination of the indication of a
region and an index into that region.
If it does trap, why? It's not forming an "illegal" pointer, even for the
AS/400 world.
It does not trap.
If it doesn't trap, why should p -= 1 succeed, but p -= 2 fail?
Because the latter creates an invalid pointer.
What if my algorithm's natural expression is to refer to p[0]..p[-9], and
expects to be handed a pointer to the last element of a[]?
No problem.
The significant difference of C, to other languages (besides the
assembly language of most architectures) is that you can form, store, and
use as arguments pointers into the middle of "objects".


That was also possible in Algol 68. But I see no problem with it on
a machine like the AS/400.

(As an example from Algol 68:
'int' a[1:10, 1:10, 1:10];
'ref' 'int' aa = a[2:6, 3:7,4];
the latter points to a two-dimensional slice...)
--
dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924131
home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/
Mar 23 '06 #293
On 2006-03-23, Dik T. Winter <Di********@cwi .nl> wrote:
In article <sl************ **********@rand om.yi.org> Jordan Abel <ra*******@gmai l.com> writes:
> On 2006-03-23, Michael Wojcik <mw*****@newsgu y.com> wrote: ...
> > No, there is not. The "trap" (a machine check, actually) can be
> > caught, and it can be responded to, by application code; but ignoring
> > it is not one of the options.

>
> You can't "catch it and do nothing"? What are you expected to _do_ about
> an invalid or protected address being loaded [not dereferenced], anyway?
> What _can_ you do, having caught the machine check? What responses are
> typical?


Consider:
int a[10], *p;

p = a - 1;
p = p + 1;

The first line of code traps, you want to ignore that trap, so what is
p after that line of code? Nothing useful, because nothing was
assigned to it.


Why not?

I guess my point is, why are you not allowed to hold an address in a
register regardless of whether you would be allowed to access the memory
at that address? That seems like a stupid architecture in the first
place. It's not "security", it's bad design masquerading as security. If
the goal is to protect an area of memory from being accessed, block
programs from _accessing_ it, not from talking about it.
Well, the second line also traps, but what is the sense in doing
nothing here? If you do nothing p is still just as undefined as
before that line.


Only under the current standard. Using the fact that it's undefined to
justify it being undefined is begging the question.
Mar 23 '06 #294
Jordan Abel <ra*******@gmai l.com> writes:
On 2006-03-23, Dik T. Winter <Di********@cwi .nl> wrote: [...]
Consider:
int a[10], *p;

p = a - 1;
p = p + 1;

The first line of code traps, you want to ignore that trap, so what is
p after that line of code? Nothing useful, because nothing was
assigned to it.


Why not?


Because the trap occurred before the value was assigned to p.
I guess my point is, why are you not allowed to hold an address in a
register regardless of whether you would be allowed to access the memory
at that address?
Because it catches errors as early as possible.

Why do you want to create an address that you're not allowed to
dereference?
That seems like a stupid architecture in the first
place. It's not "security", it's bad design masquerading as security. If
the goal is to protect an area of memory from being accessed, block
programs from _accessing_ it, not from talking about it.


Presumably it does both.

The C standard doesn't require a trap when you create an invalid
address. It merely declines to define the semantics. If you think
the AS/400 architecture is stupid, that's your privilege. If you want
to write code that creates addresses outside the bounds of an array,
nobody is going to stop you; you'll just have to look somewhere other
than the C standard for guarantees that your code will behave the way
you want it to.

Your argument, I suppose, is that the C standard *should* guarantee
the behavior. That may or may not be a good idea -- but I think we
can guarantee that nothing is going to change until and unless someone
comes up with a concrete proposal. I'm not going to do it myself,
because I'm satisfied with the standard as it is (at least in this
area). If you do so, you can expect a great deal of argument about
what behavior should be guaranteed and what should be left
implementation-defined (or even undefined).

--
Keith Thompson (The_Other_Keit h) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.
Mar 23 '06 #295
On Thu, 23 Mar 2006 22:00:14 +0000, Keith Thompson wrote:
Because it catches errors as early as possible.
No, it doesn't. It breaks idioms where no error or illegal access would
occur.
Why do you want to create an address that you're not allowed to
dereference?
Because the ability to do so is implied by the syntax of pointer
arithmetic.

This restriction (undefined semantics IS a restriction) makes
pointer-walking versions of algorithms second-class citizens to otherwize
equivalent indexed versions of algorithms.

void
foo(int *p, int n)
{
for (; --n >= 0;)
p[n] = n;
}

is "legal" and "defined" on all architectures, but the equivalent with a
pointer cursor isn't:

void
foo(int *p, int n)
{
p += n-1;
for (; --n >= 0;)
*p-- = n;
}

I suppose that this is the root of my surprise and annoyance on
discovering what the standard says. These versions *should* be
equivalent, and equivalently well-defined.
The C standard doesn't require a trap when you create an invalid
address. It merely declines to define the semantics. If you think the
AS/400 architecture is stupid, that's your privilege. If you want to
write code that creates addresses outside the bounds of an array, nobody
is going to stop you; you'll just have to look somewhere other than the
C standard for guarantees that your code will behave the way you want it
to.
Fine. Where can I find that? Can we make a sub-standard that includes
the common semantics for all "normal-looking" architectures, so that our
code can rely on them, please?
Your argument, I suppose, is that the C standard *should* guarantee the
behavior. That may or may not be a good idea -- but I think we can
guarantee that nothing is going to change until and unless someone comes
up with a concrete proposal. I'm not going to do it myself, because I'm
satisfied with the standard as it is (at least in this area). If you do
so, you can expect a great deal of argument about what behavior should
be guaranteed and what should be left implementation-defined (or even
undefined).


Yeah, but I expect most of that argument to go away, as all of the AS/400
wanna-be C coders drift off to use Java or .NET instead, leaving C a niche
language, doing the low-level systems programming that it was designed for.

--
Andrew

Mar 23 '06 #296
On Thu, 23 Mar 2006 14:16:41 +0000, Dik T. Winter wrote:
In article <pa************ *************** *@areilly.bpc-users.org> Andrew Reilly <an************ *@areilly.bpc-users.org> writes:
> On Thu, 23 Mar 2006 12:33:51 +0000, Dik T. Winter wrote:

...
> How about:
> int a[10];
> foo(a + 1);
> where
>
> foo(int *p)
> {
> p -= 1;
> /* do something with p[0]..p[9] */
> }

...
> Does p -= 1 still trap, in the first line of foo, given the way that it's
> called in the main routine?


Why should it?


It shouldn't. But if the comment (and the code) went off to do somthing
with p[1]..p[10], and the main line passed a, rather than a+1, you're
saying that it would trap. The coder, therefore, can't use a perfectly
reasonalble idiom (base shifting), even though the syntax, and the
semantics implied by that syntax, allow it.
> If not, how could foo() be compiled in a separate unit, in the AS/400
> scenario that you described earlier?


It was not me who described it, but I see no reason why that should be
impossible. Consider a pointer as a combination of the indication of a
region and an index into that region.


I *was* considering a pointer as a combination of the indication of a
region and an index into that region. In C, that index is a *signed*
integer. If the hardware has a problem with that, and causes a trap if
the index component is set to a negative value, then the implementation
should go to some lengths to preserve the impression that it works anyway.
> If it does trap, why? It's not forming an "illegal" pointer, even
> for the AS/400 world.


It does not trap.


But the author of the foo() function (as modified above) can't know that.
> If it doesn't trap, why should p -= 1 succeed, but p -= 2 fail?


Because the latter creates an invalid pointer.


But the author of foo() can't know that. This argument started because it
was pointed out that p -= 1 produced undefined behaviour. It is clear
that the behaviour *could* be very well defined. That it isn't is the
root of the discussion.
> What if my algorithm's natural expression is to refer to p[0]..p[-9],
> and expects to be handed a pointer to the last element of a[]?


No problem.


It is a problem if those elements are accessed with a walking pointer,
rather than with an array index; something that the syntax of C and
most of it's idioms and historical code implies are equivalent.

--
Andrew

Mar 23 '06 #297
Andrew Reilly <an************ *@areilly.bpc-users.org> writes:
On Thu, 23 Mar 2006 22:00:14 +0000, Keith Thompson wrote:
Because it catches errors as early as possible.


No, it doesn't. It breaks idioms where no error or illegal access would
occur.
Why do you want to create an address that you're not allowed to
dereference?


Because the ability to do so is implied by the syntax of pointer
arithmetic.


No, it's not implied by the syntax, any more than the ability to
compute MAX_INT + 1 is implied by the syntax of addition.

[snip]
The C standard doesn't require a trap when you create an invalid
address. It merely declines to define the semantics. If you think the
AS/400 architecture is stupid, that's your privilege. If you want to
write code that creates addresses outside the bounds of an array, nobody
is going to stop you; you'll just have to look somewhere other than the
C standard for guarantees that your code will behave the way you want it
to.


Fine. Where can I find that? Can we make a sub-standard that includes
the common semantics for all "normal-looking" architectures, so that our
code can rely on them, please?


Sure, go ahead.

--
Keith Thompson (The_Other_Keit h) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.
Mar 24 '06 #298
"Andrew Reilly" <an************ *@areilly.bpc-users.org> wrote in message
news:pa******** *************** *****@areilly.b pc-users.org...
On Thu, 23 Mar 2006 22:00:14 +0000, Keith Thompson wrote:
The C standard doesn't require a trap when you create an invalid
address. It merely declines to define the semantics. If you think the
AS/400 architecture is stupid, that's your privilege. If you want to
write code that creates addresses outside the bounds of an array, nobody
is going to stop you; you'll just have to look somewhere other than the
C standard for guarantees that your code will behave the way you want it
to.


Fine. Where can I find that? Can we make a sub-standard that includes
the common semantics for all "normal-looking" architectures, so that our
code can rely on them, please?


The problem is that there's really no such thing as a "normal-looking"
architecture. Every implementation differs in at least a few fundamental
things you'd find it useful to nail down, so to provide enough detail to be
meaningful your sub-standard would basically be defining the behavior of a
particular implementation.

Just about the only thing that all modern machines agree on is CHAR_BIT == 8
(and I bet someone will dispute that). Ints, pointers, address space
semantics, etc. are all up for grabs, and that's a good thing -- it allows
systems to evolve in useful ways instead of locking us into something that,
while appearing optimal today, is not likely to be tomorrow.

If you disagree, please list all of the various currently-undefined
behaviors you want to define and what implementations conform to your spec.
Who knows, ISO might adopt it...

S

--
Stephen Sprunk "Stupid people surround themselves with smart
CCIE #3723 people. Smart people surround themselves with
K5SSS smart people who disagree with them." --Aaron Sorkin

*** Free account sponsored by SecureIX.com ***
*** Encrypt your Internet usage with a free VPN account from http://www.SecureIX.com ***
Mar 24 '06 #299
On 2006-03-24, Stephen Sprunk <st*****@sprunk .org> wrote:
"Andrew Reilly" <an************ *@areilly.bpc-users.org> wrote in message
news:pa******** *************** *****@areilly.b pc-users.org...
On Thu, 23 Mar 2006 22:00:14 +0000, Keith Thompson wrote:
The C standard doesn't require a trap when you create an invalid
address. It merely declines to define the semantics. If you think the
AS/400 architecture is stupid, that's your privilege. If you want to
write code that creates addresses outside the bounds of an array, nobody
is going to stop you; you'll just have to look somewhere other than the
C standard for guarantees that your code will behave the way you want it
to.


Fine. Where can I find that? Can we make a sub-standard that includes
the common semantics for all "normal-looking" architectures, so that our
code can rely on them, please?


The problem is that there's really no such thing as a "normal-looking"
architecture. Every implementation differs in at least a few
fundamental things you'd find it useful to nail down, so to provide
enough detail to be meaningful your sub-standard would basically be
defining the behavior of a particular implementation.

Just about the only thing that all modern machines agree on is
CHAR_BIT == 8 (and I bet someone will dispute that). Ints, pointers,
address space semantics, etc. are all up for grabs, and that's a good
thing -- it allows systems to evolve in useful ways instead of locking
us into something that, while appearing optimal today, is not likely
to be tomorrow.

If you disagree, please list all of the various currently-undefined
behaviors you want to define and what implementations conform to your
spec. Who knows, ISO might adopt it.


How about defining passing a positive signed int to printf %x, %u, %o?,
or an unsigned int < INT_MAX to %d? That doesn't seem too unreasonable.
It works fine on every existing platform, as far as I know, and it is
currently required to work for user-created variadic functions.
Mar 24 '06 #300

This thread has been closed and replies have been disabled. Please start a new discussion.

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.