어느새 마지막 포스팅에서 한달 가까이 지났군요. 지난 마지막 포스팅때, Orthogonal Array (직교 배열) 에 대해서 알아보다가
멈췄네요 ㅎㅎ

저는 개인적으로는 수학을 잘 하지 못해서 그런지, 직교 배열은 관련 자료를 찾기도 쉽지가 않더군요. 사실 지난 한 달동안 직교 배열에 대해서 많이 찾아봤는데요, 워낙 여기저기 찾아보고 정리를 잘 못해서 출처도 딱히 적기가 어렵네요 -_-;; 어쨌든 근 한 달만의 포스팅이 허접하지 않게 적어보겠습니다 ^^;

직교 배열의 개론(?) 부터 말씀 드리면.
직교 배열은 Latin Square라는 수학적 행렬을 기반으로 합니다. Latin Square란, 정사각형 (row와 column의 갯수가 같은) 행렬 중, 특정 row나 column에 중복된 요소가 존재하지 않으면서 모든 요소가 한번씩 나타나는 행렬을 말합니다. 그림으로 설명하는 게 낫겠죠 ^^; 요소가 3인 (n=3) Latin Square는 아래와 같이 2개를 예로 들 수 있습니다.



위와 같은 모양을 하게 됩니다. M1, M2 두 행렬의 어느 row 혹은 column에도 요소가 중복되지 않습니다.

그럼 이제 위의 두 행렬을 합쳐보겠습니다. M1과 M2의 각 행과 열에 매치되는 요소들을 합합니다. 그러면


처럼 되겠죠. 이 행렬 L의 특징은, 행렬 내의 어떤 요소도 중복된 짝(pair)이 없다는 것입니다. 이런 경우를 우리는
두 행렬이 '직교한다', 'Mutual Orthogonal Latin Square(MOLS)'라고 합니다.
 2개의 배열을 합쳤고, 어떤 요소도 중복되지 않았다는 것은? 그렇죠,  pair-wise입니다. 단 여기서의 pair-wise는 커버리지를 
만족하는 최소의 pair-wise는 아닙니다. 단순히 수학적인 pair-wise (서로소) 입니다. 

요소가 3개인 Latin Square는 실제로 위의 2개 보다 더 많습니다. 정확히 계산하는 법은 모르곘으나, 얼추 해봐도 3개는 넘는군요.
그렇지만, Orthogonal하며, 요소가 3개인 Latin Square는 위의 행렬조합밖에 없습니다. 

그 이유는... (사실 여기부터는 찾아본 자료에 이러이러 하다고 하니까 그런 줄 알고 있는 내용입니다. 수학적으로 증명할 줄 모릅니다 -_-;;;)

수학적으로 orthogonal한 행렬은 요소가 n개 (단 여기서 n은 소수 (prime number) 혹은 소수의 제곱값 이어야 함) 일 때 
MOLS(n) = n - 1을 만족한다고 합니다. 즉 요소가 3이기 때문에 MOLS인 Latin Square는 3 - 1개 인 것입니다. 

자, 다음은 요소 갯수가 더 많은 latin square를 만드는 법을 알아보겠습니다. (사실 이거 찾는데 시간이 엄청 오래 걸렸습니다. 다 tool돌리면 나온다고 그런 설명만 있어서... 근데 또 알고 보니 별거 아니라는 -_-_

요소가 5개인 orthogonal array를 만들어보겠습니다. 


쉽죠? -_-;; 딱 보시면 규칙을 아실껍니다. 값이 1인 요소를 기준으로 보면, 1의 row내 index가 row가 내려갈수록 0 --> 4 --> 3--> 2--> 1로 바뀌는 것을 알 수 있습니다. 2, 3, 4, 5 모두 마찬가지 입니다. 

다음 행렬 보시겠습니다. 

이번에도 값이 1인 요소를 기준으로 살펴보면, 0 --> 3 --> 1 --> 4 --> 2 이렇게 2씩 줄어드는 것을 알 수 있습니다. (index 값이 0보다 작아지면 반대쪽 끝으로 간다고 (look around) 생각하세요)
아까는 1씩 줄어들고, 이번엔 2씩 줄어듭니다. 3번째는? 4번째는? 3씩, 4씩 줄이면 될 듯 합니다. 

역시 됩니다. 이 행렬 중 2개를 선택해서 합쳐보면, 그 조합된 값은 모두 pair-wise하게 됩니다. 

참고로, 5 역시 소수이기에 위의 방법이 가능합니다. 8이나 10개의 요소를 가진 행렬을 위의 방법으로 만들어보시면
Latin Square조차 성립할 수 없다는 것을 알게 되실겁니다. (한 column에 중복된 값이 나오게 됩니다). 다른 방법을 통해 Orthogonal array를 찾으셔야 합니다.
또 덧붙이면, 2보다 큰 요소를 갖는다면 모두 MOLS를 만들 수 있으나, '6'은 예외입니다. 6개의 요소를 가진 MOLS는 만들 수 없다는군요. 이는 Eulean Number와 연관이 있다고는 하나 제가 그거에 대해 아는 바가 없습니다. -_-;;

어쨌든 orthogonal Array의 개념은 이 정도로 정리하겠습니다. 다음 포스트는 이 orthogonal array를 어떻게 테스트 케이스에 적용하는 가를 적어보겠습니다. (이번엔 한 달씩이나 걸리진 않아요 ㅎㅎ)

참조 목록
- Foundation of Software Testing:: Chapter 4. Test Generation. Aditya P.Mathur. Purdue University.
- A Practical Strategy for Testing Pair-wise Coverage of Network Interfaces. Allan W.Williams et. al
- An Evaluation of Combination Strategies for Test Case Selection. Mats Grindal et.al

'Software Testing > Knowledge Base' 카테고리의 다른 글

Combinational Analysis #3  (4) 2009.03.05
Combinational Analysis #2  (3) 2009.03.01
Combinational Analysis #1  (0) 2009.02.05
결함 정보는 Test case로 관리해라!!  (1) 2009.01.02
Issue Tracker (Bug Tracker)적용의 어려움  (1) 2009.01.02
Posted by yunseong