Structural Testing

Structural Testing

Structural testing을 이해하기 위해서는 먼저 "프로그램이 왜 실패하는가?", "어떤 조건에서 실패가 발생하는가?를 짚어야 한다.

사용자가 기대한 결과를 제공하지 못하는 경우를 프로그램 실패 (failure)라고 정의한다. 예를 들어 정상적으로 작동해야 하는 기능이 엉뚱한 값을 출력하거나, 프로그래밍 멈추거나, 충돌하는 것까지 모두 여기에 포함되어 있다.

이러한 실패는 결국 코드 내부에 존재하는 fault(버그)가 특정 입력에 의해 실행되면서 실패로 발전하는 과정을 갖는데, 이를 PIE 모델로 보면 아래와 같다.

• Execution: 프로그램 실행이 해당 버그가 포함된 부분까지 도달해야 한다.
• Infection: 그 버그가 잘못된 상태를 만들어야 한다.
• Propagation: 그 잘못된 상태가 사용자에게 보이는 잘못된 출력으로 이어져야 한다.

이 세 단계 중 하나라도 충족되지 않으면 버그는 찾을 수 없게 된다. 즉, 테스트가 버그를 드러내려면 "버그를 실행시키고 전파되도록 만드는 입력""을 찾아야 한다.

Software Test 목적

테스트는 "미리 정의된 입력 (test case)과 기대 출력 (expected output)"을 비교하여 실패를 찾아내는 활동이다.
이때 동일한 프로그램이라도

• 사용자 요구사항 기반 테스트
• 코드 구조 기반 테스트

두 관점을 모두 사용해야 결함을 충분히 탐지할 수 있다.

Blackbox가 요구사항 충족 여부에 초점을 둔다면, whitebox는 코드 내부 구조를 모두 충분히 실행해보는 것에 초점을 둔다.
구조 기반 테스트는 프로그램의 내부 구조, 즉 소스 코드 자체를 기준으로 테스트 케이스를 설계하는 기법이다. 이는 블랙박스 테스트와 달리 코드를 직접 읽고, 그 코드의 제어 흐름과 데이터 흐름을 모델링하여 테스트를 만든다.

Program Failure

사용자는 프로그램이 모든 입력에 대해, 주어진 시간 안에, 올바른 출력을 제공하기를 기대한다.

프로그램 실패란 프로그램 실행 결과가 요구사항을 만족하지 못할 때 발생한다.

• 논리 오류 (assertion failure)
• 메모리 오류
• 리소스 누수
• Deadlock, timeout 등 concurrency 오류
• Crash (segmentation fault 등)

테스트는 fault가 failure로 이어지는 세 단계를 모두 일으키는 입력을 찾아야 한다는 점에서 중요하다.

Testing

테스트란

• 입력 (test case)을 넣고
• 실제 출력 (actual output)을 얻어
• 기대 출력 (expected output)과 비교하여
  • 같으면 test success
  • 다르면 test failure

여기서 test oracle이란 정답을 제공하는 기준이다.

Foundation of Software Testing

블랙박스와 화이트박스 테스트의 관점을 나누기 위해 다음 세 가지를 정의한다.

1. Requirement Spec: 시스템이 해야 할 일을 정의한다.
2. Program: 명세를 구현한 실제 소스 코드
3. Test Case: 입력과 예상 출력의 조합

Whitebox 테스트는 프로그램의 내부 구조를 보고 테스트 케이스를 선택한다는 점이 핵심이다.

다양한 테스트 기법이 있으나 비용과 효과 측면에서 whitebox testing인 brach coverage가 가장 효율성이 크다.

Structural Testing

Structural testing에서는 보통 아래 두 모델을 사용한다.

1. Control Flow Graph (CFG)
2. Data Flow Graph (Defs & Uses)

소스 코드를 기반으로 그래프를 생성한 뒤에는 이 그래프를 기반으로 커버리지 기준을 충족시켜야 한다.

1. Node Coverage
2. Edge Coverage
3. Loop Coverate
4. Condition Coverage
5. Path Coverate

그래프 기반 모델링이 구조 기반 테스트의 핵심이다.

Graph Basics

그래프는 소프트웨어 구조를 일반화하여 표현할 수 있는 강력한 수단이다. 테스트는 결국 그래프를 어떻게 방문할 것인가의 문제이다.

Definition of a Graph

그래프는 다음 요소로 구성된다.

• Node: 실행 지점, 문장 또는 basic block
• Edge: 제어 흐름 (a → b)
• 초기 노드 $(N_0)$
• 종료 노드 $(N_f)$
• 경로: 노드들의 연속 $[n_1, n_2, \cdots, n_M]$
  • 길이: edge 개수
  • subpath: 경로의 부분 경로
  • Reach ($n$): $n$에서 도달 가능한 그래프 부분

Test Path

초기 노드에서 시작하여 마지막 노드에서 끝나는 실제 실행 흐름을 test path라고 한다. 특히, 하나의 진입점과 하나의 종료점을 갖는 그래프를 SESE (Single-Entry Single-Exit)라고 한다.

Test path가 특정 노드나 엣지를 포함할 때, 해당 노드/엣지를 visit 한다고 표현한다. 또한 test path가 subpath 전체를 순서대로 포함할 때 tour라고 표현한다.

Control Flow Coverage

