2016년 11월 22일 화요일

SQLite의 레코드 구조와 삭제된 데이터 복구 방법


[Tech Report]SQLite의 레코드 구조와 삭제된 데이터 복구 방법



  • AhnLab


  • 2014-05-29

‘삭제된 데이터’가 견고한 포렌식 ‘증거’가 되기까지

 

앞서 2회에 걸쳐 SQLite라는 데이터베이스를 소개하고 디지털 포렌식 조사에서 SQLite의 삭제된 데이터를 복원하는 것이 중요한 이유를 알아보았다. 또한 삭제된 데이터를 복원하는 과정의 일환으로 데이터베이스 파일 내에서 삭제된 영역을 탐색하는 내용을 살펴보았다. 이를 통해 SQLite 데이터베이스 레코드 복원에 관심이 있는 독자들이 데이터베이스의 삭제된 영역을 무리 없이 추출할 수 있었으리라 기대한다. 이번 연재에서는 삭제된 영역을 확보한 이후 실질적인 레코드 내부의 필드 데이터를 획득하기까지의 과정을 알아본다.

 

<연재 목차>

1부_스마트폰 포렌식과 SQLite(2014년 3월 호)

2부_SQLite 데이터베이스의 구조적 특징과 데이터 복구(2014년 4월 호)

3부_SQLite의 레코드 구조와 삭제된 데이터 복구 방법(이번 호)
4부_스마트폰 인스턴트 메신 저 및 문자 메세지 복구하기



SQLite 데이터베이스의 삭제된 영역에 대한 추출만 성공하더라도 해당 영역에 존재하는 일부 문자열에 관한 정보를 얻을 수 있다. SQLite는 현재 문자열을 저장함에 있어 리틀엔디안(Little Endian) UTF-16, Big Endian UTF-16, UTF-8 등 3가지 형태의 유니코드 인코딩만 제공한다. 어떤 인코딩을 사용하였는지에 대한 정보를 헤더에 저장하고 있기 때문에 삭제된 영역 전체를 적절한 인코딩 방식으로 디코딩하면 일부분에서 가독성 있는 문자열 데이터를 확인할 수 있을 것이다.

 

 

삭제된 영역에 포함된 문자열 데이터 내용 확인

 


[그림 1]은 SQLite 데이터베이스 파일의 헤더 구조를 개략적으로 나타낸 것이다. 파일의 최상단으로부터 0x38의 위치를 확인하면 [그림 1]의 표시된 부분과 같이 총 4바이트의 값으로 데이터베이스 파일에서 사용하는 텍스트의 인코딩 방식이 저장되어 있는 것을 확인할 수 있다. 이때 저장되는 값은 숫자 1, 2, 3 중 하나로, 1은 UTF-8, 2는 리틀엔디안 UTF-16, 3은 빅엔디안(Big Endian) UTF-16의 인코딩 방식이 지정되었음을 의미한다.

 



[그림 1] SQLite 헤더의 구조 및 텍스트 인코딩 방식 저장 위치

 

[그림 2]는 실제 SQLite 데이터베이스 파일에 저장된 최상단 헤더의 내용으로, 파란색으로 표시된 부분이 인코딩 방식을 나타내는 데이터 블록의 위치이다. 해당 데이터 블록은 빅엔디안 형태로 값을 저장한다. 왼쪽부터 순차적으로 읽어 들이면 0x01의 값을 갖고 있음을 확인할 수 있다. 따라서 이 데이터베이스는 UTF-8로 텍스트 데이터를 인코딩하여 저장한다는 것을 알 수 있다.

 



[그림 2] 실제 SQLite 데이터베이스 파일 헤더에 저장된 인코딩 방식

 

[그림 3]~[그림 5]는 각각의 인코딩 방식으로 텍스트를 저장하고 있는 데이터베이스의 예시이다.

 

[그림 3] SQLite 데이터베이스에 빅엔디안 UTF-16으로 저장된 문자열

 



[그림 4] SQLite 데이터베이스에 리틀엔디안 UTF-16으로 저장된 문자열

 




[그림 5] SQLite 데이터베이스에 UTF-8으로 저장된 문자열

 

