공부 기록

💡 요약
- abstract: 대형 딥 뉴럴 네트워크 모델을 효율적으로 모델 병렬화 하는 방법에 관한 연구
- introduction: 큰 용량의 모델은 일반적으로 모델 병렬화하여 학습을 진행하는데, 범용적으로 효율적인 알고리즘을 적용하기 쉽지 않다는 문제가 있다.
- related works: 기존에 모델 병렬처리를 통해 네트워크를 서로 다른 계산 단위로 분할 후 이를 서로 다른 장치에 배치했는데, 낮은 하드웨어 활용률과 통신 병목 현상이 문제가 되었다. 이후, Single Program Multiple Data 및 파이프라인 병렬화가 제안되었는데, 병렬화된 각 행렬 곱셈의 결과값을 결합(AllReduce)하는데 사용되는 연산이 통신 오버헤드의 원인이 되었으며 특정 네트워크 아키텍쳐에 종속적이었다.
- method: Pipeline Model Parallelism(micro-batch) & Rematerialization
- experiment: 이미지 분류(AmoebaNet)과 기계번역(Transformer) 모델로 테스트 해 본 결과, Rematerialization 에 의해 단일 가속기에서도 메모리 요구량을 줄일 수 있었으며 모델 병렬화를 통해 모델을 확장할 수 있었다.
- conclusion & discussion: GPipe는 전체 미니 배치에 대해 단일 동기식 그라데이션 업데이트를 적용하기 전에, 마이크로 배치의 실행을 파이프라인화하는 Rematerialization과 결합한 새로운 파이프라인 병렬 처리를 도입했으며, 추가적인 통신 오버헤드가 없어 가속기 수에 따라 거의 선형적으로 확장할 수 있다. 단, 모델을 분할할 때 레이어의 파라미터가 불균형하게 분포하는 경우 가속기 수에 따라 완벽하게 선형 확장되지 않는다.

Introduction

딥 러닝이 발전하면서 모델의 파라미터 사이즈가 증가함에 따라 정확도가 비례하도록 개선되는 것을 관찰할 수 있었다.

하지만, 하드웨어적인 한계로 인해 큰 모델을 학습하는 것은 상당한 제약을 따른다. 

일반적으로 학습의 양이 많을 때, 분산 학습을 하게 되는데 두 가지 처리 방식이 있다.

• Model Parallelism: 모델의 자체의 크기가 커서 메모리가 부족할 때 사용한다. 각 디바이스는 모델의 일부분을 가지며, 결과값을 다른 디바이스에 넘겨주며 학습을 진행한다.
• Data Parallelism: 데이터 셋의 크기가 커서 메모리가 부족할때 주로 사용한다. 각 디바이스는 각각 전체 모델의 사본을 가지고 있으며, 분할된 데이터로 각자 학습 시킨 후 결과를 취합한다.

본 논문에서는 모델 병렬화에서 다루고 있는데 모델 병렬화는 효율적인 알고리즘을 구현하기 어렵고, 만약에 효율적인 알고리즘을 구현하더라도 특정 아키텍쳐나 태스크에 종속된다는 단점을 가진다. 또한, 예시 그림을 살펴보면 모델 병렬화는 데이터가 device1 -> (device2, device3) -> device4 으로 전달된다. 즉, 훈련 시 이전 레이어가 끝날때까지 기다려야 한다.

Method

GPipe는 각 레이어에서 일어나는 계산을 (1)파이프라이닝하여 병렬 처리하며, (2) Rematerialization을 활용하여 메모리 효율을 높인다.

## Pipeline Model Parallelism

모델 학습 시에는 각 레이어에서 forward propagation을 통해 loss를 계산하고, backward propagation에서 loss가 최소가 되도록 gradient를 구한다. 이 레이어를 각 디바이스에 나누면 그림 (b)와 같이 배치되는데, 앞쪽에서 결과값이 업데이트 될 때까지 기다려야하는 bubble time이 존재한다.

이 bubble time을 줄이기 위해서 본 논문에서는 그림 (c)와 같이 N개의 mini batch를 각각 M개의 동일한 micro batch로 나누어 학습을 진행한다. 그림 (c)를 보면 micro batch만 계산 후 결과값을 다음 레이어로 넘기기 때문에 다른 디바이스가 계산을 보다 빨리 시작할 수 있다. 

만약 네트워크에서 batch normalization이 이루어지는 경우, 각 계산은 micro-batch에 대한 통계를 사용하지만, evaluation을 위해 mini-batch 통계를 축적한다.. 그리고 장치 간 통신은 모든 micro-batch의 파티션 경계에서만 이루어진다. 이때, 디바이스간 데이터 전송 오버헤드가 있을 수 있지만, activation tensor만 전달하면 되기 때문에 통신 오버헤드는 무시할 수 있을만큼 작음을 관찰할 수 있었다.

bubble time은 O((K-1)/(M+K-1)) 으로 M>=4K일때 거의 무시할 수 있음을 실험을 통해 관찰할 수 있었다.

• K: partition 개수
• M: device 개수
• 이전 Layer의 계산이 끝날때까지 기다리지 않고도 backward pass 중 재 계산을 더 일찍 스케줄링 할 수 있기 때문

## Rematerialization

sequential layer 입력값을 제외하고 이후 back propagation에서 재사용 될 가능성이 있는 중간 계산 값들을 메모리에 store&load 하는 대신, 값을 일단 버리고 나중에 다시 필요할 때 재계산한다. 그 결과 메모리 요구량은 O(N*L) -> O(N+(L/K)*(N/M)) 으로 줄어든다.

• L: layer 갯수
• K: partition 갯수
• N: mini batch 갯수
• M: 디바이스 갯수
• N/M: micro batch 크기
• L/K: 파티션 당 레이어 수
• 메모리 요구량 = 그래디언트(bi)를 계산하는 데 상위 레이어 그래디언트(bi+1)와 캐시된 activation(fi(x))가 모두 필요

하지만 forward computation을 2번 계산 해야하기 때문에, 약 25% 정도 시간이 더 걸린다. 이 대기 시간을 더욱 줄이기 위해서 아래 그림과 같이 pipeline을 조정할 수 있다.

Experiment

• Naive-1: GPipe가 없는 sequential 한 버전
• Pipeline-k: k개의 가속기에 분할하여 학습
• AmoebaNet-D(L,D): cloud TPUv2s (8GB memory each)
  • L: 일반 셀 레이어 갯수
  • D: 필터 크기
  • 입력 이미지 크기 (224,224), 미니배치 크기 128
• Transformer-L: cloud TPUv3s (16GB memory each)
  • L개 layer, 각 레이어의 dimension 2048, feed-forward hidden dimensions 8192, attention heads 32 
  • 어휘 크기 32k, 시퀀스 길이 1024, 배치 크기 32

Rematerialization의 결과

- AmoebaNet: Gpipe는 back propagation과 batch splitting에 의해 중간에 계산되는 activation memory 요구량을 6.26GB->3.46GB(Peak Activation Memory)로 줄여 단일 가속기에서 318M 파라미터 모델을 구현할 수 있다.

- Transformer: 단일 가속기에서 2.7배 더 큰 모델을 훈련할 수 있다.

Model Parallelism의 결과

- AmoebaNet: 모델 병렬화를 통해 8개의 가속기에서 아메바넷을 18억개의 파라미터로 확장할 수 있었다. (약 25배)

- Transformer: 128개의 파티션으로 구성된 GPipe를 사용하면 839억개의 파라미터까지 확장할 수 있다 (약298배)

* AmoebaNet와 Transformer의 확장이 차이나는 이유는?

뉴럴 넷 모델의 경우 레이어마다 메모리 요구 사항 및 계산량이 불균형한 경우가 있는데, 이러한 경우에는 불완전한 파티셔닝 알고리즘으로 인해 부하 불균형이 발생할 수 있다. 표에서 살펴볼 수 있듯이, 마이크로 배치 수(K)가 많을수록 성능이 향상하며, 아메바넷은 모델 파라미터의 불균형한 분포로 인해 최대 모델 크기가 완벽하게 선형적으로 확장되지 않았다. 이는 아메바넷의 여러 레이어에 걸쳐 모델 파라미터가 불균형하게 분포되어 있기 때문이다. 트랜스포머 모델의 경우는 각 레이어의 파라미터 수와 입력 크기가 동일하기 때문에, 최대 모델 크기는 Transformer의 가속기 수에 따라 선형적으로 확장될 수 있었다.

이 표에서 관찰할 수 있는 것은, M이 상대적으로 작은 경우 대기 시간을 더 이상 무시할 수 없게 된다는 점이다. M=1이면 사실상 파이프라인 병렬화가 존재하지 않아 사용되는 가속기 수에 관계없이 비교적 일정한 처리량을 관찰할 수 있었다. (주어진 시간에 한 대의 장치만 계산=병렬화X)

Discussion

결론적으로 GPipe의 세 가지 핵심 속성은 아래와 같다

1) 효율성: 새로운 배치 분할 파이프라이닝 알고리즘을 사용하는 GPipe는 장치 수에 따라 거의 선형적인 속도 향상을 달성한다.

2) 유연성: GPipe는 모든 순차적 신경망을 지원한다.

3) 신뢰성: GPipe는 synchronous gradient descent을 활용하며, 파티션 수에 관계없이 일관된 훈련을 보장한다.

stochastic gradient descent - https://light-tree.tistory.com/133

RMSProp - https://box-world.tistory.com/69

카카오에서 TPU 대신 CUDA를 사용하는 pytorch용 gpipe를 구현해둔게 있어서 한번 보면 좋을 것 같음 - https://github.com/kakaobrain/torchgpipe

💡 요약
- abstract: "단일" 엣지 서버에서 애플리케이션의 실행 효율을 향상시키기 위한 연구
- introduction: 엣지 서버의 경우 리소스가 제한되어 있으며 다양한 물리 환경을 가지기 때문에 가벼운 컨테이너 가상화가 적합한데, 컨테이너 간 통신 및 데몬 프로세스에 의한 컨테이너 관리로 인해 상당한 CPU 리소스가 소모되는 문제가 있다.
- related work: 엣지 서버들과와 클라우드에서의 워크로드 스케줄링을 통해 태스크 실행 효율을 향상시키는 조사 & 베어메탈 기반 머신에서의 시나리오 조사 -> 단일 엣지 서버에서 컨테이너에 대한 효율 향상에 관한 연구는 없었음
- method: 공동 태스크 스케줄링 및 컨테이너화 기법을 제시
- experiment: 광범위한 시뮬레이션을 통해 평가한 결과, 비효율적인 컨테이너 운영을 줄이고 애플리케이션의 실행 효율을 60%까지 향상
- conclusion & discussion: JTSC 체계는 비효율적인 컨테이너 운영을 줄이고 다양한 요구사항을 충족하면서 애플리케이션의 실행 효율성을 향상시키는 것을 보였지만, 더 복잡한 시나리오에서 테스트 할 여지가 있다.

Introduction

엣지 서버의 경우 리소스가 제한되어 있으며 다양한 물리 환경을 가진다. 또한 지능형 교통, 비디오 분석, 증강 현실, 스마트 홈 등 다양한 애플리케이션을 지원하므로 소프트웨어 종속성 충돌을 피하기 위해 가상화가 좋은 방법이 될 수 있다. 

컨테이너는 가상화 기술의 한 종류로, 하나의 운영 체제 커널을 공유하면서 독립적인 파일 시스템과 환경을 갖는 프로세스를 격리하여 실행하는 기술이다. 이러한 컨테이너 기술을 엣지 환경에서 사용하는 경우,

• 경량화된 실행 환경: 컨테이너는 가상화 기술 중에서 가장 경량화된 기술이기 때문에, 엣지 디바이스와 같이 자원이 제한된 환경에서도 효율적으로 실행될 수 있다.
• 격리된 실행 환경: 컨테이너는 독립적인 파일 시스템과 환경을 갖기 때문에, 서로 다른 애플리케이션을 격리된 환경에서 실행할 수 있다. 이를 통해 애플리케이션 간의 상호작용을 방지하고, 보안성을 강화할 수 있다.
• 확장성: 컨테이너는 쉽게 생성, 복제, 이동, 삭제 등의 작업을 수행할 수 있기 때문에, 엣지 환경에서 애플리케이션을 확장하거나 축소하는 것이 용이하다.

가벼운 컨테이너 가상화를 통해 소프트웨어 의존성을 피할 수 있는는데, 컨테이너 간 통신 및 데몬 프로세스에 의한 컨테이너 관리로 인해 상당한 CPU 리소스가 소모되는 문제가 있다.

예비 실험을 통해 확인해 본 결과, (a) 컨테이너 간 통신의 경우 컨테이너 내 통신과 비슷한 전송 속도일때, CPU 사용률이 낮다. (b) 더 많은 태스크가 컨테이너에서 시작될 때, 데몬 프로세스가 더 많은 리소스를 소비한다.

컨테이너의 효율성을 개선하기 위해서는 두 가지가 있는데, 이 논문에서는 기존 컨테이너 시스템을 변경할 필요가 없는 후자의 방법을 택한다.

1. 커스터마이징 된 컨테이너를 통해 컨테이너 작업에 소모되는 CPU 리소스를 줄이는 방법

2. 비효율적인 컨테이너 작업의 사용량을 줄이는 방법

비효율적인 컨테이너 작업은 애플리케이션 작업의 스케줄링과 작업-컨테이너 간의 매핑 체계에 따라 달라지므로, 비효율적인 컨테이너 작업을 줄이기 위해서는 스케줄링과 컨테이너화를 함께 고려해야 한다.

예를 들어, 이미지 인식 애플리케이션 (a)는 (b)와 같은 다양한 작업으로 이루어져 있다. 각 작업을 컨테이너로 나눌 때, 오른쪽 방식이 왼쪽 방식에 비해 컨테이너 간 통신을 74%, 데몬 프로세스에서 사용하는 CPU 리소스를 29% 줄일 수 있다. 또한, 오른쪽 방식이 왼쪽 방식보다 작업 시간이 더 짧게 걸린다.

따라서 본 논문은 컨테이너 작업을 최적화 하기 위해 애플리케이션의 구성(태스크 간의 관계)을 나타내는 애플리케이션 모델을 구축하고, 태스크와 컨테이너에 의한 각각의 CPU 자원 사용률과 태스크의 실행 시간을 보여주는 실행 모델을 구축한다. 그리고 이러한 모델을 기반으로 공동 작업 스케줄링 및 컨테이너화(JTSC) 체계를 설계하고 있다.

논문이 기여한 바는 아래와 같다:

• 단일 엣지 서버에서 컨테이너 작업에 사용되는 CPU 리소스를 정량화하고, 작업 실행에 미치는 영향을 분석한다.
• 컨테이너화 프레임워크 및 알고리즘은 컨테이너화 체계와 작업 스케줄링을 결정함으로써, 컨테이너 작업량 및 애플리케이션의 실행 시간을 낮게 유지하도록 설계했다.

Backgrounds

2.1.1. 컨테이너

컨테이너와 가상 머신은 단일 리소스를 '가상화'하여 여러 리소스로 나타낼 수 있는 프로세스이다. 

가상 머신이 전체 머신을 하드웨어 계층까지 가상화하고, 컨테이너는 운영 체제 레벨 위의 소프트웨어 계층만 가상화한다.

따라서 컨테이너는 가상 머신에 비해 호스트와 OS 커널을 공유하기때문에 더 가볍다. 격리된 환경은 namespace와 cgroup이라는 두 가지 OS 매커니즘을 통해 제공된다.

• namespace: 호스트 이름과 도메인 이름, 파일 마운트 지점, 프로세스 간 통신(IPC) 관련 정보, 프로세스 ID(PID), 네트워크 스택, 사용자 등 서로 다른 컨테이너에 대한 리소스를 서로 격리된 상태로 유지한다.
• cgroup: 서로 다른 컨테이너의 프로세스에서 사용하는 시스템 리소스를 제한하고, 프로세스의 일시 중단/재개를 제어한다.

2.1.2. 데몬

데몬은 백그라운드 프로세스로 계속 실행되고, 종종 원격 프로세스에서 오는 주기적인 서비스 요청을 처리하기 위해 깨어나는 프로그램이다. 데몬 프로세스는 컨테이너의 시작 및 중지, 이미지 관리 등과 같은 컨테이너 관리 프레임워크에서 실행된다.

Containerd는 호스트에서 컨테이너의 수명 주기를 관리하는 컨테이너 런타임으로, 컨테이너를 생성, 시작, 중지 및 파괴한다. 또한 컨테이너 레지스트리에서 컨테이너 이미지를 가져오고, 스토리지를 마운트하고, 컨테이너에 대한 네트워킹을 활성화할 수 있다. Containerd 는 아래와 같이 구성되며, 각 구성 요소는 서로 협력하여 컨테이너 작업을 수행한다.

containerd는 대화식 사용자가 직접 제어하지 않고 백그라운드 프로세스로 실행되는 데몬으로, 위와 같은 작동 방식을 가진다.

2.1.3. 네트워크

서로 다른 컨테이너의 네임스페이스가 격리되어 있기 때문에, 공유 메모리를 통한 IPC는 서로 다른 컨테이너의 프로세스 간에 데이터를 전송하는 데 직접 사용할 수 없다. 따라서 Docker는 컨테이너 간 데이터 전송을 위해 서로 다른 네트워크 세그먼트를 연결하는 가상 스위치, 브리지를 사용한다.

데몬 프로세스가 초기화되면, 브리지 인스턴스가 시작되며, Veth(가상 이더넷)는 네임스페이스 사이의 터널 역할을 한다. Veth는 일반적으로 컨테이너에 하나, 브리지에 다른 하나 등 쌍으로 생성되는데, 그 결과 브리지와 연결된 Veth 디바이스가 있는 모든 컨테이너는 동일한 서브넷 내에 있게 되어 서로 데이터를 전송할 수 있게 된다. 이러한 브리지를 통한 데이터 전송은 데이터 패킹 및 언패킹 등의 절차가 필요하기 때문에 IPC에 비해 비효율적이라는 단점이 있다.

Preliminary Experiments

EXPERIMENTS ABOUT CONTAINER OPERATIONS

최신 컨테이너 관리 프레임워크 Docker와 일반적인 컴퓨팅 플랫폼인 X86 및 ARM 상에서 실험이 이루어졌다.

3.1. 컨테이너 간 통신

Netperf의 클라이언트와 서버를 두 개의 컨테이너(브리지를 통한 통신) 또는 동일한 컨테이너(IPC와 통신)에 배치하여 두 호스트간에 네트워크 대역폭을 측정한다. 클라이언트는 다양한 CPU 사용률(10~100%)을 가지며, 180초 동안 서버로 데이터 패킷을 계속 보낸다. 위 그래프에서 볼 수 있듯이, 브릿지 네트워크 또는 IPC의 전송 속도는 할당된 CPU 리소스에 따라 선형적으로 증가하며, 이는 전송 속도가 소모된 CPU 리소스의 양과 밀접하게 연관되어 있음을 나타낸다.

그리고 그림 5에 따르면, 네트워크 가상화 방식에 관계 없이, 데이터 전송 속도가 거의 동일한 것으로 나타났다.

3.2. 데몬 프로세스에 의한 컨테이너 관리

컨테이너 작업이 수행될 때 데몬 프로세스의 CPU 리소스 사용량을 기록하며 실험을 진행한다.

그림 6에서 볼 수 있듯이, 컨테이너 20개를 시작하기 위해 데몬 프로세스가 사용하는 CPU 리소스가 컨테이너 모니터링에 사용되는 리소스보다 훨씬 많다. 그 이유는 아래와 같다.

• 컨테이너 시작: 리소스 제한 설정, 네트워크 구성, 볼륨 마운트 등 많은 작업이 포함된다.
• 모니터링: 주기적으로 컨테이너의 상태만 확인하면 된다. 

위 예비 실험을 통해 컨테이너 간 통신이 컨테이너 내 통신보다 효율성이 떨어진다는 것을 알 수 있었다. 하지만, 서로 다른 컨테이너에 할당된 태스크 간의 데이터 전송을 위해서는 컨테이너 간 통신이 불가피하기 때문에 이러한 작업을 실행하는 경우, 데이터 전송 속도가 느려서 컨테이너가 없는 경우보다 실행 시간이 더 길어진다. 따라서 컨테이너화 방식을 신중하게 결정하여 컨테이너 간 통신량과 그에 따른 애플리케이션 실행 시간에 미치는 영향을 줄일 수 있도록 해야 한다.

컨테이너를 시작할 때 데몬 프로세스는 작업 실행을 위한 리소스를 선점하는 데 상당한 CPU 리소스를 소비하며, 애플리케이션의 총 컨테이너 시작 시간은 총 컨테이너 수와 각 컨테이너 시작 횟수라는 두 가지 요소에 따라 달라진다. 컨테이너 수는 컨테이너화 체계에 따라 결정되며, 컨테이너를 시작하는 횟수는 컨테이너에 있는 작업의 일정에 따라 달라진다. 따라서 컨테이너 애플리케이션을 최적화하기 위해서는 작업 스케줄링과 컨테이너화를 함께 고려하는 것이 필수적임을 알 수 있었다.

Methods

실험에 사용된 애플리케이션은 너무 단순하여 실제 애플리케이션을 대표하기에는 부족하기 때문에, 본 논문에서는 실험 결과를 일반적인 애플리케이션으로 확장하기 위해 애플리케이션 모델과 실행 모델이라는 두 가지 시스템 모델을 구축한다.

• 애플리케이션 모델: 일반적인 엣지 컴퓨팅 애플리케이션의 구성을 설명한다.
  • 일반적으로 애플리케이션은 표준 API로 연결된 여러 모듈로 구성되며, 이 모듈이 입력 데이터를 처리한 후 출력 데이터를 생성하는 과정을 태스크라고 한다. 태스크 간에는 종속성이 있으며, 고려해야 할 태스크 종속성에는 소프트웨어 종속성, 데이터 종속성, 커플링의 세 가지 유형이 있다.
    • 소프트웨어 종속성: 소프트웨어 구성 요소에 의존
    • 데이터 종속성: 한 작업이 다른 작업의 출력에 의존
    • 커플링: 전역 변수와 같은 공유 처리 구성 요소 등에 두 태스크가 상호 의존
  • 위 의존성에 기반하여, 결합 수준이 낮은 태스크는 태스크 오류의 영향 범위를 줄이기 위해 다른 컨테이너에 분산하는것이 좋으며, 의존성이 높은 태스크는 동일한 컨테이너에 실행하도록 한다.
• 실행 모델: 애플리케이션(태스크와 컨테이너 작업 모두 포함)의 CPU 리소스 사용률과 엣지 서버에서 태스크의 실행 시간을 나타낸다.
  • 실행중인 태스크의 라이프사이클은 크게 세 단계로 나눌 수 있다. 태스크가 blocked되면, 입력 데이터를 메모리에 캐싱하고 CPU 리소스를 사용하지 않는다. 태스크가 모든 데이터를 입력받고 난 후에는, 태스크는 다음에 실행될 수 있도록 스케줄링된다. 태스크가 완료되면, 출력 데이터는 즉시 하위 태스크로 전송되며, 데이터 전송 기간동안 CPU 리소스를 사용하게 된다. 
    • blocked: 일부 입력 데이터를 사용할 수 없거나 예약되지 않은 경우
    • running 
    • transmitting: 출력 데이터를 전송

즉, 비효율적인 작업의 양(상호 의존적인 작업)을 줄이고, 애플리케이션 실행 시간을 낮게 유지하기 위해 규칙을 설정한다.

• 컨테이너 간 통신은 비효율적이므로, 데이터 전송량이 많은 작업을 동일 컨테이너에 할당한다.
• 적절한 작업 스케줄링을 통해 컨테이너의 수를 줄임으로써, 컨테이너의 시작 횟수를 줄인다.
• 컨테이너 간 통신을 위해 두 태스크 사이에 CPU idle time을 활용한다.
  • idle time: 병렬 컴퓨팅에서는 1) 모든 상위 작업과 2) 동일한 프로세서에서 예약된 이전 작업이 완료되기 전에는 작업을 시작할 수 없기 때문에, 이 원칙에 따라 프로세서의 idle time이 존재한다. 이 idle time 동안 컨테이너 간 통신이 제대로 수행될 수 있다면 동일한 프로세서에서 후속 작업이 지연되지 않을 수 있다.
