russell@unturf.com
db29a08762
B&W print-friendly diagrams + tinkerpop-0001 + wave-3 proof sections. Squash of 94 local commits onto remote master.
400 lines
17 KiB
Java
400 lines
17 KiB
Java
package unit;
|
||
|
||
import java.util.ArrayList;
|
||
import java.util.HashSet;
|
||
import java.util.LinkedHashSet;
|
||
|
||
/**
|
||
* CFEngineRlistTest
|
||
*
|
||
* Models three CWE-407 defects in libpromises/evalfunction.c:
|
||
*
|
||
* CFE-001 (MEDIUM) — FnCallGetIndicesClassic / getindices():
|
||
* RlistAppendScalarIdemp(&keys, ...) calls RlistKeyIn(keys, ...) —
|
||
* O(K) linked-list walk per insertion. O(K²) total over K indices.
|
||
* Fix: collect indices into a StringSet (O(1) insert), convert once.
|
||
*
|
||
* CFE-002 (HIGH) — FnCallSetop / unique():
|
||
* In unique_mode, set_b is always empty. RlistAppendScalarIdemp
|
||
* falls back to walking the growing returnlist on every element —
|
||
* O(N) per element, O(N²) total for N input values.
|
||
* Fix: maintain a separate StringSet of seen values. O(N) total.
|
||
*
|
||
* CFE-003 (MEDIUM) — FnCallMapData / maparray() nested-container branch:
|
||
* Outer while over JSON object, inner while over sub-container, then
|
||
* RlistAppendScalarIdemp(&returnlist, ...) — O(R) scan of growing
|
||
* returnlist per sub-element. O(N²) total for N sub-elements.
|
||
* Fix: StringSet for dedup tracking, RlistAppendScalar for appends.
|
||
*
|
||
* Rlist is modelled as ArrayList<String>.
|
||
* StringSet is modelled as HashSet<String>.
|
||
* Operation counts are instrumented explicitly — not wall-clock timing.
|
||
*/
|
||
public class CFEngineRlistTest {
|
||
|
||
// -----------------------------------------------------------------------
|
||
// CFE-001 models
|
||
// -----------------------------------------------------------------------
|
||
|
||
/**
|
||
* Defective: RlistAppendScalarIdemp — walks the list to check membership
|
||
* before each append. Returns total comparison count.
|
||
*/
|
||
static long cfe001Defective(String[] indices) {
|
||
ArrayList<String> keys = new ArrayList<>();
|
||
long comparisons = 0;
|
||
for (String idx : indices) {
|
||
boolean found = false;
|
||
// RlistKeyIn: O(K) linear scan of existing keys
|
||
for (String existing : keys) {
|
||
comparisons++;
|
||
if (existing.equals(idx)) {
|
||
found = true;
|
||
break;
|
||
}
|
||
}
|
||
if (!found) {
|
||
keys.add(idx);
|
||
}
|
||
}
|
||
return comparisons;
|
||
}
|
||
|
||
/**
|
||
* Fixed: StringSet for dedup, convert to list once at end.
|
||
* Returns total hash-lookup count (one per insertion attempt).
|
||
*/
|
||
static long cfe001Fixed(String[] indices) {
|
||
HashSet<String> keysSet = new HashSet<>();
|
||
long lookups = 0;
|
||
for (String idx : indices) {
|
||
lookups++; // one O(1) contains() per element
|
||
keysSet.add(idx); // silently ignores duplicates
|
||
}
|
||
// Convert to list — O(K) one-time cost, not charged here
|
||
ArrayList<String> keys = new ArrayList<>(keysSet);
|
||
return lookups;
|
||
}
|
||
|
||
// -----------------------------------------------------------------------
|
||
// CFE-002 models
|
||
// -----------------------------------------------------------------------
|
||
|
||
/**
|
||
* Defective: unique() with empty set_b — dedup falls on returnlist.
|
||
* Models the unique_mode path where set_b is always empty.
|
||
*/
|
||
static long cfe002Defective(String[] values) {
|
||
ArrayList<String> returnlist = new ArrayList<>();
|
||
long comparisons = 0;
|
||
for (String value : values) {
|
||
// set_b empty → RlistAppendScalarIdemp walks returnlist
|
||
boolean found = false;
|
||
for (String existing : returnlist) {
|
||
comparisons++;
|
||
if (existing.equals(value)) {
|
||
found = true;
|
||
break;
|
||
}
|
||
}
|
||
if (!found) {
|
||
returnlist.add(value);
|
||
}
|
||
}
|
||
return comparisons;
|
||
}
|
||
|
||
/**
|
||
* Fixed: separate StringSet tracks seen values; returnlist gets plain
|
||
* appends with no membership scan.
|
||
*/
|
||
static long cfe002Fixed(String[] values) {
|
||
HashSet<String> seen = new HashSet<>();
|
||
ArrayList<String> returnlist = new ArrayList<>();
|
||
long lookups = 0;
|
||
for (String value : values) {
|
||
lookups++; // one O(1) contains() per element
|
||
if (!seen.contains(value)) {
|
||
seen.add(value);
|
||
returnlist.add(value); // plain append — no scan
|
||
}
|
||
}
|
||
return lookups;
|
||
}
|
||
|
||
// -----------------------------------------------------------------------
|
||
// CFE-003 models
|
||
// -----------------------------------------------------------------------
|
||
|
||
/**
|
||
* Defective: nested-container iteration with RlistAppendScalarIdemp.
|
||
* outerCount outer keys, each with innerCount sub-elements.
|
||
*/
|
||
static long cfe003Defective(int outerCount, int innerCount) {
|
||
ArrayList<String> returnlist = new ArrayList<>();
|
||
long comparisons = 0;
|
||
for (int i = 0; i < outerCount; i++) {
|
||
for (int j = 0; j < innerCount; j++) {
|
||
// expanded string: same value across outer keys → many dupes
|
||
String expanded = "value_" + j;
|
||
// RlistAppendScalarIdemp: O(R) scan of returnlist
|
||
boolean found = false;
|
||
for (String existing : returnlist) {
|
||
comparisons++;
|
||
if (existing.equals(expanded)) {
|
||
found = true;
|
||
break;
|
||
}
|
||
}
|
||
if (!found) {
|
||
returnlist.add(expanded);
|
||
}
|
||
}
|
||
}
|
||
return comparisons;
|
||
}
|
||
|
||
/**
|
||
* Fixed: StringSet tracks seen; plain appends to returnlist.
|
||
*/
|
||
static long cfe003Fixed(int outerCount, int innerCount) {
|
||
HashSet<String> seen = new HashSet<>();
|
||
ArrayList<String> returnlist = new ArrayList<>();
|
||
long lookups = 0;
|
||
for (int i = 0; i < outerCount; i++) {
|
||
for (int j = 0; j < innerCount; j++) {
|
||
String expanded = "value_" + j;
|
||
lookups++; // O(1) contains()
|
||
if (!seen.contains(expanded)) {
|
||
seen.add(expanded);
|
||
returnlist.add(expanded);
|
||
}
|
||
}
|
||
}
|
||
return lookups;
|
||
}
|
||
|
||
// -----------------------------------------------------------------------
|
||
// Helpers
|
||
// -----------------------------------------------------------------------
|
||
|
||
/** Build K indices where the first K/2 are unique, rest are duplicates. */
|
||
static String[] makeIndices(int k) {
|
||
int distinct = Math.max(1, k / 2);
|
||
String[] out = new String[k];
|
||
for (int i = 0; i < k; i++) {
|
||
out[i] = "idx_" + (i % distinct);
|
||
}
|
||
return out;
|
||
}
|
||
|
||
// -----------------------------------------------------------------------
|
||
// Test 1 — CFE-001: getindices() dedup cost at K=60
|
||
// Defect does O(K²) comparisons; fix does O(K) lookups.
|
||
// -----------------------------------------------------------------------
|
||
|
||
static void test1_cfe001_getindices() {
|
||
int k = 60;
|
||
String[] indices = makeIndices(k);
|
||
|
||
long defectOps = cfe001Defective(indices);
|
||
long fixedOps = cfe001Fixed(indices);
|
||
|
||
System.out.printf("test1 CFE-001: k=%d defect_comparisons=%d fixed_lookups=%d%n",
|
||
k, defectOps, fixedOps);
|
||
|
||
assert defectOps > fixedOps
|
||
: "defect must do more work than fix at k=" + k;
|
||
// With k/2 distinct values, defect compares at minimum triangular(k/2)
|
||
long expectedMinDefect = (long)(k / 2) * (k / 2 - 1) / 2;
|
||
assert defectOps >= expectedMinDefect
|
||
: "defect comparisons=" + defectOps + " expected >= " + expectedMinDefect;
|
||
}
|
||
|
||
// -----------------------------------------------------------------------
|
||
// Test 2 — CFE-002: unique() dedup cost at N=80 all-distinct input
|
||
// Defect: O(N²); fix: O(N). All-distinct maximises list scan length.
|
||
// -----------------------------------------------------------------------
|
||
|
||
static void test2_cfe002_unique() {
|
||
int n = 80;
|
||
// All distinct → worst case: every element is a cache miss on returnlist
|
||
String[] values = new String[n];
|
||
for (int i = 0; i < n; i++) values[i] = "val_" + i;
|
||
|
||
long defectOps = cfe002Defective(values);
|
||
long fixedOps = cfe002Fixed(values);
|
||
|
||
// Defect: input 0 → list empty (0 comparisons); input i → list.size()=i scans
|
||
// Total: 0 + 1 + 2 + ... + (n-1) = n*(n-1)/2
|
||
long expectedDefect = (long) n * (n - 1) / 2;
|
||
double ratio = (double) defectOps / Math.max(1, fixedOps);
|
||
|
||
System.out.printf("test2 CFE-002: n=%d distinct defect=%d (expect=%d) fixed=%d ratio=%.1fx%n",
|
||
n, defectOps, expectedDefect, fixedOps, ratio);
|
||
|
||
assert defectOps == expectedDefect
|
||
: "defect comparisons=" + defectOps + " expected=" + expectedDefect;
|
||
assert ratio > 20.0
|
||
: "expected ratio > 20x for all-distinct unique(), got " + ratio;
|
||
}
|
||
|
||
// -----------------------------------------------------------------------
|
||
// Test 3 — CFE-003: maparray() nested-container cost
|
||
// 10 outer keys × 20 sub-elements, all sub-elements produce same
|
||
// values across outer iterations → heavy dedup pressure on returnlist.
|
||
// -----------------------------------------------------------------------
|
||
|
||
static void test3_cfe003_maparray() {
|
||
int outer = 10;
|
||
int inner = 20;
|
||
|
||
long defectOps = cfe003Defective(outer, inner);
|
||
long fixedOps = cfe003Fixed(outer, inner);
|
||
|
||
double ratio = (double) defectOps / Math.max(1, fixedOps);
|
||
|
||
System.out.printf("test3 CFE-003: outer=%d inner=%d defect=%d fixed=%d ratio=%.1fx%n",
|
||
outer, inner, defectOps, fixedOps, ratio);
|
||
|
||
assert defectOps > fixedOps
|
||
: "defect must do more work than fix";
|
||
// After the first outer iteration, all inner values are known.
|
||
// From iteration 2 onward every inner lookup hits immediately at pos 0..inner-1.
|
||
// Defect comparisons are > inner * outer (always at least 1 per dup hit).
|
||
assert defectOps > inner
|
||
: "defect should do more comparisons than a single pass";
|
||
assert ratio > 2.0
|
||
: "expected ratio > 2x, got " + ratio;
|
||
}
|
||
|
||
// -----------------------------------------------------------------------
|
||
// Test 4 — Scaling: doubling N roughly quadruples defect ops (O(N²))
|
||
// but only doubles fix ops (O(N)). Covers all three defects.
|
||
// -----------------------------------------------------------------------
|
||
|
||
static void test4_quadraticScaling() {
|
||
int n1 = 50;
|
||
int n2 = 100; // 2x
|
||
|
||
// CFE-001 scaling (all-distinct indices → worst case)
|
||
String[] idx1 = new String[n1]; for (int i=0;i<n1;i++) idx1[i]="i"+i;
|
||
String[] idx2 = new String[n2]; for (int i=0;i<n2;i++) idx2[i]="i"+i;
|
||
double d1_growth = (double) cfe001Defective(idx2) / Math.max(1, cfe001Defective(idx1));
|
||
double f1_growth = (double) cfe001Fixed(idx2) / Math.max(1, cfe001Fixed(idx1));
|
||
|
||
// CFE-002 scaling (all-distinct values)
|
||
String[] val1 = new String[n1]; for (int i=0;i<n1;i++) val1[i]="v"+i;
|
||
String[] val2 = new String[n2]; for (int i=0;i<n2;i++) val2[i]="v"+i;
|
||
double d2_growth = (double) cfe002Defective(val2) / Math.max(1, cfe002Defective(val1));
|
||
double f2_growth = (double) cfe002Fixed(val2) / Math.max(1, cfe002Fixed(val1));
|
||
|
||
// CFE-003 scaling (outer fixed=5, double inner from n1/5 to n2/5)
|
||
int outer = 5;
|
||
double d3_growth = (double) cfe003Defective(outer, n2/outer) / Math.max(1, cfe003Defective(outer, n1/outer));
|
||
double f3_growth = (double) cfe003Fixed(outer, n2/outer) / Math.max(1, cfe003Fixed(outer, n1/outer));
|
||
|
||
System.out.printf("test4 scaling (2x N): CFE-001 defect=%.2fx fix=%.2fx " +
|
||
"CFE-002 defect=%.2fx fix=%.2fx CFE-003 defect=%.2fx fix=%.2fx%n",
|
||
d1_growth, f1_growth, d2_growth, f2_growth, d3_growth, f3_growth);
|
||
|
||
// Defect must grow super-linearly (> 2x when N doubles → quadratic)
|
||
assert d1_growth > 2.0 : "CFE-001 defect growth should be super-linear, got " + d1_growth;
|
||
assert d2_growth > 2.0 : "CFE-002 defect growth should be super-linear, got " + d2_growth;
|
||
assert d3_growth > 1.5 : "CFE-003 defect growth should be super-linear, got " + d3_growth;
|
||
|
||
// Fix must grow at most linearly (≤ 2.5x for 2x N, allowing hash overhead)
|
||
assert f1_growth <= 2.5 : "CFE-001 fix growth should be at most linear, got " + f1_growth;
|
||
assert f2_growth <= 2.5 : "CFE-002 fix growth should be at most linear, got " + f2_growth;
|
||
assert f3_growth <= 2.5 : "CFE-003 fix growth should be at most linear, got " + f3_growth;
|
||
|
||
// Defect must grow faster than fix for each
|
||
assert d1_growth > f1_growth : "CFE-001 defect growth should exceed fix growth";
|
||
assert d2_growth > f2_growth : "CFE-002 defect growth should exceed fix growth";
|
||
assert d3_growth > f3_growth : "CFE-003 defect growth should exceed fix growth";
|
||
}
|
||
|
||
// -----------------------------------------------------------------------
|
||
// Test 5 — Correctness: defect and fix produce identical output sets
|
||
// for all three defects.
|
||
// -----------------------------------------------------------------------
|
||
|
||
static void test5_correctness() {
|
||
// CFE-001 correctness
|
||
String[] indices = makeIndices(40);
|
||
HashSet<String> defectKeys = new HashSet<>();
|
||
{
|
||
ArrayList<String> keys = new ArrayList<>();
|
||
for (String idx : indices) {
|
||
if (!keys.contains(idx)) keys.add(idx);
|
||
}
|
||
defectKeys.addAll(keys);
|
||
}
|
||
HashSet<String> fixedKeys = new HashSet<>();
|
||
{
|
||
// Fixed just uses a HashSet directly
|
||
fixedKeys.addAll(java.util.Arrays.asList(indices));
|
||
}
|
||
assert defectKeys.equals(fixedKeys)
|
||
: "CFE-001: defect and fix must produce same key set";
|
||
|
||
// CFE-002 correctness
|
||
String[] values = makeIndices(40);
|
||
ArrayList<String> defectUniq = new ArrayList<>();
|
||
for (String v : values) {
|
||
if (!defectUniq.contains(v)) defectUniq.add(v);
|
||
}
|
||
HashSet<String> fixedUniq = new LinkedHashSet<>(java.util.Arrays.asList(values))
|
||
.stream().collect(java.util.stream.Collectors.toCollection(HashSet::new));
|
||
assert new HashSet<>(defectUniq).equals(fixedUniq)
|
||
: "CFE-002: defect and fix must produce same unique set";
|
||
|
||
// CFE-003 correctness: same distinct expanded strings regardless of strategy
|
||
int outer = 4, inner = 8;
|
||
ArrayList<String> defectResult = new ArrayList<>();
|
||
ArrayList<String> fixedResult = new ArrayList<>();
|
||
HashSet<String> seenFixed = new HashSet<>();
|
||
for (int i = 0; i < outer; i++) {
|
||
for (int j = 0; j < inner; j++) {
|
||
String exp = "value_" + j;
|
||
if (!defectResult.contains(exp)) defectResult.add(exp);
|
||
if (!seenFixed.contains(exp)) { seenFixed.add(exp); fixedResult.add(exp); }
|
||
}
|
||
}
|
||
assert new HashSet<>(defectResult).equals(new HashSet<>(fixedResult))
|
||
: "CFE-003: defect and fix must produce same result set";
|
||
assert defectResult.equals(fixedResult)
|
||
: "CFE-003: insertion order must also match (both first-seen)";
|
||
|
||
System.out.printf("test5 correctness: CFE-001 keys=%d CFE-002 uniq=%d CFE-003 result=%d%n",
|
||
defectKeys.size(), defectUniq.size(), defectResult.size());
|
||
}
|
||
|
||
// -----------------------------------------------------------------------
|
||
// Main
|
||
// -----------------------------------------------------------------------
|
||
|
||
public static void main(String[] args) {
|
||
System.out.println("=== CFEngineRlistTest ===");
|
||
System.out.println("Modelling CWE-407: CFE-001 getindices / CFE-002 unique / CFE-003 maparray");
|
||
System.out.println();
|
||
|
||
test1_cfe001_getindices();
|
||
System.out.println(" PASS test1_cfe001_getindices");
|
||
|
||
test2_cfe002_unique();
|
||
System.out.println(" PASS test2_cfe002_unique");
|
||
|
||
test3_cfe003_maparray();
|
||
System.out.println(" PASS test3_cfe003_maparray");
|
||
|
||
test4_quadraticScaling();
|
||
System.out.println(" PASS test4_quadraticScaling");
|
||
|
||
test5_correctness();
|
||
System.out.println(" PASS test5_correctness");
|
||
|
||
System.out.println();
|
||
System.out.println("All 5 tests PASSED.");
|
||
}
|
||
}
|