레이블이 deep인 게시물을 표시합니다. 모든 게시물 표시
레이블이 deep인 게시물을 표시합니다. 모든 게시물 표시

[컴][DB] MySQL 에서 transaction 과 isolation level

mysql / mysql race condition / read shadow read /lock

MySQL 에서 transaction 과 isolation level

아래는 정리되지 않은 글이다. 정리는 추후에...

mysql 의 default isolation level

MySql 의 InnoDB 는 Repeatable-read 가 기본 isolation level 이다.

기본 sql standard

sql에서 Repeatable-read 는 아래 3가지를 만족한다.

  • dirty reads (non committed data)
  • non repeatable reads (executing the same query twice should return the same values)
  • allows phantom reads (new rows are visible).

MY SQL 의 default isolation 변경법

실행시에 --transaction-isolation=level option 을 사용하면 된다.(참고)

현재 isolation level 확인방법

-- to check the current isolation level
SHOW variables like 'tx_isolation'

isolation levels

  • SQL Server 트랜잭션 잠금 및 행 버전 관리 지침 | Microsoft Docs
  • SERIALIZABLE : REPEATABLE READ 보다 더 엄격 하다. XA transactions 이나 concurrency 와 deadlocks의 troubleshooting 을 위해서
  • REPEATABLE READ : 가장 높은 수준의 consistency(일관성)
  • READ COMMITTED : locking 에 대한 overhead 가 더 중요해서 precise consistency 와 반복적인 결과들이 덜 중요할때 사용할 수 있다.
  • READ UNCOMMITTED : READ COMMITTED 와 같다. 단 dirty read(select 가 nonlocking 된 상태로 수행된다.) 가 허용된다.(consistency 를 보장하지 않는다.)
격리 수준 커밋되지 않은 읽기 반복되지 않는 읽기 가상
READ UNCOMMITTED
READ COMMITTED 아니요
REPEATABLE READ 아니요 아니요
스냅숏 아니요 아니요 아니요
직렬화 가능 아니요 아니요 아니요

가상읽기(Phantom read)가 가능하기 때문에 만약 아래와 같은 2개의 transaction 이 동시에 실행되는 경우 transaction 1 의 첫 SELECT 와 두번째 SELECT 가 다른 결과를 같게 된다. (두번째 select 의 결과 row 가 더 많을 것이다.)

-- Transaction 1
SELECT * FROM table1
SELECT * FROM table1

-- Transaction 2
INSERT INTO table1 ...

아래와 같은 transaction 이 동시에 일어나는 경우, INSERT 가 2번 된다. 이를 막기 위해 insert 시에 index 를 지정해서 넣어주면, 같은 index 에 insert 를 피할 수 있다. 하지만 문제는 끝부분에서 중복이슈는 없지만, 중복 이슈와 상관없는 경우에도 insert 가 실패하기 때문에 문제가 될 수 있다.

그리고 상품이 2개이상이 동시에 열리는 경우 2개의 상품의 마지막투자가 같은 순간에 이뤄지면, 둘다 같은 index 를 next 로 잡아서 insert 를 할 것이고, 그것이 충돌을 일으킬 수 있다.

해결책

결국 queue 를 두는 방식으로, 즉 worker 로 넘기는 방식을 쓰기로 했다. 아무래도 그래야만 consistency 가 유지될 수 있다고 본다.

-- Transaction 3
SELECT * FROM table1 ...
-- insert depending on the result of the select
INSERT INTO table1 ... 

See Also

  1. 쿠…sal: [컴][db] RDBMS 내부를 설명한 자료

References

  1. Understanding MySQL Isolation Levels: Repeatable-read | Official Pythian® Blog
  2. MySQL :: MySQL 8.0 Reference Manual :: 15.5.2.1 Transaction Isolation Levels

[컴][하드웨어] GPU 의 memory bandwidth 와 VRAM



GPU 의 memory bandwidth 와 VRAM

다음은 ref. 1 의 "Memory Bandwidth, Memory Capacity" 부분을 의역한 내용이다.

----

메모리 대역폭(memory bandwidth) 는 GPU 의 VRAM 에 한번에 얼마나 많은 양을 넣고(copy to), 뺄수(copy from) 있는 지를 알려준다. 당연한 이야기지만, 같은 해상도(resolution)에서 시각효과(visual effects) 가 많을 수록 더 높은 memory bandwidth 가 필요하다.(더 많은 data 를 한 번에 옮겨야 하니.)

VRAM 의 총용량은 GPU 의 다른 중요한 요소다. 필요한 VRAM 의 양이 현재 가능한 리소스를 넘어선다면, 게임은 계속 돌겠지만, 이 부족한 memory 부분만큼 CPU 의 main memory 를 이용하게 된다.

이것은 GPU 가 DRAM 에서 data 를 가져오게 돼서, GPU 의 VRAM 에서 가져오는 시간보다 더 오래 걸리게 된다. 결국 이것이 게임화면의 버벅임을 만들게 된다.

그래서 VRAM 의 양이 중요하긴 하지만, 일부 low-end 그래픽카드는 쓸데없이 VRAM 이 많은 경우가 있다. 즉, VRAM 이 부족해 지기 전에 다른 부분에서 bottleneck 이 걸릴 수가 있다. 그러므로 이런 경우를 방지하기 위해 benchmark 결과등을 잘 살펴서 구매를 할 필요가 있다.

---

Memory Bandwidth Specification


GPU 와 VRAM 간의 memory bandwidth 는 GDDR 의 spec. 을 확인해 보면 된다. GDDR6가 요즘 나오고 있다. 고대역폭을 위해 새롭게 만든 HBM(High bandwidth memory) 이라는 스펙도 있다. 이녀석은 GDDR6가 나오고는 경쟁력이 확실히 많이 떨어졌다.

GDDR6의 데이터 전송 속도는 최대 18Gbps로 고성능 GPU의 384비트 메모리 버스에선 864GB/s의 대역폭((18Gbps * 384bit )/ 8bit = 864GB/s)이 나온다.



References

[컴][HDD] Degaussing (디가우징) 이후에 HDD 를 재사용할 수 있나?

하드디스크 디가우징후 다시 하드를 사용할 수 있나? / 하드 재사용 / 디가우징 하드 재사용


Degaussing 이후에 HDD 를 재사용할 수 있나?


요즘 디가우징(degaussing) 이 이슈이다. 그래서 관련해서 HDD 드라이브에 대해 좀 더 알아보기로 했다.

디가우징을 하면 데이터가 사라진다는 것은 알고 있다. 그럼 이 degaussing 을 한 HDD 를 다시 사용할 수 있을까??

degaussing tool 에 따라 다르다

결론은 degaussing tool 에 달려있다. degaussing 을 할 때 servo mark (또는 servo sector 라고 함) 를 지우느냐 그렇지 않느냐에 달려있다. ref. 3을 보면 servo mark 를 살리는 degaussing tool 도 존재하는 듯 하다.


servo mark, servo sector


그럼 이 servo sector 가 무엇이길래 이것에 따라 HDD 를 다시 사용할 수 있기도 하고 없기도 할까?

HDD 는 아래와 같이 만들어져 있다. 여기서 HDD 의 head arm 이 disk platter 위를 움직이면서 read/write 를 하게 된다. 이때 이 head arm 이 움직이는 길을 만들어주는 것이 servo sector 이다.
출처 : https://ayende.com/blog/174561/the-guts-n-glory-of-database-internals-managing-records

일단 HDD 를 구성하는 flatter 내부를 보자. 보다시피 servo mark 가 존재하고, servo mark 사이에 data 를 write 하게 된다.(좀 더 자세한 내용은 ref. 4를 참고하자)

ser




servowriter

servowriter 는 HDD 를 만드는 공장에서 platter 를 묶어서 HDD 로 만들기 전에 platter(raw media)위에 servo track 들을 그려준다.

그러니 만약 degaussing 으로 servo sector 가 사라졌다면, platter 를 빼서, servowriter 로 다시 servo sector 를 그려줘야 한다.


Servo(Servomechanism)

서보메카니즘은 "피드백 제어 시스템" 이다. ref. 1 의 설명에 나와 있지만, 자전거타기를 생각하면 이해하기 쉽다.

우리는 자전거를 타면서 넘어지지 않기 위해서 페달을 돌리고, 핸들을 좌우로 꺾는다. 그리고 돌부리가 보이면 핸들을 꺾어서 피하고, 다시 원위치로 돌아오는 등 상황에 따라서 자전거를 제어한다.

이렇게 상황(output) 에서 오는 결과(feedback) 을 보고, 다음 동작(input) 을 하는 것을 이야기한다.




References


  1. 서보 메커니즘 : 김상진
  2. Servowriter - Wikipedia
  3. Secure erase 9840 and 9940 data cartridges
  4. HDD from inside: Tracks and Zones. How hard it can be?
  5. 대통령 하드디스크도 통째 보관…근거없는 양승태 컴퓨터 '디가우징' - 노컷뉴스, 2018-06-28

[컴][스크랩] 그래픽 관련 이야기

graphics /  그래픽 이론 / GTA 관련 그래픽


그래픽 관련 이야기



[컴] EV, OV, DV 인증서의 차이

인증서 종류 , ssl certificate 종류


EV, OV, DV 인증서

EV, OV, DV 인증서의 차이

간단하게 이야기 하면, 인증서의 동작에 차이는 없다. 다만 인증서를 발급해 주는 기관(흔히 CA라고 한다.) 에서 얼마나 인증서를 발행 해 주기전에 check 를 하느냐의 차이다.

그래서 EV, OV 에는 인증서(certificate)의 Subject field 에 'O'(organization) 가 추가된다. 그리고 Certificate policy 의 값도 다르다.



EV, OV, DV 확인법[ref. 3]

2012년의 ref. 3 에서는 현재로서는 DV(Domain validated)와 OV(Organization Validated) 를 구분할 수 없다.고 했다. 이때는 CA/Browser Forum 에서 제시한 Baseline Requirements 가 막 나왔을 때였어서, 각 CA(Certificate Authority)마다 어떤 식으로 OV인지, DV인지 표시하는 방법이 달랐다고 한다.

하지만 현재는 2018년이니 훨씬 더 많은 CA가 Baseline Requirements 를 따르고 있을 것이라 생각한다.

Certificate policy 에 기록

RFC 5280

X.509 에서는 RFC 5280 에 정의된 것처럼 Certificate policy 에 어떤 종류의 certificate 인지 적는다.

CA가 자신의 OID(object identifier) 를 적는다. 이 OID 는 발급한 certificate과 관련된 practices 를 적어놓은 문서를 가리킨다.
  • http://oidref.com : 여기서 oid 번호가 어떤 의미인지 파악할 수 있다.

CA/Browser Forum

Baseline Requirements 에서도 같은 방법을 사용한다.

google 의 인증서, OV
GlobalSign 의 EV 인증서
DV 인증서 예제


DV, OV, EV 발급방법의 차이

DV(Domain Validated)

  • 회사정보를 확인하지 않고, 인증서에 보이지도 않는다.[ref. 4]

OV(Organization Validated)

An Organization Validation (OV) SSL certificate is considered to be suitable SSL certificate for medium to large size business. This is because it offers higher validation as compared with DV certificate and displays domain name, organization name on the certificate. The encryption offered is up to 256-bit that enhances user’s confidence in the website they are transacting on.
On the other hand, for the issuance of EV SSL certificate, you need to submit quite a lot of documents to the certificate authority as per their need and requirement. This stringent verification process ensures strong encryption with a green padlock sign in the address bar ensuring protection against hackers.


Read more https://thebroodle.com/web/ssl/how-ev-ssl-certficate-works/
  • An Organization Validation (OV) SSL certificate
  • OV 를 발급받을 때는
    • 도메인 소유권을 확인하고,
    • "기관(organization)과 "인증서를 신청한 개인"에 대한 조사

EV(Extended Validation)

  • CA/B forum 에서 제안했다.
  • CA가 "기관(organization)" 과 "인증서를 신청한 개인"에 대해 훨씬 엄격한 검사
  • ref. 5를 보면 EV 인증서는 발급에 대략 1개월 정도 소요되는 듯 하다. 참고로 ref. 5 에서 이야기한 저렴한 곳은 여기 같다.

See Also

References

  1. What is an EV (Extended Validation) SSL Certificate and How it Works?
  2. What Are the Types of SSL?
  3. How to tell DV and OV certificates apart | UNMITIGATED RISK, 2012년 9월
  4. DV, OV or EV? How to offer the right SSL Certificate - OpenSRS, 2015. 5. 22
  5. EV SSL 인증서 발급 과정에서 알게된 것들 - 리디주식회사 RIDI Corporation, 2017년 3월 5일

[컴][보안] 로그인 관련 보안 2

로그인과 보안 / secure login / 로그인 고민




목차
  1. 로그인 관련 보안 - 1
  2. 로그인 관련 보안 - 2










handshake - exchange the symmetric key

여기서 관건은 MitM 공격이 ssl 을 해놨을 때 틀린 CA 에 대해서 volley (정확히는 HttpsConnection) 가 verification 을 해서 error 을 내뿜으면, 굳이 이 작업을 하지 않아도 될 듯 하다. 그러나 이것은 실제 test 를 해보기 전에 아직 확신할 수 없다.


client <-------------> server
request key   ---->
              <---- public key
symmetric key ----> 


public key 를 server 에서 받지 않는다.

ssl/https 에서는 public key 를server 에서 받은 후 그 public key 를 이용해서 symmetric key 를 주고 받게 된다. 이 경우에 인증서를 인증할 수 있기에 이렇게 한다. 하지만 나는 보내주는 public key 가 누가 보냈는지 알 수 가 없다. 중간에서 공격자가 보내도 그냥 맞는 거구나 하고 보내 버릴 것이다.



server 가 client 로 부터 symmetric key 를 받고나서 server 는 해당 key 를 어떤 user 의 key 라고 알고 있어야 한다. 그래야 해당 user 의 request 가 오면 그 key 를 사용해서 복호화(decryption) 을 할 수 있다. 이를 위해서 DB 에 저장이 필요하다.


이 때 token 이 있는 경우라면, token 을 보고 user 를 구분할 수 있다. 하지만, token 이 없는 경우라면, 임시로 저장을 해 놓아야 하는데, 이를 위해서 phone number 를 public key 로 암호화 해서 보낸다.

하지만 여기서 "폰번호" 는 임시 token 으로 사용하는 것이라, 실제 id 와 연관된 db 에 저장하지 말자. 실제 id 로 사용되는 폰번호와 관련해서 사용하면 공격자가 이상한 값이나 존재하는 값과 비슷한 값을 보내는 경우 다른 사람이 사용하는 record 에 저장하는 문제가 생길 수 있다.

  • token 을 가지고 있는 경우 : token 을 보고 판별한다.
  • token 이 없는 경우 : 폰번호를 public key 로 key 를 주고받을 때 같이 보낸다.
    • 가입이 이미 되어 있는 경우
    • 가입이 안된 경우



Hacking

 아래와 같은 공격이 가능하다. 하지만 아래와 같이 할 것이라면, 차라리 가짜 app 을 하나 만들어서 비밀번호를 입력하게 하는 것이 훨씬 간단하다. 그래서 그나마 공격자가 선택하는 방법은 public key 를 바꿔 놓는 수준이 될 듯 하다.

공격자가 자신의 server 로 접속하게 해서 비밀번호를 알아낸다.


이상황에서 고려할 수 있는 hacking 은 누군가(여기서는 A라고 칭하자.) 의 핸드폰을 몰래 가져다가 public key 를 공격자의 public key 로 교체하고 A 에게 다시 돌려주는 것이다.

이 상황은 ssl 인증서로 무력화 될 수 있지만, 폰을 훔쳤을 때 인증서도 조작할 수 있다.

그러면 A 는 이 public key 를 가지고 통신을 하겠지만, 직접 server 와 통신할 수 없다. key 가 틀려서. 그래서 domain 을 공격자의 server 로 변경해 놓는다.
  1. public key 변경
  2. domain 변경(or DNS 조작)
 이 상황에서 공격자의 server 와 통신을 하면서 A 가 실제로 송금을 한다면, 송금은 안되지만, 공격자는 A 의 auth token 과 비밀번호를 알 수 있다.
  1. auth-token
  2. 비밀번호
이러면 공격자는 A 의 폰을 훔치고, 이 auth-token 과 비밀번호를 가지고 자신의 계좌로 송금할 수 있다.

대처

이 상황을 막고자, public key 를 쉽게 바꿀 수 없도록 한다. 그 방법으로 public key 를 file 자체로 놔두지 않고, xor 등의 연산을 통해 만들어 사용한다. 그리고, crc 등의 방법을 사용해서 변경되지 않음을 확인한다?

이글  이 도움을 준다.
  1. public key 를 xor 등의 연산을 통해 획득
  2. CRC 등의 방법을 이용해서 public key 내용이 변하지 않음을 확인.(이부분도 공격자가 변경 해 놓을 수 있다. 하지만 이런 식으로 힘을 드리는 것보단 차라리 app 을 교체해 놓는 것이 낫다.)
  3. 이체 후 서버에서 고객의 email 등(또는 GMS 등, 실제 서버만이 가능한 것)으로 알림을 준다. (폰으로 주는 것은 안된다. 공격자가 이미 전화번호를 알고 있어서 sms 를 흉내내서 보낼 수 있다.)
    이것은 고객이 자신의 송금 명령이 제대로 된 서버에게 보내졌는지를 확인하는데에 도움을 준다.












[컴][보안] 로그인 관련 보안 1



2015년10월에 정리한 글을 다시 옮겨왔다.




Toss 의 로그인

Toss 가 본인 명의의 휴대폰 1대에서만 사용가능하다고 한다.
송금이 사용자의 휴대폰에서만 가능하다.

그래서 자신이 직접 전화번호(phone number) 를 입력할 수 없다.

폰번호, 기기 ID 확인은 어디서?

폰번호 + 기기 ID (IMEI) 가 일치해야 할 듯 하다. 이것을 통신사에서 확인할 수 있나? 아니면 server 에 가지고 있어야 하는가?


  1. 사용자의 비밀번호를 아는 경우 : 사용자의 폰이 아니라서 불가능
  2. 사용자의 폰에서 시도하는 경우 (훔친 경우) : 사용자의 비밀번호를 몰라서 불가능
  3. 사용자의 폰을 복제하는 경우 : 새롭게 login 을 하면 문자가 날라온다. 그러므로 걸릴 듯 하다.
  4. 사용자의 폰을 훔친경우 + 비밀번호를 아는 경우 : 어쩔 수 없다?

처음에 등록하는 암호가 이들이 사용하는 Login password 인 듯 하다.
이 값을 받아서 hash 해서 저장하고, local 에도 hash value 로 저장 해 놓는다.
그리고, 전화번호와 pw 를 보내서 인증을 받는다?

toss 가 local 에 가지고 있는 값, TOSS.xml

<?xml version='1.0' encoding='utf-8' standalone='yes' ?>
<map>
    <string name="gaCode">9WOv+FvTQXaaU2+aNj1DTw==
    </string>
    <string name="seqNo">zeYYBd62OnqMld4PxW64h++T+yhxeq3wA+Cb3BTBJWM=
    </string>
    <string name="aesKey">xOolFn/09ZO1boBpzGsMw3sWQ3AnlstqHfqPc9k+PJUhksJN0aRU7J631l2oLcme
    </string>
    <string name="pKey">Dw0tPa4Nm58Dt7UxfEuk7tOs7VSQ9pZPOMQ+VGthUU1HKDwTxcjeULVdwdIzQZkh
    </string>
    <string name="timestamp">RNZp58Zh16VZs4IKulvXtQ==
    </string>
    <string name="promotion"></string>
    <string name="privateKey">...
    </string>
    <string name="initData">...
    </string>
    <string name="pNumber">5bEKGSs6BbE2lE4vAt32lQ==
    </string>
    <string name="hasSetTossAlarm">9zV6TSbGJjPn0EnPdHkCxA==
    </string>
    <string name="birthDate">y/6msagccRolTPjekUgFCg==
    </string>
    <string name="name">4Ta03cJDFgrqcAT0RUgdJA==
    </string>
    <string name="faultCount">xfjOGX+ONgBoI7KVMAD40g==
    </string>
    <string name="INIT">9zV6TSbGJjPn0EnPdHkCxA==
    </string>
</map> 



SSL에서 Main-In-The-Middel Attack 





Login 2


여기 글 처럼 auth token 을 쓰자. 그리고 비밀번호를 수정할 때 마다 auth token 이 다시 만들어지게 된다. 이러면 아래의 고민 중 credential 을 stolen 당할 때 client 에 암호화 과정이 들어가 있어서 hacker 들이 추측할 수 있는 여지가 줄어든다.

조금 다른 점은 새롭게 로그인할 때마다 시간을 기록하고, auth token 을 다시 만든다? time 을 더해서?
그러면 한 앱에서 한개만 가능할 것이다.

이건 처음에 생각한 것과 비슷한데, 처음 생각은 auth token 처럼 고정적인 token 을 만들생각을 안하고, expired token 만 고려했는데, 이번엔 2개의 token 을 사용하자.

이 Auth Token 을 가지고 있고, 이녀석을 가지고 다시 expired 가 있는 token 을 얻어오도록 하자.


https sniff, MITM

MITM 의 공격에서는 보통 인증서가 잘못 되었다고 뜬다. (참고) 이것이 volley 에서 어떻게 동작하는지 확인이 필요하다. 만약 error 가 된다면, 굳이 https 가 공격 당할 걱정을 안해도 될까?? 일단 가능할 듯 하다.

MITM 공격에 대비해서 https 위에 다시 한번 https 를 얹어놓자. 정확히 비슷하지는 않지만, sniffing 을 대비해서 한 번 더 encryption 을 해 놓는다. 이부분은 https 와 비슷하게, asymmetric encryption 으로 symmetric 의 key 를 주고 받고, 이 key 를 이용해서 encrypt 해서 보내면, server 에서 decrypt 를 한다.
symmetric encryption 의 key 는 주기적으로 server 에서 교체하면 된다.
client 의 public key 는 client 에 대한 인증역할도 같이 할 수 있다. 그러기 위해서 각 user 의 private key 를 저장하고 있는다.


auth token, expired token

expired token 이 csrf 공격의 방어 기능을 할 수 있다. 그렇다면 expired token 의 generation 을 절대적으로 핸드폰에서만 가능하도록 해야만 한다. phone number 를 가져와서 expired token 의 hash 를 만들때 사용한다.



auth token , no expired token

auth token 만을 이용하자. 이러면, rooting 된 폰에 의해서 auth token 을 stolen 되고, data/data 내용을 그대로 가져가서 새로운 폰에서 toss 를 시작한다고 하면, 여기서 다 잘 된다고해도, 송금할 때 결국 비밀번호를 다시 입력해야 한다. 그래서 괜찮다.

폰정보를 가지고 있을 필요는 없어 보인다. 이 또한 복제될 수 있어서.

expired token 이 필요치 않은 이유

expired token 은 sniffing 때문에 필요하다고 생각했는데, expired token 대신에 auth token 을 사용하다가 sniffing 을 당한다고 해도, 결국 비밀번호를 다시 입력 하는 부분 때문에 사용할 수 없을 듯 하다.

sniffing 에 대한 대비

위의 <https sniff, MITM> 를 참고하자.
expired token 등 sniffing 될 요소들을 사용할 때 한번 더 암호화 하고, ssl 을 사용한다. 이것은 hacked 된 https line 에서 해킹이 어렵게 해준다.

그러면 비밀번호를 보내는 순간에 sniffing 을 당하지 않아야 하는데.... https 같은 경우 secured line 이 아닌 상황이라면, 비밀번호가 노출되는데, 이때를 위해 public key 로 암호화를 걸어놓자.? 하지만 이경우도 brute force 로 알아낼 것이다. 왜냐하면 toss 의 경우는 "숫자4+문자" 의 형태라, 경우의 수가 작은 편이다. public key 가 노출된 상황이라면, 모든 case 에 대한 table 을 가지고 있게 되고, 이런 상태라면 암호화를 한 비밀번호도 손쉽게 노출된다.

그러면 주기적으로 public key 를 갱신해준다. ? 그러면 public key 를 저장하지 말고, network 로 받는다. 하지만 이 경우에 xor 등으로 난독화 하려는 계획이 어려워 질 수 있다. 물론 2개를 받아서 xor 후에 사용할 수도 있을 듯 하다.

송금 수신자 정보 암호화

만약 phone 을 hacking 하지 않고, sniffing 만 하는 경우에, token 을 알고 있다면, 송금이 가능해 진다. 이때 비밀번호가 같이 가기에 괜찮은데, 이렇게 되기 위해서는
비밀번호와 수신자 정보를 같이 암호화 해야 한다. 따로 암호화 하면, 비밀번호 부분을 가져다 이용할 수 있다.
그래서 encrypt("비밀번호","수신자정보") 형식등으로 암호화를 해서 보내야 한다. 그러면 비밀번호를 모르기에 암호화 키를 알아도 적절한 값을 만들 수 없다.
그런데, 비밀번호가 간단하니, 여기에 "hashed 폰번호" 또는 "hashed timestamp" 를 추가로 이용한다.?



rooting 에 대한 대비

그리고 auth-token 은 rooting 등으로 쉽게 가져갈 수 있다. 이것은 다른 app 들에서 하듯이 rooting 인 phone 에서 실행이 안되도록 하는 방법이 있다. 하지만 이것도 우회하는 법들이 생겨났기에, 임시방편밖에 안된다.
rooting 을 하고, token 을 가져간 공격자는 이것을 가지고, 시도를 할 수 있지만, 다행히 비밀번호를 몰라서 바로 hacking 당하지 않는다. 그러므로 잘못 시도된 비밀번호에 대해 user 에게 알려줄 필요가 있다.



처음 등록시 password 전달

처음에 public/private key pair 를 가지고 있는 상태가 된다. public key 를 client 가 가지고 있는다. 이 key 는 처음 password 를 등록할 때 쓰이게 된다.
client 에서는 public key 로 암호화 한다. 이 때 random 값을 같이 준다.
  • public_key_encrypt(pw, random)
password 와 public key 가 모두 노출되어도 유추할 수 없다. random 값이 없으면 rainbow table attack 이 가능할 수 있다.

key 교체시

