Moez Krichen
email: moez.krichen@redcad.org

Roobaea Alroobaea

A New Model-Based Framework for Testing Security of IOT Systems in Smart Cities Using Attack Trees and Price Timed Automata

Keywords: Model-Based, Testing, Security, Internet of Things, IoT, Smart Cities, Attack Tree, Price Timed Automaton, UPPAALL, TTCN-3, Cloud

In this paper we propose a new model-based framework for testing security properties of Internet of Things in Smart Cities. In general a model-based approach consists in extracting test cases from a formal specification either of the system under test or the environment of the considered system in an automatic fashion. Our framework is mainly built on the use of two formalisms namely Attack Trees and Price Timed Automata. An attack tree allows to describe the strategy adopted by the malicious party which intends to violate the security of the considered IOT system. An attack tree is translated into a network of price timed automata. The product of the constructed price timed automata is then computed using the well known UPPAALL platform. The obtained timed automata product serves as input for the adopted test generation algorithm. Moreover our framework takes advantage of the use of the standardized specification and execution testing language TTCN-3. With this respect, the obtained abstract tests are translated into the TTCN-3 format. Finally we propose a cloud-oriented architecture in order to ensure test execution and to collect the generated verdicts.

Introduction

Nowadays Internet of Things (IoT) is playing an important role in our modern society as a technology which allows to connect everyday objects to Internet. These objects are equipped with sophisticated interfaces which give them the capabilities to measure physical aspects from the environment and to interact with other entities by exchanging specific messages.

This new technology has provided a wide generation of valuable and innovative services. In this manner, modern cities are becoming smarter by adopting intelligent systems for water management, traffic control, energy management, street lighting, public transport, etc. However, these services can massively be attacked and compromised by several malicious parties whenever adequate and appropriate security measures are absent.

A few years ago, the smart devices that make up the Internet of Things, such as light bulbs, thermostats, webcams, and many others , were seen as potential targets for attackers to activate or disable remote devices and to harm consumers. Today, the IoT no longer represents a mere target, but a real plat-form which may be used by attackers to launch dangerous remote aggressions and to cause very serious incidents.

With the emergence of wide-ranging Open Source worms, such as Mirai [START_REF] Antonakakis | Understanding the mirai botnet[END_REF], capable of spreading to tens of millions of IoT devices, attackers can exploit these systems to generate a massive influx of traffic and disconnect any company or institution from Internet. Beyond the massive attack of the network, these IoT attack platforms can present other forms of threats, such as information theft and passwords decryption.

The attacks on industrial control systems have taken a disturbing turn. Cyber criminals attack the operational core of vital infrastructures taking advantage of their vulnerability. Recent attacks have not only disrupted the provision of essential services, such as electricity, but have also damaged automation systems to return to normal operation.

For instance the 2015 and 2016 attacks in Ukraine [START_REF] Boyte | A comparative analysis of the cyberattacks against estonia, the united states, and ukraine: Exemplifying the evolution of internetsupported warfare[END_REF] that caused power outages were perfectly planned and coordinated. The attackers managed to hijack the automation systems to cause power outages and then perform a well-ordered succession of destructive payloads on workstations, servers, and embedded devices.

In the future, it will be more difficult to recover from breakdowns caused by attacks, and interruptions may be measured in days instead of hours. Events of this type force providers in charge of these infrastructures to think about how to act in the event of an attack.

In this context our goal in this work is to propose a new framework for testing security aspects for IoT systems deployed in smart cities in order to avoid such anomalies or at least to minimize them as much as possible. Our framework is model-based (Krichen et al., 2018a) in the sense that it is based on the use of a formal approach which consists is generating test cases from a given model.

In our case, the considered model corresponds to the behavior of the attacker aiming to violate the system under investigation. First the behavior of the attacker is given as an attack-tree [START_REF] Kordy | Dag-based attack and defense modeling: Dont miss the forest for the attack trees[END_REF]. The latter is a formalism used to describe the strategy adopted by the attacker to achieve its goal.

In a second step the proposed tree is translated into an equivalent network of price timed automaton [START_REF] Behrmann | Priced timed automata: Algorithms and applications[END_REF] which is a graphical representation which is used to model timed behaviors. The obtained network of price timed automaton serves as an input for the test generation algorithm.

The generated abstract test cases are then translated into the specification and execution standard testing language TTCN-3 (Lahami et al., 2012a). Finally a cloud-oriented test architecture [START_REF] Tilley | Software Testing in the Cloud: Perspectives on an Emerging Discipline[END_REF] is proposed to run the obtained TTCN-3 concrete tests and to collect the generated verdicts.

The rest of this paper is organized as follows. Section 2 introduces the notion of attack trees. Section 3 defines the model of price timed automata. Section 4 illustrates how attack trees are translated into networks of price timed automata. Section 5 presents an overview about the test generation and execution phases. Section 6 reports on related research works dealing with IoT security testing. Finally Section 7 summarizes the main contributions of the paper and gives some possible directions for future work.

Attack Trees

Attack trees (AT) [START_REF] Kordy | Dag-based attack and defense modeling: Dont miss the forest for the attack trees[END_REF] correspond to a useful graphical formalism to study the security of critical systems. More precisely an attack tree can be seen as a graphical representation of the attacker strategy represented in the form of a tree.

The root of an AT corresponds to the goal the attacker aims to fulfill. The children of a node in the AT are refinements of the goal of the corresponding parent node into sub-goals.

The refinement of an internal node of an AT can be either conjunctive or disjunctive:

• A conjunctive refinement is used when the fulfilment of all the childrens goals is needed to fulfill the parent's goal. In this case we associate an AND-Gate with considered parent node (See Figure 1-(a)).

• A disjunctive refinement is used when the fulfilment of one of the childrens goals is enough to fulfill the parent's goal. In this second case an OR-gate is associated with the considered node (See Figure 1-(b)). We consider a finite set of attribute variables Attribs = {Att 1 , • • • , Att n }. These attributes are used to describe the characteristics of the attacker like available resources for instance. We denote by Vals ⊆ (R ≥0 ) n the set of valuations of the attributes.

The leaves of the AT correspond to the elementary actions the attacker has to execute. They are called basic attack steps (BAS). Each BAS is equipped with an additional attribute Time (which measures the time since the basic attack step started) and two preconditions:

Ready2Start : Vals → {0, 1}
which indicates that the BAS can be started or not (i.e., has enough resources to start for example); and

Able2Succeed : Vals → {0, 1}
which indicates whether the BAS can succeed or not. These preconditions are Boolean combinations of linear equations over Attributes. Moreover each BAS has an update function:

Modi f y : Vals × R ≥0 → Vals
which updates the attribute values when time elapses. At this level we assume that time dependence is linear between the attributes {Att 1 , • • • , Att n } and the special attribute Time.

Let PrePost(Attribs) be the set of all possible triples (Ready2Start, Able2Succeed, Modi f y) defined with respect to Attribs. We also define an Attacker Initializer which gives the initial valuation of the attributes. It is defined as:

Init : {Att 1 , • • • , Att n } → R ≥ 0.
The set of attack tree gate types is defined as:

Gates = {AND, OR}.
An attack tree A is formally defined as a tuple Nds,Chld, Rt, Attribs, Init, Ftrs where:

• Nds is a finite set of attacker nodes;

• Chld : Nds → Nds * associates a set of children to each parent node;

• Rt corresponds to the root of the AT A which defines the global goal of the attacker;

• Attribs corresponds to the set of attributes of the AT A;

• Init corresponds to the attacker initializer;

• Ftrs : Nds → Gates ∪ PrePost(Attribs) associates an AND/OR Gate with each internal node and a tuple (Ready2Start, Able2Succeed, Modi f y) with each leaf of the AT.

An example of an AT is given in Figure 2. This AT is inspired from the work of [START_REF] Kumar | Quantitative attack tree analysis via priced timed automata[END_REF]. The goal of the attacker here is to crack the password of a protected file. As indicated by the figure the global goal of the attacker can be achieved by:

• Either cracking the password: this sub-goal can in turn be achieved using one of three possible choices (namely: Dictionary, Guessing or Brute Force attacks).

• Or performing a password attack: this sub-goal can be either achieved by a Social Engineering or a Key Logger attacks. The Social Engineering attack is in turn decomposed into two BASs namely: Generic Reconnaissance and Trap Execution. Similarly the Key logger attack is achieved within two BAS: Key Logger Installation and Password Intercept. More details about this example can be found in the previously mentioned article [START_REF] Kumar | Quantitative attack tree analysis via priced timed automata[END_REF].

Priced Timed Automata

The model of Priced timed automata (PTA) [START_REF] Behrmann | Priced timed automata: Algorithms and applications[END_REF] is an extension of timed automata, obtained by assigning costs to actions and locations. Next, we will denote by Ψ(Y ) the set of all possible Boolean predicates over a set Y of continuous variables.

A priced timed automaton P is defined as a tuple Loc, loc 0 ,Cl, Act, Edg, Inv,Cost where:

• Loc is a finite set of states;

• loc 0 ∈ L is the initial state;

• Cl is a finite set of clocks;

• Act is finite a set of labels;

• Edg ⊆ Loc × Ψ(Cl) × Act × 2 Cl × Loc gives the set of transitions;
• Inv : Loc → Ψ(Cl) assigns invariants to locations;

• Cost : Loc ∪ Edg → N n ≥0 .
assigns cost rates to states and costs to edges.

An edge loc, ψ, act, λ, loc ∈ Edg defines a transition from location loc to location loc taking an action act. This edge can only be traversed when the constraint ψ over Cl is true, and the set λ ⊆ Cl identifies the subset of clocks which must be reset after the execution of the transition.

A trace of P = Loc, loc 0 ,Cl, Act, Edg, Inv,Cost is a sequence of locations and transitions T R = loc 0