• 실행 기간에 큰 영향을 미치는 작업 중에는 컨테이너 간 통신을 피한다.

그리고 위 규칙을 따르는 공동 스케줄링 및 컨테이너화 체계를 제안한다. 

1. 먼저 할당된 프로세서에서 작업을 스케줄링하여 '초기 스케줄'을 얻는다.
   • 이 작업에서는 컨테이너 작업이 고려되지 않는다.
2. 비효율적인 작업을 줄이기 위해, 초기 스케줄을 기반으로 태스크를 컨테이너에 매핑한다.
   • 이 작업에서 컨테이너화 체계(태스크-컨테이너 간의 매핑)가 결정된다.
3. 컨테이너 간 통신으로 인해 작업의 실행 시간이 변경될 수 있으므로 초기 스케줄을 적용할 수 없다. 따라서 컨테이너화 체계에서 얻은 새로운 작업 실행 기간을 기반으로 작업 스케줄이 업데이트 된다.

Evaluation

본 논문에서는 실제 워크플로우를 사용하여 작업과 작업 간의 종속성으로 구성된 JTSC를 평가했다. 각 태스크는 데이터 처리를 위한 일정량의 CPU 리소스 계산량 대 컨테이너 간 통신 비율(0.1, 0.5, 1, 5, 10)을 가진다. 작업 간의 종속성은 행렬로 표현되었으며, 일부 요소는 종속성 충돌을 나타내기 위해 무한대로 설정되었다.

JTSC의 성능은 컨테이너 간 전송량, 컨테이너 시작 횟수, 특정 애플리케이션의 실행 기간, JTSC의 실행 시간 등 특정 메트릭을 기반으로 평가된다.

• CPF: critical path first algorithm
• STO: start timestamp order
• ICRO: Idle-time-to-communication ratio order algorithm
• Rand: randomly search for a feasible containerization scheme
• SFD: smallest ICP
• SFC: smallest CST
• SFE: smallest NED

본 논문에 따르면 컨테이너화 알고리즘마다 컨테이너 간 통신과 컨테이너 시작 횟수를 줄이는 측면에서 장단점이 있는 것으로 나타났다. 

• 통신 집약적인 작업에는 CPF와 ICRO가 더 나은 성능을 발휘한다.
• 컨테이너를 자주 시작하고 중지해야 하는 작업에는 STO가 더 나은 성능을 발휘한다.

서로 다른 성능을 강조하는 세 가지 컨테이너화 알고리즘이 포함된 JTSC 체계를 설계하여 애플리케이션의 작업 스케줄과 컨테이너화 체계를 결정했다. 그 결과 시뮬레이션을 통해 엣지 서버의 CPU 자원, 의존도 요구사항, 다양한 스케일의 애플리케이션, 다양한 초기 스케줄 등 다양한 조건에서 비효율적인 컨테이너 운영을 줄이고 애플리케이션의 실행 효율을 지속적으로 향상시킨다는 목표를 달성했다.

단, 본 논문에서 고려한 시나리오는 단일 엣지 서버에서 FaaS 애플리케이션만을 고려한 것이므로, 보다 복잡한 환경의 시나리오를 추가하는 것이 좋을 것으로 보인다. 예를 들어,

1) 이기종 연산 능력을 갖추고 무선 네트워크를 통해 연결된 여러 엣지 서버가 있는 엣지 컴퓨팅 시스템

2) 여러 애플리케이션을 동시에 고려

3) 작업의 워크플로우로 설명할 수 없는 애플리케이션 등

Discussion

애플리케이션의 워크플로우를 생성하는 것을 내가 직접 해서 연구에 적용해보기는 어려울 것 같다.

실험 방법 등이 좀 더 자세히 나왔으면 좋았을 것 같은데 조금 아쉽다.

https://www.usenix.org/conference/atc12/technical-sessions/presentation/barker

전체적인 논문 요약

• 실제 메모리 및 특정 시나리오 두 가지의 트레이스를 사용하여 페이지 공유의 실제 문제에 대해 연구한 논문이다.
  • real world 트레이스에서는 약 15%의 sharing level 을 관찰했는데, 이는 중요하긴 하지만 예상보다는 낮은 sharing 정도였다. 흥미로운 점은, 연구에서 본 대부분의 sharing 은 self-sharing 에서 비롯되었으며, 이 경우에는 가상화가 불필요하다.
• 공유에 영향을 미치는 다양한 요소에 대한 연구를 진행했다.
  • homogeneity 플랫폼의 핵심 역할(이종 시스템보다 동종 시스템에서 비교적 많은 sharing 이 관찰됨)
  • OS 특성 및 애플리케이션 수정의 다양한 점진적인 영향 관찰(OS family, application setup, OS version, OS architecture)
  • 새로운 기술(ASLR과 같은)은 sharing 에 영향을 미칠 수 있다

아마존 EC2 와 같은 대규모 데이터 센터의 서비스의 운영자는 고객에게 기계 리소스를 임대한 다음, 고객은 임대한 기계에서 자체 애플리케이션을 운영한다. 단일 물리적 서버가 여러 고객에게 제공되어야 하기 때문에 공급자는 가상 머신을 이용하여 사용자들을 격리한다. 이러한 모델에서 메모리 효율성은 종종 개별 물리적 서버에서 서비스 제공자가 서비스할 수 있는 고객 수를 결정하는 병목 리소스가 될 수 있다. 대부분의 가상화된 시스템은 단순히 VM 간에 사용 가능한 물리적 메모리를 분할하기 때문에, 각 VM이 소비하는 메모리 양을 기반으로 시스템당 가능한 고객 VM 수가 대략적으로 계산될 수 있다. 그런데 만약, 적은 양의 메모리만 사용하여 각 고객에게 서비스를 제공할 수 있다면 주어진 서버에서 더 많은 고객을 잠재적으로 처리할 수 있으므로 활용도가 높아지고 하드웨어 비용이 절감된다.

Background & Motivation

가상 머신은 가상화를 사용한 가상 환경인데, 가상화 기술을 사용하기 이전에, 전통적인 컴퓨터에서는 물리적인 컴퓨터 하나에 하나의 OS 만 설치가 가능했다.

이런 방식에는 몇가지 문제점이 있었는데,

1. 실제 CPU 가 모두 활용된다면 가장 좋은 퍼포먼스를 낼 수 있었겠지만, 실제로 CPU 를 100% 사용하지 못하는 경우가 많았다.

2. 새로운 OS 가 필요할 때마다 컴퓨터를 추가해야하고, 이는 물리적 공간의 증가, 즉 낭비로 이어졌다.

이렇게 남는 자원을 잘 활용하기 위해서 서버 가상화 기술을 이용한 여러개의 가상 머신으로 나누어 사용하게 되었고, 각각의 가상 머신은 독립적인 물리 서버처럼 동작한다.

가상화 환경에서 메모리 주소 체계를 살펴보면, 그림과 같이 가상주소, 물리주소, 머신 주소라는 세 단계를 가진다.

가상 머신에서 동작하는 게스트 운영체제는 가상화 환경에서 동작한다는 사실을 모르는 상태이며, 하이퍼바이저의 중재 아래 실제 물리 주소로 변환해서 사용된다.

중복된 부분을 제거하고, 동일한 페이지는 공유함으로써 자원을 효율적으로 공유하기 위해 여러가지 Page Sharing 방식을 사용할 수 있다.

Page Sharing 은 크게 두가지 종류가 있을 수 있다.

• self-sharing: 개별 VM 내에서 공유하는 방식이며, 왼쪽 그림 예시를 보면 machine 당 A, B, C 3 copy 씩 존재하므로 6개의 중복 페이지들을 절약할 수 있다.
• Inter-VM sharing: 여러 VM에서 공유하는 방식이고, 오른쪽 그림 예시를 보면 하나의 shared machine 의 VM 에 3개의 unique 페이지 A, B, C 가 존재하지만, 하이퍼바이저는 copy 페이지들을 공유할 수 있으므로 6개의 중복 페이지들을 절약할 수 있다.

다시 페이지 중복 예시로 돌아와서, Inter-VM sharing 의 하나의 예시 Contents Based Page Sharing 를 알아보자.

Contents Based Page Sharing 이란 여러 VM에서 동일한 메모리 페이지를 제거하자는 아이디어로부터 시작되었다.

하이퍼바이저가 VM의 페이지들를 가져와 물리적 메모리에 매핑하고, 이 하이퍼바이저가 중복 페이지들을 탐지하여 중복을 제거하는 것이다. 이 페이지들의 원본을 copy-on-write references 로 대체하며, 과다 사용한 페이지에 대해서는 free 를 함으로써 자원을 절약 할 수 있다.

Copy-on-Write in Operating System
Copy-on-Write(CoW) 는 주로 부모 및 자식 프로세스가 초기에 동일한 메모리 페이지를 공유할 수 있도록 하는 리소스 optimization 기술입니다. 상위 또는 하위 프로세스가 공유 페이지를 수정하는 경우에만 페이지가 복사됩니다.
(데이터의 단위가 복사되었지만 수정되지 않은 경우 "복사" 는 주로 원본 데이터에 대한 참조로 존재할 수 있습니다.)

CoW 기술의 주요 의도 는 상위 프로세스가 하위 프로세스를 생성할 때마다 상위 프로세스와 하위 프로세스가 처음에 메모리에서 동일한 페이지를 공유한다는 것입니다. 따라서 만약 상위 또는 하위 프로세스가 공유 페이지를 수정하려고 하면, 이 페이지의 사본이 생성되고 수정은 다음에서만 수행됩니다. 해당 프로세스에 의해 페이지 사본이 생성되며 다른 프로세스에는 영향을 미치지 않습니다.

출처: https://www.studytonight.com/operating-system/copyonwrite-in-operating-system

이 연구와 함께 읽어보면 좋을 관련 연구는 세 가지 정도 있다.

• Memory resource management in VMware ESX server, SIGOPS 2002
  • https://dl.acm.org/doi/10.1145/844128.844146
  • 주기적으로 메모리를 스캔하여 중복을 감지하는 방법으로 접근한 연구
  • ESX Server 에 contents based page sharing 방식을 적용
  • 일부 케이스들에 대해서 30% 이상의 메모리 절약이 나타났다
• Difference Engine: Harnessing Memory Redundancy in Virtual Machines. OSDI 2008
  • https://www.usenix.org/conference/osdi-08/difference-engine-harnessing-memory-redundancy-virtual-machines
  • 서로 매우 유사한 페이지 granularity 와 patching 페이지에 대해 sharing memory 를 적용한 연구
  • sub-page level sharing 과 page patching 을 이용하는 방법
  • 일부 케이스들에 대해서 60% 이상의 메모리 절약이 나타났다
• Satori: Enlightened Page Sharing, ATC 09
  • https://www.usenix.org/conference/usenix-09/satori-enlightened-page-sharing
  • short-lived 페이지를 보는 데 집중한 연구
  • 가능한 sharing memory 의 90% 를 포착할 수 있었다는 연구 결과

이전 연구들에서는 대부분의 페이지 공유가 여러 컴퓨터에서 공통적으로 사용되는 OS 라이브러리와 같은 중복 메모리 영역으로 인해 발생한다고 제안되었다.

연구자들은 간단한 벤치마크 실험을 진행하면서, 가상화된 환경에서 발견된 공유의 상당 부분이 실제로 각 VM 내부에 있다는 사실이 발견했다. 이는 제안한 이전 연구와 반대되는 결과로, 제로 페이지를 제외하고 평균적으로 총 메모리의 436MB를 공유할 수 있지만, 이 중 2/3(67%)는 개별 VM 내 self-sharing 페이지로 인한 것이며 나머지 3분의 1은 inter-vm sharing 으로 인한 것이었다. 

(제로 페이지를 추가하여 통계를 내면, 내부 공유 비율이 3/4(77%) 이상으로 증가하게 된다.)

