Algorithmic techniques for detection and classification of digital objects

Abstract

In this PhD Thesis there have been studied the algorithmic techniques for the detection and classification of digital object. In the area of digital objects, this Thesis focuses mainly on the investigation of designing and proposing algorithmic techniques that detect and classify (in terms of indexing) a specific category of digital objects, the one of software, and more precisely the malicious software, providing finally an integrated algorithmic framework for protection against malicious software. Malicious authors, in order to avoid traditional detection methods, have developed highly sophisticated practices focusing on mutating their produced malicious samples, incorporating mutation engines that mutate the structure of the generated malicious samples (i.e., polymorphism and metamorphism). On the first development axis of this thesis, the research focuses on the design and the proposal of a mutation-tolerant graph-based representation of malicious software sample's behavior (behavioral graph) resulted from System-call Dependency Graphs, or, for short ScDG, a Directed Acyclic Graph produced through Dynamic Taint Analysis of the executed sample. So, in the first state we propose the Group Relation Graph, or, for short GrG, a Directed Weighted Graph that is an abstraction of ScDG resulting after grouping disjoint vertices of it, utilizing the property that system-calls can be merged into groups based on their similar functionality. Further, we extent this approach by proposing the Coverage Graph, or, for short CvG, where we investigating the dominating relations among the vertices of GrGs regarding the vertex weight and degree. Additionally, extending the potentials of the above graph-based representations, we also propose the Temporal Graphs, that actually depict the structural evolution of the previously proposed graphs (i.e., GrG and CvG) by depicting their structures through instances captured over specific periods. Among others, we propose a set of similarity metrics that utilize quantitative, relational and qualitative characteristics of the above graph-based representations of malicious software sample's behavior, utilizing them in order to experimentally evaluate the detection and classification potentials of our model. Moreover, since the usage of mobile devices exhibits a wide spread, dependently of te adoption of IoT, throughout this thesis, it has also been studied the development of graph-based algorithmic techniques that would integrate the overall algorithmic framework for protection against malicious software by investigating graph-based strategies for suppressing and finally avoiding potential pandemics caused by malware's spread. More precisely, we propose a set of graph-based techniques for modeling the topology of towns-planning, the node mobility patterns as also the propagation behavior, incorporating them to develop an algorithmic technique that defines the maximum permitted time required by a counter- measure to take effect removing the malware from an infected device (i.e., response time) in order to finally the pandemic spread. Finally, the precision of the proposed approach is tested throughout a series of repetitive (Monte Carlo) series of experiments of various epidemic models and set of factors that affect the malware's spread.

