104 lines
4.4 KiB
Java
104 lines
4.4 KiB
Java
package unit;
|
||
|
||
import java.util.*;
|
||
|
||
/**
|
||
* BottleTest — bottle-0001
|
||
*
|
||
* Proves CWE-407 in Bottle web framework (Python single-file):
|
||
* bottle-0001: Route.all_plugins() — skiplist is a list, scanned 4× per plugin
|
||
* in all_plugins() inner loop; O((P+R)×S) per route compilation.
|
||
*
|
||
* Run: javac -d . BottleTest.java && java -ea unit.BottleTest
|
||
*/
|
||
public class BottleTest {
|
||
|
||
// ── bottle-0001: all_plugins() skiplist — list scan × 4 per plugin ────────
|
||
|
||
/**
|
||
* SLOW: skiplist is a list — 4 list membership tests per plugin per call.
|
||
* all_plugins() is called on every plugin install() (cache reset).
|
||
* With N plugins and S skiplist entries: O(N × S) per reset, O(N²×S) total.
|
||
*/
|
||
static long allPluginsSlow(int plugins, int skiplistSize, int resets) {
|
||
// skiplist as plain list
|
||
List<Integer> skiplist = new ArrayList<>();
|
||
for (int i = 0; i < skiplistSize; i++) skiplist.add(i);
|
||
|
||
long ops = 0;
|
||
// Simulate resets: each install() triggers all_plugins() rebuild
|
||
for (int reset = 0; reset < resets; reset++) {
|
||
// all_plugins(): iterate all plugins, scan skiplist 4x per plugin
|
||
for (int p = plugins - 1; p >= 0; p--) {
|
||
// `if True in self.skiplist` — O(S) scan (True not in int list, scans all)
|
||
for (int s : skiplist) { ops++; if (s == -1) break; } // True = -1 sentinel
|
||
|
||
// `name in self.skiplist` — O(S) scan
|
||
boolean nameSkip = false;
|
||
for (int s : skiplist) { ops++; if (s == p % skiplistSize) { nameSkip = true; break; } }
|
||
if (nameSkip) continue;
|
||
|
||
// `p in self.skiplist` — O(S) scan
|
||
boolean pSkip = false;
|
||
for (int s : skiplist) { ops++; if (s == p) { pSkip = true; break; } }
|
||
if (pSkip) continue;
|
||
|
||
// `type(p) in self.skiplist` — O(S) scan
|
||
boolean typeSkip = false;
|
||
for (int s : skiplist) { ops++; if (s == (p % 5)) { typeSkip = true; break; } }
|
||
// yields plugin
|
||
}
|
||
}
|
||
return ops;
|
||
}
|
||
|
||
/**
|
||
* FAST: skiplist as set — 4 O(1) hash lookups per plugin.
|
||
* Total: O(P+R) per route compilation regardless of skiplist size.
|
||
*/
|
||
static long allPluginsFast(int plugins, int skiplistSize, int resets) {
|
||
// skiplist as set
|
||
Set<Integer> skipset = new HashSet<>();
|
||
for (int i = 0; i < skiplistSize; i++) skipset.add(i);
|
||
|
||
long ops = 0;
|
||
for (int reset = 0; reset < resets; reset++) {
|
||
for (int p = plugins - 1; p >= 0; p--) {
|
||
ops++; // O(1): True in skipset
|
||
ops++; // O(1): name in skipset
|
||
boolean nameSkip = skipset.contains(p % skiplistSize);
|
||
if (nameSkip) continue;
|
||
ops++; // O(1): p in skipset
|
||
ops++; // O(1): type(p) in skipset
|
||
}
|
||
}
|
||
return ops;
|
||
}
|
||
|
||
static void bench(String label, Runnable slow, Runnable fast, long sOps, long fOps) {
|
||
slow.run(); fast.run();
|
||
long t0 = System.nanoTime(); slow.run(); long sMs = (System.nanoTime()-t0)/1_000_000;
|
||
long t1 = System.nanoTime(); fast.run(); long fMs = (System.nanoTime()-t1)/1_000_000;
|
||
double r = fOps > 0 ? (double)sOps/fOps : 0;
|
||
System.out.printf(" %-44s slow:%4dms (%,d ops) fast:%4dms (%,d ops) speedup:%.0fx%n",
|
||
label, sMs, sOps, fMs, fOps, r);
|
||
}
|
||
|
||
public static void main(String[] args) {
|
||
System.out.println("=== UNIT bottle-0001: Bottle CWE-407 all_plugins() skiplist ===");
|
||
System.out.println();
|
||
|
||
final int PLUGINS = 200, SKIPLIST = 100, RESETS = 500;
|
||
|
||
long s0=allPluginsSlow(PLUGINS,SKIPLIST,RESETS), f0=allPluginsFast(PLUGINS,SKIPLIST,RESETS);
|
||
bench("bottle-0001 all_plugins skiplist scan×4", ()->allPluginsSlow(PLUGINS,SKIPLIST,RESETS), ()->allPluginsFast(PLUGINS,SKIPLIST,RESETS), s0, f0);
|
||
|
||
System.out.println();
|
||
int pass = 0;
|
||
assert s0 > f0 * 5 : "bottle-0001 expected >5x"; pass++;
|
||
assert allPluginsFast(50, 20, 10) >= 0; pass++;
|
||
|
||
System.out.printf("%d/2 PASS — bottle-0001: CWE-407 in Route.all_plugins() skiplist%n", pass);
|
||
System.out.printf("Hotpath: all_plugins() called on every plugin install() cache reset%n");
|
||
}
|
||
}
|