마이크로소프트 준 플레이어 오류와 자동수정하는 방법에 대해 알아보자

 마이크로소프트 준 미디어 플레이어(Microsoft Zune media players) 오류와 자동수정하는 방법에 대해 알아보자.

2008년 12월31일에 마이크로소프트 준 미디어 플레이어에서 오류가 발생했다.

그 이유는 아래의 코드에 문제가 있었기 때문이다.

void zunebug(int days) {
	int year = 1980;
	while (days > 365)  {
		if (days > 366)	{
			days -= 366;
			year += 1;
			}
			else {
			}
		}
		else {
			eays -= 365;
			year += 1;
		}
	}
	printf("current year is %d\n", year);
}

 이 예제의 목적은, negative test case는 무한루프가 발생하는 inputs 366(1980년)과 10593(2008년)으로 구성되어있고, positive test case는 input 1000, 2000, 3000, 4000, 5000이고 이것들은 각각 옳바른 output으로 1982년, 1985년, 1988년, 1990년, 1993년이다.

그 다음 변수 V에 대해 알아보자. V는 원래 프로그램과 동일하게 초기화된다.

 Generation 1에서는, 2개의 mutate V가 동작한다: 조건문 "if (days > 366) { days -= 366; year +=1;}"는 원래 코드의 6번과 7번 라인 사이에 삽입된다; 그리고 "days -= 366"은 10번과 11번 라인 사이에 문장이 삽입된다.

첫 번째 삽입에는 if라는 전체 하위 트리뿐 아니라 전체 하위 트리가 포함됩니다. 이렇게하면 밑에 코드들이 생성된다.

변형된 프로그램은 negative test case 366(1980년) 와 하나의 positive test case(1000)은 패스된다.

 V는 2, 3, 4, 5세대가 변하지 않고 살아남지만, 6세대에선 아래의 동작에 의해 muatated 된다:

6~10번 라인은 삭제되고, "days -= 366"은 13-14번 라인 사이에 삽입된다. 프로그램의 결과는 아래그림처럼 된다.

V는 모든 test case를 통과하고, 초기 복구로 V는 검색이 종료된다.

 최적화 단계는 불필요한 변경을 버리기 위해 호출된다. 원본 프로그램과 세개의 키가 변경된것을 비교해보았다(원본 프로그램의 라인넘버를 사용해서 비교했다): c1 = "days -= 366" 6번라인에서 제거된다.;

c2 = "days -= 366" 9번과 10번라인 사이에 삽입된다; c3 = "days -= 366" 10번과 11번 라인 사이에 삽입된다. 

 이렇게 생성된 최종 repair는 아래의 그림과 같다. 이것은 검색이 생성할수 있는 많은 repair중 하나이다.

 Figure 1은 하나의 GP 시도에서 시간 경과에 따른 population의 평균 적합성(average fitness)이 어떻게 변하는지를 보여줍니다. 프로그램이 실행되었을때, 5개의 positive test case(각각 weight 는 1)와 2개의 negative test case(각각 weight는 10)를 사용한다. 그림1은 마찬가지로 1세대에서 시작하는 primary repair V의 적합성 궤도(fitness trajectory)를 보여준다. V는 원본 프로그램이고, primary repair가 발견된 7세대까지 계속 진화된다.

3.2 Other Repairs

 우리는 모든 경우에 수리를 생성하는 Zune 버그 외에 10 개의 프로그램에서이 방법을 테스트했습니다.

이 결과를 테이블1에 요약해놓았다;  이 그림의 일부는 [23]번 레퍼런스에서 재생성되었다.

그 결과 GP는 C프로그램 제품의 다양하게 문서화된 버그에 대한 수리를 자동으로 발견 할 수 있는것을 보여준다. 그 결과 흥미로운 질문들이 많이 떠올랐다; 어떻게 수리는 GP로부터 탐색되는지, Test case selection, 더 큰 문제에 대한 확장성(scalability), repair quality. 다음 소제목에서 처음 문제의 3개를 다루고 이후 Section 5에서 repair quality에 관한 질문을 다룰것이다.

3.3 The Role of Crossover

 Crossover는 GP의 중요한 검색 연산자로, 다른 individual의 부분 솔루션을 재결합하여 새로운 individual을 만든다. Section 2.3에서 설명한 원래의 구현은 individual이 항상 원래 부모 프로그램으로 돌아 가기 때문에 크로스 오버의 잠재적인 힘을 이용하지 않습니다. 테이블 1에선 input은 2개의 individual로, 각 개체에서 랜덤 위치(i.e., statement)를 선택하고, 해당 내용은 바꾼 다음, 다음 두 가지의 genotypes들을 리턴하는 기존 GP crossover operator와 현재 구현한 데이터를 비교한다. 데이타가 결정적인것이 아니긴 하지만, 두개의 구현(implementation)은 비교할만한 것처럼 보인다. 이 결과의 잠재적인 설명은 우리가 사용하는 버전에 관계없이 crossover가 문제를 검색(search)하는데 충분히 기여를 못한다는 것이다. 이 질문에 대해서는 Section 3.5에서 더 알아볼 것이다.

