Files

436 lines
17 KiB
JavaScript
Raw Permalink Normal View History

/**
* Test PLTC Correctness with Zanzibar Rules
*
* Verifies that PLTC (with SCC condensation) correctly answers queries
* when complex Zanzibar rules (ChainRule, ParentRule, etc.) are used.
*
* Key test: PLTC only sees "agnostic" base edges, not logical edges.
* We verify that PLTC's transitive closure on base edges matches
* the authorization logic results.
*/
import { Arbiter } from '../src/index.js';
/**
* Test Case 1: ChainRule with cycles
*/
function testCase1_ChainRuleWithCycles() {
console.log('\n' + '='.repeat(80));
console.log('Test Case 1: ChainRule with Friend Cycles');
console.log('='.repeat(80));
const arbiter = new Arbiter({
fastConstructionMode: true,
enableInference: false
});
// Create users with friend relationships (bidirectional = cycles)
arbiter.addNode('user:alice', 'user');
arbiter.addNode('user:bob', 'user');
arbiter.addNode('user:charlie', 'user');
arbiter.addNode('file:doc1', 'file');
arbiter.addNode('file:doc2', 'file');
// Friend relationships (bidirectional = creates cycles)
arbiter.addRelation('user:alice', 'friend', 'user:bob');
arbiter.addRelation('user:bob', 'friend', 'user:alice');
arbiter.addRelation('user:bob', 'friend', 'user:charlie');
arbiter.addRelation('user:charlie', 'friend', 'user:bob');
// Ownership
arbiter.addRelation('user:bob', 'owns', 'file:doc1');
arbiter.addRelation('user:charlie', 'owns', 'file:doc2');
// Configure rules
arbiter.setRelationConfig('friend', { type: 'direct' });
arbiter.setRelationConfig('owns', { type: 'direct' });
// Chain rule: friend_file = friend -> owns
arbiter.setRelationConfig('friend_file', {
type: 'chain',
steps: [
{ relation: 'friend', direction: 'out' },
{ relation: 'owns', direction: 'out' }
]
});
console.log('Graph structure:');
console.log(' alice <-> bob <-> charlie (friend cycles)');
console.log(' bob -> doc1 (owns)');
console.log(' charlie -> doc2 (owns)');
console.log(' Chain rule: friend_file = friend -> owns');
// Initialize PLTC
arbiter.graphManager.initializeReachabilityChecker();
const stats = arbiter.getReachabilityStats();
console.log(`\nPLTC Stats: ${stats.pltcInitialized ? '✓' : '✗'}`);
console.log(` SCCs: ${stats.sccCount || 'N/A'}`);
// Test queries
const testQueries = [
{ source: 'user:alice', relation: 'friend_file', target: 'file:doc1', expected: true, desc: 'alice -> friend(bob) -> owns(doc1)' },
{ source: 'user:alice', relation: 'friend_file', target: 'file:doc2', expected: true, desc: 'alice -> friend(bob) -> friend(charlie) -> owns(doc2)' },
{ source: 'user:bob', relation: 'friend_file', target: 'file:doc1', expected: true, desc: 'bob -> owns(doc1) (direct)' },
{ source: 'user:bob', relation: 'friend_file', target: 'file:doc2', expected: true, desc: 'bob -> friend(charlie) -> owns(doc2)' },
{ source: 'user:charlie', relation: 'friend_file', target: 'file:doc1', expected: true, desc: 'charlie -> friend(bob) -> owns(doc1)' },
{ source: 'user:charlie', relation: 'friend_file', target: 'file:doc2', expected: true, desc: 'charlie -> owns(doc2) (direct)' },
];
console.log('\nTesting ChainRule queries:');
let correct = 0;
let incorrect = 0;
for (const query of testQueries) {
// Get ground truth using authorization logic (bypassPLTC to get true result)
const groundTruth = arbiter.check(query.source, query.relation, query.target, {
bypassPLTC: true,
noInfer: true
});
const groundTruthBool = groundTruth && groundTruth.possibility > 0;
// Get PLTC result (via isReachable - PLTC is used internally)
const pltcReachable = arbiter.isReachable(query.source, query.target);
// Get authorization result (uses PLTC internally for fast-fail)
const authResult = arbiter.check(query.source, query.relation, query.target, {
noInfer: true
});
const authResultBool = authResult && authResult.possibility > 0;
// For chain rules, PLTC should detect reachability, but authorization logic determines access
// We expect: groundTruth === authResult (authorization should be correct)
// And: pltcReachable should be true if groundTruth is true (PLTC should not have false negatives)
const pltcCorrect = !groundTruthBool || pltcReachable; // PLTC should not have false negatives
const authCorrect = groundTruthBool === authResultBool;
if (pltcCorrect && authCorrect) {
correct++;
console.log(`${query.desc}`);
console.log(` Ground truth: ${groundTruthBool}, PLTC reachable: ${pltcReachable}, Auth: ${authResultBool}`);
} else {
incorrect++;
console.log(`${query.desc}`);
console.log(` Ground truth: ${groundTruthBool}, PLTC reachable: ${pltcReachable}, Auth: ${authResultBool}`);
if (!pltcCorrect) {
console.log(` ERROR: PLTC false negative!`);
}
if (!authCorrect) {
console.log(` ERROR: Authorization logic incorrect!`);
}
}
}
console.log(`\nResults: ${correct} correct, ${incorrect} incorrect`);
return incorrect === 0;
}
/**
* Test Case 2: Multi-hop ChainRule
*/
function testCase2_MultiHopChain() {
console.log('\n' + '='.repeat(80));
console.log('Test Case 2: Multi-hop ChainRule');
console.log('='.repeat(80));
const arbiter = new Arbiter({
fastConstructionMode: true,
enableInference: false
});
// Create hierarchy: user -> team -> project -> resource
arbiter.addNode('user:alice', 'user');
arbiter.addNode('team:eng', 'team');
arbiter.addNode('project:web', 'project');
arbiter.addNode('resource:server1', 'resource');
// Relations
arbiter.addRelation('user:alice', 'member_of', 'team:eng');
arbiter.addRelation('team:eng', 'owns', 'project:web');
arbiter.addRelation('project:web', 'has_access', 'resource:server1');
// Configure rules
arbiter.setRelationConfig('member_of', { type: 'direct' });
arbiter.setRelationConfig('owns', { type: 'direct' });
arbiter.setRelationConfig('has_access', { type: 'direct' });
// Multi-hop chain: user_resource = member_of -> owns -> has_access
arbiter.setRelationConfig('user_resource', {
type: 'chain',
steps: [
{ relation: 'member_of', direction: 'out' },
{ relation: 'owns', direction: 'out' },
{ relation: 'has_access', direction: 'out' }
]
});
console.log('Graph structure:');
console.log(' alice -> eng -> web -> server1');
console.log(' Chain rule: user_resource = member_of -> owns -> has_access');
// Initialize PLTC
arbiter.graphManager.initializeReachabilityChecker();
// Test query
const groundTruth = arbiter.check('user:alice', 'user_resource', 'resource:server1', {
bypassPLTC: true,
noInfer: true
});
const groundTruthBool = groundTruth && groundTruth.possibility > 0;
const pltcReachable = arbiter.isReachable('user:alice', 'resource:server1');
const authResult = arbiter.check('user:alice', 'user_resource', 'resource:server1', {
noInfer: true
});
const authResultBool = authResult && authResult.possibility > 0;
console.log('\nTesting multi-hop chain:');
console.log(` Ground truth: ${groundTruthBool}`);
console.log(` PLTC reachable: ${pltcReachable}`);
console.log(` Auth result: ${authResultBool}`);
const pltcCorrect = !groundTruthBool || pltcReachable;
const authCorrect = groundTruthBool === authResultBool;
if (pltcCorrect && authCorrect) {
console.log(' ✓ PASS');
return true;
} else {
console.log(' ❌ FAIL');
if (!pltcCorrect) console.log(' PLTC false negative!');
if (!authCorrect) console.log(' Authorization incorrect!');
return false;
}
}
/**
* Test Case 3: ChainRule with cycles and multiple paths
*/
function testCase3_ChainRuleMultiplePaths() {
console.log('\n' + '='.repeat(80));
console.log('Test Case 3: ChainRule with Cycles and Multiple Paths');
console.log('='.repeat(80));
const arbiter = new Arbiter({
fastConstructionMode: true,
enableInference: false
});
// Create users in friend cycles
arbiter.addNode('user:alice', 'user');
arbiter.addNode('user:bob', 'user');
arbiter.addNode('user:charlie', 'user');
arbiter.addNode('user:dave', 'user');
arbiter.addNode('file:doc1', 'file');
arbiter.addNode('file:doc2', 'file');
// Friend network (creates cycles)
arbiter.addRelation('user:alice', 'friend', 'user:bob');
arbiter.addRelation('user:bob', 'friend', 'user:alice');
arbiter.addRelation('user:bob', 'friend', 'user:charlie');
arbiter.addRelation('user:charlie', 'friend', 'user:bob');
arbiter.addRelation('user:charlie', 'friend', 'user:dave');
arbiter.addRelation('user:dave', 'friend', 'user:charlie');
// Ownership
arbiter.addRelation('user:bob', 'owns', 'file:doc1');
arbiter.addRelation('user:dave', 'owns', 'file:doc2');
// Configure rules
arbiter.setRelationConfig('friend', { type: 'direct' });
arbiter.setRelationConfig('owns', { type: 'direct' });
// Chain rule: friend_file = friend -> owns
arbiter.setRelationConfig('friend_file', {
type: 'chain',
steps: [
{ relation: 'friend', direction: 'out' },
{ relation: 'owns', direction: 'out' }
]
});
console.log('Graph structure:');
console.log(' alice <-> bob <-> charlie <-> dave (friend cycles)');
console.log(' bob -> doc1, dave -> doc2 (ownership)');
// Initialize PLTC
arbiter.graphManager.initializeReachabilityChecker();
const stats = arbiter.getReachabilityStats();
console.log(`\nPLTC Stats: SCCs: ${stats.sccCount || 'N/A'}`);
// Test queries with multiple possible paths
const testQueries = [
{ source: 'user:alice', target: 'file:doc1', expected: true, desc: 'alice -> bob -> doc1' },
{ source: 'user:alice', target: 'file:doc2', expected: true, desc: 'alice -> bob -> charlie -> dave -> doc2' },
{ source: 'user:charlie', target: 'file:doc1', expected: true, desc: 'charlie -> bob -> doc1' },
{ source: 'user:charlie', target: 'file:doc2', expected: true, desc: 'charlie -> dave -> doc2' },
];
console.log('\nTesting queries with multiple paths:');
let correct = 0;
let incorrect = 0;
for (const query of testQueries) {
const groundTruth = arbiter.check(query.source, 'friend_file', query.target, {
bypassPLTC: true,
noInfer: true
});
const groundTruthBool = groundTruth && groundTruth.possibility > 0;
const pltcReachable = arbiter.isReachable(query.source, query.target);
const authResult = arbiter.check(query.source, 'friend_file', query.target, {
noInfer: true
});
const authResultBool = authResult && authResult.possibility > 0;
const pltcCorrect = !groundTruthBool || pltcReachable;
const authCorrect = groundTruthBool === authResultBool;
if (pltcCorrect && authCorrect) {
correct++;
console.log(`${query.desc}: PLTC=${pltcReachable}, Auth=${authResultBool}`);
} else {
incorrect++;
console.log(`${query.desc}: PLTC=${pltcReachable}, Auth=${authResultBool}, Truth=${groundTruthBool}`);
}
}
console.log(`\nResults: ${correct} correct, ${incorrect} incorrect`);
return incorrect === 0;
}
/**
* Test Case 4: ParentRule (hierarchical)
*
* ParentRule semantics:
* - Hierarchical relation: 'contains' (parent contains child)
* - Access relation: 'can_access' (user can access object)
* - Rule: user has access to object if user has access to object's parent
*
* Query: check(alice, can_access, readme)
* Logic: find readme's parent (docs), check check(alice, can_access, docs)
*/
function testCase4_ParentRule() {
console.log('\n' + '='.repeat(80));
console.log('Test Case 4: ParentRule (Hierarchical)');
console.log('='.repeat(80));
const arbiter = new Arbiter({
fastConstructionMode: true,
enableInference: false
});
// Create folder hierarchy
arbiter.addNode('user:alice', 'user');
arbiter.addNode('folder:root', 'folder');
arbiter.addNode('folder:docs', 'folder');
arbiter.addNode('folder:projects', 'folder');
arbiter.addNode('file:readme', 'file');
// Hierarchical relationships (containment): parent contains child
arbiter.addRelation('folder:root', 'contains', 'folder:docs');
arbiter.addRelation('folder:root', 'contains', 'folder:projects');
arbiter.addRelation('folder:docs', 'contains', 'file:readme');
// Access relationships: user can access folder
arbiter.addRelation('user:alice', 'can_access', 'folder:root');
arbiter.addRelation('user:alice', 'can_access', 'folder:docs');
// Note: alice has access to root, so by ParentRule semantics, alice has access to everything under root
// This includes projects (since projects's parent is root)
// Configure rules
// 'can_access' uses ParentRule, which looks for 'contains' as the parent relation
arbiter.setRelationConfig('can_access', {
type: 'parent',
parentRelation: 'contains' // The hierarchical relation name
});
console.log('Graph structure:');
console.log(' Hierarchical: root contains docs, docs contains readme');
console.log(' Access: alice -> can_access -> root, alice -> can_access -> docs');
console.log(' Parent rule: user has access to object if user has access to object\'s parent');
// Initialize PLTC
arbiter.graphManager.initializeReachabilityChecker();
// Test queries
// Query: check(alice, can_access, readme)
// Logic: readme's parent is docs (via contains), check check(alice, can_access, docs)
// Since alice -> can_access -> docs exists, should return true
const testQueries = [
{ source: 'user:alice', target: 'file:readme', expected: true, desc: 'alice -> readme (via docs parent)' },
{ source: 'user:alice', target: 'folder:docs', expected: true, desc: 'alice -> docs (direct access)' },
{ source: 'user:alice', target: 'folder:projects', expected: true, desc: 'alice -> projects (via root parent - ParentRule grants access)' },
];
console.log('\nTesting ParentRule queries:');
let correct = 0;
let incorrect = 0;
for (const query of testQueries) {
const groundTruth = arbiter.check(query.source, 'can_access', query.target, {
bypassPLTC: true,
noInfer: true
});
const groundTruthBool = groundTruth && groundTruth.possibility > 0;
const pltcReachable = arbiter.isReachable(query.source, query.target);
const authResult = arbiter.check(query.source, 'can_access', query.target, {
noInfer: true
});
const authResultBool = authResult && authResult.possibility > 0;
const pltcCorrect = !groundTruthBool || pltcReachable;
const authCorrect = groundTruthBool === authResultBool;
if (pltcCorrect && authCorrect && groundTruthBool === query.expected) {
correct++;
console.log(`${query.desc}: ${authResultBool}`);
} else {
incorrect++;
console.log(`${query.desc}: PLTC=${pltcReachable}, Auth=${authResultBool}, Truth=${groundTruthBool}, Expected=${query.expected}`);
}
}
console.log(`\nResults: ${correct} correct, ${incorrect} incorrect`);
return incorrect === 0;
}
// Run all tests
console.log('='.repeat(80));
console.log('PLTC with Zanzibar Rules Correctness Tests');
console.log('='.repeat(80));
console.log('\nTesting that PLTC (with SCC) correctly answers queries');
console.log('when complex Zanzibar rules are used (ChainRule, ParentRule, etc.)');
console.log('\nKey verification: PLTC only sees base edges, not logical edges.');
console.log('We verify that PLTC\'s transitive closure matches authorization logic.');
const results = {
test1: testCase1_ChainRuleWithCycles(),
test2: testCase2_MultiHopChain(),
test3: testCase3_ChainRuleMultiplePaths(),
test4: testCase4_ParentRule()
};
console.log('\n' + '='.repeat(80));
console.log('Summary');
console.log('='.repeat(80));
console.log(`Test 1 (ChainRule with cycles): ${results.test1 ? '✅ PASS' : '❌ FAIL'}`);
console.log(`Test 2 (Multi-hop chain): ${results.test2 ? '✅ PASS' : '❌ FAIL'}`);
console.log(`Test 3 (Multiple paths): ${results.test3 ? '✅ PASS' : '❌ FAIL'}`);
console.log(`Test 4 (ParentRule): ${results.test4 ? '✅ PASS' : '❌ FAIL'}`);
const allPassed = Object.values(results).every(r => r);
if (allPassed) {
console.log('\n✅ ALL TESTS PASSED: PLTC with SCC correctly handles Zanzibar rules!');
console.log('\nConclusion:');
console.log(' - PLTC only sees base edges (agnostic relations)');
console.log(' - SCC condensation preserves reachability correctly');
console.log(' - PLTC\'s transitive closure matches authorization logic');
console.log(' - Complex rules (ChainRule, ParentRule) work correctly with SCC');
} else {
console.log('\n❌ SOME TESTS FAILED: PLTC with SCC has issues with Zanzibar rules!');
process.exit(1);
}