Azzeddine Amiar

Mickaël Delahaye

Yliès Falcone

Lydie Du Bousquet

CoMET: Compressing Microcontroller Execution Traces to Assist System Understanding

Keywords: trace comprehension, cyclic program, execution trace, trace compression, Sequitur

Recent technology advances have made possible the retrieval of execution traces on microcontrollers. However, even after a short execution time of the embedded program, the collected execution trace contains a huge amount of data. This is due to the cyclic nature of embedded programs. The huge amount of data makes extremely difficult and time-consuming the understanding of the program behavior. Software engineers need a way to get a quick understanding of execution traces. In this paper, we present an approach based on an improvement of the Sequitur algorithm to compress large execution traces of microcontrollers. By leveraging both cycles and repetitions present in such execution traces, our approach offers a compact and accurate compression of execution traces. This compression may be used by software engineers to understand the behavior of the system, for instance, identifying cycles that appears most often in the trace or comparing different cycles. Our evaluations give two major results. On one hand our approach gives high compression rate on microcontroller execution traces. On the other hand software engineers mostly agree that generated outputs (compressions) may help reviewing and understanding execution traces.

I. INTRODUCTION

Most of the automated systems contain microcontrollers, from car engines to domestic appliances. Although there are many development environments for embedded applications, there are few tools dedicated to their analysis. A manual analysis is a tedious and time consuming task [START_REF] Rohani | An analysis of fault effects and propagations in AVR microcontroller ATmega103(L)[END_REF]. In our work, we aim to make it easier for software engineers to understand a microcontroller behavior by exploring execution traces.

In general, software engineers have to either analyze electrical signals generated from components, or try to reproduce microcontroller behaviors using simulation [START_REF] Shamnur | XStatic: A simulation based ESD verification and debug environment[END_REF], [START_REF] Chatterjee | Simulation-based signal selection for state restoration in silicon debug[END_REF]. However, the manual process and the lack of information about external devices that are connected to a microcontroller, does not allow software engineers to reproduce the real behavior of the embedded application. In the past few years, a technique has been proposed to collect basic execution traces using a specific probe [START_REF] Arm | Embedded trace macrocells (ETM)[END_REF]. Recording microcontroller execution enables software engineers to collect information about the system behavior as an execution trace without input/output data [START_REF] Ko | Automated trace signals identification and state restoration for improving observability in post-silicon validation[END_REF], [START_REF] Basu | Efficient trace signal selection for post silicon validation and debug[END_REF]. However, collected execution traces are often very large [START_REF] Hamou-Lhadj | Compression techniques to simplify the analysis of large execution traces[END_REF], [START_REF] Burtscher | The VPC trace-compression algorithms[END_REF] and incomprehensible. The huge amount of data is mainly due to the real-time and cyclic nature of microcontroller applications. Consequently, even for the most experienced engineer, a manual analysis of such traces takes significant effort and time. Since such applications are cyclic, a limited number of different instructions are executed numerous times.

In this paper, we aim to help software engineers to look over an execution trace faster, and to make more informed decisions on which part(s) of the trace they need to analyze in detail. To facilitate the comprehension of execution traces, we propose a compression approach based on a grammar generation. We formalize and extend the Sequitur algorithm [START_REF] Nevill-Manning | Identifying hierarchical structure in sequences: A linear-time algorithm[END_REF], which, given an input trace, produces a grammar by leveraging regularities frequently found in the input trace. The output grammar is an accurate but compact representation of the input trace. Our algorithms are implemented in a tool named J-Cyclitur, which is written in the Java programming language and is freely available at http://io32.forge.imag.fr. The J-Cyclitur enables us to compress several real traces coming from embedded applications (gathered using the ETM probe) and network traffic simulations.

The rest of the paper is organized as follows. The next section exposes the context of applications that are embedded on microcontrollers. Section III proposes a formalization of the Sequitur algorithm, this formalization is based on several informal descriptions found in the literature. In Section IV, we present the Cyclitur algorithm, which is an extension of the Sequitur algorithm in the context of cyclic embedded applications. Our algorithm is empirically validated in Section V. Section VI discusses related work, and, Section VII draws some conclusions and perspectives.

II. MICROCONTROLLER APPLICATION CONTEXT

A microcontroller is an integrated circuit that consists of all elements of a microprocessor-based structure [START_REF] Parab | Exploring C for microcontrollers: A hands on approach[END_REF], such as a microprocessor (CPU), data memory (RAM, EEPROM), program memory (ROM, OTPROM, UVPROM or EEPROM), and input/output. Thanks to the affordable prices of microcontrollers, the development of embedded applications is now within reach of non-specialists. For example, a 32-bit microcontroller, with 128Kb of SRAM and 1Mb FLASH, costs about 7 USD, and can meet numerous use cases.

In recent past, debugger engineers used oscilloscopes to analyze embedded applications by interpreting electric sig-nals. Thanks to the arrival of new microcontrollers, the situation is changing. For instance, the microcontroller ARM Cortex-Mx [START_REF] Arm | Cortex-M series[END_REF] includes a part dedicated to trace collection, called ETM cell (Embedded Trace Macrocell) [START_REF] Arm | Embedded trace macrocells (ETM)[END_REF]. Using a probe [START_REF] Arm | [END_REF], it is possible to obtain a trace in the form of a series of the so-called instruction-sequence breaks that reflects the execution. A sequence break occurs during the execution of a program when next instruction does not directly follow the current one, it is a jump.

A typical example of C program for microcontrollers is shown in Listing 1. If the condition at line 31 evaluates to false, the next executed instruction is not the instruction at line 32 but the instruction at line 35. The destination addresses of jumps are recorded by the ETM cell. The probe enables the user to extract the execution trace as a set of sequence breaks ordered by their occurrence in time. The execution trace obtained for the particular program shown in Listing 1 contains the following lines: 2, 7, 10, 13, 16, 19, 22, 25, 31, 35 and 39, where each line corresponds to a sequence break.

As can be seen in Listing 1, such program contains an infinite main loop (starting at line 2), to scan actively the inputs of the microcontroller and calculate the outputs. The huge amount of data contained in the trace (even after a short time execution) is mainly due to this infinite loop.

In this paper, we address the first two steps of the debug process, namely the comprehension and the analysis of execution traces. Indeed, we propose a method to compress the execution traces [START_REF] Larus | Whole program paths[END_REF], [START_REF] Hamou-Lhadj | Compression techniques to simplify the analysis of large execution traces[END_REF], [START_REF] Hamou-Lhadj | Summarizing the content of large traces to facilitate the understanding of the behaviour of a software system[END_REF] of microcontroller embedded programs. We exploit the presence of the infinite main active loop to generate a compression. We call loop header the instruction that defines this main active loop. The compression is based on the Sequitur algorithm, which is discussed in the following section.

