基于 SciPy.sparse 的稀疏矩阵运算及其在网络安全关联分析中的应用

import numpy as np
from scipy.sparse import csr_matrix

# 模拟 10000 员工 × 5000 权限的授权矩阵
m, n = 10000, 5000
density = 0.0005  # 0.05% 的非零元
nnz = int(m * n * density)

rows = np.random.randint(0, m, nnz)
cols = np.random.randint(0, n, nnz)
data = np.ones(nnz, dtype=np.int8)

# 稀疏存储
A_sparse = csr_matrix((data, (rows, cols)), shape=(m, n))

# 内存对比计算
sparse_bytes = A_sparse.data.nbytes + A_sparse.indices.nbytes + A_sparse.indptr.nbytes
dense_bytes = A_sparse.toarray().nbytes

print(f"矩阵维度: {m} × {n}")
print(f"非零元素: {nnz} (密度 {density*100:.3f}%)")
print(f"稠密存储内存: {dense_bytes / 1024**2:.2f} MB")
print(f"稀疏存储内存: {sparse_bytes / 1024**2:.2f} MB")
print(f"压缩倍数: {dense_bytes / sparse_bytes:.1f}×")

coo_matrix((data, (i, j)), shape=(M, N), dtype=None, copy=False)

csr_matrix((data, indices, indptr), shape=(M, N))
# 或从其他格式转换
csr_matrix(coo_obj)

import numpy as np
from scipy.sparse import coo_matrix, csr_matrix, csc_matrix, lil_matrix

# 原始非零元数据（三元组）
data = np.array([1, 2, 3, 4, 5, 6])
row  = np.array([0, 1, 1, 2, 3, 3])
col  = np.array([0, 1, 3, 2, 0, 3])

# 步骤1：COO 构造（最直接）
A_coo = coo_matrix((data, (row, col)), shape=(4, 4))
print("COO 格式矩阵：")
print(A_coo.toarray())

# 步骤2：转换为 CSR（运算最快）
A_csr = A_coo.tocsr()
print("\nCSR 内部结构：")
print(f"  data    = {A_csr.data}")      # 非零元值
print(f"  indices = {A_csr.indices}")  # 列索引
print(f"  indptr  = {A_csr.indptr}")   # 行指针：[0, 1, 3, 4, 6]

# 步骤3：转换为 CSC
A_csc = A_coo.tocsc()
print("\nCSC 内部结构：")
print(f"  data    = {A_csc.data}")
print(f"  indices = {A_csc.indices}")  # 行索引
print(f"  indptr  = {A_csc.indptr}")   # 列指针

# 步骤4：LIL 逐元素修改
A_lil = lil_matrix((4, 4))
A_lil[0, 0] = 10           # 单个元素赋值
A_lil[1, [1, 3]] = [20, 30]  # 整行批量赋值
print("\nLIL 修改后：")
print(A_lil.toarray())

from scipy.sparse import csr_matrix

A = csr_matrix([[1, 0, 2], [0, 3, 0], [4, 0, 5]])
B = csr_matrix([[0, 6, 0], [7, 0, 8], [0, 9, 0]])

# 稀疏 + 稀疏（结果仍为稀疏）
C = A + B
print("A + B =")
print(C.toarray())

# 稀疏 * 标量
D = 2.5 * A
print("\n2.5 * A =")
print(D.toarray())

v = np.array([1, 2, 3])

# 稀疏矩阵 × 稠密向量
print("A @ v =", A @ v)

# 稀疏矩阵 × 稀疏矩阵（结果仍为稀疏）
E = A @ B
print("\nA @ B =")
print(E.toarray())

# 行切片（CSR 高效）
row_0 = A[0, :]          # 第 0 行
rows_01 = A[[0, 2], :]   # 第 0、2 行

# 列切片（CSR 支持，但效率不如 CSC）
col_1 = A[:, 1]

