페이퍼요약 - 이벤트 시퀀스를 활용한 효과적인 상호운용성 테스팅 방법 by Kuhn

제목: 이벤트 시퀀스를 활용한 효과적인 상호운용성 테스팅 방법(Efficient Methods for Interoperability Testing Using Event Sequences)

저자: Richard Kuhn 외 4인, 미국

문서유형: 저널 페이퍼(총 4페이지), 2012년

 

이벤트 시퀀스가 특히 중요한 시스템을 효율적으로 테스트하기 위해 시퀀스 커버링 어레이를 사용한 사례를 기술한 자료

---

소프트웨어 테스팅에서 이벤트 시퀀스

• 많은 타입의 소프트웨어에서 이벤트 시퀀스는 중요한 고려사항임. 예를 들면, GUI에서 사용자가 가능한 어떤 이벤트 순서를 선택하든 소프트웨어가 정확하게 동작해야 함(또는 적절한 에러 메시지를 제공해야 함)
• 여러 통신/센서 입력을 받아들여 다수의 통신 링크 및 기타 인터페이스로 출력을 하는 “미션 크리티컬 시스템”에서도 이벤트가 발생하는 순서를 테스트하는 것이 중요함
• 이런 소프트웨어를 테스팅 시 특정 이벤트가 어떤 다른 이벤트에 앞서서 발생했는지 여부가 종종 실패(failure)를 촉발시키는 중요 조건이 됨. 예, 기기 B와 C가 둘 다 이미 연결된 경우에 기기 A를 연결하면 실패가 일어남, A가 시작될 때 B가 이미 연결되어 있지 않으면 실패가 일어남
• 여기서 실패를 야기시킨 이벤트 시퀀스가 반드시 연속적일 필요는 없음. 즉, 타 이벤트가 해당 이벤트 시퀀스 사이에 끼어 있을 수도 있음(인터리빙)
• 이 논문에서 설명된 방법은 이런 성격의 테스팅 문제를 다루기 위해 개발되었으며 조합 방법(combinatorial methods)을 활용함

시퀀스 커버링 어레이(Sequence Covering Array: SCA) 정의

• 시퀀스 커버링 어레이는 집합 n으로부터 취해진 이벤트들 t가 (n > t) 모든 가능한 t-way 순서로 테스트되는 것을 보장한다.
• 시퀀스 커버링 어레이 SCA(N, S, t)를 그 엔트리가 유한 집합 S(s 심볼들로 구성됨)로부터 나온 N x S 매트릭스로 정의. S로부터 나온 심볼들의 모든 t-way 치환(permutation)이 어레이의 최소한 하나의 행에 등장함(즉, 각 행이 s 심볼들의 치환을 나타냄)
• 이 치환에서 t 심볼들이 반드시 인접할 필요는 없음. 즉, 심볼 x1, x2, ..., xt의 모든 t-way 배열에 대해서 정규 표현식 .*x1.*x2.*xt.*가 어레이의 적어도 한 행에 매치한다.

예1: 3-way 이벤트 시퀀스 테스팅

• 제어 시스템과 상호작용하는 특정 기기(devices)들을 사용하는 공장 자동화 시스템의 컴포넌트에서 아래 표에 정의된 이벤트들을 테스트 하고자 함
• 6개 이벤트에 대해 6! = 720개의 가능한 시퀀스가 존재하며, 이 이벤트들이 어떤 순서로 발생되든지 간에 시스템이 정확하고 안전하게 반응해야 함
• 오퍼레이터가 특정 순서로 사용하도록 지침을 받았다 하더라도 실수가 발생할 수 있으며 이로 인해 사용자가 다치거나 오퍼레이션이 손상되어서는 안됨
• 이 컴포넌트의 설정(setup), 연결(connections), 조작(operation)이 모두 수동이기 때문에 각각의 테스트에 상당한 시간이 걸릴 수 있음
• 이 시스템을 최대한 철저히 테스트 하고 싶지만 시간과 비용 제약이 모든 가능한 시퀀스를 테스트 하는 것을 허용하지 않음. 그래서 “모든 3-이벤트 시퀀스(all 3-event sequences)”를 테스트 하기로 함

[시스템 이벤트 예]

• 6개 이벤트 a, b, c, d, e, f로부터 나온 3개 이벤트의 서브셋 중 하나가 {b, d, e}이다.
• 서브셋 {b, d, e}는 6개 치환(permutations)이 가능: [bde], [bed], [dbe], [deb], [ebd], [edb]
• 이 치환들 중 하나인 [dbe] 시퀀스를 커버하는 테스트의 예를 들자면 [adcfbe]나 [adcbef] 같은 것이 있다.
• 아래 표처럼 단지 10개 테스트만 가지고 ‘모든 3-이벤트 시퀀스’를 테스트 할 수 있음. 즉, a..f 로부터 취해진 3개 이벤트 시퀀스가 어떤 순서로 배열되었든지 간에 아래 표에서 매핑되는 하나의 테스트(행)를 찾을 수 있음(이벤트 서브셋 시퀀스가 반드시 인접해 있을 필요는 없으며 타 이벤트가 사이에 끼어 있는 인터리빙이 가능)

이벤트 서브셋 {b, d, e}의 6개 치환 모두가 위 표의 테스트에 등장한다. 즉, [bde]는 Test 5에, [bed]는 Test 4에, [dbe]는 Test 8에, [deb]는 Test 3에, [ebd]는 Test 7에, [edb]는 Test 2에 등장함 

예2: 2-way 이벤트 시퀀스 테스팅

아래 표처럼 첫 테스트에서 이벤트들을 어떤 순서로 나열한 후 두 번째 테스트는 첫 테스트를 역순서로 함으로써 2-way 시퀀스 커버링 어레이가 구축될 수 있음

[2-way 시퀀스 커버링 어레이]

시퀀스 커버링 어레이 생성

• ‘시퀀스 커버링 어레이(SCA)’는 t<n 일 때 n 변수들로 만들어진 모든 t-way 조합들 중 적어도 하나를 포함하는 ‘표준 커버링 어레이’와 유사함
• SCA를 생성하는 여러 방법이 개발되었지만 가장 효율적인 방법은 ‘단순 그리디 알고리즘(a simple greedy algorithm)’이다.
• 그리디 알고리즘은 다수의 후보 테스트를 반복적으로 생성하고 가장 많은 수의 아직 커버되지 않은 시퀀스를 커버하는 것을 선택함(이 반복이 모든 시퀀스가 커버될 때까지 계속됨) 

3-way 및 4-way 시퀀스 커버링 어레이의 테스트 개수

• 아래 표는 다양한 크기의 이벤트 셋에 대한 3-way 및 4-way 시퀀스 테스트의 수를 보여줌(SCA가 그리디 알고리즘을 사용해 생성됨)
• 대규모 시스템 예에서는 연결할 기기가 10개가 될 수도 있는데 이 경우 치환의 수가 10! 이다. 즉, 완전한 테스팅(exhaustive testing)을 위해 3,628,800개의 테스트가 필요
• 이 경우 모든 3-way 시퀀스를 커버하는 3-way 시퀀스 커버링 어레이를 활용하면 테스트 수를 크게 줄일 수 있음. 아래 표에서 볼 수 있듯이 10개 이벤트의 모든 3-way 시퀀스를 커버하는데 14개의 테스트가 요구됨

[3-way와 4-way 조합 시퀀스의 테스트 개수]

시퀀스 커버링 어레이 특성

• 2-way 시퀀스는 단지 2개 테스트만 필요로 하지만 2-way 이상의 경우 n 이벤트를 위한 테스트 수가 log n 으로 증가함(아래 그래프 참조)
• 필요한 테스트의 수가 이벤트의 수에 대수적으로(logarithmically) 증가하기 때문에 많은 수의 이벤트를 가진 복잡한 시스템을 테스팅하는 경우에도 t-way 시퀀스 커버리지를 다루기가 용이함(적절한 테스트 케이스 수로 테스트 하는 것이 가능)

현실에서 시퀀스 커버링 어레이 활용 사례

1) 테스트 대상 시스템

• 다수의 기기를 랩탑 컴퓨터의 입/출력으로 사용하는 미국 공군의 미션 크리티컬 시스템(비밀 보장 의무로 인해 자세한 정보는 밝힐 수 없음)을 테스트 하는데 SCA를 사용함
• 시스템 기능이 이벤트가 발생하는 순서에 의존적임. 하지만 어떤 서브 시퀀스에서 이벤트가 서로 인접해 있는지 아닌지는 문제되지 않음. 또한 이벤트가 어떤 스텝 하에 있는지 여부도 문제되지 않음
• 이 시스템의 테스트 절차(test procedure)가 8개 스텝을 가짐: 시스템 부트하기, 애플리케이션 열기, 스캔 실행하기, 주변 장치 P-1부터 P-5까지 연결하기
• 주변 장치들 간의 의존성 때문에 일부 시퀀스에서는 시스템이 제대로 동작하지 않을 수도 있음이 예상됨(즉, 정확한 오퍼레이션을 위해 다수의 주변 장치들 간의 협조가 필요하지만 경험상으로 보면 스타트업 동안 자신의 파트너 기기가 존재하지 않으면 일부가 실패하기도 함). 따라서 주변 장치들의 연결 순서가 매우 중요함
• 또한 이벤트 시퀀스에 제약(constraints)이 있음: 1) 애플리케이션이 열리기 전까지는 스캔을 할 수 없고, 2) 시스템이 부트되기 전까지는 애플리케이션을 열 수 없음
• 8개 스텝에 대해 40,320개 치환이 존재하지만 일부는 무의미하고(예, 부트 전에 연결된 주변장치 순서를 변경하는 것) 또 다른 일부는 무효임(예, 제약을 위반). 이런 것들을 제외하면 약 7,000개가 유효한 시퀀스인데 테스트하기에는 너무 많은 숫자임(특히 수동의 물리적인 기기 연결을 요구하는 시스템 테스트에서 실행하기에는 너무 많음)

2) 테스트 케이스

• 테스트 시퀀스 생성에서 부트업(boot-up)을 제거하고 7개 이벤트(스텝)에 대해 SCA를 사용하여 해당 시스템을 테스트함
• 일차적으로 모든 3-way 시퀀스를 커버하는 테스트 구성(test configuration)이 그리디 알고리즘을 통해 생성됨(아래 표의 맨 좌측 열에 1~12 테스트 번호가 매겨짐)
• 시스템 테스트의 고유한 요구사항에 기반하여 이 사전 계산된 시퀀스(the pre-computed sequences)에 일부 변경이 가해짐. 만일 6=‘Open App’이고 5=‘Run Scan’이면 애플리케이션이 시작되기 전에 스캔이 실행될 수 없기 때문 케이스 1, 4, 6, 8, 10, 12가 무효(invalid)가 되어버림. 즉, 치환 자체는 유효하지만 케이스가 무효가 됨
• 여기서 케이스 1과 4처럼 해당 항목들이 인접해 있으면 이들을 서로 교환하는 방식으로 문제를 해결함. 나머지 케이스(6, 8, 10, 12)의 경우는 각각으로부터 여러 개의 케이스가 파생되어 생성됨(아래 표의 첫 열을 보면 6A, 6B, 6C, 6D, 8A … 등이 있음)
• 또한 테스트에서 3개의 USB 연결 각각이 어디에 위치하는지가 문제가 되는지를 확인함. 즉, 아래 표에서 볼 수 있듯이 USB-RIGHT, USB-LEFT, USB-BACK 같은 정보가 포함됨

[최종 테스트 어레이]