III. A FORMALIZATION OF SEQUITUR

In the literature, Sequitur [START_REF] Nevill-Manning | Identifying hierarchical structure in sequences: A linear-time algorithm[END_REF] is described at an informal level. In this section we propose a formalization of Sequitur and the grammars that it generates.

Preliminaries: An alphabet Σ is a finite set of symbols. Given an alphabet Σ, a string (or word) is a sequence of symbols of Σ. The set of all finite strings on Σ is noted Σ * . The length of a string σ ∈ Σ * , noted |σ|, is the number of symbols in σ. The empty string over Σ, i.e., the string of length 0, is noted Σ or when clear from context. By σ i we indicate the i-th element of σ. A digram is defined as a string of length 2.

A. Sequitur Grammars

Below we present the grammar generated by Sequitur and their properties.

Definition 1 (Sequitur Grammar). A Sequitur grammar is a tuple Σ, Γ, S, ∆ where: • and ∆ ⊆ Γ × (Σ ∪ Γ) * is a finite set of production rules (or simply rules), such that the following properties are verified:

• Σ is a finite alphabet of terminal symbols, • Γ is a disjoint finite alphabet of nonterminal symbols, • S ∈ Γ is a start symbol, i.e.,
• for every nonterminal A, there is a unique string α such that A, α is in ∆ and |α| is at least 2, • there is a strict partial order over Γ, such that, for all production rule A, α ∈ ∆, every nonterminal in α precedes A.

A production rule A, α ∈ ∆ is noted A → α, where the nonterminal A (resp. the string α) is called the head (resp. the body) of the rule. By extension, the grammar body is the set of the rules' bodies {α | ∃A : A, α ∈ ∆}. The start rule is the unique rule whose head is the start symbol S. Note that in Sequitur grammars, there is exactly one rule γ → σ per nonterminal γ ∈ Γ. In addition, a partial order over Γ ensures that the grammar is non-recursive (cycle-free). In the following, a Sequitur grammar is simply called a grammar and we consider a grammar G = Σ, Γ, S, ∆ . When clear from context, we might refer to a rule by its head.

1 let S be a fresh nonterminal (S / ∈ Σ ∪ Γ 0 ) 2 G ← Σ, Γ 0 ∪ {S}, S, ∆ 0 ∪ { S, } 3 for i = 1 to |ω| do
replace both occurrences of δ in G with D ∆ ← ∆ ∪ { D, δ } Γ ← Γ ∪ {D} end else if ¬ Utility(G) then let A, α ∈ ∆ be a rule used once replace the occurrence of A with α in G ∆ ← ∆ { A, α } Γ ← Γ {A} end end end return G Fig. 1. Function Sequitur(Σ, ω, Γ 0 , ∆ 0 )

B. Algorithm

Sequitur, proposed by Nevill-Manning and Witten [START_REF] Nevill-Manning | Identifying hierarchical structure in sequences: A linear-time algorithm[END_REF], is a grammar-based compression algorithm used in a variety of fields, ranging from bio-informatics to natural language processing. To generate a compression, Sequitur takes a string as input, and finds repeated subsequences present in the string to build a compact grammar. It operates in linear time and in an online fashion. Each repetition gives rise to a rule in the grammar, and is replaced with a nonterminal symbol. The compression process is executed iteratively. To illustrate how Sequitur operates, let us consider the string: abcabcabcabcabc. Sequitur generates the following grammar:

S → AAB A → BB B → abc
The original string contains 15 symbols and the grammar generated using Sequitur contains 11 symbols. The compression results in the explicit capture of the repetitions of the subsequence abc. We shall explain how this resulting grammar is obtained using the algorithm of Fig. 1. The referred lines are those of Fig. 1. Sequitur takes as input four parameters: a set of terminal symbols Σ, a string ω, the initial set of nonterminal symbols Γ 0 , which can be the empty set or not 1 , and ∆ 0 the initial set of rules (can be empty or not). Sequitur starts with a start rule with as body, and iterates over the characters of the input string. Each character is handled in two phases. First, Sequitur adds the new character as a terminal symbol at the end of the body of the start rule (line 4). Second, if it is necessary (line 5), it applies one or more reduction steps in order to ensure two properties on the grammar: digram uniqueness (from line 6 to 15) and rule utility (from line 16 to 20).

(A = B ∧ A → α ab β ∧ B → γ cd δ) ⇒ ab = cd (1) (A → α ab β cd γ) ⇒ ab = cd . (2)
Statement (1) says that if G contains two rules A → α ab β and B → γ cd δ with A = B, then ab is not equal to cd. Table I details step-by-step the application of Sequitur on the input string abcabc. For each step, this table indicates the number of read symbols (i), the current grammar, the undertaken action with the corresponding line(s) in the algorithm, and the status of the two properties (digram uniqueness and rule utility). On this example, after adding the symbol b to the body of rule S, abca at step 5, the digram ab occurs twice, and consequently the digram uniqueness property is violated. Sequitur creates a new rule A, ab with a new nonterminal A as head, and the digram ab as body, to replace both digram occurrences in the grammar with A, as in step 6.

Statement (2) says that if G contains a rule A → α ab β cd γ,
2) Rule utility: It ensures that every rule (nonterminal) except the start rule is used more than once in the grammar body.

Property 2 (Rule utility). The rule utility property holds for G, noted Utility(G) if:

∀A ∈ Γ\{S} : B,β ∈∆ {i ∈ [1..|β|] | β i = A} ≥ 2 .
Sequitur ensures the rule utility property as follows. If a rule is referred to once (line 16), Sequitur eliminates it, and replaces the occurrence of its head (nonterminal) with its body (lines [START_REF] Hamou-Lhadj | Effective exploration and visualization of large execution traces[END_REF][START_REF] Heizmann | Refinement of trace abstraction[END_REF][START_REF] Gailly | [END_REF][START_REF] Aoe | Computer Algorithms: String Pattern Matching Strategie[END_REF]. Note that, this mechanism allows the formation of rules whose body consists of more than two symbols.

On the example of Table I, after adding the next input symbol c at step 7, Sequitur introduces the new rule B → Ac to ensure the digram uniqueness property in step 8. In the resulting grammar, the nonterminal A occurs once in the grammar body, precisely in the body of rule B → Ac. In this case, in step 9, to restore the rule utility property, Sequitur eliminates rule A → ab and replaces the occurrence of A in the body of B → Ac with the digram ab.

Note that Sequitur terminates on all finite input strings. Each input symbol is added one at a time and each addition may trigger a finite sequence of reduction steps. Indeed, the sequence of steps is finite because each reduction step, for either property, ensures that the following quantity strictly decreases (w.r.t. the lexicographical order on N 2 ):

A,α ∈∆ {i ∈ [1..|α|] | α i ∈ Σ} , ∆ ,
that is, either the number of terminal occurrences in the grammar (i.e., the sum of the number of terminal occurrences in each rule body) decreases, or it stays the same but the number of rules decreases. Sequitur compresses a string in linear time [START_REF] Nevill-Manning | Identifying hierarchical structure in sequences: A linear-time algorithm[END_REF]. Indeed, given an input string of length n, if each addition may lead to up to O( √ n) reduction steps, the overall algorithm execution does not take more than O(n) reduction steps.

IV. MICROCONTROLLER TRACE COMPRESSION

We describe in this section the improved Sequitur algorithm.

A. Squeezing repetitions 1) Enhanced string (r-string) and grammar (r-grammar): Given an alphabet Σ, an r-string ψ is a sequence of symbols with a number of consecutive repetitions. In other words, it is a sequence of pairs symbol, strictly positive integer . The set of r-strings over Σ is Σ * r = (Σ × N \ {0}) * . In an r-string ψ, ψ i,1 stands for the symbol of the i-th element of ψ and ψ i,2 stands for its number of repetitions. |ψ| denotes the number of elements in the r-string ψ. To lighten notations, repetition numbers are placed in superscript after symbols and they are omitted when equal to one. For instance, ab 5 d 10 is a shorthand for the sequence a, 1 b, 5 d, 10 . The expansion of the rstring ψ ∈ Σ * r , noted ψ, is a string in Σ * , and is defined as follows:

ψ = ψ 1,1 • • • ψ 1,1 repeated ψ1,2 times ψ 2,1 • • • ψ 2,1 ψ2,2 times • • • ψ |ψ|,1 • • • ψ |ψ|,1 ψ |ψ|,2 times .
Note that |ψ| indicates the number of pairs symbol, number , and not the number of symbols in the expansion (| ψ|).

Definition 2 (r-grammar). An r-grammar G is a 4-tuple Σ, Γ, S, ∆ where:

• Σ is a finite alphabet of terminal symbols, • Γ is a disjoint finite alphabet of nonterminal symbols, • S ∈ Γ is a start symbol, i.e., a particular nonterminal, • and ∆ ⊆ Γ × (Σ ∪ Γ) *
r is a set of r-production rules, such that the following properties are verified:

• for every nonterminal A, there is a unique r-string α such that A, α is in ∆ , • there is a strict partial order over Γ, such that, for all production rule A, α ∈ ∆ , every nonterminal in α precedes A.

An r-production rule A, α ∈ ∆ is noted A → α, where the nonterminal A (resp. the r-string α) is called the head (resp. the body) of the rule. The r-grammar body is {α | ∃A : A, α ∈ ∆ }, i.e., the set of the rules' bodies. In the following, we consider an r-grammar G = Σ, Γ, S, ∆ .

2) Enhanced compression ReSequitur: Given in Fig. 2, ReSequitur is inspired from Sequitur [START_REF] Nevill-Manning | Identifying hierarchical structure in sequences: A linear-time algorithm[END_REF]. Indeed, it ensures that adapted versions of digram uniqueness and rule utility properties hold on its output r-grammar: Property 3 (Digram uniqueness). The digram uniqueness property holds for G , noted RUniqueness(G ), if for all terminals A, B ∈ Γ, symbols a, b, c, d ∈ Σ ∪ Γ, strictly positive integers n, m, p, q ∈ N\{0}, and r-strings α, β, γ, δ ∈ (Σ ∪ Γ) * r , the two following statements hold:

(A = B ∧ A → α a n b m β ∧ B → γ c p d q δ) =⇒ a n b m = c p d q (3) (A → α a n b m β c p d q γ) =⇒ a n b m = c p d q . ( 4
) Statement (3) states that if ∆ contains two rules A → α a n b m β and B → γ c p d q δ with A = B, then a n b m is not equal to c p d q (that is, a = c ∨ b = d ∨ n = p ∨ m = q). State- ment (4) states that if ∆ contains a rule A → α a n b m β c p d q γ, then a n b q is not equal to c p d q .
Property 4 (Rule utility). The rule utility property holds for G , noted RUtility(G ), if:

∀A ∈ Γ \ {S} : B,β ∈∆ i∈[1..|β|] β i,2 if β i,1 = A 0 if β i,1 = A ≥ 2 .
Property 4 states that for each nonterminal A ∈ Γ, if A is not the start symbol S, it must be used at least twice in the grammar body (taking account consecutive repetitions).

In addition, ReSequitur ensures another property stating that any digram in an r-grammar body is composed of different symbols.

Property 5 (No consecutive repetition). G has no consecutive repetitions, which is noted RConsecutive(G ), if:

∀a, b ∈ Σ ∪ Γ, ∀n, m ∈ N \ {0}, ∀α, β ∈ (Σ ∪ Γ) * r , ∀C ∈ Γ : C, α a n b m β ∈ ∆ ⇒ a = b .
To ensure this property at each iteration of the outer loop, ReSequitur merges every digram of the form a n a m into a single repeated symbol a n+m (Fig. 2, lines 6-8).

B. Detecting and exploiting cycles with Cyclitur

Recall that the objective of our work is to compress cyclic traces extracted from microcontrollers. The main characteristic of the programs at the origin of these traces, is the active main loop, which is often expressed using a while(1) statement.

The first step in our approach is cycle detection. A cycle is a subsequence of the execution trace that represents one execution of the main active loop of the embedded program. Cycle detection relies on the localization of a special event that represents the loop header, noted lh. Definition 3 (Set of Cycles). For a string ω, and a loop header lh, the set of cycles in ω using the loop header lh is defined as:

C(ω, lh) = { i, j ∈ N 2 | 1 ≤ i ≤ j ≤ |ω| ∧ ω i = lh ∧ (j = |ω| ∨ ω j+1 = lh) ∧ ∀k ∈ [i + 1..j] : ω k = lh} .
C(ω, lh) is a set of pairs of indexes, where each pair i, j represents a subsequence (cycle) ω i..j . For each cycle i, j , the subsequence ω i..j starts with the loop header lh (except for the first one if the trace does not start with the loop header), contains at most one occurrence of the loop header lh, and ends either with the symbol before the next occurrence of the loop header lh or at the end of the sequence ω.

Detecting cycles using the loop header event essentially consists in dividing the trace into blocks, where each block represents a specific cycle. ReSequitur is applied on each of

1 let S be a fresh nonterminal representing a rule (S / ∈ Σ ∪ Γ 0 ) 2 G ← Σ, Γ 0 ∪ {S}, S, ∆ 0 ∪ { S, } 3 for i ← 1 to |ω| do 4 append (ω i )
1 to body of rule S