act 0 --→ λ 0 t 0 c 0 loc 1 act 1 --→ λ 1 t 1 c 1 loc 2 • • • where:
• For every i, there is a transition T i = (loc i , ψ i , act i , λ i , loc i+1 ) ∈ E;

• For every i, c i = C(T i ) + t i • C(l i ) is the cost incurred in the transition;

• The initial valuation V 0 = -→ 0 which assigns 0 to every clock in Cl;

• After each transition, there is a new clock valuation V i+1 = (V i +t i )[λ i = 0] obtained by increasing every clock in X i by t i and re-initializing all clocks in λ i to 0;

• Each valuation V i + t for t < t i must satisfy the invariant Inv(l i );

• The valuation V i + t i must satisfy ψ i for every i.

Let be the parallel product operator over price timed automata. That is given a set of PTAs {P 1 , P 2 , • • • P n }, P 1 P 2 • • • P n will denote the corresponding parallel product obtained by synchronizing the transitions of the component PTAs via joint signals. The formal definition of this operator is given in [START_REF] Bengtsson | Timed Automata: Semantics, Algorithms and Tools[END_REF]. [START_REF] Kumar | Quantitative attack tree analysis via priced timed automata[END_REF].

From Attack Trees to Price Timed Automata

In this section we explain how an attack tree is transformed into a network of price timed automata. The proposed transformation is borrowed from the work of [START_REF] Kumar | Quantitative attack tree analysis via priced timed automata[END_REF]. First in Figure 3 we draw the price timed automaton corresponding to a basic attack step. The proposed PTA has five nodes. The considered BAS is activated when the input-signal activate BAS? is received from the corresponding parent-node PTA. In order to execute this input-signal the condition Ready2Start(Val) == 1 must hold.

The clock variable Time is reset to zero as soon as the BAS is activated. The attributes of the attacker are updated through the transition labeled with Val := Mo f i f y(Val, Time). At the end of the execution of the BAS the PTA reaches either state Succeeded BAS or Failed BAS. In order to reach the state Succeeded BAS the condition Able2Succeed(Val) == 1 must hold.

In Figure 4, we propose a PTA which corresponds to a parent node connected to two children via an AND gate. This PTA is activated after receiving the input-signal activate Prt?. After that an activation output-signal is sent to each child PTA. If a success signal is received from both children then the parent PTA moves to its success state.

Similarly Figure 5 is an illustration of the PTA corresponding to a parent node connected to two children via an OR gate. In this case receiving a success Finally Figure 6 gives a PTA which corresponds to the execution of the global goal of the attacker. The output signal activate Root! will be the first action to be executed by the network of obtained PTAs.

Test Generation and Execution

Test generation consists in extracting abstract test cases from the obtained network of PTAs. For this purpose we may use UPPAAL CORA [START_REF] Behrmann | Priced timed automata: Algorithms and applications[END_REF][START_REF] Rasmussen | Resource-optimal scheduling using priced timed automata[END_REF] which is an extension of the platform UPPAAL. This extension is enriched with additional variables used for optimal reachability analysis.

As already mentioned the proposed framework in this work is based on the TTCN-3 standard (ETSI, 2015). For this purpose, we will take advantage from the work of [START_REF] Lahami | Safe and Efficient Runtime Testing Framework Applied in Dynamic and Distributed Systems[END_REF]Lahami et al., 2012a). Next we give a brief recall about the main constituents of the TTCN-3 reference architecture as illustrated in Figure 7:

• Test Management (TM): manages the whole test process by starting and stopping tests;

• Test Logging (TL): manages all log events;

• TTCN-3 Executable (TE): runs the compiled TTCN-3 code;

• Component Handling (CH): places parallel test components and guarantees communication between them;

• Coding and Decoding (CD): encodes and decodes received from and sent to the TE;

• System Adapter (SA): adjusts the communication with the application or system under test;

• Platform Adapter (PA): implements the set of external functions. At this level we are interested in defining a set of rules for transforming abstract test cases into concrete TTCN-3 tests.

The adopted transformation algorithm may be inspired by the following works (Axel [START_REF] Rennoch | TTCN-3 Quick Reference Card[END_REF][START_REF] Hochberger | Informatik 2006 -Informatik für Menschen[END_REF][START_REF] Ebner | TTCN-3 Test Case Generation from Message Sequence Charts[END_REF]. Table 1 gives some examples of Cloud computing can be used in the field of software testing to deal with the problem of lack of resources and the considerable cost of building a distributed test solution during the testing activity. Consequently, the notion of Cloud testing is increasingly emerging in order to offer cost-effective and efficient testing facilities. As defined by [START_REF] Gao | Cloud testing-issues, challenges, needs and practice[END_REF], it corresponds to testing activities (namely test case generation, test case execution and test result evaluation) on a cloud-oriented environment.

The proposed cloud testing architecture is built based on TaaS (Testing as a Service) concepts. Figure 8 outlines an overview of its different components of this architecture.

• Test management GUI: offers a GUI (Graphical User Interface) charged with manages the whole testing process.

Related Work

Authors of [START_REF] Felderer | Model-based security testing: A taxonomy and systematic classification[END_REF] proposed an interesting survey on dozens of articles related to model-based security testing chosen from the most relevant digital sources and classified with respect to specific criteria. However this review did not cover any work dealing security issues for IoT and smart cities. In the opposite way, the authors of [START_REF] Ahmad | Model-based testing as a service for iot platforms[END_REF] presented a model-based approach to test IoT systems but they did not consider security aspects in anyway. Moreover the authors of [START_REF] Wang | Formal analysis of security properties of cyber-physical system based on timed automata[END_REF] proposed a formal framework based on timed automata for analyzing security properties of cyberphysical systems. In (Krichen et al., 2018a), the authors proposed a preliminary work which introduced a model based approach for testing security aspects of IoT systems in smart cities. Regarding the use of attack trees we mention the following works [START_REF] Aslanyan | Quantitative verification and synthesis of attackdefence scenarios[END_REF] [START_REF] Kammüller | Attack tree analysis for insider threats on the iot using isabelle[END_REF] [START_REF] Kumar | Quantitative attack tree analysis via priced timed automata[END_REF] [START_REF] Kordy | Dag-based attack and defense modeling: Dont miss the forest for the attack trees[END_REF] which adopted this formalism to model and analyse security attacks. However none of these works has attempted to use testing techniques to check the ability of the considered systems to defend themselves against security attacks.

Conclusion

In this work we proposed a new approach for testing security aspects for IoT systems in Smart Cities. The proposed approach is based on the use of attack trees which correspond to a graphical representation of the strategy adopted by an attacker in order to violate the IoT system. We proposed a transformation method to translate a given attack tree into a network of price timed automata. The latter is then used as input for the test generation algorithm for producing abstract test cases. The obtained test cases are translated into concrete TTCN-3 test scenarios. Finally a cloud oriented testing architecture is proposed in order to execute tests and collect testing results.

Many extensions are possible for this work. First we may take advantage from the work of [START_REF] Lahami | Safe and Efficient Runtime Testing Framework Applied in Dynamic and Distributed Systems[END_REF][START_REF] Krichen | A formal framework for blackbox conformance testing of distributed real-time systems[END_REF][START_REF] Lahami | Using knapsack problem model to design a resource aware test architecture for adaptable and distributed systems[END_REF][START_REF] Krichen | Interesting properties of the real-time conformance relation[END_REF] to build a decentralized testing architecture. Moreover we may adopt the methodology proposed in [START_REF] Krichen | A model-based approach to combine conformance and load tests: an ehealth case study[END_REF][START_REF] Maâlej | A model based approach to combine load and functional tests for service oriented architectures[END_REF][START_REF] Maâlej | Automated significant load testing for WS-BPEL compositions[END_REF][START_REF] Maâlej | Model-based conformance testing of WS-BPEL compositions[END_REF]Maâlej et al., 2012a) to combine security and load tests for IoT applications. Finally we may exploit the same techniques presented in [START_REF] Bensalem | A simplified approach for testing real-time systems based on action refinement[END_REF] in order to refine abstract test cases before translating them into TTCN-3.

Figure 1 :

 1 Figure 1: Different possible gates of an attack tree.

Figure 2 :

 2 Figure 2: An example of an attacker tree inspired by the work of[START_REF] Kumar | Quantitative attack tree analysis via priced timed automata[END_REF].

Figure 3 :

 3 Figure 3: A priced timed automaton for a basic attack step.

Figure 4 :

 4 Figure 4: A priced timed automaton for an AND gate and a parent node having two children.

Figure 5 :

 5 Figure 5: A priced timed automaton for an OR gate and a parent node having two children.

Figure 6 :

 6 Figure 6: Priced timed automaton corresponding to the global goal of the attacker.

Figure 7 :

 7 Figure 7: TTCN-3 Architecture (Lahami et al., 2016).

  the rules to use to derive TTCN-3 tests from abstract test cases. These rules are concisely explained below: • R1: This rule generates a new TTCN-3 module for each abstract test suite; • R2: This rule transforms each test sequence into a TTCN-3 test case; • R3: This rule associates a TTCN-3 timer with each abstract timed behavior; • R4: This rule transforms each test sequence into a TTCN-3 function; • R5: This rule transforms the abstract channels into TTCN-3 templates.

Table 1 :

 1

	R#	Abstract Concepts TTCN-3 Concepts
	R1	Test Suite	TTCN-3 Module
	R2	Single Trace	TTCN-3 Test Case
	R3	Timed Behavior	TTCN-3 Timer
	R4	Test Sequence	TTCN-3 Function
	R5	Channel	TTCN-3 Template

It is worth noting that the two previous cases can be easily extended to the situation where a parent node has more than two children.


Moez Krichen
email: moez.krichen@redcad.org

Roobaea Alroobaea

Mariam Lahami
email: mariam.lahami@redcad.org

Towards a Runtime Standard-Based Testing Framework for Dynamic Distributed Information Systems

