Online Judge (grader) design

ดองบล็อคไปเสียนานมากในขณะที่เกมก็เริ่มมีเกมที่มันเล่นจนแบบว่าไม่รู้จะเล่นยังไงให้สนุกแล้วจนต้องดรอปไปอยู่บ้าง

ในภาคซอฟต์แวร์จะมีกิจกรรมอยู่อันนึงครับคือ SOSCamp เป็นการติวโปรแกรมมิ่งให้น้องใหม่ซึ่งก็จะมีการทำโจทย์ พอทำโจทย์ก็ต้องมีระบบตรวจ เพื่อนรีเควสมานานมากกกแล้วว่าอยากรู้ design ของระบบก็เลยเขียนสักหน่อย

## Overall

ระบบแบ่งเป็น 3 ส่วนครับคือ UI, API, Grader ซึ่งผมเลือกเป็น PHP หมดเลยเพราะช่วงนั้นเห่อ [Laravel](http://laravel.io) และ [Silex](http://silex.sensiolabs.org) นิดๆ และถ้ามีคนจะช่วยทำ ใช้ Silex บน PHP น่าจะง่ายกว่าใช้ Django โดยเฉพาะคนที่เขียน Java มา คือ Silex ค่อนข้างจะ low level มาก เขียนอะไรๆ มันจะตรงไปตรงมาไม่มีลัดเท่าไร แล้วก็ PHP Class มันหน้าตาเกือบ Java ตัด type

## UI

ตัว UI เขียนด้วย AngularJS ทั้งหมดเลยเพราะผมอยากลองเล่น [AngularJS](http://angularjs.org) พอดี เขียนเสร็จก็เรียนรู้มันไปเยอะแต่รู้สึกว่ายากอยู่ ตอนหลังมารื้อทำใหม่แล้วเอาระบบ resolve ออกพบว่าเขียนง่ายขึ้นเป็นกอง

ด้วยสไตล์ของ Angular อยู่แล้ว ตัว UI ทั้งหมดออกแบบเป็นแบบ single page app คือมี HTML file เดียวรันทุกอย่าง ไม่มีการเปลี่ยนหน้าใดๆ นอกจากการใช้ AJAX ดึงข้อมูลมาแสดง ตรงนี้การเลือกใช้ Angular + Angular-ui-router ทำให้เขียนง่ายและดีมากๆ

ข้อดีอย่างนึงของการทำ Single page app คือมันบังคับให้ทุกอย่างเป็น API พอจะทำใหม่ก็ทำได้ง่ายๆ แค่เขียนตัวครอบ API ขึ้นมาใหม่ จบ

## API

ฝั่ง API ใช้ Silex ครับ ผมลองเขียนแบบ OOP ดูโดยทำคลาสที่สามารถ extend มันมาแล้วระบุชื่อ Eloquent model และ URL (Eloquent เป็น library สำหรับต่อ database ของ Laravel ซึ่งผมดึงมาใช้เดี่ยวๆ ไม่เอา Laravel มาทั้งตัว เป็น ORM ตัวเดียวใน PHP ที่ผมชอบ) จะได้เป็น API ที่สามารถ List, read, write ลง database ได้ทันทีพร้อมระบบ access control ซึ่งก็ลดเวลาพัฒนาไปได้มาก ตอนหลังผมแกะระบบตัวนี้ไปใช้ในระบบลงทะเบียนงานบายเนียร์ด้วย วันเดียวก็เขียนระบบเสร็จ

## Grader

ส่วนสำคัญที่สุดของโปรแกรมแน่นอนว่าต้องเป็นตัวเกรดเดอร์เอง ซึ่งตัวเกรดเดอร์นั้นใช้ไลบรารีหลายตัวช่วยในการพัฒนา (ผมคิดว่าบางตัวเป็น extra ไม่ใช้ก็ได้ แต่ใช้แล้วมันทำให้โปรแกรมเท่ขึ้น พวก Symfony/Console Symfony/Process พวกนี้)

ตัว grader จะต่อเข้ากับคิวงานกลาง ซึ่งระบบเก็บคิวงานที่ผมใช้คือโปรแกรม beanstalkd และใช้ library pheanstalk เพื่อเชื่อมต่อจาก PHP เมื่อมีการส่งงานเข้ามาใน API ก็จะโยนรายละเอียดงานเข้าไปใน beanstalk

ตัว grader ที่ต่อกับคิวงานนั้นจะมี infinite loop รับงานใหม่อยู่ เมื่อได้รับงานแล้วก็จะเข้าสู่ logic ในการตรวจ ซึ่งจะมีกระบวนการคือ

### 1. รันโค้ด generate test case

ตัวระบบ test case generator ผมอยากให้มันทรงพลัง สุ่มโจทย์ได้ และเป็นธรรมชาติที่สุด ก็เลยใช้วิธีเขียนโปรแกรมมาครอบโปรแกรมที่ใส่ไว้ในโจทย์ ข้อเสียคือรองรับการส่งได้แค่ภาษาที่มีโปรแกรมครอบ

หน้าที่ของโปรแกรมครอบไม่ยากครับ ขั้นแรกโปรแกรมจะ include โปรแกรมที่โจทย์กำหนดเข้ามา (ใน Java ใช้ reflection, Python ใช้ exec ซึ่งผมว่าไม่ดีเพราะ \__name__ มันไม่เปลี่ยน, PHP ใช้ include) ทีนี้ขั้นต่อมาจะแยกตามภาษา

– **PHP:** มันคือ `echo json_encode(run());` นั่นล่ะครับ
– **Java:** มันจะส่ง `LinkedList` เข้าไปโดย pass by reference แล้วเอา LinkedList ตัวนั้นส่งเข้า GSON ออกมา
– **Python:** ผมจำไม่ชัวร์แต่น่าจะประมาณว่าเอา for in วนเพื่อทำเป็น list แล้วโยนใส่ `json.dumps`

จริงๆ มันก็ดูไม่ช่วยเท่าไรนะ แต่ผมว่า python เนี่ยมันเขียนสนุกดีตรงที่ `yield` รัวๆ ไม่ต้องเอาข้อมูลไปพักใส่ array อะไรแล้ว return ออกมาทีเดียวเหมือนภาษาอื่นๆ (PHP ก็มี yield แต่มันใหม่เกินไป)

### 2. คอมไพล์โค้ดเฉลยและโค้ดคำตอบ

มาถึงขั้นตอนสำคัญครับคือการคอมไพล์โค้ด ซึ่งก็ไม่มีอะไรยากเท่าไรคือรัน compiler ตามแต่ภาษาแล้วให้มันออกมาที่ไฟล์ที่กำหนดก็เสร็จ แต่ความยุ่งยากอยู่ที่ Java ซึ่งชื่อคลาสจะต้องเป็นไปตามชื่อไฟล์ด้วย ผมก็เลยใช้วิธีโกงๆ คือตั้งชื่อไฟล์ว่า Input.java แล้วคอมไพล์ ถ้ามันผ่านก็จบ ไม่ผ่านตัว `javac` จะบอกมาว่า should be named ….java ก็ให้โปรแกรมมันอ่าน error ตัวนี้ไปแล้ว rename file ให้ (และเก็บชื่อคลาสไว้ด้วยเพราะตอนรันต้องใช้)

### 3. Run

ขั้นตอนการรันก็รันแบบตรงไปตรงมาครับ ทีนี้จะพูดถึงเทคนิคการ sandbox หรือป้องกันความปลอดภัยของโค้ดสักหน่อย ซึ่งจริงๆ มันทำงานมาตั้งแต่ส่วน generate test case แล้ว

ตัว grader จะใช้โปรแกรม docker ในการรันครับ ซึ่งหลักการคร่าวๆ ของ docker มันคือการใช้ความสามารถ namespace, cgroup ของ linux kernel ใหม่ๆ ช่วยแยกการทำงาน คนที่อยู่ namespace อื่นๆ จะมองไม่เห็นกันเอง แต่ข้างนอกสุดมองเห็นข้างในได้ นอกจากนี้มันยังสามารถกำหนดทรัพยากรให้ cgroup ได้อีกด้วย (คล้ายๆ virtualization แบบ virtualbox อะไรพวกนี้อะครับ แต่มัน overhead ต่ำกว่ามากเพราะรันอยู่ใน kernel ตัวเดียวกันเลย)

ข้อดีอย่างนึงของ docker คือสภาวะข้างในมันคงที่ถ้าเราก๊อปไป นั่นหมายความว่าถ้าเราเซตดีๆ version ของ compiler, runtime, library จะเหมือนกันหมดเลยถึงเราจะกระจาย grader ไปหลายๆ เครื่องก็ตาม

ทีนี้เวลารันด้วยความสามารถจำกัดทรัพยากรก็ทำให้สะดวกโยธินในการจัดการแล้วครับ

– memory limit บังคับด้วย cgroup ได้เลยตรงๆ
– networking ก็บังคับได้เลยว่าไม่ให้มีการ์ดแลน
– time limit อันนี้ใช้ symfony/process จับเวลาเอา ถ้าเกินแล้วก็สั่งให้ docker kill ทิ้ง
– privileges ก็สั่งให้ docker รันใน user ปกติ (ปกติ docker จะรันด้วย root) ก็เรียบร้อย

### 4. Cleanup

เสร็จแล้วก่อนจะจากก็ต้องลบไฟล์พวกที่เป็นผลจากการคอมไพล์ต่างๆ และตัว container ออก (ใส่เข้ามาทีหลังตอนเทส fork bomb ดู) เป็นอันเสร็จ

### 5. Submit

ตัว grader จะส่งงาน 2 รอบคือตอนที่ได้งานมา (เพื่อแสดงสถานะ grading) และเมื่อเสร็จแล้วจะส่งข้อมูลกลับเข้าไปใน API อีกครั้งหนึ่ง ซึ่งก็เป็น JSON ธรรมดา โดยอาศัยการยึนยันตัวแบบ shared secret คือ API, grader จะมี string ตัวหนึ่งเปรียบเสมือนรหัสผ่านที่ต้องส่งให้ API ทุกครั้งที่จะอัพเดตสถานะงาน

## อื่นๆ

จริงๆ แล้วไม่ใช้ docker ก็ได้นะครับ เช่น elab ใช้โปรแกรม box ถ้าผมจำไม่ผิดมันจะใช้ความสามารถ ptrace คือเมื่อโปรแกรมลูกมีการเรียกฟังก์ชั่นของระบบ โปรแกรมแม่ (นั่นคือ box) จะถูกถามว่าอนุญาตหรือไม่ก่อนที่จะทำงานได้ (chrome เก่าๆ รู้สึกว่าจะใช้เทคนิคนี้เหมือนกันบนลินุกซ์) ตอนหลัง box มีรุ่นใหม่คือ isolate ซึ่งก็ใช้ cgroup เหมือนกัน แต่ผมเดาว่าน่าจะ overhead น้อยกว่า docker

(ผมไม่ได้เช็ค fact ตรงนี้นะ ไปค้นดูละเอียดๆ เองดูก่อนถ้าจะลองทำดู)

หรือจะใช้วิธีดิบเถื่อนรันไปตรงๆ เลยก็ได้ ซึ่งผมเดาว่ารุ่นพี่คงจะใช้กันเพราะมันเขียนง่ายดี แต่อาศัยความเชื่อใจว่าจะไม่มีใครส่งอะไรน่ากลัวเข้าไปในระบบ ยิ่งบางทีไม่ได้เขียน time limit ไว้ด้วย ส่ง infinite loop เข้าไปก็เรียบร้อย

ผมคิดไว้ทีนึงว่าวิธีนึงที่ทำให้มันเร็วขึ้นคือรัน docker แช่ไว้เลยแล้วข้างในมีโปรแกรมที่เขียนในภาษานั้นๆ แล้วข้างนอกแค่บอกให้รันโค้ด ซึ่งมันจะตัด overhead เรื่องการ start, stop ตัว docker และ runtime ของภาษานั้นๆ ไปได้พอสมควรเลย แต่ข้อเสียคือเรื่อง memory leak และการ limit ต่างๆ จะทำได้ยากกว่า ใน source ของ grader จะมีคลาส EnhancedJava อยู่ซึ่งผมก็ใช้หลักการตรงนี้ แต่เขียนไม่เสร็จเพราะเขียนๆ ไปแล้วนึกถึงเรื่องการจับ limit นี่แหละแล้วคิดว่าเลิกทำดีกว่า ให้ผมคุมเองน่าจะมีปัญหา security ตามมาแหงๆ

KUWIN Autologin

ผมเห็นรุ่นพี่หลายคนทำ KUWIN autologin ไว้หลายตัว @nattster on Android Firefox Standalone แต่เหมือนว่าจะโดน CAPTCHA ติดเลยใช้ไม่ได้ (หรือเปล่า ผมไม่ได้ลอง)

ทีนี้หน้า Login KUWIN เนี่ย จะเป็น CAPTCHA บวกเลขครับ ผมเดาๆ อยู่นะว่ามันมีทางแกะได้ ไว้ไม่มีไรทำจริงๆ (แปลว่าชาติหน้า) จะลองแกะดูเพราะมันดูง่าย ทีนี้ผมเป็นคนบวกเลขในใจไม่ได้ เจอสองหลักมีทดเปิด terminal รัน bc คิดอย่างเดียว บังเอิญผมเจอกับ KUWIN Tools บน Android ซึ่งเป็น Official apps เลยก็เลยสงสัยว่ามันทำยังไง แอพทางการไม่น่าจะใช้วิธีแกะ CAPTCHA

เอาล่ะ ได้เวลาแฮค!

ก่อนอื่นเลยก็ต้องมี APK มันก่อนครับ ก็สอยกลับมาง่ายๆ ด้วย adb pull โง่ๆ ทีนึง เสร็จแล้วผมก็ Google ต่อ ว่าจะทำอะไรกับมันดี เอาเป็นว่า decompile ละกัน

Google แนะนำคำถามนี้ มาให้ผมซึ่งก็ตรงเป๊ะ คือ โหลด dex2jar มาแก้เป็น jar แล้วใช้ jd-gui แก้กลับเป็น Java ก็ลุยสิครับ

Screen Shot 2556-09-14 at 11.29.40 PM

ผมเดาว่าโค้ดต้องสงสัยอยู่ไม่ใกล้ไม่ไกลอยู่นี่แหละ แต่โค้ดมันแก้ตัวแปรนิดๆ แล้วมีเมธอดนี้หลายอันแต่หลาย signature ผมไม่แน่ใจ เลยตัดสินใจว่าจะเล่นมุกเดิมอีกคือ Privoxy ขาประจำ แต่ทว่า…

Screen Shot 2556-09-14 at 11.31.32 PM

มันมีเส้นกั้นบางระหว่างผมกับปลายทาง ผมเห็น mobile.php ขึ้นหรา นั่นคือคำตอบผมแน่ๆ แต่ผมจะรู้ได้ยังไงว่าจะส่งอะไรเข้าไป และตอนนี้กำแพงระหว่างผมกับมันคือตัว s เพียงตัวเดียวที่อยู่ในคำว่า https

เอาวะ!

ด้วยความที่ผมยังไม่อยากจะอ่าน Java มั่วๆ นั่น ผมเลยตัดสินใจว่าเรามาอ่าน assembly (หรือให้ถูกคือ smali) ดีกว่า

Screen Shot 2556-09-14 at 11.34.55 PM

เข้าใจง่ายกว่า Java สิบเท่า gg…

ยังสิ ผมตัดสินใจว่าแก้ก็แก้วะ ก็เลยเดาไปเดามาสองสามที สุดท้ายแทบจะ rewrite method ตัวนั้นใหม่ให้เหลือ string เดียว (เหมือนจะก๊อปจากเมธอดอื่นมา) แล้วก็ได้ตามต้องการ โค้ดจะส่งข้อมูลไปหาเว็บผมแทน ผมลงแอพที่โมในมือถือทันทีและรัน ไม่นานก็ได้ข้อมูลที่ต้องการ ไม่ต้องพึ่ง Privoxy


ตอนนี้ protocol mobile.php ก็แกะมาได้พอสมควรแล้วครับ เลยทำเป็น extension KUWIN Autologin ขึ้นมา ก็เข้าไปดาวน์โหลดใช้ได้ เวลาเข้าเว็บอะไรมันจะดีดขึ้นมาว่า logging in แล้วก็ logged in ให้เข้าเว็บนั้นอีกทีก็เข้าได้เลยโดยไม่ต้องใส่รหัสผ่าน

(Chrome มันไม่มี API wifi connect อะนะครับเลยทำ auto login แบบไม่ต้องกดอะไรเลยไม่ได้ ผมจะ hold request คาไว้จนกว่าจะ login เสร็จก็ไม่ได้เพราะ sync request มันห้าม AJAX กลัวเกิด circular ซ้อนกันไปมา)

สำหรับหน้า settings ผมขี้เกียจทำก็เลยฝากเพื่อนทำ เพื่อนก็ฝากพี่ทำมาให้แบบที่เห็น ตอนแรกเป็น Comic Sans ผมเห็นแล้วปวดใจเลยแก้ๆ ได้เท่านี้ ไว้รุ่นหน้าอยากเพิ่มฟีเจอร์แล้วจะมาทำเอง (ว่าจะใส่ bandwidth log น่ะครับ)

Okay, KUWIN fixed. Next stop: nisit.kasetsart.org…