1 ω ← 2 foreach i, j ∈ C(ω, lh) in increasing order do 3 Σ , Γ , S , ∆ ← ReSequitur(Σ, ω i..j , Γ 0 , ∆ 0 ) 4 Γ 0 ← Γ 5 ∆ 0 ← ∆ 6 ω ← ω • S 7 end 8 Σ , Γ , S , ∆ ← ReSequitur(Σ, ω , Γ 0 , ∆ 0 ) 9 return Σ , Γ , S , ∆ Fig. 3. Function Cyclitur(Σ, ω, Γ 0 = ∅, ∆ 0 = ∅, lh)
these block, to detect repetitions inside cycles (Fig. 3, lines 2-7), while sharing the same set of rules. Applying ReSequitur algorithm on the compression produced by the previous step allow us to detect similar sequences of cycles in the trace (Fig. 3, line 8).

V. IMPLEMENTATION AND EVALUATION

The first step in the evaluation of our trace-compression approach is an experimental evaluation, which consists in comparing grammars obtained by applying Sequitur and Cyclitur on various execution traces. The experimental evaluation was made possible thanks to J-Cyclitur. The second step is a qualitative evaluation, which evaluates the quality of the produced compressions, and measures their capability to help software engineers decide which parts they want to analyze in detail.

A. J-Cyclitur

J-Cyclitur is a tool written in Java in 4,000 LOC that implements both Sequitur and Cyclitur algorithms. It takes as input an execution trace file. It extracts automatically a string of symbols. For instance, given a microcontroller execution trace, a symbol is a program counter. Then J-Cyclitur compresses the string using Sequitur and Cyclitur algorithms. Finally, it outputs a grammar, either as text or as a Java object for programmatic use.

B. Metrics of experimental evaluation

In the following, we use a given string (trace) ω, and the output grammar (resp. r-grammar) generated with Sequitur (resp. Cyclitur), noted G = Σ, Γ, S, ∆ .

1) Grammar size: The size of the grammar G is the sum of the number of symbol occurrences in its body (both terminals and nonterminals) and the number of its rules.

2) Compression ratio: Noted Comp(G), this metric is used to compare the degree of compression of grammars generated using Sequitur and Cyclitur.

Comp(G) =

Size(G) |ω|

3) Compressed cycle size: For a generated compression, this third metric indicates how many symbols are analyzed in the grammar to detect a particular cycle. This metric can also be seen as the number of paths that the debugger engineer shall follow in the grammar to find an entire cycle.

Note that the cycle detection step in Cyclitur ensures that each cycle corresponds to a single symbol, then the compressed cycle size is always one with Cyclitur.

C. Programs and traces

The traces used to evaluate our approach come from five embedded programs, which are provided by STMicroelectronics and EASii IC. For confidentiality reasons, programs are not described. In the following we denote by Pi the program number i.

Once at a time, each program is downloaded on a STM32F107 EVAL-C microcontroller board and executed. The trace produced by the execution is recovered using a Keil Ulinkpro probe [START_REF] Arm | [END_REF], and saved in CSV format. In the trace file, for each instruction, we have its index, which is an ID, the time when it was executed, its corresponding assembly instruction and the program counter (PC). For our compression approach we are only interested in the PCs. For each program, five execution traces are produced.

D. Results

Table II contains the results of the experimental evaluation,

where each line represents a trace of a program. The two columns (# Symbols) and (# Cycles) represent respectively the number of symbol occurrences and the number of cycles in a trace. For a grammar G generated by Sequitur, Table II contains its size (Size(G)), its compression ratio (Comp(G)), and the average of the compressed cycle size over cycles (AvgAC (G)). For a grammar G generated by Cyclitur, Table II contains its size (Size(G )), and its compression ratio (Comp(G )). For Cyclitur, Table II does not contain AvgAC (G ), which is the average of the compressed cycle size in the grammar G , because, by construction, the compressed cycle size of any cycle in a Cyclitur-generated grammar is always equal to one.

Fig. 4 graphically summarizes these results. For both algorithms (Sequitur in gray and Cyclitur in white), and for each program, Fig. 4 displays the arithmetic average of the compression ratios over the five collected traces of the program.

Note that the use of the other average measures gives different values, but the same result: the difference between the generated compressions using Sequitur and Cyclitur. In Fig. 4, the arithmetic average is used to have a better illustration. The compression ratio takes value between 0 and 1, where 0 represents the best compression, and 1 the worst.

In Fig. 4, we compare for each program, the average of compression computed using the grammars generated by Sequitur and the grammars generated by Cyclitur. For example, for program P1, we observe that our approach produces better compression than Sequitur. The sizes of grammars generated by Sequitur for the execution traces of P1 vary from 1,181 up to 2,631; they contain 214-387 terminals, 728-1,689 nonterminals, and 239-1,689 rules. The sizes of original traces vary between 1,048,571 and 1,048,576, with 31,562-53,821 cycles. Therefore, the ratios of compression vary between 0.0011 and 0.0025. Cyclitur produces grammars whose sizes vary from 1,139 to 2,044 with 213-385 terminals, 687-1,237 nonterminals, and 239-423 rules. The compression ratios vary between 0.0010 and 0.0019. Also, when Sequitur-generated grammars require 5-13 symbols (AvgAC (G)) to represent a cycle, Cyclitur ensures each cycle can be represented as a unique symbol. In Fig. 4, we note that for all the programs used in the experimental evaluation, the use of Cyclitur generates a better compression than Sequitur. The ratios of compression are better from 15% to 30%.

E. Cyclitur and network traces

We evaluate our trace-compression approach on four additional traces obtained from network simulations. The considered network is a Multi-Channel Multi-Interface Wireless Mesh Network (WMN) with routers based on the IEEE 802.11 technology [START_REF] Oliveira | Connectivity in multichannel multi-interface wireless mesh networks[END_REF]. The loop header used to detect cycles and to divide generated traces into blocks is a specific event that refers to the emission a request from client to server. The first trace consists of 6,011,850 events spread over 9,574 cycles. The ratio of compression using Sequitur is 0.0027% for a generated grammar whose size is 16,531, and which contains 744 terminals, 12,375 nonterminals and 3,412 rules. The size of the grammar generated using Cyclitur is 16,057; it contains 373 terminals, 13,884 nonterminals and 4182 rules. The compression ratio for Cyclitur grammar is 0.0026%.

The second trace consists of 8,040,942 events spread over 9,574 cycles. Sequitur generates a grammar whose size is 18,639, and which contains terminals, 14,042 nonterminals and 3,881 rules. The size of the grammar generated

Compression

Ratio

Trace

Sequitur Cyclitur Fig. 5. Compared compression ratios for each WMN trace using Cyclitur is 18,439; it contains 373 terminals, 13,884 nonterminals and 4,182 rules. The use of Sequitur and Cyclitur on the second trace gives respectively 0.00023% and 0.0022% as compression ratio. Cyclitur generates a grammar that contains more rules than the grammar generated by Sequitur, although the Cyclitur compression is easier to understand and to analyze, because it is more compact and it facilitates cycle detection.

The third WMN trace contains 10,312,955 events spread over 33,834 cycles. Sequitur generates a grammar that contains 605 terminals, 12,584 nonterminals, and 3,501 rules. The compression ratio for the Sequitur grammar is 0.0016%. Cyclitur generates a grammar that contains 272 terminals, 7,783 nonterminals, and 2,090 rules. The compression ratio for the Cyclitur grammar is 0.0009%.

The last WMN trace contains 13,883,977 events spread over 2,797 cycles. The ratio of compression using Sequitur is 0.0020% for a generated grammar whose size is 28,181 and which contains 661 terminals, 21,575 nonterminals and 5,945 rules. The size of the grammar generated using Cyclitur is 26,468; it contains 349 terminals, 20,108 nonterminals and 6,011 rules. The compression ratio for Cyclitur grammar is 0.0019%.

The previous results show that Cyclitur can be used likewise to compress trace collected from networks. In Fig. 5, we note that for all network traces used in the experimental evaluation, the use of Cyclitur generates a better compression than Sequitur. Note that the compression ratio takes value between 0 and 1, where 0 represents the best compression, and 1 the worst.

F. Quality evaluation

We performed a study to evaluate the quality of the produced compressions, and to measure their capability to help software engineers decide which parts they want to analyze in detail.

1) Subjects and the object of study: To evaluate trace compressions, we made an online evaluation using:

• An execution trace that contains 15,391 lines2 ,

• The Sequitur-generated compression3 (123 lines),

• The Cyclitur-generated compression 4 (113 lines). The execution trace was obtained by running on a STM32 evaluation board, a program that simply consists in counting the number of iterations of the main loop. If the iteration number is divisible by two, the program prints a specific text on the LCD screen; otherwise it turns on some LEDs for two seconds.

Without providing program source code, we asked 20 software engineers to evaluate the capability of the compressions to assist in the understanding of system behavior. Assisting in the understanding of system behavior consists in helping decide which cycles in the trace should be analyzed in detail. Among the software engineers that participated to this quality evaluation, 20% analyze execution traces never or rarely, 55% analyze execution traces from occasionally to often, and 25% analyze execution traces from frequently to always.

2) The evaluation of compressions: To measure the subjective quality of the trace compression techniques, we designed an online opinion poll, which involves the active participation of human judges. Participants rate the compressions generated using Sequitur and Cyclitur based on the help provided to decide what parts of trace they need to analyze in detail.

In the first phase, the software engineers were presented with the generated trace and asked to answer the question "What do you think about the trace?". For the question, the responders had to choose one or more choices among the following:

• "Huge amount of data",

• "Incomprehensible data",

• "Comprehensible data". The size of the provided trace represents only around 2% of the size of one of our benchmark trace, however, 60% of the responders agreed that the trace file contains a huge amount of data. Concerning the trace comprehension, while 30% found the trace comprehensible, 55% found it incomprehensible.

In the second phase, the software engineers were presented with the compression generated using Sequitur and asked to answer the question "Does the compression help you decide which parts you want to analyze in detail?". The software engineers answered by "yes" or "no". The results show that 65% answered by no, while 35% found that the Sequitur compression helps to decide which parts to analyze in detail.

The next phase consists in evaluating Cyclitur compression. The developers were presented with the compression generated using Cyclitur and asked to answer two questions. First question was "Do you notice a specific cycle in the compression?". The developers answered "yes" or "no". By analyzing the results we observe that 60% of the software engineers found that the Cyclitur compression helps to identify which of cycles should be analyzed in detail. According to the suggestions of the software developers that answered the question by "no", the main reason behind their negative answer choice was the absence of a visualization.

The second question was "With respect to the Sequitur compression, do you think that Cyclitur compression is more helpful?". The software engineers had five options to choose from to answer the previous question, where each option being assigned a score: not helpful (assigned a score of 1), slightly helpful (score of 2), moderately helpful (assigned a score of 3), very helpful (assigned a score of 4), extremely helpful (assigned a score of 5).

We observe that 100% of software engineers found that the Cyclitur compression is more helpful in analyzing an execution trace than the Sequitur compression. In more details, 20% had found that the Cyclitur compression is extremely helpful comparing to the Sequitur compression, and 25% found it very helpful.

In order to understand how developers performed the evaluation, we asked them to answer one follow-up question, which is: "Using Cyclitur compression, what did help you decide which cycle(s) should be analyzed in detail". The cycle detection and the position of cycles in the Cyclitur compression were used up to 57% to decide which cycles the software engineers need to analyze. The number of repetitions of cycles in the compression was used 89% to decide which cycles to analyze.

VI. RELATED WORK

Compressing traces of microcontrollers with the objective of analyzing them remains a challenge. In other areas, particularly in object oriented context, there are numerous studies concerning reduction and compression of execution traces. Hamou-Lhadj and Lethbridge [START_REF] Hamou-Lhadj | Compression techniques to simplify the analysis of large execution traces[END_REF] use an acyclic oriented graph representing method calls to compress traces. A rulebased approach using method calls is proposed in [START_REF] Taniguchi | Extracting sequence diagram from execution trace of Java program[END_REF], [START_REF] Hamou-Lhadj | Effective exploration and visualization of large execution traces[END_REF], which aims to build a compression by using the construction of trees. It is possible to summarize large execution traces using finite automata like in [START_REF] Heizmann | Refinement of trace abstraction[END_REF]. In addition to their trace compression, in [START_REF] Hamou-Lhadj | Summarizing the content of large traces to facilitate the understanding of the behaviour of a software system[END_REF] Hamou-Lhadj and Lethbridge, propose the deletion of implementation and useless details to ease the analysis of execution traces. These object oriented approaches are not suitable for our purpose for multiple reasons. First, they discard the order of events, which is paramount to understand a program. Second, they use input/output data. In our context, such information is rarely available, and raises important storage problems. Third, these approaches reason about method calls. In optimized microcontroller code, function calls alone are often inadequate to understand the program, since the core logic of a program is sometimes coded in a single function.

