Somayeh Sobati Moghadam

Jérôme Darmont
email: jerome.darmont@univ-lyon2.fr

Gérald Gavin
email: gerald.gavin@univ-lyon1.fr

Enforcing Privacy in Cloud Databases

Keywords: Databases, Cloud Computing, DBaaS, Data Privacy, Data Encryption

Outsourcing databases, i.e., resorting to Database-as-a-Service (DBaaS), is nowadays a popular choice due to the elasticity, availability, scalability and pay-as-you-go features of cloud computing. However, most data are sensitive to some extent, and data privacy remains one of the top concerns to DBaaS users, for obvious legal and competitive reasons. In this paper, we survey the mechanisms that aim at making databases secure in a cloud environment, and discuss current pitfalls and related research challenges.

Introduction

Cloud computing offers a variety of services via a pay-per-use model on the Internet. The flexibility that cloud computing offers is very appealing for many organizations, especially mid-sized and small ones, because it provides reduced start-up costs and means to financially cope with variations in system usage. Outsourcing data to the cloud is particularly interesting [START_REF] Xiong | Preserving data privacy in outsourcing data aggregation services[END_REF]. However, some data are especially sensitive, e.g., personal data, health-related data, business data, and generally data used in decision-support processes. Outsourcing a database in the cloud raises security issues, some related to cloud architectures (e.g., untrusted service providers, curious cloud employees...), and others related to such concerns as data privacy, integrity and availability. With increasingly sophisticated internal and external cloud attacks, traditional security mechanisms are no longer sufficient to protect cloud databases [START_REF] Yuhanna | Your Enterprise Database Security Strategy[END_REF].

Let us consider a Database-as-a-Service (DBaaS) scenario (Figure 1) where a user outsources a database at one or more Cloud Service Providers' (CSPs). The objective is to eliminate storage and minimize computation at the user's to take full advantage of cloud benefits. Yet, anything beyond the user is considered untrusted. CSPs might indeed be honest but curious, i.e., read the user's data, or even be malicious or maliciously hacked, i.e., alter data or provide fake query results. Network transactions are also considered unsafe. The user must thus protect sensitive data and queries before sending them to CSPs, and safely reconstruct query results "at home". In this paper, we survey the security mechanisms that may be exploited in our cloud database scenario, particularly in terms of privacy. Another recent survey intersects ours [START_REF] Saleh | Processing Over Encrypted Data: Between Theory and Practice[END_REF], but more deeply focuses on cryptography, while we adopt a broader scope on security, put more emphasis on querying efficiency and survey non-cryptographic methods (Section 2). We also mostly target database practitioners and researchers with no background in cryptography. Moreover, we review cryptographic methods that are not covered in [START_REF] Saleh | Processing Over Encrypted Data: Between Theory and Practice[END_REF], i.e., secret sharing, Private Information Retrieval (PIR) and oblivious RAM (ORAM) schemes. We classify cryptographic tools that can be exploited within cloud database scenarios into secret sharing schemes (Section 3), index-based methods (Section 4) and secure databases (Section 5). Finally, we conclude this paper by a global discussion (Section 6).

2 Non-Cryptographic Methods

Differential Privacy

Differential privacy aims at protecting data privacy when performing statistical queries [START_REF] Dwork | Differential Privacy[END_REF]. While global statistics are public, individual data must remain private. To achieve this goal, a noise term is added to statistical query results, e.g., to an average salary, thus preventing the computation of individual salaries. It would indeed be easy to compute a new salary that has just been added in the database, knowing averages avg and the number of records n in the dataset: avg n+1 × (n + 1) -avg n × (n).

A randomized algorithm A enforces -differential privacy if and only if, for any two databases DB 1 and DB 2 that differ on exactly one record, the ratio between the probability that A outputs O on DB 1 and DB 2 is bounded by a constant: P (A(DB 1 ) = O) ÷ P (A(DB 2 ) = O) ≤ e [START_REF] Yang | Differential privacy in data publication and analysis[END_REF]. The tradeoff is that the smaller is, the better privacy is enforced, but the worse accuracy is. Thus, one major challenge is reducing the amount of noise while still satisfying differential privacy. Yet, in a DBaaS context, a curious CSP would still have access to fine-grained data, which is incompatible with our data outsourcing scenario, where we aim at protecting data event from the CSP.

Data Anonymization

Data anonymization irreversibly modifies data in a way that prevents the identification of sensitive information, while allowing querying data for releasing useful statistical information [START_REF] Dwork | Differential Privacy[END_REF]. Some database management systems (DBMSs) natively include anonymization schemes. For example, Oracle Data Masking Pack provides data masking for various types of data, replacing real data with realistic-looking values [START_REF]Data Masking Best Practices[END_REF]. Obscuring query processing and results may also be achieved either by rejecting queries leading to privacy disclosure or through methods such as k-anonymity and its variants t-closeness and l-diversity, which transform k distinguishable records into k indistinguishable records [START_REF] Sweeney | k-Anonymity: A Model for Protecting Privacy[END_REF].

In a DBaaS context, privacy-preserving queries in a distributed environment can be achieved by table perturbation and reconstruction [START_REF] Rakesh Agrawal | Privacy Preserving OLAP[END_REF]. Perturbation randomly replaces an element in a table by another with probability p. Then, reconstruction can estimate COUNT queries over the perturbed table. Unfortunately, other aggregation functions are not supported. Similarly, random data distortion techniques may be used, e.g., the zero-sum method provides an accurate estimation of summation for range queries [START_REF] Yuan | Privacy preservation for data cubes[END_REF], but it induces a trade-off between privacy and accuracy. Finally, adding different amounts of noise to query answers can be used, e.g., with iReduct [START_REF] Xiao | iReduct: differential privacy with reduced relative errors[END_REF]. iReduct initially estimates query answers and iteratively refines its estimates to minimize relative errors.

Data anonymization is less complex than encryption and straightforwardly allows querying anonymized data. However, it typically reduces data granularity, which may cause a loss of effectiveness and correctness in computation [START_REF] Charu | A General Survey of Privacy-Preserving Data Mining Models and Algorithms[END_REF]. Moreover, the various anonymization methods have different impacts on data utility. As a result, the same anonymized table may provide accurate answers to some queries and inaccurate results to others. More importantly, data anonymization cannot provide an adequate level of security since private personal data can be re-identified by an adversary who has some knowledge about data [START_REF] De Montjoye | Unique in the Crowd: The privacy bounds of human mobility[END_REF].

Data Fragmentation

In data fragmentation [START_REF] Aggarwal | Two Can Keep A Secret: A Distributed Architecture for Secure Database Services[END_REF], data are assumed not to be sensitive per se. What is sensitive is their association with other data. Privacy is thus guaranteed by concealing such associations with respect to a predefined set of security constraints that express restrictions on one or more attributes in a table [START_REF] Ciriani | Selective data outsourcing for enforcing privacy[END_REF][START_REF] Ali Hadavi | Database as a Service: Towards a Unified Solution for Security Requirements[END_REF]. For instance, given a P atient table, constraint C = {N ame, Illness} indicates that associations between patient names and illnesses should not be disclosed. Then, the table is split into fragments such that attributes listed in a constraint belong to different fragments. For instance, table P atient would be split in two fragments P atient 1 and P atient 2 , with N ame ∈ P atient 1 and Illness ∈ P atient 2 . Yet, most data fragmentation approaches apply to numerical data and specific methods most be used to handle categorical data [START_REF] Ricci | Privacy-Preserving Cloud-Based Statistical Analyses on Sensitive Categorical Data[END_REF].

In a cloud context, data can be partitioned at independent CSPs' with respect to security constraints. When a query is issued, an appropriate subquery is transmitted to each CSP, then the results are pieced together at the user's. Moreover, intrinsically sensitive attributes such as social security numbers are stored locally at the user's. Eventually, fragmentation-based approaches yield little overhead on query computation, but are vulnerable in cases of CSP collusion and CSP inference on data updates [START_REF] Ali Hadavi | AS5: A Secure Searchable Secret Sharing Scheme for Privacy Preserving Database Outsourcing[END_REF]. Additionally, retaining sensitive data at the user's requires local storage capacities, which is incompatible with our data outsourcing scenario.

Secret Sharing-Based Methods

Secret sharing is a particular cryptographic method introduced by Shamir in which a secret piece of data is mathematically divided into so-called shares that are stored at n participants' [START_REF] Shamir | How to Share a Secret[END_REF]. One single participant has no means to reconstruct the secret. A subset of k ≤ n participants is indeed required to reconstruct the secret, providing perfect theoretical privacy when at most k -1 participants collude, i.e., exchange shares. Moreover, computations can run directly on shares, outputting unintelligible results that can only be put together through k participants. Finally, up to n -k participants may disappear without compromising data availability; and message authentication code or signature can be applied to guarantee data integrity. Thus, secret sharing is a promising solution to security challenges in cloud data outsourcing [START_REF] Ali Hadavi | AS5: A Secure Searchable Secret Sharing Scheme for Privacy Preserving Database Outsourcing[END_REF] since one can easily imagine participants being CSPs. In the following subsections, we review the secret sharing-based approaches that aim at outsourcing databases, and then discuss them globally.

Verifiable Secret Sharing

Thompson et al.'s scheme allows participants to collaboratively compute aggregation queries without gaining knowledge of intermediate results [START_REF] Thompson | Privacy-Preserving Computation and Verification of Aggregate Queries on Outsourced Databases[END_REF]. A lightweight cryptographic scheme is introduced for privacypreserving computation and verification of SUM and AVG aggregation queries. Moreover, users can verify query results with the help of signatures, while the data values contributing to the results are kept secret from both users and the CSPs. The query issuer indeed interacts with a single CSP to obtain aggregation results and can verify whether the CSP returns correct results. However, aggregation queries other than SUM and AVG cannot be computed with this scheme.

