페이퍼요약 - 멀티쓰레드 프로그램 테스팅 도구를 위한 프레임워크와 벤치마크 by Eytani

제목: 멀티쓰레드 프로그램 테스팅 도구를 위한 프레임워크와 벤치마크(Toward a Framework and Benchmark for Testing Tools for Multi-Threaded Programs)

저자: Yaniv Eytani 외 3인, 이스라엘

문서유형: 저널 페이퍼(총 13페이지), 2005년

 

현존하는 멀티쓰레드 프로그램 테스팅 기술(기법, 도구, 연구 분야)을 포괄적으로 조사하여 이들을 담을 수 있는 프레임워크를 제시한 자료 

---

현 컨커런트 테스팅 기술

• 멀티쓰레드 프로그램의 품질을 향상시키기 위한 많은 연구가 학계와 산업계에서 진행되어옴
• 특히 발견 및 분석이 어려운 동시성 결함(예, 의도하지 않은 경쟁 상황, 데드락)을 식별하기 위한 기술과 도구 개발이 소프트웨어 테스팅의 중요한 이슈로 부상함
• 기존 솔루션들은 크게 정적 기법(프로그램을 정적으로 분석하여 유용한 정보를 도출)과 동적 기법(프로그램 실행을 동반)으로 구분된다.

1. 정적 기법(Static techniques)

• 정형적 검증(Formal Verification): 모델 체커는 특별한 모델링 언어로 표현된 소프트웨어 모델을 체계적이고(systematic) 완전한(exhaustive) 상태 공간 탐색을 통해 검증하는 도구. 이 모델 체킹이 컨커런트 시스템의 속성(properties)을 검증하는데 활용되며, 속성은 대개 시간 로직(temporal logic)의 불변식(invariants/predicates)이나 공식(formulas)으로 표현된다. 소프트웨어 모델을 수작업으로 생성하는 것을 많은 노력을 요구하고 에러 가능성도 높으므로 자동 또는 반자동으로 모델을 생성할 수 있는 추상화 기법(abstraction techniques) 개발에 연구가 집중됨. 대표적인 예로 FeaVer, Bandera, SLAM, Java PathFinder, BLAST 등이 있음
• 모델 구축 토대로 정적 분석(Static Analysis) 활용: 정적 분석을 통해 도출되는 정보가 검증(verification)을 위한 모델을 구축하는데 기초 정보로 활용됨. 예를 들어, 슬라이싱을 통해 관심 속성과 관련 없는 프로그램 부분을 제거하는 의존성 분석(Dependency analysis), 각 프로그램 구문(program statement)에 의해 업데이트 되는 위치를 판단하는 포인터 분석(Pointer analysis) 등은 각 프로그램 구문이 모델 상태에 미칠 수 있는 영향을 결정하는데 사용된다. 동시적 프로그램에서 Escape analysis는 어떤 변수가 쓰레드 로컬(thread-local)이고 어떤 변수가 공용(shared)인지를 결정하는데 사용되며, 이 정보는 모델을 최적화하거나 동적 테스팅 기법에서 사용되는 인스트루멘테이션을 배치(placement)하는데 사용될 수 있다.
• 검증 및 결함 발견을 위해 정적 분석(Static Analysis) 활용: 특정 동시성 관련 속성을 검증하기 위한 특수한 정적 분석 도구가 개발됨. 예를 들어, 데이터 경쟁(또한 데드락)을 발견하기 위한 특화된 타입 시스템(type systems), 데이터 흐름 분석기(data-flow analyzers), 정적 충돌 분석기(Static conflict analysis)가 존재함. 타입 시스템은 프로그래머가 프로그램에 주석(annotations)을 제공 할 것을 요구하며, 만약 프로그램 설계가 타입 시스템에 인코딩된 설계 패턴과 일관되지 않으면 가짜 경보(false alarms)를 생성한다. TVLA은 동시성을 모델링 할 수 있고 동시적 프로그램의 다양한 속성을 엄격하게 검증할 수 있는 정적 분석 프레임워크이지만 분석 비용이 상대적으로 높아서 규모가 작은 프로그램으로 적용 범위가 제한된다.

2. 동적 테스팅 기술(Dynamic testing technologies)

여기서 언급되는 모든 동적 테스팅 기법이 인스트루멘테이션 기술(instrumentation technology)을 활용함. 인스트루멘터(instrumentor)는 원래의 프로그램(소스 또는 오브젝트)을 입력으로 받아서 추가 삽입한 구문을 통해 여러 다른 위치에서 해당 프로그램을 계측(instruments)하는 도구이다. 즉, 프로그램 실행 동안에 인스트루멘터에 의해 끼워 넣어진 인스트럭션(instructions)이 실행된다. 