Keywords: Distributed, Information Systems, Runtime, Dynamic, Adaptable, TTCN-3, Testing, Isolation, Generation, Minimization, Classification

In this work, we are interested in testing dynamic distributed information systems. That is we consider a decentralized information system which can evolve over time. For this purpose we propose a runtime standard-based test execution platform. The latter is built upon the normalized TTCN-3 specification and implementation testing language. The proposed platform ensures execution of tests cases at runtime. Moreover it considers both structural and behavioral adaptations of the system under test. In addition, it is equipped with a test isolation layer that minimizes the risk of interference between business and testing processes. The platform also generates a minimal subset of test scenarios to execute after each adaptation. Finally, it proposes an optimal strategy to place the TTCN-3 test components among the system execution nodes.

INTRODUCTION

Nowadays, information systems are steadily gaining importance as a major ingredient for a wide range of modern technologies and computerized services. More precisely we are interested in distributed information systems [START_REF] Grusho | Information security architecture synthesis in distributed information computation systems[END_REF][START_REF] Yesikov | Multi-agent approach for distributed information systems reliability prediction[END_REF] which correspond to decentralized systems made of sets of physical devices and software components. Moreover we pay a particular attention to dynamic distributed information systems which are systems that can evolve during execution time.

The possible changes the considered system may encounter could be either structural or behavioral. On the first hand, structural changes correspond to the addition or deletion of physical nodes or links between nodes. On the other hand, behavioral changes correspond to the addition, deletion or update of the software components installed on the physical nodes of the system.

It is worth noting that these two types of changes may happen while the system is running. Consequently this may lead to the apparition of new risks, bugs and problems for the considered distributed information system either locally (on some limited parts of the system) or globally (on the whole behavior of the system).

In both cases this is considered as a dangerous and critical situation. Thus very urgent and efficient measures must be taken in order to guarantee the correctness and the safety of the distributed information system we are dealing with.

To remedy this, we adopt in this work an online testing approach which can be applied at runtime. For that, we propose a standard-based testing platform for dynamic distributed information systems. The proposed platform uses the TTCN3 standard and takes into account both structural and behavioral adaptations. Moreover, it is equipped with a test isolation layer which minimizes the risk of interference between testing and business processes. We also compute a minimal subset of test cases to run and efficiently distribute them among the execution nodes.

The remainder of this paper is organized as follows. Section 2 is dedicated for Runtime Testing for Structural Adaptations. In Section 3, we propose techniques for Runtime Testing of Behavioral Adaptations. Finally, Section 4 summarizes the main contributions presented in this paper and states some directions for future work.

The process depicted in Figure 1 shows the different steps to fulfill in order to execute runtime tests when structural reconfiguration actions happen: • Dependency Analysis: This step focuses on determining the affected components of the system under test by a structural reconfiguration action.

• Test Case Selection: This step allows to identify the set of test cases to choose from the Test Case Repository and which will be applied on the set of components identified during the previous step.

• Test Component Placement: This step allows to distribute test components over the execution nodes while taking into account specific constraints.

• Test Isolation and Execution: This step allows to take into account isolation aspects and to execute the test cases selected during step 2.

More details about these different steps are given in the next sections.

Dependency Analysis

Our goal here is to reduce the cost of the test activity with respect to both to time and resources. For that purpose, after each dynamic evolution of the system we determine the subset of components of the system which were impacted by the considered dynamic evolution. This allows us not to execute all the available test cases at runtime. Rather we choose a minimal subset of tests (corresponding to the modified parts of the system) and then we re-execute them. Our technique is based on the use of a dependency analysis algorithm. The latter is used in several software engineering branches (e.g., testing [START_REF] Li | Matrix-based Component Dependence Representation and Its Applications in Software Quality Assurance[END_REF], maintenance and evolution (Qu et al., 2010), etc.).

In [START_REF] Alhazbi | Dependencies Management in Dynamically Updateable Component-Based Systems[END_REF] the authors define dependency as "the reliance of a component on other(s) to support a specific functionality". So It can be seen as a binary relation between components. A component C 1 is said to be an antecedent to component C 2 if its functionalities or data are exploited by C 2 . Moreover in this case, B is said to be dependent on C 1 . For a such situation we use the following notation

C 2 → C 1 .
The authors of [START_REF] Larsson | Configuration Management for Component-Based Systems[END_REF] define the relation → in a formal fashion as follows. Let N odes be the set of components of the considered system. The set of dependencies of this system is:

Dep = (C p ,C q ) : C p ,C q ∈ N odes ∧C p → C q .
In this manner, the current configuration of the system is made of two elements namely the set of components and the set of corresponding dependencies C on f = (N odes, Dep). At the beginning, the dependency graph stores only the direct dependencies between the different components of the system. Then in a second step indirect dependencies are calculated by means of transitive closure algorithm [START_REF] Ioannidis | Efficient Transitive Closure Algorithms[END_REF] applied on the initial graph. For instance in the example given by Figure 2 there is no direct dependency between the two nodes C1 and C4 however an indirect dependency exist between them through the node C2. Similarly an indirect dependency exist between C1 and C5 through the node C3.

Test Case Selection

When dynamic adaptations occur, we need to consider two types of test cases. The first type corresponds to unit tests which allow to check the correctness of the components which were affected at a local level. Besides, the second type corresponds to integration tests which are necessary to guarantee compatibility and correct interaction between the different components of the system which were influenced by the dynamic adaptation.

As shown in Figure 3, this step consists in identifying a subset of test cases from an already existing test suite in order to test the affected parts of the system. For that purpose several regression test selection methods have been adopted in the literature. The proposed methods are mostly based on dependency analysis techniques [START_REF] Rothermel | Analyzing Regression Test Selection Techniques[END_REF]. Since we opted for a standard-based test execution platform, our tests will be written in the TTCN-3 language and run by TTCN-3 test components. More precisely two types of TTCN-3 components are needed namely Main Test Components (MTC) and Parallel Test Components (PTC). As illustrated in Figure 4, an MTC can be charged of the execution of a unit test for a specific component of the system under test (Figure 4.a). Otherwise it can collaborate with a set of PTCs in order to execute some integration tests corresponding to a set of interacting components of the system (Figure 4.b). In the next section we explain how the placement of these different test components is done.

Test Component Placement

In this section, we explain how to compute an adequate plan to distribute test cases over the different nodes of the execution environment. For this purpose we consider both connectivity and resource constraints of the different components of the system.

First the connectivity constraint corresponds to the fact that a given TTCN-3 test component needs to have a connection (either direct or indirect) with all components of the system it is in charge of testing. For instance the system shown in Figure 5 is made of ten components. These components can be divided into three subsets according to connectivity namely {C1,C2,C3}, {C4,C5} and {C6,C7,C8,C9,C10}. Consequently at least three test components are needed in order to test this system (i.e., a TTCN-3 test component for each of the previously defined subsets of the system nodes).

The second constraint to take into account at this level deals with the availability of resources required by test components in order to execute the set of selected test cases. That is each node of the execution environment which is hosting a particular test component must have enough resources to execute the test cases attributed to this test component. Among these resources we may consider for instance the CPU load, the memory occupation, the storage capacities, etc.

Computing an adequate test placement strategy is done by fitting the previous constraints. This procedure may be considered as a Constraint Satisfaction Problem (CSP) [START_REF] Ghédira | Constraint Satisfaction Problems, chapter Foundations of CSP[END_REF]. More precisely the problem in hand can be instantiated as a particular variant of the Knapsack Problem [START_REF] Martello | Knapsack Problems: Algorithms and Computer Implementations[END_REF][START_REF] Kellerer | Knapsack Problems[END_REF], called Multiple Multidimensional Knapsack Problem (MMKP) [START_REF] Lahami | Using knapsack problem model to design a resource aware test architecture for adaptable and distributed systems[END_REF]. As presented in Figure 6, the test component placement takes as inputs the minimal set of test cases (generated during the test selection phase), a description of the amount of resources needed by the test components and finally a description of the state of available resources in each node of the execution platform. As an output this module generates a resource aware test plan.

Test Isolation and Execution

