557 lines
19 KiB
JavaScript
557 lines
19 KiB
JavaScript
|
/**
|
||
|
|
* Targeted B2C Diagnostic Test
|
||
|
|
*
|
||
|
|
* Purpose: Diagnose why B2C scenario has:
|
||
|
|
* 1. False negatives (over-refusing)
|
||
|
|
* 2. Low QPS (1002 vs 17241 in enterprise)
|
||
|
|
*
|
||
|
|
* Hypothesis:
|
||
|
|
* - SCC bug causing incorrect PLTC queries (fixed, but need to verify)
|
||
|
|
* - Chain evaluation not finding paths that exist
|
||
|
|
* - Execution path not using PLTC efficiently
|
||
|
|
*
|
||
|
|
* Approach:
|
||
|
|
* 1. Small controlled graph (50 users, 200 files) for easy inspection
|
||
|
|
* 2. Trace execution path for each query
|
||
|
|
* 3. Measure time in each phase
|
||
|
|
* 4. Verify SCC correctness
|
||
|
|
* 5. Verify PLTC queries
|
||
|
|
* 6. Verify chain evaluation
|
||
|
|
*/
|
||
|
|
|
||
|
|
import { Arbiter } from '../src/index.js';
|
||
|
|
|
||
|
|
// Helper function to generate preferential attachment edges (from original test)
|
||
|
|
function generatePreferentialAttachmentEdges(numNodes, avgDegree) {
|
||
|
|
const edges = [];
|
||
|
|
const degrees = new Array(numNodes).fill(0);
|
||
|
|
|
||
|
|
// Start with a small clique
|
||
|
|
for (let i = 0; i < Math.min(5, numNodes); i++) {
|
||
|
|
for (let j = i + 1; j < Math.min(5, numNodes); j++) {
|
||
|
|
edges.push([i, j]);
|
||
|
|
degrees[i]++;
|
||
|
|
degrees[j]++;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
// Preferential attachment
|
||
|
|
const totalEdges = Math.floor((numNodes * avgDegree) / 2);
|
||
|
|
for (let i = edges.length; i < totalEdges; i++) {
|
||
|
|
// Select source node with probability proportional to degree
|
||
|
|
let src = Math.floor(Math.random() * numNodes);
|
||
|
|
const srcProb = degrees[src] / (edges.length * 2 + 1);
|
||
|
|
if (Math.random() > srcProb) {
|
||
|
|
src = Math.floor(Math.random() * numNodes);
|
||
|
|
}
|
||
|
|
|
||
|
|
// Select target node with probability proportional to degree
|
||
|
|
let dst = Math.floor(Math.random() * numNodes);
|
||
|
|
while (dst === src) {
|
||
|
|
dst = Math.floor(Math.random() * numNodes);
|
||
|
|
}
|
||
|
|
const dstProb = degrees[dst] / (edges.length * 2 + 1);
|
||
|
|
if (Math.random() > dstProb) {
|
||
|
|
dst = Math.floor(Math.random() * numNodes);
|
||
|
|
while (dst === src) {
|
||
|
|
dst = Math.floor(Math.random() * numNodes);
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
edges.push([src, dst]);
|
||
|
|
degrees[src]++;
|
||
|
|
degrees[dst]++;
|
||
|
|
}
|
||
|
|
|
||
|
|
return edges;
|
||
|
|
}
|
||
|
|
|
||
|
|
// Small controlled B2C scenario
|
||
|
|
function setupSmallB2C() {
|
||
|
|
const arbiter = new Arbiter({
|
||
|
|
fastConstructionMode: true,
|
||
|
|
enableInference: false
|
||
|
|
});
|
||
|
|
|
||
|
|
const numUsers = 50;
|
||
|
|
const numFiles = 200;
|
||
|
|
|
||
|
|
// Create users
|
||
|
|
const users = [];
|
||
|
|
for (let i = 0; i < numUsers; i++) {
|
||
|
|
const userKey = `user:user${i}`;
|
||
|
|
users.push(userKey);
|
||
|
|
arbiter.addNode(userKey, 'user');
|
||
|
|
}
|
||
|
|
|
||
|
|
// Create a controlled friend graph (not random)
|
||
|
|
// Create 3 friend clusters with some cross-connections
|
||
|
|
console.log(' Building controlled friend graph...');
|
||
|
|
const clusters = [
|
||
|
|
users.slice(0, 15), // Cluster 1: users 0-14
|
||
|
|
users.slice(15, 30), // Cluster 2: users 15-29
|
||
|
|
users.slice(30, 50) // Cluster 3: users 30-49
|
||
|
|
];
|
||
|
|
|
||
|
|
// Within-cluster friendships (bidirectional)
|
||
|
|
for (const cluster of clusters) {
|
||
|
|
for (let i = 0; i < cluster.length; i++) {
|
||
|
|
for (let j = i + 1; j < Math.min(i + 5, cluster.length); j++) {
|
||
|
|
arbiter.addRelation(cluster[i], 'friend', cluster[j]);
|
||
|
|
arbiter.addRelation(cluster[j], 'friend', cluster[i]);
|
||
|
|
}
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
// Cross-cluster connections (fewer, for friend-of-friend testing)
|
||
|
|
for (let i = 0; i < 5; i++) {
|
||
|
|
const u1 = clusters[0][Math.floor(Math.random() * clusters[0].length)];
|
||
|
|
const u2 = clusters[1][Math.floor(Math.random() * clusters[1].length)];
|
||
|
|
arbiter.addRelation(u1, 'friend', u2);
|
||
|
|
arbiter.addRelation(u2, 'friend', u1);
|
||
|
|
}
|
||
|
|
|
||
|
|
// Create files with known owners
|
||
|
|
console.log(' Creating files with known owners...');
|
||
|
|
const files = [];
|
||
|
|
for (let i = 0; i < numFiles; i++) {
|
||
|
|
const fileKey = `file:file${i}`;
|
||
|
|
files.push(fileKey);
|
||
|
|
arbiter.addNode(fileKey, 'file');
|
||
|
|
|
||
|
|
// Assign owner: first 100 files to cluster 1, next 50 to cluster 2, rest to cluster 3
|
||
|
|
let owner;
|
||
|
|
if (i < 100) {
|
||
|
|
owner = clusters[0][i % clusters[0].length];
|
||
|
|
} else if (i < 150) {
|
||
|
|
owner = clusters[1][(i - 100) % clusters[1].length];
|
||
|
|
} else {
|
||
|
|
owner = clusters[2][(i - 150) % clusters[2].length];
|
||
|
|
}
|
||
|
|
arbiter.addRelation(owner, 'owns', fileKey);
|
||
|
|
}
|
||
|
|
|
||
|
|
// Configure relations
|
||
|
|
arbiter.setRelationConfig('friend', { type: 'direct' });
|
||
|
|
arbiter.setRelationConfig('owns', { type: 'direct' });
|
||
|
|
|
||
|
|
// Chain rule: friend_file = user -> friend -> owns -> file
|
||
|
|
arbiter.setRelationConfig('friend_file', {
|
||
|
|
type: 'chain',
|
||
|
|
steps: [
|
||
|
|
{ relation: 'friend', direction: 'out' },
|
||
|
|
{ relation: 'owns', direction: 'out' }
|
||
|
|
]
|
||
|
|
});
|
||
|
|
|
||
|
|
// Friend-of-friend rule: user -> friend -> friend -> owns -> file
|
||
|
|
arbiter.setRelationConfig('friend_of_friend_file', {
|
||
|
|
type: 'chain',
|
||
|
|
steps: [
|
||
|
|
{ relation: 'friend', direction: 'out' },
|
||
|
|
{ relation: 'friend', direction: 'out' },
|
||
|
|
{ relation: 'owns', direction: 'out' }
|
||
|
|
]
|
||
|
|
});
|
||
|
|
|
||
|
|
console.log(` Created ${arbiter.relations.length} relations`);
|
||
|
|
console.log(` ${numUsers} users, ${numFiles} files`);
|
||
|
|
|
||
|
|
return { arbiter, users, files, clusters };
|
||
|
|
}
|
||
|
|
|
||
|
|
// Generate test queries with known expected results
|
||
|
|
function generateTestQueries(setup) {
|
||
|
|
const { arbiter, users, files, clusters } = setup;
|
||
|
|
const queries = [];
|
||
|
|
|
||
|
|
// Build helper maps to find actual valid paths
|
||
|
|
const userToFriends = new Map();
|
||
|
|
const friendToFiles = new Map();
|
||
|
|
|
||
|
|
for (const rel of arbiter.relations) {
|
||
|
|
const srcKey = arbiter.keyByNodeId.get(rel.src);
|
||
|
|
const dstKey = arbiter.keyByNodeId.get(rel.dst);
|
||
|
|
if (!srcKey || !dstKey) continue;
|
||
|
|
|
||
|
|
const relName = rel.rel || rel.relation;
|
||
|
|
|
||
|
|
if (relName === 'friend') {
|
||
|
|
if (!userToFriends.has(srcKey)) userToFriends.set(srcKey, []);
|
||
|
|
userToFriends.get(srcKey).push(dstKey);
|
||
|
|
} else if (relName === 'owns' && users.includes(srcKey) && files.includes(dstKey)) {
|
||
|
|
if (!friendToFiles.has(srcKey)) friendToFiles.set(srcKey, []);
|
||
|
|
friendToFiles.get(srcKey).push(dstKey);
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
// Test Case 1: Direct friend file access (should PASS)
|
||
|
|
// Find a user with a friend who owns a file
|
||
|
|
let foundFriendFile = false;
|
||
|
|
for (const user of users) {
|
||
|
|
const friends = userToFriends.get(user) || [];
|
||
|
|
for (const friend of friends) {
|
||
|
|
const friendFiles = friendToFiles.get(friend) || [];
|
||
|
|
if (friendFiles.length > 0) {
|
||
|
|
queries.push({
|
||
|
|
sourceKey: user,
|
||
|
|
targetKey: friendFiles[0],
|
||
|
|
relation: 'friend_file',
|
||
|
|
expected: true,
|
||
|
|
description: `Direct friend file access: ${user} -> friend -> ${friend} -> owns -> ${friendFiles[0]}`
|
||
|
|
});
|
||
|
|
foundFriendFile = true;
|
||
|
|
break;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
if (foundFriendFile) break;
|
||
|
|
}
|
||
|
|
|
||
|
|
// Test Case 2: Friend-of-friend file access (should PASS)
|
||
|
|
// Find a user -> friend -> friend -> owns -> file path
|
||
|
|
let foundFoFFile = false;
|
||
|
|
for (const user of users) {
|
||
|
|
const friends = userToFriends.get(user) || [];
|
||
|
|
for (const friend of friends) {
|
||
|
|
const friendFriends = userToFriends.get(friend) || [];
|
||
|
|
for (const fof of friendFriends) {
|
||
|
|
if (fof === user) continue; // Skip self
|
||
|
|
const fofFiles = friendToFiles.get(fof) || [];
|
||
|
|
if (fofFiles.length > 0) {
|
||
|
|
queries.push({
|
||
|
|
sourceKey: user,
|
||
|
|
targetKey: fofFiles[0],
|
||
|
|
relation: 'friend_of_friend_file',
|
||
|
|
expected: true,
|
||
|
|
description: `Friend-of-friend file access: ${user} -> ${friend} -> ${fof} -> owns -> ${fofFiles[0]}`
|
||
|
|
});
|
||
|
|
foundFoFFile = true;
|
||
|
|
break;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
if (foundFoFFile) break;
|
||
|
|
}
|
||
|
|
if (foundFoFFile) break;
|
||
|
|
}
|
||
|
|
|
||
|
|
// Test Case 3: No path (should FAIL)
|
||
|
|
// Find a file owned by a user with no connection to source
|
||
|
|
queries.push({
|
||
|
|
sourceKey: clusters[0][0],
|
||
|
|
targetKey: 'file:file150', // Owned by cluster 3, no connection
|
||
|
|
relation: 'friend_file',
|
||
|
|
expected: false,
|
||
|
|
description: 'No path (different cluster, no connection)'
|
||
|
|
});
|
||
|
|
|
||
|
|
// Test Case 4: Direct ownership (should PASS via 'owns', not chain)
|
||
|
|
queries.push({
|
||
|
|
sourceKey: clusters[0][0],
|
||
|
|
targetKey: 'file:file0',
|
||
|
|
relation: 'owns',
|
||
|
|
expected: true,
|
||
|
|
description: 'Direct ownership'
|
||
|
|
});
|
||
|
|
|
||
|
|
// Test Case 5: Simple friend_file within cluster (should PASS)
|
||
|
|
// Find a user -> friend -> owns -> file path within same cluster
|
||
|
|
for (const user of clusters[0]) {
|
||
|
|
const friends = userToFriends.get(user) || [];
|
||
|
|
for (const friend of friends) {
|
||
|
|
if (!clusters[0].includes(friend)) continue; // Must be in same cluster
|
||
|
|
const friendFiles = friendToFiles.get(friend) || [];
|
||
|
|
if (friendFiles.length > 0) {
|
||
|
|
queries.push({
|
||
|
|
sourceKey: user,
|
||
|
|
targetKey: friendFiles[0],
|
||
|
|
relation: 'friend_file',
|
||
|
|
expected: true,
|
||
|
|
description: `Friend file access within cluster: ${user} -> ${friend} -> owns -> ${friendFiles[0]}`
|
||
|
|
});
|
||
|
|
return queries; // Found all test cases
|
||
|
|
}
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
return queries;
|
||
|
|
}
|
||
|
|
|
||
|
|
// Trace execution path for a single query
|
||
|
|
function traceQuery(arbiter, query) {
|
||
|
|
const { sourceKey, targetKey, relation } = query;
|
||
|
|
const trace = {
|
||
|
|
query,
|
||
|
|
timings: {},
|
||
|
|
results: {},
|
||
|
|
path: []
|
||
|
|
};
|
||
|
|
|
||
|
|
const sourceId = arbiter.nodeIdByKey.get(sourceKey);
|
||
|
|
const targetId = arbiter.nodeIdByKey.get(targetKey);
|
||
|
|
|
||
|
|
trace.path.push(`Query: ${sourceKey} -> ${targetKey} (${relation})`);
|
||
|
|
trace.path.push(`Node IDs: ${sourceId} -> ${targetId}`);
|
||
|
|
|
||
|
|
// Phase 1: PLTC reachability check
|
||
|
|
const rc = arbiter.graphManager.operations.reachabilityChecker;
|
||
|
|
const pltcStart = Date.now();
|
||
|
|
|
||
|
|
if (rc && rc.pltcIndex && rc.pltcIndex.initialized) {
|
||
|
|
// PLTC handles SCC internally - query directly with original node IDs
|
||
|
|
const pltcQuery = rc.pltcIndex.query(sourceId, targetId);
|
||
|
|
const isReachable = arbiter.isReachable(sourceKey, targetKey);
|
||
|
|
|
||
|
|
trace.timings.pltc = Date.now() - pltcStart;
|
||
|
|
trace.results.pltc = {
|
||
|
|
pltcQuery,
|
||
|
|
isReachable
|
||
|
|
};
|
||
|
|
|
||
|
|
trace.path.push(`PLTC: query=${pltcQuery}, isReachable=${isReachable}`);
|
||
|
|
} else {
|
||
|
|
trace.results.pltc = { error: 'PLTC not initialized' };
|
||
|
|
}
|
||
|
|
|
||
|
|
// Phase 2: Authorization check (full chain evaluation)
|
||
|
|
const authStart = Date.now();
|
||
|
|
const authResult = arbiter.check(sourceKey, relation, targetKey, { noInfer: true });
|
||
|
|
trace.timings.auth = Date.now() - authStart;
|
||
|
|
|
||
|
|
const authPass = authResult && authResult.possibility > 0;
|
||
|
|
trace.results.auth = {
|
||
|
|
result: authResult,
|
||
|
|
pass: authPass,
|
||
|
|
method: authResult?.meta?.method || 'unknown'
|
||
|
|
};
|
||
|
|
|
||
|
|
trace.path.push(`Auth: ${authPass ? 'ALLOW' : 'DENY'} (method: ${trace.results.auth.method})`);
|
||
|
|
|
||
|
|
// Phase 3: Manual chain traversal (if chain rule)
|
||
|
|
if (relation === 'friend_file' || relation === 'friend_of_friend_file') {
|
||
|
|
trace.path.push(`Manual chain traversal:`);
|
||
|
|
const relationConfig = arbiter.relationConfigs.get(relation);
|
||
|
|
if (relationConfig && relationConfig.type === 'chain') {
|
||
|
|
const steps = relationConfig.steps;
|
||
|
|
trace.path.push(` Steps: ${steps.map(s => `${s.relation}:${s.direction}`).join(' -> ')}`);
|
||
|
|
|
||
|
|
// Manually trace the chain
|
||
|
|
let currentNodes = [sourceId];
|
||
|
|
for (let stepIdx = 0; stepIdx < steps.length; stepIdx++) {
|
||
|
|
const step = steps[stepIdx];
|
||
|
|
const nextNodes = [];
|
||
|
|
|
||
|
|
for (const nodeId of currentNodes) {
|
||
|
|
const nodeKey = arbiter.keyByNodeId.get(nodeId);
|
||
|
|
const outgoing = arbiter.relations.filter(r =>
|
||
|
|
r.src === nodeId && (r.rel || r.relation) === step.relation
|
||
|
|
);
|
||
|
|
|
||
|
|
trace.path.push(` Step ${stepIdx + 1} (${step.relation}): ${nodeKey} has ${outgoing.length} outgoing edges`);
|
||
|
|
|
||
|
|
for (const rel of outgoing) {
|
||
|
|
nextNodes.push(rel.dst);
|
||
|
|
const dstKey = arbiter.keyByNodeId.get(rel.dst);
|
||
|
|
trace.path.push(` → ${dstKey}`);
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
currentNodes = nextNodes;
|
||
|
|
|
||
|
|
// Check if target is reachable at this step
|
||
|
|
if (currentNodes.includes(targetId)) {
|
||
|
|
trace.path.push(` ✓ Target reached at step ${stepIdx + 1}!`);
|
||
|
|
break;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
if (!currentNodes.includes(targetId)) {
|
||
|
|
trace.path.push(` ✗ Target not reached through chain`);
|
||
|
|
}
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
return trace;
|
||
|
|
}
|
||
|
|
|
||
|
|
// Main diagnostic function
|
||
|
|
function runDiagnostics() {
|
||
|
|
console.log('🔬 B2C Diagnostic Test\n');
|
||
|
|
console.log('='.repeat(60));
|
||
|
|
|
||
|
|
// Setup
|
||
|
|
const setup = setupSmallB2C();
|
||
|
|
const { arbiter } = setup;
|
||
|
|
|
||
|
|
// Initialize PLTC
|
||
|
|
console.log('\n⚡ Initializing PLTC...');
|
||
|
|
const initStart = Date.now();
|
||
|
|
arbiter.graphManager.initializeReachabilityChecker();
|
||
|
|
const initTime = Date.now() - initStart;
|
||
|
|
const rc = arbiter.graphManager.operations.reachabilityChecker;
|
||
|
|
|
||
|
|
console.log(` Initialization time: ${initTime}ms`);
|
||
|
|
console.log(` PLTC initialized: ${rc.pltcIndex.initialized}`);
|
||
|
|
console.log(` Graph edges: ${rc.pltcIndex.graph.edges.size}`);
|
||
|
|
console.log(` SCC count: ${rc.pltcIndex.sccUnionFind?.getComponentCount() || 'N/A'}`);
|
||
|
|
|
||
|
|
// Generate test queries
|
||
|
|
const queries = generateTestQueries(setup);
|
||
|
|
|
||
|
|
// Trace each query
|
||
|
|
console.log('\n📊 Tracing queries...');
|
||
|
|
const allTraces = [];
|
||
|
|
let totalPLTCTime = 0;
|
||
|
|
let totalAuthTime = 0;
|
||
|
|
|
||
|
|
for (const query of queries) {
|
||
|
|
console.log(`\n${'-'.repeat(60)}`);
|
||
|
|
console.log(`Query: ${query.description}`);
|
||
|
|
console.log(` ${query.sourceKey} -> ${query.targetKey} (${query.relation})`);
|
||
|
|
console.log(` Expected: ${query.expected ? 'PASS' : 'FAIL'}`);
|
||
|
|
|
||
|
|
const trace = traceQuery(arbiter, query);
|
||
|
|
allTraces.push(trace);
|
||
|
|
|
||
|
|
totalPLTCTime += trace.timings.pltc || 0;
|
||
|
|
totalAuthTime += trace.timings.auth || 0;
|
||
|
|
|
||
|
|
// Print trace
|
||
|
|
for (const line of trace.path) {
|
||
|
|
console.log(` ${line}`);
|
||
|
|
}
|
||
|
|
|
||
|
|
// Check result
|
||
|
|
const actual = trace.results.auth.pass;
|
||
|
|
const match = actual === query.expected;
|
||
|
|
console.log(` Result: ${actual ? 'PASS' : 'FAIL'} ${match ? '✓' : '❌'} (Expected: ${query.expected ? 'PASS' : 'FAIL'})`);
|
||
|
|
|
||
|
|
if (!match) {
|
||
|
|
console.log(` ⚠️ MISMATCH!`);
|
||
|
|
if (query.expected && !actual) {
|
||
|
|
console.log(` False negative: Should pass but failed`);
|
||
|
|
console.log(` PLTC query: ${trace.results.pltc?.pltcQuery}`);
|
||
|
|
console.log(` isReachable: ${trace.results.pltc?.isReachable}`);
|
||
|
|
} else {
|
||
|
|
console.log(` False positive: Should fail but passed`);
|
||
|
|
}
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
// Performance summary
|
||
|
|
console.log(`\n${'='.repeat(60)}`);
|
||
|
|
console.log('Performance Summary:');
|
||
|
|
console.log('='.repeat(60));
|
||
|
|
console.log(`Total queries: ${queries.length}`);
|
||
|
|
console.log(`Total PLTC time: ${totalPLTCTime}ms (${(totalPLTCTime / queries.length).toFixed(2)}ms/query)`);
|
||
|
|
console.log(`Total Auth time: ${totalAuthTime}ms (${(totalAuthTime / queries.length).toFixed(2)}ms/query)`);
|
||
|
|
const pltcQPS = totalPLTCTime > 0 ? Math.round(queries.length / (totalPLTCTime / 1000)) : 'N/A';
|
||
|
|
const authQPS = totalAuthTime > 0 ? Math.round(queries.length / (totalAuthTime / 1000)) : 'N/A';
|
||
|
|
console.log(`PLTC QPS: ${pltcQPS}`);
|
||
|
|
console.log(`Auth QPS: ${authQPS}`);
|
||
|
|
|
||
|
|
// Accuracy summary
|
||
|
|
const correct = allTraces.filter((t, i) =>
|
||
|
|
t.results.auth.pass === queries[i].expected
|
||
|
|
).length;
|
||
|
|
console.log(`\nAccuracy: ${correct}/${queries.length} (${(correct / queries.length * 100).toFixed(1)}%)`);
|
||
|
|
|
||
|
|
// Diagnose issues
|
||
|
|
console.log(`\n${'='.repeat(60)}`);
|
||
|
|
console.log('Diagnosis:');
|
||
|
|
console.log('='.repeat(60));
|
||
|
|
|
||
|
|
const falseNegatives = allTraces.filter((t, i) =>
|
||
|
|
queries[i].expected && !t.results.auth.pass
|
||
|
|
);
|
||
|
|
|
||
|
|
if (falseNegatives.length > 0) {
|
||
|
|
console.log(`\n⚠️ False Negatives (${falseNegatives.length}):`);
|
||
|
|
for (const trace of falseNegatives) {
|
||
|
|
console.log(` ${trace.query.description}`);
|
||
|
|
console.log(` PLTC query: ${trace.results.pltc?.pltcQuery}`);
|
||
|
|
console.log(` isReachable: ${trace.results.pltc?.isReachable}`);
|
||
|
|
console.log(` Auth method: ${trace.results.auth.method}`);
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
const falsePositives = allTraces.filter((t, i) =>
|
||
|
|
!queries[i].expected && t.results.auth.pass
|
||
|
|
);
|
||
|
|
|
||
|
|
if (falsePositives.length > 0) {
|
||
|
|
console.log(`\n⚠️ False Positives (${falsePositives.length}):`);
|
||
|
|
for (const trace of falsePositives) {
|
||
|
|
console.log(` ${trace.query.description}`);
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
if (falseNegatives.length === 0 && falsePositives.length === 0) {
|
||
|
|
console.log(`\n✓ All queries correct!`);
|
||
|
|
}
|
||
|
|
|
||
|
|
// Performance analysis: Why is QPS low in full scenario?
|
||
|
|
console.log(`\n${'='.repeat(60)}`);
|
||
|
|
console.log('Performance Analysis:');
|
||
|
|
console.log('='.repeat(60));
|
||
|
|
|
||
|
|
const avgPLTCTime = totalPLTCTime / queries.length;
|
||
|
|
const avgAuthTime = totalAuthTime / queries.length;
|
||
|
|
const pltcFastFail = allTraces.filter(t =>
|
||
|
|
t.results.auth.method === 'pltc_fast_fail'
|
||
|
|
).length;
|
||
|
|
const pltcPass = allTraces.filter(t =>
|
||
|
|
t.results.pltc?.pltcQuery === true && t.results.auth.pass
|
||
|
|
).length;
|
||
|
|
|
||
|
|
console.log(`Average PLTC time: ${avgPLTCTime.toFixed(2)}ms`);
|
||
|
|
console.log(`Average Auth time: ${avgAuthTime.toFixed(2)}ms`);
|
||
|
|
console.log(`PLTC fast-fail count: ${pltcFastFail}`);
|
||
|
|
console.log(`PLTC pass (true positive): ${pltcPass}`);
|
||
|
|
console.log(`\nObservations:`);
|
||
|
|
console.log(` - PLTC is ${(avgPLTCTime / avgAuthTime).toFixed(1)}x faster than full auth check`);
|
||
|
|
console.log(` - ${((pltcFastFail / queries.length) * 100).toFixed(1)}% queries fast-failed by PLTC`);
|
||
|
|
console.log(` - ${((pltcPass / queries.length) * 100).toFixed(1)}% queries passed PLTC and auth`);
|
||
|
|
|
||
|
|
// Check if chain evaluation is the bottleneck
|
||
|
|
const chainQueries = queries.filter(q => q.relation === 'friend_file' || q.relation === 'friend_of_friend_file');
|
||
|
|
if (chainQueries.length > 0) {
|
||
|
|
const chainTraces = allTraces.filter((t, i) =>
|
||
|
|
chainQueries.some(cq => cq === queries[i])
|
||
|
|
);
|
||
|
|
const avgChainTime = chainTraces.reduce((sum, t) => sum + (t.timings.auth || 0), 0) / chainTraces.length;
|
||
|
|
console.log(` - Average chain evaluation time: ${avgChainTime.toFixed(2)}ms`);
|
||
|
|
console.log(` - Chain queries: ${chainQueries.length}/${queries.length}`);
|
||
|
|
}
|
||
|
|
|
||
|
|
// Debug: Check if PLTC is missing paths due to condensation
|
||
|
|
console.log(`\n${'='.repeat(60)}`);
|
||
|
|
console.log('PLTC Path Verification:');
|
||
|
|
console.log('='.repeat(60));
|
||
|
|
|
||
|
|
// For each chain query, verify if PLTC should see the path
|
||
|
|
for (let i = 0; i < queries.length; i++) {
|
||
|
|
const query = queries[i];
|
||
|
|
const trace = allTraces[i];
|
||
|
|
|
||
|
|
if (query.relation === 'friend_file' || query.relation === 'friend_of_friend_file') {
|
||
|
|
const sourceId = arbiter.nodeIdByKey.get(query.sourceKey);
|
||
|
|
const targetId = arbiter.nodeIdByKey.get(query.targetKey);
|
||
|
|
|
||
|
|
// PLTC handles SCC internally - query directly
|
||
|
|
const pltcQuery = rc.pltcIndex.query(sourceId, targetId);
|
||
|
|
|
||
|
|
console.log(`\nQuery: ${query.sourceKey} -> ${query.targetKey} (${query.relation})`);
|
||
|
|
console.log(` PLTC query result: ${pltcQuery}`);
|
||
|
|
console.log(` Expected PLTC result: ${query.expected ? 'true' : 'false'}`);
|
||
|
|
|
||
|
|
if (pltcQuery !== query.expected && query.expected) {
|
||
|
|
console.log(` ⚠️ PLTC MISMATCH: Expected true but got ${pltcQuery}`);
|
||
|
|
console.log(` This suggests PLTC's transitive closure is missing the path`);
|
||
|
|
}
|
||
|
|
}
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
runDiagnostics();
|
||
|
|
|