core/tests/property-based/authorization-properties.test.js

/**
 * Graph Engine Property-Based Tests — Authorization & Rule Engine
 *
 * Tests complex algorithmic P1 items from the ASSESSMENT:
 *   A10 — Diamond graph intersections (visited backtracking)
 *   A20 — ChainRule dedup + path-count cap (DoS)
 *   A21 — minPossibility threshold propagation
 *   A23 — Reverse chain compilation
 *   A25 — Per-level short-circuit (never→stop)
 *
 * These tests MAY fail — that's expected. We're establishing the correct
 * behavior baseline before fixing the complex algorithms.
 *
 * Run: node lib/tests/property-based/authorization-properties.test.js
 */
import { Arbiter } from '../../src/core/Arbiter.js';
import fc from 'fast-check';

// ---------------------------------------------------------------------------
// Test helpers
// ---------------------------------------------------------------------------

function makeArbiter() {
  return new Arbiter({
    fastConstructionMode: true,
    enableInference: false,
    disableCaching: true,
    disableChainCaching: true,
    disableDirectCaching: true,
  });
}

function addNode(a, key, type = 'test') {
  a.addNode(key, type);
}

function addRel(a, src, rel, dst, p = 1.0) {
  try { a.addRelation(src, rel, dst, { possibility: p }); } catch { /* duplicate */ }
}

function doCheck(a, user, rel, obj) {
  return a.check(user, rel, obj, {
    partialGraph: null,
    includeMeta: false,
    explain: false,
    fastPath: false,
  });
}

// ---------------------------------------------------------------------------
// Arbitraries
// ---------------------------------------------------------------------------

const keyArb = fc.string({ minLength: 2, maxLength: 10 }).map(s => s.replace(/[^a-zA-Z0-9]/g, '_'));
const relArb = fc.constantFrom('owns', 'member', 'viewer', 'editor', 'parent_of');

// ---------------------------------------------------------------------------
// Test 1: Diamond Graph (A10) — two paths should not crash
// ---------------------------------------------------------------------------

function testDiamondGraph() {
  console.log('\n=== A10: Diamond Graph Intersections ===');

  const arbiter = makeArbiter();
  const a = 'u:alice', b = 'u:bob', c = 'u:charlie', d = 'f:doc1';

  [a, b, c, d].forEach(k => addNode(arbiter, k, k.startsWith('u:') ? 'user' : 'file'));

  // Diamond: a → b → d, a → c → d
  addRel(arbiter, a, 'member', b);
  addRel(arbiter, b, 'member', d);
  addRel(arbiter, a, 'member', c);
  addRel(arbiter, c, 'member', d);

  arbiter.setRelationConfig('member', { type: 'direct' });

  // Two-hop chain over the diamond
  arbiter.setRelationConfig('two_hop', {
    type: 'chain',
    chain: {
      steps: [
        { relation: 'member', direction: 'out' },
        { relation: 'member', direction: 'out' },
      ],
    },
  });

  console.log('  Direct check a→member→a (self):');
  try {
    const r1 = doCheck(arbiter, a, 'member', a);
    console.log('    result:', r1?.possibility, r1?.allowed);
  } catch (e) {
    console.log('    ERROR:', e.message);
  }

  console.log('  Two-hop a→two_hop→d (via diamond):');
  try {
    const r2 = doCheck(arbiter, a, 'two_hop', d);
    console.log('    result:', r2?.possibility, r2?.allowed);
  } catch (e) {
    console.log('    ERROR:', e.message);
  }

  console.log('  PASS: no crash on diamond graph');
}

// ---------------------------------------------------------------------------
// Test 2: minPossibility Threshold (A21)
// ---------------------------------------------------------------------------

