2014/06/18 18:39

第10章 著名な脆弱性対策
バッファオーバーフロー: #4 あふれを検出するデバッグ

領域あふれの問題の検出については、ロジックが複雑に入り組んでいる場合、ソースコードから見いだすのは容易でない。そのような場合、デバッガ等のツールの下で対象のプログラムを動かして、問題を見つけ出すことになる。

スタックおよびヒープにおけるあふれを検出するためのコンパイラのオプションやデバッグ・ツールがいくつか存在する。

次にその主なものを紹介する。

あふれの検出
図10-4: あふれの検出

あふれの検出等に使うことのできるデバッグ・ツール

ヒープにおける領域あふれやダブルフリー等の問題を検出できるツールをふたつ紹介する。ひとつは独立したツール、もうひとつは統合開発環境の中の機能である。

(1) Valgrind [GNU/Linux]

ヒープデバッガを中心とした GNU/Linux 専用のツールスイートである。割当領域外への書き込みや、メモリリークを検出することができる。

Valgrind が備えるツールには、下記のようなものがある。

  • Memcheck
    最も主要なツール、ヒープデバッガ。動的メモリに関わる諸問題を検出する(領域外のアクセス、未初期化領域の参照、不正free、メモリリーク、重複領域のmemcpy)
  • Cachegrind
    キャッシュプロファイラ。CPUキャッシュをエミュレートし、使用状況を調べることができる
  • Callgrind
    Cachegrind プラス呼び出しグラフ生成
  • Massif
    ヒーププロファイラ
  • Helgrind
    スレッドデバッガ ほか
例: Valgrind の Memcheck
対象プログラムをデバッグモード(gcc -g 等)でコンパイルしてあると、Valgrindは問題とともにソースコード位置も知らせてくれる。
   1: $ valgrind --tool=memcheck --leak-check=yes test_program
...
			↓≪≪実行途中における、 malloc()した領域からのあふれの検出≫≫
   8: ==1929== Invalid write of size 1
   9: ==1929==    at 0x8048970: header_getContentType (test_program.c:110)
  10: ==1929==    by 0x8049A58: block_processHeader (test_program.c:586)
  11: ==1929==    by 0x8049EA6: block_processField (test_program.c:673)
  12: ==1929==    by 0x8049F80: main_processBlock (test_program.c:712)
  13: ==1929==  Address 0x1BA4B4B2 is 0 bytes after a block of size 434 alloc'd
  14: ==1929==    at 0x1B904DF0: malloc (vg_replace_malloc.c:131)
  15: ==1929==    by 0x8048930: header_getContentType (test_program.c:106)
  16: ==1929==    by 0x8049A58: block_processHeader (test_program.c:586)
  17: ==1929==    by 0x8049EA6: block_processField (test_program.c:673)	
  18: ==1929==
...

			↓ ≪≪プログラム終了時、メモリリークの検出≫≫
1048: ==1929== 60907 bytes in 134 blocks are definitely lost in loss record 12 of 12
1049: ==1929==    at 0x1B904DF0: malloc (vg_replace_malloc.c:131)
1050: ==1929==    by 0x8048930: header_getContentType (test_program.c:106)
1051: ==1929==    by 0x8049A58: block_processHeader (test_program.c:586)
1052: ==1929==    by 0x8049EA6: block_processField (test_program.c:673)
1053: ==1929== 

			↓ ≪≪メモリリークのサマリ≫≫
1054: ==1929== LEAK SUMMARY:
1055: ==1929==    definitely lost: 60907 bytes in 134 blocks.
1056: ==1929==    possibly lost:   334 bytes in 1 blocks.
1057: ==1929==    still reachable: 1512 bytes in 14 blocks.
1058: ==1929==         suppressed: 0 bytes in 0 blocks.

参照URL http://valgrind.org/

(2) Application Verifier [Visual Studio 2005, Windows]

領域あふれの検出に使うことはできないが、Visual Studio に備わっているApplication Verifier(日本語名「アプリケーションの検証」)は、Visual C++ のデバッガとともに動作させると、ヒープのダブルフリー等の不具合を検出してくれるものである。

他にも、ハンドルの検証やロックの検証等の機能がある。

参照URL http://www.microsoft.com/japan/msdn/vstudio/

あふれを検出できるランタイム・ライブラリの機能

通常のランタイムライブラリの代わりに、領域あふれ等を検出する能力が組み込まれたライブラリをプログラムにリンクしてデバッグを行う方法がある。

(1) Mudflap [GCC]

バッファオーバーフロー、メモリリーク、ポインタの誤使用等を実行時に検出してくれるライブラリおよびGCCのコンパイルオプション。

Valgrind に比べて、解析速度が速く、stack, data, bss 変数のチェックが行えるが、コンパイルオプションとライブラリの追加オプションが必要である。

GCCオプション: -fmudflap -lmudflap
マルチスレッドの場合のGCCオプション: -fmudflapth -lmudflapth


