Markus Gruber
email: markus.gruber@inso.tuwien.ac.at

Phillip Wieser
email: phillip.wieser@inso.tuwien.ac.at

Stefan Nachtnebel
email: stefan.nachtnebel@inso.tuwien.ac.at

Christian Schanes
email: christian.schanes@inso.tuwien.ac.at

Thomas Grechenig
email: thomas.grechenig@inso.tuwien.ac.at

Extraction of ABNF Rules from RFCs to Enable Automated Test Data Generation

The complexity of IT systems and the criticality of robust IT systems is constantly increasing. Testing a system requires consideration of different protocols and interfaces, which makes testing hard and expensive. Test automation is required to improve the quality of systems without cost explosion. Many standards like HTML and FTP are semiformally defined in RFCs, which makes a generic algorithm for test data generation based on RFC relevant. The proposed approach makes it possible to automatically generate test data for protocols defined as ABNF in RFCs for robustness tests. The introduced approach was shown in practice by generating SIP messages based on the RFC specification of SIP. This approach shows the possibility to generate data for any RFC that uses ABNF, and provides a solid foundation for further empirical evaluation and extension for software testing purposes.

Introduction

Security testing is an important and at the same time also expensive task for developing robust and secure systems. Costs of software testing increase due to the complexity and interconnection of modern software systems. Different interfaces, protocols and standards are used which requires much test effort to cover all aspects. Test automation can eliminate repetitive and time-consuming manual testing tasks and therefore reduce costs. Test data is required to test a System Under Test (SUT), and good test data might increase confidence in software quality, e.g., by testing more parts of the software [START_REF] Ebert | Software Measurement: Establish -Extract -Evaluate -Execute[END_REF].

Many Internet standards are commonly defined in a document called Request For Comments (RFC). The Internet Engineering Task Force (IETF) describes the purpose of RFC as:

"Memos in the RFC document series contain technical and organizational notes about the Internet. They cover many aspects of computer networking, including protocols, procedures, programs, and concepts, as well as meeting notes, opinions, and sometimes humor." [START_REF] Force | Overview of rfc decument series[END_REF] Augmented Backus Naur Form (ABNF), a metalanguage to describe the syntax of parsable structures, is often used in RFCs to describe formal specifications, e.g., protocol specifications or flow definitions. These ABNF rules are usually hidden in informal descriptions.

Certain ABNF rules within an RFC are used to specify protocols or technologies. Examples are Hyper Text Transfer Protocol (HTTP) or Session Initiation Protocol (SIP), which are defined using ABNF rules. Based on these ABNF rules, test data can be generated in order to test different aspects of the interface, e.g., the conformance of a SUT to an RFC.

In this work, an approach to semi-automatically generate test data based on an RFC specification is presented. The process of extracting ABNF rules out of an RFC and the transformation from ABNF to XML Schema Definition (XSD) makes it possible to generate test data in Extensible Markup Language (XML) format. For test data generation, a number of existing frameworks and scientific test data generation algorithms can be used. XML is widely used in web applications and enables test data transformation to various other formats. The application of this approach is shown by generating test data for SIP messages based on the specification of SIP in RFC 3261 [START_REF] Rosenberg | RFC 3261: SIP -Session Initiation Protocol[END_REF]. The possibility to semiautomatically generate test data based on an RFC might greatly reduce the time and effort needed to efficiently test a SUT.

Fenner [START_REF] Fenner | Bill fenner's abnf extractor[END_REF] has developed a simple heuristic extractor as part of his ABNF parser. The solution proposed in this paper is based on this parser, but the workflow is adapted and additional features to generate a valid and self-contained set of ABNF rules are implemented. Valid and self-contained ABNF rulesets do not contain validation errors, e.g., syntax errors or missing rules. These rulesets can be validated by other ABNF parsers, e.g., Bill's ABNF Parser1 , to prove syntactic and semantic validity. Additionally, the ability to transform ABNF rules to XSD is introduced. For automated test data generation we use our approach presented in a previous work [START_REF] Schanes | Generic data format approach for generation of security test data[END_REF] which operates on an XSD model.

The remainder of this paper is structured as follows. An overview of related work is given in Sect. 2. Section 3 describes ABNF and the concept of ABNF model extraction. Section 4 covers test data generation based on transformation from ABNF rules to XSD. Section 5 covers the results and the lessons learned by developing and applying the approach for test data generation of SIP systems. The paper finishes with a conclusion and ideas for further work in Sect. 6.

Related Work

The IETF regularly publishes RFCs which describe Internet standards. Other organizations like International Organization for Standardization (ISO) and World Wide Web Consortium (W3C) publish standards in computer science as well.

ABNF is only one metalanguage to describe parsable structures, other widely used formal metalanguages are Backus Naur Form (BNF) [START_REF] Mccracken | Backus-naur form (bnf)[END_REF], Wirth Syntax Notation (WSN) [START_REF] Wirth | What can we do about the unnecessary diversity of notation for syntactic definitions?[END_REF] or Extended Backus Naur Form (EBNF) [START_REF] Standard | [END_REF].

Concerning test data generation, one can distinguish between random and dynamic test data generation [START_REF] Michael | Generating software test data by evolution[END_REF]. Random data generation techniques do not require (but may take into account) an interface-or protocol specification of the SUT. While some authors state that random data generation produces test data efficiently [START_REF] Arcuri | Random testing: Theoretical results and practical implications[END_REF], [START_REF] Gutjahr | Partition testing vs. random testing: the influence of uncertainty[END_REF], others have come to the conclusion that most data is rejected by the SUT [START_REF] Mcminn | Search-based software test data generation: A survey[END_REF], [START_REF] Ribeiro | Test case evaluation and input domain reduction strategies for the evolutionary testing of object-oriented software[END_REF]. Dynamic data generation approaches analyze the execution of test data against a SUT and try to generate new data based on the obtained knowledge. One approach tries to adapt test data so that critical software regions are tested more thoroughly [START_REF] Carbin | Automatically identifying critical input regions and code in applications[END_REF], while another employs dynamic binary analysis [START_REF] Caballero | Polyglot: automatic extraction of protocol message format using dynamic binary analysis[END_REF].

The proposed approach generates data in the generic format XML. Several authors show the transformation of XML to other commonly used formats [START_REF] Van Deursen | XML to RDF conversion: A generic approach[END_REF], [START_REF]information technology ASN.1 encoding rules: XML encoding rules (XER)[END_REF], [START_REF] Fong | Converting relational database into XML document[END_REF], [START_REF] Jacinto | Bidirectional conversion between XML documents and relational databases[END_REF]. Specific applications of test data generation from XSD have been proposed by several authors. A simple XML data generator based on defined rules has been proposed in [START_REF] Aboulnaga | Generating synthetic complexstructured XML data[END_REF]. Another software called TAXI generates XML documents based on an XSD [START_REF] Bertolino | TAXI-a tool for XML-based testing[END_REF], while ToxGene described in [START_REF] Barbosa | ToXgene: a templatebased data generator for XML[END_REF] is a templatebased generator of synthetic XML documents. For the presented approach in this work our test data generation approach presented in [START_REF] Schanes | Generic data format approach for generation of security test data[END_REF] is used, which allows the generation of XML data based on XSD input.

Concept of ABNF Model Extraction from RFC

This section presents an introduction to the usage of ABNF in RFCs followed by the description of the process of the specification extraction approach. This is an iterative process of improving the quality of the extracted ruleset. This section also describes the ABNF error classes which can occur during this process.

Introduction to the Usage of ABNF in RFCs

ABNF is a metalanguage based on BNF and defined in RFC 5234 [START_REF] Crocker | Augmented bnf for syntax specifications: Abnf[END_REF]. Both are notations for context-free grammars, used to describe the syntax of parsable structures, e.g., communication protocols. Most RFCs use ABNF to describe formal specifications. These ABNF rules, however, are usually embedded in informal descriptions, as seen in Fig. 1. In addition to the informal description at the top of this example, this ABNF rule consists of the rule name (HTTP-Version) and the rule definition on the right side. ABNF rules in one RFC can also reference ABNF rules in other RFCs. A mutual dependence of each ABNF rule can be described with a dependency tree, as shown in [START_REF] Stefanec | Grammar-based sip parser implementation with performance optimizations[END_REF].

The ABNF specification is a set of derivation rules. These rules can be seen as a tree of rules and operators. Several options exist for creating this tree. One possible option is the top-down parsing strategy, which consists of taking a single element of interest, designating it as root of the tree and adding the dependent rules iteratively. Another possibility is the bottom-up parsing strategy. Here, all rules are considered and topologically sorted based on their dependencies, resulting in a tree with multiple roots. The approach presented in this paper