As already mentioned our work is based on the TTCN-3 standard. More precisely we are inspired by the work of (Lahami et al., 2012a;[START_REF] Lahami | Safe and Efficient Runtime Testing Framework Applied in Dynamic and Distributed Systems[END_REF]. Next we recall the main constituents of the TTCN-3 reference architecture as shown in Figure 7 In Figure 7, the abbreviation TCI stands for TTCN-3 Control Interface and the abbreviation TRI stands for TTCN-3 Control Interface. As already mentioned, we need to consider some isolation operations during the test execution phase in order to avoid any possible interference between business behaviors and test behaviors. So inspired by the work of [START_REF] Lahami | Safe and Efficient Runtime Testing Framework Applied in Dynamic and Distributed Systems[END_REF], we intend to extend the standard TTCN-3 architecture with a test isolation component (Figure 8). This new component is connected with both the system adapter (SA) and the system under test. It allows to choose the appropriate isolation strategy for each constituent under test depending on the nature of that constituent. Next, we briefly describe five possible isolation strategies:

• The BIT-based strategy: corresponds to a builtin-testing approach where we assume that the SUT components are initially equipped with interfaces which accept both business inputs and test inputs simultaneously.

• The aspect-based strategy: which is inspired from Aspect-Oriented Programming (AOP) paradigm [START_REF] Kienzle | Transactions on Aspect-Oriented Software Development VII: A Common Case Study for Aspect-Oriented Modeling, chapter Crisis Management Systems: A Case Study for Aspect-Oriented Modeling[END_REF][START_REF] Kiczales | An Overview of As-pectJ[END_REF] and consists in equipping each SUT component with an aspect providing testing facilities.

• The tagging-based strategy: consists in tagging test inputs with a special flag to differentiate them business inputs.

• The cloning-based strategy: consists in creating a copy of the component under test and then testing the created clone instead of the original component.

• The blocking-based strategy: consists in preventing temporarily the component under test from receiving any requests from its environment except from the test components to which it is connected.

Figure 8: TTCN-3 Architecture Extended with an Isolation Component [START_REF] Lahami | Safe and Efficient Runtime Testing Framework Applied in Dynamic and Distributed Systems[END_REF].

Testing of Behavioral Adaptations

Now we move to the second part of this work which deals with runtime testing of distributed information systems after behavioral adaptations. For this purpose we adopt a formal approach [START_REF] Krichen | A Formal Framework for Conformance Testing of Distributed Real-Time Systems[END_REF][START_REF] Krichen | Conformance testing for real-time systems[END_REF] based on the use of the model of timed automata [START_REF] Alur | A theory of timed automata[END_REF]. That is we assume the our system is modelled as a simple timed automaton or a product of timed automata. Moreover we assume the considered model may evolve either partially or entirely after the occurrence of a dynamic behavioral adaptation. Consequently there is a need to update the set of available test cases either by creating new tests or modifying old ones. For that reason we need to take advantage from both selective regression testing and modelbased testing techniques. In order to reach this goal, we adopt a four-step approach as illustrated in Figure 9. The four considered steps are the following:

• Model Differentiation: consists in comparing the old and the new model of the distributed information system we have in hand in order to detect similarities and differences between them; • Old Tests Classification: consists in sorting the old tests and dividing them into three groups (1. Tests which need to be removed because they are no longer valid, 2. Tests which are partially valid and need to be updated and finally 3. Tests which are still valid and do not need any update); • Test Update and Generation: consists in updating the partially valid tests detected in the previ-ous step and generating new test cases covering the new behaviors appearing in the new model of the system;

• TTCN-3 Transformation: consists in concretizing the set of obtained tests by translating them from an abstract level into a TTC-3 representation.

More details about these different steps are given in the next subsections. However before that we start by giving a brief description of the formalism used to model distributed information systems, namely UP-PAALL timed automata.

UPPAAL Timed Automata

In order to specify the behavioral models of evolved systems, Timed Automata (TA) are chosen for the reason that they correspond to a widespread formalism usually used for modeling behaviors of critical and real-time systems. More precisely, we opt for the particular UPPAAL style [START_REF] Behrmann | A tutorial on uppaal[END_REF] of timed automata because UPPAAL is a wellestablished verification tool. It is made up of a system editor that allows users to edit easily timed automata, a simulator that visualizes the possible dynamic execution of a given system and a verifier that is charged with verifying a given model w.r.t. a formally expressed requirement specification. Within UPPAAL timed automata, a system is modeled as a network of timed automata, called processes. A timed automaton, is an extended finite-state machine equipped with a set of clock-variables that track the progress of time and that can guard when transitions are allowed.

Let C l be a set of continuous variables called clocks, and Act = I np ∪ Out} where I np is a set of inputs and Out a set of outputs. Gd(C l) is defined as the set of guards on the clocks C l being conjunctions of constraints of the form c op n, where c ∈ C l, n ∈ N, and op ∈ { , ≤, =, ≥, }. Moreover, let U p(C l) denote the set of updates of clocks of the form c := n.

A timed automaton over (Act, C l) is a tuple (Loc, l 0 , Act,C l, Inv, Ed), where :

• Loc is the set of locations;

• l 0 ∈ Loc is the initial location;

• Inv : Loc -→ Gd(C l) a function which an invariant to each location;

• Ed is the set of edges such that Ed ⊆ Loc × Gd(C l) × Act τ × U p(C l) × Loc.
A simple example of a UPPAALL timed automaton is shown in Figure 10. It has:

• Two locations: Idle and InUSe; • One input action: use?;

• One output action done!;

• One clock (x).

The system is initially occupying the location Idle. The clock x is reset to 0 when the input action use? takes place. The system is allowed to stay at most C times unit at the location InUse. Finally when the clock x reaches the value C the output action done! is produced and the system goes back to its initial location. Then the same cycle can start again and again.

Model Differentiation

As already mentioned the goal of this step is to compare the old and new models of the system under test. That is to find differences and similarities between them. This allows us to avoid generating the whole set of test cases from scratch after each behavioral adaptation of the system. For this purpose we need to split the behaviors described by the new model of the system into four groups (as illustrated in Figure 9):

• Newly Detected Behaviors: correspond to the set of behaviors present in the new model of the system but not in the old one;

• Partially Valid Behaviors: correspond to the set of behaviors that bear a high level of similarity with some old behaviors of the system but are not completely identical to them;

• Still Valid Behaviors: correspond to the set of behaviors which are in common between the two versions of the model of the system;

• No Longer Valid Behaviors: correspond to the set of behaviors present in the old model of the system but not in the new one and which therefore must be rejected.

To achieve this goal, we need to take advantage from different works present in the literature. For instance, [START_REF] Pilskalns | Regression Testing UML Designs[END_REF] presented a technique which allows to reduce the complexity of identifying the modification impact from different UML diagrams. The authors consider different design changes which are classified according to whether they create, modify, or delete elements in the diagram.

In this same context, [START_REF] Chen | Modelbased Regression Test Suite Generation Using Dependence Analysis[END_REF] propose a regression technique based on the use of the model of Extended Finite State Machine. This model is used to identify the effects of three types of modifications: modification, addition or deletion of a transition.

Old Tests Classification

Once the computation of the different sets of behaviors is achieved as explained in the previous step, the next task to do consists in splitting the set of old available test cases accordingly into three subsets of tests (see Figure 9):

• Partially Valid Tests: correspond to the set of partially valid behaviors of the new model of the system;

• Still Valid Tests: correspond to the set of still valid behaviors of the new model;

• No Longer Valid Tests: correspond to the set of no longer valid behaviors present in the old model of the system and which must be rejected.

At this level too we need to take advantage from existing contributions in the literature. For example, [START_REF] Briand | Automating Regression Test Selection Based on UML Designs[END_REF] introduce a UML-based regression test selection strategy. The latter allows to classify tests issued from the initial behavioral models as obsolete, reusable and re-testable tests.

Similarly, [START_REF] Fourneret | Selective Test Generation Method for Evolving Critical Systems[END_REF] proposed a technique which selects reusable tests, discards obsolete ones and generates only new ones.

Moreover in [START_REF] Korel | Test Prioritization Using System Models[END_REF], the authors split the set of old tests into high and low priority subsets. A high priority is attributed to tests that manipulate modified transitions and a low priority to tests that do not include any modified transition.

Test Update and Generation

As illustrated in Figure 9, we need to update partially valid tests identified during the test classification step and to derive new test cases from the newly detected behaviors identified during the model differentiation step. For this purpose we need to use techniques borrowed from model-based testing approaches [START_REF] Krichen | Conformance testing for real-time systems[END_REF][START_REF] Krichen | A formal framework for black-box conformance testing of distributed real-time systems[END_REF].

More precisely the technique we intend to adopt consists in using a particular type of timed automata called observer automata [START_REF] Blom | Specifying and Generating Test Cases Using Observer Automata[END_REF]. These automata allow to model the specific behaviors we are interested in testing. In our case the behaviors to model are the newly detected behaviors discovered during the differentiation step.

The main steps to follow are the following:

1. Transforming the desired behavior into an observer automaton;

2. Computing the product of the observer automaton and the new timed automaton model of the system under test;

3. Deriving test cases from the obtained timedautomaton product using classical test generation techniques.

The previously mentioned steps can be performed using the test generation tool UPPAAL CO √ ER [START_REF] Hessel | CO √ ER A Real-Time Test Case Generation Tool[END_REF] which supports the notion of observers and test case generation.

TTCN-3 Transformation

This step consists in defining a set of rules to derive TTCN-3 tests from abstract test cases obtained during the previous steps. Our transformation algorithm will be inspired by the following works [START_REF] Rennoch | TTCN-3 Quick Reference Card[END_REF]Lahami et al., 2012a;[START_REF] Hochberger | Informatik 2006 -Informatik für Menschen, Band 2, Beiträge der 36[END_REF][START_REF] Ebner | TTCN-3 Test Case Generation from Message Sequence Charts[END_REF].

In table 1 we give some examples of the rules to use to translate abstract test cases into concrete TTCN-3 tests. These rules are briefly explained below:

• R1: consists in generating a new TTCN-3 module for each considered abstract test suite;

• R2: consists in transforming each abstract test sequence into a concrete TTCN-3 test case;

• R3: consists in associating a TTCN-3 timer with each abstract timed behavior;

• R4: consists in transforming each abstract test sequence (with the form input-delay-output) into a concrete TTCN-3 function;

• R5: consists in transforming the abstract channels (declared in the UPPAAL XML file) into concrete TTCN-3 templates. In this article, we adopted a runtime testing approach to validate and test dynamic distributed information systems. For this purpose, we proposed a standard-based and resource aware test execution platform which allows to deal efficiently with both structural and behavioral adaptations. On the one hand structural adaptations correspond to the addition or deletion of nodes and/or connections between the nodes of the system under test. On the other hand behavioral adaptations correspond to the addition, deletion or update of the software components or functionalities installed on the physical devices of the considered system under test.

Firstly, Our platform is standard-based since it is built upon the TTCN-3 specification and execution testing language. Indeed we adopted the generic standard TTCN-3 architecture extended with an isolation layer which allows to avoid possible risks of interference between testing and business processes. To reach this goal, five possible isolation strategies may be adopted at this level namely: 1. BIT-based, 2. aspect-based, 3. tagging-based, 4. cloning-based, and finally 5. blocking-based.

Secondly, our platform is resource aware since it ensures test selection and optimal placement of test components among physical nodes of the system under test. The test selection phase consists in identifying a subset of tests scenarios from an already existing repository in order to test the affected parts of the system. Besides, the placement phase consists in computing an appropriate plan to assign test cases to the different nodes of the execution environment using adequate optimization techniques.

