Malware analysts often need to search large corpuses of obfuscated binaries for particular sequences of related instructions. The use of simple tactics, such as dead code insertion and register renaming, prevents the use of conventional, big-data search indexes. Current, state of the art malware detectors are unable to handle the size of the dataset due to their iterative approach to comparing files. Furthermore, current work is also frequently designed to act as a detector and not a search tool. I propose a system that exploits the observation that many data/control-flow relationships between instructions are preserved in the presence of obfuscations. The system will extract chains of flow-dependent instructions from a binary’s Program Dependence Graph (PDG). It will then use a representation of each chain as a key for an index that points to lists of functions (and their corresponding files). Analysts will be able to quickly search for instruction sequences by querying the index.

El texto completo de este trabajo no está disponible en el Repositorio Académico UPC por restricciones de la casa editorial donde ha sido publicado. / In the past decade, there has been an increasing need for semantic-aware data search and indexing in textual (structured and NoSQL) databases, as full-text search systems became available to non-experts where users have no knowledge about the data being searched and often formulate query keywords which are different from those used by the authors in indexing relevant documents, thus producing noisy and sometimes irrelevant results. In this paper, we address the problem of semantic-aware querying and provide a general framework for modeling and processing semantic-based keyword queries in textual databases, i.e., considering the lexical and semantic similarities/disparities when matching user query and data index terms. To do so, we design and construct a semantic-aware inverted index structure called SemIndex, extending the standard inverted index by constructing a tightly coupled inverted index graph that combines two main resources: a semantic network and a standard inverted index on a collection of textual data. We then provide a general keyword query model with specially tailored query processing algorithms built on top of SemIndex, in order to produce semantic-aware results, allowing the user to choose the results' semantic coverage and expressiveness based on her needs. To investigate the practicality and effectiveness of SemIndex, we discuss its physical design within a standard commercial RDBMS allowing to create, store, and query its graph structure, thus enabling the system to easily scale up and handle large volumes of data. We have conducted a battery of experiments to test the performance of SemIndex, evaluating its construction time, storage size, query processing time, and result quality, in comparison with legacy inverted index. Results highlight both the effectiveness and scalability of our approach. / This study is partly funded by the National Council for Scientific Research - Lebanon (CNRS-L), by the Lebanese American University (LAU), and the Research Support Foundation of the State of Sao Paulo ( FAPESP ). Appendix SemIndex Weighting Scheme We propose a set of weighting functions to assign weight scores to SemIndex entries, including: index nodes , index edges, data nodes , and data edges . The weighting functions are used to select and rank semantically relevant results w.r.t. the user's query (cf. SemIndex query processing in Section 5). Other weight functions could be later added to cater to the index designer's needs. / Revisión por pares

