How (un)safe is pointer arithmetic?
I recognize that this is a controversial topic – if you’re a safety-critical professional using C or C++, I’d be glad to hear your views.
Using explicit pointer arithmetic in critical software is generally frowned upon. MISRA 2004 rules 17.1 to 17.3 prohibit some particular cases of explicit pointer arithmetic that do not give rise to well-defined results. Rule 17.4 then states that “Array indexing shall be the only allowed form of pointer arithmetic”. All 4 rules are “required” rather than “advisory”, so 17.4 appears to make the preceding 3 rules redundant. The implication seems to be that developers who break 17.4 should at least honour 17.1 to 17.3.
The most common use of explicit pointer arithmetic in C is to increment a pointer while processing an array of data in a loop:
for (T* p = arr; p != arr + numElements; ++p) {
*p = foo(*p);
}
The expression arr + numElements is a classic C pointer to one-past-the-last-element of the array.
In C++ programming using the Standard Template Library, the idiom of processing an array by incrementing a pointer through its elements is generalised through the concept of iterators:
for (C<T>::iterator p = coll.begin(); p != coll.end(); ++p) {
*p = foo(*p);
}
where coll has type C<T>, i.e. some collection whose elements are of type T.
We can readily replace the C example above with code that does not use pointer arithmetic:
for (size_t i = 0; i != numElements; ++i) {
arr[i] = foo(arr[i]);
}
Does this version have any disadvantages compared to the one that increments the pointer? Well, it may be a little slower. A non-optimising compiler will generate code to evaluate arr[i] every time it appears within the body of the loop – slower than evaluating *p. An optimising compiler will probably create an induction variable to track the value of &arr[i], mimicking pointer p from the original version. Even so, on a RISC architecture it needs to use 3 registers to be efficient (to hold i, &arr[i], and numElements); whereas the original version needs just 2 (to hold p and arr + numElements).
Ideally, architects of critical systems should specify sufficiently powerful hardware that the software developers can concentrate on correctness and not have to worry about minor differences in efficiency. Unfortunately, in mass markets such as the automobile industry, and in low-energy markets such as space, pressure to minimise hardware power is often present.
So, can we safely ignore MISRA rule 17.4 and use the pointer-incrementing version? Is pointer arithmetic really any more dangerous than array indexing? Arithmetic on pointers can yield pointers that are outside the array they were intended to point to; but is this a worse or harder-to-avoid hazard than indexing an array out-of-bounds? If you’ve read this far and have a view on this, why not leave a comment on this entry?
Because we do occasionally see instances of pointer arithmetic in safety-critical code we’ve been asked to look at, we decided to see whether could verify these properties in ArC:
- Pointer arithmetic is only applied to array pointers;
- Pointer arithmetic always yields a pointer into the original array or to one-past-the-last-element of the original array;
- When two pointers are compared or subtracted, they point into the same array;
- A pointer to one-past-the-last-element is never dereferenced.
The answer is that it is no more difficult verify these properties than to verify that array indices are in bounds. So we do support pointer arithmetic in ArC. That is why array pointers in ArC have the lwb ghost member (see my earlier post about taming array pointers). In the absence of pointer arithmetic, the lower bound is always zero.
If you’re using C++ rather than C and you’re taking my earlier advice to use Array, Vector or similar classes in preference to naked arrays, then you may be tempted to revert to naked arrays and pointer arithmetic where efficiency is vital. However, we’ve found it straightforward to implement an efficient Array class that supports either pointer arithmetic or iterators; and when run-time index checking is enabled, we provide run-time pointer arithmetic or iterator checks as well.
Need help with using C or C++ in critical systems? Click on my picture above.
David Crocker's Verification Blog 
I’m skeptical of the claim that the for-loop using explicit index i is “probably” slower. Didn’t Don Knuth teach us that premature optimization is the root of all evil, and to first benchmark before making assumptions about the speed difference? I just tested it with gcc on my platform, and here are the results:
ptr index
-O0 6.26s 6.35s
-O1 3.59s 3.09s
-O2 1.04s 1.03s
-O3 0.26s 0.26s
So it looks like not only was the claim in this blog post wrong — it was actually backwards. At some low optimization levels, using an index is actually *faster* (not slower as claimed in this blog post). At higher optimization levels, they are exactly equivalent in speed.
I agree with you that speed differences should be benchmarked before making decisions on how to write the code for best performance. The speeds of both versions will depend greatly on the compiler and processor architecture. You didn’t say what processor you ran the tests on, so I’m guessing that you used a PC or Mac with an x86 or x64 CPU. These processors have a highly parallel architecture and scaled indexing instructions, making the indexing operation very efficient if the element size is 1, 2, 4 or 8 bytes. Most critical embedded systems run on processors with less parallelism and simpler instruction sets. The reason that the speeds were the “other way round” at -O1 may be because I used the expression “p != arr + numElements” in the for-loop header, and at -O1 the compiler may not move the addition operation outside the loop. I don’t have time to run the tests myself right now, but you might like to try repeating the test with the end-of-array pointer precomputed, and using an array of structures with the structure size > 8 bytes.The fact that at -O3 the times are the same makes me wonder whether gcc is now sufficiently advanced to optimize variable ‘i’ away completely in the non-pointer code.
By the way, I’d like to make a stylistic nit. Instead of writing
for (size_t i = 0; i != numElements; ++i) {
arr[i] = foo(arr[i]);
}
I recommend that you use the following form instead:
for (size_t i = 0; i arr[0]), p->len); <— Is this pointer arithmetic?
The latter line is more or less equivalent to pointer arithmetic applied to a "struct foo *", but it seems a plausibly safe/allowable form of pointer arithmetic.
Crud. My last blog comment got horribly mangled somehow by the blogging system, causing a large block of text and code to be completely deleted. Maybe it is the less-than and greater-thans? Annoying.
Let me try again, this time with some HTML PRE tags, to see if that fixes the problem. In the first half of my blog comment, I intended to recommend that you use
instead of
The reason is that this makes the loop invariant slightly easier to deduce. The difference is minor in this particular case, but in more complex code, I find my recommended variant a bit easier on the eyes. For an automatic verification system, it might not make any difference, but for a human programmer, I think it’s to our benefit to pick idioms that make it as easy as possible to reason about code.
Let’s see if this comment comes through correctly. If it does, I’ll try to submit another comment explaining the second half of my query, about pointer arithmetic.
In examples such as this, there are usually two parts to the loop invariant. The trivial part is 0 <= i <= numElements, which is indeed easier to deduce using < rather than != in the loop termination condition. The second and more difficult part is typically of the form "forall j in 0..(i – 1) :- p(j)". The other thing we need to deduce is the state on exit from the loop. Using the != form allows us to deduce i == numElements on exit, from which we can compute the loop postcondition from the full invariant. Using the < form makes this more difficult. We have found that the invariant 0 <= i <= numElements is something that the prover can normally suggest if it is omitted. So I prefer the != form. Dijkstra made a similar argument on page 56 of his book "A Discipline of Programming", together with another argument in support of the != form.
OK, it looks like that worked. Cool. On to the second point I intended to make, but which was truncated.
I like the ideas you have about how to restrict pointer arithmetic. It occurs to me there may be some interesting cases not mentioned in your rules. For instance:
struct foo { size_t len; double arr[0]; // a variable-length array } void bar(double a[], size_t alen) { ... } struct foo *p = ...; bar(&(p->arr[0]), p->len); len); <==== What about this?In the last two lines above, the expression to compute the first argument to foo() is more or less equivalent to pointer arithmetic applied to a “struct foo *”, but it seems the first one is a plausibly safe/allowable form of pointer arithmetic, whereas the second one is OK to disallow.
Yuck. My comment got mangled again. Silly WordPress.
I was trying to show two invocations of bar(). Here is the first:
Here is the second:
These two are operationally equivalent. The latter is pointer arithmetic. Is the former pointer arithmetic, too? If it does count as pointer arithmetic, is it allowable? It seems reasonable to me that the first should be allowed but the second could be disallowed.
Those two expressions are only guaranteed to be equivalent if you are using a C99 compiler, and I believe the correct way to declare that array field in C99 is “double arr[]” rather than “double a[0]”. I think I would prefer to use “bar(p->arr, p->len)” rather than either of the other forms.
I know this post is old but pointer arithmetic is detected as error in MISRA C with reason because increasing a pointer on a embedded platform does not automatically mean that it works as you think. For example I implemented a circular buffer using pointer arithmetic and I got results which would theoretically be impossible. Using array indexing in the same place gave me the correct results. So I would not recommend to use pointer arithmetic on a embedded platform.
Hi, and thanks for your comment. Pointer arithmetic is well-defined in the C standard, provided you obey the constraints that avoid undefined behaviour. So if it gave a result that “would theoretically be impossible” then I think either your compiler was at fault or your idea of “theoretically impossible” does not conform to what the C standard actually guarantees. Although the MISRA-C 2004 guidelines include a required rule that forbids pointer arithmetic (along with some other rules to follow if you break that one), the MISRA-C 2012 standard allows pointer arithmetic, and has a number of rules to ensure that it is only used when the behaviour is well-defined.