key version 관리가 필요하다. 서버에서 key 를 바꾸고 새롭게 key 를 장착할 때 기존의 모든 client 가 새로 등록을 할 수 없게 된다. 이 경우에 새로운 버전을 설치하라고 알려줄 필요도 있을 듯 하다.


default public/private key pair

  1. 처음에 접속하면 받도록 하자. 어차피 공개된 녀석이라 굳이 가지고 있을 필요는 없을 듯 하다.
  2. 이녀석은 client 에서 server 로 보내기만 하는 경우이면서
  3. 크기가 작은 녀석을 암호화 할 때 사용가능 하다.(asym 은 암호화 속도가 느려서 큰 것은 힘들다.) 

symmetric 암호 key

  • public_key_decrypt<유저 입력 password  + 랜덤 값+ 폰 넘버>
client 에서 결정하자. 이 시도가 좋지 않을 수 있다. 대부분 서버에서 결정하고 내려준다.(여기를 확인하면 이것이 일반적인 결정인 것을 알 수 있다.)

 임시 key 등은. 하지만 여기서는 public key 를 가지고 있는 쪽이 client 여서 client 가 결정을 내린다. public key 로 암호화 해서 보내면, private key 를 가진 server 만 알 것이다.


client 에서 보낸 암호를 가지고 symmetric 암호화를 하면 된다. 이 때 symmetric 암호키는 랜덤한 값이며, 항상 password 를 보내는 순간에 password 와 같이 보낸다. 그리고 symmetric key 를 받자마자 서버가 symmetric 암호화로 data 를 보낸다. 이러면, sniffing 을 당해도 rainbow attack 등을 피할 수 있다. 그리고 매번 변경돼서, token 을 가져가도 크게 의미가 없다. 누군가 token 을 가지고 key 를 시도한다해도, 암호를 같이 encrypt 하지 않았다면 인정받지 못하게 된다.

세션이 없기에, db 에 임시 저장이 필요하다? 이렇게 되면, 암호가 invalidate 되는 시점도 정확히 정해져야 한다. random 한 값이 사용되므로, 항상 db 에 저장해야 할 필요가 있다.TokenAuthentication 도 token 을 가지고, 이녀석에 해당하는 user 를 가져오는데, 이것처럼 TokenAuthentication 일 때 symmetric key 도 같이 가져오도록 한다.

이 상황은 하지만,처음 로그인에서는 가능하지만, 이후에 token 으로 login 을 하는 경우에는 적합하지 않다. 송금을 누르고 송금정보가 날라갈 때 암호화할 key 가 이미 있어야 한다. 그렇지 않다면, 2번 왔다갔다 해야 한다.


만약 client 가 random 하게 값을 정해서 server 로 보냈다고 하자. 그렇다면, 누구나 그렇게 random 하게 만들어서 server 로 보낼 수 있다. 공개키는 얻을 수 있으니. 그러면 server 는 아무하고 encrypted 통신을 하게 된다. client 가 공격자인 경우도 생긴다.



Login

  • 전화번호 : 노출
  • public key : 해킹에 의해 노출
  • 비밀번호 : 입력
    • 비밀번호를 key logger 를 사용하지 않는한 안전하다고 가정.

여기서 문제는 rainbow table 로 경우의 수를 만들어서 던져볼 수 있다. 그래서 local 에서 credential 을 만들 때 hashing 을 한 번 하고, 그 값을 가지고 credential 을 만들어야 한다. 그러나 그래도 source 를 decompile 한다면, hashing 횟수나 salt 를 쉽게 파악할 수 있을 듯.

time delta

time delta 를 쓰지 않으면, 결국 client 를 hacking 해서 보안이 문제될 수 있다.
그래서 본인 휴대폰 인증받는 순간(문자, ARS 등)  의 시간을 기준으로 한 time 를 만들어서 보내자.
그러고 인증이 통과되면,(로그인 완료후) 이 시간을 server db 에 저장 해 놓고,
time(sec.) 이 이 시간에서 멀지 않은 시간(약 30분?) 으로 setting 된다면,
ok 로 받아드린다.

  • 공격 유형 : 이것은 해커가 public key, id, pw 를 모두 알고 있는 상태에서 해 볼 가능성이 있는 공격이다. 근데 pw 가 노출될 확률이 낮다.



폰을 도난 당한 경우

누군가 폰을 훔쳐갔을 경우, 도둑이 rooting 을 할 수 있다. 그러면, SharedPreference 등에 접근할 수도 있고, 그대로 app 을 사용할 수 있다.

정지방법
이 경우에 외부에서 정지시킬 수 있어야 한다.
  1. 다른 폰에서 앱을 새롭게 login 을 하거나, : time-delta 로 이전 로그인을 차단한다.  / 비밀번호를 변경한다.?
  2. web 을 통해 정지 명령 : server db 에서 time 을 조작해서 time-delta 를 이용할 수 있다.
이 가능하다.

공격

  • 해킹을 통해, credential 을 얻은 경우 : 이 경우 시도해도, 위의 "정지방법" 에 의해 time-delta 가 맞지 않아서 걸린다. 그래서 setCurTime 을 이용한 time 대한 수정을 하려고 할 것이다.(아래 참고)
  • public key, id, pw, 얻은 경우 : time delta 를 알아내기 위해, 다양한 time 을 넣고, credential 을 만들고 사용하려 할 것이다. 이런 접근이 있는 경우 서버에서 감지해서 처리해야 한다. -> 패스워드 변경유도



setCurTime 에 대한 공격

만약 이 request 를 외부에서 해 온다면? 이걸 어떻게 app 에서만 하도록 할 수 있나?

첫 인증시만 사용가능 하도록 : 이것은 ARS 인증? 등을 할 때, 인증이 성공한 경우에만(로그인을 하듯이) time 을 저장한다. 그 외의 경우에는 setCurTime 을 요청하지 않는다.

본인인증 확인 가운데에 설정을 하는 것이라, 노출되지 않는다?
credential 을 만들 때 전해준다.? : 이건 다른 쪽에서 비슷하게 흉내낼 수 있다. rainbow attack 이 들어올 것이다.

공격 상황

  • 해커가 credential 을 가지고 있다.(public key (비밀번호 + id + timedelta )) 그래서 이 credential 에 time-delta 가 들어가는 것을 알고, 이 time-delta 를 맞추기 위해 setCurTime 을 특정 시간으로 조정하려 할 때(무자비하게 여러번 시도 할 것이다.), 
  • credential 을 새롭게 만드는 것도 시도할 수 있지만, 비밀번호를 모를 확률이 크다.













본인인증

  • 한국 모바일 인증 > 개인정보취급방침 : 여기에 보면, toss 가 처음에 인증을 위해 필요한 항목을 입력하는 것과 일치하는 것을 알 수 있다. 아래 2가지 항목을 확인하자.
    • 본인확인기관(이동통신사, 공인인증기관 등)을 통한 본인확인 정보의 일치여부 확인 : 휴대폰번호, 통신사, 성명, 성별, 생년월일, 내/외국인 구분
    • 휴대폰 사용자 확인을 위한 SMS인증번호 전송

위의 인증을 위해서라도, server 에서는 "전화번호"를 가지고 있어야 한다.


OAuth 등의 로그인을 고려해 보자. facebook 같은 녀석으로 한번 login 을 하고 나면, 그 이후로 access token 으로 이녀석을 접근한다. 이것도 어쩔 수 없이 한번의 노출을 만들지만, 그 이후에 id/pw 는 노출되지 않으므로, 항상 id/pw 가 노출되는 것보다 현저하게 노출위험을 줄일 수 있다.

같은 의미로, app 이 처음 실행할 때만 id/pw 를 입력받도록 한다. 그리고 나서 access token 을 발급하자. 그러면, 이 access token 을 저장하고 있다가, 다시 app 을 실행하게 되면, 이 access token 을 보내고,


JWT vs Django login


Using JSON Web Tokens as API Keys 를 참고해서 login 을 위해 JWT 를 사용하기로 했다.
Redirecting Our Django Website to Our Ember App - Shippo

장점

  • 위의 글을 참고한다면, 다양한 방법으로 token 을 이용할 수 있을 듯 하다.
  • Django Rest Framewrok jwt 를 이용하면, permission_class 등의 방법을 그대로 사용할 수 있다.


Django login 도 같은 기능을 제공하긴 한다. csrftoken 을 이용해서, 그런데 문제는 site 에 접근하지 않고, csrftoken 을 받아오는 방법을 찾기가 시간이 걸린다. 그리고 확장성도 떨어진다. Django 자체의 login 과 연동하긴 좋을 수 있다.




client 가입 알고리즘

서버

  1. IMEI 와 전화번호를 서버에 저장한다.
    처음 인증할 때 "통신업체"를 통해 폰이 본인인 것을 확인한다.(아무래도 handset 자체에 대한 검증은 하지 않는 듯 하다.)
  2. public key 를 client에 넘겨준다.
  3. 이때의 datetime 을 기록한다.

client

  1. public key 를 저장한다. 저장시 여기를 참고 
  2. IMEI 와 timestamp 를 public key 를 이용해서 암호화해서 저장하고, 이것을 사용한다.
    • 이것이 결국 password 역할을 할 것이다.
    • 해커는 이 날짜의 존재를 모르기에 만들기 어려울 것이다.
    • 만약 decompile 로 날짜와 함께 만들어진다는 것을 안다고 해도, 이 날짜가 특정시간에 맞춰야 하기에 그 특정시간을 알 수 없다.
  3. public key 를 가지고 있어도 되고, 버려도 된다.
  4. 이 암호화된 IMEI 와 phone number 를 server 로 날려서 token 을 받는다.

서버

  1. 서버에서는 client 에서 온 암호화된 text 를 private key 로 decrypt 한다.
  2. 그리고 날짜를 public key를 넘겨준 날과 비교한다. 시간상 10분(?) 이내라면 허락한다.
  3. 그 이외의 날짜가 같이 IMEI 와 encrypt 된 경우에는 허락하지 않는다.




asynch algo 를 사용한다. timestamp 를 넣어서 암호화된 text 가 steal 되어도 안전하게 만든다.





client 에서 자동 로그인

  1. phone number SIM 에서 읽기
  2. device id 가져오기
  3. phone_number + device id 를 가지고 encryption or hashing
  4. 이 값을 server 로 전송해서 login

pw 암호화

device id 를 phone number 를 key 로 해서 암호화 한다. 이 때 key 는 phone number 를 4자리 단위로 shift 해서 만든다.
  • 01023026616 --->  66160102302 



JWT

djangorestframework-jwt  사용

  • 접속시에 token 을 만든다. 
  • 이 token 은 expiration time 을 갖는데, 이 expiration time 이 끝나기 전에 refresh 를 하면 계속 유지된다. (JWT_EXPIRATION_DELTA)
  • 하지만 이런식으로 같은 token 이 유지되는 시간도 한계를 정할 수 있다.(JWT_REFRESH_EXPIRATION_DELTA)
  • 어느정도 시간 유지가 적절한가?
  • 계속 화면을 띄워놓고 있는 경우에 계속 refresh 를 하기는 부담스럽다. 차라리 refresh 를 못하게 하고, expiration time 을 1일 정도로 가져가는 것이 나은가?






IMEI 를 확인하지 않는경우

SIM의 MSISDN + IMSI 를 복제된 경우

여기서 toss 처럼 인증을 하면, 문자를 받거나, 전화인증에서 양쪽에 전화가 걸려올 수 있다. 그래서 노출될 수 있다. 하지만 그 순간에 본인이 핸드폰을 못봐서 넘어갔을 확률이 있으므로, 이를 대비해서 로그인 후 "로그인했다" 는 정보를 시간과 함께 sms 로 전달해 준다.

그러므로 굳이 IMEI 정보를 알고 있지 않아도 될 듯 하다.



로그인

1번째 로그인

폰에서 app 을 깔고, 처음 로그인 할 때 (전화번호, 이름, 기기 id ) 를 server에 저장
그리고 계속 이 번호로 로그인한다.
처음에 비밀번호를 등록할 때,


이 때 특정 public key 를 보내준다. ???
그럼 public key 로 특정 값을 암호화 해서 server 로 보내게 되면 server 는 그 값에 해당하는 private key 를 가지고 그녀석이 맞다는 것을 확인한다. 그런데 이것은 결국 https 라서, 전체적으로 이런 일을 중복해서 할 이유는 없다.


2번째 로그인

2번째 부터는 phone number 와 기기의 id 를 가지고 로그인한다?
여기서 jwt 를 얻어온다. 그리고 이 값으로 통신한다.


phone number 의 저장

phone number 는 서버의 db 에 저장된다. 서버에서 직접적으로 sms 를 보내는 등의 일을 해야 하기 때문에 어쩔 수 없이 노출된 값을 가지게 된다.

다만 DB에 암호화된 값으로 저장하고, decode 해서 사용할 수는 있다. 이 경우는 key 를 어떻게 가지고 있어야 할 지 고민해야 한다. 장고의 SECRET_KEY 를 이용할 수도 있다.


패스워드, hash(phone_number + Device ID)

송금할 때 사용하는 패스워드 이외에는 패스워드가 따로 없다. 대신에 기기의 ID(Device ID) 를 이용한다. 이 녀석을 직접적으로 pw 로 사용해서 확인할 필요는 없고, 이 ID 를 seed (또는 salt) 로 이용해서 나온 값(hash 값이면 될 듯 하다.)을 이용한다.

