java-topology/defects/curl/unit/CurlHeadersAndHstsAlgorithmTest.java

package unit;

import java.util.*;

/**
 * Models two curl CWE-407 defects:
 *
 * curl-0002: Curl_checkheaders O(K×H) per request — K=20 slist scans per HTTP request.
 * curl-0003: Curl_hsts O(N²) file load + O(N) per-request HSTS upgrade check.
 *
 * SLOW: linear slist/llist scan per call.
 * FAST: HashMap lookup O(1) per call.
 *
 * CWE-407: lib/transfer.c:85, lib/hsts.c:225,389
 */
public class CurlHeadersAndHstsAlgorithmTest {

    // =========================================================================
    // curl-0002: Curl_checkheaders
    // =========================================================================

    static class SlowCheckHeaders {
        long cmpOps = 0;

        String checkheaders(List<String> headers, String name) {
            for (String h : headers) {
                cmpOps++;
                if (h.toLowerCase().startsWith(name.toLowerCase() + ":"))
                    return h;
            }
            return null;
        }

        long simulateRequest(List<String> headers, List<String> lookups) {
            cmpOps = 0;
            for (String lookup : lookups) checkheaders(headers, lookup);
            return cmpOps;
        }
    }

    static class FastCheckHeaders {
        long cmpOps = 0;
        final Map<String, String> headerMap;

        FastCheckHeaders(List<String> headers) {
            headerMap = new HashMap<>();
            for (String h : headers) {
                cmpOps++;
                int colon = h.indexOf(':');
                if (colon > 0) headerMap.put(h.substring(0, colon).toLowerCase(), h);
            }
        }

        String checkheaders(String name) {
            cmpOps++;
            return headerMap.get(name.toLowerCase());
        }

        long simulateRequest(List<String> lookups) {
            long before = cmpOps;
            cmpOps = 0;
            for (String lookup : lookups) checkheaders(lookup);
            return cmpOps;
        }
    }

    // =========================================================================
    // curl-0003: Curl_hsts
    // =========================================================================

    static class SlowHsts {
        long cmpOps = 0;
        final List<String> entries = new ArrayList<>();

        String lookup(String host) {
            for (String e : entries) {
                cmpOps++;
                if (e.equalsIgnoreCase(host)) return e;
            }
            return null;
        }

        void add(String host) {
            if (lookup(host) == null) entries.add(host);
        }

        long loadFile(List<String> hosts) {
            cmpOps = 0;
            entries.clear();
            for (String h : hosts) add(h);
            return cmpOps;
        }
    }

    static class FastHsts {
        long cmpOps = 0;
        final Map<String, String> map = new HashMap<>();

        String lookup(String host) {
            cmpOps++;
            return map.get(host.toLowerCase());
        }

        void add(String host) {
            cmpOps++;
            map.putIfAbsent(host.toLowerCase(), host);
        }

        long loadFile(List<String> hosts) {
            cmpOps = 0;
            map.clear();
            for (String h : hosts) add(h);
            return cmpOps;
        }
    }

    // =========================================================================
    // Test harness
    // =========================================================================

    static List<String> makeHeaders(int n) {
        List<String> h = new ArrayList<>();
        for (int i = 0; i < n; i++) h.add("X-Custom-" + i + ": value" + i);
        return h;
    }

    // K=20 standard header lookups per HTTP request (from http.c)
    static final List<String> HTTP_LOOKUPS = List.of(
        "Host", "Content-Type", "Content-Length", "Transfer-Encoding",
        "Connection", "Accept", "Authorization", "Cookie",
        "User-Agent", "Accept-Encoding", "Cache-Control", "Pragma",
        "If-Modified-Since", "If-None-Match", "Range", "Expect",
        "Upgrade", "Origin", "Referer", "X-Requested-With"
    );

    static List<String> makeHosts(int n) {
        List<String> h = new ArrayList<>();
        for (int i = 0; i < n; i++) h.add("host" + i + ".example.com");
        return h;
    }

    public static void main(String[] args) {
        int passed = 0, total = 0;

        System.out.println("=== curl-0002: Curl_checkheaders O(K×H) ===");
        int[] hSizes = {50, 100, 200, 500};
        for (int h : hSizes) {
            List<String> headers = makeHeaders(h);
            SlowCheckHeaders slow = new SlowCheckHeaders();
            FastCheckHeaders fast = new FastCheckHeaders(headers);
            long s = slow.simulateRequest(headers, HTTP_LOOKUPS);
            long f = fast.simulateRequest(HTTP_LOOKUPS);
            double ratio = (double) s / Math.max(f, 1);
            total++;
            boolean ok = s > f && ratio >= 5.0;
            System.out.printf("H=%3d K=%2d  slow=%7d fast=%3d ratio=%6.1fx  %s%n",
                h, HTTP_LOOKUPS.size(), s, f, ratio, ok ? "PASS" : "FAIL");
            if (ok) passed++;
        }

        System.out.println("=== curl-0003: Curl_hsts hsts_load O(N²) ===");
        int[] nSizes = {100, 200, 500, 1000};
        for (int n : nSizes) {
            List<String> hosts = makeHosts(n);
            SlowHsts slow = new SlowHsts();
            FastHsts fast = new FastHsts();
            long s = slow.loadFile(hosts);
            long f = fast.loadFile(hosts);
            double ratio = (double) s / Math.max(f, 1);
            total++;
            boolean ok = s > f && ratio >= 5.0;
            System.out.printf("N=%4d  slow=%9d fast=%5d ratio=%6.1fx  %s%n",
                n, s, f, ratio, ok ? "PASS" : "FAIL");
            if (ok) passed++;
        }

        // Correctness checks
        List<String> hosts50 = makeHosts(50);
        // Add one dup
        hosts50.add("host0.example.com");
        SlowHsts sh = new SlowHsts(); FastHsts fh = new FastHsts();
        sh.loadFile(hosts50); fh.loadFile(hosts50);
        total++;
        boolean c1 = sh.entries.size() == fh.map.size();
        System.out.printf("hsts dedup correct (size=%d): %s%n", sh.entries.size(), c1 ? "PASS" : "FAIL");
        if (c1) passed++;

        System.out.printf("%n%d/%d PASS%n", passed, total);
        if (passed < total) System.exit(1);
    }
}