276 lines
11 KiB
Java
276 lines
11 KiB
Java
package unit;
|
||
|
||
import java.util.*;
|
||
|
||
/**
|
||
* Unit test for actix-web-0001 and actix-web-0002: CWE-407 in actix-web.
|
||
*
|
||
* actix-web-0001 (MEDIUM):
|
||
* File: actix-web/src/introspection.rs:984-989
|
||
* Symbol: update_unique — Vec::contains() inside a for loop
|
||
* Defect: Deduplication of route introspection data uses Vec::contains()
|
||
* which is O(N) per item. For M new items merged into an existing
|
||
* Vec of size N: O(N × M) total.
|
||
* Fix: Build a HashSet from existing items; each insertion is O(1).
|
||
* Total: O(N + M).
|
||
*
|
||
* actix-web-0002 (MEDIUM):
|
||
* File: actix-web-actors/src/ws.rs:431-435
|
||
* Symbol: handshake_with_protocols — protocols.iter().any() in .find()
|
||
* Defect: WebSocket protocol negotiation: for each client-requested protocol
|
||
* (R total), scan the server's supported list (P total): O(R × P)
|
||
* per upgrade request.
|
||
* Fix: Pre-build HashSet<&str> from server protocols at handshake start.
|
||
* Each client protocol check is then O(1). Total: O(P + R).
|
||
*
|
||
* Modeled here in Java:
|
||
* Rust Vec::contains() ≡ List<String> linear scan (defective)
|
||
* Rust HashSet::contains() ≡ HashSet<String> lookup (fixed)
|
||
* Comparison counts tracked at the membership-test site.
|
||
*
|
||
* Expected at N=M=200 (actix-web-0001):
|
||
* defective comparisons ≈ N × M = 40,000
|
||
* fixed comparisons ≈ N + M = 400
|
||
* ratio > 50×
|
||
*
|
||
* Expected at R=P=50 (actix-web-0002):
|
||
* defective comparisons = R × P = 2,500
|
||
* fixed comparisons = R = 50
|
||
* ratio = 50×
|
||
*/
|
||
public class ActixWebIntrospectionTest {
|
||
|
||
// =========================================================================
|
||
// actix-web-0001 model: update_unique with Vec vs HashSet
|
||
// =========================================================================
|
||
|
||
/**
|
||
* Defective update_unique: uses List.contains() (O(N) scan) inside loop.
|
||
* comparisons counts every element examined in contains().
|
||
*/
|
||
static long updateUniqueDefective(List<String> existing, List<String> newItems,
|
||
long[] comparisons) {
|
||
for (String item : newItems) {
|
||
// existing.contains(item) — O(existing.size()) linear scan
|
||
boolean found = false;
|
||
for (String x : existing) {
|
||
comparisons[0]++;
|
||
if (x.equals(item)) { found = true; break; }
|
||
}
|
||
if (!found) existing.add(item);
|
||
}
|
||
return comparisons[0];
|
||
}
|
||
|
||
/**
|
||
* Fixed update_unique: builds a HashSet from existing, then inserts each
|
||
* new item with O(1) HashSet.add (which returns false if already present).
|
||
* comparisons counts one hash-probe per item.
|
||
*/
|
||
static long updateUniqueFixed(List<String> existing, List<String> newItems,
|
||
long[] comparisons) {
|
||
Set<String> seen = new HashSet<>(existing);
|
||
for (String item : newItems) {
|
||
comparisons[0]++; // O(1) HashSet.add
|
||
if (seen.add(item)) {
|
||
existing.add(item);
|
||
}
|
||
}
|
||
return comparisons[0];
|
||
}
|
||
|
||
// =========================================================================
|
||
// actix-web-0002 model: WebSocket protocol negotiation, slice vs HashSet
|
||
// =========================================================================
|
||
|
||
/**
|
||
* Defective protocol negotiation: for each client protocol, scan server
|
||
* protocols linearly (protocols.iter().any()).
|
||
* Returns the first matched protocol, or null.
|
||
* comparisons counts every element examined in the inner any() scan.
|
||
*/
|
||
static String negotiateDefective(List<String> clientProtocols,
|
||
List<String> serverProtocols,
|
||
long[] comparisons) {
|
||
for (String req : clientProtocols) {
|
||
// protocols.iter().any(|p| p == req_p) — O(P) scan
|
||
for (String srv : serverProtocols) {
|
||
comparisons[0]++;
|
||
if (srv.equals(req)) {
|
||
return req; // first match wins
|
||
}
|
||
}
|
||
}
|
||
return null;
|
||
}
|
||
|
||
/**
|
||
* Fixed protocol negotiation: pre-build HashSet from server protocols,
|
||
* then check each client protocol with O(1) lookup.
|
||
* comparisons counts one hash-probe per client protocol.
|
||
*/
|
||
static String negotiateFixed(List<String> clientProtocols,
|
||
List<String> serverProtocols,
|
||
long[] comparisons) {
|
||
// Build HashSet once: O(P)
|
||
Set<String> serverSet = new HashSet<>(serverProtocols);
|
||
for (String req : clientProtocols) {
|
||
comparisons[0]++; // O(1) HashSet.contains
|
||
if (serverSet.contains(req)) {
|
||
return req;
|
||
}
|
||
}
|
||
return null;
|
||
}
|
||
|
||
// =========================================================================
|
||
// Tests
|
||
// =========================================================================
|
||
|
||
/**
|
||
* Test 1 — Correctness: defective and fixed update_unique produce same result.
|
||
*
|
||
* Existing: 50 unique strings. New: 50 strings (25 overlap + 25 novel).
|
||
*/
|
||
static void testUpdateUniqueCorrectnessMatch() {
|
||
List<String> existing1 = new ArrayList<>();
|
||
List<String> existing2 = new ArrayList<>();
|
||
List<String> newItems = new ArrayList<>();
|
||
|
||
for (int i = 0; i < 50; i++) {
|
||
existing1.add("item-" + i);
|
||
existing2.add("item-" + i);
|
||
}
|
||
// 25 overlap (already in existing) + 25 novel
|
||
for (int i = 25; i < 75; i++) newItems.add("item-" + i);
|
||
|
||
long[] c1 = {0}, c2 = {0};
|
||
updateUniqueDefective(existing1, newItems, c1);
|
||
updateUniqueFixed(existing2, newItems, c2);
|
||
|
||
assert new HashSet<>(existing1).equals(new HashSet<>(existing2))
|
||
: "update_unique results differ";
|
||
assert existing1.size() == 75
|
||
: "expected 75 items (50 original + 25 novel); got " + existing1.size();
|
||
|
||
System.out.println("PASS testUpdateUniqueCorrectnessMatch");
|
||
}
|
||
|
||
/**
|
||
* Test 2 — actix-web-0001: update_unique ratio at N=M=200.
|
||
*
|
||
* 200 existing items, 200 new unique items (no overlap — worst case for scan).
|
||
* Defective: sum of scan sizes = 200 + 201 + ... + 399 ≈ O(N×M).
|
||
* Fixed: 200 HashSet probes = O(M).
|
||
* Ratio > 50×.
|
||
*/
|
||
static void testUpdateUniqueRatioAtScale() {
|
||
int N = 200, M = 200;
|
||
|
||
List<String> existing1 = new ArrayList<>();
|
||
List<String> existing2 = new ArrayList<>();
|
||
for (int i = 0; i < N; i++) {
|
||
existing1.add("e" + i);
|
||
existing2.add("e" + i);
|
||
}
|
||
// New items are all unique (no overlap) — worst case
|
||
List<String> newItems = new ArrayList<>();
|
||
for (int i = 0; i < M; i++) newItems.add("n" + i);
|
||
|
||
long[] defComp = {0}, fixComp = {0};
|
||
updateUniqueDefective(existing1, newItems, defComp);
|
||
updateUniqueFixed(existing2, newItems, fixComp);
|
||
|
||
assert new HashSet<>(existing1).equals(new HashSet<>(existing2))
|
||
: "result mismatch";
|
||
|
||
// Defective: scan sizes are N, N+1, ..., N+M-1 (each novel item extends list)
|
||
long expectedDef = (long) N * M + (long) M * (M - 1) / 2;
|
||
assert defComp[0] == expectedDef
|
||
: "defective comparisons should be " + expectedDef + "; got " + defComp[0];
|
||
|
||
// Fixed: M probes
|
||
assert fixComp[0] == M
|
||
: "fixed comparisons should be M=" + M + "; got " + fixComp[0];
|
||
|
||
double ratio = (double) defComp[0] / fixComp[0];
|
||
assert ratio > 50.0
|
||
: "ratio should be >50× at N=M=200; got " + ratio;
|
||
|
||
System.out.printf(
|
||
"PASS testUpdateUniqueRatioAtScale (N=%d M=%d defective=%d fixed=%d ratio=%.1fx)%n",
|
||
N, M, defComp[0], fixComp[0], ratio);
|
||
}
|
||
|
||
/**
|
||
* Test 3 — actix-web-0002 Correctness: both negotiators find same protocol.
|
||
*
|
||
* Client requests ["graphql-ws", "chat", "json-patch"].
|
||
* Server supports ["json-patch", "graphql-ws"].
|
||
* First match should be "graphql-ws" (first in client list that server knows).
|
||
*/
|
||
static void testNegotiateCorrectnessMatch() {
|
||
List<String> client = Arrays.asList("graphql-ws", "chat", "json-patch");
|
||
List<String> server = Arrays.asList("json-patch", "graphql-ws");
|
||
|
||
long[] c1 = {0}, c2 = {0};
|
||
String defResult = negotiateDefective(client, server, c1);
|
||
String fixResult = negotiateFixed(client, server, c2);
|
||
|
||
assert "graphql-ws".equals(defResult)
|
||
: "defective should find 'graphql-ws'; got " + defResult;
|
||
assert defResult.equals(fixResult)
|
||
: "negotiation result mismatch: defective=" + defResult + " fixed=" + fixResult;
|
||
|
||
System.out.println("PASS testNegotiateCorrectnessMatch");
|
||
}
|
||
|
||
/**
|
||
* Test 4 — actix-web-0002: protocol negotiation ratio at R=P=50, no match (worst case).
|
||
*
|
||
* No overlap between client and server protocols — full scan required.
|
||
* Defective: R × P = 50 × 50 = 2,500 comparisons.
|
||
* Fixed: R = 50 comparisons (one HashSet probe per client protocol).
|
||
* Ratio = 50×.
|
||
*/
|
||
static void testNegotiateRatioAtScale() {
|
||
int R = 50, P = 50;
|
||
|
||
List<String> client = new ArrayList<>();
|
||
List<String> server = new ArrayList<>();
|
||
// No overlap: client protocols start with "c-", server with "s-"
|
||
for (int i = 0; i < R; i++) client.add("c-" + i);
|
||
for (int i = 0; i < P; i++) server.add("s-" + i);
|
||
|
||
long[] defComp = {0}, fixComp = {0};
|
||
String defResult = negotiateDefective(client, server, defComp);
|
||
String fixResult = negotiateFixed(client, server, fixComp);
|
||
|
||
assert defResult == null : "defective should return null (no match); got " + defResult;
|
||
assert fixResult == null : "fixed should return null (no match); got " + fixResult;
|
||
|
||
long expectedDef = (long) R * P;
|
||
assert defComp[0] == expectedDef
|
||
: "defective comparisons should be R*P=" + expectedDef + "; got " + defComp[0];
|
||
assert fixComp[0] == R
|
||
: "fixed comparisons should be R=" + R + "; got " + fixComp[0];
|
||
|
||
double ratio = (double) defComp[0] / fixComp[0];
|
||
assert ratio == P
|
||
: "ratio should be P=" + P + "; got " + ratio;
|
||
|
||
System.out.printf(
|
||
"PASS testNegotiateRatioAtScale (R=%d P=%d defective=%d fixed=%d ratio=%.1fx)%n",
|
||
R, P, defComp[0], fixComp[0], ratio);
|
||
}
|
||
|
||
// =========================================================================
|
||
|
||
public static void main(String[] args) {
|
||
testUpdateUniqueCorrectnessMatch();
|
||
testUpdateUniqueRatioAtScale();
|
||
testNegotiateCorrectnessMatch();
|
||
testNegotiateRatioAtScale();
|
||
System.out.println("4/4 PASS");
|
||
}
|
||
}
|