网络上网控制软件中的Node.js布隆过滤器拦截算法

/**
 * 布隆过滤器参数计算器
 * @param {number} n - 预期插入数据量
 * @param {number} p - 目标误判率（如0.001表示0.1%）
 * @returns {Object} 最优参数{m:位数组长度, k:哈希函数数量}
 */
function calculateBloomFilterParams(n, p) {
    if (p <= 0 || p >= 1) {
        throw new Error('目标误判率必须介于(0,1)之间');
    }
    if (n <= 0) {
        throw new Error('预期数据量必须大于0');
    }
    const m = Math.ceil(-(n * Math.log(p)) / (Math.log(2) ** 2));
    const k = Math.ceil((m / n) * Math.log(2));
    return { m, k };
}
module.exports = { calculateBloomFilterParams };

const crypto = require('crypto');
const { calculateBloomFilterParams } = require('./bloomFilterParams');
class BloomFilter {
    /**
     * 初始化布隆过滤器
     * @param {Object} options - 配置项
     * @param {number} options.expectedDataCount - 预期插入数据量
     * @param {number} options.falsePositiveRate - 目标误判率
     */
    constructor({ expectedDataCount = 100000, falsePositiveRate = 0.001 }) {
        // 计算最优参数
        const { m, k } = calculateBloomFilterParams(expectedDataCount, falsePositiveRate);
        this.m = m; // 位数组长度（bit）
        this.k = k; // 哈希函数数量
        // 用Buffer存储位数组，长度为字节数（向上取整）
        this.bitArray = Buffer.alloc(Math.ceil(m / 8), 0);
    }
    /**
     * 生成多个独立哈希值
     * @param {string} data - 待哈希数据（如IP地址、域名）
     * @returns {number[]} 哈希索引数组
     */
    generateHashes(data) {
        const hashes = [];
        // 通过改变盐值生成不同哈希
        for (let i = 0; i < this.k; i++) {
            const hash = crypto.createHash('sha256')
                .update(data + i) // 加盐区分不同哈希函数
                .digest('hex');
            // 将十六进制哈希转为十进制数字，取模得到索引
            const index = BigInt(`0x${hash}`) % BigInt(this.m);
            hashes.push(Number(index));
        }
        return hashes;
    }
    /**
     * 插入数据到布隆过滤器（如拦截地址）
     * @param {string} data - 待插入数据
     */
    insert(data) {
        const indexes = this.generateHashes(data);
        indexes.forEach(index => {
            const byteIndex = Math.floor(index / 8); // 计算所在字节索引
            const bitOffset = index % 8; // 计算字节内位偏移
            // 将对应位设为1（按位或操作）
            this.bitArray[byteIndex] |= (1 << bitOffset);
        });
    }
    /**
     * 批量插入数据
     * @param {string[]} dataArray - 待插入数据数组
     */
    batchInsert(dataArray) {
        dataArray.forEach(data => this.insert(data));
    }
    /**
     * 查询数据是否可能存在
     * @param {string} data - 待查询数据（如请求地址）
     * @returns {boolean} true=可能存在（需二次校验），false=一定不存在
     */
    exists(data) {
        const indexes = this.generateHashes(data);
        return indexes.every(index => {
            const byteIndex = Math.floor(index / 8);
            const bitOffset = index % 8;
            // 检查对应位是否为1（按位与操作）
            return (this.bitArray[byteIndex] & (1 << bitOffset)) !== 0;
        });
    }
}
module.exports = BloomFilter;

const BloomFilter = require('./BloomFilter');
// 1. 初始化布隆过滤器（适配10万条拦截地址，误判率0.1%）
const filter = new BloomFilter({
    expectedDataCount: 100000,
    falsePositiveRate: 0.001
});
// 2. 模拟网络上网控制软件的拦截名单（批量插入恶意IP）
const maliciousIPs = [
    '192.168.1.101', '10.0.0.5', '203.0.113.88',
    // ... 此处省略99997条恶意IP
];
filter.batchInsert(maliciousIPs);
console.log('拦截名单导入完成');
// 3. 模拟网络请求地址校验流程
function checkAddress(address, preciseDB) {
    console.log(`\n校验地址: ${address}`);
    const isPossibleMalicious = filter.exists(address);
    if (!isPossibleMalicious) {
        return console.log('结果：安全地址，允许访问');
    }
    // 二次校验（布隆过滤器判断可能存在时，查询精确数据库）
    const isReallyMalicious = preciseDB.includes(address);
    if (isReallyMalicious) {
        return console.log('结果：恶意地址，执行拦截');
    } else {
        return console.log('结果：误判，允许访问');
    }
}
// 模拟精确数据库（存储真实恶意IP）
const preciseMaliciousDB = [...maliciousIPs];
// 测试不同类型地址
checkAddress('192.168.1.101', preciseMaliciousDB); // 恶意地址
checkAddress('192.168.1.200', preciseMaliciousDB); // 安全地址
checkAddress('203.0.113.88', preciseMaliciousDB); // 恶意地址
checkAddress('172.16.0.1', preciseMaliciousDB);     // 安全地址