A Genetic Programming Approach to Automated Software Repair

A Genetic Programming Approach to Automated Software Repair

0. Abstract

유전 프로그래밍(genetic programming)은 유전 프로그래밍은 기존 C 프로그램에서 버그를 수정하기 위한 프로그램 분석 방법과 결합된다. Fitness는 수리(repair)할 버그를 실행하는 negative test case와 프로그램 요구사항을 인코드(encode)한 positive test case를 사용해서 정의된다. 성공적인 수리가 발견되었으면, 구조적으로 다른 알고리듬과 델타 디버깅 방법(delta debugging methods)은 사이즈를 최소화한다. GP 기술에서 다수의 변형은 아래의 것들을 성공하는데 기여한다:

1. 유전 연산자는 negative test case 실행경로에 따른 노드에서 지역화(localized)된다

2. 고수준 문장(high-level statement)은 프로그램 트리에서 싱글 노드처럼 표현된다.

3. 유전 연산자는 프로그램 프로그램의 다른부분에 존재하는 코드를 사용해서, 새로운 코드는 발명될 필요가 없다.

이 논문은 method를 서술하고, 이전연구에서 6만줄이 넘는 코드의 11개의 버그를 수정하는것에 관한 리뷰를 할것이다. 새로운 버그 수리법에 관해 서술하고, 알고리즘 진화 구성 요소의 효율성과 성능에 관한 실험에 대해 서술할것이다.

1. Introduction

다수의 성공적인 유전 프로그래밍(Genetic Programming)에도 불구하고 컴퓨터 프로그래머를 주로 손으로 개발하거나 유지, 수리를 하는 인간 프로그래머를 대체하진 못했다. 본 논문에서는, 어떻게 GP가 이전의 C 프로그램에서 버그를 수정하는 프로그램 분석 방법과 결합되는지에 대해 서술할 것이다. 우리는 C소스코드에 접근해서, 결함이 수리가되는것을 실행하는 negative test case와 프로그램의 행동에 요구되는것이 encode된 다수의 positive test case를 추정할것이다. input은 직접 넣으며, 수정된 버전의 GP는 positive test case를 통과하면서 negative test case를 실패하는것을 방지하는 후보 수리(candidate repair)를 진화시킨다. 그런 다음 구조적 차이 및 델타 디버깅 기술을 사용하여 복구를 최소화하고 코드 팽창을 완화합니다. 이 프로그램은 AST(Abstract syntax tree)로 표현되어져 있으며, 프로그램의 구조