Costin Manolache wrote:
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.
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.
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
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 did check the code and it looks ok - plenty of synchronized() blocks. But who knows ?
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
<?xml version="1.0" encoding="UTF-8"?> <node> <testelement class="org.apache.jmeter.testelement.TestPlan"> <testelement class="org.apache.jmeter.config.Arguments" name="TestPlan.user_defined_variables"> <property xml:space="preserve" name="TestElement.gui_class">org.apache.jmeter.config.gui.ArgumentsPanel</property> <property xml:space="preserve" name="TestElement.test_class">org.apache.jmeter.config.Arguments</property> <collection class="java.util.ArrayList" name="Arguments.arguments"/> <property xml:space="preserve" name="TestElement.name">Argument List</property> </testelement> <property xml:space="preserve" name="TestElement.gui_class">org.apache.jmeter.control.gui.TestPlanGui</property> <collection class="java.util.LinkedList" name="TestPlan.thread_groups"/> <property xml:space="preserve" name="TestElement.test_class">org.apache.jmeter.testelement.TestPlan</property> <property xml:space="preserve" name="TestElement.name">SessionTest</property> <property xml:space="preserve" name="TestPlan.functional_mode">false</property> </testelement> <node> <testelement class="org.apache.jmeter.threads.ThreadGroup"> <property xml:space="preserve" name="TestElement.gui_class">org.apache.jmeter.threads.gui.ThreadGroupGui</property> <property xml:space="preserve" name="TestElement.test_class">org.apache.jmeter.threads.ThreadGroup</property> <testelement class="org.apache.jmeter.control.LoopController" name="ThreadGroup.main_controller"> <property xml:space="preserve" name="TestElement.gui_class">org.apache.jmeter.control.gui.LoopControlPanel</property> <property xml:space="preserve" name="LoopController.loops">500</property> <property xml:space="preserve" name="TestElement.test_class">org.apache.jmeter.control.LoopController</property> <property xml:space="preserve" name="TestElement.name">Loop Controller</property> <property xml:space="preserve" name="LoopController.continue_forever">false</property> </testelement> <property xml:space="preserve" name="TestElement.name">Thread Group</property> <property xml:space="preserve" name="ThreadGroup.num_threads">40</property> <property xml:space="preserve" name="ThreadGroup.ramp_time">20</property> </testelement> <node> <testelement class="org.apache.jmeter.protocol.http.sampler.HTTPSampler"> <property xml:space="preserve" name="HTTPSampler.mimetype"/> <property xml:space="preserve" name="TestElement.gui_class">org.apache.jmeter.protocol.http.control.gui.HttpTestSampleGui</property> <property xml:space="preserve" name="HTTPSampler.path">/examples/sessionTest.jsp</property> <collection class="java.util.ArrayList" name="AbstractSampler.assertions"/> <property xml:space="preserve" name="HTTPSampler.FILE_FIELD"/> <property xml:space="preserve" name="TestElement.test_class">org.apache.jmeter.protocol.http.sampler.HTTPSampler</property> <property xml:space="preserve" name="HTTPSampler.method">GET</property> <property xml:space="preserve" name="TestElement.name">HTTP Request</property> <property xml:space="preserve" name="HTTPSampler.domain">localhost</property> <property xml:space="preserve" name="HTTPSampler.use_keepalive">true</property> <property xml:space="preserve" name="HTTPSampler.protocol">http</property> <property xml:space="preserve" name="HTTPSampler.follow_redirects">true</property> <property xml:space="preserve" name="HTTPSampler.port">8080</property> <testelement class="org.apache.jmeter.config.Arguments" name="HTTPsampler.Arguments"> <property xml:space="preserve" name="TestElement.gui_class">org.apache.jmeter.protocol.http.gui.HTTPArgumentsPanel</property> <property xml:space="preserve" name="TestElement.test_class">org.apache.jmeter.config.Arguments</property> <collection class="java.util.ArrayList" name="Arguments.arguments"/> <property xml:space="preserve" name="TestElement.name">Argument List</property> </testelement> <property xml:space="preserve" name="HTTPSampler.FILE_NAME"/> </testelement> </node> </node> </node>
/*
* Reads a file of log lines containing session IDs,
* compares all pairs of IDs, computes distribution of
* number of hex digit matches and outputs a table showing
* comparison to expected binomial distribution.
*
* Expects each line to contain a session ID enclosed in single
* quotes.
*
* Will blow up if the number of lines in the input file
* exceeds maxint.
*/
import java.io.IOException;
import java.io.LineNumberReader;
import java.io.FileReader;
import java.util.ArrayList;
public class DispersionCheck {
protected static final int SESSION_ID_BYTES = 16;
protected static final int BITS_PER_BYTE = 16;
public static void main(String args[]) {
execute(args[0]);
}
private static void execute(String fileName) {
double p = 1D/(double)BITS_PER_BYTE;
double q = 1.0D - p;
long[] freq = new long[2*SESSION_ID_BYTES+1];
double[] pct = new double[2*SESSION_ID_BYTES+1];
double[] pPowers = loadPowers(p,2*SESSION_ID_BYTES);
double[] qPowers = loadPowers(q,2*SESSION_ID_BYTES);
long[][] bCoef = loadBC(2*SESSION_ID_BYTES);
double[] density = loadDensity(bCoef,pPowers,qPowers,SESSION_ID_BYTES*2);
int ct;
try {
// System.out.println("Reading Sample File...");
String[] sample = loadSample(fileName);
// System.out.println("sample size: " + sample.length);
long iterations = sample.length;
long sumFreq = (iterations*(iterations-1))/2;
// System.out.println("Performing comparisons...");
for (int i = 0;i<iterations;i++) {
for (int j = 0; j<i;j++) {
ct = 0;
for (int k = 0; k<SESSION_ID_BYTES*2; k++) {
if (sample[i].regionMatches(k,sample[j],k,1)) {
ct++;
}
}
freq[ct]++;
}
/* if (i%500==0 && i>0)
System.out.println(i); */
}
System.out.println("Matches \t Count \t Observed pct \t Expected pct");
for (int i = 0; i<2*SESSION_ID_BYTES+1; i++) {
System.out.println(i + "\t" + freq[i] + "\t" +
(double)freq[i]/(double)sumFreq +
"\t" + density[i]);
}
} catch(Throwable e) {
e.printStackTrace();
}
}
private static long[][] loadBC(int n) {
long[][] out = new long[n+1][n+1];
out[0][0] = 1;
for (int i = 1; i<n+1; i++) {
out[i][0] = 1;
out[i][1] = i;
out[i][i] = 1;
for (int j = 2; j<i; j++) {
out[i][j] = out[i-1][j-1] + out[i-1][j];
}
}
return out;
}
private static double[] loadPowers(double p, int n) {
double out[] = new double[n+1];
out[0] = 1D;
for (int i=1; i<n+1; i++) {
out[i] = out[i-1]*p;
}
return out;
}
private static double[] loadDensity(long[][] bc, double[] pPowers, double[]
qPowers, int trials) {
double[] out = new double[trials+1];
for (int i = 0; i<trials+1; i++) {
out[i] = (new
Double(bc[trials][i])).doubleValue()*pPowers[i]*qPowers[trials-i];
}
return out;
}
private static String[] loadSample(String fileName) {
String line;
ArrayList temp = new ArrayList();
try {
LineNumberReader lr = new LineNumberReader(new FileReader(fileName));
while ((line = lr.readLine()) != null) {
temp.add(line.substring(line.indexOf("'")+1,line.lastIndexOf("'")-1));
}
String[] out = new String[temp.size()];
for (int i = 0; i<temp.size(); i++) {
out[i] = (String)temp.get(i);
}
return out;
}
catch (IOException e) {
e.printStackTrace();
return null;
}
}
}
Matches Count Observed pct Expected pct 0 6761889 0.13525130513051306 0.12678878637700033 1 13971121 0.27945036503650367 0.27048274427093405 2 13973792 0.2795037903790379 0.2794988357466318 3 9005335 0.18012471247124712 0.18633255716442124 4 4203635 0.08408110811081108 0.09006073596280359 5 1512929 0.030261606160616062 0.03362267475944667 6 437199 0.008744854485448544 0.010086802427834001 7 104311 0.0020864286428642865 0.002497684410701753 8 20791 4.1586158615861585E-4 5.203509188961985E-4 9 3390 6.780678067806781E-5 9.250683002599085E-5 10 535 1.0701070107010701E-5 1.4184380603985265E-5 11 65 1.3001300130013002E-6 1.8912507471980354E-6 12 5 1.0001000100010001E-7 2.2064592050643746E-7 13 3 6.000600060006E-8 2.2630350821173075E-8 14 0 0.0 2.0475079314394686E-9 15 0 0.0 1.638006345151575E-10 16 0 0.0 1.1602544944823657E-11 17 0 0.0 7.280028200673667E-13 18 0 0.0 4.04446011148537E-14 19 0 0.0 1.9867523354664978E-15 20 0 0.0 8.609260120354823E-17 21 0 0.0 3.279718141087552E-18 22 0 0.0 1.0932393803625173E-19 23 0 0.0 3.168809798152224E-21 24 0 0.0 7.92202449538056E-23 25 0 0.0 1.6900318923478527E-24 26 0 0.0 3.0333905760089665E-26 27 0 0.0 4.493911964457728E-28 28 0 0.0 5.3498951957830096E-30 29 0 0.0 4.919443858191273E-32 30 0 0.0 3.279629238794182E-34 31 0 0.0 1.410593220986745E-36 32 0 0.0 2.9387358770557188E-39
/* * ==================================================================== * * The Apache Software License, Version 1.1 * * Copyright (c) 1999 The Apache Software Foundation. All rights * reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * * 1. Redistributions of source code must retain the above copyright * notice, this list of conditions and the following disclaimer. * * 2. Redistributions in binary form must reproduce the above copyright * notice, this list of conditions and the following disclaimer in * the documentation and/or other materials provided with the * distribution. * * 3. The end-user documentation included with the redistribution, if * any, must include the following acknowlegement: * "This product includes software developed by the * Apache Software Foundation (http://www.apache.org/)." * Alternately, this acknowlegement may appear in the software itself, * if and wherever such third-party acknowlegements normally appear. * * 4. The names "The Jakarta Project", "Tomcat", and "Apache Software * Foundation" must not be used to endorse or promote products derived * from this software without prior written permission. For written * permission, please contact [EMAIL PROTECTED] * * 5. Products derived from this software may not be called "Apache" * nor may "Apache" appear in their names without prior written * permission of the Apache Group. * * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE * DISCLAIMED. IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF * SUCH DAMAGE. * ==================================================================== * * This software consists of voluntary contributions made by many * individuals on behalf of the Apache Software Foundation. For more * information on the Apache Software Foundation, please see * <http://www.apache.org/>. * * [Additional notices, if required by prior licensing conditions] * */ import java.io.IOException; import java.security.MessageDigest; import java.security.NoSuchAlgorithmException; import java.util.ArrayList; import java.util.HashMap; import java.util.Random; public class DispersionTest { protected MessageDigest digest = null; protected String entropy = null; protected Random random = null; protected String randomClass = "java.security.SecureRandom"; protected static final String DEFAULT_ALGORITHM = "MD5"; protected static final int SESSION_ID_BYTES = 16; protected static final int BITS_PER_BYTE = 16; protected String algorithm = DEFAULT_ALGORITHM; /** * Return the MessageDigest object to be used for calculating * session identifiers. If none has been created yet, initialize * one the first time this method is called. */ public synchronized MessageDigest getDigest() { if (this.digest == null) { try { this.digest = MessageDigest.getInstance(algorithm); } catch (NoSuchAlgorithmException e) { try { this.digest = MessageDigest.getInstance(DEFAULT_ALGORITHM); } catch (NoSuchAlgorithmException f) { this.digest = null; } } } return (this.digest); } /** * Generate and return a new session identifier. */ protected String generateSessionId() { // Generate a byte array containing a session identifier Random random = getRandom(); byte bytes[] = new byte[SESSION_ID_BYTES]; getRandom().nextBytes(bytes); bytes = getDigest().digest(bytes); // Render the result as a String of hexadecimal digits StringBuffer result = new StringBuffer(); for (int i = 0; i < bytes.length; i++) { byte b1 = (byte) ((bytes[i] & 0xf0) >> 4); byte b2 = (byte) (bytes[i] & 0x0f); if (b1 < 10) result.append((char) ('0' + b1)); else result.append((char) ('A' + (b1 - 10))); if (b2 < 10) result.append((char) ('0' + b2)); else result.append((char) ('A' + (b2 - 10))); } return (result.toString()); } /** * Set the entropy increaser value. * * @param entropy The new entropy increaser value */ public void setEntropy(String entropy) { String oldEntropy = entropy; this.entropy = entropy; } /** * Return the entropy increaser value, or compute a semi-useful value * if this String has not yet been set. */ public String getEntropy() { // Calculate a semi-useful value if this has not been set if (this.entropy == null) setEntropy(this.toString()); return (this.entropy); } /** * Return the random number generator instance we should use for * generating session identifiers. If there is no such generator * currently defined, construct and seed a new one. */ public synchronized Random getRandom() { if (this.random == null) { synchronized (this) { if (this.random == null) { // Calculate the new random number generator seed long seed = System.currentTimeMillis(); char entropy[] = getEntropy().toCharArray(); for (int i = 0; i < entropy.length; i++) { long update = ((byte) entropy[i]) << ((i % 8) * 8); seed ^= update; } try { // Construct and seed a new random number generator Class clazz = Class.forName(randomClass); this.random = (Random) clazz.newInstance(); this.random.setSeed(seed); } catch (Exception e) { // Fall back to the simple case this.random = new java.util.Random(); this.random.setSeed(seed); } } } } return (this.random); } // Modified from 1/10/03 post "Collide.java" by Tim Funk public static void main(String args[]) { DispersionTest t = new DispersionTest(); try { t.go(Integer.parseInt(args[0])); } catch(Throwable e) { e.printStackTrace(); } } // Modified from 1/10/03 post "Collide.java" by Tim Funk private void go(int iterations) { String[] sample = new String[iterations]; double p = 1D/(double)BITS_PER_BYTE; double q = 1.0D - p; long[] freq = new long[2*SESSION_ID_BYTES+1]; double[] pct = new double[2*SESSION_ID_BYTES+1]; double[] pPowers = loadPowers(p,2*SESSION_ID_BYTES); double[] qPowers = loadPowers(q,2*SESSION_ID_BYTES); long[][] bCoef = loadBC(2*SESSION_ID_BYTES); double[] density = loadDensity(bCoef,pPowers,qPowers,2*SESSION_ID_BYTES); int ct; long sumFreq = (iterations*(iterations-1))/2; try { // System.out.println("Generating sample..."); for (int i=0;i<iterations;i++) { sample[i] = generateSessionId(); /* if (i%5000==0 && i>0) System.out.println(i); */ } // System.out.println("Performing comparisons..."); for (int i = 0;i<iterations;i++) { for (int j = 0; j<i;j++) { ct = 0; for (int k = 0; k<2*SESSION_ID_BYTES; k++) { if (sample[i].regionMatches(k,sample[j],k,1)) { ct++; } } freq[ct]++; } /* if (i%500==0 && i>0) System.out.println(i); */ }; System.out.println("Matches \t Count \t Observed pct \t Expected pct"); for (int i = 0; i<2*SESSION_ID_BYTES+1; i++) { System.out.println(i + "\t" + freq[i] + "\t" + (double)freq[i]/(double)sumFreq + "\t" + density[i]); } } catch(Throwable e) { e.printStackTrace(); } } private static long[][] loadBC(int n) { long[][] out = new long[n+1][n+1]; out[0][0] = 1; for (int i = 1; i<n+1; i++) { out[i][0] = 1; out[i][1] = i; out[i][i] = 1; for (int j = 2; j<i; j++) { out[i][j] = out[i-1][j-1] + out[i-1][j]; } } return out; } private static double[] loadPowers(double p, int n) { double out[] = new double[n+1]; out[0] = 1D; for (int i=1; i<n+1; i++) { out[i] = out[i-1]*p; } return out; } private static double[] loadDensity(long[][] bc, double[] pPowers, double[] qPowers, int trials) { double[] out = new double[trials+1]; for (int i = 0; i<trials+1; i++) { out[i] = (new Double(bc[trials][i])).doubleValue()*pPowers[i]*qPowers[trials-i]; } return out; } }
-- To unsubscribe, e-mail: <mailto:[EMAIL PROTECTED]> For additional commands, e-mail: <mailto:[EMAIL PROTECTED]>
