Léopold Ouairy
email: leopold.ouairy@inria.fr

Hélène Le-Bouder
email: helene.le-bouder@imt-atlantique.fr

Jean-Louis Lanet
email: jean-louis.lanet@inria.fr

Protection of systems against fuzzing attacks

Keywords: unsupervised machine-learning, k-Nearest-Neighbors, vulnerability detection, fuzzing attacks, Java Card, Chucky

A fuzzing attack enables an attacker to gain access to restricted resources by exploiting a wrong specification implementation. Fuzzing attack consists in sending commands with parameters out of their specification range. This study aims at protecting Java Card applets against such attacks. To do this, we detect prior to deployment an unexpected behavior of the application without any knowledge of its specification. Our approach is not based on a fuzzing technique. It relies on a static analysis method and uses an unsupervised machine-learning algorithm on source codes. For this purpose, we have designed a front end tool fetchVuln that helps the developer to detect wrong implementations. It relies on a back end tool Chucky-ng which we have adapted for Java. In order to validate the approach, we have designed a mutant applet generator based on LittleDarwin. The tool chain has successfully detected the expected missing checks in the mutant applets. We evaluate then the tool chain by analyzing five applets which implement the OpenPGP specification. Our tool has discovered both vulnerabilities and optimization problems. These points are then explained and corrected.

Introduction

A fuzzing attack aims at sending crafted messages to a running program in order to test all the possible paths of its control flow. With this method and according to the system response, an attacker can detect a deviation of the program's expected behavior, in response to his message. This same crafted message can perturb the program's state machine and change its current state. By modifying the state of the program, an attacker can illegally gain access to resources stored onto the Java Card. One of the reasons for this illegal transition in the state machine can be related to the absence of input validation tests. Such a forgotten condition is called a missing-check. With this work, we aim at detecting those missing-checks before a fuzzing attack. Our approach is not based on a fuzzing attack, but on a static analysis of the source codes. To achieve this task, we have created three tools. The first one, ChuckyJava is an adaptation of Chucky-ng [START_REF] Yamaguchi | Chucky: Exposing missing checks in source code for vulnerability discovery 1[END_REF]8] for Java. The second tool we have designed is fetchVuln. It is a front-end layer above ChuckyJava which aims at automating tests of ChuckyJava. Moreover, it gathers all the outputs that ChuckyJava generates and it processes them to produce a report about vulnerable methods of the applet under analysis. The last tool is LittleDarwinJC which is based on LittleDarwin [START_REF] Parsai | Littledarwin: a feature-rich and extensible mutation testing framework for large and complex java systems[END_REF]. Its objective is to generate Java mutant applets and it enables us to characterize and evaluate the ability of fetchVuln to detect those mutants. We have tested fetchVuln on an applet set implementing OpenPGP. This evaluation has brought to the fore two optimization problems while we have discovered two vulnerabilities in the implementations. The context is presented in section 2. The state of the art is exposed in section 3. Section 4 explains the functioning of Chucky-ng. The adaptation phase is shown in section 5. We expose our methodology in section 6. Then, we describe our results and discuss the evaluation of the performances in section 7. The limitations of our tool are exposed in section 8. To finish, we present our conclusion in section 9.

Context

A program with a state machine accepts only a set of commands from a specific state. Such commands enable the program to change its state from one to another. A specification clarifies both states and transition links that shall be implemented for a program.

OpenPGP is an open version of the Pretty Good privacy (PGP) standard defining encryption formats. Fig. 1 shows a fragment of the OpenPGP state machine specification with the command COMPUTE_DIGITAL_SIGNATURE. It allows or denies the data to be signed before being written to the card. The S node (state Selected) is where the program accepts messages. During the process, the state checks the value of the incoming message in order to determine which command to execute. This is represented by the test on transition from state S to the state 1. The state machine then checks the parameter PW1 (Password 1) if necessary. If verifyPW1() fails, then the state machine enters the ERROR state. If the test succeeds, the applet can perform the signature operations. By entering in the state S, the program waits for another command. To illustrate a missing-check, suppose that the condition verifyPW1() from node 2 to node 3 is missing does not exist. It is possible for an attacker to enter state 3 with a wrong PW1. 3 State of the art Dynamic and hybrid protection Dynamic and hybrid protection techniques consist in filtering user controlled inputs. We have found this kind of input cleaning on web application domains. As an example, the XSS attack mitigation which uses (UrlEncoder or HtmlEncoder[9] for example) to filter user controlled inputs. This step has to ensure that the message format and its application domain are correct. One drawback of this mitigation method is the possibility of missing cases against a new attack and it needs to be updated to improve the filtering accuracy. If an attacker has access to the source code of the library, then he can adapt its inputs to bypass the secure filter. In her PhD [START_REF] Kamel | Sécurité des cartes à puce à serveur web embarqué[END_REF], Kamel proposes to implement a filtering library API JCXSSFilter. She chooses to adapt it to fit in the OWASP's ESAPI [START_REF]Owasp enterprise security[END_REF] open-source web application. Added to this, the use of such secure libraries add an extra overhead in the system.

Formal methods

The tools Z [START_REF] Spivey | Understanding z: a specification language and its semantics[END_REF], VDM [START_REF] Jones | Systematic software development using vdm[END_REF] rely on formal methods. They aim to mathematically specify the expected behavior of a sequential system by using sets, relations and functions. Burdy et al.[2] present an experiment on formal validation of Java Card applets. To specify a behavior, the user has to annotate his Java classes with the Java Modeling Language. One of the drawbacks of this method is the necessity to specify the right behavior for all classes. Depending on the size of the project, this step can be difficult. Added to this, if the specification of the applet changes, the developer has to adapt his code in order to fit it to the new expected behavior.

Static Analysis A concolic analysis performs both concrete and symbolic analysis for a given source code. This is the case for the tool JDart [START_REF] Luckow | Assisted discovery of vulnerabilities in source code by analyzing program slices 1, 3 9[END_REF] which relies on this kind of static analysis. For instance, the symbolic execution aims at discovering the paths a program can follow, while the concrete one proposes valid inputs to use in order to follow a specific path. In the static analysis field, taint analysis techniques aims at following the evolution of an input through a program. To illustrate this method, suppose that one wants to follow a parameter. To do this, the tool has to taint this variable. Then, every variable which uses this tainted parameter gains the same taint color. Pixy[4] uses taint analysis. It aims at propagating limited string value information in order to handle some of PHP's most dynamic features. One drawback of a concolic analysis is that if there is a lot of paths, then the analysis could never finish its execution.

Text mining Text mining is a technique which consists in extracting the terms (words) present in software components (files) and their frequencies. Then, the term frequencies are correlated in order to build a model which predicts if a given software component is vulnerable. This method is implemented in the tool of Scandariato et al. [START_REF] Scandariato | Predicting vulnerable software components via text mining 3[END_REF].

Machine learning The tool entitled Chucky-ng[8], based on Chucky [START_REF] Yamaguchi | Chucky: Exposing missing checks in source code for vulnerability discovery 1[END_REF], relies on machine-learning to discover vulnerabilities in a source code. It extracts and compares functions with a unsupervised machine-learning algorithm in order to flag the vulnerable ones. Chucky-ng relies on the k-Nearest-Neighbors [START_REF] Sayad | K nearest neighbors[END_REF] algorithm. An important advantage for this tool is that Chucky-ng does not require to calibrate the tool with any sort of training step.

Our contribution

At the best of our knowledge, no tool for mitigation against fuzzing attacks on smart cards is publicly available. We do not want to create a smart card fuzzer to extract vulnerabilities for two reasons. The first one is the required time to send a command from a terminal to a smart card is time expensive. We want our tool to perform an analysis in the best delays. The second reason is that smart cards contains Non Volatile Memory (NVM). Such memory has a short life expectation. Therefore, sending too many commands to the card would trigger many write functions and then prematurely aging the card. We have created both fetchVuln and ChuckyJava. The former is the front-end of Chucky-Java. The latter allows the parsing of Java source codes and perform on them the unsupervised machine-learning technique of Chucky-ng.

Description of Chucky-ng

Chucky-ng takes three inputs:

the folder of applet's source codes to analyze, one or more API symbols, such as variable names, parameter names or method names, the number of neighbors to select k.

The API symbols are the element that Chucky-ng searches in every method of the source code. An analyst can add several API symbols in the analyze queue. Therefore, in order to be added to the methods to analyze, this same method must manipulate all of these API symbols. The necessity of the k parameter is explained in the Neighborhood discovery step. Once Chucky-ng succeeds its execution, it returns an anomaly score for each function containing at least one of the API symbol. The tool processes the anomaly score in four distinct steps: The parsing, the neighborhood discovery, the reduction of the vector's dimensions and the anomaly detection.

Parsing

The tool named Joern[16], first parses Java files in the applet's folder source code to analyze. Based on this, it creates a Code Property Graph [START_REF] Yamaguchi | Chucky: Exposing missing checks in source code for vulnerability discovery 1[END_REF]. This graph gathers all nodes and links of the abstract syntax tree, the control flow graph and the data flow graph into one single graph. This same graph focuses mainly on the representation of functions from the source code.

Neighborhood discovery

During this step, Chucky-ng creates a set of functions which contain at least one API symbol under analysis. This is done by running through the Code Property Graph. From this set, Chucky-ng picks one function. Then, it represents every function of the set as vectors of dimension |API symbols|. It uses the machine-learning algorithm k-Nearest-Neighbors [START_REF] Sayad | K nearest neighbors[END_REF] on these vectors in an unsupervised way, in order to gather the most k similar neighbors to the picked one. This value of k is required as input and it determines the number of similar functions to gather. The k-Nearest-Neighbors algorithm is split into two steps.

The first step aims at increasing the selection of neighbor's accuracy. To do so, Chuckyng uses an approach based on Inverse Document Frequency (IDF) in order to discriminate rares API symbols. It insists on the fact that rare symbols are meaningful compared to others used by the vast majority of the function set. Two functions using the same rare API symbols should be more similar than two functions using only regular API symbols. Chucky-ng's set of vectors now contains these new values based on the IDF.

