데이터 흐름 테스팅

데이터 흐름 테스팅(Data Flow Testing)

• 데이터 흐름(Data Flow): 어떤 한 변수의 ‘정의(definition)’에서부터 ‘사용(uses)’까지의 그 값의 흐름
• 데이터 흐름 테스팅은 프로그램 변수에 상응하는 메모리 위치가 적절한 방식으로 접근되는지를 확인하기 위해 변수 값 ‘할당(assignment)’과 ‘사용(usage)’을 추적한다.
• ‘데이터 흐름 아노말리(Data flow anomaly)’라 불리는 데이터 관련 비정상적인 상황을 식별하고자 함. 예를 들면, 아래와 같은 것들이 있다.
  - 정의된 변수가 또 다시 정의됨(Defined and Then Defined Again)
  - 정의되지 않은 변수가 사용됨(Undefined but Referenced)
  - 정의된 변수가 미사용됨(Defined but Not Referenced)
• 아래 그림은 변수의 상태(U: 미정의, D: 정의되고 미사용됨, R: 정의되고 사용됨, A: 비정상)와 특정 상태로 전이하게 만드는 액션(d: 정의하기, r: 사용하기, u: 정의 해제하기) 을 나타냄. 예를 들어, 미정의 상태(U)인 변수에 사용하기(r) 액션이 가해지면 비정상 상태(A)로 변경됨 

 

[변수의 상태 전이 다이어그램]

 

데이터 흐름 그래프(Data Flow Graph: DFG)

• 데이터의 정의(definitions)와 사용(uses)을 식별하려는 목적을 가지고 그려진 그래프
• 소스 코드의 데이터 흐름을 중심으로 하는 별도의 데이터 흐름 그래프를 작성할 수도 있지만 대개는 제어 흐름 그래프(Control Flow Graph)의 노드와 에지에 변수의 정의와 사용에 관한 정보를 주석으로 추가하는 방식을 활용함
• 프로그램에 데이터 변수가 등장할 때 마다 아래 중 어디에 해당되는지 분류하여 제어 흐름 그래프의 적절한 위치에 데이터 정보를 덧붙인다. 
  - 변수 정의(Definition): 변수에 값이 할당됨
  - 변수 정의 해제(Undefinition 또는 Kill)
  - 변수 사용(Use): 변수 값이 읽혀짐. 즉, 변수가 표현식이나 조건문에서 사용됨

 

기호	데이터 흐름 레이블 설명
def	주어진 위치에서 변수 v에 값이 할당됨. 즉, 변수 v의 값이 메모리로 저장됨
c-use	변수 v의 값이 주어진 위치의 계산식에서 사용됨(Computation use)
p-use	변수 v의 값이 주어진 위치의 조건식에서 사용됨(Predicate use)

 

[변수 레이블 첨가 예]

 

데이터 흐름 분석 관련 용어

 

데이터 흐름 커버리지 기준(Data flow coverage criteria)

프로그램에서 어떻게 변수가 정의되고 사용되는지를 기반으로 하여 커버리지 기준을 적용함. 즉, 데이터 흐름 그래프 상에서 각 변수의 ‘def-use pair’가 다양한 방식으로 실행되도록 하는 기준이며, 대표적으로 아래와 같은 것들이 있다. 

• all-defs 기준: 프로그램에서 변수 v가 정의된 위치 각각에 대해서 해당 def 위치에서부터 적어도 하나의 use(c-use이든 p-use이든 상관 없음) 위치까지의 def-clear path를 포함하도록 테스트 케이스 집합을 생성함. 즉, 모든 정의(all definitions)가 한 번씩은 사용되게 된다.
• all-c-uses 기준: 프로그램에 존재하는 변수 v의 모든 정의와 해당 정의로부터 도달가능한 변수 v의 모든 c-use에 대해서, 각 def에서부터 모든 c-use 노드까지의 def-clear path를 포함하도록 테스트 집합을 생성함. 즉, 변수 정의 각각에 의해 영향을 받는 모든 계산식(all computations)이 실행되어야 함
• all-p-uses 기준: 변수 v의 모든 정의와 해당 정의로부터 도달가능한 v의 모든 p-use에 대해서, 각 def부터 모든 p-use까지의 def-clear path를 포함하도록 테스트 집합을 생성함. 즉, 변수 정의 각각에 의해 영향을 받는 모든 브랜치가 실행되도록 테스트를 수행
• all-c-uses/some-p-uses 기준: all-c-uses 기준과 동일하지만 예외적으로 변수 v의 c-use가 존재하지 않는 경우 v의 def부터 일부 p-use까지의 def-clear path를 대신 선택
• all-p-uses/some-c-uses 기준: all-p-uses 기준과 동일하지만 예외적으로 변수 v의 p-use가 존재하지 않는 경우 v의 def부터 일부 c-use까지의 def-clear path를 대신 선택
• all-uses 기준: all-p-uses 기준과 all-c-uses 기준의 결합. 프로그램에 존재하는 변수 v의 모든 def-use pair에 대해서 적어도 하나의 상응하는 경로를 포함하도록 테스트 케이스 집합을 생성함. 변수 def에 의해 직접적으로 영향을 받는 모든 계산식과 모든 브랜치가 실행되게 됨
• all-du-paths 기준: 변수 v의 정의 각각에 대해서 모든 가능한 du-path를 포함하도록 테스트 케이스 집합을 생성한다. 이 때 각 경로에 루프가 존재하지 않거나 또는 많아야 하나의 루프만 포함하도록 한다.

 

[데이터 흐름 커버리지 기준의 적용 예]

 

데이터 흐름 커버리지 기준의 포함 관계(Subsumption relationships)

제어 흐름 커버리지 기준의 계층도와 마찬가지로 데이터 흐름 기준들 간에도 아래 그림과 같은 포함 관계가 형성된다(상위에 위치한 커버리지 기준이 하위 기준을 포함). 일반적으로 데이터 흐름 커버리지 기준이 제어 흐름 커버리지 기준 보다 더 강력한 커버리지를 제공하는 것으로 여겨지며, 따라서 데이터 흐름 커버리지 기준들을 충족시키는데 더 많은 비용이 들어간다. 

[데이터 흐름 커버리지 기준 관계도]

 

데이터 흐름 테스팅의 활용

• 데이터 흐름 분석 기법이 동적인 테스팅 뿐만 아니라 정적 프로그램 분석(static program analysis)에도 사용될 수 있음
• 데이터 흐름 커버리지 기준을 통해 선택된 경로가 실행되려면 해당 경로의 모든 프레디켓이 참(true)이 되도록 하는 입력 변수(input variables)의 값 할당과 글로벌 변수가 존재해야 하지만 그렇지 못한 경우가 많다. 즉, 실행 불가능한 경로(Infeasible/inexecutable paths) 때문에 100% 데이터 흐름 커버리지 달성이 대체로 어려움
• 데이터 흐름 테스팅은 이론적으로는 상당한 연구가 이루어졌지만 현업에서 실제 적용되는 사례는 드문편이다.