이 값을 server 의 DB 에 저장하고, 매 로그인할 때 client 에서 (phone-number, device id) 로 hash 값(또는 암호화한 값)을 만들어 보낸다.?

client 에 암호화, 해시함수를 두는 경우

이것이 server db 를 해킹한 사람들이 client 의 library 에 대한 decompile 을 시도할 것이다.

그러면 시간이 걸리겠지만 가능해 진다. (사실 암호화나, hash 함수나, 이름만 알면 그냥 사용하면 되고, 단순히 seed 나 salt 값을 어떻게 적용했는지의 문제일 뿐일 수 있다.)  그러면 hacking 해서 번호와 device id 에 대한 해독이 가능할 수 있다.
하지만 이 경우에도 phone number 의 암호화가 되어 있는 경우에는 알아내기 힘들 수 있다.

이 부분이 binary 로 되어 있어 decompile 이 어렵고 시간이 걸려서 포기하는 집단도 있을 것이다.

application server 에 암호화, 해시함수를 두는 경우

기기 id 와 폰 번호를 바로 server 로 넘기고, server 는 이 값을 가지고 hash function 을 이용해서 비밀번호를 만들어 저장해 놓는다.

이 경우 hash function 은 노출되지 않아서 server db 를 해킹한 해커는 application server 에 대한 해킹을 다시 하지 않는 이상 db 에서 의미있는 값을 얻기 어렵다.

하지만 client 쪽에서 format 만 맞춰서 쉽게 request 를 날릴 수 있게 된다. request 날리면 서버에서 알아서 암호화를 하고 비교를 할 테니, 암호화의 의미가 server db 가 해킹당했을 때의 대비만을 위한 것이 된다.



만약 phone-number 가 노출된 경우

phone number 를 phone SIM 에서 바로 가져오기 때문에(SIM 에서 안드로이드 SDK 를 통해) 직접 입력하지 않는다. 그래서 phone 의 SIM 에 새겨진 번호를 조작하지 않았다면 괜찮다.


만약 SIM 을 조작했다면?(복제폰?)

전화번호가 같더라도, device id 가 같지 않다. 그래서 이 경우에는 device id 까지 해커가 훔쳐야 한다.

만약 SIM 을 복제 하고, device id 도 복제했다면

폰으로 시도

비밀번호를 몰라서 막히던지, 비밀번호 재설정을 할 때 막힌다.
비밀번호 확인작업을 하는데, 이때 비밀번호 재설정도 할 수 있다. 그런데 재설정 작업은 이들이 자신만의 방법(계좌에 돈 보내고, 그 날짜로 확인)을 이용한다. 이과정 때문에 어쩔 수 없이 공인인증서 등으로 확인이 된다.
그렇기 때문에 여기서 막힌다.

pc로 시도

여기에 어떻게 해서 이들이 send request format 에 맞춰서 송금 명령을 server 로 보냈다고 하자. 그러면 여기서 jwt token 을 얻고, 이 token 으로 계속 통신을 할 것이다. 하지만 송금할 때에는 다시 비밀번호를 직접 입력해야 한다. 결국 비밀번호를 몰라서 실패한다.



기기 ID 가 노출되어서 알려진 경우

기기id가 노출돼서 그것을 카피한 핸드폰으로 시도 해도 암호방식을 해킹해야 한다.

암호방식 binary

암호방식은 이것이 일단 binary라서 바로 해독은 불가능하지만 해킹이 불가능은 아니다. 그래도 memory 채 가져와서 사용할 수 있을지도.?


그런데 시드 서버가 갖고 있어야 하는가?
암호화한 값을 비교 할 수만 있면 된다.
암호를 해독할 필요가 있나?
서버가 털릴때를 대비해야한다.
암호화도 털려서 온다해도 서버에서 인증이 거부 될만한 요소를 가지고 있는가?


서버가 해킹될 때

서버가 털리면
  • 암호화된 패스워드(기기id, IMEI)
  • 전화번호 : 암호화 하는 것이 나을 듯 하다. 속도의 저하가 있을 수 있지만 보안이 더 중요하다.
  • 실명
  • 암호화된 송금 비밀번호(hashed value)
DB 암호화를 고려해 볼 수도 있다. (:: DBguide.net :: 데이터 전문가 지식포털)
이 부분은 일단 많은 방법들이 나와 있어서 크게 문제되지는 않을 듯 하다.


송금 비밀번호

송금 비밀번호는 계속해서 다른 기기에서도 일치여부를 확인할 수 있어야 한다.
그래서 서버쪽에서만 암호화 또는 hashing을 한다.

hashing 의 salt 를 무엇으로 해야 하나?

기기가 바뀌어도 유지돼야 해서, device id 는 안된다.
폰번호가 바뀐 경우는 모르겠다.
명확한 것은 실명인 듯 하다.


스니핑에 대한 고려로

송금 비밀번호를 서버쪽에 보낼 때 암호화가 필요한가? 필요할 듯 하다. 스니핑을 하지 않더라도, 임의로 값을 만들어서 보내는 경우에 앱을 통해서가 아니라 외부툴일 가능성이 있는데 외부 툴로 가능하게 되면, 쉽게 뚤린다. 토스의 5자리의 경우는 특히.

그러므로 보내기 전에 한번 가공을 하고, 그 값을 서버 DB 에 저장된 값과 비교하는 것이 나을 듯 하다.

이것도 마찬가지로 server db 가 해킹당한 후에 해커가 client 의 decompile 을 노릴 수 있다.



서버쪽에서 해킹 당한 경우

이 경우 hashing 되어 있어서, hashing algorithm 을 적용하고, salt 를 파악하지 못하면 의미가 없다. application server 도 해킹을 같이 당해야 한다.

client 에서 당하는 경우


  • 클라이언트에서 입력한 상황에서 메모리의 값을 steal 할 확률 : 이정도의 해킹이 쉽게 될지 모르겠다. 메모리 주소를 쉽게 알 수 없을테니. 일단 잘모르겠다.
  • 키에 대한 로깅으로 해킹하는 방법이 있을 수 있는데 : 키에 대한 로깅을 방지하려고 난독 키보드를 이용한다.








[컴] 버그와 개발

테스트와 개발 / TDD / 완벽한 개발

버그

몇달전 reddit 에 올라온 링크가 있다. 이글을 통해 소프트웨어 개발과 버그에 대한 고민을 좀 해보자.

이 NASA 의 글에서 Test 는 정말 엄청나다. 새로운 기능을 하나 구현하는데 그들은 2년이 걸렸다. 그들은 수많은 테스트를 시행했지만 결국 그들의 프로그램이 완전무결하다는 것을 보증할 수 없었다고 한다.
  1. Developing software for the space shuttle : programming, 2017년 12월31일
  2. Computers in the Space Shuttle Avionics System, Computers in Spaceflight: The NASA Experience
우리가 계속 사용하는 software들도 계속 버그가 나타난다.
  1. 윈도우10 레드스톤3 벌써부터 버그 발생? | 케이벤치
  2. 인텔 CPU 커널 버그 총정리 : 대규모 보안 결함으로 성능 악영향 가능 - ITWorld Korea
  3. 씨넷코리아 | 맥OS의 어이없는 버그 “루트 권한 프리패스?”



개인적 결론

개발자가 버그를 너무 무시하는 것은 좋지 않다. 그것은 정말 안좋은 프로그램을 만들 수도 있기 때문이다.

하지만 빠른 개발을 위해서라면, 핵심에 집중하는 것이 낫다. 중요한(critical) 버그가 아니라면 그저 넘어가는 것이 낫다.

이것의 핵심은 어떤 기능이 가져다줄 가치가 버그로 인해 잃어버리게 될 가치보다 충분히 크다면 개발에 집중해야 한다고 본다.

그래서 결론은 reddit의 comment 에도 있지만, 우리가 버그를 잡는데에 공을 드리기 보다는 빠르게 prototype 을 만들고, 그것의 실패을 통해 bug를 잡는 방법(예를 들면, open beta test 등)을 확장하는 것이 더 나은 방법이라고 여겨진다.

물론 안타깝게도 개발자는 소프트웨어의 책임자가 아니라서, 매니저가(또는 사장)이 이런 방법에 동의할 수 있어야 할 듯 하다.









[컴] NERF 프로젝트

UEFI 부팅과정


구글 엔지니어 로널드 미니치(Ronald Minnich)의 발표








사용자가 인식하지 못하는 3가지 OS

  1. ME
    1. 사용자는 모르지만 인텔CPU는 그 동작을 인식할 수 있는 CPU 자원 제어(Ring -2)
    2. 시스템을 켜고 끄거나 인텔CPU 모르게 전원이 차단된 컴퓨터의 디스크 이미지를 재구성(Ring -3) 할 수 있다.
    3. 오픈소스 운영체제(OS) 미닉스(MINX) 3 버전의 변종이지만, 그 소스코드는 비공개다.
    4. 인텔 CPU의 액티브매니지먼트테크놀로지(AMT) 기능도 ME를 기반으로 구동된다.
  2. UEFI(통합확장펌웨어인터페이스)
    1. 메인 CPU에서 구동
    2. 복잡한 커널을 지녔으며 수백만줄의 코드로 구성
    3. 부팅이 완료된 뒤 UEFI 애플리케이션이 구동
    4. 보안모델이 불명확
    5. 다양한 시스템 기능에 접근할 수 있는 컴포넌트를 포함
  3. SMM
    1. 바이오스(BIOS) 영역에서 실행되는 시스템관리모드(SMM)
    2. ME 가 Ring -3 이라면 SMM과 UEFI는 Ring -2
    3. 오래된 16비트 마이크로프로세서(인텔 8086)용 코드의 통로
    4. 인텔의 칩셋은 한 번 SMM을 설치하면 이후 동작 단계에서 D램의 상위 8MB 크기 영역을 숨겨버린다. 그래서 사용자나 관리자는 그 코드를 control 할 수 없다.
    5. SMM은 제조사가 사용자 시스템 통제를 지속하는 역할을 한다.

사용자가 볼 수 있는 부분

  1. 일반 애플리케이션(Ring 3)
  2. 사용자 OS(Ring 0)
  3. OS를 가상화하는 SW(Ring -1)

NERF 프로젝트(Non-Extensible Reduce Firmware)

  • UEFI 펌웨어 기능을 "작은 리눅스 커널"과 "초기 램 파일 시스템(initial RAM file system, initramfs)"으로 대체하는 작업, code의 custom portion 들이 GO(언어 고) 로 만들어져있다.
  • 인텔CPU ME 펌웨어의 세부 구성요소를 파헤쳐서 가능한 많은 기능을 분석한 다음 그 전반적인 동작을 리눅스OS의 영역으로 되가져오기로 했다
  • 분석 결과 인텔CPU ME 펌웨어 자체를 전혀 쓰지 않는 것은 불가능
  • ME의 구성요소 대부분은 제거할 수 있는 것으로 파악
  • NERF 의 목표
    1. 해로운 동작을 할 수 있는 능력을 덜어낼 것.
    2. 동작을 더 가시화할 것
    3. 없애기 힘든 ME 펌웨어 자체를 제외한, 웹서버 및 IP스택 등 모든 런타임 구성요소를 제거
    4. UEFI의 IP스택과 다른 드라이버도 제거
    5. ME와 UEFI의 자체 덮어쓰기(self-reflash) 기능을 없앨 것
    6. 펌웨어의 플래시 업데이트를 리눅스에서 관리할 것

 UEFI 구성요소

UEFI boot 과정

References

  1. 인텔CPU 보안구멍, 구글이 메운다 - 지디넷코리아




[컴] Desktop HDD 와 NAS 의 차이

엔터프라이즈 NAS의 장점, NAS 와 일반하드의 차이점 /




이곳의 내용은 ref. 1 의 내용을 번역하고 재 구성한 것에 지나지 않는다. 정확한 내용은 ref. 1을 확인하자.

ref. 1에서 하드 선택시 아래3가지를 중요하게 여겨야 한다고 한다.

  1. RV sensors
  2. disc clamps 
  3. structural rigidity of the base plate



Desktop HDD 와 NAS 의 차이가 있는 부분