The second step consists in gathering the k most similar functions from the one picked at the beginning of the Neighborhood discovery. To do so, Chucky-ng processes the vectors using the cosine distance metric where x and y are vectors API symbols values restricted by the IDF filtering:

cos(x x x, y y y) = 1 - x x x • y y y ||x x x|| • ||y y y|| . (1)
The use of this distance metric is twofold. Since Chucky-ng needs to consider rare API symbols, this metric takes into account both the orientation and the Euclidean distance of vectors. Since Chucky-ng has the similar methods set to the one picked, it does not need the vectors anymore. Instead, Chucky-ng uses new vectors whose dimensions are the number of the total number of expressions used in every method of the set. Mind that the Neighborhood discovery, the Reduction of vector's dimension and the Anomaly detection steps are repeated as many times as there are methods in the set.

Reduction of the vector's dimension

This step objective is to reduce the dimension of the method set. It achieves this by removing tests of the program which does not manipulate any of the API symbols. For example, if a control structure does not uses this API symbol either in its condition or body, Chucky-ng discards this control structure for the rest of the algorithm. It reduces the total number of expressions and therefore the dimension of vectors. To do so, Chucky-ng relies on the Code Property Graph in order to taint the API symbol evolution through the source code. Added to this, Chucky-ng manages to reduce the dimensions of the vectors by normalizating the remaining expressions. It suppresses minor syntactical differences. As an example, the binary relational operators ( , <, , >) are now replaced by $CMP expression. It affects the arguments, the return value of callees (callees) and the conditions of control structures. For example, the expression if (ident 1) is normalized as if (ident $CM P $N U M ). It reduces the impact of small syntactical differences.

Anomaly detection

During this step, Chucky-ng creates a model of normality. This object is a vector whose dimensions are each of the remaining expressions. For each dimension, the value is the average presence for this expression in all the functions of our set as shown in equation [START_REF] Jones | Systematic software development using vdm[END_REF]. Let E be the normalized expression set and X the set of neighbor functions. ϕ(x) is the mapping function that transforms neighbors in a vector space. The function I(x, e) is equal to 1 if neighbor x contains the expression e. Otherwise I is equal to 0.

ϕ : X → R |E| , ϕ(x) → (I(x, e)) e∈E .
(2)

Let µ be the vector of normality and N the neighbor set.

µ = 1 |N | n∈N ϕ(n), µ ∈ R |E| . (3)
Chucky-ng then creates a distance vector d as in equation ( 4) which corresponds to the values of the normality model minus the values of our function vector under test. The distance vector is in fact the list of the anomaly scores for each expression.

d = µ -ϕ(x), d ∈ R |E| . (4)
To finish, the anomaly score for the function under analysis is the maximum value of the distance vector as shown in equation ( 5). Its range is from [-1.00, 1.00]. If the anomaly score is closer to 1.00, our function is more likely to omit an expression, compared to the other functions. On the contrary, if it is closer to -1.00, our function has an expression that none of the others perform.

Score = max(d). (5)
Even if Chucky-ng precises the anomaly score for a whole function, in practice, we observe all of its expression's anomaly scores. For example, if a function's anomaly score is set to 1.00 for an expression, all scores ranked under 1.00 are hidden by the result of Chucky-ng. To be efficient, an analyst has to read the whole distance vector including the -1.00 expressions. As we have discovered in the methodology (section 6), an anomaly score of -1.00 is meaningful in our case: it corresponds to an extra-check. In other words, the applet may accept an unwanted additional command in the state machine.

Adaptation

5.1 From C/C++ to Java Java shares notions that are similar to those in C++. For instance, the class abstraction and virtual methods are similar. While such notions are shared with C++, we have syntactically adapted them in order to fit to the Joern[16], the parser. To achieve this task, we have modified Joern and Chucky-ng in order to link them together to the functionalities we have implemented. We now explain how we handle those specificities.

Abstract classes Methods which are declared in an abstract class in Java do not have definition. Since such methods are defined in another Java source file, ChuckyJava discards methods only declared. This prevent the use of duplicates methods.

Virtual methods If a class inherits of methods defined in the Java API, than ChuckyJava cannot parse them. To prevent this, we have created a tool that gathers both used and defined classes in the source code, and then it warns the user if a class is used but is never declared. This can happen if the user calls an object constructor from the Java's API.

New expressions

We have to take into account new expressions or control flow structures. As an example, in C++, the try/catch clause does not have the finally block. Since this last one is executed either if the catch is triggered or not, we have decided to treat it as code block, outside of the control flow of the try/catch. Other ways to iterate exists in Java and not in C++ such as the iteration over a list. For example, for(Element e: elements) { [...] }.

New operators

We have implemented two binary operators which exist in Java but not in C/C++. Those operators are the structure comparison operator of strict equality === and the bit shift to the right, which includes the sign byte >>>.

Switch/cases Chucky-ng does not handle and detect missing cases in a switch/case structure. ChuckyJava takes into account the missing cases in order to detect this kind of missing-check. It means that ChuckyJava can now return an anomaly score for such tests. Every applet has to declare a process method in order to handle the reception of a message from an external source. In many cases, they use a switch/case to handle the instruction byte and launch the expected operations. In Java Cards, switches are important since they inform us about the allowed or denied commands of an applet.

ChuckyJava

We modify the ChuckyJava's algorithm in order to improve its accuracy during the Neighborhood discovery step.

Object Type For the Neighborhood Discovery step, we now take into account two new API symbols. An object's cast type and the type of an object if it is created as a parameter of a method call. To illustrate the cast, from the expression (byte) 0x0F, we now extract the byte type and we include it in the vector's dimension. For the second new API symbol, the expression call( new OwnerPin(0x03,0x04)) corresponds to the object creation inside a method call. From now on, the type OwnerPin would be included in the vector's dimension too. These modifications improve ChuckyJava's ability to gather similar functions with a better accuracy.

The methodology

This section presents the test framework we have created. It includes the three tools fetchVuln, LittleDarwinJC, ChuckyJava. Fig. 2 shows the relation between those tools. Fig. 2: fetchVuln requests ChuckyJava to test every API symbols. For each analyzed symbols, the output from ChuckyJava is stored and processed by fetchVuln. LittleDar-winJC produces different sets from the original ones, each of them containing one single mutation

FetchVuln

We have created the tool fetchVuln. This front-end's objective is to help an analyst to discover vulnerabilities easier. This tool operates in two distinct steps. It can be seen as a top layer over ChuckyJava.

Firstly, it lists all API symbols used within all the applets and their usage. Based on this, the tool is able to perform an analysis with ChuckyJava for each of these symbols. This is useful since ChuckyJava requires to specify one or multiple API symbols. Once ChuckyJava returns its output containing the anomaly score for each selected methods, fetchVuln stores it. It is stored as a list of triplets: method, missing-check (or feature) and anomaly score.

Secondly, when the execution of ChuckyJava for each API symbol is done, it outputs a report. Based on a configurable output filter value, this report contains the anomaly scores, the method names, the locations in the source code and the missing-check associated. This is readable by an analyst and it sorts the result from the highest anomaly score 1.00 to the defined output filter value. Moreover, our tool feedbacks statistics. For instance, it is able to output the number of API symbols for which we do not have enough similar neighbors. This can happen if a precise parameter name is used in too few functions. Another example of statistics that fetchVuln outputs is the number of functions with anomalies compared to total number of functions.

LittleDarwinJC

Thanks to fetchVuln, we are now able to output automatically a vulnerability report for an applet folder. We validate the adaption of Chucky-ng to Java. Secondly, we want to verify fetchVuln capacity to detect single variation of conditions in a source code. It enables us to characterize our tool. To do this, we have chosen to adapt the tool LittleDarwin [START_REF] Parsai | Littledarwin: a feature-rich and extensible mutation testing framework for large and complex java systems[END_REF]. We base our tool LittleDarwinJC on it since it generates mutations on the source code instead of the bytecode of a Java file. Then, we create a folder of one applet4 . This same applet is duplicated five times inside the folder. LittleDarwinJC creates many copies of the original applets folder as there are existing conditions in the applet. On each folder, it removes one different single condition. Therefore, each applet folder is now a mutant and none of these mutants is duplicated. Then, a temporary tool we have created requests fetchVuln to perform an analysis on every mutant applet folders. If its final report shows an abnormal method with an anomaly score set to 1.00, then the mutant has been found by fetchVuln. We conclude from our tests that fetchVuln is able to detect missing-checks. An extra-check is the anomaly where only one applet of the set performs a tests, but none of the others. A missing/extra-assignment is similar to missing/extra-checks, but on variable assignments. After this first step, we have tested the tool ability to discover other varieties of anomaly. From our results, fetchVuln is able to detect extra-checks and missing/extra-assignments too. Moreover, since we implemented the switch-case as conditions in ChuckyJava, fetchVuln is able to detect missing-checks within the cases.

Evaluation

Vulnerability results

Description of the dataset Our dataset is made of five different Java Card applets, all implementing the OpenPGP[11] specification. Among these applets, we can find two different versions of OpenPGP: the 2.0.1 one, and the 3.3.1 one. These applets and their OpenPGP versions are listed in Table 1. To communicate from a card terminal to the Java Card, one has to send an APDU object which contains the communication information. Among the bytes sent during this process, we present three APDU's header bytes: the CLA byte, the INS byte and the P1 byte. The CLA (Class) byte is used to define the interindustry class. The second one is the INS (Instruction) which enables the applet to determine which command the user wants to perform. The last one, the P1 (Parameter 1) byte, is a parameter for the instruction command. We analyze the results of fetchVuln and therefore ChuckyJava.

A useless check We have executed an analysis on the callee JCSystem.makeTransient-ByteArray. We set the value of the number of neighbors to select (parameter k) to 4. Since all applets implement a process method, this value of k enables us to gather all the process functions in order to compare them with ChuckyJava. Listing 1.1 shows the output we obtain with ChuckyJava for the PGPKey constructor in the PGPKey.java file.

