BAB 2
LANDASAN TEORI
Pada bab ini membahas tentang teori penunjang dan penelitian sebelumnya yang berhubungan dengan penerapan algoritma Boyer-Moore untuk menemukan kembali pesan SMS yang telah dihapus pada handphone Android.
2.1. Mobile Forensic
Mobile forensic merupakan bagian dari ilmu yang mempelajari tentang forensik digital namun dalam lingkup yang lebih kecil. Digital forensic mempelajari bagaimana caranya mengidentifikasi, mengumpulkan bahkan menganalisis suatu barang bukti digital untuk dijadikan sebagai alat bukti (Carrier, 2003). Terdapat empat tahapan dalam pembuktian bukti digital (Casey, 2011), sebagai berikut:
1.
Identifikasi bukti digital
Identifikasi bukti digital merupakan tahapan pertama dalam proses digital forensic. Identifikasi bukti digital bertujuan untuk mengidentifikasi bukti digital yang berasal dari perangkat digital. Sumber bukti digital menjadi fokus utama pada tahap ini.
8
2.
Penyimpanan bukti digital
Penyimpanan bukti digital dilakukan untuk mendapatkan bukti digital yang utuh, hal ini dilakukan untuk menghindari kerusakan, perubahan atau hilangnya barang bukti digital. Bukti digital yang utuh menentukan tingkat keberhasilan dalam melakukan digital forensic. Penyimpanan bukti digital dilakukan secara bitstream image untuk menjaga keaslian bukti digital.
3.
Analisa bukti digital
Analisa bukti digital merupakan hal yang utama dalam digital forensic. Hal ini dilakukan untuk mencari atau menganalisis keberadaan bukti digital yang mungkin ditemukan.
4.
Presentasi bukti digital
Bukti digital yang sudah ditemukan akan ditampilkan untuk dijadikan barang bukti digital yang sah menurut hukum.
Proses forensik digital bergantung pada sistem operasi yang digunakan. Sebagai contoh, kebanyakan pengguna komputer dekstop menggunakan sistem operasi Microsoft Windows, atau pengguna smartphone yang lebih banyak menggunakan sistem operasi Android. Oleh karena itu, diperlukan kemampuan untuk melakukan identifikasi pada perangkat digital tertentu yang menggunakan sistem operasi tertentu, karena banyaknya jenis perangkat digital mengakibatkan identifikasi terhadap perangkat digital sulit dilakukan (Raharjo, 2013). Mobile forensic memeberikan pemahaman tentang bagaimana barang bukti digital diperoleh dari mobile phone. Di dalam mobile phone ada banyak layanan atau fitur yang dapat dijadikan sebagai bukti digital seperti Subscriber Identity Module (SIM), internal memory, memory card dan network service providers (Zareen & Baig 2010). Adapun beberapa bukti digital yang kemungkinan besar dapat didapatkan pada mobile phone seperti pada Tabel 2.1.
9
Tabel 2.1. Daftar bukti digital yang dapat ditemukan (Zareen & Baig, 2010) No.
Bukti Digital
Sumber
1
Name of Service Provider
Dicetak dibelakang SIM Card
2
Unique Id Number
Dicetak dibelakang SIM Card
3
Location Area Identity (LAI)
Disimpan pada SIM Card
4
International Mobile Equipment Disimpan dan dicetak pada mobile phone Identity (IMEI)
5
Text Message Data (SMS)
Disimpan pada SIM Card atau memory
6
Contact
Disimpan pada SIM Card atau memory
7
Call Logs
Disimpan pada SIM Card atau memory
8
Images/Sound/Videos
Disimpan pada memory
2.2. Android
Android merupakan sistem operasi yang di kembangkan oleh Open Handset Alliance (OHA). Gabungan ini berisikan lebih dari 50 perusahaan mobile technology, mulai dari handset manufactures dan service provider sampai semiconductor manufacture dan software developers, seperti Acer, ARM, Google, eBay, HTC, Intel, LG Electronics, Qualcomm, Sprint and T-Mobile. Tujuan utama OHA adalah mempercepat innovasi terhadap perkembangan perangkat mobile dengan memberikan susuatu yang lebih murah namun memiliki kemampuan yang lebh baik (Lessard et al, 2010). Sejak dirilis hingga sekarang pengguna smartphone terus meningkat, hal ini disebabkan oleh migarasi dari feature phone ke smartphone. Menurut data yang dikeluarkan eMarketer sebuah perusahaan peneliti pasar, pengguna smartphone di seluruh dunia akan menyentuh 4,55 milliar pada 2014 sebagaimana terlihat pada Tabel 2.2. Dan data yang dikeluarkan oleh International Data Corporation (IDC) pada tahun 2015 sistem operasi Android menjadi sistem operasi mobile yang paling banyak digunakan pada smartphone dengan market share sekitar 84,8% pada tahun 2014 sebagaimana terlihat pada Tabel 2.3.
10
Tabel 2.2. Data pengguna mobile phone di dunia (eMarkerter, Dec 2013) Tahun
Jumlah(milliar)
Populasi(%)
2012
4,08
58,2
2013
4,33
61,1
2014
4,55
63,5
2015
4,77
65,8
2016
4,95
67,7
2017
5,13
69,4
Tabel 2.3. Data market share OS smartphone di dunia tahun 2014 (IDC, Aug 2015) Operating System
Market Share
Android
84,8%
iOS
11,6%
Windows Phone
2,5%
BlackBerry OS
0,5%
Others
0,7%
2.2.1. Architecture Sangat penting untuk mengenal lebih jauh lagi mengenai sistem operasi Android khusunya bagaimana arsitektur sistem operasi tersebut bekerja, hal ini dapat berguna untuk melakukan prosedur keamanan maupun dalam melakukan analisis forensik (Hoog, 2010). Secara umum arsitektur Android dibedakan menjadi lima bagian atau lapisan yaitu (Yoon, 2012) : 1. Linux Kernel
Sistem operasi Android dibuat dengan menggunakan kernel Linux 2.6, bagian ini berfungsi sebagai penghubung yang berguna untuk membantu dan mengatur hardware dan software secara bersamaan. Kenel Linux menyediakan
11
driver layar, kamera, keypad, WiFi, flash memory, audio dan IPC untuk menyediakan proses pada sumber daya aplikasi.
2. Libraries
Libraries merupakan sebuah paket pustaka yang berisi fitur - fitur yang digunakan untuk menjalankan aplikasi. Pustaka hanya dapat digunakan oleh program yang berada di level atasnya. Beberapa library yang terdapat adalah libraries media untuk memutar video atau audio, libraries SQLite untuk menggunakan database pada perangkat Android.
3. Android Runtime
Android runtime merupakan layer di mana aplikasi Android dijalankan. Core libraries merupakan sabuah paket inti yang berfungsi sebagai penerjemah bahasa C atau Java, sedangkan Dalvik Virtual Machine merupakan mesin virtual berbasis register yang digunakan untuk pengoptimalan dalam menjalankan fungsi - fungsi Android secara efisien.
4. Application Framework
Dalam membangun aplikasi, Android menggunakan kerangka aplikasi yang menyediakan kelas - kelas tersendiri. Selain itu, juga menyediakan abstraksi generik untuk mengakses, serta mengatur tampilan user interface dan sumber daya aplikasi.
5. Applications Layer
Top-level dari arsitektur Android adalah lapisan aplikasi. Lapisan ini yang pertama kali tampak ketika pengguna mengoperasikan perangkat Android, tanpa mengetahui proses apa saja yang sedang berlangsung di balik lapisan ini. Program berjalan dalam Android runtime dengan menggunakan kelas dan service dari framework application.
12
Bagian - bagian tersebut bekerja secara bersamaan dan saling bergantung dengan yang lain. Rangkuman bagian arsitektur Android dapat dilihat pada Gambar 2.1.
APPLICATIONS Home
Contact
Phone
Browser
...
APPLICATION FRAMEWORK Activity Manager
Package Manager
Window Manager
Telephony Manager
Content Provider
Resource Manager
View System
Location Manager
Notification Manager
ANDROID RUNTIME
LIBRARIES Surface Manager
Media Framework
SQLite
Core Libraries
OpenGL | ES
Free Type
WebKit
Dalvik Virtual Machine
SGL
SSL
libc
LINUX KERNEL Display Driver
Camera Driver
Flash Memory Driver
Keypad Driver
WiFi Driver
Audio Driver
Binder (IPC) Driver Power Management
Gambar 2.1. Arsitektur sistem operasi Android (Yoon, 2012)
2.2.2. Library Layer Bagian terpenting dalam melakukan analisis forensik adalah tempat di mana data tersebut disimpan. Bagian ini berada pada lapisan libraries. Pada perangkat Android semua data disimpan dalam database file berjenis SQLite. Beberapa data seperti pesan
13
SMS, call history, browser history, password dan lainnya disimpan dalam sebuah file database SQLite. SQLite yang memiliki sifat removable sangat membantu dalam melakukan analisis forensik. SQLite merupakan sebuah embedded database yang bersifat open source, yang dibuat dengan menggunakan bahasa C oleh D. Richard Hipp, jika dibandingkan dengan database lainnya seperti SQL Server, Oracle, MySQL dan lainnya, SQLite merupakan database yang ringan digunakan dalam prosesnya, selain itu SQLite menjadi embedded database yang mempunyai engine yang lengkap sehingga tidak membutuhkan komponen yang lain, ada delapan keunggulan yang dimiliki SQLite antara lain (Bi, 2009) : 1. Open Source Embedded Database
SQLite merupakan embedded database yang bersifat open source. Terdiri kurang dari 30.000 baris ANSI C, yang mana ini dapat digunakan secara bebas untuk tujuan tertentu.
2. Practical Database
SQLite tidak memerlukan proses instalasi dan konfigurasi, tidak memerlukan proses start dan stop, dan tidak membutuhkan wewenang seorang administrator. Seperti pada kasus system collapse atau lose of power, SQLite dapat mengembalikan keadaan seperti semula secara otomatis.
3. Easily Database
File database SQLite dapat dibaca dan ditulis pada media penyimpanan secara langusng tanpa membutuhkan proses tambahan. File database yang sama dapat digunakan pada perangkat yang berbeda.
14
4. No Data Type
Perbedaan yang mencolok pada SQLite terletak pada tidak ada tipe datanya. SQLite dapat memasukan data apapun ke tabel apapun, tanpa mengetahui atribut data tersebut.
5. Many Support
SQLite mendukung ACID dan SQL92 serta multiple tables dan indexes, transactions, views, triggers seperti database umumnya.
6. Multi Platform
SQLite memiliki kinerja yang cepat, efisien dan terukur, yang tidak bergantung pada sistem operasi yang sedang digunakan. SQLite dapat digunakan pada sistem operasi yang beragam.
7. Supports API
SQLite menyediakan banyak dukungan untuk terhadap API, dan mendukung bahasa pemrograman yang umum seperti C/C++, PHP, Perl dan lainnya. API berguna sebagai penghubung antara programming language dengan database file.
8. Good reliability
SQLite memiliki ketahanan yang bagus dalam melakukan sebuah proses data. Dan telah memenuhi dari 90% cakupan uji.
2.2.3. Database Architecture Data yang tersimpan dalam smartphone Android memiliki aturan yang baku dalam penyimpanan datanya, walaupun ada aplikasi yang tidak membutuhkan media
15
penyimpanan (Hoog, 2010). Secara umum file database yang digunakan pada smartphone Android berada pada direktori data/data/<packagaName>/databases seperti pada Tabel 2.4 .
Tabel 2.4. Subdirektori /data/data/<packageName> (Hoog, 2010) shared_prefs
Directory Storing
lib
Custom library files an application requires
files
Files the developer saves to internal storage
cache
Files cached by the application
databases
SQLite database and journal files
File database yang menyimpan data pesan SMS berada pada direktori /data/data/com.android.providers.telephony/databases/mmssms.db. File mmssms.db memliki beberapa tabel seperti pada Gambar 2.2. Pesan SMS tersimpan dalam tabel sms pada database tersebut. Adapun arsitektur tabel sms seperti pada Tabel 2.5. Android_metadata
pdu
canonical_addresses
locale
sqlite_sequences
Words_contentc
Pending_msgs
Words_segment
Pdu_recipient_threads
Semc_metadata
sms
raw
threads
Words_segdir
Semc_threads
part
attachment
rate
addr
drm
Sr_pending
Gambar 2.2. Tabel pada file database mmssms.db (Hoog, 2010)
16
Tabel 2.5. Arsitektur tabel sms (Hoog, 2010) Name
Type
_id
INTEGER PRIMARY KEY
thread_id
INTEGER
address
TEXT
person
INTEGER
date
INTEGER
date_sent
INTEGER
protocol
INTEGER
read
INTEGER
status
INTEGER
type
INTEGER
reply_path_present
INTEGER
subject
TEXT
body
TEXT
service_center
TEXT
locked
INTEGER
error_code
INTEGER
seen
INTEGER
semc_message_priority
INTEGER
parent_id
INTEGER
delivery_status
INTEGER
star_status
INTEGER
2.3. Short Message Service
Short Message Service (SMS) merupakan layanan yang berbentuk Instant Messaging (IM) yang memungkinkan user untuk bertukar pesan singkat kapanpun dan dimanapun. Pesan SMS dikirim menggunakan jaringan GSM (Global System for Mobile Comunication). Sebuah pesan SMS maksimal terdiri dari 140 bytes, dengan
17
kata lain sebuah pesan bisa memuat 140 karakter 8-bit, 160 karakter 7-bit atau 70 karakter 16-bit. Dengan perkembangan teknologi yang semakin pesat, layanan text messages sudah sesuatu yang tidak asing lagi bagi user. Konsep yang user friendly memberikan kemudahan bagi pengguna sehingga layanan ini menjadi sangat disukai. Menurut data yang dikeluarkan oleh Pew Research Center pada tahun 2012 pengguna smartphone sangat aktif menggunakan layanan text messages sebesar 61% per hari dan 80% per minggu, hal ini membuat layanan text messages menjadi layanan favorit pada pengguna smartphone, sebagaimana terlihat pada Tabel 2.6.
Tabel 2.6. Aktivitas pengguna smartphone (Pew Research Center, Oct 2012) Activity
Weekly (%)
Daily (%)
Text Messages
80
61
Internet Browsing
62
36
Played Games
54
31
Social Networking Site
62
46
Music/Videos
31
8
Read books
15
7
Shop
24
5
Read magazines
11
4
2.3.1. Deleted Message Penggunaan yang mudah, cepat dan efisien membuat layanan ini menjadi pilihan utama dalam melakukan komunikasi. Baik penggunaan secara pribadi maupun untuk keperluan umum. Bahkan tidak jarang pesan SMS berisikan sebuah pesan rahasia yang ingin ditunjukan pengirim kepada penerima untuk maksud dan tujuan tertentu. Di era modernisasi ini tidak jarang pesan SMS menjadi alat bukti dalam penyidikan kasus tindak kejahatan, sebagaimana yang diatur dalam Undang - Undang No 11 Tahun 2008 tentang Informasi dan Transkasi Elektronik. Penghapusan, penghilangan atau penyembunyian pesan SMS sama saja dengan melakukan tindak kejahatan. Pada perangkat Android penghapusan pesan SMS dapat dibedakan menjadi empat jenis yaitu :
18
1. Delete Message
Delete message merupakan salah satu pilihan untuk menghapus satu item pesan SMS yang dikirim atau yang diterima.
2. Delete Conversation
Delete conversation merupakan pilihan untuk menghapus seluruh percakapan pesan SMS berdasarkan satu nomor pengirim.
3. Delete Several
Delete several memiliki fungsi yang sama dengan delete conversation, namun memiliki pilihan item nomor pengirim lebih dari satu.
4. Delete All
Delete all memeiliki fungsi menghapus seluruh percakapan pesan SMS yang ada pada smartphone Android tersebut, baik itu pesan SMS keluar atau masuk.
Pesan SMS tersimpan dalam sebuah file database berjenis SQLite, pesan SMS yang dihapus kemungkinan tidak dihapus secara permanen atau ditimpa dengan pesan SMS yang lain, pesan SMS yang sudah dihapus tersebut masih disimpan dalam file database. Pesan SMS yang telah dihapus masih mungkin untuk ditemukan selama pesan SMS tersebut belum ditimpa oleh pesan SMS yang baru. Pesan SMS yang telah dihapus tersebut bisa dilihat dalam bentuk hexadecimal dengan pola yang mudah dipahami (Hoog, 2010). Pada banyak kasus, penghapusan pesan SMS dalam file database SQLite tidak disempurnakan dengan penghapusan bit nya, sehingga pesan SMS tersebut tidak benar - benar terhapus secara bersih, kondisi ini dapat digunakan untuk menemukan kembali pesan SMS yang telah dihapus (Stahlberg at al, 2007). Record pesan SMS yang dihapus akan dipindahkan ke ruang yang tidak terisi pada memori, sedangkan ruang yang kosong akan digunakan kembali dengan record
19
yang baru, dengan mempertimbangkan dua faktor: apakah record yang baru akan cocok dengan ruang yang diberikan dan apakah record yang baru memenuhi tata aturan pada tabel tersebut. Proses penghapusan dan pemasukan record dapat dilihat pada Gambar 2.3. Proses ini dibagi menjadi empat tahapan, yaitu : 1. Tahap pertama terdapat enam record yang aktif, yang menempati sebagian ruang yang sudah dialokasikan untuk table storage. 2. Tahap kedua, setelah penghapusan record t3 dan t5, ruang yang ditempati akan dibebaskan, tetapi data tersebut masih dapat dipulihkan. 3. Selanjutnya pada tahap ketiga, record t7 dimasukan, menggunakan ruang bebas yang ada sehingga menimpa record t3. Dilain sisi terdapat proses penghapusan record t1 dan t4. 4. Pada tahap selanjutnya prosedur vacuum dijalankan, untuk mengatur kembali active records (t2,t7,t6), dan mengurangi ruang yang dialokasikan pada database file. Record t5 akan dibuang dan menduplikat record t6 pada ruang yang tidak terisi di file system.
Gambar 2.3. Ilustrasi insert dan delete record (Stahlberg at al, 2007)
2.3.2. Message Pattern Pesan SMS yang telah dihapus dapat dilihat ketika proses generate sudah dilakukan. Proses generate ini mengubah file database SQLite ke dalam bentuk hexadecimal. Pola hexadecimal ini yang akan diteliti untuk mendapatkan pesan SMS yang sudah
20
dihapus. Secara garis besar pola yang berasal dari proses generate ini dibagi menjadi empat bagian seperti pada Gambar 2.5 dan Gambar 2.6, yaitu :
1. File Info
Pada bagian ini terdapat informasi tentang identifikasi jenis file. Pada 16 bytes pertama maka akan ditemukan pola hexadecimal 53 51 4C 69 74 65 20 66 6F 72 6D 61 74 20 33 00 , jika diubah ke dalam bentuk ASCII menjadi “SQLite format 3.”, ini menunjukan file tersebut berjenis database SQLite.
2. Struktur Tabel Database
Selanjutnya setelah bagian file info, terdapat bagian struktur tabel database. Pada bagian ini seluruh tabel dan strukturnya yang ada pada database akan direpresentasikan dalam hexadecimal. Setiap tabel yang ada akan ditandai dengan pola 43 52 45 41 54 45 20 54 41 42 4C 45 jika diubah ke dalam karakter ASCII menjadi “CREATE TABLE”.
3. Pesan SMS
Pola pesan SMS baik itu yang masih tersimpan atau yang sudah dihapus selalu diawali oleh header pesan SMS tersebut, kemudian nomor pesan sms, tanggal dan isi pesan SMS. Selengkapnya dapat dilihat pada Gambar 2.4.
Gambar 2.4. Pola pesan SMS (Hoog, 2010)
Keempat bagian dalam Gambar 2.4 terdiri dalam pola heksadesimal. Header pesan SMS terdeiri dari rangkaian bytes 08 08 08. Nomor pesan SMS umumnya diawali dengan +62 untuk standart nomor negara Indonesia atau 2B 36 32 kemudian diikuti digit nomor selanjutnya. Sama seperti no_id, isi_pesan juga dapat dengan mudah dibaca dengan cara mengkonversi kedalam karakter ASCII. Namun 6 bytes setelah no_id merupakan waktu pesan SMS tersebut
21
dikirim atau diterima. Untuk mengetahui waktu pesan SMS tersebut 6 bytes pola akan diubah terlebih dahulu dalam bentuk decimal, kemudian didapatkan pola waktu berdasarkan Unix Epoch in milliseconds (Hoog, 2010). Contoh : 01 41 30 74 FF DA diubah kedalam desimal menghasilkan 13799497476058 ini merupakan bentuk waktu dalam bentuk Unix Epoch dan ketika diubah kedalam bentuk waktu biasa maka akan didapatkan Rabu, 18 September 2013 09:44:36.
4. Trigger Database
Kemudian pada bagian terakhir terdapat kumpulan trigger yang digunakan pada file database tersebut. Seperti trigger insert, trigger update atau trigger delete.
Gambar 2.5. Struktur file database yang tidak berisi pesan SMS (Hoog, 2010)
22
Gambar 2.6. Struktur file database yang berisi pesan SMS (Hoog, 2010)
2.4. String Matching
String matching atau pencocokan string merupakan sebuah metode pencarian sebuah pattern P [1........m] pada teks T [1........n] dimana m<=n (Lecroq, 1992). Terdapat dua teknik yang biasa digunakan pada string matching, yang pertama adalah exact matching, teknik ini digunakan pada algoritma Needleman Wunsch, Smith Waterman, Knuth–Morris–Pratt, Dynamic Programming, maupun Boyer-Moor, selain exact matching terdapat teknik lainnya yaitu approximate matching, teknik ini digunakan pada algoritma fuzzy string, Rabin Karp, Brute Force (Singla et al, 2012).
2.4.1. Exact String Matching Exact string matching merupakan pencocokan string secara tepat dengan susunan karakter yang ada pada pattern P dan teks T (Knuth et al, 1977), string yang dicocokan memiliki jumlah maupun urutan karakter yang sama.
23
Teks T = t1, t2, t3 ... tn dimana n adalah panjang teks sedangkan pattern P = p1, p2, p3 ... pm m adalah panjang pattern. Exact string matching membandingkan karakter yang ada teks T dengan karakter yang pada pattern P dengan berdasarkan kecocokan karakter (Bhandari et al, 2013). Sebagai contoh : algorithm dengan alggrithm, memiliki jumlah karakter yang sama namun ada satu karakter yang berbeda maka dianggap tidak cocok.
2.4.2 Approximate String Matching Approximate string matching merupakan pencocokan string berdasarkan kemiripan karakter dari segi penulisannya yang ada pada pattern P dan teks T (Patrick et al, 1980). Tingkat kemiripan ditentukan oleh jumlah karakter dan susunan karakter, serta kemiripan antara dua buah string yang dibandingkan. Contoh : a goritna dengan algoritma, memilki jumlah karakter yang sama namun terdapat dua karakter yang berbeda. Jika perbedaan ini dianggap sebagai kesalahan dalam penulisan, maka dua string tersebut dapat dikatakan cocok. Approximate string matching secara umum dapat diasumsikan dengan T1...n dimana T adalah teks dan n panjang teks, kemudian P1...m dimana P adalah pattern dan m panjang pattern yang relatif lebih singkat dari n. Kemiripan atau kecocokan ditentukan oleh jumlah karakter alfabet ∑ dan urutan alfabet σ . Dan
k yang
menyatakan ketidakcocokan diantara dua buah string (Navarro, 2001).
2.4.3. Window Sliding Window sliding merupakan teknik yang diterapkan pada exact matching, teknik ini menggunakan bantuan window sebagai poros pergeseran pattern untuk kemudian dicocokan pada teks seperti pada Gambar 2.7. Prinsip kerja metode ini adalah sebagai berikut : 1. Melakukan pencocokan teks dengan bantuan window yang memiliki ukuran yang sama dengan panjang pattern. 2. Meletakan karakter pattern pada window 3. Menempatkan window pada awal teks 4. Mencocokan karakter pada window dengan karakter pada teks. Setelah melakukan pencocokan, baik itu hasilnya cocok atau tidak cocok, dilakukan
24
shift ke kanan teks. Prosedur ini dilakukan secara berulang - ulang sampai window berada pada akhir teks, atau pada posisi terkanan teks.
Teks
Window
shift
Window
Gambar 2.7. Ilustarsi windows sliding Algoritma string matching mempunyai tiga komponen utama (Crochemore et al, 1996), sebagai berikut : 1. Pattern, yaitu deretan karakter yang akan dicocokan dengan teks, pattern diasumsikan dengan x = x[0...m-1], dengan m adalah panjang pattern. 2. Teks, yaitu deretan karakter yang akan dicoba kecocokannya dengan pattern, teks diasumsikan dengan y=y[0...n-1], dengan y adalah panjang teks. 3. Alfabet, berisi semua simbol yang digunakan pada teks dan pattern, diasumsikan dengan ∑ , dan ASIZE sebagai ukurannya.
2.5. Algoritma Boyer-Moore
Algoritma Boyer Moore termasuk salah satu algoritma yang memiliki kinerja yang lebih baik dalam melakukan pencarian string khususnya dalam jenis data ASCII, biner dan heksadesimal (Dermawan, 2001). Algoritma ini melakukan pencocokan string dari kanan ke kiri, karakter yang berada paling kanan pada string merupakan karakter pertama yang akan dicocokan dengan teks atau pattern (Boyer et al, 1977). Algoritma ini menggunakan dua fungsi shift untuk mengambil jumlah langkah pergeseran berikutnya ketika terjadi
25
ketidakcocokan, dua fungsi shift tersebut adalah bad-character shift atau occurrence shift dan good-suffix shift atau heuristic shift (Choudhary et al, 2012).
2.5.1. Deskripsi kerja algoritma Boyer-Moore Deskripsi kerja algoritma boyer moore dapat dijelaskan dengan membuat sebuah contoh kasus ketidakcocokan pada saat pencocokan karakter pada teks dan pattern berlangsung. Karakter pattern x[i]=a tidak cocok dengan karakter teks y[i+j]=b saat pencocokan pada posisi j. Maka x[i+l .. m-1]= y[i+j+1 .. j+m-1]=u dan x[i] ≠ y[i+j] (Choudhary et al, 2012). Maka dari kasus ketidakcocokan tersebut diambil langkah pergeseran selanjutnya dengan memilih jumlah pergeseran yang paling besar antara bad-character shift dan good-suffix shift, hingga karakter pada teks y[i+j] memenuhi karakter yang ada pada pattern x[i].
2.5.2 Bad-Character Shift Bad-character adalah karakter yang ada pada teks y[i+j] yang tidak cocok dengan karakter pada pattern x (Crochemore et al, 1996). Sehingga jumlah pergeseran maksimum bad-character shift dapat diambil dari jumlah pattern x[i]. Konsep dari fungsi bad-character shift adalah sebagai berikut : 1. Jika bad-character y[i+j] terdapat pada pattern di posisi terkanan k yang lebih kiri dari x[i] maka pattern digeser ke kanan sejauh i-k. Seperti diberikan pada Gambar 2.8.
y
x
x
b
u
a
u
b
Contains no b
shift
Gambar 2.8. Bad-character shift, b terdapat di pattern x
26
2. Jika bad-character y[i+j] tidak ada pada pattern sama sekali, maka pattern dapat digeser ke kanan sejauh jumlah i. Hal ini ditunjukan pada Gambar 2.9.
y
x
b
u
a
u
shift
x Contains no b Gambar 2.9. Bad-character shift, b tidak ada di pattern x 3. Jika bad-character y[i+j] terdapat pada pattern di posisi terkanan k yang lebih kanan dari x[i] maka pattern seharusnya digeser sejauh i-k yang hasilnya negatif. Maka bila kasus ini terjadi akan diabaikan, karena pergeseran selanjutnya dari algoritma boyer-moore akan diambil jumlah pergeseran yang baling besar (Cantone et al, 2010).
Pada tabel bad-character, setiap karakter pada pattern diberi nilai sesuai dengan ukuran jauhnya karakter tersebut dari karakter paling kanan dari pattern dan untuk karakter yang tidak terdapat pada pattern akan diberi nilai sejumlah karakter pada pattern. Adapun pseudocode untuk pergeseran bad-character ini adalah sebagai berikut : Procedure preBmBc( input y : array[0..n-1]of char, input n : integer, input/output bmBc : array of integer ) Deklarasi i:integer Algoritma for (i=0; i
27
2.5.3. Good-suffix shift Good-suffix merupakan jumlah pergeseran yang dihitung berdasarkan posisi di mana ketidakcocokan terjadi. Aturan pada good-suffix shift dijelaskan sebagai berikut : 1. Good-suffix shift merupakan pergeseran yang dibutuhkan dari x[i]=a ke karakter lain yang letaknya lebih kiri dari x[i] dan terlektak di sebelah kiri segmen u seperti pada Gambar 2.10.
y
x
x
b
u
a
u
c
u
shift
Gambar 2.10. Good-suffix shift, u terjadi lagi didahului karakter c berbeda dari a
2. Jika tidak ada segmen yang sama dengan u, maka cari u yang merupakan suffiks terpanjang u. Dalam hal ini ditunjukan pada Gambar 2.11.
y
x
b
u
a
u
x
shift
v
Gambar 2.11. Good-suffix shift, hanya suffix dari u yang terjadi ladi di pattern x
Pada tabel pergeseran good-suffix, nilai pergeseran digunakan ketika ketidakcocokan ditemukan
berdasarkan
karakter
pada
posisi
keberapa
yang
menyebabkan
ketidakcocokan. Nilai dari setiap karakter yang ada pada pattern bergantung terhadap ada atau tidaknya perulangan akhiran(suffix) v dari text pada pattern. Semakin banyak
28
perulangan, maka akan semakin kecil nilai pergeseran. Untuk menentukan nilai-nilai tersebut, lebih dahulu menghitung nilai tabel suffix yang bertujuan untuk memberi tanda adanya perulangan akhiran. Dari tabel suffix inilah tabel good-suffix akan didapat.
Pada tabel suffix, berisi nilai dari tiap karakter yang ada pada pattern yang menunjukkan ada atau tidaknya perulangan akhiran (suffix) dan dimana posisi perulangan tersebut sehingga ketika proses perhitungan tabel good-suffix dapat diketahui seberapa banyak pergeseran yang akan dilakukan untuk pencocokan selanjutnya. Adapaun pseudocode untuk pergeseran good-suffix adalah sebagai berikut : Procedure suffixes( input y: array[0..n-1] of char, input n: integer, input/output suff: array of integer ) Deklarasi f, g, i : integer Algoritma suff[n-1] ← n; g ← n-1 for (i = n-2; i >= 0; --i) if(i > g and suff[i + n – 1 - f] < i-g)do suff[i] ← suff[i + n – 1 - f]; else if(i= 0 and y[g] == y[g + n – 1 - f])do --g; suff[i] ← f-g; endif endfor Procedure preBmG ( input y: array of char, input n:integer, input/output bmGs: array of integer ) Deklarasi i, j : integer suff : array [0..YSIZE] of integer Algoritma suffixes(y, n, suff) for (i=0; i < n; ++i)do
29
bmGs [i] ← n for (i= n-1; i >= -1; --1) if(i == -1 or suff[i] == i+1) for(j=0; j < n-1-i; ++j) if(bmGs[j] == n) bmGs[j] ← n-1-i for (i=0; i <= n-2; ++i) bmGs[n-1-suff[i]] ← n-1-i
2.5.4. Cara kerja algoritma Boyer-Moore Pada kasus ketidakcocokan terjadi, algoritma akan membandingkan nilai pergeseran yang dimiliki oleh bad-character shift dan good-suffix shift, di mana nilai pergeseran yang memiliki nilai yang paling besar yang akan digunakan untuk melakukan pergeseran selanjutnya. Cara kerja dari algoritma Boyer-Moore dapat dijabarkan sebagai berikut :
1. Manjalankan terlebih dahulu prosedur preBmBc dan preBmGs untuk mendapatkan jumlah pergeseran.
a. Menjalankan prosedur preprocessing Boyer-Moore bad-character (preBmBc). Prosedur ini untuk menjalankan fungsi menentukan berapa jumlah pergeseran yang dibutuhkan untuk mencapai karakter tertentu pada teks dari karakter pattern terakhir atau terkanan. Hasil dari prosedur preBmBc disimpan pada tebel BmBc.
b. Menjalankan prosedur suffix, prosesdur suffix dijalankan untuk memeriksa kecocokan sejumlah karakter yang berada di posisi terakhir atau terkanan dengan sejumlah karakter yang dimulai dari setiap karakter yang lebih kiri dari karakter yang terkanan tadi. Hasil dari prosedur disimpan dalam tabel suffix. Suffix[i] mencatat panjang dari suffix yang cocok dengan segmen dari pattern yang diakhiri karakter ke-i.
c. Menjalankan
prosedur
preprocessing
Boyer-Moore
good-suffix
(preBmGs). Prosedur ini dijalankan untuk mengetahui berapa banyak langkah pada pattern dari sebuah segmen ke segmen yang lain yang
30
sama yang letaknya lebih kiri dengan karakter di sebelah kiri segmen yang berbeda. Prosedur preBmGs menggunakan tabel hasil dari prosedur suffix untuk mengetahui pasangan segmen yang sama.
2. Melakukan proses pencarian string dengan menggunakan hasil dari prosedur BmBc dan BmGs yaitu tabel BmBc dan BmGs. Dan melakukan perbandingan untuk menentukan jumlah pergeseran selanjutnya.
2.6. Penelitian Terdahulu
Metode string matching telah banyak diimplementasikan pada algoritma pencarian baik itu dengan metode exact string macthing maupun approximate string matching. Metode tersebut digunakan untuk melakukan pencarian string di dalam pattern. Tenlima (2009) menggunakan salah satu algoritma string matching dalam melakukan pencocokan string pada dokumen teks dengan menggunakan algoritma Knuth-Morris-Pratt (KMP). Pada penelitian ini Tenlima berusaha untuk membantu mencari, mencocokan dan melakukan pengeditan string pada teks dengan menggunakan algoritma KMP. Hoog (2011) menggunakan perintah grep dalam melakukan pencarian pesan SMS yang telah dihapus. Grep merupakan perintah dalam sistem operasi Linux/UNIX yang berguna untuk melakukan pencarian kata atau frase pada sebuah file. Grep menggunakan algoritma Aho-Corasick dalam implementasinya. Pencarian dilakukan dengan menggunakan perintah-perintah lainnya agar hasil pencarian lebih efektif. Perintah ini yang digunakan Hoog dalam mencari pesan SMS yang sudah dihapus berdasarkan id nomor pesan SMS tersebut. Stahlberg (2007) melakukan penelitian tentang karakteristik file database SQLite, menerangkan bahwa penghapusan record atau data dalam file database SQLite tidak dibarengi dengan penghapusan bit pada memori, data yang telah dihapus masih tersimpan dalam file database, sehingga menemukan kembali data tersebut sangat mungkin dilakukan selama data tersebut belum ditimpa dengan data yang baru.