어렵게 추출한 삭제된 영역에서 문자열 데이터만 확보하는 데서 그친다면, 들인 노력에 비해 다소 손해가 아닐 수 없다. 일례로 문자/채팅 애플리케이션이 사용하는 데이터베이스 파일의 경우에는 전화번호, SMS 메시지 등과 같이 사건의 실마리가 되는 중요한 내용이 문자열 데이터로 저장되어 있다. 그러나 해당 메시지가 보낸 메시지인지, 받은 메시지인지의 여부나 문자 메시지의 송/수신 시간 정보 등은 정수 형태로 데이터베이스에 저장된다. 특히 이러한 정보는 어렵게 확보한 문자열 데이터를 더욱 견고한 증거로 만들어 주는 역할을 하기 때문에 반드시 추출할 필요가 있다.



 


SQLite는 ▲정수(整數) ▲실수(實數) ▲바이너리(Binary) 데이터 ▲문자열 데이터 등 총 4가지 형식으로 데이터를 저장한다. 이중 정수형 데이터와 실수형 데이터는 삭제된 영역에서 16진수로 존재하는 주변의 데이터와 구분이 되지 않기 때문에 삭제된 레코드의 구조를 정확하게 분석해야만 저장되었던 값을 확인할 수 있다. 따라서 삭제된 영역을 추출한 후에는 반드시 레코드 구조 분석을 통해 각각의 필드에 저장되었던 정확한 값을 취해야만 한다.



 


[표 1]은 각각의 데이터 타입과 길이에 따른 식별 값(Value)을 나타낸 것이다. 각 항목의 식별 값은 삭제된 레코드의 구조를 분석할 때 매우 유용하게 사용할 수 있으므로 간단히 살펴보도록 하자.

 

[표 1] SQLite에 존재하는 데이터 타입의 식별 값 정보

 

 

SQLite 레코드의 전체 구조

 


SQLite의 레코드 구조는 [그림 6]과 같은 형태를 갖는다. SQLite는 레코드의 위치만 정확하게 찾는다면 앞에서부터 순차적으로 해석하며 각각의 필드에 저장된 정보를 확인할 수 있도록 구성되어 있다.

 




[그림 6] SQLite 레코드 구조

 

레코드 구조의 최상단에는 레코드 전체의 길이를 나타내는 값이 존재하며, 이어서 각 행(Row)의 식별 값인 RowID가 저장되어 있다. RowID 다음에는 ‘데이터 헤더’라고 불리는 영역이 존재한다. 해당 영역의 상위 2바이트는 데이터 헤더의 길이를 나타내며, 나머지 영역은 레코드 내부에 존재하는 필드의 길이와 데이터 타입 정보가 [표 1]과 같은 형태로 존재한다. 바로 이 나머지 영역이 우리가 관심을 가져야 할 부분, 즉 데이터가 저장된 데이터 영역이다. 데이터 영역은 모든 필드가 구분 없이 연달아 존재하므로 데이터 헤더의 정보를 이용해 적절히 구분하여 데이터를 복원해야 한다.

 

가변길이 정수의 구조




SQLite 데이터베이스가 여타의 파일 구조와 구분되는 특징 중 하나는 가변길이 정수의 사용이다. SQLite는 작고 단단한 데이터베이스를 완성하기 위해 레코드 구조 곳곳에 가변길이 정수를 사용한다.




가변길이 정수의 가장 큰 특징은, 정수 값을 표현하는 데이터의 길이를 외부에 저장하지 않더라도 그 길이와 정수 값을 알 수 있는 형태로 되어 있다는 점이다. 이러한 특징을 이용하면 파일 전체의 구조가 조금 더 단순해지며 전체의 파일 포맷을 효율적인 형태로 구성할 수 있다.



이를 위해 SQLite는 [그림 7]과 같이 레코드 헤더의 전체 레코드 길이와 RowID를 가변길이 정수로 저장하고 있다. 가변길이 정수는 최소 1바이트에서 최대 9바이트의 크기를 가지며, 각 바이트의 최상위 비트를 종료 플래그로 사용하고 있다. 따라서 실제 정수 데이터의 저장은 각 바이트의 하위 7비트 조합을 이용한다. 또한 9바이트 길이의 정수는 종료 플래그를 설정할 필요가 없기 때문에 최대 64비트를 사용하여 정수 값을 표현할 수 있다.

 




[그림 7] 가변길이 정수의 구조

 

 

데이터 헤더의 구조




레코드에서 RowID까지 해석했다면, 그 다음 2바이트 데이터 블록에 저장되어 있는 데이터 헤더의 길이를 이용해 데이터 헤더와 데이터 영역을 정확하게 구분할 수 있다.




