전체 글 123

그래프 표현

인접행렬(adjacency matrix) 행렬을 사용하여 나타낸다. ex> (v1. v2)가 존재한다면 matrix[1][2] = 1, 존재하지 않으면 값은 0이된다. 필요한 기억장소의 크기 = 공간복잡도(space complexity) = S(n) = n제곱 무방향 그래프에서는 행렬이 대각선을 중심으로 대칭(symmetric)이다. 이는 완전 그래프를 제외하고는 대부분의 그래프일 경우 edge 수는 적기 때문에 대부분의 행렬원소들은 0이 된다. 고로 상당량의 기억장소가 낭비된다. 인접리스트(adjacency list)

그래프 용어

G : 그래프 V : 정점(vertex) E : 간선(edge), 연결선. 정점을 연결하는 선. V x V의 부분집합. G = (V,E) V(G) = 그래프 G를 구성하는 정점들의 집합. E(G) = 그래프 G를 구성하는 연결선들의 집합. 무방향 그래프(undirected graph) 쌍방통행이 가능한 그래프. 즉, 방향성이 없는 선이다. 고로 (v1, v2) = (v2, v1) 방향 그래프(directed graph) 일방통햄만이 가능한 그래프 즉, 방향성이 있는 선. 고로 (v1, v2) ≠ (v2, v1) 방향 그래프에서 정점의 쌍은 로 표시한다. 이 때 v1을 꼬리(tail)이라 한고 v2를 머리(head)라 한다. 제한 사항> 1. 자기 자신을 향하는 연결선은 없다.(no self loop) 2..

objdump을 통한 해부

바이너리 파일 해킹 시 사용되는 툴 리눅스는 아래의 a.c에서 만든 main()을 어떻게 실행시키는가. 요약 1. GCC는 crtbegin.o, crtend.o, gcrt1.o를 첨가형 프로그램을 컴파일한다. 이 때 다른 기본 라이브러리들도 동적으로 링크된다. 프로그램의 시작 주소는 _start의 주소로 설정된다. 2. 커널은 실행 파일을 읽어들여 /text/data/bss/stack을 생성한다. 이 때 매개변수와 환경변수를 위한 페이지를 할당하고 필요한 정보는 스택에 push 한다. 3. _start가 실행된다. _start는 스택에서 커널이 집어넣은 정보를 얻고 __libc_start_main을 위한 매개변수 스택을 만든 후 _start를 부른다. 4. __libc_start_main은 malloc과..

OS/Linux 2012.01.18

euid, uid

euid : 유효사용자 ID. 명령어 실행시 실제 어떤 사용자 권환으로 실행되는가. 커널은 프로세스마다 네가지 번호 부여. 실제uid(ruid), 유효uid(euid), 실제gid(rgid), 유효gid(egid) 실제(real) 번호들은 계정 관리를 위해 사용. 유효(Effective) 번호들은 접근 권한을 결정할 목적. 보통은 실제번호와 유효번호가 동일. 정상적이라면 프로세스는 자신에게 부여된 네가지 번호를 변경하지 못한다. 예외) 다른 프로그램 파일을 실행하고 싶은 프로세스는 exec 시스템 콜 가족 중의 하나를 호출. 이때 새로운 프로그램의 이미지를 담고 있는 파일의 setuid 나 setgid 허가 비트가 설정되어 있다면 프로그램의 euid와 egid는 실행되는 파일의 uid와 gid로 설정. ..

OS/Linux 2012.01.18
반응형