ref. 1 의 테이블을 확인하면 3가지 HDD의 차이점을 확인할 수 있다.

  1. Reliability
  2. Work Load Rating*
  3. Usage
  4. Usage By Form Factor
  5. Balance Control
  6. Seagate Acu_trac
  7. Heads
    1. NAS 드라이브와 Enterprise NAS 드라이브 모두 Desktop HDD 에 비해 높은 성능의 head 를 사용한다.
    2. 높은 성능의 head 는 좁은 물리적 크기들과 높은 signal to noise ratio 를 갖는다.
    3. 하드에러의 margin을 높여서 긴작업을 해도 error 가 적게 발생하게 된다.
    4. 이 증가된 margin 은 "높은 작업 온도", "높은 진동 환경"과 "높고 지속적인 부하(work loads)"과 같은 여러 스트레스에 대한 견고함을 향상시키는데 이용된다.
    5. "높은 작업 온도", "높은 진동 환경"과 "높고 지속적인 부하(work loads)", 이 3개의 요소가 NAS 드라이브의 성능에 중요한 영향을 미친다.
    6. head 의 품질이 NAS 드라이브의 신뢰성(reliability) 를 극적으로 증가시킨다.(MTBF, worload rating, usage)
    7. 드라이브가 error recovery 에 좀 덜 의존적이면 "좀 더 긴 사용시간", "더 높은 성능"을 갖게된다.
    8. 드라이브가 트랙사이의 빈 공간을 이용해서 좀 더 효과적으로 외부의 이벤트들을 흡수할 수 있을때 한결같은 data rate 은 더 높은 레벨에서 유지되어 진다.
  8. Disks
  9. Firmware
  10. Enterprise NAS HDD 만 다른 경우
    1. Motor : 
      1. 회전축(spindle) 을 위쪽 커버에 나사를 추가적으로 넣어서 좀 더 고정해 준다.
      2. 모터는 위아래 양쪽에 있다.(기본은 아래에만 있다.) 이로인해 50%정도 radial response 가 50% 정도향상된다. 그리고 상단에 있는 모터를 같이 사용하는 것은 진동이 심한 환경에서 잠재적인 이득이 있다.
      3. 이것은 결국 아래쪽에 한개만 있는 것보다 높은 수준의 구조적견고함(structural rigidity)을 가져다 준다.
      4. 이때문에 최근에 Enterprise NAS HDD는 높은 pack 부하(high pack loads)를 견딜 수 있다.
      5. disk windage plates 도 중요: 플래터 사이의 공기간섭(air disturbance)을 감소시켜준다.
      6. 베어링 구조: bubbles form, they are expelled
        많은 기름을 가지고 있는 centrifugal seals 를 갖고 있어서 높은 온도에서 장점을 갖는다.
    2. Rotational Vibration : 진동이 더 많다.
    3. Vibration Control
      1. RV sensors 는 가속도를 측정하는 센서로, 이것이 가속(acceleration), 진동(vibration) 과 충격(shock) 에 비례하는 결과를 제공한다.
      2. HDD 의 PCBA 에 붙어있다. 드라이브가 놓여있는 공간의 외부 진동을 측정하기 한다. (팬, 소리간섭, 랙(rack)의 진동등) 그래서 이 정보를 드라이브에 제공하고, 드라이브는 이런 환경의 변화에 따라 수정하고 보완한다.
      3. 이 덕에 head 가 좀 더 정확한 지점에 오래 머무를 수 있게 되는데, 이것은 그렇지 않을때 생기는 recovery step 등을 하지 않게 해줘서 처리능력(throughput performance)이 일정하게 유지 될 수 있게 해준다. 
      4. 이건 좀 더 빠른 spindle speed 를 가지는 Enterprise NAS HDD 에서 중요한다.
      5. 이것은 desktop HDD pcb 에는 없다.
    4. Base Plate
    5. Top Cover Attached
    6. Voice Coil Magnets(아래 그림 참조)
      1. 전기-기계 발생기(actuator)는 돌아가는 disc 표면에서 write/read 요소를 움직이는 방법이다. 추가로 writer/reader 가 원하는 위치(data track)로 움직이게 해준다.
      2. coil 감는 것(coil winding) 의 디자인과 자력 강도(magnet strength)가 voice coil motor 의 가속능력을 결정한다.
      3. 즉, 강한 VCM 디자인은 더 높은 가속능력과 더 빠른 움직이는 시간을 갖게 되고 그로인해 성능이 올라간다.
      4. Enterprise NAS HDD 는 좀 더 강한 자력의 VCM 을 사용한다.
    7. Disk Clamps
    8. Humidity Sensors






Desktop HDD 를 NAS 에 사용하기 어려운 이유


  • Desktop HDD 은 끊임없이 사용되는 것(constant use) 을 전제로 만들어지지 않았다. 그래서 NAS 에 사용하면 컴퓨터에서 사용할때보다 더 빠르게 노화되고, 닳게 된다.
  • tolerance: NAS HDD 는 더 높은 tolerance 를 갖는다. 이것은 다른 여러개의 HDD 와 같은 공간에서 돌아가게 되는 NAS HDD 의 필수요소이다.
  • firmware: firmware 도 다르다. Desktop HDD 는 desktop 사용에 최적화 되어 있다. NAS HDD는 끊임없이 사용되는 것에 최적화되어 있다. NAS 드라이브 firmware 는 또한 RAID 와 rebuild 시간에 최적화 되어 있다. 그래서 NAS에서 rebuild 가 훨씬 빠르다.
  • 플래터종류 : 다른 드라이브타입(desktop, NAS, enterprise NAS, ..)에는 다른 등급의 플래터(platter) 들이 있다. NAS 드라이브, 특히 enterprise NAS drive)는 더 높은 부하량(work load rating) 을 갖게 된다. 그래서 완전 다른 타입의 플래터가 필요하다.



References


  1. Pick The Right Drive For The Job — 24/7 NAS HDDs vs. Desktop HDDs | StorageReview.com - Storage Reviews, 2015년 7월

[컴] Spectre



Microarchitectural Side-Channel Attacks

이 구성요소들은 미래의 프로그램의 행동 예측을 통해 프로세서의 성능을 향상시킨다.
행동예측을 위해서 그 구성요소들은 과거 프로그램 동작과 관련된 state 를 유지한다. 그리고 미래 행동이 과거의 행동이랑 연관이 있거나 비슷할 것이라고 가정한다.

여러개의 프로그램들이 같은 하드웨어에서 동작할 때 (동시에 또는 time sharing 을 통해 ) 어느 한 프로그램에 의해 이뤄진 microarchitectural state 의 변화는 다른 프로그램에 영향을 준다. 결과적으로 이것이 한 프로그램에서 다른 프로그램으로의 의도치 않은 정보의 유출을 일으킬 수 있다.

과거의 작업들은 BTB, branch history, caches 을 통한 정보유출을 보여줬다. 여기서 우리는 Flush+Reload 와 그것의 변형인 Evict+Reload 를 사용해서 민감한 정보를 유출할 것이다.

이 기술들을 이용해서 공격자는 cache 에서 희생자(victim)가 공유한 cache line 을 추출할 수 있다.

희생자가 잠시 프로그램을 수행한 후에 공격자는 추출된 cache line(evicted cache line) 에 해당하는 주소에서 메모리를 읽는데 얼마나 시간이 걸리는지 측정하게 된다.

만약 victim 이, 모니터되고 있는 cache line 에 접근하면, 그 데이터는 cache 에 있게 되고, 접근은 빨라진다. 그렇지 않고, 만약 victim 이 그 line 에 접근하지 않았다면, read는 느리게 된다. 그렇기 때문에 access time 을 측정하는 것으로, 공격자는 victim 이 추출(eviction step)과 조사(probing step) 과정사이에서 monitored cache line 에 접근했는지 여부를 알 수 있다.

2개의 기술사이의 중요한 차이점은 cache 에서 monitored cache line 을 추출(evicting ) 할 때 사용되는 방법(mechanism) 이다.

Flush+Reload 기술에서는 공격자는 line 을 추출하기 위해 x86의 clflush 같은 기계어처럼 원래 그런 목적으로 만들어진 instruction을 사용한다.(dedicated machine instruction)

Evict+Reload 에서는 추출(eviction) 이 cache line 을 저장하고 있는 cache set 에서의 경합(contetion)을 만들어서 추출하게 된다. 즉, 다른 memory location 들을 접근해서 이 정보가 cache 로 들어오고 이전에 추출한 line 을 버리도록 만든다.



작성중...


See Also


References

  1. Meltdown and Spectre

[컴] Meltdown







요즘 CPU의 심각한 보안 구멍(security hole) 이 있다고 여기저기서 난리다. 그래서 내용을 좀 파보기로 했다.

일단 이 문제에 대해 자세한 설명을 해주는 page 는 아래와 같다.

크게 2개의 bug 가 보고 되었는데, meltdown 과 spectre 라 불린다.
  1. Meltdown
  2. Spectre
여기서는 Meltdown 리포트에 있는 글 가운데 몇개의 내용을 번역하고, 정리해봤다.


Meltdown

Out-of-order execution

Out-of-order execution 은 최적화 기술의 하나이다. 이 기술은 CPU core 의 모든 실행 단위(execution units) 에 대한 사용을 최대화 하기 위한 기술이다.(즉, execution unit 이 놀지않고 쉬지않고 일하도록 한단 이야기다.)

CPU 가 instruction들을 "순차적인 프로그램 순서(sequential program order)"로만 처리하는 것 대신에, 모든 필요한 resource(자원)가 갖춰지자마자 실행하게 된다. 순서를 벗어나서 실행을 하기 때문에 이름이 out-of-order execution 이다.

이러면 현재 동작에 의해 execution unit이 점유되어 있는 동안에도, 다른 execution unit 들은 다른 것들을 실행할 수 있다. 그래서 instruction들은 그들의 결과가 architectural definition을 따르는 만큼 병렬로 실행될 수 있다.

좀 더 쉽게 이야기하면, 원래 프로그램은 프로그램 내에서도 분리될 수 있는 부분이 있다. 예를 들면, 아래와 같은 코드가 있다면,
(1) c = a+b
(2) f = d+e
(3) h = c+f
(1) 과 (2) 는 아무런 연관성이 없기 때문에 병렬로 진행해도 된다. 만약 이것을 sequential program order 로 수행한다면, (1) 이후에 (2)가 진행되고, 그 후에 (3)이 진행될 것이다.

실제로,  out-of-order  execution을 지원하는 CPU 들은 추측해서 operation 을 수행하는 기능을 제공한다. 이 기능은 CPU가 instruction 이 필요해지고 commit되는 것인지 아닌지 대해 확실해 지기 전(즉, 결과를 확정짓기전에), 프로세서의 out-of-order logic 이 instruction들을 처리할 때까지는 수행된다.
In  practice,  CPUs  supporting  out-of-order  execution support  running  operations
speculatively to  the  extent that the processor’s out-of-order logic processes instruc-
tions before the CPU is certain whether the instruction will be needed and committed.

모든 이전의 instruction 들의 결과를 commit 하기전에 프로세서가 operation 을 수행하는 것을 여기서는 out-of-order execution 이라고 하자.


branch prediction units

branch prediction unit 들은 어떤 instruction 이 다음에 수행될 지에 대한 학습된 추측(educated guess) 을 얻게 된다. Branch predictor 들은 조건이 실제로 정해지기전에 어떤 branch 의 방향으로 갈 것인지를 정하기 위해 노력한다.

그래서 정해진 branch 에 있는 dependency 가 없는 instruction 들은 미리 수행되고, 만약 예측이 맞는다면 그대로 그 결과를 사용하게 된다.
만약 예측이 틀리면, reorder buffer 를 clearing 하고 unified reservation station 을 다시 초기화를 한다.

branch prediction 종류

  • static branch prediction
  • Dynamic branch prediction
  • One-level branch prediction 
  • neural branch prediction


주소 공간 Address Spaces


translation table

각 프로세스들을 독립적으로 하기위해서 CPU들은 가상메모리 공간(virtual address spaces)을 제공한다. virtual address 들은 물리적인 memory 주소로 번역(translate)된다.

virtual address spaces 들은 page 들의 집합(set)들로 나눠진다. "multi-level page translation table"을 통해서 이 page set들은 은 물리적인 메모리에 mapping 된다.

translation table 들은 가상주소에서 물리적주소로의 mapping 을 정의한다. 또한 readable, writeable, executable, user-accessible 같은 권한 체크(privilege check)를 수행할 때 사용되는 protection property 들을 정의한다.
  • virtual address --> physical address
  • protection property
특별한 CPU register 에 최근에 사용된 translation table 이 저장되어 있다. process 마다 virtual address space 를 구현하기 위해서 context switch 마다 OS 는 next process의 translation table address리 이 register 로 가져온다.

이 덕에 각 process는 그들의 virtual address space 에 속해있는 data 에만 접근할 수 있다. 이것은 해당하는 translation table들의 user-accessible property 를 disable 하는 방법을 통해서 OS 에 의해 수행된다.


kernel address space

kernel address space 는 kernel 의 사용만을 위한 memory mapped 만을 가지고 있는 것이 아니라 user page 들에 대한 operation 들을 수행한다. 즉, data 를 그곳에 write 할 수 있다. 결과적으로, 모든 물리적 memory 는 일반적으로 kernel 에 mapped 된다.

리눅스OS X 에서 이것은 direct-physical map을 통해서 이뤄진다. 즉, 모든 물리적인 메모리는 직접적으로 이미 정의된 virtual address 에 mapped 된다.

윈도우에서는 direct-physical map 대신에 paged pools, non-paged pools, system cache 라고 불리는 것들을 이용한다. 이 pool 들은 kernel memory space 에 있는 virtual memory 영역들이다. 이 virtual memory 영역들은 물리적인 페이지들을 virtual address 들에 mapping 해준다. virtual address 들은 memory 에 남거나 (non-paged pool) 또는 copy 가 이미 disk 에 저장됐기 때문에 memory 에서 지워질 수 있다.(paged pool) system cache 는 모든 file-backed page들의 mapping들을 포함한다. 이 memory pool들은 일반적으로 물리적 메모리의 많은 부분(large fraction) 을 모든 process의 kernel address space로 map 한다.


ASLR

memroy corruption 버그들은 종종 특정 data 의 주소들의 지식을 요구한다. memory corruption bug 들을 이용한 공격들을 지연시키기 위해서 non-executable stacks 와 stack canaries 가 와 함께 address space layout randomization(ASLR) 이 소개됐다.

  • non-executable stacks
  • stack canaries
  • address space layout randomization(ASLR)

