[논문]안드로이드 운영체제의 Ext4 파일 시스템에서 삭제 파일 카빙 기법

김도현; 박정흠; 이상진

doi:10.13089/jkiisc.2013.23.3.417

안드로이드 운영체제의 Ext4 파일 시스템에서 삭제 파일 카빙 기법
File Carving for Ext4 File System on Android OS 원문보기

情報保護學會論文誌 = Journal of the Korea Institute of Information Security and Cryptology, v.23 no.3, 2013년, pp.417 - 429

김도현 (고려대학교 정보보호연구원) , 박정흠 (고려대학교 정보보호연구원) , 이상진 (고려대학교 정보보호연구원)

초록
AI-Helper

많은 리눅스 운영체제와 안드로이드 운영체제에서 Ext4 파일 시스템을 사용하고 있어 디지털 포렌식 관점에서 Ext4 파일 시스템 상의 삭제 파일 복구가 현안이 되고 있다. 본 논문은 Ext4 파일 시스템에서 파일의 할당, 삭제 시 특징을 분석함으로써 삭제된 파일에 대한 복구 방법을 제시하였다. 특히 안드로이드 운영체제의 파일 할당 정책을 바탕으로 비 할당 영역에 조각나 있는 삭제된 파일에 대한 복구 방법을 제시한다.

Abstract ▼ AI-Helper

A lot of OS(Operating Systems) such as Linux and Android selected Ext4 as the official file system. Therefore, a recovery of deleted file from Ext4 is becoming a pending issue. In this paper, we suggest how to recover the deleted file by analyzing the entire structure of Ext4 file system, the study of metadata area, the distinct feature when file is assigned and deleted. Particularly, we focus on studying the features of file which is assigned in Ext4 file system in Android OS and also suggest the method to recover the deleted file that is fragmented from the un-allocated area.

주제어

AI 본문요약
AI-Helper

* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.

문제 정의

본 논문은 Ext4 파일 시스템을 분석함으로써 파일 할당 정책과 안드로이드 내부의 사용자 데이터가 존재하는 파티션, 애플리케이션 설치 시 생성되는 파일들의 종류 및 특성 등을 이용하여 애플리케이션 등의 데이터가 삭제된 경우 관련된 파일들을 효과적으로 복구 및 분석할 수 있는 방법을 제안하였다. 특히 제안한 방법을 통해 많은 사용자 데이터가 존재하는 XML파일과 SQLite 데이터베이스 파일을 등을 효과적으로 복구할 수 있도록 하였다.
본 논문은 Ext4 파일 시스템의 전체적인 구조와 파일시스템의 메타데이터에 해당하는 영역에 대한 연구 및 파일의 할당, 삭제 시 특징을 분석하였다. 또한, 추가적으로 안드로이드에서 사용되는 Ext4 파일 시스템에서 파일이 할당되는 특징을 통해 파일의 단편화 특성을 연구함으로써 비 할당 영역으로부터 조각나 있는 삭제된 파일에 대한 카빙 방법을 제시하였다.
본 절에서는 Ext4 파일 시스템의 전체적인 구조와 메타데이터 영역에 대해서 알아본다. Ext4 파일 시스템은 데이터 저장의 최소 단위인 블록들로 이루어져 있으며 블록의 크기는 1KB, 2KB, 4KB 중 하나를 선택하여 사용할 수 있지만 기본적으로는 4KB를 사용한다.
본 절에서는 Ext4 파일 시스템이 파일을 할당하는 방식과 파일의 단편화 현상 등의 특징들을 알아보고 파일을 삭제할 때 파일 시스템의 내부 메타데이터 영역에 나타나는 변화에 대해서 알아본다.
본 절에서는 안드로이드 운영체제의 특징 및 그로 인해 발생되는 안드로이드 운영체제에서 사용된 Ext4 파일 시스템의 내부 데이터의 종류 및 할당 특성에 대해서 알아본다. 특히, 사용자 데이터가 존재하는 XML, SQLite 데이터베이스 파일에 대해 자세히 알아본다.
본 절에서는 안드로이드 운영체제의 특징 및 그로 인해 발생되는 안드로이드 운영체제에서 사용된 Ext4 파일 시스템의 내부 데이터의 종류 및 할당 특성에 대해서 알아본다. 특히, 사용자 데이터가 존재하는 XML, SQLite 데이터베이스 파일에 대해 자세히 알아본다.

가설 설정

Ext4 파일 시스템은 [그림 3]과 같이 데이터의 크기가 블록 크기의 배수가 아닐 경우, 데이터가 저장되는 마지막 블록의 비할당 영역을 ‘0x00’으로 초기화하는데 이러한 영역은 데이터의 마지막을 판단할 수 있는 기준으로 사용될 수 있다. 블록의 크기는 4KB, 데이터의 크기는 13KB로 가정하였다.