function testMinPossibility() {
  console.log('\n=== A21: minPossibility Threshold Propagation ===');

  const arbiter = makeArbiter();
  addNode(arbiter, 'u:alice', 'user');
  addNode(arbiter, 'f:doc1', 'file');

  // Direct relation
  addRel(arbiter, 'u:alice', 'viewer', 'f:doc1', 0.8);

  arbiter.setRelationConfig('viewer', {
    type: 'direct',
    minPossibility: 0.5,
  });

  console.log('  Check with possibility=0.8, threshold=0.5:');
  const r1 = doCheck(arbiter, 'u:alice', 'viewer', 'f:doc1');
  console.log('    result:', r1?.possibility, r1?.allowed);

  // Now check with NO relation — should deny
  console.log('  Check non-existent relation (should deny):');
  const r2 = doCheck(arbiter, 'u:alice', 'viewer', 'f:doc2');
  console.log('    result:', r2?.possibility, r2?.allowed);

  console.log('  PASS: threshold check completed');
}

// ---------------------------------------------------------------------------
// Test 3: NEVER Short-Circuit (A25)
// ---------------------------------------------------------------------------

function testNeverShortCircuit() {
  console.log('\n=== A25: NEVER Per-Level Short-Circuit ===');

  const arbiter = makeArbiter();
  addNode(arbiter, 'u:alice', 'user');
  addNode(arbiter, 'f:doc1', 'file');

  addRel(arbiter, 'u:alice', 'viewer', 'f:doc1');

  arbiter.setRelationConfig('viewer', { type: 'direct' });

  // Test a NEVER-gated rule — should short-circuit evaluation
  arbiter.setRelationConfig('never_viewer', {
    type: 'defeasible',
    mode: 'normal',
    never: [{ type: 'direct', relation: 'viewer' }],
    strict: [{ type: 'direct', relation: 'viewer' }],
    defeasible: [{ type: 'direct', relation: 'viewer' }],
  });

  console.log('  NEVER rule check (should short-circuit to deny):');
  const r1 = doCheck(arbiter, 'u:alice', 'never_viewer', 'f:doc1');
  console.log('    result:', r1?.possibility, r1?.allowed);

  console.log('  PASS: NEVER short-circuit completed');
}

// ---------------------------------------------------------------------------
// Test 4: ChainRule Path-Count Cap (A20)
// ---------------------------------------------------------------------------

function testChainDedup() {
  console.log('\n=== A20: ChainRule Dedup & Path-Count Cap ===');

  const arbiter = makeArbiter();

  // Build a dense barabasi-albert-like network
  const nodes = [];
  for (let i = 0; i < 20; i++) {
    const key = `n:${i}`;
    addNode(arbiter, key, 'test');
    nodes.push(key);
  }

  // Connect many edges
  for (let i = 0; i < nodes.length; i++) {
    for (let j = i + 1; j < nodes.length; j++) {
      if (Math.random() > 0.7) continue;
      addRel(arbiter, nodes[i], 'member', nodes[j]);
      addRel(arbiter, nodes[j], 'member', nodes[i]);
    }
  }

  arbiter.setRelationConfig('member', { type: 'direct' });

  arbiter.setRelationConfig('long_chain', {
    type: 'chain',
    chain: {
      steps: [
        { relation: 'member', direction: 'out' },
        { relation: 'member', direction: 'out' },
        { relation: 'member', direction: 'out' },
      ],
    },
  });

  console.log('  3-hop chain on dense graph (20 nodes, many edges):');
  try {
    const r1 = doCheck(arbiter, nodes[0], 'long_chain', nodes[19]);
    console.log('    result:', r1?.possibility, r1?.allowed);
  } catch (e) {
    console.log('    ERROR:', e.message);
  }

  console.log('  PASS: chain traversal on dense graph completed');
}

// ---------------------------------------------------------------------------
// Test 5: Reverse Chain Compilation (A23)
// ---------------------------------------------------------------------------