kernel 을 보호하기 위해 KASLR 은 모든 boot 에서 드라이버가 위치하는 곳에 대한 offset들을 randomize 한다. kernel data 구조의 위치를 추측하게 만들기 때문에 결과적으로 공격을 하기 어렵게 한다.

side-channel attack

그러나 side-channel attack 들은 kernel data 구조들의 특정 위치를 알 수 있게 해주거나 자바스크립트에서 ASLR 을 무력화 시킨다. 소프트웨어의 버그와 이 주소들의 지식은 높은 권한의 코드 수행을 가능하게 해준다.


Cache attack

보통 CPU 들은 cache 를 가지고 있다. 우리가 거의 상식적으로 알고 있듯이 cache 는 자주쓰는 내용을 저장해 놓고, 빠르게 불러오는 용도의 저장소라고 할 수 있다.
Address space translation tables 들도 memory 에 저장되면서 동시에 regular cache 들에 cached 된다.

Cache side-channel attacks 은 cache 들로 인해 생기는 시간차(timing differences)를 이용한다.

예제, toy example

아래의 코드를 보자.
raise_exception();
// the line below is never reached
access(probe_array[data * 4096]);

이 코드에서 access(probe_array[data * 4096]); 부분은 실제로 수행될 수 없다. 일단은 앞에 raise_exception() 에서 프로그램이 종료되기 때문이기도 하고, raise_exception() 이 없다고 해도 이부분은 OS 에서 exception 으로 처리해서 이론적으로는 접근할 수 없다.

그런데, out-of-order exception 때문에 CPU 는 아마 이미 위의 코드에 해당하는 모든 instruction 들을 수행했을 것이다. 왜냐하면, exception 코드와 access(probe_array[data * 4096]); 코드는 dependency 가 없기 때문이다.

이것은 register 나 memory 로 load 되지 않았기 때문에 크게 문제되지 않지만, 미세구조적인 부작용(microarchitectural side effect)이 있다.

out-of-order execution 를 수행하는 동안에 참조되어지는 memoryregister 에 fetch 되고, 또한 cache 에 저장된다. 만약 out-of-order execution 이 버려져야 하면, register 와 memory 에 있는 내용들은 commit 되지 않는다. 그럼에도, cached 된 내용은 cache 에 그냥 남아 있게 된다.

Flush+Reload 로 "특정 memory 위치가 cache 됐는지 여부"를 알아낼 수 있는데, 이 방법을 통해 이 microarchitectural side-channel attack 의 효과를 크게 할 수 있다.

access(probe_array[data * 4096]); 는 probe_array를 data 값에 따라 4096 byte(4kB) 간격으로 접근하게 된다. 그래서 data 의 값으로 부터 memory page 까지의 injective mapping 이 있다. 즉 2개의 값은 같은 page 로 접근이 되지 않는다. 결과적으로 만약 page의 cache line 이 cached 되면 우리는 data 의 값을 알 수 있다.
(역자: 이것에 대한 좀 더 이해하기 쉬운 설명은 ref. 3을 확인하자. ref. 3 의 설명은 data 의 값은 cache된다 하더라도 user 가 접근할 수 없기에, data 을 주소를 가리키는 index 로서 사용해서 data 가 array 의 어떤 부분을 가리키는지를 확인하므로써 data 의 값을 판단한다고 한다.)

prefetcher는 page 범위들을 넘어서 data 를 접근할 수 없기 때문에, 다른 페이지들로 펼치는 것은 prefetcher 에 의한 false positive (틀렸는데 맞다고 하는 경우)들을 없애준다.




Meltdown


Meltdown(멜트다운) 은 2개의 빌딩 블럭들을 합쳐 놓은 것이다.
먼저 공격자는 CPU 가 transient instruction sequence(일시적으로 머무르는 명령어 순서) 를 실행하게 한다. 이 transient instruction sequence는 물리적인 메모리 어딘가에 저장해 놓은 "접근할 수 없는 비밀 값(inaccessible secret value)" 을 사용한다.

transient instruction sequence 은 은신처의 송신기처럼 동작해서 결국에 공격자에게 이 비밀값을 넘겨주게 된다.

Meltdown 은 3가지 단계로 구성된다.

Step 1

공격자가 접근할 수 없는 특정 메모리 위치의 내용이 register 로 load 된다.

원래 user application 의 virtual address 에도 kernel memory 의 내용이 mapping 된다. 그러나 user 의 권한으로 이 부분을 접근하면, OS 는 exception 을 발생시킨다.
여기서 meltdown 은 out-of-order execution 취약점을 이용한다.

Step 2

transient  instruction 은 register 의 비밀내용을 바탕으로 cache line 에 접근한다.

Step 3

공격자는 Flush와 Reload 를 이용해서 자신이 접근할 cache line을 정할 수 있게 된다. 그래서 결국 선택된 메모리 위치에 저장된 비밀을 접근할 수 있게 된다.

여러 메모리 위치(memory location) 에 대해 이 방법을 반복해서 사용하므로써 공격자는 물리적인 메모리 전체와 kernel memory 를 dump 할 수 있다.



See Also

  1. CPU.fail
  2. 멜트다운과 스펙터가 울린 경보음··· 하드웨어 취약점 33가지 살펴보기 - CIO Korea, 2020-01-11 

References

  1. 인텔 CPU 보안 무엇이 문제?...패치하면 성능 저하도, 동아사이언스
  2. Meltdown and Spectre
  3. https://pgr21.com/pb/pb.php?id=freedom&no=75348

[컴] 플래시 메모리 SLC, MLC, TLC

간단한 정리 SLC, MLC, TLC / 플레쉬 / 플래쉬 / nand flash /  메모리 / erase

간단한 flash memory 동작

쓰고, 지우기

셀에 전자를 채워넣고, 채워진 전자를 빼내는 방식을 하는 것이 우리가 흔히 아는 write, erase 가 된다.

읽기

  1. 채워진 전자의 양에 따라 자기장의 크기가 달라지는데, 이것에 의해 그 밑을 지나는 N 채널의 전도폭이 변한다.
  2. 이 N채널의 전도폭의 차이로 인해 전하량에(전류값에) 차이가 발생
  3. 이 전하량을 읽어서 어디부터 어디까지는 0으로, 어느값부터 어느값까지는 1로 구분한다.

SLC, MLC, TLC 의 cell

SLC 는 cell 하나에 2의 state 만 표현하는 것이다. 즉 전자가 채워져 있으면 1로 보고, 비워져 있으면 0으로 보면 된다.
MLC 는 cell 하나에 전자가 채워진 양에 따라 4가자의 state 를 표현하게 된다. 전자가 1/3 정도 채워지면 01, 2/3 정도 채워지면 10, 3/3 채워지면 11, 비워져 있으면 00 으로 보게 된다.
TLC 는 cell 하나에서 8가지 state 를 표현한다. MLC 와 마찬 가지로 1/7 정도 채워져 있으면 001, 2/7 정도 채워져 있으면 010, … 그래서 7/7 차면, 111 이 된다.

ECC 코드

위에서 한 이야기 처럼 SLC 보다 MLC, TLC 는 전자를 세밀하게 조절해야 한다. 그래야 하나의 cell 에서 여러가지를 표현할 수 있다. 그런데 이렇게 세밀하게 조절하면 필연적으로 간섭이 발생한다. 그래서 MLC, TLC 들은 확실히 SLC 보다 error 가 많다. 그래서 이 에러를 줄이기 위해 ECC(Error correcting code) 를 크게 줄 수 밖에 없다. 그래서 MLC, TLC 가 SLC 의 2배 용량이 되지 못하고, 성능도 좋지 못한 이유다.

산화막

cell 에 전자를 가두고, 흘려버리기 위해 산화막을 사용하는데, 이 녀석을 전자가 계속 왔다갔다 하다 보면 전자가 이 산화막에 조금씩 쌓이게 된다. (대충 철에 자력이 걸려서 철이 자석이 되는 것을 상상하면 된다.)

이렇게 되면 이 산화막을 통과하는 양이 줄어들거나 할 텐데, SLC 는 state 간의 전압차가 커서 어느정도 전하량이 줄어들어도 인식하는데 큰 문제가 없지만, MLC 나 TLC 는 state 간의 전압차가 크지 않아서 전압이 미세하게 틀어져도 잘못된 값으로 write / erase 될 수 있다.

그래서 MLC, TLC 의 수명이 SLC 에 비해 떨어진다.그래서 이것을 극복하기 위해 spare 영역, over provisioning 부분을 추가해 놓는다.

from: 전기 On·Off 썸타는 반도체, 스마트폰의 ‘줄기세포’

적층구조

위 그림 설명의 GATE 가 최초에는 ‘floating gate’ 라는 이름으로 ’도체’를 사용했다. 그래서 그 안으로 (-)전자를 끌어드렸다. 이 도체 floating gate의 상태가 변하고 1, 0 을 표시하게 된다. 위 그림의 스위치 on/off 를 보면 될 것 같다. 

SLC 는 이것을 채우고 비우는 것으로 1, 0 을 표시하는 것이고, MLC 는 이 floating gate 가 비어있으면 00, 1/3정도 채운것을 01, 2/3 채우면, 10, 3/3 을 채우면 11 이 된다.

그런데 공정이 미세해지면서 cell 간의 간섭을 줄이기 위해 ’부도체’로 바꿨다. ’부도체’는 말그대로 ’전자’가 흐르지 않는다. 그래서 구멍(trap)이 많은 부도체(실리콘 나이트라이드)를 이용해서 그 구멍에 전하를 저장하게 한다. (치즈를 연상하면 된다.)

from : [플래시메모리, 어디까지 알고 있니] 플래시메모리 No.1 역사의 시작 | 삼성반도체
[그림.2] from: https://www.samsungsemiconstory.com/m/434

이제 이것을 세로로 세운다. 위 그림(그림. 2)과 아래 그림(그림. 3)을 참고하자. 이렇게 세워서 양쪽으로 이 것을 붙이는 구조를 만들었다. 이것이 ‘3D V-NAND’ 이다. 이렇게 양쪽으로 붙이게 되면서 이것을 원형으로 만들어 사용하게 됐다. 그림2 그림을 보면 짐작이 가지만 이것이 요즘 ’구멍’을 얼마나 더 깊게 뚫을 수 있느냐를 이야기하는 것의 핵심일 것이다. 이 구멍을 뚫어야 control gate 안에 반도체Floating Gate 를 집어넣을 수 있을테니 말이다.

[K-반도체, 도전과 응전] ①누가 한국 반도체산업을 위협하나 - 오피니언뉴스 낸드 플래시 기술의 핵심은 저장공간을 높게 쌓은 뒤 전류가 흐르는 구멍(hole)을 한 번에 뚫는 ‘싱글스택(Single stack)’ 기술이다. 삼성전자는 128단 낸드플래시에도 싱글스택을 적용했다. SK하이닉스는 128단 최초 양산시 더블 스택을 적용했다. 100층 빌딩을 지을 때 한 번에 쌓아 올리기 않고 50층씩 두개를 연이어 쌓은 셈이다. 싱글스택은 더블스택보다 회로가 간단해 속도가 빠르다. 생산공정도 간단하다. 성능은 높은데 생산비용은 덜 드는 것이다.

포브스는 마이크론의 176단 낸드 출시를 전하면서 “마이크론 관계자가 176단 낸드가 88단을 두번 쌓은 ’더블스택’이라고 언급했다”고 밝혔다. 영미권 전자 전문지 아난드테크(anandtech), 익스트림 테크(Extreme Tech), 퍼드질라(fudzilla) 등은 모두 마이크론 사의 176단 낸드플래시가 “88단을 두번 쌓은 제품”이라고 분석하며 “새로운 기술이 아니다”고 덧붙였다.

from: https://m.blog.naver.com/shakey7/221416796692

References

[컴] 비트코인의 hash 알고리즘

비트코인 해쉬 알고리즘  / 해시 알고리즘 / bitcoin hash funciton

Bitcoin

비트코인관련 흥미로운 글이 있어서 정리 해 놓는다.

  • Bitcoin 에서 사용하는 hash function 은 SHA-256 이다.
  • Bitcoin 은 security 를 위해 SHA-256 을 두번 사용한다.(double-SHA-256)
  • 어떤 hash 값을 찾느냐 하면, 연속된 0 으로 된 hash 값을 찾아야 한다.
  • hash function 은 원래 예측안되는 random 값을 결과로 주며, 역으로 추측할 수 없는 특성때문에 특정 hash 값을 찾으려면 원하는 hash 값이 나올때까지 input 을 계속 변경하는 수밖에 없다.
  • 현재(2017년 12월)는 연속된 0이 약 17개 정도 있는 hash 값을 발견해야 한다. 이것의 확률은 1/140,000,000,000,000,000,000 정도라고 한다.


  • 비트코인 블럭 샘플
  •  hash function 의 input 으로 주면 연속된 0 을 가진 hash값(block hash) 가 나오게 된다.
  • hash input 은 아래 값들을 모아서 만들어진다.
    • version
    • previous block hash(reversed)
    • Merkle root(reversed)
    • timestamp
    • bits
    • nonce
  • 비트코인 블럭 샘플의 값을 가지고 테스트 해보면 이미 채굴된 값이라서 당연히 연속된 0이 나오지만, 대부분의 경우는 그렇지 않다. 그 경우에는 nonce 나 다른 부분의 값을 변경하면서 연속된 0 이 나오는 input 을 찾아야 한다.