The v e r s i o n o f an HTTP message i s i n d i c a t e d by an HTTP-V e r s i o n f i e l d i n t h e f i r s t l i n e o f t h e message .

HTTP-V e r s i o n = "HTTP" "/" 1 * DIGIT " . " 1 * DIGIT follows the second approach, since it is more flexible and supports our goal to extract all ABNF rules, e.g., including referenced rules in other RFCs. A drawback of the second approach is, that the developer most likely will have to deal with rules that are not relevant, since only some rules (or a single rule including dependencies) are in scope of interest. Special classes of ABNF rules are prose rules, semantic pseudo rules and stub rules. A prose rule is enclosed by < >. Prose rules are informal definitions of rules. Figure 2 shows an example of a prose rule in RFC.

LOALPHA = <any US-ASCII l o w e r c a s e l e t t e r " a " . . " z">

Fig. 2. Example of a prose rule

Semantic pseudo rules use operators to describe semantic relations, which will lead to an ABNF syntax error. Figure 3 shows an example of a syntax error in an ABNF rule. r e s p o n s e i s f r e s h = ( f r e s h n e s s l i f e t i m e > c u r r e n t a g e ) Fig. 3. Example of a semantic pseudo rule, leading to a syntax error Stub rules, in contrast to semantic pseudo rules, are semantically incorrect. Figure 4 shows an example of a stub rule, i.e., a Message Digest 5 (MD5) checksum found in RFC 1864 [START_REF] Myers | The content-md5 header field[END_REF]. It is very likely that this MD5 checksum will not represent a valid checksum of the generated sample.

Process of the Specification Extraction Approach

Based on the extractor developed by Fenner [START_REF] Fenner | Bill fenner's abnf extractor[END_REF], additional features were implemented, e.g., namespacing, case escaping or detecting and separating prose rules, to heuristically extract all defined conditions from the RFC. Not all RFCs could be parsed automatically, because in some cases conflicts could not be resolved automatically in order to get semantically correct ABNF rulesets. To increase the quality of the approach, it was decided to use a semi-automatic approach to extract ABNF rules from RFCs. The ABNF extractor automatically processes the following steps in order to get a final ruleset free of any errors:

1. Handle multiple input files as a single set of rules 2. Detect prose rules for semi-automatic processing 3. Expand # operators to valid constructs in ABNF syntax, because # is an originally unsupported rule in ABNF but defined later in some RFCs as #rule 4. Replace widely-used (but actually forbidden) characters "_" by "-" and "|" by "/" 5. Strip comments from rules 6. Unify the rules and remove redundancies 7. Replace rules that are defined multiple times (same name and same definition) by a single occurrence 8. Generate a dependency tree 9. Topologically sort rules based on the dependency tree The topological sorting of rules is necessary, because if a rule is referenced before defined some parsers may throw errors. Additionally to the automatically processed tasks, the following rule adaption possibilities to clean the ABNF rules in order to get a valid and self-contained ruleset exist:

-Blacklist definitions for all rules which should be ignored -Namespace transformations for rules with the same name in different RFCs -Replace rule names with case-insensitive rule names -Replace invalid rule definitions with customized rules Our approach proposes a solution for each error, but the final choice of the rule adaption must be accomplished manually in order to avoid semantic errors.

Validating Validity and Self-Containedness of a Rule Set

The syntactic validity of ABNF rules can be tested using ABNF parsers, which throw an error if invalid ABNF syntax is used.

In order for a ruleset to be self-contained, all referenced rules need to be defined in the current ABNF document, meaning that there are no rules that are not defined. A simple algorithm as seen in Fig. 6 uses all extracted ABNF rules as input. It can be used to generate two sets: One contains all defined rules, and the other contains all referenced rules. By verifying that every referenced rule is part of the set of defined rules, one can verify that there are no missing rules.

Error Classes of ABNF Generation

During the automated derivation of a model with the ABNF rules from one or more RFCs different problems can arise. The three main classes of problems are missing rule errors, syntax errors and double rule errors. By using multiple RFCs, e.g., referencing definitions in other RFCs, it can occur, that rules are defined more than once. If not all RFCs are given as input to the parser, missing rule errors can occur. Due to failures during the parsing process, syntax errors can arise, e.g., wrong definitions in the RFC or problems of parsing the ABNF rules from the RFC text. Figure 7 shows the errors which can occur during the extraction process.

Missing Rule Errors A missing rule is a rule, that is referenced, but is not defined. For example the rules A and B are defined, rule A references rules B and C, but rule C is not defined. This could happen if a rule is defined as prose or defined in a referenced document.

If a rule may be referenced from another RFC, these references are informally defined either in a prose rule, or in the surrounding textual description. If this occurs, one can either import the complete referenced RFC or copy the specific rule. Another problem could occur, when some RFCs include some core rules (as defined in RFC 5234 [START_REF] Crocker | Augmented bnf for syntax specifications: Abnf[END_REF]), while other core rules are missing. Core rules are basic rules that are in common use. Some authors include all ABNF core rules directly in implementations of scanners or parsers. For the sake of simplicity, it is suggested to include them in a separate file. Concerning duplicate -or missing -rules, they would be treated equally to extracted rules.

A special kind of errors are non-validation errors. A ruleset which contains non-validation errors contains valid ABNF syntax, but is semantically incorrect. Semantic errors can only be detected by so-called validating parsers (in contrast to non-validating parsers). One reason could be, that some rules are only stub rules. This issue can not be solved in ABNF, but only by some processor on a higher level that takes semantic aspects like data dependencies into account.

Another reason of non-validation errors could be blind text as part of a rule. Blind text is meant as additional information or description, but parsers may consider it part of the rule. An example of blind text in an ABNF rule can be seen in Fig. 8. Because of its indent, the blind text will be treated as part of the rule, which will result in a syntax error although the text is only meant as a comment.

c r e d e n t i a l s = auth-scheme #auth-param Note t h a t many b r o w s e r s w i l l o n l y r e c o g n i z e B a s i c and w i l l ←֓ r e q u i r e t h a t i t be t h e f i r s t auth-scheme p r e s e n t e d . ←֓ S e r v e r s s h o u l d o n l y i n c l u d e B a s i c i f i t i s m i n i m a l l y ←֓ a c c e p t a b l e .

Fig. 8. Example of blind text in an ABNF rule

Syntax Errors The second error class are syntax errors. Mostly, semantic pseudo rules (as explained in Sect. 3.1) occur in addition to regular rule definitions, or are referenced by another semantic rule. Although it is not usable in ABNF directly, it could be parsed as additional information. This information could be used at a later time for a format supporting it, e.g., XSD generation. Because of the lack of typing, and describing semantic relations in ABNF, these rules have to be stubbed. Another possibility is, transforming the ABNF to a different grammar, which enables supporting the specific aspect of the subjected prose rule.

Double Rule Errors

The third error class are double rule errors. If the semantic pseudo rule is a duplicate of a regular rule, the semantic pseudo rule could be simply ignored.

The ABNF standard defines rule names as case-insensitive, which is not always the case in RFCs. Sometimes, rules with the same name (and different casing) are intended to be different. The presented approach solves this by heuristically replacing the upper-cased letter with a lower-cased and some additional ABNF-compatible information tagging it as escaped. Figure 9 shows an example of escaping the upper-cased letters. This circumstance also often occurs, when importing referenced RFCs.

' Foo ' would be e s c a p e d t o '---f ---oo ' Fig. 9. Example of escaped upper-case letter 'F' Another case of double rule errors could occur when importing a referenced RFC, or processing multiple RFCs. Then, it may happen, that rules are defined in multiple RFCs. Similar rules with the same name and same body can be resolved by ignoring all duplicated rules. It may also happen, that the two rules mean two completely different things in the different scopes of the RFCs. In this case, it is required to namespace them in an ABNF-compatible fashion. One option would be to set a prefix to the affected rules to avoid duplicated rules.

Test Data Generation Based on Transformation from ABNF Rules to XSD

This section presents the approach of test data generation based on transformation from ABNF rules to XSD. An XSD file describes the structure of an XML document, and was introduced by the W3C. The reason for choosing XSD as the destination format is that test data generation in XML format, which is a generic format and can be transformed to many other formats, is easily possible and existing data generation algorithms can be used. Several differences and similarities of ABNF and XSD need to be taken into account, which are described in this section.

Differences Between ABNF and XSD

Each rule itself can be transformed to a valid XSD representation, but the result of the combination of the rules does not produce a valid XSD. In ABNF, literals, references and ranges may all be used as a part of the rule definition, but those constructs all need to be transformed to XSD differently. Well-formed XSD documents are well-formed XML documents themselves. Not all characters are valid in XML, but it is required to be able to encode all bytes from 0x00 to 0xFF. Therefore one of the binary types had to be picked. The type hexBinary was chosen in favor of base64Binary, because it is easier to use with a regular expression pattern. When using hexBinary to encode a text, each letter is represented by two hexadecimal characters, and can be changed individually without the need to re-encode the rest of the string.