Listing 1.1: The anomaly score, the expression, the function and file concerned -1.00 " ( n u l l $CMP $RET ) " PGPKey PGPKey . j a v a : 3 8

Since the anomaly score is evaluated to -1.00, it means that the test is performed in this method while it is not in other similar methods. We can verify this assumption with this code snippet available in the appendix A. At this point in the applet, tmpBuf has been declared but no memory has been allocated, this it points on null. The evaluation is always true. ChuckyJava detects here a useless test which can be eliminated.

Dead code detection

We are able to detect dead code with ChuckyJava. Listing 1.2 shows the output we obtain for analysis of the process method of the MyPGPid applet. ChuckyJava returns an anomaly score of -1.00. It means that the process function performs a case ISO7816.INS_SELECT which is not in other process functions. By analyzing the code of appendix B, we can see a test performed at the beginning: se-lectingApplet(). Both this test and the case ISO7816.OFFSET_INS check the value of the APDU's INS byte. Moreover, both of them returns immediately if this byte's value is 0xA4. This explains why the second test in the switch can not be reached and is therefore not necessary.

A misuse of the CLA byte By analysing the ChuckyJava output for the process method, we are able to detect a misuse of the CLA byte. This same byte has to be checked before usage, as requested in the OpenPGP specification [11]. In the MyPGPid applet, this byte is tested by a bitwise AND and the value 0xFC, but not in the other applets. We have discovered that this assignation performed, but the value of buffer[ISO7816.-OFFSET_CLA] is pratically never checked in the source code. The value is verified once in a method. Nearly every values for the CLA byte are possible for this applet. An attacker could be able to exploit it to make the program unexpectedly enter in a new state. The OpenPGP specification stipulates that this CLA byte shall be verified in order to allow only specific values (most of the time: 0x00, 0x0C, 0x10 or 0x1C according to the current state).

A Missing-Check for the P1 byte We have discovered an anomaly for the P1 byte. We have investigated the verify functions of our applet set. The output of ChuckyJava in listing 1.4 warns us about an anomaly existing in the OpenPGPApplet.java file. This anomaly shows the verify function which does not use nor check the P1 byte while the others do it. According to the specification for the verify method, the P1 byte shall be set to 0x00 for this precise command. This is a missing-check because it is performed in the verify functions of the other applets of the set. The code snippet for OpenPGPApplet is available in appendix C. The anomaly score of 0.67 instead of 1.00 is due to a limitation which we discuss in section 8.

Performance evaluation

A quality assurance tool (QA) in smart cards aims at verifying if all the specified commands are implemented (conformance testing). Our tool fetchVuln is not a QA tool. It detects if the applet has more functionalities than expected. To illustrate this purpose, imagine an applet which is perfectly implementing the OpenPGP specification. Each command a user send to the applet returns the expected output. We now suppose that a back-door exists in the applet. A QA tool is not able to detect it, because the applet performs perfectly according to its specification. However, since fetchVuln detects extra-checks, it is able to discover such an anomaly in an applet.

Time overheads

This performance evaluation focuses on the advantages of using fetchVuln instead of a physical verification. To test a Java applet, an analyst can first generate several different messages. Then, he sends them individually to the smart card to obtain the output. Finally, he verifies that the combination input/output is conform to the specification. The drawback of physically testing the inputs is the communication cost between a smart card and the terminal. It is time expensive. We have tested the method and the process has last roughly one second to transmit a single command to the applet FluffyPGPApplet. The time required with such an analysis, increases with the number of states which the specification plans. As a comparison, fetchVuln requires about 3 minutes to analyze a set of five applets implementing the OpenPGP specification, including FluffyPGPApplet. This analyzes was performed on a Intel i7-7600U 2.8GHz CPU, using two of the four threads available in a virtual environment.

Limitations

Number of missing-checks

During the fourth step, ChuckyJava creates vectors which contain information about the presence or not of a normalized expression only. For example, the condition if (k == 3) is normalized as ( k $CMP $NUM ). If there are multiple conditions comparing k with a number, the tool normalizes them with the same expression. Then, the value for the dimension ( k $CMP $NUM ) is equal to one regardless of the number of comparison. We can see in Listing 1.5 that two tests are executed. However, only one is performed in Listing 1.6. After the normalization step, both vectors representing the code snippet have the dimension ( k $CMP $NUM ). Its value is equal to one in both vectors. This leads to a non-detection of some missing-checks.

Missing distinction between variables and constants

We are able to observe that in some cases it is not possible for ChuckyJava to distinguish a variable from a constant. Listing 1.7 shows an initialization with a variable. This same variable could be uninitialized at this point but there is no test to verify it. In Listing 1.8, the same function call uses a constant as a parameter. Since it is a constant, it is more likely to be defined in one of the project classes. In this example, its value is set to 10. It is not necessary to test its value before using it. However, if the other applets use a variable as like in Listing 1.7, then ChuckyJava detects a wrong missing-check here for code snippet in Listing 1.8. Added to this, ChuckyJava is not able to handle differences between identifiers. For example, we want ChuckyJava to analyze the identifier buffer. Then, all similar identifiers (tmpBuff, buf, etc.) are discarded. To perform an accurate analyze with our tool, we first have to normalize the used identifiers, which is one of our current research directions.

Conclusion

We have designed a tool chain which includes ChuckyJava, fetchVuln and LittleDar-winJC. It aims at detecting incorrect implementations of specification within Java Card applets. We have improved the original tool by adding various features. fetchVuln has successfully detected mutant applets generated with LittleDarwinJC. Added to this, we have discovered that our tool is able to detect extra-checks and missing-assignements too. In real conditions, fetchVuln is able to detect wrong implementations specification. However, the tool has two limitations. We are currently working on the identifier problem since it is the most restrictive one. Because it is a known problem, we have found different methods to start with. We are heading to source code de-obfuscation and source codes merging techniques [START_REF] Kuhn | Semantic clustering: Identifying topics in source code 13[END_REF][START_REF] Tairas | Phoenix-based clons detection using suffix trees 13 16[END_REF] to solve this limitation.

Fig. 1 :

 1 Fig. 1: Partial state machine of the COMPUTE_DIGITAL_SIGNATURE. There are conditions to transition from a state to another. States are represented by the nodes. The S node is the Selected state. Source from the OpenPGP specification[11]

Listing 1 . 2 :

 12 ChuckyJava output for MyPGPid -1.00 " c a s e ISO7816 . INS_SELECT " p r o c e s s MyPGPid . j a v a

Listing 1 . 3 :

 13 misuse of the CLA byte -1.00 " b u f f e r [ ISO7816 . OFFSET_CLA ] = ( b y t e ) ( b u f f e r [ ISO7816 . OFFSET_CLA ] & ( b y t e ) 0 → xFC ) p r o c e s s MyPGPid . j a v a : 3 4 7

Listing 1 .

 1 4: Missing-check of P1 byte 0 . 6 7 " b u f f e r [ ISO7816 . OFFSET_P1 ] $CMP ( b y t e ) ( $NUM) " v e r i f y OpenPGPApplet . j a v a → : 4 1 3

Listing 1 . 5 :

 15 Two comparisons of number with k p u b l i c v o i d t e s t ( i n t k ) { i f ( k <= 1 ) c a l l e e ( 1 ) ; e l s e i f ( k <= 2 ) c a l l e e ( 2 ) ; } Listing 1.6: Vulnerable code p u b l i c v o i d t e s t ( i n t k ) { i f ( k <= 1 ) c a l l e e ( 1 ) ; / / M i s s i n g c h e c k . . . c a l l e e ( 2 ) ; }