SHA-256 해쉬 알고리즘

  • SHA256 hash algorithm 은 512bits 를 input 으로 받는다.
  • 그래서 결과로 256-bit 을 내어준다.
  • SHA 256 은 간단한 작업을 64번 반복해서 output 을 만든다.
  • 이 간단한 작업을 그림으로 표현하면 아래와 같다.

1 round

잘보면 대충 알 수 있는데, 일단 A,B,C,D,E,F,G,H 는 각 하나당 4byte(32bit) 로서 총 64 byte를 보여준다. 한 round 를 수행하면, ABCDEFG 가 오른쪽으로 움직이고, H 만 여러가지 계산을 거쳐서 A의 자리로 가게 된다. 자세한 설명은 아래 링크들을 참고하자.


scrypt hash algorithm

  • 하드웨어로 구현이 어렵도록 디자인된 hash algorithm
  • Litecoin / Dogecoin 등의 가상화폐가 사용한다.






[컴] 구글 개발자의 보안관련 패치 요청에 대한 리누스 토발즈의 답변



구글 개발자의 보안관련 패치 요청에 대한 리누스 토발즈의 답변


보안이 중요하긴 하지만, 그것이 언제나 우선시 되어야 할 항목은 아니다라는 취지의 글인듯 싶다. 약간 분노를 토하는 느낌이다.

대략의 내용은 보안의 문제가 언제나 버그는 아니이며, 보안의 문제가 process 를 죽이는 것을 합리화할 이유는 아니다라며 비판하고 있다. 오히려 security people 들이 이야기 하는 보안문제라고 부르는 것 자체가 '버그' 다라고 하고 있다.

대체적으로 느낌은 security people 들의 자신들만이 옳다는 시각에 대한 비판을 하는 듯 하다.

ref. 1에서 원본을 확인할 수 있다.


그리고 아래 reddit 의 comment 에서 좀 더 균형잡힌 의견들을 확인할 수 있다.



References

  1. Linux-Kernel Archive: Re: [GIT PULL] usercopy whitelisting for v4.15-rc1
  2. 리눅스 창시자 토발즈 "보안이 프로세스 죽이지 말아야" - 지디넷코리아


[컴] BCDboot 의 동작




BCDboot 의 동작






  1. BCDboot 이 "boot-environment 파일"들을 설치된 Windows 이미지에서 "시스템 파티션"으로 복사한다.
  2. BCDBoot 은 시스템 파티션에 "BCD(Boot Configuration Data) store"를 만드는데, 이 BCD store 는 컴퓨터가 Windows partition 으로 가서 부팅하도록 해준다.
  3. UEFI 기반 컴퓨터에서는 BCDBoot 은 이 boot 파일들을 가리키기 위해 NVRAM 에 firmware entry 를 추가한다.
  4. BCDboot 은 새로운 BCD store 를 만들고, 시스템 파티션에 있는 BCD boot-environment 파일들을 초기화하기 위해서 %WINDIR%\System32\Config\BCD-Template 에 있는 template 파일을 이용한다. 
  5. BCDboot 은 최신버전의 boot-environment files 를 os image 의 %WINDIR%\boot 폴더 에서 시스템 파티션으로 복사해 준다.
  6. 기본적으로 BCDboot 은 현재 Windows partition 에 대한 boot entry 가 있다면 현재 있는 entry 를 지우고 다시 복사한다.





References


  1. BCDboot Command-Line Options

[컴][보안] WPA2 보안 문제 - KRACK



WPA2 공격

KRACK(Key Reinstallation Attacks) 이라는 것으로 WPA2 protocol에서 해킹이 가능하다.

이 공격은 WPA protocol 자체의 취약점을 이용하는 것이다. 그래서 현재 대부분의 기기가 취약점이 노출되어 있다.(linux, openBSD, 맥OS , windows)

현재 windows 나 ios 에서는 4-way handshake 에서의 KRACK 공격은 통하지 않는다. (windows 랑 mac 에서 spec. 을 안따라서 그렇다.[ref. 1]) 그러나 group key refresh handshake 등 다른 handshake 에 대한 공격은 유효하다.

KRACK 은 아래와 같은 handshake 를 공격하는 것이다. 각 공격방법에 대한 이야기는 ref. 1 에 자세히 나와 있다.

  • 4-way handshake
  • PeerKey Handshake
  • ‎group key refresh handshake
  • Fast Basic Service Set (BSS) Transition (FT) handshake


대략적으로 4-way handshake 에 대한 공격 내용을 이야기하면 다음과 같다.
  1. AP 가 4번째 메시지를 받기전에 중간에서 못받게 가로채면
  2. AP 가 client 에게 3번째 메시지를 다시 보낸다.
  3. 그러면 client 가 3번째 메시지를 받고 이미 설정했던 PTK(Pairwise Transient Key) 를 다시 install 한다. 
  4. 그리고 그러면서 nonce 를 초기화 한다. 이 초기화되는 nonce 로 공격자가 replay, decrypt, and/or forge packets 를 할 수 있다고 한다.[ref. 1 6.1 Impact of Nonce Reuse in 802.11]

자세한 내용은 "ref. 1 의 3. ATTACKING THE 4-WAY HANDSHAKE" 를 보자.





Refernces

  1. https://papers.mathyvanhoef.com/ccs2017.pdf
  2. https://arstechnica.com/information-technology/2017/10/severe-flaw-in-wpa2-protocol-leaves-wi-fi-traffic-open-to-eavesdropping/
  3. https://arstechnica.com/information-technology/2017/10/how-the-krack-attack-destroys-nearly-all-wi-fi-security/

[컴] unit test 작성 범위는 ?

유닛테스트 작성방법 / 유닛테스트 작성 범위 / unittest / 유닛 테스트 / 테스트 작성 방법 / how to write unittest / unit test

Unit test 의 작성 범위

reddit 에 재밌는 글이 올라왔다.
대략의 내용은 "굳이 하지 않아도 되는 Unit Test 까지 만드느라고 시간을 낭비하고 있다." 정도일 듯 하다. 


우리가 unit test 를 필요로 하는 이유중 하나는 code가 추가되거나 변경될 때, 기존동작에 영향을 미치지 않는 것에 대한 확신을 가지기 위해서 이다.

개인적으로도 이 관점에서 우리가 만약 계속 확장되고, 다듬어져야 하는 project를 진행한다면 unit test 가 꼭 필요하다고 생각된다.

하지만 그렇다고 해서 모든 code 에 대한 검증을 할 필요는 없다. 그것은 시간이 너무 많이 소요되며, 크게 의미가 있지도 않다.

그럼 어떤 unit test 를 하지말아야 할까?


wrapper function 처럼 명확한 code 는 하지 않아도 된다.

위의 link 글에서도 이야기 하지만, 너무나 명확한 code는 굳이 unit test 를 작성할 필요가 없다.

위의 글에서는 아주 명확한 case 를 보여준다. 아무 일도 하지 않고, wrapper function 의 역할을 하는 method 가 예시로 나온다.


public method 에 대한 unit test 만으로 충분

원래 unit test 가 private method 에 대한 test 를 하지 않도록 되어 있지는 않다. 실제로 구글링을 해봐도 unit test 에서 private method 에 대한 test 방법들이 있다.

그래서 필자도 처음에는 특정 logic 에 대한 검증을 하기 위해 private method 라도 unit test 를 시행했다.

하지만 이런 경우 차라리 새롭게 public method 를 사용하도록 새로운 class 로 refactoring 을 하는 것이 맞는 듯 하다. 그리고 되도록 unit test 는 public method 선에서 처리하는 것이 좋은 듯 하다.

왜냐하면 private method 는 결국 public method 안에서 사용되며, private method 가 제대로 동작하지 않는다면 public method 또한 제대로 동작하지 않기 때문에 굳이 중복해서 test 를 행할 피요가 없기 때문이다.


그리고 우리가 public method 수준의 unit test 를 가지고 있어야, class 내부를 refactoring 하는 경우에 많은 private methods 들이 변경될 때 우리는 그것에 대한 unit test 를 없애고, 또 만들어야 하는 일을 하지 않아도 된다.

그러기에 우리는 public method 수준에서 unit test 를 충실하게 작성하면 충분할 것이라 생각한다.


mock up 이 필요한 경우등은 private method 를 test 해야 하는가?

그런데 간혹 외부 라이브러리 등의 문제등으로 mockup 등을 만들 수 없는 경우가 있을 수 있다. 이 경우 public method 를 검증하지 못할 수 있다. 그래서 private method 를 검증해야 할 것 같다. 하지만 만약 그런 경우의 private method 라면 새로운 class 로 만드는 것을 고려해 봐야 할 것이다. 아래 글들이 도움이 될 듯 하다.


See Also



[컴][네트워크] WannaCrypt ransomware 동작방식

워너크립트 동작방식 / 랜섬웨어 동작방식 / wannacrypt ransomware 동작 방식



WannaCrypt ransomware

요즘 한창 WannaCrypt 라는 ransomware(랜섬웨어) 때문에 뉴스들이 사람들에게 겁주고 있다. 평소에 백업을 잘해놓았다거나, windows update 를 잘해왔다면 겁을 먹을필요까지야 있을까 싶긴한데, 여튼 괜한 공포심을 조장하는 듯 싶어서 일단 이녀석이 어떻게 동작하는지 궁금했다.

그런데 한글 문서로 분석된 녀석이 하나도 없어서, 적어도 백신만드는 회사들에서라도 글을 써줘야 하는 건 아닌가 싶었는데, 안타깝게도 조용하다.

여하튼 일단 MS 에서 분석한 글을 찾았다. ref. 1 으로 가서 확인하면 된다.

여기서 다 번역하기는 귀찮고, 이해를 도울 몇개 글만 가져왔다.


WannaCrypt 동작 방식

아래는 ref. 1 의 내용중 일부를 가져와서 번역했다. 참고하자.

However, in this unique case, the ransomware perpetrators incorporated publicly-available exploit code for the patched SMB EternalBlue vulnerability, CVE-2017-0145, which can be triggered by sending a specially crafted packet to a targeted SMBv1 server, was fixed in security bulletin MS17-010, released on March 14, 2017.
보통은 사용자가 실행을 시켜야 하지만, 이번 케이스는 특별한 packet 을 보내면 SMBv1 server 가 받아서 실행을 시켜주는 케이스이다.
이것에 대한 패치는 2017년 3월 14일에 이루어졌다.

The exploit code used by WannaCrypt was designed to work only against unpatched Windows 7 and Windows Server 2008 (or earlier OS) systems, so Windows 10 PCs are not affected by this attack.
WannaCrypt 의 코드는 패치가 안된 윈도우7과 윈도우서버 2008(또는 이전버전의 os) 시스템에서 동작하게 만들어졌다. 윈도우즈10은 괜찮다.

The dropper tries to connect the following domain using the API InternetOpenUrlA():

hxxp://www[.]iuqerfsodp9ifjaposdfjhgosurijfaewrwergwea[.]com

If connection is successful, the threat does not infect the system further with ransomware or try to exploit other systems to spread; it simply stops execution. However, if the connection fails, the dropper proceeds to drop the ransomware and creates a service on the system.

In other words, blocking the domain with firewall either at ISP or enterprise network level will cause the ransomware to continue spreading and encrypting files.
The threat creates a service named mssecsvc2.0, whose function is to exploit the SMB vulnerability in other computers accessible from the infected system:

dropper 가 특정 url 에 접속을 시도하는데, 이 접속이 성공하면, 동작을 멈춘다. 그런데 이 url 에 대한 접속이 실패하면, dropper 가 ransomware 를 떨구고, 그 컴퓨터에 mssecsvc2.0라는 이름의 service 를 만든다. 이 service 가 다른 컴퓨터(아직 패치되지 않은)들을 감염시키기 시작한다.
그러니까 ISP 나 기업네트워크 단의 firewall 에서 이 도메인에 대한 접속이 막혀있다면, 랜섬웨어가 동작하게 된다.


See Also

  1. [MS-SMB]: Server Message Block (SMB) Protocol
  2. Microsoft SMB Protocol Packet Exchange Scenario (Windows)





References

  1. WannaCrypt ransomware worm targets out-of-date systems – Windows Security, 2017-05-12


[컴][머신러닝] Machine Learning





대략적인 이해를 위해서 여기를 읽어보자.

Machine Learning

machine learning 에서 결론은 어떤 input 들에 대한 model(방정식)을 구하는 것이라고 보면 될 듯 하다. 즉 어떤 input 이 어떤 방정식(모델)을 따른다면, 우리는 새로운 input 이 들어왔을 때 이 input 에 대한 output 이 어떻게 나올지 알 수 있다.

