STAB：面向算法瓶颈的规格驱动测试

评估算法代码的效率需要能够暴露运行时瓶颈的测试用例。以往方法生成效率测试用例时，要么通过增大输入规模，要么通过生成让给定实现运行缓慢的代码特定输入。因此，它们并未触及驱动算法最坏情况的输入结构条件。我们提出STAB，一个仅凭自然语言问题规格即可生成暴露算法瓶颈的测试用例的规格驱动流水线。STAB将任务拆分为约束约束下的极大化和对抗结构注入两部分：(i) 约束饱和器提取约束条件，并利用基于规则的饱和与对相关变量的CP-SAT优化，求解出较大的可容许规模赋值；(ii) 对抗情景注入器通过关键词匹配与K近邻（KNN），从精选的情景目录中检索实现层面的对抗构造原理。STAB将问题规格、求解出的边界以及检索到的构造原理编码为结构化生成规格，LLM据此合成Python测试用例生成器。在CodeContests上，STAB将生成测试用例暴露算法瓶颈的比率在开源LLM上平均从50.43%提升到73.45%，在闭源LLM上平均从57.45%提升到71.85%，并且在Python、Java和C++上均取得一致提升。代码发布于https://github.com/suhanmen/STAB。