Αλέξανδρος Φραντζής Φεβ 2006
To άρθρο αυτό είναι το τέταρτο της σειράς "Reverse Engineering σε περιβάλλον Linux". Σκοπός της σειράς είναι να εξοικοιώσει τους αναγνώστες με τις βασικές τεχνικές του Reverse Engineering, με έμφαση στο πως αυτές μπορούν να εφαρμοστούν στο Linux, και να τους προσφέρει πιο βαθιές γνώσεις για τη λειτουργία του συστήματος τους.
1. Εισαγωγή
2. Εικονικές Μηχανές
3. Μερικές σκέψεις για το μέλλον του RCE - Obfuscation
4. Hands-on παράδειγμα: Java vs C
5. Πρόκληση
Καλωσήρθατε στο τέταρτο άρθρο (η μέτρηση αρχίζει από το 0) για Reverse Code Engineering σε Linux!
Το γενικό θέμα με το οποίο ασχολείται το παρόν άρθρο είναι οι εικονικές μηχανές (Virtual Machines).
Στο πρώτο τμήμα θα ασχοληθούμε εν συντομία με την ιστορία και το γενικό σχεδιασμό των VMs.
Στο δεύτερο τμήμα εκφράζονται μερικές σκέψεις μου για το μέλλον του RCE και το πως σχετίζεται η τεχνική του obfuscation με αυτό.
Στο τρίτο τμήμα του άρθρου, θα μάθουμε γιατί ο κώδικας Java μπορεί να είναι πιο γρήγορος από τον ίδιο κώδικα σε C.
Στο τέταρτο και τελευταίο τμήμα θα δώσουμε μια ενδεικτική λύση για την προηγούμενη πρόκληση και βέβαια το Hall of Fame.
Καλό RCE!
Η εικονική μηχανή (Virtual Μachine), όπως δηλώνει και το όνομα της, είναι μια μηχανή που υφίσταται μόνο στο βασίλειο του αφηρημένου. Πρόκειται για επεξεργαστή υλοποιημένο μόνο με λογισμικό, με δικό του σετ εντολών και ιδιαίτερων χαρακτηριστικών.
Μια προφανής και σημαντική χρήση των εικονικών μηχανών είναι η εξομοίωση και η μελέτη υπαρχόντων ή και υπό σχεδίαση hardware συστημάτων. Για αυτή την κατηγορία έχει επικρατήσει η ονομασία εξομοιωτής (emulator) και σήμερα για σχεδόν όλα τα υπολογιστικά συστήματα περασμένων εποχών υπάρχει ένας εξομοιωτής.
Ένας δεύτερος πολύ σημαντικός λόγος για την ύπαρξη VMs είναι η χρήση τους ως ένα "μονωτικό στρώμα" ανάμεσα στις εφαρμογές και το υλικό. Μια εφαρμογή που είναι σχεδιασμένη για μια VM μπορεί να εκτελεστεί σε οποιοδήποτε επεξεργαστή για τον οποίο υπάρχει ένας διερμηνευτής για τον κώδικα της VM. Αυτή είναι η νοοτροπία του "Προγραμμάτισε μια φορά, τρέξε παντού" (Code Once, Run Everywhere).
Πολύ συχνά οι εικονικές μηχανές χρησιμοποιούνται για να δώσουν στο προγραμματιστή την ψευδαίσθηση πως δουλεύει σε ένα ιδιαίτερα εξελιγμένο σύστημα, με χαρακτηριστικά ειδικά σχεδιασμένα για την εργασία του. Τέτοιες μηχανές χρησιμοποιούνται σε παιχνίδια όπου βασικές εντολές του εικονικού επεξεργαστή μπορεί να είναι για παράδειγμα "μετακίνησε το sprite A από τη θέση x στη θέση y".
Οι εικονικές μηχανές, αν και είναι πολύ στη μόδα σήμερα, δεν αποτελούν καινούργιο φαινόμενο. Ήδη από το 1970 η ανάγκη διαχωρισμού των διάφορων φάσεων της μεταγλώττισης ενός προγράμματος οδήγησε τους δημιουργούς μεταγλωττιστών στην εισαγωγή και χρήση ενδιάμεσων μορφών κώδικα. Μια πολύ γνωστή ενδιάμεση μορφή είναι η P-Code που χρησιμοποιήθηκε για τους μεταγλωττιστές της γλώσσας Pascal. Πολύ σύντομα η P-Code έπαψε να χρησιμοποιείται μόνο στους μεταγλωττιστές και έγινε η βάση μιας εικονική μηχανής για το σύστημα της UCSD Pascal.
Παρ' όλο που που η δεκαετία του '70 μοιάζει μακρινή, τα πράγματα δεν έχουν αλλάξει πολύ στον συγκεκριμένο τομέα. Οι σύγχρονες γλώσσες προγραμματισμού χρησιμοποιούν το ίδιο μοντέλο με μια μικρή αλλά σημαντική προσθήκη. Για λόγους ταχύτητας, οι πιο εξελιγμένοι διερμηνευτές δεν εκτελούν τον κώδικα σε ενδιάμεση μορφή αλλά τον μετατρέπουν στη γλώσσα μηχανής του επεξεργαστή στον οποίο τρέχουν (native code). Η μετατροπή αυτή γίνεται την ώρα της εκτέλεσης και ονομάζεται Just-In-Time (JIT) μεταγλώττιση, ενώ η κλασική μεταγλώττιση έχει την ονομασία Ahead-Of-Time (AOT).
Οι ενδιάμεσες μορφές κώδικα αλλά και γενικά τα σετ εντολών μπορούν να χωριστούν σε δύο μεγάλες κατηγορίες, ανάλογα με το πως τροφοδοτούνται οι εντολές με δεδομένα.
Στην πρώτη κατηγορία ανήκουν οι μορφές κώδικα στις οποίες τα δεδομένα ανταλλάσσονται μέσω καταχωρητών. Οι μηχανές που υλοποιούν αυτό το μοντέλο ονομάζονται register-based και αποτελούν τη πλειοψηφία των hardware επεξεργαστών. Η πράξη a=a+b*c σε ένα τέτοιο σύστημα έχει τη μορφή:
move t1, b ;; t1=b multiply t1, t1, c ;; t1=t1*c add a, a, t1 ;; a=a+t1
Αντίθετα, τα συστήματα όπου το μέσο ανταλλαγής δεδομένων είναι ο σωρός ονομάζονται stack-based. Ο σωρός αυτός έχει την ειδική ονομασία σωρός τελεστέων (operand stack). Οι περισσότερες εικονικές μηχανές ακολουθούν αυτό το μοντέλο διότι έχει αποδειχθεί ότι προσφέρει ταχύτερη εκτέλεση σε λογισμικό και είναι πιο απλή και συμπαγής. Η πράξη a=a+b*c εδώ έχει την εξής μορφή (στα σχόλια φαίνεται η κατάσταση του σωρού μετά την εκτέλεσης της εντολής):
load b ;; Σωρός: [b] load c ;; Σωρός: [b] [c] multiply ;; Σωρός: [b*c] load a ;; Σωρός: [b*c] [a] add ;; Σωρός: [a+b*c] store a ;; Σωρός: - , a=a+b*c
Να σημειωθεί ότι και στις αρχιτεκτονικές βασισμένες σε καταχωρητές υπάρχει η έννοια του σωρού αλλά δεν έχει τον ίδιο σκοπό, δηλαδή να είναι το βασικό κανάλι δεδομένων μεταξύ εντολών.
Σήμερα, η Java της Sun και το .NET της Microsoft είναι ίσως τα δύο πιο διάσημα περιβάλλοντα που χρησιμοποιούν εικονικές μηχανές. Και τα δύο είναι βασισμένα στη stack-based αρχιτεκτονική και τα σετ εντολών τους είναι παρεμφερή. Τα standards και για τις δύο περιβάλλοντα υπάρχουν ανοικτά στο internet. Στο Linux, υλοποιήσεις της Java Virtual Machine προσφέρονται από τη Sun, την ΙΒΜ και επίσης υπάρχουν μερικές open source προτάσεις όπως το kaffe ( http://www.kaffe.org[1]). Για το .NET στο Linux υπάρχει το open source Mono Project ( http://www.mono-project.com[2]).
2: http://www.mono-project.com
Η ενδιάμεση μορφή στην οποία αποθηκεύονται τα προγράμματα σε Java είναι τα Java Bytecodes. Κατά την εκτέλεση της Java Virtual Machine (JVM) κάθε thread αποτελείται από τα παρακάτω στοιχεία:
Κάθε στιγμή το πρόγραμμα βρίσκεται μέσα σε μία συνάρτηση και αποθηκεύει τις τοπικές πληροφορίες σε ένα πλαίσιο στον κανονικό σωρό. Το πλαίσιο περιέχει το σωρό τελεστέων, έναν πίνακα τοπικών μεταβλητών και κάποιες άλλες πληροφορίες που σχετίζονται με τα δεδομένα της κλάσης στην οποία ανήκει η μέθοδος. Η πρώτη τοπική μεταβλητή (index 0) περιέχει την αναφορά στο τρέχον instance της κλάσης. Πρόκειται ουσιαστικά για το this που σίγουρα έχουν χρησιμοποιήσει όσοι έχουν ασχοληθεί με Java. Από εκεί και πέρα (index 1) οι τοπικές μεταβλητές περιέχουν τις παραμέτρους της συνάρτησης. Η έννοια των τοπικών μεταβλητών είναι πιο ευρεία από αυτή που έχουμε συνηθίσει από άλλες γλώσσες (πχ C).
Ένα μικρό παράδειγμα:
![[IMG]](/kennedy.gemi.dev/35/img/pcode.png){kind=link}
public int alf(int x)
{
if (x > 3)
x++;
else
x--;
return x;
}
παράγει τα εξής bytecodes:
|| .. ! ;----------------------------------------------
|| .. ! ; public int test::alf(int)
|| .. ! ;----------------------------------------------
|| .. ! alf_fd:
|| .. ! iload_1 ;; Φόρτωσε στο σωρό τελεστέων τη δεύτερη τοπική
;; μεταβλητή (την πρώτη παράμετρο της συνάρτησης).
|| fe ! iconst_3 ;; Φόρτωσε στο σωρό τελεστέων τη σταθερά 3.
|| ff ! if_icmpge loc_108 ;; Αν η κορυφαία τιμή στο σωρό τελεστέων είναι μεγαλύτερη ή ίση
;; με την αμέσως προηγούμενη, πήγαινε στη διεύθυνση 108.
|| 102 ! iinc 1, 1 ;; Πρόσθεσε στη δεύτερη τοπική μεταβλητή την τιμή 1.
|| 105 ! goto loc_10b ;; Πήγαινε στη διεύθυνση 10b.
|| 108 !
|| ... ! loc_108:
|| ... ! iinc 1, 0ffh ;; Πρόσθεσε στη δεύτερη τοπική μεταβλητή την τιμή -1.
|| 10b !
|| ... ! loc_10b:
|| ... ! iload_1 ;; Φόρτωσε στο σωρό τελεστέων τη δεύτερη τοπική μεταβλητή.
|| 10c ! ireturn ;; Πάρε την κορυφαία τιμή από τον τρέχον σωρό τελεστέων και
;; τοποθέτησέ την στην κορυφή του σωρού τελεστέων του κώδικα
;; που κάλεσε την τρέχουσα συνάρτηση.
Για να κάνουμε disassemble κάποιο class αρχείο στις εντολές της JVM (όπως παραπάνω) μπορούμε να χρησιμοποιήσουμε τον ΗΤ editor ( http://hte.sourceforge.net[3]). Όμως, μπορούμε να πάμε ακόμα πιο πέρα, χρησιμοποιώντας κάποιον decompiler για Java ο οποίος θα προσπαθήσει να μας δώσει τον αρχικό πηγαίο κώδικα! Δυο πολύ γνωστοί Java decompilers είναι ο MOCHA ( http://www.brouhaha.com/~eric/computers/mocha.html[4]) και ο JAD ( http://kpdus.tripod.com/jad.html[5]).
4: http://www.brouhaha.com/~eric/computers/mocha.html
5: http://kpdus.tripod.com/jad.html
Γλώσσες όπως η Java και η C# που χρησιμοποιούν ενδιάμεσες μορφές κώδικα ως το βασικό μέσο μεταφοράς τους, εμφανίζουν μια νέα πρόκληση για το RCE. Οι ενδιάμεσες μορφές μεταφέρουν αναπόφευκτα πολλές πληροφορίες για τον πηγαίο κώδικα και έτσι κάποιος θα μπορούσε να θεωρήσει πως είναι πιο εύκολο να τον ανασυνθέσουμε. Και αυτό είναι, όντως, αλήθεια.
Έπρεπε, λοιπόν, να βρεθεί ένας διαφορετικός τρόπος για προστασία του κώδικα από τα αδιάκριτα μάτια. Αυτό που έγινε, τελικά, είναι να δοθεί περισσότερο βάρος στην παλιά τεχνική του code obfuscation. Οι ίδιες βασικές αρχές παρέμειναν αλλά προσαρμόστηκαν στη νέα πραγματι��ότητα του αντικειμενοστρεφούς μοντέλου.
Σκοπός του obfuscation είναι να μετασχηματίσει ένα πρόγραμμα σε ένα άλλο, ισοδύναμο του, τέτοιο ώστε να είναι πιο δύσκολο να κατανοηθεί από ανθρώπους. Επιπλέον χρειάζεται ο μετασχηματισμός αυτός να είναι δύσκολα αντιστρεπτός από κάποιο άλλο αυτόματο εργαλείο (deobfuscator). Στο παιχνίδι παίζουν ρόλο πολλοί αντικρουόμενοι παράγοντες και έτσι πρέπει να βρεθεί μια ικανοποιητική λύση, ανάλογα με τις ανάγκες του χρήστη. Για παράδειγμα, αύξηση της πολυπλοκότητας του κώδικα μπορεί να επιφέρει δραματική αλλαγή στην ταχύτητα εκτέλεσης, οπότε πρέπει να αποφασιστεί τι έχει μεγαλύτερη σημασία, η απόδοση ή η προστασία.
Ο πιο απλός τρόπος obfuscation ενός προγράμματος είναι η μετονομασία των συμβόλων του (μεταβλητές, συναρτήσεις κτλ) σε ακατανόητες συμβολοσειρές. Άλλο είναι να βλέπεις μια συνάρτηση "CheckUser" και άλλο αυτή να λέγεται "mvkof89". Πάντως, αν και έτσι δυσχεραίνονται οι RCE προσπάθειες, η κατάσταση δεν είναι τόσο άσχημη.
Το επόμενο βήμα είναι το λεγόμενο control-flow obfuscation. Σκοπός αυτής της τεχνικής είναι να μπερδευτεί τόσο πολύ η ροή του προγράμματος ώστε να είναι δύσκολο να την ακολουθήσει κάποιος. Για παράδειγμα το απλό κομμάτι κώδικα:
printf("OK");
μπορεί να μετασχηματιστεί στο ισοδύναμο:
y=72;
...
x=random();
if ( (x*13) % 5 < 3) {
doit:
if (y > 61)
printf("OK");
else
printf("KUKU");
}
else {
if (y * 2 - 6 == 138)
goto doit;
printf("KUKU");
}
Φανταστείτε τι σύγχυση μπορεί να προκληθεί σε επίπεδο bytecodes (η και γλώσσα μηχανής)! Από τη μεριά τους, οι deobfuscators προσπαθούν να αντιμετωπίσουν τη μέθοδο αυτή χρησιμοποιώντας αυτόματες τεχνικές για την απόδειξη θεωρημάτων. Για παράδειγμα, βλέποντας πως το y είναι 72 ξέρουν πως πάντα ισχύει y>61 και επομένως το printf("KUKU") δεν πρόκειται να εκτελεστεί ποτέ.
Για επιπλέον αύξηση του χάους σε ένα πρόγραμμα, μπορεί να εφαρμοστεί η τεχνική του data obfuscation. Εδώ στο στόχαστρο βρίσκονται πλέον τα δεδομένα του προγράμματος τα οποία σπάνε, συγχωνεύονται, ψευδο-κρυπτογραφούνται και γενικώς υπόκεινται σε ένα σωρό μετασχηματισμούς. Ένα απλό παράδειγμα:
;; Έστω a ένας πίνακας 20 στοιχείων
x = 0;
for(i = 0; i < 20; i++) {
x += a[i];
}
if (x == 10)
printf("Ok!");
else
printf("Kuku!");
;; Έστω a ένας πίνακας 20 στοιχείων
x = 100;
for(i = 0; i <20; i++) {
x += 2 * a[i] + i;
}
if (x == 310)
printf("Ok!");
else
printf("Kuku!");
Υπάρχουν πολλές ακόμη κατηγορίες obfuscating μετασχηματισμών και ένας σωστός συνδυασμός τους καθιστά την κατάσταση πολύ δύσκολη για τον reverse engineer.
Στο μέλλον προβλέπω (κοιτώντας τη κρυστάλλινη σφαίρα :) ) πως το παιχνίδι του RCE σε ένα μεγάλο βαθμό θα έχει μετατραπεί σε ένα παιχνίδι obfuscation/deobfuscation. Εδώ και καιρό υπάρχουν εργαλεία για obfuscation ενώ τον τελευταίο καιρό εμφανίζονται πρωτότυποι deobfuscators βασισμένοι σε σχετικές δημοσιεύσεις. Ας αρχίσουν οι χοροί...
...και την 42η μέρα ο Θεός δημιούργησε την C. Βλέποντας την απειλή οι δυνάμεις του Κακού αποφάσισαν να αντεπιτεθούν... και έτσι γεννήθηκε η Java.
Η Java από τότε που δημιουργήθηκε κλήθηκε να αντιμετωπίσει τις κυρίαρχες τότε (αλλά και σήμερα) C και C++. Η σύγκριση ήταν αναπόφευκτη΄ η Java διαφημιζόταν ως μια πιο κομψή και ασφαλής C++, μια γλώσσα ικανή να χρησιμοποιηθεί σε ένα ευρύ πεδίο εφαρμογών, από ιστοσελίδες μέχρι ενσωματωμένες συσκευές. Όπως συνηθίζεται στον κόσμο των υπολογιστών, ένας "ιερός" πόλεμος ξέσπασε.
Οι πολέμιοι της Java είχαν κυρίως δύο λόγους για τους οποίους ήθελαν να την κάψουν στην πυρά. Καταρχάς υπήρχαν εκείνοι που στο άκουσμα της λέξης "αντικειμενοστρεφής" έβγαζαν σκόρδα και προσπαθούσαν να ξορκίσουν τα δαιμόνια. Σε αυτούς, βέβαια, δεν άρεσε ούτε η C++, η οποία όμως έπαιρνε άφεση διότι μπορούσε απλώς να χρησιμοποιηθεί ως βελτιωμένη C. Ο δεύτερος και πιο καταδικαστικός λόγος ενάντια στην Java ήταν ότι ήταν αργή. Ειδικά σε ότι είχε σχέση με γραφικές διεπαφές (GUI) ήταν εκνευριστικά αργή και επιπλέον είχε μια μέτριας ποιότητας (εμφανισιακά, τουλάχιστον) βιβλιοθήκη χειριστηριών.
Σήμερα, αρκετό καιρό ύστερα από την έναρξη της διαμάχης, τα πράγματα φαίνεται να έχουν μπει σε μια τάξη. Η Java έχει καταφέρει να βελτιωθεί θεαματικά στο φλέγον θέμα της απόδοσης και έτσι έχει κατακτήσει μια αρκετά υψηλή θέση στις καρδιές των προγραμματιστών αλλά και των διοικητικών στελεχών. Η C παραμένει κυρίαρχη στον τομέα για τον οποίο σχεδιάστηκε, τον προγραμματισμό συστημάτων, ενώ η C++ απολαμβάνει μια σταθερή θέση σε εφαρμογές που επωφελούνται από την αντικειμενοστρεφή προσέγγιση και ταυτόχρονα έχουν αυξημένες απαιτήσεις απόδοσης.
Δυστυχώς στις απόψεις πολλών η Java και γενικά οι διερμηνευόμενες (interpreted) γλώσσες έχουν στιγματιστεί από την αργοπορία που τις χαρακτήριζε στα πρώτα τους βήματα. Στο πείραμα που ακολουθεί θα εξετάσουμε και θα εξηγήσουμε την απρόσμενα καλή απόδοση ενός προγράμματος σε Java.
Στο πείραμα που ακολουθεί θα μετρήσουμε τους χρόνους εκτέλεσης του ίδιου προγράμματος σε C (gcc 3.2.3) και σε Java (Sun J2RE 1.4.2_01). Το πρόγραμμα είναι η αναδρομική συνάρτηση υπολογισμού των όρων της σειράς fibonacci fn = fn-1 + fn-2, με f0 = 0 και f1 = 1.
Σε C:
#include <stdio.h>
#include <stdlib.h>
unsigned long fib(unsigned long n)
{
if (n < 2)
return n;
else
return fib(n-1) + fib(n-2);
}
int main(int argc, char *argv[])
{
int n;
if (argc < 2)
n = 1;
else
n = atoi(argv[1]);
printf("%lu\n", fib(n));
return 0;
}
Σε Java:
public class fib {
public static void main(String args[]) {
int n;
if (args.length < 1)
n = 1;
else
n = Integer.parseInt(args[0]);
System.out.println(fib(n));
}
public static int fib(int n) {
if (n < 2)
return n;
else
return fib(n-1) + fib(n-2);
}
}
Μεταγλωττίζουμε τα δύο προγράμματα και τα εκτελούμε 3 φορές το καθένα. Το J2RE της Sun προσφέρει δύο εικονικές μηχανές, την server και την client (default). Η πρώτη έχει μεγαλύτερες απαιτήσεις μνήμης αλλά έχει ως αποτέλεσμα καλύτερη ταχύτητα εκτέλεσης ενώ η δεύτερη έχει πιο μικρές απαιτήσεις αλλά η ταχύτητα εκτέλεσης δεν είναι η βέλτιστη. Εδώ χρησιμοποιούμε την παράμετρο "-server" που επιλέγει την server VM (εικονική μηχανή).
$ gcc -O3 -fomit-frame-pointer -o fib.c.exe fib.c $ time fib.c.exe 39 63245986 real 0m7.479s user 0m7.361s sys 0m0.017s $ time fib.c.exe 39 63245986 real 0m7.478s user 0m7.368s sys 0m0.013s $ time fib.c.exe 39 63245986 real 0m7.471s user 0m7.366s sys 0m0.016s $ javac fib.java $ time java -server fib 39 63245986 real 0m5.853s user 0m5.618s sys 0m0.049s $ time java -server fib 39 63245986 real 0m5.848s user 0m5.625s sys 0m0.043s $ time java -server fib 39 63245986 real 0m5.847s user 0m5.622s sys 0m0.044s
Η Java φαίνεται να έχει αρκετά καλύτερες επιδόσεις από τη C!!! Είναι δυνατόν; Ευτυχώς ή δυστυχώς είναι!
Αφού περάσει το πρώτο σοκ, ανασυντασσόμαστε και προσπαθούμε να φερθούμε όσο πιο επιστημονικά γίνεται. Έχουμε ένα πείραμα με απροσδόκητα αποτελέσματα και καλούμαστε να τα εξηγήσουμε.
Καταρχάς, γνωρίζουμε ότι o διερμηνευτής της Java περιέχει JIT μεταγλωττιστή οπότε γενικά θα περιμέναμε μια καλή απόδοση. Το βασικό ερώτημα είναι το τι έκανε ο JIT μεταγλωττιστής, που δε μπόρεσε να κάνει ο gcc, ώστε να βελτιώσει την απόδοση κατά 20% περίπου. Για να απαντήσουμε σε αυτό το ερώτημα το καλύτερο που μπορούμε να κάνουμε είναι να συγκρίνουμε τον κώδικα μηχανής που παρήγαγε καθένας από τους δύο αντιπάλους.
Τον κώδικα μηχανής που παρήγαγε ο gcc είναι πολύ απλο να τον εξετάσουμε χρησιμοποιώντας τον HT Editor. Βεβαίως, μπορείτε να χρησιμοποιήσετε όποιο εργαλείο σας βολεύει.
|| ....... ! ;**************************************************** || ....... ! ; function fib (global) || ....... ! ;**************************************************** || ....... ! fib: ;xref c80483d7 c80483e4 c8048427 || ....... ! ;xref c8048434 || ....... ! push esi || 8048411 ! push ebx || 8048412 ! mov esi, [esp+0ch] ;; esi=n || 8048416 ! cmp esi, 1 || 8048419 ! mov eax, esi || 804841b ! ja loc_8048420 || 804841d ! || ....... ! loc_804841d: ;xref j804843f || ....... ! pop ebx || 804841e ! pop esi || 804841f ! ret || 8048420 ! || ....... ! loc_8048420: ;xref j804841b || ....... ! sub esp, 0ch || 8048423 ! lea edx, [esi-1] || 8048426 ! push edx || 8048427 ! call fib ;; fib(n-1) || 804842c ! lea edx, [esi-2] || 804842f ! mov ebx, eax || 8048431 ! mov [esp], edx || 8048434 ! call fib ;; fib(n-2) || 8048439 ! lea eax, [eax+ebx] ;; eax = fib(n-1) + fib(n-2) || 804843c ! add esp, 10h || 804843f ! jmp loc_804841d
Ένα πολύ χρήσιμο χαρακτηριστικό του HT editor είναι ότι υποστηρίζει πληθώρα εκτελέσιμων αρχείων, μεταξύ αυτών και τα .class αρχεία της Java! Έτσι είναι απλό να εξετάσουμε και τα bytecodes στα οποία μεταφράστηκε η συνάρτηση fib:
|| ... ! ;---------------------------------------------- || ... ! ; public static int fib::fib(int) || ... ! ;---------------------------------------------- || ... ! fib_1fa: || ... ! iload_0 ;; Σωρός: [n] || 1fb ! iconst_2 ;; Σωρός: [n] [2] || 1fc ! if_icmpge loc_201 ;; Σωρός: -, if (n >= 2) goto loc_201 || 1ff ! iload_0 ;; Σωρός: [n] || 200 ! ireturn || 201 ! || ... ! loc_201: ;xref j1fc || ... ! iload_0 ;; Σωρός: [n] || 202 ! iconst_1 ;; Σωρός: [n] [1] || 203 ! isub ;; Σωρός: [n-1] || 204 ! invokestatic <int fib::fib(int)> 4 ;; Σωρός: [fib(n-1)] || 207 ! iload_0 ;; Σωρός: [fib(n-1)] [n] || 208 ! iconst_2 ;; Σωρός: [fib(n-1)] [n] [2] || 209 ! isub ;; Σωρός: [fib(n-1)] [n-2] || 20a ! invokestatic <int fib::fib(int)> 4 ;; Σωρός: [fib(n-1)] [fib(n-2)] || 20d ! iadd ;; Σωρός: [fib(n-1)+fib(n-2)] || 20e ! ireturn
Η αποστολή μας, αν τη δεχθούμε, είναι να βρούμε και να αναλύσουμε τον κώδικα μηχανής που παρήγαγε ο JIT μεταγλωττιστής (native κώδικας). Το πρόβλημα είναι ότι δε γνωρίζουμε καθόλου την εσωτερική λειτουργία του Sun Java διερμηνευτή (αφού ο κώδικας είναι κλειστός). Το μόνο σίγουρο είναι ότι ο εκτελέσιμος κώδικας μηχανής δημιουργείται δυναμικά κάπου στο χώρο διευθύνσεων της Java και ο έλεγχος κάποια στιγμή περνάει στο σημείο αυτό.
Αρχίζοντας την εξερεύνηση μας εκτελούμε ��ην ltrace -i -o fib.ltr java -server fib 10 (βλέπε προηγούμενα τεύχη). Εξετάζοντας το fib.ltr τα αποτελέσματα δεν είναι ιδιαίτερα ενθαρρυντικά, οπότε συνεχίζουμε με την strace -i -o fib.str java -server fib 10. Προς το τέλος του fib.str βρίσκουμε τα εξής:
[400379db] open("/home/alf/projects/magaz/issue3/src/fib.class", O_RDONLY|O_LARGEFILE) = 5
[401514e7] fstat64(5, {st_mode=S_IFREG|0644, st_size=561, ...}) = 0
[401512f7] stat64("/home/alf/projects/magaz/issue3/src/fib.class", ...
[40036eeb] read(5, "\312\376\272\276\0\0\0.\0$\n\0\7\0\22\n\0\23\0\24\t\0\25"..., 561) = 561
[40036f5f] close(5) = 0
[40118b71] gettimeofday({1081166745, 55282}, NULL) = 0
[40118b71] gettimeofday({1081166745, 55460}, NULL) = 0
[40118b71] gettimeofday({1081166745, 55594}, NULL) = 0
[40118b71] gettimeofday({1081166745, 56101}, NULL) = 0
[40118b71] gettimeofday({1081166745, 56241}, NULL) = 0
...
[401516d7] lstat64("/home", {st_mode=S_IFDIR|0755, st_size=4096, ...}) = 0
[401516d7] lstat64("/home/alf", {st_mode=S_IFDIR|0711, st_size=4096, ...}) = 0
[401516d7] lstat64("/home/alf/projects", {st_mode=S_IFDIR|0755, st_size=4096, ...}) = 0
[401516d7] lstat64("/home/alf/projects/magaz", {st_mode=S_IFDIR|0755, st_size=4096, ...}) = 0
[401516d7] lstat64("/home/alf/projects/magaz/issue3", {st_mode=S_IFDIR|0755, st_size=4096, ...}) = 0
[401516d7] lstat64("/home/alf/projects/magaz/issue3/src", {st_mode=S_IFDIR|0755, st_size=4096, ...}) = 0
[40118b71] gettimeofday({1081166745, 82175}, NULL) = 0
[40118b71] gettimeofday({1081166745, 82915}, NULL) = 0
[40118b71] gettimeofday({1081166745, 83546}, NULL) = 0
[40118b71] gettimeofday({1081166745, 83719}, NULL) = 0
[40118b71] gettimeofday({1081166745, 83851}, NULL) = 0
...
[40159ac5] brk(0) = 0x80c4000
[40159ac5] brk(0x80c5000) = 0x80c5000
[40159ac5] brk(0) = 0x80c5000
[40159ac5] brk(0x80c6000) = 0x80c6000
[40036e5b] write(1, "89", 2) = 2
[40036e5b] write(1, "\n", 1) = 1
...
[400a8ac1] kill(789, SIGRTMIN) = 0
[400a8ac1] kill(789, SIGRTMIN) = 0
[40154c7d] unlink("/tmp/hsperfdata_alf/787") = 0
...
Παρατηρούμε πως η Java διαβάζει το .class αρχείο που περιέχει τα bytecodes της εφαρμογής μας. Ύστερα αρχίζει να διαβάζει συνεχώς την ώρα της ημέρας, μαθαίνει κάποια πράγματα για το τρέχον directory, συνεχίζει να δειγματοληπτεί την ώρα, αυξάνει το μέγεθος του data segment κατά 0x2000 bytes και τελικά τυπώνει το αποτέλεσμα (89). Ομολογουμένως οι πληροφορίες δεν είναι ιδιαίτερα χρήσιμες.
Ένα ενδιαφέρον σημείο είναι το αρχείο /tmp/hsperfdata_alf/787 το οποίο βλέπουμε να διαγράφεται. Παραπάνω στο fib.str υπάρχει το σημείο που ανοίγει:
[400379b8] open("/tmp/hsperfdata_alf/787", O_RDWR|O_CREAT|O_TRUNC, 0600) = 3
[4015bd61] ftruncate(3, 16384) = 0
[4015d8ed] old_mmap(NULL, 16384, PROT_READ|PROT_WRITE, MAP_SHARED, 3, 0) = 0x4081e000
[40036f41] close(3) = 0
Το /tmp/hsperfdata_alf/787 αντιστοιχείται (mapped) στις διευθύνσεις μνήμης 0x4081e000-0x40822000 και περαιτέρω προσπελάσεις γίνονται μέσα από αυτές τις διευθύνσεις. Μπορούμε να δούμε τα περιεχόμενα του αρχείου αν φροντίσουμε ώστε να αργήσει να τελειώσει το πρόγραμμα μας (πχ με java -server fib 100), για να μην προλάβει να σβηστεί το προσωρινό αυτό αρχείο.
Μια σύντομη εξέταση του αρχείου μας δείχνει πως πρόκειται για πληροφορίες που χρησιμοποιεί ο HotSpot(TM) JIT μεταγλωττιστής της Sun. Έτσι εξηγείται και το "hsperfdata_alf" που μάλλον σημαίνει HotSpot(TM) Performance Data για τον χρήστη alf. Επίσης, το αρχείο αρχίζει με τα bytes 0xCA 0xFE 0xC0 0xC0. Η αναζήτηση στο internet για το νόημα των bytes ήταν άκαρπη, πάντως υποψιάζομαι ότι είναι το signature των αρχείων δεδομένων του JIT μεταγλωττιστή.
Αν και (ελπίζω) ενδιαφέρουσα, η ως τώρα περιήγηση στον JIT μεταγλωττιστή δε μας οδήγησε πιο κοντά στη λύση. Παραμένει το καίριο ερώτημα για τη θέση του native κώδικα.
Ένας συλλογισμός που ίσως μας οδηγήσει στη λύση είναι ο παρακάτω: Ο java διερμηνευτής αφού δημιουργήσει τον native κώδικα περνάει τον έλεγχο σε αυτόν. Ο κώδικας μας είναι αμιγώς cpu-intensive, δηλαδή χρησιμοποιεί πολύ τον επεξεργαστή και δεν έχει I/O που μπορούν να διακόψουν τη λειτουργία του. Αυτό σημαίνει πως αν σε μια τυχαία χρονική στιγμή εξετάσουμε σε ποια διεύθυνση δείχνει ο instruction pointer (IP) της διεργασίας, αυτή με πολύ μεγάλη πιθανότητα θα βρίσκεται μέσα στις διευθύνσεις που καταλαμβάνει ο native κώδικας.
Επομένως, το πρόβλημα μας μετασχηματίστηκε στην εύρεση ενός τρόπου να παρακολουθούμε σε ποια διεύθυνση βρίσκεται η εκτέλεση κάποια διεργασίας!
Μια πρώτη σκέψη είναι να εκτελέσουμε την java στο GDB, να διακόπτουμε το πρόγραμμα κάθε λίγο και να καταγράφουμε τις τιμές του IP. Απλό και αποτελεσματικό... μόνο που δε φαίνεται να λειτουργεί στη δική μας περίπτωση :(
$ gdb -q java (no debugging symbols found)...(gdb) r -server fib 10 Starting program: /usr/lib/j2sdk1.4.2_01/bin/java -server fib 10 (no debugging symbols found)...[New Thread 16384 (LWP 1536)] (no debugging symbols found)... (no debugging symbols found)...Cannot find user-level thread for LWP 1536: generic error (gdb) info reg No selected frame. (gdb) q The program is running. Exit anyway? (y or n) y Cannot find thread 16384: generic error (gdb) q The program is running. Exit anyway? (y or n) y Cannot find thread 16384: generic error
Όχι μόνο δεν καταφέραμε να τρέξουμε τη Java αλλά "τα πήρε" και ο GDB. Αααργκ!!! Αν κάποιος ξέρει τι συμβαίνει παρακαλώ να μου γράψει...
Μην απελπίζεστε! Ευτυχώς για εμάς, το πάντα χρήσιμο /proc προσφέρει την υπηρεσία που χρειαζόμαστε (τον τρέχων IP μιας διεργασίας). Η πληροφορία βρίσκεται καλά κρυμμένη μέσα στο /proc/#/stat και θα χρησιμοποιήσουμε την εντολή ps για να τη φέρουμε στην επιφάνεια. Συγκεκριμένα θα χρησιμοποιήσουμε τη παράμετρο -ο για να ορίσουμε τις πληροφορίες που θέλουμε να εμφανίζει η ps (βλέπε man page).
Τώρα, λοιπόν, έχουμε όλα τα εργαλεία στα χέρια μας και μπορούμε να αρχίσουμε δουλειά! Με τις παρακάτω εντολές τρέχουμε τη java και κάθε 0.2 δευτερόλεπτα τυπώνουμε τον IP της (30 δείγματα).
$ java -server fib 100 &
[1] 1390
$ for ((i=0;$i<30;i++)); do ps --pid=1390 -o eip; sleep 0.2; done
EIP
42900340
EIP
429003b8
EIP
4290033b
EIP
4290031c
EIP
4290030f
EIP
42900302
EIP
42900372
EIP
429002e0
EIP
429002e0
EIP
42900414
EIP
42900386
EIP
429003dc
EIP
429003d3
EIP
429002e0
EIP
4290044d
EIP
42900455
EIP
429003dc
EIP
429003b4
EIP
42900369
EIP
42900453
EIP
42900409
EIP
42900350
EIP
42900441
EIP
429003c4
EIP
429002e7
EIP
42900372
EIP
42900390
EIP
42900311
EIP
429003b4
EIP
429003b4
Παρατηρούμε πως ο κώδικας βρίσκεται σε ένα βρόχο με μικρότερη διεύθυνση την 0x429002e0 και μέγιστη 0x42900453. Οι διευθύνσεις αυτές μπορεί να μην είναι τα ακριβή άκρα του βρόχου, αφού έχουμε κάνει τυχαία δειγματοληψία, αλλά με μεγάλη πιθανότητα είναι κάπου εκεί κοντά.
Το μόνο που μένει τώρα είναι να διαβάσουμε τον κώδικα που βρίσκεται σε αυτές τις θέσεις μνήμης. Για το σκοπό αυτό θα χρησιμοποιήσουμε και πάλι το /proc και συγκεκριμένα το "αρχείο" /proc/#/mem. Η πρόσβαση στο αρχείο γίνεται με τις γνωστές εντολές (open/fopen, lseek/fseek, read/fread) αλλά υπάρχουν δύο σημεία που πρέπει να προσεχθούν. Καταρχάς, για να μας επιτραπεί να διαβάσουμε από το mem αρχείο θα πρέπει η δική μας διεργασία να έχει "δεθεί" με τη διεργασία της οποίας τη μνήμη σκοπεύουμε να προσπελάσουμε. Αυτό το "δέσιμο" γίνεται μέσω της ptrace, η οποία μας δίνει το δικαίωμα να παρακολουθούμε τη διεργασία. Ένα δεύτερο σημείο προσοχής είναι ότι θα πρέπει η διεργασία που μας ενδιαφέρει να μην είναι σε κατάσταση εκτέλεσης. Αυτό επιτυγχάνεται στέλνοντάς της το σήμα SIGSTOP.
$ kill -SIGSTOP 1390 $ memread 1390 0x429002e0 0x200 < fib.bin Reading from Process: 1390 Address: 0x429002e0 Size: 512 Successfully read 512 bytes!
Ο αριθμός των 512 bytes επιλέχθηκε αυθαίρετα, με μόνη προϋπόθεση να είναι μεγαλύτερος από τα όρια του βρόχου που βρήκαμε προηγουμένως.
Ο κώδικας του memread: memread.c.gz[6].
Τώρα που επιτέλους έχουμε στα χέρια μας τον native κώδικα μπορούμε να αρχίσουμε την ανάλυση. Τι μυστικά κρύβει, άραγε, αυτό το μικρό αρχείο των 512 bytes;
Φορτώνουμε το αρχείο στον ht με ht fib.bin και επιλέγουμε disasm/x86 mode (πατώντας space ή F6). Παρακάτω φαίνεται ο κώδικας με κάποια σχόλια:
00000000 89842400d0ffff mov [esp-00003000], eax 00000007 81ec24000000 sub esp, 0x24 0000000d 83f902 cmp ecx, 0x2 ;; ecx=n 00000010 0f8c5d010000 jl 0x173 ;; n < 2 ? 00000016 89742414 mov [esp+0x14], esi 0000001a 896c2418 mov [esp+0x18], ebp 0000001e 897c241c mov [esp+0x1c], edi 00000022 8be9 mov ebp, ecx 00000024 4d dec ebp ;; ebp=n-1 00000025 8bd9 mov ebx, ecx 00000027 83c3fb add ebx, fffffffb ;; ebx=n-5 0000002a 8bf1 mov esi, ecx 0000002c 83c6fe add esi, fffffffe ;; esi=n-2 0000002f 8bc1 mov eax, ecx 00000031 83c0fc add eax, fffffffc ;; eax=n-4 00000034 8bd1 mov edx, ecx 00000036 83c2fd add edx, fffffffd ;; edx=n-3 00000039 83fd02 cmp ebp, 0x2 0000003c 0f8c96000000 jl 0xd8 ;; n-1 < 2 => n < 3 ? 00000042 83fe02 cmp esi, 0x2 00000045 7c40 jl 0x87 ;; n-2 < 2 => n < 4 ? 00000047 8954240c mov [esp+0xc], edx ;; 0000004b 89442408 mov [esp+0x8], eax ;; Save registers (1) 0000004f 895c2404 mov [esp+0x4], ebx ;; 00000053 890c24 mov [esp], ecx ;; 00000056 8bca mov ecx, edx 00000058 90 nop 00000059 90 nop 0000005a 90 nop 0000005b e8a0ffffff call 0x0 ;; call fib(n-3) 00000060 89442410 mov [esp+0x10], eax 00000064 8b4c2408 mov ecx, [esp+0x8] 00000068 90 nop 00000069 90 nop 0000006a 90 nop 0000006b e890ffffff call 0x0 ;; call fib(n-4) 00000070 8bf8 mov edi, eax 00000072 037c2410 add edi, [esp+0x10] ;; edi = fib(n-3)+fib(n-4) 00000076 8b0c24 mov ecx, [esp] ;; 00000079 8b5c2404 mov ebx, [esp+0x4] ;; Restore registers (1) 0000007d 8b442408 mov eax, [esp+0x8] ;; 00000081 8b54240c mov edx, [esp+0xc] ;; 00000085 eb02 jmp 0x89 00000087 8bfe mov edi, esi ;; edi = n-2 00000089 83fa02 cmp edx, 0x2 0000008c 7c26 jl 0xb4 ;; n-3 < 2 => n < 5 ? 0000008e 8954240c mov [esp+0xc], edx ;; 00000092 89442408 mov [esp+0x8], eax ;; Save registers (2) 00000096 895c2404 mov [esp+0x4], ebx ;; 0000009a 890c24 mov [esp], ecx ;; 0000009d 8bc8 mov ecx, eax 0000009f e85cffffff call 0x0 ;; call fib(n-4) 000000a4 8be8 mov ebp, eax 000000a6 8b4c2404 mov ecx, [esp+0x4] 000000aa 90 nop 000000ab e850ffffff call 0x0 ;; call fib(n-5) 000000b0 03c5 add eax, ebp ;; eax = fib(n-4) + fib(n-5) 000000b2 eb11 jmp 0xc5 000000b4 8954240c mov [esp+0xc], edx ;; 000000b8 89442408 mov [esp+0x8], eax ;; Save registers (3) 000000bc 895c2404 mov [esp+0x4], ebx ;; 000000c0 890c24 mov [esp], ecx ;; 000000c3 8bc2 mov eax, edx 000000c5 8be8 mov ebp, eax 000000c7 03ef add ebp, edi 000000c9 8b0c24 mov ecx, [esp] ;; 000000cc 8b5c2404 mov ebx, [esp+0x4] ;; Restore registers (2,3) 000000d0 8b442408 mov eax, [esp+0x8] ;; 000000d4 8b54240c mov edx, [esp+0xc] ;; 000000d8 83fe02 cmp esi, 0x2 000000db 0f8c80000000 jl 0x161 ;; n-2 < 2 => n < 4 000000e1 83fa02 cmp edx, 0x2 000000e4 7c39 jl 0x11f ;; n-3 < 2 => n < 5 000000e6 8bfa mov edi, edx 000000e8 89442408 mov [esp+0x8], eax ;; 000000ec 895c2404 mov [esp+0x4], ebx ;; Save registers (4) 000000f0 890c24 mov [esp], ecx ;; 000000f3 8bc8 mov ecx, eax 000000f5 90 nop 000000f6 90 nop 000000f7 e804ffffff call 0x0 ;; call fib(n-4) 000000fc 8944240c mov [esp+0xc], eax 00000100 8b4c2404 mov ecx, [esp+0x4] 00000104 90 nop 00000105 90 nop 00000106 90 nop 00000107 e8f4feffff call 0x0 ;; call fib(n-5) 0000010c 8bf8 mov edi, eax 0000010e 037c240c add edi, [esp+0xc] ;; edi = fib(n-4) + fib(n-5) 00000112 8b0c24 mov ecx, [esp] ;; 00000115 8b5c2404 mov ebx, [esp+0x4] ;; Restore registers (4) 00000119 8b442408 mov eax, [esp+0x8] ;; 0000011d eb02 jmp 0x121 0000011f 8bfa mov edi, edx 00000121 83f802 cmp eax, 0x2 00000124 7c37 jl 0x15d ;; n-4 < 2 => n < 6 00000126 890424 mov [esp], eax 00000129 8bf1 mov esi, ecx 0000012b 8bcb mov ecx, ebx 0000012d 90 nop 0000012e 90 nop 0000012f e8ccfeffff call 0x0 ;; call fib(n-5) 00000134 890424 mov [esp], eax 00000137 8bce mov ecx, esi 00000139 83c1fa add ecx, fffffffa ;; n' = n - 6 0000013c 90 nop 0000013d 90 nop 0000013e 90 nop 0000013f e8bcfeffff call 0x0 ;; call fib(n-6) 00000144 030424 add eax, [esp] ;; eax = fib(n-5) + fib(n-6) 00000147 eb14 jmp 0x15d 00000149 8b6c2418 mov ebp, [esp+0x18] 0000014d 8b7c241c mov edi, [esp+0x1c] 00000151 8b742414 mov esi, [esp+0x14] 00000155 83c424 add esp, 0x24 00000158 e9a377ffff jmp ffff7900 0000015d 03c7 add eax, edi 0000015f eb02 jmp 0x163 00000161 8bc6 mov eax, esi 00000163 03c5 add eax, ebp 00000165 8b6c2418 mov ebp, [esp+0x18] 00000169 8b7c241c mov edi, [esp+0x1c] 0000016d 8b742414 mov esi, [esp+0x14] 00000171 eb02 jmp 0x175 00000173 8bc1 mov eax, ecx 00000175 83c424 add esp, 0x24 00000178 c3 ret 00000179 90 nop ;; Από εδώ και κάτω είναι άχρηστος (για τους σκοπούς μας) κώδικας 0000017a 90 nop 0000017b 8bc8 mov ecx, eax 0000017d ebca jmp 0x149 0000017f 8bc8 mov ecx, eax 00000181 ebc6 jmp 0x149 00000183 8bc8 mov ecx, eax 00000185 ebc2 jmp 0x149 00000187 8bc8 mov ecx, eax 00000189 ebbe jmp 0x149 0000018b 8bc8 mov ecx, eax 0000018d ebba jmp 0x149 0000018f 8bc8 mov ecx, eax 00000191 ebb6 jmp 0x149 00000193 8bc8 mov ecx, eax 00000195 ebb2 jmp 0x149 00000197 8bc8 mov ecx, eax 00000199 ebae jmp 0x149
Το παραπάνω listing αν και μεγάλο σε μήκος είναι στην ουσία αρκετά απλό. Οι βασικοί λόγοι για τους οποίους φαίνεται μπερδεμένο είναι οι συνεχείς μετακινήσεις προς και από το σωρό και οι επαναχρησιμοποίηση των καταχωρητών για εντελώς διαφορετικό σκοπό (πχ ο ebp αρχικά εκφράζει το n-1 ενώ αργότερα, από τη διεύθυνση 0xc7 και πέρα περιέχει κάποιο άλλο άθροισμα).
[]{#advice} Το πρώτο βήμα για την ανάλυση κώδικα σε assembly είναι συνήθως η επισύναψη σχολίων πάνω στον κώδικα όπως παραπάνω. Ένας καλός τρόπος για να συνεχίσουμε είναι η σταδιακή μετατροπή του κώδικα σε κάποια πιο υψηλή και γνώριμη μορφή, αγνοώντας περιττές λεπτομέρειες. Για παράδειγμα, το κομμάτι ανάμεσα στις διευθύνσεις 0x39 και 0x87 θα μπορούσε ως επόμενο βήμα να γραφτεί:
if (n-1 < 2) goto 0xd8
if (n-4 < 2) goto 0x87
edi = fib(n-3) + fib(n-4)
goto 89
87: edi = n-2
89:
και ύστερα, αναγνωρίζοντας τη δομή if-else που υπάρχει:
if (n-1 < 2) goto 0xd8
if (n-4 >= 2)
edi = fib(n-3) + fib(n-4);
else
edi = n-2;
89:
Ακολουθώντας μια τέτοια διαδικασία τελικά καταλήγουμε στον παρακάτω Java/C κώδικα που εκφράζει πιο ξεκάθαρα την λειτουργία του assembly κώδικα:
int fib_jit(int n)
{
int C,D;
if (n < 2)
return n;
if (n >= 3) {
int A,B;
if (n >= 4)
A=fib_jit(n-3)+fib_jit(n-4);
else
A=n-2;
if (n >= 5)
B=fib_jit(n-4)+fib_jit(n-5);
else
B=n-3;
C=A+B;
}
else
C=n-1;
if (n >= 4) {
int A,B;
if (n >= 5)
A=fib_jit(n-4)+fib_jit(n-5);
else
A=n-3;
if (n >= 6)
B=fib_jit(n-5)+fib_jit(n-6);
else
B=n-4;
D=A+B;
}
else
D=n-2;
return D+C;
}
Βέβαια, ακόμη και με την παραπάνω μορφή το τι ακριβώς συμβαίνει και γιατί λειτουργεί το κατασκεύασμα του JIT μεταγλωττιστή παραμένει κάπως μυστήριο. Για να ανακαλύψουμε όλη την αλήθεια θα πρέπει να θυμηθούμε την αρχική συνάρτηση fib. Αυτή μπορεί να ξαναγραφτεί ως:
public static int fib(int n) {
int R;
if (n >= 2)
R=fib(n-1) + fib(n-2);
else
R=n;
return R;
}
Σας θυμίζει τίποτα; Η δομή if-else που υπάρχει στη αρχική fib φαίνεται να μοιάζει πολύ με τις if-else που υπάρχουν διάσπαρτες στην fib_jit. Για την ακρίβεια, οι δομές που υπάρχουν στην fib_jit είναι η fib() για διάφορες παραστάσεις του n!!!
Για να γίνει πιο κατανοητό το παραπάνω θεωρήστε το:
if (n >= 4)
A = fib_jit(n-3)+fib_jit(n-4);
else
A = n-2;
το οποίο πρακτικά είναι το:
Α=fib(n-2);
Κάνοντας τις παραπάνω αντικαταστάσεις και κάποιες απλοποιήσεις προκύπτει η εξής fib_jit1:
int fib_jit1(int n)
{
int C,D;
if (n < 2)
return n;
if (n >= 3)
C = fib(n-2) + fib(n-3);
else
C = n-1;
if (n >= 4)
D = fib(n-3) + fib(n-4);
else
D = n-2;
return D+C;
}
Χμμ, εμφανίστηκαν πάλι οι γνωστές δομές if-else. Είναι σαν τον κώδικα της μαρμότας... ξαναζείς τον ίδιο κάθε φορά :) Αν αντικαταστήσουμε και αυτές τις δομές με την αντίστοιχη fib προκύπτει:
int fib_jit2(int n)
{
if (n < 2)
return n;
return fib(n-1) + fib(n-2);
}
H παραπάνω συνάρτηση δεν είναι άλλη από τη αυθεντική fib! Επομένως φτάσαμε στο συμπέρασμα πως fib=fib_jit και άρα όντως η fib_jit λειτουργεί σωστά, αφού στην ουσία είναι η ίδια η fib σε άλλη μορφή.
Τώρα πιστεύω πως είναι σαφές τι "μαγικά" έκανε ο JIT μεταγλωττιστής της Java. Ουσιαστικά έκανε inlining των αναδρομικών κλήσεων της fib σε δύο επίπεδα βάθους! Αυτό είχε ως αποτέλεσμα να αποφευχθεί ένα μέρος του κόστους των κλήσεων συναρτήσεων και επομένως να αυξηθεί η ταχύτητα εκτέλεσης.
Τελικά είναι η Java πιο γρήγορη από τη C; Θέλω να ελπίζω πως θα συμφωνήσετε μαζί στο ότι αυτή είναι η λάθος ερώτηση! Αυτό που πρέπει να ρωτήσουμε είναι αν ο JIT μεταγλωττιστής παράγει πιο γρήγορο κώδικα από τον gcc. Η απάντηση είναι πως ειδικά σε αυτή τη περίπτωση ναι και σε γενικές γραμμές παράγει εξίσου καλό κώδικα.
Αν συνεχίσουμε το πείραμα και μεταγλωττίσουμε τη συνάρτηση fib_jit() (σε C) με τον gcc, το τελικό εκτελέσιμο θα έχει ελαφρώς καλύτερη απόδοση από αυτό της Java. Το θέμα εδώ είναι ότι ο JIT μας απαλλάσσει από αυτή τη διαδικασία. Βέβαια, για να υπερασπιστούμε λίγο και τον gcc, o JIT μεταγλωττιστής έχει το πλεονέκτημα πως έχει πρόσβαση και στις πληροφορίες δυναμικής εκτέλεσης του προγράμματος ενώ ο gcc μπορεί μόνο στατικά να ελέγξει τον κώδικα.
Ηθικό δίδαγμα: οι γλώσσες δε μπορούν να συγκριθούν με κριτήριο την ταχύτητα, μόνο οι μεταγλωττιστές τους μπορούν.
Η προηγούμενη πρόκληση είχε ως στόχο την ανακάλυψη ενός τρόπου για να ανοίξει η θήκη μέσα στην οποία βρίσκεται ένας πρότυπος RISC επεξεργαστής, μέσω της μελέτης του emulator του.
Καταρχάς, ο emulator περιείχε συνολικά τρία αρχεία: το εκτελέσιμο risc-emu, το change.txt και το log.txt. Παρ' όλο που τα δύο τελευταία αρχεία έχουν .txt κατάληξη, κάθε άλλο παρά text είναι! Θα μπορούσαμε να τα αγνοήσουμε τελείως αλλά για να υπάρχουν εκεί κάποιο ρόλο παίζουν... Επιπλέον, δεν αισθάνεστε την ανάγκη να ικανοποιήσετε την περιέργεια σας; Τι άραγε κρύβουν τα αρχεία αυτά;
Μια προσεκτική παρατήρηση των στοιχείων μπορεί να φέρει στην επιφάνεια τέσσερα σημεία που οδηγούν στη λύση:
1.
Τα αρχεία έχουν κατάληξη .txt. Αν και τα ίδια δεν αποτελούνται από κείμενο, πιθανότατα να έχουν κάποια σχέση με κείμενο. Βέβαια, ίσως οι καταλήξεις να είναι εντελώς παραπλανητικές {δαιμονικό γέλιο ακούγεται στο υπόβαθρο} :)
2.
Τα αρχεία έχουν ακριβώς το ίδιο μέγεθος. Αυτό είναι ισχυρό στοιχείο πως σχετίζονται μεταξύ τους έμμεσα ή άμεσα.
3.
Αν συνδυάσουμε τα ονόματα των δύο αρχείων λαμβάνουμε τη λέξη changelog η οποία είναι ένα αρκετά κοινό αρχείο που ακολουθεί προγράμματα. Το γεγονός αυτό ενισχύει την άποψη πως τα δύο αρχεία συνδέονται μεταξύ τους. Το θέμα είναι πως υπάρχουν άπειροι τρόποι να συνδυαστούν δύο αρχεία!
4.
Αν προσέξετε το κείμενο της πρόκλησης, ο emulator ονομάζεται "RISC-emu v0.42rox". Η ύποπτη λέξη εδώ είναι το rox το οποίο είναι το ανάποδο του xor...
Πιστεύω πως τώρα πια το μυστήριο αρχίζει να ξεδιαλύνει. Αν εφαρμόσετε το δυαδικό τελεστή xor, byte προς byte μεταξύ των δύο αρχείων, θα καταλήξετε στο εξής:
RISC-emu Changelog -------------------- v0.42 ------ - Preliminary support for sorting rom module authentication scheme. The random values are stored at registers 0x90, 0x91, 0x92 after startup. - Added support for the "random reg" instruction v0.41 ----- - Added Support for the new "swap reg1,reg2" instruction (opcode 0x82) - Preliminary support for the "random reg" instruction v0.40 ------ - The CPU architecture has changed significantly so this version is an almost complete rewrite. *ram 1024 bytes, *registers 256, 4-bytes each *The instruction size is now 4 bytes.
Οι πιο σημαντικές πληροφορίες που μας δίνει το παραπάνω changelog είναι ότι ο επεξεργαστής έχει μέγεθος εντολών 4 bytes και εφόσον πρόκειται για RISC αρχιτεκτονική αυτό ισχύει για όλες τις εντολές. Επίσης μαθαίνουμε ότι υπάρχει μια εντολή swap με opcode 0x82 και μια εντολή random reg με άγνωστο opcode. Τέλος στους καταχωρητές 0x90, 0x91 και 0x92 αρχικά τοποθετούνται τυχαίες τιμές που πρέπει να ταξινομήσουμε (sorting rom module authentication scheme).
Αν τρέξουμε το πρόγραμμα μερικές φορές μας ζητάει να ταξινομήσουμε τρεις αριθμούς κάθε φορά:
$ ./risc-emu Welcome to Skynet. Please sort: 975 $ ./risc-emu Welcome to Skynet. Please sort: 396
Για να το καταφέρουμε αυτό θα πρέπει να φτιάξουμε ένα πρόγραμμα στον κώδικα μηχανής του συγκεκριμένου RISC επεξεργαστή. Το βασικό μας πρόβλημα είναι ότι δεν ξέρουμε καν ποιο είναι το σετ εντολών του επεξεργαστή! Το μόνο που μπορούμε να κάνουμε είναι να το βρούμε αναλύοντας τον εξομοιωτή.
Αν φορτώσουμε το εκτελέσιμο στον ht και κάνουμε μια βόλτα στο .text section θα παρατηρήσουμε ότι τα πράγματα δεν είναι και τόσο καλά.
|| ....... ;************************************************************** || ....... ; section 13 <.text> || ....... ; virtual address 08048464 virtual size 000004b8 || ....... ; file offset 00000464 file size 000004b8 || ....... ;************************************************************** || ....... mov eax, 0d6b4dc0bh || 804846a mov cl, 0a5h || 804846c add eax, 493d0701h || 8048471 fcom double ptr [ecx+5dh] || 8048474 cmp eax, 5d51d6d9h || 8048479 add al, 3 || 804847b cmp eax, 5d51d041h || 8048480 mov ebp, 0aaaaaa2ah
Οι παραπάνω εντολές δεν είναι του είδους που θα περίμενε κάποιος σε ένα τέτοιο πρόγραμμα. Και το entry point που είναι χαμένο; Επιλέγοντας το mode elf/header στον ht βρίσκουμε ότι το entry point είναι στη διεύθυνση 0x80489ea. Χμμ... ελέγχοντας τη διεύθυνση, με έκπληξη διαπιστώνουμε πως δεν ανήκει σε κανένα section!!!
Sections:
Idx Name Size VMA LMA File off Algn
...
11 .text 000004b8 08048464 08048464 00000464 2**2
CONTENTS, ALLOC, LOAD, CODE
12 .fini 0000001b 0804891c 0804891c 0000091c 2**2
CONTENTS, ALLOC, LOAD, READONLY, CODE
13 .rodata 00000010 08048938 08048938 00000938 2**2
CONTENTS, ALLOC, LOAD, READONLY, CODE
14 .data 000000a4 08049960 08049960 00000960 2**5
CONTENTS, ALLOC, LOAD, DATA
...
To κοντινότερο section είναι το .rodata το οποίο όμως τελειώνει αρκετά πριν το entry point, στη διεύθυνση 0x8048947. Τι γίνεται εδώ;
Θυμηθείτε πως για το φόρτωμα του προγράμματος βασική δομική μονάδα δεν είναι το section αλλά το segment. Με άλλα λόγια, δεν φορτώνονται sections αλλά segments που μπορούν να περιέχουν παραπάνω από ένα sections. Για το risc-emu η λίστα με τα segments είναι (με objdump -p):
Program Header:
PHDR off 0x00000034 vaddr 0x08048034 paddr 0x08048034 align 2**2
filesz 0x000000c0 memsz 0x000000c0 flags r-x
INTERP off 0x000000f4 vaddr 0x080480f4 paddr 0x080480f4 align 2**0
filesz 0x00000013 memsz 0x00000013 flags r--
LOAD off 0x00000000 vaddr 0x08048000 paddr 0x08048000 align 2**12
filesz 0x00000948 memsz 0x00000948 flags rwx
LOAD off 0x00000960 vaddr 0x08049960 paddr 0x08049960 align 2**12
filesz 0x000001c0 memsz 0x000001c4 flags rwx
DYNAMIC off 0x00000a08 vaddr 0x08049a08 paddr 0x08049a08 align 2**2
filesz 0x000000c8 memsz 0x000000c8 flags rw-
NOTE off 0x00000108 vaddr 0x08048108 paddr 0x08048108 align 2**2
filesz 0x00000020 memsz 0x00000020 flags r--
Το πρώτο load segment είναι το code segment και το δεύτερο το data segment. Και πάλι το entry point δε φαίνεται να ανήκει σε κανένα segment!
Το κλειδί στην όλη υπόθεση είναι το πεδίο align, με τιμή 2^12= 0x1000 (μια σελίδα). Η τιμή αυτή μας λέει ταυτόχρονα τρία πράγματα:
1.
Τo segment μπορεί να φορτωθεί μόνο σε κομμάτια πολλαπλάσια των 0x1000 bytes.
2.
Τo segment μπορεί να φορτωθεί μόνο από file offsets πολλαπλάσια των 0x1000 bytes.
3.
Το segment μπορεί να τοποθετηθεί μόνο σε εικονικές διευθύνσεις πολλαπλάσιες των 0x1000 bytes.
Αν το data segment αρχίζει από ένα άλλο σημείο μιας σελίδας τότε φορτώνεται όλη η σελίδα στην οποία ανήκει η αρχή του data segment και έτσι ίσως φορτωθεί ένα μέρος από το τέλος του code segment. Επίσης σε περίπτωση που το text segment δεν τελειώνει σε όρια σελίδας τότε πάλι φορτώνεται όλη η σελίδα στην οποία ανήκει και επομένως ίσως φορτωθεί και ένα μέρος από την αρχή του data segment. Αυτή η τελευταία παρατήρηση είναι ο λόγος που το πρόγραμμα μας με το άφαντο entry point λειτουργεί. Το παρακάτω σχήμα ίσως ξεκαθαρίσει λίγο τα πράγματα:
Τα δύο segments αντιστοιχούνται σε δύο διαφορετικά σημεία της εικονικής μνήμης αλλά υπάρχουν μόνο μια φορά στη φυσική μνήμη. Έτσι η διεύθυνση 0x80489ea (entry point) έχει τα ίδια δεδομένα με τη διεύθυνση 0x80499ea η οποία ανήκει στο data segment! Ουσιαστικά το entry point δείχνει σε κώδικα που βρίσκεται μέσα στο data segment στο αρχείο αλλά έχει φορτωθεί παρέα με το code segment στη μνήμη. Πολύ μπέρδεμα η όλη υπόθεση... ελπίζω να βγάλατε άκρη τελικά ;)
Για να δούμε τι υπάρχει στο entry point αρκεί λοιπόν να πάμε με τον ht στη διεύθυνση 0x80499ea. Εκεί, όμως, δε θα δούμε εντολές διότι ο ht δεν επεξεργάζεται τα bytes που βρίσκονται στο .data section, αφού θεωρεί (δίκαια) πως δε περιέχουν κώδικα. Για να αναλύσει τη συγκεκριμένη διεύθυνση θα πρέπει να δηλώσουμε ότι όντως εκεί υπάρχει κώδικας. Αρκεί στο mode elf/sections headers να επιλέξουμε to section .data και να αλλάξουμε το πεδίο flags ώστε το flag executable να είναι 1 (πατώντας F4 όταν είμαστε στα flags μπαίνουμε σε edit mode). Τώρα στο elf/image θα έχει αναλυθεί και ο κώδικας στο entry point:
|| 80499ea mov ecx, 4b8h || 80499ef mov eax, 8048464h || 80499f4 xor byte ptr [eax], 55h || 80499f7 inc eax || 80499f8 dec ecx || 80499f9 jnz 80499f4h || 80499fb jmp 8049464h || 8049a00 add [eax], al || 8049a02 add [eax], al
Ο κώδικας είναι πολύ απλός: αρχίζοντας από τη διεύθυνση 0x8048464 και για τα επόμενα 0x4b8 bytes, το κάθε byte (b) αντικαθίσταται με το (b xor 0x55). Πρόκειται για έναν στοιχειώδη αλγόριθμο κρυπτογράφησης. Η διεύθυνση 0x8048464 (όπως και η διεύθυνση 0x8049464) είναι η αρχή του .text section και η τιμή 0x4b8 το μήκος του section. Αυτός είναι και ο λόγος που τα περιεχόμενα του .text δεν έβγαζαν κάποιο νόημα όταν τα εξετάσαμε στην αρχή.
Από εδώ και πέρα υπάρχουν δύο τρόποι για να προχωρήσουμε. Ο πρώτος είναι να "παγώσουμε" το πρόγραμμα αμέσως μετά την αποκρυπτογράφηση και να αποθηκεύσουμε την εικόνα του σε κάποιο αρχείο (βλέπε προηγούμενο άρθρο Packed Executables - Συμπιεσμένα Εκτελέσιμα). Αυτό μπορεί να επιτευχθεί χρησιμοποιώντας το gdb, με την τοποθέτηση ενός breakpoint στη διεύθυνση 0x80489fb. Αφού "χτυπήσει" το breakpoint μπορούμε με την εντολή dump να αποκτήσουμε την εικόνα της μνήμης του προγράμματος.
Επειδή ο αλγόριθμος κρυπτογράφησης είναι εξαιρετικά απλός, μπορούμε με κάποιο πρόγραμμα ή hex editor να αποκρυπτογραφήσουμε μόνοι μας το .text section. Αν θέλουμε να μπορεί να εκτελείται το πρόγραμμα, δε θα πρέπει να αμελήσουμε να διορθώσουμε το entry point η τουλάχιστον να αδρανοποιήσουμε τον αλγόριθμο κρυπτογράφησης (πχ αλλάζοντας το κλειδί από 0x55 σε 0x00).
Από εδώ και πέρα μένει η ανάλυση του κώδικα που είναι το πιο χρονοβόρο και κουραστικό μέρος. Δε θα αναφερθώ περισσότερο σε αυτή διότι στηρίζεται σε μεγάλο βαθμό στην εμπειρία του αναλυτή. Μερικές συμβουλές μπορείτε να βρείτε εδώ[7]. To μόνο περίεργο που μπορεί να συναντήσετε είναι το γεγονός ότι η δομή ελέγχου switch υλοποιείται σε χαμηλό επίπεδο (από τον gcc) με εμφωλευμένες δομές if, ακολουθώντας τη λογική της δυαδικής αναζήτησης. Για παράδειγμα το:
![[IMG]](/kennedy.gemi.dev/35/img/mem.png){kind=link}
switch(x) {
case 1: ...; break;
case 2: ...; break;
case 3: ...; break;
case 4: ...; break;
case 5: ...; break;
case 6: ...; break;
default: ...; break;
}
μπορεί να μεταγλωττιστεί σα να είχατε γράψει κώδικα της μορφής:
if (x<4) {
if (x<=2) {
if (x==1) ...;
if (x==2) ...;
}
else /* x==3 */
...;
}
else if (x<=6)
if (x<=5) {
if (x==4) ...;
if (x==5) ...;
}
else /* x==6 */
...;
}
else /* default */
...;
O επεξεργαστής έχει εντολές των 4 bytes με το byte 0 να είναι το opcode. Οι διαθέσιμες εντολές είναι:
--------------------------------------------------------------------------------
\ Opcode Περιγραφή Όνομα
HALT 0x00 halt
ADD 0x01 reg{b1} = reg{b2} + reg{b3}
LOADIL 0x02 low word(reg{b1}) = (b2b3)
LOADIH 0x03 high word(reg{b1}) = (b2b3)
STORE 0x04 mem{(b1b2)} = reg{b3}
LOAD 0x05 reg{b3} = mem{(b1b2)}
INDSTORE 0x06 mem{reg{b1} + reg{b2}} = b3
INDLOAD 0x07 b3 = mem{reg{b1} + reg{b2}}
BE 0x08 if (reg{b1} == reg{b2}) ip += 4 * b3
BNE 0x09 if (reg{b1} != reg{b2}) ip += 4 * b3
BU 0x0A ip += 4 * (b1b2)
BR 0x0B ip += reg{b1}
PRINT 0x0C τύπωσε τα δεδομένα με αρχή τη θέση μνήμης (b1b2) ως δεκαεξαδικό, χαρακτήρα η συμβολοσειρά (b3=0,1,2)
SETLT 0x0D if (reg{b2} < reg{b3}) reg{b1} = 1; else reg{b1} = 0;
SWAP 0x82 reg{b1} <=> reg{b2}
RANDOM 0xFF reg{b1} = random(0,9)
--------------------------------------------------------------------------------
όπου reg[i]: το περιεχόμενο του καταχωρητή i, mem[i]: το περιεχόμενο της θέσης μνήμης i, (ij): η λέξη (16-bit) που δημιουργείται από τα bytes i και j με i το λιγότερο σημαντικό byte, ip: δείκτης για την επόμενη εντολή που θα εκτελεστεί, bi: το byte i της τρέχουσας εντολής.
Για να ταξινομήσουμε τους τρεις αριθμούς ένας απλός αλγόριθμος είναι:
if (r91 < r90) swap(r90, r91); if (r92 < r90) swap(r90, r92); if (r92 < r91) swap(r91, r92);
δηλαδή στη γλώσσα του δικού μας RISC:
setlt r9,r91,r90 be r0,r0,+1 swap r91,r90 setlt r9,r92,r90 be r9,r0,+1 swap r92,r90 setlt r9,r92,r91 be r9,r0,+1 swap r92,r91
Αρκεί να σώσουμε το δυαδικό κώδικα σε ένα αρχείο και να το φορτώσουμε στον εξομοιωτή με risc-emu <αρχείο>. Βέβαια, μην περιμένετε ο εξομοιωτής να επιβεβαιώσει την ορθότητα της λειτουργίας του προγράμματος... όπως λέει και το changelog η υποστήριξη για το συγκεκριμένο χαρακτηριστικό δεν είναι πλήρης :)
Αυτή τη φορά έλαβα μόνο μια απάντηση, η οποία όμως ήταν πραγματικά αξιόλογη!
Συγχαρητήρια, λοιπόν, στον Γιώργο Πρέκα για τη λύση[8] του !
8: ./prekas_geo-rce2sol.tar.gz
Από το email του Γιώργου: "Η λύση αποτελείται από τα εξής αρχεία: changelog.txt, το αποκρυπτογραφημένο changelog του εξομοιωτή. geo.c, το πρόγραμμα που αποκρυπτογραφεί το changelog.txt αρκεί να υπάρχουν στον κατάλογο εκτέλεσής του τα αρχεία change.txt και log.txt. newprg, ο αποκρυπτογραφημένος εξομοιωτής. Φαίνεται πως κάποιο λάθος έκανα με την εντ��λή dump του gdb και το αρχείο περιέχει δύο images: Ένα αποκρυπτογραφημένο και ένα κρυπτογραφημένο. Δεν το διόρθωσα γιατί φοβόμουν ότι μετά θα χάνονταν όλα τα σχόλια που είχα γράψει στον ht. newprg.ht*, αρχεία για τον ht. rom, αποτελεί ένα rom module, του οποίου η εκτέλεση μπορεί να εξομοιωθεί με την εντολή ./risc-emu rom, και αφού πρώτα ταξινομήσει τις τιμές των καταχωρητών 0x90, 0x91, 0x92, εκτελεί έναν ατέρμονα βρόχο, ώστε να μπορέσει τελικά να ανοιχτεί η περιβόητη θήκη. Σημείωση: Από όσα κατάλαβα, για να θεωρηθεί ένα rom module έγκυρο πρέπει να ταξινομήσει τους συγκεκριμένους καταχωρητές. Αυτό δεν το ελέγχει ο εξομοιωτής, αν και έπειτα αφού αποκρυπτογράφησα το changelog.txt, κατάλαβα πως δεν είναι ολοκληρωμένη η υποστήριξη της συγκεκριμένης λειτουργίας."
Τον source κώδικα της πρόκλησης και τη δική μου λύση μπορείτε να την κατεβάσετε από εδώ[9].
Ευτυχώς ή δυστυχώς, αυτό το άρθρο είναι μάλλον το τελευταίο της σειράς οπότε δεν υπάρχει επόμενη πρόκληση. Πάντως, όσοι πραγματικά ενδιαφέρονται για γρίφους τέτοιου είδος δεν έχουν παρά να ψάξουν στο internet όπου θα βρουν αρκετές σχετικές σελίδες. Το μόνο αρνητικό στην όλη υπόθεση είναι πως οι περισσότερες από αυτές ασχολούνται με εκτελέσιμα σε περιβάλλον Win32. Καλή συνέχεια!