문서요약 - 커버링 어레이 소개 by NIST

제목: 커버링 어레이 소개(An Introduction to Covering Arrays)

저자: NIST(the National Institute of Standards and Technology), 미국

문서유형: 웹 문서, 2008년

출처: http://math.nist.gov/coveringarrays/coveringarray.html

 

소프트웨어 테스팅에서 일정 수준의 테스트 커버리지를 유지하면서 테스트 케이스의 수를 줄이는데 활용할 수 있는 커버링 어레이의 개념을 소개한 자료

---

동기(Motivation)

• 소프트웨어가 종종 많은 구성(configurations)를 가지고 있는데 이들 각각에 오류가 있을 수도 있음. 소프트웨어 테스팅은 이러한 구성 어디에서도 실제 에러가 일어나지 않음을 보장하려는 노력
• 이런 목적을 달성할 수 있는 한 가지 방법은 모든 가능한 구성(all possible configurations)을 시뮬레이션 하여 에러가 발생하지 않음을 체크하는 것이지만, 이 경우 체크해야 할 구성이 너무 많기 때문에 비현실적임
• 소프트웨어 프로그램의 모든 가능한 구성을 테스팅 하지 않고 훨씬 작은 수의 신중하게 선정된 구성들만으로도 모든 프로그램 동작의 적당한 시뮬레이션이 달성 가능. 커버링 어레이(A covering array)는 이런 목적에 사용될 수 있는 수학적 객체이다.

커버링 어레이 정의

• ‘커버리지(coverage)’라는 개념은 어떤 샘플 구성들의 집합(a set of sample configurations)이 모든 가능한 구성들의 집합(the set of all configurations)을 얼마나 잘 커버하는지를 정량화하는데 사용됨
• ‘풀 커버리지(full coverage)’는 모든 가능한 구성들이 선택된 것을 의미하고, ‘노 커버리지(no coverage)’는 어떤 것도 선택되지 않았음을 의미. 중간 수준의 커버리지(Intermediate levels of coverage)는 패러미터 t를 통해 정의됨
• 구성들의 총 수(the total number of configurations)를 표현하는데 있어서 두 개의 추가적인 패러미터가 존재함: k는 어떤 한 구성이 명세할 필요가 있는 변수들의 수(the number of variables)이고, v는 k 변수 각각이 가질 수 있는 가능한 값들의 수(the number of possible values)이다. 실제로는 각 변수가 가지는 값들의 수가 다를 수 있지만 여기서는 단순화를 위해 동종의 경우만 고려함(즉, 모든 k가 동일한 v를 가짐)
• t = k이면 풀 커버리지가 달성되고, t = 0이면 노 커버리지가 됨. t는 때때로 커버링 어레이의 강도(strength)라고도 지칭됨

커버링 어레이 예

• 4개의 이진 변수(binary variables)를 가지는 간단한 프로그램(즉, k=4이고 v=2)에서 풀 커버리지(t=4)를 위해 아래와 같은 구성들을 테스트함(16개의 행을 가진 어레이 테이블)

• 위 구성 목록을 살펴보면 네 개의 열 중 어떤 것이든 두 개가 선정되면 모든 가능한 값의 쌍(all possible pairs of values)이 나타나는 것을 알 수 있음. 구체적으로 말하자면 1열과 2열만이 선택된 경우(또는 1열과 3열만이 선택된 경우 등등) 가능한 값의 쌍 모두가(즉, ‘00’, ‘01’, ‘10’, ‘11’) 테이블의 행에 등장한다.
• 위의 테이블처럼 모든 구성을 완전히 커버하지 않고도 이런 속성(property)을 가지는 다른 구성 테이블도 존재함. 예를 들면, 아래의 5개의 구성(행)을 가진 테이블에서 어떤 두 개 열이 쌍으로 선택되든지 간에 이진 입력 값의 모든 가능한 구성이 행에 등장함
• 이런 속성을 ‘2-커버리지’라 부르며 t=2일 경우에 상응함. 아래 테이블이 ‘2-커버리지 속성’을 충족시키므로 이를 커버링 어레이라고 부름

• 위의 설명을 임의적 t로 일반화시킬 수 있음(t-way 커버리지 정의). 어레이의 k개 열로부터 선택된 t개 열에 대해 모든 가능한 v^t 터플(tuples)이 어레이의 행에 등장함

NOTE: 커버링 어레이는 반드시 t-covering 속성을 충족시켜야 함(즉, k 열로부터 어떤 t 열이 선택되었을 때 가능한 t-터플의 모든 v^t가 반드시 행에 등장해야 함). 예를 들어, 아래 어레이는 t=2, v=2, k=4의 커버링 어레이가 아니다. 두 번째 열과 네 번째 열을 보면 2-tuple(1,0)이 행에 등장하지 않는 것을 알 수 있음

최적성(Optimality)

• 최적의 커버링 어레이(optimal covering arrays)를 찾는 노력은 “고정된 t, v, k 값에 대해 가장 작은 커버링 어레이의 크기가 얼마인가?”의 문제임
• k가 열의 수(the number of columns)를 결정하므로 실제 이 질문은 t-covering 속성을 충족시키면서 어레이가 가질 수 있는 가장 작은 행의 수(the smallest number of rows)가 얼마인지를 묻는 것이다.
• 앞에 나온 5개 행을 가진 커버링 어레이는 실제로 최적의 어레이임. t=2이고 v=2인 이 특별한 경우를 제외하고 최적 커버링 어레이 크기가 얼마인지 일반적으로 알려지지 않음. 예를 들어, t=3, v=2, k=4인 경우의 아래 커버링 어레이가 9개 행을 가지지만 실제는 8개로 충분함

응용(Applications)

• 커버링 어레이가 소프트웨어 테스팅 작업에 주로 응용됨. 어떤 소프트웨어 패키지이든 두 개의 패러미터(입력의 수, 각 입력이 가질 수 있는 값의 수)를 당연히 가짐
• 단순화를 위해 여기서는 모든 입력이 동일한 수의 값들을 가지는 경우만 고려하며, 첫 패러미터가 k에 상응하고 두 번째는 v에 상응함. 세 번째 패러미터 t는 직접 선택할 필요가 있으며 이것이 입력 공간(the input space)의 커버리지 수준을 결정함
• 이상적으로 t=k로 할 수 있겠지만 대개 너무 많은 구성을 테스트 해야 하는 결과를 낳음. 실증적 연구에 따르면 대개의 소프트웨어 패키지에서 에러를 찾는데 t가 6을 초과할 필요가 없다고 함
• 일단 패러미터들이 고정되면 커버링 어레이가 생성될 수 있음. 이 어레이의 행은 소프트웨어 패키지 상에서 수행되어야 할 필요가 있는 테스트에 상응함(따라서 이것을 프로그램이 사용할 수 있는 형태로 전환할 필요가 있음)
• 예를 들어, 네트워크화된 인쇄 시스템을 테스트 시 그 입력으로 ‘운영체제’, ‘웹브라우저’, ‘네트워크 타입’, ‘시각(the time of day)’이 있을 수 있음. 각 입력이 두 개 값만을 취한다면 앞의 5개 행을 가진 커버링 어레이를 아래와 같은 테스트 스위트로 전환 가능