Literals, strings and ranges can be expressed either as patterns using a regular expression, or as an enumeration. It was decided to take the regular expression pattern approach, because the representation as regular expression is more compact and therefore in our opinion more readable. Especially when a large number of data instances are possible for an element, an enumeration is not a viable option. Existing regular expression parsers can be used to generate instances that conform to a regular expression.

Additionally a string literal in ABNF is case-insensitive. This means "foo" could produce "fOo", "FOo", etc. For the sake of simplicity, "foo" will only produce "foo" after transforming to XSD.

Mapping ABNF to XSD

To use our generic approach of data generation as described in our previous work [START_REF] Schanes | Generic data format approach for generation of security test data[END_REF], which allows the generation of XML data based on XSD input, an ABNF ruleset needs to be transformed to XSD. An example of the expected result, i.e., for the transformation of the DIGIT rule, is seen in Fig. 10. Our approach uses a transformation matrix, as seen in Fig. 11, from ABNF rules to XSD. These mapping rules require additional transformation logic to correctly generate a valid XSD element tree. The proposed approach derives transitions from ABNF rules to XSD elements by comparing the valid children of the enclosing element with the valid parents of an enclosed element, until a transition from the enclosing to the enclosed element is detected.

To reduce complexity, classes are combined, as defined in the first column of Fig. 11, of (in this case) compatible ABNF rules:

-Choice, Group, Repetition ≡ CGR -Literal, String, Range ≡ LSR A repetition is transformed to XSD using a (single-content) sequence with attributes minOccurs and maxOccurs. Therefore it is in the same class as group.

However, the following transformations are used to transform ABNF rule classes to XSD trees. XSD follows certain restrictions concerning element positioning in the tree, which need to be considered for the transformation.

1. Rule → CGR 2. Rule → Ref erence 3. Rule → LSR 4. CGR → CGR 5. CGR → Ref erence 6. CGR → LSR
Classes irrelevant to our approach have been omitted.

Description of XML Test Data Generation from XSD

After transformation of the ABNF rules to XSD, a generic data generation framework is used to generate the required test data in XML format. For this purpose, the test data generation features of an existing fuzzing framework called fuzzolution 2 were used, which are also described in [START_REF] Schanes | Generic data format approach for generation of security test data[END_REF].

The XSD document generated in the previous step serves as an input to the framework. Data is generated based on two features of the generated XSD, which are structural information and data-based restrictions.

Structural information is represented by elements like choice, sequence as well as attributes like minOccurs. The used framework takes these restrictions into account, and generates XML instances that conform to the given XSD. Data-based restrictions describe the data within the elements. In this example, hexadecimal values are generated for several elements based on the information available in the XSD.

Using the transformed XSD, the framework generates test data in XML format. These XML files contain the test data and might be used either directly by executing it against a SUT or by transforming it to another format first.

Experiences with Generation of Test Data for SIP Systems

In this section, the applicability of the proposed approach for a specific RFC is presented. For this purpose, test data for SIP messages as defined in RFC 3261 [START_REF] Rosenberg | RFC 3261: SIP -Session Initiation Protocol[END_REF] is generated and validated. Since the number of Voice over IP (VoIP) systems and SIP users is constantly increasing, attackers have more incentive to attack SIP systems. This shows the necessity to automatically test SIP systems to find and resolve robustness errors.

Generation of SIP Test Data Based on the RFC

The process of generating test data in this approach can be summarized by these steps:

1. Generate ABNF rules out of the RFC using the presented ABNF extractor approach 2. Transform the ABNF ruleset to an XSD tree 3. Generate XML test data based on the XSD using the test data generation framework 4. Transform XML test data to SIP messages and validate them Using the presented approach, a large amount of valid and invalid test data for SIP systems based on RFC 3261 could be generated. While the XSD contains restrictions which describe valid instances, invalid instances can be generated by violating the constraints defined in the XSD, e.g., violating regular expression patterns or violating structural restrictions, e.g., omitting required elements.

To validate the generated valid data, a custom stand-alone tool was developed that transforms XML messages back to raw SIP messages. The resulting SIP messages were validated using APG 3 , an ABNF parser. Part of the set of tools is a set of ABNF rules for SIP messages. These rules were used to show that the validity of the generated SIP messages. Provided that the external ABNF ruleset is valid, it was thus shown that the generated SIP messages are valid with respect to the RFC.

Learnings and Limitations of the Proposed Approach

Compared to the ABNF extraction of HTTP (RFC 2616), which needed a quite large amount of rule adaption iterations, SIP (RFC 3261) only needed a couple of iterations. As in RFC 2616, an informal note was parsed as part of one rule and had to be redefined. In contrast to RFC 2616 no syntactical errors were detected in rules. Also in contrast to RFC 2616, having quite a lot of dependencies, is was only necessary to import two other RFCs to fix missing rule errors. RFC 2806 could be imported directly, and RFC 1035 was written in BNF and had to be transformed to ABNF.

It was observed that the generated XSD file did not include all desired structural restrictions. A very specific example is that it is not possible to set required and optional message headers for different SIP methods (e.g., REGISTER and INVITE) individually. Instead, the message header elements and the SIP method are independent choice elements in XSD. This means that all permutations of those two groups are allowed. However, this is not a restriction of this approach, because the ABNF rules are not more restricted in the RFC.

Discussion of Test Data Generation from RFC

The framework used for data generation, fuzzolution, makes it possible to generate a large number of data files with little risk of memory shortages. The problem, however, lies in the large possibilities of combinations of possible test data instances.

The XSD file for the test data generation of SIP messages contains about 8000 lines of code. In its most basic configuration, the framework generates all possibilities, i.e. each combination of possible structural and data-related instances is generated. Because this schema file contains many choice indicators and optional elements, the number of possibilities of valid XML files is very large. Recursive structures are used (an element might contain itself), so it is not even possible to generate all instances because an infinite number of possibilities exists. All those problems are considered and resolved in our generic data generation approach [START_REF] Schanes | Generic data format approach for generation of security test data[END_REF] by configuration of the framework.

Missing ABNF rules have to be reviewed manually, deciding whether to import, stub or write the rule. This could be partially automated by parsing the text for referenced RFCs. The proposed approach includes fetching potentially interesting RFCs, searching the RFCs and ordering based on distance heuristics and importing of the top-rated RFC, with eventual user intervention.

Conclusion and Further Work

In this paper, an approach of generating test data from RFCs was presented. This is done by extracting an ABNF model from an existing RFC. Based on this model, an XSD file is generated, which in turn is the input for a data generation software which generates data in XML format. This test data might be used for testing a SUT. For the extraction of an ABNF model, a heuristic extractor by Fenner [START_REF] Fenner | Bill fenner's abnf extractor[END_REF] is extended to get a valid and self-contained ruleset. Using the proposed approach makes it possible to semi-automatically generate test data based on an RFC. The application of the approach was shown using SIP and proved to be able to generate valid and invalid test data to test a system.

Future areas of work include the stateful representation of SIP in this approach, and the improvement of the transformation from ABNF to XSD in order to test more aspects of the system. In the SIP example, this means to make a distinction between allowed message headers for each allowed message.

The ABNF rules are only a small part of RFCs in comparison to the text length. They mostly consist of natural language descriptions discussing the field of interest. This information could be helpful constructing test data, or distinguish between valid and invalid variations. These include for example semantic relations, constraints, examples and references to other RFCs. The approach proposed in this paper might support additional research in implementing a parser looking for those natural language patterns.

With the presented approach, an automated extraction of a model for the generation of test data is possible. With the presentation of the transformation from ABNF to XSD, a generic data generation approach for different protocols is possible. This allows clear separation of concerns for test tools and a focus on a robust test generation logic.

Fig. 1 .

 1 Fig. 1. Example of an ABNF rule in RFC 2616

Fig. 4 .

 4 Fig. 4. Example of a stub rule

Figure 5

 5 Figure5describes our approach to extract a valid and self-contained ABNF ruleset of an RFC. The approach starts with the choosing of an arbitrary RFC, or multiple RFCs, one wants to have an ABNF ruleset for. After the initial configuration, it is an iterative process, fixing one problematic rule after another, until the full set of ABNF rules is generated.

Fig. 5 .

 5 Fig. 5. Process of the ABNF extraction approach

Fig. 6 .

 6 Fig. 6. Pseudocode: Constructing set of definitions and set of references

Fig. 7 .

 7 Fig. 7. Error Classes of ABNF Generation and Countermeasures.