Listing 1 . 7 :

 17 Local variablei f ( m y _ v a r i a b l e > 0 ) m y I n i t M e t h o d ( m y _ v a r i a b l e ) ; Listing 1.8: Constant p r i v a t e s t a t i c f i n a l i n t MY_CONSTANT = 1 0 ; m y I n i t M e t h o d (MY_CONSTANT) ;

  g e t D a t a ( apdu ) ; r e t u r n ; c a s e PUT_DATA : p u t D a t a ( apdu ) ; r e t u r n ; c a s e PUT_DATA_CHAINING : p u t D a t a C h a i n i n g ( apdu ) ; r e t u r n ; c a s e VERIFY : i f ( b u f f e r [ ISO7816 . OFFSET_P1 ] ! = 0 ) { I S O E x c e p t i o n . t h r o w I t ( ISO7816 . → SW_WRONG_P1P2) ; } l c = apdu . s e t I n c o m i n g A n d R e c e i v e ( ) ; i f ( l c == 0 ) { I S O E x c e p t i o n . t h r o w I t ( ISO7816 . SW_SECURITY_STATUS_NOT_SATISFIED ) ; } s w i t c h ( b u f f e r [ ISO7816 . OFFSET_P2 ] ) { c a s e ( b y t e ) 0 x81 : i f ( chv1 . g e t T r i e s R e m a i n i n g ( ) == ( b y t e ) 0 ) { I S O E x c e p t i o n . t h r o w I t ( SW_PIN_BLOCKED ) ; } s t a t u s = chv1 . c h e c k ( b u f f e r , ( s h o r t ) ISO7816 . OFFSET_CDATA , ( b y t e → ) l c ) ; break ; c a s e ( b y t e ) 0 x82 : i f ( chv2 . g e t T r i e s R e m a i n i n g ( ) == ( b y t e ) 0 ) { I S O E x c e p t i o n . t h r o w I t ( SW_PIN_BLOCKED ) ; } s t a t u s = chv2 . c h e c k ( b u f f e r , ( s h o r t ) ISO7816 . OFFSET_CDATA , ( b y t e → ) l c ) ; break ; c a s e ( b y t e ) 0 x83 : i f ( chv3 . g e t T r i e s R e m a i n i n g ( ) == ( b y t e ) 0 ) { I S O E x c e p t i o n . t h r o w I t ( SW_PIN_BLOCKED ) ; } s t a t u s = chv3 . c h e c k ( b u f f e r , ( s h o r t ) ISO7816 . OFFSET_CDATA , ( b y t e → ) l c ) ; break ; d e f a u l t : I S O E x c e p t i o n . t h r o w I t ( ISO7816 . SW_WRONG_P1P2) ; } i f ( ! s t a t u s ) { I S O E x c e p t i o n . t h r o w I t ( ISO7816 . → SW_SECURITY_STATUS_NOT_SATISFIED ) ; } r e t u r n ; c a s e GENERATE_ASYMMETRIC_KEY_PAIR : g e n e r a t e A s s y m e t r i c K e y P a i r ( apdu ) ; r e t u r n ; c a s e PERFORM_SECURITY_OPERATION : p e r f o r m S e c u r i t y O p e r a t i o n ( apdu ) ; r e t u r n ; c a s e CHANGE_REFERENCE_DATA : / * F a l l t h r o u g h * / c a s e RESET_RETRY_COUNTER : c h a n g e R e s e t C h v ( apdu ) ; r e t u r n ; c a s e INTERNAL_AUTHENTICATE : i f ( b u f f e r [ ISO7816 . OFFSET_P1 ] ! = 0 | | b u f f e r [ ISO7816 . OFFSET_P2 ] ! = 0 ) { I S O E x c e p t i o n . t h r o w I t ( ISO7816 . SW_WRONG_P1P2) ; } i f ( ! chv2 . i s V a l i d a t e d ( ) ) { I S O E x c e p t i o n . t h r o w I t ( ISO7816 . SW_SECURITY_STATUS_NOT_SATISFIED ) ; } l c = r e c e i v e D a t a ( apdu , tmpData ) ; s i g . i n i t ( keyAuth . g e t P r i v a t e ( ) , C i p h e r . MODE_ENCRYPT) ; l c = s i g . d o F i n a l ( tmpData , ( s h o r t ) 0 , l c , tmpData , ( s h o r t ) 0 ) ; s e n d D a t a ( apdu , tmpData , l c ) ; r e t u r n ; c a s e GET_CHALLENGE : i f ( b u f f e r [ ISO7816 . OFFSET_P1 ] ! = 0 | | b u f f e r [ ISO7816 . OFFSET_P2 ] ! = 0 ) { I S O E x c e p t i o n . t h r o w I t ( ISO7816 . SW_WRONG_P1P2) ; } l c = apdu . s e t O u t g o i n g ( ) ; random . g e n e r a t e D a t a ( tmpData , ( s h o r t ) 0 , l c ) ; apdu . s e t O u t g o i n g L e n g t h ( l c ) ; apdu . s e n d B y t e s L o n g ( tmpData , ( s h o r t ) 0 , l c ) ; r e t u r n ; / / c a s e EXPORT_KEY_PAIR : / / e x p o r t K e y P a i r ( apdu ) ; / / r e t u r n ; c a s e INS_CARD_READ_POLICY : R e a d P o l i c y ( apdu ) ; r e t u r n ; c a s e INS_CARD_KEY_PUSH : KeyPush ( apdu ) ; r e t u r n ; d e f a u l t : I S O E x c e p t i o n . t h r o w I t ( ISO7816 . SW_INS_NOT_SUPPORTED ) ; } } C Verify function of OpenPGPApplet p r i v a t e v o i d v e r i f y (APDU apdu , b y t e mode ) { i f ( mode == ( b y t e ) 0 x81 | | mode == ( b y t e ) 0 x82 ) { / / Check l e n g t h o f i n p u t i f ( i n _ r e c e i v e d < PW1_MIN_LENGTH | | i n _ r e c e i v e d > PW1_MAX_LENGTH) I S O E x c e p t i o n . t h r o w I t ( ISO7816 .SW_WRONG_LENGTH) / / Check g i v e n PW1 and s e t r e q u e s t e d mode i f v e r i f i e d s u c c e s f u l l y i f ( pw1 . c h e c k ( b u f f e r , _0 , ( b y t e ) i n _ r e c e i v e d ) ) { i f ( mode == ( b y t e ) 0 x81 ) pw1_modes [PW1_MODE_NO81] = t r u e ; e l s e pw1_modes [PW1_MODE_NO82] = t r u e ; } e l s e { I S O E x c e p t i o n . t h r o w I t ( ( s h o r t ) ( 0 x63C0 | pw1 . g e t T r i e s R e m a i n i n g ( ) ) ) ; } } e l s e i f ( mode == ( b y t e ) 0 x83 ) { / / Check l e n g t h o f i n p u t i f ( i n _ r e c e i v e d < PW3_MIN_LENGTH | | i n _ r e c e i v e d > PW3_MAX_LENGTH) I S O E x c e p t i o n . t h r o w I t ( ISO7816 .SW_WRONG_LENGTH) ; / / Check PW3 i f ( ! pw3 . c h e c k ( b u f f e r , _0 , ( b y t e ) i n _ r e c e i v e d ) ) { I S O E x c e p t i o n . t h r o w I t ( ( s h o r t ) ( 0 x63C0 | pw3 . g e t T r i e s R e m a i n i n g ( ) ) ) ; } } e l s e { I S O E x c e p t i o n . t h r o w I t ( ISO7816 . SW_INCORRECT_P1P2 ) ; } }

Table 1 :

 1 OpenPGP applets and their implementation versions

	Applet name OpenPGP version
	FluffyPGP	2.0.1
	JCOpenPGP 2.0.1
	MyPGPid	2.0.1
	OpenPGPCard 2.0.1
	SmartPGP	3.3.1

https://github.com/FluffyKaon/OpenPGP-Card


Sébastien Ferré
email: ferre@irisa.fr

Peggy Cellier
email: peggy.cellier@irisa.fr

How Hierarchies of Concept Graphs Can Facilitate the Interpretation of RCA Lattices?

Keywords: Formal Concept Analysis, Relational Concept Analysis, Data Mining, Concept Graph

Relational Concept Analysis (RCA) has been introduced in order to allow concept analysis on multi-relational data. It significantly widens the field of application of Formal Concept Analysis (FCA), and it produces richer concept intents that are similar to concept definitions in Description Logics (DL). However, reading and interpreting RCA concept lattices is notoriously difficult. Nica et al have proposed to represent RCA intents by cpo-patterns in the special case of sequence structures. We propose an equivalent representation of a family of RCA concept lattices in the form of a hierarchy of concept graphs. Each concept belongs to one concept graph, and each concept graph exhibits the relationships between several concepts. A concept graph is generally transversal to several lattices, and therefore highlights the relationships between different types of objects. We show the benefits of our approach on several use cases from the RCA litterature.

Introduction

Many domains produce multi-relational data. For example, in the health domain, one can have patients taking drugs, drugs giving some symptoms and interacting with other drugs, doctors taking care of patients and prescribing drugs to patients, etc. In order to extract knowledge from that kind of data, many data mining techniques, such as Formal Concept Analysis (FCA) [START_REF] Ganter | Formal Concept Analysis: Mathematical Foundations[END_REF], require the flattening of multi-relational data but this results in loss of structural information, and a more difficult interpretation of discovered patterns. It is therefore desirable to have direct methods for multi-relational mining [START_REF] Džeroski | Relational Data Mining[END_REF]. Several generalizations of FCA have been proposed to handle relational data: Power Context Families [START_REF] Prediger | Simple concept graphs: A logic approach[END_REF], Relational and Logical Concept Analysis [START_REF] Ferré | Arbitrary relations in formal concept analysis and logical information systems[END_REF], Relational Concept Analysis (RCA) [START_REF] Rouane-Hacene | Relational concept analysis: mining concept lattices from multi-relational data[END_REF], and Graph-FCA [START_REF] Ferré | A proposal for extending formal concept analysis to knowledge graphs[END_REF]. RCA has so far been the most frequently used approach with applications in health [START_REF] Rouane-Hacene | Relational concept analysis: mining concept lattices from multi-relational data[END_REF][START_REF] Nica | Extracting hierarchies of closed partially-ordered patterns using relational concept analysis[END_REF] or model driven engineering [START_REF] Falleri | Use of model driven engineering in building generic fca/rca tools[END_REF].

An important issue for the effective use of RCA is the interpretation of its outputs. Indeed, RCA produces not one but several concept lattices, and the intent of each concept may depend on the intent of other relationally-related concepts, recursively. To the best of our knowledge, there has been only one proposal to automatically extract and graphically represent the relational patterns that are buried into concept intents: Nica's cpo-patterns [START_REF] Nica | Extracting hierarchies of closed partially-ordered patterns using relational concept analysis[END_REF]. However, it has several restrictions. First, it is defined only for sequential data. Second, it generates cpo-patterns only for the concepts of one chosen lattice. Third, it generates a cpo-pattern for each concept of the chosen lattice, missing potential factorizations between patterns and thus interesting information between patterns.

In this paper, we propose a novel and generic graphical representation of RCA outputs that emphasizes the relational patterns. We call it hierarchy of concept graphs. It has the following good properties. First, it makes no assumption on the context family, and can therefore handle all kinds of graph structures, not only sequences. Second, it is at the same time a complete and non-redundant representation of the family of concept lattices, and does not require to choose one concept lattice as starting point. Third, it offers a better balance in the display between generalization ordering (lattice edges), and relationships (relational attributes). Fourth, it clusters concepts into concept graphs, and hence produce a coarser-grained representation. Fifth, it can be efficiently computed from the concept lattices, in linear time.

Section 2 discusses related work. Section 3 shortly recalls the main definitions of RCA. Section 4 introduces our representation of RCA outputs as a hierarchy of concept graphs, illustrates it on a reference example of RCA, and discusses its properties. Section 5 evaluates our approach on a few use cases, and discusses the impact of representation choices. Section 6 concludes and draws perspectives.

Related Work

