王博-AiDD2024北京站-大语言模型时代的变异分析

大语言模型时代的变异分析 王博北京交通大学 演讲嘉宾 王博 北京交通大学计算机与信息技术学院讲师、硕士生导师，CCF专业会员、CCF系统软件专委执行委员、CCF开源发展委员会执行委员。分别于北京大学、中国科学技术大学和中南大学获得博士、硕士和学士学位。研究兴趣为软件测试与调试，已在ASE、ISSTA、TOSEM、软件学报等发表多篇论文。担任ASE、FSE、ICST、Internetware等软件工程重要会议PC，担任TSE、TOSEM、TDSC、EMSE、JSS、ASEJ、IET Software、JSME、软件学报等多个期刊审稿人。获得ISSTA 2017杰出论文奖，全国大学生系统能力大赛优秀指导教师和北京市高校优质教案。 1.背景2.痛点3.解决思路4.具体实现5.总结与展望 目录 背景PART 01 软件正确性至关重要 •软件缺陷已经导致很多灾难性后果•保障软件的正确性十分重要•当我们说软件是正确的：程序的行为符合正确性规约(specification) 保障正确性的方法 intfoo(inta,intb) {returna + b;} 1.形式化方法 Formal Method: (a >= 0 && b <=0) ||(a <= 0 && b >=0) ||(a >= 0 && b >= 0 && a + b >= 0) ||(a <= 0 && b <= 0 && a + b <= 0) 2.软件测试 Testing:foo(0, 1) = 1;foo(INT_MAX, 1) = ERROR;foo(INT_MAX-1, 1) = INT_MAX ;foo(INT_MAX, INT_MIN) =-1; 测试是不完备的！ 测试质量直接影响到软件质量 •核心问题是：我们如何度量测试的好坏？ •测试质量达标的系统才有一定的可信度•测试集约减•测试排序 •我们朴素的愿望：希望测试能发现真实缺陷 •但是在发现之前，真实的缺陷对于我们是未知的•“测试可以非常有效地显示bug存在，但却无法证明bug的不存在” •我们可以使用一些指标，间接地度量测试质量 •测试覆盖 •变异测试：用人造缺陷发现率估计真实缺陷发现率 变异测试概览 每个变异体是原始程序的小型文法改动 变异测试概览 变异测试在软件测试中的发展 •变异测试自1971年被DeMillo和Hamlet提出以来，是软件测试中的重要方法 •修改位置：从一阶变异(first order)到高阶(higher-order)，支持修改多处 •在单元测试中： •面向高级语言源码：C、Java、Python、JS…•面向中间表示：Java bytecode, LLVM-IR•从桌面应用到Android、MPI、智能合约程序等 •从单元测试扩展到其他测试阶段： •集成测试•设计阶段（例如在基于模型的软件开发过程中针对设计FSM的变异） 从变异测试到变异分析 •基于变异的缺陷自动定位（mutation-based fault localization）是变异测试的衍生技术 •缺陷自动定位：给定测试集（至少有一个未通过测试）和程序，返回程序中的语句出错可疑度分数。 •传统定位方法：基于测试覆盖信息对语句排序（spectrum-based fault localization） 从变异测试到变异分析 工具和标准程序集 •变异测试 •C语言: •Proteum(108 mutation operators)•Milu(Higher-order)•WinMut(IR-based) •Java语言:•MuJava•Major [By Rene Just]•JavaLanch(IR-based) [ByZeller]•PITest(Commercial tool) •标准测试集 •Software-artifact Infrastructure Repository (somehowoutdated)•Defects4J (Java)•ManyBugs(C) 痛点PART 02 挑战1：生成高质量的变异 •现有方法生成变异主要有两类 •基于规则的传统方法•PIT、Major、JavaLanche、AccMut•生成变异过于简单，不考虑代码上下文，文本上与真实bug差别很大 •基于学习的方法 •训练模型，学习真实Bug的代码变换模式•DeepMutation[ICSME-19]、LEAM [ASE-22]•训练数据集有限，生成大量错误变异 挑战2：可扩展性较低 •阻碍变异分析走向工业实践的是可扩展性（Scalability）较低 •假如有M个变异，N个测试 •变异分析的计算复杂度：O(M) + O(M×N)•𝑇!"!#$=∑%∈'𝑡())*,%+∑%∈'𝑡,"%-.$),%+∑%∈'∑/∈0𝑡!)(!,%,/ •在实际规模的程序中，M会很大 挑战2：可扩展性较低 •以变异测试为例，如下一行源码产生二十多个变异 挑战3：等价变异体 •等价变异体：变异后的程序与原始程序在功能上完全相同，即它们对所有可能的输入产生相同的输出。 •等价变异的危害： •增加测试成本 •影响变异分数计算的精确度 •判断等价变异体是不可判定问题：不存在一个自动算法完美解决 解决思路PART 03 面向挑战1：大模型时代的变异生成 •大模型在代码理解和代码变换上出色的能力，为提升变异分析提供了新的方向 •大模型在程序修复上取得了显著的效果•buggy-> correct •问题：大模型在变异分析上能否取得良好效果？ 面向挑战2：基于共享计算的加速 •变异分析执行过程中需要反复执行测试•其中存在大量冗余计算•我们可以尝试共享冗余计算进行加速 具体实现PART 04 基于大模型的变异生成 •大模型能否生成更接近真实bug的变异？ •有效性： •语法正确•变异有“揭错”能力 •自然性： •符合一般的编程规范•编码模式和习惯与真实代码一致 •变异足够多样，且有足够数量的变异被杀死 •避免生成等价变异•生成的有足够比例的变异能被测试检测•语义尽可能丰富 基于大模型的变异生成：模型设置 •选用了4个模型•包括开源模型和商用闭源模型（实验还在扩展中） •GPT-3.5-Turbo和GPT-4-Turbo通过购买APIToken•开源模型通过租用2台双卡3090服务器 基于大模型的变异生成：数据集 •面向Java语言（Java是拥有最多Baseline的语言）•Defects4Jv1.20上395个真实的缺陷•ConDefects上的45个没有数据泄露风险的缺陷 基于大模型的变异生成：对比方法 •我们的对比方法涵盖了所有的Java最新变异生成方法 •基于规则•PIT [ISSTA-16]•Major [ISSTA-11] •基于学习•LEAM [ASE-22] •基于小规模的预训练模型•muBert[ICST-22] 基于大模型的变异生成：Prompt设计 基于大模型的变异生成：评估生成代价 •代价指标： •时间代价（秒）•平均生成1k个变异的代价 基于大模型的变异生成：评估可用性 •机器学习方法不可避免地生成无用变异 •可用性指标： •编译通过率•无效变异率•等价变异率（按95%置信度和5%误差幅度采样） 基于大模型的变异生成：评估变换多样性 •变换多样性指标： •变异是否引入新的AST节点类型(例如，a+b-> a–b没有引入新类型，但a+b-> foo(a,b)引入了方法调用) 基于大模型的变异生成：评估变换多样性 •变换多样性指标： •删除变异所占比例•引入新的AST节点类型分布 基于大模型的变异生成：与真实缺陷的语法相似度 •指标： •变异与真实缺陷的BLEU分数•变异与真实缺陷的AST编辑距离 基于大模型的变异生成：与真实缺陷的语法相似度 基于大模型的变异生成：与真实缺陷的行为相似度 •行为相似度指标： •真实缺陷检测率•与真实缺陷耦合率•Ochiai系数（语义相似度指标） 基于大模型的变异生成：不同Prompt的影响 •P1：默认prompt•P2：P1移除few-shotexample•P3：P2移除方法Context•P4：P1 +添加方法对应的测试 基于大模型的变异生成：不同模型的表现 基于大模型的变异生成：导致不可编译变异的原因 基于大模型的变异生成：不同上下文长度 基于大模型的变异生成：不同的Few-shot Example 基于大模型的变异生成：生成固定数量的变异 •如果要求生成同样数量的变异•我们将所有工具生成的变异数限制为最少的一个（muBert） 基于共享计算的加速：大模型时代变异分析效率依然不高Each mutant has a small 基于共享计算的加速：标准变异分析中的冗余计算 基于共享计算的加速：分支流计算 基于共享计算的加速：AccMut [ISSTA-17] •Equivalence Modulo States:Two mutants areequivalent modulo the current stateifexecuting them leads to the same state from the current state[Wang et al., 2017]The label below is the 基于共享计算的加速：AccMut依然存在大量冗余计算 1.AccMut is unable to merge more mutants 基于共享计算的加速：WinMut[ASE-21] 基于共享计算的加速：WinMut的实现 •在LLVM-IR基础上实现，即它是在中间表示级别实施变异分析•变异算子涵盖当前所有中间表示级别分析的工具•程序员透明的、内存上的IO库 基于共享计算的加速：WinMut的实验对象程序 基于共享计算的加速：WinMut的实验效果 WinMutis faster than AccMut with angeometric average speed up of5.57X. WinMutuses7.3%fewer processes thanAccMut. 基于共享计算的加速：下一步的WinMut-Turbo •当前方法都是在尝试优化Fork之前的计算•我们通过程序分析，可以优化Fork之后的计算•如果我们确定Fork之后的子进程一定会影响测试结果，就及时终止•WinMut-Turbo：在WinMut基础上，进一步带来30%的加速 总结和展望PART 05 基于大模型的变异生成 •大模型在生成变异上有独特的优势 •最大的优势在于生成行为上接近真实bug的变异 •目前仍有很大提升空间 •使用prompt-engineering•使用LLM微调•探索多智能体在变异生成的应用 面向大模型的复杂变异加速 •虽然相比于当前最新方法（SSE），已经累计加速50x •当前的加速方法有一定局限性•仅能优化限定代码区间的简单变异•面对大模型生成的复杂变异，如何进一步优化是未来工作重点 THANKS