Σε αυτή τη διδακτορική διατριβή διερευνήθηκαν οι αλγοριθμικές τεχνικές για την ανίχνευση και τη κατάταξη ψηφιακών αντικειμένων. Στον τομέα των ψηφιακών αντικειμένων, η παρούσα εργασία επικεντρώνεται κυρίως στη μελέτη του σχεδιασμού και της περαιτέρω ανάπτυξης αλγοριθμικών τεχνικών ανίχνευσης και κατάταξης μιας συγκεκριμένης κατηγορίας ψηφιακών αντικειμένων, αυτής του λογισμικού και πιο συγκεκριμένα του κακόβουλου λογισμικού, δημιουργώντας εν τέλει ένα ολοκληρωμένο αλγοριθμικό πλαίσιο για την προστασία ενάντια σε αυτό. Οι δημιουργοί των κακόβουλων λογισμικών, προκειμένου να αποφύγουν τις καθιερωμένες μεθόδους ανίχνευσης, έχουν αναπτύξει ευφυείς τεχνικές που εστιάζουν στη μετάλλαξη των παραγόμενων κακόβουλων λογισμικών, ενσωματώνοντας μηχανισμούς μετάλλαξης που στόχο έχουν να τροποποιήσουν ριζικά τη δομή των παραγόμενων δειγμάτων. Ως εκ τούτου, στον πρώτο άξονα, η έρευνα επικεντρώνεται στο σχεδιασμό και την πρόταση μιας αναπαράστασης μέσω γραφήματος της συμπεριφοράς του δείγματος κακόβουλου λογισμικού (συμπεριφοριστικό γράφημα) ανθεκτικής σε μεταλλάξεις, η οποία προκύπτει από τα Γραφήματα Εξάρτησης Κλήσεων Συναρτήσεων Συστήματος (κατευθυνόμενα άκυκλα γραφήματα), τα οποία κατασκευάζονται αντλώντας πληροφορία από την εκτέλεση δυναμικής ανάλυσης του εκτελεσθέντος κακόβουλου λογισμικού. Έτσι, σε πρώτο επίπεδο, προτείνουμε το Γράφημα Συσχετίσεων Ομάδων (κατευθυνόμενο έμβαρο γράφημα) το οποίο προκύπτει έπειτα από ομαδοποίηση των κόμβων του γραφήματος Εξάρτησης Κλήσεων Συναρτήσεων Συστήματος, αξιοποιώντας την ιδιότητα ότι οι κλήσεις συναρτήσεων συστήματος μπορούν να συγχωνευθούν σε ομάδες ανάλογα με την ομοειδή λειτουργικότητά τους. Επιπρόσθετα, επεκτείνουμε αυτή την προσέγγιση προτείνοντας το Γράφημα Κάλυψης, όπου διερευνούμε τις ``σχέσεις κυριαρχίας" μεταξύ των κόμβων του γραφήματος Συσχετίσεων Ομάδων, αναφορικά με το βάρος και το βαθμό αυτών. Επιπλέον, επεκτείνοντας τις δυνατότητες των παραπάνω γραφημάτων προτείνουμε επίσης τα Χρονικά Μεταβαλλόμενα Γραφήματα, τα οποία απεικονίζουν τη δομική εξέλιξη των προτεινόμενων γραφημάτων (δηλ. Γραφήματα Συσχετίσεων Ομάδων και Γραφήματα Κάλυψης) απεικονίζοντας την εξέλιξη στη δομή τους μέσω στιγμιότυπων αυτών, τα οποία καταγράφονται ανα συγκεκριμένες περιόδους. Μεταξύ άλλων, προτείνουμε ένα σύνολο μετρικών ομοιότητας, όπου αξιοποιούνται τα ποσοτικά, σχεσιακά και ποιοτικά χαρακτηριστικά των παραπάνω γραφημάτων αναφορικά με τη συμπεριφορά των κακόβουλων λογισμικών, αξιοποιώντας αυτές τις μετρικές για τη μετέπειτα αποτίμηση των δυνατοτήτων ανίχνευσης και κατάταξης των προταθέντων μοντέλων. Επιπλέον, δεδομένου ότι η χρήση των φορητών συσκευών παρουσιάζει ευρεία εξάπλωση, κατά την εκπόνηση της παρούσας διατριβής μελετήθηκε η ανάπτυξη αλγοριθμικών τεχνικών βασισμένων σε γραφήματα, οι οποίες θα ολοκληρώνουν το ευρύτερο αλγοριθμικό πλαίσιο προστασίας ενάντια στο κακόβουλο λογισμικό, με τη διερεύνηση στρατηγικών βασισμένων σε γραφήματα για την καταστολή και περαιτέρω αποφυγή εν δυνάμει πανδημικών φαινομένων που θα προκύψουν από την εξάπλωση του κακόβουλου λογισμικού. Πιο συγκεκριμένα, προτείνουμε μια σειρά τεχνικών για τη μοντελοποίηση της τοπολογίας του πολεοδομικού σχεδιασμού, των μοτίβων κίνησης των φορητών συσκευών καθώς επίσης και της συμπεριφοράς μετάδοσης (αναφορικά με το ακολουθούμενο επιδημιολογικό μοντέλο), συντονίζοντας τα μοντέλα αυτά στην πλαισίωση μιας αλγοριθμικής τεχνικής που θα καθορίζει τον μέγιστο επιτρεπόμενο χρονικό όριο που απαιτείται από ένα αντίμετρο προστασίας προκειμένου να απομακρυνθεί το κακόβουλο λογισμικό από μια μολυσμένη συσκευή (χρόνος απόκρισης), ώστε τελικά να αποφευχθεί η πανδημία. Τέλος, η ευρύτερη απόδοση της προτεινόμενης προσέγγισης παρουσιάζεται μέσα από μια σειρά επαναλαμβανόμενων πειραμάτων (Monte Carlo) ακολουθώντας διαφορετικά επιδημιολογικά μοντέλα, λαμβάνοντας παράλληλα υπόψη και ένα σύνολο παραγόντων που επηρεάζουν την εξάπλωση του κακόβουλου λογισμικού.