Cyclomatic complexity

아래 내용은 위키피디아 번역한 것입니다.

http://en.wikipedia.org/wiki/Cyclomatic_complexity

Cyclomatic complexity (또는 conditional complexity, 이하 CC) 는 Software Metric 의 하나이다.

* Software Metric : a measure of some property of a piece of software or its specifications : 소프트웨어 측량법

1976에 J. McCabe, Sr 에 의해 개발되었고 프로그램의 복잡도를 가리키는 데 사용된다. CC는 프로그램의 소스 코드로부터 선형 독립 경로( linearly independent paths ) 를 측정한다. 개념은 Flesch-Kincaid 가독성 테스트에 의해 측정되는 일반적인 텍스트 복잡도와 약간 유사하다.

* Linearly independent path : 이 글에서는 선형 독립 경로 라고 번역됩니다.

CC 는 프로그램의 흐름 제어 그래프 (control flow grapth)를 이용하여 계산된다. 그래프의 노드는 더이상 나눌 수 없는 명령어 집합이다, 그리고 단방향 변(directed edge)은 만일 첫 번째 명령이 실행 된 후 바로 두번째 명령이 실행된다면 두 노드를 연결한다. CC 는 또한 프래그램 내의 함수, 모듈 또는 클래스등에도 응용될 수 있다.

* directed edge  : directed 는 방향성 또는 단방향으로 해석될 수 있고, edge 는 변 또는 선으로 해석될 수 있음)  : 말하자면 노드와 노드를 연결하는 단방향 화살표이다

기본 경로 테스팅 (Basis Path Testing, McCabe 에 의해 처음 제안된 테스팅 전략 )은 각각의 선형 독립 경로를 테스트한다. 이 경우, 테스트 케이스의 개수는 프로그램의 CC 와 동일하다.

Description

한 소스 코드 영역의 CC 는 선형 독립 경로의 개수이다. 예를 들면, 만일 소스 코드가 IF 문 또는 For 반복문과 같은 결정 지점 (decision points)이 하나도 없다면, 복잡도는 1이 될 것이다, 왜냐하면 오직 하나의 경로만이 존재하기 때문이다. 만약 코드가 하나의 조건을 포함하고 있는 한 개의 IF 문을 가지고 있다면, 2개의 경로가 있게 된다. 하나는 IF 문이 TRUE 로 평가될 때 이고 다른 하나는 FALSE 로 평가될 때이다.

수학적으로, 구조화된 프로그램( Structured Program ) 의 CC 는 기본 블락(basic block)들로 구성된 방향그래프 (directed graph)로 정의된다.그리고 블락들 간에 제어의 흐름을 변(edge)으로 표현한다. (프로그램의 제어 흐름 그래프). 복잡도는 아래 정의와 같다.

* Structured Program : 구조화된 프로그램 : 여기서 Structured 의 의미는 특별히 "함수 당 하나의 종료 (return 문)를 가지는" 것을 의미 한다.

M = E - N + 2P

M = Cyclomatic Complexity

E = 변의 개수

N = 노드의 개수

P = 연결된 컴포넌트(connected component)의 개수

간단한 프로그램의 제어 흐름 그래프. 프로그램은 빨간색 노드에서 실행을 시작하고, 그러고 나서 하나의 루프 (그 빨간색 바로 아래의 세개의 노드로 된 그룹)로 들어 간다. 루프를 나오면 하나의 조건 문이 있다 (루프의 아래 그룹), 그리고 마침내 프로그램은 파란색 노드에서 종료한다. 

위 그림의 CC 는 다음과 같다.

9 (E) - 8 (N) + 2 * 1 (P) = 3 (CC)

다른 공식은 각 종료 지점(exit point)이 다시 시작 지점(entry point)과 연결되는 그래프에 사용된다. 이 경우, 그래프는 "강하게 연결되었다 (strongly connected)' 라고 불리어지고, 프로그램의 CC 는 그래프의 cyclomatic 개수와 같다 (첫번째 Betti 수라고 알려진). 공식은 다음과 같다.

M = E - N + P

이것은 그래프에 존재하는 선형 독립 사이클 (linearly independent cycle)의 개수를 계산하는 것과 같다, 즉 자신안에 다른 사이클을 포함하지 않는 사이클들 말이다. 각각의 종료 지점이 다시 시작 지점으로 되돌아 반복하기 때문에 각 종료 지점마다 적어도 하나의 사이클은 존재하게 된다.

단일 프로그램 (또는 서브루틴 또는 메소드)의 경우, P 는 항상 1과 같다. 그러나 CC 는 동시에 여러개의 프로그램 또는 서브프로그램에 동시에 (예로, 한 클래스의 모든 메소드) 적용될 수도 있고,  그러한 경우 P 는 프로그램의 개수와 동일할 것이다, 왜냐하면 각각의 서브프로그램은 그래프에서 연결되지 않은 서브셋(disconnected subset)으로 나타날 것이기 때문이다.

오직 하나의 진입점과 종료점을 가진 임의의 구조화된 프로그램의 CC 는  그 프로그램이 가지는 결정 지점(decision point, 즉, 'if' 문 과 조건 반복문)의 개수에 일을 더한 것과 같다.

CC는 여러개의 종료점을 가지는 한 프로그램으로 확장될 수 있다; 이 경우 다음과 같다:

π - s + 2

π 는 프로그램의 결정 지점(decision point)의 개수이고, 

s 는 종료점의 개수이다.

