SimDroidUI : a new method of UI-based Clustering of Android applications

With the growing popularity of smartphones, and consequently of appli- cation stores, a method for comparing Android applications is needed. In response, researchers proposed various approaches to capture application similarity by comparing source code. Because they rely on calculating dif- ferences between code used by the developers, such approaches are good for detecting pirated applications, code reuse, and for bug fixing. However, they are ineffective where a comparison of just the front-end of the application is needed; this is required to compare applications with similar usage and similar User Interface (UI), even with different code structure. A method for analyzing application front-end has been proposed in previous works, but this method often needs to execute applications in a remote emulator. In light of this, we propose a new approach for similarity analysis among Android applications by comparing the application front-end without ex- ecuting Android application. The key intuition is that we can consider application UIs as hierarchies of view elements. This assumption allows us to compare application front-ends by comparing sequences of elements. Two applications can be considered as much visually similar as many part these hierarchies they have in common. Moreover, we can improve our ap- proach by grouping together applications with the same UI and by obtaining a summary of the common UI elements. As a consequence, the operation of clustering brings to quickly identifying series of applications similar to a given one without comparing a new sample with the whole database. We experimentally demonstrate that our approach builds ”clusters” that are good representation of UI similarity. Our results show that SimDroid-UI is able to identify application similarity more quickly and effectively than previous works. Finally, we prove that cluster created by SimDroid-UI tends to put together applications with the same type of usage for the final user, rather than similarity at source code level.

Negli ultimi anni siamo stati testimoni di una notevole diffusione di smart- phone e conseguentemente di numerosi negozi virtuali per la distribuzione di applicazioni Android. L’enorme quantità di applicazioni ormai esistente sui mercati rende nec- essario il ricorso a metodi sempre più evoluti per il loro confronto e la loro classificazione. Accanto al mercato ufficiale di Google Play sono sorti e si sono progressivamente diffusi numerosi mercati alternativi che mettono a disposizione degli utenti variegate applicazioni non facilmente controllabili. Questo solleva numerosi problemi di sicurezza e di difesa della proprietà in- tellettuale, poiché non è agevole individuare, tra le stesse, quelle malevole o quelle che violano i diritti d’autore. In letteratura esistono diversi metodi, basati sul confronto tra appli- cazioni Android, per fronteggiare tali problematiche. La maggior parte di essi analizza il codice sorgente. Tuttavia, nel tempo tali metodi hanno mostrato limiti e si sono rivelati inefficaci in relazione alla necessità di con- frontare le Interfacce Utente. Sui mercati sono infatti rinvenibili applicazioni che, pur apparendo graficamente simili, sono caratterizzate da codici sor- gente differenti tra loro. Attualmente esiste un metodo che compara le interfacce utente delle applicazioni basandosi esclusivamente sull’analisi di immagini e non sulla struttura delle interfacce; esso per di più richiede lunghi tempi di esecuzione. Il nostro approccio propone un nuovo ed efficiente metodo di misura della similarità tra due applicazioni Android che guarda la struttura dell’interfaccia utente e che risulta scalabile in caso di ampi database di applicazioni. L’idea sottostante a detto approccio è quella che una qualsiasi applicazione Android è rappresentata mediante una serie di layout proposti all’utente. Questi ul- timi sono paragonabili a degli alberi tra i quali sussiste un insieme di relazioni del tipo padre-figlio. Applicazioni con la stessa Interfaccia utente presenter- anno alberi simili. Ad esempio due applicazioni che presentano entrambe, in una schermata, una lista di campi testuali, saranno rappresentate da simili relazioni padre-figlio, dove i figli sono i campi testuali e il padre è l’oggetto che li raggruppa. Abbiamo esaminato lo stato dell’arte del tree mining, focalizzandoci sui migliori metodi di confronto tra alberi di elementi. Questi ricercano, all’interno di un database di alberi (chiamato foresta), le strutture ricor- renti, rappresentate da sotto-alberi. Due alberi, e dunque due applicazioni, risulteranno tanto più simili, quanti più sotto-alberi essi hanno in comune. Essendo la lista di pattern di una applicazione considerabile come insiemi di elementi, è stato possibile ricorrere alla Similarità di Jaccard, ben nota in letteratura, che esprime un valore oggettivo di similarità tra due insiemi. Più in dettaglio, con SimDroid-UI , abbiamo implementato un metodo di raggruppamento (clustering) di applicazioni Android basato sulla similarità di Jaccard. In sostanza, SimDroid-UI offre due funzionalità: (1) raggruppa un database di applicazioni rispetto alla loro similarità visiva e (2) ricerca le applicazioni più simili partendo da un nuovo campione. A partire dunque dai raggruppamenti creati, SimDroid-UI ricerca gli el- ementi simili rispetto ad una specifica applicazione, permettendo di ritrovare velocemente, all’interno di un ampio database di applicazioni, la lista delle applicazioni più simili al campione. La novità del nostro metodo sta nel fatto che, a differenza dei metodi di similarità già presenti in letteratura, non ha bisogno di confrontare ripetuta- mente le singole applicazioni con il nuovo campione, in quanto utilizza una rappresentazione tramite cluster che permette di individuare subito la parte del database contenente le applicazioni più simili. Abbiamo quindi confrontato SimDroid-UI con pHash e Androsim, due dei principali metodi di ricerca di applicazioni simili, utilizzando Puppet- droid, un progetto di analisi dinamica di malware Android. Esso si basa sulla comparazione visiva per simulare l’utilizzo umano di una applicazione Android e risulta tanto più accurato quanto più efficiente è il metodo di similarità utilizzato. I risultati sperimentali hanno dimostrato che il nostro metodo riesce a produrre gruppi di applicazioni che ben rappresentano la similarità delle singole applicazioni. Inoltre, i raggruppamenti si avvicinano alla divisione semantica che un utente fa rispetto alla tipologia di utilizzo. Abbiamo provato che SimDroid-UI è più efficace nella ricerca di applicazioni simili visivamente, confrontandolo con altri approcci esistenti in letteratura. In- fine, i test hanno evidenziato come il nostro metodo sia più veloce rispetto a quelli che non utilizzano tecniche di clustering e a quelli che necessitano dell’esecuzione dell’applicazione. Vero è che non esiste un metodo unico di calcolo dello similarità tra due applicazioni, ma quello che si sceglie di adottare è spesso il più funzionale allo scopo della ricerca. Il nostro metodo può infatti facilmente essere affiancato ai metodi già presenti, per fornire un valore di similarità tra due applicazioni da un diverso punto di vista. Riassumendo, i contributi originali di questa tesi sono i seguenti: > abbiamo proposto un nuovo metodo per valutare la similarità tra due applicazioni Android. > abbiamopropostounmetododiraggruppamentodiapplicazionibasato su similarità visiva; > abbiamo proposto un metodo di ricerca all’interno di un dataset effi- cace e scalabile; > abbiamo implementato il nostro approccio in SimDroid-UI , un tool che offre all’utente un servizio di ricerca di applicazioni simili tra loro; > abbiamo valutato sperimentalmente il sistema, dimostrando che i rag- gruppamenti creati sono validi e riescono a rappresentare le varie tipolo- gie di applicazioni presenti sul mercato.