Regarding behavioral adaptations, our methodology comprises four steps. The first step corresponds to the differentiation between the old and the new models of the system in order to identify similarities and differences between them. The second step consists in sorting the old tests and splitting them into three suitable sets. The third step lies in updating a subset of old tests and in generating a set of new test cases. Finally, the fourth step consists in translating the set of obtained tests scenarios from an abstract representation into the TTCN-3 language.

Our work is at its beginning and many efforts are still needed on both theoretical and practical aspects in order to achieve the different goals mentioned in this article:

• We need to build an appropriate model for the considered system under test. At this level we need to choose an optimal level of abstraction for this model. That is the latter should be neither too small nor too big. Being too small may cause the loss of important details of the system and being too big may lead to the famous state explosion problem which may make our approach completely infeasible.

• We also need to consider some sophisticated heuristics to solve the test component placement problem. In fact since we are adopting a runtime testing approach then the time to find an acceptable placement plan should be enough short in order to detect anomalies at the right moment.

• Moreover we need to propose efficient technical solutions to implement the different isolation strategies mentioned previously in this article. In the same manner we should develop and install adequately the different TTCN-3 test components upon the physical devices of the system in order to guarantee the success of the whole approach.

Figure 1 :

 1 Figure 1: The different steps for structural adaptations validation of the system under test.

Figure 2 :

 2 Figure 2: An example of a 5-nodes dependency graph and its corresponding 5x5 dependency matrix. The configuration of the system can be presented either by a Component Dependency Graph or an equivalent Component Dependency Matrix. In Figure 2 we give an example of such a dependency graph and its equivalent dependency matrix.At the beginning, the dependency graph stores only the direct dependencies between the different components of the system. Then in a second step indirect dependencies are calculated by means of transitive closure algorithm[START_REF] Ioannidis | Efficient Transitive Closure Algorithms[END_REF] applied on the initial graph. For instance in the example given by Figure2there is no direct dependency between the two nodes C1 and C4 however an indirect dependency exist between them through the node C2. Similarly an indirect dependency exist between C1 and C5 through the node C3.

Figure 3 :

 3 Figure 3: Illustration of the test selection phase.

Figure 4 :

 4 Figure 4: TTCN-3 components used to execute unit and integration test cases.

Figure 5 :

 5 Figure 5: An example of a system under test made of ten components.

Figure 6 :

 6 Figure 6: Illustration of the TTCN-3 Test Component Placement Module.

  : • Test Management (TM): starts and stops tests, provides parameters and manages the whole test process; • Test Logging (TL): handles all log events; • TTCN-3 Executable (TE): executes the compiled TTCN-3 code; • Component Handling (CH): distributes parallel test components and ensures communication between them; • Coding and Decoding (CD): encodes and decodes data exchanged with the TE; • System Adapter (SA): adapts the communication with the system under test; • Platform Adapter (PA): implements external functions.

Figure 7 :

 7 Figure 7: TTCN-3 Reference Architecture (Lahami et al., 2016).

Figure 9 :

 9 Figure 9: The different steps for behavioral adaptations validation of the system under test.

Figure 10 :

 10 Figure 10: A simple UPAALL timed automaton.

Table 1 :

 1

	R#	Abstract Concepts TTCN-3 Concepts
	R1	Test Suite	TTCN-3 Module
	R2	Single Trace	TTCN-3 Test Case
	R3	Timed Behavior	TTCN-3 Timer
	R4	Test Sequence	TTCN-3 Function
	R5	Channel	TTCN-3 Template

• Finally we may combine load and functional testing aspects as done in[START_REF] Krichen | A model-based approach to combine conformance and load tests: an ehealth case study[END_REF][START_REF] Maâlej | Automated significant load testing for WS-BPEL compositions[END_REF][START_REF] Maâlej | Modelbased conformance testing of WS-BPEL compositions[END_REF] Maâlej et al., 2012a).


Jean-Philippe Bauchet
email: jean-philippe.bauchet@inria.fr

Florent Lafarge
email: florent.lafarge@inria.fr

CITY RECONSTRUCTION FROM AIRBORNE LIDAR : A COMPUTATIONAL GEOMETRY APPROACH

Keywords: Urban reconstruction, airborne Lidar, point clouds, classification, kinetic data structures

We introduce a pipeline that reconstructs buildings of urban environments as concise polygonal meshes from airborne LiDAR scans. It consists of three main steps : classification, building contouring, and building reconstruction, the two last steps being achieved using computational geometry tools. Our algorithm demonstrates its robustness, flexibility and scalability by producing accurate and compact 3D models over large and varied urban areas in a few minutes only.

INTRODUCTION

Urban reconstruction techniques have attracted an increasing attention from the scientific community over the last decade. Applications of such techniques include, for instance, urban planning, natural disaster management, or radio-wave propagation (l, i).

Various data sources are considered by such algorithms, such as ground imagery, satellite imagery, or pre-existing GIS data. However, despite high acquisition costs, LiDAR point clouds are more accurate and remain a data source commonly used by land surveying offices or civil engineers (s, u).

Yet, models generated by current city modeling techniques may be enriched with semantic information, or represented using progressive levels of detail. The CityGML standard (ö, r) considers four coarse-to-fine levels applicable to airborne datasets, from LOD0 to LOD3.

In this paper, we present a pipeline that receives as input an unstructured point set describing a urban environment, and generates as output a LOD2 representation of the scene in compliance with the CityGML standard. More precisely, we aim at providing a faithful reconstruction of buildings with tilted roofs. The representation of superstructures like dormers or chimneys is beyond the scope of this paper. Our main idea is to make use of powerful computational geometry tools to extract the geometric signatures of the observed buildings. We emphasize the accuracy and the scalability of our method, since it is able to process large datasets with millions of points, dense or sparse, in a few minutes.

RELATED WORKS

There exists a vast literature on automatic urban reconstruction techniques, (a, a; t, o; s, u), demonstrating the deep interest of scientists and industrials for this research topic. Various data sour-ces may be considered, leading us to draw a first distinction between all existing approaches, based on this criterion. Indeed, some algorithms may specifically address the problem of large-scale urban reconstruction from aerial imagery (b, e; n, e), satellite imagery (a, u) or multi-view stereo dense meshes (u, h; r, e; l, a). Some others combine different sources of data to generate urban models with the finest level of detail (l, e).

In this work, we focus on the problem of city modeling from LiDAR point clouds. Roof height estimation and building reconstruction is often the most valuable information to extract from such data, which is acquired using terrestrial or aerial devices. In particular, nadir or near-nadir acquisitions pose a specific constraint, as facades are missed by scanners. Current state-of-the-art approaches have been extensively reviewed (n, a) and can be divided in three categories.

Data-driven methods are probably the most popular techniques. These are bottom-up approaches, in which parametric primitives are extracted from the data and assembled to form a reconstructed model. Existing pipelines typically consist of three successive steps : classification, segmentation and geometric modeling. The semantic interpretation of the data, and the clustering of buildings into individual structures may involve statistical arguments (u, o) or discriminative geometric features coupled with energetic formulations (f, a). However, the models produced by such techniques do not achieve the same level of detail. For instance, the methods proposed in (o, h) and (u, o) only reconstruct multi-level flat buildings from airborne point clouds, which is suitable for Manhattan-like districts but less accurate for residential areas. In contrast, the algorithm of (h, o) considers a binary space partitioning tree to generate LOD2 polyhedral meshes from a point cloud. The one of (o, h) reaches a similar level of detail by minimizing 2.5D quadric error functions, i.e. taking into account both the surface being reconstructed and its projected boundary. However, due to the projection of the points on a 2D grid, the reconstructed facades show a zig-zagging effect, which might be corrected by the mesh simplification procedure described in (o, h). The cell decomposition approach proposed in (d, a) allows to reconstruct buildings with a compact representation, but requires precise building footprints as input. The method of (f, a) also returns persuasive results over large-scale areas, but suffers from the same failing. Recently, deep-learning-based methods have also been developed in a context of LOD2 urban modeling and achieve very promising results (a, h).

Model-driven methods, for their part, represent the opposite, Figure 1. Overview of our pipeline. Our method consists of three main steps. We first label points of the LiDAR scan as ground, vegetation or roof. Then, we apply a contouring algorithm to the height map, revealing the facades initially absent in the point set. Finally, we extract and propagate planar primitives from the point cloud, dividing the space into polyhedra that are labelled to obtain a 3D reconstruction of buildings.

top-down strategy. This family of techniques considers a predefined library of template structures (e.g. flat, gable, hip or mansard roofs) that is matched to the input data. The work of (r, e) offers a first example of model-driven algorithm : elements of the point cloud are first classified as flat or non-flat and a roof topology graph is considered to decompose a complex building into simpler structures. Another example is the work of (a, u) in which a stochastic approach is used to select the roof templates that best fit the input data. Also requiring building footprints as prior knowledge, the method of (n, e) uses Ransac and supervised machine learning techniques to generate a LOD2 reconstruction of a sparse LiDAR point in a model-driven way. However, such approaches may lack of flexibility with respect to the variety of urban landscapes. Finally, hybrid-driven methods try to take the best of both worlds : parameterized primitives are extracted and assembled with respect to a set of constraints derived from constructive solid geometry (o, i) (f, a).

In the following, we present an algorithm that addresses the problems we exposed before by exploiting powerful computational geometry tools. Given an airborne input point cloud, we design a scalable and data-driven algorithm that generates LOD2 representations of different urban environments as concise polyhedral meshes.

ALGORITHM

Input

As depicted by Figure 1, our algorithm takes as input a point cloud with oriented normals. Normals can be easily estimated thanks to the acquisition system information. If not provided, then basic mathematical tools like principal component analysis can be used.

Classification

The first step of our pipeline consists in assigning semantic labels to points of the point cloud. Three labels are considered : ground, vegetation, and building.

