Ana Rosa Cavalli
email: ana.cavalli@it-sudparis.eu

Azzedine Benameur
email: azzedine.benameur@sap.com

Wissam Mallouli
email: wissam.mallouli@montimage.com

Keqin Li
email: keqin.li@sap.com

A Passive Testing Approach for Security Checking and its Practical Usage for Web Services Monitoring *

Keywords: Web Services, Passive Testing, Security Checking, Nomad Formal Language

To achieve a meaningful business goal, Web services are combined and connected together based on a predefined workflow. In this distributed configuration, tasks are executed by different entities usually managed by different business partners which makes the security monitoring of the whole business process complex. Indeed, the application of classical monitoring methods is not suitable in this kind of service oriented architecture (SOA) where execution traces collection is generally distributed and security requirements implicate several Web services. In this paper we propose a passive testing approach for SOA, encompassing a non-intrusive module that gathers selected traces for web services in both cases of centralized and decentralized workflows, and also a passive tester that analyzes the distributed collected traces and deduces a verdict concerning the respect of the Web services to their security requirements. Finally we apply the proposed methodology to a Loan Origination Process using BPEL workflow.

INTRODUCTION

Web service technology is defined by the W3C [START_REF]World Wide Web Consortium[END_REF] as a software system designed to support interoperable machine-to-machine interaction over a network. It provides the possibility to integrate business applications and connect business processes across company boundaries. A business process can then be composed of individual Web services that belong to different companies. In other words, a business process is a network of Web services without any global supervision system. To leverage Service Oriented Architecture (SOA) [START_REF]Oasis standard: Reference model for service oriented architecture v1.0[END_REF], services are connected together to achieve more complex tasks using a workflow specification language [2]. Currently, Business Process Execution Language for Web Service (BPEL4WS, denoted BPEL in the following) [START_REF] Juric | Business Process Execution Language for Web Services BPEL and BPEL4WS 2nd Edition[END_REF] is the de facto standard to describe the interactions of the individual Web service in both abstract and executable ways.

In SOA, communications are made through XML-Based messages called SOAP [START_REF]Simple object access protocol 1.1[END_REF] messages. These communications are distributed and their security requirements implicates several Web services. Thus, ensuring this security in such distributed configuration is challenging. Testing is a mean to provide guarantee that the security properties are holding when the system is implemented.

Formal testing allows to check the respect of the security requirements of a system. It can be either active or passive. Active testing permits to validate a Web service implementation by applying a set of test cases and analyzing its reaction. It implies that we have a global control on the service architecture which is difficult to perform in a dynamic topology in the case of decentralized workflows for instance. Besides, the active testing becomes difficult to perform when the network is built from components (services) that are running in their real environment and cannot be interrupted or disturbed. In this situation, there is a particular interest in passive testing techniques in which traffic flows of deployed Web services are monitored. This testing consists in analyzing collected data according to some functional and security requirements described in a formal specification.

In this paper, we rely on passive testing techniques to study web services in both cases of centralized and decentralized workflows in order to detect any security flaw. Our main contributions are the following: (i) A trace collection mechanism for both centralized and distributed web services. (ii) Formalization of security properties/policies using Nomad formalism. (iii) A detailed implementation of the proposed mechanism (trace collection and passive testing tool). (iv) A running example with security analysis, and selected properties formalized.

The remainder of this paper is organized as follows. In section 2, we discuss the related work tackling with Web services workflows monitoring. Section 3 presents the distributed collection mechanism of the web services traffic in both cases of centralized and decentralized architectures. Section 4 presents the methodology and tool to analyze this global trace by comparing it to the security requirements described in Nomad formal language. In section 5 we apply our methodology on an industrial case study: Loan Origination Process. Section 6 concludes the paper and presents future work.

RELATED WORK

Most of works related to Web services reasoning focus on two related but distinct problems. The first one is the formal description of Web services composition. One of the proposed approaches is to use planning techniques on behavioral models as in [START_REF] Lallali | Automatic timed test case generation for web services composition[END_REF][START_REF] Narayanan | Simulation, verification and automated composition of web services[END_REF][START_REF] Pistore | Automated composition of web services by planning at the knowledge level[END_REF]. For instance, [START_REF] Narayanan | Simulation, verification and automated composition of web services[END_REF] proposes a methodology to specify Web services composition into Petri nets and provides decision procedures for Web service simulation, verification and composition. Other works, such as [START_REF] Pistore | Automated composition of web services by planning at the knowledge level[END_REF], rely on transition rule systems that model the interactions among services at the knowledge level. This allows us to avoid the explosion of the search space due to the usually large and possibly infinite ranges of data values that are exchanged among services. The authors of [START_REF] Lallali | Automatic timed test case generation for web services composition[END_REF] proposes to build the behavioral Web services model by automatically translating existing process descriptions, such as BPEL ones, into timed automata system. This system specification is used later for model-based testing purpose.

The second problem is the property verification on Web services in order to guarantee that deployed applications satisfy a set of requirements and temporal properties (for instance, the absence of deadlocks). It is usually argued, for instance by [START_REF] Salaün | Describing and reasoning on web services using process algebra[END_REF], that existing automated model-checking tools can support these tasks under the condition that components' behavior and their interactions are described by formal models. Web services development reinforces the need of tools to improve their reliability and their security respect. Several works [START_REF] Grosclaude | Model-based monitoring of software components[END_REF][START_REF] Yan | Monitoringweb service networks in a model-based approach[END_REF] tried to deal with the functional behavior of Web services. [START_REF] Grosclaude | Model-based monitoring of software components[END_REF] is devoted to monitoring componentbased software systems whose behavior is modeled using a formalism based on Petri nets. In addition, [START_REF] Yan | Monitoringweb service networks in a model-based approach[END_REF] relies on existing BPEL specifications and examine how to translate them into a transition rule formalism. In this paper, we propose a formal approach to develop a monitoring tool dedicated for Web services workflow security checking. We claim that our methodology is innovative and do not generate any fault positives.

PRELIMINARIES

Background on BPEL Workflow for Web Services

A workflow could be defined as a collection of tasks organized to accomplish some business process [START_REF] Georgakopoulos | An overview of workflow management: From process modeling to workflow automation infrastructure[END_REF]. A task can be performed by one or more software systems (e.g., web services), one or a team of humans, or a combination of these. In addition to a collection of tasks, a workflow defines the order of task invocation or condition(s) under which tasks must be invoked, task synchronization, and information flow (dataflow). Workflow management systems (WFMSs) are used to provide the ability to specify, execute, report on, and dynamically control workflows.

Traditionally, the workflow management and scheduling is carried out by a single centralized workflow management system. This WFMS is responsible for enabling task execution, monitoring workflow status, and guaranteeing task dependencies. However, in an electronic commerce environment with inter-organizational workflows, since the systems are inherently distributed, heterogeneous, and autonomous in nature, decentralized workflow management systems are used.

Therefore with respect to our work, the collection mechanism of execution traces has to work with both the centralized and decentralized architectures.

Centralized Workflow

A typical example of centralized workflow is a business process defined by BPEL4WS [2]. BPEL Business Processes offer the possibility to aggregate web services and define the business logic between each of these service interactions. It is also said that BPEL orchestrates such web service interactions. Each service interaction can be regarded as a communication with a business partner. Such an interaction is potentially two sided: the process invokes the partner and the partner invokes the process.

In BPEL, there exist a couple of simple activities with the purpose of consuming messages from and providing messages to web service partners. These activities are the receive activity, the reply activity and the invoke activity. All these activities allow exchanging messages with external partners (services). At the same time, BPEL provides means to structure the business logic according to business needs, using sequence activity, if-else activity, repetitive activities, etc.

From the trace collection point of view, each service (business partner) can have a local view of execution information (e.g., SOAP message exchange) related to the business process, and the orchestrator, i.e., the BPEL engine, has a global view.

Decentralized Workflow

From a system point of view, the collaborating enterprises constitute an autonomous decentralized system since they pursue a common goal as a whole but each of them is highly independent. The features of this kind of collaboration are as follows:

• On the one hand, it is required that business processes of collaborating partners should be integrated seamlessly in order to ensure high operation efficiency;

• On the other hand, it is required that only necessary information should be exchanged across organizational boundaries. The internal structures of the business process should remain as black-box because the technical know-how and commercial secrets of a company are embedded in its business processes.

Therefore, integrated business process management of this loosely coupled and dynamically changed partnership does not require a centralized business process model that will be shared and maintained by all collaborating partners. Instead, it is required that business processes of an enterprise are designed, implemented and managed by the enterprise itself. The function as well as the monitoring and control of a business process is wrapped as externally accessible service, which will be integrated with the business processes of the collaborating enterprises on demand as well as on the fly. In summary, business processes are modeled and executed in a decentralized manner.

Correspondingly, several decentralized workflow management systems are proposed, such as [START_REF] Atluri | A chinese wall security model for decentralized workflow systems[END_REF] and [START_REF] Montagut | The pervasive workflow: a decentralized workflow system supporting long running transactions[END_REF].

From the trace collection point of view, in such an architecture, no single workflow management agent has the global view of the workflow. The distributed pieces of execution information of the workflow need to be correlated to obtain a global picture.

Security Rules Specification for BPEL

To formally specify security properties that the BPEL-based workflow has to respect, we rely on an interpretation of Nomad language [START_REF] Cuppens | Nomad: A Security Model with Non Atomic Actions and Deadlines[END_REF]. Nomad stands for 'Non Atomic Actions and Deadlines' model. It allows to express privileges on non atomic actions or tasks performed within a workflow. It combines deontic and tempo-ral logics and can describe conditional 1 privileges and obligations with deadlines. The main features of Nomad model are to provide means to specify:

• Privileges (permission, prohibition or obligation) associated with non atomic actions/tasks.

• Conditional privileges, which are privileges only triggered when specific conditions are satisfied.

• Privileges that must be fulfilled before some specific deadlines.

Nomad formal model is designed to regulate the nature and the context of tasks that can be performed within different systems or organizations workflow. Intended to be generic, Nomad do not formally define any atomic action it can rely on, so that it can be applied to case studies with different characteristics. In this paper, we instantiate Nomad to fulfill passive testing aspects and we define then an atomic action as the occurrence of an event within the studied system workflow. This event (emission or reception of a message between two system components) can be detected by the trace collection unit and is stored in a log file. Some constraints on message parameters values are also considered in the action syntax description:

Event (Par1 op Val1, Par2 op Val2, ..

. , Parn op Valn)

Where:

• Event represents a message exchanged between two system entities.

• P ari (i ∈ {1, ... , n} are the message parameters. These parameters represent the relevant fields in the message (n is the number of these relevant message fields). Some of these parameters are always considered, such as the message type, the sender identifier (IP address) and the destination identifier (IP address).

• V ali (i ∈ {1, ... , n}) are the possible parameters values.

• op is an operator that allows to compare Pari and Vali. op ∈ {=, =, <, >, ≤, ≥, }.

DEFINITION 1. (Abstention of doing an action) If

A is an action that can be performed within a system S, then not(A) (which means "the non occurrence of A") is an action.

DEFINITION 2. (Non-atomic action)

If A and B are actions that can be performed within a system S, then (A; * ; B) (which means "A followed by B"), (A; B) (which means "A followed immediately by B") and (A&B) (which means "A in parallel with B") are non-atomic actions.

DEFINITION 3. (Formula)

If A is an action then start(A) (A is being started), doing(A) (A is being performed) and done(A) (A has been finished) are formula.

DEFINITION 4. (Formula)

• If α and β are formula then ¬α, (α ∧ β), (α ∨ β), (α → β) and (α ↔ β) are formula.

1 Most privileges do not apply unconditionally. Thus, we need to model privileges that are only active in specific contexts.

• If α is a formulae then ⊕ n α (in the n next messages/events in the trace, α will be true) and n α (in the n previous messages/events in the trace, α was true) are formula.

For instance, if we are in the event number 'nb', ⊕ n α means that α will be true for a certain event i such as (nb < i < nb + n + 1). While, n α means that α was true for a certain event i such as (nb -n -1 < i < nb).

• If α is a formulae then O d α (α was true d units of time ago if d ≤ 0, α will be true after d units of time if d ≥ 0) is a formulae.

• If α is a formulae then O <d α (within d units of time ago, α was eventually true if d ≤ 0, α is eventually true within a delay of d units of time if d ≥ 0) is a formulae.

• If α is a formulae then <d α is formula. <d α is to be read α will be true (if d ≥ 0) or was true (if d≤0) during d units of time.

• If α and γ are a formula, then (α|γ) is a formulae: in the context γ, the formulae α is true.

DEFINITION 5. (More details)

• If n = 1, then ⊕ 1 α can be denoted ⊕α and means: immediately in the next event in the trace, α will be true.

• If n = 1, then 1 α can be denoted α and means: immediately in the previous event in the trace, α was true.

• If n = ∞, then ⊕ ∞ α means: at certain point in the future in the trace, α will be true.

• If n = ∞, then ∞ α means: at certain point in the past in the trace, α was true.

Notice that using Nomad formalism, we deal with a discrete time. The choice of the unit of time can be very important and depends on the studied system. DEFINITION 6. (Temporal modalities) If α is a formulae then α (α is necessary) and ♦α (α is possible) are formula.

DEFINITION 7. (Deontic modalities)

If α is a formulae then modality P(α) (α is permitted), F(α) (α is forbidden) and O(α) (α is mandatory) are formula.

DEFINITION 8. (A security rule)

We define a security rule as a formulae with the following format: R (α|β) where R ∈ {P,F,O} and α and β are formula. P (α|β) (resp. F (α|β), O (α|β)) means that it is permitted (resp. prohibited, mandatory) to have α true when context β holds.

TRACE COLLECTION MECHANISM FOR SOA

Web services can be seen as black-box, where only the interfaces and input/output parameters are known. The communication is made through SOAP messages where these interfaces are called and parameters are sent.

In general, to collect execution traces on a running system, we need to install observation points (called also probes) into specific strategic points. These observations points aim to collect data exchanged between relevant entities. The collected traces are usually stored in one or many trace files depending on if we are dealing The architecture of our trace collection module is depicted in Figure 1. The module is placed at each workflow engine layer. It logs selected elements of a SOAP message, which are defined in the logging policy file. In the case of centralized workflow, all the message exchanges are handled by the BPEL workflow engine and only a trace collection module is needed. Table 1 gives an example on how the logging policy is expressed. Each service is identified by its namespace, the name of the XML element follows. The first audit rule depicted is to select the content of the node < username > from a web service identified by the namespace http : //ws1.com and to select the same node from another web service identified by the namespace http : //ws2.com which is distinct from the first one.

The second audit rule specifies to log the content of the node < LoanRequest > from a web service identified by the namespace http : //ws1.com and to select all the nodes (using * ) from the web service identified by the namespace http : //ws3.com. For readability we use two rules but they can be expressed in one line using the spacing separator. The policy can also be expressed using de facto standards such as Xpath.

PASSIVE TESTING METHODOLOGY

Preliminaries

Our passive testing methodology for security checking is divided into three main steps:

• The definition of passive testing architecture: This architecture depends on the nature of the workflow. Collection modules are placed at each workflow engine layer. The traces files are then merged (based on each event timestamp) into one file that describes all the exchanged messages within the whole system. Notice that in the case of a centralized workflow, only one file is generated from the beginning.

• The description of the system security requirements using a formal specification language: the description concerns the security rules that the studied system has to respect. We rely in this paper on Nomad language introduced in section 3.2. This can be done by an expert of the Web service under test that understands in details its security requirements.

Audit • The security analysis: based on the security policy specification, the passive tester has to perform security analysis on the global trace file to deduce a global verdict. This verdict is PASS if the system trace respects the specified security policy and FAIL if it does not. The INCONCLUSIVE verdict is possible if the tester can not extract the necessary information from the collected traces in the case of a short trace for example. If the trace is long enough (or if the traffic collection is continuous), we can claim that it describes the global behavior of the system and consequently the verdict concerns the system conformance according to its security policy.

Passive Testing Tool

To automate the process of scanning the captured traces in order to detect possible violations of security rules, we rely on a passive testing tool developed by Montimage. A high level description of this tool is given in Figure 2. This tool allows automated analysis of the captured traces to determine if the given Nomad security rules are satisfied or not. It takes as input three different files:

• The system security rules defined/described in Nomad formal language and written in XML format.

• The traces captured by the collection module.

• And information on the Web Service that is being observed. This information represents data of interest (mainly event fields' names) that are relevant to the automated analysis of the captured traces. It indicates the fields of interest (defined also in the logging policy file) so that only these are extracted and stored by the tool.

In order to use the tool, first the security rules and the data of interest need to be defined. This is performed by an expert of the Web service. Then, the security rules are written in XML format (see Figure 3) to make them easier to be interpreted by humans and software.

The context part of the rule is denoted by an <if> tag that identifies the triggering event. An event is a set of conditions that need to be satisfied for a given message exchange. When analyzing a security rule, we have the triggering event, called 'reference' event, and the other events, called 'current' events, that should occur before or after the triggering event (depending on the rule). The events that need to be verified on the 'current' events are found in the <then> tag. Conditions are of the form:

(<variable>)(<operation>)(<variable> | <value>)
meaning that a <condition> compares a <variable> to <value> or another <variable> through an <operation>. Variables can refer to the 'reference' event or the 'current' event. This allows comparing the two. Values can be strings or numbers and operations can be: contains, is equal to, does not contain, is different than, is less than, is less than or equal to, etc.

The second step is to parse the captured trace to analyze it according to these security rules. The verdict obtained for a security rule can be either PASS, FAIL or INCONCLUSIVE meaning respectively that all events where satisfied, that at least one event was not satisfied or that it is not possible to give a verdict due to the lack of information in the trace.

CASE STUDY: LOAN ORIGINATION PRO-CESS 6.1 Introduction

The Loan Origination Process (LOP) describes a customer wanting to buy a bundled product. Several external and internal ratings need to be obtained by the processing clerk in order to check the credit worthiness of the customer (internal rating, Credit Bureau). Once the credit worthiness of the customer has been positively established, the bank selects a bundled product and submits it to the customer. If the customer is satisfied by the proposed product, both parties come to an agreement and sign a contract.

Figure 4 illustrates the different steps of the scenario, with the actors and the roles involved. After the customer makes a loan request:

• (1) His identity is checked by the pre-processing clerk. Then, two parallel rating engines start and the customer worthiness is establish by two separate entities. • (3) The internal rating checks the customer worthiness with regards to his history in the bank. In case of negative result, the manager can intervene.

• (4) The bank calculates the price of the loan using the bank Internal Computer System

• (5) The bank and the customer come to an agreement.

This case study in a banking context is very interesting from the security and privacy point of view. It involves different organizations dislocated geographically and organizationally which implies that some properties can be satisfied locally and no necessary hold on the global workflow.

Architecture and Implementation

The implementation of the scenario is based on the Service Oriented Architecture paradigm [START_REF]Oasis standard: Reference model for service oriented architecture v1.0[END_REF]. We assign several services to the different entities: front office, back office, back office of the manager. So far, we have implemented a simplified version of a workflow having excluded a manager approval task.

• The front office is in charge of identifying the customer, storing the loan request and finalizing the contract. These func-tions are performed respectively by the following Web services: 'WS Authentication', 'WS Store Loan' and 'WS Loan Calculation'.

• The risk assessment is done by a parallel invocation of the bank internal rating engine and a third party represented by WS Internal Rating and WS External Rating.

• The back office is modeled as an interface of the WS Calculation Offer.

The logical architecture of the LOP implementation is depicted in figure 5. Four layers are needed to fully decouple the business logic from the functional implementation. A database layer makes a clear separation between the database of the bank computing the internal rating, and the credit bureau database providing an external assessment. The Rules layer enables decoupling of the business rules from the code in such a way that if regulations (or practices) of the partner evolve, the only layer to update is the rules layer. The Web service layer is complemented by the orchestration layer that contains the BPEL specification of the process that is interpreted by a WFMS. The latter describes how web services works together and on which interface.

Security Analysis

We want to check several security properties that the LOP process has to respect. The first step consists in formalizing them using Nomad formal language:

1. (Security Rule 1) Separation of duty: between the pre and the post processing clerks. The loan processing is divided into two main phases: pre-processing and post-processing.

To avoid frauds the pre-processing clerk should not be the same employee as the post-processing clerk. where user = "http-8080-Processor"+"i" and i ∈ {1,...,30}

2. (Security Rule 2) Authentication: to ensure that the user is authenticated before executing the workflow. The employee should be authenticated before performing any operation. In the LOP, this is obtained by contacting a Security Token Service which issues a security token to the service client. The service client contacts the web service with the provided token and the service can decide whether the client is a trusted entity or not. where user = "http-8080-Processor"+"i" (i ∈ {1,...,30}) and Any ∈ {WSLoanStorage, WSInternalRating, WSCredit-Bureau, WSLoanCalculation, WSWFTerminator } 3. (Security Rule 3) Deny of service attack avoidance: if a same clerk/cus-tomer has more than 3 loan requests within the same minute, we consider him/her as a potential malicious clerk/customer and we might want to investigate later. where user1 = "http-8080-Processor"+"i" (i ∈ {1,...,30}), user2 = "http-8080-Processor"+"j" (j ∈ {1,...,30}) and i = j.

Trace Collection

In order to be able to check the properties expressed in 6.3. We first identify the web services involved, and then the elements contained in the SOAP message that will be required to use passive testing. The trace collection policy depicted in table 2 is based on the following reasoning.

• Separation of Duty: the pre-processing clerk identifies him self on WS Authentication, and then the release of the loan is done by the post-processing clerk on WS Store Loan. The XML schema for these messages contains a tag element < employeeN ame >. Therefore the audit rules for this properties will log the element < EmployeeN ame > from the two namespaces respectively belonging to WS Authentication and WS Store Loan. (see audit rules 1 and 2)

• Authentication: Each workflow instance has a unique ID. We need to check that for any given workflow ID there is a respective successfully message exchange with WS Authentication. The audit rule 3 expresses that we have to log messages from all the services (namespace=http://*) that contain the LoanID element. Then, we use audit rule 4 that allows to verify that the authentication is ok.

• Deny of service attack avoidance: each loan request has a unique number and is associated to a pre and post processing clerk. We here use the complete execution trace over multiple workflow instances and the elements < LoanID >, < EmployeeN ame >. (see audit rules 5 and 6)

In figure 6 presents some trace lines which show the brokered authentication mechanism.

Passive Testing Results

The security rules described in Section 6.3 were evaluated in the traces provided by SAP obtained from the point of observation depicted in the Figure 1. The security rules are defined using the XML format supported by the passive testing tool (see figure 8 for the first Nomad security rule), defining the types of events to inspect and evaluate in the trace. This file, in conjunction with the trace file, where provided as input for the passive testing tool.

The verdicts obtained were PASSED for all the security rules, except for three cases where the security rule number 2 was applied (2 INCONCLUSIVE verdict and one FAIL verdict) and for four cases where the security rule number 4 was applied taking into account a 10 minutes timeout value (FAIL verdict). A more detailed review of the tool output showed that the FAILED results of the fourth rule actually correspond to false positive verdicts and correct events in the trace were detected as errors by the experiment. Indeed, a mistake was embedded in the XML design of the security rule where the timeout was assigned to 100 seconds and not 10 minutes.

The results obtained with the second security rule shows the difficulty, in some cases, of applying passive testing techniques to an application such as the LOP process. Indeed, at the beginning of the captured trace, some operations are performed and the authentication of users is not logged (but perhaps this authentication is done before the beginning of the trace capture). This indicates that the definition of the security rule is not sufficiently precise to be relevant in the case of too short traces that do not provide all the needed data information.

Notice also that the security rule number three was never applied in the collected trace since no malicious was acting during the trace capture.

In general the results of the experimentation showed that the techniques used worked correctly on the captured traces and the approach is suitable for applying on Web services such as the LOP process.

CONCLUSIONS AND FUTURE WORK

Passive testing has shown to be well adapted to test systems, or components, which are in operation in their real environment and cannot be interrupted or disturbed. In this paper, we presented a passive testing approach and its application for security checking of web services based on the SOA architecture. In particular, the passive testing is applied to a case study, the LOAN Origination Process using BPEL workflow. The security properties have been described using the Nomad language, well adapted to describe permission, prohibition and obligations and includes time constraints. The security properties to be evaluated have been provided by SAP and their evaluation has been carried out using a passive testing tool developed by Montimage. The implementation of the Loan Origination Process has also been provided by SAP.

Several experiments have been performed on the service implementation. The application of these techniques showed that passive testing techniques can be applied to industrial cases studies to help improve the reliability of the proposed services and that the techniques and tools are scalable.

As future work, we plan to explore and evaluate new types of security rules in this framework. The XML representation of the Nomad security rules need also to be refined to be able to express and test more complex security rules. Regarding the passive testing tool, we plan to adapt it to be able to analyze SOAP packets online. This will also allow the tool to be used to detect that the protocol exchanges occur as expected during the operation of the Web service.

ADDITIONAL AUTHORS

No additional authors.

Figure 1 :

 1 Figure 1: Trace Collection Module

Figure 2 :

 2 Figure 2: Passive Testing Tool

Figure 3 :

 3 Figure 3: XML Format for Defining a Nomad Security Rule

Figure 4 :

 4 Figure 4: Loan Origination Process Workflow

Figure 5 :

 5 Figure 5: Layered Implementation Achitecture of The Loan Origination Process Workflow

F

  (start(Event(EventT ype = calculateLoan, P rocessor = user))| ∞ done(Event(EventT ype = storeLoan, P rocessor = user)))

F

  (start(Event(EventT ype = Any, P rocessor = user))| ¬ ∞ done(Event(EventT ype = W SAuthentication, P rocessor = user)))

F

  (start(Event(EventT ype = W SLoanRequest, P rocessor = user))| O <-1min done(Event(EventT ype = W SLoanRequest, P rocessor = user)); * ; Event(EventT ype = W SLoanRequest, P rocessor = user)); * ; Event(EventT ype = W SLoanRequest, P rocessor = user))) where user = "http-8080-Processor"+"i" and i ∈ {1,...,30} 4. (Security Rule 4) Timeout property: calculateLoan should be called within 10 minutes after storeLoan is called. P(start(Event(EventT ype = calculateLoan, P rocessor = user 1 ))|O <-10min done(Event(EventT ype = storeLoan, P rocessor = user 2 )))

Figure 7 :

 7 Figure 7: XML Format for The First Nomad Security Rule

  Audit rule 1 logN odList = http : //authentication.ws.ebusiness.prototype.serenity .crnce.sap.com | EmployeeN ame Audit rule 2 http : //loanstorage.ws.ebusiness.prototype.serenity .crnce.sap.com | EmployeeN ame Audit rule 3 logN odList = http : // * | LoanID Audit rule 4 logN odList = http : //authentication.ws.ebusiness.prototype.serenity .crnce.sap.com | ClientSSN Audit rule 5 logN odList = http : //authentication.ws.ebusiness.prototype.serenity .crnce.sap.com | EmployeeN ame Audit rule 6 logN odList = http : //authentication.ws.ebusiness.prototype.serenity .crnce.sap.com | LoanID

	Table 2: Trace Collection Policy
	2008-10-28 16:25:23,812 [http-8080-Processor18]
	INFO com.sap.crnce.serenity.patterns.security.
	a2.logging.SecureLogHandler -SecureLoggingMod
	ule: http request from Address: 127.0.0.1 to Ad
	dress: http://localhost:8080/axis2/services/Sec
	urityTokenService
	2008-10-28 16:25:23,812 [http-8080-Processor18]
	INFO com.sap.crnce.serenity.patterns.security.
	a2.logging.SecureLogHandler -SecureLoggingMod
	ule: action performed -> http://schemas.xmlsoap
	.org/ws/2005/02/trust/RST/Issue
	(...)
	2008-10-28 16:25:27,046 [http-8080-Processor16]
	INFO com.sap.crnce.serenity.patterns.security.
	a2.logging.SecureLogHandler -SecureLoggingMod
	ule: http request from Address: 127.0.0.1 to Ad
	dress: http://localhost:8080/axis2/services/WSA
	uthentication
	2008-10-28 16:25:27,046 [http-8080-Processor16]
	INFO com.sap.crnce.serenity.patterns.security.
	a2.logging.SecureLogHandler -SecureLoggingMod
	ule: action performed -> urn:AuthenticateClient
	(...)
	Figure 6: Example of Captured Traces for LOP Process

The research leading to these results has received funding from the European Community Seventh Framework Programme (FP7/2007-2013) under grant agreement no 215995.


Eva Coupeté

Vincent Weistroffer

Olivier Hugues

Fabien Moutarde

Sotiris Manitsaris

Philippe Fuchs

New Challenges for Human-Robot Collaboration in an Industrial Context: Acceptability and Natural Collaboration

In this paper, we focus on two challenges to enable human-robot collaboration in factories. The first challenge is to evaluate the acceptability of an operator to work with a robot on a new collaborative task. Comparing physical and virtual situation, we highlight notions related to acceptability which can be evaluated using virtual reality. This will able us to evaluate future collaborative scenarios before their setting-up on supply chains.

The second challenge is to provide a natural collaboration between the robot and the operator. We chose to study gesture recognition to enable a smooth collaboration. With this method, the robot should be able to understand its environment, adapt its speed and be synchronized with the operator.

We used two use cases to test our frameworks, to evaluate them and to highlight possible improvements.

I. INTRODUCTION

The development of robots has been common in our society, and also in our industries. Social robots have already been useful in various contexts: guide in museum, stimulation for autistic children or assistant for elderly people for example. In an industrial context, robots are also present. Until a few years ago, industrial robots evolved in specific areas, away from operators. Nowadays, collaborative industrial robots are progressively incorporated in supply chains. These robots are used to help the operator with complementary skills (strength, precision,..). Operator and robot can work side by side on different tasks, i.e. in copresence, or on a common task, i.e. in collaboration.

Interaction between operators and industrial collaborative robots raise new questions about human-robot interaction. The first one is to ensure the operator security. When the industrial robots were in closed areas, any intrusion in these parts of the supply chain automatically stopped the robots. This option is no longer available in the context of a humanrobot interaction. During the past years, new technologies provided ways to make the robot understand its environment. Depth-cameras, laser sensors, and inbuilt sensors, like force sensors or tactile sensors, enable robots to be safe and to be able to react accordingly if there is a contact with an operator. vincent.weistroffer@cea.fr A second question is acceptability. Will operators, who were taught to stay away from robot, accept to work every day with a robot as a co-worker? The question of acceptability has been well studied in the case of social robots were communication can occur between a robot and a human. In industrial context, the question is different: the kind of robots and the interaction modes are different. To evaluate the acceptability, some factors can be common (robot appearance or movement), but other can be specific of the industrial context (spatial or temporal distribution).

A third question is about the collaboration, how to make it natural? By natural, we mean a smooth and efficient collaboration. The robot needs to adapt its speed and to respond fluidly to the operator needs at the appropriate time.

In this paper, we present frameworks to answer the two last questions. The organization of the paper is the following. In Section II, we present related work on human-robot collaboration in the industry. In Section III, we describe two use cases we used in our study. In Section IV, we focus on the framework to evaluate the acceptability using virtual reality. In Section V, we present our method to enable a natural collaboration using gesture recognition. Finally, we provide a conclusion and perspectives in Section VI.

II. RELATED WORK

Human-robot interaction is becoming more and more present in our everyday life. Social robots are already used to help elderly people [START_REF] Vincze | Towards a Robot for Supporting Older People to Stay Longer Inde-pendent at Home[END_REF] or to guide visitors in a museum [START_REF] Thrun | MINERVA: A second-generation museum tour-guide robot[END_REF]. But human-robot collaboration implies more interaction by reaching a common goal [START_REF] Bauer | Human-robot collaboration: a survey[END_REF]. An efficient collaboration can be made by coordinate the participants actions in time and space [START_REF] Vesper | How to support action prediction: Evidence from human coordination tasks[END_REF]. Preferences and needs of the human can be taking into account while a robot is performing its tasks [START_REF] Alami | Task planning for human-robot interaction[END_REF].

In factories, new collaborative robots are designed to be intrinsicly safe and to provide complementary skills to human co-workers like the Kuka LWR [START_REF]Kuka Robotics[END_REF] and the Universal Robot UR [START_REF]Universal Robot UR[END_REF]. Robot apparence [START_REF] Hinds | Whose Job Is It Anyway? A Study of Human-Robot Interaction in a Collaborative Task[END_REF], manipluator's movments [START_REF] Zanchettin | Acceptability of robotic manipulators in shared working environments through human-like redundancy resolution[END_REF] or different robot arms and movement profiles [START_REF] Weistroffer | A methodology to assess the acceptability of human-robot collaboration using virtual reality[END_REF] have been studied to see if they have an impact on the acceptability of human-robot collaboration.

Simple task sharing between a robot and an operator have also been studied, like holding the same table [START_REF] Wojtara | Human-robot collaboration in precise positioning of a three-dimensional object[END_REF], but in most the majority of the cases the robot is working alone on low added value tasks [START_REF] Fitzgerald | Developing baxter[END_REF]. Smooth collaboration is still a challenge to enable an expension of these collaborative robots in factories.

III. USE-CASES

In this Section, we will present two use-cases: a copresence scenario and a collaborative scenario.

A. Use case 1: Scenario of copresence

For this use case, the operator and the robot work side by side, sharing the same area, but working on different tasks. This use case is inspired from concrete operations on car doors. The robot role on the door is to fix a sealing sheet on the door. To do this, it applies a caster on the edge of the sheet to stick it definitively. In car plants, this operation is currently done by a human but it can lead to muskuloskeletal disorders, especially on the wrist of the operator. That is why a robot was chosen to perform this task while operators are concentrated on other operations next to the robot, see Fig. 1.

B. Use case 2: Scenario of collaboration

For this use case, the operator and the robot are working on a common task, in collaboration. The task is inspired from the assembly of motor hoses on supply chain. Presently, the assembly process of motor hoses has some drawbacks: the worker has to find the appropriate parts of the motor hoses among other motor parts, which is a lack of time and increase the cognitive load of the worker. In this collaborative scenario, the robot is giving the appropriate piece to the operator. The assembly of motor hoses requires the worker to take two hose parts respectively on left and right side, join them, screw them, take a third part from left, join it, screw it, and finally place the mounted motor hose in a box. The actions performed by the robot are giving a piece with the right claw and giving a piece in the left claw. The operator and the robot are facing each other and are separated by a preparation table, see Fig. 2.

IV. AXIS 1: DEFINING THE CONDITION OF ACCEPTABILITY USING VIRTUAL REALITY

A. Protocole

We want to know how a human-robot interaction can be accepted by an operator. Many parameters have to be evaluated; virtual reality can be an interesting tool to perform tests on new human-robot interaction configurations. We Fig. 2. Use-case to study a human robot collaboration want to establish which notions, related to acceptability, can be evaluated in virtual situation.

For both use cases presented below in Section III we created a similar virtual environment, see Fig. 3 and Fig. 4. User studies have been performed to gather subjective impressions through questionnaires and more objective measures were taken thanks to physiological measures, both in physical and virtual environment. The results of this study will be used to test, in a virual environnemnt, futur industrial human-robot collaboration scenarios.

B. Use case 1

The aim of this study is to gather operators' subjective impression when working side by side with a collaborative robot. We compared different proximity configurations: one far and one close. On each configuration, operators had to complete 4 cycles of 4 doors, both in virtual and physical environment. Physiological measures to gather information on stress and physical effort were taken at the end of each cycle. Questionnaires were asked at the end of each configuration to evaluate several notions : usability, safety, robot skills, impression and acceptability. Globally the far configuration has been preferred to the close configuration. Through the questionnaires, operators found that the far configuration is more usable, safer and more acceptable.

The same trend can be observed in both physical and virtual environment. The operator's subject impressions can be correlated in both situations. But, in the virtual environnemnt, operators felt less constraints and less physical effort. Also, the virtual robot was more accepted that the real one.

C. Use case 2

With this study, we wanted to compare different levels of interaction with the robot. We used three scenarios with increasing interaction. For the first scenario, the robot puts the motor pieces on the table where the operator can grab them. On the second scenario, the robot gives directly the pieces to the operators. And finally, in the third scenario, with more interaction, the robot maintains the main part while the operator assembles the other parts and screws them. For each scenario, two configurations were designed: a manual configuration and an automatic configuration. For the manual configuration, the operator uses buttons to indicate to the robot to do the next action (to free a piece from its claws, or to change the orientation of the main part for the third scenario). In the automatic configuration, there is no more buttons, an external person pressed the buttons to simulate a smooth interaction where the robot reacts accordingly the operators' actions. On each combination of configuration (manual and automatic) and scenario, the operators had to complete 3 cycles of assembly.

Like for the first use case, we used questionnaires and physiological measures. Questionnaires were asked after each configuration, while physiological measures were taken after each cycle. For this use case, a good correlation was found between the physical and virtual results. With the increase of interaction, the physical effort of the operator decreased. Moreover, the operator preferred the automatic configuration than the manual configuration. Indeed, removing the buttons decreased the cognitive load of the worker during the task and allowed a smooth collaboration.

D. Conclusion Axis 1

A good correlation has been found on the notions of usability, perceived utility and perceived efficiency of a humanrobot collaboration system in virtual and physical situations. For hedonist components of acceptability (perceived safety, perceived relaxation and satisfaction) the results from the questionnaires were correlated while a gap was found for the skin conduction level in physical and virtual situations. The users seem less sensitive to stress in a virtual environment.

Virtual reality appears to be an efficient tool to perform user studies on acceptability on human-robot collaboration when dealing with subjective notions. Moreover, the results of the second use case show that operators prefered an automatic situation rather pressing on buttons, because the collaboration was smoother. This highlights the need for robots to be more intelligent and to be able to understand their environment.

V. AXIS 2: INTELLIGENT ROBOT WITH PERCEPTION TO UNDERSTAND ITS ENVIRONNEMNT

We investigate the recognition of technical gestures performed by the operator to enable a smooth collaboration between the robot and the operator. With gesture recognition, the robot can understand which task is being performed, can anticipate on a future task and adapt its speed. Furthermore, during the study described subsection in IV-C, the operators expressed a preference for the automatic mode, where the robot automatically reacts to the worker action.

A. Use case 1

On the use case of copresence, we used inertial sensors carried by the operators. We determined a set of gestures to be recognized and we tested two types of sensors: a jacket equipped of 12 inertial sensors located at the operator joints, and a set of two sensors affixed to each of the operator hands. Both these technologies are unaffected by occlusions and they provide a rotational representation of the gestures. The 4 gestures we want to recognize are: to remove a protective paper on the sealing shit, to fit on door the sealing sheet, to pre-fix the sealing sheet on the door and to fit the window sealing strip. These gestures are illustrated in Fig. 5. We obtain 96% of correct recognition using the jacket and 86% of correct recognition using the set of two sensors. Even if these results are good, we observed that the inertial sensors could disturb the operators during their task performance, non-intrusive sensors should be prefered for an industrial context.

B. Use case 2

On the use case of collaboration, we decided to use nonintrusive sensors to prevent the operator to be hindered by additional equipment. We used a depth camera with a top view to minimize the possible hands occlusions while the operator is performing his assembly task. We also equipped the tools with inertial sensors, the screwing gun in this use case. We chose 5 gestures to recognize: to take a part in the robot right claw, to take a part in the robot left claw, to join two parts together, to screw and to put the final motor hose in a box. These gestures are illustrated Fig. 6.

We process the data from the depth camera by tracking the operator hands in the depth map. Using only data from Fig. 6. Gestures on the collaboration use case the depth camera, we reach 80% of correct recognition, and with late fusion of data from the depth camera and the inertial sensor on the screwing gun we obtain 94% of correct recognition. We implemented this solution on the robot from the second use case. Its claws open automatically when an operator wants to take a piece. This enables smooth and natural human-robot collaboration.

C. Conclusion Axis 2

This two use cases highlighted the challenges to enable natural human-robot collaboration in the industry. The choice of sensors is restricted to prevent any hindrance for the operator. Also, the choice of gestures must be done to efficiently synchronize the robot to the operator. Moreover, the system of gesture recognition should be robust to prevent any false recognition which could lead the robot to a misunderstanding of its environment. However, this method enables smooth human-robot collaboration close to a human-human collaboration, which could help the operator efficiency during his tasks performance.

VI. CONCULSION

In this paper, we presented two frameworks dealing with new challenges for human-robot collaboration in supply chain. These two challenges can be expressed as: will the operator accept to work with a robot as a partner and how to make the collaboration natural?

We first presented two use cases, a co-presence scenario and a collaborative scenario. We used these use cases to evaluate our frameworks.

To evaluate the acceptability of an operator to work with a robot on a new collaborative task, we decided to use virtual reality. Each use case was designed in a physical and in a virtual environment. We compared results, from questionnaires and physiological measures, in both situations. We conclude that virtual reality can be helpful to evaluate subjective notions on acceptability. The conception of a new scenario in a virtual environment, before its installation on supply chain, could enable testing these notions and adapt the new collaborative task to improve the operators' acceptability. Moreover, this work highlights the operators' preference for a smooth collaboration with a robot.

To enable a natural collaboration, we studied technical gesture recognition to help the robot to be synchronized with the operator. We used two types of sensors: inertial sensors held by the operator for the first use case, depth camera and inertial sensors on tools for the second use case.

Gesture recognition with inertial sensor on the operator led to good recognition results, but is too intrusive to be used in an industrial context. With the depth camera, a first step to extract information, hands location, from the depth map is necessary. Using hands locations and data from the inertial sensor on the screwing-gun, we obtained recognition rate equivalent to those obtained on the first use case with the intrusive set-up. However, a more robust system without any false recognition, should be necessary to prevent the robot from any misunderstanding of its environment.

These two frameworks enable us to propose solutions to evaluate the acceptability of an operator on a new collaborative task and to provide a smooth collaboration. Improvement can be made, and new technologies in a near future will certainly lead to new answers for these challenges.

Fig. 1 .

 1 Fig. 1. Use-case to study a human robot copresence

Fig. 3 .

 3 Fig. 3. Physical and virtual environment on the copresence use-case

Fig. 4 .

 4 Fig. 4. Physical and virtual environment on the collaboration use-case

Fig. 5 .

 5 Fig. 5. Gestures on the copresence use case

ACKNOWLEDGMENT

The authors wish to thank the operators who gave their time to participate in the study. This research benefited from the support of the Chair 'PSA Peugeot Citroën -Robotics and Virtual Reality', led by MINES ParisTech and supported by PEUGEOT S.A. The partners of the Chair cannot be held accountable for the content of this paper, which engages the authors' responsibility only


U Tan

O Rabaste

C Adnet

F Arlery

J.-P Ovarlez

Optimization Methods for Solving the Low Autocorrelation Sidelobes Problem

Keywords:

In this paper, a discussion is made on the optimization methods that can solve the low autocorrelation sidelobes problem for polyphase sequences. This paper starts with a description and a comparison of two algorithms that are commonly used in the literature: a stochastic method and a deterministic one (a gradient descent). Then, an alternative method based on the Random Walk Metropolis-Hastings algorithm is proposed, that takes the gradient as a search direction. It provides better results than a steepest descent alone. Finally, this autocorrelation question is handled differently, considering a mismatched filter. We will see that a mismatched filter performs impressively well on optimized sequences.

I. INTRODUCTION

Since 1950, sets of sequences with some properties (autocorrelation, cross-correlation) have been sought. In radar for instance, they are often of interest, because a signal with a "good" autocorrelation property may be distinguished from a time-shifted version of itself, while the cross-correlation property enables a signal to be set apart from another signal.

In terms of radar detection, the autocorrelation function is usually referred to a "matched filter". If the matched filter presents high sidelobes, it may be problematic in the presence of multiple targets. In that case, weak targets can be hidden by a stronger one. Hence, one should find sequences with low autocorrelation sidelobes. This is the objective of this paper.

Searching for those sequences can be seen as an optimization problem, the minimization of a function called "energy". This energy quantifies the autocorrelation sidelobe level of a sequence, like the Merit Factor introduced by Golay [START_REF] Golay | Sieves for low autocorrelation binary sequences[END_REF]. There exists a lot of methods that can provide suboptimal solutions to this optimization problem. Stochastic methods are usually helpful, as no hypothesis on the cost function is required ( [START_REF] Malekzadeh | Intelligent Computing Technology: 8th International Conference, ICIC 2012[END_REF], [START_REF] Liu | Orthogonal polyphase code sets design for mimo radar using tabu search[END_REF], [START_REF] Dam | Polyphase sequence design using a genetic algorithm[END_REF], [START_REF] Deng | Polyphase code design for orthogonal netted radar systems[END_REF]); their convergence to a global minimum is almost certain theoretically. A gradient descent, also known as a steepest descent, is a fast algorithm for finding a local minimum of a function [START_REF] Baden | Efficient energy gradient calculations for binary and polyphase sequences[END_REF]. In this paper, we propose another stochastic method, based on the Metropolis-Hastings algorithm. It generates random variables, but in the descent direction defined by the gradient.

Furthermore, this autocorrelation problem can be handled differently using mismatched filters. A mismatched filter may highly reduce the sidelobe level, at a cost of some SNR (Signal-to-Noise Ratio) loss. As it is possible to obtain numerically the optimal mismatched filter [START_REF] Rabaste | Mismatched filter optimization for radar applications using quadratically constrained quadratic programs[END_REF], we will try to make some connections between the autocorrelation level of a sequence and the gain that can be obtained with the optimal mismatched filter.

This article only deals with polyphase sequences. But it is possible to extend the following procedure for binary sequences (usually referred as "LABS" for Low Autocorrelation Binary Sequence in the literature), and for sets of sequences with "good" autocorrelation and cross-correlation ( [START_REF] Arlery | Efficient gradient method for locally optimizing the periodic/aperiodic ambiguity function[END_REF], [START_REF] Tan | Phase code optimization for coherent mimo radar via a gradient descent[END_REF]).

This paper is organized as follows. Section II describes and compares two algorithms, a random search and a steepest descent, in order to solve the low autocorrelation sequence problem. Section III suggests another algorithm, based on the Metropolis-Hastings algorithm, that combines the two abovementioned ones. The last section studies the efficiency of a mismatched filter on an optimized-or-not sequence.

II. COMPARISON OF TWO OPTIMIZATION METHODS IN THE LOW AUTOCORRELATION SIDELOBES PROBLEM

In order to search for sequences with low autocorrelation sidelobes, the procedure employed in this article is inspired from a recent article (Baden et al. [START_REF] Baden | Efficient energy gradient calculations for binary and polyphase sequences[END_REF]). It is based on a real function, called "energy", that quantifies the energy present in the autocorrelation sidelobes of a given sequence. Hence, this search is equivalent to a minimization problem.

Let us consider a polyphase sequence a of length N and of constant modulus, i.e. a = [a 1 , ..., a N ] T = e j2παi i∈ 1,N . Assume that a i = 0 for i < 1 and i > N .

The discrete aperiodic autocorrelation, denoted by c = a * a, is the sequence:

c m = N i=1 a i a * i+m (-N < m < N ) , (1)
where we note (.) * the complex conjugate operator. By including some weighting w to allow shaping of the sidelobes, and an exponent p ∈ N to control the peak sidelobe, the autocorrelation sidelobe energy E a is defined by:

E a (a) = N -1 m=-N +1 w m (c m c * m ) p . (2)
Finding the minimum of E a , the cost function throughout this paper, is a difficult task. Indeed, it is a non convex problem (because of the constant modulus hypothesis) that must be optimized over a large set of variables (of size equal to the length N of the sequence). Suboptimal approaches are usually considered in the literature: stochastic and deterministic methods.

Hence, in this section, we recall quickly two well-known optimization methods, one from each approach: a random search and a gradient descent [START_REF] Baden | Efficient energy gradient calculations for binary and polyphase sequences[END_REF]. We compare then their performances on the optimization problem mentioned earlier.

The next section will propose an original alternative that mixes some aspects of the two previous-cited methods.

A. Stochastic Methods

Stochastic methods ( [START_REF] Malekzadeh | Intelligent Computing Technology: 8th International Conference, ICIC 2012[END_REF] to [START_REF] Deng | Polyphase code design for orthogonal netted radar systems[END_REF]) are characterized by the presence of randomness in the optimization process. The iterative process can be divided into two steps, specific to each method. A generation step creates candidates by mutation or exploration of the domain. A selection step evaluates these candidates through the cost function. One can notice that the mutation operator is quite sneaky, as the linear combination of two sequences with low autocorrelation sidelobes does not necessarily provide another one with better sidelobes... Common stochastic methods for designing polyphase includes genetic algorithms [START_REF] Dam | Polyphase sequence design using a genetic algorithm[END_REF], evolutionary strategies [START_REF] Deng | Polyphase code design for orthogonal netted radar systems[END_REF], tabu search [START_REF] Liu | Orthogonal polyphase code sets design for mimo radar using tabu search[END_REF], etc.

The principle of a stochastic method is described in the table 1, with the most basic algorithm, the random search. end if 7: until a stop criterion is met Like most methods, stochastic methods have some advantages and some drawbacks. A short list is given below. Advantages

• Stochastic methods can be used to solve every optimization problem, as they don't need any hypothesis on the cost function (smoothness, convexity...). • Their global convergence is almost certain theoretically... Drawbacks • ... but it cannot be established in practice.

• The longer the sequence is, the slower the algorithms are.

B. Gradient Descent

The gradient descent is a fast algorithm for finding a local minimum of a function. It starts with an initial guess of the solution, and as many times as needed, moves it towards the opposite direction of the gradient at that point. Table 2 gives its procedure. Pros and cons of a gradient descent are the following: a = a -γ∇ E (a) 8: until a stop criterion is met Partial derivatives of the energy function E a , with respect to the phase angle of a, denoted α exist; their calculation is detailed in [START_REF] Baden | Efficient energy gradient calculations for binary and polyphase sequences[END_REF], and the result (3) is given below, with η a sequence that depends on c. So it makes sense to use a gradient descent.

∂E a ∂α j = -2p [a j ((η • c * ) * a) j ] -2p [a j ((η • c) * a r ) N +1-j ] , (3)
There are other deterministic algorithms, like the CAN algorithm, introduced by Stoica et al., and described in [START_REF] Song | Optimization methods for designing sequences with low autocorrelation sidelobes[END_REF]. This algorithm expresses the problem in the frequency domain, and solves it with a minimization-majoration technique. However, it suffers from a high computational complexity, due to the use of singular value decompositions (SVD).

C. First results: Comparison of the two methods

In this part, a random search and a steepest descent are applied in order to find sequences with low autocorrelation sidelobes. Figure 1 shows the improvements we can get from a random sequence of length N = 127. In this example, one can observe that both methods perform well: around 15 dB are gained from a random initialization, with a little more for the random search. That gives us a PSL (Peak Sidelobe Level) at around 36 dB. Notice that this result is consistent, compared to other stochastic methods [START_REF] Milewski | A hybrid optimization method for designing polyphase sequences[END_REF] described in the literature. Although the computational time is not really a reliable indicator (as it depends on a lot of parameters), the difference between the two methods is quite impressive: the gradient descent has converged in a few seconds, while it has been about minutes for the random search.

The procedure is repeated in figure 2, with a sequence of length N = 1024. This time, the trend is reversed in favour of the gradient descent: a difference of 3.5 dB can be observed between the two methods. As a random search explores "naturally" the whole domain, the increasing number of degrees of freedom implies a lengthier computation time. However, for practical reasons, the iteration process has to be stopped after a finite reasonable amount of time, thus implying a degradation of performance for high length sequences.

III. AN ALTERNATIVE METHOD BASED ON THE GRADIENT

A steepest descent is a deterministic algorithm. Since this algorithm will converge to the first local optimum on the descent path, its performance strongly depends on the initialization. Hence, it may be interesting to study the performance of a multi-start gradient, or to use a gradient descent during the generation process of a stochastic method, as suggested in [START_REF] Milewski | A hybrid optimization method for designing polyphase sequences[END_REF]. On the other side, stochastic methods are not trapped by local minima, and may thus explore the whole search domain, at the cost of extra computational time.

In this section, we propose an alternative method for minimizing the energy E a . It combines two aspects of the methods described earlier: the exploration of the heuristics, and the fast convergence of a steepest descent. pseudo-randomly, avoiding to fall into a local minimum. Table 3 describes this algorithm, where rand(x, y) denotes a random number between x and y. Its main feature is on the choice of the generation step. The proposed iterative process faces three possible cases: if the cost function at the new proposed candidate is improved, this candidate is accepted, and we randomly increase the descent step in order to possibly go further in the descent direction (case (a)). If the new candidate does not provide an improvement, then it may still be accepted with some probability P (δ) (b). Finally, if it is not accepted (c), we propose to decrease the step in order to increase the probability to accept a new candidate at the next iteration.

if δ := E(a -γ∇ E (a)) -E(a) < 0 then 6: a = a -γ∇ E (a) 7: γ = γ 0 + rand(0, γ 0 ) (a) 8:
else if P (δ) < rand(0, 1) then

9: a = a -γ∇ E (a) (b) 10:
else

11: γ = γ 0 -rand(0, γ 0 ) (c) 12:
end if 13: until a stop criterion is met Figure 2 provides an overview of the efficiency of the proposed algorithm. A gain of 3.5 dB -in terms of PSLis obtained, compared to a standard gradient descent. Figure 3 compares the convergence rate of the two methods by setting a PSL-objective to reach. As the gradient descent can be computed in O(N log(N )) operations [START_REF] Baden | Efficient energy gradient calculations for binary and polyphase sequences[END_REF], one can see that it is also the case for the proposed algorithm, up to a multiplicative factor.

Thus, the proposed method offers better results, at the cost of a reasonable computational cost. So it is appropriate to use it for designing long polyphase sequences.

IV. MISMATCHED FILTERING From here, this article has only been focused on the autocorrelation function of a sequence, that is to say on the matched filter. Such a procedure is thus limited to exactly N degrees of freedom (the length of the sequence) to obtain the best possible PSL. However it is possible to replace the matched filter by a different filter, that will not be optimal in terms of Signal-to-Noise Ratio (SNR) but may provide a better PSL. Using such a mismatched filter provides additional degrees of freedom in order to optimize the PSL, thus allowing to obtain better PSL performance at the cost of a controllable loss in processing gain. The number of additional degrees of freedom will be equal to the length of the mismatched filter, that can be chosen to be longer than the considered sequence.

Let f be a mismatched filter of length N f . The output of the mismatched filter is the sequence d = a * f , where:

d m = N f i=1 a i f * i+m (-N f < m < N f ) . (4)
Apart from the Peak-to-Sidelobe Ratio (PSLR), the efficiency of a mismatched filter can be measured by the Signalto-Noise Ratio (SNR) and the loss in processing gain (LPG). These quantities are defined by:

SNR = 10 log 10 (|a H f |) , (5)
LPG = 10 log 10 (|a H f |) 2 (a H a)(f H f ) (6)
A recent article [START_REF] Rabaste | Mismatched filter optimization for radar applications using quadratically constrained quadratic programs[END_REF] explains how to generate the optimal mismatched filter. The procedure is based on the resolution of an optimization problem, the minimization of the PSLR. The latter can be cast as a Quadratically Constrained Quadratic Program (QCQP). This proposed QCQP is shown to be convex, so it is possible -for instance by using an interior point method -to find the global minimum, and thus i.e. the optimal mismatched filter. In this procedure, the LPG can also be constrained to a given value.

In this section, we suggest to inspect the efficiency of the optimal mismatched filter, according to the initialization. So, we consider two sequences of length N = 127: a random one, and the same sequence, optimized with the proposed method in section III. Their optimal mismatched filter, of length N f = 3N -1 is computed and applied; results are shown figure 4, on the top and the bottom respectively.

We first notice that, interestingly, the matched filter of the optimized sequence presents a better PSLR than the mismatched filter of the initial random sequence, with a difference of approximately 6 dB. Of course, the PSLR provided by the mismatched filter for optimal sequence is much better. Note also that surprisingly the gain provided by the mismatched filter compared to the matched filter is better for the optimized sequence than for the initial sequence.

Hence, in order to obtain a sequence with low sidelobes in autocorrelation, it seems interesting to start with an optimization of the sequence itself, with methods like the one suggested in the previous section, and then employ an optimal mismatched filter on it. Following this procedure, the figure 4 shows that it is possible, for a sequence of length N = 127, to obtain sidelobes with a really flat profile at -52 dB, and with a loss of only 0.3 dB. Such a level is very interesting, especially for sequences with such length!

V. CONCLUSION

In this paper, a method for finding a sequence with low sidelobes in autocorrelation has been presented. It explores a lot of candidates, because of the random feature of the Metropolis-Hastings algorithm, but good ones, as they are chosen in the direction of the gradient. Obtained results are better than what we can obtain with a steepest descent, at the cost of some additional but reasonable computational time. This method can be extended to obtain sets of sequences with low sidelobes in both autocorrelation and cross-correlation.

By definition, a mismatched filter provides a gain on the Peak to Sidelobe Ratio, at a cost of a loss in processing gain. We have observed that this gain is higher on sequences that are optimized than those that are not. The procedure that consists in an optimization of a sequence, and an application of the optimal mismatched filter on it seems promising.

Ongoing work will be focused on:

of a candidate b 4 :

 4 if E a (b) < E a (a) then

0Figure 1 .

 1 Figure 1. Optimization of the autocorrelation of a polyphase sequence of length N = 127

Figure 2 .

 2 Figure 2. Optimization of the autocorrelation of a polyphase sequence, of length N = 1024

Figure 3 .

 3 Figure 3. Comparison of the convergence rate, according to the sequence length and its associated PSL-objective (logarithmic scale)

Algorithm 3

 3 Proposed Method 1: input: selection law P , initial step γ 0 2: random sequence initialization a 3: step initialization, γ = γ 0 4: repeat 5:

Figure 4 .

 4 Figure 4. Matched filter and mismatched filter for a initial sequence of length N = 127. On top: non-optimized sequence. On the bottom: optimized sequence.

  Our method is based on the Random Walk Metropolis-Hastings algorithm, originally proposed by Metropolis et al. in 1953. It allows the evaluation of the cost function in different areas of the search domain. The generation process in the solution we propose is not done on the neighbourhood, but on the line defined by the gradient. The step parameter (just like the one in a descent) is determined

		5
	(s)]	0
	[log 2
	time	-5
	Elapsed	-10
							Proposed Method
							Gradient Descent
		-15
		4	6	8	10	12	14	16	18
				Sequence length [log 2 (N)]
	Sequence length N	2 4	2 5	2 6	2 7	2 8	2 9
	PSL-objective (dB) -20 -27 -29 -33 -35 -37
	Sequence length N 2 10 2 11 2 12 2 13 2 14
	PSL-objective (dB) -39 -41 -42 -43 -44

• Studying the connection between the length of the sequence, its optimal mismatched filter and the PSL (Peak Sidelobe Level) • Jointly optimizing the code and its mismatched filter • Applying these methods on the coherent MIMO ambiguity function case


U Tan

C Adnet

O Rabaste

F Arlery

J.-P Ovarlez

J.-P Guyvarch

Phase Code Optimization for Coherent MIMO Radar Via a Gradient Descent

Keywords:

In this paper, a gradient descent method is used to build radar waveform sequences with good autocorrelation and/or cross-correlation. The approach we propose is based on the energy, a function that measures the sidelobe level of a sequence, and its gradient. Then, we extend and apply it to the optimization of the coherent MIMO (Multiple Input Multiple Output) ambiguity function. We suggest to look for the transmitted signals that reduce the autocorrelation sidelobe level of the signal transmitted by the whole antenna. The obtained results, highlighted by the low sidelobe level of the ambiguity function, seem promising.

I. INTRODUCTION

Multiple Input Multiple Output (MIMO) radar is an emerging concept that has been inspired from wireless communications. Transmit elements of a MIMO radar send different signals which can be separated at the receiving end, providing waveform diversity. Two configurations of MIMO radars are usually considered, denoted as statistical and coherent. In a statistical MIMO radar, antenna elements are widely separated, hence improving detection performance [START_REF] Haimovich | Mimo radar with widely separated antennas[END_REF]. On the other hand, all the elements of a coherent (or co-located) MIMO radar are closely spaced, providing a better spatial resolution [START_REF] Li | Mimo radar with colocated antennas[END_REF]. This paper focuses on the latter, and especially on waveform design.

MIMO radar waveforms can be classified into different categories [START_REF] Sun | Analysis and comparison of mimo radar waveforms[END_REF]: CDMA (Code Division Multiple Accessphase code per antenna), FDMA (Frequency-Division Multiple Access -one frequency per antenna), TDMA (Time Division Multiple Access -transmission in time), etc. However, all these signals suffer from a range/angle coupling [START_REF] Rabaste | Signal waveforms and range/angle coupling in coherent colocated mimo radar[END_REF]. CDMA waveforms seem to present the best coupling, at the cost of high range sidelobe levels.

In general, considered phase codes are sequences providing autocorrelation and cross-correlation with low sidelobes, because a signal with a "good" autocorrelation property may be distinguished from a time-shifted version of itself, while the cross-correlation property enables a signal to be set apart from another signal. Some known families of sequences have been reviewed in [START_REF] Arlery | Utilization of spreading codes as dedicated waveforms for active multi-static primary surveillance radar[END_REF].

Searching for those sequences can be seen as an optimization problem, for instance the minimization of some energy criteria. The energy characterizes, for instance, the autocorrelation sidelobe level of a sequence, like the Merit Factor introduced by Golay [START_REF] Golay | Sieves for low autocorrelation binary sequences[END_REF]. A branch and bound approach [START_REF] Mertens | Exhaustive search for low-autocorrelation binary sequences[END_REF] or an evolutionary strategy [START_REF] Militzer | Evolutionary search for low autocorrelated binary sequences[END_REF] can be used to solve this optimization problem. However, these algorithms become very expensive and ineffective with long sequences.

A recent article [START_REF] Baden | Efficient energy gradient calculations for binary and polyphase sequences[END_REF] gives a solution to the particular problem of the autocorrelation sidelobe minimization based on a steepest descent algorithm based on the gradient of the sidelobe energy. This method will be extended to the coherent MIMO radar case. Instead of optimizing on the original signals transmitted by the antennas, the optimization will rather be done on the signal transmitted in different directions. These directions are obtained by linear combinations of the signals transmitted by the antennas.

This paper is organized as follows. In Section II, a gradient descent is used in order to improve the autocorrelation of a sequence, the cross-correlation of a couple of sequences, and then both simultaneously. Section III tries to reduce the sidelobes of the coherent MIMO ambiguity function, again with a gradient descent.

II. OPTIMIZATION OF THE AUTOCORRELATION AND THE

CROSS-CORRELATION OF A SIGNAL

This section introduces a set of polyphase sequences with small autocorrelations and cross-correlations. At first, each property is studied separately for one sequence for the autocorrelation, and a couple of sequences for the cross-correlation case; obtained results are then combined.

The procedure employed here is inspired from a recent article (Baden et al. [START_REF] Baden | Efficient energy gradient calculations for binary and polyphase sequences[END_REF]). It is based on a real function, called "energy", that quantifies the energy present in the autocorrelation sidelobes of a given sequence. It may be enough to hunt for minima of the energy function to obtain sequences with a low sidelobe level. Hence, this search is equivalent to an optimization problem.

As said in the introduction, stochastic methods are usually helpful. Their convergence to a global minimum is almost certain theoretically. In practice though, global convergence cannot be established, and furthermore, the longer the sequence is, the slower the algorithms are.

Here, a gradient descent, also known as a steep descent, will be used. The steep descent is a fast algorithm for finding a local minimum of a function. It starts with an initial guess of the solution, and as many times as needed, moves it towards the opposite direction of the gradient at that point. One then needs to compute the partial derivatives of each energy (autocorrelation, cross-correlation) in regards to the different phases. The derivation of the gradient of the cross-correlation is shown in section II-A, whereas the autocorrelation one is shown section II-B. Illustrations of optimizations from random polyphase sequences will be shown.

Note that steepest descent algorithms are bound to converge to local optima of the cost function. However, as will be seen thereafter, it appears that for the particular case of the phase codes, these local optima provide already quite interesting sidelobe levels.

A. Optimizing polyphase cross-correlation

This part deals with the reduction of cross-correlation sidelobes for a couple of polyphase sequences. It derives from the computation of the energy gradient, introduced by Baden et al. in [START_REF] Baden | Efficient energy gradient calculations for binary and polyphase sequences[END_REF]. The "energy" is a function that evaluates the sidelobes level of a sequence (here, the cross-correlation sidelobes level).

Let us consider two polyphase sequences a and b, following the same hypothesis: they are of length N and of constant modulus, i.e. a = [a 1 , ..., a N ] T = e j2παi i∈ 1,N . Assume that a i = 0 for i < 1 and i > N .

The discrete cross-correlation, denoted by x = a * b, is the sequence:

x m = N i=1 a i b * i+m (-N < m < N ) . (1)
By including some weighting w to allow shaping of the sidelobes, and an exponent p to control the peak sidelobe, the cross-correlation sidelobe energy E c is defined by:

E c (a, b) = N -1 m=-N +1 w m (x m x * m ) p . (2)
As a small energy means low sidelobes, a steepest descent should find a "better" sequence. However, it requires a gradient computation; the procedure is detailed in [START_REF] Baden | Efficient energy gradient calculations for binary and polyphase sequences[END_REF], and main results are given below.

In the following, we note (.) * the complex conjugate operator, (.) r the reverse part of any vector (i.e. a r = [a N , . . . , a 1 ]), the real part and imaginary part are respectively denoted by (.) and (.).

According to the chain rule, the gradient of E c with respect to the phase angle α can be written as:

∂E c ∂α j = (a j ) ∂E c ∂ (a j ) -(a j ) ∂E c ∂ (a j ) . (3)
So we have to examine the partial derivatives of E c with respect to the real and imaginary parts of a. Let us set γ = (γ -N +1 , . . . , γ N -1 ) T where γ m = w m (c m c * m ) p-1 . Thse partial derivatives are:

∂E c ∂ (a j ) = 2p N -1 m=-N +1 γ m (x m ) (b j+m ) -(x m ) (b j+m )
∂E c ∂ (a j ) = 2p [((γ • x) * b * ) j ] , (4)
∂E c ∂ (a j ) = 2p N -1 m=-N +1 γ m (x m ) (b j+m ) + (x m ) (b j+m ) = 2p [((γ • x) * b * ) j ] . (5)
where • denotes the Hadamard product. Putting ( 4) and ( 5) into the equation (3) gives:

∂E c ∂α j = 2p (a j ) [((γ • x) * b * ) j ] -2p (a j ) [((γ • x) * b * ) j ] = 2p a * j ((γ • x) * b * ) j . (6)
In the same way, the partial derivative of the crosscorrelation energy with respect to β -the phase angle of b -should be computed. As the calculation steps are quite analogous, the main results are listed below.

∂E c ∂ (b j ) = 2p [(γ • x) * a * r ] N +1-j , ∂E c ∂ (b j ) = -2p [(γ • x) * a * r ] N +1-j , ∂E c ∂β j = -2p [b j ((γ • x) * a * r ) N +1-j ] . (7)
Finally, an optimization of a and b can be done, again with a gradient descent, in order to find a couple of sequences with a better cross-correlation property. Figure 1 gives an example of an optimization of the cross-correlation of two sequences of length N = 256. Both sequences have been randomly initialized; their cross-correlation sequence is represented by the red-dotted line. An enhancement of around 25 dB can be obtained after applying the previous procedure.

B. Optimizing polyphase autocorrelation

Consider now only one sequence a under the same assumptions as above. The autocorrelation is expressed as c = a * a and can be computed as:

c m = N i=1 a i a * i+m (-N < m < N ) (8)
The autocorrelation sidelobe energy is defined as:

E a (a) = N -1 m=-N +1 w m (c m c * m ) p (9)
The gradient of this energy is needed to reduce the autocorrelation with a steepest descent. Every calculation step can be found in [START_REF] Baden | Efficient energy gradient calculations for binary and polyphase sequences[END_REF], so only major developments are listed here.

As the procedure is similar, let us start with the partial derivatives with respect to the real and imaginary parts of a.

η is set to η m = w m (c m c * m ) p-1 for convenience. ∂E a ∂ (a j ) = 2p N -1 m=-N +1 η m (c m ) ( (a j+m ) + (a j-m )) + (c m ) (-(a j+m ) + (a j-m )) = 2p [((η • c) * a * ) j + ((η • c) * a r ) N +1-j ] , ∂E a ∂ (a j ) = 2p N -1 m=-N +1 η m (c m ) ( (a j+m ) + (a j-m )) + (c m ) ( (a j+m ) -(a j-m )) = 2p [((η • c) * a * ) j -((η • c) * a r ) N +1-j ] .
The gradient of E a with respect to the phase angle α can be deduced with the chain rule:

∂E a ∂α j = (a j ) ∂E a ∂ (a j ) -(a j ) ∂E a ∂ (a j ) = -2p [a j ((η • c * ) * a) j ] -2p [a j ((η • c) * a r ) N +1-j ] . (10)
Figure 2 shows an illustration of an autocorrelation optimization using a steep descent. A random initialization is used. Its autocorrelation is represented with a red dotted line. A gain of 15 dB can be observed for this sequence of length N = 256. One can notice that the gain is smaller than the cross-correlation one; it can be explained by the increase of the number of degrees of freedom.

C. Optimizing both autocorrelation and cross-correlation

In general, optimization of the autocorrelation or the crosscorrelation alone is not sufficient. It is usually desired to design a set of sequences with low sidelobes level, in both properties. This section investigates the two-sequences case, but can easily be generalized for a set of several sequences.

Here, the energy E should depict the autocorrelation and the cross-correlation of two polyphase sequences a and b: 6), ( 7) and (10) gives:

E = E a (a) + E a (b) + E c (a, b) . (11)
∂E ∂α j = ∂E a (a) ∂α j + ∂E c (a, b) ∂α j = -2p [a j ((η a • c a * ) * a) j ] -2p [a j ((η a • c a ) * a r ) N +1-j ] + 2p a * j ((γ • x) * b * ) j , ∂E ∂β j = ∂E a (b) ∂β j + ∂E c (a, b) ∂β j = -2p b j ((η b • c a * ) * b) j -2p b j ((η b • c a ) * b r ) N +1-j -2p [b j ((γ • x) * a * r ) N +1-j ]
where c a stands for the discrete autocorrelation sequence of a, and η a m = w m (c a m (c a m ) * ) p-1 . Figure 3 depicts the autocorrelation and the crosscorrelation of two sequences of length N = 256 after a joint optimization. The gain in autocorrelation and in crosscorrelation sidelobe levels is reduced compared to the results obtained with separate optimizations. However, a compromise can be observed: each property has pretty much the same level (the peak sidelobe level is around -28 dB).

III. COHERENT MIMO WAVEFORM DESIGN WITH A GRADIENT DESCENT

In the coherent MIMO Radar concept, several waveforms are sent simultaneously by different radiating elements. The radiated signal (by the whole antenna) is a linear combination of all the transmitted ones; it is distinct for each angular direction through phase-shifting in space.

