226 lines
8.8 KiB
Java
226 lines
8.8 KiB
Java
import java.util.*;
|
||
import java.util.concurrent.atomic.AtomicLong;
|
||
import java.util.stream.Collectors;
|
||
|
||
/**
|
||
* Unit tests for grpc-java CWE-407 defects.
|
||
*
|
||
* Defects:
|
||
* grpc-java-0001: PriorityLoadBalancer.handleNameResolutionError — priorityNames List.contains()
|
||
* O(C×P) inside child loop. Fix: maintain a parallel HashSet<String>.
|
||
* grpc-java-0002: XdsClientImpl.getActiveAuthorities — returns List<String> when size < 100,
|
||
* used in .contains() inside double-loop over subscribers. Fix: always HashSet.
|
||
* grpc-java-0003: Util.intersect (OkHttp) — O(|first|×|second|) nested loop for cipher suite
|
||
* intersection per TLS handshake. Fix: build HashSet of second, scan first once.
|
||
*
|
||
* Each test simulates the defect using the same data-structure logic,
|
||
* measures op-count ratio (defect vs fix), and asserts ratio > threshold.
|
||
*/
|
||
public class GrpcJavaTest {
|
||
|
||
// -----------------------------------------------------------------------
|
||
// grpc-java-0001: priorityNames List.contains() in handleNameResolutionError
|
||
// -----------------------------------------------------------------------
|
||
|
||
/** Defect: O(C × P) — List.contains per child */
|
||
static long priorityLbHandleErrorDefect(List<String> priorityNames, List<String> children) {
|
||
long ops = 0;
|
||
for (String child : children) {
|
||
// List.contains is O(P)
|
||
for (String p : priorityNames) {
|
||
ops++;
|
||
if (p.equals(child)) break;
|
||
}
|
||
}
|
||
return ops;
|
||
}
|
||
|
||
/** Fix: O(C + P) — HashSet.contains per child */
|
||
static long priorityLbHandleErrorFixed(List<String> priorityNames, List<String> children) {
|
||
long ops = 0;
|
||
Set<String> prioritySet = new HashSet<>(priorityNames); // O(P)
|
||
ops += priorityNames.size();
|
||
for (String child : children) {
|
||
ops++; // O(1) hash lookup
|
||
}
|
||
return ops;
|
||
}
|
||
|
||
static void testGrpcJava0001() {
|
||
int P = 200; // priorities (e.g., localities in a cluster)
|
||
int C = 200; // children (same order of magnitude)
|
||
|
||
List<String> priorityNames = new ArrayList<>();
|
||
for (int i = 0; i < P; i++) priorityNames.add("priority-" + i);
|
||
|
||
// children match at end (worst case for list scan)
|
||
List<String> children = new ArrayList<>(priorityNames);
|
||
Collections.shuffle(children);
|
||
|
||
long defectOps = priorityLbHandleErrorDefect(priorityNames, children);
|
||
long fixedOps = priorityLbHandleErrorFixed(priorityNames, children);
|
||
|
||
double ratio = (double) defectOps / fixedOps;
|
||
System.out.printf("grpc-java-0001: P=%d C=%d defect_ops=%d fixed_ops=%d ratio=%.1fx%n",
|
||
P, C, defectOps, fixedOps, ratio);
|
||
|
||
if (ratio < 10.0) {
|
||
throw new AssertionError("grpc-java-0001: expected ratio >= 10x, got " + ratio);
|
||
}
|
||
System.out.println("grpc-java-0001: PASS");
|
||
}
|
||
|
||
// -----------------------------------------------------------------------
|
||
// grpc-java-0002: getActiveAuthorities returns List, used in .contains()
|
||
// inside double-loop over resourceTypes × subscribers
|
||
// -----------------------------------------------------------------------
|
||
|
||
/** Defect: authorities is a List — contains() is O(A) */
|
||
static long xdsActiveAuthoritiesDefect(
|
||
int resourceTypes, int subscribersPerType, List<String> authoritiesList) {
|
||
long ops = 0;
|
||
// Outer double-loop: resourceTypes × subscribersPerType
|
||
for (int t = 0; t < resourceTypes; t++) {
|
||
for (int s = 0; s < subscribersPerType; s++) {
|
||
String authority = "auth-" + (s % authoritiesList.size());
|
||
// List.contains is O(A)
|
||
for (String a : authoritiesList) {
|
||
ops++;
|
||
if (a.equals(authority)) break;
|
||
}
|
||
}
|
||
}
|
||
return ops;
|
||
}
|
||
|
||
/** Fix: authorities is always a HashSet — contains() is O(1) */
|
||
static long xdsActiveAuthoritiesFixed(
|
||
int resourceTypes, int subscribersPerType, List<String> authoritiesList) {
|
||
long ops = 0;
|
||
Set<String> authoritiesSet = new HashSet<>(authoritiesList); // O(A) once
|
||
ops += authoritiesList.size();
|
||
// Outer double-loop: same structure but O(1) contains
|
||
for (int t = 0; t < resourceTypes; t++) {
|
||
for (int s = 0; s < subscribersPerType; s++) {
|
||
String authority = "auth-" + (s % authoritiesList.size());
|
||
ops++; // O(1) hash lookup
|
||
}
|
||
}
|
||
return ops;
|
||
}
|
||
|
||
static void testGrpcJava0002() {
|
||
int A = 90; // authorities (< 100, in the code's "use list" branch)
|
||
int T = 5; // resource types (LDS/RDS/CDS/EDS/SRDS)
|
||
int S = 1000; // subscribers per type
|
||
|
||
List<String> authorities = new ArrayList<>();
|
||
for (int i = 0; i < A; i++) authorities.add("auth-" + i);
|
||
|
||
long defectOps = xdsActiveAuthoritiesDefect(T, S, authorities);
|
||
long fixedOps = xdsActiveAuthoritiesFixed(T, S, authorities);
|
||
|
||
double ratio = (double) defectOps / fixedOps;
|
||
System.out.printf("grpc-java-0002: A=%d T=%d S=%d defect_ops=%d fixed_ops=%d ratio=%.1fx%n",
|
||
A, T, S, defectOps, fixedOps, ratio);
|
||
|
||
if (ratio < 10.0) {
|
||
throw new AssertionError("grpc-java-0002: expected ratio >= 10x, got " + ratio);
|
||
}
|
||
System.out.println("grpc-java-0002: PASS");
|
||
}
|
||
|
||
// -----------------------------------------------------------------------
|
||
// grpc-java-0003: Util.intersect O(|first|×|second|) per TLS handshake
|
||
// -----------------------------------------------------------------------
|
||
|
||
/** Defect: nested loop intersection — O(N×M) */
|
||
static <T> List<T> intersectDefect(T[] first, T[] second) {
|
||
List<T> result = new ArrayList<>();
|
||
for (T a : first) {
|
||
for (T b : second) {
|
||
if (a.equals(b)) {
|
||
result.add(b);
|
||
break;
|
||
}
|
||
}
|
||
}
|
||
return result;
|
||
}
|
||
|
||
static <T> long countIntersectDefectOps(T[] first, T[] second) {
|
||
long ops = 0;
|
||
for (T a : first) {
|
||
for (T b : second) {
|
||
ops++;
|
||
if (a.equals(b)) break;
|
||
}
|
||
}
|
||
return ops;
|
||
}
|
||
|
||
/** Fix: build HashSet of second, single scan of first — O(N+M) */
|
||
static <T> List<T> intersectFixed(T[] first, T[] second) {
|
||
List<T> result = new ArrayList<>();
|
||
Set<T> secondSet = new LinkedHashSet<>(Arrays.asList(second));
|
||
for (T a : first) {
|
||
if (secondSet.contains(a)) {
|
||
result.add(a);
|
||
}
|
||
}
|
||
return result;
|
||
}
|
||
|
||
static <T> long countIntersectFixedOps(T[] first, T[] second) {
|
||
long ops = second.length; // build set
|
||
ops += first.length; // scan first (O(1) per lookup)
|
||
return ops;
|
||
}
|
||
|
||
static void testGrpcJava0003() {
|
||
// Realistic TLS cipher suite sizes:
|
||
// 'first' = configured grpc cipher list (~25 entries)
|
||
// 'second' = socket.getEnabledCipherSuites (~50 entries)
|
||
int CONFIGURED = 25;
|
||
int ENABLED = 50;
|
||
int HANDSHAKES = 10000; // number of TLS handshakes
|
||
|
||
String[] configured = new String[CONFIGURED];
|
||
String[] enabled = new String[ENABLED];
|
||
|
||
for (int i = 0; i < CONFIGURED; i++) configured[i] = "TLS_CIPHER_" + i;
|
||
for (int i = 0; i < ENABLED; i++) enabled[i] = "TLS_CIPHER_" + (i * 2); // overlap ~12
|
||
|
||
// Verify both produce same result
|
||
List<String> r1 = intersectDefect(configured, enabled);
|
||
List<String> r2 = intersectFixed(configured, enabled);
|
||
if (!r1.equals(r2)) {
|
||
throw new AssertionError("grpc-java-0003: results differ: " + r1 + " vs " + r2);
|
||
}
|
||
|
||
long defectOps = countIntersectDefectOps(configured, enabled) * HANDSHAKES;
|
||
long fixedOps = countIntersectFixedOps(configured, enabled) * HANDSHAKES;
|
||
|
||
double ratio = (double) defectOps / fixedOps;
|
||
System.out.printf(
|
||
"grpc-java-0003: configured=%d enabled=%d handshakes=%d "
|
||
+ "defect_ops=%d fixed_ops=%d ratio=%.1fx%n",
|
||
CONFIGURED, ENABLED, HANDSHAKES, defectOps, fixedOps, ratio);
|
||
|
||
if (ratio < 5.0) {
|
||
throw new AssertionError("grpc-java-0003: expected ratio >= 5x, got " + ratio);
|
||
}
|
||
System.out.println("grpc-java-0003: PASS");
|
||
}
|
||
|
||
// -----------------------------------------------------------------------
|
||
// Main
|
||
// -----------------------------------------------------------------------
|
||
|
||
public static void main(String[] args) {
|
||
testGrpcJava0001();
|
||
testGrpcJava0002();
|
||
testGrpcJava0003();
|
||
System.out.println("ALL PASS");
|
||
}
|
||
}
|