Property driven program slicing and watermarking in the abstract interpretation framework

Abstract

Interpretation theory formalizes the conservative approximation of the semantics of hardware and software computer systems. Abstract Interpretation approximates semantics according to some property of choice, this is formalized by choosing an appropriate abstract domain to use as abstraction of the semantics. A great variety of abstract domains can be formulated and the choice of domain off ers a trade-o ff between precision and computational complexity. This thesis illustrates the instantiation of the Abstract Interpretation in the following scenarios, Program slicing, Watermarking relational databases, Watermarking program source code. In this dissertation, a further refi nement of the traditional slicing technique, called property driven program slicing is proposed by combining it with a static analysis in Abstract Interpretation framework. Very often, we are interested on a specific property of the variables in the slicing criterion, rather values. This is the case for instance, when dealing with non-interference in language-based security, where abstractions come into play in modeling the observational power of attackers. Therefore, when performing slicing, the abstract properties of variables and the abstract dependencies come into account. This approach of slicing, is not simply a pure generalization of a well-known technique, but provides new insights in links existing between di fferent computer science fields. Strengthening the ownership rights on outsourced relational database is very important in todays internet environment. In this context, the thesis introduces a distortion free watermarking technique that strengthen the verifi cation of integrity of the relational databases by using a public zero-distortion authentication mechanism based on a Abstract Interpretation framework. With the increasing amount of program source code which is distributed in the web, software ownership protection and detection is becoming an issue. In this scenario, a public key software watermarking (asymmetric watermarking) scheme is proposed which is similar in spirit to zero-knowledge proofs. The proposed approach of watermarking a source code is seen as an alternative to encryption as a way to support software authentication rather a tool for copyright protection.

L'interpretazione astratta è una teoria che formalizza l'approssimazione conservativa della semantica di sistemi informatici hardware e software, focalizzandosi su alcune proprietà, che espresse mediante opportune strutture algebriche (domini astratti) possono essere calcolate in modo corretto (anche se non completo). Una grande varietà di domini astratti può essere elaborata, a aseconda dei contesti di applicazione, e con scelta dei domini astratti è possibile modulare in modi diversi precisione e complessità computazionale. Questa tesi considera l'applicazione di tecniche di Interpretazione Astratta in tre diversi scenari: Program slicing; Watermarking di database relazionali; Watermarking del codice sorgente di programmi. Relativamente al Program slicing, viene proposto un raffinamento delle tecniche tradizionali già presenti in letteratura. Molto spesso, siamo interessati a una specifica proprietà delle variabili in un criterio di slicing, piuttosto che ai suoi effettivi valori. Questo è il caso, ad esempio, quando si analizza la non-interferenza in language-based security, dove le astrazioni entrano in gioco per modellare il potere osservativo degli attaccanti. In questo scenario, lo slicing tiene in considerazione le proprietà astratte delle variabili e le dipendenze astratte. Questo approccio allo slicing, non è solo la generalizzazione della tecnica tradizionale, ma offre nuovi spunti nelle relazioni tra diverse aree di ricerca dell'informatica. Un secondo scenario di applicazione delle tecniche di Interpretazione Astratta è la progettazione di watermarking di database relazionali, la cui rilevanza è legata al fatto che in Internet è molto importante preservare i diritti di proprietà nei database relazionali mantenuti in outsourcing. In tale ambito, viene proposta una tecnica di watermarking senza distorsione, che migliora la verifica dell'integrità dei database relazionali utilizzando un meccanismo di autenticazione pubblica. L'ultimo scenario considerato è quello del Watermarking del codice sorgente di programmi: all'aumentare della quantità di codice sorgente distribuito sul web, la protezione e il rilevamento delle proprietà del software è diventata una questione importante. Nella tesi, viene presentato uno schema di watermarking software a chiave pubblica (watermarking asimmetrico), basato su tecniche di trasformazione che preservano la semantica, e che è simile nello spirito alle zero-knowledge proofs. L'approccio proposto si pone come un'alternativa alla cifratura e l'autenticazione software piuttosto che come uno strumento per la protezione del copyright.