BAB III ANALISIS Untuk membangun perangkat lunak yang mampu mendeteksi kasus plagiarisme pada sekumpulan source code dengan menggunakan metode berbasis struktur, dilakukan analisis terhadap Learning Management System (LMS) secara keseluruhan dan detektor plagiarisme sebagai salah satu komponen LMS. Analisis LMS diberikan pada Subbab 3.1, sedangkan analisis detektor plagiarisme diberikan pada Subbab 3.2.
3.1 Deskripsi Sistem Learning Management System (LMS) merupakan kombinasi berbagai perangkat lunak yang secara keseluruhan berfungsi untuk manajemen dan pengumpulan learning content [NEI02]. Pada Tugas Akhir ini, sebuah detektor plagiarisme otomatis akan dibangun untuk menjadi komponen baru pada suatu LMS yang bernama Milestone. Milestone dipakai untuk pengumpulan dan manajemen tugas pemrograman di
laboratorium programming program studi Informatika Institut Teknologi Bandung. LMS tersebut dibuat oleh asisten laboratorium programming pada tahun 2006. Detektor yang akan dikembangkan mempunyai fungsi utama untuk mendeteksi plagiarisme tugas pemrograman yang dikumpulkan.
upload tugas pemrograman
Mahasiswa
komunikasi
pemberian tugas
Pengajar grading
deteksi plagiarisme
Milestone
Gambar III-1. Deskripsi Learning Management System Milestone
1
III-2 Deskripsi Learning Management System Milestone dapat dilihat pada Gambar III-1. Terdapat dua aktor yaitu mahasiswa dan pengajar. Aktor pengajar merupakan aktor yang mempunyai peran sebagai penilai atau pembuat keputusan mengenai sistem penilaian, misalnya dosen dan asisten. Saat Tugas Akhir ini ditulis, LMS Milestone masih dalam tahap pengembangan. Grading dan komunikasi masih dilakukan manual, sementara upload tugas pemrograman masih belum sempurna. Pembahasan pada Tugas Akhir ini hanya mencakup use case deteksi plagiarisme saja.
3.2 Detektor Plagiarisme pada Source Code Analisis mengenai detektor plagiarisme diawali dengan analisis keunggulan detektordetektor terdahulu dan karakteristik kelas pemrograman untuk menentukan spesifikasi detektor. Pembahasan dilanjutkan dengan analisis algoritma pembandingan yang akan dipakai, analisis spesifikasi fungsional utama detektor plagiarisme, use case dan skenario penggunaan, diakhiri dengan rancangan global yang disertai penjelasan untuk setiap subsistem penting dalam detektor plagiarisme. Detektor plagiarisme yang dianalisis akan diimplementasikan dan diberi nama Deimos. 3.2.1 Adopsi Aspek-aspek Perangkat Lunak Pendeteksi Plagiarisme Beberapa perangkat lunak pendeteksi plagiarisme pada source code yang menggunakan metode structure-based telah dibahas pada Subbab 2.3. Hasil eksplorasi akan digunakan sebagai dasar analisis detektor plagiarisme Deimos yang akan dikembangkan pada Tugas Akhir ini. Aspek-aspek tertentu dari masing-masing perangkat lunak akan diadopsi dan diimplementasikan pada pembangunan detektor plagiarisme Deimos. Ikhtisar adopsi aspek-aspek perangkat lunak pendeteksi plagiarisme yang akan diimplementasikan pada Deimos diberikan pada Tabel III-1. Algoritma pembandingan yang akan diterapkan di Deimos yaitu algoritma Running Karp-Rabin Greedy String Tiling (penjelasan detil mengenai algoritma ini terdapat pada Subbab 2.2). Algoritma LCS yang dipakai di YAP1 mempunyai masalah jika ada perubahan urutan substring. Algoritma Heckel yang dipakai di Plague dan YAP2 mempunyai kelemahan juga karena substring panjang yang lebih mungkin merupakan hasil praktek plagiarisme seringkali tidak diutamakan. Oleh karena itu, algoritma RKR-GST yang dapat menangani masalah-masalah algoritma LCS dan Heckel
III-3 dipilih. Algoritma tersebut tidak mempunyai masalah dengan perubahan urutan substring dan selalu mengutamakan substring identik yang lebih panjang. Berkaitan dengan algoritma RKR-GST yang dipilih menjadi algoritma pembandingan, representasi linier source code yang akan dipakai pada Deimos adalah token string dengan token berupa numerik (integer). Pada algoritma RKR-GST, perlu dilakukan hashing terhadap deretan token. Oleh karena itu, token yang berupa numerik akan mempercepat proses hashing, karena dapat langsung digunakan pada fungsi hash. Jika token berupa string, maka nilai hash untuk setiap token perlu dihitung terlebih dahulu sebelum menghitung nilai hash untuk deretan token. Tabel III-1 Ikhtisar Aspek-aspek Perangkat Lunak Pendeteksi Plagiarisme yang Akan Diimplementasikan pada Deimos Plague YAP JPlag Deimos Aspek RKR-GST RKR-GST Algoritma Heckel YAP1: LCS pembandingan YAP2: Heckel YAP3: RKR-GST Representasi Structure profile Token file, dengan Token string, Token string, dengan linier source setiap token dengan setiap token setiap token berupa code berupa angka berupa string angka Extendability Banyak bagian Membangun Membangun Membangun tokenizer untuk bahasa pada aplikasi tokenizer baru tokenizer baru baru pemrograman harus dibangun lain ulang. Portability UNIX UNIX Cross-platform Cross-platform Melalui antarmuka Akses dan Desktop-based Desktop-based Desktop-based, web, pengguna dapat cara kerja namun terdapat mengeksekusi deteksi antarmuka web hanya untuk upload source code yang sudah di-upload kumpulan source melalui LMS. code. Setelah source code diupload, deteksi dieksekusi secara manual. Tampilan Text-based Text-based Halaman HTML di- Hasil diolah dengan server-side script dan hasil deteksi generate oleh ditampilkan dalam detektor. format HTML.
Seperti yang telah diuraikan pada Subbab 2.3.1, untuk menambahkan fitur penanganan bahasa pemrograman baru pada Plague, perlu banyak perubahan di berbagai komponen. Sedangkan pada YAP dan JPlag, tanggung jawab untuk merubah source code menjadi token string dan tanggung jawab untuk melakukan pembandingan sudah jelas dipisahkan dan didelegasi pada unit yang berbeda, sehingga untuk menambahkan penanganan bahasa pemrograman baru hanya perlu merubah komponen yang bertugas untuk merubah source code menjadi token string
III-4 (sering disebut sebagai tokenizer). Oleh karena itu, pada Deimos tanggung jawab untuk tokenisasi dan pembandingan juga akan diberikan pada unit yang berbeda. 3.2.2 Karakteristik Kelas Pemrograman Dasar Salah satu aspek penting pada penentuan spesifikasi detektor plagiarisme adalah karakteristik lingkungan tempat detektor akan digunakan dan karakteristik umum kumpulan source code yang akan dideteksi. Belum ada sistem deteksi yang benarbenar sempurna diimplementasikan pada berbagai lingkungan penggunaan. Dari pembahasan pada Subbab 2.3, bisa disimpulkan bahwa setiap detektor plagiarisme mengutamakan beberapa requirement untuk dipenuhi terlebih dahulu sesuai dengan target implementasi. YAP mengorbankan sedikit akurasi deteksi agar waktu deteksi menjadi lebih singkat daripada Plague. Terdapat juga berbagai detektor plagiarisme
lain yang
menggunakan
metode
deteksi
berbeda yang
lebih
mengutamakan sensitivity dan specifity walaupun kompleksitas algoritma yang dipakai meningkat secara eksponensial sesuai dengan jumlah file yang dibandingkan [CHE03]. Waktu yang digunakan untuk proses deteksi memang tidak diutamakan pada detektor-detektor jenis tersebut. JPlag masih tertipu oleh beberapa jenis modifikasi ketika pengujian, tapi dianggap salah satu sistem terbaik jika mempertimbangkan akurasi yang cukup tepat dan waktu deteksi yang cukup singkat. YAP3 dan JPlag dikembangkan agar memenuhi kebutuhan deteksi secara umum
sehingga hasilnya cukup efektif ketika menangani kumpulan program dalam berbagai tingkat kerumitan, walaupun akan terjadi local confusion yang disebabkan oleh beberapa jenis modifikasi yang dilakukan plagiator. Modifikasi rumit yang tidak bisa ditangani YAP3 dan JPlag tersebut ada yang dapat ditangani oleh detektor plagiarisme yang menggunakan pembandingan representasi dinamik program. Biasanya detektordetektor tersebut dikembangkan untuk mendeteksi program besar dengan algoritmaalgoritma yang cukup rumit. Pada Tugas Akhir ini, detektor plagiarisme otomatis Deimos dikembangkan dengan konteks untuk mendeteksi plagiarisme di kelas pemrograman dasar yang jumlah mahasiswanya mencapai ratusan. Selain itu, biasanya deteksi dilakukan secara rutin dengan frekuensi yang cukup tinggi. Dengan mempertimbangkan banyaknya jumlah program yang perlu dibandingkan dan frekuensi deteksi, maka waktu proses deteksi
III-5 yang singkat sangatlah penting. Algoritma Running Karp-Rabin Greedy String Tiling sangatlah tepat untuk diterapkan karena mempunyai kompleksitas rata-rata yang hampir linier. Pada kelas pemrograman dasar, selain soal yang diberikan masih sederhana, modifikasi yang dilakukan oleh plagiator pun biasanya juga sederhana karena belum banyaknya pengetahuan pemrograman yang dimiliki. Sebagian besar sistem yang telah dibangun mengasumsikan source code yang akan dideteksi merupakan program yang cukup rumit dan panjang. Namun, topik-topik pada kelas pemrograman dasar belum terlalu rumit. Biasanya memang sebagian besar submisi yang dikumpulkan akan mempunyai kesamaan karena spesifikasi tugas yang diberikan pun tidak mempunyai banyak macam solusi yang berbeda dalam hal struktural. Beberapa sistem yang berkonsentrasi agar tidak tertipu oleh modifikasi struktur yang rumit, kemungkinan besar akan menganggap seluruh submisi kelas pemrograman dasar sebagai hasil plagiarisme. Karena itu, Deimos lebih diutamakan untuk menangani modifikasi-modifikasi struktural yang sederhana. Topik yang dipelajari pada kelas pemrograman akan terus mengalami peningkatan kerumitan, sehingga setiap tugas pemrograman pun akan mempunyai tingkat kerumitan yang berbeda-beda. Untuk menyesuaikan spesifikasi deteksi dengan tingkat kerumitan program yang berbeda tersebut, pengajar dapat menentukan sensitivitas deteksi plagiarisme akan dilakukan. Pada Tugas Akhir ini, Deimos dirancang agar dapat melakukan deteksi plagiarisme pada source code dalam bahasa pemrograman Pascal dan LISP. Bahasa pemrograman Pascal dan LISP dipilih karena merupakan bahasa pemrograman dasar yang banyak
dipakai di kelas pemrograman bagi pemula. 3.2.3 Analisis Algoritma Running Karp-Rabin Greedy String Tiling Seperti yang telah dibahas pada Subbab 3.2.1, algoritma Running Karp-Rabin Greedy String Tiling (RKR-GST) dipilih karena algoritma tersebut dapat menangani kelemahan-kelemahan algoritma pembandingan lainnya terutama dalam aspek perubahan urutan kumpulan substring dan pengutamaan substring yang lebih panjang. Pada Subbab ini, akan dibahas dua isu utama penggunaan algoritma RKR-GST, yaitu pemilihan parameter minimum-match-length dan kelemahan algoritma RKR-GST.
III-6 Semakin kecil nilai minimum-match-length, maka sensitivitas deteksi semakin tinggi. Jika terdapat segmen-segmen source code yang sama pada dua buah blok program, maka sensitivitas yang tinggi akan memungkinkan seluruh segmen yang sama tersebut diduga sebagai hasil praktek plagiarisme. Jika sensitivitas deteksi rendah, maka segmen-segmen sama yang ukurannya pendek tidak dianggap sebagai praktek plagiarisme, melainkan dianggap sebagai kesamaan yang tidak disengaja. Jika sensitivitas minimal, maka pasangan program yang dianggap sebagai praktek plagiarisme hanyalah pasangan yang
memiliki source code yang sama secara
keseluruhan. Semakin panjang ukuran segmen yang sama antara dua buah source code, maka semakin besar dugaan bahwa segmen tersebut merupakan hasil plagiarisme. Misalnya deteksi plagiarisme dengan minimum-match-length 3 dilakukan terhadap dua buah token string P dan T seperti pada Gambar III-2. Walaupun terdapat dua segmen yang sama, hanya deretan token yang lebih panjang dari minimum-matchlength yang diduga sebagai hasil plagiarisme. Hanya segmen yang terdiri dari 3 token atau lebih saja yang akan diduga sebagai hasil plagiarisme. Segmen pertama hanya terdiri dari dua buah token sama yaitu BGP dan VAR yang tidak diduga sebagai plagiarisme sebab lebih kecil dari minimum-match-length yang bernilai 3. Segmen kedua diduga sebagai plagiarisme karena mengandung 7 token, yaitu ASG, BGW, ASG, WR, RD, ASG, EDW. 0 PRG
1 BGP
2 VAR
3 WR
4 RD
5 ASG
6 ASG
7 BGW
8 ASG
9 WR
10 RD
11 ASG
12 EDW
13 EDP
14
P T
BGP
VAR
VAR
ASG
BGW
ASG
WR
RD
ASG
EDW
BGW
ASG
EDW
WR
EDP
Gambar III-2. Pengaruh nilai minimum-match-length pada deteksi plagiarisme
Cara
menentukan
nilai
minimum-match-length
yang
tepat
adalah
dengan
mempertimbangkan banyaknya token pada token string yang dihasilkan proses parsing. Nilai minimum untuk minimum-match-length yaitu satu, sedangkan nilai maksimal adalah banyaknya token pada token string yang dihasilkan. Secara umum, satu token merepresentasikan satu buah statement atau kalimat pada source code berbahasa pemrograman Pascal. Sedangkan pada LISP, satu token merepresentasikan satu buah simbol atau kata.
III-7 Cara kerja algoritma RKR-GST secara detil dapat dilihat pada Subbab 2.2, sedangkan penjelasan lebih detil mengenai cara kerja algoritma menentukan dugaan plagiarisme berdasarkan parameter minimum-match-length (sensitivitas) dapat dilihat pada Lampiran A. Algoritma RKR-GST ini juga mempunyai kelemahan. Jika terdapat pertukaran statement atau ekspresi pada bagian yang merupakan hasil praktek plagiarisme, maka ada kemungkinan bagian tersebut tidak terdeteksi sebagai hasil plagiarisme. Contohnya jika terdapat bagian source code yang disalin oleh plagiator dengan modifikasi pada urutan statement seperti pada Kode III-1, maka ada kemungkinan bagian tersebut tidak terdeteksi sebagai hasil plagiarisme jika nilai minimum-matchlength cukup besar. Jika minimum-match-length bernilai 7, maka bagian tersebut tidak akan dianggap sebagai plagiarisme. Namun jika minimum-match-length bernilai 4, deretan statement yang terletak sebelum statement yang ditukar masih dianggap sebagai hasil praktek plagiarisme. Agar keseluruhan bagian dianggap sebagai hasil praktek plagiarisme, minimum-match-length harus bernilai 1. Inilah kelemahan utama algoritma RKRGST. Namun hal ini masih dapat ditoleransi karena pertukaran statement ini secara umum hanya menyebabkan perbedaan similaritas yang tidak besar [WIS96,LUT00]. i := 0; sum:=0;
i := 0; sum:=0;
while (i < 10) do
while (i < 10) do
begin
begin
sum := sum + i;
sum := sum + i;
write(sum);
i := i + 1;
i := i + 1;
write(sum);
end;
end;
Kode III-1. Modifikasi Urutan Statement yang Merupakan Salah Satu Usaha Plagiator Untuk Menyembunyikan Praktek Plagiarisme
Pada contoh yang diilustrasikan pada Kode III-1, modifikasi yang dilakukan tidak mempengaruhi output eksekusi program, karena perubahan nilai i tidak berpengaruh pada nilai sum yang ditampilkan ke layar. Modifikasi-modifikasi yang mempengaruhi output eksekusi program tidak dibahas pada Tugas Akhir ini karena detektor tidak mempunyai tanggung jawab untuk verifikasi hasil eksekusi program.
III-8 3.2.4 Spesifikasi Fungsional dan Non-fungsional Deimos Fungsi utama detektor plagiarisme otomatis Deimos yaitu mendeteksi kasus plagiarisme pada kumpulan source code program yang diberikan. Sesuai dengan penjelasan tentang metode structure-based pada Subbab 2.1.4.2, fungsi utama tersebut dapat dibagi menjadi dua buah subfungsi, yaitu fungsi mengubah source code menjadi token string dan fungsi membandingkan setiap pasangan token string. Deimos juga mempunyai fungsi menampilkan hasil deteksi dalam bentuk yang mudah dianalisis oleh pengajar. Analisis bentuk tampilan diuraikan dengan lebih rinci di Subbab 3.2.7.3. Spesifikasi fungsional Deimos dijelaskan secara lebih detil pada Tabel III-2. Deimos akan digunakan untuk mendeteksi plagiarisme pada kelas pemrograman yang
jumlah mahasiswanya mencapai ratusan. Oleh karena itu, Deimos harus mampu melakukan proses deteksi untuk banyak source code dalam waktu yang sesingkatsingkatnya. Selain itu, Deimos dirancang agar dapat digunakan oleh lebih dari satu pengajar, sehingga data hasil deteksi yang disimpan secara terpusat harus dapat diakses dari berbagai komputer.
Nomor SRS
Tabel III-2. Spesifikasi Fungsional Deimos Fungsi Keterangan
SRS-F-01
Mengubah source code menjadi token string.
SRS-F-02
Membandingkan setiap pasangan token string
SRS-F-03
Membuat tampilan hasil deteksi dalam bentuk yang mudah dianalisis (lihat Subbab 3.2.7.3) Menghapus data hasil deteksi.
SRS-F-04
Membaca kumpulan source code yang diberikan pengajar kemudian mengkonversi setiap source code menjadi token string yang merepresentasikan struktur program. Fungsi ini disebut juga sebagai tokenisasi. Membandingkan setiap token string yang dihasilkan oleh fase tokenisasi secara berpasangan. Kemudian setiap bagian token string yang mempunyai kesamaan dengan pasangannya akan ditandai, lalu nilai similaritas akan dihitung untuk setiap pasangan program dan disimpan ke penyimpanan data persisten. Menampilkan hasil deteksi dari data deteksi otomatis yang disimpan di penyimpanan data persisten dalam bentuk yang mudah dianalisis oleh pengajar. Hasil deteksi akan ditampilkan dalam format HTML. Menghapus data hasil deteksi batch tertentu dari penyimpanan data persisten jika tidak diperlukan lagi.
Pada Tugas Akhir ini, Deimos dibangun untuk mendeteksi plagiarisme source code dalam bahasa pemrograman Pascal dan LISP. Namun, Deimos harus dirancang agar tidak perlu membangun ulang keseluruhan detektor ketika menambahkan fasilitas deteksi bahasa pemrograman yang lain, sehingga waktu dan usaha yang dibutuhkan pun akan seminimal mungkin. Seperti detektor-detektor plagiarisme terdahulu yang
III-9 telah dibahas pada Subbab 3.2.1, hal ini bisa dicapai dengan mengenkapsulasi bagian yang bertanggung jawab atas fungsi tokenisasi dan bagian yang bertanggung jawab atas fungsi pembandingan. Dengan begitu untuk menambahkan bahasa baru, hanya bagian yang bertanggung jawab untuk mengubah source code menjadi token string saja yang perlu diubah atau dibangun ulang. Seperti telah dibahas pada Subbab 3.2.2, salah satu karakteristik kelas pemrograman adalah tipe soal pemrograman yang cukup sederhana namun mengalami peningkatan kesulitan seiring dengan waktu. Oleh karena itu, perlu ada penyesuaian sensitivitas deteksi dengan kerumitan source code agar tidak banyak kesalahan pada dugaan praktek plagiarisme yang dihasilkan. Berdasarkan analisis pada Subbab 3.2.1, algoritma yang akan dipakai untuk pembandingan pada Deimos yaitu algoritma Running Karp-Rabin Greedy String Tiling. Algoritma tersebut memiliki parameter yang
disebut
minimum-match-length
(lihat
Subbab
2.2),
yang
dapat
merepresentasikan sensitivitas deteksi. Nilai minimum-match-length tersebut akan menjadi input program, sehingga pengajar dapat menyesuaikan sensitivitas deteksi dengan kerumitan soal pemrograman yang diberikan. Penjelasan detil mengenai pemilihan parameter ini dapat dilihat pada Subbab 3.2.3. Penjelasan untuk seluruh spesifikasi non-fungsional Deimos dapat dilihat pada Tabel III-3.
Nomor SRS SRS-NF-01 SRS-NF-02
SRS-NF-03 SRS-NF-04
Tabel III-3. Spesifikasi Non-fungsional Deimos Spesifikasi non-fungsional Pengajar dapat mengakses aplikasi detektor dan data hasil deteksinya dari berbagai komputer. Proses deteksi yang efisien. Detektor harus dapat menangani jumlah source code yang mencapai ratusan dalam waktu yang dapat ditoleransi, yaitu tidak lebih dari setengah hari kerja untuk kelas berisi seratus mahasiswa. Detektor dapat dikembangkan lebih lanjut agar dapat menangani bahasa pemrograman lain tanpa mengembangkan ulang seluruh detektor. Pengajar dapat menentukan sensitivitas deteksi sehingga dapat disesuaikan dengan tingkat kerumitan topik pemrograman.
3.2.5 Use Case Deimos Berdasarkan spesifikasi fungsional pada Subbab 3.2.3, dibuat diagram Use Case untuk detektor plagiarisme otomatis Deimos. Use case untuk Deimos dapat dilihat pada Gambar III-3, sedangkan penjelasan setiap use case dapat dilihat pada Tabel III-4.
III-10
Mendeteksi plagiarisme
Pengajar Melihat tampilan hasil deteksi
Menghapus hasil deteksi
Gambar III-3. Diagram Use Case Deimos
Pemetaan antara spesifikasi fungsional pada Tabel III-2 dan use case dapat dilihat pada Tabel III-5. Use case deteksi plagiarisme merupakan pemetaan dari spesifikasi fungsional mengubah source code menjadi token string dan membandingkan setiap pasangan token string. Tabel III-4. Definisi Use Case Deimos Nomor Use Case
Use Case
UC-M-01
Mendeteksi plagiarisme.
UC-M-02
Melihat tampilan hasil deteksi.
UC-M-03
Menghapus hasil deteksi.
Deskripsi Mendeteksi plagiarisme otomatis pada kumpulan source code menggunakan metode berbasis struktur. Deteksi dimulai dengan mengubah source code menjadi token string, dilanjutkan dengan membandingkan setiap pasangan token string sambil menyimpan hasil deteksi ke penyimpanan data persisten. Setelah deteksi selesai, notifikasi dikirimkan ke pengajar melalui email jika dikehendaki. Membuat tampilan dalam format HTML dari data hasil deteksi yang disimpan di penyimpanan data persisten. Menghapus hasil deteksi tertentu dari penyimpanan data persisten, sehingga data yang tidak diperlukan lagi dapat dibuang.
Tabel III-5. Keterhubungan Spesifikasi Fungsional dengan Use Case Deimos Nomor SRS Nomor Use Case SRS-F-01 SRS-F-02 SRS-F-03 SRS-F-04
UC-M-01 UC-M-01 UC-M-02 UC-M-03
III-11 3.2.6 Skenario Penggunaan Deimos Pada subbab ini diuraikan mengenai skenario penggunaan Deimos untuk mendeteksi plagiarisme, melihat hasil deteksi dan menghapus hasil deteksi. Skenario yang dijelaskan di subbab ini hanya skenario normal. Skenario use case detil dapat dilihat pada Lampiran B. Skenario penggunaan Deimos untuk mendeteksi plagiarisme otomatis pada source code bisa dilihat pada Gambar III-4. Berikut ini merupakan penjelasan skenario tersebut: 1. Pengajar memberikan alamat direktori tempat disimpannya kumpulan source code program yang akan dideteksi dan men-trigger detektor melalui web browser untuk melakukan deteksi plagiarisme otomatis pada kumpulan source code tersebut. 2. Web browser mengirimkan request pada detektor plagiarisme. 3. Deimos mendeteksi plagiarisme pada source code yang terdapat dalam direktori yang dispesifikasikan pengajar dan menyimpan hasil deteksi ke penyimpanan data persisten. Setelah deteksi selesai, Deimos akan mengirimkan email notifikasi ke alamat email yang tersimpan di penyimpanan data persisten. 4. Deimos mengirimkan status bahwa deteksi selesai sebagai response ke web browser. 5. Web browser menampilkan status bahwa deteksi sudah selesai. Komputer user
1
2
Trigger
Web Browser
5 Pengajar
Komputer yang terinstalasi Deimos
Hasil deteksi
Deimos HTTP
3 4 source code
Gambar III-4. Skenario Penggunaan Deimos Untuk Mendeteksi Plagiarisme Secara Otomatis
Skenario yang diuraikan di atas merupakan skenario normal untuk mendeteksi plagiarisme. Jika ada masalah dengan koneksi jaringan setelah web browser mengirimkan request kepada Deimos untuk melakukan deteksi, maka proses deteksi akan tetap dieksekusi pada komputer yang terinstalasi Deimos walaupun tidak ada status yang dikirimkan sebagai response kepada web browser. Namun proses deteksi
III-12 bisa gagal jika gangguan terdapat pada komputer tempat terinstalasinya Deimos. Oleh karena itu disarankan untuk mengulangi proses deteksi sampai hasil deteksi yang lengkap didapatkan. Skenario penggunaan Deimos untuk melihat hasil deteksi bisa dilihat pada Gambar III-5. Berikut ini merupakan penjelasan detil skenario tersebut: 1. Pengajar meminta detektor untuk menampilkan hasil deteksi melalui web browser. 2. Web browser mengirimkan request pada detektor plagiarisme. 3. Deimos mengambil data yang sesuai dengan permintaan pengajar dari penyimpanan data persisten. 4. Deimos membentuk tampilan hasil deteksi berdasarkan data yang telah diambil. 5. Deimos mengirimkan tampilan hasil deteksi dalam format HTML sebagai response kepada web browser. 6. Web browser menampilkan tampilan hasil deteksi yang diterima.
Gambar III-5. Skenario Penggunaan Deimos Untuk Melihat Hasil Deteksi Plagiarisme
Skenario penggunaan Deimos untuk menghapus hasil deteksi tertentu bisa dilihat pada Gambar III-6. Berikut ini merupakan penjelasan detil skenario tersebut: 1. Pengajar meminta detektor untuk menampilkan daftar hasil deteksi melalui web browser. 2. Web browser mengirimkan request pada detektor plagiarisme. 3. Deimos mengambil daftar hasil deteksi dari penyimpanan data persisten. 4. Deimos mengirimkan daftar hasil deteksi sebagai response kepada web browser. 5. Web browser menampilkan daftar hasil deteksi yang diterima. 6. Pengajar memilih hasil deteksi yang ingin dihapus. 7. Web browser mengirimkan request pada detektor plagiarisme. 8. Deimos menghapus hasil deteksi yang telah dipilih pengajar dari penyimpanan data persisten.
III-13 9. Deimos mengirimkan status bahwa hasil deteksi sudah dihapus sebagai response kepada web browser. 10. Web browser menampilkan status bahwa hasil deteksi telah dihapus. Komputer user
1
2 5
6 User
Komputer yang terinstalasi Deimos
Web Browser
HTTP
4
3 Deimos
8
7
10
9
Hasil deteksi
Gambar III-6. Skenario Penggunaan Deimos Untuk Menghapus Hasil Deteksi Tertentu
Skenario yang diuraikan di atas merupakan skenario normal untuk menghapus hasil deteksi. Jika ada masalah dengan koneksi jaringan sehingga hanya sebagian hasil deteksi yang terhapus, sebaiknya operasi penghapusan diulang kembali. 3.2.7 Rancangan Global Deimos Terdapat dua aplikasi yang menjadi komponen detektor plagiarisme Deimos (lihat Gambar III-7). Aplikasi pertama adalah aplikasi web yang dapat diakses melalui perantaraan web browser. Aplikasi kedua adalah aplikasi backend yang berupa aplikasi desktop yang akan diimplementasikan dalam bahasa pemrograman Java. Aplikasi web akan diimplementasikan dalam PHP. Sesuai dengan spesifikasi nonfungsional yang telah dijelaskan pada Subbab 3.2.3, pengajar harus dapat men-trigger deteksi dan mengakses data hasil deteksi dari berbagai komputer. Oleh karena itu, digunakan aplikasi web untuk memenuhi fungsi trigger deteksi plagiarisme pada direktori yang dispesifikasikan dan menampilkan hasil deteksi. Aplikasi backend merupakan aplikasi yang melakukan proses deteksi plagiarisme otomatis pada kumpulan source code program yang diberikan. Tanggung jawab untuk melakukan deteksi tidak dilimpahkan pada suatu aplikasi web untuk mencegah kemungkinan terjadinya time out. Eksekusi aplikasi backend tersebut akan di-trigger oleh aplikasi web setelah pengajar memilih direktori source code yang akan dideteksi.
III-14 Ikhtisar tanggung jawab aplikasi web dan aplikasi backend beserta input yang dibutuhkan dan hasil proses eksekusinya dapat dilihat pada Tabel III-6. Tabel III-6. Tanggung Jawab Komponen Deimos beserta Input yang Dibutuhkan dan Hasilnya Komponen
Tanggung jawab
Input yang dibutuhkan
Hasil proses eksekusi
Deteksi plagiarisme
- Direktori kumpulan source code yang akan dideteksi. - Bahasa pemrograman pada source code target deteksi. - Nilai sensitivitas deteksi. Alamat email tujuan.
Hasil deteksi pada penyimpanan data persisten
Deimos
Aplikasi backend
Aplikasi web
Mengirimkan notifikasi ketika deteksi selesai. Trigger aplikasi backend.
Menghapus hasil deteksi. Menampilkan hasil deteksi pada halaman HTML. (penjelasan detil pada Subbab 3.2.7.3)
- Nama direktori kumpulan source code yang akan dideteksi. - Path direktori tempat aplikasi backend. Nama direktori kumpulan source code yang akan dideteksi Hasil deteksi pada penyimpanan data persisten.
Email notifikasi terkirim ke alamat email tujuan. Aplikasi backend tereksekusi.
Hasil deteksi dihapus dari penyimpanan data persisten. Tampilan pada halaman HTML berupa informasi umum deteksi, tabel distribusi similaritas, matriks similaritas, dan halaman pasangan program
Rancangan global Deimos dapat dilihat pada Gambar III-7. Terdapat dua buah subsistem pada aplikasi backend Deimos yaitu tokenizer dan comparator.
Gambar III-7. Rancangan Global Deimos
Tokenizer dipisahkan dari subsistem comparator karena tokenizer merupakan satusatunya komponen yang tergantung kepada bahasa pemrograman source code target
III-15 deteksi. Jika aplikasi ingin dibuat agar dapat menangani bahasa pemrograman lainnya, maka hanya tokenizer saja yang perlu diganti. Tanggung jawab setiap subsistem beserta input yang dibutuhkan dan hasil prosesnya dapat dilihat pada Tabel III-7. Tabel III-7. Tanggung Jawab Setiap Subsistem pada Aplikasi Backend Deimos beserta Input yang Dibutuhkan dan Hasilnya Nama Tanggung jawab subsistem Input yang Hasil proses subsistem dibutuhkan eksekusi Tokenizer - Membaca source code pada - Direktori kumpulan Sebuah token string direktori masukan. source code yang akan untuk setiap source - Untuk setiap source code, dideteksi. code. dilakukan scanning atau parsing - Bahasa pemrograman terhadap source code sambil pada source code target menyimpan token yang mewakili deteksi bagian-bagian dari source code. - Token set. Comparator - Membandingkan setiap pasang - Kumpulan token - Nilai similaritas token string. string yang dihasilkan untuk setiap - Pada setiap pembandingan, nilai komponen tokenizer. pasangan source similaritas pasangan dihitung dan - Nilai sensitivitas code. disimpan ke penyimpanan data deteksi. - Bagian-bagian persisten. Bagian-bagian source source code yang code yang diduga merupakan hasil diduga merupakan praktek plagiarisme diasosiasikan hasil praktek dengan warna yang berbeda dan plagiarisme beserta posisinya disimpan ke penanda warna penyimpanan data persisten untuk yang berbeda untuk keperluan pembuatan tampilan setiap bagian. HTML pada aplikasi web.
Berdasarkan penjelasan pada Subbab 2.3, salah satu masalah sistem-sistem deteksi plagiarisme terdahulu adalah ketergantungan pada sistem operasi. Oleh karena itu Deimos diimplementasikan menggunakan bahasa pemrograman Java dan PHP agar Deimos dapat diinstalasi pada berbagai komputer dengan sistem operasi berbeda.
Detil subsistem tokenizer dan comparator akan dijelaskan pada Subbab 3.2.7.1 dan Subbab 3.2.7.2, sementara detil aplikasi web akan dibahas pada Subbab 3.2.7.3. 3.2.7.1 Tokenizer Subsistem tokenizer mempunyai tanggung jawab utama untuk mengubah source code program menjadi token string. Untuk itu diperlukan analisis statik terhadap source code yang dapat dilakukan dengan mengimplementasikan scanner dan/atau parser sesuai dengan bahasa pemrograman target deteksi. Proses parsing dilakukan sambil memanfaatkan token set yang terdefinisi di dalam penyimpanan data persisten. Token set adalah kumpulan token yang mewakili setiap elemen bahasa pemrograman. Tokenizer akan mencari token pada token set yang menjadi padanan elemen source
III-16 code kemudian mengkonversi elemen source code tersebut menjadi token dan menambahkannya ke akhir token string. Salah satu aspek yang menjadi isu perancangan parser tersebut adalah adanya perbedaan
paradigma
bahasa
pemrograman.
Untuk
bahasa
pemrograman
berparadigma prosedural atau berorientasi objek, biasanya dilakukan proses parsing sebagai bagian dari kompilasi ketika executable dibuat. Namun untuk bahasa pemrograman berparadigma fungsional, biasanya yang diterapkan adalah evaluasi ekspresi pada interpreter. Untuk keperluan deteksi plagiarisme pada Deimos, untuk bahasa pemrograman dengan paradigma apapun akan dibangun parser berdasarkan grammar yang sudah disusun terlebih dahulu. Untuk membuktikan hal itu, pada Tugas Akhir ini akan dibangun parser untuk bahasa pemrograman Pascal dan LISP. Perancangan scanner dan parser untuk bahasa Pascal dan LISP beserta grammar dan token set untuk masing-masing bahasa dapat dilihat pada Lampiran C. Dalam perancangan token set, setiap token harus dipilih sedemikian rupa agar merepresentasikan karakteristik inti program yang sulit diubah oleh plagiator, contohnya reserved words. Elemen-elemen program seperti whitespace dan komentar tidak boleh menjadi bagian dari token string karena merupakan bagian-bagian yang paling mudah dijadikan sasaran modifikasi. Selain itu, mengingat deretan token yang dihasilkan dari proses tokenisasi akan dihitung nilai hash-nya untuk dibandingkan pada algoritma Running Karp-Rabin Greedy String Tiling, token-token pada detektor plagiarisme otomatis Deimos berupa integer agar nilai hash lebih cepat dihitung. Jika token berupa string, akan dihasilkan kompleksitas algoritma yang lebih tinggi karena nilai hash harus dihitung untuk setiap token tunggal sebelum menghitung nilai hash untuk deretan token. Subsistem ini tergantung kepada bahasa pemrograman source code yang akan dideteksi.
Agar
detektor
plagiarisme
otomatis
mampu
menangani
bahasa
pemrograman lainnya, perlu ditambahkan tokenizer baru yang sesuai dengan bahasa pemrograman target. Pada Tugas Akhir ini, hanya tokenizer untuk target bahasa pemrograman Pascal dan LISP yang akan dikembangkan.
III-17 3.2.7.2 Comparator Subsistem ini mempunyai tanggung jawab melakukan pembandingan sekaligus menghitung similaritas untuk setiap pasangan source code. Subsistem akan memanfaatkan token string yang dihasilkan oleh subsistem tokenizer. Nilai similaritas dan penanda bagian-bagian program yang mempunyai kesamaan dengan program pasangannya akan disimpan ke penyimpanan data persisten. Algoritma yang dipilih yaitu algoritma Running Karp-Rabin Greedy String Tiling (lihat Subbab 2.2.3). Algoritma tersebut memang dirancang untuk menemukan bagian-bagian yang sama pada dua buah string. Tujuan itu sesuai dengan tujuan deteksi plagiarisme otomatis pada source code, yaitu menemukan segmen-segmen yang sama pada pasangan source code. Walaupun pada string diselipkan substring tambahan untuk menyembunyikan plagiarisme, RKR-GST dapat tetap menemukan padanan bagian source code yang sama. Selain itu, algoritma RKR-GST tidak terpengaruh oleh perbedaan urutan bagian-bagian source code. Berdasarkan studi yang diuraikan pada Subbab 2.2.3 dan analisis pada Subbab 3.2.3, algoritma ini efektif dalam menemukan praktek plagiarisme dan juga mempunyai kompleksitas algoritma yang hampir linier. Namun, efektivitas algoritma ini juga tergantung pada token set dan nilai minimum-match-length yang dipilih. Nilai minimum-match-length menyatakan tingkat sensitivitas (semakin kecil nilai minimummatch-length, deteksi semakin sensitif), maka dari itu penggunalah yang akan menentukan tingkat sensitivitas deteksi tersebut, karena harus disesuaikan dengan tingkat kerumitan source code pemrograman. Formula yang dipakai untuk menghitung similaritas harus mempertimbangkan faktor panjang source code dan jumlah token yang ditandai pada algoritma RKR-GST [WIS96]. Formula perhitungan similaritas pasangan source code yang akan dipakai di Deimos yaitu sebagai berikut : Similarity = length_of_tokens_tiled/length_of_shorter_program*100%
Keterangan : a. Similarity merupakan persentase similaritas pasangan program.
III-18 b. length_of_tokens_tiled merupakan jumlah token yang sama pada kedua program yang dibandingkan. Nilai ini didapatkan dari algoritma Running KarpRabin Greedy String Tiling. c. length_of_shorter_program merupakan jumlah token pada program yang lebih pendek. 3.2.7.3 Aplikasi web Subsistem ini mempunyai tanggung jawab mengambil data hasil deteksi dan menampilkannya dalam format HTML. Melalui aplikasi web, pengajar juga dapat mengeksekusi deteksi plagiarisme dan juga menghapus hasil deteksi yang sudah tidak diperlukan. Tampilan hasil deteksi harus mudah dibaca oleh pengajar, karena hasil deteksi yang dilakukan sistem otomatis tidak bisa dijadikan keputusan final apakah suatu source code merupakan hasil plagiarisme atau tidak. Masih dibutuhkan pertimbangan dari manusia setelah deteksi otomatis menghasilkan nilai similaritas setiap pasangan source code. Oleh karena itu, harus ada tampilan yang sebaik mungkin yang mempermudah pengajar ketika melakukan drill-down data hasil deteksi. Pada halaman utama (lihat Gambar III-8), terdapat data statistik umum proses deteksi, tabel distribusi nilai similaritas, dan matriks similaritas. Pada tabel distribusi similaritas pengajar dapat melihat jumlah pasangan program yang mempunyai nilai similaritas pada range tertentu. Diharapkan tabel tersebut dapat memberikan gambaran umum mengenai tingkat plagiarisme yang terjadi. Untuk memperlihatkan kesamaan setiap pasangan program, pada halaman utama juga ditampilkan nilai similaritas setiap pasangan program dalam bentuk matriks similaritas. Jika nilai similaritas salah satu pasangan program di-klik, maka akan ditampilkan halaman baru yang memperlihatkan bagian-bagian yang sama dari pasangan program yang dipilih (lihat Gambar III-9).
III-19
Gambar III-8. Contoh Rancangan Tampilan Halaman Utama Hasil Deteksi pada Deimos
Pada halaman yang memperlihatkan pasangan program, bagian-bagian yang diduga merupakan hasil plagiarisme akan ditandai dengan warna yang berbeda, sehingga pengajar dapat dengan mudah mengetahui segmen-segmen source code yang diduga hasil plagiarisme beserta padanannya pada pasangan source code. Bagian source code yang tidak diduga sebagai hasil plagiarisme akan berwarna hitam, sementara bagian yang merupakan dugaan hasil praktek plagiarisme akan ditandai dengan warna lain. Warna tersebut sudah ditentukan oleh comparator ketika melakukan pembandingan, sehingga aplikasi web hanya perlu menampilkan source code sesuai warna yang sudah
III-20 ditentukan. Pasangan yang ditandai dengan warna hitam tidak diperhitungkan pada pembuatan tabel distribusi similaritas.
Gambar III-9. Contoh Rancangan Tampilan Halaman Perbandingan Pasangan Source Code pada Deimos
Aplikasi web akan diimplementasi dengan PHP sehingga setelah deteksi selesai detektor tidak perlu langsung men-generate halaman HTML sejumlah pasangan program seperti sistem-sistem deteksi plagiarisme terdahulu, melainkan tampilan akan di-generate ketika pengajar membutuhkannya. Melalui tampilan hasil deteksi yang telah dijelaskan di atas, diharapkan detektor akan dapat mendukung pengajar dalam memutuskan kasus-kasus plagiarisme yang terjadi. 3.2.8 Penanganan Modifikasi-modifikasi Source Code yang Menyembunyikan Praktek Plagiarisme Berdasarkan studi pada Subbab 2.1.2 dan analisis karakteristik kelas pemrograman pada Subbab 3.2.2, plagiarisme yang dilakukan oleh mahasiswa kelas pemrograman mempunyai karakteristik khusus yaitu adanya modifikasi-modifikasi yang tidak mempengaruhi eksekusi program. Agar detektor tidak tertipu oleh modifikasimodifikasi tersebut, perlu ada penanganan khusus yang tergantung pada implementasi tokenizer dan algoritma pembandingan yang dipilih. Detil modifikasi-modifikasi yang umum dilakukan oleh mahasiswa pemrograman di Teknik Informatika ITB dan penanganannya bisa dilihat pada Tabel III-8.
III-21 Tabel III-8. Penanganan Modifikasi-modifikasi yang Dilakukan Mahasiswa Kelas Pemrograman Jenis Modifikasi Komponen Cara penanganan penanggung jawab Menghilangkan atau menambah Scanner Mengabaikan seluruh komentar. komentar. (analisis leksikal) Mengubah indentasi dan Scanner Mengabaikan seluruh whitespace. estetika penulisan program. (analisis leksikal) Mengubah nama identifier. Scanner Mengabaikan nama identifier. (analisis leksikal) Beberapa tipe scalar dianggap sama, yaitu Mengubah tipe variabel dengan Parser (analisis sintaks) integer, real, character, string, dan tipe lain yang dapat sebagainya. Penjelasan detil dapat dilihat menggantikannya, misalnya pada Lampiran C. integer dengan real. Parser Mengabaikan statement print atau write Menyelipkan statement, (analisis sintaks) yang hanya menampilkan string, dan terutama statement yang menyimpan informasi statement yang fungsinya menampilkan tulisan menampilkan suatu nilai saja. ke layar. Mengubah jenis ekspresi Parser Semua ekspresi kondisional dianggap (analisis sintaks) sebagai bagian dari statement. Jenis kondisional, misalnya a > 1 ekspresi maupun informasi operator dan dengan 2 <= a. operand diabaikan. Menyalin sebagian source code Algoritma Running Algoritma ini mampu menemukan bagiansaja (plagiarisme segmen). Karp-Rabin Greedy bagian yang sama tanpa terpengaruh posisi String Tiling atau panjang bagian yang sama tersebut. Mengubah urutan deklarasi Algoritma Running Algoritma ini mampu menemukan bagianfungsi, mengubah urutan Karp-Rabin Greedy bagian yang sama tanpa terpengaruh posisi statement. String Tiling dan urutan bagian-bagian yang sama tersebut.
