Re: Duplicate session IDs are *common*[GFI-T105-3E21F8D3D7B6FFDE]

[Phil Steitz <ph...@steitz.com>]

Using a modified version of Tim Funk's "Collide.java", I ran the
following dispersion test (using Sun's Linux jdk's 1.3.1_03 and 1.4.1_01):

1. Generate n session id's.
2. For each pair of generated id's, count the number of matching
characters in the two strings (i.e., the number of positions where the
hex digits are the same).
3. Compare the distribution of matches to the binomial distribution
B(16,1/16).

The results of one run of 10000 (using 1.4.1_01) are attached (along
with the code). They show close agreement with the expected
distribution.  I did several runs with 10-30k sample sizes. Of course, 
this doesn't *prove* anything; but it does support the hypothesis that 
p(exact match among two session IDs) ~ 1/2^128.

Re: Duplicate session IDs are *common*[GFI-T105-3E21F8D3D7B6FFDE]

[Phil Steitz <ph...@steitz.com>]

Costin Manolache wrote:
> 
> Could you make a small modification and run the same test with
> 20 concurent threads ? I checked the code and we have plenty of 
> syncs, but you never know.

OK -- for this I went to the horse's (or maybe I should say, "cat's") 
mouth with the same result -- collisions still look very unlikely.
Here is what I did (using unpatched tomcat 4.1.18, Sun's linux JDK 
1.3.1_03):

1. Put a jsp that does nothing but get a session and then invalidate it 
(sessionTest.jsp) in /webapps/examples;
2. Set up a jmeter test with 20 threads, no delay, hitting 
sessionTest.jsp 500 times each (SessionTest.jmx);
3. grep 'Created' localhost_examples_log.<date>.txt > sessions.txt;
4. Run "DispersionCheck.java" (attached) to grab the generated session 
IDs from sessions.txt and do the comparisons as before.

Output is attached as DispersionCheckOut.txt.  Note that among the 
199,990,000 pairs of session ID's examined, none agreed in more than 13 
of 32 hex digits.

BTW, I noticed that in my original tests, I was only comparing the first 
half of the strings (forgot that the hex conversion doubles the length - 
DOH!).  I have attached a corrected version of the standalone program 
DispersionCheck.java that does all of the comparisons and compares the 
distribution to B(32,1/16) instead of B(16,1/16). Results are as expected.

-Phil

> 
> I did check the code and it looks ok - plenty of synchronized() blocks.
> But who knows ?

If there is a problem, it could be "protection," not just 
synchronization (which just guarantees serialization).  I notice that 
the valid flag is used to protect sessions from being updated while they 
are expiring, etc.  I posted a (probably insignificant) bug report a 
couple of weeks ago 
(http://nagoya.apache.org/bugzilla/show_bug.cgi?id=15746) indicating 
that a session being recycled could in theory have attributes added by 
other threads still holding references to it between the time that its 
attributes are cleared and when its isValid flag is set to false.  The 
result would be that a "dirty" session would be reused.

I have been trying to make this (or other similar things) to happen 
using jmeter tests to no avail; but I will keep trying.

> 
> Costin
> 

> 

Re: Duplicate session IDs are *common*[GFI-T105-3E21F8D3D7B6FFDE]

[Costin Manolache <cm...@yahoo.com>]

Impressive.

Could you make a small modification and run the same test with
20 concurent threads ? I checked the code and we have plenty of 
syncs, but you never know.

Interesting - java.util.Random is not synchronized, so it is very likely
that 2 threads calling the method at the same time will get a collision.
java.security.SecureRandom seems ok. 

Most random sources use some "natural" entropy ( time, number of interrupts, 
etc ) and some alghoritm to derive the next number. If 2 calls are too 
close to each other, we'll not have enough entropy and without the right
synchronization you may get the same result ( if the seed wasn't updated ).

I did check the code and it looks ok - plenty of synchronized() blocks.
But who knows ?

Costin

Phil Steitz wrote:

> Using a modified version of Tim Funk's "Collide.java", I ran the
> following dispersion test (using Sun's Linux jdk's 1.3.1_03 and 1.4.1_01):
> 
> 1. Generate n session id's.
> 2. For each pair of generated id's, count the number of matching
> characters in the two strings (i.e., the number of positions where the
> hex digits are the same).
> 3. Compare the distribution of matches to the binomial distribution
> B(16,1/16).
> 
> The results of one run of 10000 (using 1.4.1_01) are attached (along
> with the code). They show close agreement with the expected
> distribution.  I did several runs with 10-30k sample sizes. Of course,
> this doesn't *prove* anything; but it does support the hypothesis that
> p(exact match among two session IDs) ~ 1/2^128.





--
To unsubscribe, e-mail:   <ma...@jakarta.apache.org>
For additional commands, e-mail: <ma...@jakarta.apache.org>