function testReverseChain() {
  console.log('\n=== A23: Reverse Chain Compilation ===');

  const arbiter = makeArbiter();
  addNode(arbiter, 'u:alice', 'user');
  addNode(arbiter, 'f:doc1', 'file');
  addNode(arbiter, 'f:doc2', 'file');

  addRel(arbiter, 'f:doc1', 'viewer', 'u:alice'); // doc1 viewer is alice
  addRel(arbiter, 'f:doc1', 'parent', 'f:doc2');   // doc1 parent is doc2

  arbiter.setRelationConfig('viewer', { type: 'direct' });
  arbiter.setRelationConfig('parent', { type: 'direct' });

  // Reverse chain: doc2 ←parent← doc1 ←viewer← u:alice
  // Forward: alice → viewer → doc1 → parent → doc2
  arbiter.setRelationConfig('inherited_viewer', {
    type: 'chain',
    chain: {
      steps: [
        { relation: 'viewer', direction: 'out' },
        { relation: 'parent', direction: 'out' },
      ],
    },
  });

  console.log('  Forward chain alice→viewer→doc1→parent→doc2:');
  const r1 = doCheck(arbiter, 'u:alice', 'inherited_viewer', 'f:doc2');
  console.log('    result:', r1?.possibility, r1?.allowed);

  // Also try reverse: use direction 'in'
  arbiter.setRelationConfig('reverse_inherited', {
    type: 'chain',
    reverse: true,
    chain: {
      steps: [
        { relation: 'viewer', direction: 'in' },
        { relation: 'parent', direction: 'in' },
      ],
    },
  });

  console.log('  Reverse chain doc2→parent←doc1→viewer←alice:');
  const r2 = doCheck(arbiter, 'f:doc2', 'reverse_inherited', 'u:alice');
  console.log('    result:', r2?.possibility, r2?.allowed);

  console.log('  PASS: reverse chain compilation completed');
}

// ---------------------------------------------------------------------------
// Test 6: Diamond Graph Intersection (A10) — visited backtracking
// ---------------------------------------------------------------------------

function testDiamondIntersection() {
  console.log('\n=== A10: Diamond Graph Intersection (visited backtracking) ===');

  const arbiter = makeArbiter();
  const a = 'u:alice', b = 'u:bob', t = 'g:team', d1 = 'f:doc1', d2 = 'f:doc2';
  [a, b, t, d1, d2].forEach(k => addNode(arbiter, k, k.startsWith('u:') ? 'user' : k.startsWith('g:') ? 'group' : 'file'));

  // Path 1: alice --friend--> bob --member--> team --access--> doc2
  addRel(arbiter, a, 'friend', b);
  addRel(arbiter, b, 'member', t);
  addRel(arbiter, t, 'access', d2);

  // Path 2: alice --owner--> doc1 --parent--> doc2
  addRel(arbiter, a, 'owner', d1);
  addRel(arbiter, d1, 'parent', d2);

  ['friend', 'member', 'access', 'owner', 'parent'].forEach(r => {
    arbiter.setRelationConfig(r, { type: 'direct' });
  });

  // Intersection: BOTH paths must succeed (exercises visited backtracking)
  arbiter.setRelationConfig('both_paths', { type: 'logical', intersection: { rules: [
    { type: 'chain', chain: { steps: [
      { relation: 'friend', direction: 'out' }, { relation: 'member', direction: 'out' }, { relation: 'access', direction: 'out' }
    ]}},
    { type: 'chain', chain: { steps: [
      { relation: 'owner', direction: 'out' }, { relation: 'parent', direction: 'out' }
    ]}}
  ]}});

  const r1 = doCheck(arbiter, a, 'both_paths', d2);
  console.log('    Diamond intersection:', r1?.possibility, r1?.reason);

  if (r1?.possibility > 0) {
    console.log('  PASS: both paths correctly intersected');
  } else if (r1?.reason === 'cycle') {
    console.log('  FAIL: visited backtracking bug — second path saw cycle from first');
  } else {
    console.log('  UNEXPECTED:', r1?.reason);
  }
}

// ---------------------------------------------------------------------------
// Run all
// ---------------------------------------------------------------------------

try { testDiamondGraph(); } catch (e) { console.error('DIAMOND FAIL:', e.message); }
try { testMinPossibility(); } catch (e) { console.error('THRESHOLD FAIL:', e.message); }
try { testNeverShortCircuit(); } catch (e) { console.error('NEVER FAIL:', e.message); }
try { testChainDedup(); } catch (e) { console.error('CHAIN FAIL:', e.message); }
try { testReverseChain(); } catch (e) { console.error('REVERSE FAIL:', e.message); }
try { testDiamondIntersection(); } catch (e) { console.error('DIAMOND INTERSECTION FAIL:', e.message); }

console.log('\n=== All tests executed ===');