171105-NASAC17-程序修复(武汉大学-玄跻峰)

玄跻峰武汉大学基于自动修复的软件质量保证[e-mail].05,2017Harbin,China1•研究背景•问题与挑战•程序修复研究的四个阶段•未来机遇与讨论内容从Bug到Debug2知晓缺陷找到缺陷分析缺陷软件程序中的缺陷消灭缺陷测试用例-Test Case从Bug到Debug3知晓缺陷找到缺陷分析缺陷软件程序中的缺陷消灭缺陷测试用例-Test Case@TestpublicvoidtestFoo(){asserta.parent!=null;…asserta+b==3;}测试用例软件测试、软件调试、程序理解、软件维护、软件分析…从Bug到Debug4知晓缺陷找到缺陷分析缺陷修复缺陷软件程序中的缺陷消灭缺陷测试用例-Test Case5软件遍布各个领域程序修复的现状：人工修复人工编写代码补丁，检验补丁正确性修复程序难人力成本高引入错误多潜在风险大人工程序修复正面临极大挑战程序修复的目的6FredBrooks1999年图灵奖得主修复程序难代码复杂，修复易出错依赖专家级程序员人力成本高时间长成本消耗巨大引入错误多不成熟的补丁引入新错误Mozilla项目的百万行代码显示，超过10%的修复仍遗留错误Apache项目平均每个错误修复超过5天时间，并且人力成本随项目进度激增增加人力投入会使得已经错漏百出的软件项目开发陷入泥潭。——《人月神话》潜在风险大补丁多样性危及后续开发维护开源项目程序员众多，代码风格迥异，补丁多样性导致更易出错人工程序修复正面临极大挑战程序修复的类型7测试用例一系列人工编写的代码能够被自动工具读取用于描述软件行为•自然语言需求驱动的程序修复•形式化规格驱动的程序修复•测试驱动的程序修复测试用例广泛存在，补丁可能自动生成流程：编写代码补丁，执行测试用例，检验补丁正确性测试驱动的程序修复8intgcd(intu, intv) {‐if(u * v == 0)  {+  if(u == 0 || v == 0)  {return(Math.abs(u) + Math.abs(v));... } 输入u输入v预期输出观测输出测试结果0333Pass2^302^292^292^30+2^29Fail…………程序错误示例计算u与v的最大公约数，经典项目ApacheCommonsMath的错误报告Math-238代码补丁带有错误的程序测试用例程序修复方法程序补丁测试驱动的程序修复9带有错误的程序测试用例程序修复方法程序补丁应用场景：测试驱动开发（Test-DrivenDevelopment）持续集成（ContinuousIntegration）回归测试（RegressionTesting）DevOps…GitHub.com10现有方法基于尝试并验证的策略，补丁的检查依赖于多次测试用例执行。算法精度低，时间消耗高，难以用于真实程序难于精准•无指引，盲目搜索•测试用例能力不足•无法修复复杂程序语义基于遗传程序设计的修复方法GenProg等(ICSE’09,TSE’12)难于高效•多次执行测试用例，耗时•测试用例结构复杂，存在冗余……精准和高效的生成代码补丁，以通过测试用例问题和挑战程序修复断代“十年史”11玄跻峰等.自动程序修复方法研究进展.软件学报,27(4),2016.研究历史•早期工作，2008年国际同行提出基于演化计算的自动修复算法•至今10年时间，发展了大量的高水平成果02468101220082009201020112012201320142015论文数量年份会议短文技术报告期刊论文会议长文程序修复断代“十年史”12玄跻峰等.自动程序修复方法研究进展.软件学报,27(4),2016.研究历史•早期工作，2008年国际同行提出基于演化计算的自动修复算法•至今10年时间，发展了大量的高水平成果部分国内学者成果•国防科技大学齐玉华、毛晓光教授课题组(ICSE2014)•北京大学熊英飞、张路教授课题组(ASE2015,ICSE2017)•上海交通大学钟浩教授课题组(ICSE2016)…我们曾给出的粗糙分类•基于搜索的程序修复(ICSE2009,TSE2012)•基于穷举的程序修复(ICST2010,ISSTA2015)•基于约束求解的程序修复(ICSE2013,TSE2017)软件质量保证132008-尝试2013-学习2013-推断2014-校正自动修复研究尝试学习推断校正14‐if(u * v == 0)  {+  if(u == 0 || v == 0)  {return(Math.abs(u) + Math.abs(v));... 输入u输入v预期输出观测输出测试结果0333Pass2^302^292^292^30+2^29Fail…………基于遗传规划的修复，GenProg,byWeimerandLeGoues,ICSE2009,TSE2012.程序转换为抽象语法树执行测试用例查找bug可能的位置，用于指导变异应用遗传规划生成新的语法树重用已有的代码，变换位置和关系，生成新的代码基于遗传规划的程序修复尝试学习推断校正15尝试学习推断校正16尝试学习推断校正17尝试学习推断校正18尝试学习推断校正基于测试的程序修复框架19验证补丁第一条语句第二条语句最末语句SearchbasedpatchgenerationExhaustionbasedpatchgenerationConstraint-solvingbasedpatchgeneration或或20基于遗传规划的修复，GenProg,byWeimerandLeGoues,ICSE2009,TSE2012.程序转换为抽象语法树执行测试用例查找bug可能的位置，用于指导变异应用遗传规划生成新的语法树真实C程序bug实验，印证了GenProg方法的实践效果实践上验证了自动方法行之有效，并且很多后续方法依赖该实验数据集每个8美元，修复105个bug中的55个,byLeGouesetal.,ICSE2012.基于遗传规划的程序修复尝试学习推断校正21修复方法有效性的实证评估Automatic Repair of Real Bugs in Java: A Large‐Scale Experiment on the Defects4J Dataset. Empirical Software Engineering, 2017. 实证结果不佳尝试学习推断校正22•多数方法基于尝试并验证（generate‐and‐validate）的策略，算法精度低，时间消耗高，难以用于真实程序•多数方法局限于修复运算符和数值程序，无法修复面向对象程序程序修复-尝试Object object= null; Object = new Object();Object.foo(); Object object= null; Object.foo(); Object = new Object();尝试学习推断校正软件质量保证232008-尝试2013-学习2013-推断2014-校正自动修复研究24从人工补丁学习自动化代码生成，Par,byKimetal.,ICSE2013.Distinguishedpaperaward,2013程序修复-学习历史驱动的程序修复，byLe,David,LeGoues,SANER2016.从人工学习到自动学习程序修复的精确条件合成，byXiong,Zhang,Yan,Zhang,Han,Huang,Zhang,ICSE2017.终于走到了精确•dependency-basedordering•documentanalysis•predicatemining尝试学习推断校正25DeepFix:通过深度学习修复常见C语言错误,byGuptaetal.AAAI2017程序修复-学习尝试学习推断校正26•向谁学习•高频数据数据趋向程序修复-学习尝试学习推断校正软件质量保证272008-尝试2013-学习2013-推断2014-校正自动修复研究28SemFix:基于语义分析的程序修复,byNguyen，etal.,ICSE2013.基于组件的程序合成程序修复-推断Angelix:通过符号分析的大规模多行程序补丁合成,byQietal.,ICSE2016.基于Angelicforest的推断技术尝试学习推断校正测试驱动的自动程序修复框架29方法从程序执行到代码补丁推断的自动转换主要技术•基于静态程序分析的面向对象语义编码转换，包括收集对象实时状态和特性•基于约束求解的补丁合成，一次求解即可生成补丁，避免多次尝试的时间消耗继承多态封装面向对象的复杂语义程序修复–推断尝试学习推断校正Xuan, et al. Nopol: Automatic Repair of Conditional Statement Bugs in Java Programs. IEEE Trans. Software Engineering, 2017.  30尝试if(true){，不是true值!尝试if(false){，是false值!if(u * v == 0)  {补丁的输出自动的输出推断-动态推测补丁的运行时数值程序修复–推断尝试学习推断校正补丁的输入动态上下文编码-将面向对象语义编码成动态值31对象语义继承多态对象状态空引用运行时值……补丁的输出自动的输出推断-动态推测补丁的运行时数值程序修复–推断尝试学习推断校正•生成一个if ( cond) { … } 中的cond生成一个布尔表达式exp，使得•其中，Cloc,m,n是运行时的收集值的集合32补丁的输出自动的输出推断-动态推测补丁的运行时数值合成补丁补丁的约束求解-将补丁生成转换为约束求解补丁的输入动态上下文编码-将面向对象语义编码成动态值程序修复–推断•实验输出–22个真实的条件bug的数据集•22BugdatasetinGitHub,–修复方法已开源•NopolinGitHub， et al. Nopol: Automatic Repair of Conditional Statement Bugs in Java Programs. IEEE Trans. Software Engineering, 2017.  程序修复–推断尝试学习推断校正现实并不那么美•不成功的例子，源自ApacheCommonsMath•Bug:•人工补丁：•我们的补丁：34尝试学习推断校正还有更多不足•SMT求解器的性能缺陷•不能够处理带有参数的methodcall会导致组合爆炸•存在没有angelicvalue的条件语句35尝试学习推断校正软件质量保证362008-尝试2013-学习2013-推断2014-校正自动修复研究•过拟合补丁(overfittingpatch)–能够通过测试用例，却不与需求相符37程序修复–校正通过测试生成识别过拟合补丁byQi&Reiss,ISSTA2017.识别过拟合补丁更好的测试用例带来更好的程序修复,byYang,etal.FSE2017.利用新测试用例引导补丁生成尝试学习推断校正测试用例的冲突和冗余38intgcd(intu, intv) {... if(u * v == 0)  {return(Math.abs(u) + Math.abs(v));... 5个测试用例带有错误的程序12345测试用例噪声补丁质量差冗余补丁生成慢测试代码行为不一致-降低修复精度过多测试用例-增加修复时间尝试学习推断校正Xuan, et al. B‐Refactoring: Automatic Test Code Refactoring to Improve Dynamic Analysis. Information and Software Technology, 2016.  测试用例约简的