The literature commonly supposes that the transmitted waveforms are orthogonal. Such orthogonality would provide the ability to separate perfectly each component in reception. Thus desired phase codes should ideally present perfect aperiodic autocorrelation and cross-correlation properties. As these properties are not theoretically feasible, one should search for the best possible sequences in terms of output MIMO ambiguity sidelobes. A first solution would be to optimize the autocorrelation and the cross-correlation sidelobes of the sequences transmitted by the antennas. However, it appears that the range cut of the MIMO ambiguity function is provided by a linear combination of all autocorrelation and cross-correlation sidelobes of the transmitted sequences, with linear coefficients depending on the considered direction. It is thus preferable to optimize directly the autocorrelation and cross-correlation sidelobes of the signal transmitted in different considered directions. We propose to study the autocorrelation in several directions.

A. Problem Formulation

Let us consider a transmitting array of N E antennas and a receiving array of N R antennas. The signal radiated by the whole antenna, denoted by s(θ c ), is [START_REF] Rabaste | Signal waveforms and range/angle coupling in coherent colocated mimo radar[END_REF]:

s i (θ c ) = N E -1 m=0 e jx T E,m k(θc) s m i , (12)
where:

• x T E,m is the position of the m th antenna, • k(θ c ) is the wave vector in the direction θ c ,