데이터 헤더는 [그림 8]과 같이 [표 1]의 식별 값을 기반으로 구성되어 있다. 정수와 실수를 표현하는 필드는 데이터 헤더에 데이터 유형과 길이를 1바이트로 표현하고 있으며, BLOB과 TEXT의 경우에는 식별 값을 가변길이 정수로 표현하고 있다. BLOB과 TEXT는 각각 짝수와 홀수로 데이터 헤더에 기록되어 서로를 구분한다.




앞서 [표 1]에서 구분한 데이터 헤더의 유형에 따라 데이터의 길이 정보 역시 획득할 수 있으므로, 데이터 영역에서 각 필드를 구분할 수 있다. 

 




[그림 8] 데이터 헤더의 구조

 

 

레코드 삭제 후의 변화



지금까지 살펴본 내용을 통해 SQLite에서 레코드 내용을 어려움 없이 해석할 수 있을 것이다. 그러나 레코드가 삭제되었을 경우에는 [그림 8]과 같이 레코드 헤더의 상위 4바이트가 덮어 쓰여지기 때문에 데이터 헤더의 위치를 알 수 없게 된다. 따라서 삭제된 레코드 영역을 추출하더라도 각 필드를 구분하기 위해서는 데이터 헤더의 위치를 정확히 찾을 수 있어야만 한다.

 




[그림 9] 레코드 삭제 시 덮어 쓰여지는 영역

 

레코드 삭제 시 데이터를 덮어 쓰는 것은 비할당 블록을 효율적으로 관리하여 추후에 삽입되는 데이터가 효율적으로 공간을 사용할 수 있도록 하기 위한 조치이다. 이는 디지털 포렌식 분석가의 입장에서는 가변길이 정수의 해석을 통해 정확하게 데이터 헤더의 위치를 판단할 수 있는 기반이 사라지게 되는 것이므로 매우 아쉬운 방식이다. 그럼에도 불구하고 대부분의 경우 SQLite가 갖는 데이터 헤더와 그 안의 식별 값들의 특징을 통해 다음과 같이 데이터 헤더의 위치를 정확하게 판단할 수 있다.

 

복원 방법




삭제된 레코드에서 데이터 헤더의 위치를 추측하기 위해서는 레코드 헤더에 존재하는 2가지 가변길이 정수(레코드 길이, RowID)가 삭제되기 전에 차지하고 있던 길이를 구해야 한다. 추측하는 길이는 가변길이 정수 2개의 조합이 나타낼 수 있는 길이이어야 하므로, 최초 2바이트로 시작하여 1바이트씩 차례로 늘려가며 18바이트를 넘지 않도록 해야 한다. 가변길이 정수를 추측한 이후, 추측된 길이에 데이터 헤더의 길이를 나타내는 2바이트를 더한 위치를 추측된 데이터 헤더의 위치로 최종 판단할 수 있다.




추측한 위치가 올바른 데이터 헤더 영역인지 판단하는 과정은 다음과 같다.




우선 스키마 테이블을 통해 레코드 각 필드의 데이터 타입을 얻은 후 해당 데이터 타입이 가질 수 있는 식별 값을 [표 1]에서 찾는다. 이때 데이터 헤더의 모든 내용이 스키마 테이블과 일치하는지 확인한다. 데이터 헤더의 위치가 정확하게 추측되었다면 순차적으로 존재하는 각 필드의 식별 정보가 [표 1]의 내용과 모두 일치할 것이다.




조건 검사를 위해 필요한 각각의 필드 타입은 스키마 테이블 이외에 페이지(Page)내에 존재하는 정상적인 레코드를 통해서도 얻을 수 있다. 검사 과정에서 하나의 필드라도 조건을 만족하지 못한다면 추측 길이를 1바이트만큼 늘려서 이전과 같은 과정을 반복한다. 추측 길이가 2개의 가변길이 정수의 최대 길이인 18바이트를 넘는다면 복원을 시도하는 레코드의 데이터가 이미 덮어 쓰여졌거나 레코드의 시작 지점을 잘못 지정한 것으로 판단할 수 있다. 이 경우 레코드의 시작 지점을 1바이트씩 뒤로 옮겨가며 복원을 시도하여 비할당 영역에 존재하는 레코드를 복원해야 한다. 또한 레코드가 복원되었음에도 비할당 영역에 데이터가 남아 있다면 복원된 레코드의 다음 위치부터 같은 방법을 반복적으로 시도하여 복원 가능한 삭제된 레코드를 모두 추출해야 한다.

 

 

레코드 복원 예제



