문서요약 - GrammaTech 정적 분석기를 통한 동시성 에러 발견 by GrammaTech

제목: GrammaTech 정적 분석기를 통한 동시성 에러 발견(Finding Concurrency Errors with GrammaTech Static Analysis)

저자: GrammaTech, 미국

문서유형: 기술 화이트 페이퍼(총 8페이지)

 

멀티쓰레드 프로그램에 특정적인 동시성 버그를 설명하고, 이런 버그를 찾고 발생 가능성을 줄이는데 도움이 되는 도구인 CodeSonar 정적 분석기를 소개한 자료 

---

멀티쓰레딩으로 인한 개발 복잡성 증가

• 여러 오퍼레이션이 동시에 실행될 수 있을 때 모든 면에서 복잡성이 증가함. 특히 다수의 쓰레드에 있는 인스트럭션들이 인터리브(interleaved) 될 수 있다는 점이 복잡성을 크게 증가시킴
• 대개 가능한 인터리빙 수가 매우 크며 인스트럭션 수가 증가함에 따라 막대하게 증가한다. 이런 현상은 ‘조합 폭발(combinatorial explosion)’로 알려짐
• 쓰레드 A가 M개 인스트럭션을 실행하고 쓰레드 B가 N개 인스트럭션을 실행할 때, 이 두 쓰레드의 가능한 인터리빙 수는 이다. 아래 그림 예 참조

[각각 2개 인스트럭션을 가진 2개 쓰레드에 6가지 인터리빙이 가능]

[각각 3개 인스트럭션을 가진 2개 쓰레드에 20가지 인터리빙이 가능]

멀티쓰레드 프로그램 테스팅의 어려움

• 실제 소프트웨어에서 가능한 인터리빙 수는 천문학적인 숫자를 보이므로 모든 인터리빙을 완전하게 테스트 하는 것이 불가능
• 더구나 인터리빙 결정이 시스템 스케쥴러에 의해 이루어지므로 프로그래머나 사용자의 통제 밖이다. 즉, 개발자의 의도 하에 특정 실행에서 특정 인터리빙이 일어나도록 만드는 것이 매우 어려움
• 멀티쓰레드 프로그램에 존재하는 불확정성(nondeterminism)은 전통적인 소프트웨어 테스팅의 효과성을 크게 저하시킴. 단일 쓰레드 프로그램에서는 어떤 결함을 일관되게 드러나게 하는 테스트를 작성할 수 있지만, 멀티쓰레드 프로그램에서는 불확정적 인터리빙 때문에 하나의 테스트가 여러 다른 동작을 보일 수 있다. 따라서 주어진 프로그램 실행(run)에서 특정 동작이 발생하도록 하는 것이 어렵거나 불가능하다. 

동시성 버그(Concurrency bugs)

1. 데이터 경쟁(Data Race)

• 단일 쓰레드 환경에서는 존재하지 않는 종류의 문제
• 다수의 실행 쓰레드가 공용 데이터에 접근 시 이 중 적어도 하나가 접근을 분리하는 분명한 동기화 오퍼레이션 없이 데이터 값을 변경할 때 발생(두 쓰레드의 인터리빙에 따라 시스템이 일관성 없는 상태로 남겨질 수 있음)
• 데이터 경쟁은 발견되지 않은 채 무기한으로 잠복해 있다가 흔하지 않은 상황에서만 드물게 모습을 드러내기 때문에 진단 및 재현이 어렵다.
  - 잘 테스트되고 전개된 소프트웨어에서 나타나는 에러는 종종 데이터 경쟁이 그 근원이다.
  - 모습을 드러냈더라도 그 이상 증상이 일관되게 나타나지 않기 때문에 개발자가 종종 데이터 경쟁 관련 버그 보고를 ‘재현불가능(unreproducible)’으로 여겨 폐기한다.

아래 그림은 간단한 데이터 경쟁의 예이다.

• 입구 센서와 출구 센서가 있는 제조 조립 라인에서 현재 라인상에 있는 아이템 숫자를 관리함. 즉, 라인에 아이템이 들어올 때 마다 입구 센서 컨트롤러가 count를 증가시키고, 아이템이 라인의 끝에 도달할 때 마다 출구 센서 컨트롤러가 count를 감소시킨다.
• 컴퓨터에 구현된 count 증가 오퍼레이션과 감소 오퍼레이션은 먼저 메모리로부터 count 값을 로드하고, 이를 국소적으로(locally) 수정하고, 최종적으로 메모리에 다시 저장한다.
• 이 업데이트 트랜잭션이 적절한 보호책(safeguards) 없이 멀티쓰레드 시스템에서 실행되는 경우, 컨트롤러가 공용 데이터 부분인 count에 읽기(read)와 쓰기(write)를 할 수 있으므로 데이터 경쟁이 발생할 수 있다.
• 아래 그림에서는 부정확한 값인 69가 결과로 나왔으며, 인터리빙이 어떻게 발생하는지에 따라 또 다른 부정확한 집계인 71이 되거나 정확한 값인 70이 산출되기도 함(결과 값이 정확하게 나오다가 가끔은 값이 너무 높거나 또는 낮게 나오다 보니 멀티쓰레드 프로그래밍 문제에 익숙하지 않은 프로그래머를 당혹하게 만들고 원인을 찾느라 많은 시간과 노력을 소비하게 함)

[데이터 경쟁 예: 조립 라인에서 아이템 수가 부정확하게 집계 됨]

데이터 경쟁을 피하기 위해 흔히 사용되는 기법으로 자물쇠(locks), 세마포어(semaphores), 메시지 전달(message passing) 등이 있지만 이 기법들도 아래와 같은 나름의 문제를 가져온다.