General data compression methods have been used for program traces, for example, Gzip [START_REF] Gailly | [END_REF], or VPC4 [START_REF] Burtscher | The VPC trace-compression algorithms[END_REF]. However, such compression usually generates a result that is not understandable by the engineer. The use of these techniques may imply loss of reference points, which are cycles in our approach. We think that cycles revealed in the process of compression may assist automatic trace analysis, for example using cycle matching [START_REF] Aoe | Computer Algorithms: String Pattern Matching Strategie[END_REF].

An approach proposed by James R. Larus in [START_REF] Larus | Whole program paths[END_REF] captures the program execution using trace recording, and represents a dynamic executed control flow of a program. To compress traces, the author uses Sequitur to find inherent regularities (e.g., repeated code). The DAG representation of grammar produced by Sequitur is called Whole-Program Path (WPP). This approach is interesting; however, its main motivation is the detection of hot subpaths, which are short sequences of acyclic paths that are costly. Our work consists in compressing traces by detecting and exploiting cycles. It allows us to reach better compression ratios than Sequitur. Also, our approach keeps cycles as reference points while the WWP approach does not take cycles into account. That is why, the WWP approach is not relevant in our work context.

Similarly to the approach of James R. Larus, we rely on Sequitur, a grammar-based compression algorithm. Such algorithms are the objects of active research in information theory (cf. [START_REF] Charikar | The smallest grammar problem[END_REF] for a survey). In particular, several extensions of Sequitur aimed at obtaining better compressions by producing smaller grammars. For instance, Yang and Kiefer proposed a generalization of Sequitur to n-grams (rather than digram) [START_REF] Yang | Efficient universal lossless data compression algorithms based on a greedy sequential grammar transform-Part one: Without context models[END_REF]. This change ultimately leads to smaller grammars. However using this algorithm comes at a price: the algorithm does not share the same time and space complexity as Sequitur, and as a result, is not usable on huge program traces. On the contrary, Cyclitur keeps the same complexity as the original Sequitur algorithm.

VII. CONCLUSION AND PERSPECTIVES

In the microcontroller context, the new microprocessors ARM Cortex-Mx [START_REF] Arm | Cortex-M series[END_REF], enable recording the component behavior and save it as an execution trace file. Analyzing execution trace may help in the understanding and debugging tasks. However, even for a short execution time, the generated trace contains a huge amount of data, making the system comprehension task difficult and tedious. It is important to provide to the engineer in charge of debugging an overview of the execution trace.

In this article we propose an approach that aims to provide a compression of trace. The compression process is based on a grammar-based compression using our improvement of Sequitur [START_REF] Nevill-Manning | Identifying hierarchical structure in sequences: A linear-time algorithm[END_REF], named Cyclitur. Our approach starts by dividing a trace into cycles, where each cycle is an execution of the active main loop. The second step consists in discovering and compressing similarities inside cycles. The detection and compression of repetitions and regularities in terms of cycles is the third and last step of our approach.

Our approach is evaluated, first quantitatively to compare its compression rate to the existing Sequitur algorithm; second qualitatively to determine if such compression could be useful to software engineers. The quantitative evaluation shows that our approach generates an equivalent or better compression than Sequitur on benchmark execution traces. On microcontroller execution traces, Cyclitur compression ratios were better than Sequitur compression ratios from 15% to 25%. The quality survey points out three important facts. First, software engineers usually find that Cyclitur-generated trace compressions are easier to analyze than their Sequiturgenerated counterparts. Second, Cyclitur may help in identifying and locating important details in an execution trace. Third, our survey highlights the need of a graphical visualization for software engineers to analyze such a trace compression.

As a future work we intend to facilitate the understanding of the compression through visualization. We also intend to help in diagnostic by adapting dynamic validation and data mining techniques [START_REF] Fayyad | From data mining to knowledge discovery in databases[END_REF], for compressed traces, to help in fault localization.

4 append ω i to body of rule of S 5 while

 45 ¬ Uniqueness(G) ∨ ¬ Utility(G) do 6 if ¬ Uniqueness(G) then 7 let δ be repeated digram in G 8 if ∃ A, α ∈ ∆ : α = δ then 9 replace the other occurrence of δ in G with A else form new rule D, δ where D / ∈ (Σ ∪ Γ)

1 )

 1 Digram uniqueness: It states that a grammar should not contain two non-overlapping occurrences of the same digram in the grammar body. Property 1 (Digram uniqueness). The digram uniqueness property holds for G, noted Uniqueness(G), if for all terminals A, B ∈ Γ, symbols a, b, c, d ∈ Σ ∪ Γ, and strings α, β, γ, δ ∈ (Σ ∪ Γ) * , the two following statements hold:

  then ab is not equal to cd. Sequitur ensures Property 1 as follows. If adding a symbol (line 4) produces a non-overlapping repetition of a digram in the grammar body, then the property does not hold anymore (line 6). Sequitur restores the property either by creating a new rule or by reusing an existing rule (lines 7-15). If the repeated digram corresponds already to the body of an existing rule, Sequitur replaces this digram with the corresponding nonterminal (line 9), which represents the concerned rule. Otherwise, it forms a new rule with the digram as body and a new nonterminal as head, and replaces both occurrences of the digram with this new nonterminal symbol (lines 11-14).

5 while 8 replace every occurrence of a n a m in G with a n+m 9 else 13 else 14 form 16 ∆ 17 Γ 22 ∆ ← ∆ { A, α } 23 ΓFig. 2 .

 5891314161722232 Fig. 2. Function ReSequitur(Σ, ω, Γ 0 , ∆ 0 )

Fig. 4 .

 4 Fig. 4. Compared average compression ratios for each program

  a particular nonterminal,

	Listing 1. Example of C embedded application code
	int main(void){
	while(1){
	static JOY_State_TypeDef JoyState = JOY_NONE;
	static TS_STATE * TS_State;
	JoyState = IOE_JoyStickGetState();
	switch (JoyState) {
	case JOY_NONE:
	LCD_DisplayStringLine(Line5, "JOY: ----");
	break;
	case JOY_UP:
	LCD_DisplayStringLine(Line5, "JOY: UP ");
	break;
	case JOY_DOWN:
	LCD_DisplayStringLine(Line5, "JOY: DOWN ");
	break;
	case JOY_LEFT:
	LCD_DisplayStringLine(Line5, "JOY: LEFT ");
	break;
	case JOY_RIGHT:
	LCD_DisplayStringLine(Line5, "JOY: RIGHT ");
	break;
	case JOY_CENTER:
	LCD_DisplayStringLine(Line5, "JOY: CENTER ");
	break;
	default:
	LCD_DisplayStringLine(Line5, "JOY: ERROR ");
	break;
	}
	TS_State = IOE_TS_GetState();
	Delay(1);
	if (STM_EVAL_PBGetState(Button_KEY) == 0) {
	STM_EVAL_LEDToggle(LED1);
	LCD_DisplayStringLine(Line4, "Pol: KEY Pressed ");
	}
	if (STM_EVAL_PBGetState(Button_TAMPER) == 0) {
	STM_EVAL_LEDToggle(LED2);
	LCD_DisplayStringLine(Line4, "Pol: TAMPER Pressed ");
	}
	if (STM_EVAL_PBGetState(Button_WAKEUP) != 0) {
	STM_EVAL_LEDToggle(LED3);
	LCD_DisplayStringLine(Line4, "Pol: WAKEUP Pressed ");
	}
	}
	}