강하게-결합된 제어 흐름 그래프를 보여주는 위 함수에 대해 두번째 공식을 이용하여 계산해보면 다음과 같다. 

E = 10, N = 8 그리고 P = 1, 그래서 프로그램의 CC 는 여전히 3 이다.

Implications for Software Testing

CC 의 또다른 적용은 특정 모듈의 테스트 커버리지를 달성하기 위해 필요한 테스트 케이스의 개수를 결정하는 데 있다. 

CC 의 두 가지 속성때문에 유용하다, M 이 특정 모듈의 CC 라고 가정하자.

• M 은 완전한 브랜치 커버리지를 달성하기 위해 필요한 테스트 케이스 개수의 상한선이다.
• M 은 제어 흐름 그래프 (CFG) 를 달성하는 경로 개수의 하한선이다. 각 테스트 케이스가 하나의 경로라고 가정하면, Path coverage 를 달성하기 위해 필요한 테스트 케이스의 개수는 실제로 도달할 수 있는 경로의 개수와 동일하다. 그러나 일부 경로는 CFG 를 통한 경로의 개수가 path coverage 에 필요로 하는 테스트 케이스 개수의 명백한 상한선일지라도 불가능할 수 있다. (가능한 경로의) 최후의 개수는 가끔 M 보다 작다.

위 세가지 경우에 대한 개수는 다음과 같다.

branch coverage ≤ cycomatic complexity < 경로의 개수

예를 들어, 두개의 순차적인 if-then-else 구문으로 구성된 프로그램을 고려해 보자.

if ( c1() )     f1(); else     f2(); if( c2() )     f3(); else     f4();

이 예에서는, 두개의 테스트 케이스로 완전한 branch coverage 를 충분히 달성할 수 있지만, 완전한 path coverage 를 달성하기 위해서는 4개의 테스트 케이스가 필요하다. 또한 프로그램의 CC 는 3 (9 - 7 + 1) 이다.

일반적으로, 한 모듈의 모든 실행 경로 전체를 테스트하기 위해서는 크게 신경써야만 한다. 이것은 아주 높은 복잡도(complexity number)를 가진 모듈은 낮은 값을 가진 모듈보다 더 많은 테스팅 노력이 필요로 하다는 것을 의미한다 왜냐하면 더 높은 복잡도는 코드에 더 많은 경로가 존재한다는 것을 가리키기 때문이다. 이것은 또한 프로그래머가 이해하기에 더 어렵다는 것을 의미한다 왜냐하면 프로그래머는 다른 경로들과 그러한 경로의 결과를 이해해야 하기 때문이다.

불행히도, 프로그램의 모든 가능한 경로를 테스트 하는 것이 언제나 실용적인 것은 아니다. 위 예제를 살펴보면, 추가적인 if-then-else 문이 추가될 때 마다, 가능한 경로의 개수는 두 배가 된다. 프로그램이 이런 식으로 커진다면, 모든 경로에 대해 테스트를 하는 것은 비현실적이다.

하나의 일반적인 테스팅 전략은, NIST 구조화된 테스팅 방법에 의해 지지되는, 모듈의 충분한 커버리지를 얻기위해필요한 white-box test 의 개수를 결정하기 위해 모듈의 CC 를 사용하는 것이다. 거의 모든 경우, 이러한 방법을 따르면, 하나의 모듈은 최소한 CC 만큼의 테스트는 가해져야 한다. 대부분의 경우, 테스트의 개수는 함수의 모든 적절한 경로를 테스트하는 데 충분하다. 

정밀하게 테스트 하기 위해 단순한 branch coverage 보다는 더많은 테스트를 필요로 하는 함수의 예로 다시 위 함수를 살펴보자. 하지만 버그가 일어나는 것을 피하기 위해 f1() 또는 f3() 중 하나를 호출하는 임의의 코드는 반드시 다른 것을 호출해야 한다고 가정하자. c1() 과 c2() 의 결과는 독립적이다고 가정하고, 위에서 언급된 함수는 버그를 포함하고 있다는 것을 의미한다. Branch coverage 는 해당 메소드에 단지 두개의 테스트만 수행하도록 하고, 가능한 테스트 케이스의 집한은 아래와 같을 것이다.

• c1() 은 true 를 반환하고 c2() 도 true 를 반환
• c1() 은 false 를 반혼하고 c2() 도 false 를 반환.

이 테스트 케이스의 어떤 것도 버그를 발견하지 못한다. 하지만, 만일 필요로 하는 테스트 케이스 개수에 CC 를 사용한다면, 그 개수는 3으로 증가할 것이다. 그리하여 우리는 반드시 아래 경로 들 중 하나를 테스트해야만 한다.

역자 주: 가정에서 f1() 을 호출한 경우 f3 () 를 반드시 호출해야 한다고 하였습니다. (그 반대도 마찬가지) 만약 f1() 을 호출하였는데 f3() 를 호출하지 않았다면 버그가 발생한다고 가정하였습니다. 위의 경우는 f1() -> f3(), f2() -> f4() 가 되기 때문에 둘다 버그가 발생하지 않습니다. 하지만 아래의 경우는 f1() ->f4(), f2() -> f3() 가 되기 때문에 에러가 발생합니다.

• c1() 은 true 를 반환하고 c2() 는 false 를 반환
• c1() 은 false 를 반환하고 c2() 는 true 를 반환

이 테스트 케이스 중 하나는 버그를 발견할 것이다.