プログラム example3.c
 1 #include <string.h>
 2 
 3 sub () {
 4     char c8[8];
 5     strcpy(c8, "1234567890");
 6 }
 7
 8 main () {
 9     sub();
10 } 
コンパイルするコマンドの例
cc -fmudflap -lmudflap example3.c -o example3
実行例
$ ./example3
*******
mudflap violation 1 (check/write): time=1167124492.737106 ptr=0xbff80720 size=11
pc=0x5d5f9d location=`(strcpy dest)'
      /usr/lib/libmudflap.so.0(__mf_check+0x3d) [0x5d5f9d]
      /usr/lib/libmudflap.so.0(__mfwrap_strcpy+0x158) [0x5e2368]
      ./example3(sub+0x3c) [0x8048630]
Nearby object 1: checked region begins 0B into and ends 3B after
mudflap object 0x8fb2588: name=`example3.c:4 (sub) c8'
bounds=[0xbff80720,0xbff80727] size=8 area=stack check=0r/3w liveness=3
alloc time=1167124492.700013 pc=0x5d59dd
number of nearby objects: 1

環境変数 MUDFLAP_OPTIONS を設定すると次のようなこともできる。

・Mudflapを一時的に無効にする

$ MUDFLAP_OPTIONS="-mode-nop" ./example3

・タイムスタンプとバックトレースを止める

$ MUDFLAP_OPTIONS="-no-timestamps -backtrace=0" ./example3
タイムスタンプとバックトレースを止めて実行した例
$ MUDFLAP_OPTIONS="-no-timestamps -backtrace=0" ./example3
*******
mudflap violation 1 (check/write): time=1167124513.569876 ptr=0xbff0d680 size=11
pc=0xd31f9d location=`(strcpy dest)'
Nearby object 1: checked region begins 0B into and ends 3B after
mudflap object 0x9f7d5f0: name=`example3.c:4 (sub) c8'
bounds=[0xbff0d680,0xbff0d687] size=8 area=stack check=0r/3w liveness=3
alloc time=0.000000 pc=0xd319dd
number of nearby objects: 1

参照URL http://gcc.gnu.org/wiki/Mudflap_Pointer_Debugging

(2) MALLOC_CHECK_ [glibcを制御する環境変数]

MALLOC_CHECK_ は、glibc(GNU C Library)がもつ malloc() - free() 関連のチェック機能を活性化させる環境変数である。この環境変数に値を定義すると、malloc() で割り当てたメモリブロックの簡単な保護と異常検出の機能がはたらき、free() 関数が呼び出されたときに次の問題が生じていないかのチェックが行われるようになる。

  • malloc() で割り当てたブロックの手前のメモリの4バイト分のどこかが不正な値で上書きされていないか
  • malloc() で割り当てたブロックの後続のメモリ1バイト分が不正な値で上書きされていないか
  • すでに free() されたポインタを再度 free() しようとしていないか

環境変数 MALLOC_CHECK_ に設定された値に応じ、glibc は次のように振る舞う。

  • MALLOC_CHECK_=0 上記の問題でプログラムに異常をきたすのを防ぐが報告はしない
  • MALLOC_CHECK_=1 問題を検出してメッセージを出す
  • MALLOC_CHECK_=2 問題を検出してプロセスをアボートさせる
  • MALLOC_CHECK_=3 1 と 2 の両方を行う

参照URL http://www.gnu.org/software/libc/manual/html_node/Heap-Consistency-Checking.html

(3) -D_FORTIFY_SOURCE=n [GCC, glibc]

C言語の標準ランタイム関数を使用するプログラムの実行がよりセキュアに行われるよう、マクロの仕組みを用いて呼び出すライブラリ関数をより堅固なバージョンに置き換えるglibc(GNU C Library)の機能である。

1) 呼び出すライブラリ関数を切り替えるオプション

GCC にコンパイルオプション -D_FORTIFY_SOURCE=1 あるいは =2 を指定すると、あふれを起こしやすい strcpy() のような関数がマクロ展開によって同様な処理を行うが領域あふれを検査するよう対策された別の関数 __strcpy_chk() に置き換わる。
プログラム実行時にあふれ等の問題が検出されたときは、プロセスの実行が abort()によって中止される。

この方法を使うと、ソースコードを変更する必要がなく、コンパイルのし直しのみであふれ検出機能をはたらかせることができる。

GCCに指定するオプション: -O1 -D_FORTIFY_SOURCE=1 または =2

この機能を使用するときは、コンパイラの最適化オプションを -O1 またはそれ以上のレベルで指定する必要がある。


プログラム example1.c
1 #include <stdio.h>
2 main () {
3 	char buf[4];
4 	gets (buf);
5 	puts (buf);
6 }
コンパイルと実行の例
$ gcc -O1 -D_FORTIFY_SOURCE=2 example1.c -o example1
$ ./example1
aaaa
*** buffer overflow detected ***: ./example1 terminated
======= Backtrace: =========
/lib/libc.so.6(__chk_fail+0x41)[0x464d7161]
/lib/libc.so.6(__gets_chk+0x174)[0x464d70c4]
./example2[0x804840d]
/lib/libc.so.6(__libc_start_main+0xdc)[0x4640bf2c]
./example2[0x8048351]
======= Memory map: ========
00651000-00652000 r-xp 00651000 00:00 0          [vdso]
08048000-08049000 r-xp 00000000 fd:00 914420     /home/test/example2
08049000-0804a000 rwxp 00000000 fd:00 914420     /home/test/example2
0947a000-0949b000 rwxp 0947a000 00:00 0 
45a27000-45a40000 r-xp 00000000 fd:00 948678     /lib/ld-2.5.so
    ...省略...