이는 메모리 공유가 관리되는 방식(예를 들어 더 많은 VM을 함께 배치해도 공유 수준이 크게 증가하지 않을 수 있다는 점)과

메모리 공유가 구현되는 방식(예를 들어 단일 OS 내에서 공유하는 것은 여러 VM에서 공유하는 것만큼 효과적일 수 있다는 점) 모두에 영향을 미친다.

문제 정의 및 실험 방법

• 일반적인 실제 기계에서는 어떤 수준의 page sharing 이 주로 일어날 것인가?
  • self-sharing vs inter-vm sharing
  • laboratory study와 어떻게 다른가?
• sharing potential에 영향을 미치는 요소는 무엇인가?
  • mac/win/linux (OS), mixed versions (major, minor versions), 32/64 bit (architecture of OS
  • 새로운 OS 기술이 sharing에 어떤 영향을 미칠 것인가?

• Memory Buddies Traces: collect memory snapshots every 30 minutes
  • https://traces.cs.umass.edu/index.php/CpuMem/CpuMem
• 실제 memory traces 와 시나리오 기반 추가 traces 분석
• 스캐닝과 스냅샷 을 이용하여 중복 해시를 탐지한다.

실험 결과

실제 메모리 트레이스의 Sharing 경향

먼저 실제 메모리 트레이스의 sharing 경향을 보기 위해 일주일동안 30분마다 수집한 트레이스의 self-sharing 에 대한 최대값, 최소값, 그리고 평균값에 대해 집계한 그래프를 보면 (E는 굉장히 특이한 경우이므로 제외하고 해석)

• self-sharing 의 점유율의 평균값이 10%가 넘는다
  • 이 값은 크지는 않지만 확실히 중요하다.
  • 위 집계값은 제로 페이지를 완전히 제외한 값이다.
  • 만약 제로 페이지를 추가하여 집계하면 훨씬 더 많은 self-sharing 점유율이 도출된다.
• self-sharing maximum 값이 약 50% 까지 존재한다.
  • 트레이스 수집 기간 동안 특정 시점에 많은 기계가 매우 높은 수준의 내부 중복성을 가지고 있었음을 알 수 있다.
• minimum 값을 보면 트레이스 수집 일주일간 항상 최소 약 5% 이상의 내부 중복 가능성을 보여주었다.

Inter-VM sharing 경향을 보면, (그래프는 inter-VM sharing 이 가장 높은 쌍 6개를 보여주고 있음)

inter-VM sharing의 평균값은 약 2%로 매우 낮으며, 나머지 15개의 페어링에서는 더 낮은 0.1% 의 inter-VM sharing 이 관찰되었다.

maximum 값을 보더라도 페어링 머신에서 inter-VM sharing은 6%를 넘지 않았다.

왜 self-sharing 이 크게 나타났을까? 그 이유를 알아보고자 케이스 스터디가 진행되었다.

linux desktop 에서 linux memory tracker 를 사용하여 트레이스 추출하게 되면, 페이지의 내용과 이를 사용하는 프로세스를 추적할 수 있고, 개별 페이지의 해시 값을 알 수 있다고 한다.

이 트레이스의 sharing 참여도를 분석해 본 결과, 왼쪽 그래프를 보면, 데스크 탑 애플리케이션을 분석한 것이라 그런지 GUI 프로세스가 메모리 사용량을 지배한다는 점을 알 수 있다.

오른쪽은 개별 공유 라이브러리와 나머지 요소들의 sharing 참여도를 분석한 그래프인데, x축의 빨간 색은 개별 공유 라이브러리를 각각 나타내고, 파란색의 libraries는 전체 공유 라이브러리 합계, heap은 모든 프로그램 힙, 그리고 stacks은 모든 프로그램 스택을 나타낸다.

그래프를 보면 50%에 달하는 self-sharing 이 프로그램 힙과 관련이 있음을 알 수 있다.

이렇게 힙 페이지가 가장 많이 공유되고 있는 상황은 특정 데이터 구조를 반복적으로 할당하고 해제하는 부산물일 가능성이 높다.

왜냐하면 페이지 사본에는 현재 사용중인 페이지 뿐만 아니라 OS 에서 아직 회수하지 않은 오래된 페이지가 포함될 수 있기 때문이다.

공유 라이브러리 중 가장 많이 공유되는 단일 라이브러리는 Firefox에서 사용하는 사용자 인터페이스 라이브러리인 libxul이다. libc와 같은 다른 라이브러리가 더 널리 사용되지만, 전반적으로 훨씬 적은 공유에 관여했다.

위 결과로 해당 프로세스들에서 데이터 할당이 중복되고 자체 공유가 많이 발생함을 알 수 있었다.

Sharing 에 영향을 주는 요소

Sharing 에 영향을 줄 수 있는 요소로 플랫폼의 동질성을 생각해 볼 수 있다.

먼저 real-world 트레이스 분석과 같이 self-sharing 에 대한 영향을 분석해보면,

OS 제품군 및 버전을 보는 것만으로도 상당한 차이점이 있음을 알 수 있다.

MAC, Windows XP VM의 경우 Windows 7, Linux VM 들에 비해 훨씬 더 높은 self-sharing 을 나타낸다.

(=> Mac OS X 및 Windows XP 시스템이 더 높은 수준의 내부 메모리 중복성을 지향하는 경향이 있으며 이 중복성을 활용하면 더 큰 이점을 볼 수 있음)

특히 VM이 새로 부팅되었지만 더 이상 소프트웨어를 실행하고 있지 않음을 나타내는(no-app) 빨간 바를 보면, 

server 또는 desktop 과 같이 응용 프로그램을 추가할 때 공유가 no-app에 비해 크게 바뀐점이 없다는 것을 알 수 있다. 

이는 기본 시스템이 대부분의 self-sharing 을 제공하며, user-level applications에서는 아주 작은 sharing 증가를 포함한다는 점을 뜻한다.

또 다른 흥미로운 점은 32비트 시스템에서 64비트 시스템으로 전환할 때 Ubuntu의 두 버전에서 공유하는 기본 시스템이 크게 감소한다는 것이다. (=> 32비트 시스템 라이브러리보다 64비트 시스템 라이브러리에서 더 낮은 수준의 중복성을 나타낸다.)

참고로 두 버전에서 CentOS 에 대해 공유하는 비율은 매우 낮다. 

이는 앞쪽의 process 별 분석에서 추론할 수 있듯이, 주로 GUI가 없기 때문이라고 볼 수 있다.

이제 플랫폼 동질성에 대한 Inter-VM Sharing 영향을 분석해보면,

모든 페어링에 대한 완전한 결과는 그래프에 생략되어 있지만 대표적인 샘플은 그림 8 과 9에 나와 있다.

그림 8은 선택된 페어링에 대한 Inter-VM Sharing 의 메가바이트 단위 절대적인 값을 보여주고, 

그림 9는 각 페어링에 대한 self-sharing 과 inter-VM sharing 의 상대적 중요성을 보여준다.

첫 번째 알 수 있는 점은 major OS (Mac OS X - Windows 또는 Linux) 간의 페어링에서는 Inter-VM sharing 이 무시할 수 있는 정도라는 점이다. 그래프 외의 모든 경우에 대해, 이러한 쌍은 그림 8에서 볼 수 있는 것처럼 mac/win7-64 쌍과 매우 유사하다.

그래프를 보면 no-app(기본 시스템) 의 inter-vm sharing 은 거의 없고, 서버 애플리케이션이나 데스크탑 애플리케이션을 셋업 했을 때 아주 작은 inter-vm sharing 을 관찰 할 수 있다.

애플리케이션 셋업 시 작은 inter-vm sharing 이 관찰 된 이유는 공유 리소스 파일 때문일 가능성이 높고, 그래서 서버 케이스보다 데스크탑 케이스에서 훨씬 더 크다고 생각할 수 있다.

두번째 알 수 있는 점은 공통 major 플랫폼의 다른 버전을 함께 사용하면 no-app(기본 시스템)에서 inter-vm sharing 이 매우 작은 값이지만, 공통 응용 프로그램의 경우 inter-vm sharing 의 비율이 증가됨을 관찰 할 수 있다.

기본 시스템에는 inter-VM sharing 이 5% 미만으로 거의 없지만, 애플리케이션을 셋업 하면 inter-VM sharing 양이 크게 증가한다.

이는 office 프로그램과 같은 많은 응용 프로그램 자체가 이러한 시스템에서 동일한 버전을 실행하여 상당한 양의 inter-VM sharing 이 추가되기 때문이다.

마찬가지로, Ubuntu 페어링을 살펴보면, Ubuntu 10.04와 10.10 32비트 간에 75% self-sharing 을 살펴봤을 때, no-app 기본 시스템에서 inter-vm sharing 이 매우 작은 값이라는 점을 알 수 있지만, 앱 셋업을 하게 되면 상당한 응용 프로그램 공유가 표시된다.

세번째로 inter-vm sharing 에 영향을 줄 수 있는 요소로 os architecture 가 있다.

32비트에서 64비트로 OS architecture 을 변경할 때를 관찰해보면, 대부분의 inter-vm sharing 을 완전히 제거하는 주요 OS 버전을 변경하는 것보다 훨씬 "덜" 영향이 있다.

아키텍처별 동작을 볼 수 있는 한 가지 주목할만한 사례는 두 개의 64비트 Ubuntu 버전(ub04-64/ub10-64)을 페어링할 때이다. 

이 경우, no-app 시스템의 80%에 달하는 공유는 self-sharing 이 아닌 inter-vm sharing 으로 인한 것이다.

그 이유는 이전에 그림 7에서 볼 수 있는 것처럼 두 시스템 모두 self-sharing 이 최소화되었기 때문일 수 있다.

정리하자면, family, applications, version, architecture 순으로 inter-VM sharing 을 감소시키는 영향이 크기 때문에,

inter-VM sharing 을 개선하기 위해 family, applications, version, architecture 순으로 수정해보는 노력을 할 수 있다.

Memory Security and Sharing

마지막으로 OS 기술의 발전이 sharing 에 어떤 영향을 미치는지 알아보자.

운영 체제 설계자는 공격자로부터 시스템을 강화하고 악용 기회를 줄이기 위한 새로운 방법을 끊임없이 모색하고 있다. 

한 가지 일반적인 공격은 메모리 버퍼 오버플로 공격이다. 만약 메모리 오버플로우가 일어나서 덮어쓴 메모리가 키 라이브러리 기능과 같이 알려진 주소에 있는 경우에는 메모리를 다루는 데에 오류가 발생하여 잘못된 동작을 야기할 수 있다. 이러한 종류의 공격에 대해 시스템을 강화하기 위해, 최신 운영 체제는 메모리에서 주요 라이브러리 및 프로그램 리소스(예: 힙)의 위치를 ​​무작위로 지정하는 주소 공간 레이아웃 무작위화 기술을 사용한다. 

이 기술은 공격자가 알려진 주소를 사용하는 것을 방지하기 위해 설계되었으며, 그림 13a에 표시된 주소 공간의 예에 대해 두 가지 가능한 무작위화가 그림 13b 및 13c에 나와 있다.

주소 공간 레이아웃 무작위화는 좋은 보안 수단이지만, 동일한 VM 에 대해 메모리 적재 시마다 달라지는 기법이므로, 페이지 공유 가능성에 영향을 미칠 가능성이 있다. ASLR이 활성화된 경우에는 동일한 소프트웨어를 실행할 수 있는 두 VM의 메모리 내용이 달라질 수 있으므로 공유 가능성이 줄어든다. 예를 들어, 그림 13b 및 13c에서 보여주는 랜덤화된 주소 공간은 랜덤화되지 않은 경우보다 더 적게 공유할 수 있다. 

연구에서는 여러 운영 체제에서 여러 구현을 평가하여 ASLR이 공유 가능성에 미치는 영향에 대한 연구를 수행했다.

• Ubuntu 10.10 64비트 (표준 Ubuntu 커널 버전/패치된 PaX버전 2.6.32)
• Windows 7 64비트
• Mac OS X 10.7

총 4개의 기기에서 실험이 진행 되었는데, 이 실험의 의도는 4가지 ASLR 구현 각각에 대해, 무작위화가 공유에 영향을 미치는지 여부를 식별하고, 만약 그렇다면 이 영향의 범위를 결정하고자 하는 것이었습니다.

이를 위해 각각은 동일한 기본 이미지에서 부팅되는 시나리오를 시뮬레이션합니다. 

(왜냐하면 기본 이미지 부팅은 가상화와 페이지 공유 둘다 확인할 수 있는 시나리오이며, 사용자가 sharing 가능성을 fine-tuning 하게 되는 경우를 나타냅니다. )

테스트 방식은 다음과 같다.

1. ASLR을 전역적으로 비활성화

2. VM을 재부팅하여 메모리를 안정적인 상태로 재설정하고, 셸 스크립트 또는 배치 파일을 사용하여 미리 정의된 응용 프로그램 목록(웹 브라우저, 텍스트 편집기, 사무용 소프트웨어, 음악 플레이어 등)을 열어 VM의 메모리를 채운다.

3. 메모리 내용이 안정화된 후, '무작위화되지 않은' 메모리 스냅샷을 캡처한다.

4. ASLR을 전역적으로 활성화한다.

5. 재부팅한 다음 스냅샷 절차를 다시 반복하여 '무작위' 스냅샷을 얻는다.

공유 감소 비율에 대한 결과는 그림 14 에 확인할 수 있다. 총 공유 감소는 self-sharing 및 inter-VM sharing 으로 더 세분화되어 분석했습니다. – 주의할 점은, self-sharing 과 inter-vm sharing 이 총 sharing 에 동등하게 기여하지 않기 때문에 total-sharing 에는 이들 값이 추가되지 않는다는 점이다.

ASLR 을 활성화 하게 되면, total sharing 이 작지만 눈에 띄게 감소하는 것을 볼 수 있다. 

주의할점은 Mac 은 시스템 자체에 대해 무작위화가 비활성화되지 않았으므로. 눈에 띄는 total sharing 감소를 관찰 할 수 없었다.

(Mac Lion 내에서 무작위화를 비활성화하는 직접적인 방법은 없습니다. – 알려진 유일한 방법은 프로세스 생성 중에 특정 POSIX 플래그를 설정하는 것입니다. 이를 활용하기 위해 단순히 이 플래그를 설정한 다음, 무작위화 없이 실행되는 대상 응용 프로그램을 생성하는 스크립트를 작성합니다.)

이외의 다른 sharing 들을 약 10% 이상의 total sharing 감소가 관찰되었다.

좀더 자세히 보면, Linux의 경우 ASLR은 self-sharing 및 inter-vm sharing 모두 줄였다. 

그러나 Windows의 경우, total-sharing 이 inter-vm sharing 으로 인한 것이었다. windows 에서 self-sharing은 시스템은 무작위화에 상관없이 동일한 양을 공유한 것이다. 이는 가상화되지 않은 환경에서, Windows에서의 공유가 ASLR의 영향을 전혀 받지 않는다는 것을 의미한다. 

Mac OS X에서는 Windows와 반대 동작이 관찰되었는데, inter-vm sharing 감소가 관찰되지 않았기 때문에 여기에서 모든 감소는 모두 self-sharing 으로 인한 것이다. 이에 대한 한 가지 이유는 자체 공유의 상대적인 양일 수 있다. (그림 7. 앞쪽에서 확인했듯이 Mac OS X의 자체 공유는 Windows 7보다 훨씬 높음)

결론

결론적으로 페이지 공유는 메모리 효율성을 높일 수 있는 기회를 제공하기 위해 나온 개념이지만, 

메모리 효율성을 증가시키는 이점을 극대화 하기 위해서는 페이지 공유에 영향을 미치는 요인을 이해하는 것이 중요하다. 

이 연구에서는 페이지 공유의 소스에 대한 조사 및 분석을 제시하며 많은 경우 공유 가능성의 대부분은 여러 시스템, Inter-VM Sharing 이 아니라 단일 시스템, Self-Sharing 의 중복성에 기인한다는 것을 발견했다. 이것은 Sharing 이 가상화된 시스템에 제한될 필요 없이 단일 VM 수준에서 또한 효과적으로 활용될 수 있음을 시사한다.

또한, VM 간 공유를 위해, 여러 애플리케이션 플랫폼을 조사하고 운영 체제 동질성이 Inter-VM Sharing 의 가장 중요한 구성 요소라는 점을 발견했다. (애플리케이션과 아키텍처 및 버전 동질성은 그 다음 요소)

그리고, Linux 커널 내에서 자체 공유에 대한 Case Study 를 수행하고, GUI 응용 프로그램 및 관련 시스템 라이브러리가 자체 공유 가능성의 가장 명확한 소스임을 발견했다. (Linux 외 다른 OS 에서도 동일한지 향후 연구로 남겨 둠)

마지막으로, 주소 공간 레이아웃 무작위화가 공유 가능성에 미치는 영향을 조사했다. 그 결과 모든 주요 시스템에서 이 기능이 공유 잠재력에 측정 가능한 부정적인 영향을 미친다는 것을 발견했다.

Linux와 같은 상용 커널은 제한된 유형 및 메모리 안전 보장 만 제공하는 저수준 프로그래밍 언어로 작성되어

공격자가 메모리 손상 취약성을 악용하여 커널에 대해 정교한 런타임 공격을 시작할 수 있다.

아래 논문을 읽고, 리눅스 커널 취약점과 각 도구의 특징 및 구조를 비교해 보았다.

[ACM 2011] Linux kernel vulnerabilities: State-of-the-art defenses and open problems

[CCS 2016] UniSan: Proactive Kernel Memory Initialization to Eliminate Data Leakages

[NDSS 2018] K-Miner: Uncovering Memory Corruption in Linux

[USENIX 2019] PeX: A permission check analysis framework for Linux kernel

[NDSS 2021] KUBO: Precise and Scalable Detection of User-triggerable Undefined Behavior Bugs in OS Kernel

커널은 종종 신뢰할 수있는 컴퓨팅 기반의 일부이기 때문에 커널 취약성을 방지하는 것은 많은 시스템의 보안을 달성하는 데 중요하다. Linux 커널 취약성에 대한 두 가지 사례 연구를 제시하여 커널 보호 기술과 관련하여 현재의 최신 기술을 평가하고 있다.

Linux에는 10 가지 일반적인 커널 취약점 클래스가 있으며,이 취약점은 임의의 메모리 수정에서 정보 유출, 서비스 거부 공격에 이르는 다양한 공격으로 이어질 수 있다. 취약점의 약 2/3가 커널 모듈이나 드라이버에 있고, 반대로 1/3의 버그가 코어 커널에서 발견되며, 단일 기술이 모든 커널 취약점을 막을 수는 없다.

• Missing Pointer Check - 커널은 access_ok 검사를 생략하거나 __get_user와 같은 더 빠른 작업을 오용한다. 이 작업은 사용자가 제공한 포인터 또는 인덱스 변수의 값을 확인하지 않고 사용자 공간 메모리만 가리키도록 함. ⇒ 권한이없는 프로세스가 임의의 커널 메모리 위치에서 읽거나 쓸 수 있도록하여 메모리 손상 (CVE-2010-4258), 정보 공개 (CVE-2010-0003), DoS (CVE-2010-2248) 또는 권한 에스컬레이션(CVE-2010-3904 및 CVE-2010-3081)으로 이어진다.
• Missing Permission Check - 커널은 호출 프로세스에 권한이 있는지 여부를 확인하지 않고 권한있는 작업을 수행한다. 이 범주의 취약점은 커널 보안 정책을 위반하게 된다. ⇒ 임의 코드 실행 (CVE-2010-4347), 권한 상승 (CVE-2010-2071 및 CVE-2010-1146), append-only 파일 덮어 쓰기(CVE2010-2066 및 CVE-2010-2537)
• Buffer Overflow - 커널이 버퍼에 액세스 할 때 상한 또는 하한을 잘못 확인하고 (CVE-2011-1010), 예상보다 작은 버퍼를 할당하고 (CVE-2010-2492), 안전하지 않은 문자열 조작 함수를 사용한다(CVE-2010-1084). 또는 커널 스택에 비해 너무 큰 지역 변수를 정의한다(CVE-2010-3848). ⇒ 메모리 손상 (쓰기 용) 또는 정보 공개 (읽기 용) 공격을 하며 공격자는 근처의 함수 포인터를 덮어 쓰고 커널의 제어 흐름 무결성을 파괴하여 권한 상승 공격을 수행 할 수 있다.
• Integer Overflow - 커널이 정수 연산을 잘못 수행하여 정수 오버플로, 언더 플로 또는 부호 오류가 발생하면, 공격자는 메모리를 할당하거나 액세스하는 데 잘못된 값을 사용하도록 커널을 속여 <버퍼 오버플로> 취약점이 허용하는 것과 유사한 공격을 허용 할 수 있다. ⇒ 곱셈 후 overflow가 발생하면 커널이 필요보다 작은 버퍼를 할당 할 수 있다(CVE-2010-3442). 빼기 후 underflow은 버퍼 끝을 넘어서 메모리 손상을 일으킬 수 있다(CVE-2010-3873). 비교 중 부호 오류는 경계 검사를 우회하고 정보 공개를 유발할 수 있다(CVE-2010-3437).
• Uninitialized data - 커널은 사용하지 않는 필드를 제로화하지 않고 커널 버퍼의 내용을 사용자 공간에 복사하므로 커널 스택의 변수와 같은 잠재적으로 민감한 정보가 사용자 프로세스에 유출된다 (CVE-2010-3876). ⇒ 이 범주에는 모든 범주 중 가장 높은 29 개의 취약점이 있고, 의도하지 않은 정보 공개를 초래한다. 또한 일부 커널 데이터 구조의 정확한 주소, 개인 커널 키 또는 기타 커널 임의성을 알아야하는 공격과 같은 다른 공격을 가능하게 할 수 있다.
• Memory mismanagement - 외부 메모리 소비 (CVE-2011-0999), 메모리 누수 (CVE-2010-4249), 이중 사용 가능 (CVE-2010-3080) 및 사용 후 사용 오류 (CVE-2010-3080)와 같은 커널 메모리 관리의 취약성이 포함된다. (CVE-20104169 및 CVE-2010-1188). ⇒ 일반적으로 임의의 메모리 손상이 가능하며, 공격자는이를 악용하여 DoS 공격을 수행 할 수 있다.
• Miscellaneous - 널 포인터 역 참조, 0으로 나누기 (CVE-2011-1012 및 CVE2010-4165), 무한 루프 (CVE-2011-1083 및 Null 포인터 역 참조)와 같이 일반적으로 프로세스 충돌, 커널 패닉 또는 중단을 초래할 수 있다(CVE-2010-1086) 교착 상태 (CVE-2010-4161), 데이터 경합 (CVE-2010-4526 및 CVE-2010-4248).

• 해결 방안
  • Runtime Tools
    • Software fault isolation (BGI Tool) - 커널과 모듈 간의 제어 된 공유를 지원하여 커널 모듈을 분리하는 도구이며, BGI는 각 모듈에 대한 메모리 액세스 제어 목록(ACL)을 제공한다. BGI를 사용하는 프로그래머는 ACL을 설정하고, 핵심 커널에서 다양한 기능을 호출 할 때 모듈의 권한을 부여하거나 취소할 수 있다 (예 : 메모리 할당시 액세스 권한 부여, 메모리 해제시 액세스 취소).
      • 장점 - BGI는 취약한 모듈이 이중없는 버그 및 일부 버퍼 오버 플로우와 같이 액세스 권한이 없어야하는 커널 메모리를 덮어 쓰는 것을 방지 할 수 있다.
      • 단점 - 액세스 권한이 있어야하는 커널 메모리에 대한 액세스는 허용한다. 즉, 모듈 내부의 취약점과 버그가있는 모듈의 경계를 넘으려는 특정 공격만 처리한다.
      • ex) 파일 시스템 모듈에 버퍼 오버플로 취약점이있는 경우 공격자는 모듈의 내부 데이터를 변조하고 모듈이 setuid 바이너리에만 적용되는 코드를 실행하도록 속여 루트 권한을 얻을 수 있음
    • Code integrity (SecVisor) - 커널에 코드 무결성을 적용한다. 얇은 하이퍼 바이저 계층은 해당 코드가 커널 모드에서 실행되도록 허용되기 전에 모든 코드를 인증한다.
      • 장점 - SecVisor는 코드 삽입 공격을 방지하는 데 효과적이다.
      • 단점 - SecVisor의 존재를 인식하지 못하는 일반적인 공격을 방어 할 수는 있지만 지속적인 공격자는 중요한 커널 데이터를 손상 시키거나 기존 커널 코드에 대한 제어 흐름을 가로 채어 공격을 가할 수 있다. 즉, SecVisor는 공격을 작성하기 어렵게 만들지만 공격자가 취약성을 악용하는 것을 막지는 못한다.
    • User-level drivers (SUD)
      • 장점 - 사용자 수준에서 장치 드라이버를 실행하고 드라이버의 취약점이 커널의 나머지 부분에 영향을 미치지 않도록 한다. (드라이버 자체를 충돌시켜 서비스 거부 공격으로 전환) DoS 영향을 완화하려면 섀도우 드라이버와 같은 별도의 복구 메커니즘이 필요하다.
      • 한계점 - 커널 보안 취약성의 극히 일부만이 장치 드라이버에서 발생하며, 사용자 수준 드라이버가 다른 취약성은 해결하지 못한다.
    • Memory tagging (Raksha)
      • 장점 - 커널 코드가 신뢰할 수 없는 입력 (사용자 프로세스 또는 네트워크에서)을 오용하는 경우, 이를 감지하여 공격자가 코드 삽입 공격을 수행하거나 제어 흐름을 장악하는 것을 방지 할 수 있다.
      • 단점 - SecVisor와 마찬가지로 이는 커널 제어 흐름에 의존하지만 다른 많은 취약점을 해결하지 못하며 특정 유형의 악용만 방지한다.
    • Uninitialized memory tracking
      • Kmemcheck - 주어진 워크로드에 대해 초기화되지 않은 메모리 취약성을 감지하는 Linux 커널의 런타임 도구로, 커널 메모리 할당 자의 도움으로 각 메모리 바이트의 초기화 상태를 추적한다.
        • 장점 - 커널 코드가 초기화되지 않은 메모리를 통해 민감한 데이터를 유출하는 문제를 구체적으로 해결할 수 있다.
        • 단점 - 스택에서 초기화되지 않은 데이터 읽기를 감지 할 수 없다.
      • SD (Secure Delocation)
        • 장점 - 주기적으로 커널 스택을 제로화하여 초기화되지 않은 스택 변수의 정보 누출을 줄인다.
        • 단점 - 동적으로 할당 된 객체를 처리하지는 않는다.
      • 단점 - 버그를 악용하기 더 어렵게 만들지만 모든 정보 공개 버그를 찾아 예방할 수는 없다.