# 单元素访问
print(f"A[0, 2] = {A[0, 2]}")

eigs(A, k=6, M=None, sigma=None, which='LM', v0=None, ncv=None, 
     maxiter=None, tol=0, return_eigenvectors=True, Minv=None, OPinv=None, OPpart=None)

from scipy.sparse.linalg import eigs
from scipy.sparse import diags

# 构造 1000×1000 三对角稀疏矩阵（有限差分常见形式）
n = 1000
main_diag = 2 * np.ones(n)
off_diag = -1 * np.ones(n - 1)

A_tri = diags([off_diag, main_diag, off_diag], offsets=[-1, 0, 1], format='csr')

# 计算前 5 个最小特征值
evals, evecs = eigs(A_tri, k=5, which='SM')

print("前 5 个最小特征值：")
print(np.real(evals))

import numpy as np
from scipy.sparse import coo_matrix, csr_matrix

# 设置随机种子以保证结果可复现
np.random.seed(2026)

# 模拟企业规模
n_users = 2000   # 员工数
n_perms = 800    # 权限项数
density = 0.003  # 授权密度（真实系统通常 < 0.5%）

# 计算非零元数量
nnz = int(n_users * n_perms * density)

# 生成随机的用户-权限授权记录
rows = np.random.randint(0, n_users, nnz)  # 用户ID
cols = np.random.randint(0, n_perms, nnz)  # 权限ID

# 权限等级：1=读，2=写，3=执行，5=管理
# 管理权限最少，读权限最多，符合实际分布
vals = np.random.choice([1, 2, 3, 5], nnz, p=[0.5, 0.3, 0.15, 0.05])

# 先用 COO 格式构造（适合从原始三元组直接转换）
UP_coo = coo_matrix((vals, (rows, cols)), shape=(n_users, n_perms))

# 转换为 CSR 格式（适合后续运算）
UP = UP_coo.tocsr()

# 输出矩阵基本信息
print("=" * 50)
print("【步骤一】用户-权限授权矩阵构造完成")
print("=" * 50)
print(f"矩阵维度: {UP.shape}")
print(f"非零元素: {UP.nnz}")
print(f"实际密度: {UP.nnz / (n_users * n_perms) * 100:.3f}%")
print(f"稀疏存储内存: {(UP.data.nbytes + UP.indices.nbytes + UP.indptr.nbytes) / 1024**2:.3f} MB")
print(f"稠密等价内存: {UP.toarray().nbytes / 1024**2:.2f} MB")
print(f"压缩比: {UP.toarray().nbytes / (UP.data.nbytes + UP.indices.nbytes + UP.indptr.nbytes):.0f}×")

# 提取前 4×4 子矩阵观察
micro = UP[:4, :4]

# 转回 COO 以便观察三元组
micro_coo = micro.tocoo()

print("【步骤二】CSR 内部结构微观观察（前 4×4 子矩阵）")
print("-" * 50)
print(f"非零元值 (data):    {micro_coo.data}")
print(f"行索引 (row):       {micro_coo.row}")
print(f"列索引 (col):       {micro_coo.col}")
print("-" * 50)

# 观察 CSR 压缩后的结构
micro_csr = micro.tocsr()
print(f"CSR.data:    {micro_csr.data}")
print(f"CSR.indices: {micro_csr.indices}")
print(f"CSR.indptr:  {micro_csr.indptr}")
print("-" * 50)
print("indptr 解读：")
for i in range(4):
    start = micro_csr.indptr[i]
    end = micro_csr.indptr[i+1]
    if start == end:
        print(f"  第 {i} 行: 无非零元")
    else:
        cols = micro_csr.indices[start:end]
        vals = micro_csr.data[start:end]
        print(f"  第 {i} 行: 列索引 {cols.tolist()}, 值 {vals.tolist()}")

from scipy.sparse import csr_matrix

