20160118

1. [ATC’14] Scalable read-mostly synchronization using passive reader-writer locks 읽기
– 현재 진행 중인 연구와 관련해 읽어본 논문. 생각보다 큰 관련은 없었음.
– Reader-writer locks(rwlocks)는 reader 사이에 병렬성을 최대화시키기 위해 사용한다. 현존하는 rwlock들은 reader 사이에 경쟁을 유발하고, writer의 쓰기 시간을 증대시킨다. 선점을 해결하지 못하고, critical section 내에서의 sleep을 허용하지 않는 등의 문제가 있다. 이 논문에서는 scalability를 높이면서도 writer latency를 줄여주는 passive reader-writer lock을 제안한다. prwlock은 bounded staleness를 사용하고, memory barrier와 atomic instruction 사용을 회피한다. 대신에 IPI를 사용한다.
bounded staleness는 memory barrier 없이도 짧은 시간 안에 reader가 writer의 쓰기 정보를 확인할 수 있다는 것이다.
– scalable한 rwlock은 reader 사이에 상태 공유가 없어야 하고, writer가 없을 때에는 memory barrier가 없어야 한다. 하지만 실제로는 불필요한 memory barrier가 발생하고, 이것이 성능 저하를 유발한다. prwlock에서는 이러한 문제들을 해결하고자 한다.
– 기존의 rwlock에서는 writer가 reader의 상태를 확인하기 위해 memory barrier를 사용하는데, 이것은 pessimistic한 선택이다. 실제로 실험해보면 대부분의 reader가 writer와 상태 공유를 빠른 시간 안에 한다 (bounded staleness). 이러한 성질을 사용해 passive reader-writer lock을 구현한다.
– prwlock에서는 version 변수를 사용한다. writer가 version 변수를 사용해 lock 획득을 알리는 것. 시스템은 bounded staleness를 가지므로, memory barrier 없이도 reader가 이러한 정보를 빠른 시간 안에 공유하게 된다. straggling reader에게는 IPI를 사용해 정보를 즉시 공유하도록 한다. 그리고 sleep하는 reader는 passive rwlock이 아닌 기존의 active rwlock을 사용하도록 해 문제를 해결한다.
– 논문을 읽는데 배경 지식이 부족해서 이해에 어려움을 겪음. rwlock의 문제가 무엇인지, memory barrier란 무엇인지, 그것의 문제는 무엇인지, 기존의 locking mechanism에 무엇이 있는지 배경 지식 부족해 이해에 어려움을 겪음.
– 리눅스 커널 락 관련된 이해에 [4]와 [5]가 도움이 되었음.

References:
[1] Ran Liu et al., Scalable read-mostly synchronization using passive reader-writer locks, https://www.usenix.org/system/files/conference/atc14/atc14-paper-liu.pdf
[2] Ran Liu et al., Scalable read-mostly synchronization using passive reader-writer locks, https://www.usenix.org/conference/atc14/technical-sessions/presentation/liu
[3] Paul E. McKenney and Jonathan Walpole, What is RCU, Fundamentally?, https://lwn.net/Articles/262464/
[4] 한동훈, 리눅스 커널 락을 없애려는 시도들, http://www.hanbit.co.kr/network/view.html?bi_id=1442
[5] 동기화 기법: Read-Copy-Update, http://summerlight.tistory.com/entry/%EB%8F%99%EA%B8%B0%ED%99%94-%EA%B8%B0%EB%B2%95-Read-Copy-Update


2. Milos Prvulovic, High Performance Computer Architecture
Udacity에서 Milos Prvulovic의 컴퓨터 구조 강의를 조금 들었음. 핵심 개념을 쉽고 이해하기 쉽게 잘 설명해준다. 기억에 남는 세 가지 영상만 가져옴.
– 컴퓨터 구조란 무엇인가? 목적에 맞는 컴퓨터를 설계하는 것.
what is computer architecture.PNG


– Power에는 static power와 dynamic power가 있음. 수도꼭지를 세게 조절하면 힘은 더 들지만 물이 적게 샐 것. 수도꼭지를 약하게 조절하면 힘은 덜 들지만 물이 많이 샐 것. 수도꼭지 조절을 dynamic power, 새는 물을 static power라고 생각해도 됨. Dynamic power를 높이면 static power는 줄어든다. Dynamic power를 낮추면 static power가 늘어난다. 두 가지 모두를 고려해 최적점을 찾아야 한다.
static dynamic power.PNG

– coherence와 consistency의 차이는 무엇인가? coherence란 같은 주소에 대한 접근 순서를 정의하는 것. consistency란 서로 다른 주소에 대한 접근 순서를 정의하는 것.
coherence and consistency.PNG