• 한계점
  1. 취약점은 장치 드라이버, 커널 모듈 및 핵심 커널 코드를 포함하여 커널의 거의 모든 부분에 존재하므로, 커널 모듈과 같이 커널의 한 부분에만 집중하는 솔루션은 그 자체로는 충분하지 않다.
  2. 많은 런타임 도구는 특정 종류의 취약성에 대한 악용을 방지하는 대신 특정 종류의 악용을 방지하는 데 중점을 두기 때문에, 주어진 취약점을 알고있는 공격자는 대상 시스템에서 작동하는 모든 악용을 자유롭게 선택할 수 있으므로 차이점이 중요하다. 따라서 어떤 방식 으로든 취약성을 악용 할 수있는 방어 메커니즘은 제한적으로 사용된다.
  3. Linux가 안전하지 않은 언어로 모놀리식하게 작성되었다는 사실에서 많은 취약점이 계속해서 발생한다.

UniSan: Proactive Kernel Memory Initialization to Eliminate Data Leakages

운영 체제 커널은 대부분의 컴퓨터 시스템에서 사실상 신뢰할 수있는 컴퓨팅 기반이다.

OS 커널을 보호하기 위해 공격 (예 : 코드 재사용 공격)을 방어하기 위해 kASLR 및 StackGuard와 같은 많은 보안 메커니즘이 점점 더 많이 배포되었지만, 이러한 보호의 효과는 아직 부족하다. 커널에는 무작위 포인터 또는 canary를 유출하여 kASLR 및 StackGuard를 우회하는 많은 정보 유출 취약성이 있다. 암호화 키 및 파일 캐시와 같은 커널의 다른 민감한 데이터도 유출 될 수 있다. 대부분의 커널 정보 누출은 초기화되지 않은 데이터 읽기로 인해 발생한다. 안타깝게도 메모리 안전 시행 및 동적 액세스 추적 도구와 같은 기존 기술은이 위협을 완화하기에 충분하거나 효율적이지 않다.