# 计算权限共现矩阵 C = M^T × M
# 结果自动保持为 CSR 格式
PP = (UP.T @ UP).astype(float)

# 去除自环（我们不关心权限与自身的共现）
PP.setdiag(0)

print("【步骤三】权限共现矩阵计算完成")
print("-" * 50)
print(f"共现矩阵维度: {PP.shape}")
print(f"非零元素: {PP.nnz}")
print(f"密度: {PP.nnz / (n_perms * n_perms) * 100:.3f}%")

# 找出共现度最高的 5 对权限
PP_coo = PP.tocoo()
top5_idx = np.argsort(PP_coo.data)[-5:][::-1]

print(f"\nTop 5 共现权限对（权限A, 权限B, 共现次数）：")
for idx in top5_idx:
    perm_a = PP_coo.row[idx]
    perm_b = PP_coo.col[idx]
    count = PP_coo.data[idx]
    print(f"  权限 {perm_a:3d} ↔ 权限 {perm_b:3d} : 共现 {count:.0f} 次")

from scipy.sparse.linalg import eigs

# 对权限共现矩阵进行稀疏特征值分解
# k=10: 计算前10个最大特征值
# which='LM': Largest Magnitude（模最大）
evals, evecs = eigs(PP, k=10, which='LM')

# eigs 返回的可能是复数（数值误差），取实部
evals = np.real(evals)
evals_sorted = np.sort(evals)[::-1]  # 从大到小排序

print("【步骤四】稀疏特征值分解 —— 异常社群检测")
print("-" * 50)
print(f"前 10 个最大特征值：")
for i, val in enumerate(evals_sorted, 1):
    print(f"  λ_{i:2d} = {val:8.2f}")

print("-" * 50)
print(f"λ_1 / λ_3 比值 = {evals_sorted[0] / evals_sorted[2]:.2f}")
print("\n审计提示：")
print("  • 若前几个特征值显著大于其余，说明存在紧密权限簇")
print("  • 若 λ_1/λ_3 > 2.0，建议提取对应特征向量，定位具体权限ID进行重点审查")

from scipy.sparse import csr_matrix

# 构造 8 节点的权限转移图（有向）
# 节点含义示例：0=普通读, 1=普通写, 2=配置读, 3=日志读, 4=备份读, 5=脚本执行, 6=网络配置, 7=管理员
edges = [
    (0, 2),   # 普通读 → 配置读
    (1, 2),   # 普通写 → 配置读
    (2, 5),   # 配置读 → 脚本执行
    (3, 5),   # 日志读 → 脚本执行
    (4, 5),   # 备份读 → 脚本执行
    (5, 7),   # 脚本执行 → 管理员
    (6, 7),   # 网络配置 → 管理员
]

# 构造稀疏邻接矩阵
row_idx = [e[0] for e in edges]
col_idx = [e[1] for e in edges]
Adj = csr_matrix(([1]*len(edges), (row_idx, col_idx)), shape=(8, 8))

# 计算两步转移矩阵 Adj^2
Adj2 = Adj @ Adj

print("【步骤五】间接权限提升路径检测")
print("-" * 50)
print(f"一步转移矩阵非零元: {Adj.nnz}")
print(f"两步转移矩阵非零元: {Adj2.nnz}")
print(f"新增间接路径数: {Adj2.nnz} 条")
print("-" * 50)
print("一步转移路径（直接）：")
for i, j in zip(Adj.nonzero()[0], Adj.nonzero()[1]):
    print(f"  权限 {i} → 权限 {j}")
print("-" * 50)
print("两步转移路径（间接提权）：")
for i, j in zip(Adj2.nonzero()[0], Adj2.nonzero()[1]):
    count = int(Adj2[i, j])
    print(f"  权限 {i} → ... → 权限 {j} (共 {count} 条路径)")

import matplotlib.pyplot as plt

# 创建一个综合可视化图
fig = plt.figure(figsize=(16, 10))