Several generalizations of FCA have been proposed to handle relational data. Power Context Families [START_REF] Prediger | Simple concept graphs: A logic approach[END_REF] has a formal context for each relation arity, i.e. a context of objects, a context of couples of objects, a context of triples of objects, etc. A concept lattice is computed for each context, independently of other contexts. The resulting concepts are used as a vocabulary of types and relations to build concept graphs that are similar to Conceptual Graphs [START_REF] Sowa | Conceptual structures. Information processing in man and machine[END_REF][START_REF] Chein | Graph-based knowledge representation: computational foundations of conceptual graphs[END_REF]. Relational and Logical Concept Analysis [START_REF] Ferré | Arbitrary relations in formal concept analysis and logical information systems[END_REF] takes as input a power context family limited to unary and binary relations but extended to complex logical descriptions. It generates a single concept lattice where concept intents combine both unary and binary descriptors, and where the labeling of the concept lattice is extended with relationships between concepts. Relational Concept Analysis (RCA) [START_REF] Rouane-Hacene | Relational concept analysis: mining concept lattices from multi-relational data[END_REF] takes as input a power context family limited to unary and binary relations. In practice, the unary context is split in several unary contexts, one for each type of object. RCA generates a concept lattice for each type of object, where concept intents are sets of classical attributes and relational attributes. The latter represent relationships to other concepts in the concept lattice family. Graph-FCA [START_REF] Ferré | A proposal for extending formal concept analysis to knowledge graphs[END_REF] takes as input a power context family without restriction on arities. It generates a set of graph patterns where each node represents a unary concept, each pair of nodes represents a binary concept, etc. For each concept arity, the set of all concepts forms a concept lattice.

The above shows that there are two kinds of representations of the results: concept lattices and concept graphs. They complement each other: concept lattices emphasizes the generalization ordering between concepts, while concept graphs emphasize the relationship patterns between objects in data. In RCA, the native representation is made of concept lattices, and the relationship patterns are only indirectly accessible through relational attributes. Recently, Nica et al [START_REF] Nica | Extracting hierarchies of closed partially-ordered patterns using relational concept analysis[END_REF] have proposed a solution to combine concept lattices with graph patterns. However it is not a general solution for RCA because of the limitations already discussed in the introduction.

Relational Concept Analysis (RCA)

We here recall the definitions of context family and lattice family in RCA. We therefore focus on the input and output of RCA, and we ignore the methodology and algorithms that are used to compute the concept lattices from the context family. Indeed we are here concerned with the graphical representation of RCA lattices rather than on their computation. A detailed presentation of RCA is available in previous papers, in particular [START_REF] Rouane-Hacene | Relational concept analysis: mining concept lattices from multi-relational data[END_REF]. The input data of RCA is called a relational context family (RCF). In words, it is a collection of formal contexts, one for each kind of objects, together with a collection of binary relations going from the objects of one context to the objects of the same or another context. Definition 1. A Relational Context Family (RCF) is a pair (K K K, R R R) where:

-K K K = {K i } i=1..n is a set of contexts K i = (O i , A i , I i ), and -R R R = {r k } k=1.
.m is a set of relations r k where r k ⊆ dom(r k ) × ran(r k ), and dom(r k ), ran(r k ) ∈ {O i } i=1..n are respectively the domain and range of r k .

As a running example, we reuse the RCF defined in [START_REF] Rouane-Hacene | Relational concept analysis: mining concept lattices from multi-relational data[END_REF] about pharmacovigilance of AIDS patients and drugs: ({K p , K d }, {takes, itb, iw }). Context K p describes 4 patients in terms of age, gender, and observed Adverse Drug Reactions (ADR) (14 attributes). Context K d describes 6 drugs in terms of active molecule, and expected ADR (16 attributes). Relation takes relates patients to the drugs they have taken. Relation itb ("is taken by") is the inverse of takes. Relation iw ("interacts with") relates couples of drugs that interact with each other (it is symmetric).

Given an RCF, the output of RCA is a collection of concept lattices, one for each context of the RCF. The relations of the RCF are taken into account by repeatedly applying a mechanism of relational scaling on each context and its concept lattice, until convergence is reached. This leads to the introduction of relational attributes that express relational constraints, and contribute to the formation of concepts (see [START_REF] Rouane-Hacene | Relational concept analysis: mining concept lattices from multi-relational data[END_REF] for more details).

Definition 2. Let (K K K, R R R) be a RCF. The Relational Concept Lattice Family (RCLF) is a set of concept lattices L L L = {L i } i=1..n , one for each context K i . Each concept c i in L i is a pair (X, Y ) where:
-X ⊆ O i is the extent of the concept, and -Y is the intent of the concept, and contains attributes in A i and relational attributes in the form ρ r : c j where ρ ∈ {∃, ∀∃, ...} is a scaling operator,

r ∈ R R R, dom(r) = O i , ran(r) = O j , and c j ∈ L j .
In this paper, we only consider existential scaling (ρ = ∃) even though our approach is applicable to other scaling operators. Figure 1 shows the concept lattice L p of patients, and Figure 2 the concept lattice L d of drugs. Both are represented with reduced labelling, i.e. each object/attribute appears only once. Object labels are placed below the concept, while attribute labels are placed above and on the right of the concept. Each relational attribute ∃r : c j is displayed as r : c j .

The reading and interpretation of RCA lattices is notoriously difficult. The main reason is probably that reading the intent of a concept requires not only to traverse the lattice upward, as in FCA, but also to follow relationships to other concepts through the relational attributes. For example, concept p7 groups the adult patients who have fatigue, and take a drug in concept d10 and a drug in concept d14. Concept d10 groups the drugs for which diarrhea is expected, and which are taken by patients in concept p7. Loops in the exploration of the intent, like in that example, lead to circular definitions of concepts, and contribute to the difficulty of interpretation.

Hierarchies of Concept Graphs

Our objective is to facilitate the reading of the intent of RCA concepts, in order to facilitate their interpretation. The first idea is to display the different lattices side-by-side, and to materialize each relational attribute r : c 2 on a concept c 1 as a relational edge, i.e. a labeled and directed edge c 1 r -→ c 2 . However, the graphical representation becomes denser and even less readable; and its structure is dominated by the lattice structures at the cost of elongated relational edges. A better balance between lattice edges and relational edges is desirable. The second idea is to identify relational structures as subsets of interrelated concepts from different lattices, and to use them as building blocks in the graphical representation. We propose to define those relational structures as the Strongly Connected Components (SCC) [3] of the dependency graph between concepts. The intuition behind that dependency graph is that the intent of a concept depends on its ancestors in the lattice, and also on the target concepts of relational attributes.

Dependency Graph. We first define the notion of concept dependency and then the dependency graph of a RCLF. -V is the set of all concepts of all lattices in L L L except bottom concepts, and

E = {(c 1 , c 2 ) | c 1 , c 2 ∈ V and c 1 → c 2 }.
SCCs as Concept Graphs. From there, a SCC of G L L L is a maximal set of concepts (possibly from several lattices) where each concept has a dependency path to all other concepts in the SCC for the definition of its intent. SCCs are used to define concept graphs, which are the building blocks of our graphical representation. Definition 5. A concept graph is the subgraph of the lattice family (enriched with relational edges) that is induced by a SCC of G L L L . It therefore mixes concepts from several lattices, and both lattice edges and relational edges.

In Figure 3, each rounded box contains a concept graph (G1-G6). Nodes are concepts from the two RCA lattices in Figures 1 and2 (same id, same labels). Relational edges (arrows) replace the relational attributes to graphically represent the relational dependencies. Lattice edges that cross concept graph boundaries are displayed as dotted lines to keep the graph light, and to emphasize the concept graphs over the global lattice structures. It is notable in this example that no relational edge crosses concept graph boundaries. This is because in the context family each relation either has an inverse relation (e.g., takes and itb) or is a symmetric relation (e.g., iw ).

Furthermore, it is known that the SCCs of a graph form a directed acyclic graph, where SCC 1 → SCC 2 if any concept in SCC 1 depends on any concept in SCC 2 . The concept graphs of a RCLF can therefore be organized into a hierarchy of concept graphs. For example, concept graph G2 is a child of concept graph G1 in Figure 3 because several concepts in G2 have lattice edges (dotted lines) to concepts in G1: e.g., from p4 to p6, or from d12 to d14. Those hierarchical relationships can be seen as a complex version of the lattice edges, combining several lattice edges across different lattices.

Interpretation. We here give a short interpretation of the hierarchy of concept graphs in Figure 3. G1 represents the most general pattern between patients and drugs. It shows that all patients take drugs expected to give fatigue and diarrhea, and that all drugs are taken by an adult with fatigue. G2-4 are specializations of G1. For example, G4 specializes G1 to patients with bleeding. G2 specializes G1 to patients with hairloss and oedema, which all take drugs giving vomiting and rash, which are taken by a patient with hives, and by a female patient. G5 and G6 represent patterns that are specific to individual patients and drugs, Fig. 3. Hierarchy of concept graphs: arrows represent relational attributes (takes from patients to drugs, itb from drugs to patients, iw between drugs), dotted lines represent lattice edges across concept graphs and are therefore less interesting from a data-mining perspective. G5 shows that some patients (p13) take drugs (d6 and d3) that cause liver dammage (d5) and are in interaction with drug Sustiva (d13) which is taken by patient Lane (p3).

Discussion. The hierarchy of concept graphs has a number of good theoretical properties. First, it is a complete representation because it keeps all concepts and edges from the concept lattices. It is also parcimonious in that it does not duplicate any concept, edge, or label. Second, it is more readable because it displays relation attributes as relation edges, and because its layout offers a better balance between lattice edges and relational edges. Moreover, when the many concepts are clustered in a small number of concept graphs, the RCLF can be read at a higher level of granularity. Third, it is efficient to compute because the SCCs can be extracted in time linear with the size of G L L L , and hence in the cumulated size of lattices in L L L.

Use Cases

