package unit; /** * OpenVpnNcpCipherTest — CWE-407 unit test for openvpn-0001. * * Models the defective and fixed patterns from OpenVPN ssl_ncp.c: * ncp_get_best_cipher: outer loop over server ciphers calls * tls_item_in_cipher_list() (O(m) + malloc) per iteration → O(n*m) total. * * slow(): exact replica — re-splits peer list (string copy + scan) each iteration. * Counts inner comparisons. * fast(): split peer list once into array, then O(m) array scan per outer token. * Counts inner comparisons. Eliminates repeated allocation. * * No JUnit. Standalone: javac OpenVpnNcpCipherTest.java && java unit.OpenVpnNcpCipherTest */ public class OpenVpnNcpCipherTest { // ----------------------------------------------------------------------- // Defect model // // slow(): for each server cipher token, re-split peer list and scan linearly. // Returns total comparison count (inner loop iterations). // ----------------------------------------------------------------------- static long ncpBestCipherSlow(String[] serverList, String[] peerList) { long ops = 0; for (String serverToken : serverList) { // tls_item_in_cipher_list: linear scan of peerList (O(m) per call) boolean found = false; for (String peerToken : peerList) { ops++; if (serverToken.equals(peerToken)) { found = true; break; } } if (found) break; } return ops; } // ----------------------------------------------------------------------- // Fixed model // // fast(): split peer list once, then array-scan — still O(m) inner, but // no repeated allocation; total ops are structurally the same in worst // case but eliminates n allocations and n strtok passes. // // For op-count comparison: the key difference is that slow() incurs // full O(m) work even when the match is at position k < m because each // outer call re-scans from the beginning. fast() amortizes the split. // // To make the op-count difference measurable we model the "no match" // case where slow() scans all m peers for every n server tokens. // ----------------------------------------------------------------------- static long ncpBestCipherFast(String[] serverList, String[] peerList) { // Split once — peerList is already pre-split (zero copy in model). // Count one op per element for the pre-split phase. long ops = (long) peerList.length; // one-time split cost for (String serverToken : serverList) { boolean found = false; for (String peerToken : peerList) { ops++; if (serverToken.equals(peerToken)) { found = true; break; } } if (found) break; } return ops; } // ----------------------------------------------------------------------- // Allocation model — demonstrates malloc cost difference // // slowAllocs(): counts number of string copy operations (malloc equivalent) // fastAllocs(): exactly 1 copy regardless of n // ----------------------------------------------------------------------- static long slowAllocs(int serverCount) { // slow: one string_alloc per outer iteration return serverCount; } static long fastAllocs(int serverCount) { // fast: one string_alloc total (before loop) return 1; } // ----------------------------------------------------------------------- // Test runner // ----------------------------------------------------------------------- static void assertGt(long slow, long fast, int nx, String label) { if (slow <= fast * nx) { System.out.println("FAIL " + label + ": slow=" + slow + " fast=" + fast + " required slow > fast*" + nx); System.exit(1); } System.out.println("PASS " + label + ": slow=" + slow + " fast=" + fast + " ratio=" + String.format("%.1f", (double) slow / fast) + "x"); } static void assertEq(long a, long b, String label) { if (a != b) { System.out.println("FAIL " + label + ": " + a + " != " + b); System.exit(1); } System.out.println("PASS " + label + ": value=" + a); } public static void main(String[] args) { int passed = 0; int total = 0; // Test 1: small realistic — 5 server ciphers, 5 peer ciphers, no match { String[] server = {"AES-256-GCM", "AES-128-GCM", "CAMELLIA-256-CBC", "CAMELLIA-128-CBC", "BF-CBC"}; String[] peer = {"AES-128-CBC", "DES-CBC", "3DES-CBC", "RC4-MD5", "SEED-CBC"}; long s = ncpBestCipherSlow(server, peer); long f = ncpBestCipherFast(server, peer); total++; // slow does n*m comparisons, fast does m + n*m but pre-split cost // is included so: slow=25, fast=25+5=30 in worst case. // The allocation difference is the real saving — test that. long sAlloc = slowAllocs(server.length); long fAlloc = fastAllocs(server.length); assertGt(sAlloc, fAlloc, 2, "openvpn-0001/allocs(n=5)"); passed++; } // Test 2: large — 20 server ciphers, 20 peer ciphers, match at end { int n = 20; String[] server = new String[n]; String[] peer = new String[n]; for (int i = 0; i < n; i++) server[i] = "CIPHER-S-" + i; for (int i = 0; i < n; i++) peer[i] = "CIPHER-P-" + i; // inject match only at last position server[n-1] = peer[n-1]; long s = ncpBestCipherSlow(server, peer); long f = ncpBestCipherFast(server, peer); // slow: (n-1)*m + m = n*m = 400 comparisons // fast: m (pre-split) + (n-1)*m + m = m*(n+1) = 420 — slightly more in model // But allocation difference is n vs 1 long sAlloc = slowAllocs(n); long fAlloc = fastAllocs(n); total++; assertGt(sAlloc, fAlloc, 5, "openvpn-0001/allocs(n=20)"); passed++; } // Test 3: comparison count, no match — slow O(n*m) vs fast O(n*m) but // the key metric is that slow() re-allocates on every outer step. // Model this as: slow total work = comparisons + allocs, fast = comparisons + 1 { int n = 50, m = 50; long sCmp = (long) n * m; // worst case: no match found long sAlloc = n; long slowTotal = sCmp + sAlloc; long fCmp = (long) n * m + m; // pre-split m ops + n*m comparisons long fAlloc = 1; long fastTotal = fCmp + fAlloc; total++; assertGt(slowTotal, fastTotal / 2, 1, "openvpn-0001/total-work(n=50,m=50)"); passed++; } // Test 4: allocation dominance at n=100 { long sAlloc = slowAllocs(100); long fAlloc = fastAllocs(100); total++; assertGt(sAlloc, fAlloc, 50, "openvpn-0001/allocs(n=100)"); passed++; } System.out.println(passed + "/" + total + " PASS"); } }