제안 방법

각 블록 그룹에 존재하는 block bitmap의 위치로 차례로 이동하여 bitmap을 해석함으로써 비할당 블록을 파악한다. 모든 블록 그룹의 block bitmap을 해석하면 파일 시스템 전체의 비할당 영역을 수집할 수 있다.
본 논문은 Ext4 파일 시스템의 전체적인 구조와 파일시스템의 메타데이터에 해당하는 영역에 대한 연구 및 파일의 할당, 삭제 시 특징을 분석하였다. 또한, 추가적으로 안드로이드에서 사용되는 Ext4 파일 시스템에서 파일이 할당되는 특징을 통해 파일의 단편화 특성을 연구함으로써 비 할당 영역으로부터 조각나 있는 삭제된 파일에 대한 카빙 방법을 제시하였다.
SQLite 데이터베이스 파일의 경우 페이지 크기와 파일 크기, 테이블 스키마 정보를 획득한 후 페이지 단위로 탐색을 진행하며 이때 발견되는 각 페이지들은 해당 파일을 구성하는 페이지로 판단하여 해당 SQLite 데이터베이스 파일에 포함한다. 탐색을 진행하며 발견되는 SQLite 데이터베이스의 저널 파일들은 카빙 대상에서 제외하며, 발견된 Table Leaf 페이지의 레코드의 스키마 정보가 해당 데이터베이스 파일의 스키마 정보와 일치하지 않는 경우와 그 외의 파일의 시그니처가 발견되는 경우는 온전한 카빙이 불가능한 경우이므로 탐색을 중지하고 다시 파일 시스템의 블록 단위 탐색을 수행한다. 카빙이 정상적으로 완료되지 않은 SQLite 데이터베이스 파일은 레코드 재조합을 위해 스키마 정보에 따라 따로 분류한다.

대상 데이터

본 논문에서는 실질적인 테스트를 위해 실제로 약 15개월 정도 사용한 삼성 안드로이드폰인 갤럭시 S2(SHW-M250S)와 약 12개월 정도 사용한 갤럭시 노트(SHV-E160S)의 내부 데이터를 테스트 세트로 사용하였다. 갤럭시 S2에서는 총 6,074개, 갤럭시 노트에서는 총 7,319개 파일이 존재하였다.

성능/효과

첫째, 생성되는 파일의 크기가 127MB 이상이거나 해당 블록그룹에서 관리하는 데이터 블록에 더 이상 저장할 공간이 없는 경우에는 파일이 조각나서 저장되며 이러한 경우 두 개 이상의 extents를 사용하게 된다. 둘째, 이미 존재하는 파일의 내용이 수정되면서 내부 데이터가 증가할 경우 추가된 데이터는 기존 파일의 데이터 블록에 연속적으로 저장되지 못하고 다른 영역으로 조각나서 저장될 수 있다. 첫 번째의 경우는 Ext4 파일 시스템을 사용하는 일반적인 리눅스 시스템과 안드로이드 운영체제에서 비슷하게 발생하지만 두 번째의 경우는 주로 안드로이드 운영체제에서 발생하며 그 빈도가 매우 높다.
‘File Identifier’ 항목이 inode번호이며, ‘Physical Sector’ 항목은 해당 데이터의 물리적 위치다. 디렉터리들은 모두 1번 블록 그룹에 존재한다는 것을 알 수 있고 이를 통해 같은 디렉터리 내의 데이터들은 같은 블록 그룹 안에 할당하는 Ext4 파일 시스템의 데이터 할당 정책을 확인할 수 있다.
db’파일의 단편화 정보를 확인한 것으로 파일의 중간에 존재하는 저널 파일만 파일 복구 대상에서 제외함으로써 SQLite 데이터베이스 파일을 온전히 복구할 수 있다. 이와 같은 프로세스를 통해 3조각 이상으로 조각난 약 27.9%의 파일 중에서 약 35.29%의 파일이 복구 가능하며 전체적으로는 약 81.94%의 SQLite 데이터베이스 파일의 복구가 가능하다.
본 논문은 Ext4 파일 시스템을 분석함으로써 파일 할당 정책과 안드로이드 내부의 사용자 데이터가 존재하는 파티션, 애플리케이션 설치 시 생성되는 파일들의 종류 및 특성 등을 이용하여 애플리케이션 등의 데이터가 삭제된 경우 관련된 파일들을 효과적으로 복구 및 분석할 수 있는 방법을 제안하였다. 특히 제안한 방법을 통해 많은 사용자 데이터가 존재하는 XML파일과 SQLite 데이터베이스 파일을 등을 효과적으로 복구할 수 있도록 하였다. 이러한 연구 결과를 토대로 도구를 개발하고 많은 테스트를 통해 알고리즘을 수정해 나간다면 Ext4 파일 시스템을 사용하는 많은 임베디드 기기에 대한 디지털 포렌식 분석에 많은 도움을 줄 수 있을 것이다.

