一句话:提出跨引擎渐近复杂度分歧现象,并给出按各引擎增长率估计分散度自动检测该类分歧的方法
论文指出同一段 JavaScript 代码在不同引擎中可能落入不同的渐近复杂度类,称之为跨引擎渐近复杂度分歧(cross-engine asymptotic complexity divergence)。作者给出具体例证:立即 break 的 for..in 在 QuickJS 中为 O(1),而在 V8 与 SpiderMonkey 中为 O(n);一个构建并检查字符串的循环在 SpiderMonkey 中是线性的,但在 V8 与 QuickJS 中是二次的。针对该现象,论文提出对参数化程序 P(N) 改变输入规模参数,估计各引擎上的增长率,并按增长率的分散程度对候选程序排序,从而自动发现分歧案例及其触发条件。引擎内部的根因分析以及 Algorithmic DoS 可利用性的实证评估被明确列为后续工作。
The same JavaScript code can enter different asymptotic complexity classes in different engines, a phenomenon we call cross-engine asymptotic complexity divergence. Across V8, SpiderMonkey, and QuickJS, entering a for..in that breaks immediately is O(1) in QuickJS and O(n) in V8 and SpiderMonkey; a build-and-inspect string loop is linear in SpiderMonkey but quadratic in V8 and QuickJS. We propose automatic detection over parameterized programs P(N): vary input size parameters and rank candidates by the spread of their estimated per-engine growth rates. Our goal is to find divergence cases and their triggering conditions. Engine-internal root-cause analysis and an empirical assessment of Algorithmic DoS exploitability are subsequent studies.