In this section we present two use cases in order to compare graph concepts with results of Graph-FCA and cpo-patterns from [START_REF] Nica | Extracting hierarchies of closed partially-ordered patterns using relational concept analysis[END_REF]. The first one describes the royal family. The second use case is about flu patients and medical examinations. The first use case is the one used for Graph-FCA [START_REF] Ferré | Graph-FCA in practice[END_REF]. It describes a subset of the British royal family: Charles, Diana, William, Harry, Kate, George, and Charlotte. The power context family uses two attributes (male and female), and two relations (parent and its inverse child). Note that the relations have the same object type as domain and range: people. RCA produces one lattice containing 19 concepts. Figure 4 shows the hierarchy of concept graphs obtained from that lattice with our approach. Concepts are clustered in 5 concept graphs. G5 is not detailed because it contains very specific concepts, and hence does not bring new knowledge. The hierarchy of concept graphs enables to reach the following interpretations for each concept: p0 people p8 male parents (fathers) p1 male people (men) p9 female parents (mothers) p3 female people (women) p6 people with a father and mother (children) p10 people with a child (parents) p4 male children (sons) The concept of "daughters" has a single instance (Charlotte), and is found in G5, a specialization of G4. The relation from p10 (parents) to p4 (sons) shows that, in the context, every parent has a son but not necessarily a daughter. The relations froms p6 to p8 and p9 shows that, in the context, every child who has a known father also has a known mother, and reciprocally. Concept graph G4 exhibits the relational pattern of a nuclear family, relating children to their father and mother as parents, with the specificity in this context that all parents have a son.

Royal Family: Genealogical Data

Comparing those results to Graph-FCA, it is interesting to note that the graph patterns of Graph-FCA are equivalent to the RCA concept graphs, up to a few representation changes. Graph-FCA patterns only represent relational edges, not lattice edges. The generalization ordering between concepts and patterns is therefore not explicitly represented. In Graph-FCA the use of inverse relations is implicit so that the child relation is redundant with the parent relation. Note that Graph-FCA also defines n-ary concepts such as "couple" or "sibling". The equivalence with Graph-FCA on this example must not be generalized. In fact, it does not hold on the running example about patients and drugs.

Medical Histories and Comparison to cpo-Patterns

The second use case is the one used for cpo-Patterns [START_REF] Nica | Extracting hierarchies of closed partially-ordered patterns using relational concept analysis[END_REF]. It describes flu patients through their symptoms, their viral tests and their medical examinations. The specificity of that dataset is the sequentiality of the data. For instance for patient p1 we know that a viral test on 28/09 is preceded by a medical examination on 26/09 which is also preceded by another medical examination on 25/09. The power context family uses 6 symptom attributes (COUGHmoderate, FEVERmoderate, ?moderate, COUGHhigh, FEVERhigh, ?high) and two relations: RME-ipb-ME (sequential relation between medical examinations), RVTipb-ME (sequential relation from viral tests to medical examinations). It describes five viral tests and ten medical examinations. RCA produces two lattices. The viral test lattice contains 12 concepts and the medical examination lattice contains 18 concepts.

Figure 5 shows the hierarchy of concept graphs obtained from those lattices with our approach. We note that it is a special case, indeed each concept is a concept graph by its own. It is due to the fact that the relation "is-precededby" has no inverse relation, and forms no cycle because of its sequential nature. It is thus impossible to find more than one concept in a strongly connected component. The greyed concepts are the concepts from the viral test lattice, other concepts come from the medical examination lattice. In the graph only concepts with support greater than one are shown. We can read in the hierarchy that all viral tests (top concept 0) are preceded by a medical examination (top concept 1). That relational pattern has two specialisations. The first one where the symptom during the examination is moderate cough (concepts 2 and 8). The second one where there is a high symptom (concepts 7 and 14). We can also note that parts of sequential patterns are shared by several concepts. For instance, concept 24 and 10 are preceded by a medical examination with high cough (concept 4). In fact, concept 9 specializes concept 10 by inserting between the viral test and the high cough (concept 4) two additional medical examinations (concepts 21 and 23), which are themselves specialisations of concept 24. It highlights the overlaps between sequential patterns.

We have also conducted experiments when considering the inverse relation of "is-preceded-by" (ipb), i.e. "is-followed-by" (ifb). The power context family is thus extended with two relations: RME-ifb-ME and RME-ifb-VT. RCA still produces two lattices but the hierarchy of concept graphs is different. Indeed, eleven concept graphs are extracted. Each of them contains several concepts and only one viral test concept. Figure 6 shows an excerpt of the hierarchy of concept graphs with those inverse relations. For the sake of readability and compactness, we modified the representation of concept graphs in two ways: (a) only the most specific concepts of a concept graph are kept, and (b) the full intent of those concepts is shown, instead of the reduced intent, so that each concept graph can be read in isolation. Eight concept graphs among the eleven are shown and only two of them (G4 and G5) are detailled in the figure. Concept graph G4 can be read as "a viral test (concept 13) preceded by a medical examination with moderate cough (concept 15) and a medical examination with high fever (concept 16) and both of them are preceded by a medical examination with a high symptom (concept 31)".

The interesting result is that the eleven concept graphs match exactly the eleven cpo-patterns extracted by [START_REF] Nica | Extracting hierarchies of closed partially-ordered patterns using relational concept analysis[END_REF]. However, there are some differences in the display of the patterns. Indeed, in order to compute the strongly connected components, the inverse relations have to be added and they appear in the result. For instance between concepts 13 and 15 there are two arrows, one in each direction, because the relation is-followed-by (ifb) is the inverse relation of ispreceded-by (ipb). In the same vein, ifb and ipb are transitive relations, and thus some arrows are redundant. For example, the arrows between concepts 13 and 31 can be deduced from the paths through concepts 15, and 16 by transitivity. In [START_REF] Nica | Extracting hierarchies of closed partially-ordered patterns using relational concept analysis[END_REF], the representation was specialized for sequential data, and so that kind of redanduncies were avoided. On the contrary, our approach is general and allows to take into account any kind of relations without any assumption on them. In order to avoid those redundancies the description language of power context families should be modified in order to add a way to specify relation properties (e.g., is transitive, is symmetric, has an inverse), and then it should be taken into account when computing and displaying the concept graphs. The same can be said for the redundancy on attributes. Indeed, when looking at the intent of concept 15, we can note the redundancy between "?moderate" and "COUGHmoderate". It is due to the conceptual scaling used on the symptom attributes. By taking into account the hierarchy between attributes, the display of the concept graphs can be simplified without loosing information.

Conclusion and Perspectives

We have proposed a novel and general representation of RCA concept lattices, called hierarchy of concept graphs, in order to facilitate their interpretation. The key idea is to exhibit relational patterns by having a better balance in the display between lattice edges and relational edges. Each concept graph clusters a set of concepts (from different lattices) whose intents are mutually dependent, and exhibits a relational pattern. Concept graphs are organized into a hierarchy so that generalization ordering between concepts is lifted to concept graphs. As future work, we plan to study the impact of relation properties (e.g., inverse, transitivity) on the trade-off between the number of concept graphs and the size of each concept graph. It will also be necessary to develop tools for the dynamic visualization of large hierarchies of concept graphs, à la Conexp1 .

Fig. 1 .

 1 Fig. 1. The relational concept lattice of patients Lp (reduced labelling)

Definition 3 .

 3 Let L L L be a RCLF and c 1 , c 2 be two concepts in L L L. Concept c 1 depends on concept c 2 , denoted by c 1 → c 2 , if:c 2 is a parent concept of c 1 (c 1 ≤ c 2 ),or c 1 is labeled by a relational attribute ρ r : c 2 . Definition 4. Let L L L be a RCLF. The dependency graph of L L L is the directed graph G L L L = (V, E) where:

Fig. 4 .

 4 Fig. 4. Hierarchy of concept graphs about the royal family (G5 not detailed)

Fig. 5 .

 5 Fig.5. Hierarchy of concept graphs about medical histories. Each concept is a concept graph on its own. Greyed concepts are about viral tests, others are about medical examinations. Only concepts with support greater than one are shown.

Fig. 6 .

 6 Fig. 6. Hierarchy of concept graphs about medical histories with inverse relation ifb. Only concept graphs whose concepts have their support greater than one are shown.

http://conexp.sourceforge.net/

This research is supported by ANR project PEGASE (ANR-16-CE23-0011-08).


Sébastien Ferr
email: ferre@irisa.fr

Responsive and Flexible Controlled Natural Language Authoring with Zipper-based Transformations

Keywords: Controlled Natural Languages, Authoring, User Interaction, Abstract Syntax, Huet's Zippers, Focus DET(Some), CLASS(owl:Thing), DOWN, PROP -(dbo:release), DOWN, DET

Controlled natural languages (CNL) have the benefits to combine the readability of natural languages, and the accuracy of formal languages. They have been used to help users express facts, rules or queries. While generally easy to read, CNLs remain difficult to write because of the constrained syntax. A common solution is a grammar-based auto-completion mechanism to suggest the next possible words in a sentence. However, this solution has two limitations: (a) partial sentences may have no semantics, which prevents giving intermediate results or feedback, and (b) the suggestion is often limited to adding words at the end of the sentence. We propose a more responsive and flexible CNL authoring by designing it as a sequence of sentence transformations. Responsiveness is obtained by having a complete, and hence interpretable, sentence at each time. Flexibility is obtained by allowing insertion and deletion on any part of the sentence. Technically, this is realized by working directly on the abstract syntax, rather than on the concrete syntax, and by using Huet's zippers to manage the focus on a query part, the equivalent of the text cursor of a word processor.

Introduction

An important issue in the Semantic Web [START_REF] Hitzler | Foundations of Semantic Web Technologies[END_REF], and knowledge-based systems in general, is to fill the gap between the natural language (NL) of users, and the formal languages (FL) of those systems (e.g., OWL, SPARQL, Answer Set Programming). Formal languages make data processable by machines but they also constitute a language barrier to the production and consumption by end users. Controlled Natural Languages (CNL) [START_REF] Kuhn | A survey and classification of controlled natural languages[END_REF] offer an interesting solution in that they combine the readability of natural languages, and the accuracy of formal languages. An input sentence respecting the syntactic and semantic constraints of the CNL can be parsed non-ambiguously into a formal expression (e.g. a query), and hence can be automatically interpreted (e.g. computing query results). CNLs also offer a good adequacy between what can be expressed respectively by the natural language and the formal language. In contrast, the spontaneous natural language approach generally adopted in Question Answering (QA) [START_REF] Lopez | Is question answering fit for the semantic web?: A survey[END_REF] suffers from problems of ambiguity and adequacy.