Αρχικά θα μελετήσουμε κάποιες έννοιες σχετικές με το δίκτυο της κινητής τηλεφωνίας και θα ασχοληθούμε πιο συγκεκριμένα με τα υποσυστήματα που μεταφέρουν τα γραπτά μηνύματα κινητής τηλεφωνίας. Κύριο μέλημά μας όμως αποτελεί η ανάλυση του τρόπου αποθήκευσης των μηνυμάτων σε συσκευές κινητής τηλεφωνίας και πιο συγκεκριμένα σε συσκευές που έχουν εγκατεστημένο το λειτουργικό σύστημα Android. Θα μελετήσουμε το λειτουργικό σύστημα Android και θα δούμε ποια είναι τα σημαντικότερα πλεονεκτήματά του, ώστε ένας χρήστης να επιλέξει το συγκεκριμένο λειτουργικό σύστημα για τη συσκευή του, αλλά και γιατί αποτελεί πλέον κυρίαρχο λειτουργικό σύστημα για την ανάπτυξη μικροεφαρμογών από τους προγραμματιστές. Ως προς το λειτουργικό Android θα αναλύσουμε εκτενέστερα τον τρόπο αποθήκευσης των γραπτών μηνυμάτων και θα δούμε πως το Android δομεί το κείμενο των μηνυμάτων και τις διάφορες πληροφορίες που παρέχονται από το ίδιο το δίκτυο της κινητής τηλεφωνίας. Θα αναλύσουμε τα σύντομα γραπτά μηνύματα κινητής τηλεφωνίας, γνωστά και ως sms, που είναι η υπηρεσία σύμφωνα με την οποία οι χρήστες ανταλλάσσουν αποκλειστικά κείμενο διατυπώνοντας συναισθήματα, σκέψεις, καθώς και σημαντικές πληροφορίες. Οι πληροφορίες αυτές αποθηκεύονται στη συσκευή κάθε χρήστη και κάθε συσκευή αποτελεί το μοναδικό οικιακό αποθηκευτικό μέσο σε όλο το δίκτυο της κινητής τηλεφωνίας. Οι πληροφορίες που αποθηκεύεται στα sms, αποτελεί σύνθετο πρόβλημα ανάλυσης, καθώς απαρτίζεται από ελλιπής προτάσεις, μεικτό περιεχόμενο ελληνικών και greeklish γραμμάτων, καθώς και συντομογραφίες που ακολουθούν ένα προσωπικό τρόπο γραφής κάποιων λέξεων δίχως να ακολουθείται κάποια νόρμα σύνταξης, ορθογραφίας και συλλαβισμού στο κείμενο. Θα δούμε πως μπορούμε με κατάλληλο φιλτράρισμα της πληροφορίας των γραπτών μηνυμάτων να προσεγγίσουμε όσο το δυνατόν περισσότερο την ανθρώπινη λογική γραφής. Θα αναλύσουμε τα φιλτραρισμένα δεδομένα και θα περιγράψουμε πως μπορεί και ο ίδιος ο χρήστης να συμβάλλει σημαντικά στο φιλτράρισμα αυτό αποκλείοντας λέξεις της αρεσκείας του από τα σύνολο των δεδομένων που θα χρησιμοποιηθούν για ευρετηριοποίηση και πως αυτό επηρεάζει σημαντικά την απόδοση της αναζήτησης. Θα επικεντρωθούμε στις πιο διαδεδομένες δομές δεδομένων που χρησιμοποιούνται για ευρετηριοποίηση και θα αναλύσουμε ποια είναι η κατάλληλότερη δομή που πρέπει να χρησιμοποιηθεί στην περίπτωσή μας και πως αυτή τροποποιήθηκε για το σκοπό της μελέτης μας. Θα αναλύσουμε πως η μετατροπή αυτή αποτέλεσε σημαντική εξέλιξη στην απόδοση του ευρετηρίου μας και πως η αναζήτηση με τη χρήση του ανεστραμμένου ευρετηρίου που αναπτύξαμε απογειώνει την ταχύτητα ανάκτησης των δεδομένων των μηνυμάτων. Τέλος, παραθέτουμε την εφαρμογή που αναπτύξαμε με τη χρήση της γλώσσας προγραμματισμού Java για το λειτουργικό σύστημα Android που ενσωματώνει το ανεστραμμένο ευρετήριο που αναπτύξαμε και βοηθά στην αναζήτηση οποιασδήποτε πληροφορίας από τα γραπτά μηνύματα είτε απευθείας από τη βάση των μηνυμάτων του Android είτε χρησιμοποιώντας το ευρετήριο. / In the current thesis an inverted index was designed for Adroid sms messages which is speeding the information retrieval from the sms database.

Doctor en Ciencias, Mención Computación / El principal objetivo de los sistemas de recuperación de información (SRI) es encontrar, lo más rápido posible, la mejor respuesta para una consulta de un usuario. Esta no es una tarea simple: la cantidad de información que los SRI manejan es típicamente demasiado grande como para permitir búsquedas secuenciales, por lo que es necesario la construcción de índices. Sin embargo, la memoria es un recurso limitado, por lo que estos deben ser eficientes en espacio y al mismo tiempo rápidos para lidiar con las demandas de eficiencia y calidad. La tarea de diseñar e implementar un índice que otorgue un buen compromiso en velocidad y espacio es desafiante tanto del punto de vista teórico como práctico. En esta tesis nos enfocamos en el uso, diseño e implementación de estructuras de datos compactas para crear nuevos índices que sean más rápidos y consuman menos espacio, pensando en ser utilizados en SRI sobre lenguaje natural. Nuestra primera contribución es una nueva estructura de datos que compite con el índice invertido, que es la estructura clásica usada en SRIs por más de 40 años. Nuestra nueva estructura, llamada {\em Treaps Invertidos}, requiere espacio similar a las mejores alternativas en el estado del arte, pero es un orden de magnitud más rápido en varias consultas de interés, especialmente cuando se recuperan unos pocos cientos de documentos. Además presentamos una versión incremental que permite actualizar el índice a medida que se van agregando nuevos documentos a la colección. También presentamos la implementación de una idea teórica introducida por Navarro y Puglisi, llamada Dual-Sorted, implementando operaciones complejas en estructuras de datos compactas. En un caso más general, los SRI permiten indexar y buscar en colecciones formadas por secuencias de símbolos, no solamente palabras. En este escenario, Navarro y Nekrich presentaron una solución que es óptima en tiempo, que requiere de espacio lineal y es capaz de recuperar los mejores $k$ documentos de una colección. Sin embargo, esta solución teórica requiere más de 80 veces el tamaño de la colección, haciéndola poco atractiva en la práctica. En esta tesis implementamos un índice que sigue las ideas de la solución óptima. Diseñamos e implementamos nuevas estructuras de datos compactas y las ensamblamos para construir un índice que es órdenes de magnitud más rápido que las alternativas existentes y es competitivo en términos de espacio. Además, mostramos que nuestra implementación puede ser adaptada fácilmente para soportar colecciones de texto que contengan lenguaje natural, en cuyo caso el índice es más poderoso que los índices invertidos para contestar consultas de frases. Finalmente, mostramos cómo las estructuras de datos, algoritmos y técnicas desarrolladas en esta tesis pueden ser extendidas a otros escenarios que son importantes para los SRI. En este sentido, presentamos una técnica que realiza agregación de información de forma eficiente en grillas bidimensionales, una representación eficiente de registros de accesos a sitios web que permite realizar operaciones necesarias para minería de datos, y un nuevo índice que mejora las herramientas existentes para representar colecciones de trazas de paquetes de red. / Este trabajo ha sido parcialmente financiado por Millennium Nucleus Information and Coordination in Networks ICM/FIC P10-024F, Fondecyt Grant 1-140796, Basal Center for Biotechnology and Bioengineering (CeBiB) y Beca de Doctorado Nacional Conicyt

