Μοντελοποίηση και επαλήθευση κινητών συστημάτων με τεχνικές αλγεβρικών προδιαγραφών

Abstract

The scope of the thesis is the modeling and verification of mobile systems using algebraic specification techniques. Α mobile system is a computing and/or a communication system where the notion of location of its components is of major criticality and its change affects system’s behavior. Due to the special characteristics of such systems, and the rapid proliferation of mobile devices, networks and services, the requirements for reliability, security and functionality has led to the development of formal methods for mobile systems. Formal methods, which are techniques, languages and tools based on mathematics, provide an unambiguous, strict mathematical description or specification which is used for effective design, analysis and verification of desired properties of the system. An important branch of formal methods are algebraic specification languages with a rigorous basis on mathematical logical systems or combinations of them. Such a language is CafeOBJ, an executable, new generation algebraic specification language, member of the OBJ family languages. Its main characteristic that differentiates it from other formalisms is its direct support to behavioural specification paradigm since it embeds special hidden sorts and behavioural operators in its syntax. Behavioural specification is based on hidden algebra and supports an object oriented style of algebraic specification. It also supports specification of distributed concurrent systems as abstract state machines and verification of safety properties of them through theorem proving techniques such as simultaneous induction and coinduction. Based on the above specification techniques, MobileOBJ is proposed, that is an algebraic framework for specification and verification of mobile systems. The specification of the mobile system, protocol or procedure consists of specification modules which describe either data types as visible sorts, or the system as a Mobile Observational Transition System, a kind of behavioural object. Based on this specification, verification of properties of the mobile system using theorem proving techniques is feasible. Since the transitions of the system are specified as equations makes the method easier to read, understand and learn than other related methods, which prerequisite deeper knowledge of theorem proving. Next, the integration of Mobile Observational Transition Systems with Timed and Hybrid Observational Transition Systems is performed to capture not only the discrete but also the continuous characteristics of mobiles systems, such as timing constraints, resource scarcity or distance. To demonstrate the applicability and practicality of the framework, a number of case studies are conducted. Security aspects of mobile systems are of major importance, and it was inevitable to take them into account. Authentication protocols for sensor networks and multicasting settings have been formally specified, and safety properties of them have been verified. In the last section of the thesis, a protocol algebra is proposed inspired by the module algebra and the hierarchical object composition technique based on hidden algebra. The preservation of some properties of the component protocols to the composed protocol for some operators of the algebra has been proved. Finally, a number of applications of the algebra are presented.