While CNLs are much easier to read compared to FL, they remain difficult to write because of the constrained syntax. Syntactic and semantic errors can be frequent and frustrating, especially for users who are new to the CNL and/or the domain vocabulary. The latter is related to the well-known habitability problem [START_REF] Kaufmann | Evaluating the usability of natural language query languages and interfaces to semantic web knowledge bases[END_REF], which occurs when users do not known exactly what falls in the scope of the knowledge-based system, and what is out of scope. A common solution in CNL editors is to use an auto-completion mechanism (e.g., ACE [START_REF] Kaljurand | A multilingual semantic wiki based on attempto controlled english and grammatical framework[END_REF], Ginseng [START_REF] Kaufmann | Evaluating the usability of natural language query languages and interfaces to semantic web knowledge bases[END_REF]) that suggests the next possible words in a sentence. Those suggestions are derived from the CNL grammar and the domain vocabulary, and possibly predicted from usage statistics [START_REF] Guy | Architecture of a web-based predictive editor for controlled natural language processing[END_REF][START_REF] Palmaz | Statistically-guided controlled language authoring[END_REF]. The major advantages of auto-completion are to prevent syntactic errors, and to alleviate the habitability problem. However, we here identify two limitations of auto-completion for CNL authoring. First, as auto-completion is designed to complete a sentence word after word, it results that at most steps the current sentence is not complete, and hence cannot be translated as such to the formal language, and therefore cannot be interpreted. For example, in the case of a query, results can be computed and returned only once the sentence expressing it is complete. When the query happens to have no result, the user will only detect it at the end even if the constraints expressed in the first half of the query were already sufficient to make the results empty. Second, auto-completion is limited to adding words at the end of the partial sentence. In comparison, a text editor allows for insertions and deletions at any position, and has a cursor to let the user control that position. For a user, expressing her knowledge or information needs is generally not a linear process, and goes through rectifications, insertions, substitutions, etc. There is a need to combine suggestions with a flexible authoring process.

We propose an alternative solution to guide users in the authoring of CNL sentences, by following the principles of the NF design pattern [START_REF] Ferr É | Bridging the gap between formal languages and natural languages with zippers[END_REF]. In our proposal, the authoring process is based on sequences of transformations at the abstract syntax level, rather than on the addition of words at the concrete syntax level. As a consequence, the concrete form is obtained by NL generation from the abstract form, rather than the reverse by syntactic parsing as usually done in CNL and QA. The formal expression is obtained as usual by translation from the abstract form, generally using compositional semantic techniques such as Montague grammars [START_REF] Dowty | Introduction to Montague Semantics[END_REF]. We claim that our solution improves auto-completion in terms of responsiveness and flexibility. It is responsive because transformations are designed to take a complete sentence as input, and to return a complete sentence as output. Therefore, at each step, the current sentence is complete, and can therefore be interpreted to give the user intermediate results and feedback. Our solution is also flexible because it allows for insertions and deletions on any part of the sentence, where a part is defined as a node of the abstract syntax tree. We use Huet's zippers [START_REF] Huet | Functional pearl -the zipper[END_REF] as a technique to represent that part, called focus, which plays a role similar to the text cursor of a word processor. We illustrate our approach on a small yet expressive query language whose target FL is SPARQL [START_REF]SPARQL 1.1 query language[END_REF].

The paper is structured as follows. Section 2 shortly recalls the principles of the NF design pattern, and Huet's zippers. Section 3 describes our approach in detail through a concrete use case. Section 4 reports on the implementation and application of our approach to several tasks. The principle of the NF design pattern [START_REF] Ferr É | Bridging the gap between formal languages and natural languages with zippers[END_REF] is schematized as a "suspended bridge over the NL-FL gap" in Figure 1. The central pillar is made of Abstract Syntax Trees (AST) with a focus on one AST node. The nature of the intermediate language abstracted by the ASTs depends on the application: e.g., queries, descriptions, logical axioms. The AST is initialized by the system, and modified by users applying structural transformations, not by direct textual input. For that reason, it is important to design a complete set of transformations, so that every AST is reachable through a finite sequence of transformations. Conversely, only safe transformations should be suggested to users, so as to avoid syntactic and semantic errors. In the case of querying, a semantic error could be applying a transformation that leads to an empty result. In the case of ontology construction, it could be constructing an axiom that leads to inconsistency.

In order for the AST structure to be understood by both the user and the machine, verbalization translates ASTs to NL, and formalization translates ASTs to FL. In addition to those translations, verbalization supports user control by showing suggested transformations in NL, and formalization supports the computation of suggestions by taking into account the semantics of the AST. A key issue in the design of ASTs is to make the two translations semantically transparent, and simple enough. First, the AST structure should reproduce the syntactic structure of NL (e.g., sentences, noun phrases, verb phrases), while abstracting as many details as possible. Indeed, starting with a flat representation like SPARQL, it is possible to produce a NL version [START_REF] Ngomo | I don't speak SPARQL: translating SPARQL queries into natural language[END_REF], but it is difficult to make it stable across transformations. Second, the AST structure should semantically align with the target FL. Indeed, every AST that can be obtained by a sequence of transformations must have a semantics that is expressible in FL. The design pattern supports multi-lingualism because only verbalization depends on the chosen NL. In particular, the NL can be changed at any time in the course of a user session. Moreover, NL generation is known to be easier than NL understanding so that it is easier to support more languages.

In this paper, we concentrate on the representation of the abstract syntax, the focus, and the transformations. We assume classical techniques for the verbalization to NL (e.g., Grammatical Framework [START_REF] Ranta | Grammatical framework[END_REF]), and for the translation to FL (e.g., Montague grammars [START_REF] Dowty | Introduction to Montague Semantics[END_REF]).

Huet's Zippers

In his "Functional Pearl" [START_REF] Huet | Functional pearl -the zipper[END_REF], Huet introduced the zipper as a technique for traversing and updating a data structure in a purely functional way, and yet in an efficient way. Pure functional programming completely avoids modification in place of data structures, and makes it much easier to reason on program behaviour, and hence to ensure their correctness [START_REF] Turner | Functional programming and proofs of program correctness[END_REF]. We here use zippers for the incremental construction of ASTs. A simple and illustrative example is on simply chained lists, their traversal, and the insertion of elements. Given a base type elt for list elements, the list datatype is defined with two constructors: one for the empty list, one for adding an element at the head of another list.

list ::= Nil | Cons(elt, list) The AST of list [1, 2, 3] is Cons(1, Cons(2, Cons(3, Nil)))
. The zipper idea is to keep a location in the list such that it is easy and efficient to insert an additional element at that location, and also to move that location to the left or to the right. A location (e.g. at element 2 in the above list) splits the data structure in two parts: the sub-structure at the location ([2, 3]), and the surrounding context ([1, ]). It has been shown that the context datatype corresponds to a data structure with one hole, and can be seen as the derivative of the structure datatype [START_REF] Abbott | ∂ for data: differentiating data structures[END_REF]. We therefore name list ("list-prime") the context datatype for lists, and define it as follows.

list ::= Root | Cons (elt, list )
That definition says that a list occurs either as a root list or as the right-argument of constructor Cons, which has in turn its own context. For example, the context at location 3 of list [1, 2, 3] is Cons (2, Cons (1, Root)). In fact, a list context is the reverse list of the elements before the location. Finally, a zipper data structure combines a structure and a context: zipper ::= List(list, list ). A zipper contains all the information of a data structure plus a location in that structure. That location is also called "focus".

A zipper makes it easy to move the location to neighbour locations, and to apply local transformations such as insertions or deletions. For example, to insert an element x in a list zipper List(l, l ) is as simple as returning the zipper List(Cons(x, l), l ). Given a zipper List(l, Cons (e, l )), the location can be moved to the left by returning the zipper List(Cons(e, l), l ).

Detailed Use Case: SPARQL-based Querying

In this section, we describe in detail our approach taking SPARQL-based querying as a use case2 . Our abstract intermediate query language covers the basic graph patterns, and their composition with union (UNION) and negation (NOT EXISTS).

AST Zippers

The following datatype definitions describe the abstract syntax of our query language. Given base types for RDF nodes (node), RDFS classes (class), and RDFS properties Note that this is very similar to the definition of abstract syntax in Grammatical Framework [START_REF] Ranta | Grammatical framework[END_REF], with categories here in italic, and functions here in bold. Node np in Figure 2 points to the tree representation of an example AST. It has type np, and specifies "any film directed by Steven Spielberg and whose genre is SF or Fantasy". The AST definitions reflect NL syntax with noun phrases and verb phrases, but is indeed abstract because all sorts of syntactic distinctions are ignored. The type vp is used to represent relative clauses (occurence of vp in DetThat) because the two have the same semantics. The two constructors Has and IsOf account for the traversal direction of a property, but not whether the property is verbalized with a verb, a noun, or a transitive adjective. Note that Boolean connectors are defined on both NPs and VPs.

The following datatype definitions describe the structure of AST contexts. They are automatically obtained as the derivatives of the AST datatypes (see Section 2.2). When a constructor has several arguments (e.g., And), the derived constructors are indexed by the position of the focus (e.g., And 2 for a focus on the second argument).

np 2 points to the tree representation of an example AST context. It has type np , and specifies the one-hole AST "select the release date of ", where the underscore (hole) gives the location of the zipper sub-structure. Note that the path in the context AST from the root to Select is the reverse of the path in the one-hole AST from the root to the hole. Finally, the following datatype definition describes a AST zipper, combining an AST and an AST context.

zipper ::= NP(np, np ) | VP(vp, vp )

