195 lines
7.9 KiB
Java
195 lines
7.9 KiB
Java
package unit;
|
||
|
||
import java.util.*;
|
||
|
||
/**
|
||
* GoEthereumTest — CWE-407 benchmark for go-ethereum-0001
|
||
*
|
||
* go-ethereum-0001: txpool/legacypool lookup.addAuthorities() — auths slice O(N²)
|
||
* Real code (core/txpool/legacypool/legacypool.go):
|
||
* auths map[common.Address][]common.Hash // slice per authority
|
||
*
|
||
* func (t *lookup) addAuthorities(tx *types.Transaction) {
|
||
* for _, addr := range tx.SetCodeAuthorities() {
|
||
* list, ok := t.auths[addr]
|
||
* if !ok { list = []common.Hash{} }
|
||
* if slices.Contains(list, tx.Hash()) { // O(N) scan
|
||
* continue
|
||
* }
|
||
* list = append(list, tx.Hash())
|
||
* t.auths[addr] = list
|
||
* }
|
||
* }
|
||
*
|
||
* When many txs share the same authority address, the slice for that address
|
||
* grows to length N and each Contains() call scans the whole list: O(N) per
|
||
* insertion, O(N²) total.
|
||
*
|
||
* Fix: change auths to map[common.Address]map[common.Hash]struct{} — O(1) lookup.
|
||
*
|
||
* func (t *lookup) addAuthorities(tx *types.Transaction) {
|
||
* for _, addr := range tx.SetCodeAuthorities() {
|
||
* set, ok := t.auths[addr]
|
||
* if !ok {
|
||
* set = make(map[common.Hash]struct{})
|
||
* t.auths[addr] = set
|
||
* }
|
||
* if _, dup := set[tx.Hash()]; dup { continue }
|
||
* set[tx.Hash()] = struct{}{}
|
||
* }
|
||
* }
|
||
*/
|
||
public class GoEthereumTest {
|
||
|
||
// --- Defective implementation: auths as map[addr][]hash (slice) ---
|
||
|
||
/**
|
||
* Simulates lookup.addAuthorities() with a slice per authority address.
|
||
*
|
||
* @param N number of distinct tx hashes to add under one authority
|
||
* @return total comparison operations performed (slices.Contains scans)
|
||
*/
|
||
static long slowAddAuthorities(int N) {
|
||
// auths: map[address][]hash — one entry, one authority address
|
||
Map<String, List<String>> auths = new HashMap<>();
|
||
long ops = 0;
|
||
for (int i = 0; i < N; i++) {
|
||
String addr = "authority_0";
|
||
String hash = "tx_hash_" + i;
|
||
List<String> list = auths.computeIfAbsent(addr, k -> new ArrayList<>());
|
||
// slices.Contains — O(current list length)
|
||
boolean dup = false;
|
||
for (int j = 0; j < list.size(); j++) {
|
||
ops++;
|
||
if (list.get(j).equals(hash)) { dup = true; break; }
|
||
}
|
||
if (!dup) list.add(hash);
|
||
}
|
||
return ops;
|
||
}
|
||
|
||
/**
|
||
* Simulates lookup.addAuthorities() with a set per authority address (the fix).
|
||
*
|
||
* @param N number of distinct tx hashes to add under one authority
|
||
* @return total comparison operations performed (map probes, each O(1))
|
||
*/
|
||
static long fastAddAuthorities(int N) {
|
||
// auths: map[address]map[hash]struct{} — O(1) lookup
|
||
Map<String, Set<String>> auths = new HashMap<>();
|
||
long ops = 0;
|
||
for (int i = 0; i < N; i++) {
|
||
String addr = "authority_0";
|
||
String hash = "tx_hash_" + i;
|
||
Set<String> set = auths.computeIfAbsent(addr, k -> new HashSet<>());
|
||
ops++; // one O(1) probe (contains + add combined)
|
||
set.add(hash);
|
||
}
|
||
return ops;
|
||
}
|
||
|
||
// --- Benchmark harness ---
|
||
|
||
static void bench(String label, Runnable slow, Runnable fast, long sOps, long fOps) {
|
||
// warm up
|
||
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 ratio = (double) sOps / Math.max(fOps, 1);
|
||
System.out.printf(" %-55s slow: %5dms (%,d ops) fast: %5dms (%,d ops) op-ratio: %.0fx%n",
|
||
label, sMs, sOps, fMs, fOps, ratio);
|
||
}
|
||
|
||
public static void main(String[] args) {
|
||
System.out.println("GoEthereumTest — go-ethereum-0001: txpool lookup.addAuthorities() slice O(N²) vs map O(N)");
|
||
System.out.println();
|
||
|
||
System.out.println(" [go-ethereum-0001: addAuthorities() dedup check]");
|
||
int[] cases = {100, 500, 1000};
|
||
for (int N : cases) {
|
||
long sOps = slowAddAuthorities(N);
|
||
long fOps = fastAddAuthorities(N);
|
||
bench(
|
||
String.format("N=%d txs, 1 authority address", N),
|
||
() -> slowAddAuthorities(N),
|
||
() -> fastAddAuthorities(N),
|
||
sOps, fOps
|
||
);
|
||
}
|
||
|
||
System.out.println();
|
||
|
||
// --- Assertions ---
|
||
int pass = 0;
|
||
|
||
// 1. Slice approach is O(N²): total ops for N unique hashes = 0+1+2+…+(N-1) = N*(N-1)/2
|
||
// For N=1000 that's 499,500 ops. Map is N=1000 ops. Ratio ~500x.
|
||
{
|
||
int N = 1000;
|
||
long sOps = slowAddAuthorities(N);
|
||
long fOps = fastAddAuthorities(N);
|
||
long expected_slow = (long) N * (N - 1) / 2; // 499500
|
||
assert sOps == expected_slow
|
||
: "go-ethereum-0001 slow op count mismatch: got=" + sOps + " expected=" + expected_slow;
|
||
assert fOps == N
|
||
: "go-ethereum-0001 fast op count mismatch: got=" + fOps + " expected=" + N;
|
||
double ratio = (double) sOps / fOps;
|
||
assert ratio > 200
|
||
: "go-ethereum-0001 expected >200x op-ratio; got " + ratio;
|
||
System.out.printf(" PASS go-ethereum-0001: N=%d, slow=%,d ops, fast=%,d ops, ratio=%.0fx%n",
|
||
N, sOps, fOps, ratio);
|
||
pass++;
|
||
}
|
||
|
||
// 2. Duplicate insertion: slice and map both reject duplicates, same count
|
||
{
|
||
// Add same hash twice — only one should be retained
|
||
Map<String, List<String>> sliceMap = new HashMap<>();
|
||
List<String> list = sliceMap.computeIfAbsent("addr", k -> new ArrayList<>());
|
||
String hash = "tx_0";
|
||
if (!list.contains(hash)) list.add(hash);
|
||
if (!list.contains(hash)) list.add(hash);
|
||
assert list.size() == 1 : "slice dedup failed: size=" + list.size();
|
||
|
||
Map<String, Set<String>> setMap = new HashMap<>();
|
||
Set<String> set = setMap.computeIfAbsent("addr", k -> new HashSet<>());
|
||
set.add(hash);
|
||
set.add(hash);
|
||
assert set.size() == 1 : "map dedup failed: size=" + set.size();
|
||
|
||
System.out.printf(" PASS duplicate-rejection: slice.size=%d, set.size=%d%n",
|
||
list.size(), set.size());
|
||
pass++;
|
||
}
|
||
|
||
// 3. Remove: map supports O(1) delete vs slice's O(N) index scan
|
||
// Verify correctness of remove-by-key semantics
|
||
{
|
||
Map<String, Set<String>> setMap = new HashMap<>();
|
||
Set<String> set = setMap.computeIfAbsent("addr", k -> new HashSet<>());
|
||
for (int i = 0; i < 5; i++) set.add("tx_" + i);
|
||
set.remove("tx_2");
|
||
assert !set.contains("tx_2") : "map remove failed";
|
||
assert set.size() == 4 : "map remove size wrong: " + set.size();
|
||
if (set.isEmpty()) setMap.remove("addr");
|
||
set.clear();
|
||
setMap.computeIfAbsent("addr", k -> new HashSet<>());
|
||
setMap.get("addr").add("tx_x");
|
||
setMap.get("addr").remove("tx_x");
|
||
if (setMap.get("addr").isEmpty()) setMap.remove("addr");
|
||
assert !setMap.containsKey("addr") : "empty-set cleanup failed";
|
||
System.out.printf(" PASS remove-authority: O(1) delete, empty-cleanup correct%n");
|
||
pass++;
|
||
}
|
||
|
||
System.out.println();
|
||
System.out.printf("%d/3 PASS%n", pass);
|
||
System.out.printf("go-ethereum-0001: txpool lookup.addAuthorities() auths []hash → map[hash]struct{} O(N²) → O(N)%n");
|
||
System.out.printf("Hotpath: every EIP-7702 set-code tx added to pool; worst case O(T×I) per authority%n");
|
||
if (pass < 3) {
|
||
System.out.println("FAIL");
|
||
System.exit(1);
|
||
}
|
||
System.out.println("ALL PASS");
|
||
}
|
||
}
|