후속연구

Ext4 파일 시스템에서 삭제된 파일 복구에 대한 연구들이 진행되었지만 extents 구조체로부터 삭제된 파일의 데이터 블록 정보가 초기화되기 때문에 복구가 불가능 하다는 사실을 확인하고[1], journal log 영역에 남아있는 가장 최근의 삭제된 파일만 확인이 가능하다는 등의 많은 한계점이 존재한다[2]. 또한, Ext4 파일 시스템이 안드로이드 운영체제에서 사용될 경우 일반적인 리눅스 시스템과는 사용 방식이 다르고 그에 따라 내부 데이터의 저장 방식 및 종류들도 다르기 때문에 이에 대한 추가적인 연구가 필요하다.
2에서 살펴본 것과 같이 조각난 블록들은 해당 블록 그룹에 존재할 가능성이 높기 때문에 블록 그룹별로 SQLite 데이터베이스의 페이지들을 수집한 뒤, 조각난 Table Leaf 페이지들로부터 추가적인 재조합을 수행한다. 또한, 카빙된 많은 XML, SQLite 데이터베이스 파일들을 효과적으로 분석하기 위해 파일 내부 문자열 추출을 수행하면 디지털 포렌식 분석에 더 많은 도움이 될 것이다[23].
일반적인 리눅스 시스템에서 사용된 Ext4 파일 시스템에 대한 카빙을 수행할 경우는 다양한 포맷들을 고려해야 하지만 안드로이드폰에서 사용된 Ext4 파일 시스템의 경우는 [표 3]에 언급한 것처럼 다소 제한적인 포맷만이 존재한다. 이 파일들 중 디지털 포렌식 관점에서 중점적으로 카빙 대상이 되는 파일은 사용자 데이터가 저장되어 있는 SQLite 데이터베이스 파일과 단편화된 SQLite 데이터베이스의 실제 레코드가 존재하는 Table Leaf 페이지, 사용자가 입력한 계정 및 패스워드 등의 설정 정보들이 저장되어 있는 XML 파일이며 추가적으로 사용자가 애플리케이션을 사용하며 생성된 BMP, GIF, JPG, PNG 등의 그래픽 관련 파일에 대해서도 카빙을 수행할 필요가 있다. SQLite 데이터베이스 파일을 제외한 파일들은 일반적으로 크기가 작고 내용 수정 시 증가되는 데이터의 양도 작기 때문에 대부분 연속적으로 존재한다.
특히 제안한 방법을 통해 많은 사용자 데이터가 존재하는 XML파일과 SQLite 데이터베이스 파일을 등을 효과적으로 복구할 수 있도록 하였다. 이러한 연구 결과를 토대로 도구를 개발하고 많은 테스트를 통해 알고리즘을 수정해 나간다면 Ext4 파일 시스템을 사용하는 많은 임베디드 기기에 대한 디지털 포렌식 분석에 많은 도움을 줄 수 있을 것이다.

질의응답

핵심어	질문	논문에서 추출한 답변
	Ext4 파일 시스템이 메타데이터를 활용한 파일 복구가 불가능한 이유는 무엇인가?	Ext4 파일 시스템은 일반적으로 윈도우에서 사용되는 NTFS와 FAT 파일 시스템과는 달리 파일이 삭제될 때 메타데이터의 데이터 블록 포인터가 초기화되므로 메타데이터를 활용한 파일 복구가 불가능하다. 또한, I/O의 효율성을 높이기 위하여 블록 포인터를 extents 구조체로 저장함으로써 Ext3 파일 시스템에 비하여 파일의 단편화는 줄어들었지만 Ext3에서 사용하던 파일 복구 방식을 사용하지 못하게 되었다[1].
	Ext4 파일 시스템에서 단편화가 발생되는 이유는 무엇인가?	Ext4 파일 시스템은 I/O의 효율성을 위해 최대한 파일 단편화를 회피하지만 단편화가 발생되는 이유는 크게 두 가지가 있다. 첫째, 생성되는 파일의 크기가 127MB 이상이거나 해당 블록그룹에서 관리하는 데이터 블록에 더 이상 저장할 공간이 없는 경우에는 파일이 조각나서 저장되며 이러한 경우 두 개 이상의 extents를 사용하게 된다. 둘째, 이미 존재하는 파일의 내용이 수정되면서 내부 데이터가 증가할 경우 추가된 데이터는 기존 파일의 데이터 블록에 연속적으로 저장되지 못하고 다른 영역으로 조각나서 저장될 수 있다. 첫 번째의 경우는 Ext4 파일 시스템을 사용하는 일반적인 리눅스 시스템과 안드로이드 운영체제에서 비슷하게 발생하지만 두 번째의 경우는 주로 안드로이드 운영체제에서 발생하며 그 빈도가 매우 높다.
	Ext4 파일 시스템은 어떤 블록 크기를 사용하는가?	본 절에서는 Ext4 파일 시스템의 전체적인 구조와 메타데이터 영역에 대해서 알아본다. Ext4 파일 시스템은 데이터 저장의 최소 단위인 블록들로 이루어져 있으며 블록의 크기는 1KB, 2KB, 4KB 중 하나를 선택하여 사용할 수 있지만 기본적으로는 4KB를 사용한다. Ext4 파일 시스템은 데이터를 효과적으로 관리하기 위해 [그림 1]과 같이 Ext4 파일 시스템 내부의 모든 블록들을 여러 개의 블록 그룹으로 묶어서 관리한다.