To this end, we rely on the classification package provided by the CGAL library (r, i). For each point of the input dataset, this method computes multi-scale geometric features such as elevation, planarity or vertical dispersion for instance. Extra features provided along with the dataset, like the number of returns, are also taken into account. Given a ground truth training set, these features are then used to train a classifier. The default choice for the classifier is a random forest, that constructs several decision trees to assign each point to one of the three aforementioned subsets.

Interactively labelling the data to get a representative training dataset is a tedious work. However, the CGAL library offers the possibility to save and reuse a trained classifier, which is particularly useful for processing urban scenes of similar nature (dense or surburban areas, downtowns, historical centers...).

Building contouring

Facades of buildings are often partially or completely missing in aerial point clouds. To obtain accurate reconstructions of cities from such data, we first need a robust method that detects significant height discontinuities in the classified point cloud.

To this end, we project all points on a horizontal, uniformly sampled grid, in order to generate two kinds of maps : (i) a height map, normalized as a grayscale image, (ii) a probability map, measuring the proportion of projected points labelled as buildings in each cell of the grid.

These two maps are then processed by the polygonal partitioning technique of (u, a). Given an input image, this algorithm first detects line-segments, which are linear approximations of regions where the image gradient is high and regular. These line-segments propagate across the image, until intersecting each other, resulting in a decomposition of the image into convex polygons. Here, we generate a polygonal decomposition of the height map. Intuitively, the detected line-segments, later included in the edges of the partition, correspond to regular height discontinuities in a given direction, i.e. to facades.

Using the probability map previously defined, we further assign a binary activation variable to each polygonal cell, indicating if it is part, or not, of a building footprint. In order to simplify the partition, and decrease the number of cells, we finally apply a clustering algorithm that merges neighbor cells upon condition that there is no height discontinuity at their common border.

Building reconstruction

To obtain a LOD2 reconstruction from an oriented point cloud, from which we discard all points labelled as vegetation, we propose an algorithm in three steps.

First of all, we extract planar primitives from the point cloud.

We apply a region-growing algorithm, implemented in the CGAL library (s, e). A plane hypothesis is iteratively propagated from a point to its neighbors. It is accepted if it has a minimum number of inliers N , with respect to a maximal point-to-plane distance ε. If input points are noisy, more robust methods such as efficient Ransac (h, c) or structure-aware shape collapse (n, a) can be considered. The threshold N should be set depending on the density of the cloud, so that N points cover an area of 5 m 2 approximately, whereas ε is typically set to 0.5 m. Once all planes have been extracted, we obtain a set of primitives represented by the planar convex hulls of the different sets of inliers associated to those planes.

The second step of our algorithm consists in performing a kinetic propagation of the primitives in the 3D space. Similarly to the work of (u, a), we initialize and process a priority queue to predict and sort intersections between extending primitives. We choose to apply homothetic transformations of ratio (1 + t), where t ≥ 0 represents the current simulation time. Assuming the existence of a bounding box containing all primitives, processing all intersections results in a polyhedral decomposition of the space.

However, predicting the intersection time between two planar primitives is a costly operation. For large datasets with millions of points, the simultaneous propagation of thousands of primitives is a very complex and time-consuming operation. On the other hand, vertical planes corresponding to facades cannot be extracted from the input point cloud, since the data is missing. This is the reason why we split the spatial propagation problem into F subproblems, where F is the number of polygonal footprints returned by the procedure described in section 3.3. More precisely, for each footprint we get the list of primitives that intersect or are included in it by projection, and perform a spatial propagation restricted to the dimensions of the footprint. We obtain a set of F 3D subgraphs G1, G2, . . . GF .

The third and final step of our pipeline consists in labelling the polyhedra of each subgraph Gi as inside or outside the buildings to reconstruct. The facets at the interface between outside and inside polyhedra then correspond to the output surface.

We use a voting scheme, based on the observation that in aerial datasets, points delimit the upper parts of the objects of interest. Let Pi be the set of polyhedrons of the subgraph Gi. For each polyhedron pj ∈ Pi, where j = 1, 2 . . . |Pi|, we initialize a counter cj to 0. All polyhedrons located below (resp. above) any plane inlier decrement (resp. increment) their counters.

Let us now consider a vector X with |Pi| binary activation variables : xj = 1 (resp. xj = 0) if the polyhedron pj is labelled as inside (resp. outside) a building to extract. We measure the quality of an output surface using a two-term energy of the form

U (X) = D(X) + λV (X) (1)
D(X) is a data term that encourages the selection of a polyhedron pj when cj < 0, and its rejection when cj > 0. We have :

D(X) = 1 |I| |P i | j=1 dj(xj) (2)
where

dj(xj) = -cj when xj = 0 cj when xj = 1 (3)
and |I| is twice the number of inliers. V (X), for its part, is a generalized Potts model that penalizes the total area of the surface :

V (X) = 1 A j∼k a jk • 1 x j =x k (4)
where j ∼ k denotes an adjacency relationship between two polyhedra pj and p k , a jk is the surface of their common facet, and A is a normalization term defined as the sum of the areas of all facets of the subgraph Gi.

Given a balancing term λ ∈ [0, 1], the optimal surface that minimizes energy U is determined by a min-cut algorithm (y, o). A low value of λ returns a too large and too complex surface, while a high value of λ tends to shrink it. In our experiments, we typically set λ to 0.5.

EXPERIMENTS

Datasets. We tested our algorithm on four datasets, representing various urban landscapes. The covered cities are listed in Table 1. The size is given in millions of points.

Qualitative results. We present in Figures 2,3, 4 and 4 the models generated by our algorithm for these cities. From a qualitative point of view, we obtain persuasive LOD2 reconstructions of most buildings. The Biberach and Vaihingen datasets contain a lot of gable and hip roofs which are correctly approximated by our algorithm. As for the Portland and San Diego datasets, our technique also succeeds in determining intermediate levels in complex structures, as well as tilted roofs if any. Facades, which are almost completely missing in the input scans, are generally recovered by a single plane in a given direction. Some of them, however, might be affected by an unwanted zig-zagging effect, reflecting errors in the building contouring procedure. Note that trees could be also reconstructed in 3D by template matching (r, e) to better represent the urban landscapes.

Quantitative results. In Figures 2 and3, we provide altimetric error maps for each dataset. To generate them, we restrict the input point cloud to elements labelled as rooftops, and compute the one-sided Hausdorff distance from every point to the reconstructed surface. This way, we can evaluate the precision of our method. We compute a raw reconstruction error : the mean footprints towards one direction or another.

Performances. We list in Table 3 the performances of our algorithm for our two biggest datasets, Vaihingen and Portland, in terms of memory peak and running times. Measures were perform on a machine equiped with an Intel R Core TM i7-6700HQ processor clocked at 2.60 GHz and a 32 GB RAM. The obtained values demonstrate the ability of our algorithm to process large volumes of data in a short time.

Limitations. Despite its advantages, our algorithm suffers from a few shortcomings. Any error caused by an intermediate step of the pipeline has an impact on the final result. Parts of the cloud representing buildings mislabelled by the classifier will not be reconstructed. Besides, the reconstruction is very sensi- tive to building contouring errors : if some footprints or intermediate heights inside multi-level structures are missed in the coutouring process, then buildings will also be missing or badly approximated in the final result.

Besides, our primitive detection scheme only extracts planes from the input point cloud. This feature is sufficient for reconstructing accurately most buildings, but free-form shapes like domes or curved walls will only be approximated as a set of planar shapes. Small structures like dormers and chimneys may also be ignored in the reconstructed model, if the minimal number of inliers by the plane extraction procedure is too high.

CONCLUSIONS

In this paper, we presented a pipeline for automatically reconstructing a urban scene from an airborne LiDAR scan at the level of detail LOD2. We used a kinetic approach, in which a set of predetected line-segments and planar polygons propagate to decompose the 2D and 3D spaces into cells that are labelled and assembled in our final model. Our approach is fast, scalable and delivers simple polyhedral meshes. It returns promising results on various datasets, representing different types of urban environments.

In future works, we plan to refine the building contouring algorithm in order to simplify and improve the accuracy of our reconstructed models. We might resort to deep-learning-based methods to this end. Another research path would consist in integrating non-linear primitives to our kinetic scheme to achieve better reconstructions of free-form structures.

Figure 2 .

 2 Figure 2. Results on European-style urban landscapes. Left column : classified point clouds. Points labelled as ground, vegetation or buildings are colored in gray, green and red, respectively. Center column : reconstructed models. Right column : altimetric error map, in which a darker color represents a larger error. From left to right : classified point cloud, reconstructed model, and altimetric error map. Some close-ups are showed in Figures 4 and 4.

Figure 3 .

 3 Figure 3. Results on American-style urban landscapes. Some close-ups are showed in Figures 4 and 4.

Figure 4 .

 4 Figure 4. Close-ups on the reconstructed models. From top to bottom : church (Biberach), tent (Biberach), residential area (Vaihingen).

Figure 5 .

 5 Figure 5. Close-ups on the reconstructed models. From top to bottom : multi-level building (Portland), urban landscape (San Diego).

Table 1 .

 1 Presentation of the dataset.

	City	Type	Size	Density (pts/m 2 )
	Biberach	Historical center 2.3M	3.0	Biberach	0.85	0.31
	Vaihingen	Residental area	7.3M	6.3	Vaihingen	1.91	0.43
	Portland	Downtown	8.7M	7.8	Portland	1.75	0.53
	San Diego	Downtown	4.5M	1.6	San Diego	2.34	0.62
	one-sided Hausdorff distance. However, this measure may be
	biased. Indeed, isolated mislabelled points in the classification
	process, and a few buildings missed by the contouring algo-
	rithm and further ignored in the reconstruction phase, tend to
	overestimate the average reconstruction error. That is why we
	suggest, on an indicative basis, a corrected reconstruction er-
	ror, which discards points located at more than 3 meters from
	a building which corresponds to the average height of a floor.
	Our measures are listed in Table 2.