이 어떤 방정식(모델) 이 앞으로 이야기할 hypothesis function 이 된다.

  • Supervised Learning[ref. 1] : data set 이 있고, 이 input 에 대해 어떤 output 이 나오는가 나와야 하는지를 알고 싶을때 사용할 수 있다.
    이 알고리즘은 input 과 output 에 상관관계가 있다고 생각하는 것이다. labeled data 를 가지고 작업한다고 생각하면 된다.
    문제는 다음 2가지로 나눌 수 있다.
    • regression problem : 결과값이 continuous 한 값으로 나오는 문제들, 예를 들어 "집크기와 가격에 대한 data 가 있을 때, 크기가 X 만한 집의 가격은?" 등의 문제가 regression problem 이 될 수 있다.
      결과 값으로 정수처럼 딱 나눠지는(discrete) 한 결과를 찾기보다는 실수 값을 찾는 문제일 가능성이 크다. continuous 값을 찾아야 하니까. 물론 그렇다고 정수를 결과값을 찾는 문제라고 해서 모두다 classification problem 은 아니다.
    • classification problem : 결과값이 discrete 한 값일 때 쓴다. 예를 들어 "집크기가 X 만한 집이 있다면 이 집의 가격은 Y 보다 큰가, 작은가?" 라는 문제는 크다, 작다 의 2가지 결과값중 하나가 output 이 되기 때문에 이녀석은 classification problem 이 된다.
  • Unsupervised Learning[ref. 2]
    • clustering algorithm
      어떤 dataset 에 대해서 grouping 을 알아서 해준다.
    • non-clustering algorithm : cocktail party alogorithm
      여러개가 섞여서 혼란스러운 상황에서 어떤 구조를 찾아준다. 목소리 2개가 섞여 있는 파일에서, 음성을 분리해 내는 등의 일을 한다.
    • octave : machine learning prototype 을 만들기 좋은 tool / Download

Training set
m = training example 의 개수
x = input / feature 라고 부름
y = output / target variable 이라 부름


hypothesis function

우리가 training set 을 통해서 알아낸 "예측 모형(model)" 을 hypothesis function 이라고 부른다.
  • function h : X → Y (h maps from x's` to y's)
이것을 좀 더 직관적으로 생각해보면, 우리는 주어진 어떤 값들(traning set) 을 좌표안에 찍고, 이 점들을 대체로 만족하는 "식"(hypothesis function)을 구하는 것이다.(식은 결국 그 점들을 전부 아우르는 그래프를 그려낼 것이다.)

우리가 이 "식"을 구하면 우리는 training set 이외의 위치의 값도 알 수 있고, 이것으로 예측을 하는 것이다.

그리고 이 hypothesis function 에서 우리가 구해야 하는 것은 θ 이다. 즉 식이 성립하기 위한 '상수' 를 찾아야 한다.(ref. 9 에서 θ 를 '가중치' 라고 이야기한다. ref. 9의 설명이 필자는 이해하기 쉬웠다.)

일단 여기서는 꼭 1차 방정식만을 이야기하는 것이 아니다 x 가 x2 을 뜻할 수도 있다.

예를 들어 아파트값을 구하기 위해 우리가 사용하는 변수가 '평수', "단지크기" 라고 한다면, 과연 "평수"가 아파트값에 미치는 영향이 클지, "단지크기" 가 아파트값에 미치는 영향이 큰지에 따라 가중치를 달리 할 것이다.

  • 아파트 값 = ("평수"x θ1) x ("단지크기" x θ2)



Univariate linear regression

여기서 우리는 이 함수(hypothesis function)가 일차방정식이라고 하자.(즉 어떤 input 과 output 과의 관계가 '일차방정식' 의 모양과 비슷하다고 보면 된다.)

그래서 우리는 y= θ+ θ1x 라는 방정식에서 θ 의 값을 찾아 낼 것이다. 여기서 이 θ 값은 어떤 값이어야 하는가?

당연히 이 θ 값을 넣어서 만든 h(x) 의 y 값이 실제 값과  가장 잘 맞는 θ 값이어야 한다.

from: ref. 2

이렇게 x 가 한개인 hypothesis function 을 단일변량 선형회귀 (Linear regression with one variable / Univariate linear regression) 라고 한다.
  • Linear regression model : hθ(x) = θ0 + θ1x

linear regression 의 목적은 cost function J(θ) 를 최소화 하는 것이다. 즉, 우리가 만든 hypothesis function 과 실제값과의 괴리를 최소화 하는 것이다.





Cost Function

이것을 이용해서 우리가 만든 hypothesis function 이 얼마나 실제값에 잘 맞는지 여부를 알아낼 수 있다.
from: ref. 3
위의 J(theta0, theta1) 이 cost function 이다. 이 함수를 "Squared error function", 또는 "Mean squared error" 라고 부른다.

이 함수를 잘 보면 결국 "예측값 - 실제값" 의 평균을 구하는 것이다. 즉 "우리가 예측한 것이 실제 값들에서 얼마나 멀어져 있는가?" 에 대한 값을 구하는 것이다.

이 cost function 의 최소값이 "괴리"가 가장 적다는 뜻이되고, 결국 predict model 이 정교하다는 것을 이야기 하기에, 우리는 cost function 의 최소값을 찾아야 한다.

hθ(x) 방정식이 y= θ1x 처럼 변수가 1개라면 위의 cost function 은  변수가 2개(θ0, θ1)인 2차방정식(x2)이 된다. 그러면 그래프의 모양은 아래처럼 될 것이다. (J(θ1),  θ1)



그리고 hθ(x) 방정식이 y= θ+ θ1x처럼 변수가 2개(θ0, θ1)라면 위의 cost function 은  변수가 3개인 2차방정식이 된다. 그러면 아래와 같은 모양이 된다.(J(θ1),  θ, θ1)
from: ref. 4

여기서  J(θ0 , θ1) 의 최소값을 선택하면, 우리는 training set 에 가장 가까운 hθ(x) 를 찾게 되는 것이다.


최소값을 찾는데에 도움을 주는 알고리즘


  • Gradient Decent Alogorithm
  • Normal Equation



Gradient Decent Algorithm

그럼 우리는 cost function 의 최소값을 찾아야 하는데, 이걸 찾게 도와주는 알고리즘중 하나가 Gradient Decent Algorithm 이다. 이 Gradient Decent Algorithm 이 Machine learning 알고리즘이다.

Gradient Decent Algorithm 이 있는데, 이녀석의 공식은 아래와 같은 식을 수렴이 될때까지 반복하는 것이다.
위 공식을 수렴(convergence)이 될 때까지 반복
α(alpha): learning rate


이 녀석의 계산은 아래처럼 해야 한다. 즉, θ0 를 계산한 후 그 값을 가지고 θ1 를 계산하는 것이 아니라, θ0 , θ1를 동시에 계산한 후에, 이 값을 update 한다.

이 공식을 풀어서 이야기 해보면, 현재 우리가 가진 hypothesis function, hθ(x) 가 있고, 이 녀석은 θ0 , θ1으로 이뤄져 있는데, 이 θ0 , θ1값을 바꿔가면서 가장 적합한 hθ(x) 를 찾아야 한다.

이 때 가장 적합한 hθ(x)를 찾는 것은 cost function 의 값이 가장 적은 값을 찾는 것이다. 그래서 Gradient Decent 알고리즘의 식은 θ값을 cost function 과 관계있게 만들어 준다.

특정 θ0 , θ1값에서의 cost value 가 있고, 이 cost value 에서의 기울기를 구한다. 이 기울기의 값도 중요하지만, 이 기울기로 방향을 정하게 된다. 이렇게 구한 기울기 방향으로 현재의 θ값을 움직여 나가는 것이다.(그것이 식에서는 현재 θ값에 값을 - 하는 것으로 표현된다.)

그래서 α(alpha) 가 learning rate 라 불린다. α(alpha) 가 크다면 최소값에 빠르게 접근할 수 있고, α(alpha) 가 작다면 느리게 접근하게 된다. 하지만 α(alpha) 가 너무 크면 움직이는 간격이 너무 커서 최소값을 지나쳐 버리고 다시 diverge 될 수 도 있다.


Multivariate Linear Regression

여러개의 변수 Multiple features

2개 이상의 변수가 있는 경우를 보자. 이것도 linear regression 이지만 변수가 여러개인 linear regression 이다. 그래서 multivariate linear regression (다변량 선형회귀)이라 부른다.

이전의 h 함수는 1개의 변수 x 가 있었다.
hθ(x) = θ+ θ1x

이 변수 하나가 대상의 특징(feature) 이라고 보면 된다.
hθ(x) = θ+ θ1x1 + θ2x2 + θ3x3 ... + θnxn

hθ(x) = θ0x0 + θ1x1 + θ2x2 + θ3x3 ... + θnxn


Gradient Descent for multiple variables

아래 모습처럼 feature 수만큼(x1, x2..) 의 식이 있고, 이것이 하나의 iteration 이 된다.




이 feature scaling 은 feature 즉 x0, x1, x2 .. 값들의 범위를(input value의 범위) 조절하는 것이다.(scaling) 이것은

Gradient Descent 를 좀 더 효율적으로 사용하기 위해 필요하다.


Gradient Descent 를 이용해서 우리는 hypothesis function 에 쓸 적절한 θ 값을 얻을 수 있다. 이 때 θ의 범위가 크면 descend 가 천천히 이루어진다. 그리고 x1, x2, ..(input value) 의 범위가 다르면 θ의 진동이 커진다. 그래서 최소값을 구하는데에 오랜 시간이 걸린다.

이때 θ의 범위를 줄이고, x1, x2 의 범위를 비슷하게 맞춰주면 적은 수의 연산으로 빠르게 최소값을 찾을 수 있다.(이부분에 대한 설명은 Gradient Descent in Practice I - Feature Scaling - Coursera 을 참고하자.)

standadization

이 θ의 범위를 줄이고, 변수 x1, x2, ... 의 범위를 비슷하게 하기 위해 x0, x1, x2 의 값들을 표준화, 정상화(normalization) 을 해준다. normalization 에 대한 이야기는 아래 경로를 참고하자.


Learning rate

gradient decent 에서 learning rate 값인 α를 구하는 법을 보자.

위 공식을 수렴(convergence)이 될 때까지 반복
α(alpha): learning rate
위에서 이야기 했지만, α가 너무 크면 수렴이 되지 않고, 너무 작으면 계산이 오래걸린다.
그래서 이 값을 정할 때는 대략적으로 값을 대입해서 아래처럼 그래프를 그려보면서 값이 제대로 수렴하는지를 확인해서 가장 적절한 α값을 선택한다.
from. ref. 6

Polynomial Regression

linear regression 의 그래프는 직선이다. 즉, input data 들이 대략적으로 한줄로 표현될 수 있다는 이야기다. 이때의 식이 다음과 같다.
  • hθ(x) = θ0x0 + θ1x1 + θ2x2 + θ3x3 ... + θnxn

하지만 data 속성이 꼭 linear 하지 않을 수 있다. 이때 polynomial regression 이 가능하다.
  • hθ(x) = θ0 + θ1x1 + θ2x12 ---->  θ0 + θ1x1 + θ2x2 (where x2 = x12 ) 
  • hθ(x) = θ0 + θ1x1 + θ2x12 + θ3x13



Octave 에서 구현한 Gradient Descent





Normal Equation[ref. 7]

Gradient Descent 알고리즘 처럼 J 값(cost function, 우리의 모델이 실제 data 와 얼마나 멀어져있나.) 을 최소화 하는 방법중 하나이다.

우리가 2차방정식에서 최소값 또는 최대값을 구할때 미분을 이용하듯이, vector 에 대해서도 편미분을 통해 구할 수 있다. 그런데 이것을 선형대수를 이용하는 것이다.(?)[ref. 7]
  • θ=(XTX)-1XTy
X, y 에 대해서는 아래 그림을 참고하자.
from : ref. 7


Gradient Descent Normal Equation
Need to choose alpha(learning rate) No need to choose alpha
Needs many iterations No need to iterate
O (kn2) O (n3), need to calculate inverse of XTX
Works well when n is large Slow if n is very large

  • n x n 행렬의 역행렬을 구하는데에는 대체로 O (n3) 이 소요된다.
  • 대체로 feature 의 개수 n 이 10,000 이하라면, 요즘 컴퓨터에서 사용할 만 하다고 한다.

Gradient Descent 알고리즘과 차이점

Gradient Descent 알고리즘은 여러번 수행을 해서 J(θ) 의 최소값을 찾는 방법이라면, Normal Equation 은 계산을 통해 한번에 최소값을 찾는 방법이다.


XTX 의 inverse matrix 가 없다면(not invertable)?

XTX is noninvertible 인 경우는 아래와 같은 이유일 수 있다.
  • 일단 redundant 한 feature 가 없는지 살펴보고, 있다면, 지운다.
    • 만약 집값의 feature 중에, "평수" 가 있고, "m2" 가 같이 있다면, 이것은 지운다.
  • 너무 많은 feature 를 사용하는 경우 라면 (m <= n) (m: the number of example)
  • feature 를 몇개 삭제하던지, regularization 이라는 방법을 이용한다.



References

  1. Supervised Learning | Coursera,
  2. Unsupervised Learning - Stanford University | Coursera
  3. Cost Function - Intuition I | Coursera
  4. Cost Function - Intuition II - Stanford University | Coursera
  5. Gradient Descent For Linear Regression - Stanford University | Coursera
  6. Gradient Descent in Practice I - Feature Scaling - Stanford University | Coursera
  7. Normal Equation | Coursera
  8. Machine Learning
  9. 기계 학습(Machine Learning, 머신 러닝)은 즐겁다! Part 1 – Jongdae Lim – Medium