Bugtraq mailing list archives
Re: StackGuard: Automatic Protection From Stack-smashing Attacks
From: ranaur () ECP INF PUC-RIO BR (Ranaur the Elven Warlock)
Date: 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
Current thread:
- Re: StackGuard: Automatic Protection From Stack-smashing Attacks Steve Bellovin (Dec 19)
- Re: StackGuard: Automatic Protection From Stack-smashing Attacks Crispin Cowan (Dec 19)
- Re: StackGuard: Automatic Protection From Stack-smashing Attacks Kragen (Dec 19)
- Re: StackGuard: Automatic Protection From Stack-smashing Attacks Tim Newsham (Dec 19)
- Re: StackGuard: Automatic Protection From Stack-smashing Attacks Crispin Cowan (Dec 19)
- Linux vsyslog() overflow Solar Designer (Dec 20)
- Re: Linux vsyslog() overflow Dann Lunsford (Dec 22)
- Re: StackGuard: Automatic Protection From Stack-smashing Attacks Mark Whitis (Dec 30)
- Re: StackGuard: Automatic Protection From Stack-smashing Attacks Ranaur the Elven Warlock (Dec 30)
- Apache memory/process management. MichaĆ Zalewski (Dec 31)
- Re: Apache memory/process management. Dean Gaudet (Dec 31)
- Re: StackGuard: Automatic Protection From Stack-smashing Attacks Crispin Cowan (Dec 19)