Re: StackGuard: Automatic Protection From Stack-smashing Attacks

[ranaur () ECP INF PUC-RIO BR (Ranaur the Elven Warlock)]

(this thread is becoming something more for math than to security but
only for curiosity ...)

On Tue, 30 Dec 1997, Mark Whitis wrote:

> I post this minor statistical correction to bugtraq because many of
> the readers of this list have frequent occasion to calculate
> probabilities for security related problems and I have found this
> rule of thumb to be useful it mental calculations.
        Right, nice rule of thumb. And useful.

>   limit as n approaches infinity of 1-( (1-1/n)^n ) is about 0.63.
        To be more precise as n approaches infinity 1-( (1-1/n)^n )
approaches 1 - 1/e.

> I am not an expert on statistics and I have not tried a symbolic
> solution to this problem but I have found the general rule(s) of
> thumb to be handy.  If anyone cares to derive a proof for this,
> by all means send me a copy.
        After some hours and many scribblings I came to a analytical
solution for your rule of thumb ...

        Let 1/n be the probability to happen the event (in our case the
flaw) at any try. After we try m times. We have the probability:

        1/n + (1 - 1/n).1/n + (1 - 1/n)^2.1/n + ... + (1 - 1/n)^m.1/n

(easy)

        We can rearrange this to a more compact formula:

             m
        1/n.sum((1-1/n)^i )
            i=0

                             m
        It's well-know that sum(x^i) = (1 - x^m+1)/(1-x) and ...
                            i=0

        in our case n = m, so ...

        1 1 - ( 1 - 1/n )^(n+1)
        -.--------------------- = 1 - ( 1 - 1/n )^(n+1)
        n 1 - ( 1 - 1/n)

        Problem is, calculatin the limit when n -> infinity.

        The hypotesys(better, the wild guess that worked ;-) is:

          lim[ 1 - ( 1 - 1/n )^(n+1) ] = 1 - 1/e, so ...
           n->inf

                lim[(1 - 1/n)^(n+1)] = 1/lim[(1+1/n)^(n)]
                 n->inf                   n->inf

        we can say that: lim x^(n+1) = lim x^n (n -> inf)

        so we get:

        lim [(1 - 1/n).(1 + 1/n)]^(n) = 1       n -> inf

        lim ( 1 + 1/n - 1/n + n^(-2)) = 1       n -> inf
        (we dropped the exploen because 1^(-n) = 1 )

        lim n^(-2) = 0  n -> -2

        so 1 = 1 (right)

        As we like to show.

(sorry about the english ... I hope it didn't harm the solution)

        Have a happy new year,

        Ranaur

         72343909365914955820090853918127362974800311909501722
           809321335 I'm not a number; I'm a free man! 193580963
             224315487 ranaur () usa net 7820  The prisoner 629962308
           691192077 http://www.inf.puc-rio.br/~ranaur 491038436
         4104925118618221315502224252800220835446429441594174