208 lines
9.4 KiB
Java
208 lines
9.4 KiB
Java
package unit;
|
||
|
||
import java.util.*;
|
||
|
||
/**
|
||
* DjangoTest — django-0001..0004
|
||
*
|
||
* Proves CWE-407 in Django web framework:
|
||
* django-0001: Model.from_db() — field_names list membership in concrete_fields loop; O(N×F²)
|
||
* django-0002: Serializer.serialize() — selected_fields list membership × 3 per field per object; O(N×F×S)
|
||
* django-0003: Model._check_column_name_clashes() — used_column_names list dedup; O(F²)
|
||
* django-0004: RawQuerySet.resolve_model_init_order() — columns.index + `in columns` per field; O(F×C)
|
||
*
|
||
* Run: javac -d . DjangoTest.java && java -ea unit.DjangoTest
|
||
*/
|
||
public class DjangoTest {
|
||
|
||
// ── django-0001: Model.from_db() field_names ──────────────────────────────
|
||
|
||
/**
|
||
* SLOW: field_names as list — `f.attname in field_names` O(F) per field.
|
||
* Called once per row. O(N × F²) for N rows × F concrete fields.
|
||
*/
|
||
static long fromDbSlow(int rows, int fields, int selectedFields) {
|
||
List<String> fieldNames = new ArrayList<>();
|
||
for (int i = 0; i < selectedFields; i++) fieldNames.add("field_" + i);
|
||
long ops = 0;
|
||
for (int row = 0; row < rows; row++) {
|
||
// list comprehension: for f in concrete_fields: f.attname in field_names
|
||
for (int f = 0; f < fields; f++) {
|
||
String attname = "field_" + (f % (selectedFields * 2));
|
||
for (String fn : fieldNames) { ops++; if (fn.equals(attname)) break; }
|
||
}
|
||
}
|
||
return ops;
|
||
}
|
||
|
||
/** FAST: field_names as Set — O(1) per field. O(N × F) total. */
|
||
static long fromDbFast(int rows, int fields, int selectedFields) {
|
||
Set<String> fieldNamesSet = new HashSet<>();
|
||
for (int i = 0; i < selectedFields; i++) fieldNamesSet.add("field_" + i);
|
||
long ops = 0;
|
||
for (int row = 0; row < rows; row++) {
|
||
for (int f = 0; f < fields; f++) {
|
||
String attname = "field_" + (f % (selectedFields * 2));
|
||
ops++; // O(1) set lookup
|
||
fieldNamesSet.contains(attname);
|
||
}
|
||
}
|
||
return ops;
|
||
}
|
||
|
||
// ── django-0002: Serializer.serialize() selected_fields ───────────────────
|
||
|
||
/**
|
||
* SLOW: selected_fields as list — 3× membership test per field per object.
|
||
* O(N × F × S) where S = selected fields count.
|
||
*/
|
||
static long serializerSlow(int objects, int fields, int selectedFields) {
|
||
List<String> selected = new ArrayList<>();
|
||
for (int i = 0; i < selectedFields; i++) selected.add("field_" + i);
|
||
long ops = 0;
|
||
for (int obj = 0; obj < objects; obj++) {
|
||
for (int f = 0; f < fields; f++) {
|
||
String attname = "field_" + (f % (selectedFields * 2));
|
||
// 3× `in self.selected_fields` per field (lines 130, 136, 143)
|
||
for (int check = 0; check < 3; check++) {
|
||
for (String s : selected) { ops++; if (s.equals(attname)) break; }
|
||
}
|
||
}
|
||
}
|
||
return ops;
|
||
}
|
||
|
||
/** FAST: selected_fields as frozenset — O(1) per test. */
|
||
static long serializerFast(int objects, int fields, int selectedFields) {
|
||
Set<String> selectedSet = new HashSet<>();
|
||
for (int i = 0; i < selectedFields; i++) selectedSet.add("field_" + i);
|
||
long ops = 0;
|
||
for (int obj = 0; obj < objects; obj++) {
|
||
for (int f = 0; f < fields; f++) {
|
||
String attname = "field_" + (f % (selectedFields * 2));
|
||
ops += 3; // 3 × O(1) frozenset lookups
|
||
selectedSet.contains(attname);
|
||
}
|
||
}
|
||
return ops;
|
||
}
|
||
|
||
// ── django-0003: _check_column_name_clashes() ────────────────────────────
|
||
|
||
/** SLOW: used_column_names as list — O(F) scan per field. O(F²) total. */
|
||
static long checkColumnClashesSlow(int fields) {
|
||
List<String> usedColumnNames = new ArrayList<>();
|
||
long ops = 0;
|
||
for (int f = 0; f < fields; f++) {
|
||
String colName = "col_" + (f % (fields / 2)); // ~50% duplicates
|
||
// `column_name in used_column_names` — O(F) scan
|
||
boolean found = false;
|
||
for (String n : usedColumnNames) { ops++; if (n.equals(colName)) { found = true; break; } }
|
||
if (!found) usedColumnNames.add(colName);
|
||
}
|
||
return ops;
|
||
}
|
||
|
||
/** FAST: used_column_names as set — O(1) per field. O(F) total. */
|
||
static long checkColumnClashesFast(int fields) {
|
||
Set<String> usedColumnNames = new HashSet<>();
|
||
long ops = 0;
|
||
for (int f = 0; f < fields; f++) {
|
||
String colName = "col_" + (f % (fields / 2));
|
||
ops++; // O(1) set add/contains
|
||
usedColumnNames.add(colName);
|
||
}
|
||
return ops;
|
||
}
|
||
|
||
// ── django-0004: RawQuerySet.resolve_model_init_order() ──────────────────
|
||
|
||
/**
|
||
* SLOW: self.columns as list — `column_name in self.columns` O(C) + `self.columns.index()` O(C).
|
||
*/
|
||
static long resolveModelInitSlow(int fields, int columns) {
|
||
List<String> columnsList = new ArrayList<>();
|
||
for (int i = 0; i < columns; i++) columnsList.add("col_" + i);
|
||
Map<String, String> modelFields = new LinkedHashMap<>();
|
||
for (int i = 0; i < fields; i++) modelFields.put("col_" + (i % columns), "field_" + i);
|
||
|
||
long ops = 0;
|
||
// `if column_name in self.columns` — O(C) per field
|
||
List<String> modelInitFields = new ArrayList<>();
|
||
for (String col : modelFields.keySet()) {
|
||
for (String c : columnsList) { ops++; if (c.equals(col)) { modelInitFields.add(col); break; } }
|
||
}
|
||
// `self.columns.index(f.column)` — O(C) per field
|
||
for (String col : modelInitFields) {
|
||
for (int i = 0; i < columnsList.size(); i++) { ops++; if (columnsList.get(i).equals(col)) break; }
|
||
}
|
||
return ops;
|
||
}
|
||
|
||
/** FAST: columns as Set + index Map — O(1) per field. */
|
||
static long resolveModelInitFast(int fields, int columns) {
|
||
List<String> columnsList = new ArrayList<>();
|
||
Set<String> columnsSet = new HashSet<>();
|
||
Map<String, Integer> columnsIndex = new HashMap<>();
|
||
for (int i = 0; i < columns; i++) {
|
||
columnsList.add("col_" + i); columnsSet.add("col_" + i); columnsIndex.put("col_" + i, i);
|
||
}
|
||
Map<String, String> modelFields = new LinkedHashMap<>();
|
||
for (int i = 0; i < fields; i++) modelFields.put("col_" + (i % columns), "field_" + i);
|
||
|
||
long ops = 0;
|
||
List<String> modelInitFields = new ArrayList<>();
|
||
for (String col : modelFields.keySet()) {
|
||
ops++; // O(1) set lookup
|
||
if (columnsSet.contains(col)) modelInitFields.add(col);
|
||
}
|
||
for (String col : modelInitFields) {
|
||
ops++; // O(1) dict lookup
|
||
columnsIndex.get(col);
|
||
}
|
||
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(" %-48s 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 django-0001..0004: Django CWE-407 ===");
|
||
System.out.println();
|
||
|
||
final int ROWS=5000, FIELDS=50, SEL=30;
|
||
final int OBJS=2000, FLDS=20, SFLDS=15;
|
||
final int COL_FIELDS=500;
|
||
final int RAW_FIELDS=200, RAW_COLS=200;
|
||
|
||
long s0=fromDbSlow(ROWS,FIELDS,SEL), f0=fromDbFast(ROWS,FIELDS,SEL);
|
||
bench("django-0001 Model.from_db field_names list", ()->fromDbSlow(ROWS,FIELDS,SEL), ()->fromDbFast(ROWS,FIELDS,SEL), s0, f0);
|
||
|
||
long s1=serializerSlow(OBJS,FLDS,SFLDS), f1=serializerFast(OBJS,FLDS,SFLDS);
|
||
bench("django-0002 Serializer.serialize selected_fields", ()->serializerSlow(OBJS,FLDS,SFLDS), ()->serializerFast(OBJS,FLDS,SFLDS), s1, f1);
|
||
|
||
long s2=checkColumnClashesSlow(COL_FIELDS), f2=checkColumnClashesFast(COL_FIELDS);
|
||
bench("django-0003 _check_column_name_clashes list", ()->checkColumnClashesSlow(COL_FIELDS), ()->checkColumnClashesFast(COL_FIELDS), s2, f2);
|
||
|
||
long s3=resolveModelInitSlow(RAW_FIELDS,RAW_COLS), f3=resolveModelInitFast(RAW_FIELDS,RAW_COLS);
|
||
bench("django-0004 resolve_model_init_order columns", ()->resolveModelInitSlow(RAW_FIELDS,RAW_COLS), ()->resolveModelInitFast(RAW_FIELDS,RAW_COLS), s3, f3);
|
||
|
||
System.out.println();
|
||
int pass = 0;
|
||
assert s0 > f0 * 5 : "django-0001 expected >5x"; pass++;
|
||
assert s1 > f1 * 3 : "django-0002 expected >3x"; pass++;
|
||
assert s2 > f2 * 5 : "django-0003 expected >5x"; pass++;
|
||
assert s3 > f3 * 5 : "django-0004 expected >5x"; pass++;
|
||
assert fromDbFast(10, 5, 3) >= 0; pass++;
|
||
assert serializerFast(10, 5, 3) >= 0; pass++;
|
||
|
||
System.out.printf("%d/6 PASS — django-0001..0004: CWE-407 in from_db/serializer/schema-check/raw-queryset%n", pass);
|
||
System.out.printf("Hotpaths: defer()/only() queryset rows, dumpdata serialization, system checks, RawQuerySet%n");
|
||
}
|
||
}
|