The geometric error is typically caused by : (i) undetected superstructures on rooftops, (ii) uncorrectly approximated primitives in the plane extraction procedure (e.g. a unique plane approximates the two sides of a gable roof) and (iii) the resolution of the generated height map, that may shift the extracted

City

Raw error (m) Corrected error (m)

Table 2 .

 2 Geometric error for each dataset.

Table 3 .

 3 Performance measures for datasets Vaihingen and Portland.

		Vaihingen Portland
	Building contouring (s)	13.5	20.9
	Building reconstruction (s)	509.3	872.8
	Memory peak (GB)	2.2	2.6

ACKNOWLEDGEMENTS

This work was supported by LuxCarta Technology. The authors thank Lionel Laurore, Yuliya Tarabalka and Frederic Trastour for their comments and technical discussions.


Simon Clevers
email: simon.clevers1@univ-rouen.fr

Valérie Dupray

Florent Simon

Gérard Coquerel

G Coquerel Is

Is Second Harmonic Generation a

come   L'archive ouverte pluridisciplinaire

Introduction

Aim of this study : To evaluate the potential of SHG signal measurements to detect the phase transitions by comparison with other usual techniques such as Differential Scanning Calorimetry (DSC), X-Ray Powder Diffraction (XRPD). Two samples are studied : a commercial MHBA (normally constituted of the stable form) and a pure metastable product obtained by recrystallization in acetone.

Comparison with Differential Scanning Calorimetry

Comparison with X-Ray Powder Diffraction

Commercial MHBA

-XRPD confirms that :

• the 2 polymorphic forms are present in commercial MHBA.

• the structural impurity highlighted by SHG corresponds to the metastable form.

- -The commercial compound exhibits a low SHG signal (55 times less intense than the recrystallized product).

Thermo-SHG

Principle of SHG:

A laser beam is sent on the sample at the fundamental frequency ω ðIf the sample is non centrosymmetric a SHG signal is detected at twice the fundamental frequency. ðAccording to the Kurtz and Perry method 1 the signal is compared to a reference signal. In our case, samples were compared to KDP.

Second Harmonic Generation (SHG):

SHG is an optical process which can be used to detect the non-centrosymmetry of crystalline compounds 1,2 (powder form). In order to study phase transitions, a device has been developed to perform SHG measurements versus temperature. The case of 3-hydroxybenzoic acid is considered.

A known irreversible phase transition from the noncentrosymmetric metastable form (SHG Positive) to the centrosymmetric stable form (SHG negative) occurs at circa 160 C 3 .

3-Hydroxybenzoic acid (MHBA) exhibits two polymorphic forms :

SHG positive

The SHG device can be used to track this phase transition. ðThe SHG signal is measured versus temperature using a spectrometer.

Results:

-SHG allow the monitoring of the polymorphic transition of MHBA from its metastable to its stable form -SHG can probe the stuctural purity of the sample and track the conversion of a small amount of metastable form.

-

  In two cases : Average onset fusion peak ≈ 201.7 C -Recrystallized MHBA DSC scans exhibit a weak exothermic event around 167 C (at 10K/min) attributed to the crystallization of the metastable (Pna2 1 ) form into the stable form (P2 1 /c).-DSC curves of commercial MHBA exhibit no heat exchange corresponding to a phase transition. In the case of commercial product, this technique can not detect the

  ðThe commercial sample contains a SHG positive compound = small amount of metastable noncentrosymmetric form SHG and XRPD are complementary techniques Conclusion Understanding the possible relationship between the lattice thermal expansion (highlighted by a peak shift in TR-XRPD) and the SHG signal and determine more accurately the temperature of the solid-solid phase transition. to detect the phase transition in the case of the commercial product ðPossibility to follow a phase transition by SHG measurements. ðHigh sensitivity of SHG compared to DSC. ðIn favorable cases SHG is a very sensitive probe to assess the structural purity.

Non centrosymmetric peak reference disappears between 142 C and 152 C

	Relative X-R ay intensity
	16	16,2	16,4	16,6	16,8	17	17,2	17,4	17,6	17,8	18


est destinée au dépôt

Product

  Families for Crisis Management : The challenges of contemporary industry Houssem Chemingui, Sabrine Edded, Inès Gam El Golli To cite this version: Houssem Chemingui, Sabrine Edded, Inès Gam El Golli. Product Families for Crisis Management : The challenges of contemporary industry. International Conference on Information Systems for Crisis Response and Management in Mediterranean Countries, Oct 2015, Tunis, Tunisia. Information Systems for Crisis Response and Management in Mediterranean Countries Second International Conference, ISCRAM-med 2015, Tunis, Tunisia, October 28-30, 2015, Proceedings. hal-02295937

CERTIFICATE OF PRESENCE


S Clevers

A Burel

N Couvrat

V Dupray

G Coquerel

Relevance of Second Harmonic Generation Microscopy (SHG-M) in Material Sciences

Second harmonic generation (SHG) is an extremely sensitive and rapid technique to detect absence of inversion centers in crystalline structures. Combined with microscopy, SHG-M, permits (i) to monitor temperature-induced phase transitions; (ii) to detect noncentrosymmetric zones inside heterogeneous materials. Therefore, as analytical tool, SHG-M covers a large domain of applications, in complement with other classical techniques (e.g. XRPD, DSC, optical microscopy). The present work illustrates the use of SHG-M in selected monophasic and multiphasic sample studies. Particularly, reinvestigation of Phenanthrene phase transition is presented.

Introduction

If an intense electromagnetic field (laser) interacts with a crystal, the dielectric polarization of this crystal is not a linear response of the incident electric field and new effects appear. Second harmonic generation (SHG) is a second-order non-linear optical effect which occurs in non-centrosymmetric crystals. The first observation of such phenomena was reported by Franken et al. [START_REF] Franken | Generation of Optical Harmonics[END_REF] It should be noted that for centrosymmetric materials (i.e. where the inversion center is a symmetry element present in the crystal) second harmonic generation cannot occur. Among several methods to detect the noncentrosymmetry in crystals, SHG appears to be one of the most selective and sensitive because it allows the detection of almost all non-centrosymmetric classes [START_REF] Ok | Bulk characterization methods for non-centrosymmetric materials: second-harmonic generation, piezoelectricity, pyroelectricity, and ferroelectricity[END_REF] except the 432 classes. Note that for 622 and 422 classes SHG is theoretically forbidden by the Kleinman symmetry conditions. However, the Kleinman symmetry rule is only valid if there is no significant absorption, and thus presents some failures. [START_REF] Kleinman | Theory of Second Harmonic Generation Light[END_REF] Consequently, if second-order nonlinear optical materials have attracted much attention due to their high potential for photonic and optoelectronic applications, especially as frequency doubling crystals or devices (such as photonic crystals) [START_REF] Arie | Periodic, quasi-periodic, and random quadratic nonlinear photonic crystals[END_REF], SHG also appears to be relevant in systematic material analysis. [START_REF] Richardson | Systematic Materials Analysis[END_REF] In 1968 Kurtz and Perry [START_REF] Kurtz | A Powder Technique for the Evaluation of Nonlinear Optical Materials[END_REF] developed a method for assessing the efficiency of SHG in powder samples. This method is of particular interest because suitable single crystals are often not available in many cases, and was widely used for large screening of materials where only a small amount of powder is required. Moreover, powder SHG (PSHG) measurements are extremely fast compared to other spectroscopic methods. PSHG has thus been used in many material studies, e.g. to (i) resolve space group ambiguities when X-ray methods failed to draw unambiguous conclusions (direct evidence of the presence or absence of centrosymmetry could be decisive) [START_REF] Dougherty | A second harmonic analyzer for the detection of noncentrosymmetry[END_REF], (ii) find new efficient frequency converter crystals, and (iii) perform very fast prescreening of conglomerate with relevant applications in the pharmaceutical industry [START_REF] Galland | Spotting Conglomerates by Second Harmonic Generation[END_REF] (the presence of a SHG signal often indicates the absence of racemic compound, a condition required for the application of Preferential Crystallization [START_REF] Coquerel | Preferential Crystallization[END_REF]). This method was also recently used to assess the structural purity of an organic compound down to the ppm level. [START_REF] Clevers | Temperature resolved second harmonic generation to probe the structural purity of m-hydroxybenzoic acid[END_REF] SHG can also be coupled with a heating stage to monitor solid-solid phase transitions (temperatureresolved SHG or TR-SHG). To date, this has been used in several works, with application to monotropic phase transition [START_REF] Clevers | Monotropic Transition Mechanism of m-Hydroxybenzoic Acid Investigated by Temperature-Resolved Second Harmonic Generation[END_REF], enantiotropic phase transition [START_REF] Dougherty | A second harmonic analyzer for the detection of noncentrosymmetry[END_REF] or order-disorder phase transition [START_REF] Yuan | New Intermediate Polymorph of 1-Fluoro-adamantane and Its Second-Order-like Transition toward the Low Temperature Phase[END_REF]. It should be noted that the evolution of SHG signal with pressure was also recently studied [START_REF] Bayarjargal | Second harmonic generation measurements at high pressures on powder samples[END_REF].

Combined to a microscope, SHG microscopy (SHG-M) allows scientists to obtain a 2D or 3D view of the non-centrosymmetric zones (e.g. crystals, domains, defects) inside a bulk sample. SHG-M has proved a great relevance for imaging in several fields such as biology or material sciences. For example, SHG-M was used to monitor, in situ, the crystallization of a noncentrosymmetric phase from a supersaturated solution [START_REF] Kissick | Second-Order Nonlinear Optical Imaging of Chiral Crystals[END_REF], to selectively detect the presence of a pharmaceutical compound inside an excipient matrix [START_REF] Toth | Selective Imaging of APIs in Powdered Blends with Common Excipients Utilizing TPE-UVF and UV-SONICC[END_REF], to investigate microstructure [START_REF] Yokota | Optical Second Harmonic Generation Microscopy as a Tool of Material Diagnosis[END_REF], or to image a crystal undergoing a polymorphic transition [START_REF] Clevers | Monotropic Transition Mechanism of m-Hydroxybenzoic Acid Investigated by Temperature-Resolved Second Harmonic Generation[END_REF].