3.4 Varying the Number of Test Cases

 테이블1에서의 결과는 일반적으로 fitness function에서 6개의 개별값으로 제한하는 6가지 test case를 포함한다. 이것은 GP에 비교적 거친 신호를 제공하기 때문에 진화되는(evolved) repair의 복잡성을 제한시킬수도 있다. 또한, 프로그램은 소수의 test case에서 잡을수있는것보다 더 중요한 기능을 가질수도 있다.  일반적으로 프로그램은 test case는 너무 많고, test case selection과 time-aware test suit prioritization은 21번 레퍼런스처럼 능동적인 연구 영역 이다. 

 이번 섹션에서는 더 많은 test case가 사용되었을 때의 GP 성능이 어떤지에 대해 알아볼 것이다.

그림2는 70개의 다른 시도의 결과를 평균적으로 나타낸 것이다. fitness function과 24개의 test case를 사용했다: 20개의 positive test case와 4개의 negative test case. error bar는 하나의 표준편차로 표현하였다.

 이상적으로 test case는 독립적이다. 이 경우에는 원래 5개(1000, 2000, 3000, 4000, 5000)를 선택하고 다음을 추가하여 선택했습니다. 하나의 임의의 negative number(-100); 하나의 negative 숫자가 긍정적이였다면 프로그램은 멈출것이다(-366). 하나의 극도로 큰 숫자(100000000); 윤년(leap year)근처의 다수의 임의의 숫자를 선택하고 이런 버그를 사용하는 날짜 주변의 숫자를 찾는다. 4개의 negative test case는 다른 윤년: 1980(i.e., 366), 1984, 2012년과 마찬가지로 원본의 버그(모든 Zunes는 12월에 버그가 발생한다)를 포함하고 있다.

 놀랍지않게도, 초기 세대(generation)는 높은 분산(high variance)이 있는 적합성 값을 가지며 이후 세대에서는 분산이 감소합니다. 원본 프로그램은 positive test case를 통과하지만 negative test case는 실패합니다. 왜냐하면 fitness가 20이기 때문이다. 모든 세대에 걸처, 평균 적합도(average fitness)는 기준치가 20아래고, 다수의 individual은 원본 프로그램(original program)보다 성능이 안좋다. 따라서, primary repair는 첫번째 fitness를 잃고 회복하는 global optimum을 알게되었다. 

 직관적으로, 추가 test case는 검색 공간(search space)을 지나치게 제한하여 성공률을 낮출 수 있다. 그러나, 이 예제에서는 반대이다. 7개의 테스트케이스를 사용하여, 평균 성공 비율(success rate)는 72%였고, 24개의 test case를 사용하면 75%의 성공 비율이 나왔다. 그러나, 추가적인 test case는 알고리즘의 총 실행시간을 극적으로 증가시켰다: 7개의 test case는 primary repair를 사용한 평균 시간은 56.1초였고, 24개의 test case는 641.0초가 걸렸다. 모든 적합성 평가(fitness evaluation)에는 잠재적으로 모든 test case를 실행하는것이 포함된다. 따라서, 일반적으로, test case가 적은 fitness function을 선호한다.

3.5 Genetic operator

우리의 구현의 몇가지 비정상적인 특징들이 있다. 이 섹션에서는 여러 작업자의 상대적 기여도를 연구하고 수리를 수행하는 데 필요한 유전적 변화(genetic changes)의 수를 연구한다. Table 2는 프로그램의 대표 샘플(representative sample)을 위한 다양한 GP 검색 방법의 결과를 평균 20회 이상 테스트한 결과이다. 

 두번째 열(column)은 컴파일하는데 실패한 특정 프로그램 변형의 비율을 나타낸것이다. 우리는 memoize 결과를 이미 실패된 프로그램을 리컴파일링하는것을 방지하는것처럼 나타내었다. 그래서 숫자들이 낮게 보인다.

 나머지 열들은 유전 연산자(genetic operator)의 적합 평가(fitness evaluation)의 숫자와 repair 성공 횟수 데이터를 나타낸다. 유전 연산자(genetic operator) 적합 평가(fitness evaluation)의 평균 숫자는 2.19(3, 4, 5, 7행의 합) 2.19이고, 성공적인 repair를 만드는 연산자의 평균 숫자는(8, 9, 10, 12 행의 합) 4.63 이다. population(40)에서 모든 individual을 합산하고 3.6세대 (평균 13개) 이내에 평균적으로 수리가 발견되었다는 것을 고려하면, 평균적으로 검색은 667건의 유전적 조작으로 primary repair를 발견해야 한다. individual operation을 고려할 때,명확한 패턴(clear pattern)을 식별하고 다른 연산자의 상대적 중요성에 대한 명확한 결론을 내리기가 어렵다. 예를 들어, 데이타는 Delete 연산자가 최고로 효과적이라는것을 제안한다. 하지만, 이것은 평균은 indent가 한가지 예로 왜곡된것을 알 수 있다. 종합해서, 그러나, 우리는 GP가 놀랍게도 작은 수의 서치에 보통 성공적인 repair를 할수있다는것을 결론지었다. 이것은 버그를 수리 할 때 영리함의 대부분이 문제 표현, 적합성 함수 및 최소화 단계에서 발생한다고 제안한다. 그리고 우리가 다음에 다루는보다 복잡한 문제까지 접근법이 얼마나 잘 확장 될 것인가에 대한 질문을 제기합니다. 

