How to make (ptr + len) > lim safe?

[Michael B Allen]

I like to use limit pointers as sentinels when working on buffers
of data. Meaning I use ptr < lim where ptr and lim are both pointers
rather than n 0 to determine if it is safe to proceed writing to that
location. The rationale is that it is simpler and thus safer because
you're not constantly recomputing integer n.

However, I've run into a case where this fails and I'd like to know what
the experts would do.

If I want to precompute if a pointer plus a length will exceed the limit
pointer I have a condition that can easily fail. There are two possible
expressions:

1) Add the length to the pointer and check to see if it exceeds the
limit like:

char *ptr, *lim;
int len;

if ((ptr + len) >= lim)
return -1;

This is not ok because len could be so large that the computed pointer
value becomes negative and the expression evaluates to false.

2) Compute the available space between the limit and pointer and compare
that to the required length:

if ((lim - ptr) =< len)
return -1;

This is also not ok because if lim is (char *)-1 and ptr is relatively
small, the computed space is still negative and thus the condition is
false. I'm not sure if this will happen on 32 bit platforms but on 64
bit it certainly can.

Note that I always also check to make sure lim != NULL and that ptr < lim.

So given any values for lim, ptr and len except lim != NULL and ptr <
lim, what expression would you use to safely ensure that ptr + len is
less than lim?

Mike

[Jack Klein]

On Wed, 16 Jan 2008 23:02:12 -0500, Michael B Allen <io****@gmail.com>
wrote in comp.lang.c:

I like to use limit pointers as sentinels when working on buffers
of data. Meaning I use ptr < lim where ptr and lim are both pointers
rather than n 0 to determine if it is safe to proceed writing to that
location. The rationale is that it is simpler and thus safer because
you're not constantly recomputing integer n.

However, I've run into a case where this fails and I'd like to know what
the experts would do.

If I want to precompute if a pointer plus a length will exceed the limit
pointer I have a condition that can easily fail. There are two possible
expressions:

1) Add the length to the pointer and check to see if it exceeds the
limit like:

char *ptr, *lim;
int len;

The real problem here is that you are using the wrong integer type for
len. Use a size_t, which is the natural size for expressing object
sizes.

Even if you have to deal with a signed int type, assign it to a
size_t. If the signed int value is negative, it will convert to a
very large size_t value.

Then check the size_t value against a maximum value, which you decide
on. If and only if the size_t value (which is unsigned) is within
your limits should you apply it to the pointer.

if ((ptr + len) >= lim)
return -1;

This is not ok because len could be so large that the computed pointer
value becomes negative and the expression evaluates to false.

Pointers are not signed values, they don't come in "negative" and
"positive".

2) Compute the available space between the limit and pointer and compare
that to the required length:

if ((lim - ptr) =< len)
return -1;

This is also not ok because if lim is (char *)-1 and ptr is relatively
small, the computed space is still negative and thus the condition is
false. I'm not sure if this will happen on 32 bit platforms but on 64
bit it certainly can.

Note that I always also check to make sure lim != NULL and that ptr < lim.

So given any values for lim, ptr and len except lim != NULL and ptr <
lim, what expression would you use to safely ensure that ptr + len is
less than lim?

As I said above, my first step would be to convert the length to
size_t, an unsigned type, and check that against a predefined maximum.

--
Jack Klein
Home: http://JK-Technology.Com
FAQs for
comp.lang.c http://c-faq.com/
comp.lang.c++ http://www.parashift.com/c++-faq-lite/
alt.comp.lang.learn.c-c++
http://www.club.cc.cmu.edu/~ajo/docs/FAQ-acllc.html

[Peter Nilsson]

James Kuyper <[e-mail]:

Michael B Allen wrote:

Note that I always also check to make sure lim != NULL
and that ptr < lim.

However, if ptr and lim both point into or one past the end
of the same array, and if ptr < lim, then lim-ptr has to be
positive, and that is something the standard does say.

Chapter and verse please.

Not directly, but by inference from what it says about the
binary '-' operator and the '<' operator, when acting on
pointers:

6.5.6p9: "When two pointers are subtracted, both shall
point to elements of the same array object, or one past
the last element of the array object; the result is the
difference of the subscripts of the two array
elements."

6.5.8p5: "... pointers to array elements with larger
subscript values compare greater than pointers to
elements of the same array with lower subscript values."

Since ptr<lim, lim points to an array element with a
larger subscript value than the one ptr points at. The
difference of the pointers is equal to the difference
of the subscripts, and therefore has to be positive.

There is no requirement that PTRDIFF_MAX >= SIZE_MAX. So,
what is the value of (ptr + PTRDIFF_MAX + 1 - ptr) in the
case where the pointer additions are valid?

--
Peter

[William Ahern]

Michael B Allen <io****@gmail.comwrote:
<snip>

1) Add the length to the pointer and check to see if it exceeds the
limit like:

char *ptr, *lim;
int len;

if ((ptr + len) >= lim)
return -1;

This is not ok because len could be so large that the computed pointer
value becomes negative and the expression evaluates to false.

Where are you getting len? The scenario for me might be something like:

size_t fill(unsigned char *dst, size_t dstlen) {
unsigned char *pos = dst;
unsigned char *end = dst + dstlen;

while (pos < end) {
*(pos++) = '.';
}

return pos - dst;
}

Point being, if the caller hasn't written buggy code I can depend on the
pointer arithmetic being well defined. If dstlen is "too long" (or, if I
were using a signed integerr, negative), clearly the caller is passing
erroneous information about their output buffer, and there's nothing I can
do about that.

2) Compute the available space between the limit and pointer and compare
that to the required length:

if ((lim - ptr) =< len)
return -1;

This is also not ok because if lim is (char *)-1 and ptr is relatively
small, the computed space is still negative and thus the condition is
false. I'm not sure if this will happen on 32 bit platforms but on 64
bit it certainly can.

A negative pointer doesn't make sense. But, related to above, if lim was
calculated improperly, that's simply a bug, and one of a sort not restricted
to this type of usage.

Note that I always also check to make sure lim != NULL and that ptr < lim.

The former test isn't necessary. All that matters is if lim >= ptr and ptr <
lim (and that ptr points to a valid object). Testing for a NULL pointer is
[hopefully] superfluous and also an example of testing for the wrong
condition: it matters not that lim is NULL, but whether ptr is NULL. And in
any event, if both ptr and lim are NULL you're okay, as long as the
relationship holds.

So given any values for lim, ptr and len except lim != NULL and ptr <
lim, what expression would you use to safely ensure that ptr + len is
less than lim?

The real problem with using pointers this way is that, technically speaking,
you cannot do arbitrary pointer arthmetic this way if the calculations would
be undefined. On a segmented architecture if len is greater than the size of
the actual object, you get undefined behavior by computing and comparing
such a pointer. Likewise if you, as I often did, incremented a positional
pointer past [one past] the end of the object. In Unix these operations are
_better_ defined (though you obviously run into issues with overflow) and
usually more forgiving, because they make other requirements beyond the C
specification, such as a flat memory model. But I have run into debuggers
which have depended on the letter of the C specification, and it became
enough of a pain that I'm more careful about using pointers this way.

Instead, I'm increasingly more likely to use a position "pointer" which is
simply an integer counter, and instead of comparing pointers I compare the
counter with a length paramater. (Using unsigned arithmetic, of course.)
This way the counter can extend beyond the length, for instance if I want to
continuing calculating the output length of an operation, even if I've run
out of destination buffer space. (Cf snprintf). This may end up in slightly
additional CPU work, because I may need to recompute pointers more often (as
opposed to incrementing a pointer, which can also act as the counter). Or it
may not.

[Richard Tobin]

In article <20****************************@gmail.com>,
Michael B Allen <io****@gmail.comwrote:

>1) Add the length to the pointer and check to see if it exceeds the
limit like:

char *ptr, *lim;
int len;

if ((ptr + len) >= lim)
return -1;