Node and Edge Coverage

모든 노드/엣지를 한 번 이상 방문하면 충족된다. Edge coverage가 Node coverage보다 조금 더 강력하다.

Edge-Pair Coverage

길이가 2인 모든 subpath를 방문하면 충족된다. 이때 test requriement는 다음과 같이 표현된다. $\text{TR}_\text{EPC}=[0,1,2], [1,2,3]$ 등

Loops in Coverage

Loop가 있으면 경로가 무한히 길어지므로 complete path coverage는 불가능하다. 이를 다루기 위해 loop를 1회만 수행하거나, prime path를 도입하여 가장 합리적인 path를 선택하는 등의 방법이 제시되었다.

Simple Path vs Prime Path

• 내부에 중복 노드가 없는 경로를 Simple Path라고 한다.
• Simple path 중 다른 simple path의 proper subpath가 아닌 것 즉, 가장 긴 유효 simple path를 Prime Path라고 한다.

Prime Path Coverage는 EC, EPC, NC를 모두 포함한다.

Round Trip Coverage

시작과 끝이 같은 prime path를 Round Trip Coverage라고 한다. Loop 중심 coverage를 표현하지만, NC/EC보다 약한 경우도 있다.

Sidetrip & Detours

Subpath를 순서대로 포함하되, 중간에 다른 노드를 거쳤다가 다시 돌아올 수 있다. (sidetrip)

Subpath의 노드들을 순서대로 방문하는 것을 detour라고 한다.

Pure Structural Coverage의 한계

Branch coverage 100%를 달성해도 의미적 오류를 잡을 수 없다. 즉, 구조적 기준만으로는 의미적 오류를 잡을 수 없다.

Data Flow Coverage

데이터 흐름 기반 테스트는 값이 어디에서 정의되고 어떻게 사용되는지를 추적함으로써 테스트가 충분한지 판단한다. 단순히 노드와 엣지 같은 구조를 보는 구조적 테스트와 달리, 값이 실제로 어떻게 흐르는지 분석한다는 점에서 의미적인 오류를 찾는 데 효과적이다.

• Goal: 모든 변수들이 올바르게 계산되는지 보장하는 것
• Definition: 변수가 메모리에 저장되는 시점
• Use: 변수에 접근하는 (읽는) 시점

DU pair

특정 변수를 정의하고 사용하는 지점이 $l_i$와 $l_j$일 때 두 지점을 연결하는 def-clear path가 존재해야 DU-pair가 성립한다.

def-clear란 경로 위에서 변수가 다시 정의되지 않는 경로를 뜻한다. 즉, $l_i$에서 정의된 값이 손상되지 않고 $l_j$까지 도달하는 것을 의미한다.

DU-Path는 DU-pair를 만족시키는 simple path (자시 반복이 없는 경로)를 말한다. 변수 $v$에 대해 def-clear 조건을 만족해야 한다. 테스트 경로가 특정 DU-Path를 따랐다고 인정되려면 다음 조건을 만족해야 한다.

• DU-Tour: 테스트 경로가 해당 DU-Path를 순서대로 포함하면서, 전체 경로가 $v$에 대해 def-clear 상태여야 한다.
• 다른 커버리지 기준과 마찬가지로 sidetrip (다른 경로로 샜다가 다시 돌아오는 것)을 허용할 수 있다. 점검 방식은 이전의 prime path touring과 동일하다.

Data Flow Coverage

데이터 흐름 기반 커버리지는 다음 세 단계로 구성된 테스트 강도 계층 구조를 갖는다.

1. All-defs Coverage (ADC): 모든 정의가 적어도 하나의 use에 도달해야 한다. 즉, 정의되었는데 사용되지 않는 값이 있어서는 안 된다.
2. All-uses Coverage (AUC): def가 도달 가능한 모든 use를 test path가 커버해야 한다. 각 def는 가능한 모든 use와의 조합을 만족해야 한다.
3. All-du-paths Coverage (ADUP): def와 use 사이 가능한 모든 def-clear du-path를 탐색해야 한다. AUC보다 더 강력하고, 데이터 흐름 기반 기준 중 가장 강도 높은 기법이다.

구조 기반 테스팅에서는 prime path coverage가 매우 강력하지만, 데이터 흐름 기반 기준으로는 ADUP가 가장 강력하다.

Structural Coverage for Source Code

Control Flow Graph

CFG는 프로그램의 실행 가능한 모든 흐름을 노드와 엣지로 시각화한 모델이다.

• Node: 분기가 없는 연속 실행 구문
• Edge: 제어 흐름 (분기, 반복 등)

예를 들어 if 문에서 각 return은 독립된 노드로 취급되어야 한다.

Edge Coverage

CFG의 모든 edge를 방문해야 한다.

Edge-Pair Coverage

길이 2인 모든 subpath를 방문해야 한다. EC에서 보이지 않던 숨겨진 버그를 EPC에서 탐지할 수 있다.

Prime Path Coverage

Simple path 중 더 이상 확장될 수 없는 path를 모두 커버해야 한다. Primt path coverage에서 infeasible 경로가 존재할 수 있다는 것을 밝힌다.

CFG 기반 테스트는 연구가 잘 되어 있으며 비교적 체계적이다. 하지만 실제 코드를 CFG로 옮길 때는 subtle 설계 결정이 필요하다.