Fig. 10 .

 10 Fig. 10. Example of ABNF to XSD transformation

Fig. 11 .

 11 Fig. 11. Basic ABNF to XSD mapping rules.

https://code.google.com/p/bap/

http://security.inso.tuwien.ac.at/esse-projects/fuzzolution/


Thang Hoang
email: thang.hoangminh@stu.edu.vn

Deokjai Choi
email: dchoi@jnu.ac.kr

Viet Vo

Anh Nguyen

Thuc Nguyen

A Lightweight Gait Authentication on Mobile Phone Regardless of Installation Error

Keywords: gait authentication, identification, pattern recognition, behavioural biometric, mobile accelerometer, mobile security

In this paper, we propose a novel gait authentication mechanism by mining sensor resources on mobile phone. Unlike previous works, both built-in accelerometer and magnetometer are used to handle mobile installation issues, including but not limited to disorientation, and misplacement errors. The authentication performance is improved by executing deep examination at pre-processing steps. A novel and effective segmentation algorithm is also provided to segment signal into separate gait cycles with perfect accuracy. Subsequently, features are then extracted on both time and frequency domains. We aim to construct a lightweight but high reliable model; hence feature subsets selection algorithms are applied to optimize the dimension of the feature vectors as well as the processing time of classification tasks. Afterward, the optimal feature vector is classified using SVM with RBF kernel. Since there is no public dataset in this field to evaluate fairly the effectiveness of our mechanism, a realistic dataset containing the influence of mobile installation errors and footgear is also constructed with the participation of 38 volunteers (28 males, 10 females). We achieved the accuracy approximately 94.93% under identification mode, the FMR, FNMR of 0%, 3.89% and processing time of less than 4 seconds under authentication mode.

Introduction

The explosion of mobility nowadays is setting a new standard for information technology industry. Mobile devices sales skyrocketed over recent years. A survey on the mobile market 1 showed that there were six billion subscriptions by the end of 2011. Technology constantly evolves and creates more intelligent devices. Their abilities are not only limited in calling, or texting, but also cover a variety of utilities, including portable storage and business applications, such as e-commerce or m-banking [START_REF] Pousttchi | Assessment of todays mobile banking applications, from the view of customer requirements[END_REF].

However, misperceiving mobile devices as an absolutely safe repository to store critical information could make owners face up to security issues. Such devices can be easily lost, stolen, or illegally accessed [START_REF] Breitinger | User Survey on Phone Security and Usage[END_REF], which makes sensitive or/and important information of mobile owners become vulnerable (see more [START_REF] Breitinger | User Survey on Phone Security and Usage[END_REF]). Consequently, authentication settings have evolved to become a more priority issue. The most widely-used authentication methods in mobile currently are PINs, visual patterns, and passwords because of their ease in use and implementation. However, these methods are not always effective considering remembrance and security aspects [START_REF] Breitinger | User Survey on Phone Security and Usage[END_REF]. Implementations on physiological biometric could overcome this issue completely [START_REF] Jain | An Introduction to Biometric Recognition[END_REF]. However, it is hard to deploy them on mobile phone since existing mobile resources would not guarantee to acquire specialized data such as iris, fingerprint, etc. properly. Similar to other active authentications like PIN and password, physiological biometrics also cause time consuming which is one of the main obstacles preventing users from using these techniques. They forced us to pay attention and perform explicit gestures to be authenticated (e.g. typing passphrases, facing to the front camera, etc.). This causes obtrusiveness and inconvenience in frequent use.

Thus, a friendlier and reliable authentication mechanism which can operate implicitly without users awareness is desired to be found and aimed to ameliorate mobile security. Recently, a novel approach using wearable sensors to authenticate human gait has been introduced and achieved potential results [START_REF] Pan | Accelerometer-based gait recognition via voting by signature points[END_REF][START_REF] Ailisto | Identifying People from Gait Pattern with Accelerometers[END_REF]. Accordingly, sensors are attached to human body in various positions such as pocket, waist and footgear to record physical locomotion. This approach takes advantage of modern mobile devices sensing capabilities including GPS, accelerometer, magnetometer, gyroscope sensor, etc. Moreover, devices are usually put in their owners' pockets for most of the day [START_REF] Breitinger | User Survey on Phone Security and Usage[END_REF], so gaits can be authenticated implicitly and continuously by acquiring walking signals. For this reason, sensor-based gait authentication has a significant advantage in implementation on mobile. It will provide developers with an edge over improving various techniques in authentication.

The above potentialities of wearable sensor authentication motivated us to improve and establish a similar mechanism running on mobile. Since 2009, this study has been initiated on mobile and achieved encouraging results [START_REF] Terada | Performance of gait authentication using an acceleration sensor[END_REF][START_REF] Derawi | Unobtrusive User-Authentication on Mobile Phones using Biometric Gait Recoginition[END_REF]. However, they were still in early stages and methods were tried-out on ideal conditions in which mobiles were always installed at an exact position and orientation by tightening directly to equipment such as suite, footgear, or human body. Processing steps such as segmentation and noise elimination which could directly affect the recognition model were not analyzed in depth. Finally, there was no evaluation of the possibility of running authentication directly on mobile devices. Authentication tasks were assigned to powerful computers rather than mobile resources. An excessively complex model could face up to critical challenges when it is deployed under limited computational capabilities.

In this paper, we focus on finding solutions to deal with existing matters:

(1) To handle mobile installation issues, we introduce a novel lightweight but effective calibration method by taking full advantage of existing sensors on modern mobile phone. (2) Gait preprocessing phases are investigated thoroughly to improve the effectiveness of authentication mechanism. A novel segmentation algorithm which could segment acquired data into well separated gait cycles is also presented. (3) To make sure the authentication model can run smoothly and independently under limited computational resources on mobile phone, we apply some techniques to reduce the processing time of learning algorithm. A scenario is also designed to construct a particular dataset under more realistic conditions to fairly evaluate our proposed model. We perform our study on both authentication and identification modes. The impacts of mobile installation errors and processing steps to the authentication model are analyzed deeply. Finally, the authentication is deployed directly on the mobile phone to experiment the possibility of running such model with limited computational resources. With promising results achieved from the experiment, solving installation issues and providing a novel lightweight reliable gait authentication are our main contributions.

The rest of this paper is organized into 4 sections. Section 2 presents state of the art in which we summarize typical previous studies related to sensor-based gait authentication. Section 3 presents our proposed authentication model. Section 4 summaries our experimental results. Finally, conclusions will be presented in Section 5.

State of the Art

Human gait has been considered as a particular style and manner of moving human feet and hence contains the information of identity authentication. In a more detailed level view, the mechanism of human gait involves synchronization between the skeletal, neurological and muscular system of human body [START_REF] Fish | Clinical assessment of human gait[END_REF]. In 2005, H. Ailisto et al. were the first to propose the gait authentication using wearable sensor [START_REF] Ailisto | Identifying People from Gait Pattern with Accelerometers[END_REF] and this area was further expanded by Gafurov et al. [START_REF] Gafurov | Gait Recognition Using Wearable Motion Recording Sensors[END_REF]. In general, sensors are attached to various positions on human body to record locomotion signal. Various sensors are experimented including gyroscope, rotation sensor but acceleration sensor (or accelerometer) is the most commonly used. In this field, there are two typical approaches: (1) Template Matching (TM) and (2) Machine Learning (ML). In (1), acquired signal is preprocessed and then split into patterns. Best patterns which represent the most characteristics of the subject are considered as representative gait templates. They are then stored as referred templates corresponding to individual. Various distance metrics such as Dynamic Time Warping (DTW) [START_REF] Bours | Eigensteps: A giant leap for gait recognition[END_REF][START_REF] Derawi | Unobtrusive User-Authentication on Mobile Phones using Biometric Gait Recoginition[END_REF][START_REF] Thang | Gait Identification Using Accelerometer on Mobile Phone[END_REF], Euclidean distance [START_REF] Terada | Performance of gait authentication using an acceleration sensor[END_REF][START_REF] Bours | Eigensteps: A giant leap for gait recognition[END_REF], autocorrelation [START_REF] Ailisto | Identifying People from Gait Pattern with Accelerometers[END_REF], nearest neighbors [START_REF] Pan | Accelerometer-based gait recognition via voting by signature points[END_REF] are used for calculating the similarity score between a given pattern and referred templates.

