110 lines
3.9 KiB
Java
110 lines
3.9 KiB
Java
package unit;
|
|
|
|
import java.util.*;
|
|
|
|
/**
|
|
* Standalone unit test for grafana-0002: CWE-407.
|
|
*
|
|
* grafana-0002: Folder/dashboard permission UID deduplication O(P²)
|
|
* slow() mirrors the defective pattern: for each of P permission strings,
|
|
* calls slices.Contains on the growing result slice — O(P) per iteration.
|
|
* Total cost: O(P²).
|
|
* fast() uses a HashMap seen-set for O(1) membership; total cost O(P).
|
|
* Assert: slowOps > fastOps * 5x for P=500 permissions (all distinct UIDs).
|
|
*
|
|
* Models four affected sites in folder.go (lines 253, 451, 544) and
|
|
* dashboard_service.go (line 1534).
|
|
*/
|
|
public class Grafana0002FolderPermDedupTest {
|
|
|
|
static final String SCOPE_PREFIX = "folders:uid:";
|
|
|
|
/**
|
|
* Slow path — slices.Contains on growing result slice: O(P²).
|
|
*/
|
|
static long slowPermDedup(List<String> permissions) {
|
|
long ops = 0;
|
|
List<String> uids = new ArrayList<>();
|
|
for (String p : permissions) {
|
|
if (p.startsWith(SCOPE_PREFIX)) {
|
|
String uid = p.substring(SCOPE_PREFIX.length());
|
|
// slices.Contains(uids, uid) — O(uids.size()) linear scan
|
|
boolean found = false;
|
|
for (String existing : uids) {
|
|
ops++;
|
|
if (existing.equals(uid)) { found = true; break; }
|
|
}
|
|
if (!found) {
|
|
uids.add(uid);
|
|
}
|
|
}
|
|
}
|
|
return ops;
|
|
}
|
|
|
|
/**
|
|
* Fast path — HashMap seen-set: O(P) total.
|
|
*/
|
|
static long fastPermDedup(List<String> permissions) {
|
|
long ops = 0;
|
|
Map<String, Boolean> seen = new HashMap<>();
|
|
List<String> uids = new ArrayList<>();
|
|
for (String p : permissions) {
|
|
if (p.startsWith(SCOPE_PREFIX)) {
|
|
String uid = p.substring(SCOPE_PREFIX.length());
|
|
ops++; // O(1) map lookup
|
|
if (!seen.containsKey(uid)) {
|
|
seen.put(uid, true);
|
|
uids.add(uid);
|
|
}
|
|
}
|
|
}
|
|
return ops;
|
|
}
|
|
|
|
static void testFolderPermDedup() {
|
|
int P = 500; // permission entries — all distinct UIDs (worst case, no dupes)
|
|
|
|
List<String> perms = new ArrayList<>(P);
|
|
for (int i = 0; i < P; i++) {
|
|
perms.add(SCOPE_PREFIX + "folder-uid-" + i);
|
|
}
|
|
|
|
long sOps = slowPermDedup(perms);
|
|
long fOps = fastPermDedup(perms);
|
|
|
|
int minRatio = 5;
|
|
boolean pass = sOps > fOps * minRatio;
|
|
System.out.printf("grafana-0002 [P=%d all-distinct]: slow=%d fast=%d ratio=%.1fx — %s%n",
|
|
P, sOps, fOps, (double) sOps / fOps, pass ? "PASS" : "FAIL");
|
|
if (!pass) throw new AssertionError("grafana-0002 FAIL: slow=" + sOps + " fast=" + fOps);
|
|
}
|
|
|
|
static void testFolderPermDedupWithDuplicates() {
|
|
int P = 500; // permission entries — 50 unique UIDs, 10 dupes each
|
|
int UNIQUE = 50;
|
|
|
|
List<String> perms = new ArrayList<>(P);
|
|
for (int i = 0; i < P; i++) {
|
|
perms.add(SCOPE_PREFIX + "folder-uid-" + (i % UNIQUE));
|
|
}
|
|
|
|
long sOps = slowPermDedup(perms);
|
|
long fOps = fastPermDedup(perms);
|
|
|
|
// With duplicates, slow still scans the full seen-slice for each entry
|
|
// After the first UNIQUE entries are collected, each subsequent entry
|
|
// scans all UNIQUE already-collected items before finding the hit.
|
|
int minRatio = 5;
|
|
boolean pass = sOps > fOps * minRatio;
|
|
System.out.printf("grafana-0002 [P=%d 50-unique 10x-dupes]: slow=%d fast=%d ratio=%.1fx — %s%n",
|
|
P, sOps, fOps, (double) sOps / fOps, pass ? "PASS" : "FAIL");
|
|
if (!pass) throw new AssertionError("grafana-0002 dup FAIL: slow=" + sOps + " fast=" + fOps);
|
|
}
|
|
|
|
public static void main(String[] args) {
|
|
testFolderPermDedup();
|
|
testFolderPermDedupWithDuplicates();
|
|
System.out.println("2/2 PASS");
|
|
}
|
|
}
|