Bab II Dasar Teori Pada Bab ini, akan dibahas hasil studi literatur maupun eksplorasi yang akan dipakai pada Tugas Akhir ini. Studi literatur ini mencakup penjelasan mengenai kontes-kontes pemrograman, desain dan aspek security yang harus dimiliki sebuah sistem kontes pemrograman. Karena sistem ini akan dibangun secara terdistribusi untuk meningkatkan skalabilitas maka di bab ini juga akan dijelaskan mengenai dasar teori load sharing pada sebuah sistem terdistribusi. 2.1. Kontes Pemrograman Pada bagian ini akan dibahas mengenai kontes pemrograman yang merupakan latar belakang dari pembangunan sistem pelatihan kompetisi pemrograman ini. 2.1.1. Ikhtisar Kontes Pemrograman Kontes pemrograman secara umum memiliki banyak peran. Kontes pemrograman sebagai sebuah olahraga, memberikan hiburan kepada penonton dan juga peserta. Kontes juga bertujuan sebagai wadah untuk berprestasi. Kontes memotivasi peserta untuk memasuki sebuah disiplin ilmu, mempelajari, dan berlatih berbagai kemampuan dan keterampilan. Kontes juga berperan sebagai model bagi kompetisi yang serupa dan memajukan kontes-kontes yang lain serta kurikulum informatika. Dengan adanya kontes, dapat terbangun sebuah komunitas yang terdiri atas pelajar, pelatih, dan pendukung lainnya [COR06]. Adanya kontes membuat pengajaran berbagai bidang menjadi lebih atraktif. Saat pelajar mempelajari sebuah konsep dasar dari ilmu komputer, mereka segera dapat menemukan tempat di mana mereka dapat mendemonstrasikan kemampuan mereka, karya mereka, membagikan pemikiran mereka, dan membandingkan diri mereka dengan orang lain [DAG06].
II-1
II-2
2.1.2. Kontes-Kontes Pemrograman Pada subbab-subbab berikut akan dibahas mengenai 2 buah kontes pemrograman yang paling popular di dunia sekarang ini yakni IOI yang menjadi model utama materi kompetisi pemrograman yang digunakan serta ACM ICPC. 2.1.2.1. ACM Intercollegiate Programming Contest ACM ICPC [ACM09] adalah sebuah kontes pemrograman yang ditujukan bagi mahasiswa. Pada kontes ini, sebuah tim yang terdiri dari 3 orang berbagi sebuah komputer dan diminta untuk mengerjakan beberapa soal dalam waktu 5 jam. Setiap soal terdiri atas deskripsi permasalahan, format masukan, format keluaran, dan juga sebuah contoh sederhana antara masukan dan keluaran yang diminta. Tim dapat mengerjakan setiap persoalan tanpa urutan tertentu dan menghasilkan sebuah potongan program yang ditulis dalam bahasa pemrograman seperti Pascal, C. C++, dan Java. Program tersebut harus dapat menangani semua masukan yang valid. Kode program yang dihasilkan oleh tim, dikumpulkan secara online ke judge yang kemudian melakukan pengujian terhadap semua test case. Jika program tersebut berjalan pada waktu dan memori yang ditentukan serta menghasilkan keluaran yang benar maka program diterima, sebaliknya ditolak. Tidak ada penilaian untuk test case yang benar (partial). Setiap tim dapat mengumpulkan kembali jawaban kembali jika jawaban sebelumnya salah. Ketika sebuah program diterima maka tim akan mendapat penalti, 1 poin untuk setiap menit berjalan sejak kontes dimulai dan 20 poin untuk setiap jawaban yang salah yang sudah dikumpulkan. Peringkat peserta ditentukan dari jumlah soal yang berhasil dikerjakan dengan jumlah penalti sebagai tie-breaker. Selama kontes berjalan, terdapat sebuah papan skor yang menampilkan jumlah soal yang diselesaikan dan penalti untuk setiap tim. Kontestan dan penonton (untuk kontes onsite dan online) dapat melihat papan skor. Meski demikian papan skor tidak diupdate selama satu jam terakhir untuk menimbulkan rasa tegang bagi peserta sebelum pengumuman dilaksanakan. Pada setiap komputer peserta akan
II-3
dipasang balon-balon berwarna warni untuk setiap soal yang telah diselesaikan oleh peserta. 2.1.2.2. International Olympiad of Informatics International Olympiad of Informatics atau IOI [IOI05] adalah sebuah kompetisi tahunan di bidang ilmu komputer. IOI pertama kali didirikan pada tahun 1989 dan meniru model International Mathematical Olympiad. IOI ditujukan bagi peserta dari sekolah menengah terutama yang memiliki bakat di bidang ilmu komputer. Tujuan dari IOI adalah untuk mempopulerkan disiplin ilmu komputer kepada pelajar sekolah. Setiap delegasi sebuah negara terdiri dari 4 orang peserta. Setiap peserta berkompetisi dalam dua buah sesi 5 jam yang dipisahkan pada hari yang berbeda. Pada setiap sesi peserta diminta untuk menyelesaikan 3 buah soal yang mempunyai spesifikasi mirip dengan ACM ICPC. Soal ini telah diterjemahkan ke dalam bahasa asal peserta. Solusi harus ditulis dalam bahasa Pascal, C, dan C++ dan dikumpulkan secara online. Meski demikian peserta tidak dapat melihat nilai dari hasil pekerjaannya. Peserta dapat mengumpulkan jawaban berkali-kali. Nilai akan diumumkan secara tertulis kepada peserta satu persatu di hari setelah sesi dilaksanakan. Test case juga diberikan supaya peserta dapat melihat letak kesalahannya ataupun juga melakukan protes kepada panitia jika peserta yakin bahwa test case tersebut salah. Berbeda dengan ACM ICPC, IOI memberikan nilai kepada jawaban untuk setiap test case yang berhasil dikerjakan oleh program peserta (partial scoring). Batas waktu runtime program biasanya sangat ketat sehingga hanya algoritma yang terbaik yang dapat menyelesaikan semua test case. Selain dari tipe soal yang mirip ACM ICPC tersebut, terdapat 2 jenis soal yang lain yakni output only dan interactive. Pada tipe soal output only atau yang lebih dikenal dengan open-data test, peserta telah diberikan sekumpulan test case masukan. Dengan test case tersebut peserta diminta untuk menghasilkan data keluaran yang diharapkan. Pada tipe interactive task, peserta diminta membuat
II-4
sebuah program yang nantinya akan berinteraksi dengan program yang dimiliki oleh panitia. Tujuan dari interactive task ini biasanya adalah untuk mensimulasikan sebuah permainan di mana program peserta akan mengeluarkan langkah untuk menjawab langkah yang diberikan oleh program yang diberikan untuk memaksimalkan keuntungan pada permainan. Pada IOI 2008, implementasi interaksi ini dilakukan dengan format library. Peserta diminta untuk mengumpulkan jawaban dalam bentuk library. Sebelum 2008, implementasinya dilakukan dengan menggunakan standard input dan output. 2.2.
Sistem Manajemen Kontes Pemrograman
Untuk melaksanakan kontes-kontes pemrograman seperti yang dibahas pada Subbab sebelumnya, diperlukan adanya sistem yang membantu penyelenggara kontes. Sistem ini biasanya menyediakan fungsionalitas untuk melakukan penilaian jawaban peserta secara otomatis di samping fungsionalitas seperti manajemen kontestan, administrasi, dan lain-lain. 2.2.1. Desain Sistem Manajemen Kontes Pemrograman Fungsionalitas utama yang disediakan oleh sebuah sistem kontes pemrograman adalah automated judge. Perangkat ini bertugas untuk melakukan evaluasi jawaban kontestan secara otomatis. Proses evaluasi biasanya dilakukan dalam 3 tahap utama yakni melakukan kompilasi kode program jawaban, mengeksekusi program tersebut pada beberapa test case yang telah disediakan, dan terakhir memeriksa kebenaran keluaran program. Fungsionalitas lain yang penting dalam menyelenggarakan sebuah sistem kontes adalah manajemen user (termasuk autentikas dan pengaturan akses), administrasi (menambahkan/menyunting soal, test case, konfigurasi soal, dan melakukan rejudging jawaban peserta), dan sebuah portal kontes (menampilkan ranking, jawaban, klarifikasi, dan informasi lain) Beberapa kontes sistem yang ada sekarang ini memberikan fungsionalitas tambahan seperti melakukan backup data dan juga mencetak kode jawaban.
II-5
2.2.2. Kebutuhan Sistem Kontes Pemrograman Forizek menyebutkan bahwa terdapat beberapa kebutuhan yang harus dimiliki oleh sebuah sistem kontes [FOR06]. 1. Flexibility Setiap kontes pemrograman memiliki kebutuhan yang berbeda satu sama lain. Sebuah sistem kontes harus dapat dengan mudah diadopsi untuk peraturan kontes yang berbeda-beda. Untuk mencapai fleksibilitas yang baik, sebuah kontes harus didesain secara moduler. 2. Robustness Sistem kontes harus robust dan reliable. Sistem tidak boleh crash sewaktu-waktu ketika kontes sedang dijalankan. 3. User-friendliness and Support Sistem harus mudah digunakan dan memiliki dokumentasi yang baik. Kebanyakan sistem kontes hanya memiliki fungsionalitas minimal untuk dapat berjalan. Banyak sistem yang memiliki dokumentasi sangat minim sehingga hanya dapat digunakan oleh pengembang. 4. Trust Sistem harus dapat membatasi akses ke beberapa informasi, menjaga integritas hasil kontes, dan lain-lain. Pengembang sistem kontes harus dapat menjaga kepercayaan dari pemilik kontes. 2.2.3. Implementasi
Perangkat
Lunak
Manajemen
Kontes
Pemrograman Pada subbbab ini dibahas 3 buah sistem manajemen kontes pemrograman yang telah banyak digunakan: Mooshak, PC2, dan MO-Eval. 2.2.3.1.
Mooshak
Mooshak [MOO08] adalah sebuah sistem manajemen kontes pemrograman yang berbasis web. Fitur-fitur dasar Mooshak terdiri atas automatic judging untuk
II-6
jawaban peserta kontes, tanya jawab untuk soal, manajemen soal, dan lain-lain. Selain itu Mooshak juga menyediakan fitur-fitur administrasi yang cukup lengkap seperti melakukan replikasi dan backup data kontes, peserta, jawaban, dan juga soal. Mooshak juga mendukung berbagai jenis aturan kontes yang ada. Penyelenggara kontes diberikan banyak sekali pilihan-pilihan konfigurasi untuk kontes dan soal yang akan digunakan. Mooshak dikembangkan sebagai aplikasi open source untuk lingkungan dengan sistem operasi Linux menggunakan server Apache dan bahasa script TcL. Sistem ini mampu menangani source code dalam berbagai bahasa pemrograman, khususnya yang sering digunakan dalam kompetisi pemrograman: C, C++, Java dan Pascal. Bahasa pemrograman jamak ditangani dengan menggunakan kompilator-kompilator eksternal yang harus
didefinisikan terlebih dahulu oleh administrator sistem. Mooshak juga
sering digunakan pada pembinaan yang diadakan oleh TOKI. 2.2.3.2.
PC2
PC2 atau Programming Contest Control System [PCC09] dan sering diucapkan “P-C-square” adalah sebuah sistem yang dikembangkan untuk mendukung pelaksanaan sebuah lomba dalam berbagai lingkungan komputasi. Aplikasi ini mempunyai fasilitas pengumpulan jawaban berupa kode melalui jaringan komputer.
Juri
dapat
melakukan
kompilasi
ulang jawaban
tersebut,
mengeksekusinya, melihat isi jawaban, melihat hasil penilaian, dan mengirimkan respons kepada peserta atas jawaban yang sudah dikumpulkan. Sistem secara otomatis memberi penanda waktu dan menyimpan jawaban yang dikirim, menampilkan dan melakukan update kedudukan sementara dari para peserta dalam berbagai cara, dan memberikan fasilitas kepada juri untuk mengambil dan menilai ulang jawaban yang sudah pernah dikirim. Aplikasi ini juga memberikan fasilitas bagi peserta untuk meminta klarifikasi kepada para juri. Para juri juga dapat menuliskan pengumuman bagi semua peserta. Selain itu, PC2 juga mendukung pengadaan kontes yang diadakan secara simultan pada tempat yang berbeda-beda dan menampilkan sebuah papan kedudukan untuk setiap tempat.
II-7
Sistem ini juga memberikan banyak opsi-opsi yang dapat dipilih dan dikonfigurasi secara bebas oleh administrator untuk menyesuaikan sistem untuk peraturan kontes yang lebih spesifik. Opsi tersebut antara lain jumlah peserta, jumlah soal, bahasa pemrograman yang digunakan, metode penilaian, dan lain-lain. Aplikasi juga memberikan kemudahan untuk penyuntingan langsung ke dalam basisdata. Sistem ini dikembangkan di California State University. Sistem ini pertama kali dikembangkan dengan menggunakan Turbo Pascal. Akan tetapi versi terakhir dikembangkan menggunakan Java dengan antarmuka Java Swing. Sistem ini sering dipakai dalam kontes pemrograman ACM ICPC. PC2 didistribusikan dalam bentuk binary dan closed source. 2.2.3.3.
MO-Eval
MO-Eval [MAR07] yang memiliki nama asli MO Contest Environment adalah sebuah sistem manajemen kontes sederhana yang menerapkan aturan kontes pada IOI. Pada aturan ini, peserta kontes mengerjakan soal dan kemudian mengirimkan jawaban yang nantinya akan dinilai secara offline pada akhir kontes. Meski demikian MO-eval di masa depan akan dikembangkan lebih moduler sehingga dapat memfasilitasi konfigurasi-konfigurasi aturan kontes lain seperti ACMICPC. Tipe soal yang didukung oleh sistem ini antara lain offline task (batch), interactive, dan open-data task (output only). Oleh pengembangnya, MO-eval digunakan pada Czech Olympiad in Programming dan Czech-Polish-Slovak Preparation Camp. MO-eval dikembangkan oleh Martin Mares sejak tahun 2002. Sistem ini dikembangkan dengan bahasa C dan bahasa shell scripting Bash untuk mesin bersistem
operasi
Linux
dengan
arsitektur prosesor
i386.
Sistem
didistribusikan secara open source dibawah lisensi GPL2. Tabel II-1. Perbandingan Kontes Sistem Antarmuka Penggunaan Teknologi Tipe soal
Mooshak Web based Online CGI dan TcL Batch task IOI ACM style
&
PC2 Desktop based Onsite Java Batch task ACM
MO-Eval Command line Offline Bash dan C Custom defined task
ini
II-8
2.3. Sistem Pelatihan Pemrograman Online Selain dari sistem-sistem manajemen kontes yang digunakan secara langsung pada saat kontes berjalan, terdapat sistem-sistem pelatihan yang dapat digunakan oleh pelajar untuk melakukan latihan setiap saat. Dengan sistem ini pelajar dapat mengukur kemampuannya dengan hasil yang diberikan oleh sistem. Meski demikian umumnya sistem pelatihan menyediakan fungsi kontes di mana peserta selain dapat mengukur kemampuannya juga dapat membandingkannya dengan peserta lain. Pada subbab berikut penulis akan menjabarkan 2 buah sistem pelatihan online yang banyak digunakan di dunia. 2.3.1.
USACO Training
USACO (USA Computing Olympiad) Training [USA09] adalah sistem pelatihan berbasis Internet yang berupa kumpulan tulisan yang sifatnya instruksi dan berisi soal-soal pemrograman yang mendukung. Sistem ini dibuat untuk mendukung pelatihan di USACO sendiri meski sistem ini juga memperbolehkan peserta di luar Amerika Serikat untuk mengaksesnya dan melakukan latihan di sana. Pada sistem ini, peserta dihadapkan oleh beberapa bab latihan. Bab-bab tersebut disusun dari tingkat kesulitan terendah sampai tersulit. Untuk mengerjakan soalsoal pada bab tersebut, peserta diharuskan untuk membaca instruksi atau materi yang ada di awal bab. Setelah itu peserta dapat membuka soal-soal dan mengumpulkan jawaban. Untuk dapat mengakses sebuah bab, peserta harus menyelesaikan semua soal-soal yang ada di bab sebelumnya. Selain dari layanan pelatihan, USACO juga memberikan kesempatan bagi peserta untuk mengikuti kontes yang diadakan secara periodik. Setiap kontes dibagi ke dalam 3 tingkat kesulitan : bronze, silver, dan gold. Tingkat kesulitan soal termudah terdapat pada tingkat bronze hingga gold merupakan kontes dengan soal yang tersulit. Untuk dapat mengikuti kontes silver, peserta harus mempunyai rating yang cukup setelah mengikuti kontes bronze. Setelah itu peserta dapat naik ke kontes silver hingga kontes gold.
II-9
2.3.2.
Z-Trening
Z-Trening [ZTR09] adalah sebuah situs pelatihan pemrograman online. Situs ini dibuat oleh Alexandar Zlateski. Situs ini memiliki fitur yang sangat lengkap. Peserta dapat melihat melihat kumpulan-kumpulan soal yang disediakan pada situs. Soal-soal ini dikelompokkan berdasarkan kategori-kategori tertentu. Peserta dapat mengakses setiap soal yang ada kemudian mengumpulkan jawaban untuk soal tersebut. Proses penilaian yang dilakukan oleh sistem secara realtime. Peserta dapat melihat status jawabannya mulai dari pengumpulan, menunggu autograder, dan pengujian pada test case secara langsung. Selain itu peserta dapat melihat statistik pengumpulan jawaban yang sudah dilakukan. Pada statistik ini, sistem menampilkan trend pengumpulan jawaban, jumlah jawaban benar, jumlah soal yang dikerjakan, persentase jawaban benar, dan lain-lain. Untuk setiap soal yang ada, sistem menampilkan deskripsi soal, informasi soal, rating soal, rasio jawaban benar, jawaban-jawaban terakhir yang dikumpulkan oleh peserta, peserta-peserta yang menjawab benar, dan lain-lain. Situs juga menyediakan forum-forum diskusi untuk setiap soal sehingga peserta-peserta dapat berdiskusi mengenai soal tersebut. Sebagai tambahan, situs ini juga menyelenggarakan kontes-kontes yang diadakan secara online dan periodik. Peserta dapat mengikuti kontes-kontes yang diadakan tersebut. Sistem juga menampilkan kontes-kontes yang telah diikuti oleh seorang peserta dan medali yang didapatkannya. Selain itu sistem juga menampilkan kontes-kontes yang telah diadakan sebelumnya dan juga kontes yang akan datang dalam bentuk kalender. 2.4. Aspek Penting Pada Sistem Pelatihan dan Kontes Pemrograman Beberapa kebutuhan untuk sebuah sistem kontes pemrograman telah dijelaskan pada Subbab 2.2.2: flexibility, robustness, user-friendliness, dan trust. Di dalam Tugas Akhir ini penulis memfokuskan pada aspek yang menjadi rumusan masalah. Rumusan masalah ini merupakan bagian dari kebutuhan tersebut. Kebutuhan flexibility ingin dicapai pada aspek extensibility sehingga sistem dapat
II-10
beradaptasi dengan kebutuhan-kebutuhan dan perkembangan tipe-tipe soal baru. Selain itu aspek security dan scalability merupakan bagian dari kebutuhan robustness di mana sistem dapat terjaga sehingga tidak mudah crash 2.4.1. Extensibility Extensibility adalah kemudahan pengadaptasian produk perangkat lunak terhadap perubahan spesifikasi [MEY97]. Ada 2 hal yang penting di dalam meningkatkan extensibility 1. Design simplicity Arsitektur yang sederhana akan mudah diadaptasi daripada yang lebih rumit. 2. Decentralization Semakin otonom sebuah modul maka kemungkinan besar perubahan kecil hanya akan mempengaruhi satu atau sedikit modul daripada menimbulkan efek berantai yang mempengaruhi sistem secara keseluruhan. Di dalam pengembangan soal, aspek extensibility pada sistem dimaksudkan untuk memfasilitasi pengembangan soal sehingga sistem mampu menggunakan soalsoal yang telah dibuat atau akan dibuat meski terdapat perubahan-perubahan spesifikasi dalam sistem. 2.4.2. Security Karena sebuah sistem kontes umumnya menerima source code sebagai bentuk jawaban maka sistem ini menjadi sangat rentan untuk diserang. Forizek juga mendaftarkan beberapa serangan-serangan yang dapat terjadi pada sebuah sistem kontes. Serangan-serangan ini dapat diklasifikasikan menjadi 3 jenis berdasarkan waktu serangan: compilation-time, execution-time, dan contest-time. Serangan compilation-time dan execution-time terjadi pada saat proses penilaian jawaban peserta sementara serangan contest-time meliputi serangan-serangan lain. Selain berdasarkan waktu serangan, serangan juga dapat diklasifikasikan berdasarkan tujuan serangan: denial of service, privileges escalation, destructive attack, dan covert channel. Serangan denial of service bertujuan untuk membatasi beberapa pengguna dalam mengakses layanan sistem. Serangan priviliges
II-11
escalation bertujuan untuk mendapatkan akses ke area atau materi yang seharusnya tidak dapat diakses. Destructive attack bertujuan untuk merusak layanan sistem sehingga tidak dapat diakses oleh siapapun. Covert channel adalah situasi di mana penyerang menggunakan sebuah cara yang tidak diberikan oleh pengembang sistem untuk berkomunikasi dengan pengguna lain. 2.4.2.1. Forcing High Compilation Time Serangan ini termasuk ke dalam tipe compilation-time dan denial of service. Sebuah kode yang pendek dan sederhana dapat membutuhkan waktu kompilasi yang sangat lama. Jika sistem tidak membatasi waktu kompilasi maka hal ini akan digunakan untuk membatasi aktivitas compiler dan dapat berujung pada terhentinya proses automated judging. #include <map> using namespace std; typedef map
M1; typedef map<M1,M1> M2; typedef map<M2,M2> M3; typedef map<M3,M3> M4; typedef map<M4,M4> M5; typedef map<M5,M5> M6; typedef map<M6,M6> M7; typedef map<M7,M7> M8; int main() { M8 tmp; } Kode II-1. Forcing High Compilation Time
Untuk pencegahan, sistem perlu memberikan batasan waktu kompilasi. Selain itu, menggunakan lebih dari satu mesin akan mengurangi dampak dari serangan ini; jika sebuah mesin terhenti maka mesin yang lain masih dapat berjalan untuk melakukan automated judging. 2.4.2.2. Consuming Resource At Compilation Time Serangan ini termasuk ke dalam tipe compilation-time dan denial of service. Beberapa compiler melakukan lookahead dalam melakukan parsing kode
II-12
program (untuk memahami sebuah kode, compiler harus melihat kode yang mengikutinya dan hal ini tidak dapat dibatasi). Jika compiler diberikan sebuah masukan yang sangat besar maka compiler akan membaca seluruh input tersebut ke dalam memori. Sebuah baris kode #include “/dev/random” pada mesin dengan sistem operasi UNIX akan berakibat fatal bagi sistem. Compiler akan terus membaca masukan random ke dalam memori sampai seluruh memori digunakan. Untuk mencegah serangan ini, perlu adanya pembatasan lingkungan kompilasi pada proses kompilasi. Compiler hanya dapat mengakses beberapa resource tertentu. Hal sederhana yang dapat dilakukan adalah untuk menjalankan compiler dengan lingkungan yang sama dengan yang digunakan pada saat menjalankan program kontestan. 2.4.2.3. Accessing Restricted Material Serangan ini termasuk ke dalam tipe compilation-time, execution time, dan priviliges escalation. Penyerang mungkin mengakses materi-materi yang sifatnya rahasia: keluaran yang benar, solusi juri, jawaban lain, berkas nilai, dan lain-lain. Salah satu contoh serangan ini adalah pada saat kompilasi, jika seorang kontestan mengetahui atau menebak lokasi yang benar dari sebuah resource maka kontestan akan mencoba memasukkan resource tersebut ke dalam kode program. Pada saat kompilasi dan eksekusi, seharusnya resource tersebut tidak tersedia pada mesin yang sedang digunakan. 2.4.2.4. Misusing The Network Serangan ini termasuk ke dalam tipe contest-time dan priviliges escalation. Jika kontestan dapat memonitor dan menyimpan trafik jaringan terutama trafik ke sistem automated judge, maka kontestan dapat melakukan intersepsi jawaban kontestan lain dan mengumpulkan jawaban tersebut sebagai miliknya. Kontestan juga dapat melakukan komunikasi dengan kontestan lain melalui jaringan atau menggunakan password kontestan lain untuk mencuri jawaban milik kontestan tersebut. Untuk mencegahnya, komunikasi pada sistem kompetisi berbasis web
II-13
harus dilakukan dengan menggunakan protokol HTTPS. Untuk sistem kompetisi onsite, pencegahan juga dapat dilakukan dengan cara melakukan konfigurasi jaringan, memonitor trafik jaringan, dan juga mencatat aksi-aksi kontestan. 2.4.2.5. Modifying or Harming Testing Environment Serangan ini termasuk ke dalam tipe execution time, destructive, dan DoS. Serangan paling sederhana dari tipe ini adalah dengan mengirimkan kode yang dapat menghilangkan berkas apa pun yang bisa dihilangkan. Cara lain adalah dengan menuliskan keluaran sebesar-besarnya sehingga
sistem menjadi
kekurangan space harddisk. Meski dengan penggunaan sandbox, pengembang sistem kontes harus tetap berhati-hati atas apa yang boleh dijalankan oleh program peserta. Hampir semua yang tidak penting untuk program yang benar dapat disalahgunakan untuk merusak sistem. 2.4.2.6. Circumventing the Time Measurement Serangan ini termasuk ke dalam tipe execution time. Pada serangan ini, peserta berusaha untuk memotong waktu hasil pengukuran automated judge untuk memperoleh waktu komputasi yang lebih lama. Salah satu caranya adalah jika sistem hanya mengukur waktu proses yang dijalankan oleh sistem maka proses tersebut dapat mengeksekusi fork untuk membuat child process yang akan menjalankan komputasi. 2.4.2.7. Exploiting Covert Channel Serangan ini termasuk ke dalam tipe contest-time dan covert channel. Sistem kontes biasanya memberitahukan hasil penilaian kepada peserta secara langsung. Informasi ini biasanya bergantung pada perilaku program peserta terhada test case yang rahasia. Informasi yang diberikan ini dapat digunakan untuk mendapatkan informasi mengenai test case yang rahasia tersebut. Informasi yang diberikan biasanya berupa informasi mengenai kompilasi gagal, eksekusi gagal, penggunaan memori berlebihan, dan waktu eksekusi berlebihan. Dengan menggunakan informasi ini peserta dapat menebak-nebak test case. Pencegahan dapat dilakukan dengan mendesain test case yang bagus.
II-14
void sendInformation(int n) { malloc(1024*(n&31));//send 5 bits in the memory size n >>= 5; if (n==0) exit(0);//terminate with a wrong answer if (n==1) assert(0);//abort if (n==2) while(1);//exceed the time limit if (n==3) { int a=3*n; a/=9-a; }//division by zero } Kode II-2. Exploiting Covert Channel
2.4.2.8. Misusing Additional Services Serangan ini termasuk ke dalam tipe contest-time dan denial of service. Biasanya sistem kontes memiliki fasilitas tambahan seperti pencetakan kode program dan juga fasilitas backup. Peserta dapat melakukan serangan terhadap fasilitas seperti ini, contohnya mencetak berkas sebanyak 500 halaman sehingga menghabiskan kertas pada printer. Peserta juga dapat melakukan backup data yang sangat besar sehingga mesin kehabisan space pada harddisk. %!PS /Times-Roman findfont 100 scalefont setfont /page 0 def { /page page 1 add def % increment the page counter page 4 gt { exit } if % try omitting this line! 100 550 moveto page 20 string cvs show % print the page number showpage % ship out the page } loop Kode II-3. Misusing Additional Service
2.4.2.9. Exploiting Bugs In Operating System Serangan ini termasuk ke dalam tipe execution-time, contest-time dan priviliges escalation. Jika kontestan mampu mengakses mesin di mana jawaban dinilai, maka kontestan dapat melakukan scanning mesin ini untuk mencari kelemahan
II-15
sistem dan mencoba mengeksploitasinya. Kontestan dapat mencoba menjalankan sebuah kode pada mesin termasuk di dalamnya sebuah exploit. Eksploitasi yang berhasil akan berujung pada pemaparan test case yang rahasia sampai membiarkan kontestan merusak sistem yang bersangkutan. Untuk mencegahnya, perlu dibuat isolasi pada beberapa subsistem sehingga tidak dapat diakses oleh kontestan. Kontestan hanya dapat berinteraksi dengan sebuah komputer yang berperan sebaga antar muka dari kontes. Jawaban kontestan harus dieksekusi pada sebuah sandbox yang aman untuk dapat mencegah pengaksesan bagian-bagian dari sistem operasi. 2.4.2.10. Obfuscation Obfuscation bukan merupakan tipe serangan melainkan sebuah cara untuk membantu kesuksesan tipe serangan yang lain. Sebagai contoh, pada banyak sistem kontes metode penanganan fungsi-fungsi terlarang pada kode program dilakukan dengan mencari nama fungsi tersebut pada kode program. Akan tetapi cara demikian tidak cukup ketika nama kode program diobfuskasi. Untuk melakukan pencegahan pemanggilan fungsi tersebut perlu dilakukan pencegahan pada level system call. Sistem perlu mendeteksi pemanggilan system call yang dilakukan oleh program peserta. 2.4.3. Scalability Peningkatan kinerja adalah salah satu isu yang paling penting di dalam sistem komputasi terdistribusi. Peningkatan kinerja ini biasanya ditangani dengan 2 cara yakni menambahkan node ke dalam sistem (scale out) atau meningkatkan kapasitas dari sebuah node (scale up). Meski demikian, banyak situasi buruk disebabkan oleh pendistribusian kerja yang buruk pada keseluruhan sistem. Untuk itu dibutuhkan strategi load balancing yang baik pada pembagian kerja dari node sumber pekerjaan (source) kepada node yang melakukan pekerjaan. (server) Load sharing adalah usaha untuk menjaga kemampuan sistem dalam bekerja dengan menjamin bahwa tidak ada satu node yang idle dalam menunggu pekerjaan [WAN85]. Load balancing sendiri adalah pendekatan dimana proses yang ingin dikerjakan akan didistribusikan ke pada semua node sehingga beban
II-16
kerjanya menjadi sama. Load sharing sering diacu sebagai load balancing karena proses load sharing juga bertujuan untuk menyamakan beban kerja pada setiap node. Sifat-sifat yang diinginkan dari adanya load sharing antara lain 1. Optimal Overall System Performance Jumlah kapasitas pemrosesan menjadi maksimal dan mempunyai jeda yang dapat diterima. 2. Fairness of Service Kinerja yang adil untuk setiap pekerjaan yang dilakukan. 3. Failure Tolerance Sistem dapat berjalan dengan baik meski dapat terjadi beberapa kesalahan. Wang juga membagi load sharing kedalam dua jenis taksonomi. Taksonomi pertama membagi load sharing kedalam dua jenis yakni source initiative dan server initiative. Di dalam source initiative, source akan memilih server node untuk diberi pekerjaan. Sedangkan server initiative, algoritma pembentukan antrian dilakukan pada server node. Perbedaan yang lain adalah pada source initiative, keputusan pembagian terjadi pada saat pekerjaan tiba, sedangkan pada server initiative, keputusan terjadi pada saat pekerjaan pergi dari server.
Tabel II-2. Klasifikasi Load Sharing Information Dependency 1 2 3 4
5
6
7
Source Initiate
Server Initiate
server = f(source) server = f(source, ω) server = f(source, ω, sequence state) server = f(source, ω, sequence state, server busy/idle status) server = f(source, ω, sequence state, server queue length) server = f(source, ω, sequence state, server queue length, departure epoch of completed job at servers) server = f(source, ω,
source = f(server) source = f(server, ω) source = f(server, ω, sequence state) source = f(server, ω, sequence state, source queue emptiness) source = f(server, ω, sequence state, source queue length) server = f(source, ω, sequence state, arrival epoch of jobs at source)
server = f(source, ω,
II-17
Information Dependency
Source Initiate
sequence state, server queue length, departure epoch of completed and remaining job at servers) * ω randomly generated parameter
Server Initiate sequence state, server queue length, arrival epoch and execution times of jobs at sources)
Taksonomi kedua disebut dengan information dependency. Jenis ini membagi load sharing ke dalam derajat-derajat berdasarkan informasi yang dibutuhkan oleh server node tentang status dari source node atau sebaliknya. Terdapat 7 derajat ketergantungan informasi mulai dari derajat pertama di mana pembagian kerja tidak membutuhkan informasi sama sekali dan derajat terakhir di mana strategi membutuhkan informasi tambahan. Adanya informasi ini akan meningkatkan kinerja dengan penambahan overhead pada komunikasi dan koordinasi. Tabel II.2 menunjukkan perbedaan information dependency pada sourceinitiative dan server-initiative. Algoritma source-initiative dilambangkan dengan sebuah fungsi … . yang berarti server yang ditunjuk merupakan fungsi dari . Begitupula dengan algoritma server-initiative. … .