bfa0c000-bfa22000 rw-p bfa0c000 00:00 0          [stack]
アボートしました
$

2) コンパイル時にも問題を検出

判断が可能な場合にはコンパイル時にもあふれの警告が出力される。


プログラム example2.c
1 #include <string.h>
2 main () {
3 	char c8[8];
4 	strcpy (c8, "1234567890");
5 }

3) 運用における使用

-D_FORTIFY_SOURCE によって導入されるチェックロジックのオーバーヘッドは比較的小さいと言われている。デバッグ時のみならず、プログラムのリリース後もこのオプションを使用することによって攻撃に備えるのもひとつの方法である。

(4) /RTCs [Visual Studio 2005, Windows]

スタック上の変数領域のあふれを実行時に検出してくれる、Visual C++ のコンパイルオプション。

文字型配列(char[ ])のみならず、スタック上のすべての変数を検査してくれるのが特徴である。変数の大きさが1バイトしかなくても、型がintやポインタであってもあふれが検査される。

あふれを検出するのに使われる方法は、変数ひとつひとつの前後に 0xCCCCCCCC の値をもつ4バイトのワードが置かれ、これが壊れていないか、関数からのリターン時に調べるというものである。この /RTCs の検査は、/GS のスタック破壊検査よりも先に行われる。


プログラム
func () {
   int	i;
   char	c16[16];
   char	*p;
   int	j;

   i = 0x11111111;
   memset (c16, 0x22, sizeof(c16));
   p = 0x33333333;
   j = 0x44444444;
   c16[16] = 0xFF;
   return 0;
}
func() 関数からリターンする直前のスタックの内容
0x0012FE20  cccccccc cccccccc cccccccc cccccccc  フフフフフフフフフフフフフフフフ
0x0012FE30  cccccccc cccccccc 44444444 cccccccc  フフフフフフフフDDDDフフフフ
                              ↑int  j
0x0012FE40  cccccccc 33333333 cccccccc cccccccc  フフフフ3333フフフフフフフフ
                     ↑char *p
