1291.17 상태 머신의 테스트 커버리지 확보의 어려움

1291.17 상태 머신의 테스트 커버리지 확보의 어려움

1. 테스트 커버리지의 개념

테스트 커버리지(test coverage)는 테스트 스위트(test suite)가 시스템의 동작 공간을 얼마나 포괄적으로 검증하였는지를 측정하는 정량적 지표이다. FSM의 테스트에서 대표적으로 사용되는 커버리지 기준은 다음과 같다 (Binder, 1999):

  1. 상태 커버리지(State Coverage): 모든 상태가 최소 1회 이상 활성화되었는가.
  2. 전이 커버리지(Transition Coverage): 모든 전이가 최소 1회 이상 실행되었는가.
  3. 전이 쌍 커버리지(Transition Pair Coverage): 모든 연속 전이 쌍 (t_i, t_j)가 최소 1회 이상 실행되었는가.
  4. 경로 커버리지(Path Coverage): 모든 가능한 실행 경로가 테스트되었는가.

각 커버리지 기준은 상위 기준이 하위 기준을 포용하는 계층적 관계를 가지며, 경로 커버리지가 가장 강력하지만 달성이 가장 어렵다.

2. 상태 커버리지의 비용

n개의 상태를 가진 FSM에서 상태 커버리지를 달성하기 위해서는 초기 상태에서 모든 상태에 도달하는 테스트 입력 시퀀스를 설계해야 한다. 최소 테스트 시퀀스의 길이는 FSM의 연결 구조에 따라 달라지며, 최악의 경우 O(n)에 비례한다. 상태 수가 수백에서 수천에 달하는 대규모 FSM에서도 상태 커버리지 자체는 달성 가능하나, 이것이 시스템의 올바름을 보장하지는 않는다.

3. 전이 커버리지의 복잡도

전이 커버리지는 모든 전이가 최소 1회 실행될 것을 요구한다. t개의 전이를 가진 FSM에서 전이 커버리지를 달성하기 위한 최소 테스트 시퀀스 수는 그래프의 오일러 경로(Eulerian path) 존재 조건에 의하여 결정된다. 오일러 경로가 존재하면 단일 시퀀스로 모든 전이를 커버할 수 있으나, 일반적인 FSM에서는 복수의 테스트 시퀀스가 필요하다.

밀접하게 연결된 FSM에서 t \approx O(n \times |\Sigma|)이므로, 전이 커버리지를 위한 테스트 비용은 상태 수와 이벤트 수의 곱에 비례한다.

4. 경로 커버리지의 비실용성

경로 커버리지는 초기 상태에서 임의의 종료 조건까지의 모든 가능한 실행 경로를 열거하고 각 경로를 최소 1회 테스트할 것을 요구한다. 순환(cycle)이 존재하는 FSM에서 경로의 수는 무한하며, 순환을 제한하더라도 길이 L 이하의 경로 수는 O(n^L)에 달한다.

예를 들어, 50개의 상태와 평균 연결도(average degree) 5를 가진 FSM에서 길이 10 이하의 경로 수는 5^{10} \approx 10^7에 달한다. 이는 경로 커버리지의 완전한 달성이 대규모 FSM에서 실질적으로 불가능함을 의미한다.

5. 가드 조건에 의한 추가 복잡도

FSM의 전이에 가드 조건(guard condition)이 부착된 경우, 동일 상태에서 동일 이벤트에 대하여 가드 조건에 따라 상이한 전이가 선택된다. 가드 조건의 조합까지 고려한 테스트 커버리지를 달성하려면, 각 전이에 대하여 가드 조건이 참인 경우와 거짓인 경우를 모두 테스트해야 한다. g개의 독립적 가드 조건이 하나의 전이에 부착된 경우, 해당 전이의 조건 조합 수는 2^g이며, 이는 전이 수준에서의 테스트 복잡도를 지수적으로 증가시킨다.

6. 테스트 오라클의 부재

FSM 테스트에서 테스트 오라클(test oracle)—실행 결과의 올바름을 판단하는 기준—의 정의가 어려울 수 있다. FSM의 기대 행동은 전이 테이블에 의하여 정의되나, 가드 조건의 평가 결과, 행동의 부작용(side effect), 환경과의 상호작용 등에 의하여 실제 행동이 기대와 상이할 수 있다. 자동화된 테스트 오라클의 구성은 FSM의 완전한 형식적 명세(formal specification)를 전제하며, 이러한 명세 자체의 작성 비용이 적지 않다.

7. 회귀 테스트의 비용 증가

FSM이 수정될 때마다 기존 테스트 스위트를 재실행하여 회귀 오류를 탐지하는 회귀 테스트(regression testing)가 수행되어야 한다. FSM의 규모가 증가할수록:

  1. 테스트 스위트의 크기 증가: 충분한 커버리지를 유지하기 위한 테스트 케이스의 수가 증가한다.
  2. 테스트 실행 시간 증가: 각 테스트 케이스의 실행 시간이 FSM의 경로 길이에 비례하여 증가한다.
  3. 테스트 유지보수 비용 증가: FSM의 구조 변경 시 기존 테스트 케이스의 기대 결과를 갱신해야 하며, 이 비용은 변경 규모에 비례한다.

8. 행동 트리의 테스트 용이성

행동 트리에서 테스트 커버리지의 확보는 FSM에 비하여 구조적으로 용이하다:

  1. 노드 단위 단위 테스트: 각 노드(액션 노드, 조건 노드)가 독립적으로 테스트 가능하며, 블랙보드의 상태를 모의(mock)하여 다양한 입력 조합에 대한 노드의 반환값을 검증할 수 있다.
  2. 서브트리 단위 통합 테스트: 서브트리를 독립적으로 실행하여 내부 노드 간의 상호작용을 검증할 수 있다.
  3. 결정적 실행 모델: Tick 기반 실행에서 동일 트리와 동일 블랙보드 상태에 대하여 항상 동일한 실행 경로가 결정되므로, 테스트의 재현성(reproducibility)이 보장된다.
  4. 경로 수의 제한: 트리 구조에서 루트에서 리프까지의 경로 수는 리프 노드의 수에 비례하며, 이는 FSM에서의 경로 수의 조합적 폭증과 대비된다.

9. 참고 문헌

  • Binder, R. V. (1999). Testing Object-Oriented Systems: Models, Patterns, and Tools. Addison-Wesley.
  • Chow, T. S. (1978). “Testing Software Design Modeled by Finite-State Machines.” IEEE Transactions on Software Engineering, SE-4(3), 178–187.
  • Colledanchise, M., & Ögren, P. (2018). Behavior Trees in Robotics and AI: An Introduction. CRC Press.

v0.1.0