SQLite, one of the most popular light-weighted database system, has been widely used in various systems. However, the compact design of SQLite did not make enough consideration on user data security. Specifically, anyone who has obtained the access to the database file will be able to read or tamper the data. Existing encryption-based solutions can only protect data on storage, while still exposing data when in computation. In this article, we combine the Trusted Execution Environment(TEE) technology and the authenticated encryption scheme, proposed and developed the CryptSQLite, a high security SQLite database system, which protects both the confidentiality and integrity of users' data. Our security analysis proves that CryptSQLite can protect data confidentiality and integrity. Our implementation and experiments indicate that CryptSQLite incurs an average of 21 percent of extra time for SQL statement executions, compared with traditional encryption-based solutions that failed to offer rigorous security guarantees.

Sketches are probabilistic data structures designed for recording frequencies of items in a multi-set. They are widely used in various fields, especially for gathering Internet statistics from distributed data streams in network measurements. In a distributed streaming application with high data rates, a sketch in each monitoring node “fills up” very quickly and then its content is transferred to a remote collector responsible for answering queries. Thus, the size of the contents transferred must be kept as small as possible while meeting the desired accuracy requirement. To obtain significantly higher accuracy while keeping the same update and query speed as the best prior sketches, in this article, we propose a new sketch - the Slim-Fat (SF) sketch. The key idea behind the SF-sketch is to maintain two separate sketches: a larger sketch, the Fat-subsketch, and a smaller sketch, the Slim-subsketch. The Fat-subsketch is used for updating and periodically producing the Slim-subsketch, which is then transferred to the remote collector for answering queries quickly and accurately. We also present the error bound as well as an accurate model of the correct rate of the SF-sketch, and verify their correctness through experiments. We implemented and extensively evaluated the SF-sketch along with several prior sketches. Our results show that when the size of our Slim-subsketch and of the widely used Count-Min (CM) sketch are kept the same, our SF-sketch outperforms the CM-sketch by up to 33.1 times in terms of accuracy (when the ratio of the sizes of the Fat-subsketch and the Slim-subsketch is 16:1). We have made all source codes publicly available at Github [“Source code of SF sketches,” [Online]. Available: https://github.com/paper2017/SF-sketch].

Nowadays, an explosive increase of the size of Forwarding Information Base (FIB) in backbone router makes IP lookup a challenging issue. An effective solution is to use Bloom filter. Because of its false positive, to boost longest prefix matching (LPM), sophisticated Bloom filter-based algorithms were proposed, which makes FIB updating extremely difficult. To address this issue, in this paper, we propose a novel IP lookup algorithm which prunes unneeded prefix probes incurred by false positive and supports FIB updating. Experimental results show that our algorithm can save approximately 7~24% on-chip memory space than the well-known PBF (longest Prefix matching using Bloom Filters) while keeping the same average number of probes of 1.003 per IP lookup. In other words, given a limited on-chip memory budget, our proposed algorithm can handle FIB 7~24% bigger than PBF. The source code can be found in [1].

A sketch is a probabilistic data structure that is used to record frequencies of items in a multi-set. Sketches have been applied in a variety of fields, such as data stream processing, natural language processing, distributed data sets etc. In this paper, we propose a new sketch, called Slim-Fat (SF) sketch, which has a much smaller memory footprint for query while supporting updates. The key idea behind our proposed SF-sketch is to maintain two separate sketches: a small sketch called Slimsubsketch and a large sketch called Fat-subsketch. The Slimsubsketch enables fast and accurate querying. The Fat-subsketch is used to assist the insertion and deletion from Slim-subsketch. We implemented and evaluated SF-sketch along with several prior sketches and compared them side by side. Our experimental results show that SF-sketch significantly outperforms the most commonly used CM-sketch in terms of accuracy. The full version is provided at arXiv.org [12].