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.
Matches Count Observed pct Expected pct 0 17803987 0.3561153515351535 0.3560741304517928 1 18988607 0.3798101210121012 0.37981240581524567 2 9492989 0.18987876787678767 0.18990620290762283 3 2953095 0.059067806780678064 0.05908192979348266 4 640277 0.012806820682068207 0.01280108478858791 5 102349 0.002047184718471847 0.0020481735661740655 6 12445 2.4892489248924893E-4 2.50332324754608E-4 7 1168 2.3362336233623362E-5 2.3841173786153143E-5 8 80 1.6001600160016002E-6 1.7880880339614857E-6 9 3 6.000600060006E-8 1.0596077238290286E-7 10 0 0.0 4.944836044535467E-9 11 0 0.0 1.798122198012897E-10 12 0 0.0 4.994783883369158E-12 13 0 0.0 1.0245710529988017E-13 14 0 0.0 1.463672932855431E-15 15 0 0.0 1.3010426069826053E-17 16 0 0.0 5.421010862427522E-20
/* * ==================================================================== * * 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/02 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/02 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;
int[] freq = new int[SESSION_ID_BYTES+1];
double[] pct = new double[SESSION_ID_BYTES+1];
double[] pPowers = loadPowers(p,SESSION_ID_BYTES);
double[] qPowers = loadPowers(q,SESSION_ID_BYTES);
long[][] bCoef = loadBC(SESSION_ID_BYTES);
double[] density = loadDensity(bCoef,pPowers,qPowers,SESSION_ID_BYTES);
String id;
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<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<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]>
