paperbot · PL 论文追踪

全部论文 待读 收藏

Toward Automatically Detecting Cross-Engine Asymptotic Complexity Divergence in JavaScript

面向自动检测 JavaScript 中跨引擎渐近复杂度分歧
ASE Proceedings of the 41st IEEE/ACM International Conference on Automated Software Engineering2026引用 0 inbox
Minseok Choe
crossref: 2026-10-09

AI 速览

一句话:提出跨引擎渐近复杂度分歧现象,并给出按各引擎增长率估计分散度自动检测该类分歧的方法

论文指出同一段 JavaScript 代码在不同引擎中可能落入不同的渐近复杂度类,称之为跨引擎渐近复杂度分歧(cross-engine asymptotic complexity divergence)。作者给出具体例证:立即 break 的 for..in 在 QuickJS 中为 O(1),而在 V8 与 SpiderMonkey 中为 O(n);一个构建并检查字符串的循环在 SpiderMonkey 中是线性的,但在 V8 与 QuickJS 中是二次的。针对该现象,论文提出对参数化程序 P(N) 改变输入规模参数,估计各引擎上的增长率,并按增长率的分散程度对候选程序排序,从而自动发现分歧案例及其触发条件。引擎内部的根因分析以及 Algorithmic DoS 可利用性的实证评估被明确列为后续工作。

问题
同一 JavaScript 程序在不同引擎中可能呈现不同的渐近复杂度,目前缺乏自动发现此类跨引擎分歧及其触发条件的手段。
方法
针对参数化程序 P(N) 改变输入规模参数,估计每个引擎上的程序增长率,并以各引擎增长率估计值的分散程度对候选程序排序,以筛选出分歧案例。
评估
摘要仅给出实例性观察,即 for..in 立即 break 与字符串构建—检查循环在 V8、SpiderMonkey、QuickJS 三个引擎中的复杂度差异;系统的实证评估、引擎内部根因分析与 Algorithmic DoS 可利用性均留作后续研究。
原文摘要(Abstract)

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.

链接与引用

DOI 原文 · PDF(开放获取) ·

BibTeX
@inproceedings{paperbot12504,
  title = {Toward Automatically Detecting Cross-Engine Asymptotic Complexity Divergence in JavaScript},
  author = {Minseok Choe},
  booktitle = {ASE},
  year = {2026},
  doi = {10.1145/3832783.3844571}
}