UniSan - OS 커널에서 초기화되지 않은 읽기로 인한 모든 정보 유출을 제거하기위한 새로운 컴파일러 기반 접근 방식으로, 할당이 커널 공간을 떠날 때 완전히 초기화되었는지 여부를 확인하기 위해 바이트 수준, 흐름 민감, 컨텍스트 민감 및 필드 민감 초기화 분석 및 도달 가능성 분석을 사용한다. 그렇지 않은 경우 커널을 자동으로 계측하여 이 할당을 초기화한다. UniSan의 분석은 오탐을 방지하기 위해 보수적이며 OS 커널의 의미를 보존하여 강력하다. UniSan을 LLVM 패스로 구현했고, 43 개의 알려진 데이터 및 많은 새로운 초기화되지 않은 데이터 유출 취약점을 성공적으로 예방할 수 있다. 또한 최신 커널의 19 가지 새로운 취약점이 Linux와 Google에 의해 확인되었다. LMBench, ApacheBench, Android 벤치 마크 및 SPEC 벤치 마크를 사용한 광범위한 성능 평가에서도 UniSan이 무시할 수있는 성능 오버 헤드를 부과하는 것으로 나타났다.

<특징>

• 초기화되지 않은 데이터 읽기로 인한 커널 정보 누출을 방지하는 데 중점을 둔다.
• 정적 분석에 의해 안전하지 않은 것으로 감지 된 할당 된 메모리를 선택적으로 제로화
• 자동화 된 컴파일러 기반 접근 방식 ⇒ 소스 코드를 수동으로 수정할 필요가 없으며 데이터 구조 패딩 또는 부적절한 초기화로 인한 누출을 투명하게 제거 할 수 있다.
• 절차 간 정적 분석을 활용하여 1) 할당이 커널 공간을 벗어나는지 여부와 2) 할당이 누출 지점까지 가능한 모든 실행 경로를 따라 완전히 초기화되었는지 확인 ⇒ 이전의 강제 초기화 접근 방식의 모든 한계를 극복
• 커널 공간을 떠나기 전에 가능한 실행 경로에서 초기화 된 것으로 입증 될 수없는 할당의 1 바이트가있는 한 안전하지 않은 것으로 간주된다.(보수적인 판단) ⇒ 거짓 음성이 없다.
• 스택 및 힙 할당을 모두 처리하며, 정밀도를 향상시켜 오탐을 최소화하기 위해 UniSan의 분석은 세분화되어 할당의 각 바이트를 흐름과 상황에 맞는 방식으로 추적 ⇒ 안전하지 않은 할당을 감지하면 할당의 초기화되지 않은 부분을 0으로 설정하도록 커널을 계측

<구조>

Unisan(Uninitialized Data Leak Sanitizer): 정적 분석에 의해 안전하지 않은 것으로 감지 된 할당 된 메모리를 선택적으로 제로화

UniSan은 분석 및 계측이 수행되는 커널 소스 코드에서 컴파일 된 LLVM IR (즉, 비트 코드 파일)을 입력으로 사용하고, 출력으로 보안 IR을 자동으로 생성한다.

• 할당 감지기
  • 커널을 분석하고 완전히 초기화되지 않은 채 커널 공간을 벗어날 수있는 모든 잠재적 안전하지 않은 개체를 보수적으로 식별
  • 도달 가능성 분석 및 초기화 분석을 통합하여 커널 공간을 떠날 때 할당 바이트가 초기화되지 않았는지 확인한다.
  • 스택 또는 힙 할당이 주어지면 UniSan은 정적 데이터 흐름 (taint) 분석을 활용하여이 할당이 copy_to_usr 및 sock_sendmsg와 같은 사전 정의 된 싱크에 도달 할 수 있는지 확인한다. ⇒ 전파 경로를 따라 UniSan은 할당의 각 바이트에 대한 초기화 상태도 추적한다. 할당의 바이트가 가능한 실행 경로에서 초기화되지 않은 채 싱크에 도달하면 UniSan은이를 안전하지 않은 것으로 간주한다.
• 할당 initializer
  • memset를 삽입하거나 할당 플래그를 변경하여 초기화되지 않은 메모리를 제로화, 즉 감지 된 안전하지 않은 할당을 자동으로 초기화
  • 모든 안전하지 않은 할당을 수집 한 후 UniSan은 바로 뒤에 초기화 코드를 사용하여 IR을 계측한다.
  • 스택 할당의 경우 UniSan은 memset 또는 zero-initiailzation을 삽입하여 초기화한다.
  • 힙 할당의 경우 UniSan은 할당 함수 (예 : kmalloc)에 __GFP_ZERO 플래그를 추가한다.
  • 계측 된 비트 코드 파일을 조립하고 연결하여 UniSan은 보안 커널 이미지를 생성한다.

<평가>

• 약 2000개의 모듈
• 약 1,500 개의 안전하지 않은 스택 할당과 300 개의 안전하지 않은 힙 할당을 감지
• 최신 Linux 커널 및 Android 커널에서 19 개의 새로운 초기화되지 않은 데이터 유출을 확인
• I / O 집약적 인 서버 프로그램에 미치는 성능 영향을 측정하기 위해 ApacheBench를 사용하여 Apache 웹 서버의 성능을 테스트

<장단점>

• 장점
  • 바이트 수준 감지를 수행하므로 정적으로 할당 된 총 바이트 수와 감지 된 안전하지 않은 바이트도 보고할 수 있다
  • 초기화 횟수를 최소화하여 성능 오버 헤드를 제어 할 수 있다. ⇒ 최대 오버 헤드는 7.1 %입니다. 또한 UniSan의 성능 오버 헤드는 대부분의 경우 무시할 수있는 수준 (<1 %)임을 알 수 있다.
• 한계점
  • 커널 소스 코드가 필요하다
  • 제로 초기화의 보안적 영향 - 일부 시스템은 초기화되지 않은 메모리를 임의의 소스로 사용하는데, (ex. OpenSSL의 SSLeay 구현은 초기화되지 않은 버퍼를 엔트로피 소스로 사용하여 난수를 생성 - ssleay_rand_bytes () 참조) 제로 초기화는 이러한 임의성 소스의 엔트로피를 감소시킨다.
  • false positive - UniSan은 정확도를 희생하여 거짓 음성을 제거하고 있다. (즉, 거짓 양성 비율을 높임).
  • 기본 커널 구성에서 활성화 된 모듈만 포함되고 있다. 현재 Linux 커널에는 총 20,000 개의 모듈이 있으므로 대부분은 평가에 포함되지 않았고, LLVM에서 컴파일 할 수 없는 모듈도 많기 때문에 패치를 위해 추가적인 노력이 필요하다.
  • user space 프로그램을 지원하기 위해서는 라이브러리의 IR도 포함하고 소스 (힙용)와 싱크를 재정의 해야 한다.

K-Miner: Uncovering Memory Corruption in Linux

<특징>

• Linux와 같은 대형 상용 운영 체제 커널을 효율적으로 분석하고 가능한 메모리 손상을 감지 할 수 있는 프레임워크
• 커널 코드의 고도로 표준화 된 인터페이스 구조를 활용하여 확장 가능한 포인터 분석을 가능하게 하고, 상황에 맞는 글로벌 분석을 수행
• 최신 OS 커널의 정확한 절차 간 정적 분석을 가능하게하기 위해 대규모 코드 기반, 복잡한 상호 의존성 및 전역 커널 포인터와 메모리 개체 간의 aliasing 관계 처리와 같은 여러 가지 문제를 해결한다.
• 절차 간 분석을 통해 K-Miner는 댕글링 포인터, 사용자 애프터 프리, 이중 자유 및 이중 잠금 취약성과 같은 여러 등급의 메모리 손상 취약성을 체계적이고 안정적으로 발견할 수 있다.
• 제시된 프레임 워크는 확장 가능하며 추가 분석 패스를 추가하는 것은 간단하다. K-Miner에는 보고 및 협업을 용이하게하는 웹 기반 사용자 인터페이스가 포함되어 있다. 또한 경보수 및 성능에 대한 광범위한 그래프 기반 분석 개요 및 통계를 제공한다.