3.6 GP Performance and Scalability

먼저 알고리즘의 여러 부분의 상대적 실행 시간을 고려한다. 이 실험은 쿼드코어 3 GHZ 머신에서 실행되었다; 몇가지 예외를 제외하고는 프로세스가 CPU 바운드였다. GP 프로토타입은 싱글 스레드로 작동되고, 한번에 하나의 적합성 평가(fitness evaluation)만 수행되며 적합성 평가중에는 모든 test case가 동시에 실행된다. 

평균적으로, 크로스 오버 작업을 실행하기 위해 내부 표현을 조작하는 데 5%±7%의 시간이 소요되었습니다. 시간의 3% ± 3%가 mutation 작업하는데 소요됬다; 시간의 10% ± 14%는 AST를 memoizeing하고 보기좋게 표현하는 fitness function을 계산하는데에 사용되었다. 시간의 22% ± 18% 는 positive test case를 실행하는데 소비되었고, 시간의 33% ± 18%는 negative test case를 실행하는데 소비되었고, 시간의 27% ± 13%는 gcc를 호출하는데 소비되었다. ±는 하나의 표준 편차를 의미한다: 내부 표현을 다루는데 소비한 시간은 보통 노이즈고, 보기좋게 표현하는것, 컴파일과 test case를 평가하는것은 지배적인 시간 비용으로 나타났다. 평균 실행은 총합에서 190초가 걸렸다. 

 이 방법의 실행가능성을 평가하기위해, 알고리즘이 문제 크기와 어떻게 비례 하는지를 알아야하며 해결해야 할 문제의 예상 크기를 알아야합니다.

 그림3, 첫번째 복구까지 fitness evaluation의 평균으로 측정된 검색시간 대비 가중치 경로 길이(weighted path length)를 표시한다. 로그 - 로그 스케일에서, 관계는 기울기 1.26 (90 % 신뢰도 : [0.90, 1.63])과 대략 선형 관계입니다. 우리는 강력한 결론을 도출 할만한 충분한 데이터가 없지만, 검색 시간은 지수 법칙 y = axb 형식의 b는 최적 곡선 (1.26)의 기울기이고 b = 1은 검색 시간이 선형 적으로 증가했음을 나타냅니다. 이것은 유망하다, 이것은 검색 시간이 가중치가있는 실행 경로의 작은 다항식으로 증가하고 지수가 아니라는 것을 나타 내기 때문에 바람직합니다. 

 두번째 질문은 버그의 사이즈 분포와 관련되어있다. 짧게, GP가 수리를 예상하는 버그의 실행경로의 예상 길이는 얼마인지? 이 질문에 대한 확실한 데이터는 없지만, 2004년 Van Belle는 거대한 오픈소스 저장소에 체크인된 size 분포의 revision이 문서화했고,  power law distribution과 닮았다는것을 확인했다. 그는 자신의 데이터에 가장 적합한 분포를 정확하게 결론 지을 수 없었지만 trend는 큰 것보다 많은 작은 변화가 있음을 보여주었습니다. 이것은 미래 연구의 중요한 영역이지만, 대부분의 버그 복구가 단일 기능으로 국한된다는 사실이 밝혀지면 GP 접근법의 실용성에 대해 훨씬 더 낙관적인 시각을 가질 수 있습니다

4. Related Work

우리가 아는건, GP는 기존의 소프트웨어를 발전시키는데 이전에 사용되지 않았다. Arcuri는 GP를 사용해서 소프트웨어의 버그를 수리하는 아이디어를 제안했고, 버블 정렬 알고리즘(bubble sort algorithm)의 예제의 코드를 손으로 써서 아이디어를 설명했다. 그러나 우리의 실험은 진짜 버그가있는 실제 프로그램의 결과를 처음으로보고하는 것으로 보입니다.