• 노이즈 생성기(Noise makers): 다양한 타이밍 시나리오를 유발하여 테스트가 실패하도록 만드는 노력을 하는 도구(결과적으로 버그가 발견될 확률을 높이고 테스팅 효율성을 증가시킴). 순차적 프로그램에서 이런 유형의 도구는 대개 애플리케이션의 특정 서비스를 부인하는 방식으로 작동한다(예, 메모리 할당 요청에 대해 가용 메모리가 없다고 알림). 순차적 분야에서는 프로그램이 우아하게 실패하는지(즉, 장애 발생 시 프로그램을 의도한 특정 상태로 만들고 정상적으로 종료시킴)를 검증하는데 주로 사용되지만, 동시적 프로그램에서는 테스트가 계속해서 정확하게 수행되는지를 체크하기 위하여 각 테스트 실행에서 여러 다른 합법적인 인터리빙이 등장하도록 만든다(어떤 의미에서는 노이즈 생성 도구가 다른 가능한 스케쥴러의 동작을 시뮬레이션 한다고 볼 수 있음). 프로그램 실행 동안에 노이즈 휴리스틱(noise heuristic)이 인스트루멘터에 의해 편입된 호출(calls)을 수신하고, 임의적으로(또는 특정 통계치나 커버리지에 기반하여) 일종의 지연(delay)이 필요한지를 결정한다.
• 경쟁 상황 및 데드락 발견(Race and deadlock detection): 서로간의 시간적 동기화 구문(synchronization statement)이 없는 두 개 쓰레드(적어도 하나가 write)가 하나의 변수로 접근하는 경쟁 상황은 버그의 징후로 여겨진다. 경쟁 상황 식별기(Race detectors)는 경쟁 상황이 존재하는지 증거를 찾는 도구이다(온라인 또는 오프라인으로 수행됨). 대개 경쟁 상황 식별기는 정보가 수집될 수 있도록 먼저 코드를 인스트루멘테이션하고 이어서 수집된 정보를 처리하는 방식으로 작동한다. 온라인 경쟁 상황 식별은 애플리케이션 속도 저하 등의 성능 문제가 생길 수 있으며, 오프라인 경쟁 상황 식별은 거대한 양의 추적 정보(traces)가 생성되는 단점이 있다. 모든 유형의 경쟁 상황 식별기에서 나타나는 주요 문제점은 너무 많은 가짜 경보(false alarms)가 생성되고 스케쥴링 순서에 민감하다는 점이다. 데드락은 한 쓰레드 집합에서 쓰레드들이 다른 쓰레드가 이미 점유한 자물쇠를 획득하려 함에 따라 더 이상의 진전이 멈추어버린 상태로, 데드락의 증거를 찾기 위해 traces를 검토하는 도구가 존재한다. 구체적으로 자물쇠 그래프(lock graphs)에서 순환(cycles)이 존재하는지를 찾는다.
• 재현(Replay): 동시적 테스팅의 가장 성가신 특징 중 하나가 일단 버그가 발견되어도 디버그 하기가 매우 어려울 수 있다는 점이다. 즉, 버그의 재현 확률이 높지 않으며, 재현이 된다 하더라도 디버거나 출력 구문(print statements)을 사용하여 분석을 시도하면 사라져버린다. 따라서 디버깅을 위해서는 테스트를 재현(replay)하는 능력이 필수적임. 재현 도구는 기록(record)과 재생(playback)의 두 단계를 가진다. 기록 단계에서 타이밍과 프로그램의 다른 “임의적(random)” 의사결정에 대한 정보가 기록되고, 재생 단계에서는 테스트가 실행되며 재생 메커니즘(replay mechanism)은 이전 테스트와 동일한 의사결정이 취해지도록 보장한다.
• 커버리지(Coverage): 멀티쓰레딩 분야에서는 구문 커버리지(statement coverage) 같은 전통적인 커버리지 측정이 별로 유용하지 않음. 유망한 멀티쓰레드 커버리지 모델로는 버그 패턴을 커버하는 모델을 생성하거나(예, 경쟁 상황이 발생할 수 있는 변수를 체크하고 테스팅에 포함) 또는 각 동기화 구문이 테스트 흐름에 영향을 주는지를 체크하는 동기화 커버리지 등이 있다(이 두 커버리지 모델은 ConTest에서 구현됨). 이 외에도 추가적인 커버리지 생성이 필요하고 버그 발견과의 연관성도 연구될 필요가 있다.
• 체계적 상태 공간 탐색(Systematic state space exploration): 자동 테스트 생성, 실행, 평가를 단일 도구에 통합하는 기술. 이 도구는 여러 동시적 컴포넌트로 구성된 시스템의 상태 공간을 컴포넌트의 실행을 통제하고, 관측하고, 재초기화(reinitializing) 하여 체계적으로 탐색한다. 이 도구들은 대개 데드락이나 사용자 정의 어써션(user-specified assertions) 위반 사례를 찾으며, 상태 공간 탐색 중에 에러가 발견될 때마다 해당 에러 상태를 야기한 시나리오를 저장한다(이 시나리오는 차후 재생 가능). 

제안된 프레임워크

• 아래 그림은 여러 다른 컨커런트 테스팅 기술 간의 상호작용을 위해 설계된 모델이다. 여러 다른 기술이 관측 데이터베이스(observation database)를 통해 서로 의사소통 할 수 있으며, 인스트루멘테이션은 동적 박스(dynamic box)와 추적 평가 박스(trace evaluation box)에 포함된 모든 기법들을 가능하게 하는 기반 기술이다. 대표적인 인스트루멘테이션 기술로 AspectJ가 있음
• 관측 데이터베이스를 통해 어떤 것도 공유하지 않은 독립적인 기술들도 일부 존재함(예, cloned 테스트의 커버리지 측정)
• 이 프레임워크는 여러 기술들을 적절히 조합하여 사용하면 추가적인 가치 창출이 가능함을 보여준다.

[다른 기술간의 상호작용]

관측 데이터베이스(The observation database)에는 아래와 같은 정보가 포함된다(부분적 제안):

• 관심 변수(Interesting variables): 경쟁 상황 또는 버그에 관여할 수 있는 변수
• 가능한 경쟁 상황 위치(Possible race locations): 프로그램에서 의심이 되는 위치
• 중요하지 않은 위치(Unimportant locations): 잘 동기화 된 영역(예, 단 하나의 쓰레드만 살아 있는 영역)
• 커버리지 정보(Coverage information): 어떤 커버리지 태스크가 커버되었는지 보여줌
• 실행 추적 정보(Traces of executions): 오프라인 분석기(off-line analyzers)에 의해 사용됨