Conceptions of sport ability and practice of sport: an implicit measure NICOLAS MASCRET, JEAN-LOUIS FALCONETTI, and FRANÇOIS CURY Aix Marseille Université, CNRS, ISM UMR 7287, 13288, Marseille, France People may endorse two conceptions of the nature of sport ability: an entity theory (sport ability is considered innate, stable, a gift, a talent) and an incremental theory (sport ability is improvable, linked to training and effort). Previous studies (e. g., [START_REF] Biddle | Motivation for physical activity in young people: entity and incremental beliefs concerning athletic ability[END_REF] have used explicit methods to assess these beliefs. Using an implicit measure (ST-IAT, Single-Target Implicit Association Test) in order to overcome the social desirability which might be induced by self-reported measures, this study examined (1) whether automatic and implicit conceptions of sportspersons and non-sportspersons differed, and (2) the correlation between IAT score and explicit perceived competence in sport. The results showed that sportspersons automatically associated sport with training rather than talent, whereas non-sportspersons had an easier association between sport and talent. Even if sportspersons had higher perceived competence in sport than non-sportspersons, the IAT score was not related to perceived competence. KEY WORDS: Entity, Implicit theory, Incremental, Implicit Association Test, Nonsportspersons, Perceived competence, Sport ability beliefs.

In a context of declining physical activity and increasing obesity [START_REF] Ng | Time use and physical activity: a shift away from movement across the globe[END_REF], it is important to understand the motivational factors associated with physical activity and sport. Beliefs, such as implicit theories, can affect a person's cognition, affect and behaviour in achievement areas, and can influence a person's interpretation of events. The inaugural works of [START_REF] Dweck | Motivational processes affecting learning[END_REF] and [START_REF] Dweck | A social-cognitive approach to motivation and personality[END_REF] highlighted implicit theories of intelligence, i.e. what individuals think about the nature of intelligence. Two conceptions of the nature of intelligence were identified: an entity theory (intelligence is innate, stable, a gift, a talent) and an incremental theory (intelligence is improvable, linked with work and effort). Implicit theories are not the reality, but rather personal beliefs. In education, literature reviews (e.g., [START_REF] Dweck | Self-Theories: Their impact on competence motivation and acquisition[END_REF] showed that incremental theory was related to adaptive outcomes, whereas entity theory was a negative predictor of student performance.

Following these initial works conducted in the academic domain, sport studies have focused on the distinction between the entity and incremental theories [START_REF] Biddle | Motivation for physical activity in young people: entity and incremental beliefs concerning athletic ability[END_REF][START_REF] Sarrazin | Goal orientations and conceptions of the nature of sport ability in children: a social cognitive approach[END_REF]. Entity theory considered sport or athletic ability improvable with effort and training, and incremental theory considered sport ability innate, stable, depending on genetics, gift or talent. [START_REF] Sarrazin | Goal orientations and conceptions of the nature of sport ability in children: a social cognitive approach[END_REF] created the first self-reported scale to identify implicit theories of sport ability, called the Conceptions of the Nature of Athletic Ability Questionnaire (CNAAQ). This first questionnaire was revised by [START_REF] Biddle | Motivation for physical activity in young people: entity and incremental beliefs concerning athletic ability[END_REF], who created the CNAAQ-2. Results in sport literature confirmed the results in academic domain. Incremental and entity theories were respectively linked with adaptive and maladaptive outcomes. For example, entity beliefs predicted amotivation towards physical education and sport [START_REF] Biddle | Motivation for physical activity in young people: entity and incremental beliefs concerning athletic ability[END_REF], reduced effort [START_REF] Chen | Implicit theories of athletic ability and self-handicapping in college students[END_REF] or self-handicapping [START_REF] Ommundsen | Self-handicapping strategies in physical education classes: The influence of implicit theories of the nature of ability and achievement goal orientations[END_REF], whereas incremental beliefs about athletic ability were positively linked with enjoyment of sport [START_REF] Chian | Motivational profiles of junior college athletes: a cluster analysis[END_REF], intrinsic motivation [START_REF] Moreno | Motivation in the exercise setting: integrating constructs from the approach-avoidance achievement goal framework and self-determination theory[END_REF] or perceived competence [START_REF] Cury | Perceptions of competence, implicit theory of ability, perception of motivational climate, and achievement goals: a test of the trichotomous conceptualization of endorsement of achievement motivation in the physical education setting[END_REF].

Several studies [START_REF] Chian | Motivational profiles of junior college athletes: a cluster analysis[END_REF][START_REF] Wang | Young people's motivational profiles in physical activity: a cluster analysis[END_REF][START_REF] Wang | Achievement goal profiles in school physical education: differences in self-determination, sport ability beliefs, and physical activity[END_REF] have used cluster analysis including sport ability beliefs, in order to identify subgroups of participants with differentiated motivational patterns. Amotivated group and low motivated groups showed amotivation, low incremental beliefs, low perceived competence, low sport and physical activity. On the contrary, highly motivated group showed low amotivation, high incremental beliefs, high perceived competence, high sport and physical activity participation. These results highlighted that sport ability beliefs may influence sport participation. Incremental and entity beliefs were respectively negatively and positively linked with amotivation [START_REF] Wang | Achievement goal profiles in school physical education: differences in self-determination, sport ability beliefs, and physical activity[END_REF]. The amotivated individuals perceived that there is little or no purpose in continuing with the activity [START_REF] Vallerand | Measures of intrinsic and extrinsic motivation in sport and physical activity: A review and critique[END_REF]. They tended to reject sport participation, and there is a great risk of becoming less physically active and even abandoning sport. Further investigations on this question were promising to explore to what extent conceptions of sport ability among sportspersons and non-sportspersons differ.

Consequently, assessing representations of sport ability is inescapable in order to understand behaviours in a sport context. People with an incremental theory seek to increase their skills and competencies, choose adapted challenges, and consider that mistakes are part of learning process. People with an entity theory develop negative affects and cognitions when they face a problem, so they readily tend to give up the task or to reduce their invest-ment when they think they could fail. It might be difficult for some people to admit that they think sport ability depends on talent, gift or genetics and cannot be improved, because that would be like saying that they were not themselves talented or gifted in sport. Consequently, self-reported measures about conceptions of the nature of athletic ability, such as CNAAQ [START_REF] Sarrazin | Goal orientations and conceptions of the nature of sport ability in children: a social cognitive approach[END_REF] or CNAAQ-2 [START_REF] Biddle | Motivation for physical activity in young people: entity and incremental beliefs concerning athletic ability[END_REF], may be subject to social desirability (e.g., [START_REF] Crosby | Recent unobtrusive studies of Black and White discrimination and prejudice: A literature review[END_REF][START_REF] Crowne | A new scale of social desirability independent of psychopathology[END_REF]. Social desirability is the tendency of respondents to answer questions in order to be viewed favourably by others, to present themselves at their best. Subjects' desire to be perceived positively is widely assumed to be a potential source of distortion of self-report measures [START_REF] Greenwald | Implicit social cognition: Attitudes, self-esteem, and stereotypes[END_REF]. Even if the reliability of self-reported measures about implicit theories of sport ability were evidenced and confirmed, we might think that social desirability would prevent some persons from explicitly declaring an entity theory of sport ability. Indeed, in all studies about conceptions of the nature of sport ability (e.g., [START_REF] Biddle | Motivation for physical activity in young people: entity and incremental beliefs concerning athletic ability[END_REF][START_REF] Cury | Perceptions of competence, implicit theory of ability, perception of motivational climate, and achievement goals: a test of the trichotomous conceptualization of endorsement of achievement motivation in the physical education setting[END_REF][START_REF] Moreno | Motivation in the exercise setting: integrating constructs from the approach-avoidance achievement goal framework and self-determination theory[END_REF][START_REF] Ommundsen | Self-handicapping strategies in physical education classes: The influence of implicit theories of the nature of ability and achievement goal orientations[END_REF][START_REF] Wang | Achievement goal profiles in school physical education: differences in self-determination, sport ability beliefs, and physical activity[END_REF][START_REF] Wang | Sport ability beliefs, 2x2 achievement goals, and intrinsic motivation: the moderating role of perceived competence in sport and exercise[END_REF], incremental scores are higher than entity scores, even for clusters called "amotivated" by sport [START_REF] Chian | Motivational profiles of junior college athletes: a cluster analysis[END_REF][START_REF] Wang | Young people's motivational profiles in physical activity: a cluster analysis[END_REF].

To evaluate implicit cognitive constructs, the Implicit Association Test (IAT) provides a computer-based measure of strengths of automatic associations [START_REF] Greenwald | Measuring individual differences in implicit cognition: The Implicit Association Test[END_REF], especially in the domains of stereotypes and identity (e.g., [START_REF] Greenwald | Understanding and using the Implicit Association Test: I. An improved scoring algorithm[END_REF]. When a person is quick to pair a concept and an attribute, the implicit association between them is considered strong. For example, [START_REF] Nosek | Math = male, me = female, therefore math ≠ me[END_REF] studied the maths-gender stereotype using the latency of association of lexical stimuli in one compatible condition (like "math-male" and "arts-female") compared to an incompatible condition (like "math-female" and "arts-male"). In the IAT procedure, many attitude objects had a complementary category (Greenwald & Farnham, 2000), as for examples male and female, or math or liberal arts. But IAT cannot highlight the evaluative associations with a singletarget concept. Therefore, [START_REF] Karpinski | The single category implicit association test (SC-IAT) as a measure of implicit social cognition[END_REF] created the Single Category Implicit Association Test (SC-IAT), which is a modified version of the IAT that eliminates the need for the second contrast category. The choice between IAT and SC-IAT depends on the research question, and the SC-IAT seems more beneficial when a naturally opposing category is unavailable [START_REF] Karpinski | The single category implicit association test (SC-IAT) as a measure of implicit social cognition[END_REF], like the category sport in the present study.

Despite minor procedural differences, SC-IAT was conceptually identical to the Single-Target IAT used here (ST-IAT; [START_REF] Bluemke | Reliability and validity of the Single Target IAT (ST IAT): assessing automatic affect towards multiple attitude objects[END_REF][START_REF] Wigboldus | Single target implicit associations[END_REF]. ST-IAT included an initial practice stage with only good and bad target words, had fewer target words in each stage and did not use a response window for slow answers [START_REF] Karpinski | The single category implicit association test (SC-IAT) as a measure of implicit social cognition[END_REF]. The reliability and the validity of the ST-IAT was tested and validated across different attitude domains [START_REF] Bluemke | Reliability and validity of the Single Target IAT (ST IAT): assessing automatic affect towards multiple attitude objects[END_REF]. Up to date, there was no IAT, SC-IAT or ST-IAT that identified implicit theories about conceptions of the nature of sport ability.

The aims of the present study were to develop a ST-IAT which could highlight whether the automatic and implicit conceptions of sportspersons and non-sportspersons differed, and to study if the correlation between conceptions of ability and perceived competence previously identified using explicit measures was still valid with an IAT measure.

Method

PARTICIPANTS AND PROCEDURE

Participants

Data were collected in France from 117 voluntary participants (82 men, 35 women, M age = 26.57 years, age range: 18-29 years). Two groups were constituted: sportspersons and nonsportspersons. All the sportspersons (95 participants) were competitors and licence-holders in a club affiliated to a sport federation. They were not high-level sportspersons or professionals. One group of non-sportspersons was also constituted with participants who declared they were not licence-holders. They did not engage in organised sport activities, defined as having a regular schedule and being part of a formal, organised group, such as a recreational group or organisation [START_REF] Slutzky | The link between children's sport participation and self-esteem: Exploring the mediating role of sport self-concept[END_REF]. Moreover, they did not practice informal sport or did so for less than an hour a month. We are in line with [START_REF] Wang | Achievement goal profiles in school physical education: differences in self-determination, sport ability beliefs, and physical activity[END_REF] work, in which the lower category of the duration of time participants engaged in sport activities was less than an hour per week. Lastly, participants who had been sportspersons and competitors in the past were excluded from the study. Consequently, 22 participants represented those individuals who did not, and had never, participated in sport. The sample size is low, but we have used stringent criteria for inclusion in this group to focus on their specific implicit beliefs about sport ability. Moreover, small sample sizes may be used with IAT procedure (e. g., [START_REF] Greenwald | Measuring individual differences in implicit cognition: The Implicit Association Test[END_REF]. Even if all participants in the present study were representative of the repartition between sportspersons and non-sportspersons in France [START_REF] Mignon | Les pratiques sportives en France [Sport activities in France[END_REF], future studies should be conducted with larger samples of non-sportspersons.

Stimuli and pilot test

Twenty nouns selected by fifteen lecturers specialised in the sport domain were used as lexical stimuli: ten talent words and ten training words. The words were rated by 100 undergraduates in the sport domain for the degree to which they were talent-related or trainingrelated on a 5-point scale (1 = strongly linked to talent, 3 = neither talent-linked nor training-linked, 5 = strongly linked to training). Only the eight words with the best scores were retained for talent (genetic, predisposition, innate, natural, aptitude, birth, genius, potential) and for training (work, planning, preparation, programme, repetition, method, progression, improvement). The talent words were rated as more talent-related (M = 1.98, SD = 1.06) than were the training words, and the training words were rated as more training-related (M = 4.15, SD = 1.06) than the talent words. Word length was controlled by counting the numbers of letters, and there were no significant differences (t(14) = -1.31, p = .21) between talent words (M = 8.25, SD = 3.06) and training words (M = 10.00, SD = 2.20). For sport stimuli, the eight words used by Clément-Guillotin, Chalabaev and Fontayne (2011) were added to four other words selected by the same 15 lecturers. Then, these twelve sport words were rated by the same 100 undergraduates for their degree of link with sport on a 5-point scale (1 = not at all, 5 = extremely). The eight words with the most extreme evaluation were kept (M = 3.70, SD = 1.37), as the eight sport words used in the ST-IAT (team, stadium, changing room, competition, match, rankings, podium, medal). Based on these ratings, the 24 words were selected and used as lexical stimuli.

Design and procedure

Each participant was seated alone at a desk with a personal computer with a 15" monitor using Inquisit 3 software. The participants were briefly instructed that the experiment would test their reaction times and that they should assign the stimuli which appeared in the centre of the screen to different categories as quickly and correctly as possible. Participants placed one finger on the E key (the left key) of the keyboard and another finger on the I key (the right key). of the screen. So the participant must press the left-key response as fast as possible. If a sport word (e. g., team, competition) appeared in the centre of the screen, the participant must also press the left-key response. If a training word (e. g., work, method) appeared, the participant must press the right-key response. The category sport was then switched to the right key for the other half of the task.

Following the ST-IAT procedure [START_REF] Bluemke | Reliability and validity of the Single Target IAT (ST IAT): assessing automatic affect towards multiple attitude objects[END_REF], the measure consisted of 80 trials divided into two combined blocks. Participants started with a training block (20 trials) for the evaluative words prior to each combined block. Each stimulus was presented at least twice, adding up to 40 trials per combined block. The procedure is presented in Table I. Following the protocol suggested by [START_REF] Bluemke | Reliability and validity of the Single Target IAT (ST IAT): assessing automatic affect towards multiple attitude objects[END_REF], individual responses less than 300ms, responses more than 3,000ms, and nonresponses were eliminated. Data from participants who had an error rate over 20% on the ST-IAT were removed from analyses. All participants met the error rate criterion, so all participants were included in the results.

MEASURES

Talent-Training -IAT (TT-IAT)

The difference in response latency between the average speed of response to sport and talent items when they were paired together, and the average speed of response to sport and training items when they were paired together was used. ST-IAT scores were computed by using the D-score algorithm [START_REF] Greenwald | Understanding and using the Implicit Association Test: I. An improved scoring algorithm[END_REF] applied to the ST-IAT data [START_REF] Bluemke | Do features of stimuli influence IAT effects[END_REF], 2008). Sport was the target concept and talent and training were the attribute concepts. In the present study, in order to examine more specifically the entity theory of sport ability, which is more likely to be sensitive to social desirability, sporttalent was considered a compatible condition, and sport-training an incompatible one. If participants' IAT score is positive and superior to 0.15 [START_REF] Greenwald | Understanding and using the Implicit Association Test: I. An improved scoring algorithm[END_REF], this would show that they have a higher association between sport and talent than sport and training, evidencing that they are more likely to hold to an entity theory. If IAT score is negative, it is the opposite.

6

N. Mascret, J.-L. Falconetti, F. Cury

Perceived competence

This subscale was assessed with [START_REF] Durand | French version of the Robert-Balague perception of success questionnaire[END_REF] French translation from the Intrinsic Motivation Inventory [START_REF] Mcauley | Psychometric properties of the Intrinsic Motivation Inventory in a competitive sport setting: A confirmatory factor analysis[END_REF]. Participants responded to the four perceived competence items (e.g., "I think I am pretty good at sport") using a 1 (strongly disagree) to 5 (strongly agree) scale. Internal consistency was good for perceived competence (α = .92).

Results

In the Implicit Association Test analysis (e.g., [START_REF] Bluemke | Reliability and validity of the Single Target IAT (ST IAT): assessing automatic affect towards multiple attitude objects[END_REF][START_REF] Greenwald | Understanding and using the Implicit Association Test: I. An improved scoring algorithm[END_REF][START_REF] Karpinski | The single category implicit association test (SC-IAT) as a measure of implicit social cognition[END_REF], the ST-IAT revealed a negative slight to medium-sized association between sport and talent (D = -0.23) for the whole population, evidencing that participants had a stronger implicit association between sport and training than between sport and talent. The whole population was representative of the repartition between sportspersons and non-sportspersons in France [START_REF] Mignon | Les pratiques sportives en France [Sport activities in France[END_REF]. Separate analyses revealed a negative slight to medium-sized association between sport and talent (D = -0.32) for sportspersons, and a positive slight to medium-sized association between sport and talent (D = 0.17) for non-sportspersons. There was a significant difference (t(115) = -7.04, p < .0001) between sportspersons' IAT score (M = -0.32, SD = 0.30) and non-sportspersons' IAT score (M = 0.17, SD = 0.26), evidencing that non-sportspersons implicitly associated sport more often with talent than sportspersons, who had a higher implicit association between sport and training than between sport and talent.

The IAT score was not correlated with perceived competence of sportspersons (r = -.01, p = .92) and non-sportspersons (r = -.29, p = .20). A t test conducted on perceived competence revealed a significant effect of practising sport (t(115) = 4.36, p < .0001). Sportspersons had higher perceived competence in sport (M = 3.81, SD = 0.82) than non-sportspersons (M = 2.89, SD = 1.14).

Discussion

The aims of the present study were on one hand to highlight with implicit measures automatic associations between sport and talent/training according to the practice of sport or not, and on the other hand to identify correlations between this implicit measure and self-reported perceived competence in sport. The results showed that non-sportspersons had a higher automatic association between sport and talent than between sport and training, contrary to sportspersons. If people believe that athletic ability cannot change, it is easier for them to build this automatic association between sport and talent. Reasons for being non-sportspersons are numerous, but some non-sportspersons may think that they were not born to practice sport. They have developed the belief that sport ability is relatively stable and related to talent, which they doubted that they sufficiently possessed. According to [START_REF] Biddle | Motivation for physical activity in young people: entity and incremental beliefs concerning athletic ability[END_REF], entity beliefs were strong predictors of amotivation. Believing that athletic ability is a gift and is stable appears to be motivationally maladaptive, and may account for the absence of sport practice for this specific group. Consequently, non-sportspersons implicitly and automatically associated sport more often with talent than sportspersons. These results were in line with those found with explicit measures [START_REF] Wang | Young people's motivational profiles in physical activity: a cluster analysis[END_REF][START_REF] Wang | Achievement goal profiles in school physical education: differences in self-determination, sport ability beliefs, and physical activity[END_REF]. The interest of implicit measures like ST-IAT is to overcome the social desirability biases of explicit and self-reported measures which can be distorted or deformed by participants [START_REF] Greenwald | Measuring individual differences in implicit cognition: The Implicit Association Test[END_REF]. Indeed, for non-sportspersons, admitting that sport ability depends on talent and cannot be improved is an indirect way to confess that they are not talented or gifted enough to practice sport themselves. In studies with explicit measures, incremental scores are higher than entity scores even for clusters called "amotivated" by sport [START_REF] Chian | Motivational profiles of junior college athletes: a cluster analysis[END_REF][START_REF] Wang | Young people's motivational profiles in physical activity: a cluster analysis[END_REF], which may indicate some form of social desirability. With implicit measures based on a response time paradigm, there is lack of dependence on introspective access to the association strengths being measured [START_REF] Greenwald | Understanding and using the Implicit Association Test: I. An improved scoring algorithm[END_REF] and therefore a limitation of social desirability, which will reveal participants with an automatic association between sport and talent that a self-reported measure may not identify.

By contrast, sportspersons had a stronger implicit association between sport and training than between sport and talent. This implicit result was in line with explicit ones, in which participation in sport was positively related to incremental beliefs [START_REF] Chian | Motivational profiles of junior college athletes: a cluster analysis[END_REF]. Social desirability had less impact on incremental theorists than on entity theorists, because effort, work and training are often valued socially in the sport context. Time spent in sport activities affords opportunities to build sport competencies and, in turn, the practitioners' self-concept of their abilities [START_REF] Slutzky | The link between children's sport participation and self-esteem: Exploring the mediating role of sport self-concept[END_REF]. Sportspersons adopted a daily or frequent practice of training. Consequently, they are more likely to automatically associate sport with training in the TT-IAT.

Furthermore, studies using explicit measures showed that participants with high perceptions of sport competence tended to endorse explicit incre-8 N. Mascret, J.-L. Falconetti, F. Cury Implicit conceptions of sport ability 9 mental beliefs and participants with low perceptions of sport competence tended to endorse entity beliefs (e.g., [START_REF] Biddle | Motivation for physical activity in young people: entity and incremental beliefs concerning athletic ability[END_REF][START_REF] Cury | Perceptions of competence, implicit theory of ability, perception of motivational climate, and achievement goals: a test of the trichotomous conceptualization of endorsement of achievement motivation in the physical education setting[END_REF][START_REF] Moreno | Motivation in the exercise setting: integrating constructs from the approach-avoidance achievement goal framework and self-determination theory[END_REF][START_REF] Ommundsen | Self-handicapping strategies in physical education classes: The influence of implicit theories of the nature of ability and achievement goal orientations[END_REF][START_REF] Wang | Sport ability beliefs, 2x2 achievement goals, and intrinsic motivation: the moderating role of perceived competence in sport and exercise[END_REF]. In line with the literature (e. g., [START_REF] Chian | Motivational profiles of junior college athletes: a cluster analysis[END_REF][START_REF] Wang | Achievement goal profiles in school physical education: differences in self-determination, sport ability beliefs, and physical activity[END_REF], results of the present study showed that sportspersons had higher explicit perceived competence in sport than non-sportspersons. As noted earlier, TT-IAT scores were different between these two groups, evidencing different automatic associations between sport, talent and training. However, explicit perceived competence of sportspersons and non-sportspersons was not correlated with their respective TT-IAT scores. Concerning non-sportspersons, the negative correlation between perceived competence and IAT score was high and in line with explicit literature (e. g., [START_REF] Cury | Perceptions of competence, implicit theory of ability, perception of motivational climate, and achievement goals: a test of the trichotomous conceptualization of endorsement of achievement motivation in the physical education setting[END_REF], but it was not significant principally as a result of the low sample size of this group. Moreover, TT-IAT is not a measure of incremental or entity beliefs, contrary to the explicit CNAAQ-2. IAT was assumed to be a measure of the relative strength of association between concept-attribute pairs [START_REF] Nosek | Understanding and using the Implicit Association Test: II. Method variables and construct validity[END_REF]. For example, our results evidenced the fact that sportspersons automatically associated sport and training in the IAT, but that did not mean the association between sport and talent has been rejected. The results indicated the strength of respondents' automatic preferences for talent relative to training -that is, differential association of talent and training with sport. Consequently, perceived competence may be linked with different patterns of IAT scores, but the lack of association between these measures was somewhat surprising. However, one of the central topics on unconscious processes is the link between implicit and explicit measures (e. g., [START_REF] Greenwald | Implicit social cognition: Attitudes, self-esteem, and stereotypes[END_REF], and the literature on this relationship is inconclusive [START_REF] Fazio | Implicit measures in social cognition research: their meaning and use[END_REF]. Further research is warranted to better understand the relations between explicit measure of perceived competence and implicit measure of conceptions of sport ability. The development of an implicit measure of perceived competence in sport, likely to be less sensitive to social desirability, could also be considered.

In conclusion, the use of an implicit measure like ST-IAT in this study showed that it is useful in order to overcome the social desirability which could appear with non-sportspersons who would not dare confess that they thought sport ability was not improvable and mainly linked to talent, gift and genetics. Furthermore, highlighting beliefs about sport ability with implicit and/or explicit measures is an important way to understand the determinants of practice of sport, especially to identify the reasons why some people do not practise sport and to encourage them to start it.

  Fig. 1 -Screenshot of the ST-IAT.

TABLE I

 I Category Assignment And Stimulus Proportions Across ST-IAT Blocks For An Exemplary Participant

	Block	Trials	Function	Left-key response	Right-key response
	1	20	Practice	Talent words + Sport words	Training words
	2	40	Test	Talent words + Sport words	Training words
	3	20	Practice	Training words + Sport words	Talent words
	4	40	Test	Training words + Sport words	Talent words

N.Mascret, J.-L. Falconetti, F. Cury


A Filipescu
email: adrian.filipescu@ugal.ro

L Dugard
email: luc.dugard@inpg.fr

S Stamatescu

ROBOTS CONTROL BASED ON PARAMETER IDENTIFICATION AND ADAPTIVE GAIN SMOOTH SLIDING OBSERVER-CONTROLLER

Keywords: Robotic manipulators, adaptive gain, smooth sliding observer-controller, parameter identification

Robots control based on parameter identification and adaptive gain smooth sliding observer-controller

Adrian Filipescu, Luc Dugard, Sabin

INTRODUCTION

The state and parameter uncertainties in the model of the rigid robotic manipulators, considered as MIMO non-linear systems, as well as the deviations of the parameters from their nominal values and external disturbances lead to some problems in parameter identification and state estimation. All that makes absolutely necessary the design of the controller and/or the observer such as the closed loop robustness is achieved, stability with small tracking and estimation errors. It is well known that the robustness to model parameter uncertainties and external disturbances of the closed loop can be achieved with a variable structure controller. Maintaining the system on a sliding surface, weakens the influence of the uncertainties in the closed loop performances and quickly leads to an equilibrium point. [START_REF] Filipescu | Smooth variable structure observer-controller with adaptive gains[END_REF], an adaptive variable structure control with parameterized tangent hyperbolic as switching function (denoted k -tanh) with adaptive modifications of its magnitude (denoted as λ -modification) is used, instead of a pure relay one with constant gain.

*corresponding author

In this paper is used also the parameterized tangent hyperbolic function (denoted k -tanh) is used as a switching function in order to alleviate, or/and eliminate chattering. Decreasing the parameter k in the switching function makes the gain around zero smaller and the un-modelled dynamics are excited in a smaller measure at high frequency. Also, the delay due to the control input calculus and the finite rate of switching can lead to chattering. Using the λmodification into the gain of k -tanh switching function, smoothes the response and increases the robustness to structural uncertainties. The adaptive gain is time depending, with the norm of the corresponding sliding surface, as input. Based on a time-varying parameters identification technique presented in [START_REF] Xu | Parameter identification methodology based on variable structure control[END_REF], [START_REF] Xu | VSS theorybased parameter identification scheme for MIMO systems[END_REF] and [START_REF] Xu | A VSS identification scheme for time-varyng parameters[END_REF], we extend the scheme, by introducing, the observer, smooth switching function and adaptive gains. It is then applied to a general model of the robotic manipulator dynamics. The physical robot may have inside the joint, gears and clutches, through the torque supplied by the DC motor is transmitted in order to move the link. For this reason, the general model of the robotics manipulator is involved. We develop a variable structure observer-controller based on the work of [START_REF] Sanchis | Sliding Controller-Sliding Observer Design for Nonlinear Systems[END_REF]. Extensions of sliding control to MIMO non-linear uncertain systems have been made in [START_REF] Khalil | Nonlinear systems[END_REF] and [START_REF] Utkin | Sliding modes in control and optimisation[END_REF]. Several applications of the variable structure control to robotic manipulator controlling point out the robustness to uncertainties and external disturbances of the closed loop [START_REF] Slotine | Tracking control of non-linear systems using sliding surfaces, with applications to robot manipulator[END_REF][START_REF] Canudas De Wit | Sliding observers for robots manipulators[END_REF]. With the ktanh switching function and the λ -modification in the observer-controller gains, the closed loop behaves like an approximate sliding mode, in the neighbourhood of the corresponding sliding surface.

The main contributions of this paper are concerned with: the adaptive smooth sliding observer-controller, the updating law of the variable structure gains, and finally the identification of the time-varying parameters and external disturbances.

The paper is organized as follows. In the Section 2, a general model for the n -degree of freedom robot manipulator and the sliding observer are presented. The smooth sliding observer is designed, the gain updating law is presented and a bound for the estimate error is computed. The design of the adaptive gain smooth sliding controller is performed in Section 3. An upper bound of the tracking error is provided, too. In Section 4, a stable identification scheme of time-varying parameters and external disturbances applied to a n -DOF robotic manipulator is presented. A 2-DOF vertical robotic manipulator, together with closed loop simulation results are presented in the Section5. Some conclusion remarks can be found in Section 6.

ADAPTIVE GAIN SMOOTH SLIDING OBSERVER

A very general model of the robotic manipulator can be expressed as a square non-linear MIMO model

( ) ( ) ( ) [ ] , , , , , , , , , , 1 2 2 1 2 1 1 1 2 1 2 1 p n n n n ℜ ∈ = ℜ ∈ ℜ ∈ + = ℜ ∈ = - p x y u x u p x x g p x x f p x h x x x x & &
(1) where only the vector 1 x is available for measurement, u and y are control input and measured output, respectively. The state space dimension is n 2 and

[ ] n T T T 2 2 1 ℜ ∈ = x x x
is the state vector. , then the system may be feedback linearisable. Let choose as the observer sliding surface as

n o 0 x x S = - = 1 1
ˆ, the observer can be written as

( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) [ ] , , , , , , , , ˆk tanh t ˆ, k tanh t ˆ2 1 2 1 2 1 1 1 o o 2 1 1 2 2 2 o o 1 1 1 1 1 p x x u p x x g p x x f p x h S Θ x x Γ x x S Θ x x Γ x + + + - - = + + - - = - & & (2) where [ ] n 1 11 1 diag γ γ = L Γ , [ ] n 2 21 2 diag γ γ = L Γ with 2 , 1 , 0 = > γ i ij and n j , 1 = . 0 > o k
is a design parameter.

The gains

[ ] n 1 11 1 diag θ θ = L Θ , [ ] 21 21 2 diag θ θ = L Θ
, are time-varying and defined by ( λ -modification is included)

( ) ( ) [ ], diag 1 1 11 11 1 1 1 1 n n x x x x t t - - - - = L & ρ Θ λ Θ (3) ( ) ( ) [ ], diag 1 1 11 11 2 2 2 2 n n x x x x t t - - - - = L & ρ Θ λ Θ (4) where [ ] n 1 11 1 diag λ λ = L λ , [ ] n 2 21 2 diag λ λ = L λ , [ ] n 1 11 1 diag ρ ρ = L ρ , [ ] n 2 21 2 diag ρ ρ = L ρ , with i 1 λ , i 2 λ , i 1 ρ , i 2 ρ , n i , , 1 L = positive constants.
Remark 1: The dynamics (3) and (4) of the switching force the matrices 1 Θ and 2 Θ to the negative values. They are almost zero when the observer is in the neighbourhood of sliding surface. In order to satisfy the attractiveness condition

n i S S oi oi , , 1 , 0 K & = <
, the gain 1 Θ must be chosen such that

( ) ( ) ( ) [ ). 0 , , , 1 , ˆ2 2 1 ∞ ∈ ∀ = - > θ - t n i t x t x t i i i K (5)
By an appropriate choice of the matrices 1 λ and 1 ρ , the above condition at 0 = t remains satisfied for any 0 > t .

If the active torque delivered by the joint DC-motor is considered as the control input, the model of the n -DOF robotic manipulator is

( ) ( ) ( ) , m , m , , m , p p p d u q G q F q q q C q q H + = + + + [ ] T n q q K 1 = q
is the vector of link

K = = x q , [ ] T n x x 2 21 2 K & = = x q
be the angular positions and velocity vectors, respectively. The measurements only concern the link positions 1 x y = . The robot state space representation can be written as

( ) ( ) ( ) . m , m , , m , 2 P 1 2 p 2 1 1 p 1 2 2 1         - - + + - = = - d u Fx x G x x x C x H x x x & & (7)
Taking into account the uncertainties, one can define:

( ) ( ) ( ) , , ˆ1 2 1 1 1 p p m m x H x H x H + = (8) ( ) ( ) ( ) , , , , , ˆ2 1 2 2 1 1 2 1 P p m m x x C x x C x x C + = (9) ( ) ( ) ( ) , , ˆ1 2 1 1 1 p p m m x G x G x G + = (10)
as the estimates of function matrices:

( ) p m , 1 x H , ( ) p m , , 2 1 x x C , ( ) p m , 1 x G
. Without loss of the generality, the friction is considered as a positive constant uncertain diagonal matrix F ˆ.

The following assumptions have to be done: With the above notations the model (6) can be rewritten as

. 2 1 2 1 n 2 1 n       + +       -             -             - =             d u 0 G 0 x x F 0 0 0 x x C 0 I 0 x x H 0 0 I & & (11)
The smooth sliding observer ( k -tanh as switching function), with gains adaptively updated ( λmodification, as in ( 3) and ( 4), is included), is given by the equations

( ) ( ) ( ) ( ) ( ) ( ) [ ] . ˆk tanh t ˆk tanh t ˆ2 2 1 o o 2 1 1 2 2 2 o o 1 1 1 1 1 u G x F x C H S Θ x x Γ x x S Θ x x Γ x - + + - + - - = + + - - = - & & (12)
The smooth switching function allows to consider that the approximate conditions:

0 , 0 ≈ ≈ o o S S
& are satisfied during sliding.

(

)

o o k S tanh
can be expressed from the first equation of ( 12) and replaced in the second. Hence, the estimate error equation can be written as

[ ] [ ] d u G Fx Cx H u G x F x C H x Θ Θ x - - + + + - + + - - = - - - 2 2 1 2 2 1 2 1 1 2 2 & . (13)
Above equation assures the stability of the observer and exponential convergence rate as how is proofed in [START_REF] Sanchis | Sliding Controller-Sliding Observer Design for Nonlinear Systems[END_REF]. Let nxn ℜ ∈ Q be the time varying positive definite matrix defined as

( ) ( ) ( ) ( ) ( ) F x x Θ Θ x H Q , , ˆ2 1 1 1 2 1 + ϑ + = -t t m t p , (14) where ( ) ( ) [ ] 2 2 2 2 1 2 2 1 , , , x x x x x C x x x = ∂ ∂ = ϑ p m , ( 15
) ( ) ( ) ( ) 2 2 1 2 2 1 2 2 1 , , , , , ˆx x x x x x C x x x C ϑ + = p p m m .
(16) Choosing large eigenvalues of Q , the observation error can be globally ultimately bounded (Corollary 5.3 from [START_REF] Khalil | Nonlinear systems[END_REF]. The matrix Q determines the robustness of the observer to the parameter uncertainties. Taking 2 V as a Lyapunov function candidate

( ) 2 1 2 2 , 2 1 x m V p T x H x = , ( 17
)
the derivative can be expressed as

[ ]           - - + + + - - - + ϑ + - = + = - - d u Fx Cx G H H F x C G x F x x Θ Θ H x x H x x H x x ~2 1 Ṽ 2 2 1 2 2 2 2 2 1 1 2 T 2 2 T 2 2 T 2 2 & & & (18)
using the robot equations property ( )

n 2 2 2 1 T 2 , 0 , 2 ˆℜ ∈ ∀ =       - x x x x C H x & (19)
and the notations:

1 1 1 ˆ-- - - = H H H , (20)
( ) ( ) ( ) p p m m , , , , , ~2 1 2 1 2 1 x x C x x C x x C - = , (21)
G G G - = ˆ, F F F - = ˆ. ( 22
)
Let define the vector ( )

2 2 1 , , x x x µ µ = as [ ] 2 2 1 2 2 ˆFx d u Cx G H H x C x F G µ + - - + - - - - = - (23)
and assume that µ is linearly bounded by 2

x :

0 , ~2 > ∀ γ + β ≤ t x µ . ( 24
)
for some 0 , > γ β

, then the derivative of the Lyapunov function is bounded by

( ) 2 2 2 2 2 min 2 2 2 min 2 Ṽ x x x µ x x Q Q ε - ≤ β + γ + λ - ≤ + λ - ≤ & , ( 25
)
where ε is a positive constant satisfying

γ - λ ≤ ε Q inf . ( 26
)
If at 0 = t , the switching gain 1 Θ satisfies (5), both gains 1 Θ , 2 Θ follow the adaptation laws (3) and ( 4), respectively, and the vector µ is bounded, then there exists 0 1 ≥ t such that the velocity estimation error satisfies the inequality ( ) ( )

1 2 2 min max 2 , 0 ~max t t e t t < ∀ λ λ ≤ λ ε - H x x H H . ( 27
)
More, in finite time, the estimation error enters into the ball ( )

r , 0 B
. That means ( )

1 min min max 2 , ~t t r t ≥ ∀ ≤ ε - γ - λ β λ λ ≤ Q H H x , ( 28
)
where the ball radius satisfies the inequality

ε - γ - λ β λ λ ≥ Q H H min min max r . ( 29
)
Remark 2: The adaptation law (3), starting from nonzero initial condition, assures the non-singularity of the gain matrix 1 Θ during sliding. Hence, the matrix Q can be computed all the time using the expression (14). The ultimate bound r satisfying (29) is smaller if

Q min λ
is greater, i.e., if the initial value of 1 Θ is chosen smaller than 2 Θ .

ADAPTIVE GAIN SMOOTH SLIDING CONTROLLER

The controller is defined assuming only that the state 1

x is known and that the state 2 x is provided by the observer. Corresponding to the n -dimensional control input, the controller sliding surface is defined as

( ) ( ) ( ) ( ) ) ( ) t t t t r r c y x ψ y x x x S - + - = 1 2 2 1 , ˆ& , (30)
where

( ) t r y
represents the trajectory to be tracked. The matrix

[ ] n ψ ψ = K 1 diag ψ , with positive constants, n i i , , 1 , L = ψ
, determines the dynamics during sliding. The sliding surface is attractive if the following condition holds

n i S S ci ci , , 1 , 0 ˆK & = < . ( 31
)
The time derivative of the sliding surface can be written as

( ) ( ) ( ) ( ) ( ) [ ] ( ) r 2 r 2 1 2 1 2 1 1 p 1 r 1 2 r 1 2 c , , , , , , ˆm , ˆy x ψ y p x x u p x x g p x x f x h y x ψ y x - + - + = - + - = - (32)
If k -tanh is used as the switching function and if the diagonal matrix

[ ] n η η = L 1 diag η is taken time depending, including the λ -modification, ( ) ( ) [ ] cn c c c S S t t diag 1 L & ρ η λ η - - = , (33)
the controller which fulfils the sliding

condition 0 ˆ= c S &
can be expressed as

( ) ( ) ( ) ( ) ( ) ( ) [ ] r 2 r c c c 1 2 1 1 2 1 k tanh t ˆ, , , , , ˆy x ψ y S η S ψ p x h p x x g p x x f u & & & - - + + - + - = - , (34)
where the matrices:

[ ] cn c c λ λ = L 1 diag λ , [ ] cn c c ρ ρ = L 1 diag ρ are positive definite. The term c S ψ -
is introduced for reducing the controller to classical feedback linearization one [START_REF] Marino | Non-linear control design[END_REF] if the switching term is set to zero.

Despite the calculus of the control input for n -DOF robotic manipulator, to fulfil the attractiveness condition (31), it is necessary to express the derivative of the sliding surface (30)

( ) ( ) ( ) ( ) [ ] ( ) r 2 r p 1 2 2 p 2 1 1 p 1 r 2 r 2 c ˆm , x m , , ˆm , ŷ x ψ y u x G F x x x C x H y x ψ y x S - + - - + + - = - + - = - . ( 35
)
Similarly as for the observer, by the using k -tanh as a switching function and the λ -modification into the gain, the sliding condition is fulfilled if the control input is chosen as:

( ) ( ) ( ) ( ) ( ) ( )         - - + + - + + + = r 2 r c c c p 1 p 1 2 2 p 2 1 ˆk tanh t m , ˆm , m , , ˆy x ψ y S η S ψ x H x G x F x x x C u & & & . ( 36
)
The controller switching gain ( )

t η
is adaptively updated as in (33).

Remark 3: The observer error is nonzero if a k -tanh function is used as a switching function in the observer equations. The controller sliding surface c S ˆ can still be attractive by choosing sufficiently large initial values for the switching gains 1 Θ and 2 Θ . Moreover, the tracking error does not go to zero on controller sliding surface, because the smooth controller is used ( k -tanh switching function).

Remark 4: In order to reduce the influence of velocity estimation error in the control input, the relative weight of the states 2

x in the definition of the sliding surface should be decreased. This explains the introduction of the supplementary term c S ψin the control input. The increasing of the parameter ψ is limited by the switching frequency and possible measurement noise.

By the using (13), the derivative of the sliding surface (30) can be expressed as

( ) ( ) ( ) ( ) ( ) 2 1 1 2 c c c c t t k tanh t ˆx ψ Θ Θ S ψ S η S - + - = - & . ( 37
)
If the gain ( )

t η satisfies the inequality ( ) ( ) ( ) ( ) [ ] n 1 i , t , x t t t S ˆi 2 1 1 2 i ci i K = ∀ ψ - Θ Θ ≥ η - ψ - , (38)
then the attractiveness condition is verified. Because 1 Θ and 2 Θ are diagonal matrices, the inequality (38) can be written as

( ) ( ) ( ) n 1 i , t , x tt t S ˆi 2 i i 1 i 2 i ci i K = ∀         ψ - θ θ ≥ η - ψ .( 39
)
Remark 5: The initial value of the switching controller gain must be defined to guarantee the sliding condition after convergence of the observer, when the error in state estimates is bounded by (28).

The term c S ψ ˆ maintains the sliding variable bounded during the observer transient. This leads to

( ) ( ) ( ) ( ) γ - λ β λ λ ψ - θ θ ≥ η - Q H H min min max 1 2 i o i o i o i t t t . (40)
By an appropriate choice of c λ and c ρ with respect to 1 λ , 2 λ , 1 ρ and 2 ρ , the above condition can be satisfied all the time.

Expressing the control input sliding condition as ( )

2 1 2 x y x ψ y x - = - + - r r & , (41)
where the true velocity state is introduced, and taking into account (28), a bound of the tracking error can be obtained ( )

1 min min max , 1 t t y x i ri i > ∀ γ - λ β λ λ ψ ≤ - Q H H . ( 42
)
Remark 6: The actual value of 1 t depends on the convergence rate of the observer, and on the time defined by the gain matrix ψ . The, observer and the controller, both of them into a smoothed form, can achieve high performance. By choosing the value of the constant o k greater than c k , the smooth switching function of the observer is closer to a pure relay than the smooth switching function of the controller. Therefore, the observer converges faster than the controller with small estimate error. The state estimates could be chattering-free, independent by of the value of the gains 1 Θ and 2 Θ . More, by choosing the matrices 1 Θ and 2 Θ adaptively updated as in ( 3) and ( 4), the magnitudes of the switching function go to small values while link position errors go to small values.

Remark 7: During sliding, the error . ˆ1 1 x x S -= o is approximately zero. The derivate is not exactly zero, but it is a high frequency signal of average approximately zero, with an amplitude depending of 1 Θ . If the gain 1 Θ goes to zero, the derivative of the velocity estimation error goes to zero or becomes very small. That means a reduced observation error even in the presence of parameter uncertainties. Also, the behaviour of the controller is similar with that of the full state measurements if its switching is based on a smooth variable. The smooth controller means a reduced or free chattering for the control input law and/or the output.

PARAMETER IDENTIFICATION BASED ON SMOOTH SLIDING OBSERVER-CONTROLLER

The way followed for the time-varying parameter identification is quite different from that proposed by [START_REF] Xu | A VSS identification scheme for time-varyng parameters[END_REF]. Firstly, it is based on the state estimates and on the faster convergence of the observer than the controller. Secondly, it is based on smooth sliding observer-controller, both of them having adaptive switching gain. Zero or small state estimate error leads to zero or small tracking error and small gains of the corresponding switching function. Consequently, during sliding the weight of the switching term is negligible with respect to the compensation part. Define as the parameter vector estimate with p ˆ. If the functions f , g and h are linear in time-varying parameters, each term of the system (1) can be expressed as follows:

( ) ( ) ( ) ( ) ( ) ( ) t ˆ, ˆ1 1 n nx 2 1 2 1 n nx n 2 1 1 1 2 1 1 nxn nxn n p p p x x h 0 0 x x h x x x p x h 0 0 I         ϕ +       =             - ( ) ( ) ( ) ( ) ( ) ( ) t , ˆ, ˆ, , ˆˆ2 1 n nx 2 1 2 1 n nx n 2 1 1 2 2 1 2 p p p x x f 0 0 x x f x p x x f x         ϕ +       =       - - , (44)
( ) ( ) ( )( ) t , , , , , , ˆ2 1 3 2 1 1 n n 2 1 nxn nxn n p u x x Φ u x x g 0 u 0 p x x g 0 0 I +       =             (45)
Define the followings matrices and vectors:

( ) ( )       = p x h 0 0 I p x H , , ˆ1 1 0 nxn nxn n , ( 46
) ( ) ( )       = 2 1 1 1 2 1 2 1 0 , , , ˆx x h x x x x x h ( ) ( ) ( ) ( )         ϕ = - - 1 1 2 1 2 1 2 1 2 1 1 , , , ˆp p n nx n nx n x x h 0 0 x x x x ( ) ( )       = p x x f x p x x f , , ˆ, , ˆ2 1 2 2 1 0 , ( ) ( )       = 2 1 1 2 2 1 01 , ˆ, ˆx x f x x x f , ( 49
) ( ) ( ) ( ) ( )         ϕ = - - 2 1 2 1 2 1 2 1 2 , , ˆp p n nx n nx n x x f 0 0 x x Φ , ( 50
) ( ) ( )       = p x x g 0 0 I p x x G , , , , ˆ2 1 2 1 0 nxn nxn n , ( 51
) ( ) ( )       = u x x g 0 u x x g , , , , ˆ2 1 1 2 1 n o , ( 52
)
In the relationships ( 46),…,(52

), 0 Ĥ , 0 Ĝ are n nx2 2 matrices, 1 Φ , 2 Φ , 3 Φ are p nxn 2 matrices
and 0 f , 01 f , 0 ĝ , 0 ĥ are n 2 vectors. With the above notations the robot model can by expressed compactly by:

( ) ( ) ( ) 0 2 1 0 2 1 0 1 0 , , , , ˆu p x x G x x f x p x H + = & , (53)
where

[ ] T T T n u 0 u 0 = .
Assumption 4: To each element

i i i p p p ≤ ≤ . ( 54
)
Assumption 5: There exist bounding functions ( )

1 x α ,
( )

1 ˆx α such that ( ) ( ) ( ) ( ) ( ) ( ) [ ] [ ). 0 t , p p p , , , , , ˆ, , , min min p i i i n n 1 1 1 1 0 1 1 1 1 1 0 1 1 ∞ ∈ ∀ ∈ ∀ ℜ ∈ ∀ ℜ ∈ ∀ α ≤ ≤ α ≤ ≤ - - - - p x x p x H p x h x p x H p x h (55)
Assumption 6: There exist n nx2 2 function matrices, structured as follows:

( ) ( )       = 2 1 01 2 1 01 , , ˆx x g 0 0 I x x G nxn nxn n (56)
of full rank, and

( ) ( )       = p x x g 0 0 0 p x x G , , , , ˆ2 1 02 2 1 02 nxn nxn nxn , ( 57
) with ( ) ( )p x x p x x , , , 2 1 02 2 1 02 ij ij g g = , such that ( ) ( ) ( ) [ ] p x x G I x x G p x x G , , , ˆ, , ˆ2 1 02 n 2 2 1 01 2 1 0 + = . ( 58
)
Assumption 7: There is a positive constant σ such that

n T ℜ ∈ ∀ σ ≥ - v v v g h v , ˆ2 1 . ( 59
)
Define the matrix ( )

3 2 1 2 1 2 1 , , , , ˆΦ Φ Φ u x x x x Φ + + - = & & ( 60
)
and the vector ( )

0 0 0 2 1 2 1 , , , , ˆg f h u x x x x ω - - = & & (61) of p nxn 2
and n 2 -dimension, respectively. Suppose that Φ Φ T is a nonsingular matrix, then the parameter estimate p ˆ can be computed as the minimum residuum solution of the system

ω p Φ ) = ˆ. ( 62
)
In order ensure the boundedness of p ˆ, the following scheme is used for computing the parameter estimate

( ) ( ) ( ) ( ) [ ] ( )                  >       ∈             <       = - - - - . p îf p , p p îf ˆ, p îf p t p ˆmax max min min min min i i T 1 T i i i i T 1 T i T 1 T i i T 1 T i i ω Φ Φ Φ ω Φ Φ Φ ω Φ Φ Φ ω Φ Φ Φ (63)
With the observer (2) and the control law (34), both of them having smooth switching term and gains adaptively updated, the neighborhood of the controller sliding surface (30) can be reached in finite time.

The following Lyapunov function has been chosen

2 ˆc T c V S S = . ( 64
)
The controller sliding surface (30) depends on the tracking error vector (reference tracking and velocity tracking)

( ) ( ) [ ] T T r T r r 2 1 x y x y x x e - - = - = & . ( 65
)
The derivative of the Lyapunov function can be expressed as

( )

x y e S S e e S S S S -

∂ ∂ = ∂ ∂ = = r c T c c c c T c V . ( 66
)
Using the equality (53), the above derivative function can be written as

( ) u G H f H y e S S 0 1 0 0 1 0 - - - - ∂ ∂ = r c T c V & & . ( 67
)
The smooth sliding controller (32) can be expressed as the sum of two terms,

s c u u u + = , (68)
where

( ) ( )( ) ( ) [ ] r 2 r c 1 2 1 1 2 1 c ˆ, , , , , ˆy x ψ y S ψ p x h p x x g p x x f u - - + - + - = - (69)
is the compensation part, and

( )( )( ) ( ) c c s k t S η p x h p x x g u tanh , , , ˆ1 2 1 1 - = (70)
is the switching part. Using (58) and the block diagonal form of the matrices, the compensation part can be further expressed as

[ ] [ ] ( ) [ ] p Φ Φ x h f y g I g u 2 1 2 2 2 1 1 r 1 02 n 01 c - - + - + = , (71)
where

( ) ( )      ϕ = - 1 1 2 1 2 2 1 ˆp n nx x x h Φ & , ( ) ( )      ϕ = - 2 1 2 1 2 2 2 , ˆp n nx x x f Φ are p nxn matrices
which hold the second block row of the matrices 1 Φ and 2 Φ , respectively.

In order to re-write the variable structure term, the c c k S tanh whilst the system evolution is in a neighbourhood of the sliding surface, the attractiveness condition is satisfied, the switching gain ( )

- - = L π (72)
and using the relationships ( 64), (55), and ( 59), there exists a positive constant ξ such that

( ) ( ) ( ) ( ) ( ) ( ) [ ] ( ) [ ) ∞ ∈ ∀ σ ξ + α ≤ - 0 t , k tanh k tanh k tanh ˆt , , , ˆc c T c c c c 1 2 1 1 S S S π Φ η p x h p x x g . ( 73
)
The variable structure part can be re-expressed as

( ) ( ) ( ) [ ] ( ) ( ) c c c c T c c c c s k k k k S S S S π Φ u tanh tanh tanh tanh σ ξ + α = . (74)
With these components of the controller, taking into account the particular structure of the function matrices and vectors ( 46)…( 52), the derivative of the Lyapunov function may be expressed as

( ) [ ] [ ] [ ] ( ) [ ] ( ) [ ] ( ) [ ] [ ] [ ] [ ] ( ) [ ] ( ) [ ] [ ] ( ) ( ) ( ) ( ) [ ] ( ) ( ) [ ] ( ) ( ) ( ) ( ) ( ) [ ] ( ) ( ) [ ] ( ) ( ).
g I g p Φ Φ f x h h S u g h S u g I g p Φ f p Φ x h h S ξ - ≤ σ ξ + α - α ≤ σ ξ + α - - - + = -         - + + - - + - = -         + - - - + = - - - - - - - (75) Defining the set       ≤ c c k 1 Ŝ
, we can say that there exists some 0 ≥ T such that

[ ) T t , 0 ∈ ∀ , ( ) c c k t 1 ˆ> S and ( ) t c S ˆ
will be strictly decreasing until it reaches the set in finite time and remains inside thereafter (for T t ≥ ).

Particularizing the above relationships for n -degree of freedom robot manipulator, considering the estimates of the velocities and the uncertainties in the parameters, the robot model (11) becomes

      +       +       + -       + + - =       +       d 0 u 0 G x C 0 G x F x C x H 0 x H x n n p 2 2 2 n 1 2 2 1 2 p 2 n 2 1 1 m ˆm & & . (76)
Define the n nx2 2 matrices and n 2 vectors, respectively

      = H 0 0 I H 0 nxn nxn n ,       = 2 1 1 0 x H x h & & , (77)
( ) ( )        = - - 1 2 2 1 1 ˆp p n nx n nx n 0 x H 0 0 Φ & , ( 78
)       - - - = G x F x C x f 2 2 2 0 ,       - - - = 1 2 2 1 2 01 Ĝ x F x C x f , (79) ( ) ( )        - - = - - 1 2 2 2 1 2 ˆp p n nx n nx n 1 G x C 0 0 Φ , ( 80
)       = n nxn nxn n I 0 0 I G 0 ˆ, ( )       = u 0 u x x g , , ˆ2 1 0 n , ( 81
) ( ) ( )         = - - 1 1 3 ˆp p n nx n n nx nxn 0 0 0 0 Φ . ( 82
)
This allows to rewrite as

u G f x x H 0 0 2 1 0 + =       & & (83)
or equivalently as

p Φ g p Φ f p Φ h 3 0 2 01 1 0 + + + = + . (84)
Remark 8: The smooth sliding controller allows the using of the compensation part as equivalent control input signal during sliding. The adaptive gain of the controller switching term goes to zero or becomes very small, depending on the error in the state estimate. Therefore, the influence of the noise induced by control input acquisition is very small in the parameter estimate.

Remark 9: In closed loop, the robustness to uncertainties makes insensitive the stability to phase lag induced by the filters used to compute the derivatives of the state estimate.

Remark 10: As emphasized in [START_REF] Xu | A VSS identification scheme for time-varyng parameters[END_REF], the reference signal has to be chosen in order to avoid the singularity of the matrix Φ Φ T .

CLOSED LOOP SIMULATION

A two degree of freedom vertical robot with two rigid revolute joints, two rigid links, a time varying payload ( ) t m p and an additive disturbance ( )

+ + + +       + + + = x H , (86) ( ) ( )                     - - - +       - -
+ + + +       + + + = x G (88) [ ] 10 10 diag = F , (89)
( ) [ ] ( ) [ ] ( ) [ ]                   + + + + + = 22
( ) [ ] ( ) [ ] ( ) [ ]             + + + + + = 0 cos 1 0 cos 1 cos 2 2 0 0 0 0 22 21 12 22 12 21 12 1 x x x x x x x ( ) ( ) ( ) ( ) ( ) ( ) ( )                               - + - - - + - - + + =
( ) ( ) ( ) ( ) ( ) ( ) ( )                     + - - + - - + + =

  1, the closed loop simulated manipulator response is shown. Adaptive gains, smooth sliding observer-controller and time varying parameter have been introduced into the loop. Small parameter uncertainties (5%) have been considered. By choosing o k greater than c k , a faster sliding observer convergence than that of the sliding controller has been obtained. The response is free of chattering, although limitations have been introduced into reference signal was chosen in order to avoid the singularity of the matrix Φ Φ T . In order to compute the derivatives of the state estimate the first order numerical difference has been used. The phase lag does not lead to instability and fluctuation in the parameter estimates.

Fig. 1 .Fig. 2 .

 12 Fig. 1. Closed loop robot response, smooth sliding observer and controller, parameterized tangent hyperbolic switching function 10 = o k , 1 = c k .

& & & & &(6)where

& & & & & & & &

& & & & & , (43)

& & & & ,(47)

& & & ,(48)

& & & & &

& & &

& & &

& & &

& & & &

& & & Φ(91)


Metric Strand Spaces for Locale Authentication Protocols

F. Javier Thayer, Vipin Swarup, and Joshua D. Guttman

The MITRE Corporation, USA {jt,swarup,guttman}@mitre.org

Abstract. Location-dependent services are services that adapt their behavior based on the locations of mobile devices. For many applications, it is critical that location-dependent services use trustworthy device locations, namely locations that are both accurate and recent. These properties are captured by a security goal called locale authentication whereby an entity can authenticate the physical location of a device, even in the presence of malicious adversaries. In this paper, we present a systematic technique for verifying that location discovery protocols satisfy this security goal. We base our work on the strand space theory which provides a framework for determining which security goals a cryptographic protocol achieves. We extend this theory with a metric that captures the geometric properties of time and space. We use the extended theory to prove that several prominent location discovery protocols including GPS do not satisfy the locale authentication goal. We also analyze a location discovery protocol that does satisfy the goal under some reasonable assumptions.

Introduction

Location-dependent services have been well-studied and are widely expected to become an integral part of the pervasive computing infrastructure. These services adapt their behavior depending on the current locations of mobile devices. Device locations are provided by location discovery protocols. Security is a major concern in these systems and a wide variety of security goals have been studied in the literature, e.g., the privacy, freshness, and availability of location information. In this paper, we focus on the threat of malicious users deceiving location-dependent services by providing incorrect or stale location data. They may do this by subverting or bypassing the location discovery protocols.

Robustness against this threat is captured by the security goal of locale authentication whereby an entity can authenticate the physical location of a device, even in the presence of malicious adversaries. The entity can then issue a locale certificate that asserts that principal P has a physical presence at location (or within region) x at some time during a time interval t. A node that wishes to use this attribute certificate must verify the certificate by checking its signature and determining whether the creator is trusted to have used a secure locale authentication protocol to authenticate the stated location.

Locale certificates are indeed feasible. Consider a person P who needs a certificate stating that she is at the physical address x at time t. P contacts a certificate granting authority which then dispatches a human agent to P 's claimed location. The agent validates P 's identity and secret key (which we assume P has previously obtained), verifies P 's location at time t, and issues a document to P with this information and bearing the certificate authority's signature. Clearly this scheme is impractical since it requires a human to service each request, but it illustrates that the concept of a locale certificate is feasible.

A potentially better alternative is to provide each user with a tamper-proof GPS locator device that discovers and certifies the user's location. Such devices have been developed [START_REF] Denning | Location-based authentication: Grounding cyberspace for better security[END_REF]. However, as we show in Section 7.2, any GPS device which relies exclusively on the commercial GPS external signal can be attacked and hence is inadequate for locale authentication in sensitive applications.

In this paper, we provide a precise definition of locale authentication and we present a systematic technique for proving whether or not location discovery protocols satisfy the locale authentication goal. Our work is based on the strand space theory which provides a framework for determining what security goals a cryptographic protocol achieves. Strand spaces are a special-purpose execution model for security protocols, based on a Lamport-style causal partial ordering. Behaviors of some principals, "regular principals," are assumed to follow the rules of the protocol, while others, adversarial principals, do whatever they like, constrained by cryptography and the secrets they possess.

The key notion is a possible global execution, or "bundle," namely a causally well-founded directed acyclic graph, in which the nodes are message transmissions or receptions. The nodes may lie on any number of regular or adversarial behaviors. Every message reception must be explained by some earlier transmission of the same message. Causal well-foundedness justifies a principle of induction for bundles, which is the basis of powerful and reusable proof techniques. Strand spaces were intended to capture a minimal view of protocol behavior, leading to conceptually spare and focused analysis techniques.

Secure location protocols combine cryptography with the physics of message transmission. The cryptographic operations authenticate the principals and preserve confidentiality, while the physics of message transmission constrain their possible locations. We enrich the strand space model by associating a spacetime location with each node. The strands follow the world lines of principals. Some bundles are compatible with the physics of message transmission -e.g. the maximum message transmission speed -while others are not. An assertion true in every bundle compatible with the physics is a valid conclusion of a secure location protocol. We use this extended theory to prove that several prominent location discovery protocols including GPS do not satisfy the locale authentication goal. We also analyze a location discovery protocol that does satisfy the goal under some reasonable assumptions.

The remainder of this paper is organized as follows. In Section 3, we review related work. In Section 4, we summarize a broad range of security goals for location discovery protocols. We then focus on the goal of locale authentication and we describe our threat model and attack classes that compromise this goal. In Section 5, we present the metric strand space model. In Section 6, we consider four prominent location discovery protocols and we use the metric strand space model to examine whether they provide locale authentication under a specified threat model. Section 8 concludes the paper with a discussion of future directions for this novel line of work.

Some Examples

Consider a client device intended to participate in secure location protocols. It contains a private asymmetric key, and the manufacturer provides a certificate binding the public part of the same key pair to the identity of the purchaser. The device has some tamperproofing, to ensure that it is unlikely to have been subverted without effort on the part of the owner, and certainly not unbeknownst to the owner. The behavior of the device is as follows. When the owner specifies a number of location servers, the device interacts with them so that they can jointly provide evidence of the device's location.

The interaction between the device and the servers consists of two phases. First, a cryptographic protocol allows the device and server to agree on a pair of new shared secrets. This phase uses asymmetric cryptography and is thus expected to be slow. Second, the server transmits a random bitstring; when the device receives it, the device does a bitwise exclusive or with one shared secret, and replies with the result. This operation is very fast. The device also emits an estimate of the time t δ elapsed between receipt and reply; the estimate is encrypted with the other shared secret. The server calculates the elapsed time t between transmitting the challenge and receiving the xor ed response; it then certifies that the distance to the device is approximately c • (t -t δ )/2, where c is the transmission speed in this medium. If the location of each server is known, and the device interacts with a suitable number of servers within a short period of time, then the location of the device on the surface of the earth or in three-dimensional space may be determined.

For the first phase of interaction, we use the Needham-Schroeder-Lowe protocol, taking the resulting shared secrets to be the two nonces. The full protocol is shown in Figure 1. Evidently, if it were possible for a third party to determine the nonces, then with judicious jamming, it may be possible for the third party to convince L that D is at the third party's location. For instance, if the protocol were based on the original, flawed Needham-Schroeder protocol instead of the version as fixed by Lowe, then an attack would be possible (Figures 2,3). In this scenario, the owner has asked its device to determine its distance from P , a location server that turns out to act fraudulently; P can then surely convince an honest location server that D is where P is. By suitable choices of t δ , probably any distance can be established.

D {|N d ˆD|}L - {|N d ˆD|}L -L • {|N d ˆK ˆL|}D {|N d ˆK ˆL|}D • • {|K|}L - {|K|}L -• • N N • • t δ N ⊕ N d - N ⊕ N d -• t • {|N ˆtδ |}K - {|N ˆtδ |}K -• Fig. 1. A Distance-determining Protocol D {|N d ˆD|}L - {|N d ˆD|}L -L • {|N d ˆK|}D {|N d ˆK|}D • • {|K|}L - {|K|}L -• • N N • • t δ N ⊕ N d - N ⊕ N d -• t • {|N ˆtδ |}K - {|N ˆtδ |}K -• Fig. 2. A Flawed Distance-determining Protocol D {|N d ˆD|}P -P • {|N d ˆD|}L -L • {|N d ˆK|}D • • {|K|}P -P • {|K|}L -• • N • • N ⊕ N d -• t • {|N ˆt|}K -• Fig. 3. An Attack on the Protocol of Figure 2
Thus, in protocols of this kind, there is a tight interconnection between the structure of the cryptographic protocol-the way that it uses cryptography to establish authentication and shared secrets-and its usefulness to determine location.

Related Work

A wide variety of location discovery protocols (e.g., [START_REF]Secure Localization and Time Synchronization for Wireless Sensor and Ad Hoc Networks[END_REF]) have been proposed in the literature. Some protocols let a device compute its own location, some let a server compute the location of a device for the server's own use, and some let a server or device convince a third party of a device's location. The protocols may be passive where the load on location servers is independent of the number of protocol runs, or active where the server load is a function of the number of protocol runs (e.g., if the server has to respond to messages sent by devices).

Location discovery protocols compute the location of a device by using a distributed set of servers whose locations are known precisely. Distance bounding protocols [START_REF] Brands | Distance-bounding protocols[END_REF] typically use distance or angle measurements of signal transmissions between the servers and the device, and they solve for the unknown location using triangulation (or multilateration) techniques. Distance measurements are made by either measuring the signal strength of a received signal or by measuring the arrival times of one or more signals. Signal strength measurements are converted to distance measurements by knowing the power of the transmitted signal and by modeling its expected strength at various locations [START_REF] Bahl | Radar: An in-building RF-based user location and tracking system[END_REF]. Arrival times are converted to distance measurements by knowing the time of signal transmission and the propagation speed within the transmission medium [START_REF] Hofmann-Wellenhof | The Global Positioning System: Theory and Practice[END_REF]. Alternatively, if two signals with different propagation speeds are transmitted simultaneously, then the distance can be computed without knowing the actual transmission time of the signals [START_REF] Priyantha | The cricket compass for context-aware mobile applications[END_REF]. Angle measurements are made by using special antenna configurations that measure the angle of arrival of a signal.

The most prominent location discovery system is the Global Positioning System (GPS). In this scheme, multiple synchronized satellites transmit periodic messages; a device that receives transmissions from several satellites can use the signals to triangulate its own position. Denning and MacDoran [START_REF] Denning | Location-based authentication: Grounding cyberspace for better security[END_REF] have proposed building a locale authentication service using GPS signals. They suggest that a device can capture the signals it receives from multiple satellites and can package the received signals into a credential. A trusted server can verify that the signals have not been tampered with, and can use the signals to compute the device's position. As we prove in Section 7.2, such a scheme is not secure if the GPS geometry is public knowledge, e.g., as with commercial GPS.

Sastry et al [START_REF] Sastry | Secure verification of location claims[END_REF] and Capkun et al [START_REF] Capkun | SECTOR: Secure tracking of node encounters in multi-hop wireless networks[END_REF] analyze protocols that can securely verify certain location claims. Their analyses are specific to their respective proposed protocols. Further, they only address the question of whether some arbitrary user is in a designated physical region. In contrast, in this paper we present a general, systematic model for verifying the security properties of any location discovery protocol. We apply this technique to several protocols, includ-ing a protocol that addresses the question of whether a specific user (i.e., a user with a specific secret key) is in a designated physical region. Meadows et al [START_REF] Meadows | Distance bounding protocols: Authentication logic analysis and collusion attacks[END_REF] present a qualitative framework for analyzing distance bounding protocols based on extending an authentication logic and is closest in spirit to our work.

Security for Location Discovery Protocols

Let N, M, P, and Q be principals (e.g., cryptographic keys, mobile nodes with identities, etc.), L be a physical location (or region), and t be a time interval. Some of N, M, P, and Q may possibly be the same principal. If a principal P has a physical presence at a location L (e.g., if P has access to a node at L), then we say that "P is at L" or that "P controls L".

The purpose of a location discovery protocol is to enable M to determine the location of N during t. However, location discovery protocols are subject to attacks by malicious penetrators. In this section, we examine a range of desirable security goals for location discovery protocols, and a set of attacks that may compromise those goals.

Security Goals

Desirable security goals for location discovery protocols include:

Locale Occupancy Authentication: If M determines that some principal was at L during t, then there was indeed a principal at L during t. Locale Authentication: If M determines that N was at L during t, then N was indeed at L during t. Thus, a penetrator cannot make M believe that N is at a location other than N's true location. Privacy: An unauthorized penetrator (e.g., an eavesdropping node) cannot obtain location information via a location discovery protocol. For instance, if M uses a location discovery protocol to determine that N is at L during t, then penetrator P should not be able to learn that N is at L during t. Availability: An authorized principal M can determine N's location at any time. Thus, a penetrator cannot prevent M from determining N's location. Nonrepudiation: Evidence that N was at L during t is irrefutable. With such evidence, M can prove to Q that N was at L during t.

Most of the literature on location discovery protocols addresses the functionality of the protocols, namely enabling M to determine the location of N during time interval t. Some techniques enable a node to determine its own location (e.g., [START_REF] Hofmann-Wellenhof | The Global Positioning System: Theory and Practice[END_REF], [START_REF] Priyantha | The cricket compass for context-aware mobile applications[END_REF]), while others enable a node to determine the location of another node (e.g., by measuring signal strengths [START_REF] Bahl | Radar: An in-building RF-based user location and tracking system[END_REF] or round-trip ping times). Some techniques address the privacy and availability goals, but most do not satisfy the goals of authentication or nonrepudiation.

Threat Model and Attacks

We distinguish between various threats based on the locations that are controlled by penetrators. Control of a location may enable a penetrator to monitor, delay, alter, delete, redirect, or replay any signals (message transmissions) that traverse that location or its immediate neighborhood. However, in this paper, we assume that a penetrator cannot block broadcast transmissions between two neighboring nodes that the penetrator does not control. Note that some penetrators may only control a small number of locations (e.g., a soldier in enemy territory). Some penetrators may control an entire physical region (e.g., an enemy state that controls some territory). Some penetrators ("insiders") may control some nodes used by location discovery protocols, e.g., trusted location servers.

Location discovery protocols are subject to a wide range of attacks. For instance, a penetrator may deny that he was at location L during time t, a penetrator may prevent M from determining N's location, a penetrator may monitor the location discovery protocol to learn the location of a user, etc. In this paper, however, we focus only on attacks on authentication. There are two broad types of attacks.

Location integrity attacks may cause M to believe that N is at location L, even though N does not have a physical presence at L. Two special cases of this attack are: (a) deception attacks where a penetrator P causes M to believe that P is at location L, even though that is not the case; and (b) positioning attacks where a penetrator P causes M to believe that M is at location L, even though that is not the case. Note that, depending on the attack, the penetrator may or not be able to select the location L.

Masquerade attacks by a penetrator P at L may cause M to believe that the penetrator is N at L. Note that a penetrator P at L may launch a combination masquerade and location integrity attack to cause M to believe that N is at L'.

Metric Strand Spaces

We now extend the formalism of strand spaces [START_REF] Thayer Fábrega | Strand spaces: Proving security protocols correct[END_REF] (see Appendix A for a summary of the strand space theory). The extended theory will enable us to prove whether a location discovery protocol is secure against location integrity and masquerade attacks. In our intended application, a strand will model a sequence of events in a process or in a processor.

We assume that all nodes are subject to physical constraints dictated by the laws of nature as we understand them. We use two laws in this paper. First, a message must be sent before it is received. Second, messages cannot travel faster than the signal speed in the medium of transmission (e.g., the speed of sound in water, or the speed of light). We also assume an idealized model of message transmission; specifically, we assume that broadcast messages are transmitted by a spherical wavefront.

A partial pseudometric on a set X is a partial function d with non-negative real values on X × X such that d(x, x) = 0, d(x, y) = d(y, x) when either side is defined, and the triangle inequality d(x, y) ≤ d(x, z) + d(z, y) holds when d(x, y), d(x, z), d(z, y) are all defined.

A time elapse function on a partially ordered set (X, ) is a partial function e with non-negative real values defined on pairs x, y where x y such that e(x, x) = 0 and with the additivity property: e(x, y) = e(x, z) + e(z, y)

whenever x z y.

Recall that for nodes m, m in a single strand of a strand space, m ⇒ * m means there is a sequence of intermediate nodes m ⇒ m 1 ⇒ m 2 ⇒ • • • ⇒ m , all on the same strand. Definition 1. A geometric bundle is a tuple (B, dist, elapse, c) where B is a bundle, dist is a partial pseudometric on nodes(B), elapse is a time elapse function on pairs m, n ∈ nodes(B) such that m ⇒ * n, and c is a positive real.

Notice that it is possible for different nodes m, n to be within 0 distance of each other. For instance, if the strand s is associated to a static object, then all nodes on s are within 0 distance of each other. However, we can obtain a metric space X from X = nodes(B), by identifying points m, n which are at 0 distance from each other. The space X and the quotient map x → x completely determine X. We will refer to X as the geometry of the bundle, c as the message propagation speed, and elapse as the elapsed time between successive events on a strand. We need to relate the metric and the elapsed time function:

Axiom 1 Suppose m 1 → n 1 ⇒ * m 2 → • • • ⇒ * m k → n k is
a path in the bundle such that m 1 , n k are on the same strand and dist(m k , n k ) are all defined. Then

elapse(m 1 , n k ) = 1 c k i=1 dist(m i , n i ) + k-1 =1 elapse(n , m +1 ). (2)
In this paper, elapse will be interpreted as elapsed time with respect to a global clock. A global time on a bundle is a function T : nodes

(B) → R such that elapse(m, n) = T(m) -T(n).
Given a geometric bundle with global time, we will use terms such as propagation time, propagation distance, etc. If strands may be associated with mobile objects, we need to relate the metric and the elapsed time function for nodes on a single strand: dist(m, n) ≤ v × elapse(m, n) where m ⇒ * n and where v is a positive real that represents the maximum speed of any object. However, for simplicity, we assume in this paper that all nodes on a strand have the same location (the results in this paper can be extended easily to deal with mobile objects by using the above axiom). This corresponds to strands being associated with static objects and is captured by the following definition: Definition 2. A static geometric bundle is a geometric bundle (B, dist, elapse, c) where for all pairs m, n ∈ nodes(B) such that m ⇒ * n, dist(m, n) = 0.

Security Analysis of Location Protocols

We now give several illustrative examples of protocols, with precise locale authentication claims and proofs.

Protocol 1

This first protocol is ancient. It is typically used in the inverse direction to empirically determine the medium propagation speed c from the known distance.

The initiator A sends a nonce N a and expects return N a . Responder returns N a . There are thus two kinds of strands in this protocol:

1. Initiator strands s = m 1 , m 2 ∈ Init[N a ] with trace +N a , -N a . 2. Responder strands t = n 1 , n 2 ∈ Resp[N a ] with trace -N a , +N a . Proposition 1 Suppose C is a static geometric bundle. If C contains a strand s = m 1 , m 2 ∈ Init[N a ]
of height 2 and N a uniquely originates on s, then C contains a strand whose distance from the nodes of s is at most c/2× elapse(m 1 , m 2 ) . Proof. Let s = (m 1 , m 2 ). Since N a uniquely originates on m 1 , there is a path

p 1 → q 1 ⇒ * p 2 → • • • ⇒ * p k → q k from m 1 to m 2 (i.e., p 1 = m 1 and q k = m 2 ). Now: elapse(m 1 , m 2 ) ≥ 1 c k i=1 dist(p i , q i ) ≥ 1 c (dist(p 1 , p 2 ) + dist(p 2 , q k )) = 2 × 1 c × dist(m 1 , p 2 ) (since p 1 = m 1 and q k = m 2 ) Thus, dist(m 1 , p 2 ) ≤ c/2 × elapse(m 1 , m 2 ).
Since the strand whose existence is claimed may be a penetrator strand, this protocol gives no information about who is within the specified distance.

Protocol 2

The purpose of this protocol is to provide A with a number r > 0 and the following guarantee to A: B is within distance r from A. A generates a nonce value which it signs and sends to B. B receives N a and determines a time delay T to allow for processing time. B signs N a ˆT and after an elapsed time of T sends N a ˆT with its signature to A.

Schematically, the protocol can be described thus:

A B • {|N a |} K -1 A → • • ← {|N a ˆT |} K -1 B •
Note that we are modeling a message accompanied by a hash as an encryption with a private key. After running this protocol A should have B's reply. Let T elapsed be the time interval A observes between the transmission of the nonce N and receipt of the response from B. A then computes the value:

r = 1 2 × T elapsed -T × c
Of course an attacker could still be present, but the claim is that A has received a guarantee that B, an honest participant, is within a ball of radius r of A.

There are two kinds of strands in this protocol:

1. Initiator strands s = m 1 , m 2 ∈ Init[B, N a , T ] with trace +N a , -{|N a ˆT |} K -1 B . 2. Responder strands t = n 1 , n 2 ∈ Resp[B, N a , T ] with trace -N a , +{|N a ˆT |} K -1 B for which elapse(n 1 , n 2 ) ≥ T .
We need to assume the hash-key mapping = term(m 2 ) originates on at least one strand t. t is regular, since the set of penetrator keys is empty. Thus t must be the second node n 2 of a regular strand in Resp[B, N a , T ]. In particular there is a path q = q 0 , q 1 , . . . , q (q) from n 2 to m 2 . Since N a is uniquely originating at s, there is a path p = p 0 , p 1 , . . . , p (p) from the first node m 1 of s to the first node n 1 of t. The paths p, q may traverse intermediate nodes on various strands. However, by the definition of geometric strand space and Axiom 1:

A → K -1 A is injective.
elapse(m 1 ,m 2 ) ≥ ≥ 1 c (p)-1 k=0 dist(p k , p k+1 ) + elapse(n 1 , n 2 ) + 1 c (q)-1 k=0 dist(q k , q k+1 ) ≥ 1 c dist(m 1 , n 1 ) + dist(m 2 , n 2 ) +T = 2 × 1 c × dist(m 1 , n 1 ) + T Thus, dist(m 1 , n 1 ) ≤ 1/2 × elapse(m 1 , m 2 ) -T × c.

Clock Distortion

The preceding protocol has two related problems:

1. The condition that the reported delay time T be less than the elapsed time for the initiator is too severe; 2. The requirement that principals have exact clocks is unrealistic.

We briefly indicate a simple refinement of the model that can deal with bounded time drift and distortion. The main idea here is that the time variation is bounded:

Definition 3. A time elapse function τ s on a strand s is α bounded iff elapse(m, n) ≤ α τ (m, n).
Having these distortion bounds allows us to introduce locale certificates with specified tolerances. We leave the details to future work.

Noninteractive Schemes

The previous locale schemes were based on the pessimistic assumption that the attacker may actually block all messages. We now consider schemes in which this capability is weakened or eliminated altogether. The impossibility of blocking messages is formulated as follows: Definition 4. A bundle C in a geometric strand space with global time T is radial iff for every positive node m and every strand s there is a negative node n on s such that m → n and

T(n) = T(m) + 1 c dist(m, n)
The property expressed in this definition implies that messages sent are always received by all principals and in particular, that messages cannot be destroyed by the attacker. Questions of system failure are not an issue here since there is no intermediate hardware between sender and receiver to required for message delivery. A weaker property which allows for failure conditions for strands is also possible, but our goal here is to consider questions of authenticity not of liveness.

Protocol 3

Consider the following protocol: A generates a nonce value N , attaches a signature and emits the signed term

{|N |} K -1 A . The value {|N |} K -1
A is received by a set of location servers B i . We assume the location servers B i have access to universal time T. B i notes the time

T i = T(m i ) it first receives the signal {|N |} K -1 A .
We note that B i may receive the signal more than once since an attacker may attempt to confuse the location servers by delay and retransmission,

The servers

B i send the values {|{|N |} K -1 A ˆTi |} K -1 i
to a central server, who creates a certificate with information on A's location.

A B i S n A {|N |} K -1 A → m i • {|{|N |} K -1 A ˆTi |} K -1 i → • Proposition 3
The following relations hold:

1 c dist(n A , m i ) -dist(n A , m j ) = T i -T j . (3)
Proof. Suppose A generates the message at time T A = T(n A ) then by the definition of global time, for every B i we have the identity:

T i -T A = 1 c dist(n A , m i ),
from which formula (3) follows immediately by subtraction.

Corollary 4 Suppose the underlying geometry is R 3 with Euclidean distance.

Then the distance equation for each pair of servers constrains n A to be on a hyperboloid.

Proof. This follows from the fact that the locus of points z whose distances from points a 0 , a 1 satisfy "dist(z, a 0 ) -dist(z, a 1 ) = constant" is a hyperboloid. This scheme is impractical since it requires that all servers respond to each request for locale authentication.

Protocol 4

We now describe a passive scheme much like GPS. The scheme is passive in the sense that the location servers just transmit signals instead of responding to clients. The protocol we describe is an idealized form of the actual protocol because we assume transmissions are continuous. For each time value t the server A i generates a nonce N t,Ai and at time t transmits {|N t,Ai |} K -1 A i

. The client collects all signals received at a single time instant and packages the messages into a vector

{|N t,Ai |} K -1 A i , . . . , {|N t,Ai |} K -1 A i
. This vector is used as a locale certificate. It would appear to constrain the client to be on an intersection of balls whose centers are the locations of the servers.

Unfortunately, this scheme does not appear to be much better than saying "I am here", because nothing enforces the client to package the messages actually received at a single instant, even if the servers encrypt the signals. Encryption of the nonces adds no security to this protocol, since an attacker may determine beforehand which value of t to use for each server.

To analyze this protocol with encrypted nonces, we associate to each server A i the function µ i : t → {N t,Ai } K A i . For each time instant t, the value of this function is the encrypted value of the nonce transmitted at time t by the server A i . Let us consider a fixed client B with location x. Since we are assuming the underlying geometry is radial, any signal transmitted by the server is received by the client after propagation delay. Denoting the signal propagation delay to x from the location of A i by τ Ai,x , we have

τ Ai,x = 1 c dist(A i , x) (4)
Thus the client sees a time translate of the server generated function

µ i φ Ai,x (t) = µ i (t -τ Ai,x ). ( 5
)
The goal of this protocol, ostensibly, is to provide a principal at x the data to assemble a locale certificate that binds that principal to location x at time t. The client is expected to package the sequence of values corresponding to messages received at time t, into a vector φ A1,x (t), . . . , φ An,x (t) . which he can then use as a certificate. However, a malicious client may package some other sequence of signals received at different times t 1 , . . . , t n into a bogus certificate φ A1,x (t 1 ), . . . , φ An,x (t n ) .

Ai B Aj

nA i ,t {|Nt|} K -1 A i → ← {|Ns|} K -1 A j nA j ,s n A i ,t {|N t |} K -1 A i → ← {|N s |} K -1 A j n A j ,s n A i ,t {|N t |} K -1 A i → n A j ,s n A i ,t (iii) {|N t (iii) |} K -1 A i → mi ← {| Ns |} K -1 Aj
In the following proposition we use the expression "complete knowledge of the underlying geometry" whose meaning is explained in the context of the proof.

Proposition 5 Under free encryption, if B has complete knowledge of the underlying geometry, of its own location and that of all the servers, then B can falsify any location.

Proof. B is at location x. Let y be some arbitrary location. Since the locations of the servers are known to B, the distances dist(A i , y) are known to B. It follows that the propagation times

τ Ai,y = 1 c dist(A i , y)
from location of A i to y are also known to B. Note

φ Ai,y (t) = µ i (t -τ Ai,y ) = µ i ((t + τ Ai,x -τ Ai,y ) -τ Ai,x ) = φ Ai,x (t + τ Ai,x -τ Ai,y ). (6)
Every term in this last expression is accessible to B. Thus B can claim the vector φ A1,x (t + τ A1,x -τ A1,y ), . . . , φ An,x (t + τ An,x -τ An,y ) .

as a time t location certificate, thus asserting to be at location y.

We leave open the more general question of whether it is possible to have a passive location discovery protocol that satisfies the locale authentication goal.

Conclusion

We identified the security goal of locale authentication and provided a systematic technique for proving that location protocols satisfy that goal. The technique is based on extending the well-developed strand space theory with a metric that captures the geometric properties of time and space. We used the metric strand space theory to prove that several prominent location discovery protocols including GPS do not satisfy the locale authentication goal. We also analyzed a location discovery protocol that does satisfy the goal under some reasonable assumptions.

There are occasions in which certificates for physical parameters other than location would be desirable. For instance, a regulatory agency may require certification that certain parameters (level of contaminants, radiation, temperature) in a production facility are within legal tolerances. In principle, this can be done in much the same way by a certification authority by dispatching a human agent to the site. This can also be done by a tamper-proof gauge which issues an electronic certificate or prints out a paper one. However, there is no obvious way to exploit some physical resource such as geometry so that these certificates can be issued remotely without tamper-proof gadgetry. At this point the remote construction of such certificates remains an open problem. Another interesting question is whether it is possible to have a passive location discovery protocol that satisfies the locale authentication goal.

A Strand Space Definitions

This appendix, derived from [START_REF] Thayer Fábrega | Strand spaces: Proving security protocols correct[END_REF][START_REF] Guttman | Authentication tests and the structure of bundles[END_REF], defines the basic strand space notions.

A.1 Strands, Strand Spaces, and Origination

Consider a set A, the elements of which are the possible messages that can be exchanged between principals in a protocol. We will refer to the elements of A as terms. In a protocol, principals can either send or receive terms. We represent transmission of a term as the occurrence of that term with positive sign, and reception of a term as its occurrence with negative sign. Definition 5. A signed term is a pair σ, a with a ∈ A and σ one of the symbols +, -. We will write a signed term as +t or -t. (±A) * is the set of finite sequences of signed terms. We will denote a typical element of (±A) * by σ 1 , a 1 , . . . , σ n , a n . A strand space over A is a set Σ with a trace mapping tr : Σ → (±A) * .

By abuse of language, we will still treat signed terms as ordinary terms. For instance, we shall refer to subterms of signed terms. We will usually represent a strand space by its underlying set of strands Σ.

Definition 6. Fix a strand space Σ.

1. A node is a pair s, i , with s ∈ Σ and i an integer satisfying 1 ≤ i ≤ length(tr(s)). The set of nodes is denoted by N . We will say the node s, i belongs to the strand s. Clearly, every node belongs to a unique strand. 2. If n = s, i ∈ N then index(n) = i and strand(n) = s. Define term(n) to be (tr(s)) i , i.e. the ith signed term in the trace of s. Similarly, uns term(n) is ((tr(s)) i ) 2 , i.e. the unsigned part of the ith signed term in the trace of s. 3. There is an edge n 1 → n 2 if and only if term(n 1 ) = +a and term(n 2 ) = -a for some a ∈ A. Intuitively, the edge means that node n 1 sends the message a, which is received by n 2 , recording a potential causal link between those strands. 4. When n 1 = s, i and n 2 = s, i + 1 are members of N , there is an edge n 1 ⇒ n 2 . Intuitively, the edge expresses that n 1 is an immediate causal predecessor of n 2 on the strand s. We write n ⇒ + n to mean that n precedes n (not necessarily immediately) on the same strand. 5. An unsigned term t occurs in n ∈ N iff t term(n). 6. Suppose I is a set of unsigned terms. The node n ∈ N is an entry point for I iff term(n) = +t for some t ∈ I, and whenever n ⇒ + n, term(n ) ∈ I. 7. An unsigned term t originates on n ∈ N iff n is an entry point for the set I = {t : t t }. 8. An unsigned term t is uniquely originating in a set of nodes S ⊂ N iff there is a unique n ∈ S such that t originates on n. 9. An unsigned term t is non-originating in a set of nodes S ⊂ N iff there is no n ∈ S such that t originates on n.

If a term t originates uniquely in a suitable set of nodes, then it can play the role of a nonce or session key, assuming that everything that the penetrator does in some scenario is in that set of nodes.

N together with both sets of edges n 1 → n 2 and n 1 ⇒ n 2 is a directed graph N , (→ ∪ ⇒) .

A bundle is a finite subgraph of N , (→ ∪ ⇒) , for which we can regard the edges as expressing the causal dependencies of the nodes. If C is a bundle, then the C-height of a strand s is the largest i such that s, i ∈ C. C-trace(s) = tr(s)(1), . . . , tr(s)(m) , where m = C-height(s).

We say that s ∈ C if the C-height of s equals length(s).

Proposition 2 2 .

 22 Suppose C is a static geometric bundle. Suppose also that the set of penetrator keys is empty. If C contains a strand s in Init[B, N a , T ] of height 2 and N a uniquely originates on s, then C contains a strand t in Resp[B, N a , T ] of height Moreover the distance from the nodes of s to the nodes of t is at most 1/2 × elapse(m 1 , m 2 ) -T × c. Proof. Let s = m 1 , m 2 . The term {|N a ˆT |} K -1 B

Definition 7 .

 7 Suppose → C ⊂ →; suppose ⇒ C ⊂ ⇒; and suppose C = N C , (→ C ∪ ⇒ C ) is a subgraph of N , (→ ∪ ⇒) . C is a bundle if: 1. N C and → C ∪ ⇒ C are finite. 2. If n 2 ∈ N C and term(n 2 ) is negative, then there is a unique n 1 such that n 1 → C n 2 . 3. If n 2 ∈ N C and n 1 ⇒ n 2 then n 1 ⇒ C n 2 . 4. C is acyclic.In conditions 2 and 3, it follows thatn 1 ∈ N C , because C is a graph. Definition 8. A node n is in a bundle C = N C , → C ∪ ⇒ C , written n ∈ C, if n ∈ N C ; a strand s is in C if all of its nodes are in N C .

This work was supported by the MITRE-Sponsored Research Program.