Re: [Lit.] Buffer overruns

newstome_at_comcast.net
Date: 12/31/04 

Date: Fri, 31 Dec 2004 17:43:48 GMT

Andrew Swallow <am.swallow@btopenworld.com> wrote:
> newstome@comcast.net wrote:
>
>> Andrew Swallow <am.swallow@btopenworld.com> wrote:
>>
>>>David Wagner wrote:
>>>[snip]
>>>
>>>
>>>>Douglas A. Gwyn wrote:
>>>>
>>>>Are automatic bounds checks a safety net? Are they useful? If so,
>>>>what do you mean when you say they don't help the application achieve
>>>>its functions? How can something be useful but not help the application
>>>>achieve its functions? What other meaning of "useful" did you have
>>>>in mind? I'm having trouble following the argument.
>>>
>>>The purpose of automatic bound checks to to find *design* errors in the
>>>software and its specifcations. To do this they require between about
>>>75% and 90% of the aircraft's computational power.
>>
>>
>> If bounds checks are taking anything even remotely approaching 75-90%
>> of computational power, then something is horribly, horribly wrong.
>> Should be 10% or less....
>
> What has gone wrong is that by adding bounds checking you have added a
> major increase in complexity.
>
> The statement
> a[i] = b[i]
>
> Can be complied with out bounds checking as
>
> 1. Load index register with content of i
> 2. Load accumulator with content of b[] offset by index register
> 3. Store accumulator in a[] offset by index register
>
> With bounds checking this becomes
>
> 1. Load index register with content of i
> 2. Compare index register with lower limit of array a
> 3. Jump if too small to error_routine
> 4. Compare index register with upper limit of array a
> 5. Jump if too big to error_routine
> 6. Compare index register with lower limit of array b
> 7. Jump if too small to error_routine
> 8. Compare index register with upper limit of array b
> 9. Jump if too big to error_routine
> 10. Load accumulator with content of b[] offset by index register
> 11. Store accumulator in a[] offset by index register
>
> When the code is in a subroutine things are even worse because the
> limits are not stored in fixed locations.
>
> For an over head of less than 10% major optimisation need performing
> like range checks on subroutine entry and the software to be performing
> mathematical functions using ordinary variables.

First off, your code above uses about the most pedantic bounds
checking possible, to exaggerate the bounds checking overhead.
Intelligent compilers for decent languages will do much, much better.

Second, the expression (a simple assignment from one array to another)
is almost nothing but array accesses, so looking at that in isolation
will again exaggerate the overhead.

I just did a little test: the gcc java-native compiler has an option
to turn off bounds checking. Using a tight selection sort loop
(sorting 70,000 ints) I tried with and without bounds checking. This
code is almost solid array accesses, so in fact is just about as bad
as any code you can imagine for bounds checking overhead. Second, the
optimization in gcc isn't the greatest. The overhead? Right at 20%.

I imagine most real code (i.e., not tight loops with constant array
references) will be less than 10% overhead.

>> No, that's not what bounds checks (in the situation we're discussing
>> here) are primarily for at all. It's to make sure that things don't
>> go out of control in a production environment. The logic here is
>> amazingly simple:
>>
>> 1) Complex software is going to have bugs.
>> 2) Many bugs will be bounds errors.
>
> It is only a minor cause of errors, range errors on for loops are easy
> to spot using code inspections.

Reality, and the huge prevalance of number of buffer overflows in real
code, seems to disagree with you.

>> 3) Software that simply shuts down is better than software that runs
>> out of control with unpredictable and undefined behavior.
>
> An even better way is to put the software in prom, separate the
> locations of variables and arrays whilst running a watch dog timer.
> Test software at the upper and lower limits of arrays; perform worst
> case analysis on stacks and queue sizes.

I have no idea what you're saying here.... I'm not sure why software
in PROM would help at all.

>> The only even slightly controversial part of that is #3, in software
>> with high availability requirements. However, I'd still argue that
>> shutting down into a reasonable failover mode is much better than
>> unpredictable behavior....
>
> If you want to do something useful ban dynamic memory allocation. When
> a program leaves the linker it should have all the ram it needs. Memory
> leaks and shortages are hard to find.

This, of course, would help, but would be a pretty fundamental blow to
how software works and is designed these days. 

-- 
That's News To Me!
newstome@comcast.net

Relevant Pages

  • Re: [Lit.] Buffer overruns
    ... > of computational power, then something is horribly, horribly wrong. ... Load accumulator with content of boffset by index register ... Compare index register with lower limit of array a ... Compare index register with lower limit of array b ...
    (sci.crypt)
  • Re: Text Script
    ... > more overhead than reading from an array as it is an in-memory operation. ... For small files this adds much overhead. ... >> Rewinding a file might indeed be instantaneous as you say, ... design time efficiency may be in the eye of the beholder - ...
    (microsoft.public.windows.server.scripting)
  • Re: Ada.Containers.Vectors - querying multiple elements
    ... there would be a distributed overhead. ... compilers store it separately. ... In order to be able to represent an array as ... so I don't think it would make sense to allow 'First to be an invalid ...
    (comp.lang.ada)
  • Re: Derived types and allocatable
    ... (snip on overhead for allocate on assignment) ... In order to do a whole array assignment at all you must ... where R does allocate on assignment. ...
    (comp.lang.fortran)
  • Re: High Memory Consumption of Classes and Arrays
    ... Only the array itself has overhead. ... memory as a reference type. ... > least consume 40 bytes of memory. ...
    (microsoft.public.dotnet.framework.performance)