Attasena et al. specifically target cloud data warehouses through a flexible, verifiable secret sharing scheme named fVSS [START_REF] Varunya Attasena | fVSS: A New Secure and Cost-Efficient Scheme for Cloud Data Warehouses[END_REF]. fVSS minimizes shared data volume, provides inner and outer data verification to check data correctness and the honesty of CSPs, improves the ability to update shares in case of CSP failure, and adjusts share volume with respect to CSP pricing policies. Moreover, in addition to queries explicitly handled by previous schemes, fVSS also allow grouping queries that are ubiquitous in On-Line Analysis Processing (OLAP). However, although some queries can be computed directly over shares (e.g., exact match queries), others require that some or all data are decrypted first (e.g., range queries).

Wang et al. propose a framework for secure and efficient query processing of relational data in the cloud that allows exact match and range queries, as well as updates [START_REF] Wang | A Comprehensive Framework for Secure Query Processing on Relational Data in the Cloud[END_REF]. B+-tree indexes are also built to optimize query response. Both data and indexes are organized into matrices, encrypted and stored at CSPs'. Additionally, data integrity is achieved by using checksum and an index structure. This framework is robust against statistical attacks.

Statistical attacks refer to an adversary obtaining some information about ciphertexts, i.e., encrypted data, through prior knowledge about plaintexts, i.e., clear data [START_REF] Ali Hadavi | AS5: A Secure Searchable Secret Sharing Scheme for Privacy Preserving Database Outsourcing[END_REF]. For instance, the adversary may know plaintext distribution or frequency. Then, by extracting statistics from ciphertexts, the adversary can infer ranges containing dense data or highlight ciphertexts bearing the same frequency as plaintexts.

Order-preserving Secret Sharing

Agrawal et al. propose a complete approach to execute exact match, range, and aggregation queries over shares outsourced at multiple CSPs [START_REF] Agrawal | Database Management as a Service: Challenges and Opportunities[END_REF]. Original data are divided using order-preserving polynomials such that the order of shares is the same as that of original data. However, while this solution allows efficiently processing any kind of queries, including updates, it is susceptible to statistical attacks [START_REF] Ali Hadavi | AS5: A Secure Searchable Secret Sharing Scheme for Privacy Preserving Database Outsourcing[END_REF].

Hadavi et al. introduce a framework to provide data privacy based on threshold secret sharing [START_REF] Ali | Secure data outsourcing based on threshold secret sharing; towards a more practical solution[END_REF]. First, secret values are encrypted by an Order Preserving Encryption (OPE) scheme (Section 5.1). Then, a B+-tree is built over ciphertexts and sent to an index server. The user receives query responses, including record numbers, from the index server and can then request these records from the CSPs. As Agrawal et al.'s scheme, this approach supports different kind of queries over shares, including exact match, range and aggregation queries, as well as updates. Moreover, it provides stronger security than Agrawal et al.'s scheme. It is indeed secure against frequency attacks, and an extension uses distribution perturbation to improve its robustness against statistical attacks in general [START_REF] Ali Hadavi | AS5: A Secure Searchable Secret Sharing Scheme for Privacy Preserving Database Outsourcing[END_REF]; but at the price of a higher computational overhead.

Discussion

Table 1 provides a comparison of secret sharing-based database outsourcing methods with respect to the queries that can run directly on shares and security features beyond privacy and availability, i.e., integrity checks and robustness against statistical attacks. Despite secret sharing's benefits, it is not trivial to process some queries directly over shares, especially queries requiring data ordering. Obviously, it is not efficient to send back all shares in response to a query, and execute the query over reconstructed values at the user's. However, the techniques that allow directly processing such queries as range queries over shares reveal some information about plaintexts, e.g., duplicates [START_REF] Agrawal | Database Management as a Service: Challenges and Opportunities[END_REF]. Moreover, since every secret is shared n times, global share size can be quite large. Communication between the user and multiple CSPs is not optimal in terms of bandwidth resources either. As a result, storage and communication overhead of secret sharing-based approaches is remarkably high for moderately large databases [START_REF] Krawczyk | Secret Sharing Made Short[END_REF].

Index-Based Methods

In databases, data encryption is usually managed at the tuple level [START_REF] Davida | A Database Encryption System with Subkeys[END_REF], which prevents any computation over ciphertexts. Thus, indexes based on plaintexts are stored together with the encrypted database to help return ciphertexts in response to queries. We distinguish three types of index-based methods, namely bucketization, order preserving indexing and indexes used in Searchable Encryption (SE) schemes. We review them in the following subsections before providing a global discussion.

Bucketization-Based Indexing

Bucketization-based indexing involves dividing data into buckets and providing explicit labels for each bucket [START_REF] Mykletun | Aggregation Queries in the Database-As-a-Service Model[END_REF]. The domain of an attribute is partitioned into a set of non-overlapping buckets. Labels may preserve the order of values in the original domain or not. They are stored along with encrypted tuples. Such indexing allows exact match, range (if data order is preserved) and join queries, but also induce false positives in query answers. Thus, query post-processing is needed at the user's to filter out false positives [START_REF] Samarati | Data Protection in Outsourcing Scenarios: Issues and Directions[END_REF].

Hacigümüs et al. partition data as in histogram construction, e.g., by equi-depth and equi-width partitioning [START_REF] Hacigümüs | Executing SQL over encrypted data in the database-service-provider model[END_REF]. Then, it assigns a random tag to each bucket. Any table T (A 1 , A 2 , ..., A n ) from a database is stored at the CSP's as T S (etuple, A S 1 , A S 2 , ..., A S n ), where etuple is the encrypted tuple and each A S i is the index of attribute A i . Each query is rewritten into server-side and user-side subqueries Q S and Q C , respectively. Q S is executed by the CSP over ciphertexts using indexes A S i . The result of Q S is then sent back to the user, who decrypts it and executes Q C to filter out false positives. Query rewriting requires maintaining metadata, including bucket labels.

With the help of an homomorphic function, this approach is extended to support aggregation queries over ciphertexts [START_REF] Hacigümüs | Efficient execution of aggregation queries over encrypted relational databases[END_REF]. The homomorphic encryption function is based on the Privacy Homomorphism (PH) scheme [START_REF] Ronald L Rivest | On data banks and privacy homomorphisms[END_REF], which relies on the difficulty of factoring large composite integers, just like the famous Rivest-Shamir-Adleman (RSA) public-key cryptosystem. Unfortunately, Mykletun and Tsudik demonstrate that the CSP can obtain plaintexts with access to ciphertexts only [START_REF] Mykletun | Aggregation Queries in the Database-As-a-Service Model[END_REF].

Based on their rebuttal of Hacigümüs et al., Mykletun and Tsudik propose a simple alternative for supporting aggregation queries [START_REF] Mykletun | Aggregation Queries in the Database-As-a-Service Model[END_REF]. The user precomputes aggregation values (e.g., SUM and COUNT) for each bucket, encrypts and stores them at the CSP's. Moreover, instead of using the PH scheme, Mykletun and Tsudik use provably secure additive homomorphic encryption schemes such as Paillier's [START_REF] Paillier | Public-Key Cryptosystems Based on Composite Degree Residuosity Classes[END_REF] and El Gamal's [START_REF] El | A public key cryptosystem and a signature scheme based on discrete logarithms[END_REF]. Precomputing aggregations decreases security risks, but requires extra storage and makes updates more complex. Updates must indeed be executed in two steps: 1) actual data update and 2) update of related precomputed aggregates in a bucket.

Hore et al. also address shortcomings of Hacigümüs et al.'s method. They notably optimize the accuracy of range queries to minimize false positives in query results [START_REF] Hore | A Privacy-Preserving Index for Range Queries[END_REF]. They also introduce a re-bucketization technique, in which the user can fine-tune bucketization to achieve a desired level of privacy. Moreover, they propose a new method for answering range queries on multidimensional data [START_REF] Hore | Secure multidimensional range queries over outsourced data[END_REF]. Range queries over multiple attributes, e.g., age < 20 and salary > 25k, are allowed, while minimizing the cost of multidimensional bucketization. Yet, a threshold is defined to help the user control the trade-off between risk of data disclosure and cost.

Order-Preserving Indexing

Order Preserving Encryption Scheme (OPES) Agrawal et al.'s OPES is an OPE indexing scheme that supports range and equality queries over integers [START_REF] Agrawal | Order-Preserving Encryption for Numeric Data[END_REF]. OPES transforms plaintexts with an order preserving function so that transformed values (e.g., index values) follow a target distribution. Comparison operations can be directly applied at the CSP's without inducing spurious tuples nor false positives. However, this scheme has been demonstrated to be vulnerable to statistical attacks [START_REF] Liu | New order preserving encryption model for outsourced databases in cloud environments[END_REF].

OPE with Splitting and Scaling (OPESS) The OPESS scheme encrypts XML databases [START_REF] Hui | Efficient Secure Query Evaluation over Encrypted XML Databases[END_REF]. Wang et al. adopt splitting and scaling techniques to create index values following a uniform distribution. Plaintext order is preserved over indexes. Moreover, identical clear values are transformed into different indexes so that this scheme is robust against statistical attacks. However, this scheme flattens the frequency distribution of index values.