0x0012FE50  22222222 22222222 22222222 22222222  """"""""""""""""
                     ↑char c16[16]
0x0012FE60  ccccccff cccccccc 11111111 cccccccc  .フフフフフフフ....フフフフ
                  **          ↑int i
0x0012FE70  9bbfcf2a 0012ff48 004114a3 00000000  *マソ・H...」.A.....
0x0012FE80  00000000 7ffdf000 cccccccc cccccccc  .....・..フフフフフフフフ
0x0012FE90  cccccccc cccccccc cccccccc cccccccc  フフフフフフフフフフフフフフフフ

※ c16[ ] の前後に 0xcc 以外が書き込まれていることがあふれとして検出される

参照URL http://www.microsoft.com/japan/msdn/vstudio/

저작자 표시 비영리 변경 금지
Posted by code쟁이 RosaGigantea
2014/06/18 18:00
출처 : http://studyfoss.egloos.com/5278709
gcc: 4.4.3



mudflap 라이브러리는 gcc 내에 포함된 메모리 검사 기능으로
포인터를 통한 메모리 접근 시 이를 검사하는 코드를 원래의 코드 내에 직접 삽입하는 방식이다.
mudflap은 gcc와 통합되어 있기 때문에 코드를 생성하는 과정 내에서
포인터를 통한 메모리 접근을 인식하면 자동으로 그에 대한 검사 코드를 만들 수 있다.

기본적인 동작 방식은 미리 할당된 메모리 영역에 대한 정보를 등록하여 데이터베이스를 구성해 두고
포인터를 이용한 메모리 접근 시 등록된 메모리 영역에 대한 접근인지를 체크하는 식이다.

전역 변수 및 문자열 상수, 명령행 인자, 환경 변수 등은 프로그램 실행 시작 시 자동으로 등록되며
스택 변수의 경우 해당 block에 진입/탈출 시 동적으로 등록/해제된다.
help 변수의 경우도 heap 할당 함수를 (malloc, calloc 등) wrapping하여
해당 영역에 대한 정보를 등록하도록 되어 있다.

이러한 등록 과정은 __mf_register() 함수가 수행하는데
기본적으로 메모리 영역의 시작 주소, 크기, 객체 타입, 이름 등의 정보가 저장된다.
여기서 객체 타입은 heap, stack, static 등을 구분하기 위한 정수값이며
객체 이름은 "파일명:줄번호:행번호 (함수명) 변수명"의 형태이다.

간단한 예제를 살펴보기로 하자.

#include <stdio.h>

int main(void)
{
  char buf[16];
  char msg[] = "Hello mudflap!";
  char *p = msg;
  p[-1] = '\0';
  return 0;
}


p 변수는 원래의 msg 영역을 벗어난 메모리 영역에 접근했다.
이 경우 사실은 msg 아래에는 buf가 할당되어 있으니 메모리 자체로는 접근이 가능한 구역이긴 하다.
하지만 mudflap은 코드에서 buf에 접근하지 않았으므로 buf를 등록하지 않기 때문에
이러한 종류의 메모리 접근도 오류로 잡아낼 수 있다.

mudflap을 이용하도록 컴파일하려면 -fmudflap 옵션을 추가해야 한다.
(multi-thread 프로그램에서 이용할 경우에는 mudflapth 옵션을 대신 이용해야 한다.)
이에 관련된 builtin spec들을 살펴보면 다음과 같다.

*cpp_unique_options:
    %{fmudflap:-D_MUDFLAP -include mf-runtime.h}
    %{fmudflapth:-D_MUDFLAP -D_MUDFLAPTH -include mf-runtime.h} 

*cc1_options:
    %{fmudflap|fmudflapth:-fno-builtin -fno-merge-constants}

*mfwrap:
    %{static: %{fmudflap|fmudflapth:  --wrap=malloc --wrap=free --wrap=calloc --wrap=realloc
                                      --wrap=mmap --wrap=munmap --wrap=alloca}
        %{fmudflapth: --wrap=pthread_create}}
    %{fmudflap|fmudflapth: --wrap=main}

*mflib:
    %{fmudflap|fmudflapth: -export-dynamic}

*link_command:
    %(mfwrap) %(link_libgcc) %o %(mflib)


cpp 실행 시에는 _MUDFLAP 매크로를 정의하고 mf-runtime.h 파일을 #include한다.
cc1 실행 시에는 문자열/메모리 관련 함수들을 최적화하지 않고 mudflap을 통하여 실행하기 위해
builtin 함수를 사용하지 않도록 하고 동일한 문자열 상수로 별도로 관리하기 위해 병합하지 않는다.
링크 시에는 main 함수를 wrapping하기 위해 실행 파일 내의 심볼들도 dynamic symbol table을 통해 공개하며
특히 static 빌드 시에는 동적 메모리 함수들도 관리하기 위해 모두 wrapping한다.

다음과 같이 컴파일 후 실행하면 아래와 같은 메시지를 출력할 것이다.
(-fmudflap 옵션을 주고 맨 뒤에 -lmudflap을 링크하도록 지정해야 한다.)
우분투의 경우 libmudflap0 와 libmudflap0-dev 패키지를 설치하면 테스트해 볼 수 있다.

$ gcc -fmudflap test.c -lmudflap
$ ./a.out
*******
mudflap violation 1 (check/write): time=1269503302.202747 ptr=0xbfb80bdc size=1
pc=0xb77a2d6d location=`test.c:8:3 (main)'
      /usr/local/lib/libmudflap.so.0(__mf_check+0x3d) [0xb77a2d6d]
      ./a.out(main+0xcf) [0x80488d3]
      /usr/local/lib/libmudflap.so.0(__wrap_main+0x49) [0xb77a2569]
Nearby object 1: checked region begins 1B before and ends 1B before
mudflap object 0x8627588: name=`test.c:6:8 (main) msg'
bounds=[0xbfb80bdd,0xbfb80beb] size=15 area=stack check=0r/0w liveness=0
alloc time=1269503302.202732 pc=0xb77a250d
number of nearby objects: 1


메시지는 메모리 쓰기 접근 시 오류가 났음을 보여주며 (check/write)
접근 주소 및 크기와 소스 코드에서의 위치까지 표시해 준다.
그 아래는 stack backtrace 정보를 출력한 것이다.
그 아래는 접근한 영역의 근처에 있는 등록된 메모리 영역 정보를 표시하는 것으로
1 바이트 뒤에 "test.c:6:8 (main) msg" 객체가 있다는 것을 보여준다.
해당 객체의 메모리 위치는 bounds 속성에서 볼 수 있고, 객체 타입(area)은 stack이다.

그럼 mudflap은 어떻게 스택에 할당된 메모리 영역을 관리할 수 있을까?
가장 기본적으로는 포인터에 대한 대입 (assignment) 연산이 일어나는지 확인한 후
해당 (즉, 포인터에 대입된) 메모리 영역을 __mf_register() 함수로 등록하는 것이다.

gcc는 코드 생성 과정에서 포인터를 통한 스택 접근을 확인하면
다음과 같은 식으로 (C++의 예외 처리 방식을 이용하도록) 코드를 변경한다.
위에서 코드 컴파일 시 -fdump-tree-mudflap1 옵션을 주면 이 과정을 볼 수 있다.

$ gcc -fmudflap -fdump-tree-mudflap1 test.c -lmudflap
$ cat test.c.008t.mudflap1 

;; Function main (main)

main ()
{
  char * D.1297;
  int D.1298;
  char buf[16];
  char msg[15];
  char * p;

  try
    {
      __mf_register (&msg, 15, 3, "test.c:6:8 (main) msg");
      msg = "Hello mudflap!";
      p = &msg;
      D.1297 = p + -1;
      *D.1297 = 0;
      D.1298 = 0;
      return D.1298;
    }
  finally
    {
      __mf_unregister (&msg, 15, 3);
    }
}


위에서 보듯이 해당 코드는 try-finally 블록으로 감싸지고
코드의 시작과 finally 부분에 msg를 등록/해제하는 register/unregister 함수가 추가되었다.
참고로 3번째 인자로 주어진 3이라는 값은 해당 객체가 stack 타입 임을 나타낸다. (__MF_TYPE_STACK)

위의 코드는 아직 mudflap 처리가 완전히 끝난 것이 아니라서 빠져있지만
최종적으로 메모리를 역참조(dereference) 하는 부분에는 메모리 접근을 검사하는 코드가 추가될 것이다.
GNU C 확장 기능인 statement expression을 이용하여 표현하면 p->f 식의 메모리 접근은
({ __mf_check(p, sizeof(*p), __MF_CHECK_WRITE, location); p; })->f 와 같은 형태로 바뀐다.
실제로는 lookup cache 검사 및 필드 f의 위치로 인해 이와는 약간 다른 형태의 코드가 생성된다.

또한 string이나 memory 관련 표준 함수들도 mudflap에 의해 wrapping되어
실제 함수 수행 전에 먼저 메모리 영역에 대한 검사가 이루어진다.
다음은 memcpy 함수에 대한 wrapper 루틴이다.

WRAPPER2(void *, memcpy, void *dest, const void *src, size_t n)
{
  TRACE ("%s\n", __PRETTY_FUNCTION__);
  MF_VALIDATE_EXTENT(src, n, __MF_CHECK_READ, "memcpy source");
  MF_VALIDATE_EXTENT(dest, n, __MF_CHECK_WRITE, "memcpy dest");
  return memcpy (dest, src, n);
}


여기서 실제 검사하는 MF_VALIDATE_EXTENT 매크로에서 수행하는데
이는 다음과 같이 정의되어 있다.

#define MF_VALIDATE_EXTENT(value,size,acc,context) \
 do { \
  if (UNLIKELY (size > 0 && __MF_CACHE_MISS_P (value, size))) \
    if (acc == __MF_CHECK_WRITE || ! __mf_opts.ignore_reads) \
    __mf_check ((void *) (value), (size), acc, "(" context ")"); \
 } while (0)


먼저 주어진 메모리 영역을 최근에 참조한 캐시 (__mf_lookup_cache)에서 찾아보는데
찾지못한다면 (__MF_CACHE_MISS_P()가 true를 반환) __mf_check()를 호출하여 등록된 전체 객체를 모두 찾아본다.
이 때 설정에 따라 read 접근인 경우 검사를 수행하지 않을 수도 있다. (-ignore-reads)

동적 메모리 함수의 경우에는 마찬가지로 wrapper 함수를 만들어서 내부적으로 실제 함수를 호출한 뒤
결과로 얻어진 영역을 __mf_register() 함수를 통해 자동으로 등록하도록 되어 있다.

하지만 이렇게 하더라도 모든 메모리 정보를 추적할 수는 없는 경우가 있다.
예를 들어 mudflap을 이용하지 않고 빌드된 외부 라이브러리를 이용하는 경우
해당 라이브러리 함수 내에서 할당된 동적 메모리 등의 경우는 mudflap에서 알아낼 수가 없다.

이 경우 프로그램에서 해당 메모리 접근 시 violation이 발생할 수 있는데
(혹은 어떤 이유로든 mudflap이 인식하지 못하는 정상적인 영역에 접근 시에도 마찬가지다)
이런 상황에 대처하기 위해 mudflap이 제공하는 몇 가지 heuristic을 이용할 수 있다.
이는 MUDFLAP_OPTIONS라는 환경 변수를 다음 중 하나로 설정하면 된다.

  • -heur-proc-maps : 리눅스에서 제공하는 /proc/<pid>/maps 파일에 등록된 영역이면 허가한다.
  • -heur-stack-bound : 현재 할당된 스택 영역 내의 접근은 허가한다.
  • -heur-start-end : 프로그램의 text/data/bss 영역 내의 접근은 허가한다.
  • -heur-argv-environ : 프로그램 실행 시 주어진 argv, env 배열에 대한 접근은 허가한다. (기본값: enable)


이 외에도 MUDFLAP_OPTIONS는 mudflap의 전반적인 동작 모드를 변경하거나
violation 발생 시 동작 변경 및 추가적인 정보를 표시할 수 있는 등의 여러가지 옵션을 설정할 수 있다.
옵션의 전체 목록은 mudflap을 이용해 빌드된 프로그램 실행 시 MUDFLAP_OPTIONS에 -help를 설정하면 볼 수 있다.


=== 참고 문헌 ===


저작자 표시 비영리 변경 금지
Posted by code쟁이 RosaGigantea
2014/06/18 15:52

http://www.slideshare.net/codenavy/ss-9303139


읽어보면 좋은 자료.

참고가 될듯..

저작자 표시 비영리 변경 금지
Posted by code쟁이 RosaGigantea
2014/06/18 15:49

출처 : http://www.mimul.com/pebble/default/2012/05/30/1338342349153.html

개요

OpenMP는 여러개의 프로세스가 공유된 메모리를 참조하는 환경에서 다중 스레드 병렬 프로그래밍을 위한 표준 스펙이다. 여기에서 제공하는 API를 통해 사용자들은 어플리케이션의 성능 향상을 얻을 수 있게 된다.



OpenMP의 주요 동기요인은 성능, 확장성, 이식성, 표준성을 목표로 한다. 그리고 C, C++(#으로 시작), Fortran(90에서는 !$로 시작)을 지원하고 있다.
역사로는 1997년에 Fortran 1.0가 최초로 나왔고 그 후 1998년 C/C++ 1.0이 출시, 2005년에 OpenMP 2.5가, 2008년에 OpenMP 3가 나와서 현재에 이르고 있다.
OpenMP를 주로 사용하는 방법은 프로파일링을 통해 시간을 많이 차지하는 부분을 식별하고 해당 프로그램에서 사용되는 의존성, 데이터의 유효 범위를 예측한 다음 지시어의 설정을 통해 병렬 처리를 하여 성능 향상을 얻는 방식으로 진행된다.

구성



1) Directives(컴파일러 지시자)
쓰레드 사이의 작업 분담, 통신, 동기화를 담당을 한다. 컴파일러가 지시자를 참고하여 다중 쓰레드 코드를 생성하게 된다.
Work-Sharing 지시자는 상세히 설명할 필요가 있어서 아래에 새로운 단락으로 빼서 설명하고 여기서는 동기화, 데이터 유효 범위 지시자를 설명한다. OpenMP 프로그래밍은 컴파일러가 모두 알아서 처리하는게 아니라 동기화 및 의존성 제거 등의 작업은 사용자가 직접 소스코드에 기술해 주어야 한다는 점에서 병렬프로그래밍이 어렵게 인식되는 부분중에 하나다.

- 상호 배제 동기화

  • critical : 병렬영역 안에서 critical section을 지정하면 그 영역은 하나의 스레드에서 실행 된다.
  • atomic : 하나의 스칼라 변수를 경신하는 지정된 단일 문장(single statement)에 대해 여러 스레드가 접근하는 것을 방지한다. mini-critical section의 역할과 비슷하다.
  • flush : 하나의 메모리에 여러 개의 스레드가 경합을 벌이는 경우 그 정합성을 유지시켜 주는 지시어

- 이벤트 동기화

  • barrier : 모든 스레드들이 barrier에 도달할 때까지 대기하게 된다.
  • ordered : ordered section 내부의 루프 실행을 순차적으로 진행한다.
  • master : master section을 마스터 쓰레드에서만 실행시킨다.
  • taskwait : 모든 task가 taskwait에 도달할 때까지 대기한다.

- 데이터의 유효 범위 지시자

  • private : 지정된 변수를 스레드끼리 공유하는 것 방지한다. 주로 스칼라값, 여러 쓰레드들이 동시에 접근해서 쓰기를 할경우 사용.
  • shared : 지정된 변수를 모든 스레드가 공유하도록 한다. 디폴트.
  • default : private 또는 shared로 선언되지 않은 변수의 기본적인 유효범위 지정한다.
  • firstprivate : private 변수처럼 각 쓰레드에 개별적으로 변수 생성하고 각 스레드 마다 순차 영역에서 가져온 값으로 초기화한다.
  • lastprivate : private 변수처럼 각 스레드에 개별적으로 변수 생성하고 순차 실행에서 마지막 계산에 해당되는 값. 즉, 마지막 반복실행의 값을 마스터 스레드에게 넘겨준다.
  • reduction : reduction 변수는 shared이고 다중 스레드에서 병렬로 수행된 계산 결과를 환산해 최종 결과를 마스터 스레드로 내 놓는다.
  • schedule : 작업의 균등 분배를 위해 schedule 을 사용한다.

2) Runtime Library
병렬화에 직접 참여는 하지 않지만 실행 환경에서 병렬 매개 변수(참여 스레드의 개수, 번호 등)의 설정과 조회를 통해 병렬화 정보를 변경 조회할 수 있다.

  • omp_set_num_threads : 병렬 영역에서 사용할 스레드 개수 설정
  • omp_get_num_threads() : 병렬 영역 안에서 호출되어 생성된 스레드의 개수를 리턴
  • omp_get_thread_num() : 병렬 영역 안에서 생성된 스레드들의 ID를 리턴
  • omp_get_max_threads() : 병렬 영역에서 사용 가능한 최대 스레드 개수 리턴
  • omp_set_nested() : nested 병렬성 지원 여부 결정
  • omp_set_dynamic() : 순차 영역에서 호출되어 이어지는 병렬 영역 들의 스레드 개수 할당을 동적으로 수행
  • omp_get_nested() : 호출되는 시점의 nested 병렬성 설정 여부 확인
  • omp_get_dynamic() : 스레드 할당 방식이 동적인지 확인
  • omp_in_parallel() : 호출된 지점이 순차 영역인지 병렬 영역인지 확인
  • omp_get_num_procs() : 프로그램에서 사용 가능한 물리적 프로세서의 총 개수 확인

3) Environment Variables
Runtime Library와 중복되는 부분이 많지만 우선순위는 동일한 지시자를 반복 사용했을 경우 Runtime Library가 우선된다. 주요한 일은 실행 시스템의 병렬 매개 변수(스레드 개수 등)를 설정해 실행시에 제어를 한다.

  • OMP_NUM_THREADS : 병렬영역에서 사용 가능한 최대 스레드 개수 지정
  • OMP_SCHEDULE : schedule type이 runtime으로 지정된 루프들에게 scheduling 방식 지정
  • OMP_DYNAMIC : 스레드 개수의 동적할당 여부 결정
  • OMP_NESTED : nested 병렬성 지원 여부 결정

 

프로그래밍 모델

1) Fork-Join 모델
쓰레드가 병렬 구문를 만나면 쓰레드는 그 자신을 포함한 추가적인 쓰레드(0개 이상의)로 이루어진 쓰레드 팀을 만든다(Fork). 병렬 구문를 만난 쓰레드는 팀의 마스터 쓰레드를 호출 하게 되고(Join) 다른 쓰레드들은 팀의 slave 쓰레드라고 불리어진다.



Work-Sharing 모델

같은 작업을 쓰레드별로 실행하는 것이 아니라 작업을 분할해서 쓰레드별로 나누어서 실행하는 것을 말한다.

1) for
바로 뒤에 오는 for 루프의 반복 실행을 쓰레드에 분배한다. 그리고 루프 끝에 암시적 장벽(동기화)이 존재한다. 이를 피할려면 nowait 사용하면 된다.
데이터 병렬화시에 활용된다.



#include <stdio.h>
#include <omp.h>

int main(int argc, char *argv[]) {
  int i;
#pragma omp parallel for
  for(i=0; i<10; i++) {
    printf("[%d-%d] Hello World\n", omp_get_thread_num(), i);
  }
   return 0;
}
> gcc -fopenmp -o for_hello for_hello.c
> ./for_hello
[0-0] Hello World
[0-1] Hello World
[0-2] Hello World
[2-6] Hello World
[2-7] Hello World
[2-8] Hello World
[3-9] Hello World
[1-3] Hello World
[1-4] Hello World
[1-5] Hello World


2) sections
독립된 여러 개 작업을 각 스레드에 분산 실행한다. 그리고 sections 구문 끝에 암시적 장벽(동기화)이 존재하고 이를 피할려면 nowait 사용하면 된다.
기능적 분할에 이용된다.



#include <stdio.h>
#include <omp.h>

int main(int argc, char *argv[]) {
#pragma omp parallel
#pragma omp sections
  {
#pragma omp section
    {
      printf("[%d] Hello \n", omp_get_thread_num());
    }
#pragma omp section
    {
      printf("[%d] World \n", omp_get_thread_num());
    }
  }
  return 0;
}
> gcc -fopenmp -o section_hello section_hello.c
> ./section_hello
[0] Hello 
[3] World 


3) single
병렬 영역 내부에서 하나의 스레드만을 이용해 작업 수행한다. single 지시어자 가장 먼저 접근한 스레드에 작업 할당된다. single 구문 끝에 암시적 장벽(동기화)이 존재한다.마찬가지로 이를 피하기 위해서는 nowait 사용하면 된다.
병렬 영역 내에서의 입/출력 수행에 주로 사용된다.



#include <stdio.h>
#include <omp.h>

int main(int argc, char *argv[]) {
#pragma omp parallel
 {
#pragma omp single
    {
      printf("[%d] Hello \n", omp_get_thread_num());
      
    }
    printf("[%d] World \n", omp_get_thread_num());
  }
  return 0;
}

> gcc -fopenmp -o single_hello single_hello.c
> ./single_hello
[3] Hello 
[3] World 
[2] World 
[1] World 
[0] World 


4) Task
OpenMP 버전 3.0 이상부터 추가된 지시자며, 수행할 작업을 한번의 호출로 진행되는 작업이나 한번의 구문으로 실행 가능한 작업 단위 나눈다. 태스트 실행은 작업 스케쥴링이 적용된다.

#include <stdio.h>
#include <omp.h>

int main(int argc, char *argv[]) {
#pragma omp parallel
  {
#pragma omp single
    {
#pragma omp task
      {
        printf("Hello ");
      }
#pragma omp task
      {
        printf("World ");
      }
#pragma omp taskwait
      printf("\nThanks! ");
    }
  }
  printf("\n");
  return 0;
}

> gcc -fopenmp -o task_hello task_hello.c
> ./task_hello 
Hello World 
Thanks! 


추후에는 mysql++ 라이브러리를 활용해서 MySQL Benchmark 클라이언트 성능 개선 예제를 올려볼까 합니다.

[참조 사이트]

Tags : 


저작자 표시 비영리 변경 금지
Posted by code쟁이 RosaGigantea
2014/06/18 15:48

출처 : http://geniusduck.tistory.com/28



Class 및 Class instance 의 기본 표기 형식 


Class 표기형식 

UML Diagram 중에서 가장 기본적인 표현 단위인 클래스의 표기형식을 알아보자.


Class 표기형식

+  :  public
-  :  private 
#  :  protected


*  variables, methods 는 생략이 가능하나 class 이름은 반드시 명시해주어야 한다.

위의 class 를 소스코드로 표현하면 아래와 같다.

Person Class



Class instance 객체의 표기형식 


Class instance 객체의 표기형식



Relationships( 관계 표현 )

서로 의미있는 클래스들의 관계에는 크게 4가지 종류가 있다.

일반적인 의미의 연결 관계인 연관( association ) 관계, 전체와 부분을 나타내는 

집합( aggregation )  관계, 다른 클래스의 재산을 물려받는 상속( inheritance ) 관계

그리고 한 클래스가 다른 클래스에 영향을 미치는 의존( dependency ) 관계가 있다.


이 중에서도 association  과 aggregation, composition 이 세가지 관계가 가장 헷갈릴 수 

있는데 간략하게 정리를 해보자면 아래의 그림과 같다. 회색 부분이 각각의 관계를 구분짓는 

기준이 된다고 볼 수 있다.


사용자 삽입 이미지


association 과 dependency 를 구분짓는 가장 큰 기준은 ' 참조하는 클래스 인스턴스의 

레퍼런스를 계속 유지하고 있느냐, 아니냐 ' 이다. 아래의 소스 코드들을 보면서 이해해보자.


[ 소스 코드 1 ] dependency


사용자 삽입 이미지



[ UML ] dependency ( A ----> B )


사용자 삽입 이미지




[ 소스 코드 2 ] association
 

사용자 삽입 이미지


[ UML ] association ( A - > B )


사용자 삽입 이미지




◆ dependency( 의존 관계 )

클래스가 연관, 상속, 집합 관계로 엮여 있는 것은 아니지만, 한 곳이 변경되면 그것을 사용하는
 
다른 곳도 같이 변경해줘야 하는 관계를 표현할 때 주로 사용한다. 단, 주의해야 할 점은 

association 과 달리 dependency 의 경우에는 클래스 인스턴스의 레퍼런스를 유지하고 

있지 않다는 점이다. 레퍼런스를 계속적으로 유지하게 되면 이는 association 으로 표현해야 

한다.

주로 다음과 같은 세 가지 경우에 의존 관계로 표현한다.

1. 한 클래스의 메소드가 다른 클래스의 객체를 인자로 받아 그 메소드를 사용한다.
  ( 가장 일반적 ) 

2. 한 클래새의 메소드가 또 다른 클래스의 객체를 반환한다.

3. 다른 클래스의 메소드가 또 다른 클래스의 객체를 반환한다. 이때 이 메소드를 호출하여
   반환되는 객체의 메소드를 사용한다.





◆ association( 연관 관계 )


한 객체가 다른 객체와 연결되어 있음을 나타낼 때 그들을 연관관계로 지칭한다. 이러한 

연관관계에서 중요하게 볼 점은 ' 연관 관계의 방향( navigability ) 과 멀티플리시티

( multiplicity ) 이다.

사용자 삽입 이미지



양방향 연관 관계 : 연결된 클래스들이 서로의 존재를 알고 있다는 의미이다.

위의 UML 을 해석하자면 House 와 Person 클래스는 서로의 존재를 알고 있으며, 반드시 

한 사람 이상이 House에 속해야 한다는 것을 뜻한다. 

사용자 삽입 이미지


단방향 연관 관계 : House 클래스는 Person 클래스의 존재를 알고 있지만, Person 은 

House 클래스의 존재를 모르고 있다고 이해하면 된다. 이와 같은 경우는 House 클래스만 

Person 클래스에 대한 참조값을 가지고 있고, Person 은 House 에 대한 어떠한 참조값도 

가지고 있지 않는다.  


관계 표현을 나타낸 그림에서 보면 일반 연관과 특수 연관이라고 나뉘어 지는데, 

특수 연관이라는 것은 임의로 만든 단어이다.  일반 연관이란 앞에서 살펴본 association 을 

나타내며,  association 중에서도 ' 부분과 전체 ' 로 나눌 수 있는 관계를 aggregation 과 

composition 으로 묶어서 분류한 것이다.

aggregation 과 composition 은 모두 association 의 한 특별한 형태로 각각을 구분하는 

기준은  ' life cycle 이 같느냐, 같지 않느냐 ' 이다. life cycle 이란 클래스 인스턴스의 

생명 주기를 말하는 것으로 생성에서 소멸까지의 과정을 말한다. 즉, life cycle 이 같다는 것은
 
관계된 클래스 혹은 그 인스턴스의 생성과 소멸이 동시에 이루어진다는 것을 뜻한다.

쉽게 예를 들어 표현하자면 모자와 안경을 쓴 사람을 놓고 보자. 현재 이 사람을 구성하고 있는 

요소에는 눈, 팔, 다리와 같이 사람이 죽으면 같이 없어지는 요소들이 있고, 안경 모자와 같이 

바꿔 사용할 수 있는 요소들이 있다. 즉, 눈, 팔, 다리는 사람과 life cycle 이 같은
 
composition 관계 이고, 안경이나 모자는 aggregation 관계인 것이다. 이러면 이해가 좀 쉽게 

갈라나? ^-^ 


[ 소스 코드 1 ] aggregation 

사용자 삽입 이미지


[ UML ] aggregation

사용자 삽입 이미지



[ 소스 코드 2 ] composition

사용자 삽입 이미지


[ UML ] composition

사용자 삽입 이미지



◆ 상속 관계 ( inheritance ) 

[ 소스 코드 ] 

사용자 삽입 이미지


[ UML ] inheritance

사용자 삽입 이미지



 interface

[ 소스 코드 ] 

사용자 삽입 이미지

[ UML ] 

사용자 삽입 이미지


저작자 표시 비영리 변경 금지
Posted by code쟁이 RosaGigantea
TAGUML

티스토리 툴바