This thesis covers design and practical realization of a tool for quick search in large image databases, containing from tens to hundreds of thousands photos, based on image similarity. The proposed technique uses various methods of descriptor extraction, creation of Bag of Words dictionaries and methods of storing image data in PostgreSQL database. Further, experiments with the implemented software were carried out to evaluate the search time effectivity and scaling possibilities of the design solution.

Background Google, Bing, and Baidu are the most commonly used search engines in the world. They also have some problems. For example, when searching for Jaguar, most of the search  results are cars, not animals. This is the problem of polysemy. Search engines always provide the most popular but not the most correct results. Aim We want to design and implement a search function and explore whether the method of classified news can improve the precision of users searching for news. Method In this research, we collect data by using a web crawler. We use a web crawler to crawl    the data of news in BBC news. Then we use NLTK, inverted index to do data pre-processing, and use BM25 to do data processing. Results Compare to the normal search function, our  function has a lower recall rate and a higher precision. Conclusions This search function can improve the precision when people search for news. Implications This search function can be used not only to search news but to search everything. It has a great future in search engines. It can be combined with machine learning to analyze users' search habits to search and classify more accurately.

No description available.

The dramatic increase in the amount of content available in digital forms gives rise to large-scale digital libraries, targeted to support millions of users and terabytes of data. Retrieving information from a system of this scale in an efficient manner is a challenging task due to the size of the collection as well as the index. This research deals with the design and implementation of an inverted index that supports searching for information in a large-scale digital library, implemented atop a massively parallel storage system. Inverted index partitioning is studied in a simulation environment, aiming at a terabyte of text. As a result, a high performance partitioning scheme is proposed. It combines the best qualities of the term and document partitioning approaches in a new Hybrid Partitioning Scheme. Simulation experiments show that this organization provides good performance over a wide range of conditions. Further, the issues of creation and incremental updates of the index are considered. A disk-based inversion algorithm and an extensible inverted index architecture are described, and experimental results with actual collections are presented. Finally, distributed algorithms to create a parallel inverted index partitioned according to the hybrid scheme are proposed, and performance is measured on a portion of the equipment that normally makes up the 100 node Virginia Tech PetaPlex™ system. NOTE: (02/2007) An updated copy of this ETD was added after there were patron reports of problems with the file. / Ph. D.

In this work I argue that field of text search has focused mostly on long text documents, but there is a growing need for efficient short text search, which has different user expectations. Due to this reduced data set size requirements different algorithmic techniques become more computationally affordable. The focus of this work is on approximate and prefix search and purely text based ranking methods, which are needed due to lower precision of text statistics on short text. A basic prototype search engine has been created using the researched techniques. Its capabilities were demonstrated on example search scenarios and the implementation was compared to two other open source systems representing currently recommended approaches for short text search problem. The results show feasibility of the implemented prototype regarding both user expectations and performance. Several options of future direction of the system are proposed.

This thesis focuses on index and retrieval mechanism of an ontology based medical domain search engine. First, indexing techniques and retrieval methods are reviewed. Then, a special indexing and retrieval mechanism are introduced. This thesis also specifies the functional requirements of these mechanisms. Finally, an evaluation is given by indicating the positive and negative aspects of mechanisms.