20160510

동시성 프로그램의 이해
data race free yet race bug.PNG
– Atomicity violation은 한 쓰레드의 atomic operation (p-r) 사이에 다른 쓰레드의 연산(q)이 끼어드는 것. 프로그래머의 의도대로라면 p-r-q 또는 q-p-r이 되어야 하는데, p-q-r이 되는 것.
– 위 코드에는 data race가 없지만, atomicity bug가 있다. Vector의 constructor 초기화 과정에서 elementCount가 증가하면 문제가 됨.

TOCTOU attack.PNG
– 권한 확인과 실제 사용이 atomic하지 않으면 루트 권한으로 임의의 명령을 실행할 수 있다. setuid 비트가 걸린 symlink를 열고 실행하는 사이에, 공격자가 symlink를 바꿔치기 하면 된다.

– A code block is atomic if for every interleaved execution, there is an equivalent execution with the same result where the code block is executed serially (i.e., not interleaved with other threads).

– An atomicity violation (atomicity bug) is a race bug that violates the atomicity of an atomic block defined by programmers (defined by requirement specification).

– Atomicity bug detection에는 세 종류가 있다.
1) Reduction based technique
2) Access pattern based technique
3) Happens-before relation based technique.

1. Lipton’s Reduction
– An interleaved execution σ can be reduced to an equivalent interleaved execution σ’ by swapping commuting operations.
– Two operations a and b in σ are commuting if
1) a and b are executed by different threads, and
2) a is immediately followed by b, and
3) their execution orders do not change the resulting state in an execution.
– An operation p is right-mover if p commutes with the operation that immediately follows p and executed by another thread
– An operation p is left-mover if p is commutes with the operation immediately followed by p , executed by another thread
– An operation p is both-mover if p is right-mover and left-mover at the same time.
non-mover if p is neither right-mover nor left-mover.
– Atomizer checks if an observed execution σ can be reduced to an equivalent serial execution σ’
– Atomizer assumes that every public methods are atomic blocks

Lipton's reduction rule.PNG

– Lipton’s reduction에 의해 reduction해 serialize되는 경우에는 atomicity bug가 없다.

Lipton's reduction serializable.PNG

Lipton's reduction non-serializable.PNG
– [Right-mover]* [Non-mover]?[Left-mover]*의 패턴을 확인해도 된다.
– Lipton’s reduction은 false positive를 일으킬 수 있다.
false positive of analyzer.PNG

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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s

누적 방문자 수
  • 98,779 hits
%d bloggers like this: