개념
먼저 경계를 긋는다 — 코드 구조가 아니라 동작 모델이다
모듈 53(레슨 2)에서 경로 테스트와 순환 복잡도를 다뤘다. 그쪽의 그래프는 코드의 제어 흐름 이고 정점은 문장, 간선은 분기다. 이 레슨의 그래프는 시스템의 동작 모델 이고 정점은 상태, 간선은 전이다. 둘 다 "그래프에서 경로를 뽑는다" 는 말을 쓰지만 대상도, 기준도, 100% 가 뜻하는 것도 다르다. 순환 복잡도·기저 경로·실현 불가능 경로는 그쪽 레슨에 있으니 여기서 반복하지 않는다.
커버리지 기준 네 단계
같은 모델에 어떤 기준을 요구하는지가 생성될 케이스의 성격과 개수를 전부 결정한다. 아래 모델을 끝까지 쓴다 — 전기차 충전기 세션이다.
상태 5개: A 대기 · B 인증중 · C 충전중 · D 일시정지 · E 종료
t1 A -> B 카드태그
t2 B -> C 인증성공
t3 B -> A 인증실패
t4 C -> D 일시정지
t5 D -> C 재개
t6 C -> E 종료요청
t7 D -> E 강제종료
t8 E -> A 정산완료| 기준 | 요구 사항 | 다른 이름 |
|---|---|---|
| 상태 커버리지 | 모든 상태를 최소 1회 방문 | 정점 커버리지. 가장 약함 |
| 전이 커버리지 | 모든 전이를 최소 1회 실행 | 간선 커버리지, 0-스위치 커버리지 |
| N-스위치 커버리지 | 길이 N + 1 의 모든 전이 연쇄를 최소 1회 | 1-스위치 = 전이 쌍 |
| 경로 커버리지 | 시작부터 종료까지 가능한 모든 경로 | 순환이 있으면 무한 |
상태 커버리지는 거의 쓰지 않는다. 위 모델에서 A → B → C → D → E 한 경로면
5개 상태를 다 밟지만, 전이는 8개 중 4개만 밟는다. 상태 커버리지 100% 가
전이의 절반을 빠뜨린다 는 것을 숫자로 확인할 수 있다.
N-스위치 커버리지의 정의
N-스위치 커버리지는 T. S. Chow 가 1978년 유한 상태 기계 테스트 논문에서 제시한 기준이다("switch cover" 의 일반화로 n-switch 집합 커버 계층을 정의했다). 핵심은 연쇄 길이 다.
0-스위치 전이 1개 t1
1-스위치 연속한 전이 2개 t1 t2
2-스위치 연속한 전이 3개 t1 t2 t4
N-스위치 연속한 전이 N + 1 개"연속" 의 뜻은 하나뿐이다 — 앞 전이의 도착 상태가 뒤 전이의 출발 상태여야 한다. 그래서 세는 방법도 기계적이다. 각 전이에 대해, 그 도착 상태에서 나가는 전이 개수를 곱해 나간다.
왜 이 기준이 필요한가. 전이 커버리지 100% 는 "각 전이가 혼자서는 동작한다" 만
보장한다. 실무 결함의 상당수는 전이의 연쇄 에서 나온다 — 일시정지 → 재개 → 일시정지 를 반복했을 때 과금 누적이 어긋나는 결함은 t4·t5 를 각각 한 번씩
밟아서는 절대 안 잡힌다. 1-스위치가 t5 t4 쌍을 요구하는 순간 잡힌다.
기준만 바꿨을 때 — 실제 숫자
위 모델의 출발 상태별 나가는 전이 수(분기도)는 A:1, B:2, C:2, D:2, E:1 이다.
각 기준의 커버 항목 수를 세어 보자.
| 기준 | 커버해야 할 항목 수 | 증가율 |
|---|---|---|
| 상태 커버리지 | 5 | — |
| 전이(0-스위치) | 8 | 1.6배 |
| 1-스위치 | 12 | 1.5배 |
| 2-스위치 | 18 | 1.5배 |
| 3-스위치 | 27 | 1.5배 |
| 경로 커버리지 | 무한 (t4 t5 순환) | — |
1-스위치의 12는 이렇게 나온다. 전이별로 도착 상태의 분기도를 적으면
t1:2(→B), t2:2(→C), t3:1(→A), t4:2(→D), t5:2(→C), t6:1(→E), t7:1(→E), t8:1(→A)
이고 합이 12다. 2-스위치는 그 12개 쌍마다 다시 마지막 도착 상태의 분기도를
곱해 18, 3-스위치는 같은 방식으로 27이 된다.
여기서 전이 하나만 추가해 보자. t9 : C -> A (충전 중 긴급정지로 대기 복귀)를
넣는다. 상태는 그대로 5개, 전이는 9개다.
| 기준 | 전이 8개일 때 | t9 추가 후 | 변화 |
|---|---|---|---|
| 전이(0-스위치) | 8 | 9 | +13% |
| 1-스위치 | 12 | 15 | +25% |
| 2-스위치 | 18 | 24 | +33% |
| 3-스위치 | 27 | 39 | +44% |
모델에 한 줄을 적었더니 3-스위치 요구 케이스가 44% 늘었다. 이것이 MBT 에서 가장 자주 터지는 사고의 구조다. 기획 변경 한 줄이 야간 회귀 실행 시간을 배로 만들고, 아무도 그 인과를 못 짚는다.
규모를 미리 가늠하는 어림식은 단순하다. 전이 수를 E, 평균 분기도를 b 라
하면 N-스위치 항목 수는 대략 E x b^N 이다. 상태 20개에 평균 분기도 3이면
전이는 60, 1-스위치는 180, 2-스위치는 540, 3-스위치는 1,620 이다. N 은 지수에
있다 는 사실만 기억하면 된다.
그래서 어디까지 요구할 것인가
| 선택 | 언제 |
|---|---|
| 전이 커버리지 100% | 기본값. 모든 MBT 도입의 최소선 |
| 1-스위치 100% | 상태가 누적 값(과금·잔액·재고)을 들고 있을 때 |
| 1-스위치 100% + 핵심 구간만 2-스위치 | 실무에서 가장 흔한 타협. 모델을 영역으로 쪼개 기준을 다르게 준다 |
| 2-스위치 이상 전면 적용 | 통신 프로토콜·안전 관련 시스템. 실행 시간 예산을 먼저 확인 |
| 경로 커버리지 | 순환이 없는 작은 모델에서만 성립 |
기준을 모델 전체에 균일하게 주지 않는 것이 핵심 기술이다. 결제·과금 구간만 2-스위치, 조회 구간은 전이 커버리지로 두면 케이스 수가 몇 배씩 줄어든다.
생성 알고리즘 — 같은 기준, 다른 산출물
커버리지 기준이 "무엇을 덮을지" 라면 생성 알고리즘은 "어떤 순서로 걸을지" 다. 같은 전이 커버리지 100% 를 요구해도 알고리즘에 따라 산출물의 성격이 전혀 다르다.
| 방식 | 어떻게 걷는가 | 산출물 성격 |
|---|---|---|
| 무작위 순회(random walk) | 나갈 수 있는 전이 중 하나를 무작위로 골라 계속 걷는다 | 경로가 길고 중복이 많다. 사람이 떠올리지 못하는 긴 조합이 나온다. 재현에는 시드가 필요 |
| 가중 무작위 | 전이에 붙인 가중치를 확률로 쓴다 | 실사용 빈도를 반영한 운영 프로파일 테스트. 희귀 경로는 거의 안 나온다 |
| 미방문 우선 무작위 | 아직 안 밟은 전이를 무작위로 고르고, 거기까지 최단 경로로 이동 | 커버리지 100% 를 짧은 경로로 달성. 케이스 수가 적고 안정적 |
| 목표 지향 탐색(A*) | 특정 상태·전이까지의 최단 경로 | 재현 시나리오·회귀 1건을 뽑을 때. 커버리지 달성용이 아니다 |
| 너비 우선 전이 트리 | 시작 상태에서 깊이를 한 단계씩 늘려 전개 | N-스위치 집합을 체계적으로 만든다. Chow 계열 기법의 구현 |
| 순회 최적화 | 모든 전이를 최소 총 길이로 한 번씩 덮는 닫힌 경로를 계산 | 실행 시간이 가장 짧다. 경로가 길어 실패 지점 분리가 어렵다 |
마지막 항목이 중국인 집배원 문제(Chinese Postman Problem) 다. "모든 간선을 최소 한 번씩 지나는 가장 짧은 닫힌 경로" 를 구하는 고전 그래프 문제이고, 전이 커버리지 100% 를 최소 비용으로 달성한다는 요구와 정확히 같은 문제다. 모든 정점의 진입·진출 차수가 같은 그래프라면 해답은 오일러 회로이고, 길이는 전이 수와 같다.
실무적으로 중요한 단서가 있다. 대부분의 MBT 도구는 중국인 집배원 해법을 그
이름으로 제공하지 않는다. GraphWalker 의 공식 문서에 열거된 생성기는 random,
weighted_random, quick_random, predefined_path, a_star, 그리고 아직
미출시로 표기된 shortest_all_paths 다 — 별도의 집배원 생성기는 없고,
quick_random 이 "미방문 간선을 고른 뒤 최단 경로로 이동" 하는 근사 전략 을
쓴다. 그래서 중국인 집배원은 최적값을 가늠하는 기준선 으로 쓰는 것이 맞다.
도구가 뽑은 경로 길이가 전이 수의 두세 배를 넘으면 알고리즘 선택을 다시 본다.
알고리즘을 고르는 기준
| 상황 | 고를 것 |
|---|---|
| 야간 회귀에서 전이 커버리지를 안정적으로 유지 | 미방문 우선 + 전이 커버리지 100% |
| 장시간 안정성·메모리 누수·상태 꼬임 탐색 | 무작위 순회 + 시간 기반 정지 조건 |
| 출시 전 실사용 패턴 재현 | 가중 무작위 + 운영 로그에서 뽑은 가중치 |
| 특정 결함 재현 경로 1건 | 목표 지향 탐색 |
| 규제 제출용 커버리지 증빙 | 전이 트리 + 결정적 순회(같은 입력이면 같은 산출물) |
마지막 줄을 놓치기 쉽다. 규제 심사에 제출할 테스트 설계는 재현 가능해야 한다. 무작위 순회는 시드를 고정해 기록하지 않으면 "이 케이스 목록을 어떻게 얻었는지" 를 설명할 수 없다.
기대 결과는 어디서 오는가 — MBT 의 오라클 문제
생성기는 입력 순서만 만든다. 각 단계에서 무엇이 올바른 결과인지는 말해 주지 않는다. 모듈 58(레슨 1)에서 오라클의 다섯 출처(명세·이전 버전·병행 구현·불변식· 휴리스틱)와 그 신뢰도·비용을 다뤘다. MBT 에서는 그중 어떤 것을 쓸 수 있는지가 구조적으로 정해진다.
| 오라클 | MBT 에서의 구현 | 강도 |
|---|---|---|
| 상태 불변식 | 정점에 붙인 검증 코드. "충전중 이면 세션이 열려 있고 전력값이 0보다 크다" | 가장 많이 쓴다 |
| 모델 변수와의 대조 | 모델이 액션으로 누적한 값(kWh, 시도 횟수)을 시스템 값과 비교. 축소된 병행 구현 | 강하다. 모델이 복잡해지는 대가 |
| 전이 후행 조건 | 간선에 붙인 검증. "t6 실행 후 상태가 종료 이고 영수증 번호가 발급된다" | 강하다 |
| 부정 전이의 거부 응답 | 금지 조합에서 거부 코드와 상태 불변을 확인(레슨 1) | 설계 필요 |
| 충돌 감지만 | 예외·5xx·행·메모리 급증만 본다 | 가장 약하다. 긴 무작위 경로의 현실 |
여기서 알고리즘 선택이 오라클 강도와 맞물린다. 무작위 순회로 300스텝을 걸으면 사람이 각 단계의 기대 결과를 적어 둘 수 없다. 그래서 긴 무작위 경로는 사실상 "죽지 않는지" 만 보는 스모크형 오라클 로 떨어진다. 반대로 미방문 우선 생성이 뽑은 짧은 경로는 단계마다 불변식을 검증할 수 있다.
짧은 결정적 경로 케이스 수 많음 · 경로당 단계 적음 · 오라클 강함 · 실패 지점 명확
긴 무작위 경로 케이스 수 적음 · 경로당 단계 많음 · 오라클 약함 · 실패 지점 모호둘을 섞어 돌리는 것 이 정석이다. 커밋마다 미방문 우선 + 전이 커버리지, 야간에 무작위 순회 + 시간 기반 정지 조건으로 따로 돌린다.
마지막으로 모델이 오라클을 겸하는 순환 을 경계해야 한다. 모델에서 기대 결과를 뽑아 그 모델로 생성한 테스트를 판정하면, 모델이 틀렸을 때 아무 신호도 나오지 않는다. 그래서 상태 불변식은 모델이 아니라 명세에서 받아 적어야 하고, 그 작업이 레슨 4의 워크숍에서 이뤄진다.
실무에서 왜 필요한가
"MBT 를 도입했는데 케이스가 4,000개 나왔습니다" 라는 보고는 숫자가 아니라 설정의
문제다. 커버리지 기준과 생성 알고리즘을 분리해 설명할 수 있으면 대화가 달라진다 —
"2-스위치를 전체에 걸었습니다. 과금 구간만 2-스위치로 좁히고 나머지를 전이
커버리지로 내리면 약 600개가 됩니다" 가 가능해진다. E x b^N 어림식만 있어도
회의 중에 추정이 나온다.
반대 방향의 설득도 필요하다. 전이 커버리지 100% 를 달성했다는 리포트를 받았을 때 "연쇄는 안 봤다" 고 말할 수 있어야 한다. 일시정지·재개를 반복하면 과금이 어긋나는 결함, 취소·재주문을 번갈아 하면 쿠폰이 복구되지 않는 결함은 전부 1-스위치 영역이다. 커버리지 숫자가 100% 인데 결함이 계속 나오는 상황에서 이 구분이 다음 행동을 정한다.
그리고 생성 전에 오라클을 정하는 습관이 비용을 가장 많이 아낀다. 경로를 먼저 뽑아 놓고 "이제 기대 결과를 적자" 로 가면 수백 건 앞에서 멈춘다. 오라클을 정점·간선의 검증 코드로 먼저 설계하면, 경로가 몇 개로 늘어나든 추가 작업이 없다 — 이것이 MBT 의 실질적인 이득이 나오는 지점이다.