Αντικείμενο της διατριβής αποτελεί η μοντελοποίηση και η επαλήθευση κινητών συστημάτων με χρήση τεχνικών αλγεβρικών προδιαγραφών. Με τον όρο κινητά συστήματα αναφέρονται τα συστήματα υπολογισμού ή/και επικοινωνιών στα οποία η έννοια της θέσης των αντικειμένων αποτελεί κρίσιμο χαρακτηριστικό τους και η μεταβολή της επηρεάζει καθοριστικά τη συμπεριφορά τους. Λόγω της ιδιαιτερότητας των συστημάτων αυτών, και εξαιτίας τη ραγδαίας εξάπλωσης της χρήσης των κινητών δικτύων και υπηρεσιών, οι απαιτήσεις για αξιοπιστία, ασφάλεια και λειτουργικότητα έχουν οδηγήσει στην ανάπτυξη τυπικών μεθόδων προσανατολισμένων στα κινητά συστήματα. Οι τυπικές μέθοδοι, οι οποίες είναι τεχνικές, γλώσσες και εργαλεία με ισχυρό μαθηματικό υπόβαθρο, μας δίνουν τη δυνατότητα μιας αυστηρής, μαθηματικά ορισμένης, χωρίς ασάφειες, περιγραφής ή προδιαγραφής των συστημάτων, η οποία χρησιμοποιείται για το σχεδιασμό τους, την ανάλυση, και την επαλήθευση επιθυμητών ιδιοτήτων τους. Ένας πολύ σημαντικός κλάδος των τυπικών μεθόδων είναι οι αλγεβρικές γλώσσες προδιαγραφών, οι οποίες έχουν ως μαθηματικό υπόβαθρο τους μαθηματικά λογικά συστήματα ή συνδυασμούς τους. Μια τέτοια εκτελέσιμη αλγεβρική γλώσσα προδιαγραφών νέας γενιάς, απόγονος των γλωσσών OBJ, είναι η CafeOBJ. Το βασικότερο χαρακτηριστικό της γλώσσας αυτής που τη διακρίνει από αντίστοιχους φορμαλισμούς, είναι η άμεση υποστήριξη που παρέχει στη συμπεριφοριακή προδιαγραφή με την ενσωμάτωση στο συντακτικό της ειδικών τύπων και τελεστών. Η συμπεριφοριακή προδιαγραφή, η οποία έχει τις βάσεις της στην άλγεβρα με κρυμμένους τύπους, υποστηρίζει την αλγεβρική προδιαγραφή με αντικείμενα ή αφηρημένες μηχανές καταστάσεων, δίνοντας τη δυνατότητα περιγραφής κατανεμημένων, δυναμικών συστημάτων με ταυτόχρονες διεργασίες. Παράλληλα, με χρήση τεχνικών επαλήθευσης που βασίζονται σε αυτή, μας δίνει τη δυνατότητα απόδειξης ιδιοτήτων ασφαλείας των συστημάτων που έχουν προδιαγραφεί. Με βάση τα παραπάνω, προτείνεται το πλαίσιο προδιαγραφής και επαλήθευσης κινητών συστημάτων MobileOBJ. Η προδιαγραφή του κινητού συστήματος, πρωτοκόλλου ή διαδικασίας, αποτελείται από τη σύνθεση τεμαχίων προδιαγραφών (specification modules) τα οποία περιγράφουν είτε τους τύπους δεδομένων, είτε το σύστημα σαν ένα Κινητό Παρατηρήσιμο Σύστημα Μετάβασης, ένα είδος συμπεριφοριακού αντικειμένου. Στη συνέχεια με βάση αυτή την προδιαγραφή και κάνοντας χρήση τεχνικών απόδειξης θεωρήματος είναι δυνατή η επαλήθευση ιδιοτήτων της. Το ότι ο δυναμικός χαρακτήρας του συστήματος προδιαγράφεται με εξισώσεις, κάνει τη μέθοδο αυτή καλύτερα κατανοητή και ευκολότερη από αντίστοιχες μεθόδους που προαπαιτούν βαθύτερη γνώση των τεχνικών απόδειξης θεωρήματος. Στη συνέχεια, επεκτείνοντας την αρχική προσέγγιση, δίνεται η δυνατότητα προδιαγραφής και φυσικών, συνεχών – πέραν των διακριτών – χαρακτηριστικών των κινητών συστημάτων, όπως ο χρόνος και η απόσταση. Τα παραπάνω επιτυγχάνονται με την ενοποίηση των Κινητών Παρατηρήσιμων Συστημάτων Μετάβασης με τα Χρονικά και τα Υβριδικά Παρατηρήσιμα Συστήματα Μετάβασης. Η εφαρμογή της μεθόδου παρουσιάζεται μέσα από τη μελέτη μιας σειράς περιπτώσεων που αντιστοιχούν σε συστήματα και πρωτόκολλα. Τα ζητήματα ασφαλείας για ένα κινητό σύστημα είναι μεγάλης κρισιμότητας και γι’ αυτό το λόγο δεν θα μπορούσαν να παραβλεφθούν. Στα πλαίσια αυτά έχουν προδιαγραφεί και επαληθευθεί πρωτόκολλα ασφαλείας για ασύρματα δίκτυα αισθητήρων και πολύ-εκπομπής. Στο τελευταίο κομμάτι της διατριβής προτείνεται μια άλγεβρα πρωτοκόλλων για την επαναχρησιμοποίηση και σύνθεση πολύπλοκων πρωτοκόλλων από στοιχειώδη με βάση τις τεχνικές ιεραρχικής σύνθεσης αντικειμένων με χρήση συμπεριφοριακών αλγεβρικών προδιαγραφών και της άλγεβρας τεμαχίου προδιαγραφής. Αποδεικνύεται η διατήρηση ιδιοτήτων των στοιχειωδών πρωτοκόλλων στα σύνθετα πρωτόκολλα για τελεστές της άλγεβρας, και παρουσιάζονται παραδείγματα εφαρμογών της.