Second method is the most popular approach used in pattern recognition areas. In this approach, gait signal is segmented into patterns. On each pattern, features are extracted in time domain, frequency domain, and wavelet domain or by special techniques such as time delay embedding [START_REF] Frank | Activity and Gait Recognition with Time-Delay Embeddings[END_REF]. Extracted feature vectors are then classified using supervised classifiers like HMM [START_REF] Nickel | Classifying Accelerometer Data via Hidden Markov Models to Authenticate People by the Way they Walk[END_REF], SVM [START_REF] Nickel | Classificatoin of Acceleration Data for Biometric Gait Recognition on Mobile Devices[END_REF][START_REF] Hestbek | Biometric Gait Recognition For Mobile Devices Using Wavelet Transform And Support Vector Machines[END_REF][START_REF] Sprager | A cumulant-based method for gait identification using accelerometer data with Principal Component Analysis and Support Vector Machine[END_REF][START_REF] Thang | Gait Identification Using Accelerometer on Mobile Phone[END_REF][START_REF] Frank | Activity and Gait Recognition with Time-Delay Embeddings[END_REF], ANN [START_REF] Mondal | Gait Based Personal Identification System Using Rotation Sensor[END_REF], LDA [START_REF] Mondal | Gait Based Personal Identification System Using Rotation Sensor[END_REF]. Some other works propose hybrid approaches in which either distance metrics such as DTW [START_REF] Yuexiang | Gait Authentication Based on Acceleration Signals of Ankle[END_REF], Euclidean [START_REF] Gafurov | Gait Recognition Using Wearable Motion Recording Sensors[END_REF][START_REF] Mntyjrvi | Identifying Users of Portable Devices From Gait Pattern With Accelerometers[END_REF], are used to measure the similarity scores of features extracted in time and frequency domains, or similarity scores of gait templates can be considered as features which are used for classification [START_REF] Sun | Curve Aligning approach for gait authentication based on a wearable sensor[END_REF].

In early stages, most of works used standalone sensors (SSs) have been implemented with a variety of success rate, they still have some restrictions. For example, SSs is relatively expensive and the interface of some special sensors needs to be developed separately. Thus, there is an increasing need to develop an easy-to-operate gait monitoring system within pervasive and ubiquitous environment. Recently, the developing of micro electromechanical (MEMs) technology helped such sensors to be miniaturized and integrated inside mobile devices (known as mobile sensors -MS). Gait authentication has been initially experimented on MS during recent years. In 2010, J. Frank et al. [START_REF] Frank | Activity and Gait Recognition with Time-Delay Embeddings[END_REF] used HTC G1 cell phone with built-in accelerometer attached at the trouser pocket position to collect gait signal. By using time-delay embedding combined with SVM classifier, they achieved a perfect recognition rate of 100%. In comparison to SSs, MSs are designed to be cheaper, simpler and as a result the quality is not guaranteed as SSs. For example, the sampling rate is low and unstable (<50Hz vs. >100Hz), the noise is rather high. Derawi et al. [START_REF] Derawi | Unobtrusive User-Authentication on Mobile Phones using Biometric Gait Recoginition[END_REF] pointed up that impact by redid Holien's work [START_REF] Holien | Gait Recoginition under non-standard circumstances[END_REF] using MS instead of SS and achieved EER of 20.1% compared to 12.9%. Table 1 summarized gait authentication approaches and their performances with various evaluation metrics such as Equal Error Rate (EER), Recognition Rate (RR), etc. on both SS and MS.

Methodology

We pay particular attention to the position of mobile device. It is put freely inside the trouser pocket. This position turns out to be the most appropriate for the mobile phone bearer [START_REF] Breitinger | User Survey on Phone Security and Usage[END_REF]. The authentication method is implemented by machine learning approach. Acquired gait signal is precisely segmented into patterns containing a sequence of gait cycles using our segmentation algorithm. Features are then extracted in time and frequency domains. Subsequently, feature subset selection algorithms are applied to find the best feature subset giving the most accuracy rate as well as reducing feature dimension. Finally, Support Vector Machine (SVM) classifier is applied to obtain the last model. A detailed description of milestones in gait authentication will be explained in the following.

Data Acquisition

We perform our study on a Google Android HTC Nexus One mobile phone. The authentication mechanism is constructed based on gait signal acquired by a built -in accelerometer. Acceleration forces acting on the phone are measured in three spatial dimensions (X, Y, and Z as illustrated in figure 1(a)) when subjects are walking. Based on the relationships between gravity, acceleration and motion, we present the output of accelerometer as 3-component vectors

A = [a X , a Y , a Z ] (1)
where a X , a Y , a Z represent the magnitude of the acceleration forces acting on three directions respectively. Because of the accelerometers characteristics, its sensing is very sensitive to mobile installation. Normally in fact, it is impossible to ensure the phone will always be at a fixed orientation and position all the time without additional accessories. Two issues could occur concurrently: (1) misplacement and (2) disorientation errors (figure 1(b-d)). From our observation, the impact of misplacement does not significantly affect accelerometers sensing axes once it is put in the trouser pocket. It is easily solved without exploiting more information.

Looking into the case of disorientation error, as accelerometer senses acceleration forces acting on three dimensions of the phone, acquired signals will be contaminated if it is not always fixed correspondingly to its bearer. Acceleration vectors should always be represented in a constantly referred coordination system instead of an unstable one (mobile coordinate system in this case). To do this, an additional built-in magnetometer is used along with the accelerometer. In our study, Earth is considered as the referred context. A rotation matrix is calculated based on the yaw, pitch, and roll angles which represent the angle changes between mobile and Earth coordinate system. These angles are determined by the combination of magnetometer and accelerometer.

In summary, two kinds of information are determined to construct an effective gait authentication model: (1) yaw, pitch and roll angles determined before users start to walk and (2) gait signal of individuals. A scenario to acquire these values is explained meticulously in section 4.2.

Data Pre-processing

Signal Transformation

As gait signals of individuals are acquired with arbitrary installations. Thus, the first step is standardizing raw signals to eliminate the impacts of disorientation and misplacement errors.

Disorientation Errors Elimination

Denote A = [a X a Y a Z ] as the raw acceleration vector corresponding to mobile coordinate system. To transform the acceleration vector A to acceleration vector A = [a X a Y a Z ] corresponding to the Earth coordinate system, we multiply A by a rotation matrix R as following

A = A • R (2)
The rotation matrix R is calculated from yaw (α), pitch (β), roll (γ) angles, which represent three composed rotation that move an unstable frame C M (mobile coordinate) to a given referred context C E (Earth coordinate). In other words, α, β, γ angles denote the angles of rotating C M about α, β, γ respectively. The rotation matrix R can be formulated as

R (α, β, γ) =   cos α cos β cos α cos β sin γ -sin α cos γ cos α sin β cos γ + sin α sin γ sin α cos β sin α sin β sin γ + cos α cos γ sin α sin β cos γ -cos α sin γ -sin β cos β sin γ cos β cos γ   (3)
Note that we assume once mobile device is fixed on a rigid body, its orientation is kept unchanged with respect to that of the rigid body during walking. This means the relative position between C M and C E is also unchanged. Thus, the three angles and R are constant.

Theoretically, the phone should be calibrated according to its bearers context. Its purpose aims to make sure accelerometer will precisely sense gait signals in 3 dimensions corresponding to subjects walking direction. However, it is such a challenge to determine the relative position of mobile phone and its bearer with limited existing mobile resources. There is a restriction when considering Earth coordinate system as the fixed context. In this method, mobile orientation is calibrated to make the phone always parallel to the ground. Its Z-axis points toward the sky and perpendiculars to the ground. Therefore, Z-axis coincides with bearers upright. X and Y axes are always tangential to the ground and point towards the East and the magnetic North Pole respectively (figure 2(a)). Acceleration forces acting on each X and Y axis will be sensed imperfectly. However, this minor limitation does not adversely affect our mechanism. We found that although the gait signals recorded at X or Y axis are imperfect, the total acceleration forces of these two axes are guaranteed to be accurate. Thus, calibrating Z-signal precisely is necessary and efficient in this step. The authentication is constructed regardless of discretely calibrating X and Y axis signals.

Misplacement Errors Elimination

When the phone is put in the subjects trouser pocket, it lays around his/her thigh. From our observation, walking is a slow activity with a moderate fluctuation. Consequently, any strong acceleration is likely to last no longer than a few tenths of a second. Furthermore, once the phone is placed close to a joint of the leg, output signals are dominated by gravitational signals [START_REF] Kern | Wearable Sensing to Annotate Meeting Recordings[END_REF]. The influence of misplacement in this case is not considerable and it can be reduced by applying a low-pass filter to eliminate detail components in the signal. This filter is described in the following section.

Time Interpolation and Noise Elimination

As the mobile accelerometer is power saving designed to be simpler than standalone sensors, its sampling rate is not stable and entirely depends on mobile OS. The time interval between two consecutive returned samples is not a constant. The sensor only outputs value when the forces acting on each dimension have a significant change. The sampling rate of our device is approximately 27 Hz. Therefore, acquired signal is interpolated to 32 Hz using linear interpolation to ensure that the time interval between two samplepoints will be fixed.