실제 간단한 데이터베이스의 예를 통해 정보가 삭제되었을 때 삭제된 영역에서 레코드를 복원하는 과정을 살펴보자. [그림 10]과 같은 스키마를 갖는 테이블이 선언된 SQLite 데이터베이스 파일이 있다고 가정하자. VARCHAR(256)이라는 타입은 실제로는 SQLite에서 TEXT 형식으로 처리된다. SQLite에서 다루는 데이터 타입은 표 1에서 규정하는 4가지 항목이 전부이다.

 




[그림 10] SQLtie 데이터베이스 테이블 예시

 

생성된 데이터베이스 파일에 총 4개의 레코드를 삽입한 후, 첫 번째 레코드와 세 번째 레코드를 삭제하였다. [그림 11]은 예시를 위해 삽입된 레코드와 삭제 후에 남아있는 레코드를 나타낸 것이다.

 




[그림 11] 레코드의 삽입과 삭제(1,3번 레코드 삭제) 예시

 

이제 3번 레코드를 기준으로 삽입한 데이터가 파일 내부에서 삭제된 후 어떻게 변화되는지 살펴보자. [그림 12]는 4개의 레코드를 모두 삽입한 후의 파일에서 레코드가 존재하는 모습이다. 레코드의 길이와 RowID가 각각 1바이트의 가변길이 정수로 표현되었음을 알 수 있다.

 




[그림 12] 3번 레코드의 삭제 전(빨간색 표시)

 

[그림 13]은 3번 레코드의 삭제 후 변화를 나타낸다. 4바이트 값이 비할당 블록 관리를 위한 정보로 갱신되면서 레코드 길이, RowID, 데이터 헤더의 길이 값이 소실된 것을 확인할 수 있다.

 




[그림 13] 3번 레코드의 삭제 후의 모습(빨간색 표시 부분)

 

이제 상위 4바이트 값이 소실된 상태로 데이터 헤더를 찾아 각 필드의 데이터를 복원해야 한다. [그림 14]는 삭제된 3번 레코드의 데이터 헤더를 찾아 내용을 복원하는 과정을 도식화한 것이다. [그림 14]와 같이 삭제된 영역으로 판단되는 지점을 시작으로 추측 길이를 늘려나가며 스키마 테이블과 추측 위치의 식별 값 일치 여부를 확인 한다.

 




[그림 14] 삭제된 데이터(3번 레코드)의 복원 과정 예시

 

이때 A 필드는 RowID로 사용되어 덮어 쓰여진 영역에 존재하므로 B, C, D 필드의 식별값 만을 비교해야 한다. 결과적으로 정수 형태의 데이터가 갖는 식별 값 범위인 1 ~ 6 사이의 값이 연달아 존재한다. TEXT 형태의 데이터가 갖는 값은 13 이상의 홀수이므로 나타나는 영역은 [그림 14]에 빨간색 박스가 시작하는 위치의 3바이트 영역(0x04, 0x01, 0x17)임을 알 수 있다. 실제로 각 식별 정보를 통해 확보한 길이 정보로 데이터 영역을 구분한 결과, 데이터베이스에서 삽입했던 값들을 확인할 수 있다.

 

지금까지 SQLite 데이터베이스에서 레코드가 삭제되었을 때 삭제된 영역의 파악부터 삭제된 영역의 레코드를 복원하는 과정을 살펴보았다. 다음 호에서는 SQLite를 활용하고 있는 스마트폰 메신저 애플리케이션에서 삭제한 메시지를 복원하는 내용을 살펴볼 예정이다. 스마트폰 포렌식에서 실제 사용되는 기술을 살펴봄으로써, 지금까지의 연재를 통해 SQLite 데이터베이스 복원에 대해 알아본 내용을 더욱 실질적으로 이해할 수 있을 것이다.@










  • AhnLab 로고



  • 전상준 클라우드분석팀 연구원




이 정보에 대한 저작권은 AhnLab에 있으며 무단 사용 및 도용을 금합니다.

단, 개인이 비상업적인 목적으로 일부 내용을 사용하는 것은 허용하고 있으나, 이 경우 반드시 출처가 AhnLab임을 밝혀야 합니다.

기업이 이 정보를 사용할 때에는 반드시 AhnLab 의 허가를 받아야 하며, 허가 없이 정보를 이용할 경우 저작권 침해로 간주되어 법적인 제재를 받을 수 있습니다. 자세한 내용은 컨텐츠 이용약관을 참고하시기 바랍니다.

정보 이용 문의 : contents@ahnlab.com


댓글 없음:

댓글 쓰기