접근 제어 행렬 (Access Matrix) - 주체와 객체 간 접근 권한을 2차원 표로 표현하는 수학적 모델

핵심 인사이트 (3줄 요약)

1. 본질: 접근 제어 행렬은 **행(Row)에 주체(프로세스/도메인)**을, **열(Column)에 객체(파일/프린터)**를 배치하고, 각 교차점에 **권한 집합(읽기/쓰기/실행)**을 표기하여 접근 권한을 수학적으로 표현하는 모델이다.
2. 가치: 이 2차원 행렬 구조 덕분에, OS는 특정 프로세스가 특정 객체에 접근하려 할 때 (프로세스, 객체) 좌표만 확인하면 되므로 $O(1)$ 시간에 접근 권한을 검증할 수 있다.
3. 한계: 실제 시스템에서 행렬의 99%이상이 비어있어(희소 행렬), 메모리 낭비가 심하다. 따라서 실제로는 ACL(행 기준 분할) 또는 **Capability(열 기준 분할)**로 구현한다.

1. 개요 및 배경 (Context & Necessity)

1.1 접근 제어 행렬의 정의

접근 제어 행렬(Access Matrix)은 다음과 같이 정의된다:

Matrix[i][j] = 도메인 i가 객체 j에 대해 보유한 권한 집합

1.2 놀이공원에서의 비유

놀이공원에서:

• 행(Row): 방문객 유형 (성인/어린이/직원)
• 열(Column): 놀이기구 (바이킹/회전목마/ 롤러코스터)
• 교차점: 해당 방문객이 해당 놀이기구를 탈 수 있는지 여부

1.3 수학적 표현

      파일1     파일2     프린터
도메인A  {Read}    {}       {}
도메인B  {Read}   {Write}  {Print}
도메인C  {}       {}       {Print}

2. 아키텍처 및 핵심 원리 (Deep Dive)

2.1 희소 행렬(Sparse Matrix) 문제

실제 시스템에서는:

• 도메인(사용자) 수: 수만~수십만
• 객체(파일) 수: 수백만~수천만
• 행렬 칸 수: 수조~수천조
• 실제 권한이 있는 칸: 약 0.01%

따라서 통짜 행렬을 메모리에 저장하는 것은 비현실적이다.

2.2 권한의 전파: Copy와 Owner

권한 회수(Revocation)가 필요한 경우, 시스템은 행렬을 스캔하여 해당 권한을 찾아 제거해야 하므로 $O(N)$ 시간이 소요된다.

3. 구현 방식: Global Table

3.1 Global Table의 개념

희소 행렬 문제를 해결하기 위해, 권한이 존재하는 튜플만을 저장한다:

<도메인A, 파일1, {Read}>
<도메인B, 파일2, {Read, Write}>
<도메인B, 프린터, {Print}>

3.2 Global Table의 한계

• 선형 탐색: 권한 확인 시 리스트 전체를 탐색해야 하므로 $O(N)$ 시간
• 락 경합: 중앙 테이블에 동시 접근 시 동기화 문제 발생

4. 기대효과 및 결론

• 이론적 완전성: 접근 제어 행렬은 보안 정책의 수학적 모델로서 완전한 표현력을 제공한다.
• 실제 한계: 희소 행렬 문제로 인해 실제 시스템에서는 ACL 또는 Capability 방식으로 분할 구현된다.
• 현대적 변형: 데이터베이스 인덱싱과 유사하게, 해시 맵 등을 활용하여 탐색 성능을 개선한다.

관련 개념 맵 (Knowledge Graph)

👶 어린이를 위한 3줄 비유 설명

1. 접근 제어 행렬은 학교의 "학생-교실-출입 가능 여부" 표와 같다. 각 학생이 어떤 교실에 출입할 수 있는지 한눈에 볼 수 있다.

2. 희소 행렬 문제는 100명의 학생과 1000개의 교실이 있으면 표가 10만칸이 되는데, 실제 출입 가능한 칸은 수십 개뿐이라 칸의 대부분이 비어있어 공간이 낭비되는 것과 같다.

3. 구현 분할은 비어있는 칸을 생략하고, **"출입 가능한 경우만"**을名簿(명부)에 적어두는 것과 같다. 이렇게 하면 공간을 절약할 수 있지만, 특정 학생의 출입 가능 교실을 찾으려면名簿를 모두 확인해야 하는 문제가 있다.