In the original version of Sequitur, such a parameter does not exist. We present a parameterized form of Sequitur as it will be used by our extension in the next section.

Available online at http://io32.forge.imag.fr/formulaire/Trace.txt

Available online at http://io32.forge.imag.fr/formulaire/Sequitur.txt

Available online at http://io32.forge.imag.fr/formulaire/Cyclitur.txt

ACKNOWLEDGMENT

This work has been funded by the French-government Single Inter-Ministry Fund (FUI) through the IO32 project (Instrumentation and Tools for 32-bit Microcontrollers). The authors would like to thank STMicroelectronics, AIM and ESAii IC for their help.


Frédéric Prost
email: frederic.prost@imag.fr

Lydie Terras
email: lydie.terras@imag.fr

Privacy and Nomadic Computing A Public-Key Cryptosystem Based on Passwords

Keywords: Password, Public-key cryptography, Secure hashing functions, RSA, PGP

The use of public-key cryptography is complicated in a nomadic computing era. Private keys are typically huge numbers that are impossible to memorize or even to write down and have to be stored electronically. Therefore a mobile user has somehow to keep its private key with him at all time (it is senseless to imagine that the private key is dowloaded through a public network). It is neither realistic nor safe. Indeed the mobile device must be protected, which is usually done through password mechanisms. At the end of the day all the cryptosystem relies on this password. In this paper we propose a generic way to produce keys from a password using secure hashing functions. We have done an implementation of a nomadic PGP as a proof of concept: the software is a java applet, thus platform independent, providing a complete solution for mail encryption based on public-key cryptography. In the end the user just has to remember its password, and no longer has to rely on specific software/operating system/hardware settings.

INTRODUCTION

Key management is a central concern in cryptosystems. Indeed, at the very core of any cryptosystem used for communication (when it is used to safely store information it is different) lies this paradox: the receiver should be able to decrypt the message, but can only do so with the appropriate key. Moreover this key has to remain secret and is linked to the key used to encrypt the message. Hence the question: if one is able to communicate safely encryption/decryption keys why does he need a cryptosystem in the first place? Instead of safely communicating the key it would be enough to safely transmit the message. Asymetric cryptography, like RSA [START_REF] Rivest | A method for obtaining digital signatures and public-key cryptosystems[END_REF] or ElGamal [START_REF] Elgamal | A public-key cryptosystem and a signature scheme based on discrete logarithm[END_REF], partially solves this paradox: the key used to encrypt data is public while the key used to decrypt remains private; moreover the relation between the keys is such that it is very hard (from a computational point of view) to compute the private key having only the knowledge of the public key (although it is easy if you have the suitable hints that remain private). The problem with such cryptosystems is that private keys are typically very big integers, typically fo a few thousand bits length, and are therefore impossible to remember or even (although it is not a good security policy) to write down in a scrapbook.

In our era of nomadic life and because of the multiplicity of means used to connect to the internet, the issue of how to carry your private key with you remains. Historically it was stored in one's personnal computer which was physically secured, under lock and key, at home or at the office. Nowadays people use more and more different ways and tools for internet and mail access: from smartphones to workstations through access with netbooks and random computers (think internet cafes, public computers in airport etc.).

In order to tackle with this problem we propose a system that produces keys from passwords. The raw idea is to have a deterministic, although non invertible, algorithm that relies on secure hashing functions. The result of the secure hashing function is used as a pseudo-random sieve to produce the keys. The system is implemented as a java applet and is platform independent: one just needs a browser, and also needs to remember its password, to generate and use a public key cryptosystem and no longer has to store its private keys.

We start in section 2 by a brief discussion of the security aspects related to this idea. In section 3 we present a method to generate keys for the RSA cryptosystem. We present a proof of concept in the form of a software that is a PGP-like software in which symetric and asymetric encryption are used together, called Nomadic PGP in section 4. The basic blocks of Nomadic PGP are the hashing function Whrilpool, RSA for the asymetric encryption and twofish for the symetric encryption. Finally we conclude in section 5.

SECURITY DISCUSSION

As B. Schneier strengthens it again and again in [START_REF] Schneier | Beyond Fear. Thnking Sensibly about Security in an Uncertain World[END_REF] all security problems/solutions are trade-offs. In essence we propose the use of a public key cryptosystem, in which the user may choose an arbitrary large security parameter, in a way that is completely determined by a password (and the length of the key to produce). Clearly since the aim of our system is to be able to keep the password in memory the key space is much smaller (if the password had the same length as the private key we would have gain nothing) than what it could theoretically be. By construction only a limited fraction of keys (regardless of the way keys are produced)can be explored by an implementation following our idea. The natural question is: how the restriction to passwords interfere with the strength of the original cryptosystem ? In other words what have we lost for the benefit of being able to remember a very large (the size of the generated key is unnbounded) private key ?

In order to fix ideas suppose that we are generating RSA keys of size 2048 bits (the size of the modulus) from passwords using a hashing function f . The raw idea is to produce enough blocks from the password in order to produce two primes of size 1024 by applying f to the password (with deterministic modifications of the password for each new block) and to multiply those two primes together (the detailed process is given in section 3).

The factorization of a 2048 bits integer is today out of reach: as of today the largest number factorised was RSA-768 of length 768 bits see [START_REF] Kleinjung | Factorization of a 768-bit rsa modulus[END_REF]. So the easiest way to break the system is to recover the password using either a brute force attack, or some weakness of the hashing function f . If we rely on the assumption that f is a dependable secure hashing function (our system is completly parameterized by the hashing function used so it is a fair assumption) there only remains the question of the brute force attack. At this point we can note that the attack is more complicated than just computing a hash and comparing it to some stored value. Indeed the public value is computed from many hashes and is not instantaneous. We refer the reader to section 4 for practical results. Another important point to note is that numbers generated this way are pseudo-random, and uniformally distributed among numbers that are the product of two primes otherwise the security assumption on f would be wrong. In the last analysis the strengh of the system is the same as the strength of a secure symetric encryption algorithm using the password as an encryption key regardless of the size of the key generated.