# (a) 用户-权限矩阵 spy 图
ax1 = plt.subplot(2, 3, 1)
ax1.spy(UP[:500, :200], markersize=1.5, color='#1B4965', aspect='auto')
ax1.set_title('(a) User-Permission Matrix (500x200)', fontsize=11)
ax1.set_xlabel('Permission ID')
ax1.set_ylabel('User ID')

# (b) 权限共现矩阵 spy 图
ax2 = plt.subplot(2, 3, 2)
ax2.spy(PP[:100, :100], markersize=2, color='#5FA8D3', aspect='auto')
ax2.set_title('(b) Permission Co-occurrence Matrix (100x100)', fontsize=11)
ax2.set_xlabel('Permission ID')
ax2.set_ylabel('Permission ID')

# (c) 特征值谱
ax3 = plt.subplot(2, 3, 3)
ax3.bar(range(1, 11), evals_sorted, color='#CA2E55', alpha=0.8, edgecolor='black', linewidth=0.5)
ax3.axhline(y=evals_sorted[2], color='#2E86AB', linestyle='--', linewidth=2, 
            label=f'阈值 λ₃={evals_sorted[2]:.1f}')
ax3.set_title('(c) Eigenvalue Spectrum (Anomaly Detection)', fontsize=11)
ax3.set_xlabel('Eigenvalue Index')
ax3.set_ylabel('Eigenvalue Magnitude')
ax3.legend(fontsize=9)

# (d) 一步权限转移
ax4 = plt.subplot(2, 3, 4)
ax4.spy(Adj, markersize=18, color='#F18F01', aspect='equal')
ax4.set_title('(d) One-Step Privilege Transfer', fontsize=11)
for i in range(8):
    for j in range(8):
        if Adj[i, j] == 1:
            ax4.text(j, i, '1', ha='center', va='center', color='white', fontsize=9, fontweight='bold')

# (e) 两步权限提升
ax5 = plt.subplot(2, 3, 5)
ax5.spy(Adj2, markersize=18, color='#C73E1D', aspect='equal')
ax5.set_title('(e) Two-Step Privilege Escalation (Adj²)', fontsize=11)
for i in range(8):
    for j in range(8):
        if Adj2[i, j] > 0:
            ax5.text(j, i, str(int(Adj2[i, j])), ha='center', va='center', 
                    color='white', fontsize=9, fontweight='bold')

# (f) 跨规模内存对比
ax6 = plt.subplot(2, 3, 6)
sizes = [500, 1000, 2000, 4000, 8000]
sparse_mems = []
dense_mems = []

for n in sizes:
    nnz_t = int(n * n * 0.001)  # 0.1% 密度
    r = np.random.randint(0, n, nnz_t)
    c = np.random.randint(0, n, nnz_t)
    v = np.random.rand(nnz_t)
    S = csr_matrix((v, (r, c)), shape=(n, n))
    sparse_mems.append((S.data.nbytes + S.indices.nbytes + S.indptr.nbytes) / 1024**2)
    dense_mems.append(S.toarray().nbytes / 1024**2)

x = np.arange(len(sizes))
width = 0.35
ax6.bar(x - width/2, dense_mems, width, label='Dense', color='#E63946', alpha=0.8)
ax6.bar(x + width/2, sparse_mems, width, label='Sparse', color='#06D6A0', alpha=0.8)
ax6.set_xticks(x)
ax6.set_xticklabels([str(s) for s in sizes], fontsize=9)
ax6.set_title('(f) Memory Comparison (nxn, 0.1% Density)', fontsize=11)
ax6.set_ylabel('MB (log)')
ax6.set_yscale('log')
ax6.legend(fontsize=9)

plt.suptitle('Fig.3  Comprehensive Visualization of Cybersecurity Privilege Correlation Analysis', fontsize=14, y=0.98)
plt.tight_layout(rect=[0, 0, 1, 0.96])
plt.show()