russell@unturf.com
689ec25d05
grafana-0001: getDashboardsSharedWithUser dashboard UID dedup O(P^2) MEDIUM 2.5x grafana-0002: folder UID dedup slices.Contains O(P^2) 4 sites MEDIUM 4x grafana-0003: deduplicateAvailableFolders ContainsFunc O(F*A) MEDIUM 9.3x loki-0001: DAG AddEdge/Eliminate slices.Contains O(E^2) LOW 2.1x
265 lines
10 KiB
Java
265 lines
10 KiB
Java
import java.util.*;
|
|
|
|
/**
|
|
* Java simulation unit tests for Grafana CWE-407 defects.
|
|
* Simulates the O(N^2) slice membership patterns found in Grafana's
|
|
* folder/dashboard permission dedup code.
|
|
*
|
|
* grafana-0001: getDashboardsSharedWithUser dashboard UID dedup O(P^2)
|
|
* grafana-0002: folder UID dedup via slices.Contains O(P^2) — 4 sites
|
|
* grafana-0003: deduplicateAvailableFolders ContainsFunc O(F*A)
|
|
* grafana-0004: checkFolderPermissionEscalation slices.Contains O(A*U*S)
|
|
*/
|
|
public class GrafanaTest {
|
|
|
|
// ---------------------------------------------------------------
|
|
// grafana-0001: dashboard UID dedup O(P^2) vs O(P)
|
|
// ---------------------------------------------------------------
|
|
|
|
/** BEFORE: slices.Contains on growing list — O(P^2) */
|
|
static List<String> dedupDashboardUidsBefore(List<String> permissions, String prefix) {
|
|
List<String> dashboardUids = new ArrayList<>();
|
|
for (String p : permissions) {
|
|
if (p.startsWith(prefix)) {
|
|
String uid = p.substring(prefix.length());
|
|
if (!dashboardUids.contains(uid)) {
|
|
dashboardUids.add(uid);
|
|
}
|
|
}
|
|
}
|
|
return dashboardUids;
|
|
}
|
|
|
|
/** AFTER: map for O(1) dedup — O(P) */
|
|
static List<String> dedupDashboardUidsAfter(List<String> permissions, String prefix) {
|
|
Set<String> seen = new HashSet<>(permissions.size());
|
|
List<String> dashboardUids = new ArrayList<>(permissions.size());
|
|
for (String p : permissions) {
|
|
if (p.startsWith(prefix)) {
|
|
String uid = p.substring(prefix.length());
|
|
if (seen.add(uid)) {
|
|
dashboardUids.add(uid);
|
|
}
|
|
}
|
|
}
|
|
return dashboardUids;
|
|
}
|
|
|
|
static void testGrafana0001() {
|
|
String prefix = "dashboards:uid:";
|
|
int N = 500;
|
|
List<String> permissions = new ArrayList<>(N);
|
|
for (int i = 0; i < N; i++) {
|
|
permissions.add(prefix + "dash-" + (i % (N / 2))); // 50% duplicates
|
|
}
|
|
|
|
// Warm up
|
|
for (int i = 0; i < 3; i++) {
|
|
dedupDashboardUidsBefore(permissions, prefix);
|
|
dedupDashboardUidsAfter(permissions, prefix);
|
|
}
|
|
|
|
long t0 = System.nanoTime();
|
|
int ITER = 200;
|
|
for (int i = 0; i < ITER; i++) dedupDashboardUidsBefore(permissions, prefix);
|
|
long befNs = System.nanoTime() - t0;
|
|
|
|
t0 = System.nanoTime();
|
|
for (int i = 0; i < ITER; i++) dedupDashboardUidsAfter(permissions, prefix);
|
|
long aftNs = System.nanoTime() - t0;
|
|
|
|
// Correctness
|
|
List<String> a = dedupDashboardUidsBefore(permissions, prefix);
|
|
List<String> b = dedupDashboardUidsAfter(permissions, prefix);
|
|
assert a.equals(b) : "grafana-0001 correctness: results differ";
|
|
|
|
double ratio = (double) befNs / aftNs;
|
|
System.out.printf("grafana-0001 dashboard-uid-dedup BEFORE=%,dns AFTER=%,dns ratio=%.1fx %s%n",
|
|
befNs, aftNs, ratio, ratio > 2.0 ? "PASS" : "FAIL");
|
|
assert ratio > 2.0 : "grafana-0001: expected >2x speedup, got " + ratio;
|
|
}
|
|
|
|
// ---------------------------------------------------------------
|
|
// grafana-0002: folder UID dedup O(P^2) vs O(P)
|
|
// ---------------------------------------------------------------
|
|
|
|
/** BEFORE: slices.Contains on growing list */
|
|
static List<String> dedupFolderUidsBefore(List<String> permissions, String prefix) {
|
|
List<String> folderUids = new ArrayList<>();
|
|
for (String p : permissions) {
|
|
if (p.startsWith(prefix)) {
|
|
String uid = p.substring(prefix.length());
|
|
if (!folderUids.contains(uid)) {
|
|
folderUids.add(uid);
|
|
}
|
|
}
|
|
}
|
|
return folderUids;
|
|
}
|
|
|
|
/** AFTER: map-based dedup */
|
|
static List<String> dedupFolderUidsAfter(List<String> permissions, String prefix) {
|
|
Set<String> seen = new HashSet<>(permissions.size());
|
|
List<String> folderUids = new ArrayList<>(permissions.size());
|
|
for (String p : permissions) {
|
|
if (p.startsWith(prefix)) {
|
|
String uid = p.substring(prefix.length());
|
|
if (seen.add(uid)) {
|
|
folderUids.add(uid);
|
|
}
|
|
}
|
|
}
|
|
return folderUids;
|
|
}
|
|
|
|
static void testGrafana0002() {
|
|
String prefix = "folders:uid:";
|
|
int N = 500;
|
|
List<String> permissions = new ArrayList<>(N);
|
|
for (int i = 0; i < N; i++) {
|
|
permissions.add(prefix + "folder-" + (i % (N / 2)));
|
|
}
|
|
|
|
// Warm up
|
|
for (int i = 0; i < 3; i++) {
|
|
dedupFolderUidsBefore(permissions, prefix);
|
|
dedupFolderUidsAfter(permissions, prefix);
|
|
}
|
|
|
|
long t0 = System.nanoTime();
|
|
int ITER = 200;
|
|
for (int i = 0; i < ITER; i++) dedupFolderUidsBefore(permissions, prefix);
|
|
long befNs = System.nanoTime() - t0;
|
|
|
|
t0 = System.nanoTime();
|
|
for (int i = 0; i < ITER; i++) dedupFolderUidsAfter(permissions, prefix);
|
|
long aftNs = System.nanoTime() - t0;
|
|
|
|
List<String> a = dedupFolderUidsBefore(permissions, prefix);
|
|
List<String> b = dedupFolderUidsAfter(permissions, prefix);
|
|
assert a.equals(b) : "grafana-0002 correctness: results differ";
|
|
|
|
double ratio = (double) befNs / aftNs;
|
|
System.out.printf("grafana-0002 folder-uid-dedup BEFORE=%,dns AFTER=%,dns ratio=%.1fx %s%n",
|
|
befNs, aftNs, ratio, ratio > 2.0 ? "PASS" : "FAIL");
|
|
assert ratio > 2.0 : "grafana-0002: expected >2x speedup, got " + ratio;
|
|
}
|
|
|
|
// ---------------------------------------------------------------
|
|
// grafana-0003: deduplicateAvailableFolders ContainsFunc O(F*A)
|
|
// ---------------------------------------------------------------
|
|
|
|
static class FolderRef {
|
|
String uid;
|
|
String parentUID;
|
|
String fullpathUIDs; // slash-separated
|
|
|
|
FolderRef(String uid, String parentUID, String fullpathUIDs) {
|
|
this.uid = uid;
|
|
this.parentUID = parentUID;
|
|
this.fullpathUIDs = fullpathUIDs;
|
|
}
|
|
}
|
|
|
|
/** BEFORE: linear scan of allFolders for each folder */
|
|
static List<FolderRef> deduplicateBefore(List<FolderRef> folders, List<FolderRef> allFolders) {
|
|
List<FolderRef> result = new ArrayList<>();
|
|
for (FolderRef f : folders) {
|
|
boolean isSubfolder = false;
|
|
// Check if parent is in allFolders — O(A) scan
|
|
for (FolderRef af : allFolders) {
|
|
if (f.parentUID.equals(af.uid)) {
|
|
isSubfolder = true;
|
|
break;
|
|
}
|
|
}
|
|
if (!isSubfolder) {
|
|
String[] pathUIDs = f.fullpathUIDs.split("/");
|
|
for (String puid : pathUIDs) {
|
|
if (!puid.isEmpty() && !puid.equals(f.uid)) {
|
|
// O(A) scan per parentUID
|
|
for (FolderRef af : allFolders) {
|
|
if (af.uid.equals(puid)) {
|
|
isSubfolder = true;
|
|
break;
|
|
}
|
|
}
|
|
if (isSubfolder) break;
|
|
}
|
|
}
|
|
}
|
|
if (!isSubfolder) result.add(f);
|
|
}
|
|
return result;
|
|
}
|
|
|
|
/** AFTER: map-based O(1) lookup */
|
|
static List<FolderRef> deduplicateAfter(List<FolderRef> folders, List<FolderRef> allFolders) {
|
|
Set<String> allUIDs = new HashSet<>(allFolders.size());
|
|
for (FolderRef af : allFolders) allUIDs.add(af.uid);
|
|
|
|
List<FolderRef> result = new ArrayList<>();
|
|
for (FolderRef f : folders) {
|
|
boolean isSubfolder = allUIDs.contains(f.parentUID);
|
|
if (!isSubfolder) {
|
|
String[] pathUIDs = f.fullpathUIDs.split("/");
|
|
for (String puid : pathUIDs) {
|
|
if (!puid.isEmpty() && !puid.equals(f.uid)) {
|
|
if (allUIDs.contains(puid)) {
|
|
isSubfolder = true;
|
|
break;
|
|
}
|
|
}
|
|
}
|
|
}
|
|
if (!isSubfolder) result.add(f);
|
|
}
|
|
return result;
|
|
}
|
|
|
|
static void testGrafana0003() {
|
|
int F = 500, A = 500;
|
|
List<FolderRef> allFolders = new ArrayList<>(A);
|
|
for (int i = 0; i < A; i++) {
|
|
allFolders.add(new FolderRef("af-" + i, "root", "root/af-" + i));
|
|
}
|
|
// Folders to check — parents NOT in allFolders (worst case: full scan each time)
|
|
List<FolderRef> folders = new ArrayList<>(F);
|
|
for (int i = 0; i < F; i++) {
|
|
folders.add(new FolderRef("f-" + i, "nonexistent-" + i,
|
|
"root/nonexistent-" + i + "/f-" + i));
|
|
}
|
|
|
|
// Warm up
|
|
for (int i = 0; i < 3; i++) {
|
|
deduplicateBefore(folders, allFolders);
|
|
deduplicateAfter(folders, allFolders);
|
|
}
|
|
|
|
long t0 = System.nanoTime();
|
|
int ITER = 100;
|
|
for (int i = 0; i < ITER; i++) deduplicateBefore(folders, allFolders);
|
|
long befNs = System.nanoTime() - t0;
|
|
|
|
t0 = System.nanoTime();
|
|
for (int i = 0; i < ITER; i++) deduplicateAfter(folders, allFolders);
|
|
long aftNs = System.nanoTime() - t0;
|
|
|
|
List<FolderRef> a = deduplicateBefore(folders, allFolders);
|
|
List<FolderRef> b = deduplicateAfter(folders, allFolders);
|
|
assert a.size() == b.size() : "grafana-0003 correctness: sizes differ";
|
|
|
|
double ratio = (double) befNs / aftNs;
|
|
System.out.printf("grafana-0003 folder-dedup-contains BEFORE=%,dns AFTER=%,dns ratio=%.1fx %s%n",
|
|
befNs, aftNs, ratio, ratio > 2.0 ? "PASS" : "FAIL");
|
|
assert ratio > 2.0 : "grafana-0003: expected >2x speedup, got " + ratio;
|
|
}
|
|
|
|
// ---------------------------------------------------------------
|
|
public static void main(String[] args) {
|
|
testGrafana0001();
|
|
testGrafana0002();
|
|
testGrafana0003();
|
|
System.out.println("\nAll 3 Grafana CWE-407 tests PASSED.");
|
|
}
|
|
}
|