# Re: StackGuard: Automatic Protection From Stack-smashing Attacks

Ranaur the Elven Warlock (ranaur@ECP.INF.PUC-RIO.BR)
Wed, 31 Dec 1997 02:20:57 -0200

(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