When accelerometer samples movement data by user walking, some noises will inevitably be collected. These additional noises came from various sources (e.g., idle orientation shifts, screen taps, bumps on the road while walking). Moreover, mobile accelerometer produces numerous noises compared with standalone sensors since its functionality is fully governed by mobile OS layer. A digital filter needs to be designed to eliminate noises and reduce the impact of misplacement error concurrently. Multi-level wavelet decomposition and reconstruction method are adopted to filter the signal.

Fig. 3. Multi-level wavelet decomposition

According to figure 3, original signal is denoted by S(n). High-pass filter and low-pass filter are denoted by HF and LF. Within each level, the outputs from high-pass filter are known as detail coefficients. On the other hand, low-pass filter outputs contain most of the information of the input signal. They are known as coarse coefficients. The signal is down-sampled by 2 at each level. Coefficients obtained from the low-pass filter are used as the original signal for the next level, and this process continues until the desired level is achieved.

In contrast, reconstruction is the reverse of decomposition process. To eliminate noises, we assign the detail coefficients to 0. The reconstruction of the signal is computed by concatenating the coefficients of high-frequency with lowfrequency. In this study, the Daubechies orthogonal wavelet (Db6) with level 2 is adopted for reducing noise and eliminating the impact of misplacement error simultaneously.

Data Segmentation

Segmentation is the most important step that could directly affect to the quality of learning algorithms. As already stated, gait authentication is based on walking style of individuals. Meanwhile walking is a cyclic activity. Acquired signal should be segmented according to gait cycles instead of a fixed time interval (e.g. 5 or 10 seconds) like previous works [START_REF] Hestbek | Biometric Gait Recognition For Mobile Devices Using Wavelet Transform And Support Vector Machines[END_REF][START_REF] Nickel | Classifying Accelerometer Data via Hidden Markov Models to Authenticate People by the Way they Walk[END_REF][START_REF] Nickel | Classificatoin of Acceleration Data for Biometric Gait Recognition on Mobile Devices[END_REF].

Fig. 4. Illustration of a gait cycle

Gait cycle is defined as the time interval between two successive occurrences of one of the repetitive events when walking [START_REF] Whittle | Gait analysis an introduction 4th edition[END_REF]. In other words, two consecutive steps form a gait cycle. As shown in figure 4, the cycle starts with initial contact of the right heel, and then it will continue until the right heel contacts the ground again. The left goes through exactly the same series of events as the right, but displaced in time by half a cycle.

When the subject walks, the movement of thigh will be from back to front. In addition, at the time the heel touches the ground in phase "a" or phase "g" as in figure 4, the association between ground reaction force and inertial force together make the transformed Z-axis signal strongly change and form negative peaks with absolute high magnitudes. These peaks are considered as marking points used to distinguish separated gait cycles. From our previous work [START_REF] Thang | Gait Identification Using Accelerometer on Mobile Phone[END_REF], we designed an algorithm to detect these points. The algorithm filters noisy peaks based on a threshold calculated by mean and standard deviation. However, we recently observed that this threshold is not always robust especially in case subject walks with light steps. In this case, marking points are not displayed vividly. Thus, we improve the segmentation capability by applying an additional autocorrelation algorithm to estimate the approximate time gap tg between two consecutive gait cycles. Unlike previous works, tg is assumed to oscillate around a pre-defined fixed range [START_REF] Yuexiang | Gait Authentication Based on Acceleration Signals of Ankle[END_REF][START_REF] Derawi | Unobtrusive User-Authentication on Mobile Phones using Biometric Gait Recoginition[END_REF]. In fact, such range is not robust since user can walk with arbitrary velocities. tg should be dynamically calculated based on each characteristic of the gait signal.

First, the autocorrelation algorithm is applied to the transformed Z-axis data to determine the regularity of the signal.

A m = N -|m| i=1 x i x i+m (4)
where A m is the autocorrelation coefficient, x i is the time series data point, x i+m is the time-lagged replication of the time series.

Then A m is normalized to [0, 1] by dividing to A 0 .