3. [ASIACRYPT’11] Oblivious RAM with O((logN)3) Worst-Case Cost 읽기
– 원래는 [CCS’13] Path ORAM an extremely simple oblivious RAM protocol을 읽고 싶었는데, 이해가 잘 되지 않아 더 예전에 나온 이 논문을 읽어봄. Path ORAM은 binary tree에 기반하는 ORAM이기 때문에, 그림이 있는 것이 어느 정도 이해하기 쉬움. 하지만 [CCS’13] Path ORAM an extremely simple oblivious RAM protocold에는 그림이 거의 없음. 아마 ORAM이 암호학 관련 학회에서 주로 연구되는 주제이기 때문인 것 같다. 본인의 경우에는 Martin Maas의 발표 자료를 보는 것이 Path ORAM을 이해하는데 도움이 되었음.
– slides from A High-Performance Oblivious RAM Controller on the Convey HC-2ex Heterogeneous Computing Platform
path ORAM overview.PNG
path ORAM organization.PNGpath ORAM storage overhead.PNG
– ORAM은 사용자가 데이터 접근 패턴을 숨길 수 있는 유용한 기법이다. 현재까지 대부분의 선행 연구들이 ORAM의 amortized cost를 최적화하는 것에 목표를 두었다. amortized cost는 개선되었을지 몰라도, worst case cost는 증가하기도 했다. 이 논문에서는 worst case cost가 poly-logarithmic한 Path ORAM을 제안한다. 이 논문의 contribution은 poly-log worst case cost를 보이며 constant client side storage cost를 보이는 ORAM을 제안했다는 점, binary tree에 기반한 ORAM을 제안했다는 점, 단순한 ORAM을 제안했다는 점이다.
– 현재까지의 ORAM은 Read와 Write를 interface로 가짐. 그리고 obliviousness를 보장하기 위해 연산과 동시에 무의미한 Read와 Write를 생성하곤 했음. 이 논문에서는 ReadAndRemove와 Add를 primitive operation으로 가지며, 이를 사용해 Read와 Write를 구현한다. ReadAndRemove는 해당 주소에서 데이터를 읽고 삭제하는 연산이며, Add는 해당 주소에 값을 쓰는 연산이다. Read, Write, Pop 연산 모두 ReadAndRemove와 Add로 구현할 수 있다.
– Path ORAM에서 data block은 server side의 binary tree의 node에 저장된다. 각 노드는 bucket이며, 여러 개의 data block을 저장할 수 있다. 한 개의 data block u는 leaf node l과 연관되어 있다. Data block u는 반드시 root node r과 leaf node l 사이의 path 위에 존재하지만, 어디에 존재하는지는 모른다. Data block u와 leaf node l 사이의 연관은 client에 의해 유지된다. 읽기 또는 쓰기 연산 시마다 data block u는 다른 leaf node l’과 연관된다. 이 때 연관되는 leaf node l’은 이전의 연관인 l과 무관하다. 이와 같은 방식으로 데이터 접근의 obliviousness를 유지한다.

2016/02/01 내용 추가.
– 2016/02/01에 승흔이가 SIGSAC에서 path ORAM에 대한 내용을 발표함. 2016/01/18에 path ORAM에 대한 내용을 간략히 정리했으므로, 여기에 오늘 들은 내용을 추가로 정리한다.
– ORAM은 원래 memory가 아니라 HDD같은 storage access pattern을 숨기고자 만들어짐.
– 메모리 접근 패턴을 가지고 control flow snooping을 할 수 있음. 명령어의 주소 패턴을 관찰하면 control flow를 재구성할 수 있음. 일반적으로 control flow는 코드의 figerprint와 같이 쓰일 수 있으므로, 명령어들이 암호화되어 있어도 라이브러리처럼 이미 공개된 코드라면 그 내용을 유추해볼 수 있음. 뿐만 아니라, control flow snooping을 통해 RSA의 key도 유추해낼 수 있음 ([ASPLOS’04] HIDE: an infrastructure for efficiently protecting information leakage on the address bus).
– Path ORAM의 동작 과정: 서버 측(메모리)에는 binary tree가 있고, binary tree의 각 노드는 4개의 slot으로 구성됨. 각 slot에 data가 암호화되어 저장되어 있음. 클라이언트(프로세서)에는 데이터 블록과 그것이 들어가 있는 path를 기록한 position map이 있음. 클라이언트가 데이터를 읽고 싶을 때, 해당 data가 들어있는 path의 leaf node를 메모리에 요청. Leaf node가 주어지면 root로부터 leaf까지의 path에 있는 모든 데이터를 읽어서 stash에 가져온다. 가져온 데이터 중에서 필요한 데이터 블록만 사용하고, 이 블록은 다른 leaf node로 매칭함. 가져온 모든 데이터를 다시 해당 path에 넣는다. 한편 사용한 데이터의 경우에는 remap된 leaf node와 교차되는 지점에 삽입한다. 새로운 path와 교차되는 지점에 삽입할 수 없다면 stash에 둔다. 그리고 다음에 삽입할 기회가 생긴다면 삽입한다.

Advertisements
Tagged with: , , , , , , , , , , , , , , , , , , , , , , , , , , , ,
Posted in 1) Memo

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

Recent Posts
누적 방문자 수
  • 142,141 hits
%d bloggers like this: