#algorithmic-complexity-vulnerability

共收录 1 条相关安全情报。

← 返回所有主题
👥 作者: Yuanmin Xie, Xiangfan Wu, Wenhao Wu, Lingyun Ying, Puzhuo Liu, Haipeng Qu, Zhongyuan Chen, Min Zhou, Chengnian Sun

算法复杂度漏洞(ACV)是指攻击者通过精心构造的输入触发目标系统的最坏情况执行行为,导致严重性能退化或拒绝服务。现有ACV检测工具通常依赖模糊测试、符号执行或混合分析,但存在语言特异性、需要大量人工构建测试框架以及运行时插桩开销大等问题。本文提出ShadowProbe,一个可扩展且语言无关的ACV发现框架。其核心思路是:许多看似无害的标准库API隐藏了非平凡的计算成本(称为“影子复杂度”),攻击者可利用这些成本诱发意外的超线性运行行为。ShadowProbe采用多阶段流水线:首先通过轻量静态分析筛选候选函数,依据影子复杂度信号;然后从项目级符号自动重建最小可执行上下文;再借助大语言模型(LLM)合成尺寸可控的输入以探测最坏情况行为;最后通过执行时间测量和鲁棒统计增长推断来验证候选,区分真正的算法爆炸与运行时噪声(如垃圾回收、JIT编译效应)。在WISE基准测试上,ShadowProbe持续提升了分析效率。进一步将其应用于大规模系统,包括CPython、JDK、Zig、Rustc和vLLM,发现了许多先前未知的ACV,其中大部分已被维护者确认并部分修复。这些结果表明ShadowProbe能够在多样化的真实世界代码库中识别隐藏的算法风险。本文适合安全工程师、性能工程师以及关注软件供应链安全的开发人员阅读。

💡 推荐理由: 算法复杂度漏洞(ACV)难以通过常规测试发现,但可导致严重DoS风险。ShadowProbe首次实现语言可扩展的轻量级检测,已在大规模系统中找到多个被确认的漏洞,对保障关键基础设施稳定性有直接价值。

🎯 建议动作: 研究跟进:评估该框架对内部关键系统的适用性,并关注其后续工具化进展。

排序因子: 来自 arXiv 其他板块 (+2) | 命中热门研究主题 (+2) | Community 数据源 (+1) | LLM 评分加成 (+0.6)