147 lines
6.1 KiB
Java
147 lines
6.1 KiB
Java
package unit;
|
||
|
||
import java.nio.charset.StandardCharsets;
|
||
import java.util.HashMap;
|
||
|
||
/**
|
||
* mbedtls-0001 unit test
|
||
*
|
||
* Models the O(S×C) ALPN selection in mbedtls_ssl_parse_alpn_ext()
|
||
* and the O(S+C) fixed version using a hash map of client names.
|
||
*
|
||
* Compile: javac -d . MbedTlsAlpnParseTest.java
|
||
* Run: java unit.MbedTlsAlpnParseTest
|
||
*/
|
||
public class MbedTlsAlpnParseTest {
|
||
|
||
// ------------------------------------------------------------------ //
|
||
// Model the defective O(S × C) implementation //
|
||
// ------------------------------------------------------------------ //
|
||
static String defectiveSelect(String[] serverList, byte[][] clientNames) {
|
||
// outer: server preference order
|
||
for (String server : serverList) {
|
||
byte[] sb = server.getBytes(StandardCharsets.UTF_8);
|
||
// inner: full scan of client list with memcmp
|
||
for (byte[] client : clientNames) {
|
||
if (client.length == sb.length &&
|
||
java.util.Arrays.equals(client, sb)) {
|
||
return server;
|
||
}
|
||
}
|
||
}
|
||
return null;
|
||
}
|
||
|
||
// ------------------------------------------------------------------ //
|
||
// Model the fixed O(C + S) implementation using a hash set //
|
||
// ------------------------------------------------------------------ //
|
||
static String fixedSelect(String[] serverList, byte[][] clientNames) {
|
||
// Build hash set of client names — O(C)
|
||
HashMap<String, Boolean> clientSet = new HashMap<>();
|
||
for (byte[] c : clientNames)
|
||
clientSet.put(new String(c, StandardCharsets.UTF_8), Boolean.TRUE);
|
||
|
||
// Iterate server list — O(S), each lookup O(1)
|
||
for (String server : serverList) {
|
||
if (clientSet.containsKey(server))
|
||
return server;
|
||
}
|
||
return null;
|
||
}
|
||
|
||
// ------------------------------------------------------------------ //
|
||
// Counting versions //
|
||
// ------------------------------------------------------------------ //
|
||
static long[] ops = new long[2];
|
||
|
||
static String defectiveCounting(String[] serverList, byte[][] clientNames) {
|
||
for (String server : serverList) {
|
||
byte[] sb = server.getBytes(StandardCharsets.UTF_8);
|
||
for (byte[] client : clientNames) {
|
||
ops[0]++;
|
||
if (client.length == sb.length && java.util.Arrays.equals(client, sb))
|
||
return server;
|
||
}
|
||
}
|
||
return null;
|
||
}
|
||
|
||
static String fixedCounting(String[] serverList, byte[][] clientNames) {
|
||
HashMap<String, Boolean> clientSet = new HashMap<>();
|
||
for (byte[] c : clientNames) {
|
||
ops[1]++;
|
||
clientSet.put(new String(c, StandardCharsets.UTF_8), Boolean.TRUE);
|
||
}
|
||
for (String server : serverList) {
|
||
ops[1]++;
|
||
if (clientSet.containsKey(server))
|
||
return server;
|
||
}
|
||
return null;
|
||
}
|
||
|
||
static byte[] name(String s) { return s.getBytes(StandardCharsets.UTF_8); }
|
||
|
||
// ------------------------------------------------------------------ //
|
||
// Tests //
|
||
// ------------------------------------------------------------------ //
|
||
static int pass = 0, fail = 0;
|
||
|
||
static void check(String label, boolean cond) {
|
||
if (cond) { System.out.println(" PASS " + label); pass++; }
|
||
else { System.out.println(" FAIL " + label); fail++; }
|
||
}
|
||
|
||
public static void main(String[] args) {
|
||
System.out.println("=== mbedtls-0001: ALPN parse O(S×C) defect ===\n");
|
||
|
||
String[] serverList = {"h2", "http/1.1", "grpc"};
|
||
|
||
// Test 1: match on first server preference
|
||
byte[][] client1 = {name("h2"), name("http/1.0")};
|
||
check("defective: picks h2 (server pref)", "h2".equals(defectiveSelect(serverList, client1)));
|
||
check("fixed: picks h2 (server pref)", "h2".equals(fixedSelect(serverList, client1)));
|
||
|
||
// Test 2: match on second server preference
|
||
byte[][] client2 = {name("http/1.0"), name("http/1.1")};
|
||
check("defective: picks http/1.1", "http/1.1".equals(defectiveSelect(serverList, client2)));
|
||
check("fixed: picks http/1.1", "http/1.1".equals(fixedSelect(serverList, client2)));
|
||
|
||
// Test 3: no match
|
||
byte[][] client3 = {name("ftp"), name("smtp")};
|
||
check("defective: no match → null", defectiveSelect(serverList, client3) == null);
|
||
check("fixed: no match → null", fixedSelect(serverList, client3) == null);
|
||
|
||
// Test 4: server preference wins (h2 beats http/1.1 even if client listed it second)
|
||
byte[][] client4 = {name("http/1.1"), name("h2")};
|
||
check("defective: server-order preference",
|
||
"h2".equals(defectiveSelect(serverList, client4)));
|
||
check("fixed: server-order preference",
|
||
"h2".equals(fixedSelect(serverList, client4)));
|
||
|
||
// Test 5: complexity — adversarial input
|
||
int S = 10;
|
||
int C = 500;
|
||
String[] bigServer = new String[S];
|
||
for (int i = 0; i < S; i++) bigServer[i] = "proto-server-" + i;
|
||
|
||
byte[][] bigClient = new byte[C][];
|
||
for (int i = 0; i < C - 1; i++) bigClient[i] = name("proto-client-" + i);
|
||
bigClient[C - 1] = name(bigServer[S - 1]); // match at last server position
|
||
|
||
ops[0] = 0; ops[1] = 0;
|
||
String rd = defectiveCounting(bigServer, bigClient);
|
||
String rf = fixedCounting(bigServer, bigClient);
|
||
|
||
System.out.println("\n Complexity comparison (S=" + S + ", C=" + C + "):");
|
||
System.out.println(" Defective ops: " + ops[0]);
|
||
System.out.println(" Fixed ops: " + ops[1]);
|
||
System.out.printf(" Speedup: %.1fx%n", (double) ops[0] / ops[1]);
|
||
|
||
check("defective and fixed agree", java.util.Objects.equals(rd, rf));
|
||
check("defective ops > 4x fixed ops", ops[0] > 4 * ops[1]);
|
||
|
||
System.out.println("\n--- " + (pass + fail) + " tests: " + pass + " passed, " + fail + " failed ---");
|
||
if (fail > 0) System.exit(1);
|
||
}
|
||
}
|