• s m := [s m 1 , ..., s m N ]
is the waveform of length N assigned to the m th antenna. The cross-correlation x between two signals at different angles θ c and θ c can be written as:

x l = N i=1 s i (s i+l ) * = N i=1 N E -1 m=0 e jx T E,m k(θc) s m i N E -1 m =0 e jx T E,m k(θ c ) s m i+l * = m,m e jx T E,m k(θc)-jx T E,m k(θ c ) N i=1 s m i (s m i+l ) * .
One can notice that the cross-correlation is an accumulation of all the autocorrelation and the cross-correlation between two transmitted signals, within a phase shift. We recall the phase shift is

ϕ m,m = x T E,m k(θ c ) -x T E,m k(θ c ). If θ = θ c
, this reduces to the autocorrelation function.

In the same way as section II, let us define the crosscorrelation sidelobe energy function:

E c (s, s ) = N -1 l=-N +1 w l (x l x * l ) p .
This energy function shall be minimized so that the waveform transmitted by the whole antenna has low cross-correlation sidelobes in the direction θ c . This optimization problem will also be solved by a gradient descent: the computation of the partial derivatives of the energy function with respect to the phase angle of each transmitted signal is explained in the next part.

B. Energy Gradient Calculation

The energy gradient is computed in two steps. First, partial derivatives with respect to the real and the imaginary part of s m (the signal transmitted by each antenna) are determined. The energy gradient with respect to each phase is then deduced from the chain rule. Some developments are superfluous and are not given here.