A m = A m A 0 with A 0 = N i=1 x 2 i ( 5
tg = t(A k ) ( 6
)
where t(i) is the time-lagged of point i.

Denotes P = p i as the set of negative peaks2 obtained when passing through a filter described in [START_REF] Thang | Gait Identification Using Accelerometer on Mobile Phone[END_REF]. From Eq. 6, the distance between two marking points is estimated to be a definite amount of tg. Unusual peaks in P which do not fall to these positions are excluded to obtain the optimal set of marking points P (figure 5(b)). The segmentation procedure is summarized as follows

Algorithm 1 Gait Signal Segmentation

Input: Time series of transformed Z-axis gait signal SZ , number of gait cycles (GCs) n per segment, number of overlapping gait cycles o with n = ok, k ∈ N Output: sets of separated segments Mi, Mi contains n consecutive GCs and overlaps o GCs with Mi-1 1. Extract set of negative peaks P using T = µ + kσ as described in [START_REF] Thang | Gait Identification Using Accelerometer on Mobile Phone[END_REF] on SZ . 2. Calculate the auto-correlation coefficients Am of SZ using Eq. 5 3. Find A k and calculate the time gap t between gait cycles using Eq. 6 4. Filter unusual peaks in P based on their positions and values for (each peak p in P ) do if (position of(p) -position of(p -1) < αt) then if value of(p) < value of(p -1) then remove(p) else remove(p -1) end if else if (position of(p) -position of(p -1) < βt) then if position of(p + 1) -position of(p) < γt then remove(p) else remove(p + 1) end if else remove(p) end if end for 5. Extract gait cycles GCs based on filtered P . GC(i) = S pos(p i+1 ) pos(p i ) 6. Remove unusual GCs if their length is significant unlike t to obtain best gait cycles 7. Combine n consecutive GCs to form a segment for (i = 0, j = 0; j < length(GCs)n; i + +, j+ = o) do Mi = GC j+n j end for return Mi

In this algorithm, user-defined values such as α, β, γ are estimated from experiment to precisely determine position of peaks representing the beginning of a gait cycle in all cases (e.g. α = 0.25, β = 0.75, γ = 0.16 was used in our work). From our study, gait signal is segmented into separated patterns in which each pattern contains n = 4 consecutive gait cycles and overlap n/2 gait cycles from the previous one. Features are extracted in every separated pattern on both time and frequency domains to obtain feature vectors used for classification.

Feature Extraction and Classification

In this stage, three phases are investigated to obtain an optimal classification model: First, possible features on both time and frequency domains are extracted on 3 types of acceleration data including Z-axis signal a Z , magnitude

m XY Z = a 2 X + a 2 Y + a 2 Z and sum of acceleration forces of X -Y axes m XY = a 2 X + a 2 Y .
As discussed in section 3.2, X -Y signals could not be distinguished with current limited resources on mobile devices. Hence, we consider the sum of forces acting simultaneously on both axes. Second, feature subset selection algorithms are applied for obtaining the best feature set. Feature subsets are selected based on the accuracy criterion of the learning algorithm. Finally, the best feature subsets are classified using Support Vector Machine (SVM) classifier with Radial Basis Function (RBF) kernel.

Time Domain Features

We extract features which can represent characteristics of gait signal in time domain including

• Average maximum acceleration

avg max = mean(max(GC i )) n i=0 (7)
• Average minimum acceleration avg min = mean(min(GC i )) n i=0 [START_REF] Terada | Performance of gait authentication using an acceleration sensor[END_REF] • Average absolute difference

avg abs dif f = N i=1 |x i -x| (9)
• Root Mean Square

RM S = 1 N N i=1 x 2 i ( 10
)
• 10-bin histogram distribution

his dist = n j 9 0
with n j = i x i size(bin j ) where

j∆ j 10 ≤ x i ∈ bin j < (j + 1)∆ j 10 , ∆ j = max -min (11)
• Standard deviation

σ = 1 N -1 N i=1 |x i -x| (12)
• Waveform length

wl = N -1 i=1 |x i+1 -x i | (13)
where x i is the data point in time series of a segment, n is the number of gait cycles GC in the segment, N is the total number of data point in the segment. These features above are extracted on 3 types of signal including a Z , m XY Z and m XY

• Cadence period

T cad = n i=1 l(GC i ) n (14)
• Cadence frequency

f cad = n n i=1 l(GC i ) ( 15
)
where l(GC i ) is the length of gait cycle i.

Frequency Domain Feature

• 40 first FFT coefficients

f f t = X k 39 k=0 where X k = N -1 n=0
x n e -j2πkn N (16)

• 40 first DCT coefficients dct = X k 39 k=0 where X k = 1 2 x 0 + N -1 n=1 x n cos π N n k + 1 2 (17)
Similar to features on time domains, these coefficients are extracted on a Z , m XY Z and m XY . As stated before, the walking speed of users in fact is not absolutely constant. Hence, the length of gait cycles is not stable. Calculating coefficients on frequency domain (e.g. FFT, DCT) requires window frames (or patterns) have the same fixed length. Meanwhile, the length of gait cycles fluctuates slightly around time gap tg calculated in section 3.3. As a result, the number of data points in every gait cycle needs to be normalized by using our proposed algorithm [START_REF] Thang | Gait Identification Using Accelerometer on Mobile Phone[END_REF] to make sure the frequency coefficients are calculated properly.

Feature Subset Selection

Total 29 features are extracted in both time and frequency domains. However concatenating whole features to form a final feature vector whose dimension is grown up to be supreme not only require a lot of computational tasks but also return a suboptimal result. Only features that are highly discriminative between each individual should be selected. We applied algorithms using hill-climbing strategies to select the best feature subset from the feature pool. ------------wlXY Z 94.92

Sequential Forward Selection (SFS) Algorithm SFS algorithm was originally proposed by Whitney [START_REF] Whitney | A Direct Method of Nonparametric Measurement Selection[END_REF]. The idea of SFS algorithm is to determine the best feature from the feature pool which increases the most classification accuracy and concatenate it to the current feature vector at each step. SFS algorithm performs a greedy optimization in the feature space. However, the main drawback of this algorithm is called "nesting effect" in which discarded features will not be picked anymore. Hence, a local maximum of the feature space is usually found only.

Sequential Floating Forward Selection (SFFS) Algorithm SFFS algorithm [START_REF] Pudil | Float search methods in feature selection[END_REF] is the improvement of SFS to avoid nesting effect. In SFFS, a new feature is determined and concatenated to the current feature vector using the SFS strategy. Additionally, there is a backward phase to recheck to current feature vector after concatenating a new feature. Features in the selected set are conditionally excluded and moved back to feature pool until no improvement is achieved to the previous sets. Table 2 illustrates the most significant feature subset selected by SFS and SFFS algorithms. The feature vector is initialized by empty. Each row represents a selected feature that increases the classification accuracy rate. By applying SFS and SFFS separately, the number of final feature subsets is reduced from 29 to 12 and 13 respectively. This is not only help to reduce processing time and computational tasks of learning and prediction but also ameliorate the classification accuracy. It will be shown more from our experiment.

Experiments

Data Collection Scenario

We experimented on data collected from built-in accelerometer and magnetometer in Google Nexus One mobile phone 3 . The sampling rate of both sensors is approximately 27 Hz by setting to SENSOR DELAY FASTED mode on Android SDK. In this study, we would like to construct a more realistic dataset. In reality, two main factors including the effect of footgear and mobile installation often occur that could significantly affect gait of individuals. Hence, a scenario is designed to construct the dataset in which acquired gaits are collected under the influence of such factors. During experiment process, each volunteer will wear all three types of footgear including sleeper, sandal and shoe. The scenario is designed as following:

-Preparation (1 st ) phase: Volunteers wear 1 of 3 footgear types and put the mobile phone in their trouser pocket according to any position and orientation. Subsequently, they will be asked to stand still for few seconds. During this time, the accelerometer and the magnetometer will be activated to collect values for determining yaw, pitch and roll angles. Subsequently, the rotation matrix will be calculated and stored inside mobile storage for acceleration vector transformation later.

-Collection (2 nd ) phase: After the rotation matrix is stored successfully, volunteers will perform walking activity around 36 seconds on the ground floor. They will be asked to walk as naturally as possible. During this time, accelerometer will be activated to collect gait signals.

A total of 38 volunteers including 28 males and 10 females with the average age from 24 to 28 participated to our dataset construction. Each volunteer will perform around 18 laps. Each lap includes two phases above. Before starting a new lap, they will change the footgear and install the mobile to another orientation and position. Note that since the transformation matrix is always estimated in the preparation phase before volunteers start walking. Hence we have a constraint that when volunteers perform walking, the mobile will not change its position and orientation. To ensure that, we ask volunteers to wear trousers having the narrow pocket (e.g. the jean trouser). Totally, we acquired 24624 seconds walk of 38 volunteers.

Overall Gait Identification Result

Total 8500 patterns are extracted from the dataset by using our segmentation algorithm. Around 8500 38 patterns corresponding to each volunteer are split into two separated parts. The first part is used for training (T-part) and the remaining is used for prediction (P-part). We used libsvm 4 [26] as the tool to perform SVM with RBF kernel. The performance of RBF kernel fully depends on selecting parameters (C, γ). In order to construct an optimal SVM model, we perform a strategy to find the good (C, γ) yielding the best classification result. Features described in section 3.4 are extracted on both T-part and P-part. To deal with over-fitting issue, 10-fold cross validation is applied on T-part with various (C, γ). The (C, γ) yielding the best cross validation accuracy will be selected. According to [START_REF] Chang | LIBSVM: a library for support vector machines[END_REF], we tried exponentially growing sequences of C and γ to identify the 'coarse' pair first C = 2 -5 , 2 -4 , 2 -3 , . . . , 2 15 and γ = 2 -15 , 2 -14 , 2 -13 , . . . , 2 3 . Subsequently, a more detailed search is performed to identify a finer (C f , γ f ) yielding an optimal cross-validation accuracy. The best (C f , γ f ) = (2 3.5 , 2 -5. 25 ) is identified at the cross-validation accuracy of 98.71%. Then, whole T-par t is trained again using (C f , γ f ) to obtain the final SVM model. An overall accuracy rate approximately 94.93% is achieved when using such model to predict T-part. Additionally, by applying the SFS and SFFS algorithm, the dimension of feature vectors is reduced and the classification accuracy is slightly increased as well. The processing time is also ameliorated significantly (table 3 and figure 6(b)). By applying SFFS, the prediction time only costs 411 ms per sample using mobile resources. In authentication mode, a task requires to predict on 9 consecutive samples (discussed in 4.3). It costs less than 4 seconds to make a decision. This is an acceptable level compared to original case (≈ 20 seconds). Note that processing time is very important in mobile applications since we aim to deploy a lightweight authentication model running directly on mobile phone. Nowadays, it is likely to be optimized by its weight, power and size rather than computational power (e.g. CPU, memory). Hence reducing feature dimension will help the mobile device to perform classification task more quickly so that the interaction between the phone and its user is also improved.

Impacts of Installation Error

Before discussing the impact of mobile installation, we first compare the performance of segmentation based on gait cycles against previous studies used fixed size segmentation [START_REF] Hestbek | Biometric Gait Recognition For Mobile Devices Using Wavelet Transform And Support Vector Machines[END_REF][START_REF] Nickel | Classifying Accelerometer Data via Hidden Markov Models to Authenticate People by the Way they Walk[END_REF][START_REF] Nickel | Classificatoin of Acceleration Data for Biometric Gait Recognition on Mobile Devices[END_REF]. Since walking is a regularly cyclic activity, it is relatively easy to perceive that segmentation based on gait cycle always yields a better classification result compared with based on a fixed length (table 4(a)). Second, we analyze the impacts of installation errors to segmentation algorithm and the classification accuracy. Note that a perfect accuracy rate of segmentation is achieved when using our algorithm with the transformed Z-signal.

All gait cycles are detected and segmented correctly. Table 4(b) illustrates the performance of segmentation task with/without fixing disorientation error. As discussed above, the periodicity of walking is only represented well in transformed Z-signal. Without rectifying such issues, the segmentation algorithm could not determine precisely the regularity of gait cycles caused by Z-signal's instability. Therefore, each segmented pattern could not only represent a sequence of consecutive gait cycles well. That leads features extracted from these patterns could not represent the characteristics of walking style of individuals well. As a result, the classification accuracy rate is contaminated. Even with using segmentation based on fixed length, the best achieved classification rate at length = 3000ms is also worse (79.53%).

Authentication Result

The difference between authentication and identification is that authentication performs binary classification tasks meanwhile identification performs multi-class tasks. Based on the achieved results in identification, we also do an experiment on authentication to determine how effective of our mechanism when it operates under authentication mode. Since the unbalance of imposter vs. genuine data (37 imposter vs. 1 genuine for each genuine person) could negatively affect the performance of classification tasks [START_REF] Weiss | Learning when training data are costly: The effect of class distribution on tree induction[END_REF]. Hence, we will rearrange the data to make it fit to 3 1 imposter data genuine data ratio corresponding to each genuine. To make a fair evaluation, selecting imposter data will be based on ascending order of the most misidentification in confusion matrix as shown in figure 6(a). For example, subject '1' is misidentified mostly with subjects '26', '2' and '24'. Hence, data of '26', '2' and '24' will be prior to be selected as imposters of subject 1 first. The remaining ones are selected randomly from the set of remaining subjects to achieve the ratio of 3:1.

As illustrated in figure 7, we achieved the False-Match-Rate (FMR) perfectly (0%). However, the False-Not-Match-Rate (FMNR) is still unacceptable (19.35%). In authentication, FMR and FMNR reflect the reliability and the friendliness of the system respectively. The problem that causes the high FMNR is the unbalance of imposter data vs. genuine data (3:1) issue. That would lead true genuine is recognized as imposter frequently. To reduce the FMNR without increasing FMR, we apply a scheme that is similar to [START_REF] Nickel | Classifying Accelerometer Data via Hidden Markov Models to Authenticate People by the Way they Walk[END_REF]. From our dataset, we can extract n patterns from a lap of each subject. Instead of considering n as separated testing samples as usual, whole n patterns will be considered as genuine if there are m genuine patterns detected in n. That means each authentication task will perform on a sequences of n consecutive patterns to make a decision. From our experiment, we choose m = 2 and n = 9 which is significantly smaller than [START_REF] Nickel | Classifying Accelerometer Data via Hidden Markov Models to Authenticate People by the Way they Walk[END_REF]. The achieved FMR and FNMR are 0% and 3.89% respectively which is remarkably comparative with other works [START_REF] Hestbek | Biometric Gait Recognition For Mobile Devices Using Wavelet Transform And Support Vector Machines[END_REF][START_REF] Nickel | Classifying Accelerometer Data via Hidden Markov Models to Authenticate People by the Way they Walk[END_REF][START_REF] Nickel | Classificatoin of Acceleration Data for Biometric Gait Recognition on Mobile Devices[END_REF][START_REF] Frank | Activity and Gait Recognition with Time-Delay Embeddings[END_REF][START_REF] Derawi | Unobtrusive User-Authentication on Mobile Phones using Biometric Gait Recoginition[END_REF][START_REF] Sprager | A cumulant-based method for gait identification using accelerometer data with Principal Component Analysis and Support Vector Machine[END_REF]. In this paper, we proposed a novel lightweight but highly reliable gait authentication on mobile phone. Although the quality of built-in sensors is low (the sampling rate is only 27Hz), the achieved results are very considerable. It reflects high potentials to deploy our mechanism to support current active mobile authentications such as PIN or password in reality. Since there is currently no public dataset in this field, the comparison between related works is only relative. Therefore, a more realistic dataset is also constructed to evaluate our mechanism fairly. Nevertheless, there is a minor unrealistic constraint in this study. We assumed that the phone is fixed at rigid body during walking phase. Furthermore, the influence of many environment factors such as human emotion, time effect, and ground materials to individual gait is not explored. Hence, such issues will be considered deeper in future. Moreover, since many excellent sensors are more and more integrated on modern mobiles nowadays (e.g. gyroscope, tilt sensor), mining all sensor resources to perfect a practical authentication model is our future road map.

Fig. 1 .

 1 Fig. 1. (a) Mobile coordinate system, (b) misplacement error, (c) disorientation error and (d) both cases

Fig. 2 .

 2 Fig. 2. (a) Mobile orientation after applying rotation matrix, (b) the relative position between the phone and its wearer

Fig. 5 .

 5 Fig. 5. (a) Auto-correlation coefficients with the estimated tg, (b) detected marking points in Z-signal Figure 5(a) illustrates autocorrelation coefficients A which represent the regularity of the walking signal. The approximate time gap of gait cycles is determined by the gap between two red peaks in which the first one correspond with A 0 . The remaining A k is detected by a designed peak detection algorithm.

Figure 6 (

 6 a) illustrates the confusion matrix of prediction result.

Fig. 6 .

 6 Fig. 6. (a) Confusion matrix of the gait recognition using SVM and RBF kernel with C = 2 3.5 , = 2 -5.25 , (b) the classification accuracy of various amounts of feature subsets by applying SFFS and SFS algorithm

Fig. 7 .

 7 Fig. 7. FNMR of each 38 subjects at FMR=0% before (blue-columns) and after (redline) applying voting scheme m = 2, n = 12

Table 1 .

 1 State of the art gait authentication using Standalone (S) and Mobile sen-

	sor (M) including Accelerometer (A), Rotation Sensor (R) by approaches: Template
	Matching (TM), Machine Learning (ML) and Hybrid (H)
	Previous Sensor/	Location Methods	No. Subjects	Results
	Works	Sampling rate
	[14]	MA / 27Hz	T Pocket TM, ML	11	79.1%, 92.7% RR
	[6]	SA / 50Hz	Ankle	H	22 (16M 6F)	3.03% EER
	[5]	9 SR	Body	ML (LDA)	30 (25M 5F)	100% RR
	[15]	MA	T Pocket ML (SVM)	36	HTER: 10.1%
	[7]	SA / 40Hz	Ankle	H	22	3.27% EER
	[16, 17] MA / 120Hz Hip	ML (HMM)	48 (30M 18F) 6.15% EER, 5.9%
		MA / 45Hz		ML (SVM)		FMR, 6.3%FNMR
	[8]	SA / 100Hz	Ankle	TM (Euclidean)	10	20% EER
	[18]	MA / 25 Hz T Pocket ML (SVM)	25	100% RR
	[9]	SA / 100Hz	Hip	TM (PCA)	60(43M 17F)	1.6% EER
	[19]	MA / 45Hz	Hip	TM (DTW)	51 (41M 10F) 20% EER
	[20]	MA / 37Hz	Hip	ML ( SVM)	6	90.3 3.2% RR
	[10]	SA / 16Hz,	Ankle	H (Euclidean)	21 (12M 9F)	5% EER
		100Hz	Pocket	H (Manhattan)	100 (70M 30F) 7% EER
			Arm		50(33M 17F)	10% EER
			Hip		30 (23M 7 F) 13% EER
	[11]	SA / 100Hz	Body	TM(NN)	30	96.7% RR
	[12, 13] SA / 256Hz

Waist TM(cross-corr.), H 36 (19M 17F) 6.4 %, 10%, 19% (FFT, histogram) EER

Table 2 .

 2 Feature subset(s) selection using SFS and SFFS algorithms

	#	SFS Algorithm Feature Accuracy (%) Feature SFFS Algorithm Accuracy (%)
	1 dctXY Z	75.27	dctXY Z	75.27
	2 dctXY	88.67	dctXY	88.67
	3 his distZ	90.86	his distZ	90.86
	4 wfXY	92.52	f f tXY	91.70
	5 wfZ	93.29	f f tXY Z	93.62
	6 avg minXY Z	93.43	avg abs dif fXY Z	94.01
	7 dctZ	93.50	dctZ	94.25
	8 T cad	93.73	avg abs dif fXY	94.46
	9 f f tXY	94.04	avg abs dif fZ	94.67
	10 f f tXY Z	94.64	f cad	94.69
	11 avg abs dif fXY Z	94.78	avg minZ	94.81
	12 avg maxZ	94.90	avg maxZ	94.85
	13

Table 3 .

 3 The performance of reducing feature dimension versus non-reducing case

		No. Subsets Accucary Loading Time Prediction Time
	Original	29	94.34%	205897 ms	2280 ms
	SFS	12	94.90%	86799 ms	398 ms
	SFFS	13	94.93%	84223 ms	411 ms

Table 4 .

 4 (a) Improvements of segmentation based on gait cycles compared with fixed length, (b) the influence of disorientation error to the effectiveness of classification mode

		(a)		(b)
	Segmentation method Accuracy 3000ms 87.88%	Segmentation Fixing dis-Accuracy method orientation
	Fixed length	6000ms	87.78%	Fixed length	No	79.53%
		9000ms 2 gait cycles 92.26% 84.73%	Our algorithm	No Yes	84.03 % 94.93%
	Gait cycle	4 gait cycles 94.93%
		8 gait cycles 90.94%

Report of the Wireless Intelligence Company [J. Gillet, "Wireless Intelligence: Global mobile connections surpass 6 billion by year-end",

2011]

Negative peaks are defined oppositely with peaks pre-defined in[START_REF] Thang | Gait Identification Using Accelerometer on Mobile Phone[END_REF]. Negative peaks are data points that its value is lower than its predecessor and successor.

Access http://www.gsmarena.com/htc_google_nexus_one-3069.php for its specification

Software available at http://www.csie.ntu.edu.tw/ ~cjlin/libsvm

Acknowledgments. "This research was supported by the MSIP (Ministry of Science, ICT&Future Planning), Korea, under the ITRC (Information Technol-ogy Research Center) support program (NIPA-2013-H0301-13-3005) supervised by the NIPA (National IT Industry Promotion Agency)"