There's no portable way to do this. You just can't safely computer
ptr+len if if might be outside the object (except for the special case
of one-beyond-the-end).

In practice, if you have "flat" pointers, you can do tests like this,
but because of wraparound you would need to compare against the lower
limit as well.

But the whole idea is misguided. You should not be relying on this
sort of check. After all, if people are handing you bogus pointers,
how can you be sure that the ones in range are correct?

-- Richard
--
:wq

[James Kuyper]

Peter Nilsson wrote:

James Kuyper <[e-mail]:

>Michael B Allen wrote:

>>Note that I always also check to make sure lim != NULL
and that ptr < lim.

However, if ptr and lim both point into or one past the end
of the same array, and if ptr < lim, then lim-ptr has to be
positive, and that is something the standard does say.

Chapter and verse please.

Already provided:

>Not directly, but by inference from what it says about the
binary '-' operator and the '<' operator, when acting on
pointers:

6.5.6p9: "When two pointers are subtracted, both shall
point to elements of the same array object, or one past
the last element of the array object; the result is the
difference of the subscripts of the two array
elements."

6.5.8p5: "... pointers to array elements with larger
subscript values compare greater than pointers to
elements of the same array with lower subscript values."

Since ptr<lim, lim points to an array element with a
larger subscript value than the one ptr points at. The
difference of the pointers is equal to the difference
of the subscripts, and therefore has to be positive.

There is no requirement that PTRDIFF_MAX >= SIZE_MAX. So,
what is the value of (ptr + PTRDIFF_MAX + 1 - ptr) in the
case where the pointer additions are valid?

It is a negative value, and therefore a value that an implementation
should never permit to be the result of subtracting two pointers into
the same array, if the left operand compares greater than the right
operand. ptrdiff_t must be chosen to be large enough to ensure the
behavior required by 6.5.6p9 and 6.5.8p5.

Subscripts into an array are only allowed to be positive, regardless of
the value of PTRDIFF_MAX, and therefore the difference between a larger
subscript and a smaller one can never be negative. The description of
the binary '-' operator acting on pointers doesn't say that the result
is "the difference of the subscripts, after conversion to ptrdiff_t". It
just says that it's the difference of the subscripts.

[Michael B Allen]

On Thu, 17 Jan 2008 06:40:40 -0500
pete <pf*****@mindspring.comwrote:

Michael B Allen wrote:

int
copy_or_else(char *str, char *buf, char *blim)
{
size_t len = strlen(str) + 1;

if (buf == NULL || blim <= buf)
return -1;

<snip>

Concerning buf and blim in copy_or_else only, is the above code legal?

No.
If (blim < buf) then the program isn't defined either.

Object pointers can only have 4 kinds of values:
1 object address
2 one past object address
3 null
4 indeterminate

Relational operators

>= < <=

are only defined for pointers
which point to the same object, or one past.

Hi Pete,

So what you're saying is that if someone can supply an invalid value
wrt to the standard, we should make no attempt to check for it?

If the user supplies a blim pointer that points to an element of buf
(or one after the end of buf) then is the above code legal?

If yes, then the means and end are the same so why NOT at least make an
attempt to check possible indeterminate values?

It seems to me that what you're saying only reenforces the idea of using
a limit pointer because it gives the function an opportunity to validate
the value.

Mike

[Paul Hsieh]

On Jan 16, 8:02 pm, Michael B Allen <[e-mail]:

I like to use limit pointers as sentinels when working on buffers
of data. Meaning I use ptr < lim where ptr and lim are both pointers
rather than n 0 to determine if it is safe to proceed writing to
that location. The rationale is that it is simpler and thus safer
because you're not constantly recomputing integer n.

However, I've run into a case where this fails and I'd like to know
what the experts would do.

If I want to precompute if a pointer plus a length will exceed the
limit pointer I have a condition that can easily fail. There are two
possible expressions:

1) Add the length to the pointer and check to see if it exceeds the
limit like:

char *ptr, *lim;
int len;

if ((ptr + len) >= lim)
return -1;

This is not ok because len could be so large that the computed
pointer value becomes negative and the expression evaluates to false.