Let us start by giving some details on the real part (and the imaginary one) of the cross-correlation sequence x:

(x l ) = m,m e jϕ m,m N i=1 s m i (s m i+l ) * = m,m (e jϕ m,m ) N i=1 (s m i ) (s m i+l ) + (s m i ) (s m i+l ) - m,m (e jϕ m,m ) N i=1 (s m i ) (s m i+l ) -(s m i ) (s m i+l ) , (x l ) = m,m (e jϕ m,m ) N i=1 (s m i ) (s m i+l ) + (s m i ) (s m i+l ) + m,m (e jϕ m,m ) N i=1 (s m i ) (s m i+l ) -(s m i ) (s m i+l ) .
As the radiated signal s(θ c ) is basically a linear combination of the transmitted signals s m , it is not absurd to consider the partial derivatives of the energy w.r.t. the real part (and the imaginary part) of s m . Before that, we derive the crosscorrelation x:

∂ (x l ) ∂ (s u v ) = m,m (e jϕ m,m ) δ um (s m v+l ) + δ um (s m v-l ) - m,m (e jϕ m,m ) -δ um (s m v+l ) + δ um (s m v-l ) = m,m δ um (e -jϕ m,m s m v+l ) + δ um (e jϕ m,m s m v-l ) = m (e -jϕu,m s m v+l ) + (e jϕm,u s m v-l ) , ∂ (x l ) ∂ (s u v ) = m (e jϕu,m (s m v+l ) * ) + (e jϕm,u s m v-l ) ∂ (x l ) ∂ (s u v ) = m (e -jϕu,m s m v+l ) + (e jϕm,u s m v-l ) ∂ (x l ) ∂ (s u v ) = m (e jϕu,m (s m v+l ) * ) -(e jϕm,u s m v-l ) .
Set γ to γ l = w l (x l x * l ) p-1 . Gathering all the previous results gives:

∂E c ∂ (s u v ) = 2p N -1 l=1-N γ l (x l ) ∂ (x l ) ∂ (s u v ) + (x l ) ∂ (x l ) ∂ (s u v ) = 2p N -1 l=1-N γ l (x l )
m (e -jϕu,m s m v+l )

+ (e jϕm,u s m v-l )

+ γ l (x l ) m (e jϕu,m (s m v+l ) * ) + (e jϕm,u s m v-l ) = 2p m N -1 l=1-N (γ l x l e -jϕu,m s m v+l ) + (γ l x * l e jϕm,u s m v-l ) = 2p m ((γ • x)e -jϕu,m * (s m ) * ) v + ((γ • x * )e jϕm,u * (s m ) * r ) N +1-v , ∂E c ∂ (s u v ) = 2p N -1 l=1-N γ l (x l ) ∂ (x l ) ∂ (s u v ) + (x l ) ∂ (x l ) ∂ (s u v ) = 2p m ((γ • x)e -jϕu,m * (s m ) * ) v + ((γ • x * )e jϕm,u * (s m ) * r ) N +1-v .
Let α u (v) the phase angle of the element s u v . According to the chain rule, the partial derivative of E c with respect to that phase can be written as:

∂E c ∂α u (v) = (s u v ) ∂E c ∂ (s u v ) -(s u v ) ∂E c ∂ (s u v ) = -2p m s u v ((γ • x * )e jϕu,m * s m ) v (13) + s u v ((γ • x)e -jϕm,u * (s m ) r ) N +1-v .

