High performance pattern matching and data remanence on graphics processing units

Pattern matching is an important task in a plethora of different fields ranging from computer science to medical application, but is also a resource consuming problem.With the increase in network link speed, and the tremendous amounts of data generated, serial pattern matching on Central Processing Unit (CPU) is close to being rendered obsolete. The ubiquitous Graphics Processing Unit (GPU) have become the focus of much interest within the scientific community due to their highly parallel computing capabilities, and cost effectiveness offered by the hardware.This thesis presents an empirical investigation of massively parallel single and multi-pattern matching algorithms, as well as security and privacy concerns for data processing on GPUs. This thesis demonstrates a trie reduction algorithm that reduces the size of the data stored in GPU memory. GPUs have a limited amount of memory and with the increasing number of patterns to be searched for, space complexity is of great importance. This work addresses these challenges and investigates different memory hierarchies for different matching problems increasing the overall performance.This work also presents a Digital Forensic (DF) and Reverse Engineering (RE) methodology based on an evaluation of the different memory hierarchies present in a GPU.The results of the investigation presented in this thesis show that single and multi-pattern matching algorithms can benefit of the massively parallel capabilities of GPUs when implemented with hardware design in mind. Furthermore, it is demonstrated that data offloaded to the GPU is subject to data leaks.Pattern matching is an important task in a plethora of different fields ranging from computer science to medical application, but is also a resource consuming problem.With the increase in network link speed, and the tremendous amounts of data generated, serial pattern matching on Central Processing Unit (CPU) is close to being rendered obsolete. The ubiquitous Graphics Processing Unit (GPU) have become the focus of much interest within the scientific community due to their highly parallel computing capabilities, and cost effectiveness offered by the hardware.This thesis presents an empirical investigation of massively parallel single and multi-pattern matching algorithms, as well as security and privacy concerns for data processing on GPUs. This thesis demonstrates a trie reduction algorithm that reduces the size of the data stored in GPU memory. GPUs have a limited amount of memory and with the increasing number of patterns to be searched for, space complexity is of great importance. This work addresses these challenges and investigates different memory hierarchies for different matching problems increasing the overall performance.This work also presents a Digital Forensic (DF) and Reverse Engineering (RE) methodology based on an evaluation of the different memory hierarchies present in a GPU.The results of the investigation presented in this thesis show that single and multi-pattern matching algorithms can benefit of the massively parallel capabilities of GPUs when implemented with hardware design in mind. Furthermore, it is demonstrated that data offloaded to the GPU is subject to data leaks