B+tree indexing Shmueli et al. [START_REF] Shmueli | Designing secure indexes for encrypted databases[END_REF] and Damiani et al. [START_REF] Damiani | Balancing confidentiality and efficiency in untrusted relational DBMSs[END_REF] use B+-trees built on database plaintext attribute values to preserve order in secure environments. B+-trees must either be stored in a trusted machine [START_REF] Ali | Secure data outsourcing based on threshold secret sharing; towards a more practical solution[END_REF] or be encrypted at the CSP's, where each B+-tree is stored in a table with two attributes: node identifier and node content. In addition to ordering, B+-tree indexes support exact match, range and grouping queries, as well as predicates such as LIKE. For example, to execute a range query, the user sends a sequence of queries until reaching the leaf corresponding to the range's lower bound. Then, the node identifier helps retrieve all the tuples belonging to the range. The advantage of such indexing is that index content is not visible to the CSP and reveals no information about underlying plaintexts [START_REF] Damiani | Balancing confidentiality and efficiency in untrusted relational DBMSs[END_REF].

Searchable Encryption

SE allows the CSP to run keyword-based searches on encrypted data [START_REF] Song | Practical Techniques for Searches on Encrypted Data[END_REF] that are particularly suitable to data outsourcing [START_REF] Bösch | A Survey of Provably Secure Searchable Encryption[END_REF]. Considering a set of documents {D i } i=1,n and an index of keywords {w j } j=1,m describing the documents, users encrypt both documents D i with any secure encryption scheme using a key K Enc and keywords w j with a searchable scheme using a key K Index . The encrypted documents and index are then outsourced. When searching for documents containing some keywords, the user sends a so-called trapdoor encapsulating the keywords to the CSP [START_REF] Sun | Privacy-Preserving Keyword Search Over Encrypted Data in Cloud Computing[END_REF]. Then, the CSP can search the encrypted index and the trapdoor to find the corresponding documents and send them back to the user. Both symmetric (private) and asymmetric (public) key encryption can be used to build symmetric SE (SSE) and asymetric SE (ASE) schemes, respectively [START_REF] Sun | Privacy-Preserving Keyword Search Over Encrypted Data in Cloud Computing[END_REF]. ASE schemes support various query types such as range and subset queries, but are computationally intensive. SSE is more efficient than ASE, but supports fewer query types. SE induces a trade-off between security, efficiency and query expressiveness. SE schemes with higher levels of security induce higher complexity, while SE schemes supporting more query types are either less secure and/or less efficient [START_REF] Bösch | A Survey of Provably Secure Searchable Encryption[END_REF]. Moreover, most SE schemes reveal access patterns, i.e., which documents contain a keyword. Only techniques based on PIR or ORAM do not.

PIR [START_REF] Cachin | Computationally Private Information Retrieval with Polylogarithmic Communication[END_REF][START_REF] Chang | Single Database Private Information Retrieval with Logarithmic Communication[END_REF][START_REF] Lueks | Sublinear Scaling for Multi-Client Private Information Retrieval[END_REF] enables a user to retrieve data from an outsourced database while preventing the CSP from learning any information about retrieved data [START_REF] Chor | Private Information Retrieval[END_REF], i.e., PIR enforces query privacy. Unfortunately, in a single-server setting, the only thing a user can do is retrieving the whole database, which induces communication overhead and annihilates the benefits of outsourcing. However, in a multiple-server setting where copies of the database are stored at k non-communicating/colluding CSPs, a user can hide queries by querying each server for a part of data, so that no server knows the whole query.

ORAM allows reading and writing to memory without revealing access patterns to the CSP [START_REF] Goldreich | Software Protection and Simulation on Oblivious RAMs[END_REF]. In ORAM schemes, a user stores encrypted data at the CSP's and continuously shuffles and re-encrypts data as they are accessed [START_REF] Stefanov | Path ORAM: an extremely simple oblivious RAM protocol[END_REF]. Let P = (q 1 , . . . , q n ) be an access pattern. The shuffling process induces the transformation of each query q i into multiple queries, producing a new access pattern P . An ORAM protocol is secure if two access patterns ORAM(P ) and ORAM(P ) are computationally indistinguishable.ORAM can be implemented using symmetric or fully homomorphic encryption (Section 5.1). An alternative solution for hiding access patterns is to frequently send fake queries to CSPsto prevent any adversary from inferring correlations between frequently queried data [START_REF] Mavroforakis | Modular Order-Preserving Encryption, Revisited[END_REF]. Yet, generating fake but realistic-looking queries is a challenge.

Unfortunately, a common limitation of PIR and ORAM schemes is a prohibitive query execution time [START_REF] Williams | Access privacy and correctness on untrusted storage[END_REF].

Discussion

Table 2 provides a comparison of index-based methods with respect to the query types they allow and whether they require a post-processing step to eliminate false positives.

Table 2. Comparison of index-based methods

Allowed queries

Exact match Range Aggregation Post-processing Hacigümüs et al. [START_REF] Hacigümüs | Executing SQL over encrypted data in the database-service-provider model[END_REF] user has to filter intermediate results sent by the CSP to reconstruct the global result. Hence, bucketizationbased methods induce computational overhead at the user's, too. Such an overhead can be high, especially for queries that return a large number of encrypted tuples [START_REF] Tu | Processing Analytical Queries over Encrypted Data[END_REF], e.g., grouping queries running on fine-grained data.

Finally, although index-based approaches are quite popular in cloud data outsourcing due to their efficiency [START_REF] Ali Hadavi | AS5: A Secure Searchable Secret Sharing Scheme for Privacy Preserving Database Outsourcing[END_REF][START_REF] Samarati | Data Protection in Outsourcing Scenarios: Issues and Directions[END_REF], their main limitation lies in data update. Typically, such methods but SE exploit the distribution of plaintexts, while update operations may change it, making index regeneration unavoidable [START_REF] Ali Hadavi | AS5: A Secure Searchable Secret Sharing Scheme for Privacy Preserving Database Outsourcing[END_REF]. As a result, index-based solutions but SE are suitable for read-only data. Yet, SE schemes are either too costly or too limited in query expressiveness to be used in practice.

5 Secure Databases

CryptDB

CryptDB is a pioneer system that allows efficient SQL query processing over ciphertexts into a DBMS [START_REF] Raluca | CryptDB: protecting confidentiality with encrypted query processing[END_REF]. The properties of a cryptographic scheme determine the kinds of queries that can be directly executed over ciphertexts. Thus, CryptDB implements several schemes with respect to different user-determined security requirements and query needs. Thus, we first describe these cryptographic schemes, and then we detail CryptDB's architecture.

Query-Aware Encryption Schemes

Random Encryption (RND) RND schemes are the strongest security schemes. They indeed guarantee semantic security, i.e., it is computationally impossible to distinguish two ciphertexts. For instance, let x be a plaintext value and E an RND encrypting function. If, using the same encryption key, e 1 = E(x) and e 2 = E(x), then with high probability, e 1 = e 2 . However, RND schemes do not allow any computations nor queries over ciphertexts. They are only designed for safe storage.

Homomorphic Encryption (HE) HE allows performing arbitrary arithmetic operations over ciphertexts without decryption [START_REF] Gentry | A fully homomorphic encryption scheme[END_REF] while still providing semantic security. For instance, with an additive HE scheme, for any two encryptions E(x) and E(y), there exists a function f such that f (E(x), E(y)) = E(x + y). Fully homomorphic encryption (FHE) is prohibitively slow and requires so much computing power that it cannot be used in practice as of today. However, partially homomorphic encryption (PHE) is efficient for specific operations and can be used in practice. PHE allows either addition or multiplication over ciphertexts and guarantees semantic security. Paillier's [START_REF] Paillier | Public-Key Cryptosystems Based on Composite Degree Residuosity Classes[END_REF] and El Gamal's [START_REF] El | A public key cryptosystem and a signature scheme based on discrete logarithms[END_REF] are examples of PHE schemes. For instance, with Paillier's PHE, the product of two encryptions encrypts the sum of the encrypted values, i.e., E(x) × E(y) = E(x + y).

Deterministic Encryption (DET) DET encrypts identical data values into identical encryptions when using the same key, i.e., ∀x, y: x = y ⇔ E(x) = E(y). Thus, DET allows queries with equality predicates, equijoins, as well as GROUP BY, COUNT and DISTINCT queries [START_REF] Raluca | Building practical systems that compute on encrypted data[END_REF]. DET is secure only when there is no redundancy in data. It is not robust against statistical attacks. Although some public key encryption schemes allow exact match queries with stronger security guarantees [START_REF] Boneh | Public Key Encryption with Keyword Search[END_REF], search takes linear time with the size of the database, while DET operates in logarithmic time [START_REF] Bellare | Deterministic and Efficiently Searchable Encryption[END_REF], thus explaining its adoption in CryptDB.

Order Preserving Encryption (OPE) OPE is a deterministic encryption scheme that preserves plaintext order in ciphertexts. Let x and y be two plaintext values and E an OPE scheme. If x ≤ y, then E(x) ≤ E(y). This feature allows range queries, MIN and MAX aggregations, and ordering over ciphertexts. In terms of security, OPE is weaker than DET because it reveals data order. Yet, it can provide sufficient security for some applications, e.g., when the adversary does not possess any prior knowledge, while increasing the efficiency of query processing [START_REF] Özsoyoglu | Anti-Tamper Databases: Querying Encrypted Databases[END_REF]. CryptDB's Architecture CryptDB follows three principles to solve the problem of querying encrypted databases: 1) SQL-aware encryption that uses cryptographic schemes within SQL queries; 2) adjustable query-based encryption to minimize data leakage; and 3) chain cryptographic keys in user passwords to enable data decryption only for authorized users with access privileges.

In CryptDB's core, encryption is structured in multiple embedded levels akin to onion layers. Each onion layer helps process given classes of queries. The outermost layers are RND and HE, HE actually being Paillier's PHE scheme. RND and HE provide the highest level of security, whereas inner layers, OPE and DET, provide more functionality. The OPE layer is an enhancement of [START_REF] Boldyreva | Order-Preserving Symmetric Encryption[END_REF]. Eventually, two new cryptographic schemes enable join operations.