From a more general point of view it seems that we loose nothing by limiting the strength of the cryptosystem to the strength of passwords. Indeed in every day life, even if the cryptosystem used is RSA with huge keys of length 4096 bits, then the easiest way to break the cryptosystem is not to try to factorize this number but to steal the private key that is stored on a computer or on some device. Even if the private key is encrypted it all boils down to find a password or two (one for login and the other one to decrypt the encrypted private key) to recover it in the vast majority of the cases.

RSA KEY GENERATIONS USING SECURE HASH FUNCTIONS

In our proof of concept we have used the Whirlpool hashing function, see [START_REF] Barreto | The whirlpool hashing function[END_REF] for its formal definition, in order to generate a RSA key pair (public and private). In a nutshell (we refer to [START_REF] Rivest | A method for obtaining digital signatures and public-key cryptosystems[END_REF] for the complete definition of the RSA cryptosystem) we need to produce to prime numbers p, q. Then let n = pq and φ(n) = (p -1)(q -1). We need to choose e such that φ(n) and e are coprime and we have to compute d the multiplicative inverse of e modulo n. The public key is the pair e, n and the secret key is the pair d, n. In practice e is first chosen as the 5 th Fermat number (if it doesn't work we deterministically chose the closest number coprime with n starting from it).

Whirlpool is a secure hashing function of the Miyaguchi-Preneel family and is based on AES (Daemen and Rijmen, 1999). Whirlpool produces a digest of size 512 bits for any message of lenght less than 2 256 bits. The idea is to use the password digest as a sieve to look for a prime number: if the digest is a prime number it is ok otherwise we add 2 to the digest (if it is an odd digest of course) until we find the next prime number.

The first limitation that we have to overcome is the fixed length of the digest which is 512 bits. In order to look for bigger prime numbers in a deterministic way we are going to produce as many 512 bits blocks as necessary by applying repeatedly Whirlpool to the password. Since we do not want to repeat the same block again and again we add the last bit of the previous to the password to compute the next block. We call this alogrithm WhirlpoolNBits. It is schematically presented on figure 1.

Since the RSA keys needs two prime numbers the process has to be repeated in order to create a second prime number. One choice is to concatenate the password with itself as a 'second password' sent to WhirlpoolNbits. This method can be used as often as necessary if more pseudo-random numbers are needed regarding the cryptosystem considered.

NOMADIC PGP

An applet based on this approach has been designed and implemented as a proof of concept. It is a nomadic version of PGP [START_REF] Zimmermann | The Official PGP User's Guide[END_REF] and can be used for mail encryption, decryption and authentication. It relies on RSA for the asymetric encryption and twofish, see [START_REF] Schneier | The Twofish Encryption Algorithm: A 128-Bit Block Cipher[END_REF], for the symetric encryption. The idea of P. Zimermmann is to combine the best of both worlds: the asymetric encryption is used to encrypt a session key and the symetric encryption (much faster) use this session key to encrypt the message. Moreover, as in PGP, there is a signature mechanism for Nomadic PGP.

The nomadic PGP applet

The nomadic PGP applet provides three services:

• Key generation: a public key is generated from a password and a desired key lenght.

• Encryption of messages: with a message and a public key as input the applet produces an encrypted message that can be copy/paste as the mail to be sent. If the sender desires to sign its message he also has to give its password as input.

• Decryption of messages: The message to be decrypted and the password are given as input. If an authenticity check is need one also has to input the public key of the sender. The decrypted message together with the result of the authenticity check are displayed.

The Nomadic PGP can be downloaded from http://membres-lig.imag.fr/prost/NPGP/.

A typicaly use/case scenario is the following. Suppose that Alice wants to send an e-mail to Bob. Bob enters his password to generate a public key that he publishes on his website. Alice copies this public key and enters it with her password and the message she wants to encrypt in the application. It returns her the encrypted message. Alice copies and pastes the result on a e-mail client and sends it to Bob. Bob receives the e-mail, he copies and pastes the encrypted message in the application and enters also his password then it returns him the decrypted message (he can also gives the public key of Alice to check a signed message).

We briefly explain how each service of the applet is implemented in the following sections.

Encryption

The input for the encryption process consists in a public key, a message and a password. The first step is to generate the secret key as discussed in section 3. Then, a session key is generated as follows: the concatenation of the password, the message and a timestamp are hashed into a 256 bit digest using Whirlpool. This digest is the session key that is going to be used by twofish to encrypt the message. The output consists of three parts. The first part is the encryption by RSA of the session key with the public key that was given as input. The second part is the encryption by RSA of the pad size: since twofish is 128 bits block cypher it can be necessary to pad the original message with useless 0's, the pad size will allow the removal of this extra 0's after decryption. And finally the third part is the message encrypted with twofish and the session key. Note that because of the timestamp the session key is always different even for two mails with the same content.

The encryption process is schematically given in figure 2.

Decryption

The input for the decryption process consists in the password with a Nomadic PGP encrypted message. The firt step is to generate the private key associated with the password. This private key is used to decrpyt the first and second parts of the message to recover the session key and the pad size. The session key is given and the third part of the message are given as input to twofish, and the result of twofish is stripped off the unnecessary 0's thanks to the pad size.

The decryption process is given in figure 3.

Digital signature with nomadic PGP

Nomadic PGP includes a simple digital signature mechanism. During the encryption the user has to provide its password in order to generate its private key. Then a digest of the message is computed using Whirlpool and this digest is encrypted with RSA and the private key of the sender. The encrypted digest is appended to the message to be sent. On the receiving end, the message, the password of the recipient and the public key of the sender are needed. The decryption is performed as described in section 4.3. The public key of the sender is used to decrypt the last part of the message which is compare to the digest of the decrypted message. If it matches then the signature is valid.

The signature scenario is schematically depicted in figure 4.

CONCLUSION

We have proposed and implemented a nomadic PGP including a basic signature scheme. Instead of having to deal with a private key management (where to store the private key, how to protect it etc.), the user has only to remember a password in order to gener-ate its private key and to cypher/decypher messages. Moreover, the key generation as well as the cryptographic system are implemented as a java applet. Thus Nomadic PGP is platform independant and can be used anywhere without requiring specific software environment. This provides a fully nomadic cryptographic solution.

From a security point of view it appears that the reduction of the strength of cryptographic systems to the strength of a, humanly memorizable, password is realistic. Indeed most platforms, especially mail servers, cloud services and so on are protected by password mechanisms and if a more complicated key is need it is most probably going to be stored in a place protected by a password. We think that the development of frameworks allowing detemernistic and non reversible generation of complicated keys (especially in the case of public cryptography and its uses for communication and certification) is the path to fol-

Figure

  Figure 1: WhirlpoolNBits algorithm

Figure 3 :

 3 Figure 3: Decryption process