참고문헌 (23)

Kevin D. Fairbanks, "An analysis of Ext4 for digital forensics," Digital Investigation, Vol. 9, pp. 118-130, Aug. 2012.

상세보기
Dohyun Kim, Jungheum Park, Keun-gi Lee, and Sangjin Lee, "Forensic Analysis of Android Phone using Ext4 File System Journal Log," Lecture Notes in Electrical Engineering, Vol. 164, pp. 435-446, June. 2012.
Val Henson, Zach Brown, Theodore Ts'o, and Arjan van de Ven, "Reducing fsck time for ext2 file systems," Proceeding of the Linux Symposium, Vol. 1, July. 2006.
Philip Craiger, "Recovering Digital Evidence from Linux Systems," IFIP The International Federation for Information Processing, Vol. 194, pp. 233-244, Feb. 2005.
SANS Information, Network, Computer Security Training, Research, Resources, http://www.sans.org.
Hal Pomeranz, "EXT3 File Recovery via Indirect Blocks," http://computer-forensics.sans.org/summit-archives/2011/EXT3-file-recovery.pdf.
Gregorio Narvaez, "Taking advantage of Ext3 journaling file system in a forensic investigation," SANS Institute Reading Room, Dec. 2007.
ext3grep, http://code.google.com/p/ext 3grep.
extcarve, http://freecode.com/projects/extcarve.
giis-ext4, http://www.giis.co.in.
Stellar Phoenix Linux Data Recovery, http://www.stellarinfo.com/linux-data-recovery.htm.
EaseUS, http://www.easeus.com/datarecoverywizard.
Brian Carrier, File Sysetm Forensic Analysis, Addison Wesley Professional, 2005.
Aneesh Kumar K.V, Mingming Cao, and Jose R Santos, "Ext4 block and inode allocator improvements," Proceeding of the Linux Symposium, July. 2008.
Avantika Mathur, Mingming Cao, and Suparna Bhattacharya, "The new ext4 filesystem: current status and future plans," Proceedings of the Linux Symposium, June. 2007.
Theodore, "Speeding up file system checks in ext4," The Linux Foundation, 2009.
Guidance Software, http://www.guidancesoftware.com.
SQLite Database File Format, http://www.sqlite.org/fileformat2.html.
SQLite Database File Format2, http://www.evolane.com/support/manuals/shared/manuals/tcltk/sqlite/fileformat.html.
Simson L. Garfinkel, "GarCarving contiguous and fragmented files with fast object validation," Digital Investigation, Vol. 4, pp. S2-S12, Sept. 2007.

상세보기
Golden Richard III, Vassil Roussev and Lodovico Marziale, "In-Place File Carving," Digital Forensics III : IFIP The International Federation for Information Processing, Vol. 242, pp. 217-230, Jan. 2007.
Jungheum Park, Hyunji Chung, and Sangjin Lee, "Forensic analysis techniques for fragmented flash memory pages in smartphones," Digital Investigation, Vol 9, pp. 109-118, Nov. 2012.

상세보기
Sangjun Jeon, Jungheum Park, Keun-gi Lee, and Sangjin Lee, "An Efficient Method of Extracting Strings from Unfixed-Form Data," Lecture Notes in Electrical Engineering, Vol.164, pp.425-434, June. 2012.

저자의 다른 논문 :

LOADING...

표제어: PCR

동의어: Packet Collision Rate

용어 설명 출처 목록 (6)

용어 설명: PCR은 세균 특이성이 있는 primer를 이용하여 적은 수의 세균이 있을지라도 쉽게 검출할 수 있는 유용한 방법이며, 이를 이용하여 구강 내 치면세균막이나 타액에서 직접 세균을 검출할 수 있게 되었다[8].

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증