Ciphertext access is achieved through a trusted proxy server that encrypts data, rewrites queries (by anonymizing table and attribute names and encrypting constants) and decrypts query results. The proxy server stores encryption keys, the database schema and the onion layers of all attributes in the database. When a query is issued, the proxy dynamically peels off onion layers downs to a layer corresponding to the given computation. For instance, consider the query SELECT * FROM employee WHERE name = 'Alice'. First, the proxy issues a query to peel off the RND layer for attribute name down to the DET layer. Then, the proxy rewrites the query as SELECT * FROM T1 WHERE A2 = '0xac18f', where T1 and A2 denote the anonymization of table employee and attribute name, respectively, and 0xac18f = E DET ('Alice'). Similary, aggregation query SELECT SUM(salary) FROM employee would translate as SELECT SUM HE (A3) FROM T1, where SUM HE is a user-defined function implementing Paillier's PHE and A3 is the anonymization of attribute salary.

MONOMI

While CryptDB offers one of the first practical solutions for secure DBMSs, there are still a lot of queries that are not supported, especially OLAP-like queries. As an illustration, CryptDB supports only 2 queries out of 22 from the TPC-H decision support benchmark [START_REF]TPC Benchmark H (Decision Support) Standard Specification Revision 2.1[END_REF]. Thence, MONOMI builds upon CryptDB to allow the execution of analytical workloads [START_REF] Tu | Processing Analytical Queries over Encrypted Data[END_REF].

To this aim, MONOMI adds in a designer that optimizes the physical database layout at the CSP's and a query planner that splits query execution between the CSP and the user. The optimal plan for executing some queries may indeed involve sending intermediate results between the user and the CSP several times to execute different parts of a query [START_REF] Tu | Processing Analytical Queries over Encrypted Data[END_REF]. For instance, to run a SUM / GROUP BY / HAVING query, MONOMI computes the SUM and GROUP BY at the CSP's through the HE and DET encryption schemes, respectively. Then, since HE does not preserve data order, the HAVING statement is executed at the user's after decryption. This strategy helps MONOMI allow 19 out of the 22 queries of TPC-H.

Multi-Valued Order Preserving Encryption (MV-OPE)

Lopes et al. rightly claim that "little attention has been devoted to determine how a data warehouse hosted in a cloud should be encrypted to enable analytical queries processing" [START_REF] Cruz Lopes | Processing OLAP Queries over an Encrypted Data Warehouse Stored in the Cloud[END_REF]. Thence, they propose the MV-OPE scheme that allows GROUP BY queries over ciphertexts. Such a scheme could replace CryptDB's and MONOMI's OPE without having to compute anything at the user's.

Generally speaking, MV-OPE extends OPE by encrypting the same plaintext into different ciphertexts while preserving the order of the plaintexts [START_REF] Kadhem | MV-OPES: Multivalued-Order Preserving Encryption Scheme: A Novel Scheme for Encrypting Integer Value to Many Different Values[END_REF]. Thus, given two clear values x and y and an MV-OPE function E, if x < y then E(x) < E(y). MV-OPE can be used to compute operations such as equality, difference, inequalities, minimum, maximum and count [START_REF] Cruz Lopes | Processing OLAP Queries over an Encrypted Data Warehouse Stored in the Cloud[END_REF]. MV-OPE improves robustness against statistical attacks and only leaks the order of data. Lopes et al.'s scheme combines MV-OPE with FHE (Section 5.1). Moreover, as CryptDB and MONOMI, it involves a secure host, e.g., a trusted proxy server. Despite using FHE, Lopes et al. experimentally show that computing queries over ciphertexts at the CSP's is significantly faster than computing them at the user's after decryption.

Secure Trusted Hardware

Trusted hardware devices are widely used for security, e.g., smart cards for secure authentication and secure coprocessors in automated teller machines (ATMs). Quite naturally, the idea of processing queries inside tamper-proof enclosures of trusted hardware, such as a secure coprocessor or Field Programmable Gate Array (FPGA)-based secure programmable hardware [START_REF] Eguro | FPGAs for trusted cloud computing[END_REF], came up. Such components are physically hosted at the CSP's. They have access to encryption keys and allow performing a limited set of queries over ciphertexts.