Therefore, when editing a query, the focus can be put on any noun phrase (i.e. on any entity involved in the query) or on any particular verb phrase (i.e. on any description of any entity in the query). Figure 2 displays the tree representation of an example zipper that represents the NL question "Give me the release date of films directed by Steven Spielberg and whose genre is SF or Fantasy", where the focus is on films. Its formalization in SPARQL is: SELECT ?x1 ?x2 WHERE {?x2 dbo:releaseDate ?x1. ?x2 rdf:type dbo:Film. ?x2 dbo:director dbr:Steven Spielberg. {?x2 dbo:genre "SF"} UNION {?x2 dbo:genre "Fantasy"}}.

A Complete Set of Zipper Transformations

Because ASTs are only built by the successive and interactive application of transformations, it is important to define one or several initial zippers and a set of zipper transformations that makes the building process complete.

Definition 1 (completeness).

A set of initial zippers and a set of zipper transformations are complete w.r.t. AST datatypes iff every AST zipper can be reached by applying a finite sequence of transformations starting with an initial zipper.

We start by defining an initial AST x 0 for each AST datatype x: s 0 := Select(np 0 ), np 0 := DetThat(Some, owl:Thing, True), vp 0 := True. An initial zipper can then defined as zipper 0 := NP(np 0 , Select ). It corresponds to the totally unconstrained query that returns the list of everything. A menu of application-specific initial zippers can be added according to frequent types of queries, and so that the users have less transformations to perform.

We continue by defining a number of zipper transformations. A zipper transformation is formally defined as a partial mapping from zipper to zipper. Transformations are denoted by all-uppercase names, and are defined by unions of mappings from a zipper pattern to a zipper expression. We strive to define our transformations in terms of the domain vocabulary rather than in terms of the AST constructs, so as to avoid exposing users to the latter. Therefore, our first transformations insert the primitive elements (i.e. nodes, determiners, classes, and properties) depending on the current focus. Other transformations allow the introduction of the Boolean connectors between noun phrases and verb phrases. They are defined in a generic way below, where X/x stands for both NP/np and VP/vp. Transformations AND, OR coordinate a substructure x with an initial AST x 0 , and move the focus to x 0 . Transformation NOT toggles the application of negation.

AND := X(x, x ) → X(x 0 , And 2 (x, x )) A generic DELETE transformation can also be defined to undo insertions.

OR := X(x, x ) → X(x 0 , Or 2 (x, x )) NOT := X(Not(x), x ) → X(x, x ) | X(x, x ) → X(Not(x), x ) T (Node(n)) := NODE(n) T (DetThat(d,
DELETE := X(x, x ) → X(x 0 , x)
In order to allow transformations at an arbitrary focus, it is important to allow moving the focus through the AST. To this purpose, we define four transformations UP, DOWN, LEFT, RIGHT to move the focus respectively up to the parent AST node, down to the leftmost child, to the left sibling, and to the right sibling. We only provide the definitions for constructor And(np, np) as other constructors work in a similar way. Proof. First, it is easy to show that the moving transformations give access to all zippers of an AST. Therefore, to prove completeness, it is enough to prove that every zipper in the form NP(np, Select ) is reachable. Figure 3 defines a recursive function T (x) that returns a transformation sequence from an initial AST x 0 to any AST x, where x stands for any AST datatype. For each case, it can be proved that the transformation sequence T (x) indeed leads from x 0 to x, and that every recursive call is well defined (sub-structure x 0 at focus). ID is the identity transformation.

The above proof provides an algorithm T for computing the transformation sequence leading to any AST x. The example zipper given in Figure 2 can be reached with the following sequence: In practice, it appears useful to tune transformations so as to minimize the number of interaction steps for users: e.g., moving down after inserting a property, moving up after inserting a node, moving down when inserting a property at a noun phrase, avoiding the insertion of default elements (e.g., determiner Some, class owl:Thing). Applying those rules reduces the number of steps in the example from 19 to 9:

PROP -(dbo:genre); CLASS(dbo:Film); PROP(dbo:director); NODE(dbr:Steven Spielberg); AND; PROP(dbo:genre); NODE("SF"); OR; NODE("Fantasy").

Implementation, Applications, and Evaluation

Our approach of authoring based on zippers and transformations is implemented in a functional programming language (OCaml), and has already been used in three applications: SPARKLIS3 [START_REF] Ferr É | Sparklis: An expressive query builder for SPARQL endpoints with guidance in natural language[END_REF], UTILIS [START_REF] Hermann | An interactive guidance process supporting consistent updates of RDFS graphs[END_REF], and PEW [START_REF] Ferr É | Semantic authoring of ontologies by exploration and elimination of possible worlds[END_REF]. Those applications target different tasks and formal languages (FL). SPARKLIS targets semantic search with SPARQL; UTILIS targets descriptions of RDF nodes; and PEW targets ontology design and completion with OWL class expressions. All include the conjunctive subset of the intermediate language defined in previous section, and extends it with task-specific constructs. In each application, the user interface has three parts (see Figure 4 for a screenshot): the current sentence and focus (top), the suggested transformations (center), and the semantic interpretation of the sentence (bottom). The latter is made of query answers for SPARK-LIS, similar nodes for UTILIS, and class instances for PEW. The suggested transformations are selected so as to avoid semantically misformed sentences: e.g., empty results in SPARKLIS or inconsistent ontology in PEW. The suggested transformations are generally grouped in three categories: (a) classes and properties, (b) entities and values, (c) Boolean connectors and other transformations. The focus is highlighted in the sentence, and can be moved freely by clicking the relevant parts of the sentence.

User studies have been conducted in all three applications, and are reported in the related papers. SPARKLIS is online since April 2014, and more than 100,000 navigation steps have been performed by more than 1000 unique users. It has recently been officially adopted as a SPARQL query builder by two French institutions: Persée4 and INIST 5 . A user study comparing UTILIS to Protégé has shown that users prefered the fine-grained suggestions of UTILIS to the static entity lists of Protégé. We have also observed that those suggestions improve consistency across RDF descriptions without the rigidity of a prescriptive schema. Another user study comparing PEW to Protégé has demonstrated promising results in terms of quantity, precision, and recall of the produced axioms, and in terms of usability. A notable result is the increase in recall, from 24% with Protégé to 56% with PEW, where 100% would mean a complete OWL formalization of the domain knowledge for the selected OWL fragment. Overall, our approach requires less background knowledge, and is more productive and safe compared to the direct use of formal languages or to the use of Semantic Web tools such as Protégé. The main difficulty appears to be in the understanding of the focus, and its impact on the suggested transformations. Some training is necessary for new users but most of them progress rapidly.

Conclusion and Perspectives

We have presented an alternative solution to the problem of CNL authoring. Like the auto-completion solution, it guides the user in the authoring process, and prevents the construction of misformed sentences. The novelty lies in the fact that the system suggestions are abstract syntax transformations rather than concrete words. As a consequence, the translation between the concrete and the abstract syntaxes goes backward, i.e. from the abstract to the concrete through a verbalization process that also applies to the suggested transformations. There are two benefits: (1) constructed sentences are complete at any step of the authoring process, allowing for intermediate results and feedback (responsiveness), and (2) editions can apply at any focus, i.e. any position or part of the sentence (flexibility). We have shown how to use Huet's zippers on the abstract syntax in order to represent the current focus and efficiently apply transformations. An interesting perspective is to implement this approach in Grammatical Framework (GF), in order to offer an alternative authoring process in applications. GF already offers the definition of abstract syntax, and verbalization (called linearization in GF). The definitions of contexts and zippers can be automatically derived from the abstract syntax, and zipper transformations can be naturally defined as functions on zippers.

Figure 1 .

 1 Figure 1. Principle of transformation-based authoring for bridging the gap between NL and FL

Figure 2 .

 2 Figure 2. Example zipper made of a sub-structure (np), and a context (np )

  NODE(n) := NP(np, np ) → NP(Node(n), np ) DET(d) := NP(DetThat(det, class, vp), np ) → NP(DetThat(d, class, vp), np ) CLASS(c) := NP(DetThat(det, class, vp), np ) → NP(DetThat(det, c, vp), np ) | VP(True, vp ) → VP(IsA(c), vp ) PROP(p) := NP(DetThat(d, c, True), np ) → VP(Has(p, np 0 ), DetThat 3 (d, c, np )) | VP(True, vp ) → VP(Has(p, np 0 ), vp ) PROP -(p) := (same as PROP, replacing Has by IsOf)

Figure 3 .

 3 Figure 3. Recursive definition of the transformation sequence T (x) from x 0 to AST x

  DOWN := NP(And(np 1 , np 2 ), np ) → NP(np 1 , And 1 (np , np 2 )) UP := NP(np 1 , And 1 (np , np 2 )) → NP(And(np 1 , np 2 ), np ) | NP(np 2 , And 2 (np 1 , np )) → NP(And(np 1 , np 2 ), np ) RIGHT := NP(np 1 , And 1 (np , np 2 )) → NP(np 2 , And 2 (np 1 , np )) LEFT := NP(np 2 , And 2 (np 1 , np )) → NP(np 1 , And 1 (np , np 2 )) Theorem 1 (completeness). The initial zipper zipper 0 = NP(np 0 , Select ) and the above set of transformations is complete, assuming transformation NODE(n) is suggested for all nodes of the target RDF graph, and similarly for transformations DET(d), CLASS(c), PROP(p), and PROP -(p).

Figure 4 .

 4 Figure 4. Screenshot of SPARKLIS

This research is supported by ANR project PEGASE (ANR-16-CE23-0011-08).

The complete source code of an extension of this use case is available online in the OCaml programming languages. Visit http://www.irisa.fr/LIS/ferre/pub/CNL2018.ml

Online version at http://www.irisa.fr/LIS/ferre/sparklis/ with examples and screencasts.

http://data.persee.fr/

https://www.loterre.fr/category/explorer/

Acknowledgements. We thank the anonymous reviewers for their valuable feedback, and insightful suggestions, as they helped to improve this paper.