• 코드의 크기와 복잡성을 증가시켜 더 이해하기 어렵게 만듬
• 부정확하게 사용되는 경우는 프로세스 또는 전제 프로그램의 진행을 막는 결과를 낳음. 즉, 데드락(deadlock)이나 기아 현상(starvation) 같은 또 다른 문제로 이어질 수 있음
• 불필요하게 사용된 경우 쓸데없이 속도(성능)를 저하시키는 결과를 낳음
• 필요한 곳에서 실수로 생략된 경우는 보호를 제공하는데 실패

2. 데드락(Deadlock)

• 둘 또는 그 이상의 쓰레드가 서로가 필요로 하는 자물쇠(lock)을 점유하고 있어서 상대의 진전을 방해함
• 아래는 2개의 공용 변수를 보호하기 위해 사용된 2개 자물쇠에서 데드락이 발생하는 예를 보여준다. 이 예에서 다수의 조립 라인이 현재 조립 중인 아이템 총 수를 나타내는 count와 품질 통제에 실패한 완료 아이템 수를 기록한 bad_items을 공유함
• 한 쓰레드가 count에 대한 자물쇠를 확보하고 또 다른 쓰레드는 bad_items에 대한 자물쇠를 확보함에 따라 이 두 쓰레드가 필요한 두 번째 자물쇠를 얻는 것이 불가능하게 됨. 즉, 양쪽 쓰레드 모두 자신의 오퍼레이션을 수행할 수 없게 되면서 이미 확보한 자물쇠를 절대 풀지 않게 되고 결과적으로 두 쓰레드가 완전히 막히게 됨

[두 쓰레드 간의 데드락: 양쪽 쓰레드 모두 진전 불가능]

3. 프로세스 기아 현상(Process Starvation)

• 쓰레드가 다른 쓰레드에 의해 장시간 점유된 자물쇠(lock)을 기다리고 있으면 굶주리게 된다. 예) 특정 자물쇠를 점유한 쓰레드가 대규모 디스크 읽기 또는 네트워크로부터 데이터 도착 같은 이벤트를 기다리는 중임
• 앞에 나온 제조업 자동화 시스템 예에 정기적인 감사 쓰레드(audit thread)가 포함된다고 가정. 감사 쓰레드는 현재 count 수가 (라인에 진입한 총 아이템 수 - 빠져나간 총 아이템 수)와 일치하는지 확인하기 위해 모든 입구 및 출구 기록을 검토함. 이 감사 쓰레드는 count와 모든 센서에 대한 자물쇠를 확보할 필요가 있으며, 따라서 모든 업데이트는 감사 쓰레드가 완료되기를 기다려야만 한다.
• 만약 감사 쓰레드가 너무 오래 실행되면 업데이트가 크게 지연될 수 있으며 심지어는 미해결 업데이트 쓰레드가 미처 진행되기 전에 그 다음 감사 쓰레드가 또 다시 모든 자물쇠를 획득하여 실행을 시작할 수도 있다. 최악의 경우 일부 또는 모든 업데이트가 절대 실행 기회를 얻지 못하게 될 수도 있다.

GrammaTech 사의 CodeSonar 정적 분석기

• CodeSonar는 동시적 프로그램에서 발생할 수 있는 문제를 식별하고 제거하는 것을 지원하는 여러 체커를 포함한다. 예) Data Race 분석
• CodeSonar는 이미 포함되어 있는 체커 외에도 엔지니어가 프로젝트에서 사용된 특정 동기화 기법이나 특정 소프트웨어 결함을 겨냥한 자신만의 체크(custom checks)를 추가할 수 있도록 확장된 API(CodeSonar Extension API)를 제공한다.
• CodeSonar는 다수의 가능한 실행 경로와 인터리빙을 파악하기 위해 '기호 실행(symbolic execution)' 기법을 사용하며, 프로그램의 실행 없이 동시성 에러를 발견하여 멀티쓰레드 소프트웨어 검증에 중요한 역할을 한다(테스팅에서는 채워질 수 없는 부분을 커버해줌)
• 데이터 경쟁 체크: CodeSonar는 공용 메모리(shared memory locations)로의 접근 패턴을 검토하여 데이터 경쟁을 식별하고 Data Race 경고를 발행한다.
• 데드락 체크: 동일한 자물쇠가 다른 쓰레드에 의해 다른 순서로 획득될 수 있는 경우 Conflicting Lock Order 경고를 발행함으로써 데드락 위험에 처한 소프트웨어 식별을 돕는다.
• 기아 현상 체크: 특정 자물쇠를 점유하는 쓰레드에 의해 호출되는 모든 프로시져 집합을 검토하여 기아 현상을 식별하도록 돕는다. 예를 들어, 기능 f()가 다른 쓰레드를 막거나 긴 실행 시간을 가지는 것으로 알려져 있다면, f()가 하나 또는 여러 자물쇠를 점유한 쓰레드에 의해 호출될 때마다 경고를 발행하는 체커를 엔지니어가 구축하여 추가할 수 있다.
• 동기화 기법을 효과적으로 사용하는 코드를 작성하는 것은 쉽지 않으며, 따라서 코딩 표준은 종종 어떤 상황에서 어떤 기법을 사용할 수 있는지에 대한 제한을 가한다. 예를 들어, “C 언어에 대한 JPL 코딩 표준(JPL Institutional Coding Standard for the C Programming Language)”은 태스크 동기화(task synchronization)를 위해 태스크 지연 기능(task delay functions)을 사용하는 것을 허용하지 않음. CodeSonar는 JPL 코딩 표준을 위한 체크들을 포함하며, 그 중 하나인 Task Delay Function 체크는 동기화 목적으로 사용된 태스크 지연 기능이 식별될 때 마다 경고를 발행한다.