TrustedDB TrustedDB is an SQL database processing engine that makes use of IBM 4764/5 cryptographic coprocessors [START_REF] Arnold | IBM 4765 cryptographic coprocessor[END_REF] to run custom queries securely [START_REF] Bajaj | TrustedDB: a trusted hardware based database with privacy and data confidentiality[END_REF]. Coprocessors offer several cryptographic schemes such as the Advanced Encryption Standard (AES), the Triple Data Encryption Standard (3DES), RSA, pseu-dorandom number generation and cryptographic hash functions. Yet, cryptographic coprocessors are significantly constrained in both computation ability and memory capacity. Thus, a trade-off must be considered between cheap query processing on untrusted main processors (at the CSP's) and expensive computation inside secure coprocessors.

Sensitive data can only be decrypted and processed by the user or a secure coprocessor. Only non-sensitive data are stored unencrypted at the CSP's. When a query is issued, it is encrypted at the user's, rewritten as a set of subqueries and executed at the CSP's or in the secure coprocessor database engine, with respect to data sensitivity. The final result is assembled, encrypted by the secure coprocessor and sent back to the user.

Cipherbase Cipherbase aims at deploying trusted hardware for secure data processing in the cloud [START_REF] Arasu | Transaction processing on confidential data using Cipherbase[END_REF]. Cipherbase actually extends Microsoft SQL Server with in-server, customized FPGA-based trusted hardware. The FPGA is a trusted black box for computing operations over ciphertexts, which are encrypted with a nonhomomorphic encryption scheme such as AES. The FPGA decrypts data internally, processes the operations and encrypts the result back. As in TrustedDB, query processing on non-sensitive data is handled by the CSP.

Discussion

CryptDB is much cited, but is quite insecure and introduces some loopholes. Its onion adjustable encryption architecture is indeed unidirectional, i.e., once an attribute is set down to a weak scheme such as DET, it never returns to a higher encryption level [START_REF] Kerschbaum | Adjustably encrypted in-memory column-store[END_REF]. Moreover, attributes targeted by exact match and range queries are encrypted with DET and OPE, respectively, and are vulnerable to statistical attacks. As a result, once an exact match or range query is issued, the system becomes vulnerable ever after. DET and OPE have even been shown to be much more insecure than previously expected [START_REF] Naveed | Inference Attacks on Property-Preserving Encrypted Databases[END_REF]. Additionally, peeling down onion layers induces an overhead, especially in the case of big tables.

Moreover, although CryptDB does support many types of queries, there are still many unsupported types of queries, e.g., predicate evaluation on more than one attribute. MONOMI addresses this shortcoming, but retains the same security mechanisms as CryptDB. MONOMI also induces a heavy communication overhead between the user and the CSP, since intermediate results may be exchanged several times to execute different parts of a query [START_REF] Tu | Processing Analytical Queries over Encrypted Data[END_REF].

Despite a distributed architecture, Lopes et al's solution requires a trusted server to securely execute GROUP BY queries. In our database outsourcing scenario, all service providers that are external to the user's are considered untrusted. Thus, Lopes et al's trusted server would be located at the user's, inducing costs that do not fit our scenario. Additionally, this solution does not support MIN and MAX aggregation operators directly over ciphertexts.

Finally, beside computation ability and memory capacity limitations, trusted hardware is still very expensive, which is again contrary to our scenario that aims at using cheap commodity machines in the cloud. Moreover, leaving unencrypted attributes jeopardizes ciphertext, because relationships between ciphertexts and plaintexts may reveal information about ciphertexts [START_REF] Arasu | Orthogonal Security with Cipherbase[END_REF].

Conclusion

Although encryption methods enforce privacy, in some cases, the impact on performance makes them inapplicable to cloud databases. It is indeed currently impossible to develop a system that meets both state-of-the-art cryptographic security standards and query performance requirements. In this final section, we provide a global discussion on security, performance and storage requirements for secure databases, before concluding the paper.

Security

The DET and OPE schemes, which are notably used in CryptDB, allow efficiently performing queries over ciphertexts. Database optimization techniques, e.g., usual indexing methods, can also be used to enhance query performance. However, DET and OPE leak a non-negligible amount of information and are vulnerable to statistical attacks [START_REF] Kellaris | Generic Attacks on Secure Outsourced Databases[END_REF]. For example, a large fraction of tuples from DET encrypted attributes can be decrypted by statistical attacks [START_REF] Naveed | Inference Attacks on Property-Preserving Encrypted Databases[END_REF]. The vulnerability of DET is extremely detrimental to DBs with high redundancy, e.g., data warehouses. The weak security of OPE makes it inappropriate, too. It is indeed even worse than DET in terms of security [START_REF] Furukawa | Short Comparable Encryption[END_REF][START_REF] Kellaris | Generic Attacks on Secure Outsourced Databases[END_REF]. Eventually, a recent class of generic attacks against private range query schemes invalidates much of the existing literature [START_REF] Kellaris | Generic Attacks on Secure Outsourced Databases[END_REF].

Thus, FHE looks like a more appropriate choice for encryption. In particular, PHE encryption can be used to sum ciphertexts, but the cost of decryption at the client's can remain high. As of today, it is indeed usually more efficient to decrypt data at the client's and then perform the aggregation, rather than processing aggregation queries over ciphertexts at the CSP's [START_REF] Tu | Processing Analytical Queries over Encrypted Data[END_REF]. Yet, FHE is likely to become a viable alternative in the upcoming decade, with both new FHE schemes and improvements in hardware performance. However, since preserving the order of data is necessary when running queries such as sorting, grouping and range operations, the issue of designing order preserving FHE schemes will have to be addressed.

Query Post-Processing

Tuple and table-level encryption are casually considered preferable to attribute-level encryption, because of lower startup costs at the user's and minimal storage costs at the CSP's [START_REF] Hore | Managing and querying encrypted data[END_REF]. However, the loss of data granularity is an important deficiency in scenarios such as OLAP. Thus, some solutions that use tuplelevel encryption (Section 4) handle query processing by means of auxiliary indexes at the CSP's (e.g., bucketization-based indexing) and perform final query processing at the user's. Similarly, MONOMI splits the execution of queries between the user and CSP. In such solutions, it is essential to cut down the bandwidth required to transfer intermediate results and user computational resources for user side query processing [START_REF] Tu | Processing Analytical Queries over Encrypted Data[END_REF], which is quite an open issue. CPU and storage usage at the user's must indeed be minimum for maintaining the benefits of outsourcing.

Storage Overhead

CryptDB, MONOMI and Cipherbase use attribute-level encryption, i.e., each attribute value is encrypted independently [START_REF] Arasu | Transaction processing on confidential data using Cipherbase[END_REF], at the cost of storage overhead. For instance, using classical AES in Cipher-Block Chaining (CBC) mode, a 32-bit integer is encrypted on 256 bits [START_REF] Arasu | Transaction processing on confidential data using Cipherbase[END_REF]. Worse, Paillier's PHE scheme, which is used in CryptDB, operates over 2048-bit ciphertext [START_REF] Tu | Processing Analytical Queries over Encrypted Data[END_REF]. MONOMI addresses this issue by packing multiple values from a single tuple into one PHE encryption, using Ge and Zdonik's scheme [START_REF] Ge | Answering Aggregation Queries in a Secure System Model[END_REF]. This optimization works properly for a table with many PHE-encrypted attributes, but would complicate partial updates that reset some but not all attribute values packed into a PHE tuple encryption [START_REF] Raluca | Building practical systems that compute on encrypted data[END_REF]. Thus, although security vs. performance is necessarily a tradeoff, there is still some room for improving the storage overhead of cryptographic schemes, especially for secret sharing schemes.

Computational Overhead

Operations at the CSP's should not involve any expensive arithmetic operations such as modular multiplication or exponentiation [START_REF] Sion | Towards Secure Data Outsourcing[END_REF]. However, for instance in Paillier's scheme, encrypting the sum of two clear values x and y requires multiplying ciphertexts E(x) and E(y) modulo a 2048-bit public key, i.e., E(x + y) = E(x) × E(y). Such modular multiplications are computationally expensive, especially on big tables.

MONOMI implements a grouped homomorphic addition optimization. All to-be-aggregated attributes are packed in such a way that aggregation queries can be computed with a single modular multiplication. This implies that all queries must be declared ahead of time, which it is not possible for all applications, e.g., OLAP ad-hoc navigation. Yet, performance optimization techniques, such as indexing, partitioning or view materialization, can apply onto ciphertexts. However, although they speed up some queries, they also slow down others [START_REF] Tu | Processing Analytical Queries over Encrypted Data[END_REF]. As a result, it is crucial to select a cryptographic method that meets all usage constrains. Again, a tradeoff must be defined to meet the intended level of privacy while minimizing the impact on performance.

Wrap-up

In this paper, we review the security mechanisms that can nowadays be used in the deployment of cloud databases. We particularly focus on the cryptographic schemes and the (would-be) secure systems that enable executing queries over ciphertexts without decryption. This survey highlights the potential benefits of existing solutions in a cloud computing context, but also that one must take great care about security guarantees before selecting one such solution.

Moreover, cryptography cannot prevent all attacks by malicious adversaries, e.g., Distributed Denial of Service (DDoS) attacks. It is thus essential to clearly specify the objectives of cloud database deployment, to adopt security mechanisms that are adapted to these objectives. Such preliminary work shall determine the initialization of secure protocols, the choice of cryptographic schemes, the need for a trusted third party, etc.

Finally, since computational performance is currently still a bottleneck, resorting to data distribution and query parallelization must be a priority. Thus, cloud frameworks such as Hadoop [START_REF]Hadoop[END_REF] and Spark [START_REF]Apache Spark -Lightning-fast cluster computing[END_REF] should be exploited in future secure cloud DBMSs.

Fig. 1 .

 1 Fig. 1. Database outsourcing scenario

Table 1 .

 1 Comparison of secret sharing-based methods

			Allowed queries		Additional security features
		Exact match Range Aggregate Update Integrity Statistical attacks
	Thompson et al. [68]	No	No SUM/AVG No Signature	Not robust
	Attasena et al. [11]	Yes	Yes	Yes	Yes Signature	Not robust
	Wang et al. [71]	Yes	Yes	Yes	Yes Checksum	Robust
	Agrawal et al. [3]	Yes	Yes	Yes	Yes	None	Not robust
	Hadavi et al. [36]	Yes	Yes	Yes	Yes	None	Robust

Table 3

 3 summarizes the features of the cryptographic schemes used in CryptDB.

			No	Yes
	GROUP BY	No No	Yes	Yes
	Information leakage None None Duplicates Data order

When defining an indexing method, it is important to consider two conflicting requirements. On one hand, the index should be related to the data well enough to allow efficient query execution. On the other hand, this relationship between plaintexts and the index should minimize the risk of any disclosure or loss of privacy[START_REF] Elovici | A Structure Preserving Database Encryption Scheme[END_REF][START_REF] Samarati | Data Protection in Outsourcing Scenarios: Issues and Directions[END_REF]. For example, in bucketization-based indexing, decreasing the number of buckets impairs performance, while a larger number of buckets increases the risk of data disclosure. In our database outsourcing scenario, a critical drawback of bucketization-based indexing is the loss of data granularity, which prevents grouping operations. The CSP can indeed not distinguish between tuples in buckets and the


Julián Andrés Galindo
email: julian.galindo@univ-grenoble-alpes.fr

Éric Céret
email: eric.ceret@univ-grenoble-alpes.fr

Sophie Dupuy-Chessa
email: sophie.dupuy@univ-grenoble-alpes.fr

Toward a generic architecture for UI adaptation to emotions

Keywords: Adaptation des interfaces Software architectures User interface adaptation, architecture, emotion detection

L'adaptation des interfaces homme-machine à l'exécution est une problématique bien connue en interaction homme-machine qui devient encore plus prégnante lors qu'il s'agit de prendre en compte des caractéristiques dynamiques de l'utilisateur telles que les émotions. En guise de

INTRODUCTION

Human Computer Interfaces must now be able to dynamically adapt to changes which may occur in their context of use (user, platform and environment) while preserving usability [START_REF] Calvary | A unifying reference framework for multi-target user interfaces[END_REF]. Such adaptation can deal with dynamic user properties such as emotions felt by users during interaction. As a matter of fact, emotions are recognized as important factors for considering user experience [START_REF] Reeves | How people treat computers, television, and new media like real people and places[END_REF][START_REF] Carberry | Introduction to special Issue on 'Affective modeling and adaptation[END_REF]. So an interesting approach is to use emotions for user interfaces (UI) adaptation [START_REF] Nasoz | Adaptive intelligent user interfaces with emotion recognition[END_REF]. As previous works in UI [START_REF] García Frey | UsiComp: an extensible model-driven composer[END_REF][START_REF] Paterno | MARIA: A universal, declarative, multiple abstraction-level language for service-oriented applications in ubiquitous environments[END_REF], such approaches need to be generic. One element of genericity is the architecture. In [START_REF] Galindo | Toward a UI Adaptation Approach Driven by User Emotions[END_REF], we propose an architecture, Perso2U, for UI adaptation to emotions. This architecture seems to be generic as adaptation is based on rules that do not depend on emotion detection tools. However, the success of UI adaptation depends on the finding of relevant emotions. Hence a crucial part of the architecture is emotion detection and particularly its independence from emotion recognition tools.

Nowadays, there are many emotion recognition tools such as Microsoft API 1 ,FaceReader2 and Affdex 3 .These tools usually provide seven basic emotions with some uncertainty. There is clearly a risk of divergence between them because of the accuracy differences in face detection algorithms [START_REF] Brodny | Comparison of selected off-the-shelf solutions for emotion recognition based on facial expressions[END_REF]. These divergences could lead to erratic emotion identification and thus to unreliable and unstable adaptations. So our question is related to the possibility to use any of these tools in our architecture. That is the point studied in this paper to show the possibility of a generic interpretation of emotions. In this paper, we propose to compare three face emotion recognition tools used in Perso2u. We hypothesize that from these tools, the inferring engine can provide similar emotion results (positive, negative, surprise and neutral) during the interaction. To identify this similarity, we conduct an experiment with 40 users across 4 websites. This paper describes the results of this experiment and its impact on the PersoU2 architecture.

The following section of the paper presents the related work about UI adaptation to emotions. The third section describes the Perso2u architecture. Next we present an experiment that compares three emotion recognition tools. The last section summarizes our results and presents future work.

RELATED WORK

Users' emotions have been modeled in many works [START_REF] Hudlicka | Increaing Sia Architecture Realism by Modeling and Adapting to Affect and Personality[END_REF][START_REF] Lisetti | MAUI: a Multimodal Affective User Interface Sensing User's Emotions based on Appraisal Theory-Questions about Facial Expressions…[END_REF]. In such works, emotions are studied in relation to other users' features such as learnability or performance. However, none of them deals with reusing this knowledge about the user for exploring deeply UI adaptation. Few other proposals use emotion recognition to adapt the UI [START_REF] Nasoz | Adaptive intelligent user interfaces with emotion recognition[END_REF][START_REF] Hudlicka | Assessment of User Affective and Belief States for Interface Adaptation: Application to an Air Force Pilot Task[END_REF][START_REF] Hudlicka | Increaing Sia Architecture Realism by Modeling and Adapting to Affect and Personality[END_REF]. In this paper, we are particularly interested in the genericity of their architecture, i.e. in the independence of their adaptation process from the emotion recognition tool used. First, the Affect and Belief Adaptive Interface System (ABAIS) [START_REF] Forbes-Riley | Designing and evaluating a wizarded uncertainty-adaptive spoken dialogue tutoring system[END_REF][START_REF] Hudlicka | Assessment of User Affective and Belief States for Interface Adaptation: Application to an Air Force Pilot Task[END_REF] is based on four modules: User state assessment, impact Prediction, strategy Selection, and GUI Adaptation. The first one is in charge of the emotion inference, which combines user information and a rule-based approach to infer the affective user state. Even if it is not explicit in the papers, the process appears to be independent from recognition tools thanks to these rules. But only one emotion, anxiety, is considered and UI adaptation only affects icons, displays, notifications and custom configuration. Adaptation does not consider the structure (layout) of the UI.

Second, Nasoz proposes an adaptive intelligent system [START_REF] Nasoz | Adaptive intelligent user interfaces with emotion recognition[END_REF] relying on the recognition of affective states from physiological signals (sensors) based on a Multimodal Affective User Interface architecture [START_REF] Lisetti | MAUI: a Multimodal Affective User Interface Sensing User's Emotions based on Appraisal Theory-Questions about Facial Expressions…[END_REF]. The emotion inference analyses data given by emotion recognition tools (e.g. facial analysis) while the adaptation relies on a machine learning technique that considers some user's attributes such as recognized emotion, personality trait, age, gender and emotion frequency. Independence from recognition tools could be ensured thanks to the independence of the inference of emotions from these tools. However, adaptation rules should be made able to deal with variations in user parameters like emotion frequency (e.g. from rarely to often). To summarize, only two main architectures exist. If they seem to be generic, they have (1) limited emotions and UI adaptations and (2) fixed adaptation rules. To avoid this drawback, we propose an architecture called Perso2U.

Perso2U ARCHITECTURE

The Perso2U architecture (Fig. 1) is composed of three components: the Inferring Engine , the Adaptation Engine and the Interactive System . The Inferring engine is in charge of dynamically deducing the value of the context of Use (users with their emotions, platform, environment). Emotions are detected thanks to external Tools such as FaceReader. Then the emotion Wrapper filters and aggregates the acquired emotions values to find whether the current user emotion is positive (happiness), negative (anger, contempt, disgust, fear, and sadness), surprise or neutral. Finally inferred emotions are sent to the Adaptation Engine with other contextual information. This engine elicits the right UI adaptation: from the contextual information [START_REF] Céret | System and method for magnetic adaptation of a user interface[END_REF] , it (a) selects a UI variant (i.e. a predefined UI structure) among all available variants for the needed UI and (b) computes parameters (e.g. color, font) for even better adapting the chosen variant to the context of use. Then it displays the variant and gives it the computed parameters to the interactive module, which applies the parameters, thus displaying the appropriate adapted UI. To extend, a more complete analysis of Perso2u which includes descriptions of functions, components, examples, current prototype and feasibility results is evidenced in [START_REF] Galindo | Toward a UI Adaptation Approach Driven by User Emotions[END_REF].

EXPERIMENTAL STUDY

The experimental study aims at exploring one initial and promising criterion for the genericity of the architecture: the independence from the way of detecting emotions. So the inferring engine must be able to send appropriate emotions to the adaptation engine whatever the detection tool is. We will show that from three different detection tools, the inferring engine can infer similar results.

Goal and hypothesis

The objective of this experiment is to examine how similar are emotions, i.e. contempt, happiness, anger, disgust, fear, sadness, surprise and neutral 4 ,detected by different face emotion recognition tools. For getting reliable comparison, we needed that these tools start from the same input, the users' pictures taken during interaction. We also wanted the tools to provide similar sets of emotions, so that their aggregation is meaningful. Three tools could be identified that answer these constraints: Affectiva, FaceReader and Microsoft emotion API. So the experiment hypothesis is: H1: the emotions detected by Affectiva, FaceReader and Microsoft emotion API are similar enough to be able to infer from them similar aggregated emotions: positive (happiness), negative (anger, contempt, disgust, fear and sadness), surprise and neutral.

Experimental method

Four UI versions of a same travel website were designed and developed [START_REF] Dupuy-Chessa | Considering aesthetics and usability temporalities in a model based development process[END_REF]. The websites differ by two factors that influence users' emotions while interacting with a UI: usability and aesthetics. So by combining two values (low vs. high) for these two factors (aesthetics and usability), four versions of the website were created (Fig. 2).

Procedure, tasks and participants

Each participant was assigned to one version of the travel website. While he/she was interacting with the website, his/her emotions were detected based on user taken photos every 10 seconds. Second, to ensure that participants are involved enough in the interaction, they had to answer an online questionnaire corresponding to three tasks to achieve: (1) look for a 5-stars hotel offering a visit in the desert, (2) look for a specific hotel with a breakfast plan and (3) look for a hotel circuit in a specific location. Lastly, 40 persons participated to the experiment, 10 participants per website. The participants were 50% male from 21 to 67 years old and 50% female from 23 to 63 years old (mean male age 34, σ=13.95 and mean female age 27 with σ=12.34).

A. Before (300x260) B. After (300x320).

Interaction Data and Images Correction

During the experiment, the following triple data is captured per user: User, UI and the Survey which results in a set of 8 emotions, 67 UI elements and 41 Survey attributes across 40 users. To clarify, user features such as identifier (1 to 40), age, gender and a set of emotions: happiness, contempt, fear, anger, sadness, disgust, surprise and neutral (when available) with values from 0 to 1. Furthermore, table 1 and 2 illustrates interaction data for each web site: the number of clicks, the number of images detected, avg. time and page views per website. These measures reached in total 2754,1240,122 and 905 respectively.

Measures and method

User pictures were sent to the 3 emotions detection tools for getting the emotions detected in realtime for FaceReader and Microsoft in contrast to Affectiva where post analysis was done. Before being able to compare emotions detected by tools, we had to make some corrections. As a matter of fact, to get realistic values from tools during the interaction, participants were not required to have a predefined position (rigid head or hand positions) as it is usually done. But some images were not good enough for an interpretation with FaceReader. So a face image correction was done for FaceReader for every image. The correction was done by adding a white rectangle at the bottom of the image without affecting the user face as illustrated in Fig. 3. As a benefit, it was possible to improve the image detection, quality and gather emotion values (Fig3. B). Finally, the 1226 captured images were sent to Microsoft API and FaceReader and Affdex, which could recognize respectively 880, 703 and 706 of them. In other words, each tool produced respectively an error rate of 28.22%, 42.65% and 42,41%. Each tool produced for each picture a vector of emotion measures with values from 0 to 1: happiness, contempt, fear, sadness, anger, disgust, surprise and, for Microsoft API and FaceReader, neutral. Then distances for each emotion measure across all tools were computed by using Euclidean distances to compare how similar they are [START_REF] Kalita | Recognition of Facial Expression Using Eigenvector Based Distributed Features and Euclidean Distance Based Decision Making Technique[END_REF]. This process relies on a distance function applied to the three vectors: emotionDistance=distance {VfaceReader,i, VMSAPI,i, VAffDex,i}/n where Vx,i is the value of emotion I in vector of tool X, and n refers to the number of emotions measures across all vectors. This division was necessary to obtain a central value per data set (vector). To illustrate, happiness distance is equal to the distance among VfaceReader,happiness, VMSAPI,happiness, VAffDex,happiness which is then divided by the number of vector items

Feasibility of a generic architecture

The results confirm that there are similar recognized emotions among the three tools: low distances were found with values under 2.0% for all emotions (happiness, contempt, disgust, sadness, fear, anger and surprise) as shown in Fig. 4 and tables 3, 4 and 5. In fact, more similarity is shown in negative than positive emotions with a global average of 0.96 and 0.84% for each group (Table 5 & 4). While neutral was almost a double than surprise (0,8%, Table 3).

Table 5: Distances among emotion recognition tools in negative emotions.

tools disgust sadness fear anger contempt avg. a-f 0,0092 0,0151 0,0070 0,0085 0,0204 1,20% a-m 0,0102 0,0119 0,0036 0,0045 0,0190 0,98% f-m 0,0035 0,0115 0,0061 0,0067 0,0070 0,70% avg. 0,77% 1,28% 0,55% 0,66% 1,55% 0,96% a: affectiva, f: faceReader and m: microsoft.

Failed emotion recognition

Fig. 5 evidences that there are cases where the emotion recognition fails for a specific time slot. In fact, during this user interaction, there were 2, 4, and 2 failed emotion detections for Affectiva, FaceReader and Microsoft in different time slots and UI variances. In such case, the adaptation may need to consider a time range rather than a time slot to define the user response at interacting with the UI.

Experiment limitations

Although these results are encouraging, some restrictions should be noted. First, all presented tools rely on the same emotion detection method (user face image) without considering others such as eye tracking, heart rate or video trace analysis. Second, other elements in the context of use have not been considered such as noisy and light environment or different platforms (e.g. mobile). Lastly, correlations between users' declared and recognized emotions will extend the inferring engine validation.

This paper presents an architecture named Perso2u for UI adaptation emotions and an experiment to show its independence from emotions detection tools. It validates that it is feasible to have similar emotion values with different tools as first step (inferring) in a generic architecture to drive UI adaptation based on emotions. More experiments will be necessary to prove the correlation between the declared emotions and the inferred ones in order to validate the inferring engine.

From the inferred emotions, some adaptation rules must be implemented and experimented to validate the global architecture.

Figure 1 :

 1 Figure 1: Global schema of the Perso2U architecture.

Figure 2 :

 2 Figure 2: Four variants of a web site user interface.

Figure 3 :

 3 Figure 3: FaceReader image correction (A and B).

  a: affectiva, f: faceReader and m: microsoftTable 4: Distances among emotion recognition tools in positive emotion.

Figure 4 :

 4 Figure 4: Distances among emotion recognition tools.

Figure 5 .

 5 Figure 5. A User Happiness detection for each tool.

Table 1 :

 1 User interaction data collected by clicks and images.

		Clicks	Images
	w1	515	226
	w2	549	280
	w3	944	354
	w4	746	380
	Total	2754	1240

Table 2 :

 2 User interaction data collected by avg. interaction time and page views. w1=web site 1, w2=web site 2, w3=web site 3 and w4=web site 4.

		avg. Interaction time	page
		(minutes)	views
	w1	32	289
	w2	29	172
	w3	27	216
	w4	34	228
	Total	122	905

Table 3 :

 3 Distances among emotion recognition tools in surprise and neutral emotions.

www.microsoft.com/cognitive-services/en-us/emotion-api

www.noldus.com/human-behavior-research/products/facereader

www.affectiva.com/solutions/affdex/

Not available in Affectiva (JS SDK).


Véronique Terrier
email: veronique.terrier@unicaen.fr

Some computational limits of trellis automata

Keywords: xiyi ∈ {ab, ba, bb} for i = 1,

We investigate some computational limits of trellis automata. Reusing a counting argument introduced in [4], we show that: {x1 . . . xny1 . . .

Introduction

Trellis automata are one of the simplest parallel language recognizer. Introduced by Dyer [START_REF] Dyer | One-way bounded cellular automata[END_REF], as real-time one-way bounded cellular automata, they represent a significant class of formal languages with low complexity. Notably, they are equivalent to the linear conjunctive grammars [START_REF] Okhotin | Automaton representation of linear conjunctive languages[END_REF]. In spite of their simplicity, they have a rich computational ability and recognize various languages. In this regard, the linear context free, the visible pushdown, the poly-slender context free languages are known to be all recognized by trellis automata [START_REF] Čulík | Systolic trellis automata[END_REF][START_REF] Okhotin | On the equivalence of linear conjunctive grammars and trellis automata[END_REF][START_REF] Okhotin | Input-driven languages are linear conjunctive[END_REF][START_REF] Čulík | Variations of the firing squad problem and applications[END_REF][START_REF] Terrier | Recognition of poly-slender context-free languages by trellis automata[END_REF].

On the other side, some limits are known. Trellis automata are not closed under concatenation and do not contain all (and even deterministic) context-free languages. To support these claims, several languages have been shown not to be trellis languages [START_REF] Terrier | On real time one-way cellular array[END_REF][START_REF] Terrier | Language not recognizable in real time by one-way cellular automata[END_REF][START_REF] Okhotin | Input-driven languages are linear conjunctive[END_REF]:

the context free language L 1 L 1 square of L 1 = {1 k 0u10 k : k > 0, u ∈ {0, 1} * } the language {uvu : u, v ∈ {0, 1} * , |u| > 1}, the deterministic context free (and LL [START_REF] Čulík | Variations of the firing squad problem and applications[END_REF]) language {c m a l0 ba l1 b • • • a lm b • • • a lz bd n : m, n, l i ≥ 0, z ≥ 1, l m = n}.

The proofs rely on counting arguments which set conditions on the structure of trellis languages.

Here we will reuse another counting argument introduced in [START_REF] Grandjean | Linear functional classes over cellular automata[END_REF] in the context of functional computation, which demonstrated that the reverse operation is not realizable in minimal time on cellular automata. This argument will allow to exhibit some new prerequisite for a language to be recognized by trellis automata. As an application, we will prove that the language {x 1 . . . x n y 1 . . . y n : x i y i ∈ {ab, ba, bb} for i = 1, . . . , n} is not a trellis language.

The paper is organized as follow. Section 2 recalls the basic definitions about trellis automata. Section 3 describes the notion of language factors diagram which can be interpreted as the language counterpart of trellis computation. Section 4 considers the patterns which may occur in the trellis computation and the ones which may occur in the factors diagrams, and also their correlation. Section 5 states a necessary condition regarding the patterns for a language to be recognizable by trellis automata. Section 6 shows that the language {x 1 . . . x n y 1 . . . y n : x i y i ∈ {ab, ba, bb} for i = 1, . . . , n} does not fulfill such a condition.

Trellis automaton

A trellis automaton is one of the simplest parallel language recognizer. Its underlying structure is a triangular array with sites arranged in staggered rows, as shown below.

x1 x2 x3 x4 x5 x6
the result is read on the topmost site the input is fed to the bottom row A trellis automaton on an input of size 6

Formally, a trellis automaton is specified by a tuple (Q, Σ, Q acc , δ) where

-Q is the finite set of states -Σ ⊂ Q is the input alphabet -Q acc ⊂ Q is the set of accepting states -δ : Q 2 → Q is the transition function
If n is the length of w, the trellis has height n and contains on its i-th row, the

n + 1 -i values δ(x 1 . . . x i ), δ(x 2 . . . x 1+i ), . . . , δ(x n+1-i . . . x n )
A trellis automaton is said to accept (resp. reject) a word w ∈ Σ * , if on input w the topmost cell enters an accepting (resp. non-accepting) state.

Definition 1 (Trellis language). A language L over an alphabet Σ is a trellis language if there exists some trellis automaton (Q, Σ, Q acc , δ) which accepts exactly the words w ∈ L. The accepting state a marks the topmost cell of every triangle whose basis is a factor in Mi a . The accepting state d marks the Dyck words, a marks the proper prefixes of Dyck words, b marks the proper suffixes of Dyck words, r marks all the other words.

A fundamental feature of trellis automata has been noticed by Čulík:

Property 1 (Outside-context independance [START_REF] Čulík | Variations of the firing squad problem and applications[END_REF]). The computation of any word contains the computations of all its factors.

As it can be seen in Example 1 or 2, the automaton which tests the input w processes together all its factors.

Factors diagram for a language

As a matter of fact, Property 1 has strong implications on the structure of languages recognized by trellis automata. To make them explicit, let us first introduce the language counterpart of trellis computation.

Definition 2 (Factors diagram).

Let L be a language on an alphabet Σ.

The indicator function of L, noted 1 L , is defined by

1 L : Σ * → {0, 1} w → 1 if w ∈ L 0 if w / ∈ L Let w = x 1 . . .
x n be a word. The factors diagram of w for the language L, denoted Γ L (w), is a triangular array which records the values of all slices of w.

If n is the length of w, the factors diagram has height n and contains on its i-th row, the n + 1 -i values

1 L (x 1 . . . x i ), 1 L (x 2 . . . x 1+i ), . . . , 1 L (x n+1-i . . . x n ) a a b a b b a b a a b b
1 1 0 1 0 0 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 1 1 0 0 0 0 0 0 0 1 0 0 1 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 (a) ΓMi a (w) for Mia, the language of words with a in the middle a a b a b b a b a a b b 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 (b) ΓDyck(w) for the Dyck language 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 The following proposition formally describes the relationship between automaton evolutions and factors diagrams. Proposition 1. Let A = (Q, Σ, Q acc , δ) be any trellis automaton, L be the language accepted by A and 1 acc be the indicator function of the set of accepting states:

1 acc : Q → {0, 1} q → 1 if q ∈ Q acc 0 if q / ∈ Q acc
For any word w ∈ Σ * , given its automaton computation C A (w) and its factors diagram Γ L (w), we have:

1 acc (C A (w)) = Γ L (w)
4 Trellis automaton patterns and language patterns Therefore, a prerequisite for a language to be a trellis one, is the following. All patterns which occur in the factors diagrams of such a language, must arise in the evolutions of some trellis automaton. Let us focus at the patterns of triangular shape.

Definition 3 (Characteristic pattern). Let L be a language. A characteristic pattern of height h is any triangle of height h extracted from a factors diagram of L. P L (h) will refer to the set of all distinct characteristic patterns of height h. We may describe the automaton patterns in the same way:

Definition 4 (Automaton patterns). Let A = (Q, Σ, Q acc , δ) be a trellis automaton. An automaton pattern of height h is any triangle of height h extracted from a computation of A. P A (h) will refer to the set of all distinct automaton patterns of height h.

However, trellis automata are deterministic local devices. So, for an automata pattern, the bottom row completely determines the subsequent rows. In other words, an automata pattern of height h can be viewed as a row pattern of length h complemented with its consequences. As shown earlier in [START_REF] Terrier | On real time one-way cellular array[END_REF], it entails a necessary condition for a language to be recognizable by a trellis automaton, regarding to the number of its characteristic patterns:

Lemma 1. If L is a trellis language then the number of characteristic patterns of height h, |P L (h)|, is in 2 O(h) .
Proof. Assume that L is a language accepted by some trellis automaton A = (Q, Σ, Q acc , δ). According to Proposition 1, the characteristic patterns match the projection of the automaton patterns:

P L (h) = 1 acc (P A (h)). In terms of cardinal, it means that |P L (h)| ≤ |P A (h)|.
Moreover, the number of automaton patterns of height h is bounded by the number of distinct rows of length h where values range in Q:

|P A (h)| ≤ |Q| h .
Now, as the area of a characteristic pattern of height h is in Θ(h 2 ) and its values are 0 or 1, we can find languages whose set of characteristic patterns grows larger than 2 O(h) . Using this counting argument, it has been shown that the following languages are not trellis ones:

-The context-free language L 1 L 1 , square of the linear language

L 1 = {1 k 0u10 k : k > 0, u ∈ {0, 1} * }, since |P L1L1 (h)| ∈ 2 Θ(h 2 )
. See [START_REF] Terrier | On real time one-way cellular array[END_REF]. -The deterministic context-free language (and even LL(1) language

) L = {c m a l0 ba l1 b • • • a lm b • • • a lz bd n : m, n, z ≥ 1, l i ≥ 0, l m = n}, since |P L (h)| ∈ Ω(h!). See [8].
Of course, this criterion is only a necessary condition and not a sufficient one. Another drawback of this approach is that to estimate the growth rate of the characteristic patterns number of height h as h grows large, is not usually an easy task. By the way, the previous witness languages are ad hoc languages to fulfill the counting requirement. And the status of more common languages remains as yet unknown. Two candidates are currently mentioned:

-The balanced language over {a, b} defined as the set of strings with the same number of symbols a and b:

Eq = {w ∈ {a, b} * : a (w) = b (w)}
-The copy language defined as the set of words repeated twice: it will not allow us to determine whether they are trellis languages or not.

Copy = {ww : w ∈ {a,
Here we will focus on a subfamily of the characteristic patterns composed of horizontal stripes.

Definition 5 (Stripes patterns).

A stripes pattern is a characteristic pattern such that all the values within each row are equal. The characteristic string of a stripes pattern of height h is the binary string c = c 1 • • • c h of length h where c i is the 0 or 1 value of the i-th row of the stripes pattern.

An automaton pattern π would be said to have a characteristic string c if its projection 1 acc (π) is a stripes pattern of characteristic c.

Note that the characteristic string completely characterizes the stripes pattern. And so, whatever the language, the number of its stripes patterns of height h is bounded by 2 h . Regardless of the fact that the subfamily of stripes patterns is not so large and even within the bound defined in Lemma 1, it has been proved that any trellis automaton could not display all of them: Proposition 2 (Grandjean, Richard, Terrier [START_REF] Grandjean | Linear functional classes over cellular automata[END_REF]). For any trellis automaton A, there exist some stripes patterns which never occur in the space-time diagrams of A.

Along the same lines, Proposition 2 could be refined to deal with languages exhibiting not necessarily all stripes patterns. Definition 6. For any language L, C L will refer to the set of characteristic strings whose corresponding stripes patterns occur in L. Give, any subset F ⊂ C L , the integer α F h will refer to the minimal number of double length extensions of every string of length 2 h within F:

α F h = min c∈F ,|c|=2 h (|{d ∈ F : c is a prefix of d and |d| = 2|c|}|) Proposition 3.
If L is a language which admits a subset F of characteristic strings such that the sequence (α F h ) is monotonic and divergent, then L is not a trellis language.

The counting argument used to prove the proposition is based on the next technical fact. Fact 1. Let (α h ) be any monotonic sequence of positive integers which is divergent: α h+1 ≥ α h for all h, and lim h→∞ α h → ∞. Let C be any positive constant.

Then the sequence (u h ) defined recursively by:

u 0 = C and u h+1 = u 2 h α h converges to 0.
Proof. First, observe that

u h = C 2 h / h-1 i=0 α 2 h-i-1 i
Second, by assumption, there exists an index H such that α h ≥ C + 1, for all h ≥ H. Then for h ≥ H,

u h ≤ C 2 h / h-1 i=H (C + 1) 2 h-i-1 = C 2 h /(C + 1) 2 h-H
So the sequence (u h ) converges to 0.

Proof (Proposition 3). Assume that L is a language accepted by some trellis automaton A = (Q, Σ, Q acc , δ). We will construct a sequence of strings w i of length 2 i belonging to F such that the number of automaton patterns with characteristic w i is bounded by u i . Then, according to Fact 1, we will have u I < 1 for I large enough. That means there will be no automaton pattern with characteristic u I and hence w I would not be a characteristic string of L. Thus the assumption that L is a trellis language, would lead to a contradiction.

The construction of the sequence of strings w i is done by recurrence:

The base case. For i = 0, the automaton patterns of height 1 are reduced to one site and their number is bounded by the cardinal of Q. So there are at most C = |Q| automaton patterns with characteristic string 0 or 1. Let set w 0 be a string of length 1 belonging to F and u 0 be |Q|.

X Y Z T c1 c2 c3 c 2 i c 2 i +1 c 2 i+1
wi Fig. 3: Subdivision of an automaton pattern in four patterns X, Y , Z and T

The inductive step. Consider all automaton patterns of height 2 i+1 having a characteristic string whithin F which is a double length extension of w i . As depicted in Figure 3, we can divide such a kind of pattern in four sub-patterns X, Y , Z and T where X, Y and Z are of height 2 i and also where X and Y share the characteristic w i . By recurrence assumption, the number of automaton patterns of characteristic w i is bounded by u i and so the number of couples (X, Y ) is at most u 2 i . Furthermore the sub-patterns Z and T depend only on X and Y . That is to say the number of automaton patterns whose characteristic strings are extensions of w i is bounded by u 2 i . Now, since the minimal number of extensions of w i whithin F is α i , the average number of automaton patterns per extension is bounded by u i+1 = u 2 i /α i . In other words, there is one extension w i+1 of w i with length 2 i+1 and belonging to F such that the number of automaton patterns with characteristic w i+1 is bounded by u i+1 .

6 Some non trellis language Now we will apply the previous criterion to show that the language NO aa = {x 1 . . . x n y 1 . . . y n : x i y i ∈ {ab, ba, bb} for i = 1, . . . , n} ∪ {w ∈ {a, b} * : w is of odd length} is not a trellis language. As an aside, notice that NO aa is not a context-free language although its complement Mi a Mi a is a context-free one.

As preliminary, let us look at an example. Figure 4 depicts the factors diagram on the input word ω bab 12 abbbabaaabbab ω . The dark sites mark the 0 values (i.e., the factors not in NO aa ), the light sites mark the 1 values. We observe that the black horizontal stripes in the upper part match the symbols a of the input. Proposition 4. The language NO aa = {x 1 . . . x n y 1 . . . y n : x i y i ∈ {ab, ba, bb} for i = 1, . . . , n} ∪ {w ∈ {a, b} * : w is of odd length} is not a trellis language.

Proof. According to Fact 2, every string of F = {01, 11} * is a characteristic string of NO aa . Besides, within F, every string c 1 1 . . . c 2 h-1 1 of length 2 h is the prefix of 2 h-1 strings of double length: {c 1 1 . . . c 2 h-1 1e 1 1 . . . e 2 h-1 1 : e 1 , . . . , e 2 h-1 ∈ {0, 1}} ⊂ F. Hence α F h = 2 h-1 and so the sequence (α F h ) is monotonic and divergent. Then it follows from Proposition 3 that NO aa is not a trellis language.

As a matter of fact, it can be shown in the same way that the language NO ab = {x 1 . . . x n y 1 . . . y n : x i y i ∈ {aa, ba, bb} for i = 1, . . . , n} ∪ {w ∈ {a, b} * : w is of odd length} is not a trellis language. At the same time, neither Mi a Mi a nor Mi a Mi b are trellis languages.

Conclusion

As illustrated in this paper, to make explicit limitations on the computational ability of trellis automata, the analysis of the characteristic patterns associated to trellis languages, is a significant approach. But we are still far from having fully exploited such tools.

The language Mi a Mi a and its derived forms have been shown not to be trellis ones. Despite the fact it gives us good reason to believe that the Copy language, coinciding with (Mi a Mi b ) ∩ (Mi b Mi a ) ∩ {aa, ab, ba, bb} * , is not recognizable by trellis automata, the question remains still open. Regarding the Okhotin's grammars hierarchy, another challenge would be to determine whether the language (Mi a Mi a ) is representable by a conjunctive grammar or not [START_REF] Okhotin | Conjunctive and boolean grammars: The true general case of the context-free grammars[END_REF].

Example 1 .a b a b b a b a a b b c b c b b c b c c b b a b a b b a b a a b b c b b c b c c b b a b b a b a

 1 The trellis automaton ({a, b, c}, {a, b}, {a}, δ) accepts the set of strings of odd length whose middle symbol is a: Mi a = {uav : u, v ∈ {a, b} * and |u| = |v|} a

Example 2 .

 2 The trellis automaton ({a, b, d, r}, {a, b}, {d}, δ) recognizes the set of Dyck words over {a, b} a a b a b b a b a a b b a d r d b r d r a d b a a b b r b a r a

Fig. 1 :Example 3 .a a b a b b a b a a b b a d r d b r d r a d b a a b b r b a r a b a d b r b r a r d a b r b r r a b d r b r r r d a b r r r

 13 Fig. 1: Factors diagram Γ L (w) on word w = aababbabaababb for the language L

Fig. 2 :

 2 Fig. 2: The factors diagram is the projection of the automaton computation

Example 4 .

 4 Consider Mi a the language of strings with a in the middle. The factors diagrams of Mi a consist of vertical stripes of only 0 or only 1.

Example 5 .

 5 The automaton pattern 2, is entirely defined by its bottom row d r d b (and, of course, by the automaton rules).

  b} * } Here we will look at the language Mi a Mi a and the variant Mi a Mi b where Mi a (resp. Mi b ) stands for the set of odd length words with a (resp. b) in the middle: Mi a = {xay ∈ {a, b} * : |x| = |y|} Making use of an approach introduced in [4], we will show that Mi a Mi a and Mi a Mi b are not trellis languages. But although they are closely related to the Copy language and its negative variant: Copy = (Mi a Mi b ) ∩ (Mi b Mi a ) ∩ {aa, ab, ba, bb} * {ww : w ∈ {a, b} * } = (Mi a Mi a ) ∩ (Mi b Mi a ) ∩ {aa, ab, ba, bb} * = Eq ∩(Mi a Mi a )

Fig. 4 :Fact 2 .

 42 Fig. 4: The factors diagram on ω bab 12 abbbabaaabbab ω for the language NO aa