russell@unturf.com
d4ed2dff91
Hibernate (5 HIGH): addColumn/addReferencedColumn/addIndex ArrayList→LinkedHashSet (19x) FK second-pass LinkedHashSet, orderHierarchy LinkedHashSet MyBatis (1 MEDIUM): sortConstructorMappings indexOf→HashMap (12x) EF Core (2 HIGH + 1 MEDIUM): FindGenerationProperty HashSet (250x), AddPrincipals HashSet (250x), FK discovery HashSet (6x) Diesel (3 MEDIUM): SQLite/MySQL row position()→BTreeMap (51x) SQLAlchemy (2 HIGH): _values_bindparam Set (500x), evaluated_keys Set (500x) Peewee (1 MEDIUM): _SortedFieldList.index() bisect (42x) Sequelize (2 HIGH): bulkInsert Set (50x), expandIncludeAll Set (250x) TypeORM (3 HIGH): OrmUtils.uniq Map (500x), diffColumns Set (125x), updatedColumns Set (100x) Doctrine ORM (1 HIGH + 2 MEDIUM): hydrator discriminator (26x), addSubClass (250x), SqlWalker partial (130x) GORM (1 MEDIUM): sortCallbacks getRIndex→map (194x) SQLite: SqliteTest unit proof 4/4 PASS (101x) Unit tests: all PASS — Hibernate/MyBatis/EfCore/Diesel/SQLAlchemy/Peewee/ Sequelize/TypeORM/Doctrine/GORM Whitepaper: 157 sites, 62 ecosystems; PDF 752K
89 lines
3.5 KiB
Java
89 lines
3.5 KiB
Java
package unit;
|
||
|
||
import java.util.*;
|
||
|
||
/**
|
||
* PeeweeTest — peewee-0001
|
||
*
|
||
* Proves CWE-407 in Peewee ORM:
|
||
* peewee-0001: _SortedFieldList.index() — list.index(field._sort_key) O(N) linear scan
|
||
* Called repeatedly when accessing field metadata. Fix: bisect for O(log N).
|
||
*
|
||
* Run: javac -d . PeeweeTest.java && java -ea unit.PeeweeTest
|
||
*/
|
||
public class PeeweeTest {
|
||
|
||
// ── peewee-0001: _SortedFieldList.index() ────────────────────────────────
|
||
|
||
/**
|
||
* SLOW: mirrors _SortedFieldList.index() before fix.
|
||
* _keys.index(field._sort_key) is O(N) linear scan.
|
||
* Called once per field access during query compilation.
|
||
* O(F × N) for F accesses on a model with N fields.
|
||
*/
|
||
static long sortedFieldListSlow(int numFields, int numAccesses) {
|
||
List<Integer> keys = new ArrayList<>();
|
||
for (int i = 0; i < numFields; i++) keys.add(i);
|
||
long ops = 0;
|
||
for (int a = 0; a < numAccesses; a++) {
|
||
// Access field at position that varies across accesses (worst case: back half)
|
||
int target = numFields / 2 + (a % (numFields / 2));
|
||
// list.index() — O(N) scan
|
||
for (int i = 0; i < keys.size(); i++) {
|
||
ops++;
|
||
if (keys.get(i).equals(target)) break;
|
||
}
|
||
}
|
||
return ops;
|
||
}
|
||
|
||
/**
|
||
* FAST: mirrors _SortedFieldList.index() after fix.
|
||
* bisect_left(self._keys, k) is O(log N).
|
||
* O(F × log N) total.
|
||
*/
|
||
static long sortedFieldListFast(int numFields, int numAccesses) {
|
||
List<Integer> keys = new ArrayList<>();
|
||
for (int i = 0; i < numFields; i++) keys.add(i);
|
||
long ops = 0;
|
||
for (int a = 0; a < numAccesses; a++) {
|
||
int target = numFields / 2 + (a % (numFields / 2));
|
||
// Binary search — O(log N)
|
||
int lo = 0, hi = keys.size();
|
||
while (lo < hi) {
|
||
int mid = (lo + hi) >>> 1;
|
||
ops++;
|
||
if (keys.get(mid) < target) lo = mid + 1;
|
||
else hi = mid;
|
||
}
|
||
}
|
||
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(" %-52s 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 peewee-0001: Peewee ORM CWE-407 ===");
|
||
System.out.println();
|
||
|
||
final int FIELDS = 500, ACCESSES = 1000;
|
||
|
||
long s0 = sortedFieldListSlow(FIELDS, ACCESSES), f0 = sortedFieldListFast(FIELDS, ACCESSES);
|
||
bench("peewee-0001 _SortedFieldList.index() list vs bisect",
|
||
() -> sortedFieldListSlow(FIELDS, ACCESSES), () -> sortedFieldListFast(FIELDS, ACCESSES), s0, f0);
|
||
|
||
System.out.println();
|
||
int pass = 0;
|
||
assert s0 > f0 * 5 : "peewee-0001 expected >5x"; pass++;
|
||
|
||
System.out.printf("%d/1 PASS — peewee-0001: CWE-407 in Peewee _SortedFieldList%n", pass);
|
||
System.out.printf("Hotpath: field metadata access during query compilation on models with many fields%n");
|
||
}
|
||
}
|