Tab. PSHG, TR-SHG and SHG-M cover a large domain of applications as analytical apparatus in complement with other classical techniques (e.g. XRPD, DSC, optical microscopy). If noncentrosymmetric structures are not the most numerous among materials (e.g. 24.1% of the structures reported in the Cambridge Structural Database (CSD) are non-centrosymmetric [START_REF] Allen | Applications of the Cambridge Structural Database in organic chemistry and crystal chemistry[END_REF]), they are preponderant in many fields of industrial applications (e.g. pharmaceuticals and optoelectronic devices). Recently, we have successfully achieved the purification of phenanthrene with an ultimate purity of 99.999 mol%. We report herein the reinvestigation of the known phase transition of this compound by means of SHG-M.

Phase transition in phenanthrene.

Three polymorphs of phenanthrene are know: (i) a low temperature (LT) ordered form crystallizing in the P2 1 space group, (ii) a high temperature (HT) form crystallizing in P2 1 /c space group and exhibiting dynamic disorder and (iii) an additional high pressure polymorph crystallizing in the P2 1 /m space group. [START_REF] Petricek | Orientational disorder in phenanthrene. Structure determination at 248, 295, 339 and 344 K[END_REF] In 1976, temperature-dependent SHG measurements were the first definitive evidence of the polymorphic transition between the LT-phase and the HT-phase (see Fig. 3a). [START_REF] Dougherty | A second harmonic analyzer for the detection of noncentrosymmetry[END_REF] TR-SHG monitoring showed the progressive conversion of the LT form toward the HT on heating (complete vanishing of the SHG signal due to the inversion center symmetry element in HT-form), and electrical resistance measurements suggested the potential occurrence of two separate transitions of different orders in a narrow temperature range. Besides the unusual character of Phenanthrene solidsolid transition, another parameter was found to critically influence on the behavior of the compound in the solid state. Indeed, the chemical purity of the solid has a strong impact on the transition, as on the melting point of the compound. [START_REF] Couvrat | Combining zone melting and preparative chromatography to purify Phenanthrene[END_REF] This exemplified through the various data reported in the literature about the solid-solid phase transition and summarized in Tab.1. They highlight, in particular, the discrepancies on the transition temperature and raised the question of the mechanism of the transition, which was, up to now, not resolved.

The study of this transition by means of SHG-microscopy could help to understand or point out the microscopic mechanism.

Material and methods

Mulitphoton microscope and TR-SHG

Insight X3 single laser with automated dispersion compensation (Spectra-Physics, Santa Clara, USA) and a TCS SP8 MP confocal microscope (Leica Microsystems, Wetzlar, Germany) were used to performed confocal microscopy as well as two-photon microscopy imaging of the samples. The laser cavity had over 2.67 W of average power at 900 nm and was tunable from 680 nm to 1300 nm. The repetition rate was 80 MHz and the temporal width at the output of the cavity was around 120 fs (<100fs between 850 nm and 1050 nm). The laser was controlled with the LASX Leica software. Two Leica hybrid descanned detectors (HyD) were used to record images in backward direction. For two-photon imaging experiments, signal was collected after the microscope objective via a dichroic beamsplitter, transparent to wavelengths greater than 815 nm. Microscope objectives were long working distance dry Leica objectives (HC PL Fluotar 5X NA 0.15, HC PL Fluotar 10X NA 0.3 or HC PL APO 20X NA 0.4 CS2). An electro-optical modulator was used to adjust the laser power at the entrance of the confocal system. The spectral acquisition was performed using an internal hybrid detector. The collected photons were dispersed by a prism and a specific motorized split mirror selects the spectral detected band before the hybrid detector. Acquisitions were performed between 385 nm and 780 nm every 3 nm and a spectral bandwidth of 5 nm. In order to check if the sample produce fluorescence, an emission spectral scan is performed. Typically, the sample is excited at a given wavelength (e.g. 1200 nm or 900 nm) while scanned through the emission wavelength (e.g. in the 385nm-780nm range).

The SHG and THG should appear at the half and at the third of the excitation wavelength, respectively. For temperature-resolved SHG measurements, the sample was placed in a computer controlled Heating-Cooling stage (Linkam THMS-600) having a 100ohm platinum resistor sensor DIN 1/10 th (maximum temperature deviation of 0.07°C in the 70°C-80°C range). The calibration of the Linkam was check by comparing melting temperature obtained by DSC and by the Linkam and was estimated at +/-1°C A coverslide was placed on the top of the sample and gently pressed on it.

Differential Scanning Calorimetry (DSC)

Thermal analyses were conducted in a DSC 214 Netzsch equipped with an intra-cooler. The sample was placed in a 25-mL closed aluminum crucible. The atmosphere during the measurements was regulated by nitrogen flux (50mLmin -1 ), and heating runs were conducted under conditions similar to those of the TR-SHG measurements in order to compare the results. Data treatment was performed with a Netzsch Proteus V.6.1

Ultra-purification of Phenanthrene

Different chemical grades (90% and 98%) of phenanthrene were purchased from Alfa Aesar. Ultrapure phenanthrene was obtained from 98% batch by combining different techniques as (i) Classical crystallization procedures (recrystallization in solution or from the melt), (ii) selective formation of co-crystals, (iii) selective chemical modification followed by a cocrystallization step, (iv) sublimation. In these work these pathways have been explored and a 99.999 mol.% ultimate purity of Phenanthrene has been achieved. Single-crystals of phenanthrene was finally obtained by last sublimation operation. The mass of on typical single-crystal was estimated at circa 10µg.

Results and discussion

Effect of purification

In order to check the SHG efficiency of the phenanthrene, emission spectra of different phenanthrene grades (i.e. 90%, 98% and 99.999%) were recorded and are shown in Fig. 1.

One can notice for all different grades, a sharp peak at 450 nm corresponding to the SHG signal (half of 900 nm excitation wavelength). Interestingly, both 90% and 98% grade exhibit emission spectra typical to fluorescence spectra but not for 99.999% grade. This behavior is probably closely related to the presence of impurities in phenanthrene although the emission spectra do not fit the emission spectra of the main impurities of phenanthrene (i.e. carbazole, dibenzothiophene, fluorene). One can recall that phenanthrene has the ability to form solid solutions with its impurities, consequently, the explanation for these particular emission spectra could be due to specific interactions in the solid state. This results point out the extreme sensitivity of confocal microscopy and the necessity to systematically check the purity of samples prior to experiments.

Fig. 1 Emission spectra of different phenanthrene grade for excitation wavelength at 900nm (left) and zoom in (right). The peak at 450 nm correspond to the Second harmonic emission.

3.2

Temperature resolved Second harmonic generation.

The phenanthrene has a propensity to sublimate. The sublimated sample could then recrystallized (from vapor) on the different optical elements (principally the fuse silica window of the heating/cooling stage). This could create unpredictable intensity fluctuation of the laser intensity arriving on the sample and misinterpretations. To limit such problems, and prior to TR-SHG experiment, the analyzed sample amount was reduced and a cover slide was place on the top of the sample to limit diffusion of molecules. For instance, for experiments concerning the ultrapure phenanthrene, a single-crystal of circa 10 µg was used. The evolution of SHG with the temperature at 1K/min was monitored and different curves are presented in Fig. 3. For ultrapure phenanthrene, the signal disappears at 76.2°C (see Erreur ! Source du renvoi introuvable. and Fig. 3) In the historical SHG measurements, a 98% phenanthrene was used and the temperature was circa 72°C. If we assume that the commercial grade purity was similar in the 70's compared to the currently available commercial grade, this temperature is closely related to the DSC peak temperature (72.6°C) that correspond to end of the transition. The temperature of transition of ultrapure phenanthrene found by SHG is much higher and could be due to a better detection threshold of the detector and a spectrally resolved analysis (avoiding misinterpretation). Nevertheless, transition temperature determined by SHG are 65°C and 75.2C for 90% and 98% phenanthrene grades, respectively. This highlights the crucial role of impurities in the phase transition. An increase of the impurities concentration creates a depression of transition point (more than 10°C between 90% and ultrapure grades). The impurities concentration seems not drastically changed the unusual character of the transition observed in the SHG measurements. The LT-form still seems undergoing a progressive transition toward the HT-form. One can also notice the hysteresis in the appearance/disappearance temperature of the SHG signal upon cooling/heating increases with the impurities concentration (0.5°C, 2.8°C and 4°C for the ultrapure, 98% and 90% phenanthrene grades, respectively). In addition to observed peak in DSC, this clearly proves the 1 st order contribution of this transition. Fig. 3(b-d) shows that the SHG intensity on cooling is lower compare to that upon heating. This could be due to stress induce by thermal treatment and solid-solid transition in the crystals. In addition, for temperature cycle experiment the SHG intensity upon cooling is (i) higher if the temperature of transition is not exceeded (e.g. cycle from 50°C to 65°C), (ii) lower if the temperature of transition is exceeded. Further investigations are in progress to understand such behavior.

Conclusion

The solid-solid transition of phenanthrene sample of different purity grades was investigated by means of SHG-M. Influence of impurities was highlighted. The impurity concentration do not change the progressive transition from the LT to the HT form observed in SHG but has drastic influence on the temperature of transition and hysteresis. Further investigations are in progress to understand the behavior observed during temperature cycles.

Fig. 2

 2 Fig. 2 SHG-M pictures upon heating of ultrapure phenanthrene single-crystal.

Aknowledgment

This work has been funded by Region Normandie and the European Regional Development Fund (FEDER-FSE Normandie 2014-2020) through the project SCAMPI