<구조>

1. 기존 컴파일러 제품군 LLVM 위에 구축된다. 컴파일러(1 단계)는 두 개의 입력을 받는다.
   • 선택한 커널 기능 목록이 포함 된 구성 파일 - 사용자는 개별 커널 기능을 선택하거나 선택 취소 할 수 있다. (기능이 비활성화되면 해당 코드가 구현에 포함되지 않음) 따라서 분석 결과는 특정 쌍의 커널 코드 및 구성 파일에 대해서만 유효하다.
   • 컴파일러 제품군은 구성에 따라 커널 코드를 구문 분석합니다. 코드를 구문 적으로 확인하고 AST (추상 구문 트리)를 만든다. 그런 다음 컴파일러는 내부적으로 AST를 소위 중간 표현 (IR)으로 변환한다.이 표현은 본질적으로 추상적인 가상 머신 모델을 나타낸다. IR은 일련의 변환 과정을 통해 커널 코드를 분석하고 최적화하는 데도 사용된다.
2. 컴파일러는 커널의 IR을 K-Miner에 대한 입력으로 전달하여 모든 시스템 호출 목록을 통해 코드를 정적으로 확인한다.
   • 모든 시스템 호출에 대해 K-Miner는 시스템 호출 함수의 진입점을 다음과 같이 사용하여 호출 그래프 (CG), 값 흐름 그래프 (VFG), 포인터 분석 그래프 (PAG) 및 기타 여러 내부 데이터 구조를 생성한다.
   • 데이터 구조가 생성되면 K-Miner는 실제 정적 분석 패스를 시작하여 시스템 호출의 제어 흐름을 분석한다.
     • 다양한 유형의 취약성에 대한 개별 패스: dangling-pointer, use-after-free, doublefree 및 double-lock 오류
   • 패스는 상황에 맞는 가치 흐름 분석으로 구현되며, 주어진 시스템 호출의 제어 흐름을 고려하여 절차 간 상황 정보를 추적하고 호출 그래프에서 내려간다.
3. 잠재적인 메모리 손상 버그가 발견되면 KMiner는 모든 관련 정보 (영향을 받는 커널 버전, 구성 파일, 시스템 호출, 프로그램 경로 및 개체)가 포함 된 보고서를 생성한다.

1. LLVM-IR은 K-Miner에 vmlinux 비트 코드 이미지로 전달되어 사전 분석을 시작하여 전역 커널 컨텍스트를 초기화하고 채운다.
2. 이 컨텍스트 정보는 개별 시스템 호출을 분석하는 데 사용되는데, 여러 분석 패스 (예 : 매달린 포인터, 사용 후 사용 및 이중 무료 검사기)를 연속적으로 실행하거나 각각 독립적으로 실행할 수 있다.
3. 다양한 유효성 검사 기술을 통해 버그 보고서를 삭제하여 오 탐지 수를 줄인다.
4. 정렬 된 보고서는 취약성보고 엔진을 사용하여 렌더링된다.

<평가>

• 기본 구성 (defconfig)을 사용하여 5가지 버전의 Linux 커널에 대해 메모리 손상 검사기를 실행
• K-Miner는 29 개의 가능한 취약점을 발견하여 총 539 개의 경보를 생성했으며, 대부분은 오탐으로 분류 되었다
• 시스템 호출 당 평균 분석 시간은 약 25 분

<장단점>

• 장점
  • 현재 Linux 커널은 2,400 만 줄 이상의 코드로 구성되어 있으며 수십 개의 서로 다른 아키텍처와 수백 개의 외부 하드웨어 용 드라이버를 지원하기 때문에, 대량의 프로그램 코드에 대한 데이터 구조와 의존성 그래프를 생성하면 궁극적으로 리소스 요구 사항이 폭발적으로 증가하게 된다. 따라서 코드를 생략하지 않고 중간 결과를 재사용 할 수 있도록 개별 분석 패스에 대한 코드 양을 줄이는 기술을 제공하며, 시스템 호출 인터페이스에 따라 커널을 분할함으로써 모든 코드를 고려하고 중요한 데이터 구조 (예 : 커널 컨텍스트)의 재사용을 허용하면서 분석 된 경로 수를 크게 줄이고 있다.
  • false positive를 과도한 근사값으로 주게 되면, 개발자가 처리 할 수없는 많은 보고서가 생성되는데 KMiner는 오탐의 수를 최소화하고 있다. 오탐의 수는 개별 분석 패스의 구현에 따라 크게 달라지므로 가능한 한 많은 정보를 활용하여 런타임에 불가능한 사례가 필요한 보고서를 제거하거나 너무 대략적인 근사치를 만들도록 분석을 신중하게 설계합니다. 또한 협업 웹 기반 사용자 인터페이스에서 개발자에게 표시하기 전에 생성 된 보고서를 삭제, 중복 제거 및 필터링할 수 있다.
  • 사용자 지정 및 확장 가능한 프레임 워크로 설계되었기 때문에 추가 검사기를 구현하는 것은 간단하다.

• 한계점
  • 경우에 따라 커널은 LLVM에서 다루지 않을 수있는 비표준 코드 구조와 사용자 정의 컴파일러 확장을 사용하는데, 이 경우 패치가 필요하다.
  • 컨텍스트 처리는 모든 후속 데이터 흐름 분석 단계의 첫 번째 단계를 나타내므로 시간이 많이 걸린다.
  • 여전히 많은 수의 false positive가 표시 되고있다. 특히, 커널 코드에서 nullness 검사에 기반한 조건부 분기가 잠재적인 use-after-free로 보고되는 경우가 많다. (정적 분석 도구에는 항상 일정한 수의 false positive가 있기 때문에 개발자는 컴파일러 경고를 확인하는 방법과 유사하게 이러한 경고를 교차 확인해야한다)
  • K-Miner의 경우, 모든 간접 callsite의 1 % 만 해결한다. 왜냐하면, K-Miner에서 사용하는 SVF는 코드 기반이 전체 커널보다 작은 각 파티션에서 실행되고 분석 범위가 상당히 제한되고 다른 파티션의 함수 포인터를 해결할 수 없어 해상도가 저하된다. 또한, PeX 논문에서 실험한 결과, defconfig보다 훨씬 더 큰 코드 기반을 포함하는 allyesconfig에서는 메모리 부족으로 인해 작동하지 않는다는 것을 발견했다.

PeX: A permission check analysis framework for Linux kernel

권한 검사는 권한있는 기능에 대한 액세스 제어를 제공하여 운영 체제 보안에 필수적인 역할을 하지만, 커널 개발자가 새로운 권한 검사를 올바르게 적용하고 큰 코드 기반과 커널의 복잡성으로 인해 기존 검사의 건전성을 확장 가능하게 확인하는 것은 특히 어렵다.

<특징>

• Linux용 정적 권한 검사 오류 탐지기로, 커널 코드를 입력으로 받아 누락되고 일관되지 않으며 중복 된 권한 검사를 건전하고 확장 가능하게 감지 할 수 있다.
• PeX는 새롭고 정확하며 확장 가능한 간접 호출 분석 기술인 KIRIN (커널 인터페이스 기반 간접 호출 분석)을 사용하여 커널 추상화 인터페이스에 사용되는 공통 프로그래밍 패러다임을 활용한다.
• KIRIN이 구축 한 절차 간 제어 흐름 그래프를 통해 PeX는 모든 권한 검사를 자동으로 식별하고 권한 검사와 권한있는 기능 간의 매핑을 추론한다.

<구조>

PeX는 LLVM 비트 코드 형식의 입력 커널 소스 코드를 공통 권한 검사로 취해 누락, 불일치 및 중복 권한 검사를 포함하여 감지 된 모든 권한 검사 오류를 분석하고 보고 한다. 그 결과 PeX는 공식적으로 문서화되지 않은 권한 검사 및 권한 있는 기능의 매핑을 생성한다.

1. 콜 그래프 생성 및 분할
   • 사용자 공간 접근 가능 함수 : 시스템 호출 진입 점을 나타내는 공통 접두어 SyS_가 있는 함수에서 시작하여 PeX는 호출 그래프를 탐색하고 방문한 모든 함수를 표시하고, 이를 사용자 공간 접근 가능 함수로 취급한다. 파티션에서 사용자가 접근 할 수있는 기능은 가능한 권한 검사 오류에 대해 조사된다.
   • 커널 초기화 기능 : 부팅 중에 만 사용되는 기능을 수집하여 중복 검사를 감지합니다. Linux 커널은 start_kernel 함수에서 부팅하고 공통 접두사 __init를 사용하여 함수 목록을 호출합니다.
2. PeX는 KIRIN의 결과를 활용하여 콜 그래프를 생성 한 다음, 이를 두 그룹으로 분할한다. 분할 된 호출 그래프는 권한 검사와 권한있는 기능간의 매핑 추론에 사용되는 ICFG (Interprocedural Control Flow Graph)를 구축하기위한 기반으로 사용된다.
   • 권한 검사 래퍼 감지주어진 권한 검사 함수에 대해 PeX는 함수의 인수를 호출 수신자에게 전달하는 함수 내의 모든 호출 명령을 검색하고, 권한 검사만 사용하는 다른 호출자를 제외하고 권한 매개 변수를 래퍼로 전달하는 호출자만 참조한다.
   • 권한 확인 오류를 정확하고 정확하게 감지하려면 전체 권한 확인 목록이 필요하다. PeX는 래퍼를 포함한 모든 권한 검사를 식별하는 프로세스를 자동화하여 래퍼 검사를 효율적으로 시행합니다. PeX는 사용자가 제공한 권한 검사의 불완전한 목록을 입력으로 받습니다. 여기서 시작해서 PeX는 호출 그래프에 대해 포워드 호출 그래프 슬라이싱을 수행하여 기본 권한 검사를 감지한다.
3. Privileged Function Detection
   • 권한 검사 오류를 효과적으로 감지하려면 권한 검사와 권한있는 기능 간의 매핑을 이해하는 것이 중요한데, PeX는 주어진 권한 검사에 의해 보호되는 권한 기능을 자동으로 식별 할 수있는 절차 간 지배자 분석을 활용한다. PeX는 ICFG 위에있는 각 권한 검사가 지배하는 호출 명령의 모든 호출자를 잠재적인 권한 기능으로 보수적으로 취급한다.
4. Non-privileged Function Filter
   • Privileged Function Detection에서의 보수적 접근 방식은 false positive를 유발할 수 있기 때문에, 4단계에서 PeX는 휴리스틱 기반 필터를 적용하여 잘못된 권한 함수를 제거한다.
5. Permission Check Error Detection
   • 마지막 단계에서는 잠재적 권한 검사 오류를 감지하기 위해 권한있는 함수의 사용을 확인하는 단계이다. 권한 검사와 권한있는 기능 간의 지정된 매핑에 대해 PeX는 해당 권한 검사를 염두에 두고 권한있는 기능에서 시작하여 ICFG의 역방향 순회를 수행한다. PeX는 관심있는 각 권한 기능에 대한 가능한 모든 경로의 유효성을 검사한다.

<평가> K-Miner 접근법과 비교

K-Miner는 분석을 위해 전체 커널 코드를 사용하는 대신 시스템 호출 단위로 커널을 분석하여 SVF의 확장성 문제를 해결했다. K-Miner는 주어진 시스템 호출에서 도달 할 수있는 커널 코드의 작은 크기의 파티션을 생성하고 해당 파티션에 SVF를 적용한다.