C. Application and Results

In this part, we will search for transmitted sequences s m in such a way that the aperiodic correlation of the signal produced by the array s(θ c ) is optimized. Since that signal s(θ c ) depends on the direction θ c (cf. equation ( 12)), and since we want good sidelobes in any direction, we have to examine another formulation of the minimization problem that considers several directions Θ:

min s 0 ,...,s N E -1 E(s) := θ∈Θ E c (s(θ), s(θ)) . (14)
As ∇E can easily be deduced from eq. ( 13), a steepest descent is employed to find a transmitting set {s 0 , . . . , s N E -1 } (which is a local minima of E).

Figures 4 to 7 present some results of a simulated radar antenna with four transmitters (N E = 4) and four receivers. Phase codes are of length N = 256, and four directions are inspected. Two methods are compared:

1) the proposed method, i.e. an optimization of the transmitted waveforms in order to improve the autocorrelation property of the radiated signal 2) the usual method, i.e. an optimization of the autocorrelation and the cross-correlation of the transmitting set. This set is obtained with the procedure described in Section II. An improvement of the autocorrelation of the radiated signal in a direction of interest is shown in Figure 4. A gain of 10 dB can be noticed compared to a random initialization (represented by the red dotted line), whereas the second method does not improve this autocorrelation. In the three other directions of interest, sidelobe levels are quite similar. Moreover, Figure 5 shows that it is not needed to take into account the orthogonality of the transmitted sequences in order to improve the autocorrelation of the radiated signal in a direction.

Let us recall the problematic described in the introduction. The aim of this article is to search for phase-coded waveforms so that the radar has a good range/angle resolution, and low sidelobe levels (in range and in angle). The socalled ambiguity function can provide directly a measure of these criteria. Figure 6 and Figure 7 represent the ambiguity function obtained for the proposed method and the usual one respectively. We have made the assumption that there is no Doppler effect during a pulse. Results are promising, as the sidelobe level is around -28 dB. They are slightly better than what we get with a Gold code, [START_REF] Rabaste | Signal waveforms and range/angle coupling in coherent colocated mimo radar[END_REF] or with the usual method. Notice that the range cut at θ = 0 is equivalent to the autocorrelation of the signal diffused by the whole antenna (cf. Figure 4). IV. CONCLUSION

In this paper, we have seen that a gradient descent is an interesting method for finding sequences with low sidelobes in autocorrelation (or in cross-correlation). This method has also been applied to search for transmitted sequences of a coherent MIMO radar in a way that the emitted signal has a nice autocorrelation. Results are promising as the associated ambiguity function presents low sidelobes in range and in angle.

Ongoing work will be focused on:

• Taking into account the cross-correlation in the MIMO waveform optimization • Optimizing the radiated energy in the different directions • Jointly optimizing the code and its optimal mismatched filter ACKNOWLEDGMENT This work is partly supported by a DGA-MRIS scholarship.

Figure 1 .

 1 Figure 1. Optimization of the cross-correlation of a couple of sequences

Figure 2 .

 2 Figure 2. Optimization of the autocorrelation of a polyphase sequence

Figure 3 .

 3 Figure 3. On the top: optimization of the autocorrelation. On the bottom: optimization of the cross-correlation

Figure 4 .Figure 5 .Figure 6 .Figure 7 .

 4567 Figure 4. Optimization of the aperiodic correlation of the radiated signal in a direction of interest. On the top: with the proposed method. On the bottom: with the usual method.