2) Compute the available space between the limit and pointer and
compare that to the required length:

if ((lim - ptr) =< len)
return -1;

This is also not ok because if lim is (char *)-1 and ptr is
relatively small, the computed space is still negative and thus the
condition is false. I'm not sure if this will happen on 32 bit
platforms but on 64 bit it certainly can.

Note that I always also check to make sure lim != NULL and that ptr <
lim.

So given any values for lim, ptr and len except lim != NULL and ptr <
lim, what expression would you use to safely ensure that ptr + len is
less than lim?

It can't be done perfectly in a single comparison. Assuming wrap
around semantics for pointer values and sizeof(int) <= sizeof
(intptr_t) what you want is:

intptr_t diff = (intptr_t) (lim - ptr);
if (ptr < lim) {
if (diff 0 && len >= diff) return -1;
} else {
if (diff <= 0 && len >= diff) return -1;
}

The point being that len is a signed integer, and *cannot* cause ptr
+len to exceed the limit if lim is more than INTPTR_MAX away from ptr.

However, it is extremely unlikely that you need to actually do the
full comparison as shown above. In context of your code, you can
usually assume that ptr < lim, and depending on the size of your
object, you might be able to assume that |lim-ptr| < INTPTR_MAX. If
not, then you can usually determine the point at which some of the
conditions are already met (or not) by how ptr or len are being
modified in the code that precedes this point.

Personally, I have found that using signed integer offsets and
detecting the wrap around cases at the moment they might happen is the
best approach. So I compare offsets, and make sure I can successfully
assume that there are no wrap around effects by the time I am doing
limit checks ("The Better String Library" is based pervasively on this
-- extensive tests on 16 bit platforms (which I can cause overflows to
happen easily even though real memory is available to create such
strings) have been done to check that it is correct.)

You are also technically potentially violating the standard if you are
comparing pointers that are not referencing the same object. But if
you can assume that its the same object, then the assumptions listed
above can usually be made, and you can find an equivalence in
operations to the offset approach that I use (though, IMHO, its harder
to see if your code is correct).

--
Paul Hsieh
http://www.pobox.com/~qed/
http://bstring.sf.net/

[pete]

Michael B Allen wrote:

>
On Thu, 17 Jan 2008 06:40:40 -0500
pete <pf*****@mindspring.comwrote:

Michael B Allen wrote:

int
copy_or_else(char *str, char *buf, char *blim)
{
size_t len = strlen(str) + 1;
>
if (buf == NULL || blim <= buf)
return -1;

<snip>

>
Concerning buf and blim in copy_or_else only,
is the above code legal?

No.
If (blim < buf) then the program isn't defined either.

Object pointers can only have 4 kinds of values:
1 object address
2 one past object address
3 null
4 indeterminate

Relational operators

>= < <=

are only defined for pointers
which point to the same object, or one past.

Hi Pete,

So what you're saying is that if someone can supply an invalid value
wrt to the standard, we should make no attempt to check for it?

Think etymologically.
Should there be any way to "determine"
the value of an "indeterminate" pointer?

You knew that you were taking a chance
and that you might have to learn something
as a consequence of posting your code,
so keep a stiff upper lip.

If (buf) is the address
of the lowest addressable byte of an object,
then the expression (buf - 1) is undefined.
The attempted evaluation of an undefined expression like
(buf (buf - 1))
makes the entire c program undefined.
That's the wrong way to write code.
We aggressively discourage
the use of undefined code on this newsgroup.

--
pete

[Michael B Allen]

On Thu, 17 Jan 2008 17:06:56 -0500
pete <pf*****@mindspring.comwrote:

If (buf) is the address
of the lowest addressable byte of an object,
then the expression (buf - 1) is undefined.
The attempted evaluation of an undefined expression like
(buf (buf - 1))
makes the entire c program undefined.

You still have not answered why an invalid blim pointer is any different
from an invalid size_t size.

Both forms can compute invalid addresses of buf which means they both
exhibit behavior that is equally undefined.

However, your new.c function dereferences that address which in practice
is much more likey to cause a fault. Therefore you have yet again provided
a positive argument for using a limit pointer instead of a size_t.

Thanks,
Mike

[Peter Nilsson]

James Kuyper <[e-mail]:

Peter Nilsson wrote:

James Kuyper <[e-mail]:

Michael B Allen wrote:
Note that I always also check to make sure lim != NULL
and that ptr < lim.
>
However, if ptr and lim both point into or one past the
end of the same array, and if ptr < lim, then lim-ptr
has to be positive, and that is something the standard
does say.

Chapter and verse please.

Already provided:

<snip>

6.5.6p9: "When two pointers are subtracted, both shall
point to elements of the same array object, or one past
the last element of the array object; the result is the
difference of the subscripts of the two array
elements."

It then says...

The size of the result is implementation-defined, and its
type (a signed integer type) is ptrdiff_t defined in the
<stddef.hheader. If the result is not representable in
an object of that type, the behavior is undefined. In
other words, if the expressions P and Q point to,
respectively, the i-th and j-th elements of an array
object, the expression (P)-(Q) has the value i-j provided
the value fits in an object of type ptrdiff_t. ...

Seems pretty clear to me that there's a possibility that
ptrdiff_t need not be able to represent a difference of two
otherwise valid pointers to elements from the same array.

<snip>

ptrdiff_t must be chosen to be large enough to ensure the
behavior required by 6.5.6p9 and 6.5.8p5.

6.5.6p9 is pretty clear that ptrdiff_t need not be large
enough.

--
Peter

[James Kuyper]

Peter Nilsson wrote:
....
[Re: 6.5.6p9]

It then says...

The size of the result is implementation-defined, and its
type (a signed integer type) is ptrdiff_t defined in the
<stddef.hheader. If the result is not representable in
an object of that type, the behavior is undefined. In
other words, if the expressions P and Q point to,
respectively, the i-th and j-th elements of an array
object, the expression (P)-(Q) has the value i-j provided
the value fits in an object of type ptrdiff_t. ...

Seems pretty clear to me that there's a possibility that
ptrdiff_t need not be able to represent a difference of two
otherwise valid pointers to elements from the same array.

Conceded - I'd forgotten that part, and didn't happen to re-read it
while researching my response - I knew what I was looking for, and
stopped reading as soon as I found it.

[Richard Tobin]

In article <47**********@mindspring.com>, pete <pf*****@mindspring.comwrote:

>So what you're saying is that if someone can supply an invalid value
wrt to the standard, we should make no attempt to check for it?

>Think etymologically.
Should there be any way to "determine"
the value of an "indeterminate" pointer?

Etymologically, that's exactly what you can do to one.

-- Richard
--
:wq

[William Ahern]

Michael B Allen <io****@gmail.comwrote:

>
If the function is use properly blim should not be less than buf.

However, I find that if someone can do something they eventually will. So
why not check? If they're using the function incorrectly, then undefined
behavior is moot anyway.

No, it's not. What the standard may leave undefined may nonetheless behave
in a constructive manner on the implementation.

So to check the buffer parameters I need to check if buf == NULL or
if blim == NULL or if blim <= buf but I don't need to check if blim ==
NULL since blim <= buf would detect if blim == NULL.

Then, within the logic of the function I check buf <= blim as necessary
to make sure I don't write past the end (again assuming blim is valid).

So what if buf was NULL? Good. Write to it. On many implementations this
will cause the application to crash, and the programmer will learn of his
mistake.

Likewise, if the caller has you writing past the end up a buffer, good!
There are implementations and/or debuggers which can catch this. Your
defenses measure may serve only to frustrate these tools, and to obsfuscate
or hide bugs.

Point being, these checks are often times counter-productive. They hide
bugs. I don't want my bugs hidden. Rather, I want to find them as soon as
possible.

[Michael B Allen]

On Fri, 18 Jan 2008 12:34:26 -0800
William Ahern <wi*****@wilbur.25thandClement.comwrote:

So to check the buffer parameters I need to check if buf == NULL or
if blim == NULL or if blim <= buf but I don't need to check if blim ==
NULL since blim <= buf would detect if blim == NULL.

Then, within the logic of the function I check buf <= blim as necessary
to make sure I don't write past the end (again assuming blim is valid).

So what if buf was NULL? Good. Write to it. On many implementations this
will cause the application to crash, and the programmer will learn of his
mistake.

So rather than simply being told that you did something wrong you would
rather someone hit you over the head with a baseball bat?

Returning an error isn't sufficient to indicate that ... well ... an
error occured?

If you write to an invalid address that's undefined behavior. If blim
is not within range of buf that is undefined behavior. At least a buf <=
blim check has a chance of catching it. And if it doesn't I'd rather get a
"Bus error" than scramble the stack with shell code.

Mike

[William Ahern]

Michael B Allen <io****@gmail.comwrote:

On Fri, 18 Jan 2008 12:34:26 -0800
William Ahern <wi*****@wilbur.25thandClement.comwrote:

So to check the buffer parameters I need to check if buf == NULL or
if blim == NULL or if blim <= buf but I don't need to check if blim ==
NULL since blim <= buf would detect if blim == NULL.
>
Then, within the logic of the function I check buf <= blim as necessary
to make sure I don't write past the end (again assuming blim is valid).

So what if buf was NULL? Good. Write to it. On many implementations this
will cause the application to crash, and the programmer will learn of his
mistake.

So rather than simply being told that you did something wrong you would
rather someone hit you over the head with a baseball bat?

Yes. If _I_ as a programmer did something wrong, I want to be told in the
same manner. I don't want processing errors mixed up with "you fscked up
pointers" errors. It's confusing.

Returning an error isn't sufficient to indicate that ... well ... an
error occured?

It's a different _kind_ of error. I think most people can agree that,
relatively speaking, C provides paltry language devices for signaling
exceptions. Indeed, with regard to such coding errors, maybe most languages
are so impoverished. Nonetheless, I much prefer that coding errors are
signaled in a fashion befitting coding errors.

If I create a function to duplicate a string, like strdup(), and it returns
NULL, that means "I couldn't duplicate the string". Maybe memory was low.
Who knows. But the import is the same. No duplicate string because of some
condition regarding the current state of the application or machine.

Now, if a NULL return _also_ might mean, "you passed me the wrong pointer",
then what? What, exactly, is the program supposed to do now? Treat it like
the other errors? That doesn't make sense. If I had the foresight to expect
such an error, shouldn't I have had the foresight to prevent it?

Ultimately, I think the point is that not all errors are the same. If an
engineer's conception of an error is, "Oh shit, now what do I do?", then
such checks might make sense. But if an "error" is really just another way
of signaling a meaningful condition regarding the process or computation,
then you want to keep these things separate. And you want to keep them
separate because, usually, good engineering doesn't mean punting on errors.
It means handling and responding to errors. There's really no way for the
application to handle or respond to such bugs, at least in the typical
context.

If you write to an invalid address that's undefined behavior. If blim
is not within range of buf that is undefined behavior. At least a buf <=
blim check has a chance of catching it. And if it doesn't I'd rather get a
"Bus error" than scramble the stack with shell code.

Sort of. Certainly you'd rather get a bus error, but not because you should
be worried about code injection. That's an ex post concern. Ex ante, what
you care about is writing code which makes it easier to fix bugs. And, as a
general rule, you don't accomplish that by putting superfluous checks
everywhere. If you focused on such ex post concerns at the expense of ex
ante measures, in the long run you'll likely end up with a higher risk of
code injection.

That's what I mean by saying that such defensive measures are
counter-productive. Certainly Bruce Schneier isn't wrong by emphasizing
defense-in-depth. Many people will argue that coding defensively is the
wrong way to approach security. That's not what I'm arguing, though I think
most people who do make such arguments aren't necessarily disputing the
notion of defense-in-depth, either. In any event, such things aren't so
straight-forward. The means to the end isn't so brutish.

- Bill