Database Components on Chip
by Nicolas Anciaux, Luc Bouganim and Philippe Pucheral
Ubiquitous computing and ambient intelligence introduce the need for embedding data and evaluating database queries in a growing variety of ultra-light computing devices. The SMIS project at INRIA focuses on the design of database components embedded in a chip. Applications range from mobile computing to data confidentiality protection.
Pervasive computing is now a reality, and intelligent devices flood many aspects of our everyday lives. As stated by the Semiconductor Industry Association, semiconductors integrated in traditional computers currently represent less than 50% of a market of $US204 billion. As new applications appear, the need for database techniques embedded in various forms of lightweight computing devices arises.
Sensor networks gathering weather, pollution or traffic information have motivated several recent works (eg the COUGAR project at Cornell). They have brought out the need to execute local computation on the data, like aggregation, sort and top-n queries, either to save communication bandwidth in push-based systems or to participate in distributed pull-based queries. Other forms of autonomous mobile hosts include hand-held devices (eg personal databases, diaries, tourist information, etc). These can be used to execute on-board queries on data downloaded before a disconnection. Personal folders on a chip constitute another motivation to execute on-board queries. Typically, smart cards are used in various mobile applications involving personal data (such as healthcare, insurance, phone books, etc). In this context, queries can be fairly complex and their execution must be confined to the chip to prevent any disclosure of confidential data. Thus, saving communication costs, allowing disconnected activities and preserving data confidentiality are three different concerns that motivate the storage of data and the execution of on-board queries on lightweight computing devices.
The resource asymmetry of lightweight devices entails a thorough re-thinking of database techniques. Our research objective is therefore to design embedded database components that can match highly constrained hardware resources.
Preliminary studies led us to design and validate a full-fledged DBMS, called PicoDBMS, embedded in an advanced smart card platform (powerful CPU, tiny RAM, fast read-time and dramatically slow write-time in EEPROM stable storage). PicoDBMS is based on a compact and efficient ad-hoc storage and indexation model. The PicoDBMS query evaluator takes advantage of the CPU power and the fast read-time in the EEPROM to process any type of SQL query without using RAM, whatever the volume of the queried data.
Capitalising on this work, new and important research efforts need to be undertaken:
- to better capture the impact of each device hardware constraint on database techniques
- to propose new storage, indexation and query techniques allowing ad-hoc embedded database components to be built
- to set up co-design rules helping to calibrate the hardware resources of future devices to match the requirements of specific applications.
As a first step in this research agenda, we are conducting a comprehensive analysis of the RAM consumption problem. We try to answer three important questions. First, does a memory lower bound exist whatever the volume of the queried data? Second, how can a query be optimised without hurting this lower bound? Third, how does an incremental growth of RAM impact the techniques devised in a lower bound context? This study provides helpful guidelines to calibrate the RAM resource of a hardware platform according to a given application’s requirements, as well as to adapt an application to an existing hardware platform. In the mid-term, we plan to focus on energy consumption and on the usage of future stable-memory technologies.
Besides mobile computing and ambient intelligence, database components embedded in a chip may serve other important purposes in a wide range of applications. Typically, tamper-resistant chips (eg smart cards or tokens) can be used to make information systems safer. Data security is particularly emphasised in mobile environments. For instance, the increasing connection of travelling employees to corporate databases and the need to resort to Web-hosting companies and Database Service Providers to make personal data available to mobile users introduce new threats to data confidentiality. Users have no choice other than to trust the privacy policies of Web companies. However, according to the FBI, database attacks are more and more frequent (their cost is estimated to be more than $100 billion per year) and 45% of the attacks are conducted by insiders.
While traditional database security principles like user authentication, communication encryption and server-enforced access controls are widely accepted, they remain inoperative against insider attacks. Several attempts have been made to strengthen server-based security approaches thanks to database encryption. However, as Oracle confesses, server encryption has not proven to be the 'armour plating' that was expected, because the Database Administrator (or an intruder usurping his/her identity) has enough privilege to tamper with the encryption mechanism and get the clear-text data. Client-based security approaches, where decryption only occurs at the client-side, have been recently investigated but they cannot support data-sharing among users having different access rights.
The client-based solution we are developing at INRIA, called C-SDA (Chip-Secured Data Access), allows encrypted data to be queried while controlling personal privileges. C-SDA comprises an access right manager, a query rewriter, a query evaluator and a cryptographic engine, all embedded into a smart card to prevent tampering. As pictured in Figure 1, C-SDA acts as an incorruptible mediator between a client (potentially mobile) and the encrypted database. To illustrate the benefits of this approach, C-SDA allows complex permissions to be expressed on encrypted data, for example, 'give user X the privilege to compute the average salary of all employees without giving her access to the elementary data'. This cooperation of hardware and software security allows the orthogonality between access-right management and data encryption to be reestablished.