전반적으로 PeX는 DAC, CAP 및 LSM에 대해 각각 221, 850 및 1017 경고 (권한있는 기능별로 그룹화 됨)를 보고했다. PeX는 36 개의 버그 목록을 보고 했으며, 그중 14 개는 Linux 커널 개발자가 확인했다.

<장단점>

• 장점
  • 많은 양의 분석을 빠른 시간 내에 할 수 있다.
    • KIRIN의 효과를 강조하기 위해 유형 기반 (PeX + TYPE) 및 K-Miner 스타일 (PeX + KM) 간접 호출 분석을 사용하여 종단 간 PeX 분석을 반복한 결과, allyesconfig의 경우 PeX + TYPE 및 PeX + KM은 12 시간 실험 제한 내에 분석을 완료 할 수 없다. PeX + TYPE은 ICFG에서 너무 많은 (거짓) 모서리를 생성하고 PeX 분석의 마지막 단계에서 경로 폭발을 겪었다. 타임 아웃 전에 19 개의 버그만보고되었다. 그 동안 PeX + KM은 이전 포인터 분석 단계에서 시간이 초과되어 버그를보고하지 못했다.
• 한계점
  • 도메인 지식이있는 커널 개발자는 복잡하지 않게 오류를 식별 할 수 있지만, 연구자들은 36 개의 버그 경고를 보수적으로 보고 하도록 했다. 대신 오픈 소스로 열어 두어 커널 개발자가 권한이있는 기능을 식별하고 더 많은 실제 권한 오류를 수정하는 데 기여하도록 했다.
  • PeX에서 보고한 특정 정적 경로는 프로그램 실행 중에 동적으로 실행되지 않아 오탐지가 발생할 수 있다.
    • 이 문제를 해결하기 위해 경로 제약을 해결하는 솔루션을 고안이 필요하다.
  • 비실용적 인 수동 작업이 많다.
    • Linux 커널에 대해 125,172 개의 버그 보고서를 생성했지만 팀이 보고서 중 838 개에 불과한 두 번의 버그 검토 마라톤을 실시한 후 17개만 확인 되었습니다.

KUBO(Kernel-Undefinned Behavior Oracle): Precise and Scalable Detection of User-triggerable Undefined Behavior Bugs in OS Kernel

Undefined Behavior bugs(정의되지 않은 동작 버그: UB)는 주로 비교적 낮은 수준의 프로그래밍 언어 (예 : C / C ++)로 구현 된 소프트웨어에 상주하는 광범위한 프로그래밍 오류를 나타내며, 트리거 된 UB는 종종 권한이없는 사용자 공간 프로그램의 악용으로 이어질 수 있으며 OS 내에서 중요한 보안 및 안정성 문제를 일으킬 수 있다. 커널에서 UB를 감지하는 이전 작업은 확장성을 위해 정밀도를 희생해야했고, 그 결과 사용성을 심각하게 손상시키는 극도로 높은 오탐지 문제를 겪었다.

<특징>

• KUBO는 높은 정밀도와 전체 커널 확장성을 동시에 달성하며 새로운 Linux 커널용 정적 UB 검출기
• 사용자 공간 입력에 의해 트리거 될 수있는 중요한 UB를 감지하는 데 중점을 두고 있다.
• 높은 정밀도는 UB 트리거 경로 및 조건의 만족도에 대한 KUBO의 검증에서 비롯되고, 전체 커널 확장성은 온 디맨드 방식으로 콜 체인을 따라 점진적으로 뒤로 이동하는 효율적인 절차 간 분석을 통해 가능하다. 
• KUBO는 각 UB 명령에서 시작하여 잠재적인 사용자 공간 입력 사이트를 추적하는 주문형 증분 절차 간 분석을 수행한다. 증분 콜 체인 업 워크라고 하는 이 분석은 필요할 때 콜 체인에서 선택한 호출자 기능으로만 역 추적한다. 필요성은 BTI (Bug Triggerability Indicator)라고하는 경험적 UB 트리거 가능성 표시기에 의해 결정된다. BTI가 참으로 분석 된 후 KUBO는 종속 매개 변수를 스캔하고, 이를 오염시키는 발신자만 조사한다. 이러한 절차 간 분석 설계를 통해 KUBO는 이전 작업에서와 같이 탐지 세차를 희생하거나 절차 간 데이터를 무시하고 종속성을 제어하지 않고도 전체 커널 코드베이스를 확장하고 분석 할 수 있다.

<구조>

• 먼저 맨 처음에는 각 잠재적 UB 명령어 (UBSan에 의해 표시됨)에서 시작하여 코드 경로를 따라 다시 이동하고, UB가 사용자 공간 입력에 의해 트리거 될 수 있는지 확인한다. KUBO는 이 때, 순회 코드 경로 P와 관련된 두 가지 요구 사항을 기반으로 트리거 가능성을 결정한다. UB 조건에 관련된 변수는 사용자 공간 입력에 완전히 의존 한다. (또는 그에 의해서만 수정되어야함)
• 만약, P 및 UB 조건에 대한 경로 제약 조건이 만족될 경우, KUBO는 데이터를 정적으로 추적하고 각 UB 트리거링 변수의 종속성을 제어하여 R1을 확인한다. 현재 함수에서 R1을 결정할 수없는 경우 (ex. 그림에서 1, R1에서는 UB 조건 변수의 데이터 소스 또는 그 종속성을 아직 찾을 수 없음) KUBO는 절차 간 분석이 필요한지 BTI라는 경험적 지표를 통해 확인한다.
• BTI가 참이면(2) KUBO는 사용자 공간 입력에 의해 UB가 트리거 될 수 있다는 높은 신뢰도를 가지고, BTI는 KUBO가 분석해야하는 절차 간 경로의 수를 줄인다. BTI가 거짓(3)이면 KUBO는 증분 콜 체인 업 워크를 시작하고 선택한 호출자 함수에 대한 역방향 분석을 계속하여 R1이 유지되는지 확인한다 (즉, UB 조건부 변수가 사용자 공간 입력에서만 값을 가져옴).
  • 증분 콜 체인 업 워크는 한 번에 하나의 호출자 함수를 선택하고 R1에 대한 또 다른 검사 라운드를 위해 함수의 데이터 흐름 요약을 입력 추적 구성 요소(4)로 보낸다. 이 프로세스는 R1이 확인 / 정의되거나 기능 홉 수가 제한에 도달하면 중지된다.
  • R1이 확인 된 후 (2또는 5) 포스트 버그 분석의 일부로 KUBO는 SMT 솔버를 사용하여 경로 제약 조건 및 UB 조건이 만족 스러운지 확인하여 R2를 확인합니다. R2도 충족되면 KUBO는 나머지 버그 후 분석을 수행하여 UB가 의도하지 않은 결과를 초래할 수 있는지 여부를 최종적으로 확인하고, 그렇다면 버그 보고서(6)를 생성한다.

<평가>

• KUBO의 정확성과 완전성
  • 수동으로 설정된 Ground Truth를 기반으로 두 가지 제어 된 실험을 통해 KUBO의 FNR (false negative rate) 및 FDR (false detection rate)을 측정
  • UB로 확인 된 19 개의 CVE (S eval)가 포함 된 비교적 오래된 Linux 커널 (4.1)을 테스트했고 KUBO가 놓친 19 개 CVE 중 몇 개를 검사하여 위음성 비율을 도출
    • KUBO는 테스트 된 커널에서 19 개 CVE 중 12 개를 올바르게 감지하여 36.8 %의 위음성 비율을 나타냈다.
  • 오 탐지율을 측정하기 위해 최신 Linux 커널 (5.6.13)을 사용하고 KUBO에서 생성 한 모든 버그 보고서를 수동으로 검증
    • 총 166 개의 커널 모듈과 잠재적 UB 버그를 확인했고, 그 결과로 KUBO는 40 개의 UB 버그 보고서를 생성했다. 각 보고서를 수작업으로 조사한 결과, 그 중 29 개가 실제 UB 버그 (11 개 허위 버그)였으며, 27.5 %의 오 탐지율을 확인했다.
    • 이 비율은 오 탐지 비율이 91 % 인 대규모 코드베이스에서 작동 할 수있는 기존 UB 감지기보다 현저히 낮다.
• 전체 Linux 커널을 분석 할 때 KUBO의 성능 오버 헤드
  • 처리 시간은 다양한 복잡성으로 인해 모듈마다 다르고 모든 작업이 스레드 풀에 배치되었지만 대부분의 모듈은 16 시간 (0.5h + 4m + 15h) (파란색 막대) 내에 완료 될 수 있다. 복잡한 모듈은 에 33시간 (2h + 6m + 30h) (빨간색 막대) 인 최악의 시나리오로 훨씬 더 오래 걸린다.
  • 각 분석 단계에서 각 모듈을 하나씩 분석하는 대신 모든 작업이 스레드 풀에 배치되었으며 스레드 풀에 들어간 순간부터 완료 될 때까지 개별 모듈의 시간을 측정했다.
  • 오염 분석의 경우 대부분의 하위 시스템에서 기능별 taint 요약을 생성하는 데 30 분이 걸리지 만 드라이버 / 넷 드라이버 / inFiniband 드라이버 / gpu 및 드라이버 / 넷은 약 2시간이 걸린다.
  • 콜 그래프 분석에는 모든 모듈이 6 분 미만 소요된다.
  • KUBO의 경우 분석 시작 후 15 시간 이내에 161 개의 하위 시스템이 완료된다. 주석이 달린 양이 많고 코드베이스가 복잡하기 때문에 5 개의 하위 시스템의 경우 15 시간이 더 걸린다.
    • ex. 하위 시스템 fs, drivers : video, drivers : gpu, net 및 drivers : scsi 등
  • ⇒ KUBO는 너무 많은 오버 헤드없이 고품질의 버그 보고서를 생성 할 수 있으며, 전체 분석은 합리적인 시간 인에 완료 될 수 있다.

<장단점>

• 장점
  • KUBO는 사용자 공간 입력에 의해 트리거 될 수 있는 OS 커널에서 UB를 감지하는 데 중점을 두기 때문에, user space에서 가져온 데이터에 대한 UB의 종속성을 추적할 수 있다.
  • 높은 오탐지로 어려움을 겪는 커널에서 UB를 감지하는 이전 작업과 달리 KUBO는 데이터를 추적하고 함수 호출에서 종속성을 제어하는 새로운 절차 간 분석을 제공한다.
  • 사용자 제어 데이터를 중심으로하는 온 디맨드 증분 콜 체인 업 워크 분석을 통해 KUBO는 절차 간 데이터 흐름을 추적하여 전체 Linux 커널을 분석 할 수 있다.
    • KUBO는 모든 KConfig 항목이 활성화되고 드라이버가 포함 된 전체 커널을 분석했다.
• 한계점
  • KUBO는 현재 하드웨어 입력 소스를 처리하지 않으며 이로 인해 설문조사에서 누락 된 버그 중 5개가 발생했다.
    • 하드웨어 인터페이스는 다양한 하드웨어 사양 (예 : DMA, MMIO)으로 인해, 들어오는 신뢰할 수없는 입력을 식별 할 때 일반적으로 사례별로 분석해야한다.
  • 평가에서 알 수 있듯이 KUBO의 오탐 중 80%가 절차 내 제한으로 인해 불완전한 사후 버그 분석으로 인해 발생한다.

결론

• KMiner - Linux 커널에서 메모리 손상 버그를 감지하기위한 정적 분석 도구로, 가치 흐름 분석을 기반으로하며 메모리에 대한 잠재적 인 잘못된 작업을 추론 할 수 있다. 특정 메모리 개체에서 사용 가능
• PEX - 전체 커널 호출 그래프를 생성하고 정적 호출 체인을 사용한다. 커널에서 권한 검사 오류를 감지하기위한 분석
• Unisan - API 오용을 찾는 것을 목표로 한다. 절차 내 분석은 높은 거짓 감지율, 특히 정수 감지에 사용되는 경우 API 매개 변수가 API로 유입되는 위치와 방식을 추적 할 수 없기 때문에 오버플로가 발생할 수 있다.
• KUBO - 확장 가능하고 효율적인 절차 간 분석을 사용하며 사용자 공간 입력에 의해 트리거 될 수있는 중요한 Undefined Behavior bugs를 감지하는 데 중점을 둔다.